15-853: Algorithms in the "Real World"
Carnegie Mellon University, Computer Science Department
Fall 2003

Fluid Flow Image

Instructors: Guy Blelloch and Bruce Maggs
Time: Monday and Wednesday 1:30 - 2:50 (1st class, Wednesday Sept. 3)
Place: 5409 Wean Hall
Credit: 12 Units
Prerequisites: An advanced undergrad course in algorithms (15-451 or equivalent will suffice).
Office Hours: TBA
  • Course overview and topic list.
  • Readings, Notes and Slides
  • Course Requirements and Grading Criteria.
  • Approximate schedule.
  • Assignments.
  • Information on algorithms available on the web
  • Companies that sell products that use various algorithms
  • Class List

    • Course Overview:

    This course covers how algorithms and theory are used in "real-world" applications. The course will cover both the theory behind the algorithms and case studies of how the theory is applied. It is organized by topics and the topics change from year to year.

    This year we will cover the following topics. The exact subtopics might change

  • Cryptography
    One-way functions, basic protocols
    Number theory review: groups, fields, Galois fields
    Private key cryptosystems (Block Ciphers, Rijdael)
    Public key cryptosystems (SSL, RSA, ElGamal, Diffie-Hellman key exchange)
    Kerberos and Digital Cash

  • Error Correcting Codes
    Hamming Codes, Linear Codes
    Reed Solomon Codes, Cyclic Codes (uses in CDs, DVDs, DSL, ...)
    Expander graphs and Tornado codes

  • Graph Separators
    Definitions, Planar graph separators
    General graph separators
    Applications to linear-systems solving and graph compression

  • Linear and Integer programming
    Flow problems as Linear programs
    Simplex, Elipsoid and Interior point methods
    Reductions to integer programs
    Basic techniques for solving integer programs
    Airline crew scheduling

  • Web Algorithms
    Inverted indexes and searching
    Google page-rank and Hubs and Authorities
    Near duplicate removeal

    • A small sample of companies that sell products that use various algorithms:

    Optimization
    Geometry and Meshing
    Biology
    Cryptography
    CPLEX
    CAPS Logistics
    IBM OSL
    Astrokettle
    APC
    Carmen Systems
    Lindo Systems
    LogicTools     		Fluent
    Geomagic
    Pointwise
    Ansys
    FEGS
    CFDRC
    Marc
    Femsys
    AVL     		Celera
    Curagen
    HGSI
    MLNM
    Hyseq
    Genset
    Incyte
    Variagenics     		Algorithmic Research
    RSA Security
    Entrust
    Cryptomathic
    Netegrity
    InterTrust
    Zero Knowledge
    Mach 5
    Trick's List Owen's List Netsci's list Rivest's List

    Requirements and Grading Criteria

    TBA

    Assignments

  • Assign 1: Cryptography (ps and pdf), solution (ps and pdf) : Due Sep 24, 2003

  • Assign 2: Error Correcting Codes (ps and pdf), solution (ps and pdf) : Due Oct 8, 2003

  • Assign 3: Graph Separators (ps and pdf), : Due Oct 29, 2003

    Notes on solving recurrences using the "Akra-Bazzi" method and examples. See also Cormen, Leiserson, and Stein, pp. 62-90.

  • Assign 4: Linear/Integer Programming (ps and pdf), : Due Nov 19, 2003

    • Relevant Books

    See the lists within each of the topic pages

    Help on giving presentations:

  • How to Present a Paper in Theoretical Computer Science, by Ian Parberry.
    • Guy Blelloch, guyb@cs.cmu.edu.