# UU-MTH- 1005 Discrete Mathematics Assignment Page 1

UU-MTH- 1005 Discrete Mathematics Assignment Page 1

Assignment

The exercises of this exam are worth up to total 100 marks.

Instructions:

Please download the assignment brief, answer clearly in a separate answer sheet of word

document and submit it using the corresponding submission link.

Write the answer for each exercise on a separate page and indicate the number of the

question on the top of the page.

You should read the instructions of each question carefully.

You must indicate all steps of the calculations and not only provide the answers of

the calculations.

There are seven (7) exercises. Please, answer all the exercises.

Where necessary, use the abbreviations, notations, symbols and formulae used in the

course materials or the e-book.

UU-MTH- 1005 Discrete Mathematics Page 2

1. A) List the elements of each of the following sets.

i) { | }

ii) { | }

B) Give the characterizing property of the following sets.

i) { }

ii) { }

C) Give the following using the sets given in A) and B) above

i)

ii) | |

D) i) Use the direct proof technique to prove

ii) Use the proof by contradiction technique to prove

[20 Marks]

2. Given the following two polynomials

and . Carry

out the following operations

a) , , , , and

b) Factorization of and

c) Simplification of

using factorization done in b).

[20 Marks]

3. A) For a function defined by

, find the following, using

images and inverse images, given that { } and

{ }

i)

ii)

B) Show if the expression

defined in A) above has an inverse by

first finding out if it is bijective. Write its inverse if it has.

[10 Marks]

UU-MTH- 1005 Discrete Mathematics Page 3

4. A) Given the set { } and relations defined on set A as follows:

{ }

i) Represent the relation R in a directed graph.

ii) By explaining from the directed graph:

Is the relation R reflexive? Symmetric? Asymmetric? Transitive? Equivalence?

B) Solve the following recurrence relations using an appropriate method for each.

i)

with

ii) with

iii) with and

[20 Marks]

5. A) The Bursaries’ Committee of a certain country offers scholarships to only 4

students from a particular school who come out first, second, third and fourth

in their final year examinations.

i) Find the number of ordered ways the students can qualify for a scholarship if

the school has 10 students sitting for their final examinations.

ii) Solve for the problem i) above if order is not important.

B) i) In a group of 100 people, each person picks a number from 97 to 115. What

is the minimum number of people you need to be sure two of them have the

same number?

iii) At a certain university 525 of the seniors are history majors or math majors

(or both). There are 102 senior math majors, and 35 seniors are majoring in

both history and math. How many seniors are majoring in history?

[10 Marks]

6. A) Give the graphical representation of the following deterministic finite state

automata with its transition function.

{

}

{ }

{ }

{ }

UU-MTH- 1005 Discrete Mathematics Page 4

Transition function:

Present State Next State for Input 0 Next State for Input 1

B) Give the languages, and their natures (descriptions), generated by the following

grammars

i) { },

{ },

,

ii) { },

{ },

,

| |

[10 Marks]

7. Use Warshall’s algorithm to find the shortest paths of the following weighted

graph

[10 Marks]