| 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 |
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.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 328.1 | ALIEN::POSTPISCHIL | Thu Aug 15 1985 18:28 | 13 | ||
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.2 | R2ME2::GILBERT | Fri Aug 16 1985 18:16 | 1 | ||
Then p(n,r) should be chosen to minimize the cost, right? | |||||
| 328.3 | ALIEN::POSTPISCHIL | Fri Aug 16 1985 18:40 | 4 | ||
Yes, indeed. Any ideas? -- edp | |||||
| 328.4 | R2ME2::GILBERT | Fri Aug 30 1985 14:23 | 4 | ||
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.5 | ALIEN::POSTPISCHIL | Thu Sep 05 1985 10:31 | 6 | ||
Re .4: How about a proof? -- edp | |||||
| 328.6 | HARE::GILBERT | Thu Sep 05 1985 11:01 | 21 | ||
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.7 | ALIEN::POSTPISCHIL | Thu Sep 05 1985 11:34 | 7 | ||
Re .6: I'm afraid I can't let you off that easily. Let's see this straightforward demonstration. -- edp | |||||