Probability Basics
Sample space, events, P(A or B), P(A and B), complement rule, and independent vs dependent events.
Lessons
1. Intro
(The Goal)
2. Sample Space
(All possible outcomes)
3. Outcomes
(Individual results)
4. Events
(Subsets of the sample space)
5. Probability Formula
(Favorable over total)
6. Example - Rolling a Die
(Probability of rolling > 4)
7. Probability Bounds
(Always between 0 and 1)
8. Complement Rule
(Probability of "not A")
9. Example - Complement
(At least one head in 3 flips)
10. Union of Events
(A or B happens)
11. Addition Rule
(P(A or B) formula)
12. Intersection of Events
(A and B both happen)
13. Example - Union and Intersection
(Card draw probabilities)
14. Mutually Exclusive Events
(Cannot happen together)
15. Example - Mutually Exclusive
(Rolling 2 or 5)
16. Independent Events - Intro
(One does not affect the other)
17. Multiplication Rule
(P(A and B) for independent events)
18. Example - Independent Events
(Two dice rolls)
19. Dependent Events - Intro
(One affects the other)
20. Conditional Probability
(Probability given something happened)
21. Example - Conditional Probability
(Cards without replacement)
22. General Multiplication Rule
(Works for dependent events)
23. Quiz: Basic Probability
(Knowledge check)
24. Expected Value - Intro
(Average outcome over many trials)
25. Expected Value Formula
(Weighted average)
26. Example - Expected Die Roll
(Fair six-sided die)
27. Expected Value - Unfair Outcomes
(Different probabilities)
28. Applications in CS
(Why probability matters)
29. Randomized Algorithms
(Using probability for speed)
30. Hash Collisions
(Birthday paradox in hash tables)
31. Problem - Two Dice Sum
(Read statement)
32. Two Dice - Sample Space
(36 outcomes)
33. Two Dice - Event
(Sum equals 7)
34. Two Dice - Answer
(P = 1/6)
35. Problem - Birthday Paradox
(Read statement)
36. Birthday - Complement Approach
(Easier to count no match)
37. Birthday - Calculation
(Multiply probabilities)
38. Birthday - Insight
(Why it is surprising)
39. Problem - Weighted Random
(LeetCode 528)
40. Weighted Random - Idea
(Convert weights to ranges)
41. Weighted Random - Prefix Sum
(Build cumulative array)
42. Weighted Random - Binary Search
(Find the range)
43. Weighted Random - Implementation
(Python code)
44. Quiz: Independence and Expected Value
(Knowledge check)
45. Practice Problems
(Apply what you learned)
46. Problem - Linked List Random Node
Uniform random selection
47. Linked List Random Node - Insight
Reservoir sampling idea
48. Linked List Random Node - Implementation
The pseudocode
49. Problem - Shuffle an Array
Fair randomization
50. Shuffle - Fisher-Yates Algorithm
The standard solution
51. Shuffle - Implementation
The code
52. Lessons from Shuffle
summary
53. Problem - Random Pick with Weight
Weighted random selection
54. Weighted Pick - Prefix Sum
Converting weights to ranges
55. Weighted Pick - Binary Search
Finding the target range
56. Weighted Pick - Implementation
The code
57. Lessons from Weighted Pick
summary
58. Problem - Random Pick Index
Reservoir sampling variant
59. Pick Index - Reservoir Sampling
Fair selection in one pass
60. Pick Index - Implementation
The code
61. Lessons from Pick Index
summary
62. Section Recap
What we learned