Scribd Logo
Upload

Welcome to Scribd!

  • 27 views

    Question Paper Code:: Reg. No.

    Uploaded by

    Vijay Vijay
    This document provides information about an examination for the course Design and Analysis of Algorithms. It includes 16 questions divided into three parts (Part A, B, C) worth a total of 100 marks. The questions cover topics related to algorithms including sorting, greedy algorithms, dynamic programming, NP-complete problems, graph algorithms, and backtracking. Students are asked to provide algorithms, analyze running times, and solve problems related to these algorithm design techniques.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Question Paper Code:: Reg. No.

    Uploaded by

    Vijay Vijay
    27 views3 pages
    This document provides information about an examination for the course Design and Analysis of Algorithms. It includes 16 questions divided into three parts (Part A, B, C) worth a total of 100 marks. The questions cover topics related to algorithms including sorting, greedy algorithms, dynamic programming, NP-complete problems, graph algorithms, and backtracking. Students are asked to provide algorithms, analyze running times, and solve problems related to these algorithm design techniques.

    Original Title

    X20397(CS6402)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides information about an examination for the course Design and Analysis of Algorithms. It includes 16 questions divided into three parts (Part A, B, C) worth a total of 100 marks. The questions cover topics related to algorithms including sorting, greedy algorithms, dynamic programming, NP-complete problems, graph algorithms, and backtracking. Students are asked to provide algorithms, analyze running times, and solve problems related to these algorithm design techniques.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    27 views3 pages

    Question Paper Code:: Reg. No.

    Uploaded by

    Vijay Vijay
    This document provides information about an examination for the course Design and Analysis of Algorithms. It includes 16 questions divided into three parts (Part A, B, C) worth a total of 100 marks. The questions cover topics related to algorithms including sorting, greedy algorithms, dynamic programming, NP-complete problems, graph algorithms, and backtracking. Students are asked to provide algorithms, analyze running times, and solve problems related to these algorithm design techniques.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    *X20397*

    Reg. No. :

    Question Paper Code : X20397

    B.E./B.Tech. Degree Examinations, November/December 2020


    Third/Fourth Semester
    Computer Science and Engineering
    CS 6402 – Design and Analysis of Algorithms
    (Common to : Information Technology)
    (Regulations 2013)

    Time : Three Hours Maximum : 100 Marks

    Answer all questions

    Part – A (10×2=20 Marks)

    1. Give the Euclid’s algorithm for computing gcd of two numbers.

    2. What is a basic operation ?

    3. Give the mathematical notation to determine if a convex direction is towards left


    or right and write the algorithm.

    4. Prove that any comparison sort algorithm requires Ω (n log n) comparisons in the
    worst case.

    5. State the general principle of greedy algorithm.

    6. What is meant by dynamic programming ?

    7. Define the iterative improvement technique.

    8. What is maximum cardinality matching ?

    9. How NP-Hard problems are different from NP-Complete ?

    10. Define Hamiltonian Circuit problem.


    X20397 -2- *X20397*

    Part – B (5×13=65 Marks)

    11. a) i) Write the Insertion sort algorithm and estimate its running time. (7)
    ii) Find the closest asymptotic tight bound by solving the recurrence equation
    T(n) = 8T(n/2) + n2 with (T(1)=1) using Recursion tree method. [Assume that
    T(1)∈Θ(1)]. (6)
    (OR)
    b) i) Suppose W satisfies the following recurrence equation and base case (where
    c is a constant) : W(n) = c.n + W(n/2) and W(1) = 1. What is the asymptotic
    order of W(n) ? (6)
    ii) Show how to implement a stack using two queues. Analyze the running time
    of the stack operations. (7)

    12. a) What is divide and conquer strategy and explain the binary search with suitable
    example problem. (13)
    (OR)
    b) Solve the following using Brute-Force algorithm : (13)
    Find whether the given string follows the specified pattern and return 0 or 1
    accordingly.
    Examples :
    i) Pattern : “abba”, input : “redblueredblue” should return 1
    ii) Pattern : “aaaa”, input : “asdasdasdasd” should return 1
    iii) Pattern : “aabb” input : “xyzabcxzyabc” should return 0.

    13. a) Give the Pseudo code for Prim’s algorithm and apply the same to find the
    minimum spanning tree of the graph shown below :

    (OR)
    b) Explain the memory function method for the Knapsack problem and give the
    algorithm.
    *X20397* -3- X20397

    14. a) i) State and prove Max-Flow Min-Cut theorem. (7)


    ii) Summarize the steps of the simplex method. (6)
    (OR)
    b) i) Explain briefly about Stable marriage algorithm. (7)
    ii) Determine the time-efficiency class of the stable marriage algorithm. (6)

    15. a) i) Suggest an approximation algorithm for traveling salesperson problem.


    Assume that the cost function satisfies the triangle inequality. (7)
    ii) Explain how job assignment problem could be solved, given n tasks and n
    agents where each agent has a cost to complete each task, using Branch and
    Bound technique. (6)
    (OR)
    b) i) The knight is placed on the first block of an empty board and moving according
    to the rules of chess, must visit each square exactly once. Solve the above
    problem using backtracking procedure. (7)
    ii) Implement an algorithm for Knapsack problem using NP-Hard approach. (6)

    Part – C (1×15=15 Marks)

    16. a) Apply the greedy technique to find the minimum spaning tree using Prim’s
    algorithm for the given graph. (15)

    (OR)
    b) Explain the 4-Queen’s problem using backtracking. Write the algorithms. Give
    the estimated cost for all possible solutions of 4-Queen’s problem. Specify the
    implicit and explicit constraints. (15)

    –––––––––––––

    You might also like