CS502 Assignment 3 Solution
#1
CS502 Design and Analysis of Algorithms
Assignment 3 Solution - Spring 2017

Question. 1  Consider the following Directed Acyclic Graph.
[Image: dvLRV2c.jpg]

Run BFS on this graph by taking node ‘1’ as source node and list the vertices in order while running BFS.
 
Note: Write a list of vertices only, no need to show the intermediate steps.

Answer: 1, 3, 4, 8

Question. 2
 
Two directed graphs are given below Graph (A) & Graph (B), You are required to answer the following questions
1.      Is “Graph (A)” a connected graph? State Yes / No with valid reason
2.      Is “Graph (B)” contains a Hamiltonian cycle? State Yes / No with valid reason
 
 [Image: w3zvPmJ.png][Image: yAxKbmk.png]

                        Graph (A)                                                                                Graph (B)


Answer:

  1. No, because 1 is not connected with 5 directly and also 5 is not connected with 3 directly.
  2. Yes, 1, 2, 3, 4, 1 creates a Hamiltonian cycle.
  


Possibly Related Threads...
Thread Author Replies Views Last Post
  CS604 Assignment 3 Solution Pakistani 2 261 07-26-2017, 06:17 PM
Last Post: Rubaisha(Moody Girl)
  CS507 Assignment solution Rubaisha(Moody Girl) 0 171 07-25-2017, 10:23 PM
Last Post: Rubaisha(Moody Girl)
  CS601 Assignment 4 Solution Rana 0 504 07-24-2017, 11:49 AM
Last Post: Rana
  CS401 Assignment 3 Solution Pakistani 0 303 07-21-2017, 01:34 PM
Last Post: Pakistani
  CS504 Assignment 3 Rana 7 1,020 07-19-2017, 08:06 AM
Last Post: Rana
  CS605 assignment-3 Solution Nadeem Rana vu 1 212 07-14-2017, 05:49 PM
Last Post: Pakistani
  CS601 Assignment 3 Solution Pakistani 2 407 07-13-2017, 10:57 AM
Last Post: Rana
  cs 601 Assignment Sadaf Afzal 2 265 07-11-2017, 11:13 AM
Last Post: Pakistani
  CS301 Assignment 3 Solution Pakistani 2 1,110 07-09-2017, 07:13 PM
Last Post: Rana
  CS101 Assignment 3 Solution Rana 2 1,002 07-08-2017, 08:07 PM
Last Post: Rana



Users browsing this thread:
1 Guest(s)