Assignment Submission

Homework 3 must be submitted electronically. Your submission must include 2 files:

1.) The source code must be inR5RS dialect. Any other scheme or lisp dialect will be an automatic 0. You should have a single .rkt file that contains your function.

2.) 1 – 2 page description of your algorithm and its complexity as an ACII text document, MS Word document, or a PDF file. Since the program you must write is short, the description of the algorithm and complexity analysis carry significant weight on your grade.

Pack all your files in a single zip file. Use the following naming convention. If your name is John Smith, then your file name must be jsmith.zip. Zip files which are not properly named or packed will receive 0 points.

Problem Description

Write a single function three-part-dif? (question mark included) that takes a list of non-zero positive integers and determines if there exists three non-empty sublists such that the difference between the sums of two sublists is equal to the sum of the third sublist. Furthermore, all numbers must be used at most once, and each individual number is unique and may only exist within one of the sublists at any given time. So, two numbers that are duplicates in the original list are mutually exclusive from each other and each may exist within a different sublist but a single individual number may not be duplicated amongst different sublists at a given instance.

You must return #t if there exists such a 3-partition of the list else return #f. (#t and #f is true and false respectively in R5RS).

Only return a single #t even if there are more than one partitioning which results in the above. Same with no such partition, only return a single #f.

For the function, the only required parameter is the single list. It must be the first parameter to the function. You may then add as many additional auxiliary parameters that are scalar as you would like. Scalar parameters hold a single value and are not collections such as other lists. Auxiliary parameters are meant to help with the solving of the problem. For example, if the list is ‘(1 2 3) and you decide to use two additional auxiliary parameters then your function will look like the following

(define three-part-dif? (lambda (lst aux1 aux2) ;rest of code )

And will be called like this

(three-part-dif? ‘(1 2 3) 0 0)

If you decide to have three additional auxiliary parameters, then your function will look like the following

(define three-part-dif? (lambda (lst aux1 aux2 aux3) ;rest of code )

And will be called like this

(three-part-dif? ‘(1 2 3) 0 0 0)

The main part here is that the list parameter should be the first parameter and your auxiliary parameters should follow.

Finally, you are not reading from a file. The program will be ran in Dr. Racket and your function will simply be called within the interactive window with the list to be tested as well as the auxiliary parameters.

Tests

Here are some test calls

‘ (3 1 2) should return #t. There are two ways to get 3 sublists that follow the rule.

{1} {3} and {2}. Since the sum of {1} is 1 and the sum of {3} is 3 then 3 – 1 = 2 which is the sum of {2}.

You can also get #t by {2} {3} and {1} where 3 – 2 = 1.

‘ (100 25 5 10 25 50 10 25) should return #t. The three sublists are

{100, 25} – {25, 10} = {5, 10, 25, 50} or 125 – 35 = 90.

‘ (64 68 22 42 92 28 23 47 87 100) should return #f.

‘ (1 95 39 28 41 99 49 79 13 80) should return #t.

‘ (75 1 65 17 60 13 39 77 19 62 50 36 65 74 76) should return #f.

‘ (107 136 46 84 105 186 158 7 125 186 129 66 132 24 149) should return #t.

‘(169 193 3 141 192 163 17 98 115 113 83 55 147 36 38) should return #f.

NOTE: If you copy and paste from this document the list then you might run into a formatting issue with the single quote. Sometimes, Word or Blackboard will change certain characters to a Unicode equivalent which is not the single quote on a standard US-QWERTY keyboard. You may need to change the single quote to the ASCII version.

Code

Your function should have the following signature

(define three-part-dif? (lambda ()

(cond

…

)))

In other words, your function must take as its first parameter the list of integers followed by as many auxiliary scalar parameters of your choice which will be initialized to 0. You must utilize cond and may only have 1 cond statement.

The information between the < and > is not R5RS but pseudocode that explains what is expected so please don’t try to write in your actual code.

Restrictions

Inside your function you are only allowed the following scheme constructs:

null?

car

cdr

else

cond

+

–

abs (for the absolute value)

=

or

if

and

or

three-part-dif?

user defined names (for the names of your parameters)

integer literals

parentheses

If you have a question about using a certain construct, then make sure to ask first. If you do not ask and turn in a solution which using something not in the list, then you will be penalized.

You cannot define or call any other function except for what is listed above. This means you must write a single function to solve the problem.

NOTE: Make sure before you submit to remove any debug code. If you leave any code that writes to stdout or have extra lists outside the main list, it will be counted against your score.