Save Time On Research and Writing

Hire a Pro to Write You a 100% Plagiarism-Free Paper.

Get My Paper
## Assignment 2

### Instructions

According to our suggested 16 week “Course Schedule,” you should complete and submit Assignment 2 by the Sunday at the end of Week 6. This assignment is worth 10% of your final grade. To receive full marks, answer each of the following questions in a clear and comprehensive manner. You can find the assignment marking criteria at the end of this document.

### Questions

1. Show that if *f*(*n*) is *O*(*h*(*n*)) and *g*(*n*) is *O*(i(*n*)), then *f*(*n*) + *g*(*n*) is *O*(*h*(*n*) + i(n)).

[2 marks]

2. Show that 3(*n *+ 1)7 + 2*n *log *n *is *O*(*n*7). **Hint:** Try applying the rules of Theorem 1.7. You will have to use the insert equations to answer this question. [2 marks]

Save Time On Research and Writing

Hire a Pro to Write You a 100% Plagiarism-Free Paper.

Get My Paper
3. Give an *O*(*n*)-time algorithm for computing the depth of each node of a tree *T*, where *n *is the number of nodes of *T*. Assume the existence of methods setDepth (*v*,*d*) and getDepth(*v*) that run in *O*(1) time. [2 marks]

4. What does the following algorithm do? Analyze its worst-case running time and express it using “Big-Oh” notation. [2 marks]

**Algorithm** Foo *(a,n):*

*Input*: two integers, *a* and *n*

*Outpu*t: ?

*k* ß 0

*b* ß 1

**while** *k* < *n* **do**

*k* ß*k + 1*

*b* ß* b* **a*

**return** *b*

5. a. Describe (in pseudo-code) a findAll Elements (*k*) method of an AVL tree *T*. It should run in *O*(logn + *s*) time where *n* is the size of *T* and *s* is the number of elements returned (i.e., the number of nodes in *T* whose key is *k*).

b. Analyze the running time of your algorithm.

[2 marks]

### Marking Criteria for Assignments

You will be awarded full marks if your answer adequately answers the question addressed.

Total marks = 10

You will be awarded partial marks if your answer demonstrates:

· Application of the major and alternative approaches, methods, or algorithms to solve the problem.

· Evidence of appropriate logic.

· Evidence of correct computational skills and data structures.

· Inclusion of appropriate comments or explanations.

For details about how to submit this assignment, refer to the “Assignment Submission Instructions” under the Assignments Overview tab of your course.