A rooted tree T is static and contains n nodes. Among the edges from a node to its children, exactly one of them is solid. The others are dashed. The choice of which child is solid may change over time. A sequence of FindRoot() operations are done, as described here: FindRoot(x): The path from x to the root of the tree is followed. Whenever a dashed edge is encountered a cost of one is incurred by the algorithm. Before, during, or at end of this process the algorithm is allowed to change which is the solid edge from any node to its children. The cost of each switch is one. The Greedy implementation of the FindRoot(x) algorithm switches all the dashed edges on the path to solid at the beginning of the FindRoot, so its cost is just one for each dashed edge on the path from x to the root. The Omniscent algorithm is smarter. It can make decisions about which edges to flip based on the future as well as past FindRoots. The Static algorithm must make its choices of which edges are to be dashed and which are to be solid at the very beginning of the FindRoot sequence, and then never changes these choices. (a) Assuming that Omniscent and Greedy both start with the same tree and same arrangement of solid and dashed edges, prove that Greedy is always at most a factor of 2 more expensive than Omniscent. (I.e. Greedy is 2-competitive.) Use a potential function. (b) Give a strategy for Static such that any FindRoot costs it at most log2 n. Note that these two parts together show that Greedy costs at most 2 log n amortized per FindRoot. A rooted tree T is static and contains n nodes. Among the edges from a node to its children, exactly one of them is solid. The others are dashed. The choice of which child is solid may change over time. A sequence of FindRoot() operations are done, as described here: FindRoot(x): The path from x to the root of the tree is followed. Whenever a dashed edge is encountered a cost of one is incurred by the algorithm. Before, during, or at end of this process the algorithm is allowed to change which is the solid edge from any node to its children. The cost of each switch is one. The Greedy implementation of the FindRoot(x) algorithm switches all the dashed edges on the path to solid at the beginning of the FindRoot, so its cost is just one for each dashed edge on the path from x to the root. The Omniscent algorithm is smarter. It can make decisions about which edges to flip based on the future as well as past FindRoots. The Static algorithm must make its choices of which edges are to be dashed and which are to be solid at the very beginning of the FindRoot sequence, and then never changes these choices. (a) Assuming that Omniscent and Greedy both start with the same tree and same arrangement of solid and dashed edges, prove that Greedy is always at most a factor of 2 more expensive than Omniscent. (I.e. Greedy is 2-competitive.) Use a potential function. (b) Give a strategy for Static such that any FindRoot costs it at most log2 n. Note that these two parts together show that Greedy costs at most 2 log n amortized per FindRoot