Lesson test: Choosing a structure

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.

Choosing a structure

1.[3p]
Why is polynomial time taken as the definition of efficient, despite $n^{100}$ being polynomial?

Polynomials are closed under composition, so a polynomial algorithm calling a polynomial subroutine stays polynomial

Correct

No algorithm with a large exponent has ever been found

The answer is: Polynomials are closed under composition, so a polynomial algorithm calling a polynomial subroutine stays polynomial

Because $n^{100}$ is faster than $2^{n}$ for every $n$

The answer is: Polynomials are closed under composition, so a polynomial algorithm calling a polynomial subroutine stays polynomial

Because hardware doubles in speed regularly

The answer is: Polynomials are closed under composition, so a polynomial algorithm calling a polynomial subroutine stays polynomial

2.[3p]
A $2^{n}$ algorithm runs at $10^{12}$ operations per second. How many seconds does $n = 100$ take, in units of $10^{18}$ ?

CorrectNot quite: 1.27

3.[3p]
What defines the class NP?

Every yes-instance has a short certificate that can be checked in polynomial time

Correct

No polynomial algorithm exists for any problem in it

The answer is: Every yes-instance has a short certificate that can be checked in polynomial time

Every problem in it can be solved in nondeterministic exponential time

The answer is: Every yes-instance has a short certificate that can be checked in polynomial time

It contains exactly the problems not in P

The answer is: Every yes-instance has a short certificate that can be checked in polynomial time

4.[2p]
Every problem in P is also in NP.

True

Correct

False

The answer is: True

5.[3p]
A problem is NP-complete when

it is in NP and every problem in NP reduces to it in polynomial time

Correct

no algorithm for it exists

The answer is: it is in NP and every problem in NP reduces to it in polynomial time

it reduces to some problem in P

The answer is: it is in NP and every problem in NP reduces to it in polynomial time

it has been proved to require exponential time

The answer is: it is in NP and every problem in NP reduces to it in polynomial time

6.[3p]
Which of these are real routes to solving an NP-complete problem in practice?

Select all that apply

An approximation algorithm with a guaranteed factor, such as 1.5 for metric travelling salesman

Correct

Confining the exponential blow-up to a parameter that is small in practice

Correct

Exploiting structure in the instances that actually arrive, as SAT solvers do

Correct

A polynomial algorithm for the general case, which exists but is slow

The answer is: An approximation algorithm with a guaranteed factor, such as 1.5 for metric travelling salesman, Confining the exponential blow-up to a parameter that is small in practice, Exploiting structure in the instances that actually arrive, as SAT solvers do

7.[2p]
A workload asks only "is this exact key present", millions of times per second. The right structure is

a hash table

Correct

a balanced binary search tree

The answer is: a hash table

a binary heap

The answer is: a hash table

a sorted array with binary search

The answer is: a hash table

8.[3p]
A leaderboard must report a player's rank among ten million. Which structure answers it in $O (\log n)$ ?

A balanced search tree whose nodes store their subtree sizes

Correct

A binary heap keyed by score

The answer is: A balanced search tree whose nodes store their subtree sizes

A hash table keyed by player identifier

The answer is: A balanced search tree whose nodes store their subtree sizes

An unsorted array of scores

The answer is: A balanced search tree whose nodes store their subtree sizes

9.[3p]
Match each workload to the structure it calls for.

Repeatedly take the smallest pending item
Look up by exact key and nothing else
List every key between two bounds
Find routes through a network of links

a hash table
a binary heap
a graph with adjacency lists
a balanced search tree

Show the answer

Repeatedly take the smallest pending item: a binary heap Look up by exact key and nothing else: a hash table List every key between two bounds: a balanced search tree Find routes through a network of links: a graph with adjacency lists

1.[3p] Why is polynomial time taken as the definition of efficient, despite n100 being polynomial?

2.[3p] A 2n algorithm runs at 1012 operations per second. How many seconds does n=100 take, in units of 1018?

3.[3p] What defines the class NP?

4.[2p] Every problem in P is also in NP.

5.[3p] A problem is NP-complete when

6.[3p] Which of these are real routes to solving an NP-complete problem in practice?

7.[2p] A workload asks only "is this exact key present", millions of times per second. The right structure is

8.[3p] A leaderboard must report a player's rank among ten million. Which structure answers it in O(logn)?

9.[3p] Match each workload to the structure it calls for.

1.[3p]
Why is polynomial time taken as the definition of efficient, despite $n^{100}$ being polynomial?

2.[3p]
A $2^{n}$ algorithm runs at $10^{12}$ operations per second. How many seconds does $n = 100$ take, in units of $10^{18}$ ?

3.[3p]
What defines the class NP?

4.[2p]
Every problem in P is also in NP.

5.[3p]
A problem is NP-complete when

6.[3p]
Which of these are real routes to solving an NP-complete problem in practice?

7.[2p]
A workload asks only "is this exact key present", millions of times per second. The right structure is

8.[3p]
A leaderboard must report a player's rank among ten million. Which structure answers it in $O (\log n)$ ?

9.[3p]
Match each workload to the structure it calls for.