## Documents

## Assignments

Extra credit problems on Kattis. These can be completed any time prior to the final exam. Each successfully solved problem is worth 1/4 point added to your final grade in the course.

HW 1 (GCD, induction) [ TeX ] : due Friday, August 31 @ 1:10pm

HW 2 (Asymptotic analysis) [ TeX ] : due Friday, September 7 @ 1:10pm

HW 3 (Graphs) [ TeX, graph.txt ] : due Friday, September 14 @ 1:10pm

- HW 4 (DAG analysis) [ TeX ] : due Friday, September 21 @ 1:10pm
- Demo: demo-dag.in | demo-dag.out | demo-cycle.in | demo-cycle.out
- Checker script: check-graph.py
- Tiny: graph-tiny-1.in | graph-tiny-2.in
- Small: graph-small-1.in | graph-small-2.in
- Medium: graph-med-1.in | graph-med-2.in
- Big: graph-big-1.in | graph-big-2.in
**ALL GRAPHS IN ONE ARCHIVE**: graphs.tar.gz

HW 5 (percolation) [ TeX ] : due Friday, October 5 @ 1:10pm

Union-find lecture notes (you will need this to do the HW)HW 6 (Divide & Conquer) [ TeX ] : due Friday, October 19 @ 1:10pm

HW 7 (Dynamic Programming I) [ TeX ] : due Friday, October 19 @ 1:10pm

- HW 8 (Dynamic Programming II) [ TeX ] : due Friday, October 26 @ 1:10pm
HW 9 (Flow Networks) [ TeX ] : due Friday, November 2 @ 1:10pm

HW 10 (NP completeness) [ TeX ] : due Friday, November 30 @ 1:10pm

Many of the assignments are gratefully based on materials from Brent Heeringa.

## Activities/Lectures

Suggested readings are in italics. K&T refers to *Algorithm Design* by Kleinberg and Tardos.

### Introduction to Algorithms

F 25 Aug — reasons for POGIL, GCD

M 27 Aug — Proving algorithms correct (Euclidean algorithm)

W 29 Aug — Asymptotic Analysis I (Big-O,

*Ω*,*Θ*)

### Graphs

W 5 Sep — Graphs

F 7 Sep — BFS (definitions, properties, asymptotics)

*K&T 3.2, 3.3*M 10 Sep — BFS applications (connected components)

*K&T 3.4, 3.5*W 12 Sep — Bipartite graphs

F 14 Sep — DAGs and topological sorting

*K&T 3.6*; topsort algorithm pseudocode and analysis

### Greedy Algorithms

M 17 Sep — intro to Dijkstra’s algorithm

*K&T 4.4*W 19 Sep — Dijkstra’s algorithm

*K&T 4.4*F 21 Sep — Analysis of Dijkstra’s algorithm

M 24 Sep — Minimum spanning trees

*K&T 4.5*W 26 Sep — no class

### Exam 1

- F 28 Sep — Exam 1

### Divide and Conquer

M 1 Oct — Intro to Divide & Conquer

W 3 Oct — Divide & Conquer Arithmetic

F 5 Oct — Master Theorem; Karatsuba’s algorithm

### Dynamic Programming

M 9 Oct — Intro to dynamic programming

W 11 Oct — DP example: hi/lo-stress jobs

M 16 Oct — 2D dynamic programming

W 18 Oct — Matrix chain multiplication

F 20 Oct — Matrix chain mult; Floyd-Warshall algorithm (all-pairs shortest paths with arbitrary weights + cycle detection)

### Network flow

M 22 Oct — Introduction to network flow

W 24 Oct — Ford-Fulkerson algorithm

F 26 Oct — Network flow applications

M 29 Oct — Max flow/min cut theorem

### Amortized analysis

F 2 Nov — Accounting method

M 5 Nov — Amortized analysis examples

W 7 Nov — Binomial heaps

### Exam 2

- F 9 Nov — Exam 2

### Intractability

M 12 Nov — Intro to reductions

*K&T*8.1W 14 Nov — Reductions

F 16 Nov — SAT, 3-SAT

*K&T*8.2M 19 Nov — NP, NP-completeness

*K&T*8.3M 26 Nov — CIRCUIT-SAT is NP-complete

*K&T*8.4W 28 Nov — NP-hard video games

### Strings, matching, and linear sorting

F 30 Nov — Comparison sorting lower bound, bucket sort

M 3 Dec — Radix sort

### Final exam

- F 7 Dec —
**Final exam**(Cumulative)