Algoritmik 2000 (dAlg)

Indholdsfortegnelse til noter ps-version,pdf-version.

• A self-adjusting data structure - Splay Trees.ps-version, pdf-version.
  • Splay Trees
    • Splay Trees
    • Implementation of splay
    • Analysis
    • Problems
    • Appendix
• Introduction to algebraic algorithms. ps-version, pdf-version
  • Matrix multiplication
    • Strassen multiplication
  • Polynomials
    • Representations
    • Operations
      • Product (Convolution)
      • Division
    • The discret Fourier transform
      • Harmonic analysis - discret Fourier transform revisited
    • Problems
    • Appendix (proof of Lemma 3.2)
• Introduction to parallel algorithms. ps-version, pdf-version.
  • Models
  • Time, work and optimality
    • Brent's scheduling principle
  • Merging and sorting
    • Prefix computations
    • Merge on a CRCW-PRAM
    • Bucket- and radix-sort
    • Bucket- and radix-sort on an EREW-PRAM
  • Simulation of CRCW-PRAMs on EREW-PRAMs
  • Problems
• Introduction to lower bounds. ps-version, pdf-version.
  • Adversary arguments
  • Counting arguments
    • Linear computation trees
    • Applications
    • Generalisations
    • Problems

Sidst opdateret af Sven Skyum (sskyum@daimi.aau.dk) 26-1-00.