Design and Analysis of Algorithms (Aug-Dec 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:00-12:00

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

Home works:     

Home work 1 (Due September 19)
Home work 2 (Due October 3)
Home work 3 (Due October 12)
Home work 4 (Due November 4)
Home work 5 (Due November 14)
Home work 6 (Due November 23)

Handouts:               

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

Schedule (Tentative): will be filled up as we proceed

	29^th August	No class
1	31st August	Introduction: Fibonacci sequence, algorithms to find the n-th 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.	Divide and Conquer algorithms: Solving divide and conquer recurrences, Matrix Multiplication, Counting inversions.
9	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.
12	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
14	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. Divide and Conquer algorithms: Polynomial multiplication and the Fast Fourier Transform.
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
26	16^th Nov	Dynamic Programming: Characteristics of dynamic programing, longest common subsequence problem
27	18^th Nov	Dynamic Programming:  Matrix chain multiplication, all pairs shortest path problem: Floyd Warshall, Johnson
	21st Nov	No Class: Revolution Day
28	23^rd Nov	P, NP, NP Completeness
29	25^th Nov	P, NP, NP Completeness
30	28th Nov	Review
	30^th Nov	Test 2
	2nd Dec	Closing!!