CS 4349 — Advanced Algorithm Design and Analysis, Homework 1
Question 1
a
b
After the k-th iteration of the outer loop, the k-th largest element of the array will at be the n-i+1th index. For example, after the first iteration of the outer loop, the largest element of the array will be at the nth index of the array.
c
The outer loop uses loops for an input array of length . The last loop is redundant, as it is guaranteed that the smallest index will be located at index and indices will already be sorted. Therefore, no swaps will be performed. This is additional comparison is asymptotically negligible however.
Question 2
where We must show that Proof. Basis : We must show that .
Inductive Step:
We assume that as our inductive hypothesis.
We must show that
Question 3
There is no greatest negative rational number Proof. Assume for contradiction that there is a greatest rational number. This then may be denoted as , where .
Take another number . , and therefore is greater than . This is a contradiction, thus there is no greatest rational number.
Question 4
a
Does and both hold for two functions?
Yes. since and
b
Prove by counterexample that is false.
Assume . Informally, this means that if a function is upper bounded by a function , then it must also be lower bounded by . For counterexample, take . . However, .
Thus,
c
Prove directly that
This follows from the definition of .
A function is for all
Since , it is trivially true that for all .
d
Prove by counterexample that
A function is for all .
Note that
For counterexample, assume there is exists a for which for some . This means that for n > , however this is a contradiction since must be strictly greater than , and for
Question 5
In the first iteration of the loop, comparisons (and swaps) will be required to move the smallest element of the array to the th index of the array. In the second, the previously sorted elements need not be compared, so swaps will be necessary.
This pattern continues until only swap is necessary.
.
For insertion sort, this means that comparisons will be necessary.