Programming Assignment #2
ML
Assignment
Due
by Noon on March 31, 2009.
Part 0: Download and Install ML
Before
you begin the assignment, you must install ML. The
version of ML that we will use for this assignment
is
Standard ML of New
Jersey.
You should be able to find a binary for your system
from
this page.
Once you download and decompress the file, add the
location of sml.exe to your path. Now you should
be able to run ML by simply typing "sml" from the
command prompt.
Please download and install ML, as soon as possible, to
avoid problems and stress closer to the due date.
Part
1: Simulating a Deterministic Finite Automaton (45
points)
In this
part, you will reimplement the DFA simulator, from Chapter
10 in the Scott's book, in ML. The original
code is written in Scheme and can be found on page 538 in
Figure 10.1. Your main function should be
named
simulate and take
as arguments the list structure containing the DFA and an
input list. The following is an example of a call to
simulate and the corresponding output:
simulate(
("q0",
[(("q0", 0), "q2"),
(("q0", 1), "q1"), (("q1", 0), "q3"), (("q1", 1), "q0"),
(("q2", 0), "q0"),
(("q2", 1), "q3"), (("q3", 0), "q1"), (("q3", 1), "q2")],
["q0"]),
[0, 1, 1, 0, 1]
);
=> val it = ["q0", "q2", "q3", "q2", "q0", "q1",
"reject"] : string list
Part
2: The Greedy Grocery Store Clerk (40
points)
A
grocery store clerk has a line forming in their check-out
aisle. The clerk is very slow and knows that people
will leave before the clerk can check-out every customer's
order. Therefore, since the clerk is greedy, the
customers are asked to reform the line in
decreasing
order of
their total purchases. The clerk can serve them in
this order to maximize total sales. Your job is to
write ML code to total each customer's purchase and sort
the line.
Assume you are given a list of customers and their
purchases in the following form:
[(customer_name1, [(num_items1,
cost_of_item1),(num_items2, cost_of_item2),...])
(customer_name2, [(num_items1, cost_of_item1),....])
...
(customer_name_n, [(num_items1, cost_of_item1),...])
]
The
interpretation is that customer_name1
has
num_items1
of the
first item at cost_of_item1
dollars
for each item. Your code should total the items in
the customer's cart. That is, the total amount in the
first customer's cart is:
(num_items1
* cost_of_item1) + (num_items2 * cost_of_item2) + ....
You
should call your function
grocery_store_line; the
function should take the customer-item list as an
argument.
Your sorting algorithm should be based on a quicksort
algorithm.
The following is an example of a call to grocery_store_line
and the corresponding output:
grocery_store_line [
("rebecca", [(3, 2.25), (10, 6.7), (2,
3.2)]),
("gene", [(8, 0.2), (3, 0.25), (15,
0.15)]),
("albert", [(1, 100.30)])
];
=>val it =
[("albert",100.3),("rebecca",80.15),("gene",4.6)] : (string
* real) list
Note the steps of the Quicksort algorithm (sorting least to greatest--the other way 'round is symmetrical):
1. If the list is empty or contains a single element it is sorted and no further action is required.
2. Otherwise, choose an element from the list to be the "pivot"
3. Create two sub-lists, one containing all elements less than the pivot and one containing all elements greater than the pivot.
4. Sort the two sub-lists recursively.
5. The sorted list is composed of a.) the sorted sub-list of elements less than the pivot, followed by b.) the pivot element itself, followed by c.) the sorted sub-list of elements greater than the pivot.
After we go over the algorithm in class, you should see me on office hours if you still have questions. I'll be happy to go over some examples with you.
Write-up
and Questions (15 Points):
Describe,
for both Parts 1 and 2, the functions you created to
complete the task. Briefly describe your reason for
the way you structure the solution for each part. In
addition, answer the following
questions:
1. What
is the type of the simulate function from Part 1?
2. What is the type of the grocery_store_line function from
Part 2?
3. In words, describe what changes you would need to make
to the simulate function to handle nondeterministic finite
automatons (NFAs). Your description can be
high-level.
What
to Hand-in
Send me an email with a zip file containing code files for each Part 1 and 2, and
your write-up. Title the email "COMP524 Program2" and call the attached zip file yourlastname.zip
Tips
• Use
Professor Stotts'
ML Notes;
•
Think recursively, and use ML's pattern matching
functionality to make things easy;
•
Understand the let construct,
and built-in functions such as map.
• To
convert from int to
real, use
the real() function
• You
need not type the while program at the interpreter each
time you want to run it. Simple create a text file with
your program in it... use whatever editor you like to write
the program. Let's say I have my program in a file called
prog.ml Then when I run the interpreter I type
this:
use
"prog.ml";
Grading:
Your assignment will be graded not only on the ability to
be correctly interpreted and produce the correct
output, but also on the correct and efficient use of
language constructs provided by ML such as
recursion,
pattern matching, anonymous
functions,
and lists.
For instance, you should attempt to only use the functional
language constructs. I will grade both the quality of
the source code, comments (on nearly every line for this assignment!), and the output. Collaboration is
not allowed on this assignment; you may discuss the ML language but not approaches (or code) for the assignment.
Also, you may not use outside resources such as the Internet, other then the online materials I have linked to here. See me during office hours if you need additional help.
The Honor Code applies
to this program. Please, read
http://www.cs.unc.edu/Admin/Courses/HonorCode.html
for more
details.
--
GOOD LUCK AND HAVE FUN --