CISC 621: Algorithm Design and Analysis

Catalog Description:
Emphasis on developing expertise in the design and analysis of algorithms. Equal importance given to techniques and specific algorithms. Particular topics include advanced data structures, graph algorithms, disjoint set manipulation, sorting and selection, amortized analysis, NP-completeness, and matrix and polynomial multiplication.

Current Texts:
Introduction to Algorithms
Cormen, Leiserson, and Rivest
McGraw-Hill

Goals:
The fundamental methods for designing good algorithms in both theory and practice are studied, together with the methods for analyzing time and space demands of algorithms. Important algorithms of data access, graphs, and algebraic structures are studied. Computational complexity classes are introduced. Approximation methods and probabilistic methods for hard problems are considered.

Content:

• Review of mathematical techniques for the analysis of algorithms.
• Algorithm strategies: divide and conquer, balancing, dynamic programming
• Sorting and order statistics: fast algorithms for sorting, for median
• Stored data access: hashing, trees, balanced tree structures, dictionaries
• Graph algorithms: path finding, shortest path, transitive closure
• Fast fourier transform and its applications
• Introduction to the complexity hierarchy: Nondeterministic models, the classes P and NP, NP completeness, the reduction of one problem to another, exponentially hard problems.

Required Background: CISC 220 (Data Structures), CISC 320 (Algorithms and Advanced Programming) and Math 215 (Discrete Mathematics).

Helpful Background: An undergraduate course on algorithms, and/or one on logic. A strong background in mathematics (analysis and algebra) is helpful but not assumed.