{"id":13760,"date":"2013-02-04T11:12:15","date_gmt":"2013-02-04T05:42:15","guid":{"rendered":"http:\/\/www.kopykitab.com\/blog\/?p=13760"},"modified":"2021-08-17T11:07:08","modified_gmt":"2021-08-17T05:37:08","slug":"gtu-exam-paper-designer-and-analysis-of-algorithms-june-2012","status":"publish","type":"post","link":"https:\/\/www.kopykitab.com\/blog\/gtu-exam-paper-designer-and-analysis-of-algorithms-june-2012\/","title":{"rendered":"GTU Exam Paper Designer and Analysis of Algorithms June 2012"},"content":{"rendered":"

GTU Exam Paper Designer and Analysis of Algorithms June 2012<\/p>\n

GUJARAT TECHNOLOGICAL UNIVERSITY<\/strong><\/p>\n

BE- Vth<\/sup> SEMESTER-EXAMINATION – MAY\/JUNE – 2012<\/strong><\/p>\n

Subject code: 150703<\/strong><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Subject Name: Design and Analysis of Algorithms<\/strong><\/p>\n

\n

Total Marks: 70<\/p>\n

Instructions:<\/p>\n

    \n
  1. Attempt all questions.<\/li>\n
  2. Make suitable assumptions wherever necessary.<\/li>\n
  3. Figures to the right indicate full marks.<\/li>\n<\/ol>\n

    Q.1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Answer the following.<\/p>\n

    (i)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Compare Iterative and Recursive algorithm to find out Fibonacci series.<\/p>\n

    Explain why analysis of algorithms is important? Explain: Worst Case, Best Case<\/p>\n

    (ii)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>& Average Case Complexity.<\/p>\n

    (iii)\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Explain characteristics of Greedy Algorithm.<\/p>\n

    (iv)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>What is Principle of Optimality? Explain its use in Dynamic Programming Method.<\/p>\n

    Q.2 (a) Write a program\/algorithm of Selection Sort Method. What is Complexity of the method?<\/p>\n

    (b) Explain Quick Sort Method with example.<\/p>\n

    OR<\/p>\n

    (b) What is Divide and Conquer Technique? Give the use of it for Binary Searching Method.<\/p>\n

    Q.3 (a) Define Minimal Spanning Tree(MST). Explain Krushkal\u2019s Algorithm to find MST with example.<\/p>\n

    (b)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Solve Making Change problem using Dynamic Programming. (denominations: d1=1,d2=4,d3=6). Give your answer for making change of Rs. 8.<\/p>\n

    OR<\/p>\n

    Q.3 (a) Explain Dijkstra\u2019s algorithm to find minimum distance of all nodes from a given node. (Greedy algorithm)<\/p>\n

    (b)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Solve the following Knapsack Problem using Dynamic Method. Write the equation for solving above problem.<\/p>\n

    n = 5, W = 100<\/p>\n\n\n\n\n\n
    Object<\/td>\n\u00a01<\/td>\n\n

    2<\/p>\n<\/td>\n

    		\n

    3<\/p>\n<\/td>\n

    		\n

    4<\/p>\n<\/td>\n

    		\n

    5<\/p>\n<\/td>\n<\/tr>\n

    Weight (w) \u00a010<\/td>\n20<\/td>\n\n

    30<\/p>\n<\/td>\n

    		40<\/td>\n\n

    50<\/p>\n<\/td>\n<\/tr>\n

    Value (v)<\/td>\n\u00a020<\/td>\n30<\/td>\n\n

    66<\/p>\n<\/td>\n

    		40<\/td>\n\n

    60<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Q.4 (a) Explain Backtracking Method. What is N-Queens Problem? Give solution of 4- Queens Problem using Backtracking Method.<\/p>\n

    (b) Explain Breadth First Traversal Method for Graph with algorithm.<\/p>\n

    OR<\/p>\n

    Q.4 (a) Explain Chained Matrix Multiplication with example.<\/p>\n

    (b)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Define: Acyclic Directed Graph, Articulation Point, Dense Graph, Sparse Graph.<\/p>\n

    (c)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Explain Min Max Principle.<\/p>\n

    Q.5 (a) Explain in Breif:<\/p>\n

    P Problem, NP Problem, Heap Tree, Travelling Salesman Problem (b) Explain finite automata for string matching.<\/p>\n

    OR<\/p>\n

    Q.5 (a) Explain Rabin- carp method for string matching and also give the algorithm.<\/p>\n

    (b)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>What is Recursion? Give the implementation of Tower of Hanoi problem using Recursion.<\/p>\n

    (c)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>Define :Big Oh, Big Omega and Big Theta Notation.<\/p>\n","protected":false},"excerpt":{"rendered":"

    GTU Exam Paper Designer and Analysis of Algorithms June 2012 GUJARAT TECHNOLOGICAL UNIVERSITY BE- Vth SEMESTER-EXAMINATION – MAY\/JUNE – 2012 Subject code: 150703 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Subject Name: Design and Analysis of Algorithms Total Marks: 70 Instructions: Attempt all questions. Make suitable assumptions wherever necessary. Figures to the right indicate full marks. Q.1\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Answer the following. (i)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":""},"categories":[120,1],"tags":[1858,2962],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts\/13760"}],"collection":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/comments?post=13760"}],"version-history":[{"count":1,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts\/13760\/revisions"}],"predecessor-version":[{"id":115903,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/posts\/13760\/revisions\/115903"}],"wp:attachment":[{"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/media?parent=13760"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/categories?post=13760"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kopykitab.com\/blog\/wp-json\/wp\/v2\/tags?post=13760"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}