Advanced Algorithms Theoretical Questions

What is the time complexity of x^n?
Can we optimize it?

• O(n^2).
  No we can't.

• O(n).

  By optimizing it using “Exponentiation by Squaring”, it becomes O(log n).

• O(n).

  No we can't.

• O(n*log n).

  By optimizing it using “Exponentiation by Squaring”, it becomes O(log n).

What is the maximum number of id[] array entries that can change (from one value to a different value) during one call to union when using the quick-find data structure on n elements?

• log n

• 1

• n - 1

• n

What is the time complexity of "union" and "find" operation in Quick-Find?

• Union: O(n)

  Find: O(1)

• Union: O(n)

  Find: O(n)

• Union: O(1)

  Find: O(n)

• Union: O(n)

  Find: O(log n)

Consider the maximum number of array accesses during a find operation when using the quick-union data structure on 𝑛 elements. How does this quantity grow as function of 𝑛?

• constant

• logarithmic

• quadratic

• linear

What is the time complexity of "union" and "find" operations in Quick-Union?

• Union: O(n)

  Find: O(n)

• Union: O(n)

  Find: O(1)

• Union: O(1)

  Find: O(n)

• Union: O(log n)

  Find: O(n)

Time complexity of Weighted Quick-Union?

• Union: O(log n)

  Find: O(log n)

• Union: O(log n)

  Find: O(n)

• Union: O(n)

  Find: O(log n)

• Union: O(1)

  Find: O(log n)

What does adjacent mean in a graph?

• Two vertices connected directly by an edge.

• Two vertices connected undirectly.

• Two vertices connected by something.

• Two vertices connected but not directly.

A cycle that uses each edge of a graph exactly once is called:

• An Euler tour

• A Kok-Jailau tour

• A Hamilion tour

• An Octopus tour

What is the space complexity for Adjacency matrix?

• O(V^2)

• O(E+V)

• O(1)

• O(E logV)

What is the space complexity for Adjacency list?

• O(E+V)

• O(V^2)

• O(1)

• O(E logV)