Information Technology Reference
In-Depth Information
D
Ω
(
BS
(
n
)) =
1
2
log
n
(log
n
−
1
)
6.8.2 Fast Sorting Networks
Ajtai, Komlos, and Szemeredi [
14
] have shown the existence of a sorting network (known
as the
AKS sorting network
)on
n
inputs whose circuit size and depth are
O
(
n
log
n
)
and
O
(log
n
)
, respectively. The question had been open for many years whether such a sorting
network existed. Prior to [
14
] it was thought that sorting networks required
Ω(log
2
n
)
depth.
.......................................
Problems
MATHEMATICAL PRELIMINARIES
6.1 Show that
(
,
+
,
∗
,0,1
)
is a commutative ring, where
+
and
∗
denote integer addition
and multiplication and 0 and 1 denote the first two integers.
6.2 Let
p
be the
set of integers modulo
p
,
p>
0, under addition and multiplication
modulo
p
with additive identity 0 and multiplicative identity 1. Show that
p
is a ring.
6.3 A
field
F
is a commutative ring in which each element other than
0
has a multiplicative
inverse. Show that
(
p
,
+
,
∗
,0,1
)
is a field when
p
is a prime.
MATRICES
6.4 Let
M
n×n
be the set of
n
×
n
matrices over a ring
R
. Show that
(
M
n×n
,
+
n
,
×
n
,0
n
,
I
n
)
is a ring, where
+
n
and
×
n
are the matrix addition and multiplication operators
n
zero and identity matrices.
6.5 Show that the maximum number of linearly independent rows and of linearly indepen-
dent columns of an
n
and 0
n
and
I
n
are the
n
×
m
matrix
A
over a field are the same.
Hint:
Use the fact that permuting the rows and/or columns of
A
and adding a scalar
product of one row (column) of
A
to any other row (column) does not change its rank.
Use row and column permutations as well as additions of scalar products to rows and/or
columns of
A
to transform
A
into a matrix that contains the largest possible identity
matrix in its upper left-hand corner. This is called
Gaussian elimination
.
6.6 Show that
(
AB
)
T
×
=
B
T
A
T
for all
m
×
n
matrices
A
and
n
×
p
matrices
B
over a
R
commutative ring
.
MATRIX MULTIPLICATION
6.7 The standard matrix-vector multiplication algorithm for a general
n
n
matrix requires
O
(
n
2
)
operations. Show that at most
O
(
n
log
2
3
)
operations are needed when the matrix
is Toeplitz.
Hint:
Assume that
n
is a power of two and treat the matrix as a 2
×
×
2matrixof
n/
2
1 values determine all the entries in a
Toeplitz matrix. Thus, the difference between two
n
×
n/
2 matrices. Also note that only 2
n
−
×
n
Toeplitz matrices does not
require
n
2
operations.
Search WWH ::
Custom Search