Fall 2017 CS231

This is a course about algorithms and their analysis

About CS231

The language of computer science is to a great extent the language of algorithms. Although there are many thousands of algorithms, there are relative few basic design techniques. These include: divide-and-conquer, greedy, dynamic programming, and network flow. We will illustrate these techniques by studying a few fundamental algorithms of each type. In addition to helping us understand classic solution techniques, these algorithms have proven very useful in practice. Their names and the names of the problems they solve have become a standard part of the language of computer science.

Unfortunately, there is rarely a best algorithm to solve a given problem. Each approach involves a series of tradeoffs. Therefore, we will also study methods for evaluating the usefulness of an algorithm in a given situation. Among the various competing measures, we will focus primarily on the anal- ysis of time and space complexity. However, a number of other issues will also be discussed.

Meet your instructors & tutors

Click here for CS231 drop-in calendar

CS231 Fall 2017 schedule

Note that all readings are required to be done before class, except for the first lecture :)
Please check this page frequently, as it is subject to change.






Sep 4

Labor Day: no classes

Sep 5

Sep 6

Sep 7

Lecture 1: Introduction

Reading (not required): Chapter 1

Sep 8

Sep 11

Part I - Basics

Lecture 2: Tractability and Asymptotic order or growth

Reading: Sections 2.1 and 2.2

Sep 12

Sep 13

Sep 14

Lecture 3: The Stable Matching problem

Reading: Sections 1.1 and 2.3

Sep 15

Assignment 1 due at 9:00pm

Sep 18

Lecture 4: Priority Queues

Reading: Section 2.5

Sep 19

Sep 20

Sep 21

Lecture 5: Priority Queues and Binary Search Trees

Reading: KT Section 2.5 and CLRS Section 12.1

Sep 22

Assignment 2 due at 9:00pm

Sep 25

Part II - Graphs

Lecture 6: Intro and Basics

Reading: Sections 3.1 and 3.2

Sep 26

Sep 27

Sep 28

Lecture 7: Graph Traversals

Reading: Sections 3.3 and 3.4

Sep 29

Assignment 3 due at 9:00pm

Oct 2

Lecture 8: Connectivity in Graphs and Topological Ordering

Reading: Sections 3.2, 3.5 and 3.6

Oct 3

Oct 4

Oct 6

Oct 9 4

Fall Break: no classes

Oct 10

Fall Break: no classes

Oct 11

Oct 12

Part III - Greedy Algorithms

Lecture 9: Scheduling

Reading: Section 4.1

Oct 13

Assignment 4 - Full version due at 9:00pm

Oct 16

Lecture 10: More on Scheduling

Reading: Section 4.2

Oct 17

Oct 18

Oct 19

Lecture 11: Scheduling again?!

Oct 20

Assignment 5 due on Sunday at 11:59pm

Oct 23

Lecture 12: Graphs again?!
(SP - MST)

Reading: Sections 4.4 and 4.5

Oct 24

Oct 25

Oct 26

Exam 1

Includes: Everything until the end of Lecture 11

Oct 27

Oct 30

Part IV - Divide and Conquer

Lecture 13: Merge Sort

Reading: Section 5.1 and 5.2

Oct 31

Nov 1

Nov 2

Lecture 14: Recurrence Relations and More on Sorts

Reading**: Section 5.2
Heap Sort
Quick Sort

Nov 3

Nov 6

Lecture 15: More on Divide and Conquer

Reading: Section 5.3

Nov 7

Nov 8

Nov 9

Part V - Dynamic Programming

Lecture 16: Basics and Principles

Reading: Sections 6.1 and 6.2

Nov 10

Assignment 6 due at 9:00pm

Nov 13

Lecture 17: The Knapsack problem

Reading: Sections 6.3 and 6.4

Phase 1 of paper due

Nov 14

Nov 15

Nov 16

Lecture 18: Back to Graphs :)

Reading: Sections 6.8 and 6.9

Nov 17

Assignment 7 due at 11:59pm

Nov 20

Exam 2 - In class

Includes: Everything till the end of lecture 18

Nov 21

Nov 22

Thanksgiving Break

Nov 23

Thanksgiving Break

Nov 24

Thanksgiving Break

Nov 27

Part VI - Advanced Topics

Lecture 19: Network Flow (1)

Reading: Sections 7.1, 7.2, and 7.3

Phase 2 of paper due

Nov 28

Nov 29

Nov 30

Lecture 20: Network Flow (2)

Reading: Sections 7.1, 7.2, and 7.3

Dec 1

Dec 4

Lecture 21: Computational intractability and NP-Completeness

Reading: Skim Sections 8.1 to 8.4

Dec 5

Dec 6

Dec 8

Lecture 22: A peek into distributed algorithms

Dec 9

Assignment 8 due at 9:00pm

Dec 11

Lecture 23: Final poster presentations

Dec 12

Last day of classes

Dec 13

Reading period

Dec 14

Reading period

Dec 15

Final exams

Dec 18

Final exams

Dec 19

Final exams

Dec 20

Final exams

Dec 21

Final Paper Due

Dec 22

Enjoy your break :)

Administrative details of CS231

Course Overview

