D321 Exam Study Guide

🔁

Q1 — Fibonacci: Recursive vs. Iterative

5 pts

The Question

Discuss the differences between recursive and iterative solutions for Fibonacci in terms of time complexity.

✅ Iterative — O(n)

Uses a loop. Calculates each number once. Linear time — scales well.

fib = 0, 1 for i in range(n-1): fib = prev + fib

⚠️ Recursive — O(2ⁿ)

Calls itself twice at each step. Exponential time — gets incredibly slow fast!

def fib(n): if n<=1: return n return fib(n-1)+fib(n-2)

📝 Key Answer: Iterative is far more efficient — O(n) vs O(2ⁿ). As n grows, recursive becomes exponentially slower because it recalculates subproblems repeatedly. Iterative just loops once through.

🔗

Q2 — Linked Lists & Memory

4 pts

Part A — What type of list is shown?

The diagram shows nodes with arrows going both directions and the last node connects back to the first.

✅ Answer: Circular Doubly Linked List — each node has a NEXT pointer AND a PREVIOUS pointer, and the tail connects back to the head.

The 4 Types of Linked Lists — Quick Reference

Type	Direction	Last → First?	Real Use
Singly Linked	One way →	No	Simple lists
Circular Singly	One way →	Yes ↩	Chess game turns
Doubly Linked	Both ↔	No	Music player (fwd/back)
Circular Doubly	Both ↔	Yes ↩	Mac app switcher (⌘+Tab)

Part B — Memory allocation

✅ Answer: Unlike arrays (contiguous memory), a linked list stores nodes in scattered/random memory locations. Each node holds: (1) the data value, (2) a pointer to the NEXT node, and (3) in doubly linked: a pointer to the PREVIOUS node. The pointers connect the scattered pieces together.

🌲

Q3 — Min & Max Heap Trees

8 pts

Part A — What are Min/Max Heaps?

🔽 Min Heap

Every parent is smaller than its children. The root = smallest element.

🔼 Max Heap

Every parent is larger than its children. The root = largest element.

Part B — Build a heap from: [1, 4, 8, 48, 12, 15, 22]

📝 Process (Max Heap example):

Insert all elements into a complete binary tree in order
Start at index n/2 (middle), work backwards to root
"Bubble down" each element — swap parent with the larger child if parent is smaller
Result: Root = 48 (largest), every parent > its children

💡 Remember: A heap is a complete binary tree — every level is filled left to right before going to the next level.

🗂️

Q4 — Hash Tables & Collision Resolution

8 pts

Part A — What is a collision?

✅ Answer: A hash collision occurs when two different pieces of data produce the same hash value, mapping them to the same slot in the hash table.

Part B — Two Collision Resolution Strategies

1️⃣ Direct Chaining (Linked List)

When two keys collide, create a linked list at that slot. All colliding values go into the same chain.

Think: each table slot is a bucket with a chain hanging from it

2️⃣ Linear Probing (Open Addressing)

If a slot is full, move to the next available slot (decrease index by 1). Wraps around to the end if needed.

Problem: "clustering" — slots fill up in groups, slowing things down

🔑 Also know: Double hashing — uses a second hash function to calculate how many slots to jump, solving the clustering problem of linear probing.

For the exam table (PHL=4, ORY=8, GCM=6...):

Apply linear probing: if the target slot is taken, keep decrementing the index until you find an empty slot. Apply chaining: if the slot is taken, add to the linked list at that position.

🔢

Q5 — Binary Arithmetic

10 pts

Part A — Binary Multiplication: B = 111.0011 × C = 1.00101

📝 Partial Sum Method:

Ignore decimal point, multiply as whole numbers
For each bit in C (right to left): if bit = 1, write B shifted left; if bit = 0, write zeros
Add all partial products in binary
Count total decimal places in both numbers, place the decimal point that many positions from the right

⚠️ B has 4 decimal places + C has 5 decimal places = 9 decimal places in the answer

Part B — Binary Addition: B + C

Rule	Result	Carry
0 + 0	0	0
0 + 1 or 1 + 0	1	0
1 + 1	0	1
1 + 1 + 1 (with carry)	1	1

📝 Steps: Align decimal points. Add bit by bit from right to left, carrying over when needed. The exam answer for 111.0011 + 1.00101 = 1000.10001 (align and carry carefully!). The slide answer shows: 00100.010

🔄

Q6 — Number System Conversions from 11011.101

10 pts

Starting number: `11011.101`

