We have already used top-down programming to solve problems. In our exploration of bacterial genomes in Chapter 1, we wrote a function `ReverseComplement()`

to take the reverse complement of a DNA string by assuming that we had two simpler functions `Reverse()`

and `Complement()`

.

ReverseComplement(text) x ← Reverse(text) y ← Complement(x) return y

We also applied top-down programming when we simulated many elections by assuming that we had already written a subroutine `SimulateElection()`

that would handle simulating a single election.

SimulateMultipleElections(polls, electoralVotes, numTrials, marginOfError) winCount1 ← 0 winCount2 ← 0 tieCount ← 0 for numTrials total trials votes1,votes2 ← SimulateElection(polls, electoralVotes, marginOfError) if votes1 > votes2 winCount1 ← winCount1 + 1 else if collegeVotes2 > collegeVotes1 winCount2 ← winCount2 + 1 else (tie!) tieCount ← tieCount + 1 probability1 ← winCount1/numTrials probability2 ← winCount2/numTrials probabilityTie ← tieCount/numTrials return probability1, probability2, probabilityTie

The `SimulateOneElection()`

function in turn called an `AddNoise()`

subroutine, which is where the gritty details of the program were hiding in the form of (pseudo)random number generation, which required its own set of subroutine calls.

As we move toward larger programs with many functions, we can visualize how these functions are organized using a **function hierarchy**, or a network in which functions are connected to subroutines that they call by arrows. In a function hierarchy, the “root” function (i.e., the one at the top of the diagram that has no incoming arrows) solves the computational problem at hand. Function hierarchies are shown in the figure below for the functions `SimulateMultipleElections()`

and `ReverseComplement()`

.

Exercise:Review the Game of Life Problem from the previous lesson. Plan the highest-level function in the hierarchy that will solve this problem. What subroutine(s) will be helpful?