This shows the start of the semester and key dates. Progress will probably be better indicated in the homework. An approximate overall list of topics, mostly in the right order is given at the end. Dates will depend on our speed.
Introduction, induction, asymptotic growth rates,
Ch1, 2.1-3, Appendix A
Questions on Ch 1, 2.1-3 reading; basic math reference, Simple recursive functions and order estimates, recursive examples, simple sorts, Master Theorem, merge sort, start quicksort
Section 2.4, 3.1, 4.1, Appendix B, 5.1, 5.2
more quicksort, binarysearch, divide+conquer, other sorts
Section 5.3, 5.5
Feb 13, Feb 20
Feb 27(quiz due)
Mar 5 - vacation
Mar 19, Mar 26, Apr 2, Apr 9
Apr 16 (quiz due)
This is a quick start. I still need to update some of the order and numbering, since the latest edition of the text has shifted some things.
Read ch 1 - data structure and algorith background. What was not in 271? What needs more coverage?
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)