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 C or higher in MAT 211 or AMS 210; CSE 214 or CSE 260
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

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 Projects

Not applicable since it is a theory course.

Course Webpage

CSE373