CMPU-145, Spring 2013
Asmt. 1 Instructions

DUE:  Monday, Feb. 11 @ 1:30 p.m.


Begin by creating an asmt1 directory in your own CS account.  Then
download the "asmt-helper.txt" and "asmt1-template.txt" files from the
course web page.  Next, open up the "asmt-1-template.txt" file in
DrScheme.  Insert your NAME in the appropriate places; save the file,
giving it a reasonable name (e.g., "myname-asmt1-defns.txt"); and then
click the Run button.  Make sure that the results look good before
proceeding.

The template file shows how to layout programming assignments for this
class.  Notice the use of the HEADER and PROBLEM functions that are
defined in the "asmt-helper.txt" file.  Note also that the expression,
(load "asmt-helper.txt") must appear in your file before you use these
functions.  The helper file also defines the TESTER function that you
have already used in lab.  You should use the TESTER function to
thoroughly test the functions you define for this assignment.

PROBLEM 1.

  Define a function, called DISJOINT?, that takes two lists as its
  inputs.  It should return #t if those lists are disjoint (i.e., if
  they do not have any elements in common). 

  ==> Notice the "contract" that is included in the template file.
      It shows the name of the function, describes each input,
      and describes the output.  You should always include a CONTRACT
      for every function you define for any assignment.

  Here are a couple of examples:

    > (disjoint? '(a b c) '(d e f g))
    #t
    > (disjoint? '(a b c) '(d e b f g))
    #f

  ==> One way to define this function is to compute the intersection
      of the two lists and then check whether it is empty.  However,
      that is not very efficient; so please don't do that.  Instead,
      you should walk through the first list.  For each item in the
      first list, check whether it is an element of the second list.
      If you ever discover that an item in the first list is also a
      member of the second list, then you should immediately stop
      computing and return #f. 


PROBLEM 2.

  Define a function, called POWER-SET, that takes a list representing
  a set as its only input.  It should return a list-of-lists representing
  the power-set of the input list, as illustrated below.

    > (power-set '(a b c))
    (() (c) (b) (b c) (a) (a c) (a b) (a b c))

  Notice how the built-in LENGTH function can be used to help with testing:

    > (length (power-set '(1 2 3 4 5 6 7 8 9 10)))
    1024

  Once again, notice the CONTRACT that has been provided for you in
  the template file.  In the future, you will be responsible for
  inserting appropriate contracts for your functions.

  Recall from class how one can approach the power-set computation:

     Example:   LISTY = (1 2 3)

                   FIRST element = 1

                   REST of listy = (2 3)

                   Recursive Function call generates the
                   power-set of the rest of the list, namely:

                        (() (2) (3) (2 3))

                   Then we "somehow" create another list that
                   is pretty much like this one except that each
                   sub-list has a 1 consed onto it:

                        ((1) (1 2) (1 3) (1 2 3))

                   Then we concatenate these two lists together to
		   yield the desired result:

                        (() (2) (3) (2 3) (1) (1 2) (1 3) (1 2 3))

     Note:  The order of the subsets doesn't matter.

     Hints:  Use a LET* to generate a sequence of helpful preliminary
             results.

             Carefully consider CONS, LIST and APPEND.
             Which do you need for what?

             Look at the solutions to Lab1.



===============================================

When you are convinced that your functions are working properly
and have included enough TESTER expressions to convice ME that
they are working properly...

   Save your definitions file.

   Use the "Save Other"/"Save Interactions as Text" menu command to
   save your interactions.

   Create a new directory called something like  myName-asmt1-submit-dir
   using the following command:

        mkdir myName-asmt1-submit-dir

   Copy the three files needed for this assignment into that directory:

     cp  my-defns.txt  my-inters.txt  asmt-helper.txt  myName-asmt1-submit-dir

   Submit electronically using the submit145 command:

     submit145 asmt1 myName-asmt1-submit-dir

   Then print out your defns and inters files:

     enscript -2jr my-defns.txt
  
     enscript -2jr my-inters.txt

   ==> STAPLE the pages with the defns file on top!

   Turn in your printouts to me 
     (or put them in the box outside my office door)!

-----------------

 Congrats.  You're done!