# Topic sequence

See the schedule so far.

• Read ch 1: Is this review?
• Read ch 2.1 basics or measurement of algorithms, into 2.2 to p 53 (big Oh), plus 2.3 on basic analysis of non-recursive algorithms: How much is review? What do you want to go over? I will go over theta and omega orders, in 2.2, and tie together all the order discussion.
• Appendix A: math formulas - for your notes. Good to know what has a formula, and be able to look up details in your notes.
• 2.4 A bit on analysing recursive algorithms (more later) example of recursion with trees:
• 5.4 mostly review of binary tree terminology, pre, post, inorder traversals,
• 4.4: Generating combinatorial objects, also recursive
• Basic sorts, searches, naive algorithms: 3.1 (selection sort), 4.1 (insertion sort), 3.2 (sequential search), 3.4 Knapsack problem
• Further search, sort, with an emphasis on divide and conquer: AppendixB, 5.1 (merge), 5.2 (quick), 5.3 (binary search, emphasize average), 4.6 median, 5.5 Strassen matrix mult - reference as a totally different divide and conquer application from the sorts, and other sorts: 6.4 Heap sort, 7.1 counting sort; sort analysis: 11.2 decision trees.
• Dynamic data structures: my amortizing notes, 7.3 hashing, 7.4 B-trees (largely my notes added)
• basic graph algorithms: 4.2 depth and breadth first searches, 4.3 topological sorting, with additional notes, for strongly connected components of digraphs, and the decomposition of a digraph into a DAG of strongly connected components.
• greedy techniques; more graphs: 9.1 Prim, data structure: priority heap with decrease key, 9.2 Kruskal, data structure: union-find in-tree, 9.3 Dijikstra, other greedy: 9.4 huffman
• More graphs: all pairs shortest path: Warshall, Floyd
• Dynamic programming: (largely my notes) fibonacci seq as basic example, problems from my notes, 8.4 knapsack
• P, NP, NP complete 11.3 (plus some extra notes)