please see the attached file below
CIS 350/3501 Summer 2022 Data Structures and Algorithm Analysis Homework # 1 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).