Course Info (Syllabus)

Basics

CompSci 161 → Design & Analysis of Algorithms, Prof. Shindler, Fall 2026
Textbook → Algorithms by Jeff Erickson
Week 1 to-do → read the syllabus + policy docs (treat as reading due Tuesday), check Canvas access, [optional] exam seating preferences poll

Rules

No paid note taking, no selling notes, no uploading handouts or lecture slides, no recording lecture → student conduct code violations

Getting Help

Help hours
Anyone could answer it? → public post on EdDiscussion (can be anonymous to classmates)
Includes partial HW solution? → private post on Ed
Email Shindler → subject starts with “CompSci 161”, send from @uci email, include full name + student ID
- Emergency → email + private Ed post
You’re responsible for everything in lecture and discussion

Workload

4 units → ~12 hrs/week
- Lecture + discussion = 5 hrs
- Reading / lecture prep ~1–2 hrs
- Rest → reviewing + homework (not last minute)

Keeping Up

Discussion problems posted in advance → attempt them first, then discuss
Problem sets → not collected but important, read on release, work continuously
Warm-ups → not collected, but lecture assumes you did them

Grading (assumes in-person exams)

Component	Weight
Problem Sets	0% (but important)
PrairieLearn Homework	3%
Four PrairieTests (new this quarter)	24%
Four Topic Exams (not weighted equally)	8%
Core Topic Mastery	65%

Preemptive Final

65% = showing competency on 4 core topics, each has a final exam question
Example: topic 1 = Divide & Conquer → quiz Wed week 3 (Oct 14) has a D&C question (~1.5 pts)
- The matching final exam question is worth 15% of the class grade
- Your % on the quiz question = lower bound for your final exam question score → get it right week 3 → credit early
Two ways to earn each mastery topic

How to Succeed

Attend lecture + discussion, take notes on paper, review/organize after class
- Summarize the main idea, repeat the operations, turn proofs/algorithms from lecture into writing
Do practice problems → treat it like a math class
- Solve yourself first → discuss with study group → check solutions → [optional] ask an LLM but critically (plausible ≠ correct)

Lecture 1: The Celebrity Problem

Definition

Person P is a celebrity if:
1. Everyone else knows who P is
2. P does not know anyone else

Checking if a Person P Is a Celebrity

Takes 2n − 2 questions
- n − 1 other people (everyone minus P)
- Each of them is involved in 2 questions → “do you know P?” and “does P know you?”
Checking everyone this way → upper bound of n · (2n − 2) questions → O(n²)

Brute Force Pseudocode

check(P, G):
	for each x in G − {P}:
		if x does not know P: return false
		if P knows x: return false
	return true

This is the brute force algorithm → ask yourself:
- Did we repeat work?
- Did we do unnecessary work?

Better Approach: Elimination

Copy the set of people (everyone starts “standing”)
While 2 or more people are standing:
- Let a, b = two distinct arbitrary people still standing
- Ask: does a know b?
  - If a knows b → a is not a celebrity → remove a
  - If a does not know b → b is not a celebrity → remove b
Every question eliminates exactly one person → takes n − 1 questions to narrow it down to one candidate
The last person standing is only a candidate → still need to run check on them (2n − 2 more questions) → total ≤ 3n − 3 → O(n)

How Many Celebrities Can a Group Have?

So far, we assumed a group has at most one celebrity
Could a group have zero celebrities? → yes
Could a group have 2 or more celebrities? → no
- If A and B were both celebrities → A must know B (everyone knows a celebrity), but A knows no one → contradiction

Lecture 2: Prerequisite Review — Proofs

Direct Proof: n odd → n² odd

n odd → n = 2k + 1 for some integer k
n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
2·(integer) + 1 → odd ✓

Pythagorean Theorem: a² + b² = c²

Build a big square with side a + b
Place 4 copies of the right triangle (legs a, b, hypotenuse c) inside, one in each corner → the empty space in the middle is a tilted square with side c
Count the big square’s area two ways:
- (a + b)² = a² + 2ab + b²
- 4 triangles + middle square = 4 · (ab/2) + c² = 2ab + c²
Set equal → a² + 2ab + b² = 2ab + c² → a² + b² = c² ✓

Primitive Pythagorean Triples

