Four algorithms solve the same problem on an input of size n. Their step counts are listed below. Which algorithm becomes impractical (unreasonable running time) fastest as n grows large?
n steps
n² steps
2ⁿ steps
5 × n steps
Choose your answer
Was this exam question helpful?
Which two statements about heuristic solutions are true? Select two answers.
A heuristic may not produce the optimal answer
A heuristic aims to run in a reasonable amount of time
A heuristic always finds the best possible solution
A heuristic guarantees a correct answer for every input
Choose your answer
Was this exam question helpful?
When comparing the efficiency of two algorithms, computer scientists focus mainly on:
how the number of steps grows as the input size increases
the exact number of steps for one small input
the colour scheme used in the code editor
how many comments the code contains
Choose your answer
Was this exam question helpful?
Which of the following is an example of a decision problem?
Finding the shortest route that visits every city on a map
Determining whether a given number appears in a list
Sorting a list of scores into ascending order
Calculating the average of a set of exam marks
Choose your answer
Was this exam question helpful?
Finding the largest value in a list is a problem. What is the correct term for the task of finding the largest value in the specific list (8, 3, 9, 2)?
an instance of the problem
the efficiency of the problem
a heuristic for the problem
an optimization of the problem
Choose your answer
Was this exam question helpful?
Two correct algorithms solve the same scheduling problem. Algorithm P performs a number of steps proportional to n³ (polynomial). Algorithm Q performs a number of steps proportional to n! (factorial). For very large values of n, which statement is true?
Algorithm Q runs in a reasonable amount of time because factorial growth is efficient
Both algorithms run in an unreasonable amount of time because they solve the same problem
Algorithm P runs in a reasonable amount of time; Algorithm Q runs in an unreasonable amount of time
Algorithm P runs in an unreasonable amount of time because n³ grows faster than n!
Choose your answer
Was this exam question helpful?
A delivery company needs to find the shortest route that visits 60 addresses. Checking every possible route would take an unreasonable amount of time, so the company instead uses an approach that quickly produces a route that is good enough, though not guaranteed to be the shortest. This approach is best described as:
a decision problem
an exhaustive search
a polynomial-time exact solution
a heuristic
Choose your answer
Was this exam question helpful?
For a large input of size n, which of the following describes an algorithm that runs in a reasonable amount of time?
An algorithm whose number of steps is proportional to n²
An algorithm whose number of steps is proportional to 2ⁿ
An algorithm whose number of steps is proportional to n!
An algorithm whose number of steps is proportional to 3ⁿ
Choose your answer
Was this exam question helpful?
An algorithm's efficiency can be measured informally by counting how many times a statement runs. If list contains n elements, how many times does the DISPLAY command execute in the following code segment?
FOR EACH x IN list
{
FOR EACH y IN list
{
DISPLAY(x + y)
}
}n times
n² times
2 × n times
n − 1 times
Choose your answer
Was this exam question helpful?