This, the first graded assignment of the semester asks you to solve a simple problem in each of five programming languages: Java, C++, Ada 95, C#, and Python. The problem is Exercise 6.18 in the textbook:
Construct a program that outputs (in some order) all structurally distinct binary trees of n nodes. Two trees are considered structurally distinct if they have different numbers of nodes or if their left or right subtrees are structurally distinct. There are, for example, 5 structurally distinct trees of 3 nodes:
![]()
These are most easily output in “dotted parenthesized form”:
(((.).).) ((.(.)).) ((.).(.)) (.((.).)) (.(.(.)))
You can think of the parenthesized expressions as being generated by the following grammar:
T →a tree can be empty T → (.)or a single node T → (T.T)or a node with left & right children
Finding trees is a naturally recursive problem. 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.
When run, your programs should read a single integer n from standard input, and then output the appropriate trees to standard output (as dotted lists, one per line, in arbitrary order).
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.
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 run the script
~cs254/bin/TURN_IN.
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.
We will be using the following language implementations:
javac (Sun’s Java 5 compiler)
and run with the java interpreter. Both are located in
/usr/staff/bin on the CSUG machines.
g++ (the GNU C++ translator).
It’s in /usr/bin. It produces native executables.
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.
mcs (the Mono project C#
compiler) and run with the mono JIT/run-time system.
Both are located in /u/cs254/bin.
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:
Before the beginning of class on Tuesday, September 9, send e-mail
to cs254 containing answers to the following
questions:
"hello,
world" to standard output in C#? In Ada?
