Graph theory

Graph Theory Preparation Resources for GATE CSE

July 16, 2015 by Arjun Suresh 6 Comments

Materials for GATE preparation in Graph Theory

33,888 total views, 1 views today

GATE Overflow
Aptitude Overflow

Consider the following code fragment executed by a process of PID=1055. int main() { int a=5; if (fork() == 0) { a = a + 5; b= getppid(); printf(“%d, %d \n”, a, b); } else { c = a - 5; d= getpid(); printf (“%d, %d \n”, c, d); } return 0; } Write the output of a, b, c, d? [...]

Answered: Self Doubt

The answer is 20. See below image OR One way to select root. 10 / \ LST (3 elements) RST (2 elements) Now LST contains an element out of 5 (As the root is chosen) So Total ways to choose element $_{}^{5}\textrm{C}_{3}$ and RST contains 2 element So number of ways = $_{}^{2}\textrm{C}_{2}$ Let LST chosen { 20,30,40} Now 2 chosen as root of… [...]

Answered: Kenneth Rosen Edition 6th Exercise 2.2 Question 8 (Page No. 120)

i think in 7 rhs {{∅}, {∅}} both are same according to set definition only distinct are allowed so it will become {{∅}} now question is {{∅}} ⊂ {{∅}} is it proper subset so answer is false. please tell am i thinking right?? [...]

What is the admission procedure for IIT Madras MS in CSE?

Hello all, I wanted to know, what is the procedure for getting admission into MS in CSE in IIT Madras. Please also provide the GATE cutoff is possible. Thanks! [...]

Answered: GATE CSE 1988 | Question: 4ii

The Ex-OR gate is used to differentiate b/w normal binary addition vs 2’s complement addition. ref:- https://www.ijert.org/efficient-design-of-2s-complement-addersubtractor-using-qca-2 [...]

Answered: GATE CSE 2021 Set 2 | Question: 20

Answer: 80000 bits per second Explanation Transfer Time(let Ty) given as 1 cycle. Let Preparation Time be Tx. Processor operating frequency given as 2 MHz, from this we can calculate Cycle Time = 1/2MHz = 0.5 micro seconds. %time CPU blocked = 0.5% (Given) For cycle stealing mode, %time CPU blocked = (transfer time/preparation time)*100, putting the values in this formula, 0.5% = 1 cycle/Tx Tx = 100 micro second. The Tx depends upon device data transfer rate. Now DMA is transferring 8 bit data, and to prepare 8 bits of data, time required by the device is 100 micro seconds, so we can… [...]

Answered: CAT2018-2: 92

Given that, $ 4^{n} . 17^{19} $ Taking the $ \log_{10}$ both sides. $ \log_{10}4^{n} . \log_{10} 17^{19} $ $ \Rightarrow n \log_{10}4 . 19 \log_{10}17 \; [ \because \log_{b}a^{x} = x \log_{b}a] $ $ \Rightarrow n > 19 \left( \frac{\log_{10}17}{ \log_{4}17} \right) $ $ \Rightarrow n > 19 ( \log_{4}17) \; \left[ \log_{b}a = \frac{ \log_{x}a}{ \log_{x}b} \right] $ For easy calculation, let us assume $17 \approx 16.$ Now, $ n > 19 ( \log_{4} 16)$ $ \Rightarrow n > 19 ( \log_{4} 4^{2})$ $ \Rightarrow n > 19 \times 2 ( \log_{4}4)$ $ \Rightarrow $ [...]

Answered: CAT2018-2: 100

Let, $ \text{S} = \frac{1}{ \log_{2}100} – \frac{1}{ \log_{4}100} +\frac{1}{\log_{5}100} – \frac{1}{\log_{10}100} + \frac{1}{\log_{20}100} – \frac{1}{\log_{25}100} + \frac{1}{\log_{50}100} $ $ \Rightarrow \text{S} = \log_{100}2 – \log_{100}4 + \log_{100}5 – \log_{100}10 + \log_{100}20 – \log_{100}25 + \log_{100}50 \left[ \because \log_{b}a = \frac{1}{\log_{a}b} \right] $ $ \Rightarrow \text{S} = \log_{100}2 – \log_{100}4 + \log_{100}5 – \log_{100}10 + \log_{100}(5 \cdot 4) – \log_{100}(5 \cdot 5) + \log_{100}(5 \cdot10) $ $ \Rightarrow \text{S} = \log_{100}2 – \log_{100}4 + \log_{100}5 – \log_{100}10 + \log_{100}5 +\log_{100}4 – \log_{100}5 – \log_{100}5 + \log_{100}5 + \log_{100}10 \; \left[ \because \log_{x}(ab) = \log_{x}a + \log_{x}b \right] $ $ \Rightarrow… [...]

