Q1. What does it mean if we claim that f(x) = o(g(x)) as x goes to infinity? Choose one of the following: 1. There exists such constant C that f(x) >= g(x)/C for sufficiently large x. 2. The limit of f(x)/g(x) is equal to 1 as x goes to inifinity. 3. The limit of f(x) - g(x) is equal to 1 as x goes to infinity. 4. The limit of f(x) / g(x) is 0 as x goes to infinity. 5. The limit of g(x)/f(x) is 0 as x goes to infinity.

Q2. Consider the statement 5*N**2 = Theta(15 + N). It is (choose one of the following) 1. True 2. False 3. Can be true or false depending on a particular problem 4. Neither true nor false. 5. Completely meaningless.

Q3. Which of the epxressions included below grows most slowly as N goes to infinity? (choose one)

1. O(N**2) 2. O(N*log(N)) 3. O(N**3*log(N)) 4. O(N) 5. O(log(log(N)))

Q4. Which of the following quantities can server as measures of the size of the problem?

1. Number of loops in the program, number of lines in the loop, number of function or methods in the program. 2. Number of elements in input arrays or lists, number of bits in a binary representation of the argument. 3. Number of elementary operations like additions, multiplications, calling the function by itself, etc.

Q5. Which of the following quantities can server as measures of the complexity of the problem?

1. Number of loops in the program, number of lines in the loop, number of function or methods in the program. 2. Number of elements in input arrays or lists, number of bits in a binary representation of the argument. 3. Number of elementary operations like additions, multiplications, calling the function by itself, etc.

Q6. Which of the following algorithms has the complexity O(log(N))?

1. Fast Fourier Transformation 2. Horner scheme to compute values of polynomials 3. Euclid's algorithm to compute GCDs. 4. Quicksort 5. "Slowsort" which we've developed in the classes.

Q7. To what kind of problems can we apply the Verlet algorithm?

1. Solving recursion relation. 2. Integer optimization problem. 3. Searching for the largest element in an array. 4. Solving ordinary differential equations in physics. 5. Finding Hamiltonian cycles in a graph.

Q8. From the following list of algorithms choose one which has the complexity O(N*log(N)).

1. Implementing matrix multiplication as it is taught at the linear algebra courses. 2. Fast Fourier Transformation 3. Euclid's algorithm to compute GCDs 4. Traveling salesman problem. 5. Horner scheme.

Q9. Why is the most naive recursive version of the algorithm to compute Fibonacci numbers that bad?\

1. It has exponential complexity. 2. It has the complexity O(N**4) 3. It is incorrect. 4. It needlessly computed the same quantities several times. 5. It cannot compute Fibonacci numbers larger than 1000000.

Q10. Which temporal complexity is "worst" (leading to longest time performance for large N):

1. O(log(N)) 2. O(2**N) 3. O(N!) 4. O(log(log(N)) 5. O(N!!)

Q11. Explain why reducing complexity from O(N**2) to O(N*log(N)) can be considered as an achievement.

1. Because the logarithm is a very nice function. 2. Because the linear function grows slowlier than the logarythmic one. 3. Because the logaritmic function grows slowlier than the linear one. 4. For another but unknown reason.

Q12. Why sets seem to be more convenient data structures to represent undirected graphs than the standard Python lists?

1. Because the list are unordered and the sets are ordered 2. Because the sets take less amount of memory. 3. Because the lists are ordered and the sets are not. 4. There is in fact no difference between them.