thanks a lot bro...........
On 6/15/12, Umair Saulat <saulat.umair@googlemail.com> wrote:
> *CS502 - Fundamentals of Algorithms*
>
> *Quiz No.3 Dated 15-06-2012*
>
>
>
>
>
> In in-place sorting algorithm is one that uses arrays for storage :
> An additional array
>
> *No additional array** (Right Answer)*
>
> Both of above may be true according to algorithm
>
> More than 3 arrays of one dimension.
>
>
>
> The running time of quick sort depends heavily on the selection of
>
> No of inputs
>
> Arrangement of elements in array
>
> Size o elements
>
> *Pivot element **(Right Answer)*
>
>
>
> In stable sorting algorithm
>
> One array is used
>
> In which duplicating elements are not handled.
>
> More then one arrays are required.
>
> *Duplicating elements remain in same relative position after sorting.
> **(Right
> Answer)*
>
> * *
>
> Which sorting algorithn is faster :
>
> O(n^2)
>
> O(nlogn)
>
> *O(n+k) **(Right Answer)*
>
> O(n^3)
>
>
>
> In Quick sort algorithm,constants hidden in T(n lg n) are
>
> Large
>
> Medium
>
> Not known
>
> *Small **(Right Answer)*
>
> * *
>
> Quick sort is based on divide and conquer paradigm; we divide the problem
> on base of pivot element and:
>
> *There is explicit combine process as well to conquer the solutin. (Right
> Answer)*
>
> No work is needed to combine the sub-arrays, the array is already sorted
>
> Merging the subarrays
>
> None of above.
>
>
>
>
>
>
>
> There is relationship between number of back edges and number of cycles in
> DFS
>
> Select correct option:
>
> Both are equal.
>
> Cycles are half of back edges.
>
> Cycles are one fourth of back edges.
>
> * There is no relationship between back edges and number of cycle **(Right
> Answer)*
>
> * *
>
> You have an adjacency list for G, what is the time complexity to compute
> Graph
>
> transpose G^T ?
>
> Select correct option:
>
> * (V+E) **(Right Answer)*
>
> V.E
>
> V
>
> E
>
>
>
>
>
> Question # 3 of 10 ( Start time: 06:54:27 PM ) Total Marks: 1
>
> You have an adjacency list for G, what is the time complexity to compute
> Graph
>
> transpose G^T.?
>
> *?(V + E) **Right Answer)*
>
> ?(V E)
>
> ?(V)
>
> ?(V^2)
>
>
>
> What is the time complexity to extract a vertex from the priority queue in
> Prim's
>
> algorithm?
>
> Select correct option:
>
> *log (V) (**Right Answer)*
>
> V.V
>
> E.E
>
> log (E)
>
>
>
> Dijkstra's algorithm :
>
> Select correct option:
>
> Has greedy approach to find all shortest paths
>
> Has both greedy and Dynamic approach to find all shortest paths
>
> *Has greedy approach to compute single source shortest paths to all other
> vertices (**Right Answer)*
>
> Has both greedy and dynamic approach to compute single source shortest
> paths to all other vertices.
>
>
>
>
>
>
>
> What algorithm technique is used in the implementation of Kruskal solution
> for the
>
> MST?
>
> *Greedy Technique (**Right Answer)*
>
> Divide-and-Conquer Technique
>
> Dynamic Programming Technique
>
> The algorithm combines more than one of the above techniques
>
>
>
> What is the time complexity to extract a vertex from the priority queue in
> Prim's
>
> algorithm?
>
> Select correct option:
>
> O (log E)
>
> ? (V)
>
> ? (V+E)
>
> *O (log V) (**Right Answer)*
>
>
>
> Which is true statement in the following.
>
> Kruskal algorithm is multiple source technique for finding MST.
>
> Kruskal's algorithm is used to find minimum spanning tree of a graph, time
> complexity of this algorithm is O(EV)
>
> Both of above
>
> *Kruskal's algorithm (choose best non-cycle edge) is better than Prim's
> (choose best Tree edge) when the graph has relatively few edges ) (**Right
> Answer)*
>
> * *
>
> The relationship between number of back edges and number of cycles in DFS
> is,
>
> Both are equal
>
> Back edges are half of cycles
>
> Back edges are one quarter of cycles
>
> *There is no relationship between no. of edges and cycles (**Right Answer)*
>
> * *
>
> Kruskal's algorithm (choose best non-cycle edge) is better than Prim's
> (choose best tree
>
> edge) when the graph has relatively few edges.
>
> *True (**Right Answer)*
>
> False
>
> * *
>
> * *
>
> What is the time complexity to extract a vertex from the priority queue in
> Prim's
>
> algorithm?
>
> Select correct option:
>
> *log (V)*
>
> V.V
>
> E.E
>
> log (E)
>
>
>
> Suppose that a graph G = (V,E) is implemented using adjacency lists. What
> is the complexity of a breadth-first traversal of G?
>
> Select correct option:
>
> O(|V |^2)
>
> *O(|V | |E|) (**Right Answer)*
>
> O(|V |^2|E|)
>
> O(|V | + |E|)
>
>
>
> What is generally true of Adjacency List and Adjacency Matrix
> representations of graphs?
>
> Select correct option:
>
> 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) **Right Answer)*
>
> 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)
>
>
>
> What general property of the list indicates that the graph has an isolated
> vertex?
>
> Select correct option:
>
> There is Null pointer at the end of list.
>
> *The Isolated vertex is not handled in list. (not Sure)*
>
> Only one value is entered in the list.
>
> There is at least one null list.
>
>
> A dense undirected graph is:
>
> Select correct option:
>
> *A graph in which E = O(V^2) **(Right Answer)*
>
> A graph in which E = O(V)
>
> A graph in which E = O(log V)
>
> All items above may be used to characterize a dense undirected graph
>
>
>
>
> In digraph G=(V,E) ;G has cycle if and only if
>
> Select correct option:
>
> The DFS forest has forward edge.
>
> *The DFS forest has back edge (**Right Answer)*
>
> The DFS forest has both back and forward edge
>
> BFS forest has forward edge
>
>
>
> Back edge is:
>
> Select correct option:
>
> *(u, v) where v is an ancestor of u in the tree. (**Right Answer)*
>
> (u,v) where u is an ancesstor of v in the tree.
>
> (u, v) where v is an predcessor of u in the tree.
>
> None of above
>
>
>
> Using ASCII standard the string "abacdaacacwe" will be encoded with
> __________ bits
>
> Select correct option:
>
> 64
>
> *128 (**Right Answer)*
>
> 96
>
> 120
>
>
> Cross edge is :
>
> Select correct option:
>
> (u, v) where u and v are not ancestor of one another
>
> (u, v) where u is ancesstor of v and v is not descendent of u.
>
> *(u, v) where u and v are not ancestor or descendent of one another
> (**Right
> Answer)*
>
> (u, v) where u and v are either ancestor or descendent of one another.
>
>
>
> Which statement is true?
>
> Select correct option:
>
> If a dynamic-programming problem satisfies the optimal-substructure
> property, then a locally optimal solution is globally optimal.
>
> If a greedy choice property satisfies the optimal-substructure property,
> then a locally optimal solution is globally optimal.
>
> *Both of above **Right Answer)*
>
> None of above
>
> 10 If you find yourself in maze the better traversel approach will bE
>
>
> A dense undirected graph is:
>
> Select correct option:
>
> *A graph in which E = O(V^2) **(Right Answer)*
>
> A graph in which E = O(V)
>
> A graph in which E = O(log V)
>
> All items above may be used to characterize a dense undirected graph
>
>
> Which is true statement.
>
> Select correct option:
>
> *Breadth first search is shortest path algorithm that works on un-weighted
> graphs **(Right Answer)*
>
> Depth first search is shortest path algorithm that works on un-weighted
> graphs.
>
> Both of above are true.
>
> None of above are true.
>
>
> Forward edge is:
>
> Select correct option:
>
> (u, v) where u is a proper descendent of v in the tree.
>
> *(u, v) where v is a proper descendent of u in the tree. (**Right Answer)*
>
> (u, v) where v is a proper ancesstor of u in the tree.
>
> (u, v) where u is a proper ancesstor of v in the tree.
>
>
> Back edge is:
>
> Select correct option:
>
> *(u, v) where v is an ancestor of u in the tree. (**Right Answer)*
>
> (u,v) where u is an ancesstor of v in the tree.
>
> (u, v) where v is an predcessor of u in the tree.
>
> None of above
>
>
>
>
>
> Suppose that a graph G = (V,E) is implemented using adjacency lists. What
> is the complexity of a breadth-first traversal of G?
>
> Select correct option:
>
> O(|V |^2)
>
> *O(|V | |E|) (**Right Answer)*
>
> O(|V |^2|E|)
>
> O(|V | + |E|)
>
>
>
> In digraph G=(V,E) ;G has cycle if and only if
>
> Select correct option:
>
> The DFS forest has forward edge.
>
> *The DFS forest has back edge (**Right Answer)*
>
> The DFS forest has both back and forward edge
>
> BFS forest has forward edge
>
>
>
> What general property of the list indicates that the graph has an isolated
> vertex?
>
> Select correct option:
>
> There is Null pointer at the end of list.
>
> *The Isolated vertex is not handled in list. (not Sure)*
>
> Only one value is entered in the list.
>
> There is at least one null list.
>
>
>
> If you find yourself in maze the better traversel approach will be :
>
> BFS
>
> *BFS and DFS both are valid **(Right Answer)*
>
> Level order
>
> DFS
>
>
>
> Cross edge is :
>
> (u, v) where u and v are not ancestor of one another
>
> (u, v) where u is ancesstor of v and v is not descendent of u.
>
> *(u, v) where u and v are not ancestor or descendent of one another
> (**Right
> Answer)*
>
> (u, v) where u and v are either ancestor or descendent of one another.
>
>
>
> What algorithm technique is used in the implementation of Kruskal solution
> for the MST?
>
> *Greedy Technique (**Right Answer)*
>
> Divide-and-Conquer Technique
>
> Dynamic Programming Technique
>
> The algorithm combines more than one of the above techniques
>
>
>
> Kruskal's algorithm (choose best non-cycle edge) is better than Prim's
> (choose best tree edge) when the graph has relatively few
>
> *True (**Right Answer)*
>
> False
>
>
>
> You have an adjacency list for G, what is the time complexity to compute
> Graph transpose G^T.?
>
> *?(V + E) **Right Answer)*
>
> ? (V E)
>
> ? (V)
>
> ? (V^2)
>
>
>
> A digraph is strongly connected under what condition?
>
> A digraph is strongly connected if for every pair of vertices u, v e V, u
> can reach v .
>
> *A digraph is strongly connected if for every pair of vertices u, v e V, u
> can reach v and vice versa. (**Right Answer)*
>
> A digraph is strongly connected if for at least one pair of vertex u, v e
> V, u can reach v and vice versa.
>
> A digraph is strongly connected if at least one third pair of vertices
> u, v e V, u can reach v and vice versa.
>
>
>
> The relationship between number of back edges and number of cycles in DFS
> is,
>
> Both are equal
>
> Back edges are half of cycles
>
> Back edges are one quarter of cycles
>
> *There is no relationship between no. of edges and cycles (**Right Answer)*
>
>
>
> What algorithm technique is used in the implementation of Kruskal solution
> for the MST?
>
> *Greedy Technique (**Right Answer)*
>
> Divide-and-Conquer Technique
>
> Dynamic Programming Technique
>
> The algorithm combines more than one of the above techniques
>
> --
> *Zindagi mein 2 Logo ka buhat khayal rahkoooo
>
> *
> *Ist woh jiss ney tumhari jeet ke Liye buhat kuch hara hoo (Father)
>
> 2nd woh jiss ko tum ney har dukh me pukaara hoo (Mother)
> *
> *
> *
> *Regards, *
> *Umair Saulat*
>
> --
> To post to this group, send email to vuhelp_pk@googlegroups.com
> To unsubscribe from this group, send email to
> vuhelp_pk+unsubscribe@googlegroups.com
>
>
> Group Rules Vuhelp4u
> Sharing of Video songs links, movies links, dramas links are not allowed in
> study group. Only Islamic and general information Video links allowed.
> SPAM, Advertisement, and Adult messages are NOT allowed and that member will
> be behaved strictly.
> http://groups.google.com/group/vuhelp_pk?hl=en_US
>
--
To post to this group, send email to vuhelp_pk@googlegroups.com
To unsubscribe from this group, send email to vuhelp_pk+unsubscribe@googlegroups.com
Group Rules Vuhelp4u
Sharing of Video songs links, movies links, dramas links are not allowed in study group. Only Islamic and general information Video links allowed.
SPAM, Advertisement, and Adult messages are NOT allowed and that member will be behaved strictly.
http://groups.google.com/group/vuhelp_pk?hl=en_US
No comments:
Post a Comment