Q1(a): Show the Stack after each operation of the following sequence that starts with the empty stack:

push(a), push(b), top(), pop(), push(c), pop(), push(d), pop(), pop()

Q1(b): Show the Queue after each operation of the following sequence that starts with the empty queue:

enqueue(a), enqueue(b), dequeue, enqueue(c), enqueue(d), dequeue, dequeue

Q2(a): For each of the following functions, indicate how much the functions value will change, if its argument is increased threefold.

(a) n3 (b) 2n (c) log2 n

Q2(b): Indicate whether the first function of each of the following pairs has a smaller, same, or larger order of growth (to within a constant multiple) than the second function.

(a) 2n-1 and 2n (b) (n - 1)! and n! (c) log23 n and log2 n2

Q3: How many comparisons (both successful and unsuccessful) are made by the brute-force string-matching algorithm in searching for each of the following patterns in the binary text of 1000 ones?

(a) 11010 (b) 00111 (c) 111010

Q4: For each of the following algorithms, indicate (i) a natural size metric for its inputs; (ii) its basic operation; (iii) whether the basic operation count can be different for inputs of the same size:

(a) Computing the sum of n numbers (b) Computing n!