Read Microsoft Word - MT365 Exam 03 solutionsX.doc text version

MT365 Examination 2003 Part 1 1. (a) The graph of the town is shown right. Since there are four vertices of odd degree, the graph is neither Eulerian nor semi-Eulerian. Hence there is no walk which crosses each bridge exactly once. Adding a bridge CD, for example, allows such a walk: BCACDEDABECE. It is not possible for such a walk to begin and end in the same place since there are still two vertices (B and E) of odd degree. 1 2 3 4 5 1 2 3 4 5 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 0

A

Solutions

B

C

D

(b)

E

1

2.

(a)

(c)

5 4 3

2

(b)

2, 2, 2, 3, 3

(The two vertices of degree 3 are adjacent here but not in the original graph.)

8

S1

11

B

5 2 2

9

T1

9 3 10

3.

S

7

3

T

S2

7

A

6

C1 4

C2 7

T2

A

A

B

C

D

E

F

4.

(a)

(b)

E D

F C

B

A

A F

(c)

C

F D

(d)

E B

D E C

B

John Taylor 2004

www.brighton.ac.uk/cmis/staff/jt40

5.

(a)

Consider the edges in order of increasing weight. Select PT, weight 3. Select QR, weight 4. Select PQ, weight 5. Do not select RT (weight 5) or QT (weight 6) as each would create a cycle. Select QS, weight 7. All vertices have been connected giving the following minimum spanning tree of weight 19. P 3 5 T Q 7 4

S

(b)

R

Edge of smallest weight incident with R is RQ, weight 4. Edge of smallest weight joining Q or R to a new vertex is RT, weight 5. Edge of smallest weight joining Q, R or T to a new vertex is PT, weight 3. Edge of smallest weight joining P, Q, R or T to a new vertex is QS, weight 7. All vertices have been connected giving the following minimum spanning tree of weight 19. 3 P T 5 R 4 Q 7 S

6.

(a)

The first-fit algorithm gives the following 4 worker solution (the bins correspond to workers).

19 G 17 13 B D 5 A 6 C 10 E 9 H 18 F

W1

W2

W3

W4

MT365 Exam 2003 Solutions

Page 2 of 16

(b)

The first-fit decreasing algorithm gives the following 3 worker solution.

20 F 12 10 B E 7 D W3 H 19 20 G 18 A 13 C

W1

W2

7.

(a)

The bipartite graph for the framework is shown right. Since the graph is connected, the framework is rigid. The bipartite graph is not a tree (a cycle is shown), so the bracing is not a minimum bracing.

r1

c1

r2 r3 r4

c2 c3

(b)

c4

c5

8.

(a)

G is not planar. Deleting vertices c and f gives the subgraph shown on the right which is isomorphic to K3,3 .

Hence, by Kuratowski's Theorem (handbook, page 22), G is not planar. Alternatively use the cycle method with Hamiltonian cycle C: abcdefgha. Edges not in C: ad, be, bg, dg, eh. Place ad in set A: A = {ad}. This forces bg, be into B: B = {bg, be}. This forces dg, eh into A: A = {ad, dg, eh}. Now the edges dg and eh of A are incompatible so G is not planar.

a h

b

g e

d

a h

b c

(b)

(G) = 2 (since the graph is bipartite, as shown

on the right).

g f e

d

MT365 Exam 2003 Solutions

Page 3 of 16

9.

(a)

3 A 1 B 2 C 2 D

2 W 3 5 0 0

0 X 1 0 0 6

0 Y 0 2 0 1

0 Z 4 6 7 0

A B

W X Y Z

(b)

C D

10.

(a) (b)

C is not cyclic since, for example, 001100 is a codeword but 000110 is not. C is a (6, 3)-code so a parity check matrix is a 3 × 6 matrix. Parity check equations are: x1 + x6 = 0, x2 + x5 = 0 and x3 + x4 = 0.

1 0 0 0 0 1 Therefore a parity check matrix is H = 0 1 0 0 1 0 . 0 0 1 1 0 0

(c)

Taking H as a generator matrix for the dual code C , the linear combinations of the rows of H give the codewords in C. Therefore, C = C .

11.

(a)

Since POP(PUSH(mathematics, s)) = s, we have TOP(POP(PUSH(mathematics, s))) = TOP(s) = biology. There are two ways this could be written. The simplest is the following: PUSH(chemistry, PUSH(biology, POP(POP(s)))). A better solution that identifies `biology' and `chemistry' from their positions in the original stack s is the following. PUSH(TOP(POP(s)), PUSH(TOP(s), POP(POP(s)))).

