## Documents

- Syllabus
- POGIL roles
- Lecture notes from the previous semester. The lecture notes will not always match up perfectly with what we do in class, but you may find them to be a helpful resource.
- Induction exemplars
- 1D dynamic programming exemplar
- Final exam

## Assignments

HW 3 [ TeX ] : due Friday, September 15 @ 3pm

Torn2PiecesSkeleton.java, torn2pieces-skeleton.py- HW 4 [ TeX ] : due Friday, September 22 @ 3pm
- 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

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 28 Aug — Proving algorithms correct (Euclidean algorithm)

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

*Ω*,*Θ*)

### Graphs

W 6 Sep — Graphs

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

*K&T 3.2, 3.3*M 11 Sep — BFS applications (bipartite)

*K&T 3.4, 3.5*W 13 Sep — DAGs and topological sorting

*K&T 3.6*

### Greedy Algorithms

F 15 Sep — topological sorting, intro to Dijkstra’s algorithm

*K&T 4.4*M 18 Sep —

*no class*W 20 Sep — Dijkstra’s algorithm

*K&T 4.4*F 22 Sep — Dijkstra’s algorithm, minimum spanning trees

*K&T 4.5*M 25 Sep — Implementing Kruskal’s MST algorithm, Union-find structure

*K&T 4.6*W 27 Sep — Union-find

*K&T 4.6*

### Exam 1

- F 29 Sep — Exam 1

### Divide and Conquer

M 2 Oct — Intro to Divide & Conquer

W 4 Oct — Finish intro activity; Karatsuba’s algorithm

F 6 Oct — Median/select

### 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 — More 2D dynamic programming

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

### Network flow (oops)

- M 23 Oct — Introduction to network flow

### Amortized analysis

W 25 Oct — Binary counters; accounting method

F 27 Oct — Amortized analysis examples

M 30 Oct — More examples; direct method

W 1 Nov — Binomial heaps

### Network flow

F 3 Nov

M 6 Nov

W 8 Nov

### Exam 2

- F 10 Nov — Exam 2