本次中国香港作业是一个算法分析的算法代写Homework

Problem 1: (15 points)

a) Let A[1:n] be an arbitrary array of real numbers. Write a backtracking algorithm that
generates all permutations f of {1,2,…,n} such that A[f(1)]≤A[f(2)] ≤A[f(3)] ≤ … ≤A[f(n)].

b) Let A[1:n] be an array of positive numbers, k an integer where 1<k< n, and C a positive
number. Give a backtracking algorithm that generates all subsets of k elements of A such that
the sum of those k elements is < C.

Problem 2: (15 points)

Consider an arbitrary binary tree T of 𝑛𝑛 nodes, and assume that its nodes are labeled 1 through 𝑛𝑛
in such a way that the pre-order traversal of T visits the nodes in the following order: 1, 2, … , 𝑛𝑛.

a. Give three examples of T for 𝑛𝑛 = 5. Be sure that in each example, the pre-order traversal of
your tree visits the nodes in the order 1, 2, 3, 4, 5.

Note: Observe –but do not prove– that for every subtree T’ in T, the smallest-label node of T’
is the root of T’. You do not have to do anything in this note, only just observe it.

b. The inorder traversal of T visits the nodes of T in some order that is a permutation 𝑋𝑋[1: 𝑛𝑛] of
1, 2, … , 𝑛𝑛. Using the observation above, write a divide-and-conquer algorithm that takes as
input a permutation (i.e., array) 𝑋𝑋[1:𝑛𝑛] of the 𝑛𝑛 nodes, and constructs as output the tree T
whose inorder traversal is 𝑋𝑋[1: 𝑛𝑛].

c. Conclude a Backtracking formulation and algorithm for generating all binary trees of
𝑛𝑛 nodes.

Problem 3 (25 points)

a. A node-weighted graph is a graph where every node x has a weight w(x). An independent set
of a graph G is any subset of nodes in G such that no two nodes in that subset are adjacent.

The weight of an independent set is the sum of the weights of its nodes. Give an
approximate cost function 𝐶𝐶̂ (other than the “cost so far”) for a branch-and-bound algorithm
that takes as input a node-weighted graph G and a positive integer k, and returns a minimum
weight k-node independent set. Prove the validity of your 𝐶𝐶̂.

b. Apply your algorithm to derive a minimum-weight 3-node independent set in the following
graph G=(V,E): V={1, 2, 3, 4, 5, 6}, E={(1,2), (2,3), (3,4), (4,5), (5,6), (6,1), (1,4), (3,6)},
and w(i)=10-i for all i=1, 2, … , 6. Make sure you show the solution tree and the 𝐶𝐶� of each
generated tree-node. (Note: in order not to generate an independent set multiple times,
generate the nodes of any set in increasing order)

程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB

本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易！

E-mail: itcsdx@outlook.com  微信:itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。