Algorithm: process/instructions -- programming skills

Abstraction: how to store data

Algorithm vs. program

Power:
Get input base, power
Set ans = 1 (multiplication)
Set count = 0 (addition/counter)
If count < power
1. Multiply answer by base
2. Add 1 to count
3. Go back to if line
Otherwise, output answer
→ ans = ans * base

Casting: x = bool(x)
False: 0, 0.0., ‘’
True: all else
Add strings “str” + “str” or “str“ + “int”
Float = decimal
Boolean = True, False → type matters (use ==)

5 / 3 = 1.6666667
5 // 3 = 1 (cuts off decimal part) → not rounding
5 % 3 = 2 (remainder)
Negative: find biggest multiple of -n that is still less than -m (find distance)
-5%10 = 5

To change type: int(“45”), str(1234), int(5.67) = 5 (truncates), round(5.67) = 6

Interpreter/Shell: >>> (always outputs answer)
Editor: print(____, ___, ____) → No need for type changing when printing

Comments:
# single line
“““
multi-line
“““
x = x+2 → x += 2
x = x*2 → x *= 2 or if string: x = ‘2’ → x *= 2 = ‘22’
> < >= <= == : must be same type on both sides
- String comparison: later letter are greater “boo” > “ahh” (compare 1st, if same compare 2nd)
length doesn’t matter
Abstraction: agreement about how to represent information at different levels
Python code
Interpreter
Translate → something else
Output ← result
Parsing (levels of abstraction → what code we write, how Python reads it)
Function → operator → tokens
Tokenizing: breaking text into tokens/words
Parsing: imposing structure/meaning on tokens
(1) Runtime error​ (NameError) after parsing, after tokenizing, error while running code
Bytecode (set of instructions that computer knows how to run) → variables, literals, functions
Program memory
- Constant table, variable table, stack (stores stuff → loads in stack for operation)
- Once you use a loaded variable, is gets deleted (must reload)
- Only need to store once
Python Bytecode bucket #
X=5 LOAD_CONST 1 (5)
Y=7 STORE_FAST 0 (x)
Z = x+y LOAD_CONST 2 (7)
STORE_FAST 1 (y)
LOAD_FAST 0 (x)
LOAD_FAST 1 (y)
BINARY_ADD
STORE_FAST 2 (z)
Store_fast: loads const into variable
Load_fast: load variables
Can use dis.dis(myfunc) to see breakdown

(2) Logical Error​: parses fine, runs fine, but is logically incorrect
** can’t be recognized by Python
(3) Syntax Error
Code will not run, even if error is in last line (Bytecode will not load)

decimal system → $7.34 = 7*10​2​ + 3*10​1​ + 4*10​0​ (powers of 10)

Binary: 0 1 (powers of 2)
1 0 1 = 1(2​2​ ) + 0(2​1​ ) + 1(2​0​ ) = 5
0
1
10
11
100
101
110
111
1010 = 1(2​3​) + 0(2​2​) + 1(2​1​) + 0(2​0​) = 10

**Largest n-digit number in binary = 2​n​-1

Bit = a single 0 or 1
8 bits = 1 byte (max binary = 255)
4 bits/half-byte = hexadecimal system (base 16) 0 1 2 3 4 5 6 7 8 9 A B C D E F
A = 10
B = 11…
1F = 0001 1111

ASCII: assigning 7 bits to an english character (encoding)

- Assigns any characters (numbers, symbols, letters) to binary code
- 1 byte of info
- Allows us to encode strings
UniCode: other characters in diff languages
- 2-6 bytes
- Emojis+much more info

2’s compliment: avoids +0 and -0

If positive
1. Whole number in binary (add zero at left)
If negative
1. Add 1
2. Flip sign
3. Convert to binary
4. Flip all bits 1→ 0, 0→ 1
5. Keep 1 at left-most position to indicate negative (sign bit)
OR
1. Flip bits
2. Convert to whole number
3. Multiply by -1 and subtract 1

Color = pixels - RGB combinations → need 3 bytes to store information (8 bits each since 255)
Greyscale = 1 byte

Functions
function(arguments)
print( ) = side effect → NONE since it doesn’t return a value
Libraries: import __library__ (i.e. math) → math.degrees(math.pi) = 180.0
When making a function:
1. Name
 2. Input
3. Body
4. Output

