Lab Exercise #5 Solution

Python provides several simple and powerful mechanisms to structure data. The list is a vital example that enables us to manipulate and reason with ordered collections. We can use an ordered collection (list) to represent and store numerical information (test scores, daily temperature measurements, time-ordered experimental results, and the like). We can also represent more abstract things like decks of cards and traffic patterns. In this lab, you will explore several problems that utilize lists.

 

 

Like Alice Through the Looking Glass

Mutability refers to the ability to change something. So far, most of the things we've seen are immutable… they can't be changed. "But what do you mean?" you ask, "we've been changing variables all the time!". Yes you have. The variables you're using are changing (that's why we call them 'variable'… duh) But the objects your variables have been referring to are not! Numbers, strings, and tuples in Python are immutable. They can't be changed, only created or destroyed. So then, what exactly does a variable contain? A variable contains a reference to an object. Let's explore this a bit. First, set up a couple of simple variables:

 

var1 = 0 <ENTER

var2 = 0 <ENTER

 

 

This looks like var1 contains the value zero as does var2. In a way, they do, but they really

don’t contain any values at all. To see this, let's use the Python id() function:

 

id(var1) <ENTER

id(var2) <ENTER

 

They both have the same identifier… they are both names for the same thing! namely the "integer object identified as nnnn with the value 0". So what happens if we change the 'value' of var2?

 

var2 = 6 <ENTER

id(var1) <ENTER

id(var2) <ENTER

 

var2 has changed. It now points to (references) a different object… an integer object with the

value 6.

 

 

This is a very subtle, but important thing to understand. Python maintains values in objects (recall that every object has a unique identifier, a type and a value). Variables do not contain values, they contain references… the identifiers of the objects they point to. When you change the 'value' of a variable that is bound to an immutable object, a new object is created (if not already in existence) and the variable binding is updated to reference the new object.

So far, all of this detail hasn't mattered much. This is because numbers (integers, floats, complex)

and strings are immutable, so worrying about where the value is stored doesn't really trouble us.

 

But Python list objects are mutable. They can be changed! This means that the object itself is updated. Let's look at one way in which this may cause issues. Start by creating a simple list:

 

 

mylist = [1,2,3,4] <ENTER

list1 = mylist*3 <ENTER

list1 <ENTER

 

 

That looks like we might expect… a list consisting of 3 copies of mylist. Now let's change one of the list1 values:

 

 

list1[2] = 55 <ENTER

list1 <ENTER

 

 

All is well. The third list1 element has been changed as we expected (actually, the reference to the object in the list has been changed) Now let's create another list in similar fashion:

 

 

list2 = [mylist]*3 <ENTER  # be sure to put brackets around

[mylist]

list2 <ENTER

 

 

hmm… this looks a little different. That's because it is different. It's actually a list of 3 lists. Now try to change the second element as before:

 

list2[2] = 55 <ENTER

 

 

oops… the element at list2[2] was another list. We just replaced it with a single value (55). But now for the weird part:

 

 

mylist[2] = 99 <ENTER

list2

 

 

Oh my! We changed an element in mylist and suddenly list2 was altered as well! We didn’t do anything to list2 (explicitly anyway). We'd better check to see if list1 suffered a similar fate:

 

 

list1 <ENTER

 

Why didn't list1 change as well?! The answer to all of this lies in the fact that lists 1) do not contain values, they contain references that point to things and 2) lists are mutable. In the first example, list1 actually contains the identifiers of the individual immutable numeric objects (1,

2, 3 and 4) whereas the second list (because we surrounded mylist with square brackets when we created list2) contains three references (pointers) to mylist. When mylist is subsequently changed, the references still point to the original object (mylist) which is no longer the same… it’s been changed!

 

Try this:

 

 

id(mylist) <ENTER

id(list2[0]) <ENTER

id(list2[2]) <ENTER

 

 

What do you notice? Explain to one of your TAs why this is the case.

 

 

Warm -up

 

 

1) Histograms

Write a program that will simulate the tossing of two dice and keep track of the occurrence frequency of each two-die sum (2...12). You should generate 10,000 pairs of separate random integers in the range 1 through 6 and, using a list of integer counters, determine the number of times each two-die sum occurs. After 10,000 simulated "rolls" of the dice, output the totals for each possible outcome. [Hint: consider simply using the dice total to index the list of counts]

 

After 10,000 simulated “rolls” of the dice, print the total for each possible outcome as shown below:

 

2: 1284

3: 2556

.

.

.

12: 1568

 

where each of the dice totals (the left column) is printed using format with a field of width two, and the counts (the rightmost column) are printed using format with a field of width five.

 

 

An example of using format() to generate a field of width five is given below:

 

format(8,“5d”)

“     8”

 

(Note that the quotes around the 8 in the last line of output won’t actually appear –this is just to illustrate that five blank spaces have been added in front of 8).

 

