Question 1

A quadratic algorithm has the growth-rate function ______.
A)O(n²)
B)O(n³)
C)O(2ⁿ)
D)O(log2ⁿ)

Accepted Answer

A quadratic algorithm has a growth-rate function of O(n²), which means that the time required to execute the algorithm increases with the square of the input size. This is because the algorithm performs operations that scale with the square of the input size, making it less efficient for larger inputs. Options B, C, and D do not accurately reflect the growth rate of a quadratic algorithm.

Question 2

Which of the following can be used to compare two algorithms?
A)growth rates of the two algorithms
B)implementations of the two algorithms
C)test data used to test programs which implement the two algorithms
D)computers on which programs which implement the two algorithms are run

Accepted Answer

Growth rates provide a quantitative measure of the efficiency of algorithms, making it easier to compare different algorithms. Implementations, test data, and computers used do not provide direct means for comparison between algorithms.

Question 3

Algorithm efficiency is typically a concern for ______.
A)small problems only
B)large problems only
C)medium sized problems only
D)problems of all sizes

Accepted Answer

B

Question 4

Assuming a linked list of n nodes,the code fragment: Node curr = head;
While (curr != null){
System.out.println(curr.getItem());
Curr.setNext(curr.getNext());
} // end while
Requires ______ comparisons.
A)n
B)n - 1
C)n + 1
D)1

Accepted Answer

The while loop will iterate n times, so there are n comparisons. However, the statement curr.setNext(curr.getNext()) does not involve any additional comparisons. Therefore, the code requires n+1 comparisons.

Question 5

Which of the following growth-rate functions indicates a problem whose time requirement is independent of the size of the problem?
A)O(n)
B)O(log2ⁿ)
C)O(2ⁿ)
D)O(1)

Accepted Answer

O(1) is a constant time complexity, meaning that the time requirement for executing the code is always the same, regardless of the size of the input. Therefore, it indicates a problem whose time requirement is independent of the size of the problem. The other options demonstrate varying degrees of growth in time as the input size increases.

Question 6

A linear algorithm has the growth-rate function ______.
A)O(log2ⁿ)
B)O(2ⁿ)
C)O(n)
D)O(1)

Accepted Answer

A linear algorithm has a growth rate of O(n), meaning the running time increases linearly with respect to the size of the input. The other options (O(log2ⁿ), O(2ⁿ), O(1)) represent logarithmic, exponential, and constant growth rates, respectively, and are not consistent with a linear algorithm.

Question 7

Given the statement: Algorithm A requires time proportional to f(n)
Algorithm A is said to be ______.
A)in class f(n)
B)of degree f(n)
C)order f(n)
D)equivalent to f(n)

Accepted Answer

The term "time proportional to f(n)" implies that the growth rate of the algorithm is directly proportional to the complexity of the input, represented by f(n). Therefore, Algorithm A is said to be of order f(n). Choice C) is the only option that correctly represents this concept. Choice A) is incorrect because "class" is not a relevant term in describing algorithmic complexity. Choice B) is incorrect because "degree" is more commonly used to describe the highest exponent in a polynomial function. Choice D) is incorrect because "equivalence" suggests that the algorithm has the same complexity as f(n), which may not necessarily be true.

Question 8

Assuming a linked list of n nodes,the code fragment: Node curr = head;
While (curr != null){
System.out.println(curr.getItem());
Curr.setNext(curr.getNext());
} // end while
Requires ______ write operations.
A)n
B)n - 1
C)n + 1
D)1

Accepted Answer

The code performs a write operation on each node by setting the next pointer, so it requires n write operations for n nodes.

Question 9

The value of which of the following growth-rate functions grows the fastest?
A)O(n)
B)O(n²)
C)O(1)
D)O(log2ⁿ)

Accepted Answer

B) O(n²) represents a quadratic growth rate, which increases faster than linear (O(n)), constant (O(1)), and logarithmic (O(log2ⁿ)) growth rates as n becomes large.

Question 10

An algorithm's execution time is related to the number of ______ it requires.
A)parameters
B)test data sets
C)data fields
D)operations

Accepted Answer

An algorithm's execution time depends on the number of operations it requires to complete the task. The more operations an algorithm has to execute, the longer it will take to complete. Therefore, the correct choice is D - operations.

Question 11

If a problem of size n requires time that is directly proportional to n,the problem is ______.
A)O(1)
B)O(n)
C)O(n²)
D)O(2ⁿ)

Accepted Answer

If the time required is directly proportional to n, then the problem is of linear time complexity. This can be denoted by O(n). Hence, option B is the correct choice. Option A, O(1) indicates that the time required for the problem is constant, which is not the case. Option C, O(n²) indicates a polynomial time complexity, which is higher than linear time. Option D, O(2ⁿ) indicates an exponential time complexity, which is much higher than linear time.

Question 12

Consider an algorithm that contains loops of the form: for (x = 1 through n ){
For (y = 1 through x){
For (z = 1 through 10){
Task T
} // end for
} // end for
} // end for
If task T requires t time units,the loop on y requires ______ time units.
A)10 * t
B)(10 * t)+ x
C)10 * t * x
D)t * x

Accepted Answer

The outer loop runs for n times, and for each iteration, the middle loop runs x times. Inside these two loops, task T is executed 10*z times, where z runs from 1 to 10. Therefore, the total number of times task T is executed is:
n * (1 + 2 + ... + n) * 10 = n * (n + 1) / 2 * 10 = 5 * n * (n + 1)
It follows that the total time units required to execute task T is t * 5 * n * (n+1).
So, the loop on y requires 5 times more time units than task T, and it runs x times within each outer iteration. Thus, the loop on y requires 5 * t * x time units, which is equal to the choice C.

Question 13

