Fall 2019 CS231

This is a course about algorithms; their design and 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 2019 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.

Monday

Tuesday

Wednesday

Thursday

Friday

Sep 2

Labor Day: no classes

Sep 3

Sep 4

Sep 5

Lecture 1: Introduction

Sep 6

Sep 9

Part I - Basics

Lecture 2: More on data structures

Reading: Pages 9 to 20 in this and all of that

Sep 10

Sep 11

Sep 12

Lecture 3: Priority Queues

Reading: Section 2.5

Sep 13

Sep 16

Lecture 4: Asymptotic Order of Growth

Reading: Sections 2.1 and 2.2

Sep 17

Sep 18

Sep 19

Lecture 5: Stable matching

Reading: Section 1.1 and 2.3

Assignment 1 due at 11:59PM (via Gradescope)

Sep 20

Sep 23

Lecture 6: Stable matching (2)

Reading: Section 1.1 and 2.3

Sep 24

Sep 25

Sep 26

Part II - Graphs

Lecture 7: Graph representation

Reading: Section 3.1

Assignment 2 due at 11:59PM (via Gradescope)

Sep 27

Sep 30

Lecture 8: Graph Traversal

Reading: Sections 3.2 and 3.3

Oct 1

Oct 2

Oct 3

Lecture 9: Back to complexity analysis

Reading: Sections 3.2 and 3.3

Assignment 3 is due at 11:59pm

Oct 4

Oct 7

Lecture 10: Directed graphs Reading: Sections 3.5 and 3.6

Oct 8

Oct 9

Oct 10

Part III - Greedy Algorithms

Lecture 11: Interval scheduling (1)

Reading: Section 4.1

Assignment 4 due at 11:59pm

Oct 11

Oct 14

Fall Break

Oct 15

Fall Break

Oct 16

Oct 17

Lecture 12: More on scheduling

Reading: Sections 4.1 and 4.2

Oct 18

Oct 21

Exam 1
In class

Oct 22

Oct 23

Oct 24

Lecture 13: Scheduling to minimize lateness

Reading: Section 4.2

Oct 25

Oct 28

Lecture 14: Graphs, again!

Reading: Section

Oct 29

Oct 30

Oct 31

Part IV - Divide and Conquer

Lecture 15: Merge Sort

Assignment 5 due

Nov 1

Nov 4

Lecture 16: Counting Inversions

Reading: Section

Nov 5

Nov 6

Nov 7

Lecture 17:

Reading: Sections 6.1 and 6.2

Assignment 6 due

Nov 8

Nov 11

Part V - Dynamic Programming

Lecture 18: Basics and Principles

Reading: Sections 6.1 and 6.2

Nov 12

Nov 13

Nov 14

Lecture 19: Scheduling, again!

Reading: Sections

Assignment 7 due

Nov 15

Nov 18

Lecture 20: The Knapsack problem

Reading: Sections

Nov 19

Nov 20

Nov 21

Lecture 21: Graphs, again!

Reading: Sections

Assignment 8 due

Nov 22

Nov 25

Exam 2

Nov 26

Nov 27

Thankgiving break

Nov 28

Thankgiving break

Nov 29

Thankgiving break

Dec 2

Part VI - Invited Lectures

Lecture 22: Network Flow

Dec 3

Dec 4

Dec 5

Lecture 23: Computational intractability and NP-Completeness

Dec 6

Dec 9

Final Presentations

Dec 10

Dec 11

Reading period

Dec 12

Reading period

Dec 13

Reading period

Dec 16

Final exams

Dec 17

Final exams

Dec 18

Final exams

Dec 19

Final exams

Dec 20

Final Paper due

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 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 before 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.

Assignment Submission This semester we will be using GradeScope for all all CS231 assignments submissions. Assignments will be submitted weekly, in pdf format, to their corresponding directories. You will receive an email with more details after the first class.

Course Communication

We will be using Piazza for all course communications, and student discussions. You will also receive an invitation to join the course Piazza page after the first 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 page 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 Pizza page is also a good place to find people to join a study group. You should plan on reading group meetings 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 11:20 AM - 12:35 PM in E111.

Discussion Sections Similar to Supplemental Instruction (SI), discussion sections is a support program offered for selected Wellesley courses. Our discussion leaders are trained and highly experienced in tutoring. They will offer study sections throughout the semester. During discussion sections, they will cover problem set solutions and review important concepts. Discussion sections are open to all students enrolled in the course. We highly recommend attending at least one of these sections every week, as well as reviewing the handouts used in them.

Final Presentations and Paper: During the last few weeks of the semester, teams of 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 (5 pages). Each team will present their work in a final presentation 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-class, non-collaborative exams that are open book and open notes. There will be no final exam, as there will be a final presentation and paper instead. 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 **NEW** Wellesley College grading policy. 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.

Proof Modules (Problems)

In some assignments, you will find a problem marked with [Proof-problem] For these problems, you need to carefully formulate and write your arguments for the correctness of your solutions. For these proof problems, you need to submit on the same day as the assignment, but in a separate sheet. T Your proof will be graded through the weekend, and you’ll get feedback on it by Monday. Based on your grade, you have a chance to resubmit it, if you want.
Grading:
* If the proof is correct and complete, you get full points (1)
* If edits need to be made, you get (0.5), and you can resubmit the following Thursday.
* If many edits need to be made, you get (0), and you can resubmit the following Thursday.

Peer Review

In some assignments, 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:

Submission

A softcopy of the assignments must be submitted to GradeScope 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.

Working with Latex

You can work with Latex editors locally on your computers. There are many editors, and I personally use Atom since it works for both Windows and Latex. In any case, you must download the Tex libraries first. For Windows, you need the Miktex library, and for Mac OS, you need the MacTex library. If you don't want to go through all of that, you can always use Overleaf , which is an online editor and compiler, with some nice tutorials as well.

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.
Late passes will be distributed in the second week of class. They allow you to get 24-hour extensions on any assignment.

Special Accommodations

If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, please contact Accessibility and Disability Resources (ADR) to get a letter outlining your accommodation needs, and submit that letter to me. You should request accommodations as early as possible in the semester, or before the semester begins, since some situations can require significant time for review and accommodation design. If you need immediate accommodations, please arrange to meet with me as soon as possible. If you are unsure but suspect you may have an undocumented need for accommodations, you are encouraged to contact (ADR). They can provide assistance including screening and referral for assessments.

Disability Services can be reached at accessibility@wellesley.edu, at 781-283-2434, by scheduling an appointment online at their website, https://www.wellesley.edu/adr or by visiting their offices on the 3rd floor of Clapp Library, rooms 316 and 315.


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: Yes, you do.