Question Details

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


please answer these math problems, ?thank you very much. ? ?Please do them in hand ?writing, or computer format, ?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 & 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 > 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 "?"). 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 "greedy algorithm" 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 "approximate" 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 "greedy algorithm" 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 "c(e)" 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 "greedy algorithm" 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 > 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 "Apples" and the cat named "Biggles", while Janet picks the dog

 

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

 

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

 

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

 

"SGIISSSAAUM".)

 

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

 

as a pair?

 

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

 

the vowels occur in alphabetical order?

 

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

 


Solution details:
STATUS
Answered
QUALITY
Approved
ANSWER RATING

This question was answered on: Sep 18, 2020

PRICE: $15

Solution~0001003661.zip (25.37 KB)

Buy this answer for only: $15

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)

Pay using PayPal (No PayPal account Required) or your credit card . All your purchases are securely protected by .
SiteLock

About this Question

STATUS

Answered

QUALITY

Approved

DATE ANSWERED

Sep 18, 2020

EXPERT

Tutor

ANSWER RATING

GET INSTANT HELP/h4>

We have top-notch tutors who can do your essay/homework for you at a reasonable cost and then you can simply use that essay as a template to build your own arguments.

You can also use these solutions:

  • As a reference for in-depth understanding of the subject.
  • As a source of ideas / reasoning for your own research (if properly referenced)
  • For editing and paraphrasing (check your institution's definition of plagiarism and recommended paraphrase).
This we believe is a better way of understanding a problem and makes use of the efficiency of time of the student.

NEW ASSIGNMENT HELP?

Order New Solution. Quick Turnaround

Click on the button below in order to Order for a New, Original and High-Quality Essay Solutions. New orders are original solutions and precise to your writing instruction requirements. Place a New Order using the button below.

WE GUARANTEE, THAT YOUR PAPER WILL BE WRITTEN FROM SCRATCH AND WITHIN YOUR SET DEADLINE.

Order Now