CS502 - Design and Analysis of algorithms finalterm papers

Dear fellows

This is my today's Algo paper

Fibonacci sequence 2mark

Clique cover problem 2mark

Make Adjacency list from the given table 3marks

Communication design problem (MST).

Strong connected component problem
[You must be registered and logged in to see this link.]
Heapify proof..... 5marks

Dijkstra Algorithmn

Define Floyd Marshall 5marks
[You must be registered and logged in to see this link.]
Floyd Marshall 3marks
runtime
space used
[You must be registered and logged in to see this image.]
DFS algoritmn 3marks

My today paper of Algorithm
total 52 questions 40 MCQ's and the following are some questions which i remember
(1) give a detailed example of 2-d maxima 2
(2) what is common problem in communication networks and circuit designing? 2
(3) write suedo code of relaxing a vertex 5
(4) write suedo code of dijkstra algorithm? 5
(5) define NP completeness 5
(6) define floyed warshall algorithm in these two cases 5
do not go through a vertex k at all
do go through a vertex k
(7) Define DAG 3
and a lot of repeated objective from past papers
[You must be registered and logged in to see this image.]

4 Questions of 5 Marks

1) Write steps of sieve techniques
2) Write Psuedo code of Dijkstra's algorithm
3) Prove the Lemma:
Consider a diagraph G = ( V,E ) and any DFS forest for G. G has a cycle if and only if the DFS forest has a back edges
4) Answer the following
Where the cliquer cover problem is used?

What is decision problem, also explain with examples?