Exam Details
| Subject | Design and Analysis of Algorithm | |
| Paper | ||
| Exam / Course | B.Tech In Computer Science And Engineering (BTCSVI) | |
| Department | School of Engineering & Technology (SOET) | |
| Organization | indira gandhi national open university | |
| Position | ||
| Exam Date | June, 2016 | |
| City, State | new delhi, |
Question Paper
No. of Printed Pages: 3 IBICS-OI4I
B.Tech. -VIEP -COMPUTER SCIENCE AND ENGINEERING (BTCSVI) Term-End Examination ..:J0436 June, 2016
sics-a14 DESIGN AND ANALYSIS OF ALGORITHM
Time: 3 hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks.
1. What is the difference between BFS and DFS? 3
What is the difference between binary search and Fibonacci search? 3
Write Kruskal's algorithm for minimum spanning tree. 4
2. Why is the worst case analysis of an algorithm more important than the average case analysis 4
Explain various asymptotic methods used to represent the rate of growth of running time of algorithms. 6
3. Write down the "Dixon integer factorization algorithm" stepwise. 10
4. Write a backtracking program for solving the knapsack optimization problem. Explain elaborately recursive backtracking algorithm. 10
5. What is dynamic programming How is it different from greedy approach Explain its characteristics with examples. 10
6. Describe an algorithm with an example to compute the binomial coefficient and derive its efficiency. 10
7. Write an algorithm to search an item in a linear list. If there are nodes in the list, what is the running time of your algorithm? 10
8. Prove that the Clique problem is NP complete. 5
Explain Rabin-Karp string matching technique with a suitable example. 5
9. Sort the given values using Quick sort algorithm: 5
65,70,75,80,85,60,55,50,45
What is the Matrix Chain Multiplication Problem? 5
10. Write short notes on any two of the following: 2x5=10
Travelling Salesperson Problem
Input Enhancement in String Matching
Decision Trees
B.Tech. -VIEP -COMPUTER SCIENCE AND ENGINEERING (BTCSVI) Term-End Examination ..:J0436 June, 2016
sics-a14 DESIGN AND ANALYSIS OF ALGORITHM
Time: 3 hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks.
1. What is the difference between BFS and DFS? 3
What is the difference between binary search and Fibonacci search? 3
Write Kruskal's algorithm for minimum spanning tree. 4
2. Why is the worst case analysis of an algorithm more important than the average case analysis 4
Explain various asymptotic methods used to represent the rate of growth of running time of algorithms. 6
3. Write down the "Dixon integer factorization algorithm" stepwise. 10
4. Write a backtracking program for solving the knapsack optimization problem. Explain elaborately recursive backtracking algorithm. 10
5. What is dynamic programming How is it different from greedy approach Explain its characteristics with examples. 10
6. Describe an algorithm with an example to compute the binomial coefficient and derive its efficiency. 10
7. Write an algorithm to search an item in a linear list. If there are nodes in the list, what is the running time of your algorithm? 10
8. Prove that the Clique problem is NP complete. 5
Explain Rabin-Karp string matching technique with a suitable example. 5
9. Sort the given values using Quick sort algorithm: 5
65,70,75,80,85,60,55,50,45
What is the Matrix Chain Multiplication Problem? 5
10. Write short notes on any two of the following: 2x5=10
Travelling Salesperson Problem
Input Enhancement in String Matching
Decision Trees
Other Question Papers
Departments
- Centre for Corporate Education, Training & Consultancy (CCETC)
- Centre for Corporate Education, Training & Consultancy (CCETC)
- National Centre for Disability Studies (NCDS)
- School of Agriculture (SOA)
- School of Computer and Information Sciences (SOCIS)
- School of Continuing Education (SOCE)
- School of Education (SOE)
- School of Engineering & Technology (SOET)
- School of Extension and Development Studies (SOEDS)
- School of Foreign Languages (SOFL)
- School of Gender Development Studies(SOGDS)
- School of Health Science (SOHS)
- School of Humanities (SOH)
- School of Interdisciplinary and Trans-Disciplinary Studies (SOITDS)
- School of Journalism and New Media Studies (SOJNMS)
- School of Law (SOL)
- School of Management Studies (SOMS)
- School of Performing Arts and Visual Arts (SOPVA)
- School of Performing Arts and Visual Arts(SOPVA)
- School of Sciences (SOS)
- School of Social Sciences (SOSS)
- School of Social Work (SOSW)
- School of Tourism & Hospitality Service Sectoral SOMS (SOTHSM)
- School of Tourism &Hospitality Service Sectoral SOMS (SOTHSSM)
- School of Translation Studies and Training (SOTST)
- School of Vocational Education and Training (SOVET)
- Staff Training & Research in Distance Education (STRIDE)
Subjects
- Advanced Computer Architecture
- Artificial Intelligence
- Computer Architecture
- Computer Networks
- Computer Organisations
- Cryptography And Network Security
- Data Structure
- Data Warehousing And Mining
- Database Management System
- Design and Analysis of Algorithm
- Digital Image Processing
- Discrete Maths Structure
- E-Business
- Formal Language And Automata
- Logic Design
- Microprocessor
- Mobile Computing
- Object Oriented Programming
- Operating Systems
- Parallel Algorithms
- Pattern Recognition
- Principles of Programming Lang.
- Real Time Systems
- Software Engineering
- Software Quality Engineering
- Software Reusability
- System Programming And Compiler Design
- Theory Of Computation
- Unix Internals And Shell Programming
- Web Technology