Session activities¶

Activities¶

In the Exercise 1, you will use the following rooted tree as an example. The key of each node is shown and the root of the tree is 8.

Exercise 1a¶

In a rooted tree there is a unique path from each node to the root. For example, the path from the node whose key is 4 to the root is the following: { 4, 7, 6, 8 }.

Write the path to the root for each node. (9 paths)

Exercise 1b¶

It is desired to compile a set containing all the paths given in Exercise 1a. You have access to the root node, and you need to traverse all nodes up to the leaves, starting from the root node. The compiled paths should start from each node and extend up to the root node, as in Exercise 1a.

Write pseudocode or C++ code that will compile the paths from each node to the root. (Note: since a set is being compiled, the order of the paths in the set is not important.)

Pseudocode¶

It can be assumed that for each node in the tree there is a data type Node that has the following attributes:

Node.key = the key of a node
Node.parent = pointer to parent of Node or NIL if root
Node.children = all children of Node

The following assumptions can be made:

Node.children is some container containing all the children of Node.
Node.children.length() can be assumed to contain the number of children.
Root is a Node that contains the root node of the tree.

C++¶

Similarly as for the pseudocode, you may use the following C++ struct and constants for your function that compiles the paths given in Exercise 1a.

All nodes are using the following struct:

struct Node {
  int key=NO_KEY;
  Node* parent = NO_NODE;
  std::unordered_set<Node*> children = {};
}

With the following constants:

int NO_KEY = -1;
Node* NO_NODE = nullptr;

You may use the C++ base code provide in a zip . The code already contains the Node struct and the constants shown above. It also generates the example tree shown above. You only need to write the function that compiles the paths.

Exercise 2a¶

Exercise 2 focuses on heaps, specifically on maintaining information about the median of input data using two heaps. To begin, consider the process of adding a sequence of input values and tracking how the median changes after each addition.

Provide the following details after each addition from the sequence of input values: 5, 6, 7, 4, 2, 1, 11, 12, 13, 14, 15:

The value that was added.
Whether the added value is smaller or larger than the old median value.
The new median value after the addition.

Exercise 2b¶

Write pseudocode or C++ code that maintains information about the median of input data using two heaps. The solution should work efficiently, if the median is requested often, and new data elements are added between median requests.

You may use the C++ base code provide in a zip .

The following following functions might be helpful:

A+ presents the exercise submission form here.