(a, b, c) with a² + b² = c² and no common factor other than 1
- e.g. (3, 4, 5), (5, 12, 13), (8, 15, 17), (7, 24, 25), (20, 21, 29), (9, 40, 41)
- (6, 8, 10) is not primitive → everything divisible by 2
Key fact → every square is 0 or 1 mod 4
- Even: (2k)² = 4k² → 0 mod 4
- Odd: (2k + 1)² = 4(k² + k) + 1 → 1 mod 4
Partial credit: a, b can’t both be even
- a, b even → a² + b² even → c² even → c even
- Now 2 divides a, b, and c → common factor → not primitive, contradiction
Full credit: a, b can’t both be odd
- a, b odd → a² ≡ 1, b² ≡ 1 mod 4 → c² = a² + b² ≡ 2 mod 4
- But squares are only ever 0 or 1 mod 4 → contradiction
So exactly one of a, b is odd and the other is even

Induction 1: Fibonacci Parity

F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂
Claim: Fₙ is even iff 3 divides n
Look at the pattern → 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 → parities: E, O, O, E, O, O, E, O, O, E…
Stronger claim to induct on → for every k ≥ 0, (F₃ₖ, F₃ₖ₊₁, F₃ₖ₊₂) = (even, odd, odd)
- Base (k = 0): (F₀, F₁, F₂) = (0, 1, 1) → (E, O, O) ✓
- Step: assume true for k, then
  - F₃ₖ₊₃ = F₃ₖ₊₂ + F₃ₖ₊₁ = O + O = E
  - F₃ₖ₊₄ = F₃ₖ₊₃ + F₃ₖ₊₂ = E + O = O
  - F₃ₖ₊₅ = F₃ₖ₊₄ + F₃ₖ₊₃ = O + E = O
Every n is 3k, 3k + 1, or 3k + 2 → Fₙ is even exactly when n = 3k → both directions of the “iff” ✓
Why the stronger claim? → Fₙ depends on the two previous terms, so the hypothesis has to carry parity info about both

Induction 2: Removing a Vertex Without Disconnecting

Claim: connected G with |V| ≥ 2 has 2 distinct vertices x₁, x₂ where G − x₁ and G − x₂ are both still connected
Proof idea → use a spanning tree T of G (exists since G is connected)
A tree with ≥ 2 vertices has ≥ 2 leaves
- Take the longest path in T → its two endpoints u, v are distinct
- If endpoint u had a neighbor besides the next vertex on the path:
  - Neighbor on the path → cycle → impossible in a tree
  - Neighbor off the path → path could be longer → contradicts “longest”
- So u and v are both leaves
Removing a leaf from a tree leaves a tree → T − u is connected and touches every vertex of G − u → G − u is connected
Same for v → x₁ = u, x₂ = v ✓

Discussion 1: Review — Counting

Answers can stay as un-evaluated expressions (sums, C(n, k)) → shown evaluated here for sanity

Q1: Simple Counting

(a) Flip a coin until heads, max 4 flips → how many outcomes?
- H, TH, TTH, TTTH, TTTT → 5
(b) Roll a 6-sided die, then flip a coin that many times → outcomes?
- Rolled k → 2ᵏ flip sequences → Σ₍ₖ₌₁₎⁶ 2ᵏ = 2 + 4 + 8 + 16 + 32 + 64 = 126
(c) 3-digit numbers where digit 1 ≠ digit 2 and digit 2 ≠ digit 3
- 1st digit: 1–9 → 9 choices (can’t start with 0)
- 2nd digit: 0–9 except the 1st → 9 choices
- 3rd digit: 0–9 except the 2nd → 9 choices (it can equal the 1st)
- 9 · 9 · 9 = 729

Q2: Skittles (Stars and Bars)

Bag = 20 candies, 5 flavors, order doesn’t matter → only the count of each flavor matters
Stars and bars → splitting n identical items into k groups = C(n + k − 1, k − 1)
- Picture 20 stars (candies) and 4 bars (dividers between the 5 flavors) → choose which 4 of the 24 spots are bars
(a) Any mix → C(24, 4) = 10,626
(b) At least one of each flavor → put 1 of each in first, then distribute the other 15 freely
- C(15 + 4, 4) = C(19, 4) = 3,876
(c) 1 to 20 candies, no flavor minimum
- Direct: Σ₍ₖ₌₁₎²⁰ C(k + 4, 4)
- Trick → add a 6th fake flavor “empty space” so the total is always exactly 20 → C(25, 5), then subtract the 1 bag that’s all empty space (0 candies)
- C(25, 5) − 1 = 53,130 − 1 = 53,129

