Unit 6 Review

Which of the following is true of algorithms?

• Algorithms may have an infinite set of instructions

• Algorithms must be expressed using a programming language

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

• Every problem can be solved with an algorithm

The following algorithm is followed by a person every morning when they get up from bed to go to school

Wake up

Brush teeth

Put on shirt

Put on pants

Put on socks

Put on shoes

Tie shoes

Which concept does this algorithm BEST demonstrate?

• Sequencing

• Selection

• Iteration

• Execution

A town government is designing a new bus system. The planners are deciding where to put the different bus stops. They want to pick a set of bus stop locations that will minimize the distance anyone needs to walk in order to get to any bus stop in town. What term best defines this kind of problem?

• A decision problem

• An optimization problem

• An undecidable problem

• An efficiency problem

A school is creating class schedules for its students. The students submit their requested courses and then a program will be designed to find the optimal schedule for all students.

The school has determined that finding the absolute best schedule cannot be solved in a reasonable time. Instead they have decided to use a simpler algorithm that produces a good but non-optimal schedule in a more reasonable amount of time.

Which principle does this decision best demonstrate?

• Unreasonable algorithms may sometimes also be undecidable

• Heuristics can be used to solve some problems for which no reasonable algorithm exists

• Two algorithms that solve the same problem must also have the same efficiency

• Approximate solutions are often identical to optimal solutions

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

• Linear

• Constant

• Polynomial

• Exponential

Which of the following best describes the existence of undecidable problems?

• Undecidable problems are problems for which more than one algorithm solves the problem and computer scientists have not yet chosen the algorithm they believe is best

• Undecidable problems are problems for which an algorithm can be written that will produce the same output for at least two possible inputs

• Undecidable problems are problems for which an algorithm can be written that produces a correct output for all inputs but in an unreasonable time

• An undecidable problem is a problem for which no algorithm can be constructed that always produces a correct output

A group of students writes their names and unique student ID numbers on sheets of paper. The sheets are then randomly placed in a stack.

Their teacher is looking to see if a specific ID number is included in the stack. Which of the following best describes whether their teacher should use a linear or a binary search?

• The teacher could use either type of search though the linear search is likely to be faster

• The teacher could use either type of search though the binary search is likely to be faster

• Neither type of search will work since the data is numeric

• Only the linear search will work since the data has not been sorted

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

[1, 5, 20, 50, 51, 80, 99]

• 1

• 3

• 6

• 7

Which of the following is a benefit of parallel and distributed computing?

• Distributed computing typically requires fewer computers

• Distributed computing can be used when parallel solutions are not possible

• Parallel computing scales more effectively than sequential computing

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

A sequential algorithm is broken into three stages

Sequential Algorithm Time

Download stage: 1 minute Sorting stage: 6 minutes Upload stage: 1 minute

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

Parallel Algorithm Time

Download stage: 1 minute Sorting stage: 2 minutes Upload stage: 1 minute

What is the speedup of the parallel solution?

• 6 minutes

• 4 minutes

• 2

• 3