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:
1. 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.
2. 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.