MA214 Algorithms and Data Structures
2023/24
Exercises 7
(DFS, BFS, binary search trees)
Exercise 7.1. Depth-First Search 3 pts
Recall the Depth-First Search (DFS) algorithm and the pseudocode on this week’s lec-ture slides. Implement this algorithm in Python using our implementation of graphs in Graphs.py. Call the two functions DFS and DFSVisit. Use the template DFS.py provided on Moodle.
Exercise 7.2. Wrestlers 3 pts
There are two groups of professional wrestlers:“babyfaces” (“good guys”) and “heels” (“bad guys”). Our goal is to assign n professional wrestlers to these two groups under the following constraints. Between any pair of professional wrestlers, there may or may not be a rivalry. We have a list of the r pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform. such a designation, your algorithm should produce it.
Exercise 7.3. Binary Search Trees 4 pts
In this question, you are asked to implement a binary search tree (See Chapter 12 in the course textbook). A binary search tree is organised in the form. of a binary tree, where each node stores a value attribute (say, an integer) and two links, to the left and the right child of the current node. Both children of a leaf node are None. In addition, a binary search tree satisfies the following property:
• Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.value≤x.value. If y is a node in the right subtree of x, then y.value>x.value. (Here we broke the ties towards the left, differently from the textbook.)
On the moodle page is a template BST.py for a binary search tree implementation. Please use this template for completing the questions below. Here is an excerpt from this template.
1 class Node :
2 def __init__ ( self , val , par ) :
3 self . left = None
4 self . right = None
5 self . parent = par
6 self . value = val
7
8 class BinarySearchTree :
9 def __init__ ( self ) :
10 self . root = None
11
12 # returns the minimum (in the left - most item );
13 # returns None if the tree is empty
14 def min( self ) :
15 # Part (a)
16
17 # inserts x in the tree unless present ;
18 # returns pointer to Node with value x
19 def insert ( self , x ) :
20 # Part (b)
21
22 # returns Node with value x in the tree ;
23 # if not present , returns None
24 def find ( self , x ) :
25 # Part (c)
(a) Implement a Python function min() that returns the minimim value stored in the current binary search tree.
(b) Implement a Python function insert(x) that inserts the value x into the binary search tree (unless already existent) and returns a pointer to the Node with value x.
(c) Implement a Python function find(x) that finds the value x in the binary search tree and returns a pointer to the Node containing it (if it exists). If x is not present in the tree, then it returns None.