ANTICIPATED LECTURE TOPICS

  • Part I: BASIC PROBABILITY

    • [Tues Jan 15] Introduction, Review of math prereqs
    • [Thurs Jan 17] Probability on events
    • [Fri Jan 18] Recitation:
    • [Tues Jan 22] Discrete Random Variables, Expectation, Conditional Probability, Conditional Expectation
    • [Thurs Jan 24] Expectation via Conditioning, Linearity of Expectation
    • [Fri Jan 25] Recitation:
    • [Tues Jan 29] Variance; Random Sums of Random Variables
    • [Thurs Jan 31] Z-transform
    • [Fri Feb 1] Recitation:
    • [Tues Feb 5] Continuous Random Variables
    • [Thurs Feb 7] Pareto distribution
    • [Fri Feb 8] Recitation: Generating Random Variables for Simulation
    • [Tues Feb 12] Laplace transform
    • [Thurs Feb 14] Normal distribution and Central Limit Theorem
    • [Fri Feb 15] Recitation:
    • [Tues Feb 19] MIDTERM 1

  • Part II: RANDOMIZED ALGORITHMS

    • [Thurs Feb 21] Introduction to Randomized Algs -- Quicksort, Linear Search
    • [Fri Feb 22] Recitation: Discussion of Midterm 1 solutions
    • [Tues Feb 26] Easy Randomized Algs -- Skip Lists, Min Cut
    • [Thurs Feb 28] Convex Hull and Hashing
    • [Fri Mar 1] Recitation:
    • [Tues Mar 5] Probabilistic Method
    • [Thurs Mar 7] Markov and Chebyshev Inequalities with Applications
    • [Fri Mar 8] NO CLASSES MID-SEMESTER BREAK
    • [Tues Mar 12] NO CLASS SPRING BREAK
    • [Thurs Mar 14] NO CLASS SPRING BREAK
    • [Fri Mar 15] NO CLASS SPRING BREAK
    • [Tues Mar 19] Chernoff Bounds I
    • [Thurs Mar 21] Chernoff Bounds II
    • [Fri Mar 22] Recitation: Review of Chernoff
    • [Tues Mar 26] MIDTERM 2

  • Part III: MARKOV CHAINS & QUEUES

    • [Thurs Mar 28] Discrete time Markov Chains (DTMCs)
    • [Fri Mar 29] Recitation: Discussion of Midterm 2 solutions
    • [Tues Apr 2] DTMC II
    • [Thurs Apr 4] DTMC III
    • [Fri Apr 5] Recitation
    • [Tues Apr 9] DTMC IV
    • [Thurs Apr 11] PageRank + Back to Exponential
    • [Fri Apr 12] Recitation
    • [Tues Apr 16] Poisson Process
    • [Thurs Apr 18] NO CLASS -- CARNIVAL
    • [Fri Apr 19] NO RECITATION -- CARNIVAL
    • [Tues Apr 23] Continuous-time Markov chains
    • [Thurs Apr 25] M/M/1 + Little's Law
    • [Fri Apr 26] Recitation
    • [Tues Apr 30] M/M/k/k, PASTA
    • [Thurs May 2] M/M/k
    • [Fri] Recitation: Review for final

Click Here for homeworks: HOMEWORKS

Important Announcements:

  • Homework 1: Problem 2. Please assume that the probability of the intersection of the n events is > 0. Please use induction.
  • Homework 3: Problem 5. "Home" and "Sleep" are synonymous in this problem.
  • MIDTERM I: FEB 19th in class.
  • Homework 4: When writing code, use any language you like. When inserting code into your pdf, you will find it helpful to use \begin{verbatim} and \end{verbatim} and put the code in between these.
  • MIDTERM I: You are allowed to bring notes on one side of a 3x5 index card.
  • Extra office hours in GHC 7207 Sunday 3 p.m. - 5 p.m.
  • CHANGE OF SCHEDULE: We are ending Part II one lecture early. We are also moving up MIDTERM II by one class. MIDTERM II is now scheduled for Tuesday, March 26.
  • MIDTERM II: You are allowed to bring notes on one side of a 3x5 index card.
  • Part III of the class will cover Chapters 6-14 (or more) of "Performance Modeling and Design of Computer Systems," available on Amazon .
  • A cheaper way to buy the above book (for $60) is to go to the Cambridge University Press website: CUP and use the following discount code: L3PMDCS
  • Mor will be out of town and needs to move her office hours on March 26th to the same time (5:30 p.m.) on March 28th.
  • Mor will have EXTRA OFFICE HOURS tomorrow (Wednesday, March 20) from 11 a.m. - 12 p.m. in case more people need help on homework.