D321 — Start From Zero Study Guide

Chapter 1 · Data Structures & Algorithms

📊 Algorithms, Recursion & Linked Lists

Background Knowledge

What is an algorithm, and what is time complexity?

An algorithm is just a set of instructions for solving a problem. Like a recipe — it takes inputs and produces an output.

Time complexity is how we measure how much longer an algorithm takes as the input gets bigger. We use Big O notation for this.

O(1) — Constant

Always takes the same time, no matter the input. Fast. Like looking up your name in a phonebook if you know the exact page.

O(n) — Linear

Time grows proportionally to input size. Scan through a list of 100 items → 100 steps. List of 1,000 → 1,000 steps.

O(n²) — Quadratic

Time grows by the square. A list of 10 → 100 steps. A list of 100 → 10,000 steps. Gets slow fast.

O(2ⁿ) — Exponential

Doubles with every new input. n=10 → 1,024 steps. n=50 → over 1 quadrillion steps. Basically unusable at large n.

Question 1 · 5 points

01

Recursive vs Iterative Fibonacci — which is better, and why?

5 pts

📖

First: what IS Fibonacci? It's a sequence where each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21… The rule is F(n) = F(n-1) + F(n-2), starting with F(0)=0, F(1)=1.

Method 1: Recursion

The function calls itself to solve smaller versions of the problem.

def fib(n):
    if n <= 1:
        return n            # base case — stop here
    return fib(n-1) + fib(n-2)  # calls itself TWICE!

The problem? To calculate fib(5), it calls fib(4) AND fib(3). Then fib(4) calls fib(3) and fib(2)... it recalculates the same values over and over. The tree of calls explodes.

Time: O(2ⁿ) — exponential 💀

Method 2: Iteration

Uses a loop. Calculates each number once and moves on. No repeated work.

