UU-MTH- 1005 Discrete Mathematics Assignment Page 1

UU-MTH- 1005 Discrete Mathematics Assignment Page 1
The exercises of this exam are worth up to total 100 marks.
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
ii) | |
D) i) Use the direct proof technique to prove
ii) Use the proof by contradiction technique to prove

Get Your Custom Essay Written From Scratch
Are You Overwhelmed With Writing Assignments?
Give yourself a break and turn to our top writers. They’ll follow all the requirements to compose a premium-quality piece for you.
Order Now

[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
{ }


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.
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
i) { },
{ },

ii) { },
{ },
| |
[10 Marks]
7. Use Warshall’s algorithm to find the shortest paths of the following weighted
[10 Marks]