Exam Details
Subject | discrete mathematical structures | |
Paper | ||
Exam / Course | b.tech | |
Department | ||
Organization | Institute Of Aeronautical Engineering | |
Position | ||
Exam Date | November, 2018 | |
City, State | telangana, hyderabad |
Question Paper
Hall Ticket No Question Paper Code: AHS013
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
Four Year B.Tech III Semester End Examinations (Regular) November, 2018
Regulation: IARE R16
DISCRETE MATHEMATICAL STRUCTURES
Time: 3 Hours (Common to CSE IT Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Show that is a Tautology using truth table.
Show that the statement "Every positive integer is the sum of squares of three integers" is false.
2. Construct the truth table for the formula (PV V :P.
Explain about the tautological implications and logical equivalence using theorem.
UNIT II
3. Show that a relation R defined on the set of real numbers as R if a2 b2 c2 d2.
Show that R is an equivalence relation.
Let Draw the diagram of the graph R and also give its matrix.
4. Illustrate the following function definition with graph. Let X and Y be any two sets. A relation f
from X to Y is called a function if for every x2X there is a unique y2Y such that
Let and Also let f:X→Y be and g:Y→Z be
given by Find gof.
UNIT III
5. Show that the intersection of any two congruence relations on a set is also a congruence relation.
Let and be the algebraic system. Show that is a homomorphic image of
Page 1 of 2
6. Prove using the theorem by showing that the composition of semi group homomorphism is also
a semi group homomorphism.
Let be the algebraic system of natural numbers. Define an equivalence relation E on N
such that x1 Ex2 iff either x1-x2 or x2-x1 is divisible by 4. Show that E is a congruence relation
and that the homomorphism g defined is the natural homomorphism associated with E.
UNIT IV
7. What is the solution of the recurrence relation an for n 2 given that a0
a1 6.
Find the recurrence relation for the Fibonacci sequence.
8. A computer system considers a string of decimal digits a valid codeword if it contains an even
number of 0 digits. For instance, 1230407869 is valid, whereas 120987045608 is not valid. Let an
be the number of valid n-digit codeword's. find the recurrence relation for an.
Find r recurrence relation for Cn, the number of ways to parenthesize the product of n+1 numbers,
x0, x1x2…xn, to specify the order of multiplication. For example, C3=5 because there are five ways
to parenthesize x0, x1x2 x3 to determine the order of multiplication: ((x0.x1)x2).x3 (x0.(x1)x2).x3
(x0. x1) x0.((x1)x2).x3) x0. (x1 (x2 .x3)).
UNIT V
9. Prove that if G is connected graph with n vertices and edges then G is a tree.
Show that the graphs G and H displayed in following Figure 1 are isomorphic.
Figure 1
10. Prove that the chromatic number of a tree is always 2 chromatic polynomial is
Show that neither graph displayed in following Figure 2 has a Hamilton circuit.
INSTITUTE OF AERONAUTICAL ENGINEERING
(Autonomous)
Four Year B.Tech III Semester End Examinations (Regular) November, 2018
Regulation: IARE R16
DISCRETE MATHEMATICAL STRUCTURES
Time: 3 Hours (Common to CSE IT Max Marks: 70
Answer ONE Question from each Unit
All Questions Carry Equal Marks
All parts of the question must be answered in one place only
UNIT I
1. Show that is a Tautology using truth table.
Show that the statement "Every positive integer is the sum of squares of three integers" is false.
2. Construct the truth table for the formula (PV V :P.
Explain about the tautological implications and logical equivalence using theorem.
UNIT II
3. Show that a relation R defined on the set of real numbers as R if a2 b2 c2 d2.
Show that R is an equivalence relation.
Let Draw the diagram of the graph R and also give its matrix.
4. Illustrate the following function definition with graph. Let X and Y be any two sets. A relation f
from X to Y is called a function if for every x2X there is a unique y2Y such that
Let and Also let f:X→Y be and g:Y→Z be
given by Find gof.
UNIT III
5. Show that the intersection of any two congruence relations on a set is also a congruence relation.
Let and be the algebraic system. Show that is a homomorphic image of
Page 1 of 2
6. Prove using the theorem by showing that the composition of semi group homomorphism is also
a semi group homomorphism.
Let be the algebraic system of natural numbers. Define an equivalence relation E on N
such that x1 Ex2 iff either x1-x2 or x2-x1 is divisible by 4. Show that E is a congruence relation
and that the homomorphism g defined is the natural homomorphism associated with E.
UNIT IV
7. What is the solution of the recurrence relation an for n 2 given that a0
a1 6.
Find the recurrence relation for the Fibonacci sequence.
8. A computer system considers a string of decimal digits a valid codeword if it contains an even
number of 0 digits. For instance, 1230407869 is valid, whereas 120987045608 is not valid. Let an
be the number of valid n-digit codeword's. find the recurrence relation for an.
Find r recurrence relation for Cn, the number of ways to parenthesize the product of n+1 numbers,
x0, x1x2…xn, to specify the order of multiplication. For example, C3=5 because there are five ways
to parenthesize x0, x1x2 x3 to determine the order of multiplication: ((x0.x1)x2).x3 (x0.(x1)x2).x3
(x0. x1) x0.((x1)x2).x3) x0. (x1 (x2 .x3)).
UNIT V
9. Prove that if G is connected graph with n vertices and edges then G is a tree.
Show that the graphs G and H displayed in following Figure 1 are isomorphic.
Figure 1
10. Prove that the chromatic number of a tree is always 2 chromatic polynomial is
Show that neither graph displayed in following Figure 2 has a Hamilton circuit.
Other Question Papers
Subjects
- ac machines
- advanced databases
- aircraft materials and production
- aircraft performance
- aircraft propulsion
- aircraft systems and controls
- analog communications
- analysis of aircraft production
- antennas and propagation
- applied physics
- applied thermodynamics
- basic electrical and electronics engineering
- basic electrical engineering
- building materials construction and planning
- business economics and financial analysis
- compiler design
- complex analysis and probability distribution
- computational mathematics and integral calculus
- computer networks
- computer organization
- computer organization and architecture
- computer programming
- concrete technology
- control systems
- data structures
- database management systems
- dc machines and transformers
- design and analysis of algorithms
- design of machine members
- digital and pulse circuits
- digital communications
- digital ic applications using vhdl
- digital logic design
- digital system design
- disaster management
- disaster management and mitigation
- discrete mathematical structures
- dynamics of machinery
- electrical circuits
- electrical measurements and instrumentation
- electrical technology
- electromagnetic field theory
- electromagnetic theory and transmission lines
- electronic circuit analysis
- electronic devices and circuits
- elements of mechanical engineering
- engineering chemistry
- engineering drawing
- engineering geology
- engineering mechanics
- engineering physics
- english
- english for communication
- environmental studies
- finite element methods
- fluid mechanics
- fluid mechanics and hydraulics
- fundamental of electrical and electronics engineering
- fundamental of electrical engineering
- gender sensitivity
- geotechnical engineering
- heat transfer
- high speed aerodynamics
- hydraulics and hydraulic machinery
- image processing
- industrial automation and control
- instrumentation and control systems
- integrated circuits applications
- introduction to aerospace engineering
- kinematics of machinery
- linear algebra and calculus
- linear algebra and ordinary differential equations
- low speed aerodynamics
- machine tools and metrology
- mathematical transform techniques
- mathematical transforms techniques
- mechanics of fluids and hydraulic machines
- mechanics of solids
- mechanism and machine design
- metallurgy and material science
- microprocessor and interfacing
- modern physics
- network analysis
- object oriented analysis and design
- object oriented programming through java
- operating systems
- optimization techniques
- power electronics
- power generation systems
- probability and statistics
- probability theory and stochastic processes
- production technology
- programming for problem solving
- pulse and digital circuits
- reinforced concrete structures design and drawing
- software engineering
- strength of materials - i
- strength of materials - ii
- structural analysis
- surveying
- theory of computation
- theory of structures
- thermal engineering
- thermo dynamics
- thermodynamics
- tool design
- transmission and distribution systems
- unconventional machining processes
- waves and optics
- web technologies