CSCI 8080
DESIGN AND ANALYSIS OF ALGORITHMS

 


Prerequisites:

Graduate status and a satisfactory grade in CSCI 3320.

Credit Hours:

Three credits.

Audience:

Graduate students in computer science, mathematics and related fields.

Objectives:

The main objective of this course is to provide a deep and thorough understanding of the basic concepts of problem solving using computer systems.  To achieve this goal, the course introduces in details the fundamental results in the area of algorithm analysis and design.  Several computer models are introduced to analyze the performance of algorithms.  The course covers the main algorithmic techniques along with a sampling of the applications to which these techniques can be applied.  The course also includes an introduction to the theory of NP-completeness and complexity hierarchies.

Contents and Organization:

The course covers the basic concepts related to the design and analysis of computer algorithms as well as several selected advanced concepts.  The main topics covered in the course may be summarized as follows.

  • General background in algorithms, mathematical foundation, and data structures
  • Advanced techniques for sorting and order statistics
  • Basic algorithmic techniques
  • Advanced data structures for disjoint sets
  • Graph algorithms
  • Approximation algorithms
  • The Theory of NP-Completeness
  • String matching
  • Algorithms for parallel computing
Teaching Methodology:

The coverage will be primarily through lectures, with homework assignments and student projects.

Evaluation:

Course grade will be based on exams, homework assignments and projects.  No student will pass the course without attempting all exams and submitting at least 80% of the homework.

  • Midterm (100 pts)
  • Homework (150 pts)
  • Quizzes (0-30 pts)
  • Project (100 pts)
  • Final exam (150 pts)
Project Ideas:
  • Graph Algorithms
  • Heuristic search techniques in AI applications
  • Algorithms for the design of integrated circuits
  • Parallel Algorithms
  • Approaches for solving routing problems in networks
  • Scheduling techniques for applications in field X
  • Scheduling algorithms
  • Genetic algorithms
  • Evolution based approaches for solving problems in X
  • An in-depth study of complexity analysis
  • NP-completeness
Text Book:
  • T. Cormen, C. Leiserson and R. Rivest, Introduction to Algorithms, McGraw-Hill, 1991.  (Selected sections from the following chapters 1-5, 6-10, 12-14, 16-18, 19, 22, 23-26, 36-37, 34, 30)
References:
  • Alfred Aho, John Ullman and Jeffery Hopecraft, "The Design and Analysis of Computer ALgorithms, " Addison-Wesley,1974.
  • Gregory Rawlins, "Compared to What?," Computer Science Press, 1992.
  • Ellis Horowitz and Sartaj Sahni, "Fundamentals of Computer Algorithms," Computer Science Press. 1984.
  • Robert E. Tarjan, "Data Structures and Network Algorithms," SIAM, 1983.
  • Michael Garey and David Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness,' W. H. Freeman and Company, 1979.
  • Selim Akl, "The Design and Analysis of Parallel Algorithms," Prentice-Hall, 1989.
  • Hesham H. Ali and Naveed Sherwani, "Introduction to Graph Algorithms," to be published by John Wiley & Sons.
  • Martin C. Golumbic, "Algorithmic Graph Theory and Perfect Graphs," Academic Press, 1980.
  • Robin J. Wilson and John J. Watkins, "Graphs: An Introductory Approach," John Wiley & Sons, 1990.
  • J. A. Bondy and U. S. R. Murty, "Graph Theory with Applications," North Holland, 1985.