Assignment 1:  Combinations

This, the first graded assignment of the semester, asks you to solve a simple problem in each of five very different programming languages:  Ada 95, C#, Python, Prolog, and Scheme.  Specifically, you are to write a program that takes two values, k and n, and outputs all combinations of k numbers chosen from {1, 2, ..., n}. So if, for example, you specify the values 2 and 4, you should see (in some order)

    1 2
    1 3
    1 4
    2 3
    2 4
    3 4
You may print the members of each combination in ascending or descending order (your choice); but please don't otherwise scramble them.

Finding combinations is a naturally recursive problem (iterative solutions are also possible).  The easiest and most elegant solutions employ a recursive set of 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.  Prolog's search mechanism can be used to create the equivalent of iterators, and yields a very elegant solution (my version is ony 4 lines long).  Ada and Scheme have no special iterator support; for these you'll have to work with lists (or find some other solution—e.g., tasks in Ada).  For what it's worth, Java and C++ (which you can try for extra credit) have iterator objects, which are sort of half of what you want. 

If you already knew all five languages, you’d probably find your task easiest in Prolog and hardest in Ada, with the other three somewhere in the middle.  (Of course you probably don’t know all five languages already, so the unfamiliar ones will be the hardest.)  A hint: the CD that comes with the textbook contains working versions of all the nontrivial examples in the book.  For Ada and C# you might find it helpful to start with one of these:  it will already import appropriate libraries and contain examples of the control constructs, I/O calls, etc. 

When run, your Ada, C#, and Python programs should take k and n (in that order) as command-line arguments, and then write combinations, one per line, to standard output.  For Scheme, which runs in an interpreter, please arrange for (combinations k n) to return a list of combinations, each of which is a (nested) list.  For Prolog, please arrange for combinations(k, n, L) to produce successive combinations (values for L) in response to a semicolon prompt. 

Your programs should all run in time proportional to the length of the output.  Not all “obvious” programs will do so.  Behind this link, for example, is a Python program that produces the correct output, but takes time exponential in n, regardless of k.  In particular, it takes exponential time when k = n, even though the output is only one line long (try it for, say, k = n = 20).  (For what it's worth, my version of the better Python solution is actually a shorter program.) 

Division of labor and writeup

You may work alone on this project or in teams of two. If you split up the languages, whoever takes Ada should probably do two; the other person should do three.  However you divide the programming, each team member must write his or her own README file (no sharing of text on this allowed), and turn in the project separately (with all five programs, which will be the same as the partner's code).  This means, of course, that you'll need to really understand your partner's code. 

In addition to the usual requirements, your write-up must compare and contrast the programming experience in the different languages (all five of them).  What was easy?  What was hard?  Are there noticeable 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.  To turn in your code, use the following procedure, which will be the same for all assignments this semester:  Put your write-up in a README.txt or README.pdf file in the same directory as your code, and (while still in that directory) run the script ~cs254/bin/TURN_IN on a csug machine.  The script will package the contents of the directory (and any subdirectories) into a bundle and send it to the TA for grading (so clean up any mess you might have in the directory first).  Be sure your README file describes any features of your code that the TA might not immediately notice. 

Resources

We will be using the following language implementations: 

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 gmcs (the Mono project C# compiler) and run with the mono JIT/run-time system.  Both are located in /u/cs254/bin
Prolog
Run your code under the pl interpreter.  It's in /usr/bin.
Python
Run your code under the python interpreter.  It’s in /usr/bin
Scheme
Run your code at the command line with mzscheme or, under X, with the drscheme GUI.  Both are located in /u/cs254/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: 

Ada 95
C#
Prolog
Python
Scheme

Extra Credit suggestions

  1. Try some other languages.  Java or C++ (with iterator objects) would be interesting, as would ML, Haskell, or Ruby. 
  2. Determine the asymptotic (big-O) space requirements of your various programs.  Are some of them better than others? 

Trivia Assignment

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

  1. Are you working alone or in a team?  If a team, who is your partner? 
  2. How many combinations are there of 4 elements among 10? 
  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 14, at 11:59pm; no extensions. 
Last Change:  03 September 2009 / Michael Scott's email address