Prerequisites The prerequisite for CS231 is CS230, and Math 225. Students with significant mathematical experience (writing and understanding proofs), or those who have not taken Math 225 need the permission of the instructor.

Textbook - Very Important!! The textbook for this semester is Regular readings will be assigned from the required text, Algorithm Design, by by Jon Kleinberg and Eva Tardos, 1st edition. It is required that you read the relevant sections every lecture.

Computers No programming will be done as part of this course. You will need your computers, however, to type your assignments. You are expected to use Latex for typesetting all assignments in this course.

Course Directory The CS231 course directory is located at /home/cs231 on tempest. You will be submitting your assignments, in pdf format, in that directory. Any required material, if any, of the course will be placed in the download folder inside the /home/cs231 directory, and you can access it using an ftp program (like Fetch on a Mac).

Course Group Please add yourself to the cs231-fall2017 google group. This group has several purposes. We will use it to make class announcements, such as corrections to assignments and clarifications of material discussed in class. We encourage you to post questions or comments that are of interest to students in the course.
The instructors and TAs will read messages posted in the group on a regular basis and post answers to questions found there. If you know the answer to a classmate's question, feel free to post a reply yourself. The course group is also a good place to find people to join a study group. You should plan on reading group messages on a regular basis.

Course Requirements

Lectures There are two 70-minute lectures each week that will introduce the main content of the course. Lectures are held on Mondays and Thursdays at 9:50-11:00 AM (section 01 in SCI 104), and at 11:10AM-12:20PM (section 02 in SCI 104), and

Supplemental Instruction (SI) Supplemental Instruction (SI) is an academic support program offered for selected Wellesley courses. Our academic SI leaders, Elizabeth is trained and highly experienced in tutoring. She will offer two study sessions each week throughout the semester. During SI sessions they will cover problem set solutions and review important concepts. SI sessions are open to all students enrolled in the course. We highly recommend attending one of the SI sessions every week, as well as reviewing the handouts used in SI sessions.

Final Poster and Paper: During the last few weeks of the semester, teams of 2-3 students work on a short survey paper. After choosing an interesting algorithmic problem, you will first read related literature on the topic, and summarize your findings into a short scientific paper (3-4 pages). Each team will present their work in a poster session during the last class, and will prepare a short paper to be submitted by the last day of exams.

Exams: There will be two in-term, non-collaborative exams that are open book and open notes. The first is in-class and the other one might be take-home. There will be no final exam, as there will be a final poster and paper instead. You are not allowed to collaborate with anyone else on the take-home exams. The dates of the exams are listed on the schedule. Please mark the exam dates in your calendars as they are not flexible.

Grading Policy

Final Grades Your final grade for the course will be computed as a weighted average of several components. The relative weight of each component is shown below:

This course complies with the Wellesley College grading policy. While that policy asks faculty to hold each 100- and 200-level course with 10 or more students to an average of no higher than 3.33, it does not require faculty to grade on a "curve." There is no arbitrary limit on the number of A's, B's, C's etc., and every student will be assigned the grade they earn and deserve according to the grading standards of the college.

Assignments in CS231

There will be weekly assignments in which you will analyze algorithmic problems, using concepts and techniques discussed in class. Assignments are due as indicated on the class schedule. You are required to complete the assignments on your own. You can discuss the problems with the CS231 team members and classmates, but you must write your own solutions.

Peer Review

In each assignment, there is a marked problem(s), which you are allowed to ask a classmate to review for you. If you adopt this peer-review process, then you should follow the following guidelines:


A softcopy of the assignments must be submitted to the /home/cs231/ directory, in pdf format. It is required that you typeset the assignment using Latex. You can find some good tutorials here, and here. And a complete book here. In the event you could not use Latex in one of the assignments, you can scan a hand-written submission. Please make sure that the fonts are clear and readable.

Late Assignment Policy.

No late work will be accepted unless there are extenuating circumstances (e.g., sickness, personal crisis, family problems). In this case you may request an extension before the due date. The softcopy submission will be a dated file. If the formal solutions are distributed before you turn in a late assignment, you are bound by the Honor Code not to examine these solutions.

Course FAQs

Exam questions:

Q: How can we memorize all of these algorithms before the exam?
A: The exam is open book / notes. No need to memorize anything.

Q: How long will the exam be?
A: It's only 70 minutes long. Definitely shorter than the assignments!

Q: How will the questions look like?
A: A mix of things, but it'll never be a type of problem, in which you write the algorithm to solve a new problem, and analyze it.

Assignment questions:

Q: If the problem doesn't ask us to prove the correctness of the algorithm, then we don't have to write a proof. Right?
A: Yes, you don't have to write a proof. However, what if your algorithm was incorrect? Showing us your reasoning would give you partial credit. Just a simple explanation of your reasoning would suffice.

Q: Should I write the algorithm in English? Or do I have to explain the data structures that I am using?
A: If you are not required to show the data structures that you'll be using, then you can just explain the algorithm in English. Remember, if you are asked to analyze the running time complexity of the algorithm, thinking about which data structures to use matter.

Q: Do I have to use the latex template provided?
A: No, you don't, but you have to type it in latex, and submit a pdf. If you don't use the same template, you must at least copy the header of the assignment, to fill in the assignment meta data.