Design and Analysis of Algorithms - B.Tech 5th Semester Exam., 2018

2018•Semester 3•Civil-CA•End Semester
Aryabhatta Knowledge University, Patna
B.Tech 5th Semester Exam., 2018

Design and Analysis of Algorithms

Time: 03 HoursCode: 051506Full Marks: 70

Instructions:

  1. All questions carry equal marks.
  2. There are NINE questions in this paper.
  3. Attempt any FIVE questions in all.
  4. Question No. 1 is compulsory.
Q.1 Choose the correct answer (any seven):[14]

  1. Which algorithm is better for sorting between bubble sort and quicksort?

    1. Bubble sort
    2. Quicksort
    3. Both are equally good
    4. These cannot be compared

  2. An algorithm which uses the past results and uses them to find the new results is

    1. brute force
    2. divide and conquer
    3. dynamic programming algorithm
    4. None of the mentioned

  3. Out of the following which property of algorithm does not share?

    1. Input
    2. Finiteness
    3. Generality
    4. Constancy

  4. Which of the following standard algorithms is not a greedy algorithm?

    1. Dijkstra's shortest path algorithm
    2. Kruskal algorithm
    3. Bellmen Ford shortest path algorithm
    4. Prim's algorithm

  5. What is the time complexity of Huffman coding?

    1. \( O(N) \)
    2. \( O(N \log N) \)
    3. \( O(N(\log N)^2) \)
    4. \( O(N^2) \)

  6. How many comparisons are required to sort the list 1, 2, 3... n using insertion sort?

    1. \( (n^2+n+2)/2 \)
    2. \( (n^3+n-2)/2 \)
    3. \( (n^2+n-2)/2 \)
    4. \( (n^2-n-2)/2 \)

  7. Which of the following is true about Huffman coding?

    1. Huffman coding may become lossy in some cases
    2. Huffman codes may not be optimal lossless codes in some cases
    3. In Huffman coding, no code is prefix of any other code
    4. All of the above

  8. A complexity of algorithm depends upon

    1. time only
    2. space only
    3. both time and space
    4. None of the mentioned

  9. A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of

    1. 2.40
    2. 2.16
    3. 2.26
    4. 2.15

  10. Build heap is used in heap sort as a first step for sorting. What is the time complexity of build heap operation?

    1. \( O(n \log n) \)
    2. \( O(n^2) \)
    3. \( O(\log n) \)
    4. \( O(n) \)
Q.2 Solve this question :[14]

  1. Solve the following recurrence by successive substitution method:
    \( f(1) = 1 \), if \( n=1 \)
    \( f(n) = 3f(n/2) + 6 \), if \( n>1 \)

Q.3 Solve this question :[14]

  1. COUNTING SORT algorithm assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When \( k=O(n) \), the sort runs in \( \Theta(n) \) time. Change COUNTING SORT algorithm for the numbers lying in the range p to q where \( (q-p) \) is still \( O(n) \). Also analyze the new complexity.

Q.4 Solve both questions :[14]

  1. Consider a directed acyclic graph with non-negative edge costs and with a given start vertex s. Write an algorithm to compute distances from source s in \( O(E+V) \) time. Justify why your algorithm is correct.

  2. Explain, with an example, why Dijkstra's algorithm might take \( \Omega(V \log V) \) time.

Q.5 Solve this question :[14]

  1. Consider the two standard representations of directed graphs: the adjacency-list representation and the adjacency-matrix representation. Find a problem that can be solved more efficiently in the adjacency-list representation than in the adjacency-matrix representation, and another problem that can be solved more efficiently in the adjacency-matrix representation than in the adjacency-list representation.

Q.6 Solve both questions :[14]

  1. Differentiate between the following: Fractional Knapsack vs. 0/1 Knapsack.

  2. Differentiate between the following: Kruskal's vs. Prim's Algorithm.

Q.7 Solve this question :[14]

  1. What are NP-complete problems? Write some problems which are P, NP and NP-hard. Explain any NP-hard problem in detail.

Q.8 Solve this question :[14]

  1. Explain quicksort and its asymptotic complexities. Take some distinct numbers and perform quicksort over it.

Q.9 Solve both questions :[14]

  1. Explain travelling salesman problem using Greedy method.

  2. Explain travelling salesman problem using Dynamic programming method.