CS502 Current Final Term Fall 2013 Shared by Uzma_Kanwal File 9

Uzma Kanwal CS502 paper 6-03-14 Thursday 8:00 –10:00

40 MCQS

Mcqs 8 almost last chap may say thay 5 to chap he k thay or baki yey pocha tha k np hay to np complete hay ya nai ,p hay to NP hay ya nai asay fazaool say thay jin ki smaj he nai ari the

Huffman say b thay stable inplace ka koi b nai tha moaz file say kam he thay handouts k thay zada tar but ez thay zada muskil nai tha
12 question  in subjective

 1-What is an edge   (2 marks)

2- Can an adjacency matrix for a directed graph ever not be square in shape? Why or why not?  (2 marks)

3-what is minimizing spanning tree of 2 and what is greedy approach in it.(2 marks)

4-Np say related koi lambiiiiiiiiii c statmwnts  the 2 or un ko yes no krna tha and xplain b karna tha  (2 marks)

5--what is MST and give ex of  (3 marks)

6-What is fractional knapsack problem?(3)

7-Np  complete say related tha kuch  (3 marks)

8-Describe equivalence relation, mutually reachable vertices and strong components? (3 marks)

9-What is topological sort (5 marks)

10-Dijisiktra Algorithm pscedo code (5 marks)

11-Analyze the following pseudo code for Huffman tree building algorithm. And write the body of second for loop with the proper logic: (5 marks)

HUFMAN (N, symbol[1…N], freq[1…N]
For i = 1 to N
Do t ß Tree Node(symbol[i], freq[i])
pq.insert(t, freq[i])
for i = 1 to N - 1
?
?
?
?
?
return pq.remove

12-Adjacency matrix di v the us ki 3 iterations karni the 5 marks