The Australian National University Research School of Computer Science
COMP3600/6466 – Algorithms
This tutorial is compiled by:
Cormac Kikkert, William Cashman, Timothy Horscroft, and Hanna Kurniawati
Exercise 1 C++ and Empirical Analysis Algorithm 1 getMaximum(An array of integers A)
Semester 2, 2020 Tutorial 4
1: 2: 3: 4: 5:
Lett=−∞ fori=1toA.lengthdo
if A[i] > t then Set t = A[i]
Return t
1. Read the “Introduction to C++ Guide” (https://cs.anu.edu.au/courses/comp3600/ introToCPP.pdf) and follow along with the exercises to make a program that implements the above algorithm to find the maximum of a set of numbers in a file.
2. Please augment the program you have implemented Q1, so that you can capture the CPU time required to run your implementation of getMaximum.
3. Please write a program to generate random numbers for you to test the program you implemented in Q2 on a variety of input size, especially on large input size.
4. Please empirically analyse the running time of your implementation of getMaximum.
Hint: You might want to use the program you wrote in Q3 to generate a variety of input sizes, use them as the inputs to your implementation of getMaximum, gather the running time of each run, and fit the pairs of input size – running time data you gathered into a linear function.
5. Please find a tight asymptotic upper bound for the average case running time of getMaximun and compare your theoretical analysis with your results in Q4. You can assume the elements of A are uniformly distributed and independent of each other, and that each element is unique.
Note: Ideally, you do this question before Q4, and the results of this theoretical analysis becomes a guess on the function you fit your data into in Q4. However, to ensure sufficient time to get you started on C++, in this tutorial, we swap the order.
Exercise 2 Randomized Algorithms and Its Analysis
1. Recall RandQuickSort from the lecture. What value would the function Partition(A, p, r) returns
if all elements of A[p,···,r] have the same value? How should we change Partition(A, p, r) if we want
this function to return ⌊ p+r ⌋ when all elements of A[p,···,r] have the same value? 2
2. Is it useful to analyse the worst case analysis of a randomized algorithm? Please explain why or why not.
3. Suppose A is an array of integers. Will the algorithms below return a random permutation of the input array? Please explain why or why not.
(a)
Algorithm 2 Permutation1(A)
1: n = A.length
2: Let B[1···n] be a new array 3: offset = Random(1, n)
4: fori=1tondo
5: dest = i + offset
6: if dest > n then
7: dest = dest − n
8: B[dest] = A[i]
9: return B
Algorithm 3 Permutation2(A)
1: n = A.length
2: fori=1tondo
3: Swap A[i] with A[Random(1, n)]
(b)
Exercise 3
Exercise 4
Exercise 5
Leftover Questions from Last Tutorial
Q&A on A2 and Final Project
Optional Exercises
Note: The questions in this part of the tutorial tend to be harder. You need to finish the above exercises first before working on the questions below
1. It is known that for an almost sorted array, in general, Insertion Sort is faster than Quick Sort. Please explain why.
2. Utilising the above information about Insertion Sort, one can improve the Rand Quick Sort algo- rithm we discussed in class by running Rand Quick Sort until the array is almost sorted and then completing the sort using Insertion Sort. Specifically, one can terminate the Rand Quick Sort when the sub-arrays are of size k, and continue sorting using Insertion Sort on the entire array. Please theoretically analyse:
(a) The asymptotic upper bound on the average case running time of the modified Rand Quick Sort above.
(b) A suitable value for k.