COURSE TITLE: EECS 336 Design and Analysis of Algorithms

CATALOG DESCRIPTION: Analysis techniques: solving recurrence equations. Algorithm design techniques: divide and conquer, the greedy method, backtracking, branch-and-bound, and dynamic programming. Sorting and selection algorithms, order statistics, heaps, and priority queues.

REQUIRED TEXT: Kleinberg and Tardos, Algorithm Design, Addison Wesley

REFERENCE TEXT: Cormen, Leiserson, Rivest, & Stein, Introduction to Algorithms, McGraw-Hill

COURSE GOALS: This course will discuss fundamental concepts and techniques for designing efficient algorithms and analyzing their performance. Topics include recurrences; sorting and order statistics; dynamic programming; greedy strategies; amortized analysis; advanced data structures; graph algorithms; efficient reductions and computational hardness.

COURSE COORDINATOR: Jason Hartline

PREREQUISITES: EE CS 310 and EECS 311

COURSE TOPICS:

Examples of efficient algorithms and performance analysis.

Recurrences.

Sorting and order statistics.

Dynamic programming.

Greedy Strategies.

Amortized Analysis.

Basic and advanced data structures.

Graph algorithms.

Efficient reductions and NP-Completeness.

HOMEWORK ASSIGNMENTS:

There will be weekly reading assignments and weekly problem sets.

GRADES:

Problem sets – 60%

Midterm – 10%

Final exam – 30%