CS 31: Algorithms, Spring 2019

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

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

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

Students don't have to buy any of the above books. Indeed, if you Google, you may find pdf copies on the web. You are, however, not allowed to look at or refer to the solutions manuals for these books.

Evaluation

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

More details here.

Tentative Weekly Schedule

<--

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

Policies

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.