Design and
Analysis of Algorithms (AugDec 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:0012:00
Grading:
60% on
homeworks, 40% on tests
Homework 5
(due Dec 4, 2009)
Extra credit problems (due Dec 20, 2009)
Equivalence Relations
Functions
1 
24^{th} August 
Introduction:
Algorithms, their design and analysis; The Fibonacci numbers. Algorithms to find the nth
Fibonacci number. 

2 
28^{th} August 
Introduction: Finding the nth 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 
31^{st} Aug. 
Efficiency Analysis: Growth of functions; Oh, Theta and
Omega notations. 

4 
2^{nd} ^{ }Sept. 
Algorithms with numbers: Algorithms for addition and multiplication. Modular arithmetic, equivalence relations. 

5 
7^{th} Sept. 
Algorithms with numbers: computing gcd, multiplicative inverse 

6 
9^{th} Sept. 
Algorithms with numbers: computing gcd, groups, Lagrange
theorem 

7 
14^{th} Sept. 
Algorithms with numbers: Primality testing: Fermats test,
Miller Rabin test 

8 
16^{th} Sept 
No class: Independence Day 

9 
21^{st} Sept 
Divide and Conquer Algorithms: Fast integer multiplication, divide and
conquer recurrences , the masters
theorem to solve divide and conquer recurrences. 

10 
23^{rd} Sept. 
Matrix Multiplication: The Strassens
Method 


28^{th} Sept 
No class 

11 
30^{th} Sept 
Sorting: Heap
sort and its analysis 


5^{th} Oct 
Review 


7^{th} Oct 
Test 1 

12 
14^{th} Oct 
Sorting: Quicksort and its analysis. 

13 
19^{th} Oct 
Sorting: Lower bound for comparison based sorting, counting
sort a linear time sorting algorithm. Selection 

14 
21^{th} Oct 
Integers polynomials and matrices: Polynomials, coefficient and point
value representation of polynomials, roots of unity, the discrete
Fourier transform. The FFT algorithm 

15 
26^{th} Oct 
Integers polynomials and matrices: The interpolation problem, inverse FFT,
nonrecursive FFT and the butterfly network . 

16 
28^{st} Oct 
Graph Algorithms: Basic terminology, Representation of graphs, the
adjacency matrix and the adjacency list, the depth first search algorithm 

17 
30^{th} Oct. 
Graph Algorithms: Properties of the depth fast search, directed
acyclic graphs, topological sorting 


2^{nd} Nov 
No Class: The day
of the deads 

18 
4^{th} Nov 
Graph Algorithms: Depth first search: strongly
connected components 

19 
5th Nov 
Graph Algorithms: Shortest path algorithms Dijkstra’s
algorithm 


9^{th} Nov 
Review 


11^{th} Nov 
Test 2 

20 
12th Nov 
Graph Algorithms: Minimal spanning trees 


16^{th} Nov 
No Class: Revolution day 


18^{th} Nov 
No Class: (I will be out of town) 

21 
23^{er} Nov 
Dynamic Programming 

22 
25^{th} Nov 
Dynamic Programming 

23 
30^{th} Nov 
P, NP and NPCompleteness 

24 
2^{nd} Dec 
P, NP and NPCompleteness 


4^{th} Dec 
Review 


7^{th} Dec 
Test 3 


9^{th} Dec 
Closing!! 


