Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

Maths 162: Computational Mathematics

Assignment 3 Due date:  7pm, Monday October 14th

This assignment is to be submitted online through canvas as a single PDF file, containing answers for all questions, your workings, any figures, and code in a sensible order.

Do not use your phone to take a photo of your computer screen. Photographs of computer screens will not be marked. When handing in code, either copy paste your code into your docu- ment (perhaps with a special  coding  font), or take a printscreen of your matlab window.

Note that questions are not ordered by difficulty.  If question 1 seems hard, don’t assume that the other questions will be harder, they will just be different.  We will cover the material needed for Questions 1 and 2 by Tuesday 1st of October. By Tuesday 8th of October, you will have all the tools needed to complete the entire assignment.

For each question, work through as far as you can - even if you cannot get a complete/perfect answer, write what you can.  As the main idea is to demonstrate your understanding of the ideas, methods and programming, do include all your working and your MATLAB code along with the answers that you get from your MATLAB code.

Full marks: 30 marks.

Getting help:

• No cheating. You are allowed to discuss with othershow togo about a question, but you must produce your own computations and write your answers by yourself.  Copying answers, either from other students, the internet or ’online tutors’ is considered plagiarism.
  
• Course  material: The course book, your notes from lectures,  and the tutorials all provide helpful information for answering the assignment questions.  There is also the Coder’s guide to programming and the Spider’s guide to Cobwebs.
• Help files in MATLAB: One way to find information about a particular MATLAB function is to type help in the MATLAB Command Window followed by the name of the function.  For example, to get help with using sqrt  , the square root function, type help sqrt  .   This gives basic information. For more information, you can click on the link to the Help browser (i.e., the question mark at the top of the MATLAB window.)
• Office Hours: Alastair’s office hours are currently  1:30-3:30 on Thursday.  Additional office hours will be available during assignment weeks (These will be announced on Canvas)

1    Rejection sampling and Monte Carlo Integration (7 marks)

Suppose we want to estimate the integral

. The following code attempts to estimate the integral using rejection-sampling:

N=5000;

X=  3*rand([N,1]);

Y=  2*rand([N,1]);

Q=  Y

integral =9000* mean(Q);

Unfortunately the code is horrible and wrong.

a)  The number 9000 in the above code is clearly wrong.  What should the number be?  Fix the number, and hand in the new output you get from running this function.

b) It’s a bit hard to tell what the above code is doing.   Add  some code in order to produce a colour-coded scatterplot of X,Y , with ’accepted’ points coloured in yellow, and ’rejected’ points coloured in blue. Hand in your plot.

c)  Use Matlabs hold  on and plot functions to add the line y  = esin(x)  your your scatter plot. What do you notice? How might this be a problem?

d)  How would you edit the code above in order to fix this problem and find the correct value of the integral. What is this corrected value?

2    Graph Theory Quickfire (8 marks)

This question is designed to test your understanding of the core ideas of graph theory:  namely degree- sum formula, Hamiltonian cycle, Eulerian cycle, and connectedness.

a)  A simple graph G has ten nodes.  What is the largest number of edges G can have while ensuring the graph is NOT a connected graph? Explain your reasoning.

b)  A simple graph G has ten nodes.  What is the largest number of edges G can have while ensuring the graph is bipartite? Explain your reasoning.

c)  Consider the following graph:

Starting at node b,  apply Prim’s algorithm  (also called ”the  Greedy algorithm” in class) to determine the minimum spanning tree.  Hand in your list of edges to include in the order that they are added to the spanning tree.

d)  Does the graph depicted above in part (c) have an Eulerian circuit?  (IE, a circuit which uses every edge exactly once). Does it have a Eulerian path? Explain your reasoning.  (Note, for this question we care only about the existence of edges, the costs attached to each edge are irrelevant).

3 Graphs and Coding (7 marks)

One of the main skills of 162 is being able to read and write code.  For this question you will download the function MysteryFunction .m from the assignment page, and will explain and interpret it.

function   [G]=   MysteryGraph(N)

%%   Given   a  number  N ,   create   graph .

d=2;

A=zeros(N, N)

for (k=1:N)

for (i=1:N);

if (mod(i+k, d)==1)

A(i, k)=1

end   %end   of   if .

end     %end   i   for   loop

A(k, k)=0;

end     %end  k   for   loop

G=graph(A);

plot(G)

end   %End   function .

a)  Run MysteryGraph for a variety of N values.  (In may be useful to try a couple small values, and a couple larger ones). Hand in two of your plots.  Use graph terminology from class to describe the resulting graphs (Are they complete?  Are they connected?  Are they Bipartite?  Do you have a tournament? etc etc.)

b)  Give two or three sentences explaining in words what this function is doing overall.  What is happening with each section of this code?

c)  Does MysteryFunction(5) give a graph with an Eulerian Circuit? Do we have an Eulerian path?

d)  In general, for what values of N does G have an Eulerian circuit?  Give one or two sentences justifying your answer.

e) What is the chromatic number of G for N  = 5, 6, 7 or 8?  In general, what is the chromatic number χ(G) (this number might depend on N, or might not).

f) Challenge questions (Zero marks): Suppose we instead set d=3.   In this case, how would you describe the resulting graphs?  If d = 3, for what values of N do we have an Eulerian circuit? For d = 3, what is the chromatic number χ(G)?  How does it relate to N?

4 Networks and Modelling (8 marks)

One of the most useful and powerful skills in mathematics is the ability to turn real world situations into a mathematical model... and then solve these problems using existing tools.

The ‘Northern Explorer’ train from Auckland to Wellington has six carriages.  We would like to arrange these carriages in the best possible way, and have the following information

• We have six carriages: one Engine, one for Luggage, two for Passenger seating, one Restaurant and one Viewing deck.

• The Engine carriage is legally barred from being connected to any passenger area (P,R or V).

•  Passenger carriages strongly prefer to be connected to the restaurant and viewing deck.

•  The Viewing deck doesn’t mind having carriages behind it, but slightly dislikes having carriages in front of it.

• All other connections are neutral (neither good nor bad).

a) What graph would you use to represent the information above? What do the nodes of your graph represent? What about the edges?  For each bulletpoint above, give one sentence explaining how you have represented that in the graph.

b) What type of graph theory problem from class must we solve in order to find the best possible ordering of the train?  Give one or two sentences explaining any changes you must make to the problem compared to the “standard” formulation of the problem learned in class.

c)  By hand, determine the best possible ordering of train carriages (for this small example, solving by hand is possible). What is the total ’value’ of this carriage arrangement.

d) If your train had 15 carriages, which algorithm would you use?  If your train had 30 carriages, which algorithm would you use? In each case, give a single sentence to justify your answer.