COMP SCI 2103 & 7103 Algorithm Design & Data Structure Semester 1, 2019
Practical 5: Recursion and Inheritance
Due date: 11:59pm, 3 May 2019
1 General Instructions
All submissions for the practical assignments should be under version control. Submission procedure remains the same with the first practical assignment.
The directory under version control for this assignment should be named as
https://version-control.adelaide.edu.au/svn/aXXXXXXX/YYYY/sX/adds/assignment5/
where aXXXXXXX is your student ID, ”YYYY” is the year and”sX” can be s1 or s2 for semester.
If you get stuck on one of the hidden test cases and really cannot resolve it yourself, please feel free to ask the practical tutors for hints.
We encourage you to finish your work before the practical session and take the session as consulting time.
2 Problem Description 2.1 Ob jective
This practical assignment will further test your knowledge on recursion, inheritance and polymorphism.
2.2 Design
In a file named design.pdf, describe how you are going to solve the problem and test your implementation with the test cases you designed based on the stages below. Testing Hint: it’s easier if you test things as a small piece of code, rather than building a giant lump of code that doesn’t compile or run correctly. As part of your design, you should also sketch out how you are going to build and test the code.
2.3 Problem
In this prac, you are asked to implement “map”, “filter” and “reduce” using C++. If you know some functional programming languages, you should have heard of these three names. We will describe the ideas in the following pages.
1
COMP SCI 2103 & 7103 Algorithm Design & Data Structure Semester 1, 2019
When we use programming to solve tasks, often, we need to deal with lists of stuffs. For example, databases are essentially lists of data entries and strings are basically lists of characters. “map”, “filter” and “reduce” allow convenient modification and aggregation of lists.
2.3.1 “map”
Firstly, let just look at the concept of “map”. Mathematically, given a list L = [x1, x2, · · · , xn] and a function f, by mapping f onto L, we get
map(f,L) = [f(x1),f(x2),···,f(xn)].
“map” can be applied whenever we want to apply operations to every element of the list. For example, to convert a list of characters to upper cases, we just map toUpper function onto the list, where toUpper converts lower cases to upper cases. Given a list of books, if we want the corresponding list of authors, we just map getAuthor function onto the list, where getAuthor(book) returns the correct author. Given a list of game units, if we want to heal them all (e.g., a Mage casted an area of effect (AOE) healing ability), then we just map heal onto the list of game units.
Now let us get back to C++. For simplicity, for this assignment, we only consider lists where the elements are integers, and we only consider functions that map integers to integers.
Your implementation should at the very least provide the following functionalities:
• Given a list of integers, the resulting list has every value tripled.
That is, [x1, x2, …, xn] becomes [3×1, 3×2, …, 3xn].
• Given a list of integers, the resulting list has every value raised to the power of 2.
That is, [x1, x2, …, xn] becomes [x21, x2, …, x2n].
• Given a list of integers, the resulting list has every member become the absolute value.
That is, [x1, x2, …, xn] becomes [|x1|, |x2|, …, |xn|].
In your implementation, you are required to use C++ standard vector for storing the
lists. One possible way to implement the above functionalities is as follows:
• We can create a base class with name MapGeneric, which has a private method int f(int) that specifies the operation we want to map onto a list. This method is overridden later in the derived classes to deliver specific map operations. The function f can be declared to be pure virtual (which means that you will not include a definition for this function in the base class, and the base class can not be instantiated).
• The MapGeneric class also has a public method
vector
that takes a vector as the input and returns the resulting vector after mapping. You should use recursion to implement this map function.
2
COMP SCI 2103 & 7103 Algorithm Design & Data Structure Semester 1, 2019
• Three derived classes MapTriple, MapSquare and MapAbsoluteValue can be im- plemented and each one overrides the original f method according to different re- quirement. For example, MapTriple::f(x) should return 3x.
2.3.2 “filter”
Mathematically, given a list L = [x1, x2, · · · , xn] and a function g(x) that returns a boolean value, if we filter L based on g(x), we end up with only elements that pass the g(x)test. That is, if g(x1) = g(x3) = g(x4) = true and g(x2) = g(x5) = false, then
filter(g, L) = [x1, x3, x4].
“filter” can be applied whenever we want to select some elements from a list. For example, to filter out all digits from a list of characters, we just filter isDigit() on the list, where isDigit() determines whether a character is a digit or not. Given a list of books, if we want to search for books that are novels, we just filter isNovel() from the list, where isNovel() returns whether the book is a novel or not. Given a list of game units, if we want to heal only the allied units, then we filter isAllied and then map heal.
Now let us get back to C++. For simplicity, for this assignment, the function used to filter elements only returns boolean.
Your implementation should at the very least provide the following functionalities:
• Given a list of integers, filter out the even values.
That is, [1,2,3,4,5,6,7] becomes [1,3,5,7].
• Given a list of integers, filter out the positive values:.
That is, [1, −1, 2, −2, 4, 7] becomes [−1, −2].
• Given a list of integers, select all two-digit positive numbers.
That is, [11, −1, 23, 4354, 1, 22, 4, −22] becomes [11, 23, 22].
In your implementation, you are required to use C++ standard vector for storing the
lists. One possible way to implement the above functionalities is as follows:
• We can create a base class with name FilterGeneric, which has a private method bool g(int) that specifies the operation we want to map onto a list. This method is overridden later in the derived classes to deliver specific map operations. The function g can be declared to be pure virtual.
• The FilterGeneric class also has a public method
vector
that takes a vector as the input and returns the resulting vector after filtering. You should use recursion to implement this filter function.
• ThreederivedclassesFilterOdd,FilterNonPositiveandFilterForTwoDigitPositive can be implemented and each one overrides the original g method according to dif- ferent requirement. For example, FilterOdd::g(x) should return true if and only
if x is odd.
3
COMP SCI 2103 & 7103 Algorithm Design & Data Structure Semester 1, 2019
2.3.3 “reduce”
Mathematically, given a list L = [x1, x2, · · · , xn] and a binary operator , then reduce(,L) = ((((x x )x )…)x ).
For example,
• if is +, then reduce(+, L) is simply the sum of all xi with i = 1…n.
• if is ∗, then reduce(∗, L) is simply the product of all xi with i = 1…n.
• if xi xj = max{xi, xj } is + which means the binary operator picks the larger operand as the result, then reduce(, L) is the maximum over the set L.
• if xi xj = xj , then reduce(, L) produces the last element of the list.
“reduce” can be applied for aggregating results as evidenced above. (It should be noted that here we are talking about a simplified version of “reduce”, so it may not look too impressive.)
Now let us get back to C++. For simplicity, for this assignment, we only consider lists where the elements are integers, and we only consider binary operators that take in two integer operands and produce one integer result. For simplicity, you may assume there is no list has less than 2 elements.
Your implementation should at the very least provide the following functionalities:
• Given a list of integers, use reduce to find out the minimum value.
• Given a list of positive integers, use reduce to find out the greatest common de- nominator of all the integers in the list.
In your implementation, you are required to use C++ standard vector for storing the lists. One possible way to implement the above functionalities is as follows:
• We can create a base class with name ReduceGeneric, which has a private method int binaryOperator(int, int) that specifies the operator. This method is over- ridden later in the derived classes to deliver specific map operations. The function binaryOperator can be declared to be pure virtual.
• The ReduceGeneric class also has a public method
int ReduceGeneric::reduce(vector
that takes a vector as the input and returns the result of reduce. You should use recursion to implement this reduce function.
• Two derived classes ReduceMinimum and ReduceGCD can be implemented and each one overrides the original binaryOperator method according to different require- ment. For example, ReduceMinimum::binaryOperator(x,y) should return the smaller value between x and y.
123n
4
COMP SCI 2103 & 7103 Algorithm Design & Data Structure Semester 1, 2019
2.4 Testing
Thetestscriptwillcompileyourcodeusingg++ -o main.out -std=c++11 -O2 -Wall *.cpp. It is your responsibility to ensure that your code compiles on the university system. g++
has too many versions, so being able to compile on your laptop does not guarantee that
it compiles on the university system. You are encouraged to debug your code on a lab computer (or use SSH).
You are asked to create a main function (main.cpp). It takes in one line of input. The input consists of exactly 20 integers.
Then in your main function,
• Construct a vector using these 20 integers. We denote the list by L = [x1, x2, …, x20].
• Convert the original list L to L′ = [3|x1|, 3|x2|, …, 3|xn|] using map (hint: map twice).
• From L′, select all positive two digit integers that are also odd (hint: filter twice). Let the resulting list be L′′.
• Compute the minimum value and the greatest common denominator of L′′ (using reduce). Output the results, separated by space (output should be “min gcd”).
Sample input: 6, -11, 53, -16, 73, 128, 105, 104, -71, -179, 102, 12, 21, -145, -99, 199, -156, -186, 43, -189
Sample output: 33 3
For your reference, L′ = [18, 33, 159, 48, 219, 384, 315, 312, 213, 537, 306, 36, 63, 435,
297, 597, 468, 558, 129, 567], L′′ = [33, 63].
Sample input: -5, -24, -123, -81, 200, 157, 84, 67, -83, -60, -72, 192, -25, -20, -50, -181,
-70, -15, -108, -123 Sample output: 15 15
For your reference, L′ = [15, 72, 369, 243, 600, 471, 252, 201, 249, 180, 216, 576, 75, 60, 150, 543, 210, 45, 324, 369], L′′ = [15, 75, 45].
3 Marking Scheme
Your submission should contain at least design.pdf, main.cpp and other cpp files and header files.
This practical is worth 3% of your final mark. Every practical assignment is marked out of 6.
• Design (2 marks):
– Diagram of central classes and explanation of core functions (1 mark)
5
COMP SCI 2103 & 7103 Algorithm Design & Data Structure Semester 1, 2019
– Details of your own test cases/schemes (1 mark) • Style (2 marks):
– Proper usage of C++ language elements and paradigm (1 mark) – Comments on non-trivial code blocks and functions (1 mark)
• Functionality (2 marks):
– Passing public test cases (1 mark)
– Passing hidden test cases (1 mark)
6