Lab 10 - Practice Exam Questions (Weeks 11 and 12)
Reminder (VERY IMPORTANT)#
Take this opportunity to login NOW into the lab computer with your ANU credentials if you have not done it before (or if you do not know or remember if you have done it before).
Recall that the final exam will be performed in the lab using the lab computers.
Objectives#
This lab contains some examples of the types of problems you may encounter on the final exam. The exam will in general cover all topics covered in lectures and labs, for example, to check your ability to (but not limited to):
- Improve the quality of certain code
- Propose “good” test cases to some function without needing to know the code
- Read, understand, and debug certain code
- Analyse the time complexity
- Write Python code to solve certain programming problems
Problems are presented in no particular order. Don’t assume that the first is easier than the second, and so on.
Tutors may be busy talking with students about the project assignment during week 11 and 12, but you can ask them during week 11 and 12 if you have any questions.
You can use the testing functions provided in the skeleton files for the programming problems to test your implementation, much like for homework/project assignments and the final exam.
1. Improving code quality#
Good code quality is essential for a successful development of a large program. Aspects of good code quality include: good docstrings/comments, good variable/function names, good code organisation, and code efficiency (when necessary). In the following you will exercise how to improve the quality of certain code.
Exercise 1.1#
The following function splits a string into a list of substrings, where each
substring consists of only letters, and returns the list. For example:
my_func("hello everONE 12 hh3")
returns ['hello', 'everONE', 'hh']
.
def my_func(astring):
l = []
s = ""
for i in range(len(astring)):
if "a" <= astring[i] <= "z": # lower-case letter
s = s + astring[i]
# do special thing with first element
if i == len(astring)-1:
l = l+[s]
elif "A" <= astring[i] <= "Z": # character is a number
s = s + astring[i]
# do special thing with first element
if i == len(astring)-1:
l = l+[s]
else:
# upper-case letter
if len(s) == 0:
i = i-1+1
else:
l=l+[s]
s="" # set s to empty string
return l
Describe all ways in which the quality of the code above can be improved. Your suggested improvements must be specific. (For example, if you think that naming should be improved, you must give at least one specific example of which names should be changed and to what; just answering “better names” is not enough.)
Exercise 1.2#
In a sequence of numbers, we say that there is a peak at index i if the value at i is greater than both the neighbouring values, at i-1 and at i+1. The first and last number in the sequence are also peaks, if they are greater than their one neighbouring value. For example, in the sequence
[13.0, 9.6, 14.2, 17.5, 8.9, 9.7, 15.7, 20.4, 14.8, 13.2, 13.6, 15.6, 17.9, 24.1, 19.2]
there are peaks at indices 0 (because 13.0 > 9.6
), 3 (because 14.2 < 17.5 > 8.9
),
7 (because 15.7 < 20.4 > 14.8
) and 13 (because 17.9 < 24.1 > 19.2
).
The following function takes as argument a numeric
sequence and returns average distance between all the peaks in it.
The distance between two peaks at indices i
and j
is defined as abs(i-j)
.
def my_func(s):
x = [] # sets x to empty list
for i in range(len(s)):
if i - 1 >= 0 and i + 1 < len(s):
if s[i] > s[i-1] and s[i] > s[i+1]:
x.append(i)
elif i - 1 >= 0 and i + 1 >= len(s):
# i is the first element
if s[i] > s[i-1]:
x.append(i)
elif i - 1 < 0 and i + 1 < len(s):
# i is the last element
if s[i] > s[i+1]:
x.append(i)
if len(x) < 2:
return 0.0
else:
count = 0
t = 0
for i in range(len(x)):
for j in range(i + 1, len(x)):
count += 1
t += abs(x[i] - x[j])
return t / count
Describe all ways in which the quality of the code above can be improved. Your suggested improvements must be specific. (For example, if you think that naming should be improved, you must give at least one specific example of which names should be changed and to what; just answering “better names” is not enough.)
2. Testing#
Testing is an important skill. Software testers usually need to think about designing a small enough set of good test cases that still cover a large spectrum of parameters to ensure that the code runs correctly for most or all parameters. In the following you will exercise how to carefully design good test cases for some function without even knowing the code of the function.
Exercise 2.1#
Here is a function and its docstring:
def smallest_non_negative(number_list):
"""
Argument is a list of numeric values (integer or float).
Returns the smallest non-negative value in the list,
and zero if there is no such value.
"""
Write at most 4 test cases for this function. For each test case, you must write down the input (argument to the function) and the expected return value. Each test case should specify valid arguments for the function. Your test cases should cover all relevant corner cases.
Exercise 2.2#
Here is a function and its docstring:
def sequence_similarity(s1, s2)
"""
s1 and s2 are two sequences of the same length.
Returns the number of i-th elements that are equal
between two sequences, i.e., where s1[i] == s2[i]
"""
Write at most 4 test cases for this function. For each test case, you must write down the input (argument to the function) and the expected return value. Each test case should specify valid arguments for the function. Your test cases should cover all relevant corner cases.
Exercise 2.3#
For a sequence of strings and an integer k, we want to find a substring of length k
that is common to the most strings and must occur at least twice.
For example, for the sequence ['honestness', 'honestly', 'dishonest', 'fairly']
and k=6
, the answer is 'honest'
because it appears in 3 strings and no substring
of length 6 appears in all 4 strings. For the same list of strings and k=5
,
the answer is 'hones'
or onest
. When there is more than one solution like this,
it is OK to report one of them. For k=7
, the answer is ''
(empty string)
because there is no substring of length 7 that occurs in 2 or more strings.
Here is a function with its docstring which aims to implement this:
def most_common_substr(seq_strings, k):
"""
seq_strings is a sequence of strings with at least 2 elements.
k is a positive integer.
Returns a string of length exactly k which appears as a
sub-string in the most elements of seq_strings.
If no substrings of length k exist in 2 or more elements
of seq_strings, the empty string is returned.
If two or more substrings of length k appear in the same number
of elements of seq_strings only one will be returned.
"""
Write at most 5 test cases for this function. For each test case, you must write down the input (argument to the function) and the expected return value(s). Each test case should specify valid arguments for the function. Your test cases should cover relevant corner cases.
3. Debugging#
Exercise 3.1#
Each of the following pieces of python code attempt to compute and print
the maximum difference between any pair of numbers in a list x
. (Note
that the maximum difference is always greater than or equal to zero, which
is the difference between any number and itself.)
For each one, you should
determine whether it is correct, meaning that it runs without error and
prints the correct value. If it is not, provide an input
that would cause the code to return the wrong output and
explain precisely what is wrong with the code.
Assume that variable x
is defined in the global namespace and that its
value is a non-empty list of numbers.
(a)
def find_max(x, y):
c = []
for i in x:
for j in y:
c.append(x[i] - y[j])
return max(c)
print("The max difference is ", find_max(x, x))
(b)
def find_max(x, y):
d = 0
for i in x and j in y:
d = max(d, i - j)
return d
print("The max difference is ", find_max(x, x))
(c)
def find_max(y):
z = x[0] * y
for i in range(len(x)):
x[i] = y * x[i]
if x[i] > z:
z = x[i]
return z
print("The max value is ", find_max(1))
print("The min value is ", find_max(-1))
print("The max difference is ", find_max(1) - find_max(-1))
(d)
def find_max(x):
x = x.sort()
return x[-1] - x[1]
print("The max difference is ", find_max(x))
Exercise 3.2#
We call a dictionary invertible if every key in it maps to a unique value,
or in other words, for every value appearing in the dictionary, there is
only one key that maps to that value. Below are three attempts to define a
function is_invertible(adict)
, which takes as argument a dictionary and
returns True
if the dictionary is invertible, and False
otherwise.
For example, is_invertible({ 'a' : 'b', 'b' : 'e', 'c' : 'f' })
should
return True
, but is_invertible({ 'a' : 'b', 'b' : 'e', 'c' : 'b' })
should return False
, because keys 'a'
and 'c'
both map to the same
value, 'b'
.
For each of the functions below, determine whether it is correct or not. Correct mean that the function runs without error and returns the right answer for any dictionary. If a function is not correct, explain precisely what is wrong with it.
(a)
def is_invertible(adict):
return sorted(adict.keys()) == sorted(adict.values())
(b)
def is_invertible(adict):
d = {}
for value in adict.values():
if value in d:
return False
else:
d[value] = 1
return True
(c)
Note: This implementation of the function uses another function,
make_inv_dict
, which is also defined below.
def is_invertible(adict):
inv_dict = make_inv_dict(adict)
return adict == inv_dict
def make_inv_dict(adict):
if len(adict) > 0:
key, val = adict.popitem()
adict = make_inv_dict(adict)
if val not in adict.values():
adict[key] = val
return adict
else:
return {}
Exercise 3.3#
Here is a function that takes as argument a sequence:
def funX(a_list):
index = 0
while index < len(sorted(a_list)) // 2:
index = index + 1
return sorted(a_list)[index]
(a) Explain what funX
does in general. A good answer is one
that describes the purpose of the function - something you would write
in its docstring.
(b) funX
is unnecessarily inefficient. Rewrite the function so
that it does the same thing, but as efficiently as possible.
Exercise 3.4#
Here is another function that takes a sequence as argument:
def funY(x):
i = 0
while i < len(x):
i = i + x[i] % len(x)
return i
(a) Give an example, if possible, of an argument sequence that
causes funY
to get stuck in an infinite loop, as well as an argument
sequence for which the function executes without error and returns a
value.
(b) What are the runtime errors that can occur in funY
, assuming
the argument is of type list
? For each error, give an example of an
argument list that causes the error.
Exercise 3.5#
A strictly increasing consecutive subsequence is a part of a sequence
in which every element is strictly greater than the previous element.
Because “strictly increasing consecutive subsequence” is a bit long,
we will call this a streak. For example, in the sequence (1,5,2,4,7,2)
,
the subsequences (1,5)
and (2,4,7)
are streaks. (Of course,
by definition, any subsequence of a streak is also a streak.)
(2,4,7)
is the longest streak among all streaks of that input sequence.
Below is a function that takes as argument a sequence of numbers, and it aims to return the length of the longest streak of the input sequence:
def longest_streak(seq):
i=0
counter=1
narray=[]
#base case
if len(seq)==0:
return(0)
while i < len(seq)-1:
if seq[i] < seq[i+1]:
counter=counter+1
i=i+1
else:
narray.append(counter)
counter=1
i=i+1
if len(narray)==0:
return(counter)
else:
return(max(narray))
However, the function above is not correct.
(a) Provide an example of argument, of correct types, that makes this function return the wrong answer or that causes a runtime error. The argument must be a sequence of numbers.
(b) Explain the cause of the error that you have found, i.e., what is wrong with this function. Your answer must explain what is wrong with the function as given. Writing a new function is not an acceptable answer, regardless of whether it is correct or not.
4. Time complexity#
Exercise 4.1#
Simplify the following big O expressions as much as possible:
- \(O(n + 10)\).
- \(O(100 * n)\).
- \(O(25)\).
- \(O(n^2 + n^3)\).
- \(O(n + n + n + n)\).
- \(O(1000 * \log{n} + n)\).
- \(O(1000 * n * \log{n} + n)\).
- \(O(2^n + n^2)\).
- \(O(10^{12} + 5 + 3 + 1)\).
- \(O(n + \sqrt{n} + n^2 + n * \log{n})\).
Exercise 4.2#
For each of the functions below, please write down the time complexity in big-O notation with respect to \(n\) and explain why.
- Note 1: complexity of the
len()
function andappend()
method is \(O(1)\) - Note 2: in the
matmul(A,x)
function, \(n\) denotes the number of rows and columns in the 2D arrayA
def elements_at_even_index(seq):
result=[]
for i in range(len(seq)):
if i%2==0:
result.append(seq[i])
return seq
def matmul(A,x):
assert len(shape(A))==2
assert len(shape(x))==1
assert A.shape[0]==A.shape[1]
assert A.shape[1]==x.shape[0]
y=x.copy()
for i in range(A.shape[0]):
y[i]=0.0
for j in range(A.shape[1]):
y[i]+=A[i,j]*x[j]
return y
def first_or_last_is_even(seq):
assert len(seq)>0
first_is_even=False
if seq[0]%2 == 0:
first_is_even=True
last_is_even=False
if seq[-1]%2 == 0:
last_is_even=True
return first_is_even or last_is_even
def power(x,n):
assert n>=0
if n==0:
return 1
else:
if (n%2==0):
return power(x*x,n//2)
else:
return x*power(x*x,n//2)
def f(n):
assert n>=0
if n==0:
return 0
elif n==1:
return 1
else:
return f(n-1)+f(n-1)
Exercise 4.3#
Given the following function:
def sum_scan(l):
result = [0 for i in range(len(l))]
for i in range(len(l)):
for j in range(i+1):
result[i]=result[i]+l[j]
return result
(a) Figure out what the function sum_scan
does and explain it
with words.
(b) Write down the time complexity in big-O notation as a function
of \(n\) being the length of the input list l
.
(c) Can you think of an alternative algorithm for the sum_scan
function
with a reduced order of time complexity? If yes, write it down the alternative
sum_scan
function.
Programming problems#
For each problem there is a problem description and a skeleton file for you to write your solution into. This file also has a testing function that runs several test cases on your functions (like you have seen in the homeworks).
Remember that the set of tests provided is never complete. Your task is to write a function that solves the problem that is described for all valid arguments (i.e., all arguments that meet the restrictions given in the problem description). Passing the tests does not prove that your implementation is correct, but failing any test proves that your code is wrong.
Problem 1#
A sequence of numbers is called super-increasing if and only if every number in the sequence is strictly greater than the sum of all numbers preceding it in the sequence. The first element in the sequence can be any number.
For example, the sequences 1,3,5,11,21
and -2,1,2
are both
super-increasing; the sequence 1,3,5,7,19
is increasing, but not
super-increasing.
Write a function super_increasing(seq)
that takes as argument a
sequence of numbers and returns True if the sequence is super-increasing
and False if it is not.
- You can assume that the argument is a non-empty sequence of numbers.
- You should not assume that values in the sequence are unique or increasing.
- You should not make any assumption about the type of the argument other than that it is a sequence type; likewise, you should not make any assumption about the type of the numbers in the sequence, other than that they are numbers.
- The function must not modify the argument sequence.
- The function must return a truth value (a value of type
bool
).
Files:
- Skeleton file: super_increasing.py
You should write your solution into this file. Remember that:
- The file must contain only syntactically correct python code (and comments).
- Do not import any module that you do not use.
- You must define a function named
super_increasing
that has one parameter. You may also define additional functions if it helps you break down or solve the problem.
Using the testing function:
The skeleton code file includes a testing function, test_super_increasing
,
which will run some tests on your function and raise an error if any test
fails. Passing the tests does not prove that your solution is correct.
Failing any test proves that your function is wrong.
Problem 2#
A closed interval of the real number line is defined by its lower
and upper end points.
Write a function interval_intersection(lA, uA, lB, uB)
that returns
the length of the intersection of two intervals A and B.
Arguments lA
and uA
are the lower and upper end points of interval
A, and lB
and uB
are the lower and upper end points of
interval B. If the intervals do not intersect, the function should
return 0.
For example, interval_intersection(0, 3, 1, 5)
should return
2
, because the intersection of the two intervals [0,3] and
[1,5] is [1,3], which has a length of 3 - 1 = 2.
- You can assume that the function’s arguments are numbers, but NOT that they are integers, or positive.
- Your function must return a number.
Files:
- Skeleton file: interval_intersection.py
You should write your solution into this file. Remember that:
- The file must contain only syntactically correct python code (and comments).
- Do not import any module that you do not use.
- You must define a function named
interval_intersection
that has four parameters. You may also define additional functions if it helps you break down or solve the problem.
Using the testing function:
The skeleton code file includes a testing function,
test_interval_intersection
,
which will run some tests on your function and raise an error if any test
fails. Passing the tests does not prove that your solution is correct.
Failing any test proves that your function is wrong.
Problem 3#
The integral of any function over a bounded interval [a,b] can be approximated by a sum. Each term in the sum approximates the integral over a small part of the interval with the area of a trapezoid that has two corners on the x-axis and two on the curve. For example, the following figure shows the curve x - x2 and two trapezoids: one over the interval [0.1, 0.4] and one over the interval [1.1, 1.4].
Let f(x) be the function that we want to integrate. The area of the trapezoid over the interval [x,x+d] is ((f(x) + f(x + d)) / 2) * d.
Write a function approximate_integral(lower, upper, nterms)
that calculates an approximation of the integral of the function
f(x) = x3 (that is, x cubed) over a bounded interval
using the trapezoid method.
The three parameters of the function are the lower and upper bound
of the interval, and the number of terms in the sum. The function
should calculate the sum of nterms
trapezoids of equal width.
- You can assume that
lower
is less than or equal toupper
. - You can assume that
nterms
is a positive integer. - Your function should return a numeric value.
Example:
approximate_integral(0, 2, 2)
should return 5. The first trapezoid is over the interval [0,1] and has an area of 0.5 (((0 + 1) / 2) * 1); the second is over the interval [1,2] and has an area of 4.5 (((1 + 8) / 2) * 1).
Files:
- Skeleton file: approximate_integral.py.
You should write your solution into this file. Remember that:
- The file must contain only syntactically correct python code (and comments).
- Do not import any module that you do not use.
- You must define a function named
approximate_integral
that has three parameters. You may also define additional functions if it helps you break down or solve the problem.
Using the testing function:
The skeleton code file includes a testing function, test_approximate_integral
,
which will run some tests on your function and raise an error if any test
fails. Passing the tests does not prove that your solution is correct.
Failing any test proves that your function is wrong.
Problem 4#
Let’s say that a counting dictionary is a dictionary
in which all values (not keys) are positive integers. (In other words,
it’s the kind of dictionary you get when you use a dictionary to count
repetitions of keys.) Given two counting dictionaries, A
and B
, the
difference between A
and B
is another counting dictionary that
contains the key-value pairs (k, n)
where n = A[k] - B[k]
for
exactly those keys k
such that n > 0
or k
appears only in A
.
Write a function count_dict_difference(A, B)
that takes as
arguments two counting dictionaries and returns a new dictionary that
is the difference between them.
- You can assume that both arguments are dictionaries, and the values stored in them are integers.
- You should make no assumption about the types of keys that can appear in the dictionaries.
- Your function must not modify either of the argument dictionaries.
- Your function should value of type
dict
.
Example:
For example if A = {'s': 4, 'm': 1, 'p': 2, 'i': 4}
(that’s the
letter counts for the word ‘mississippi’) and
B = {'e': 1, 's': 3, 'm': 1, 'p': 1, 'i': 2, 't': 1}
(that’s the
letter counts for the word ‘pessimist’), the difference of A
and B
is the dictionary {'s' : 1, 'p' : 1, 'i' : 2}
(note how 'm'
is not
in the difference because A['m'] - B['m'] == 0
).
Files:
- Skeleton file: count_dict_difference.py
You should write your solution into this file. Remember that:
- The file must contain only syntactically correct python code (and comments).
- Do not import any module that you do not use.
- You must define a function named
count_dict_difference
that has two parameters. You may also define additional functions if it helps you break down or solve the problem.
Using the testing function:
The skeleton code file includes a testing function, test_count_dict_difference
,
which will run some tests on your function and raise an error if any test
fails. Passing the tests does not prove that your solution is correct.
Failing any test proves that your function is wrong.
Problem 5#
Write a function remove_all(a_list, element)
, which removes all
occurrences of element
from a_list
. You can assume that the first
argument to the function, a_list
, is a list. The function should not
return any value (i.e., return None
) but should modify the argument
list. For example,
In [1]: my_list = [1,2,3,2,3,1,2]
In [2]: remove_all(my_list, 2)
In [3]: my_list
Out [3]: [1,3,3,1]
Files:
- Skeleton file: remove_all.py.
You should write your solution into this file. Remember that:
- The file must contain only syntactically correct python code (and comments).
- Do not import any module that you do not use.
- You must define a function named
remove_all
that has two parameters. You may also define additional functions if it helps you break down or solve the problem.
Using the testing function:
The skeleton code file includes a testing function, test_remove_all
,
which will run some tests on your function and raise an error if any test
fails. Passing the tests does not prove that your solution is correct.
Failing any test proves that your function is wrong.
Problem 6#
The moving average of a numeric sequence is a sequence of averages
of subsequences of the original sequence; the subsequences are known
as windows (or a sliding window), and the length of the subsequence
used is called the window size.
More precisely, given a sequence S
, the moving average with window
size w
is sequence A
such that the first element in A
is the
average of w
consecutive elements in S
starting with the first,
the second element in A
is the average of w
consecutive elements
in S
starting with the second, and so on until the last element in
A
, which is the average of w
consecutive elements in S
ending
with the last.
Example:
If S = (2, 0, -2, 2)
and w = 2
, the moving average is [1, -1, 0]
.
1
is the average of (2, 0)
, -1
is the average of (0, -2)
, and
0
is the average of (-2, 2)
.
Write a function moving_average(seq, wsize)
that computes and returns
the moving average of seq
with window size wsize
.
- You should assume that the argument is a sequence of numbers (integer or floating point, or a mix of them).
- You should NOT make any assumption about the type of the sequence (e.g., it could be list, tuple or NumPy array).
- You can assume that
wsize
is an integer, at least 1, and less than or equal to the length ofseq
. - Your function must return a sequence of numbers (this can be, for example, a list, a tuple or NumPy array).
Files:
- Skeleton file: moving_average.py
You should write your solution into this file. Remember that:
- The file must contain only syntactically correct python code (and comments).
- Do not import any module that you do not use.
- You must define a function named
moving_average
that has two parameters. You may also define additional functions if it helps you break down or solve the problem.
Using the testing function:
The skeleton code file includes a testing function, test_moving_average
,
which will run some tests on your function and raise an error if any test
fails. Passing the tests does not prove that your solution is correct.
Failing any test proves that your function is wrong.
Problem 7#
We say that a list that contains lists is nested. The result of unnesting (also known as “flattening”) a nested list is a list that contains the same non-list elements as the nested list, in the same order, but in a single list.
For example, [1, [2], [[3], [[4], 5]]]
is a nested list. The
unnesting of this list is [1, 2, 3, 4, 5]
.
Write a function called unnest
that takes as argument a list,
which may be nested, and returns the unnesting of the argument
list.
- You should assume that the argument is a list, and that all elements in the list are either lists or some non-sequence type.
- Your function must not modify the argument list. It must return
a value of type
list
.
Files:
- Skeleton file: unnest.py
You should write your solution into this file. Remember that:
- The file must contain only syntactically correct python code (and comments).
- Do not import any module that you do not use.
- You must define a function named
unnest
that has one parameter. You may also define additional functions if it helps you break down or solve the problem.
Using the testing function:
The skeleton code file includes a testing function, test_unnest
,
which will run some tests on your function and raise an error if any test
fails. Passing the tests does not prove that your solution is correct.
Failing any test proves that your function is wrong.