闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

AMS 301 Finite Mathematical Structures

Exam 2

Question 1 (5 points) Highlight (or draw below) the shortest path tree rooted at node A in the graph below. What is the name of the algorithm you used?

Question 2 (15 points) Using the same graph as in Question 1, ﬁnd an approximately optimal (no worse than 2 ●opt) Traveling Salesperson (TSP) tour. State any algorithms you use and (brieﬂy) explain each step.

Question 3 (10 points) Indicate whether each statement is ”True” or ”False.” In all parts, graphs are assumed to include at least 3 nodes.

(i) Consider a circuit C in a graph G, where not all edges in C have the same weight. The heaviest edge in this circuit must not be in any MST for G.

(ii) There are n! ways to arrange n distinct objects around a circle.

(iii) Suppose that all edge costs for a graph G are equal. Then, the BFS tree rooted at vertex A is the shortest paths tree rooted at A.

(iv) If all edge costs in a graph G are distinct, then there is a unique MST.

(v) Consider a graph G containing vertices A and B (and possibly others). A BFS tree rooted at vertex A and a BFS tree rooted at vertex B must have the same number of edges.

Question 4 (8 points) In all parts of this problem, we consider a balanced 7-ary tree T with 80 internal nodes. (a) How many leaves does T have? Show your work.

(b) What is the height of the tree T? Show your work.

Question 5 (12 points)

(a) Consider a connected graph G on 41 vertices. What is the largest number of edges that G may have? Show your work.

(b) Consider a tree T on 33 vertices. What is the smallest number of leaves T can have? Show your work.

Question 6 (16 points)

(a) Draw a graph G and assign weights to G’s edges so that Dijkstra’s Algorithm will fail to produce a shortest paths tree, when rooted at a node A. Explain why Dijkstra’s Algorithm fails.

(b) True or False: Let T be a shortest paths tree rooted at a node A in a graph G. If 3 units are added to the weight of every edge, then any shortest paths tree associated with the new weights must include the same edges as T. If you answer “True,” then explain why; if you answer “False,” then provide a counterexample.

Question 7 (14 points) In all parts of this problem, we consider 10-digit numbers. That is, leading zeros are not allowed. For example, 9000000000 is allowed, but 0123456789 is not allowed.

(a) How many 10-digit numbers exist? Show your work.

(b) How many 10-digit numbers exist that are divisible by 5? Show your work.

Question 8 (8 points) I put the Scrabble letters “M,” “A,” “X,” “I,” “M,” “A,” “L” in a bag. Without looking, I select the letters one-by-one and place them in the order of my selections (assume that all Scrabble letters are chosen from the bag with equal probability). Show your work.

(a) How many arrangements of the letters “M,” “A,” “X,” “I,” “M,” “A,” “L” exist?

(b) What is the probability that the letters “M,” “A,” “X” appear in this order, consecutively (as in “ILMAXMA”)?

Question 9 (12 points) A high school basketball team will have 5 players – 3 of them will play the forward position and 2 of them will play the guard position. 15 people try out for the team. Of these people, 7 are able to play the forward position, 6 are able to play the guard position, and 2 are able to play either the forward or the guard positions. How many ways are there to form a team? Show your work.