please see the attached file
CIS 350/3501 Summer 2022 Data Structures and Algorithm Analysis
Homework # 1
Due: 5/21/2022
Total points: 90
Note, this is an individual homework assignment.
Submission instruction:
Upload your homework as a single WORD or PDF file to Canvas under the Assignment “HW1” folder.
Problem 1 (10 points)
Order the following functions by growth rate: √N, N, 2/N, 2N , N3, N logN, N log2 N, 37, N2 log N, N1.5, N loglog N, N2, 2N/2, N log(N2). Also, indicate which functions asymptotically grow at the same rate.
Problem 2 (16 points)
For each of the following six program fragment, give an analysis of the running time in Big-Oh notation.
(1) sum = 0;
for(i = 0; i < n; i++)
sum++;
(2) sum = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
sum++;
(3) sum = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n * n; j++)
sum++;
(4) sum = 0;
for(i = 0; i < n; i++)
for(j = 0; j < i; j++)
sum++;
(5) sum = 0;
for(i = 0; i < n; i++)
for(j = 0; j < i * i; j++)
for(k = 0; k < j; k++)
sum++;
(6) sum = 0;
for(i = 1; i < n; i++)
for(j = 1; j < i * i; j++)
if (j % i == 0 )
for(k = 0; k < j; k++)
sum++;
(7)
int sum (int n) {
if n == 1 {
return 1;
}
return n + sum(n-1);
}
(8)
int sum (int n)
{
if (n <= 1 )
return 1;
else
return n + sum((3*n)/5);
}
Problem 3 (9 points)
An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following (assuming low-order terms are negligible)?
Linear
O(NlogN)
Quadratic
Cubic
Problem 4 (10 points)
Show that the maximum number of nodes in a binary tree of height h is 2h+1-1.
Problem 5 (10 points)
Give the prefix (based on the preorder traversal), infix (based on the inorder traversal), and postfix (based on the postorder traversal) expressions corresponding to the following tree:
Problem 6 (10 points)
Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search tree.
Show the result of deleting the root.
Problem 7 (15 points)
Write efficient functions that take only a pointer to the root of a binary tree, T, and compute:
The number of nodes in T.
The number of leaves in T.
The number of full nodes in T.
What is the running time of your functions.
Problem 8 (10 points)
Show how the tree in the figure below is represented using a firstChild/nextSibling link implementation (as described in the PPT lecture 4, slide 17).
