**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:**

- Algorithm Design by Kleinberg and Tardos

**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: **