算法课业代写 CS 6212代写 algorithm代写 cs算法作业代写

CS 6212 Homework 3

算法课业代写 Problem 1: (15 points) Let a1 < a2 < a3 < a4 < a5 < a6 be 6 numbers accessible with the following probabilities: p1 = 1/20, p2 = 5/20, p3 = 2/20,

Problem 1: (15 points)

Let a₁ < a₂ < a₃ < a₄ < a₅ < a₆ be 6 numbers accessible with the following probabilities: p₁ = 1/20, p₂ = 5/20, p₃ = 2/20, p₄ = 1/20, p₅ = 3/20 and p₆=2/20. Let q₀ be the probability of searching for an item <a₁, q₆ the probability of searching for an item >a₆, and q_i the probability of searching for an item between ai and a_i+1 for i = 1, 2, 3, 4, 5. Take q₆=0, and q_i = 1/20 for i=0, 1, 2, 3, 4, 5. You are to construct an optimal binary search tree.

a. Write down a table for the w_ij‘s, and a table for the C_ij‘s and their corresponding r_ij‘s as defined in the algorithm for optimal binary search trees.

b. Construct the optimal binary search tree.

Problem 2: (25 points) 算法课业代写

You are a consultant for a company where the salary of every employee is given as , and the company has a hierarchical structure, i.e., tree, T: the president is the root, and each node represents the immediate subordinate of its parent node. The company is experiencing major losses; therefore, a decision was made to lay off a certain number of employees. To have the largest cut in cost, the company wants to lay off the employees whose combined salary is the maximum possible, but, to make sure that the company does not lose expertise or information, the company decided that if a certain employee is laid off, then none of his/her immediate subordinates (children nodes) can be laid off. Such a lay-off list is called optimal.

a. Give a dynamic programming algorithm to compute an optimal lay-off list for this company, given T and the salaries ’s. (Note that the president of the company may be laid off too!) 算法课业代写

Hint: Define for each node the quantities and , where

• the maximum sum of salaries of the layoff list for the subproblem corresponding to the subcompany rooted at

• is the same as except that is to be laid off, and

• is the same as except that is not to be laid off.

Your algorithm should compute and , by you deriving recurrence relations for them, and then conclude the layoff list.

b. Analyze the time complexity of your algorithm.

c. Modify your algorithm so that to ensure that the president of the company is not laid off.

Problem 3: (15 points) 算法课业代写

Let G=(V,E) be the following weighted undirected graph: V={1,2,3,4,5} and  E={[(1, 3) 5], [(3, 4) 1], [(3,5) 3], [(1,4) 7], [(2, 4) 3], [(4,5) 5], [(1, 2) 12]} where [(i,j) a] means that (i,j) is an edge of weight a. Apply the all-pairs-shortest-paths algorithm to find the distance between every pair of nodes in G. (Represent the weights by a matrix A^(k) after each step, for k = 1,2,3,4,5.)

Problem 4: (25 points)

Throughout this problem, assume the graphs are undirected and represented by adjacency lists.

a. Using a graph traversal technique, write an algorithm to check if an input graph G is a perfect binary tree. Analyze the time complexity of your algorithm. (Note: your algorithm can compute the degrees of the nodes before performing any traversal.)

b. Same as part (a) except this time your algorithm has to check if the input graph is a full binary tree. Again, analyze the time complexity of your algorithm.

c. Same as part (a) except this time your algorithm has to check if the input graph is a perfect k- ary tree for some integer k (k ≥ 2) that your algorithm must determine. Again, analyze the time complexity of your algorithm.

Problem 5: (20 points) 算法课业代写

Let G = (V,E) be the following undirected graph: V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11}, and E = {(1,3), (1,5), (1,7), (1,10), (1,11), (3,2), (2,6), (6,9), (9,2), (2,7), (7,3), (5,11), (5,8), (5,4), (5,10), (4,10)}

a. Do a depth-first search on G from node 1, showing the depth-first search tree, the backward edges, and the DFN’s and L’s of every node.

b. Identify the articulation points, based on the conditions of the algorithm.

c. Do a breadth-first search on G from node 1, showing the breadth-first search tree, the cross edges, and the distance from 1 to each node (assuming all the edges are of weight 1).

更多代写：CS加拿大网课代上  托福网考作弊  英国微积分Midterm代考  国外研究生论文代写  留学生presentation代写  国外presentation代写

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