Programming Exercise: Set Comparisons - Counting
In this exercise, we will develop a technique for comparing the
contents of two multi-sets (the mathematical term "set" means roughly
"group of items whose order doesn't matter, which cannot have
duplicated values." "Multi-set" means "set of items where each value
may be duplicated an arbitrary number of times.")
Remeber that to use vectors you need to have #include
<vector> in your file.
3 points
- Write a function bool isSameList(const vector<int>&
l1, const vector<int> l2); that takes two ordered lists
and decides if they are the same.
- Write a function int count(const vector<int>& l, int
n) that counts the number of times n appears in l.
- Write a function int maxVal(const vector<int>& l)
that returns the maximum value in the list.
- Write a function vector<int> counts(const
vector<int>& l) that returns the number of times each
integer value appears in l (So if is the list [1, 4, 2, 5,
2, 1], counts should return [0, 2, 2, 0, 1, 1] since there are no
zeros, 2 ones, 2 twos, no threes, one four, and one five in the list.)
Hint: you will want to return a vector of size max(l).
- Write a function isSameSet(const vector<int>&l1,
const vector<int>&l2) that uses counts and
isSameList to decide if the values in l1 and l2
appear the same number of times (and thus l1 and l2
represent the same multi-set).
Extra Credit Options
- 1 points: Rewrite all of these functions only using
while loops (no for loops).
- 2 points: Rewrite counts to run in linear time
instead of quadratic time. (It may only make 1 pass through the list
after calling max).