C
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIRST SEMESTER M.TECH DEGREE EXAMINATION, DEC 2017
COMPUTER SCIENCE AND ENGINEERING
(Computer Science and Engineering)
07CS6103 Algorithms and Complexity
Max. Marks: 60 Duration: 3 Hours
Answer all six questions. Part of each question is compulsory.
Answer either part or part of each question
Q.No Module 1 Marks
1a Explain various asymptotic notations used in algorithm analysis. 4
Answer b or c
b Use Master's theorem to solve the recurrences. Give the asymptotic upper and lower
bounds for in each of the following recurrences. Assume that is constant for
2. Make your bounds as tight as possible and justify your answers.

√


5
c Solve the following recurrence using Recursion Tree method.
cn2
5
Q.No
Module 2
Marks
2a Give the properties of B-Tree? Analyze the complexity of B-tree insertion with an example. 4
Answer b or c
b Explain aggregate analysis of a binary counter. 5
c Explain union by rank and path compression and analyse its complexity 5
Q.No
Module 3
Marks
3a Explain the working of DFS and its complexity. 4
Answer b or c
b
Write Floyd-Warshall's algorithm. We are given a weighted, directed graph E).Find the
shortest path from the given graph using Floyd-Warshall's algorithm.
.
5
c Define sparse graph. Explain the Johnson's algorithm with an example.
5
Q.No Module 4 Marks
4a Illustrate Bellman ford algorithm with an example. 4
Answer b or c
b Explain in detail maximum bipartite matching problem. 5
c Explain matroid with an example 5
Q.No Module 5 Marks
5a Give a randomized algorithm for pattern matching. 5
Answer b or c
b Explain Freivald's technique and finger printing mechanism. 7
c Give a randomized algorithm for verifying equality of strings 7
Q.No Module 6
Marks
6a Discuss the P class, NP and NP complete problems. 5
Answer b or c
b
Consider the following variant of 3-SAT called Not-All-Equal-SAT: Given a 3-CNF formula, decide
whether there exists an assignment to the variables of the formula such that every clause
contains at least one literal that is true and at least one literal that is false. Show that this problem
is NP-complete.
7
c Explain approximation algorithms. Give the approximation algorithm for Vertex cover with an
example.
7