Title: Analysis of Algorithms (crosslisted with AMS 373 and CSE 373)

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.

Prerequisite: C or higher in MAT 211 or AMS 210; CSE 214 or CSE 260

Credits: 3

Textbook:

   Note: Subject to change - do not buy before confirming with the course instructor

Major Topics Covered: 

  • Preliminaries: Algorithm Correctness, Asymptotic (big-Oh) Notation, Problem Modeling
  • Data Structures: Review of Elementary Data Structures (stacks/queues), Dictionary Data Structures Such As Binary Search Trees, Priority Queues Such As Heaps
  • Sorting: Algorithmic Applications of Sorting, Analysis of Quicksort, Mergesort, and Heapsort, Distribution/radix Sorting, Lower Bounds
  • Problem Decomposition Algorithms: Dynamic Programming (edit Distance, Chain Matrix Multiplication), Divide-and-conquer Algorithms (binary Search and Ariants)
  • Combinatorial Search: Backtracking, Exhaustive Search, Permutations/subsets
  • 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)
  • Intractability: Problem Reductions, NP-completeness, Approximation Algorithms

Undergraduate Bulletin Course Information

Course Webpages: