**DESIGN AND ANALYSIS OF ALGORITHMS**

Com S 311

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