/* ***************************************************************************** * 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 PointST implementation * perform per second for input1M.txt (1 million points), where the query * points are random points in the unit square? * * Show the raw data you used to determine the operations per second. * Use at least 1 second of CPU time for each data point. * (Do not count the time to read in the points or to build the 2d-tree.) * * Repeat the question but with your KdTreeST implementation. * * Fill in the table below, using one digit after the decimal point * for each entry. **************************************************************************** */ calls to CPU time calls to nearest() nearest() (seconds) per second ------------------------------------------------------ PointST: KdTreeST: /* ***************************************************************************** * Did you fill out the mid-semester feedback form? * If not, please do so now: https://goo.gl/forms/btvmRqdo0WaxsPhs2 **************************************************************************** */ /* ***************************************************************************** * 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. **************************************************************************** */