Assignment 4 (11,12 March)

1. Study the possibility of an alternative implementation of the interval search tree using k-d trees. Show the regions of overlap between i=(xi,yi) and j=(xj,yj) on 2-D X-Y graphics. (This was a new idea proposed during the lecture).

2. Develop a data structure to support Min-Gap operation. I.e. find the smallest difference between any pair of values in S. E.g. when S={1,5,9,15,18,22} , Min-Gap would return 3 (18-15=3). Describe efficient versions of Insert, Delete, Search and Min-Gap. Analyze the efficiency of the data structure.

3. Use Union-Find to create a maze. Maze can be retrieved from http://biit.cs.ut.ee/~vilo/edu/2008-09/Algorithmics/maze/ (e.g. maze_50x50.swog is a 50x50 maze). This maze is intended for visualisation using SWOG: http://biit.cs.ut.ee/swog/ Simply copy-paste the maze into the SWOG input field. The files have been created using the maze.pl perl program in that directory.

To create a maze you have to remove a minimal amount of walls (how many exactly?) to make all rooms connected. You can take the printout and remove those lines that need to be removed from the visualisation input file. Yellow is intended to fill the connected white area (I have not tested it on a proper maze). Each room has a nr that you can see by hovering with a mouse over the room.

4. Implement (yourself!) both the division-based hash code and multiplication-based hash code (table size T < 100). For both cases develop one "good" and one "bad" version. Test the goodness of all versions by making a histogram of how the random values (integers) are distributed. As well as develop a strategy to "break" your hash codes - i.e. describe a procedure to generate integers that would all map to the same value.

5. Imagine a unit circle with some radius and values (xi,yi), s.t. xi2+yi2<1 that are distributed evenly across the entire area of the circle. Your task is to sort the points by their distance to origin. To use the bucket sort, design a formula for inserting all points to m equal-area buckets.

6. Bonus (2p): Implement some linear-time sorting algorithm and evaluate it's performance against system-provided sorting mechanisms (e.g. qsort in C). Can you demonstrate convincingly the superiority of your linear-time method to sort 64-bit integers?

edit