Ait-aa
ไปยังการนำทาง
ไปยังการค้นหา
This is a homepage for CS304 Advanced Algorithms.
Homework
Each problem refers to the problem in the 3rd Edition of CLRS. For owners of the 2nd Edition book, most problems remain the same, for those which are different, an equivalent problem in the 2nd Edition is provided in brackets.
- Homework 1 (due 18 Feb):
- Chapter 2: Problem 2-3.
- Chapter 3: Exercises 3.1-1, 3.1-2; Problems 3-1a, 3-1b, 3-2, 3-4.
- Chapter 4: Exercises 4.4-1 [4.2-1], 4.4-2 [no eq.], 4.4-9 [4.2-5]; Problem 4-5 [4-6].
- Homework 2 (due 14 Apr):
- Chapter 17: Exercise 17.1-3, 17.2-1, 17.2-2
- Chapter 15: Problems 15-1, 15-4, 15-6
- Homework 3 (due 21 Apr):
- Chapter 5: Exercises 5.2-3, 5.2-4, 5.2-5; Problem 5-2
- Chapter 8: Problem 8-4
- Chapter 9: Problem 9-1
- Homework 4
- Chapter 16: Exercise 16.1-2, 16.1-4
- Chapter 22: Exercise 22.3-2
- Chapter 23: Exercise 23.1-1, 23.1-5
- Chapter 34: Exercise 34.1-4, 34.2-6, 34.5-1; Problems 34-1(a), 34-1(b)
Course materials
- Week 1-1 (1/19): Introduction, insertion sort, asymptotic notations
- Week 1-2 (1/21): More on big-O and algorithm analysis. Divide and conquer (maximum subarray sum)
- Week 2-1 (1/26 - 1:30 hours): Integer multiplication. Solving recurrences. Master's theorem. Balls and bins.
- Week 3-1 (2/2): Practice on divide and conquer (convex hull problem). Review on probability theory. The hiring problem. The birthday problem.
- week 3-2 (2/4): Balls and bins. Analysis of the heaviest bins. Binomial and geometric random variables. Coupon collector's problem.
- week 4-1 (9/2 - 1:45 hrs): Randomized quick sort. Comparison-based sorting lower bound.
- week 5-1 (16/2 - 1:45 hrs): Linear time sorting algorithms. Intro to selection algorithms.
- week 5-2 (18/2 - 1:30 hrs): Worst-case quick selection algorithm. Randomized selection algorithm. Intro to AVL trees.
- week 6-1 (23/2): AVL trees. Amortized analysis: lazy deletions, dynamic tables, multi-level sorted arrays.
- week 7-1 (8/3): Potential methods. Splay trees. Scapegoat trees.
- week 8-1 (15/3): Dynamic programming 1: Introduction, Rod cutting, Longest increasing subsequence
- week 8-2 (17/3): Dynamic programming 2: Matrix chain multiplication, Longest common substring
- week 9-1 (31/3 - 3 hrs): Dynamic programming 3: Review, Edit distance, Knapsack
- week 10-1 (7/4 - 3 hrs): Greedy algorithms (activity selection, Huffman codes)
- week 11-1 (12/4): Basic graph algorithms (graph search, DFS, BFS)
- week 12-1 (19/4): Minimum spanning trees, shortest paths
- week 12-2 (21/4): NP-completeness 1
- week 13-1 (25/4 - 3 hrs): NP-completeness 2. Additional data structures (Hashing, B-trees, Fibonacci heaps, van Em Bose trees)
