## 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

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

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

#### 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
10. 03/02/2012: Activity selection problem continued

11. 08/02/2012: Introduction to graphs

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

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

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

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

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

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

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

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

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

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

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

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

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

27. 06/04/2012: Holiday

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

29. 13/04/2012: Holiday

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

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