Select Page

Assignment 2
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.
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 + 2n log n is O(n7). Hint: Try applying the rules of Theorem 1.7. You will have to use the insert equations to answer this question. [2 marks]
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
Output: ?
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.