CSC 226 ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 1 – PROGRAM AND WRITTEN

Description

1 Programming Assignment
The assignment is to design and implement the LinearSelect algorithm and compare it to the QuickSelect
algorithm. The problem is defined as follows:
Input: An array 𝐴 of 𝑛 integers and a positive integer 𝑘.
Output: The 𝑘𝑡ℎ smallest element in array 𝐴.
Your task is to write a java program, stored in a file named LinearSelect.java, that contains a class,
LinearSelect, which takes an integer array 𝐴 and a positive integer 𝑘 as its only arguments, and returns the
𝑘𝑡ℎ smallest value. You are provided with the file QuickSelect.java which you may use as a template for
LinearSelect.java. The only changes that need to be made to QuickSelect.java are the names of the class
and some functions as well as the entire pivot selection function pickRandomPivot(). That is, instead of
picking a random pivot, you pick the pivot using the median of medians algorithm. Below I have given a
pseudocode version of this algorithm in-place. You may use it or some variation of it or something else
entirely in your code, as long as it is finding a good approximation of the median in linear time.
Algorithm pickCleverPivot(left, right, A)
Input: Array A and left and right indices marking the endpoints of subarray of size n
within A you are currently recursing on
Output: The median of medians, m, of the subarray in A from index left to index right.
if n ≤ 5 then
return the median of the subarray of elements (using any method)
Divide subarray in A into ⌈𝑛/5⌉ groups of 5 (or possibly less for the last group) elements
for i  1 to ⌈𝑛/5⌉ do
find the median of each group (using any method)
collect the medians above together at the front of subarray of A
return pickCleverPivot(left, left+⌈𝑛/5⌉, A)

Once you have LinearSelect running you are to compare it to QuickSelect by measuring their running
times on arrays of sizes 𝑛 = 25, 125, 625, 3125, 15625, 78125, and 390625, respectively, given in the
provided text files. Each file consists of 𝑛 + 1 values between 1 and 𝑛, (not necessarily distinct.) The first
value in the file is 𝑘, and the rest are the 𝑛 inputs for the array.
The main() function is designed to read the contents of a text file provided on the command line, for
example
C:\> java QuickSeleck selection_test25.txt
and separate the data into int k and int[] array. It then calls QS(array, k), measures the run time of the
program in nanoseconds and reports the results.
2 Test Datasets
A set of input files containing test data are available in the ‘Assignments’ folder under the ‘Resources’ tab
on ConneX, sorted by their size. You should ensure that your implementation gives the correct answer on
these test files before submitting. It may also be helpful to test your implementation on a variety of other
inputs, since the posted data may not cover all possible cases. Depending on the running time of your
algorithm, it may not be able to process some of the larger input files.
3 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated testing
(using large test arrays similar to the ones posted on ConneX) and human inspection. To receive the full
25 marks I would like you to go to the end of your written assignment and report your findings comparing
QuickSelect and LinearSelect and discuss.
Score Description
0 – 5 Submission does not compile.
5 – 15 The LinearSelect program runs in worse than 𝑂(𝑛)
time.
15 – 20 The LinearSelect program runs in 𝑂(𝑛) time.
20 – 25 The LinearSelect program runs in 𝑂(𝑛) time and
the comparative analysis is included.
To be properly tested, every submission must compile correctly as submitted. If your submission does
not compile for any reason (even trivial mistakes like typos), it will receive at most 5 out of 25. The
best way to make sure your submission is correct is to download it from ConneX after submitting and test
it. You are not permitted to revise your submission after the due date, and late submissions will not be
accepted, so you should ensure that you have submitted the correct version of your code before the due
date. ConneX will allow you to change your submission before the due date if you notice a mistake. After
submitting your assignment, ConneX will automatically send you a confirmation email. If you do not
receive such an email, your submission was not received. If you have problems with the submission
process, send an email to the instructor before the due date.

CSC 226 FALL 2016
ALGORITHMS AND DATA STRUCTURES II
ASSIGNMENT 1 – WRITTEN
UNIVERSITY OF VICTORIA
1. Consider the insertion of items with the following keys (in the given order) into an initially empty
AVL tree: 30, 40, 24, 58, 48, 26, 11, 13, 17. Draw the resulting AVL trees after each insertion (nine
of them).
2. What is the minimum number of internal nodes in an AVL tree of height 5? Draw such a tree.
3. Given functions 𝑓, 𝑔: ℕ → ℝ, prove that 𝑓(𝑛) ∈ (𝑔(𝑛)) if and only if 𝑓(𝑛) ∈ O(𝑔(𝑛)) and 𝑓(𝑛) ∈
(𝑔(𝑛)).
4. Consider the version of selection sort I gave you in lecture 2, shown below:
Algorithm selectionSort(A,n):
Input: Array A of size n
Output: Array A sorted
for k  0 to n–2 do
min  k
for j  k+1 to n–1 do
if A[j] < A[min] then
min  j
end
end
swap(A[k], A[min])
end
end
Draw the decision tree associated with running this algorithm on a sequence of 3 distinct values, say
𝑆 = [𝑥0, 𝑥1, 𝑥2], where each 𝑥𝑖 ∈ {1,2,3}. Label each internal node with the comparison done at that
node in terms of 𝑥𝑖
(for example, 𝑥𝑖 < 𝑥𝑗
) and label each external node with the actual sequence 𝑆
that leads the algorithm towards that external node. Note, your results should be consistent, meaning
each path can correspond to at most one permutation of the original data.
5. Suppose you would like to sort 𝑛 music files, but you only have an old, unreliable computer, which
you have nicknamed “Rustbucket”. Every time Rustbucket compares two music files, 𝑥 and 𝑦, there
is an independent 50-50 chance that it has an internal disk fault and returns the value -1, instead of the
correct result of 1 for true or 0 for false, to the question, “𝑥 ≤ 𝑦?” Otherwise, Rustbucket correctly
performs every other kind of operation (including comparisons not involving music files.) Describe
an efficient algorithm that can use Rustbucket to sort 𝑛 music files correctly and show that your
algorithm has expected running time that is 𝑂(𝑛 log 𝑛).