Algorithms - Test 1

15n^1/5 = O(log n)

False, n^15 grows faster than log n. n^15 is Omega(log n)

Binary searching a specific element in a sorted n-element array is O(log n)

True

If f = O(g), then g = O(f) cannot be true

False, f is both O(g) and Omega(g), and g is both O(f) and Omega(f)

In analyzing the asymptotic complexity of f(n) in Big-O, we only need to consider the highest term of f(n)

True, the term with the highest time complexity dominates

In analyzing the asymptotic complexity of f(n), we should replace all constant factors with 1

True, this is because the constant factor c in the definition

Linearly searching a specific element in an n-element array is O(n)

True, checking a length n array from the first to the last element takes O(n)

Locating the value of the 100th element in an n-element array (n is at least 100) is O(1)

True, obtaining the datum from a specific memory location takes O(1) time

The code segment below finds the greatest number from a, an array of 500 integers. Its time complexity is Theta(n).

greatest = a[0]

for i from 1 to 499:

if greatest < a[i]:

greatest = a[i]

False, the loop body runs a constant (499) times only

The eighth Fibonacci number is 13

True

The recursive implementation of finding the n-th Fibonacci number is mathematically correct. Therefore, we can apply it in practice even when n is big

False, the algorithm is mathematically correct but it is exponential and impractical when n is big.

The time complexity of a double loop is O(n^2) always

False, it is true when the loop indexes are n. When the loop indexes are constant, its time complexity is Theta(1)

There is a linear algorithm to find the n-th Fibonacci number

True, there is one in the lecture notes (slide 13, ch. 0)

Nothing needs to be agreed in a symmetric cryptosystem

False, the key must be agreed in symmetric cryptosystem

An encrypt function should be a bijection

True, we need an inverse function to decrypt it, so an encryption function should be a bijection

The multiplicative inverse of 7 in Z11 is 5

False, 35 mod 11 = 2 (not 1)

Alice and Bob may establish a secure communication even they have never known each other before

True, they can do it with an asymmetric cryptosystem

Alice must have both public and private keys for her to send a message to Bob

False, Alice only needs the public key to send her message

The security of RSA relies on the fact: it is computationally hard to factor a large integer

True, this is because of that the best known algorithm is exponential to factorize a large integer

Proposition: Ax E Z37 ^ x != 0, then x has a multiplicative inverse

True, because 37 is prime, any nonzero number in the ring is relatively prime to 37

Proposition: Ax E Z77 ^ x != 0, then x has a multiplicative inverse

False, any multiples of 7 or 11 do not have inverse in the ring (77 is not prime)

The integer pair (77, 5) can be a public key in RSA

False, because 5 is not relative prime to phi = (7-1)(11-1) = 60, it does not have an inverse in the ring. (e must be relative prime to phi, and phi = (p - 1)(q-1). (n = pq)

If (33, 3) is a public key in RSA, then it encrypts 5 as 23.

False, 5^3 mod 33 = 125 mod 33 = 26 not 23

Breaking RSA is simple in theory but hard in practice when n is large

True, it is simple in theory. It is not practical because the best known algorithm of factorizing a large integer is exponential.

It is very expensive computationally to evaluate a^n mod m when a, m, and n are very large integers

False, the fast modulo exponentiation algorithm is logarithmic, which is VERY efficient

Let m and n be two positive integers. Then, the most efficient algorithm available to find gcd(m, n) is O(log (max(m, n)).

True, Euclid's gcd algorithm is logarithmic

There is no integer solution for the equation 412x + 260y = 5

True, From the extended Euclid's algorithm, we know ax + by = gcd(a, b) has integer solution. In this question, a = 412 and b = 260. Since gcd(412, 260) = 4 not 5, the equation does not have any integer solution

The multiplicative inverse of 12^35 mod 37 = 12

True, Because 37 is prime, 12 * 12^35 mod 37 = 12^36 mod 37 = 1 according to Fermat's Little Theorem

If n is prime, then Aa E Zn a != 0, a^n-1 mod n = 1

True, this is Fermat's Little Theorem

If 3a E Zn and a^n-1 mod n = 1, then n is prime

False

If a^n-1 mod n = 1 for k different a E Zn, then the probability of n being prime is 1 - 1/2^k. Note: ignore Carmichael numbers

True, the probability of a composite number n passing a Fermat's test is less than 1/2. So, the probability of n passing k Fermat's tests is 1/2^k. Thus, the probability of n prime is 1-1/2^k.

A pseudo prime number is prime mathematically

False, a pseudo prime number is NOT mathematically prime. It can be composite but with a very small probability

If (33, 3) is a public key in RSA, then the private key is 7.

True

With a binary tree to illustrate merge sorting an n-item array, the height of the tree is Theta(n).

False

Sorting an n-item array with merge sort. The merge step is O(n)

True

An algorithm developed with the divide-and-conquer paradigm can be usually illustrated as a branch tree

True

Algorithms developed with divide-and-conquer paradigm are often implemented recursively

True

Both bubble sort and merge sort algorithms are quadratic, i.e., Theta(n^2)

False

Merge sort always perform better than bubble sort

False

In divide-and-conquer approach, the divide step is top-down and the conquer step is a bottom-up

True

Even in the best case, bubble sort is still less efficient than quick sort

False

In the worst case, quick sort can be quadratic

True

Applying divide-and-conquer, one may always improve computational efficiency

False

In analyzing asymptotic time complexity of a recursively defined algorithm, one may apply the master's theorem if the conquer step is O(n^d)

True

A recursive algorithm can be computationally efficient

True

Fast Fourior transformation algorithm is developed with divide-and-conquer

True

Rewrite a mathematical expression from its simplest form to a more complicated one may lead to improvement of computational efficiency.

True

How do we analyze time complexity of divide-and-conquer algorithm

the master theorem

The height h of the tree for merge sort is

O(log n)

The time complexity for merge at each level is

O(n)

Merge-sort has a time complexity of

O(n log n)

some sorting algorithms include

merge, bubble, selection, insertion, quick, and heap

the matrix multiplication algorithm is

O(n^3)

Discrete Fourier Transformation (DFT) is

quadratic