Design and
Analysis of Algorithms (AugDec 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:0012:00
Grading:
50% on homeworks
10%
on periodical quizes
40%
on tests

29^{th}
August 
No class 

1 
31st August 
Introduction:
Fibonacci sequence, algorithms to find the nth 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 
7^{th} Sept. 
Algorithms
with numbers: Algorithms
for addition, multiplication and division. Equivalence
relations. Congruence modulo N. Modular addition,
multiplication and exponentiation 

4 
12^{th} Sept. 
Algorithms
with numbers: Greatest
Common Divisor, Euclid's Algorithm, Extended Euclid's
Algorithm, Multiplicative inverse modulo N, Eulers phi
function 

5 
14^{th} Sept. 
Algorithms with numbers: Groups:
Lagrange theorem, Eulers theorem, Fermats Little Theorem.
A short introduction to randomized algorithms 

6 
19^{th} Sept 
Algorithms
with numbers: Primality testing: Fermats
test and Miller Rabins test. Quiz 1 

7 
21^{st} Sept 
Divide and
Conquer algorithms: Merge Sort, Karatsuba multiplication, Solving Divide and conquer
recurrences. 

8 
26^{th} Sept. 



28^{th}
Sept 
Divide and
Conquer algorithms: Quicksort and
its analysis 

10 
3^{rd}
Oct 
Sorting:
Heapsort and
its analysis 

11 
4th Oct 
Review of Probability:
Sample space, events, conditional probability, discrete
random variables, expectation and variance. 


5^{th}
Oct 
Sorting:
Lower bound for
comparison based sorting. Linear time sorting
algorithms 

13 
7^{th} Oct 
Discussion on HW1 by Sandra. Review of Probability: Some problems involving computation of exepectation  

10^{th}
Oct 
Divide
and Conquer algorithms: Selection Problem 

15 
12^{th} Oct 
Divide and Conquer algorithms:
Polynomial
multiplication and the Fast Fourier Transform. 

16 
14^{th} Oct  Review 

17 
17^{th}
Oct 
Test 1 

18 
19^{th}
Oct 
Discussion
on the test. 

19 
24^{th}
Oct 
Graph
Algorithms:
Basic Terminologies: directed and undirected graphs,
paths, trees, cycles, graph representation: adjacency
list, adjacency matrix 

20 
26^{st}
Oct 
Graph
Algorithms: Breadth first search and its
properties, testing Bipartiteness 

21 
31^{th} Oct. 
Graph
Algorithms: Depth first search and its
properties, Topological sorting 


2^{nd} Nov 
No
Class: Day of the dead 

22 
4^{th} Nov  Graph Algorithms:
Strongly connected components. 


7^{th} 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 


16^{th} Nov 
Dynamic Programming: Characteristics
of dynamic programing, longest common subsequence
problem 


18^{th} Nov 
Dynamic Programming: Matrix
chain multiplication, all pairs shortest path
problem: Floyd Warshall, Johnson 


21st Nov 
No
Class: Revolution Day 


23^{rd} Nov 
P, NP, NP Completeness 


25^{th} Nov 
P,
NP, NP Completeness 

30 
28th Nov 
Review 


30^{th} Nov 
Test 2 

2nd Dec 
Closing!! 