University of Sargodha MS 1" Term Examination 2014 Subject: Computer Science Paper: Advanced Algorithm Analysis (CS-5143) Time Allowed: 3 Hours
Discussion
Ask a question about this paper, or help someone else with theirs. Answers are emailed to whoever asked.
No questions yet — be the first to ask.
More Advance Analysis of Algorithms papers
See all
University of Sargodha MS 1" Term Examination 2015 Subject: Computer Science Paper: Advanced Analysis of Algorithms (CS-5143) Maximum Marks: 80
Uploaded 3 years ago
Download ↓
Time Allowed: 2:30 hrs University of Sargodha M.Sc(IT), 4th Final Term Exam, 2015 Paper: Analysis of Algorithm (CS-610)
Uploaded 3 years ago
Download ↓
Paper: University of Sargodha M. Sc. I. T, 4" Term Exam 2015. Analysis of Algorithms (CS: 610)
Uploaded 3 years ago
Download ↓
Paper text
University of Sargodha
MS 1" Term Examination 2014
Subject: Computer Science Paper: Advanced Algorithm Analysis (CS-5143)
Time Allowed: 3 Hours
Session: 2014-16 Spring
Note:
Maximum Marks: 80
Q.1.
Q.2.
0.3
Objective part is compulsory. Attempt any four questions from subjective part.
ni
Objective Part
Winte short answers of the following on your answer sheet.
f. Show a bipartite graph with the help of elexample.
1. What is asymptotic complexity
• What are multi threaded algorithms
vii. What are maximum flow networks?
(2*8)
IV. Deline Algorithms. .
Subjective Part
Both parts of this question is relevant to dynamic programming.
[16]
a. Show optimal subsequence of matrices for Matrix Multiplication. Suppose A is 10x30 matrix, B
is 30x5 matrix, and C is 5x60 matrix
b. Find longest common subsequence. Let X- XMJYAUZ and Y=MZJAWXU
Both parts of this question are relevant to Greedy Algorithm.
[16]
a. Show Huffman coding for a data string that has following character frequency.
Character
A
Frequency
24
12
10
D
8
b. What is the number of coins required to create a sum of 21 Rs. The available coins are of Rs 1,
Rs 2, Rs. 7, Rs,
8.
Q.4.yf find shortest path from the following graph using Bellman-Ford and Dijkstra's algorithms. Let s
be the source node.
[16]
ustadni.com
b (ing
ani,.com
4
5
wustadni.com
Q.5y Apply any two amortized analysis technique on a Stack that has Push, Pop, and Multipop
Q.6.
Vrite note on the following.
[16]
[6+5+51
a. Vertex Cover Problem
b. Travelling Salesman person Problem
c. Set Covering Problem
Explain Naive String Matching and Rabin Karp String Matching with the help of an example.
Clearly describe all steps.
visit website: ustadni.com