Lab 9
This lab contains examples of the type of programming problems you may encounter on the programming exam (final exam part B). The problems are presented in no particular order. Don’t assume that the first is easier than the second, and so on.
For each problem there is a problem description, a skeleton file for you to write your solution into, and a testing program (like the ones you have seen for the homework problems). Learn to use the testing program! It can provide useful feedback on errors in your solution, whether they are simple such as syntax errors or violations of the submission requirements, or semantic errors in your implementation.
Problem 1#
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_intergral(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: problem1.py
- Testing program: test_problem1.py
- Testing module: testing.py
Using the testing program:
To run the testing program, download both
test_problem1.py and its supporting
module testing.py and save them to the same
directory as your solution file. Then run test_problem1.py
.
The program will test the implementation of the function named
approximate_integral
in the file problem1.py
in the same directory.
If you have named your solution file differently, you need to change
the name of the tested file on the last line of the testing program.
Other than this, you should make no changes to the testing program.
Remember that:
- Your solution file must be syntactically correct python code.
- Your solution file must not contain anything other than function definitions, import statements and comments.
- You can use docstrings, but only inside a function definition.
The testing program will reject your file if it breaks any of these requirements.
Problem 2#
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 count dictionaries, A
and B
, the
difference between A
and B
is another count 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 count 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: problem2.py
- Testing program: test_problem2.py
- Testing module: testing.py
Using the testing program:
To run the testing program, download both
test_problem2.py and its supporting
module testing.py and save them to the same
directory as your solution file. Then run test_problem2.py
.
The program will test the implementation of the function named
count_dict_difference
in the file problem2.py
in the same directory.
Remember that:
- Your solution file must be syntactically correct python code.
- Your solution file must not contain anything other than function definitions, import statements and comments.
- You can use docstrings, but only inside a function definition.
The testing program will reject your file if it breaks any of these requirements.
Problem 3#
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 NumPy array, which does not contain anything other than (integer or floating point) numbers. (Note, however, that the problem does not require you to use anything other than general sequence operations that also work on other sequence types. That is, there is nothing in the problem or its solution that is specific to NumPy arrays.)
- 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 NumPy array, or a sequence that can be converted to an array (such as a list of numbers).
Files:
- Skeleton file: problem3.py
- Testing program: test_problem3.py
- Testing module: testing.py
Using the testing program:
To run the testing program, download both
test_problem3.py and its supporting
module testing.py and save them to the same
directory as your solution file. Then run test_problem3.py
.
The program will test the implementation of the function named
moving_average
in the file problem3.py
in the same directory.
Remember that:
- Your solution file must be syntactically correct python code.
- Your solution file must not contain anything other than function definitions, import statements and comments.
- You can use docstrings, but only inside a function definition.
The testing program will reject your file if it breaks any of these requirements.
Problem 4#
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: problem4.py
- Testing program: test_problem4.py
- Testing module: testing.py
Using the testing program:
To run the testing program, download both
test_problem4.py and its supporting
module testing.py and save them to the same
directory as your solution file. Then run test_problem4.py
.
The program will test the implementation of the function named
unnest
in the file problem4.py
in the same directory.
Remember that:
- Your solution file must be syntactically correct python code.
- Your solution file must not contain anything other than function definitions, import statements and comments.
- You can use docstrings, but only inside a function definition.
The testing program will reject your file if it breaks any of these requirements.
Problem 5#
The digit sum of a number is the sum of the digits in the number when it is written out. For example, the digit sum of 52 is 7 (5 + 2) and the digit sum of 1000 is 1 (1 + 0 + 0 + 0).
Write a function digit_sum(number)
that takes as argument a number
and returns its digit sum.
- You can assume that the argument is a non-negative integer.
- You should not assume any upper limit on the number. (Remember
that python’s
int
type can represent integers of unlimited range.)
Files:
- Skeleton file: problem5.py
- Testing program: test_problem5.py
- Testing module: testing.py
Using the testing program:
To run the testing program, download both
test_problem5.py and its supporting
module testing.py and save them to the same
directory as your solution file. Then run test_problem5.py
.
The program will test the implementation of the function named
digit_sum
in the file problem5.py
in the same directory.
Remember that:
- Your solution file must be syntactically correct python code.
- Your solution file must not contain anything other than function definitions, import statements and comments.
- You can use docstrings, but only inside a function definition.
The testing program will reject your file if it breaks any of these requirements.
Advanced: In the lecture on the floating point number representation, we mentioned that integers can be represented in a base other than 10, for example, base 2 (binary) or base 3. Another base sometimes used in computing is base 8.
Modify your digit_sum
function to take a second argument, representing
the base. (The base must be at least 2. For bases greater than 10, we
don’t have digits, but for the purpose of summing their value this is
not necessary.) There is no testing program for this variant, so you will
have to create your own tests.