CSCI-4020: Design and Analysis of Algorithms

Design and Analysis of Algorithms

Computer Science 4020 (Spring 2024)

Time and Place: Tuesdays and Fridays, 12:00pm-1:50pm, SAGE 5510

Instructor: Elliot Anshelevich, WebEx meeting room, eanshel@cs.rpi.edu

Teaching Assistant: Chris Jerrett, jerrec@rpi.edu

Office Hours: (subject to change)
Chris Jerrett: Amos Eaton 110: Wednesday 12pm-2pm
Elliot Anshelevich: Tuesdays 2pm-3pm in-person in Lally 311; Thursdays 3:30pm-4:30pm in WebEx meeting room

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.

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.

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:

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. 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 in the Syllabus.

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. A make-up exam for the midterm will occur exactly one week after the original exam; if a make-up exam cannot be taken at that time, then the final exam grade will take its place. 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. Note that all class policies and exam dates are subject to change if the course has to be offered remotely.

Grading. The midterm will count for 35% of your final grade, the final for 45%, and the homework for 20%. Please see the Syllabus for details. We will drop the lowest homework grade.
Regrades: Any request to re-evaluate a grade must be made at least 24 hours, and at most one week, after 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 on Gradescope. 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: 55-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 to the above cutoffs, to pass the class, a student must earn an average grade of at least 50 percent on the exams. The exam average is calculated as [.35*(Midterm)+.45*(Final)]*(100/80).