Some problems for CS students to solve

Reg Dodds
Department of Computer Science
University of Stellenbosch
rdodds@[Link]

January 20, 2013

 Summary
This is a set of simple problems that students should be able to solve by
programming them proficiently in some language. Most of the solutions
presented here are presented in a Python-like style or in executable Python
rather than in C-like, or which is similar, Java-like pseudo code.
We have chosen Python because it is so easy to learn. A pleasant side
effect is that Python forces users into the tidy habit of indenting their code
with a rigor not laid down by other languages thus ensuring clear compre-
hension of the block structure of their code.
Many more solutions than problems are presented because although we
attempt to evolve an efficient solution to each problem, there is generally
more than one way of programming it. Some of the less efficient solutions
present alternate viewpoints and add to our stock of programming tools. So
we often tackle the same problem with solutions that differ in outlook and
character. This is not limited to presenting many solutions both recursively
and iteratively but also to presenting dynamic programming or divide-and-
conquer solutions. Sometimes an alternate algorithm for the same problem
illustrates a fundamentally different approach such as deriving the algorithm
directly from an induction hypothesis, and improving the solution by refining
the hypothesis.
 Preface
These problems have been lying around in our cupboards in a less accessible
form.
James Connan used some of them with a Pascal-like pseudo code that
does not go down well with Python programmers who are used to a much
more elegant type of pseudo code that almost looks like the pseudo code
one finds in modern books on algorithms such as the book by Cormen et al.
(2009) that are not based on some specific language.
 Chapter 1

Digits and numbers

The problems in this chapter are based mainly on the properties of numbers.
We consider the digits of a number, the factors of a number, be they prime
or not, the primacy of a number, and other related problems.
Problem 1.1 Count the number of digits in integer n
Calculate the number of decimal digits of the integer n.

Solution— Counting the digits of the integer n

