Michael Bender

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. 

Bulletin Link

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.

None

• 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

N/A

CSE385