CS2030 Practical Assessment #2

Back to homepage

Divide-and-Conquer is an algorithmic paradigm that solves a computation problem which can be broken down into smaller sub-problems of the same type, and the solutions of these sub-problems should make up part of the solution of the original problem.

As an example, given a pair of integers a and b (a <= b), the sum of squares of each number, sumSq(a,b), between a and b (both inclusive) can be defined with a solution that makes use of the divide and conquer algorithmic paradigm. A recursive solution of the above problem is given below:

jshell> int sumSq(int a, int b) {
   ...>     if (a == b) {
   ...>         return a * a;
   ...>     } else {
   ...>         int mid = (a + b) / 2;
   ...>         return sumSq(a, mid) + sumSq(mid + 1, b);
   ...>     }
   ...> }
| created method sumSq(int,int)
jshell> sumSq(5, 7)
$.. ==> 110
jshell> sumSq(5, 15)
$.. ==> 1210

Suppose we are given the pair of values (5, 7). Following the recursive solution above, the sum of squares can be worked out to be

sumSq(5, 7) = sumSq(5, 6) + sumSq(7, 7)
 = (sumSq(5, 5) + sumSq(6, 6)) + sumSq(7, 7)
 = (25 + 36) + 49
 = 110

A general solution that makes use of the divide and conquer algorithm paradigm is given below:

• Decide if the given problem can be further divided into smaller sub-problems.
• If the problem is atomic, i.e. cannot be subdivided further, then return the trivial solution to this problem.
• Otherwise, divide the problem into a pair of sub-problems, and recursively solve (conquer) the sub-problems.
• Combine the solutions of the sub-problems appropriately.

There are many other algorithms that makes use of the divide and conquer algorithmic paradigm. Each divide-and-conquer algorithm aims to solve a problem (represented as type T) that results in a solution (of type R). For example,

• Sum of squares — problem represented as a pair of integers, with the result as an integer;
• Summing the integer elements in a non-empty list — problem represented as a list, with the result as an integer;
• Merge sort — problem represented as a non-empty list, with the result as a list;
• ...

Task

In this task, you are to write a generic solver for solving problems using the divide and conquer algorithmic paradigm. A client that makes use of the solver need only provide the respective parts of the general solution, while disregarding the intricacies of recursion.

Take Note!

This task comprises a number of levels. You are required to complete ALL levels.

The following are the constraints imposed on this task. In general, you should keep to the constructs and programming discipline instilled throughout the module.

• Write each class or interface in its own file. Do not use single letter names for classes or interfaces.
• Ensure that ALL object properties and class constants are declared private final, unless otherwise specified.
• Ensure that that your classes are NOT cyclic dependent.
• ONLY the following java libraries ARE allowed:
  • java.util.List
  • java.util.Optional
  • functional interfaces from java.util.function
• The following are NOT allowed:
  • null
  • instanceof
  • if..else, switch..case, ?: conditional expression
  • for, while
  • enum
  • Optional methods: isPresent(), isEmpty(), get() and equals(Object)
  • methods of the String class
• There is no need to use bounded wildcards.
• You are NOT allowed to define anonymous inner classes; define lambdas instead.
• Other usual restrictions:
  • Use only &&, || and ! in logical expressions.
  • You are NOT allowed to use * wildcard imports.
  • You are NOT allowed to use method references ::
  • You are NOT allowed to define array constructs, e.g. String[] or using ellipsis, e.g.String...
  • You are NOT allowed to use Java reflection, i.e. Object::getClasses and other methods from Class

The Pair class with an additional of method to simplify the creation of Pair objects is provided for you.

Level 1

Let us start by creating a generic DnC<T,R> (for divide and conquer) class to handle problems of type T with a solution of type R.

• Write a static of method that creates the DnC. The method takes in the following arguments in order:
  • a problem of type T,
  • a Predicate<T> that checks whether the problem is atomic, and
  • a Function<T,R> representing the trivial solution that transforms the problem of type T to a value of type R.
• Write a void peek(Consumer<T> action) method that performs the action on the problem of type T. We use this to output the problem encapsulated within the DnC. As such, you do not need to write any toString() method in the DnC class.

