## 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

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