KHULNA UNIVERSITY OF ENGINEERING & TECHNOLOGY

B.Sc. Engineering 3rd Year 1st Term Examination.Zfllti

Department of Computer Science and Engineering
CSE 3101
Theory of Computation ·
' TIME: 3 hours FULL MARKS: 210

N.B. i) Answer ANY THREE questions from each section in separate scripts ..
ii) Figures in the right margin indicate full marks.
SECTION A
(Answer ANY THREE questions from this section in Script A)
1. a) Give a comparative discussion about alphabet, language, and power of alphabet. (07)
b) Design a Deterministic Finite Automata (DFA) that accepts the language L such that L={w I (13)
w starts with O and has odd length or starts with 1 and has even length}.· How will you test
the membership of a string using the above DFA?
c) What is the basic difference between the extended transition functions of DFA and (10)
Nondeterministic Finite Automata (NF A)? Explain with an example.
d) How can you verify whether a regular language is empty or not. (05)

2. a) Write regular expression/definition for the following languages; (12)

(i) All strings containing no more than two a's over alphabet {a, b, c}.
(ii) The set of strings of O's and l's whose number of l's is divisible by four and
whose number of O's is even.
(iii) All string of digits with at most one repeated digit.
(iv) All Strings which contain no run's of a's length greater thari two over alphabet
{a, b, c}.
b) Design a NF A that accepts set of all strings. of a's and b's such· that there are two a's (12)
separated by a number of positions that is divisible by 3. Also show the states NFA will be
in during the processing of valid input. ·
c) Convert the following NFA to DFA. (11)

..
· 3� a) Define e-NFA. Consider the following 1;:-NFA (13)

Compute s-closure of each state and find it's equivalent DFA.

· b) Construct an e-NFA equivalent to (0+1)*(0+11). . (10)
c) Prove that if L=L(A) for some DFA A, then there is a regular expression R such that (12)
L=L(R).

· 4. a) Consider the following grammar: (12)

S7ABIAS
A7aAle
B7BB IAB I bb
Answer these questions
(i) What's shortest string it accepts? Are there more than one that length?
(ii) What language does it generate?
(iii) Show this grammar is ambiguous. . .
b) Give a context Free Grammar (CFG) for the language of balanced parenthesis and squared "(12)
brackets. How would you interpret the string "([[00[]]([])])"?
c) Define CFG. Construct a CFG for the given expression: (a+b)(a+b+O+l)* (11)

Page: 1 of2
 SECTIONB
(Answer ANY THREE questions from this section in Script B)
5. a) What is push down automata (PDA)? How does it differ from &-NFA? (07)
b) Construct deterministic PDA to accept the following language, L={if r I n>O}. (11)
c) Prove the theorem, let L be L(PF) for some PDA PF where PF== (Q,L,f,l>F,qo,zo,F)°then there (12)
is a PDA PN such that L = N(PN). .
d) Why is it that the transition function for DPDA's only works for 1 alphabet symbol and 1 (05)
stack symbol?

6. a) Consider the following grammar (25)

87 AACD
A7aAbls
C7 aC la
D7aDa I bDb I s
And simply safe order .
(i) Eliminate s-production,
(ii) Eliminate unit production.
(iii) Eliminate Useless symbols
(iv) Put the grammar in CNF
b) Discuss about PDA acceptance (i) From empty stack to final state and (ii) From final state to (10)
empty stack.

7. a) State pumpinglemma for CFL's and its advantages (06)

b) Use pumping lemma to show the following (i) anbmr! is context free for n � 0, m � 0 and (12)
p=n. (ii) anbmd' is not context free for n � 0, m=2n and p=m+n.
c) Convert the following grammar to a PDA that accepts the same language by empty stack. (10)
S70Sli A
S7IAO IS Is
d) Explain the halting problem of Turing Machine (TM). (07)

8. a) What is meant by a Turing Machine (TM) with.two way infinite tape? Give example(s). (05)
b) Design a Turing Machine (TM) to implement the function "multiplication" using the (14)
subroutine copy. Simulate the action for the input 001000.
c) Let I={a,b,c} and let A={a;b1ck i,j,k�Oandi=jori-k}. Describe a pushdown (10)
automaton (PDA) that recognizes A.
d) Write the differences between single and multi-tape TM. (06)

Page: 2 of2
 . KHULNA UNIVERSITY
