Reading Assignment: Up to lecture 7 from cs312-s04.
4/4/05:
Sorting. Decision Trees. Lower bound to the comparisons-based sorting
problem. Sorting in linear time. Order Statistics. Computing the
median in worst-case linear time.
4/6/05: Analysis of
algorithm select. Solving recurrence relations by substitution.
4/11/05: Randomized
algorithms and probabilistic analysis. Indicator random
variables. The hire-assistant algorithm. Generating random
permutations in linear time.
4/13/05: More on the
generation of random permutations in linear time. The birthday
paradox.
4/20/05: Least Squares
method. Experimental analysis of the complexity of an algorithm.
4/25/05: Solving overdetermined linear systems and the
Least Squares method. A randomized algorithm for the Median.
4/27/05: Randomized Quicksort. Analysis of the expected
running time.
5/4/05: The Quicksort equation. Ordinary Generating
Functions (OGF). Solving recurrences using OGFs. The OGF of the
Fibonacci Numbers. Counting the number of binary trees. Catalan
Numbers.
5/9/05: Solving linear (homogeneous) recurrences of
arbitrary order with OGFs. Solving the Quicksort equation using
OGFs.
5/11/05: Generalities on Data Structures. Specification of
Adt's. Implementation and OOP.
5/16/05: Review of the midterm examination.
download assignment.
5/18/05: The Dictionary Adt. Binary Search Trees (BST)
implementation. Analysis of the height of randomly built
BST. Definition of AVL balanced trees. Fibonacci
Trees. Rotations. RedBlack trees: insertion in RB trees.
Reading assignment: the Java Collections Framework, interface Set and
class TreeSet.
5/23/05: The Horner method. Evaluation/Interpolation of
polynomials. The Vandermonde matrix and the Vandermonde
transform. Convolution Theorem. The Fourier matrix. Properties of the
(principal) n-roots of unity. Discrete Fourier Transform
(DFT). Efficient computation of the DFT: the FFT.
5/25/05: Summary on Algorithmic Design Techniques:
Divide-and-Conquer, Greedy and Dynamic Programming. The principle of
suboptimality. Single source-all destinations Shortest paths problem:
the Dijkstra algorithm. Indirect min-heap implementation. Minimum
Spanning Trees: the Kruskal's algorithm. Union-find
implementation. The all-pairs shortest path problem. Matrix
multiplication and shortest paths. The Floyd-Warshall algorithm.
6/1/05: Presentation: Kolmogorov Complexity, Lempel-Ziv
coding and Quantum Computing.
Herbert Wilf. Generatingfunctionology.
Academic Press, 1994. A book on Generating Functions available on line
(please read copyright note).
R. Sedgewick and Philippe Flajolet. Analysis of
Algorithms. Addison-Wesley, 1996. (OGF, QuickSort equation, Catalan Numbers)
Thomas M. Cover, Joy A. Thomas. Elements of Information
Theory. Wiley and Sons, Inc., 1991. (Information, Entropy, Data
compression, Kolmogorov Complexity, Universal Coding)