Binary Trees

Consider the BinaryTreeNode class shown below. public class

BinaryTreeNode {

public Object element;

public BinaryTreeNode left;

public BinaryTreeNode right;

public BinaryTreeNode(Object element) {

this.element = element;

this.left = null;

this.right = null;

}

public void add(Object element) {

BinaryTreeNode node = new BinaryTreeNode(element); if (left == null)

left = node;

else if (right == null) right = node;

else if (left.size() < right.size())

left.add(element);

else right.add(element);

}

public int size() {

int size = 1;

if (left != null) size += left.size();

if (right != null) size += right.size();

return size;

} }

(a) Draw a diagram of the tree resulting from setting the root to be

BinaryTreeNode(“a”), and subsequently using the add method to add “b”,

“c”, “d”, “e”, “f”, “g” to the root in that order.

2. (b) Taking into account that both size() and add() are implemented

recursively and that add() calls size(), derive an informal estimate of the

time complexity for the add() method.

3. (c) Consider how you might improve the efficiency of the add() and

size() methods with respect to time by storing the size as an attribute of

the class. Explain your new design and detail the changes you would make to

the BinaryTreeNode class and its methods.

4. (d) Explain whether the changes you have made in part (c) above alter the

time complexity of the add() method. If not, why not, if so, what is the new

time complexity and why.

3. Grammars and parsing

1. (a) Grammar descriptions often include “one or more” and “zero or more”

patterns. Give an example of a grammar containing a “one or more” pattern,

and show how the same pattern can be implemented using explicit recursion.

What does this result suggest to you: Is this extra syntax needed? Why? (Or

why not?)

2. (b) Consider the following fragment of a grammar for a Java-like language:

method = mod type IDENTIFIER OPEN args CLOSE

block

mod = visibility STATIC?

visibility = PUBLIC | PROTECTED | PRIVATE

args = type IDENTIFIER (COMMA args)?

(where symbols in CAPITALS denote terminals). Explain how you would

implement a parser for this grammar using recursive descent. Illustrate your

answer using pseudo-code to implement the method and args

productions. (You may assume that you already have recogniser functions for

all the other symbols, and can create any additional functions you need.)

3. (c) Suppose you now decided to implement terminal recognisers directly

from the string representing the program text, rather than performing

tokenisation to get a stream of tokens. How would you go about it? How

would you keep track of “where you are” in parsing the input? What would

the terminal recognisers look like (in pseudocode)?

4. Graphs, complexity, and data structure management

1. (a) One of the major pitfalls in designing algorithms such as breadth-first

traverses that operate on graphs is ensuring that they always terminate.

Explain (with an example) how this problem arises, and explain in detail how

to ensure that a traverse of graphs avoids divergence.

2. (b) Dijkstra’s algorithm works by storing a distance for each node in the

graph. Compare and contrast the following two approaches to representing

the distance:

1. (i) As an attribute on the class representing nodes; and

2. (ii) As a lookup table mapping node labels to distances.

Explain carefully any assumptions you make and any restrictions that you

need to impose.

3. (c) Suppose you decide to use the adjacency matrix representation of a

graph. Discuss the issues that arise when adding nodes to the graph using

this representation. What is the computational complexity of this operation in

terms of the number of nodes N? Discuss a technique to improve the

performance of the operation, and compare and contrast the costs involved

with those of the edge list representation.

Order Now

Payment Methods

All online transactions are done using all major Credit Cards or Electronic Check through PayPal. These are safe, secure, and efficient online payment methods.

Our customer support team is here to answer your questions. Ask us anything!

👋 Hi, how can I help?