# Cs502 Final Term Papers

My Current paper ...:)ye aye thy mjy shukria...

Mcqs kuch moaz masy thy bki huffman ka topic aur reuction wla topic last ma ha jisma N=NP or co NP wly masy mcqs zeyda aye thy..shukria

Back edge ,forward edge and cross edge

Forward edge: (u, v) where v is a proper descendent of u in the tree.

Back edge: (u, v) where v is an ancestor of u in the tree.

Cross edge: (u, v) where u and v are not ancestor or descendent of one another.

Free tree

A free tree is a tree with no vertex designated as the root vertex.

Define according to Kruskal's algorithm creat_set(u) find_set(U) union(u,v) Answer: Page 147

Create-set(u): Create a set containing a single item u.

Find-set(u):Find the set that contains u

Union(u,v): merge the set containing u and set containing v into a common set.

. Where Arise Clique Cover? (pg176)

Answer:

The clique cover problem arises in applications of clustering. We put an edge between two nodes

if they are similar enough to be clustered in the same group. We want to know whether it is

possible to cluster all the vertices into k groups.

LONG QUESTION

suppose you could prove that an NP-complete problem can be solved in polynomial time. What would be the consequence? 5 marks

If we can solve a problem in polynomial time, we can certainly verify the solution in polynomial time.

More formally, we do not need to see a certificate to solve the problem; we can solve it in polynomial time anyway.

However, it is not known whether P = NP. It seems unreasonable to think that this should be so. Being able to verify that you have a correct solution does not help you in finding the actual solution. The belief is that

P 6= NP but no one has a proof for this.

Aik sawal tha osma Depth first search ky through loops or cycle find krna tha tabular form ma tha ? 5 marks

Topological form ka sawal tha aik? 5 marks

Aik sawal tha NP wla last ma ha reuction waly masy? 5 marks

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

## 0 comments