[SOLVED] CSC4520 Assignment 1

1.  Sort the following asymptotic growth rates in an increasing order: (!)#, 𝑛!, 4#, 𝑛!, log 𝑛, (log 𝑛)”.

”

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

1