CS502 Solved Final Term Subjective Paper

CS502 - Fundamentals of Algorithms Solved Final Term Subjective Paper 

Solved by Umair Saulat 

 

Attachments:

CS502-FINALTERM-SUBJECTIVE-SOLVED

[ ]

447 Kb

CS502 Final term Subjective Paper - 2

CS502 Subjective Final Term Questions Jan-2012

1) Give Detail Example of 2-d mazama Problem

Apply prime Algorithm on Following Graph (A graph Given in paper)

Where Clipe Problem Arise

What is Deamion Problem and give Examples

explain  with Flody Algorithm  ( Running time and Space used )

CS502 Final term Subjective Paper - 1

Subjective Questions were as follows...

• Fibonacci sequence 2mark
• Clique cover problem 2mark
• Make Adjacency list from the given table 3marks
• Communication design problem (MST).
• Strong connected component problem
• Heapify proof..... 5marks
• Dijkstra Algorithmn 
• Define Floyd Marshall 5marks
• Floyd Marshall 3marks
• runtime 
• space used
• DFS algoritmn 3marks

CS502 Final term Solved paper 2010

                                             FINALTERM  EXAMINATION
                                                            Spring 2010
                         CS502- Fundamentals of Algorithms (Session - 4)


Time: 90 min
M a r k s: 58
CS502 Question No: 1       
 An optimization problem is one in which you want to find,
       Not a solution
       An algorithm
       Good solution
       The best solution
   
CS502 Question No: 2       
 Although it requires more complicated data structures, Prim's algorithm for a minimum spanning tree is better than Kruskal's when the graph has a large number of vertices.
       True
       False
   
CS502 Question No: 3       
 If a problem is in NP, it must also be in P.
       True
       False
       unknown
   
CS502 Question No: 4       
 What is generally true of Adjacency List and Adjacency Matrix representations of graphs
       Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)
       Lists require less space than matrices and they are faster to find the weight of an edge (v1,v2)
       Lists require more space than matrices and they take longer to find the weight of an edge (v1,v2)
       Lists require more space than matrices but are faster to find the weight of an edge (v1,v2)
 
CS502 Question No: 5       

 If a graph has v vertices and e edges then to obtain a spanning tree we have to delete
       v edges.
       v – e + 5 edges
        v + e edges.
       None of these
   
CS502 Question No: 6       
 Maximum number of vertices in a Directed Graph may be |V²|
       True
       False
   
CS502 Question No: 7       
 The Huffman algorithm finds a (n) _____________ solution.
       Optimal
       Non-optimal
       Exponential
       Polynomial
   
CS502 Question No: 8       
 The Huffman algorithm finds an exponential solution
       True
       False
   
CS502 Question No: 9       
 The Huffman algorithm finds a polynomial solution
       True
       False

CS502 Question No: 10       
 The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.
       True
       False
   
CS502 Question No: 11       
 The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.
       True
       False
   
CS502 Question No: 12       
 Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string.
       True
       False
   
CS502 Question No: 13       
 Shortest path problems can be solved efficiently by modeling the road map as a graph.
       True
       False
   
CS502 Question No: 14       
 Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.
       True
       False
   
CS502 Question No: 15       
 Bellman-Ford allows negative weights edges and negative cost cycles.
       True
       False
   
CS502 Question No: 16       
 The term “coloring” came form the original application which was in architectural design.
       True
       False
   
CS502 Question No: 17       
 In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.
       True
       False
   
CS502 Question No: 18       
 Dijkstra’s algorithm is operates by maintaining a subset of vertices
       True
       False
   
CS502 Question No: 19       
 The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key.
       True
       False
   
CS502 Question No: 20       
 Consider the following adjacency list:
 
                
Which of the following graph(s) describe(s) the above adjacency list
      





CS502 Question No: 21       
 We do sorting to,
       keep elements in random positions
       keep the algorithm run in linear order
       keep the algorithm run in (log n) order
       keep elements in increasing or decreasing order
   
CS502 Question No: 22       
 After partitioning array in Quick sort, pivot is placed in a position such that
       Values smaller than pivot are on left and larger than pivot are on right
       Values larger than pivot are on left and smaller than pivot are on right
       Pivot is the first element of array
       Pivot is the last element of array
   
CS502 Question No: 23       
 Merge sort is stable sort, but not an in-place algorithm
       True
       False
   
CS502 Question No: 24       
 In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array.
       Delete
       copy
       Mark
       arrange
   
CS502 Question No: 25       
 Dynamic programming algorithms need to store the results of intermediate sub-problems.
       True
       False

CS502 Question No: 26       
 A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r matrix C. There are (p . r) total entries in C and each takes _________ to compute.
       O (q)
       O (1)
       O (n²)
       O (n³)
   
CS502 Question No: 27    ( M a r k s: 2 )
 Give a detailed example for 2-d maxima problem.
   
CS502 Question No: 28    ( M a r k s: 2 )
 Differentiate between back edge and forward edge.
   
CS502 Question No: 29    ( M a r k s: 2 )
 How the generic greedy algorithm operates in minimum spanning tree
   
CS502 Question No: 30    ( M a r k s: 2 )
 What are two cases for computing  assuming we already have the previous matrix  using Floyed-Warshall algorithm
   
CS502 Question No: 31    ( M a r k s: 3 )
 Describe Minimum Spanning Trees Problem with examples.
   
CS502 Question No: 32    ( M a r k s: 3 )
 What is decision problem, also explain with example
   
CS502 Question No: 33    ( M a r k s: 3 )  Prove that the generic TRAVERSE (S) marks every vertex in any connected graph exactly once and the set of edges (v, parent (v)) with parent (v) ¹ F form a spanning tree of the graph.
   