Q3: Elevator (7 passengers, 10 floors)

Each person picks independently → 10⁷ equally likely outcomes total
(a) All different floors → 10 · 9 · 8 · 7 · 6 · 5 · 4 choices
- P = (10 · 9 · 8 · 7 · 6 · 5 · 4) / 10⁷ = 604,800 / 10⁷ ≈ 0.0605
(b) Only even floors → 5 even floors → 5⁷ / 10⁷ = (1/2)⁷ = 1/128
(c) All different and only even → 7 people but only 5 even floors → pigeonhole → 0
(d) (a) or (b) → inclusion–exclusion → P(a) + P(b) − P(c) = 0.06048 + 0.0078125 − 0 ≈ 0.0683

Q4: 12-Sided Die

(a) Primes in 1–12 → 2, 3, 5, 7, 11 → 5/12 (1 isn’t prime)
(b) 1000 rolls, exactly 200 primes → binomial: pick which 200 rolls are prime, those are prime, rest aren’t
- C(1000, 200) · (5/12)²⁰⁰ · (7/12)⁸⁰⁰
(c) At least 200 primes → add up (b) for every count from 200 to 1000
- Σ₍ₖ₌₂₀₀₎¹⁰⁰⁰ C(1000, k) · (5/12)ᵏ · (7/12)¹⁰⁰⁰⁻ᵏ
(d) Expected value → average of 1..12 → (1 + 2 + … + 12)/12 = 78/12 = 6.5

Problem Set 0: Prerequisite Questions

Not collected, no official solutions posted → the point is to see what prereqs you need to review
Q11 → same as Lecture 2 Fibonacci proof
Q13 → same as Discussion 1 Q4 (12-sided die)
Q14 → same as Discussion 1 Q2 (Skittles)

Q1: isPrime Running Time

isPrime(n):
	if n = 1: return false
	else if n = 2: return true
	else if n is even: return false
	for i from 3 to ⌈√n⌉ by twos:
		if i divides n: return false
	return true

(a) Loop goes from 3 to √n, stepping by 2 → about √n / 2 iterations → O(√n)
(b) Polynomial time? → No
- “Polynomial” is measured in the input size, not the input’s value
- Input size = number of bits to write n → b ≈ log₂ n → n ≈ 2ᵇ
- √n = 2ᵇᐟ² → exponential in b
- Intuition → adding one digit to n makes it ~10× bigger, and the loop ~3× longer

Q2: “Resolute” Numbers

n is resolute if 3 divides n² + 2n; claim: every odd n is resolute → disprove with a counterexample
n = 1 → 3 ✓, n = 3 → 15 ✓, n = 5 → 25 + 10 = 35 → 35/3 isn’t an integer ✗
n = 5 is odd but not resolute → claim is false

Q3: Sorted Squares (interview question)

Input: sorted V of n distinct numbers (can be negative) → output V′ = their squares, sorted
(a) O(n log n) → square everything, then sort
(b) O(n) → two pointers
- The biggest square is always at one of the ends (most negative or most positive)
- l = 0, r = n − 1, fill V′ from the back
- Compare |V[l]| vs |V[r]| → write the bigger square into the next back slot of V′, move that pointer inward
- Each step places one value → n steps → O(n)
- e.g. V = [−4, −1, 0, 3, 10] → 100, then 16, then 9, then 1, then 0 → V′ = [0, 1, 9, 16, 100]
(c) Better than O(n)? → No
- V′ has n entries, and every one depends on a different input value → you have to at least read all n inputs and write all n outputs → Ω(n)

Q4: Easy-and-Funny Professors

Each prof = (difficulty, humor), all distinct values
Prof P is dominated if some other prof Q is both easier and funnier → never pick P
Goal → return every prof who is not dominated
Example check → Venabili (4, 65), Grant (2, 35), Walsh (8.2, 90) survive
- Jones Jr (8, 15) → Venabili is easier + funnier → out
- Plum (9, 85) → Walsh is easier + funnier → out
(a) Algorithm
- Simple → for each prof, compare against every other prof, keep if nobody dominates → Θ(n²)
- Better → sort by humor, funniest first, then scan while tracking the lowest difficulty seen so far
  - Everyone already scanned is funnier than the current prof
  - Current prof survives iff their difficulty < min difficulty so far (easier than everyone funnier than them)
  - Update the min, keep going
