Schedule | Policies |
---|

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

** Background Assumed: **

Students should have basic knowledge about programming * and * should be able to read and write math proofs.
If you have taken CS 1, CS 10, and CS 30, you should be fine. In case you haven't, then please see the instructor.
See this for what I teach in CS30.

- Deeparnab Chakrabarty (Instructor)

Monday 4:30p - 5:30p @Sudi 214, Wednesday (4:30pm - 5:30pm) @Sudi 212

Thursday (4:30pm - 5:30pm) "individual" office hours @Sudi 216

- Prantar Ghosh (Head TA): Monday 1pm - 2pm @Sudi 212, Wednesday 1pm - 2pm @Sudi 214
- Sean Paulsen (TA): Monday 3:00pm - 4:00pm @Sudi 212, Wednesday, 2:30pm - 3:30pm @Sudi 114
- Sunbir Chawla (TA): Friday, 5:30pm - 6:30pm @Sudi 114
- Christina Lu (TA) : Tuesday, 2pm - 3pm @Sudi 212
- Linda Xiao (TA): Tuesday, 7:30pm - 8:30pm @Sudi 115
- Richard Yang (TA) : Sundays, 1pm - 3pm @Sudi 114
- Edward Yao (TA): Tuesday, 1pm - 2pm @Sudi 212

** Text Books **

There is ** no required ** textbook. Lecture notes will be posted after every lecture.
However, the material is mostly going to be from the following two books, and I will give pointers to them as well.

- (DPV)
*Algorithms*by Dasgupta, Papadimitriou, Vazirani - (CLRS)
*Introduction to Algorithms*by Cormen, Leiserson, Rivest, Stein

** Evaluation **

- Drills: 30%
- Weekly Problem Sets : 25%
- Midterm : 12 + 12%
- Endterm : 21%

Date | Topics | Notes | Other Reference |
---|---|---|---|

26 Mar (Tue): | Algorithms with Numbers | Lec, Supp | [DPV 1.1] |

27 Mar (X): | Big-Oh notation | Lec | [DPV 0.3, CLRS 3.1] |

28 Mar (Thu): | Divide and Conquer 1: Merge Sort, Counting Inversions | Lec, Supp | [DPV 2.3, CLRS 2.3] |

2 Apr (Tue): | Divide and Conquer 2 : Maximum Range Sub-Array, Multiplying Polynomials Fast | Lec | [CLRS 4.1], [DPV 2.1] |

3 Apr (X): | Prantar Proves Master Theorem | Notes | |

4 Apr (Thu) | Divide and Conquer 3: Closest Pair of Points; Dynamic Programming 0: Recursion with Memory | Lec | [CLRS 33.4] |

9 Apr (Tue) | Dynamic Programming 1 : Subset Sum Problem | Lec | |

10 Apr (X): | Dynamic Programming 2: Knapsack problem | Lec | |

11 Apr (Thu) | Dynamic Programming 3: Longest Common Subsequence, Edit Distance | Lec | |

16 Apr (Tue) | Instructor Out-of-Town | ||

18 Apr (Thu) | In-class Midterm 1: 10A hour, Filene |
Instructor Out-of-Town | |

23 Apr (Tue) | Randomized Algorithms 1: Frievald, QuickSort | Lec | |

25 Apr (Thu) | Randomized Algorithms 2: Hashing | Lec | |

30 Apr (Tue) | Graph Algorithms 1: Depth First Search | Lec | |

1 May (X) | Graph Algorithms 1.5: Depth First Search (some proofs) | ||

2 May (Thu) | Graph Algorithms 2: Applications of Depth First Search | Lec | |

7 May (Tue) | Graph Algorithms 3: BFS, Shortest Paths | Lec | |

9 May (Thu) | Graph Algorithms 4: Dealing with Negative Costs | Lec | |

10th May (Fri) | In-class Midterm 2, [3:30p to 6:00p, LSC100] |
||

14 May (Tue) | Graph Algorithms 5: Flows and Cuts | Lec | |

16 May (Thu) | Graph Algorithms 6: The Ford-Fulkerson Algorithm | Lec | |

21 May (Tue) | Graph Algorithms 7: Applications of Flows | Lec | |

23 May (Thu) | Graph Algorithms 8: Faster Flows | Lec | |

28 May (Tue) | P, NP, and all that Jazz | Lec | |

28 May (Tue) | Review | Lec | |

June 1 (Sat) | In Class Finals : 3pm - 6pm |

