.png)
Mobiprep has created last-minute notes for all topics of Algorithm to help you with the revision of concepts for your university examinations. So let’s get started with the lecture notes on Algorithm.
Our team has curated a list of the most important questions asked in universities such as DU, DTU, VIT, SRM, IP, Pune University, Manipal University, and many more. The questions are created from the previous year's question papers of colleges and universities.
Backtracking
Question- 1) What is Backtracking?
Answer: It is an algorithmic technique that considers searching every possible combination in order to solve a computational problem. It is the method of building the solution one piece at a time recursively and incrementally. The method keeps removing all those choices that do not contribute to the solution. Backtracking is considered to be best fit for only specific categorized problems, i.e., decision making problems, optimization problems and enumeration problems.
Decision making problem :To find the path from given source to destination point in a maze
Optimization problem :Queens's problem
Enumeration problem : Knapsack problem
Question- 2) What is Recursive Maze Algorithm?
Answer: It is one of the best implementation of Backtracking technique. In terms of programming language, a maze can be represented by a 2D array. In general, a maze can be defined as collection of both successful and unsuccessful paths between two points namely source and destination. The recursive maze algorithm is the algorithm designed to solve the maze-type problems where the base concept of algorithm is backtracking.
Example: Consider the following-
The concept of recursive maze problems goes as follows:
1 (START) | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 1 | 1 | 0 |
1 | 0 | 1 | 1 (END) |
Consider the above maze where 0 means there could be no possibility to pass through that particular cell, and 1 is allowed to go through that particular cell.
Out of all the ways of successfully reaching END point from the START, we find only 1 particular way being possible which allows reaching the end (destination) successful. (As marked above)
These types of problems are called as recursive maze problem.
Question- 3) Explain Hamiltonian Circuit Problems?
Answer: Hamiltonian circuit problems are the ones which have a condition that each and every node of the given graph must be visited for exactly one time.
Real life examples include electrical connections in a household, a complete route from a source location to destination and back to source in a different route.
Question- 4) Explain Subset-Sum Problem?
Answer: A set can be defined as a collection of homogeneous elements. Array is considered to be the basic data structure where as even other data structures can also are considered for a set. Sets in java are more popularly considered as the data structure to represent set than an array. Subset is considered to be a portion of sets. A subset may be of length zero to a complete set length. The subset problem deals with the extraction of a subset from a set upon the given condition.
Question- 5) Explain N-Queens Problem?
Answer: N Queens's problem deal with the placement of N number of queens on a square maze where distance between two queens should be greater than one unit in any dimension, i.e., either of row, column or diagonal.
Question- 6) Explain m-color Problem?
Answer: m-color problem deals with coloring of nodes for given graph with the condition that no two adjacent nodes should have same color.
The minimum number of colors possible with the above condition for a given graph/cycle is called as chromatic number.
The m-color problem is also popularly called as vertex-coloring problem.
Question- 7) Explain with example the implementation of Backtracking in Knapsack problem.
Answer: Knapsack problem deals with finding the maximum possible value against least possible sum of weights for the given set of pairs of weights and values.
As already discussed backtracking is the mechanism which implements multiple recursions to find the optimal possibility.
As Knapsack being one such target problem of backtracking, thus, backtracking is also considered to be one of the solution approaches to solve knapsack.
Example: Consider the following example,
Question- 8) Give an example of back tracking in daily life.
Answer: The real life examples of back tracking in day to day life are as follows:
Solving a Sudoku puzzle
Finding the shortest path in the graph between two nodes. (In GPS tracking)
Finding the safer ways for a coin to move in a chess board.
Question- 9) Draw State Space Tree can be drawn as follows. {5, 10, 12, 13, 15, 18} M=30.
Answer:
