Skip to content
SmartFigureEdu

CS 3401 Algorithms question paper, November/December 2024

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 40921

B.E./B.Tech. DEGREE EXAMINATIONS, NOVEMBER/DECEMBER 2024.

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.

    What is recurrence relation?

  3. 3.

    Name the graph traversal techniques.

  4. 4.

    Differentiate indegree and outdegree.

  5. 5.

    Define Divide and Conquer approach.

  6. 6.

    List the elements of Greedy strategy.

  7. 7.

    Write the time complexity for solving n-Queens problem.

  8. 8.

    Define Optimal Binary search.

  9. 9.

    Give example for NP hard and NP complete problem.

  10. 10.

    List some applications of using Randomized algorithms.

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)

    Explain various complexity measures and the role of asymptotic notations towards algorithm analysis.

  2. Or
  3. (b)

    Describe Binary search and Interpolation search algorithm with an example. Give its respective complexity measures.

  4. 12.
    (a)

    Write Kruskal's algorithm and to find the Minimum Spanning tree for the following graph [Figure: undirected weighted graph with vertices A to J; edges A-F 2, A-B 3, F-G 7, F-E 1, G-E 6, G-H 15, B-D 16, B-C 17, C-D 8, D-E 11, D-I 4, E-I 10, E-H 5, C-I 18, I-H 12, I-J 9, H-J 13]

  5. Or
  6. (b)

    In the given graph, the vertex represents the city and edge represents the cost between the two vertices. Apply Dijkstra's shortest algorithm and find the Optimal cost to reach the destination. Also determine the Worst case time complexity of the algorithm. [Figure: directed graph with source s (0) and vertices t, x, y, z (each infinity); edges s->t 10, s->y 5, t->x 1, t->y 2, y->t 3, y->x 9, y->z 2, x->z 4, z->x 6, z->s 7]

  7. 13.
    (a)

    Apply Merge sort algorithm to sort the given set of numbers (40, 25, 69, 65, 31, 53, 86, 24, 55, 57, 19, 21, 16) and compute the Worst-case, Average-case and Best-case time complexity of the algorithm.

  8. Or
  9. (b)

    Produce Huffman tree for the following data and encode the data abbcddeef. [Table: Character - Frequency: a 5, b 9, c 12, d 13, e 16, f 45]

  10. 14.
    (a)

    Apply Backtracking approach and determine whether the given graph can be colored using 4 colors with graph colouring techniques. [Figure: undirected graph with 12 vertices numbered 1 to 12]

  11. Or
  12. (b)

    Consider the following graph. The vertex represents the city and edge represents the cost between the two vertices. A salesman starts from node 1, visit all the cities exactly once and return to the starting node. Justify that the algorithm that uses optimality principle produces an optimal tour cost to visit all cities. [Figure: directed graph on cities 1, 2, 3, 4 with costs shown on the arcs: between 1 and 2: 2 and 2; between 1 and 4: 6 and 5; between 2 and 3: 9 and 3; between 4 and 3: 7 and 4; between 1 and 3: 10 and 4; between 4 and 2: 8]

  13. 15.
    (a)

    Explain Polynomial time algorithms problems with an example.

  14. Or
  15. (b)

    Apply approximation algorithm for Travelling salesmen problem with suitable example.

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)

    Apply Ford Fulkerson algorithm for the following graph and determine the maximum flow in the graph. [Figure: flow network with source s, sink t and vertices v1, v2, v3, v4; edges s->v1 16, s->v2 13, v1->v2 10, v2->v1 4, v1->v3 12, v3->v2 9, v2->v4 14, v4->v3 7, v3->t 20, v4->t 4]

  2. Or
  3. (b)

    Consider the given set of numbers (65, 70, 75, 80, 85, 60, 55, 40, 45). Apply Quicksort by using

    • (i)First element as Pivot element(7)
    • (ii)Middle element as Pivot element.(8)

Other CS3401 papers