# Assignment 1:  Tree Enumeration

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):

• C#, Go, Rust, or Swift
• Python or Ruby
• Prolog
454 students must also write in Scheme.  Your programs should generate (in some order) all rooted, ordered trees with n nodes.  Here “rooted” means for every pair of connected nodes we know which is the parent and which is the child; moreover, every node has a unique parent, except for the root, which has none.  “Ordered” means that if two of the subtrees under a given node are structurally distinct, it matters which one is to the left and which is to the right—so, for example, the following three trees are all distinct:

As it turns out, there are 42 different trees with 6 nodes (only three of which are shown above).  With 4 nodes there are only five trees:

These are most easily output in “parenthesized” form:

```((())())
(((())))
(()()())
((()()))
(()(()))
```
Examine those carefully: they correspond, in order, to the five trees above. Each pair of parentheses corresponds to a node; the nested parens are children; empty (innermost) parens are leaves.

Enumerating trees is a naturally recursive problem, for which there are several possible solutions.  The most obvious, perhaps, is to observe that you need one node for the root (assuming n ≠ 0).  You can then partition the remaining n−1 nodes among kn−1 subtrees (in many different ways), where the possible structures for each subtree are a recursive instance of the problem.  This works, but it’s tricky to get right.  (One advantage of this approach is that it lends itself to dynamic programming, which will generate solutions faster.)

A simpler approach is to trace out a left-to-right, depth-first traversal of the tree, keeping track at each step of the current depth and the number of remaining nodes.  At each step, you can choose to move down the tree (adding a left paren to the output, increasing the depth by one, and decreasing the number of remaining nodes by one) or move up the tree (adding a right paren to the output, decreasing the depth by one, and leaving the number of remaining nodes the same—except, of course, that you can’t move up if you’re at depth 0, and you can’t move down if you’re out of remaining nodes.  When you’re at depth 0 with no remaining nodes, you’ve found a possible tree.  The only tricky part is that when you have a real choice, you have to explore both options.

If you already knew all of the required 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 the languages already, so the unfamiliar ones will be the hardest.)  A hint: you can easily find toy programs in all these languages on the web.  For Ada and C# in particular, you might find it helpful to start with one of these toys:  it will already import appropriate libraries and contain examples of the control constructs, I/O calls, etc.  For what it’s worth, I wrote a solution in Scheme as part of designing the project; that solution is 16 lines long.

When run, your programs (in all languages other than Prolog) should read a single integer n from standard input, and then output the appropriate trees to standard output (in parenthesized form), 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.

## Division of labor, write-up, and turn-in

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 their own `README` file (no sharing of text on this allowed), and turn in the project separately (with all five or six 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.

Be sure to read the instructions on the grading page regarding the turn-in procedure and requirements.  You may also wish to consult the grading rubric on Blackboard.  To turn in your code, use the following procedure, which will be the same for all assignments this semester:  On a `csug` machine, 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`.  The script will package the contents of the directory (and any subdirectories) into a bundle and send it to the TAs for grading (so clean up any mess you might have in the directory first).  Be sure your write-up (`README` file) describes any features of your code that the TAs might not immediately notice.  In addition, for this assignment, your `README` file must compare and contrast the programming experience in the different languages you used (all five/six of them).  What was easy?  What was hard?  Are there noticeable differences in speed?  What do you like/dislike?

## Resources

We will be using the following language implementations.  The Go compiler is installed in `/u/cs254/bin`, which you should add to your `PATH` environment variable (ask a friend or one of the TAs if you don’t know how).  All the rest of the languages are in `/usr/bin` or `/usr/staff/bin`, both of which should already be on your `PATH` by default.

Compile your code with `gnatmake` (a wrapper for the GNU Ada translator).  It produces native executables.
C#
Compile your code with `mcs` (the Mono project C# compiler) and run with the `mono` JIT/run-time system.
Go
Run your code from the command line with `go`
Run your code under the `ghci` interpreter, or compile with `ghc` (the Glasgow Haskell Compiler) to produce native binaries.
Prolog
Run your code under the `swipl` interpreter.
Python
Run your code under the `python3` interpreter.
OCaml
Run your code under the `ocaml` interpreter, or compile with `ocamlc` to produce native binaries.
Ruby
Run your code under the `ruby` interpreter.
Rust
Compile your code with `rustc`.
Scheme (for 454 or extra credit)
Run your code at the command line with `plt-r5rs` or, under X, with the `drracket` GUI.  Be sure to configure the latter to use the R5RS language standard (it boots up expecting a vastly expanded language that will try to force you to use modules and other features you don’t want to have to learn at this point.)
Swift
Run your code under the `swift` interpreter, or compile with `swiftc`

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:

Principal web repository for everything Ada, including documentation, compilers, and tools.
An older repository, now going somewhat stale, but still with some excellent content.
The Ada 2012 Reference Manual.  (Note: this is a tough slog.  You’ll want to find a gentler tutorial—do a Google search.)
C#
Go
• go-lang.org/
Principal web site for Go.  Includes a nifty in-the-web-page interpreter with which to experiment.
Prolog
Python
• www.python.org/
Principal web site for Python, with documentation, tutorials, implementations, tools, and news from the user community.
OCaml
• ocaml.org/
Principal web site for OCaml, with documentation, tutorials, implementations, tools, etc.
Ruby
• ruby-lang.org/
Principal web site for Ruby, with documentation, tutorials, implementations, tools, etc.
Rust
• rust-lang.org/
Principal web site for Rust, with documentation, tutorials, implementations, tools, etc.
Scheme
• '(schemers . org)
Good general site for Scheme resources.
• racket-lang.org/
The Scheme implementation we’re using.  Actually supports a significantly larger extended language.  Includes documentation and downloads (if you want to install it on your personal machine).
• schemers.org/Documents/Standards/R5RS/
The Scheme R5 standard (the version you should use).  R7 is the latest standard, but you won’t be needing any of the newer features.
Swift

## Extra Credit suggestions

1. Try some other languages.  Java or C++ would be interesting, as would Smalltalk or Ruby.  If you’re not in 454, try Scheme.
2. Build a solution based on dynamic programming.  What is the asymptotic complexity of this solution and of its more naive alternative?
3. Give a closed form formula for T(n), the number of trees produced by your code for a given parameter n, and prove that it’s correct.
4. Display your trees graphically.  (Note that this is an extra option, and should be enabled by some special mechanism.  By default, your code must generate parenthesized form.)

## Trivia Assignment

Before end of day on Friday, September 9, each individual student (even if planning to work in a team) should complete the T1 trivia assignment found on Blackboard

## MAIN DUE DATE:

Tuesday September 20, by end of day US Eastern time; no extensions.
Last Change:  04 November 2022 /