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.
Top

Reference books

  1. Algorithm Design by Kleinberg and Tardos
  2. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
  3. Algorithms by Dasgupta, Papadimitriou, Vazirani online copy
I may cover some topics from other sources. The references will be mentioned from time to time.
Top

Evaluation

There will be four assignments, two class tests, midsem, and endsem. The weightage is as follows:
  1. Assignments: 15
  2. Class tests: 20
  3. Midsem: 25
  4. Endsem: 40
Top

Copying policy

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.
Top

Assignments

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.

Assignment 1 Assignment 2
Brief answers/solutions to assignment 1.
Top

Lectures

Topics covered so far:

  1. 8 Aug: Insertion sort, asymptotic notation, lower bound on comparison sort
  2. 13 Aug: Counting and radix sort,
  3. 20 Aug: Mergesort, Quicksort, Recurrence solving by substitution method
  4. 22 Aug: Recurrence solving by recursion tree and master methods, integer multiplication and Strassen's matrix multiplication
  5. 27 Aug: Divide and Conquer: Selection in worst case linear time
  6. 3 Sep: BFS, DFS, topological sort of a DAG
  7. 5 Sep: Strongly connected components, Dijkstra's algorithm
  8. 10 Sep: Bellman-Ford algorithm, Prim and Kruskal's algorithms for minimum spanning trees, union by rank with path compression (Ref: DPV)
  9. 17 Sep: All-pairs shortest path by matrix multiplication, Floyd-Warshall algorithm, transitive closure
  10. 19 Sep: Greedy and dynamic programming: knapsack (fractional, 0/1), matrix chain multiplication, optimal merge patterns
  11. 1 Oct: Network flows: Ford-Fulkerson algorithm, Max-flow min-cut theorem, maximum bipartite matching
  12. 8 Oct: Edmonds-Karp algorithm for max-flow, Linear Programming, Duality
  13. 10 Oct: Max-flow min-cut theorem using LP duality, edge-disjoint paths in directed and undirected graphs (ref: KT)
  14. 15 Oct: Hopcroft-Karp algorithm for bipartite matching (ref: this and this)