Programming assignment 1 will give you time to practice functional programming and also give you a chance to become familiar with the Cool programming language. These skills will help prepare you for the remaining programming assignments.
For this assignment, you will be programming in Reason, a dialect of OCaml, and Cool. There are three parts to this assignment.
You may not work in a team of two people for this assignment.
You must create seven artifacts:
p1a.re, that contains your
implementations of the function interfaces required for P1a.
p1b.re, that contains your
implementations of the function interfaces required for P1b.
p1c.cl, that contains an
implementation of topological sort.
test-1.txt for P1c.
readme.txt describing your
design decisions. See the grading rubric. A few
paragraphs should suffice.
references.txt providing a
citation for each resource you used (excluding class notes, and
assigned readings) to complete the assignment. For example, if you
found a Stack Overflow answer helpful, provide a link to it.
Additionally, provide a brief description of how the resource helped
you.
Unless otherwise noted, you may use standard library functions.
Create a Reason file named p1a.re, and implement the
following function interfaces:
c_to_f
let c_to_f = (temp: float) : float => {
/* ... */
};
split_tip
let split_tip = ((price: float), (n: int)) : option(float) => {
/* ... */
};
price of a meal, and the number of ways
to split the check n, return Some
<float>, where float is the price with 20% tip split n
ways. If n is less than 1 or price is less
than 0, return None.
triangle_area
let triangle_area = ((s1: float), (s2: float), (s3: float)) : option(float) => {
/* ... */
};
Some <float> where float is the area of a triangle
with those sides. If the sides do not form a valid triangle, return
None.
repeat
let repeat = ((f: 'a => 'a), (arg: 'a), (n: int)) : 'a => {
/* ... */
};
f, an argument to the function
arg, and an integer n, return
f applied to arg n times.
list_length
let list_length = (l: list('a)) : int => {
/* ... */
};
Create a Reason file named p1b.re, and implement the
following function interfaces:
salutations
let salutations = (l: list(string)) : list(string) => {
/* ... */
};
dot_product
let dot_product = ((l1: list(int)), (l2: list(int))) : option(int) => {
/* ... */
};
Some
<int>, where int is the dot product of the two lists.
If the lists are not the same length, return None.
count
let count = ((l: list ('a)), (e: 'a)) : int => {
/* ... */
};
l, and an element,
e, return the number of occurrences of e
in l.
pre_order
let pre_order = (t: int_tree) : list(int) => {
/* ... */
};
t, return a list of the tree
items in the order that they are visited by a pre-order traversal.
int_tree_map
let int_tree_map = ((f: int => int), (t: int_tree)) : int_tree => {
/* ... */
};
f, and an integer tree,
t, return a new integer tree with f
applied to all nodes of t.
For this part of the assignment, one resource is provided:
Create a Cool program, p1c.cl. Your program must take in a
list of dependent tasks and either output a valid order in which to
perform them or the single word cycle. This problem is just
topological
sort not-so-cleverly disguised. Feel free to look up how to do
toposort on the internet and cite your references (but remember that you
must turn in your own work; you may not copy someone else's code and
claim it as your own).
Your program will accept a number of lines of textual input (via standard input). There are no command-line arguments — you must always read from standard input. Do not open a named file. Instead, always read from 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.
The interpretation is that in order to learn C one must first read the C tutorial and that in order to do P1 one must first learn C.
If the task list contains a cycle of any size, your program should output exactly and only the word cycle.
Even if the task list contains a few non-cyclic parts, any single cycle
forces you to output only the word cycle.
Always output to standard output only. Do not write anything to stderr.
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.
The above task list is not valid input because the pair learn C/read the C tutorial appears twice. Program behavior if the task list contains a duplicate pair is undefined. You will not be tested on it.
Your program may not cause any other file I/O to be performed, such as creating a temporary file to keep track of some intermediate sorting results or writing to stderr (or even causing the interpreter to write a warning to stderr). You do not need any such temporary files or stderr-printing to solve this problem.
If there are multiple outstanding unconstrained tasks, your program should output them in ascending ASCII alphabetical order. That is, if you ever have two or more tasks, each of which has no remaining dependencies, output the one that comes first ASCII-alphabetically. (This constraint makes your program deterministic; for any given input there is only one correct output.)
Because r comes before u, your output should be:
To put it another way, consider this task list:
Which yields a dependency graph like this:
A D E | \ / B C
The proper ordering for this set of tasks is A B D E C. Note that B comes before D and E, even though B depends on A. This is because, once A is finished, B is free to go and it comes first alphabetically. You may want to consider this requirement when you pick your sorting algorithm. Given this requirement the answer A D E B C is incorrect and will receive no credit.
Documentation is your friend! Here are some external resources you might find helpful:
Recall that Reason is a dialect of OCaml. You are able to make use all of OCaml's standard library and pervasives as a result. While it is possible to implement all of the function interfaces on your own, you may find it easier to use library functions in some cases (check out the List module in particular).
When implementing code in Reason, make a particular effort to use local bindings to:
You will most likely need to define recursive helper functions. To improve the performance of your code, be sure to make your functions tail-recursive whenever possible.
Take a look at unsort-cool.cl. You could do worse than
using it as a starting point.
If you're having trouble writing anything reasonable in Cool, don't forget to look at the other example Cool programs.
Building and maintaining an explicit graph structure is probably overkill. That being said, I have written a solution that uses a graph structure.
Because you receive extra credit for a working Python implementation (see the Grading Rubric below), I recommend that you complete the task in Python first. That way you can be sure that you understand the toposort algorithm in a familiar language before you try it in an unfamiliar one. Once you have it working in Python, you translate that into Cool. The automated grading server will grade any Python implementation you submit, giving you useful feedback on algorithmic correctness. This "Python-first" approach ends up being mathematically optimal for most students.
If you are still stuck, you can post on Piazza or approach the professor.
You must turn in a tar.gz file containing these files:
references.txt: your file of citationsp1a.re (contains your answers for P1a) You must turn in a tar.gz file containing these files:
references.txt: your file of citationsp1b.re (contains your answers for P1b) You must turn in a tar.gz file containing these files:
readme.txt: your README file references.txt: your file of citationstest-1.txt: a valid novel task list (it may or may not contain a cycle — your choice) p1c.cl (contains your program for P1c) p1c.py for extra credit.
Look for a separate submission page on SLUGS
team.txt: a file listing only the SLU
email IDs of both team members (see below).
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. What library functions did you use?
How did you store the (implicit) graph in P1c? What was the biggest
challenge of using Reason? Cool? One or two English paragraphs should
suffice. Spelling, grammar, capitalization and punctuation all count.
Note, you can use the CS-364 Makefile to generate a
submission archive:
make fullsubmit
The Makefile is available on Sakai and here.
Be sure to update the IDENTIFIER and EXECUTABLE
variables appropriately.
You may not work in pairs for parts A and B of this assignment.
You must complete part C of this assignment in a team of two. Teamwork imposes burdens of communication and coordination, but has the benefits of more thoughtful designs and cleaner programs. Team programming is also the norm in the professional world.
Students on a team are expected to participate equally in the effort and to be thoroughly familiar with all aspects of the joint work. Both members bear full responsibility for the completion of assignments. Partners turn in one solution for each programming assignment; each member receives the same grade for the assignment. If a partnership is not going well, the instructor will help to negotiate new partnerships. Teams may not be dissolved in the middle of an assignment.
If you are working in a team, both team members should
submit to SLUGS. The submission should include the file
team.txt, a two-line, two-word flat ASCII text file that
contains the email ID of both teammates. Don't include the @stlawu.edu bit. Example: If sjtime10 and
kaangs10 are working together, both kaangs10 and sjtime10 would submit
fullsubmit.tar.gz with a team.txt file that
contains:
kaangs10
sjtime10
Then, sjtime10 and kaangs10 will both receive the same
grade for that submission.
P1 Grading (out of 50 points):
test-1.txt file