1 of 142

Algorithmic Analysis

Chris Gregg

CS109, Stanford University

Autumn 2026

2 of 142

Learning Goals

  1. Be able to compute conditional Expectation
  2. Solve problems using the Law of Total Expectation
  3. Use Conditional Expectation for Algorithmic Analysis

3 of 142

4 of 142

4

Def: Law of Total Expectation

Def: Conditional Expectation

5 of 142

Four Prototypical Trajectories

<review>

6 of 142

Expectation

6

All the values that X can take on

The probability that X takes on that value

7 of 142

Limitation of Expectation

7

X = time to complete the medical diagnosis problem (in seconds)

Summarize the distribution in one number

8 of 142

Expectation of a Sum

​

​

E[X + Y] = E[X] + E[Y]

​

Generalized:

​

​

Holds regardless of dependency between Xi’s

8

9 of 142

Expectation of a Function

9

Law of unconscious statistician

So for example…

10 of 142

Four Prototypical Trajectories

End Review

11 of 142

11

Four practice examples to warm us up

12 of 142

Bool was Cool

12

13 of 142

Bool was Cool

  • Let E1, E2, ... En be events with indicator RVs Xi
    • If event Ei occurs, then Xi = 1, else Xi = 0
    • Recall E[Xi] = P(Ei)

​

    • Why?

13

14 of 142

Bool was Cool

  • Let E1, E2, ... En be events with indicator RVs Xi
    • If event Ei occurs, then Xi = 1, else Xi = 0
    • Recall E[Xi] = P(Ei)

​

    • Why?

14

15 of 142

Bool was Cool

  • Let E1, E2, ... En be events with indicator RVs Xi
    • If event Ei occurs, then Xi = 1, else Xi = 0
    • Recall E[Xi] = P(Ei)

​

    • Why?

15

Bernoulli aka Indicator Random Variables were studied extensively by George Boole

16 of 142

Bool was Cool

  • Let E1, E2, ... En be events with indicator RVs Xi
    • If event Ei occurs, then Xi = 1, else Xi = 0
    • Recall E[Xi] = P(Ei)

​

    • Why?

16

Boole died of being too cool

Bernoulli aka Indicator Random Variables were studied extensively by George Boole

17 of 142

18 of 142

Differential Privacy

18

Aims to provide means to maximize the accuracy of probabilistic queries while minimizing the probability of identifying its records.

​

19 of 142

Differential Privacy

19

Aims to provide means to maximize the accuracy of probabilistic queries while minimizing the probability of identifying its records.

​

Cynthia Dwork

20 of 142

Differential Privacy

20

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

100 independent values X1 … X100 where Xi ~ Bern(p)

What is returned

21 of 142

Differential Privacy

21

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

100 independent values X1 … X100 where Xi ~ Bern(p)

What is returned

22 of 142

Differential Privacy

22

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

What is E[Yi]?

100 independent values X1 … X100 where Xi ~ Bern(p)

What is returned

23 of 142

Differential Privacy

23

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

What is E[Yi]?

100 independent values X1 … X100 where Xi ~ Bern(p)

What is returned

24 of 142

Differential Privacy

24

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

What is E[Yi]?

100 independent values X1 … X100 where Xi ~ Bern(p)

What is returned

25 of 142

Differential Privacy

25

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

What is E[Yi]?

100 independent values X1 … X100 where Xi ~ Bern(p)

What is returned

26 of 142

Differential Privacy

26

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

Let

100 independent values X1 … X100 where Xi ~ Bern(p)

What is E[Z]?

What is returned

27 of 142

Differential Privacy

27

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

Let

100 independent values X1 … X100 where Xi ~ Bern(p)

What is E[Z]?

What is returned

28 of 142

Differential Privacy

28

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

Let

100 independent values X1 … X100 where Xi ~ Bern(p)

What is E[Z]?

What is returned

29 of 142

Differential Privacy

29

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

Let

100 independent values X1 … X100 where Xi ~ Bern(p)

What is E[Z]?

What is returned

30 of 142

Differential Privacy

30

# Maximize accuracy, while preserving privacy.

def calculateYi(Xi):

obfuscate = True if random.randint(0, 1) else False

if obfuscate:

return random.randint(0, 1)

else:

return Xi

Let

How do you estimate p?

Challenge: What is the probability that our estimate is good?

100 independent values X1 … X100 where Xi ~ Bern(p)

What is returned

31 of 142

Differential Privacy

31

