Lesson test: Counting the cost

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Counting the cost

1.[2p]
How many comparisons does the nested-loop duplicate check, which compares every element with every later one, perform on a list of 200 numbers?

CorrectNot quite: 19900

2.[2p]
Why is timing a program with a stopwatch a poor way to compare two algorithms?

The result describes the machine, the language and the one input tried, none of which are properties of the algorithm

Correct

Timers are not accurate enough to resolve the difference

The answer is: The result describes the machine, the language and the one input tried, none of which are properties of the algorithm

The slower algorithm may still be correct

The answer is: The result describes the machine, the language and the one input tried, none of which are properties of the algorithm

Running a program changes its cost

The answer is: The result describes the machine, the language and the one input tried, none of which are properties of the algorithm

3.[2p]
Which of these does the RAM model assume?

Select all that apply

Reading any memory cell costs one step, whatever its address

Correct

Arithmetic on a value costs one step

Correct

A cache miss costs a hundred times more than a cache hit

The answer is: Reading any memory cell costs one step, whatever its address, Arithmetic on a value costs one step, Memory is unbounded

Memory is unbounded

Correct

4.[2p]
An array holds 400 distinct values, and the searched-for value is present and equally likely to be at any position. What is the expected number of comparisons for linear search?

CorrectNot quite: 200.5

5.[2p]
An average-case cost is meaningful only once the distribution of inputs it averages over has been stated.

True

Correct

False

The answer is: True

6.[3p]
Testing whether an integer $N$ is prime by trying all divisors up to $\sqrt{N}$ is called exponential rather than cheap because

the input is the written number, of size about $\log_{2} N$ bits, and $\sqrt{N}$ is exponential in that size

Correct

square roots are expensive to compute

The answer is: the input is the written number, of size about $\log_2 N$ bits, and $\sqrt{N}$ is exponential in that size

the worst case differs from the average case

The answer is: the input is the written number, of size about $\log_2 N$ bits, and $\sqrt{N}$ is exponential in that size

division costs more than one step in the RAM model

The answer is: the input is the written number, of size about $\log_2 N$ bits, and $\sqrt{N}$ is exponential in that size

7.[2p]
Match each case to what it reports.

Best case
Worst case
Average case

the expected cost under an assumed distribution
the smallest cost over all inputs of that size
the largest cost over all inputs of that size

Show the answer

Best case: the smallest cost over all inputs of that size Worst case: the largest cost over all inputs of that size Average case: the expected cost under an assumed distribution

8.[2p]
A machine performs $10^{9}$ comparisons per second. How many seconds does a program costing $n^{2} / 2$ comparisons take on $n = 100 {,} 000$ ?

CorrectNot quite: 5

9.[2p]
The exact count $1.5 n^{2} - 1.5 n + c$ is discarded in favour of "grows like $n^{2}$ " because

the constant depends on the machine and the lower terms vanish in relative size as $n$ grows

Correct

the count was derived incorrectly

The answer is: the constant depends on the machine and the lower terms vanish in relative size as $n$ grows

quadratic algorithms are never used in practice

The answer is: the constant depends on the machine and the lower terms vanish in relative size as $n$ grows

the linear term is negative

The answer is: the constant depends on the machine and the lower terms vanish in relative size as $n$ grows

1.[2p] How many comparisons does the nested-loop duplicate check, which compares every element with every later one, perform on a list of 200 numbers?

2.[2p] Why is timing a program with a stopwatch a poor way to compare two algorithms?

3.[2p] Which of these does the RAM model assume?

4.[2p] An array holds 400 distinct values, and the searched-for value is present and equally likely to be at any position. What is the expected number of comparisons for linear search?

5.[2p] An average-case cost is meaningful only once the distribution of inputs it averages over has been stated.

6.[3p] Testing whether an integer N is prime by trying all divisors up to N is called exponential rather than cheap because

7.[2p] Match each case to what it reports.

8.[2p] A machine performs 109 comparisons per second. How many seconds does a program costing n2/2 comparisons take on n=100{,}000?

9.[2p] The exact count 1.5n2-1.5n+c is discarded in favour of "grows like n2" because

1.[2p]
How many comparisons does the nested-loop duplicate check, which compares every element with every later one, perform on a list of 200 numbers?

2.[2p]
Why is timing a program with a stopwatch a poor way to compare two algorithms?

3.[2p]
Which of these does the RAM model assume?

4.[2p]
An array holds 400 distinct values, and the searched-for value is present and equally likely to be at any position. What is the expected number of comparisons for linear search?

5.[2p]
An average-case cost is meaningful only once the distribution of inputs it averages over has been stated.

6.[3p]
Testing whether an integer $N$ is prime by trying all divisors up to $\sqrt{N}$ is called exponential rather than cheap because

7.[2p]
Match each case to what it reports.

8.[2p]
A machine performs $10^{9}$ comparisons per second. How many seconds does a program costing $n^{2} / 2$ comparisons take on $n = 100 {,} 000$ ?

9.[2p]
The exact count $1.5 n^{2} - 1.5 n + c$ is discarded in favour of "grows like $n^{2}$ " because