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. ==============================