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.
• Homework 4: (announced Apr 9th, due Apr 25th)
  • Ch 8: Problem 8-4
  • Ch 9: Problem 9-1
  • Ch 11: Exercise 11.2-1, Problem 11-1
  • Ch 15: Problems 15-1, 15-4, 15-6

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)

• Week 10 (4/11): Greedy algorithms (16.2, 16.3)

• Week 11 (4/18): Amortized analysis (17.1, 17.2, [17.3], 17.4), Data structures for disjoint sets (21.1, 21.2, 21.3)

• Week 12 (4/25):

• Week 13 (4/28):

Links

• Last year course