Design and Analysis of Algorithms (Aug-Dec 2008)

Instructor:                   Dr. Debrup Chakraborty  (debrup(AT)

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)

26th 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.


28th 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


11th Sept.

Mathematical Preliminaries: Order of growth:  Oh, Theta and Omega;


18th Sept.

Mathematical Preliminaries: Basic Counting: Permutations, Combinations, Binomial Coefficients. Recurrence Relations: Legal code-words, Fibonacci sequence, solving recurrences, the golden ratio.

HW1 due

20th 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.


23rd Sept.

Mathematical Preliminaries:  Recurrence relations: Using the master theorem. Counting: Definition of functions, countable sets, the pigeonhole principle with examples.


25rd  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

30th Sept

Sorting:  The heapsort algorithm and its analysis, the use of heap as a priority queue.


2nd Oct.

Sorting: The quick sort algorithm, the partition procedure with a randomized pivot. Worst case analysis, intuition for the average case.

HW2 due

7th  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. 


9th Oct.

Integers Polynomials and Matrices: Introduction to Rings and fields with examples.


14th Oct.

Integers,  polynomials and Matrices: Algorithms for arithmetic on large integers


15th Oct.

Tutorial: Discussion on HW 1 and 2


16th. Oct.

Tutorial: Problem solving


21st Oct.

Test 1

23rd Oct.

Integers polynomials and matrices: Polynomials, coefficient and point value representation of polynomials, roots of unity,  the discrete Fourier transform

HW3  due

28th Oct

Integers polynomials and matrices: The FFT algorithm, its analysis and variants.

29th Oct.

Graph Algorithms: Representation of graphs, the adjacency matrix and the adjacency list, the breadth first search algorithm


30th Oct.

Graph Algorithms: The depth fast search and topological sorting


4th Nov

Graph Algorithms: Minimal Spanning trees

6th Nov

Graph Algorithms: Shortest path algorithms

HW 4 due

11th Nov

Dynamic Programming


13th Nov

Dynamic Programming


18th Nov

Intractable problems

20th Nov

Intractable problems


24th Nov



28th Nov

Test 2


3rd Dec