Lecture 26 - Abstract Data Types


As usual, create a directory to hold today's activities:

$ mkdir ~/cs170/labs/lab26
$ cd ~/cs170/labs/lab26

Test Discussion

Average
65
Standard Deviation
25
Range
86

Abstract Data Type

We have been using linked lists to implement out stacks and queues. However, Stacks and Queues are not data types completely restricted to linked lists. Stacks and Queues are classifications of data types: Anything that implements their interface can call themselves a Stack or a Queue. I'll show you how this works today in lecture, so you can use them for today's lab activities.


Lab Activity 1
Radix Sort

We have discussed a handful of general sorting techniques up to this point. However, there are a couple of sorting techniques that only work on certain classes of data. For example, Pigeonhole Sort requires knowledge of the range of data. Another type of sort is called Radix sort, which can only sort integers. What is really interesting about radix sort is that it is one of the few non-comparison based integer sorting techniques.

Details

Create a file called radix.py in your directory. In this file, create a function radix_sort(a_list), which takes a list of strings. These strings are going to represent integer numbers, where the strings are padded with 0's. For example, if the number "1000" is in a_list, the number 23 is represented as "0023". This function should return a sorted version of a_list.

In radix sort, all of the "numbers" are placed in a queue based on the order they are encountered. The queue they are placed in is based on the digits place being examined. You will start from the least significant bit (the right most digit in the string), and place it into the appropriate queue based on that number. For example, for the first iteration of radix sort, the number "064" would be placed in a queue for the the digit '4', while the number "101" would be placed in the queue for the digit '1'.

After you have enqueued all of the items from the original list into the queues, you sequentially dequeue all of the queues in increasing order back into the main list. You then repeat this process for the next digit in the string, until you run out of digits. The resulting list will be a sorted copy of the list.

When you have this written out, make sure you think about the Big-Oh class of radix sort. Write your Big-Oh estimate in a comment in your radix.py file.

Example

>>> print(radix_sort(["0001", "2030", "0122", "0002", "1203", "0333"]))
['0001', '0002', '0122', '0333', '1203', '2030']

Hint

  • For radix sort, you will want to create a list of 10 queues, one for each digit. All of these queues will start off empty. You could use a dictionary, but since you know the strings you have represent integers your sort will be faster if you use just a list.

  • Remember, Strings are simply a special form of a list. You can get a specific character from the string using the [] operator, just like you would on a list. You can even specify negative values, which might make your code a little easier to write.

  • When you have put all of the values into the queues, you need to iterate over your list of queues, dequeueing them until they are empty. You will place the dequeued values into a list, so that you can process the next digits of them.

 

Challenge

The above definition of Radix sort is really Least Significant Digit (LSD) Radix Sort. The other type of Radix sort is Most Significant Digit (MSD) Radix sort, which can be used to sort strings. This function doesn't use a queue, instead it uses recursion!

Write a function msd_radix_sort(a_list, current_index), which takes a list of strings as input, and an integer representing the current digit being explored. These strings will be only lowercase, alphabetic strings. Your function should return a sorted copy of the input a_list.

MSD Radix sort places the input lists into buckets, then recursively sorts those buckets using the next character of the strings. Then, you just concatenate the lists back together to get the sorted version of the list.


Lab Assignment 26
Postfix Evaluation

We are used to what is know as in-fix notation for mathematical operators. In-fix notation requires the operator to appear between its operands. However, there is a bit of a hitch when dealing with precedence: What order do you do the operations in. We have "PEMDAS" precedence rules. However, writing a program to follow those rules is actually a little difficult.

Luckily, there is another notation that we can use to simplify these conditions. This notation is known as post-fix notation, where the operator appears directly after its operands. Using this notation and a Stack, we can un-ambiguously evaluate any expression without the need of silly parenthesis.

Details

Create a file called post_fix.py in your directory. In this file, create a function called evaluate_postfix(a_postfix_string). This function takes a string of operations defined in post-fix order, and evaluates the operations specified in the string.

A post-fix encoded string is of the form "2 3 *", where 2 and 3 are the operands for the operator "*". A post-fix encoded string of "1 2 3 * -" encodes the infix notation of "1 - ( 2 * 3 )". You only need to handle the 4 main operators [ +, -, *, / ]

