Algorithms

Speedup is when programs run in order, one command at a time.

• True

• False

Answer explanation

False.

Speedup is the time used to complete a task sequentially divided by the time to complete the task in parallel. Sequential Computing is when programs run in order, one command at a time.

Sequential computing is a type of computation where many calculations are carried out simultaneously.

• True

• False

Answer explanation

False. Parallel computing is a type of computation where many calculations are carried out simultaneously.

A computer scientist is analyzing four different algorithms used to sort a list. The table below shows the number of steps each algorithm took to sort lists of different sizes.

Based on the values in the table, which of the algorithms appear to run in reasonable time?

• A

• B

• C

• D

Answer explanation

As the size of the list grows, the number of steps needed to sort the list grows at a linear rate, as the number of steps is equal to 10n

10n for a list of size n

n. This is an example of a polynomial efficiency and indicates that the algorithm runs in a reasonable amount of time.

The number of steps for this algorithm is equal to the length of the list squared, as the number of steps is equal to n

2

n2 for a list of size n

n. This is an example of a polynomial efficiency and indicates that the algorithm runs in a reasonable amount of time.

What is a type of diagram that shows the sequence of steps in an algorithm?

• flow chart

• pie chart

• bar graph

• line graph

Which algorithm will be most useful to guess the number that someone has in their head spanning from 1-100?

• linear search

• binary search

If one would like to read through a large list of names and read every name on the list, which big O notation would you use?

• O(log n)

• O(n)

• O(nlog n)

• O(n!)

A sorted list of numbers contains 200 elements. Which of the following is closest to the maximum number of list elements that will need to be examined when performing a binary search for a particular value in the list?

• 5

• 8

• 100

• 200

Answer explanation

The binary search algorithm starts at the middle of the sorted list and repeatedly eliminates half the elements until the desired value is found or all the elements have been eliminated. For a list with 200 elements, the list will be cut in half a maximum of 7 times (with a total of 8 elements examined). The list starts with 200 elements, then is reduced to 100 elements, then to 50 elements, then to 25 elements, then to 12 elements, then to 6 elements, then to 3 elements, and then, finally, to 1 element.

For which of the following lists can a binary search be used to search for an item in the list?

["blue", "green", "jade", "mauve", "pink"] [5, 5, 5, 5, 6, 7, 8, 8, 8] [10, 5, 3, 2, -4, -8, -9, -12]

• I only

• III only

• I and III only

• I, II and III

Answer explanation

In order for a binary search on a list to work, the list must be sorted. All three lists are sorted (the first one in alphabetical order, the third one in reverse order), so a binary search is appropriate for all of them.

For which of the following situations would it be best to use a heuristic in order to find a solution that runs in a reasonable amount of time?

• Appending a value to a list of n

  elements, which requires no list elements be examined.

• Finding the fastest route that visits every location among n

  locations, which requires n!

  possible routes be examined.

• Performing a binary search for a score in a sorted list of n

  scores, which requires that fewer than n

  scores be examined.

• Performing a linear search for a name in an unsorted database of n

  people, which requires that up to n

  entries be examined.

Answer explanation

As this algorithm has a factorial efficiency, it does not run in a reasonable amount of time. A heuristic approach can be used to find an approximate solution than can run in a reasonable amount of time.

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

• 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 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. Then, if the first number is greater than the middle number, swap them.

Answer explanation

After comparing the first number and the middle number and potentially swapping them, and then comparing the middle number and the last number and potentially swapping them, the largest number will be in the third position. Next, after comparing the first number and the middle number and potentially swapping them, the three numbers will be ordered from least to greatest.