CS 280 HW3 Solutions

1) Recall
that any permutation P can be expressed as a composition of disjoint cycles.
Since these cycles are disjoint, we will present here an algorithm to express a
single cycle as a composition of transpositions. Let the cycle be (a1 a2 a3
ak). Out algorithm takes as input
this cycle, which we will call C and treat as a 1-based array of size k. We
will return an ordered list of transpositions, where the transposition at the
front of the list is intended to be applied last, as per the convention
established in HW2.

CYCLE_TO_TRANS(C[]) { //C is the
cycle notation of a cycle.

List transpositions = {};

for (int i = 2; i
<= k; i++) {

add (a1 ai) to the front of the list

}

return
transpositions;

}

//So given
the input [a1 a2 ... ak],
CYCLE_TO_TRANS produces the list

// transpositions =
{(a1 ak), (a1 a(k-1)), ... , (a1 a3), (a1 a2)}

//which is
the desired result, as found in the solution to HW2.

PERM_TO_TRANS(Cycle_list L) { //L is a
list of disjoint cycles.

List total_trans_list
= {};

For each cycle C in L {

cycle_trans_list
= CYCLE_TO_TRANS(C);

total_trans
= append(total_trans_list, cycle_trans_lost)

}

return total_transpositions

}

To execute
the algorithm on a permutation P, we execute PERM_TO_TRANS(L)
where L = {(c1a1 c1a2 ... c1ak), ((c2a1 c2a2 ... c2aj), ...} i.e. the list of
the disjoint cycles in a permutation P.

Analysis:

For a
given cycle of length k, CYCLE_TO_TRANS will add exactly (k-1) transpositions
to the return list, without performing any additional calculations. Thus its
running time is Big-Theta(k) that is, there is a
linear upper bound on the worst case running time and a linear lower bound on
the best case running time. Assume that our input to PERM_TO_TRANS has j
cycles, with the i-th cycle having length l_i, and
the sum of the lengths l_i = n (since each element in
the permutation is in exactly one cycle). The total running time for
PERM_TO_TRANS will the sum of the running times of the j calls to
CYCLE_TO_TRANS, which we know each take (l_i 1)
operations. So we have

Total
operations = Sum(i=1 to j)
of (l_i 1)

=[Sum(i=1 to j) of (l_i)] j

=[ n ] j

= n-j

Thus the
worst case is where we have 1 cycle representing the entire permutation, which
results in (n-1) transpositions and is O(n). If we
have more than one cycle, then the total running time may decrease.

Problem 2)

Input:
array (array), last index of array (last) (assume 0-based arrays)

Procedure ins_sort_rec(array, last)

if
(last > 0)

ins_sort_rec(array,
last-1) //recursive
call!

compare = array[last]

previous = last 1

repeat until previous = -1 OR array[previous] < compare

array[previous + 1] = array[previous]

previous = previous 1

end repeat

array[previous+1] = compare

end
if

end procedure

initial
call: ins_sort_rec(array, array.length
1)

Worst Case
Analysis:

If we are
sorting an array of n items, we will make exactly n calls to ins_sort_rec. The actual work of the algorithm is
performed in the body of the repeat loop, where we are shifting all of the
items in the (sorted) subarray to the left of the
item in question that are >= that item over in the array, one at a time. In
the worst case, the repeat loop for inserting item k into the (sorted) subarray with (k-1) items could execute k-1 times,
requiring k-1 shift operations. If we assume this worst case holds at each
level of recursion, we have

Total
shifts = Sum(i=1 to n) i-1

= (n-1)*n / 2

= O(n^2).

Best Case
Analysis:

Clearly
the best case is where the input array is pre-sorted. No shifts will be
performed; we just have the overhead of n levels of recursion, and a single
comparison of each item with the previous item in each level. This is O(n).

Average
Case Analysis:

Similar to
our claims for worst case, we have a number of shifts that we may need to
perform in the repeat loop for a given level of recursion. For a particular
element e_k requiring insertion into a sorted array
of k-1 elements, we expect (k-1)/2 of the items to be less than e_k, and (k-1)/2 to be larger. This results in (k-1)/2
shifted elements for this level of recursion. Thus

