# please see the attached file below

## Place your order today and enjoy professional academic writing services—From simple class assignments to dissertations. Give us a chance to impress you.

Order a Similar Paper Order a Different Paper

please see the attached file below

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).

# When writing your assignment, we aim to help you get an A, not just beat the deadline.

### Save your time - order a paper!

Get your paper written from scratch within the tight deadline. Our service is a reliable solution to all your troubles. Place an order on any task and we will take care of it. You won’t have to worry about the quality and deadlines

Order Paper NowOrder a Similar Paper Order a Different Paper