Project
Information about the programming project will be posted here.
Part 3:
- The project description can be found on the class handouts page.
- This project involves implementing a Euclidean Minimum Spanning Tree, as described in Lecture X02 (updated 4/30). See also Lecture 14 (updated 4/30) for information on how to answer nearest-neighbor queries in a kd-tree. (Read the latex lecture notes, since this is not covered in the slides.).
- Here is the skeleton code and test data.
Part 2:
- The project description can be found on the class handouts page.
- This project involves implementing a balanced variant of the kd-tree data structure, as described in Lecture 13 and Lecture 14. (It is best to read the latex lecture notes, rather than the hand-written slides, since they have more detailed information.) The differences are explained in the assignment handout.
- Here is the skeleton code and test data.
Part 1B:
- For details on quake heaps, please see these lecture notes on Quake Heaps.
- Here is the skeleton code and test data.
Part 1A:
- The handout about this programming assignment has been posted to the class handouts page.
- Here is the skeleton code and test data.
- The Quake Heap on which this assignment is based is a variant of the data structure developed and analyzed by Timothy Chan in this paper. Here is a Quake Heap web site with some nice figures illustrating operations.
- There are a few notable differences between our specifications and Chan's:
- Chan considers internal nodes to have either degree 1 or degree 2. We explicitly require that all internal nodes are binary-tree nodes. A degree-1 node is represented as having a non-null left child and a null right child.
- We are much more explicit about organizing roots according to level number.
- Chan does not sort trees when doing tree merging. We merge nodes in sorted order to guarantee that everyone will have the same tree structure, which makes testing simpler.
Part 0:
- The handout about this programming assignment has been posted to the class handouts page.
- The program must be written in Java, but you may use any IDE you like and any fairly recent version of Java should be sufficient. For instructions on how to get Java set up with Eclipse, see the CMSC 131 Java/Eclipse instructions. (Don't bother with the Course Management Plugin.)
- Here is the skeleton code and test data.
- Setting up the Java project in Eclipse (on Windows).
- Download the above Skeleton code and unzip.
- Fire up Eclipse in the Java perspective.
- Select: "File → New → Java Project".
- Unselect "Use default location" and click "Browse".
- Navigate to the folder you unzipped: "Part0-Skeleton".
- Click "Select folder".
- On returning to the New Java Project window, you should see "Project name: Part0-Skeleton" and "Location: C:\...\Part0-Skeleton". (You can change the Project name to something you prefer.)
- Unselect "Create module-info.java file".
- Click "Finish".
- If you see the folders "cmsc420_s22" and "tests" in your Eclipse Package Explorer window, then you should be good to go!
- Running the program (on Eclipse).
- In the Package-Explorer window, double-click on the files "Tester.java", "CommandHandler.java", and "DualList.java" to open them.
- The file "DualList.java" is the one you will modify.
- The file "Tester.java" contains the main program. The lines "inputFileName = "tests/test01-input.txt"" and "outputFileName = "tests/test01-output.txt"" specify the input and output files. You can change these as you like.
- To execute it, open "Tester.java", click on the "Run" icon (the green circle with the white triangle) and select "Run as → Java Application".
- If all goes as expected, you won't see anything in the Console except a line "<terminated> Tester [Java Application]...", and the output will appear in the file "tests\test01-output.txt".
- To view the output, go to the Eclipse Package Explorer window, right-click on "tests", and select "Refresh".
- Among the files under the tests directory, you should now see "test01-output.txt". Double-click to view the contents of this file.
