8-4 Water jugs

Suppose that you are given n red and n blue water jugs, all of different
shapes andsizes. All red jugs hold different amounts of water, as do the
blue ones. Moreover,for every red jug, there is a blue jug that holds
the same amount of water, and vice versa.

Your task is to find a grouping of the jugs into pairs of red and blue
jugs that hold the same amount of water. To do so, you may perform the
following operation: pick a pair of jugs in which one is red and one is
blue, fill the red jug with water, and then pour the water into the blue
jug. This operation will tell you whether the red or the blue jug can
hold more water, or that they have the same volume. Assume that such a
comparison takes one time unit. Your goal is to find an algorithm that
makes a minimum number of comparisons to determine the grouping.
Remember that you may not directly compare two red jugs or two blue
jugs.

  1. Describe a deterministic algorithm that uses \(\theta(n^2)\)
    comparisons to group the jugs into pairs.
  2. Prove a lower bound of Ω(n lg n) for the number of comparisons that
    an algorithm solving this problem must make.
  3. Give a randomized algorithm whose expected number of comparisons is
    O(n lg n), and prove that this bound is correct. What is the
    worst-case number of comparisons for your algorithm?

答:1.使用一个与插入排序类似的算法,比方我们以红壶为准,拿红壶的第一只依次与
蓝壶比较,找到与他匹配的蓝壶,然后用第二只红壶与剩下的蓝壶比较,找出第二只匹
配的蓝壶,依次类推。

2.其实水壶问题,就是一个变相的排序问题,例如,我们先将红壶依次摆开,然后给他
们找匹配的蓝壶,最终的结果不正就是我们将蓝壶按照红壶的顺序排好吗。很显然水壶
的问题是基于比较的,自然逃不出比较排序在最坏情况下的下复杂度为Ω(nlg n)的命运,
具体证明请参考

3.快速排序恰好满足这种要求,只不过与a相似比较的对象是另一种颜色的水壶,其最坏情
况下比较次数为\(O(n^2)\)。详情.

8-5 Average sorting

Suppose that, instead of sorting an array, we just require that the
elements increase on average. More precisely, we call an n-element array
A k-sorted if, for all i = 1;2,…,n - k, the following holds:

formula

  1. What does it mean for an array to be 1-sorted?
  2. Give a permutation of the numbers 1;2;….;10 that is 2-sorted, but
    not sorted.
  3. Prove that an n-element array is k-sorted if and only if
    A[i] <= A[i+k] for all i =1;2;…;n-k.>
  4. Give an algorithm that k-sorts an n-element array in O(n lg(n/k))time.
    We can also show a lower bound on the time to produce a k-sorted
    array, when k is a constant.
  5. Show that we can sort a k-sorted array of length n in O(n lg k)time.
    (Hint:Use the solution to Exercise 6.5-9. )
  6. Show that when k is a constant, k-sorting an n-element array requires
    Ω(n lg n) time. (Hint: Use the solution to the previous part along with
    the lower bound on comparison sorts.)

答:

  1. 意味着它与普通排序完全一样。
  2. 2,1,3,4,6,5,8,7,9,10。
  3. 反证法:若有任意i使得A[i]>A[i+k],那么题设不总是成立。
  4. 使用合并排序,当待排序的数目,小于等于k时停止递归。其递归深度为lg(n/k)。
  5. 根据c我们可以得出,对于一个k-排列的数组,我们可以得出k个有序的子数组,例如
    对于一个2-排列的2n个元素的数组我们可以得出两个2个有序的子数列:第一个为
    k1 <= k3
  6. 又是一个关于比较排序的下限证明的问题,由c可知,对于一个k-排序的数组来说,必
    须满足一个条件:按照e的方法生成的k个数组必然是有序的。所以问题f可以看做是,
    对k组数目为n/k的数组进行比较排序。余下,略。

8-7 The 0-1 sorting lemma and columnsort

关于8-7我对这个题目很有兴趣,但是却没有理解透彻,何其悲哀。题目太长也就不贴了,
未能理解,所以答案贴了也无意义,反而可能扰乱以后的灵感。