Introduction to Algorithms (CSCI2300) Syllabus

CSCI 2300 - Introduction to Algorithms


Syllabus and Class Policies

1. 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. Students will learn a variety of algorithm design techniques, how to apply them to different problems, and how to choose which technique should be used for which problem.

Learning Outcomes

The goal of this course is to provide a strong foundation in algorithms in preparation for jobs in industry or for more advanced courses. Algorithms are the basic language of computer science. After taking this course, you, the student, should be able to:

  • Understand the correctness of, and analyze the running times of, different algorithms.
  • Use different algorithm-design techniques, including, but not limited to, greedy, divide-and-conquer, and dynamic programming techniques, to solve particular problems.
  • Model real problems abstractly using the language of graphs and flows.
  • Solve problems by reducing to other problems whose solution is known, and show that problems are hard by reducing from other problems.
  • Make intelligent decisions about alternative data structures and algorithmic techniques in the context of practical problems, choosing from existing data structures and algorithms or designing your own when necessary.

Textbook

The required course textbook is Algorithms by Dasgupta, Papadimitriou, and Vazirani. See also the textbook errata.

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.
  • Kleinberg/Tardos: Algorithm Design. (See also slides by Kevin Wayne.)

Pre-requisites

The pre-requisites for this course are CSCI 1200 and 2200. We will assume that everyone has seen the material in these courses, and will use it as necessary.

This is not a programming class. Some of the homeworks involve programming, but you are expected to be a competent programmer coming in -- the lectures will not discuss any code. The TAs and undergraduate programming mentors can provide some help on programming issues in office hours, but you should be able to answer your own programming and debugging questions. The textbooks do not deal with programming issues almost at all. You may want to consult your textbooks from previous courses.

2. General Class Policies

Website and Announcements. We will make extensive use of electronic communication and the course website. You are responsible for checking Submitty/LMS regularly for announcements and course materials, as well as your e-mail for communications related to the class.

Lectures. Lectures will be presented live on WebEx, with recordings of those lectures made available soon after. Students are highly encouraged to attend all lectures live, but can also view the recorded versions if needed. You are responsible for all material covered and announcements made in lecture. Note that if you ask questions during lecture, those questions would also appear in the recording which will be made available; by taking this class you agree to this. Please do not post the lecture recordings anywhere, or share them with others who are not taking this class.

Exams. There will be two midterm exams (see the class Schedule for the exact dates and times), 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. The exams will be administered remotely: they will be made available on Submitty/LMS at their start time. We will not provide make-up exams except for official excused absences (see also here if you are off-campus). Any students with special circumstances must notify me during the first two weeks of class.

Grading. We will give an approximate grade breakdown in the middle of the semester, but you are responsible for keeping track of your own grades by asking the TA during lab or by checking Submitty/LMS. If there is any error with your recorded grades, you must notify the instructor within one week of the grade being recorded on LMS.

Final Grades: The final class grades will be assigned as follows.

To compute your ExamAverage, count each of the Midterm Exams as 30 percent, and the Final Exam as 40 percent. No extra credit will apply to exams.

To compute your AssignmentAverage, count the Homeworks as 90 percent, and Office Hour attendance as 10 percent. The 2 lowest homework grades and office hour attendance grades will be dropped. Then add 1 percent extra credit from each of the recitation surveys that was filled out by over 100 students.

Your FinalScore equals the minimum of your ExamAverage and your AssignmentAverage.

Your FinalScore corresponds (approximately) to the following letter grades: A/A-: 85+; B+/B/B-: 75+; C+/C/C-: 65+; D+/D: 60+.

In other words, to pass the class you must do well on both the exams and the assignments. Exams and assignments will not be curved, but the final semester grades may be curved (only to improve your grades).

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

COVID-19 Issues: The course is online for the entire semester. Students should follow all guidelines from RPI related to health and safety for themselves and other campus members. All illness related accommodations will require officially approved excuse from RPI.

