CS502 Fundamental of Algorithms Assignment # 05 Spring 2012

CS 502 Fundamental of Algorithms

Assignment # 05

Spring 2012

Total Marks = 20

Deadline

Your assignment must be uploaded / submitted before or on July 04, 2012

Upload Instructions

Please view the assignment submission process document provided to you by the

Virtual University.

Rules for Marking

Please note that your assignment will not be graded if:

• It is submitted after due date

• The file you uploaded does not open

• The file you uploaded is copied from someone else or from internet

• It is in some format other than .doc

Note: Material that is an exact copy from handouts or internet would be graded

Zero marks. Your solution should consist of the material found through different sources and written in your own words.

Assignment Statements:

Question:

Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Kruskal's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?

Note:

To solve this question, you are requested to read Kruskal's algorithm form your recommended book with listen the lecture carefully.