Time and Place: Mondays and Thursdays, 2:00pm-3:50pm, DCC 236

Instructor: Elliot Anshelevich
311 Lally Hall, 518-276-6491

Announcements and Handouts:
05/07/08 - The final exams have been graded, and can be picked up outside my office. The final grades should now be available through the RPI online system.
04/24/08 - According to the Office of the Registrar, the final exam will take place on Monday, May 5th, 11:30am-2:30pm, in Sage 5510. Check with the Registrar, as this is subject to change. If you have a conflict during the time of the Final Exam, you must email me before this Monday to schedule a make-up exam.
04/14/08 - Because of the CS Colloquium, office hours this Wednesday will take place at 5pm instead of 4pm.
04/10/08 - Problem Set 10 is due Thursday, Apr 24th, at the beginning of class. Notice that you have 2 weeks to do this homework.
04/07/08 - This Wednesday (04/09/08) office hours will take place at 5pm instead of 4pm.
04/03/08 - Problem Set 9 is due Thursday, Apr 10th, at the beginning of class.
03/27/08 - Problem Set 8 is due Thursday, Apr 3rd, at the beginning of class.
03/21/08 - This Wednesday (03/26/08) office hours will take place at 5pm instead of 4pm, and there will be no office hours at 11am.
03/20/08 - Problem Set 7 is due Thursday, Mar 27th, at the beginning of class.
03/06/08 - Problem Set 6 is due Thursday, Mar 20th, at the beginning of class. Notice that you have two weeks to do this assignment because of Spring Break.
02/21/08 - Problem Set 5 is due Thursday, Mar 6th, at the beginning of class. Notice that you have two weeks to do this assignment, since the Midterm Exam takes place in class on Feb 28th.
02/18/08 - Because of the CS Colloquium, office hours this Wednesday will take place at 5pm instead of 4pm.
02/14/08 - Problem Set 4 is due Thursday, Feb 21st, at the beginning of class.
02/11/08 - The Final Exam is currently scheduled for Monday, May 5th, 11:30am - 2:30pm. This is still subject to change. If anyone has a conflict with this time, please contact me as soon as possible.
02/07/08 - Problem Set 3 is due Thursday, Feb 14th, at the beginning of class.
01/31/08 - Problem Set 2 is due Thursday, Feb 7th, at the beginning of class.
01/17/08 - Problem Set 1 is due in two weeks (Thursday, Jan 31st), at the beginning of class.
01/14/08 - Notice that the location for this class has been changed. It will take place in DCC 236.
01/07/08 - There will be a quiz in class on Jan 24th. It will test the prerequisites for this class. To study for it, see the handout on Discrete Math (ps version), as well as Chapters 2 and 3 from the textbook. The quiz problems will be similar to the problems in the handout.
01/01/08 - 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.

Pre-requisites

The official prerequisites for the course are CSCI 2300 and MATH 2800. We will assume that everyone has seen the material in 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.
• 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. 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.

Textbook

The course textbook is Algorithm Design by Jon Kleinberg and Éva Tardos. It is available at the campus store.

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. 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 February 28th, and a comprehensive final exam during finals week. There will also be an in-class quiz during the second 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. 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 20% of your final grade, the final for 25%, and the homework for 50%. The quiz during the second week of class will count for the remaining 5%.
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.
For PhD students: This course will give you an automatic pass for a qualifying exam in Computer Algorithms if your final grade is an A (an A- will not be sufficient).

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