Homework 2
due March 25 at 11:59 pm to eCampus.
(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 different 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 different 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
