Week 5 Announcements

Lecture W5M1: Schedule Update, Due Dates, Where We Are, and HW2 Hints

Lucas P. Cordova, Ph.D.

lpcordova@willamette.edu

Willamette University

September 21, 2026

First, thank you

Last Wednesday

I was not well enough to teach on Wednesday, September 16, so class was cancelled. Thank you for your patience and for the kind messages.
Nothing is lost: today’s lecture is the one you would have had on Wednesday, and the next few meetings shift by one slot to make room.
The syllabus schedule in Canvas is updated (version 1.1), and the weekly pages for weeks 4, 5, and 6 now match it.

The schedule, reshuffled

One meeting later, then back on track

Date	Was	Now
Mon 9/21	AVL trees	Binary trees, part 1 (today)
Wed 9/23	Heaps and priority queues	Binary trees, part 2: AVL trees
Mon 9/28	Breadth-first search	Binary heaps and priority queues
Wed 9/30	DFS and topological sort	Graph search: BFS, DFS, and topological sort
Mon 10/5	Greedy and MST	Greedy and MST (unchanged)

BFS and DFS share one session on the 30th; they pair naturally, and the reading (CLRS 20.1 to 20.4) is unchanged. From October 5 on, every date in the syllabus is exactly as it was, including the midterm on Wednesday, October 14.

Due dates

What is due, and when

HW2 is extended to Wednesday, September 23 at 9:59 PM. We go through every problem today.
HW3 goes out today, due Wednesday, September 30 at 9:59 PM. It is a different kind of assignment; more on that at the end of today’s lecture.
The semester project is assigned today. Teams of three by Friday, September 25; the proposal is due Monday, October 5.

Dates on the horizon

Date	What
Wed 9/23, 9:59 PM	HW2 due (extended)
Fri 9/25	Project teams set
Wed 9/30, 9:59 PM	HW3 due; HW4 assigned
Mon 10/5	Project proposal due; last day to elect CR/NC (5 PM)
Mon 10/12	HW4 due; midterm review
Wed 10/14	Midterm exam, in class

An opportunity

Data Science Varsity 2026

A free, 10-week virtual hackathon in which student teams build real agentic AI applications alongside students from universities across Oregon, Washington, and the Bay Area.

This year’s theme: Agentic AI systems. Build autonomous AI agents that solve real problems in healthcare, education, or security.
What you get: hands-on experience building multi-agent AI systems, a dedicated industry mentor, free access to DataCamp, Databricks, Google Antigravity, Base44, and ArgosX, a portfolio project to show employers, and a shot at awards on Demo Day, December 19.
No prior AI experience required. Open to all students regardless of gender, background, or identity. Free to participate.

Data Science Varsity 2026: how to apply

Applications close today, September 21, 2026.
Apply at womeninbigdata.org/dsv2026.
Oregon students: select “Open Track Oregon” on the application form.
Questions: email wibd.dsv@womeninbigdata.org.

Where we are

The map

What changes from here

Weeks 1 to 5 built the toolkit: asymptotic notation, recurrences, the Sequence and Set interfaces, sorting three ways, hashing, and now trees. The homework asked you to prove things: bounds, invariants, amortized costs.
Weeks 6 to 13 use the toolkit on problems: graphs, shortest paths, dynamic programming, flows, hardness. The homework shifts toward designing an algorithm, arguing it is correct, and pricing it.
The proofs do not go away; they become the justification section of a design rather than the whole assignment.
Two things start today to carry that shift: the semester project, and an HW3 that asks you to build what you analyze and check the analysis against reality.

HW2, problem by problem

How to read these hints

HW2 is now due Wednesday, September 23 at 9:59 PM.
For each problem I give the first move and the question that decides the answer. The write-up is still yours: concise, complete, in LaTeX.
The grading emphasis is the same as HW1: a correct and efficient algorithm, with a running-time justification that names its source (a bound from lecture, a theorem, a counting argument).

Problem 1: hash practice (10 points)

(a) Insert the keys \(A = [18, 83, 26, 39, 91, 85, 84]\), in order, into a hash table of size \(7\) with \(h(k) = (5k + 3) \bmod 7\). Each slot holds a linked list; later insertions are appended to the end. Draw the table after all seven insertions.

(b) Now let \(h(k) = ((5k + 3) \bmod c) \bmod 7\) for a positive integer \(c\). Find the smallest \(c\) such that no collisions occur when inserting the keys of \(A\), and show the slot of each key for that \(c\).

Problem 1: how to approach it

(a) Pure bookkeeping. Compute \(5k + 3\) for each key once, reduce modulo \(7\), and append to chains in input order. Draw all seven slots, including the empty ones.
(b) Keep the seven values \(5k + 3\) from part (a). For each candidate \(c = 8, 9, 10, \ldots\), reduce them modulo \(c\), then modulo \(7\), and stop at the first \(c\) whose seven slots are all distinct.
Before computing, rule out what you can: \(c \leq 6\) cannot give seven distinct inner values, and \(c = 7\) (or any multiple of \(7\)) reproduces part (a).
A short script is a legitimate way to find \(c\). The submission must show the slot of every key for your \(c\).

Problem 2: cabin hashing (15 points)

\(2n\) campers, \(n\) cabins; each camper is assigned by hashing a self-chosen badge ID (a positive integer below \(u \gg 2n\)). The family \(\mathcal{H}\) is published before IDs are chosen; one function is drawn at random after. For each family, either show Wren and Ivy can pick IDs that guarantee a shared cabin, or prove they cannot and find the best probability they can achieve.

(a) \(h_{ab}(k) = (ak + b) \bmod n\), with \(a, b \in \{0, \ldots, n-1\}\), \(a \neq 0\).

