Implement and test a directed graph in Java. For building the digraph data structure, details are here.
For this problem, the digraph you work on will have weighted edges, and it may have cycles. Now you will use your digraph to solve the single source shortest path problem using Dijkstra's algorithm.
Details of Dijkstra are here.
Implement and test a splay tree in Java.
Assignment details
here.
This assignment is mainly a modification of the BST Assignment 2.
It will contain a working BST implementation, and it will be modified to splay
at the right times. This brings a form of balance to the BST.
Correct BST implementation:
You may build your splay implementation into the BST code that
you wrote for a previous assignment. You are essentially creating a
splay method and deciding where to put it into other method calls, and
deciding which node to splay on in each situation.
If you are not happy with your BST code, or have many problems to fix in it
to get it working well, you may wish to start with the correct BST implementation
we will post in the assignment info on Sakai.
There is no penalty for using this code.
Oracle tests: About midway in the development time, the JAR
file for the oracle tests
and the informal test explanations will be released to you via Sakai.
Do not use the Java Collections library for this assignment.
Write all your own code (except that you may use the correct BST code
that we have given you in Sakai).
Implement and test a priority queue using a minimum binary heap in Java.
Assignment details
here.
About midway in the development time, the JAR file for the oracle tests
and the informal test explanations will be released to you via Sakai.
Do not use the Java Collections library for this assignment.
Write all your own code.
Implement and test a Binary Search Tree in Java.
Use linked cells (not arrays).
Assignment details
here.
As befoer, about midway in the assignment period we will
post a test oracle and explanation on Sakai.
This is to help you, but do your own testing and be thorough.
Do not use the Java Collections library for this assignment.
Write your own linked cell and tree code.
object delegation
... notes on doing this program here.
Implement and test a LIST in Java.
Use linked cells (not arrays).
Do not use the Java Collections library for this assignment.
Write your own linked cell and list code.
Assignment details
are here.
By about mid-point in the assignment time frame,
we will post a jar file on Sakai with tests in it; we will
also post an English description of what those tests
are requiring your ADT implementation to do.
Before that point, you should be creating your own tests to thoroughly
exercise your code.
When you receive the oracle tests, you should already be convinced that your code
works properly. Applying the oracle tests will conform this (hopefully) and also
confirm for you that your code is in the proper format to feed to the grader.
Use the english specs in the Assignment writeup to decide what behavior you need to implement
and what each methods should do, especially with the special data cases.
the sentinel
... notes on doing this program here.
Especially if you are dealing with some new Java concept or technique...
Ever been to a museum and seen large, beautiful canvases by Renoir, Van Gogh, Chagal, Wyeth, etc.?
Ever been to a museum and seen the sketch books of Renoir, Van Gogh, Chagal, Wyeth, etc.?
These artists did not just sit down at a blank canvas, pull out a brush and paint out a finished work.
They all had to try different things... how to make a shadow real, how to get a collections of colors to
look right together, how to make a face look sad or expectant, how to arrange the composition for
best balance and harmony, etc...
The sketch book is where these experiments and studies are done. They try different
techniques and small works until they understand what needs to be done on the main
canvas.
You should do this too. Code small stuff. See how stuff works. See how to make
Java do your bidding. Then transfer your new knowledge into the real thing.
In this case, many of you will not have done "pointer" based coding much before,
or at all. You may not understand what it means to have an object contain
an object of its own class inside it as a field.
So make a small program to try this... experiment with it... see how to address the
objects and fields in Java. See what happens when you try various things like
printing the fields, assigning to the fields... moving objects from
"inside" one object (linked to that object) to being assigned to inside another
object. See that the objects still exist but are simple "linked together"
in different orders or patterns.
Then you will be ready to think about more complicated arrangements, like
a doubly linked list of cells.
This assignment is intended to show you how to use our test oracle with Eclipse.
The test oracle for each assignment is intended to assist you in thoroughly testing your code. It is not intended to be a complete set of tests. You can think of the oracle as a partial set of test cases that will help you make sure your code is written to the correct structure and format. The goal of giving you the oracle is so you can know that your code will be gradable by our software.
We want you to write your code, and also give good thought to how to completely test it (how to uncover the errors that might be in your work). You should test your code with your own tests first, and when you are convinced you have done a thorough job you can use the supplied test oracle to check.
The oracle is not a substitute for doing your own thinking about how your code should be exercised. We publish an english version of the tests to help you see what behavior we are looking for.
Details here.