Dr. S. Rao Kosaraju - Instructor |

P.C. Shyamshankar (Shyam) - TA |

- Class
- Tuesdays & Thursdays, 13:30 to 14:45, at Shaffer 302.
- TA Office Hours
- Mondays 13:00, at Shaffer 201.
- Mid-Term Exam
- Thursday, October 25
^{th}2012, 13:30 to 14:45 (during class), at Shaffer 302. - Final Exam
- Friday, December 14
^{th}2012, 9:00 to 12:00, at Shaffer 302.

Assignment #01 |

Assignment #02 |

Assignment #03 |

Assignment #04 |

Assignment #05 |

Mid-Semester Exam |

Assignment #06 |

Assignment #07 |

Assignment #08 |

- Random Variables, and
*k*-wise independence; - Tail Inequalities - The Markov, Chebyshev and Chernoff Bounds;
- Design of simple randomized Algorithms;
- Linear Programming Relaxation and Randomized Rounding;
- Derandomization:
- The Conditioning Method;
- The Limited Independence Method;
- The Log-Space Verification Method;

- Existence Proofs;
- Universal Hashing
- Markov Chain Mixing:
- The Metropolis and Metropolis-Hastings Algorithms;
- The Coupling Method;
- The Eigenvalue Method;

- Counting Problems;
- Semi-Definite Programming;
- Lower Bound Arguments;
- Random Bit Generation;
- Appications of Expanders.

Fall 2011: Mid-Semester |

Fall 2010: Mid-Semester |

Spring 2010: Mid-Semester |

Fall 2011: Final |