After (or sometimes before) lectures, we will write a blurb on what we did and provide references
to where the material is from. Sometimes we may provide pdfs of rough notes.

Lecture 1 (Aug 11): Introduction, Incremental Design.
In the first lecture, we began with discussions on basic principles of algorithms. The notions and concepts that act as basic building blocks for the area were discussed. We recalled wellknown principles such as abstraction, computational problem, ADT, input size, unit cost criteria and associate instruction counts, worstcase and averagecase complexity, and touched upon micro and macro analysis of algorithms. Then we turned our attention to design paradigms and started with incremental design. The solutions based on incremental design typically consists of several stages where in each stage some unprocessed part of the input is picked for processing and the partial solution obtained in the previous stage is extended to obtain the partial solution corresponding to bigger sub instance. In its simplest form, we may express a typical stage of an incremental solution as building a partial solution PS_{i} for the part of the input, say, {a_{1},a_{2},...,a_{i}} from the partial solution PS_{i1} and a_{i}. We considered the infinite wall problem to explain different flavours of incremental strategies.

Lecture 2 (Aug 13): Incremental and Decremental Design.
We discussed examples where it's more efficient to process input in a nonstraightforward order, such as heap insertion and an O(n log n) algorithm for computing the convex hull. We also discussed the gossipmonger's problem as another example where the incremental design paradigm yields an efficient algorithm; the lower bound was left as a challenge. Then, we moved on to "decremental design", where we talked about celebrity finding and dosa flipping. Go to Piazza for following up on these topics.

Lecture 3 (Aug 18): Divideandconquer and Pruning. (Rough notes)
Divideandconquer is another basic algorithmic paradigm widely used. The input is divided into several parts; for each, the problem (or a stronger variant of it) is solved recursively; finally, the solutions for the subparts are merged together. Pruning is a special case where there's only subproblem in each recursive step. We discussed binary search and the medianofmedians algorithm as examples for pruning. For divideandconquer, we saw Karatsuba and Strassen for integer and matrix multiplication respectively. We then moved to on to discuss the binary search tree as a dictionary data structure. CLRS describes RedBlack trees that selfbalance after each insertion/deletion; in class, we described AA trees (some excellent notes
here).

Lecture 4 (Aug 20): Divideandconquer.

Lecture 5 (Aug 25): Randomized Algorithms: An introduction. (Rough notes)
It's an amazing fact that giving algorithms the ability to toss a few unbiased coins can give them computational power that we don't know how to obtain deterministically (i.e., without randomness). Randomized algorithms come ostensibly in two flavours: (i) Monte Carlo algorithms which always run in a bounded amount of time but have some probability of giving incorrect answers, and (ii) Las Vegas algorithms which always give correct answers but whose running time is a random quantity. In this lecture, we described two simple algorithms of the Las Vegas type. First, we looked at a randomized algorithm for computing recursive majority on
3^{h} bits that queries at most
(8/3)^{h} input bits in expectation; any deterministic algorithm must examine all
3^{h} bits. Next, we described skip lists, a beautiful dictionary data structure that achieves
O(log
n) expected time for searches, insertions and deletions, without any of the intricate case analysis involved in redblack or AVL trees. A very nice discussion of skip lists is in
Erickson's lecture notes.

Lecture 6 (Aug 27): Concentration and the Chernoff bound.
We saw the method of randomized attrition and derived expected and high confidence bounds using the Chernoff bound.

Lecture 7 (Sep 1): Analyzing Las Vegas and Monte Carlo algorithms. (Rough notes)
We completed the analysis of skip lists started in Lecture 5. Then, we discussed a randomized selection algorithm where the pivot is chosen uniformly at random. A more detailed analysis than the one we gave in class can be found in CLRS. We then moved on to Monte Carlo algorithms and looked at a couple of important examples: polynomial identity testing and Karger's algorithm.

Lecture 8 (Sep 3): More Monte Carlo algorithms
We discussed Monte Carlo methods in detail and explained the randomized primality test.

Lecture 9 (Sep 8): Reliability analysis.

