4 discrete math problems

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 T₁(n), T₂(n), and T₃(n), respectively, be the number of element examinations¹ required by these algorithms when run on a list whose length is n. Ignoring oors, ceilings, and lower order terms, we have

^T1^{(n) = n}_p

T₂(n) = 2 n

T₃(n) = log₂(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.)

¹worst-case. . .

1

ii.Suppose that you were given a budget of 20 element examinations. For each of the threealgorithms, 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 thatBinary-Searchcan handle, as compared tothe 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 di erent computers. The computerrunning 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 outper-form 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 p

computers on which the algorithms are being run. These equations may involve n (or n) and log₂ 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 integersn 1:

n		n	xn iyi:
(x + y)n =i=0
i
X

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 6ⁿ 6ⁿ 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 V₁ = fa; bg, 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 di erent digraphs by having di erent sets of edges.

i.Draw all possible digraphs that can be constructed from the verticesV₁=fa;bg.

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, V₂ = fa; b; cg.

iii. How many possible arcs exist over V₂?

iv. How many unique digraphs can be constructed from V₂? Hint: In any such graph, each arc is either present or absent.

v. How many unique digraphs can be constructed from V₂ 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., V₃ = fa; b; c; : : :g where jV₃j = n.

vi. How many possible arcs exist over V₃? Justify your answer.

vii. How many unique digraphs can be constructed from V₃? Justify your answer.

viii. How many unique digraphs can be constructed from V₃ using exactly k arcs? Justify your answer.

Problem 4 [25 pts, (8,8,9)]: Recurrences ***EXTRA CREDIT***

In each of the following problems, solve the recurrence using the method described in class and in the text. You must show your work, otherwise you will lose points.

Assume a base case of T (1) = 1. As part of your solution, you will need to establish a pattern for what the recurrence looks like after the k-th iteration. For this assignment, you need not formally prove that your patterns are correct via induction, though you will lose points if your patterns are not correct. Your solutions may involve n raised to a power and/or logarithms of n. For example, a solution of the form 8^log2n is unacceptable; this should be simpli ed as n^log28 = n³.

i. T (n) = T (n 1) + n².

ii. T (n) = 4 T (n=2) + 2n.

iii. T (n) = 9 T (n=3) + n².

3