# Write these program in algorithmic language

Question 1: Definition of the structures nodeR and listR
First define a constant maxLevel (for our example maxLevel is 4), then a structure nodeR having as attributes two integers value and level and an array of pointers to nodeR tabPointers.
– value is the value of the node on which is ́established the strictly ascending order of the chained list.
– level gives the number of pointers in the array tabPointers, it corresponds to the number of shortcuts available from the node.
– tabPointers is an array of pointers to nodeR of maxLevel cells of which we will use only the first level cells.
Then define the type listR which is a pointer to nodeR.
Afterwards, we will make sure that the first node of a list of type listR
is always a node of level maxLevel.
Stage 2 consists of nodes with values 2, 4, 10, 14, 16, 24, 28 and stage 3 consists of nodes with values 2, 10, 16 and 24. The array of pointers tabPointers of a node will allow to link this node to the next node of the same floor, and this for all the floors to which the node belongs. For example, for the list L0 the node with value 10 is connected to the node with value 14 for the ́etage 2 and to the node with value 16 for the ́etage 3.
Question 2. Creating a node
Define a procedure creationNode(v,k:integers):pointer to nodeR that returns a pointer to nodeR of value v and level k. You will set all pointers to nodeR equal to None.
Question 3. Construction of stage 1 of L
Define a procedure constructionStage1(n:integer,arrayValues,
Stage of a list L
The floors go from 1 to maxLevel. The floor i is made of nodes of level superior or equal to i. Thus stage 1 is a simply chained list linking all nodes together (see Figure 2). The last node points to None.
2
L0
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32
Figure 2 – Construction of the ́th level 1 of the list L0
arrayLevels:integer array):listR which constructs a list L of type listR from two integer arrays arrayValues and arrayLevels of size n such that the first node has the attribute level a equal to arrayLevels[0] and the attribute value equal to arrayValues[0], the second node has the attribute level equal to arrayLevel[1] and the attribute value equal to arrayValues[1] and so on.
In order to respect the listR structure, we will make sure that the following two conditions on the two arrays are checked:
Condition C1 the ́el ́ements of arrayValues are rank ́es in strictly increasing order.
Condition C2 the first cell of arrayLevels defines the value maxLevel and all other cells have a value between 1 and maxLevel
Make the procedure constructionFloor1 traverse the minimum number of nodes.
The list in Figure 1 was constructed with the following two arrays that verify conditions C1 and C2:
arrayLevel = [4,2,1,1,3,1,2,4,1,1,1,3,1,2,1,1] arrayValues = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32]
Question 4. Construction of the other floors of L
We have seen that the i-stage of L is constituted by the nodes whose level is greater than or equal to i. We must now link these nodes together using pointer arrays. Each node of level i will be connected to the next node of that level. For example, for the node with value 2, the next node on level 4 is the node with value 16 and the next node on level 3 is the node with value 10.
Define a procedure constructionListR(n:integer,arrayLevels, arrayValues:array of integers):listR that returns L with all levels.
You must perform only one walk through the list for the construction of levels 2 to maxLevel.
Question 5: Searching for a node from a value
The search is performed from a node by using the highest level pointer and going down one level.
The search is performed from a node by using the highest level pointer and going down one level when we need to return to that node.
We will explain this search on an example. Suppose we are searching for the node with value x = 14 in L0 (Figure 3). The num ́erotation in blue a1, a2,…corresponds to the order of access to the nodes during this search and the arrows in blue are the d ́erotation in blue.
blue are the d ́eplacements made between the nodes.
We start from the ́etier 4 of the first node of value 2 (a1) to the node of value
16 (a2). 16 is larger than x, so we have ́and ́e too far, we return to the value node 2 (a3) and move on to the third floor by going to the value node 10 (a4). We arrive again on the node of value 16 (a5) and we return to the node of
3
L0
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32
a6 a7
a3 a4 a5 a1 a
Figure 3 – Finding the node with value 14 in the L0 listvalue 10 (a6).
Borrowing from floor 2, we arrive at the node with value 14 (a7) which is the node we are looking for, so the search is over.
In general, the return on a node is done when the borrowed pointer points to None or when the value of the pointed node is greater than the value x. We see that x is not present in the list when we arrive at floor 0 (we return to a node when we are at floor 1).
a) Perform ́etape by ́etape this algorithm by taking successively the values 12, 20 and 25.
b)Define a procedure searchNode(L:listR,x:integer):pointer to nodeR that returns a pointer to nodeR P of L such that P →value = x or returns None when such a node does not exist.
You must imperatively perform only one traversal of the list to perform the search.
Question 6: Inserting a node with value x
As an example, we will insert a node with value 13 and level 4 (see Figure 4).
Location of the insertion
L0
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32
L0
2 4 6 8 10 12 13 14 16 18 20 22 24 26 28 30 32
Figure 4 – Insertion of a node of value 13 and level 4 in L0 4
For each level below or equal to the level of the node to be inserted, we must determine the pointers to the first nodes with a value greater than 13. Here the level is equal to maxLevel, so all the levels are to be considered. On figure 4 these pointers are in black boxes and the nodes they point to are in white. At the end of the insertion, these black pointers will point to the new node we just inserted and this node will point to the white nodes. For example, at level 3 the node with value 10 points to the node with value 16. At the end of the insertion, the node with value 10 points to the new node with value 13 and this one points to the node with value 16.
Define the procedure insertionNode(L:listR,x,k:integer):listR to perform the insertion of x into L. Remember to handle the following cases:
1. if the list is empty, we return a pointer to nodeR P with the value x and the level k.
2. there is already a node with the value x, we do not modify the list L
3. x is smaller than the y-value of the first node. In this case, we swap the values of x and y
the values of x and y and insert the new value x and k
Hints: for stage 1, this is the classic insertion that we have seen in class and in the tutorial. Start by performing the insertion at floor 1 and modify your algorithm to perform the insertion at all floors. use an array of pointers to store the pointers corresponding to the black cells.
You must perform only one walk through the list to perform the insertion.
Question 7. Deleting a node of value x
Deletion is very similar to insertion. Consider deleting the node
L0
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32
L0
2 4 6 8 10 12 14 18 20 22 24 26 28 30 32
Figure 5 – Deleting the node of value 16 in L0
of value 16 in L0 (see Figure 5). The black boxes represent the pointers to the node to be deleted and the white boxes represent the nodes to which the node to be deleted points. At the end of the deletion, the pointers of the black boxes will point to the white boxes.
5
Define the procedure deleteNode(L:listR,x:integer):listR.
As before for the insertion, you must store in an array the pointers of the black cells. Don’t forget to consider the following cases
1. the list is empty
2. the list contains only one node of value x 3. the list does not contain the value x
4. the value x appears on the first node
In the last case, as we want the first node to be of level maxLevel, you will exchange the values between the first and the second node, then you will replace, for each level, all pointers from the first node to the second node by a pointer to the node on which the second node points. And finally you will delete the second node.
You must do only one traversal of the list to perform the deletion.
Thereafter, k will be a stritement positive natural number and n will be the integer 2^n
Question 8. * Complexity of the search
The cost of a search algorithm for an integer x will be the number of comparisons made between x and another integer (value of a node for a list, value of a cell for an array).
a) Complexity of the search in a sorted list
Determine the worst case complexity of searching for x in a simply chained sorted list containing the values 2, 4, . , 2n, 2(n 1).
Determine also the complexity on average, when x is drawn randomly with the uniform distribution on the set [2n 2] = {1, 2, 3, . 2n 2}.
b) Complexity of the search in a sorted array.
Let T be an array of integers sorted by ascending order containing the values 2, 4, . , 2n, 2(n 1). Give the worst case complexity of the dichotomous search on this array and in which cases we have this worst case.
c) Complexity of the search on a shortened list
Let L be a list of type listR containing the values 2, 4, . , 2n, 2n 2. Propose a choice of level distribution for the nodes of L so that the steps of the search for x are similar to the dichotomous search on a sorted array. Specify how you choose maxLevel. You will illustrate your remarks on an example by taking k = 4 and the values 2, 4, . . . , 32, 34 and performing the search for the node of value x by taking for x three values between 1 and 34.
Do you think the shortcut list is a good data structure to perform the search for an x-value efficiently?
In the following, k d ́esignates a stritement positive natural number and n is the integer 2
Translated with www.DeepL.com/Translator (free version)