## 16s-4102: Algorithms

This course meets in Rice Hall Auditorium on Tue Thu at 3.30--4.45.

My office hours are Tue,Thu 1.45-3p in my office which is the 5th floor of Rice, #512. You can also write me to make a different appt if you cannot make that time. Here is the schedule:

- Tue, Thu, 1-3p, Rice 512 (abhi)
- Wed, 1.30-4p, Rice 512 lounge (Saba)
- Thu 11-1, Rice 512 lounge (Paul)
- Thu 5-7p, Rice 512 lounge (Chunkun)
- Fri, 2-4p, Rice 430 (Frank)

## Homeworks

- Final [tex],due Wed 5/11.
- H8 [tex],due Wed 5/4. Extra credit: Extra [tex]
- H7
- H6
- H5
- Midterm
- H4
- H3
- H2
- H1
- H0

I've posted the caricatures you produced for the first assignment.

## Recent Lecture Videos/Slides

- L27: Reductions & Data structures
- L26: NP and reductions
- L25: LP and reductions
- L24: Linear Programming and applications
- L23: Stable matching algorithm
- L22: Edmonds-Karp Max flow, Bipartite matching and applications
- L21: Max flow, Ford-Fulkerson
- L20: All-pairs shortest paths, Maxflow
- L19: Shortest Paths, Bellman-Ford, All-pairs shortest paths
- L18: Shortest Paths, Dijkstra, Breadth-first search
- L17: Greedy: MST, Prim Algorithms
- L16: Greedy: MST, Kruskal + Generic
- L15: Greedy Algorithms
- L14: Greedy Algorithms
- L13: Review
- L12: (DP) Gerrymandering
- L11: (DP) Typesetting
- L10: (DP) Matrix Chain, Seam Carving
- L9: Dynamic Programming Intro
- L8: FFT, Median
- L7: Matrix mult, FFT
- L6: Closest Points, Arbitrage
- L5: Masters Theorem, Substitution
- L4: Induction, Masters thm
- L3: Tree, Induction
- L2: Recurrences
- L1: Intro

## News

Tweets by @cs4102## 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, 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, a take-home midterm, and a take-home exam. 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 150 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.

## Old Lectures

To help you decide whether to take the course, here are the annotated lecture notes from 13f (not all slides covered in each lecture); 16s will closely follow the schedule, but there will be a few additional/different topics.- L1: Intro
- L2: Divide & Conquere
- L3: Mult, Merge
- L4: Recurrences, Master's Thm
- L5: Master's Thm, Closest Pair
- L6: Closest Pair, Matrix, Median
- L7: Median, Arbitrage, FFT
- L8: FFT, Dynamic Prog
- L9: Log Cutter, Matrix chains
- L10: Matrix Chains, Typesetting
- L11: Typesetting, seam carving
- L12: Seams, Gerrymandering
- L13: Greedy
- L14: Caching, Huffman
- L15: Huffman Coding
- L16: Min spanning tree
- L17: MST, Shortest paths
- L18: Shortest paths, Bellman-Ford
- L19: All pairs
- L20: Max flow
- L21: (Guest) Parallel Merge
- L22: Max flow
- L23: (Guest)
- L24: Max flow
- L25: Reductions
- L26: Stable Matching
- L27: Randomization
- L28: Crypto, Review