def birthdaySong(name):
print(“Happy birthday to you”)
print(“Happy birthday to you”)
print(“Happy birthday dear” + name)
print(“Happy birthday to you”)
(no need for output line)
birthdaySong(“Sam”)
print(“HERE”, birthdaySong(“Stella”)) = NONE

**function always returns something: even if you don’t return anything -> return “NONE”

def randomFunction(x):
x = x+20
return x /2 **more useful is you want to use the output for something else
print(randomFunction(4) + randomFunction(2))

** exits immediately after returning → can fix by using if loop

global​ y inside function → scope inside function or globally
Global vs. in function are not connected

Combining Booleans: logical operations → ___ and ___, ___ or ___, not( )
not(x<5) → x>=5

Conditionals → control structures to change direction of code (make choice)

if <boolean value>:
<conditional body>
if <boolean expression>: 1 else per if statement (only connected to if directly preceding it)
<body_if_true>
else:
<body_if_false>
if <boolean expression_A>: when if is true, all elif’s are ignored (elif’s checked in order)
<body if A true>
elif <___ connects to if before it

Nesting control
Bits = electrical voltage (low =1, high=1)
Logical gates: hardware’s boolean operations (input/output instead of true/false)
- AND (rounded square) A^B
- OR (rounded triangle) AVB
- NOT (triangle with circle at point) -A
- NAND (circle in front of AND) -(A^B)
- NOR (circle in front of OR) -(AVB)
- XOR (if exactly 1 and 0) A⊕B

Input as switch (off/on) + lightbulb as output (off/on)

Algorithm using gates: build generalizable process

1. Look for which letter is always 1 or 0
2. Decide condition for remaining letter in combination to constant letter
3. Connect truth table to circuit

Writing real algorithms:

1. Addition: to fix this, output + carry: output = 0 = XOR, carry = 1 = AND
X Y X+Y

1 1 **10

1 0 1

0 1 1

0 0 0
Half adder: 1 bit addition (9+7)
Full adder: 17 + 25 C_in = value carried in from previous computation
C_out = regular carry: need at least 2 1’s to be 1 = X⊕Y⊕C​in
N-bit adder: chain together full adders → replace each full adder with black box
Each black box makes Cout that becomes Cin for next black box
Each number (X,Y) in binary from switches on or off

Boolean expression → truth table → circuit

Set, Reset, Previous output
S R P Result

1 1 1 0

1 1 0 0

1 0 1 1

1 0 0 1
 0 1 1 0

0 1 0 0

0 0 1 1

0 0 0 0

(not R since all results = 0 when R = 1) and (S or P since results = 1 if at least S or P is 1)

→ save state even if switch is turned off

while <boolean expression>:

<loop body>
- Need update variable

for i in range(<number> plus 1 every time):

<loop body>
- Updates loop variable by itself → default +1
- 0 is implicit start
- range(start, end → up to not including)
- range(start, end, step size)

- Nested loops good for 2 dimensional datasets

for i in range(1, 5):
for j in range(1, 5):
print(i, j)

String is iterable type → can loop over

s = “Hello”
for c in s:
print(c + “!”) → prints each letter one at a time, lets us break up string into parts
Linear search for value in iterable value

def linearSearch(s, char):

for c in s:
if c == char:
return True
return False
Assign elements of s an index from 0 to length of s → s[]
def linearSearch(s, char):
for i in range(len(s)):
if char == s[i]:
return i → will give first instance even if repeats
 return -1 → not found in string s

def linearSearch(s, char):

i=0
while i < len(s):
if s[i] == char:
Return i
i = i+1
return -1

if c in “aeiou” → instead of c == ‘a’ or c == ‘e’ or c == ‘i’....

**can’t index in integers, only characters

For-range is best option: more options, not as complicated + needing more info
While loop necessary if range endpoint not known

hasIncreasingDigits → need indexing since we are interested in two elements at once

x = 1234
str_x = str(x)
For i in range(len(str_x)-1)
If str_x[i] >= str_x[i+1]
Return False ** write a false conditional
def hasIncreasingDigits(num):
While (num >0):
First = num % 10 → last digit
Num = num //10 → split out the last digit
If first <= num%10
Return False
Return True

Slicing
s[len(s)-1] = s[-1] = last character (negative indexes go from right to left of string)
s[1:len(s):1] = s[beginning:ending:step] → can be used to get substring of whole string
s[1::] = s[1:]

**up to and not including the ending point

“____” in s → “True” or “False” (looking at all possible substrings, any sequence of characters)

ord(“​single​ character”) = ASCII value

