COT 5405: Design and Analysis of
Algorithms
(Spring
2015)
Home
Schedule notes
Assignment
Class 1 (01/13): Course
introduction, Stable
Matching
Class 2 (01/15): Stable Matching (continue); analysis
Class 3 (01/20): Analysis (continue); Chapter 3: Graphs
Class 4 (01/22): Graphs (continue, demo
of DAG); Greedy: interval
scheduling
Class 5 (01/27): Greedy: scheduling
Class 6 (01/29): Greedy: shortest path, minimal
spanning tree; demo of
Dijkstra algorithm
Class 7 (02/03): Greedy: Huffman
code
Class 8 (02/05): revisit: Heapsort,
Priority Queue
Class 9 (02/10): Priority Queue (continue); Divide and
Conquer: Mergesort, counting inversions
Class 10 (02/12): Multiplication
; Unix machine in CS for teaching;
Programming assignment 1 is released and due Feb. 22nd midnight
via webCourse
Class 11 (02/17): Multiplication (continue); Dynamic
programming: weighted
interval scheduling
Class 12 (02/19): Dynamic programming: segmented least square,
knapsack
Class 13 (02/24): Dynamic programming: RNA secondary structure,
sequence alignment,
Class 14 (02/26): Dynamic programming: shortest path in graph
Class 15 (03/03): Mid-term Exam (closed
book)
Class 16 (03/05): Network flow: max flow
and mini cut (demo of max flow)
Class 17 (03/17): max flow
application
Class 18 (03/19): max flow application (continue); homework 2 is
assigned and due Mar. 29th midnight via WebCourse
Class 19 (03/24): Polynomial time reduction;
Class 20 (03/26): reduction (continue); NP-complete
Class 21 (03/31): NP-complete (continue); Poly-reduction
Class 22 (04/02): Poly-reduction (continue);
Class 23 (04/07): Approximation (demo of list scheduling)
Class 24 (04/09): Approximation (continue); Programming
assignment 2 is released and due April 19th midnight via
webCourse
Class 25 (04/14): Approximation: LP relaxation; Knapsack
approximation;
Class 26 (04/16): Randomization
Class 27 (04/21): Randomization (continue)
Class 28 ()4/23): Final exam review
April 30th (Thursday):
10am-12:50pm In-Class Final Exam