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 and data structures 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 software 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. The labs 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 lab. 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 the course website regularly for announcements and course materials, as well as your e-mail for communications related to the class.

Lectures. Students are highly encouraged to attend all classes. You are responsible for all material covered and announcements made in lecture.

Laptops and Electronic Devices. No laptops or other electronic devices are allowed in lecture, excpet that you use it for in-class polling. Even if you are diligently taking notes on your laptop, the bright screen and the activity is extremely distracting to the people behind you. Because of this, "movie theater" rules apply: no laptops, phones, or other devices with a screen on them should be out during lecture, except for in-class polling. After the polling, you mst turn it off. Students who continually disrupt the class will be asked to leave.

Exams. There will be two midterm exams in class (see the class Schedule) for the exact dates, and a comprehensive final exam during finals week. All exams are open-textbook and open-notes. We will not provide make-up exams unless the absence is excused by the Dean of Students. Any students with special circumstances must notify me during the first two weeks of class.

Grading.The two midterm exams will count for 20% of your final grade each, the final exam for 30%, the homework for 18%, the labs for 10%, and the recitation attendance for 2%. We will drop the lowest homework grade. 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 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. 
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.

Final Grades: Final scores will correspond to the following letter grades: A/A-: 90-100; B+/B/B-: 80-90; C+/C/C-: 70-80; D+/D: 65-70 
Exam Cutoff: In addition to the above cutoffs, to pass the class, a student must earn a weighted average grade of at least 65 percent on the exams.

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.
In this class, you are allowed (and encouraged) to discuss homework and lab problems with other members of the class, and to formulate ideas together. However, everyone must write up their assignments completely separately, and include the names of everyone you discussed the assignment with. When working on lab 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 or lab 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, 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. No collaboration, or any electronic devices, is allowed during exams. 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. 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 handed in at the beginning of lecture on the day it is due, in the folder labeled with your section number; if consisting of multiple pages the pages must be stapled (we will take off points if this is not the case). Electronic submissions will not be accepted. Each student will be given a budget of two (2) 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 of lecture, for example on the following Monday instead of on Friday. Any part of a late day that you use counts as a full late day. For example, if you submit your homework until the end of lecture instead of the beginning, that counts as a full late day, so you might as well wait and submit it at the start of the following lecture. You cannot use both late days for the same homework. Please do not submit homework anywhere except at the beginning of class; homework submitted in any other way may be discarded and will receive a 0-grade.

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 a written note from the office of the Dean of Students. Late days are not applicable to labs!

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 your writing is illegible, or if we do not understand what you are trying to say. Because of this, it is in your best interest to type your work (we suggest using LaTeX), and 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, and include the list of "collaborators" that you discussed the assignment with. 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 homework grade 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 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 has been made. Do not be surprised if your regrade takes a long time, as we will only process them periodically.

3. Lab Guide

Labs: The purpose of labs is to help you with the course material in a smaller setting. You will be required to complete a small assignment for each lab. This assignment will be handed out in advance, and ideally, you will finish the assignment in advance of the lab. However, you can get help from the TAs during lab if you are unable to finish in advance. See the class hour schedule for the time and place of your lab section. Labs will be held weekly and attendance to scheduled labs is required. Those who show up late for lab or those who leave without completing the lab risk not receiving full credit. Labs cannot be made up: the only way to receive credit for a missed lab is to obtain a written note from the office of the Dean of Students excusing your absence. The exams will contain material covered in labs. Due to the size of the sections, you must attend your assigned lab section. The TA will take attendance and you will not receive credit unless you attend your assigned section. Homeworks will also be usually returned on Wednesdays during labs, so it is in your best interest to attend them.

A reminder: this is not a programming class. The labs involve programming, but you are expected to be a competent programmer coming in. The TAs and undergraduate programming mentors can provide some help on programming issues in lab, but you should be able to answer your own programming and debugging questions.

Lab Grading: To obtain credit for a completed lab assignment, you must show your code and results to a TA during your assigned lab section. Please do not submit your code: we will ignore it. The only way to get credit for a lab is to show your results and code to a TA in person during your assigned lab section. Please make sure that the TA checks you off: do not leave the lab section before the TA records your name and grade. If your results are shown to the lab TA before the end of the section, then the grading will be as follows:

• 3 - The results and code are essentially correct
• 2 - The results and code have some problems, but the main ideas are mostly correct
• 1 - Given at discretion of the TA
• 0 - Did not attend lab, or results and code are completely wrong or incomplete