CSE373

CSE373

Analysis of Algorithms

3

Steven S. Skiena

Mathematical analysis of a variety of computer algorithms including searching, sorting, matrix multiplication, fast Fourier transform, and graph algorithms. Time and space complexity. Upper-bound, lower- bound, and average-case analysis. Introduction to NP completeness. Some machine computation is required for the implementation and comparison of algorithms.

MAT 211 or AMS 210; CSE 214

• Provide a rigorous introduction to worst-case asymptotic algorithm analysis.
• Develop classical graph and combinatorial algorithms for such problems as sorting, shortest paths and minimum spanning trees.
• Introduce the concept of computational intractability and NP completeness.

Fundamentals of Algorithmic, Gilles Brassard and Paul Bratley, Prentice Hall ISBN: 0-13-335068-1

The Algorithm Design Manual, Steven Skiena, Springer-Verlag, NY 1997

• Preliminaries: Algorithm correctness, asymptotic (big-Oh) notation, problem modeling , (1.5 weeks)
• Data Structures: Review of elementary data structures (stacks/queues), dictionary data structures such as binary search trees, priority queues such as heaps, (1.5 weeks)
• Sorting: Algorithmic applications of sorting, analysis of quicksort, mergesort, and heapsort, distribution/radix sorting, lower bounds, (1.5 weeks)
• Problem Decomposition Algorithms: Dynamic programming (edit distance, chain matrix multiplication), divide-and-conquer algorithms (binary search and variants), (1.5 weeks)
• Combinatorial Search: Backtracking, exhaustive search, permutations/subsets, (1 week)
• Graph Algorithms: graph data structures (adjacency lists/arrays), BFS/DFS, topological sorting, connectivity testing, minimum spanning trees, shortest paths (Dijkstra's and Floyd's algorithms), (3 weeks)
• Intractability: problem reductions, NP-completeness, approximation algorithms, (2 weeks)

http://www.cs.sunysb.edu/~cse373