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, 2016 | |
| City, State | new delhi, |
Question Paper
No. of Printed Pages: 4
IBICS-OI4I
B.Tech. -VIEP -COMPUTER SCIENCE AND
ENGINEERING (BTCSVI)
Term-End Examination
December, 2016
003U4
BICS-014: DESIGN AND ANALYSIS OF ALGORITHM
Time: 3 hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks.
1. Determine the time-complexity of the pseudocode given below, using Big-O notation:
int psum (int
{int partial_sum;
partial_sum
for i i
{partial_sum =partial_sum i
}return partial_sum;
}
State Master's theorem. The recursive equation of time-complexity of an algorithm is given by x T n^2. Find the asymptotic bounds of using Master's theorem. 5
2. Write the algorithm for Quick Sort. Apply it to sort the following data:
25 10 30 15 20 28
Analyse the performance of Quick Sort. 3 4 3
3. What is Aggregate Analysis? A sequence of n operations is performed on a data structure and the ith operation costs if i is an exact power of 2 and 1 otherwise. Apply Aggregate Analysis to determine the amortized cost per operation. 5
Write Strassen's algorithm. Apply it to multiply the following matrices: 2 3
5 6 and 6
3 5 9
4. Write Kruskal's algorithm. Apply the algorithm to the following graph and find the minimum spanning tree: 2 8 <img src='./qimages/8717-4.jpg'>
5. Two algorithms, A1 and A2, run on the same machine. The running time of Al is 100 n^2 and the running time of A2 is 2^n. Find the value of for which Al runs faster than A2. Based on the value of n comment on the performance of Al and A2. 5
What is fractional knapsack problem Consider 5 items along with their respective weights and values given below:
I I1, I2, I3, I4, I5>
w= 10, 20, 30, 40 30, 20, 100, 90, 160
The capacity of knapsack W 60. Find the solution to the fractional knapsack problem. 5
6. Discuss the Travelling Salesman Problem. Use it to compute the minimum travel cost, for the tour plan of the sales agent, shown below: 4 6 <img src='./qimages/8717-6.jpg'>
7. Write short notes on any two of the following: 2x5=10 Knuth-Morris-Pratt Algorithm CYK Algorithm Monte Carlo Algorithm
8. Briefly discuss the following complexity classes with suitable examples: 5x2=10 P NP co-NP NP-Hard NP-Complete
9. Explain the term Matroids, with suitable example. 5
Explain Huffman coding, with suitable example. 5
10. Write the iterative and recursive algorithms to find the sum of n integers. Compare the complexity of the algorithms. 3 3 4
IBICS-OI4I
B.Tech. -VIEP -COMPUTER SCIENCE AND
ENGINEERING (BTCSVI)
Term-End Examination
December, 2016
003U4
BICS-014: DESIGN AND ANALYSIS OF ALGORITHM
Time: 3 hours Maximum Marks: 70
Note: Attempt any seven questions. All questions carry equal marks.
1. Determine the time-complexity of the pseudocode given below, using Big-O notation:
int psum (int
{int partial_sum;
partial_sum
for i i
{partial_sum =partial_sum i
}return partial_sum;
}
State Master's theorem. The recursive equation of time-complexity of an algorithm is given by x T n^2. Find the asymptotic bounds of using Master's theorem. 5
2. Write the algorithm for Quick Sort. Apply it to sort the following data:
25 10 30 15 20 28
Analyse the performance of Quick Sort. 3 4 3
3. What is Aggregate Analysis? A sequence of n operations is performed on a data structure and the ith operation costs if i is an exact power of 2 and 1 otherwise. Apply Aggregate Analysis to determine the amortized cost per operation. 5
Write Strassen's algorithm. Apply it to multiply the following matrices: 2 3
5 6 and 6
3 5 9
4. Write Kruskal's algorithm. Apply the algorithm to the following graph and find the minimum spanning tree: 2 8 <img src='./qimages/8717-4.jpg'>
5. Two algorithms, A1 and A2, run on the same machine. The running time of Al is 100 n^2 and the running time of A2 is 2^n. Find the value of for which Al runs faster than A2. Based on the value of n comment on the performance of Al and A2. 5
What is fractional knapsack problem Consider 5 items along with their respective weights and values given below:
I I1, I2, I3, I4, I5>
w= 10, 20, 30, 40 30, 20, 100, 90, 160
The capacity of knapsack W 60. Find the solution to the fractional knapsack problem. 5
6. Discuss the Travelling Salesman Problem. Use it to compute the minimum travel cost, for the tour plan of the sales agent, shown below: 4 6 <img src='./qimages/8717-6.jpg'>
7. Write short notes on any two of the following: 2x5=10 Knuth-Morris-Pratt Algorithm CYK Algorithm Monte Carlo Algorithm
8. Briefly discuss the following complexity classes with suitable examples: 5x2=10 P NP co-NP NP-Hard NP-Complete
9. Explain the term Matroids, with suitable example. 5
Explain Huffman coding, with suitable example. 5
10. Write the iterative and recursive algorithms to find the sum of n integers. Compare the complexity of the algorithms. 3 3 4
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