ECE665 Solutions for Homework 2 Spring LATEST UPDATE Arizona State UniversityECE 665hw2_sol.QUESTIONS AND VERIFIED ANSWERS.

Document Content and Description Below

ECE665 { Solutions for Homework 2 { Spring 2017 C-2.2 (15’) Question: Describe how to implement the queue ADT using two stacks, so that the amortized running time for dequeue and dequeue is O(1),... assuming that the stacks support constant time push, pop, and size methods. What is the running time of the dequeue() and dequeue() methods in this case? Solution: Name the two sta'... Question: Two ordered trees T0 and T" are said to be isomorphic if one of the following holds: • Both T0 and T" consist of a single node • Both T0 and T" have the same number k of subtrees, and the ith subtree of T0 is isomorphic to the ith subtree of T", for i = 1; :::; k. Design an algorithm that tests whether two given ordered trees are isomorphic. What is the running time of your algorithm? Solution: According to the definition of isomorphic, the algorithm starts from the root nodes of two given tree T0 an...... Input: two root nodes root1 and root2 from two given trees T0 and T" Output: whether two tree are isomorphic 1: if root1 and root2 are external nodes then 2: return true; 3: else if the number of the children for root1 and root2 are different then 4: return false; 5: end if 6: for each pair of children ch1i and ch2i at position i do 7: if checkIsomorphic(ch1i; ch2i) is false then 8: return false; 9: end if 10: end for 11: return true; End Algorithm 1 Since each pair of the tree nodes have been visited once, the total running time of the algorithm is O(n). n is the smaller number of nodes in the tree T0 and T". C-2.19 (15’) Question: The path length of a tree T is the sum of the depths of all the nodes in T. Describe a linear-time method for computing the path length of a tree T (which is not necessarily binary). Input: the current node, the depth of the current node. Output: current path length 1: if current is null then 2: return 0; 3: end if 4: pLen = depth; // add the depth of the current node 5: for each child ch of current do 6: pLen += pathLen(ch; depth + 1) 7: end for 8: return pLen End Algorithm Each node in the tree T has been visit once and only one add operation is performed. So the running time is O(jV j) which is proportional to the number of nodes jV j. C-2.28 (15’) Question: Show that, for any n, there is a sequence of insertions in a heap that requires Ω(n log n) time to process. Solution: Considering a s... Question: Develop an algorithm that computes the kth smallest element of a set of n distinct integers in O(n + k log n) time. Solution: Construct a heap, which takes O(n) time. Then call removeMinElement k times, which takes O(k log n) time. C-3.4 (15’) Question: Describe how to perform the operation removeAllElements(k) in an ordered dictionary implemented with a binary search tree T, and show that this method runs in time O(h + s), where h is the height of T and s is the size of the iterator returned. [Show More]

Last updated: 1 year ago

Preview 1 out of 4 pages