DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF ENGINEERING & TECHNOLOGY PESHAWAR
COURSE TITLE: ADVANCED ANALYSIS OF ALGORITHMS STUDENT REG #: ___________________
FINAL TERM EXAM – SPRING 2025 MS/PHD (COMPUTER SCIENCE)
TIME ALLOWED: 02 HOURS TOTAL WEIGHTAGE: 50%
ATTEMPT ALL QUESTIONS INSTRUCTOR: DR. IMRAN KHALIL
QUESTION 01. P, NP, NP-COMPLETE, & NP-HARD PROBLEM [10]
A delivery drone management system aims to calculate the most efficient route to visit a series of
drop-off locations exactly once and return to the base station. The company wants an exact and fast
solution through a software system.
Briefly answer the following questions:
a) Identify the class of problem described.
b) Explain whether this problem belongs to P, NP, NP-Complete, or NP-Hard, with justification.
c) Is it feasible to find an optimal solution in polynomial time?
Solution:
d) The problem is the Traveling Salesman Problem (TSP).
e) It belongs to NP-Hard, as there is no known polynomial-time algorithm for an exact solution.
f) Therefore, for large input sizes, finding an optimal solution is not feasible in polynomial time.
QUESTION 02. DYNAMIC PROGRAMMING [10]
You work at a biotech startup developing population models for disease spread. The model requires
calculating the nth term of a sequence defined similarly to the Fibonacci sequence. Your existing
recursive code is inefficient for large n. You're asked to optimize it using dynamic programming.
Briefly answer the following questions:
a) Write the DP-based algorithm.
b) Compare time and space complexity with the recursive version.
Solution:
𝐴𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 𝐷𝑃𝑓𝑖𝑏(𝑛, 𝑚𝑒𝑚𝑜 = {0: 0, 1: 1})
𝑖𝑓 𝑛 𝑖𝑛 𝑚𝑒𝑚𝑜
𝑟𝑒𝑡𝑢𝑟𝑛 𝑚𝑒𝑚𝑜[𝑛]
𝑚𝑒𝑚𝑜[𝑛] = 𝐷𝑃𝑓𝑖𝑏(𝑛 − 1, 𝑚𝑒𝑚𝑜) + 𝑓𝑖𝑏(𝑛 − 2, 𝑚𝑒𝑚𝑜)
𝑟𝑒𝑡𝑟𝑢𝑛 𝑚𝑒𝑚𝑜[𝑛]
Time and Space Complexity Analysis:
o Original Recursive Approach:
▪ Time: 𝑂(2𝑛 ) (exponential).
▪ Space: 𝑂(𝑛) (due to the call stack).
o DP with Memoization:
Page 1 of 4
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF ENGINEERING & TECHNOLOGY PESHAWAR
▪ Time: 𝑂(𝑛) (each Fibonacci number is computed once).
▪ Space: 𝑂(𝑛) (to store the memo table).
QUESTION 03. ALGORITHM DESIGN TECHNIQUE [10]
Analyze the following nested loop algorithm which simulates sensor data readings over a grid. Identify three
basic operations, compute their frequency in the worst case, and determine the overall time complexity.
𝐴𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 𝐹𝑖𝑛𝑎𝑙𝐸𝑥𝑎𝑚(𝑑𝑎𝑡𝑎[ ], 𝑛)
{
𝑓𝑜𝑟 𝑖 𝑖𝑛 𝑟𝑎𝑛𝑔𝑒(𝑛):
𝑓𝑜𝑟 𝑗 𝑖𝑛 𝑟𝑎𝑛𝑔𝑒(𝑛):
𝑓𝑜𝑟 𝑘 𝑖𝑛 𝑟𝑎𝑛𝑔𝑒(𝑛):
𝑠𝑢𝑚 += 𝑠𝑒𝑛𝑠𝑜𝑟_𝑑𝑎𝑡𝑎[𝑖][𝑗][𝑘]
}
Solution:
• Basic operations:
o Initialization (i, j, k),
o Comparison,
o Increment
• Each loop runs 𝑛 times → Total operations ≈ 𝑛 × 𝑛 × 𝑛 = 𝑛³
• Time Complexity: 𝑂(𝑛³)
QUESTION 04. Randomization (Fermat’s Little Theorem) [10]
Design an algorithm to probabilistically test if a number is prime using Fermat’s Little Theorem. Demonstrate
a case where a composite number falsely passes the test and discuss the implications in cryptography.
Example of Failure:
Page 2 of 4
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF ENGINEERING & TECHNOLOGY PESHAWAR
Risk: Such failures can lead to weak cryptographic keys, falsely assumed to be prime.
QUESTION 05. GREEDY APPROACH [10]
Given 𝑒𝑖𝑔ℎ𝑡 activities {𝑎1 , 𝑎2 , … 𝑎8 } with the start and finish times. Select the maximum number of
activities that can be performed by a single person, assuming that a person can work on a single
activity at a time.
Activities 𝐀𝟏 𝐀𝟐 𝐀𝟑 𝐀𝟒 𝐀𝟓 𝐀𝟔 𝐀𝟕 𝐀𝟖
Start 1 0 1 4 2 5 3 4
Finish 3 4 2 6 9 8 5 5
𝑨𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎 𝐴𝑐𝑡𝑖𝑣𝑖𝑡𝑦𝑆𝑒𝑙𝑒𝑐𝑡𝑖𝑜𝑛 𝐺𝑟𝑒𝑒𝑑𝑦(𝐴𝑐𝑡𝑖𝑣𝑖𝑡𝑦𝑆𝑒𝑡 𝐴 )
𝑆𝑜𝑟𝑡 𝐴 𝑏𝑦 𝑓𝑖𝑛𝑖𝑠ℎ 𝑡𝑖𝑚𝑒.
𝑆 = {𝑎1}
𝑗 = 1
𝒇𝒐𝒓 𝑖 = 2 𝑡𝑜 𝑛 𝒅𝒐
𝒊𝒇 𝑠𝑖 ≥ 𝑓𝑗 𝒕𝒉𝒆𝒏
𝑆 = 𝑆 ∪ {𝑎𝑖 }
𝑗 = 𝑖
𝒆𝒏𝒅 𝒊𝒇
𝒆𝒏𝒅 𝒇𝒐𝒓
𝒓𝒆𝒕𝒖𝒓𝒏 𝑆
Briefly answer the following questions:
a) Identify and list the final set of selected activities.
b) Compute the time complexity of the algorithm in worst-case and justify why it is considered a greedy
approach.
Page 3 of 4
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF ENGINEERING & TECHNOLOGY PESHAWAR
Solution:
a) 𝐴3 , 𝐴6 , 𝐴7
b) Time Complexity
• Sorting step: 𝑂(𝑛 𝑙𝑜𝑔 𝑛)
• Selection loop: 𝑂(𝑛)
• Total Time Complexity: 𝑂(𝑛 𝑙𝑜𝑔 𝑛)
Page 4 of 4
