# Algorithms - Spring 2012 - Tentative Major Dates and Topics

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.

Jan 23

Ch1, 2.1-3, Appendix A

Jan 30

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

Feb 6

more quicksort, binarysearch, divide+conquer, other sorts

Section 5.3, 5.5

Feb 13, Feb 20

Feb 27(quiz due)

Mar 5 - vacation

Mar 12
Midterm Exam

Mar 19, Mar 26, Apr 2, Apr 9

Apr 16 (quiz due)

Apr 23
Review
Apr 30
Final exam

# Topic sequence

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)