PROGRAMMING ASSIGNMENT #4- Buffer Graph

For this project, you will reproduce Project 1 with the following modifications:
1. Instead of using an array for your memory manager, its memory will be a disk file mediated
by a buffer pool.
2. You will maintain a graph data structure.
3. There is a new command that will compute and print some statistics on the graph.
Assignment:
You will process a series of commands (similar to the commands of Project 1) to store a collection
of artist and song names. You will use a memory manager to manage storing the names, with the
names themselves stored in a file on disk. This memory manager will be identical to Project 1,
except that instead of using an array, you will use the disk file managed by a buffer pool. Be careful
that you write out all of the buffers at the end of the program, because your correctness score will
depend in part on your memory file exactly matching the reference test’s memory file.
Just as in Project 1, you will use two closed hash tables, one for accessing artist names and
the other for accessing song titles.
The main addition to Project 1 is that you will maintain a graph data structure. The graph
will be implemented using the adjacency list data structure (see Chapter 14 in OpenDSA). The
graph will have a node for each song and each artist, and will link a song node with an artist node
if there is a recording of that song by that artist. Specifically, when you process an insert command
with artist ART and song SONG, you will do the following:
1. If this is a new artist name or new song name, add new nodes to the graph as necessary.
2. Add a link in the recording graph between the nodes for ART and SONG.
You will need to come up with a reasonable way for expanding the number of nodes in the
graph as necessary. Keep in mind that nodes can be removed from the graph as well.
Invocation and I/O Files:
The program would be invoked from the command-line as:
java GraphProject {memFile} {numBuffs} {buffSize} {initHashSize} {commandFile} {statFile}
The name of the program is GraphProject. Parameter {memFile} is the name of the file that
will store the memory pool. Parameter {numBuffs} determines the number of buffers allocated for
the buffer pool. Parameter {buffSize} is the size for a block in the memory pool (and so also the
size of a buffer in the buffer pool). Parameter {initHashSize} is the initial size of the hash table
(in terms of slots). Your program will read from text file {commandFile} a series of commands,
with one command per line. The program should terminate after reading the end of the file. The
1
statFile should print out collected statistics just as in Project 3. You should time how long it takes
to process the command file, and then print the statistics (including time required) at the end of
the program.
The formats for the commands are identical to that of Project 1, with the following addition:
print {artist|song|blocks|graph}
This is identical to Project 1, except for the addition of the graph option. When the graph
option is given you will do the following:
1. Compute connected components on the graph. (You will use the Union/FIND algorithm for
this purpose, see OpenDSA Module 13.1.) Print out the number of connected components,
and the size of the largest connected component.
2. Compute (and print) the diameter for the largest connected component using Floyd’s algorithm for computing all-pairs shortest paths (OpenDSA Module 14.8).
Programming Standards:
You must conform to good programming/documentation standards. Web-CAT will provide
feedback on its evaluation of your coding style, and be used for style grading. Beyond meeting
Web-CAT’s checkstyle requirements, here are some additional requirements regarding programming
standards.
• You should include a comment explaining the purpose of every variable or named constant
you use in your program.
• You should use meaningful identifier names that suggest the meaning or purpose of the
constant, variable, function, etc. Use a consistent convention for how identifier names appear,
such as “camel casing”.
• Always use named constants or enumerated types instead of literal constants in the code.
• Source files should be under 600 lines.
• There should be a single class in each source file. You can make an exception for small inner
classes (less than 100 lines including comments) if the total file length is less than 600 lines.
We can’t help you with your code unless we can understand it. Therefore, you should no bring
your code to the GTAs or the instructors for debugging help unless it is properly documented and
exhibits good programming style. Be sure to begin your internal documentation right from the
start.
You may only use code you have written, either specifically for this project or for earlier programs, or code provided by the instructor. Note that the OpenDSA code is not designed for the
specific purpose of this assignment, and is therefore likely to require modification. It may, however,
provide a useful starting point.
Deliverables:
You will implement your project using Eclipse, and you will submit your project using the
Eclipse plugin to Web-CAT. Links to the Web-CAT client are posted at the class website. If you
make multiple submissions, only your last submission will be evaluated. There is no limit to the
number of submissions that you may make.
2
You are required to submit your own test cases with your program, and part of your grade will
be determined by how well your test cases test your program, as defined by Web-CAT’s evaluation
of code coverage. Of course, your program must pass your own test cases. Part of your grade will
also be determined by test cases that are provided by the graders. Web-CAT will report to you
which test files have passed correctly, and which have not. Note that you will not be given a copy
of these test files, only a brief description of what each accomplished in order to guide your own
testing process in case you did not pass one of our tests.
When structuring the source files of your project, use a flat directory structure; that is, your
source files will all be contained in the project “src” directory. Any subdirectories in the project
will be ignored.
You are permitted to work with a partner on this project. When you work with a partner, then
only one member of the pair will make a submission. Be sure both names are included in the
documentation. Whatever is the final submission from either of the pair members is what we will
grade unless you arrange otherwise with the GTA.
Pledge:
Your project submission must include a statement, pledging your conformance to the Honor
Code requirements for this course. Specifically, you must include the following pledge statement
near the beginning of the file containing the function main() in your program. The text of the
pledge will also be posted online.
// On my honor:
//
// - I have not used source code obtained from another student,
// or any other unauthorized source, either modified or
// unmodified.
//
// - All source code and documentation used in my program is
// either my original work, or was derived by me from the
// source code published in the textbook for this course.
//
// - I have not discussed coding details about this project with
// anyone other than my partner (in the case of a joint
// submission), instructor, ACM/UPE tutors or the TAs assigned
// to this course. I understand that I may discuss the concepts
// of this program with other students, and that another student
// may help me debug my program so long as neither of us writes
// anything during the discussion or modifies any computer file
// during the discussion. I have violated neither the spirit nor
// letter of this restriction.
Programs that do not contain this pledge will not be graded.
3