Skip to content
SmartFigureEdu

CS 3401 Algorithms question paper, April/May 2023

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 30121

B.E./B.Tech. DEGREE EXAMINATIONS, APRIL/MAY 2023.

Fourth Semester

Computer Science and Engineering

CS 3401 — ALGORITHMS

(Common to : )

(Regulations 2021)

Time : Three hoursMaximum : 100 marks

Answer ALL questions.

PART A — (10 × 2 = 20 marks)

  1. 1.

    Define time complexity of an algorithm.

  2. 2.

    List the types of asymptotic notations in analysing complexity of algorithms.

  3. 3.

    Outline a directed graph with an example.

  4. 4.

    What is minimum spanning tree?

  5. 5.

    Outline divide-and conquer algorithm design paradigm.

  6. 6.

    Define a multistage graph.

  7. 7.

    What is backtracking?

  8. 8.

    State the travelling salesman problem.

  9. 9.

    Outline the difference between a tractable problem and an intractable problem.

  10. 10.

    State the bin packing problem.

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)

    Write an algorithm to perform linear search on an array of 'N' numbers. Illustrate the best case, average case and worst case complexity of the linear search algorithm with an example.

  2. Or
  3. (b)

    What is pattern searching? Outline the steps in the Rabin-Karp algorithm for pattern searching with an example.

  4. 12.
    (a)

    Outline the breadth first search graph traversal algorithm and depth first search graph traversal algorithm with an example.

  5. Or
  6. (b)

    Explain the Dijkstra's shortest path algorithm with an example.

  7. 13.
    (a)

    Outline the merge sort algorithm with an example.

  8. Or
  9. (b)

    What is a Huffman tree? Outline the steps to build a Huffman tree using greedy algorithm design paradigm with an example.

  10. 14.
    (a)

    State the Hamiltonian circuit problem. Outline the steps to find the Hamiltonian circuit using backtracking algorithm design paradigm with an example.

  11. Or
  12. (b)

    State the Knapsack problem. Outline how Knapsack problem can be solved using branch and bound algorithm design paradigm with an example.

  13. 15.
    (a)

    Elaborate NP-complete problem and NP-hard problem with an example.

  14. Or
  15. (b)

    Outline the randomized quick sort algorithm with an example.

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)

    Apply the insertion sort algorithm to sort the following sequence of n numbers stored in an array A. 15,9,1,22,26,19,55,43,99,2 Illustrate each step of the sorting process.

  2. Or
  3. (b)

    What is dynamic programming? Explain the dynamic programming solution for matrix chain multiplication with an example.

Other CS3401 papers