. OF ENGINEERING
. & TECHNOLOGY
B.Sc. Engineering 3rd Year 1st Term Examination, 2016"
Department of Computer Science and Engineering
CSE 3109
Database Systems
TIME: 3 hours Fuu;· MARKS: 210
N.B. i) Answer ANY THREE questions from each section: in separate scripts.
ii) Figures in the right margin indicate full marks.. ··
. '·
SECTION A
(Answer °ANY THREE questions from this section in Script A)
1. a) Define attribute and domain of attribute with proper example. -·- - ·---- (05)
b) Represent the following concepts by. entity relationship diagram and hence find the physical (20)
schema of the 'concept.
i) · Attribute with relationship ii) . · Role in a relationship
· . iii) Total and partial participation iv) · Weak entity set
v) Many to many relationship .
c) Consider two entities E1 and E2 having simple and single valued attributes. R1 and R2 are two (10)
relationships between E1 and E2. Rr is one-to-many and R2 is many-to-many relationship. R1
and R2 do not have attributes of their own. Draw an ER diagram. ·

2. a) "In a B+ tree index structure, 50% storage utilization is guaranteed" - justify the system. (06)
b) Give a comparison between (i) primary index and secondary index (ii) dense index and sparse -(10)
index.
c) AB+ tree index structure has height 2 and maximum fan out 5. What is the minimum and (06)
maximum number of keys possible in this index structure?
d) Explain the overflow and underflow situation for a B+ tree index structure. How do you (13)
perform range key query. in a B+ tree index structure?

3. a) Define referential integrity and referential integrity constraints with example. Consider the (13)
following relational database
employee(e-narne, street, city)
works(e-narne, c-name, salary)
company( c-name, city) ,
manages( e-name, m-name) ,·. ·· '
Give an SQL DDL· definition of the database. Identify relational integrity constraints that
should hold and include themin the DDL definition. ·
b) Define trigger. A bank does not allow any negative account balances, the bank deals with (10)
overdrafts by "'
i) setting account balance to zero
ii) creating a loan in the amount of over draft.
iii) giving this loan a loan number identical to account number of the withdrawn account.
Create a trigger on update of the account relation.
c) Define BCNF. When do you prefer 3NF over BCNF? Explain with example. (07).
d) Why are certain functional dependencies called trivial? Give example. (05)

4. a) How can you relate functional dependency and primary key? Consider the patient scheme (10)
PDB( patno, patname, appno, time, doctor) and functional dependencies
F = {patno � patname, patno appno � time doctor, time � appno}. Find the super key of
the schema.
b) A relation R(A, B, C, D, E) is decomposed into R1(A, B, C) and R2(A, D, E). Is the (08)
· decomposition lossless? If the following functional dependencies hold F = {A � BC,
CD � E, B � D, E �A}.
c) What do you mean by document type definition (DTD)? A document of a company contains (12)
following items- ·
. "Report, Section, Subsection, ShortSection, Title, Para, List, Code, Keyword and example"
Report has attribute security having value high / low I medium.
Code and keyword are required field.
Define a DTD for the above document.
d) Give a comparison between XML data and relational data. (05)

Page: 1 of2
 SECTIONB
(Answer ANY THREE questions from this section in Script B)

5. a) What do you mean by database management system? What is the purpose(s) of a database (10)
system?
b) Consider a two dimensional integer array of size nxm that is to be used in your favourite (12)
programming language. Using the array as an example, illustrate the difference
i) Between the three levels of data abstraction
ii) Between a schema and instances.
c) Consider a relation account having· attributes accountnumber, branch_narne and balance. (05)
Write a relation- algebra statement to increase the balances by 5%. ·
d) "SQL is a non procedural language". Do you agree with the statement? Explain with (08)
example. .

in
6. a) Consider the relational database given Fig 01, where the primary keys are underlined. Give (12)
an expression in the relational algebra to express each of the following queries
i) Find the names of all employees in the database who live in the same city and on
the same street as do their managers.
ii) Find the names of all employees in the database who do not work for First Bank
Corporation.
iii) Find the names of all employees who earn more than 'every employee of Small
Bank Corporation.
employee(J,erson-ID, person-name, street, city)
works(person-ID, company-name, salary)
company(company-name, city, minm-salary, maxm-salary, sales)
erson-Il) mana er-name)
Fig. 01 for Q. 6 (a) and Q. 7(a)
b) What is join operation? Why do you need join operation? Explain different types of join (11)
operation.
c) Let the following relation schemas be given: (12)
R = (A, B, C), S = (B, D, E, F) ·
Let relations r(R) and s(S) be given. Give an expression in.SQL that is equivalent to each of
the following queries
i) ITAB (r) [><] f1sc<r) ii) TiiF(uc=i)(r x s))
, '

