|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 in-depth 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, McGraw-Hill, 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.
|4-up, 1-up||Chapter 0||Stable matching from Sec 1.1 [KT]
Alternative source: Sec 0.5 [Erickson]
Math foundation topics from [LLM] and [Erickson]
(8/29 to 9/19)
|4-up, 1-up||Chapter 2
|Closest pair from Sec 5.4 [KT]
Quicksort, Quick Select: Sec 1.5 [Erickson]
Radix and Bucketsort, Sec 8.3, 8.4 [CLRS]
|4-up, 1-up||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.
(9/26 to 10/3)
|4-up, 1-up||Sections 5.1 and 5.2
(10/5 to 10/17)
|Matrix chain muliplication: 12 mins
Shortest path: 26 mins
|4-up, 1-up||Chapter 6
|36 mins, 16 mins||4-up, 1-up||Sections 7.1, 7.4,
7.6 before 7.6.2
|Sec 27.1 and 27.2, [Erickson]|
| Max flow: 47 mins 6 mins
Bipartite matching: 11 mins
|4-up, 1-up||Sections 7.2, 7.3||Max-flow Applications: Ch 24 [Erickson]
More applications: Ch 25 [Erickson]
Max-flow algorithms: Ch 23 [Erickson]
(10/24 to 11/7)
| Introduction: 60 mins 14 mins
Hashing: 72 mins 10 mins
Bloom filters: 20 mins
String matching: 7 mins
Primality testing: 21 mins
|4-up, 1-up||Some topics:
Sections 1.3, 1.5
|Randomized min-cut: Ch 14 [Erickson]
Hashing: Ch 12 [Erickson]
Rabin-Karp: Sec 13.1 to 13.3 [Erickson]
Medium access protocol: Sec 13.1 [KT]
Randomized closest pair: Sec 13.7 [KT]
(11/7 to 11/9)
|Disjoint sets: 6 mins, 66 mins||4-up, 1-up||Lecture notes,
Ch 15 of [Erickson],
|Amortized analysis: Ch 15 [Erickson]|
(11/14 to 11/21)
| Intro: 3 mins 11 mins 8 mins 4 mins 7 mins 6 mins
Exact search: 39 mins
Parallel search: 35 mins
Fingerpriting: 45 mins
|4-up, 1-up||Lecture notes.||Algorithms on Strings, Trees and Sequences,
(11/28 to 11/30)
|12 mins, 36 mins, 34 mins, 19 mins||4-up, 1-up||Chapter 8|
|12||Coping with NP-
(12/5 to 12/7)
|52 mins, 31 mins, 43 mins||4-up, 1-up||Chapter 9,
Grading will be based on exams (74%) and homeworks and homework quizzes (26%). There will be two midterms, each counting for 19%, and a final, accounting for 36% of your final grade. I expect there to be 4 to 5 submitted homeworks, together adding up to 16% to 18%. I expect 3 to 5 quizzes, adding up to 8% to 10%.
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 low-stress 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 F-grade. Note that it is a "one strike and you are out" policy, i.e., you end up with an F-grade regardless of how well you have done in the course until then. There will be no exceptions.
Office: 364 New Computer Science
Office Hours: Tue/Thu 1:45pm to 2:15pm and 3:50pm to 4:30pm
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:
Mid-term I: around 10/10
Mid-term 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, 632-6748v/TDD. DSS will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation of disability is confidential.