-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathQuestions.txt
86 lines (60 loc) · 3.22 KB
/
Questions.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/*******************************************************************************
File: Questions.txt
Author: Yi Shen
<your partner's name and CS login, if pair programming>
Completion Date: <date you completed this source file>
Course: CS 367, Spring 2016
*******************************************************************************/
Directions: answer the following six (6) questions.
1) Before running your program, what is the worst complexity of building tree for
ArrayList, Binary Search Tree, Binary Search Tree with a small positive
rebalance factor(e.g 2) and RBTree?
Answer: For arrayList, it's O(1), BST: O(N). BST with small rebalance factor: O(NlogN), RBTree: O(logN)
2) Before running your program, what is the worst complexity of contains search for
ArrayList, Binary Search Tree, Binary Search Tree with a small positive
rebalance factor(e.g 2) and RBTree?
Answer: ArrayList: O(N). BST:O(N). BST balanced: O(logN). RBTree: O(logN)
3) Before running your program, what is the worst complexity of range search for
ArrayList, Binary Search Tree, Binary Search Tree with a small positive
rebalance factor(e.g 2) and RBTree? Assume the range is small. Assume the result of
range search contains K elements.
Answer: ArrayList: O(N). BST: O(N). BST balanced: O(logN). RBTree: O(logN)
For questions 4 - 6, you should use the Evaluator program as written.
4) In this question you will run the program using the parameters
indicated below:
random_1000.txt 10 2 3
a)For random data, what are the rankings (from fastest to slowest) for the four
data structures based on the mean time of building a tree, contains search, and range
search?
Build tree: ArrayList < RBTree ~= BSTree < BSTBalanced
Contains: BSTreeBalanced< BSTree~=RBTree< ArrayList
Range: BSTree Balanced< BSTree <= RBTree < ArrayList
b)What about for the sorted data?
Answer:
BuildTree: ArrayList <RBTree < BSTree < BalancedBST
Contains: BSTreeBalanced <= RBTree < ArrayList < BSTree
Range: BSTreeBalanced < RBTree < ArrayList < BSTree
5) In this question you will run the program using the parameters
indicated below:
random_10000.txt 10 2 3
a)Does the ranking change for the larger data set on random data and sorted data?
b)Which data structure has the largest growth rate function? Explain your answers in terms
of building tree, contains search and range search for random data and sorted data.
Answer:
a. The ranking is still the same (similar).
b. Largest GRF: Random: Building tree: BalancedBST
Contains: ArrayList
Range: ArrayList
Sorted: Building: BSTBalanced
Contains: ArrayList/BSTree
Range: BSTree
6) In this question you will run the program using the parameters
indicated below:
random_1000.txt 10 2 3
random_1000.txt 10 5 3
random_1000.txt 10 10 3
Briefly explain how the rebalanceThreshold effects the time for building tree, contains search
and range search.
Answer: Higher threshold will reduce the time it takes to build Balanced BSTree
contains: Smaller threshold will reduce the time to check contains.
Range: Small threshold will have less time to do range search.