Design and Analysis of Algorithms (Aug-Dec 2009)

Instructor:               Dr. Debrup Chakraborty  (debrup(AT)cs.cinvestav.mx)

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:                    60% on home-works, 40% on tests

## Home works:          Homework 1  (due 14th September 2009)                                     Homework 2  (Probs 1-13 due 28th September 2009, prob. 14 due Oct 14)                                     Homework 3  (Probs 1-6 due  Oct. 19, probs. 7-8 due Oct 30) Sample code to measure time                                                 Homework 4  (due Nov 20, 2009)

(due Dec 4, 2009)

Extra credit problems (due Dec 20, 2009)

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

 1 24th August Introduction: Algorithms, their design and analysis; The Fibonacci numbers. Algorithms to find the n-th Fibonacci number. 2 28th August Introduction: Finding the n-th Fibonacci number, solving linear homogeneous recurrence relations with constant coefficients. The insertion sort algorithm and its analysis. Best case and worst case running times of algorithms. 3 31st  Aug. Efficiency Analysis:  Growth of functions;  Oh, Theta and Omega notations. 4 2nd  Sept. Algorithms with numbers:  Algorithms for addition and multiplication. Modular arithmetic, equivalence relations. 5 7th Sept. Algorithms with numbers: computing gcd, multiplicative inverse 6 9th Sept. Algorithms with numbers:  computing gcd, groups, Lagrange theorem 7 14th  Sept. Algorithms with numbers:  Primality testing: Fermats test, Miller Rabin test 8 16th Sept No class: Independence Day 9 21st Sept Divide and Conquer Algorithms:  Fast integer multiplication, divide and conquer recurrences , the masters theorem to solve divide and conquer recurrences. 10 23rd Sept. Matrix Multiplication: The Strassens Method Sorting: The merge sort. 28th Sept No class 11 30th Sept Sorting: Heap sort and its analysis 5th Oct Review 7th Oct Test 1 12 14th Oct Sorting: Quicksort and its analysis. 13 19th Oct Sorting: Lower bound for comparison based sorting, counting sort- a linear time sorting algorithm. Selection 14 21th Oct Integers polynomials and matrices: Polynomials, coefficient and point value representation of polynomials, roots of unity, the discrete Fourier transform. The FFT algorithm 15 26th Oct Integers polynomials and matrices: The interpolation problem, inverse FFT, non-recursive FFT and the butterfly network . 16 28st Oct Graph Algorithms: Basic terminology, Representation of graphs, the adjacency matrix and the adjacency list, the depth first search algorithm 17 30th Oct. Graph Algorithms: Properties of the depth fast search, directed acyclic graphs, topological sorting 2nd Nov No Class: The day of the deads 18 4th Nov Graph Algorithms: Depth first search: strongly connected components 19 5th Nov Graph Algorithms: Shortest path algorithms-  Dijkstra’s algorithm 9th Nov Review 11th Nov Test 2 20 12th Nov Graph Algorithms: Minimal spanning trees 16th Nov No Class: Revolution day 18th Nov No Class: (I will be out of town) 21 23er Nov Dynamic Programming 22 25th Nov Dynamic Programming 23 30th Nov P, NP and NP-Completeness 24 2nd Dec P, NP and NP-Completeness 4th Dec Review 7th Dec Test 3 9th Dec Closing!!