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

ProblemMinimum of TwoIntegersInput:Integersaandb.Output:The minimum value ofaandb.

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 `Min2()`

*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, `Min2()`

should return the value of `Min2()`

*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 `else`

. Since `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).

STOP:Does`still return the desired answer if`

`Min2()`

`a`

and`b`

are equal?

The if statement in

exemplifies a common if statement. The following hypothetical function first executes instructions `Min2()`

*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

Although

is a short function, it allows us to introduce `Min2()`

**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 `if`

as a function name.`return`

## 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!

ProblemMinimum of ThreeNumbersInput:Integersa,b, andc.Output:The minimum value ofa,b, andc.

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()`

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 `b`

.

If `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 `a`

* *and `c`

* *is smaller must be our desired minimum. Lines 3–6 of

contain the if block; in this block, we check which of `Min3()`

`a`

* *and `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.`Min3()`

We have discussed what happens in

if `Min3()`

`a`

* *is smaller than `b`

. If `a`

* *is not smaller than `b`

, then we enter the else block on lines 8–11 of

and return the smaller of `Min3()`

`b`

* *and `c`

, as shown below. These lines bring us to the end of

.`Min3()`

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?`

`Min3()`

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 `Min3()`

! How can we use what we have already done to simplify `Min2()`

?`Min3()`

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 `Min3()`

by using the value returned by the function `Min3()`

. In general, a function that occurs within the body of another function is known as a `Min2()`

**subroutine**, and in this case we say that `Min3()`

**calls**

as a subroutine.`Min2()`

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:`Min3()`

return Min2(a,c)

Although a function would normally immediately stop at a return statement,

must `Min3()`

*wait *when it encounters the call to

. In the meantime, the control flow passes to `Min2()`

, with input variables of `Min2()`

`a`

* *and `c`

. If `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 `Min3()`

terminates.`Min3()`

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.`Min3()`

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 `a`

* *and `b`

against the minimum of `c`

* *and `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()`

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 `else if`

`month`

, and then within that block jumping straight to the block corresponding to the value of `day`

. A final function incorporating

is shown below.`else if`

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