Exercises: Simulations, Algorithmic Efficiency, and Undecidable Problems

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.

1. a) What are the possible values of RANDOM(1, 6)?

1. b) How many different values can RANDOM(5, 15) return?

1. c) Which call could simulate flipping a coin?

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:

1. a) $n$ steps

1. b) $n^2$ steps

1. c) $2^n$ steps

1. d) $n!$ steps

Compare the number of steps for two algorithms:

1. a) Which algorithm is reasonable and which is unreasonable? Explain from the table.

1. b) A computer performs 1 billion steps per second. About how long does the $2^{30}$ algorithm take?

1. 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.

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)

1. a) What is the probability that each simulated shot is made? Explain.

1. b) What range of values can be displayed?

1. c) Will the output be the same on every run? Why does running the simulation many times and averaging give a better estimate?

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.

1. a) Explain the difference between a decidable and an undecidable problem.

1. b) The problem described is known as the halting problem. Is the company's claim possible? Explain.

1. c) Describe one practical thing developers can still do to catch programs that get stuck.

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.

1. a) Compute the number of routes for $n = 5$ and $n = 10$. Then use $14! = 87{,}178{,}291{,}200$ for $n = 15$.

1. 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.

1. 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 first and then checks neighbors, using about $10n$ steps.

1. a) Compute the number of steps for each algorithm when $n = 10$ and when $n = 1{,}000$.

1. b) For what value of $n$ do the two algorithms use the same number of steps? Which is faster for larger $n$?

1. c) Are both algorithms reasonable? Explain. Then explain why the algorithm with fewer steps for small inputs is not always the best choice.