University of Sargodha MS 1" Term Examination 2015 Subject: Computer Science Paper: Advanced Analysis of Algorithms (CS-5143) Maximum Marks: 80
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 2014 Subject: Computer Science Paper: Advanced Algorithm Analysis (CS-5143) Time Allowed: 3 Hours
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 2015
Subject: Computer Science Paper: Advanced Analysis of Algorithms (CS-5143)
Maximum Marks: 80
Time Allowed: 3 Hours
Objective Part (Compulsory)
..No. 1. Write short answers for the following questions. (8x2-16)
1) Define asymptotic analysis.
2) Define Big-Oh notation.
3) What is fast algorithm?
(4) What properties does a problem hold for applying dynamic programming approach?
5h What are the steps for designing dynamic programming algorithm?
ustag
What is the main idea of dynamic programning approach?
Define optimal substructure property.
Define longest common subsequence (LCS) problem.
Subjective Part
ustadni.com
(4x16=64)
Note: Attempt any four questions.
Q.No.2. Write Bellman-ford algorithm and elaborate it by performing dry run on the following
graph.
Q.No.3. Prove optimal substructure of shortest path stated as: Given a weighted directed graph
G = (V,
E) with weight function w: E → R, let p = < V1.... Uk > be a shortest path between
vertex v, and Uk and for any i,j such that 1 ≤ i ≤ / ≤ k, let pi = (V,,...,v, be subpath of p
from vertex v, to vertex v. Then ply is the shortest path from v, to v;.
CQ.No.4. Prove correctness of cut property.
ladni coterm countner on the own are show you prese by stop.
Q.No.5. Perform counting sort on the following array. Show your procedure step by step.
stadni.co
Q.No. 6. Design a Huffman coding scheme ta encode a text file containing alphabets (A, B, C, D,
E, F,
G) with the following frequencies.
Alphabets
A
ustadni.com
G
Frequencies
10
20
30
40
50
60
70
visit website: ustadni.com