The hash table is a dictionary data structure that supports constant time searches, insertions and deletions, on average. We talked about heuristic choices for hash functions as well as universal hash functions which satisfy the simple uniform hashing assumption. Finally, we described the elegant KarpRabin string matching algorithm as an application of hashing.

Lecture 11 (Sep 15): Dynamic programming.
Dynamic programming is a basic algorithmic paradigm that often manages to make an exponential time recursive solution be polynomial. Our viewpoint, as in the book by Dasgupta et al, is that DP is about arranging subproblems in such a way that their dependencies form a directed acyclic graph and then solving the subproblems according to a linearization of the DAG. We illustrated the technique through several problems: the
nth Fibonacci number, longest increasing subsequence of an array, edit distance, maximum independent set in a tree, and the FloydWarshall allpairs shortest paths (APSP) problem. The currentbest APSP algorithm, which uses a lot more sophistication, is from 2014 by Ryan Williams;
here are some lecture notes sketching this.

Continuing along the lines of the APSP algorithm discussed in the last lecture, we moved to another classic graphtheoretic optimization problem: finding minimum spanning trees in weighted undirected graphs. We discussed a metaalgorithm that underlies most MST algorithms. Then, we showed that three instantiations of it are Boruvka, Prim, and Kruskal. Our presentation was drawn from these
excellent lecture notes by Erickson.

We moved to another classic problem on graphs: computing shortest paths starting from a given source. We described Dijkstra's algorithm which assumes that there are no negativeweight edges. Then, we also talked about the BellmanFord algorithm for the general case when there are negative edges. Finally, we discussed finding shortest simple paths on undirected graphs with negative edges and showed a reduction from this problem to that of finding minimum weight perfect matchings in nonbipartite graphs.

Lecture 14 (Sep 29): Amortized Analysis (Introduction)
We started our discussion on amortized analysis. We defined an Abstract Datatype as a mathematical model together with a set of operations defined on it, a Data Structure as an organization of the elements of such a mathematical model such that operations can be efficiently implemented and finally a Data Type as a mathematical model with operations, but with respect to a problem domain. The dictionary ADT was introduced with the operations insert, delete and search.
Amortization as an alternative to complex algorithms: looking for relaxation in constraints while not compromising on efficiency. Introduction to the accounting and potential function methods of amortized analysis. Case study: a FIFO queue with the operations push(x, S) and multipop(k, S).

Lecture 15 (Sep 30): Priority Queue (Leftist Heap), Amortized Analysis (Skew Heaps)
Case studies: number of bit flips required to count from 0 to n, number of operations required to implement a dynamic array such as C++ std::vector that doubles in size when required.
Introduction to the Priority Queue ADT with operations insert(x, S), delete_min(S) and meld(S1, S2). Implementations: using an array, a sorted list and a binary heap and their respective complexity measures. Heriditary property of heaps. Extended binary tree, leftist tree and leftist heap, their memory representations. Implementation of Priority Queue as a leftist heap. Description of operations in terms of meld. Amortized alternative: skew heaps, which use a BST without extensive bookkeeping.

Lecture 16 (Oct 8): Priority Queue (Binomial Heap), Amortized Analysis (Fibonacci Heaps)
Introduction of a new operation to the ADT: decrease_key(). Comparison of Priority Queue implementations: leftist heap, binary heap, binomial heap. Introduction to Binomial Trees and their memory representation. Description of operations: insert(x, S), delete_min(S), decrease_key(x, y, S), meld(S1, S2). Time vs memory: implementation tradeoffs. Complexity analysis.
Lazy and busy computation. Amortized alternative: Fibonacci Heaps — as a forest of unrestricted trees. Memory representation. Tree merging. Description of operations: insert(x, S), meld(S1, S2) and delete_min(S). Marked and unmarked nodes, description of decrease_key(x, y, S). Amortized analysis: accounting and potential function methods.

Lecture 17 (Oct 15): Lower Bound Theory
Problem cost as a function of allowed primitives. Difference between the lower bound of computing the sum of a geometric series when:
 only addition and multiplication are allowed (commutative ring), and
 division is allowed (integral domain or field)
