Week 8

Question 1

What problems are not known to be in P?

Answer 1

Travelling salesperson
Bin-pacing
Graph colouring
Timetabling

Question 2

What is the travelling salesman?

Answer 2

Decide if a salesperson can complete a round trip of N cities within a given mileage allowance, visiting each city exactly once.

Question 3

What is the Hamilton cycle problem

Answer 3

In TSP it decides whether a round trip that visits each city exactly once is even possible.

Question 4

What is the Bin-packing problem?

Answer 4

Decide if T trucks, each of which can carry a load W can carry N crates of different weights.

Question 5

What is the Knapsack problem?

Answer 5

0-1 knapsack problem is to pack a backpack that can hold weight W with items of different weights and values.

Question 6

What is graph colouring problem

Answer 6

Assign colours to each vertex of a graph G such that no adjacent vertices get same colour. The aim is to minimize the number of colours while coloring a graph.

Question 7

What is the timetabling problem

Answer 7

The timetabling problem is to create a timetable so that given a list of modules, a list of students enrolled on those modules, and the timeslots available, no student has a clash.

Question 8

How do we make progress for problems not in P

Answer 8

Use algorithms that find:
solutions that are approximate
solutions that come quickly on average
solutions that are probably correct.

Question 9

Explain solutions that are approximate

Answer 9

One way to make progress is to find solutions that are
approximate — a reasonably short tour or a timetable with a
few clashes may be better than nothing.

Question 10

Explain solutions that come quickly on average

Answer 10

Another way to make progress is to find solutions that come
quickly on average — typical data may not cause a problem.

Question 11

Explain solutions that are probably correct

Answer 11

Another way to make progress is to find solutions that are
probably correct — there is a very small chance the solution
will be incorrect.

Question 12

What is the complexity class NP

Answer 12

NP is for problems for which there are no known algorithms for finding solutions in P, but there are algorithms for checking solutions in P.

Question 13

What does NP stand for

Answer 13

Non-deterministic polynomial time. It is the collection of decision problems that can be solved by a
non-deterministic machine in polynomial time.

Question 14

Whats an example of NP problem

Answer 14

Sudoku

Question 15

What are NP complete problems?

Answer 15

The hardest problems in NP. If an algorithm in P was found for it, there would be algorithms in P found for all of them.

Question 16

What is the SAT problem?

Answer 16

The SAT problem is to assign values to the variables of a
boolean formula 𝜑 that make it true.
For
𝜑 = (¬𝑝 ∨ 𝑞) ∧ (¬𝑞 ∨ 𝑟) ∧ (𝑝 ∨ 𝑞 ∨ ¬𝑟)
take 𝑝 = false and 𝑞 = true, and 𝑟 = true.
The SAT problem is NP-complete.

Question 17

What are other NP-complete problems?

Answer 17

Clique
String correction problem
Rubik’s cube problem
Subgraph isomorphism problem

Question 18

What is clique problem?

Answer 18

Find a fully connected subgraph in a graph. It is NP-complete.

Question 19

What is the string correction problem?

Answer 19

Compute the shortest edit distance between one string and another. e.g. rain -> shine is 4 steps
Replace Delete Insert Copy

Question 20

What is the rubiks cube problem?

Answer 20

Compute the minimal unscrambling action needed to make all of the faces the same.

Question 21

What is Subgraph Isomorphism problem?

Answer 21

Determine whether one graph G contains a subgraph that is isomorphic to H. It is NP complete.

Question 22

How do we solve NP-complete problems?

Answer 22

Exact algorithms
Approximate algorithms
Probablistic algorithms

Question 23

What is an exact algorithm?

Answer 23

Usually only work for relatively small input
Travelling salesman has (n-1)!/2 possible tours, so O(n!). Using dynamic programming to remember subtours makes this O(n^2 2^N)

Question 24

What is an approximate algorithm?

Answer 24

Finds a decent solution that is not optimal but can be computed in P time.

Question 25

What is a probablistic algorithm?

Answer 25

Finds a solution that is probably a good one.

Question 26

What is a probablistic algorithm?

Answer 26

Finds a solution that is probably a good one.