We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>
+ Link For Assignments, GDBs & Online Quizzes Solution |
+ Link For Past Papers, Solved MCQs, Short Notes & More |
Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion
How to Add New Discussion in Study Group ? Step By Step Guide Click Here.
Tags:
+ How to Follow the New Added Discussions at Your Mail Address?
+ How to Join Subject Study Groups & Get Helping Material? + How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators? + VU Students Reserves The Right to Delete Your Profile, If?.
+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)
+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)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
&
.•°How to Download past papers from study groups°•.
Please Click on the below link to see…
solved
Can't find any download link, could you plz share the link ? Thanks.
plz anyone share his or her paper
solved
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
© 2020 Created by + M.Tariq Malik. Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
VU Students reserves the right to delete profile, which does not show any Activity at site nor has not activity more than 01 month.
We are user-generated contents site. All product, videos, pictures & others contents on vustudents.ning.com don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com or Contact us at contact Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List | Moderators Group
All Members | Featured Members | Top Reputation Members | Angels Members | Intellectual Members | Criteria for Selection
Become a Team Member | Safety Guidelines for New | Site FAQ & Rules | Safety Matters | Online Safety | Rules For Blog Post