Mathematics In Computing
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Mathematics In Computing as PDF for free.
More details
- Words: 3,704
- Pages: 11
Question Paper Mathematics in computing (BC131): January 2008 Section A 1.
Answer any two from the four questions given below: × 20 a. Prove i. A È (A ∩ B) =A ii. A ∩ (A È B) = A b.
2.
a.
iv. Find the composition relation R ο R. Prove i. A × (B ∩ C) = (A × B) ∩ (A × C) ii. A × (B ∪ C) = (A × B) ∪ (A × C)
Let
A=
1 −1 2 0 3 4
B=
2 −3 0 1 D= C = 5 −1 −4 2 −1 0 0 3
a.
( 5 marks)
( 5 marks)
( 3 marks) ( 3 marks) ( 2 marks) ( 2 marks) ( 5 marks) ( 5 marks)
2 −1 3 ( 3 marks) ( 2 marks)
Find the Boolean matrices
0 1 0 where A= 1 0 1 B = 1 0 0
4.
( 5 marks)
4 0 −3 −1 −2 3
Find i. AC ii. AD b.
= 40 marks)
( 5 marks)
ii. (A Ç B)1 = A1 È B1 Let R be the relation on the positive integers N defined by the equation x + 3y = 12 that is R = {(x, y) : x + 3y = 12} a. i. Write R as a set of ordered pairs. ii. Domain and Range of R. iii. Find R-1. b.
3.
Prove i. (A È B)1 = A1 Ç B1
(2
1 0 0 1 0 0 be Boolean matrices. 0 1 1
i. A+B ( 3 ii. AB ( 4 iii. A2 ( 4 iv. B2 ( 4 There are six roads between A and B and four roads between B and C. Find the number of ways that one can drive: i. From A to C by way of B. ( 2 ii. Round trip from A to C by way of B. ( 4 iii. Round trip from A to C by way of B without using the same road more than once.
marks) marks) marks) marks)
marks) marks)
b.
i. ii. iii. iv.
( ( ( ( (
Find the number of ways in which five persons can sit in a row. How many ways are there if two of the persons insist on sitting next to one another? Solve part (a) assuming they sit around a circular table. Solve part (b) assuming they sit around a circular table.
4 1 3 3 3
marks) mark) marks) marks) marks)
Section B Answer any two from the three questions given below: × 10
5. 6. 7.
Prove
(2 = 20 marks)
12 22 32 n2 n(n + 1) . + + + ..... + = 1.3 3.5 5.7 (2n − 1)(2n + 1) 2(2n + 1)
( 10 marks)
A coin is weighted so that P(H) = 1/3 and P(T) = 1/2, is tossed until a head or five tails occur. Find the expected number of tosses of the coin. ( 10 marks) State any five laws of the algebra of propositions. ( 10 marks)
Section C Answer any two from the four questions given below: × 20
(2 = 40 marks)
8.
Prove that in a group cancellation laws holds.
( 20 marks)
9.
Define a ring with its axioms.
( 20 marks)
10.
Write the depth-first search algorithms which systematically examine the vertices and edges of a graph G. ( 20 marks)
11.
Explain how the graphs are represented in computer memory? Explain any one method.
( 20 marks)
END OF QUESTION PAPER
Suggested Answers Mathematics in computing (BC131): January 2008 Section A 1.
a.
We will use Venn Diagram to prove, i. Let us assume A & B have some elements in common
AIB
A I (A U B)
A U (A ∩B) =A;
ii.
Let us assume A & B have some elements in common
AUB
b.
We will use Venn Diagram to prove
a.
i.
A I (A U B)
< TOP >
2.
ii.
b.
The ordered pairs are: R= {(0,4),(3,3),(6,2),(9,1),(12,0)} The domain of R is {0, 3, 6,9, 12} The range of the R= {4, 3, 2, 1,0}
iii.
R –1 ={(4,0),(3,3,),(2,6),(1,9),(0,12)
iv.
The composition relation R ο R R ={ (0,4),(3,3),(6,2),(9,1),(12,0)} R = { (0,4),(3,3),(6,2),(9,1),(12,0)} RoR = {(3,3) (12, 4)}
i.
A X (B ∩ C) = (A X B) ∩ (A X C) L.H.S = A X (B ∩ C) B∩C
ii .
=
{(x, y) : x ∈ B, and y ∈ C )
=
{z: z ∈ A} X { ( x, y) : x ∈ B, and y ∈ C}
=
{(z, x) : (z, x) ∈ A X B and (z, y) : (z, y) ∈ A X C }
=
(A X B) ∩ (A X C) = R.H.S
A X (B ∪ C) = (A X B) ∪ (A X C) L.H.S = A X (B U C) B∪C
=
{(x, y) : x ∈ B, or y ∈ C )
=
{z: z ∈ A} X { ( x, y) : x ∈ B, or y ∈ C}
=
{(z, x) : (z, x) ∈ A X B or (z, y) : (z, y) ∈ A X C }
=
(A X B ) ∪ (A X C) = R.H.S
< TOP >
3.
a.
i.
AC
2 −3 0 1 −1 2 A= C = 5 −1 −4 0 3 4 −1 0 0 1(-3)+(-1)(-1)+0 1x2 (-1)5+2(-1) 0x2+3x5+4(-1) 0(-3)+3(-1)+4x0
1x0 + (-1)(-4)+0 0+(3)(-4)+0
2 − 5 − 2 −3 + 1 +4 15 − 4 −3 −12
ii.
−5 −2 +4 11 −3 −12 AD
2 1 −1 2 A= D = −1 0 3 4 3 1x2 + (-1) (-1) + 2x3 9 ⇒ ⇒ 0x2 + 3(-1) + 4x3 9
b.
i.
0 1 0 1 0 0 A + B ⇒ 1 0 1 + 1 0 0 1 0 0 0 1 1 0 + 1 1 + 0 0 + 0 ⇒ 1 + 1 0 + 0 1 + 0 1 + 0 0 + 1 0 + 1
ii.
1 1 0 = 1 0 1 1 1 1
0 1 0 1 0 0 A.B ⇒ 1 0 1 . 1 0 0 1 0 0 0 1 1 0.1 + 1.1 + 0.0 0.0 + 1.0 + 0.1 0.0 + 1.0 + 0.1 ⇒ 1.1 + 0.1 + 1.0 1.0 + 0.0 + 1.1 1.0 + 0.0 + 1.1 1.1 + 0.1 + 0.0 1.0 + 0.0 + 0.1 1.0 + 0.0 + 0.1 0 + 1 + 0 0 + 0 + 0 0 + 0 + 0 ⇒ 1 + 0 + 0 0 + 0 + 1 0 + 0 + 1 1 + 0 + 0 0 + 0 + 0 0 + 0 + 0 1 0 0 1 1 1
iii.
BA
1 0 0 0 1 0 B = 1 0 0 A= 1 0 1 0 1 1 1 0 0 1.0 + 0.1 + 0.1 1.1 + 0.0 + 0.0 1.0 + 0.1 + 0.0 B.A. = 1.0 + 0.1 + 0.1 1.1 + 0.0 + 0.0 1.0 + 0.1 + 0.0 0.0 + 1.1 + 1.1 0.1 + 1.0 + 1.0 0.0 + 1.1 + 1.0 0 + 0 + 0 1 + 0 + 0 0 + 0 + 0 ⇒ 0 + 0 + 0 1 + 0 + 0 0 + 0 + 0 0 + 1 + 1 0 + 0 + 0 0 + 1 + 0 0 1 0 ⇒ 0 1 0 1 0 1 iv.
0 1 0 0 1 0 A2 = 1 0 1 1 0 1 1 0 0 1 0 0 0.0 + 1.1 + 0.1 0.1 + 1.0 + 0.0 0.0 + 1.1 + 0.0 A.A. = 1.0 + 0.1 + 1.1 1.1 + 0.0 + 1.0 1.0 + 0.1 + 1.0 1.0 + 0.1 + 0.1 1.1 + 0.0 + 0.0 1.0 + 0.1 + 0.0 0 +1+ 0 0 + 0 + 0 0 +1+ 0 A2 = 0 + 0 + 1 1 + 0 + 0 0 + 0 + 0 0 + 0 + 0 1 + 0 + 0 0 + 0 + 0 1 0 1 1 1 0 = B2 = 0 1 0 1 0 0 B = 1 0 0 0 1 1 1 0 0 1 0 0 B.B = 1 0 0 . 1 0 0 0 1 1 0 1 1
1.1 + 0.1 + 0.0 1.0 + 0.0 + 0.1 1.0 + 0.0 + 0.1 B.B = 1.1 + 0.1 + 0.0 1.0 + 0.0 + 0.1 1.0 + 0.0 + 0.1 0.1 + 1.1 + 1.0 0.0 + 1.0 + 1.1 0.0 + 1.0 + 1.1 1 + 0 + 0 0 + 0 + 0 0 + 0 + 0 = 1 + 0 + 0 0 + 0 + 0 0 + 0 + 0 0 + 1 + 0 0 + 0 + 1 0 + 0 + 1
4.
a.
b.
i.
1 0 0 = 1 0 0 1 1 1
To draw A to C via B There are 6 roads from A to B. Person can take any one of the roads. There are 4 roads from B to C.Person can take any one of the roads. Hence the number of ways in which a person can drive from A to C via B. P(6,1) x P(4,1) = 6 x 4 = 24 ii. Round trip from A to C by B There are 6 roads from A to B. Person can take any one of the roads. There are 4 roads from B to C. Person can take any one of the roads. In order to return the person can use any one of the road to come back from C to B.(i.e is 4 roads). In order to return from B to A , there are 6 roads to come back from B to A. => P(6,1) x P(4,1) x P(4,1) x P(6,1) => 6 x 4 x 4 x 6 =>576 iii. Round trip from A to C by way of B without using the same road more than once. To travel from A to B there are 6 roads so P(6,1) To travel from B to C there are 4 roads so P(4,1) To travel from C to B there are 3 roads so P(3,1) To travel from B to A there are 5 roads so P(5,1) Þ P(6,1) x P(4,1) x P(3,1) x P(5,1) Þ6x4x5x3 =>360 i. The five people sit in a row = (5)! ways => 120 ii. Two people insist in sitting next to each other, then the two people are considered as one combination, so effectively 4 are used for different arrangements and the two person can also alter the arrangement Þ P(4,1)P(2,1) Þ |4 x |2 Þ 4 x 3 x 2 x 2 = 48 iii.
One person is fixed in circular arrangement. So The different arrangements of the no. of people sitting in the circular table = (5-1)! = 4! = 24 iv.
< TOP >
When two people insist in sitting next to each other, it is considered as one combination. One person is fixed in a circular arrangement. Hence the no of ways in which |3 = 6
Section B 5. 2
1
P (n):
2
+
1.3
2
3.5
3
+
2
+ .......... +
5.7
n
2
(2n − 1) (2n+1)
=
n(n+1) 2(2n+1)
P (n) is clearly true for n =1 that is 1
P (1):
3
1.2
=
2(3)
=
1 3
Suppose P (n) is true. 2
1
1.3
2
+
2
n
+...+
3.5
2
(2n-1)(2n+1)
2
⇒
1.3
2
+
2
3.5
+
2
=
n +n 2(2 n + 1)
+
3
n(n+1) 2(2n+1) ( n + 1)
Adding the next term =
1
=
2
[2( n + 1) − 1][2( n + 1) + 1]
2
n
+
5.7
(n+1)
(2n-1) (2n+1)
2
2
[2(n+1)] - 1
= simply the R.H.S 2
n +n = 4n + 2
+
(n+1) 2
4(n +2n+1) -1
2
n +n = 4n + 2
+
(n+1)
4n + 2
+
2
(n+1)
4n + 2
+
2
(n + 1)
2
2
4n + 6n +2n + 3
2
=
2
4n +8n+3
2
n +n
=
2
4n +8n+4 -1
2
n +n
=
2
n +n 2(2 n + 1)
+
(n +1)
2
2n(2n + 3) + 1(2n + 3)
+
to the R.H.S. & L.H.S
(n+1)
2
[2( n + 1) − 1][2( n + 1) + 1]
< TOP >
2
=
=
n +n
+
2(2n + 1)
(n+1)
2
(2n+3) + (2n+1)
n( n + 1)(2n + 3) +2(n+1)
2
2(2n + 1)(2n + 3) ( n + 1) 2 n + 3n + 2n + 2 2
=
2(2n + 1)(2 n + 3) 2
=
( n + 1) (2n + 5n + 2) 2(2n + 1)(2n + 3) 2
=
=
=
=
6.
( n + 1) (2n + 4n + n + 2) 2(2n + 1)(2 n + 3) ( n + 1) (n+2) (2n+1) 2(2n+1)(2n+3) ( n + 1)( n + 2) 2(2n + 3) ( n + 1)( n + 1 + 1) 2[2(n+1) +1]
= Which is P (n+1) Thus it is seen that P (n+1) is true whenever P (n) is true. By principle of mathematical inductiion true for all n. The possible outcomes are H, TH, TTH, TTTH,TTTTH,TTTTT With respect to independent trials P(H) = 1/3 and P(T) = ½ The random variable X of interest is the number of tosses in each outcome . Thus X(H) = 1 X(TH) = 2 X(TTH) = 3 X(TTTH) = 4 X(TTTTH) = 5 X(TTTTT) = 5 And these X values are assigned the probabilities P(1) = P(H) = 1/3= 1/3 P(2) = P(TH) = 1/3x ½= 1/6 P(3) = P(TTH) = 1/3x 1/2x1/2= 1/12 P(4) = P(TTTH) = 1/3x1/2x1/2x1/2= 1/24 P(5) = P(TTTTH) = 1/2x1/2x1/2x1/2x1/3= 1/48 P(5) = P(TTTTT) = 1/2x1/2x1/2x1/2x1/2= 1/32 Accordingly E(X) = 1x1/3+ 2x1/6+3x1/12+4x1/24+5x1/48+ 5x1/32
P (n) is < TOP >
< TOP >
7.
The laws of the algebra of propositions are: Idempotent laws (1a) p∨ p ≡ p (1b) p ∧ p ≡ p Associative laws (2a) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (2b) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Commutative laws (3a) p ∨ q ≡ q ∨ p (3b) p ∧ q ≡ q ∧ p Distributive laws (4a) p∨ (q∧ r )≡ (p ∨ q) ∧ (p ∨ r) (4b) p∧ (q∨ r )≡ (p ∧ q) ∨ (p ∧ r) Identity Laws (5a) p∨ T ≡ p (5b) p∧ F ≡ p (6a ) p∨ T ≡ T (6b) p∧ F≡ F Complement Laws (7a) p ∨ ~p ≡ T (7b) p ∧ ~ p ≡ F (8a) ~T ≡ F ( 8b) ~ F≡ T Involution law (9)~ ~ p ≡ p DeMorgan’s Laws (10 a) ~ ( p ∨ q) ≡ ~p ∧ ~q (10b) ~(p∧ q) ≡ ~p ∨ ~q
< TOP >
Section C 8.
ab = ac implies b =c & ba = ca implies b =c .( cancellation laws ) According to theorem For all a,x,y belonging to a Group (G,*) if a * x = a*y then x =y and if x * a = y * a then x=y If a * x = a * y then a-1 *(a * x) = (a-1 *a )* y e * x = e *y x=y If x * a = y * a then ( x* a ) * a-1 = ( y* a ) * a-1 x * ( a* a-1) = y * ( a * a -1) x*e=y*e x=y If x * a = y * a then ( x* a) * a
-1 =
( y * a )* a -1
-1 )
9.
x *( a *a = y * ( a * a -1) x*e=y*e x=y < TOP > Rings are a non empty set with two binary operation: an operation of addition and an operation of multiplication. The ring has the following axioms: [R1] For any a, b, c ∈ R we have (a +b) +c = a+ (b +c) [R2] There exists an element 0 ∈ R , called the zero element such that a+0 = 0 +a = a for
every
a∈R.
[R3] For each a ∈ R there exits an element -a ∈ R called the negative of a, such that a + (-a) = (-a)+a =0 [R4] For any a, b ∈ R, we have a+b = b+a [R5] For any a, b, c ∈ R we have (ab)c = a(bc) [R6] For any a , b, c ∈ R we have
10.
11.
i. a(b+c) = ab + ac ii. (b+c)a = ba + ca < TOP > The depth –first Search This algorithm executes a depth first search on a graph G beginning with a starting vertex . Step 1: Initialize all vertices to the ready state (STATUS =1) Step 2: Push the starting vertex A onto STACK and change the status of A to the waiting state (STATUS = 2) Step 3: Repeat Steps 4 and 5 until STACK is empty. processed state Step 4: Pop the top vertex N of STACK . Process N, and set STATUS (N) = 3 , the Step 5: Examine each neighbour J of N i. If STATUS (J) = 1 (ready state ), push j onto STACK and reset STATUS (J) = 2 (waiting state) If STATUS (J) =2 (waiting state) delete the previous J from the STACk and push the current J onto ii. STACK. iii. If STATUS (J) = 3 (processed state ) ignore the vertex J [End of Step 3 loop] Step 6: Exit < TOP > 1. Sequential representation of G by means which uses adjacency matrix. Sequential representation of G by means which uses adjacency matrix. Adjacency matrix: The graph G is a a graph with m vertices and suppose the vertices have been ordered say v1,v2, v3, v4,………..vm .Then the adjacency matrix A =[ aij] of the graph G is the m x m matrix defined by Aij = 1 if v I is adjacent to vj 0 otherwise. The diagram below indicates an adjacency matrix of the graph G , where the vertices are ordered A,B,C,D,E .Observe that each edge { vi, vj} of G is represented twice by aij =1 and aji =1 .So the particular adjacency matrix is symmetric.
2.
The adjacency matrix A of a graph G does depend on the ordering of the vertices of G, that is different ordering of the vertices yields a different adjacency matrix. The drawbacks of the adjacency matrix have the following drawbacks: a. It is difficult to insert and delete vertices in G. b. Suppose the number of edges is O(m) or even O (mlogm) , that is suppose G is sparse. c. The matrix A will contain many zeros, so large memory space will be wasted. Linked representation or adjacency structure of G which uses linked list of neighbors. Let G be a graph with m vertices. The representation of the structure is indicated in the diagram:
The linked representation of a graph G which maintains G in memory by using its adjacency lists will normally contain two files : vertex file and edge file. Vertex file: A vertex file will contain the list of vertices of graph G usually maintained by an array or by a linked list. VERTEX indicates the name of the vertex. NEXT –V: it points to the next vertex in the list of vertices in the vertex file when the vertices are maintained by a linked list. PTR will point to the first element in the adjacency list of the vertex appearing in the edge file. Shaded area :It indicates that other information can be stored in the Edge File: The edges file contains the edges of the graph G. The edge file contains all the adjacency list of G where each list is maintained in memory by a linked list. Each record of the edge file will correspond to a vertex in an adjacency list. Each record has the following information: a. EDGE: It will be the name of the edge b. ADJ points to the location of the vertex in the vertex File. c. NEXT points to the location of the next vertex in the adjacency list. Shaded area :It indicates that other information can be stored in the The diagram below indicates Vertex file and Edge file.
< TOP >
< TOP OF THE DOCUMENT >
Answer any two from the four questions given below: × 20 a. Prove i. A È (A ∩ B) =A ii. A ∩ (A È B) = A b.
2.
a.
iv. Find the composition relation R ο R. Prove i. A × (B ∩ C) = (A × B) ∩ (A × C) ii. A × (B ∪ C) = (A × B) ∪ (A × C)
Let
A=
1 −1 2 0 3 4
B=
2 −3 0 1 D= C = 5 −1 −4 2 −1 0 0 3
a.
( 5 marks)
( 5 marks)
( 3 marks) ( 3 marks) ( 2 marks) ( 2 marks) ( 5 marks) ( 5 marks)
2 −1 3 ( 3 marks) ( 2 marks)
Find the Boolean matrices
0 1 0 where A= 1 0 1 B = 1 0 0
4.
( 5 marks)
4 0 −3 −1 −2 3
Find i. AC ii. AD b.
= 40 marks)
( 5 marks)
ii. (A Ç B)1 = A1 È B1 Let R be the relation on the positive integers N defined by the equation x + 3y = 12 that is R = {(x, y) : x + 3y = 12} a. i. Write R as a set of ordered pairs. ii. Domain and Range of R. iii. Find R-1. b.
3.
Prove i. (A È B)1 = A1 Ç B1
(2
1 0 0 1 0 0 be Boolean matrices. 0 1 1
i. A+B ( 3 ii. AB ( 4 iii. A2 ( 4 iv. B2 ( 4 There are six roads between A and B and four roads between B and C. Find the number of ways that one can drive: i. From A to C by way of B. ( 2 ii. Round trip from A to C by way of B. ( 4 iii. Round trip from A to C by way of B without using the same road more than once.
marks) marks) marks) marks)
marks) marks)
b.
i. ii. iii. iv.
( ( ( ( (
Find the number of ways in which five persons can sit in a row. How many ways are there if two of the persons insist on sitting next to one another? Solve part (a) assuming they sit around a circular table. Solve part (b) assuming they sit around a circular table.
4 1 3 3 3
marks) mark) marks) marks) marks)
Section B Answer any two from the three questions given below: × 10
5. 6. 7.
Prove
(2 = 20 marks)
12 22 32 n2 n(n + 1) . + + + ..... + = 1.3 3.5 5.7 (2n − 1)(2n + 1) 2(2n + 1)
( 10 marks)
A coin is weighted so that P(H) = 1/3 and P(T) = 1/2, is tossed until a head or five tails occur. Find the expected number of tosses of the coin. ( 10 marks)
Section C Answer any two from the four questions given below: × 20
(2 = 40 marks)
8.
Prove that in a group cancellation laws holds.
( 20 marks)
9.
Define a ring with its axioms.
( 20 marks)
10.
Write the depth-first search algorithms which systematically examine the vertices and edges of a graph G. ( 20 marks)
11.
Explain how the graphs are represented in computer memory? Explain any one method.
( 20 marks)
END OF QUESTION PAPER
Suggested Answers Mathematics in computing (BC131): January 2008 Section A 1.
a.
We will use Venn Diagram to prove, i. Let us assume A & B have some elements in common
AIB
A I (A U B)
A U (A ∩B) =A;
ii.
Let us assume A & B have some elements in common
AUB
b.
We will use Venn Diagram to prove
a.
i.
A I (A U B)
< TOP >
2.
ii.
b.
The ordered pairs are: R= {(0,4),(3,3),(6,2),(9,1),(12,0)} The domain of R is {0, 3, 6,9, 12} The range of the R= {4, 3, 2, 1,0}
iii.
R –1 ={(4,0),(3,3,),(2,6),(1,9),(0,12)
iv.
The composition relation R ο R R ={ (0,4),(3,3),(6,2),(9,1),(12,0)} R = { (0,4),(3,3),(6,2),(9,1),(12,0)} RoR = {(3,3) (12, 4)}
i.
A X (B ∩ C) = (A X B) ∩ (A X C) L.H.S = A X (B ∩ C) B∩C
ii .
=
{(x, y) : x ∈ B, and y ∈ C )
=
{z: z ∈ A} X { ( x, y) : x ∈ B, and y ∈ C}
=
{(z, x) : (z, x) ∈ A X B and (z, y) : (z, y) ∈ A X C }
=
(A X B) ∩ (A X C) = R.H.S
A X (B ∪ C) = (A X B) ∪ (A X C) L.H.S = A X (B U C) B∪C
=
{(x, y) : x ∈ B, or y ∈ C )
=
{z: z ∈ A} X { ( x, y) : x ∈ B, or y ∈ C}
=
{(z, x) : (z, x) ∈ A X B or (z, y) : (z, y) ∈ A X C }
=
(A X B ) ∪ (A X C) = R.H.S
< TOP >
3.
a.
i.
AC
2 −3 0 1 −1 2 A= C = 5 −1 −4 0 3 4 −1 0 0 1(-3)+(-1)(-1)+0 1x2 (-1)5+2(-1) 0x2+3x5+4(-1) 0(-3)+3(-1)+4x0
1x0 + (-1)(-4)+0 0+(3)(-4)+0
2 − 5 − 2 −3 + 1 +4 15 − 4 −3 −12
ii.
−5 −2 +4 11 −3 −12 AD
2 1 −1 2 A= D = −1 0 3 4 3 1x2 + (-1) (-1) + 2x3 9 ⇒ ⇒ 0x2 + 3(-1) + 4x3 9
b.
i.
0 1 0 1 0 0 A + B ⇒ 1 0 1 + 1 0 0 1 0 0 0 1 1 0 + 1 1 + 0 0 + 0 ⇒ 1 + 1 0 + 0 1 + 0 1 + 0 0 + 1 0 + 1
ii.
1 1 0 = 1 0 1 1 1 1
0 1 0 1 0 0 A.B ⇒ 1 0 1 . 1 0 0 1 0 0 0 1 1 0.1 + 1.1 + 0.0 0.0 + 1.0 + 0.1 0.0 + 1.0 + 0.1 ⇒ 1.1 + 0.1 + 1.0 1.0 + 0.0 + 1.1 1.0 + 0.0 + 1.1 1.1 + 0.1 + 0.0 1.0 + 0.0 + 0.1 1.0 + 0.0 + 0.1 0 + 1 + 0 0 + 0 + 0 0 + 0 + 0 ⇒ 1 + 0 + 0 0 + 0 + 1 0 + 0 + 1 1 + 0 + 0 0 + 0 + 0 0 + 0 + 0 1 0 0 1 1 1
iii.
BA
1 0 0 0 1 0 B = 1 0 0 A= 1 0 1 0 1 1 1 0 0 1.0 + 0.1 + 0.1 1.1 + 0.0 + 0.0 1.0 + 0.1 + 0.0 B.A. = 1.0 + 0.1 + 0.1 1.1 + 0.0 + 0.0 1.0 + 0.1 + 0.0 0.0 + 1.1 + 1.1 0.1 + 1.0 + 1.0 0.0 + 1.1 + 1.0 0 + 0 + 0 1 + 0 + 0 0 + 0 + 0 ⇒ 0 + 0 + 0 1 + 0 + 0 0 + 0 + 0 0 + 1 + 1 0 + 0 + 0 0 + 1 + 0 0 1 0 ⇒ 0 1 0 1 0 1 iv.
0 1 0 0 1 0 A2 = 1 0 1 1 0 1 1 0 0 1 0 0 0.0 + 1.1 + 0.1 0.1 + 1.0 + 0.0 0.0 + 1.1 + 0.0 A.A. = 1.0 + 0.1 + 1.1 1.1 + 0.0 + 1.0 1.0 + 0.1 + 1.0 1.0 + 0.1 + 0.1 1.1 + 0.0 + 0.0 1.0 + 0.1 + 0.0 0 +1+ 0 0 + 0 + 0 0 +1+ 0 A2 = 0 + 0 + 1 1 + 0 + 0 0 + 0 + 0 0 + 0 + 0 1 + 0 + 0 0 + 0 + 0 1 0 1 1 1 0 = B2 = 0 1 0 1 0 0 B = 1 0 0 0 1 1 1 0 0 1 0 0 B.B = 1 0 0 . 1 0 0 0 1 1 0 1 1
1.1 + 0.1 + 0.0 1.0 + 0.0 + 0.1 1.0 + 0.0 + 0.1 B.B = 1.1 + 0.1 + 0.0 1.0 + 0.0 + 0.1 1.0 + 0.0 + 0.1 0.1 + 1.1 + 1.0 0.0 + 1.0 + 1.1 0.0 + 1.0 + 1.1 1 + 0 + 0 0 + 0 + 0 0 + 0 + 0 = 1 + 0 + 0 0 + 0 + 0 0 + 0 + 0 0 + 1 + 0 0 + 0 + 1 0 + 0 + 1
4.
a.
b.
i.
1 0 0 = 1 0 0 1 1 1
To draw A to C via B There are 6 roads from A to B. Person can take any one of the roads. There are 4 roads from B to C.Person can take any one of the roads. Hence the number of ways in which a person can drive from A to C via B. P(6,1) x P(4,1) = 6 x 4 = 24 ii. Round trip from A to C by B There are 6 roads from A to B. Person can take any one of the roads. There are 4 roads from B to C. Person can take any one of the roads. In order to return the person can use any one of the road to come back from C to B.(i.e is 4 roads). In order to return from B to A , there are 6 roads to come back from B to A. => P(6,1) x P(4,1) x P(4,1) x P(6,1) => 6 x 4 x 4 x 6 =>576 iii. Round trip from A to C by way of B without using the same road more than once. To travel from A to B there are 6 roads so P(6,1) To travel from B to C there are 4 roads so P(4,1) To travel from C to B there are 3 roads so P(3,1) To travel from B to A there are 5 roads so P(5,1) Þ P(6,1) x P(4,1) x P(3,1) x P(5,1) Þ6x4x5x3 =>360 i. The five people sit in a row = (5)! ways => 120 ii. Two people insist in sitting next to each other, then the two people are considered as one combination, so effectively 4 are used for different arrangements and the two person can also alter the arrangement Þ P(4,1)P(2,1) Þ |4 x |2 Þ 4 x 3 x 2 x 2 = 48 iii.
One person is fixed in circular arrangement. So The different arrangements of the no. of people sitting in the circular table = (5-1)! = 4! = 24 iv.
< TOP >
When two people insist in sitting next to each other, it is considered as one combination. One person is fixed in a circular arrangement. Hence the no of ways in which |3 = 6
Section B 5. 2
1
P (n):
2
+
1.3
2
3.5
3
+
2
+ .......... +
5.7
n
2
(2n − 1) (2n+1)
=
n(n+1) 2(2n+1)
P (n) is clearly true for n =1 that is 1
P (1):
3
1.2
=
2(3)
=
1 3
Suppose P (n) is true. 2
1
1.3
2
+
2
n
+...+
3.5
2
(2n-1)(2n+1)
2
⇒
1.3
2
+
2
3.5
+
2
=
n +n 2(2 n + 1)
+
3
n(n+1) 2(2n+1) ( n + 1)
Adding the next term =
1
=
2
[2( n + 1) − 1][2( n + 1) + 1]
2
n
+
5.7
(n+1)
(2n-1) (2n+1)
2
2
[2(n+1)] - 1
= simply the R.H.S 2
n +n = 4n + 2
+
(n+1) 2
4(n +2n+1) -1
2
n +n = 4n + 2
+
(n+1)
4n + 2
+
2
(n+1)
4n + 2
+
2
(n + 1)
2
2
4n + 6n +2n + 3
2
=
2
4n +8n+3
2
n +n
=
2
4n +8n+4 -1
2
n +n
=
2
n +n 2(2 n + 1)
+
(n +1)
2
2n(2n + 3) + 1(2n + 3)
+
to the R.H.S. & L.H.S
(n+1)
2
[2( n + 1) − 1][2( n + 1) + 1]
< TOP >
2
=
=
n +n
+
2(2n + 1)
(n+1)
2
(2n+3) + (2n+1)
n( n + 1)(2n + 3) +2(n+1)
2
2(2n + 1)(2n + 3) ( n + 1) 2 n + 3n + 2n + 2 2
=
2(2n + 1)(2 n + 3) 2
=
( n + 1) (2n + 5n + 2) 2(2n + 1)(2n + 3) 2
=
=
=
=
6.
( n + 1) (2n + 4n + n + 2) 2(2n + 1)(2 n + 3) ( n + 1) (n+2) (2n+1) 2(2n+1)(2n+3) ( n + 1)( n + 2) 2(2n + 3) ( n + 1)( n + 1 + 1) 2[2(n+1) +1]
= Which is P (n+1) Thus it is seen that P (n+1) is true whenever P (n) is true. By principle of mathematical inductiion true for all n. The possible outcomes are H, TH, TTH, TTTH,TTTTH,TTTTT With respect to independent trials P(H) = 1/3 and P(T) = ½ The random variable X of interest is the number of tosses in each outcome . Thus X(H) = 1 X(TH) = 2 X(TTH) = 3 X(TTTH) = 4 X(TTTTH) = 5 X(TTTTT) = 5 And these X values are assigned the probabilities P(1) = P(H) = 1/3= 1/3 P(2) = P(TH) = 1/3x ½= 1/6 P(3) = P(TTH) = 1/3x 1/2x1/2= 1/12 P(4) = P(TTTH) = 1/3x1/2x1/2x1/2= 1/24 P(5) = P(TTTTH) = 1/2x1/2x1/2x1/2x1/3= 1/48 P(5) = P(TTTTT) = 1/2x1/2x1/2x1/2x1/2= 1/32 Accordingly E(X) = 1x1/3+ 2x1/6+3x1/12+4x1/24+5x1/48+ 5x1/32
P (n) is < TOP >
< TOP >
7.
The laws of the algebra of propositions are: Idempotent laws (1a) p∨ p ≡ p (1b) p ∧ p ≡ p Associative laws (2a) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (2b) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) Commutative laws (3a) p ∨ q ≡ q ∨ p (3b) p ∧ q ≡ q ∧ p Distributive laws (4a) p∨ (q∧ r )≡ (p ∨ q) ∧ (p ∨ r) (4b) p∧ (q∨ r )≡ (p ∧ q) ∨ (p ∧ r) Identity Laws (5a) p∨ T ≡ p (5b) p∧ F ≡ p (6a ) p∨ T ≡ T (6b) p∧ F≡ F Complement Laws (7a) p ∨ ~p ≡ T (7b) p ∧ ~ p ≡ F (8a) ~T ≡ F ( 8b) ~ F≡ T Involution law (9)~ ~ p ≡ p DeMorgan’s Laws (10 a) ~ ( p ∨ q) ≡ ~p ∧ ~q (10b) ~(p∧ q) ≡ ~p ∨ ~q
< TOP >
Section C 8.
ab = ac implies b =c & ba = ca implies b =c .( cancellation laws ) According to theorem For all a,x,y belonging to a Group (G,*) if a * x = a*y then x =y and if x * a = y * a then x=y If a * x = a * y then a-1 *(a * x) = (a-1 *a )* y e * x = e *y x=y If x * a = y * a then ( x* a ) * a-1 = ( y* a ) * a-1 x * ( a* a-1) = y * ( a * a -1) x*e=y*e x=y If x * a = y * a then ( x* a) * a
-1 =
( y * a )* a -1
-1 )
9.
x *( a *a = y * ( a * a -1) x*e=y*e x=y < TOP > Rings are a non empty set with two binary operation: an operation of addition and an operation of multiplication. The ring has the following axioms: [R1] For any a, b, c ∈ R we have (a +b) +c = a+ (b +c) [R2] There exists an element 0 ∈ R , called the zero element such that a+0 = 0 +a = a for
every
a∈R.
[R3] For each a ∈ R there exits an element -a ∈ R called the negative of a, such that a + (-a) = (-a)+a =0 [R4] For any a, b ∈ R, we have a+b = b+a [R5] For any a, b, c ∈ R we have (ab)c = a(bc) [R6] For any a , b, c ∈ R we have
10.
11.
i. a(b+c) = ab + ac ii. (b+c)a = ba + ca < TOP > The depth –first Search This algorithm executes a depth first search on a graph G beginning with a starting vertex . Step 1: Initialize all vertices to the ready state (STATUS =1) Step 2: Push the starting vertex A onto STACK and change the status of A to the waiting state (STATUS = 2) Step 3: Repeat Steps 4 and 5 until STACK is empty. processed state Step 4: Pop the top vertex N of STACK . Process N, and set STATUS (N) = 3 , the Step 5: Examine each neighbour J of N i. If STATUS (J) = 1 (ready state ), push j onto STACK and reset STATUS (J) = 2 (waiting state) If STATUS (J) =2 (waiting state) delete the previous J from the STACk and push the current J onto ii. STACK. iii. If STATUS (J) = 3 (processed state ) ignore the vertex J [End of Step 3 loop] Step 6: Exit < TOP > 1. Sequential representation of G by means which uses adjacency matrix. Sequential representation of G by means which uses adjacency matrix. Adjacency matrix: The graph G is a a graph with m vertices and suppose the vertices have been ordered say v1,v2, v3, v4,………..vm .Then the adjacency matrix A =[ aij] of the graph G is the m x m matrix defined by Aij = 1 if v I is adjacent to vj 0 otherwise. The diagram below indicates an adjacency matrix of the graph G , where the vertices are ordered A,B,C,D,E .Observe that each edge { vi, vj} of G is represented twice by aij =1 and aji =1 .So the particular adjacency matrix is symmetric.
2.
The adjacency matrix A of a graph G does depend on the ordering of the vertices of G, that is different ordering of the vertices yields a different adjacency matrix. The drawbacks of the adjacency matrix have the following drawbacks: a. It is difficult to insert and delete vertices in G. b. Suppose the number of edges is O(m) or even O (mlogm) , that is suppose G is sparse. c. The matrix A will contain many zeros, so large memory space will be wasted. Linked representation or adjacency structure of G which uses linked list of neighbors. Let G be a graph with m vertices. The representation of the structure is indicated in the diagram:
The linked representation of a graph G which maintains G in memory by using its adjacency lists will normally contain two files : vertex file and edge file. Vertex file: A vertex file will contain the list of vertices of graph G usually maintained by an array or by a linked list. VERTEX indicates the name of the vertex. NEXT –V: it points to the next vertex in the list of vertices in the vertex file when the vertices are maintained by a linked list. PTR will point to the first element in the adjacency list of the vertex appearing in the edge file. Shaded area :It indicates that other information can be stored in the Edge File: The edges file contains the edges of the graph G. The edge file contains all the adjacency list of G where each list is maintained in memory by a linked list. Each record of the edge file will correspond to a vertex in an adjacency list. Each record has the following information: a. EDGE: It will be the name of the edge b. ADJ points to the location of the vertex in the vertex File. c. NEXT points to the location of the next vertex in the adjacency list. Shaded area :It indicates that other information can be stored in the The diagram below indicates Vertex file and Edge file.
< TOP >
< TOP OF THE DOCUMENT >
Related Documents
Mathematics In Computing
November 2019 9
Computing
October 2019 42
Computing
May 2020 20
Beauty In Mathematics
November 2019 18
Misconception In Mathematics
November 2019 29