def fib_iter(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b   # just update two variables
    return a

Time: O(n) — linear ✓

Exam Answer

The iterative approach is far more efficient. Iterative runs in O(n) time — it visits each step exactly once. Recursive runs in O(2ⁿ) — it branches into two calls at every step, causing massive repeated computation. As n grows, recursive becomes exponentially slower and quickly becomes impractical.

Background Knowledge

What even IS a linked list vs a regular list?

Regular List (Array)

Elements sit in a continuous block of memory, side by side. Fast to access by index (just jump to position). But inserting/deleting in the middle requires shifting everything.

Analogy: Reserved seats in a row at a theater — you know exactly where seat 7 is.

Linked List

Elements are scattered anywhere in memory. Each element (node) stores its data AND a pointer (address) to the next node. Easy to insert/delete anywhere — just update pointers.

Analogy: A scavenger hunt — each clue tells you where the next one is hidden.

Question 2 · 4 points

02

What type of list is the diagram, and how is it stored in memory?

4 pts

The diagram shows nodes connected with arrows pointing in both directions, AND the last node's arrow wraps back to the first. That's the key pattern.

The 4 Types of Linked Lists

Type	Arrows	Last connects to first?	Real-world example
Singly Linked	→ one way	No	Basic list
Circular Singly	→ one way	✓ Yes (loops)	Chess game (whose turn is it?)
Doubly Linked	↔ both ways	No	Music player (fwd & back)
Circular Doubly ← THIS ONE	↔ both ways	✓ Yes (loops)	Mac ⌘+Tab app switcher

Part A Answer

Circular Doubly Linked List. Each node has a NEXT pointer (forward) and a PREVIOUS pointer (backward), and the last node's NEXT pointer points back to the head (first) node.

Part B — Memory Allocation

Unlike arrays, a linked list doesn't need contiguous memory. Each node is an object stored at any available memory address, containing:

Each node holds: [DATA | PREV_POINTER | NEXT_POINTER]

The NEXT_POINTER is the memory address of the next node. The PREV_POINTER is the address of the previous one. They can be anywhere in RAM — the pointers link them together logically.

Part B Answer

Nodes are allocated in non-contiguous (scattered) memory locations. Each node stores its value plus two pointers — one to the next node's address, one to the previous node's address. In a circular doubly linked list, the tail's NEXT pointer stores the head's address, and the head's PREV pointer stores the tail's address, forming a complete loop.

Question 3 · 8 points

03

Min Heap, Max Heap — what are they and how do you build one?

8 pts

🌲

First: what's a binary tree? A tree is a structure where each element (node) has at most 2 children (left and right). A complete binary tree fills every level left-to-right before starting the next level. A heap is always a complete binary tree.

🔽 Min Heap

Every parent is smaller than or equal to its children. The root = minimum value in the whole tree.

1

4

8

12

15

22

48

🔼 Max Heap

Every parent is larger than or equal to its children. The root = maximum value in the whole tree.

48

15

22

12

4

8

1

Building a heap from [1, 4, 8, 48, 12, 15, 22]

The process is called "heapify". Here's how to build a Max Heap:

Place all elements into the tree in order, left-to-right, filling level by level: 48 is at position n/2 (the last non-leaf node). Start there.
"Bubble down" each element starting from the middle and going left to the root. Compare a parent to its children — if a child is bigger, swap them.
After bubbling down 48 (already largest, no swap needed), check 8 — its children are 15 and 22. 22 > 8 so swap. Now 22 is the parent.
Check 4 — its children are 48 and 12. 48 > 4, so swap. Now 48 is the parent. Keep going until no more swaps needed.
Finally, the root will hold the largest value (48), satisfying the Max Heap property.

Exam Answer — Part A

Min Heap: A complete binary tree where every parent ≤ its children. Root holds the minimum. Max Heap: A complete binary tree where every parent ≥ its children. Root holds the maximum.

Exam Answer — Part B (show your steps!)

Insert [1, 4, 8, 48, 12, 15, 22] into a complete binary tree. For a Max Heap: start from the middle element and "bubble down" — compare each parent to its children and swap if a child is larger. Repeat until the entire tree satisfies the Max Heap property (48 at root). For a Min Heap, swap when a child is smaller, resulting in 1 at root.

Question 4 · 8 points

04

Hash table collisions — what are they and how do you resolve them?

8 pts

🗂️

What's a hash table? It's a super-fast lookup structure. You run your data through a hash function (like "divide by 5 and take the remainder") to get an index. Then you store the data at that index. Looking things up is O(1) — instant!

Analogy: Imagine 10 filing cabinets numbered 0–9. To file a document, you take the last digit of the document ID — that's its cabinet number. Fast to find! But what if two documents end in the same digit? That's a collision.

Part A — What is a collision?

A hash collision occurs when two different pieces of data produce the same hash value, meaning they're mapped to the same slot in the hash table. Example: if h(PHL)=4 and h(HKG)=4, both try to go in slot 4.

Resolution Strategy 1: Direct Chaining (Linked Lists)

Instead of one value per slot, each slot holds a linked list. Colliding values just get added to the chain.

0

ORY

1

LAX → DCA

2

empty

3

empty

4

PHL → GLA → HKG (chained!)

Resolution Strategy 2: Linear Probing (Open Addressing)

If the target slot is occupied, search for the next available slot by decrementing the index by 1. Wrap around to the end if you hit 0.

Example: PHL hashes to slot 4. HKG also hashes to slot 4. Slot 4 is full, so try slot 3 — it's empty! Put HKG in slot 3 instead.

⚠️

Problem with linear probing: "Primary clustering" — items pile up in long contiguous blocks, making future insertions slower and slower. The fix: Double Hashing — use a second hash function to calculate how many slots to jump (not just 1). This spreads things out more evenly.

Chapter 2 · Binary, Octal & Hexadecimal

🔢 Number Systems & Binary Arithmetic

Background Knowledge

Why does binary exist? What IS it?

Computers are made of transistors — tiny switches that are either ON (1) or OFF (0). That's it. So everything a computer does is built from combinations of 1s and 0s. This is binary (base 2).

We use decimal (base 10) in everyday life — ten digits (0-9). Binary only has 2 digits (0 and 1). Octal uses base 8 (digits 0–7). Hexadecimal uses base 16 (digits 0–9 then A–F).

How to read a binary number

Each position represents a power of 2, from right to left: 1, 2, 4, 8, 16, 32...

1

0

1

.

1

0

1

16 + 8 + 0 + 2 + 1 = 27 | .5 + 0 + .125 = .625 → 27.625 in decimal

Question 5 · 10 points

05

Binary multiplication and addition of B = 111.0011 and C = 1.00101

10 pts

Part A — Binary Multiplication (B × C)

💡

The method is called Partial Sum (shift and add). Just like long multiplication in decimal, but simpler because every bit is either 0 or 1.

Ignore decimal points temporarily. Treat both as whole numbers.
For each bit in C (right to left): if the bit is 1, write out B shifted left by that position. If the bit is 0, write a row of zeros.
Add all the partial products together in binary.
Count total decimal places in B (4) plus decimal places in C (5) = 9 decimal places in the final answer. Place the decimal point 9 positions from the right.

Part B — Binary Addition (B + C)

Align the decimal points. Add column by column from right to left.

Inputs	Sum bit	Carry
0 + 0	0	0
0 + 1 or 1 + 0	1	0
1 + 1	0	carry 1 to left
1 + 1 + 1 (with carry)	1	carry 1 to left

Exam Answer (from slides)

Addition result: 00100.010

Show your work: write B and C aligned at the decimal, add bit by bit right-to-left, carrying when 1+1.

Question 6 · 10 points

06

Convert 11011.101 to Hex, Octal, IEEE 754, and 1's Complement

10 pts

Starting number:

1

0

1

.

1

0

1

a) → Hexadecimal