Professor at Stanford

Story which continues to unfold…

32 of 142

What is Amazon?

32

33 of 142

Cape Town, 2006

34 of 142

What is Amazon?

34

* 74% of Amazons Profits

**More profitable than Amazon’s North

America commerce operations

https://www.fool.com/investing/2022/07/07/aws-chief-says-amazons-most-profitable-segment-is/

35 of 142

Computer Cluster Utilization

35

36 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

​

36

Since X is an expectation, can you express it as a sum?

37 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

    • Let Bernoulli Bi be an indicator for Ai
    • Since requests independent:

37

Since X is an expectation, can you express it as a sum?

38 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

    • Let Bernoulli Bi be an indicator for Ai
    • Since requests independent:

38

Since X is an expectation, can you express it as a sum?

39 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

    • Let Bernoulli Bi be an indicator for Ai
    • Since requests independent:

39

Since X is an expectation, can you express it as a sum?

40 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

    • Let Bernoulli Bi be an indicator for Ai
    • Since requests independent:

40

Since X is an expectation, can you express it as a sum?

41 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

    • Let Bernoulli Bi be an indicator for Ai
    • Since requests independent:

41

Since X is an expectation, can you express it as a sum?

42 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

    • Let Bernoulli Bi be an indicator for Ai
    • Since requests independent:

42

Since X is an expectation, can you express it as a sum?

43 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

    • Let Bernoulli Bi be an indicator for Ai
    • Since requests independent:

43

Since X is an expectation, can you express it as a sum?

44 of 142

Computer Cluster Utilization

  • Computer cluster with k servers
    • Requests independently go to server i with probability pi
    • Let event Ai = server i receives no requests
    • X = # of events A1, A2, … Ak that occur
    • E[X] after first n requests?

​

​

    • Let Bernoulli Bi be an indicator for Ai
    • Since requests independent:

44

Since X is an expectation, can you express it as a sum?

45 of 142

When stuck, brainstorm about random variables

46 of 142

47 of 142

48 of 142

Toy Collection

48

49 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

49

50 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

50

51 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

51

52 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

​

Can you express X as a sum of other random variables?

52

53 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

53

Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.

X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]

54 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

54

Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.

After i successes, the probability of the next success is p = (n – i) / n

X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]

Xi ~ Geo( p = (n – i) / n)

E[Xi] = 1 / p = n / (n – i)

55 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

55

Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.

After i successes, the probability of the next success is p = (n – i) / n

X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]

Xi ~ Geo( p = (n – i) / n)

E[Xi] = 1 / p = n / (n – i)

56 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

56

Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.

After i successes, the probability of the next success is p = (n – i) / n

X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]

Xi ~ Geo( p = (n – i) / n)

E[Xi] = 1 / p = n / (n – i)

(i = 0 to n-1)

57 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

57

Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.

After i successes, the probability of the next success is p = (n – i) / n

X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]

Xi ~ Geo( p = (n – i) / n)

E[Xi] = 1 / p = n / (n – i)

(i = 0 to n-1)

58 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

58

Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.

After i successes, the probability of the next success is p = (n – i) / n

X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]

Xi ~ Geo( p = (n – i) / n)

E[Xi] = 1 / p = n / (n – i)

(i = 0 to n-1)

Approches log(n)

59 of 142

Toy Collection

  • You are trying to collect n distinct toys
    • Each purchase, each toy is equally likely
    • Let X = # purchases until you have ≥ 1 of each toy. What is E[X]?

59

Let Xi = # of trials to get success after i-th success where “success” is getting an unseen toy.

After i successes, the probability of the next success is p = (n – i) / n

X = X0 + X1 + ... + Xn-1 ⇒ E[X] = E[X0] + E[X1] + ... + E[Xn-1]

Xi ~ Geo( p = (n – i) / n)

E[Xi] = 1 / p = n / (n – i)

(i = 0 to n-1)

Approches log(n)

60 of 142

60

61 of 142

Four Prototypical Trajectories

Conditional Expectation

62 of 142

Conditional Expectation

  • X and Y are discrete random variables:

​

​

​

62

Analogously, continuous random variables:

63 of 142

Conditional Expectation

63

64 of 142

Conditional Expectation

  • Roll two 6-sided dice D1 and D2
    • X = value of D1 + D2 Y = value of D2
    • What is E[X | Y = 6]?

​

​

​

​

​

​

64

65 of 142

