Match the following with respect to algorithm paradigms:

	List - I		List - II
(a)	The 8-Queen’s problem	(i)	Dynamic programming
(b)	Single-Source shortest paths	(ii)	Divide and conquer
(c)	STRASSEN’s Matrix multiplication	(iii)	Greedy approach
(d)	Optimal binary search trees	(iv)	Backtracking

8 - queen’s problem:

• In this, 8 queens are placed on a 8 × 8 chessboard such that none of them can take same place.
• It is the backtracking approach. In backtracking approach, all the possible configurations are checked and check whether result is obtained or not.
•  A queen can only be attacked if it is in the same row or column or diagonal of another queen.

Single source shortest path:

• It is used to find the shortest path starting from a source to the all other vertices.
• It is based on greedy approach.
• Example of single source shortest path algorithm is Dijkstra’s algorithm which initially consider all the distance to infinity and distance to source is 0.

Strassen’s matrix multiplication:

• It is a method used for matrix multiplication. It uses divide and conquer approach to multiply the matrices.
• Time consumption is improved by using Strassen’s method as compared to standard multiplication method.
• It is faster than standard method. Strassen’s multiplication can be performed only on square matrices.

Optimal binary search tree:

• It is also known as weight balanced binary tree. In optimal binary search tree, dummy key is added in the tree by first constructing a binary search tree.
• It is based on dynamic programming approach. Total cost must be as small as possible.