chr(number) = letter
Escape sequence: _____\n____ separates a string into two new lines (\\ if you want to include \)
Reading from files
Recognize new lines with \n
String methods
s.islower( ) → dot = call function on string s : checks if lowercase
s.isupper( )
s.isdigit( )
Return True or False
s.count(“string you’re looking for: can be 1 char or multiple”)
s.find(“f”) → returns index of first occurrence
s.lower( ) converts all uppercase letters to lowercase, vs. s.upper( )
** does not change original s
** set new string equal to t = s.lower( ) to save it
s.replace(“a”,”b”) replace all instances of a with b
def allunique(s):
for c in s:
if s.count(c)>1:
return False
else: return True** WRONG
return True → should be outside the loop bc you want it to test the whole string

String parsing
for word in s.split(where you want to separate):
print(word)

for word in s.split(\n): splits lines of text files

if word == “____”:
return True
return False

Input and Files

Input: x = input(“Enter something: “) → takes input in string form
print(“Hi “ + x)
Use typecast to change int(x) to integer if x is a string (can’t typecast int(“30”))
s.strip( ) removes any whitespace at beginning and end of string

f = open(“sample.txt”, “r”) # read mode

text = f.read( ) # returns a string
f = open(“sample.txt”, “w”) # write mode
f.write(“Hi class!”)
f.close( ) after reading/writing
f.readline() reads each line of text

To find # lines for each character

char = “HAMLET”
count = 0
for line in script.split(“\n”):
periodIndex = line.find(“.”) ---> finds 1st period in in line
Name = line[:periodIndex]
If name == char:
count = count +1
print(line)

MIDTERM I REVIEW SESSION

Data types:
- string str()“abcd” (char)
- Integer int()
- Float
- Boolean True/False

Code syntax:
(1) if x < 5: → if multiple if’s all will run
(2) elif x == 5:
(3) else:

for i in range(5): i = 0,1,2,3,4 (0 is beginning, 4 is ending, +1 increment)

for i in range(10,0,-1): (-1 increment)
for i in range(len(s)): all elements covered
for i in s: if you don’t care about actual index number; i takes on every element in s

x=0 must initialize first

while x < len(s):
x = x+1 must increment inside loop (x += 1)

Bytecode: order of operation

(1) LOAD_CONST: constant value (index 1) → no need to load the variable storing execution value
(2) STORE_FAST: store into variable (index 0)
(3) LOAD_FAST: load from fast table into execution space (index 0)
(4) BINARY_ADD: execute on loaded variables
(5) STORE_FAST: store value of execution into new variable in fast table (1)
** store into constant before fast
** start constant table with index 1, start fast table with index 0
Tokenizing → matching variables to values

Binary:
Unsigned binary conversion:
- Divide by 2 | remainder
 - Bring whole number factor down + continue
- Stop at ½ = 1
- Go bottom to up to determine binary
53 = 110101
53 26 1

26 13 0

13 6 1

6 3 0

3 1 1

1 1

2’s complement: ​CIRCLE

Left-most bit = sign
0010
1. Flip bits: 1101 (negative to positive, vice versa)
2. Add 1: 1110 → 1+1= 2 = 10 (1 carries over)

_​ _ _ _
Signed magnitude bit: 1 = negative, 0 = positive
Hold value

Circuits:
Look for patterns after fixing first input and combine to get boolean expression
(when x = 0, (Y__Z) notX)

Half Adder: represent binary addition

Carry = leftmost digit C_out = 1 only for AND
Output = rightmost digit
**need AND (carry) + XOR (output)

Full Adder = blackbox

- Takes in C_in, X, Y
- Spits out Sum, C_out
- Can’t add 11 and 01 with just 1 FA → need 2 (vertically taken for addition → inputs = 11 for
FA1 and 10 for FA2)
- FA1: sum = 0, carry = 1 = C_out, C_in = 0 for first FA
- C_out from FA1 = C_in of FA2
- FA2: sum = 0, carry = 1 = C_out → adds extra bit of info
Sum = 0, carry is 1
Decode file:
- Read the text in file
- Decode message
- Break string based on new lines
- Break the string based on spaces
- Casting a number using chr()
- Put a char in a word
- Put a work in a message
- Return the message

def decodeFile(filename):
f = open(filename, “r”)
text = f.read( )
f.close( )
for line in text.split(“\n”):
nextWord = “”
for word in line.split(“ “):
num = chr(int(word))
nextWord = nextWord + num
message = message + “ “ + nextWord
return message
**no return → function implicitly returns none, so printing a function without return statement will print
NONE

Data abstraction: Pixels + ASCII

Pixels: Red, green, blue: each represented by byte (8 bits per color) with values in range 1-255
4 bits of info = 1-15
Hex value: 0123457689ABCDEF (0-15, 1 character each)
#FFD700 = [15] [15] [13] [7] [0] [0] = 1111 1111 1101 0111 0000 0000 ← how gold represented
→ number represents proportion of each color
ASCII: letter, symbols, punctuation each have numbers → converted to binary
00111011 = 59 (binary) = : in ASCII

Circuit abstraction:
Half Adders: adds two binary digits (11, 10, 01, 00)
1+1 = 10 → need another output column to store carried value 1
2 inputs of single binary digits, carry number, sum
Full Adders: 3 inputs (X, Y, Cin from previous addition), output (1’s digit), carry number
N-Bit Adders: chain together full adders (adding numbers of multiple bits in length by adding single digit
numbers one by one + carrying number over)
Flip-Flops

- Converting between binary and decimal: 2’s complement

- Make slots for 64 32 16 8 4 2 1 and fill with 1 or 0
__ __ __ __ __ __ __
- For negative: add 1, find binary of absolute value of it
-27 → |-26| → 11010 → to make negative add 0 to left + flip bits → 100101
First 1 = -32
ASCII representation (unsigned)
‘A0’ = 65 48
‘C0’ = 67 48 → ​0​100011 0011000 ← add zero in front to get 8 bits/byte

For truth table, break into chunks by columns and combine boolean expression

Errors:
Syntax you see right away (print(“Uh oh))
Runtime after you run the function (print(1/0))
Logical: python won’t notice it but you’re not expressing what you want correctly

Ceiling divide: n//10 → truncates fraction part → integer divide

For each == for c in s:

EXAM I MATERIAL END

Graphics
Edit shell configuration
Change gui = none: no GUI support
Change startDir

Starter code:
from tkinter import → tkinter = graphics library

- Window that pops up

- Canvas in window that we can draw on
def makeCanvas(w, h): width and height
root Tk() → actual window
canvas = Canvas(root, width=w, height=h)
canvas.configuration(bd = 0, highlightthickness =0)
canvas.pack()
draw(canvas) → where we actually draw the design
root.mainloop() → keep window open until you close it
makeCanvas(400, 400)
Top left corner = (0,0) → x doesn’t change horizontally
y is positive downwards
def draw(canvas):
canvas.create_rectangle(100, 150, 300, 200) → (x1, y1, x2, y2)
canvas.create_oval(200, 50, 220, 300, fill = “red”, width = 10, outline = “pink”)

**width of outline 0 → infinity

**shapes layered based on order of shapes in code
**colors can be names or RBG Hex value → #______ (2 characters each for R, G, B)
** order of fill, width doesn’t matter

canvas.create_text(200, 200, text = “___”, font = “Arial 30 bold”, fill = “green”)

Coordinate = center of text location
canvas.create_line(100, 100, 300, 300, width = 20)

canvas.create_text(200, 0, text = “up high”, anchor = “n”)

**anchor = center, n, nw → if aligned in some way to box
For rectangle: top left corner(x1,y1) + bottom right corner coordinates(x2,y2)
For oval: bounding box

Drawing a grid
Left: size*(number of circles that came before) → repeated loop variable
Right: left + size

To draw first column of circles

size = 400 / (10 → number of circles you want in row)
for row in range(10):
Top = row * size
Bottom = top + size
To draw top row of circles
for col in range(10):
Left = col * size
Right = left + size
If col%3 == 0:
Color == “red”
elif...
canvas.create_oval(left, top, right, bottom, fill = “color”)

Lists

lst = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] → also iterable

lst[0] = 1
Can store multiple data types in a single list
Empty list = [ ] (same as empty string)
lst = [ 4 ] * 20

Built-in functions:
len(lst)
min(lst), max(lst) → for strings too
sum(lst) → only for numbers

Boolean comparison:[1, 2, 3, 4] == [5, 6, 7, 8] **order+length matters

- Compares them in order (first elements)
- Shorter lists are smaller than longer lists
To check empty list: check that len([ ]) == 0

lst = [7, 5, 3]
3 in lst → returns boolean
lst.count(5) = 1
lst.index(3) = 2 → returns first index of occurance

lst[:len(list)-1:2] cuts off every second element

lst = lst[1:] cut off first element
lst = lst + [1, 2, 3] add elements to string

print(range(10)) = range(0, 10)

print(list(range(10))) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(list(“hello world”)) → puts each letter as its own element

def generateFibNumbers(numList):
fibList = [1,1]
while fibList[len(fiblist)-1] < max(numLst):
nextFib = fibList[len(fibList)-2] + fibList[len(fibList)-1]
fibList = fibList + [nextFib]
return fibList

lst.append( ) → adds to list, does NOT return anything, directly changes the list itself → MUTABILITY
L = [2,3,4]
Issue comes when we want to make a copy:
(1) M = L
(2) N = [2,3,4]
Alias​ → special kind of copy where 2 variables refer to same value
L.append(8) → changes L but also M
id(L) → unique number of value (location of where value is stored)
id(L) = id(M) , but not equal to id(N)
L is M → boolean for whether or not id’s of L and M are the same

Alias helpful when:

M=L
L=M
print(L, M) → same lists, loses value of M

Need to hold onto M’s original value

Tmp = M
M=L
L = tmp

L.remove( )
L.insert(index#, value)
lst.pop( ) → removes element at index, also returns value its removing

M=L
L.append(4)
L = L + [5] → changes L only, not M

Destructive: remove, insert, append

Non-destructive: L+[value], str, int operations

sorted(M)
L[5] = “foo” → can directly change value at this location → mutable
Strings are NOT mutable → immutable

Want to remove all instances of a value: DON’T use for loop since length of list decreases per iteration
(same for adding elements to list → infinite loop)
L = [3,5,2,3,6,3]
for i in range(len(L)):
if L[i] == 3:
L.remove(3)
print(L)

s = ‘bananas’
lst = [ ]
for c in s:
ff c not in lst:
 lst.append(c)
print(lst)

** use for loop if you’re not changing list elements

INSTEAD: use while loop

i=0
while i < len(L):
L.insert(i+1, L[i]*2)
i = i+2
print(L)

List of lists
lst = [ [1,2,3], [4,5,6], [7,8,9] ]
lst = [ ]
For row in range(3):
Tmp = [ ]
For col in range(3):
tmp.append(0)
lst.append(tmp)
print(lst)

Lst[0][1] = 4 → every _row and _ col value is aliased

# rows = len(lst)
# cols = len(lst[0])

Recursion
Remove a number each time until [ ] and then return back
Base case = [ ]
Recursive case = all other numbers

def recursiveSum(lst):
if len(lst) == 0:
return 0
else:
return lst[0] + recursiveSum(lst[1:]) → must be smaller than input list (taking away
element each time)

def recursionFunction(input):
if base_case: (smallest version)
return something
else:
 Remove a part from input to make it smaller
Partial_solution = recursionFunction(input - part)
Return the part combined with the partial_solution

Ex) Return the number of elements in a list:

def recursiveSum(lst):
if len(lst) == 0:
return 0
else:
return lst[0] + recursiveSum(lst[1:])

Ex) Return factorial of number:

def factorial(n):
if n == 0:
return 1
else:
return ​n * factorial(n-1) ​→ same function name

Ex) Calculate nth Fibonacci number (sum of previous 2 numbers)

def fib(n):
if n <= 2: → only numbers that don’t follow general rule
return 1
else:
return fib(n-1) + fib(n-2)

Towers of Hanoi:
def moveDiscs(discs, start, temp, end):
if discs == 1:
print(“move 1 disk from “ + start + “to” + end)
Else:
Steps = 0
Steps += moveDisks(discs - 1, start, end, temp)
Steps += moveDiscs(1, start, temp, end)
Steps += moveDisks(discs-1, temp, start, end)
Return steps
moveDiscs(4, “red”, “black”, “blue”)

How to write search recursively​:

def search(lst, item):
if len(lst) == 0:
return False
elif lst[0] == item:
 return True
else:
return search(lst[1:], item)

Binary search​: how many times can I divide my list in half until I exit (only 1 element left)
def binarySearch(lst, item):
if len(lst) == 0:
return False
mid = len(lst) // 2
if lst[mid] == item:
return True
elif item < lst[mid]:
return binarySearch(lst[:mid], item)
else: # item > lst[mid]
return binarySearch(lst[mid+1])

Linear search: best case = 1 (first element), worst = n steps (last or not in list)
Binary search: best case = 1 (middle element), worst = log ​2 (n)
​
→ only add 1 more iteration by doubling the list length

