The five languages are Ruby, OCaml, Python, C and Cool. You will use Ruby, OCaml and Python for PA2 through PA5 (you must use each one at least once; you may use your favorite one twice). In PA2 through PA5 you will write an interpreter for Cool, so it is important that you understand how Cool works now. The C (not C++) implementation is so that you can gain a better appreciation for time-saving features of higher-level languages (e.g., automatic memory management, first-class higher-order functions, object-oriented programming). No assignment in this class after PA1 will use C.
You can find tutorials, manuals and other resources for these languages on the main project webpage.
Your program will accept a number of lines of textual input (via standard input). That text input will contain a non-zero but even number of lines. Every two lines represent a pair of tasks. The first line gives the name of a task, the second line gives the name of a task that it depends on. This text input is also called the task list.
The task list will contain only standard ASCII characters (no UTF/8 Unicode or special accents). The goal is to test programming and program language concepts, not your internationalization abilities.
Each task name starts at the beginning of the line and extends all the way up to (but not including) the end of that line. So the newline or carriage return characters \r or \n are not part of the task name. Each task name is at most 60 characters long. (This limit is to make the C implementation easier; if you can support longer strings natively, feel free to do so.)
Example task list:
learn C read the C tutorial do PA1 learn C
read the C tutorial learn C do PA1
get a job have experience have experience work on a job work on a job get a job
There is no fixed limit on the number of lines in the task list (although it is not zero and it is even).
Two tasks with the same name are really just the same task. Use standard string equality.
Duplicated pairs of tasks are not allowed. For example:
learn C read the C tutorial do PA1 learn C learn C read the C tutorial
Your program may not perform any other file I/O, such as creating a temporary file to keep track of some intermediate sorting results. You do not need to create any such temporary files to solve this problem.
learn C understand C pointers learn C read the C tutorial do PA1 learn C
read the C tutorial understand C pointers learn C do PA1
B A C D C E
A D E | \ / B C
Take a look at the files in pa1-hint.zip. You could do worse than using them as starting points.
If you're having trouble writing anything reasonable in Cool, don't forget to look at the example Cool programs that are distributed near the interpreter.
Building and maintaining explicit graph structure is probably overkill.
Since you do not know the number of tasks in advance you will need some sort of dynamic memory allocation.
I recommend solving the problem in the Python, Ruby or OCaml first (depending on where you are most comfortable) and then just translating your solution into the others. Translating into Cool and C will not be as easy, however.
Use this as an opportunity to see what you like about various languages. What do you think of Python's enforced tabbing? How about ML's abysmal error reporting? Ruby's below-par execution speed? C's general hideousness?
For bonus brownie points, try to make your OCaml, Ruby and Python implementations as functional as possible (e.g., eschew side effects).
Don't know which language to pick for PA0? Look at the pa1-hint.zip file and pick a language that looks like it would be easy to debug. Your first attempt (for PA0) will probably contain the most algorithmic errors. After that it's more of a matter of translating it into other languages.
The testcase.list file should contain a valid task list (it may or may not contain a cycle -- your choice). It will be used as one of the test cases to grade all of the submissions, so you have the chance to be certain of getting at least one right.
The readme.txt file should be a plain ASCII text file (not a Word file, not an RTF file, not an HTML file) describing your design decisions. Which language did you start with? How did you store the (implicit) graph? Which language was the hardest? One or two English paragraphs should suffice. Spelling, grammar, capitalization and punctuation count.
Submit your zip file to Toolkit.
For the one-week PA0 checkpoint, you must have at least two of the implementations done. This separates the project into two phases: (0) Can I write this program at all? and (1) Can I write this program in three other languages?
For PA0 you must turn in two source files. Use the following names:
We will perform the autograding on some unspecified test system. It is likely to be Solaris/UltraSPARC, Cygwin/x86 or Linux/x86. However, your submissions must officialy be platform-independent (not that hard with a scripting language). You cannot depend on running on any particular platform.
There is more to your grade than autograder results. See the Programming Assignment page for a point breakdown.