Lecturer: | Rob Johnson |
TAs: | Sam McCauley (smccauley AT cs DOT stonybrook DOT edu) Li Niu (lniu AT cs DOT stonybrook DOT edu) |
Time: | MoWe 2:30-3:50pm |
Location: | Engineering 143 |
Office Hours: | Rob: We 4:00-5:30, Th 3:30-5:00 2313D Computer Science Building Sam: MoTh 1:15-2:15, 1309 Computer Science Building Li: Fr 9-10, TA Room (Computer Science Building) |
Home page: | http://www.cs.sunysb.edu/~rob/teaching/cse548-fa12 |
Sam's review session will take place tomorrow, Thursday Dec. 6th, at 1pm in room CS 2114. He will post pictures of the blackboard on Blackboard. He will cover B^epsilon-trees and the answers to the mid-term and HW3. Rob's review session will take place Monday, Dec. 10th, at 12pm in room CS 2120. Bring questions! The final exam will take place Tuesday, Dec. 11th, at 5:30pm in Benedict hall. This is a dorm building. I don't know the room number, so arrive early and look around. I will! Also, Matthew Cordaro has graciously posted a PDF with all his notes for the entire class on dropbox: http://tinyurl.com/bay8ndr.
Date | Topic/Reading assignment |
---|---|
8/27 | No class: Travel |
8/29 | No class: Travel |
9/3 | No class: Labor day |
9/5 | Hashing: chaining vs. linear probing, balls and bins, expected occupancy, w.h.p. definition, w.h.p. max bin, coupon collecting (a slight detour...) |
9/10 | Hashing: average vs worst case, algorithmic complexity attacks, 2-universal hashing, the power of 2 choices, cuckoo hashing, bloom filters, quotient filters |
9/12 | Sorting: merge sort, quick sort, divide and conquer, recurrence relations |
9/17 | Sorting: median-finding, lower bounds; Union-find and amortized analysis |
9/19 |
Heaps: Binomial heaps, Fibonacci heaps Rob's OH canceled |
9/24 |
Guest lecture: Don Porter Concurrent Algorithms Rob's OH canceled |
9/26 |
Guest lecture: Don Porter Concurrent Algorithms Rob's OH canceled |
10/1 | Ordered structures: 2-3 trees, red-black trees, splay trees |
10/3 | Ordered structures: treaps, cache-oblivious trees?, skip lists |
10/8 | Data structures for external storage: DAM model, B+-trees, LSM-trees |
10/10 | Data structures for external storage: Fractal trees (aka LSM-trees + fractional cascading), B^\epsilon trees, Sorting in external storage, k-way merge sort, distribution sort? |
10/15 |
Guest lecture (Rob's OH canceled) TBD |
10/17 |
Guest lecture (Rob's OH canceled) TBD |
10/22 | String algorithms: substring searching, longest-common substring, edit distance, longest repeated substring? |
10/24 | Graph algorithms: DFS, BFS, connected components, topological sort, minimum spanning tree, |
10/29 | Graph algorithms: matching, max-flow/min-cut, min-cost flow, dijkstra's algorithm, all-pairs shortest paths, CFL reachability |
10/31 |
Guest lecture (Rob's OH cancelled) TBD |
11/5 |
Guest lecture (Rob's OH cancelled) TBD |
11/7 |
Guest lecture (Rob's OH cancelled) TBD |
11/12 | Complexity theory: P vs NP, NP-completeness, NP-complete examples |
11/14 | Complexity theory: reductions, approximation algorithms, co-NP, PSPACE, EXP, P#, etc. |
11/19 | Linear programming: simplex algorithm, duality, primal dual method |
11/21 | No class: Thanksgiving break |
11/26 | Linear programming: polynomial-time algorithms, integer-linear programming, convex programming |
11/28 | Other fascinating topics: number theory (primality testing), FFT |
12/3 | Other fascinating topics: error-correcting codes, network coding, compression |
12/5 | Other fascinating topics: expander graphs, polynomial identity testing, matrix multiplication |
12/11 | Final Exam: 5:30-8:00 |
Note: If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, please contact the staff in the Disabled Student Services office (DSS), Room 133, Humanities, 632-6748v/TDD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.
Note: Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/.