CS 473 - Algorithms I

Semester: Spring, 2013
Text Book: T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein Introduction to Algorithms, Mit Press and McGraw-Hill, 2009.
Reference: E. Horowitz and S. Sahni, Fundementals of Computer Algorithms, Computer Science Press 1978.
Instructor: Ugur Dogrusoz

Weekly Topics

WEEK(1): Introduction: analysing algorithms, designing algorithms.

WEEK(2): Asymptotic notation.

WEEK(3): Divide and conquer: Strassen

WEEK(4): Randomized quicksort: analysis.

WEEK(5): Medians and order statistics.

WEEK(6): Heaps: heapsort, priority queues.

WEEK(7): Sorting in linear time.

WEEK(8): Dynamic programming: matrix-chain multiplication, longest common subsequence.

WEEK(9): Dynamic programming: 0/1 Knapsack problem, resource allocation problem.

WEEK(10): Greedy algorithms: activity selection problem, Hufmann codes.

WEEK(11): Greedy algorithms: task scheduling problem.

WEEK(12): Amortized analysis: aggregate, accounting and potential methos, dynamic tables.

WEEK(13): Review

Last updated: XXX YY, ZZZZ