# Class Assignments

## Assignment 6: DiGraph Implementation in Java, and Topo Sort due Sunday, April 17, 11:55pm (hand in via Sakai)

Implement and test a directed graph in Java. Use it to compute a topological sort for an input graph. Details here.

You may use the Java Collections library for this assignment. You may want lists or queues, etc. Write your own graph and toposort code.

## Assignment 4: Splay Tree Implementation in Java due Friday, April 1, 11:55pm (hand in via Sakai)

Implement and test a Splay Tree (SPLT) in Java. Details here.

Do not use the Java Collections library for this assignment. You don't need lists or queues, etc. Write your own cell and tree code.

## Assignment 5: Binary Heap Implementation in Java due Monday, March 21, 11:55pm (hand in via Sakai)

Implement and test a Minimum Binary Heap (BHEAP) in Java. Details here.

Do not use the Java Collections library for this assignment. It is array based, so you don't need lists or queues, etc. Write your own heap code.

## Assignment 3: Basic BST Implementation in Java due Wed. Feb 17, by 11:59 pm (hand in via Sakai)

Implement and test a Binary Search Tree (BST) in Java. Details here.

## Assignment 2: Implementing QUEUE with LIST, LIST with Array, Links due Wed Feb. 03, by 11:59 pm (hand in via Sakai)

#### Overview

For this assignment use Java. Do not use the Java libraries for LIST and QUEUE. Write all your own code.

Create a Java program that uses the Bridge design pattern to build and exercise QUEUE of String with 2 different implementations (array, and linked cells). We are actually going to do this by

• first implementing LIST of String two ways (array, and linked cells)
• and then implementing QUEUE of String using the LISTs.

Use this ADT signature for QUEUE of String:
```   new:                  --> QUEUE
enq:   QUEUE x String --> QUEUE
deq:   QUEUE          --> QUEUE
front: QUEUE          --> String
size:  QUEUE          --> int
empty: QUEUE          --> boolean
```
This is the collection of methods the front end will offer. Note that they are "queueish" method names.

On the backend will be a general list, with these methods:

```   new                        --> LIST
ins:   LIST x String x int --> LIST
rem:   LIST x int          --> LIST
get:   LIST x int          --> String
size:  LIST                --> int
empty: LIST                --> boolean
```
Note that this has "list-ish" method names. Note also that you do not need to implement the "find" operation on LIST, as there is no corresponding capability in QUEUE. However, the "get" operation will be needed for implementing the "front" operation in QUEUE.

#### Functional Signatures vs. Java Classes

These functional signatures are like what we saw for the abstract ML axiom definitions. Now that we are going to build them in Java, you will have to "objectify" the methods... for example

```   new:    --> QUEUE
will become a constructor for class Queue, like
Queue( ) { ... }

and

enq: QUEUE x String --> QUEUE
will become a void method in class Queue like this
void enq ( String val ) { ... }
```

#### Bridge Considerations

Follow the stack example I gave for the bridge pattern, except (of course) you will do queues instead of stacks. The client side class will be QUEUE of String and that class will have the methods shown above for QUEUE. This client-side QUEUE object will also contain a reference to a backend implementation object (a LIST using either array or links). Calls to the QUEUE operations will be implemented by calling in some appropriate way operations in the implementation LIST object.

The backend implementation will have an interface that will define the common operations in LIST (shown above). You then create subclasses (implement the interface) for each of the LIST implementation methods: one for an array-based version of LIST and another for the linked cells version of LIST.

#### Bones of the Code

Build your program by filling in this rough outline. It basically is setting up the bridge, and making clear the distinction between the abstraction side (QUEUE) and the implementation side (LIST).

#### Main program

Your main program will be a test driver that will create one of each kind of QUEUE (a QUEUE with an array list implementation, and a QUEUE with a links list implementation). Do these steps:

1. Read the first of the command line arguments (a sequence of blank-separated strings, see this class example for getting it done); add (enq) that first string onto each QUEUE.
2. Print the size of each queue (separate lines)
3. Print the front element on each queue (separate lines)
4. do a deq operation on each queue
5. Print the size of each queue (separate lines)
Now read the rest of the command line arguments and add (enq) each string onto each QUEUE in the order they appear in the command line. Once the args are all processed, go into a loop that runs as many times as there are arguments less one; inside the loop do this:
1. print the front element on each QUEUE (separate lines)
2. do a deq on each QUEUE
3. print each QUEUE size (separate lines)

Here is an example. Let's assume the command line args are these:

```  greek  alpha  beta  gamma
```
The output should look like this:
```  1
1
greek
greek
0
0
alpha
alpha
2
2
beta
beta
1
1
gamma
gamma
0
0
```
The output will be symmetrical like this if both implementation methods are correctly providing the QUEUE behavior.

## Assignment 1: ADT Axiomatic Specifications due Thursday Jan. 28, by 11:59 pm (hand in via Sakai)

To get used to ML and practice how it can be used for abstract specs, do these (not to hand in):
• Download SML of NJ and get used to using basic ML.
• Try some of the ML-expressed ADT specs given in the class notes.
• Write the ADTs we studies in class (STACK of int, QUEUE of int) into ML as practice as well.

Now do these to hand in for credit:
1. Write in ML an axiomatic semantic definition of the basic LIST ADT we studied in class. This is really just translating the ADT specs we looked at in the powerpoint into ML code. Make sure you supply ML code that tests the ADT thoroughly to convince yourself (and me) that you have the definition correct.

2. Write in ML an axiomatic semantic definition for a Bounded Queue of E (BQUE). A BQUE is created with some finite size (>0) and when an enq operation is done, if the BQUE is full then nothing changes... the item is not added to the BQUE and no items in the BQUE are removed.
You can use the axioms we developed in class for a Bounded Stack (BST) as a model; obviously there will be some changes in the axioms, since a BQUE behaves differently from a BST. Use these signatures:
```     BQUE of E

new: pos       -> BQUE    (here, pos is int > 0)
enq: BQUE x E  -> BQUE
deq: BQUE      -> BQUE
front: BQUE    -> E
size: BQUE     -> nat     (naturals, int >=0 )
max: BQUE      -> pos
empty: BQUE    -> boolean
full: BQUE     -> boolean
```
As with the LIST definition, make sure to supply ML code that tests the specs to make sure they are correct.
```

```