Example

  >>> evaluate_postfix("2 3 *")
  6
  >>> evaluate_postfix("1 2 3 * -")
  -5
  >>> evaluate_postfix("1 2 + 3 * 4 /") #((1 + 2) * 3) / 4
  2.25

Hint

  • You are going to need to split the input string up. use the split method of strings to split on the spaces. And make sure you input strings all have spaces in the appropriate places.

  • You are going to iterate of the list of tokens from the string, to determine the operands for an operator. If you see a number in the list, simply push it onto the top of your stack. If you see an operator, simply pop the two items from the top of the stack. These are the second and first operands, respectively. Make sure to push the result of that operation onto the stack.

  • You do not need to handle the special cases of if there are not enough items on the stack. You can assume all of the input is properly formatted. However, you should make sure that any properly formatted string does work in your code.

 

Challenge

Converting from in-fix to post-fix is a little bit of a pain. However, so is converting from in-fix to post-fix in code. While the evaluation of post-fix can ignore precedence levels and parenthesis, you actually have to account for them in the conversion. The code for this again uses a Stack.

You are going to tokenize a string of the form "( 1 + 2 ) * 3 / 4". Notice the spacing, especially around the parenthesis. This is to make life easier. The rules are as follows:

  1. If the token you have is an operand, append it to the end of your string,
  2. If the token is a left parenthesis, push it onto your stack.
  3. If the token is a right parenthesis, pop the stack until you find the first left parenthesis. Append every operator you find on the stack between them.
  4. If the token is an operator, push it on the stack. First, however, remove any operator that has a higher or equal precedence level and append it to the end of the string.
  5. When you reach the end of the input string, make sure you append all remaining operators onto the output string.

Write a function called convert_to_postfix(infix_string), which takes as input an infix notation string and returns a string representing the postfix notation, using the above algorithm.


Submission

When you have finished, create a tar file of your lab26 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab26.tgz lab26/

To submit your activity, go to cseval.roanoke.edu. You should see an available assignment called Lab Assignment 26. Make sure you include a header listing the authors of the file.


In-Class Notes


Homework Problems

Each week until the end of the semester, I will give out 2 - 3 additional (short) programming activities to be completed on your own time. These will not be graded. However, these will be invaluable as study aids for the programming portion of the final. Be prepared to get "Have you tried <insert homework program here>?" as an answer to future questions.

For consistency sakes, you might want to keep these separate from your other files. Create a directory called week10_homework, which will hold your homework for this week:

$ cd ~/cs170/
$ mkdir week10_homework
$ cd week10_homework

Problem 1

Cartesian Product

Write a function cartesian_product(a_list), which takes a list as a parameter. This function should return a list, which is the cartesian product of the input list with itself.

Recall that the typical definition of cartesian product takes two lists as input. It produces a set of all possible parings between the two lists. Your function should only take one list as a parameter. It is straight forward to write this using a loop. You should attempt to solve this problem recursively.

Example

>>> my_list = [0, 1, 2, 3]
>>> print(cartesian_product(my_list))
[(3, 3), (2, 2), (2, 3), (3, 2), (1, 1), (1, 2), (2, 1), (1, 3), (3, 1),
 (0, 0), (0, 1), (1, 0), (0, 2), (2, 0), (0, 3), (3, 0)]
>>>

Problem 2

Sieve of Eratosthenes

Write a function eratosthenes(max_prime), which takes a single integer as a parameter. This integer is going to specify the largest integer to check for primality. This function should return a linked list of all of the prime numbers between 2 and max_prime, inclusive.

The Sieve of Eratostheses starts out with a list of all of the integers in the range 2 to max_prime. To find the next prime, you simply remove the head element, and also remove all of the multiples of that number from the list. For the first iteration, 2 is the first prime, and all multiples of 2 are removed from the list. Then, you remove the next element from the head of the list (which will be 3). This is the next prime. Then you remove all multiples of 3 from the list. This continues until the starting list is empty, leaving you with a list of all of the primes.

Example

>>> print(eratostheses(10))
head -> 7 -> 5 -> 3 -> 2 -> None
>>> print(eratostheses(50))
head -> 47 -> 43 -> 41 -> 37 -> 31 -> 29 -> 23 -> 19 -> 17 -> 13 -> 11 -> 7 -> 5 -> 3 -> 2 -> None

Last modified: Wed Mar 26 14:42:03 EDT 2014