COMP90038 Tutorial Week 3 Solution

Plan
We provide more exercises than we can cover in the tutorial, so that you have more to practice on in your own time.
The exercises
15. For each of the following pairs f, g, determine whether f(n) ∈ O(g(n)), or g(n) ∈ O(f(n)), or both:
√
(a) f(n) = (n2 + 1 − n2)/2 and g(n) = 2n (b) f(n) = n2 + n n and g(n) = n2 + n
√
(c) f(n) = nlogn and (d) f(n) = n + logn and g(n) = n
(e) f(n) = 4nlogn + n and g(n) = (n2 − n)/2 (f) f(n) = (logn)2 and g(n) = 2 + logn
16. Show the steps of selection sort, when given the keys S, O, R, T, X, A, M, P, L, E.
17. One possible way of representing a polynomial
p(x) = anxn + an−1xn−1 + ··· + a1x + a0
is as an array A of length n + 1, with A[i] holding the coefficient ai.
(a) Design a brute-force algorithm for computing the value of p(x) at a given point x. Express this as a function Peval(A,n,x) where A is the array of coefficients, n is the degree of the polynomial, and x is the point for which we want the value of p.
(b) If your algorithm is Θ(n2), try to find a linear algorithm.
(c) Is it possible to find an algorithm that solves the problem in sub-linear time?
18. Trace the brute-force string search algorithm on the following input: The path p is ‘needle’, and the text t is ‘there_need_not_be_any’. How many comparisons (successful and unsuccessful) are made?
19. Assume we have a text consisting of one million zeros. For each of these patterns, determine how many character comparisons the brute-force string matching algorithm will make:
(a) 010001 (b) 000101 (c) 011101
20. Give an example of a text of length n and a pattern of length m, which together constitute a worst-case scenario for the brute-force string matching algorithm. How many character comparisons, as a function of n and m, will be made for the worst-case example. What is the value of m (the length of the pattern) that maximises this function? i.e. What is the worst case pattern length?
21. The assignment problem asks how to best assign n jobs to n contractors who have put in bids for each job. An instance of this problem is an n × n cost matrix C, with C[i,j] specifying what it will cost to have contractor i do job j. The aim is to minimise the total cost. More
formally, we want to find a permutation hj1,j2,...jni of h1,2,...,ni such that is minimized. Use brute force to solve the following instance:
Job 1 Job 2 Job 3 Job 4
Contractor 1 9 2 7 8
Contractor 2 6 4 3 7
Contractor 3 5 8 1 8
Contractor 4 7 6 9 4
22. Give an instance of the assignment problem for which the smallest item C[i,j] of its cost matrix is not included in its solution.