=========================================================================== CSC 324 Assignment 4 -- Marking Scheme Winter 2009 =========================================================================== NOTE TO STUDENTS: You will find below the marking scheme used for your homework, including the meaning of marking codes and number of marks associated with each one. (Note that the weight of the questions was changed slightly compared with the assignment handout, to account for the true relative difficulty and amount of work involved in each question.) This file also contains my instructions to the marker (so you can get an idea of how the homework was marked) and the marker's comments about each question. Please take the time to read this carefully before you ask questions about the grading of your homework! NOTE TO MARKER: Be picky! On any homework, it is the responsibility of students to show that they understand how to solve each problem and to write up their answers carefully. Remember that marking is not only about evaluating a student's performance, but also mostly about giving them feedback so that they can learn from their mistakes. This is especially important for students who made numerous or more serious mistakes, as they are likely to need more feedback in order to understand why their answers were incorrect. For each question, I list solution elements with an associated code for writing on student papers (the letter(s) between underscores _) and a number of marks. There are also general errors (with associated codes) given below, with a maximum number of marks to take off for each type of general error (as a percentage of the value of the question). You will likely encounter other common errors, or maybe decide to break down the marking scheme further. Simply make note of these changes/additions to the marking scheme, and introduce new code letters (or short words) to allow you to quickly give accurate feedback to the students (both in terms of what they did wrong and how many marks it cost them). Your marking comments will be included in this marking scheme and posted on the course website so that students may look up the meaning of marking codes and understand how their work was marked. ------ Part I [51 marks] ------ 1. range [17 marks] correctness [7 marks]: _O_ output [4 marks]: from test cases _I_ inspection [3 marks]: code looks reasonable efficiency [4 marks]: _A_ asymptotic [2 marks]: correct overall runtime _D_ detailed [2 marks]: reasonable effort to avoid duplicated/unnecessary computation style [6 marks]: appropriate use of _U_ unification and cut [2 marks] _H_ "helper" predicates [1 mark] _C_ comments [2 marks] _W_ whitespace and indentation [0.5 marks] _N_ identifier names [0.5 marks] Marker's Comments/Common Mistakes: - Should use cuts to avoid checking number(H) multiple times: Inefficient way: range([H|T], Min, Max) :- \+number(H), ... range([H|T], Min, Max) :- number(H), ... Efficient way: range([H|T], Min, Max) :- \+number(H), !... range([H|T], Min, Max) :- ... - Don't need 4 cases when the list head is a number and the function calls range on the tail and compares the min/max of the tail to the current head. In the worst case, calls range on the tail 4 times. Can call it only once: Ex1: Use semi-colon as logical-or: range([H|T], Min, Max) :- number(H), range(T,K,L), ((H <= K, Min is H); Min is K), ((L <= H, Max is H); Max is L). Ex2: Use a helper functions min and max: range([H|T], Min, Max) :- number(H), range(T, K, L), min(H, K, Min), max(H, L, Max). - One main causes of failed tests was when the current head of the list is a number, and range is called on the tail of the list and then the min/max compared to the current head. If the call to range on the tail fails, because the tail doesn't contain any numbers, the whole case fails. Requires a case where the call to range(Tail) fails, and the head is the max and the min. - Many people did not use unification: Without unification: range([X], Min, Max) :- number(X), Min is X, Max is X. With unification: range([X], X, X) :- number(X). - Most people put cuts in useless places. (Like at the end of the line of the last case of a predicate). - A very inefficient and common solution: range(L, Min, Max) :- member(Min, List), member(Max, List), ... n^2 different combinations of Min and Max that will satisfy these 2 calls to member, where n is the size of list. For each of those n^2 combinations, must then check if the chosen elements for Min and Max are actually the min/max of the list. 2. uniquify [17 marks] correctness [7 marks]: _O_ output [4 marks]: from test cases _I_ inspection [3 marks]: code looks reasonable efficiency [4 marks]: _A_ asymptotic [2 marks]: correct overall runtime _D_ detailed [2 marks]: reasonable effort to avoid duplicated/unnecessary computation style [6 marks]: appropriate use of _U_ unification and cut [2 marks] _H_ "helper" predicates [1 mark] _C_ comments [2 marks] _W_ whitespace and indentation [0.5 marks] _N_ identifier names [0.5 marks] Marker's Comments: Correctness: - Forgot case [] (-0.5 I) Efficiency: - Don't need to run uniquify on tail more than once. (-1 A, -1 D) - Don't need to check member(Head, Tail) more than once. (-1 D) 3. flatten [17 marks] correctness [7 marks]: _O_ output [4 marks]: from test cases _I_ inspection [3 marks]: code looks reasonable efficiency [4 marks]: _A_ asymptotic [2 marks]: correct overall runtime _D_ detailed [2 marks]: reasonable effort to avoid duplicated/unnecessary computation style [6 marks]: appropriate use of _U_ unification and cut [2 marks] _H_ "helper" predicates [1 mark] _C_ comments [2 marks] _W_ whitespace and indentation [0.5 marks] _N_ identifier names [0.5 marks] Marker's Comments: Correctness: - Many people used \+atomic(H) or \+atom(H) to ensure that the head of the list was not a list. However atomic([]) and atom([]) both pass, so empty lists were not flattened. Efficiency: - Should use cut and proper ordering to only check if the head is a list once or twice. (-1D) ------- Part II [49 marks] ------- 1. permute [17 marks] correctness [7 marks]: _O_ output [4 marks]: from test cases _I_ inspection [3 marks]: code looks reasonable efficiency [4 marks]: _A_ asymptotic [2 marks]: correct overall runtime _D_ detailed [2 marks]: reasonable effort to avoid duplicated/unnecessary computation style [6 marks]: appropriate use of _U_ unification and cut [2 marks] _H_ "helper" predicates [1 mark] _C_ comments [2 marks] _W_ whitespace and indentation [0.5 marks] _N_ identifier names [0.5 marks] Marker's Comments: - The majority of the submissions did not work correctly when the second argument was instantiated instead of the first. - Many who did check which argument was instantiated could have used cut and proper ordering to avoid unnecessary computation. Inefficient: permute(L0,L1) :- \+var(L0), perm_helper(L0, L1). permute(L0, L1) :- \+var(L1), perm_helper(L1, L0). permute(L0, L1) :- var(L0), var(L1), perm_helper(L1, L0). Efficient: permute(L0, L1) :- \+var(L0), !, perm_helper(L0, L1). permute(L0, L1) :- perm_helper(L1, L0). 2. simple [32 marks] correctness [16 marks]: _O_ output [12 marks]: from test cases _I_ inspection [4 marks]: code looks reasonable efficiency [6 marks]: _A_ asymptotic [3 marks]: correct overall runtime _D_ detailed [3 marks]: reasonable effort to avoid duplicated/unnecessary computation style [10 marks]: appropriate use of _U_ unification and cut [3 marks] _H_ "helper" predicates [2 marks] _C_ comments [3 marks] _W_ whitespace and indentation [1 mark] _N_ identifier names [1 mark] Marker's Comments: - Lots of misuse of cuts: used indiscriminately (at the end of every line), or not used at all (even where it would have been necessary). [-1 to -2 on _U_] - Many uses of '=' or 'is' instead of unification. [-1 to -2 on _U_] - Many duplicate computations: rules with identical heads and first few sub-goals, which should be factored out. [-2 to -3 on _D_] - Confusion between atomic/1 and atom/1: atomic(X) succeeds iff X is an atom, number, or string -- not just an atom! [-1 on _I_] - Many tests failed because predicate generated multiple answers -- sometimes the same answer was repeated, other times additional answers were incorrect (not simplified). [-1 to -2 on _I_, -1 on _U_] - Some students used ';' to write monolithic-looking rule sets for predicates. In every such case, the resulting rules were inefficient (there were many common sub-goals to each alternative, that should have been factored out). This cost -2 marks for style.