SPRING 2014 ASSIGNMENT
PROGRAM - Master of Science in Information Technology (MSc IT)Revised Fall 2011
SEMESTER - 2
SUBJECT CODE & NAME – MCA4040- ANALYSIS AND DESIGN OF ALGORITHMS
CREDIT 4 BK ID B1480 MAX. MARKS 60
You can pay in 6 instalment of Rs 125-125 if u have any doubt.
computeroperator4@gmail.com
www.smuassignment.in
www.assignmenthelpforall.blogspot.in
Q. No. 1 Write the steps involved in analyzing the efficiency of non-recursive algorithms. 10
Answer:
The steps involved in analyzing the efficiency of non-recursive algorithms are as follows:
Decide the input size based on the constraint n
Identify the basic operations of algorithm
2 Define selection sort and explain how to implement the selection sort? 3+7=10
Answer:
Definition: Selection sort is one of the simplest and performance oriented sorting techniques that work well for small files. It has time complexity as O(n2) which is unproductive on large lists.
3 What is mean by Topological sort? And explain with example. 5+5=10
Answer: Topological sort is done using a directed acyclic graph (DAG), which is a linear ordering of all vertices G= (V, E) is an ordering of all vertices such that if G contains an edge (u, v), then u appears before v in the ordering. A topological sort of a particular graph can be looked upon as a horizontal line where all directed edges travel from left to right. Thus, topological sort
4. Explain good-suffix and bad-character shift in Boyer-Moore algorithm. 5+5=10
Answer: Good suffix Shift
This shift helps in shifting a matched part of the pattern, and is denoted by Q. Good suffix shift Q is applied after 0 < k < m characters are matched.
Q = distance between matched suffix of size k and its rightmost occurrence in the pattern that is
5 Solve the Knapsack problem using memory functions.
Item 1 2 3 4
Weight 2 6 4 8
Value (in Rs.) 12 16 30 40
Knapsack capacity is given as W=12. Analyze the Knapsack problem using memory functions with the help of the values given above. 10
Answer:
Knapsack Problem by Memory Functions
| I | 0 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
6 Any NP problem can be converted into SAT (Satisfiability problem) in polynomial time. Explain in detail. 4+6=10
Answer: Stephen Cook in 1971 stated that
“Any NP problem can be converted into SAT (Satisfiability problem) in polynomial time”
Satisfiability problem SAT – This is a decision problem whose instance uses only AND, OR and
No comments:
Post a Comment