Programming for Problem Solving for B.Tech. Pt-I (IT/EIE/ECE) 1st Semester Examination, 2025

Department of Engineering and Technological Studies, University of Kalyani

B.Tech. Pt-I (IT/EIE/ECE) 1st Semester Examination, 2025

Subject: Programming for Problem Solving

Paper: IT101

Full marks=70 Time: 3 Hours

The figures in the right-hand margin indicate marks.

Candidates are required to give their answers in their own words as far as possible.

The notations follow their standard meanings.

Answer question number one and any five from rest.

1.     Answer any ten questions:     (2 x 10 = 20)

    (i)     What do you mean by I-P-O cycle?

    (ii)     Write down the main components of the computer system.

    (iii)     What do you mean by infinite loops? Gives example using do-while statements.

    (iv)     What are the difference between ‘compiler’ and ‘interpreter’?

    (v)     What do you mean by ‘Modulo Division’?

    (vi)     Write down the different types of modern computer based on shapes, sizes and capabilities. Also, classify the modern computer based on working principle.

    (vii)     What do you mean by ‘scanf()’ and ‘printf()’ function in C-Programming?

    (viii)     What do you mean by ‘BASE’ for a given number system? Propose a number

system having ‘BASE’ as (N+1).

    (ix)     What is ‘getchar()’ and ‘putchar()’ function in C-Programming?

    (x)     What do you mean by ‘Recursive function’?

    (xi)     What do you mean by ‘break’ and ‘continue’ statement in C-Programming?

    (xii)     What do you mean by ‘Pointer’ variables.

    (xiii)     What are the deference between ‘string’ and ‘character’?

    (xiv)     Define the file-functions fopen(), fscanf(), fprintf().

    (xv)     What do you mean by conditional operator?

2.     (i)     What do you mean by C-Tokens? Write down the difference between keywords and identifiers.

        (ii)     Write a C-program using integer arithmetic to convert a given number of days into years, months and days.

        (iii)     Write a C-program to find the GCD (Greatest Common Divisor) of two integer numbers.
                                                                                            (4+3+3)

3.     (i)     What do you mean by the ‘GOTO STATEMENT’ in C-Programming? What are the disadvantages?

        (ii)     What do you mean by ‘loop’ in C-Programming? Draw the flow-diagram for ‘entry- controlled loop’ and ‘exit-controlled loop’.

        (iii)     Write a C-program to print the following output using for-loops.

            * * * * *
            * * * *
            * * *
            * *
            *
                                                                        (3+4+3)

4.     (i)     What do you mean by ‘switch’ statement? Discuss different types of ‘if- statemements’.

        (ii)     Distinguish between ‘auto’, ‘register’ and ‘static’ variables.

        (iii)     Write a C-program to find the factorial of a number using recursion.

                                                                            (4+4+2)

5.     (i)     The Fibonacci numbers are defined recursively as follows:

                F1 = 1, F2 = 1, Fn = Fn-1+Fn-2, for n > 2

Write a C-function that will generate and print the first n Fibonacci numbers.

        (ii)     What is array? Discuss different data types in C-programming.

        (iii)     Write down the the different string-handling liberary functions with examples.

                                                                            (4+2+4)

6.     (i)     What do you mean by ‘structure’ and ‘union’ in C-programming? Write down the differences based on their memory need for execution.

        (ii)     Define the sizeof() operator.

        (iii)     What are the differences between ‘Arrays of Structures’ and ‘Arrays within Structures’?
                                                                            (5+2+3)

7.     (i)     Consider the following declaration:

                int x=10, y=10;

                int *p1 = &x, *p2= &y;

What is the value of each of the following expressions?

        (a)     (*p1)++             (b)     ++(*p2)

        (ii)     What do you mean by ‘call-by-reference’ and ‘call-by-value’ in a C-programming?

        (iii)     Write a C-program function using pointers to exchange the values stored in two locations in the memory.
                                                                                (2+3+5)

8.     Short notes:                                (2 x 5)

Answer any two of the following:

    (i)     ‘Hardware’ and ‘Software’ of a computer.

    (ii)     ‘Compiler’ and ‘Linker’ in C.

    (iii)     Classification of computer based on generation.

    (iv)     ‘Non-positional Number System’ vs. ‘Positional Number System’.

Automata & Compiler Design – UGC-NET Previous Years’ Questions

NET-JUNE-2026

1.    Match the LIST-I with LIST-II

LIST-I Language		LIST-II Type of Language
A.	L1 ={anbm |  n,m ≥0}	I.	Unrestricted
B.	L2 ={anbm |  (n=m)≥0 }	II.	Context  Sensitive
C.	L3 = { anbncndnen |  n ≥1 }	III.	Regular
D.	L4 = {anbncmdne2|  n,m ≥0}	IV.	Context Free

