Plan
School of Computing and Information Systems COMP90038 Algorithms and Complexity Tutorial Week 5
20–24 August 2018
Questions 23–26 are related to brute-force problem solving. There may not be time to cover more than two. The rest of the questions mostly relate to graphs and search.
The exercises
23. Consider the subset-sum problem: Given a set S of positive integers, and a positive integer t, find a subset S′ ⊆ S such that ∑ S′ = t, or determine that there is no such subset. Design an exhaustive-search algorithm to solve this problem. Assuming that addition is a constant-time operation, what is the complexity of your algorithm?
24. Consider the partition problem: Given n positive integers, partition them into two disjoint subsets so that the sum of one subset is the same as the sum of the other, or determine that no such partition exists. Designing an exhaustive-search algorithm to solve this problem seems somewhat harder than doing the same for the subset-sum problem. Show, however, that there is a simple way of exploiting your algorithm for the subset-sum problem (that is, try to reduce the partition problem to the subset-sum problem).
25. Consider the clique problem: Given a graph G and a positive integer k, determine whether the graph contains a clique of size k, that is, G has a complete sub-graph with k nodes. Design an exhaustive-search algorithm to solve this problem.
26. Consider the special clique problem of finding triangles in a graph (noting that a triangle is a clique of size 3). Show that this problem can be solved in time O(|V |3|E|).
27. Draw the undirected graph whose adjacency matrix is
Starting at node a, traverse the graph by depth-first search, resolving ties by taking nodes in alphabetical order.
abcde
a b c d e
01100 10100 11011 00101 00110
28. Consider this graph:
fbcg
d
ae
(a) Write down the adjacency matrix representation for this graph, as well as the adjacency list representation (assume nodes are kept in alphabetical order in the lists).
(b) Starting at node a, traverse the graph by depth-first search, resolving ties by taking nodes in alphabetical order. Along the way, construct the depth-first search tree. Give the order in which nodes are pushed onto to traversal stack, and the order in which they are popped off.
(c) Traverse the graph by breadth-first search instead. Along the way, construct the depth- first search tree.
29. Explain how one can use depth-first search to identify the connected components of an undi- rected graph. Hint: Number the components from 1 and mark each node with its component number.
30. The function Cyclic is intended to check whether a given undirected graph is cyclic.
function Cyclic(⟨V, E⟩)
mark each node in V with 0 count ← 0
foreachvinV do
if v is marked with 0 then cyclic ← HasCycles(v) if cyclic then
return True return False
function HasCycles(v) count ← count + 1 mark v with count
for each edge (v, w) do
if w’s mark is greater than 0 then return True
if HasCycles(w) then return True
◃ w is v’s neighbour ◃ w has been visited before ◃ a cycle can be reached from w
return False
Show, through a worked example, that the algorithm is incorrect. A later exercise will ask
you to develop a correct algorithm for this problem.
31. (Optional—state space search.) Given an 8-pint jug full of water, and two empty jugs of 5- and 3-pint capacity, get exactly 4 pints of water in one of the jugs by completely filling up and/or emptying jugs into others. Solve this problem using breadth-first search.
32. (Optional—use of induction.) If we have a finite collection of (infinite) straight lines in the plane, those lines will split the plane into a number of (finite and/or infinite) regions. Two regions are neighbours iff they have an edge in common. Show that, for any number of lines, and no matter how they are placed, it is possible to colour all regions, using only two colours, so that no neighbours have the same colour.