CSE 548/AMS 542 Spring 2016. Algorithms
Lecturer: 
Rob Johnson 
TAs: 
TBD 
Location: 
E4330 Melville 
Time: 
TuTh 11:30am12:50pm 
Rob's Office Hours: 
Tu 4:00pm5:30pm, Th 1:00pm2:00pm, 368 Computer Science Building 
Tim Barron's Office Hours: 
We 45pm 2217 OLD Computer Science Building 

Sarthak Ghosh's Office Hours: 
Mo 12:152:15pm, 2217 OLD Computer Science Building 
Ziqiao Guan's Office Hours: 
We 35pm, 2217 OLD Computer Science Building 
Yuren Huang's Office Hours: 
Th 2:303:30pm, 2217 OLD Computer Science Building 

Chai Zhi's Office Hours: 
We 2:303:30pm, 2217 OLD Computer Science Building 

News
 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).
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:
 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, 2universal hashing, the power of 2 choices, cuckoo
hashing, bloom filters, quotient filters
 Sorting: merge sort, quick sort, divide and conquer,
recurrence relations, etc., medianfinding, lower bounds
 Unionfind (and amortized analysis)
 Heaps: Binomial heaps, Fibonacci heaps
 Ordered structures: 23 trees, redblack trees, splay
trees, treaps, cacheoblivious trees?, skip lists
 Data structures for external storage: DAM model, B+trees,
LSMtrees, Fractal trees (aka LSMtrees + fractional cascading),
B^\epsilon trees, Sorting in external storage, kway merge sort,
distribution sort?
 String algorithms: substring searching, longestcommon
substring, edit distance, longest repeated substring?
 Graph algorithms: DFS, BFS, connected components,
topological sort, minimum spanning tree, matching, maxflow/mincut,
mincost flow, dijkstra's algorithm, allpairs shortest paths, CFL
reachability
 Complexity theory: P vs NP, NPcompleteness, NPcomplete
examples, reductions, approximation algorithms, coNP, PSPACE, EXP,
P#, etc.
 Other fascinating topics: number theory (primality
testing), FFT, errorcorrecting codes, network coding, compression,
expander graphs, polynomial identity testing, matrix multiplication
 Linear programming: simplex algorithm, duality, primal
dual method, polynomialtime algorithms, integerlinear programming,
convex programming
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:
Requirements and Grading
Subject to tweaks throughout the semester.
 Homeworks (40%). I will assign 48 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.
Schedule
Note: the schedule may change throughout the semester.
Date 
Topic 
Reading assignment 
Notes 


No class: Rob sick 
None 
None 

Introduction, probability, balls and bins 
None 
None 
5/11 
Final exam (5:30pm8: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) 6326748. They will determine with you what accommodations, if
any, are necessary and appropriate. All information and documentation
is confidential.
Academic Integrity:
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 schoolspecific
procedures. 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/
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 schoolspecific procedures.