UNC-CH COMP 410

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

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):
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.