CPSC 170 A

- Location
- Trexler 363
- Times
- MWF 3:30 - 5:30

- Office Hours
- M-Th 6 - 7pm
- Office
- Trexler 365B
- chssmith AT roanoke DOT edu

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

### Question 10

### Question 11

### Question 12

### Challenge

### Challenge

#### Submission

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

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)

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)

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

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)

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)

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)

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`

.