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

Course materials

• Week 1-1 (1/19): Introduction, insertion sort, asymptotic notations
  • YouTube:
    • Merge procedure: Part 1, Part 2, Part 3
    • Examples for O-notation: Full

• Week 1-2 (1/21): More on big-O and algorithm analysis. Divide and conquer (maximum subarray sum)
  • YouTube:
    • Analysis of merge sort: Part 1, Part 2
    • Integer Multiplication: Part 1, Part 2
    • Solving recurrences with the recursion-tree method: Full

• 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)

Links

• Old home pages for 2014 and 2013