 CISC-466/3.0 Algorithms II

Original Author: Selim Akl
Last Revised: September 25, 2006

Calendar Description

A continuation of CISC 365/3.0. Lower bound theory. Average-case analysis of algorithms. Approximation algorithms. Probabilistic algorithms. Parallel algorithms.

Prerequisite: CISC 365/3.0.

Objectives

Why take CISC-466? This is your last chance in this program to:

• understand the theory behind algorithmic techniques encountered in earlier introductory courses, such as dynamic programming, the greedy method, and approximation algorithms;
• become familiar with certain advanced algorithms with far reaching applications in business (linear programming), in engineering (matrix algorithms and the fast Fourier transform), and in computer security (number theoretic algorithms);
• learn several algorithm design and analysis approaches that are fundamental in today's computing, including string matching (of great importance in bioinformatics), computational geometry (with applications in graphics and image recognition), and amortized analysis.

Topics

Theoretical Foundations for Dynamic Programming (1 week)

• Elements of dynamic programming
• The principle of optimality

Theoretical Foundations for Greedy Methods (1 week)

• Elements of the greedy strategy
• Matroids

Amortized Analysis of Algorithms (1 week)

• The aggregate method
• The accounting method
• The potential method
• Dynamic tables

Sorting Networks (1 week)

• Comparison networks
• The 0-1 principle
• Examples of sorting networks

Matrix Operations (1 week)

• Fast matrix multiplication
• Parallel algorithms

Linear Programming (1 week)

• The simplex algorithm
• Duality

Polynomials and the Fast Fourier Transform (1 week)

• The discrete Fourier transform (DFT)
• Efficient implementation
• Circuits for the DFT

Number-Theoretic Algorithms (1.5 week)

• The RSA public-key cryptosystem
• Primality testing
• Integer factorization

String matching (1 week)

• The Rabin Karp algorithm
• The Knuth-Morris-Pratt algorithm

Computational Geometry (1.5 week)

• Segment intersection
• Convex hulls
• Closest pair

Approximation Algorithms (1 week)

• Vertex cover
• Traveling salesperson
• Subset-sum

Possible textbooks

Primary

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd edition, The MIT Press (Cambridge, Massachusetts)/McGraw-Hill (New York), 2009.

Secondary

• J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley (Boston, Massachusetts), 2006.
• D. S. Hochbaum, ed., Approximation Algorithms for NP-hard Problems, PWS Publishing (Boston, Massachusetts), 1997.