Instructor
Prasad Jayanti
Office: 224 Sudikoff Laboratory
Email: prasad@cs.dartmouth.edu
Office Hours
When emailing a question about a homework problem, instead of sending it to an individual, please send it
to all of the course staff (professor and 4 TAs) at
cs25staff@cs.dartmouth.edu
This way someone or the other will see and respond without much delay.
Also, whenever you have questions, feel free to see the professor or the TAs
during the following office hours:
- Monday: 12:30-1.30pm (Prof. Jayanti) and 6.00-8.00pm (TA, Room 213)
- Tuesday: 1:00-3:00pm (Prof. Jayanti) and 4.30-8.15pm (TA, Room 213)
- Friday: 12:30-1.30pm (Prof. Jayanti)
Teaching Assistants
Course Description
Algorithm design is heart and soul of computer science,
and CS 25 is all about designing algorithms and analyzing their time and space complexity.
The course covers Divide and Conquer, Greedy, and Dynamic Programming strategies for algorithm design,
and studies algorithms for sorting, median-finding, graphs, network flows, and implementations
of clever data structures, such as balanced trees and disjoint-sets.
For algorithm analysis, the course covers amortized analysis and how to solve certain 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 difficult enterprise.
By covering clever and 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 some understanding of how to present a convincing argument that the algorithm produces the correct answer within a certain time bound
Lectures
Lectures are in 115 Sudikoff in the 10 hour: MWF, 10:00-11:05 AM.
X-hour is Thursday 12:00-12:50.
X-hours
Since this course covers a lot of nontrivial material,
I expect to use nearly all X-hours for lectures.
Please note that there will be a lecture during the first X-hour
on Thursday, September 24, from 12:00 to 12:50pm.
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.
Prerequisite
Computer Science 8 and 19.
Text
There is one text, and it is required: Introduction to
Algorithms, Third edition by Thomas H. Cormen, Charles
E. Leiserson, Ronald L. Rivest, and Clifford Stein; we will refer to
it as "CLRS."
The Day by Day page will tell you what
reading I expect you to do for each lecture. You are
responsible for checking the syllabus page to find out what to
read. And you are of course responsible for then actually
doing the assigned reading.
Homework
There will be weekly homework assignments. They usually go out on
a Wednesday and are due in class one week later; the first homework will be
assigned on Wednesday, September 30. Only Professor Jayanti
may grant any extensions on homework assignments.
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. 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 details to clearly present your
solution, but not so many 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.
- You can work with others. 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, and so you should not simply "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, if you worked on that problem with anyone,
you should write down their names at the start of the solution
to that problem.
If you receive help from the professor or the TAs, be sure to acknowledge those names also.
- 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. 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 below under the section titled ``Exams'').
- Protocol during office hours:
If you receive any help during office hours (from me or the TA), we require that
you don't take any notes during such help sessions.
The idea is that you should understand what we discuss and be able to reconstruct it later
to write up the solution on your own.
- Extra credit problems:
In some homeworks, I might assign extra credit problems.
The points you get on these normally 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 scores
and the exam 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 extra credit problems
only after you have solved the regular problems as well as you possibly can,
and you enjoy the challenge that the extra credit problems pose.
Homework Lateness Policy
Homework is due at the beginning of class on the announced due date.
Late homework has an immediate 20% penalty
(unless you have a valid excuse and, unless impossible,
have discussed with me in advance), and 10% penalty per calendar day after that.
I will not accept a homework after the next homework is due, or after the final.
In this course, if you do not do homework on time,
you will soon find yourself overwhelmed, so please be regular with your work.
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 professor.
The midterm exam will go out on Wednesday, October 28 and will be due
before class starts on Wednesday, November 4.
The midterm exam replaces that week's homework.
The final exam will be a takehome exam.
It will be available on the web starting December 5
(more precisely, no later than 12.01am on December 5).
You will have 48 hours to work on the exam.
To accomodate 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 December 7.
This way I can be certain that I have all of the exams back
before noon on December 9.
Before the final exam, we will have a review session 1.00-2.30pm on Friday, December 4.
Grading
Simple formula:
- Homework: 50%
- Midterm exam: 25%
- Final exam: 25%
Although the cut offs vary from year to year, I provide the following information from the 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+: 85 to 90
- B: 80 to 85
- Other grades from D to B-: 60 to 80
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.
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.
The rules are different for the exams (because
exams are where we find out what you have learned by doing 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 homework 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, their Use and Acknowledgment,
which can be found on the internet at www.dartmouth.edu/~sources
Dartmouth's Academic Honor Principle applies to this course.
Please be sure to read the principle, which you can find at
.
Please ask me if you have any questions about the honor code as it
applies to CS 25. Better safe than sorry!
Disabilities
Students with disabilities enrolled in this course and who may
need disability-related accommodations are encouraged to make an appointment
to see me on or before October 2.
All discussions will remain confidential, although the
Student Accessibility Services office may be consulted
to discuss appropriate implementation of any accommodation
requested.
Religious Observances
Some students may wish to take part in religious observances that occur during
this acdemic term. If you have a religious observance that conflicts with
your participation in the course, please meet with me
on or before Friday, October 2 to discuss appropriate accommodations.
Back to CS 25 home page
Prasad Jayanti
<prasad@cs.dartmouth.edu>
Last modified: Tuesday, September 23, 2009