Every True or False

Question 1

The time complexity of an algorithm can be Ω(n) and O(n^2)

Answer 1

TRUE

Question 2

Interpolation search is faster on average than binary search.

Answer 2

TRUE

Question 3

Given an unsorted array of n integers, the median element in the array can be found in Θ(n) time in the average-case

Answer 3

TRUE

Question 4

Even if we consider algorithms that run on quantum computers, no algorithm can factor an integer into its prime factors in polynomial time.

Answer 4

FALSE

Question 5

The asymptotic time complexity for adding two n-bit integers is Θ(n).

Answer 5

TRUE

Question 6

Timesort is a hybrid of Merge Sort and Insertion Sort, and like both Merge Sort and Insertion Sort, it is a stable sorting algorithm.

Answer 6

TRUE

Question 7

In a binary heap (considered as a tree), any two leaf nodes have either the same depth or depths differing by one

Answer 7

TRUE

Question 8

Given an array of 1,000,000 records in which only a few are out of order and they are not far from their correct position, the best choice of a sorting algorithm is Insertion sort because the array is almost sorted.

Answer 8

TRUE

Insertion sort is an adaptive sorting algorithm.

Question 9

A function f(n) can be O(n^2) and Ω(n)

Answer 9

TRUE

Question 10

A graph G = (V,E) is said to be sparse if |E| = O(|V|)

Answer 10

TRUE

Question 11

For a priority queue implemented as a binary heap, the two operations of inserting an element and removing an element (and maintaining the heap property) each have O(log n) complexity, where n is the size of the priority queue.

Answer 11

TRUE

Question 12

Prim’s algorithm can find a minimal spanning tree of a graph only if the graph is undirected.

Answer 12

FALSE

Question 13

There is an algorithm that tests whether a graph G = (V,E) is acyclic in worst-case time complexity O(V+E)

Answer 13

TRUE

DPS&raquo_space; O(V+E)

Question 14

Breadth first search uses a stack

Answer 14

FALSE

Uses a QUEUE.

Question 15

An optimal solution to the fractional knapsack problem can be found by a greedy algorithm, whereas an optimal solution to the 0/1 knapsack problem cannot.

Answer 15

TRUE

Question 16

The shortest path between two vertices in a minimum-spanning tree is always the shortest path between the two vertices in the full graph.

Answer 16

FALSE

Question 17

The Bellman-Ford algorithm, which solves the single-source shortest-path problem in a graph with negative weight edges but no negative cycles, has an asymptotic complexity of Θ(V*E) regardless of whether the graph is sparse or dense.

Answer 17

TRUE

Question 18

The single-source shortest path in an acyclic graph can be solved in Θ(V+E) time, even if the graph has negative-cost weights.

Answer 18

TRUE

Question 19

The single-source longest-path problem in a graph is just as easy to solve as the single source-path problem in the same graph.

Answer 19

FALSE

Question 20

1 + 2 + 3 + . . . + (n-1) + n = O(n)

Answer 20

FALSE

Question 21

Merge sort is an in-place algorithm.

Answer 21

FALSE

Question 22

The boolean satisfiability problem can be solved by a deterministic polynomial-time algorithm if and only if P = NP.

Answer 22

TRUE

Question 23

Any problem that in the complexity class P is also in the complexity class NP.

Answer 23

TRUE

Question 24

If a problem is NP-Hard, it is also NP-complete.

Answer 24

FALSE