** Evaluation Policies : Details**

- After almost every class there will be a
**Drill**exercise of a few problems with a (more than)__48 hour__deadline. These are supposed to make sure you understand the material taught in class that day. Many of the drills will involve coding the algorithms in your favorite language.*You must do these drills on your own without discussion with anyone.*You must also write all your code on your own, and not browse the web for answers. Clarification questions should be asked on Piazza. Be careful not to violate the Honor Principle.

You should of course try to do every drill. I understand that the time constraint is tight, and thus there will be a 15% grace. So, if the total points on drills is 60, you will be graded as if the total is 51. So if you get 45/60, it will be counted as 88.4% (and not 75%).

- There will be
**Weekly Problem Sets**. These will be*challenging*problems. You will have at least a week to solve them, and will be due by Wednesday 11:59pm. Doing these will reinforce the algorithmic techiques you learn the previous week.

You should first try doing this problems on your own. When stuck, you are allowed to discuss ideas with your (a) fellow students, (b) TAs, and (c) instructor. No one else (not even your individual Tutor, if you have one).*But you must write your answers in your own words*. Also, for*every*question, you must mention who you discussed with. This is serious; if you don't you will get a 0 for that question.

- I will also be posting
**Ungraded problem sets (UGPs)**. The difficulty of these problems will be somewhere between drills and the weekly problem sets. Doing the UGPs first may help you in solving the Weekly Problem Set. I will also post their solutions, usually on Sunday mornings.

- I may post
**Extra Credit**problems attached with certain weekly problem sets. Students can hand in the solutions with the weekly problem set. These are, as the name says, extra credit. They won't be counted for the final points, but it may affect my decisions for students on the border of two grades. But you should attempt these only after you have finished your weekly problem set.

- At times, after a certain concept is covered, I may also post other
**Supplemental Problems**. Use these to get more practice and learn a bit more about any concept.

- There will be three
**in-class, timed, closed-book**exams (two midterms + one final). You should think of the drills and problem sets as practice for your exams. If you have sharpened your skills doing the PSets, then you will be able to do the exams well. Bluntly put, if you are only using office hours to get the Psets solved, chances are you won't do well in the exams.

- Final grades will be
**curved**. However, if you get more than 92%, you will get an A. If you get more than 55%, you will pass the course. These are sufficient conditions, not necessary. I expect the median grade to be B+ (of course I can be surprised either way).

- Most importantly, Algorithms are fun;
**Please have fun**. Algorithms are indeed difficult to master, and the barrage of problems that I provide from my end (although only a few are for credit) may feel stressful. Please don't be stressed. Algorithms, after all, are not the most important thing in life.

** 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. However, Drills will have slack, that is, even if you miss one,
you will have an opportunity to make up.

** 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.

** Office Hours Policy **

There is ** no laptop/cell phone allowed ** in office hours (Instructor or TA). So if you have a specific question on a problem set, please make sure to get a print-out of that problem set.
You are also not allowed to sit in office hours and write your assignment solutions. Remember: if you don't understand the concepts, you may suffer in the
in-class tests.

** Academic Integrity / Honor Code **

__ All work submitted for credit must be your own.__
This means what you put down on paper for submission ** must be your own words ** and
cannot be in any way copied from a black/white board, a computer screen, or even your notes from class.
Please be *extremely sure* of this. Also, many of the problems have their solutions on the web.
You are ** not allowed ** to search or obtain and consult these solutions.

You ** cannot ** discuss the drill problem sets with anyone. Clarification questions can be asked on Piazza, or face-to-face.
Piazza is preferred as the doubt may be common and the answer reaches everyone.

You may *discuss* the problem sets and ideas to attack them with (a) your classmates (taking the course with you), (b) the TAs, and (c) the instructor.
**No one else.** Not even your individual Tutor, if you have one.

You are also not allowed to give away solutions to your classmates.
Clarification questions about problems should be asked on Piazza.

__ This is important: Please carefully read what is written below.__

When you submit your weekly problem set, at the beginning of each problem you must write who all helped you and who all you helped with this problem.
If you did not talk with anyone, mention this as well. This information forms a part of your submission.
** This can't be written as a comment on your Canvas submission. **
** If you do not follow the above, you may be awarded zero points. Seriously.**
I know many solutions are written at the last minute; spend the first 10 seconds of that minute to
cite people who help you.

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. Please, please don't be in a situation where you and I need to go through unpleasantries.