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 | December, 2015 | |
| City, State | new delhi, |
Question Paper
Explain the characteristics of a problem that can be solved efficiently by using Dynamic programming technique.
Differentiate between generating function and bounding function.
Discuss string matching algorithm with the help of an example.
2.(a) Illustrate the operations of Heap-extract max on the heap
A 1}.
Describe the performance of quick-sort.
3. How does backtracking work on the 8 Queens problem Describe with the help of suitable examples.
4.(a) What is hashing Explain the different methods of hashing. Explain amortized balanced tree.
5.(a) Solve the recurrence relation, where 1 and for n 2 satisfies n.
(b) Explain matrix multiplication using divide and conquer technique.
6.(a) What are NP, Co-NP, NP-Hard and NP-Complete problems? Prove that the vertex-cover is NP-Complete.
7.(a) Write an algorithm for BFS. Solve the water jug problem using BFS, considering two jugs, one of which can store 4 gallons of water and the other can store 3 gallons of water. How will you measure 2 gallons of water in 4-gallons jug? Write Prim's algorithm. Find the minimum cost spanning tree using Prim's algorithm for the tree below. <img src='./qimages/13299-7b.jpg'>
8.(a) Define the Hamiltonian cycle problem. Explain Monte Carlo algorithm.
9. Explain, with the help of an example, Las Vegas algorithm for search.
10. Write short notes on any two of the following:
(a) Floyd-Warshall Algorithm Bellman-Ford Algorithm Universal Hashing
Differentiate between generating function and bounding function.
Discuss string matching algorithm with the help of an example.
2.(a) Illustrate the operations of Heap-extract max on the heap
A 1}.
Describe the performance of quick-sort.
3. How does backtracking work on the 8 Queens problem Describe with the help of suitable examples.
4.(a) What is hashing Explain the different methods of hashing. Explain amortized balanced tree.
5.(a) Solve the recurrence relation, where 1 and for n 2 satisfies n.
(b) Explain matrix multiplication using divide and conquer technique.
6.(a) What are NP, Co-NP, NP-Hard and NP-Complete problems? Prove that the vertex-cover is NP-Complete.
7.(a) Write an algorithm for BFS. Solve the water jug problem using BFS, considering two jugs, one of which can store 4 gallons of water and the other can store 3 gallons of water. How will you measure 2 gallons of water in 4-gallons jug? Write Prim's algorithm. Find the minimum cost spanning tree using Prim's algorithm for the tree below. <img src='./qimages/13299-7b.jpg'>
8.(a) Define the Hamiltonian cycle problem. Explain Monte Carlo algorithm.
9. Explain, with the help of an example, Las Vegas algorithm for search.
10. Write short notes on any two of the following:
(a) Floyd-Warshall Algorithm Bellman-Ford Algorithm Universal Hashing
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