|
CS 3343/3341 Analysis of Algorithms
Spring 2012 Calendar | |||||
| Week | Dates
<Notes> |
Lecture Topics |
Recitations | Weird Topics |
Exams,
etc. |
| 1 |
Jan 17 Jan 19 |
Exponentiation,
survey
binary, ternary search |
0 Practice 1 Queues, Ans |
1 WOM Storage 2 Fib. Search |
None |
| 2 |
Jan 24 Jan 26 |
Random #s, Quicksort randomization |
2 Recursion, Ans |
3 Bolts & nuts 4 Fake Coin |
Quiz 1, Answers |
| 3 |
Jan 31 Feb 02 |
Circular queues Recursion trees |
3 Linked Lists, etc. Ans |
5 Fib. Matrix 1 | None |
| 4 |
Feb 07 Feb 09 |
Divide and Conquer, merge sort |
4 Binary Search Trees, etc. Ans |
6 Newton's Meth. 1 |
Quiz 2, Answers |
| 5 |
Feb 14 Feb 16 |
Strassen's matrix mult., fast multiplication |
5 Heapsort, Median Ans |
7 Fib. Matrix 2 8 Half-a-Bit 1 |
None |
| 6 |
Feb 21 Feb 23 |
Dyn. Prog., memoization Applications |
6 Recurrences Ans |
None | |
| 7 |
Feb 28 Mar 01 |
Catch up (or ketchup) |
7 Dyn Prog., etc. Ans |
9 Merkle's Puzzles |
None |
| 8 |
Mar 06 Mar 08 |
Review Exam |
8 Exam Review Ans |
10 Hamiltonian Path |
Exam, answers |
| Spring Break: 12-16 March 2012 | |||||
| 9 |
Mar 20 Mar 22 |
Graphs, representations Breadth- depth- first srch |
None | 11 Newton's Meth. 2 |
None |
| 10 |
Mar 27 Mar 29 |
Shortest paths,
QC Min. spanning tree |
9 Graph Rep. Ans, C Ans |
None | |
| 11 |
Apr 03 Apr 05 |
Hierarchy | 10 Graph Srch, Ans |
None | |
| 12 |
Apr 10 Apr 12 |
Hashing | 11 Dijkstra-log2 | 12 Zero-Know. Proofs |
None |
| 13 |
Apr 17 Apr 19 |
NP,
NP-complete, NPC Examples |
12 Hashing, etc., Ans |
None | |
| 14 |
Apr 24 Apr 26 |
Turing Machines, Undecidable Probs. |
13 Final Review, Ans |
Quiz 3, answers |
|
| 15 | May 01 | More on undecidability | None | None | None |
| May 7 10:30-1pm |
Final Exam | Final Answers |
|||
|
Color coded links: Dark means "material posted or covered." Light means "material not yet posted or not yet covered."
| |||||