Question

1) 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

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

3)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

Answer 1

PLEASE FIND THE ANSWERS BELOW.

In the third problem, we got an EMPTY Stack in the end.

Hence, the input string is accepted.!!