GATE Computer Science | Complete Paper Solution | Data Structures and Algorithm | GATE 2020

In this video, I have discussed the GATE computer science and engineering paper solution based on data structures and algorithm. In this video, I have explained all 10 questions of gate 2020. The questions are as follows: 1. What is the worst-case time complexity of inserting n^2 elements into an AVL-tree with n elements initially? Θ(n^4) Θ(n^2) Θ(n^2logn) Θ(n^3) 2. The preorder traversal of a binary search tree is 15,10,12,11,20,18,16,19 Which one of the following is the postorder traversal of the tree? A. 10,11,12,15,16,18,19,20 B. 11,12,10,16,19,18,20,15 C. 20,19,18,16,15,12,11,10 D. 19,16,18,20,11,12,10,15 3. For parameters a and b, both of which are ω(1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is Θ(logalogbn) Θ(logabn) Θ(logblogan) Θ(log2log2n) 4. What is the worst-case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order? A. Θ(n) B. Θ(nlogn) C. Θ(n) D. Θ(1) 5. In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k. Θ(logn) Θ(logn+k) Θ(klogn) Θ(nlogk) 6. Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ___________. 7. consider a graph G=(V,E), where v=(v1,v2,...v100), E=((vi,vj)|1=i=j=100) and weight of the edge (vi,vj) is |i-j|. The weight of minimum spanning tree of G is..... 8. Consider a double hashing scheme in which the primary hash function is h1(k)=k mod 23, and the secondary hash function is h2(k)=1+(k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k=90 is_____________. 9.Let G=(V,G) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u,v)∈V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is Θ(∣E∣+∣V∣) Θ(∣E∣∣V∣) Θ(E∣log∣V∣) Θ(∣V∣) I have created this free of cost YouTube channel for computer science and information technology students. Through this channel, I have tried to explain some important topics in a simple way. This channel is very helpful for computer science engineering students may be from GATE, NET, M.TECH, B.Tech, BCA, BSC, MCA, MSC etc. In this channel, I am trying to cover previous years solved GATE questions, Data Structures, Algorithm Design, Operating System, Data Base Management System(DBMS), Theory of computation (TOC), compiler design, C programming etc. Below are the links of my playlists: 1. Operating System: https://www.youtube.com/playlist?list=PLPzfPcir5uPS8g2FThf0JuaUFwjK7arQM 2. Data Structures: https://www.youtube.com/playlist?list=PLPzfPcir5uPQ6LrB421cvMvcF3EcsGrr5 3. Motivational Videos: https://www.youtube.com/playlist?list=PLPzfPcir5uPS17f148fXiFjYWKmNSgQsn 4.. Algorithm: https://www.youtube.com/playlist?list=PLPzfPcir5uPREJTKg1bsDIOh2PB0VAVNs 5. Theory of Computation: https://www.youtube.com/playlist?list=PLPzfPcir5uPT7J0KiJtbvyh-dm_irb69R 6. Compiler Design: https://www.youtube.com/playlist?list=PLPzfPcir5uPQqHm1dYzzNSpjfc-7X_ozq 7. GATE previous year solutions: https://www.youtube.com/playlist?list=PLPzfPcir5uPTyNs8crY1kIOXK1Q5j7zCS My Channel URL: http://www.youtube.com/c/NargishGupta My Website URL: https://www.nargishgupta.com #gate2020 #gate #computerscience #nargishgupta #gatesolution #gatecse