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.

Bulletin Link
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