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.
Teaching assistant: Muthuvel Murugan I
Some of the topics listed below have been covered in programming courses.
However, the focus of the course will be on understanding the design and
correctness proofs of these algorithms.
- Sorting, Searching
- Graph algorithms: DFS, BFS, topological sorting of a DAG, finding strongly
connected components of a directed graph, minimum spanning trees
- Divide and conquer: selection in linear time
- 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.
Brief answers/solutions to assignment 1.
Topics covered so far:
- 8 Aug: Insertion sort, asymptotic notation,
lower bound on comparison sort
- 13 Aug: Counting and radix sort,
- 20 Aug: Mergesort, Quicksort, Recurrence solving by substitution method
- 22 Aug: Recurrence solving by recursion tree and master methods, integer
multiplication and Strassen's matrix multiplication
- 27 Aug: Divide and Conquer: Selection in worst case linear time
- 3 Sep: BFS, DFS, topological sort of a DAG
- 5 Sep: Strongly connected components, Dijkstra's algorithm
- 10 Sep: Bellman-Ford algorithm, Prim and Kruskal's algorithms for minimum
spanning trees, union by rank with path compression (Ref: DPV)
- 17 Sep: All-pairs shortest path by matrix multiplication, Floyd-Warshall
algorithm, transitive closure
- 19 Sep: Greedy and dynamic programming: knapsack (fractional, 0/1),
matrix chain multiplication, optimal merge patterns
- 1 Oct: Network flows: Ford-Fulkerson algorithm, Max-flow min-cut theorem,
maximum bipartite matching
- 8 Oct: Edmonds-Karp algorithm for max-flow, Linear Programming, Duality
- 10 Oct: Max-flow min-cut theorem using LP duality, edge-disjoint paths in
directed and undirected graphs (ref: KT)
- 15 Oct: Hopcroft-Karp algorithm for bipartite matching (ref: this and this)