All of the lists for this problem set are lists of integers,
The C++ problems use the following type Cell.
struct Cell
{
Cell* next;
int item;
Cell(int i, Cell* n)
{
item = i;
next = n;
}
};
Suppose that drop(n, L) is intended to return the list that you get by removing the first n members of list L. For example, drop(2, [4,7,9,0,3]) = [9,0,3] and drop(0, [2,4,6,8]) = [2,4,6,8]. If n is larger than the length of L then drop(n, L) = [ ]. For example, drop(8, [2,4,6]) = [ ].
Using the conceptual view of lists that we have used in class, write equations that tell how to compute drop(n, L) for any nonnegative number n and any list L. Check that your equations are true by trying an example of each.
Translate the equations for drop that you got in the preceding question to yields a C++ definition of function drop.
Suppose that take(n, L) is intended to return the length n prefix of list L. For example, take(2, [4,7,9,0,3]) = [4,7], take(3, [2,4,6,8,10,12,14]) = [2,4,6], take(1, [2,4,6]) = [2] and take(0, [1,2,3,4]) = [ ]. If n is larger than the length of L then take(n, L) = L. For example, take(8, [2,4,6]) = [2,4,6].
Using the conceptual view of lists that we have used in class, write equations that tell how to compute take(n, L) for any nonnegative number n and any list L. Check that your equations are true by trying an example of each.
Translate the equations that you derived for the preceding question to produce a definition of function take in C++.
Suppose that isPrefix(A, B) is intended to return true if list A is a prefix of list B. For example, isPrefix([2,4], [2,4,6]) = true but isPrefix([2,4], [2,5,4]) = false. Every list is a prefix of itself, so isPrefix([3,6,8], [3,6,8]) = true. The empty list is a prefix of every list, so isPrefix([ ], [2,9]) = true.
Using the conceptual view of lists that we have used in class, write equations that tell how to compute isPrefix(A, B) for any two lists A and B. Check that your equations are true by trying an example of each.
Translate your equations for isPrefix into a C++ definition of function isPrefix.
Suppose that function removeFirst(n, L) is intended to return the result of removing the first occurrence of n from list L. For example, removeFirst(4, [2,4,6]) = [2,6], removeFirst(3, [3,5,3]) = [5,3] and removeFirst(8, [8]) = [ ]. If n does not occur in list L, then removeFirst(n, L) = L. For example, removeFirst(3, [2,4,6]) = [2,4,6].
Using the conceptual view of lists that we have used in class, write equations that tell how to compute removeFirst(n, L) for any integer n and list L. Check that your equations are true by trying an example of each.
Translate your equations for removeFirst into a C++ definition of removeFirst. Notice that removeFirst does not change the list. It builds a new list.
(This problem requires more thought than previous problems, but it is well within your reach.) Say that list A is a sublist of list B if you can obtain list A by removing zero or more members of list B, without rearranging the remaining members. For example, [2,3,6] is a sublist of [1,2,3,4,5,6,7], since you can obtain list [2,3,6] by removing the 1, 4, 5 and 7 from [1,2,3,4,5,6,7]. Since you can delete no members, every list is a sublist of itself. Since you are not allowed to do any rearrangement, [2,4,5] is not a sublist of [4,2,5].
Suppose that isSublist(A, B) is intended to return true if list A is a sublist of list B. Using the conceptual view of lists that we used in class, write equations that tell how to compute isSublist(A, B) for any lists A and B. Check your equations using examples.
Hint. The empty list is a sublist of every list, and it is the only sublist of the empty list. For longer lists, you are trying to match up members of B with corresponding members of A, possibly ignoring some members of B. When there is a match between the first members of A and B, it is always safe to presume that those two values are a correct match. For example, isSublist([2,4,6], [2,3,4,5,6]) = isSublist([4,6], [3,4,5,6]) because you can assume that, if it is possible to remove zero or members of [2,3,4,5,6] to yield [2,4,6], you can always do that by leaving the 2 at the beginning of [2,3,4,5,6] and removing other members (if any).
Translate your equations for isSublist(A, B) from the preceding question into C++. That is, define isSublist in C++.