Total
shifts = Sum(i=1 to n) (i 1)/2

= (n-1)*n/4

= O(n^2)

Problem 3) [Solution courtesy of Scott Stoness]

i)

Clearly,
we cannot have more inversions than there are distinct pairs of numbers,

which is simply n^2. However, it must be noted that the
order in which the

elements of the pair are chosen is immaterial, since under
no circumstances can

both (i, j) and (j, i) be an inversion (e.g. either A[i] > A[j] or A[j] > A[i], but

not both). By similar reasoning, (i, i) cannot
be an inversion, since it is never

the case that A[i] > A[i]. Thus,
we are left with the problem of counting how

many different ways we can choose 2 distinct elements
from a set of n elements,

where order doesnt matter: this is
exactly nCr2 = n*(n-1) / 2

The
permutation with the most inversions can thus be easily shown to be the

reverse sorted list; each element then participates in an
inversion with each and

every element following it in the list. Thus, we end up
with the summation:

(n-1) + (n-2) + ... + 2 + 1 + 0 = Sum(i=0 to n-1) i = n*(n-1)/2 as desired.

ii)

Clearly,
they are positively correlated

Insertion
sort with no inversions runs in O(n) time, as each
element is simply

tacked onto the end of the array as it is built. When we
are inserting an

element, note that we will have to move it to the left
exactly as many places

as inversions it participates in as the left hand
element. More formally, the

inner loop of insertion sort will run |S| times when
inserting element s, where

S = {(i, s)|(i, s) is an inversion}.

We can
see that it must run at least |S| times,
since if (i, s) is in S, i < s yet

A[i] < A[s]. Thus A[s] must
appear earlier in the final list than A[i], and we

know that insertion sort walks down the list in order,
so A[i] has already been

inserted, and A[s] has to
be swapped with it.

We can
also observe that it must run at most |S| times,
by observing that the

invariant for insertion sort is that when we insert a new
element s into the

array, the first s − 1
elements are already sorted. Let k be the
index such that

(k, s) is in S, and A[k] is
minimal. In the sorted list (of size s−1), everything
to the

right of A[k] is
larger than it, and in an inversion with s. Take
an element with

original index m is such
that in the sorted list it is to the right of A[k].
Clearly,

then, A[m] > A[k], and
since A[s] < A[k], A[s] < A[m].
Furthermore, since m

has already been inserted, m <
s. Thus, (m, s) is an inversion. Therefore,
only

the last |S| elements
in the sorted list of size s−1 are in
inversions with s, and

the inner loop of insertions sort will run only |S| times.

Thus, we
can specify the running time of insertion sort as O(n + I), where
I is

the number of inversions.

iii)

Modify MergeSort so that during the Merge operation, whenever we
select an

element from the right hand sub-array, we increment the
inversion count by the

number of elements in the left hand sub-array.

This
modification results in an algorithm which is still O(nlogn) (just as is basic

MergeSort), as our modifications to Merge simply consist of
adding an integer to

a global inversion counter, which is clearly
constant time, and keeping track of

the number of elements in the left-hand list, which we
can do by an initial O(n)

count, and then a decrement of this counter everything
we take something

off the right hand list. Thus, Merge is still O(n), and our modified MergeSort

is thus O(nlogn), since we
changed nothing but Merge.

Does
this work? Were clearly not counting anything that is
not an inversion;

note that when Merge begins, the original index of
everything in the right hand

list is greater than the original index of anything in
the left hand list. Thus,

when we pull something off the right hand list, it has
a smaller value than,

but a larger index than, everything left on the left
hand list, which is the very

definition of inversion. Have we missed any inversions? That
would require (i, j)

to be an inversion, but to never be in a position
where A[i] and A[j] were
on

separate sides of a Merge; intuitively, it seems true that
every pair of indices are

on different sides of a Merge at some point during MergeSort, but this would

