P1

The isPermuation problem is this: Given an array A of n integers, determine whether A represents a permutation, i.e. determine whether A contains exactly the numbers from 0 to n-1, each appearing exactly once, but allowed to appear in any order. Here is an algorithm to solve the problem:

isPermV1(A,n)
bad = 0
i = 0
while i < n do

  if A[i] < 0 or A[i] >= n     \__ increment bad if A[i] is out of range
    bad = bad + 1              /

  j = 0                       \
  while j < i do               |__ increment bad if A[i] has a duplicate earlier in A
    if A[j] = A[i]             |
      bad = bad + 1            |
    j = j + 1                 /

if bad > 0
   return FALSE
else
   return TRUE
	  

Give an analysis of the worst-case running time of this algorithm.

---

P2

Use the idea of time-space tradeoff to write down an improved version of this algorithm. Hint: declare an array X of n zeros prior to entering the outer while and try to think about how having that on hand allows you to speed up the algorithm.

---

P3

This question refers to selectionSort and insertionSort as described in the Class 6 notes. Consider the array A given below and show what the array looks like after four iterations of the selectionSort's outer loop (i.e. after the i=3 iteration is completed). Separately, show what the array looks like after four iterations of the insertionSort's outer loop (i.e. after the i=3 iteration is completed) starting out with the same A as shown below.

A:  0  9 43  8  1 41 40  5
   ------------------------
    0  1  2  3  4  5  6  7
      

---

P4

Give a loop invariant for selectionSort's outer loop. Then give a loop invariant for insertionSort's outer loop. I'm not asking you to prove the invariants for me, though they need to be strong enough that you could prove them if I asked. I'm also not asking you to prove the correctness of selectionSort and insertionSort, though your invariants should also be strong enough that you could use them to prove the selectionSort/insertionSort correct.

---

P5

Suppose that we want to sort an array $A$ of length $n$, in which each element of $A$ is itself an array of $n$ integers. We will define "<" for these arrays as

Algorithm: lt(a,b)
Inputs: a and b, both n-element arrays of integers
Output: true if a is "less than" b, false otherwise

k = 0;
while k < n and a[k] = b[k] do
  k = k + 1

if k < n and a[k] < b[k]
  return true
else
  return ralse
      

Analyze the worst-case running time of selectionSort in this case, i.e. with an n-element array $A$, each element of which is array of $n$ integers, using the above algorithm as "<".
Note1: You must justify both your lower bound and upper bound!
Note2: You may assume the elements of $A$ are pointers to arrays of ints, so that swapping two elements of $A$ is a constant time operation.

---

P6

Practice with logarithms! Recall that "$\lg$" means "log base 2". Prove that $\lg (n-1) + \lg (n+1) \lt 2 \lg n$ for all $n \gt 1$.

---