GATECSE - User contributions [en]

Category:Combinatory Notes

2015-05-07T01:01:48Z

Starry Starr: Created page with "Category:Combinatory"

[[Category:Combinatory]]

Number of Binary trees possible with n nodes

2015-05-07T01:01:25Z

Starry Starr:

<metadesc>What's the number of distinct binary trees possible with n labeled nodes?
What's the number of distinct binary trees possible with n unlabeled nodes?
What's the number of distinct binary trees structures possible with n nodes?
What's the number of distinct binary search trees possible with n nodes? </metadesc>
==What's the no. of distinct binary trees possible with n labeled nodes?==

===Solution===
For a binary tree with <math>n</math> nodes, the no. of edges is <math>n-1</math>. So, this problem can be reduced to the no. of ways in which we can make <math>n-1</math> edges from <math>n</math> vertices. An edge can be made either as a left child of a node or as a right child. Hence, for <math>n</math> nodes, we have <math>2n</math> possibilities for the first edge, <math>2n-1</math> for the second edge and so on. Thus, for <math>n-1</math> edges, the total no. of ways

= $2n \times (2n-1) \times (2n-2)\times ....\times (2n - (n - 2))$

= $2n \times (2n-1) \times (2n-2) \times .... \times (n + 2)$

=$ \frac{(2n)!} { (n+1)!}$

==What's the no. of distinct binary trees possible with n unlabeled nodes? (No. of structurally different binary trees possible with n nodes)==

===Solution===
If the nodes are similar (unlabeled), then the no. of distinct binary trees will be the above value divided by the no. of distinct permutations possible for a binary tree structure, which will be $n!$ for a tree with $n$ nodes.

$ \frac{(2n)!} { (n+1)! n!}$

=$\frac{2nCn}{n+1}$

