CSE 204 – Design and Analysis of Algorithms

Unit 3: Search techniques & Randomized algorithms

by

A. Aswani Devi, PhD (NIT Warangal),

Assistant Professor, Department of CSE,

SRM University AP
Course
IoT Unitization Plan – Unit-3 Theory
Key Characteristics

1. BFS & DFS, Backtracking

2. 8-Queen’s problem
3. Knight’s tour
4. Travelling Salesman Problem (TSP)
5. Branch-and-bound: 16-puzzle problem
6. TSSP
7. Randomized algorithms: Playing Cards
 Unit-3 & Chapter-1:
BFS & DFS, Backtracking
IoT Key Characteristics
BFS & DFS, Backtracking

Backtracking is a problem-solving algorithmic technique that involves finding a

solution incrementally by trying different options and undoing them if they lead to a
dead end.

Breadth-First Search (BFS) and Depth-First Search (DFS) are two fundamental
algorithms used for traversing or searching graphs and trees.

Two cases of BFS and DFS are:

1. Visiting a vertex

2. Exploring a vertex (visiting all adjacent vertices)

IoT
BFS
Key Characteristics

1. Queue data structure is used. (FIFO) 6

2. Explore and Visit 1 5

3. Add to the result

4 2 7
4. Construct BFS Spanning tree

5. Time complexity is O(n) 8

3

Initialize for vertex 1 10 9

IoT Key Characteristics
BFS Example

Queue BFS Spanning Tree

1 4 2 3 5 8 7 10 9 6 1

(Visited vertices in the first iteration)

4 2

Result
1, 4, 2, 3, 5, 8, 7, 10, 9, 6 5 7
3 8

Cross edges 10 9
6
IoT Key Characteristics
Other possible BFS Solutions

1) 1, 2, 4, 8, 5, 7, 3, 6, 10, 9 6

2) 5, 2, 8, 7, 6, 3, 1, 9, 10, 4 1 5

A graph can have multiple valid 4 2 7

BFS constructions

8
3

Complexity is O(V+E)
10 9
IoT
DFS
Key Characteristics

1. Stack data structure is used. (LIFO) 6

2. Visit and Explore 1 5

3. Add to the result

4 2 7
4. Construct DFS Spanning tree

5. Time complexity is O(n) 8

3

Initialize for vertex 1 10 9

IoT Key Characteristics
DFS Example

Stack DFS Spanning Tree

(Visited vertices in the first iteration) 1

tos 5
4
7
3
8
Result 2
2 10 9
1, 4, 3, 10, 9, 2, 8, 7, 5, 6
3 8

4 Back edges 7

1 5
6
IoT Key Characteristics
Other possible DFS Solutions

1) 1, 2, 8, 7, 5, 6, 3, 9, 10, 4 6

2) 3, 4, 1, 2, 5, 6, 7, 8, 10, 9 1 5

4 2 7
A graph can have multiple valid
DFS constructions
8
3

Complexity is O(V+E)
10 9
Unit-3 & Chapter-2:
8-Queen’s problem
IoT Key Characteristics
8-Queen’s problem

❖ Backtracking algorithm

❖ Problem: Place n queens in n*n chess board so that no two of them can
“attack” i.e., no two of them are on the same row, column or diagonal.

❖ Solutions are expressed in n-tuple

Complexity is O(N!)
IoT Key Characteristics
8-Queen’s problem

1 2 3 4 5 6 7 8
❖ Backtracking algorithm
1 Q
❖ Problem: Place n queens in 2 Q
n*n chess board so that no 3 Q
two of them can “attack” i.e., 4 Q
no two of them are on the
5 Q
same row, column or diagonal.
6 Q
❖ Solutions are expressed in n- 7 Q
tuple 8 Q
IoT Key Characteristics
8-Queen’s problem Pseudocode

1. begin from the leftmost column

2. if all the queens are placed, return true/ print configuration

3. check for all rows in the current column

❖ a) if queen placed safely, mark row and column; and recursively check if we
approach in the current configuration, do we obtain a solution or not

