Course Description  Grading  Schedule  Instructor/TA  Texts  Lecture Notes  Special needs 
This course has two sections. This is the web page for the PhD section. The PhD course will provide an indepth introduction to a broad range of topics in algorithms, including more recent topics such as randomized and approximation algorithms. We will also learn how these algorithms have been built into software that we use frequently, such as diff, sort, compress, gzip, rsync, grep, agrep, spell, and so on. The full list of topics is:
Note that for the second half of the material, video lectures are available (see the links under "Lecture Notes"). Instead of repeating these lectures in the class room, I will expect you to review the lectures before the class, so that we can focus the class room lecture on discussing problem sets and answering questions.
Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms, McGrawHill, 2006.
It would be helpful to print the slides in advance and bring them to the class. This way, you can take notes on top of the slides, so that you can recall some of the important points made (or explained) in the lecture.
Videos are available for some of the lectures. If I get volunteers to tape the remaining lectures, I will post them all. In addition, for topics that are already covered in videos, we will prioritize the class time to answer questions and to work out problems, instead of having to repeat every thing that is already in these videos.
Note that we will cover a good deal of material outside the textbook. The slides will serve as the primary reference for this material, but in most cases, I have included external references on these topics. You need to know every thing in the slides, plus the textbook chapters/sections referenced below. In addition, a few of the "other" references will be italicized, which indicates that I recommend every student to review that material.
Ch.  Topic  Video  Slides (PDF)  Textbook References  Other References 
1  Introduction (8/29) 
4up, 1up  Chapter 0  Stable matching from Sec 1.1 [KT] Alternative source: Sec 0.5 [Erickson] Math foundation topics from [LLM] and [Erickson] 

2  Divide and conquer (8/29 to 9/19) 
4up, 1up  Chapter 2 Section 4.5 
Closest pair from Sec 5.4 [KT] Quicksort, Quick Select: Sec 1.5 [Erickson] Radix and Bucketsort, Sec 8.3, 8.4 [CLRS] 

3  Basic graph algorithms (9/21, 9/26) 
4up, 1up  Chapter 3 Sections 4.1 to 4.3 
Basic Graphs: Ch 18 [Erickson] A good reference for representing, manipulating graphs and using them for modeling problems. 

4  Greedy algorithms (9/26 to 10/3) 
4up, 1up  Sections 5.1 and 5.2 Section 4.4 

Midterm I  
5  Dynamic programming (10/5 to 10/19) 
Matrix chain muliplication: 12 mins Shortest path: 26 mins 
4up, 1up  Chapter 6 Section 4.6 

6  Linear programming (10/24) 
36 mins, 16 mins  4up, 1up  Sections 7.1, 7.4, 7.6 before 7.6.2 
Sec 27.1 and 27.2, [Erickson] 
7  Advanced graph algorithms (10/24) 
Max flow: 47 mins 6 mins Bipartite matching: 11 mins 
4up, 1up  Sections 7.2, 7.3  Maxflow Applications: Ch 24 [Erickson] More applications: Ch 25 [Erickson] Maxflow algorithms: Ch 23 [Erickson] 
8  String algorithms (10/26 to 11/7) 
Intro: 3 mins 11 mins 8 mins 4 mins 7 mins 6 mins Exact search: 39 mins Parallel search: 35 mins Fingerpriting: 45 mins 
4up, 1up  Lecture notes.  Algorithms on Strings, Trees and Sequences, Dan Gusfield 
Midterm II  
9  Randomized algorithms (11/9 to 11/21) 
Introduction: 60 mins 14 mins Hashing: 72 mins 10 mins Bloom filters: 20 mins String matching: 7 mins Primality testing: 21 mins 
4up, 1up  Some topics: Sections 1.3, 1.5 
Randomized mincut: Ch 14 [Erickson] Hashing: Ch 12 [Erickson] RabinKarp: Sec 13.1 to 13.3 [Erickson] Medium access protocol: Sec 13.1 [KT] Randomized closest pair: Sec 13.7 [KT] 
10  Amortized analysis (11/28) 
Disjoint sets: 6 mins, 66 mins  4up, 1up  Lecture notes, Ch 15 of [Erickson], Sec 5.1.4. 
Amortized analysis: Ch 15 [Erickson] 
11  NPcomplete problems (11/30) 
12 mins, 36 mins, 34 mins, 19 mins  4up, 1up  Chapter 8  
12  Coping with NP completeness (12/5, 12/7) 
52 mins, 31 mins, 43 mins  4up, 1up  Chapter 9, excluding 9.3 
Grading will be based on exams (68%) and homeworks and homework quizzes (27%), and class participation (5%). There will be two midterms, each counting for 15% to 20%, and a final, accounting for 35% to 40% of your final grade. I would like to schedule the midterms outside the lecture hours so that you can have more time to finish the exams, and so that we won't lose class time for discussions.
Homework problem sets will be handed out most weeks, but submissions will be only on alternate weeks. Homeworks will include some programming problems from time to time, but these are intended to pique your interest rather than completed programs that need to be submitted for grading. When you program, make sure you understand the complexity of basic data structures you use. (For instance, if you use Python, make sure that use real arrays if you need constant time access, not lists that provide an indexing operation but takes time linear in the size of the list.)
Homeworks can be completed in groups of three. It is strongly recommended that every student try to work out the problems on their own before discussing with their partners. Only a single copy of homework is submitted per group. Homework quizzes will be based on homeworks. They may be given every two weeks or so. They are intended to be lowstress events, where you will solve a few problems that are very similar to homework problems handed out in the preceding two weeks. Each quiz will take between 20 to 30 minutes.
Homeworks are due by 11:59pm on the specified date. However, we do not intend to penalize students for delays lasting up to 3 hours. Work submitted more than 3 hours late will likely receive a zero credit. However, every student is permitted to skip one assignment in a semester in order to accommodate unforeseen circumstances. Use this "pass" wisely, because you can get only one such pass.
Any form of copying in the course, and all forms of academic dishonesty, are considered serious offenses, and will be prosecuted to the maximum extent permitted by university policies. The minimum penalty for any form of copying, whether from your friends, the Internet or outside sources, or from previous offerings of the course, will be an Fgrade. Note that it is a "one strike and you are out" policy, i.e., you end up with an Fgrade regardless of how well you have done in the course until then. There will be no exceptions.
R. Sekar
Office: 364 New Computer Science
Office Hours: Tue/Thu 1:45pm to 2:15pm and 3:50pm to 4:30pm
TAs:
Santiago Vargas (savargas at cs.stonybrook.edu)
Office Hours: MW 3pm to 4pm in Old CS 2217
Lecture time/location: Tue/Thu at 2:30pm to 3:50pm, Earth and Space 069.
First lecture: August 29, Tuesday
Last lecture: December 7, Thursday
Approximate Dates for Exams:
Midterm I: around 10/10
Midterm II: around 11/14
Final Exam: December 18, Monday, 11:15am to 1:45pm, location TBD.
If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, I would urge that you contact the staff in the Disabled Student Services office (DSS), in the ECC building, 6326748v/TDD. DSS will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation of disability is confidential.