Skip to content
SmartFigureEdu

CS 3401 Algorithms question paper, November/December 2023

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 20868

B.E./B.Tech. DEGREE EXAMINATIONS, NOVEMBER/DECEMBER 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 recursion relation.

  2. 2.

    Discuss the time and space complexity of insertion sort.

  3. 3.

    What is minimum spanning tree?

  4. 4.

    What is bipartite graph?

  5. 5.

    What is meant by principle of optimality?

  6. 6.

    Write down the steps to build Huffman free.

  7. 7.

    Write short notes on graph colouring.

  8. 8.

    What is travelling salesman problem? Give an example.

  9. 9.

    Differentiate tractable and intractable problems.

  10. 10.

    Write an algorithm to find the kth smallest number.

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)

    Write the asymptotic notations used for best case, average case and worst case analysis of algorithms. Also write an algorithm of finding maximum element of an array and perform best, worst and average case complexity with appropriate order notations.

  2. Or
  3. (b)
    • (i)Write and explain naive string mating algorithm.(6)
    • (ii)Suppose T = 1011101110 and p = 111. Find all valid ships.(7)
  4. 12.
    (a)

    Write and explain the pseudo code for breadth first search and discuss its time complexity.

  5. Or
  6. (b)

    Write and explain the pseudo code for Floyd Warshall algorithm and write its time complexity.

  7. 13.
    (a)

    Explain in detail about merge sort. Illustrate the algorithm with a numeric example and provide complete analysis of merge sort algorithm.

  8. Or
  9. (b)

    Explain the dynamic programming approach of matrix multiplication with an example.

  10. 14.
    (a)

    Write down the steps to solve subset sum problem using backtracking approach explain with an example.

  11. Or
  12. (b)

    Write down the steps to solve Travelling Salesperson problem using branch and bound approach. Explain with an example.

  13. 15.
    (a)

    Write short notes on the following:

    • (i)NP algorithms(4)
    • (ii)NP Hardness(4)
    • (iii)NP-Completeness(5)
  14. Or
  15. (b)

    Write short notes on the following:

    • (i)Problem Reduction(4)
    • (ii)Primality testing(4)
    • (iii)Randomized sorting(5)

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)

    Write and explain the Dijikstra's algorithm. Find the shortest path the following graph using Dijikstra's algorithm. [Figure: directed weighted graph; edges s->a 1, s->b 5, a->b 2, a->c 2, a->d 1, b->d 2, c->d 3, c->e 1, d->e 2]

  2. Or
  3. (b)

    Solve the following instance of Knapsack problem by branch and bound algorithm. [Table: Item - Weight - Profit: 1 - 5 - $40; 2 - 7 - $35; 3 - 2 - $18; 4 - 4 - $4; 5 - 5 - $10; 6 - 1 - $2]

Other CS3401 papers