Conditional Expectation

  • Roll two 6-sided dice D1 and D2
    • X = value of D1 + D2 Y = value of D2
    • What is E[X | Y = 6]?

​

​

​

​

​

​

65

66 of 142

Conditional Expectation

  • Roll two 6-sided dice D1 and D2
    • X = value of D1 + D2 Y = value of D2
    • What is E[X | Y = 6]?

​

​

​

​

​

66

67 of 142

Conditional Expectation

  • Roll two 6-sided dice D1 and D2
    • X = value of D1 + D2 Y = value of D2
    • What is E[X | Y = 6]?

​

​

​

​

    • Intuitively makes sense: 6 + E[value of D1] = 6 + 3.5

​

67

68 of 142

Four Prototypical Trajectories

Conditional Expectation as a Function

69 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

69

70 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

70

E[X|Y=y]

71 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

71

E[X|Y=y]

This is a function with Y as input

72 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

72

E[X|Y=y]

73 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

73

E[X|Y=y]

74 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

74

E[X|Y=y]

75 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

75

E[X|Y=y]

76 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

76

E[X|Y=y]

77 of 142

Conditional Expectation

  • Define g(Y) = E[X | Y]
  • This is a function of Y

​

​

​

​

77

E[X|Y=y]

78 of 142

Conditional Expectation

78

Doesn’t make sense. Take expectation of random variables, not events

This is a number:

This is a function of y:

79 of 142

Expectation

79

X = favorite number

Y = year in school

80 of 142

Expectation

80

X = favorite number

Y = year in school

81 of 142

Expectation

81

X = favorite number

Y = year in school

E[X] = 0 * 0.05 + … + 9 * 0.10 = 5.38

82 of 142

Conditional Expectation

82

E[ X | Y ] ?

X = favorite number

Y = year in school

83 of 142

Conditional Expectation

83

E[ X | Y ] ?

Year in school, Y = y

E[ X | Y = y ]

2

5.5

3

5.8

4

6.0

5

4.7

X = favorite number

Y = year in school

84 of 142

Conditional Expectation

84

E[X | Y] ?

Year in school, Y = y

E[X | Y = y]

2

5.5

3

5.8

4

6.0

5

4.7

X = favorite number

Y = year in school

85 of 142

Conditional Expectation

85

X = units in fall quarter

Y = year in school

E[X | Y] ?

86 of 142

Four Prototypical Trajectories

Want to see something cool?

87 of 142

What the heck does this give you?

87

88 of 142

Law of Total Expectation

88

Def of E[X|Y]

89 of 142

Law of Total Expectation

89

Def of E[X|Y]

Chain rule!

90 of 142

Law of Total Expectation

90

Def of E[X|Y]

Chain rule!

I switch the order of the sums

91 of 142

Law of Total Expectation

91

Def of E[X|Y]

Chain rule!

I switch the order of the sums

Move that x outside the y sum

92 of 142

Law of Total Expectation

92

Def of E[X|Y]

Chain rule!

I switch the order of the sums

Move that x outside the y sum

Marginalization

93 of 142

Law of Total Expectation

93

Def of E[X|Y]

Chain rule!

I switch the order of the sums

Move that x outside the y sum

Marginalization

Def of E[X]

94 of 142

Four Prototypical Trajectories

Law of Total Expectation

95 of 142

Law of Total Expectation

95

For any discrete random variable X and any discrete random variable Y

Recall the Law of Total Probability

96 of 142

96

(The Streaming Part)

97 of 142

How long does this code take to run?

97

Netflix streams millions of hours of videos per day. They REALLY care about the speed of the following code:

How long does this line of code take? Say 512 MB movie.

database.get_movie(movie_name)

98 of 142

How long does this code take to run?

98

  1. 0.3s
  2. 1.6s
  3. 5 mins
  4. 2 hours

database.get_movie(movie_name)

99 of 142

Millisecond Latency

99

  1. 0.3s
  2. 1.6s
  3. 5 mins
  4. 2 hours

Its in Palo Alto

database.get_movie(movie_name)

100 of 142

Minute Latency

100

  1. 0.3s
  2. 1.6s
  3. 5 mins
  4. 2 hours

I have the file

101 of 142

Many Minutes Latency

101

  1. 0.3s
  2. 1.6s
  3. 5 mins
  4. 2 hours

私はファイルを持っています

102 of 142

Are we done?

102

5mins across the world!!!!!!

103 of 142

103

I have the file

104 of 142

104

I have the file

2 hours

