CSP Unit 6 Algorithms Assessment

Which of the following is true of algorithms?

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

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

1. Wake up

2. Brush teeth

3. Put on shirt

4. Put on pants

5. Put on socks

6. Put on shoes

7. Tie shoes

Which concept does this algorithm best demonstrate?

Sequencing.

Which of these algorithms will move the robot along the same path as the algorithm below?

REPEAT 2 TIMES

{

REPEAT 3 TIMES

{

MOVE_FORWARD()

}

ROTATE_LEFT()

MOVE_FORWARD()

ROTATE_RIGHT()

}

REPEAT 2 TIMES

{

MOVE_FORWARD()

MOVE_FORWARD()

MOVE_FORWARD()

ROTATE_LEFT()

MOVE_FORWARD()

ROTATE_RIGHT()

}

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?

An optimization problem.

The algorithm below is used to find the largest element in a list of numbers.

By modifying one of the lines in the program it is possible to make the algorithm find the smallest element. Which line would need to be modified and how?

01 target <- list[1]

02 FOR EACH num IN list

03 {

04 IF(num > target)

05 {

06 target <- num

07 }

08 }

09 DISPLAY(target)

Line 04 becomes IF (num < target).

Which of the following algorithms is the same as the flowchart shown below?

myNum <- RANDOM (1, 10)

REPEAT UNTIL (myNum > 8)

{

DISPLAY (myNum)

myNum <- RANDOM (1, 10)

}

DISPLAY ("Done")

This graph shows the efficiencies of two different algorithms that solve the same problem. Which of the following is most efficient?

The algorithms have different efficiencies depending on the input size.

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?

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

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

Exponential.

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

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?

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]

3

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

II & III

A software company used to run an algorithm sequentially on one server. As more users start using their app, the company decided to rewrite the program to be parallel. It is now run on four separate servers instead of one Thanks to the use of a parallel algorithm, the same process that used to take 40 minutes to run now only requires 20 minutes.

The company is considering purchasing additional computers to decrease the time the program runs even further. Which of the following best describes the impacts of running the parallel algorithm on an even larger number of computers?

The algorithm will likely require less time to run though the improvements in efficiency will not be as significant as before.

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?

4 minutes