DESIGN AND ANALYSIS OF ALGORITHMS
Com S 311
Course Topics
The following is a tentative schedule of the topics we will be covering in class.
| Date | Sections | Topics |
|---|---|---|
| Aug 23 | 1.1-1.2, 2.1 | Introduction; Analysis of Insertion Sort |
| Aug 25 | 2.2 | Loop Invariants; Correctness of Insertion Sort and Merge Sort |
| Aug 27 | 2.3 | Analysis of Merge Sort; Divide and Conquer Algorithms |
| Aug 30 | 3.1 | Asymptotic Notation |
| Sept 1 | 3.2 | Growth of Functions |
| Sept 3 | A.1 | Summation Formulas |
| Sept 6 | - | University Holiday |
| Sept 8 | A.2 | Bounding Summations |
| Sept 10 | 4.1-4.2 | Recurrences |
| Sept 13 | 4.3-4.4 | The Master Method |
| Sept 15 | 6.1-6.3 | Binary Trees & Heaps |
| Sept 17 | 6.4-6.5 | Heapsort & Priority Queues |
| Sept 20 | 7.1-7.3 | Quick Sort & Randomized Quick Sort |
| Sept 22 | 7.4, 9.1 | Analysis of Quick Sort; Minimum & Maximum |
| Sept 24 | 9.2, 8.1 | Selection; Lower Bound on Sorting |
| Sept 27 | 8.2-8.3 | Sorting in Linear Time |
| Sept 29 | 12.1-12.3 | Binary Search Trees |
| Oct 1 | 13.1-13.2 | Red-Black Trees |
| Oct 4 | 13.3, 14.1-14.2 | Red-Black Tree Insertion; Augmenting Data Structures |
| Oct 5 | - | Exam I (6:30 pm - 8:30 pm) |
| Oct 6 | 15.2 | Matrix-Chain Multiplication |
| Oct 8 | 15.3 | Elements of Dynamic Programming |
| Oct 11 | 15.4 | Longest Common Subsequence |
| Oct 13 | 15.4 | Optimal Substructure Theorem |
| Oct 15 | 16.1 | Greedy Algorithms; Activity-Selection |
| Oct 18 | 16.2 | The Greedy Strategy |
| Oct 20 | 16.2, 16.3 | 0-1 Knapsack & Fractional Knapsack; Prefic Codes |
| Oct 22 | 16.3 | Huffman Codes |
| Oct 25 | - | No Class (due to Night Exam on Oct 5) |
| Oct 27 | B.4, B.5, 22.1 | Graphs and Trees; Graph Representations |
| Oct 29 | - | No Class (due to Night Exam on Nov 8) |
| Nov 1 | 22.2 | Breadth-first Search |
| Nov 3 | 22.3 | Depth-first Search |
| Nov 5 | 22.4 | Topological Sort |
| Nov 8 | 23.1 | Minimum Spanning Trees |
| Nov 8 | - | Exam II (6:30 pm - 8:30 pm) |
| Nov 10 | 23.2 | The Algorithms of Kruskal and Prim |
| Nov 12 | 24 | Single Source Shortest Paths |
| Nov 15 | 24.1, 24.3 | Dijkstra's Algorithm, Bellman-Ford Algorithm |
| Nov 17 | 25.1-25.2 | All-Pairs Shortest Paths, The Floyd-Warshall Algorithm |
| Nov 19 | 34.1-34.2 | Polynomial Time Verification |
| Nov 22 | - | Fall Break |
| Nov 24 | - | Fall Break |
| Nov 26 | - | Fall Break |
| Nov 29 | 34.3 | NP-Completeness & Reducibility |
| Dec 1 | 34.4 | NP-Completeness Proofs |
| Dec 3 | 34.5 | NP-Complete Problems and Reductions |
| Dec 6 | 32.1, 32.3 | String Matching |
| Dec 8 | 32.4 | The Knuth-Morris-Pratt Algorithm |
| Dec 10 | - | Exam III (in class) |
Iowa State University - Computer Science Department Top of this page