CISC466/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. Averagecase analysis of algorithms. Approximation algorithms. Probabilistic algorithms. Parallel algorithms.
Prerequisite: CISC 365/3.0.
Objectives
Why take CISC466? 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 01 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
NumberTheoretic Algorithms (1.5 week)
 The RSA publickey cryptosystem
 Primality testing
 Integer factorization
String matching (1 week)
 The Rabin Karp algorithm
 The KnuthMorrisPratt algorithm
Computational Geometry (1.5 week)
 Segment intersection
 Convex hulls
 Closest pair
Approximation Algorithms (1 week)
 Vertex cover
 Traveling salesperson
 Subsetsum
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)/McGrawHill (New York), 2009.
Secondary
 J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley
(Boston, Massachusetts), 2006.
 D. S. Hochbaum, ed., Approximation Algorithms for NPhard Problems,
PWS Publishing (Boston, Massachusetts), 1997.
