16f4800: 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, BellmanFord, Allpairs shortest paths
 L16 (Tue 11.1) Max flow: FordFulkerson, EdmondsKarp
 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.
 abhi: Tue 1130130, WVH350
 Huy: Tue 330530, WVH358
 Ruiyang: Wed 24, tbd
 Shreyes: Wed 46
 Deepen: Thu 13
 Kushagra: Thu 35
Policies

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.

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.

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:
 CLRS: “Introduction to Algorithms”
 Kleinberg+Tardos, “Algorithm Design”
In addition, I recommend the following Coursera links for you to review between and after my lectures:
 Tim Roughgarden’s open course Alg Part I
 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, opensource 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 webbased 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.