## Description

- (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?

2

- 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.

3