Spring 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


CS231 Spring 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

Jan 28

Lecture 1: Introduction

Section 1.1

Assignment 0 out

Jan 29

Jan 30

Jan 31

Part I - Basics

Lecture 2: Stable Matching Problem

Section 1.1

Assignment 0 due
Assignment 1 out

Feb 1

Feb 4

Lecture 3: Stable Matching Problem

Sections 1.1 and 2.3

Feb 5

Feb 6

Feb 7

Lecture 4: Asymptotic Order of Growth

Sections 2.1 and 2.2

Assignment 1 due
Assignment 2 out

Feb 8

Feb 11

Part II - Graphs

Lecture 5: Intro and Representation

Sections 3.1 and 3.2

Feb 12

Feb 13

Feb 14

Lecture 6: Graph Traversals

Sections 3.2 and 3.3

Assignment 2 due
Assignment 3 out

Feb 15

Feb 18

Presidents' Day

Feb 19

Lecture 7: Directed Graphs

Sections 3.5 and 3.6

Feb 20

Feb 21

Part III - Greedy Algorithms

Lecture 8: Introduction

Section 4.1

Assignment 3 due

Feb 22

Feb 25

Exam 1

Feb 26

Feb 27

Feb 28

Lecture 9: Interval Scheduling

Sections 4.1 and 4.2

Assignment 4 out

Mar 1

Mar 4

No class (snow day)

Mar 5

Mar 6

Mar 7

Lecture 10: Interval Scheduling

Section 4.1 and 4.2

Mar 8

Mar 12

Mar 13

Mar 14

Lecture 12: Minimum Spanning Tree

Handout

Sections 4.5

Mar 15

Mar 19

Mar 20

Mar 21

Spring Break

Mar 22

Spring Break

Mar 25

Spring Break

Mar 26

Spring Break

Mar 27

Spring Break

Mar 28

Spring Break

Mar 29

Spring Break

Apr 1

Part IV - Divide and Conquer

Lecture 14: Mergesort and Counting Inversions

Section 5.1 and 5.2

Apr 2

Apr 3

Apr 4

Lecture 15: Divide and Conquer
Midterm Review

Sections 5.2 and 5.3

Assignment 6 due

Apr 5

Apr 8

Exam 2

Apr 9

Apr 10

Apr 11

Part V - Dynamic Programming

Lecture 16: Basics and Principles

Sections 6.1 and 6.2

Assignment 7 out

Apr 12

Apr 15

Patriots' Day

Phase 1: Topic

Apr 16

Apr 17

Apr 19

Apr 22

Lecture 18: Shortest Path (Bellman-Ford)

Sections 6.4 and 6.8

Phase 2: Related Work

Apr 23

Apr 24

Apr 25

Lecture 19: Network Flow

Sections 7.1 and 7.2

Assignment 8 due on April 27th

Apr 26

Apr 29

Lecture 20: Network Flow and Computational intractability

Sections 8.1 and 8.3

Apr 30

May 1

Ruhlman Conference

May 2

Exam 3

May 3

May 6

Final Presentations

Phase 3.1: Presentation

May 7

May 8

May 9

Final Presentations

May 13

Reading Period

May 14

Reading Period

May 15

Final Exams

May 16

Final Exams

May 17

Final Exams

May 20

Final Exams

May 21

Final Exams

Phase 4: Final Paper

May 22

May 23

May 24

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.

Course Group The Google Group is CS-231-01-SP19. You should make sure that you are subscribed to this group. Important course announcements will be posted to the group, such as corrections to assignments and clarifications of material discussed in class.


Course Requirements

Lectures There are two 75-minute lectures each week that will introduce the main content of the course. Lectures are held on Mondays and Thursdays at 9:55-11:10 AM in SCI 364.

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 multiple study sections each week 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 two classes, and will prepare a short paper to be submitted by the last day of exams.

Exams: There will be three in-term, 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:


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.

Submission

Submissions and grading will be handled through Gradescope. You should sign up on Gradescope using the course code: 9PYWJN. All assignments must be typeset using LaTeX and submitted in PDF format. LaTeX is the most widely used tool to professionally typeset mathematical content, proofs, conference and journal papers, etc.

COLLABORATION POLICY

You are encouraged to talk with CS231 team members and classmates about the course and to form study groups. Unless otherwise instructed, feel free to discuss problem sets with classmates and exchange ideas about how to solve them.

You are encouraged to work in teams with other students. The team members can work together closely but each student must write and submit their own solution. You must mention the names of your collaborator(s) in your assignment.

While open exchange of ideas is encouraged, there is a thin line between collaboration and plagiarism. Please note that you must compose your own solution to each assignment. Furthermore, you should never look at another student's solutions. For example, it is OK to borrow ideas from the textbook, from materials discussed in class, and from other sources as long as you give proper credit. However it is unacceptable and constitutes a violation of the Honor Code (1) to write a solution together and turn in two copies of the same solution, (2) to copy a solution written by your classmates, (3) to read another student's or team's solution or (4) to view assignments, exams and solutions from previous terms of CS231.

In keeping with the standards of the scientific community, you must give credit where credit is due. If you use an idea that was developed by (or jointly with) others, please reference them in your work. It is unacceptable for students to work together but not to acknowledge each other in their write-ups.

LATE ASSIGNMENT POLICY

You are allowed four (4) late passes of 24 hours each, no questions asked, and you can use more than one late pass per assignment. It is required that you communicate that you are using your late pass by the due date of the assignment by email. 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.

SPECIAL ACCOMODATIONS

If you have a disability or condition, either long-term or temporary, and need reasonable academic adjustments in this course, please contact Disability Services to get a letter outlining your accommodation needs, and submit that letter to your instructor. 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 the instructor for your section as soon as possible. If you are unsure but suspect you may have an undocumented need for accommodations, you are encouraged to contact Disability Services. They can provide assistance including screening and referral for assessments. Disability Services can be reached at disabilityservices@wellesley.edu, at 781-283-2434, by scheduling an appointment online at their website, or by visiting their office: 3rd floor of Clapp Library (rooms 316 & 315).