CPTR 124 Fundamentals of Programming Lab

List Processing

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 the range function.)
The specifications for the functions are listed here:
- maximum(seq)
  
  Returns the maximum value in the list seq. The function should return None 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 list seq. Said another way, it returns the lowest index in seq that contains the value seek. If seek is not present in seq, 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 list seq.
  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 lists seq1 and seq2 contain exactly the same elements, regardless of their order within the lists; otherwise, the function returns False.
  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 call equivalent(list1, list3) would return false, because even though both lists contain the same values, list1 has two 3s while list3 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.
- prefix(seq1, seq2)
  
  Given list seq1 with length n and list seq2, the function returns true if the first n elements of seq2 are identical to the contents of seq1; that is, seq1 is a "prefix" of seq2. The function returns false if seq1 is not prefix of seq2.
  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 call sort(s) reorders s 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 the qual function. The qual parameter is a function that accepts a single parameter and returns True or False.
  For example, suppose you have the following function bigger_than_10:
  def bigger_than_10(n): return n > 10
  The call filter([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 function f. The parameter f is a function that accepts a single parameter and returns a value. map applies function f to each element in seq, replacing the element with the return value of f.
  For example, suppose you have the following function twice:
  def twice(n): return 2 * n
  and the list [1, 5, 2, 4, 9, 3] named my_list. The call map(my_list, twice) would modify the elements of my_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 of dist. 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 call rotate(s, 2) rearranges s 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 forward dist 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 call rotate(s, -2) rearranges s 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 and seq2 both represent lists. The call subsequence(seq1, seq2) returns true, if seq2 is a subsequence of seq1; 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]
               
```
  and seq2 is the sequence
```
               [19, -4, 0]
               
```
  seq2 is a subsequence of seq1.
  If seq1 is the sequence
```
               [23, 4, 19, -4, 0, 3]
               
```
  and seq2 is the sequence
```
               [19, 0]
               
```
  seq2 is a subsequence of seq1.
  If seq1 is the sequence
```
               [23, 4, 19, -4, 0, 3]
               
```
  and seq2 is the sequence
```
               [19, -4, 0, 3, 5]
               
```
  seq2 is not a subsequence of seq1, because seq2 contains an element that does not appear in seq1.
  If seq1 is the sequence
```
               [23, 4, 19, -4, 0, 3]
               
```
  and seq2 is the sequence
```
               [23, 0, -4]
               
```
  seq2 is not a subsequence of seq1 even though all of its elements appear in seq1. This is because seq2's elements are not in the same relative order as in seq1 (0 comes after –4 in seq1 but before –4 in seq2.)
  If seq1 is the sequence
```
               [23, 4, 19, -4, 0, 3]
               
```
  and seq2 is the sequence
```
               [23, 4, 19, -4, 0, 3]
               
```
  seq2 is a subsequence of seq1; 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 list seq2 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 nor input 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:
1. 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.
2. Ensure that your liststuff.py module runs without any problems with the very simple test file simplelisttestfile.py. If your liststuff.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 your liststuff.py Python source file to http://eclass.e.southern.edu.