OF COMBAT To Get AIR 1 GATE 2023 Sweta Kumari TELEGRAM Link to get NOTES : https://t.me/SWETAKCS Referral Code : HELLOSONU01 CODE : HELLOSONU01 REFERRAL CODE : HELLOSONU01 REFERRAL CODE : HELLOSONU01 STARTING SQL TODAY COMPLETE COURSE ON DATABASE MANAGEMENT SYSTEM (DBMS) GATE 2023/24/25 Use HELLOSONU01 referral code to get max discount on Unacademy plus/lite/iconic subscription & 350 SRPs book. NEW COURSE STARTED From 15th SEPT
COMPLETE COURSE ON C Programming & Data Structures GATE 2023/24/25 Use HELLOSONU01 referral code to get max discount on Unacademy plus/lite/iconic subscription & 350 SRPs book. REFERRAL CODE : HELLOSONU01 FROM WHERE YOU SHOULD PRACTICE ? Only With ICONIC SUBSCRIPTION HELLOSONU01 REFERRAL CODE : HELLOSONU01 BEST REVISION Book For GATE CS IT (Covers all the Important Concepts , All the Important PYQs , Important Formulae , Short Tricks From All the Units of Computer science subjects + General Aptitude) FOR NEW SUBSCRIBERS Free with Unacademy Subscription using referral code HELLOSONU01 (ALSO DISCOUNT Code) HAMILTONINAN CIRCUIT (n>=3) = Passes through every vertex Check Planarity of graph Bipartite graph = No odd 1. e, v where v >= 3 DIRAC’S THEOREM = Degree of every vertex should be at least n/2 GRAPH length cycle Circuits of length 3 THEORY ORE’S THEOREM = deg(u) + deg(v) >= n (non adjacent) Revise in 1 E <= 3v-6 E(G’) + E(G) = Complete graph NOTE – Degree of 1 vertex means not Hamiltonian circuit Page 2. e, v where v >= 3 E(G’) = n(n-1)/2 - E(G) No Circuits of length 3 E <= 2v-4 strongly connected components = edge EULER GRAPH = Passes through every edge between every pair of vertex VERTICES OF EVEN DEGREE = Single Revision Page (SRP) EULER CIRCUIT Maximum number of edges in a Handshaking thm : Sum of degree of vertices = 2 x edges PYQs connected planar, simple graph = 3n-6 EXACTLY 2 VERTICES OF ODD DEGREE = EULER PATH BUT NOT CIRCUIT Four Color thm : 4 colors are sufficient to color planar 90 Minutes Lecture Converted in 1 Page graph Kn,n => K3,3 Kn+1,n => K8,9 Isomorphic Graphs = Count nodes , count edges , Always Hamiltonian circuit. Self Complementary graph – Isomorphic to its Check degree of each vertex , check length of cycle complement (in both graphs) DISCRETE MATHEMATICS = Half no. of edges in complete graph = n(n-1)/4 (must be disable by 4 or 0) Maximum number of edges in undirected A connected graph ‘G’ may have graph C5 cycle is the only graph which is self complementary at most (n–2) cut vertices. = n(n-1)/2 Euler’s formula : R = E – V + 2 (Always 1 region is the maximum number of cut No. of graphs can be constructed = 2 n(n-1)/2 bounded) edges possible is ‘n-1’. Undirected Graph : If all weights distinct in MST , Number of odd degree vertices is even. 1. Always contain emin Sum of degree of all vertices is even. Maximum number of edges in Complete 2. Unique MST bipartite graph = n2/4 3. Emax present in MST Max. edges in connected graph which doesn’t form cycle = (n-1) Circuit Rank = m-(n-1) Which is correct statement in context of order of an element of the group? A. The order of every element of a finite group is finite. B. The Order of an element of a group is the same as that of its inverse. C. If a and b are elements of a group then the order of ab is same as order of ba. D. All of the above Which is correct statement in context of order of an element of the group? A. The order of every element of a finite group is finite. B. The Order of an element of a group is the same as that of its inverse. C. If a and b are elements of a group then the order of ab is same as order of ba. D. All of the above
ANSWER :D Properties of the order of an element of the group: The order of every element of a finite group is finite. The Order of an element of a group is the same as that of its inverse a-1. If a and b are elements of a group then the order of ab is same as order of ba. What is conservative 2PL concurrency control protocol? A. A 2PL protocaol where a transaction has to acquire locks on all the data items it requires before the transaction begins it execution. B. A 2PL protocaol where a transaction can acquire locks on data items whenever it requires (only in growing phase) during its execution. C. It ensures that the schedule generated would be Serializable, Recoverable and Cascadeless. D. NONE What is conservative 2PL concurrency control protocol? A. A 2PL protocaol where a transaction has to acquire locks on all the data items it requires before the transaction begins it execution. B. A 2PL protocaol where a transaction can acquire locks on data items whenever it requires (only in growing phase) during its execution. C. It ensures that the schedule generated would be Serializable, Recoverable and Cascadeless. D. NONE
Answer : A In Conservative 2-PL, A transaction has to acquire locks on all the data items it requires before the transaction begins it execution. It does not have growing phase. It ensures that the schedule generated would be Serializable and Deadlock-Free. It does not ensures Recoverable and Cascadeless schedule. In which cache mapping technique , block size does not affect the cache tag anyhow ? A. Direct cache mapping B. Fully associative cache mapping C. Set associative cache mapping D. A and C
. In which cache mapping technique , block size does not affect the cache tag anyhow ? A. Direct cache mapping B. Fully associative cache mapping C. Set associative cache mapping D. A and C
Answer - D In fully associative cache, on decreasing block size, cache tag is reduced and vice versa. Which of the following is deterministic CFL? A. 𝐿1 = {𝑎𝑚 𝑏𝑛 𝑐 𝑘 𝑑𝑙 |𝑚 = 𝑛, 𝑘 = 𝑙 } B. 𝐿2 = {𝑎𝑚 𝑏𝑛 𝑐 𝑘 𝑑𝑙 |𝑖𝑓 𝑛 = 𝑘 𝑡ℎ𝑒𝑛 𝑚 = 𝑙 } C. 𝐿3 = 𝑎𝑚 𝑏𝑛 𝑐 𝑘 𝑑 𝑙 𝑚 = 𝑛 = 𝑘 = 𝑙)} D. None of these Which of the following is deterministic CFL? A. 𝐿1 = {𝑎𝑚 𝑏𝑛 𝑐 𝑘 𝑑𝑙 |𝑚 = 𝑛, 𝑘 = 𝑙 } B. 𝐿2 = {𝑎𝑚 𝑏𝑛 𝑐 𝑘 𝑑𝑙 |𝑖𝑓 𝑛 = 𝑘 𝑡ℎ𝑒𝑛 𝑚 = 𝑙 } C. 𝐿3 = 𝑎𝑚 𝑏𝑛 𝑐 𝑘 𝑑 𝑙 𝑚 = 𝑛 = 𝑘 = 𝑙)} D. None of these ANS: A Solution: (A) L1 is DCFL L2 is CFL but not DCFL L3 is not CFL The message 100100 is to be transmitted by taking the CRC polynomial X3 + X2 + 1. to protect it from errors. What must be the message to be sent after appending the CRC to the message ? a. 100100000 b. 100100001 c. 100100011 d. 100100101 Ans. b) The message 100100 is to be transmitted by taking the CRC polynomial X3 + X2 + 1. to protect it from errors. What must be the message to be sent after appending the CRC to the message ? a. 100100000 b. 100100001 c. 100100011 d. 100100101 Ans. b) What will be output of the following program? #include <stdio.h> int main() { char str[] = "%d %c", arr[] = "bcdefa"; printf(str, 0[arr], 2[arr + 3]); return 0; } a) 97 b b) 98 a c) 97 a d) Compile error
Answer: b Description: Output will be 98 a 0[arr] equivalent to arr[0] 2[arr+3] is equivalent to arr[2+3] And printf(str, 0[arr], 2[arr + 3]) is another variation of printf syntax which runs without any error. What will be output of the following program? #include <stdio.h> int main() { char str[] = "%d %c", arr[] = "bcdefa"; printf(str, 0[arr], 2[arr + 3]); return 0; } a) 97 b b) 98 a c) 97 a d) Compile error
Answer: b Description: Output will be 98 a 0[arr] equivalent to arr[0] 2[arr+3] is equivalent to arr[2+3] And printf(str, 0[arr], 2[arr + 3]) is another variation of printf syntax which runs without any error. Consider a system using TLB for paging with TLB access time of 40ns. What hit ratio is reduced for TLB to reduce the effective memory access time from 400ns to 280ns? (A) 95% (B) 90% (C) 85% (D) 80% Ans: D Sol: Given that without using TLB, the effective memory access time = 400ns, which is 2 * tm Hence memory access time tm = 200ns
280 = H(40+200) + (1-H) (40 + 400) H = 0.8 = 80% Consider a system using TLB for paging with TLB access time of 40ns. What hit ratio is reduced for TLB to reduce the effective memory access time from 400ns to 280ns? (A) 95% (B) 90% (C) 85% (D) 80% Ans: D Sol: Given that without using TLB, the effective memory access time = 400ns, which is 2 * tm Hence memory access time tm = 200ns
280 = H(40+200) + (1-H) (40 + 400) H = 0.8 = 80% Consider a simple undirected graph G with 40 vertices then maximum number of edges in this graph without self-loop and multiple edges between 2 vertices is? (A) 40 (B) 80 (C) 780 (D) 820
Ans: C Solution: Maximum edges in a simple graph with n vertices = n(n-1) / 2 = (40*39) / 2 = 780 Consider a simple undirected graph G with 40 vertices then maximum number of edges in this graph without self-loop and multiple edges between 2 vertices is? (A) 40 (B) 80 (C) 780 (D) 820
Ans: C Solution: Maximum edges in a simple graph with n vertices = n(n-1) / 2 = (40*39) / 2 = 780 Consider a demand paging system which takes x millisecond to service a page fault and y millisecond to fulfil a memory request of CPU without page-fault. If x is 7 times of y and page fault rate is 0.1 then the effective memory access time is given by? (A) 6.4y millisecond (B) 6y millisecond (C) 1.7y millisecond (D) 1.6y millisecond Ans: D Sol: x =7y
Effective memory access time = 0.1 * x + (1-0.1)*y
= 0.1 * 7y + 0.9 * y = 1.6 y Consider a demand paging system which takes x millisecond to service a page fault and y millisecond to fulfil a memory request of CPU without page-fault. If x is 7 times of y and page fault rate is 0.1 then the effective memory access time is given by? (A) 6.4y millisecond (B) 6y millisecond (C) 1.7y millisecond (D) 1.6y millisecond Ans: D Sol: x =7y
Effective memory access time = 0.1 * x + (1-0.1)*y
= 0.1 * 7y + 0.9 * y = 1.6 y Which of the following is true regarding relations? (A) Identity relation I on set A is reflexive, transitive but not symmetric (B) Void Relation R = Φ is symmetric and transitive but not reflexive (C) Universal relation is reflexive, symmetric but not transitive. (D) All of the above
Ans: B Solution: The different relations correctly can be expressed as Identity relation I on set A is reflexive, transitive and symmetric Void Relation R = Φ is symmetric and transitive but not reflexive Universal relation is reflexive, symmetric and transitive Which of the following is true regarding relations? (A) Identity relation I on set A is reflexive, transitive but not symmetric (B) Void Relation R = Φ is symmetric and transitive but not reflexive (C) Universal relation is reflexive, symmetric but not transitive. (D) All of the above
Ans: B Solution: The different relations correctly can be expressed as Identity relation I on set A is reflexive, transitive and symmetric Void Relation R = Φ is symmetric and transitive but not reflexive Universal relation is reflexive, symmetric and transitive Suppose a user has a schedule in which two transactions T1 and T2 and TS(T2) < TS(T1) then which operation is allowed under Thomas Write Rule but not under Basic Time Stamp Ordering ? A. R1(X) W2(X) B. W1(X) R2(X) C. W1(X) W2(X) D. W2(X) W1(X)
ANSWER : C The main update in Thomas Write Rule is ignoring the Obsolete Write Operations. This is done because some transaction with a timestamp greater than TS(T) (i.e., a transaction after T in TS ordering) has already written the value of X. Hence, logically user can ignore the Write(X) operation of T which becomes obsolete. Suppose a user has a schedule in which two transactions T1 and T2 and TS(T2) < TS(T1) then which operation is allowed under Thomas Write Rule but not under Basic Time Stamp Ordering ? A. R1(X) W2(X) B. W1(X) R2(X) C. W1(X) W2(X) D. W2(X) W1(X)
ANSWER : C The main update in Thomas Write Rule is ignoring the Obsolete Write Operations. This is done because some transaction with a timestamp greater than TS(T) (i.e., a transaction after T in TS ordering) has already written the value of X. Hence, logically user can ignore the Write(X) operation of T which becomes obsolete. Which statement is incorrect regarding CRC Generator ?
A.CRC can detect all double-bit errors provided the divisor contains at least three logic 1’s. B.CRC can detect any odd number of errors provided the divisor is a factor of x+1. C.CRC can detect all burst error of length greater than the degree of the polynomial. D.CRC can detect most of the larger burst errors with a high probability.
ANSWER : C
CRC can detect all single-bit errors
CRC can detect all double-bit errors provided the divisor contains at least three logic 1’s. CRC can detect any odd number of errors provided the divisor is a factor of x+1. CRC can detect all burst error of length less than the degree of the polynomial. CRC can detect most of the larger burst errors with a high probability. Which statement is incorrect regarding CRC Generator ?
A.CRC can detect all double-bit errors provided the divisor contains at least three logic 1’s. B.CRC can detect any odd number of errors provided the divisor is a factor of x+1. C.CRC can detect all burst error of length greater than the degree of the polynomial. D.CRC can detect most of the larger burst errors with a high probability.
ANSWER : C
CRC can detect all single-bit errors
CRC can detect all double-bit errors provided the divisor contains at least three logic 1’s. CRC can detect any odd number of errors provided the divisor is a factor of x+1. CRC can detect all burst error of length less than the degree of the polynomial. CRC can detect most of the larger burst errors with a high probability.
