# Fall 2018 **CS231**

This is a course about **algorithms**; their design and analysis

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.

Labor Day: no classes

Lecture 3: Back to the Stable Matching problem

(notes)

Assignment 1 due in class

Part II - Graphs

Lecture 5: Intro and representation

(slides)

Assignment 2 due in class

Exam 1

Fall Break: no classes

Fall Break: no classes

Lecture 10: More on Scheduling

(Notes)

Assignment 4 due in class

Part IV - Divide and Conquer

Lecture 14: Merge Sort

(Slides)

Assignment 6 due in class

Exam 2

Part V - Dynamic Programming

Lecture 17: Basics and Principles

(Slides)

Lecture 19: Back to Graphs :)

(Slides)

Assignment 8 due in class

Thanksgiving Break

Thanksgiving Break

Thanksgiving Break

Part VI - Invited Lectures

Lecture 21: Network Flow

**Reading: ** Skim Sections 7.1 to 7.3

Lecture 22: Computational intractability and NP-Completeness

**Reading: ** Skim Sections 8.1 to 8.4

Assignment 9 due in class

Final Presentations

Final Presentations

Reading period

Reading period

Final exams

Final exams

Final exams

Final exams

Enjoy your break :)

** 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**
You will be added to the cs231-fall2018 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.

**Course Piazza Page**
You will also receive an invitation to join the course Piazza page.
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.

**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 1:30-2:40 PM (section 01 in E111), and
at 2:50-4:00PM (section 02 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 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.

**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: 35%
- Final Presentation and Paper: 20%
- Exam 1 : 10%
- Exam 2 : 15%
- Exam 3 : 15%
- Class Participation: 5%
- Total: 100%

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

- You must indicate clearly on your assignment cover page who reviewed your work.
- In return for your classmate reviewing your problem(s), you must review their corresponding problem(s) as well.
- You are allowed to edit your solutions according to the feedback you get from the review.
- Submit both your solutions, before and after the review.

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.

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.