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 31stFriday 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
Course materials
- Week 1 (1/10): Introduction, insertion sort, asymptotic notations
- Week 3 (1/31): Divide and conquer, continue
- 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)
