What is wrong with these answers?

Linked list notation, conceptual and C++.

Notice that h:t is the list whose head is h and whose tail is t. We are only working with lists of integers. So the head of a list is an integer. The tail of a list is a list.

Determining what is wrong

Each of the following examples is taken from student answers on quiz 4. In some cases, some small modifications might have been done, either deliberately or by accident.

All of these answers are incorrect. Inspect each one and decide which of the following describes it. A given answer might have more than one kind of error.

The answer link gives my list of issues. I have not always tried to list all of the errors.

• Nonsense: It makes no sense at all.

• Incorrect notation: It uses conceptual notation in a C++ function definition or C++ notation in a conceptual equation.

• Syntax error. This covers syntax errors other than incorrect notation errors.

• Type error: This covers wrong type of parameter, wrong return type, etc.

• Wrong number of parameters. A function is used with the wrong number of parameters.

• Compile error. This covers compile errors other than the prior kinds of errors.

• Incorrect: The function gives an incorrect answer. This can apply to a function that has other errors if there is an obvious way to fix those errors. Give an example where the answer is incorrect.

• No recursion. The function definition cannot possibly be right because it does not use recursion or a loop, and some kind of repetition is clearly needed.

Conceptual equations for successors: equation 1

The first equation for successors should be

  successors([]) = [].

1. successors([]) = NULL

   Answer

2. successors([]) = h+1 : []

   Answer

3. successors([]) = [n]

   Answer

4. successors([]) = return successors of L

   Answer

5. successors([]) = L

   Answer

6. successors([]) = head : 0

   Answer

7. successors([]) = 1:[]

   Answer

Conceptual equations for successors: equation 2

The second equation for successors should be

  successors(L) = head(L) : successors(tail(L))   (when L is not empty).

1. successors(L) = head(L) : head(tail(L))

   Answer

2. successors(L) = head(L) : 1 : tail(L)

   Answer

3. successors(L) = L->head + 1 : successors(L->tail)

   Answer

4. successors(L) = cons(head(L) + 1, successors(tail(L))

   Answer

5. successors(L) = con(L->head, successors)

   Answer

6. successors(L) = h:t + 1

   Answer

7. successors(L) = head(L) + 1 : L

   Answer

8. successors(L) = [n+1]

   Answer

9. successors(L) = n+1 to member of list

   Answer

10. successors(L) = 1 + head[L] : tail[L]

    Answer

11. successors(L) = const(head + 1)

    Answer

12. successors(L) = cons(L->head, successors(L->tail))

    Answer

13. successors(L) = new ListCell(L->head+1, successors(L->tail))

    Answer

14. successors(L) = head++ : tail++

    Answer

15. successors(L) = L(head) + 1

    Answer

16. successors(L) = return L head and loop again

    Answer

17. successors(L) = L(n+1)

    Answer

18. successors(L) = [3, -8, -4, 5] + [4, -7, -3, 6]

    Answer

19. successors(L) = head(L) + 1 : tail(L) + 1

    Answer

20. successors(L) = list integers = n+1

    Answer

21. successors(L) = head(L) + 1 : head(tail(L)) + 1

    Answer

22. successors(L) = head(L) : successors(tail(L) + 1)

    Answer

23. successors(L) = cons(head + 1, successor(tail))

    Answer

24. successors(L) = [head(L) + 1, successors(tail(L))]

    Answer

25. successors(L) = 1 + n : successors(tail(L))

    Answer

26. successors(L) = head(L) + 1 : head(L) : 1

    Answer

27. successors(L) = new List(L) + 1

    Answer

28. successors(L) = L + 1

    Answer

29. successors(L) = A = (head(L) + 1) : A

    Answer

First merge equation

The first equation for merge should be

  successors([], B) = B.

1. merge([], B) = [B]

   Answer

2. merge([], B) = head(B) : tail(B)

   Answer

3. merge([], B) = B:[]

   Answer

4. merge([], B) = [A]

   Answer

5. merge([], B) = true

   Answer

6. merge([], B) = [], [3,5,6,13]

   Answer

7. merge([], B) = merge(B, tail(B))

   Answer

8. merge([], B) = return B head and tail

   Answer

9. merge([], B) = returns B

   Answer

10. merge([], B) = []:B

    Answer

11. merge([], B) = A->head A = A->tail

    Answer

12. merge([], B) = merge(emptylist, B)

    Answer

Third merge equation

The third equation for merge should be

  successors(A, B) = head(A) : merge(tail(A), B)  (when head(A) < head(B)).

1. merge(A, B) = head(A) : B

   Answer

2. merge(A, B) = cons(head(A), merge(tail(A), B))

   Answer

3. merge(A, B) = new ListCell(head(A), merge(tail(A), B))

   Answer

4. merge(A, B) = [A,B]

   Answer

5. merge(A, B) = head(A):head(B) -> head(tail(A)) < head(tail(B))

   Answer

6. merge(A, B) = [X + Y]

   Answer

7. merge(A, B) = head(A)

   Answer

8. merge(A, B) = head(A) = head(C)

   Answer

9. merge(A, B) = head(B) : merge(A, tail(B))

   Answer

10. merge(A, B) = return head of B and loop again

    Answer

11. merge(A, B) = head(B) tail(A)

    Answer

12. merge(A, B) = h(A), h(B)) : (A,B)

    Answer

