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