Description
Q1 Consider the java program TestSort found here:
https://secure.ecs.soton.ac.uk/notes/comp1201/assignment1/question1.shtml
This program generates an array of 100 random doubles and sorts them using three different algorithms: Insertion sort, Shell sort and Quick sort (the java default), outputting
the time taken by each algorithm.
(a) Modify TestSort to measure the running time on different sizes of arrays. Plot a
graph of the average run time against the size of the input. For this, you will need
to run the three algorithms for several arrays of the same size.
Note: Your answer should only include a brief summary of the modifications made
to the code, and the graph mentioned above. (2 marks)
(b) If a program runs in Θ(n
a
), (that is, T(n) ≈ c ∗ n
a
), then the logarithm of the run
time grows linearly with the logarithm of the size of the input. Take the logarithm
of the run time and array size for the previous data and re-plot your graph as a
log-log graph. (1 mark)
(c) Use the log-log graph to estimate the average-case time complexity of insertion sort.
(1 mark)
(d) Estimate the average running time of insertion sort on an array of size 1010. (1
mark)
Q2 Graph colouring is a classic problem described here:
http://en.wikipedia.org/wiki/Graph_coloring
Consider the Java program found here:
https://secure.ecs.soton.ac.uk/notes/comp1201/assignment1/question2.shtml
This program generates a random graph and then tries all possible colourings of the nodes.
It then shows the best colouring possible.
(a) Write a new class to measure the average run time of this program for problems of
size 12 to 17. Plot a graph of the logarithm of the run time against the problem size.
Note: Your answer should only include a brief description of your new class and
the graph mentioned above. (2 marks)
1
(b) From your measurements, estimate the average-case time complexity of the graphcolouring solver. Explain your working in detail. Is the answer what you expected,
and why? (3 marks)
Q3 This question considers a version of binary search trees which store elements of the form
hkey, valuei, with the key being used for comparisons (for the purpose of arranging
elements in the tree), and with duplicate keys being allowed.
(i) A simple way to implement such a binary search tree is to modify the insert operation
so that the new element is added to the left subtree when the key being added is
below that of the root, and to the right of the subtree when the key being added
is greater than or equal to that of the root. As with standard binary search trees,
new elements are inserted by creating new leaves. What is the time complexity of
inserting n elements with identical keys into an initially empty binary search tree?
Explain your answer in detail. (1 mark)
(ii) Now consider a different version of the insert operation, which keeps a boolean flag
at each node, and inserts an element with the same key either to the left subtree
or to the right subtree, depending on the value of the flag. The value of the flag
alternates between 0 and 1 every time a node is visited while inserting an element
with the same key. What is the time complexity of inserting n identical elements into
an initially empty binary search tree, with this modified insert operation. Explain
your answer in detail. (2 marks)
(ii) Finally, consider yet another implementation of binary search trees which allow
duplicate keys, which keeps a (singly) linked list of values associated to the same
key, and inserts into the list. What is the time complexity of inserting n identical
elements into an initially empty binary search tree, with this new implementation?
Explain your answer in detail. (2 marks)
2
