| Course Description | Grading | Schedule | Instructor/TA | Texts | Lecture Notes | Special needs |
Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms, McGraw-Hill, 2006.
Links to videos from previous offerings of the course are included for
some of the lectures. The topics we will cover in the class will be
somewhat different, so it is not a substitute for attending
lectures. The video links are provided in case you cannot recall the explanation
from the class lecture and need to go over the material again.
| Ch. | Topic | Video | Slides (PDF) | Textbook References | Notes and Additional References |
| 1 | Introduction (8/23) |
Chapter 0 | Follow links from the last slide of PDF | ||
| 2 | Divide and conquer (8/29 to 9/1) |
Chapter 2 Section 4.5 |
Quicksort, Quick Select: Sec 1.5 [Erickson] Radix and Bucketsort, Sec 8.3, 8.4 [CLRS] |
||
| 3 | Basic graph algorithms (9/6, 9/8) |
Chapter 3 Sections 4.1, 4.2 |
Ch 18 [Erickson] is a good reference for representing and manipulating graphs and using them for modeling problems. |
||
| 4 | Greedy algorithms (9/13 to 9/15) |
Sections 5.1 and 5.2 | |||
| 5 | Amortized analysis (9/15 to 9/20) |
Disjoint sets: 6 mins, 66 mins | Section 5.1.4 | Lecture slides covered in class: vectors and disjoint sets. Refer to [Erickson] Ch 15 for amortization overview, and Ch 17 for in-depth disjoint sets coverage. |
|
| 6 | Dynamic programming (9/20 to 10/4) |
Matrix chain muliplication: 12 mins Shortest path: 26 mins |
PDF | Chapter 6 Sections 4.3, 4.4, 4.6 |
|
| 7 | Randomized algorithms |
Hashing: 72 mins
10 mins Bloom filters: 20 mins String matching: 7 mins Primality testing: 21 mins |
Some topics: Sections 1.3, 1.5 |
Hashing: Ch 12 [Erickson] Rabin-Karp: Sec 13.1 to 13.3 [Erickson] Randomized closest pair: Sec 13.7 [KT] |
|
| 8 | NP-complete problems |
12 mins, 36 mins, 34 mins, 19 mins | Chapter 8 | ||
| 9 | Coping with NP- completeness |
52 mins, 31 mins, 43 mins | Chapter 9, excluding 9.3 |
||
| 10 | String algorithms |
Intro: 3 mins 11 mins 8 mins 4 mins 7 mins 6 mins Exact search: 39 mins Fingerpriting: 45 mins |
Lecture notes. |
Your final grade will be based on exams (65% to 75%) and homeworks/homework quizzes (25% to 35%). There will be one or two midterms and a comprehensive final exam.
A new homework problem set will be handed out approximately every two weeks. Homeworks can be completed in groups of three. It is strongly recommended that students try to work out the problems on their own before discussing with their partners. Only a single copy of the homework should be submitted per group.
In an effort to reduce the temptation to cheat, homework scores will be multiplied by 4/3. This means that you can get full credit by answering just 75% of the problems correctly. Note that you cannot get more than 100% on a homework, so you might as well omit problems you cannot solve, rather than trying to look them up on the internet, and risk failing the course if you are caught. (If we determine that a particular homework is harder than usual, we may further increase this multiplication factor.)
Note that scaling will be applied only to those problems where you clearly acknowledge the errors or incompleteness of your solution. It will not apply in either of the followig cases: (a) you attempt to cover up the errors or incompleteness in your solution, or (b) your solution is written up poorly, and is hard for us to understand. In those cases, you will likely receive a zero score. So, make sure that your solutions are understandable. Keep in mind that in coding interviews, if you cannot explain your solution and convince the interviewer, it won't matter that you have the right solution.
Homework quizzes will be based on homeworks. I expect every other homework to be followed by a homework quiz. You should be able to do well in these quizzes if you understood how to solve the homework problems. No additional preparation should be necessary. To reduce the pressure associated with these quizzes, we will scale these scores in the same way as homeworks. Each quiz will take 20--25 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 get only one such pass. If you submit all the homeworks, then we will effectively drop the homework in which in scored the lowest.
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.
R. Sekar
Office: 364 New Computer Science
Office Hours:
Tue: 3:00pm to 4:00pm in New CS 364
Tue/Thu: 7:50pm in Frey 102 (right after class)
TAs
Abiyaz Chowdhury (firstname.lastname at cs.stonybrook.edu)
Office Hours:
Mondays and Fridays 2pm to 3pm on Zoom
Wednesdays 2pm to 3pm at Old CS 2126
Day homeworks are due 5pm on Zoom
Balaji Jayasankar (bjayasankar at cs.stonybrook.edu)
Office Hours: Wednesday 5pm to 6pm
Location: Old CS 2126 or on Zoom
Lecture time/location: Tue/Thu at 6:30pm to 7:50pm, Frey Hall 102.
If you have special needs, concerns or a disability, please contact the staff at Student Accessibility Support Center (SASC). SASC staff will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation will remain confidential.