Design and Analysis of Algorithms
This is an introductory course on algorithms for B.Sc. second year students.
Students from M.Sc. first year are also welcome to take the course if they have the prerequisite background.
Teaching assistants: Nikhil Mande, Pratik Ghosal
The assumed background will be that of the programming course the B.Sc. students
have done in their first year. This includes the following:
- 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)
We will not have enough time to cover all of the following topics in sufficient depth, but we will cover as much as possible:
If time permits, we will see some number theoretic algorithms including primality testing.
- 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
- Introduction to approximation and randomized algorithms
I may cover some topics from other sources. The references will be mentioned
from time to time.
- Algorithm Design by Kleinberg and Tardos
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
- Algorithms by Dasgupta, Papadimitriou, Vazirani online copy
There will be four assignments, two class tests, midsem, and endsem. The
weightage is as follows:
- Assignments: 15
- Class tests: 20
- Midsem: 25
- Endsem: 40
While solving the assignments (and class tests and exams too!), you are not
supposed to discuss with anyone (neither in your class nor anyone else).
If at all you discuss an assignment problem
with someone, name of that person should be mentioned while writing the
solution of that particular problem. If you look up the solution on the
Internet, the link to the solution should also be mentioned while writing it.
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.
Note: Please read the Copying policy before you start
solving the assignment. The solutions/hints will be posted on the
deadline. Hence no late submissions are allowed.
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)
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
Final marks and grades
Topics covered so far:
- 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)
- 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
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.
- 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