Computer Algorithms

Computer Science 4020/6210 (Spring 2018)

Time and Place: Tuesdays and Fridays, 12:00pm-1:50pm, Sage 3303

Instructor: Elliot Anshelevich
311 Lally Hall, 518-276-6491
first letter of first name + first 6 letters of last name AT cs dot rpi dot edu

Teaching Assistants:
Wennan Zhu,
Ben Abramowitz,
Office Hours: (subject to change)
Ben Abramowitz: Sage 2704; Wednesday 12pm-1:50pm
Wennan Zhu: Amos Eaton 127; Thursday 1pm-2:50pm
Elliot Anshelevich: Lally 311; Thursday 3pm-4:50pm (or by appointment)

Announcements and Handouts:
5/09/18 - The final exam grades will be posted on LMS sometime on Friday. The graded exams can be viewed in Elliot's office 2pm-4pm on Friday.
4/27/18 - According to the Office of the Registrar, the final exam will take place on Wednesday, May 9, 3pm-6pm, in Sage 3303. Check with the Registrar, as this is subject to change. If you have a serious conflict during the time of the Final Exam, you must email me before Tuesday, May 1st to schedule a make-up exam.
4/13/18 - Problem Set 8 is due Tuesday, Apr 24, at the beginning of class. Notice that this homework is due on a Tuesday.
4/06/18 - Due to the CS colloquium, Elliot's office hours on Thursday Apr 12 will take place at 2pm-3:50pm (not at 3pm-4:50pm).
4/06/18 - Problem Set 7 is due Friday, Apr 13, at the beginning of class.
3/23/18 - Problem Set 6 is due Friday, Apr 6, at the beginning of class. Notice that you have two weeks to do this assignment.
3/09/18 - Problem Set 5 is due Friday, Mar 23, at the beginning of class.
2/22/18 - Elliot will hold extra office hours on Monday, Feb 26, at 3pm-5pm.
2/16/18 - Problem Set 4 is due Friday, Feb 23, at the beginning of class.
2/16/18 - Problem Set 2 is graded and can be picked up in class or during office hours. See here for the grading comments.
2/09/18 - Problem Set 3 is due Friday, Feb 16, at the beginning of class.
2/02/18 - Ben's office hours on Wednesday, February 7, are canceled.
2/02/18 - Problem Set 2 is due Friday, Feb 9, at the beginning of class.
1/26/18 - Problem Set 1 is due Friday, Feb 2, at the beginning of class. It should be submitted both on LMS and as a physical copy.
1/01/18 - There will be a quiz in class on Jan 19; it will take about 1 hour. This quiz will test the prerequisites for this class. To study for it, see the handout on Discrete Math, as well as Chapters 2 and 3 from the textbook.
1/01/18 - This is where various announcements will appear during the semester.

Class Schedule

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. For more details, see the Syllabus.


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. There will also be a quiz during the first week of class that will test your knowledge of the pre-requisite material for this class.


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.

Homework. Homework will be assigned every 1-2 weeks, and can be done in pairs. There will not be any programming assignments. Homework should submitted on LMS, and also be handed in at the beginning of lecture on the day it is due. For more information about homework, see the 4020 Homework Guide.
You are required to prove your statements, unless otherwise specified. If a homework or exam question asks you to design an algorithm for a certain task, then the answer must consist of a description of the algorithm (an English description is fine), as well as an analysis of its running time and a proof of its correctness.

Exams. There will be a midterm exam in class on February 27, and a comprehensive final exam during finals week. There will also be an in-class quiz during the first week of class testing knowledge that is pre-requisite for this class. All exams are open-textbook and open-notes. Make-up tests or homework assignments will not be given except in case of an emergency. Students who know they are going to miss a test must notify me in advance. Special circumstances can be accommodated if I am notified about them in advance.

Grading. The midterm will count for 30% of your final grade, the final for 35%, and the homework for 30%. The quiz during the first week of class will count for the remaining 5%. 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. 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 students taking CSCI 6210 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 to the above cutoffs, to pass the class, a student must earn an average grade of at least 50 percent on the exams. Similarly, to receive a grade of A-, B-, C- or above, a student must earn an average grade of at least 85, 75, and 60 percent respectively on the exams. The exam average is calculated as [.3*(Midterm)+.35*(Final)+.05*(Quiz)]*(100/70).

Additional Requirements for CSCI 6210. Some of the homeworks will include additional problems specifically for 6210. Moreover, all students registered for CS 6210 must in addition complete a report on a published research paper of their choice related to algorithm design. The student must read this paper, and write a report (1) summarizing the topic of this paper and its major contributions, and (2) the algorithms involved and how these algorithms address the problems in the paper. This report is due on the last day of class; any student registered for CS 6210 who does not submit such a report will automatically receive a failing grade for the semester.

Policy on Academic Integrity: You are allowed (and encouraged) to discuss homework problems with other members of the class, and to formulate ideas together. However, everyone must write up their assignments separately, and include the names of everyone you discussed the assignment with. You may not copy (or near-copy) a solution from another, or use resources other than the class notes or the class textbook. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity, and may result in the final grade being reduced by a letter and a 0-grade for the homework for both parties. No collaboration and nothing electronic is allowed during exams.
See the Rensselaer Handbook of Student Rights and Responsibilities for more. The Rensselaer Graduate Student Supplement also defines various forms of Academic Dishonesty and procedures for responding to them. Students should make themselves familiar with this information.