105 of 142

Four Prototypical Trajectories

Expected Run Time

106 of 142

Expected runtime

106

Location, l

E[Runtime | Location = l]

P(Location = l)

Palo Alto

0.3s

0.10

SoCal

1.6s

0.50

Japan

300.0s

0.37

Space

7200.0s

0.03

Let Location (L for short) be the location where the movie file is stored

What is the expected runtime of

database.get_movie(movie_name)

107 of 142

Expected runtime

107

Location, l

E[Runtime | Location = l]

P(Location = l)

Palo Alto

0.3s

0.10

SoCal

1.6s

0.50

Japan

300.0s

0.37

Space

7200.0s

0.03

Let Location (L for short) be the location where the movie file is stored

What is the expected runtime of

database.get_movie(movie_name)

Using the Law of Total Expectation

108 of 142

Expected runtime

108

Location, l

E[Runtime | Location = l]

P(Location = l)

Palo Alto

0.3s

0.10

SoCal

1.6s

0.50

Japan

300.0s

0.37

Space

7200.0s

0.03

Let Location (L for short) be the location where the movie file is stored

What is the expected runtime of

database.get_movie(movie_name)

Using the Law of Total Expectation

109 of 142

Four Prototypical Trajectories

Analyze Recursive Code

110 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

110

Let Y = value returned by Recurse(). What is E[Y]?

​

111 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

111

Let Y = value returned by Recurse(). What is E[Y]?

​

112 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

112

Let Y = value returned by Recurse(). What is E[Y]?

​

113 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

113

Let Y = value returned by Recurse(). What is E[Y]?

​

114 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

114

Let Y = value returned by Recurse(). What is E[Y]?

​

115 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

115

Let Y = value returned by Recurse(). What is E[Y]?

​

116 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

116

Let Y = value returned by Recurse(). What is E[Y]?

​

117 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

117

Let Y = value returned by Recurse(). What is E[Y]?

​

118 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

118

Let Y = value returned by Recurse(). What is E[Y]?

​

119 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

119

Let Y = value returned by Recurse(). What is E[Y]?

​

120 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

120

Let Y = value returned by Recurse(). What is E[Y]?

​

121 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

121

Let Y = value returned by Recurse(). What is E[Y]?

​

122 of 142

Analyzing Recursive Code

int Recurse() {

int x = randomInt(1, 3); // Equally likely values

​

if (x == 1) return 3;

else if (x == 2) return (5 + Recurse());

else return (7 + Recurse());

}

​

​

122

Let Y = value returned by Recurse(). What is E[Y]?

​

123 of 142

123

124 of 142

Four Prototypical Trajectories

If we have time…

125 of 142

125

Your company has one job opening for a software engineer.

​

You have n candidates. But you have to say yes/no immediately after each interview!

​

Proposed algorithm: reject the first k and accept the next one who is better than all of them.

​

What’s the best value of k?

Hiring an Engineer

Aka The Secretary Problem

Aka The Optimal Stopping Problem

Aka The Marriage Problem

126 of 142

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

What is the

127 of 142

127

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

What is the

i

k

128 of 142

128

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

What is the

i

k

129 of 142

129

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

What is the

i

k

130 of 142

130

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

What is the

i

k

131 of 142

131

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

What is the

i

k

Hint: where is the best among the first i – 1 candidates?

132 of 142

132

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

What is the

i

k

Hint: where is the best among the first i – 1 candidates?

Here?

133 of 142

133

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

What is the

i

k

Hint: where is the best among the first i – 1 candidates?

Here?

134 of 142

134

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

i

k

Hint: where is the best among the first i – 1 candidates?

135 of 142

135

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

136 of 142

136

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

137 of 142

137

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

By the law of total expectation

138 of 142

138

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

By the law of total expectation

139 of 142

139

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

By the law of total expectation

140 of 142

140

n candidates, must say yes/no immediately after each interview.

Reject the first k, accept the next who is better than all of them.

What’s the best value of k?

​

B: event that you hire the best engineer

X: position of the best engineer on the interview schedule

Hiring and Engineer

By the law of total expectation

Fun fact. Optimized when:

141 of 142

Uncertainty Theory

141

Beta Distributions

Adding Random Vars

Central Limit Theorem

Sampling

Algorithmic Analysis

Thompson Sampling

Bootstrapping

​

Information Theory

As requested by CS faculty

142 of 142

Where are we in CS109?

142

On Friday…

Chris Piech, CS109