Design and Analysis Algorithm Past Paper BSCS Mid Term 2016 UOS
Read and Download Design and Analysis Algorithm Past Paper BSCS Mid Term 2016 UOS
This is the official Mid Term Examination Paper of Design and Analysis of Algorithms for BSCS students of the University of Sargodha (IT HUB College), held in 2016. The paper includes real-world problem-solving, algorithm writing, and complexity analysis to test students’ practical understanding of algorithms.
Time Allowed
120 minutes (2 Hours)
Total Marks: 60
Detailed Question Breakdown
Q.1 (Choice Based – Real World Algorithm)
Write an algorithm to solve a shortest path problem like:
- Write an algorithm that selects the smallest number of elements from a set whose sum is ≥ a given integer.
Q.2 (Theory & Writing)
Includes:
- Characteristics of Dynamic Programming
- Applications of Dynamic Programming
- Matrix Chain Multiplication steps
- Example application in C++
Q.3 (Code Writing Problem)
Write code for optimal parenthesization using matrix chain multiplication. Matrix dimensions are provided in a table.
Useful for mastering optimal substructure and multiplication cost minimization.
Q.4 (Frequency-Based Algorithm Writing)
Write an algorithm that finds the most frequent element in an array.
A classic problem often used in interviews and exams.
Q.5 (State Transition Diagram Problem)
Given a diagram of car chassis entering and exiting multiple assembly lines, students are asked to:
- Calculate total time
- Determine minimum path time
- Apply dynamic programming to find optimized transitions
To learn step-by-step how matrix chain multiplication works using dynamic programming, check this guide:
GeeksforGeeks – Matrix Chain Multiplication
Study Tip:
Start by practicing the matrix-based and real-world application problems. These questions often repeat with slight changes. Focus on understanding time complexity, recursion, and dynamic programming logic clearly.