Students who are ill, under quarantine for COVID-19, or suspect they are ill will report that to Student Life. Student Life will verify and notify all faculty who have that student. Once notification is made, all faculty will make every reasonable effort to accommodate the student’s absence and will communicate that accommodation directly to the student. Failure to make an appropriate accommodation for a verified or reasonably suspected case of illness may be appealable under the student grade appeal process. Students who need to report an illness should contact the Student Health Center via email or call 518-276-6287. For student seen off campus, a student may request an excused absence via http://www.bit.ly/rpiabsence with an uploaded doctor's note that excuses them.

Policy on Academic Integrity: Student-teacher relationships are based on trust. For example, students must trust that teachers have made appropriate decisions about the structure and content of the courses they teach, and teachers must trust that the assignments that students turn in are their own. Acts which violate this trust undermine the educational process. The Rensselaer Handbook of Student Rights and Responsibilities defines various forms of Academic Dishonesty and you should make yourself familiar with these.

  • Homework Collaboration: In this class, 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 completely separately. When working on programming assignments, you may discuss general approaches to the problem, but you may not look at anyone else's code or show your code to them: all the actual programming must be done entirely on your own. Failure to write the solution to a homework completely on your own will be considered a breach of academic integrity. You may not copy (or near-copy) a solution from another, or use resources other than the class notes or the class textbook. Use of materials other than the class textbooks to formulate your solutions, including any material found on the Internet or material from previous versions of this course, is a clear breach of academic integrity and will be punished severely.
  • OK to do: To give more concrete examples, it is OK to discuss and work on problems together with other students in the class. It is OK to bring your homework to the TA and ask them if it is correct or if this approach makes sense. It is OK to say "this is just like page ... from the textbook, but with the following changes", or "the solution is the same as the previous problem, but with the following changes". After solving a problem together with other students, or with help from TAs, it is OK to write up the solution formally by yourself, possibly consulting some small amount of notes you made while meeting with other students or the TA. If you use any source other than the course staff, other students in this course, course textbook, or lectures, to come up with solutions, then you must acknowledge your use of this source accordingly at the time of submission. If you cite your sources, you will not be committing a breach of academic integrity, although since you are being graded on your own understanding of the material and not work done by others, your grade may be adjusted accordingly.
  • NOT OK to do: violations of academic integrity include, but are not limited to the following. Searching the Internet for solutions to homework problems before submitting them, even to "check" your answers. Asking for help with solutions from people who are not enrolled in the same class. Using existing solutions instead of solving the problems yourself (possibly together with other students). Copying a solution from the textbook or handouts and presenting it as your own: it is fine to use solutions from the class textbook or lecture, but you must cite your work by saying where this solution comes from! Sharing typed or finished solutions from other students: everyone should write their solutions independently, and no one should be showing each other detailed solutions or code!
  • Exams: You may not collaborate, discuss, or provide your exam solutions to anyone, except the course instructor and TAs. This includes after the exam is over. While you are allowed to use the class textbook and notes and handouts during exams, using any other resources to formulate solutions during the exam, including any material found on the Internet or material from previous versions of this course, is a clear breach of academic integrity and will be punished severely.

Violating the above policy will result in the final grade being reduced by a letter and a 0-grade for the assignment for both parties, as well as reporting this breach of academic integrity to the appropriate authorities at RPI. Depending on the circumstances, harsher penalties may be used, including a failing grade for the class.

3. Homework Guide

Homework Submission, Late Homeworks:

Homework should be submitted as a printable pdf file on Submitty: https://submitty.cs.rpi.edu/courses/s21/csci2300sec5to8. As with all assignments submitted on submitty, it is the student's responsibility to verify that the correct files successfully uploaded, and that the files can be read by the graders. The homework should be typed, although you can include hand-drawn formulas or figures. I highly suggest learning and using LaTeX to format your homework. For some resources, I recommend a LaTeX tutorial; for actual writing I suggest either installing MiKTeX or using an online editor like Overleaf. LaTeX abilities will be useful for you far beyond this course, so it is well worth learning.