(b)

12.

(a)

Chord: AD Chord: AC. Chord: BD

Cycle: ADCBA Cycle: ACBA Cycle: BDCB Cutset: {AB, AD, AC} Cutset: {CD, AD, BD}

Equation: v1 - v6 + v4 - v2 = 0 Equation: Equation: Equation: Equation: v3 + v4 - v2 = 0 v5 - v6 + v4 = 0 i2 + i1 + i3 = 0 i4 - i3 - i1 - i5 = 0 i6 + i1 + i5 = 0

(b)

Branch: AB Branch: CB Branch: CD

Cutset: {CB, AC, AD, BD} Equation:

MT365 Exam 2003 Solutions

Page 4 of 16

13.

(a)

The following table is the table of differences modulo 11.

- 0 2 3

0 - 2 3

2 3 4 9 8 7 - 10 9 1 - 10 1 5 - 4

8 3 5 6 7 -

4 4 2 8 8 6

Each non-zero number modulo 11 appears exactly twice in the table; hence {0, 2, 3, 4, 8} is a prefect difference set modulo 11. (b) (Note that, in the following table, it is not necessary to give the last column.) 1 0 2 3 2 1 3 4 3 2 4 5 4 3 5 6 11 10 1 2 3 7

4 5 6 7 8 9 10 0 (c)

v = 11, r = 5 (each number appears exactly one in each row), k = 5 and = 2 (each number appeared twice in the table of differences in part (a)). Hence:

(v ­ 1) = 2 × 10 = 20 = 5 × 4 = r(k ­ 1).

Part 2 14. (a) Let Kr, r (r 2) have vertex sets {v1, v2, ..., vr} and {w1, w2, ..., wr}. Then v1w1v2w2... vrwrv1 is a Hamiltonian cycle, so Kr, r is Hamiltonian. Diagrammatically:

v1 v2 w1 w2

vr -1 vr

wr -1 wr

MT365 Exam 2003 Solutions

Page 5 of 16

(b)

In any bipartite graph the vertices in a path alternate between the two vertex sets. Therefore any cycle in a bipartite graph contains the same number of vertices from each vertex set. Since the two vertex sets in K6, 8 contain different numbers of vertices, there is no cycle that contains every vertex. Hence K6, 8 is not Hamiltonian. Let G denote the complement of G and, for each vertex v V(G), let deg v and deg v denote the degree of v in G and G respectively.

(c)

Then, for all v G, deg v + deg v = n - 1 . Let G be a simple1 self-complementary graph such that deg v + deg w < n - 1 for each pair of adjacent vertices. Let v and w be any two non-adjacent vertices in G. Then v and w are adjacent in G so deg v + deg w < n - 1 . (Note that G also satisfies the given condition on degrees of adjacent pairs of vertices since it is isomorphic to G.) Hence deg v + deg w = (n - 1) - deg v + (n - 1) - deg v

= 2n - 2 - (deg v + deg v) > 2n - 2 - (n - 1) = n - 1. Therefore, for each pair of non-adjacent vertices of G, deg v + deg w n . Hence, by Ore's Theorem (handbook, page 6), G is Hamiltonian.

15.

(a)

List: 1, 2, 3, 4, 5, 6. Sequence: (1, 2, 3, 4). First element in the list not in the sequence: 5. Join vertices 1 and 5.

5 1 2 3 4 6

Sequence: (2, 3, 4). List: 1, 2, 3, 4, 6. First element in the list not in the sequence: 1. Join vertices 2 and 1.

5 1 2 3 4 6

Sequence: (3, 4).

List: 2, 3, 4, 6.

1

I think the question should have stated that G is simple; the complement is only defined for simple graphs.

MT365 Exam 2003 Solutions

Page 6 of 16

First element in the list not in the sequence: 2. Join vertices 3 and 2.

5 1 2 3 4 6

Sequence: (4). List: 3, 4, 6. First element in the list not in the sequence: 3. Join vertices 4 and 3.

5 1 2 3 4 6

Sequence: ( ). List: 4, 6. Join vertices 4 and 6 to give the final labelled tree.

5 1 2 3 4 6

(b)

The tree is the following.

n +1

1

2

3

n

n+2

(c)

