HW 1 - Fundamentals
- 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.
- 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.
- Give an algorithm for the following problem.
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).
- Give an efficient algorithm for the following problem. Sorting the array is not efficient enough. Hint: Pick a good auxiliary data structure.
Given: An array a of n integers in the range 0..5.
Find: The most-commonly occurring value in a.
- Give an efficient algorithm for the following problem. It should do at most n - 1 comparisons and not alter the array.
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).
- Order the following functions according to their order of growth (lowest to highest). The symbol "^" denotes exponentiation.
- (n+7)! + n^3
- n + 10^10
- (lg (n^5))^2
- sqrt n
- 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?
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