(This is the $n^{th}$ [http://en.wikipedia.org/wiki/Catalan_number Catalan number])

==What's the no. of distinct binary search trees possible with n nodes?==
===Solution===
Counting the no. of distinct binary search trees possible for n nodes, is similar to counting the no. of distinct binary trees possible for n nodes assuming nodes are unlabeled. Hence, this value will also be

=$\frac{2nCn}{n+1}$

($n^{th}$ [http://en.wikipedia.org/wiki/Catalan_number Catalan number])

Alternatively, for each valid binary search tree, we can get $n!$ binary trees by permuting the vertices, of which only 1 permutation is a [http://en.wikipedia.org/wiki/Binary_search_tree $BST$]. Hence, the total no. of binary search trees possible with $n$ nodes will be

$\frac{\text{No. of distinct binary trees with $n$ distinct nodes}} {n!}$

= $ \frac{(2n)!} { (n+1)! n!}$

=$\frac{2nCn}{n+1}$

($n^{th}$ [http://en.wikipedia.org/wiki/Catalan_number Catalan number])

(We can also use the fact that for a given tree structure, there can be only 1 [http://en.wikipedia.org/wiki/Binary_search_tree $BST$]. Hence, no. of different [http://en.wikipedia.org/wiki/Binary_search_tree $BST$]s with n nodes will be equal to the no. of different binary tree structures possible for n nodes)

{{Template:FBD}}

[[Category: Combinatory Notes]]

[[Category: Compact Notes for Reference of Understanding]]

Category:Probability

2015-05-07T00:59:58Z

Starry Starr: Created page with "Category:Engineering Mathematics"

[[Category:Engineering Mathematics]]

Category:Combinatory

2015-05-07T00:59:24Z

Starry Starr: Created page with "Category:Engineering Mathematics"

[[Category:Engineering Mathematics]]

Category:Probability questions

2015-05-07T00:59:06Z

Starry Starr:

[[Category: Engineering Mathematics questions]]
[[Category:Probability]]

Category:Probability and Combinatorics Notes

2015-05-07T00:58:38Z

Starry Starr:

[[Category: Combinatory]]
[[Category:Notes & Ebooks for GATE Preparation]]

Category:Probability questions

2015-05-07T00:56:16Z

Starry Starr:

[[Category: Engineering Mathematics questions]]
[[Category:Probability and Combinatorics]]

Category:Mathematics questions from GATE

2015-05-07T00:56:02Z

Starry Starr:

[[Category: Engineering Mathematics questions]]
[[Category: Previous Year GATE Questions Subject-wise]]

Category:Linear Algebra questions

2015-05-07T00:55:47Z

Starry Starr:

[[Category:Engineering Mathematics questions]]
[[Category:Linear Algebra]]

Category:Calculus questions

2015-05-07T00:55:34Z

Starry Starr:

[[Category:Engineering Mathematics questions]]
[[Category:Calculus]]

Category:Theory of Computation

2015-05-07T00:52:58Z

Starry Starr:

[http://www.youtube.com/playlist?list=PL601FC994BDD963E4 Video lectures by Shai Simonson] are the best

Here is the first video from the series

{{#ev:youtube|HyUK5RAJg1c}}

Here are few terms which you must be familiar with

[http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch11/NP2.html NP Complete]

[http://csfundas.wordpress.com/theory-of-computation-2/recursively-enumerable/ Recursively Enumerable Sets]

This post describes about Computability concepts like SAT / NP completeness

P represents the class of problems that can be solved in polynomial time

NP represents the class of problems whose solutions can be verified in polynomial time

In other words, nondeterministically guess the solution and verify it in polynomial time. The guessing is nondeterministic and verification is polynomial. Thus nondeterministic polynomial (NP) time

If P were equal to NP, there would be amazing consequences. It means every problem verifiable in polynomial time could also be solved in polynomial time, all combinatorial optimizations could be solved in polynomial time. The curse of combinatorial explosions would be gone. Seems unlikely to be true… however NO counterproof (namely P!=NP) has been found.

===SAT problem (introduced by scientist Cook)===

The most important achievement of Cook is to show that P=NP iff a particular computational problem called SAT is in P.

Cook showed that any problem in NP can be transformed to a corresponding instance of SAT problem in such a way that the original has a solution iff the satisfiability instance has. Moreover, this translation can be done in polynomial time. In other words SAT problem is general enough to capture the structure of any problem in NP. It follows that if we can solve the SAT problem in polynomial time, then we would be able to construct a polynomial time algorithm to solve any problem in NP.

The SAT problem is one archetypal problem. In the field of combinatorial optimization , there is one archetypal problem (integer linear programming) and many combinatorial problems can be stated in terms of ILP.

===NP Completeness (introduced by Prof. Karp)===

Karp decided to investigate whether certain classic combinatorial problems long believed to be intractable were also archetypal in Cook’s sense. Karp called them “polynomial complete” (later known as NP complete)

A problem is said to be NP complete if it lies in the class NP and every problem in NP is polynomially reducible to it. Thus by Cook’s theorem the SAT problem is NP complete. To show a given problem in NP is NP complete it if sufficient to show that some problem already known to be NP complete is polynomial time reducible to it. By constructing a series of polynomial reductions, Karp showed that most problems were NP complete.



[[Category:GATE Subjects in CSE]]

[[Category:GATE Subjects in CSE]]

Category:Graph Theory questions from GATE

2015-05-07T00:48:05Z

Starry Starr:

[[Category:Graph Theory questions]]
[[Category:Engineering Mathematics questions]]

Category:Engineering Mathematics questions

2015-05-07T00:47:14Z

Starry Starr: Created page with "Category:Engineering Mathematics Category:Previous Year GATE Questions Subject-wise"

[[Category:Engineering Mathematics]]
[[Category:Previous Year GATE Questions Subject-wise]]

Category:Graph Theory questions from GATE

2015-05-07T00:46:41Z

Starry Starr:

[[Category:Graph Theory questions]]
[[Category:Previous Year GATE Questions Subject-wise]]

Category:Set Theory & Algebra

2015-05-07T00:45:51Z

Starry Starr: Created page with "Category:Engineering Mathematics"

[[Category:Engineering Mathematics]]

Category:Set Theory & Algebra questions from GATE

2015-05-07T00:45:25Z

Starry Starr: Created page with "Category:Set Theory & Algebra Category:Previous Year GATE Questions Subject-wise"

[[Category:Set Theory & Algebra]]
[[Category:Previous Year GATE Questions Subject-wise]]

Category:Graph Theory questions

2015-05-07T00:43:40Z

Starry Starr:

[[Category: Engineering Mathematics questions]]
[[Category:Graph Theory]]

GATE2013 q1

2015-05-07T00:43:00Z

Starry Starr:

A binary operation $\oplus$ on a set of integers is defined as $x \oplus y = x^{2}+y^{2}$. Which one of the following statements is '''TRUE''' about $\oplus$?

'''(A) Commutative but not associative'''

(B) Both commutative and associative

(C) Associative but not commutative

(D) Neither commutative nor associative

{{Template:FBD}}

[[Category: GATE2013]]
[[Category: Set Theory & Algebra questions from GATE]]

GATE2010 q4

2015-05-07T00:42:16Z

Starry Starr:

Consider the set S = $\{1, ω, ω^2\}$, where $\omega$ and $\omega^2$ are cube roots of unity. If $*$
denotes the multiplication operation, the structure $(S, *)$ forms

'''(A) A Group'''

(B) A Ring

(C) An integral domain

(D) A field
==={{Template:Author|Happy Mittal|{{mittalweb}} }}===
We can directly answer this question as "A Group", because other three options require two operations over structure,
but let us see whether $(S, *)$ satisfies group properties or not.
<ul>
<li>Closure: If we multiply any two elements of $S$, we get one of three elements of $S$, so $S$ is closed over $*$.</li>
<li>Associativity: multiplication operation is anyway associative.</li>
<li>Identity element: $1$ is identity element of $S$.</li>
<li>Inverse element: inverse of $1$ is $1$ because $1 * 1 = 1$, inverse of $ω$ is $ω^2$, because
$ω * ω^2 = 1$. Also inverse of $ω^2$ is $ω$, because $ω^2 * ω = 1$</li>
</ul>
Thus, $S$ satisfies all $4$ properties of group, so it is a group. In fact, $S$ is an abelian group, because it also satisfies commutative
property.
<br>
So, option <b>(A)</b> is correct.

{{Template:FBD}}

[[Category: GATE2010]]
[[Category: Set Theory & Algebra questions from GATE]]

Category:Sets and Relations questions from GATE

2015-05-07T00:40:26Z

Starry Starr:

[[Category: Set Theory & Algebra questions]]
[[Category: Set Theory & Algebra questions from GATE]]

Category:Graph Theory questions from GATE

2015-05-07T00:39:29Z

Starry Starr:

[[Category:Graph Theory questions]]
[[Category: Graph Theory questions from GATE]]

Category:Graph Theory

2015-05-07T00:38:37Z

Starry Starr:

[[Category:Engineering Mathematics]]

Category:Databases

2015-05-07T00:36:48Z

Starry Starr: Created page with "Category:GATE Subjects in CSE"

[[Category:GATE Subjects in CSE]]

Category:Database Notes

2015-05-07T00:36:23Z

Starry Starr:

[[File:DATABASE_SYSTEMS.pdf |Ebook Database Systems]]

[http://www2.cs.siu.edu/~cli/CS430/solution6.pdf Database decomposition examples]

{{Template:FB}}
[[Category:Databases]]
[[Category:Notes & Ebooks for GATE Preparation]]

Category:CO & Architecture

2015-05-07T00:35:25Z

Starry Starr: Created page with "Category:GATE Subjects in CSE"

[[Category:GATE Subjects in CSE]]

Optimization

2015-05-07T00:34:34Z

Starry Starr:

* [http://www.agner.org/optimize/optimizing_assembly.pdf Agner Optimizing Assembly Code]

{{Template:FB}}

[[Category:Compilers]]
[[Category:CO & Architecture]]
[[Category:Technical]]

Category:Computer Architecture Notes

2015-05-07T00:34:15Z

Starry Starr:

[http://iete-elan.ac.in/SolQP/soln/soln_ac07.pdf Questions]

[http://cs.stanford.edu/people/eroberts/courses/soco/projects/risc/pipelining/ Pipelining]

[http://www.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/hazards.html Pipeline Hazards]

==Cache memory organization in Processors ==
[[Cache Memory|Cache Memory]]

[[Category:Notes & Ebooks for GATE Preparation]]
[[Category: CO & Architecture]]

Category:Architecture questions

2015-05-07T00:33:59Z

Starry Starr:

[[Category:CO & Architecture]]

Category:Automata questions

2015-05-07T00:32:28Z

Starry Starr:

[[Category:Theory of Computation]]

Category:Theory of Computation

2015-05-07T00:31:51Z

Starry Starr: Created page with "Category:GATE Subjects in CSE"

[[Category:GATE Subjects in CSE]]

Automata Doubts

2015-05-07T00:30:28Z

Starry Starr:

=='''1.''' If $L$ and $L'$ are both recursively enumerable, then $L$ is recursive. Why?==

==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===

Given $L$ is $RE$. So there is a $TM$, which accepts and halts for all words in $L$.
Now, if $L'$ is $RE$, then there is a $TM$, which accepts and halts for all words not in $L$.
So, if a word is given (either from $L$ or not from $L$), give it to both those $TM$s. If it is from $L$, the first $TM$ will halt and we say it belongs to $L$. If it is not from $L$, the second one will halt and we say it doesn't belong to $L$. Thus, $L$ becomes recursive.

{{Template:FBD}}

[[Category: Theory of Computation]]

Category:Automata Theory Notes

2015-05-07T00:30:05Z

Starry Starr:

[http://www.youtube.com/playlist?list=PL601FC994BDD963E4 Video Lectures by Shai Simonson]

[http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch11/NP2.html NP Complete]

[http://www.idt.mdh.se/kurser/cd5560/10_01/examination/KOMPENDIER/Regular/kompendium_eng.pdf Regular expressions, questions and solutions]

[http://csfundas.wordpress.com/theory-of-computation-2/recursively-enumerable Recursively Enumerable Sets]

[http://www.seas.upenn.edu/~cit596/notes/dave/relang0.html Recursively Enumerable Sets]

[http://www.cs.cmu.edu/~eugene/teach/auto01/notes/ Notes from CMU]

[http://carlstrom.com/stanford/comps/Automata-and-Formal-Languages.txt Definitions]

[http://www.cs.ucr.edu/~jiang/cs150/slides4week7_PDA+EquivToCFG.pdf Push Down Automata]

[http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_25.pdf Linear Bounded Automata]

[http://www.cs.cornell.edu/Courses/cs4820/2013sp/Handouts/TMproblems.pdf Turing Machine Problems]

[http://www.cs.cornell.edu/Courses/cs4820/2013sp/Handouts/481TM.pdf Turing Machine Handout]

[http://www.cs.toronto.edu/~sacook/csc463h/notes/comp.pdf Reduction examples for decidablility]

[http://theory.stanford.edu/~trevisan/cs154-12/rice.pdf Rice's theorem, Undecidable and unrecognizable problems on TM]

[http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf Undecidable problems about L(CFG)]

[http://courses.engr.illinois.edu/cs373/fa2013/Lectures/lec25.pdf Trivial and Non-trivial properties of L(M)]

[http://www.cs.wcupa.edu/~rkline/fcs/grammar-undecidable.html Undecidable Problems]

[http://infolab.stanford.edu/~ullman/ialc/spr10/slides/cfl5.pdf Closure property of CFL]

[http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf NP Complete]

[http://channel9.msdn.com/Series/C9-Lectures-Yuri-Gurevich-Introduction-to-Algorithms-and-Computational-Complexity/C9-Lectures-Algorithms-with-Yuri-Gurevich-Introduction-and-Some-History A good lecture going deep into Abstract Machines]

[[NP,_NP_Complete,_NP_Hard| P, NP, NPC and NP-Hard in SImple terms]]

[[Identify_the_class_of_the_language|Identify the class of the language]]

[[Category:Theory of Computation]]
[[Category: Notes & Ebooks for GATE Preparation]]

C

2015-05-07T00:28:56Z

Starry Starr:

[[File:The_C_Programming_Language.pdf]] Dennis Ritchie

[[Category: Programming & Data Structures]]

C Coding Questions

2015-05-07T00:28:47Z

Starry Starr:

<metadesc>C coding questions for understanding the concepts and features of C language</metadesc>
__FORCETOC__
==C Objective Questions==
<quiz display="simple">
{'''What is the output of this program?'''
<syntaxhighlight lang="c" >
#include <stdio.h>
int main()
{
char *ptr;
char string[] = "How are you?";
ptr = string;
ptr += 4;
printf("%s",ptr);
return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' How are you?

+'''(b)''' are you?

-'''(c)''' are

-'''(d)''' No output
||ptr points to the start of the string and hence ptr+4 will point to the 5th char in the string. So, %s will print the characters from ptr+4 till \0 is encountered. ("How are you?" is a string literal and a \0 is implicitly added at the end of it by the compiler)

{''' Which of the following will print the value 2 for the above code?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a[10][20][30] = {0};
a[5][2][1] = 2;

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' printf("%d",*(((a+5)+2)+1));

-'''(b)''' printf("%d",***((a+5)+2)+1);

+'''(c)''' printf("%d",*(*(*(a+5)+2)+1));

-'''(d)''' None of these
||* is the dereferencing operator and to access an element in a 3D array we have to dereference 3 times as in (c)

{''' What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a = 5;
int b = ++a * a++;
printf("%d ",b);
return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)'''25

-'''(b)''' 30

-'''(c)''' 36

+'''(d)''' Undefined Behavior
||In C language if we modify a variable more than once between two sequence points, undefined behavior results (output can be anything on any compiler) and arithmetic operators doesn't form sequence points

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a = 5;
switch(a)
{
default:
a = 4;
case 6:
a--;
case 5:
a = a+1;
case 1:
a = a-1;
}
printf("%d \n",a);

return 0;
}
</syntaxhighlight>
|type="()"
/}
+'''(a)''' 5

-'''(b)''' 4

-'''(c)''' 3

-'''(d)''' None of these
||In switch, a jump happens to the matching case (or else to default) and all statements below that are executed unless there is a break.

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a = 2,b = 5;
a = a^b;
b = b^a;
printf("%d %d",a,b);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 5 2

-'''(b)''' 2 5

-'''(c)''' 7 7

+'''(d)''' 7 2
|| ^ does the XOR operation. a^b = 010 ^ 101 = 111 = 7. Now, b^a = 101 ^ 111 = 010 = 2

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a[][3] = {1, 2, 3, 4, 5, 6};
int (*ptr)[3] = a;
printf("%d %d ", (*ptr)[1], (*ptr)[2]);
++ptr;
printf("%d %d\n", (*ptr)[1], (*ptr)[2]);

return 0;
}
</syntaxhighlight>
|type="()"
/}
+'''(a)''' 2 3 5 6

-'''(b)''' 2 3 4 5

-'''(c)''' 4 5 0 0

-'''(d)''' none of the above

{'''What is the output of the following program? '''
<syntaxhighlight lang="c">
#include <stdio.h>
void f(char**);

int main()
{
char *argv[] = { "ab", "cd", "ef", "gh", "ij", "kl" };
f(argv);

return 0;
}
void f(char **p)
{
char *t;
t = (p += sizeof(int))[-1];
printf("%s\n", t);
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' ab

-'''(b)''' cd

-'''(c)''' ef

+'''(d)''' gh

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdarg.h>
#include <stdio.h>

int ripple(int n, ...)
{
int i, j, k;
va_list p;
k = 0;
j = 0;
va_start(p, n);
for (; j < n; ++j)
{
i = va_arg(p, int);
k += i;
}
va_end(p);

return k;
}
int main()
{
printf("%d\n", ripple(2, 5, 7));

return 0;
}
</syntaxhighlight>
|type="()"
/}
+'''(a)''' 12

-'''(b)''' 5

-'''(c)''' 7

-'''(d)''' 15

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int counter(int i)
{
static int count = 0;
count = count + i;

return count;
}

int main()
{
int i, j;
for (i = 0; i <= 5; i++)
j = counter(i);
printf("%d\n", j);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 10

+'''(b)''' 15

-'''(c)''' 6

-'''(d)''' 7

{''' What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
const int x = 5;
const int *ptrx;
ptrx = &x;
*ptrx = 10;
printf("%d\n", x);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 5

-'''(b)''' 10

+'''(c)''' Compile Error

-'''(d)''' Garbage value

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
#define x 4+1
int main()
{
int i;
i = x*x*x;
printf("%d",i);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 125

+'''(b)''' 13

-'''(c)''' 17

-'''(d)''' None of above

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
char c=125;
c=c+10;
printf("%d",c);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 135

-'''(b)''' +INF

+'''(c)''' -121

-'''(d)''' -8

{''' What is the output of the following program?'''
<syntaxhighlight lang="c">

#include <stdio.h>
int main()
{
int i=10;
static int x=i;
if(x==i)
printf("Equal");
else if(x>i)
printf("Greater");
else
printf("Lesser");

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' Equal

-'''(b)''' Greater

-'''(c)''' Lesser

+'''(d)''' Compile Error

{'''Consider the following code segment:'''
<syntaxhighlight lang="c">
#include <stdlib.h>

int *f1()
{
int x = 10;
return &x;
}
int *f2()
{
int *ptr;
*ptr = 10;
return ptr;
}
int *f3()
{
int *ptr;
ptr = (int*) malloc(sizeof (*ptr));
return ptr;
}
</syntaxhighlight>
'''Which of these functions uses pointers incorrectly?'''
|type="()"
/}
+'''(a)''' f3 only

-'''(b)''' f1 and f3

-'''(c)''' f1 and f2

-'''(d)''' f1, f2, and f3

{''' What is the output of the following program? (Assume sizeof (int) is 4)'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int i = 3;
int j;
j = sizeof(++i + ++i);
printf("i=%d j=%d\n", i, j);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' i=4 j=4

+'''(b)''' i=3 j=4

-'''(c)''' i=5 j=4

-'''(d)''' the behavior is undefined

{''' What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
void f1(int*, int);
void f2(int*, int);
void (*p[2])(int*, int);

int main()
{
int a = 3;
int b = 5;
p[0] = f1;
p[1] = f2;
p[0](&a, b);
printf("%d %d ", a, b);
p[1](&a, b);
printf("%d %d\n", a, b);

return 0;
}

void f1(int *p, int q)
{
int tmp = *p;
*p = q;
q = tmp;
}
void f2(int *p, int q)
{
int tmp = *p;
*p = q;
q = tmp;
}
</syntaxhighlight>
|type="()"
/}
+'''(a)''' 5 5 5 5

-'''(b)''' 3 5 3 5

-'''(c)''' 5 3 3 5

-'''(d)''' none of the above

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
void e(int);

int main()
{
int a = 3;
e(a);
putchar('\n');

return 0;
}
void e(int n)
{
if (n > 0)
{
e(--n);
printf("%d ", n);
e(--n);
}
}
</syntaxhighlight>
|type="()"
/}
+'''(a)'''0 1 2 0

-'''(b)''' 0 1 2 1

-'''(c)''' 1 2 0 1

-'''(d)''' 0 2 1 1

{''' Consider the following code segment:'''
<syntaxhighlight lang="c">
typedef int (*test)(float*, float*);
test tmp;
</syntaxhighlight>
'''What is the type of tmp?'''
|type="()"

/}
-'''(a)''' function taking two pointer-to-float arguments and returning pointer to int

-'''(b)''' pointer to int

+'''(c)''' pointer to function taking two pointer-to-float arguments and returning int

-'''(d)''' none of the above

{''' What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>

int main()
{
char p;
char buf[10] = {1, 2, 3, 4, 5, 6, 9, 8};
p = (buf + 1)[5];
printf("%d\n", p);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 5

-'''(b)''' 6

+'''(c)''' 9

-'''(d)''' none of the above

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
struct node
{
int a;
int b;
int c;
};
struct node s = { 3, 5, 6 };
struct node *pt = &s;
printf("%d\n", *((int*)pt+1));

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 3

+'''(b)''' 5

-'''(c)''' 6

-'''(d)''' 7

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main(void)
{
char a[5] = { 1, 2, 3, 4, 5 };
char *ptr = (char*)(&a + 1);
printf("%d %d\n", *(a + 1), *(ptr - 1));

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' Compile Error

-'''(b)''' 2 1

+'''(c)''' 2 5

-'''(d)''' none of the above

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
void foo(int[][3]);

int main(void)
{
int a[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
foo(a);
printf("%d\n", a[2][1]);

return 0;
}

void foo(int b[][3])
{
++b;
b[1][1] = 9;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 8

+'''(b)''' 9

-'''(c)''' 7

-'''(d)''' none of the above

{'''Consider the following function:'''
<syntaxhighlight lang="c">
int foo(int x, int n)
{
int val = 1;
if (n > 0)
{
if (n % 2 == 1)
val *= x;
val *= foo(x * x, n / 2);
}
return val;
}
</syntaxhighlight>

'''What function of x and n is computed by foo?'''
|type="()"
/}
+'''(a)''' $x^n$

-'''(b)''' $x×n$

-'''(c)''' $n^x$

-'''(d)''' none of the above

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>

int main()
{
int a = 0;
switch(a)
{
default:
a = 4;
case 6:
a--;
case 5:
a = a+1;
case 1:
a = a-1;
}
printf("%d \n",a);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' 5

-'''(b)''' 4

+'''(c)''' 3

-'''(d)''' 0

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a = 2;
if(a == (1,2))
printf("Hello");
if(a == 1,2)
printf("World");

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' Hello

-'''(b)''' World

+'''(c)''' HelloWorld

-'''(d)''' Compile Error

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a = 1,2;
int b = (1,2);
if(a == b)
printf("Equal");
else
printf("Not Equal");

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' Equal

-'''(b)''' Not Equal

-'''(c)''' Compiler Dependent

+'''(d)''' Compile Error

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
void foo(char *);

int main()
{
char *string = "Hello";
foo(string);
printf("%s",string);

return 0;
}

void foo(char *a)
{
while(*a)
{
*a += 1;
a++;
}
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' Hello

-'''(b)''' Ifmmp

-'''(c)''' Compile Error

+'''(d)''' Segmentation fault

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>
int main()
{
char s[] = "Hello World";
int i = 0;
while(*(s++))
i++;
printf("%d",i);

return 0;
}
</syntaxhighlight>
|type="()"
/}
-'''(a)''' Segmentation Fault

+'''(b)''' Compile Error

-'''(c)''' 12

-'''(d)''' 0

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int a = 10;
int main()
{
fun();
fun();

return 0;
}

int fun()
{
static int a = 1;
printf("%d ",a);
a++;

return 0;
}
</syntaxhighlight>
|type="()"
/}
+'''(a)''' 1 2

-'''(b)''' 1 1

-'''(c)''' 10 11

-'''(d)''' 10 10

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
#define crypt(s,t,u,m,p,e,d) m##s##u##t
#define begin crypt(a,n,i,m,a,t,e)
int begin()
{
printf("Hello\n");

return 0;
}
</syntaxhighlight>
|type="()"
/}
+'''(a)''' Hello

-'''(b)''' Link error

-'''(c)''' Segmentation fault

-'''(d)''' Compiler error
</quiz>

==Some Questions==
<quiz display="simple">

{'''Consider the following program:'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a[10][20][30]={0};
printf("%ld",&a+1 - &a);

return 0;
}
</syntaxhighlight>
'''What is the output of this program?'''
|type="{}"
/}
{ 1 }

{'''Consider the following program:'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a[10][20][30] = {0};
int *b = a;
int *c = a+1;
printf("%ld", c-b);

return 0;
}
</syntaxhighlight>
'''What is the output of this program?'''
(You may ignore compiler warnings)
|type="{}"
/}
{ 600 }

{''' What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>
int* fun();

int main()
{
int *a = fun();
printf("%d",*a);

return 0;
}
int* fun()
{
int *a =(int*) malloc(sizeof(int));
*a = 10;
return a;
}
</syntaxhighlight>
|type="{}"
/}
{ 10 }

{''' What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int *a = fun();
printf("%d",a);

return 0;
}
int fun()
{
int a = 10;
return a;
}
</syntaxhighlight>
|type="{}"
/}
{ 10 }

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
#include <string.h>

int main()
{
char string[] = "Hello";
printf("%zu %zu",sizeof(string),strlen(string));

return 0;
}
</syntaxhighlight>
|type="{}"
/}
{ 6 5 }

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
float a = 0.5;
if(a == 0.5)
printf("Yes");
else
printf("No");

return 0;
}
</syntaxhighlight>
|type="{}"
/}
{ Yes }

{'''What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
#include <string.h>
void foo(char *);

int main()
{
char a[100] = {0};
printf("%zu %zu",sizeof(a),strlen(a));

return 0;
}
</syntaxhighlight>
|type="{}"
/}
{ 100 0 }

{'''What is the output of the following program?''' (Assume input is 10)
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
int a;
printf("%d",scanf("%d",&a));

return 0;
}
</syntaxhighlight>
|type="{}"
/}
{ 1 }

{'''If the binary equivalent of 5.375 in normalised form is 01000000 10101100 00000000 00000000, what will be the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
#include <math.h>

int main()
{
float a=5.375;
char *p;
int i;
p = (char*)&a;
for(i=0; i<2; i++)
printf("%x", (unsigned char)(p[i]^p[3-i]));

return 0;
}
</syntaxhighlight>
|type="{}"
/}
{ 40ac }

{''' What is the output of the following program?'''
<syntaxhighlight lang="c">
#include <stdio.h>
int main()
{
char str[] = {'a','b','c','\0'};
str[0] -= 32;
printf("%s",str);

return 0;
}
</syntaxhighlight>
|type="{}"
/}
{ Abc }

</quiz>
==Questions from Datatypes==
{{:C_Questions_on_Datatypes}}

==Questions from Pointers==
{{:C_Questions_on_Pointers}}

==Some codes==

'''1. What is the following function doing?'''
<syntaxhighlight lang="c">
int foo(int n)
{
int sum = 0;
while(n > 0)
{
n = n & n-1;
sum++;
}
return sum;
}
</syntaxhighlight>
'''Ans''':

'''2. What is the following function doing?'''
<syntaxhighlight lang="c">
int foo(int a, int b)
{
int c = a, d = b;
while(a != b)
{
if(a < b)
a = a+c;
else
b = b+d;
}
return a;
}
</syntaxhighlight>
'''Ans''':

'''3. What is the following function doing?'''
<syntaxhighlight lang="c">
int foo( int a, int b)
{
int c = a-b;
c = c&(0x80000000);
return (!c)*a +(!!c)*b;
}
</syntaxhighlight>
'''Ans''':

'''4. What is the following function doing?'''
<syntaxhighlight lang="c">
unsigned fun(unsigned a, unsigned b)
{
int i;
unsigned j = 0;
for(i = 0; i < 32; i++)
{
j <<= 1;
j += !!(a & 0x80000000);
a <<= 1;
if(j >=b)
{
j -= b;
a++;
}
}
return a;
}
</syntaxhighlight>
'''Ans''':

'''5. What is the following function doing?'''
<syntaxhighlight lang="c">
unsigned fun(unsigned int a)
{
unsigned int i, x = 0, y = 0, z = 0;
for(i = 0; i < 16; i++)
{
y <<= 2;
y += !!(a & 0x80000000) << 1;
y += !!(a & 0x40000000);
a <<= 2;
x = x + (x&1);
x <<= 1;
z <<= 1;
if(x + 1 <= y)
{
x++;
z++;
y-=x;
}
}
return z;
}
</syntaxhighlight>
'''Ans''':

'''6. Write the code to dynamically allocate a 2-D array of size m x n.'''

'''Ans''':

'''7. Declare a pointer to a function accepting an integer and returning void.'''

'''Ans''':

'''8. Write the condition so that the below code outputs <math>\unicode{x201C}</math>Hello World<math>\unicode{x201D}</math>.'''
<syntaxhighlight lang="c">
#include<stdio.h>
int main()
{
if(<condition>)
{
printf("Hello ");
}
else
{
printf("World\n");
}

return 0;
}
</syntaxhighlight>
'''Ans''':

'''9. Write a one line code to check if a number is a power of 2.'''

'''Ans''':

'''10. Write a one line code to invert the last four bits of an integer.'''

'''Ans''':

{{Template:FBD}}

[[Category:Programming & Data Structures]]
[[Category:Code]]

Category:Algorithms questions

2015-05-07T00:27:42Z

Starry Starr:

[[Category:Algorithms]]

Category:Graphs

2015-05-07T00:27:28Z

Starry Starr:

[[Category:Code]]
[[Category:Algorithms]]

Category:Sorting

2015-05-07T00:27:16Z

Starry Starr:

[[Category:Code]]
[[Category:Algorithms]]

Category:Algorithms

2015-05-07T00:26:58Z

Starry Starr: Created page with "Category: GATE Subjects in CSE"

[[Category: GATE Subjects in CSE]]

Category:Algorithms & Data Structures Notes

2015-05-07T00:26:18Z

Starry Starr:

[[Category: Notes & Ebooks for GATE Preparation]]
[[Category: Algorithms]]

Category:Trees

2015-05-07T00:26:05Z

Starry Starr:

[[Category: Algorithms]]

[[Category: Code]]