Big - O notation:
Linear search → O(n) (linear in N) → number of operations = const. * n + const.
​ ​(n) + const
Binary search → O(log(n)) → number of operations = const. * log(n) const
(don’t care about constants)
[2 million] → log​2​(2 million) = 20 → doesn’t grow as much at large N

O(1) → constant time for any input size

O(N) → #steps * iterations

m^n (depends on n since looping over n → for i in range(n)) → O(m)

Sorting
def selectionSort(L): → swapping (index matters)
for i in range(len(L)-1):
minSoFar = L[i]
for j in range(i+1, len(L)):
if L[j] < minSoFar:
minSoFar = L[j]
tmp = L[minIndexSoFar]
L[minIndexSoFar] = L[i]
L[i] = tmp
runtime → O(N​2​)
def insertionSort(L): → moving next items into already sorted list + inserting
for i in range(1, len(L)):
tmp = L[i]
j=i-1
while j >= 0 and L[j] > tmp:
L[j+1] = L[j]
j=j-1
L[j+1] = tmp
runtime → O(N​2​)

def mergeSort(L): → merges sections of list and them compares first elements of each section to sort
if len(L) == 0 or len(L) == 1:
return None
mid = len(L) //2
left = L[:mid]
right = L[mid:]
mergeSort(left)
mergeSort(right)

leftIndex = 0
rightIndex = 0
i=0
while leftIndex < len(left) and rightIndex < len(right):
if left[leftIndex] < right[rightIndex]:
L[i] = left[leftIndex]
leftIndex = leftIndex + 1
else:
L[i] = right[rightIndex]
rightIndex = rightIndex + 1
i = i +1
while leftIndex < len(left):
L[i] = left[leftIndex]
leftIndex = leftIndex + 1
i = i +1
while rightIndex < len(right):
L[i] = right[rightIndex]
rightIndex = rightIndex + 1
i=i+1
runtime → O(Nlog​2​N) → much better than N​2​ at large N

Memory → same amount of size per element (know how to find any element)
Hashing​ → Hash function value = non-negative integer
hash(x) → i
x != y → hash(x) != hash(y) (usually return two different values)
def myHash(s):
num = 0
for c in s:
num += ord(c)
return num
Python already has built-in hash function: hash( )

Hash table
1. Put NONE in each index
2. Use hash function to determine value and place in specific index (replace NONE with value)
a. Let one index hold more than 1 unique item → inner list = “collision”
b. Don’t have duplicates
3. myHash(“zebra”) % 10 → to bring back into bounds of hash function
4. **Mutable values should not be in hash table → hash(x) != same index i every time
a. Can’t hash lists

Dictionary
Maps key → value (mailbox, dictionary)
- Keys are hashed (can look up)
- Can access value once key in located
Indexed by keys (which can take on any immutable value)
d={}
d[“apple”] = “red” → adds to dictionary : apple is key, red is value
del d{“apple”} → deletes from dictionary
“apple” in d → boolean
d.keys( )
len(d)

Iteration over dictionary to see key-value pairs:

for key in d:
print(key, d[key])

def getNumberCounts(lst):
d={}
for item in lst:
digit = item % 10 → one’s digit
if digit not in d:
d[digit] = [ ]
d[digit].append(item)
return d
def mostCommonDigit(d):
bestVal = None
bestCount = 0
for digit in d:
If len(d[digit]) > bestCount:
bestVal = digit
bestCount = len(d[digit])
return bestVal

Trees
Root → nodes → children, leaves
Define using dictionaries
- Single node = 2 keys
- 1 key = value
- 2 key = list of children (other dictionaries)

Function that takes in tree, and prints all value of tree

def printTree(t):
if t[“children”] == [ ]:
print(t[“value”])
else:
for child in t[“children”]:
printTree(child)

To change value of node:

node = t[“children”][0] → get to node
node[“value”] = 99 → change value
To add/remove value:
node = {“value” : 99, “children” : [ ]} → make new node with 2 keys
parent = t[“children”][2]
parent[“children”].append(node)

def searchTree(t,item):
if len(t[“children”]) == 0:
return t[“value”] == item
else:
if t[“value”] == item:
return True
for child in t[“children”]:
result = searchTree(child, item)
if result == True:
return True
return False
Place restrictions on #children + order of children → makes searching the tree more efficient
Binary tree: 0-2 children, left < right
- 3 keys: value, left, right ( : None if it doesn’t have child there)

