$ 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']
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
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