CSP Unit 10 Review

Which of these statements about algorithms is FALSE?

• Not every problem can be solved with an algorithm

• Every algorithm can be constructed using combinations of sequencing, selection, and iteration

• Algorithms must be expressed using a programming language

• Algorithms have a finite set of instructions

Which concept does this algorithm BEST demonstrate?

• Execution

• Sequencing

• Selection

• Iteration

The traveling salesman problem is an example of which kind of problem:

• An optimization problem

• A decision problem

• An efficiency problem

• An undecidable problem

We used a heuristic instead of an algorithm to solve the traveling salesman problem because:

• It is an undecidable problem

• No algorithm could have been created

• The algorithm would have been unreasonable

Which algorithm is more efficient when the input size = 10?

• Algorithm A

• Algorithm B

• Their efficiencies are the same

Which of the following algorithmic efficiencies would be considered MOST efficient?

• log

• linear

• polynomial

• exponential

You have a shuffled deck of playing cards and are trying to find a "7". Which type of search should you use?

• binary

• linear

• Either one will work

• Neither one will work

A computer is performing a binary search on the sorted list of 5 numbers below. What is the maximum number of iterations needed to find the item?

[3 , 8 , 10, 11, 13]

• 2

• 3

• 4

• 5

Which of the following are NOT TRUE of parallel and distributed computing?

• Parallel computing scales more effectively than sequential computing

• Distributed computing allows larger problems to be solved quicker

• Distributed computing improves the speed at which an individual computer executes a program

A sequential algorithm to sort cards is broken into three stages

Sequential Algorithm Time

• Shuffle stage: 10 sec

• Sorting stage: 65 sec

• Re-stack stage: 5 sec

A parallel version of the algorithm completes the sorting stage in parallel leading to a new set of times

Parallel Algorithm Time

• Shuffle stage: 10 sec

• Split stage: 5 sec

• Sorting stage: 15 sec

• Re-stack stage: 10 minute

What is the speedup of the parallel solution?

• 2

• 1

• 30 sec

• 5 sec