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:
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
Give an analysis of the worst-case running time of this algorithm.
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.
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
's outer loop (i.e. after the i=3 iteration is completed).
Separately, show what the array looks like after four iterations of
'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
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
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
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]
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 "<".
justify both your lower bound and
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.
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$.