Simulations, Algorithmic Efficiency, and Undecidable Problems
Your favorite video game decides whether a loot box gives you a rare item. A weather app predicts a hurricane's path days ahead. A delivery app plans a route through dozens of stops. Behind all three are the same questions: How can a program imitate chance? How long will an algorithm take as the problem grows? And is there anything a computer can never do? Let's find out.
Random Values
Many programs need unpredictable results: shuffling a playlist, rolling dice in a board game, spawning an enemy at a random spot. In AP pseudocode, one procedure does this:
RANDOM(a, b) returns an integer from a to b, including both a and b. Each value is equally likely.
So RANDOM(1, 6) can return 1, 2, 3, 4, 5, or 6, like a die. RANDOM(5, 15) can return 5, 6, ..., 15. That is $15 - 5 + 1 = 11$ different values.
The count of values in RANDOM(a, b) is $b - a + 1$. The "+ 1" is there because both ends are included.
Turning random numbers into events
To model an event with a known probability, split the possible values into "success" and "fail" groups.
a) What are the possible values of RANDOM(1, 6)? b) How many different values can RANDOM(5, 15) return? c) Which call could simulate flipping a coin?
- a) What are the possible values of
RANDOM(1, 6)?
- b) How many different values can
RANDOM(5, 15)return?
- c) Which call could simulate flipping a coin?
Simulations
A simulation is a program that imitates a real-world situation using a simplified model. Engineers simulate how a bridge handles wind. Doctors simulate how a disease spreads. Game designers simulate crowds.
Simulations are useful because they can be:
-
Safer: no one gets hurt if a virtual bridge collapses.
-
Cheaper and faster: thousands of trials run in seconds.
-
Possible when real tests aren't: you can't crash a real planet.
But a simulation is only a model, so it has limits:
-
It leaves out details of the real world, so results can be wrong.
-
It depends on the assumptions and data its creators chose, which can include bias.
-
A simulation never replaces final real-world testing.
Simulating with random values
Simulations often use RANDOM to represent chance. Liam models a player who makes 70% of her free throws:
makes ← 0
REPEAT 10 TIMES {
IF (RANDOM(1, 10) ≤ 7) {
makes ← makes + 1
}
}
DISPLAY(makes)
Seven of the 10 values (1 through 7) count as a made shot, so each shot is made with probability $\frac{7}{10} = 70\%$. The output is a whole number from 0 to 10.
Because of the randomness, each run can give a different result. One run might show 6, the next 8. Running the simulation many times and averaging the results gets close to the expected value, $10 \times 0.7 = 7$ makes. More trials give a more reliable estimate.
This shows a useful difference. A deterministic algorithm gives the same result every time for the same input, such as adding up a list of numbers. A probabilistic algorithm uses RANDOM, so it can give different results on different runs, like the free-throw simulation above.
Engineers use simulations to test how a bridge responds to strong winds before building it. Give one benefit and one limitation of using simulations instead of…
Engineers use simulations to test how a bridge responds to strong winds before building it. Give one benefit and one limitation of using simulations instead of real-world experiments.
Liam simulates a basketball player who makes 70% of her free throws. a) What is the probability that each simulated shot is made? Explain. b) What range of values can be…
Liam simulates a basketball player who makes 70% of her free throws.
makes ← 0
REPEAT 10 TIMES
{
IF (RANDOM(1, 10) ≤ 7)
{
makes ← makes + 1
}
}
DISPLAY(makes)
- a) What is the probability that each simulated shot is made? Explain.
- b) What range of values can be displayed?
- c) Will the output be the same on every run? Why does running the simulation many times and averaging give a better estimate?
Algorithmic Efficiency
Two algorithms can solve the same problem, but one may be far faster. Efficiency describes how the number of steps grows as the input size $n$ grows.
Think of a group chat: telling 1 friend takes 1 message. If you must message every pair of $n$ friends, the work grows much faster than $n$.
| Growth | Example | Type |
|---|---|---|
| $n$ | check each item once | reasonable |
| $n^2$ | compare every pair | reasonable |
| $2^n$ | try every subset | unreasonable |
| $n!$ | try every ordering | unreasonable |
An algorithm runs in reasonable time if its steps grow as a polynomial in $n$ (like $n$, $n^2$, or $n^3$). It runs in unreasonable time if its steps grow exponentially or faster ($2^n$, $n!$).
Notice how $2^n$ starts small, then explodes past $n^2$.
| $n$ | $n^2$ | $2^n$ |
|---|---|---|
| 10 | 100 | 1,024 |
| 20 | 400 | 1,048,576 |
| 30 | 900 | 1,073,741,824 |
Heuristics and trade-offs
Some problems have no known reasonable algorithm that finds the best answer. Take a driver who must visit $n$ cities once and return home. Checking every route means $(n-1)!$ routes, which is unreasonable.
A heuristic is an approach that gives a good answer quickly, though not guaranteed to be the best. For the delivery route, a heuristic is "always go to the nearest unvisited city next." It runs fast but may produce a longer route than the optimal one. The trade-off is speed versus perfect accuracy.
An algorithm runs in reasonable time if the number of steps grows as a polynomial in the input size $n$, such as $n$ or $n^2$. It runs in unreasonable time if the number…
An algorithm runs in reasonable time if the number of steps grows as a polynomial in the input size $n$, such as $n$ or $n^2$. It runs in unreasonable time if the number of steps grows exponentially or faster. Classify each as reasonable or unreasonable:
- a) $n$ steps
- b) $n^2$ steps
- c) $2^n$ steps
- d) $n!$ steps
Compare the number of steps for two algorithms: | $n$ | $n^2$ | $2^n$ | |---|---|---| | 10 | 100 | 1,024 | | 20 | 400 | 1,048,576 | | 30 | 900 | 1,073,741,824 | a) Which…
Compare the number of steps for two algorithms:
| $n$ | $n^2$ | $2^n$ |
|---|---|---|
| 10 | 100 | 1,024 |
| 20 | 400 | 1,048,576 |
| 30 | 900 | 1,073,741,824 |
- a) Which algorithm is reasonable and which is unreasonable? Explain from the table.
- b) A computer performs 1 billion steps per second. About how long does the $2^{30}$ algorithm take?
- c) For $n = 60$, the exponential algorithm needs about $1.15 \times 10^{18}$ steps. About how many years is that at the same speed? Use $1\text{ year} \approx 3.15 \times 10^7$ seconds.
A delivery driver must visit $n$ cities and return home. Brute force checks every possible order. Starting at a fixed city, there are $(n-1)!$ routes. a) Compute the…
A delivery driver must visit $n$ cities and return home. Brute force checks every possible order. Starting at a fixed city, there are $(n-1)!$ routes.
- a) Compute the number of routes for $n = 5$ and $n = 10$. Then use $14! = 87{,}178{,}291{,}200$ for $n = 15$.
- b) A computer checks 1,000,000 routes per second. How long does it take for $n = 10$ and for $n = 15$? Give the second answer in hours, rounded to one decimal place.
- c) Is the brute-force algorithm reasonable or unreasonable? Describe a heuristic that gives a good, though not necessarily best, route, and explain the trade-off.
Two algorithms find out whether a list of $n$ values has a duplicate. Algorithm A compares every pair, using about $\dfrac{n(n-1)}{2}$ steps. Algorithm B sorts the list…
Two algorithms find out whether a list of $n$ values has a duplicate.
-
Algorithm A compares every pair, using about $\dfrac{n(n-1)}{2}$ steps.
-
Algorithm B sorts the list first and then checks neighbors, using about $10n$ steps.
- a) Compute the number of steps for each algorithm when $n = 10$ and when $n = 1{,}000$.
- b) For what value of $n$ do the two algorithms use the same number of steps? Which is faster for larger $n$?
- c) Are both algorithms reasonable? Explain. Then explain why the algorithm with fewer steps for small inputs is not always the best choice.
Undecidable Problems
So far, problems were solvable, just sometimes slowly. Some problems cannot be solved by any algorithm at all.
A decidable problem is one where an algorithm can always give a correct yes/no answer for every input. An undecidable problem is one where no algorithm can give a correct answer for all possible inputs.
The most famous example is the halting problem: given any program and its input, decide whether the program will eventually stop or run forever. In 1936, Alan Turing proved that no algorithm can solve this for every program.
Why? Imagine a perfect "halting checker." You could build a tricky program that asks the checker about itself and then does the opposite of what the checker predicts. Whatever the checker says would be wrong, so a perfect checker cannot exist.
Undecidable does not mean useless. A program can still solve the halting problem for some programs. It just can't work for all of them.
In practice, developers catch stuck programs with timeouts (stop a program after a set time), testing with many cases, and code review for loops that may never end.
A software company claims it has built a tool that can analyze any program and tell with certainty whether it will eventually stop or run forever. a) Explain the…
A software company claims it has built a tool that can analyze any program and tell with certainty whether it will eventually stop or run forever.
- a) Explain the difference between a decidable and an undecidable problem.
- b) The problem described is known as the halting problem. Is the company's claim possible? Explain.
- c) Describe one practical thing developers can still do to catch programs that get stuck.
Back to the start: a loot box uses RANDOM, a hurricane forecast is a simulation, and a delivery route is an efficiency problem where a heuristic beats brute force.