Choose the correct answer from the options given below:

1.    A - III,    B - I,    C - II,    D - IV

2.    A - III,    B - IV,    C - I,    D - II

3.    A - III,    B - II,    C - IV,    D - I

4.    A - II,    B - III,    C - IV,    D - I

NET-JUNE-2026

2.    If L₁ is a regular language and L₂ is a context free language, which of the following statement is correct ?

1.    Any subset of L₁ ∪ L₂ is context free.

2.    L₁ ∩ L₂ is a context free language.

3.    L₁ ∩ L₂ is a regular language.

4.    L₁ ∩ L₂ is accepted by a deterministic 

        push down automatons.

NET-JUNE-2026

3.    Arrange the following families of languange from specialization to generalization, defined over alphabet Σ :

A.    Family of all regular languages.

B.    Family of all Turing acceptable languages.

C.    Family of all Turing decidable languages.

D.    Family of all context free languages.

Choose the correct answer from the options given below:

1.    A, B, C, D

2.    A, C, B, D

3.    A, D, C, B

4.    A, D, B, C

NET-JUNE-2026

4.    Which of the following statements is incorrect ?

    1.    Given a context free grammar G and a string x, an algorithm can be designed to decide whether x ∈ L(G) in polynomial time.

    2.    Given a context free grammar L , its complement is also context free.

    3.    The language {aⁿ b^m c^p:  m, n, p  ≥ 0,   m ≠ n or m ≠ p} is not deterministic context free.

    4.    Class of deterministic context free languanges is closed under intersection. 

NET-JUNE-2026

5.    The minimum state of DFA of the following would be the

following:

NET-JUNE-2026

6. - to - 10.    Link Questions:

Consider the following Context Free Grammar (G):-

S -> A B

B -> + A B | ∈

A -> C D

D -> * C D | ∈

C -> [S] | x

Variable = {S, A, B, C, D} 

Terminals = {+, *, [, ], x }

6.    Find the Follow (A) & Follow (C).

    1.    Follow (A) = { ], $ };     

            Follow (C) = { +, ], $ };

    2.    Follow (A) = { +, ], $ };     

            Follow (C) = { *, +, ], $ };

    3.    Follow (A) = { *, $, [ };     

            Follow (C) = { *,  [, $ };

    4.    Follow (A) = { *, ], $ };     

            Follow (C) = { +, ], $ };

7.    In the LL(1) Parsing table of the given CFG, how many valid non blank entities will be there in the rows for variables 'B' and 'D' ?

    1.    B = 3 entries ;    D = 4 entries

    2.    B = 6 entries ;    D = 5 entries

    3.    B = 2 entries ;    D = 3 entries

    4.    B = 1 entries ;    D = 2 entries

8.    Identify the correct statement from the following.

    1.    The given CFG (G) is Left recursive

    2.    The given CFG (G) needs Left factorization

    3.    [ [ x * x ] + x] is a valid sentence of this grammar

    4.    The given CFG (G) has an SLR (0) Parser as well.

