Conceptual | C++ notation |
---|---|
[ ] | NULL or emptyList |
isEmpty(L) or L = [ ] | isEmpty(L) or L == NULL or L == emptyList |
head(L) | head(L) or L->head |
tail(L) | tail(L) or L->tail |
h : t | cons(h, t) or new ListCell(h, t) |
[1,2,3] or 1:2:3:[ ] | cons(1, cons(2, cons(3, NULL))) |
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.
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.
The first equation for successors should be
successors([]) = [].
successors([]) = NULL
Answersuccessors([]) = h+1 : []
Answersuccessors([]) = [n]
Answersuccessors([]) = return successors of L
Answersuccessors([]) = L
Answersuccessors([]) = head : 0
Answersuccessors([]) = 1:[]
AnswerThe second equation for successors should be
successors(L) = head(L) : successors(tail(L)) (when L is not empty).
successors(L) = head(L) : head(tail(L))
Answersuccessors(L) = head(L) : 1 : tail(L)
Answersuccessors(L) = L->head + 1 : successors(L->tail)
Answersuccessors(L) = cons(head(L) + 1, successors(tail(L))
Answersuccessors(L) = con(L->head, successors)
Answersuccessors(L) = h:t + 1
Answersuccessors(L) = head(L) + 1 : L
Answersuccessors(L) = [n+1]
Answersuccessors(L) = n+1 to member of list
Answersuccessors(L) = 1 + head[L] : tail[L]
Answersuccessors(L) = const(head + 1)
Answersuccessors(L) = cons(L->head, successors(L->tail))
Answersuccessors(L) = new ListCell(L->head+1, successors(L->tail))
Answersuccessors(L) = head++ : tail++
Answersuccessors(L) = L(head) + 1
Answersuccessors(L) = return L head and loop again
Answersuccessors(L) = L(n+1)
Answersuccessors(L) = [3, -8, -4, 5] + [4, -7, -3, 6]
Answersuccessors(L) = head(L) + 1 : tail(L) + 1
Answersuccessors(L) = list integers = n+1
Answersuccessors(L) = head(L) + 1 : head(tail(L)) + 1
Answersuccessors(L) = head(L) : successors(tail(L) + 1)
Answersuccessors(L) = cons(head + 1, successor(tail))
Answersuccessors(L) = [head(L) + 1, successors(tail(L))]
Answersuccessors(L) = 1 + n : successors(tail(L))
Answersuccessors(L) = head(L) + 1 : head(L) : 1
Answersuccessors(L) = new List(L) + 1
Answersuccessors(L) = L + 1
Answersuccessors(L) = A = (head(L) + 1) : A
AnswerThe first equation for merge should be
successors([], B) = B.
merge([], B) = [B]
Answermerge([], B) = head(B) : tail(B)
Answermerge([], B) = B:[]
Answermerge([], B) = [A]
Answermerge([], B) = true
Answermerge([], B) = [], [3,5,6,13]
Answermerge([], B) = merge(B, tail(B))
Answermerge([], B) = return B head and tail
Answermerge([], B) = returns B
Answermerge([], B) = []:B
Answermerge([], B) = A->head A = A->tail
Answermerge([], B) = merge(emptylist, B)
AnswerThe third equation for merge should be
successors(A, B) = head(A) : merge(tail(A), B) (when head(A) < head(B)).
merge(A, B) = head(A) : B
Answermerge(A, B) = cons(head(A), merge(tail(A), B))
Answermerge(A, B) = new ListCell(head(A), merge(tail(A), B))
Answermerge(A, B) = [A,B]
Answermerge(A, B) = head(A):head(B) -> head(tail(A)) < head(tail(B))
Answermerge(A, B) = [X + Y]
Answermerge(A, B) = head(A)
Answermerge(A, B) = head(A) = head(C)
Answermerge(A, B) = head(B) : merge(A, tail(B))
Answermerge(A, B) = return head of B and loop again
Answermerge(A, B) = head(B) tail(A)
Answermerge(A, B) = h(A), h(B)) : (A,B)
Answermerge(A, B) = A:B = [A,B]
Answermerge(A, B) = B:A
Answermerge(A, B) = returns list A before B
Answermerge(A, B) = [head(A), head(B)]
Answermerge(A, B) = head(A) + tail(A) + head(B) + tail(B)
Answermerge(A, B) = cons(A->head, merge(A->tail, B))
Answermerge(A, B) = [B,A] merge(tail(A), tail(B))
Answermerge(A, B) = [head(A), merge(head(B), tail(A))]
Answermerge(A, B) = head(A) and merge(tail(A), tail(B))
Answermerge(A, B) = head(A) : tail(B)
Answermerge(A, B) = cons(head(A) : head(B) : tail(B)
Answermerge(A, B) = A : cons(tail(A), B)
Answermerge(A, B) = List merge1 = cons(head(A), tail(merge1))
Answermerge(A, B) = cat(head(A), head(B), tail(A), tail(B))
Answermerge(A, B) = merge(A,B)
Answermerge(A, B) = C = head(A) : C merge(A->tail, B)
AnswerA correct definition of successors is
List successors(ConstList L) { if(L == NULL) { return NULL; } else { return cons(head(L) + 1, successors(tail(L))); } }
List successors(ConstList L) { if(isEmpty(L)) { return; } ... }Answer
List successors(ConstList L) { if(L == NULL) { return isEmpty(L); } ... }Answer
List successors(ConstList L) { List B = new List(L->head, L->tail); ... }Answer
List successors(ConstList L) { List K = new List; ... }Answer
List successors(ConstList L) { if(L->tail == NULL) { ... }Answer
List successors(ConstList L) { if(L == NULL) { return NULL; } else { return successors(L->tail); } }Answer
List successors(ConstList L) { if(L == NULL) { return NULL; } else { int h = L->head; ConstList t = L->tail; return cons(h++, successors(t)); } }Answer
List successors(ConstList L) { if(L == NULL) { return NULL; } else { L->head++; L->tail++; successor(L); } }Answer
List successors(ConstList L) { List* p = new List; p = L; if(p == NULL) { return NULL; } else { return successors(p->head + 1); } }Answer
List successors(ConstList L) { if(L == NULL) { return NULL; } else { return successors(L); } }Answer
List successors(ConstList L) { List sL = []; if(isEmpty(L) == true) { return sL; } else { sL = cons(head(L) + 1, NULL); return successors(tail(L)); } }Answer
List successors(ConstList L) { if(L == NULL) { return NULL; } else { cons(head(L), successors(tail(L) + 1)); } }Answer
List successors(ConstList L) { if(L == NULL) { return NULL; } else { return cons(head(L), successors(tail(L))); } }Answer
List successors(ConstList L) { if(L == NULL) { return NULL; } else { return ListCell(L->head + 1, successors(L->tail)); } }Answer
List successors(ConstList L) { if(L->tail == NULL) { return new ListCell(L->head + 1, NULL); } ... }Answer
List successors(ConstList L) { if(L == NULL) { return 0; } ... }Answer
List successors(ConstList L) { List* s = new ListCell(); if(isEmpty(L)) { return cons((L->head + 1, s); } ... }Answer
List successors(ConstList L) { if(L == NULL) { // do nothing } else { return L(n+1); } }Answer
List successors(ConstList L) { if(L == NULL) { return 0; } else { List N = L; N->head = head + 1; N->tail = tail + 1; return N; } }Answer
List successors(ConstList L) { if(L == []) { return []; } ... }Answer
List successors(ConstList L) { if(successors = NULL) { return NULL; } ... }Answer
List successors(ConstList L) { List s = new List; while(L != NULL) { s:(head(L) + 1); } return s; }Answer
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))); } }
List merge(ConstList A, ConstList B) { if(A == NULL) { return new ListCell(B.head, B.tail); } ... }Answer
List merge(ConstList A, ConstList B) { if(A == NULL) { return new List(B->head, B->tail); } ... }Answer
List merge(ConstList A, ConstList B) { if(A == []) { return B; } ... }Answer
List merge(ConstList A, ConstList B) { List C = new List; if(A == []) { C = merge(B, tail(B)); } ... }Answer
List merge(ConstList A, ConstList B) { if(A->head >= B->head) { return merge(A->tail, B->tail); } ... }Answer
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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