ALGORITHM CS702 Final Term Paper 2013
Total Marks = 100
Time Allowed = 180 minutes
Question No. 1. (10 points) (From
Lecture 23)
Find the
longest common subsequence from “11101010” and “101010010” using dynamic
programming
Question No.2. (10 points) (From
Lecture 25)
Find the
maximum size of mutually compatible activities that are using the same
resource. Finishing and starting time has been given in the table below.
|
i
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
|
si
|
1
|
3
|
0
|
5
|
3
|
5
|
6
|
8
|
8
|
2
|
12
|
|
fi
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
Question No.3. (Points 15) (From
Lecture 26)
Give the
Huffman codes for each of the following letters. Also make the Huffman tree.
Letter with frequencies are given as below.
a:45 b:13 c:12 d:16 e
:9 f :5
Question No.4. (Points 15) (From
lecture 32)
Run the
Kruskal’s algorithm on the following graph to find the minimal spanning tree
Question No.5. (15 points) (From
lecture no 33)
Find the
shortest paths by running the Bellman Ford Algorithm, from source node s.
Question No.6. (From lecture no 38, 39,
40) (5 + 5 + 10)
a)
If a|b and a|c, then prove
that a|(bx + cy)
b)
If a|b and b|a, then prove
that a = ±b
c)
If n2 is even,
then prove that n is also even
Question No.7. (10 + 5)(From lecture No
44)
CLIQUE =
{<G,k> | G is an undirected graph with a clique of size k}
Show that
CLIQUE is NP-Hard and CLIQUE is in NP (10+5)
Download Click here