This assignment should be done in Java; its purpose is to gain familiarity with the Java List libraries. A good way to get documentation of the Java libraries is to Google, for example, "Java LinkedList".

- Write a function
`sumlist(LinkedList<Integer> lst)`that adds up a list of`Integer`. Write a similar function`sumarrlist(ArrayList<Integer> lst)`. - Write a function
`subset(Predicate p, LinkedList<Object> lst)`that returns a new list containing only the values in`lst`that satisfy the predicate`p`. We will assume that`p.pred(item)`can be used to test an item. - Write a destructive function
`dsubset(Predicate p, LinkedList<Object> lst)`that removes from`lst`the values that do not satisfy the predicate`p`. - Write a function
`some(Predicate p, LinkedList<Object> lst)`that returns the first item in`lst`that satisfies the predicate`p`. If no item satisfies the predicate, return`null`. - Write a function
`mapcar(Functor f, LinkedList<Object> lst)`that returns a new list containing the results of applying`f.fn(item)`to each item in the list`lst`. The output list should be in the same order as the original list.We will be especially interested in

`mapcar`because it is the first component of MapReduce, which we will study later. Many kinds of computations can be described using MapReduce. MapReduce runs in parallel on networks of hundreds of thousands of processors at Google. - Write a function
`merge(LinkedList<Object> lsta, LinkedList<Object> lstb)`that returns a new list formed by merging the two input lists in order. The input lists are assumed to be in sorted order (ascending). We will assume that the elements of the lists can be cast to`(Comparable)`so that they support`.compareTo()`. Duplicates should be retained in a merge. - Write a function
`sort(LinkedList<Object> lst)`that produces a sorted list containing the elements of the input list. A list with only one element is sorted; otherwise, produce two new lists, each with half the input elements, sort the sublists (by calling this function recursively) and merge them. How does the Big O() of this sort compare to the Big O() of the destructive merge sort in the class notes? What is the Big O of garbage that is produced by this sort function? - Write a function
`intersection(LinkedList<Object> lsta, LinkedList<Object> lstb)`that returns a new list that is the set intersection of the two input lists. Sort the input lists first and use the merge technique to form the intersection. - Write a function
`reverse(LinkedList<Object> lst)`that produces a new list in the reverse order of the input list. The method`.addFirst(Object o)`is an O(1) way to add an element at the front of a list, so that a linked list can be used as a stack as well as a queue.