COMP20003 Algorithms and Data Structures @ Semester 2, 2022

Purpose

The purpose of this assignment is for you to:

Improve your proficiency in C programming and your dexterity with dynamic memory allocation.

Demonstrate understanding of a concrete data structure (quadtree) and implement a set of algorithms.

Practice multi-file programming and improve your proficiency in using UNIX utilities.

Building a PR Quadtree (Inserting Datapoints)

In a PR quadtree, each node represents a rectangle that covers part of the area that we wish to index. The root node covers the entire area. A PR quadtree is built            recursively: we first start with an initial rectangle that should contain all the points

we wish to store (how could you find a rectangle for nn 22-dimensional points so      that it contains all given datapoints?). To then construct a PR quadtree of a set of nn points, we insert the points one by one and recursively subdivide a rectangle into     four equally sized sub-rectangles whenever a rectangle would contain more than a  single point. After the insertion process is complete, every leaf node is either            coloured in black (contains a single datapoint) or white (indicating that the node is    empty), and internal nodes are coloured in grey (see the figure above).

Alternatively, you could also use the following strategy: we insert all points into the            rectangle and recursively partition each rectangle into 4 quadrants (sub-rectangles) until each rectangle contains at most one point.

The construction of a PR quadtree also leads to one important difference between them and binary trees: a binary tree depends on the order of value insertion whereas a PR quadtree is independent of the order of datapoint insertion. The reason is that the nodes are independent from the inserted datapoints (the rectangles are          determined by the initial rectangle of the root node).

Search

To enable efficient search, the rule is that every leaf node in a PR quadtree either contains a single point or no point at all. Every node in a PR quadtree is either a leaf node or an internal node, i.e., has four children representing a subdivision of the current       rectangle into four equally sized quadrants. The region of an internal node always   contains more than one point.

If we search for a single datapoint using its 2D2D coordinates, we first check if the point lies in the quadtree. If it does, we recursively compute on each level the sub-      rectangle that contains the coordinates of the datapoint to be searched until we   reach a leaf node. The leaf node either contains the datapoint or it does not.

Your Task

Your implementation of a PR quadtree has to support a number of functions to store data points and to search for them. You will need to implement functions to support       inserting data points, searching for individual datapoints and searching (returning) for all datapoints within a query rectangle.

Insertion

To insert a data point into a PR quadtree we start with the root node. If the PR quadtree is empty, i.e., the root node is coloured as white (which we represent as a pointer to    NULL) and the point lies within the area that should be covered with the PR              quadtree, the data point becomes the root. If the root is an internal node, we             compute in which of the four children the data points lies (of course, if the data point lies outside of root rectangle, it is not inserted and an error message returned).        Again, if the corresponding node is an internal node, we recursively repeat this         process until we find a leaf node. If the leaf node is empty, we simply insert the        point. If the leaf node is black, i.e., has already one node, we need to split the leaf   node into four children, i.e., the existing black leaf node becomes a grey internal      node. We repeat splitting the node until we find an internal node so that two of its     children contain the existing and the newly inserted datapoint, i.e., are black leaf      nodes. In other words: splitting a black leaf can also led to a recursive process.

Find (Search)

To find a datapoint (and often its associated information), we simply traverse the PR         quadtree by selecting the internal child node whose rectangle contains the location of the datapoint. The search stops once we have reached a leaf node. If the leaf    node has stored the datapoint, we return its associated information; otherwise the  search simply reports that the datapoint is not stored in the PR quadtree.

Range (Window) Query

An important query is to report all datapoints whose locations are contained in a given        query rectangle. This query is typically called a range or window query. To run range query on a quadtree, we have the following recursive process: we start the root and check if the query rectangle overlaps with the root. If it does, we check which            children nodes also overlap with query rectangle (this could be all of them for a         centred query rectangle). Then we repeat this procedure for all internal children        overlapping with the query rectangle. The recursion stop once we have reached the leaf level. We return the datapoints from all black leaf nodes whose datapoints are   located within the query rectangle.

Implementation Details

To implement your own PR quadtree, you will need to set up some data structures and       functions, you will likely need a number of structures and helper functions, these are not required and you do not need to follow the naming style or function as                 described, but you will likely find them useful in your implementation. As a minimum

you will likely have the following data structures:

