heap data structure can be efficiently implemented in a range using the C++ Standard Template Library (STL). In this exercise you are asked to utilize STL in order to build and manipulate a heap efficiently

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Question 1 [Topic: Heaps] [Percentage: 15%]: A heap data structure can be efficiently implemented in a range using the C++ Standard Template Library (STL). In this exercise you are asked to utilize STL in order to build and manipulate a heap efficiently. In particular, you are requested to:

1. Make a heap consisting of 10 different integers of your own choosing. Include a statement to show the maximum element of the heap.

2. Add a new value that is the mean of the random values you creates in the previous step. Floor the value if needed (truncate decimal part). 3. Delete the maximum element of the heap and

3. Sort the heap.

2   Write down the code to achieve all the operations mentioned above and clarify which section of the code does what.

Question 2 [Topic: Binary Trees] [Percentage: 35%]: Consider the following subsets of code:

File: BinaryNodeTree.h

 #ifndef BINARY_NODE_TREE_ #define BINARY_NODE_TREE_

#include "BinaryTreeInterface.h" #include "BinaryNode.h"

#include "PrecondViolatedExcept.h" #include "NotFoundException.h" #include <memory>

template<class ItemType> class BinaryNodeTree : public BinaryTreeInterface<ItemType>

{

private:

std::shared_ptr<BinaryNode<ItemType>> rootPtr;

protected:

//------------------------------------------------------------

// Protected Utility Methods Section:

// Recursive helper methods for the public methods.

//------------------------------------------------------------        int

getHeightHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const; int getNumberOfNodesHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const;

 

// Recursively adds a new node to the tree in a left/right fashion to keep tree balanced.

auto balancedAdd(std::shared_ptr<BinaryNode<ItemType>> subTreePtr, std::shared_ptr<BinaryNode<ItemType>> newNodePtr);

// Removes the target value from the tree. virtual auto removeValue(std::shared_ptr<BinaryNode<ItemType>>              subTreePtr, const ItemType target, bool& isSuccessful);

// Copies values up the tree to overwrite value in current node until    // a leaf is reached; the leaf is then removed, since its value is stored in the parent.

auto moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr);

// Recursively searches for target value.

virtual auto findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,

 

const ItemType& target, bool& isSuccessful) const;

// Copies the tree rooted at treePtr and returns a pointer to the root of the copy.

auto  copyTree(const std::shared_ptr<BinaryNode<ItemType>> oldTreeRootPtr) const;

// Recursively deletes all nodes from the tree.

void destroyTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr);

// Recursive traversal helper methods:

void preorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr)    const;                void inorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const; void postorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;

 

public:

//------------------------------------------------------------

// Constructor and Destructor Section.

//------------------------------------------------------------

BinaryNodeTree();

BinaryNodeTree(const ItemType& rootItem);  BinaryNodeTree(const ItemType& rootItem,std::shared_ptr<BinaryNodeTree<ItemType>> leftTreePtr,

const std::shared_ptr<BinaryNodeTree<ItemType>> rightTreePtr); BinaryNodeTree(const std::shared_ptr<BinaryNodeTree<ItemType>>& tree);

virtual ~BinaryNodeTree();

 

//------------------------------------------------------------

// Public BinaryTreeInterface Methods Section.

//-----------------------------------------------------------

-    bool isEmpty() const;   int getHeight() const;   int getNumberOfNodes() const;

 

ItemType getRootData() const throw(PrecondViolatedExcept); void setRootData(const ItemType& newData);

bool add(const ItemType& newData); // Adds an item to the tree

bool remove(const ItemType& data); // Removes specified item from the tree void clear();

Provide implementations for the protected methods:

• void inorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const; [10/35]

• void postorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const; [10/35]

• void preorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const; [10/35]

• void destroyTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr); [5/35]

In your implementation of destroyTree utilize postorder traversal.

Question 3 [Topic: Dijkstra’s Shortest Paths] [Percentage: 25%]: dijkstra

Q3.1 [18%/25%]: For a graph represented by its adjacency matrix int graph[V][V] and a starting vertex int src find the shortest paths for all vertices using the Dijkstra’s algorithm. Function declaration follows:

Q3.2 [2%/25%]: Write the adjacency matrix for the directed graph shown below

Q3.3 [5%/25%]: Use the depth-first strategy to traverse the graph in the Figure above, beginning with vertex 0. List the vertices in the order visited.

Question 4 [Topic: Comprehensive] [Percentage: 25%]: Answer to all the questions set below.

Q4.1 [10%/25%]: Trees-related questions

 §  Beginning with an empty binary search tree, what binary search tree is formed when you add the following letters in the order given? J, N, B, A, W, E, T

• Why does a node in a red-black tree require less memory than a node in a 2-3-4 tree?

• Why can’t a Red-Black Tree have a black child node with exactly one black child and no red child?

• What is the maximum height of a Red-Black Tree with 14 nodes?

Q4.2 [5%/25%]: Graphs-related questions

 

• Is it possible for a connected undirected graph with five vertices and four edges to contain a simple cycle? Explain your

• Write the adjacency matrix and the adjacency list for the graph depicted

• Draw the BFS spanning tree whose root is vertex 0 for the graph shown

Q4.3 [5%/25%]: Heaps-related questions

• Is the full binary tree in the figure below, a semiheap?

• Consider the maxheap in the figure below, draw the heap after you add 12 and remove

• Visualize the initially empty myHeap after the following sequence of operations

o myHeap.add(2)

o myHeap.add(3)

o myHeap.add(4)

o myHeap.add(1)

o myHeap.add(9)

o myHeap.remove()

o myHeap.add(7)

o myHeap.add(6)

o myHeap.remove()

o myHeap.add(5)

Q4.4 [5%/25%]: Dictionaries-related questions 

• What is the Big-O function for addition, removal, retrieval and traversal of

o unsorted array-based dictionary:

o unsorted link-based dictionary:

o sorted array-based dictionary:

o sorted link-based dictionary:

o BST-based dictionary:

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of