Information Technology Reference
In-Depth Information
.......................................
Problems
MATHEMATICAL PRELIMINARIES
10.1 Show that the the pyramid graph on m inputs, P ( m ) ,has m ( m + 1 ) / 2vertices.Let
n = m ( m + 1 ) / 2. Show that m
2 n
1.
10.2 Show that the following inequalities hold for integers m and x :
m/x
m/x
( m + x
1 ) /x
( m
x + 1 ) /x
m/x
m/x
10.3 Suppose that p log 2 p
2 q/ log 2 q .
10.4 For n positive integers x 1 , x 2 , ... , x n , show that the following inequality holds between
the geometric mean on the left and the arithmetic mean on the right:
q for positive integers p , q
2. Show that p
x n ) 1 /n
( x 1 x 2 ···
( x 1 + x 2 +
···
+ x n ) /n
e −x holds for x
10.5 Show that the inequality ( 1
x )
1.
10.6 Show that there are ( r + k )! /r ! ways for k ordered values to appear among r distinct
ordered items.
10.7 Show that there are N ( n , k )= n + k− 1
k
< 2 n + k− 1 ways to choose with repetition k
of size n where the order among the numbers is unimportant.
Choosing with repetition means that a number can be chosen more than once.
Hint: Without loss of generality, let
A
numbers from a set
A
=
{
1, 2, ... , n
}
. Since order is unimportant,
assume the chosen numbers are sorted. Let each chosen number be represented by a
blue marker. Imagine placing the blue markers on a horizontal line. For 1
i
n
1,
place a red marker between the last blue marker associated with the number i and the
first blue marker associated with the number i + 1, if any. This representation uniquely
determines the number of elements of each type chosen. How many ways can the red
markers be placed?
10.8 Show that a complete balanced binary tree on 2 k− 1 leaves has 2 k
1 vertices including
leaves and that each path from a leaf to the root has k
1edgesand k vertices.
THEPEBBLEGAME
10.9 Consider the circuit shown in Fig. 2.15 . Treat each gate and each input vertex as a
vertex. Give a good pebbling strategy for this graph.
10.10 Give a pebbling strategy for the m -input counting circuit in Fig. 2.21 (b) that uses
O (log 2 m ) pebbles and O ( m ) steps. Determine the minimum number of pebbles
with which the circuit can be pebbled. Determine the number of steps needed with
this minimal pebbling.
Search WWH ::




Custom Search