Information Technology Reference
In-Depth Information
1.6 Describe an algorithm to convert numbers from decimal to binary notation.
1.7 A graph
G
=(
V
,
E
)
can be described by adjacency lists, one list for each vertex in the
graph. The
adjacency list
for vertex
v
V
is a list of vertices to which there is an edge
from
v
. Generate adjacency lists for the two graphs of Fig.
1.2
.
∈
TASKSASFUNCTIONS
1.8 Let
5
be the set
{
0, 1, 2, 3, 4
}
. Let the addition operator
⊕
over this set be
modulo
5;
that is, if
x
and
y
are two such integers,
x
y
is obtained by adding
x
and
y
as integers
and taking the remainder after division by 5. For example, 2
⊕
⊕
2
=
4
mod
5whereas
5
.
1.9 Give a truth table for the Boolean function whose value is
Tr u e
exactly when either
x
or
y
or both is
Tr u e
and
z
is
False
.
3
⊕
4
=
7
=
2
mod
5. Provide a table describing the function
f
⊕
:
5
×
→
5
RATE OF GROWTH OF FUNCTIONS
1.10 For each of the fifteen unordered pairs of functions
f
and
g
below, determine whether
f
(
n
)=
O
(
g
(
n
))
,
f
(
n
)=Ω(
g
(
n
))
,or
f
(
n
)=Θ(
g
(
n
))
.
a)
n
3
;
n
6
;
n
3
log
2
n
;
c)
e)
f) 2
2
n
.
2
n
log
2
n
;
n
2
n
;
b)
d)
1.11 Show that 2
.
7
n
2
+
6
√
n
log
2
n
≤
8
.
7
n
2
for
n
≥
3.
METHODS OF PROOF
1.12 Let
S
r
(
n
)=
j
=
1
j
r
denote a sum of powers of integers. Use proof by induction to
show that the following identities on arithmetic series hold:
a)
S
2
(
n
)=
n
3
3
+
n
2
2
+
6
S
3
(
n
)=
n
4
4
+
n
3
2
+
n
2
4
b)
COMPUTATIONAL MODELS
1.13 Produce a circuit and straight-line program for the Boolean function described in Prob-
lem
1.9
.
1.14 A
state diagram
for a finite-state machine is a graph containing one vertex (or
state
)
for each pattern of data that can be held in its memory and an edge from state
p
to
state
q
if there is a value for the input data that causes the memory to change from
p
to
q
. Such an edge is labeled with the value of the input data that causes the transition.
Outputs are generated by a finite-state machine when it is in a state. The vertices of its
state diagram are labeled by these outputs.
Provide a state diagram for the finite-state machine described in Fig.
1.5
(b).
1.15 Using the straight-line program given for the full-adder circuit in Section
1.4.1
,describe
how such a program would be placed in the random-access memory of the RAM and
how the RAM would run the fetch-and-execute cycle to compute the values produced
by the full-adder circuit. This is an example of circuit simulation by a program.
Search WWH ::
Custom Search