HW 1 - Fundamentals

CS 350 Spring 2011 HW 1 - Fundamentals
  1. Look at the Wikipedia page for "Fisher-Yates" shuffle. Find the "inside-out shuffle" on that page. Do not mock the pseudocode, as I wrote it. Give an implementation of that algorithm in your favorite programming language.
  2. Modify the algorithm of textbook problem 1.2.9 to find the distance between the farthest (most numerically different) elements in an array of numbers.
  3. Give an algorithm for the following problem.
    PAIRWISE MAXIMIZATION
    Given: A positive integer n and a function f : [0, 1..n] -> [0, 1..n] -> Z,
    Find: Arguments x and y maximizing f(x,y).
  4. Give an efficient algorithm for the following problem. Sorting the array is not efficient enough. Hint: Pick a good auxiliary data structure.
    MODAL AVERAGE
    Given: An array a of n integers in the range 0..5.
    Find: The most-commonly occurring value in a.
  5. Give an efficient algorithm for the following problem. It should do at most n - 1 comparisons and not alter the array.
    SORTEDNESS
    Given: An array a of n integers in the range 0..5n.
    Find: Whether the array is already in sorted order (return true) or not (return false).
  6. Order the following functions according to their order of growth (lowest to highest). The symbol "^" denotes exponentiation.
    1. (n+7)! + n^3
    2. n + 10^10
    3. (lg (n^5))^2
    4. 2^(2n)
    5. sqrt n
  7. Consider the following sorting algorithm. What is its "big-O" worst-case running time, in terms of the size n of the array? Is the algorithm correct?
    ALGORITHM BIGSORT

    To sort an n-element zero-based array a: k ← n - 1 fori ← 0..n-1 h ← a[i] ih ← il ← a[i] il ← iforj ← i+1..n-1 ifa[j] > hh ← a[j] ih ← jifa[j] < ll ← a[j] il ← j exchange a[i] with a[il] ifk > i exchange a[k] with a[ih] k ← k - 1