COMP 410 Assignments Page UNC-CH COMP 410 Class Assignments Info For ALL: Checking Code and Submitting Assignments Common Grading Issues... how to avoid them (run Java 8) Assignment 5: Dijkstra's Algorithm for single source shortest path (weighted) due Mon, Nov 16, at 11:55pm (hand in via Sakai) 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. You MAY USE the Java Collections library for this assignment. You may want lists, queues, hashmaps, etc. You will need a priority queue to make Dijkstra's algorithm efficient. Use your own ADT's or use the Java collections versions, your choice. Write your own graph code and your own Dijkstra's code. Notes on the Oracle We will post an oracle for this assignment, as we have for others. In this assignment we are suggesting a 2-phase implementation: first build the basic graph data structure and test it with the oracle then add to your code the Dijkstra algorithm and solve the shortest path problem... use the oracle to test this as well We will use the same oracle for each phase, as the oracle contains tests for the basic build operations (add node, add edge, etc.) as well as calls to the dijkstra operation. For the first phase you should see success for the build operations and failure for dijkstra. Then when you complete the second phase you will see all green on the tests. As usual, you should do your own testing as the oracle is not a complete set of test cases. The grader will be more comprehensive... as usual. Assignment 4: Cache_LFU Implementation in Java due Mon, Nov. 2, 11:55pm (hand in via Sakai) Implement and test Cache data structure using a Least Frequently Used (LFU) frame replacement policy. This will be done with a cooperating pair of data structures: a HashMap (from Java collections) and a MinBinHeap which you write on your own. 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. Use the Java Collections library for HashMap in this assignment. Write all your own code for MinBinHeap. Assignment 3: HashMap Implementation in Java due Mon, Oct 14, 11:55pm (hand in via Sakai) Implement and test a HashMap in Java. This a MAP abstraction built on a hash table. The MAP interface is the same one you implemented in Assignment 2. Assignment details here. As before, 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 all your own code for the ADTs. Assignment 2: TreeMap Implementation using Linked Cells, in Java due Wed, Sept 23, 11:55pm (hand in via Sakai) Implement and test a TreeMap in Java. Use linked cells (not arrays). This a MAP abstraction built on a Binary Search Tree. We will discuss both ADTs in class. Assignment details here. As before, 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 code and map and tree code. Assignment 1: StackSet Implementation using Linked Cells, in Java due Wed, Sep. 2, 11:55pm (hand in via Sakai) Implement and test a StackSet 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 (the "oracle"); 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. Linked Cells and Pointers: This discussion contains some possibly useful information about doing linked cell programming with objects in Java. Another way to say this is using "pointers" in Java. A pointer is a reference to some memory location (like a reference to an object). In languages like C and C++, a pointer is a basic data type. In Java, it is not. Use of a pointer is disciplined. This assignment is largely "fill in the blanks". We are giving you a code framework that you will cut and paste into Eclipse, and then you will write the missing methods that correctly give the behavior defined by the StackSet ADT abstraction. You will also write code to test your implementation -- to convince yourself that your code has captured all the required bahavior, correctly. Later assignments will be more complicated. We are still warming up here. Tips on programming all your assignments (and life) 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 look 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. Assignment 0: Hello World! (Using Eclipse with the Test Oracle) due Wed, Aug. 19 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. 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 Details here.
