Exam Details
| Subject | design & analysis of algorithms(daa) | |
| Paper | ||
| Exam / Course | mca | |
| Department | ||
| Organization | Gujarat Technological University | |
| Position | ||
| Exam Date | November, 2018 | |
| City, State | gujarat, ahmedabad |
Question Paper
1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER-V EXAMINATION WINTER 2018
Subject Code: 3650001 Date: 15/11/2018
Subject Name: Design Analysis of Algorithms
Time: 10.30 am to 1.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
Give the difference between greedy algorithms and Dynamic Algorithms.
Explain how the efficiency of an iterative algorithm can be increased?
What do you mean by Decrease and conquer? Give examples
03
02
02
I)Define the following terms
Algorithm
Optimal Solution
Pruning
Space Complexity
II) Define recursion. What are the advantages of using recursion and discuss about its implementation issues.
04
03
Q.2
What do you understand by analysis of algorithm? Write a note on Asymptotic notations.
07
Explain the algorithm using D C method to multiply two large matrices.
07
OR
Explain the use of D C technique for Binary Search Method. Give the algorithm for the same. Give its time complexity for its best average and worst cases.
07
Q.3
Define MST. Explain Kruskal's Algorithm. How to solve it using union-find Data structure.
07
Using greedy algorithm find an optimal scheduling for the following jobs to be completed in given deadlines.
07
OR
Q.3
Explain Dijikstra's Shortest path Algorithm
07
Find Longest common subsequence for the following data
ABCBDA
Y=BDCABA
Also discuss the algorithm.
07
Q.4
Explain matrix chain multiplication algorithm. Find out minimum number of multiplications required for multiplying matrices A[1 X B[5 X C[4 X D[3 X E[2 X 1]. Also give the optimal parenthesization of matrices
07
Write a note on BFS and explain it giving an example.
07
OR
2
Q.4
Explain Rod Cutting problem. Find the maximum profit for the following data.
Length of the rod 5
Profit for 4 cuts of unit are
Also give the algorithm for the same.
07
Write a note on DFS and explain it giving an example.
07
Q.5
Write a note on 8 puzzle problem
07
Write a short on TSP. How it can be solved using branch and Bound strategy? Explain it with an example
07
OR
Q.5
Explain Branch Bound strategy to solve a problem and explain 0-1 knapsack problem
07
Write a note on NP-hard and NP complete algorithms.
07
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER-V EXAMINATION WINTER 2018
Subject Code: 3650001 Date: 15/11/2018
Subject Name: Design Analysis of Algorithms
Time: 10.30 am to 1.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
Give the difference between greedy algorithms and Dynamic Algorithms.
Explain how the efficiency of an iterative algorithm can be increased?
What do you mean by Decrease and conquer? Give examples
03
02
02
I)Define the following terms
Algorithm
Optimal Solution
Pruning
Space Complexity
II) Define recursion. What are the advantages of using recursion and discuss about its implementation issues.
04
03
Q.2
What do you understand by analysis of algorithm? Write a note on Asymptotic notations.
07
Explain the algorithm using D C method to multiply two large matrices.
07
OR
Explain the use of D C technique for Binary Search Method. Give the algorithm for the same. Give its time complexity for its best average and worst cases.
07
Q.3
Define MST. Explain Kruskal's Algorithm. How to solve it using union-find Data structure.
07
Using greedy algorithm find an optimal scheduling for the following jobs to be completed in given deadlines.
07
OR
Q.3
Explain Dijikstra's Shortest path Algorithm
07
Find Longest common subsequence for the following data
ABCBDA
Y=BDCABA
Also discuss the algorithm.
07
Q.4
Explain matrix chain multiplication algorithm. Find out minimum number of multiplications required for multiplying matrices A[1 X B[5 X C[4 X D[3 X E[2 X 1]. Also give the optimal parenthesization of matrices
07
Write a note on BFS and explain it giving an example.
07
OR
2
Q.4
Explain Rod Cutting problem. Find the maximum profit for the following data.
Length of the rod 5
Profit for 4 cuts of unit are
Also give the algorithm for the same.
07
Write a note on DFS and explain it giving an example.
07
Q.5
Write a note on 8 puzzle problem
07
Write a short on TSP. How it can be solved using branch and Bound strategy? Explain it with an example
07
OR
Q.5
Explain Branch Bound strategy to solve a problem and explain 0-1 knapsack problem
07
Write a note on NP-hard and NP complete algorithms.
07
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)