﻿ COMP3250A代写 算法设计和分析代写 - 作业代写, 算法代写

# COMP3250A代写 算法设计和分析代写

2021-06-11 17:11 星期五 所属： 作业代写 浏览：67

## Date: April 3, 2020

COMP3250A代写 1.(30points) Suppose you need to solve some computational problem X, and there are three candidate algorithms:

### 1.(30points)   COMP3250A代写

Suppose you need to solve some computational problem X, and there are three candidate algorithms:

• Algorithm A solves X by dividing a problem of size n into 4 subproblems of size n/2, recursively solving each subproblem, and then combining the solutions in O(n2) time.
• AlgorithmB solves X by dividing a problem of size n into 2 subproblems of size n  1, recursively solving each subproblem, and then combining the solutions in O(1) time.
• Algorithm C solves X by dividing a problem of size n into 2 subproblems of size n/2, recursively solving each subproblem, and then combining the solutions in O(n3) time.

Which algorithm will you choose? Why?

### 2.(30 points)    COMP3250A代写

Consider the minimum spanning tree (MST) problem.  Suppose you are given   an undirected graph tt = (V, E) with positive edge weights we’s, e E. Suppose you are further given an MST T of the graph. Finally, consider the scenario when an edge e gets anupgrade and as a result its weight decreases from we to w’e.

a）(10 points) True  or False:  If e is in the MST Tr.t. the original weights, it remains  an MST w.r.t. the updated weights. Give a brief explanation of your answer.

b）(10 points)  Design an algorithm for finding the MST w.r.t. the updated weights with     a running time better than running Prim’s or Kruskal’s algorithms from scratch.

c）(10 points) Analyze the running time of your algorithm.

### 3.(40 points)  COMP3250A代写

You met a mighty fortune teller who was able to tell you the prices of a stock inthe next n days, denoted as p1, p2, . . . , pn. However, to maintain balance of the universe, you are only allow to buy 100 shares once, and sell them once. After that, the predictions will no longer be Therefore, your goal is to find two days 1 i < j n such that pj pi is the largest; then, you may buy on day i and sell on day j.

Example: If the input array is 19, 5, 8, 9, 7, 16, 17, 15, then the best solution is i = 2 and j = 7, i.e, buying on day 2 at price 5 and selling on day 7 at price 17.

a）(10points) Show that the trivial algorithm that tries every pair i and j and calculates the corresponding sums can be implemented in O(n2) time.

b）(15 points) Design a divide and conquer algorithm for this problem with a runningtime better than O(n2).

c）(15 points) Analyze the running time of your algorithm.