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