CS 58000 --- Spring 2016

Design and Analysis of Algorithms

Professor:

Greg N. Frederickson
Office: LWSN 2116E
Office hours: MW 3:30-5:00pm, and by appointment
email: gnf at cs.purdue.edu
We will use Blackboard: https://mycourses.purdue.edu/

Assistant:

Young-San Lin

Text:

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
Introduction to Algorithms, third edition, MIT Press, 2009.

Partial List of Topics:

Recurrence Relations
Prune and Search, and Divide and Conquer
Dynamic Programming
Data Structures including Fibonacci heaps, disjoint sets
Graph Algorithms including max flow (Goldberg-Tarjan)
Lower Bound Techniques
NP-complete Problems including approximation algorithms
PSPACE-complete Problems
Randomized Algorithms ?

Course Work:

Approx. weight in grade
Written assignments (7-10) 30%
Midterm exam (8:00pm-10:00pm, February 29, in ARMS 1010) 35%
Final Exam (during exam period) 35%

Prerequisites:

CS 38100

Assignments:

Will be posted on Blackboard.




Last updated December 16, 2015.