< 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 28 total points. You may only access this webpage, 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_square(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)]

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

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

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