Design and Analysis of Algorithm (CMPS 500)
Spring 2009

Time and Place

9:30 – 10:45 am on Tuesday and Thursday in ACTR 101

 

Instructor

Dr. Raja Loganantharaj
The Center for Advanced Computer StudiesContact: 482-5345 Voice and logan AT cacs.louisiana.edu (e-mail)

Teaching Assistant

Ms. Reshmi Nair Rajan
Office Hours: 9AM-12 Noon on Monday and Wednesday in ACTR 327
rxr0888 AT louisiana.edu(e-mail)

Prerequisites


Strong background in data structure and CMPS 341 or equivalent

Outline

The objectives of this course include

  • To teach the student the ability to understand research papers which include significant analysis of algorithms.
  • To develop the skill in analyzing running time of most algorithms and
  • To get familiar with several algorithm design techniques

The topics covered include

Review of Basics

 

Divide and Conquer

Ch 7 (Ref 1)

Sorting algorithms

Ch 6,7 and 8

Dynamic programming

Ch 15, Ch 8 (Ref 1)

Greedy algorithms

Ch 16, Ch 6 (Ref 1)

Amortized analysis

Ch 17

B-trees

Ch 18

Binomial heaps

Ch 19

Fibonacci heaps

Ch 20

Union-find

Ch 21

Strongly connected components

Ch 22, Sec 5

Shortest paths

Chs 24-25

Max flow

Ch 26

NP-completeness

Ch 34

Approximation algorithms

Ch 35

 

 

Text book and reading materials

1. Fundamentals of Algorithms Second Edition by T. H. Cormen, Charles E. Leiserson, R. L. Rivest and C. Stein MIT Press 2002

Reference Books

 1. Fundamental of Algorithms by G. Brassard and P. Bratley

2. Introduction to Design and analysis of Algorithm, by D. R. Stinson, 2 nd edition.

Evaluation

It is based on homework, quizzes mid term, final and a semester project. midterm 30%, Final 35%, homework 20%, project 10%, quizzes 5% and class participation 0 to -5%. Grades: A >85, B >75%, C>65%, D>55% and F is for the rest.

Cheating of any form will not be tolerated and the violators will be punished according to the rules set forth by the University of Louisiana.