point2D that stores the location of datapoint;

rectangle2D that specifies a rectangle given an bottom-left 2D point and a upper-right 2D point;

dataPoint, which is a structure that stores the location and associated information (i.e., the footpath information);

quadtreeNode, which stores a 2D rectangle and 4 pointers referring to the four children SW, NW, NE and SE.

You will also likely need the following functions:

inRectangle: tests whether a given 2D point lies within the rectangle and returns 1 (TRUE) if it does. The function takes the point and the rectangle; note that the convention is that points are within a rectangle if they are on lower and right boundary but not on the top or left boundary. This enables us to construct a well-defined partition of the  space if points lie on boundaries of the quadtree node rectangle.

rectangleOverlap: tests whether two given rectangles overlap and returns 1 (TRUE) if they do.

determineQuadrant: given a rectangle and point, returns the quadrant of the rectangle that the point lies in. The convention is 0=SW, 1=NW, 2=NE, 3=SE for the quadrant. You may like to implement helper functions which also select relevant pointers from the  quadtreeNode given a quadrant. You may find writing an enum quadrant useful for  implementing and using this function.

addPoint: this function will add a datapoint given with its 2D coordinates to the quadtree. You will need to setup the logic discussed before.

searchPoint: tests whether a datapoint given by its 2D coordinates lies within the rectangle and returns the datapoint (and its stored information) if it does and NULL otherwise.

rangeQuery: takes a 2D rectangle as argument and returns all datapoints in the PR

quadtree whose coordinates lie within the query rectangle.

Tip: if you have begun implementing and are stuck, check this page, you will likely need one of these functions.

Stage 3 - Supporting Point Region Queries

In Stage 3, you will implement the basic functionality for a quadtree allowing the lookup of data by longitude (x) and latitude (y) pairs.

Your Makefile should produce an executable program called dict3. This program should take seven command line arguments.

The first argument will be the stage, for this part, the value will always be 3. The second argument will be the filename of the data file.

The third argument will be the filename of the output file.

The fourth and fifth argument specify the x, y co-ordinate pair of the bottom-left corner of the root node area, with the first value referring to the longitude (x) and the second value referring to the latitude (y).

The sixth and seventh argument specify the top-right corner of the root node area,

following the same convention.

Your program should:

Just as in Assignment 1, read data from the data file specified in the second command line argument. This may be stored unchanged from dict1 or dict2 in earlier                      implementations.

Construct a quadtree from the stored data.

Interpret and store the fourth, fifth, sixth and seventh arguments as long double values. The strtold  function should be used to achieve this.

Accept co-ordinate pairs from stdin, search the constructed quadtree for the point region  containing the co-ordinate pair and print all matching records to the output file. You may assume that all queries will be terminated by a new line. You should interpret these values as double values.

In addition to outputting the record(s) to the output file, the list of quadrant directions  followed from the root until the correct point region is found should be output to stdout.

Your approach should insert each footpath's (start_lon, start_lat) and (end_lon, end_lat)   pairs into the quadtree, allowing the footpath to be found from its start or end point.

Where multiple footpaths are present in the found point region, footpaths should be printed

in order of footpath_id.

The quadrants in relation to the dataset are:

Stage 4 - Supporting Range Queries

In Stage 4, you will add the additional functionality to your quadtree to support range queries given by (x, y) co-ordinate pairs.

Your Makefile should now also produce an executable program called dict4 . This program should take seven command arguments, similar to Stage 3, with only the expected value of the first argument changing:

The first argument will be the stage, for this part, the value will always be 4. The second argument will be the filename of the data file.

The third argument will be the filename of the output file.

The fourth and fifth argument specify the x, y co-ordinate pair of the bottom-left corner of the root node area, with the first value referring to the longitude (x) and the second value referring to the latitude (y).

The sixth and seventh argument specify the top-right corner of the root node area,

following the same convention.

Your dict4 program should:

Just as Stage 3, read in the dataset, store it in a dictionary and construct a quadtree on the stored data.

For Stage 4, you should accept sets of pairs of co-ordinate long double type values from stdin, and efficiently use the quadtree to find all footpaths which are within the      bounds of the query. You may assume that no blank lines will be present in the    queries.