13. merge(A, B) = A:B = [A,B]

    Answer

14. merge(A, B) = B:A

    Answer

15. merge(A, B) = returns list A before B

    Answer

16. merge(A, B) = [head(A), head(B)]

    Answer

17. merge(A, B) = head(A) + tail(A) + head(B) + tail(B)

    Answer

18. merge(A, B) = cons(A->head, merge(A->tail, B))

    Answer

19. merge(A, B) = [B,A] merge(tail(A), tail(B))

    Answer

20. merge(A, B) = [head(A), merge(head(B), tail(A))]

    Answer

21. merge(A, B) = head(A) and merge(tail(A), tail(B))

    Answer

22. merge(A, B) = head(A) : tail(B)

    Answer

23. merge(A, B) = cons(head(A) : head(B) : tail(B)

    Answer

24. merge(A, B) = A : cons(tail(A), B)

    Answer

25. merge(A, B) = List merge1 = cons(head(A), tail(merge1))

    Answer

26. merge(A, B) = cat(head(A), head(B), tail(A), tail(B))

    Answer

27. merge(A, B) = merge(A,B)

    Answer

28. merge(A, B) = C = head(A) : C merge(A->tail, B)

    Answer

Definitions of 'successors'

A correct definition of successors is

List successors(ConstList L)
{
  if(L == NULL)
  {
     return NULL;
  }
  else 
  {
     return cons(head(L) + 1, successors(tail(L)));
  }
}

1. List successors(ConstList L)
   {
      if(isEmpty(L)) 
      {
         return;
      }
      ...
   }
   

   Answer

2. List successors(ConstList L)
   {
      if(L == NULL) 
      {
         return isEmpty(L);
      }
      ...
   }
   

   Answer

3. List successors(ConstList L)
   {
     List B = new List(L->head, L->tail);
     ...
   }
   

   Answer

4. List successors(ConstList L)
   {
     List K = new List;
     ...
   }
   

   Answer

5. List successors(ConstList L)
   {
     if(L->tail == NULL)
     {
       ...
   }
   

   Answer

6. List successors(ConstList L)
   {
     if(L == NULL)
     {
        return NULL;
     }
     else 
     {
        return successors(L->tail);
     }
   }
   

   Answer

7. List successors(ConstList L)
   {
     if(L == NULL)
     {
        return NULL;
     }
     else 
     {
        int h = L->head;
        ConstList t = L->tail;
        return cons(h++, successors(t));
     }
   }
   

   Answer

8. List successors(ConstList L)
   {
     if(L == NULL)
     {
        return NULL;
     }
     else 
     {
        L->head++;
        L->tail++;
        successor(L);
     }
   }
   

   Answer

9. List successors(ConstList L)
   {
     List* p = new List;
     p = L;
     if(p == NULL)
     {
        return NULL;
     }
     else 
     {
        return successors(p->head + 1);
     }
   }
   

   Answer

10. List successors(ConstList L)
    {
      if(L == NULL)
      {
        return NULL;
      }
      else 
      {
        return successors(L);
      }
    }
    

    Answer

11. List successors(ConstList L)
    {
      List sL = [];
      if(isEmpty(L) == true)
      {
         return sL;
      }
      else 
      {
         sL = cons(head(L) + 1, NULL);
         return successors(tail(L));
      }
    }
    

    Answer

12. List successors(ConstList L)
    {
      if(L == NULL)
      {
         return NULL;
      }
      else 
      {
         cons(head(L), successors(tail(L) + 1));
      }
    }
    

    Answer

13. List successors(ConstList L)
    {
      if(L == NULL)
      {
         return NULL;
      }
      else 
      {
         return cons(head(L), successors(tail(L)));
      }
    }
    

    Answer

14. List successors(ConstList L)
    {
      if(L == NULL)
      {
         return NULL;
      }
      else 
      {
        return ListCell(L->head + 1, successors(L->tail));
      }
    }
    

    Answer

15. List successors(ConstList L)
    {
      if(L->tail == NULL)
      {
         return new ListCell(L->head + 1, NULL);
      }
      ...
    }
    

    Answer

16. List successors(ConstList L)
    {
      if(L == NULL)
      {
         return 0;
      }
      ...
    }
    

    Answer

17. List successors(ConstList L)
    {
      List* s = new ListCell();
      if(isEmpty(L))
      {
         return cons((L->head + 1, s);
      }
      ...
    }
    

    Answer

18. List successors(ConstList L)
    {
      if(L == NULL)
      {
        // do nothing
      }
      else 
      {
         return L(n+1);
      }
    }
    

    Answer

19. List successors(ConstList L)
    {
      if(L == NULL)
      {
        return 0;
      }
      else 
      {
        List N = L;
        N->head = head + 1;
        N->tail = tail + 1;
        return N;
      }
    }
    

    Answer

20. List successors(ConstList L)
    {
      if(L == [])
      {
         return [];
      }
      ...
    }
    

    Answer

21. List successors(ConstList L)
    {
      if(successors = NULL)
      {
         return NULL;
      }
      ...
    }
    

    Answer

22. List successors(ConstList L)
    {
      List s = new List;
      while(L != NULL)
      {
        s:(head(L) + 1);
      }
      return s;
    }
    

    Answer

Definitions of 'merge'

A correct definition of merge is

  List merge(ConstList A, ConstList B)
  {
    if(A == NULL) 
    {
      return B;
    }
    else if(B == NULL) 
    {
      return A;
    }
    else if(head(A) <= head(B))
    {
      return cons(head(A), merge(tail(A), B));
    }
    else
    {
      return cons(head(B), merge(A, tail(B)));
    }
  }

1.   List merge(ConstList A, ConstList B)
     {
       if(A == NULL)
       {
         return new ListCell(B.head, B.tail);
       }
       ...
     }
   

   Answer

2.   List merge(ConstList A, ConstList B)
     {
       if(A == NULL)
       {
         return new List(B->head, B->tail);
       }
       ...
     }
   

   Answer

3.   List merge(ConstList A, ConstList B)
     {
       if(A == [])
       {
         return B;
       }
       ...
     }
   

   Answer

4.   List merge(ConstList A, ConstList B)
     {
       List C = new List;
       if(A == [])
       {
         C = merge(B, tail(B));
       }
       ...
     }
   

   Answer

5.   List merge(ConstList A, ConstList B)
     {
       if(A->head >= B->head)
       {
         return merge(A->tail, B->tail);
       }
       ...
     }
   

   Answer

6.   List merge(ConstList A, ConstList B)
     {
       if(A == NULL && B != NULL) 
       {
         return B;
       }
       else if(A != NULL && B == NULL) 
       {
         return A;
       }
       else if(head(A) ≤ head(B))
       {
         return cons(head(A), cons(tail(A), B));
       }
       ...
     }
   

   Answer

7.   List merge(ConstList A, ConstList B)
     {
       if(A == NULL) 
       {
         return B;
       }
       if(B == NULL) 
       {
         return A;
       }
       if(A->head <= B->head)
       {
         return new List(A->head, merge(A->tail, B->tail));
       }
       if(A->head > B->head)
       {
         return new List(A->head, merge(A->tail, B->tail));
       }
     }
   

   Answer

8.   List merge(ConstList A, ConstList B)
     {
       if(A == NULL) 
       {
         return B;
       }
       if(B == NULL) 
       {
         return A;
       }
       if(head(A) ≤ head(B))
       {
         return (head(B), merge(A,B));
       }
       if(A->head > B->head)
       {
         return (head(A), merge(B,A));
       }
     }
   

   Answer

9.   List merge(ConstList A, ConstList B)
     {
       if(A->tail == NULL || B->tail == NULL) 
       {
         return new ListCell(A->head, NULL);
       }
       else if(A-> <= B->head)
       {
         return new ListCell(A->head, merge(A->tail, B->tail));
       }
       if(A->head > B->head)
       {
         return new ListCell(B->head, merge(A->tail, B->tail));
       }
     }
   

   Answer

10.   List merge(ConstList A, ConstList B)
      {
        List mergedList = new ListCell(NULL);
        if(isEmpty(tail(A)) 
        {
          return cons(tail(B), mergedList);
        }
        else if(isEmpty(tail(B)))
        {
          return cons(tail(A), mergedList);
        }
        ...
      }
    

    Answer

11.   List merge(ConstList A, ConstList B)
      {
        if(A == NULL)
        {
          return B;
        }
        else if(B == NULL)
        {
          return A;
        }
        else if(A.head ≤ B.head)
        {
          return merge(A.head, A->tail = B.head);
        }
        else {
          return merge(B.head, B->tail = A.head);
        }
      }
    

    Answer

12.   List merge(ConstList A, ConstList B)
      {
        if(A == NULL)
        {
          return B;
        }
        else if(B == NULL)
        {
          return A;
        }
        else if(A ≤ B)
        {
          return cons(A, merge(B));
        }
        else {
          return cons(B, merge(A));
        }
      }
    

    Answer

13.   List merge(ConstList A, ConstList B)
      {
        if(A == NULL)
        {
          return B;
        }
        else if(B == NULL)
        {
          return cons(A->head, merge(A->tail([]));
        }
        else if(head(A) <= head(B))
        {
          return cons(A->head, merge(A->tail(B));
        }
        else {
          return cons(B->head, merge(B->tail(A));
        }
      }
    

    Answer

14.   List merge(ConstList A, ConstList B)
      {
        if(A == NULL)
        {
          return B;
        }
        else if(B == NULL)
        {
          return A;
        }
        else if(A->head <= B->head)
        {
          List L = new ListCell(B, A);
        }
        else {
          List L = new ListCell(A, B);
        }
        merge(A->tail, B->tail);
        return L;
      }
    

    Answer

15.   List merge(ConstList A, ConstList B)
      {
        if(A == NULL)
        {
          return B;
        }
        else if(B == NULL)
        {
          return A;
        }
        else if(A->head ≤ B->head)
        {
          return ListCell(head->A, merge(head->B, tail->A));
        }
        else {
          return ListCell(head->B, merge(head->A, tail->B));
        }
      }
    

    Answer

16.   List merge(ConstList A, ConstList B)
      {
        if(A == NULL)
        {
          return ConstList B;
        }
        else if(B == NULL)
        {
          return ConstList A;
        }
        else if(head(A) ≤ head(B))
        {
          return cons(head(A) && merge(head(B), tail(A)));
        }
        else {
          return cons(head(B) && merge(head(A), tail(B)));
        }
      }
    

    Answer

17.   List merge(ConstList A, ConstList B)
      {
        if(A == NULL)
        {
          return B;
        }
        else if(B == NULL)
        {
          return A;
        }
        else if(B->head - A->head > 0)
        {
          return cons(A->head, merge(B->tail))
        }
        else {
          return cons(B->head, merge(A->tail))
        }
      }
    

    Answer

18.   List merge(ConstList A, ConstList B)
      {
        List final = new List[200];
        if(A == NULL)
        {
          return B;
        }
        else if(B == NULL)
        {
          return A;
        }
        else if(head(A) > head(B))
        {
          return merge(head(A), merge(tail B, A))
        }
        else {
          return merge(head(B), merge(tail B, B))
        }
      }
    

    Answer

19.   List merge(ConstList A, ConstList B)
      {
        List C = NULL;
        if(A = NULL)
        {
          return NULL;
        }
        else if(B = NULL)
        {
          return NULL;
        }
        else if(head(A) <= head(B))
        {
          C = cons(head(A), C);
          return merge(A->tail, B);
        }
        else if(head(A) > head(B))
        {
          C = cons(head(B), C);
          return merge(A, B->tail);
        }
      }
    

    Answer

20.   List merge(ConstList A, ConstList B)
      {
        List merge1 = NULL;
        while(A != NULL && B != NULL)
        {
          if(head(A) ≤ head(B))
          {
            merge1 = cons(head(A), merge1);
            A = tail(A);
          }
          else {
            merge1 = cons(head(B), merge1);
            B = tail(B);
          }
        }
        return merge1;
      }
    

    Answer