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
1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA- SEMESTER EXAMINATION -SUMMER-2019
Subject Code:3650001 Date: 02-05-2019
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
i. Worst case running time for Radix Sort is
ii. Average case running time for Bubble Sort is
iii. To denote two string ab and ac RE will be
iv. Prims and Kruskal Algorithms are used for tree.
v. Algorithm is used to find the shortest path.
vi. NPT stands for
vii. ET stands for
07
Explain Big Omega and Theta Notation.
07
Q.2
Solve the Traveling salesman problem using dynamic programming for given connection matrix for 4-nodes graph.
0
10
15
20
5
0
9
10
6
13
0
12
8
8
9
0
07
What is Top Down design method? Explain with example of gcd.
07
OR
i. Discuss some of ways to improve the efficiency of algorithm.
ii. Explain where D&C fails.
05
02
Q.3
Explain Multiplication of N-Digit integers using Divide and Conquer. Consider 2345 and 6789 as two numbers for example.
07
Explain Binary Search? Write an iterative algorithm for binary search and explain the best, average and worst case in O notation.
07
OR
Q.3
Discuss Strassen Matrix Multiplication with example.
07
What is Merge Sort? Write a recursive algorithm for merge sort and discuss time complexity of merge sort.
07
Q.4
Explain Greedy Strategy. Discuss Knapsack problem for P and
07
Explain Dynamic programming. Explain how it is used for coin exchange problem if we have coin with denomination 4 and 6 units and we want to make change of 8 units.
07
OR
Q.4
List and explain four steps in dynamic programming solution.
07
Discuss union and find data structure with example.
07
Q.5
Give simplified definition of Explain Transitivity Rule, Sum Rule, Polynomial Rule, Constant absorption rule and Multiplication Rule of Notation.
07
2
Explain execution time of straight line programs, programs loops and recursive programs.
07
OR
Q.5
Discuss Backtracking Strategy. Explain how it can be used to solve the 4-queen problem
07
Explain DFS and BFS. Write an algorithm for BFS and discuss the total running time of BFS.
07
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA- SEMESTER EXAMINATION -SUMMER-2019
Subject Code:3650001 Date: 02-05-2019
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
i. Worst case running time for Radix Sort is
ii. Average case running time for Bubble Sort is
iii. To denote two string ab and ac RE will be
iv. Prims and Kruskal Algorithms are used for tree.
v. Algorithm is used to find the shortest path.
vi. NPT stands for
vii. ET stands for
07
Explain Big Omega and Theta Notation.
07
Q.2
Solve the Traveling salesman problem using dynamic programming for given connection matrix for 4-nodes graph.
0
10
15
20
5
0
9
10
6
13
0
12
8
8
9
0
07
What is Top Down design method? Explain with example of gcd.
07
OR
i. Discuss some of ways to improve the efficiency of algorithm.
ii. Explain where D&C fails.
05
02
Q.3
Explain Multiplication of N-Digit integers using Divide and Conquer. Consider 2345 and 6789 as two numbers for example.
07
Explain Binary Search? Write an iterative algorithm for binary search and explain the best, average and worst case in O notation.
07
OR
Q.3
Discuss Strassen Matrix Multiplication with example.
07
What is Merge Sort? Write a recursive algorithm for merge sort and discuss time complexity of merge sort.
07
Q.4
Explain Greedy Strategy. Discuss Knapsack problem for P and
07
Explain Dynamic programming. Explain how it is used for coin exchange problem if we have coin with denomination 4 and 6 units and we want to make change of 8 units.
07
OR
Q.4
List and explain four steps in dynamic programming solution.
07
Discuss union and find data structure with example.
07
Q.5
Give simplified definition of Explain Transitivity Rule, Sum Rule, Polynomial Rule, Constant absorption rule and Multiplication Rule of Notation.
07
2
Explain execution time of straight line programs, programs loops and recursive programs.
07
OR
Q.5
Discuss Backtracking Strategy. Explain how it can be used to solve the 4-queen problem
07
Explain DFS and BFS. Write an algorithm for BFS and discuss the total running time of BFS.
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)