❖ b) if placing yields a solution, return true

❖ c) if placing does not yield a solution, unmark and try other rows

4. if all rows tried and solution not obtained, return false and backtrack
Unit-3 & Chapter-3:
Knight’s tour
Knight’s tour
A knight's tour is a sequence of moves of a knight on a chessboard such that
the knight visits every square exactly once.
Knight’s tour Solution: Example

Input N=8

0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
Output 42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
Knight’s tour: Hamiltonian path problem
❖ Hamiltonian path: A traceable path in an undirected or directed graph that
visits each vertex exactly once.

❖ The Hamiltonian path problem decides if a directed or undirected graph,

contains a Hamiltonian path, a path that visits every vertex in the graph
exactly once.

❖ The knight's tour problem is an instance of the Hamiltonian path problem

in graph theory.
Backtracking Algorithm: Knight’s tour
❖ If (all squares are visited) ⇒ print the solution

❖ Else
1. Add one of the next moves to solution vector and recursively check if this move leads to
a solution.

2. If the move chosen in the above step doesn't lead to a solution, then remove this move
from the solution vector and try other alternative moves.

3. If none of the alternative's work, then return false ("no solution exists")

Complexity is O(𝟖𝒏 )
 Unit-3 & Chapter-4:
Travelling Salesman Problem (TSP)
Travelling Salesman Problem (TSP)
❖ A Hamiltonian path, is a path in an undirected graph that visits each vertex
exactly once.

❖ A Hamiltonian Cycle or Circuit in a graph G is a cycle that visits every

vertex of G exactly once and returns to the starting vertex.

❖ Travelling Salesman Problem (TSP): Given a set of cities and distances

between every pair of cities, the problem is to find the shortest possible route
that visits every city exactly once and returns to the starting point.

❖ To find a minimum weight Hamiltonian Cycle.

TSP: Example -1
❖ A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is
80. (minimum weight Hamiltonian Cycle out of (n-1)! Permutations of cities)

1. 4-3-2
2. 3-4-2
3. 2-4-3
4. 2-3-4
5. 4-2-3
6. 3-2-4

Complexity is O(N!)
TSP: Example - 2
❖ Find the minimum weight Hamiltonian Cycle for the graph below:

Mumbai 1,400 km Delhi

980 km 2,200 km

Bangalore 350 km Chennai

 Unit-3 & Chapter-5:
Branch-and-bound: 16-puzzle problem
Branch-and-bound
❖ Branch-and-bound: Searching for the solution by dividing the problem into
smaller subproblems, or branches, and then eliminating certain branches
based on bounds on the optimal solution.

❖ This process continues until the best solution is found or all branches have
been explored.

❖ 16-puzzle problem: A classic sliding puzzle consisting of a 4x4 grid with 15

numbered tiles and one empty space.
16-puzzle problem
Branch-and-bound: 16-puzzle problem
Initial State: The starting configuration of the puzzle.

Goal State: The desired configuration (typically numbers in ascending order).

Cost Function: Uses the Manhattan distance heuristic to estimate the cost.

Priority Queue: A min-heap to always expand the lowest cost node first.

Node Expansion: Generate possible moves by shifting the empty space.

Pruning: Discard nodes with higher costs than the best-known solution.

Complexity is O(N!)
 Unit-3 & Chapter-6:
TSP using Branch and Bound Strategy
TSP
❖ Back tracking uses DFS and Branch and bound uses BFS.

❖ State space tree explores the entire TSP in terms of all possible tours.

1
1 2

2 3 4

4 3
3 4 2 4 2 3

4 3 4 2 3 2
TSP: Example

1 2 1 2 3 4 5
1 ∞ 20 27 10 11
2 15 ∞ 16 4 2
3 3 5 ∞ 2 4
4 3 4 19 6 18 ∞ 3
5 16 4 7 16 ∞

5
TSP: Example

1 2 3 4 5
1 ∞ 10 17 0 1 10 1 C = 25
2 12 ∞ 11 2 0 2
3 0 3 ∞ 0 2 2
4 15 3 12 ∞ 0 3
2
5 11 0 0 12 ∞ 4

