## Computer Science 510 |
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.

- 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.
- Datatypes
- 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.

`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? - if
- 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.)* - 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

functionalimplementation, NOT animperativeimplementation. 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.)