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. This course is offered as CSE 373 and MAT 373.

Bulletin Link

• Ability to perform worst-case asymptotic algorithm analysis
• Ability to define and use classical combinatorial algorithms for problems such as sorting, shortest paths and minimum spanning trees
• Understanding of computational intractability and NP completeness
• Ability to apply data structure and algorithmic techniques to design computationally efficient solutions.

Steven Skiena, The Algorithm Design Manual, second edition, Springer-Verlag, 2008.

• 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)

Not applicable since it is a theory course.

CSE373