a) Suppose we have a recursive function defined on a binary tree. The function takes as...

Transcribed Image Text:

a) Suppose we have a recursive function defined on a binary tree. The function takes as input a node in the tree, calls another function BAR that performs some work on the node and then makes a recursive call on its parent, provided it has one. 1: def FOO(u) 2: BAR(u) 3: 4: if u.parent is not empty then FOO(u.parent) Suppose BAR(u) takes O(log n) time to execute. Analyze the time complexity of running Foo from a leaf of a tree with n nodes. b) Solve the following recursion: T(n): = c) We have a set S of line segments on the real line (all having distinct length) and we want to pick a set TCS of these line segments such that every segment s; in S is covered by the union of the segments in T. In other words, T is a covering of S if the union of all segments in T is the union of all segments in S. Example: 4: 5: 6: 7: In the example above, we have three line segments: $₁ = [0,4], $2 = [0,2], and $3 [3,4]. The smallest cover T contains only $₁. Picking s₁ and any other line segment is still a cover, but not the smallest one. Not picking s₁ results in T not covering every line segment in S, since s₁ is not fully covered. [T(n) = 4T(n/2) +0(n) for n >1 (0(1) for n = 1 $1 Construct a counterexample to show that the following algorithm doesn't com- pute the smallest set T: Sort the line segments in S by their length in decreasing order. For every segment si, if s; isn't covered by T, we add s; to T. 1: def SMALLESTCOVER(S) 2: 3: for i T← [] Sort S by the length of the segments in decreasing order and renum- ber such that |s1| ≥ |$2| ≥ ... ≥ |Sn| 1; i a) Suppose we have a recursive function defined on a binary tree. The function takes as input a node in the tree, calls another function BAR that performs some work on the node and then makes a recursive call on its parent, provided it has one. 1: def FOO(u) 2: BAR(u) 3: 4: if u.parent is not empty then FOO(u.parent) Suppose BAR(u) takes O(log n) time to execute. Analyze the time complexity of running Foo from a leaf of a tree with n nodes. b) Solve the following recursion: T(n): = c) We have a set S of line segments on the real line (all having distinct length) and we want to pick a set TCS of these line segments such that every segment s; in S is covered by the union of the segments in T. In other words, T is a covering of S if the union of all segments in T is the union of all segments in S. Example: 4: 5: 6: 7: In the example above, we have three line segments: $₁ = [0,4], $2 = [0,2], and $3 [3,4]. The smallest cover T contains only $₁. Picking s₁ and any other line segment is still a cover, but not the smallest one. Not picking s₁ results in T not covering every line segment in S, since s₁ is not fully covered. [T(n) = 4T(n/2) +0(n) for n >1 (0(1) for n = 1 $1 Construct a counterexample to show that the following algorithm doesn't com- pute the smallest set T: Sort the line segments in S by their length in decreasing order. For every segment si, if s; isn't covered by T, we add s; to T. 1: def SMALLESTCOVER(S) 2: 3: for i T← [] Sort S by the length of the segments in decreasing order and renum- ber such that |s1| ≥ |$2| ≥ ... ≥ |Sn| 1; i

Answer rating: 100% (QA)

solution Ansa def Foo u Bar u then is not emply then uparent is not empty Foo uparent urual game Xa... View the full answer