Design and Analysis of Algorithms (Aug-Dec 2011)

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

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)

## Handouts:

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 1 31st August Introduction: Fibonacci sequence, algorithms to find the n-th Fibonacci number; Linear Search; Worst case, best case and average case running times 2 5th  Sept. Asymptotic Growth of functions: Insertion sort, the big O, big Omega, Theta, small o, small omega notations and their properties. 3 7th Sept. Algorithms with numbers: Algorithms for addition, multiplication and division. Equivalence relations. Congruence modulo N. Modular addition, multiplication and exponentiation 4 12th Sept. Algorithms with numbers: Greatest Common Divisor, Euclid's Algorithm, Extended Euclid's Algorithm, Multiplicative inverse modulo N, Eulers phi function 5 14th  Sept. Algorithms with numbers: Groups: Lagrange theorem, Eulers theorem, Fermats Little Theorem. A short introduction to randomized algorithms 6 19th Sept Algorithms with numbers: Primality testing: Fermats test and Miller Rabins test. Quiz 1 7 21st Sept Divide and Conquer algorithms: Merge Sort, Karatsuba multiplication, Solving Divide and conquer recurrences. 8 26th Sept. Divide and Conquer algorithms: Solving divide and conquer recurrences, Matrix Multiplication, Counting inversions. 9 28th Sept Divide and Conquer algorithms:  Quicksort and its analysis 10 3rd Oct Sorting: Heapsort and its analysis 11 4th Oct Review of Probability: Sample space, events, conditional probability, discrete random variables, expectation and variance. 12 5th Oct Sorting: Lower bound for comparison based sorting. Linear time sorting algorithms 13 7th Oct Discussion on HW1 by Sandra. Review of Probability: Some  problems involving computation of exepectation 14 10th Oct Divide and Conquer algorithms: Selection Problem 15 12th Oct Divide and Conquer algorithms: Polynomial multiplication and the Fast Fourier Transform. 16 14th Oct Review 17 17th Oct Test 1 18 19th Oct Discussion on the test. Divide and Conquer algorithms: Polynomial multiplication and the Fast Fourier Transform. 19 24th Oct Graph Algorithms: Basic Terminologies: directed and undirected graphs, paths, trees, cycles, graph representation: adjacency list, adjacency matrix 20 26st Oct Graph Algorithms: Breadth first search and its properties, testing Bipartiteness 21 31th Oct. Graph Algorithms: Depth first search and its properties, Topological sorting 2nd Nov No Class: Day of the dead 22 4th Nov Graph Algorithms: Strongly connected components. 7th Nov No class 23 9th Nov Shortest path problems: Dijkstra's Algorithm 24 11th Nov Shortest path problems: Bellman Ford, Difference Constraints, Currency Arbitrage 25 14th Nov Minimal Spanning Trees: The cut property, Prims Algorithm, Kruskals algorithm, Disjoint set data structure 26 16th Nov Dynamic Programming: Characteristics of dynamic programing, longest common subsequence problem 27 18th Nov Dynamic Programming:  Matrix chain multiplication, all pairs shortest path problem: Floyd Warshall, Johnson 21st Nov No Class: Revolution Day 28 23rd Nov P, NP, NP Completeness 29 25th Nov P, NP, NP Completeness 30 28th Nov Review 30th Nov Test 2 2nd Dec Closing!!