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 well-known principles such as abstraction, computational problem, ADT, input size, unit cost criteria and associate instruction counts, worst-case and average-case 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₁,a₂,...,a_i} from the partial solution PS_i-1 and a_i. We considered the infinite wall problem to explain different flavours of incremental strategies.

We discussed examples where it's more efficient to process input in a non-straightforward 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): Divide-and-conquer and Pruning. (Rough notes)

Divide-and-conquer 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 median-of-medians algorithm as examples for pruning. For divide-and-conquer, 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 Red-Black trees that self-balance after each insertion/deletion; in class, we described AA trees (some excellent notes here).

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(logn) expected time for searches, insertions and deletions, without any of the intricate case analysis involved in red-black or AVL trees. A very nice discussion of skip lists is in Erickson's lecture notes.

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.

We discussed Monte Carlo methods in detail and explained the randomized primality test.

Lecture 10 (Sep 10): Hashing. (Rough notes)

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 Karp-Rabin string matching algorithm as an application of hashing.

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 Floyd-Warshall all-pairs shortest paths (APSP) problem. The current-best APSP algorithm, which uses a lot more sophistication, is from 2014 by Ryan Williams; here are some lecture notes sketching this.

Lecture 12 (Sep 22): Minimum spanning trees. (Rough notes)

Continuing along the lines of the APSP algorithm discussed in the last lecture, we moved to another classic graph-theoretic optimization problem: finding minimum spanning trees in weighted undirected graphs. We discussed a meta-algorithm 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.

Lecture 13 (Sep 24): Shortest paths. (Rough notes)

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 negative-weight edges. Then, we also talked about the Bellman-Ford 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 non-bipartite 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 trade-offs. 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. LPT-based approximation algorithm and its analysis.

Lecture 21 (Nov 05): Intro to Linear Programming (Rough notes)

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 Ford-Fulkerson. 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 MinCut-MaxFlow theorem.

Lecture 22 (Nov 08): Linear Programming, Part 2 (Rough notes)

The MinCut-MaxFlow 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 MinCut-MaxFlow theorem.

We then returned to LP's in general and described the multi-commodity flow problem. We also discussed how to compute optimal strategies in 2-player 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.

Lecture 24 (Nov 10): LP Duality (Rough notes)

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.

Lecture 25 (Nov 12): LP Duality, Part 2 (Rough notes)

We discussed the complementary slackness theorem. We then used it to give a primal-dual 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, NP-hard, and NP-complete. 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 NP-hard.

Lecture 27 (Nov 19): Reductions between NP-hard 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 3D-Matching.