require proof for a rigourous
answer.

Problem
4)

i)

Claim: (1 1)^n = (1 n)

(0 1) (0 1)

Proof by
induction on n:

Base
Case: n = 1.

(1 1)^1 = (1 1)

(0
1) (0 1)

Inductive
Hypothesis: assume that it holds for case n:

(1 1)^n = (1 n)

(0
1) (0 1)

Want to
show that case (n+1) holds.

From the
I.H., we have

(1 1)^n = (1 n)

(0
1) (0 1)

right-multiplying both sides by (1 1)
gives

(0 1)

(1 1)^n * (1 1) = (1 n) * (1 1)
<=> (1 1)^(n+1) = (1*1+0*n 1*1+1*n) = (1 n+1)

(0
1) (0 1) (0 1)
(0 1) (0 1) (0*1+1*0 0*1+1*1) (0 1 )

which is exactly the (n+1) case.

ii)

We wish
to prove (n-r)!.r! | n! for all n and for
all r (with 0<=r<=n). This is equivalent to proving that n! / (n-r)!*r! is an integer. Let
this second formulation be our claim, P(n).

Proof by induction on n (not r!)

Base Case: n=1. we have 2 cases:

` r = 0: 1! / 1!0! = 1 which is an integer`

` r = 1: 1! / 0!1! = 1 which is an integer`

` `

`Inductive Hypothesis: Assume case n to be true:`

n! / (n-r)!*r! is an integer for all r 0<=r<=n.

`Want to show: `

`(n+1)! / (n+1 - r)!*r! is an integer for all r 0<=r<=n+1.`

`Initially, let us restrict r to the range 1<=r<=n. We can then apply two instances of our inductive hypothesis as follows:`

` n! / (n-r)!r! + n! / (n-(r-1))!(r-1)! = sum of two integers = an integer.`

`= n!*((n+1-r)+r) / (n+1-r)!*r! `

`= (n+1)! / (n+1 r)!r! = an integer.`

` `

` `

This is
the form of case (n+1), although we arent quite finished. We need to show that
(n+1)! / (n+1 r)!r! is an integer for all r
0<=r<=n+1, and we have only shown it for 1<=r<=n. Consider
the missing cases:

r=0: (n+1)! / (n+1 0)*0! = (n+1)! / (n+1)! =
1 which is an integer

r=n+1: (n+1)! / (n+1 n+1)!*(n+1)! = (n+1)! / (n+1)!
= 1 which is an
integer.

Thus we have shown that (n+1)! / (n+1 r)!r!
is an integer for the entire desired range, 0<=r<=n+1,
and our proof is complete.

Problem 4 iii)

Verification of hint 1:

C(n,r) = n! / (n-r)!r! = n! / r!(n-r)! = n! /
(n-(n-r))!(n-r)! = C(N,n-r)

Verification of hint 2:

` n! n!`

` C(n,r) + C(n,r+1) = --------- + ---------------`

` (n-r)! r! (n-r-1)! (r+1)!`

` n! (r+1) n! (n-r)`

` = ------------- + -------------`

` (n-r)! (r+1)! (n-r)! (r+1)!`

` n! (n-r+r+1)`

` = -------------`

` (n-r)! (r+1)!`

` (n+1)!`

` = -------------------`

` (n+1-(r+1))! (r+1)!`

` = C(n+1,r+1)`

`Claim: (a+b)^n = Sum[C(n,k) a^k b^(n-k), {0<=k<=n}] for n >= 1`

Proof by induction on n.

`Base Case: case n = 1`

`(a+b)^1 = a + b = C(1,0)*a^0*b^1 + C(1,1)*a^1*b^0 as desired.`

`Inductive hypothesis: assume case n `

`(a+b)^n = Sum[C(n,k) a^k b^(n-k), {0<=k<=n}]`

We
wish to show that case (n+1) holds:

`(a+b)^n = Sum[C(n,k) a^k b^(n-k), {0<=k<=n}] (ind. Hyp)`

