Skip to content
SmartFigureEdu

CS 3401 Algorithms question paper, April/May 2024

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 50901

B.E./B.Tech. DEGREE EXAMINATIONS, APRIL/MAY 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.

    State how the running time of an algorithm is measured.

  2. 2.

    Outline the significance of performing worst case analysis of an algorithm.

  3. 3.

    List the data structures that are used for representing graphs.

  4. 4.

    What is a strongly connected graph? Give an example.

  5. 5.

    What kinds of problems are solved using divide and conquer approach?

  6. 6.

    State the elements of greedy approach.

  7. 7.

    With an example, define Hamiltonian circuit.

  8. 8.

    Why is branch and bound approach found to be appropriate for solving travelling salesman problem?

  9. 9.

    State the difference between tractable and non-tractable problems.

  10. 10.

    When is a problem said to be NP- hard? Give an example.

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)
    • (i)Explain in detail about various asymptotic notations and it's properties.(8)
    • (ii)Use substitution method to show that T(n) = 2T(n/2) + n is O(n log(n)).(5)
  2. Or
  3. (b)
    • (i)With a suitable example, illustrate the time and space complexity analysis of binary search and linear search.(8)
    • (ii)Explain the working of naive string matching algorithm with ABCCDDAEFG as the text input and CDD as the search string.(5)
  4. 12.
    (a)
    • (i)Write the pseudocode for BFS and DFS traversals on the graph given below in fig. 12 (a) (i) and compare the time and space complexity of the two traversals. [Fig. 12 (a) (i): undirected graph with vertices 0 to 4; edges 0-1, 0-2, 1-2, 1-3, 2-4, 3-4](7)
    • (ii)Find the Minimum Spanning Tree of the following graph in fig. 12 (a) (ii) using Kruskal's algorithm. [Fig. 12 (a) (ii): undirected weighted graph; edges a-b 4, a-h 8, b-c 8, b-h 11, c-d 7, d-e 9, d-f 14, e-f 10, h-i 7, i-g 6, h-g 1, g-f 2](6)
  5. Or
  6. (b)
    • (i)Given a graph and a source vertex in the graph, find the shortest paths from the source vertex 0 to all vertices in the given graph 12 (b) (i). [Fig. 12 (b) (i): undirected weighted graph with vertices 0 to 8; edges 0-1 4, 0-7 8, 1-2 8, 1-7 11, 2-3 7, 2-8 2, 2-5 4, 3-4 9, 3-5 14, 4-5 10, 5-6 2, 6-7 1, 6-8 6, 7-8 7](8)
    • (ii)Using Ford-Fulkerson algorithm find the maximum possible flow in the network given below Fig 12 (b) (ii). [Fig. 12 (b) (ii): flow network, each edge labelled flow/capacity; S->A 0/8, S->D 0/3, A->B 0/9, D->B 0/7, D->C 0/4, B->T 0/2, C->T 0/5](5)
  7. 13.
    (a)
    • (i)Demonstrate divide and conquer approach by Performing quick sort on the following values. 44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88(7)
    • (ii)Using Dynamic programming, Solve matrix chain multiplication problem.(6)
  8. Or
  9. (b)
    • (i)Solve the following problem using Greedy algorithm. Given activities with their start and finish times, select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.(8)
    • (ii)A character-coding problem. A data file of 100,000 characters contains only the characters a-f, with the frequencies indicated as below [Table: Frequency (in thousands): a 45, b 13, c 12, d 16, e 9, f 5] Show the steps in constructing the final Huffman tree representing the optimal prefix code.(5)
  10. 14.
    (a)
    • (i)Explain the steps in solving n-queens problem using backtracking approach.(5)
    • (ii)Solve the following subset sum problem using back tracking. Let S = {3,7,9,13,26,41}; d(sum) = 51.(8)
  11. Or
  12. (b)
    • (i)Discuss briefly about the general method of branch and Bound approach and state how it differs from backtracking.(8)
    • (ii)Explain the branching mechanism in the Branch and Bound Strategy to solve 0/1 Knapsack problem.(5)
  13. 15.
    (a)
    • (i)Show that if an algorithm makes atmost a constant number of calls to polynomial time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time.(8)
    • (ii)Show that the satisfiability of Boolean formulas in 3-conjunctive normal form (3- CNF) is NP-complete.(5)
  14. Or
  15. (b)
    • (i)Illustrate polynomial-time approximation scheme for the sum of subsets problem.(7)
    • (ii)Illustrate the working of Miller-Rabin randomized primality test.(6)

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)
    • (i)How many spurious hits does the Rabin-Karp matcher encounter in the text T = 3141592653589793 when Working modulo q = 11 and looking for the pattern P = 26. Briefly write about the processing time, worst-case running time and average-case running time of Rabin-Karp algorithm.(10)
    • (ii)With an example to show the best-case, worst-case and average case analysis of heap sort.(5)
  2. Or
  3. (b)
    • (i)Run the Bellman-Ford algorithm on the directed graph of figure 16 (b) (i) below using vertex s as the source and show the results after each pass of an algorithm. [Fig. 16 (b) (i): directed graph with s = 0 and t, x, y, z = infinity; edges s->t 6, s->y 7, t->x 5, x->t -2, t->y 8, t->z -4, y->x -3, y->z 9, z->x 7, z->s 2](7)
    • (ii)With an example, Show that the cardinality of a maximum matching M in a bipartite graph G equals the value of a maximum flow f in its corresponding flow network G'.(8)

Other CS3401 papers