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].

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.

Links

• Old home pages for 2014 and 2013