This, the first graded assignment of the semester, asks you to solve a simple problem in each of five different programming languages (six if you’re in 454):
Each of your programs should take, as input, a sequence of n
integers, and should output a (not necessarily contiguous) subsequence
that is as long as possible, and in which the elements are monotonically
increasing left-to-right. So, for example, if your input is
19 3 11 7 15 12 4 12 8 16then one possible output would be
3 7 15 16There are several other possible outputs, all of length 4:
3 4 8 16 3 4 12 16 3 7 8 16 3 7 12 16 3 11 12 16 3 11 15 16This particular input sequence has no monotonically increasing subsequence of length 5. Note that the input numbers need not necessarily form a dense set, nor need they be unique.
There are many possible algorithms to solve this problem. The most obvious, perhaps, are doubly-recursive, and take O(2n) time. The fastest use dynamic programming, and run in O(n logn) time. 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.
If you already knew all the languages, you’d probably find your task easiest in Prolog and hardest in Ada, with the other languages ranging in between. (Of course you probably don’t know all the languages already, so the unfamiliar ones will be the hardest.) A hint: the companion site for 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 and C# programs should read a single
line from standard input, containing the entire input sequence.
They should print the output sequence (again on a single line) to
standard output.
For Prolog, please arrange for lis(seq, L)
, where
seq
is a Prolog list, to instantiate L
with an
appropriate sublist.
For Python, OCaml, and Scheme, you may write a function that takes a
list as input and returns a list as output; you can simply call this
function in the interpreter:
Python: lis([19, 3, 11, 7, 15, 12, 4, 12, 8, 16])
OCaml: lis([19; 3; 11; 7; 15; 12; 4; 12; 8; 16])
Scheme: (lis 19 3 11 7 15 12 4 12 8 16)
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 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.
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
, README.md
, 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?
Did you find iterators to be helpful?
We will be using the following language implementations.
The Ruby and Python interpreters; the Haskell Ocaml interpreters and
compilers; and the Ada, C#, Go, and Swift compilers
are found in /usr/bin
.
The Rust compiler and the Scheme and Prolog interpreters are found in
/usr/staff/bin
.
gnatmake
(a wrapper for the
GNU Ada translator). It produces native executables.
mcs
(the Mono project C#
compiler) and run with the mono
JIT/run-time system.
go
.
ghci
interpreter, or
compile with ghc
(the Glasgow Haskell Compiler) to
produce native binaries.
prolog
interpreter.
python3
interpreter.
ocaml
interpreter, or
compile with ocamlc
to produce native binaries.
ruby
interpreter.
rustc
.
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
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:
README
.
Before the end of the day on Friday, August 29, complete the T1 trivia assignment found on Blackboard.