Computer Science 4020 (Spring 2021)

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

**Instructor: Elliot Anshelevich,**
WebEx meeting room,

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

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

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

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