9.    What will be the FIRST (S) & FIRST (D) ?

    1.    FIRST (S) = { +, [, x };     

            FIRST (D) = { +, * };

    2.    FIRST (S) = { [, ], x };     

            FIRST (D) = { +, ∈ };

    3.    FIRST (S) = { [, x };     

            FIRST (D) = { *, ∈ };

    4.    FIRST (S) = { [, x, ∈ };     

            FIRST (D) = { *, ∈ };

10.    The I₀ state of the canonical LR (0) set of the SLR (1) parser of this CFG has how many productions ?

    1.    3

    2.    4

    3.    5

    4.    6

NET-DEC-2025

1.    A phase of a compiler which produce the symbol table is

    1.    Syntax analysis

    2.    Semantic analysis

    3.    Target code generation

    4.    Code optimization

NET-DEC-2025

2.    Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.

Assertion A: L={ aⁿ bⁿ cⁿ : n ≥ 0 } is accepted by a linear bounded automata.

Reason R: Linear bounded automata's recognize exactly the class of context sensitive languages.

In the light of the above statements, choose the most appropriate answer from the options given below

    1.    Both A and R are correct and R is the correct explanation of A.

    2.    Both A and R are correct bur R is not the correct explanation of A.

    3.    A is correct but R is not correct.

    4.    A is not correct but R is correct.

NET-DEC-2025

3.    Match the LIST-I with LIST-II

LIST-I Grammar		LIST-II All productions  are of the form
A.	Regular Grammar	I.	A -> aX, where  a ∈ T and  X ∈ V*
B.	Unrestricted  Grammar	II.	A -> xB, A -> x  or A -> Bx, A ->x where  A, B ∈ V and x ∈ T*
C.	Chomsky  Normal  Form	III.	x -> y, where  x ∈(V U T)*  and  y ∈(V U T)*
D.	Greibach Normal  Form	IV.	A -> BC or  A -> a , where A, B, C are in V and a  is in T

Choose the correct answer from the options given below:

1.    A - II,    B - III,    C - I,    D - IV

2.    A - I,    B - III,    C - II,    D - IV

3.    A - II,    B - III,    C - IV,    D - I

4.    A - II,    B - IV,    C - I,    D - III

NET-DEC-2025

4.    Which of the following languages cannot be accepted by push down automata ?

    A.    L = { aⁿ bⁿ cⁿ : n ≥ 0 }

    B.    L={ a^p  : p is Prime }    

    C.    L={ wcw^R  : w ∈ (a, b)* }

    D.    L={ w ∈ (a, b)* : n_a(w) = n_b(w) }

    E.    L = { aⁿ b^m c^n+m : n ≥ 0, m ≥ 0 }

Choose the correct answer from the options given below:

    1.    A, C & D only

    2.    B, D & E only

    3.    A & B only

    4.    C & D only

NET-DEC-2025

5.    Let P and Q be two regular expressions over ∑. If p does not contain ∈, then the following equation in R namely,

R = Q + RP

has a unique solution given by,

    1.    R = Q* P*

    2.    R = Q P*

    3.    R = PQ*

    4.    R = Q* + P* R

NET-DEC-2025

6.    What is the space complexity of the CYK algorithm for the P table, where n is the number of words in the sentence and m is the number of non terminal symbols in the grammar ?

    1.    O(n³)

    2.    O(nm²)

    3.    O(n²m)

    4.    O(n²m²)

NET-DEC-2025

7.    If r₁ and r₂ are regular expressions, then which of the following are correct. 

    A.    L ( r₁+ r₂ ) = L ( r₁ ) U L ( r₂ )   

    B.    L ( r₁ . r₂ ) = L ( r₁ )  L ( r₂ )   

    C.    L ( ( r₁ ) ) = L ( r₁ )   

    D.    L ( r₁* ) = ( L ( r₁ ) )*   

Choose the correct answer from the options given below:

    1.    A & B only

    2.    B, C & D only

    3.    A, C, & D only

    4.    A, B, C & D 

NET-DEC-2025

8.    Arrange the following in the order of execution while proving a Language is non-Regular using pumping lemma.

    A.    Split in to xyz satisfying pumping lemma conditions.

    B.    Assume the language is regular.

    C.    Choose a string of length ≥ pumping length.

    D.    Show contradiction when pumping y.

Choose the correct answer from the options given below:

    1.    B, C, D, A

    2.    C, D, A, B

    3.    B, C, A, D

    4.    A, B, C, D

NET-DEC-2025

9.    Match the LIST-I with LIST-II

LIST-I Input		LIST-II Compiler Phase
A.	Syntax Tree	I.	Code  Generator
B.	Character  Stream	II.	Syntax  Analyzer
C.	Intermediate Represen- tation	III.	Semantic Analyzer
D.	Token  Stream	IV.	Laxical  Analyzer

Choose the correct answer from the options given below:

1.    A - II,    B - III,    C - IV,    D - I

2.    A - III,    B - IV,    C - I,    D - II

3.    A - III,    B - I,    C - IV,    D - II

4.    A - I,    B - IV,    C - II,    D - III

NET-DEC-2025

10.    Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R.

Assertion A: If L is Regular, then its complement L' is necessarily regular.

Reason R: Complement of a language can be obtained by swapping final and non-final states in a DFA.

In the light of the above statements, choose the most appropriate answer from the options given below

    1.    Both A and R are correct and R is the correct explanation of A.

    2.    Both A and R are correct bur R is not the correct explanation of A.

    3.    A is correct but R is not correct.

    4.    A is not correct but R is correct.

NET-DEC-2025

11.    Arrange the following tasks of Laxical Analyzer in correct sequence:

    A.    Token Generation.

    B.    Removal of comments / White sphere.

    C.    Buffering and reading source characters.

    D.    Return token stream to parser. 

Choose the correct answer from the options given below:

    1.    A, B, C, D

    2.    B, A, C, D

    3.    C, B, A, D

    4.    B, A, D, C

NET-JUNE-2025

1.    Arrange the following parsers in increasing order of their power of handling grammars i.e. from the least powerfull parser to the most powerfull parser.

    A.    LR(0)    B.    LR(1)    C.    LALR(1)    D.    LL(0)    E.    SLR

Choose the correct answer from the options given below:

    1.    LL(0) -> LR(0) -> SLR -> LR(1) -> LALR(1)

    2.    SLR ->  LR(0) -> LL(0) -> LR(1) -> LALR(1)

    3.    LL(0) -> LR(0) -> SLR -> LALR(1) -> LR(1)

    4.    LR(0) -> LL(0) -> SLR -> LR(1) -> LALR(1)

NET-JUNE-2025

2.    Consider the following DFA that generates set of strings over = ∑{a, b, c}    

Now identify that which of the followings is the best description of the language for the above DFA

    1.    L = ( a* + b* + c* )*
    2.    L = ( a + b + c )* (abc)* ( a + b + c )*

    3.    L = {Set of strings, all starting with 'a, b, c' but ending with 'c'}

    4.    L = {Set of strings, all having even count (including 0) of substring 'abc'}

NET-JUNE-2025

3.    Match the LIST-I with LIST-II

LIST-I		LIST-II
A.	Type 3 Grammar	I.	V -> ( V U ∑ )*
B.	Type 2 Grammar	II.	λVβ ->   λ(V U ∑)* β ,  Where  (λ, β)∈  (V U ∑)*
C.	Type 1 Grammar	III.	( V U ∑ )* -> ( V U ∑ )*
D.	Type 0 Grammar	IV.	V -> V∑ | ∑

Choose the correct answer from the options given below:

1.    A -> II,    B -> III,    C -> IV,    D -> I

2.    A -> III,    B -> I,    C -> IV,    D - II

3.    A -> IV,    B -> I,    C -> II,    D -> III

4.    A -> III,    B -> II,    C -> I,    D -> IV

NET-JUNE-2025

4.     Consider the following DFA

    Which of the following NFA is valid for  the given DFA ?

NET-JUNE-2025

6. - to - 10.    Link Questions:

Consider the following Three Address code sample for solving the questions:

100:    t1 = y+2

101:    initial = x / t1

102:    limit = 10

103:    if i>j goto 105

104:    goto 111

105:    if num > b goto 107

106:    goto 111

107:    num = limit - 1

108:    b = y+2

109:    i = i - num

110:    goto 103

111:    i = i - num

112:    k = j+b

6.    Which of the followings is the correct Flow graph for the TAC given in the passage ?   

    1. 

0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0

2. 

0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1

3. 

0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

4. 

0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1

7.    Which of the following is the correct High level code for the given TAC in the passage ?

1.	t1 = y+2 init = x / t1 ; limit = 10; if (i>j | |  num > b) { num =  limit - 1; b = y+2; i = i - num; } j = i - num; k = k+b;	2.	init = x / (y+2); limit = 10; while (i>j | |  num > b) { num =  limit - 1; b = y+2; i = i - num; } j = i - num; k = k+b;
3.	init =  x / (y+2); limit = 10; if (i > j) { while ( num>b) num =  limit-1; } else { b = y+2; i = i - num; } j = i - num; k = k+b;	4.	init =  x / (y+2); limit = 10; while (i > j && num > b) { num = limit - 1; b = y+2; i = i - num; } j = i - num; k = k+b;

8.    What all blocks does Block 3 & Block 5 dominate in the  Flow graph for the TAC given in the passage ?

    1.    Block 3 : 3;        Block 5 : 5

    2.    Block 3 : 3, 4, 5, 6;        Block 5 : 5, 6

    3.    Block 3 : 3, 7;        Block 5 : 5, 7

    4.    Block 3 : 3, 4, 7;        Block 5 : 5, 6, 7

9.    Which of the following is the Optimized version for the given TAC in the passage ?

1.	100:     t1 = y+2 101:    initial = x / t1 102:     limit = 10 103:    if i>j goto 105 104:     goto 111 105:    if num > b goto 107 106:     goto 111 107:    b = y+2 108:     i = i - limit - 1 109:    goto 103 110:    k = i+b	2.	100:     t1 = y+2 101:    initial = x / t1 102:     limit = 10 103:    if i>j goto 105 104:     goto 111 105:    if num > b goto 107 106:     goto 111 107:    b = y+2 108:     i = i - limit - 1 109:    goto 103 110:    k = i+b
3.	100:    t1 = y+2 101:    initial = x / t1 102:    limit = 10 103:    if i>j goto 105 104:    goto 111 105:    if num > b goto 107 106:    goto 111 107:    num = limit - 1 108:    b = y+2 109:    i = i - num 110:    goto 103 111:    i = i - num 112:    k = j+b	4.	100:    t1 = y+2 101:    initial = x / t1 102:    limit = 10 103:    if i>j goto 105 104:    goto 111 105:    if num > b goto 107 106:    goto 111 107:    num = limit - 1 108:    b = y+2 109:    i = i - num 110:    goto 103 111:    i = i - num 112:    k = j+b

10.    What are the various LEADERS (leading statements) for the
TAC given in the passage ?

    1.    100, 102, 103, 104, 105, 107, 110

    2.    100, 103, 105, 107, 111, 112

    3.    100, 103, 105, 106, 107, 111

    4.    100, 103, 104, 105, 106, 107, 111