Homework 1
1. (20 points) Sort the following asymptotic growth rates in an increasing order:
(
!
"
)#, �!, 4#, �!, log �, (log �)".
2. (20 points) Using Figure 10.1 (Textbook Exercise 10.1-1) as a model, illustrate the
result of each operation in the sequence PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8),
and POP(S) on an initially empty stack S stored in array S[1, 2, …, 6].
3. (20 points) Using Figure 10.2 (Textbook Exercise 10.1-3) as a model, illustrate the
result of each operation in the sequence ENQUEUE(Q, 4), ENQUEUE(Q, 1),
ENQUEUE(Q, 3), DEQUEUE(Q), and ENQUEUE(Q, 8) on an initially empty queue Q
stored in array Q[1, 2, …, 6].
4. (20 points) The structure of a singly linked list is shown as follows:
Please give the pseudocode of the operations Insertion and Deletion on a singly linked
list. For Deletion, it is required that deleting the first key from the list. (Hint: refer to the
operations of insertion and deletion on a doubly linked list in Chapter 10.2).
5. (20 points) Write the pseudocode of Tree-Predecessor procedure. (Hint: predecessor
of a node x is the largest key smaller than x in tree and the idea to find a predecessor is
similar to Tree-Successor procedure in Textbook.)
