...
Homework 7 (Due 11:59pm Thursday, November 5, 2020)
Submit via SVN
Preliminaries
...
- (10 pts.)
boolean contains(int key)
returnstrue
ifkey
is in the list,false
otherwise. - (10 pts.)
int reverse()
constructs a list that is the reversal of this. - (10 pts.)
int sum()
computes the sum of the elements in the list. - (10 pts.)
double average()
computes the average of the elements in the list; returns0
if the list is empty.
Hint: you can cast anint
todouble
by using the prefix casting operator(double)
. - (10 pts.)
IntList notGreaterThan(int bound)
returns a list of elements in this list that are less or equal tobound
. - (10 pts.)
IntList remove(int key)
returns a list of all elements in this list that are not equal tokey
. - (10 pts.)
IntList subst(int oldN, int newN)
returns a list of all elements in this list witholdN
replaced bynewN
. - (30 15 pts.)
IntList merge(IntList other)
merges this list with the input list other, assuming that this list and other are sorted in ascending order. Note that the lists need not have the same length.
Hint: add a methodmergeHelp(ConsIntList other)
that does all of the work if one list is non-empty (aConsIntList
). OnlymergeHelp
is recursive. Use dynamic dispatch on the list that may be empty. Recall thata.merge(b)
is equivalent tob.merge(a)
. You can formulate help methods as visitors. - (15 pts.)
IntList mergeSort()
. Leveraging themerge
"method" you just wrote (as a visitor), writemergeSort()
that sorts anIntList.
Recall that you need to write a help function that splits a list approximately in two.