From niloofar@cs.toronto.edu Fri Jul 26 11:40:53 2002
Date: 26 Jul 2002 15:37:49 GMT
From: Niloofar Arshadi <niloofar@cs.toronto.edu>
Cc: Tristan Miller <psy@cs.toronto.edu>,
Newsgroups: ut.cdf.csc270h
Subject: A2 marking scheme


Hi,

   Here is the marking scheme for A2.


-- Niloofar


1. (11 marks)

   (a) (6 marks)

       - (1  mark) The dimensions of the array are clearly specified or
                   obvious from context; the size of the array is
                   appropriate;
       - (4 marks) Correctness of the algorithm;
       - (1  mark) The algorithm is not tied to particular values of m and
                   n. For example, loops should be like for i=1 to m, not
                   for i=1 to 6;
       - If the solution is recursive, they get 0 mark.

   (b) (5 marks)

       - 5 marks for the exact table (exception: can have j rows and i
         columns instead);
       - -1/10 mark per incorrect cell;
       - -1 mark for not labelling i and j;
       - -1 mark for each extra row or column;

2. (22 marks)

   (a) (14 marks)

       - An excellent writeup with the best solution (O(kc) running time
         and O(c) space) gets 14 marks;
       - An excellent writeup with the solution of O(kc) running time and
         O(kc) space gets at most 13 marks;
       - An excellent writeup with the solution of O(kc^2) solution gets
         at most 12 marks;
       - An excellent writeup with the solutin that has greater than poly-
         nomial time (e.g. recursive solution) gets at most 7 marks;
       - An excellent writeup with incorrect solution gets at most 7
         marks, provided that some good ideas are in the writeup;
       - If there is no writeup, they get 0 mark, even if with correct
         recurrence relation and algorithm.

       - (7 marks) for the reasoning
       - (3 marks) for the recurrence relationship
       - (4 marks) for the algorithm

   (b) (5 marks)

       - 5 marks for the exact table (exception: can have i columns and j
         rows), plus indicating which cell holds the solution;
       - 1 mark for showing which cell holds the solution;
       - 1/2 mark for each row correct
       - -1 mark for not labelling i and j
       - -1 mark for each extra row or column

   (c) (3 marks)

       - (1 mark) stating the running time correctly
       - (1 mark) stating the space usage correctly
       - (1 mark) the analysis of the running time and space usage