1 0 3 0 0 21 + 4

Cost of reduction = 25

Reduced Matrix
TSP: Example

1 2 3 4 5
1 ∞ ∞ ∞ ∞ ∞ ∞ 1 C = 25
2 ∞ ∞ 11 2 0 0
3 0 ∞ ∞ 0 2 0
4 15 ∞ 12 ∞ 0 0
2
5 11 ∞ 0 12 ∞ 0

0 ∞ 0 0 0 0+0

Cost of reduction = c(1, 2) + 𝑟 + 𝑟 ′ = 10 + 25 + 0 = 35

TSP: Example

1 2 3 4 5
1 ∞ ∞ ∞ ∞ ∞ ∞ 1 C = 25
2 12 ∞ ∞ 2 0 0
3 ∞ 3 ∞ 0 2 0
4 15 3 ∞ ∞ 0 0
2
5 11 0 ∞ 12 ∞ 0

11 0 ∞ 0 0 0 + 11
3

Cost of reduction = c(1, 3) + 𝑟 + 𝑟 ′ = 17 + 25 + 11 = 53

TSP: Example

1 2 3 4 5
1 ∞ ∞ ∞ ∞ ∞ ∞ 1 C = 25
2 12 ∞ 11 ∞ 0 0
3 0 3 ∞ ∞ 2 0
4 ∞ 3 12 ∞ 0 0
2
5 11 0 0 ∞ ∞ 0

0 0 0 ∞ 0 0+0
4
3

Cost of reduction = c(1, 4) + 𝑟 + 𝑟 ′ = 0 + 25 + 0 = 25

TSP: Example
C = 25
1 2 3 4 5
1 ∞ ∞ ∞ ∞ 1
∞ ∞
2 12 ∞ 11 2 ∞ 2
3 0 3 ∞ 0 ∞ 0
3 5
4 15 3 12 ∞ ∞ 2
5 ∞ 0 0 12 ∞ 0

0 0 0 0 ∞ 5+0 4
3

Cost of reduction = c(1, 5) + 𝑟 + 𝑟 ′ = 1 + 25 + 5 = 31

TSP: Example
C = 25
❖ Least cost branch and bound
1 1
❖ Start with the node 4 matrix

1 2 3 4 5 C = 35 C = 25 C = 31
C = 53
1 ∞ ∞ ∞ ∞ ∞ ∞ 2 2 3 3 4 4 5 5
2 ∞ ∞ 11 ∞ 0 0
3 0 ∞ ∞ ∞ 2 0
4 ∞ ∞ ∞ ∞ ∞ ∞
5 11 ∞ 0 ∞ ∞ 0

0 ∞ 0 ∞ 0 0+0 6 2 7 3 8 5
Cost of reduction = c(4, 2) + 𝑟 + 𝑟 ′ = 3 + 25 + 0 = 28 C = 28 C = 50 C = 36
TSP: Example

2 3 4 5
Cost of the tour = 28

Path: 1-4-2-5-3 2 3 5
C = 52 C = 28

9 3 5 10

C = 28
3 11
 Unit-3 & Chapter-7:
Randomized algorithms: Playing Cards
Randomized algorithms: Playing Cards
❖ Fisher-Yates Shuffle Algorithm to shuffle a deck of cards by randomizing the
given array of cards with the complexity of O(n)

❖ Shuffling is in such a way that every random permutation of array element

should be equally likely.

❖ A function rand() generates a random number in O(1) time.

Start from the last element and swap it with a

for i from n - 1 down to 1 do randomly selected element from the whole array
j = random integer with 0 <= j <= i
exchange a[j] and a[i] Consider the array from 0 to n-2 and repeat the
process till we hit the first element.
 Research Review Meeting JNTU Kakinada
IoT Key Characteristics
Recommended Resources
1. Cormen, Thomas H., et al. *Introduction to Algorithms*. 3rd ed., MIT Press, 2009.
Thank You