CS算法代写 Graph Theory代写 algorithm代写 cs作业代写
312CS420/520: Graph Theory with Applications to CS, Winter 2022 Homework 2 CS算法代写 Homework Policy: 1. Students should work on homework assignments in groups of preferably three people. Eac...
View detailsSearch the whole station
算法课业代写 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,
Let a1 < a2 < a3 < a4 < a5 < a6 be 6 numbers accessible with the following probabilities: p1 = 1/20, p2 = 5/20, p3 = 2/20, p4 = 1/20, p5 = 3/20 and p6=2/20. Let q0 be the probability of searching for an item <a1, q6 the probability of searching for an item >a6, and qi the probability of searching for an item between ai and ai+1 for i = 1, 2, 3, 4, 5. Take q6=0, and qi = 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 wij‘s, and a table for the Cij‘s and their corresponding rij‘s as defined in the algorithm for optimal binary search trees.
b. Construct the optimal binary search tree.
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.
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.)
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.
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代写 论文代写 写手招聘 英国留学生代写
CS420/520: Graph Theory with Applications to CS, Winter 2022 Homework 2 CS算法代写 Homework Policy: 1. Students should work on homework assignments in groups of preferably three people. Eac...
View detailsAlgorithm in Action CSCI-570 Homework 4 算法作业代写 1 Compute Max-Flow And Min-Cut 2 Escape From the Building In this problem, we need to decide whether there is a feasible plan for all th...
View details