Computer Science 510 Programming Languages Problem Set 1

Fall 2003 Due Sept 22

Rules for collaboration: You may discuss the problem sets with other students to increase your understanding of the material. However, what you write down and turn in should be your own work.  Some problems may be similar to problems from previous years.  Do not use previous years solutions to help you solve these problems.

All problem sets are due at 11:00 a.m. in class on the due date.

1. If you don't know SML, locate a reference manual on the web, from the library or the campus store.  Make sure you have access to an SML compiler.  See the course homepage for more information.
2. Datatypes
   Write ML datatypes that implements binary digits (bit) and binary numbers (bnum) as described below.

   • a binary digit is either On or Off. (datatype bit = ....)
   • a binary number is either a binary digit followed by another binary number, or it is Zero (datatype bnum = ....)
   Implement ML functions 

   • eval_bit : bit -> int 
   • eval_bnum : bnum -> int 
   • add  : bnum -> bnum -> bnum

   The first two functions take a binary digit and binary number and return the corresponding integer.  The third function takes two binary numbers and computes the binary number that represents their sum. 

    

3. Implement quicksort in ML. That is, write the following functions

   get_pivot: int list -> int * int list
   partition: int * int list -> int list * int list
   sort: int list -> int list
   

   such that
   • if (i,L')=get_pivot(L) then i is some element of the list L and L' is a list of all the other elements of L;
   • if (L1,L2)=partition(i,L) then L1 @ L2 is a permutation of the list L, and all the elements of L1 are less than or equal to i, and all the elements of L2 are greater than i;
   • and if L' = sort(L) then L' is a permutation of L and the elements of L' are in nondecreasing order.
   Experiment with at least two implementations of get_pivot: for example, get the first element of the list, or get the middle element. Have your partition function print a "." whenever it does a comparison. How is the efficiency of the quicksort algorithm on an already-sorted input differ with your different get_pivot functions?

 

4. Modify your sort function (and the other two as necessary) so that the comparison function can be passed as an argument:

   sort: ('a * 'a -> bool) -> 'a list -> 'a list
   

   Demonstrate the polymorphism by sorting a list of strings into reverse alphabetical order; and by sorting a list of integers so that all the odd numbers come before all the even numbers (with the order otherwise arbitrary).

   As part of your demonstration, show the ML declarations that execute sort on these two lists, and the transcript of your ML session.

   (If you were not able to get your quicksort working, you may implement any polymorphic sorting algorithm (insertion sort, bubble sort, etc.) that takes a sort function as an argument.)

    

5. Consider the following datatype declaration for an integer-storing red-black tree:

datatype color = R | B

datatype tree = Empty | T of color * tree * int * tree

Red-black trees also maintain the following 3 invariants

• In any node T (c,t1,x,t2), x is greater than any element in t1 and any element in t2 is greater than x.
• No red node has a red parent.
• Every path from the root to an empty node contains the same number of black nodes.

Implement the following operations on red-black trees, making sure to maintain the three invariants above:

empty : tree                    (* an empty tree *)

member : int -> tree -> bool    (* member x t is true if x is in t *)

insert : int -> tree -> tree    (* insert x t returns a new tree

                                     containing the elements of t union {x} *)

You may use any algorithms textbook you choose to help you implement these functions (or you can try to figure it out yourself).  However, you must hand in a functional implementation, NOT an imperative implementation.  In other words, you are not allowed to use references in your solution.

Hint:  standard algorithms textbooks use imperative languages like C to solve this problem, and, in general, present TERRIBLY coded algorithms.

Hint:  the key to insertion is in the definition of an auxiliary function that rebalances trees.  There is a solution in which the core of the balance function can be written in approximately five lines of code (use pattern matching!).

 This question will be graded both on correctness and on elegance of the final solution.  (Of course, both correctness and elegance are important in all of the answers that you give in this course.)