7. Algorithms

Question 1

A(n) ____ is a sequence of steps that solves a problem, generating correct output for any valid input values.

Answer 1

algorithm

Question 2

A(n) ____ problem specifies an input, a question about the input that can be answered using a computer, and the desired output.

Answer 2

computational

Question 3

An efficient algorithm is one whose runtime increases no more than ____ with respect to the input size.

Answer 3

polynomially

Question 4

____ problems are a set of problems for which no known efficient algorithm exists.

Answer 4

NP-complete

Question 5

One of the three characteristics of an NP-complete problem is that no ____ algorithm has been found to solve an NP-complete problem.

Answer 5

efficient

Question 6

One of the three characteristics of an NP-complete problem is that no one has proven that an efficient algorithm to solve an NP-complete problem is ____.

Answer 6

impossible

Question 7

One of the three characteristics of an NP-complete problem is that if an efficient algorithm exists for one NP-complete problem, then ____ NP-complete problems can be solved efficiently.

Answer 7

all

Question 8

____ is the amount of resources used by an algorithm.

Answer 8

Computational complexity

Question 9

An algorithm’s computational complexity includes ____ and ____.

Answer 9

runtime, memory usage

Question 10

An algorithm’s ____ is the scenario where the algorithm does the minimum possible number of operations. An algorithm’s ____ is the scenario where the algorithm does the maximum possible number of operations.

Answer 10

best case, worst case

Question 11

Complexity analysis always treats the input data size as a(n) ____.

Answer 11

variable

Question 12

An algorithm’s ____ complexity is a function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N.

Answer 12

space

Question 13

An algorithm’s ____ space complexity is the space complexity not including the input data.

Answer 13

auxiliary

Question 14

____ is a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.

Answer 14

Linear search

Question 15

An algorithm’s ____ is the time the algorithm takes to execute.

Answer 15

runtime

Question 16

Binary search is a faster algorithm for searching a list if the list’s elements are ____ and ____ accessible (such as an array).

Answer 16

sorted, directly

Question 17

For an N element list, the maximum number of steps required to reduce the search space to an empty sublist using binary search is ____.

Answer 17

(log base 2 of N) + 1

Question 18

Compared to a linear search, binary search is incredibly efficient in finding an element within a(n) ____ list.

Answer 18

sorted

Question 19

A(n) ____ is a technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.

Answer 19

heuristic

Question 20

An example of a problem that a heuristic algorithm can solve is the ____ problem.

Answer 20

0-1 knapsack problem

“0-1” means that 0 or 1 of each item can be taken.

For this problem a heuristic algorithm would always take the most valuable item that fits in the knapsack’s remaining space.