Syllabus for Computer Science 365b, Design and Analysis of Algorithms
Spring 2017
Course Information
I (Dan Spielman) expect to teach this course every Spring for the
foreseeable future.
Prerequisites
The prerequisites for this course are discrete math
(CS 202 or Math 244) and CS 223.
The background in discrete math is essential.
You should be used to reasoning about graphs and
have some experience writing proofs.
Students will tell you that CS 223 is less essential.
But, it would be better to take it first if you can.
The main things that are taught in CS 223 that you must know
are how to implement basic data structures
in a language like C or Java.
You should also be able to estimate how many basic operations
are required by these implementations.
If you have not taken the prerequisites, be sure to familiarize yourself
with the material in Chapters 2 and 3 of Kleinberg-Tardos.
I also recommend that you try out the optional
Problem Set 0, and discuss it with the ULAs.
Yale has no mechanism to prevent you from taking the course
if you have not taken the prerequisites.
Proceed at your own risk.
Course Requirements
There will be 8 problem sets and two in-class tests.
There will not be a final exam.
The grading breakdown will be:
- Problem sets: 75%
- Tests: 25%
Problem Sets
A perusal of the
course schedule
will reveal that all problem sets are due at 2pm.
Note that is half an hour before class.
Problem sets submitted between 2pm and 2:30pm will receive a 5% late
penalty.
We might accept problem sets between 2:30pm and the end of class,
but we make no guarantees other than that those would receive a
substantial late penalty.
Note: we might change the time that problem sets are due to some time
the night before.
We will decide this by a vote of the class.
You will have longer for some problem sets than others, so
they will not all be handed out on Thursdays.
All problem sets must be submitted via Gradescope.
Gradescope requires a PDF of your homework.
There are three ways that students usually produce these:
- Write it by hand, and scan it by camera or scanner.
- Write it in LaTeX, and generate a PDF. We recommend generating
your latex either through an editor like Emacs or Sublime,
via an integrated package like TexWorks or TexShop, or
an online system like ShareLaTeX. We will provide some examples of
good LaTeX.
- Write it in Word, using "Insert Equation" for the math, and
generate a PDF.
If generating a PDF is going to pose a problem, contact the course
staff as early as possible to let us know so that we can figure out
how to make a suitable accomodation.
Assignment 0, uploading a current picture of yourself to gradescope,
has two purposes: making sure you (and us) have gradescope working,
and helping me learn who you are.
It is worth 1% of your grade.
If there are going to be problems with Gradescope, we would like to
know as soon as possible.
While I have largely given up on learning the names of everyone in the
class, I still try to figure out who most of the students are.
A picture will be very helpful.
Warning: generating a pdf from a picture might not be straightforward.
The problem sets are only distributed via Canvas, and do not
appear here.
Each problem set will have 3 problems, except
it is possible that problem sets 5 and 6 will only have two problems each.
Solution Sets
Solution sets are only distributed on paper.
These solutions are for your own personal use, and are not to be given
to other students or stored anywhere that students in future years
might encounter them.
The one exception to this rule is that you may give a copy of a
solution sets to another student who is presently enrolled in the course.
Late Assignments
As solution sets will be distributed at the end of the class at which
they are due, late
assignments will not be accepted.
There is a small chance that we will accept a problem set submitted
during class before the solutions have been handed out.
But, it would be substantially penalized.
Students who have a Dean's excuse for a problem set will be assigned
an alternate problem set.
Revised Collaboration Policy
You should strive to solve these problems on your own. But, sometimes even understanding the problems poses a
challenge. You are welcome to discuss the problems with your classmates to achieve understanding of the problems and to consider small examples. After you understand the problems, you should try to solve them on your own. If you need help, you can discuss the problems with the course staff. You may also ask others to find mistakes in your attempted solutions, and you may help find mistakes in your classmates' solutions.
If you are truly stuck, you may discuss the problems with a few other students.
If you do this, you must follow Stan Eisenstat's "Gilligan's Island Rule":
When discussing an assignment with other students, you may write on a board
or a piece of paper, but you may not take any written or electronic record
away from the discussion. Moreover, you must engage in a full hour of mind-
numbing activity (e.g., watching back-to-back episodes of Gilligan's Island)
before you work on the assignment again. This will ensure that you can
reconstruct what you learned from the discussion, by yourself, using your own
brain.
You must write your solutions independently.
Every problem set will come with an online form which you must use to
report your collaborators.
Failure to list people with whom you have discussed a problem set is
considered a violation of academic honesty.
Referencing sources
Similarly, if your solution draws on sources such as books or web
pages other than those supplied with the course, you must cite those
as well.
Where to find information
- The course schedule page. Look here
first.
- If there is information you need, and it is not on the course
schedule page, please look at this page. It should be here
- If neither of these pages reveals what you need to know,
you can email the course staff at
cs365ta@cs.yale.edu.
We may choose not to answer questions whose answers appear on
these pages.
- If you miss a class and would like to find out what happened,
ask another student in the course. Please do not ask the course
staff.
Also, do not forget to look at the course
schedule page
to find out which readings go with with lectures.
Technology in the classroom
One of your jobs as an undergraduate is to figure out how you learn
best. I learn best when I take notes with my right hand on a piece of paper with
no lines, or when I simulate this process with a tablet.
Some of you will learn best when you take notes with a laptop,
and some of you will be better off just paying careful attention and
not taking notes at all.
I will not presume to tell you what is best for you.
I do request that you ask a question if you are confused.
Even if you do not know why you are confused, asking a question can
give you time to figure out why.
Some professors misinterpret recent research in Education to conclude that
students should not use technology in classrooms.
However, this research studies how most students perform on certain
artificial tasks. It does not and can not predict how you will perform
best. Most students are right-handed and will learn best if they take
notes with their right hands. However, it would be idiotic
to dictate that all students must take notes with their right hands.
I'll save my other complaints with interpretations of that research for another time.