CSE385

Course CSE385
Title Analysis of Algorithms: Honors
Credits 4
Course Coordinator Michael Bender
Description

Algorithmic design and analysis for Computer Science Honors students.  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. Randomization.  Introduction to NP completeness. Some machine computation is required for the implementation and comparison of algorithms.
Prerequisite Prerequisites: CSE 113 or CSE 150 or CSE 215 or MAT 200 or MAT 250; AMS 210 or MAT 211; CSE 214 or CSE 260; Honors in Computer Science or the Honors College or the WISE Honors Program or University Scholars or Simons STEM Scholars.
Course Outcomes
  1. Ability to perform worst-case asymptotic algorithms analysis.
  2. Ability to define and use classical combinatorial algorithms for problems such as sorting, shortest paths and minimum spanning trees.
  3. Understanding of algorithmic techniques such as divide-and-conquer and dynamic programming. 
  4. Understanding of computational intractability and NP completeness.
  5. Ability to apply data structure and algorithmic techniques to design computationally-efficient solutions.
Textbook

None
Major Topics Covered in Course
  • Asymptotic notation
  • RAM and other computational models
  • Divide and Conquer (Merge Sort, Exponentiation, Matrix Multiplication, Strassens Algorithm, Median Finding, Master Method, Median Finding, Closest Pair Problem)
  • Dynamic Programming (Edit Distance, Knapsack Problem, Space-Efficient Edit Distance, Shortest-path In DAGs and Applications)
  • Introduction to Graphs (Directed and Undirected Graphs, Depth First Search and Breadth First Search, Topological Sort, Shortest Path Algorithms)
  • Minimum Spanning Trees (Prims, Kruskalls, Boruvkas)
  • Big Data Algorithms, External-Memory Algorithms, and Cache-Oblivious Algorithms
  • Randomized Algorithms and Data Structures (Karp-rabin String Matching, Skip Lists, Search Trees, Hashing)
  • NP Completeness and Reductions
Laboratory

N/A
Course Webpage

CSE385