Session activities¶

Exercises for the week 9 exercise session¶

In the following exercises 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 1 - Paths¶

It is desired to compile a set containing all the paths given in Exercise 1. 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 1.

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 1.

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 - Median¶

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 of the item added.
Whether the added value is smaller or larger than the old median value.
The new median value after the addition.

Exercise 2b - Median - implementation¶

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.