To illustrate, the sum of squares problem described above can be represented as a Pair<Integer,Integer> with a and b encapsulated in a Pair.

jshell> Pair<Integer,Integer> p = Pair.of(5, 5) // (a, b)
p ==> (5, 5)

jshell> Predicate<Pair<Integer, Integer>> pred =
   ...> pair -> pair.first() == pair.second() // atomic if a == b
pred ==> $Lambda$15/0x00000008000b0040@4b9e13df

jshell> Function<Pair<Integer, Integer>, Integer> f =
   ...> pair -> pair.first() * pair.first() // trivial solution a*a
f ==> $Lambda$16/0x00000008000b0440@1d057a39

jshell> DnC<Pair<Integer,Integer>, Integer> dnc = DnC.of(p, pred, f)
dnc ==> DnC@4c70fda8

jshell> dnc.peek(x -> System.out.println(x))
(5, 5)

jshell> p = Pair.of(5, 7)
p ==> (5, 7)

jshell> dnc = DnC.of(p, pred, f)
dnc ==> DnC@28d25987

jshell> dnc.peek(x -> System.out.println(x))
(5, 7)

Here is another example that sums up integer elements in a non-empty list. Note that the problem is of type List<Integer> with a solution type of Integer.

jshell> DnC.of(List.of(1), list -> list.size() == 1, list -> list.get(0)).
   ...> peek(x -> System.out.println(x))
[1]

jshell> DnC.of(List.of(1, 2, 3), list -> list.size() == 1, list -> list.get(0)).
   ...> peek(x -> System.out.println(x))
[1, 2, 3]

Level 2

We now handle atomic problems of type T with a trivial solution of type R.

• Write a solve() method that takes no arguments, and returns the solution wrapped within an Optional if the problem is atomic, or Optional.empty otherwise.

The sum of squares problem (5, 5) is atomic. Hence, there is a trivial solution of 25.

jshell> Pair<Integer,Integer> p = Pair.of(5, 5)
p ==> (5, 5)

jshell> Predicate<Pair<Integer, Integer>> pred = pair -> pair.first() == pair.second()
pred ==> $Lambda$15/0x00000008000b1040@26be92ad

jshell> Function<Pair<Integer, Integer>, Integer> f = pair -> pair.first() * pair.first()
f ==> $Lambda$16/0x00000008000b1440@14acaea5

jshell> DnC<Pair<Integer,Integer>, Integer> dnc = DnC.of(p, pred, f)
dnc ==> DnC@59fa1d9b

jshell> dnc.solve()
$.. ==> Optional[25]

However, the sum of squares problem (5, 7) is non-atomic with no trivial solution.

jshell> p = Pair.of(5, 7)
p ==> (5, 7)

jshell> dnc = DnC.of(p, pred, f)
dnc ==> DnC@5b275dab

jshell> dnc.solve()
$.. ==> Optional.empty

For the problem of summing integer elements in a non-empty list, the trivial solution arises when the list has exactly one element. A list with more than one element does not have a trivial solution.

jshell> DnC.of(List.of(1), list -> list.size() == 1, list -> list.get(0)).solve()
$.. ==> Optional[1]

jshell> DnC.of(List.of(1, 2, 3), list -> list.size() == 1, list -> list.get(0)).solve()
$.. ==> Optional.empty

Level 3

Now consider the case when the problem is non-atomic. We need to extend the generic class DnC to include the pair of sub-problems.

• Write an overloaded of method that takes in an additional argument of type Function<T,Pair<T,T>> that transforms the current problem of type T to a pair of sub-problems Pair<T,T>.
• Write a left() method that returns the left sub-problem of the current problem as a DnC.
• Write a right() method that returns the right sub-problem of the current problem as a DnC.

As an example, if the current sum of squares problem is represented by the pair (5, 7), then this problem can be broken down into a pair of sub-problems. Invoking left() returns the left sub-problem (5, 6); invoking right() returns the right sub-problem (7, 7). Note that if the current problem is atomic, left() and right() will return the same problem.

jshell> Pair<Integer,Integer> p = Pair.of(5, 7)
p ==> (5, 7)

