/****************************************************************************** * Name: * NetID: * Precept: * * Partner Name: * Partner NetID: * Partner Precept: * * Hours to complete assignment (optional): * ******************************************************************************/ Programming Assignment 5: Kd-Trees /****************************************************************************** * Describe the Node data type you used to implement the * 2d-tree data structure. *****************************************************************************/ /****************************************************************************** * Describe your method for range search in a kd-tree. *****************************************************************************/ /****************************************************************************** * Describe your method for nearest neighbor search in a kd-tree. *****************************************************************************/ /****************************************************************************** * How many nearest neighbor calculations can your brute-force * implementation perform per second for input100K.txt (100,000 points) * and input1M.txt (1 million points), where the query points are * random points in the unit square? * * Show your work by providing, for each input size (100K and 1M), * how many calls to nearest your timing test made and how much time * it took the test to complete. * (Do not count the time to read in the points or to build the 2d-tree.) * * Repeat the question but with the 2d-tree implementation. *****************************************************************************/ calls to nearest() per second brute force 2d-tree --------------------------------- input100K.txt input1M.txt /****************************************************************************** * Known bugs / limitations. *****************************************************************************/ /****************************************************************************** * Describe whatever help (if any) that you received. * Don't include readings, lectures, and precepts, but do * include any help from people (including course staff, lab TAs, * classmates, and friends) and attribute them by name. *****************************************************************************/ /****************************************************************************** * Describe any serious problems you encountered. *****************************************************************************/ /****************************************************************************** * If you worked with a partner, assert below that you followed * the protocol as described on the assignment page. Give one * sentence explaining what each of you contributed. *****************************************************************************/ /****************************************************************************** * List any other comments here. Feel free to provide any feedback * on how helpful the class meeting was and on how much you learned * from doing the assignment, and whether you enjoyed doing it. *****************************************************************************/