First note that vertices of degree 0 do not appear in the Prüfer sequence. Let the vertex v be labelled k. Then k appears in the Prüfer sequence if and only if, at some stage in the algorithm, v is adjacent to a vertex of degree 1 with smallest label. If deg v = n then v is adjacent to a vertex of degree 1 which is deleted (ie has smallest label) on n ­ 1 occasions after which v has degree 1. There are now two possibilities. Either v becomes a vertex of degree 1 with smallest label, in which case it is deleted without k appearing again in the Prüfer sequence. Or v is eventually one of the remaining two vertices in which case the algorithm terminates without k being appearing again in the Prüfer sequence. Therefore the label k appears n ­ 1 times in the Prüfer sequence.

16.

(a)

The problem is to maximise n (student numbers) subject to cost, c 10. 1st branching

(1, 0, 0, 0) c = 2 n = 30

0

(0, 1, 0, 0) c = 5 n = 90 (0, 0, 1, 0) c = 7 n = 130 (0, 0, 0, 1) c = 3 n = 50

Store: (0, 0, 1, 0), n = 130

MT365 Exam 2003 Solutions

Page 7 of 16

2nd branching

(1, 1, 0, 0) c = 7 n = 120 (1, 0, 0, 0) (1, 0, 1, 0) c = 9 n = 160 (1, 0, 0, 1) c = 5 n = 80

0

(0, 1, 0, 0) (0, 0, 1, 0)

Store: (1, 0, 1, 0), n = 160

3rd branching

(1, 1, 1, 0) c = 14 (1, 1, 0, 0) (1, 0, 0, 0) (1, 0, 1, 0) (1, 1, 0, 1) c = 10 n = 170

×

0

(0, 1, 0, 0) (0, 0, 1, 0)

Store: (1, 1, 0, 1), n = 170

4th branching

(1, 0, 0, 0) (1, 0, 1, 0) (1, 0, 1, 1) c = 12

×

0

(0, 1, 0, 0) (0, 0, 1, 0)

Store: unchanged

5th branching

(0, 1, 1, 0) c = 12 (0, 1, 0, 0)

×

0

(0, 1, 0, 1) c = 8 n = 140 (0, 0, 1, 0)

Store: unchanged

6th branching

0

(0, 0, 1, 0)

(0, 0, 1, 1) c = 10 n = 180

Store: (0, 0, 1, 1), n = 180 The solution is to teach C and D with a cost of 10 APUs, generating 180 student numbers. (b) The problem is now to minimise c subject to a constraint n Nmin. The initial vertex is 1 = (1, 1, 1, 1) (ie all the courses are chosen) and the roles of 0s and 1s in the solution vectors are reversed. Thus vectors ending in 0 are and are not branched from. marked with

MT365 Exam 2003 Solutions

Page 8 of 16

At each branching n and c are calculated as before. A vertex is marked with × if n Nmin. The store is updated when a solution vector is found with c less that the at currently in the store.

17.

(a) (b)

Value of flow = sum of flows in arcs from S = 10 + 5 + 10 = 25.

1st labelling and flow augmenting path:

(S,15) A

10,25 5,15 4,5 6,15

D (B,1)

10,20

7,15

3,5

S

(A,1)

10,20

B

5,5 7,15

E

6,10

9,15

(D,1)

6,20

T (E,1)

C

5,5

F

Increase flow along SABDET by 1.

2nd labelling and flow augmenting path:

(S,14) A

11,25 5,15 5,5 6,15

D (A,9)

10,20

8,15

4,5

S

B

5,5 7,15

E

6,10

10,15

(D,1)

6,20

T (E,1)

10,20

C

5,5

F

Increase flow along SADET by 1.

3rd labelling and flow augmenting path:

(S,13) A

12,25 5,15 5,5 7,15

D (A,8)

10,20

8,15

5,5

S

B

5,5 7,15

E

6,10

11,15

T

10,20

6,20 5,5

C

F

Increase flow along SADT by 8.

MT365 Exam 2003 Solutions

Page 9 of 16

4th labelling and flow augmenting path:

(S,5) A

20,25 5,15 5,5 15,15

D (B,7)

18,20

8,15

5,5

S

(S,10)

10,20

B

5,5 7,15

E

6,10

11,15

T (D,2)

6,20 5,5

C

F

Increase flow along SBDT by 2.

5th labelling and flow augmenting path:

(S,5) A

20,25 7,15 5,5 15,15

D (B,5)

20,20

10,15

5,5

S

(S,8)

10,20

B

5,5 7,15

E

6,10

11,15

(F,4)

6,20

T (E,4)

C

5,5

F

(B,8)

Increase flow along SBFET by 4.

6th labelling and flow augmenting path:

