## [answered] A ssignment 4 Mat 3 4 4 Due: Reading Chapter 3, 3.3 &am

please answer these math(applied combinatorics) problems, ?please use computer to answer the questions , i do not accept hand writings. thank you very much.

A ssignment 4 Mat 3 4 4 Due: 11/17/2016 This assignment is due in Lecture on the 17th, not in Tutorial on the 16th

You may hand it in (early) on the 16th if you wish. Reading

? Chapter 3, 3.3 &amp; Chapter 5, 5.1-5.4 Exercises

De f i n i t i o n 1 An n ? n matrix M (with non-negative integer entries and with n &gt; 2) is the cost matrix

for a (weighted, complete) directed graph G if the (i, j)-th entry in M is the weight of the edge (xi , xj )?

(except that the (i, i)-th entries are all &quot;?&quot;). Therefore, for example, the entry in the upper-right corner will

be the weight of the edge going from x1 to xn .

The cost of a path or circuit in G is the sum of the weights of the edges included in that path or circuit.

E x e rc i s e 1 Consider the (large) TSP Problem given by the following cost matrix (do not draw the graph!):

?

2 5 11 1

A=

10 11 1 42

1 1

?

4

8

0

8

7

1

21

2 5

6

?

1

1

6

5

1

7

3 2

7

1

?

0

4

3

1

3

4 4

7

4

1

?

2

2

1

66

5 3

7

2

2

2

?

1

1

33

6 9

7

9

31

3

12

?

1

11

7 6

7

11

17

4

14

36

?

3

8 8

7

3

4

3

16

63

70

?

9 7

7 11 20 5 18 63 99 100

? (a) What is the cost of the Hamilton Circuit produced by the &quot;greedy algorithm&quot; discussed in class (which

always takes the locally best edge) if we start the algorithm at x1 ? (Recall that this algorithm is slightly

simpler than the &quot;approximate&quot; algorithm given in section 3.3.)

(b) Find (by hand - do not show your work), a Hamilton Circuit whose cost is less than one fifth of the one

which the &quot;greedy algorithm&quot; produced.

E x e rc i s e 2 Consider the (small) TSP problem given by the following cost matrix:

?

1 B=

2

3 1

?

4

9 2

4

?

27 3

9 27

? Use the Branch and Bound method discussed in lecture and the textbook to find a lowest-cost Hamilton

Circuit through this graph. Show all your work, making sure to follow the algorithm precisely (include

your updated cost matrices, as well as a tree which represents your overall argument).

E x e rc i s e 3 Suppose that C = v1 ? v2 ? ... ? vn ? v1 is a Hamilton Circuit of lowest cost in a graph G. And

let P = C ? (vn , v1 )? be the Hamilton Path from v1 to vn created by simply removing the last edge from C.

Is P necessarily the least-cost Hamilton Path in G starting at v1 and ending at vn ? (Justify your answer.) Mat 3 4 4 A ssignment 4 Due: 11/17/2016 E x e rc i s e 4 For this problem, assume we are in the symmetric TSP context: i.e. for each pair of vertices, a

and b, the cost of traveling from a to b is equal to the cost of traveling in the opposite direction. Calling

this single edge e, we let &quot;c(e)&quot; be this (single) cost of travel on that edge. And for the purposes of counting

the number of edges e (see below), we will only count the edges (a, b)? and (b, a)? as a single edge.

Consider the following TSP-solving algorithm (which assumes that the inputted cost matrix is symmetric):

? Let v be the number of vertices in the graph. And let c be this number multiplied by the average cost,

written a, of all the edges in the graph, i.e.

!

1X

c = v?a = v?

c(e)

e

e?E ? Perform a &quot;greedy algorithm&quot; search, starting at x1 , except that:

? Each time we add an edge to our path, we add its cost to a running total t;

? And if at any step in the process we add an edge to our path, and this results in t &gt; c, we

backtrack in our process to the first time where there is an edge that hasn?t been tried and whose

use results in t 6 c. Then we take the least-cost such option (if there is a tie here, we take the

option which takes us to the vertex xi with i smallest).

(a) Which Hamilton Circuit does this algorithm produce for the graph with cost matrix B above? Show

your work. (Note that in calculating c, you don?t count, for instance, both of the (equal) weights on edges

(x1 , x2 )? and (x2 , x1 )? ; only one.)

(b) Give an argument for why this algorithm is guaranteed to finish with an answer (in finite time) when

applied to any cost matrix. (That is, we never reach a point while applying our algorithm where we have no

options for continuing to construct our circuit.)

Hint: Is it possible for all of the Hamilton Circuits in a graph to have total cost strictly greater than c?

E x e rc i s e 5 Sam and Janet are picking dogs and/or cats from among 14 different dogs and 11 different

cats. How many different outcomes are there if Sam picks a dog and a cat and then Janet picks either a dog

or a cat, and then Janet decides that she wants to swap the animal they have in common (if Janet picked a

dog then they exchange the dogs they picked; if Janet picked a cat, they exchange the cats they picked)?

(For example, suppose Sam picks the dog named &quot;Apples&quot; and the cat named &quot;Biggles&quot;, while Janet picks the dog

named &quot;Chewy&quot;; then the final outcome is that Sam gets &quot;Chewy&quot; and &quot;Biggles&quot;, while Janet gets &quot;Apples&quot;.)

E x e rc i s e 6 How many arrangements are there of the letters in the word &quot;MISSISSAUGA&quot; so that:

(a) The arrangements start with an &quot;S&quot; immediately followed by an &quot;M&quot;, &quot;U&quot; or &quot;G&quot;? (For example,

&quot;SGIISSSAAUM&quot;.)

(b) The arrangements end with &quot;M&quot;, the first &quot;S&quot; occurs before the first &quot;A&quot;, and the two &quot;A&quot;s occur together

as a pair?

(c) The arrangements start and end with an &quot;S&quot;, they have at least one consonant between each vowel, and

the vowels occur in alphabetical order?

(d) The arrangements have the &quot;G&quot; immediately beside an &quot;S&quot; (either as &quot;GS&quot; or as &quot;SG&quot; or as &quot;SGS&quot;, etc.)?

Solution details:
STATUS
QUALITY
Approved

This question was answered on: Sep 18, 2020

Solution~0001003662.zip (25.37 KB)

This attachment is locked

We have a ready expert answer for this paper which you can use for in-depth understanding, research editing or paraphrasing. You can buy it or order for a fresh, original and plagiarism-free copy from our tutoring website www.aceyourhomework.com (Deadline assured. Flexible pricing. TurnItIn Report provided)

STATUS

QUALITY

Approved

Sep 18, 2020

EXPERT

Tutor