Tutorial
COMP20007 Design of Algorithms
Week 4 Workshop Solutions
1. Solving recurrence relations Solve the following recurrence relations, assuming T (1) = 1.
(a) T(n)=4n−3
T (n) = T (n−1)+4 means T (n−1) = T ((n−1)−1)+4 = T (n−2)+4, and T (n−2) = T (n−3)+4, and so on. Repeatedly substitute into the first equation, until the pattern becomes clear. Then, produce the base case to eliminate T.
T (n) = T (n − 1) + 4
= T (n − 2) + 4 + 4
= T (n − 3) + 4 + 4 + 4 .
= T (n − k) + k × 4 .
= T (n − (n − 1)) + (n − 1) × 4 = T (1) + (n − 1) × 4
= 1 + 4n − 4
= 4n − 3
(b) T (n) = n(n + 1) 2
T (n) = T (n − 1) + n
= T (n − 2) + (n − 1) + n
= T (n − 3) + (n − 2) + (n − 1) + n
.
= T (n − k) + (n − (k − 1)) + · · · + (n − 2) + (n − 1) + n
.
= T (n − (n − 1)) + (n − (n − 1 − 1)) + · · · + (n − 2) + (n − 1) + n = T (1) + (n − n + 1 + 1) + · · · + (n − 2) + (n − 1) + n
= 1 + 2 + · · · + (n − 2) + (n − 1) + n
= n(n + 1) 2
(starting to see the pattern?)
(bring in the base case)
(triangle numbers)
1
(c) T (n) = 2n − 1
T(n) = 2T(n−1)+1
= 2(2T(n − 2) + 1) + 1 = 22T(n − 2) + 2 + 1 =22(2T(n−3)+1)+2+1=23T(n−3)+22 +2+1
.
=2kT(n−k)+2k−1 +···+22 +2+1 .
=2(n−1)T(n−(n−1))+2(n−1)−1 +···+22 +2+1 =2n−1T(1)+2n−2 +···+22 +2+1
=2n−1 +2n−2 +···+22 +2+1
= 2n − 1 (sum of powers of 2 is the next power of 2, minus 1)
2. Mergesort complexity (optional) Recurrence relation:
T (n) = T n + T n + Θ(n) = 2T n + Θ(n)
where T (n) is the runtime of mergesort sorting n elements. The first T ( n2 ) is the time it takes to sort the left half of the input using mergesort. The other T ( n2 ) is the time it takes to sort the right half. Θ(n) is a bound on the time it takes to merge the two halves together.
We haven’t seen the master theorem in class yet, and for this question we aren’t required to solve the recurrence relation. However if we did want to solve this we can recognise that this recurrence relation fits the master theorem, with a = 2, b = 2, and d = 1.
logb(a) = log2(2) = 1 = d so, by the master theorem, T (n) ∈ Θ(n log n).
3. Subset-sum problem First, we’ll cover some terminology. The power set of a set S – often denoted P(S) – is the set of all subsets of S, e.g., if S = {1, 2, 3} then,
P(S) = {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.
If a set has |S| elements then P(S) has 2|S| elements. An exhaustive-search approach to this subset-sum
problem will include iterating over all subsets of S, and checking whether their sum is t:
function SubsetSum(S, t)
for each S′ in Powerset(S) do
if i∈S′ i = t then return Yes
return No
Since |S| = n, we know that there are 2n power sets to iterate through. For each power set we must compute a sum, which will be an O(n) operation. So the runtime of this subset sum problem is O(n2n).
How can we systematically generate all subsets of the given set S? For each element x ∈ S, we need to generate all the subset of S that happen to contain x, as well as those that do not. This gives us a natural recursive algorithm:
function Powerset(S) if S=∅then
222
2
return {∅} else
x ← some element of S
S′ ← S \ {x}
P ← Powerset(S′)
return P ∪ {s ∪ {x} | s ∈ P }
4. Partition problem At first it might seem we have to do something more sophisticated than in the subset-sum problem, however this problem reduces nicely to this problem.
First we’ll notice that if there are sets A and B which partition S and have equal sum they’ll have to satisfy the following two equations:
A+B=S (1) A=B (2)
So we can see that A = B = 21 S would have to hold. First, if S is odd we know the answer is No (given our elements are integers). Second, if such sets A and B exist, any set with sum 12 S will do. So:
function HasPartition(S) sum ← i∈S i
if sum is odd then
return No
return SubsetSum(S, sum/2)
3
5. Graph representations
(b)
Adjacency lists:
A → B, C B→A C→
D → A, C E→
Adjacency matrix:
ABCDE A0 1 1 0 0 B1 0 0 0 0
(a) Adjacency lists:
A → B, C
B → A, C
C → A, B, D D→C
E→
Adjacency matrix:
ABCDE
A0 1 1 0 0
B1 0 1 0 0 C1 1 0 1 0
D0 0 1 0 0 E00000
Sets of vertices and edges:
G = (V,E), where V = {A,B,C,D,E}, and
E = {{A,B},{A,C},{B,C},{C,D}} Degree is the number of edges connected to
a vertex. Node C has the highest degree (3).
C0 0 0 0 0
6. Graph representations continued Note that in this question we assume that self-loops are not allowed.
Additionally, we could always check whether a graph is constant time if we know (in constant time) the number of edges. If the number of edges is exactly n = n(n − 1)/2 then the graph is complete,
2
otherwise it is not.
(a) Determining whether a graph is complete.
(i) In the adjacency list representation we just want to check that for each node u, every other node is in its adjacency list.
If we can check the size of the list in O(1) time then we just need to go through each vertex and check that the size of the list is n − 1, and thus this operation will be linear in the number of nodes: O(n).
If we have to do a scan through the adjacency list then this would take O(m), which for a complete graph will be asymptotically equivalent to O(n2).
(ii) In the adjacency matrix representation, a complete graph would contain 1’s in all position except for the diagonal (since we can not have self loops). So there will be n2 − n positions in the matrix to lookup, and thus this operation will take O(n2) time.
(iii) For the graph to be complete the set of edges must contain each pair of vertices. There will be n edges if the graph is indeed complete, so we could just check the size of the edge set
2
E. This would be a constant time operation: O(1).
However if we can’t just check the size of the set we’ll have to look through all edges which
will take O(m) time.
(b) Determining whether the graph has an isolated node.
4
D10100 E00000
Sets of vertices and edges:
G = (V,E), where V = {A,B,C,D,E}, and
E = {(A,B),(A,C),(B,A),(D,A),(D,C)}
For a directed graph, degree is separated into in-degree and out-degree: the number of edges going into or out of each vertex, re- spectively. Nodes A and C have the highest in-degree (2).
We’ll have a think about how long it takes to determine if a single node is isolated, and then apply that to each vertex (i.e., n times)
(i) In the adjacency list representation, a node is isolated if its adjacency list is empty. This is O(1) to check per node, so O(n) for the whole graph.
(ii) In the adjacency matrix representation to check if a node is isolated we must look at each entry in that node’s row or column and confirm that all entries are 0. This is O(n) per node so O(n2) in total.
(iii) In the sets of vertices and edges representation we can loop through the set of edges and confirm that a vertex does not appear. This will take O(m) for a single node.
However we can also check a whole graph in a single pass by keeping track of all the nodes at once (in an array or a hash table for instance) and ticking them off as we see them, at the end we can iterate through this array/hash table to check if there were any isolated nodes. So this will take O(n + m) time.
7. Sparse and dense graphs (optional) Graphs with a constant number of edges per vertex (i.e., the degree of the vertices doesn’t grow with n) are sparse. Some examples of these are cycles and grid graphs:
Examples of dense graphs are complete graphs:
Real world examples of sparse graphs might arise from a graph representing the internet, and for dense graphs we could consider a network of cities, connected by all the possible aeroplane routes.
Storing sparse graphs using the various graph representations give rise to the following space com- plexities:
(i) To store an adjacency list we need to store one piece of data per edge. So the space complexity is O(m). Thus in a sparse graph the space complexity is O(n).
(ii) To store an adjacency matrix we need to store n2 pieces of information, regardless of m. So a sparse graph is still O(n2) space.
5
(iii) Sets of vertices and edges just require n items for the vertices and m items for the edges, so O(n + m). In a sparse graph this becomes O(n + n) = O(n).
6