back to cs512-syllabus

CS512 - Teaching Material - Fall 2004

Lectures

  1. 9/27/2004: Review on the foundations. Computation of the modular exponentiation through the Repeated Squaring Method.

    Reading Assignment: Up to lecture 7 from cs312-s04.


  2. 9/29/2004: (updated Thu, 2:45pm) Asymptotic Notation. Divide and Conquer recurrence relations. The Master Method. The Divide and Conquer design technique. Examples: Mergesort. More general recurrence relations: the Akra-Bazzi method. Proof of the Akra-Bazzi method.

    Exercises: Analyze algorithm Stooge-Sort (Chapter 7, page 161) and write a nonrecursive version of the repeated squaring method algorithm (see notes).


  3. 10/4/2004: Approximations of sums. The method of the integral. Elements of enumerative combinatorics. Formal Power series. Ordinary Generating functions (OGF) and Exponential Generating Functions (EGF). Convolutions. Harmonic numbers. Counting the number of binary trees. Catalan Numbers.

    Exercises: Use OGFs to solve the Fibonacci recurrence relation. Analyze the complexity of the Factorial algorithm assuming a quadratic algorithm for the multiplication of integers.


  4. 10/6/2004: Randomized QuickSort. The QuickSort equation. Solution of the QuickSort equation using OGFs. Analysis of the complexity of the Factorial algorithm assuming a quadratic (suboptimal) algorithm for the multiplication of integers.

  5. 10/11/2004: Bernoulli Numbers. Bernoulli Polynomials. The Euler-MacLaurin Summation Formula. Asymptotic approximations of factorials and Harmonic numbers. Stirling constant and the Euler-Mascheroni constant.

    6. 10/13/2004: Midterm 1

  6. 10/18/2004: More on Asymptotic Approximations. Absolute error and relative error. Timing the execution of a Java program. Theory and experiments: minimizing the square error.

  7. 10/20/2004: Recursion revisited. Memoization. Introduction to Dynamic Programming. Principle of suboptimality. The Matrix-chain Multiplication Problem.

  8. 10/25/2004: Review of the midterm examination. Backtracking algorithms.

  9. 10/27/2004: Overview on exam topics. Numerical Algorithms. Computation of the square root of a real number using Newton's method. Gradient Descent Methods.

  10. 11/1/2004: All-pairs shortest Path algorithms. The Matrix multiplication algorithm and the Floyd-Warshall Algorithms (Textbook: 25.1 and 25.2).

  11. 11/3/2004: Advanced Data Structures: Binary Heaps, Priority Queues and Binary Search Trees.

  12. 11/8/2004: Analysis of the average height of randomly built binary search trees (cp.12.4). Balanced trees: AVL and Red Black trees (cp.13).

  13. 11/10/2004: Insertion in AVL balanced trees. Rotations. Fibonacci trees. Insertion in Red Black trees. Analysis of the black height of a Red Black tree. Combinations of binary search trees and heaps: Treaps.

  14. 11/15/2004: Markov Chains. Stochastic matrices and transition graphs. Limit Distribution and Ergodicity. Irreducibility and Aperiodicity.

    Reading Assignment: Markov chains and Hidden Markov Models.


  15. 11/17/2004: Stationary Markov Chains. Limit Distribution and stationary distribution. Hidden Markov Models (HMMs). Three classical problems about HMMs. Dynamic programming solution to problem 1.

  16. 11/22/2004: The problem of State estimation in Hidden Markov Models (Problem 2). The Viterbi algorithm.

  17. 11/24/2004: Evaluation and interpolation of polynomials. The Vandermonde matrix and Vandermonde transformations. Convolution theorem. The Fourier matrix and the Discrete Fourier Transform (DFT). Fast computation of the DFT: the Fast Fourier Transform (FFT).

Student Presentations:

  1. 11/29/2004: Search Engines. Page ranking techniques: determination of Hubs and Authorities, LSI and cosine distance. Google (updated).

  2. 12/1/2004: Singular Value Decomposition and LSI.

  3. 12/2/2004: Number Theory and Cryptography. Primality is in P.

  4. 12/6/2004:DNA Computing and Quantum Computing.

Download latex file template.tex.

Important Deadlines

Packages