COMP4500/7500 Advanced Algorithms & Data Structures Tutorial Exercises 3 (2014/2)∗
School of Information Technology and Electrical Engineering, University of Queensland
August 27, 2014
This material aims to familiarise you with analysing programs to determine a formula that characterises their running times, and with graph representations and algorithms. It is important that you attempt to derive the required algorithms. A good treatment of elementary graph algorithms may be found in CLRS Chapter 22 [3rd, 2nd]; CLR Chapter 23 [1st].
1. UsingΘ-notation(ratherthanO-notation),givetheworst-caseexecutiontimecomplexitiesofacallP(n),where the argument n is a positive integer.
P(n)
1 fori=1ton
2 Q(i) given that
(a) the execution time of Q(i) is Θ(1) (b) the execution time of Q(i) is Θ(n) (c) the execution time of Q(i) is Θ(i) (d) the execution time of Q(i) is Θ(n2) (e) the execution time of Q(i) is Θ(i2)
2. Using Θ-notation, give the worst-case time complexity of a call P(n), where the argument n is a positive integer: P(n)
1 2 3 4 5 6 7 8
fori=1ton
if i mod 5 == 0
for j = 1 to i fork = 1ton
// statements taking Θ(1) time else / i mod 5 ̸= 0
for j = 1 to i
// statements taking Θ(1) time
3. Consider the following merge procedure as used in implementing merge sort. It merges two segments of array: array[left..middle] and array[middle+1..right]. Each of these segments is assumed to be in order before the merge takes place.
// This file contains the Java code from Program 15.15 of
// “Data Structures and Algorithms
// with Object-Oriented Design Patterns in Java”
// by Bruno R. Preiss.
//
// Copyright (c) 1998 by Bruno R. Preiss, P.Eng.
// All rights reserved.
//
// http://www.pads.uwaterloo.ca/Bruno.Preiss/books/opus5/
// programs/pgm15_15.txt
∗Copyright ⃝c reserved August 27, 2014
1
COMP4500/7500 (2014) Tutorial Exercises 3 (August 27, 2014) 2
//
public class TwoWayMergeSorter
extends AbstractSorter
{
Comparable[] tempArray;
protected void merge (int left, int middle, int right)
{
int i = left;
int j = left;
int k = middle + 1;
while (j <= middle && k <= right)
{
if (array [j].isLT (array [k]))
tempArray [i++] = array [j++];
else
tempArray [i++] = array [k++];
}
while (j <= middle)
tempArray [i++] = array [j++];
for (i = left; i < k; ++i)
}
// ... }
array [i] = tempArray [i];
Carefully analyse the performance of procedure merge to give a worst case upper bound on its time complexity. All individual variable assignments take constant time as do comparisons and numeric operations. What is the space overhead of this procedure in Θ notation?
4. (See CLRS Exercise 22.1-2, p592 [3rd], p530 [2nd], CLR Exercise 23.1-2, p468 [1st])
Give an adjacency-list representation for a complete binary tree on 7 vertices. Give an equivalent adjacency- matrix representation. Assume that the vertices are numbered 1 to 7 with 1 as the root of the tree, 2 and 3 as its children, 4 and 5 as the children of 2, and 6 and 7 as the children of 3.
5. (See CLRS Exercise 22.1-1, p592 [3rd], p530 [2nd], CLR Exercise 23.1-1, p468 [1st])
(a) The out-degree of a vertex is the number of edges leaving the vertex. Give an abstract algorithm to compute the out-degrees of all vertices of a directed graph and for each vertex u set u.od to its out-degree. It is to be abstract in the sense that we do not want to worry about implementation details of the underlying data structures. You may use the abstract for loop
for each vertex u ∈ G.V “process vertex u”
to traverse the vertices of the graph G, and the abstract for loop for each vertex v ∈ G .Adj[u]
“process edge (u, v)”
to traverse the edges (u, v) adjacent to u.
(b) Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? Give your analysis in terms of the number of vertices, abbreviated |V |, and number of edges, abbreviated |E|, of the graph. What assumptions do you make in this analysis?
(c) Give an algorithm using abstract for loops as above to determine the in-degrees of all the vertices of a directed graph. The in-degree of a vertex is the number of edges entering the vertex. How long does it take to compute the in-degrees?
COMP4500/7500 (2014) Tutorial Exercises 3 (August 27, 2014) 3
(d) Outlineaproceduretocomputetheout-degrees,butthistimeratherthanusingtheabstractforloops(which are not available in most languages), do so in Java-like pseudocode. This will require you to design (but not necessarily implement) appropriate traversal procedures. You should indicate both algorithmic and data structure ideas that are used.
(e) Consider how the corresponding in-degree problem could be solved.
6. (See CLRS Exercise 22.1-3, p592 [3rd], p530 [2nd], CLR Exercise 23.1-3, p468 [1st])
ThetransposeofadirectedgraphG=(V,E)isthegraphGT =(V,ET),where ET ={(v,u)∈V ×V |(u,v)∈E}.
Thus,GT isGwithallitsedgesreversed.
(a) Describe an algorithm for computing GT from G, for an adjacency-list representation of G. Assume the existence of a procedure INITGRAPH(G) for initialising a graph G to the empty graph, and methods G.ADDVERTEX(u) to add a vertex u to a graph G, and G.ADDEDGE(u, v) to add an edge from u to v to a graph G. Analyse the running time of your algorithm.
(b) Giveatransposealgorithm,butthistimeusingadjacency-matrixrepresentation,whereG.edgeisaboolean matrix with both the rows and columns indexed by vertices, so that G.edge[u, v] is TRUE if and only if there is an edge from u to v in G.
Analyse the running time of your algorithm.