Algorithms Quiz

Suppose a large group of people in a room were all born in the same year. Which of the following algorithms will identify the correct people who have the earliest birthday based on just the month and day? For example, a person born on February 10 is considered to have an earlier birthday than a person born on March 5. Which of the three algorithms will identify the correct people?

I. All the people in the room stand up. All standing people form pairs where possible, leaving at most one person not part of a pair. For each pair, the person with the earlier birthday remains standing, while the other person in the pair sits down. If there is a tie, both people sit down. Any individual not part of a pair remains standing. Continue doing this until only one person remains standing. That person has the earliest birthday.

II. All the people in the room stand up. All standing people form pairs with another standing person that they have not previously been paired with where possible, leaving at most one person not part of a pair. For each pair, the person with the earlier birthday remains standing, while the other person in the pair sits down. If there is a tie, both people in the pair remain standing. Any individual not part of a pair remains standing. Continue doing this until only one person remains standing or all persons standing have the same birthday. Anyone still standing has the earliest birthday.

III. Beginning with the number 1, ask if anyone was born on that day of any month. Continue with the numbers 2, 3, and so on until a positive response is received. If only one person responds, that person has the earliest birthday. If more than one person responds, determine which person was born in the earliest month, and that person or those persons have the earliest birthday

• I only

• II only

• I and II

• II and III

Which of the following algorithms displays the correct distance for all possible values of num1 and num2?

• Step 1:

  Add num1 and num2 and store the result in the variable sum.

   Step 2:    Take the absolute value of sum and display the result.

• Step 1:

  Subtract num1 from num2 and store the result in the variable diff.

  Step 2:

  Take the absolute value of diff and display the result.

• Step 1:

  Take the absolute value of num1 and store it in the variable absNum1.

  Step 2:

  Take the absolute value of num2 and store it in the variable absNum2.

  Step 3:

  Add absNum1 and absNum2 and display the result.

• Step 1:

  Take the absolute value of num1 and store it in the variable absNum1.

  Step 2:

  Take the absolute value of num2 and store it in the variable absNum2.

  Step 3:

  Subtract absNum1 from absNum2 and display the result.

Which of the following algorithms will allow the robot to make a single circuit around the rectangular region of black squares, finishing in the exact location and direction that it started in each of the four grids?

• Step 1:

  Keep moving forward, one square at a time, until the square  to the right of the robot is black.

  Step 2:

  Turn right and move one  square forward.

  Step 3:

  Repeat steps 1 and 2 three more times.

• Step 1:

  Keep moving forward, one square at a time, until  the square to   the right of the robot is no longer black.

  Step 2:

  Turn right and move one      square forward.

    Step 3: Repeat steps 1 and 2 three more times.

• Step 1:

  Move forward three squares.

  Step 2:

  Turn right and move one square forward.

  Step 3: If the square to the right of the robot is black, repeat steps 1 and 2.

• Step 1:

  Move forward three squares.

  Step 2:

  Turn right and move one square forward.

  Step 3:

  If the square to the right of the robot is not black, repeat steps 1 and 2.⁼

The code segment below uses the procedure GoalReached, which evaluates to true if the robot is in the gray square and evaluates to false otherwise.

REPEAT UNTIL (GoalReached ())

{

<MISSING CODE>

}

Which of the following replacements for <MISSING CODE> can be used to move the robot to the gray square?

• REPEAT UNTIL (CAN_MOVE (forward) = false)

  {

  ROTATE_RIGHT ()

  }

  MOVE_FORWARD ()

• REPEAT UNTIL (CAN_MOVE (forward) = false)

  {

  MOVE_FORWARD ()

  }

  ROTATE_RIGHT ()

• REPEAT UNTIL (CAN_MOVE (right))

  {

  ROTATE_RIGHT ()

  }

  MOVE_FORWARD ()

• REPEAT UNTIL (CAN_MOVE (right))

  {

  MOVE_FORWARD ()

  }

  ROTATE_RIGHT ()

A programmer is creating an algorithm that will be used to turn on the motor to open the gate in a parking garage. The specifications for the algorithm are as follows.

• The gate should not open when the time is outside of business hours.

• The motor should not turn on unless the gate sensor is activated.

• The motor should not turn on if the gate is already open.

Which of the following algorithms can be used to open the gate under the appropriate conditions?

• Check if the time is outside of business hours. If it is, check if the gate sensor is activated. If it is, check if the gate is closed. If it is, turn on the motor.

• Check if the time is during business hours. If it is, check if the gate sensor is activated. If it is, check if the gate is open. If it is, turn on the motor.

• Check if the time is during business hours. If it is, check if the gate sensor is activated. If it is not, check if the gate is open. If it is not, turn on the motor.

• Check if the time is during business hours. If it is, check if the gate sensor is activated. If it is, check if the gate is open. If it is not, turn on the motor.