The digits of n are manipulated by integer division and multiplication of n by
10. We indicate integer division by ‘//’.1 So, n = n // 10 removes the last
digit of n.2 To retrieve this removed digit necessitates some manipulation.
First, consider the number (n // 10) * 10. It differs from n in having its
final digit replaced by 0; the other digits are the same. So, to get the final
digit, all we need to do is to deduct it from n as follows
1 digit = n - (n // 10) * 10
Another obvious way of calculating the last digit is to use the modulo oper-
ator, which is written as % in Python as follows:
1 digit = n % 10
But we were not asked to get the last digit, we were asked to count all the
digits of n. This is done by retrieving the last digit repeatedly and counting
1
Python 3 uses the binary operator ‘//’, while most other languages, even earlier
versions of Python, use the binary operator ‘/’ embedded between two integers to give an
integer result. When one of the operands of ‘/’ is a number with a decimal fraction or a
floating point number then the result also becomes floating point and the fraction does
not disappear—such a number then requires a function such as int() to convert it to an
integer.
2
Experienced programmers conventionally write n = n // 10 as n //= 10.

1
 these iterations as follows. We initialize the number of digits m to zero and
at each step replace n by its value with its last digit removed.
1 m = 0
2 while n > 0:
3 n = n // 10
4 m = m + 1
However, this will usually be programmed by using the ‘operate-and-becomes’
notation and embedding the code in a function.
1 def noDigits(n):
2 m = 0
3 while n > 0:
4 n //= 10
5 m += 1
6 return m
7
8 m = noDigits(n)
The variable n is unaffected by the invocation m = noDigits(n). This is not
the last word. Python has some useful built-in operators that should be
used when programming this problem. The str() function can be used to
turn the integer into a string, and the len() function counts the number of
characters in the string. The call below gives the same result.
1 m = len(str(n))

Exercise 1.2 Display the digits of the integer in reverse.

——— 

Problem 1.3 Given integers n and m calculate nm

When m is positive nm or n to the power m is defined as

nm = n × n × n × . . . m times.

More generally, the definition of n to any integer power m is


 n × n × n × . . . m times
 if m > 0,
m
n = 1 if m = 0,
 1/(n × n × n × . . . |m| times)

if m < 0.

Solution— Number raised to integer power

For positive values the power is quite easy to calculate. Simply start with a
product that is 1 and replace it m times by product × n, i.e.,

2
 1 product = 1
2 for count in range(m):
3 product = product * n
This seems to be the last word, but it is rather inefficient. We will dis-
cuss more efficient ways of doing later in Problem 4.9. In the mean time
we will use the function below to do integer exponentiation. It takes m
multiplications.
1 def power(n, m):
2 product = 1
3 for count in range(m):
4 product = product * n
5 return product
When the power is negative we proceed in the same way for |m| multiplica-
tions but invert the product. We use a boolean variable called negativePower
that becomes True when the power is negative to keep track of what action
to take.
1 def power(n, m):
2 product = 1
3 negativePower = False
4 if m < 0:
5 negativePower = True
6 m = -m
7 for count in range(m):
8 product = product * n
9 if negativePower:
10 product = 1/product
11 return product
——— 

Problem 1.4 Check if n is an Armstrong number

Design an algorithm to check if a given number n is an Armstrong number.

Suppose the number n is written in decimal form as

n = dm−1
1 10m−1 + dm−2
2 10m−2 + . . . + d2m−2 102 + dm−1 10 + dm

where each di ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} for i ∈ [1..m] and m is the number

of decimal digits of n.
The integer n is an Armstrong number if the sum of each digit of n raised to
the power m of the number of digits in the number, is equal to the original

3
 number, then that number is said to be an Armstrong number, that is, n is
an Armstrong number if the following equality holds

n = dm m m m m
1 + d2 + . . . + dm−2 + dm−1 + dm

Solution— Algorithm for Armstrong number

Given the integer n, the program must split it into its m digits, count them
to get the value of m, and then sum their powers and check if the sum equals
n.
The m digits of n are peeled of it from its rear end. The least significant digit
of n is found by integer division and multiplication. Integer division gives
an integer result by dropping the fractional part of the division. Multiplying
this result by the divisor produces the original number with a zero in the last
digit. Deducting this zero-ended number from n yields the least significant
digit—the normally most right-hand digit of n.
1 digit = n - (n // 10) * 10
In order to proceed to the next-to-last digit the last digit needs to be re-
moved. Integer division by 10 gets rid of the last digit. We adapt our code
slightly so that the final digit can be repeatedly removed until nothing—
zero—is left. The following code must be iterated to get each digit.
1 digit = n - (n // 10) * 10
2 n = n // 10
By introducing a new variable ndiv10 we can avoid doing the division twice.
The while statement runs until n becomes zero.
1 while n > 0:
2 ndiv10 = n // 10
3 digit = n - ndiv10 * 10
4 n = ndiv10
After running the while only the leftmost digit will be available, so we need
to do the summation for the Armstrong number inside the loop.
1 armstrong = 0
2 while n > 0:
3 ndiv = n // 10
4 digit = n - ndiv10 * 10
5 armstrong += digit ** m
6 n = ndiv10
This will not work yet because we have know the value of m before the loop
starts. A similar loop is necessary to determine m but we must be careful
not to destroy n in the process.

4
 1 n = int(input("Enter an integer: "))
2 m = 0
3 copyOfn = n
4 while n > 0:
5 ndiv10 = n // 10
6 m += 1
7 digit = n - ndiv10 * 10
8 n = ndiv10
9 n = copyOfn
10 # followed by Armstrong code
Expanding this gives
1 n = int(input("Enter an integer: "))
2 m = 0
3 copyOfn = n
4 while n > 0:
5 ndiv10 = n // 10
6 m += 1
7 digit = n - ndiv10 * 10
8 n = ndiv10
9 print (m)
10 n = copyOfn
11 # Determine if n is an Armstrong number
12 armstrong = 0
13 while n > 0:
14 ndiv10 = n // 10
15 digit = n - ndiv10 * 10
16 armstrong += digit ** m
17 n = ndiv10
18 n = copyOfn
19 if n == armstrong:
20 print("%d is an Armstrong number\n" % n)
——— 

Solution— 2 Algorithm for Armstrong number—stores n into an

array of digits
The procedure would run a bit faster if we stored the digits of n into an
array so that they ned not be calculated twice. So we first make an array
to hold 100 digits. In python this is a data structure called a list and we
initialize it to contain 100 zeros and then store the digits in it and alter the
second part of the program
1 digits = [0]*100
2 n = int(input("Enter an integer: "))

5
 3 m = 0
4 copyOfn = n
5 while n > 0:
6 ndiv10 = n // 10
7 digits[m] = n - ndiv10 * 10
8 n = ndiv10
9 m += 1
10 n = copyOfn
11 # Determine if n is an Armstrong number
12 armstrong = 0
13 for i in range(m):
14 armstrong += digits[i] ** m
15 if n == armstrong:
16 print("%d is an Armstrong number\n" % n)
——— 

1 # James untouched
2 digits : array[1..100] of number
3
4 get num from user
5 set cnt = 0
6 while num <> 0 do
7 begin block
8 set cnt = cnt + 1
9 set digits[cnt] = remainder of num/10
10 set num = integer part of num/10
11 end block
12 set total = 0
13 for i ranges from 1 to cnt do
14 set total = total + digits[i]\^cnt
15 if num = total then display num is an Armstrong number

Problem 1.5 Display the first 15 Armstrong numbers

1 set number = 0
2 set num = 1
3 repeat
4 set count = 0
5 while num <> 0 do
6 begin block
7 set count = count + 1
8 set digits[count] = remainder of num/10

6
 9 set num = integer part of num/10
10 end block
11 set total = 0
12 for i ranges from 1 to count do
13 set total = total + digits[i]^count
14 if num = total then
15 begin block
16 display num
17 set number = number + 1
18 end block
19 set num = num + 1
20 until number = 15

Problem 1.6 Find all the n < 10000 with nondecreasing digits
Examples of such numbers are 11, 12, . . . , 19, 22, 23, . . . , 29, 33, 34, . . . , 39.

Problem 1.7 Find all the n < 1000 with nondecreasing digits that
also have squares with nondecreasing digits
Examples of such numbers are 122 = 144i, 132 = 169, 152 = 225, 162 = 256,
372 = 1369.

Problem 1.8 Convert an integer in base 10 to another base

Given a number in base 10, convert it to a base supplied by the user. The
user supplied base can be anything between 2 and 16.

Solution— Converting between bases

If there was a limit on the size of the base 10 number, then a collection of if
statements would have sufficed. That is:
1 get Num from user
2 get Base from user
3
4 if Num > Base^n then
5 begin block
6 display integer part of Num/(Base^n)
7 set Num = remainder of Num/(Base^n)
8 end block
9 .
10 .
11 .
12 if Num > Base^0 then
13 begin block
14 display integer part of Num/(Base^0)
15 set Num = remainder of Num/(Base^0)

7
16 end block
17

18
19 where Base^n is Base to the power of n
——— 

Solution— 2
This can easily be rewritten as
1 get Num from user
2 get Base from user
3
4
5 for n ranges from x to 0 do
6 begin block
7 if Num > Base^n then
8 begin block
9 display integer part of Num/(Base^n)
10 set Num = remainder of Num/(Base^n)
11 end block
12 end block
——— 

However, we are still restricted by the size of x and 210 = 1024 is much
smaller than 910 = 3486784401

Solution— 3
We know that we can convert a number from base ten to any base by re-
peatedly dividing by the base. So we have
1 get Num from user
2 get Base from user
3
4 repeat
5 display remainder Num/Base
6 set Num = integer part of Num/Base
7 until Num = 0
——— 

Solution— 4

As a while loop

8
 1 get Num from user
2 get Base from user
3
4 while (Num <> 0) do
5 begin block
6 display remainder Num/Base
7 set Num = integer part of Num/Base
8 end block
9 Implement a binary search algorithm that displays
10 the index of the desired value and the number of
11 lookups [Link] a bubble sort [Link] a program that allows the user
12 to play blackjack against the computer.
——— 

Use a array of unique random numbers to ”shuffle” the cards.d

Problem 1.9 Cash register

When a cash purchase is made, the cashier normally has to give the
customer change. The customer does not want a bulky wallet, so it is up
to the cashier to give the customer the smallest number of notes and coins.
Write an algorithm to assist the cashier in determining which notes and
coins to give the customer.

Answer
What do we need? The total of the purchase made. The amount ten-
dered.
What do we know? The following notes and coins are available to us:
R200, R100, R50, R20, R10, R5, R2, R1, 50c, 20c, 10c, 5c, 2c, 1c
What do we want to do? We want to minimize the number of coins
and notes used, so we want to always use the biggest (in value) notes and
coins possible. So we start with the biggest denomination and work our way
down, each time calculating how many of that denomination to return.

Solution— 1

1 get purchase Total from user

2 get Amount tendered from user
3 set Change = Amount - Total
4
5 if Change >= R200 then
6 begin block

9
 7 display R200 x integer part of Change/R200
8 set Change = remainder of Change/R200
9 end block
10 if Change >= R100 then
11 begin block
12 display R100 x integer part of Change/R100
13 set Change = remainder of Change/R100
14 end block
15 if Change >= R50 then
16 begin block
17 display R50 x integer part of Change/R50
18 set Change = remainder of Change/R50
19 end block
20 if Change >= R20 then
21 begin block
22 display R20 x integer part of Change/R20
23 set Change = remainder of Change/R20
24 end block
25 if Change >= R10 then
26 begin block
27 display R10 x integer part of Change/R10
28 set Change = remainder of Change/R10
29 end block
30 if Change >= R5 then
31 begin block
32 display R5 x integer part of Change/R5
33 set Change = remainder of Change/R5
34 end block
35 if Change >= R2 then
36 begin block
37 display R2 x integer part of Change/R2
38 set Change = remainder of Change/R2
39 end block
40 if Change >= R1 then
41 begin block
42 display R1 x integer part of Change/R1
43 set Change = remainder of Change/R1
44 end block
45 if Change >= 50c then
46 begin block
47 display 50c x integer part of Change/50c
48 set Change = remainder of Change/50c
49 end block
50 if Change >= 20c then
51 begin block

10
52 display 20c x integer part of Change/20c
53 set Change = remainder of Change/20c
54 end block
55 if Change >= 10c then
56 begin block
57 display 10c x integer part of Change/10c
58 set Change = remainder of Change/10c
59 end block
60 if Change >= 5c then
61 begin block
62 display 5c x integer part of Change/5c
63 set Change = remainder of Change/5c
64 end block
65 if Change >= 2c then
66 begin block
67 display 2c x integer part of Change/2c
68 set Change = remainder of Change/2c
69 end block
70 if Change >= 1c then
71 begin block
72 display 1c x integer part of Change/1c
73 set Change = remainder of Change/1c
74 end block
——— 

Solution— 2

The algorithm above solves the problem, but is not very elegant. It
would be nice if we could find a way of using a loop rather than writing so
many if statements. We notice that the pattern 5xx, 2xx, 1xx is repeated.
In fact, if we had a R500 note, we would have had the same pattern 5xx,
2xx, 1xx repeated 5 times, decreasing by a factor 10 every time. So we will
use this to to implement a more elegant solution. In order to make it easier
for reader to follow, it will be assumed that all amounts are in cents instead
of Rands and cents. (Converting all amounts to cents can easily be achieved
multiplying by 100.)
1 get purchase Total from user
2 get Amount tendered from user
3 set Change = Amount - Total
4

5 set One = 50000

6 set Two = 20000
7 set Three = 10000

11
 8
9 repeat
10 if (Change >= One) and (One < 50000) then
11 begin block
12 if One >= 500 then
13 display R(One/100) x integer part of Change/One
14 else display (One)c x integer part of Change/One
15 set Change = remainder of Change/One
16 set One = One/10
17 end block
18 if (Change >= Two) then
19 begin block
20 if Two >= 200 then
21 display R(Two/100) x integer part of Change/Two
22 else display (Two)c x integer part of Change/Two
23 set Change = remainder of Change/Two
24 set Two = Two/10
25 end block
26 if (Change >= Three) then
27 begin block
28 if Three >= 100 then
29 display R(Three/100) x integer part of Change/Three
30 else display (Three)c x integer part of Change/Three
31 set Change = remainder of Change/Three
32 set Three = Three/10
33 end block
34 until Change = 0
——— 

Solution— 3

The algorithm can be rewritten using a while loop.

1 get purchase Total from user
2 get Amount tendered from user
3 set Change = Amount - Total
4
5 set One = 50000
6 set Two = 20000
7 set Three = 10000
8
9 while Change <> 0) do
10 begin block
11 if (Change >= One) and (One < 50000) then
12 begin block

12
13 if One >= 500 then
14 display R(One/100) x integer part of Change/One
15 else display (One)c x integer part of Change/One
16 set Change = remainder of Change/One
17 set One = One/10
18 end block
19 if (Change >= Two) then
20 begin block
21 if Two >= 200 then
22 display R(Two/100) x integer part of Change/Two
23 else display (Two)c x integer part of Change/Two
24 set Change = remainder of Change/Two
25 set Two = Two/10
26 end block
27 if (Change >= Three) then
28 begin block
29 if Three >= 100 then
30 display R(Three/100) x integer part of Change/Three
31 else display (Three)c x integer part of Change/Three
32 set Change = remainder of Change/Three
33 set Three = Three/10
34 end block
35 end block
——— 

Solution— 4

The algorithm in Solutions 2 and 3 still uses multiple if statements. We

can reduce this by recognizing another pattern.
R200.00 R100.00 R50.00
R20.00 R10.00 R5.00
R2.00 R1.00 R0.50
R0.20 R0.10 R0.05
R0.02 R0.01
We can obtain the next denomination by halving the current one. Every
third time we multiply by 2/5. We continue to use only cents and the
algorithm now becomes:
1 get purchase Total from user
2 get Amount tendered from user
3 set Change = Amount - Total
4
5 set Denommination = 200000
6 set Cnt = 1

13
 7
8 while (Change <> 0) do
9 begin block
10 if (Change >= Denomination) then
11 begin block
12 if Denomination >= 100 then
13 display R(Denomination/100) x integer part of Change/Denomination
14 else display (Denomination)c x integer part of Change/Denomination
15 set Change = remainder of Change/Denomination
16 end block
17 if Cnt is divisible by 3 then set Denomination = 2*Denomination/5
18 else set Denomination = Denomination/2
19 set Cnt = Cnt + 1
20 end block
——— 

Solution— 5

We can also use our knowledge of arrays to solve the problem. We use
a two dimensional array to store the number of each denomination needed.
First we initialize the array with the denominations and we zero the number
for each.
Money is an array[1..2][1..14] of numbers.
1 get purchase Total from user
2 get Amount tendered from user
3 set Change = Amount - Total
4
5 set Denomination = 20000
6
7 for Index ranges from 1 to 14 do
8 begin block
9 set Money[1][Index] = Denomination
10 set Money[2][Index] = 0
11 if Index is divisible by 3 then
12 set Denomination = 2*Denomination/5
13 else set Denomination = Denomination/2
14 end
15
16 set Cnt = 1
17
18 while (Change <> 0) do
19 begin block
20 if Change >= Money[1][Cnt] then

14
21 begin block
22 set Money[2][Cnt] = integer part of Change/Money[1][Cnt]
23 set Change = remainder of Change/Money[1][Cnt]
24 end block
25 set Cnt = Cnt + 1
26 end block
27
28 set Cnt = 1
29
30 while (Money[1][Cnt] >= 100) do
31 begin block
32 if Money[2][Cnt] > 0 then
33 display R(Money[1][Cnt]/100) x Money[2][Cnt]
34 set Cnt = Cnt + 1
35 end block
36
37 repeat
38 if Money[2][Cnt] > 0 then
39 display (Money[1][Cnt])c x Money[2][Cnt]
40 set Cnt = Cnt + 1
41 until Cnt > 14
——— 

Problem 1.10 Determine if a number N is prime

Given a number (N), write an algorithm to determine if the number is prime
or not.

What is a prime number?

It is a number that is divisible only by itself and 1.

How would we check to see if a number is prime or not?

If a number is divisible by any number other than 1 or itself, then that
number is not prime.

Solution— Algorithm for primes by trial division

In plain English
1. Get the number to check.

2. Assume the number is prime.

3. Test divisibility of the number by all potential factors between 1 and

the number itself.

15
 4. If the number is divisible by any of these numbers, then it is not prime,
otherwise it is prime.
In pseudocode
1 get Num from user
2 get IsPrime = True
3 for PFactor ranges from 2 to Num-1 do
4 begin block
5 if Num divisible by PFactor then set IsPrime = False
6 end block
7 if IsPrime = True then display Num is prime
8 else display Num is not prime
——— 

Solution— Slightly improved prime checker

If we look at the factors of non-prime numbers, we notice that they are

symmetrical around the square root of the number. That is, for say 36, the
factors are 1 × 36, 2 × 18, 3 × 12, 4 × 9, 6 × 6, 9 × 4, 12 × 3, 18 × 2, and 36 × 1.
Therefore we only need to check each potential factor up to the square root
of the number. Also, as soon as we find a factor for the number, we can
stop checking because the number is not prime.
In plain English
1. Get the number to check.

2. Check all potential factors until the factor is greater than the square
root of the number or we find a factor that divides into the number
without a remainder.
In pseudocode
1 repeat loop
2
3 get Num from user
4 set PFactor = 1
5 repeat
6 set PFactor = PFactor + 1
7 until (PFactor > square root of (Num)) or (Num divisible by PFactor)
8 if PFactor <= square root of (Num) then display Num is not prime
9 else display Num is prime
10
11 while loop begin block
12 get Num from user

16
13 set PFactor = 2
14 while (PFactor <= square root of (Num)) and (Num not divisible by PFactor)
15 begin block
16 set PFactor = PFactor + 1
17 end block
18 if PFactor <= square root of (Num) then display Num is not prime
19 else display Num is prime
——— 

Problem 1.11 Write a program that will convert and angle from
decimals to degrees minutes and seconds.

Problem 1.12 Write a program that will convert a number from

digits to its English equivalent.
For example 105 becomes one hundred and [Link]

Problem 1.13 Greatest common divisor—GCD

Write and algorithm to find the GCD (Greatest Common Divisor) of two
numbers, x and y.

Solution— 1

What is the GCD?

It is the biggest number that divides into both x and y without leaving
a remainder.
This means that the biggest possible GCD is at most the smaller of the
two numbers.
1 get x from user
2 get y from user
3
4 if x > y then set Smaller = y
5 else Smaller = x
6

7 for PFactor ranges from 1 to Smaller do

8 begin block
9 if (x divisible by PFactor) and (y divisible by PFactor) then GCD = PFactor
10 end block
11 display GCD
——— 

17
 Solution— GCD version 2
We can reduce the execution time of the algorithm by first checking if the
smaller number is the GCD and then checking all numbers less then it and
stopping as soon as we find a factor.
1 get x from user
2 get y from user
3
4 if x > y then set Smaller = y
5 else Smaller = x
6

7 set GCD = Smaller

8
9 While not((x divisible by GCD) and (y divisible by GCD)) do
10 set GCD = GCD - 1
11 display GCD
The condition for the while statement can also be written as: While (x
not divisible by GCD) or (y not divisible by GCD) do ——— 

Solution— 3
Two millennia and three centuries ago Euclid presented us with an even
more elegant solution. He showed that
1 GCD(x, y) = GCD(y, remainder of x/y) if y > 0
2 GCD(x, y) = x if y = 0
3
4 In pseudocode this is:
5

6 get x from user

7 get y from user
8
9 while (y > 0) do
10 begin block
11 set Tmp = remainder of x/y
12 set x = y
13 set y = tmp
14 end block
15 display GCD = x
——— 

Problem 1.14 GCD of a list of numbers

Find the GCD of any list of numbers.

18
 Solution— GCD of a list numbers
The GCD of three or more numbers can be found by finding the GCD of
pairs of numbers. That is:
1 GCD (x, y, z) = GCD (x, GCD (y, z)) or GCD (x, y, z) = GCD ( GCD (x, y), z)
——— 

Solution— GCD of a list numbers

If can also be found using the same strategy as used in Solutions 1 and 2.
Solution 2, for three numbers would then be
1 get x from user
2 get y from user
3 get z from user
4
5 if (x > y) and (z > y) then set Smallest = y
6 if (x > z) and (y > z) then set Smallest = z
7 if (y > x) and (z > x) then set Smallest = x
8
9
10 set GCD = Smaller
11

12 While not((x divisible by GCD) and (y divisible by GCD) and (z divisible by GCD)) do
13 set GCD = GCD - 1
14 display GCD
——— 

Problem 1.15 Convert marks into letter grades

Write a program that will convert a mark as a given as a percentage to grade
symbol, e.g. 80% becomes an ‘A’.

Problem 1.16 Guess the number

Write a program that will generate a random integer, in the range, starting
with [1..10] and allow the user to guess the number.
After each guess the program tells the user if the guess was to high or
too low. After 12 or so unsuccessful guesses the game is lost.
Introduce levels so that each time the user guesses the number correctly,
a new number is generated in from a larger range. Each time the user fails
to guess the correct number within the allowed number of guesses, they get
demoted to a lower level.

Problem 1.17 Lowest common denominator—LCM

Find the LCM (Lowest Common Denominator) of two numbers, x and y.

19
 What is the LCM?
It is the smallest number that is divisible by both x and y. That is, into
which both x and y will divide without leaving a remainder.
What do we know about the LCM?
The LCM must be greater than or equal to the larger of x and y. The
LCM must be less than or equal to the product of the x and y.

Solution— LCM 1

1 get x from user

2 get y from user
3
4 if x > y then set Greater = x
5 else set Greater = y
6

7
8 for PLCM ranges from (x*y) to Greater do
9 if (PLCM is divisible by x) and (PLCM is divisible by y) then set LCM = PLCM
10 display LCM
——— 

Solution— 2
Solution 1 will always check all numbers between the larger (of x and y) and
the product (of x and y). We can also rewrite the algorithm in such a way
that it will only check numbers up to and including the LCM and then stop.
1 get x from user
2 get y from user
3
4 if x > y then set Greater = x
5 else set Greater = y
6

7 set PLCM = Greater

8 set LCM = 1
9
10 repeat
11 if (PLCM is divisible by x) and (PLCM is divisible by y) then set LCM = PLCM
12 set PLCM = PLCM + 1
13 until (LCM is divisible by x) and (LCM is divisible by y)
14 display LCM
Note: LCM is used to terminate the loop because the value of PLCM
is changed after assigning it to LCM. Also, LCM is initialized otherwise it

20
 has no definite value until the condition for the if statement is satisfied.
——— 

Solution— LCM 3
We know that if one number is divisible by another number, then the first
number must be a multiple of the second number. That is, 100 is divisible
by 10. 100 is a multiple of 10. 10 x 10 = 100. Only multiples of 10 will
be divisible by 10 (10, 20, 30, ...). We therefore do not even need to check
numbers between 10 and 20, or 20 and 30, etc. Solution 2 can therefore be
improved as follows:
1 get x from user
2 get y from user
3
4 if x > y then set Greater = x
5 else set Greater = y
6
7 set PLCM = Greater
8 set LCM = 1
9
10 repeat
11 if (PLCM is divisible by x) and (PLCM is divisible by y) then set LCM = PLCM
12 set PLCM = PLCM + Greater
13 until (LCM is divisible by x) and (LCM is divisible by y)
14 display LCM
——— 

Solution— LCM 4

Solution 3 can be rewritten using a while loop.

1 get x from user
2 get y from user
3
4 if x > y then set Greater = x
5 else set Greater = y
6
7 set PLCM = Greater
8

9 while not ((PLCM is divisible by x) and (PLCM is divisible by y)) do

10 set PLCM = PLCM + Greater
11
12 display PLCM

21
 Note: We are checking the loop termination condition before changing
PLCM, so we do not need to make a copy of it. When the loop terminates,
PLCM will be the LCM. Also, the not can be moved into the bracket,
changing the condition from not((PLCM is divisible by x) and (PLCM is
divisible by y)) to (PLCM is not divisible by x) or (PLCM is not divisible
by y) ——— 

Problem 1.18 Solve a set of n linear equations

Write a program that will solve a set of n linear equations in n unknowns.
Write a program that allows the user to perform matrix operations, such
as matrix addition, subtraction, and multiplication. Write a program that
generates two random arrays (reuse your old code) of length n and m respec-
tively. Merge the two arrays into one by alternately selecting elements from
[Link] a program that takes two sorted arrays and produces a single
sorted array.

Problem 1.19 Merge two sorted lists

Given arrays sorted n ascending order, merge them to produce one sorted
array.

Solution— Merge two sorted lists

1 arrone : array [1..n] of number

2 arrtwo : array [1..m] of number
3 arrthree : array [1..(m+n)] of number
4
5 procedure merge
6 begin block
7 set cnt1 = 1
8 set cnt2 = 1
9 set cnt3 = 1
10 while (cnt1 <= n) and (cnt2 <= m) do
11 begin block
12 if arrone[cnt1] < arrtwo[cnt2] then
13 begin block
14 set arrthree[cnt3] = arrone[cnt1]
15 set cnt1 = cnt1 + 1
16 end block
17 else
18 begin block
19 set arrthree[cnt3] = arrtwo[cnt2]
20 set cnt2 = cnt2 + 1

22
21 end block
22 set cnt3 = cnt3 + 1
23 end block
24 if cnt1 > n then
25 begin block
26 for i ranges from 0 to m-cnt2 do
27 set arrthree[cnt3+i] = arrtwo[cnt2+i]
28 end block
29 else
30 begin block
31 for i ranges from 0 to n-cnt1 do
32 set arrthree[cnt3+i] = arrone[cnt1+i]
33 end block
34 end block
——— 

Problem 1.20 Find all the prime numbers from 2 to N .

There are many useful variations of this problem.

Problem 1.21 Find the first N primes

Solution— Find primes

What is a prime number?
It is a number that is divisible only by itself and 1.
How would we check to see if a number is prime or not?
If a number is divisible by any number other than 1 or itself, then that
number is not prime.
What do we know/have?
We have already constructed several algorithms to check whether a number
is prime or not. All we need to know now is use one of these algorithms to
check all numbers and count each prime until we have N of them.
Algorithm
In plain English
Get N , the number of primes the user wishes to find Check all numbers from
2 up until we have found N primes
In plain English, refine
1 Get N, the number of primes the user wishes to find
2

23
 3 Start with 2
4 Repeat
5 Assume the number is prime
6 Test divisibility of the number by all possible numbers
7 between 1 and the number itself
8 If the number is divisible by one of these numbers, then
9 it is not prime,
10 Otherwise
11 it is prime,
12 count it
13 Until we have found N primes
In slightly more exact pseudocode
1 repeat loop
2
3 get N from user
4 set Count = 0
5 set Num = 2
6 repeat
7 set PFactor = 1
8 repeat
9 set PFactor = PFactor + 1
10 until (PFactor > square root of (Num)) or (Num divisible by PFactor)
11 if (PFactor <= square root of (Num)) then display Num is not prime
12 else
13 begin block
14 display Num is prime
15 set Count = Count + 1
16 end block
17 until Count = N
Another more refined version
1 while loop
2
3 get N from user
4 set Count = 0
5 set Num = 2
6 while Count < N do begin block
7 set PFactor = 2
8 while (PFactor < square root of (Num)) and
9 (Num not divisible by PFactor) do
10 set PFactor = PFactor + 1
11
12 if (PFactor <= square root of (Num)) then
13 display Num is not prime

24
14 else begin block
15 display Num is prime
16 set Count = Count + 1 end block end block
——— 

Problem 1.22 Numeric integration by summing rectangles

Given a function y = f (x), an interval [xi , xi+1 ], and a number n of intervals
such that i = 0, 1, . . . , n − 1.

Find the approximate area under the curve by calculating and summing the
areas of each rectangle of width xi − xi+1 and height f (xi ).

Solution— Integration
We slice the area under the graph into n rectangles and calculate the area of
each rectangle. Summing the areas of each rectangle will yield an approxi-
mation for the total area under the graph.
If we substitute a value for x into the equation, we get the corresponding y
value. This y = f (xi ) value represents the height of the rectangle. Using xi
and xi+1 we can calculate the width. Thus we can calculate the area of the
rectangle. If we sum the areas of all these rectangles that are in the interval
[a, b] then we get the approximate area under the graph. It should be clear
that the sum of these rectangles is less than the area under the curve.
1 get f from user
2 get a from user
3 get b from user
4 get n from user
5
6 set Area = 0
7 for Tmp ranges from a to b in steps of (b - a)/n do
8 set Area = Area + f(Tmp)*width
9 display Area
——— 

We can improve this approximation by using the second ordinate for the
value of the height, and following the same procedure. This approximates
the actual area under the curve from above. The average of these two values
will provide a much better approximation of the integral. Without repeating
the whole process the following idea achieves the same result.

25
Problem 1.23 Numeric integration by summing trapezia3
This problem is often posed as finding an approximation to the definite in-
tegral
Z b
f (x)dx.
a
Find the approximate area under the curve by calculating and summing the
areas under each trapezium bounded by the x-axis, by the two ordinates
xi –f (xi ), xi+1 –f (xi+1 ), and the line (xi , f (xi ))–(xi+1 , f (xi+1 )). Figure1.1
shows the ith trapezium. The function f (x) is given. and the bounds of the

fofx
fxpi

fxi

xi xpi

Figure 1.1: A trapezium.

area to be approximated are given as the closed interval [a, b].

3
If you do not know Latin you might be inclined to spell the plural of trapezium as
trapeziums. Some people talk of trapezoids.

26
Chapter 2

Binomial coefficients and

Pascal’s triangle

2.1 Binomial coefficients

Consider the binomial (x + y)n for n = 0. Since (x + y)0 = 1, the terms in
x and y disappear and we write down a single 1. Putting n = 1

(x + y)1 = 1x + 1y,

and we get a 1 and another 1. When n = 2 the equation becomes

(x + y)2 = 1x2 + 2xy + 1y 2

giving 1, 2, and 1 again. Next for n = 3 the equation becomes

(x + y)3 = (x + y)(1x2 + 2xy + 1y 2 )

= 1x3 + 2x2 y + 1xy 2
= + 1x2 y + 2xy 2 + 1y 3
= 1x3 + 3x2 y + 3xy 2 + 1y 3 ,

yielding the coefficients 1, 3, 3, and 1. In general we write

n
!
n
X n
(x + y) = xr y n−r (2.1)
r=0
r

giving the coefficients as the numbers nr . For now we know that 30 = 1,

3
3
3

1 = 3, 2 = 3, 3 = 1. One of the tasks we set is to calculate these

27
coefficients in various ways. Before doing this we look at a property that we
can derive from Equation 2.1 by setting both x and y to 1,
n
!
n
X n
2 = 1r 1n−r
r=0
r

So
n
!
X n
= 2n (2.2)
r=0
r

Pascal’s triangle is an arrangement of the binomial coefficients in a table.

We will call the number in Row n and Column r, C(n, r). The table is easy
to calculate. Assume that all the values in Column 0, C(i, 0) = 1, for
i = 1, 2, . . . and the values in Column 1 are In column 1 the values are given
by C(i, 1) = i for i = 1, 2, . . .. This makes C(1, 0) = 1 and C(1, 1) = 1,
Consider a portion of the table of numbers of the binomial coefficients in a

Columns
Rows r−1 r
n−1 C(n − 1, r − 1) C(n − 1, r)
n C(n, r − 1) C(n, r) = C(n − 1, r − 1) + C(n − 1, r)

triangle. It is named after Blaise Pascal. It has been studied for centuries
and is still the focus of vigorous attention.
The rows of Pascal’s triangle are conventionally enumerated starting
with row zero, and the numbers in odd rows are usually staggered rela-
tive to the numbers in even rows. A simple construction of the triangle
proceeds in the following manner. On the zeroth row, write only the num-
ber 1. Then, to construct the elements of following rows, add the num-
ber directly above and to the left with the number directly above and
to the right to find the new value. If either the number to the right or
left is not present, substitute a zero in its place. For example, the first
number in the first row is 0 + 1 = 1, whereas the numbers 1 and 3 in
the third row are added to produce the number 4 in the fourth row.”

28
 n
n
n
n
n
n
n
n
n
n
n
n

n 0 1 2 3 4 5 6 7 8 9 10 11
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
9 1 9 36 84 126 126 84 36 9 1
10 1 10 45 120 210 252 210 120 45 10 1
11 1 11 55 165 330 462 462 330 165 55 11 1

Problem 2.1 Display Pascal’s triangle

Design an algorithm that will display a Pascal triangle. Use recursion to

calculate the terms.

b(n, k) = b(n − 1, k − 1) + b(n − 1, k)b(n, 0) = 1b(n, n) = 1

Solution— A recursive algorithm

Recursive function to calculate terms

1 function pascal(n,k)
2 begin block
3 if (k = 0) or (k = n) then return set pascal = 1
4 else return set pascal = pascal(n-1, k-1) + pascal(n-1, k)
5 end block
——— 

Solution— Binomial coefficients using addition

——— 

Problem 2.2 Display Pascal’s triangle

Pascal’s triangle must be presented in a tabular form.

Problem 2.3 Display Pascal’s triangle as a triangle

Display Pascal’s triangle in the form

29
 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

By convention the first row is called ‘Row 0’. The sum of its coefficients
is 1. The sum of the coefficients of Row 4 is 15, in general the sum of the
binomials in row r is 2r .

Solution— Displaying Pascal’s triangle

1 get num from user

2 for n ranges from 0 to num do
3 begin block
4 for k ranges from 0 to num do
5 begin block
6 display pascal(n, k)
7 end block
8 end block
——— 

Problem 2.4 Perfect numbers

Design an algorithm that will check if a number supplied by the user is a
perfect number.
A perfect number is a number, n, such that:

n = f1 + f2 + . . . + fk

where the fi , i = 1, 2, . . . , k are the factors of n.

In other words: If a number is equal to the sum of all its factors, exclud-
ing itself, then that number is a perfect number.

Algorithm

Solution— Perfect numbers

This function finds all the factors of a number, places them in an array and
returns the number of factors found.

30
 1 factors : array [1..1000] of numbers
2

3 function fact (num)

4 begin block
5 set cnt = 0;
6 for i ranges from 1 to num do
7 begin block
8 if num is divisible by i then
9 begin block
10 set cnt = cnt + 1
11 set factors[cnt] = i
12 end block
13 end block
14 return set fact = cnt
15 end block
The main algorithm
1 get num from user
2 count = fact (num)
3 set total = 0
4 for i ranges from 1 to count - 1 do
5 set total = total + factors(i)
6 if total = num then display num is a perfect number
——— 

Problem 2.5 Display the first 15 perfect numbers

Solution— Display the first 15 perfect numbers

1 set count = 0
2 set num = 1
3 repeat
4 count = fact (num)
5 set total = 0
6 for i ranges from 1 to count - 1 do
7 set total = total + factors(i)
8 if total = num then
9 begin block
10 set count = count + 1
11 display num
12 end block
13 set num = num + 1
14 until count = 15

31
 ——— 

Problem 2.6 Prime numbers again

Use an array to construct an efficient algorithm to find prime numbers.

Solution— Prime numbers with an array

We know that if n is divisible by d, then n must also be divisible by all of
d’s factors, e.g. 16 is divisible by 8. It is also divisible by 8’s factors, 1, 2,
4. This means that when we check for factors of a number we can ignore
compound numbers and consider only the prime divisors of n. ——— 

Let’s find the first 1000 prime numbers

Algorithm
1 primes : array [1..1000] of numbers
2

3 set num_of_primes = 1
4 set primes[num_of_primes] = 2
5 set number_to_test = 3
6 repeat
7 set cnt = 1
8 while (num_to_test is not divisible by primes[cnt])
9 and (primes[cnt] < sqrt(num_to_test)) do
10 begin block
11 set cnt = cnt + 1
12 end block
13 if num_to_test is not divisible by primes[cnt] then
14 begin block
15 set num_of_primes = number_of_primes + 1
16 set primes[number_of_primes] = num
17 end block
18 set num_to_test = num_to_test + 1
19 until num_of_primes = 1000
20 for i ranges from 1 to 1000 do
21 display primes[i]

Problem 2.7 2
Find all prime numbers between Num1 and Num2.

Solution— Getting primes

What is a prime number? It is a number that is divisible only by itself

and 1.

32
 How would we check to see if a number is prime or not? If a number
is divisible by any number other than 1 or itself, then that number is not
prime.
What do we know/have? We have already constructed several algorithms
to check whether a number is prime or not. All we need to know now is use
one of these algorithms to check each number between Num1 and Num2.
Algorithm in plain English
1 Get Num1, the lower boundary of the range
2 Get Num2, the upper boundary of the range
3 For each number between Num1 and Num2
4 1. Assume the number is prime
5 2. Test divisibility of the number by all potential factors
6 between 1 and the number itself
7 3. If the number is divisible by any of these numbers,
8 then it is not prime, otherwise it is prime
Algorithm in pseudocode using a repeat loop
1 repeat loop
2
3 get Num1 from user
4 get Num2 from user
5 for Num ranges from Num1 to Num2 do
6 begin block
7 set PFactor = 1
8 repeat
9 set PFactor = PFactor + 1
10 until (PFactor > square root of (Num))
11 or (Num divisible by PFactor)
12 if PFactor <= square root of (Num) then
13 display Num is not prime
14 else display Num is prime
15 end block
Algorithm in pseudocode using a while loop
1 while loop
2
3 get Num1 from user
4 get Num2 from user
5 for Num ranges from Num1 to Num2 do
6 begin block
7 set PFactor = 2
8 while (PFactor < square root of (Num)) and (Num not divisible by PFactor)
9 begin block
10 set PFactor = PFactor + 1

33
11 end block
12 if PFactor <= square root of (Num) then display Num is not prime
13 else display Num is prime
14 end block
——— 

34
Chapter 3

UWC Computer Science I:

Problem Solving

James Connan
jconnan@[Link]

3.1 Academic Responsibility

Academic dishonesty will not be tolerated. Students suspected of academic
dishonesty will be referred to the Proctor’s office.

3.2 Course Objectives

• Read, understand and solve problems

• Apply Problem solving techniques

• Understand sequence, selection and repetition control structures

• Design algorithms to solve problems

• Express algorithms in pseudo code or structured diagrams

• Improve analytical thinking and problem solving skills

35
3.3 What does a Computer Scientist do?
Computer Scientists use computers to solve problems.
Often new software needs to be developed to solve problems.
Software development requires problem solving and programming skills.

3.4 What is problem solving?

Problem solving is a process.
The first step in problem solving is understanding and exploring the prob-
lem.
Next a strategy for solving the problem must be found.
Use the strategy to solve the problem.
Reflect on the solution.

3.5 What are Algorithms?

Algorithms describe methods by which tasks are to be accomplished.
An algorithm is a set of instructions.
When an algorithm is executed a task is accomplished.

Example algorithms
Knitting pattern, e.g. cardigan, jersey.
Assembly Instructions, e.g. models, furniture, etc.
Recipe, e.g. pancake, pumpkin fritter, scones.
Pattern, e.g. dress, blouse, shirt, trousers, etc.
Musical score, e.g. for Beethoven’s Fifth Symphony, Beatles’ Ob-La-Di,
Ob-La-Da, etc.)

3.6 Syntax, Semantics and Logic

When designing algorithms there are certain common errors that must be
avoided. These are errors in syntax, semantics and logic. Syntax rules state
how symbols in a language are used. In the sentence ‘sleeve the seams’ or
the expression ‘2+=3’ valid English and mathematical symbols are used, but
the way they are combined does not result in a valid sentence or expression.
Semantic rules determine the meaning of symbols. The sentence ‘The
elephant ate the peanut.’ is a valid English sentence, but ’The peanut ate

36
the elephant.’ makes no sense.
Logic rules check if the solution properly describes the process. If an
incorrect formula is used, or instructions are executed in incorrect order,
then the algorithm will fail.

3.7 Stepwise/Top-down Refinement of Algorithms

When constructing an algorithm, it is a good idea to start off by describing
the solution in the most general terms. So, designing an algorithm to make
a cup of coffee, the first iteration yields:
1. boil water
2. put coffee in cup
3. add water to cup
Each step is now examined and were sensible further refinements are
made.
1. boiled water
This can be further refined by saying:
1.1. fill kettle
1.2. switch on kettle
1.3. wait until boil
1.4. switch off kettle

2. put coffee in cup

Can be expanded to:
2.1. open coffee jar
2.2. measure coffee
2.3. put coffee in mug
2.4. close coffee jar

3. add water to cup

Becomes
3.1. pour water from kettle into mug until mug full
Again the algorithm is checked to see if there are any steps that need
further refinement.
1. boil water
1.1. fill kettle
1.1.1. put kettle under tap

37
 1.1.2. turn on tap
1.1.3. wait until kettle full
1.1.4. turn off tap
1.2. switch on kettle
1.3. wait until boil
1.3.1. wait until kettle whistles
1.4. switch off kettle
2. put coffee in cup
2.1. open coffee jar
2.1.1. take jar off shelf
2.1.2. remove lid
2.2. measure coffee
2.3. put coffee in mug
2.4. close jar
2.4.1. replace lid
2.4.2. replace jar on shelf
3. add water to cup
3.1. pour water from kettle into mug until mug full
There are no now further sensible refinements that can be made to the
algorithm, so the algorithm is complete.

3.8 Sequential Algorithms

The coffee-making algorithm is an example of a sequential algorithm. Se-
quential algorithms have the following characteristics:

1. Steps are executed one at a time.

2. Each step is executed exactly once: none are repeated or omitted.

3. The steps are executed in the same order in which they are written.

4. Termination of the last step implies termination of the algorithm.

3.9 Trace Tables

Trace tables are used to verify that the algorithm performs the desired task.
All variables are written down in such a way as to serve as headers for
columns that will be used to track them as the algorithm is executed. The
algorithm is then executed one line at a time and changes to all variables
are noted. It may be desirable to keep track of any output produced by the
algorithm as well.

38
3.10 Conditionals
Sequential algorithms allow us to solve many problems, but sometimes the
solution to a problem cannot be expressed in a sequential way. There may
also be instructions that we only want to execute under certain conditions.
In the coffee making algorithm, for example, if the kettle is already full we
do not need to fill it. The conditional statements we have are as follows:
if condition then
statement
The statement will only be executed if the condition holds.
if condition then
statement1
else
statement2
If the condition holds statement1 is executed and if it does not hold statement2
is executed.
case variable of
condition1: statement1
condition2: statement2
condition3: statement3
. . .
Case statements can be used to replace multiple if statements. If the variable
matches condition1 then statement1 will be executed. The same holds for
condition2, condition3, etc.

3.11 Looping Constructs

Solutions often include some form of repetition. The same action is repeated
over and over with few or no changes. If the objective is to work out the
average of some numbers then the number must be read in and totalled
one at a time until all numbers have been added. The total is then divided
by the number of numbers to obtain the average. There are three looping
structures available to us. These are the for-loop, the while-loop and the
repeat-loop.

3.11.1 The for-loop

for variable ranges from startvalue to endvalue do

statement

39
The value of variable is set to startvalue. The statement is then executed.
The value of variable is then incremented and statement is executed again.
This is repeated until the value of variable exceeds endvalue. At this stage
the loop exits. It is also possible to set startvalue higher than endvalue
and decrement variable each iteration until it reaches endvalue.
3.11.2 The while-loop

while condition do
statement
As long as the condition is valid the while-loop will continue executing
the statement. This means that statement must change something to allow
condition to become untrue or the loop will never terminate. There are
examples where it is desirable to have a loop that never terminates, but in
most cases this is not true.
3.11.3 The repeat-loop

repeat
statement
until condition
The statement will be executed until the condition is met. If the
statement does not change something to allow the condition to become true
then the loop will never terminate.
Some rules of thumb for loops
1. If we know exactly how many times we want a loop to be executed, it
is normally desirable to use a for-loop.

2. The main difference between a while-loop and repeat-loop is that

with a while-loop the condition is checked before the loop is entered
while with a repeat-loop the condition is checked after the first iter-
ation of the loop.

3. repeat-loops and while-loops are usually interchangeable. In order

to change from the one to the other the condition needs to be negated.

3.12 Statement Blocks

So far we have only referred to single statements. If we have multiple state-
ments we can encapsulate them with a begin block and end block. These
statements then become a single unit.

40
begin block
statement
statement
statement
end block

begin ... end\\

{ ... }
Nested Loops
Loops within loops
Arrays
Many problems require the use of lists as part of the solution. One way
to handle lists is to use arrays. The syntax is as follows:
arrayname: array [start..end] of type
where, arrayname is the name of the array, start..end is the range of the
array, and type is the type of data that can be stored in the array
Examples
num: array [1..3] of number
num: 1 2 3

number [ ]
This array provides us with a variable, num, that has three ‘slots’ of type
number in which we can store values. These ‘slots’ are accessed by using
num[1], num[2] and num[3].
word: array[1..15] of character

word: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

number [ ]
This array provides us with 15 ‘slots’ of type character. They are accessed
by using word[1], word[2], ... , word[15].
num: array [5..8] of number

41
 num: 5 6 7 8

number [ ]
This provides us with four ‘slots’ referenced using num[5], num[6], num[7]
and num[8].
set arr[2] = 7
This will store the value 7 in the position two of the array.
set arr[i] = 5
This will store the value 5 in position i of array arr. The value i must
be within the range of the array. That means that the value of i must be
between start and end.
set arr[i+1] = 5
Same as above, except that i+1 must now be within the range of the
array.
set arr[5] = arr[7]
This will set the value of the 5’th element of the array equal to the value
of the 7’th element.
set num = arr[3]
This will set the value of num equal to the value stored in position 3 of
array arr.
Arrays can have more than one dimensions. That is:
num : array [1..3][1..5] of number
num: 1 2 3 4 5
1

2
3

number [ ][ ]
This visualization is often used to make it easier to understand what multiple
—in this case 2—dimensional arrays are. We now have 15 ‘slots’ and each
‘slot’ is identified by two numbers. num[1,1] is the first element in the array
and num[3,5] is the last. There are now two indices1 that need to be used
1
If you don’t know Latin you might have called them indexes.

42
 to reference each element and each must be within the boundaries defined
for its range. It is important to remember that the visualization above is
exactly that, just a visualization. The array could also have been visualized
as follows:
word: 1,1 1,2 1,3 1,4 1,5 2,1 2,2 2,3 2,4 2,5 3,1 3,2 3,3 3,4 3,5

number [ ][ ]
In fact this is the actual order that these elements are stored in memory
by just about every programming language except Fortran. It is known as
row-major order.
We are not restricted to two dimensions.
num : array [1..3][4..6][1..5][1..2][3..5] of number
This is a five dimensional array. We can store 3 × 3 × 5 × 2 × 3 = 270
elements in this array. Each element is referred to by 5 indices. Hence, num
[i,j,k,l,m] refers to one element in the array. Each of the indices i, j, k,
l, m must be within its defined range.
Arrays, combined with the looping structures we have already encoun-
tered, are very powerful tools to help us solve problems.

3.13 Functions and Procedures

We have already encountered block statements. When we have a block of
statements that perform a particular task it is often convenient to label this
block in a special way that allows us to refer to it again at a later time. For
example:
The following algorithm calculates and displays x to the power of y.
1 set answer = 1
2 for i ranges 1 to y do
3 set answer = answer * x
4 display answer
We can rewrite this as
1 procedure pow(x,y)
2 begin block
3 set answer = 1
4 for i ranges from 1 to y do
5 set answer = answer * x
6 display answer
7 end block

43
 We can now call this procedure from another algorithm
1 get num from user
2 get power from user
3 pow (num,power)
We can also write this as a function
1 function pow(x,y)
2 begin block
3 set answer = 1
4 for i ranges from 1 to y do
5 set answer = answer * x
6 return set pow = answer
7 end block
The difference between a procedure and function is that a procedure can
only act on data/variables while a function can return a value.
1 get num from user
2 get power from user
3 set result = pow(x,y)
4 display result

3.14 Recursion
A function or procedure is said to be recursive when it calls itself. It is
possible to rewrite the power function above as a recursive function.
1 function pow(x,y)
2 begin block
3 if y = 0 then return set pow = 1
4 else return set pow = pow(x,y-1) * x
5 end block
When writing a recursive function the first thing to do is to find the base
case.
For example: Write an algorithm to work out n!
1! = 1,
2! = 1 × 2,
3! = 1 × 2 × 3,
4! = 1 × 2 × 3 × 4,
etc.
We can rewrite this as
1! = 1,

44
 2! = 1! × 2,
3! = 2! × 3,
4! = 3! × 4,
etc.
In general n! = (n − 1)! × n
The base case is: when n = 1 then n! = 1. Thus
1 function factorial(n)
2 begin block
3 if n = 1 then return set factorial = 1
4 else return set factorial = factorial (n-1) x n
5 end block

Problem 3.1 Write a recursive algorithm that will add two num-
bers

Problem 3.2 Roots of a quadratic equation

Write an algorithm that will find and classify the roots of the quadratic
equation
ax2 + bx + c = 0
then x has the two values
√ √
b2 − 4ac b2 − 4ac
x = −b + or x = −b −
2a 2a
√
−4ac
Note that when a = 0 then x = −c/b, if b = 0 then x = 2a and if
c = 0 then x = −b/a.

Solution— Roots of a quadratic equation

√
We need to ensure that x exists, i.e. that the argument, of the square root
function x is positive.
Remember that the square root of something is always non negative, in
other words it is greater or equal to zero.2
Algorithm
2
Don’t let this definition of square root mislead you: The square root of a number
2
is that number that when it is squared gives the number. Since √ the (−10) is 100
it leads you to believe that the square root of 100 is −10 or 10. The 100 = 10, it is not
−10.

45
 1 get a from user
2 get b from user
3 get c from user
4
5 if a = 0 then
6 begin block
7 if c <> 0 then display x = -b/c
8 else
9 begin block
10 if b <> 0 then display x = 0
11 else display a=b=c=0
12 end block
13 end block
14 if a <> 0 then
15 begin block
16 if b^2 > -4ac then
17 begin block
18 display x = (-b + sqrt(b^2 - 4ac))/2a
19 display newline
20 display x = (-b - sqrt(b^2 - 4ac))/2a
21 display newline
22 end block
23 else display roots are not real
24 end block
——— 

Problem 3.3 Write a program that searches through an array se-

quentially and returns the index of the desired value and the num-
ber of lookups made.

Problem 3.4 Write a program that will find the sum of the first n
terms of the Taylor series for sin x
The Taylor-Maclaurin series for sin x which is given by
sin x = x − x3 /3! + x5 /5! − x7 /7! . . .
converges extremely rapidly. The error that is made using this estimation is
at most the size of the first term that has been left out such that the error
made when using only the terms shown above is at most |x9 /9!| which for
x = 1 is 0.0000027553, so taking the sum of the first four terms results in
six digits of accuracy. Since 32-bit floating point yields numbers with 7-digit
accuracy adding the next term, i.e., x9 /9! for x = 1, results in a value for
sin x with an error of at most 0.000000025048—that is seven accurate digits.

46
 Problem 3.5 Write a program that will convert a temperature
from Celsius to Fahrenheit and vice versa.

Problem 3.6 Write a program that generates n unique random

numbers.

Problem 3.7 Make a list of 10 different random numbers

Design an algorithm to construct an array of 10 unique random whole num-
bers.

Solution— Make a list of 10 different random numbers

1 numbers: array [1..10] of number

2
3 function insert (num, count)
4 begin block
5 set found = false
6 for i ranges from 1 to count do
7 if numbers[i] = num then set found = true
8 if found <> true then
9 begin block
10 set count = count + 1
11 set numbers[count] = num
12 end block
13 return set insert = count
14 end block

1 set count = 0
2 repeat
3 set x = random
4 count = insert(num, count)
5 until count = 10
——— 

Problem 3.8 Write a program that will allow the user to calculate
the sum, dot product or cross product of two vectors.3

3
See [Link] product and [Link]
wiki/Dot product.

47
 Problem 3.9 Create a list of 10 random integers in a tighter range
Now redesign your the algorithm to construct an array of 10 unique random
whole numbers in the range [A, B), for example, let the range be numbers
from the set {17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28}, represented by the
range [17, 29). Note that (1) the range excludes 29, and that there are enough
different numbers to enable the construction of at least 10 different numbers.

Problem 3.10 Create a list of 10 random integers

Now redesign your the algorithm to select 10% of the numbers from an array
of N unique random whole numbers in the range [A, B), for example, let the
range be numbers from the set {1, 2, 3, . . . , 100} denoted by the range [1, 101).
Note that (1) the range excludes 101, and that there are enough different
numbers to enable the construction of at least 10% of the numbers.

Problem 3.11 Water flow

Design an algorithm that will perform water flow rate calculations given that
Volume of water (kl) Cost (R/kl)
0 to 80.0 0.90
80.1 to 120.0 1.15
120.1 or more 1.25

Algorithm
1 get volume from user
2 if volume > 120 then set cost = (volume-120)x1.25 + 40x1.15 + 80x0.90
3 if volume > 80 and volume <=120 then set cost = (volume-80)x1.15 + 80x0.90
4 if volume <= 80 then set cost = volume x 0.90
5 display volume water costs cost

3.15 Dates and days

Calculations with dates and clocks are common applications of modular
arithmetic.

Problem 3.12 Given the year, calculate if it is a leap year or not.

If the year is divisible by 400 it is a leap year. If it is divisible by 100 and
not by 400 it is not a leap year. The years 1700, 1800 and 1900 are not leap
years, but 1600, and 2000 are leap years. Of the remaining years, every year
that is not divisible by 100 but is divisible by 4 is a leap year. For example
2008, 2012, 2016 are leap years.

48
 Solution— Calculating leap years
The leap year status is determined by some if statements.
1 def isLeapyear(year):
2 if year % 400 == 0:
3 return True
4 if year % 100 == 0:
5 return False
6 if year % 4 == 0:
7 return True
8 else:
9 return False
A shorter version is:
1 def isLeapyear(year):
2 return year % 400 == 0 or year % 4 == 0 and year % 100 != 0
——— 

Problem 3.13 Number of days in the months

Calculate the number of days in the months of a given the year.

Solution— Days in a month

1 daysinmonth = [30 + (month + month//8 ) % 2 for month in range(1, 13)]

2 \end{lslisting}
3 gives
4 \begin{lslisting}
5 [31, 30, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
All that still needs to be done is to adjust for February. What we do is to re-
place daysinmonth[1] by 28 + int(isLeapyear(year))]. The \lstinlineint(True)!
is 1 and int(False) is 0. The complete code for the days in the months fol-
lows.
1 def daysInmonth(year):
2 days = [30 + (month + month//8 ) % 2 for month in range(1, 13)]
3 days[1] = 28 + int(isLeapyear(year))
4 return days
——— 

Problem 3.14 Day of the week

A popular application of modulo arithmetic concerns calculating the day of
the week. Given the Gregorian calender date determine the day of the week.

49
 Solution— Day of the week
One start by counting the difference in days by calculating the number of
years, months and days from a base date for which you know the day of the
week, and then simply getting the day of the week using modulo 7. We call
this number the daydate.
It does not matter what the starting date is, if the days counted are
correct then calculate daydate for today and get today = daydate % 7. Since
we know what day of the week today is, henceforth today represents that
day of the week. Suppose today is a Tuesday, and today= 3, then 3 is a
Tuesday, 4 is a Wednesday, 5 is a Thursday, 6 is a Friday, 0 is a Saturday, 1
is a Sunday, 0 is a Monday. Now we calculate daydate, given the parameters
year, month, day
1 def daydate(year, month, day):
2 mdays = [30 + (m + m//8 ) % 2 for m in range(1, 13)]
3 mdays[1] = 28 + int(isLeapyear(year))
4 days = 1
5 mdays = [0]+mdays[:-1]
6
7 for m in range(month):
8 days += mdays[m]
9 mdays[m] = days
10
11 days = day + mdays[month-1]
12 years = year - 1600 # Our base date is 1601-01-01
13 days += years * 365
14 leapcenturies = ((years - 1) // 100 - 16)//4 + 1 # Add leap years
15 days += leapcenturies
16 weekdays = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
17 return weekdays[days % 7]
——— 

Problem 3.15 Calculate the Gregorian calendar date of Easter

Sunday.
The rules for determining the date of Easter or Passover are quite easy.
During 325 ACE in Nicaea the first ecumenical council of the catholic church
determined the date of Easter as the first Sunday after the full moon after
March 21—the spring equinox in the Northern hemisphere. The calculations
were based on the Julian calender and since 1582 and 1752 in the United
Kingdom and the United States of America on the Gregorian calendar. The
date of Easter varies between March 22 and April 25.

50
 Solution— The Gauss 1812 algorithm for calculating Easter
The algorithm of Gauss for calculating Easter
1
2 a = year %19
3 b = year % 4
4 c = year % 7
5 k = floor (year/100)
6 p = floor ((13 + 8k)/25)
7 q = floor (k/4)
8 M = (15 p + k q) % 30
9 N = (4 + k q) % 7
10 d = (19a + M) % 30
11 e = (2b + 4c + 6d + N) % 7
12 Gregorian Easter is 22 + d + e March or d + e 9 April
13 if d = 29 and e = 6, replace 26 April with 19 April
14 if d = 28, e = 6, and (11M + 11) % 30 < 19, replace 25 April with 18 April
15 For the Julian Easter in the Julian calendar M = 15 and N = 6 (k, p, and q are unnecessary)
——— 
Solution— Easter in a spreadsheet
The following spreadsheet formula calculates the date of Easter Sunday.
1 =ROUND(DATE(A1,4,1)/7 + MOD(19*MOD(A1,19) - 7, 30)*14%, 0)*7 - 6
——— 
Problem 3.16 Birthdays on the same day
Suppose that a room is occupied by some people. If there is only one person
in the room nobody will share his birthday so the probability q that there is
365
nobody to share his birthday is q1 = 365 = 1. When there are two people in
the room the probability that no two people share a birthday becomes q2 =
365×364
3652
= 0.9972602739.4 In general if there are n people in the room the
probability that no pair of people share a birthday becomes
Qn
−r+1
r=1 365
qn = .
365n
The problem is to discover how many people must be in the room for the
probability that there are two people that have a birthday on the same day
are in the room, i.e. find an n such that p = 1 − qn > 0.5.
Solution— Birthdays on the same day
Simply calculate the running fraction qn to discover at which n it becomes
less that a half. ——— 
4
Notice how we write the repeating decimal 0.99 72602739 72602739 . . ..

51
 Chapter 4

Problems with solutions in

python

4.1
Problem 4.1 S = N
P
r=1 r
Suppose that the integer N is given. Construct an algorithm to add all the
integers from 1 up to and including N , i.e. calculate the sum S,
N
X
S= r = 1 + 2 + . . . + N.
r=1

Solution— S = N
P
r=1 r
We first initialize a variable called S to zero and subsequently add the values
of r running from 1 to N one by one.
1 N = 10
2 S = 0
3 for r in range(1, N+1):
4 S += r
5 print ("Sum of integers from 1 to %d is %d" % (N, total))
A much tidier solution, more in the spirit of Python style, is:
1 N = 10; S = sum([r for r in range(1, N+1)])
The for r in range(1,N+1) generates each r which is then agglomerated
into a list by the surrounding brackets [. . . ]. The function sum is built in,
and yields the sum of the numbers in a list.

52
 If you were Carl-Fried Gauss, at the age of about ten years, you would
no doubt have noticed that the sums

1, 2, . . . , N − 1, N

+
N, N − 1, . . . , 2, 1
add up to
N + 1, N + 1, . . . , N + 1,
and that half of this is the required sum, and further you would have seen
that there are N of these N + 1 terms and you have given the answer in a
flash as
N × (N + 1)
.
2
Gauss would have programmed the requested result as
1 N = 10; S = N*(N+1)/2
Notice that despite the division by two, the result is a whole number.
——— 

Problem 4.2 Sum a list of integers

Suppose an array of numbers is given in the list L, e.g.
1 L = [17, 23, 29, 31, 37, 41, 47]
Sum the numbers in the list. You may assume that all the entries in the list
are integers.

Solution— Sum the numbers in a list

Suppose L is ready to use, then the simple Python answer is
1 S = sum(L)
——— 

Problem 4.3 Sum numbers stored in a file

On the other hand it is more likely that the numbers reside in some file,
“with each number on its own line”,1 and where the file is displayed by an
editor as:
1
In actual fact it means that the file has each integer terminated by the newline
character ‘\n’. So the list in our example is stored in a file as the single string
"17\n23\n29\n31\n37\n41\n47\n51\n53\n". Check that the file has altogether 27
characters. The file does not end with a character for the end of the file.

53
1 17
2 23
3 29
4 31
5 37
6 41
7 47

Solution— Sum numbers stored in a file

Let us now read the list of numbers and add them one by one.
1 f = open ("[Link]", ’r’)
2 L = [Link]()
3 [Link]()
4 S = 0
5 for r in L:
6 S += int(r)
7 print ("Sum of integers in the list is %d" % S)
The [Link]() bunches the substrings separated by newline characters
together into one string. This string still has to be converted into an integer
by the function int(r) before it can be summed. ——— 

Solution— Sum numbers stored in a file—Python style

A more Pythonic way to program this follows
1 print ("Sum of integers in the list is %d" %
2 sum([int(r) for r in open("[Link]",’r’).readlines()]) )
Since the number r is read in as a string from the file we turn it into an
integer using the built in int function so that it may be summed. ———


Problem 4.4 Sum numbers recursively

The next version of the N
P
r=1 r problem sets it in a new angle. Sum the
numbers 1 to N using a recursive function called by invoking add(N). A
recursive function is defined in terms of itself.

Solution— Sum numbers recursively

The idea is that when called as add(1), the function yields the sum 1. When
add(N) is called with a value of N exceeding 1, the result is defined as
the sum of that value of N added to the value of add(N-1). At each step
the function calls itself, but with an argument that is smaller by 1. These
contractions of the arguments yield what is known as a contraction mapping

54
 which eventually turns the argument into 1 which will then be added to 2,
. . . until finally N is added. So, first test if N is 1 and otherwise return
N + add(N − 1).
1 def add(N):
2 if N == 1:
3 return N
4 else:
5 return N + add(N-1)
6
7 print (add(10))
——— 

Problem 4.5 Add using inc and dec

Add the two positive integer arguments A and B with add(A,B) given the two
functions inc(N) which returns N + 1 and dec(N) which returns the value of
N − 1.

Solution— Add using inc and dec

The idea is to add B to A in the following manner. First check if B is zero,
in which case the value of A is returned. Otherwise return the value of the
add of A increased by 1, and B decreased by 1. In other words return the
value of add(inc(A), dec(B)). This continues until the second argument
becomes a zero when the value of the first argument is returned.
1 def add(A, B):
2 if B == 0:
3 return A
4 else:
5 return add(inc(A), dec(B))
6
7 print (add(3, 7))
Notice how the second argument is contracted until it becomes zero, at which
stage the first argument has been incremented by one enough times to have
reached A + B. ——— 

Problem 4.6 Multiply without ×-operator

Show how to multiply two positive integers numbers using addition only. The
function mult(A, B) must yield the value of A × B.

Solution— Multiply with addition

The idea is to add the value of A repeatedly until it has been added B times.

55
 The function returns zero when the value of B is zero, and returns the value
of A when B is one, otherwise the function returns mult(A, B - 1) + A. We
have multiplied without using addition. The Python code follows
1 def mult (A, B):
2 if B == 0:
3 return 0
4 elif B == 1:
5 return A
6 else:
7 return add(mult(A, dec(B)), A)
8
9 print (mult(3,7))
——— 

Problem 4.7 Recursive exponentiation

Show how to exponentiate a positive integer to a positive integer power using
multiplication only.

Solution— Recursive exponentiation

We will call the function power(A, B) and it will yield the value of AB
which is A × A × A . . . A, B times. The idea is to multiply the value of
A repeatedly until it has been multiplied B times. The function returns
1 when the value of B is zero, and returns the value of A when B is one,
otherwise the function returns power(A, B - 1) * A. We have raised A to
the power B using multiplication. The Python code follows
1 def power (A, B):
2 if B == 0:
3 return 1
4 elif B == 1:
5 return A
6 else:
7 return mult(power(A, dec(B)), A)
8

9 print (power(3,7))
——— 

These recursive solutions have practical bounds—they just do not work on

a computer with a small memory stack when the arguments get large. Our
power function will soon run out of memory on even the largest of machines.

Problem 4.8 More efficient exponentiation

Calculate power(A, B)= AB more efficiently.

56
 Solution— Using logarithms to calculate exponents
The simple answer is to use logarithms. Since log AB = B log A, we write
AB = exp(B log A) and get the result quite quickly. The snag is that the
accuracy of the log and exp is usually limited on computers to about 7
digits for single precision or to 18 digits for double precision—Python uses
double precision reals. This may be a problem when doing exponentiation
in cryptographic calculations where numbers with precisions of 256 or 512
binary digits are used.2 We give a version of this function
1 def power (A, B):
2 from math import log, exp
3 return exp(B*log(A))
4
5 print (power(3, 100))
Python has a built-in operator for exponentiation, so we could simply have
programmed
1 print (3**100)
Python also has a built-in function for exponentiation, so the following is
also a good way
1 print (pow(3,100))
——— 

Problem 4.9 An efficient method for exponentiation

What is an efficient way of doing multiple digit exponentiation in Python,
without the advantage of the built-in operator or function called pow(A, B)?

Solution— A fast method for exponentiation

There are several fast methods. We will show a fast method that uses an
interesting trick for exponentiating AB where both numbers are positive in-
tegers. We must calculate
AB = A × A × . . . × A, B times, requiring B − 1 multiplications. Sup-
pose we were asked to calculate A32 . This could have been done in less
2
Since dlog10 25 12/ log10 e = 107, 512 bits occupy 107 decimal digits.

57
 multiplications by
A2 = A × A,
A4 = A2 × A2 ,
A8 = A4 × A4 ,
A16 = A8 × A8 ,
A32 = A16 × A16 .

Instead of 31 multiplications 5 are sufficient. What do we do when B is not

a power of 2? If B = 33 the sequence of multiplications becomes
A2 = A × A,
A4 = A2 × A2 ,
A8 = A4 × A4 ,
A16 = A8 × A8 ,
A32 = A16 × A16 .
At some stage one more multiplication by A is needed, since A33 = A32 × A.
If B were 34 then one more multiplication by A2 is needed.
The table shows the number of multiplications needed for calculating some
powers of A
The power is calculated as follows: start with a product of 1. Set mul to A.
If B is odd then multiply product by mul and replace B by B//2. Square
and replace mul *= mul. Stop when B = 0.
1 def power (A, B):
2 mul = A
3 product = 1
4 while B != 0:
5 if B % 2 == 1:
6 product *= mul
7 mul *= mul
8 B //= 2
9 return product
10
11 print (power(3,7))
This is a very efficient algorithm but Python’s built-in pow(A, B) has a much
better performance. How does Python do it? ——— 
Problem 4.10 N ! recursively
Calculate the factorial function, N ! = 1 × 2 × 3 . . . × N using recursion.

58
Table 4.1: Number of multiplications needed for An . Note: Table has not
been checked for correctness.

Power of Number of
A multiplications How
A2 1 A×A
A3 2 A×A×A
A4 2 A2 × A2
A5 3 A2 × A2 × A
A6 3 A2 × A2 × A2
A7 2 A2 × A2 × A3
A8 3 A4 × A4
A9 4 A4 × A4 × A
A10 4 A4 × A4 × A2
A11 5 A4 × A4 × A3
A12 4 A4 × A4 × A4
A13 4 A4 × A4 × A5
..
. A4 × A4 × A7
A16 4 A8 × A8
A32 5 A16 × A16
A33 6 A32 × A
A34 6 A32 × A2

59
 Solution— N ! recursively
When the argument of factorial(N) is 1 or 0 return a 1 otherwise the
factorial of N is N * factorial(N-1).
1 def factorial (N):
2 if N < 2:
3 return 1
4 else:
5 return N * factorial(N-1)
6
7 print (factorial(6))
——— 

Problem 4.11 N ! iteratively

Calculate the factorial function, N ! = 1 × 2 × 3 . . . × N without using recur-
sion.

Solution— N ! iteratively
The non-recursive solution of N ! applies the definition directly. Build the
product that we have named product starting from 1. Multiply this by each
value r ∈ [2..N ] ≡ [2..N + 1).
1 def factorial (N):
2 product = 1
3 if N > 1:
4 for r in range(2, N+1):
5 product *= r
6 return product
7
8 print (factorial(6))
In Line 5 the “times and becomes” operator “product *= r” requires less
typing than “product = product * r”, so it is preferred. ——— 

Problem 4.12 Binomial coefficients

Calculate “choose r out of n objects”,
!
n n!
= nC r =
r r!(n − r)!

We will discuss binomial coefficients later in Section 2.1.

Solution— Binomial coefficients using factorials
A very slow way of calculating nr is by following the formula slavishly, i.e.

divide n! by r!(n − r)!.

60
 1 def factorial (n):
2 product = 1
3 if n > 1:
4 for r in range(2, n+1):
5 product *= r
6 return product
7
8 def binom(n, r):
9 return factorial(n)/(factorial(r)*factorial(n-r))
10
11 print (binom(52,4))
——— 

Solution— Binomial coefficients using some mathematics

Since n! = (n × n − 1 × . . . × n − r + 1) × (n − r)!, first dividing n! by (n − r)!
yields

nr = n × n − 1 × . . . n − r + 1

The symbol nr is called a falling factorial and is an abbreviation for n × n −

1 × . . . n − r + 1. What remains, is to calculate nr /r!. Noticing that the one
of the numbers in the product n × n − 1 is divisible by 2 and next seeing
that one of the factors in n × n − 1 × n − 2 must be divisible by 3 leads us to
the idea of calculating the binomial coefficient as an accumulating product.
First put binom = 1 and then letting n decrease by 1 in each iteration, and r
starting at 0 increase by 1 in each iteration accumulate the binomial product
as
1 binom = n
2 for r in range(2, R+1):
3 n -= 1
4 binom = binom * n // r
This method uses r − 1 multiplications and divisions and the product never
gets bigger than the result. The method in Solution 4.1 gets the factorials
with close to 2n multiplications and one division. Some simple arithmetic
provides a method that works faster for any n > r.
1 def binom(n, r):
2 binom = n
3 for k in range (2, r+1):
4 n -= 1
5 binom = binom * n // k

61
 6
7 return binom
——— 

Another very interesting solution based solely on additions is presented in

Solution2.1
Problem 4.13 Counting digits in numbers
Count the total number digits of each factorial from 1 to 100000.

The ultimate Pythonic way to write the factorial function is to use a gen-
erator. The generator yields values one by one, discarding the previous
values.

Solution— N ! with a generator

Our generator for factorials is a simple variation of the iterative version of
the function. When control arrives at the yield command the calculation
is suspended and the environment is saved so that it can be restored on
reentry.
1 def factorials (N):
2 product = 1
3 num = 1
4 while num <= N:
5 yield product
6 num += 1
7 product *= num
8
9 n = 1000
10 count = 0
11 for f in factorials(n):
12 count += len(str(f))
13
14 print (count)
——— 

Many problems lend themselves to recursive solutions. These recursive

solutions often lend themselves to be readily turned into iterative solutions,
e.g. factorials, Fibonacci numbers and sorting. Let us consider those to-
gether with their more practical iterative solutions.

Problem 4.14 Fibonacci numbers

The sequence of numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . are called the Fibonacci

62
 numbers. Starting with 0 and 1 next number in the sequence is the sum of
the previous two.

Solution— Fibonacci numbers recursively

Fibonacci numbers are defined recursively as F0 = 0, F1 = 1, Fn = Fn−1 +
Fn−2 so the recursive code is pretty easy.
1 def F (N):
2 if N == 0:
3 return 0
4 elif N == 1:
5 return 1
6 else:
7 return F(N-1) + F(N-2)
8
9 print (F(50))
——— 

Problem 4.15 Fibonacci numbers

There is no need to implement Fibonacci numbers recursively and the recur-
sive code runs excessively slowly. Create an iterative solution.

Solution— Fibonacci numbers iteratively

If N is zero return a zero; if N is 1 return a 1, and otherwise use two
variables to hold the oldest and most recent values and return their sum
after updating them.
1 def F (N):
2 if N <= 0:
3 return 0
4 n = 0
5 ancient = 0
6 old = 1
7 while n < N:
8 ancient, old = old, ancient + old
9 n += 1
10 return ancient
11
12 from time import time
13 for n in range (2, 101):
14 start = time()
15 print("F(%d) = %d, took %.5f s." % (n, F(n), time() - start))
This code runs in linear time, much faster than the recursive solution that
runs in exponential time. ——— 

63
 Problem 4.16 A generator for Fibonacci numbers
Program a generator version of Fibonacci based on the iterative solution.

Solution— A generator for Fibonacci numbers

The trick is to figure out where to put the yield command.
1 def F (N):
2 n = 0
3 ancient = 0
4 old = 1
5 while n <= N:
6 yield ancient
7 ancient, old = old, ancient + old
8 n += 1
9 return ancient
10
11 from time import time
12 for n in range (2, 101):
13 start = time()
14 print("F(%d) = %d, took %.5f s." % (n, F(n), time() - start))
——— 

Problem 4.17 Sorting a list

Construct a program to sort a list L of uniform—all the elements are num-
bers or all of them are strings—items from smallest to largest. The sorting
algorithm works as follows. Remove the first element of the list and then
concatenate the collection of the elements smaller than it, the selected ele-
ment, and the collection of all those greater or equal to it.

Solution— Sorting a list

1 def sort(L):
2 if not L:
3 return L
4 it, rest = L[0], L[1:]
5 smaller = [item for item in rest if item < it]
6 greaterEqual = [item for item in rest if item >= it]
7 return sort(smaller) + [it] + sort(greaterEqual)
8
9 from random import random
10

11 N = 100
12 L = [int(random()*N) for x in range(N)]
13 print (sort(L))

64
 ——— 

Recursive solutions are sometimes easier to conceive. An example whose

iterative solution is far from obvious is the towers of Hanoi problem. The
recursive solution is easy.

Problem 4.18 The towers of Hanoi

Program the towers of Hanoi problem recursively. Three pins are presented;
one has a stack of disks piled on top of one another from the smallest on top
to the largest at the bottom. The other two pins are empty. The three pins
are called ‘from’, ‘help’ and ‘to’. The pins are stacked on the from tower.
The problem is to move the disks one-by-one such that a larger disk never
lies on top of a smaller disk from tower to tower until all the disks are in
the correct order on the to tower.

Solution— The towers of Hanoi

Assume that there are N disks to be manipulated. The idea of the solution
is very simple. How can the bottom disk be moved? It can only be moved if
nothing lies on top of it and the pin you are moving it to is clear. How can
this be brought about? Obviously N − 1 pins need to be moved to the help
disk. Once these disks are out of the way the largest disk—lying on the from
pin—can be moved to the to pin. What remains to be done? The N − 1
disks on the help pin must be moved onto the biggest disk now lying on the
to pin. In all the recursive procedures above the problem was reduced to
doing something for one item, and then repeating the procedure for N − 1
items. So we have solved the towers of Hanoi problem. The next step is
the most difficult. What parameters will the procedure need? The value N
seems to be essential. Each separate tower needs its own parameter since
our procedure must know at each step from where, to where a disk must be
moved and which tower remains.3 We will call the procedure hanoi and give
it four parameters.
1 def hanoi (N, from, help, to):
2 if N == 1:
3 print ("move disk from %s to %s" % (from, to))
4 else:
5 hanoi (N-1, from, to, help)
6 print ("move disk from %s to %s" % (from, to))
7 hanoi (N-1, help, from, to)
3
Perhaps it is possible to can get away with naming only the from and to towers in
the list of parameters.

65
8
9 hanoi (3, "From", "Help", "To")
——— 

Polynomials are interesting for many reasons. They form the basis of our
number system. They may be used to approximate functions as accurately
as needed. Polynomials are useful because they are easy to differentiate and
integrate. They play an important role in algebra.

Problem 4.19 Evaluating a polynomial

A univariate polynomial of degree n in x may be written as

Pn (x) = a0 + a1 x + a2 x2 + . . . + an−1 xn−1 + an xn .

Univariate polynomials are usually referred to simply as polynomials. By

writing the same terms the other way round

Pn (x) = an xn + an−1 xn−1 + . . . + a2 x2 + a1 x + a0

we get a different view of the same polynomial and in this form putting
the variable x = 10 and restricting the coefficients to the decimal digits
di ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, the polynomial

Pn (10) = dn 10n + dn−1 10n−1 + . . . + d2 102 + d1 10 + d0

represents the decimal number written as

dn dn−1 . . . d2 d1 d0

Solution— Evaluating a polynomial

Suppose the coefficients are stored in an array a. Write code for evaluating
the polynomial Pn (x), called by P(n, a, x). The value of n may be deter-
mined by inside the function using n = len(a), but the meaning of the call
is clearer if the n is passed as an argument. It may be coded as follows.
1 def P(n, a, x):
2 pol = a[0]
3 xpowern = 1
4 for i in range(1, n+1):
5 xpowern *= x
6 pol = pol + a[i]*xpowern
7 return pol
8

66
 9 from time import time
10 a = [1, 4, 6, 4, 1]
11 n = 4
12 for x in range(0, 11):
13 start = time()
14 print("P%d(%f) = %f, took %.5f s." % (n, x, P(n,a,x), time() - start))
Another way of writing the polynomial is to number the coefficients differ-
ently as

Pn (x) = a0 xn + a1 xn−1 + . . . + an−1 x2 + an−1 x + an .

Rewrite the code corresponding to the array written with the coefficient of
the xn first. ——— 

Solution— Faster evaluation of a polynomial

1 def Pn(n, a, x):

2 pol = 0
3 xpowern = 1
4 for i in range(n, -1, -1):
5 pol = pol + a[i]*xpowern
6 xpowern *= x
7 return pol
8
9 from time import time
10 a = [1, 4, 6, 4, 1]
11 n = 4
12 for x in range(0, 11):
13 start = time()
14 print("P%d(%f) = %f, took %.5f s." % (n, x, Pn(n,a,x), time() - start))
——— 

These obvious first attempts both use 2n multiplications. Rewrite the

code to use n multiplications.

Solution— Horner’s rule for polynomial evaluation

The insight is to start at the back and do only one multiplication per itera-
tion. The idea is called Horner’s rule and uses only n multiplications for a
polynomial of degree n.
1 def P(n, a, x):
2 pol = a[n]
3 for k in range(n-1, -1, -1):

67
 4 pol = a[k] + pol*x
5 return pol
6
7 from time import time
8 a = [1, 4, 6, 4, 1]
9 n = 4
10 for x in range(0, 11):
11 start = time()
12 print("P%d(%f) = %f, took %.5f s." % (n, x, P(n,a,x), time() - start))
——— 

Problem 4.20 Representation of numbers by polynomials

A number in base ten, e.g. 1234567 may be represented as the array digits = [1, 2, 3, 4, 5, 6, 7].
Use the polynomial algorithm to find the value of the number.

Solution— Representation of numbers by polynomials

1 def P(n, a, x):

2 pol = a[n]
3 for k in range(n-1, -1, -1):
4 pol = a[k] + pol*x
5 return pol
6
7 from time import time
8 digits = [1, 2, 3, 4, 5, 6, 7]
9 n = 6
10 for x in range(0, 11):
11 start = time()
12 [Link]()
13 print("P%d(%f) = %f, took %.5f s." % (n, x, P(n,digits,x), time() - start))
——— 

Problem 4.21 Addition of polynomials

Given two polynomials, Pn (x) and Qn (x) write a program to add them, i.e.
write code to produce

Rn (x) = Pn (x) + Qn (x).

Problem 4.22 Subtraction of polynomials

Given two polynomials, Pn (x) and Qn (x) write a programme to subtract
them, i.e. write code to produce

Rn (x) = Pn (x) − Qn (x).

68
Problem 4.23 Multiplication of polynomials
Given two polynomials, Pn (x) and Qn (x) write a programme to multiply
them. i.e. write code to produce
Rn (x) = Pn (x) × Qn (x).
Problem 4.24 Division of polynomials
Given two polynomials, Pn (x) and Qn (x) write a programme to divide them.
i.e. write code to produce
Rn (x) = Pn (x)/Qn (x).
Problem 4.25 Polynomials representing numbers
The polynomial over the variable b with coefficients conveniently called digits
di ∈ [0..b) = {0, 1, ..., b − 1}, may be used to represent any number in base b
Pn (b) = dn bn + dn−1 bn−1 + . . . + d2 b2 + d1 b + d0
Write code to convert a number Pn (b) in base b to a number Qn (r) in base
r with digits called si ∈ [0..c) = {0, 1, . . . , c − 1}. with the same value. The
problem is to convert the polynomial P
P = dn bn + dn−1 bn−1 + . . . + d2 b2 + d1 b + d0
into the polynomial Q
Q = sn rn + sn−1 rn−1 + . . . + s2 r2 + s1 r + s0 ,
so that P = Q.
Solution— Polynomials representing numbers
This turns out to be easy. We are given the polynomial P and its coefficients
and are asked to extract the “digits”, si from it. Since P = Q, we can do
arithmetic on Q as the proxy of P , so, first copy Q into P . Consider Q,
Q = sn rn + sn−1 rn−1 + . . . + s2 r2 + s1 r + s0 ,
All the terms of Q excepting s0 are divisible by r, so it is clear that we can
calculate s0 by
s0 = Q mod r
and then subtract—the digit—s0 from Q, divide the result with r and replace
Q with the result
Q − s[0]
Q= = sn rn−1 + sn−1 rn−2 + . . . + s2 r + s1 .
r
In Python we do this with the two lines

69
1 s[0] = Q % r
2 Q //= r
The steps start repeating. At this stage, all the terms of Q excepting s1 are
divisible by r, so it is calculated

s1 = Q mod r

and then subtract the digit s1 from Q, divide the result with r and replace
Q with that

Q − s[1]
Q= = sn rn−2 + sn−1 rn−3 + . . . + s3 r + s2 .
r
In Python we do this with the two lines
1 s[1] = Q % r
2 Q //= r
The process continues while Q 6= 0. The code becomes
1 s = [0]*(n + 1)
2 i = 0
3 while Q != 0:
4 s[i] = Q % r
5 Q //= r
6 i += 1
——— 

70
Chapter 5

Some problems from various

sources

Problem 5.1 Flatten a binary search tree rightwise

You are given an unbalanced binary search tree. Flatten it into a binary
search tree with only right children.

Problem 5.2 Flatten a binary search tree leftwise

You are given an unbalanced binary search tree. Flatten it into a binary
search tree with only left children.

Problem 5.3 Balance a binary search tree

Balance a binary search tree by rightwise flattening and then turn this into
a balanced tree.

Problem 5.4 Find the sum of the numeric keys in a path from the
root to a given node in a binary search tree

Problem 5.5 Find an item in a sorted list that has been cut once
Suppose you have a sorted list of length n that has been rotated by k places.

Problem 5.6 Find kth non-repeated char

Problem 5.7 Find nth largest number in a stream of numbers

Problem 5.8 Reverse a linked list

71
Problem 5.9 Reverse a doubly-linked list

Problem 5.10 Find Pythagorean triples

Find the sum of all Pythagorean integer triples a, b, c with c2 = a2 + b2 where
0 < a ≤ N , 0 < b ≤ N and 0 < c ≤ N and N ≤ 1000.

Problem 5.11 Given the time give the angle in radians between
the short hand and the long hand of an analogue clock

Problem 5.12 Program Snakes and ladders

Problem 5.13 Merge three sorted lists

Problem 5.14 Merge n sorted lists

Problem 5.15 Find nearest common ancestor of two nodes in a

binary search tree

Problem 5.16 Find common numbers in two sets

Given a set of 100 integers and another set of 1000000 integers, find their
intersection.

Problem 5.17 Make a new set from the numbers in two sets
Given a set of A of 100 integers and another set of B of 1000000 integers,
form a new set that contains all the numbers in A ∪ B.

Problem 5.18 Find the numbers in two sets that are not common
to both sets
Given a set of 100 integers and another set of 1000000 integers. This set is
called the symmetric difference.

Problem 5.19 Find the number of days between two dates

Problem 5.20 Is a given undirected graph a tree or not?

72
 Problem 5.21 Is a given undirected graph a tree or not?

Problem 5.22 Find common data from two very large files that do
not fit into memory simultaneously

Problem 5.23 Print an n-ary tree in breadth first order

Problem 5.24 Checking if two binary search trees are similar or

not

Problem 5.25 Use command line code to get the common data
from three files

1 cat f1 f2 sort uniq -d > tmpfile;

2 cat f3 tmpfile sort uniq -d

Problem 5.26 You have a jar with balls uniquely numbered from
1 to 100. You have removed 99 of these balls. What is the number
on the remaining ball?

Problem 5.27 Find the square root of a given number A.

The ancient Babylonians had a fast formula for calculating the square root
of any number. This algorithm was described by Heron of Alexandria in his
book called Metrica near the dawn of the √ Christian era about 60 ACE.
Apply Heron’s formula to calculate A:
“(1) Start with a guess of the root r.
(2) If r2 is close enough to A, then use r as the square root.
(3) Otherwise re-estimate r using the average of r and A/r, i.e.,
r + A/r
r←
2
.
(4) Repeat from step (2).”

73
 √
In books on numerical mathematics Heron’s formula to calculate A is
often ascribed to Newton and is described using the series {r0 , r1 , r2 , . . .}
that converges to the root.
Initialize r0 = 1, and
iterate rn+1 = (rn + A/rn )/2
2
until |rn+1 −A| < ε where ε is an arbitrary small positive number. Note that
careful application of this formula in a program does not require subscripts.

Problem 5.28

Problem 5.29 Find the first repeated element in an array.

Problem 5.30 Find the first repeated integer in an array of inte-

gers

Problem 5.31 Find the all the repeated elements in an array.

Problem 5.32 Find the first repeated character in a string

Problem 5.33 Find the most repeated Object in an array of Ob-

jects

Problem 5.34 Reverse the characters of a string iteratively and

recursively

Problem 5.35 Find the largest and and second largest elements in
a list of integers.

Problem 5.36 Swap the largest and smallest elements in a list of

integers.

Problem 5.37 Reverse the words of a sentence.

74
Problem 5.38 Convert decimal number to Roman number.

Problem 5.39 Remove the n-th element from a linked list.

Problem 5.40 Remove the last element from a linked list.

Problem 5.41 Remove the first element from a linked list.

Problem 5.42 Find the most repeated Object in an array of Ob-

jects

Problem 5.43 Reverse the characters of a string iteratively and

recursively

Problem 5.44 Implement a queue using one or more stacks

Problem 5.45 Without destroying the queue find if element is in

the queue

Problem 5.46 Check if two binary trees mirror one another ex-
actly

75
Chapter 6

Linux command line

interface problems

Problem 6.1 Find telephone numbers in all .html files

Solution— Find telephone numbers in all .html files

The find below finds numbers such as -959-3004, 0-959-3004, 02-959-3004,
021-959-3004, 2721-959-3004, or 54321-959-3004,
find -name *.html | xargs grep "[0-9]\{0,3\}[-][0-9]\{3\}[-][0-9]\{4\}"

The regular expression ‘[0-9]’ means the same as ‘[0123456789]’ and it

matches any single digit, whereas the regular expression ‘[-]’ matches ex-
actly one ‘-’ character. The trailing ‘\{1,5\}’ in ‘[a-z]\{1,5\}’ matchs all
lowercase letter strings or words of length one to five. The pattern ‘[^+]’
matches any single character other than ‘+’. Note that some grep programs
do not require the ‘{’ and ‘}’ to be escaped with a ‘\’ character.
Use man find, man xargs and man grep for more information about
these commands.
Explain why 54321-959-3004 and 987654321-959-3004 are also matched.
——— 

76
Bibliography

Thomas H Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction

to Algorithms. MIT Press, 1990.

Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford

Stein. Introduction to Algorithms. MIT Press and McGraw-Hill, 3rd ed.
edition, 2009.

77
Appendix A

The Standard International

(SI) symbols for numbers

Prefix Symbol 1000m 10n Decimal Short scale Long scale Since
yotta Y 10008 1024 1000000000000000000000000 Septillion Quadrillion 1991
zetta Z 10007 1021 1000000000000000000000 Sextillion Trilliard 1991
exa E 10006 1018 1000000000000000000 Quintillion Trillion 1975
peta P 10005 1015 1000000000000000 Quadrillion Billiard 1975
tera T 10004 1012 1000000000000 Trillion Billion 1960
giga G 10003 109 1000000000 Billion Milliard 1960
mega M 10002 106 1000000 Million 1960
kilo k 10001 103 1000 Thousand 1795
hecto h 10002/3 102 100 Hundred 1795
deca da 10001/3 101 10 Ten 1795
10000 100 1 One —
deci d 1000−1/3 10−1 0.1 Tenth 1795
centi c 1000−2/3 10−2 0.01 Hundredth 1795
milli m 1000−1 10−3 0.001 Thousandth 1795
micro 1000−2 10−6 0.000001 Millionth 1960
nano n 1000−3 10−9 0.000000001 Billionth Milliardth 1960
pico p 1000−4 10−12 0.000000000001 Trillionth Billionth 1960
femto f 1000−5 10−15 0.000000000000001 Quadrillionth Billiardth 1964
atto a 1000−6 10−18 0.000000000000000001 Quintillionth Trillionth 1964
zepto z 1000−7 10−21 0.000000000000000000001 Sextillionth Trilliardth 1991
yocto y 1000−8 10−24 0.000000000000000000000001 Septillionth Quadrillionth 1991

78
Appendix B

Using simplegui

We introduce the simple interface in Python called simplegui

79
Contents

1 Digits and numbers 1

2 Binomial coefficients and Pascal’s triangle 27

2.1 Binomial coefficients . . . . . . . . . . . . . . . . . . . . . . . 27

3 UWC Computer Science I: Problem Solving 35

3.1 Academic Responsibility . . . . . . . . . . . . . . . . . . . . . 35
3.2 Course Objectives . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 What does a Computer Scientist do? . . . . . . . . . . . . . . 36
3.4 What is problem solving? . . . . . . . . . . . . . . . . . . . . 36
3.5 What are Algorithms? . . . . . . . . . . . . . . . . . . . . . . 36
3.6 Syntax, Semantics and Logic . . . . . . . . . . . . . . . . . . 36
3.7 Stepwise/Top-down Refinement of Algorithms . . . . . . . . . 37
3.8 Sequential Algorithms . . . . . . . . . . . . . . . . . . . . . . 38
3.9 Trace Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.10 Conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.11 Looping Constructs . . . . . . . . . . . . . . . . . . . . . . . . 39
3.11.1 The for-loop . . . . . . . . . . . . . . . . . . . . . . . 39
3.11.2 The while-loop . . . . . . . . . . . . . . . . . . . . . . 40
3.11.3 The repeat-loop . . . . . . . . . . . . . . . . . . . . . 40
3.12 Statement Blocks . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.13 Functions and Procedures . . . . . . . . . . . . . . . . . . . . 43
3.14 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.15 Dates and days . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4 Problems with solutions in python 52

4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5 Some problems from various sources 71

80
6 Linux command line interface problems 76

A The Standard International (SI) symbols for numbers 78

B Using simplegui 79

81