Instructors: Ten Bradley and Armin Jamshidpey
Due date: July 8, 2020 at 5:00pm
Coverage: Modules 5, and 6
This assignment consists of a programming and written component. Please read the course website carefully to ensure that you submit each component correctly. Assignment solutions are to be submitted to Markus.
Topics: Trees and Graph Interface
1 Programming Component
1. (10 marks) Using the given Contiguous class, implement the class BinaryTree using details from lectures.
In particular, use the following details:
The root of the Binary Tree will be stored at index 0 of the Contiguous.
Given that a node is stored at index i:
{ The left child is stored at 2i+1.
{ The right child is stored at 2i+2.
{ The parent is stored at (i – 1)=2.
{ The Contiguous has size at least 64.
If a tree node at a given index does not exist, None is stored at that index.
Submit your implementation as binaryTreeContiguous.py.
2. (10 marks) Using the given BinaryNode class, implement the class BinaryTree using details from lecture.
In particular, use the following details:
BinaryTree has a field root that store None if the tree is empty. Otherwise, it stores a BinaryNode.
If a node does not have a parent node, the parent of the node is None.
If a node does not have a left child, the left child is None.
If a node does not have a right child, the right child is None.
Submit your implementation as binaryTreeLinked.py.
3. (5 marks) As a user of the Binary Tree class, write the function traversal(BinaryTree) that consumes a binary tree and returns a contiguous array containing the items in BinaryTree in in-order traversal order.
Your implementation of traversal must be able to be used to traverse any BinaryTree that matches the interface given for P1 and P2.
Submit your implementation as traversal.py.
Written component on the next page.
2 Written Component
1. Given the following binary tree, answer the following questions.
(a) (2 marks) Draw how the tree would be stored using linked memory.
(b) (2 marks) Draw how the tree would be stored using contiguous memory.
(c) Consider a binary tree that has n nodes stored similarly to the given binary tree, i.e. one node is stored per level. Answer the following questions.
i. (2 marks) In terms of O-notation, how much memory is required to store the n nodes when using linked memory Justify your answer.
ii. (2 marks) In terms of O-notation, how much memory is required to store the n nodes when using contiguous memory Justify your answer.
iii. (2 marks) A tree with very few nodes per level is called a sparse tree. Considering the memory required for linked and contiguous implementations, which implementation would you choose if you know you are storing a sparse tree Justify your answer.
2. (5 marks) Within an undirected simple graph with 2 or more vertices, there are always at least two vertices with the same degree.
Write pseudocode for the function same degree(G), that consumes an undirected simple graph and returns the most common degree in the graph.
Use the interfaces for Undirected Graph given at the end of this assignment.
Hint: consider using ADTs we have previously learned to store data.
3. (10 marks) One definition for a tree is a graph with no cycles. Based on that definition, we can write a function
Tree To Graph that takes an Unordered Tree as a parameter and returns an Undirected Graph.
Write pseudocode for the function which will create a new instance of an Undirected Graph. All the nodes from the Unordered Tree will be represented as vertices in the graph, and relationships between a node, such as a parent and child node, will be represented as an edge. You may assume that all values stored in the tree are unique.
Use the interfaces for Unordered Tree and Undirected Graph given at the end of this assignment.
3 ADT Interfaces
3.1 BinaryTree Interface
A NodeID is a unique identified for each node in a Binary Tree. Preconditions:
For value, parent, left child, right child, set value, ID is a valid NodeID in self.
For add leaf, ParentID is a valid NodeID in self and Side is Left” or Right”, or ParentID is None and Side is
“”.
