Lecture 37 - Test

If you do not currently have a directory for tests, create one in your cs170 directory, and also create a directory for the final. 

$ mkdir ~/cs170/tests
$ mkdir ~/cs170/tests/final
$ cd ~/cs170/test/final

This portion of the test is worth 35 total points. You may reference any files within your directory. You may only access the Python documentation website and the tkinter documentation website. NO OTHER WEBSITES ARE PERMITTED. As usual, you are not allowed to directly copy any code from the Internet or another individual without citation. You should also follow all coding standards discussed thus far.

Final

Question 10

Download the file queue.py, and save it into your test directory. Write a function called reverse_queue(a_queue) in a file called question_10.py. This function should take a queue as a parameter, and modify the queue so that all of the elements are now in reverse order. You may use any additional data structures necessary. 

>>> my_queue = queue.Queue()
>>> for i in range(10):
...     my_queue.enqueue(i)
>>> print(my_queue)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> reverse_queue(my_queue)
>>> print(my_queue)
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

(10 points)

Question 11

Download the file tree.py, and save it into your test directory. Write a function called is_complete_binary_tree(a_binary_tree) in a file called question_11.py. This function should take a binary tree as a parameter, and recursively determine whether the tree is a complete binary tree order.

YOU WILL NEED A HELPER FUNCTION FOR THIS

Remember, a tree is a complete binary tree if every node has 0 children, just a left child, or has both children. 

>>> my_tree = tree.BinaryTree()
>>> my_tree.insert(5)
>>> my_tree.insert(3)
>>> my_tree.insert(2)
>>> my_tree.insert(4)
>>> my_tree.insert(7)
>>> my_tree.insert(6)
>>> print(is_complete_binary_tree(my_tree))
True
>>> my_tree.root.right.left = None
>>> my_tree.root.right.right = my_tree._Node(6)
>>> print(is_complete_binary_tree(my_tree))
False

(10 points)

Question 12

Download the graph.py file into your test directory. In a file called question_12.py, write a function called is_connected(a_graph), which returns True if the specified undirected graph is connected.

Recall that a undirected graph is connected if every vertex appears in a depth first traversal of the graph, irrelevant of the starting position. Write a function called depth_first(a_graph, curr_vertex, visited_list), which adds all of the verticies that can be reached from curr_vertex to the visited list.

exam_sample.in 
>>> my_graph = graph.Graph("exam_sample.in")
>>> print(is_connected(my_graph))
True
>>> my_graph.adjacency_matrix[2][4] = 0
>>> print(is_connected(my_graph))
False

(15 points)

 

Challenge

In your question_9.py file, write a function is_binary_search_tree(a_binary_tree). This method takes a binary tree as input and returns True if the provided tree is a binary search tree.

Recall that a binary tree is a binary search tree if the entire left sub-tree is less than or equal to the root, and if the entire right sub-tree is greater than the root. This must be true for all nodes in the tree.

(8 points)

 

Challenge

In a file called bonus.py, write a function called draw_recursive_tree(curr_point, curr_length, curr_angle). This method takes a tuple of integers (x, y), a positive integer, and an angle in radians. This method should use Tk to draw a fractal tree.

A fractal tree can be drawn by drawing a line from curr_point to the point curr_length distance away at angle curr_angle. from this new point, recursively draw a line at angle ± π / 4 from the current angle, with half the length. Continue doing this until the curr_length is 1.

The following image is what a tree looks like, if DIMS = 400, and the following statement is executed: 

	draw_recursive_tree((DIMS // 2, DIMS), DIMS // 2, math.pi / 2)

(8 points)

Submission

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

cd ~/cs170/tests
tar czvf final.tgz final/

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

Last modified: Fri Mar 21 12:35:54 EDT 2014