# COMP1201 Assignment 1 solution

\$25.00

Original Work
Category:

## 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.
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.
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?