Algorithms and Data Structures – 60-254 – Sample midterm 1

Part I: Multiple choice (10 marks = 2 marks × 5)
For this part clearly write down the single choice that you believe is the most accuarate.
1. Let N and N0 be the number of division steps performed by Euclid’s GCD algorithm (as described
in the notes, where we set r m mod n, without checking for the relative sizes of m and n) for the
inputs m = 13, n = 21 and m = 21 and n = 13 respectively. Then,
(a) N − N0 = 1
(b) N0 − N = 1
(c) N − N0 = 0
(d) None of the above
Ans:
2. If T(n) = c2 n2+c1 n+c3 is an estimate of the worst-case time-complexity of some algorithm, which
of the following is the best description of T(n) in terms of the big-Oh notation:
(a) T(n) = O(n)
(b) T(n) = O(n2)
(c) T(n) = O(n3)
(d) None of the above
Ans:
3. Given the list of integers 1, -2, 3, -6, 7, -8, 9, 10, -11, indexed from 1 to 9, the left-to-right linear scan
algorithm (O(n) algorithm) will set as candidate start positions for a maximum contiguous sequence
the elements at the index positions:
(a) 1,3,4,6
(b) 1,3,4,6,9
(c) 1,3,5,7
(d) None of the above
Ans:
4. As we discussed in class, a queue can be simulated using two stacks. If n is the number of elements
currently in the queue, while an enqueue operation takes 1 push, a dequeue operation needs:
(a) 2n − 1 pops and 2(n − 1) pushes
(b) n − 1 pops and n − 1 pushes
(c) 2n pops and 2n pushes
(d) None of the above
Ans:
5. The Fibonacci sequence 1,1,2,3, … can be generated iteratively by starting with the first two (0th
and 1st) and generating every subsequent one by adding the previous two. In fact, the nth Fibonacci
number can be generated by n − 1 additions for n  2. Thus we need 5 additions to generate the 6th
Fibonacci number. However, a recursive program to generate the 6th Fibonacci number needs:
(a) 12 additions
(b) 11 additions
(c) 10 additions
(d) None of the above
Ans:
Part II: True/False answers (10 marks = 2 marks × 5)
For this part, clearly write down if each asserted statement is TRUE or FALSE. You must write “TRUE”
or “FALSE” not “T” or “F”.
1. This question refers to Lab 1. The extended GCD algorithm determines integers u and v for a pair of
positive integers m and n such that um + vn = gcd(m, n).
Assertion: The reason that it works correctly is that at each step inside the loop that tests for
termination we maintain a pair of integers u and v such that um + vn= current remainder.
Ans:
2. Suppose the (worst-case) time-complexity T(n) of a certain algorithm, where n is the input size, is
expressed by the following recurrence relation:
T(n) = T(n − 1) + n − 1, for n > 1
T(1) = 0
Assertion The claim is that T(n) = O(n).
Ans:
3. Consider the follwing sequence of integers: 3,2,5,-16,3,1,-5,10,-12,6,2,-7.
Assertion: The above sequence has 2 different maximum contiguous subsequences each having a value
of 10.
Ans:
4. Suppose we implement a queue using an array, where the front and back of the queue are movable,
but we ensure that front  back.
Assertion: In such an implementation both the enqueue and dequeue operations take O(1) time.
Ans:
5. Consder the following recursive program segment:
//assume: m  n
procedure mystery(m,n){
if n=0 or n=m return 1;
else return mystery(m-1, n) + mystery(m-1, n-1);
}
Assertion: The output of the above procedure on the call mystery(6,4) is 15
Ans:

Part III: Short answers (20 marks = 5 marks × 4)
For this part, give brief answers. The space provided after each question is an upper bound on the length of
your answer!
1. For the input m = 21 and n = 13 to the extended GCD algorithm that you implemented in Lab 1,
find u and v such that u  21 + v  13 = gcd(21, 13) = 1. Show all steps leading to the result, that is,
simulate the algorithm you implemented on this input. Just the final answer carries no credit.
Ans:
2. Give a big-Oh analysis of the running time of the following program fragment:
for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) for(int k = 0; k < j; k++) sum++; Ans: 3. An array A[0..n − 1] contains n distinct entries, with each entry lying in the range [0, n]. This means that one of the numbers in the given range is not an array entry. Suggest an efficient algorithm for determining which one it is, under the restriction that you are allowed only a few bytes of extra memory (meaning that you don’t have enough memory for creating another array of the size of A). What is the time-complexity of your algorithm ? Ans: 4. We discussed in class how we can use a stack to check if a string made up of open, “(”, and closed, “)”, parentheses is balanced. Simulate this algorithm on the input string “((()))(())()” to determine if it is balanced or not. (this means you must explicitly write down the sequence of pushes and pops that the algorithm would generate). Ans: 5. We discussed in class an implementation (from your textbook) of the dynamic programming approach for making change for k cents using coins of denominations c1, c2, c3, .., cn. In this implemenation two arrays are used: one for recording the last coin used to make change for j cents, j  k, and another for recording the minimum number of coins used. Follow this approach to determine the fewest coins needed to make change for 13 cents, using coins of denominations 1,5,10,25. Show all details; this means working through this implementation for the input value 13. If you just write down the answer without showing any of the work, you will receive no credit.