AP Computer Science Principles · Unit 3 lecture · Part 12 of 14 · 10 min

3.14 to 3.16 Libraries, random values and simulationsBorrowed code, chance, and models of the world

Mr. Thompkins
Three short topics, one theme: programs that reach beyond what you wrote yourself. Code from libraries, numbers you can't predict, and models of things too big or too dangerous to try for real.

Libraries and APIs

A software library contains procedures that can be used in creating new programs. Existing code segments can come from internal sources (code you or your team wrote before) or external ones (libraries other people wrote). Using libraries simplifies creating complex programs: you don't write your own sorting or drawing code. An API, application program interface, is the specification of how the procedures in a library behave and can be used. Documentation for a library or API is necessary to understand what its procedures do and how to call them.

Library procedure (from its API)What the documentation promises
round(x)Returns x rounded to the nearest whole number
sqrt(x)Returns the square root of x; x must be at least 0
sortList(aList)Puts aList in order from smallest to largest
drawCircle(x, y, r)Draws a circle of radius r centered at (x, y)
What an API's documentation tells you: the name, the parameters, and what it does or returns. Not how it works inside.
?Wait, is a library an example of procedural abstraction?
Exactly that. You call sqrt(x) knowing only what the documentation says it does. How it computes the square root is hidden, and the library's authors can improve it without breaking your program.

Random values

RANDOM(a, b) returns a random whole number from a to b, including both a and b, and each result is equally likely. RANDOM(1, 6) is a die roll: 1, 2, 3, 4, 5 or 6. Because of randomness, a program that uses RANDOM may produce a different result each time it runs, so questions often ask what values are possible, or how likely one is.

To find a probability, count: favorable outcomes divided by total equally likely outcomes. RANDOM(1, 10) ≤ 3 is true for 3 of the 10 values, so 30 percent of the time. For two separate random calls, list every pair. Two calls of RANDOM(1, 3) give 3 × 3 = 9 equally likely pairs.

x \ yy = 1y = 2y = 3
x = 1234
x = 2345
x = 3456
All 9 outcomes of RANDOM(1, 3) + RANDOM(1, 3). The sum 4 appears 3 times, so its probability is 3/9 = 1/3.
?Wait, how many values does RANDOM(a, b) have?
b - a + 1. RANDOM(1, 6) has 6 values. RANDOM(0, 4) has 5 (0, 1, 2, 3, 4), not 4. Forgetting the "+ 1" is the classic slip.

Simulations

Simulations are abstractions of more complex objects or phenomena for a specific purpose. They mimic real-world events, using varying sets of values to reflect a changing state, so we can draw inferences without the constraints of the real world. They're most useful when real experiments are impractical: too big, too small, too fast, too slow, too expensive or too dangerous. Simulations help people form and refine hypotheses, and random number generators can model the variability of the real world.

Building a simulation means removing details and simplifying. That makes it possible, but it has a cost: a simulation can contain bias from the choices of which real-world elements are included or left out. Its results are only as good as its assumptions.

Real situationWhy simulate itA detail you might leave out
Evacuating a stadiumToo dangerous to test for realPeople who stop to help others
Spread of a fluToo slow and unethical to wait and watchDifferent contact by age
A new bus routeToo expensive to build firstRiders who switch to bikes
A galaxy formingToo big and too slowMost individual stars
Why each situation is simulated, and one detail a simple model might leave out (a possible source of bias).
1heads ← 02REPEAT 100 TIMES3{4  IF (RANDOM(1, 2) = 1)15  {6    heads ← heads + 17  }8}9DISPLAY(heads)
  1. line 4 A fair coin: 1 means heads, 2 means tails
output › a whole number from 0 to 100, usually near 50
Simulating 100 coin flips. Each run can display a different number.
Pause and think
What values can the coin-flip simulation display? Is 50 guaranteed?
I thought about it. Show me
Any whole number from 0 to 100. 50 is the most likely single value, but it isn't guaranteed, and it isn't even very likely on its own. In 100,000 simulated runs, about 96 percent of the results were between 40 and 60.
Possible outputs and probability
x ← RANDOM(1, 3), then y ← RANDOM(1, 3), then DISPLAY(x + y). (a) List every value that could be displayed. (b) What is the probability that 4 is displayed? (c) Could 1 or 7 ever be displayed?
  1. (a) The smallest sum is 1 + 1 = 2 and the largest is 3 + 3 = 6, and every sum between is reachable: 2, 3, 4, 5, 6.
  2. (b) There are 3 × 3 = 9 equally likely (x, y) pairs. The pairs that sum to 4 are (1, 3), (2, 2) and (3, 1): 3 of 9, so 1/3.
    Why?
    Count pairs, not sums. The sums aren't equally likely; the pairs are.
  3. (c) No. 1 would need a 0, and 7 would need a 4, and RANDOM(1, 3) only gives 1, 2 or 3.

Answer: (a) 2, 3, 4, 5, 6. (b) 3/9 = 1/3. (c) No: the possible sums are 2 through 6 only.

Stuck? Get a hint
  1. Make a 3 by 3 table: x down the side, y across the top.
  2. Fill each cell with x + y.
  3. Count the cells equal to 4, out of 9.
Check yourself
A game should award a prize with a probability of exactly 20 percent. Which condition does that?
  1. ARANDOM(1, 5) = 5
  2. BRANDOM(0, 5) = 0
  3. CRANDOM(1, 20) = 1
  4. DRANDOM(1, 10) ≤ 1
Show the answer

A. RANDOM(1, 5) has 5 equally likely values, and 1 of them is 5: 1/5 = 20 percent. RANDOM(0, 5) has 6 values (about 17 percent), RANDOM(1, 20) = 1 is 5 percent, and RANDOM(1, 10) ≤ 1 is 10 percent.

Check yourself
A city simulates traffic on a new bridge but leaves out bicycles and pedestrians to keep the model simple. Which is the most likely consequence?
  1. AThe simulation will run more slowly than the real bridge.
  2. BThe results may be biased, because elements of the real situation were left out.
  3. CThe simulation cannot use random numbers.
  4. DThe simulation becomes an exact copy of reality.
Show the answer

B. Simplifying is what makes simulations possible, but choices about what to include or leave out can bias the results. A bridge designed only for cars might fail the people who walk or bike.

  • A library holds reusable procedures. An API specifies how they behave; documentation explains how to use them.
  • RANDOM(a, b): a whole number from a to b, inclusive, each equally likely. That's b - a + 1 values.
  • Probability: favorable equally likely outcomes ÷ total. For two calls, count pairs.
  • Simulations are abstractions for when real tests are impractical. Simplifying can introduce bias.