# Fall 2021 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.

## CS231 Fall 2021 schedule

Note that all readings are required to be done before class, except for the first lecture :)
Date Lecture topic Textbook reading In-class notes More resources
Sep 09 Introduction Course webpage Slides Tell me more about you!
Part I: Basics
Sep 13 Sorting and Analysis Look up old CS230 slides Lecture Stubs
Sep 16 Asymptotic order of growth Textbook Sections 2.1 and 2.2 Slides
Sep 20 Stable Matching problem Textbook Chapter 1
Assignment 1 - due Wednesday Sep22 at 11:59pm
You can find the latex template here
Sep 23 More on the stable matching problem Textbook Chapter 1
Part II: Graph algorithms
Sep 27 Graph representation Textbook Section 3.1
• Slides
• Graph representation notes
Video on graph representation
Sep 30 Graph traversal Textbook Section 3.2 and 3.3
• Slides
DFS animation vs. BFS animation
Oct 4 Directed graphs Textbook Section 3.6
• Slides
• Graph traversal analysis and theorems
Implentation of Topological Sorting
Assignment 2 - due Wednesday Oct 6th at 11:59pm
You can find the latex template here
Oct 7 Directed graphs - continued Textbook Section 3.6
• Notes on DAGs
Oct 7 to
Oct 13
Exam 1
Virtual and PYOT (Pick Your Own Time)
Oct 11 Fall break
Part III: Greedy algorithms
Oct 14 Interval Scheduling problem Textbook Section 4.1
Watch video with title: Greedy1
Oct 18 More on Interval Scheduling Textbook Section 4.1
Watch videos with titles: Greedy2 and Greedy3
Oct 21 Another Scheduling problem Textbook Section 4.2
Watch video with title: Greedy4
Oct 25 Shortest Path problem Textbook Section 4.4
Watch video with title: Greedy5
Oct 28 Minimum spanning trees Textbook Section 4.5
Watch video with title: Greedy6
Part IV: Divide and Conquer algorithms
Nov 1 Merge Sort and Quick Sort Textbook Sections 5.1 and 5.2 Nice tutorial
Nov 4 Recurrences Textbook Section 5.2
Nov 8 More on Divide and Conquer TBD
Nov 8 to
Nov10
Exam 2
Virtual and PYOT (Pick Your Own Time)
Part V: Dynamic Programming
Nov 11 Dynamic Programming - Intro Textbook Sections 6.1 and 6.2
Watch video with title: DP1
Nov 15 Yet another scheduling problem Textbook Sections 6.1 and 6.2
Watch video with title: DP2
Nov 18 The Knapsack problem Textbook Section 6.4
Watch video with title: DP3
Nov 22 Weighted shortest path Textbook Section 6.8
Watch video with title: DP4
Nov 25 Thanksgiving break
Nov 29 Network Flow Problem TBD
Dec 2 Application of Network Flow TBD
Dec 6 Review lecture Watch videos with titles: DP1-DP4
Dec 9 Exam 3
Virtual and PYOT (Pick Your Own Time)
Dec 13 Preparing for poster session No reading

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

Assignment Submission This semester we will be using GradeScope for all CS231 assignments submissions. 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 Expectations

Lectures Per College guidelines, all lectures will be in-person. There are two 75-minute lectures each week, during which we will discuss the main content of the course.
Lectures are held on Mondays and Thursdays at 9:55 AM - 11:10 AM in L047.

Support All support in the course will be held virtually, through Zoom chats, Piazza posts and discussions, and emails.

Christine's Office Hours All office hours will be held via Zoom. There will be two types of office hours, open join-in and one-on-one office hours.
* Open join-in office hours will be held on Thursdays from 1PM to 2PM.
* As for the one-on-one office hours, 15 minute slots will be available for your to sign up on the course's support calendar. Once you sign up, a Zoom meeting will be automatically scheduled.
* Of course, if none of these times work for you, feel free to email me, and I will do my best to schedule another time with you.

Drop-in Hours All drop-in hours will also be virtual. The slots will be available on the course's support calendar, and you can request an appointment directly by choosing a time-slot.

Exams: There will be three virtual, 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 Presentations and Paper: During the last few weeks of the semester, teams of 2 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 scientific paper (min 6 pages, max 10 pages).
Each team will present their work in a final presentation during the last class (or reading period), and will prepare a paper to be submitted by the last day of exams.

### Assignments in CS231

There will be bi-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.
Collaboration on assignments 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 individually.

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.

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 computer. 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. You have a 24-hour extension on any and all assignments. You don't need to ask for permission if you need to take advantage of that extension. However, beyond this automatic extension, no late work will be accepted unless it has been discussed with the instructor first, except for extenuating circumstances (e.g., sickness, personal crisis, family problems), which can be discussed after the fact.

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

This course complies with the 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.

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