- Trace: Walsh 8.2 ✓ (min 8.2) → Plum 9 ✗ → Venabili 4 ✓ (min 4) → Grant 2 ✓ (min 2) → Jones Jr 8 ✗ → Jones Sr 8.5 ✗ → Moriarty 10 ✗
(b) Sort Θ(n log n) + one scan Θ(n) → Θ(n log n) worst case
(c) Best possible? → probably yes
- Values are arbitrary reals → can’t use counting/radix sort tricks, only comparisons
- This is the classic “maxima of a point set” problem, which is known to need Ω(n log n) comparisons in the worst case

Q5: Common Key in Two Max-Heaps

Only allowed: max() O(1), extractMax() O(log n), insert(e) O(log n), and O(1) extra memory
Algorithm → compare the two tops over and over:

while A and B both non-empty:
	if A.max() = B.max(): return true
	if A.max() > B.max(): A.extractMax()
	else: B.extractMax()
return false

Why it’s safe to throw away the bigger top → if A.max() > B.max(), every element of B is ≤ B.max() < A.max(), so A’s top can’t be in B
Basically merging both heaps in descending order and checking for a match, like merge in mergesort
Runtime → each loop iteration removes one element → ≤ n iterations · O(log n) = O(n log n), O(1) extra memory ✓

Q6: Alien Alphabet

Given m words already in alien alphabetical order → find a letter order consistent with them, or prove the aliens lied
Build a directed graph → one vertex per letter (n vertices)
For each adjacent pair of words (wᵢ, wᵢ₊₁):
- Find the first position where they differ → letters x (in wᵢ) and y (in wᵢ₊₁) → add edge x → y (“x comes before y”)
- Everything after the first difference tells you nothing (like “cat” < “dog” says nothing about a vs o)
- No difference but wᵢ is longer (wᵢ₊₁ is a prefix of wᵢ, like “apple” before “app”) → lie, output that pair
Only adjacent pairs are needed → the order is transitive, so the other pairs are implied
Topological sort the graph
- Works → that’s a valid alphabet order (letters with no constraints can go anywhere)
- Finds a cycle (x before y before … before x) → lie, output the cycle + the word pairs that made those edges
Runtime → comparing adjacent words = O(L) where L = total length of all words; graph has n vertices, ≤ m − 1 edges → topo sort O(n + m) → O(L + n) overall

Q7: Euclidean Algorithm

(a) gcd(698, 277) → keep doing (bigger) = q · (smaller) + remainder
- 698 = 2 · 277 + 144
- 277 = 1 · 144 + 133
- 144 = 1 · 133 + 11
- 133 = 12 · 11 + 1
- 11 = 11 · 1 + 0 → last non-zero remainder → gcd = 1
(b) Find s, t with 698s + 277t = 1 → run it backwards (extended Euclid), substituting remainders from the bottom up
- 1 = 133 − 12 · 11
- sub 11 = 144 − 133 → 1 = 13 · 133 − 12 · 144
- sub 133 = 277 − 144 → 1 = 13 · 277 − 25 · 144
- sub 144 = 698 − 2 · 277 → 1 = 63 · 277 − 25 · 698
- s = −25, t = 63 → check: 63 · 277 = 17,451 and 25 · 698 = 17,450 → difference 1 ✓
(c) Measure 1 oz with a 698 bottle and a 277 bottle → act out 63 · 277 − 25 · 698 = 1
- Repeatedly fill the 277 bottle and pour it into the 698 bottle
- Whenever the 698 bottle is full, dump it out and keep pouring what’s left of the 277
- After 63 fills you’ve poured 17,451 oz total and dumped 25 full 698s = 17,450 oz → 1 oz left in the 698 bottle

Q8: 11¹⁵² mod 77

