My Report (&Account)

DAA Online Test


Correct Answer: 2 points | Wrong: -1 point
Grades: A* (100% score) | A (80%-99%) | B (60%-80%) | C (40%-60%) | D (0%-40%)
advertisement

Here is the complete list of test quizzes on Design & Analysis of Algorithms.

1. Which of the following can be the base case for the recursive implementation used to find the length of linked list?

#include<stdio.h>
#include<stdlib.h>
struct Node
{
      int val;
      struct Node *next;
}*head;
int get_len()
{
      struct Node *temp = head->next;
      int len = 0;
      while(temp != 0)
      {
          len++;
          temp = temp->next;
      }
      return len;
}
int main()
{
      int arr[10] = {1,2,3,4,5}, n = 5, i;
      struct Node *temp, *newNode;
      head = (struct Node*)malloc(sizeof(struct Node));
      head->next = 0;
      int len = get_len();
      printf("%d",len);
      return 0;
}

Question 1 of 50

2. Select the appropriate recursive call for QuickSort.(arr is the array, low is the starting index and high is the ending index of the array, partition returns the pivot element, we will see the code for partition very soon)

Question 2 of 50

3. Interpolation search is a variation of?

Question 3 of 50

4. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?

Question 4 of 50

5. What is a subset sum problem?

Question 5 of 50

6. What will be the recurrence relation of the code of recursive bubble sort?

Question 6 of 50

7. Which happens if the fast-moving pointer(hare) reaches the tail of the linked list?

Question 7 of 50

8. Which of the following is false about the Kruskal’s algorithm?

Question 8 of 50

9. An undirected graph has an eulerian cycle if and only if all the vertices have an odd degree.

Question 9 of 50

10. Consider the following code to find the nth fibonacci term using dynamic programming:

1. int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

Which technique is used by line 7 of the above code?

Question 10 of 50

11. What is the total block length 'n' of a Hamming code?

Question 11 of 50

12. Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?

Question 12 of 50

13. Which of the following areas do closest pair problem arise?

Question 13 of 50

14. Cocktail sort is a comparison based sort.

Question 14 of 50

15. Choose the correct function for recursive bubble sort?

Question 15 of 50

16. Consider the following assembly line problem:

time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4

What is the minimum time required to build the car chassis?

Question 16 of 50

17. What will be the ciphered text if the string “HELLO” is given as input to the code of hill cipher with keyword as “SANFOUNDRY”?

Question 17 of 50

18. The Depth First Search traversal of a graph will result into?

Question 18 of 50

19. What is the worst case time complexity of tree sort (when implemented with a balanced tree)?

Question 19 of 50

20. Consider the figure given below. If a message is flooded from node A, it will reach to which of the following nodes?
Find the nodes if a message is flooded from node A for the given graph

Question 20 of 50

21. Consider the following dynamic programming implementation of the dice throw problem:

#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     { 
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return _____________;
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be added to complete the above code?

Question 21 of 50

22. What are the values of Catalan numbers for n = 0, 1, 2, 3, 4 and 5?

Question 22 of 50

23. A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?

Question 23 of 50

24. What is the worst case time complexity of randomized quicksort?

Question 24 of 50

25. In divide and conquer, the time is taken for merging the subproblems is?

Question 25 of 50

26. Fill in the blank to complete the code.

