Design and Analysis of Algorithms

(for M.Sc.Applications of Mathematics, 2011 batch)

Reference:

Introduction to algorithms by Cormen, Leiserson, Rivest, Stein

Fundamentals of computer algorithms by Horowitz, Sahani, Rajasekaran (for some selected topics)

Assignments:

  1. Small assignment 1: Write correctness proofs of insertion sort and merge sort algorithms

  2. Small assignment 2: Write correctness proof of Radix sort algorithm.
    Which of the following sorting algorithms are stable: Quicksort, Heapsort, Insertion sort, Merge sort

  3. Assignment 1: Following problems from the book of Cormen et al. (Numbers in brackets indicate marks.)
    2-3 (1,1,2,3), 2-4 (1,1,1,2), 3.1-1 (3), 3.1-4 (4), 3-2 (6), 3-4 (8), 4.1-6 (3), 4.2-4 (3), 4.2-5 (3), 4.3-2 (3), 4.4 c,f,j (9), 6-2 (2,2,3,3,3), 6-3 (2,2,3,3,3,3), 8-6 (1,2,2,2)
    Total marks=90
    (Hints/answers)

  4. Class test 1


  5. Midsem paper (held on 23/02/2012)


  6. Class test 2


  7. Assignment 2 (due on April 4th, no late submissions): Following problems from CLRS: 15.1, 23-1, 23.1-4, 25.1-5, 26.2-10, 24.1-3, 24-2, 24-4, 23-4, 23.1-11, 26.2-8, 26.3-5
    (3 more problems are available on this page.)

    8. (Hints/answers with marking scheme)

  8. Endsem paper (held on 27/04/2012)

    9. Hints/answers

    Marks

    A mark list is available here.

    Lectures

    1. 04/01/2012: Introduction, insertion sort, merge sort

    2. 06/01/2012: Asymptotic notation, methods for solving recurrence relations: substitution, recursion tree

    3. 11/01/2012: Recurrences continued: recursion tree, master method

    4. 13/01/2012: Heapsort, Quicksort

    5. 18/01/2012: Lower bounds for comparison sorts, Counting sort, Radix sort

    6. 20/01/2012: Dynamic programming: Matrix chain multiplication, Introduction to 0/1 knapsack

    7. 25/01/2012: 0/1 knapsack continued, Introduction to greedy method

    8. 27/01/2012: The fractional knapsack problem, activity selection problem

      9. 01/02/2012: Class test 1
    9. 03/02/2012: Activity selection problem continued

    10. 08/02/2012: Introduction to graphs

      11. 10/02/2012: Class rescheduled to 13/02
    11. 13/02/2012: Breadth-first search, Depth-first search

    12. 15/02/2012: Depth-first search continued, Topological sorting

    13. 17/02/2012: Identifying strongly connected components of a directed graph, minimum spanning trees (greedy algorithm)

    14. 29/02/2012: Kruskal and Prim's algorithms for MST, Single source shortest paths: Dijkstra's algorithm, Bellman-Ford algorithm

    15. 02/03/2012: All-pairs shortest paths: Floyd-Warshall algorithm,

      16. 07/03/2012, 09/03/2012: No class

    16. 12/03/2012: Introduction to network flows (extra class)

    17. 14/03/2012: Ford Fulkerson algorithm, Edmond-Karp algorithm

    18. 16/03/2012: Applications of divide-and-conquor technique (a small leftover module): Selection in linear time, convex hull in plane

    19. 21/03/2012: Convex hull algorithm continued, NP-completeness: Optimization vs. decision problems, definitions of P and NP, concept of verifier and certificate.

    20. 23/03/2012: Reducibility, NP-complete and NP-hard problems, Circuit satisfiability problem is NP-complete

    21. 28/03/2012: NP-completeness of SAT, 3-CNF SAT, and clique

      22. 30/03/2012: No class
    22. 04/04/2012: NP-completeness of vertex cover and subset sum

      23. 06/04/2012: Holiday

    23. 11/04/2012: Introduction to Approximation and randomized algorithms: 2-approximation for vertex cover, randomized 8/7-approximation algorithm for MAX 3-SAT

      24. 13/04/2012: Holiday

    24. 18/04/2012: Approximation algorithms continued: derandomization of the 8/7-approximation algorithm, log n-approximation to set-cover, 2-approximation to Max Cut

      25. 20/04/2012: Class cancelled due to Discrete Maths endsem