Purdue Engineering Professional Education

logo header header
Toll-Free in U.S. (877) 598-4233
     Print
CS58000 - Algorithm Design, Analysis, and Implementation

Spring 2014

Days/Time: TTh / 4:30-5:45 pm
Credit Hours: 3

Learning Objective:
To learn about and be able to apply data structures techniques and algorithm design and analysis techniques as the graduate level. To understand and construct lower bound proofs, as well as prove membership in problem classes such as NP-complete and PSPACE-complete.

Description:
Basic techniques for designing and analyzing algorithms: dynamic programming, divide and conquer, balancing. Upper and lower bounds on time and space costs, worst case and expected cost measures. A selection of applications such as disjoint set union/find, graph algorithms, search trees, pattern matching. The polynomial complexity classes P, NP, and co-NP; intractable problems.
Tentative Syllabus

Topics Covered:
Tentative: growth of functions asymptotic analysis
Karatsuba/Strassen
solving recurrence
probabilistic analysis, quick sort
linear time selection (randomized and deterministic)
lower bound of sorting
dynamic programming
divide and conquer
splay trees
binomial heaps
fibonacci heaps
treaps
union find
shortest path
max flow
depth first search
strongly connect components
string matching algorithm
fft
approximation algorithms
randomized algorithms
parallel algorithms
online algorithms
game theory
machine learning theory
NP-completeness

Prerequisites:
A bachelor degree in computer science or an equivalent field. Students not in the Computer Science master's program should seek department permission to register.
An undergraduate course in the analysis of algorithms, and an undergraduate course in the discrete mathematics used in computer science.

Applied/Theory: 30/70

Web Address:
https://www.cs.purdue.edu/homes/wu510/course/580s14/

Web Content:
Syllabus, grades, homework assignments, solutions, chat room and message board (via Piazza) will be available.

Homework:
Seven to ten written assignments. These assignments will generally involve the design and analysis of efficient algorithms and may require substantial thought. Approximately 10 hours per week on average.

Projects:
None.

Exams:
A midterm exam near the middle of the course, and a final exam.

Textbooks:
*Tentative-check the Office of the Registrar Textbooks for the official list*
Following two books are recommended: Dexter C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, 1992. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms , 3rd Edition, MIT Press, 2009.

Computer Requirements:
ProEd minimum computer requirements.

ProEd Minimum Requirements: view

Tuition & Fees: view

Yi Wu
Phone
765-496-2763
Email
wuyi@purdue.edu
Office
Purdue University
Computer Science Department
305 N University Street
West Lafayette, IN 47907-2107
Instructor HomePage