Question 1:
0.5 was awarded for the right answer
1.5
was awarded for the proof
I automatically deducted 0.5 if you did only
specified c but not n in your proof (which a lot of people did).
Question
2:
-1 if you got encodings wrong
-1 if you didn't specify the length of
the encodings
Almost everybody got part (b) wrong. Please see the solutions
for the proper way to do this.
Question 3:
Accept states and
reject states should *never* be intermediate states (meaning you should enter
into an accept state and reject state only once, when you are completed your
computation). I didn't deduct marks for this, unless it caused serious
errors.
Most people did not follow directions with respect to their RAM
programs. You were to use the recipe given in the notes to construct your RAM
program. Many of you used your own techniques. If you did this and your
technique worked, I didn't take any marks off, even though you deviated from
the instructions.
Points were taken off for small errors (= instead of ^,
or omitting an =, etc...).
Points were taken off if you forgot to read the
input into registers and expected it to be there, or if you didn't do a
complexity analysis.
Question 4:
Many people's TMs in 4(a) didn't
work properly.
If you expect certain symbols to be on the second tape, your
TM must arrange for this in the implementation of your TM. It is not sufficient
to say that you are assuming that there is a copy of the input from your first
tape on the second tape.
A Turing machine is deterministic, which means
that you must have one and only one transition coming out of a state for each
distinct set of input(s). You cannot have two transitions out of the same state
for the same input(s). Marks were taken off for this and I made a comment on
your papers about contradictory transitions.
Tapes do not start with blank
symbols. If you try to rewind past the beginning of a tape, you don't get to a
blank space: you remain on the first symbol of the tape. If you want to
identify the beginning of a tape, you need to write a special symbol overtop of
the first character.
Part (b) was generally well done by most. Marks were
taken off if your implementation had errors, didn't work properly, etc...
Question
5:
The breakdown of marks for part (a) was as follows:
* (1 mark) L1, L2 in P
-> L1 union L2 in P
* (1 mark) L1, L2 in P -> L1 intersection L2 in P
* (2 marks) L1, L2 in P
-> L1L2 in P
*
(1 mark) L in P -> comp(L) in P
You cannot use examples in order to
prove things.
You need to use the definition of P in order to prove these
statements. Venn diagrams are not sufficient.
For L1L2, you cannot assume
that you know where the string identified by L1 ends and the string identified
by L2 starts. You must divide into two substrings and try all such divisions
(see solution).
For part (b), the approach to prove that one thing is a
subset of another is show that if any element x is in the subset, it is also in
the superset.
Question 6:
The breakdown of marks was as
follows:
* (8
marks) if LPL can be solved in polynomial time, then LP is in P
* (12 marks) if LP is in P,
then LPL can be solved in polynomial time
This was an if and only if proof,
which means you had to prove both directions. Some of you only proved one of
the two directions.
Something that many students did was to devise an
algorithm for LPL based on LP. This algorithm ran in O(mn), where m was bounded
by the number of vertices or edges in the graph. Using this logic, they said
that if LPL can be solved in polynomial time, and their algorithm (which solved
LPL) ran in O(mn) where m was an upper bound on the number of calls to LP, this
implied that LP ran in polynomial time. This is false. Just because your
algorithm solves LPL, this does not mean that it is *a* polynomial time
algorithm that solves LPL. Your algorithm may in fact be exponential. Being in
P just means that *a* polynomial time algorithm exists. The way to solve this
was to devise an algorithm for LP which called LPL and ran in polynomial
time.
Points were deducted if you assumed LP or LPL return a path; neither
of them do. You have no way of getting the path.
Question 7:
For
part (a), the breakdown of marks was as follows:
* (4 marks) Give the algorithm
* (1 mark) Justify that it
runs in polynomial time
I was pretty lenient here in the marking of part a.
I took marks off if I didn't feel that you didn't adequately expand on why your
algorithm ran in polynomial time or were vague about various details about your
algorithm.
For part (b), the breakdown of marks was as follows:
* (8 marks) Show that LP is
in NP
* (8 marks)
Give a reduction algorithm
* (7 marks) Verify the correctness of your
reduction algorithm
* (2 marks) Demonstrate that your algorithm runs in polynomial time
Generally,
there was a lot of problems with this question.
NOTE: A reduction algorithm
does NOT solve an instance of a problem. It should only take a problem of one
sort (in this case, Hamiltonian Path) and convert it to an instance of another
problem (in this case, LongestPath). If your reduction tried to solve
LongestPath given an instance of HamPath, I deducted significant marks. If you
tried to solve LongestPath and claimed that it ran in polynomial time, I also
deducted significant marks (if you could find a polynomial time algorithm for
LongestPath, you'd be a millionaire).
Hamiltonian Path is not the same
problem as Hamiltonian Cycle. Please be careful here.
Please study the
solutions for the problem since you will be looking at / performing a number of
problems of this variety.