Lectures Discrete Structures Efficient Algorithms and
Data Structures I Randomized Algorithms Proseminar Proofs from The Book Lab Course Algorithmen-Entwurf Courses for PhD Students Oberseminar

Randomized Algorithms

• Lecturer:
  Prof. Dr. Ernst W. Mayr
• Module:
  IN2160, TUMonline
• Area:
  4+2 lectures per week in area III (Theoretical Computer Science)
  core course, topic algorithms
• Time and Place:
  Tuesday, 08:00–10:00, 00.13.009A
  Thursday, 08:00–10:00, 00.13.009A
  Attention: Room change (for February 2, 2012 only): Room E.126, IMETUM, ZIMT!
  Attention: Because of Dies Academicus there will be no lecture on Th. 8th December!
  Attention: Room change (for October 18, 2011 only): Room MI 00.08.038!
• Exercises
  2 hours per week exercises accompanying the lectures
  Teaching Assistant: Jeremias Weihmann
• Exam:
  The exam will take place on Mo. 6th February 2012 from 16:15 to 19:15 in room 5510.01.050 (MW 1050, Johann-Bauschinger-Zeichensaal).
  The mentioned time is the net process time. Please attend 15 minutes before.
  The only permitted aid is an A4-page that contains notes written on both sides by your own hand. (Printers are not allowed.)
• Exam Review Meeting:
  The Exam Review Meeting will take place on Tue. 14th February 2012 from 16:15 to 16:45 in room 03.11.018.
• Repeat exam:
  The repeat exam will take place on Mo. 2th April 2012 from 14:15 to 17:15 in room 03.11.018.
  The mentioned time is the net process time. Please attend 15 minutes before.
  The only permitted aid is an A4-page that contains notes written on both sides by your own hand. (Printers are not allowed.)
• Audience:
  graduate students of computer science
  students with computer science as minor
• ECTS: 8 Punkte
• Prerequisites:
  1st and 2nd year courses
  Course Efficient Algorithms and Datastructures I advantagious, but not necessary.
• Recommended for:
  Fundamental knowledge in algorithms
• Contents:
  During the last years efficient algorithms have been discovered for various problems which outperfom deterministic algorithms with respect to system and/or time resources. Often randomized algorithms are also much easier to implement and analyze than their deterministic counterparts.
  In this lecture we will present basic principles for the design of randomized algorithms.
• Lecture Notes: Lecture notes (in German) will be provided on the German form of the webpage (click on the German flag).
• Content of the lecture so far (the lecture roughly follows the book of Motwani and Raghavan, see literature)
  

  Date	Ch.	Sec.	Subs.	Topic
  18.10.2011:		0		Organization of the course
  		1		Planned topics of the course
  		2		Literature
  	I	1		Paradigms of Randomized Algorithms
  20.10.2011				(Continued)
  		2		What’s not in the course
  		3		Simple Examples
  			1	Randomized Quicksort
  25.10.2011				(Continued)
  			2	Min-Cut
  			3	Binary Planar Partition
  27.10.2011				(Continued)
  			4	Secretary Problem
  			5	Matrix Multiplication (Fingerprinting)
  03.11.2011			6	Game Tree Evaluation
  		4		Las Vegas vs. Monte Carlo
  		5		A Probabilistic Recurrence
  08.11.2011		6		Machine Models and Complexity Classes
  			1	Turing Machines and RAMs
  			2	Languages and (Decision) Problems
  			3	Complexity Classes
  10.11.2011			4	Reductions
  15.11.2011			5	Probabilistic Complexity Classes
  17.11.2011			6	(Randomized) Boolean Circuits and Uniformity
  19.11.2011				(Continued)
  			7	A simple derandomization
  	II			Moments and Deviations
  		1		Occupancy problems
  			1	Balls into bins
  24.11.2011				(Continued)
  			2	Birthdays
  		2		Markov and Chebyschev Inequalities
  		3		Two-Point Sampling and Probability Amplification
  				(Continued)
  29.11.2011		4		Principle of Deferred Decisions
  			1	Clock Solitaire
  			2	Stable Marriage Problem
  01.12.2011				(Continued)
  			3	Coupon Collector’s Problem
  03.12.2011				(Lecture cancelled)
  13.12.2011				(Continued)
  	III			Tail Inequalities
  		1		Chernoff Bounds
  15.12.2011				(Continued)
  20.12.2011				(Continued)
  		2		Routing in a Parallel Computer
  22.12.2011				(Continued)
  10.01.2012				(Continued)
  		3		A Wiring Problem
  12.01.2012				(Continued)
  		4		Martingales
  17.01.2012				(Continued)
  19.01.2012	IV			The Probabilistic Method
  		1		Game tree and set balancing revisited
  		2		Max-Cut
  		3		k-Max-SAT
  24.01.2012				(Continued)
  		4		Probabilistic construction and existence
  			1	Expanding graphs
  			2	Probability Amplification

• References:
  

  Downloadable Literature

  R. Motwani, P. Raghavan:

  Randomized Algorithms
  Cambridge University Press, 1995.

  C. Scheideler:

  Probabilistic Methods for Coordination Problems
  HNI-Verlagsschriftenreihe, Band 78, 2000.

• Office Hours:
  look here