## Assignments

- HW 4 [ TeX ] : due Friday, February 17 @ 4pm
- 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

HW 7 [ TeX, lorem.txt, neruda.tar ] : due Friday, March 17 @ 4pm

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

## Lectures

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

### Introduction to Algorithms

W 18 Jan — Stable matchings and the Gale-Shapley algorithm

*K&T Ch. 1, including Solved Exercises*F 20 Jan — Proof of Gale-Shapley algorithm correctness

M 23 Jan — Data representations for Gale-Shapley

*K&T Ch. 2*W 25 Jan — Asymptotic analysis

F 27 Jan — Asymptotic analysis II (Complexity zoo)

M 30 Jan — Largest sum subinterval problem

### Graphs

W 1 Feb — More LSS, intro to graphs (representation, paths, cycles, trees)

*K&T 3.1*F 3 Feb — BFS (definitions, properties, asymptotics)

*K&T 3.2, 3.3*M 6 Feb — Bipartite graphs, directed graphs

*K&T 3.4, 3.5*W 8 Feb — DAGs and topological sorting

*K&T 3.6*

### Greedy Algorithms

F 10 Feb, M 13 Feb — Dijkstra’s Algorithm

*K&T 4.4*W 15 Feb — Kruskal’s and Prim’s MST algorithms

*K&T 4.5*F 17 Feb — Implementing Prim’s algorithm

*K&T 4.6*W 22 Feb — Implementing Kruskal’s algorithm, Union-Find structure

*K&T 4.6*

### Exam 1

- F 24 Feb —
**Exam 1**

Covering asymptotic analysis, graphs, and greedy algorithms

### Divide and Conquer

M 27 Feb — Integer multiplication, Master Theorem

*K&T 5.1, 5.2, 5.5*W 1 Mar — Matrix multiplication, FFT intro

*K&T 5.6*F 3 Mar — FFT [ slides ]

*K&T 5.6*

### Dynamic Programming

M 6 Mar — Intro to Dynamic Progragmming (Fibonacci, hi/lo stress jobs)

*K&T*6.1, 6.2W 8 Mar — Matrix chain multiplication (MatrixChainFull.java)

*K&T*6.5F 10 Mar — Floyd-Warshall algorithm

*K&T*6.8

### Network Flow

M 13 Mar — Network flow I (definitions, Ford-Fulkerson algorithm)

*K&T*7.1W 15 Mar — Network flow II (F-F algo examples, flows and cuts)

*K&T*7.2F 17 Mar — Network flow III (max flow/min cut theorem)

*K&T*7.5, 7.6

**Spring break**

### Amortized analysis

M 27 Mar — Intro to amortized analysis. Aggregate method, accounting method

W 29 Mar — Binomial trees and heaps

F 31 Mar — Potential method, splay trees

M 3 Apr — Analysis of splay trees

### Exam 2

- W 5 Apr —
**Exam 2**

Covering divide & conquer, DP, network flow, and a bit of amortized analysis

### Intractability

F 7 Apr — Reductions

*K&T*8.1M 10 Apr — SAT, 3-SAT

*K&T*8.2W 12 Apr — NP, NP-completeness

*K&T*8.3F 14 Apr — CIRCUIT-SAT is NP-complete

*K&T*8.4M 17 Apr — Lots of things are NP-complete

(3-SAT, SAT, independent set, vertex cover, set cover, travelling salesman, hamiltonian circuit)

*K&T*8.4, 8.5

### Strings and matching

W 19 Apr — Rabin-Karp matching

F 21 Apr — Rabin-Karp matching II

M 24 Apr — Radix sort

W 26 Apr — Suffix tries I

F 28 Apr — Suffix tries II

M 1 May — Suffix tries III

### Final exam

- M 8 May —
**Final exam**(Cumulative)