# Topics

## 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)