AP CSP - Unit 6: Lesson 6: Assessment Day

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

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

•   Selection

• Iteration

• Execution

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

• 
• 
• 
• 

A town government is designing a new bus system and are deciding where to put the different bus stops. They want to pick the collection of locations that minimizes the distance anyone needs to walk in order to get to at least one bus stop. What term best defines the kind of problem?

• A decision problem

•   An optimization problem

•   An undecidable problem

•   An efficiency 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?

• Line 01 becomes target <- list[2]

• Line 04 becomes IF (num < target)

• Line 04 becomes IF (num = target)

• Line 01 becomes list[0] <- target

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

• 
• 
• 
• 

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

• These algorithms are equally efficient

• Algorithm A is more efficient than algorithm B

•   Algorithm B is more efficient than algorithm A

•   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?

• 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

• Exponential

•   Polynomial  

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 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

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