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

Discrete Structures II (SS 03)

• Lecturer:
  Prof. Dr. Angelika Steger

• Area:
  3 lectures per week in undergraduate studies
  compulsory course

• Time and Place:
  

  Monday	10:00 - 12:00	MI 00.02.001
  Tuesday	10:00 - 11:00	MI 00.02.001

• Exercises:
  2 hours per week central exercises accompanying the lectures
  

  Friday

  13:15 - 14:45

  MI 00.02.001

  Teaching Assistants: Martin Marciniszyn, Alexander Offtermatt-Souza and Jan Remy
  

• Exams:
  There will be a midterm exam on 24.5.2003 and an endterm exam on 12.7.2003.
  In each exam a maximum number of 40 credits can be achieved. The total number of credits is determined as follows: total credits = 0.3 * midterm-credits + 0.7 * endterm-credits.
  To pass the course discrete structures II at least 17 total credits are required.
  
  The exam in the winter term 2003/04 will be on 17.10.2003. Additional information can be found here. To pass the exam at least 17 of 40 credits are required.
• Audience:
  undergraduate students of computer science

• Prerequisites:
  1st year courses

• Recommended for:
  Vordiplom

• Contents:
  
  • Finite probability spaces
    • Def. probability space, events, random variable
    • Some distributions
    • Markov and Chebychev inequalities
  • Infinite probability spaces
    • Normal distribution, exponential distribution
    • Central limit theorem
  • Stochastic processes
    • Markov chains
    • Queues
  • Statistics
    • Estimation variables
    • Confidence intervals
    • Checking of hypotheses

• Related and Advanced Lectures:
  Graduate courses

• Lecture Notes:
  Not available.

• References:
  [1] T. Schickinger, A. Steger: Diskrete Strukturen - Band 2, Springer Verlag 2001
  [2] M. Greiner, G. Tinhofer: Stochastik für Informatiker, Carl Hanser Verlag, 1996
  [3] H. Gordon: Discrete Probability, Springer-Verlag, 1997
  [4] R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, 1995
  [5] L. Fahrmeir, R. Künstler, I. Pigeot, G. Tutz: Statistik - Der Weg zur Datenanalyse, Springer-Verlag, 1997
  
  Note: Due to the price (of approx. 20 Euro) the Springer-Verlag rejected to give student discount for book [1].
  

• Office Hours:
  look here