(b) \(h_a(k) = \left(\lfloor kn / u \rfloor + a\right) \bmod n\), with \(a \in \{0, \ldots, u-1\}\).

(c) \(h_{ab}(k) = ((ak + b) \bmod p) \bmod n\) for a fixed prime \(p > u\): the universal family from lecture.

Problem 2: how to approach it

The question that decides everything: can Wren and Ivy pick two IDs that every function in the family treats identically?

(a) Every \(h_{ab}\) reduces modulo \(n\). What happens to \(a k + b\) when \(k\) grows by exactly \(n\)?
(b) The floor \(\lfloor kn / u \rfloor\) is computed before \(a\) is added. Which IDs land in the same block of width \(u / n\), and does \(a\) ever separate them?
(c) This is the universal family from lecture: \(p\) is prime and larger than \(u\), so distinct IDs stay distinct modulo \(p\). State the universality bound, check its hypotheses, and conclude what the best achievable probability is. No construction can beat a bound that holds for all pairs.

Problem 3: sorting the stacks (20 points)

Sort \(n\) vinyl records efficiently (asymptotically faster correct algorithms earn more) and justify the running time, when the key is:

(a) a catalog code: exactly \(8 \lceil \log_{64}(n^2) \rceil\) symbols from a \(64\)-symbol alphabet, one byte each;

(b) the pressing year, within the last \(150\) years;

(c) the playing time, a rational \(m / n^2\) minutes in \([0, 90]\) with \(m\) an integer;

(d) warmth, which no meter measures, but any two records can be compared by ear in \(O(1)\) time.

Problem 3: how to approach it

Ask one question per scenario: are the keys integers, and how large are they compared with \(n\)?

(a) A catalog code is a base-\(64\) number with \(8 \lceil \log_{64} n^2 \rceil = \Theta(\log n)\) digits. Comparing two codes costs \(\Theta(\log n)\), so a comparison sort is \(O(n \log^2 n)\). A stable pass per digit with \(64\) buckets does better: how many passes, at what cost each?
(b) Pressing years fall in a window of \(151\) values. What is \(u\), and which sort is \(\Theta(n + u)\)?
(c) Multiply every key by \(n^2\) and you have integers below \(90 n^2\). How many base-\(n\) digits is that?
(d) Warmth has no number, only a comparison. Which lower bound applies, and which sort meets it?

Problem 4: the roastery wall (15 points)

Along an \(n\)-foot wall stand \(n\) one-foot bins; bin \(i\) holds a known positive integer \(b_i\) grams, and no two bins hold the same amount. Let \(B = (b_0, \ldots, b_{n-1})\). A customer orders exactly \(r\) grams. Beatrix wants to know whether some nearby pair of bins, meaning \(|i - j| < n/8\), fills the order, meaning \(b_i + b_j = r\).

(a) Given \(B\) and \(r\), describe an expected \(O(n)\)-time algorithm that decides whether a nearby filling pair exists.

(b) Now suppose \(r < n^2\). Describe a worst-case \(O(n)\)-time algorithm for the same question.

Problem 4: how to approach it

(a) For bin \(j\), the only partner that could fill the order is the bin holding \(r - b_j\). Distinct values mean at most one such bin. What structure answers “which index holds value \(v\)?” in expected \(O(1)\)?
Do not forget the two checks after the lookup: \(i \neq j\), and \(|i - j| < n / 8\).
(b) Now \(r < n^2\). Both members of a filling pair are below \(r\), so discard everything else. Which sort is worst-case linear on integers below \(n^2\)?
Once the survivors are sorted with their indices attached, a two-finger walk visits every pair summing to \(r\) exactly once (distinct values again). Check the index condition on each.

Problem 5: scrambled headlines (40 points)

The anagram window count of \(B\) in \(T\) is the number of contiguous substrings of \(T\) that are anagrams of \(B\) (lowercase letters only). Example: \(T\) = redocsrocdecoderacedar, \(B\) = coder gives \(3\): redoc, rocde, coder.

(a) Given \(T\) and \(k\), a data structure built in \(O(|T|)\) time that, for any \(B\) with \(|B| = k\), returns the count in \(O(k)\) time.

(b) Given \(T\) and \(n\) length-\(k\) strings, an \(O(|T| + nk)\)-time algorithm returning every count.

(c) Implement (b) as count_anagram_windows(T, S) in the provided file (ord(c) is \(O(1)\); tests included).

Problem 5: how to approach it

The fingerprint. What summary of a length-\(k\) window is unchanged by permuting its letters? Count each of the \(26\) letters. Two windows are anagrams exactly when their count vectors match.
Sliding. Moving the window one letter right changes two counts. After the first window, every fingerprint costs \(O(1)\).
(a) A hash table from fingerprint to number of windows carrying it. A \(26\)-entry key hashes in \(O(1)\). Build: \(O(|T|)\). Query: fingerprint \(B\) in \(O(k)\), look it up.
(b) Build once for the shared \(k\), query \(n\) times: \(O(|T| + nk)\).
(c) In Python, tuple of \(26\) ints is a valid dict key; ord(c) - ord('a') is the index.

Problem 5: the trap

Recomputing the count vector from scratch for every window is \(O(|T| \cdot k)\). It passes every provided test and fails the running-time requirement, which is where \(25\) of the \(40\) points live. Sorting each window (\(O(|T| \cdot k \log k)\)) has the same problem. Slide.

Common to every problem this week: the answer is short once you name the right tool. Spend your time choosing, then write it down cleanly.

Today’s plan

The next ninety minutes

Minutes	What
25	This deck: announcements, where we are, HW2 problem by problem
10	The semester project: what it is and how to start (deck W5M2)
50	Binary trees, part 1, ending with HW3 (deck W5M3)

The project and lecture slides are separate decks (W5M2 and W5M3).