Grading Guide and Answer Key on Assignment #1, Prepared by Luna Dong

 Grading Guide

  • 2 points each for each question in 1 and 2
  • 12 points for 3, 6 for each function, 2 for the domain, 2 for the range and 2 for the expression.
  • 2--correct and complete answer; 1--minor errors; 0--fatal errors

NOTE: Remember to show work, or else some points will be dropped. I'm sorry for that but you need to learn the lesson.

Answer Key for Part II:

  1. 6 points:
  1.     {(a,0),(a,1),(b,0),(b,1),(c,0),(c,1),(d,0),(d,1),(e,0),(e,1)}
  2.     {(a,0,0),(a,0,1),(a,1,0),(a,1,1),(b,0,0),(b,0,1),(b,1,0),(b,1,1)}
  3.     {(a,(0,0)),(a,(0,1)),(a,(1,0)),(a,(1,1)),(b,(0,0)),(b,(0,1)),(b,(1,0)),(b,(1,1))}

NOTE: Be sure not to confuse S1*S3*S3 with (S1*S3)*S3. The answer of the latter should be:     
    (((a,0),0),((a,0),1),((a,1),0),((a,1),1),((b,0),0),((b,0),1),((b,1),0),((b,1),1))

  1.  12 points:
  1.     As f is a function, it's domain should be {0,1,2,3,5}
  2.     The range of f can be any super set of {a,b,c,e}
  3.     If the range of f is exactly {a,b,c,e}, f is a surjection; or else it is not.
  4.     No because of (0,a) and (1,a).
  5.     Just as d.
  6.     No because of (a,0) and (a,1).

NOTE: Pay attention to b) and c). Given a function, we can tell what the domain is. That's because every element in the domain should appear once and exactly once in the relations. However, we can't tell what the range is, cause some elements in the range may not appear in the relations. This is tricky and I'm sorry that only a few students did it correctly. However, for those who answered both b) and c) well, I was so excited that I gave them a bonus of 1-2.

  1. 12 points:
  1.     f MID-INSERT : elements * lists -> non-empty lists
        f MID-INSERT : ( t, [e1, ..., en] ) |-> [e1, ..., e floor(n/2)-1, t, e floor(n/2), e floor(n/2)+1, ..., en]
  2.     f MID-REMOVE : non-empty lists -> lists
        f MID-REMOVE : [e1, ..., en] |-> [e0, e1, ..., e floor(n/2)-1, e floor(n/2)+1, ..., en]
     
        lists = the set of all possible lists
        non-empty lists = the set of all possible lists which are not empty
        elements = the set of all acceptable elements in our lists.

NOTE:

  1. By saying f MID-INSERT : elements * lists -> non-empty lists, we give out the domain and range of MID-INSERT. The domain is elements * lists and the range is non-empty lists.
  2. In stead of specific elements, domain and range are actually some sets, which cover all of the possible input and output respectively. You don't need to mention the relationship between the input and output, which should be saved for formal description.
  3. For MID-REMOVE, some students give the answer of
    f MID-REMOVE : [e1, ..., en] |->( [e0, e1, ..., e floor(n/2)-1, e floor(n/2)+1, ..., en], efloor(n/2))
    We don't ask you to return the middle element. But if you write in this way, it's quite good.
  4. Actually, it's better to say what the result is when n=1.
  5. The result of floor(x) is the integer less than or equal to x, but larger than x-1. Don't use n/2 directly unless you say what will happen for n is even and n is odd. Actually, in this case ceiling(x), which gets the integer larger than or equal to x but less than x+1, is more meaningful. 
  6. I can understand formal description is a kind of hard for beginners. Hope this question and the example in the slides can help.