patternMinor
What does > mean in this TAOCP solution?
Viewed 0 times
thiswhattaocpmeandoessolution
Problem
For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd).
However, I fail to understand the solution given in TAOCP.
Problem:
Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end of the line didn’t understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put in a huge basket and taken to the National Archives in Washington, D.C. Here the contents of the basket were shuffled completely and transferred to magnetic tapes.
At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tapes and a small amount of random-access memory. How was this possible?
In other words, given the pairs $(x_i, x_{i+1})$ for $1 \le i
-
If $x' = y'$, output $(y-t, x)$ to $G'$ and advance files $F$ and $G$.
-
If $x' > y'$, advance file $G$.
-
If $x' > z$, advance file $H$.
When file $F$ is exhausted, sort $G'$ by second components and merge $G$ with it; then replace $t$ by $2t$, $F$ by $F'$, $G$ by $G'$. Thus $t$ takes the values $2$, $4$, $8$, $\ldots$; and for fixed $t$ we do $O(\log N)$ passes over the data to sort it. Hence the total number of passes is $O((\log N)^2)$. Eventually $t \ge N$, so $F$ is empty, then we simply sort $G$ on its first components.
So here is my question:
What do the more than sign denote here? $x'$, $y'$, $z$ are strings, is
However, I fail to understand the solution given in TAOCP.
Problem:
Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end of the line didn’t understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put in a huge basket and taken to the National Archives in Washington, D.C. Here the contents of the basket were shuffled completely and transferred to magnetic tapes.
At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tapes and a small amount of random-access memory. How was this possible?
In other words, given the pairs $(x_i, x_{i+1})$ for $1 \le i
-
If $x' = y'$, output $(y-t, x)$ to $G'$ and advance files $F$ and $G$.
-
If $x' > y'$, advance file $G$.
-
If $x' > z$, advance file $H$.
When file $F$ is exhausted, sort $G'$ by second components and merge $G$ with it; then replace $t$ by $2t$, $F$ by $F'$, $G$ by $G'$. Thus $t$ takes the values $2$, $4$, $8$, $\ldots$; and for fixed $t$ we do $O(\log N)$ passes over the data to sort it. Hence the total number of passes is $O((\log N)^2)$. Eventually $t \ge N$, so $F$ is empty, then we simply sort $G$ on its first components.
So here is my question:
- If $x' > y'$, advance file $G$.
- If $x' > z$, advance file $H$.
What do the more than sign denote here? $x'$, $y'$, $z$ are strings, is
Solution
What does > denote here?
It's not stated explicitly, but a reasonable meaning can be inferred from context.
The authors assume that the data can be sorted so there has to be some (total) order relation $\leq$ (canonically) on the elements. We don't care what the elements are, so we do not fix the relation, either. In any given situation, we would know what to do and have a fixed relation.
For instance, if we wanted to sort natural numbers in increasing order, $>$ would mean the usual. I we wanted to sort them in decreasing order, you'd have to replace $>$ by $<$ in the solution.
It's not stated explicitly, but a reasonable meaning can be inferred from context.
The authors assume that the data can be sorted so there has to be some (total) order relation $\leq$ (canonically) on the elements. We don't care what the elements are, so we do not fix the relation, either. In any given situation, we would know what to do and have a fixed relation.
For instance, if we wanted to sort natural numbers in increasing order, $>$ would mean the usual. I we wanted to sort them in decreasing order, you'd have to replace $>$ by $<$ in the solution.
Context
StackExchange Computer Science Q#52428, answer score: 7
Revisions (0)
No revisions yet.