Refer tо Figure 6. Nаme the blооd vessel lаbeled #32 on this figure:
Whаt vаriаtiоn оf elevatоr is commonly employed to remove stubborn or broken root tips?
Questiоn 1, Binаry Trees (12 pоints) Use the fоllowing binаry tree for this problem: (а) [2 points] Annotate the nodes of the tree with indices corresponding to the order in which they're visited during a pre-order traversal. (b) [2 points] For each node, compute the current AVL balancing factor and indicate whether the node is balanced. (c) [4 points] Treating the tree as an AVL tree, remove the node with value 70. Show the tree immediately after delection and after balancing, and describe any steps necessary to rebalance. (d) [4 points] Insert a new node with value 15 from the original tree (NOT the one from part c!). As before, show the tree immediately after insertion and after balancing, and describe any steps necessary to rebalance. Question 2, Graph Applications (12 points) Countries have different exchange rates for converting between their currencies. These rates are not necessarily transitive, meaning that if the exchange rate for currency A to B is ( R_1 ) and the rate from B to C is ( R_2 ), the rate from A to C need not be ( R_1 R_2 ). Likewise, the rate from B to A need not be ( R_1^{-1} ). This opens up the possibility of arbitrage, in which these exchange rates are exploited to turn a profit. For example, suppose that 1 U.S. dollar buys 75 Indian rupees, 1 Indian rupee buys 1.5 Japanese yen, and 1 Japanese yen buys 0.009 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy ( 75 text{ (rupees)} times 1.5 text{ (yen)} times 0.009 text{ (dollars)} = 1.0125 ) U.S. dollars, thus turning a profit of 1.25 percent. In this problem, you will develop an algorithm to identify whether and how this system can be exploited to turn a profit. (a) (2 points) The table below shows the exchange rates between currencies {A,B,C,D,E}. Treating the table as an adjacency matrix, draw the graph it represents. (b) (2 points) Are there any opportunities for arbitrage on your graph from part (a)? If so, identify a profitable sequence of trades. What does this sequence correspond to on the graph? (c) (4 points) Write pseudocode for an algorithm that, given a graph of exchange rates, identifies whether or not arbitrage is possible. If you use an algorithm we discussed in class as a subroutine, make sure to include the pseudocode for that algorithm. Hint: You may find the following facts helpful for converting multiplication to addition: (log(ab) = log a + log b) and (log 1 = 0). (d) (2 points) Describe how to modify your algorithm from part (c) to additionally output a profitable sequence of exchanges for arbitrage. (e) (2 points) What is the time and auxiliary space complexity for your solutions to parts (c) and (d)? Question 3, Recursion and Dynamic Programming (15 points) In this problem, you will develop an AI that can play a game of coins. The game starts with a pile of (N) coins, and two players take turns removing one, two, or three coins from the pile. The player who removes the last coin wins. An example run of the game is shown below, played between Alice and Bob, with (N = 5): Alice removes one coin, leaving four in the pile Bob removes two coins, leaving two in the pile Alice removes the final two coins and wins the game For a particular (N), we say that Alice is guaranteed a win if, when she goes first, there is some sequence of moves she can make such that she wins no matter what moves Bob makes. For example, Alice is guaranteed a win for (N = 5), and the game above demonstrates such a sequence of moves. Take a moment to convince yourself that there is nothing Bob could have done to win. (a) [2 points] Is Alice guaranteed a win for (N = 6)? Why or why not? (b) [4 points] Write the pseudocode for a recursive algorithm that takes (N) as an input and returns whether Alice is guaranteed a win for that particular (N) by enumerating every possible sequence of moves made by Alice and Bob. (c) [3 points] Express the time complexity of your pseudocode above in terms of a recurrence relation. (Note: you may elect to express it as a pair of mutually recursive relations instead). (d) [2 points] Compute an upper bound on the time complexity for your pseuducode from part (b) using your recurrence relation from part (c). Express the upper bound in big-(O) notation. Your upper bound does not need to be tight, but should be reasonable. Hint: you will likely need to slightly modify your recurrence relation to apply one of the formulas. If none of the formulas apply to your recurrence relation, justify why. (e) [1 points] Characterize the subproblems and use this to determine the time complexity of a hypothetical memoized version of your algorithm from (b). (f) [3 points] Describe an algorithm that uses bottom-up dynamic programming to achieve this time complexity. You do not need to write pseudocode, but your description should include, at minimum, the layout of the table, an appropriate bottom-up schedule, and the update rule. Question 4: Dijkstra's Algorithm and A* (16 points) In the following graph, vertex (0) is the source and vertex (4) is the target. (a) [2 points] In what order does Dijkstra's algorithm visit the vertices of the above graph? (b) [3 points] Show the distance and predecessor tables that result from running Dijkstra's in part (a). (c) [3 points] Consider the two heuristic functions (h_1) and (h_2) displayed below. Which, if any, are admissible for the graph shown above? Justify your answer. (d) [6 points] Run the A* algorithm twice on the graph above, once using the heuristic (h_1) and once using (h_2). What path from (0to 4) does each run output? What is the length of each path? (e) [2 points] For each of the following heuristics below, indicate whether or not it is admissible. Justify your answers. (i) (h_1(v) =) the weight of the largest edge leaving (v) (ii) (h_2(v) = ) the weight of the smallest edge leaving (v) (III) (h_3(v) = ) the length of the longest path from (vto t) Question 5, Hashmaps (10 points) Consider a hashmap that uses chaining for collision resolution. (a) [1 point] If the hashmap has 10 buckets and uses a hash function (h(k) = kbmod 10), what is the load factor after inserting 15 distinct keys? (b) [1 point] Describe the complexity of searching for a key in the hashmap in terms of the load factor (alpha). (c) [2 point] Draw the hashmap after inserting the keys (10, 11, 12, 22, 23, 32) in that order. (d) [2 point] Consider a resizing policy that doubles the size of the hashmap when the load factor reaches a certain threshold, and rehashes and inserts all the keys into the new hashmap. If (m) is the original size and (alpha) is the load factor threshold, what is the complexity of a single resize operation? (e) [4 point] Describe the overall complexity of inserting (N) elements, including resizing costs, where (N) is much larger than the original size (m). You do not need to express your answer in a closed form, but you must show your work. Congratulations, you are almost done with this exam. DO NOT end the Honorlock session until you have submitted your work to Gradescope. When you have answered all questions: Use your smartphone to scan your answer sheet and save the scan as a PDF. Make sure your scan is clear and legible. Submit your PDF to Gradescope as follows: Final Exam Email your PDF to yourself or save it to the cloud (Google Drive, etc.). Click this link to go to Gradescope to submit your work: Return to this window and click the button below to agree to the honor statement. Click Submit Quiz to end the exam. End the Honorlock session.