jshell> Predicate<Pair<Integer, Integer>> pred = pair -> pair.first() == pair.second()
pred ==> $Lambda$15/0x00000008000b0040@4b9e13df

jshell> Function<Pair<Integer, Integer>, Integer> f = pair -> pair.first() * pair.first()
f ==> $Lambda$16/0x00000008000b0440@1d057a39

jshell> DnC<Pair<Integer,Integer>, Integer> dnc = DnC.of(p, pred, f, 
   ...>     pair -> {
   ...>         int a = pair.first();
   ...>         int b = pair.second();
   ...>         int mid = (a + b) / 2;
   ...>         return Pair.of(Pair.of(a, mid), Pair.of(mid + 1, b));
   ...>     })
dnc ==> DnC@224edc67

jshell> dnc.peek(x -> System.out.println(x))
(5, 7)

jshell> dnc.left().peek(x -> System.out.println(x))
(5, 6)

jshell> dnc.left().left().peek(x -> System.out.println(x))
(5, 5)

jshell> dnc.left().left().left().peek(x -> System.out.println(x))
(5, 5)

jshell> dnc.peek(x -> System.out.println(x))
(5, 7)

jshell> dnc.right().peek(x -> System.out.println(x))
(7, 7)

jshell> dnc.right().right().peek(x -> System.out.println(x))
(7, 7)

jshell> dnc.left() instanceof DnC
$.. ==> true

jshell> dnc.right() instanceof DnC
$.. ==> true

jshell> dnc.solve()
$.. ==> Optional.empty

jshell> dnc.left().solve()
$.. ==> Optional.empty

jshell> dnc.left().left().solve()
$.. ==> Optional[25]

jshell> dnc.right().solve()
$.. ==> Optional[49]

jshell> dnc.right().right().solve()
$.. ==> Optional[49]

Notice from the above that only an atomic problem will give the solution when solve() is invoked.

Level 4

We are now ready to solve the sum of squares problem.

• Write an overloaded solve method that takes in a BinaryOperator<R> that combines the solutions.

jshell> Pair<Integer,Integer> p = Pair.of(5, 7)
p ==> (5, 7)

jshell> Predicate<Pair<Integer, Integer>> pred = pair -> pair.first() == pair.second()
pred ==> $Lambda$15/0x00000008000b0040@4b9e13df

jshell> Function<Pair<Integer, Integer>, Integer> f = pair -> pair.first() * pair.first()
f ==> $Lambda$16/0x00000008000b0440@1d057a39

jshell> DnC<Pair<Integer,Integer>, Integer> dnc = DnC.of(p, pred, f, 
   ...>     pair -> {
   ...>         int a = pair.first();
   ...>         int b = pair.second();
   ...>         int mid = (a + b) / 2;
   ...>         return Pair.of(Pair.of(a, mid), Pair.of(mid + 1, b));
   ...>     })
dnc ==> DnC@224edc67

jshell> BinaryOperator<Integer> bop = (x,y) -> x + y
bop ==> $Lambda$18/0x00000008000b1440@59fa1d9b

jshell> dnc.solve()
$.. ==> Optional.empty

jshell> dnc.solve(bop)
$.. ==> Optional[110]

jshell> dnc.left().solve(bop) // 5*5 + 6*6
$.. ==> Optional[61]

jshell> dnc.left().left().solve(bop) // the trivial solution 5*5
$.. ==> Optional[25]

Note that the last test case produces an atomic problem, so the trivial solution is returned.

Level 5

Now suppose you are given the following pairOf method which returns a pair of integers:

jshell> Pair<Integer,Integer> pairOf(int a, int b) {
   ...>     Pair<Integer,Integer> pair = Pair.of(a, b);
   ...>     System.out.println(pair + " evaluated");
   ...>     return pair;
   ...> }
| created method pairOf(int,int)

jshell> Predicate<Pair<Integer, Integer>> pred = pair -> pair.first() == pair.second()
pred ==> $Lambda$15/0x00000008000a9440@4f933fd1

jshell> Function<Pair<Integer, Integer>, Integer> f = pair -> pair.first() * pair.first()
f ==> $Lambda$16/0x00000008000ab040@7c16905e

