Design and Analysis of Algorithms

Computer Science 4020 (Spring 2021)

Time and Place: Tuesdays and Fridays, 12:20pm-2:10pm, Location: Fully online

Instructor: Elliot Anshelevich, WebEx meeting room, first letter of first name + first 6 letters of last name AT cs dot rpi dot edu

Teaching Assistant: Ben Abramowitz, abramb@rpi.edu

Office Hours: (subject to change)
Ben Abramowitz: Wednesday 5pm-7pm (click here to speak with Ben online: you should be able to use your RPI email if you click on "Microsoft")
Elliot Anshelevich: Monday 3pm-4pm and Thursday 2pm-3pm (click here to speak with Elliot online)


Class Schedule


Syllabus and Class Policies


Course Overview

This course presents fundamental ideas and techniques of modern algorithm design and analysis. After completing this course, students should be able to analyze and design efficient algorithms for a variety of computational problems. They will also be able to communicate their ideas in the form of precise algorithm descriptions and rigorous proofs. For more details, see the Syllabus.

Pre-requisites

The official prerequisites for the course are CSCI 2300 and either MATH 2800 or CSCI 2200. We will assume that everyone has seen the material in these courses, and will use it as necessary.

If you did not take a corresponding course, you must contact me during the first week of classes. To refresh your knowledge of Discrete Mathematics please read the handout on Discrete Math, as well as Chapters 2 and 3 of the textbook, and try to solve all problems. If you cannot solve many of them, I strongly recommend that you take a course in Discrete Mathematics before taking this course.

Textbook

The course textbook is Algorithm Design by Jon Kleinberg and Eva Tardos.

Although the lectures will mostly be drawn from the textbook, we will still cover things that do not appear in the text, and the textbook includes material that we will not cover in class. You are responsible for the content of the lectures as well as any assigned readings. You may also find the following books useful for reference and for different perspectives:

Homework, Exams, and Grading

Students are encouraged to attend all classes. Your active in-class participation will be a substantial part of your learning process, and will be taken into consideration when final grades are determined. You are responsible for all material covered and announcements made in lecture.

Homework. Homework will be assigned every 1-2 weeks, and can be done in pairs. For homework policies, see the 4020 Homework Guide.

Exams. There will be a midterm exam in class (see the Class Schedule for date and time), and a comprehensive final exam during finals week. All exams are open-textbook and open-notes, but searching online, collaboration, or copying from others are not allowed and would be considered a breach of academic integrity. Make-up exams will not be given except in case of an emergency, accompanied by an official Excused Absence Letter from RPI (see also here if you are off-campus). Students who know they are going to miss an exam must notify us in advance. Special circumstances can be accommodated if we are notified about them in advance.

Grading. The midterm will count for 30% of your final grade, the final for 40%, and the homework for 30%. Please see the Syllabus for details. We will drop the lowest homework grade.
Regrades: Any request to re-evaluate a grade must be made within one week of the return date of the homework or exam in question. You must explain why you think your grade should be changed in writing, and submit your request to me or a TA, together with the original problem solution. The second grade will remain. Your entire assignment or exam will be regraded and your grade may go up or down, or it may stay the same. It is also your responsibility to monitor your grades on LMS; if there is any error you must bring it to my attention within one week of the grade being posted.
Final Grades: Final scores will correspond to the following letter grades: A/A-: 85-100; B+/B/B-: 75-85; C+/C/C-: 60-75; D+/D: 50-60. (Note that graduate students cannot receive grades of D+ or D, and so must receive at least a score of 60 to pass the class.)
Exam Cutoffs: In addition, your maximum final grade can be at most 5 points more than your weighted exam average. So, for example, if your weighted exam average is 73 percent, then the maximum grade that you would be able to receive in the class is 78.