CS 31 Winter 2020 Syllabus
Instructor
Prasad Jayanti
Office: 224 Sudikoff Laboratory
Email: prasad @ cs.dartmouth. edu
Teaching Assistants
Professor's Office Hours (Tentative)
- Monday 1.30-2.30 pm (in Room 213)
- Tuesday 4.00-5.00 pm (in Room 213)
- Friday 1.30-2.30 pm (in Room 213)
All Office Hours
The times below are tentative.
- Sundays: 6.00-7.00 pm (Ugur in Room 213)
- Mondays: 1.30-2.30 pm (Professor in Room 213) & 5.00-7.00 pm (Maha and Yakoob in Room 245)
- Tuesdays: 4.00-8.00 pm (Professor, Linda, Anup, Maha in Room 213)
- Fridays: 1.30-2.30 pm (Professor in Room 213)
Course Description
Algorithm design is the heart and soul of computer science,
and CS 31 is all about designing algorithms and analyzing their time complexity.
The course covers divide-and-conquer, greedy, and dynamic programming strategies for algorithm design,
and studies algorithms for median-finding, graphs, network flows, and the design
of clever data structures, such as balanced trees and disjoint-sets.
For algorithm analysis, the course covers amortized analysis and solving certain types of recurrence relations.
Weekly homework exercises and two take-home exams reinforce learning.
Course Goals
Even if a student never subsequently studies algorithms,
the student will never forget that
(1) humanity's ability to solve large scale computational problems
that arise in the real world depends to a large degree on our ability to design efficient algorithms, and
(2) the design and analysis of algorithms is a challenging enterprise.
Through a study of efficient algorithms for some common problems (e.g., sorting, searching, shortest paths, network flows), the course helps the students
- appreciate how clever observations about a problem can lead to the design of a good algorithm
- learn some powerful strategies (e.g., Divide and Conquer, Greedy, and Dynamic Programming) that are commonly applicable in algorithm design
- learn some algorithm analysis techniques (e.g., solving recurrences and amortized analysis)
- gain understanding of how to present a convincing proof that the algorithm produces the correct answer within a certain time bound
Lectures, X-hours & Attendance Policy
All lectures are held in LSC 201 in the 10 hour: MWF 10.10-11.15 PM.
The X-hours are on Thursdays 12.15-1.05 PM.
The course covers a lot of nontrivial material, so I expect to use most or all X-hours for lectures.
It is extremely important that you have no other engagements during X-hours.
I cannot adequately emphasize the need to attend all lectures, including X-hours.
Many students find the material of CS 31 fun and useful, but challenging.
The best way to cope with the challenge is not to miss even a single lecture, not be late to class, and be attentive in class.
It takes a lot more time to learn a topic on your own (even with the help of the lecture videos).
To reinforce the importance of attending lectures, 4% of the course grade is set aside for attendance.
I understand that a variety of situations---falling sick, interviews, family emergencies etc.---lead to missing some lectures.
So, I have a liberal policy of allowing up to 8 absences without any penalty (note that attendance is taken during MWF lectures as well as Tuesday X-hours).
If a student misses more than 8 lectures (counting x-hours), they lose all 4 of the attendance points, but if they miss 8 or fewer lectures in the term,
they get all 4 attendance points.
The Day by Day page lists what
what topic is covered in each lecture.
Prerequisite
Computer Science 10 and 30 are both required. If you have not passed these two courses, you must talk to Professor Jayanti.
Text
Here are two good texts, but neither is required.
-
Introduction to Algorithms, 3rd edition,
by Cormen, Leiserson, Rivest, and Stein; we will refer to it as "CLRS."
-
Algorithm Design
, by Jon Kleinberg and ÈEva Tardos; we will refer to
it as "KT."
Homework
There will be weekly homework assignments.
They go out on Wednesdays and are due next Tuesday by 11.59 PM.
The first homework goes out on January 8.
Homework can only be turned in electronically, via canvas.
For homework lateness policy, see the section below on Policies
A few points about the homework assignments:
- Start early. Difficult problems are not
typically solved in one sitting. Start early and let the ideas
come to you over the course of a few days.
- Be rigorous. Each problem has an
unwritten requirement that you argue the correctness of your algorithm
and analyze its running time. To obtain full
credit for a problem, it is necessary to fulfill these
requirements. Normally, I expect a convincing correctness argument
and a good analysis of the running time, and not mere
"hand waving" arguments.
- Be concise. Express your algorithms at the
proper level of detail. Give enough detail to clearly present your
solution, but not so much that the main ideas are
obscured. English is often a good way to express an
algorithm; pseudocode is good for communicating a complex control
structure. Make sure you explain what your algorithm does
in words even if you use pseudocode to specify parts of it.
- You can work with others, but only to a limited extent.
Some of the problems will be
difficult, and it might often be helpful to discuss them with
others. Feel free to form study groups. The idea, however, is for
everyone to understand the problems and experience
working through the solutions, so you should not show, email, or give
a solution to another classmate. In particular, each student
should write up his or her own homework solutions and should
not read or copy the solutions of others.
For each problem, you must state the names of students whom you did any discussion with on that problem, including the professor or the TAs. You can state none if you solved the problem entirely on your own.
- Work on your own before talking to others:
Although, as I said above, you can work with others on the homework problems,
you will learn the most by first trying out each problem on your own.
Make as much progress as possible on your own before you meet with your
study group, the TA, or the professor. If you get used to working with others and
often don't come up with the solutions on your own,
you may do okay in the homework component of your grade,
but you will suffer in the exams where you are strictly prohibited
from collaborating with anyone (see the section below titled ``Exams'').
- Protocol during office hours:
Please use the office hours to ask questions and receive help.
During office hours, the TAs and I require that you don't write or type anything at all.
The idea is that you should understand what we discuss and be able to reconstruct the solution later
on by yourself when writing up your answers.
Therefore, you are required to keep your notebooks and laptops closed during office hours, and not take any pictures of the board.
- Extra credit problems:
Rarely, I might assign extra credit problems.
Any points you get on these don't count towards your final grade.
More specifically, at the end of the term
I first assign the final grades based purely on your regular homework, exam, and attendance scores.
I will then look at the extra credit points that you earned.
If you are right on the border between two letter grades and there is evidence
that you solved a substantial number of extra credit problems correctly, then
(and only then) the effort you put into the extra credit problems can help you.
Because of this policy, extra credit is unlikely to be helpful from the point of view of grades.
I therefore encourage you to work on the extra credit problems
only after you have solved the regular problems as well as you possibly can,
and only if you enjoy the challenge that the extra credit problems pose.
Homework Late Days
Each student has 3 free late days towards
homework submission over the course of the term.
Manage them wisely, conserving them for unforeseen situations such as interviews, falling sick,
multiple midterms in the same week etc.
Any portion of a late day is counted as one full day (for example, if your homework is 36 hours late,
it costs you 2 late days, and not 1.5 late days).
Even one minute late counts as a full day and
if the Canvas timestamp says you're late, you're late; no exceptions.
Late days can be used only for homework, and not for the midterm or the final exam.
Once the three late days are used up, any homework turned in late will suffer a penalty of 20% for each day
(for example, if your score on a homework would normally be 84% but you turned it in 30 hours late and you have no late days left,
your score will be recorded as 84 minus a penalty of 40, which is 44%).
Homework can only be turned in electronically, via canvas.
Exams
There will be a midterm exam and a final exam, both of which will be
take-home. Unlike the homework assignments, you may not discuss exam
problems with anyone, not even with the TAs or the professor.
Also, late days can be used only for homework
and not for the midterm or the final exam.
The midterm exam will go out on Wednesday, February 12 and will be due
by 11.59pm on Tuesday, February 18.
I give about a week to solve the midterm partly to accommodate the diverse schedules and situations such as interviews, multiple midterms,
down sick for a couple of days etc.
Late days and penalties apply only to homework and not to the midterm or the final:
the deadline of 11.59pm Tuesday, February 18 to turn in the midterm is strict.
There will be no homework during the week of the midterm.
The final exam will be a take-home exam.
It will be available on the web starting 12.01am March 9.
You will have 48 hours to work on the exam.
To accommodate everyone's schedule, I let each of you decide
when you want to start on the exam, but you must start
on the exam no later than 11.59am on March 11.
This way I am certain that I'll have all of the exams back before noon on March 13.
Homework/Exam Regrade Procedure
Your work is graded by the graduate TAs and the graders,
according to a grading guide that I explain to the graders at a meeting each week.
In case you have any grading questions on a homework or exam, please follow the procedure below.
- If the grader made an obvious mistake (e.g., totaling error), you can see me or any TA during any of the TA hours,
and we'll make the correction right away.
On the other hand, if (after reading my solutions) you feel the grader did not grade your answer accurately,
then you should contact the grader by email or during his/her office hours, in less than a week from when the homework/exam was graded,
or March 10, whichever is earlier.
You will be informed which grader graded which problems.
Please note that any regrade request that comes after the deadline stated above
will not be considered, regardless of its merit.
-
If you still feel the matter is not resolved satisfactorily, then you should email me or see me.
Grading
Simple formula:
- Homework: 48%
- Midterm exam: 24%
- Final exam: 24%
- Attendance: 4%
Although the cut offs vary from year to year (depending on the class median), I provide the following information from previous years
as a rough guide to the expected performance for the various top grade levels:
- A: 93 and above
- A-: 90 to 93
- B+: 86 to 90
- B: 81 to 86
- Grades from D to B-: 60 to 81
Honor Code
All work submitted for credit must be your own.
As explained below, the rules with regard to the extent of collaboration are different for homework and exams.
You may discuss the homework problems with your classmates, the
TAs, and Professor Jayanti, but you must write up your own
solutions. For each problem, you must indicate who else you worked
with or got any help from, small or big. Even if you worked with the same people on the entire
assignment, be sure to write their names at the start of the solution of each problem.
If you didn't collaborate with any, state that explicitly.
Any written sources used (apart from the text, your lecture notes and any
solutions that I distribute in this term) 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.
The rules are different for the exams (because
exams are where we find out what you have learned from the class and the homework).
Unlike the homework, any discussion of the problems is prohibited for
the midterm and the final exams:
you may not discuss the problems with your classmates, the TA, the professor or anyone else.
You may not consult written sources other than
the text book, your class notes, and any solutions that I distribute during this term;
and you may not consult any electronic sources, including the Internet.
You should consult a copy of Sources and Citations at Dartmouth College, which can be found on the Internet at
http://writing-speech.dartmouth.edu/learning/materials/sources-and-citations-dartmouth.
Dartmouth's Academic Honor Principle applies to this course.
Please be sure to read the principle, which you can find at
http://www.dartmouth.edu/judicialaffairs/honor/
.
Please ask me if you have any questions about the honor code as it
applies to CS 31. Better safe than sorry!
Laptop/Phone Policies
- No-Laptop/No-Phone Policy during Lecures
- We have a no-laptop/no-phone policy in class to minimize distractions and encourage participation.
Please read this article to better understand this policy.
- No-Laptop, No-Notetaking Policy during Homework Help Hours:
- We have a firm policy that you do not take any notes on paper or on any electronic
device during Homework Help Hours. Accordingly, laptops/tablets/phones
as well as notebooks should remain closed during these hours.
The basic idea is that you should understand what we have discussed and
be able to reconstruct the solutions later by yourself.
Disabilities
Students with disabilities who may need disability-related academic adjustments and services
for this course are encouraged to see me privately as early in the term as possible,
but no later than Friday, January 17. Students requiring disability-related
academic adjustments and services must consult Student Accessibility Services (SAS).
Once SAS approves any accommodations, students must bring their approvals to me.
As a first step, if students have questions about whether they qualify to receive
academic adjustments and services, they should contact the SAS office.
All inquiries and discussions will remain confidential.
Religious Observances
Some students may wish to take part in religious observances that occur during
this academic term. If you have a religious observance that conflicts with
your participation in the course, please meet with me
on or before Friday, January 17 to discuss appropriate accommodations.
Back to CS 31 home page
Prasad Jayanti
<prasad @ cs.dartmouth. edu>
Last modified: January 4, 2020