This problem is like the even-odd sorting problem in homework 3; the main difference is that even-odd sorting has to deal with two classes of numbers and three-sorting has to deal with three classes.
Despite their differences, the problems are similar enough that it's a good idea to start with even-odd sorting and extend it to provide three sorting. Putting the zeros to the left and the twos to the right is easy enough, but what about the ones in the middle (for ease of exposition, I'm going to assume that the array to be three sorted contains only zeros, ones, and twos)?
Unlike the even-odd sort, the markers for the zero and two blocks are pinned and cannot scan through the unexamined middle of the array because the scan may encounter an element not part of its block, which is awkward to deal with. The solution, suggested by the third block in the array, is to add a new marker for the end of the ones block. The ones marker is free to scan the unexamined part of the array because any element it encounters can be dealt with by swapping to the proper block. The three-sort algorithm follows directly.
three-sort(A)
l = m = 0
r = |A|
# invariant: a[0..l-1] = 0 and a[l..m-1] = 1 and a[r..|A|-1] = 2 and
# l <= m and m <= r
do m < r
if a[m] mod 3 = 0
swap(a[l], a[m])
l <- l + 1
m <- m + 1
or a[m] mod 3 = 1
m <- m + 1
or a[m] mod 3 = 2
r <- r - 1
swap(a[m], a[r])
fi
od
A are to the left of A, some of the ones in A are in
the middle of A next to the zeros, and some of the twos in A are to
the right of A; in a picture Note that
l and m point to elements immediately to the right of the block
of zeros and ones, respectively, and that r points to the left-most
element in the block of twos. Note also that either l equals m if
there is no block of ones, or that l points to the left-most one in the
block of ones.
Before the loop starts executing, l = m = 0, which means
a[0..l-1] = 0 is true by default, as is a[l..m-1] = 1, and l <=
m is also true. r = |A| before the loop, so a[r..|A|-1] = 2 is
true by default, and m <= r is also true. All these truths together mean
the invariant is true before the loop starts executing.
Let the do perform one iteration with the invariant true. One of the three guards of if statement must be true, so we have three cases to consider:
mis pointing to a zero - we want to swapa[m]witha[l], and there are two cases to consider. Ifm=l, the swap has no effect; ifm>l, then we're swapping a zero and a one into their proper locations. In either case, we increase bothmandlby one, which maintains the invariant.mis pointing to a one - in this case we can increasemby one and maintain the invariant: the blocka[l..m-1]still contains all ones andm <= rstill holds becausem < rwas true (otherwise the do wouldn't have performed an iteration) before we added one tom.mis pointing to a two - we want to swapa[m]into the block of twos, butris pointing to the left end of the block, so we have to decrease it by one before doing the swap. Becausem < rwas true before we subtracted one fromr,m <= ris true after, and the swap preserves the invariant
All three cases preserve the truth of the invariant, so an iteration of the loop preserves the invariant.
Every iteration of the loop either increases m by one or decreases r
by one, so the loop will eventually terminate. When it does, we can conclude
that m >= r. Because the invariant is true when the loop terminates,
m <= r is true and we can conclude that m = r. When m = r, the
truth of the invariant lets us conclude that the whole array is three sorted as
required.
Find an expression for the number of different itl(n)-egg breakfast sequences possible for any given non-negative itl(n). Make sure you prove all steps in your derivation.
The problem is to count the possible breakfast sequences given itl(n) eggs; that is, if
itl(T)(itl(n)) = the number of possible breakfast sequences given itl(n) eggs,find an expression for itl(T)(itl(n)).
The set of different breakfast sequences possible with itl(n) eggs can be split into two subsets: those itl(n)-egg sequences starting with scrambled eggs and those itl(n)-egg sequences starting with french toast. The two subsets are disjoint - no breakfast sequence can start with both scrambled eggs and french toast - and because every breakfast sequence must start with either scrambled eggs or french toast, every sequence in the original set must be in one of the two subsets. This means the size of the original set is equal to the sum of the size of the two subsets, or the number of itl(n)-egg breakfast sequences is equal to the number of itl(n)-egg breakfast sequences starting with french toast plus the number of itl(n)-egg breakfast sequences starting with scrambled eggs.
How many itl(n)-egg breakfast sequences start with scrambled eggs? From the statement of the problem, scrambled eggs take two eggs, so the number of itl(n)-egg breakfast sequences starting with scrambled eggs is equal to the number of breakfast sequences possible with itl(n)-2 eggs (you take each itl(n)-2-egg sequence and stick scrambled eggs on the front). Similarly, the number of itl(n)-egg breakfast sequences starting with french toast is equal to the number of breakfast sequences possible with itl(n)-1 eggs.
From the previous two paragraphs, the recurrence relation is
itl(T)(itl(n)) = itl(T)(itl(n) - 1) + itl(T)(itl(n) - 2)The base cases are itl(T)(1) = 1 - that is, scrambled eggs is the only 1-egg breakfast sequence - and itl(T)(2) = 2 - that is, either one french toast or two scrambled eggs are the only 2-egg breakfast sequences.
Divide B into two roughly equal pieces and check if A is a subarray
of either of the pieces. If it is, then return true because A is a
subarray of B. If A is not a subarray of either of the pieces, we
have to check that A isn't split between the two parts of B before
concluding that A isn't a subarray of B.
Dividing stops when B is less than twice the size of A; in that case,
it doesn't make sense to divide B further because the resulting pieces
will be smaller than A.
bool subarray(A, B)
if |B| < 2|A|
for i = 0 to |B| - |A|
if B[i..i+|A|-1] = A
return true
return false
if subarray(A, B[0..|B|/2-1]) or subarray(A, B[|B|/2..|B|-1])
return true
l <- max(0, |B|/2 - |A| + 1)
r <- min(|B|/2 - 1, |B| - |A| + 1)
do l < r
if B[l..l+|A|-1] = A
return true
l <- l + 1
od
return false
Because trees are recursive data structures, a straightforward recursive algorithm to neatly draw trees is to neatly draw a tree's children and then neatly draw the root. But the requirement that siblings be equally spaced causes a problem: the space between siblings can't be known until the siblings are drawn (to determine their width), and the siblings can't be drawn until the space between them is known (you could assign an arbitrary distance between siblings, but if it wasn't wide enough, the subtree rooted at one sibling might overlap the subtrees rooted at its adjacent siblings).
The easiest way out of this problem is to break the drawing algorithm into two parts, one part computes the width of a tree and the other part draws the tree.
The width computation has a simple recursive formulation. A tree with no children is as wide as the node itself. For a tree with children, one of the children is the widest of its siblings; assume all siblings are as wide as the widest sibling. This assumption lets us compute the overall width of the tree, and ensures both that the siblings are equally spaced and non-overlapping.neatly_draw(x, y, root) width(root) draw(x, y, root)
width() assumes each node contains a width field for storing the
width of the tree rooted at the node.
width(root)
root.width <- node diameter
if root.children != {}
for c in root.children
width(c)
root.width <- max(root.width, c.width)
root.width <- root.width*|root.children|
x, y) coordinates. The children are
drawn with the same y coordinates, which helps ensure horizontal alignment; the
x coordinates for the children are set so the children have equal space between
them and are centered under their parent.
draw(x, y, root)
draw root at (x, y)
y <- y + level-separation
x <- x - root.width/2
x-step <- root.width/|root.children|
for c in root.children
draw(x, y, c)
x <- x + x-step