Design and Analysis of Algorithm, Past Papers

Design and Analysis of Algorithm Past Paper BS 4th Term 2017 UOS

Posted by Ayesha

Read and Download Design and Analysis of Algorithm Past Paper BS 4th Term 2017 UOS

This is the BS 4th Term Past Paper for Design and Analysis of Algorithms (CS-3143) from the University of Sargodha, conducted in 2017. The paper is divided into two parts: Short Questions (SQs) and Long Questions (LQs), testing students’ conceptual and problem-solving skills in core computer science algorithms.

Time Allowed

2 Hours and 30 Minutes
Total Marks: 80

Short Questions (Objective Type)

Students are required to answer a variety of short questions covering definitions, core concepts, and quick logic-based answers. Topics include:

Divide and Conquer
Huffman Encoding
Quick Sort Recurrence
Characteristics of Dynamic Programming
Prefix Codes and Equal Frequency

A particularly interesting section involves a pseudocode titled “Algorithm Enigma” with questions on:

Basic operation
Number of executions
Time complexity
Further improvements

Long Questions (Subjective Type)

Students must attempt 4 out of 6 long questions. Each is worth 12 marks, and topics include:

Merge Sort with efficiency discussion
Huffman Coding with equal frequency edge case
Analysis of pseudocode (Enigma algorithm)
Quick Sort recurrence and efficiency
Pattern matching over finite alphabet Σ = {a, b, c}
Floyd-Warshall Algorithm with step-by-step matrix

For helpful explanations and tutorials on algorithms like Huffman Coding, Quick Sort, or Floyd Warshall, visit:
GeeksforGeeks – Design and Analysis of Algorithms

Try solving each question on your own before referring to solutions. Focus on understanding why and how the algorithm works, not just the code.