a) → Hexadecimal

Group bits in sets of 4 from the decimal point outward

Integer: 0001 1011 → 1B

Fraction: .1010 → .A

Answer: 1B.A

b) → Octal

Group bits in sets of 3 from the decimal point outward

Integer: 011 011 → 33

Fraction: .101 → .5

Answer: 33.5

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

Determine the sign bit: positive = 0
Normalize: write as 1.xxxxx × 2ⁿ → 11011.101 = 1.1011101 × 2⁴
Exponent: 4 + 127 (bias) = 131 → 10000011
Mantissa: the bits after the "1." = 1011101, pad to 23 bits with zeros
Combine: 0 | 10000011 | 10111010000000000000000

d) → First Complement (1's Complement)

Simply flip every bit: 0→1 and 1→0

11011.101 → 00100.010

Answer: 00100.010 ✓ (confirmed in slides)

⚡

Q7 — Logic Gates Expression

5 pts

The circuit diagram shows: A & B feed into an AND gate, B & C feed into an OR gate, then that feeds into an AND gate, and both AND results feed into a final OR gate.

✅ Answer from slides:

Q = AB + BC

Read the circuit: AND gate gives A·B, the OR→AND path gives B·C, and the final OR gate combines them.

Logic Gate Quick Reference:

Gate	Symbol	Rule
AND	·	Output 1 only if ALL inputs are 1
OR	+	Output 1 if ANY input is 1
NOT	A'	Flips the input
NAND	(A·B)'	AND then NOT
NOR	(A+B)'	OR then NOT
XOR	⊕	Output 1 if inputs are DIFFERENT

🔤

Q8 — ASCII Decoding

5 pts

Decode: 01001110 01101111 00100001

💡 How to use ASCII: Split the 8 bits into two groups of 4. The first 4 bits = the row, the last 4 bits = the column (or just convert each byte to decimal and look up the character).

✅ How to decode each byte:

01001110 → decimal 78 → N
01101111 → decimal 111 → o
00100001 → decimal 33 → !

Answer: "No!"

(The slide confirms this — it literally says "No!" 😄)

⚠️ Shortcut: Convert each 8-bit byte to decimal, then look up in the ASCII table provided. Binary → decimal: add up powers of 2 for each "1" bit (128, 64, 32, 16, 8, 4, 2, 1 from left to right).

📦

Q9 — Bag of Words & One-Hot Encoding

10 pts

Part A — What is Bag of Words (BoW)?

✅ Answer: BoW represents a document as a collection of word counts, ignoring grammar and word order. Each unique word in the vocabulary gets a position in a vector, and the value = how many times that word appears.

Example:

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

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

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

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

✅ Answer: Each word becomes a vector with a single "1" and all other positions "0":

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

🔗

Q10 — Set Relations

10 pts

Sets: A = Americans, M = Mathematicians, P = Philosophers, Knows = relation where (x,y) means x knows y

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

✅ Answer:
We need people who Know someone in A ∩ M
π₁(Knows ⋈ (A ∩ M))

Plain English: Find all x where there exists a y such that (x Knows y) AND y is in A AND y is in M

Part B — "Find philosophers who ONLY know mathematicians"

✅ Answer:
Philosophers in P where ALL people they know are in M
P − π₁(Knows ⋈ M')

Plain English: Start with all philosophers, remove any who know at least one non-mathematician

📐

Q11 — Set Algebra Simplification

10 pts

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

💡 Key rule to remember: A → B = A' ∪ B (Implication Law)

✅ Step-by-step proof:

Rewrite A → B using implication law: (A' ∪ B) ∩ A
Distribute ∩ over ∪: (A' ∩ A) ∪ (B ∩ A)
A' ∩ A = ∅ (Complement law): ∅ ∪ (B ∩ A)
∅ ∪ X = X (Identity law): A ∩ B
Now the full expression is: (A ∩ B) → B
Rewrite using implication: (A ∩ B)' ∪ B
De Morgan: (A' ∪ B') ∪ B
Associativity + Complement: B' ∪ B = U → A' ∪ U = U
Result = U (always true / tautology)

⚠️ The slides confirm this simplifies using: Complement law (X∪X'=U), Associative law, Implication law, and De Morgan's Law.

Essential Laws Cheat Sheet:

Law	Formula
Implication	A → B = A' ∪ B
De Morgan (∩)	(A ∩ B)' = A' ∪ B'
De Morgan (∪)	(A ∪ B)' = A' ∩ B'
Complement	A ∩ A' = ∅ \| A ∪ A' = U
Identity	A ∪ ∅ = A \| A ∩ U = A
Absorption	A ∩ (A ∪ B) = A
Abjunction	(A → B)' = A ∩ B'

🌊

Q12 — Complex Numbers & Fourier Transform

15 pts

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

📏 Magnitude

Use Pythagorean theorem:
|z| = √(real² + imaginary²)
|z| = √(2² + 3²)
|z| = √(4 + 9) = √13

≈ 3.606

📐 Angle (θ)

Use arctangent:
θ = arctan(imaginary / real)
θ = arctan(3/2)

≈ 56.31°

Part B — Steps to implement the Fourier Transform

✅ Answer (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
Compute the dot product between the complex sine wave and the signal
End loop
The result: each dot product = a Fourier coefficient for that frequency
The magnitude of coefficients = amplitude spectrum
The angle of coefficients = phase spectrum

🎵 Big idea: The Fourier Transform breaks any signal into the sum of sine waves. It answers: "What frequencies make up this signal?" This is how music equalizers, image compression, and signal processing work.

⭐ Last-Minute Power Tips

🔁 Fibonacci: Iterative = O(n), Recursive = O(2ⁿ)

🔗 List type: Circular Doubly Linked List

🌲 Heap: Min = smallest at root, Max = largest at root

🗂️ Collision fix: Chaining = linked lists, Probing = find next empty slot

📝 ASCII decode: "No!" (binary → decimal → letter)

🔄 1's Complement: Just flip all bits!

🔄 IEEE 754: Sign | Exponent+127 | Mantissa (23 bits)

⚡ Logic gates: Q = AB + BC

📦 One-hot: One "1" per row, rest are "0"s

🌊 Fourier: Loop → complex sine wave → dot product

You've got this! 🚀 Good luck on the exam!

🧠 D321 Data Representation — Exam Study Guide

📋 What's on the Exam?

Q1 — Fibonacci: Recursive vs. Iterative

✅ Iterative — O(n)

⚠️ Recursive — O(2ⁿ)

Q2 — Linked Lists & Memory

The 4 Types of Linked Lists — Quick Reference

Q3 — Min & Max Heap Trees

🔽 Min Heap

🔼 Max Heap

Q4 — Hash Tables & Collision Resolution

1️⃣ Direct Chaining (Linked List)

2️⃣ Linear Probing (Open Addressing)

For the exam table (PHL=4, ORY=8, GCM=6...):

Q5 — Binary Arithmetic

Q6 — Number System Conversions from 11011.101

Starting number: `11011.101`

a) → Hexadecimal

b) → Octal

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

d) → First Complement (1's Complement)

Q7 — Logic Gates Expression

Logic Gate Quick Reference:

Q8 — ASCII Decoding

Q9 — Bag of Words & One-Hot Encoding

Example:

Q10 — Set Relations

Q11 — Set Algebra Simplification

Essential Laws Cheat Sheet:

Q12 — Complex Numbers & Fourier Transform

📏 Magnitude

📐 Angle (θ)

⭐ Last-Minute Power Tips

🧠 D321 Data Representation — Exam Study Guide

📋 What's on the Exam?

Q1 — Fibonacci: Recursive vs. Iterative

✅ Iterative — O(n)

⚠️ Recursive — O(2ⁿ)

Q2 — Linked Lists & Memory

The 4 Types of Linked Lists — Quick Reference

Q3 — Min & Max Heap Trees

🔽 Min Heap

🔼 Max Heap

Q4 — Hash Tables & Collision Resolution

1️⃣ Direct Chaining (Linked List)

2️⃣ Linear Probing (Open Addressing)

For the exam table (PHL=4, ORY=8, GCM=6...):

Q5 — Binary Arithmetic

Q6 — Number System Conversions from 11011.101

Starting number: 11011.101

a) → Hexadecimal

b) → Octal

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

d) → First Complement (1's Complement)

Q7 — Logic Gates Expression

Logic Gate Quick Reference:

Q8 — ASCII Decoding

Q9 — Bag of Words & One-Hot Encoding

Example:

Q10 — Set Relations

Q11 — Set Algebra Simplification

Essential Laws Cheat Sheet:

Q12 — Complex Numbers & Fourier Transform

📏 Magnitude

📐 Angle (θ)

⭐ Last-Minute Power Tips

Starting number: `11011.101`