Algorithm assignment solution for Decision tree problems

1. Decision Trees

1. Three elements, say, a1, a2, and a3 can be sorted using three comparisons. The following decision tree suggests how:



Fill in the leaves of the tree: which permutation of a1, a2, and a3 has been established in each case?

2. Can you improve the decision tree?
3. The decision tree corresponds to a sorting network. Which one?
4. In general, how can one easily check whether a decision tree pictures a sorting network?
5. What’s the minimal size and what’s the minimal depth of a decision tree for sorting 10 elements?

Over the years, the game show “Beat Your Neighbours!” has lost a considerable number of viewers. In a desperate attempt to make the show more attractive, the host has decided to change the eponymous game of the show (see also Slide 123). The contestant is now presented with a grid of n × n sealed boxes, each containing a number. It costs £100 to open a box. The goal is to find a box whose number is larger than its neighbors: to the left, to the right, above, and below. (For boxes on the boundaries only three neighbors need to be considered; for boxes on the corners only two.)

1. Describe an algorithm that solves the problem. (You may wish to provide some pseudo-code or, perhaps, a concrete program in the programming language of your choice.)
2. Show that your algorithm is correct, for example, by exhibiting a suitable invariant.
3. Analyze the running time of your algorithm: how many boxes are opened in the worst-case?

Consider the leftist heap below:

1. Insert element 5 into the heap.
2. Insert element 6 into the heap resulting from part (a).
3. Insert element 2 into the heap resulting from part (b).

For each insertion show the resulting tree, and provide some details as to how you obtained the tree.

4. Harry Hacker claims that one obtains a perfect tree if the elements 1,2,...,2h−1 are inserted into an initially empty leftist heap (ie first insert 1, then 2, etc). Right or wrong? Which tree is obtained if the order of insertion is reversed?

In the lectures, we have discussed 2-3 trees, which are full trees consisting of 2- and 3-nodes. A 2-3-4 tree additionally offers 4-nodes that contain three keys and four sub-trees.

Thus, a 2-3-4 tree is a full tree consisting of 2-, 3- and 4-nodes.

Write a short essay of no more than 1000 words about the subject of constructing 2-3-4 trees. Given a sequence of elements, the goal is to build a 2-3-4 tree that contains the elements in symmetric order ie an inorder traversal yields the original sequence of elements.

Try to apply the different algorithmic methods discussed in the lectures. Can you construct 2-3-4 trees in a top-down fashion, where you first create the root node and then the sub-trees? What about a bottom-up approach, where you first create the leaves? Or, perhaps, an incremental approach, where you sequentially insert the elements of the sequence, one after the other. Analyze the running time to complete your algorithm assignment. What is the complexity of the problem: how fast can you construct a 2-3-4 tree from a given sequence of elements?

Support your arguments with diagrams, pictures, pseudo-code, or program snippets (in the programming language of your choice) as you see fit.

Solution:

1.

2. We can remove some nodes from the decision tree to make it a bit smaller.



3. Yes, the result corresponds to a sorting network. It corresponds to a level 3 sorting network because it sorts 3 elements.
4. To know if it is a sorting network is to see if it achieves the solution in a finite amount of sorting operations and on the other hand to know if it can do fixed sorting.
5. We can observe that at the last level the decision tree should contain all the permutations that are (10!) And since the tree is binary, the depth of the tree is approximately ceil (log2 (d)) + 1 where d is the number of nodes at the last level of depth, we also know that d = 10! That is to say that the final depth would be approximately ceiling (log2 (10!)) + 1 that is to say 23 levels.

This also shows that any comparison sort algorithm is O (n * log (n)) since n * log (n)> log (n!).

2.

1. The following code in python3




The basis of the algorithm is to go from left to right and from top to bottom, checking if it does not have a greater number around it, when it does, the algorithm stops.

2. Let property f be that there is no neighbor to the box with a value greater than this.
3. For all the boxes of the previous rows, no box fulfills the property f also for all the elements of the same row but to the left of it, it does not fulfill the property f.
4. In the worst case that the box that meets the condition is in the inner right corner, it will have to verify the property in all the boxes, the property is executed in constant time, that is, the final complexity is O (n ^ 2)

3

4. Yes, because the leftist heap is self-balancing, and by always adding numbers greater than the one it is, it adds it to the node with the smallest distance, like this until they all try the same distance, when that happens we have a perfect tree




As in this example, the next node is node 12, when adding node 12 it can only be left as a child to the left of node 4 or node 5, this will happen until all nodes reach the level. And having 2 ^ h-1 has exactly the number of nodes in a perfect tree; therefore the result is a perfect tree.



By inserting a smaller and smaller node in reverse, we have a degenerate tree since the new node will always be the root and the previous tree will be the left branch.

4)

This problem consists of constructing a 2-3-4 tree given a vector of elements in a list, an array, or a vector. This can be in disorder, for that the first step would be to order it, which would take O (n * log (n)).

a 2-3-4 tree has 5 different nodes the node without children that can have 3 different numbers, the node without children that has 2 different numbers, and the node without children that only has one number, there is also the node with two children that only has a number all less than it on its left and all greater than it on its right, similar to a binary search tree, then the node of 3 children and two elements, in this case, a branch would be all children with elements less than the number more to the left the middle branch would be all the elements between the two numbers and finally the branch to the right are the numbers greater than the second number. Case similar to the node with 3 elements and four branches, the first corresponds to all the minors of the leftmost, the second corresponds to the elements between which are between the leftmost number and the center, the third branch corresponds to the elements with the number in the center and the number on the right and the last branch is the largest of all numbers.

In order to build the tree you have to have several cases for the 6 different cases

For that, the recursive function that receives the arrangement with n elements, already ordered, is created, then the first cases are the base cases if the size of the arrangement is 1, 2, or 3, if it is of size 1 a node of an element without children, in the case of two elements a node with two elements and without children is created and in the case of 3 elements, a node with 3 elements and without children is created.

Then the recursive cases follow, the first case is if the size of the array n is of form 4m + 3 (that is, the n modulo 4 is 3), the first m elements are used, the resulting tree ends in the first branch, the element m + 1 will be the first element of the nodes, then the elements from m + 2 to 2 * m + 2 are called recursively and the resulting tree goes to the second branch, the second element of the node is the one located in the position 2 * m + 2, then the elements from 2 * m + 3 to 3 * m + 3 are called recursively, the arrangement obtained would be the third branch, the third element of the node would be 3m + 3, finally, it is used in the elements 3m +3 to 4m + 3 and this resulting arrangement would go last.

The case of 2 elements would be very similar but if n = 3m + 2

and the same idea the first m elements will go to the first branch the element m +1 will be the first element of the node the following m elements will go to the second branch, the element 2m + 2 will be the second element of the array and finally, the last m elements will go in the third branch.

The case of 1 element would be very similar but if n = 2m + 1 and the same idea the first m elements will go to the first branch the element m +1 will be the first element of the node the next m elements will go to the second branch.

With this recursive function, the tree 2-3-4 will be ordered and will fulfill the property in order.

It is important to consider the case 4 tree (the one with 3 elements) must be evaluated first then the case 2 trees (the one with 1 element) because every element that can be written in form 4 * m + 3 can be written in form 2 * k +1, therefore all 4 trees can be extruded as a 2 tree, therefore there would be a 2-3 tree and not a 2-3-4 tree.