Scribd
Upload
6 views55 pages

Algorithms

The document discusses various concepts related to algorithm analysis, including Big O notation, time complexity, and growth rates of functions. It presents multiple-choice questions and scenarios to evaluate understanding of these concepts, such as sorting algorithms, recursive functions, and asymptotic behavior. The content is technical and aimed at individuals studying computer science or algorithm design.

Uploaded by

Saprativ Mondal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
6 views55 pages

Algorithms

The document discusses various concepts related to algorithm analysis, including Big O notation, time complexity, and growth rates of functions. It presents multiple-choice questions and scenarios to evaluate understanding of these concepts, such as sorting algorithms, recursive functions, and asymptotic behavior. The content is technical and aimed at individuals studying computer science or algorithm design.

Uploaded by

Saprativ Mondal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
SEL Tor EXIF The concept of order (Big 0) s important because (a) Itcan be used to decide the best algorithm that solves a given problem (©) Itdetermines the maximum size of a problem that can be solved in a given amount of time (C) It is the lower bound of the growth rate of algorithm (2) Both (@) and (b) above EER Each ot the function 2° and rioen has a growth Fate .... than that of any polynomial. (@) Greater (b) Less: (©) Equalto (9) Uncertain EEE 4 machine needs a minimum Of 100 sec to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately (a) 50.2sec (b) 67sec (©) 72.7sec (d) 11.2sec EERE suppose f, 9, h, kN» N. ' f= O(h) and g = 0(k), then @ f+9=0(h+k (©) fg = (hk) (©) Both (a) and (b) above (9) None of the above TER concider the following two functions: oie fr? for © 100 Which of the following is tue? (2) 9\(n)is O(g, (ny) 6) 9 © gms O(n @) Gna” 147) is O(n) LEE Consicer the following tung fn) = 3an% a(n) = p¥logen tions: in ynctions FEED Consider the following two! Algorithms An) = nt Which of the followin, (2) An)is OCF (nm) (b) A(n)is O(F(n)) (©) g(r) isnot o(F(n)) (A) Finis a(g(n)) 1 o7 ey 19 is true? a(n) oe ae = a(n?) Which of the following is true? (@) 1iscorrect (b) 2is correct (©) 1 and 2 both are correct (@) None of these {(n) = O(g(n)) If and only if = €) a(m)=o1Km) ) ofe)=wl (©) g(n)=2(K(n)) (a) Noneot EEN Wich one of the following isu? 1. an= O(n?) (small oh) a20 2. ar? = O(n?) (big 0) a> 3. ar? # O(n?) (small oh) 27° (2) Only 1 and 2 are correct (b) Only 1 is correct (c) 1 and3 are correct only (@) Allare correct fin) = mitosn< 10! rP, otherwis? = n,itosn< a 12 +50 omer Which of the following is/@" 1. Kn)is on’) - g(n)is O(n) -)) (tin) issameas + gin)is ovr) 1.2088 ) = 0(g(N)) tand only it p i gin) = 2¢F(n)) to) a¢n)=ecttn)) ie) gn) = 2(f(n)) and g(n) = w(f(n)) o None of these Using the standard algorithm, what is the time required to determine that a number nis prime? (@ Constanttime — (b) Quadratic time (©) Logarithmic time (d) Linear time o Consider the following functions: fin) = 2” gn) =n! Hin) = rieon Which of the following statements about the asymptotic behaviour of f(n), a(n) and h(n) is true? (@) f(n) = O(g(n)); a(n) = OfA(n)) (0) f(r) = Q((n)); g(n) = O(A(n)) (©) ln) = O(f(n)); h(n) = O(f(n)) (9) A(n) = O(F(n)); g(n) = Qn) Ey bet fn) = r? tog mand 9(n) = rXlog 1)" be two Positive functions of n. Which of the following statements is correct? (2) {n) = O(9{n)) and g(r) # O(n) (©) 9(n) = O(f(n)) and f(r) # O(g(n)) (©) f(a) # O(g{(n)) and a(n) #O(A(n) (9) {n)=O(g(n)) and g(n) = O(f(n)) Match the following groups: Group-I (n > 0) Group-II A. 8n+ 4n? + Sniogn 1. 01) B n+logn+logiogn 2, Ologn) . 104+n+nlogn+logn 3, O(n) D. 10+ 10000 + 100000 4. O(nlogn) 5. O(r?) Codes: ABCD boa 409 5 4 3 4 6.34 ae M5 43 2 iorrestricted use of Goto is harmful, because it @) increase running time of programs. (©) makes debugging difficult (©) resuts in the compiler generating longer ™achine code, (@) increase memory requirement of programs. Algorithms 269 Consider the followit ing functi Void Aint ny 19 function: { It jk, m: for (i= 0; 1 < 100, 144) { for = 0; j< mn jes) { for (k= 0; ke kee) Brint%d", 4; } } Whats the worst case running time ofthe function ffor any positive value of 7? (@) (1) (©) O(n) (©) O(r?) () Or) FERED Consider the folowing segment of c code int j, m7; j=; while (< =n) The number of comparisons mode in the ‘execution of the loop for any n> Ois (@) flogri}+1— (&) n (©) [logan] (© [logn]+1 FERED whats time complexity of following code: int a=0; for (i = ( i < Mitt) for (= N; j> i; --) { azati+h } } (a) O(N) (b) O(Ns (log N) (c) O(N* Sqrt(N)) (a) Or?) Consider an array of nelement with sorted order, half the number Jement {appear more than halt the nu we what is the time complexity to count ‘the number of occurrences ot (@) Olog mes ©) an) (@) Mogleg 270 EEE] Fing the time complexity of the following ‘summation. Assume that k is a constant, k > 0 nay k fie (a) On) (b) OF) (©) Or) (@) None of these [EEE Consider the foliowing functions: 1. al 2. a, ais constant, a>0 3. 7 4. nk, kis a constant, k>0 5. Choose the correct statement which ranks all functions by order of growth. (a) 2<4<5<1<3 (bo) 4<2<3<5<1 (© 4<5<2<1<3 (@) 4<2<5<1<3 [EEE] wats time complexity of following code: inta=0, + while (7 > 0) { (a) O(N) (b) O(Sant(N)) (c) O(ni2) (d) O(log N) Consider the following recursive function: int F (int array [1], int n) { int S = 0; if(n $ =F (array, n- 1) if (array [n- 1] <0) S=S + 100; retum S; ) What is the worst case time complexity of the above function? (2) Or) (b) O(nlog n) (©) O(r?) (2) O(log n) What will be the worst case time complexity for the following code segment? int count = 0, N; Data Science & Artificial Intelligence : Practice Book for (i= 0; # temp); Ali+ 11 = AL: AL/] = temp; } } If the array is sorted the complexity is (a) O(n) {b) O(n?) (©) O(nlogn,n) (a) O(og,n) Consider the following function: Void func (int n) { int k=; inti=0; for(; i 1)q k>>=1; } } Whatis worst case time complexity of (a) Xn) (b) O(log) (©) OV?) (d) O(nlog n) thefuncton Algorithms 271 erst 5 guen two sorting algorithms A and 8 yo. Or 017199 n)and O{/?) respectively ine following statements: sider cee ‘A will sort any array faster than 1 gorithm B. onanaverage. algorithm A will sort a given 2 pray faster nan algorithm B. jrwe need 10 implement one of the two as the default sorting algorithm in a system, Tigorthm A wil always be preferable to aigorthm B. rch ofthe statements above are true? 4,2and3 e) 1and3 (e) 2and3 {6) None ofthe itn) = O(a(n)) for f, g are non-decreasing funcion, then fn) log,{Ar}9) = O(c") *fog,07), where C = power of f(n)is (@) Always true {b) Never (©) Sometimes true, sometimes not depending on fg. (6) Sometimes true, sometimes false depending onc. ‘Among the following asymptotic expression which of these functions grows slowest (as 4 function of n) asymptotically? @ (Jig nye” (©) (logn" ( @ 2 Inabove question if the array is in reverse sorted ‘Order then time complexities will be @) O(n) (©) O(nlog,n) or) (@) O(log,n) How many tir iny times i aanany tes the following loop runs for given for (int j = ; 2 i< =n; 1= powli, 2)) ' Print(“96", i); Arrange trefo Consider the following C function find (int n) (if (n< 2) then return: olse {sum =0; for (i= 1,154; (+4) “(8 for j= 1; 7S mitt) sum = sum +1 } } Assume that the division operation takes consiart time and “sum” is global variable. What 's he time complexity of “find ()"? (a) Or?) (b) @(r? log n) () nF) (d) None of these ‘What is time complexity of this code: int A(int) { if (n<=2)retum 1; else ; retum (4(vA) +n); (@) O(log loa(n)) () O(log n) (©) On) (@) O(log nlog n) What is relation between the asymptotic time complexities of fin) and on)? An) = 072" g(n)=e" (@ er=o(ne 2%) (b) = Hn" 2°) () v=a(nr2) a= a(n" 2") jlowing functions is increasing orcer of growth rate (with gin) following An) in your list itand only if An) = 1") vi 40°, n,m? PS (ey Vait0",n8, 207,188 (eo) n°8,08!3, ln, 27, 10” © J, NORA 88,088, 10" (a) None of these 272 sl Data Science & Artificial Consider the following code segment. Assume nto be a positive integer for (i= tric = mits){ for(j=tij<=mi+i) printt("Hi"); Let 7{n) represent the total running time of the above case segment. Specify which of the following statements are correct. @) Na=OrF) (b) Tn) = O(nlog n) (©) Tin) = O(r? log n) (@) Tn) = O(log n) Consider the equality 9 = X and the following 0 choices for X. 1. (rt) 2. O(r*) 3. on") 4. Q(r°) The equality above remains correct of X is replaced by: (@) Only (©) Only2 (0) 10r3or4 butnot 2 (@) 2013 or 4 but not 1 ZA inthe following C function, let n> m. int ged (n,m) { it(n%m= n=n% m, return ged (m, n); 0} return m; } How many recursive calls are made by this function? (a) (log,n) (b) Q(n) (c) @llog,log,n) (a) (vn) EEZEE Consider the following code segment of C-code: { for(int §= 1; 1< = 1; i++) { int p = powti, k) for (int /= 1; /< = p;/ ++) f } if some O(1) work Intelligence : Practice Book Calculate time complexity of a MRoe dove = time complexity will be Ode, The (a) O”/) (0) O(r#+1) (c) OW?) (BD) OA) [IE consider the following two functions f(n) = 1P, if 01 < 10,009 1?, otherwise (7) = n,if05n< 100 1? + 51, otherwise Which of the following is/are true? 1. fin)is O(r*) 2, g(nis Or?) 3. O(f(n)) is same as O(9(r)) 4. g(n)is Or?) (@) 3and4 (©) 1,2and4 (b) 1,2and3 (d) None ofthese ELEN Consicier the three functions fr) = 1? + n+ za {n) = 12r? + 34 and Mn) = 123n+4 Which of the following statements is/are tue? (@) An) =O(9(n)) — (b) g(r) = OfF{n) (©) Ar) = (h(n) (@)_A(n) = O(F(m)) ‘An algorithm is made up of two independent modules M, and M,, If order of M, is fn) and M, is g(n) then the order of algorithm is/are (a) max(f(n), g(r) (b) min(f(n), a(”)) (©) f(n) + g(r) (a) Kn)x gn) Consider the following pseudo code: sum = 0; for (= 0, i 4 4; otherwise The order of this algorithm is (@) Ollogn) (b) O(n) a) (a) Om) [BJ the recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is (@) Tn) =2T(n-2)42 (©) Min) =27(n-1) +n © Mim=2r[B ler () Tr) = 2710=1) +4 EEE] whats time complexity of Fecurrence equation Tr) = T(Vn) +1 (2) O(log n) (b) ofr?) (©) O(nlogiogn) (d) O(log log ny ie. -* wy Data Science & Artificial Intelligence : Practice Book FEY ove the recurrence n M-1(5-1)oro. (@) 8(nlog n) © (©) O(rPlogn) (gy ” fa Consider the following recurrent Tn =7 3 tar What wil be the solution of above eye (@) OA) ©) on) (c) O(n? log n) GO) Ores) [EET suppose oy=21(3) +n, T0\=T}=1 Which one of the following is FALSE? (@) T(n)=O(n?) —(b) T(n)=@{nlogn) (©) T(n)=2(0)—(d) T(r) = O(noga} [EEA The time complexity of the following C tinsex is (assume n> 0) int recursive (int 7) return (recursive (n- 1) + recursive(1~ ‘Ih ) (@) O(n) (©) Or?) : What is time complexity of the follow" eal recurrence relation and step to detv@™ Te) = Tin) +loaea? | (a) loglogn (b) 9 (©) (ogiogn? — ) # . FEY wat is the value of Mn) fr 9" relation m= 1(5)*2 ms! when nis power of2 (a) Alogn+1) ©) (c) logn+t @ What is complexity offllownd Tin) = VaTiA)+100" oe (@) enioglogn) (0) " © a” (@ ova” © ong) @ 02") tog” 2b" cal e complexity of T(n) (b) O(r? log n) (@) O(n log n) Frat is the time complexity of the following Hecurrence relation T(K) = 1(3)* 5} R? @ ow (b) Oo) (@) O(klog f) (a) O(log k) ¥ the following can be solved using Which of Mastertheorem? n),_0 fa) Tin)= (3) Toon (&) Tin)= as} logn © T=T(3}+¥09" (@) None of these We solve TOH problem recursively breaking the {ask in three sections, which of the following recurrence will accord will with the approach, that is shows correct order of work done on each recursive step. (@) Tn) = Tin-1) + 1+ Tn-1) Tin-1) + 17{n-1) +1 +Tn=1) + Kn-1) Tin=1) + T(n-1) +2 Ee Tuning time of an algorithm Tn), where nis input size, is given by following: Vet ra. [o(s)-a ifn>1 p ifn=1 Wher is "€ Pand gare constants, the order of algorithm @) © n (b) 1? What @) r lat is, Complexity of recurrence relation TK W-a1(3+«7).28 +10n-3 Algorithms xs (2) OW?) (6) O(nlog r) (b) Of?) (d) None of these Solve the recurrence relation and find complexity of it eae riv=1(F}50" (a) O(7*) (b) O(n) (©) OW) (d) O(P? log n) Let T(n) = Tin-1) + 3 Then T(n) is (@ @(1) (0) @tog") (©) @loglogn) — (A) {r) GEE] Which of the following function given by their recurrences grows the fastest asymptotically? @ Teo) =21 j} + 00r# ©) Tio)=17 § +107 © T= sor{ 3} o0tnear 2 Ged et m= Tn-+45 Tia) = 1; Then Tin) =? (a) OF) (b) O(nlog 7) (©) Oleg) (d) O(n? log n) [ESI wich recurrence relation satisfy the sequence: 2,3, 4, forn 34. (@) TIN) =2T(N-1)- TIN 2) () TIN) =2TIN-1) + TIN-2) () TN)=N+1 (d) None of these Ba w- (3) 4 then T(n) is equal to (a) (log, 7) (o) @(nlog,") (©) Or) @) a What is complexity of recurrence (nis a natural number) D)yin>2 Ti)= (sg) . 1 i ns2 (o) Or) s oa (a) O(nlog) 276 Data Science & Artificial Intel EEE] Let m, nbe positive integers. Define (m,n) as Q(m,n) =O,ifmen Q(m= n,n) +p,itmen Then Q(m, 3)is (a div b, gives the quotient when ais divided by b) (@) aconstant (©) px(mdiv3) (0) px(mmod 3) (@) 3xp [EES] The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is © M)=27(n-1)+1 BE wrctiscompioxty of recurrence relation Tin= M{ ge7} +278 +10n-5 (@) OW?) (©) O(n?) (©) Olnlogr) —_(d) None of these EEG] whats complexity of recurrence relation ro=r{F}( 3)" (2) Qnlogsn) ——(b)._O(nloglogyys n) (©) ArPloggsn) (6) nloges ) FEE] nat is complexity ofrecurrence equation Tin) = sayt(2) + ( 3) + sqrt (n) @) O(rtlog n+1)) (b) @(rP(log n+ 1)) (©) Wrllogn+4) (d) e(n*(log n + 1)) FEY 1)= Tr) + THogn) +t; 22 When you solve the above recurrence relation Using recursive tee method, whats the maximum height ofthe tree obtained? @) Hlogiogn) —(o) (log r) (©) an) (@) (7) EEE] Fina the worst case time complexity of the following recurrence relations: T(n)= T(h) + Tlogs r) +0 where cis a. Constant and 72) = 4 (@) Q(log, log, n) —(b) Qllog, n) (0) 2(n) (d) Q(nlog, n) ees @ : Practice Book Consider the folowing recur Tin) = 47/2 rT la on ut } ean 19 “ Select the correct stat (@) A sized problem is civiggy * 82mg odio «e problems of 3 size each (b) A msized problem is divided j s 0 2 ay problems of £ size each (6) Tin) =O(rF (log ny?) (a) TA) =O, a4 EAC ICCE ones EEE] Which of the folowing sorting methods so Given set of items thts areadyin sarees or in reverse sorted order with equal (@) Heapsort (0) Quick sot (6) Insertion sort (4) Selection sort EEE] Randomized quicksort is an extension of uioksort where the pivot is chosen rrdon What is the worst case compleiy of soma numbers using randomized quicksor? (a) O(n) (b) (nlogn) (©) O(n") (a) O(n!) EEE] In auick sort for sorting of n numbers, he 75? greatest element is selected as pivatusing 0(?) time complexity algorithm than whatisthe wast case time complexity of quick sor. (a) ov?) (b) O{niogr) (©) O(n?) (@) OW”) ‘A min-max heap has the following prope: * ‘almost complete binary tree where each roo an even level nthe tre i ss tan ete descendants and each of the node atanosd 8 in the tree is greater than all ofits cele Whats the worst case time complex nt minimum element" and bee ‘slement" on above data struct! (oo?! (a) O(logn) and oflogn) (b) aaa (©) O(logn) ando(n) — (d) (0) ERsY Algorithms 277 ‘Consider the following cases for quick sort to sort an array of n element a[0... n~ 1}. 4. Choosing the pivot element randomly from the given array. 2. Choosing median element as pivot. $. Choosing middle element as pivot. For which of the above cases quick sort always ives O(n log r) tine complexity? (@) 1and3 (b) 2and3 (©) tand2 (d) None of these Consider the following sorting algorithms: A. Merge sort B. Quick sor C. Heap sort D. Insertion sort Find the correct pair such that their best, average and worst case time complexities are same. (Assume that all elements are distinct) @asB (b) AC () AD (d) None of these For merging two sorted lists of sizes m and n into a sorted list of size m + n. Find out the time ‘complexity of this merging process. @) O(m) (b) Of”) (©) O(m+n) (d) O(log(m) + log(n)) Given nintegers in the range of Oto kwe want to preprocess the input in such away that to any ‘query about how many of the n-integers fall in the range a .... bin 0(1), Then what will be the processes time? (@ O(n+h) ©) O17) (©) O(log n) (@) 0W (Quick sort gives O(nlog n) worst case performance if the pivot is selected as: (@) First element of array (o) Median of frst, last and middle elements (c) Arithmetic mean of the elements: (6) None of above A sorting technique is called stable if {a) It takes O(n log n) time (b) It maintain the relative order of occurrence of non-distinct elements, (0) ttuses divide and conquer paradigm. (A) Ittakes 0(n) space. [ELE suppose there are 4 sorted ins of & olrments each. If we merge these lists into a single sorted list of n elements, how many key comparisons fare needed in the worst case using an algorithm? 6 7 8,23 ya (@) gn &) 77-3 8 9 (© Ga-3 (6) 49-3 FRE A ist of nstrings, each of length n,is sorted into lexicographic order using the merge sort algorithm, ‘The worst case running time of this computation is (a) O(nlog n) (b) O(n? log n) (©) O(rF +logn) (4) Ofr*) [iii consider an array containing 'n' elements. The ‘elements present in an array are in arithmetic progression, but one element is missing in that ‘order. What is the time complexing to find the position of the missing element using divide and conquer (by binary search), (@) On) (b) O(log n) (©) OF) (0) O(nlog n) Gow many term will be computed to determine the value of "°C, using a divide and conquer algorithms? |What is time complexity to find the K*” largest element in amin heap? (a) O(n) (©) O(log n) {c) O{nlog n) () oF) XE Given two sorted list of size ‘m’ and ‘n respectively, The number of comparisons needed in the worst case by the merge sort algorithm, willbe (a) mxn (0) maximum of m, a (€) minimum of m, n(d)_m+a-1 [EEE consider an online sorting aigorthm which is based on insertion sort, At some point of time, we have nelaments which are already in sorted ‘order, Now knew elements arrive and they need tobe added to the list using the above mentioned online sorting algorithm. The worst-case time ‘complexity to get the new sorted list with (+ k) elements is 278 Data Science & Artificial Intelligence : P Note: Initial elements are already sorted. (a) O(r{n+k)) (b) O((n + KY) (©) O(Mn+ k) (d) None of these [EXE] Given “log 1” sorted list each of sin“ os "what is time required to merge them into one single list? (@) O{nlogn) (b) O(nlog log n) (©) O(nlog nlog n) @) on) FEE“ strings each of length “n’ are given them, ‘what is time taken to sort them, 2-way merge? (@) On) (b) O(nlog n) (©) O(r2logn) —(d)- Ollogn) [ERED Given an array A of elements: 80, 70, §5, 90, 71, 72, 73, 77, 52, 50 What will be the output after 1 pass of 3 way merge sort? (@) 70, 80, 55, 90, 71, 72, 73, 77, 50, 52 (b) 55, 70, 80, 71, 72, 90, 52, 73, 50, 77 (0) 50, 52, 85, 70, 71, 72, 73, 77, 80, 90 (d) 55, 70, 80, 71, 72, 90, 52, 73, 77, 50 PEEP] What is the worst case time complexity of Bubble Sort? (@) Otlogn) (6) O(n) (c) O{nlogn) (A) O(n?) Consider an array having the following elements 20, 50, 12, 45, 19, 29, 74, 37 Then, total number of comparisons required to sort the array using merge sort? [EEEZ] which of the following represent correct recurrence for worst case of Binary search with n element. (@) n= 1 zi +0(n) ) mn =27(5) +0(1) (c) n=21(3) +n) (8) T= (3) +0(1) Ge wrich Of the following algortp, m8 moog EID virich otro ftom By x4 9 S0MINg at. ~ 700 Im, lowest worst-case complests my (@) Merge sort ©) Buty . (©) Quick sort (O Setcan lection see comparison-based algorithn? (a) Heap sort (0) Quick son (6) Radix sort (0) Topological ne [bid Given a binary-max heap. the stored in an array as 25, 14,16, 13 1g 4° What is the content of the aray ater e a, operations? (a) 14,13,8,12,10 (6) 14,12,13103 (©) 14,13,12.8,10 (@) 14,13,12108 Alist has n-strings where each sting stan 1. Using divide and conquer approach, wr the worst case running time (tightest ueser bound) to find the first string? Note: First string is a string which acess when all sings are sorted into the lexcogactea order. (2) O(r?) (©) On) (c) Ofniog n) (A) O(log) Given a sequence of nintegersin the cre 28 7, 6, 5, 4, 3, 2, 1, 0, after which teraten. °° resulting sequence would be 1. 2, 345.878 9, Of you apply insertion son? __* t@2 ERED in the standard merge sort algontman2 5 ress size n, what is the maximum numoes item can be compared? @2 (©) fog (c) n-1 (d@) nieg® ideo [ERED Assume that ne algonthms cons ne the input sequences in ascend ® mp input is already in ascending order Wh following are TRUE? 1. Quick sort runs in der) te I. Bubble sort runs in o(er) tin? I, Merge sort runs in @¢0) me IV. Ingertion sort eunsin @¢a)tin® (@) Land lt only (b) | and Ill only (©) Iland IV only (d) Land IV only sro on array oF gers and @ funeton assur? & vax) ve" " Ja ifind ane ee right element f any) mati the worst case time complexity for Max() aninput are oto") (0) On) fone (a) O() an array consisting of the following in unsorted order (placed randomly), sjement whieh is higher than its. y? consider ‘elements put 60 as first element 60, 80, 1, 95, 7, 12, 35, 90, 55 ‘Quick sort partition algorithm is applied by ¢hoosing first element as pivot element. How many total number of arrangements of array integers is possible preserving the effect of first pass of partition algorithm IWhich one of the following does not represent the array if bubble sort to sort the elements in ascending order is run after one iteration @ 1,2,5,7,8.6,4,39 ©) 3,2,5,9,8,6,4, 1,7 © 1,2,5,6,7,8,4,3,9 (@) None of the above JAmachine needs a minimum of 100 sec to sort 1000 names by quick sort. The minimum time ‘needed to sort 100 names will be approximately (@) 60.2sec (b) 6.7 sec © 72.7 sec (d) 11.2sec Which ofthe following can make for an improved version of bubble sort? (@) Traverse the array left to right during old Passes and right to left during even passes, in bubble sort {) Divide the array into smaller arrays apply Quick sort on each of the small arrays and 5 oy Me bubble sort on the entire array. sary he sdsresees to be swapped in a array and make all the swaps at In qui * Sort for sorting elements, the (a)" Smallest ih tmp ees is selected as pivot using an Plo Gatthm. What is the worst case time ty of the quick sort? Algorithms > (a) Or) (c) or?) [ERED 1h usual 87?) implormantation of insertion Sort to sort an array uss linear saarch to identity he position where an element is to be inserted inte the already sorted part of the array If instead. wo use binary search to identify the position, the worst case running time will (2) remain a(r?) (b) become @(n (log n}?) (c) become @(nlog n) (d) become @n) Match List-1 (Divide Conquer) with List-II (Recurrence Relation (Worst-Case) and select the correct answer using the codes given below the lists: List-I (b) @tntog 0 (A) O17 gr) List-lI n\ Tin = arf 3+e mi=1(5}* ©. Quicksot 3. Tin)= Mn-1)+-1 li 4. mo) =27(3 | +kn A. Binary search B. Mergesot 2. D. Max Min Codes A @1 &) 2 1 (2 4 ‘modified version of merge sortis devised with ‘a modified merge method is used where the merge takes 0(/#) time to merge lists that sums upto siz nthe te complexity for such a version ‘of merge sort is (a) O(nlog n) (o) 7) {c) (Flog 9) (@) own) What is worst case ume complexity, to deiete an middie element | frommun heap of ndistinctelement? ooo oonso aan Do 280 Data Science & Artificial Intelligence : Practice Book EERE «> e-commerce site on search for a particular key word returns the search results in order 10 popularity by default also the user is allowed to sort by price (low to high) or (high to low) however if two or more products are of the same price then among the same price products should be presented to the user in the same order of popularity. Which of the following sorting algorithm cannot be used for such a scenario? (@) Insertion sort (b) Bubble sort (©) Quicksort —_(d) None of above Which of one the following is false? (@) Heap sortis an inplace algorithm. (0) Heap sort has O(n log n) average case time complexity. (c) Heap sort is a stable sort. (@) Heap sort is 2 comparison-based sorting algorithm, [ERED tre essential part of heap sortis construction of max-heap. Consider the tree shown below, the node 24 violates the max-heap property. Once heapify procedure is applied to it, which position will it be in? ‘The asymptotic running time of Randomized QuickSort on arrays of length n. (@) in expectation is 6(nlog n) (0) In expectation is (77. (0) Inthe worst case is @(n log n) (d) Inthe worst case (7). Which of the folowing statement(s) is/are correct? (@) Consider an array A in which upto some index I, integers are stored and after that NULL values are stored, Let the size of array be n, Then time taken to find the value I would be O(log 7). (b) Consider an array A in which upto some index I, Real numbers are stored and after that NULL values are stored, Let the size of array be n, Then time taken I would be O(iog n). (c)_ Consider an array A in whic I, integers are stored and ent values are stored. Let he sizeof an We Then time taken to find the value O(n), (d) Consider an array Ain which I, Real numbers are sii Sar a NULL values are stored. Letthe szectan., be n, Then time taken to find the va would be O(n). s ‘ond te Whi (ity Which ofthe following sorting algorithms) os not have a worst case running time of ofr (@ Insertion sort (b) Mergesor (©) Quicksort (4) Bubble sort A sort method is said to be stable ifthe rete order of keys is the same after the sortasitaas before the sort. In which ofthe folowing pas both sorting algorithms are stable? (@) Quick sort and insertion sot (b) Insertion sort and Bubble sort (©) Quick sort and Heap sort (d) Quick sort and Bubble sort [EREEIA binary search tree contains the vaes-12 3, 4, 5, 6, 7 and 8. The tree is traversed 0 preorder and the values are printed out. Which ofthe following sequences isa vad oss? (a) 53124786 (bo) 53126497 (©) 53241678 (a) 53124768 Bo Giventwo sorted istofsize’m' and’ especie ‘The number of comparisons inthe worst case by the merge sor algorithm wilDe (a) mxn () maximum of m, (c) minimum of m,n (d) m+n-1 a [ERIE For merging two sorted lists of ee fo into a sorted list of size m+ ™¥° comparisons of (a) Om) (o) on) (©) O(m+n) (a) flog + 9 time a ‘The average successful search e binary search on a sorted ray roller (@ 26 (0) 27 (oc) 28 @ 29 Algorithms 281 mumber of swapping needed to sort the 9, 31,5, 13 inascending order, fAsoring technique is called stable it ig) takes O(7109 n) time fp) ltmaintains the relative order of occurrence ofnon-distinct elements 4 Ituses divide and conquer paradigm {9) Ittakes O(n) space Iconsider the following scenario during insertion Isort when the array looks like the following: {25, 75, 95, 125, 80, 5, 10} The number of comparisons that it will further take forthe array to be completely sorted are The average number of comparisons performed by the merge sort algorithm, in merging two Sorted lists of length 2 is 8 @3 o¢ 1 an r Os [Asorting technique that guarantees, that records with the same primary key ocours in the same ‘order in the sorted list as in the original unsorted list is said to be (2) Stable ©) Edema A list of nstrings, each of length n, is sorted into Kexicopraphic order using the merge sort gorithm. The worst case running time of this ‘Computation is 18) O(nI09 n) (©) O(77 + 10g n) (b) Consistent (d) Linear (b) O(n? log n) (A) O(n?) The em ase running times of Insertion sort, Scat ahd Quick son, respectively, are ) ae, 1), (nog n), and @(r?) ie Boe 9(r7), and @(nlog n) 6 } &knlog r), and @{n tog m) ; } (nog n), and @(r?) a F Bhi nY of comparison based sorting (b) a(n) (a) An An) LEI 41 aigoritnm is made up of 2 modules M, and M,,Iftime complexity of modules M, and M, are Hn) and g{n) respectively, the time complexity of the algorithm is (a) min (h(n), Kn) (b) max (h(n), Xn) (©) Ain) + Xn) (d) Ain) * Xn) [EXE suppose that the splits at every level of quicksort are in the proportion (1 - a) toa, where 0 < as ibe 3 iS@constant. The minimum depth of aleafin the recursion tree is approximately given by __ign _Ig(t-a) @) ota) 2) olan ot age © -ga © -Ba [ERE] there are nintegers to sort, each integer nas ¢ digits and each digit is in the set (1, 2,... Ml. radix sort can sort the numbers in (@) O(dnk) (b) O(dn*) (c) O((d + nk) (@) O(a(n+k)) Which of the following algorithms sort nintegers, having the range 0 to (r?— 1), in ascending order in O(n) time? (@) Selection sort (b) Bubble sort (©) Radix sort (d) Insertion sort A priority queue is implemented as a max-heap. Initially, it has five elements. The level order traversal of the heap is as follows. 20, 18, 15, 13, 12 ‘Two new elements ‘10° and ‘17" are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is: (a) 20, 18, 17, 15, 13, 12, 10 (b) 20, 18, 17, 12, 13, 10, 15 (0) 20, 18, 17, 10, 12, 13, 15 (A) 20, 18, 17, 13, 12, 10, 18 EXET the array A contains the items 10, 4, 7, 23. 67. 12 and § in that order, what will be the resultant array A after third pass of insertion sort? (a) 67, 12, 10, 5, 4, 7,29 (b) 4,7, 10, 23, 67, 12,5 (©) 4,5, 7,67, 10, 12,23 (6) 10, 7, 4, 67, 23. 128 oo OO Pad [ERE Sige shores: path problem canbe implemented by Greedy algorthms using (@) Singly linked list (b) Min Heap (©) AVitree (@) Allof the above FEE kruska's algorithm tor finding a minimum spanning tree of a weighted graph G with vertices and medges has the ime complexity of (2) OF) (b) (mn) (©) Om+n) () O(miogn) PERE fo impterent Dixsira's shortest path algorithm ‘on unweighted graphs so that it runs in linear time, then data structure to be used is (@) Que (o) Stack (©) Heap (@) Bree EE Fine tne running time of Dijkstra's algorithm on complete graph of n-vertices. (a) O(7) (bo) Or?) (© O(r?ogn) (0): OCF?) ‘Consider the following steps: S,; Characterize the structure of an optimal solution. s,: Compute the value of an optimal solution in bottom-up fashion. Which of the following step(s) is/are common to both dyneric programming and Greedy algorthm? (@) Onlys, (b) Only 5, (c) Both $, and S, (d) Neither S, or S, FER the number of spanning trees for a complete ‘graph with seven vertices is @ 2 () 7% ©) (d) 22%5 ‘The number of spanning tree possible for the following graph is EEE] Let we the minimum weight among all edge weights in an undirected connected graph, Let ¢ be a specific edge of weight w. Which of the following is FALSE? Data Science & Artificial Intelligenc : Practice Book mane (a) There isa minimum spanning tee a e Setaing (b) Hfeisnotina minimum spanning in the cycle formed by adding tee edges have the same weight,” (6) Every minimum spanning re has of weight w. Ney (d) eispresentin every minimum sparring, 8 |suppose that minimum spanning tree oy, following edge weighted graph containg a edges with weights x, yand z 7 What is the maximum value of x + y+ 2 EXE! Kruskar’s algorithm is used for finding minimum spanning tree of a weighted graph G with n vertices and m edges and edge wens are already given in a sorted list, then, what wi be the time complexity to compute the minimum cost spanning tree given that union and find operations amortized O(1)? (@) O(mlog n) (b) Or) (c) Om) () O(nlogm) [ERE consider a graph ‘G' given below nt 1.2.9.456789 If edges are having weig! weigtt and 10, Then maximum possible minimum weight spanning tree of joan [EEE Consider a weighted complete 0 [V4y Vy on Val SUCH that the weight (vp v) is 2|4~ J]. The weight of @ spanning tree of G is (@) n-1 (o) 2n-2 @ # °( nerotoning eaten rer weighted graph and any Mo sa wed 1, Bellman-Ford algorithm rice’ § ° raring at Sl always return a shortest path s rot : tion of the Bellman-Ford x the terminal algorithm, even" le, acorrect i graph has negative weight shortest path is found for a hortest path is well-defined. vyerexrorwnich s sprich of the above statements are true? @ only! wo ony lt (6) Both | and I! {@) None ofthese et k, be the complete graph on “nr? vertices in-1 iebelied{1,2, 7} with m= aod edges. What isthe number of spanning trees of K,? m oy (b) ar" m? (a mt [Consider a weight complete graph Gonthe vertex set Vj, Vpn» Vq} Such that the weight of edge (\, Vpis 4-4. The weight ‘of minimum cost spanning tree of Gis: ) 4n? (¢) 4n-4 0 (d) 2n-2 Consider the following statements: §,:Ina connected undirected graph G= (VE) with distinct edge costs, the cheapest edge F peers to every minimum spanning tree. a poneeied undirected graph G= (V, E) aes edge costs, the most expensive excluded from every minimum varia tree Be ma 3 the following is true? ly S, (b) Only S ©) Both S,and §, (d) Neither S, nor S, Assume ich pee Ghas negative weight edges. Dikstra’s lowing statement is correct when ®) Always algorithm is applied on G? ) Ayre Poduces correct results (6) Ip ayaa incorrect results "correct ee but may produce '0N€ of the above a eee 283 LEI Consiser the totiowing graph G The total number of minimum spanning 805 using Prim’s or Kruskal’s algorithn are _— Let G{V, Ban undirected graph with positive edge weights. Dikstra’s single source-shortest path algorithm can be implemented using the binary heap data structure with time complexity? @ olvi) (b) O(fEl+/ Vlog IV) (©) AlViloglvi) @) amlel +|vidies 2) Consider the undirected graph below: 8 Using Prim’ algorithm to construct 2 minimurt spanning tree starting with node A, which one | ‘of the following sequences of edges represents possible order in which the edges would be added to construct the minimum spanning tree? (@) (€.6).(C.F. G), (A, D), (A.B). (A.C) (©) (A.D), (A.B). (A.C): (C.F), (G.£). (FS) (©) (A.B). (A.D), (0.7). 6 @).(G.€). FC) @ (AD). (A.B), (OF) (FO) @).(G.6) Which of the following statement{s) is/are correct regarding Bellman-Ford shortest path algorithm? P Always finds a negative weighted cycle, if ‘one exists Q. Finds whether any: negative’ weighted cycie ig reachable from the source (a) Ponly (o) Qonly (@ BohPendQ (9) Nether PnorQ Jf minimum spanning treeof given fa |Letthe weight of i ‘graph Gas per Kruskals algorithm is 20d 85 per Prim’s algorithms wether (2) %S Me (0) a2 “> (0) WK @) ary of the above I possible depends 0° graph structure [EXE] Which of the following statements is invalid? (2) Agraph where all edge weights are distinct can have more than one shortest path between two vertices, Multiplying all edge weights by a positive number might change the cost of minimum spanning tree (©) Both (a) and (b) (2) Neither (a) nor (b) ) EEE] suppose that you are Tunning Dikstra's algorithm on the edge-weighted digraph below, starting from vertex A, ‘The table gives ‘Distance’ and ‘Parent’ entry of each vertex after vertex Ehas been deleted from, the priority queue and relaxed. Vertex | Distance | Parent A 0 NULL B 2 A c 13 F D 23 A E "1 F F 7 B G 36 F H 19 E What could be the possible values of x and y? @ x=11,y=7 (b) y= 12 (o) Y= 10 (0) x= 10, y= 14 EXER Given a set A= (4, A,,..., A, of nactivities with start and finish time (Si,f), 1 she ow 420 c 2 3 3 an Match List-l with List-II and select the correct ‘answer using the codes given below the lists: List-I ‘A.V invocations of Dijkstra’s algorithm using min heap tree data structure. B. ‘V'invocations of Bellman-Ford algorithm. C. Single invocation of Fioyd-Warshall algorithm. List-II 1. OV) 2. (Vlog V) 3. ov’) [Given edges = O(V), where Vis vertices] Codes : ABC (a)2 31 (b)3 2 1 (c)1 23 (d) None of these Select all the correct options: (2) Dijkstra’s shortest path algorithm always gives the correct output for a directed weighted graph, (b) Shortest path between two vertices may change if every edge is increased by the same quantity Bellman Ford algorithm is a dynamic © programming based technique intermediate spanning ty on en Jan undirected graph, my EZ Consider a complete graph E edges. Now, assume two shortest distance ‘ears that all edge aces si, i Mire, path are possible if atmost4 edges em 00 in the shortest path? ta (a) 180 (0) 121 (©) 160 © 16 eee Gis an undirected graph with vertexset(vt,2 V3, v4, v5, v6, v7} and edge set (viv2. x3 viv4, v2v4, v2v5, v8v4, v4v5, v4v6, vov6, v7) ‘breadth first search ofthe graphs pertmes with v1 as the root node. Which ofthe faloweg is atree edge? (@) vav4 (b) viva (©) v4vs (@) vava EE2ey Mtich of the following is First Search on the graph? (a) Finding diameter of the: ‘graph (b) Finding biparrte graph (©) Both (a) and (b) (@) None of the above HV tee application of Brea Pet Mermcercteagesinarecis ga dand nvertices is (@) maximum of nando (bo) ned (©) nd nd o> oss a Maximum number of BFS seule moto BST of height 3 is? (Root node FETE] Preorder is same as (a) Depth-frst order (b) Breadth-first order (c) Topological order (d) Linear order Fd which of the following is true @) Bon S, (pony S, valid {@) only S Valid {@ Neither S, nor S, is valid and $, are valid DFS algorithm is applied to the given graph 'garing from vertex A the maximum height of the DFS tree for DFS traversal is 2 Which of the following is the correct match between the algorithm and their time complexity? Algorithm Dikkstra (Priority queue and adjacency cost) Prim’s algorithm (Binary heap) BFS Floyd Warshall Kruskal Algorithm Bellman Ford algorithm : Time Complexity | OV+ 6) 2 O(log y E ow 5 E+ Mog eAex2px Pag 2,R-3, 8-4, 7-5, U-3 ek R483, 72, U-5 ae R2,8-3, 72, U-5 “94, R-3, 8.3, 7-5, U5 "ch of fi the St Searony HOWiNG Is application of depth- © 9, nly ° (by Ony PoobIcal sort. stron ‘ly Connected components. Algorithms ae 287 ‘ statements: mertneriiowing St (©) Both topologi ose “ydirected graph always produces the carpate Ze hui : mber of edges in the traversal ) dane number of e308 I (9) Neither topological sort nor strongly sarecive ofS connected components. sige remove all of back edges found while fo 5 re gnareced graph, terest Number of undirected graphs (not necessarily Sie connected) can be constructed given set V= (1.2. i 3, 4} of 4 vertices, are EEE which of the following are the articulation points in the following graph? O—® e lesa Ns aiseod (a) OnlyC (c) B.C,F Let Gbea graph with ‘n' vertices and ‘m edges. S,: All its DFS forest (for traversals starting at different values) will have the same number of trees. S,: Allits DFS forests willhave the same number of tree edges and the number of back edges. (@ S,- True; S,-True (0) S,- True; S,- False (©) S,-False; S,- True (A) S,-False; S, -False FETE] A mothervertexina graph G=(V, E)isavertex Vsuch/that all other yertices in Gcan be reached by a path from ¥/ What is time complexity of an efficient algoritHi to find the mother vertex in a directed connected graph? (a) OV + E)) (bo) VW) (c) O(Vlog V) (d) O(V+E) ‘the depth first search algorithm has been implemented using the stack data structure, One possible order of visiting the nade of ne folowing graph is (ob) D.C.F (d) None of these (b) ACEBFO CFE Wand (@) BCEFAD (c) BACDFE

You might also like