Computer Science

What is an ADT?

Abstract Data Design: defines behavior, not implementation

What is procedural abrastaction?

Breaking problems into functions

Why use abstraction?

Simplifies complexity

Stack order?

LIFO (Last In First Out)

Queue Order?

FIFO (First In First Out)

Stack Operations?

Push, pop, peek.

Queue operations?

Enqueue, dequeue

Real life stack example?

Undo feature

Reali life queue example?

Line at store

What is node?

Data + reference to next

What is a linked list?

Chain of nodes?

Advantage of linked list?

Dynamic size

What is Big-O?

Growth rate of algorithm

O(1)?

Constant time?

O(n)

Linear

O(n²)?

Nested loops

O(log n)?

Halving (binary search)

What is recursion?

Function calling itself

Two required parts?

Base case + recursive case

What happens without base case?

Infinite recursion

Root?

Top node

Leaf?

Node with no children

Binary Tree?

≤ 2 children

Preorder traversal?

Root → Left → Right

Inorder traversal?

Left → Root → Right

Postorder traversal?

Left → Right → Root

BST Rule

Left < Root < Right

BST search complexity?

O(log n) average

What is brute force?

Try everything

What is Dynamic Programming?

Store/reuse solutions

What is backtracking?

Try + undo

What is class?

Blueprint for objects

What is the Huffman coding?

Compression using frequency?

What is a frame?

Table mapping variable names → references

What are the 3 aspects of a variable?

Name, value, and address

What does “is” mean?

Same reference (same object)

Does Python treat all data the same?

Yes, everything is an object

Does Python copy values automatically?

No, only references

Why does Python cache some values?

Efficiency (e.g., small integers, True, None)

What happens here?

x = [1]

y = x

y.append(2)

x becomes [1,2] (same object)

What happens here?

x = 5
y = x
x = 7

y is still 5 (immutable)

Why are lists tricky with references?

They are mutable → changes affect all references

What happens here?

def f(a):
    a.append(3)

x = [1,2]
f(x)

x becomes [1,2,3]

What happens here?

def f(a):
    a = [3]

x = [1,2]
f(x)

x stays [1,2] (new reference only local)

What is the main idea of prime checking (basic)?

Test divisibility

What is the Sieve method?

Mark multiples as not prime

Gambler’s Ruin problem?

Simulate win/lose until goal or 0

Coupon Collector problem?

Collect all items randomly

Self Avoiding Random Walk?

Random movement without revisiting?

Why do we use simulations?

Approximate probabilities

How to solve big problems?

Break into functions

Why use helper functions?

Simplicity + reuse

What is abstraction?

Hide details, focus on behavior

How to read file data?

Open file → store content in list

Why store file data in list?

Easier processing

Biggest source of bugs?

Misunderstanding references

Q: What happens?

x = [1, 2]
y = x
y = y + [3]
print(x)

[1, 2]
y + [3] creates a NEW list (no mutation)

: What happens?

x = [1, 2]
y = x
y += [3]
print(x)

[1, 2, 3]
+= mutates list (same object)

What happens?

def f(a):
    a = a + [4]

x = [1, 2]
f(x)
print(x)

[1, 2]
new list created locally

What happens?

def f(a):
    a += [4]

x = [1, 2]
f(x)
print(x)

[1, 2, 4]
mutation affects original

What happens?

x = [[1], [2]]
y = x
y[0].append(9)
print(x)

[[1, 9], [2]]
nested references

What happens?

x = [[1], [2]]
y = x[:]
y[0].append(9)
print(x)

[[1, 9], [2]]
shallow copy → inner lists shared

What happens?

def f(x):
    x = 10

a = 5
f(a)
print(a)

5
integers are immutable

What happens?

def f(L):
    L.append(10)

a = [5]
f(a)
print(a)

[5, 10]

What happens?

def f(L):
    L = [10]

a = [5]
f(a)
print(a)

[5]

What happens?

def f(x):
    return x + 1

a = 3
f(a)
print(a)

3

Output?

L = [1,2,3]
for i in range(len(L)):
    L[i] += 1
print(L)

[2,3,4]

Output?

L = [1,2,3]
for x in L:
    x += 1
print(L)

[1,2,3]
x is copy of value

Output?

L = [1,2,3]
for i in range(len(L)):
    L.append(i)
print(L)

Infinite loop (grows while iterating)

Output?

d = {"a":1}
d["b"] = 2
print(d)

{'a':1, 'b':2}

Output?

d = {"a":1}
x = d
x["a"] = 5
print(d)

{'a':5}

What is output?

def f(n):
    if n == 0:
        return 0
    return n + f(n-1)

print(f(3))

6

Output?

def f(n):
    if n == 1:
        return 1
    return f(n-1) * 2

print(f(4))

8

What is missing?

def f(n):
    return f(n-1)

Base case → infinite recursion

Complexity?

for i in range(n):
    print(i)

O(n)

Complexity?

for i in range(n):
    for j in range(n):
        print(i,j)

O(n²)

Complexity?

while n > 1:
    n = n // 2	

O(log n)

What does this algorithm do?

while len(L) > 0:
    m = min(L)
    L.remove(m)

Extracts smallest repeatedly → sorting idea

What does % do?

Remainder

: What does this check?

if n % i == 0:

If i divides n

Why is Sieve faster?

Eliminate multiples instead of checking all

Key idea of simulation?

Repeat random trials

Why loop simulations many times?

Get accurate average

Q: Output?

x = [1,2]
y = x
x = [3,4]
print(y)

[1,2]

Output?

x = [1,2]
y = x
x[0] = 9
print(y)

[9,2]