Analysis of Algorithm BSCS 4th Mid Term Past Paper 2016 UOS
Read and Download Analysis of Algorithm BSCS 4th Mid Term Past Paper 2016 UOS
Time Allowed & Exam Format
This Mid Term Examination 2016 for Design and Analysis of Algorithms (BSCS 4th) was conducted by IT HUB College, University of Sargodha. The paper focuses on core algorithm design techniques, including greedy methods, dynamic programming, and matrix operations.
Time Allowed: 120 Minutes
Total Marks: 60
Short Questions (SQs)
These questions test the understanding of core algorithmic techniques and complexity analysis. Perfect for quick revision before exams.
- Write the recursive solution of the 0/1 knapsack problem
- List ingredients of dynamic programming
- Calculate worst-case time complexity of insertion sort
- Code to print optimal knapsack solution
For better understanding, explore this guide on DP-based knapsack:
GeeksforGeeks – 0/1 Knapsack Problem Explained
Long Questions (LQs)
These questions require algorithm design, coding, and optimization—frequently asked in university-level algorithm exams.
- Fuel Optimization / Subset Sum Problem (Q1)
- Real-world greedy strategy to minimize gas stops.
- OR write an algorithm to determine if two elements in a set sum to x.
- Matrix Chain Multiplication (Q3)
- Write code for optimal parenthesis based on provided S matrix.
- Most Frequent Element (Q4)
- Write an efficient algorithm to find the most repeated item in an array.
- Assembly Line Scheduling (Q5)
- Calculate F and L matrices for the provided line-scheduling diagram.
Want to learn how optimal parenthesis and matrix chain problems are solved in dynamic programming?