Syllabus for Computer Science 365b, Design and Analysis of Algorithms

Spring 2017

Course Information

  • Where : DL 220.
  • When : Tuesday and Thursday, 2:30-3:45
  • Required Textbook : Algorithm Design by Jon Kleinberg and Eva Tardos.
  • Instructor : Daniel A. Spielman.
  • You can email the course staff at
  • Announcements to the class will be made via Canvas.
  • The subject of every lecture, along with all readings, assignments and tests are listed on the course schedule. Please consult it regularly.
  • I (Dan Spielman) expect to teach this course every Spring for the foreseeable future.


    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

    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:

    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

    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.