CS 455-3
Design and Analysis of Computer Algorithms
Catalog Description
An extensive treatment of the design, analysis and complexity of algorithms. Lower bound arguments, divide-and-conquer techniques, greedy algorithms, dynamic programming, graph theoretic algorithms, PRAM algorithms, and NP-completeness and approximation algorithms.
Prerequisite:
330 with a grade of C or better or graduate standing.
Objectives
This course is designed to give students a basic understanding of the concepts of algorithm design. Techniques leading to the design of efficient algorithms and methods for analyzing the complexity of these algorithms are discussed. These objectives are pursued by considering various algorithms for real problems that arise frequently in computer applications. Algorithms are designed with an emphasis on data structure selection and the space and time requirements of the algorithm. The concepts of NP-completeness and approximation algorithms are introduced.
Course Outline
| Lectures | ||
| 1. | Mathematical preliminaries, principles and examples of algorithm analysis.
Average case analysis. Worst case analysis. |
4 |
| 2. | Lower Bounds
lower bounds for finding minimum and sorting, lower bound arguments. |
4 |
| 3. | Divide-and-conquer
mergesort, quicksort, median selection, polynomial algorithms, matrix algorithms. |
8 |
| 4. | Greedy Algorithms
elements of the greedy strategy, minimum spanning tree, shortest path. |
4 |
| 5. | Advanced Graph Algorithms
biconnected components, strongly connected components, flow algorithms. |
4 |
| 6. | Dynamic Programming
optimal matrix multiplication, optimal search trees, approximate string matching, Floyd's algorithm. |
6 |
| 7. | NP-completeness and approximation algorithms. | 6 |
| 8. | PRAM algorithms. | 4 |
| Total | 40 | |