CS 6212 Homework 4
cs算法课业代做 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
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) cs算法课业代做
Consider an arbitrary binary tree T of n nodes, and assume that its nodes are labeled 1 through n in such a way that the pre-order traversal of T visits the nodes in the following order: 1,2,… , n.
a. Give three examples of T forn= 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 X[1:n] of 1,2,… , n. Using the observation above, write a divide-and-conquer algorithm that takes as input a permutation (i.e., array)X[1:n]of the nodes, and constructs as output the tree T whose inorder traversal is X[1:n] .
c. Conclude a Backtracking formulation and algorithm for generating all binary trees ofnnodes.
Problem 5: (25 points) cs算法课业代做
A complete graph is a graph where there is an edge between every pair of nodes. A traveling salesman tour (TST) in a graph is a Hamiltonian cycle in the graph, and the weight of a TST in a weighted graph is the sum of the weights of the edges in the TST.
a. Give a greedy algorithm that attempts to compute a minimum-weight TST in a weighted complete graph. Analyze the time complexity of your algorithm.
b. Prove by a counterexample that the greedy solution is not necessarily optimal.
c. Give a divide-and-conquer algorithm that attempts to compute a minimum-weight TST in a weighted complete graph. Analyze the time complexity of your algorithm.
d. Prove by a counterexample that your divide-and-conquer solution is not necessarily optimal.
Bonus Problem: (5 points) cs算法课业代做
In Problem 2, it was observed that in any binary tree T whose pre-order traversal yields the sequence 1, 2,… , n, (i.e., pre-order(T)=[1,2,… ,n ]), the root of every subtree T’ of T has the minimum label in T’ (i.e., min(T’)=root(T’)). In this problem, you will prove this observation by induction, but to make such a proof easier, we will generalize the problem a little bit as described next.
Generalization: Assume the labels of the nodes of T are arbitrary distinct numerical values (i.e., not necessarily the successive integers 1 through n), and assume that the pre-order traversal of T lists (i.e., prints) the node labels in a sorted order (i.e., pre-order(T)=a sorted sequence). Let’s call such trees canonically labeled trees.
Prove by induction that for every subtree T’ of a canonically labeled tree T, min(T’)=root(T’).
Hint: the induction is on the number of nodes of T.
更多代写：安卓/Android代写 考试助攻 英国Statistics代写 Essay代写网站推荐 research写作 金融会计代写