(S,5) A

20,25 11,15 5,5 15,15

D (B,4)

20,20

10,15

5,5

S

(S,4)

10,20

B

5,5

E

11,15 10,10

15,15

T (F,4)

6,20 5,5

C

F

(B,4)

Increase flow along SBFT by 4.

MT365 Exam 2003 Solutions

Page 10 of 16

7th labelling and flow augmenting path:

(S,5) A

20,25 15,15 5,5 15,15

D

20,20

10,15

5,5

S

B

5,5

E

15,15 10,10

15,15

T

10,20

10,20 5,5

(S,10)

C

F

No flow augmenting path. The flow, value 45, is maximum. (c) The two minimum cuts are {AD, AB, SB, CB, CF} and {DT, DE, BF, CF}. These are shown below.

A

25 15 15

D

20

5

15

5

S

20

B

5 15

E

10

15

T

20 5

C

F

The only arc belonging to both minimum cuts is CF. Hence this is the only arc for which increasing its capacity increases the capacity of both minimum cuts and therefore increases the capacity of a minimum cut and hence the value of a maximum flow (by the Max-flow Min-cut Theorem).

18.

(a)

Activity A B C D E F G H

Immediate predecessor B C ­ B, E A, C D E, F, H D

(b)

We calculate the earliest times ei and the immediate predecessors on the critical path pi using the Critical Path Construction algorithm (handbook, page 18). This gives the following.

Page 11 of 16

MT365 Exam 2003 Solutions

[Start] [Vertex [Vertex [Vertex [Vertex [Vertex [Vertex [Vertex [Vertex [Finish]

C] B] A] E] D] F] H] G]

e0 = 0, e1 = 0, e2 = max{0 + 0, 0 + 5} = 5, e3 = max{0 + 0, 5 + 10} = 15, e4 = max{0 + 5, 15 + 15} = 30, e5 = max{5 + 10, 30 + 20} = 50, e6 = 50 + 10 = 60, e7 = 50 + 10 = 60, e8 = max{30 + 20, 60 + 5, 60 + 10} = 70, e9 = max{60 + 5, 60 + 10, 70 + 15} = 85,

p0 = 0 p1 = 0 p2 = 1 p3 = 2 p4 = 3 p5 = 4 p6 = 5 p7 = 5 p8 = 7 p9 = 8

Therefore the minimum completion time is 85 days. (c) Tracing back gives: p9 = 8, p8 = 7, p7 = 5, p5 = 4, p4 = 3, p3 = 2, p2 = 1, p1 = 0. Hence the critical path is: Start ­ C­ B­ A­ E­ D ­ H ­ G ­ Finish. (d) We first find the latest time and float for F. l9 = 85, l8 = 85 ­ 15 = 70 l7 = min{85 ­ 5, 70 ­ 5} = 65, hence float7 = l7 ­ e7 = 65 ­ 60 = 5. Therefore up to 5 days delay in F will not delay the project overall; thereafter, any further delay in F will delay the whole project. Hence a delay of 11 ­ 5 = 6 days in F will delay the project by 6 ­ 5 = 1 day.

A1 A2

P 1 P2 P3 P4 P5

19.

(a)

A3 A4 A5

(b)

I am a little puzzled by this. The algorithm allows us to begin with any matching. Let M be the initial matching A1 ­ P5, A2 ­ P1, A3 ­ P2, A4 ­ P3, A5 ­ P4, shown below, which includes the required pairing.

MT365 Exam 2003 Solutions

Page 12 of 16

A1 A2 A3 A4 A5

P 1 P2 P3 P4 P5

This is a maximum matching so the maximum matching algorithm stops at step 1 since no labelling is possible. The cost of the matching is 2 + 3 + 4 + 1 + 1 = 11. (c) Another maximum matching including the required pairing is: A1 ­ P1, A2 ­ P5, A3 ­ P2, A4 ­ P3, A5 ­ P4.

A1 A2 A3 A4 A5 P 1 P2 P3 P4 P5

Cost = 1 + 2 + 4 + 1 + 1 = 9. (d) Delete the edge A3P2 from the graph in part (a). Then the three people A1, A2, A3 collectively are suitable for only two projects, namely P1, P5; this is illustrated in the diagram below. Therefore, by the Marriage Theorem (handbook, page 25), it is not possible to find a matching that assigns all five people to suitable projects.

A1 A2 A3 A4 A5 P 1 P2 P3 P4 P5

MT365 Exam 2003 Solutions

Page 13 of 16

