02-21-2011, 07:22 PM
[FONT="]1.What are two steps generally involved while developing a dynamic programming algorithm?[/FONT]
[FONT="]i. [/FONT][FONT="]How Dijkstra’s algorithm operates?[/FONT]
[FONT="]ii. [/FONT][FONT="]What is the running time of the Dijkstra’s algorithm?[/FONT]
[FONT="] [/FONT]
[FONT="] [/FONT]
[FONT="]3.Answer yes or no and give a brief explanation for your choice.[/FONT]
[FONT="]If problem A reduces (is polynomial-time reducible) to problem B and B is NP-complete then A is NP-complete[/FONT]
[FONT="] [/FONT]
[FONT="]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.[/FONT]
[FONT="] [/FONT]
[FONT="]0[/FONT]
[FONT="]1[/FONT]
[FONT="]2[/FONT]
[FONT="]3[/FONT]
[FONT="]0[/FONT]
[FONT="]0[/FONT]
[FONT="]1[/FONT]
[FONT="]0[/FONT]
[FONT="]3[/FONT]
[FONT="]1[/FONT]
[FONT="]2[/FONT]
[FONT="]0[/FONT]
[FONT="]4[/FONT]
[FONT="]0[/FONT]
[FONT="]2[/FONT]
[FONT="]0[/FONT]
[FONT="]1[/FONT]
[FONT="]0[/FONT]
[FONT="]1[/FONT]
[FONT="]3[/FONT]
[FONT="]2[/FONT]
[FONT="]0[/FONT]
[FONT="]0[/FONT]
[FONT="]0[/FONT]
[FONT="]Answer the following question:[/FONT]
[FONT="]Can an adjacency matrix for a directed graph ever not be square in shape? Why or why not?[/FONT]
[FONT="] [/FONT]
[FONT="]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.[/FONT]
[FONT="]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.). [/FONT]
[FONT="]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.[/FONT]
[FONT="]If P1 is NP-complete, would this translation imply that P2 is NP-complete?[/FONT]
[FONT="](Give your Answer in Yes or No)[/FONT][FONT="][/FONT]
[FONT="]What is the application of edit distance technique?[/FONT]
[FONT="]Formally describe Minimum Spanning Trees Problem.[/FONT]
[FONT="] [/FONT]
[FONT="]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.[/FONT]
[FONT="] [/FONT]
[FONT="] a [/FONT]à[FONT="] b [/FONT]à[FONT="] c [/FONT]à[FONT="] e[/FONT]
[FONT="] b [/FONT]à[FONT="] a [/FONT]à[FONT="] d [/FONT]
[FONT="] c [/FONT]à[FONT="] a [/FONT]à[FONT="] d [/FONT]à[FONT="] e [/FONT]à[FONT="] f[/FONT]
[FONT="] d [/FONT]à[FONT="] b [/FONT]à[FONT="] c [/FONT]à[FONT="] f[/FONT]
[FONT="] e [/FONT]à[FONT="] a [/FONT]à[FONT="] c [/FONT]à[FONT="] f[/FONT]
[FONT="] f [/FONT]à[FONT="] c [/FONT]à[FONT="] d [/FONT]à[FONT="] e[/FONT]
[FONT="] g[/FONT]
[FONT="] [/FONT]
[FONT="]7. What are the minimum and maximum numbers of elements in a heap of height h?[/FONT]
[FONT="] [/FONT]
[FONT="]1. [/FONT][FONT="]Where clique cover problem arises?[/FONT]
[FONT="]2. [/FONT][FONT="]What is decision problem, also explain with example?[/FONT][FONT="][/FONT]
[FONT="]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].
[/FONT]
Please find the attachments for the diagrams.
[FONT="][/FONT]
[FONT="] [/FONT]
[FONT="]i. [/FONT][FONT="]How Dijkstra’s algorithm operates?[/FONT]
[FONT="]ii. [/FONT][FONT="]What is the running time of the Dijkstra’s algorithm?[/FONT]
[FONT="] [/FONT]
[FONT="] [/FONT]
[FONT="]3.Answer yes or no and give a brief explanation for your choice.[/FONT]
[FONT="]If problem A reduces (is polynomial-time reducible) to problem B and B is NP-complete then A is NP-complete[/FONT]
[FONT="] [/FONT]
[FONT="]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.[/FONT]
[FONT="] [/FONT]
[FONT="]0[/FONT]
[FONT="]1[/FONT]
[FONT="]2[/FONT]
[FONT="]3[/FONT]
[FONT="]0[/FONT]
[FONT="]0[/FONT]
[FONT="]1[/FONT]
[FONT="]0[/FONT]
[FONT="]3[/FONT]
[FONT="]1[/FONT]
[FONT="]2[/FONT]
[FONT="]0[/FONT]
[FONT="]4[/FONT]
[FONT="]0[/FONT]
[FONT="]2[/FONT]
[FONT="]0[/FONT]
[FONT="]1[/FONT]
[FONT="]0[/FONT]
[FONT="]1[/FONT]
[FONT="]3[/FONT]
[FONT="]2[/FONT]
[FONT="]0[/FONT]
[FONT="]0[/FONT]
[FONT="]0[/FONT]
[FONT="]Answer the following question:[/FONT]
[FONT="]Can an adjacency matrix for a directed graph ever not be square in shape? Why or why not?[/FONT]
[FONT="] [/FONT]
[FONT="]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.[/FONT]
[FONT="]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.). [/FONT]
[FONT="]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.[/FONT]
[FONT="]If P1 is NP-complete, would this translation imply that P2 is NP-complete?[/FONT]
[FONT="](Give your Answer in Yes or No)[/FONT][FONT="][/FONT]
[FONT="]What is the application of edit distance technique?[/FONT]
[FONT="]Formally describe Minimum Spanning Trees Problem.[/FONT]
[FONT="] [/FONT]
[FONT="]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.[/FONT]
[FONT="] [/FONT]
[FONT="] a [/FONT]à[FONT="] b [/FONT]à[FONT="] c [/FONT]à[FONT="] e[/FONT]
[FONT="] b [/FONT]à[FONT="] a [/FONT]à[FONT="] d [/FONT]
[FONT="] c [/FONT]à[FONT="] a [/FONT]à[FONT="] d [/FONT]à[FONT="] e [/FONT]à[FONT="] f[/FONT]
[FONT="] d [/FONT]à[FONT="] b [/FONT]à[FONT="] c [/FONT]à[FONT="] f[/FONT]
[FONT="] e [/FONT]à[FONT="] a [/FONT]à[FONT="] c [/FONT]à[FONT="] f[/FONT]
[FONT="] f [/FONT]à[FONT="] c [/FONT]à[FONT="] d [/FONT]à[FONT="] e[/FONT]
[FONT="] g[/FONT]
[FONT="] [/FONT]
[FONT="]7. What are the minimum and maximum numbers of elements in a heap of height h?[/FONT]
[FONT="] [/FONT]
[FONT="]1. [/FONT][FONT="]Where clique cover problem arises?[/FONT]
[FONT="]2. [/FONT][FONT="]What is decision problem, also explain with example?[/FONT][FONT="][/FONT]
[FONT="]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].
[/FONT]
Please find the attachments for the diagrams.
[FONT="][/FONT]
[FONT="] [/FONT]