CSE373

Course CSE373
Title Analysis of Algorithms
Credits 3
Course Coordinator

Steven S. Skiena
Description

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.
Prerequisite Prerequisites: C or higher in: CSE 113 or CSE 150 or CSE 215 or MAT 200 or MAT 250; MAT 211 or AMS 210; CSE 214 or CSE 260; CSE or MAT or DAS major
Course Outcomes
  • 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.
Textbook

Steven Skiena, The Algorithm Design Manual, second edition, Springer-Verlag, 2008.
Major Topics Covered in Course
  • 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)
Laboratory

Not applicable since it is a theory course.
Course Webpage

CSE373