Detailed Schedule

Notes:

The following schedule is tentative. As we progress, I will update it so that dates correspond to what actually happened.
As assignments become available, they will be posted here. There are three ways to download assignments: as ps, pdf, and tex. These files are embedded in the homework tags: click on the assignment's "H" for its ps file, "W" for its pdf, and its number (e.g. 1a) for its LaTeX.
Although tentative, use this schedule to help plan ahead. Planning is made easier because I've color-coded potentially problematic dates: tentative exams and assignments that require programming are easy to spot.
Points in programming problems are given foremost for working code. Unless you are magically endowed with special powers in predicting how long debugging might take, begin these tasks as soon as you can.
Homework solutions 1a and 1b must be LaTeX'd. Towards this end, you'll want to download and modify their corresponding LaTeX files. Consult the additional information on using Latex in this class.

Week	Lec	Tuesday	Homework	Lec	Thursday	Homework
8/30	1	Introduction, Insertion Sort	H W 1a: Logs, Induction	2	Asymptotics, Merge Sort	H W 1b: Geo Series, Growth, Rank, Stock Market
9/6	3	Recurrence Relations: Strassen, Dim. Returns	H W 2a: Div-n-Conquer Multiplication	4	More Sorting, General Lower Bounds	H W 2b: Heaps, Stooge Sort, Lower Bounds
9/13	5	Priority Queues, Amortization	H W 3a: IncrKey, Amort. Ctrs	6	Order Stats, Linear Sorting	H W 3b: Select, Amort: Arrays, BuildHeap, StackBu
9/20	7	Red-Black Trees	H W 4a: Oil-of-Olay	8	B-Trees	H W 4b: B-Trees Sorting with Trees.
9/27	9	Dynamic Programming (DP): LCS, Knapsack	H W 5a: Mono, Load Balance, Skiing	10	More DP: Matrix Mult, Opt. Search Trees	MT#1 Study Guide (pdf,ps)
10/4	11	MT#1 Review	MT #1	12	Midterm Discussion Greed	H W 6b: Party Fun, Caution
10/11	13	Graph Algs: Intro	H W 7a: Diameters, Cycle Detection, (extra day)	14	MST: Prim	H W 7b: Greed is G-R-E-A-T (not assigned)
10/18		no class: fall break		15	More MST: Kruskal Union-Find	H W 8b: Baruvka, Integer weights
10/24	16	Shortest Paths Floyd-Warshall	H W 9a: FW	17	Bellman Ford, DAG-SP	H W 9b: FW-NCC, Arbitrage, BPST
11/1	18	Dijkstra's Algorithm	H W 10a: Dijkstra's Proof and Puzzles	19	Johnson's Algorithm	H W 10b: Johnson Problems, Hurts Navigation, Integer Dijkstra
11/8	20	Network Flow (NWF)	H W 11a: NWF Proofs, Simple example	21	More NWF	H W 11b: Cut finding, NASA Partitioning
11/15	22	Linear Programming	MT#2 Study Guide	23	Midterm Review	MT #2
11/22	24	NP-Completeness (NPC)	H W 13a: Prof Lai (easy!)		no class: thanksgiving
11/29	25	More NPC	H W 14a: ILP, Hit Set	26	And More NPC	H W 14b: Kernel, Network Reliability, 2SAT
12/6	25	Approx Algs	H W 15a: Disk Storage	26	Wrap-Up, Final Review	Final Study Guide
12/13	no class: finals week