16f-4800: Algorithms

This course meets in EV024 on TueFri at 9.50–11.30.

Goals

This course will present an introduction to the theory and practice of computer algorithms. 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.

Lectures

I will post lecture slides and videos here.

• L1 (Fri 9.9) Intro, Counting people, Analyze Counting, Asymptotic notation
• L2 (Tue 9.13) Karatsuba via tree, Tree, Induction
  • (Thu 9.15) H0 due
• L3 (Fri 9.16) Induction, Masters thm, Substitution,
• L4 (Tue 9.20) Arbitrage, Closest Points,
  • (Thu 9.22) H1 due
• L5 (Fri 9.23) Matrix Mult, Median, FFT
• L6 (Tue 9.27) (Huy’s Lecture, see his slides)
• L7 (Fri 9.30) FFT review, DP intro
• L8 (Tue 10.4) Dynamic Programming, Knapsack, Seam Carving, BillBoard
• L9 (Fri 10.7) (DP) Matrix Chain, Typesetting, Gerrymandering
  • (Sat 10.8) H2 due
• L10 (Tue 10.11) Greedy Algorithms, Scheduling, Huffman
• L11 (Fri 10.14) Midterm 1
• L12 (Tue 10.18) Greedy: Huffman coding, graphs
• L13 (Fri 10.21) MST, Kruskal + Generic, Prim
  • (Sat 10.22) H3 due
• L14,L15 (Tue 10.25, Fri 10.28) Shortest Paths: Dijkstra, Bellman-Ford, All-pairs shortest paths
• L16 (Tue 11.1) Max flow: Ford-Fulkerson, Edmonds-Karp
• L17 (Fri 11.4) Bipartite matching and applications
  • (Sat 11.5) H4 due
• L18 (Tue 11.8) Stable matching
  • (Mon 11.14) H5 due
• L19 (Tue 11.15) Linear Programming and applications
• L20 (Fri 11.18) Midterm 2
• L21 (Tue 11.22) LP, Zero sum games
• L22 (Tue 11.29) Multiplicative Weights
• L23 (Fri 12.2) Randomization, pattern matching
• L24 (Tue 12.6) Streaming Topics
  • (Wed 12.7) H6 due
• Extra: NP Completeness Extra topics on NP Completeness

Homework

• H0 and the H0 template due Wed Sep 15th 5p
• H1 and the H1 src zip due Thu Sep 22th 11.59p
• H2 and the H2 src and clrscode.sty due Thu Oct 6th 11.59p
• H3 and the H3 src due Sat Oct 22th 11.59p
• Midterm practice
• H4 and the H4 src and java template due Sat Nov 5th 11.59p
• H5 and the H5 src and image files aa gold due Mon Nov 14th 11.59p
• H6 and the H6 src due Wed Dec 7th 11.59p

The homework in this class should be submitted through Gradescope. If you have not received an invitation, use the tag 9XN8Y9 to join the class.

Office hours

This course is being run in sync with another section run by Huy at 1.35–3.15. The TAs for this course are Ruiyang, Shreyes, Deepen, and Kushagra. The course also has a Piazza page that you can join here.

1. abhi: Tue 1130-130, WVH350
2. Huy: Tue 330-530, WVH358
3. Ruiyang: Wed 2-4, tbd
4. Shreyes: Wed 4-6
5. Deepen: Thu 1-3
6. Kushagra: Thu 3-5

Policies

1. No late homework will be accepted. We have to start grading as soon as you turn these in, and we need to keep our two sections in sync.

2. 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. In any case, you must write up your solutions, in your own words. Furthermore, if you did collaborate on any problem, you must clearly list all of the collaborators in your submission.

3. Finding solutions to homework problems on the Internet or by asking people who are not enrolled in the class is strictly prohibited.

Textbook

You do not need a textbook for this course, but if you would like to purchase one for review, 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. Every one of my previous advisees highly recommends it for preparing your senior 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 ShareLatex which is a web-based latex system. Using it avoids having to install your own latex system.

Expectations

This is a demanding course that assigns several homeworks, programming exercises, a midterm, and a final. I have run the course several times. Many people loved it, but some people complained about the pace, the workload, and the latency in receiving graded homeworks. TAs grade the homeworks as fast as they can, but this course only has 1 or 2 for 50 students. I encourage group/collaborative work; most people enjoy that aspect. I make myself available during evenings for Google Hangouts office hours, and I also record my lectures so that you can review them offline. That said, this course will ask you to pay attention during class, take notes, review the recordings to catch parts that you did not understand during class.