Design and Analysis of Algorithms (Sep-Dec 2013)

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

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

Home works:    

Home work 1
Home work 2
Home work 3
Home work 4
Home work 5

Handouts:               

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


Tentative schedule:

01. Sep 02.   Introduction: Algorithms for finding the  nth Fibonacci number.

02. Sep 04. Asymptotic Growth of Functions: The insertion sort; O, Theta, Omega notations

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

04. Sep 09. Algorithms with numbers: Modular arithmetic, equivalence relations, equivalence classes, modular arithmetic

     Sep 10.  No class: I would be out of town
     Sep 16.  No class: Independence day

05. Sep 20. Algorithms with numbers: Finding GCDs, multiplicative inverse, Eulers Phi function

06. Sep 23.  Algorithms with numbers: Introduction to Groups: Lagrange theorem, Eulers Theorem, Fermat's little theorem. Introduction to randomized algorithms

07. Sep 25.  Algorithms with numbers: Primality testing algorithms: Fermats test and Miller Rabin test.

08. Sep 27. Algorithms with numbers:RSA crypto system, Universal hashing

09. Sep 30. Divide and Conquer Algorithms: Merge sort, Karatsuba multiplication, Solving divide and conquer recurrences

      Oct 02. No class CCE conference

10. Oct 07. Divide and Conquer Algorithms: Strassen's matrix multiplication, Counting inversions, Quicksort

11. Oct 09. Divide and Conquer Algorithms: Review of random variables and expectations. Expected running time of an algorithm. Analysis of Quicksort

12. Oct 14. Heap sort: Heap sort and analysis. Heap as a priority queue

13. Oct 16: Lower bound on comparison based sorting; linear time sorting algorithms: Counting Sort and Bucket Sort

14. Oct 18: Revision, discussion on homework problems.

15. Oct 21. Test 1

16. Oct 23. Divide and Conquer: The median finding problem

17. Oct 28.  No class

18. Oct 30. Divide and Conquer: Polynomial multiplication and the fast fourier transform

19. Nov 04. Graph Algorithms: Introduction to graphs, the breadth first search

20. Nov 06. Graph Algorithms: Depth first search and properties

21. Nov 11. Graph Algorithms: Topological Sorting, Strongly connected components

22. Nov 13. Graph Algorithms: Shortest paths in graphs, Dijkstra's algorithm

23. Nov 13. Graph Algorithms: Bellman Ford algorithm, Currency arbitraje, solving system of difference constraints

      Nov 18.  No class: Revolution day
24. Nov 20.  Dynamic Programing:
25. Nov 22. Dynamic Programing:
26. Nov 25. NP Completeness:
27. Nov 27. NP Completeness:
28. Dec 02. Revision
29. Dec 04. Test 2
30. Dec 06. Closing