2023年11月25日

算法代写｜CS 6212 Homework 4

本次中国香港作业是一个算法分析的算法代写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)