Second Terminal Examination
Bachelor of Science in Computer Science and Information
Technology (Second Semester)
Course Title:
Discrete Structure F.M: 80
Course No: CSC 152
P.M: 32
Credit Hour: 3
Attempt all
questions.
Group A [10*2=20]
1. Define
Proposition. How do you define logically equivalent proposition?
2. Show
that (pàr )
∧(qà r) and (p ∨ q)à r are logically equivalent.
3. Sate
which rule of inference is the basis of the following argument: “If it snows
today, the university will close. The university is not closed today.
Therefore, it did not snow today”.
4. Define
product rule in basic counting principle. How many different bit strings are
there of length seven?
5. Define
Recurrence Relation. Determine whether the sequence {an} is a
solution of the recurrence relation an= 2an-1 –an-2 for
n=2,3,4….., where an=5 for every nonnegative integer n.
6. What
form does a particular solution of the linear nonhomogeneous recurrence
relation an=6an-1-9an-2 + F (n) when F (n) =3n?
7. Let
G be the grammar with vocabulary V={S,A,a,b}, set of terminals T={a, b},
starting symbol S, and productions P={SàaA,
Sàb, Aàaa}. What is L(G), the language of this
grammar?
8. What
are the strings in the regular sets specified by the regular expression 10* and
(10)*?
9. Define
m-ary tree and full m-ary tree with suitable tree diagram as examples.
10. Draw
the binary search tree for the following words: Ask, Art, Ate, Able, Alto,
Also, Avid, Ant.
Group B [5*4=20]
11. Show
that the premises “Every living thing is a plant or an animal”, “Hari’s dog is
alive and it is not a plant”, “ All
animals have heart” imply the conclusion “ Hari’s dog has a heart”.
12. What
do you mean by proof by contradiction? Give a proof by contradiction of the
theorem “If a2 is an even
number, then a is an even number”.
13. Define
Binomial Coefficient. Write the general term of the binomial expression. Also
show that the sum of the binomial coefficient is equal to 2n.
14. Define
Euler Circuit and Euler Path. Which of the following simple graphs shown below
have an Euler path?
15. Define
DFA. Construct a DFA whose language is the set of strings that ends with 111
and contains any number of ones and zeros.
Group C [5*8=40]
16. Prove
using mathematical induction that n3 – n is divisible by 3 whenever
n is a positive integer.
17. Define
Linear Non-Homogeneous Recurrence relation. Find all solutions if the
recurrence relation an= 3an-1 + 2n. What is the solution
with a1=3?
18. Define
Minimum Spanning Tree. Use Kruskal’s Algorithm to find a minimum spanning tree
in the weighted graph shown below.
19. Prove
that an undirected graph is a tree if and only if there is a unique simple path
between any two of its vertices.
20. Find
maximal flow for the network shown below.
Bernhardt College
Pre-Semester
Set A
Bachelor Level/First Year/Second Semester/Science
Digital Logic(CSC-151)
Candidates are required to give their answers in their own words as far as practicable. The figures in the margin indicate full marks.
Long Answer Questions.
Attempt any two questions. ( 2 x 10 = 20)
1. Design a 4 bit Asynchronous counter using JK Flip Flop. Draw its timing diagram.
2. Design a BCD adder with logical diagram and truth table.
3. Design a combinational circuit to check for even parity of four bits. A logic-1 output is required when the four bits do not constitute an even parity.
Short Answer Questions.
Attempt any eight questions. (8 x 5 = 40)
1. Given A=19 and B=26 represent them in binary and perform the following operations:
a. A-B (Using 2’s complement)
b. Convert the following as indicated.(i)BAD.FH to Octal (ii)(20.0625)10 to binary
2. Draw the circuit diagram of a D Flip Flop along with its Truth Table and Characteristic equation.
3. Explain PLA in detail.
4. Explain Full Subractor in detail. Design a full subtractor using 3 X 8 Decoder and necessary logic gates.
5. Mention different types of shift registers. Explain any one of them with diagram.
6. Simplify and realize the equation using NOR gates only.
7. Draw a 2 bit up down counter using T Flip Flop. Explain it with its timing diagram
8. What is DMUX? Explain with circuit diagram of 1 to 4 DMUX.
9. Explain state diagram, state table, state reduction and state assignment with suitable example.
10. Simplify using Boolean algebra
a. Y= ((ABC+A’B’)’+BC)
b. Y(WZ’+WZ)+XY
Bernhardt College
Pre-Semester
Set B
Bachelor Level/First Year/Second Semester/Science
Digital Logic(CSC-151)
Candidates are required to give their answers in their own words as far as practicable. The figures in the margin indicate full marks.
Long Answer Questions.
Attempt any two questions. ( 2 x 10 = 20)
1. Design a 4 bit synchronous binary counter using JK Flip Flop. Draw its timing diagram.
2. Design a combinational circuit to check for odd parity of four bits. A logic-1 output is required when the four bits do not constitute an odd parity.
3. What is a magnitude comparator? Explain 4-bit magnitude comparator in detail.
Short Answer Questions.
Attempt any eight questions. (8 x 5 = 40)
1. Given A=26 and B=34 represent them in binary and perform the following operations:
a. A-B (Using 2’s complement)
b. Convert the following as indicated.(i)25H to Decimal (ii)(23.625)10 to Binary
2. Write about RS flip flop with necessary circuit, block diagram, characteristic table and equation.
3. Explain Full Adder in detail. Construct Full Adder using appropriate number of Half Adders.
4. Simplify and realize the equation using NOR gates only.
5. Mention different types of shift registers. Explain any one of them with diagram.
6. Explain ROM with circuit diagram.
7. Explain state diagram, state table, state reduction and state assignment with suitable example.
8. Explain Johnson counter. How it is better than ring counter.
9. Differentiate combinational circuit from sequential circuit.
10. Simplify the following using Boolean Algebra:
a. XY + [XZ]’ + XY’Z[XY + Z]
b. (A+B)’(A’+B)’
No comments:
Post a Comment