Rule: Group binary digits into sets of 4, starting from the decimal point going both left and right. Add leading/trailing zeros as needed.

Integer part: 0001 1011 → 0001 = 1, 1011 = 11 = B → 1B

Fraction part: .1010 → 1010 = 10 = A → .A

Hex reference: 0-9 are the same, then 10=A, 11=B, 12=C, 13=D, 14=E, 15=F

Answer

1B.A in hexadecimal

b) → Octal

Rule: Group binary digits into sets of 3, starting from the decimal point going both ways.

Integer: 011 011 → 3, 3 → 33

Fraction: .101 → 4+0+1 = 5 → .5

Answer

33.5 in octal

c) → IEEE 754 (32-bit floating point)

This is how computers store decimal numbers in 32 bits. Three parts: Sign | Exponent | Mantissa

Sign bit: Positive number → 0
Normalize: Move the decimal so there's exactly one 1 before it: 11011.101 becomes 1.1011101 × 2⁴ (moved 4 places left)
Exponent: Take the power (4) and add the bias (127): 4 + 127 = 131. Convert 131 to binary: 10000011
Mantissa: Take everything after the "1." in the normalized form: 1011101. Pad with zeros to get 23 bits: 10111010000000000000000
Combine: 0 | 10000011 | 10111010000000000000000

❓

Why bias of 127? Because we need to represent both positive and negative exponents. Bias lets us store them as unsigned integers. Exponent 0 is stored as 127, exponent 4 as 131, exponent -1 as 126.

d) → 1's Complement

The absolute easiest conversion: flip every single bit. 0 becomes 1, 1 becomes 0. That's it.

1

0

1

.

1

0

1

flip all bits ↓

0

1

0

.

0

1

0

Answer (confirmed in slides)

00100.010

Chapter 3 · Character Encoding & Text Representation

⚡ Logic Gates, ASCII, Bag of Words

Question 7 · 5 points

07

Write the expression for the logic gate circuit with inputs A, B, C

5 pts

⚡

What are logic gates? They're the basic building blocks of all computer circuits. Each gate takes binary inputs and produces a binary output based on a logical rule. Every single thing a computer computes is built from combinations of these gates.

The gates you need to know

Gate	Symbol	Rule in plain English	Example
AND	· or ∧	Output 1 only if ALL inputs are 1	1·1=1, 1·0=0
OR	+ or ∨	Output 1 if ANY input is 1	1+0=1, 0+0=0
NOT	A' or Ā	Flip the input	NOT 1 = 0
NAND	(A·B)'	AND, then flip	1·1 → flip → 0
NOR	(A+B)'	OR, then flip	0+0 → flip → 1
XOR	A⊕B	Output 1 if inputs are DIFFERENT	1⊕0=1, 1⊕1=0

