Exam Details
| Subject | Design and Analysis of Algorithm | |
| Paper | ||
| Exam / Course | Post Graduate Diploma in Computer Application (PGDCA)/ Advance Diploma inComputer Applications (ADCA) / Masters in Computer Applications (MCA) | |
| Department | School of Computer and Information Sciences (SOCIS) | |
| Organization | indira gandhi national open university | |
| Position | ||
| Exam Date | December, 2015 | |
| City, State | new delhi, |
Question Paper
Write recursive binary search algorithm and analyse its run time complexity.
Solve the recurrence 2T n 2 n 2.
Using Dijkstra's algorithm, find the minimum distances of all the nodes from source node for the following graph: <img src='./qimages/14213-1c.jpg'> Construct a Turing Machine to accept all languages of palindromes on alphabet E b). Explain matrix multiplication using dynamic programming. What is minimax principle Explain with the help of an example.
2.(a) Obtain the minimum cost spanning tree for the following graph using Prim's algorithm. <img src='./qimages/14213-2a.jpg'> Obtain the DFS tree for the graph given in Q.no. considering node as root node. Explain the Chomsky's classification of grammars.
3.(a) Enumerate any five well-known techniques for designing algorithms for solving problems. Sort the following elements using Heap Sort
10,28,46,39,15,12,18,9,56,2.
Show each step, while creating a heap and processing a heap.
For any set S of strings prove that
4.(a) Arrange the following growth rates in increasing order
O(n log O(log n). For the function
f(x) 4x^3 6x
show that
but x^4
What is Pushdown Automata Build a PDA that accepts the language even palindrome.
5.(a) What is Satisfiability problem Explain briefly.
Prove that the running time of binary search algorithm in worst case is O(log2n). Using Bubble Sort, sort the following sequence in increasing order:
11,21,6,14,8,12,28,32. Write a note on regular languages.
Solve the recurrence 2T n 2 n 2.
Using Dijkstra's algorithm, find the minimum distances of all the nodes from source node for the following graph: <img src='./qimages/14213-1c.jpg'> Construct a Turing Machine to accept all languages of palindromes on alphabet E b). Explain matrix multiplication using dynamic programming. What is minimax principle Explain with the help of an example.
2.(a) Obtain the minimum cost spanning tree for the following graph using Prim's algorithm. <img src='./qimages/14213-2a.jpg'> Obtain the DFS tree for the graph given in Q.no. considering node as root node. Explain the Chomsky's classification of grammars.
3.(a) Enumerate any five well-known techniques for designing algorithms for solving problems. Sort the following elements using Heap Sort
10,28,46,39,15,12,18,9,56,2.
Show each step, while creating a heap and processing a heap.
For any set S of strings prove that
4.(a) Arrange the following growth rates in increasing order
O(n log O(log n). For the function
f(x) 4x^3 6x
show that
but x^4
What is Pushdown Automata Build a PDA that accepts the language even palindrome.
5.(a) What is Satisfiability problem Explain briefly.
Prove that the running time of binary search algorithm in worst case is O(log2n). Using Bubble Sort, sort the following sequence in increasing order:
11,21,6,14,8,12,28,32. Write a note on regular languages.
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
- Accounting and Financial Management
- Advanced Database Design
- Advanced Discrete Mathematics
- Advanced Internet Technologies
- Artificial Intelligence and Knowledge Management
- Communication Skills
- Computer Graphics and Multimedia
- Computer Organisation & Assembly Language Programming
- Data and File Structure
- Data Communication and Computer Networks
- Database Management System
- Database Management Systems
- Design and Analysis of Algorithm
- Discrete Mathematics
- Elements of Systems Analysis & Design
- Numerical and Statistical Computing
- Object Oriented Analysis and Design
- Object Oriented Technologies and Java Programming
- Operating System Concepts and Networking Management
- Operating Systems
- Parallel Computing
- Principles of Management and Information Systems
- Problem Solving and Programming
- Software Engineering
- Systems Analysis and Design