Approximate grading key for Question 4:


Alef (10 points):
There were a number of possible solutions. The classic one is:
  1. public void add(Comparable data){
  2.     ComparableLink tmp = sentinal;
  3.     while(tmp.next!=null && data.compareTo(tmp.next.data)>0)
  4.         tmp = tmp.next;
  5.     tmp.next = new ComparableLink(data, tmp.next);
  6. }

In this section, there are three catagories on which your solution was evaluated. These are guidelines to understand your mistakes, and naturally do not include explanations to all possible errors.
Note: Some gradings were not divided into these catagories. More explanations may be given on your answer sheet.

  • A 0..+2 : correct handling of the empty list case. Points also taken off if sentinal.data was used (instead of sentinal.next.data), and some other mistakes.
  • B 0..+4 : correct loop. Points also taken off if sentinal was advanced instead of a temporary pointer, and some other mistakes. If you called a (nonexistent) add() method of ComparableLink you got 0 out of 4 points, for catagory B.
  • C 0..+4 : correct insertion into list; no ruining of the list; creating a new ComparableLink holding "data" (not treating "data" as a link!), and some other issues.


Beit (10 points):
There were a number of possible solutions, recursive and iterative. A recursive solution:
  1. public boolean isSorted(){
  2.     if (next==null)
  3.         return true;
  4.     if (data.compareTo(next.data)>0)
  5.         return false;
  6.     return next.isSorted();
  7. }

  • A -1/-2 : comparing a ComparableLink instead of a Comparable in compareTo() method.
  • B -1 : syntax mistake.
  • C -7/-8 : wrong implementation.
  • D -1/-2/-3 : logic mistake (light/medium/heavy).
  • E -2 : using list methods or fields though inside ComparableLink, like isEmpty(), sentinal.
  • F -1 : very inefficient loop (e.g. not using a flag) or recursion (e.g. using & instead of &&).
  • G -2 : advancing or using "this" or "next" instead of a temporary pointer ("this" cannot be changed! changing "next" may also ruin the list (see N)).
  • H -1 : wrong sort direction: "bigger first", in contrary to question description.
  • I -1 : unnecessary ComparableLink creation .
  • J -1 : missing/wrong handling of first element after "this" in the list, while handling well the (next==null) case.
  • K -2 : missing/wrong handling of (next == null) case.
  • L -3 : comparing all elements in the list to list head (this.data), instead of each element's previous.
  • M -3 : no/wrong use of compareTo() method
  • N -2 : changing (usually ruining) the list data structure.
  • O -1 : no/wrong advancement of pointer in the loop