- In question 1c. "f 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?
- What am I supposed to do in question 6?
- 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 ?"
- 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.
- Assume there exists a polytime algorithm A for LongestPathLength.
- Assume there exists a polytime algorithm A' for LongestPath.

This should read "f(n) in Theta(f(n/2))"

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.

The problems we are considering are:

LongestPath:

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.

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.