Documents
Assignments
The weekly problem sets, typically due Friday at 1:10pm, will collectively be worth about 25% of your grade.
Discussion and collaboration on the problem sets is encouraged. However, solutions must be written up individually. Copying another student’s writeup, in whole or in part, or directly collaborating on a writeup, will be considered an academic integrity violation. Insightful discussion with others must be cited in your homework solutions. You will not lose points for such citations.
Each student has four late days to spend throughout the semester as they wish. Simply inform me any time prior to the due date for an assignment that you wish to use a late day; you may then turn in the assignment up to 24 hours late with no penalty. Multiple late days may be used on the same assignment. There are no partial late days; turning in an assignment 2 hours late or 20 hours late will both use 1 late day.
Homework assignments may be turned in either electronically (via the submission form) or on physical paper (use the envelope hanging outside my office). If you submit electronically, I strongly encourage you to use LaTeX; the easiest way to get started is by using a free account on overleaf.com. I will provide a LaTeX version of each problem set which you can use as a starting template for writing up your solutions. You will also need this LaTeX style file.
Each homework question will be graded on a 5 point scale, as follows:
 5: The solution is clear and correct. This solution would easily find a home in a research paper.
 4: The solution contains a few mistakes, but they are mostly arithmetic or of little significance to the overall argument.
 3: The solution hits on the main points, but has at least one logical gap.
 2: The solution contains several logical mistakes, but parts of it are salvageable.
 1: The solution is just plain wrong.
 0: No attempt is made at solving the problem.
Many of the assignments are gratefully based on materials from Brent Heeringa.
Assignment  Resources  Due 

Info sheet  Fri, 8/30  
HW 0 (background)  Tues, 9/3 @1pm  
HW 1 (GCD, induction)  Fri, 9/6 @1pm  
HW 2 (Asymptotic analysis)  Fri, 9/13 @1pm  
HW 3 (Graphs)  Fri, 9/20 @1pm  
HW 4 (DAG analysis)  Fri, 9/27 @1pm  
HW 5 (Percolation)  Fri, 10/11 @1pm  
HW 6 (Divide & Conquer)  Fri, 10/25 @1pm  
HW 7 (1D Dynamic Programming)  Fri, 10/25 @1pm  
HW 8 (2D Dynamic Programming)  PDF, TeX, neruda.tar, 2D dynamic programming exemplar (subset sum) 
Fri, 11/1 @1pm 
HW 9 (Flow Networks)  Fri, 11/8 @1pm  
HW 10 (Amortized Analysis)  Mon, 11/25 @1pm  
HW 11 (Reductions and NPcompleteness)  Fri, 12/6 @1pm  
Optional EC HW (Graph coloring via SAT  30 pts)  Mon, 12/16 @5pm 
Activities/Lectures
Introduction to Algorithms 

W 28 Aug  MARS  
F 30 Aug  MARS  
M 2 Sep  No class (Labor Day); optional induction review session 
MARS 
W 4 Sep  Proving algorithms correct (Euclidean algorithm) 
317 
F 6 Sep  MARS  
M 9 Sep  MARS  
Graphs 

W 11 Sep  MARS  
F 13 Sep  BFS (definitions, properties, asymptotics) 
317 
M 16 Sep  MARS  
W 18 Sep  Bipartite graphs 
317 
F 20 Sep  DAGs and topsort (topsort pseudocode and analysis) 
317 
Greedy Algorithms 

M 23 Sep  MARS  
W 25 Sep  Dijkstra’s algorithm 
317 
F 27 Sep  Analysis of Dijkstra’s algorithm 
317 
M 30 Sep  MARS  
W 2 Oct  Kruskal’s Algorithm and UnionFind 
317 
F 4 Oct  Exam 1 
317 
Divide & Conquer Algorithms 

M 7 Oct  MARS  
W 9 Oct  MARS  
F 11 Oct  Master Theorem and Karatsuba’s Algorithm 
317 
M 14 Oct  Quickselect 
317 
Dynamic Programming 

W 16 Oct  MARS  
F 18 Oct  Fall break 

M 21 Oct  DP exemplar: high/low stress jobs 
317 
W 23 Oct  MARS  
F 25 Oct  More subset sum 
MARS 
Network flow 

M 28 Oct  MARS  
W 30 Oct  The FordFulkerson algorithm 
317 
F 1 Nov  Applications of flow networks 
317 
M 4 Nov  Max flow/min cut 
317 
Amortized analysis 

W 6 Nov  MARS  
F 8 Nov  The accounting method 
317 
M 11 Nov  Amortized analysis examples 
317 
W 13 Nov  Binomial heaps 
317 
F 15 Nov  Exam 2 
317 
Intractability 

M 18 Nov  MARS  
W 20 Nov  Reductions 
317 
F 22 Nov  SAT and 3SAT 
317 
M 25 Nov  NPcompleteness 
317 
2729 Nov  Thanksgiving 

M 2 Dec  CIRCUITSAT is NPcomplete 
317 
M 4 Dec  NPhard video games 
317 
Lineartime sorting 

F 6 Dec  Comparison sorting and bucket sort 
MARS 
M 9 Dec  Radix sort 
317 
Exams
There will be two midterm exams and a cumulative final exam. For each exam, you will be given the exam questions at least one week in advance (probably longer for the final exam). You may use any resources in preparing your solutions to the exam—including your notes, textbook, online resources, and each other—with the only exception that I will not answer specific questions about the exam. On the day of the inclass exam, you must come with no notes and write out your solutions on a clean copy of the exam.
Fri 4 Oct  Midterm 1 (125 points) 
Fri 15 Nov  Midterm 2 (D&C, DP, flow networks; 125 points) 
Fri 13 Dec (25pm)  Final exam (cumulative; 200 points) 