Solution for Assignment 3

Before reading this, be sure to read the hint that was given in the assignment document as it contains 95% of what you need. The last remaining 5% is given here. The solution hinges on a few decisions that are needed for each element.

1. Does the element belong to subset 1?
2. Does the element belong to subset 2?
3. Does the element belong to neither subset?

The recursive Scheme code that fits these are the following, respectively

1. (mes (cdr list) (+ sublist1 (car list)) sublist2 (+ sub1length 1) sub2length)
2. (mes (cdr list) sublist1 (+ sublist2 (car list)) sub1length (+ sub2length 1))
3. (mes (cdr list) sublist1 sublist2 sub1length sub2length)

If we assign these to the letters F, G, and H (so F maps to the first recursive call, G maps to the second recursive call, and H maps to the third) and replace the letters in the starting code with the recursive calls we have all but the base case.

x
(define max-equal-sublists (lambda (list sublist1 sublist2 sub1length sub2length)
            (cond
                ((null? list) ;we'll get to base case next)
                ((> (mes (cdr list) (+ sublist1 (car list)) sublist2 (+ sub1length 1) sub2length)
                    (mes (cdr list) sublist1 (+ sublist2 (car list)) sub1length (+ sub2length 1)))
                 (mes (cdr list) (+ sublist1 (car list)) sublist2 (+ sub1length 1) sub2length))
                ((> (mes (cdr list) sublist1 (+ sublist2 (car list)) sub1length (+ sub2length 1))
                    (mes (cdr list) sublist1 sublist2 sub1length sub2length))
                 (mes (cdr list) sublist1 (+ sublist2 (car list)) sub1length (+ sub2length 1)))
                (else (mes (cdr list) sublist1 sublist2 sub1length sub2length))
             )  
     )
)

The base case is just checking if our sublists and lengths are the same. Hence we do the following

(if (and (= sublist1 sublist2)(= sub1length sub2length)) sub1length 0)

If the sublists and sublengths are the same then return sub1length (Since they are the same, this is okay.). If one of these conditions or both conditions are not true the return 0. The full code looks like the following

x
(define max-equal-sublists (lambda (list sublist1 sublist2 sub1length sub2length)
            (cond
                ((null? list) (if (and (= sublist1 sublist2)(= sub1length sub2length)) sub1length 0))
                ((> (mes (cdr list) (+ sublist1 (car list)) sublist2 (+ sub1length 1) sub2length)
                    (mes (cdr list) sublist1 (+ sublist2 (car list)) sub1length (+ sub2length 1)))
                 (mes (cdr list) (+ sublist1 (car list)) sublist2 (+ sub1length 1) sub2length))
                ((> (mes (cdr list) sublist1 (+ sublist2 (car list)) sub1length (+ sub2length 1))
                    (mes (cdr list) sublist1 sublist2 sub1length sub2length))
                 (mes (cdr list) sublist1 (+ sublist2 (car list)) sub1length (+ sub2length 1)))
                (else (mes (cdr list) sublist1 sublist2 sub1length sub2length))
             )  
     )
)

Since Functional languages cannot store intermittent results, like the Java solution can, we must make the function call that produced the maximum result the first time! We can actually rearrange the Java solution to be similar to the scheme solution by removing the variables that stored the recursive results. The modified Java version would look like the following

x
private static int maxEqualSublists(Node node, int s1, int s2, int sl1, int sl2) {
        if(node == null) {
            return s1 == s2 && sl1 == sl2 ? sl1 : 0;
        }
        if(maxEqualSublists(node.next, s1 + node.data, s2, sl1 + 1, sl2) 
           > maxEqualSublists(node.next, s1, s2 + node.data, sl1, sl2 + 1)) {
            return maxEqualSublists(node.next, s1 + node.data, s2, sl1 + 1, sl2);
        } else if(maxEqualSublists(node.next, s1, s2 + node.data, sl1, sl2 + 1) 
                  > maxEqualSublists(node.next, s1, s2, sl1, sl2)) {
            return maxEqualSublists(node.next, s1, s2 + node.data, sl1, sl2 + 1);
        } else {
            return maxEqualSublists(node.next, s1, s2, sl1, sl2);
        }
    }

The BigO for this can be calculated by considering if we have to run the else statement (meaning there are not 2 sublists with the same sum and length) then that means 5 recursive calls were made for each element. That's a decision tree which expands 5 times the previous level of the tree meaning we get a result of $5^n$.