CSE 548 / AMS 542 Fall 2012. Graduate Analysis of Algorithms

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

News

Overview

This course will introduce the tools for designing and analyzing algorithms for solving common problems in computer science, with a special emphasis on algorithms that one would actually want to use. The course will also introduce probabilistic methods needed to analyze randomized algorithms, and will cover basic complexity theory and approximation algorithms for hard problems.

Topics

Some subset of the following:

Requirements and Grading

Subject to tweaks throughout the semester.

Class Notes

If you would like to earn extra credit, you may volunteer to write up notes for a lecture. We will choose the best three sets of notes submitted for each lecture and post these to the course website. Only notes posted to the course website will earn extra credit. Extra credit will be curved to the final class grades such that 8 sets of notes will improve your grade by one step (e.g. from a B+ to an A-). Thus, for example, if you have notes posted for every lecture, then your final grade will be improved by one whole letter grade. Notes must be submitted in PDF format. Notes should be emailed to the TAs.

References

There is no required course textbook. I will be using the following resources to prepare the class, so they should be good references for studying:

Tips on doing well in the class

Lecture Schedule

Here's a very optimistic schedule. We'll be lucky to get through 2/3 of this material in the semester.
Warning: The notes below may contain errors. Use with caution.
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/.