Exam Details
Subject | discrete mathematics for computer science (dmcs) | |
Paper | ||
Exam / Course | mca | |
Department | ||
Organization | Gujarat Technological University | |
Position | ||
Exam Date | January, 2019 | |
City, State | gujarat, ahmedabad |
Question Paper
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER- 1 EXAMINATION WINTER 2018
Subject Code: 2610003 Date: 03-01-2019
Subject Name: Discrete Mathematics for Computer Science
Time: 10.30 am to 1.00 pm Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1
Answer the following:
1. Express the following using predicate, quantifier and logical connectives. Also verify the validity of the consequence.
Everyone who graduates gets a job.
Ram is graduated.
Therefore, Ram got a job.
4
2.
Prove ny contradiction that √2 is an irrational number.
3
Draw Hasse Diagram of the Find
1. Maximal and Minimal elements.
2. Greatest and Least members, if exist.
3. Upper bound of and l.u.b. of exist.
4. Lower bound of and g.l.b. of if exist
7
Q.2(a)1.
Define a binary relation. Let X and R 6 be a relation define on x. Write properties of R. Justify your answer.
4
2.
Define a maximal compatibility block. Write maximal compatibility blocks of the compatibility relation given in figure.
1 2
3
4
5
3
1.
Define a group. Show that is a group. Write all the sub group of
4
2.
Show that a sub group of
3
OR
Give an example of
1. A bounded lattice which is complemented but not distributed.
2. A bounded lattice which is distributed but not complemented.
3. A bounded lattice which is neither distributed nor complemented.
4. A bounded lattice which is both distributive and complemented.
4
2.
Two equivalence relation R and S are given by their relation matrices MR and MS . Show that R®S is not an equivalence relation.
MR 1 1
1 1 1
0 0 1
MS 1 1 0
1 1 1
0 1 1
3
Q.3 1.
Show by truth table that the following statement formula is a Tautology.
4
2.
Test whether the given argument is logically valid:
If chris studies, then he will pass the class test. If chris does not play cards, then he will study. Chris did not pass in the class test. Therefore, chris played cards.
3
1.
Define isomorphic lattices. Draw the Hasse diagram of lattices.
1. (S4× S25 2.
Check whether lattices are isomorphic?
3
1
2.
Define complemented lattice. Which of two lattice< Sn, for n 30 and n 45 are complemented? Draw Hasse Diagram of these lattices. Are these lattices distributive? Justify your answer.
4
OR
Q.3
Define cyclic group. Write down the properties of cyclic group. Show that is a cyclic group of order 6 and also find its generators.
7
Find a minimal sum of product form using K-map:
1. xyz xyz' x'yz
2. xyz xyz' xy'z x'yz
7
Q.4
Use Quine McCluskey method to find a minimal sum of product expression of each of the following function:
1.
2.
7
1.
Define a Boolean algebra. Show that in a Boolean algebra,
A b 0
4
2.
Show that the Boolean expression
1.
2. z y are equivalent to each other.
3
OR
Q.4
Define sub Boolean Algebra. Find all sub-algebras of Boolean proper step.
7
1.
Define Join Irreducible element, Meet irreducible element, Atom and Anti atom
4
2.
Explain Stone's Representation theorem with proper examples.
3
Q.5(a) 1.
Define Isomorphic graph.State whether the following diagraphs are isomorphic or not.Justify your answer.
v4 v3
v5
v1 v2
Graph 1
U5
U4 u3
U1 u2
Graph 2
4
2.
Define Nodebase. Is the set{v5,v8,v9,v10} a node base for the following diagraph?Justify your answer.
V1 v2 v5 v6 v9
V3 v4 v7 v8 v10
3
1.
Define weakly connected, unilaterally connected and strongly connected graphs.
3
2.
Define weak,unilateraly and strong components. Find the strong,unilateraly and weak component for the following diagraph.
3 4 6
2
1 5
4
OR
Q.5(a)
Define Path, simple Path, elementary Path. For the graph given in the figure
5 6
4 1
3
2
1. Find an elementary path of length 2 from 1 to 3.
2. Find a simple path from 1 to which is not elementary.
3. Find all possible paths from node 2 to 4 and how many of them are simple elementary?
7
Define a directed tree. Draw the graph of the tree represented by
Obtained the binary tree corresponding to it.
7
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER- 1 EXAMINATION WINTER 2018
Subject Code: 2610003 Date: 03-01-2019
Subject Name: Discrete Mathematics for Computer Science
Time: 10.30 am to 1.00 pm Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
Q.1
Answer the following:
1. Express the following using predicate, quantifier and logical connectives. Also verify the validity of the consequence.
Everyone who graduates gets a job.
Ram is graduated.
Therefore, Ram got a job.
4
2.
Prove ny contradiction that √2 is an irrational number.
3
Draw Hasse Diagram of the Find
1. Maximal and Minimal elements.
2. Greatest and Least members, if exist.
3. Upper bound of and l.u.b. of exist.
4. Lower bound of and g.l.b. of if exist
7
Q.2(a)1.
Define a binary relation. Let X and R 6 be a relation define on x. Write properties of R. Justify your answer.
4
2.
Define a maximal compatibility block. Write maximal compatibility blocks of the compatibility relation given in figure.
1 2
3
4
5
3
1.
Define a group. Show that is a group. Write all the sub group of
4
2.
Show that a sub group of
3
OR
Give an example of
1. A bounded lattice which is complemented but not distributed.
2. A bounded lattice which is distributed but not complemented.
3. A bounded lattice which is neither distributed nor complemented.
4. A bounded lattice which is both distributive and complemented.
4
2.
Two equivalence relation R and S are given by their relation matrices MR and MS . Show that R®S is not an equivalence relation.
MR 1 1
1 1 1
0 0 1
MS 1 1 0
1 1 1
0 1 1
3
Q.3 1.
Show by truth table that the following statement formula is a Tautology.
4
2.
Test whether the given argument is logically valid:
If chris studies, then he will pass the class test. If chris does not play cards, then he will study. Chris did not pass in the class test. Therefore, chris played cards.
3
1.
Define isomorphic lattices. Draw the Hasse diagram of lattices.
1. (S4× S25 2.
Check whether lattices are isomorphic?
3
1
2.
Define complemented lattice. Which of two lattice< Sn, for n 30 and n 45 are complemented? Draw Hasse Diagram of these lattices. Are these lattices distributive? Justify your answer.
4
OR
Q.3
Define cyclic group. Write down the properties of cyclic group. Show that is a cyclic group of order 6 and also find its generators.
7
Find a minimal sum of product form using K-map:
1. xyz xyz' x'yz
2. xyz xyz' xy'z x'yz
7
Q.4
Use Quine McCluskey method to find a minimal sum of product expression of each of the following function:
1.
2.
7
1.
Define a Boolean algebra. Show that in a Boolean algebra,
A b 0
4
2.
Show that the Boolean expression
1.
2. z y are equivalent to each other.
3
OR
Q.4
Define sub Boolean Algebra. Find all sub-algebras of Boolean proper step.
7
1.
Define Join Irreducible element, Meet irreducible element, Atom and Anti atom
4
2.
Explain Stone's Representation theorem with proper examples.
3
Q.5(a) 1.
Define Isomorphic graph.State whether the following diagraphs are isomorphic or not.Justify your answer.
v4 v3
v5
v1 v2
Graph 1
U5
U4 u3
U1 u2
Graph 2
4
2.
Define Nodebase. Is the set{v5,v8,v9,v10} a node base for the following diagraph?Justify your answer.
V1 v2 v5 v6 v9
V3 v4 v7 v8 v10
3
1.
Define weakly connected, unilaterally connected and strongly connected graphs.
3
2.
Define weak,unilateraly and strong components. Find the strong,unilateraly and weak component for the following diagraph.
3 4 6
2
1 5
4
OR
Q.5(a)
Define Path, simple Path, elementary Path. For the graph given in the figure
5 6
4 1
3
2
1. Find an elementary path of length 2 from 1 to 3.
2. Find a simple path from 1 to which is not elementary.
3. Find all possible paths from node 2 to 4 and how many of them are simple elementary?
7
Define a directed tree. Draw the graph of the tree represented by
Obtained the binary tree corresponding to it.
7
Other Question Papers
Subjects
- advance database management system
- advanced biopharmaceutics & pharmacokinetics
- advanced medicinal chemistry
- advanced networking (an)
- advanced organic chemistry -i
- advanced pharmaceutical analysis
- advanced pharmacognosy-1
- advanced python
- android programming
- artificial intelligence (ai)
- basic computer science-1(applications of data structures and applications of sql)
- basic computer science-2(applications of operating systems and applications of systems software)
- basic computer science-3(computer networking)
- basic computer science-4(software engineering)
- basic mathematics
- basic statistics
- big data analytics (bda)
- big data tools (bdt)
- chemistry of natural products
- cloud computing (cc)
- communications skills (cs)
- computer aided drug delivery system
- computer graphics (cg)
- computer-oriented numerical methods (conm)
- cyber security & forensics (csf)
- data analytics with r
- data mining
- data structures (ds)
- data visualization (dv)
- data warehousing
- data warehousing & data mining
- database administration
- database management system (dbms)
- design & analysis of algorithms(daa)
- digital technology trends ( dtt)
- discrete mathematics for computer science (dmcs)
- distributed computing (dc1)
- drug delivery system
- dynamic html
- enterprise resource planning (erp)
- food analysis
- function programming with java
- fundamentals of computer organization (fco)
- fundamentals of java programming
- fundamentals of networking
- fundamentals of programming (fop)
- geographical information system
- image processing
- industrial pharmacognostical technology
- information retrieving (ir)
- information security
- java web technologies (jwt)
- language processing (lp)
- machine learning (ml)
- management information systems (mis)
- mobile computing
- molecular pharmaceutics(nano tech and targeted dds)
- network security
- object-oriented programming concepts & programmingoocp)
- object-oriented unified modelling
- operating systems
- operation research
- operations research (or)
- pharmaceutical validation
- phytochemistry
- procedure programming in sql
- programming skills-i (ps-i-fop)
- programming skills-ii (ps-oocp)
- programming with c++
- programming with java
- programming with linux, apache,mysql, and php (lamp)
- programming with python
- search engine techniques (set)
- soft computing
- software development for embedded systems
- software engineering
- software lab (dbms: sql & pl/sql)
- software project in c (sp-c)
- software project in c++ (sp-cpp)
- software quality and assurance (sqa)
- statistical methods
- structured & object oriented analysis& design methodology
- system software
- virtualization and application of cloud
- web commerce (wc)
- web data management (wdm)
- web searching technology and search engine optimization
- web technology & application development
- wireless communication & mobile computing (wcmc)
- wireless sensor network (wsn)