CS代写 Our Zoom Poll

Our Zoom Poll

Why is the answer not just n factorial?

Copyright By PowCoder代写 加微信 powcoder

Think about the complete undirected graph with 3 vertices
Call vertices a, b, and c.

Are there 3! = 6 tours? If not, then n! is not the correct answer.

All possible tours for these vertices:
a->b->c->a
b->c->a->b
Q: are these two tours actually different? No: they use the same edges.

How about a->c->b->a?
This is the same tour as well.

n! is incorrect because it counts the same tour many times.
It counts each tour twice: once forward and once backward

And it counts each of these n times, one for each starting point of the tour, like this:
a->b->c->a
b->c->a->b
c->a->b->c

Answer is n!/(2*n)
= (n-1)!/2

Exhaustive search will give us something like O(n!) runtime.

———-

Comparing n! to 2^n
n! is approximately (n/e)^n
Compare that to 2^n… a lot smaller

———-

Dynamic Programming Algorithm for TSP

Memory space complexity here is huge: O(2^n)
Good example of space-time tradeoff: huge memory usage for faster runtime

let A be a two-dimensional 2^n by n array

# Base cases (2 vertices)
for j in [2, 3, …, n]:
A[{1, j}][j] = c(1, j)

# General (>= 3 vertices)
for s in [3, 4, …, n]: # s == size == num vertices
for all S such that 1 in S and |S| == s:
for j in S – {1}:
A[S][j] = min_{k in S-{1, j}} A[S-{j}][k] + c(k, j)

Runtime for the above code is: O(2^n*n *n) = O(2^n * n^2)

Postprocessing needed here is O(n); this doesn’t change the overall runtime.

Here we have O(2^n * n^2), which is much faster than O(n!)

n!, you can solve ~15 vertices
O(2^n * n^2), you can solve ~30 vertices
Doubled the problem size that you can solve.

Not a huge increase, but with these NP-complete problems you take what you can get 🙂

———-

Here was our first execution of the contraction algorithm.

Contract edge (a, c):

Contract edge (ac, d):

Just two vertices remaining, so we are done.

What are these two vertices called?
the other is acd

This is what the algorithm claims is the min cut: ({b}, {a, c, d})

a–b <-- crosses b--c <-- crosses How many edges cross that cut? 2 What's the min cut in this graph? 2 The algorithm got it right this time. And here was our second execution of the contraction algorithm. Contract edge (a, b): Contract edge (c, d): Just two vertices remaining, so we are done. The claimed min cut this time is ({a, b}, {c, d}) How many edges cross this cut? b--c <-- crosses d--a <-- crosses a--c <-- crosses 3 edges cross this cut. So the algorithm didn't find the min cut this time... got it wrong. Say that we have a graph with 50 vertices. Do you expect this algorithm to find the min cut? On every iteration, there's a chance for the algorithm to make a mistake. To get the min cut, it has to avoid making a mistake on every iteration. And there are a lot of iterations: n-1 of them. Remember: there are 2^n cuts So if the probability of this algorithm finding the min cut is 1/2^n, then it wouldn't be useful