Question 1

Sequential search is an order-n algorithm in the average case.

Accepted Answer

Sequential search has to check every element in the worst-case scenario, making it an order-n algorithm. In the average-case scenario, it will perform better than the worst case, but still have a linear runtime complexity of O(n).

Question 2

No one has yet found a solution algorithm that works in polynomial time, but neither has anyone proved that such an algorithm does not exist.

Accepted Answer

This statement accurately reflects the current state of research and understanding in computer science and complexity theory. It is commonly believed that the problem of finding a polynomial-time algorithm for certain complex problems, such as solving the traveling salesman problem or integer factorization, is unlikely to be solved, but it has not been proven impossible.

Question 3

The selection sort algorithm can recognize whether or not the list is already sorted at the beginning.

Accepted Answer

The selection sort algorithm does not consider whether the list is already sorted or not, it simply proceeds with the algorithm steps to sort the list.

Question 4

The study of the efficiency of algorithms is called the ____ of algorithms.

Accepted Answer

The study of the efficiency of algorithms is called the analysis of algorithms. Design refers to the creation of algorithms, implementation refers to the actual coding of algorithms, and testing refers to the process of verifying that algorithms work correctly.

Question 5

If we were to run the sequential search algorithm many times, with random input values occurring at various places in the list, we would find the average number of comparisons done to be approximately n/2.

Accepted Answer

This is a well-known result in theoretical computer science. The average case for sequential search is indeed O(n/2), which means that on average, half of the list needs to be searched before finding the target value. However, it's important to note that this is only an average case analysis, and the actual number of comparisons required can vary widely depending on the specific input values.

Question 6

First and foremost, we expect elegance from our algorithms._________________________

Accepted Answer

- correctness

Question 7

With sequential search, the bigger the list of items, the more work that must be done to search it._________________________

Accepted Answer

In sequential search, the algorithm iterates through each item in the list until it finds the target item. Therefore, as the size of the list increases, the algorithm has to iterate through more items, resulting in more work that must be done to search it.

Question 8

In the sequential search algorithm, the worst case occurs when the value being searched for is the first value in the list._________________________

Accepted Answer

- best

Question 9

In the sequential search algorithm, the minimum amount of work is done if the value being searched for is the ____ value in the list.

Accepted Answer

In a sequential search algorithm, the minimum amount of work is done when the value being searched for is found at the beginning of the list, which means it is the first value. This is because the algorithm stops searching as soon as it finds the target value.

Question 10

A collection of nodes and connecting edges is called a(n) vector._________________________

Accepted Answer

- graph

Question 11

The properties that make better algorithms are very similar to the properties we look for when purchasing a car.

Accepted Answer

Just like we look for fuel efficiency, reliability, speed, and safety features when purchasing a car, we also look for efficiency, accuracy, speed, and reliability in an algorithm. Similarly, just as we consider factors such as the cost, maintenance, and resale value of a car, we also consider the computational complexity, ease of implementation, and scalability of an algorithm.

Question 12

____ involves the fixing of errors that are uncovered through repeated usage with different input values.

Accepted Answer

The process of fixing errors in a program after it has been put into use is called program maintenance. This is often necessary as bugs or issues may not become apparent until the program is used with a variety of input values. Recycling, data cleanup, and garbage collection are not related to programming error fixes.

Question 13

If an Θ(n2) algorithm and an Θ(n) algorithm exist for the same task, then for large enough n, the Θ(n2) algorithm does more work and takes longer to execute, regardless of the constant factors for peripheral work.

Accepted Answer

The notation Θ(n2) implies that the algorithm has a quadratic time complexity, while Θ(n) implies a linear time complexity. As n grows larger, the time required by the quadratic algorithm to execute will increase at a faster rate than the time required for the linear algorithm. Therefore, regardless of the constant factors, the quadratic algorithm will eventually take longer to execute than the linear algorithm.

Question 14

The sequential search and selection sort algorithms are different methods to get the same thing done.

Accepted Answer

The sequential search algorithm is used to search for a specific value in a list, while the selection sort algorithm is used to sort a list in ascending or descending order. They are not interchangeable methods for achieving the same thing.

Question 15

The shuffle-left algorithm is not space-efficient._________________________

Accepted Answer

- is

Question 16

____ are useful for rating one machine against another and for rating how sensitive a particular algorithm is with respect to variations in input on one particular machine.

Accepted Answer

Benchmarks are standardized procedures or programs used to compare the performance of different computer systems or algorithms. They provide a common reference point for evaluating and comparing different technologies. Time trials, comparison times, and intensive tests may also be used for performance evaluation, but they are not as common or widely accepted as benchmarks.

Question 17

The time an algorithm takes on a particular machine is the best way for comparing two algorithms that do the same task.

Accepted Answer

The time an algorithm takes to run can be affected by various factors such as the size of the input, the hardware specification of the machine, the programming language used, and the implementation of the algorithm. Therefore, comparing two algorithms solely based on their running time on a particular machine may not always be accurate or fair. Other factors such as space complexity, the number of operations required, and the required accuracy should also be considered when comparing algorithms.

Question 18

Given a sorted list, the sequential search algorithm is more efficient than the binary search.

Accepted Answer

The binary search algorithm is specifically designed for searching in a sorted list and has a time complexity of O(log n), which is more efficient than the sequential search algorithm that has a time complexity of O(n). Therefore, the statement is false.

Question 19

____ is the algorithmic equivalence of style.

Accepted Answer

Elegance in algorithms refers to the simplicity, clarity, and conciseness of the code, while still achieving the desired result. It is the equivalent of style in writing, where the writer's use of language and structure can enhance the reader's experience.

Question 20

Binary search uses significantly more space than sequential search.

Accepted Answer

Binary search does not use more space than sequential search. Both algorithms require the same amount of space in terms of the size of the input list.

Quiz 3: The Efficiency of Algorithms