Final Exam Format & Scope
This page collects what the professor said about the structure, scoring, question style, and topic scope of the SP26 final, with direct quotes and citations to the lecture transcripts. For all in-scope formulas and identities, see the final formula sheet.
The general scope of the final, per the professor: everything covered after the midterm, plus basic probability (L25 T:2722-2763).
Scoring
Section titled “Scoring”The exam totals more than 100 points, with final score capped at 100. The mock final (final-example) totalled 120 points, so a student can skip a full question and still earn a perfect score.
“the exam is going to be more than 100. You’ll add another question for us for a chance to approve or choose. … So this exam was 120 points. So you can, for example, skip question two. And you can still score 102.” — L26 T:32-47
Mock Final Question Breakdown
Section titled “Mock Final Question Breakdown”The professor walked through the mock final’s question topics at the start of L26. This is the only sample final available; he could not find others to share.
| # | Topic | In scope for SP26 final? |
|---|---|---|
| 1 | Count-Min Sketch | yes |
| 2 | Membership / Bloom filter | no (excluded) |
| 3 | Approximate median | yes |
| 4 | Bloom filter probabilities | no (excluded) |
| 5 | Online algorithms | yes |
| 6 | Frequency moment | yes |
The professor explicitly declined to make up sample questions for the topics not represented above (MWU, distinct elements, JL lemma, NNS, etc.).
“I cannot give you a question for every topic that we have seen.” — L26 T:155
Typical Question Shape
Section titled “Typical Question Shape”A question that asks for a streaming-style algorithm tends to have two parts: first give an algorithm for the problem, then prove the guarantee of your algorithm.
“first part is given algorithm for this problem. And then the other parts [prove] the guarantees of your algorithm.” — L26 T:318-325
For multiplicative weight updates specifically, expect understanding-based questions about the setting and the algorithm, not the proof of the mistake bound (see MWU proof excluded).
For the JL lemma, a likely question style: given , , , compute the best achievable (see JL formula not given).
Proofs Are Guided, Not Open-Ended
Section titled “Proofs Are Guided, Not Open-Ended”If a question asks you to prove a guarantee, the prompt will scaffold the proof for you with hints. You will not be asked to prove a statement from scratch.
“if I ask you to prove something also, I’ll give you hints throughout the proof. I won’t just say here is a statement, go ahead and prove it.” — L26 T:279-288
A useful concrete example: the mock final’s Chernoff-bound problems give you the Chernoff statement at the top of the page and ask you to apply it to a specific situation.
Partial Credit Policy
Section titled “Partial Credit Policy”Partial credit is given, but it is gated on whether the answer engages with the actual question.
- Understand the question correctly -> guaranteed at least ~25% of the points for that question, since your attempt will be in the right direction.
- Algorithm is roughly correct but proof is shaky -> partial credit on a 30-point algorithm-then-prove question can still land around 10/30.
- Answer is orthogonal to the question (e.g. your “streaming algorithm” isn’t actually in the streaming model) -> no partial credit possible.
“If you understand the question, you are guaranteed to get at least a quarter of the points in the question. … if you don’t understand the question and you write something orthogonal, then I cannot even give you partial credit.” — L26 T:296-311
“if your algorithm is correct, or it makes some sense, then you can get, you know, at least 10 out of the 30 points. But if your algorithm is not even in the streaming model … I cannot even give you partial credit.” — L26 T:327-337
Approach Guidance from the Professor
Section titled “Approach Guidance from the Professor”The professor pushed back on question-driven studying and recommended studying the fundamentals instead.
“I think this is the wrong way of studying. How you guys are preparing is, in my mind, the wrong way, which is question in exam focused, rather than basics focused. So if the basics are solid, then the exam is more of an application.” — L26 T:200-210
“the topics that you don’t see here, the best way to study for them is just try to understand what we’ve covered in class. Because again, these are topics that are not really in a textbook.” — L26 T:341-348
Excluded Topics
Section titled “Excluded Topics”Fully Excluded
Section titled “Fully Excluded”Bloom Filter
Section titled “Bloom Filter”Covered this semester before the midterm, and explicitly removed from the final.
“I think the Bloomfilter will not then be part of the final.” — L26 T:65-66
Membership-Problem Algorithms
Section titled “Membership-Problem Algorithms”Implementation algorithms (hashing with chaining, etc.) will not be asked. The professor said the concept of “what is the membership problem” may still come up since it is foundational.
“I won’t ask you about hashing with chaining or stuff like that. … The algorithms for the membership problem, no, and Bloomfilter, no.” — L26 T:78-108
Partially Excluded
Section titled “Partially Excluded”Multiplicative Weight Updates (MWU) — Proof Excluded
Section titled “Multiplicative Weight Updates (MWU) — Proof Excluded”The Weighted Majority algorithm itself and its mistake bound are in scope. The potential-function proof is not.
“for multiplicative weight updates, so I would say, understand the algorithm. I won’t ask you details about the analysis. … If you understand what the problem is, and what the algorithm is, that’s enough.” — L26 T:174-225
Johnson-Lindenstrauss Formula — Not Given on Exam
Section titled “Johnson-Lindenstrauss Formula — Not Given on Exam”When asked directly if the formula would be provided on the test, the professor answered no. You are expected to understand the theorem well enough that the formula falls out from the guarantee.
Student: “Would you give us the formula on the test or no?” Professor: “No, because the formula… No. Because the formula, remembering the formula means that you’re already doing the wrong thing.” — L25 T:1472-1500
A likely question style: given , , , compute the best achievable (L25 T:1430-1458).
Implicitly Excluded (Not Covered in Lecture)
Section titled “Implicitly Excluded (Not Covered in Lecture)”These were not framed as “exam exclusions” by the professor, but the corresponding material was never derived in class, so it is reasonable to treat it as out of scope.
Randomized Paging — Proof Not Covered
Section titled “Randomized Paging O(logk)O(\log k)O(logk) — Proof Not Covered”You should know the guarantee (randomized eviction achieves -competitive ratio, an exponential improvement over deterministic). The proof was never given.
“So I will not prove this result.” — L25 T:196
Euclidean LSH — Derivation Not Covered
Section titled “Euclidean LSH — Derivation Not Covered”The Hamming LSH derivation (sampling a coordinate gives a -sensitive family) was done in full. For the Euclidean LSH family (random projection onto a hyperplane), only the result was stated.
“What I will not prove, you can ask, well, what about the hash family? The other distance that we are interested in is Euclidean distance” — L26 T:1859-1863
Other Logistics
Section titled “Other Logistics”- Final date: May 18 (L26 T:2679).
- No calculators (per final-example preamble): “if I feel that you have used a calculator, you get minus 15 points.”
- Office hours before the final: the professor offered a couple of hours on Friday and possibly Sunday (L26 T:2742-2756).
Disclaimer
Section titled “Disclaimer”This summary reflects what the professor said in lectures 25 and 26. Treat it as a study aid, not a contract: when in doubt, ask in office hours or on Brightspace.