7. a) Consider the relational database of Fig. 01. Now (i) create a procedure using _SQL to give all (12)
managers of First Bank Corporation a 10% raise unless the salary becomes greater than
$100,000; in such cases give only a 3%. (ii) create a trigger in SQL that checks the 'works'
table before insertion whether the salary is appropriate according to the range mentioned in
'company' table.
b) What do you mean by query processing? Write down the basic steps needed in query (10)
processing. .
c) "Every cascadeless schedule is also recoverable" - justify the statement with example. (06)
d) Why do we need concurrency control for database transaction_ though we have transaction (07)
control?

·s. a) How does a tree protocol ensure deadlock freedom? Explain with example. (10)
b) _ "2-phase locking protocol overcomes the disadvantages of locking protocol". What are .the (10)
disadvantages and how are they solved by 2-phase locking protocol? ·
c) Let relations r1(A, B, C) and r2(C, D, E) have the following properties: r1 has 20,000 tuples, (15)
ri has 45,000 tuples, 25 tuples of r1 fit on one block and 30 tuples of r2 fit on one block.
Estimate the number of block accesses required, using each of the following join strategies
for r1 [><] r2
i) Nested-loop join _ "ii) Block nested loop join ·
iii) _ Merge join

Page: 2 o/2
 KHULNA UNIVERSITY OF ENGINEERING & TECHNOLOGY
B.Sc. Engineering 3rd Year 1st Term Examination, 2016
Department of Computer Science and Engineering
CSE3119
Software Engineering and Information Systems
TIME: 3 hours FULL MARKS: 210
N.B. i) Answer ANY THREE questions fromeach section in separate scripts.
ii) Figures in the right margin indicate full marks.
SECTION A·
(Answer ANY THREE questions from this section in Script A)
1. a) Define system. Explain the basic concept of a system. (12)
b) Why is database a important factor in MIS? Explain. (08)
c) What are the elements of a system? Can you have a viable system without feedback? (10)
d) Write the difference· between Interaction and Interdependence. . (05)

2. a) Define "prototyping" and draw the diagram of the system development life cycle with (09)
prototyping.
b) What are the multifaceted roles to be a good analyst? Describe about those roles (09)
c) What are the bases for planning in system design? Explain. (09)
d) 'W rite the "disadvantages of on-site observation" and "advantages of interview" (08)

3. a) Write the reasons why it is difficult to determine user requirements. (13)

b) What kind of questions can serve as a guide for on-site observations? Explain. (12)
. c) Draw the Data Flow Diagram of a payroll system. . . (10)

4. a) Write the methodologies for system design. Draw the functional decomposition graphic tools. (09)
b) Why do we need system testing? What are the criteria used for system testing? (09)
c) What are the purposes of input design? (08)
d) Why do we need form design? Give the classification of form design. (09)

SECTIONB
(Answer ANY THREE questions from this section in Script B)
5. a) What is software engineering? Briefly discuss about green field projects and activities (12)
common to software engineering projects. . ...
b) Distinguish the followings with example: (08)"
(i) Class variable and Instance variable
(ii) Association and Aggregation
c) Briefly discuss the following terms with example: (09)
(i) Java Interface
(ii) Java Documentation
(iii) Java Exceptions
d) What do you mean by horizontal and vertical framework? Why is java interface considered as (06)
an example of horizontal framework?

6. a) Write the design principle of the Model-View-Controller (MVC) architectural pattern. (09)
b) Write the differences between Deadlock and Livelock. (08)
c) What are the disadvantages of the water fall model? (08)
d) What do you mean by project management? Also write the difficulties and risks in project (10)
management.

7. a) Write down the.activities of a server arid a client. (10)

b) Differentiate the followings: · . · (06)
(i) Generalization and Specialization
(ii) User stories vs. use cases.

Page: 1 o/2
 c) Four example of association is given in the following figure (7(c)). Briefly explain these (08)
associations:
I ·11-
(i) Employee * W_o_kr _s_F_ro l-:_c_
l o_m_p_an_y_....

(ii) I Administrative Assistant I* supervisor

*I
l.. .. Manager

(iii)
1
Office I O ... J AllocatedTo --+
*
'I
Employee
I
IoboardMember
. 3, .... 8 *I
1
(iv) Person Board of Directory

Fig. 7(c)
..
d) Consider the following figure (7(d)): Suppose, we have product class and the information of (11)
new arrivals of products are updated through this class. These updated information are taken
by websites that are detecting information change. Then they show information in their site.
Now, you are going to build this system. Which design pattern is best suited for this system?
State context, problem, forces and solution. (Only UML diagram for solution)

Sitel

Product
Info. update Site2

Fig. 7(d)
8. a) What do you mean by learning curves? Briefly discuss it as a part of usability. (05)
b) From the class diagram and state diagram of the following figures (Fig. 8(b)), write pseudo- (15)
code for course, course section and student class. On the way to write pseudo-code, you must
consider that, every new course registration require completion of prerequisite courses.

Student