def binarySearchTree(t,item):
if t[left] == None and t[“right”] == None:
Return t[value] == item
Else;
IF T[VALUE] == item:
Return True
Elif t[value] < item:
If t[right] != None:
Return binarySearchTree(t[right],item)
Else:
Return False
Else t[value] > item:
If t[left] != None:
Return binarySearchTree(t[left]),item)
Else:
Return False

d = { key : value } → setting up dictionary

d[key] = value

for k in d: → for each key in d

print d[k] → print values

def createPhonebook(nameList, numberList):

d={}
For i in range(len(nameList)):
name = nameList[i]
number = numberList[i]
if name not in d:
d[name] = number
return d
def sumTree(t):
if t[“left”] == None and t[“right”] == None:
return t[“value”]
elif t[“left”] == None:
return sumTree(t[“right”]) + t[“value”]
elif t[“right”] == None:
return sumTree(t[“left”]) + t[“value”]
else: # both children != None
return sumTree(t[“right”]) + sumTree([“left”]) + t[“value”])

More generally:
def sumTree(t}:
result = t[“value”]
for child in t[“children”]:
result = result + sumTree(child)
return result

Graphs
Connected nodes, fewer restrictions
Edges → directed (arrows), undirected (no arrows)
1. Dictionary approach: edges don’t have values (only values of nodes)
Each node (key) maps to connected nodes (values)
2. 2D List approach: edges have values
Adjacency matrix: column 1, row 1 is all connection of node A (connection of A with itself is
None) other elements of list are values of edges connected to A
nodes = [A, B, C, D, E, G, H] → indexing the actual nodes directly
If directed: backwards connection == None
# connections = len(matrix[node])
if matrix[i][j] != 0: count += count

Searching in graphs
BFS: start at first node
- Check directly connected nodes, then A, B’s connections
- Slowly seeping out from main node
- Check connected nodes that you just visited
DFS: start at first node
- Check a path all the way to the end
- If you can’t go further, backtrack to most recent node that had neighbors
BFS:
** recursion doesn’t work for graphs
1. Visit all of start’s neighbors
def breadthFirstSearch(g, start, item):
to_visit = []
visited = []
while len(to_visit) > 0:
next = to_visit[0]
to_visit.pop(0)
if next not in visited:
if next == item:
return True
else:
to_visit = to_visit + g[next]
visited.append(next)
return False

DFS:
def depthFirstSearch(g, start, item):
to_visit = []
visited = []
while len(to_visit) > 0:
next = to_visit[0]
to_visit.pop(0)
if next not in visited:
if next == item:
return True
else:
to_visit = ​g[next] + to_visit
visited.append(next)
Run time: O(n) (generally for a tree)

Tractability
P, NP, NP-complete

EXAM II MATERIAL END

