Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
MCD 4440 –Discrete Mathematics for Computer Science
Oral Presentation (Week 12) Trimester 3, 2024
Topics:
- Number Theory
- Logic
- Mathematical Induction
- Sets, Functions and Relations
- Combinatorics and Probability
- Recursions
- Graph Theory
Weighting:
5%
Due date:
Week 12 tutorial time.
Duration
5-10 minutes
Instructions
You are required to prepare detailed solutions to a question selected from the question pool which will be given to you in advanced. A random question from the question pool will be allocated to you on the day of the presentation. You are expected to write your solutions to your allocated question on the whiteboard and once you have done that, you will then explain the rationale behind your workings to the class. Questions may be asked from the audience of students and teacher in which you are expected to answer them. It is highly advisable that you tried all the questions prior to the presentation. You will be marked base on the marking rubrics as outlined below. In addition, you are required to review and mark your fellow classmates work. Please note that this is an individual assessment and you are expected to complete this assessment by yourself.MCD 4440-Number Theory
Q1. Let d = gcd (518,175).
i. Use Euclidean algorithm to find the value of
d
ii. Use Extended Euclidean algorithm to find the integer solutions for
518x + 175y = d
Q6.
Consider the probability distributions of random variables
X and Y
i. Find an expression for all the integers x that satisfy12x=9 (mod 21 )
| X | 0 | 1 | 2 |
| Pr(X=x) | 1/3 | 1/4 | m |
|
Y
|
1 | 2 | 3 |
| Pr(Y=y) | n | 1/2 | 1/3 |
i. Find the values of m and n
ii. Find the probability distribution of
Z = X + Y
iii. Find E (Z )and Var (Z)
Recursions
Q1. Consider the following recurrence relations
Sn+1=Sn+n,S0=1
Tn+1=3Tn -Tn-1,T0 =1 and T1=2
i. Find the first 4 terms of each relation
ii. Find the order of each relation
iii. Is Sn Homogeneous or Inhomogeneous? Explain why or why not?
iv. Is Tn Homogeneous or Inhomogeneous? Explain why or why not?
Graph Theory
Q1. Consider the following graph.
a. How many odd degree vertices are there in this graph?
b. What is the minimum number of edges should be remove from the graph to have an Eularian trial? Explain why?
c. Starting from A and in alphabetical order, find the spanning tree by using the
i. Breath first algorithm
ii. Depth first algorithm