III B.A./B.Sc. Mathematics 1 Paper IV (Elective -2) - Curriculum ACHARYA NAGARJUNA UNIVERSITY CURRICULUM - B.A / B.Sc MATHEMATICS - PAPER - IV (ELECTIVE - 2) 90 hrs (3hrs / week) MODERN APPLIED ALGEBRA UNIT - 1 (30 Hours) (cid:1)(cid:2)(cid:3)(cid:3)(cid:4)(cid:5)(cid:6)(cid:4)(cid:3)(cid:7)(cid:8)(cid:9)(cid:3)(cid:10)(cid:11)(cid:8)(cid:12)(cid:6)(cid:13)(cid:14)(cid:8)(cid:4)(cid:3)(cid:15) Sets and Subsets, Boolean algebra of sets, Functions, Inverses, Functions on S to S, Sums, Products and Powers, Peano axioms and Finite induction. (cid:16)(cid:2)(cid:3)(cid:3)(cid:17)(cid:13)(cid:8)(cid:7)(cid:18)(cid:19)(cid:3)(cid:18)(cid:5)(cid:20)(cid:7)(cid:6)(cid:13)(cid:14)(cid:8)(cid:4)(cid:3)(cid:15) Introduction, Relation Matrices, Algebra of relations, Partial orderings, Equivalence relations and Partitions, Modular numbers, Morphisms, Cyclic unary algebras. UNIT - 2 (20 Hours) (cid:21)(cid:2)(cid:3)(cid:22)(cid:18)(cid:7)(cid:23)(cid:24)(cid:3)(cid:6)(cid:24)(cid:5)(cid:14)(cid:18)(cid:19)(cid:3)(cid:15) Introduction - Definition of a Graph, Simple Graph, Konigsberg bridge problem, Utilities problem, Finite and Infinite graphs, Regular graph, Matrix representation of graphs - Adjacency matrix, Incidence matrix and examples; Paths and Circuits - Isomorphism, Sub graphs, Walk, Path, Circuit, Connected graph, Euler line and Euler graph; Operations on graphs - Union of two graphs, Intersecton of two graphs and ring sum of two graphs; Hamiltonian circuit, Hamiltonian path, Complete graph, Traveling salesmen problem. Trees and fundamental circuits, cutsets. UNIT - 3 (25 Hours) (cid:25)(cid:2)(cid:3)(cid:3)(cid:10)(cid:13)(cid:8)(cid:13)(cid:6)(cid:5)(cid:3)(cid:4)(cid:6)(cid:7)(cid:6)(cid:5)(cid:3)(cid:26)(cid:7)(cid:12)(cid:24)(cid:13)(cid:8)(cid:5)(cid:4)(cid:3)(cid:15) Introduction, Binary devices and states, Finite state machines, State diagrams and State tables of machines; Covering and Equivalence, Equivalent states, Minimization procedure. (cid:27)(cid:2)(cid:3)(cid:3)(cid:23)(cid:18)(cid:14)(cid:22)(cid:18)(cid:7)(cid:26)(cid:26)(cid:13)(cid:8)(cid:22)(cid:3)(cid:20)(cid:7)(cid:8)(cid:22)(cid:11)(cid:7)(cid:22)(cid:5)(cid:4)(cid:3)(cid:15) Introduction, Arithmetic expressions, Identifiers, Assignment statements, Arrays, For statements, Block strutures in ALGOL, The ALGOL grammar. UNIT - 4 (15 Hours) (cid:28)(cid:2)(cid:3)(cid:3)(cid:17)(cid:14)(cid:14)(cid:20)(cid:5)(cid:7)(cid:8)(cid:3)(cid:7)(cid:20)(cid:22)(cid:5)(cid:17)(cid:18)(cid:7)(cid:4)(cid:3)(cid:15) Introduction, Order, Boolean polynomials, Block diagrams for gating networks, Connections with logic, Logical capabilities of ALGOL, Boolean applications. Prescribed Text Book : “Modern applied Algebra” by Dr. A. Anjaneyulu, Deepti publications, Tenali. Reference Books : 1. Modern applied Algebra by Garrett Birkhoff and Thomas C.Bartee, CBS Publishers and Distributors, Delhi. 2. Graph Theory with applications to Engineering and Computer Science by Narsingh Deo, Prentice-Hall of India Pvt. Ltd., New Delhi. III B.A./B.Sc. Mathematics 2 Paper IV (Elective -2) - Curriculum ACHARYA NAGARJUNA UNIVERSITY CURRICULUM - B.A / B.Sc MATHEMATICS - PAPER - IV (ELECTIVE - 2) MODERN APPLIED ALGEBRA QUESTION BANK FOR PRACTICALS UNIT - 1 (SETS AND FUNCTIONS, BINARY RELATIONS) 1. i) Is the cancellation law A∪B = A∪C⇒ B =C true? If not give example? ii) Is the cancellation law A∩B = A∩C⇒ B =C true? If not give example? 2. Prove that S ⊂ S∩(S∪T)and that S ⊃S∩(S∪T)and S = S∩(S∪T). 3. If A,B,Care three sets, prove that (A−B)−C =(A−C)−(B−C). 4. Find a necessary and sufficient condition for S +T = S∪T where S+T =(S∪T′)∩(S′∪T). 5. Give an example of a function which is a surjection but not injection. 6. Show that the Peano’s successor function is an injection but not surjection. 7. Find the number of functions from a finite set S of n elements to itself. Among these i) how many are surjections ii) how many are injections? 8. Show that the functions f (x) = x3 and g(x) = x1/3 for x∈Rare inverses of one another. 9. Prove by induction in P,m+r =m+s⇒r = s. 10. If f , f ,......, f are injections then show that f f ... f is an injection. 1 2 m mo m−1o o 1 11. Prove by induction that n3 +2n is divisible by 3 for all n≥1. ∑n n(n+1) k = 12. Prove by induction that where nis any positive integer. 2 k=1 13. Let X ={a, b} and Y ={c,d,e}. Write down the tabular representation for the relation α on X and Y defined by the list : aαc, aαd, aα′e, bα′c, bα′d, bαe. 14. Find the matrix of the relation α on X ={a, b}and Y ={c,d,e}which is defined by the list : aαc, aαd, aα′e, bα′c, bα′d, bαe. 15. Give an example of a relation which is neither reflexive nor irreflexive. Also give its graphical represen- tation and relation matrix. 16. If ρ is symmetric, prove that ρ∨ρ2∨...∨ρn is symmetric. 17. Show that a finite poset has a least element iff it has exactly one minimal element. 18. If ρ is reflexive and transitive then show that ρ∧ρ is an equivalence relation on a set S . 19. Let A=(S, f )be a finite unary algebra with kelements. Define aRb in A to mean that for some n∈N, f n(a) =b. Show that Ris reflexive and transitive. 20. Let A=[S, f ] be any finite unary algebra with kelements. Define aRbin Ato mean that for some n∈N, f n(a) =b. Show that Ais cyclic iff for some a∈S, aRb for all b∈S. III B.A./B.Sc. Mathematics 3 Paper IV (Elective -2) - Curriculum UNIT - 2 (GRAPH THEORY) 21. Draw the graph G(V,E)where V ={A,B,C,D,E},E ={AB,AC,BC,DE}. 22. Find the Edge setE of the graph G =(V,E)given by B A C D E 23. Explain Konigsberg bridge problem and draw its graph. 24. Explain three-utilities problem and draw its graph. 0 1 0 1 0    1 0 1 1 0  0 1 0 0 0    25. Draw a graph with the adjacency matrix 1 1 0 0 1    0 0 0 1 0  2 1 3 0    1 0 1 2   26. Draw a graph with the adjacency matrix3 1 0 1    0 2 1 1  1 1 1 0 0 0 0   0 0 0 1 1 1 0  27. Draw a graph with the incidence matrix 1 1 0 1 1 0 1    0 0 1 0 0 1 1  28. Find the adjacency matrix of the graph given by v 4 e e e 8 e 5 7 1 e 4 v v 3 e 1 2 e e 3 6 v 2 29. Find the adjacency matrix of the graph given by D C A B III B.A./B.Sc. Mathematics 4 Paper IV (Elective -2) - Curriculum 30. Find the incidence matrix of the graph given by v e 4 7 e 8 v e 3 e 9 1 e v e4 e5 6 1 e 3 e v 2 2 31. Find the union, intersection and ring sum of the following two graphs. v 1 v1 h v 6 a b a g k v v 2 c 3 d e v2 c v3 l f v 4 G v5 G2 v5 1 32. Show that the two graphs are isomorphic. 33. Show that the following graphs are not isomorphic to each other. v v u u 1 2 1 2 u v v 5 u 5 6 6 u u v8 v 8 7 7 v v u u 4 3 4 3 34. Draw a circuit from the following graph which is of length nine. v 1 v v v 5 6 2 v v 10 7 v v 9 8 v v 4 3 35. Draw all the circuits of the following graph. v 2 e 1 e 5 e 2 e e 4 e 3 6 v e v 1 7 3 III B.A./B.Sc. Mathematics 5 Paper IV (Elective -2) - Curriculum 36. List all paths from v to v in the following graph. 1 8 v e v e 1 1 2 6 e 2 e e 4 5 v e v4 e7 v5 v6 3 3 e e10 e12 e e 9 13 8 v e v 7 11 8 37. Find the eccentricity and centre of the graphs. (i) a (ii) e a d d b b c f c 38. Find the rank and nuclity of the spanning tree. v b 1 1 v 2 c 3 c c b 2 1 2 v b 5 6 v b 4 3 v c 3 b 4 5 c 6 v c v 6 5 7 39. Draw all trees of three labeled vertices. 40. Find the edge connectivity of the complete graph of n-vertices. UNIT - 3 (FINITE STATE MACHINES, PROGRAMMING LANGUAGES) 41. Find the output string when the input string 1101 is run into the following machine. Present v ξ state 0 1 0 1 s s s 0 0 0 1 2 s s s 1 1 1 0 1 s s s 0 1 2 2 1 42. Give the state diagram of the following transition table. Present Next state Output state 0 1 0 1 s s s 0 0 1 3 2 s s s 1 0 2 1 4 s s s 1 1 3 2 1 s s s 1 0 4 4 3 III B.A./B.Sc. Mathematics 6 Paper IV (Elective -2) - Curriculum 43. Draw the state diagram for the following machine Present Next state Output state 0 1 0 1 s s s 0 1 0 1 0 s s s 1 0 1 0 1 s s s 0 1 2 1 3 s s s 0 1 3 2 3 s s s 1 0 4 3 2 s s s 1 0 5 4 5 44. Write the state table of the following machine. 1, 1 0, 0 0, 0 1, 1 s s 1, 1 s 0, 0 s 1, 1 0 0, 0 1 2 3 45. Establish a morphism from Mand Mgiven below : ν ξ ν ξ M M 0 1 0 1 0 1 0 1 a b c 0 1 1 1 2 0 1 b a c 0 1 2 2 1 1 0 c c a 1 0 46. Minimise the number of states in the following machine. Present Next state Output state a a a a 0 1 0 1 1 2 2 1 0 2 3 3 1 0 3 4 4 1 0 4 4 4 0 1 5 5 6 1 1 6 6 5 1 1 47. Minimise the number of states in the following machine. 0, 0 1, 0 0, 1 1, 0 0, 1 0, 0 s s s s s 0 1 1, 0 2 3 4 1, 0 1, 0 0, 0 III B.A./B.Sc. Mathematics 7 Paper IV (Elective -2) - Curriculum 48. Minimise the number of states in the following machine. Present Next state Output state a a a a 0 1 0 1 1 9 1 1 1 2 2 2 1 0 3 7 5 0 1 4 2 2 1 0 5 2 2 1 0 6 3 9 1 0 7 6 8 1 0 8 9 9 1 0 9 4 6 0 0 49. Write the ALGOL expressions for the following Mathematical expressions.  r n x2 + y2 i) a3−b3−3ab(a+b) ii) AB+CDE iii) π(r− p)2 iv) P1+100 v) log 2xy  50. Write the ALGOL expressions for the following Mathematical expressions. i) sin2ex/y ii) sin3x+ y2 iii) eA −sin A2 iv) −b+ b2 −4ac v) 1+ 1  2  2a sin|x| 51. Convert the following ALGOL expressions to conventional mathematical expressions. i) A×B−C ii) A↑(B−C) iii) A↑B−C iv) A/ B−C↑D v) A÷B−C×D Evaluate the above for A=2,B=3,C=4,D=5. 52. Write the mathematical expression for the following ALGOL expressions i) sqrt(s×(s−a)×(s−b)×(s−c)) ii) sqrt(exp(sinA)−cos(A↑5)) iii) −b+sqrt(b↑2−4×a×c)/2×a iv) (exp(x)↑x+exp(1/ x)/(exp(x↑2)+sqrt(x)) v) sqrt(exp(A)−sin(A))/ x↑2 53. Write down the effect of the following for statements. i) for i:=1step 1 until 10 do S; ii) for i:= −4step 2 until 7 do S; iii) for x:=0step 0⋅1 until 1 do S; iv) for x:=1step −0⋅1 until −0⋅5 do S; v) for x:=5step 1 until 4 do S; 54. Write the effect of executing the assignment statements of the following ALGOL block. begin real a,b,c; c:=5; a :=4⋅1; b:=2×a+7; c:=3×a−b; end 55. Write the ALGOL program which generates an array K with K[i]=i! for i =1,2,.....,10. 56. Write ALGOL program to compute the mean of 10 observations. 57. Write an ALGOL program for finding the area of a triangle, given its three sides. III B.A./B.Sc. Mathematics 8 Paper IV (Elective -2) - Curriculum 58. Two one-dimensional arrays X and Y each contain 50 elements. Write the ALGOL program to compute 50 50 LX = Σ X2 (Length of the vector X ), LY = Σ Y2 (Length of the vector Y ) j=1 j j=1 j 50 INPROD = Σ X Y (Inner product of X and Y ) j=1 j j a a a  b  11 12 13 1     A= a a a B = b     59. Write ALGOL program to multiply the matrix 21 22 23 by a column matrix 2 a a a  b  31 32 33 3 ( ) 60. Write down the ALGOL block for finding the roots of ax2 +bx+c=0, a ≠ 0 . UNIT - 4 (BOOLEAN ALGEBRAS) 61. What is two element Boolean algebra. 62. In a Boolean algebra show that x≤ z⇒ x∨(y∧z) =(x∨ y)∧z. 63. In a Boolean algebra prove that (x∧ y′)∨(x′∧ y) =(x∨ y)∧(x′∨ y′). 64. In a Boolean algebra prove that (x∧ y)∨(y∧z)∨(z∧x)=(x∨ y)∧(y∨z)∧(z∨x). 65. Let a,b∈B, a Boolean algebra. If ∨is denoted by + then prove that a+b is an upper bound for the set {a,b} and also a+b=sup{a,b}. 66. Given the interval [a,b] of a Boolean algebra A. Show that the algebraic system [[a,b],∧,∨,∗,a.b] is a Boolean algebra, where x∗ =(a∨x′)∧b,∀x∈[a,b]. 67. Draw the block diagram of p∧(p∨q). 68. Draw the block diagram of (A ∧ A )∨(A′∧ A′) 1 2 1 2 69. Draw the block diagram of ABC∨ A′B′C∨ A′B′C′. 70. Write the gating network representing the Boolean expression (x∨ y)∧(x′∨ y′∨z′)∧(y′∨z). 71. Write the gating network representing the Boolean expression [(x ∨x )∧x′]∨(x ∧x ) . 1 2 3 1 2 72. Write the Boolean expression for the gating network. x y z 73. Show that [(p⇒q)∧(p⇒r)]⇒(p⇒r) is a tautology. 74. Show that (p→q)→[(r∨ p)→(r∨q)] is tautology, regardless of r. III B.A./B.Sc. Mathematics 9 Paper IV (Elective -2) - Curriculum 75. Show that (p′→ p)∧(p→ p′)is an absurdity. 76. Construct the truth table and write the logic diagram for the following Boolean polynomial, P(x,y,z) =(x∧ y)∨(y∧z′). 77. Construct the truth table and write the logic diagram for the following Boolean polynomial, P(x,y,z) =(x∧z)∨(x′∧ y)∨(y∧z) 17⋅3−(x+1)x x <5 F(x) =  78. Write an ALGOL program to compute 19⋅4/(1+x2) x≥5 for x ranging from 0 to 10 in steps of 0⋅1. 3125−xx if x <5 F(x) =  79. Write an ALGOL program to compute (x−5)/(1+x2) if x≥5 for x ranging from 1 to 10 in steps of 0⋅1. 80. Write the ALGOL program which computes the relation matrix for the relation ρ2 where ρ is a binary relation on a set X ={x ,x ,.....,x }. 1 2 n ✦ ✽ ✦ III B.A./B.Sc. Mathematics 10 Paper IV (Elective -2) - Curriculum ACHARYA NAGARJUNA UNIVERSITY B.A / B.Sc. DEGREE EXAMINATION, THEORY MODEL PAPER (Examination at the end of third year, for 2010 - 2011 and onwards) MATHEMATICS PAPER - IV (ELECTIVE - 2) MODERN APPLIED ALGEBRA Time : 3 Hours Max. Marks : 100 SECTION - A (6 6 = 36 Marks) X Answer any SSSSSIIIIIXXXXX questions. Each question carries 6 marks 1. State Peano axioms. 2. Show that the relation m<n means m|n(meaning that m is a divisor of n) is a partial ordering of the set of all positive integers. 3. Explain utilities problem. 4. If a graph (connected or disconnected) has exactly two vertices of odd degree, prove that there must be a path joining these two vertices. 5. Draw the state diagram for the following machine. Present v ξ state 0 1 0 1 1 1 2 0 0 2 2 3 0 0 3 3 4 0 0 4 4 1 0 1 −b+ b2 −4ac  x ab +cd 6. Write ALGOL expressions for i) ii) sin3  iii) 2a  y 4q 7. Define Boolean algebra. 8. Prove that in any Boolean algebra, a∧x =0 and a∨x =1 imply x = a′. SECTION - B (4 16 = 64 Marks) X Answer AAAAALLLLLLLLLL questions. Each question carries 16 marks 9.(a) Prove that a function is left invertible iff it is one one. n n(n+1)(2n+1) (b) Prove by induction that Σ k2 = where n is any positive integer. k=1 6 OR 10.(a) Prove that an equivalence relation on a set S gives rise to a partition on S. (b) If ρ and σ are reflexive and symmetric relations on a set S, then show that the following are equivalent. ρσ ρσ=σρ ρσ=σ∨ρ i) is symmetric ii) iii) . 11.(a) Prove that a connected graph G is an Euler graph iff it can be decomposed into circuits.