-----------------------------------------------------
CSC363H1 -- Fall 20007 -- Assignment 1 Marking Scheme
-----------------------------------------------------

Basic guidelines:
 -  Be picky: students are responsible for showing that they understand, so
    take marks off for anything incomplete or ambiguous -- if you're not
    sure something is correct and you can't tell quickly, then the student
    either didn't have the right idea or didn't explain it well so take
    marks off (students can always request remarking later).
 -  Give feedback: use codes/keywords for common errors and keep a list of
    how they were marked, give more detailed feedback for unusual
    solutions; in addition, you may want to use letter codes to refer to
    specific points of the marking scheme.

1.  [15 marks]
     4: high level (correct idea)
     6: implementation level (correct implementation of high level idea,
        independently of high level idea correctness)
     5: formal level (clearly described, corresponds to implementation
        level description), including at least one or two useful traces

2.  [10 marks]
     3: format (proof by contradiction)
     7: idea (correct argument)

3.  [15 marks]
     7: argument that L_1 is recognizable
         2: format (clearly describe recognizer)
         5: idea (correct recognizer, uses dovetailing)
        (at most 2/7 for attempts to show L_1 unrecognizable)
     8: argument that L_2 is undecidable
         3: format (assume it is, construct decider for undecidable L)
         5: idea (correct construction and argument)
        (at most 3/8 for attempts to show L_1 decidable)

4.  [15 marks]
    argument that L_2 is unrecognizable:
     5: format of proof by contradiction (clear attempt to construct a
        recognizer for some unrecognizable language based on a recognizer
        for L_2)
     OR format of mapping reduction (clear construction of a specific input
        for L_2 given an arbitrary input for some unrecognizable language,
        followed by proof of correctness)
     8: idea (correct reduction)
     2: mention that this implies L_2 is undecidable

    for students who argue "L_2 is undecidable but recognizable":
     8: argument L_2 is undecidable (as in question 3)
    plut as most 2 for a well-formed attempt to show recognizability

    for students who argue "L_2 is decidable":
    at most 5/15 for attempting to do this the right way (giving a clear
    description of a decider, in the right format)

5.  [10 marks]
     2: correct answer (countable)
     4: format (clear attempt to argue correspondence with countable set)
     4: correct idea
    (at most 4/10 for attempts to show uncountable, based on format,
    including reasonable attempt to use diagonalization)