Midterm - Spring 2017 PDF

Preview

Summary

Midterm - Spring 2017...

Description

CS 3510: Design and Analysis of Algorithms Section A, Spring 2017

Midterm Name:

Notes: 1. Please don’t write a program when you describe an algorithm. You should give an idea of what the algorithm does and then discuss the details of how your algorithm does specific tasks. If you give pseudo-code, you should explain your code. 2. For every algorithm that you are asked to describe, please clearly list the steps of your algorithm and explain its correctness and runtime behavior. We recommend separating the algorithm, correctness argument, and runtime analysis into three paragraphs. 3. You can assume that basic operations on integers which are not described to have a variable length (addition, multiplatication, subtraction, floor, ceiling, absolute value, comparison of less than, greater than, or equals, and anything you can form out of a constant number of these) can be done in constant time. You can also assume that, given i, you can read ai from a list a1 , ...an in constant time.

1. ANSWER: (a) Since we have p = 13 and q = 5, we get N = pq = 65. The public key e is given to be 7, and the private key d can be calculated as: d = e−1

mod (p − 1)(q − 1) = 7−1

mod (12 × 4) = 7−1

mod 48

Observe that 7 × 7 = 49 = 48 + 1, and hence 7 × 7 mod 48 = 49 mod 48 = 1, which means that 7−1 mod 48 = 7. Thus we get d = 7. (b) Once we have d, we can decrypt the encrypted message. The RSA formulation gives us: (X e )d

mod N = X

Hence we get 27 mod 65 = X, or X = 128 mod 65 = 63.

2. ANSWER: First examine the middle element A[n/2]. If A[n/2] = n/2, we are done. If A[n/2] > n/2, then every subsequent element will also be bigger than its index since the array values grow at least as fast as the indices. Similarly, if A[n/2] < n/2, then every previous element in the array will be less than its index by the same reasoning. So after the comparison, we only need to examine half of the array. We can recurse on the appropriate half of the array. If we continue this division until we get down to a single element and this element does not have the desired property, then such an element does not exist in A. We do a constant amount of work with each function call. So our recurrence relation is T (n) = T (n/2) + O(1), which solves to T (n) = O(log n).

3. ANSWER: Given any two numbers x and y, we have the following property: gcd(x, y) × lcm(x, y) = x × y Thus, the following algorithm can find the LCM: • Run a multiplication algorithm to find the product of the two numbers, xy. • Find gcd(x, y) using Euclid’s algorithm • Return LCM(x, y) =

xy gcd(x,y )

The gcd can be found using Euclid’s algorithm in O(n3 ) time if n is the maximum number of bits in x and y. The product of xy can be computed in O(n2 ) time. Finally, dividing the product xy by the gcd can also be done in O(n2 ), since the number of bits in xy is at most 2n, and the number of bits in their gcd is at most n. Hence, the overall running time of this algorithm is O(n3 ).

4. ANSWER: If the graph has a starting point, then it must have only one source SCC (since two source SCCs are not reachable from each other), which must contain the starting point (if it’s in any other SCC, there is no path from the starting point to the source SCC). Morever, in this case every vertex in the source SCC will be a starting point. The algorithm is then simply to perform DFS starting from any node and mark the vertex with the highest post value. This must be in a source SCC. We now again run a DFS from this vertex to check if we can reach all nodes. Since the algorithm just uses decomposition into SCCs and DFS, the running time is linear....