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

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