Search the whole station

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

47

## 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, 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.

### 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).

The prev:

### Related recommendations

• #### 算法作业代写 Algorithm代写 CS代写 cs算法课业代写

267

Algorithm 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
1