A certain game keeps track of the maximum and minimum scores obtained so far. If num represents the most recent score obtained, which of the following algorithms correctly updates the values of the maximum and the minimum?

• If num is greater than the minimum, set the minimum equal to num. Otherwise, if num is greater than the maximum, set the maximum equal to num.

• If num is less than the minimum, set the minimum equal to num. Otherwise, if num is greater than the maximum, set the maximum equal to num.

• If num is less than the minimum, set the minimum equal to num. Otherwise, if num is less than the maximum, set the maximum equal to num.

• If num is greater than the minimum, set the minimum equal to num. Otherwise, if num is less than the maximum, set the maximum equal to num.

Three different numbers need to be placed in order from least to greatest. For example, if the numbers are ordered 9, 16, 4, they should be reordered as 4, 9, 16. Which of the following algorithms can be used to place any three numbers in the correct order?

• If the first number is greater than the middle number, swap them. Then, if the middle number is greater than the last number, swap them.

• If the first number is greater than the middle number, swap them. Then, if the middle number is greater than the last number, swap them.

• If the first number is greater than the middle number, swap them. Then, if the last number is greater than the last number, swap them. Then, if the first number is greater than the middle number, swap them.

• If the first number is greater than the middle number, swap them. Then, if the middle number is greater than the last number, swap them. Then, if the first number is greater than the middle number, swap them.

Which of the following algorithms display all integers between 1 and 20, inclusive, that are not divisible by 3 ?

SELECT TWO answers.

• Step 1:

  Set x to 0.

   Step 2:

  Increment x by 1.

   Step 3:

  If x is not divisible by 3, then display x.

   Step 4:

  Repeat steps 2 and 3 until x is 20.

• Step 1:

  Set x to 0.

  Step 2: If x is divisible by 3, then display x.Step 3:

  Increment x by 1.

   Step 4: Repeat steps 2 and 3 until x is greater than 20.

• Step 1:

  Set x to 1.

      Step 2: If x is divisible by 3, then do nothing; otherwise display x.Step 3:

  Increment x by 1.

    Step 4: Repeat steps 2 and 3 until x is 20.

• Step 1:

  Set x to 1.

    Step 2: If x is divisible by 3, then do nothing; otherwise display x.Step 3:

  Increment x by 1.

    Step 4: Repeat steps 2 and 3 until x is greater than 20.

A teacher has a goal of displaying the names of 2 students selected at random from a group of 30 students in a classroom. Any possible pair of students should be equally likely to be selected. Which of the following algorithms can be used to accomplish the teacher's goal?

• Step 1:

  Assign each student a unique integer from 1 to 30.

  Step 2:

  Generate a random integer n from 1 to 15.

  Step 3:

  Select the student who is currently assigned integer n and display the student’s name.

  Step 4:

  Generate a new random integer n from 16 to 30.

  Step 5:

  Select the student who is currently assigned integer n and display the student’s name.

• Step 1:

  Assign each student a unique integer from 1 to 30.

  Step 2:

  Generate a random integer n from 1 to 30.

  Step 3:

  Select the student who is currently assigned integer n and display the student’s name.

  Step 4:

  Generate a new random integer n from 1 to 30.

  Step 5:

  Select the student who is currently assigned integer n and display the student’s name.

• Step 1:

  Assign each student a unique integer from 1 to 30.

  Step 2:

  Generate a random odd integer n from 1 to 29.

  Step 3:

  Select the student who is currently assigned integer n and display the student’s name.

  Step 4:

  Generate a new random even integer n from 2 to 30.

  Step 5:

  Select the student who is currently assigned integer n and display the student’s name.

• Step 1:

  Assign each student a unique integer from 1 to 30.

  Step 2:

  Generate a random integer n from 1 to 30.

  Step 3:

  Select the student who is currently assigned integer n and display the student’s name.

  Step 4:

  The student who was selected in the previous step is assigned 0. All other students are reassigned a unique integer from 1 to 29.

  Step 5:

  Generate a new random integer n from 1 to 29.

   Step 6:

  Select the student who is currently assigned integer n and display the student’s name.

The algorithm below is used to simulate the results of flipping a coin 4 times. Consider the goal of determining whether the simulation resulted in an equal number of heads and tails.

Step 1: Initialize the variables heads_counter and flip_counter to 0.

Step 2: A variable coin_flip is randomly assigned a value of either 0 or 1. If coin_flip has the value 0, the coin flip result is heads, so heads_counter is incremented by 1.

Step 3: Increment the value of flip_counter by 1.

Step 4: Repeat steps 2 and 3 until flip_counter equals 4.

Following execution of the algorithm, which of the following expressions indicates that the simulation resulted in an equal number of heads and tails?

• coin_flip = 1

• flip_counter = 1

• flip_counter = 2

• heads_counter = 2