Design & Analysis of Algorithms

Laboratory Instructions & Assignments

By: Tamal Chakraborty

Minimum Spanning Tree Algorithms

WEEK 6

Minimum Spanning Tree

A tree T is said to be a spanning tree of a connected graph G if T is a subgraph of G and T contains all vertices of G.

The weight of a spanning tree T of G is defined as the sum of the weights of all the branches of T. A spanning tree with the smallest weight in a weighted graph is called a minimal spanning tree. Given a weighted graph G, we have to find a minimal spanning tree of the graph.
v2 5 v1 3 v3 2 4

1 v4

Finding The Minimal Spanning Tree

Greedy Strategy

Let A be a sub-set of the minimal spanning tree

At each step determine an edge (u, v) such that, if we add (u, v) to A, A remains a subset of the minimal spanning tree.

The edge (u, v) is called a safe edge for A.

Kruskals Algorithm
8

7
v1

v2

v4

2 5
v3

1.

List all the edges of the graph G in order of non-decreasing weight. (v2, v3), (v3, v4), (v1, v3), (v1, v2), (v2, v4) Select a smallest edge from G (v2, v3) From the remaining edges select the smallest edge which doesnt make a circuit with the previously selected edges.

2. 3.

4.

(v2, v3), (v3, v4) Continue until (n 1) edges have been selected (v2, v3), (v3, v4), (v1, v3)
v1

v2

v4

2
5
v3

Strategy
Read the input graph from a file using the readGraph method (refer to Assignment 3.1) Get an array of edges of the graph using the getEdges method (refer to Assignment 3.2) Sort the edges of the graph using the qsort method (refer to Assignment 5.2) The function to compare edges may be implemented as:
int edgeCmp(const void* a1, const void* a2) { edge* e1 = (edge*)a1; edge* e2 = (edge*)a2; return (e1->cost - e2->cost); }

To check whether a circuit is formed with the previously selected edges we will use the compressedFind and weightedUnion operation of Disjoint Sets (refer to Assignment 5.1)

Assignments
6.1 Implement Kruskals Algorithm:
void kruskal(G) initDisjointSet(n); k = getEdges(G, edges); qsort(edges, k, sizeof(edge), edgeCmp)
for (i = 0 to k - 1) u = edges[i].u v = edges[i].v if (compressedFind(u) compressedFind(v)) weightedUnion(u, v) print edge (u, v) in MST if (++nodes == n - 1) break

Prims Algorithm
8
7
v1 v2 v4

2 5
v3

0 7 5

7 0 2 8

5 2 0 3

8 3 0

1.

2.

3.

Start with vertex v1 and connect to the vertex which has the smallest entry in row 1, say vk. (v1, v3) Now consider (v1, vk) as one sub-graph and connect this sub-graph to a vertex other than v1 and vk that has the smallest entry among all entries in rows 1 and k, say vj. (v1, v3), (v3, v2) Now regard the tree with vertices v1, vk and vj as one sub-graph and continue this process until n vertices have been connected by n 1 edges. v4 v2 (v1, v3), (v3, v2), (v3, v4)
v1

2 5
v3

Strategy

Read the input graph from a file using the readGraph method (refer to Assignment 3.1). Pass the weighted adjacency matrix G and a source vertex s to the Prim function. Initialize an array d[] of size n using the init method, set d[s] to 0 and all other elements of d[] to . Keep the init method in a separate file Common.h
init(G, s) foreach (vertex v of G) d[v] = p[v] = -1 d[s] = 0

Initialize a priority queue with the d[] array (insert each element of d in the priority queue) At every step get a vertex u, using the extractMin method of the priority queue For each vertex v adjacent to u, if v exists in the priority queue, let i be its index in the heap, then set p[v] to u, d[v] to G[u][v] and decrease the key of the ith element of priority queue to d[v] For each element i of the array p[1 n - 1], the pair (p[i], i) gives an edge in the MST

Assignments
6.2 Implement Prims Algorithm:
void prim(G, s) init(G, s); PriorityQueue* pq = initPQ(d, n); while ((e = extractMin(pq))) u = eindex for (v = 0 to n - 1) if ((G[u][v]) AND (G[u][v] )) i = findPQ(pq, v) if (i AND G[u][v] < d[v]) p[v] = u d[v] = G[u][v] decreaseKey(pq, i, d[v])

10

Knapsack & MaxMin Algorithms

WEEK 7

Knapsack Problem
A Thief enters a store in the night, with a knapsack in his hand.