Reading the circuit diagram

In the exam diagram, tracing the paths:

• Top path: A and B feed into an AND gate → produces A·B

• Middle path: B and C feed into an OR gate → that feeds into an AND gate with something → produces B·C

• Final gate: Both results feed into an OR gate → final output Q

Q = AB + BC

Exam Answer (confirmed in slides)

Q = AB + BC

Read the circuit from left to right. Each AND gate multiplies its inputs. Each OR gate adds them.

Question 8 · 5 points

08

Decode this binary using ASCII: 01001110 01101111 00100001

5 pts

🔤

What is ASCII? Computers only understand numbers. ASCII (American Standard Code for Information Interchange) is a lookup table that maps numbers 0–127 to characters. The letter 'A' is 65, 'a' is 97, '!' is 33, space is 32, and so on. Every byte = one character.

How to decode

Convert each 8-bit group to a decimal number, then look up the character in the ASCII table.

To convert binary to decimal: write out the bit positions (128, 64, 32, 16, 8, 4, 2, 1) and add up positions that have a 1.

01001110

0+64+0+8+4+2+0 = 78

N

01101111

0+64+32+0+8+4+2+1 = 111

o

00100001

0+0+32+0+0+0+0+1 = 33

!

Exam Answer (literally in the slides 😄)

The binary decodes to: "No!"

Use the ASCII table provided on the exam. Look up each byte's decimal value to find its character.

Question 9 · 10 points

09

Bag of Words method, and one-hot encoding for [human, animal, world, computer]

10 pts

📦

The big picture: Computers can't understand words directly. We have to convert text into numbers (vectors) that math can work with. Bag of Words and One-Hot are two ways to do this.

Part A — Bag of Words (BoW)

BoW represents a piece of text as a vector of word counts. You:

Build a vocabulary — a list of all unique words across all your documents
For each document, create a vector with one position per vocabulary word
Fill in each position with how many times that word appears in that document
Grammar and word order are completely ignored — only frequency matters

Example:

Vocabulary: [the, cat, in, hat, sat, on, mat]

Sentence 1: "The cat in the hat" → [2, 1, 1, 1, 0, 0, 0]

Sentence 2: "The cat sat on the mat" → [2, 1, 0, 0, 1, 1, 1]

Analogy: You dump all the words from a document into a bag, shake it up, and count how many times each word appears. You lose the order — but you capture frequency.

Part B — One-Hot Encoding of [human, animal, world, computer]

One-hot encoding represents each item as a vector with exactly one 1 and the rest 0s. Each item "lights up" only its own position.

Word	human	animal	world	computer
human	1	0	0	0
animal	0	1	0	0
world	0	0	1	0
computer	0	0	0	1

Exam Answer

BoW: Represents text as a vector of word frequencies from a fixed vocabulary, ignoring grammar and word order. Example: "The cat sat" with vocab [the, cat, sat, on] → [1, 1, 1, 0].

One-Hot: Each word in [human, animal, world, computer] is represented as a 4-element vector with a 1 in its position and 0s everywhere else (see table above).

Chapter 4 · Relations & Set Algebra

🔗 Sets, Relations & Logical Simplification

Background Knowledge

What is set theory, and what are relations?

Sets

A set is just a collection of things. A = {all Americans}. M = {all mathematicians}. Operations: A ∩ B = intersection (in both), A ∪ B = union (in either), A' = complement (everything NOT in A).

Relations

A relation is a set of ordered pairs showing a connection between two sets. "Knows" is a relation: (Alice, Bob) ∈ Knows means Alice knows Bob. Notation: Knows ∋ (x, y) means the pair (x,y) is IN the Knows relation.

Question 10 · 10 points

10

Set relation queries about Americans, Mathematicians, Philosophers

10 pts

Given: A = Americans, M = Mathematicians, P = Philosophers, U = all people. Knows(x,y) = x knows y.

Part A — "Find people who know an American mathematician"

