Week 3-4: Recursive algorithm, solving recurrences, divide and conquer,
Week 5-6: Lower bound of comparison based sorting
Week 7-8: Dynamic technique, rod cutting
Week 9-10: Dynamic technique, binary search tree
Week 11-12: Greedy method, activity selection
Week 13-14: Linear programming
Week 15-16: NP-completeness
Week 17-18: Final exam
Syllabus:
Express relationships between functions using asymptotic notation
Formulate and compare running time functions
Design efficient algorithms using techniques such as recursion, divide and conquer greedy method, linear programming or dynamic programming
Model computational intractability using NP-completeness
Understand how classes P, NP and NP-complete might be related and how to show a problem is in NP-complete