Problem Sets
There are five problem sets, each covering two or three sessions. They are short by design: four to five problems each, released in one session and due at the start of a session about a week later.
Schedule
| # | Problem Set | Released | Due | Covers | Materials |
|---|---|---|---|---|---|
| 1 | Logic and Deduction | S3 · Mon 28 Sep | S5 · Mon 5 Oct | S1-S3 | PDF · Solutions |
| 2 | Quantifiers, Proof Techniques, Sets | S6 · Thu 8 Oct | S8 · Thu 15 Oct | S4-S6 | PDF · Solutions |
| 3 | Functions and Induction | S9 · Tue 20 Oct | S11 · Mon 26 Oct | S7-S9 | PDF · Solutions |
| 4 | Data Structures and Asymptotics | S12 · Thu 29 Oct | S14 · Mon 9 Nov | S10-S12 | PDF · Solutions |
| 5 | Recurrences and Paradigms | S14 · Mon 9 Nov | S15 · Mon 16 Nov | S13-S14 | PDF · Solutions |
Computability (S15) is not covered by a problem set; it is examined on the final exam.
What Each Problem Set Contains
Every problem set has 4-5 problems:
- Proof problems across the material of the sessions it covers.
- One starred problem, which is harder than the rest.
- One “find the bug” problem.
Problem Sets 4 and 5 include algorithm problems. These may be answered in pseudocode. Write them out by hand like everything else. Marks go to whether the algorithm is correct and whether your reasoning about its cost holds up, not to syntax. Minor syntax errors are ignored; an algorithm that does not do what you claim is not. Problem Sets 1 to 3 are proofs only.
Coverage
| # | Topics |
|---|---|
| 1 | Propositional connectives and truth tables; equivalences; CNF/DNF; natural deduction derivations; discharging assumptions; forward and backward reasoning |
| 2 | Quantifiers and their negation; free and bound variables; substitution and capture; direct, contrapositive and contradiction proofs; proof by cases; set identities; relation properties; equivalence relations and orders; closures |
| 3 | Injectivity, surjectivity, bijectivity; currying; countability and diagonalization; ordinary and strong induction; inductive definitions; structural recursion and induction; rule induction; termination measures |
| 4 | Recursion vs iteration; loop invariants; stacks, queues, trees, heaps, graphs; the BST and heap invariants; O, Ω, Θ from the definition; proving and disproving bounds; summations |
| 5 | Setting up and solving recurrences; the substitution method; the Master Theorem; correctness of divide-and-conquer algorithms; map/filter/fold; monoids |
Submission
Submission is on paper, in person. Hand your work in at the start of the session on which it is due.
- Handwritten or typeset are both fine. What is not fine is illegible work.
- Write on one side of the page only, staple the pages together, and put your name on the first page.
- If you cannot attend the session on which a problem set is due, arrange with the instructor by email to submit it in advance.
- Work handed in after the session has begun is late. See the late policy below.
There is no electronic submission and no repository to set up. Everything in PROOF100 is done on paper.
Marking
Problem sets are marked in full and returned at the following session where possible. Worked solutions with commentary are posted after each deadline.
The rubric awards explicit credit for:
- Stating the induction hypothesis on its own line, in any proof by induction
- Naming the technique you are using before you use it
- Identifying where each hypothesis is used in the argument
These earn marks even on a proof that does not fully land. A proof that reaches the right conclusion by an argument you cannot justify earns fewer marks than an incomplete proof whose reasoning is clear.
Late Policy
One problem set may be submitted up to one session late without penalty, no explanation required. Beyond that, late work is marked but not credited toward certification. If something has gone wrong in your semester, email the instructor rather than falling behind due to individual circumstances.
Problem Set 5 is due at the last session of the course, so it cannot be submitted late.
Practice Problems
Each session page carries practice problems that are not collected and not graded. They are the fastest way to find out whether a session actually landed, and the problem sets and final exam draw on the same material. Bring them to the session leaders with questions.
Academic Integrity
PROOF100 maintains a strict zero-tolerance policy for academic dishonesty. Copying work, sharing solutions, or unacknowledged use of LLMs is prohibited and will result in zero credit on the problem set and ineligibility for certification.
Collaboration. Discussing problems with other students is allowed and encouraged. Writing your solution is not a group activity: you must write up your own answers, in your own words, from your own understanding. If you worked on a problem with someone, name them at the top of your submission.
LLMs and other tools. Using an LLM to explain a concept, unpack a definition, or work through an example is fine and encouraged. Using one to generate a proof you then submit is not, whether or not you rewrite it in your own handwriting. Any use at all must be disclosed in a line at the top of your submission.
The reasoning behind this policy is simple: the final exam is closed book and written by hand under time pressure, so a student who has outsourced their problem sets to someone or something else will have practised nothing.
Navigation
Questions? Reach out on the course WhatsApp!