Design and Analysis of Algorithms (Aug-Dec 2011)

Instructor:               Dr. Debrup Chakraborty  (debrup(AT)

References:                1) Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
                                                     (This would be the text book for the course)

2)  Introduction to Algorithms , Cormen, Leiserson and Rivest (CRS)

                                               3) Design and Analysis of Computer Algorithms, Aho, Hopcroft and Ullman

Classes:                    Monday and Wednesday from 10:00-12:00


Grading:                    50% on home-works
                                                10% on periodical quizes
                                                40% on tests 

Home works:     

                                    Home work 1 (Due September 19)
                                    Home work 2 (Due October 3)
                                    Home work 3 (Due October 12)
                                    Home work 4 (Due November 4)
                                    Home work 5 (Due November 14)
                                    Home work 6 (Due November 23)


                            Hand out 1 (Solving linear homogeneous recurrence with constant coefficients)
                            Hand out 2 (Equivalence relations)

Schedule (Tentative): will be filled up as we proceed

29th August

No class



31st August

Introduction: Fibonacci sequence, algorithms to find the n-th Fibonacci number; Linear Search; Worst case, best case and average case running times


5th  Sept.

Asymptotic Growth of functions: Insertion sort, the big O, big Omega, Theta, small o, small omega notations and their properties.


7th Sept.

Algorithms with numbers: Algorithms for addition, multiplication and division. Equivalence relations. Congruence modulo N. Modular addition, multiplication and exponentiation



12th Sept.

Algorithms with numbers: Greatest Common Divisor, Euclid's Algorithm, Extended Euclid's Algorithm, Multiplicative inverse modulo N, Eulers phi function



14th  Sept.

Algorithms with numbers: Groups: Lagrange theorem, Eulers theorem, Fermats Little Theorem. A short introduction to randomized algorithms



19th Sept

Algorithms with numbers: Primality testing: Fermats test and Miller Rabins test. Quiz 1



21st Sept

Divide and Conquer algorithms: Merge Sort, Karatsuba multiplication, Solving Divide and conquer recurrences.



26th Sept.

Divide and Conquer algorithms: Solving divide and conquer recurrences, Matrix Multiplication, Counting inversions.



28th Sept

Divide and Conquer algorithms:  Quicksort and its analysis



3rd Oct

Sorting: Heapsort and its analysis



 4th Oct

 Review of Probability: Sample space, events, conditional probability, discrete random variables, expectation and variance.


5th Oct

Sorting: Lower bound for comparison based sorting. Linear time sorting algorithms



 7th Oct

 Discussion on HW1 by Sandra. Review of Probability: Some  problems involving computation of exepectation


10th Oct

Divide and Conquer algorithms: Selection Problem



12th Oct

Divide and Conquer algorithms: Polynomial multiplication and the Fast Fourier Transform.


14th Oct   Review


17th Oct

Test 1



19th Oct

Discussion on the test.
Divide and Conquer algorithms:
Polynomial multiplication and the Fast Fourier Transform.



24th Oct

Graph Algorithms: Basic Terminologies: directed and undirected graphs, paths, trees, cycles, graph representation: adjacency list, adjacency matrix



26st Oct

Graph Algorithms: Breadth first search and its properties, testing Bipartiteness


31th Oct.

Graph Algorithms: Depth first search and its properties, Topological sorting


2nd Nov

No Class: Day of the dead


  4th Nov  Graph Algorithms: Strongly connected components.

7th Nov

No class



9th Nov

Shortest path problems: Dijkstra's Algorithm


  11th Nov    Shortest path problems: Bellman Ford, Difference Constraints, Currency Arbitrage


   14th Nov
  Minimal Spanning Trees: The cut property, Prims Algorithm, Kruskals algorithm, Disjoint set data structure


16th Nov

Dynamic Programming: Characteristics of dynamic programing, longest common subsequence problem



18th Nov

Dynamic Programming:  Matrix chain multiplication, all pairs shortest path problem: Floyd Warshall, Johnson


21st Nov

No Class: Revolution Day



23rd Nov

P, NP, NP Completeness



25th Nov

P, NP, NP Completeness


  28th Nov


30th Nov

Test 2


 2nd Dec