Answered: CAT2018-2: 91

Given that, $ \text{T} = \{ 1,2,3,4\} $ $ \text{Q} = \{ 2,3,5,6 \} $ $ \text{R} = \{ 1,3,7,8,9\} $ $ \text{S} = \{ 2,4,9,10\} $ $ \boxed{ \text{A} \triangle \text{B} = ( \text{A} \cup \text{B}) – ( \text{A} \cap \text{B})} $ DIAGRAM $ \text{A} \triangle \text{B} = ({ \text{A} – \text{B}) \cup (\text{B} – \text{A})} $ Now, $ \text{P} \triangle \text{Q} = \{ 1,2,3,4\} \triangle \{ 2,3,5,6\} $ $ \Rightarrow \text{P} \triangle \text{Q} = \{ 1, 4, 5,6 \} $ And, $ \text{R} \triangle \text{S} = \{ 1,3,7,8,9 \} \triangle \{ 2,4,9,10 \} $ $ \Rightarrow \text{R} \triangle \text{S} = \{… [...]

Answered: CAT2018-2: 90

Let $x$ and $y$ be the two numbers. $ x^{2} + y^{2} = 97 \quad \longrightarrow (1) $ The geometric mean cannot exceed the arithmetic mean. $ \text{AM} \geqslant \text{GM} $ $ \Rightarrow \boxed{\frac{a_{1} + a_{2} + a_{3} + \dots + a_{n} } {n} \geqslant \sqrt[n]{a_{1} a_{2} \dots a_{n}}} $ Now, $ \frac{x^{2} + y^{2}}{2} \geqslant \sqrt{x^{2} \cdot y^{2}} $ $ \Rightarrow \frac{x^{2} + y^{2}}{2} \geqslant \sqrt{(xy)^{2}} $ $ \Rightarrow \frac{x^{2} + y^{2}}{2} \geqslant xy $ $ \Rightarrow x^{2} + y^{2} \geqslant 2xy $ $ \Rightarrow 97 \geqslant 2xy $ $ \Rightarrow 2xy \leqslant 97 $ $ \Rightarrow xy \leqslant… [...]

Answered: CAT2018-2: 81

Let say, $ p^{3} = q^{4} = r^{5} = s^{6} = k \quad \longrightarrow(1) $ Now, $ p^{3} = k \Rightarrow p = k^{\frac{1}{3}} $ $ q^{4} = k \Rightarrow q = k^{\frac{1}{4}} $ $ r^{5} = k \Rightarrow r = k^{\frac{1}{5}} $ $ s^{6} = k \Rightarrow s = k^{\frac{1}{6}} $ Now, $ \log_{s} (pqr) = \log_{k^{\frac{1}{6}}} \left( k^{\frac{1}{3}} \cdot k^{\frac{1}{4}} \cdot k^{\frac{1}{5}} \right) $ $ = \log_{k^{\frac{1}{6}}} \left[ k^{( \frac{1}{3} + \frac{1}{4} + \frac{1}{5})} \right] $ $ = \log_{k^{\frac{1}{6}}} \left[ k^{(\frac{ 20+15+12}{60})} \right] $ $ = \log_{k^{\frac{1}{6}}} \left( k^{\frac{47}{60}} \right) $ $ = \frac{47}{60} \; \log_{k^{\frac{1}{6}}} k \; [ \because \log_{b} a^{x} = x\log_{b} a ] $… [...]

Answered: CAT2018-2: 74

Given that, $ f(x) = \max \{ 5x, 52-2x^{2} \} \quad \longrightarrow (1) $ And, $x$ is a positive real number. The minimum value occurs when both the graphs intersect. Let $ y_{1} = 5x \quad \longrightarrow (2) $ And, $ y_{2} = 52 – 2x^{2} \quad \longrightarrow (3) $ DIAGRAM 1 From equation $(2),$ $ y_{1} = 5x$ is an equation of line. $ y = mx+c ; $ Where m = slope of the line , c= intercept on the y – axis. From equation $(3),$ $ y_{2} = 52 – 2x^{2}$ is a quadractic equation. $ y_{2}… [...]

%d bloggers like this:

Skip links

Graph theory

Share this:

Like this: