Exam Details
| Subject | design & analysis of algorithms(daa) | |
| Paper | ||
| Exam / Course | mca | |
| Department | ||
| Organization | Gujarat Technological University | |
| Position | ||
| Exam Date | May, 2019 | |
| City, State | gujarat, ahmedabad |
Question Paper
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA Integrated SEMESTER IX-EXAMINATION SUMMER- 2019
Subject Code: 4490601 Date: 02-05-2019
Subject Name: Design Analysis of Algorithms
Time: 02.30 pm to 5.00 pm Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1 Define the following questions:
07
i. Define Time complexity.
ii.Define Feasible Solution.
iii.Define P-type Problem.
iv.Define Algorithm.
v. Define Minimum Spanning Tree.
vi. Write down the Best case, Worst Case and Average case Complexity for
Heap sort.
vii. Define Optimal Solution.
Explain the difference between Greedy and Dynamic Algorithm.
07
Q.2
Explain Knapsack Problem using Greedy Approach With Example.
07
Analyze Selection sort algorithm in best case and worst case.
07
OR
Analyze Quick sort algorithm in best case and worst case.
07
Q.3
What is recurrence? Solve recurrence equation T n using forward
07
substitution and backward substitution method.
Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60, 25, 10, 40.
07
OR
Q.3
Explain Backtracking concept and apply the same on 8-queen problem.
07
Write equation for Chained matrix multiplication using Dynamic programming.
07
Find out optimal sequence for multiplication:
A1 × A2 × A3 × and A4 × 7]. Also give the optimal
Parenthesization of matrices.
Q.4
Explain Breadth First Search methods of Graph with algorithm with example.
07
Explain how to find out Longest Common Subsequence of two strings using
07
Dynamic Programming method. Find any one Longest Common Subsequence of
Given two strings using Dynamic Programming.
X=abbacdcba
Y=bcdbbcaac
OR
Q.4
Define NP, NP complete and NP-Hard problems. Give examples of each.
07
Explain Branch and Bound Technique with Suitable Example.
07
Q.5
Discuss matrix multiplication problem using divide and conquer technique.
07
Discuss Assembly Line Scheduling problem using dynamic programming with
07
example.
OR
Q.5
Explain 8 Puzzle Problem With Example..
07
Design and Explain Dijkstra's shortest path algorithm.
07
1
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA Integrated SEMESTER IX-EXAMINATION SUMMER- 2019
Subject Code: 4490601 Date: 02-05-2019
Subject Name: Design Analysis of Algorithms
Time: 02.30 pm to 5.00 pm Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1 Define the following questions:
07
i. Define Time complexity.
ii.Define Feasible Solution.
iii.Define P-type Problem.
iv.Define Algorithm.
v. Define Minimum Spanning Tree.
vi. Write down the Best case, Worst Case and Average case Complexity for
Heap sort.
vii. Define Optimal Solution.
Explain the difference between Greedy and Dynamic Algorithm.
07
Q.2
Explain Knapsack Problem using Greedy Approach With Example.
07
Analyze Selection sort algorithm in best case and worst case.
07
OR
Analyze Quick sort algorithm in best case and worst case.
07
Q.3
What is recurrence? Solve recurrence equation T n using forward
07
substitution and backward substitution method.
Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60, 25, 10, 40.
07
OR
Q.3
Explain Backtracking concept and apply the same on 8-queen problem.
07
Write equation for Chained matrix multiplication using Dynamic programming.
07
Find out optimal sequence for multiplication:
A1 × A2 × A3 × and A4 × 7]. Also give the optimal
Parenthesization of matrices.
Q.4
Explain Breadth First Search methods of Graph with algorithm with example.
07
Explain how to find out Longest Common Subsequence of two strings using
07
Dynamic Programming method. Find any one Longest Common Subsequence of
Given two strings using Dynamic Programming.
X=abbacdcba
Y=bcdbbcaac
OR
Q.4
Define NP, NP complete and NP-Hard problems. Give examples of each.
07
Explain Branch and Bound Technique with Suitable Example.
07
Q.5
Discuss matrix multiplication problem using divide and conquer technique.
07
Discuss Assembly Line Scheduling problem using dynamic programming with
07
example.
OR
Q.5
Explain 8 Puzzle Problem With Example..
07
Design and Explain Dijkstra's shortest path algorithm.
07
1
Other Question Papers
Subjects
- advance database management system
- advanced biopharmaceutics & pharmacokinetics
- advanced medicinal chemistry
- advanced networking (an)
- advanced organic chemistry -i
- advanced pharmaceutical analysis
- advanced pharmacognosy-1
- advanced python
- android programming
- artificial intelligence (ai)
- basic computer science-1(applications of data structures and applications of sql)
- basic computer science-2(applications of operating systems and applications of systems software)
- basic computer science-3(computer networking)
- basic computer science-4(software engineering)
- basic mathematics
- basic statistics
- big data analytics (bda)
- big data tools (bdt)
- chemistry of natural products
- cloud computing (cc)
- communications skills (cs)
- computer aided drug delivery system
- computer graphics (cg)
- computer-oriented numerical methods (conm)
- cyber security & forensics (csf)
- data analytics with r
- data mining
- data structures (ds)
- data visualization (dv)
- data warehousing
- data warehousing & data mining
- database administration
- database management system (dbms)
- design & analysis of algorithms(daa)
- digital technology trends ( dtt)
- discrete mathematics for computer science (dmcs)
- distributed computing (dc1)
- drug delivery system
- dynamic html
- enterprise resource planning (erp)
- food analysis
- function programming with java
- fundamentals of computer organization (fco)
- fundamentals of java programming
- fundamentals of networking
- fundamentals of programming (fop)
- geographical information system
- image processing
- industrial pharmacognostical technology
- information retrieving (ir)
- information security
- java web technologies (jwt)
- language processing (lp)
- machine learning (ml)
- management information systems (mis)
- mobile computing
- molecular pharmaceutics(nano tech and targeted dds)
- network security
- object-oriented programming concepts & programmingoocp)
- object-oriented unified modelling
- operating systems
- operation research
- operations research (or)
- pharmaceutical validation
- phytochemistry
- procedure programming in sql
- programming skills-i (ps-i-fop)
- programming skills-ii (ps-oocp)
- programming with c++
- programming with java
- programming with linux, apache,mysql, and php (lamp)
- programming with python
- search engine techniques (set)
- soft computing
- software development for embedded systems
- software engineering
- software lab (dbms: sql & pl/sql)
- software project in c (sp-c)
- software project in c++ (sp-cpp)
- software quality and assurance (sqa)
- statistical methods
- structured & object oriented analysis& design methodology
- system software
- virtualization and application of cloud
- web commerce (wc)
- web data management (wdm)
- web searching technology and search engine optimization
- web technology & application development
- wireless communication & mobile computing (wcmc)
- wireless sensor network (wsn)