Course Description

This course is about the art of designing efficient algorithms for a wide range of fundamental computational tasks and the science of proving the correctness of such algorithms and formally analyzing their time complexity.

The course will introduce the following basic design paradigms: divide-and-conquer, greedy algorithms, dynamic programming, amortized analysis, and randomization. The computational tasks studied will span several domains. These include sorting and order statistics, computing with integers and number-theoretic algorithms, algorithms on graphs, and geometric algorithms.

Writing mathematical proofs will be required throughout this course. Students are expected to have previous experience with writing proofs. Taking CS 30 will provide this experience.

Students will be expected to be experienced programmers before taking this course, so that they are able to reason about algorithms/code at a high level without seeing actual lines of code in front of them. Taking our department's CS 1 – CS 10 sequence will provide this experience.

Administrative Information

Instructor

Amit Chakrabarti | Sudikoff 107 | Office hours: Th 10:00-11:00, Fr 10:45-11:45

Teaching Assistants

Anup Joshi | Head TA | Office hours: Fri 15:30-16:30 in Sudikoff 213

Yining Chen | TA, Grader | Office hours: Sat 16:00-17:00 in Sudikoff 213

Richard Dionne | TA, Grader | Office hours: Sun 16:00-17:00 in Sudikoff 213

Avery Feingold | TA, Grader | Office hours Sun 17:00-18:00

Matthew Jin | TA, Grader | Office hours: Mon 10:45-11:45 in Sudikoff 213

Getting Help

Primary method: piazza

Only under exceptional circumstances: cs31-help@cs.dartmouth...

Textbooks

Required: [CLRS] Cormen, Leiserson, Riverst, Stein. Introduction to Algorithms, 3rd edition.

Recommended additional: [KT] Kleinberg, Tardos. Algorithm Design.

Work and Grading

Class Plan

Please consult the schedule page.

Grading Scheme

Weekly homework sets (30%); Two quizzes (10% + 10%); Take-home midterm (20%); Final exam (30%)

Homework and Exam Schedule

Eight homework sets, due Mondays at 23:59

Quiz 1: Thu Apr 20, 18:30-19:30 in LSC 201

Quiz 2: Thu May 18, 18:30-19:30 in LSC 201

Midterm: Take home, due Mon May 1 at 23:59 (replaces homework that week)

Final exam part 1: Take home, with 48-hour limit, due Sun Jun 4 by 10:30

Final exam part 2: Sun Jun 4, 11:30-13:30 in LSC 201

Policies

No-Laptop/No-Phone Policy

We have a firm no-laptop/no-phone policy in class. Texting, sleeping or engaging in other activities unrelated to the class is also forbidden. This policy will be strictly enforced so as to encourage active participation by all students and to avoid distracting people that are focusing on the lecture. If you come to class you are expected to obey this policy. A penalty of 5% will be applied to the final grade every time this policy is violated. (Please read this article to better understand this policy.)

Absences and Scheduling Conflicts

This course moves fast and it is difficult to replicate the experience of seeing an algorithm and analysis unfold before your eyes by merely reading a textbook. So everyone is urged to attend every class. If you have a truly unavoidable academic conflict with one of the scheduled exams, you must let me know by 23:59 on Apr 7 (firm deadline) and make alternative arrangements. The final exam will be held one time only, at the registrar's appointed time noted above.

Late Submissions

Each student has 3 free late days to be used for homework assignment over the course of the term as he/she likes, with the exception that at most 1 late day may be used for Homework 8. Once these days are used up, any homework turned in late will be returned ungraded (and earn a score of 0). No exceptions! Any portion of a late day is counted as one full day (i.e., even one minute late counts as a full day) and if the Canvas timestamp says you're late, you're late; no exceptions. Homework can only be turned in electronically, via canvas.

Regrading Policy

If you are unsure why you lost points on a homework or exam problem, or feel that the grader made a mistake, you must act before the resolution deadline for that homework/exam. The resolution deadline for a homework is the submission deadline of the next homework. The resolution deadlines for Quiz 1, Quiz 2, and Homework 8 are 11:59pm on Apr 27, May 25, and Jun 2 respectively. Before the resolution deadline you must first contact the relevant grader(s) and try to resolve the matter with them. If you are unable to resolve the matter at this step, you may (optionally) make a formal regrade request. This must be made within 12 hours of the resolution deadline.
   To make such a request you must email the course staff (cs31-help@cs.dartmouth...) with a subject line that says something like "Formal regrade request for HW4", give evidence of having tried to resolve the matter with the graders, and say why you still feel something is wrong. The professor will then make a final determination. Be aware that if you make a formal regrade request then the professor may regrade your entire homework and the professor typically has stricter standards than the graders.

Academic Integrity

Collaboration on Written Homework

When working on homework problems, you may collaborate and discuss with the course staff and other students enrolled in this term's offering of this course (and not with any other persons). However, when you prepare the final draft of your solutions, you must work entirely by yourself and write answers in your own words. At the top of your submission, you must list all people you collaborated with, received help from, or gave help to. If you did the entire homework on your own, you must state that in writing.

Sources

When working on homework problems, you may consult this course's website, any handouts given out in class, discussions on this course's piazza forum, the two textbooks for this course, and your own notes. "This course" means this particular term's offering of CS 31. Consulting any other sources is forbidden, unless the professor has made an exception in writing.

Quizzes

The quizzes in this course are closed-book and closed-notes, except that each student is allowed to bring in a one-page "cheat sheet" (you may write/print on both sides of the page). The contents of the cheat sheet must be prepared by you on your own and you must submit the cheat sheet along with the exam. Consulting any other sources is forbidden. Giving and receiving help is forbidden, except that you may ask the course staff for clarifications.

Exams

When working on a take-home exam in this course, you must work entirely on your own, neither giving help to nor receiving help from anyone. You may, however, discuss any general topic covered in the course with either the professor or the head TA, so long as your questions aren't about the specific problems on the exam. (This policy will be clarified as needed as the first exam approaches.)

These rules will be strictly enforced and any violation will be treated with the utmost seriousness.