Finding the minimum of two numbers
We will soon return to the problem of computing a GCD; for now, we will start to explain how we will program a computer. Dozens of programming languages have been developed to allow us to convert ideas into computer instructions, and each language has its own quirks that take time to learn. We want to get started explaining computational ideas as quickly as we can, and so we will place learning a specific language on hold for now. Instead, we will use a general way of describing algorithms called pseudocode that avoids getting mired in the details of a specific language.
We will illustrate pseudocode with a simple example in the form of the following computational problem.
Minimum of Two Integers Problem
Input: Integers a and b.
Output: The minimum value of a and b.
You might think that this problem cannot possibly hold any interest — we simply need to look at the two numbers and see which one is smaller! Yet we will soon see that even finding the minimum value of a collection of numbers can indicate important computational principles.
We will think of an algorithm solving a computational problem as a function that takes in the input variables specified by the problem, processes these variables in some way, and then returns the output solving the problem. This notion of a function parallels the mathematical view of a function, which is commonly taught as a “machine” that takes one or more variables as input and maps the input variables to one or more output values. For example, the mathematical function f(x,y) = (x + 3, y − 4, x · y) takes two input variables and returns a triple of values. In the case of the Minimum of Two Numbers Problem, we will call our function
, and it should take as input the two parameters a and b.
A seminal tool in programming is the ability to check a condition and branch a computer program into different possibilities based on this condition. When computing the minimum of a and b, we would like to check if a is smaller, in which case a is our minimum, and the function
should return its value; otherwise,
should return the value of b.
We can represent such a test in pseudocode by an if statement, in which we take one action if a statement is true and another action if it is not. Below is pseudocode for
Min2(), which includes our if statement.
Min2(a, b) if a < b return a else return b
The first line of
Min2() names the function and names the input variables. The second line tests if
a is smaller than
b. If this is true, then the program enters line 3 and returns the value of
a. An important point is that the function will now terminate, as a function ends when it encounters a return statement. On the other hand, if
a is not smaller than
b, then the function does not execute line 3 but instead continues to line 4, where the
else indicates that we should enter the indented line following
a is not smaller than
b, we know that
a is greater than or equal to
b, and so we can safely return the value of
b (and halt the program).
still return the desired answer if
The if statement in
exemplifies a common if statement. The following hypothetical function first executes instructions A (which may contain one or many lines). If condition X is true, then the function executes instructions Y (called the if block); if the function doesn’t encounter a return statement, then it continues onward to execute instructions B. On the other hand, if condition X is false, then the function executes instructions Z (called the else block); if it does not encounter a return statement in those instructions, then it executes instructions B.
SomeFunction(parameters) execute instructions A if condition X is true execute instructions Y else execute instructions Z execute instructions B
is a short function, it allows us to introduce control flow, or the sequence of steps that are taken when going through a function. Understanding control flow is central to a mastery of computer programming for two reasons. First, a computer program can only execute one instruction at a time (for now). Second, the control flow of a function implies a unique sequence of instructions for a given choice of parameters, which is critical because a computer needs precisely defined instructions to complete tasks.
You may be curious why certain words are typeset in bold in pseudocode. These words are called keywords, and they have reserved meanings in most programming languages. For example, a programming language would never let us use the word
to represent a variable, or
as a function name.
Subroutines: functions as building blocks
We will now tweak our ongoing problem by adding just a single input variable. Before reading on, try writing a function in pseudocode to solve it!
Minimum of Three Numbers Problem
Input: Integers a, b, and c.
Output: The minimum value of a, b, and c.
We solve the Minimum of Three Numbers Problem below using a function
. If the control flow of this function is not yet clear, don’t worry, as we will walk through it line by line.
Min3(a, b, c) if a < b if a < c return a else return c else if b < c return b else return c
After line 1 names the function and specifies the three input variables, line 2 contains an if statement testing whether
a is smaller than
a is smaller than
b, then we can immediately deduce that
b cannot be the minimum of the three parameters. As a result, we know that whichever of
c is smaller must be our desired minimum. Lines 3–6 of
contain the if block; in this block, we check which of
c is smaller and return its value:
if a < c return a else return c
These lines constitute a nested if statement within an if block in the
function. This example indicates how powerful if statements can be, since nesting them allows us to branch into as many different possibilities as we like.
We have discussed what happens in
a is smaller than
a is not smaller than
b, then we enter the else block on lines 8–11 of
and return the smaller of
c, as shown below. These lines bring us to the end of
if b < c return b else return c
STOP: Look again at the main if block and else block in
; what do they remind you of?
Part of the reason why we have separately discussed the if block and the else block in
is that they are both performing the same task, finding the minimum of two numbers. But we have already completed this task when we wrote
! How can we use what we have already done to simplify
A fundamental programming paradigm is the ability to use functions as building blocks to construct more complicated functions. Our ongoing example illustrates this concept well. We know that
needs to know the minimum of two numbers in the two highlighted blocks above. We can instead greatly shorten
by using the value returned by the function
. In general, a function that occurs within the body of another function is known as a subroutine, and in this case we say that
as a subroutine.
Min3(a, b, c) if a < b return Min2(a,c) else return Min2(b,c)
We should take a moment to explain how the control flow works when one function calls another as a subroutine. Say that we enter the if block in
and reach the following line:
Although a function would normally immediately stop at a return statement,
must wait when it encounters the call to
. In the meantime, the control flow passes to
, with input variables of
a is smaller, then this subroutine returns the value of
a; otherwise, it returns the value of
c. Only when this subroutine returns the value are we able to use this value and continue on in
. In this case, this value is used in the return statement and
Exercise: Write a pseudocode function
Min4()to find the minimum values of four input number variables using subroutines.
One answer to the preceding question is to branch again based on whether
a is smaller than
b, and then to call
, as shown below.
Min4(a, b, c, d) if a < b return Min3(a, c, d) else return Min3(b, c, d)
However, this function can be written even more concisely if we compare the minimum of
b against the minimum of
d, and then take the smaller of the two values. This idea can be implemented by the following function that contains only one line!
Min4(a, b, c, d) return Min2(Min2(a, b), Min2(c, d))
The Doomsday algorithm, and else if
Before continuing, we will introduce an important variant of the if statement by returning to the party trick that we mentioned in the beginning of the chapter, in which one can quickly determine the day of the week corresponding to a given date in the year. When students are asked how they think this algorithm might work, one of their most common ideas is to memorize the first day of the year, and then count how many days have elapsed between this first day and a given birthday. The problem with this approach is that although it would not take long to determine the day of the week for a date in January or February, dates later in the year would become intensive to calculate.
Instead, we could memorize the day of the week for the first day of every month, and then use this information to count forward in a given month. For example, if April 1st falls on a Sunday, then we would automatically know that April 8th, 15th, 22nd, and 29th also fall on Sundays, so that it would be easy to compute that April 24th falls on a Tuesday by counting two days ahead from the 22nd.
This approach is reasonable but still requires us to memorize quite a lot. The clever trick is instead to memorize a date in every month such that all these days always fall on the same day of the week. The following dates are called doomsdays. Speaking of doomsdays, in 2020, these dates all fell on a Saturday (in 2019, they fell on a Thursday, and in 2018, they fell on a Wednesday).
- January 3rd (or January 4th in leap years)
- February 28th (or February 29th in leap years)
- March 0th (we pretend that this day exists)
- April 4th
- May 9th
- June 6th
- July 11th
- August 8th
- September 5th
- October 10th
- November 7th
- December 12th
These dates are chosen for doomsdays because they can be remembered with ease. February 28th and March 0th correspond to the same day. The doomsdays of the five other even-numbered months (April, June, etc.) have the same number corresponding to the day and month (4/4, 6/6, 8/8, 10/10, 12/12). Four other dates can be remembered via the mnemonic device “I work 9-to-5 at 7–11” (yielding 5/9, 9/5, 7/11, and 11/7). As a result, we only need to memorize four pieces of information: the January and February dates, the even-month rule, and the mnemonic.
The corresponding algorithm for finding the day of the week for a given day and month is called the Doomsday algorithm. An abbreviated function implementing this algorithm in 2020 is shown below.
Doomsday2020(day, month) if month = 1 if day = 4, 11, 18, or 25 return "Saturday" else if day = 5, 12, 19, or 26 return "Sunday" else (and so on...) else if month = 2 if day = 7, 14, 21, or 28 return "Saturday" else if day = 1, 8, 15, or 22 return "Sunday" else (and so on...) else if month = 3 (and so on...)
This function is undeniably ugly. The test for whether the
month variable is equal to 2 is buried within the first else statement, and the test for whether
month is equal to 3 is buried one level lower. In practice, we don’t need the else statements, because if
month is not equal to 1, then we can automatically proceed past the if block and test if
month is equal to 2. This reasoning leads us to the following streamlined version of
Doomsday2020(day, month) if month = 1 if day = 4, 11, 18, or 25 return "Saturday" if day = 5, 12, 19, or 26 return "Sunday" (and so on...) if month = 2 if day = 7, 14, 21, or 28 return "Saturday" if day = 1, 8, 15, or 22 return "Sunday" (and so on...) if month = 3 (and so on...)
In practice, however, if we have 12 different possibilities to check, then we will typically indent them all at the same level and use the keywords
for all 11 possibilities after the first. This makes our (pseudo)code much more readable, with the control flow jumping directly to the block corresponding to the value of
month, and then within that block jumping straight to the block corresponding to the value of
day. A final function incorporating
is shown below.
Doomsday2020(day, month) if month = 1 if day = 4, 11, 18, or 25 return "Saturday" else if day = 5, 12, 19, or 26 return "Sunday" (and so on...) else if month = 2 if day = 7, 14, 21, or 28 return "Saturday" else if day = 1, 8, 15, or 22 return "Sunday" (and so on...) else if month = 3 (and so on...)