We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>


Looking For Something at vustudents.ning.com? Click Here to Search

CS502 ALL Current Final Term Papers Fall 2016 & Past Final Term Papers at One Place from 25 February 2017 to 08 March 2017

CS502 ALL Current Final Term Papers Fall 2016 & Past Final Term Papers at One Place from 25 February 2017 to 08 March 2017

+ Click Here To Join also Our facebook study Group.

..How to Join Subject Study Groups & Get Helping Material?..


See Your Saved Posts Timeline

Views: 3790

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

Replies to This Discussion

Share Your Current Final Term Papers (Questions/Pattern) & Past Papers as well here to help each other. Thanks

 

Note:-

For Important Helping Material related to this subject (Solved MCQs, Short Notes, Solved past Papers, E-Books, FAQ,Short Questions Answers & more). You must view all the featured Discussion in this subject group.

For how you can view all the Featured discussions click on the Back to Subject Name Discussions link below the title of this Discussion & then under featured Discussion corner click on the view all link.

Or visit this link 

Click Here For Detail.

&

.•°How to Download past papers from study groups°•.

 

Please Click on the below link to see…

.... How to Find Your Subject Study Group & Join .... 

solved

Can't find any download link, could you plz share the link ? Thanks.

plz anyone share his or her paper

solved

Attachments:

M.Zeeshan  thanks for sharing 

Attention Students: You don’t need to go any other site for current papers pattern & questions. Because all sharing data related to current Final term papers of our members are going from here to other sites. You can judge this at other sites yourself. So don’t waste your precious time with different links. Just keep visiting http://vustudents.ning.com/ for all latest updates.

