PUNJAB PUBLIC SERVICE COMMISSION
COMBINED COMPETITIVE EXAMINATION FOR RECRUITMENT TO THE POSTS OF
PROVINCIAL MANAGEMENT SERVICE, ETC -2022
CASE NO. 2C2023
SUBJECT: COMPUTER SCIENCE (PAPER-II)
TIME ALLOWED: THREE HOURS
MAXIMUM MARKS: 100
NOTE:
i. All the parts (if any) of each Question must be attempted at one place instead of at different places.
ii. Write Q. No. in the Answer Book in accordance with Q. No. in the Q. Paper.
iii. No Page/Space be left blank between the answers. All the blank pages of Answer Book must be crossed.
iv. Extra attempt of any question or any part of the question will not be considered.
NOTE: Attempt FIVE Questions in All. Attempt at least ONE question from each Section.
SECTION-A
Q No.1: (20 Marks)
Does the TM accept the string 1100? Show the execution of the TM on the input by giving the sequence of configurations from the start to the halting configuration.
Q No.2: (20 Marks)
(a) Construct a Context Free Grammar (CFG) for possible sequences of if and else in ‘C’.
(b) Find the moves of the above grammar to derive the if – else sequence of the string: fiele.
Q No.3: (15+5=20 Marks)
The table below shows the values of the function f(x) at various points x:
(a) Use Lagrange interpolation to find the polynomial of degree 4 that passes through all the given points.
(b) Use polynomial approximation to approximate f(1.5) and f(2.5).
Q No.4: (7+7+6=20 Marks)
1) Convert the following table into 1st normal form.
Convert the following table into 2nd normal form.
B) What is the Hierarchical data model? Explain the hierarchical data model in detail.
C) Explain “Group By* Clause in SQL.
Q No.5: (10+10=20 Marks)
(a) Consider the case, where we are using beam search as an NLP for searching computational cost. Beam search provides a tradeoff between accuracy versus computational cost as of the flexible choice. It is referred to as greedy search algorithm because of its projection. The sample nodes are given as:
Given:
The process of beam search involves:
Beam Size=2
Maximum length of an output sequence= 3.
The candidate nodes output sequences
are AA, CC, ABAB, CECE, ABDABD, and CEDED.
You are required to backtrack the searching nodes and draw/give the tree for that beam search.
(b) Apply the Breadth First Search in the formation of tree data structure as given below to figure out your goal state.
Given: Goal state is 5.
Note:
1) Just mention the values of ‘Q’ and ‘Visited’ queues/lists at every step.
2) No need to draw tree for showing any step.
Contd…..P/3
Q No.6:
“Partition Testing” is one of the strategies to help you select the test cases for testing your system. In Partition testing, you identify groups of inputs that have common characteristics and should be processed in the same way. You should choose tests from within each of these groups.
Now consider a method named “RemoveBlankSpaces* which replaces a sequence of blank spaces with a single space character. Identify the testing partitions and derive a set of tests .e. write down the strings that you will test and the test case that will be applied) for the “RemoveBlankSpaces* method.
Q No.7:
A) What is the intelligent agent in Al, and where are they used?
B) What is overfitting? How can it be overcome in Machine Learning?
C) What is game theory? How is it important in AI?
Q No.8:
Consider the Incremental line algorithm (given below) for drawing a straight line. Two points (2, 3) and (5, 6) are given. You are required to run this algorithm for these points to draw a straight line. Also show the values of variables at each step/iteration against every instruction.
