| Schedule | Problem Sets | Policies |
|---|
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. A problem set 0 will be given out on first day of class which should allow you to
test compatibility.
Text Books:
I will not follow one single textbook but most material will come from the following three.
I strongly recommend having access to these books.
| Date | Topics | Further Reading | Announcements |
|---|---|---|---|
| 4 Jan (Thu): | Introduction + Logistics. Algorithms for numbers: add, multiply, divide | [DPV 1.1], | PS 0 given out, due: 1/11 |
| 9 Jan (Tue): | Big-Oh Notation, Time complexity of Algorithms | [DPV 0.3, CLRS, chapter 3] | The slides contain more what Prof. Jayanti covered |
| 11 Jan (Thu): | GCD, Divide and Conquer 1: Finding Max, Recurrences | [DPV 1.2, CLRS, chapter 2] | PS 1 given out, due 1/18 |
| 16 Jan (Tue) | Divide and Conquer 2: Counting Inversions, MaxRange Subarray, Master Theorem | [KT 5.3, CLRS 4.1, DPV 2.2] | |
| 17 Jan (X) | Divide and Conquer 2.5: Karatsuba's Algorithm for Subquadratic Multiplication | [DPV 2.1], | We also resolved the "dynamic sorting" question which arose from last time. I will perhaps put this resolution as a problem in a problem set. |
| 18 Jan (Thu) | Divide and Conquer 3: Nearest Pair of Points on a Plane | [KT 5.4, CLRS 33.4] | PS 2 given out, due 1/25 |
| 23 Jan (Tue) | Dynamic Programming 1: Fibonacci, Counting Heads, Subset Sum | [DPV 0.2, KT 6.4] | |
| 24 Jan (X) | Dynamic Programming 1.5: Knapsack Problem | [DPV 6.4] | |
| 25 Jan (Thu) | Dynamic Programming 2: Weighted Interval Scheduling, String Snipping Problem | [KT 6.1] | PS 3 given out, due 2/5 |
| 30 Jan (Tue) | Dynamic Programming 3: String Problems | [CLRS 15.4, KT 6.6, DPV 6.2-3] | |
| 1 Feb (Thu) | Greedy Algorithms 1: Weighted Completion Time, Picking Points in General Position, Matroid | [CLRS 16.4] | |
| 6 Feb (Tue) | Greedy Algorithms 2: Approximation Algorithms, Set Cover | [DPV 5.4] | |
| 7 Feb (X) | Midterm [4:35p to 6:35pm, Kemeny 008] | ||
| 8 Feb (Thu) | Graph Algorithms: Basics, Priority Queues | [CLRS 6, DPV 3.1] | PS 4 given out, due 2/15 |
| 13 Feb (Tue) | Graph Algorithms: Depth First Search | [CLRS 22.3] | |
| 15 Feb (Thu) | Graph Algorithms: Depth First Search, Strongly Connected Components | [CLRS 22.5] | The lecture notes contain more than what was covered in class. They are mostly definitions, and one proof. Please go through them. |
| 20 Feb (Tue) | Graph Algorithms: Shortest Path, Dijkstra's Algorithm | [DPV 4.2-4.5, CLRS 24.3] | |
| 21 Feb (X) | Graph Algorithms: Bellman Ford | ||
| 22 Feb (Thu) | Graph Algorithms: Bellman Ford, Shortest Path wrap-up | [DPV 4.6, CLRS 24.3] | PS 6 given out on Canvas, due 3/1 |
| 27 Feb (Tue) | Graph Algorithms: Flows and Cuts | ||
| 1 Mar (Thu) | Applications of Flows | PS 7 given out, due 3/8 | |
| 6 Mar (Tue) | "Hard" Problems. | ||
| 11 Mar (Sunday) | Final [3:00p to 6:00p, Venue: Kemeny 008] |
Evaluation
Grading Scheme
Although the final grades will be fit to a curve, the following gives some ``guaranteed grades''
Lectures, X-hours, Attendence Policy
I will be using almost all the X-hours and it is extremely critical you keep yourself free for these hours.
Algorithms is not a spectator sport, and you must participate to learn. Ask and Answer questions both in class and Piazza.
I have reserved 3 points for this activity which are at my discretion.
Grading Scheme for Problems
We will follow Amit Chakrabarti's detailed grading scheme .
Every problem will be worth 7 points which you get if you are complete, correct, and concise.
Note: presentation is as important as the ideas.
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 two late days available. Note that even a minute late in canvas is a day late.
Any late submissions after the two late days won't be considered.
No Laptop / No Phone Policy
We have a no-laptop/no-phone policy in class to minimize distractions and encourage participation.
We have a no-laptop/no-phone/no note-taking policy during office hours.
Academic Integrity / Honor Code
All work submitted for credit must be your own.
You may discuss the homework 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!