CPTR 124 Fundamentals of Programming
In this lab you will write some functions that work with Python lists.
- Teams
You may work with a partner for this lab. You and your partner should begin thinking about the problems and begin writing the code before lab time.
- Set up
Download the Python source file
liststuff.py
. This file contains skeleton code for the functions that you are to implement. A very rudimentry test program, simplelisttestfile.py, also is available. You will want to augment this simple test file to perform some more exhaustive tests of your functions. - Implement the functions
Implement all the functions found in
liststuff.py
. The functions all process Python lists, and they expect the lists to contain only integers. The behavior of any of these functions is undefined if the list passed to it contains one or more elements that is not an integer. (Undefined behavior means you do not need to worry about what happens.)Python has built-in functions that exactly match some of the functions below, but you are not allowed to use these built-in list processing functions. In particular, you may not use any functions or methods that involve lists except for
len
. (It is OK to use therange
function.)The specifications for the functions are listed here:
-
maximum(seq)
Returns the maximum value in the list
seq
. The function should returnNone
if the list is empty.The function does not affect the contents of the list
seq
. The function should use no extra space except for a few local scalar variables.
-
find(seq, seek)
Returns the location (zero is the first position) of the first occurrence of
seek
within listseq
. Said another way, it returns the lowest index inseq
that contains the valueseek
. Ifseek
is not present inseq
, the function returns –1.The function does not affect the contents of list
seq
. The function should use no extra space except for a few local scalar variables.
-
count(seq, seek)
Returns the number of times element
seek
appears in listseq
.The function does not affect the contents of list
seq
. The function should use no extra space except for a few local scalar variables.
-
equivalent(seq1, seq2)
Returns
True
if listsseq1
andseq2
contain exactly the same elements, regardless of their order within the lists; otherwise, the function returnsFalse
.For example, suppose we have the following three lists:
- The list
list1
is[1, 2, 3, 4, 3, 5, 6]
. - The list
list2
is[3, 2, 1, 4, 6, 5, 3]
. - The list
list3
is[3, 2, 1, 4, 6, 5]
.
The call
equivalent(list1, list2)
would return true, since both lists contain exactly the same elements, although not necessarily in the same order. The callequivalent(list1, list3)
would return false, because even though both lists contain the same values,list1
has two 3s whilelist3
has only one 3.Two empty lists are considered equivalent. The function should not disturb the contents of either list during its processing. The function should use no extra space except for a few local scalar variables.
- The list
-
prefix(seq1, seq2)
Given list
seq1
with length n and listseq2
, the function returns true if the first n elements ofseq2
are identical to the contents ofseq1
; that is,seq1
is a "prefix" ofseq2
. The function returns false ifseq1
is not prefix ofseq2
.Some examples include
[2,-5,0] is a prefix of [2,-5,0,11,4] (first three elements match)
[2,-5,0] is NOT a prefix of [0,-5,2,11,4] (order matters)
[2,-5,0] is NOT a prefix of [11,2,-5,0,4] (matching elements not at beginning)
Every sequence is a prefix of itself, and the empty sequence is a prefix of any sequence.
The function should not disturb the contents of either list during its processing. The function should use no extra space except for a few local scalar variables.
-
sort(seq)
Physically rearranges the elements of list
seq
so they are in ascending order.For example, if
s
is[2, 1, 3, 1, 5, 2]
, the callsort(s)
reorderss
to[1, 1, 2, 2, 3, 5]
.The function necessarily can affect the contents of the caller's list. The function should use no extra space except for a few local scalar variables. The function should not return anything to the caller.
-
is_ascending(seq)
Returns true if the elements of list
seq
are arranged in ascending order. If any element appears after an element greater than itself, the function returns false. An empty list by default is considered to be in ascending order.The function does not affect the contents of list
seq
. The function should use no extra space except for a few local scalar variables.
-
filter(seq, qual)
Creates and returns a new list containing exactly those elements of the list
seq
that qualify according to thequal
function. Thequal
parameter is a function that accepts a single parameter and returnsTrue
orFalse
.For example, suppose you have the following function
bigger_than_10
:def bigger_than_10(n): return n > 10The callfilter([10, 15, 20, 4, 9, 31], bigger_than_10)
would return the list[15, 20, 31]
, effectively the only elements in the original list larger than 10.The function should not disturb the contents of the original list during its processing.
-
map(seq, f)
Modifies the elements of list
seq
using the functionf
. The parameterf
is a function that accepts a single parameter and returns a value.map
applies functionf
to each element inseq
, replacing the element with the return value off
.For example, suppose you have the following function
twice
:def twice(n): return 2 * nand the list[1, 5, 2, 4, 9, 3]
namedmy_list
. The callmap(my_list, twice)
would modify the elements ofmy_list
to be[2, 10, 4, 8, 18, 6]
, effectively doubling each of the elements of the list.The function necessarily can affect the contents of the original list during its processing. The function should use no extra space except for a few local scalar variables. The function should not return anything to the caller.
-
rotate(seq, dist)
Physically rearranges the elements of
seq
so that all the elements are shifted towards the back by a distance ofdist
. As an element "falls off" the rear, it is placed at the front in the space vacated when the first element was shifted backwards.For example, if
s
is originally[1, 2, 3, 4, 5, 6]
, the callrotate(s, 2)
rearrangess
to contain[5, 6, 1, 2, 3, 4]
.Notice that if
dist
is equal to the size of the list, after the rotation all the elements rotate to their original locations.If
dist
is negative, the elements are shifted forwarddist
spots instead of backwards. As an element "falls off" the front it is placed on the rear in the space vacated when the last element was shifted forwards.For example, if
s
is originally[1, 2, 3, 4, 5, 6]
, the callrotate(s, -2)
rearrangess
to contain[3, 4, 5, 6, 1, 2]
. The rotation is easier to understand if you visualize the list as a circular structure as shown in the following figure:The figure shows the original list on the left and the list rotated by –2 on the right.
This function necessarily can affect the contents of the list. The function should use no extra space except for a few local scalar variables. The function should not return anything to the caller.
-
subsequence(seq1, seq2)
The parameters
seq1
andseq2
both represent lists. The callsubsequence(seq1, seq2)
returns true, ifseq2
is a subsequence ofseq1
; otherwise, it returns false.A subsequence is a sequence of elements that are part of a potentially larger sequence. Given any sequence, you can produce a subsequence by removing none, some, or all of the elements in the original sequence. The remaining elements must appear in same relative order as in the original sequence.
The concept is best explained by some examples: If
seq1
is the sequence[23, 4, 19, -4, 0, 3]
andseq2
is the sequence[19, -4, 0]
seq2
is a subsequence ofseq1
.If
seq1
is the sequence[23, 4, 19, -4, 0, 3]
andseq2
is the sequence[19, 0]
seq2
is a subsequence ofseq1
.If
seq1
is the sequence[23, 4, 19, -4, 0, 3]
andseq2
is the sequence[19, -4, 0, 3, 5]
seq2
is not a subsequence ofseq1
, becauseseq2
contains an element that does not appear inseq1
.If
seq1
is the sequence[23, 4, 19, -4, 0, 3]
andseq2
is the sequence[23, 0, -4]
seq2
is not a subsequence ofseq1
even though all of its elements appear inseq1
. This is becauseseq2
's elements are not in the same relative order as inseq1
(0 comes after –4 inseq1
but before –4 inseq2
.)If
seq1
is the sequence[23, 4, 19, -4, 0, 3]
andseq2
is the sequence[23, 4, 19, -4, 0, 3]
seq2
is a subsequence ofseq1
; thus, any sequence is a subsequence of itself.The empty sequence is a subsequence of every sequence.
The function should disturb neither list
seq1
nor listseq2
during its processing. The function should use no extra space except for a few local scalar variables.
The specification that a function does not disturb the list means that the function should leave contents of the list unchanged; the function may not reassign, rearrange, or otherwise change the elements of the list. The specification that a function uses no extra space except for a few local scalar variables means that you may not declare any local lists or other potentially large data structures to facilitate the function's processing. We say that the function processes the list "in place" without copying its contents into another, temporary list.
None of the functions specified above should do any input or output. This means that neither
print
norinput
should appear in any of the functions. You are welcome to add printing statements during development for debugging purposes, but you should remove or comment out these printing statements when you are ready to submit your program for testing. -
- Check out
Your finished
liststuff.py
file will be evaluated for correctness and compliance. Before showing me your code, be sure that it complies with the following requirements:- Your name and your partner's name should appear in the in a comment at the top of the source code. Failure to provide such a comment results in an immediate failed test.
- Ensure that your
liststuff.py
module runs without any problems with the very simple test file simplelisttestfile.py. If yourliststuff.py
file does not run without errors with this very simple test program, it will not work with my test program either. If your code exhibits any errors, it counts as a failed test. This simple test file is very minimal and is designed merely to verify that your code meets some minimal standards; it does not begin to demonstrate the correctness of your code's logic. You should write your own test code to verify your functions' correctness.
You may provide to me your
liststuff.py
file for testing up to three times before its due date. The final test determines the score based on the number of functions that pass the tests. 10 points means 10 functions passed all their tests, 9 points means 9 of the functions passed all their tests, etc. If all 11 functions pass all their tests on the first attempt and the first attempt is performed on or before the assignment's due date, you will receive 11 out of 10 points. If you provide your functions for their first test after their due date, your score for the assignment is determined by the first test. After the final check you should submit yourliststuff.py
Python source file tohttp://eclass.e.southern.edu
.