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

- Small assignment 1: Write correctness proofs of insertion sort and merge sort algorithms
- Small assignment 2: Write correctness proof of Radix sort algorithm.

Which of the following sorting algorithms are stable: Quicksort, Heapsort, Insertion sort, Merge sort - 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) - Class test 1
- Midsem paper (held on 23/02/2012)
- Class test 2
- 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.) - Endsem paper (held on 27/04/2012)
- 04/01/2012: Introduction, insertion sort, merge sort
- 06/01/2012: Asymptotic notation, methods for solving recurrence relations: substitution, recursion tree
- 11/01/2012: Recurrences continued: recursion tree, master method
- 13/01/2012: Heapsort, Quicksort
- 18/01/2012: Lower bounds for comparison sorts, Counting sort, Radix sort
- 20/01/2012: Dynamic programming: Matrix chain multiplication, Introduction to 0/1 knapsack
- 25/01/2012: 0/1 knapsack continued, Introduction to greedy method
- 27/01/2012: The fractional knapsack problem, activity selection problem
- 03/02/2012: Activity selection problem continued
- 08/02/2012: Introduction to graphs
- 13/02/2012: Breadth-first search, Depth-first search
- 15/02/2012: Depth-first search continued, Topological sorting
- 17/02/2012: Identifying strongly connected components of a directed graph, minimum spanning trees (greedy algorithm)
- 29/02/2012: Kruskal and Prim's algorithms for MST, Single source shortest paths: Dijkstra's algorithm, Bellman-Ford algorithm
- 02/03/2012: All-pairs shortest paths: Floyd-Warshall algorithm,
- 12/03/2012: Introduction to network flows (extra class)
- 14/03/2012: Ford Fulkerson algorithm, Edmond-Karp algorithm
- 16/03/2012: Applications of divide-and-conquor technique (a small leftover module): Selection in linear time, convex hull in plane
- 21/03/2012: Convex hull algorithm continued, NP-completeness: Optimization vs. decision problems, definitions of P and NP, concept of verifier and certificate.
- 23/03/2012: Reducibility, NP-complete and NP-hard problems, Circuit satisfiability problem is NP-complete
- 28/03/2012: NP-completeness of SAT, 3-CNF SAT, and clique
- 04/04/2012: NP-completeness of vertex cover and subset sum
- 11/04/2012: Introduction to Approximation and randomized algorithms: 2-approximation for vertex cover, randomized 8/7-approximation algorithm for MAX 3-SAT
- 18/04/2012: Approximation algorithms continued: derandomization of the 8/7-approximation algorithm, log n-approximation to set-cover, 2-approximation to Max Cut

(Hints/answers with marking scheme)

Hints/answers

01/02/2012: Class test 1

10/02/2012: Class rescheduled to 13/02

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

30/03/2012: No class

06/04/2012: Holiday

13/04/2012: Holiday

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