We want: find all x such that there exists a y where (x knows y) AND (y is American) AND (y is a mathematician).

American mathematicians = A ∩ M

People who know someone in A ∩ M = the "left side" of the Knows relation, filtered to pairs where the right side is in A ∩ M

Answer

π₁(Knows ⋈ (A ∩ M))

Or in plain English: Join the Knows relation with the set of American mathematicians (A ∩ M), then project (select) just the first component (the "knower").

Part B — "Find philosophers who ONLY know mathematicians"

This is trickier. We want philosophers where every single person they know is a mathematician.

Start with all philosophers: P

Remove any philosopher who knows at least one NON-mathematician

Non-mathematicians = M' (complement of M)

Answer

P − π₁(Knows ⋈ M')

Take all philosophers, subtract those who have any "knows" relationship with someone who is NOT a mathematician. What remains are philosophers who only know mathematicians.

Question 11 · 10 points

11

Simplify: ((A → B) ∩ A) → B

10 pts

📐

The → symbol means "implies". "A → B" means "if A, then B". In set algebra, this translates to: A → B = A' ∪ B (the implication law). Memorize this — it's the key to Q11.

The laws you MUST know for this problem

Law name	Formula	Plain English
Implication	A → B = A' ∪ B	"if A then B" = "not A, or B"
Complement (∩)	A ∩ A' = ∅	A AND not-A = nothing
Complement (∪)	A ∪ A' = U	A OR not-A = everything
Identity (∪)	A ∪ ∅ = A	A or nothing = A
Domination (∪)	A ∪ U = U	A or everything = everything
Distribution	A∩(B∪C) = (A∩B)∪(A∩C)	Like algebra distribution
De Morgan (∩)	(A∩B)' = A'∪B'	NOT(A AND B) = NOT-A OR NOT-B

Step-by-step proof

Start: ((A → B) ∩ A) → B
Apply implication law to inner A→B: ((A' ∪ B) ∩ A) → B
Distribute ∩ over ∪: ((A' ∩ A) ∪ (B ∩ A)) → B
Apply Complement law — A' ∩ A = ∅: (∅ ∪ (B ∩ A)) → B
Apply Identity law — ∅ ∪ X = X: (A ∩ B) → B
Apply implication law again: (A ∩ B)' ∪ B
Apply De Morgan: (A' ∪ B') ∪ B
Rearrange (Associativity): A' ∪ (B' ∪ B)
Complement law — B' ∪ B = U: A' ∪ U
Domination law — X ∪ U = U: U

Result: U (the Universal Set) — this expression is always true (a tautology). It simplifies completely.

The slides confirm: Complement law, Associative law, Implication law, and De Morgan's Law are all used.

Chapter 5 · Image Representation

🌊 Complex Numbers & Fourier Transform

Question 12 · 15 points

12

Complex number magnitude/angle, and Fourier Transform steps

15 pts

📐

What's a complex number? A regular number lives on a line (the "real" axis). A complex number lives on a 2D plane — it has a real part (x-axis) and an imaginary part (y-axis). We write it as a + bi, where i = √(-1). Think of it as a point on a 2D grid.

Part A — Complex number (2, 3i): Magnitude & Angle

Imagine drawing an arrow from the origin (0,0) to the point (2, 3i) on a 2D graph. The magnitude is the arrow's length. The angle is how far it's rotated from the positive x-axis (counterclockwise).

📏 Magnitude (length of arrow)

Use the Pythagorean theorem — it's just the hypotenuse of a right triangle:

|z| = √(a² + b²)
= √(2² + 3²)
= √(4 + 9) = √13

Answer

|z| = √13 ≈ 3.606

📐 Angle (direction of arrow)

Use the arctangent function — it gives the angle from the x-axis:

θ = arctan(b / a)
= arctan(3 / 2)
= arctan(1.5)

Answer

θ = arctan(1.5) ≈ 56.31° (or ~0.983 radians)

Part B — Steps to implement the Fourier Transform

🎵

What is the Fourier Transform, in one sentence? It breaks any signal (like a sound wave or an image) into its component frequencies — like a prism splits white light into the rainbow. It answers: "what mix of sine waves makes up this signal?"

Joseph Fourier (1807) proved that any signal can be represented as a sum of sine waves. The Fourier Transform finds those sine waves.

Each sine wave has three properties:

Frequency

How fast it oscillates (Hz = cycles per second)

Amplitude

How tall/strong the wave is

Phase

Where in the cycle it starts

Exam Answer — Steps to implement DFT (from slides)

Loop over frequencies — for each frequency you want to analyze:
Create a complex sine wave with the same number of time points as the signal, at the current frequency. (Using Euler's formula: e^(2πift))
Compute the dot product between your complex sine wave and the original signal. This tells you how much that frequency is present in the signal.
Repeat for all frequencies. End loop.
The results are the Fourier coefficients. The magnitude of each coefficient = amplitude spectrum (how loud each frequency is). The angle = phase spectrum.

Key insight: This is essentially comparing your signal against each possible frequency using a dot product. High dot product = that frequency is strongly present in your signal.

⚡

Fast Fourier Transform (FFT): Instead of looping frequency by frequency (slow), the FFT puts all the sine waves into a matrix and does one big matrix multiplication. Same result, way faster — this is why your phone can run music apps in real time.

⚡ 60-Second Cram Card — All Exam Answers

Q1 — Fibonacci

Iterative: O(n) ✓
Recursive: O(2ⁿ) 💀

Q2 — List type

Circular Doubly Linked List
Scattered memory, 2 pointers per node

Q3 — Heaps

Min: parent ≤ children, root = smallest
Max: parent ≥ children, root = largest

Q4 — Collisions

Chaining = linked list at slot
Probing = find next empty slot

Q5 — Binary math

Addition result: 00100.010
Multiply: partial sums, then place decimal

Q6 — Conversions

Hex: 1B.A (groups of 4 bits)
Octal: 33.5 (groups of 3 bits)
1s Comp: 00100.010 (flip all)
IEEE: sign|exp+127|mantissa 23-bit

Q7 — Logic gates

Q = AB + BC

Q8 — ASCII

01001110 01101111 00100001 = "No!"

Q9 — Text encoding

BoW = word frequency vector
One-hot: single 1 per word vector

Q10–11 — Sets

A→B = A'∪B (implication law)
Q11 simplifies to U (tautology)

Q12 — Fourier

|z|=√13≈3.606, θ≈56.31°
DFT: loop → sine wave → dot product

You missed everything.Let's fix that.

📊 Algorithms, Recursion & Linked Lists

O(1) — Constant

O(n) — Linear

O(n²) — Quadratic

O(2ⁿ) — Exponential

Method 1: Recursion

Method 2: Iteration

Regular List (Array)

Linked List

The 4 Types of Linked Lists

Part B — Memory Allocation

🔽 Min Heap

🔼 Max Heap

Building a heap from [1, 4, 8, 48, 12, 15, 22]

Resolution Strategy 1: Direct Chaining (Linked Lists)

Resolution Strategy 2: Linear Probing (Open Addressing)

🔢 Number Systems & Binary Arithmetic

How to read a binary number

Part A — Binary Multiplication (B × C)

Part B — Binary Addition (B + C)

a) → Hexadecimal

b) → Octal

c) → IEEE 754 (32-bit floating point)

d) → 1's Complement

⚡ Logic Gates, ASCII, Bag of Words

The gates you need to know

Reading the circuit diagram

How to decode

Part A — Bag of Words (BoW)

Part B — One-Hot Encoding of [human, animal, world, computer]

🔗 Sets, Relations & Logical Simplification

Sets

Relations

Part A — "Find people who know an American mathematician"

Part B — "Find philosophers who ONLY know mathematicians"

The laws you MUST know for this problem

🌊 Complex Numbers & Fourier Transform

Part A — Complex number (2, 3i): Magnitude & Angle

📏 Magnitude (length of arrow)

📐 Angle (direction of arrow)

Part B — Steps to implement the Fourier Transform

Frequency

Amplitude

Phase

⚡ 60-Second Cram Card — All Exam Answers

You missed everything.
Let's fix that.