Engineering Professional Education
  Menu

Algorithm Design, Analysis, and Implementation

CS58000

Spring 2018

Days/Time: TTh / 10:30-11:45 am
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.

Topics Covered:
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

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://mycourses.purdue.edu

Web Content:
Syllabus, grades, homework assignments, solutions, chat room and message board.

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:
T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, third edition, MIT Press (2009), ISBN:9780262033848

Computer Requirements:
ProEd minimum computer requirements.

ProEd Minimum Requirements: view

Tuition & Fees: view

SEMESTERS

Spring 2017
Spring 2018
Spring 2019
Spring 2020
Spring 2021

CURRENT INSTRUCTOR(S)

Jeremiah Blocki

Phone
None

Email
jblocki@purdue.edu

Office
Purdue University
Department of Computer Science
305 N University St
West Lafayette, IN 47907-2066

Instructor HomePage