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
Grading:
50% on home-works
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
19. Nov 12. Graph Algorithms: Graph representations:
Adjacency list and adjacency matrix. Breadth first search
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