#include<stdio.h>
int main()
{
      int coins[10]={1,3,4},lookup[100000];
      int i,j,tmp,num_coins = 3,sum=100;
      lookup[0]=0;
      for(i = 1; i <= sum; i++)
      {
	   int min_coins = i;
	   for(j = 0;j < num_coins; j++)
	   {
	        tmp = i - coins[j];
	        if(tmp < 0)
	         continue;
	        if(lookup[tmp] < min_coins)
	       ______________;
	   }
	   lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

Question 26 of 50

27. How many elements can be sorted in O(logn) time using Heap sort?

Question 27 of 50

28. What will be the chromatic index for a complete graph having n vertices (consider n to be an odd number)?

Question 28 of 50

29. Who along with Samuel Morse developed Morse code?

Question 29 of 50

30. The result of the fractional knapsack is greater than or equal to 0/1 knapsack.

Question 30 of 50

31. What will be the ciphered text corresponding to “ALGORITHM” if bifid cipher is used for encryption with key as “KEY” with a period as 5?

Question 31 of 50

32. Which of the following cipher uses polybius square?

Question 32 of 50

33. What is the best case complexity of selection sort?

Question 33 of 50

34. Jump search algorithm requires which of the following condition to be true?

Question 34 of 50

35. What is the output of the following program?

#include<stdio.h>
int main()
{
      int coins[10]={1,3,4},lookup[100];
      int i,j,tmp,num_coins = 3,sum=10;
      lookup[0]=0;
      for(i=1;i<=sum;i++)
      {
	    int min_coins = i;
	    for(j=0;j<num_coins;j++)
	    {
	         tmp=i-coins[j];
	         if(tmp<0)
	          continue;
	         if(lookup[tmp] < min_coins)
		 min_coins=lookup[tmp];
	    }
	    lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

Question 35 of 50

36. What is the space complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

#include<stdio.h>
int main()
{
     int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	  tmp_max=0;
	  for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	  {
	       tmp_max +=arr[sub_arr_idx];
	       if(tmp_max > cur_max)
		 _____________;
	  }
     }
     printf("%d",cur_max);
     return 0;
}

Question 36 of 50

37. What is the following expression, lcm (a, gcd (a, b)) equal to?

Question 37 of 50

38. What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?

Question 38 of 50

39. What is the auxiliary space requirement of cycle sort?

Question 39 of 50

40. Consider a reference string 1,2,3,2,1,5,2,1,6,2,5,6,3,1,3,6,1,2,4,3 of frame size 3. Calculate the number of page faults using optimal page replacement algorithm.
The number of page faults using optimal page replacement algorithm is 14

Question 40 of 50

41. What is the general formula for finding the shortest distance between two parallel lines given by ax+by+c1=0 and ax+by+c2=0?

Question 41 of 50

42. Dijkstra's Algorithm cannot be applied on ______________

Question 42 of 50

43. What is the space complexity of the following dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?

#include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
      if(a > b)
        return a;
      return b;
}
int lps(char *str1)
{
      int i,j,len;
      len = strlen(str1);
      char str2[len + 1];
      strcpy(str2, str1);
      strrev(str2);
      int arr[len + 1][len + 1];
      for(i = 0; i <= len; i++)
          arr[i][0] = 0;
      for(i = 0; i <= len; i++)
          arr[0][i] = 0;
      for(i = 1; i <= len; i++)
      {
          for(j = 1; j <= len; j++)
          {
               if(str1[i-1] == str2[j - 1])
                   arr[i][j] = 1 + arr[i - 1][j - 1];
               else
                   arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);
          }
      }
      return arr[len][len];
}
int main()
{
     char str1[] = "ababcdabba";
     int ans = lps(str1);
     printf("%d",ans);
     return 0;
}

Question 43 of 50

44. What is the space complexity of quick search algorithm?

Question 44 of 50

45. What is the auxiliary space complexity of bead sort?

Question 45 of 50

46. Flooding algorithm shouldn’t be used if only a single destination needs the packet.

Question 46 of 50

47. Which of the following is the most commonly used data structure for implementing Dijkstra's Algorithm?

Question 47 of 50

48. Which of the following cipher is a special case of affine cipher?

Question 48 of 50

49. Which of the following is true?

Question 49 of 50

50. Which of the following gives the sum of the first n natural numbers?

Question 50 of 50


 

Topic wise Test Quizzes on Design & Analysis of Algorithms

Design & Analysis of Algorithms tests, quizzes, and exams are great ways to learn and test your Design & Analysis of Algorithms skills. Whether you’re a beginner or experienced, challenge and boost your confidence with our engaging online quizzes on Searching, Sorting, String Matching, Graph Search, Minimum Spanning Tree, Shortest Path, Flow Network, Minimum Cut, Graph Coloring, Bipartite Graph, Recursion, Greedy Algorithms, Backtracking, Dynamic Programming, Cryptography, NP Complete Problems, Page Replacement Algorithm, Quickselect Algorithm and Square Root Decomposition. Start the Design & Analysis of Algorithms online test now!

Searching Quiz

Sorting Quiz

String Matching Quiz

Number Theory Quiz

Computational Geometry Quiz

Graph Search Quiz

Minimum Spanning Tree Quiz

Shortest Path Quiz

Flow Network Quiz

Matching Quiz

Minimum Cut Quiz

Graph Coloring Quiz

Bipartite Graph Quiz

Recursion Quiz

Greedy Algorithms Quiz

Backtracking Quiz

Dynamic Programming Quiz

Cryptography Quiz

NP Complete Problems Quiz

Page Replacement Algorithm Quiz

Topological Sort Quiz

Quickselect Algorithm Quiz

Square Root Decomposition Quiz



Design and Analysis of Algorithms Certification Test

Design and Analysis of Algorithms Certification Test is a free certification exam. However, you need to score an A grade in each of the "Certification Level Tests 1 to 10" to be eligible to take part in this certification test. So, take all the "10 Tests" starting from Certification Level 1 upto Level 10, before taking the final Certification test.


Level 1 to 10 Tests:
Total Questions: 25, Total Time: 30 min, Correct Answer: 2 points, Wrong Answer: -1 point

Certification Test:
Total Questions: 50, Total Time: 1 hour, Correct Answer: 2 points, Wrong Answer: -1 point

Design and Analysis of Algorithms Internship Test

If you scored either Grade A* or Grade A in our Design and Analysis of Algorithms Internship Test, then you can apply for Internship at Sanfoundry in Design and Analysis of Algorithms.


Total Questions: 50, Total Time: 1 hour, Correct Answer: 2 points, Wrong Answer: -1 point

Design and Analysis of Algorithms Job Test

It is designed to test and improve your skills for a successful career, as well as to apply for jobs.


Total Questions: 50, Total Time: 1 hour, Correct Answer: 2 points, Wrong Answer: -1 point

Note: Before you get started on these series of online tests, you should practice our collection of 1000 MCQs on Design and Analysis of Algorithms .

Sanfoundry Scoring & Grading System

Sanfoundry tests and quizzes are designed to provide a real-time online exam experience. Here is what you need to know about them.

  • Scoring System: You get 2 points for each correct answer but lose 1 point for every wrong answer.
  • Grading System: Your grade depends on your final score and can be one of the following:

    • Grade A* - Genius (100%)
    • Grade A - Excellent (80% to 99%)
    • Grade B - Good (60% to 80%)
    • Grade C - Average (40% to 60%)
    • Grade D - Poor (0% to 40%)
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.