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)