State space approach: solution as a path from the initial state to a final state. Case study: lower bound of finding the maxiumum and minimum in an array, with only comparisons permitted. Adversarial search.

Lecture 18 (Oct 20): Greedy Algorithms
Why a greedy strategy might not always work: shortest path algorithms, coin dispenser algorithm.
The {0,1}Knapsack problem as an NP complete problem. Continuous equivalent: [0,1]Knapsack problem. Failed heuristic: highest profit first. Greedy algorithm to solve the [0,1]Knapsack problem (profit per unit weight), verification of optimality.

Lecture 19 (Oct 27): Approximation Algorithms (Introduction)
Optimization algorithms. Quality and efficacy of an approximation algorithm. Efficiency analysis and efficacy analysis. Approximation ratio for minimization and maximization problems. Importance of obtaining a tight bound, verification methods.
Case study (maximization): {0,1}Knapsack problem. Failed attempt: pure greedy strategy — unbounded approximation ratio. Modified strategy, and its analysis.

Lecture 20 (Oct 29): Approximation Algorithms (Continued)
Load balancing problem: scheduling of independent jobs as a minimization problem. Variants of the problem. Greedy approximation algorithm and its analysis.
LPT scheduling. LPTbased approximation algorithm and its analysis.

Linear programming is another big hammer for algorithm design. We discussed the definition of LP's, what it means for them to be unbounded or infeasible, and a canonical form that any LP can be converted into. We also went over the simplex algorithm at a high level.
Then, we moved onto a particular class of linear programs: maximizing flows in networks. In this case, the operation of the simplex algorithm can be described in a natural combinatorial way and in this case, it also goes by the name of FordFulkerson. The algorithm iteratively finds an augmenting path in the residual graph, each time increasing the value of the flow. The proof of correctness gave us a proof of the famous MinCutMaxFlow theorem.

The MinCutMaxFlow theorem from the last lecture has many applications, not directly connected to flows. We first showed how it implies an efficient algorithm to find a maximum cardinality matching in a bipartite graph. Of course, this also gives a way to decide if a bipartite graph admits a perfect matching. We next showed how to efficiently obtain a minimum vertex cover in a bipartite graph. Finally, we also observed how Hall's Theorem follows from the MinCutMaxFlow theorem.
We then returned to LP's in general and described the multicommodity flow problem. We also discussed how to compute optimal strategies in 2player games by a reduction to linear programming.
Finally, we also showed the maximum weighted matching in a weighted bipartite graph can also be found by LP's. The LP relaxation is natural. The analysis showed that one can also find an integral optimum.

The relationship between MaxFlow and MinCut is captured by a notion called "LP Duality". We formally defined the dual LP for a given primal LP as a way to upperbound the objective of a maximization problem. We discussed the weak and strong duality theorems. Then, we showed pairs of problems related by duality, such as maximum matching versus minimum vertex cover, set cover versus packing, and max flow versus min cut.

We discussed the complementary slackness theorem. We then used it to give a primaldual algorithm for the minimum cost perfect matching problem and an approximation algorithm for set cover.

Lecture 26 (Nov 17): NP hardness
Previously in Lecture 17, we looked at lower bounds for very restricted kinds of algorithms. How can we show hardness even against algorithms that take full advantage of a modern CPU? Although we don't know how to show such strong lower bounds unconditionally, we can compare the hardness of two problems by the means of a "polynomial time reduction." We defined the classes P, NP, NPhard, and NPcomplete. The SAT problem is as hard as any problem in NP; this is the content of Cook's theorem. One problem in NP is the Clique problem. By Cook's theorem, there is a poly time reduction from Clique to SAT. We saw that there is also a poly time reduction from SAT to Clique, making Clique NPhard.

Lecture 27 (Nov 19): Reductions between NPhard problems
We gave examples of polynomial time reductions. We saw that Clique reduces to Indendent Set which reduces to Vertex Cover. Then, we saw that SAT reduces to 3SAT which reduces to 3DMatching.