Lab 3: branching and iteration
In this lab, we will start working with two cornerstone programming constructs, namely branching and iteration. These belong to the so-called control flow instructions, as they let the programmer to alter the otherwise sequential flow of instructions (i.e., one instruction after the other). Branching and iteration are here to stay. Thus, it is important that this week you grasp their semantics while starting to develop your problem solving skills with them.
In order to help you out to develop and/or check your understanding of programs with branches and loops, we highly encourage you to use the online Python tutor along this lab (and beyond this lab). We consider the online Python tutor to be an splendid tool to satisfy this goal. Click here for more details.
As we see more and more Python programming constructs, it becomes easier to forget them. To mitigate this, we highly encourage you to keep in mind the Python cheat sheet available here, and ideally that you print it on paper and come to the labs with it all the way through.
Like lab 2, we expect that there will likely be more material in this lab than you can finish during the lab time. If you do not have time to finish all exercises, you can continue working on them later. You can do this at home on your own computer, or in the CSIT lab computers during the drop-in sessions. You may also use the InfoCommons computers (available in the university libraries and other teaching spaces).
Codebench#
Exercises 1, 4 and 5 below are available at CodeBench under the Lab3 exercise set. Make sure you SUBMIT your programs for these programming problems before you close CodeBench. Ask your tutor for help if you struggle with CodeBench.
Warm-up exercise: Truth values#
A truth value, also known as boolean or logical value, is a value that has only two possible states:
True or False. You get boolean values as a result of, e.g, using
comparison operators, such as ==, or <. Both True and False
are reserved words in Python, and they are different to strings such as
"True" and "False".
Start up a shell, and try evaluating following expressions. Make sure you understand the results you obtain:
In [1]: 5 > 4
Out [1]: ...
In [2]: type(5 > 4)
Out [2]: ...
In [3]: "aab" > "ab"
Out [3]: ...
In [4]: type("aab" > "ab")
Out [4]: ...
In [5]: type("False")
Out [5]: ...
In [6]: "False"==False
Out [6]: ...
Note that comparison operators among strings, such as, e.g.,
"aab" > "ab", are evaluated by comparing, from left-to-right,
character by character, the ASCII
codes (integer numbers) of each character.
(For completeness,, you can see
here the
correspondence among characters and ASCII codes.) In any case, if you are
comparing strings with only letters, it is easy, as comparison operators
follow alphabetic order. Upper-case letters are assumed to be before than the
lower-case ones, such that, e.g., "Z"<"a", evaluates to True, and "z"<"A" to False.
On the other hand, you can combine boolean values with boolean operators and, or and not.
In [7]: 5 > 4 and 4 > 9
Out [7]: ...
In [8]: not 4 > 9
Out [8]: ...
In [9]: True or False
Out [9]: ...
In [10]: True or True
Out [10]: ...
In [11]: type(True or False)
Out [11]: ...
Note: Python allows you to write some compound boolean expressions without a boolean operator:
10 < x <= 20
means the same as
10 < x and x <= 20
The comparisons can be both strict, both non-strict, or a mixture of strict and non-strict.
From here on, you should switch to writing your code in a file rather than typing it into the shell.
Exercise 1: programs with conditional branching [Available at CodeBench]#
Exercise 1(a): fixing a wrong function#
One can use boolean values to make decisions in if statements - this is
called conditional branching. The lecture slides contain the following function for determining
the grade associated with a final mark:
def print_grade(mark):
if mark >= 80:
print("High Distinction")
if mark >= 70:
print("Distinction")
if mark >= 60:
print("Credit")
if mark >= 50:
print("Pass")
else:
print("Fail")
Copy the function to a file so that you can run it, and test it with a
range of different values (keeping in mind that the mark should be a
number between 0 and 100) so that you see all the possible messages
printed on screen. If you struggle to understand why the
messages that are printed are actually printed, this is a good opportunity to use
the online Python tutor.
Click here
for instructions.
As we saw in the lecture, this function does not perform as intended,
and we saw one way to fix it, namely by replacing each test with compound
test expressions (for example mark < 80 and mark >= 70). Let us try
to solve the problem following a different approach.
Rewrite the function so that it works correctly using only simple
comparison expressions, if and else statements. By simple
comparison expression we mean a logical expression which does not
have boolean operators such as and or or.
Note that during the lecture last week we also saw a solution to this
exercise using elif, and only simple comparison expressions
(no boolean operators).
Exercise 1(b): computing the median of three numbers#
The median of three numbers, a, b and c, is the one that ends up in the middle when the numbers are sorted in increasing order. For example, the median of -2, 7 and 9 is 7, and the median of 7, 9 and -2 is also 7.
Write a function median with three parameters a b and c, which
returns the median of its three arguments. (Of course, the function only
works if all three arguments are numbers… or does it? What happens if
you call it with three strings? What happens if you call it with a mix
of numbers and strings?)
Note that there are many different ways to solve this problem.
Testing your function. You can test the function with sets of
small numbers (like 1,2,3); if it works for small numbers, it should
work just as well for large numbers. Note that the median of three
numbers is the same no matter in which order they are given to the
function; that is, median(1,2,3), median(1,3,2), median(2,1,3),
median(2,3,1), median(3,1,2) and median(3,2,1) should all
return the same result. What happens if you call your function with
two or three copies of the same value? (such as median(2,1,2) or
median(1,1,1)).
Exercise 2: using iteration to print a formatted table with formula evaluations#
The following exercise requires you to use a while loop.
When writing this kind of loops, chances are high that you end up in an infinite
loop until you are able to find a working solution. In the event of
an infinite loop, you should know how to interrupt the Python
interpreter. One typically interrupts the Python shell hitting the Ctrl+C keyboard combination
(which stands for press the C key while holding down the Ctrl key).
If you are running on a VSCode interactive window,
you can click on the Interrupt option at the top of the window.
For Spyder, this can be achieved by clicking on the little red square button
at top right of console pane (or Ctrl+C)
The following polynomial of degree 2 (also known as quadratic polynomial) in one variable \(t\):
\[y(t)=100t-\frac{1}{2}9.8t^2\]describes the vertical motion of a ball thrown up from the ground level at an initial velocity of 100 \(\frac{m}{s}\) (meters per second). This polynomial is used as follows: if we want to know the vertical position of the ball, say, after 0.2 seconds, then we just evaluate \(y(t)\) at \(t=0.2\) seconds, that is, substitute \(t\) by 0.2 in the polynomial defined above.
The goal of this exercise is to write a function, print_ball_motion_table, with no parameters,
that prints on screen a nicely formatted table of several
evaluations of \(y(t)\) at different values of \(t\) in an interval \([0,T]\),
where \(T\) is given.
In order to generate the different values of \(t\) at which we want to evaluate \(y(t)\), we split the interval \([0,T]\) into \(N\) equal-sized parts. The size of each part is thus \(\Delta t = \frac{T}{N}\). This will give us \(N+1\) different values of \(t\). An example of this partition is shown below with \(T=20\) and \(N=4\) (time interval \([0,20]\) split into \(4\) parts).
You may want to start this exercise
from the following incomplete code, and then fill-in the gaps (i.e.,
replace the three underscores ___ by correct code):
def print_ball_motion_table():
"""
Prints a table of the position, at different times,
of a ball thrown vertically from the ground level at
a velocity of 100 m/s. The interval [0,T] is split
into N parts, resulting into N+1 time points at which to
calculate and show the position of the ball, that is, N+1
rows in the table.
"""
T=20
N=4
t=___ # Initialize current time t to 0.0 (s)
i=___ # Initialize loop counter to zero
dt=___ # Compute Delta_t (s)
while ___: # Loop condition (compare integers!)
y=___ # Compute y(t)
print(f"{t:5.2f} {y:7.2f}")
___ # Increment loop counter i (by how much?)
___ # Increment current time t (by how much?)
Some comments in regards to this code:
- The
print(f"{t:5.2f} {y:7.2f}")print statement, withtandybeing variables, prints two columns with 5 and 7 characters wide each, formatted in decimal notation using 2 decimal digits, and separated by a single space. - It is best, to avoid trouble with rounding errors, that you write your loop condition such that it compares integer numbers instead of floating point numbers.
- Visualize the execution of your function with the online Python tutor.
For reference, the output of the function should be:
0.00 0.00
5.00 377.50
10.00 510.00
15.00 397.50
20.00 40.00
Modify your function definition statement such that T and N are function parameters
instead of local variables with hard-coded (fixed) values. Test the function with different values
of T and N. Did you write a function to evaluate \(y(t)\)? (this would allow to re-use the
formula in another context)
Exercise 3: robot programming problems#
For some of the problems in this section, you will need to use
a new feature of the robot, namely the robot’s box sensor.
The command robot.sense_color() returns the colour of the box
in front of the sensor, as a string (a value of type str). It
will return an empty string ('') if there is no box in front
of the sensor. For more about how the box sensor works, see
last week’s lecture on branching.
As usual, if you did not already, download a copy of the robot.py module and save it in your working directory for this lab. Make sure that you can import the module: the Python interpreter will look for it in the current working directory.
Remember that you must start by initialising the simulation:
robot.init()
(If you need more of a reminder about how to run and program the robot, revisit Lab 1.)
Exercise 3(a): stacking an arbitrary number of boxes#
In an early lecture, we introduced the problem of stacking boxes lined up on the shelf into a tower. Even though we could define functions that encapsulate the main steps of picking up, stacking and so on, we still needed to write different programs, with a different number of repetitions, for different numbers of boxes. (For example, here are programs for stacking 3 boxes and stacking 5 boxes.)
Write a single function, make_tower, that stacks any
number of boxes that stand in a line on the shelf into a single
tower.
To create problems with different sizes, you pass extra arguments
to the init function, for example:
robot.init(width = 7, boxes = "flat")
The “width” is the number of spaces on the table; because the initial setup leaves one empty space between each pair of boxes (otherwise the robot would not be able to pick them up), you need a width of 2*n - 1 to make a problem with n boxes (i.e., width 5 gives you 3 boxes; width 7 gives you 4 boxes; and so on).
There are two important questions to consider in the designing an algorithm for this problem:
What is the sequence of commands that is repeated for every box added to the stack?
How do you determine when to stop? The robot’s sensor can only detect the presence of boxes; how can you tell if it has reached the end of the table?
Exercise 3(b): finding boxes of a particular colour in a box stack#
In last week’s lecture, we developed a function
find_box that returned True or False depending
on whether there is a box of a given colour in the box
stack or not.
Following the same idea, write a function that finds the position of a box with a given colour in a stack. That is, your function should look like this:
def find_box_position(colour):
...
and should return the position (height above the shelf) where a
box of that colour is. The bottom-most box is in position 1, the
one immediately on top of it in position 2, and so on towards the
top of the stack. If there is no box of the specified colour,
the function should return a distinct value, such as -1. (We
choose -1 because it can never be the position in a stack, so we
can distinguish it from the case where a box has been found.)
You can use either a recursive or an iterative method (or why not try both). Note that there are two cases: either the box is found, or the robot has searched all the way through the stack.
To test your function, you need to set up simulations with a
tall stack of different colours. You can do this by passing
additional arguments to the init function, for example:
init(height = 5, boxes = [["black", "blue", "white", "red"]])
The height argument specifies the maximum height that the lift can go.
Exercise 4: The square root algorithm [Available at CodeBench]#
The Babylonian algorithm is a method of computing square roots of numbers. The method was recorded as far back as the 1st century, though the name suggests it is older than that. The algorithm can be derived as a special case of the Newton-Raphson method for solving an equation of the form \(f(x) = 0\).
The Babylonian algorithm works as follows: We want to compute the square root of some number \(a\). First, we take a guess: pick some number \(x\). Then check how good is our guess, by computing the (absolute) difference \(abs(x^2-a)\). If it’s close enough (for example, less than \(10^{-6}\)) we’re done. Otherwise, calculate an improved guess \(\frac{1}{2}(x + \frac{a}{x})\); this replaces the previous value of \(x\) and we repeat from the test.
Implement a function that computes square roots using the Babylonian
algorithm. From the algorithm’s description, you may already have guessed
that using a while loop is a good way to go.
Testing your function. The math module provides a square root
function, math.sqrt, so you can test your function by comparing its
result with what math.sqrt returns. Try changing the threshold for
when the answer is close enough and see what effect this has on the
values returned by your function.
To get a better understanding of what is happening, you can also try
adding a print call inside the loop in your function, so that you can
see how the guesses are updated in each iteration. They should be
converging towards the correct answer. Recall that you can also
use the Online Python tutor.
(You can find this example, and it’s solution, in Chapter 7 of Downey’s book.)
Exercise 5: Digit Sums [Available at CodeBench]#
The digit sum of a (positive) integer number is the sum of the digits of the number when it is written out (in base 10). For example the digit sum of 301 is 3 + 0 + 1 = 4.
Write three functions, sum_odd_digits(number),
sum_even_digits(number) and sum_all_digits(number), which compute
the sum of the odd digits, the even digits, and all digits, respectively,
in a given number. For example,
sum_odd_digits(1282736)should return 11 (because 1 + 7 + 3 = 11)sum_even_digits(1282736)should return 18 (because 2 + 8 + 2 + 6 = 18)sum_all_digits(1282736)should return 29 (because 1 + 2 + 8 + 2 + 7 + 3 + 6 = 29)
Hint #1:
The modulo (%) and floor division (//) operators are useful for
solving this problem. For example, number % 10 will give you the
least significant (“rightmost”) digit in number.
Hint #2: Think about whether you could write one or more additional functions that incorporate the common functionality from all three functions.