Design and Analysis of Algorithms MCA paper May 2021

  • Subject Code: - PGCA 1920
  • Subject Name: - Design and Analysis of Algorithms
  • Date of Examination: - May 2021
  • Class: - MCA 2nd
  • Exam Mode: - Online

Instructions to Candidates

  1. Attempt any FIVE question(s), each question carries 14 marks.

QUESTIONS

  1. How can you compare the performance of different algorithms for solving the problem? Give an appropriate illustrative example with order statistics to explain the concept.
    2.
  2. How does backtracking work on the 8 Queens problem? Explain with a suitable example.
    3.
  3. Order the following functions by growth rate : N, N1.5, N2, N log log N, N log2 N, N log (N2), 2/N.2N, 2N/2, 37, N2 log N, N3. Indicate which functions grow at the same rate.
    4.
  4. What are Asymptotic growth rates? Distinguish between recursion and iteration with example. Compare the asymptotic growth rates in these two types of approaches.
    5.
  5. If we are given a directed graph G with n vertices. Explain how will you find out the length of the shortest path between any pair of vertices in G. Justify your answer with an example.
    6.
  6. What is Heap? What are the different types of heaps? Explain how do you construct a heap? Explain the Heap Sort algorithm with an example.
    7.
  7. Explain the Merge Sort algorithm with an example and also draw the tree structure of the recursive calls made. Analyze the efficiency of Merge sort algorithm.
    8.
  8. Implement an algorithm for knapsack problem using NP-hard approach.
    9.

ANSWERS:

Q1.

Top

Comments

Post a Comment

Popular posts from this blog

Discrete Structures & Optimization MCA paper Dec 2020

Image
Subject Code : - PGCA 1917 Subject Name : - Discrete Structures & Optimization Date of Examination : - December 2020 Class : - MCA 1st Instructions to Candidates Section A   is Compulsory consisting of TEN questions carrying TWO marks each. Section B & C have FOUR questions each. Attempt any FIVE questions from SECTION B & C carrying TEN marks each. Select at least TWO questions from SECTION B & C SECTION-A What are ordered pairs? Write the concept of Hashing Functions? Discuss rings in discrete structure. What is meant by isomorphic in graph theory? Give an example of a Finite graph. Write about the principle of Inclusion. Define an undirected graph. What is the Indegree of the graph? What is the use of the Karnaugh Map? What do you mean by chromatic number? SECTION-B Give the properties of relations and functions? Prove that a graph G with e=v-1 that has no circuit is a tree. How eulerian chains and cycles are related to a connected graph? Let ...
Read more

Discrete Structure and Optimization MCA paper Nov 2021

Subject Code: - PGCA 1917 Subject Name: - Discrete Structure and Optimization Date of Examination: - Nov 2021 Class: - MCA 1st Exam Mode: - Online Instructions to Candidates Attempt any FIVE question(s), each question carries 14 marks. QUESTIONS Prove the following : X ∩ (Y ⋃ Z) = (X ∩ Y) ⋃ (X ∩ Z) How many symmetric relations will there be on a set of three elements? Investigate the function f (x) = x 2 + 3x + 2 for increasing and decreasing function in its entire domain. Prove that the set {0,1,2} forms a field with respect to addition and multiplication modulo 3. Simplify the following Boolean functions using the Karnaugh map: F = x'y'z' + x'yz' + xyz' + xy' z' Find the number of diagonals...
Read more

Advanced Database Management System MCA Paper Dec 2020

Image
Subject Code : - PGCA 1953 Subject Name : - Advanced Database Management System Date of Examination : - December 2020 Class : - MCA 1st Instructions to Candidates Section A  is Compulsory consisting of TEN questions carrying TWO marks each. Section B & C  have FOUR questions each. Attempt any FIVE questions from  SECTION B & C  carrying TEN marks each. Select at least TWO questions from  SECTION B & C SECTION-A What do you mean by redundancy & how can it be avoided? What is the difference between the strong entity and weak entity set? Discuss the four data allocation strategies in the case of Distributed Databases. What is Relational Calculus? What is a NoSQL database? List any 2 NoSQL databases. Differentiate between a super key and a candidate key. What is Multivalve dependence? What is Spatial Database? Differentiate between 2-tier and 3-tier client-server architecture of database systems. List the different activities of a Database Administra...
Read more