Question $5(2$ marks$)$

A$.$ What are the worst$-$case and best$-$case running times of the following algorithm?

B$.$ Count the number of primitive operations line by line. Show your work.

$```$

for $($i$=1$; in; i$++)$

$\_\_$time

$\{$

if $($a$[$i$]>0)$

$\{$

for$($j$=1$;j Question $1(2$ marks$)$

Assume a binary tree with integer values in the nodes. In this problem, you will design a linear$-$time algorithm that finds out existence of a path with given sum. In other words, given a sum, you need find a path from the root to any of the nodes that adds up to the given sum.

A$.$ Describe your algorithm in pseudocode.

B$.$ Analyze its worst$-$case running time.

Question $2(2$ marks$)$

Describe a memory$-$efficient solution to implement four queues in a single array. In other words, all four queues should use the same array for storing elements. The standard enqueue and dequeue methods should be updated to take an extra parameter to identify the queue. For example, the enqueue$(\backslash ($ n $\backslash ),$ element$)$ method should add an element to queue number n $,$ where n is an integer between $0$ and $3.$ Similarly, the dequeue$(\backslash ($ n $\backslash ))$ method deletes an element from queue number $"$ n $"$ where n is from $0$ to $3.$

Question $3(2$ marks$)$

Given a stack of integers, write a pseudocode to check whether each successive pair of numbers in the stack is consecutive or not. The pair can be increasing or decreasing, and if the stack has an odd number of elements, then the element at the top is left out of a pair. For example, if the stack of elements is $[4,5,\backslash (-2,-3,11,10,5,6,20]\backslash ),$ then the output should be true because each of the pairs $\backslash ((4,5),(-2,-3),(11,10)\backslash ),$ and $\backslash ((5,6)\backslash )$ consist of consecutive numbers. Your solution should ensure that the stack is restored to its original state when the algorithm is done.

Note

You should use a queue as an auxiliary data structure.

Question $4(2$ marks$)$

A$.$ Does the tree in the following figure have the heap property?

B$.$ Show step$-$by$-$step process for deleting the max element from the heap.