$ mkdir ~/cs170/labs/lab26 $ cd ~/cs170/labs/lab26
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.
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, 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.
Create a file called radix.py in your directory. In this
file, create a function radix_sort(a_list),
which takes a list of . 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 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.
>>> print(radix_sort(["0001", "2030", "0122", "0002", "1203", "0333"])) ['0001', '0002', '0122', '0333', '1203', '2030']
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.
The above definition of Radix sort is really Least Significant Digit 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.
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.
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 [ +, -, *, / ]
>>> evaluate_postfix("2 3 *")
6
>>> evaluate_postfix("1 2 3 * -")
-5
>>> evaluate_postfix("1 2 + 3 * 4 /") #((1 + 2) * 3) / 4
2.25
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.
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:
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.
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.
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
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.
>>> 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)] >>>
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.
>>> 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