Given → 11¹ ≡ 11, 11² ≡ 44, 11⁴ ≡ 11 (mod 77)
Repeated squaring → keep squaring to get powers of 2:
- 11⁸ = (11⁴)² ≡ 11² ≡ 44
- 11¹⁶ ≡ 44² ≡ 11 (since 11⁴ ≡ 11, i.e. 44² ≡ 11)
- Pattern flips 11, 44, 11, 44… → 11³² ≡ 44, 11⁶⁴ ≡ 11, 11¹²⁸ ≡ 44
Write 152 in binary → 152 = 128 + 16 + 8
11¹⁵² = 11¹²⁸ · 11¹⁶ · 11⁸ ≡ 44 · 11 · 44
- 44 · 11 = 484 → 484 − 6 · 77 = 22
- 22 · 44 = 968 → 968 − 12 · 77 = 44
11¹⁵² ≡ 44 (mod 77)

Q9: Difference of Two Odd Squares Is a Multiple of 4

Odd numbers → 2a + 1 and 2b + 1
(2a + 1)² − (2b + 1)² = (4a² + 4a + 1) − (4b² + 4b + 1) = 4(a² + a − b² − b) → multiple of 4 ✓

Q10: 2 More Than a Multiple of 4 → Not a Perfect Square

n = 4k + 2 → n ≡ 2 mod 4
Squares are only ever 0 or 1 mod 4 (same fact from the Pythagorean triple proof) → n can’t be a square ✓

Q12: 25 CS + 25 Philosophy Majors at a Round Table

Show someone is sitting between two philosophy majors
Number seats 0–49 around the circle → person at seat i sits between seats i − 1 and i + 1
Split seats into even (0, 2, …, 48) and odd (1, 3, …, 49) → 25 each
25 philosophy majors across 2 groups → pigeonhole → one group has ≥ 13
Say it’s the even seats → think of them as their own circle of 25: 0, 2, 4, …, 48, back to 0
- In a circle of 25 spots, you can fit at most 12 people with no two next to each other → 13 forces two “neighbors” i and i + 2
Seats i and i + 2 both philosophy → the person at seat i + 1 has philosophy on both sides ✓

Q15: 3-Gallon and 5-Gallon Jugs → Get 4 Gallons

(a) Graph
- Vertex = a state (x, y) → x gallons in the 3-gal (0–3), y in the 5-gal (0–5) → 4 · 6 = 24 vertices
- Edge = one legal action (fill, empty, or pour one into the other)
- Directed → e.g. pouring (3, 2) → (0, 5) can’t be undone by a single action
(b) Find a path from (0, 0) to (0, 4) → BFS gives the fewest steps
- (3-gal can’t hold 4, so the 4 has to end in the 5-gal)
- One solution: (0,0) → fill 5 → (0,5) → pour into 3 → (3,2) → empty 3 → (0,2) → pour into 3 → (2,0) → fill 5 → (2,5) → pour into 3 until full → (3,4) → empty 3 → (0,4) ✓

Q16: Number Maze

Graph
- Vertex = a cell → n² vertices
- Directed edge from cell (r, c) labeled k → to (r ± k, c) and (r, c ± k), only if it stays on the board → ≤ 4 edges per cell
- Directed → the cell you land on has a different number, so you can’t always jump back
Solve → BFS from top-left (edges are unweighted, each = 1 move)
- BFS distance to bottom-right = min moves
- Never reached → no solution
Runtime → O(n²) vertices + O(n²) edges → O(n²)
Example path (8 moves) → right, down, left, right, up, left, right, down

Q17: Dijkstra With Exactly One Negative Edge

Negative edge (u → v) with weight w < 0, no negative cycles
Hint → the shortest s → t path either uses that edge or doesn’t
Algorithm:
1. Delete the negative edge → G′ (all edges ≥ 0, Dijkstra works)
2. Dijkstra from s in G′ → distances d_s(·)
3. Dijkstra from v in G′ → distances d_v(·)
4. Answer = min( d_s(t), d_s(u) + w + d_v(t) )
  - 1st option → best path without the negative edge
  - 2nd option → best way to get to u, take the negative edge, best way from v to t
Uses the negative edge at most once → using it twice means going around a cycle, and cycles aren’t negative, so that never helps
Runtime → 2 Dijkstra calls = same Big-O as 1 ✓

Ivan's CS Notes

Explorer

ICS_161

Course Info (Syllabus)

Lecture 1: The Celebrity Problem

Lecture 2: Prerequisite Review — Proofs

Discussion 1: Review — Counting

Problem Set 0: Prerequisite Questions

Graph View

Table of Contents

Backlinks