Assignmnt#1: Marking Breakdown and Guide

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.