Assignment#1 Frequently Asked Questions
-
In question 1c. "f in Theta(f(n/2))"
This should read "f(n) in Theta(f(n/2))"
- How do we represent a transition in a Turing Machine diagram
when the Turing Machine has various tapes?
For exaple: for two tapes, if the transition
goes from state q2 to state q3 when reading sumbols a from tape 1,
reading d from tape 2, and then
writing e on tape 1 and moving left, and writing g on tape2 and moving
right, the arrow that goes from state q2 to state q3 should
have label: (a,d)->(e,g,L,R)
-
In question 2.b. what is <n> and what does the algorithm do?
Let L be the length of the encoding of n (encoding of n is represented
by <n>). Note that L will change depending on the encoding, while
the running time of the algorithm will be the same since it depends on
the number n: the for-loop does n steps. The running time of the algorithm
should be measured in terms of the length of the input L.
-
What am I supposed to do in question 6?
The problems we are considering are:
LongestPath:
-
instance: <G,u,v,k>
-
type of problem: decison problem.
-
algorithm that solves this problem returns: 0/1 (no,yes) for question ``is
there a path in G between u and v of length at least k ?"
LongestPathLength:
-
instance: <G,u,v>
-
type of problem: optimization
-
algorithm that solves this problem returns: the length of the longest path
in G between u and v.
There are two parts in this question:
-
Assume there exists a polytime algorithm A for LongestPathLength.
Prove that there exists a polytime algorithm A' for LongestPath.
To prove this, you need to provide algorithm A', which can make calls
to algorithm A, that solves LongestPath and runs in polynomial time.
-
Assume there exists a polytime algorithm A' for LongestPath.
Prove that there exists a polytime algorithm A for LongestPathLength.
To prove this, you need to provide algorithm A, which can make calls
to algorithm A', that solves LongestPathLength and runs in polynomial time.