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