Algorithm代写_算法代写_Analysis代写_problem代写

COMP3250A Design and Analysis of Algorithms

Midterm Exam

Algorithm代写 the updated weights with a running time better than running Prim’s or Kruskal’s algorithms from scratch. Design and Analysis of Algorithms

Date: April 3, 2020

1. (30 points) 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(n²) time.
• Algorithm B 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(n³) time.

Which algorithm will you choose? Why? Algorithm代写

2. (30 points) Consider the minimum spanning tree (MST) problem. Suppose you are given an undirected graph G = (V; E) with positive edge weights w_e‘s, e 2 E. Suppose you are further given an MST T of the graph. Finally, consider the scenario when an edge e gets an upgrade and as a result its weight decreases from w_eto w_e⁰ .Algorithm代写

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

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

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

3. (40 points) You met a mighty fortune teller who was able to tell you the prices of a stock in the next n days, denoted as p₁; p₂; : : : ; p_n. 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 valid. Therefore, your goal is to nd two days 1 i < j n such that p_j p_i 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.Algorithm代写

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

• (15 points) Design a divide and conquer algorithm for this problem with a running time better than O(n²).

• (15 points) Analyze the running time of your algorithm

更多其他：代写下单  Resume代写   代写案例     数据分析代写   文学论文代写

合作平台：天才代写 幽灵代写  写手招聘