ITNB2103 Discrete Mathematics

Assignment Question

 

Assignment 2 – 20%                                                                                 

Start: Week 8

Due Dates: Week 13

 

Learning outcomes

1. Use symbolic logic and truth tables in mathematical arguments.
2. Construct mathematical proofs and discrete probability

 

Assignment guidelines:

1. This assignment shall be done individually.
2. Cover page should include these details.

• Course code and Course Name
• Title of assignment
• Your name and Matric No
• Section
• Lecturer’s name

3. Plagiarism in all forms is forbidden. Students who submit plagiarized assignment and/or copy from each other will be penalized.
4. Late submission will be panelized

 

Question

Answer ALL questions                                                                                                  (100 Marks)

1. Suppose V = {S, A, a, b}, T = {a, b), S is the start symbol with productions S ® bS, S ® aA, A ® aS, A ® bA, A ® a, S ® Find a derivation of each of the following.

 

1. bbabbab

(3 Marks)

1. bbbaab

(3 Marks)

[Total:6 Marks]

 

 

 

0, 0

• Give the state table for the finite-state machines with the following state diagrams.

 

    

 

 

Start

 

 

 

0, 0

                                       

                                                                                           

 

 

 

 

 

 

 

 

                                                    

 

 

                                                                       

	0, 0
					0, 1

 

 

 

 

 

 

 

                        (12 Marks)

 

3. For the graph G= (V, E), find V, E , all parallel edges, all loops and all isolated vertices and state whether G is a simple graph. Also state on which vertices edges e₃ is incident and on which edges vertex v₂ is incident.

(8 Marks)

 

 

 

 

 

 

4. Draw graph models, stating the type of graph used, to represent airline routes where every day there are four flights from Boston to Newark, two flights from Newark to Boston, three flights from Newark to Miami, two flights from Miami to Newark, one flight from Newark to Detroit, two flights from Detroit to Newark, three flights from Newark to Washington, two flights from Washington to Newark, and one flight from Washington to Miami, with
5. an edge between vertices representing cities for each flight that operates between them (in either direction), plus a loop for a special sightseeing trip that takes off and lands in Miami

(5 Marks)

1. an edge for each flight from a vertex representing a city where the flight begins to the vertex representing the city where the flight ends

(5 Marks)

 

 

5. Determine whether the given pair of graphs is isomorphic.

 

 

 

 

 

 

 

 

 

 

 

G                                                                               H

(8 Marks)

6. Write an algorithm to finds the largest of the number a, b and c.

(4 Marks)

 

7. Determine whether the following graphs are trees. Explain your answer.

 

1. a)

 

 

 

 

1. b)

(4 Marks)

 

8. Use Prim’s algorithm and Kruskal’s algorithm to find a minimum spanning tree for the weighted graph given below.

(14 Marks)

           

9. Use Huffman coding to encode these symbols with given frequencies:

a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30.

What is the average number of bits required to encode a character?

(12 Marks)

 

 

10. a) Recursively define  a₀ = 1, a₁ = 3, a₂ = 5 and  a_n = 3a_n-2 + 2a_n-3  for  n ³ Calculate  a_n for  n = 3,4,5,6

(4 Marks)

 

1. b) Find f(2), f(3), f(4) and f(5) for the following recursive functions.

f(0) = 1

f(1) = 2

f(k) = (f(k -1))² – f(k -2) + k²

(4 Marks)

 

 

 

 

11. Prove each of the following by mathematical induction.
12. 2.3 + 2.3.4 +.…+ n (n + 1)(n + 2) = n(n+1)(n + 2)(n+3)

4

(7 Marks)

(7 Marks)

 

***END OF QUESTION PAPER***