Search the whole station

# 离散数学作业代写 MACM 201代写 D100 AND D200代写

602

## MACM 201 – D100 AND D200 ASSIGNMENT #8

### Instructions 离散数学作业代写

Answer all questions on paper or a tablet using your own handwriting. Put your name, student ID number and page number at the top of each page. Include a cover page with your name and student ID on it and also the questions that you answered. If you use paper make a photo of each page and upload your solutions to crowdmark. If you use a tablet, export your assignment to .pdf and upload the .pdf to crowdmark.

• Sections: 12.1, 12.2, 12.5, 13.2 (Kruskal’s algorithm only)

### Exercises

#### A. Textbook Questions

12.1 Exercise 12, 13.

12.2 Exercise 1, 6, 10.

For exercise 10, Grimaldi defines a complete binary tree on the bottom of page 589 to be a binary tree where all nodes have 0 children or 2 children. Figure 12.22 on page 596 has examples.

12.5 Exercise 1, 6, 8.

13.2 Exercise 2, 4.

For exercise 4, use googlemaps to find the cities in Table 13.1. Sketch a map of the cities and the highways you choose.

#### B. Instructor Questions 离散数学作业代写

##### 1.

For the rooted tree below, give the preorder and postorder traversals.

##### 2.

For this question note that reverse Polish notation is the postorder traversal.

(a) Consider the expression f = (x2 + y/3)/(1 + 5xy). Construct a rooted tree for f then express f in reverse Polish notation.

(b) Evaluate the expression 9 3 × 5 6 2 × 7 − × + given in reverse Polish notation.

##### 3.

Let G = (V, E) be a simple graph with V = {1, 2, 3, 4, 5}.

(a) Given the list of neigbours array N where N1 = {2, 5}, N2 = {1, 4, 5}, N3 = {4}, N4 = {2, 3}, and N5 = {1, 2}, draw G.

(b) Given the edges E = {{1, 3}, {2, 3}, {3, 4}, {3, 5}, {4, 5} give the list of neighbours array for E.

(c) What is advantage of the list of neighbours representation N over the set of pairs of vertexes representation for E?

##### 4.

Draw the depth-first-search spanning tree for the graph in the figure below, using the vertex order t < u < v < w < x < y < z and the vertex order z < y < x < w < v < u < t. In each case use t as the root of the spanning tree.

##### 5.

In class we showed that “if a graph has an articulation point, it cannot have a Hamiltonian cycle”. Show that the converse of that statement “if a graph has no articulation points then it has a Hamiltonian cycle?” is false by finding a counter example.

##### 6.

In the text, the proof of Lemma 12.3 reads “The result follows directly from Definition 12.9” You are to fill in the details. Note, because it is an if and only if proof there are two parts to the proof so for each part write down what you have to prove first.

##### 7.

Find Pr üfer codes for the following trees.

(a) T = (V, E) where V = {1, 2, 3, 4, 5, 6, 7} and E = {{1, 2}, {1, 3}, {1, 4}, {3, 5}, {5, 6}, {5, 7}}.

(b) T = (V, E) where V = {1, 2, 3, 4, 5, 6, 7} and E = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {4, 6}, {4, 7}}.

##### 8. 离散数学作业代写

(a) Construct the tree for the Prüfer code (3, 3, 3, 3).

(b) Given an integer 1 ≤ i ≤ n describe the tree for the Pr ¨ufer code (i,i, . . . ,i).

Reverse Polish notation became popular in the 1970s amongst scientists and engineers because the first scien- tific calculators, which were made by Hewlett Packard, used reverse Polish notation. The HP 35 shown below, released in 1972, was the world’s first scientific pocket calculator. Notice the large blue ENTER button. To calculate (22 + 33) × 55 one would press the buttons 2 2 ENTER 3 3 ENTER + 5 5 ENTER ×. Internally the calculator uses a stack to store the intermediate values. Many programming languages use reverse Polish notation and a stack to evaluate numerical expressions. If you are interested the Wikipedia page on “Reverse Polish Notation” is an informative read.

The prev: The next:

### Related recommendations

• #### 数学概率作业代写 数学概率代写 数学作业代写 概率作业代写

63

4. Probability on finite sample spaces. 数学概率作业代写 1. Are the following events A, B ⊂ Ωroulette independent? Find P(A|B) and P(B|A) in each case. a) A = Red, B = Even, 1. Are the fol...

View details
• #### 数学考试代做 Math 2415代写 数学期末代写 数学作业代写

256

Math 2415 Final Exam 数学考试代做 To get full credit you must show ALL your work. The problems must be solved without any assistance of others or the usage of unauthorized material To get fu...

View details
• #### 应用回归分析作业代写 MATH5806代写 数学作业代写 R代写

98

MATH5806 Applied Regression Analysis Mid-session Test 应用回归分析作业代写 Note: • This assessment is due Thursday 30th June (Week 5), 2:30pm and must be uploaded to Moodle. You have 1.5 ho...

View details
• #### 线性常微分方程代写 数学函数代写 微分方程代写 数学代写

274

CHAPTER 1. LINEAR ORDINARY DIFFERENTIAL EQUATIONS 线性常微分方程代写 2.Suppose that the data in Table 1.3 gave the absolute difference as a constant instead of the relative change. The recursio...

View details
1