Fundamentals of Algorithms CS502-Fall 2010 Assignment #5

Fundamentals of Algorithms

CS502-Fall 2010

Assignment #5

Deadline

Your assignment must be uploaded/submitted at or before 2^nd   Feb 2011

Uploading instructions

Please view the assignment submission process document provided to you by the Virtual University to upload the assignment.

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 take solid vision of the following topics

• Dijkstra’s Algorithm
• Bell man Ford Algorithm
• Floyd Warshall Algorithm

Guidelines

1.      In order to attempt this assignment you should have full command on Lecture # 38to Lecture # 45

2.      In order to solve this assignment you have strong concepts about following topics

• Dijkstra’s Algorithm
• Bell man Ford Algorithm
• Floyd Warshall Algorithm
• Complexity of Polynomial and Non deterministic polynomial problems

Recommended book for solving assignment

Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd ed.) McGraw Hill.

Estimated Time    2.5  hours

To search and understand the relevant material you require 1.5 and to give answer in precise manner you need one hour at maximum.

                             

Question# 1                   (7.5+7.5)

^{a)        Elaborate the three algorithms Dijkstra‘s, Bellman Ford and Floyd Warshall Algorithms on the following basis:}

                                                   ^{I.      Complexity of algorithms}

                                                 ^{II.      Domain of Applications  with examples}

                                               ^{III.      Differences}

                                               ^{IV.      Similarities}

                                                 ^{V.      Disadvantages if any}     

^{b)      Differentiate the Polynomial time and Non deterministic Polynomial problems on the bases of complexity nature with examples.}     

^{Note: Both parts answers should be in Table format. Be precise to justify your arguments.}

 

---