当前位置:天才代写 > 作业代写 > COMP3250A代写 算法设计和分析代写

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

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

COMP3250A代写

COMP3250A Design and Analysis of Algorithms

Midterm Exam

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.

COMP3250A代写
COMP3250A代写

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.

COMP3250A代写
COMP3250A代写

其他代写:作业代写  作业加急  加拿大代写 essay代写 英国代写 app代写 algorithm代写  assignment代写 analysis代写 code代写 assembly代写 CS代写 homework代写 Exercise代写 course代写 Data Analysis代写 data代写   北美代写  北美作业代写  澳大利亚代写 

合作平台:essay代写 论文代写 写手招聘 英国留学生代写

 

天才代写-代写联系方式