UNC-CH COMP 410

Class Assignments

  Info For ALL:



Assignment 6: DIjkstra's Algorithm for single source shortest path (weighted)
due Monday, April 24, at 11:55pm
(hand in via Sakai)

Add a method to your digraph code. In this case, the digraph you work on will have weighted edges, and it may have cycles.

Details here.

You may use the Java Collections library for this assignment. You may want lists, queues, hashmaps, etc. Write your own graph code and Dijkstra's code.
You will need a priority queue.




Assignment 5: DiGraph Implementation in Java, and Topo Sort
due Friday, April 14, 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, stacks, queues, heap/priority-queues, etc.
Write your own graph and toposort code.




Assignment 4: SPLT Implementation in Java
due Friday, March 31, 11:55pm
(hand in via Sakai)

Implement and test a splay tree in Java. Assignment details here.

This assignment is due in less than 2 weeks for several reasons. You have had a week and a half to think about it, first. Secondly, it is simpler than others... all you need to do is create a splay method and decide where to call it in your other methods, and on which node to splay in each situation.

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 desiding 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 have posted 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).




Assignment 3: BHEAP Implementation in Java
due Friday, Mar. 3, 11:55pm
(hand in via Sakai)

Implement and test a minimum binary heap (priority queue) 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.




Assignment 2: BST Implementation using Linked Cells, in Java
due Monday, Feb. 20, 11:55pm
(hand in via Sakai)

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.




Assignment 1: LIST Implementation using Linked Cells, in Java
due Monday, Feb. 6, 11:55pm
(hand in via Sakai)

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.

the sentinel ... notes on doing this program here.




Assignment 0: Hello World! (Using Eclipse with the Test Oracle)
due Wed, Jan 18 at 11:55pm
(hand in via Sakai)

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