Output to stdout should include all directions searched in order, with each branch            potentially containing points within the query bounds fully explored before             proceeding to the next possible branch. Where multiple directions are possible,    quadrants must be searched in the order SW , NW , NE, SE . Each direction must be separated by a space. The definitions of each quadrant are given in the table   below.

Similar to Stage 3, where multiple footpaths are returned by the range query, these should be sorted by footpath_id. Output each footpath only once for each query, even if     both its "start" and "end" points both occur in the searched region.

Example Execution

An example execution of the program might be:

Requirements

The following implementation requirements must be adhered to:

You must write your implementation in the C programming language.

You must write your code in a modular way, so that your implementation could be used in  another program without extensive rewriting or copying. This means that the            dictionary operations are kept together in a separate .c file, with its own header (.h) file, separate from the main program, and other distinct modules are similarly           separated into their own sections, requiring as little knowledge of the internal details of each other as possible.

Your code should be easily extensible to multiple dictionaries. This means that the           functions for interacting with your dictionary should take as arguments not only the values required to perform the operation required, but also a pointer to a particular dictionary, e.g. search(dictionary, value).

Your implementation must read the input file once only.

Your program should store strings in a space-efficient manner. If you are using malloc() to create the space for a string, remember to allow space for the final end of string     character, ‘\0’ (NULL).

Your program should store its data in a space-efficient manner. If you construct an index,

this index should not contain information it does not need.

Your approach should be reasonably time efficient.

You may assume the quadtree only needs to be built after all records are read for

simplicity.

You may assume you will not be provided with points outside the specified region.

A full Makefile is not provided for you. The Makefile should direct the compilation of your program. To use the Makefile, make sure it is in the same directory as your code, and type make dict3 and make dict4 to make the dictionary. You must submit your Makefile with your assignment.

Hints:

• If you haven’t used make before, try it on simple programs first. If it doesn’t work, read     the error messages carefully. A common problem in compiling multifile executables  is in the included header files. Note also that the whitespace before the command is a tab, and not multiple spaces.

•  It is not a good idea to code your program as a single file and then try to break it down    into multiple files. Start by using multiple files, with minimal content, and make      sure they are communicating with each other before starting more serious coding.

Additional Support

Your tutors will be available to help with your assignment during the scheduled workshop times. Questions related to the assignment may be posted on the Ed discussion   forum, using the folder tag Assignments for new posts. You should feel free to       answer other students’ questions if you are confident of your skills.

A tutor will check the discussion forum regularly, and answer some questions, but be         aware that for some questions you will just need to use your judgment and              document your thinking. For example, a question like, “How much data should I use for the experiments?”, will not be answered; you must try out different data and see what makes sense.

If you have questions about your code specifically which you feel would reveal too much of the assignment, feel free to post a private question on the discussion forum.

Plagiarism

This is an individual assignment. The work must be your own work.

While you may discuss your program development, coding problems and experimentation with your classmates, you must not share files, as doing this without proper            attribution is considered plagiarism.

If you have borrowed ideas or taken inspiration from code and you are in doubt about whether it is plagiarism, provide a comment highlighting where you got that     inspiration.

If you refer to published work in the discussion of your experiments, be sure to include a citation to the publication or the web link.

“Borrowing” of someone else’s code without acknowledgment is plagiarism. Plagiarism is  considered a serious offense at the University of Melbourne. You should read the    University code on Academic integrity and details on plagiarism. Make sure you are not plagiarizing, intentionally or unintentionally.

You are also advised that there will be a C programming component (on paper, not on a computer) in the final examination. Students who do not program their own         assignments will be at a disadvantage for this part of the examination.

Late Policy

The late penalty is 10% of the available marks for that project for each day (or part thereof) overdue. Requests for extensions on medical grounds will need to be supported by a medical certificate. Any request received less than 48 hours before the                   assessment date (or after the date!) will generally not be accepted except in the       most extreme circumstances. In general, extensions will not be granted if the

interruption covers less than 10% of the project duration. Remember that        departmental servers are often heavily loaded near project deadlines, and       unexpected outages can occur; these will not be considered as grounds for an extension.

Students who experience difficulties due to personal circumstances are encouraged to      make use of the appropriate University student support services, and to contact the lecturer, at the earliest opportunity.

Finally, we are here to help! There is information about getting help in this subject on the LMS. Frequently asked questions about the project will be answered on Ed.