Design and Analysis of Algorithm, Past Papers

Design & Analysis of Algorithms Past Paper 2024 – BS 4th Term (UOS)

Posted by
0
Design and analysis of algorithm 2024

University: University of Sargodha (UOS)
Program: BS 4th Term
Subject: Design & Analysis of Algorithms (CSCC-202)
Year: 2024
Time Allowed: 2 Hours 30 Minutes
Maximum Marks: 60

Why Use This Algorithms Past Paper?

This past paper helps students understand exam format, important topics and commonly repeated questions. Practicing past papers improves problem solving speed and confidence.

  • Understand algorithm concepts
  • Practice short definitions
  • Prepare complex algorithm problems
  • Improve exam writing technique

Design & Analysis of Algorithms Past Paper 2024 (Complete)

Note: Objective part is compulsory. Attempt any three questions from subjective part.

Objective Part (Compulsory)

Q.1 Write short answers of the following in 2–3 lines each. (2×12)

  1. What is a loop invariant?
  2. Define average case complexity.
  3. Other than speed, what measures of efficiency are useful?
  4. What is an in-place algorithm?
  5. Give a recurrence describing worst-case binary search.
  6. Is 2n+1 = O(2n)? Explain.
  7. Does the array 20,15,18,7,9,5,12,3,6,2 form a max-heap?
  8. Can heapsort be used as auxiliary sorting in radix sort?
  9. What is a pseudograph?
  10. How many vertices are in Cn graph?
  11. Advantages of adjacency list vs adjacency matrix?
  12. Insertion cost for inserting into max-heap?

Subjective Part (Attempt any Three)

Q.2 Algorithm to locate last occurrence of largest number.

Q.3 Sort array of −1, 0, 1 in O(n).

Q.4 Algorithm to check path existence in directed graph.

Q.5 Detect positive cycle in directed acyclic graph.

Q.6 Single-source longest path in DAG.

Download

Download Algorithms Past Paper 2024 (PDF)

Related Past Papers

More papers coming soon – stay connected!

Short Question Solutions

Click to view answers:

1. What is a loop invariant? A loop invariant is a logical condition that remains true before and after every iteration of a loop. It is used to prove correctness of algorithms.
Reference: CLRS – Introduction to Algorithms
2. Define average case complexity. Average-case complexity measures expected running time of an algorithm over all possible valid inputs of given size.
Reference: GeeksforGeeks – Algorithm Analysis
3. Other measures of efficiency? Memory usage, scalability, stability, reliability, and implementation cost.
4. What is an in-place algorithm? An algorithm that uses only a constant amount of extra memory besides input storage.
5. Recurrence for binary search (worst case) T(n) = T(n/2) + 1
6. Is 2n+1 = O(2n)? Yes. 2n+1 = 2 × 2n = O(2n).
7. Does array form max heap? Yes — it satisfies heap property: every parent ≥ children.
8. Can heapsort be auxiliary for radix sort? No. Radix sort requires stable sorting; heapsort is not stable.
9. What is pseudograph? A graph that may contain self-loops and multiple edges.
10. Vertices in Cn? Cn contains n vertices.
11. Advantages of adjacency list? Uses less memory and is efficient for sparse graphs.
12. Max-heap insertion cost? O(log n)
Newer
Linear Algebra Past Paper 2024 | BS 4th Term UOS (MATH-202)
Back to list
Older Database Systems Past Paper 2024 – University of Sargodha (BS 4th Term)