CSE 548/AMS 542 Analysis of Algorithms

Fall 2022

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

What's new this year


Course Topics


Text Book and References

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

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)
  PDF Chapter 0 Follow links from the last slide of PDF
2 Divide and
conquer
(8/29 to 9/1)
  PDF 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)
  PDF 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)
  PDF Sections 5.1 and 5.2  
5 Amortized
analysis
(9/15 to 9/20)
  Disjoint sets: 6 mins, 66 mins PDF 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
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
PDF 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 PDF Chapter 8  
9 Coping with NP-
completeness
52 mins, 31 mins, 43 mins PDF 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
PDF Lecture notes.  


Grading

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.


Instructor

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


Schedule

Lecture time/location: Tue/Thu at 6:30pm to 7:50pm, Frey Hall 102.

  • First lecture: August 23, Tuesday
  • Last lecture: December 1, Thursday
  • Final Exam: December 8, Thursday, 5:30pm to 8:00pm, Frey Hall 102.
  • No classes: October 11 (Fall Break), November 23 to 27 (Thanksgiving Break)

    Special Needs

    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.