` => `**(a+b)^(n+1)** = (a+b)Sum[C(n,k) a^k b^(n-k), {0<=k<=n}] (mult each side by (a+b)

`= Sum[C(n,k) a^(k+1) b^(n-k), {0<=k<=n}]`

` + Sum[C(n,k) a^k b^(n-k+1), {0<=k<=n}] (distributing over +)`

`= Sum[C(n,k) a^(k+1) b^(n-k), {0<=k<=n}]`

` + Sum[C(n,k+1) a^(k+1) b^(n-k), {-1<=k<=n-1}] (index shift)`

`= Sum[C(n,k) a^(k+1) b^(n-k), {0<=k<=n-1}]`

` + C(n,n) a^(n+1) b^0 + C(n,0) a^0 b^(n+1)`

` + Sum[C(n,k+1) a^(k+1) b^(n-k), {0<=k<=n-1}] (pull out first, last terms of 2`^{nd} sum)

`= Sum[(C(n,k)+C(n,k+1)) a^(k+1) b^(n-k), {0<=k<=n-1}]`

` + a^(n+1) + b^(n+1) (combining summations)`

`= Sum[C(n+1,k+1) a^(k+1) b^(n-k), {0<=k<=n-1}] `

` + a^(n+1) + b^(n+1) (hint 2)`

`= Sum[C(n+1,k) a^k b^(n+1-k), {1<=k<=n}] + a^(n+1) + b^(n+1) (index shift)`

= Sum[C(n+1,k) a^k b^(n+1-k), {0<=k<=n+1}].

`This is precisely case (n+1)`

Problem
4, iv)

This is
really just an instance of what we proved in iii), where a = b = 1 (so really,
we have already proven this.). We can prove it here using a similar proof by
induction:

Claim: 2^n = Sum[C(n,k), {0<=k<=n}] for n >= 1

`Base Case: n = 1`

`2^1 = 2 = 1 + 1 = C(1,0) + C(0,1) good.`

`Inductive Hypothesis: assume case n`

`2^n = Sum[C(n,k), {0<=k<=n}]`

`Want to show case (n+1): 2^(n+1) = Sum[C(n+1,k), {0<=k<=n+1}]`

`2^n = Sum[C(n,k), {0<=k<=n}] (ind. Hyp)`

` => `**2^(n+1)** = 2*Sum[C(n,k) a^k b^(n-k), {0<=k<=n}] (mult each side by 2)

`= (1+1)*Sum[C(n,k) a^k b^(n-k), {0<=k<=n}]`

`= Sum[C(n,k), {0<=k<=n}]`

` + Sum[C(n,k), {0<=k<=n}] (distributing * over +)`

`= Sum[C(n,k), {0<=k<=n}]`

` + Sum[C(n,k+1), {-1<=k<=n-1}] (index shift)`

`= Sum[C(n,k), {0<=k<=n-1}]`

` + C(n,n) + C(n,0)`

` + Sum[C(n,k+1), {0<=k<=n-1}] (pull out first & last terms of 2`^{nd} sum)

`= Sum[(C(n,k)+C(n,k+1)), {0<=k<=n-1}]`

` + 1 + 1 (combining summations)`

`= Sum[C(n+1,k+1), {0<=k<=n-1}] `

` + 1 + 1 (hint 2)`

`= Sum[C(n+1,k), {1<=k<=n}] + 1 + 1 (index shift)`

`= Sum[C(n+1,k), {1<=k<=n}] + C(n+1,0) + C(n+1,n+1) `

= Sum[C(n+1,k), {0<=k<=n+1}].

Which is precisely case (n+1).

Problem
5)

In the
(positive integer) Euclidean algorithm, our goal is to find the gcd of two positive integers, j >= k. We understand that
the quotient and remainder, q and r, of j/k are uniquely determined to satisfy
the relation

j = k*q + r
where q
>= 0 and 0 <= r < k

We then
note that gcd(j,k) = gcd(k,r), since r = j k*q will still divide all of the common
factors of j and k, and any common factors of (k,r)
is a factor of j as well.