An exponential algorithm has the growth-rate function ______.
A)O(n²)
B)O(n³)
C)O(2ⁿ)
D)O(log2ⁿ)

Accepted Answer

Exponential growth-rate function is represented by O(2ⁿ), as the function grows exponentially with increasing input size n. Options A and B are polynomial growth rates, while option D represents logarithmic growth rate.

Question 14

A growth-rate function of ______ implies a problem whose time requirement is constant.
A)1
B)n
C)2ⁿ
D)log2ⁿ

Accepted Answer

A growth-rate function of 1 implies a problem whose time requirement is constant. This means that regardless of the input size, the time required to solve the problem remains the same.

Question 15

The solution to the Towers of Hanoi problem with n disks requires 2ⁿ - 1 moves.If each move requires the same time m,the solution requires ______ time units.
A)2ⁿ - 1
B)(2ⁿ - 1)+ m
C)(2ⁿ - 1)/ m
D)(2ⁿ - 1)* m

Accepted Answer

The formula given states that the solution to the Towers of Hanoi problem with n disks requires 2ⁿ - 1 moves. Each move requires time m. So, the total time required would be (2ⁿ - 1) × m, which is given by option D.

Question 16

Algorithm analysis should be independent of all of the following EXCEPT ______.
A)the programming style used in the implementation of the algorithm
B)the computer used to run a program which implements an algorithm
C)the number of significant operations in an algorithm
D)the test data used to test a program which implements an algorithm

Accepted Answer

The number of significant operations in an algorithm is a fundamental aspect of algorithm analysis, as it directly impacts the algorithm's time complexity, which is independent of programming style, the specific computer used, or the test data.

Question 17

The value of which of the following growth-rate functions grows the slowest?
A)O(n)
B)O(n²)
C)O(1)
D)O(log2ⁿ)

Accepted Answer

In a growth-rate function, O(1) has constant time complexity, regardless of the size of the input. Therefore, it grows slowest as compared to O(n), O(n²), and O(log2ⁿ).

Question 18

Consider an algorithm that contains loops of the form: for (x = 1 through n ){
For (y = 1 through x){
For (z = 1 through 10){
Task T
} // end for
} // end for
} // end for
If task T requires t time units,the innermost loop on z requires ______ time units.
A)y
B)10
C)z * t
D)10 * t

Accepted Answer

The innermost loop represents a task T that requires t time units. The loop runs for 10 iterations, so the time required for it is 10t. Therefore, the option D, 10*t is the correct choice.

Question 19

Assuming a linked list of n nodes,the code fragment: Node curr = head;
While (curr != null){
System.out.println(curr.getItem());
Curr.setNext(curr.getNext());
} // end while
Requires ______ assignments.
A)n
B)n - 1
C)n + 1
D)1

Accepted Answer

The code fragment iterates through each node in the linked list, starting from the head and moving to the next node until it reaches the end (null). For a linked list of n nodes, it requires n + 1 assignments: n assignments for each node to move to the next node, and one additional assignment at the beginning to set `curr` to `head`. However, the code has a logical error in `Curr.setNext(curr.getNext());` which should be `curr = curr.getNext();` to correctly iterate through the list. The explanation is based on the assumption of understanding the intent behind the code despite the error.

Question 20

Which of the following is NOT part of the human cost of developing a computer program?
A)the efficiency of a program
B)the readability of a program
C)the modifiability of a program
D)the maintainability a program

Accepted Answer

The efficiency of a program is a technical aspect that focuses on its performance, but it is not directly related to the human cost of developing the program. The other options (B, C, and D) all relate to how humans interact with and manage the program, which can impact its development, maintenance, and overall cost.

Quiz 10: Algorithm Efficiency and Sorting

A quadratic algorithm has the growth-rate function ______.

Which of the following can be used to compare two algorithms?

Algorithm efficiency is typically a concern for ______.

Assuming a linked list of n nodes,the code fragment: Node curr = head; While (curr != null) { System.out.println(curr.getItem() ) ; Curr.setNext(curr.getNext() ) ; } // end while Requires ______ comparisons.

Which of the following growth-rate functions indicates a problem whose time requirement is independent of the size of the problem?

A linear algorithm has the growth-rate function ______.

Given the statement: Algorithm A requires time proportional to f(n) Algorithm A is said to be ______.

Assuming a linked list of n nodes,the code fragment: Node curr = head; While (curr != null) { System.out.println(curr.getItem() ) ; Curr.setNext(curr.getNext() ) ; } // end while Requires ______ write operations.

The value of which of the following growth-rate functions grows the fastest?

An algorithm's execution time is related to the number of ______ it requires.

If a problem of size n requires time that is directly proportional to n,the problem is ______.

Consider an algorithm that contains loops of the form: for (x = 1 through n ) { For (y = 1 through x) { For (z = 1 through 10) { Task T } // end for } // end for } // end for If task T requires t time units,the loop on y requires ______ time units.

An exponential algorithm has the growth-rate function ______.

A growth-rate function of ______ implies a problem whose time requirement is constant.

The solution to the Towers of Hanoi problem with n disks requires 2ⁿ - 1 moves.If each move requires the same time m,the solution requires ______ time units.

Algorithm analysis should be independent of all of the following EXCEPT ______.

The value of which of the following growth-rate functions grows the slowest?

Consider an algorithm that contains loops of the form: for (x = 1 through n ) { For (y = 1 through x) { For (z = 1 through 10) { Task T } // end for } // end for } // end for If task T requires t time units,the innermost loop on z requires ______ time units.

Assuming a linked list of n nodes,the code fragment: Node curr = head; While (curr != null) { System.out.println(curr.getItem() ) ; Curr.setNext(curr.getNext() ) ; } // end while Requires ______ assignments.

Which of the following is NOT part of the human cost of developing a computer program?