Computer Science 4020/6210 (Spring 2016)

**Time and Place:** Tuesdays and Fridays,
2:00pm-3:50pm, Amos Eaton 214

**Instructor: Elliot Anshelevich**

311 Lally Hall, 518-276-6491

Haidar Khan, khanh2@rpi.edu

John Postl, postlj@rpi.edu

Haidar Khan: Amos Eaton 217; Wednesday 12pm-2pm

John Postl: Amos Eaton 119; Thursday 11am-1pm

Elliot Anshelevich: Lally 311; Monday and Thursday 3pm-4pm (or by appointment)

**Announcements and Handouts:**

5/20/16 - The final exams have been graded; the median was 62/80 and the mean 60/80. The exams can be picked up outside my office until 5pm on Saturday. The final semester grades should be available through SIS sometime on Sunday.

5/09/16 - According to the Office of the Registrar, the final exam will take place on Thursday, May 19, 3pm-6pm, in SAGE 3510. 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 10th to schedule a make-up exam.

5/06/16 - All homeworks are now graded. Graded homeworks and solutions can be picked up at my office. See also the grading comments for Problem Set 9.

4/22/16 - Problem Set 9 is due Tuesday, May 3, at the beginning of class. Notice that this homework is due on a Tuesday.

4/15/16 - Problem Set 8 is due Friday, Apr 22, at the beginning of class.

4/11/16 - John's office hours on Thursday, April 14, are canceled.

4/04/16 - Elliot's office hours on Monday, April 4, are canceled.

4/01/16 - Problem Set 7 is due Friday, Apr 15, at the beginning of class. Notice that you have two weeks to do this assignment.

3/25/16 - Problem Set 6 is due Friday, Apr 1, at the beginning of class.

3/05/16 - Problem Set 5 is due Friday, Mar 25, at the beginning of class. Notice that you have three weeks to do this assignment, since the * Midterm Exam takes place in class on Mar 8,* followed by spring break.

2/26/16 - Problem Set 4 is due Friday, Mar 4, at the beginning of class.

2/19/16 - Problem Set 3 is due Friday, Feb 26, at the beginning of class.

2/12/16 - Problem Set 2 is due Friday, Feb 19, at the beginning of class.

2/11/16 - There will be no office hours on Monday, Feb 15, due to Presidents' Day.

2/02/16 - Problem Set 1 is due Friday, Feb 12, at the beginning of class.

2/02/16 - The quiz is graded and can be picked up in class or during office hours. See here for the grading comments.

1/01/16 - There will be a quiz in class on Jan 29; 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/16 - This is where various announcements will appear during the semester.

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

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

- Specifically, from CSCI 2300 this includes elementary data structures, binary search, sorting, big-O notation, and basic terminology involving graphs (including the concepts of depth-first search, breadth-first search, and connectivity). These topics are covered in chapters 2 and 3 of the textbook. Some topics in CSCI 4020 are similar to the ones covered in CSCI 2300: we will cover them much more in-depth, and consider much more complex applications of these algorithm design techniques than in CSCI 2300.
- The prerequisites for this course also include a background in discrete mathematics, including order of function growth, sets, recurrence relations, and proof techniques such as induction and contradiction. This also includes strong and structural induction. The lectures and homework involve the analysis of algorithms at a fairly mathematical level. We expect everyone to be comfortable reading and writing proofs, at the level of MATH 2800 or CSCI 2200.

Note: this course is usually restricted to CSCI majors. However, if you have an extensive math background, feel free to contact me and I will add you to the 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:

- Cormen/Leiserson/Rivest/Stein: Introduction to Algorithms.
- Aho/Hopcroft/Ullman: The Design and Analysis of Computer Algorithms.
- Dasgupta/Papadimitriou/Vazirani: Algorithms.
- Garey/Johnson: Computers and Intractability.
- Kozen: The Design and Analysis of Algorithms.

**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 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 March 8, 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 second 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.

*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

**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 is allowed during exams.