Reference no: EM132502380

MATH4004 Mathematics for Computing - Oxford Brookes University

Problem 1

Let A = {1, 2,3, 4} and B = {1, 2,3}. Define the function f : A → B by the rule

f (1) = 1, f (2) = 3 , f (3) = 1 and f (4) = 2.

(a) What is the image of 3?

(b) What is the codomain of f ?

(c) Draw the digraph representing f .

(d) Is the function injective? Is the function surjective? Justify your answers.

Problem 2

Suppose that ten computer programs have been submitted for batch processing. Only one program may run at a time. In how many ways can the programs be run if:

(a) there are no restrictions on processing order?

(b) four of the programs are considered higher in priority than the other six and should be processed first?

(c) the programs can be separated into three top priority (to be processed first), five medium priority (to be processed immediately after the top priority programs) and two low priority programs (to be processed last)?

Problem 3

(a) Find a Hamiltonian cycle in the graph G whose adjacency matrix is

(b) Find a minimal spanning tree for the graph below.

Problem 4

Consider the graph G with vertex-set V (G) = {a,b, c, d, e, f , g, h} and edge- list E(G) = (ab, ac, ad,bc,be,be,bf , cd,ce,cf ,de, gh).

(a) Draw the graph G .
(b) Show that the following graphs H and J are subgraphs of G .

Problem 5

Use Dijkstra's Algorithm to find the shortest distance from vertex A to all the other vertices in the following weighted digraph:

Determine the shortest path from A to Z.

Problem 6

This Problem is concerned with a functional programming language for manipulating binary rooted trees.

The set BT consists of all binary rooted trees whose vertices are elements of the set N of natural numbers. The empty tree is denoted by Ø.

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

ROOT : BT → N , 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 x N x BT → BT , where MAKE(t, n, s) = the tree with root n, left subtree t and right subtree s
MAX : N x N → N, where MAX(m, n) = the maximum of m and n

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

Draw the trees
(i) MAKE(Ø, 9, RIGHT(s))
(ii) MAKE(RIGHT(LEFT(s)), ROOT(RIGHT(s)), LEFT(LEFT(s)))

(b) A function F : BT → N is defined as below. F(t) = 0 if t = Ø
F(t) = ROOT(t) if t ≠ Ø and LEFT(t) = RIGHT(t) = Ø
F(t) = F(LEFT(t)) + F(RIGHT(t)) otherwise

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

Describe the general effect of F on any tree in BT.

(c) The function ROOTMAX : BT → BT replaces the root of an input tree t with the maximum of the roots of the left and right subtrees of t (provided that L(t) ≠ Ø and R(t) ≠ Ø). Give a description, in terms of the basic primitive functions above, of the function ROOTMAX.

Problem 7

The following algorithm, bubblesort, sorts a list of n integers into increasing order by successively comparing adjacent elements and interchanging them if they are in the wrong order.

Input x1, x2, x3, ..., xn ;
begin
for i := 1 to (n - 1) do
for j := 1 to (n - i) do if xj > xj+1 then
begin
temp:= xj ;
xj := xj+1 ;
xj+1 := temp ;
end
else {do-nothing};
end
Output x1, x2, x3, ..., xn ;

(a) When n = 4, trace the values of i, j, x1, x2, x3 and x4 for the input values x1 = 3, x2 = 2, x3 = 7, x4 =1.

(b) A time complexity function T(n) can be found for bubblesort by counting the number of times the comparison

x_j > x_j+1 is made for a general positive input n. Show that T(n) is O (n² ).

(c) Another sorting algorithm requires 3n log₂ n comparisons to sort a list of n integers into ascending order. Is this algorithm more efficient than bubblesort? Briefly justify your answer.