Homework Assignment # 2

Binary Search Trees

Due : March 17, 2003 Noon

Warning

Description

Your second assignment is to write a C, C++, Fortran, or Fortran 90 code to create fast search algorithm for two dimensional data based on the methods defined in lecture 3. This assignment is for individual students, not for groups.

Objectives

• implemented several recursive algorithms
• applied good programming technques to a code of moderate complexity
• learned how to use tree data structures for searches

Specifics

You must use C, C++, Fortran, or Fortran 90 for this program. You may use any available sort routine and the Standard Template Library for C++, if you wish. Make sure to document where you found the sort routine used in your code as required by the honor code!

• Download the search.tar file from the class website and unpack them in a local directory. (Download search.tar by clicking on the link.
• Define your data type for the points and nodes. The data type should have the positions, the index, max extents, and min extents as discussed in lecture.
• Write a code which reads these files into an array. The format is:
  • line 1 - n = number of rows in the list
  • lines 2 through n+1 have three values each - xposition (real), yposition(real), index (integer) delimited by spaces. (The fortran format used to write the data was (2f12.7,i6).)
  • each data file will have 2^n points. There are three test data sets with sizes 16, 256, 4096.
• Write or implement or find a sort routine which can order points based on their x or y positions, and can sort between a starting and ending index. A word to the wise, you will want to test this to make sure you sort negative and positive numbers correctly. (see the comment in the hints section below) You can use an existing sort routine for this work, but you must document where you found this routine.
• Write a subroutine which finds the maximum dimension (ie x or y) for a set of points with a starting and ending index
• Write a subroutine which uses the previous two routines to divide the domain using orthogonal recursive bisection ORB. You may use recursive subroutine calls for this assignment.
• Once you have debugged the ORB routine, construct a binary tree. You may use the method outlined in lecture 3 for sets of size 2^n. The basic idea we discussed involved a block move of the particle data followed by finding the extends of the nodes from the leaves to the root node. Again, refer to the lecture notes for details.
• Write a walk routine which examines the search radius and the maximum and minimum extents of each node, and determines if it can be excluded from the search. If it cannot be excluded, then go to the daughter nodes and repeat the process until you reach the leaves of the tree. When you reach a leaf, add it to the search list. The acceptance/rejection criteria for the walk is something you will need to carefully think about. If the search radius crosses a corner or an edge, you have to search the node's children.
• Allow the user to pick a search point and a search radius.
• Write a routine which solves the problem using a brute force approach (ie compare all the particles to the search point directly). Show that the search method and direct method give the same results selected cases.
• Write a short one page text report about the project and what you learned doing it. Document where what problems you had and how you solved them.
• When you are done, put a tar file containing the code, its makefile, and your report into a file called "c701hw2.tar" in your public_html directory. Make sure it can be assessed from the web.
• The code must run on the linux machines in SCS.