n
Course CourseSelection

getPrerequisite() 1
-- * requestToRegister(}
add'Iolcegistrationl.isn)
addToScheduleO
� · hasPassedCourse()
Registration *
'

Fig, 8(b1)

Planned
cancel

cancelled NotEnoughStudents
closeRegistration
requestT oRegister(aStudent)
/createRegistration
classSize 2 minimum
classSize>maximum
closed Enoughfitudents
CloseRegistration

Fig. 8(b2)

c) "A worse form of content coupling occurs when you directly modify an instance variable of (07)
an instance variable"-Explain this statement with pseudo-code.
d) There is trade-off between data coupling and stamp coupling. Increasing one often decreases (08)
the other. Why does this happen? How can we minimize this? Explain with example.

Page: 2 o/2
 KHULNA UNIVERSITY OF ENGINEERING & TECHNOLOGY
B.Sc. Engineering 3rd Year 1st Tenn Examination, 2016
Department of Computer Science and Engineering
ECE 3115
Data Communication
TIME: 3 hours FULL MARKS: 210
N.B. i) Answer ANY THREE questions from each section in separate scripts.
ii) Figures in the right margin indicate full marks. ·
SECTION A
(Ariswer ANY THREE questions from this section in Script A)
1. a) What is meant by 'data' and "signal'? Why digital transmission of data is preferable over (11)
analog transmission?
b) Define channel bandwidth and channel capacity. Prove that rectangular pulse contains infinite (09)
. number of frequency components.
c) What are frequency domain concepts? Draw the frequency spectrum of the following signals (10)
+A sin( 41ifi), (ii) � A sin(61ifi) (iii) A sin(27ifi) + : A sin(81ifi)
. (i) � '.
d) State Shannon Capacity formula. (05)

2. a) What do you mean by guided and unguided transmission medias? Compare various types of (12)
communication medias in terms of bandwidth, attenuation and delay.
b) What are the characteristics of satellite point to point link? (06) .
c) Write down the differences between Coaxial cable and optical fiber. What are the benefits of (10)
optical fiber?
d) Consider a parabolic reflective antenna with a diameter of 2m operating at 12 GHz, what is (07)
the effective area and the antenna gain?

3. a) Compare among PAM, PWM and PPM schemes. Show the step-by-step process to generate (15)
PPM waveform fromany analog signal.
b) Explain DM system. What is the problem in DM and how can we overcome this problem? (10)
c) Compare among ASK, FSK and PSK. Design a PCM system for analog audio frequency. Use (10)
standard sampling frequency and each sample value is encoded by 8 bits.

4. a) What is line coding? Sketch the waveform for the binary sequence 10011011 using the (12)
following methods: (i) Differential Manchester code, (1i) "i3ipol� AMI, (iii) Pseudoternary,
.(iv) NRZI.
b) Briefly explain the QAM technique. Also compare its performance with QPSK. (08)
c) Explain AM, FM and PM using necessary diagrams. ; (06)
d) Explain asynchronous and synchronous data transmission with their frame format. (09)

SECTIONB
(Answer ANY THREE questions from this section in Script B)
5. a) What is Protocol? Write down the functionalities of different layers in OSI model. (08)
b) What is the purpose of flow control in a transmission system in brief? (06)
c) Why does a source break up a large block of data into smaller blocks in stop and wait flow. (06)
control? . .
d) Show sliding window flow control method with diagram. Why is piggy backing used in (07)
sliding window flow control? ·
e) "Sliding window flow control is potentially much more efficient than stop and wait flow (08)
control"-give your comments about this statement and also give reasons in favor of your
comments. :

6. a) Briefly explain ADSL and HDLC. (10)

· b) Why is bit stuffing used in HDLC? A source has a data pattern of 1 I 111 I 00111 I 101. Write (I 0)
the data pattern that will be sent using HDLC.
c) Why is selective reject ARQ more efficient thanGo-Back-N ARQ? (07)
d) A series of IO-bit message M=1010001 l01 is to be transmitted across a data link using CRC (08)
for error detection. A 6-bit pattern P=l 10101 is to be used. Calculate a 5-bit FCS.

Page: 1 o/2
7. a) Why synchronous TDM is called synchronous? (08)
b) Why are headers and trailers not used in synchronous TDM_system? Explain in brief. (08)
c) Draw the block diagram ofFDM and TDM system. · (10)
d) Describe T1 PCM system. ·(09)

8. a) Compare the blocking and non-blocking characteristics of circuit switching devices. (08)
b) Describe the elements and key features ofX.25. (08)
c) Write down the advantages and disadvantages of frame relay. (07)
d) Draw the datagram approach and virtual circuit approach for packet switching. ( 12)

Page: 2 o/2