. Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order onto the stack; the pop operations print out the return value. Which of the following sequence(s) could not occur? ( May be more than one sequence.)

4 3 2 1 0 9 8 7 6 5

2 5 6 7 4 8 9 3 1 0

4 6 8 7 5 3 2 9 0 1

4 3 2 1 0 5 6 7 8 9

1 2 3 4 5 6 7 8 9 0

0 4 6 5 3 8 1 7 2 9

2. Let A be a given array of n integers. Characterize, using the big-Oh notation, the worst-case running time of

The Best characterization is :

3. For a binary tree (not necessary a BST), we are given the following information

preorder traversal sequence : D F I G T A L M X

postorder traversal sequence : I T G F L X M A D

Can you construct and draw the tree from the given ? If so, draw the tree. Is the tree unique? If the tree is not unique, how many possible binary tree with the given pair of traversal sequences?

4. Characterize, using the big-Oh notation, the worst-case running time of

4. 1. Alg Ex1(A):

 Input: array A storing n > 0 integers. 

 Output : The sum of the elements in A. 

 s  

 for i  

 s  

 return s  

4.2 Alg Ex2(A):

 Input: array A storing n > 0 integers. 

 Output : The sum of the elements at even cells in A. 

 s  

 for i  

 s  

 return s  

4.3 Alg Ex3(A) :

 Input: array A storing n > 0 integers. 

 Output : The sum of the prefix sums in A. 

 s  

 for i  

for i