O(x//=2,3) = O(logn)
Recursion:
- number : 0/1
- String: “ “
- List: []
def addone(l):
If l = []
Return []
Else:
Curr = l[0]
Remainder = l[1:]
Curr_Addone = [curr +1]
Remainder_addone = addone(remainder)
Return curr_addone + remainder_addone

FOR BINARY TREE

def countlefts(t):
Num = 0
If t[“left”] != None:
Num += 1
Num += countlefts(t[“left”])
If t[“right”] != None:
Num += countlefts(t[“right”])
Return num

IF NOT BINARY TREE

Def nwc(t):
If t([“children”] == []:
Return 0
Else:
Num = 1
For child in t([“children”]):
Num += nwc(child)
Return num

Def findcollege(collegeInfo, major):

For college in collegeInfo: # for key in dictionary
Majors = collegeInfo[college]
If major in majors:
Return college
Return None

Adjacency matrix → directed graph w/ edge values

Anything in P is also in NP → P is tractable, NP can be either tractable or intractable
“best”/”least” → not in NP, not tractable
NP complete → not known to be tractable in polynomial time
- All problems can be mapped to each other in polynomial time
- If you solve 1 tractably, you solve all of them in polynomial time
If any problem in NP complete can be solved, then all NP problems can be solved→ NP=P

Concurrency
CPU - central processing unit/processor contains:
- ALU (adders, multipliers)
- Register holds info (bytecode, program counter, accumulator, data register)
- Control unit: regulate flow of info
Thing that helps run algorithm at lowest level (all the actions)

How computers do multiple things/keep track of multiple tasks simultaneously: concurrency

Concurrency happens on a CPU at circuit-level
Concurrency tree: breaks down problem into levels that can happen at the same time
- Only if they don’t use the same resources

Deadlock​: processes stop if they overlap resources since they can’t continue until resources being used
elsewhere get freed up
Solve deadlock: different circuits request different resource priorities

Pipelining​: splitting tasks into series of subtasks (each task relies of data modified by task before it)
- Connected, sharing data → can’t start one until previous subtask finishes
- Relies on longest task to determine total time
If only 1 CPU → multitasking to run multiple processes, but you switch between them (only 1 process
running at a time)
- Appears that they all run at the same time since this switch is so fast
- Scheduler: determines when/where the switch occurs
- Transistors as switches → direct data/bits to different adders in circuits
- More transistors → faster the computer
- MOORE’S LAW
- Use multiple CPU’s instead to enhance speed → multi-core processors

MapReduce
1. Mapper algorithm: takes subset of data + produces results
2. Collected algorithm: takes results as input and combines them into a list
3. Reducer algorithm: takes in list from collector and returns the result that collector outputs

**generate dictionary in mapper for each value/break them into pieces and them combine
f = open(“icecreams.csv”, “r”)
#get the header
Header = f.readline().strip()
Col = header.split(“,”)
Prefs = []
For line in f:
Values = line.strip().split(“,”)
prefs.append(values)

Pandas​ and ​Matplotlib

Chart (week, coffee)
dict = {“week” : [all values in column]
“num_coffees” : [all values in column]}

Create dataframe using pandas:

import matplotlib.pyplot as plt
import pandas as pd

coffee_df = pd.DataFrame(dict) → use pandas to make dataframe

X = list(coffee_df[“week”])
Y = list(coffee_df[“num_coffees”])
plt.scatter(X,Y, color = “red”) → use matplotlib to make scatter plot
plt.show()

Library
OneTen
isUpperClassman(name): True if name = upperclassman, false if not
getTA(s): TA associated with section s

def getUpperClassmen():
allTAs = getAllTAs()
uCTAs = [ ]
for TA in allTAs:
if (ot.isUC(TA)):
uCTAs.append(TA)
return uCTAs
import OneTen as ot
def getAllTAs():
sections = [“A”, “B”, … “P”]
allTAs = [ ]
for letter in sections:
allTAs.append(ot.getTA(letter))
return allTAs

FINAL EXAM REVIEW

Data Visualization: numerical, categorical (ordinal (natural ordering → months)
2 cat + 1 num = heat map (1 num for total), scatterplot matrix (if several numerical data points)
Visual variable: color, row/col

ML: to teach a math model (can modify itself by learning from data) + predict future
Regression: predict numeric value
Classification: predict what category something will fall into
- Logistic regression: separates data
- SVM: want distance from line to data to match on both sides
- K nearest vector: point closest to each other will fall into same category
- Trees: can make a bunch of lines instead of 1 to divide data

AI: initial → goal state using BFS

Internet:
Computer → ISP → router
- Fault tolerance: design philosophy (ex. Packet goes missing)
- Packet: small bit of info sent across internet (carries location in total sequence, destination, who
sent it)
- Packet switching: packets bounce around/take random path to routers to get to final destination.
Can reorder them due to numbering/ordering scheme
- Relates to fault tolerance: even if one bad router, the packet reaches destination since
packet switching is random and will eventually send packet to good router

DNS (domain name server): stores mapping of IP addresses for each website (several IP addresses, so if
one goes down, you can reroute to a different IP address → fault tolerance)
Domain name: google, yahoo

Security + Privacy:
Encryption: Plaintext → ciphertext
Decryption: ciphertext → plaintext
- Symmetric key encryption: Caesar cipher, substitution cipher (depend on the same key)
 - Both people need to have the same key (shared)
- Asymmetric key encryption/public key cryptography: RSA (different keys)
- Generate public key (to anyone → encrypt) + private key (to you only → decrypt)
- No mathematical relationship between the two keys
Caesar cipher: try all the shifts and look for a common word in English → Brute force attack
Substitution cipher: list of alphabets in random order + mapping → brute force much more difficult
Could look at how often the letter appears and match

Man in the Middle Attack: in between two endpoints + messing with info
DDOS:

Cloud:
Software as a Service → consuming (Google docs)
Platform as a Service → resources to build service (Squarespace, use Alexa to build App)
Infrastructure as a Service → basic framework (don’t want to deal with hardware)

- Paying for convenience