Classroom:	MWF: 1:10p-2:00p, MCRey 315
Web page	www.cburch.com/cs/280/
Instructor:	Dr. Carl Burch
E-mail:
Telephone:	450-1377 (office); 548-0036 (home)
Office:	MCRey 310
Office hours:	M 9:10-10:00, W 2:10-3:00, R 1:10-2:00, F 9:10-10:00 drop-ins, appointments always welcome

Useful links

Textbook PDFs (official site)
Sauron submission system (instructions)

Schedule

The assignment of topics to days will change as the class progresses.

Textbook references are on the right, prefaced by a section symbol §.

Wed 14 Jan	exhaustive search
Fri 16 Jan	no class
29 Jan	MLK day - no classes
Wed 21 Jan	big-O §0.3
Fri 23 Jan	big-O & recurrences recurrence induction proof
Mon 26 Jan	divide and conquer Master Theorem §2.2 faster multiplication §2.1
Wed 28 Jan	matrix multiplication §2.5
Fri 30 Jan	Assn 1 due medians §2.4 graphs §3.1
Mon 2 Feb	graph representation §3.1 depth-first search §3.2–3.3
Wed 4 Feb	dags & topological sort §3.3 shortest distance in dags §6.1
Fri 6 Feb	longest increasing subsequence §6.2
Mon 9 Feb	Quiz 1 [Review]
Wed 11 Feb	knapsack problem §6.4
Fri 13 Feb	Take-Home Exam 1 due no class — programming contest
Mon 16 Feb	edit distance §6.3
Wed 18 Feb	limited-edges shortest path §6.6 independent set in tree §6.7
Fri 20 Feb	all-pairs shortest path §6.6 priority queues §4.5
Mon 23 Feb	Dijkstra's algorithm §4.4 Bellman-Ford algorithm §4.6
Wed 25 Feb	breadth-first search §4.2 reductions what is P? §8.2
Fri 27 Feb	what is NP? §8.2
Mon 2 Mar	Quiz 2 [Review]
Wed 4 Mar	reducing SAT to 3SAT §8.3
Fri 6 Mar	Assn 2 due reducing 3SAT to 3D MATCHING §8.3 reducing 3D MATCHING to ZOE §8.3 reducing ZOE to SUBSET SUM §8.3 reducing SUBSET SUM to KNAPSACK §8.1
7-15 Mar	Spring break - no classes
Mon 16 Mar	reducing 3SAT to INDEPENDENT SET §8.3 reducing INDEPENDENT SET to VERTEX COVER §8.3 reducing INDEPENDENT SET to CLIQUE §8.3
Wed 18 Mar	Extra Credit 1 due, 1pm approximation algorithms §9.2 approximating VERTEX COVER §9.2.1
Fri 20 Mar	Project 1 paper due approximating CLUSTERING §9.2.2 approximating SET COVER §5.4
Mon 23 Mar	approximating TSP §9.2.3 Prim's MST algorithm §5.1.5
Wed 25 Mar	Project 1 presentations
Fri 27 Mar	Extra Credit 2 due, 1pm Project 1 presentations
Mon 30 Mar	approximating KNAPSACK §9.2.4
Wed 1 Apr	Kruskal's MST algorithm §5.1.3 union-find ADT §5.1.4
Fri 3 Apr	Take-Home Exam 2 due, 5am no class - CCSC:MS conference
Mon 6 Apr	Quiz 3 [Review]
Wed 8 Apr	linear programming §7.1–7.1.2
Fri 10 Apr	Assn 3 due rounding LPs for SET COVER
Mon 13 Apr	maximum flow §7.2–7.2.3
Wed 15 Apr	minimum cuts §7.2.4–7.2.5 bipartite matching §7.3
Fri 17 Apr	Project 2 paper due distributed models (reading, §1) parallel sum (reading, §2)
Mon 20 Apr	parallel prefix scan (reading, §3)
Wed 22 Apr	Project 2 presentations
Fri 24 Apr	Project 2 presentations
Mon 27 Apr	linear programming review parallel merge sort (reading, §4) NC complexity class (reading, §5)
Thu 30 Apr	Take-home portion of final due, 10am
Tue 5 May	In-class portion of final, 2pm [Review]
7 May-24 Aug	Summer break - no classes