This, the first graded assignment of the semester asks you to solve a simple problem in each of five programming languages (six if you’re in 454): Ada 95, C#, Python, Prolog, and Haskell (454 students add Scheme). Your programs should generate (in some order) all structurally distinct full binary trees with n leaves. A binary tree is considered full (a.k.a. proper) if all internal (non-leaf) nodes have exactly two children. (Do not confuse this with a complete binary tree, in which all leaves are at the same depth.) 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 full binary trees with 4 leaves each:
These are most easily output in “dotted parenthesized form”:
(((..).).)
((.(..)).)
((..)(..))
(.((..).))
(.(.(..)))
You can think of the parenthesized expressions as being generated by the following grammar:
E →a tree can be empty E → Tor non-empty— T → .i.e., a single leaf T → (T T)or an internal node with left & right children
Finding trees is a naturally recursive problem.
The most efficient solutions employ dynamic programming, which
you may recall from a data structures course.
454 students are required to use the dynamic programming solution for at
least one of their six programs; 254 students may do so for extra credit.
Simpler though less efficient 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.
Prolog’s search mechanism can be used to create the equivalent of
iterators, and yields a very elegant solution.
Haskell provides enough machinery to build true iterators on top of the
core language; you can find them in add-on packages.
Ada has no special iterator support; for this you’ll have to
work with lists (or conceivably tasks).
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 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).
For Prolog, please arrange for trees(n, L)
to produce successive trees (values for L) in response
to a semicolon prompt.
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.
We will be using the following language implementations:
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.
gmcs (the Mono project C#
compiler) and run with the mono JIT/run-time system.
Both are located in /u/cs254/bin.
swipl interpreter.
It’s in /bin.
python interpreter. It’s
in /usr/bin.
ghci interpreter, or
compile with ghc (the Glasgow Haskell Compiler) to
produce native binaries. Both implementations are located in
/bin.
mzscheme or, under X, with the drscheme GUI.
Both are located in /u/cs254/bin.
You are welcome to work with 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 Thursday, September 6, send e-mail
to cs254 containing answers to the following
questions:
"hello,
world" to standard output in C#? In Ada?
