Get fully solved assignment. Buy online from website
online store
or
plz drop a mail with your sub code
we will revert you within 2-3 hour or immediate
Charges rs
125/subject and rs 500/semester only.
if urgent then call us on 08791490301, 08273413412
PROGRAM
BSc
IT
SEMESTER
FOURTH
SUBJECT
CODE & NAME
BT0080,
Fundamentals of Algorithms
Qus:1
Describe insertion sort algorithm with the help of an example. Give the
complexity of it.
Answer:
Insertion
sort algorithm:
The insertion sort,
algorithm for sorting a list L of n numbers represented by an array A [1... n]
proceeds by picking up the numbers in the array from left one by one and each
newly picked up number is placed at its relative position, w.r.t. the sorting order,
among the earlier ordered ones. The process is repeated till
Qus:2
State the concept of divide and conquer strategy with the help of an example.
Answer:
The
concept of divide and conquer strategy:
Given a function to
compute on n inputs, the divide-and-conquer strategy suggests splitting the
inputs into K distinct subsets, 1<K<n, yielding K subproblems. These
subproblems must be solved and
Qus:3
Explain knapsack problem. Write algorithm for it.
Answer:
Knapsack
Problem:
Given n objects and a
knapsack or bag. Object i has a weight wi, and the knapsack has a capacity m.
If a fraction xi, 0 xi 1, of object i is placed into the knapsack, then a
profit of Pi xi is earned. The objective is to
Qus:4
Explain trees and subgraphs with examples.
Answer:
Trees
and Subgraphs:
Trees:
A tree is a connected
graph without any circuits. The graph in Fig. A, for instance, is a tree. Trees
with one, two, three and four vertices are shown in Fig. B. A graph must have
at least one vertex, and
Q5.
State Cook’s theorem.
Prove
the theorem “CNF satisfiability is polynomially transformable to the clique
problem. Therefore, the clique problem is NP complete.”
Answer:
Proof: Let F=F1
F2…….Fq be an expression in CNF, where the Fi’ s are the factors,
each Fi is of the form (xi1+xi2+…..xik) where
xij is a literal. Construct an undirected graph G=(V,E) whose vertices are
pairs of integers [i,j] for 1≤ i ≤q and 1≤ j ≤k.
First component represents a
factor
Qus:6
Define and explain Hamiltonian circuit and path.
Answer:
Hamiltonian
circuit and path:
Hamiltonian
Circuit: A Hamiltonian circuit in a connected graph is
defined as a closed walk that traverses every vertex of G exactly once, except
of course, the starting vertex, at which the walk also terminates. A circuit in
a connected graph G is said to be Hamiltonian as it includes every vertex of G.
Hence
Get fully solved assignment. Buy online from website
online store
or
plz drop a mail with your sub code
we will revert you within 2-3 hour or immediate
Charges rs
125/subject and rs 500/semester only.
if urgent then call us on 08791490301, 08273413412
No comments:
Post a Comment