Today is my paper of cs502
Mcqs was coceptual
i remember some questions 
Q1Given a digraph G = (V, E), consider any DFS forest of G and consider any edge (u, v) ∈ E.
If this edge is a tree, forward or cross edge, then f[u] > f[v]. If this edge is a back edge, then f[u] ≤ f[v 5marks
Q2:Define back edge and forward edge 2marks
Q3:Define reductions? Give Example. (5)
Q4:Define forward edge . 3marks
Q5:Explain directed and undirected graph? 3marks
Q6:What is the Floyd-Warshall Algorithm Running time and Space time? 2marks
Q7:1 MST ka graph tha us ki cost batani thi......5 marks
Q8:.How Dijkstra algorithm operates? aur running time b batna tha.....3marks
Q9:Define according to Kruskal's algorithm
creat_set(u)
find_set(U)
union(u,v) 3marks


M.Zeeshan BSSE
Recent paper (2013,14,15,16) Final Term
Remember me in your prayer’s mzesh5552@gmail.com


Q # 1 How Gready algorithem works?
Ans You take the best you can get right now, without regard for future consequences.
You hope that by choosing a local optimum at each step, you will end up at a global optimum.
Q# 2 Wright brief intro about dynamic programming
Ans Dynamic programming is essentially recursion without repetition. Developing a dynamic programming algorithm generally involves two separate steps:
• Formulate problem recursively. Write down a formula for the whole problem as a simple
combination of answers to smaller subproblems.
• Build solution to recurrence from bottom up. Write an algorithm that starts with base cases and
works its way up to the final solution.

Q# 4 What is BFS and how it works?
Ans (BFS) Start with s and visit its adjacent nodes. Label them with distance 1. Now consider the neighbors of neighbors of s. These would be at distance 2. Now consider the neighbors of neighbors of neighbors of s. These would be at distance 3. Repeat this until no more unvisited neighbors left to visit.

Q# 5 Diffrance between DFS and BFS.
Ans

BFS Stands for “Breadth First Search”. DFS stands for “Depth First Search”.
 BFS starts traversal from the root node and then explore the search in the level by level manner i.e. as close as possible from the root node. DFS starts the traversal from the root node and explore the search as far as possible from the root node i.e. depth wise.
BFS is slower than DFS. DFS is more faster than BFS.
BFS requires more memory compare to DFS. DFS require less memory compare to BFS.
BFS is useful in finding shortest path DFS in not so useful in finding shortest path

Q#6 Prim’s algorithm
Ans In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Q # 7 Write the paseudo code of prim’s algorithem
Ans (not sure)

Q#8 Define topological Sort. (2 marks)

Ans A topological sort of a DAG is a linear ordering of the vertices of the DAG such that for each edge (u, v),u appears before v in the ordering.

Q#9 What is overall time of Kruskal's Algorithm if graph is sparse. (2 marks)
Ans Overall time for Kruskal is Θ(E log E) = Θ(E log V) if the graph is sparse.
Q#10 If we implement the bag data structure by using a stack, then which type of traversal it will be? (2 marks)
Ans If we implement the bag by using a stack, we have depth-first search (DFS) or traversal.
Q#11 Given a diagraph G=(V,E), consider any DFS forest og G and consider any edge (u,v) in E. Prove that if this edge is a tree, forward or cross edge, then f [u] > f [v] and if this edge is a back edge, then f [u] <= f [v]. (3 marks)
Ans For the non-tree forward and back edges the proof follows directly from the parenthesis lemma.

Q#12 According to Dijkstra's Algorithm, write the pseudo code to relax a vertex. (5 marks)

Q#13 Graph was given, by applying Kruskal's algorithm, make the MST. (5 marks)
Ans pg(149)
Q#14 by applying DFS, find the strong components the graph (graph was given) 5 marks
Ans pg(136)
Q#15 Prove that, for each minimum spanning tree T of G, there is a way to sort the edges of G in Kruskal’s algorithm so that the algorithm returns T.

Ans Sort the edges in non-decreasing order. Break ties between the edges with the same cost by having edges in T precede edges not in T. It means that if w (e) = w (e’) and e Є T, e’ Є T, then e will appear before e’ in the sorted order. If the edges are sorted this way, Kruskal‘s algorithm will return T.

Q#16 Write pseudo code for strong component in digraph.
Ans


Q#17 Show that the greedy algorithm gives an optimal solution to the activity scheduling problem? 3 marks
Ans
Let S = {a1, a2, . . . , an} of n activities, sorted by increasing finish times, that are to be scheduled to use
some resource. Then there is an optimal schedule in which activity a1 is scheduled first.
Proof:
Let A be an optimal schedule. Let x be the activity in A with the smallest finish time. If x = a1 then we
are done. Otherwise, we form a new schedule A0 by replacing x with activity a1.


Q#18 What is the greedy thing to do in Dijkstra’s algorithm?

AnsThe greedy thing to do is to take the vertex for which d[u] is minimum, i.e., take the unprocessed vertex that is closest by our estimate to s. Later, we justify why this is the proper choice.

Q#19 How the generic greedy algorithm operates in minimum spanning tree?

Ans A generic greedy algorithm operates by repeatedly adding any safe edge to the current spanning tree.

Q#20 When was floyd-warshel algorithm was introoduced? 2 marks

Ans The algorithm dates back to the early 60’s

Q#21 prove that.. froward edge is when f[u] > f[v]  and back edge is when f[u] <f[v] 3 marks

Ans For the non-tree forward and back edges the proof follows directly from the parenthesis lemma.

Q#22 What are out-degree and in-degree of a vertex in graphs? (2 marks)
Ans In a digraph, the number of edges coming out of a vertex is called the out-degree of that vertex. Number of edges coming in is the in-degree.
Q#23 What is Bellman-Ford running time? (2 marks)
Ans the running time of Bellman ford is Θ(VE) .
Q#14 Give a pseudo code for counting money problem. Take largest note or coin first?(3 marks)

Q#24 Describe three variants of shortest path problem?(3 marks)
Ans There are a few variants of the shortest path problem
Single-source shortest-path problem
Single-destination shortest-paths problem
Single-pair shortest-path problem
All-pairs shortest-paths problem
Q#25 Why we need reduction? Give an example?(5 marks)
The class NP-complete (NPC) problems consists of a set of decision problems (a subset of class NP) that
no one knows how to solve efficiently. But if there were a polynomial solution for even a single
NP-complete problem, then ever problem in NPC will be solvable in polynomial time. For this, we need
the concept of reductions.

Q#26 write a pasedo code of timestamp DFS 5 mark

Q#27 what is polynomial problem. when problem solve in polinomial algorithm
Ans A polynomial time algorithm is any algorithm that runs in O(nk) time.

A problem is solvable in polynomial time if there is a polynomial time algorithm for it.

Q#28 What is polynomial time Algorithms? Give Example  (3)
Ans A polynomial time algorithm is any algorithm that runs in O(nk) time. i.e
suppose you have an algorithm that takes as input a graph of size n and an integer k and run in O(nk) time
Q#29 What Is Activity scheduling?? Give example  (3)
Ans The activity scheduling is a simple scheduling problem for which the greedy algorithm approach provides an optimal solution.
i.e An example is that a number of lectures are to be given in a single lecture hall. The start and end times
have be set up in advance. The lectures are to be scheduled. There is only one resource (e.g., lecture hall)
Some start and finish times may overlap. Therefore, not all requests can be honored.

Q#30 :Consider a digraph G = (V, E) and any DFS forest for G. Prove that G has a cycle if and only if the DFS forest has a back edge.
Ans If there is a back edge (u, v) then v is an ancestor of u and by following tree edge from v to u,
we get a cycle.
Q#31 Is there any relationship between number of back edges and number of cycles in DFS? (2 MARKS)
ANS: There is no relationship between no. of edges and cycles (Page 131)

Q#32 How do we compute assuming we already have the previous matrix? (2 MARKS)
ANS: 1. don’t go through vertex k at all.
2 .Do go through vertex k (Page 162)

Q#33 Consider the case of 3 matrices: A1 is 5 × 4, A2 is 4 × 6 and A3 is 6 × 2 The multiplication can be carried out as ((A1A2)A3) The cost of is? (2 MARKS)

ANS: ((A1A2)A3) = (5 · 4 · 6) + (5 · 6 · 2)= 180 (Page 84)

)

