CS 410 Top: Algorithm Design & Analysis

Credit Hours:	4
Course Coordinator:	Dave Maier
Course Description:	An advanced, in-depth study of the design and analysis of algorithms. Topics include models of computation, sorting, data structures, graph algorithms, matrix multiplication, fast Fourier transforms, polynomial arithmetic, pattern matching, and NP-complete problems.
Prerequisites:	Introductory course in algorithms, data structures, discrete math.
Goals:	Upon the successful completion of this course students will be able to: Analyze a straightforward algorithm that involves simple loop structures. Set up recurrence equations that describe the time complexity of recursive algorithms, and solve the straightforward cases. Apply a repertoire of standard algorithms and techniques to novel problems. Read the well-written description of an algorithm from the computing literature and convert it to code that achieves the best asymptotic performance for that algorithm. Use asymptotic notation correctly. Recognize NP-complete problems and apply appropriate techniques to solve them. Recognize problems where dynamic programming is an appropriate solution method and be able to apply it. Describe the way to prove a problem is NP-complete. Apply divide-and-conquer techniques to develop problem solutions, and analyze the time complexity of the resulting algorithm. Recognize opportunities for creative application of sorting and hashing techniques to develop problem solutions. Apply the concept of amortized analysis in straight forward cases.
Textbooks:	Introduction to Algorithms (2nd edition), by Cormen et al.
References:	None.
Major Topics:	Review of data structures, sorting algorithms, asymptotic notation, loop invariants, analysis of simple loops, recurrences and the divide-and-conquer strategy. Breadth first and depth first search and applications; other graph algorithms as time permits. Proofs using structural induction, using graph algorithms as the example. Computational geometry and the use of sorting and balanced trees to achieve good performance. NP-completeness: definition, proof, reductions, approximations. Fast Fourier transforms as an example of divide and conquer. Amortized analysis. Strassen's algorithm (divide and conquer) and multiplication of a string of matrices (dynamic programming) String matching (if time permits)
Laboratory Exercises:	The class requires written homework and a major project, plus occasional programming exercises.

CAC Category Credits	Core	Advanced
Data Structures	0.5	1.0
Algorithms	0.5	2.0
Software Design
Computer Architecture
Programming Languages

Oral and Written Communications:	Every student writes a paper of about 10 pages explaining and commenting on a paper in the recent computing literature.
Social and Ethical Issues:	None.
Theoretical Content:	Analysis of algorithms, algorithm selection, associated mathematical techniques, concept of NP-completeness, techniques for proving algorithms are correct.
Problem Analysis:	A major goal of the course is to teach students to choose an appropriate algorithm to solve a problem. In a sense the whole class is about analyzing this problem.
Solution Design:	The students will learn to design good algorithms for solving problems of various types.