Design and Analysis of Algorithms (Aug-Dec 2008)

Instructor: Dr. Debrup Chakraborty (debrup(AT)cs.cinvestav.mx)

References: 1) Introduction to Algorithms , Cormen Leiserson and Rivest (CRS)

2) Design and Analysis of Computer Algorithms, Aho, Hopcroft and Ullman

Classes: Tuesday and Thursday from 8:00-10:00

Home works

Home work 1 (due on sept. 11)
Home work 2 (due on Oct. 2)
Home work 3 (due on Oct. 23)(sample code to measure time)
Home work 4 (due on Nov. 6 )

Schedule (Tentative)

26^th August	Introduction: Algorithms, their design and analysis, the measures of efficiency for algorithms; The algorithms to find maximum, minimum, maximum and minimum together, the second smallest element; Ideas of best case, average case and worst case analysis, ideas on lower bounds; harmonic numbers.
28^th August	Introduction: Best Case, worst case and average case analysis; Linear search and its average case analysis; Selection sort; Insertion sort and its analysis; models of computation; growth of functions; efficient algorithms
11^th Sept.	Mathematical Preliminaries: Order of growth: Oh, Theta and Omega;
18^thSept.	Mathematical Preliminaries: Basic Counting: Permutations, Combinations, Binomial Coefficients. Recurrence Relations: Legal code-words, Fibonacci sequence, solving recurrences, the golden ratio.	HW1 due
20^th Sept.	Mathematical Preliminaries: Recurrence Relations: Solving linear homogeneous recurrences with constant coefficients, method of characteristic roots, divide and conquer recurrences, the integer multiplication algorithm, the master theorem for solving recurrences.
23^rd Sept.	Mathematical Preliminaries: Recurrence relations: Using the master theorem. Counting: Definition of functions, countable sets, the pigeonhole principle with examples.
25^rd Sept.	Sorting: Introduction to graphs and trees, the rooted binary tree and some of its properties, The heap data structure, the heapify and build heap procedures
30^th Sept	Sorting: The heapsort algorithm and its analysis, the use of heap as a priority queue.
2^nd Oct.	Sorting: The quick sort algorithm, the partition procedure with a randomized pivot. Worst case analysis, intuition for the average case.	HW2 due
7^th Oct.	Sorting: Average case analysis of quicksort, the decision tree model, the lower bound on worst case complexity for comparison based sorting. Non comparison based sorting: Counting Sort and bucket sort.
9^th Oct.	Integers Polynomials and Matrices: Introduction to Rings and fields with examples.
14^th Oct.	Integers, polynomials and Matrices: Algorithms for arithmetic on large integers
15^th Oct.	Tutorial: Discussion on HW 1 and 2
16^th. Oct.	Tutorial: Problem solving
21^st Oct.	Test 1
23^rd Oct.	Integers polynomials and matrices: Polynomials, coefficient and point value representation of polynomials, roots of unity, the discrete Fourier transform	HW3 due
28^th Oct	Integers polynomials and matrices: The FFT algorithm, its analysis and variants.
29^th Oct.	Graph Algorithms: Representation of graphs, the adjacency matrix and the adjacency list, the breadth first search algorithm
30^th Oct.	Graph Algorithms: The depth fast search and topological sorting
4^th Nov	Graph Algorithms: Minimal Spanning trees
6^th Nov	Graph Algorithms: Shortest path algorithms	HW 4 due
11^th Nov	Dynamic Programming
13^th Nov	Dynamic Programming
18^th Nov	Intractable problems
20^th Nov	Intractable problems
24^th Nov	Review
28^th Nov	Test 2
3^rd Dec	Closing!!