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

**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)*. - 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*. - 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*). - 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**2^(2n)**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?**ALGORITHM BIGSORT**To sort an n-element zero-based array

*a*:*k*←*n*- 1**for***i*← 0..n-1*h*←*a*[*i*]*ih*←*i**l*←*a*[*i*]*il*←*i***for***j*←*i*+1..n-1**if***a*[*j*] >*h**h*←*a*[*j*]*ih*←*j***if***a*[*j*] <*l**l*←*a*[*j*]*il*←*j*exchange*a*[*i*] with*a*[*il*]**if***k*>*i*exchange*a*[*k*] with*a*[*ih*]*k*←*k*- 1