Computer Science Department - Technischen Universität München Chair for Efficient Algorithms

Internet Algorithmics (SS 04)

• Lecturer:
  Prof. Dr. Ernst W. Mayr
  Dr. Sven Kosub

• Area:
  4+2 lectures per week in area III (Theoretical Computer Science)
  advanced course, area algorithms

• Time and Place:
  Tuesday, 11:15-12:45, MI 00.04.011
  Wednesday, 12:15-13:45, MI 00.04.011

• Exercises:
  2 hours per week accompanying the lectures
  Tuesday, 13:15 - 14:45 Uhr, Room MI 00.13.037
  Teaching Assistant: Moritz G. Maaß
  

• Audience:
  graduate students of computer science
  students with computer science as minor
  

• Prerequisites:
  1st and 2nd year courses
  course Efficient Algorithms and Data Structures I
  course Internet Protocols advantageous but not necessary

• Recommended for:
  in-depth knowledge in topic Algorithms
  in-depth knowledge in topic Computer Networks

• Contents:
  

  Topics covered so far (as of July 20, 2004)

  1. Introduction
  1. Internet: concepts and definitions
  2. Internet applications
  3. Combinatorial problems
  4. Algorithmic techniques
  5. Course outline
  1. Internet analysis
  2. Analyzing data
  1. Algorithms on texts
  1. Definitions and notations
  2. A simple algorithm for exact pattern matching in texts
  3. Knuth-Morris-Pratt algorithm
  4. Boyer-Moore algorithm
  5. Approximate pattern matching in texts
  2. Algorithms on hypertext
  1. Manber-Wu hypertext model
  2. Exact pattern matching in hypertext
  3. Approximate pattern matching in hypertext
  4. Navarro algorithm
  3. Algorithms on data streams
  1. Processing models and complexity measures
  2. Fischer-Salzberg algorithm
  3. Estimating frequency moments
  4. Algorithms for monitors
  1. Processing models
  2. Exponential histograms
  3. Maintaining variances
  3. Analyzing networks
  1. Reconstructing network topologies
     1. Dimensioning and locating monitors
     2. Graph realization of degree sequences
     3. Graph realization of distance matrices
  2. Structural centrality
     1. Indexes of structure
     2. Distance-based centrality
     3. Feedback-based centrality
  3. Internet hierarchies
     1. An abstract model for BGP
     2. Combinatorial type-of-relationship inference

  Further topics:

  2. Managing the Internet efficiently
  3. Content delivery on the Internet
  4. Information retrieval on the Internet
  5. Internet privacy and security

• Related and Advanced Courses:
  Efficient Algorithms and Data Structures
  Computer Networks

• Lecture Notes:
  Lectures notes will be produced in parallel with the lectures.

• References:
  The course is based on recent research papers which are not yet contained in a textbook.

• Office Hours:
  look here