Crowdly

Ω(n²)

Θ(n²)

Ω(log n)

Ω(n)

Which of the following statements is a characteristic of an NP-Complete problem?

It cannot be verified in polynomial time.

It is guaranteed to have a linear-time approximation algorithm.

All instances of the problem are tractable via dynamic programming.

It can be solved in polynomial time.

It is in NP, and every problem in NP can be reduced to it in polynomial time.

Find the asymptotic running time for the recurrence relation T[n]=2T[n/4]+n^0.51 and then select every correct answer below (more than one choice could be selected).

In a polynomial-time reduction from the Hamiltonian Cycle problem to the Traveling Salesman Problem (TSP), what does the weight of an edge in the TSP instance typically represent as covered in lectures?

Weight of 0 if the edge is not in the Hamiltonian Cycle, and weight of 1 if the edge is in a Hamiltonian cycle.

The distance between the two cities represented by the edge.

The cost of traversing that edge in the Hamiltonian Cycle.

The number of cities connected by that edge.

Weight of 1 if the edge is not in the Hamiltonian Cycle, and weight of 0 if the edge is in a Hamiltonian cycle.

Which one below is NOT true about linear probing?

Linear probing is fast if the load factor is low.

Keys do not tend to cluster in linear probing.

Linear probing is cache-friendly.

Linear probing is fast if the keys are small.

Which statement is true about the recurrence relation T(m)= 8T(m/3) + 2^m

This is Case 2 of the Master Method and the solution is T(m) = Θ(m log(m))

This is Case 1 of the Master Method and the solution is T(m) = Θ(m³)

This is Case 3 of the Master Method and the solution is T(m) = Θ(2^m)

This is Case 1 of the Master Method and the solution is T(m) = Θ(2^m log(m))

This is Case 2 of the Master Method and the solution is T(m) = Θ(2^m)

This is Case 3 of the Master Method and the solution is T(m) = Θ(2^m log(m))

what is the tightest bound on the time complexity for efficiently computing the strongly connected components (SCCs) of the graph?

Given a directed graph G(V,E), where V is the set of vertices and E is the set of directed edges,

O ((V+E)logV)

O (V*E)

O (V+E)logE)

O (V+E)

O (E²)

None of these

In the Knuth-Morris-Pratt algorithm, what is the running time to compute the lps[] array if n,m are the sizes of the text and pattern, respectively? (Choose the tightest bound.)

Consider an undirected graph G(V,E,W), where V represents the nodes, E represents the undirected edges, and W represents the edge weights. What is the worst-case computational complexity of Dijkstra's single-source shortest path algorithm when using a heap data structure? Select the tightest bound.

O (V*E)

O (V logV)

None of these.

O ((V+E)logV))

O (E logE)

O ((E+V)+W*logE))

O((V+E)logE))

How many bits would be saved in a message if we use Huffman coding as a compression technique to encode the message before transmitting it over the network, given the message consists of the characters with their corresponding frequencies as follows: (Character, Frequency) a: 21, b: 4, c: 2, d: 3, e: 10, f: 20. Note that each character in the original message requires 1 byte (8 bits).

None of these.

132

348

480

240