1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER- III EXAMINATION WINTER 2017
Subject Code: 3630001 Date: 30-12-2017
Subject Name: Basic Mathematics
Time: 10:30 am to 01: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

Let U
X
Y
Z
Compute, XΔY, using Venn Diagram. (Note: XΔY
07

Define Tautology and Contradiction with examples. Prove that is tautology without constructing truth table.
07
Q.2

Let A [001101011] and B [101110001]
Compute, AT, BT
07

Let X Draw a graph of R and also give its matrix. Check whether the given relation an equivalence relation?
07
OR

Write a statement in English corresponding to the following symbolic statements:
x is integer
x is a rational number
x is prime integer
∀x


Use a truth table to determine whether the following statement form is valid:
p q
p r
therefore, p r
04
03
Q.3

Let bed, dog, let, egg} and let the relation R be given as: x,y xRy, if x and y contain some common letters.}
Identify a relation. Draw a graph for R and find maximal compatibility block for the same.
07

Let and the relation be such that x≤y if x divides y. draw the Hasse Diagram of
07
OR
Q.3

Let and s be function X to X given as
07
2
f
g
h
s
Find
Are functions s and f invertible?

Prove that ≡
07
Q.4

Show that, n<2n
07

Draw a flow chart to calculate using recursive procedure.
07
OR
Q.4

What is a relation? Give the properties of relation with a suitable example.
Give example of relation which is both symmetric and anti-symmetric.
04
03
Q.4

Given S
R indicate whether the following are true or false:
S
S
R S
R

Give the power set of the following:
05
02
Q.5

Define sub-graph. Find all sub-graphs for the given graph.
07

Draw di-graph and find in-degree and out-degree of each vertex from the given adjacency matrix. Use adjacency matrix, find total no. of path of length 1 and 2 between each vertex.
A =[111111111]
07
OR
Q.5

Define Tree. Draw a graph of tree represented by

Obtain a binary tree corresponding to it.
07

On a tree in the above question, perform the following traversals:
1. Pre-order traversal
2. Post-order traversal
3. In-order traversal
07