Graph Theory

U08606 Discrete Mathematics Semester 2 2013/14

Assignment 2

Due by 9.00am, Wednesday 30th April 2014 (week 12)

Please provide the following information Name _______________________________________________ Student Number _______________________________________________ Practical Tutor _______________________________________________ Submission Please complete this cover sheet and attach it to the front of your assignment solutions. You can hand in your work at the start of the lecture, or post your assignment in the coursework box labelled U08606 in the R building, Wheatley campus on or before the due date. Coursework submitted late without a valid justification will not be accepted unless you have made an application for an extension due to mitigating circumstances. Assessment This assignment carries 25% of the total marks for the module. All questions should be attempted and marks will be allocated as indicated. Full details of your working should be handed in for assessment. Important notice You are bound by University regulations which require that coursework submitted for assessment purposes is genuinely your own and is not borrowed or stolen from any source, including fellow students. Ask your practical tutor or attend a surgery if you need advice.

1

U08606 DISCRETE MATHEMATICS - Coursework 2

There are seven questions on this assignment

Due Date: By 5.00pm on Wednesday 30th April 2014 (week 12)

Question 1 (5 marks) The functions and are given by :f R R :g R R

1 ( )

3

x f x

  and ( ) 3 2g x x  .

Determine the functions  and ( )g f x  ( )f g x . Question 2 (5 marks) Of a company’s personnel, 9 work in manufacturing, 6 in marketing and 3 in accounting. A project group of 6 is to be formed to plan the launch of a new product. In how many ways can the project group be formed if (a) the project group includes two members from each department? (b) manufacturing is to have at least two representatives?

Question 3 (5 marks) Consider the following graphs G1 and G2.

1 1

2 2 3 4 5

3 4

5 6 6

G1 G2

For each of the graphs G1 and G2 , state whether or not the graph is (a) Eulerian and (b) Hamiltonian. If the graph is Eulerian give an Eulerian trail and if the graph is Hamiltonian give a Hamiltonian cycle.

2

Question 4 (5 marks) The following table gives the distances (in miles) between six towns A, B, C, D, E and F.

A B C D E F A - 7 26 28 37 16 B 7 - 18 23 28 20 C 26 18 - 8 11 30 D 28 23 8 - 13 42 E 37 28 11 13 - 29 F 16 20 30 42 29 -

(a) Use the minimal spanning tree algorithm to find a network of minimal total length

linking all six towns. What is the total length of the network? (b) Use the nearest neighbour algorithm (starting at town C) to find a circular route

visiting all six towns. What is the total length of the route? Question 5 (5 marks) Given the following table of modules and their prerequisites, use the Topological Sort Algorithm to find a total ordering in which the modules can be taken sequentially. Show your working.

Module Prerequisite modules

Advanced Mathematical Methods B

Basic Mathematical Methods none

Core Electronics B

Digital Imaging E, F

Electronics C

Fourier Analysis A, C

3

Question 6 (10 marks) Let C denote the set of lower case characters of the English alphabet, and let S denote the set of strings of such characters. N is the set of natural numbers. The following basic primitive functions for manipulating elements of S are given: CHAR : S  C where CHAR(s) is the first character of the non-empty string s,

REST : S  S where REST(s) is the string obtained from the non-empty string s by removing its first character,

ADD : C  S  S where ADD(c, s) is the string obtained by adding the character c to the front of the string s,

LEN : S  N where LEN(s) is the number of characters in s,

REV : S  S where REV(s) is the string obtained from the non-empty string s by reversing the characters in s.

(a) A function F : S  S is given by

F(s) = ADD(CHAR(REV(s)), REV(REST(REV(s)))). Evaluate F(s) when s = “apples”. Describe in words the effect of F on any string s containing at least two characters. (b) The function PEN(s) removes the penultimate (last but one) character from an input

string s of length at least two, leaving the rest of the string intact. For example, PEN(“robes”) = “robs”. Express the function PEN(s) in terms of the basic primitive functions above.

(c) Trace the values of u, v, s, LEN(v) and LEN(s) in the following algorithm when s =

“potato”. begin Input s while LEN(v) < LEN(s) do begin u := CHAR(s); s := REST(s); v := ADD(u,v); end Output v

v := REV(v);

end Describe in words the effect of the algorithm on an arbitrary string s. What happens if

the input string is of odd length?

4

Question 7 (10 marks) 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 jx > 1jx  is made for a general positive input n.

Show that T(n) is .  2O n (c) Another sorting algorithm requires comparisons to sort a list of n integers

into ascending order. Is this algorithm more efficient than bubblesort? Briefly justify your answer.

23 log n n