Design and Analysis of Algorithms (Sep-Dec 2012)

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, Rivest, Stein (CLRS)

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.  (Posted Sept 10, 2012. Due Sept 24, 2012)
Home work 2.  (Posted Sept 24, 2012. Due Oct 17, 2012)
Home work 3.  (Posted Oct 17, 2012. Due Nov 07, 2012)
Home work 4.  (Posted Nov 7, 2012. Due Nov 14, 2012)
Home work 5.  (Posted Nov 14, 2012. Due Nov 21, 2012)
Home work 6.  (Posted Nov 21, 2012. Due Nov 28, 2012)

## Handouts:

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

Tentative schedule:

Sep 03.   No Class

01. Sep 05.   Introduction: Algorithms to find the n-th Fibonacci number. Solving linear homogeneous recurrences with constant coefficients.

02. Sep 10. Asymptotic Growth of Functions: The insertion sort and its analysis. The O, Omega, Theta notations.

03. Sep 12. Algorithms with numbers:  Algorithms to add, subtract, multiply and divide.

04. Sep 17. Algorithms with numbers: Equivalence relations, modular arithmetic, Greatest Common divisors

05. Sep 19. Algorithms with numbers: Greatest Common Divisors, Multiplicative Inverse Modulo n, Euler's Phi function, Introduction to Groups.

06. Oct 01.  Algorithms with numbers: Lagrange's Theorem, Euler's Theorem, Fermat's Little Theorem; Introduction to Randomized Algorithms

07. Oct 03.  Algorithms with numbers: Primality Testing: Fermat's test, Miller Rabin Test.

08. Oct 05. Divide and Conquer Algorithms: Merge Sort, Karatsuba Multiplication, Solving Divide and Conquer Recurrences: The substitution method, Recurrence tree method

09. Oct 08. Divide and Conquer Algorithms: Solving Divide and Conquer Recurrences: The Master Theorem; Strassen's Matrix Multiplication, Counting Inversions

10. Oct 10. Sorting: Heap sort and its analysis, Heap as a priority queue

11. Oct 12.  A tutorial on probability: Review on sample spaces, events, conditional probability, independence, random variables and their expectations.

12. Oct 15.  Divide and Conquer: Quick sort and analysis

13. Oct 17. Sorting: Lower bound for comparison based sorting . Linear time sorting : Counting Sort and Bucket Sort

14. Oct 19: Revision and discussions

15. Oct 22. Test 1

16. Oct 24.  Divide and Conquer: Median Finding

xx. Oct 29. No Class
xx. Oct 31. No Class

17. Nov 05. Divide and Conquer: Discrete Fourier Transform and Polynomial Multiplication

18. Nov 07. Divide and Conquer: Discrete Fourier Transform and Polynomial Multiplication. Graph Algorithms: Introduction to graphs

20. Nov 14. Graph Algorithms:  Depth first search, Topological Sorting

21. Nov 16. Graph Algorithms: Strongly connected components. Shortest paths: Dijkstra's algorithm.

xx. Nov 19. No class

22. Nov 21. Graph Algorithms: Shortest Paths: Analysis of Dijkstr's algorithm. Bellman Ford algorithm
23. Nov. 23. Dynamic Programing
24. Nov 26. NP completeness
25. Nov 28. NP completeness
26. Nov 30. Revision
27. Dec 03. Test 2
28. Dec 05. Closing