CS 31: Algorithms, Spring 2018


Schedule Policies

Course Description and Goals:
Algorithms are step-by-step instructions for a computation problem. Although this sounds like a cooking recipe, good algorithms is what makes the modern world run.
          In this course, we will study algorithms rigorously. At the end of the course, the student should be able to design algorithms for problems, reason about these algorithms, and communicate the algorithm and its analysis.

Background Assumed:
Students should have basic knowledge about programming and should be able to read and write mathematical proofs. If you have taken CS 1, CS 10, CS 30 or equivalents, you should be fine. In case you haven't, then see this .


Class Times: 10A (TR: 10:10am - 12noon), X-hours (W: 3:30pm - 4:20pm)
Venue: Filene, Moore
Discussions: Piazza
Problem Sets: Canvas
Personnel and Office Hours:

Text Books:
I will not follow one single textbook but most material will come from the following two.

Evaluation

After every class there will be a drill exercise of 1 or 2 problems with a 36 hour deadline. There will be weekly problem sets. There is one Midterm and Endterm Examination which are in-class and closed-book.

Tentative Weekly Schedule

Date Topics Further Reading Announcements
27 Mar (Tue): Introduction + Logistics. Algorithms for numbers. [DPV 1.1]
29 Mar (Thu): Big-Oh Notation, Time complexity of Algorithms [DPV 0.3, CLRS 3.1]
3 Apr (Tue): Divide and Conquer 1 : Merge Sort, Recurrences, Counting Inversions [DPV 2.2, 2.3; CLRS 2.3.1] There will be X-hours tomorrow (4/4)
5 Apr (Thu) Divide and Conquer 2 : Maximum Range/Sum Subarray, Karatsuba Magic [CLRS 4.1, DPV 2.1] CLRS4.1 has a weaker result than what we did in class; DPV attributes Karatsuba to Gauss. DPV also has the Fast Fourier Transform in case I never get to it.
10 Apr (Tue) Divide and Conquer 3 : Closest Pair of Points; Recursion with Memory [CLRS 33.4] There will be X-hours tomorrow
12 Apr (Thu) Dynamic Programming 1 : Subset Sum and the Knapsack Problem [DPV 6.4]
17 Apr (Tue) Dynamic Programming 2 : Longest Common Subsequence, Longest Increasing Subsequence [CLRS 15.4, DPV 6.3]
19 Apr (Thu) Dynamic Programming 3: Weighted Interval Packing, Weighted Independent Set on Trees [DPV 6.7]
24 Apr (Tue) Randomized Algorithms 1: Checking Matrix Multiplication
25 April (X) Midterm [3:30p to 5:30pm, Filene]
26 Apr (Thu) Randomized Algorithms 2: QuickSort, Hashing, Fingerprinting
1 May (Tue) Graph Algorithms: Depth First Search There will be X-hour tomorrow.
3 May (Thu) Graph Algorithms: Depth First Search
8 May (Tue) Graph Algorithms: BFS, Shortest Paths
10 May (Thu) Graph Algorithms: Shortest Paths
15 May (Tue) Graph Algorithms: Flows and Cuts
17 May (Thu) Graph Algorithms: Flows and Cuts
22 May (Tue) TBA
24 May (Thu) TBA No Class: Instructor Out-of-Town
29 May (Tue) TBA
30 May (X-hour) TBA

Policies

Lectures, X-hours, Attendence Policy
Attend all classes. Posted slides are for review not first-view, and I don't make any guarantee that they contain everything I say in class. I will be using many of the X-hours and it is extremely critical you keep yourself free for these hours.

Regrading Policy
If there is a totalling error, please see any of the TAs and they will fix it rightaway.
On the other hand, if you feel that the grader has not graded accurately then you should clearly write down which problem and your reason why you think the grading is incorrect, staple it with your answer-sheet and hand it to the Head TA during his or her office hour
If even after this you feel unsatisfied, then you can email the instructor for a full regrade . I will look at the entire problem set and re-grade it completely.

Late Exercises and Problem Sets
Problem Sets are submitted via Canvas. Each student has a total of two late days available. Note that even a minute late in canvas is a day late. I will be extremely strict on this: any late submissions after the two late days will be straight given a zero. No excuses shall be entertained. Drill Problem Sets have no late days available.

Laptops and Phone Policy
We encourage students not to use devices in class. If they have to, then they need to seat themselves on the fringes of the classroom so as to not distract other students.
During office hours, there are no devices and no notes allowed. Period. If you need to discuss a problem set, then please have it printed out. Please don't make me repeat these policies aloud in class and office hours.

Academic Integrity / Honor Code
All work submitted for credit must be your own. This means what you put down on paper for submission cannot be in any way copied from a black/white board, a computer screen, or even your notes from class.
You cannot discuss the drill problem sets with anyone. You may discuss the problem sets with your classmates (taking the course with you), the TAs, and the instructor. No one else. You are also not allowed to give away solutions to your classmates. Clarification questions about problems should be asked on Piazza.
        At the beginning of each problem you must write who you discussed with, and what way did the person help you or you help them. This is important. If you did not talk with anyone about any of the problems, mention this at the beginning of the homework. Any written sources used (apart from the text, your lecture notes and any homework solutions that I distribute) must also be acknowledged; however, you may not consult any solutions on the Internet or from previous years' assignments, whether they are student- or faculty-generated.
        Dartmouth's Academic Honor Principle applies to this course. Please be sure to read the principle, which you can find here . Please ask me if you have any questions about the honor code as it applies to CS 31. Better safe than sorry!