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

Grading:                    60% on home-works, 40% on tests 

Home works:          Homework 1 (due 14^th September 2009)
Homework 2 (Probs 1-13 due 28^th September 2009, prob. 14 due Oct 14)
Homework 3 (Probs 1-6 due Oct. 19, probs. 7-8 due Oct 30) Sample code to measure time
Homework 4 (due Nov 20, 2009)

Homework 5 (due Dec 4, 2009)

Extra credit problems (due Dec 20, 2009)

Practice Problems:     Practice Problems 1 (solutions not to be submitted)

Handouts:                Linear Homogeneous Recurrences with Constant Coefficients

Equivalence Relations
Functions

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

1	24^th August	Introduction: Algorithms, their design and analysis; The Fibonacci numbers. Algorithms to find the n-th Fibonacci number.
2	28^th August	Introduction: Finding the n-th 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 Sorting: The merge sort.
	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, non-recursive 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 NP-Completeness
24	2^nd Dec	P, NP and NP-Completeness
	4^th Dec	Review
	7^th Dec	Test 3
	9^th Dec	Closing!!