22s-5800: Introduction to Algorithms

Waitlist

Note: if you are on the waitlist, please begin coming to lecture under the assumption that you will get into the course. As people drop the class, more slots become available. Also: I have no control over the waitlist or registration, but several people who have reached out to me who were on the waitlist are now registered officially.

Goals

Welcome to CS5800 Spring 2022. This course will present an introduction to the theory and practice of computer algorithms. It will run slightly faster than the undergraduate CS4800, but cover less material than the CS7800 version.

In the first part of the course, we study the main driving principle behind classical algorithms: namely, that to solve a problem, divide it into smaller instances of the same problem, solve the smaller ones, and combine them to solve the original instances. This idea is explicit in the divide and conquer class of algorithms, which include sorting, finding statistics like the median, multiplying numbers and matricies, computing transforms, and finding closest pairs of points.

We then extend this idea with the concept of memoization resulting in the class of dynamic programming algorithms which are prolific and appear on many standard interview questions. We then discuss a very special case of greedy algorithms in which local decisions can lead to optimal solutions.

In the second half of the course, we apply these techniques to solve basic graph problems such as minimum spanning trees and shortest paths, finding maximum flows and minimum cuts, solving bipartite matching problems, and finding stable matchings. Finally, we consider more recent algorithmic techniques such as duality, linear programming, optimization, approximation, and streaming algorithms.

First steps

• You have a few actions items before class:
  1. Enroll in the course Piazza to get answers to your questions. Note: make sure you are in my section’s Piazza.
  2. Enroll in gradescope using the registration code from Canvas or the first day of class.
  3. Review the primer on logs.

Course Basics

• Instructors: abhi shelat

• Times: TF 9.50, MR 11.45, Churchill Hall 101.

• We have 14 TAs for the course!

  • TAs:
  • The best way to engage the course staff is via piazza and office hours.

• Office hours:

  • Zoom links will be posted in Canvas and piazza.

• COVID protocols: I will be posting videos on the topics that we cover, so if you are sick, you should stay home and watch the videos to catch up when you recover. Let the course staff know and the deadlines for your homework will be adjusted. Do your best to help your friends and colleagues in the class make it through, especially if they fall ill.

Textbook

You do not need a textbook for this course, but if you would like to purchase one to supplement the lecture notes and videos, I recommend the following two books:

1. CLRS: “Introduction to Algorithms”
2. Kleinberg+Tardos, “Algorithm Design”

In addition, I recommend the following Coursera links for you to review between and after my lectures:

1. Tim Roughgarden’s open course Alg Part I
2. Wayne+Sedgewick’s course Alg Design Part I

LaTeX

You should prepare your homework solutions using LaTeX, and submit PDFs to the course submission site. LaTeX is a free, open-source scientific document preparation system; most CS technical publications are prepared using this tool. My previous students highly recommend it for preparing your thesis.

TexShop is a great tex editor for the Mac platform. For windows, I have heard good feedback about TexNiCenter.

The Not so short intro to latex is a good reference. This is another tutorial for latex from a user group.

You may also consider using Overleaf which is a web-based latex system. Using it avoids having to install your own latex system.

Course Schedule

Grading

Your final grade is computed as a weighted sum of your homework scores, your in-class quiz scores, and your exam scores. Each assignment will include a breakdown of how it will be graded. Some projects may include extra credit components that can boost your grade above the maximum score. There will be 10 homeworks, 1 midterm, and 1 final. The homework will count for 60 percent, the exams will count for 15 percent each, and the quizzes will count for 10 percent.

Homework

There will be ten assignments throughout the semester. Homework must be submitted before 11:59:59pm on the specified date. You can submit as many times as you like through gradescope. Your last commit timestamp on your files will be used to determine lateness.

If required, any programming needed for projects can be done in a language of your choice. The only universal requirement is that your projects must compile and run on an unmodified Khoury College Linux machine. Notice the stress on unmodified: if you’re relying on libraries or tools that are only available in your home directory, then we will not be able to run your code and you will fail the assignment. You are welcome to develop and test code on your home machines, but in the end everything needs to work on the Khoury College Linux machines. If you have any questions about the use of particular languages or libraries, post them to Piazza.

Exams

The midterm exam will be a take-home exam due on Wednesday March 2nd at 11:59p.

Quizzes

Throughout the semester, there will be several in-class quizzes. These quizzes will be brief; they are designed to be completed in 15 minutes or less. They are not meant to cause grief, and the questions will be straightforward. The goals of the quizzes are to encourage careful study of the lecture material.

Quizes will be posted and answered through Gradescope; you will have roughly 1 day after the time a quiz is announced to submit your answer. If you take this course asynchronously, it is your responsibility to ensure that you submit these quizzes on time.

Late Policy

This class has a generous late policy.

We recognize that there may be weeks where you won’t be able to get your assignments completed on time. Keeping this in mind, we’re allowing you to hand in two homework assignments up to 48 hours late. This means you may hand in those assignments by midnight on Friday without incurring any penalty. You may use these late passes at any point during the semester at your discretion. Beyond those two passes, there will be a 5% penalty for any assignments handed in late.

If emergency arises (illness, death, personal/family emergency) and you need further support on submitting an assignment please reach out to the course staff on Piazza using a private message.

This added flexibility will help everyone during a stressful and odd year; however, do not become too reliant on these automatic extensions. Do your best to satisfy the posted deadlines. The course staff may not be able to help you on older assignments. Thus, we encourage you to stay up to date with the course.

DRC Accommodations

Students who have disabilities who wish to receive academic services and/or accommodations should visit the Disability Resource Center at 20 Dodge Hall or call (617) 373-2675. If you have already done so, please provide your letter from the DRC to Kayla McLaughlin early in the semester so that we can arrange those accommodations.

Cheating Policy

1. Collaborating with other students in the class on homework problems is encouraged, though we urge you to first attempt working out all of the problems by yourself. It’s ok to ask your peers about the concepts, algorithms, or approaches needed to do the assignments. We encourage you to do so; both giving and taking advice will help you to learn.

2. However, you must write up, prepare, submit your solutions, in your own words. Looking at or copying code or homework solutions from other people or the Web is strictly prohibited. In particular, looking at other solutions (e.g., from other groups or students who previously took the course) is a direct violation. Projects must be entirely the work of the students turning them in, i.e. you and your group members. If you have any questions about using a particular resource, ask the course staff or post a question to the class forum.
   Example: If you have copied and pasted any text from someone else, you have violated this policy even if the two of you were working together on an assignment. Type your own keystrokes that lead you to a solution; do not copy commands that you do not understand or that you were given to you by someone else.

3. All students are subject to the Northeastern University’s Academic Integrity Policy. Per Khoury College policy, all cases of suspected plagiarism or other academic dishonesty must be referred to the Office of Student Conduct and Conflict Resolution (OSCCR). This may result is deferred suspension, suspension, or expulsion from the university.

4. If you violate this policy, you receive a 0. There will be very little leeway on enforcement of this policy.