Teaching assistants: Nikhil Mande, Pratik Ghosal

- Sorting: insertion sort, quick sort, merge sort, heap sort
- Searching: linear and binary search
- Basic data structures: stack, queue, linked list
- Graph algorithms: DFS, BFS, topological sorting of a DAG, finding strongly connected components of a directed graph, minimum spanning trees (Prim's and Kruskal's algorithms)

- Divide and conquer: selection in linear time
- Hashing, Advanced data structures: binary and Fibonacci heaps
- Greedy and dynamic programming techniques
- Network flows, bipartite matchings
- Linear programming, duality
- NP-completeness
- Introduction to approximation and randomized algorithms

Top

- Algorithm Design by Kleinberg and Tardos
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
- Algorithms by Dasgupta, Papadimitriou, Vazirani online copy

Top

- Assignments: 15
- Class tests: 20
- Midsem: 25
- Endsem: 40

Any other form of copying implies a fail grade in the course. If you get stuck while solving the assignment, you are welcome to discuss with me.

Top

Class test 1 and marking scheme

Assignment 1 Due date: Friday, 14th September, in class.

Assignment 1 solutions and marking scheme

Assignment 2 Due date: Friday, 21st September, in class.

Solutions/marking scheme for first 3 problems of Assignment 2 is here and a solution to the 4th problem (written by Nikhil) is here

Midsem paper Marking scheme will be discussed in class.

Assignment 3 Due date: Friday, 19th October, in class.

Assignment 3 solutions and marking scheme for all but the last problem.

Class test 2 and marking scheme

Endsem paper and Marking scheme

Top

Top

- 06/08/2012: Introduction, n log n lower bound for comparison sorts, counting sort, and radix sort, selection in worst-case linear time. (Ref: CLRS)
- 10/08/2012: Selection revisited, writing correctness proofs (insertion sort) (Ref: CLRS)

, integer multiplication O(n^1.59) algorithm, recurrence solving, Strassen's matrix multiplication (Ref: Dasgupta et al) - 13/08/2012: Greedy and dynamic programming techniques: Dijkstra's algorithm, Bellman-Ford algorithm, all-pairs shortest paths (Floyd-Warshall algorithm) (Ref: CLRS)
- 17/08/2012: Greedy and dynamic programming techniques: Matrix chain multiplication (Ref: CLRS),

optimal merge patterns (Ref: Horowitz, Sahani Rajasekharan)

20/08/2012: Holiday - 24/08/2012: The traveling salesperson problem (TSP): Greedy (nearest neighbour approach) for Euclidean setting, dynamic programming algorithm
- 27/08/2012: Advanced data structures: Binomial heaps (Ref: Kozen)
- 31/08/2012: Binomial heaps continued, introduction to Fibonacci heaps (Ref: Kozen)
- 03/09/2012: Fibonacci heaps (Ref: Kozen)
- 07/09/2012: Network flows: Introduction, Ford-Fulkerson algorithm (Ref: CLRS)
- 10/09/2012: Max-flow min-cut theorem, Edmonds-Karp algorithm (Ref: CLRS)
- 14/09/2012: Analysis of Edmonds-Karp algorithm, applications of network flows: maximum bipartite matching, maximum number of edge-disjoint paths
- 17/09/2012: Linear programming, formulating problems as LP: shortest paths, network flows, maximum matching
- 21/09/2012: LP Duality, strong duality theorem (without proof), max-flow min-cut theorem using LP duality
- 01/10/2012: FFT algorithm
- 05/10/2012: FFT algorithm continued (Ref: Dasgupta et al)
- 08/10/2012: Midsem discussion
- 12/10/2012: NP-completeness: Introduction, definitions
- 15/10/2012: NP-completeness of circuit-sat
- 19/10/2012: More reductions: Formula-sat, 3-CNF sat (Presentation by Nikhil)
- 22/10/2012: NP-completeness of vertex cover, clique, independent set, subset sum (Presented by Nikhil)
- 26/10/2012: NP-completeness of integer linear programming, and TSP. Formal language perspective for the definition of NP
- 29/10/2012: Hopcroft-Karp algorithm for maximum matching in bipartite graphs(Presented by Pratik)
- 02/11/2012: Hopcroft-Karp algorithm continued (Reference)
- 05/11/2012: Approximation algorithms: Introduction, 2-approximation for vertex cover problem, 2-approximation for Euclidean TSP, inapproximability of general TSP (Ref. CLRS)
- 09/11/2012: 3/2-approximation for Euclidean TSP (in fact metric TSP), log n-approximation to set-cover (Ref: Vazirani's book on Approximation Algorithms)
- 12/11/2012: log n-approximation to set-cover continued, 2-approximation to weighted vertex cover (Ref.: Analysis: Pricing method from Kleinberg-Tardos, and the presentation is from here
- 16/11/2012: Randomized 8/7-approximation algorithm for Max 3-SAT, analysis of expected running time, derandomization using conditional expectation (Ref. Kleinberg-Tardos, See this for derandomization).
- 19/11/2012: Miller-Rabin primality test (Ref. CLRS, Dasgupta et al)
- 23/11/2012: Hashing: Introduction, universal family of hash functions (Ref. Kleinberg-Tardos)

I have used various online references for LP, but the closest reference to what I taught is Dasgupta et al. 24/09/2012-28/09/2012: Midsem week, no class.

Top