Design and
Analysis of Algorithms (AugDec 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:0010:00
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 )
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^{th }Sept. 
Mathematical
Preliminaries:
Basic Counting: Permutations, Combinations, Binomial
Coefficients. Recurrence Relations: Legal codewords, 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!! 