$ mkdir ~/cs170/labs/lab23 $ cd ~/cs170/labs/lab23
, I'm not really going to have the opportunity to perform a demonstration of your next assignment on Friday. We'll start off today with a brief demo, so you can get an idea of what to expect on Friday once the official assignment description gets posted.
In addition to the written portion of the test, there will be a coding portion. This will be done on the computers. For practice, attempt the following exercises in a file called test_review.py, alone:
Write a function recursive_search, which takes
a linked list node as a parameter, and an item being
searched for. It will return True if the item is in the
linked list, and False otherwise. You must use
recursion for this exercise
>>> my_linked_list = linked_list.LinkedList() >>> for i in range(20, -1, -1): ... my_linked_list.append(i) >>> print(recursive_search(my_linked_list.head, 0)) True >>> print(recursive_search(my_linked_list.head, -1)) False >>> print(recursive_search(my_linked_list.head, 20)) True >>> print(recursive_search(my_linked_list.head, 21)) False
Write a function binary_recursive, which performs a
binary search on a Python list. This function will take two
parameters: a sorted python list and an element being searched for. It
should return True if the element is in the list, and
False otherwise. Recall that binary search
compares the middle element of the list to the item being searched
for. If they are equal, you are done. If item is greater than
middle, search the right half of the list. Otherwise, search the
left half.
>>> my_list = list(range(20)) >>> print(binary_recursive(my_list, 1)) True >>> print(binary_recursive(my_list, 10)) True >>> print(binary_recursive(my_list, -1)) False >>> print(binary_recursive(my_list, 21)) False
The Cantor Ternary Set is a mathematical set that is both infinitely sparse and infinitely dense. The idea of the Cantor Set is simple: Take a line segment from start to end on the number line. Delete the middle third of the line segment, to create two line segments. You can then recursively call the cantor procedure on each of these line segments.
Write a function cantor(start, end, depth), which
takes as parameters three integers: the starting point of the
current line, the ending point of the current line, and how deep
you want to go. It should return a list of tuples, representing
the line segments that form the cantor set. Notice that this
function must count down to 0, instead of counting up to some
pre-defined maximum.
>>> print(cantor(0, 1, 0))
[(0, 1)]
>>> print(cantor(0, 1, 1))
[(0, 0.3333333333333333), (0.6666666666666666, 1)]
>>> print(cantor(0, 1, 2))
[(0, 0.1111111111111111), (0.2222222222222222, 0.3333333333333333),
(0.6666666666666666, 0.7777777777777778), (0.8888888888888888, 1)]
>>> print(cantor(0, 1, 3))
[(0, 0.037037037037037035), (0.07407407407407407, 0.1111111111111111),
(0.2222222222222222, 0.2592592592592593), (0.2962962962962963,
0.3333333333333333), (0.6666666666666666, 0.7037037037037037),
(0.7407407407407407, 0.7777777777777778), (0.8888888888888888,
0.925925925925926), (0.962962962962963, 1)]
While it might sound like a dull activity, but determining if a string contains a set of balanced parenthesis is a very important job. Emacs does this for you, so does Mathematica and even Microsoft Office. We need something like this in Emacs or Mathematica to help catch our silly errors, like forgetting to close a parenthesis on a nested function call, for example.
While it might seem like counting is the most straight forward approach to this, it is not a complete solution. The better solution is to use a stack to determine whether the parenthesis are balanced or not.
In a file called parens.py, write a function called
is_balanced(a_string), which takes a single string as a
parameter. This function should return True if the
parenthesis in the string are balanced, and False if they are
not. Your function will need to use a Stack to accomplish this, so
make sure you copy your stack class from last lab to this directory:
$ cd ~/cs170/labs/lab23 $ cp ../lab22/stack.py . $ cp ../lab22/linked_list.py .
>>> print(is_balanced("()"))
True
>>> print(is_balanced("(")))
False
>>> print(is_balanced(")("))
False
>>> print(is_balanced("(a)"))
True
>>> print(is_balanced("((()(((())))))"))
True
The algorithm for this is straight forward: When you see an open parenthesis, push it onto the stack. When you see a closing parenthesis, pop it from the stack. If you reach the end of the string and the stack is empty, you know the parenthesis are balanced. If you ever try to pop from an empty stack, or you reach the end of the string and the stack is not empty, you know the parenthesis are not balanced.
Of course, we can use more than just traditional parenthesis in
order to break up some mathematical equation. We commonly use
square brackets ("["), and sometimes even curly braces ("{") as
well. Write a function is_balanced_multi, which
accounts for all three of these tokens.
When you have finished, create a tar file of your lab23
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab23.tgz lab23/
To submit your activity, go to cseval.roanoke.edu. You should
see an available assignment called Lab Assignment 23.
Make sure you include a header listing the authors of the file.