CS502 Fundamentals of Algorithms Assignment No .4 Solution Fall Semester 2013

[Vuhelper]

View more random threads:

• Software Engineering-1 (CS504) Assignment # 4 solution fall...
• CS408 Human computer Interaction Assignment no 5 June 2012
• CS601 Data Communication Assignment No. 03 Solution 23rd...
• CS201 Introduction to Programming Assignment No. 04...
• MGT 301 Principles of Marketing Assignment No 1 Fall...
• cs410 Visual Programming Assignment no 2 idea solution...
• cs601 assignment no 1 idea solution fall 2011 on 28th...
• CS 610 Computer Networks Assignment # 05 Fall 2010 solution
• cs201 assignment no 1 may 2015 solution
• Cs 408 assignment 2 solution....

CS502 Fundamentals of Algorithms Assignment No .4 Solution Fall Semester 2013 Due Date 01/Feb/2013



Assignment No. 04
Semester: Fall 2012
Fundamentals of Algorithm-CS502
Total Marks: 20

Due Date: 01/Feb/2013

Instructions:

Sponsored Links

Please read the following instructions carefully before submitting assignment:

You will submit your assignment before or on due date on VU-LMS.
Assignment should be completed by your own efforts it should not be copied from internet, handouts or books.
You should submit your .doc File via assignment interface at VU-LMS.
Assignment sent via Email will not be replied and accepted/graded in any case.
If the submitted assignment does not open or file is corrupt, it will not be graded.
You will submit solution only in document (.doc or .docx) File.

Objectives:

To understand the real applications Graph.

For any query about the assignment, contact at

Assignment Questions

Question1: Marks 10

A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search into the same four categories.


a. Prove that in a breadth-first search of an undirected graph, the following properties hold:

1. There are no back edges and no forward edges.

2. For each tree edge (u, v), we have d[v] = d[u] + 1.

3. For each cross edge (u, v), we have d[v] = d[u] or d[v] = d[u] + 1.


b. Prove that in a breadth-first search of a directed graph, the following properties hold:

1. There are no forward edges.

2. For each tree edge (u, v), we have d[v] = d[u] + 1.

3. For each cross edge (u, v), we have d[v] ≤ d[u] + 1.

4. For each back edge (u, v), we have 0 ≤ d[v] ≤ d[u].


Question 2: Marks 5

Explain how a vertex u of a directed graph can end up in a depth-first tree containing only u, even though u has both incoming and outgoing edges in G.


Question 3: Marks 5


Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G, then any depth-first search must result in d[v] ≤ f[u].

[Vuhelper]

Idea Solution Here:download attachment file



CS5024THASSIGNMENTCOMPLETESOLUTION.doc