Ait-aa-2014

This is a homepage for CS304 Advanced Algorithms.

Announcements

• Homework 1 is announced. You should work on this in class during the 1st hour of Jan 17th's class. It is due on Feb 7th. Jan 24th.
• Grading scheme: Midterm-1 25%, Midterm-2 25%, Final 30%, Homework 20%.

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: (to start working in class on Friday 17th, due Friday, Feb 7th Friday 31st Friday 24th)
  • Ch.2: Problems 2-2, 2-3.
  • Ch.3: Exercises 3.1-1, 3.1-2; Problems 3-1a, 3-1b, 3-2, 3-4.
• Homework 2: (announced Jan 30th, due Feb 14th)
  • Ch.4: Exercises 4.4-1 [4.2-1], 4.4-2 [no eq.], 4.4-9 [4.2-5]; Problems 4-1(a,b,d), 4-3(e,f,j) [4-4(e,f,j)], 4-5 [4-6].
• Homework 3: (announced Feb 11th, due Feb 28th)
  • Ch.5: Exercises 5.2-3, 5.2-4, 5.2-5; Problem 5-2.

Course materials

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

• Week 2 (1/17): Divide and conquer, recurrences
  • YouTube: Analysis of merge sort: Part 1, Part 2

• Week 3 (1/31): Divide and conquer, continue
  • YouTube:
    • Integer Multiplication: Part 1, Part 2
    • Solving recurrences with the recursion-tree method: Full

• Week 4 (2/7): Probabilistic analysis
  • YouTube: Probability Theory Review part 1, part 2

• Week 5 (2/14): Median and order statistics (9.2, 9.3)

• Week 6 (2/21): Sorting in linear time. (8.1, 8.3, 8.4)
  • YouTube: Lowerbound on comparion-based sorting Full

• Week 7 (2/28): Hash tables (11.1, 11.2, 11.3, 11.4); Dynamic programming (15.1)

• Week 8 (3/28): Dynamic programming (15.2, 15.4)

• Week 9 (4/4): Dynamic programming (15.4 cont), Greedy algorithms (16.1)

Links

• Last year course