CPSC 3280 M2-Programming Assignment

CPSC 3280 M2-Programming Assignment
Objective of this assignment:
 To verify empirically Theorem 12.4 (Chapter 12, Textbook) that states:
“The expected height h(n) of a randomly built binary search tree on n distinct keys
is O(lg n).”
What you need to do:
1. (10 points) Implement the Tree-Insert(T,z) operation on a binary search tree.
2. Repeatedly insert n randomly picked numbers in a binary search tree and collect the height h(n)
of the obtained tree. h(n) is the height of the binary search tree containing n elements. For
simplicity, no need to enforce that the keys are distinct. In other words, you do need to check
whether a number is already in the tree.
3. (60 points = (20 points per function/plot)) Plot on three separate graphs the plots of the functions
h(n)
lg(n)
,
h(n)
n√n
, and
h(n)
nlg(n)
versus n.
4. (30 points: 10 points per plot) Discuss the three plots and conclude regarding the asymptotic
growth of h(n). Decide whether your measurements confirm Theorem 12.4.
Objective:
The objective of this programming assignment is to verify empirically Theorem 12.4 that
states that “the expected height of a randomly built binary search tree on n distinct keys is O(lg
n).”
In order to conduct this experiment, you must implement in your preferred language
(available on Tux Machines) the Tree-Insert(T,z) operation. Below, I explain in pseudocode the
program you must write to collect data and verify Theorem 12.4. You do not need to enforce that
the keys are distinct.
Program to implement
collectData()
for n = 250 to 20,000 by 250 // 250, 500, 750, 1,000, …. 20,000
sum_heightn = 0
for j = 1 to 5 do //Take 5 measurements mj for j=1 to 5
 for i = 1 to n
 pick randomly a number p in the range [0-40,000]
create a node z
set z.key = p
 Tree-Insert(T,z)
 Measure the height hj of the tree
 Discard Tree (free memory)
 sum_heightn += hj
collect Height(n)= sum_heightn/5 // Average height for n
Write in a file F the value n and Height(n)
Data Analysis
Use any plotting software (e.g., Excel) to plot the functions h(n)
lg(n)
,
h(n)
n√n
, and h(n)
nlg(n)
 where h(n) is the
value Height(n) you collected in File F. File F is the file produced by the program you implemented.
Discuss your results based on the plots. Decide whether Theorem 12.4 (Chapter 12, Textbook) is correct.
This theorem states “The expected height h(n) of a randomly built binary search tree on n distinct keys is
O(lg n).”
CPSC 3280 M2-Programming Assignment
Start inserting your answers on the next page
>>>>>>>>>>>>>>>>>>>>
CPSC 3280 M2-Programming Assignment
Start Answering On This Page Where Indicated In Blue:
1. (10 points) Implement the Tree-Insert(T,z) operation on a binary search tree.
Insert here a snapshot of your implemented Tree-Insert(T,z) method in your preferred language...
2. Repeatedly insert n randomly picked numbers in a binary search tree and collect the height h(n).
h(n) is the height of the binary search tree containing n elements. For simplicity, no need to
enforce that the keys are distinct. In other words, you do need to check whether a number is
already in the tree.
Submit/Attach your program CollectData (to collect data) separately on Canvas for this assignment.
The program is your implementation of the pseudocode provided above to collect data. You can use
any language as long as it is already available on Engineering Unix Tux machines. Include here the
directives to compile and execute your program CollectData.
3. (60 points (20 points per function/plot)) Plot on three separate graphs the same plot of the
functions h(n)
lg(n)
,
h(n)
n√n
, and h(n)
nlg(n)
versus n.
Insert here the plot for h(n)
lg(n)
 ........
Insert here the plot for h(n)
n√n
 ........
Insert here the plot for h(n)
nlg(n)
 ........
4. (30 points: 10 points per plot) Discuss the three plots and conclude regarding the asymptotic
growth of h(n). Decide whether your measurements confirm Theorem 12.4.
Discuss here the plot h(n)
lg(n)
 ........
Discuss here the plot h(n)
n√n
 ........
Discuss here the plot h(n)
nlg(n)
 ........
Conclude the validity of Theorem 12.4
CPSC 3280 M2-Programming Assignment
Report
 Insert your answers where indicated. This file with your inserted answers will contain, explain, and
discuss the plots.
 In addition, the above report (this file) must contain the following information:
o whether your data collection program works or not (this must be just ONE sentence)
o the directions to compile and execute your program
 Good writing is expected.
 Recall that answers must be well written, documented, justified, and presented to get full credit.

What you need to turn in:
 Electronic copy of your source data collection program (separately attached to this assignment)
 Electronic copy of this file (including your inserted answers) (separately attached). Submit the file
as a Microsoft Word or PDF file.
Grading
 See points distribution with questions/tasks.