Sponsored Links


Results 1 to 1 of 1

Thread: cs502 current paper subjective type fall 2010 on 21-02-2011

  1. #1
    Administrator Xpert's Avatar
    Join Date
    May 2010
    Location
    Jhelum
    Posts
    6,237

    cs502 current paper subjective type fall 2010 on 21-02-2011

    Sponsored Links1


    1.What are two steps generally involved while developing a dynamic programming algorithm?
    i. How Dijkstra’s algorithm operates?
    ii. What is the running time of the Dijkstra’s algorithm?


    3.Answer yes or no and give a brief explanation for your choice.
    If problem A reduces (is polynomial-time reducible) to problem B and B is NP-complete then A is NP-complete

    4.The following adjacency matrix represents a graph that consists of four vertices labeled 0, 1, 2 and 3. The entries in the matrix indicate edge weights.

    0
    1
    2
    3
    0
    0
    1
    0
    3
    1
    2
    0
    4
    0
    2
    0
    1
    0
    1
    3
    2
    0
    0
    0
    Answer the following question:
    Can an adjacency matrix for a directed graph ever not be square in shape? Why or why not?

    5. Consider the following two problems. In P1 we are given as input a set of n squares (specified by their corner points), and a number k. The problem is to determine whether there is any point in the plane that is covered by k or more squares.
    In P2 we are given as input an n–vertex graph, and a number k; the problem is to determine whether there is a set of k mutually adjacent vertices. (E.g. for k = 3 we are just looking for a triangle in the graph.).
    Obviously, the problems are both in NP. There exists a simple translation from P1 to P2: just make a graph vertex for each square, and add an edge between a pair of vertices if the corresponding two squares overlap.
    If P1 is NP-complete, would this translation imply that P2 is NP-complete?
    (Give your Answer in Yes or No)
    What is the application of edit distance technique?
    Formally describe Minimum Spanning Trees Problem.

    6. Let the adjacency list representation of an undirected graph is given below. Explain what general property of the list indicates that the graph has an isolated vertex.

    a à b à c à e
    b à a à d
    c à a à d à e à f
    d à b à c à f
    e à a à c à f
    f à c à d à e
    g

    7. What are the minimum and maximum numbers of elements in a heap of height h?

    1. Where clique cover problem arises?
    2. What is decision problem, also explain with example?
    9. Show the strongly connected components of the following graph using DFS algorithm. Take node E as a starting node. [You can show final result in exam software and need not to show all intermediate steps].


    Sponsored Links


    Please find the attachments for the diagrams.

    Attached Files Attached Files

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Replies: 0
    Last Post: 11-28-2011, 11:20 PM
  2. Isl201 fall 2010 paper subjective type on 19-02-2011
    By Xpert in forum Current Papers 2010
    Replies: 0
    Last Post: 02-20-2011, 12:18 AM
  3. Replies: 0
    Last Post: 02-19-2011, 05:15 PM
  4. sta630 midterm paper 8 december fall 2010 subjective type
    By Xpert in forum Current Papers 2010
    Replies: 0
    Last Post: 12-09-2010, 06:26 PM
  5. mgt211 current paper fall 2010 subjective type december 5
    By Xpert in forum Current Papers 2010
    Replies: 0
    Last Post: 12-07-2010, 12:11 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
-: Vuhelp Disclaimer :-
None of the files shown here are hosted or transmitted by this server. The links are provided solely by this site's users. The administrator's or staff of Vuhelp.net cannot be held responsible for what its users post, or any other actions of its users. You may not use this site to distribute or download any material when you do not have the legal rights to do so. It is your own responsibility to adhere to these terms. If you have any doubts about legality of content or you have any suspicions, feel free to contact us.
Online Education | JhelumSoft | Jobs