With
polynomials in a single variable with real coefficients, we can make a similar
statement. For any two non-zero polynomials f(x), g(x), with degrees deg(f) >= deg(g), it is true that there exist unique
polynomials q(x) and r(x) such that

f(x) = g(x)*q(x) + r(x) where deg(r) < deg(g) [this is called the Division Theorem]

We
define gcd(f(x),g(x))
as the monic (that is, whose lead coefficient is 1)
polynomial of highest order that both f(x) and g(x) divide evenly. We then
observe that

gcd(f(x),g(x)
= gcd(g(x),r(x))

We can
then present our Euclidean Algorithm for Polynomials. Assume that we have some
data structure Poly to represent a polynomial, and a support procedure POLYDIV(F,G) that returns the quotient and remainder
polynomials Q and R resulting from polynomial division as formulated above. Input
to POLYEUC are two polynomials F,G with deg(F) >=
deg(G) >= 0.

POLYEUC(F,G)

Poly num = F, denom
= G

while (denom.deg > 0)

(quot,rem) = POLYDIV(F,G)

num = denom

denom = rem

if (denom == 0) return num

else return 1

Let us
prove by induction on the degree of F that POLYEUC returns the gcd(F,G)
for all polynomials F and G satisfying the input conditions.

Base
Cases:

deg(F) = 0.

Thus deg(G) = 0. Thus POLYEUC(F,G)
immediately returns 1, which is the zero degree monic
polynomial that divides all other constants. (recall
that coefficients are reals, not necessarily integers
here
)

deg(F) = 1.

Thus deg(G) = 0 or 1. If deg(G) = 0,
then POLYEUC immediately returns F if G = 0, and 1 if G = 0. The gcd(F,0)
= F, and gcd(F,k) = 1 for
non-zero k.

Strong Inductive
Hypothesis:

POLYEUC(F,G) = gcd(F,G) for all
polynomials F with deg(F) <= n and deg(G) <= deg(f).

Want to
show the claim holds for case (n+1).

Assume F
has degree n+1.

If deg(G) = 0, then POLYEUC(F,G) returns F if G = 0, and 1
otherwise. This is the gcd(F,G).

If 0
< deg(G) < n+1, then we can say with certainty
that POLYEUC(F,G) will enter the while loop at least once. After one iteration,
0 <= deg(rem) < deg(g)
(from the division algorithm). We know that gcd(F,G)
= gcd(num, denom) = gcd(G,rem) after exactly one
iteration of the loop, that deg(num) < (n+1) since num = G, and deg(denom) = deg(rem) < deg(G)
< n+1 as well. If we were to execute POLYEUC(G, rem),
we would first arrive at the while test condition in the exact state that
POLYEUC(F,G) is in after 1 iteration of the loop, and thus both pieces of code
will return the same result. Thus we can say from the I.H. (since deg(G) <= n and deg(rem) <=
n) that this returned result is gcd(G,rem), which we have already determined = gcd(F,G).

The
final case is where deg(F) = deg(G) = n+1. In this
case, we enter the while loop and after one iteration have num = G, denom = rem, with deg(G) = n+1 and deg(rem) <
n+1. Thus we cannot yet apply our inductive hypothesis. If deg(rem) = 0, we know we return gcd(F,G)
as described in the first case of our proof. Otherwise, we will enter the loop
again, and after one more iteration we will have num = rem
and denom = rem2, with deg(num)
< n+1 and deg(rem2) < n+1 as well. Thus we can now apply the I.H. to find
that the result will be the gcd(rem, rem2). From our loop
invariant, we know that gcd(F,G) = gcd(G, rem) = gcd(rem, rem2), and thus POLYEUC(F,G) returns gcd(rem,rem2) = gcd(F,G) as
desired.

Thus we
have shown that POLYEUC(F,G) = gcd(F,G)
for all polynomials F with deg(F) <= n+1 and G with deg(G) <= deg(F), and
our proof is complete.