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

### Assumed background

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

### Course plan

We will not have enough time to cover all of the following topics in sufficient depth, but we will cover as much as possible:
• 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
• NP-completeness
• Introduction to approximation and randomized algorithms
If time permits, we will see some number theoretic algorithms including primality testing.
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.

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) is here

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 scheme

Top

Top

### Lectures

Topics covered so far:

1. 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)
2. 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)
3. 13/08/2012: Greedy and dynamic programming techniques: Dijkstra's algorithm, Bellman-Ford algorithm, all-pairs shortest paths (Floyd-Warshall algorithm) (Ref: CLRS)
4. 17/08/2012: Greedy and dynamic programming techniques: Matrix chain multiplication (Ref: CLRS),
optimal merge patterns (Ref: Horowitz, Sahani Rajasekharan)
20/08/2012: Holiday
5. 24/08/2012: The traveling salesperson problem (TSP): Greedy (nearest neighbour approach) for Euclidean setting, dynamic programming algorithm
6. 27/08/2012: Advanced data structures: Binomial heaps (Ref: Kozen)
7. 31/08/2012: Binomial heaps continued, introduction to Fibonacci heaps (Ref: Kozen)
8. 03/09/2012: Fibonacci heaps (Ref: Kozen)
9. 07/09/2012: Network flows: Introduction, Ford-Fulkerson algorithm (Ref: CLRS)
10. 10/09/2012: Max-flow min-cut theorem, Edmonds-Karp algorithm (Ref: CLRS)
11. 14/09/2012: Analysis of Edmonds-Karp algorithm, applications of network flows: maximum bipartite matching, maximum number of edge-disjoint paths
12. 17/09/2012: Linear programming, formulating problems as LP: shortest paths, network flows, maximum matching
13. 21/09/2012: LP Duality, strong duality theorem (without proof), max-flow min-cut theorem using LP duality

14. 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.
15. 01/10/2012: FFT algorithm
16. 05/10/2012: FFT algorithm continued (Ref: Dasgupta et al)
17. 08/10/2012: Midsem discussion
18. 12/10/2012: NP-completeness: Introduction, definitions
19. 15/10/2012: NP-completeness of circuit-sat
20. 19/10/2012: More reductions: Formula-sat, 3-CNF sat (Presentation by Nikhil)
21. 22/10/2012: NP-completeness of vertex cover, clique, independent set, subset sum (Presented by Nikhil)
22. 26/10/2012: NP-completeness of integer linear programming, and TSP. Formal language perspective for the definition of NP
23. 29/10/2012: Hopcroft-Karp algorithm for maximum matching in bipartite graphs(Presented by Pratik)
24. 02/11/2012: Hopcroft-Karp algorithm continued (Reference)
25. 05/11/2012: Approximation algorithms: Introduction, 2-approximation for vertex cover problem, 2-approximation for Euclidean TSP, inapproximability of general TSP (Ref. CLRS)
26. 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)
27. 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
28. 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).
29. 19/11/2012: Miller-Rabin primality test (Ref. CLRS, Dasgupta et al)
30. 23/11/2012: Hashing: Introduction, universal family of hash functions (Ref. Kleinberg-Tardos)

Top