# Spring 2019 **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.

Presidents' Day

Exam 1

No class (snow day)

Spring Break

Spring Break

Spring Break

Spring Break

Spring Break

Spring Break

Spring Break

Part IV - Divide and Conquer

Lecture 14: Mergesort and Counting Inversions

**Section 5.1 and 5.2 **

Exam 2

Ruhlman Conference

Exam 3

Final Presentations

Reading Period

Reading Period

Final Exams

Final Exams

Final Exams

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

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

**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: 30%
- Final Presentation and Paper: 20%
- Exam 1 : 15%
- Exam 2 : 15%
- Exam 3 : 20%
- Total: 100%

- Here are some useful resources to learn LaTeX: Learn LaTeX in 30 minutes, Doing your HW in LaTex, LaTeX Cheat Sheet, A Beginner's Guide to LaTeX , The Not so Short Introduction to LaTeX2e . LaTex Stack Exchange has answers to many common LaTeX issues.
- To help start you up with LaTeX, a template for solutions will be provided on Overleaf, a free online LaTeX platform, similar to Share LaTeX.

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.