CS1800 Discrete Structures Profs. Fell & Sundaram Fall 2012 November 22, 2012 Written Homework 04 Assigned: Thu 22 Nov 2012 Due: Thu 29 Nov 2012 Instructions: • The assignment is due at the beginning...

1 answer below »
CS1800 Discrete Structures Profs. Fell & Sundaram Fall 2012 November 22, 2012 Written Homework 04 Assigned: Thu 22 Nov 2012 Due: Thu 29 Nov 2012 Instructions: • The assignment is due at the beginning of class on the due date specified. Late assignments will be penalized 50%, as stated in the course information sheet. Late assignments will not be accepted after the solutions have been distributed. • We expect that you will study with friends and often work out problem solutions together; however, you must write up you own solutions, in your own words. Cheating will not be tolerated. • We expect your homework to be neat, organized, and legible. If your handwriting is unreadable, please type your solutions. Use 8.5in by 11in loose-leaf or printer paper, and please do not hand in sheets that have been ripped from spiral bound notebooks. 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. 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 8log2 n is unacceptable; this should be simplified as n log2 8 = n 3 . i. T(n) = T(n - 1) + n 2 . ii. T(n) = 4 T(n/2) + 2n. iii. T(n) = 9 T(n/3) + n 2 . 3
Answered Same DayDec 21, 2021

Answer To: CS1800 Discrete Structures Profs. Fell & Sundaram Fall 2012 November 22, 2012 Written Homework 04...

Robert answered on Dec 21 2021
114 Votes
1. Comparison of Functions

The number of element examinations of the ordered linear search, chunk search, and
binary search algorithms are as follows:
 
 
 
1
2
3 2
;
2 ;
log .
T n n
T n n
T n n



i. We wish to plot the number of element examinations of each of these algorithms
on a single graph. Such a
plot is shown below:

ii. For each of the three algorithms listed, we wish to determine the largest array
length maxn such that the number of element examinations,   ,iT n is guaranteed to
be at most 20.
For the ordered linear search algorithm, we have  1 20,T n n  whence
max 20.n 
For the chunk search algorithm, we have  2 2 20,T n n  whence 10n  and
hence 100.n  Thus we have max 100.n 
For the binary search algorithm, we have  3 2log 20,T n n  whence
202 1,048,576n   and hence max 1,048,576.n 
iii. We wish to determine how many times larger an array the binary search algorithm
can handle, as compared to the size of the array that the chunk search and ordered
linear search algorithms can handle, with a budget of B element examinations,
both for 20B  and for general B.

As we have seen in the previous part, for 20B  , the binary search algorithm can
handle an array of size up to 1,048,576, as compared to an array of size up to 100
for chunk search and an array of size up to 20 for ordered linear search. Thus, for
20B  , chunk search can handle an array five times larger than ordered linear
search, and binary search can handle an array 10,485.76 times larger than chunk
search and 52,428.8 times larger than ordered linear search.
For general B, ordered linear search can handle an array of size up to B, while
chunk search can handle an array of size up to 2 / 4B and binary search can
handle an array of size up to 2 .B Thus, chunk search can handle an array / 4B
times larger than ordered linear search, while binary search can handle an array
2 22 /B B times larger than chunk search and 2 /B B times larger than ordered
linear search.
iv. Suppose we are running the ordered linear search algorithm on a Computer A,
which is 4 times faster than Computer B, on which we are running the chunk
search algorithm, which in turn is 4 times faster than Computer C, on which we
are running the binary search algorithm. We wish to determine the minimum size
1n of an array for which Computer B begins to outperform Computer A and also
the minimum size 2n of an array for which Computer C begins to outperform
Computer B.
For an array of size n, the run time of Computer A is equal to  1kT n kn , while
that of Computer B is  14 8kT n k n and that of Computer C is
 3 216 16 log ,kT n k n for some constant k. Thus, the minimum value 1n of n for
which Computer B begins to outperform Computer A is given by
1 18 .kn k n
Dividing both sides by k yields
1 18 .n n
Squaring both sides, we obtain
21 164 .n n
Finally, dividing both sides by 1n yields
1 64.n 
Now the minimum value 2n of n for which Computer C begins to outperform
Computer B is given by
2 2 28 16 log .k n k n
Dividing both sides by 8k, we obtain
2 2 22log .n n
By trial and error or otherwise, we find that
2 256.n 
2. Mathematical Induction

i. We wish to prove by induction that for all positive integers n, we have

(1)  
0
.
n
n n i...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here