=========================================================================== CSC 363H Exercise 5 -- Grading Scheme Fall 2007 =========================================================================== As usual, take off marks for ambiguous or incorrect notation, ambiguous or vague or incorrect claims that are not substantiated, or any other aspect of the answer's write-up that makes it difficult or impossible to understand. A. [3 marks] 2 marks: algorithm is clearly correct 1 mark: algorithm is clearly polytime B. [3 marks] 2 marks: algorithm is clearly correct 1 mark: algorithm is clearly polytime C. [4 marks] 2 marks: correct idea 2 marks: correct format, including using correct definition of P D. [2 marks] 1 mark: correct answer 1 mark: correct justification ----------------- Marker's Comments ----------------- A. 1. Some students rejected when they had to accept and accepted when they had to reject. For this I removed 0.5 points. 2. It is correct that division between integers can be done in polynomial time. Actually this statement is strong in the sense that the algorithm that achieves this is polynomial with respect to the length of an integer (that is log of the integer). Now if we loop n times, where n is some integer, then this operation is linear with respect to the string 1^n (n many ones). The division of two integers close to n take time log^k n, for some k>0, which is much less than any polynomial (while it is polynomial with respect to log n). Some students added (or multiplied) these running times which is incorrect (it is like adding meters and kilometers; 10 meter + 6 km is not 16 km!). However their argument used the O notation, that made their statement "accidentally" correct (it is like saying that 10 meters and 6 km is at most 16 km, which is correct). I urge students to be careful whenever they manipulate running times: running times have to be considered with respect to the same measure (here either the size of the representation of an integer n or the size of 1^n). 3. Many students were "crossing" some 1s, however they were forgetting to uncross them for the next process of the string 1^n. Their algorithm and their idea were both correct however if anyone would try to execute exactly their pseudocode, they would fail to find a correct answer. For this reason, whenever you want to give implementation details, make sure that you do it in the appropriate level, or otherwise your algorithm might be thought as defective. B. 1. Students have to understand that the running time of an algorithm strongly depends on the data structure we are using. Their arguments were sufficient for giving polynomial algorithms in general, however many of them were imprecise whenever they tried to argue about exact running time (and not for upper bounds). More specifically, to argue how much time we need to chech the existance of an edge depends on whether we have adjacency matrix, or list of neighbors. In the first case we need constant time, while in the second up to linear. Therefore, whenever you want to argue about the exact running time make sure you mention what is the encoding of your input. C. 1. I would prefer to see more detailed proofs of why their new TM meets the required specifications. However almost all of them were correct, and I did not remove any marks for being parsimonious with the proofs. D. 1. The definition (or even better a characterization) of NP suggests that for every L in NP there existence an appropriate verifier. It is also true that languages in NP are decidable, and therefore for each one of them there exist some decider. However, one should not confuse the verifier with the decider. Recall that a verifier for a language has two inputs; the standard input x (that comes with the question of whether x is in the language) and some certificate that is of polynomial size with respect to the size of x. A decider on the other hand takes as input just x.