Problem 1 [38 pts;, (16,7,3,12)]: Comparisons of Functions In the problems that follow, you will compare three algorithms for search that we discussed in class: Ordered-Linear-Search, Chunk-Search, and Binary-Search. Let T1(n), T2(n), and T3(n), respectively, be the number of element examinations1 required by these algorithms when run on a list whose length is n. Ignoring floors, ceilings, and lower order terms, we have T1(n) = n T2(n) = 2v n T3(n) = log2 (n). In each of the following parts, you must show your work, otherwise you will lose points. i. On a single sheet of graph paper, plot the number of element examinations required for each of the three algorithms when run on lists of length n = 1, 2, 4, 8, 16, 32, and 64. For each algorithm, connect the plot points with a smooth, hand-drawn curve. See the plots given in the “Exponentials and Logs” appendix of the text for examples of what you should do. Your graphs must be neat and labeled and on a reasonable scale to show the functions over the given range of n. You may print a piece of graph paper from the PDF located at the following URL: http://www.printfreegraphpaper.com/ (If you view this assignment on-line, you may simply click on the above hyperlink.) 1worst-case. . . 1 ii. Suppose that you were given a budget of 20 element examinations. For each of the three algorithms, determine the largest array length such that the number of element examinations made is guaranteed to be at most 20. iii. How many times larger is the array that Binary-Search can handle, as compared to the arrays that Chunk-Search and Ordered-Linear-Search can handle? How many times larger is the array that Chunk-Search can handle, as compared to the array that Ordered-Linear-Search can handle? Solve both for the case of 20 and the general case of a budget of B. iv. Suppose you are running the three algorithms on three different computers. The computer running Ordered-Linear-Search is 4 times faster than the one running Chunk-Search and the computer running Chunk-Search is 4 times faster than the one running Binary-Search. How large must the list be before the computer running Binary-Search begins to outperform the one running Chunk-Search? How large must the list be before the computer running Chunk-Search begins to outperform the one running Ordered-Linear-Search? (Hint: For each of the two questions, you can write an equation that indicates that the running times of the two algorithms being compared are equal, taking into account the speeds of the computers on which the algorithms are being run. These equations may involve n (or v n) and log2 n, and in general cannot be solved analytically. You can solve the two equations, however, by either plotting the relevant functions and seeing where they meet, or by comparing the running times for various values of the list size using binary search. See Exercise 9.3 on pages 128 and 129 of the text for more hints on solving such equations.) Problem 2 [30 pts; 15 each] Mathematical Induction i. Prove by induction that for all integers n = 1: (x + y) n = Xn i=0 n i x n-i y i . ii. A tromino is an L-shaped tile formed by three adjacent squares of a chessboard. We say that an arrangement of trominoes is a tiling of a chessboard if it exactly covers all the squares of the chessboard without overlap. Prove by induction that every 6n × 6 n chessboard can be tiled with trominoes, for all integers n = 1. Problem 3 [32 pts, (4 each)]: Graphs A (simple) digraph consists of a set of vertices V and a set of directed edges or arcs A. Let V1 = {a, b}, i.e., a set of two vertices labeled a and b. Now consider all (simple) digraphs which can be formed from these two vertices; one obtains different digraphs by having different sets of edges. i. Draw all possible digraphs that can be constructed from the vertices V1 = {a, b}. 2 ii. How many such digraphs have no arcs? How many such digraphs have exactly one arc? How many such digraphs have exactly two arcs? How many total digraphs are there? Now consider a vertex set of size 3, V2 = {a, b, c}. iii. How many possible arcs exist over V2? iv. How many unique digraphs can be constructed from V2? Hint: In any such graph, each arc is either present or absent. v. How many unique digraphs can be constructed from V2 with exactly three directed arcs? Hint: One must choose where to place the three directed arcs. . . Now generalize these results for a vertex set of size n, i.e., V3 = {a, b, c, . . .} where |V3| = n. vi. How many possible arcs exist over V3? Justify your answer. vii. How many unique digraphs can be constructed from V3? Justify your answer. viii. How many unique digraphs can be constructed from V3 using exactly k arcs? Justify your answer.