” INSTITUTE OF ENGINEERING Examination Control Division 'ass Marks | 32 Time [3 hes . a) ‘TRIBRUVAN UNIVERSITY 2075 Baisakh Sul ture (CTS) i Candidates are required to give their answers in their own words as far as. practicable. Attempt Al questions. The figures in the margin indicate Full Marks Assume suitable data if necessary. 2) Define proposition. List the various classes of propositions and describe about them. [1+2) b) Using rules of inferences show that the hypothesis “ It is not rainy today and its hotter than yesterday”, “we will go for shopping only if it is rainy”, “If we do not go for shopping then we will go for swimming”, and “If we go for swimming, then we will be home by sunset” lead to the conclusion “we will be home by sunset”. Prove forming the each steps along with their justification. 5) ©) Prove by mathematical induction "4"! +5?*" is divisible by 21 for n as the positive integer”. 18] Design the finite state machine for the implementation of the S - R - Hip-Hop. Design over the input I= {a,b}. [4+4] a) the NDFSA that recognizes the substring siarting with “abb” 5) Define the context sensitive, context- free and regular grammar. Formulate the regular [3+5] grammar for integers. What is recurrence relation? Solve the R-R given by a, =5a,,~6a,.+6" giving the all solutions of it. {8} b) List out the various proof techniques. Describe about the proof by contradiction and proof by equivalences using the suitable examples. 1345) Define planar graph. Is K3, a planar graph? Use hand shaking theorem to find the [2+3+3] a) edges of the graph which consists of 10 vertices each of degree six. spanning tree for the weighted graph b) Use Kruskal’s algorithm to find the minimum (8) given below.5, a) Use Dijkstra’s algorithm to find the length of the shortest path between the verticies » and d in the weighted graph given below. 18) b) Write short notes on: {2x4} (@ Eulerian path and circuits . Gi) Min-cut-Max flow theorem Gii)Caraph Coloring Giv)Bipartite and Complete bipartite graphs eee| Exam, 47 TRIBHUVAN UNIVERSITY INSTITUTE OF | Lever Full Marks 80 Examination Control Division | Programme | BEX, BCT Puss Marks 32 [Year /Part 1/1 ‘Time 3 hs 2074 Bhadra Subject: - Discrete Structure (C7551) Candidates are required to give their answers in their own words as far as practicable. v Y Attempt All questions. Y The figures in the margin indicate Full Marks. Y Assume suitable data if necessary. 1. Use rules of inference to show that the hypothesis “If my cheque book is in office, then I have paid my telephone bill”, “ was looking for phone bill at breakfast of ! was looking for phone bill in my office”, “If I was looking for phone bill at breakfast then my cheque book is on breakfast table”, “If I was looking for phone bill in my office then my cheque book is in my office”, “I have not paid my phone bill” imply the conclusion “My cheque book is on my breakfast table.” . (8) 2. Write the inverse, converse and contrapositive of the statement “I visit temple only if it's Saturday”. Prove that if'n is a positive integer, then n is even if and only if In +4 is even. [345] 3. Define tableau method with its significances? Use mathematical induction to prove the formula for the sum of a finite number of terms of Geometric Progression: (444) ™oari=atartart...+ar= when r # 1, where n is non-negative integer. 4. Given a language, L = {w € {a, b}* : w contain at-least three ‘b’ s} Write the regular expression for L and design a Finite State Automata that accepts the Language L. Your design should include the proper definition of the finite-state automation, transition table and the transition diagram, (2+6) 5, Consider the regular grammar G={N, T, P, 0) where N = set of non-terminal symbols = {o, C}, T= set of terminal symbols = (a, b}, P is the set of production rules = {-rbo, g-3aC, C-bC, Cb} and o being the starting symbol. Construct a non-deterministic finite state automaton equivalent to the given regular grammar. Use this non-deterministic (3+5) ton to generate equivalent deterministic finite state automaton. finite state autom: 6. State linear homogeneous and non-homogeneous recurrence relation with examples. Find all solutions of the recurrence relation: ay ~ 2.1 + 2n? with initial condition a; = 4. [3+5} 1. Use Dijkstra’s algorithm to find the length of shortest path from vertex A to vertex Z. in the following weighted graph. Also highlight the shortest path/paths in the graph: (8)8. State Handshaking Theorem for undirected graph. Define bipartite graph with suitable example. Draw the figure for Complete Bipartite Graph Ky4 and determine its chromatic [2#2+2+2] number. 9. How does Hamiltonian circuit differ from Euler circuit? Define Planar and Regular graphs with suitable examples. {44242} (44) 10. Write short notes on: a) Tree and its applications b) Max-flow Min-cut Theoremay TRIBHUVAN UNIVERSITY | Exam, | | Level ¥ 0) | Programme | BEX,BCT | Pass Marks 42 R 2073 Bhadra (Year /Part | 1/1 Time 3 hrs, Ete Subject: - Discrete Structure (C7551) Candidates are required to give their answers in their own words as far as practicable. Attempt All questions. The figures in the margin indicate Full Marks, Assume suitable data if necessary. Using rules of inference, prove that the hypotheses “If I get my Christmas bonus and my Ariend are free, I will take a road trip with my friends.". "If my friends don't find a job after Christmas, then they will be free.” and "I got my Christmas bonus and my friend did not find a job after Christmas." Lead to the conclusion "I will take a road trip with my friends." (8) . State the principle of strong induction. Prove the formula for the sum of a finite number nv _ ao +5] of terms of Geometric Progression: 0” ,ar! =a tartar? +... When r+ 1, where n is non-negative integer. Explain the validity of arguments with suitable example. Use direct proof to prove "if x is odd then x’ is also odd”. {4+4] . How do you define a Finite State Automation (FSA)? Design a finite state automation that accepts precisely those strings over {a,b}that end with substring aa. Your design should include the proper definition of the finite state automation, transition table and the transition diagram. (2+6) |. Write a grammar that generates the string having the given property. {444} i) String over {a,b} ending with ba ii) String over {a,b} starting with a . Find all the solutions of recurrence relation: {8} a, =7a,.,-12a,..+3" with initial conditions a, =landa, =4 . Draw the figure for the complete graph with 5 vertices (This is usually denoted by Ks). Define the term graph coloring and the chromatic number of a graph in graph coloring. What is the chromatic number of the complete graph Ks and complete bipartite ore aa K33? [2+14142+28. Use Dijkstra's algorithm to find the length of shortest path from vertex A to vertex F in est path/paths in the graph. the following weighted graph. Also highlight the shor Find the two spanning trees of given Graph 10. Write short notes on: i) MaxFlowMincut Theroem ii) Cutsets and Cutvertices ane 18} [444] [44]4 TRIBHUVAN UNIVERSITY INSTITUTE OF ENGINEERING Exam, Level | Fall Marks #0 Examination Control Division Programme | BEX,BCT | Pass Marks | 32 2073 Magh Year/Part | il/il |Time [Bhrs. _____ Subject: - Discrete Structure (C1551) Y Candidates are required to Y Attempt All questions. v v The figures in the margin indicate Full Marks. Assume suitable data if necessary, give their answers in their own words as far as practicable. 1, Hypothesis: "If today is Sunday then I will have a test in MFC and IT, If my IT teacher is sick then I will not have a test in IT. Today is Sunday and my IT teacher is sick." Conclusion: "I will have a test in MFC." Use rule of inference to Prove it. {8} ‘What do you mean by weak principle of mathematical induction? Prove that 5" -1 is divisible by 4 for all n> 1 using Induction method. (3+5] ‘What are the central ideas of formal and informal proofs? Prove that /2 is irrational [4+4] 4, Define Non-Deterministic Finite State Automata. Design a finite-state automation that accepts only those set of strings over {a,b} which ends with aba. Precisely, only those strings which end with aba should accepted and other strings over {a,b} should be rejected. Your design should include the proper definition of the finite-state automation, transition table and the transition diagram. (2+6] 5. Consider the regular grammar G = (N, T, P, o) where N =set of non-terminal symbols = {6, C), T = set of terminal symbols = {a, b}, P is the set of production rules = {arba, o->aC, C->bC, C-rb}and being the starting symbol. Construct a non- deterministic finite state automaton equivalent to the given regular grammar. Use this non-deterministic finite state automaton to generate equivalent deterministic finite state automaton. [444] 6. What do you understand by recurrence relation? Explain in brief. Setup a recurrence relation for the sequence representing the number of moves needed to solves Hanoi Tower puzzle. 7. Draw neat and clean graphs of: Ws (a wheel with 6 peripheral vertices), Ks (a complete graph with 6 vertices, Q; (a 3 dimensional hypercube) and Ko_s (complete bipartite graph). Use graph coloring technique to color each of these graphs and state their respective chromatic numbers. (3+5] [4+4] 8. Find the shortest path from vertex a to vertex Z Highlight the shortest paths in the graph. (6+2) p Zz 9. Explain the Euler circuit and Hamilton circuit with example. State the necessary and the sufficient conditions for them. (2+242+2} 10. Write short notes on: (44) i) Spanning Trees ii) Max-flow min-cut theorem neeTREUVAN COVERT _—. INSTITU’ OF ENGINEERING | Lew [BE Examination Control Division | Programme | BEX, BCI 2072 Ashwin [Year /Part 1/1 Subject: - Discrete Structure (C1551) » ¥ Candidates are required to give their answers in their own words as far as practicable. ¥ Attempt All questions. ¥ The figures in the margin indicate Full Marks. Y Assume suitable data if necessary. 1. Using resolution principle, prove that the hypotheses "If today is Tuesday then I will have a test in Discrete Structure or Microprocessor". If my Microprocessor teacher is sick then I will not have a test in Microprocessor." and "Today is Tuesday and my Microprocessor teacher is sick." lead to the conclusion that "I will have a test in Discrete Structure", [8] 2. Prove that 12 is irrational by giving a proof by contradiction. Draw the tableau for the formula (TVS) > +Q where — denotes the negation of variable, v denotes the disjunction, of variables and -» is the symbol for implication. (543) 3. State the contrapositive and inverse of the conditional statement, "If it snows tonight then I will stay at home". Using mathematical induction technique, prove that the following D statement is true: 3+3*5+3*5*....3*5"=3(5""!-1)/4 whenever n is nonnegative integer. [2+6] 4. Differentiate between a Finite State Machine and a Finite State Automation. Design a Finite State Automata that accepts precisely those string over {a,b} that contains an even no. of a's. Your design should include the proper definition of the Finite State Automata, transition table and the transition diagram. (246) 5. Consider the regular grammar G = (N, T, P, 0) where N = set of non-terminal symbols = {o, C}, T = set of terminal symbols = {a,b}, P is the set of production rules = {->ba, o-raC, C-+bC, Crb} and o being the starting symbol. Construct a non- deterministic finite state automaton equivalent to given regular grammar. Use this non- deterministic finite state automaton to generate equivalent deterministic finite state automaton. [444] 6. Find all the solutions of the recurrence relation: 8] a, =5a,.,—6a,, +2" with initial conditions a, =1and a, =4 7. Explain the Euler path and Euler circuit with the help of a diagram. State the necessary > and the sufficient conditions for Euler circuits and paths. [543] 8. Draw neat and clean graphs of: Cy (a cycle with 7 vertices), Ks (a complete graph with 5 vertices), Qs (a 3 dimensional hypercube) and K3. (complete bipartite graph). Use graph coloring technique to color each of these graphs and state their respective chromatic numbers. (4+4] 9. Use Dijkstra’s algorithm to find the length of shortest path in the following weighted graph. Also highlight the shortest path/paths in the graph: (8) » 7 : 10. Write short notes on: [4+4) i) Maximum Flow Mincut Theorem ii) Handshaking Theorem ii i OF in catalina Sl Bn eaa INSTITUTE OF ENGINEERING — | Level Examination Control Division Y Candidates are required to give their an: rmmuovanunwensiry [xa ALONE TALE Full Marks [80 | BE i ai | Time 2072 Magh ubject: - Discrete Structure (CTSSI) ¥ Attempt All questions. ¥ The figures in the margin indicate Full Marks ¥ Assume suitable data if necessary. Q) Q) ® @ ~ “Gisjunction of variables, 0 6) 6) We are given the following hypotheses: If the Chargers get a good linebacker then the Chargers can eat the Broncos If the Chargers can beat the Broncos, then the Chargers can beat the Jets. If the Chargers can beat the Broncos, then the Chargers can ‘beat the Dolphins. ‘The Chargers get a good linebacker. Show using the rules of inference that the conclusion, the Chargers beat the Jets and the Chargers can beat the Dolphins, follows from the hypatheses. Use mathematical induction to prove that Y= 267 + P= sansnsner + ACT)" = (1--TI)/4 whenever nis anon negative integer Prove that V2 is irrational by giving a proof by contradiction. Draw the tableau for the formula set O= {pHcant), (tvs) 974, AAD} “where > denotes the negati and —> denotes the implication. Differentiate between Deterministic Finite State Automata and Non-Deterministic Finite State Automata. Design a Finite State ‘Automata that accepts precisely those strings over {a, b} that contain an odd number of b’s. Your design should include the proper definition of the finite-state ‘automaton, transition table and the transition diagram. Consider the regular grammar G = (N, T, P, 0) where N= Set of Non-Terminals = {o, A, B}, T= Set of Terminals = {a, b} with productions oa, 0-bB, ADA, AaB, Ab, Aa, Bb and starting symbol 0. Construct a Non-Deterministic Finite State Automata equivalent to the above given regular grammar and convert this into equivalent Deterministic Finite State Automata. Programme | BEX, BCT | Pass Marks | 32 [3 hss. wers in their own words as far as practicable. (8) 8] BG) (5) (4+4)” @) @) (10) ay) Find all solutions of the recurrence relation Ap = 7ap-1 ~ 168.2 + 12a + 04" with initial condition ao = -2, ai = 0 and a2 = 5. Use Dijkstra’s algorithm to find the length of the shortest path between the vertices @ and z in the weighted graph displayed below. b 5 In a round-robin tournament the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles, and the Cardinals beat the Orioles. Model this outcome with a directed graph. Draw the figure for the complete bipartite graph Kas and the cycle raph with 6 vertices (This is usually denoted by Ce). What is the chromatic number of thé drawn complete bipartite graph Kas and the cycle graph Cs. Explain the Hamiltonian path and Hamiltonian circuit with the help of a diagram. (12) Write short notes on: - a) Spanning tree b) Max flow and Min cut theorem c) Planar graphs (8) {8} (4) (2+2+2+2] (3) (3+3+3]472 TRIBHUVAN UI ITE OF E Examination Control Division Programme BL% BCT Year /Part_ 0 Time 2071 Bhadra E a BE Pass Marks 5 ubject: - Discrete Structure (C7 ses in their own words as far as practicable © Candidates are required to give their answ: v Attempt All questions. ¥ The figures in the margin indicate Full Marks y¥ Assume suitable data if necessary. “tt is note raining or Sita has her umbrella,” “Sita 1. Use resolution to show the hypothesis » and “It is raining or Sita does not get doesnot have her umbrella or she does not get wet, wes” inaply tat “Sik dues mut ge! et.” {8} ‘Use mathematical induction to show that +n =[n(n + 1/2] whenever nis a positive integer. Se-te the converse, contrapositive and inverse for the conditional statement, “Igo 10 the : B beach whenever it is a sunny summer day.” 4. Why is a tableau method important in. pro formula * © =(pr-95 p++ positional logic? Draw the tableau for the (243) Where + denotes the negauon of a variaole, denotes ine conjunction of variabics and + denotes the implication. Ss Differentiate between Finite State Machines and Finite State Automata. Design a Finite State Automata that accepts precisely those strings over {a, b} that contain an odd the proper definition of the finite-state number of b’s. Your design should include automation, transition table and the transition diagram. (246) 6 Consider the regular grammar G = (N, T, P, o) where N = Set of Non-Terminals = [474] {o, A. B}, T= Set of Terminals = {2, b} with productions. o— aA, o>bB, Aa, Ba and starting symbol o. Construct a Non-Deterministic Finite State Automata equivalent to the above given regular grammar and convert this into equivalent Deterministic Finite State Automata. __-7-Find-all solutions.of the recurrence relation eine aphieen AOLeen the vertices @ and F et th betwe 8. Use Dijkstra’s algorithm t6 find the Haat of HF shortest pane (8) Zin the weighted graph displayed below d z 9, Draw the figure for the complete grat with 6 verticeS (his is usualy arise Define the tenn graph coloring andthe chromatic mumPer of a grap! 3 24247} chromatic number of the complete gap Ke? : . 10. Explain the Hamiltonian path and Hailtonia ciscuit with the help of @ diagram. State the nécessary and sufficient conditioss for Euler circuits and paths. How is Euler circuit different from the Hamiltonian circuit? (3+242] 11. Write short notes on: [3+3+3) a) Spanning tree b) Cutsets and Cutvertices c) Application of trees +e PE eer eeat Soe ™ a #6 Bean. am Full Maras 80 : 45 REBUY AN LN TUTE OF ENGINGE, e RING Lovet Ot CT Pass Marks Examination Control Division! | Programme Ba y ae ie Year / Part . 2071 Magh bject. - Discrete Structure (C7. ¥, Candidates are required to give their answers in their own words as far as practicable ¥ Attempt AU questions. Y, The figures in the margin indicate Full Marks Y Assume suitabie data if necessary. 1. Construct an argument using rules of inference to show that the hypothesis “All movies produced by John Sayles are wonderful. John Sayles produced a movie about coal vere] imply the conclusion, “There is a wonderful movie about coal miners.” You are require’ to show cach step and give reasons for those steps before you come to the desired . conclusion from the hypothesis. ie Use mathematical induction to show that 6 divides-n’ - n whenever n is a nonnegative integer. (8) 3. IEP=F, Q=T, S=T,R=F, then find truth value of: {4+4] a), S> (PAR) AGP >(RVQ)AS) by (PADS QAR) CVO 4. Define Non-Deierministic Finite State Automata, Design a Finite State Automata that accepts precisely those strings over {a, b} that do not contain two consecutive a’s. [2+6) 5. Construct the regular grammar to generate integers, Your construction should include the proper definitions of the grammar, which includes properly defined non-terminal 18] symbols, terminal symbols, production rules and starting symbol. 6. Find general solution of Ja, = Ja, +24, us 2 fength of the shortest patn oetween ine vertices a and layed below. e Ie) (8} 8. Ina rounc-robin tournament the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioies, and the Cardinals beat the Orioles. Model this outcome with a directed graph. (} 9. Draw the figure for the complete bipartite graph Ks. and the cycle graph with 5 vertices (This is usually denoted by C;). What is the chromatic number of the drawn complete bipartite graph Ks, and the cycie graph C3? [2+2+2 10. State the necessary and sufficient conditions for Euler circuits and paths. 11. Write short notes on: iy a) Hamiltonian path and Hamiltonian circuit b) Max flow and Min cut theorem ©) Planar graphsExam. 37 TRIBHUVAN UNIVER: INSTITUTE OF ENGINEERING Level BE ‘hs | 80. Examination Control Division Programme BEX, BCT Pass Marks 32 2070 Bhadra Year /Part lil Time 3 hrs, t rete Structure (CTS51) _ Subject: - Di Cant lates are required to give their answers in their own words as far as practicable. ¥ VY. Attempt All questions. The figures in the margin indicate Full Marks, Y Assume suitable data if necessary ,S=T,R =F, then find truth value of: [4+4] HP=F, Q= a) (S>(PAR)A(P>(RVQ)AS) b) (PADS (QAR) SVD , show that the hypothesis “It is not rainy today and its hotter 2. Using rules of inference than yesterday”, “We will go for movie only if it is rainy”, “If we do not go for movie, then we will go for shopping”, and “If we go for shopping, then we will be home by sunset” lead to the conclusion “We will be home by sunset”. You are required to show each steps and give reasons for those steps before you come to desired conclusion from the hypothesis. 8} 3. Prove by Mathematical Induction: (31 3.443.454 +a(n+1) (a +2)=n(n+ 1) (n+2)(n+3)/4 sad 4, Design a Finite State Machines (FSM) that performs binary serial addition. Define DFA and NDFA. Construct DFA that recognize the language “The set of bit brings that do not contain three consecutive 0’s. Show only necessary figures and state diagrams. (3+243] 5, Define and differentiate between context-sensitive, context free and regular grammars with suitable examples. Explain in short the role of regular expressions. [6+2} 6. What do you understand by recurrence relation? Explain in brief. Derive and solve the recurrence relation for Tower of Hanoi puzzle. [2+6 7. IsKs3 graph a planar graph? Explain it with suitable reasons. [4+4] 8. Define Regular and Bipartite graphs with suitable examples. Bh [242] 9. Define level and height of tree? What is full m-ary tree and balanced tree? 10, State the handshaking theorem for the undirected graph and use it to prove the theorem (+4) that an undirected graph has an even number of vertices of odd degree. (44] 11. Write down the short notes on the following: a) Maximum Flow Mincut Theorem b) Graph Coloring4. 6. 7 Putt Marks 9 BOT Pase Marke Br Ws it Time ir Year (Part 2070 Magh Subject: - Discrete Structure (C755! Candidates are required to give their answers in their own words as far as practicable Attempt All questions. The figures in the margin indicate Full Marks Assume suitable data if necessary. Construct an argument using rules of inference to show that the (8) hypotheses "Randy works hard,” “If Randy works hard, then he is th 18) + Use mathematical induction to show that Pa ae we te =n(ar lI) Qn+1)/6 whenever n is a positive integer. Sto*e tha converse, contrapositive and inverse for the conditional [3] statement, “A positive integer is a prime only if it has no divisors other tren | and itself.” (243] Define satisfiable and unsatisfiable formulas. Draw the tableau for the formula = (pags) / re = denotes the necation of a variable, v. dente aisjunction of variables and ~ denotes the conjunction of the: variables. = . Define Finite State Machines. Design a Finite State Automata that [2+6] accepts precisely those strings over {a, b} that contain two consecutive a's. Your design should include the proper definition of the finite-state automaton, transition table and the transition diagram. Consider the reguiar grammar G = (N, T, P, 6) where N= Set of (4+4] Non-Terminals A, B}, T= Set of Terminals = {a, b} with productions A, A->bA, AvvaB, A->b, Aa, Bb and starting a Non-Deterministic Finite State Automata equivalent to nvert this into equivalent — Co! the above given regular grammar and Deterministic Finite State Automata. Find all solutions of the recurrence relation Ay = 28.1 + 2° with initial condition ap =37 TRIBHUVAN UNIVERSITY Exam. Me INSTITUTE OF ENGINEERING | Level TBE TFullMarks 800 1 Examination Control Divisione] Programme | BCT | Pass Marks | 32 2069 Bhadra Year/Part |il/it | Time | 3hrs Subject: - Discrete Structure (CTS51) Y Candidates are required to give their answers in their own words as far as practicable. Y Attempt All questions, ¥ The figures in the margin indicate Full Marks — Assume suitable data if necessary. 1 ey & Construct an argument using rules of inference to show that the [8] hypotheses "If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on," "If the sailing race is held, then the trophy will be awarded," and "The trophy was not awarded" imply the conclusion "It rained." You are required to show each step and give reasons for those steps before you come to the desired conclusion from the hypotheses. (8) Use mathematical induction to prove the inequality n < 2° for all positive integers n. Why tableau method is important in the propositional logic? Draw the [2+6=8) tableau for the formula set = {(pang)s, =qQV—1, prt} where — denotes the negation of a variable, V denotes the disjunction of variables, ~ denotes the conjunction of variables and —> denotes the implication. Differentiate between Deterministic Finite State Automata and [2+6= 8) Non-Deterministic Finite State Automata, Design a Finite “State Automata that accepts precisely those strings over {a, b} that contain an even number of a’s. Your design should include the ~ proper definition of the finite-state automaton, transition table and the transition diagram. Consider the regular grammar defined by T={a, b}, N={o, C} with productions obo, o-aC, C->bC, Cb and starting symbol o. Construct a Non-Deterministic Finite State Automata equivalent to the above given regular grammar and convert this into equivalent Deterministic Finite State Automata. [4+4=96 Find all solutions of the reourrence-relation iy = Tap-1 ~ 168.2 + 1249-3 + na” with initial condition ag = -2, a1 = 0 and a2 = 5. to find the length of the shortest path Jr Use Dijkstra’s algorithm dz in the weighted graph displayed between the vertices a an below. c 3 € 8 Draw the figure for the complete bipartite graph Kas and the cycle graph with 6 vertices (This is usually denoted by Cs). ‘What is the chromatic number of the drawn complete bipartite graph Kas and the cycle graph Cs. Detine a tree and discuss its various properties as well as a, applications of trees. 10 Write short notes on: - a) Eulerian graph b) Max flow, min cut theorem c) Planar and regular graphs (3) {8} \ (2+2+2+2] (142+4=7] (343439) 437 TRIBHUVAN UNIVERSITY “Exam INSTITUTE OF ENGINEERING —_, Level BE Full Marks 80 | Programme BEX, BCT _ Pass Marks 32 thes Examination Control Division Time B® 2069 Poush Year/Part W701 cture (CTS) Candidates are required to give their answers in their own words as far as practicable. Attempt AU questions. The figures in the margin indicate Full Marks Assume suitable data if necessary. 1. Construct the truth table for (p v + q)-> 4. and state the converse, contra- positive and inverse of each of these conditional statements. 2343}. L_ Ifit snows tonight then I will say at home Ti. A positive integer is a prime only if it has no divisors other than 1 and itself. Shaw that «(pv (—'p Aq)Jand = p A-q are logically equivalent by is} jeve.oping 2 series of logical equivalence. 3. For the set of premises “If I play hgckey, then ] am sore the next day.” “I use the whirlpool if I am sore.” “I did not use the whirlpool”. What relevant ion can be d:awn? Explain the rules of inference used to draw the (41 conciusion. i. Prove the theorem “if nis a positive integer. then n is odd iff and only if n‘is odd” using proof of equivalence. ro} 5. Use the mathematical induction to prove the inequality n< 2° for all positive integer n. ial 6. » Define DFA and NDFA. Construct DFA that recognize the language “The set of pe bit strings that do not contain three consecutive.0's +. Let G be the grammar with vocabulary V={S, 0, 1}, the set of terminals 1= {0, 1), starting symbol and Production rule (S-> 118, S-»0} What is L(G), the Tanguage of this grammar? Derive the derivation tree for the derivation 01111 of this grammar. §. What is a recurrence relation? Is there any such relation which exists for the Tower of Hanoi (TOH) puzzle. If yes, then derive. Also show that your solution is optimal. [2+4+2] [2x4] [5+3] 9. Define and draw the following graphs. 1. Complete Graph Ke TI. Complete Bipartite Graph Ks, 5 IL. Cycle Graph Ce TV. Wheel Graph We {0. Define cut vertex and cut edge (bridge) and find all the cut edges in the graph given below. pez1 12. Discuss Euler and Hamilton circuit with examples. (043 Define planar graph and show that the complete graph Ks is not planar and find the chromatic tiumber of Ks. [asd+3} Write-short notes on: . (2x4), (a) Max flow and Mincut theorem (b) Spanning tree ee~” I Regular 37 TRIBHUVAN UNIVERSITY exam. | INSTITUTE OF ENGINEERING Level {Bi Full Marks | #0 Examination Control Division | Programme | BEX, BCT Pass Marks Wil Fime This 2068 Bhadra Year / Part ~ Discrete Structure Subjec Y Candidates are required to give their answers in their own words as far as practicable Y Attempt A questions, Y The figures in the margin indicate Full Marks VY Assume suitable data if necessary. 1) Using rules of inferences, show that the hypotheses “If you send me an e-mail message, then Iwill finish writing the program,” “If you do not send me an e-mail message, then | will go to sleep early,” and “If I go to sleep early, then I will wake up feeling refreshed” lead to the conclusion “If I do not finish writing the program, then | will wake up feeling refreshed.” You are required to show each steps and give reasons for those steps before you come to the desired conclusion from the hypotheses. © 2) Use mathematical induction to prove that (8) BH3-SHB S43 SPH 3ST 1/4 whenever n is a nonnegative number. 3) Prove that V2 is irrational by giving a proof by contradiction. Draw the tableau for the formula (TVS) —+ ~Q where ~ denotes the negation of a variable, V denotes the disjunction of variables and —* is the symbol for implication. (S+3) 4) Design a finite-state automaton that accepts only those set of strings over {a, 6) which starts with baa. Precisely, only those strings which begin with baa should be accepted and other strings over {a, 5) should be rejected, Your design should include the proper definition of the finite-state automaton, transition table and the transition diagram. (34243) 5) Discuss regular expressions and regular languages in detail with suitable examples. Explain the different properties of regular languages. (444) 6) Find all solutions of the recurrence relation, (8) aq = 2a. + 3" with initial condition a, = 5. 7) Use Dijkstra’s algorithm to find the length of the shortest path between the vertices a and z in the weighted graph displayed below. (8) 2 5 d e 10 e 8) Draw the figure for the complete bipartite graph Ks4 and the cycle graph with 5 vertices (This is usually denoted by Cs). What is the chromatic number of the drawn complete bipartite graph K3,4 and the cycle graph Cs, (2+2+2+2) 9) ‘State the’handshaking theorem for the undirected graph and use it to prove the theorem that an undirected graph has an even number of vertices of odd degree. Q4) 10) Write short notes on: = (44383) a) Eulerian graph b) Hamiltonian graph c) Spanning tree7 TRIBFIUVAN UNIVERSITY Exam. INSTITUTE OF ENGINEERING Level Examination Control Division Programme BEX, BCI 2068 Magh Year /Part__t1/Il Subject: - Discrete Structure Y Candidates are required to give their answers in their own words as far as practicable. Y Attempt All questions. Y. The figures in the margin indicate Full Marks. Y Assume suitable data if necessary. 1) Using rules of inferences, show that the hypotheses “It is not sunny this afternoon and it is, colder than yesterday,” “We will go swimming only if it is sunny,” “If we do not go swimming, then we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by sunset.” You are required to show each steps and give reasons for those steps before you come to the desired conclusion from the hypotheses. 3) 2) Use mathematical induction to prove that ) 2=2-742- PHA 2 ETI H= EDA whenever n is a nonnegative number. 3) What is a tableau method and why is it important in propositional logic? Draw the tableau for the formula ~((pvq) V ~p) where ~ denotes the negation of a variable and v denotes the disjunction of variables. (24244) 4) Design a finite-state automaton that accepts only those set of strings over (a, 6) which ends with aba. Precisely, only those strings which end with aba should be accepted and other strings over {a, 5} should be rejected. Your design should include the proper definition of the finite-state automaton, transition table and the transition diagram. (3+2+3) 5) Define and differentiate between context-sensitive, context-free and regular grammars with suitable examples. (+243) 6) Find all solutions of the recurrence relation @ Dag + 2n? with initial condition a, 7) Use Dijkstra’s algorithm to find the length of the shortest path between the vertices @ and z in the weighted graph displayed below. 8) b 5 d =4. c $ e 8) Draw the figure for the complete graph with 5 vertices (This is usually denoted by Ks). Define the term graph coloring and the chromatic number of a graph in graph coloring. What is the chromatic number of the complete graph Ks. (2424242) 9) Explain the Euler path and Euler circuit with the help of @ diagram. State the necessary and sufficient conditions for Euler circuits and paths. How is Hamiltonian circuit different from the Euler circuit? (+242) 10) Write short notes on (83) a) Planar and Regular graphs b) Cutsets and Cutvertices c) Application of trees