Subject Code & Title :- MAT2DMX Discrete Mathematics For Computer Science
Assessment Type :- Assignment 3
Task weighting: 15%
Objectives :-
• Proving and disproving the existence of a graphs
• Applying Kruskal’s algorithm to find a minimum spanning tree
• Applying tree traversal algorithms and demonstrating understanding on binary search tree
• Designing algorithms in pseudocode and analysing algorithm complexity
• Demonstrating understanding model of computation using Finite State Machine
MAT2DMX Discrete Mathematics For Computer Science Assignment 3 – Australia

Question 1
In each case below either draw a tree or graph with the required properties or prove that it does not exist. In degree sequence order does NOT matter.
(a) A tree on 8 vertices with degrees 1, 1, 1, 1, 1, 2, 3, 4.
(b) A tree on 6 vertices with degrees 1, 2, 3, 2, 2, 2.
(c) A connected graph on 5 vertices with degrees 2, 3, 3, 5, 5.
(d) A connected graph on 6 vertices with degrees 2, 2, 3, 4, 4, 4.

A graph can have multiple edges or loops.

(Explanation marks are for correct draw or correct explanation. If you can draw you do not need to explain. See Section 7.6 in Week 7 hand out for examples and theory.)

Question 2 :-
State which of the following graphs are planar. For those which are planar, give a planar graph drawing. For those which are not planar explain why they are not. (For reference see Section 7.5 and Week 7 practical exercises.)

Question 3
(a) Apply Kruskal’s algorithm to find a minimum spanning tree and its weight for the graph on 6 vertices

Set out your answers in the Table 2 below (see workshop video Hand out Example 5 or Week 8 practical questions 1 and 2). You may not need all given rows.

(b) Draw your spanning tree on the following set of vertices.

Question 4
Build the expression tree for the following expression (Explanation is not required).
((a − b) ∗ c) − (a ÷ ((c − d) ÷ b)).

Question 5
Consider the following binary expression tree.

(a) Write down the expression obtained from preorder traversal.
(b) Write down the expression obtained from postorder traversal.

For each case use comma to separate data from each node Explanation is not required.

Question 6
Insert the following list of integers (following order of insertion from left to right of the list) into a binary search tree. Note that your binary search tree is unique.

(Explanation is not required.)

Question 7
Consider the following algorithm:
Input: Two matrices A and B both of size n × n

Determine the time function of this algorithm. To explain, state number of time units or iterations in each line.

You only need to solve one of the two options of Question 8. Please choose one.

Question 8 Option 1
Let M be the adjacency matrix (size n × n) of a graph G = (V, E) of n vertices ( V = { 0,1,2,…,n − 1} ) in which:

Let S ⊂ V = { 0, 1, 2, … , n − 1} be a set of some vertices of G.

(a) Design an algorithm to verify if every pair of vertices in S are adjacent.
Input: An adjacency matrix M and a subset S of vertices of the graph
Output: Boolean value True if every pair of vertices in S are adjacent and False other wise

Represent your algorithm in a pseudo code. Do not use any programming language for the solution. The purpose of this question is for you to learn writing pseudo code.

(b) What is the time function and big O complexity of your algorithm? In this question mark is given only when time function is correct.

Note:
1. In a programming language, the matrix M can be represented as 2- dimentional array. In some languages Mi,j can be called as M[i][j]. You are free to use any option that you are confident with.
2.You can assume that the set S is already a subset of V. You do not have to verify this condition

Question 8 Option 2
a) Write an algorithm to solve the problem as discussed below.
b) What is time function of this algorithm? What is the big O complexity of your algorithm? In this question mark is given only when time function is correct.

In week 1 we learn how to verify if a set is a relation from a set A to a set B. We also tried a question in Assessment 1 on this where we manually check elements one by one.

In this question you are asked to write an algorithm that reads in three sets A, B, and X and out put a Boolean value True if X is a relation from set A to set B and False other wise.

MAT2DMX Discrete Mathematics For Computer Science Assignment 3 – Australia

Assumption:

1.Sets A and B are sets of objects and they have operator in. The call x in A will out put True if x is an element in A and False other wise. The same is true for set B.

2.The set X is iterable in the sense that you can iterate elements in X using the format For each element e in X.

3.Each element of X is a list of two objects. This means you can access the first and second elements of any element e of X by calling e[0] and e[1]. Our indices and list notation here are like our discussion in lectures and handout of week 9 materials.

Example:
A = {“Banana”,“Potato”,“Pumpkin”} and B = {“Fruit”,“Vegetable”}
X = {[“ Banana”,“Banana”],[“Banana”,“Fruit”]}

Your algorithm should output False because e[1] is not in B where e is the first element of X.

Your algorithm should work in the way that it can deal with any sets A, B, and X rather than only the above example input. Please think that X may have one million elements.

Question 9
(a) Determine the dominant term and using dominant term to find big O class of the following time function:

Note: You do not need lazy method for question (a).

(b) Using lazy method to prove the following:

(Set up your answer similarly to examples 10 – 11 in the lecture note (handout)).

Question 10

Consider the following finite state machine:

(a) Find f(A, 0110), f(A, 0111), f(A, 1011), f(A, 01101)
(b) Decide which of the following words are accepted by this machine:

Explain your answer. Answer without explanation will not get mark.

(c) Fill the transition function into the following table. One cell has been filled as an example.

(d) What is the language of this finite state machine?
(e) Represent the language of this machine (that you obtain from question (d)) in a regular expression. Mark is given only if your answer to (d) is correct.

MAT2DMX Discrete Mathematics For Computer Science Assignment 3 – Australia

Question 11
Consider the following language:

Represent the language L using a regular expression. Explanation is not required.