Fundamentals of Algorithms (CS502)
Assignment # 03
Spring 2018
Question # 1: 5
Marks
Marks
Consider the following set of activities along with
their start and finish time. You are required to schedule the activities (that
start first) using Greedy Algorithm for activity selection.
their start and finish time. You are required to schedule the activities (that
start first) using Greedy Algorithm for activity selection.
You have to provide all the steps. Zero
marks will be awarded for incomplete/partial solution.
marks will be awarded for incomplete/partial solution.
|
Activity
|
Start time
|
Finish time
|
|
A
|
1
|
4
|
|
B
|
3
|
5
|
|
C
|
1
|
6
|
|
D
|
5
|
7
|
|
E
|
3
|
8
|
|
F
|
5
|
9
|
|
G
|
6
|
10
|
|
H
|
8
|
11
|
|
I
|
8
|
12
|
Solution :
Question # 2: 10
(5+5) Marks
(5+5) Marks
(A)Representthe following Graph
in the Adjacency List format.
in the Adjacency List format.
Note:(1,
2, 3, 4, 5, 6, and 7 are the names of the vertices).
2, 3, 4, 5, 6, and 7 are the names of the vertices).
Solution:
(B)
Draw the Graph for the following Adjacency Matrix representation.
Draw the Graph for the following Adjacency Matrix representation.
Note:
(1, 2, 3, 4, 5, and 6 are the names of the Vertices).
(1, 2, 3, 4, 5, and 6 are the names of the Vertices).
Solution:
Download file for complete solution.
