CSCI 2300:  Introduction to Algorithms – Fall 2023

Instructor: Dr. Stacy Patterson (sep@cs.rpi.edu)

Website: https://www.cs.rpi.edu/~pattes3/csci2200

Course Description:        

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.

Pre-requisites: 

The course prerequisites are CSCI 1200 and CSCI 2200.

This is not a coding class. Some of the homework involves coding, but the lectures will not discuss any code. The TAs and undergraduate mentors can provide some help on coding issues in office hours, but you should be able to answer your own coding and debugging questions.

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 may still cover things that do not appear in the textbook, 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.

Schedule and Announcements:

An up-to-date schedule will be maintained on the course website. All course announcements will be made using the Submitty email notification system.

Exams:

There will be three exams and a cumulative final exam, on the dates indicated on the course schedule. You must take the exams during the scheduled times. There will be NO make-up exams (unless the absence is excused by the Student Success Office).

Your exam average will be computed as follows:

• Exam 1: 23%
• Exam 2: 23%
• Exam 3: 23%
• Final Exam: 31%

Homework:

There will be 10 homework assignments. You are responsible for uploading your homework into Gradescope by 11:59pm on the due date. You may turn your homework in up to 24 hours late, for 80% max credit. No homework will be accepted more than 24 hours after the due date. The lowest homework grade will be dropped. Your homework average will be computed from your grades on the other 9 assignments.  The lowest three homework grades will be dropped. Your homework average will be computed from your grades on the other 7 assignments. This policy is intended to give you flexibility if you miss homework due to illness or other circumstances. There will not be any homework extensions, except in the case of long-term illness.

Homework assignments must be typed, with each problem starting on a new page. Figures may be hand drawn (neatly). Assignments must be submitted in PDF format. You must indicate the page number for each problem in Gradescope. If you do not do this, you will receive a grade of 0 on the homework.

Recitation/Office Hours:

The Wednesday recitation period will be used as required office hours. The specific required dates are indicated on the course schedule. Please make sure the TA or mentor checks off your attendance before you leave to receive credit.

You can miss one office hours week without penalty. Your recitation average will be computed as follows:
(number of required recitations attended + 1)  / (total number of required recitations)

You can miss three of the 10 required recitations without penalty. Suppose you attend k recitations. Your recitation average will be computed as min(k,7)/7. No additional excused absences will be granted for recitation except in the case of long-term illness.

Office hours will be led by TAs and mentors: these office hours are your main opportunity for getting individual attention, asking questions about lectures , 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 that is due that week. (Of course, please feel free to ask the TAs for advice on your homework: this is why they are there!).

Course Grade Policy:

To pass the course, you must do well on the exams and homeworks, and you must attend the required office hours. Specifically, you must meet the following two requirements.

1. Your assignment grade must be at least 70%, where

assignment grade = (0.9(homework average)) + (0.1 (recitation average))

2. You must have a passing exam average.

Provided you meet these requirements, your course grade will be equivalent to your exam average.

The following table will be used to convert your course grade to a letter grade.

Percentage:    [100,93]  [90,93)  [87,90)  [83,87)        [80,83)        [77,80)        [73,77)        [70,73)        [67,70)        [60,67)        [0,60)        

Letter Grade:  A              A-            B+        B         B-        C+         C         C-         D+         D         F

Individual assignments and exams will not be curved. The course grades may be curved but only to raise the grades.

Homework and exam grades will be made available throughout the semester in Gradescope. Grades for all assignments will be determined by the professor and the TAs. You may inquire about a homework or exam grade by submitting a regrade request in Gradescope. Grades inquiries must be made within 7 days of the posting of the graded homework or exam.

Academic Integrity

Student-teacher relationships are built 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 that violate this trust undermine the educational process. The Rensselaer Handbook of Student Rights and Responsibilities and The Graduate Student Supplement define various forms of Academic Dishonesty and you should make yourself familiar with these.

Every student must formulate and write up their homework assignments independently. Looking up solutions and/or copying solutions from another source is not permitted. You may not use third-party tools, including generative language models such as ChatGPT, to create, edit, or verify your homework solutions.

You are also responsible for protecting your own homework from being copied. If multiple students turn in solutions that are identical, this is cheating, and all students involved will be held accountable.  

No collaboration is allowed during exams.

Violation of these policies will be considered a breach of academic integrity. The minimum penalty for any violation is a course letter grade reduction. Violations of academic integrity may also be reported to the Dean of Students. If you have any question concerning this policy before submitting an assignment, please ask for clarification. In addition, you can visit the following site for more information on our Academic Integrity Policy: Students Rights, Responsibilities, and Judicial Affairs.

Disability Services

Rensselaer Polytechnic Institute strives to make all learning experiences as accessible as possible. If you anticipate or experience academic barriers based on a disability, please let me know immediately so that we can discuss your options.  To establish reasonable accommodations, please register with The Office of Disability Services for Students.  After registration, make arrangements with the Director of Disability Services as soon as possible to discuss your accommodations so that they may be implemented in a timely fashion. DSS contact information: dss@rpi.edu; +1-518-276-8197; 4226 Academy Hall.