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