Programming Assignment #2
ML Assignment

Due by 3:30 PM on April 10, 2007 (Sunday night/Monday morning).



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


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 file for each Part 1 and 2, and your write-up.

Tips
 • Use Professor Stott's 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 compiled/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, and the output. Collaboration is encouraged, but you cannot share source code. 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 --