Java Reference
In-Depth Information
-
Write a function
public static int
[] createNextLine(
int
[] line )
that takes
as a parameter a reference to an array of integers storing the values of
C
n−
1
,∗
and returns a reference to a new array of integers containing
the values
C
n,∗
. Write a program for displaying the Pascal triangle of
size 35 with this method. What happens? Please explain and compare
with the fully recursive program. Deduce a simple program to display
Pascal triangles of any order.
Exercise 9.2 (Fibonacci sequences)
Fibonacci sequences are defined by the recurrence relation
F
(
n
)=
F
(
n
−
1) +
F
(
n
−
2) for
n
≥
2and
F
(0) = 0,
F
(1) = 1, otherwise.
-
Give a recursive function for computing arbitrary
F
(
n
).
-
Using the memoization technique, create a static array
static long
[]
memo;
, and procedures for filling the array and computing (returning)
a member of the sequence. What happens as
n
grows?
There exits a fast exponentiation method to compute Fibonacci numbers.
Indeed, prove that
F
(
n
+1)
=
11
10
n
F
(
n
)
.
F
(
n
)
F
(
n
−
1)
It follows that
F
(
n
+1)
=
11
10
=
F
(2
n
+1)
.
2
2
n
F
(
n
)
F
(2
n
)
F
(
n
)
F
(
n
−
1)
F
(2
n
)
F
(2
n
−
1)
Deduce that
F
(2
n
)=
F
(
n
)
×
(
F
(
n
)+2
F
(
n
−
1)) and
F
(2
n
−
1) =
F
(
n
)
2
+
F
(
n
−
1)
2
.Thusif
n
is even, then
F
(
n
)and
F
(
n
−
1) can be
obtained directly from
F
(
n/
2) and
F
(
n/
2
−
1). Similarly, if
n
is odd,
then we get
F
(
n
−
1) and
F
(
n
−
2), and
F
(
n
) is computed as the sum of
F
(
n
2). Implement this algorithm using
BigInteger
number
instead of
int
to circumvent numerical problems.
Exercise 9.3 (Hitting set problem)
−
1) +
F
(
n
−
We are given a range space (
X
,
R
)of
|X |
=
n
elements
X
1
, ..., X
n
and
|R|
=
m
subsets
R
1
, ..., R
m
. We are asked to find a hitting set, that is a
subset
X
⊆X
of elements so that each range
R
i
contains at least one
X
.
element of
-
Design a greedy algorithm to find a not too large hitting set.
-
Show that hitting set problems are dual to set cover problems by
reversing the inclusion order. Show that the duality consists merely in
transposing the incidence matrix.
Search WWH ::
Custom Search