12

The knapsack can carry only a certain amount of weight, say W at most.
The store has n items, each having a value V and weight W. The thief has to select items, such that he fills his knapsack with items, giving him the maximum value. There are two variations of this problem. In the 0/1 knapsack problem the thief has to either take the entire item or leave it altogether. In the fraction knapsack problem the thief is allowed to take fraction of items. For example, if the store contained gold biscuits it would constitute a 0/1 knapsack problem. Whereas if the store contained gold dust, it would constitute a fraction knapsack problem, since the thief can take a portion of the gold dust.

Example
Let us suppose the store has three items as shown below:
Item
1 2 3

13

Value (V)
60 100 120

Weight (W)
10 20 30

V/W
6 5 4

Let the Knapsack capacity be 50. The thief would like to make a greedy choice, hence he will pick up items with higher V/W values.

Example: 0/1 Knapsack Problem

Let us assume that it is a 0/1 Knapsack Problem, i.e. the thief has to either take the whole item or leave it.
By making a greedy choice the thief would pick up items 1 & 2 first, thereby filling the knapsack by W = 30 and earning V = 160 He cant take the item 3 anymore since his knapsack can only take 20 units of weight, whereas item 3 weighs 30. But as we can see, if the thief picked up items 2 & 3 he would have earned V = 220. Thus greedy choice did not lead to an optimal solution

14

Example: Fraction Knapsack Problem

By making a greedy choice the thief would pick up items 1 & 2 first, thereby filling the knapsack by W = 30 and earning V = 160

15

Let us assume that it is a Fraction Knapsack Problem, i.e. the thief can take a part of an item.

He will now take 20 units of weight of item 3, thereby gaining another 80 units of money. His total profit is 160 + 80 = 240 Thus greedy choice leads to an optimal solution for a fraction knapsack problem.

Strategy
Implement each item as a structure.
typedef struct item { int weight; int value; }item;

16

Sort the items in decreasing order of value/weight by the qsort method. The item comparator method may be implemented as:
int compare(const void *x, const void *y) { item *i1 = (item *)x, *i2 = (item *)y; double ratio1 = (*i1).value*1.0 / (*i1).weight; double ratio2 = (*i2).value*1.0 / (*i2).weight; return ratio2 ratio1; }

Finally iterate over items and select them by greedy choice.

Assignment
7.1 Implement the Knapsack algorithm
Knapsack(item items[], int n, int maxWeight) qsort(items, n, sizeof(item), compare) value = 0.0 presentWeight = 0 for(i = 0 to n 1) if (presentWeight + items[i].weight < maxWeight) presentWeight += items[i].weight value += items[i].value else remaining = maxWeight - presentWeight value += items[i].value * remaining * 1.0 / items[i].weight break return value

17

MaxMin Algorithm
We would formulate a divide and conquer algorithm to solve this as follows:

18

Let us consider the problem of finding the maximum and minimum of an array a[1 n] of n integers.