CS502 Question No: 34    ( M a r k s: 5 )
 Suppose you could reduce an NP-complete problem to a polynomial time problem in polynomial time. What would be the consequence
   
CS502 Question No: 35    ( M a r k s: 5 )
 Prove the following lemma,
Lemma: Given 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]
   
CS502 Question No: 36    ( M a r k s: 5 )
 What is the cost of the following graph

CS502 GDB Idea Solution Spring July 2012

CS502 GDB Idea Solution Spring July 2012

Dynamic Programming is always preferable over greedy approach ” Support or contradict this statement with solid arguments.
Solution No.1
Dynamic programming is both a mathematical optimization method and a computer programming method. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub problems in a recursive manner. [ While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively; Bellman called this the "Principle of Optimality". Likewise, in computer science, a problem that can be broken down recursively is said to have optimal substructure. If sub problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub problems.[5] In the optimization literature this relationship is called the Bellman equation.
Solution No.2
Yes, it is true. Although these both approaches are used to solve problems optimally, but in the same time there are some reasons which make Dynamic programming preferable over greedy approach e.g. dynamic programming solves problems by breaking down in smaller sub problems and also stores results in some form for future reference, which definitely comes always in a solution and also in optimal one. while greedy approach always progress in best possible solution at present without thinking about future hence it can some time mislead us in such that it cannot provide any solution to the problem. For your reference there is also an example given below which will help to understand the greedy approach disadvantage.
So we can conclude that how simple greedy approach mislead us and thus we cannot get our required solution. Now it totally clears that using greedy approach if we start from node 7 at that point the best possible of both is 12 hence it will go towards 12 and then finally towards 6. While if we look other side of tree the best possible we can obtain is 99. So we can conclude that how simple greedy approach mislead us and thus we cannot get our required solution.
Solution No.3
A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the subproblems do not have to be known at each stage; instead a “greedy” choice can be made of what looks best for the moment.
Consider this example.
You are standing at a place A. You are to goto B. There are intermediate places C1,C2 …
You want to minimize distance travelled.
Greedy Method of Solving
You don’t want to try all intermediate places. You go to the nearest intermediate place. Why? You feel by going to the nearest intermediate place, you will minimize the distance to B.
Dynamic Programming
You try all the places, but you store the previous result. Eg: To reach C3 in minimum distance, you reached by C1. So you store C1. So if you want to go to C5, by C3, you will go to C1 then C3 and then check if going from C3 to C5 is nearest.
Solution No.4
Dynamic Programming is always preferable over greedy approach because reasons which make Dynamic programming preferable over greedy approach e.g. dynamic programming solves problems by breaking down in smaller sub problems and also stores results in some form for future reference, which definitely comes always in a solution and also in optimal one. while greedy approach always progress in best possible solution at present without thinking about future hence it can some time mislead us in such that it cannot provide any solution to the problem.

CS502 Assignment No 5 Solution Spring 2012

 CS502 Assignment No 5 Solution Spring 2012

Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Kruskal’s algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?

Solution:
We know that Kruskal’s algorithm takes O(V ) time for initialization, O(E lgE) time to sort
the edges, and O(E(V )) time for the disjoint-set operations, for a total running time of O(V +
E lgE + E(V )) = O(E lgE).
If we knew that all of the edge weights in the graph were integers in the range from 1 to |V |,
then we could sort the edges in O(V + E) time using counting sort. Since the graph is connected,
V = O(E), and so the sorting time is reduced to O(E). This would yield a total running time of
O(V + E + E(V )) = O(E(V )), again since V = O(E), and since E = O(E(V )). The time
to process the edges, not the time to sort them, is now the dominant term. Knowledge about the
weights won’t help speed up any other part of the algorithm, since nothing besides the sort uses
the weight values.
If the edge weights were integers in the range from 1 to W for some constant W, then we could again
use counting sort to sort the edges more quickly. This time, sorting would take O(E +W) = O(E)
time, since W is a constant. As in the first part, we get a total running time of O(E(V )).

CS502 Assignment # 4 Solution June 2012

 CS502 Assignment # 4 Solution

Question:

Give an example of a directed graph G = (V, E), a source vertex s V, and a set of tree edges Eπ ⊆ E such that for each vertex v V, the unique path in the graph (V, Eπ) from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.

Solution:

Let V={s,1,2,3,4}
E={( s,1) ( s,2) ( 1,3) ( 1,4) ( 2,3) ( 2,4)}
Last, let

= {( s,1) ( s,2) (1,4) ( 2,3)}

If vertex 1 precedes vertex 2 on the queue for BFS, then any search will produce tree edges ( 1,3) and ( 1,4); otherwise, the tree will have edges ( 2,3) and ( 2,4).
22.2-6. There are no professional wrestlers, and r pairs of wrestlers for which there are rivalries. Find an O(n+r)-time algorithm to see if the wrestlers can be divided into ‘ good guys’ , such as rivalry is between a good and bad guy.
This question is equivalent to the following:
Given a graph on an vertices with r edges, determine whether the vertices can be divided into two parts, G,B such that no edges connects two vertices in G or two vertices in B.
It is easy to see that if such a division on possible, then there cannot be any odd length cycle; conversely, if there is no odd length cycle, a BSF can be used to construct the subdivision, start a BSF with any vertex s; call it ‘good’; put all adjacent vertices on the queue, and call them ‘ bad’; whenever a good (resp. bad) vertex is at the head of the queue, label any new adjacent vertex in the opposite way and put it on the queue. If there is no odd length cycle, there will be no ambiguity as to the designation. Since BFS takes O(n+r) steps, we are done.