CS21 Lab6: Lists, Stacks and Functions

Written work due in class this week!
Coding work due on Saturday (October 24) before midnight

This lab assignment requires you to complete some written work and also write some Python programs. First, run update21 to get the template files we have provided for you. These will serve as starting points for your programs. Next, use cd to change into your cs21/labs/06 directory and begin working on the Python programs for this lab. The pwd command helps you verify that you are in the correct sub-directory.

$ update21
$ cd cs21/labs/06
$ pwd
/home/your_user_name/cs21/labs/06
    

We will only grade files submitted by handin21 in this directory, so make sure your programs are in this directory!


Written work: The function stack
The first part of the lab involves you tracing a program with functions and showing the resulting stack that the function calls generate. This is excellent practice for what will almost certainly be a quiz question! Download the PDF here, print it out, and turn it in at the start of class on either Thursday or Friday, depending on when your class meets.
Python: List operations and functions
For this week's coding portion of the lab, you will write one program called listFns.py that implements a number of list operations. In order to complete this program you must implement each of the following functions. Note that normally it is fine to use built-in Python functions such as the list.count method, the max function, and the list.sort function, you should avoid using them in this lab because we would like you to learn how to write these functions yourself.

All of your functions should include a document comment describing the behavior of the function, the parameters and the return value.

  1. main should test each of the functions you are required to write below. You should test your program incrementally. First, write the input_integer function and be sure that it works before continuing to the get_list_from_user function. Keep this practice up until you have written all of the functions. An example of the output of this program is included at the end of the writeup, but you should be sure to test each of the functions fully in your main.
  2. input_integer takes a prompt string as its only parameter and asks the user to enter an integer using that prompt. The function repeats the prompt until the user enters a valid integer, and returns the first valid integer entered by the user. Your function should use try/except to validate that the user only enters integers.
  3. get_list_from_user takes no parameters. The function asks the user to enter a series of positive integers (using the input_integer function). Each time the user enters a value that is added to the list, display the current contents of the list. When the user enters zero or a negative integer, return a list of all the positive integers entered, in the order that the user entered them.
  4. largest_index takes a list as its only parameter and returns the index of the largest element in the list. If there are no elements in the list, this function returns -1. Examples:
    • largest_index([60, 29, 82, 45]) returns 2, the index of 82.
    • largest_index([45]) returns 0, the index of 45.
    • largest_index([2, 63, 2, 63]) returns 1, the lowest index of 63.
    • largest_index([]) returns -1, since the list is empty.
  5. smallest_index takes a list as its only parameter and returns the index of the smallest element in the list. If there are no elements in the list, this function returns -1. Examples:
    • smallest_index([60, 29, 82, 45]) returns 1, the index of 29.
    • smallest_index([45]) returns 0, the index of 45.
    • smallest_index([2, 63, 2, 63]) returns 0, the lowest index of 2.
    • smallest_index([]) returns -1, since the list is empty.
  6. find_element takes a list and an element (in that order) and returns the index of the first occurrence of the element in the list. If the element does not occur in the list or there are no elements in the list, this function returns -1. Examples:
    • find_element([60, 29, 82, 45], 60) returns 0, the index of 60.
    • find_element([60, 29, 82, 45], 82) returns 2, the index of 82.
    • find_element([60, 29, 29, 29], 29) returns 1, the first index where 29 occurs.
    • find_element([60, 29, 82, 45], 20) returns -1, since 20 is not in the list.
    • find_element([], 20) returns -1, since the list is empty.
  7. average takes a list as its only parameter and returns the average of the elements in the list. The returned average should be a float. If there are no elements in the list, return 0.0. Examples:
    • average([60, 29, 82, 45]) returns 54.0
    • average([45]) returns 45.0
    • average([2, 63, 2, 63]) returns 32.5
    • average([]) returns 0.0, since the list is empty
  8. insert_at_index takes a list, an element and an index (in that order) and returns a new list with the element inserted at the specified index. The index can be between 0 (inserted as the first element in the list) and the length of the list (inserted as the last element in the list). If position index is not valid, return the original list unchanged. Examples:
    • insert_at_index([60, 29, 82, 45], 18, 0) returns [18, 60, 29, 82, 45]
    • insert_at_index([60, 29, 82, 45], 18, 1) returns [60, 18, 29, 82, 45]
    • insert_at_index([60, 29, 82, 45], 18, 4) returns [60, 29, 82, 45, 18]
    • insert_at_index([60, 29, 82, 45], 18, 5) returns [60, 29, 82, 45] because 5 is an invalid index to insert at.
    • insert_at_index([60, 29, 82, 45], 18, -1) returns [60, 29, 82, 45] because -1 is an invalid index to insert at.
  9. remove_at_index takes a list and an index (in that order) and returns a new list with the element at the specified index removed. If the index is not valid, return the original list unchanged. Examples:
    • remove_at_index([60, 29, 82, 45], 0) returns [29, 82, 45]
    • remove_at_index([60, 29, 82, 45], 1) returns [60, 82, 45]
    • remove_at_index([60, 29, 82, 45], 5) returns [60, 29, 82, 45] because 5 is an invalid index.
    • remove_at_index([60, 29, 82, 45], -1) returns [60, 29, 82, 45] because -1 is an invalid index.
    • remove_at_index([], 0) returns [] because 0 is an invalid index.
  10. double_list takes a list as its only parameter and doubles every element in the list. This function does not create a new list, rather it modifies each element of the list. For example:
    >>> lst = [3, -2, 4, 22]
    >>> double_list(lst)
    >>> print(lst)
    [6, -4, 8, 44]
    >>> lst2 = []
    >>> double_list(lst2)
    >>> print(lst2)
    []
    
Here is an example of the program running. Your main does not have to follow this format exactly but it should test each of the functions you were required to write.
Enter positive integers that will be stored in a list.
Enter a number less than or equal to 0 to stop.

Enter a positive integer: 60
The list is now [60]
Enter a positive integer: 29
The list is now [60, 29]
Enter a positive integer: hello
That is not a valid integer.
Enter a positive integer: 82
The list is now [60, 29, 82]
Enter a positive integer: 45
The list is now [60, 29, 82, 45]
Enter a positive integer: -1
The original list is:
[60, 29, 82, 45]

The largest item in the list is 82
The position of this item is 2
The smallest item in the list is 29
The position of this item is 1

Enter an integer to search for: 29
This element was found at index 1

The average of the items is 54.0

The list with all the elements doubled is:
[120, 58, 164, 90]

Inserting element 97 at index 3 yields the list:
[120, 58, 164, 97, 90]

The list with the largest and smallest elements removed is:
[120, 97, 90]
Submit

Remember you may run handin21 as many times as you like. Each time you run it new versions of your files will be submitted. Running handin21 after you finish a program, after any major changes are made, and at the end of the day (before you log out) is a good habit to get into.