Q#34 .. Variants of shortest path solution briefly? (3 MARKS)

ANS: There are a few variants of the shortest path problem.
Single-source shortest-path problem: Find shortest paths from a given (single) source vertex s 2 V to every other vertex v 2 V in the graph G.

Single-destination shortest-paths problem: Find a shortest path to a given destination vertex t from each vertex v. We can reduce the this problem to a single-source problem by reversing the direction of each edge in the graph.
Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. No algorithms for this problem are known to run asymptotically faster than the best single-source algorithms in the worst case.
All-pairs shortest-paths problem: Find a shortest path from u to v for every pair of vertices u and v. Although this problem can be solved by running a single-source algorithm once from each vertex, it can usually be solved faster.

Q#35 What are Calatan Numbers and their formula?
Ans

Q#36 what are the application of edit distance technique . Three names? (3)
Ans Spelling Correction
Plagiarism Detection
Computational Molecular Biology
Speech Recognition
Q#37 What is fractional knapsack problem?(3)

Ans  the continuous knapsack problem (also known as the fractional knapsack problem) is an algorithmic problem in combinatorial optimization in which the goal is to fill a container (the "knapsack") with fractional amounts of different materials chosen to maximize the value of the selected materials

Q#38: What is the decision problem L1 in polynomial time reduction to decision in problem L2? (2Marks)
Ans We say that a decision problem L1 is polynomial-time reducible to decision problem L2
(written L1 ≤p L2) if there is polynomial time computable function f such that for all x, x ∈ L1 if and
only if f(x) ∈ L2

bro thanks for sharing and mcqs kaan sy aye thy waqr siddhu ki files sykuch aye thy kia

is someone tell me the answer of this question plz

4. Huffman encoding of a massage is encoded to 43bit and you have to explain why it is 43bit. Massage contain 7c, 6Ts, 5Gs, and 3a. (5 Marks)

my today's paper 

paper was easy 60% MCQS from past papers

What is the running and waiting time of Floyd-War shall Algorithm? page 164

What Is Activity scheduling?? Give example (3) 105

What is relationship between mutual reachable, equivalence relation, and component digraph? 

what is the bit of aabaadcc(is trha ki koe statement thi) binary ASCII code of hauffman

encoding

huffman encoding tree bana tha

Execute first three iteration of matrix using floyd warshall algorithm

kurskal algorithm ka aik question tha graph diya hova tha usy py kurskal algorithm use karna tha

strong component use karna tha graph py graph diya hova tha

3 Variants of shortest path problem? (3 MARKS)

itna hi yaad tha 

best of luck

kindly ap bta skty hn kn si file se aaye mcqs aur wo file b upload kr dain 

shukariya

RSS

Latest Activity

+ M.Tariq Malik liked Dɪʟ E Nᴀᴅᴀᴀɴ's discussion ENG101 Quiz No.4 Solution Spring 2019
4 minutes ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion CS311 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group CS311 Introduction to Web Services Development
10 minutes ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion CS311 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group CS311 Introduction to Web Services Development
10 minutes ago
+ M.Tariq Malik's 13 discussions were featured
12 minutes ago
+ M.Tariq Malik added a discussion to the group CS311 Introduction to Web Services Development
14 minutes ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion CS310 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group CS310 Open Source Web Application Development (PHP, PERL, CGI, Mysql)
18 minutes ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion CS310 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material in the group CS310 Open Source Web Application Development (PHP, PERL, CGI, Mysql)
18 minutes ago
+ M.Tariq Malik liked + M.Tariq Malik's discussion CS310 Final Term Papers Spring 2019 (24 August ~ 04 September 2019) & All Solved Past Papers, Solved MCQs & Helping Material
18 minutes ago

Today Top Members 

© 2019   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service