Assignment 1:  Comparing Languages
(Prime Partitions)

Many but not all positive integers can be written as a sum of distinct primes.  The number 12, for example, can be written as either 5 + 7 or 2 + 3 + 7.  The numbers 4 and 6, on the other hand, have no partition into unique primes, and the number 9 has only one:  2 + 7.  This, the first graded assignment of the semester, asks you to enumerate all the ways of partitioning a given number n into a sum of two or more distinct primes, a + b + ... + m and to do so in five different programming languages:  Java, C++, Ada 95, C#, and Python. 

When run, your programs should read an integer n from standard input, and then write the appropriate sums to standard output, in arbitrary order.  Given the input 20, for example, your programs might print

    2 + 7 + 11
    3 + 17
    7 + 13
You should print each partition only once.  Toward this end, you will probably find it easiest to write your programs in such a way that they print the addends in sorted order. 

The prime partition problem is naturally recursive.  The easiest and most elegant solutions employ iterators, which are abstractions used to drive a for loop.  We will study iterators in Section 6.5.3; you may want to read ahead.  In the terminology of that section, you’ll find that Python and C# have true iterators, Java and C++ have iterator objects, and Ada has no special iterator support.  If you already knew the languages, you’d probably find your task easiest in Python and C#, and hardest in Ada, with Java and C++ somewhere in the middle.  Of course you probably don’t know all five languages already, so that will be something of a hurdle. 

A hint:  If you program with iterators, you may find it useful to define

  1. An iterator primes(a, b) that generates all prime numbers between a and b, inclusive.

  2. An iterator prime_partitions(n, k) that generates all prime partitions of n using primes greater than k.
Given n, your program as a whole would call prime_partitions(n, 1).

Division of labor and writeup

As in all assignments this semester, you may work alone or in teams of two.  If you choose to work in pairs, one obvious division of labor is to split up the languages among you.  That’s ok, but I strongly encourage you to read each others’ solutions, to make sure you understand them. 

In addition to the usual requirements, your write-up must compare and contrast the programming experience in the different languages.  (This will of course be easier if you really understand what happened in all five.)  What was easy?  What was hard?  Are there noticable differences in speed?  What do you like/dislike?  Did you find iterators to be helpful? 

Be sure to follow all the rules on the Grading page.  As with all assignments, use the turn-in script:  ~cs254/bin/TURN_IN.  Put your write-up in a README.txt or README.pdf file in the directory in which you run the script.  Be sure to describe any features of your code that the TA might not immediately notice. 

Resources

We will be using the following language implementations: 

Java
Compile your code with javac (Sun’s Java 5 compiler) and run with the java interpreter.  Both are located in /usr/staff/bin on the CSUG machines. 
C++
Compile your code with g++ (the GNU C++ translator).  It’s in /usr/bin.  It produces native executables. 
Ada 95
Compile your code with gnatmake (a wrapper for the GNU Ada translator).  It’s in /u/cs254/bin, which you should add to your PATH environment variable (ask a friend or one of the TA if you don’t know how).  It produces native executables. 
C#
Compile your code with mcs (the Mono project C# compiler) and run with the mono JIT/run-time system.  Both are located in /u/cs254/bin
Python
Run your code under the python interpreter.  It’s in /usr/bin

You are welcome to do development using other language implementations and/or platforms, but you must ensure that your final versions compile and run correctly using the implementations listed above.  We will be testing using only these. 

I won’t be devoting lecture time to how to use these languages.  You’ll need to find on-line tutorials or other resources, and teach yourself.  Here are some decent starting points: 

Java
C++
Ada 95
C#
Python

Extra Credit suggestions

  1. Try some other languages.  A functional language (Scheme, Common Lisp, ML, Haskell) or logic language (Prolog) would be particularly interesting. 
  2. What can you say about the function P(n), the number of distict prime partitions of n?  Is there a closed form solution?  How does the function relate to other combinatorial problems, e.g. (non-prime) integer partition, set partition, and tree enumeration?  (A little number theory helps here, but you can learn a surprising amount by browsing obvious topics on Wikipedia.) 
  3. What about asymptotic complexity?  Is the most natural code efficient?  What is the best possible big-O value for this problem?

Trivia Assignment

Before the beginning of class on Tuesday, September 11, send e-mail to cs254 containing answers to the following questions: 

  1. Are you working along or in a team?  If a team, who is your partner? 
  2. How many unique prime partitions does 24 have?  What are they? 
  3. What is the version number of each of the language implementations we are using? 
  4. What is the syntax used to write the string "hello, world" to standard output in C#?  In Ada? 

MAIN DUE DATE: 

Monday September 17, at 11:59pm; no extensions. 
Last Change:  27 September 2007 / Michael Scott's email address