1.
The "running time" of an algorithm refers to
Correct Answer
B. The number of steps it takes to complete with respect to the size of the input
Explanation
The "running time" of an algorithm refers to the number of steps it takes to complete with respect to the size of the input. This means that the running time of an algorithm is determined by how many operations or instructions the algorithm needs to execute in order to solve a problem, and this can vary depending on the size of the input. It is not related to the time it takes to write the program or the actual time it takes for the program to run.
2.
A loop invariant is
Correct Answer
C. A statement about the data which reflects the progress made at each iteration toward the goal
Explanation
A loop invariant is a statement about the data that remains true before and after each iteration of the loop. It reflects the progress made towards the goal by providing information about the state of the data at each iteration. This statement remains unchanged throughout the loop execution and helps in understanding the behavior and correctness of the loop. By checking the loop invariant, one can ensure that the loop is progressing correctly and approaching the desired outcome.
3.
Let's say you do a google search for "pacman". The "key" in this scenario is:
Correct Answer
C. The word "pacman"
Explanation
The correct answer is the word "pacman" because the question is asking for the key in the scenario of doing a Google search for "pacman". In this scenario, the key refers to the specific term or keyword that is being searched for, which is "pacman" in this case.
4.
A "precondition" with respect to algorithms is:
Correct Answer
C. A true statement that can be made about the data before the algorithm is applied
Explanation
A "precondition" in the context of algorithms refers to a true statement that can be made about the data before the algorithm is applied. It is a condition or requirement that must be satisfied for the algorithm to work correctly. Preconditions help ensure that the input data meets certain criteria or properties necessary for the algorithm to produce the desired output. By checking the preconditions, we can determine if the input data is valid and suitable for the algorithm to be applied.
5.
For linear search, the "best case scenario" (when the algorithm completes with the fewest number of steps) is when:
Correct Answer
A. The first item equals the key
Explanation
In the best case scenario for linear search, the algorithm completes with the fewest number of steps when the first item in the data equals the key. This is because the algorithm starts searching from the beginning of the data, and if the first item is a match, there is no need to continue searching through the rest of the data.
6.
For linear search, the "worst case scenario" (when the algorithm takes the most number of steps) is when:
Correct Answer
C. The data does not contain the key
Explanation
In linear search, the algorithm checks each item in the data sequentially until it finds a match for the key or reaches the end of the data. In the worst case scenario, the key is not present in the data, which means the algorithm will have to check every item in the data before determining that the key is not there. This results in the algorithm taking the most number of steps, making it the worst case scenario for linear search.
7.
For binary search, the "best case scenario" (when the algorithm will completes in the fewest number of steps) is when:
Correct Answer
B. The middle item equals the key
Explanation
The "best case scenario" for binary search is when the middle item in the data equals the key being searched for. In this case, the algorithm can directly find the desired item without having to search through any other items in the data. This results in the fewest number of steps required to complete the search.
8.
For binary search, the "worst case scenario" (when the algorithm takes the most number of steps) is when:
Correct Answer
C. The data does not contain the key
Explanation
In binary search, the algorithm divides the data into halves and compares the middle element with the key being searched. If the middle element is equal to the key, the search is successful. However, if the first item equals the key or the middle item equals the key, the search will terminate early and the algorithm will not need to continue searching the remaining elements. Therefore, the worst case scenario occurs when the data does not contain the key, as the algorithm will have to compare the key with every element in the data before determining that it is not present.
9.
Note that 2^{1} = 2, and 2^{2} = 4, and 2^{3} = 8 and so on.In these relationships the term "log base 2" refers to the exponent.For example, "log base 2 of 8" is 3, and "log base 2 of 4 is 2". We can think of "log base 2 of n" as being the number of times you can cut n in half until you get 1. For example, you can cut 8 in half 3 times. In general, a "divide and conquer" algorithm that is always cutting its data in half has a running time of "log base 2 of n". What is "log base 2 of 64"? In other words, how many times can you cut 64 in half?
Correct Answer
A. 6
Explanation
The question is asking for the logarithm base 2 of 64, which represents the number of times you can divide 64 in half until you get 1. Since 64 can be divided by 2 six times (64/2 = 32, 32/2 = 16, 16/2 = 8, 8/2 = 4, 4/2 = 2, 2/2 = 1), the answer is 6.