Lab 9 - Time complexity. More practice on debugging and programming.
Objectives#
The purpose of this week’s lab is to:
- Analyse time complexity of certain codes.
- Practice debugging code again.
- Practice more programming problems.
If you have any questions about any of the material in the previous labs, now is a good time to ask your tutor for help during the lab.
Note: If you do not have time to finish all exercises (in particular, the programming problems) during the lab time, you should continue working on them later.
CodeBench#
Most exercises in this lab are available on CodeBench under the Lab9 exercise set. For exercises 1.1 and 1.2 it checks if your reimplementations work correctly or not. For exercises 2.1 to 2.4 it is to check whether your fixes to the bugs work correctly or not.
Time complexity#
As we have seen in the lecture last week, the big-O notation is used to denote the worst-case time complexity of an algorithm to solve a certain problem. If the problem size is \(n\) and the algorithm needs \(c \times n\) numerical operations to solve it, where \(c\) is a constant number (thus independent of \(n\)), we say that the algorithm has a linear time complexity \(O(n)\). Here, we assume that each operation has a constant time complexity \(O(1)\). (Otherwise, the algorithm won’t have a linear complexity anymore.)
For example,
the following function finds the index of an element in a sequence,
(returning -1
if the element is not found):
def find_element(sequence, element):
for i in range(len(sequence)):
if sequence[i] == element:
return i
return -1
It has time complexity of \(O(n)\), where \(n\) is the length of the sequence.
This is because the main for
loop needs \(n\) comparisons in the worst-case,
namely when the element we are looking for does not appear in the sequence.
As a rule of thumb, a for
or while
loop with \(n\) iterations
indicates that the code may have a complexity of \(O(n)\). If there are
two loops nested within each other, the code might have a quadratic
time complexity of \(O(n^2)\).
Let’s look at an example: the following code computes the minimum absolute difference between any pairs of elements in a numerical sequence:
def smallest_difference(sequence):
min_diff = abs(sequence[0]-sequence[1])
for i in range(len(sequence)-1):
for j in range(i+1, len(sequence)):
diff = abs(sequence[i] - sequence[j])
if min_diff > diff:
min_diff = diff
return min_diff
Let’s analyse the time complexity of this code.
Let \(n\) be the length of the input sequence. The outer for
loop
has \(n-1\) iterations using index \(i\). In the first iteration of the
outer loop, i.e., when \(i=0\), the
inner loop iterates in range(1,n)
, each doing four operations
(subtraction, abs
, comparison, and assignment), totalling \(4(n-1)\) operations.
In the 2nd iteration of the outer loop (\(i=1\)), the inner loop iterates
over range(2,n)
, which means \(n-2\) iterations. And so on. Summing all together,
the total number of operations is:
Now, when \(n\) is large enough, the \(n^2\) term will dominate over the \(n\) term.
We can also ignore the constant \(2\) multiplying this leading term.
That means that the function smallest_difference
has time complexity \(O(n^2)\).
Exercise 1.0#
Each of the following three functions takes as input an integer n. For each function, give its computational complexity in big-O notation in terms of n.
def func_a(n):
total = 0
for i in range(n):
for j in range(n):
total = total + i * j
return total
def fun_b(n):
total = 0
for i in range(100 * n):
for j in range(10):
total = total + i * j
return total
def fun_c(n):
total = 0
for i in range(100):
for j in range(n):
total = total + i * j
for k in range(n):
total = total + i * k
for l in range(100):
total = total + i * l
return l
Exercise 1.1#
It turns out that there is another algorithm for smallest_difference
with a time complexity of only \(O(n \log(n))\). Can you figure that out?
Write another function with that time complexity.
HINT: What if the sequence is sorted? What is the time for sorting?
Exercise 1.2#
Here is an implementation to compute the maximum absolute difference
in a similar merit to smallest_difference
:
def largest_difference(sequence):
max_diff = abs(sequence[0]-sequence[1])
for i in range(len(sequence)-1):
for j in range(i+1, len(sequence)):
diff = abs(sequence[i] - sequence[j])
if max_diff < diff:
max_diff = diff
return max_diff
It has a time complexity of \(O(n^2)\). You can of course follow the same idea from exercise 1.1 to reduce the complexity to \(O(n \log(n))\).
However, there is another algorithm with a linear time complexity of only \(O(n)\). Can you figure that out? Write another function with that time complexity.
Exercise 1.3#
We now want to plot the real running times of these codes in a computer.
Run the following code to define a plot_time
function:
import random
import time
import matplotlib.pyplot as plt
def plot_time(func, steps):
seq = [ random.random() for i in range(steps) ]
elapsed_times = []
for n in range(2,steps):
start_time = time.time()
# run 10 times to reduce fluctuation
for i in range(10):
func(seq[:n])
end_time = time.time()
elapsed_times.append((end_time - start_time)/10)
plt.plot(range(2,steps),elapsed_times)
plt.show()
print("Total runtime: " + str(sum(elapsed_times)) + " seconds")
Then you can run plot_time(smallest_difference, 300)
to plot the running
time (in seconds) of the smallest_difference
function for
sequences of up to 300 randomly-generated floats.
If you have a faster implementation, say, for example smallest_difference2
,
you can run plot_time(smallest_difference2, 300)
and compare
these two plots to see how different the runtimes are. Do your observations
match the time complexity analysis of the algorithms?
Debugging problems#
Learning to read, understand and debug code is a very important skill, so here are some debugging exercises to practice this skill.
Exercise 2.1#
The following are attempts to define a function that takes
three (numeric) arguments and checks if any one of them is equal to
the sum of the other two. For example, any_one_is_sum(1, 3, 2)
should return True
(because 3 == 1 + 2
), while
any_one_is_sum(0, 1, 2)
should return False
.
(a) All of the functions below are incorrect. For each of them, find examples of arguments that cause it to return the wrong answer.
Function 1#
def any_one_is_sum(a,b,c):
sum_c=a+b
sum_b=a+c
sum_a=b+c
if sum_c == a+b:
if sum_b == c+a:
if sum_a == b+c:
return True
else:
return False
Function 2#
def any_one_is_sum(a,b,c):
if b + c == a:
print(True)
if c + b == a:
print(True)
else:
print(False)
return False
Function 3#
def any_one_is_sum(a, b, c):
if a+b==c and a+c==b:
return True
else:
return False
(b) For each of the three functions above, can you work out how they are intended to work? That is, what was the idea of the programmer who wrote them? What comments would be useful to add to explain the thinking? Is it possible to fix them by making only a small change to each function?
Exercise 2.2#
Here is a function that is meant to return the position (index) of
a given element in a sequence; if the element does not appear in the
sequence, it returns the length of the sequence.
For example, find_element([3,2,1,4], 1)
should return 2
, since
that is the index where we find a 1
.
def find_element(sequence, element):
i = 0
while sequence[i] != element:
if i < len(sequence):
i = i + 1
i = i + 1
return i
However, the function is not correct. For some inputs it will cause a runtime error. Find an example of arguments that cause an error to occur. Can you correct the error without introducing another?
Exercise 2.3#
Here is a function that is meant to count the number of repetitions of
a substring in a string. For example, if the string is 'abcdabcf'
and
the substring is 'ab'
, the count should be 2. (Of course, for any of the
substrings 'a'
, 'b'
, 'c'
, 'ab'
, 'bc'
or 'abc'
, the count should
be 2.)
def count_repetitions(string, substring):
'''
Count the number of repetitions of substring in string. Both
arguments must be strings.
'''
n_rep = 0
# p is the next position in the string where the substring starts
p = string.find(substring)
# str.find returns -1 if the substring is not found
while p >= 0:
n_rep = n_rep + 1
# find next position where the substring starts
p = string[p + 1:len(string) - p].find(substring)
return n_rep
However, the function is not correct. For some inputs it will return the wrong answer, and for some inputs it will get stuck in an infinite loop. Find examples of arguments that cause these errors to happen.
Among the many string methods, there is one that does what this function
is meant to do: 'abcdabcf'.count('abc')
will return 2. Can you fix the
function above without using the string count
method, i.e., keeping
the idea of the original function and only correcting the error?
Exercise 2.4#
Here is another string function. This function is meant to remove all
occurrences of a substring from a string, and return the result. For
example, if the string is 'abcdabcf'
and the substring is 'bc'
,
we want the function to return 'adaf'
.
def remove_substring_everywhere(string, substring):
'''
Remove all occurrences of substring from string, and return
the resulting string. Both arguments must be strings.
'''
p = string.find(substring)
lsub = len(substring) # length of the substring
while p >= 0:
string[p : len(string) - lsub] = string[p + lsub : len(string)]
p = string.find(substring)
return string
This function is also not correct, and should cause a runtime error on almost any input. Like in the previous problem, try to make the function do what it is supposed to while keeping the idea of the original function Can you also find a string method that does (or can be made to do) what this function is intended to do?
Programming problems#
Note: We don’t expect everyone to finish all these problems during the lab time. If you do not have time to finish these programming problems in the lab, you should continue working on them later (at home, in the CSIT labs after teaching hours, or on one of the computers available in the university libraries or other teaching spaces).
Reading image files#
Portable pixmap, or ppm, is a simple, non-compressed image format. A ppm file can be stored in text or binary form; let’s start with reading it in text form.
A text-form ppm file starts with the magic string P3
. That means the
first two characters in the file are always P3
. This identifies the file
format. After this comes three positive integers (each written out with
the digits 0-9): the first two are the width and height of the image, and
the third is the maximum colour value, which is less than or equal to 255.
Then follows width times height times 3 integers (again, each written with
digits 0-9); these represent the red, green and blue value for each pixel.
The pixels are written left-to-right by row from the top, meaning the first
triple of numbers is the colours of left-most pixel in the top row, then
the second from the left in the top row, and so on.
Here is a small example:
P3
3 2
255
255 0 0
0 255 0
0 0 255
255 255 0
255 255 255
0 0 0
This image has width 3 and height 2, which means it has 6 pixels.
All the numbers in the file are separated with whitespace, which can be
one or more spaces (' '
) or a newlines ('\n'
). The format does not
require that all pixels in a row are on one line. In the example above,
they are written one pixel per line, but the following would also be a
correct representation of the same image:
P3
3 2
255
255 0 0 0 255 0 0 0 255
255 255 0 255 255 255 0 0 0
To display the image after reading it, you can use the imshow
function
from the matplotlib.pyplot
module. You will need to create a 3-dimensional
array
, where the sizes of the dimensions are the width, the height, and 3.
The array entries at i,j,0
, i,j,1
and i,j,2
are the red, green
and blue colour values for the pixel at row i
column j
in the image.
For example, to show the image above, you can do the following:
import numpy as np
import matplotlib.pyplot as plt
image = np.zeros((2,3,3)) # create the image array (fill with 0s)
image[0,0,:] = 1.0, 0.0, 0.0 # RGB for top-left (0,0) pixel
image[0,1,:] = 0.0, 1.0, 0.0 # RGB for top-middle (1,0) pixel
image[0,2,:] = 0.0, 0.0, 1.0 # RGB for top-right (2,0) pixel
image[1,0,:] = 1.0, 1.0, 0.0 # RGB for row 2 left (0,1) pixel
image[1,1,:] = 1.0, 1.0, 1.0 # RGB for row 2 middle (1,1) pixel
image[1,2,:] = 0.0, 0.0, 0.0 # RGB for row 2 right (2,1) pixel
plt.imshow(image, interpolation='none')
plt.show()
Note that each of the colour values above (1.0
or 0.0
) is the result
of taking the corresponding colour value from the image file (255 or 0) and
dividing it by the maximum colour value (255). The extra argument
interpolation='none'
to imshow
disables image interpolation, which
it may otherwise do if the image has low resolution.
Write a function that displays the image read from a file. You need to create an array of the right size (as read from the image file) and replace the part that fills in the values above with some kind of loop that fills in the values read from the file.
Here are two image files (of the kind that the internet is most famous for) that you can test your program on: cat_picture_1.ppm, cat_picture_2.ppm.
Advanced:
As mentioned above, the ppm format also has a binary form. It is very
similar the text format, except that each colour value is stored as a
single byte, rather than written out as text. The magic string for this
format is P6
. The width, height and max colour value are still written
out with digits, and there should be a newline before the start of the
binary image data.
Modify your program so that it can read images in both text and binary
format. (To decide which format a given file is, you will need to open
it and read the first two characters.) Note that to read the binary
format correctly, you will have to open the file in binary mode.
You can also use function file filein.read(3)
to read three consecutive
bytes for the pixel colours.
Here are the two image files above encoded in the binary form: cat_picture_1_binary.ppm, cat_picture_2_binary.ppm.