CSE 548/AMS 542 Analysis of Algorithms

Fall 2017

Course Description Grading Schedule Instructor/TA Texts Lecture Notes Special needs

Course Description

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.

Required Text:

Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms, McGraw-Hill, 2006.

Online references:

We will refer to these books and materials from time to time. They all represent excellent resources that I would recommend to every one, even if they weren't free.

Additional texts:

These are alternative texts. We won't use them in class, but they are excellent books that contain more detailed discussions than your textbook.

Lecture Notes:

Below are lecture notes and videos of a subset of lectures made the previous time I offered this course. These will be updated as we go through the semester. I expect the revisions to trim down some of the topics, so that we will have more time to discuss problem sets.

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)
  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]
2 Divide and
conquer
(8/29 to 9/19)
  4-up, 1-up 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)
  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.
4 Greedy
algorithms
(9/26 to 10/3)
  4-up, 1-up Sections 5.1 and 5.2
Section 4.4
 
Mid-term I        
5 Dynamic
programming
(10/5 to 10/19)
Matrix chain muliplication: 12 mins
Shortest path: 26 mins
4-up, 1-up Chapter 6
Section 4.6
 
6 Linear
programming
(10/24)
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]
7 Advanced graph
algorithms
(10/24)
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]
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
4-up, 1-up Lecture notes. Algorithms on Strings, Trees and Sequences,
Dan Gusfield
Mid-term 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
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]
10 Amortized
analysis
(11/28)
Disjoint sets: 6 mins, 66 mins 4-up, 1-up Lecture notes,
Ch 15 of [Erickson],
Sec 5.1.4.
Amortized analysis: Ch 15 [Erickson]
11 NP-complete
problems
(11/30)
12 mins, 36 mins, 34 mins, 19 mins 4-up, 1-up Chapter 8  
12 Coping with NP-
completeness
(12/5, 12/7)
52 mins, 31 mins, 43 mins 4-up, 1-up Chapter 9,
excluding 9.3
 

Grading

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 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.


Instructor:

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


Schedule:

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.


Special Needs

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.