[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

328.0. "Read previous by RFA" by R2ME2::GILBERT () Thu Aug 15 1985 12:02

Suppose we want to read a file containing N records, but in reverse order.
The primitive operations allow for reading the next sequential record, or
starting again at the beginning, or for randomly reading a record by its RFA
(once we know its RFA).  Suppose we want to save RFAs for only R records.
How should we proceed to minimize the number of primitive operations?

For example, if we have 6 records, and save only 1 RFA, we can proceed
as follows, taking only 14 operations (asterisks mark where we've read
the desired record).

	Read record 1
	Read record 2
	Read record 3
	Read record 4 (and save its RFA)
	Read record 5
    *	Read record 6
	Read record 4 (by RFA)
    *	Read record 5
    *	Read record 4 (by RFA)
	Read record 1 (rewind)
	Read record 2 (and save its RFA)
    *	Read record 3
    *	Read record 2 (by RFA)
    *	Read record 1 (rewind)

Let C(N,R) be the 'cost' function.  We know that C(N,0) = N(N+1)/2, and
C(N,R) = 2N-1 if R > N-2.  The example shows that C(6,1) <= 14.

What is the behaviour of C(N,R)?  What is C(N,1)?
T.RTitleUserPersonal
Name
DateLines
328.1ALIEN::POSTPISCHILThu Aug 15 1985 21:2813
Let p(n,r) denote the record at which the first RFA should be saved if optimal
cost is to be produced.

Then the record at which the second RFA should be saved is
p(n,r) + p(n-p(n,r),r-1) - 1, and the C(n,r) = C(p(n,r)-1,r) + C(n-p(n,r),r-1).

Why?  Observe that after the first RFA has been saved at record p(n,r), there
are two problems:  Reading the records from p(n,r) to n in reverse order using
r-1 RFA's and reading the records from 1 to p(n,r)-1 in reverse order using
r RFA's.


				-- edp
328.2R2ME2::GILBERTFri Aug 16 1985 21:161
Then p(n,r) should be chosen to minimize the cost, right?
328.3ALIEN::POSTPISCHILFri Aug 16 1985 21:404
Yes, indeed.  Any ideas?


				-- edp
328.4R2ME2::GILBERTFri Aug 30 1985 17:234
C( bin(x,r+1), r ) = bin(x+1,r+2) + r*bin(x,r+2),

where bin(a,b) is a binomial coefficient, and the costs for
other values of n can be found by interpolation.
328.5ALIEN::POSTPISCHILThu Sep 05 1985 13:316
Re .4:

How about a proof?


				-- edp
328.6HARE::GILBERTThu Sep 05 1985 14:0121
We have:

	C(0,r) = 0
	C(n,-1) = infinity, n>0
	C(n,r) = min [ k + C(n-k,r-1) + C(k,r) ]
	       0<=k<n

And remark that:

	C(n,0) = bin(n+1,2)
	C(1,r) = 1, r>=0

Consider the function:

	F( bin(x,r+1), r ) = bin(x+1,r+2) + r*bin(x,r+2), and
	F(n,r) for other values of n can be found by interpolation.

We see that F(0,r) = 0.  If we assume F(n,r) is a solution to the
recurrence relation for all n<N, r<R, it's a simple matter to show
that F(N,R) also satisfies the recurrence (well, if not simple, at
least it's straight-forward).
328.7ALIEN::POSTPISCHILThu Sep 05 1985 14:347
Re .6:

I'm afraid I can't let you off that easily.  Let's see this straightforward
demonstration.


				-- edp