prof hayward     cmput 204 homepage     fall 2013: a2/ea2

                        Seminar Set 3 (Some Hints)

1. Job Assignment
A simple example where the optimal solution does not include
the smallest element of the cost matrix is: [1 2; 2 100]

2. Generating All Subsets
Idea: generate binary representations of numbers in the range
[0,2n-1]. Interpret the resulting binary bit pattern of each
integer as a subset of the given set.

3. Generating All Permutations
Refer to Section 5.4 for details of the Johnson-Trotter and the lexicographic
ordering methods.
Note: these methods are outside the scope of the midterm exam.

4. Sorting by Exhaustive Search
Generate all permutations of the input list. Choose the permutation that
corresponds to a sorted list. The algorithm runs in Θ(n! n).

5. Identity of Logarithms
Take logb of both sides and note the resulting identity.
Writing a time or space function as nlog2 3 makes it obvious that
the function does not grow exponentially with the problem size n.

6. Wiggle Sort
Consider a Merge Sort like approach where array A(first, ..., last) is
divided into two nearly equal arrays: A(first ... mid) and
A(mid+1 ... last).
The divide-and-conquer step calls the function recursively to wiggle sort
the two half-sized arrays.
The combine step examines A(mid) and A(mid+1) and swaps them if necessary
to construct a valid wiggle sorted array A.

7. Searching a Young Tableau
To search a Young tableau A(0 ... m-1, 0 ... n-1) for a given number
x, consider comparing x to the middle element A(i,j) where i= floor (m/2)
and j= floor(n/2).

 If x < A(i,j) we can exclude the quadrant A(i ... n, j ... m) since
     all of its elements are larger than x.
 Else, if x > A(i,j) we can exclude the quadrant A(0 ... i, 0 ... j)
     since all of its elements are smaller than x.

Problems 8 and 9
These questions are outside the scope of the midterm exam. Hints will
be posted later.