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.
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.
其他代写：作业代写 作业加急 加拿大代写 essay代写 英国代写 app代写 algorithm代写 assignment代写 analysis代写 code代写 assembly代写 CS代写 homework代写 Exercise代写 course代写 Data Analysis代写 data代写 北美代写 北美作业代写 澳大利亚代写
