BT0080,Fundamental of Algorithms

Dear students get fully solved assignments

Send your semester & Specialization name to our mail id :

“ help.mbaassignments@gmail.com ”

or

Call us at : 08263069601

ASSIGNMENT

PROGRAM	BSc IT
SEMESTER	FOURTH
SUBJECT CODE & NAME	BT0080,Fundamental of Algorithms
CREDIT	4
BK ID	B1092
MAX. MARKS	60

Q1. Explain recursion with the help of an example.

Answer:- "Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way. For instance, when the surfaces of two mirrors are almost parallel with each other the nested images that occur are a form of recursion. It is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.

What is recursion used for?

Recursion is best used for problems where a large task can be broken down into a repetitive “sub-task”. Because a recursive routine calls itself to perform those sub-tasks, eventually the routine will come across a sub-task that it can handle without calling itself. This is

Q2.Describe binary search algorithm with the help of an example.

Answer:- Binary search algorithm

Generally, to find a value in unsorted array, we should look through elements of an array one by one, until searched value is found. In case of searched value is absent from array, we go through all elements. In average, complexity of such an algorithm is proportional to the length of the array.

Situation changes significantly, when array is sorted. If we know it, random access capability can be utilized very efficiently to find searched value quick. Cost of searching algorithm reduces to binary logarithm of the array length. For reference, log₂(1 000 000) ≈ 20. It means, that in worst case, algorithm makes 20 steps to find a value in sorted array of a million elements or to say, that it doesn't present it the array.

Algorithm

 

 

Q3. Describe the branch and bound algorithms for travelling salesman problem.

Answer:- Definitions:

•             Branch and Bound is a state space search method in which all the children of a node are generated before expanding any of its children.

Travelling Salesman Problem: A Branch and Bound algorithm

·        Definition: Find a tour of minimum cost starting from a node S going through other nodes only once and returning to the

·         

Q.4 Explain trees and sub graphs with examples.

Answer:-Tree: - A tree is a connected graph without any cycles, or a tree is a connected acyclic graph. The edges of a tree are called branches. It follows immediately from the definition that a tree has to be a simple graph (because self-loops and parallel edges both form cycles). Figure 4.1(a) displays all treewith fewer than six vertices.

Q5. Define spanning trees.  Explain Kruskal’s algorithm to find out minimal cost spanning trees.

Answer: In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that includes all of the vertices of G that is a tree. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (but see Spanning forests below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself).

The Kruskal’s Method to Find a Minimal S panning Tree :

One of the famous problems which can be solved by the greedy method is the minimal spanning tree problem. Minimal spanning trees can be defined on either or on a graph. For Kruskal’s method, minimal spanning trees are defined on graphs.

Definition: Let G=(V,E) be a weighted connected undirected graph where V represent the set of vertices and E represents the set of edges. A spanning tree of G

Q.6 Define and explain Hamiltonian circuit and path.

Answer: - A graph that contains a Hamiltonian cycle is called a Hamiltonian graph. Similar notions may be defined for directed graphs, where each edge (arc) of a path or cycle can only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced "tail-to-head").

Hamiltonian path: - a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

Hamiltonian paths and cycles and cycle paths are

Dear students get fully solved assignments

Send your semester & Specialization name to our mail id :

“ help.mbaassignments@gmail.com ”

or

Call us at : 08263069601