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

## 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 Prim’s MST algorithm

*K&T 4.6*W 27 Sep — Implementing Kruskal’s MST algorithm, Union-Find structure

*K&T 4.6*

## Exam 1

- F 29 Sep — Exam 1