Unit 6 Review (Algorithms)

Unit 6 Review (Algorithms)

By Samuel Stansbery

Multiple Choice

Which of the following is an example of the use of heuristics?

• Trying every possible combination of letters when unscrambling a word

• Considering each possible move when playing chess

• Using the formula “area=length x width” to find the area of a rectangle

• Playing chess using a defensive strategy that has often been successful for you

Multiple Choice

A binary search is to be performed on the list:

3, 5, 9, 10, 23

How many comparisons would it take to find the number 9?

• 1

• 3

• 4

• It can't find the number 9

Multiple Choice

A linear search is to be performed on the list:

12, 6, 8, 1, 3

How many comparisons would it take to find the number 1?

• 1

• 2

• 3

• 4

Multiple Choice

Identify the description of a binary search.

• Put the elements in order, check each item in turn

• Order elements,compare middle value,split list in order&loop

• Elements do not need to be in order, check each item in turn

• Randomize data, compare middle value, split list in order & loop

Multiple Choice

Identify the description of a linear search.

• Put the elements in order, check each item in turn

• Order elements,compare middle value,split list in order&loop

• Elements do not need to be in order, check each item in turn

• Randomize data, compare middle value, split list in order & loop

Multiple Choice

What is the largest number of comparisons needed to perform a binary search on an array with 42 elements?

• 2

• 5

• 6

• 41

• 42

Multiple Choice

We are searching for a number key in a sorted list that has n elements. Under what circumstances will Linear Search / Sequential Search be more efficient than Binary Search?

• key is the last element in the array

• key is in the middle of the array

• n is very large

• key is the first element in the array

• key does not exist in the array

Multiple Choice

A robot is programming a new game called “Open the box!” You give him a number and he tries to open a numbered box. He’s using Binary Search to accomplish this. Unfortunately, the boxes are not sorted. They are in the following order:

1, 3, 6, 9, 14, 10, 21

Which box can NEVER be found using binary search?

• 9

• 6

• 14

• 10

Multiple Choice

Any algorithm whose efficiency includes an n2, n3, n4 … is called ___________.

• Problem

• Polynomial

• Pseudocode

• Efficiency

Multiple Choice

Any algorithm whose efficiency includes an 2n, 3n, 4n … is called ______________.

• Problem

• Polynomial

• Exponential

• Efficiency

Multiple Choice

Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time.

• Reasonable Time

• Unreasonable Time

Multiple Choice

Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.

• Reasonable Time

• Unreasonable Time

Multiple Choice

Provides a "good enough" solution to a problem when an actual solution is impractical or impossible.

• Heuristic

• Undecidable Problem

• Unreasonable Time

• Reasonable Time

Multiple Choice

A problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.

• Heuristic

• Undecidable Problem

• Unreasonable Time

• Reasonable Time

Multiple Choice

Programs run in order, one command at a time.

• Sequential Computing

• Parallel Computing

• Distributed Computing

• Speedup

Multiple Choice

Programs are broken into small pieces, some of which are run simultaneously.

• Sequential Computing

• Parallel Computing

• Distributed Computing

• Speedup

Multiple Choice

The time used to complete a task sequentially divided by the time to complete a task in parallel

• Sequential Computing

• Parallel Computing

• Distributed Computing

• Speedup

Multiple Choice

A parallel algorithm still contains some sequential portions so the benefits of adding more processors will go down and eventually the speedup reaches a limit.

• True

• False

Multiple Choice

The impacts of running a parallel algorithm on a large number of computers includes:

• less time to run and more efficiency

• less time to run but not more efficiency

• more time to run and less efficiency

Multiple Choice

If the sequential algorithm processing time was 40 seconds, and a parallel's algorithm processing time was 20 seconds, then what is the speed up? (sequential time/parallel time)

• 80

• 2

• 1/2

• 20

Multiple Choice

A school is designing a new bus route and are deciding where to put the different bus stops. They want to pick the collection of locations that maximizes the amount of students at a pick up to at least 2 . What term best defines the kind of problem?

• A decision problem

• An undecidable problem

• An optimization problem

• An efficiency problem