COSC 1285/2123
COSC 1285/2123 Algorithms and Analysis
Tutorial 5
Decrease and Conquer Algorithmic Paradigm
Tutorial Exercises
Objective
Students who complete this tutorial should:
� Be familiar with the three major variations of decrease-and-conquer.
� Be able to apply decrease-and-conquer strategies to different problem types.
4.1.7 Apply insertion sort to sort the list E, X, A, M, P, L, E in alphabetical order.
4.5.12 Flipping pancakes There are n pancakes all of different sizes that are stacked on top of each
other. You are allowed to slip a flipper under one of the pancakes and flip over the whole stack
above the flipper. The purpose is to arrange pancakes according to their size with the biggest at the
bottom. Design an algorithm for solving this puzzle.
4.2.5a Apply the source-removal algorithm to solve the topological sorting problem for the following
digraph:
4.4.10
a Write a pseudocode for the divide-into-three algorithm for the fake-coin problem. (Make sure
that your algorithm handles properly all values of n, not only those that are multiples of 3.)
b Set up a recurrence relation for the number of weighings in the divide-into-three algorithm for
the fake-coin problem and solve it for n = 3k
c For large values of n, about how many times faster is this algorithm than the one based on
dividing coins into two piles? (Your answer should not depend on n.)
4.1.1 Ferrying soldiers A detachment of n soldiers must cross a wide and deep river with no bridge
in sight. They notice two 12-year-old boys playing in a rowboat by the shore. The boat is so tiny,
however, that it can only hold two boys or one soldier.
a How can the soldiers get across the river and leave the two boys in joint possession of the boat?
Outline the algorithm in plain English.
©2021 RMIT University 1
COSC 1285/2123
b How many times need the boat pass from shore to shore? Give a recurrence relation and solve
it.
c Explain the use of “decrease-and-conquer” in your solution.
©2021 RMIT University 2
COSC 1285/2123
Practical Exercises
Objective
Students who complete this lab should:
� Learn to implement depth first search (DFS) and breadth first search (BFS) traversal.
� Learn to use breadth first search (BFS) for computing shortest path distances in graphs.
Introduction
In this lab exercise you will complete the implementation for DFS and BFS traversals starting from
a specified seed vertex, and use BFS to compute the shortest path between to vertices in a graph.
DFS
Depth first search can be implemented as recursive algorithm, as outlined in Algorithm 1. Note that
this is slightly different from what is in the lectures as we are starting the DFS from a seed, while
the DFS in the lecture nodes is seeking to compute the DFS traversal for the whole graph. The
implementation in this workshop will not traverse the whole graph if it is disconnected.
Algorithm 1 Depth first search algorithm.
algorithm DFS (G)
Perform a Depth first search traversal of a graph.
input : Graph G = 〈V,E〉, seed/starting vertex s.
output : Graph G with its vertices marked with consecutive integers in the order they were
visited/processed.
1: // sequence collection that stores the visitation order
2: Order = []
3: // mark all vertices unvisited
4: for i = 0 to v do
5: Marked[i] = 0
6: end for
7: DFSR (s)
©2021 RMIT University 3
COSC 1285/2123
algorithm DFSR (v)
Recursively visit all connected vertices.
input : A seed/starting vertex v
output : Graph G with its vertices marked with consecutive integers in the order they were
visited/processed.
1: Marked[v] = 1
2: Order.add(v)
3: for w ∈ V adjacent to v do
4: if not Marked[w] then
5: DFSR (w)
6: end if
7: end for
BFS
Breadth first search can be implemented using a queue, which computes the correct order that the
vertices should be visited or processed. Algorithm 2 outlines the approach.
Algorithm 2 Breadth first search algorithm.
algorithm BFS (G)
Implement a Breadth First Traversal of a graph.
input : Graph G = 〈V,E〉, seed/starting vertex s.
output : Graph G with its vertices marked with consecutive integers in the order that they are
traversed/visited.
1: // sequence collection that stores the visitation order
2: Order = []
3: // mark all vertices unvisited
4: for i = 0 to v do
5: Marked[i] = 0
6: end for
7: Marked[s] = 1
8: Queue.enqueue(s)
9: while not Queue.isEmpty() do
10: v = Queue.deque()
11: Order.add(v)
12: for w ∈ V adjacent to v do
13: if not Marked[w] then
14: Marked[w] = 1
15: Queue.enqueue(w)
16: end if
17: end for
18: end while
©2021 RMIT University 4
COSC 1285/2123
Shortest path distance
The shortest path between two vertices in an unweighted graph is the path that traverses the least
number of edges to go from a source vertex to a target vertex. The shortest path distance between
two vertices is the number of edges traversed in an unweighted graph.
Computing shortest path distances using BFS
To compute shortest path distances using BFS, a minor modification is needed to the previous
pseudo code for BFS. We know that the neighbours of seed (source) vertex s has distance 0 from
s (itself). Its neighbours have a shortest path distance of 1, their neighbours have a shortest path
distance of 2 from the source vertex and so on.
To implement this, when we enqueue the vertex v, we also need to store the shortest path distance
from s to v, so that when we deque it, then we can just increment the shortest path distance by 1
for its neighbours.
Shortest path distance using BFS can be implemented as outlined in Algorithm 3.
Algorithm 3 Computing shortest path distance using Breadth first search.
algorithm ShortestPathDistance (G, s, t)
Compute the shortest path distance between source vertex s to target vertex t using BFS.
input : Graph G = 〈V,E〉, source vertex s, target vertex t. starting output : Shortest path
distance between vertices s and t. If s and t are disconnected, than return −1.
1: // mark all vertices unvisited
2: for i = 0 to v do
3: Marked[i] = 0
4: end for
5: // initial distance from source vertex is 0
6: Queue.enqueue((s, 0))
7: while not Queue.isEmpty() do
8: (v, d) = Queue.deque()
9: if v == t then
10: return d
11: end if
12: Marked[v] = 1
13: for w ∈ V adjacent to v do
14: if not Marked[w] then
15: Queue.enqueue((w, d + 1)
16: end if
17: end for
18: end while
19: // If reach here, then either s and t are disconnected or t does not exist
20: return −1
©2021 RMIT University 5
COSC 1285/2123
Provided Code
The programs BFS, DFS and BFSShortestPath reads a sequence of white-space separated inte-
gers from file as edges, construct the corresponding graph. BFS runs breadth first search traversal
on the input graph, DFS runs depth first search traversal and BFSShortestPath computes the
shortest path distance between two input vertices.
file description
Graph.java Code to implement a graph, using adjacency list representation. No need to modify this file.
BFS.java Code implementing breadth-first-traversal. You are to implement the BFS traversal
functionality, using Algorithm 2.
DFS.java Almost complete code implementing DFS traversal. You are to implement the DFS
traversal functionality, using Algorithm 1.
BFSShortestPath Skeleton code for you to implement the shortest path distance algorithm, using
Algorithm 3.
Compile the program using the following command:
javac *.java
To run BFS:
java BFS
To run DFS:
java DFS
To run BFSShortestPath:
java BFSShortestPath
We have provided a sample graph file for you to experiment with. It is called graph1.in. It
contains vertices 0 to 9. Using this file, as an example, you can run BFS on this graph on seed
vertex 1 as follows:
java BFS graph1.in 1
Task
Your task in this lab exercise is to implement the following algorithms in DFS.java, BFS.java and
BFS-ShortestPath:
� DFS.java: Implement traverse(Graph g, int s), to compute a depth first traversal from
seed vertex “s”.
� BFS.java: Implement traverse(Graph g, int s), to compute a breadth first traversal from
seed vertex “s”.
� BFSShortestPaths.java: Implement spd(Graph g, int s, int t) to compute the shortest
path distance between vertices “s” and “t”.
©2021 RMIT University 6