jshell> DnC<Pair<Integer,Integer>, Integer> dnc = DnC.of(pairOf(5, 7), pred, f, 
   ...>     pair -> {
   ...>         int a = pair.first();
   ...>         int b = pair.second();
   ...>         int mid = (a + b) / 2;
   ...>         return Pair.of(pairOf(a, mid), pairOf(mid + 1, b));
   ...> })
(5, 7) evaluated
dnc ==> DnC@59fa1d9b

Notice that creating the DnC without solving it will result in pairOf(5, 7) to be evaluated once. Moreover, solving the problem might give repeated evaluations of the same problem/sub-problem. The ordering below might be different from yours; what is important is the occurrence of repeated evaluations.

jshell> BinaryOperator<Integer> bop = (x,y) -> x + y
bop ==> $Lambda$21/0x00000008000b2440@5b275dab

jshell> dnc.solve(bop)
(5, 6) evaluated
(7, 7) evaluated
(5, 5) evaluated
(6, 6) evaluated
(5, 5) evaluated
(6, 6) evaluated
(5, 6) evaluated
(7, 7) evaluated
$.. ==> Optional[110]

To ensure that each problem or sub-problem is evaluated only once, we wrap the problem of type T around a Supplier.

• For the four-argument of method defined earlier, include another overloaded four-argument of method where the first argument (i.e. the problem of type T) is wrapped in a Supplier<T> instead.

You will also need to make some additional modifications to the existing implementation of the DnC class.

jshell> dnc = DnC.<Pair<Integer,Integer>,Integer>of(() -> pairOf(5, 7), pred, f, 
   ...>     pair -> {
   ...>         int a = pair.first();
   ...>         int b = pair.second();
   ...>         int mid = (a + b) / 2;
   ...>         return Pair.of(() -> pairOf(a, mid), () -> pairOf(mid + 1, b));
   ...>     })
dnc ==> DnC@42d80b78

Side note: the type-witness above is necessary to avoid type binding ambiguities by forcing Supplier<Pair<Integer,Integer>> to be bound to Supplier<T> and not T.

jshell> BinaryOperator<Integer> bop = (x,y) -> x + y
bop ==> $Lambda$21/0x00000008000b2440@5b275dab

jshell> dnc.solve(bop)
(5, 7) evaluated
(5, 6) evaluated
(5, 5) evaluated
(6, 6) evaluated
(7, 7) evaluated
$.. ==> Optional[110]

Notice that the creation of a DnC no longer produce any evaluations, and the outcome of dnc.solve(bop) evaluates each problem/sub-problem only once. Moreover, the evaluation is done in a depth-first manner, i.e. the left sub-problems will be evaluated before the right sub-problems.

Level 6

Let's use the DnC class for summing the elements of a List of integers.

Create a SumList class by adhering to the following:

• The SumList class inherits from the DnC class;
• Write a constructor that takes in a List<Integer>;
• You are only allowed to write ONE constructor; you cannot include any other methods or - properties;
• You are allowed to expose existing constructors (or additional constructors) in DnC to its sub-classes so as to facilitate the creation of the SumList object.

Here is a sample run of how SumList works. Only the following methods will be tested:

• left()
• right()
• solve(BinaryOperator)

jshell> SumList sumlist = new SumList(List.of(1, 2, 3, 4, 5))
sumlist ==> SumList@20e2cbe0

jshell> sumlist instanceof DnC
$.. ==> true

jshell> sumlist.solve((x,y) -> x + y)
$.. ==> Optional[15]

jshell> sumlist.left().solve((x,y) -> x + y)
$.. ==> Optional[6]

jshell> sumlist.right().solve((x,y) -> x + y)
$.. ==> Optional[9]

jshell> sumlist.right().right().solve((x,y) -> x + y)
$.. ==> Optional[5]

jshell> sumlist.right().right().right().solve((x,y) -> x + y)
$.. ==> Optional[5]

Addendum:

• SumList can be used for more than just summing. It should probably be called OpIntList instead, since we can pass other forms of BinaryOperator like (x,y) -> x * y
• Some of you would probably use the subList method of List in SumList. As a challenge, think of a solution without using subList and still adhere to the restrictions.