Fundamentals of Algorithms
CS502-Spring 2009
Assignment #4
Deadline
Your assignment must be uploaded/submitted at or before January 21st 2011
Uploading instructions
Please view the assignment submission process document provided to you by the Virtual University
Rules for Marking
It should be clear that your assignment will not get any credit if:
oThe assignment is submitted after due date.
oThe submitted assignment does not compile or run.
oThe assignment is copied.
Objectives
This assignment will help you to understand the concepts of Graph theory particularly initial representation techniques and traversing techniques of Graphs BFS and DFS logics.
Guidelines
1. In order to attempt this assignment you should have full command on Lecture # 33 to Lecture # 37
2. To explore traversing techniques you must also read the chapter of “Elementary Graph algorithms” of recommended book below.
3. In order to solve this assignment you should have strong concepts about following topics
ü Graphs basic representation techniques
ü Breadth First Search
ü Depth First Search
Recommended book for solving assignment
Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd ed.) McGraw Hill.Estimated Time 3.5 hours
Question understanding time is one hour and to develop and implement the logic of part “a” you require half an hour and to develop part “b” you required at most two hours .It all depend upon your sheer concentration while developing the assignment.
Question# 1
a) Give the adjacency matrix and adjacency list for the following graph. Fig 1.1 (2.5+2.5)
b) Apply the BFS and DFS on the following graph and show values in queue/stack stepwise on the following graph Take node 1 as source node. fig1.1 (7.5+7.5)
No comments:
Post a Comment