Each student will be given a budget of five (5) late days that they can use to turn in homeworks late. A single late day can be used to turn in the homework on the next day, for example on Friday instead of on Thursday. Any part of a late day that you use counts as a full late day. For example, if you submit your homework an hour late, that counts as a full late day, so you might as well wait and submit it on the day of the following lecture. You cannot use more than one late day for the same homework, or use a late day after already turning something in.

Use your late days wisely, if at all. This late-day policy is intended to cover unanticipated things like minor sickness, exams in other classes, etc., so that you do not have to ask for extensions. Once you have used up your budget of late days you will not be allowed to turn in homeworks late for any reason without an official Excused Absence Letter from RPI (see also here if you are off-campus).

Writing Proofs and Algorithms:

  • The best way to explain an algorithm is usually in English, with some mathematical notation. Some pseudo-code together with a short English explanation is also fine. Solutions that simply give a long piece of pseudo-code without an explanation, however, tend to contain mistakes, and be very hard to understand. We reserve the right to deduct points for such solutions, even if they turn out to be correct.
  • You should write up both your algorithms and your proofs clearly and neatly, as this will make your solution easier to understand, and will earn you more partial credit. We will take off points if we do not understand what you are trying to say. Because of this, it is in your best interest to explain everything clearly and concisely.
  • You are allowed to use any algorithm that is described in class or in the textbook in your solutions, without having to re-formulate it from scratch (in other words, you can just cite the textbook in your solution). The same holds for any results proven in class or in the textbook.

Working Together:

You are allowed (and encouraged) to discuss homework problems with other members of the class, and to formulate ideas together. There is no penalty for working in groups. However, everyone must write up their assignments separately: do not show each other completed or typed solutions. Make sure that you spend a lot of time thinking about the problems yourself and writing up the solutions; students who only follow their collaborators' lead will find the exams much more difficult.

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. It should go without saying that collaborating with people not taking this class, or using any resource other than the class textbook or notes, is a serious breach of academic integrity and will be punished severely.

Grading:

  • The lowest two (2) homework grades will be dropped.
  • 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. The entire assignment will be re-graded, and your grade may go up or down. The second grade will remain. Furthermore, we generally will not accept regrade requests that dispute the amount of partial credit awarded; we are only interested in instances where an actual mistake in grading has been made. Do not be surprised if your regrade takes a long time, as we will only process them periodically.

4. Recitation and Office Hour Guide

Recitations: In addition to the lectures, a recitation video will be made available online during most weeks. These videos are intended to provide you with support for honing your problem solving skills, as well as helping out with homeworks. You are required to view the recitation video, as well as the lecture videos. We recommend watching this video before starting on the homework.

Office Hours: Attending your assigned office hours on Wednesday is required and is part of your final grade as described in the grading policies. You can miss two office hour weeks without penalty. Please make sure the TA or mentor writes your name down before you leave, so you get credit for attending. Office hours led by TAs and mentors will take place every Wednesday: these office hours are your main opportunity for getting individual attention, asking questions about lectures and recitations, getting help on the homework, etc. They are also a good time to work together with other students in the class. We suggest planning to spend your entire assigned two hours at office hours, asking questions and working on the homework which is due that week. (Of course, please feel free to ask the TAs for advice on your homework: this is why they are there!) We will not be answering questions about the homework on the day that it is due (usually Thursday). Because of this, you are required to start the homework and view the recitation video before Wednesday, so that you have the opportunity to get help if you need it.

Recitation Grading (Extra credit): You are required to start the homework and view the recitation video before Wednesday, so that you have the opportunity to get help if you need it. Because of this, you must acknowledge that you have done so on Tuesday by logging into LMS and completing the recitation survey. This survey is anonymous; if enough students fill out the survey everyone will receive extra credit, as described in the grading policies.