\documentclass{article} \usepackage{fullpage} \begin{document} \title{CMSC 420 Project--Spring, 2003\\Version 2.02} \date{Last Modified \today} \author{ The BIG 420 project. \footnote{Participation in this project may prove HAZARDOUS to your health. Unfortunately, failure to participate early and often will definitely have an adverse effect upon your GPA. Take my advice. Start now, because you're already behind. If you don't believe me, ask someone who took this course last semester.}} \maketitle \bigskip \section{General description} The primary motivation of this project is of course to get you to build and make use of data structures, and to take a look at benefits and shortcomings for each one. The TA's motivation though is to be able to make pretty pictures with some rudimentary drawing primitives. In project one we'll have you keep track of named dots (of various sizes and colors) and analyze and update those dots via a kd tree. Should be fun ;) In future parts of the project we will replace some data structures to examine performance tradeoffs. In particular you can probably expect to see the prof's old time favorite the PM1 quadtree, and the TA's favorite the B+ tree. \subsection{Part 1: SkipList and KD Tree} This section describes the first portion of the project, comprising development of a command line interpreter, a basic data dictionary and the kd tree. \subsubsection{CMSC420: Introduction to Command Parsing, where nothing could possiblie go wrong.} You are all blessed with a professor with a Ph.D. in fault tolerance. Because of this you will be expected to develop fault tolerant programs. This means bounds checking for input numbers and checking a number of possible error conditions for each command. It also means that your parser should never fail or crash because of a malformed command. A really useful command interpreter would give useful error messages about commands, such as ``wrong number of arguments'', or ``invalid argument type'', or even better ``second argument was int, expected string''. For our purposes it will be sufficient to print a single error message regardless of the error: \begin{verbatim} ***** Error: Invalid Command. \end{verbatim} Note the standard asterisks are printed. Do not echo the erroneous command. Your parser must completely ignore blank lines. For all other lines which are not fully formed and correct commands you must print the above error. As with other parts of the project, your command parser will be tested separately from the remaining requirements of the project. So if you can't get a fully error checking parser you will not be hurt on the other parts of the project. You may assume that for commands other than error checking all commands will be upper case and there will be no spaces within a command. There will be no blank lines and all commands will be valid. A working parser cannot make any of those assumptions. Commands should be correctly interpreted regardless of case (ie. CREATE\_DOT and creaTe\_DOT should both be interpreted as the CREATE\_DOT command). Blank lines should be completely ignored (in particular do not print extraneous ``*****''s). Whitespace in general should be ignored when parsing with one exception- any string (command name, dot name, or string arguement like the colors ``RED'' ``BLUE'', etc) cannot contain internal spaces. So a command like create\_dot(foo bar, 5,6, BLUE) should be flagged as invalid. \subsubsection{Comments on java} This semester all projects are to be written in java. The version on the detective cluster is 1.4 and can be downloaded at: http://java.sun.com/j2se/1.4/download.html The online version of the documentation is at http://java.sun.com/j2se/1.4/docs/api/index.html I highly recommend you download the java sdk and do most of your work from home, if nothing else this will lighten the load on the now overworked dc machines ;) They can be very slow around lower level project due dates ;) Of course as in most cs classes your projects will be compiled and run on the detective cluster machines (dc.umd.edu), so you should check to be sure your projects work there. However, there should not be any portability issues as long as you develop with the correct java version. I've heard good things about Borland's free jbuilder (registration required); You may wish to look into that. While you are permitted to use any java drawing facility you are comfortable with, a simple drawing package is available on the class web page. It is this package that will be most readily supported by the TA's should any problems arise. The package 'Canvas.java' provides a simple class which allows drawing of circles , squares, lines, captions, and other simple primitives in a java jframe. \subsubsection{SkipList.java} Another first for this semester is a requirement that some of your data structure code implement a standard interface. This will allow the TA to include your data structure in his own code. All of your dictionary classes this semester (currently a skiplist, and later a 2-3 or bplus tree) will implement java's sortedmap interface specified at: http://java.sun.com/j2se/1.4/docs/api/java/util/SortedMap.html You may of course have any number of other public functions which you find useful for your project. [edit: I won't change this so late, but I recommend that you *do not* add extra public functions so that your class stays interchangeable with TreeMap] As the TA implements this interface with own skiplist he may reduce this requirement by allowing you to skip some of the interface requirements. [edit: see the news group for functions which you may skip] If that happens I still think it would be a very beneficial exercise to implement the entire interface. The class must be named SkipList.java (note the case) and be located in a package called cmsc420. For a tutorial on packages see: http://java.sun.com/docs/books/tutorial/java/interpack/ \subsubsection{KD Tree- order 2} Unlike with the skiplist you are free to implement the kd tree any way you like with no particular interface. I will though recommend the use of java's point classes (point2d) which will allow you to easily make use of java's geometric algorithms later on. I would also suggest that you generally try to follow the java Collection interface. Standards are good things ;) Examining the command decoder, pay particular attention to the MAP\_ALL() function, which represents to the most common historical use of a kd tree. The primary purpose of the kd tree is to perform 'orthogonal range search' (ie. the rectangle search in the command decoder), which with a balanced tree has guaranteed O(sqrt(n)+k) run time, where k is the number of elements actually found. You'll note that you can count the number of points without actually visiting them all in O(sqrt(n)) time. \subsubsection{Part 1 Command Specification\label{cs1}} You will build a command decoder with a small set of commands; you will expand it later to accommodate commands required for future parts. The following is a list of commands you should support for part 1 and a description of the output you should give for each one. Note that for all functions, you should print \verb|''*****\n''| followed by a \verb|'' ==> ``| and an echo of the command given. For instance, the entire valid output to CLEAR\_ALL() is \begin{verbatim} ***** ==> CLEAR_ALL() All structures are cleared. \end{verbatim} The sample output should make this clear. This is done to negate the effects of input redirection and to assist in grading. Note that although it is done in the samples that will appear later, you are not required to reformat the original command (fixing spacing, for instance) in any way. The definitions below will use the following standard BNF definitions. \begin{verbatim} :=| := at (,) color: := RED|GREEN|BLUE|BLACK|WHITE :=Error: The specified dot does not exist. \end{verbatim} Whenever a appears(not in this part, but it will come up later), it means a floating point decimal number printed with exactly three digits after the decimal place (including trailing zeros as necessary). Also, when looking at the list of errors, eg. \begin{verbatim} := |||| \end{verbatim} the leftmost applicable error should always be the one printed. \begin{description} \item [CREATE\_DOT(name, x, y, radius, color)] creates a 'dot' object with the appropriate name, coordinates, radius, and color. The dot will then be added to a skiplist sorted based on the name (the data dictionary) and to one based on the coordinates. The latter structure is used to check for duplicate coordinates. Coordinates will be non-negative. This should be an O(logn) operation where n is the number of dots already in the dictionary. The dots should be stored in an asciibetically sorted SkipList. (If you don't complete a working skiplist you should use a TreeMap here instead to get some credit). If a dot with the same name already exists print an error. If a dock already exists at the specified coordinates print an error. \begin{verbatim} Output summary: :=| :=Created dot . :=| :=Error: Dot already exists. :=Error: Dot already exists at the specified coordinates. \end{verbatim} \item [DELETE\_DOT(name)] Removes the dot with the given name from the data dictionary. If the dot does not exist print an error. If the given dot has already been added to the kd tree map print an error and do not remove it from the dictionary. Delete from the dictionary should be O(logn), checking for existence in the kd tree will be dependent on the structure of the tree. \begin{verbatim} Output summary: :=| :=Delete dot . :=| :=Error: Dot has already been mapped and cannot be deleted. \end{verbatim} \item [LIST\_DOTS()] Lists all dots in the data dictionary in increasing asciibetical order. This function will be used as a measure of success for the CREATE\_DOT function. \begin{verbatim} Output summary: :=| := := Dictionary is empty. \end{verbatim} \item [COLOR\_DOT(name,color)] Changes the color of the dot with the specified name to the color given. The change should be reflected in the map, however the kd tree itself should not be accessed for this operation. \begin{verbatim} Output summary: :=| :=Color of changed from to . := \end{verbatim} \item [MAP\_DOT(name)] inserts the specified dock into kd tree map. If the dot does not exist in the dictionary print an error message. The kd tree is expected to be constructed in standard fashion, which means that your tree should be exactly the same as the TA's (so long as the map\_all function is never called). \begin{verbatim} Output summary: :=| :=Dot has been added to the map. :=| :=Error: The specified dot has already been added to the map. \end{verbatim} \item [MAP\_ALL()] This function will build an ideal (log n depth) kd tree from all the dots currently in the dictionary. In practice kd trees are often built to analyze data that already exists, rather than being constructed point by point. A kd tree of order 2 built this way has guaranteed theta(logn) depth and O(sqrt(n)) rectangle query search time. The first part of this operation should be to remove any dots which are currently in the kd tree. The run time of this function should be O(nlogn) expected. \begin{verbatim} Output summary: :=| :=All dots have been added to the map. := Dictionary is empty. \end{verbatim} \item [COUNT\_RECTANGLE(lx,ly, ux,uy)] prints the number of dots on the map whose coordinates are within the closed rectangle determined by the four points: (lx,ly),(lx,uy),(ux,ly),(ux,uy). Your program should be as efficient as possible, in particular it is not necessary to visit every point in order to get a correct count. If the kd tree is built using the MAP\_ALL command then this should run in O(sqrt(n)) time. \begin{verbatim} Output summary: := :=Total count: . \end{verbatim} \item [COLOR\_RECTANGLE(lx,ly,ux,uy,color)] This function locates all dots in the kd tree map whose coordinates are contained within the closed region determined by the four points: (lx,ly),(lx,uy),(ux,ly),(ux,uy) and sets their color to the one specified. Success can be determined with the DRAW\_MAP or LIST\_DOTS commands \begin{verbatim} Output summary: := :=Update complete. \end{verbatim} \item [PRINT\_KD\_TREE()] prints the output of traversing the kd tree in {\em preorder}. If the MAP\_ALL function as not been called then your output should match the TA's exactly. The output format is identical to that of LIST\_DOTS, except for the order that the dots are printed and the error message for an empty tree. \begin{verbatim} Output summary: :=| := := Tree is empty. \end{verbatim} \item [DRAW\_MAP()] Draws all the points of the map using the java canvas class. (If you're good with java graphics you are not required to use the canvas class, but your output should be similar). Your program should stop running until the graphics window is closed(this is the default behavior of the canvas class). \begin{verbatim} Output summary: := :=Drawing complete. \end{verbatim} \item [DRAW\_KD\_TREE()] Same as the DRAW\_MAP function, except that the partitions of the kd tree are also displayed. Examples will be provided. \begin{verbatim} Output summary: := :=Drawing complete. \end{verbatim} \end{description} \subsection{Part 2: PM1 quadtree and ShortestPath} \subsubsection{Adjacency List- updated} The first [smaller] part of this project will be to implement and use an adjacency list. You'll recall that an adjacency is conceptually a 'list of lists', ie: \begin{verbatim} A->C->D C D F->K->J H->K J K \end{verbatim} After much deliberation, for this project it has been decided that you will implement this structure as a Skiplist of Skiplists. Code re-use is good stuff, and a skiplist is functionally(as far as writing your program) no worse than any of the java API classes that are available. If you don't like your own SkipList you may inherit someone elses from project 1. Note that insertion/deletion from this structure is O(log(n)log(m)), where n is the number of nodes in the graph and m is the degree of the graph (the max number of edges incident to a single vertex). This represents a binary search to find the correct row of the list to find the starting vertex, followed by a a binary search to check for existance of the ending vertex. You are guaranteed that all paths in this project will be bidirectional. This means that you need only store each edge once instead of twice, giving you half the memory usage and half the access time but making your graph less general. This optimization is up to you(it's not much to implement). You'll use the graph to implement shortest path using dijkstra's algorithm. If you have a fibbonacci heap handy the run time of this algorithm is O(V*lg(V)+E) (where E is the number of edges and V is the number of vertices). And a fibonacci heap is what you ask? Well, I have no idea, but those of you who go on to take algorithms classes will no doubt hear about fibonacci heaps again, and I just wanted to be the first to share. Let's just say that they are magical, and that you will probably *never* learn how they work. If you've put this spec on paper, feel free to X is this paragraph to avoid reading it ever again. End digression. So anyway, you will be required to do shortest path in O(ElgV). It would be nice if you understand where this bound comes from, so I will explain it below, but as with the KDTree it suffices that if you implement the algorithm correctly, that is the runtime you will have. Allow me to sketch the algorithm to explain the running time(I'm not trying to teach the algorithm here- see your book/class/newsgroup/google). Every iteration of this algorithm you are guaranteed to find the correct shortest path to exactly one node- so we know right away there will be V iterations. At each state your graph is split in two sections- the 'solved' section, for which you know the correct distances, and the rest, which have some distance values associated with them which may or may not be accurate- this set is stored in some kind of priority queue. An iteration begins by selecting the node (call it 'N') from this queue with the best distance value, adding it to the 'solved' set, and 'relaxing' all it's edges. Relaxing is when for each node adjacent to N we see if it is faster to get to that node through N than it's current best known path. We update distances and back-pointers appropriately (so we know what the shortest path actually is when we finish), and that ends the round. Note that if a node's distance value is changed, its position in the priority queue has to be fixed up somehow. (this is where the magical fibonnaci heap would come into play, it's got an advantage in this 'fix up' step). One way to do this is just to have multiple copies of the same node in the queue and ignore them when they come back up (this is the approach I will use in the explanation), or else to remove the old value before reinserting it. Either works. Now, how long does all this take. There are V rounds, and in every round we have to pull something out of the front of the priority queue- which with a skiplist is an O(1) expected time operation(note that it would be log(E) in a balanced binary tree), so each round takes O(V) time. Rather than try and deal with how many elements are added to and removed from the queue in any single round, it is easier to think about how many such operations can occur in the life of the algorithm. Every single edge in the graph has exactly one opportunity to add a vertex to the queue (during a relax operation), so there are O(E) possible insertions. If we allow duplicates, the size of the queue can grow to O(E), so we may treat each queue operation as O(log(E)). That gives O(ElogE) running time for all queue operations during the life of the algorithm. Together that gives a running time of O(V+ElgE), which since E is bounded by $V^2$, is O(ElgV). And that's the required running time of your search;) Yes, your adjacency list is to be a skiplist of skiplists, and you should go ahead and use your skiplist for the priority queue (you may either use the O(logn) operation to remove the head of the list, or you may implement a 'pop' or 'shift' operation that runs in O(1) expected/amortized time. Why expected? Well, you have update that tower for that node- and the tower may be up to about O(logn) height. Recall though that the *average* height of a node is only 2. You might want to understand this stuff- you might have occasion to want to explain it to someone someday,or something... ;) \subsubsection{PM1 Quadtree} In a bit of spontaneity I've made one change to our usual quadtree. The INIT\_QUADTREE() function will allow the user to specify the dimensions of the quadtree at runtime. (in the past we always fixed the size at 1024x1024). In exchange you may prevent your leaf nodes from ever splitting beyond 1x1 cells. Any two objects that fall into a 1x1 cell will be treated as an intersection. Because no one objected, I am mandated that we all build our trees in a standardized way, so that the structure appears identical. Your tree and nodes will have to follow the following standard rules: \begin{enumerate} \item No two points can fall in the same node \item A point cannot be contained in the same node as a segment, unless that point is an endpoint of that segment. \item No two segments can fall in the same node, unless they intersect at a shared endpoint *and* that endpoint is contained in the *same* node. \item If a point falls on the boundary between more than one node, then it must be added to every node that it intersects (a point may be contained in up to four leaf nodes). \item If a single point of a segment falls on the boundary of more than one node then it must be added to all of those nodes as above. (A single segment can of course appear in a *lot* of nodes). \item The tree must at all times be minimal- that is, there must never be a smaller tree which follows all of the above rules and still contains all of the same data. This should only be a complicated issue during deletion. \end{enumerate} In no case should you try to attempt to solve any pm1 problems with brute force. All that is generally required is logical pruning- ie. "If the segment does not overlap my southeast child, then don't try adding it to that child!" And oh yes, unlike in the book, *our* skiplists have (0,0) at the southwest corner and *not* the northwest corner(the inverted coordinate system used by your monitor and most graphics apps). Since there are a lot of complexities in how you build your quadtree there will be less stringent speed requirements then there were in P1. Still, try to make it as efficient as you can! There will still be benchmarks, and many kudos at least for the fastest implementations(maybe extra credit, but I have no say in that). Don't brute force, please? :) That should be all you need to know to build a quadtree! \subsubsection{Part 2 Command Specification\label{cs2}} You will build a command decoder with a small set of commands; you will expand it later to accommodate commands required for future parts. The following is a list of commands you should support for part 2 and a description of the output you should give for each one. Note that for all functions, you should print \verb|''*****\n''| followed by a \verb|'' ==> ``| and an echo of the command given. For instance, the entire valid output to a hypothtical *wink wink* CLEAR\_ALL() command would be: \begin{verbatim} ***** ==> CLEAR_ALL() All structures are cleared. \end{verbatim} This is done to negate the effects of input redirection and to assist in grading. Note that although it is done in the samples that will appear later, you are not required to reformat the original command (fixing spacing, for instance) in any way. The definitions below will use the following standard BNF definitions. \begin{verbatim} :=| := at (,) color: := RED|GREEN|BLUE|BLACK|WHITE :=Error: The specified dot does not exist. \end{verbatim} Whenever a appears, it means a floating point decimal number printed with exactly three digits after the decimal place (including trailing zeros as necessary). To do this in java check out the NumberFormat class. Also, when looking at the list of errors, eg. \begin{verbatim} := |||| \end{verbatim} the leftmost applicable error should always be the one printed. \begin{description} \item [INIT\_QUADTREE(size)] Sets the upper bounds for the quadtree. After initialization the quadtree should hold points/lines that fall between [0,0] at the southwest/lower left hand corner, and [$2^{size}, 2^{size}$] in the northeast upper right hand corner. If size is less than 2 or more than 30 print an error. This command will always precede the first command which requires the quadtree. This command is only valid the first time it is successfully called (out of range is not a successful call). If an attempt is made to reinitialize the tree, print an error. \begin{verbatim} Output summary: :=| :=Quadtree initialized. :=| :=Error: size out of range. :=Error: The Quadtree has already been initialized. \end{verbatim} \item [CREATE\_DOT(name, x, y, radius, color) UNCHANGED] Creates a 'dot' object with the appropriate name, coordinates, radius, and color. The dot will then be added to a skiplist sorted based on the name (the data dictionary) and to one based on the coordinates. The latter structure is used to check for duplicate coordinates. Coordinates will be non-negative. This should be an O(logn) operation where n is the number of dots already in the dictionary. The dots should be stored in an asciibetically sorted SkipList. If a dot with the same name already exists print an error. If a dock already exists at the specified coordinates print an error. \begin{verbatim} Output summary: :=| :=Created dot . :=| :=Error: Dot already exists. :=Error: Dot already exists at the specified coordinates. \end{verbatim} *** \item [DELETE\_DOT(name)] Removes the dot with the given name from the data dictionary. If the dot does not exist print an error. If the given dot has already been added to the Adjacency List (via CREATE\_PATH()) print an error and do not remove it from the dictionary. If it has already been added to the PM1 (via MAP\_SEGMENT()) print an error. Delete from the skiplist should be O(logn). Some slowdown may occur from checks to the adjacency list and PM1 if either is non-empty. This command will likely be used to verify that you can search for points in those structures ;) \begin{verbatim} Output summary: :=| :=Deleted dot . :=|| :=Error: Dot has already been added to the Adjacency List. :=Error: Dot has already been added to the Quadtree. \end{verbatim} \item [LIST\_DOTS() UNCHANGED] Lists all dots in the data dictionary in increasing asciibetical order. This function will be used as a measure of success for the CREATE\_DOT function. \begin{verbatim} Output summary: :=| := := Dictionary is empty. \end{verbatim} \item [COLOR\_DOT(name,color) UNCHANGED] Changes the color of the dot with the specified name to the color given. The change should be reflected in the map, however only the skiplist should be accessed for this operation. \begin{verbatim} Output summary: :=| :=Color of changed from to . := \end{verbatim} \item[CREATE\_PATH(name1, name2)] adds a bidirectional path between the dots named to the Adjacency List. If one or both dots does not exist print the for the first argument not found. If the segment already exists print an error. This command is not related to the PM1. \begin{verbatim} Output summary: :=| :=Created segment (name1,name2). :=| :=Error: The specified segment already exists. \end{verbatim} \item[DELETE\_PATH(name1, name2)] Deletes the edge between name1 and name2 from the Adjacency list. If either endpoint does not exist, or the edge does not exist print an error. This command is not related to the PM1. \begin{verbatim} Output summary: :=| :=Deleted Segment (name1,name2). :=|| :=Error: The specified segment does not exist. \end{verbatim} \item[SHORTEST\_PATH(name1,name2)] Prints the shortest path from the first dot to the second dot based on the segments in the Adjacency List. If either name is not in the dictionary print an error. If there is no path between the two dots (possibly because one of the endpoints was never added to the adjacency list) then print an error. Otherwise print out the shortest path, followed by the total length of the path. \begin{verbatim} Output summary: :=| := -> Total length:. := -> | := | := Error: No path exists. \end{verbatim} \item[MAP\_SEGMENT(name1,name2)] Adds a segment to the PM1.It is possible that name1==name2, this should not be an error. The PM1 should be able to know whether any given point has a path to itself or not. There is one further error to detect. If the segment intersects a segment already in the tree(except for shared endpoints), print an error and leave the PM1 unchanged. You may use this error even if the segment intersected is the same as the one you are trying to insert. Further discussion on interesection detection rules will appear on the newsgroup and later versions of the spec. This command is unrelated to the CREATE\_PATH command. \begin{verbatim} Output summary: :=| :=Mapped segment (name1,name2). :=| :=Error: Intersection detected. \end{verbatim} \item[UNMAP\_SEGMENT(name1,name2)] Deletes a segment from the PM1. If the points do not exist, or the segment does not exist, print an error. If after the operation an endpoint would be left with no adjacent segments then it should also be completely removed from the tree. The tree should be collapsed so that it is minimal- which basically means that the tree should look as if the segment had never been in the tree to begin with. (Some collapsing will need to be done). Remember that if (A,A) is explicitly added to the tree via MAP\_SEGMENT, then (A,A) must be unmapped before A is removed. \begin{verbatim} Output summary: :=| :=Unmapped Segment (name1,name2). :=| :=Error: The specified segment was not found on the map. \end{verbatim} \item [COLOR\_SEGMENTS(lx,ly,ux,uy,color)] A twist on the old version. This function will first locate all segments in PM1 which {\em OVERLAP} the specified inclusive rectangular region(determined by (lx,ly),(lx,uy),(ux,ly),(ux,uy)). Then it will change the color of the endpoints of those segments to the color specified. The endpoints will not necessarily be in the tree. Print the number of unique segments matched. Success can also be determined with the DRAW\_MAP or LIST\_DOTS commands \begin{verbatim} Output summary: := :=Update complete. Found segments. \end{verbatim} \item [PRINT\_QUADTREE()] Prints out the PM1 Quadtree map. Be sure to read the section on the PM1 to understand what its structure must be. When printing you must print in the following order: Northwest, Northeast, Southwest, Southeast. If you reach a leaf with a dot in it you should print the dot's name, followed by all the dots it is adjacent to in some order. If a black leaf does not contain an endpoint dot, print the segment that passes through it. A tree with only one isolated point created by MAP\_SEGMENT(A,A) should have output: \begin{verbatim} A:A \end{verbatim} IE., a one element tree should look like a leaf, even if not implemented that way. \begin{verbatim} Output summary: :=| := :=|| := NW NE SW SE :=:| := := | := (,) := Tree is empty. \end{verbatim} \item [DRAW\_MAP()] Draws all the points and segments of the pm1 map using the java canvas class. The points should be displayed as in part1, the lines can be plain solid black lines. (If you're good with java graphics you are not required to use the canvas class, but your output should be similar). Your program should stop running until the graphics window is closed(this is the default behavior of the canvas class). \begin{verbatim} Output summary: := :=Drawing complete. \end{verbatim} \item [DRAW\_QUADTREE()] Draws the internal partitions of the quadtree, as well as the segments inside it. Do not draw the pretty colorful dots, as they will just get in the way of debugging. \begin{verbatim} Output summary: := :=Drawing complete. \end{verbatim} \end{description} \subsection{Submission Instructions} To make your submission file, make a directory and copy all required files into it. Change to that directory and type: \begin{verbatim} tar -cvf part#.tar * gzip part#.tar \end{verbatim} To submit type(submit will usually be working 1 week before the due date): \begin{verbatim} ~mhs20001/Bin/submit # part#.tar.gz \end{verbatim} In all cases '\verb|#|' represents the number of the project part you are submitting(1,2,3 or 4). The filename is not really important; It is important that the file is in .tar.gz format and that your Main.java and other required files are not in a subfolder of the tar file. You must include the following with every submission: All necessary source files (*.java etc.) to compile your program. A file called README, all upper case, which contains your name, login id, and any information you would like to add. If you leave out the README your project will fail to submit! You are welcome to use a makefile for development (javac doesn't track dependencies very well) but I should be able to run your project with the following two commands: \begin{verbatim} javac Main.java java Main \end{verbatim} No promises are made that I will read your READMEs, but they are useful when problems come up with a project. There is a 100K filesize limit. Please don't include .class files- I will probably strip them out before testing your projects anyway. Every early submission will overwrite the previous early submission, every ontime submission will overwrite any previous ontime submissions, every 1day late submission will overwrite any previous 1day late submission and so on. So I will have one submission for every valid submission period. (Late policy TBA). I will grade every submission that is saved(including applicable bonuses and penalties) and you will get the highest grade among them If there are any errors in my IO you are still responsible for them- the spec is what is in charge. So if you match all my current IO and submit early and then someone points out that I printed the wrong error message for some function, you have to fix your project and resubmit ;) You should be coding to match the command specification, not my sample IO. Here is a (c++) makefile that you might use as a hint for how to set up dependencies for make. \begin{verbatim} CC = cxx FLAGS = LFLAGS = -lm proj4: bpnode.o bptree.o cell.o main.o pmedge.o pmpoint.o pmquadtree.o util.o $(CC) $(LFLAGS) *.o -o proj4 bpnode.o: bpnode.cpp bpnode.h bpdata.h $(CC) -c $(FLAGS) bpnode.cpp bptree.o: bptree.cpp bptree.h bpdata.h $(CC) -c $(FLAGS) bptree.cpp cell.o: cell.cpp cell.h bpdata.h pmpoint.h pmedge.h celledge.h $(CC) -c $(FLAGS) cell.cpp main.o: main.cpp bptree.h cell.h celledge.h pmedge.h pmpoint.h util.h psdraw.h $ $(CC) -c $(FLAGS) main.cpp pmedge.o: pmedge.cpp pmedge.h pmpoint.h util.h $(CC) -c $(FLAGS) pmedge.cpp pmpoint.o: pmpoint.cpp pmpoint.h pmedge.h $(CC) -c $(FLAGS) pmpoint.cpp pmquadtree.o: pmquadtree.cpp pmquadtree.h pmpoint.h pmedge.h util.h psdraw.h $(CC) -c $(FLAGS) pmquadtree.cpp util.o: util.h util.cpp $(CC) -c $(FLAGS) util.cpp clean: rm -f *.o rm -f proj4 rm -f core \end{verbatim} \subsection{Grading} There will be a few parts to grading your projects Your projects will be graded running them on a number of test files for which I have already created correct(we hope) output. Your output will have all punctuation, blank lines, and non-newline whitespace stripped before diffing similarly cleaned files. New to this semester some of your data structures may be included with the TAs own testing code to test their efficiency and correctness. In addition, there may be some subjective grading based on your drawing functions. Some text output cannot always be graded by simply diffing because there is no guarantee that we will have the same output. In these cases your project's output will be pre-processed. In the case of the B+ tree, for instance, this program will verify that each node has the correct number of keys, that they are correctly ordered, and that all the correct data is at the leaves(and any other rules I may have left out). Thanks to the miracle of automation you should expect your projects to be run on very very large inputs. Typically each test file will be worth 10 points, and you will be eligible for either 10 or 0 points depending on whether you pass for fail that test. There is no partial credit for an individual test. I may give points projects that fail a test because of 'small' errors after initial grading at my own discretion. The tests will try to test mutually exclusive components of your projects independently. However, if you don't have a dictionary which at least correctly stores all points so that some 'get lost', you may still end up failing a k-d tree test. So, if you can't get the skiplist to work you may wish to replace it with a functional TreeMap so you can get credit for the rest of the project. (This holds for other structures as well later on). \subsection{Standard Disclaimer: Right to Fail(twice for emphasis!)} As with most programming courses, the instructor reserves the right to fail any student who does not make a good faith effort to complete the project. If you have problems with completing any given part of the project please talk to Dr. Hugue immediately- do not put it off! While the TA enjoys failing students, Dr. Hugue does not, so please be kind and do the project. A submission that gets only 20 or 30 points is considerably better for you than no submission at all. \subsection{Integrity Policy} From Dr. Hugue: Your work is expected to be your own or to be labeled with its source, whether book or human or web page. Discussion of all parts of the project is permitted and encouraged, including diagrams and flow charts. However, pseudocode writing together is discouraged because it's too close to writing the code together for anyone to be able to tell the difference. Since the projects are interrelated, and double jeopardy is not my goal, we have a very liberal code use and reuse policy. First and foremost, use of code produced by anyone who is or has ever taken 420 from me requires email from provider and user to be sent to the instructor. The instructor is the sole arbiter of code use and reuse, and reserves the right to fail any student who does not make a good faith effort on the project, or who refuses to adhere to the policies stated herein. Remember, it is better to ask and feel silly, than not to ask and receive a complimentary F or XF. \end{document}