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 doesn’t 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? We’re 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 aren’t 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 2nd 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 2nd 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.