20.

(a)

(i)

Counting faces: Handshaking lemma for planar graphs: hence Handshaking lemma for graphs: hence

f = s + p + h. 2e = 4s + 5p + 6h; e = 2s + 5 p + 3h . 2 3v = 2e;

v = 4 s + 5 p + 2h . 3 3

(ii)

Substituting these into Euler's formula, v ­ e + f = 2, gives:

( 4 s + 5 p + 2h ) - ( 2s + 5 p + 3h ) + ( s + p + h ) = 2 3 3 2

1s+ 1 3 6

p=2

2s + p = 12.

(iii) There are no regular or semi-regular polyhedra with faces of all three kinds. Suitable examples include: cube (only squares), dodecahedron (only pentagons), pentagonal prism (squares and pentagons), hexagonal prism (squares and hexagons) and truncated icosahedron (pentagons and hexagons).

(b)

(i)

(ii)

(c)

(i)

There are four such animals. Starting with the square and pentagon in contact, there are four distinct ways that a hexagon may be added as shown in the diagram below.

2 1 2 3 4 3 4

(ii)

There are five such animals. Starting with the square and hexagon in contact, there are five distinct ways that a pentagon may be added as shown in the diagram below.

2 1 2 3 4 3 4 5

MT365 Exam 2003 Solutions

Page 14 of 16

(iii) All those animals with the pentagon and hexagon having an edge in common are included above in (i) and (ii). However those animals numbered 1 in (i) and (ii) are the same, as are those numbered 2. Hence there are 7 such animals.

21.

(a) (b)

There are 3 binary joints (A, D, F) and 3 quaternary joints (B, C, E); there are 9 binary links. Expanding E:

(c)

The number of links remains unchanged; hence there are 9 links. Each quaternary joint is replaced by 3 binary joints; hence the new system has 12 binary joints. From the first mobility criterion M = 3(n ­ 1) ­ 2j (handbook, page 21), we have M = 3 × 8 ­ 2 × 12 = 0 (as expected). Each quaternary joint may be expanded into binary joints in 16 ways, as illustrated below.

(d)

4 choices

12 choices

Hence there are 163 (= 4096) ways that the three quaternary joints may be expanded to produce a new system.

MT365 Exam 2003 Solutions

Page 15 of 16

22.

(a)

(i) (ii)

The parity check matrix is 4 × 6 so n = 6 and k = 2; therefore there are 2k = 4 codewords.

Rate =

k 1 = . n 3 (iii) The parity check equations are: x1 + x2 + x3 = 0 x1 + x3 + x5 = 0 x1 + x6 = 0 x1 + x2 + x3 + x4 + x5 + x6 = 0 From (3) Case A: x1 = x6 = 0 or x1 = x6 = 1. x1 = x6 = 0 Then, from (1), x2 = x3 = 0 or x2 = x3 = 1. In the first case, x5 = 0 (from (2)) and x4 = 0 (from (4)), giving codeword 000000. In the second case, x5 = 1 (from (2)) and x4 = 1 (from (4)), giving codeword 011110. x1 = x6 = 1 (1) (2) (3) (4)

Case B:

Then, from (1), x2 = 1, x3 = 0 or x2 = 0, x3 = 1. In the first case, x5 = 1 (from (2)) and x4 = 0 (from (4)), giving codeword 110011. In the second case, x5 = 0 (from (2)) and x4 = 1 (from (4)), giving codeword 101101. Hence the four codewords are: 000000, 011110, 110011, 101101. (b) (i) Extending the code by adding a parity check bit as the first bit gives: 0000000, 1001110, 1110100, 0111010, 1100011, 0101101, 0010111, 1011001

Hamming distance, = minimum weight of a non-zero codeword = 4, so the code can detect 2 errors and correct 1 error. (iii) A generator matrix for B has rows any three linearly independent codewords so a generator matrix is (ii)

1 0 0 1 1 1 0 G = 1 1 1 0 1 0 0 . 1 1 0 0 0 1 1

This is a parity check matrix for the dual of B . Since all the non-zero 3-bit words appear as columns of G, the dual of B is a Hamming code.

MT365 Exam 2003 Solutions

Page 16 of 16

Information

Microsoft Word - MT365 Exam 03 solutionsX.doc

16 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

562886


You might also be interested in

BETA
dijkstra-proof
mk:@MSITStore:K:\Data.Structures.and.Algorithm.Analysis.in.C.ch
Microsoft Word - 007.doc
Microsoft Word - further math guide.doc