< Back

Final Exam

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 45 total points. You may 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. You should also follow all coding standards discussed thus far.

Final

Question 10

Create a file called question_10.py in your directory. Inside this file, write a function called cartesian_square(a_list). This function takes a list of values, and returns a list of tuples which represents the cartesian product of a_list with itself.

Cartesian Product of a list A with itself is defined as the list of ALL ordered pairs of the elements from A. 

  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)]

(10 points)

Question 11

Download the file linked_list.py, and save it into your test directory. Write a method called delete_duplicates(self), which removes all duplicates from the linked list. You may write any additional functions and methods as necessary. 

    #Test Case 1: No duplicates
    test_list = linked_list.LinkedList()
    for i in range(10):
        test_list.append(i)

    print(test_list) #head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> None
    test_list.delete_duplicates()
    print(test_list) #head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> None

    #Test Case 2: duplicates side by side
    test_list = linked_list.LinkedList()
    for i in range(5):
        test_list.append(i)
        test_list.append(i)

    print(test_list) #head -> 4 -> 4 -> 3 -> 3 -> 2 -> 2 -> 1 -> 1 -> 0 -> 0 -> None
    test_list.delete_duplicates() 
    print(test_list) #head -> 4 -> 3 -> 2 -> 1 -> 0 -> None
    
    #Test Case 3: duplicates elsewhere in the list
    test_list = linked_list.LinkedList()

    for i in range(5):
        test_list.append(i)

    for i in range(4, -1, -1):
        test_list.append(i)

    print(test_list) #head -> 0 -> 1 -> 2 -> 3 -> 4 -> 4 -> 3 -> 2 -> 1 -> 0 -> None
    test_list.delete_duplicates()
    print(test_list) #head -> 0 -> 1 -> 2 -> 3 -> 4 -> None

(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.

An 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

(10 points)

Question 13

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_13.py. This function should take a binary tree as a parameter, and recursively determine whether the tree is a complete binary tree.

YOU WILL NEED A HELPER FUNCTION FOR THIS

 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

(15 points)

 

Challenge

For this bonus question, you will be adding to the graph.py class.

In graph theory, a hamiltonian cycle is a set of edges that visits each vertex exactly once, and the start vertex and end vertex are connected by an edge. Add a method to the graph class called has_hamiltonian, which returns True if a hamiltonian cycle exists in the graph. You may need to write a helper function.

Note: You will likely need to use backtracking to solve this problem.

A collection of test cases can be found here. 

import graph

my_graph = graph.Graph("sample_graphs/simple_graph")
print(my_graph.has_hamiltonian()) #True

my_graph = graph.Graph("sample_graphs/line_graph")
print(my_graph.has_hamiltonian()) #False

my_graph = graph.Graph("sample_graphs/cycle_graph")
print(my_graph.has_hamiltonian()) #True

my_graph = graph.Graph("sample_graphs/simple_non_path")
print(my_graph.has_hamiltonian()) #False

my_graph = graph.Graph("sample_graphs/complex_non")
print(my_graph.has_hamiltonian()) #False

my_graph = graph.Graph("sample_graphs/dodecahedron")
print(my_graph.has_hamiltonian()) #True

(5 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 \( \pm \frac{\pi}{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)

(5 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 inquire.roanoke.edu. You should see an available assignment called Final Exam.