Syllabus : Posted on August202014.
Last day to drop and receive 100% financial credit: Aug272014
Last day to drop and (possibly) get a W grade: Oct312014
Dr. Koh will instruct this class on and from Sep25. Assignment 3 is still due on that day.
Midterm on: 
Syllabus: TBD. 
Final on: 
Syllabus: TBD 
Assignment 9 
Due on TBD 
Assignment 8 
Due on TBD 
Assignment 7 
Due on TBD 
Assignment 6 
Due on TBD. Problems 12.11 (2X5 pts), 12.21 (5 pts), 12.24 (5 pts), 12.34 (5 pts), 13.12 (5 pts), 13.32 (10 pts). 
Assignment 5 
Due on TBD. Problems 11.12 (3pts), 11.22 (5 pts), 11.25 (5 pts; apply the pigeonhole principle), 11.34 (5 pts). Problem 11.33 for graduate students only (10 pts; extra credits for undergrads). 
Assignment 4 
Due on TBD. Problems 7.11 (10 pts), 7.22 (3 pts), 8.21 (10 pts), 8.31 (5 pts), 8.32 (3+4 pts), 8.41 (5 pts). Problem 8.13 (4X3 pts) for graduate students only (extra credits for undergrads). 
Due on TBD. Submit a onepage printed or handwritten report only. No emails. 

Assignment 3 
Due on Sep252014. Problems 6.14 (4 pts), 6.16 (4 pts), 6.21 (6 pts), 6.32 (4 pts). Problem 6.33 (6 pts) for graduate students only (extra credits for undergrads). The complete problem statements can be found here (thanks to Jundi Wang). 
Due on Sep162014. Note: "(repeated) substitution" refers to the iteration method shown in class. 

Due on Sep042014. 
Introduction, review of mathematical induction, asymptotic notation 

Insertion sort, asymptotic analysis 

Merge sort, recurrence relations, solution by substitution and iteration 

Recurrences and master theorem, Heapsort. 

Quicksort. 

Lower bound of sorting, linear time sorting: counting sort, radix sort and bucket sort. 

Hash tables. 

Binary Search Trees. 

Red Black Trees. 

Insertion in Red Black Trees. 

Dynamic Programming: LCS, matrixchain multiplication. 

Dynamic Programming: 01 Knapsack. 

Greedy Algorithms: Activity Selection, fractional knapsack. 

Graph basics with breadth first seach. 

Graph algorithms: Depth first search. 

Graph algorithms: Topological sort, minimum spanning tree and Prim's algorithm. 

Graph algorithms: Single source shortest path, BellmanFord and Dijkstra's algorithms. Also contains Kruskal's algorithm for minimum spanning trees. 

NPCompleteness. 

NPCompleteness and reductions. 