Theoretically, 7 is the most likely outcome. Does your histogram support this?

Stretch

 

 

1) . List Construction

Write a Python program that repeatedly prompts the user to enter a word (a string) and stores the words into a list, storing each word in the list only if the first letter of that word occurs again elsewhere in the word (e.g., in the word "Baboon", the first letter, “b”, also appears as the third letter, so "Baboon"

should be stored in the list of words). The words should be case-insensitive, so use myString.lower().

Continue entering words until the user enters a null string, "", at which point your program should print the elements stored in the list, one word per line.

 

 

2) Find the Smallest Number

Write a pure function, minimumIndex, that takes in a list of nonnegative integers (n ≥ 0) and a starting index, and then returns the index of the minimum value in the part of the list from the starting index to the end of the list (including the value at the starting index). Note that the index you return should be numbered with respect to the original list, not the smaller list slice. If there are duplicate minimum values, return only the index of the first occurrence.

 

 

A sample output is shown below:

 

 

minimumIndex([9, 1, 7, 6, 8], 2)

3

 

 

Where  [9,1,7,6,8] is the list and 2 is the starting index. We could see that the minimum of the list from index  2 to the end is number 6, which is positioned at index 3 in the list.

 

 

Do not use any Python built-in functions to search for the minimum integer in the list.

 

 

Hint: Use a variable to keep track of the current minimum index.

 

 

Workout

 

 

1) . Selection Sort

Sorting a list of objects "in place" (without the use of an additional list structure) is an important

Computer Science problem that has been extensively studied. One of the simplest methods is known as selection-sort. The selection-sort algorithm is relatively easy to understand and implement, but it is not very efficient because it takes roughly n2 operations on a list with n elements. The selection-sort algorithm is as follows:

 

 

Given a list of integers 0 to 9, inclusive, e.g.:

 

 

3 5 2 8 9 1

determine the smallest element in the list and swap it with the first element, then repeat the process for the remaining elements in the list. When you've completed the entire list, it will be sorted in ascending order of value:

Current List: [3 5 2 8 9 1]
Minimum of [3 5 3 8 9 1] is 1, at index 5
Swap values at index 0 and 5
Current List: 1 [5 2 8 9 3]
Minimum of [5 2 8 9 3] is 2, at index 2
Swap values at index 1 and 2
Current List: 1 2 [5 8 9 3]
Minimum of [5 8 9 3] is 3, at index 5
Swap values at index 2 and 5
Current List: 1 2 3 [8 9 5]
Minimum of [8 9 5] is 5, at index 5
Swap values at index 3 and 5
Current List: 1 2 3 5 [9 8]
Minimum of [9 8] is 8, at index 5
Swap values at index 4 and 5
Current List: 1 2 3 5 8 [9]
Done, list is sorted!
 
 

 

Write a Python program that will implement the selection-sort algorithm to sort an integer array in ascending order. To complete this section, your program MUST do the following:

 

 

1.   Have the user input a string of integers from 0 to 9 separated by spaces (e.g. “9 3 5 4”).

 

2.   Use the split()method to turn the string of integers entered by the user into a list.

 

3.   Convert each element of the list into an integer.

 

4.   Use your minimumIndex function from Stretch 2 portion of the lab to identify the location of the minimum of the unsorted list.

5.   Finally, print the contents of the sorted list iteratively but in the same line using: print(number,

end = “ ”)

 

 

For this lab, do not use Python’s built-in sort(), min() or anything that directly sorts or finds the index of the elements in the list list methods other than your own functions.

 

Reach out to your TAs if you need help in any step of the way.

 

Remember to check in with a TA when you have completed this portion of the lab.

 

Challenge

 

Try these challenge problems if you have extra time or would like additional practice outside of lab.

 

1) Exponent Function xy

 

 

Using only one nested for loop and the + operator (* and ** are NOT allowed), write a pure function expo that takes in two positive integer arguments x (the base, or number to be raised to a power) and y (the exponent) and returns the value of xy. The code is short, but you need to think carefully about the logic in implementing it. A sample output is provided to calculate 34 below:

 

 

expo(3,4)

81

 

2) English to Pig Latin Translator

Write a Python program that will translate an English word or phrase into Pig Latin. Pig Latin is a fun word game in which words are translated according to the following "rules":

 

 

1.  For any word that begins with one or more consonants (the letter y is considered a consonant):

move the consonants to the end of the word and append the string 'ay'.

2.  For words that begin instead with a vowel, append the string 'way' to the end. For example, the phrase "Can you speak pig latin?" would be translated:

 

"Ancay ouyay eakspay igpay atinlay?"

 

 

Or, "An apple a day keeps the doctor away" would be translated:

 

"Anway appleway away ayday eepskay ethay octorday awayway"

 

Your translator should preserve any punctuation and capitalization of words (see examples). For this exercise, you can assume that words will be separated by at least one space.