- (15 points) Describe in pseudo code how to implement the stack ADT using two queues.
- Write a C++ function that implements your solution. You can use the C++ STL queue container.
- What is the running time of the push and pop functions in this case?
- (15 points) Write a recursive function in C++ that counts the number of nodes in a singly linked list.
- Test your function using diﬀerent singly linked lists. Include the code and screenshots with testing cases.
- Write a recurrence relation that represents your algorithm.
- Solve the relation using the iterating or a recursive tree method to obtain the running time of the algorithm in Big-O notation.
- (15 points) Write a C++ recursive function that finds the maximum value in an array of integers without using any loops.
- Test your function using diﬀerent input arrays. Include the code and screenshots with testing cases.
- Write a recurrence relation that represents your algorithm. Solve the relation and obtain the running time of the algorithm in Big-O notation.
- (15 points) What is the best, worst and average running time of quick sort algorithm? Provide ar-rangement of the input and the selection of the pivot point at every case. Provide a recursive relation and solution for each case.
- (10 points) What is the best, worst and average running time of merge sort algorithm? Use two methods for solving a recurrence relation for the average case to justify your answer.
- (10 points) R-10.17 p. 493
For the following statements about red-black trees, provide a justification for each true statement and a counterexample for each false one.
- A subtree of a red-black tree is itself a red-black tree.
- The sibling of an external node is either external or it is red.
- There is a unique (2,4) tree associated with a given red-black tree.
- There is a unique red-black tree associated with a given (2,4) tree.
- (10 points) R-10.19 p. 493
Consider a tree T storing 100,000 entries. What is the worst-case height of T in the following cases?
- T is an AVL tree.
- T is a (2,4) tree.
- T is a red-black tree.
- T is a binary search tree.
- (10 points) R-9.16 p. 418
Draw an example skip list that results from performing the following series of operations on the skip list shown in Figure 9.12: erase(38), insert(48,x), insert(24,y), erase(55). Record your coin flips, as well.