SCHOOL OF ENGINEERING AND TECHNOLOGY
TCSS 343 – Assignment 3
October 28, 2019
1 GUIDELINES
Homework should be electronically submitted to the instructor by midnight on the due date. A submission link is provided on the course Canvas Page. The submitted document should be typeset using any common software and submitted as a PDF. We strongly recommend using LATEX to prepare your solution. You could use any LATEX tools such as Overleaf, ShareLatex, TexShop etc. Scans of handwritten/hand drawn solutions are not acceptable.
Each problem is worth the indicated number of points. Solutions receiving full points must be correct (no errors or omissions), clear (stated in a precise and concise way), and have a well organized presentation. Show your work as partial points will be awarded to rough solutions or solutions that make partial progress toward a correct solution.
Remember to cite all sources you use other than the text, course material or your notes.
1
2 PROBLEMS
2.1 UNDERSTAND
In this problem use the Master Theorem to find and prove tight bounds for these recurrences (2 points each).
1.
2.
3.
4.
5.
Grading You will be docked points for errors in your math, disorganization, lack of clarity, or incomplete proofs.
2.2 EXPLORE
Forthefollowingproblemsstatedaspseudo-code,let A[l…r]denotethesublistoftheinteger list A from the l-th to the r-th element inclusive, let Quad(A[1…n]) denote an algorithm that runs in time Θ(n2), and let Flash(A[1…n]) denote an algorithm that runs in time Θ(nlogloglogn).
T(n)= 243Tn+nn ifn≥27
T (n) =
c
8T n + 16n
if n < 4 if n ≥ 4
if n < 2 ifn≥2
c if n < 27 27
T(n)= 5Tn+n ifn≥25
c if n < 25 25
4
T(n)= 4n lg7
c 5T 7 +n
c
T(n)= 3n 3 2
Foo(A[1...n])
If n≤2 Then Return // nothing to do
Quad(A[1...n])
Foo(A[1...⌊2n ⌋]) 3
if n ≤ 1 4T7+nn ifn>1
Foo(A[⌊n ⌋…n]) 3
Quad(A[1…n]) End Foo.
2
(2points)1. StatearecurrencethatgivesthecomplexityT(n)foralgorithmFoo. (2points)2. FindthetightcomplexityofalgorithmFoo.
Bar(A[1…n])
If n≤1 Then Return // nothing to do
Bar(A[1…⌊2n ⌋]) 3
Flash(A[1…n]) End Bar.
(2points)3. StatearecurrencethatgivesthecomplexityT(n)foralgorithmBar. (4points)4. FindthetightcomplexityofalgorithmBar.
2.3 PROGRAMMING
The Quicksort algorithm has a Θ(n2) worst case complexity even though it is only Θ(n logn) on average. Our goal here is to observe the impact of this behavior difference in practice. We will also explore the space complexity of Quicksort. You must submit your program as part of your homework.
(2points)1.
WritetwoversionsofthePivotprocedurefortheQuicksortalgorithm:oneversion
public void int Pivot1st(Comparable[] a, int l, int r) { /* …*/
}
that takes the first element a[l] of the input array as pivot, and one version
public void int PivotMid(Comparable[] a, int l, int r) { /* …*/
}
thattakesthemiddleelementa[(l + r)/2]aspivot.
Each version should return the index p on array a[] where the pivot element lies after the pivoting process is finished, so that the following set of methods becomes complete and correct (i.e. a call to either Quicksort1st(a) or QuicksortMid(a) sorts the input array):
public void Quicksort1st(Comparable[] a, int l, int r) { if (r > l) {
int p = Pivot1st(a, l, r);
Quicksort1st(a, l, p – 1);
Quicksort1st(a, p + 1, r);
3
} }
public void Quicksort1st(Comparable[]
Quicksort1st(a, 0, a.length – 1);
}
public void QuicksortMid(Comparable[] if (r > l) {
int p = PivotMid(a, l, r);
QuicksortMid(a, l, p – 1);
QuicksortMid(a, p + 1, r);
} }
public void QuicksortMid(Comparable[]
QuicksortMid(a, 0, a.length – 1);
}
(5points)2. Writeaprogramthat:
a) {
a, int l, int r) {
a) {
a) createstwocopiesa1st[]andamid[]ofarandomarrayofnintegers(wherenis a program input),
b) sortsthembyinvokingrespectivelytheQuicksort1standQuicksortMidmeth- ods above,
c) outputsthetimeneededforeachofthesetwocalls,
d) thencallsthesamemethodsagainonthesortedarrays,
e) outputsthetimeneededforeachofthesetwocalls.
(3 points) 3. Execute your programs for successive powers of 10: n = 10, 000, n = 100, 000, n = 1,000,000, n = 10,000,000. Show the results on a comparative table. What are the execution times in each case, and what is the largest value of n that can be used from this list for each program? (NB: be prepared to handle stack overflows).
(bonus5points)4. ModifyyourprogramtousethisversionofQuicksortwherethefirstrecursivecallalways handles the shorter segment of the partitioned array first, and the second recursive call is replaced by a simple iteration, then repeat the above test (NB: xxx stand for either 1st or Mid as before):
public void SafeQuicksortxxx(Comparable[] a, int l, int r) { while (r > l) {
int p = Pivotxxx(a, l, r); if (p – l <= r - p) {
4
} }
SafeQuicksortxxx(a, l, p – 1); // shorter part
l = p + 1; // emulate SafeQuicksortxxx(a, p + 1, r) } else {
SafeQuicksortxxx(a, p + 1, r); // shorter part
r = p – 1; // emulate SafeQuicksortxxx(a, l, p – 1) }
public void SafeQuicksortxxx(Comparable[] a) { SafeQuicksortxxx(a, 0, a.length – 1);
}
A stack overflow means that here are too many pending recursive calls. What is the maximum stack size for Quicksortxxx and for SafeQuicksortxxx given an input of size n? (Just state a Big-Theta expression for the stack size rather than an exact value).
Grading Correctness and precision are of utmost importance. Use formal proof structure for the Big-Theta bounds. You will be docked points for errors in your math, disorganization, lack of clarity, or incomplete proofs.
5