APCSP - Unit 5 Flashcards
For searching in an unordered list, which search algorithm is a better choice?
Linear
For searching in an ordered list, which search algorithm is the better choice?
Binary
When would a binary search algorithm be helpful?
Looking up a person’s number in the phone book given their full name
Looking up a word in the dictionary.
When could a linear search algorithm be useful?
Guessing a secret number between 1 and 100
Looking up a person’s name in the phone book given the person’s phone number.
In a sorted list of numbers containing 500 elements, what number would be the closest to the maximum number of list elements that will be examined when performing a binary search for a value in the list.
9
In the bubble sort demo, 13 cards are being sorted. How many passes does this version of the algorithm require to sort the cards?
13
When would a bubble sort algorithm provide an appropriate solution?
Arranging books on a bookshelf by the author’s last name.
Sorting a stack of paper money into denominations–i.e., $1, $5, $10, etc.
Suppose you are sorting the following list of numbers in ascending order using the bubble sort:
[16, 4, 18, -3, 5, 2, 10, 26, 20, 8]
After the first pass through the numbers, what value would appear on the right of the list (replacing the 8)?
26
Suppose you are sorting the following list of words into alphabetical order using bubble sort:
[dog, cat, horse, whale, deer, fox]
After the first pass of the list, what word would appear on the right of the list?
Whale
Suppose you are sorting the following list of words into alphabetical order using bubble sort:
[papaya, orange, lemon, banana, zucchini, tomato, apple, squash, pumpkin]
What would be the correct order of the list after two passes through the list?
Papaya, orange, lemon, banana, apple, squash, pumpkin, tomato, zucchini.
If you were using binary search to find the number 14 in the following list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], how many iterations would be required to find 14 in the list?
3
What does an algorithm’s efficiency refer to?
How long it takes to arrange values in order.
What does it mean to say that a bucket sort is more efficient than a bubble sort?
As the size of the list grows, bucket sort will be faster than the bubble sort.
What characteristics are true of a bubble sort?
A comparison based algorithm, a quadratic algorithm.
What characteristics are true of a bucket sort?
More efficient than a bubble sort. A linear algorithm.
Under what condition would it be most beneficial to use a heuristic approach to solve a problem.
When the problem cannot be solved within a reasonable amount of time and an approximate solution is acceptable.
Consider an algorithm to solve a problem that takes 160 seconds to run on one processor. This algorithm can be divided among two processors to solve the same problem in 100 seconds. What is the speedup for this parallel algorithm.
1.6
What are the three types of control structures found in algorithms?
Sequence, Selection, Repetition
For what reason would you retain your search history?
Retain it for convenience to easily get back to websites.
For what reason would you delete your search history.
Delete for privacy concerns.
Describe the significance of the global variable index. How was indexing used with lists in our quiz app?
The index variable is used with all of the lists to select a particular item. The items in the list at the same index are related to one another. In the quiz app, the indexing allows us to move from question to question.
