CS 4040/5040: Design and Analysis of Algorithms

Spring 2020

This course provides an introduction to the modern study of computer algorithms. Through this course students should be able to:

** Course materials**^{1}**:**

- Syllabus & Introduction
- Mathematical background
- Insertion Sort: proof of correctness
- Asymptotic analysis
- Merge Sort: analysis of time complexity
- Master Theorem
- Heapsort and Priority Queues
- Quicksort
- Comparison Sort: lower bound
- Count & Radix Sort
- Selection
- Matrix Multiplication; Closest Pair
- Hand notes on Selection and Strassen and Closest Pair

- Minimum Spanning Trees
- Single Source Shortest Paths
- Hand notes on paths in complete graphs

- Fractional Knapsack
- Hand notes on optimization formulation

- 0/1 Knapsack
- Matrix Chain Multiplication
- Hand notes on matrix chain multiplication, optimization, and recursive solution

- Longest Common Subsequence
- Hand notes on LCS example

- Coin-Changing
- All Pairs Shortest Paths
- Maximum Flow & Bipartite Matching
- Classes P & NP
- NP-completeness
- NP-complete problems

- Homework 1
- Homework 2
- Homework 3
- Homework 4
- Homework 5
- Homework 6
- Project and Sample files
- Homework 7