UNC-CH COMP 410

Class Assignments




Assignment 6: (part 3) Graphs and Graph Algorithms
(due Tues. Dec. 1 by 11:59 pm)
hand in this code in the WorkBase

Use your directed graph class(es) to implement Dijkstra's shortest path algorithm. Details here.
Sample Java code showing file handling.
Sample data file "p3graphData.txt" in proper format.


Assignment 6: (part 2) Graphs and Graph Algorithms
(due Tues. Nov. 17 by 11:59 pm)
hand in this code in the WorkBase

Use your directed graph to compute a topological sort Details here.
Sample Java code showing file handling.
Sample data file "p2graphData.txt" in proper format.

Assignment 6: (part 1) Graphs and Graph Algorithms
(due Tues. Nov. 10 by 11:59 pm)
hand in this code in the WorkBase

Build and exercise a directed graph Details here.

Assignment 5: Binary Heap
(due Wed. Oct. 14 by 11:59 am, before Fall break)
hand in this code in the WorkBase

Build and exercise a binary heap Details here.

Assignment 4: (part 3) BST vs. SPLT Comparison
(due Tues. Oct. 6, by 9:29 am, class time)
hand in this code in the WorkBase

Comparative Analysis of BST vs. SPLT Details here.

Assignment 4: (part 2) Splay Tree Implementation in Java
(due Tues. Sept. 29, by 9:29 am, class time)
hand in this code in the WorkBase

Implement and test a Splay Tree in Java. Details here.

Assignment 4: (part 1) Basic BST Implementation in Java
(due Thurs. Sept. 24, by 9:29 am, class time)
hand in this code in the WorkBase

Implement and test a BST in Java. Details here.



Assignment 3: Sorted LIST
(due Tues. Sept. 22, by 9:29 am, class time)
hand in these specs in the WorkBase

Write an axiomatic specification for the ADT Sorted LIST of strings (call it SLIST). Express it in ML, and use the Guttag method for generating the axioms. For SLIST use this signature: 

  new:               --> SLIST
  add:   LIST x elt  --> SLIST    assume input list is sorted, and
                                  make sure return LIST is also
  rem:   LIST x int  --> SLIST    remove element in position i
  get:   LIST x int  --> elt      return the element in position i
  find:  LIST x elt  --> int      return position containing elt
  empty: LIST        --> boolean  
  size:  LIST        --> int
These operations are the "public" interface of the ADT. It is ok, if you need to do so, to write some "internal" operations that assist you in implementing the public operations. Internal operations are not visible to be called by code using the SLIST ADT.

Make sure, as you did in Assignment 1, to include in your ML code test cases that will demonstrate the working of your ADT.



Assignment 2: Bridge Pattern Implementation of QUEUE
(due Tues. Sept. 14, by 9:29 am, class time)
hand in these specs in the WorkBase

For this assignment use Java. Create a program that uses the Bridge design pattern to build and exercise QUEUE of real with 2 different implementations. Use this ADT signature: 

   new:                 --> QUEUE
   enq:   QUEUE x real  --> QUEUE
   deq:   QUEUE         --> QUEUE
   front: QUEUE         --> real
   size:  QUEUE         --> int
   empty: QUEUE         --> boolean
This is the set of methods the front end will offer. On the backend will be multiple implementations to make happen the actions called for on the frontend.

Backend implementations:

Your main program will be a driver that will create one of each kind of QUEUE. Then exercise each stack with the same data and sequences of operations to show that each implementation behaves the same.

If you wish to get started on this now, you can build a class that implements QUEUE using an array. Then build the classes needed to implement QUEUE using linked cells.



Assignment 1: ADT Axiomatic Specifications
(due Tues. Sept. 1, by 9:30 am, classtime)
I will give instructions later on how to hand in these specs

  1. Download SML of NJ and get used to using basic ML.
    Try some of the ML-expressed ADT specs given in the class notes.


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


  3. 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
     back: 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.