If the array contains one element then max and min are both the same (which is the only element in the array) If the array contains two elements the greater of them is max and the lesser of them is min
If the array contains more than two elements divide it into two parts P1, P2 along the mid-point, and then find the max and min of the two parts recursively. Then max = larger(max(P1), max(P2) and min = smaller(min(P1), min(P2))

Assignment
7.2 Implement the MaxMin Algorithm
maxMin(i, j, max, min) if (i == j) max = min = a[i] else if (i == j 1) if (a[i} > a[j]) max = a[i] min = a[j] else max = a[j] min = a[i] else mid = (i + j) / 2 maxMin(i, mid, max, min) maxMin(mid + 1, j, max1, min1) if (max < max1) max = max1 if (min > min1) min = min1

19

Single Source Shortest Path

WEEK 8

Shortest Path Problem

8 7
v1 v2 v4

21

2 5
v3

0 D

7 0

5 2 0

8 3 0

A simple weighted directed graph G can be represented by an n x n matrix D = [dij] where:

dij

= weight of the directed edge from i o j

= 0, if i = j
= , if there is no edge between i and j

We have to find out the shortest path from any given vertex to all other vertices

Dijkstras Algorithm
Begin 1. 2. Assign a permanent label 0 to the start vertex and a temporary label to all other vertices Update label of each vertex j with temporary label using the following rule: Labelj = min[Labelj, Labeli + dij] Where i is the latest vertex permanently labeled and dij is the direct distance between i and j.
3. 4. Choose the smallest value among all the temporary labels as the new permanent label. In case of a tie select any one of the candidates. Repeat steps 2 and 3 until all the vertices are permanently labeled

22

End

Dijkstras Algorithm
8 7
v1

23

v2

v4

2
5
v3

v1

v2

v3

v4

0
0

0
0

7
7

5
5

8
8

Strategy

24

Read the input graph from a file using the readGraph method (refer to Assignment 3.1). Pass the weighted adjacency matrix G and a source vertex s to the dijkstra function. Initialize an array d[] of size n using the init method, set d[s] to 0 and all other elements of d[] to . Refer to Assignment 6.2 Initialize a priority queue with the d[] array (insert each element of d in the priority queue) At every step get a vertex u, using the extractMin method of the priority queue For each vertex v adjacent to u, call relax(u, v, G) and decrease the key of v in the priority queue to d[v] The relax method can be implemented as follows (put it in Common.h)
relax(u, v, G) if (d[u] > d[v] + G[u][v]) d[u] = d[v] + G[u][v] p[v] = u

Assignment
8.1 Implement Dijkstras Algorithm
dijkstra(int G[][n], int s) init(G, s) PriorityQueue* pq = initPQ(d, n) while ((e = extractMin(pq))) u = e->index for (v = 0 to n - 1) if ((G[u][v]) AND (G[u][v] )) relax(u, v, G) decreaseKey(pq, findPQ(pq, v), d[v])

25

Bellman-Ford Algorithm
The Bellman-Ford algorithm solves the single source shortest path problem for graphs, in which the edge weights may be negative The Bellman-Ford algorithm indicates whether or not there is a negative weight cycle, reachable from the source, in the graph

26

If there is such a cycle the algorithm indicates that no such solution exists by returning a Boolean false If there is however no such cycle the algorithm produces the shortest paths from the source vertex to every other vertex and their weights

Assignment
8.2Implement Bellman-FordAlgorithm
bellmanFord(int G[][n], int s) init(G, s) for (i = 1 to n - 1) for (u = 0 to n - 1) for (v = 0 to n - 1) if ((G[u][v]) AND (G[u][v] )) relax(u, v, G)
for (u = 0 to n - 1) for (v = 0 to n - 1) if ((G[u][v]) AND (G[u][v] )) if (d[v] > d[u] + G[u][v]) return 0

27

return 1

All Pairs of Shortest Paths, N-Queens

WEEK 9

All pairs of shortest paths

Given a vertex of a graph, Dijkstras algorithm enables us to find the shortest path from that vertex to all other vertices The next problem is to find out the shortest path between any given pair of vertices of a graph The restriction is that G have no cycles with negative length If we allow G to contain cycles with negative length then the shortest path between any two vertices on this cycle is - The all pairs of shortest path problem is to determine a matrix A such that A(i, j) is the length of the shortest path from i to j.

29

All pairs of shortest paths

We assume all the vertices of the graph are numbered from 1 to n

30

Let Ak(i, j) be the length of the shortest path from i to j going through no intermediate vertex greater than k Then there are two possibilities 1. The path from i to j goes through k: In which case we can split the path in two parts, one from i to k and the other from k to j. Note that neither of these two paths can go through any intermediate vertex greater than k 1. Length of such a path is: Ak-1(i, k) + Ak-1(k, j)
The path from i to j does not go through k: Which means that this path goes through no intermediate vertex greater than k-1. Its length would be: Ak-1(i, j)

2.

Clearly Ak(i, j) is the minimum of these two choices

Hence Ak(i, j) = min{ Ak-1(i, j) , Ak-1(i, k) + Ak-1(k, j) }

Assignment
9.1 Implement the all pairs of shortest paths algorithm
allPairs(int a[][n]) for (k = 0 to n - 1) for (i = 0 to n - 1) for (j = 0 to n - 1) a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

31

32

The 8 Queens Problem

We have an 8x8 chessboard, our job is to place eight queens on the chessboard, so that no two of them can attack. That is, no two of them are in the same row, column or diagonal
Q

Q
Q Q

Q
Q Q Q

33

The n Queens Problem

The generalized version of the 8 Queens problem is the n Queens problem, where n is a positive integer. Let us illustrate a backtracking approach to this problem with a 4 Queens example.

Q1

Q1
X X Q2

Q1
X X Q2

Step1: Place Q1 on Col 1

Step2: Place Q2

No legal place for Q3

34

The n Queens Problem

Q1 Q1 Q1

Q2

X X

X Q3

Q2

X X X

X Q3 X

Q2

Backtrack and alter Q2

Q1

Place Q3
Q1 X X X Q2

No legal place for Q4

Q1 X Q3 X X Q4 X X Q2

Backtrack and alter Q1

Place Q2

Place Q3 and then Q4

35

The n Queens Problem

Let (x1, x2, , xn) represent a solution in which xi is the column of the ith row, where the ith queen has been placed. The xis will all be distinct, since no two queens can be in the same column. Now, how to check that they are not in the same diagonal?
Q

Q
Q Q

Q
Q Q Q

36

The n Queens Problem

Let the chessboard square be represented by the 2D array a[18, 18]. Every element on the same diagonal that runs from top-left to right-bottom has the same (row column) value. For example, a Queen at a[4,2] has attacking Queens, diagonal to it at a[3,1], a[5,3], a[6,4] (up-left to lowright).
Q

Q
Q Q

Q
Q Q Q

37

The n Queens Problem

Also all elements on the same diagonal from top-left to bottom-right have the same (row + column) value. If the Queens are placed at (i,j) and (k,l) cells, then they are in the same diagonal only if i j = k l or i+j=k+l i.e. abs(j l) = abs(i k)
Q

Q
Q Q

Q
Q Q Q

Assignment
9.2 Implement the n-queens algorithm
place(k, i) for (j = 1 to k - 1) if ((x[j] == i) || (abs(x[j] - i) == abs(j - k))) return 0; return 1; nQueens(k) for (i = 1 to n) if (place(k, i)) x[k] = i; if (k == n) displayChessBoard(); else nQueens(k + 1);

38

Graph Coloring, Hamiltonian Cycles

WEEK 10

Graph Coloring Problem

Painting all the vertices of a graph with colors such that no two adjacent vertices have the same color is called the proper coloring of a graph.
A graph in which every vertex has been assigned a color according to proper coloring is called a properly colored graph. A graph G that requires k different colors for its proper coloring, and no less, is called a k-chromatic graph. The number k is called the chromatic number of G.

40

Graph Coloring Problem

Let m be a given positive integer. In our example, say m = 3.
We want to find whether the nodes of G can be colored in such a way that no two adjacent nodes have the same color, yet only m colors are used. We design a backtracking algorithm such that given the adjacency matrix of a graph G and a positive integer n, we can find all possible ways to properly color the graph.

41

Graph Coloring Problem: How it works

Let Red be color 1

42

Let Green Let Blue

be color 2 be color 3

Let us examine how the backtracking algorithm for coloring works:

a c

b
e d

Graph Coloring Problem

a
c

43

b
e d b

a
c

b
e d b

e c d

e c d

Assignment
10.1 Implement the Graph Coloring Algorithm
void nextColor(k, G) do { x[k] = (x[k] + 1) % (m + 1); if (x[k] == 0) return; int j; for (j = 0; j < n; j++) if ((G[j][k] 0) AND (x[k] == x[j])) break; if (j == n) return; } while (true); void mColoring(k, G) do { nextColor(k, G); if (x[k] == 0) return; if (k == n - 1) display(); else mColoring(k + 1, G); } while (true);

44

Hamiltonian Cycles

45

Let G(V, E) be a connected graph with n vertices. A Hamiltonian cycle is a round trip path in G that visits every vertex once and returns to the starting position.
The graph G1 below has Hamiltonian cycles.

0 7

1 6

2
5 1

3 4

Whereas G2 has no Hamiltonian cycles.

0 4

2 3

We want to find all the Hamiltonian cycles in a graph

Hamiltonian Cycles
The following figure illustrates the backtracking approach for a possible solution

46

a c

f
e d

b c

f e d f
Dead end

e
c

Given graph

e
f
Dead end

Dead end

d
a
Solution

Part of the solution tree

Assignment
10.2 Implement the Hamiltonian Cycles Algorithm
nextVertex(k, G) do { x[k] = (x[k] + 1) % (n + 1); if (x[k] == 0) return; if (G[x[k - 1] - 1][x[k] - 1] 0) { for (j = 1 to k - 1) if (x[k] == x[j]) break; if (j == k) if ((k < n) OR ((k == n) AND G[x[n] - 1][x[1] - 1])) return; } while (true); hamilton(k, G) do { nextVertex(k, G); if (x[k] == 0) return; if (k == n) displayCycle(); else hamilton(k + 1, G); } while (true);

47

Thank you!!!

If debugging is the process of removing bugs, then programming must be the process of putting them in. - Dijkstra