# Explain how you would amend the algorithm to find a spanning tree of maximum total weight. Hence, find a spanning tree of maximum total weight for the graph G above.

## SCROLL DOWN TO DOWNLOAD A++ SOLUTION TO ALL QUESTIONS

## Discrete Mathematics

Click the pdf link for full questions

file:///C:/Users/USER/Downloads/ASS217.pdf

Question 1 (5 marks)

Relations R and S on the set {a b c d , , , } are represented respectively by the

matrices

F T T F

F T T F

F F F T

T F F F

a b c d

a

b

c

d

T F F F

T T F F

F T F T

F F T T

a b c d

a

b

c

d

(a) List the ordered pairs belonging to R .

(b) Determine the matrix representing the composition S R .

Question 2 (5 marks)

Let f and g be functions from ℕ to ℕ, where ℕ is the set of natural numbers,

with

( ) 1

( ) 2

f n n

g n n

= +

=

Determine f f , f g and g f .

8606 ASSIGNMENT 2 PAGE 2

Question 3 (5 marks)

(a) A palindrome is a string of digits which reads the same backwards as forwards.

How many different palindromes are there with 9 digits?

(b) How many distinct rearrangements are there of the letters in the word

MATHEMATICS

(i) begin with the letter H

(ii) have both the M together?

Question 4 (5 marks)

(a) Use the minimal spanning tree algorithm to find a minimum connector for the

graph G below.

A

4 7

5 6

B 5 C

4 3 2 8

D

5 7

E F

6

(b) Explain how you would amend the algorithm to find a spanning tree of maximum

total weight. Hence, find a spanning tree of maximum total weight for the graph G

above.

8606 ASSIGNMENT 2 PAGE 3

Question 5 (5 marks)

(a) Use Dijkstra’s Algorithm to find the shortest distance from vertex A to all the

other vertices in the following weighted digraph:

D

4 4 21

B F

6

13

A 5 3 H

5

11

C G

22 5 4

E

(b) Determine two different shortest paths from A to H .

8606 ASSIGNMENT 2 PAGE 4

Question 6 (10 marks)

The set BT consists of all binary rooted trees whose vertices are elements of the

set ℕ of natural numbers. The empty tree is denoted by ∅ .

The following basic primitive functions for manipulating elements of BT are given:

ROOT BT : → ℕ, where ROOT t( ) = the root of the non-empty tree t

LEFT BT BT : → , where LEFT t( ) = the left subtree of the non-empty tree t

RIGHT BT BT : → , where RIGHT t( ) = the right subtree of the non-empty tree t

MAKE BT BT BT : × × → ℕ , where MAKE t n s ( , , ) = the tree with root n , left

subtree t and right subtree s

(a) Let s be the following element of BT :

Draw the trees

(i) MAKE LEFT s (∅,10, ( ))

(ii) MAKE RIGHT LEFT s ROOT LEFT s LEFT LEFT s ( ( ( ) , ( ) , ( ) ) ( ) ( ))

(b) A function G BT : → ℕ is defined as below.

G t( ) 0 = if LEFT t RIGHT t ( ) ( ) = = ∅

G t G RIGHT t ( ) = +1 ( ( )) if LEFT t( ) = ∅ and RIGHT t( ) ≠ ∅

G t G LEFT t ( ) = +1 ( ( )) if LEFT t( ) ≠ ∅ and RIGHT t( ) = ∅

G t G LEFT t G RIGHT t ( ) = + + 2 ( ( )) ( ( )) otherwise

(i) Evaluate G s( ) where s is the tree in part (a).

(ii) Describe the general effect of G on any tree in BT .

(c) The function SWAP BT BT : → interchanges the root of an input tree t and

the root of its left subtree (provided LEFT t( ) ≠ ∅ ). Give a description, in

terms of the basic primitive functions above, of the function SWAP .

9

5

2

4 3 7

8 1

8606 ASSIGNMENT 2 PAGE 5

Question 7 (10 marks)

The following algorithm, Algorithm1, counts the number of pairs of integers in a list.

Algorithm Algorithm1

begin

Input x1, x2, …, xn

count := 0

for i := 2 to n do

begin

for j := 1 to (i – 1) do

begin

if xi = xj then

begin

count := count + 1

end

end

end

Output count

end

(a) Verify that the algorithm works on the list 2, 3, 6, 2, 6.

(b) Find a time complexity function for the algorithm by calculating how many times

the comparison i j x x = is performed for an input sequence of length n .

(c) A second algorithm, Algorithm2, also counts the number of pairs of integers in

a list. If Algorithm2 is uses 2

n n log operations, which of the two algorithms is

more efficient? Briefly justify your answe

cHECK FILE FOR QUESTIONS

A

NSWER

No. Of Words: 325

Pages 1.3

Type: Essay

Price: $20.00

## A++ SOLUTION TO ALL QUESTIONS

Course

Name

Institution Affiliation

1. a)

Orders pairs in R

b) SoR

**№**

**a**

**b**

**c**

**d**

**a**F T T F

**b**F T T F

**c**F F F T

**d**T 0 0 F

**№**

**a**

**b**

**c**

**d**

**a**T F F F

**b**T T F F

**c**F T F T

**d**F