CSE 548/AMS 542 Spring 2016. Algorithms
|Rob's Office Hours:
||Tu 4:00pm-5:30pm, Th 1:00pm-2:00pm, 368 Computer Science Building
|Tim Barron's Office Hours:
||We 4-5pm 2217 OLD Computer Science Building
|Sarthak Ghosh's Office Hours:
||Mo 12:15-2:15pm, 2217 OLD Computer Science Building
|Ziqiao Guan's Office Hours:
||We 3-5pm, 2217 OLD Computer Science Building
|Yuren Huang's Office Hours:
||Th 2:30-3:30pm, 2217 OLD Computer Science Building
|Chai Zhi's Office Hours:
||We 2:30-3:30pm, 2217 OLD Computer Science Building
- May 3. HW3 is now available. Due at the exam.
- Apr. 12. Solutions for HW2 are now available.
- Mar. 29. HW2 is now available. Due in class 4/7.
- Feb. 17. All future announcements will be made on Piazza.
- Feb. 17. Rob's OH tomorrow and all next week are canceled.
- HW1 is now available. Due in class 2/18.
Remember: 10% bonus for typing it up and 25% credit for saying "I
don't know" in answer to any problem. (But not both bonuses).
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.
Some subset of the following:
- Hashing: chaining vs. linear probing, balls and bins, expected
occupancy, w.h.p. definition, w.h.p. max bin, coupon collecting (a
slight detour...) , average vs worst case, algorithmic complexity
attacks, 2-universal hashing, the power of 2 choices, cuckoo
hashing, bloom filters, quotient filters
- Sorting: merge sort, quick sort, divide and conquer,
recurrence relations, etc., median-finding, lower bounds
- Union-find (and amortized analysis)
- Heaps: Binomial heaps, Fibonacci heaps
- Ordered structures: 2-3 trees, red-black trees, splay
trees, treaps, cache-oblivious trees?, skip lists
- Data structures for external storage: DAM model, B+-trees,
LSM-trees, Fractal trees (aka LSM-trees + fractional cascading),
B^\epsilon trees, Sorting in external storage, k-way merge sort,
- String algorithms: substring searching, longest-common
substring, edit distance, longest repeated substring?
- Graph algorithms: DFS, BFS, connected components,
topological sort, minimum spanning tree, matching, max-flow/min-cut,
min-cost flow, dijkstra's algorithm, all-pairs shortest paths, CFL
- Complexity theory: P vs NP, NP-completeness, NP-complete
examples, reductions, approximation algorithms, co-NP, PSPACE, EXP,
- Other fascinating topics: number theory (primality
testing), FFT, error-correcting codes, network coding, compression,
expander graphs, polynomial identity testing, matrix multiplication
- Linear programming: simplex algorithm, duality, primal
dual method, polynomial-time algorithms, integer-linear programming,
There is no required course textbook. I will be using the following
resources to prepare the class, so they should be good references for
Requirements and Grading
Subject to tweaks throughout the semester.
- Homeworks (40%). I will assign 4-8 homeworks throughout
the semester. I will drop the lowest grade from among your homework
scores. No late assignments will be accepted.
- Class participation (10%). I strongly encourage
discussion and debate in class. Please don't hesitate to ask
questions if you don't understand or disagree with anything
covered in this course.
- Midterm exam (25%).
- Final exam (25%). The final is cumulative, so it will
have questions covering topics from the entire semester.
Note: the schedule may change throughout the semester.
||No class: Rob sick
||Introduction, probability, balls and bins
||Final exam (5:30pm-8:00pm)
Americans with Disabilities Act:
If you have a physical, psychological, medical or learning disability
that may impact your course work, please contact Disability Support
Services, ECC (Educational Communications Center) Building, room128,
(631) 632-6748. They will determine with you what accommodations, if
any, are necessary and appropriate. All information and documentation
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. Faculty are required to
report any suspected instances of academic dishonesty to the Academic
Judiciary. Faculty in the Health Sciences Center (School of Health
Technology & Management, Nursing, Social Welfare, Dental Medicine) and
School of Medicine are required to follow their school-specific
procedures. For more comprehensive information on academic integrity,
including categories of academic dishonesty, please refer to the
academic judiciary website at
Critical Incident Management:
Stony Brook University expects students to respect the rights,
privileges, and property of other people. Faculty are required to
report to the Office of Judicial Affairs any disruptive behavior that
interrupts their ability to teach, compromises the safety of the
learning environment, or inhibits students' ability to learn. Faculty
in the HSC Schools and the School of Medicine are required to follow
their school-specific procedures.