Data Structures & Algorithms End term Class Test

1. A circular doubly linked list Abstract Data Type has a private header pointer, called
lst, which points to the first node of a circular doubly linked list. This ADT does not
maintain a specific header pointer to the last node of the list.
Given a pointer to a node n, assume that values can be read or written to by using the
field names n.prev , n.val and n.next for the previous, value and next fields of the
node respectively.
Assume that a garbage collector is being used, so nodes do not need to be explicitly
freed.
Use END for invalid or null address pointer values.
cddl_delete_last is a member function of the ADT that removes the last element from
the list (if there is one). Fill in the missing part of the pseudocode for this function
below:
Answer:
As per the question description there is a circular doubly linked list Abstract Data Type that has a
private header pointer called lst which points to the first node of the circular doubly linked list.
And for that private member I am assuming that this method is written inside the class the class.
 Node is represented by n.
 Previous of the node is represented by the n.prev.
 Value of the node is represented by the n.val.
 Next of the node is represented by the n.next.
The below algorithm covers 3 scenarios first one is if the lst is Null, second is if the lst is the
only node in the circular doubly linked list and the third is if the circular linked list have more
than two nodes.
Algorithm:
 Step 1: If lst is Null then END
 Step 2: Else-if lst.next is equal to lst then set lst to Null.
 Step 3: Else create a temp node and set that node equal to lst.
 Step 4: Iterate the circular doubly linked list while temp.next is not equal to lst.
 Step 5: Set temp to temp.next. (End of Loop)
 Step 6: Set the temp.prev.next to lst.
 Step 7: Set lst.prev to temp.prev.
 Step 8: END
The missing part of the pseudocode for this function is as follows:
void cddl_delete_last()
{
Node temp;
if(lst = NULL)
{
END;
}
else if(lst.next == lst)
{
lst = NULL;
}
else
{
temp = lst;
while(temp.next != lst)
{
temp = temp.next;
}
temp.prev.next = lst;
lst.prev = temp.prev;
}
return
}

In this pseudocode I did not use free explicitly as in the description of the question it is already
mention to assume that we are using the garbage collector.
2. For each of the following functions to calculate the largest element of an array, state
which complexity class in big O notation the function belongs to and justify your
answer with a short explanation:
a) Largest1 Method
int largest1(int []arr)
{
int n = arr.length;
int max = 0;
for (int i=0;i<n;i++)
{
bool largest = true;
for(int j=0;j<n;j++)
{
if(arr[i]<arr[j])
largest=false;
}
if(largest)
max = arr[i];
}
return max;
}
Answer:
In this function there are nested loop means there is for loop in another for loop. For each value
of i (from 0 to n) this nested loop will be executed from 0 to n. So, by this we have the time
complexity of n*n which is O(n2).
b) Largest2 Method
int largest2(int [] arr)
{
int n = arr.length;
int max = 0;
if(arr.length==0)
{
return 0;
}
else
{
max = arr[0];
for(int i=0;i<n;i++)
{
if(arr[i]>max)
max = arr[i];
}
}
return max;
}
Answer:
In this function there is a single for loop that will be executed for value of i (from 0 to n). So, the
time complexity of this function will be O(n).
 c) Largest3 Method
int largest3(int [] arr)
{
sort(arr);
if(arr.length==0)
{
return 0;
}
else
{
int last = arr[arr.length−1];
return last;
}
}
Answer:
In this function, built-in function sort() is used that sort the array in ascending order. So, this sort
function is the main contributor to the time complexity of this function. Usually, the built-in sort
function has O(nlogn) time complexity. So, the time complexity of this function will also be
O(n*logn).
Thus, the given functions will have the time complexities of O(n2), O(n) and O(n*logn)
respectively.
3. Consider a binary search tree used to store integers with methods isEmpty(t), left(t),
right(t) and root(t), to return whether the tree t, is empty, the left child tree, the right
child tree and the integer value stored at the root respectively.
a) Write a recursive function sum_rec(tree) to calculate and return the sum of all
integers stored in the tree.
Answer:
I am assuming that the left(tree) and right(tree) functions return null if left or right child
of tree does not exist respectively.

int sum_rec(tree)
{
if isEmpty(tree)
{
return root(tree)
}
return sum_rec(left(tree)) + sum_rec(right(tree))
}
The above is the pseudocode of the function that sum the integers recursively that are
stored in the tree.
 b) A Queue ADT has, for a queue q, methods q.enqueue(val) and q.dequeue() to
enqueue a value val in the queue and to dequeue and return a value from the queue
respectively. It also has a constructor which can be invoked with the command
new Queue() to create and return a new empty queue.
Write the pseudocode for a non-recursive function sum_nonrec(tree), to calculate
and return the sum of all integers stored in the tree.
Answer:
I am assuming that the q.dequeue() function returns null if the queue is empty and we still try to
dequeue it.
int sum_nonrec(tree)
{
Declare sum = 0
Declare q = new Queue()
Declare t = tree
While t != null
{
sum = sum + root(t)
if !isEmpty(t)
{
if left(t) != null
q.enqueue(left(t))
if right(t) != null
q.enqueue(right(t))
}
t = q.dequeue()
}
return sum
}
The above is the pseudocode of the function that sum the integers non recursively that are
stored in the tree.
4. Draw the result of merging the following two Binomial Heaps:

Answer:
 First, we find the degrees of each node that are represented by the square. While Degree
is the number of edges in the subtree in the node.

 Now connect the

lowest degree node
first, then higher ones from left to right. If degree of two nodes is same, then any of them
can be taken first.
 There cannot be more than one node of same degree, therefore merge two nodes together
with the same degree.
• When merging, put the higher numbered circle connected to lower numbered.
• Since there is only one node of degree 0 and degree 1, hence no merging will take
place.
• There are two nodes of degree 2, hence merge them together.
Merge 1:

Merge 2:
Now we can merge the nodes of 4 degrees.