Data Structures| Computer Science
Collaboration policy: The goal of homework is to give you practice in mastering the course material. Consequently, you are encouraged to collab- orate with others (groups of at most three). In fact, students who form study groups generally do better on exams than do students who work alone. If you do work in a study group, however, you owe it to yourself and your group to be prepared for your study group meeting. Specifically, you should spend at least 30–45 minutes trying to solve each problem beforehand. If your group is unable to solve a problem, it is your responsibility to get help from the instructor before the assignment is due. You must write up each problem solution and/or code any programming assignment by yourself without assistance, even if you collaborate with others to solve the problem. You are asked to identify your collaborators. If you did not work with anyone, you must write “Collaborators: none.” If you obtain a solution through research (e.g., on the web), acknowledge your source, but write up the solution in your own words. It is a violation of this pol- icy to submit a problem solution that you cannot orally explain to the instructor. No other student may use your solutions; this includes your writing, code, tests, documentation, etc. It is a violation of this policy to permit anyone other than the instructor and yourself read-access to the location where you keep your solutions.
1
Submission Guidelines: Your group has to submit your work on Black- board by the due date. Only one submission per group is necessary. Just make sure that you identify your group in the header by putting all names in the “author” field. For each of the program- ming assignments you must use the header template provided in Blackboard. The header must contain, your name, course number, semester, homework number, problem number, and list of collaborators (if any, otherwise put “none”). Your answers to questions that do not require coding must be in- cluded in this header as well. Your code must follow the Java formatting standards posted in Blackboard. Format will also be part of your grade. To complete your submission, you have to upload two files to Blackboard: your source file and your class file. The submission will be returned without grading if any of these guidelines is not followed.
Style and Correctness: Keep in mind that your goal is to communi- cate. Full credit will be given only to the correct solution which is described clearly. Convoluted and obtuse descriptions might receive low marks, even when they are correct. Also, aim for concise solutions, as it will save you time spent on write-ups, and also help you conceptualize the key idea of the problem.
2
Assignment 4
Programming Assignment Grading Rubric: The following rubric applies only to the programming assignment.
Program characteristic
Program feature Credit possible
Part 2
Design 30%
Algorithm 30%
Functionality 30%
Program runs without errors
20%
Correct result given 10%
Input 15%
User friendly, typos, spacing
10%
Values read in correctly
5%
Output 15%
Output provided 10%
Proper spelling, spacing, user friendly
5%
Format 10%
Documentation: name, collaborators, header, etc.
5%
Clarity: comments, indentation, etc.
5%
TOTAL 100%
1(20) 2(60) 3(20) TOTAL(100)
3
Assignment: The way that data is stored in a Binary Search Tree (BST) depends
on the order in which the values are inserted. For example, if we insert the numbers 1, 2, 3 in that order, the resulting tree has 1 in the root, 2 as a right child of the root, and 3 as a right child of 2. However, if we insert first 2, then 2 will be stored in the root, and 1 and 3 will be the left and right child of the root respectively. Moreover, not only the values are stored in different places but also the shape of the tree obtained is different. The first one is skewed whereas the second one is balanced. As a consequence, although both trees contain the same data, the worst-case cost of searching differs. The purpose of this homework is to highlight this striking difference in running time, creating a skewed BST and a (roughly) balanced BST, both with a large number of nodes, and measuring the execution time of searching on each.
1. (20 points) Estimate the asymptotic running time of searching in a skewed BST and a balanced BST. Justify your conjecture explaining which operations of the BinarySearchTree class (attached) you would use, and explain how do you obtain the overall running time from the running times of those operations. You can use asymptotic notation (big-O).
2. (60 points) Write a program to do the following.
• Input an integer x. (Should work with “big” numbers.) • Create a completely-skewed BST S containing 1, 2, . . . , x. • Create a BST R containing x integers without repetitions gen-
erated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by a big number.) Given that the numbers are generated uniformly at random, the tree will likely be balanced.
• Measure the time to search in S for a number that is not in the tree.
• Measure the time to search in R for a new random number. • Display the time taken for each search.
4
Fill in a chart like the following with the times in nanoseconds mea- sured. You may need to adjust the values of n according to your plat- form. That is, if your program takes too long to complete, or if you run out of memory, etc., reduce the range of n as needed. Your chart must have enough cells filled to be able to answer the following question.
n = 103 n = 104 n = 105 n = 106
Skewed BST Balanced BST
3. (20 points) How the results obtained compare with your conjecture? If the results differ from your conjecture, investigate the reason by looking carefully at the code of the BinarySearchTree class, and explain what happened.
4. Extra credit: Carry out the same experiments on the Java API class TreeMap. Compare the measurements with the skewed tree and random tree. Argue why the running time functions observed are (roughly) equal/different .
