a. The total dispersion of a permutation f of a set {1, 2, … , n} is 𝐷 𝑓 = |𝑓 𝑖 − 𝑖|𝑛𝑖=1 . Write
a backtracking algorithm that generates all permutations of {1, 2, … , n} where their total
dispersion is ≤ k, for some given input positive integer k.
b. Let A[1:n, 1:n] be matrix of real numbers. Write a backtracking algorithm that generates all
permutations f of {1, 2, … , n} where 𝐴 𝑖, 𝑓 𝑖 < 𝐶𝑛𝑖=1 , for some given input constant 𝐶.
Problem 2: (15 points)
a. Let 𝐺1 = (𝑉1,𝐸1) and 𝐺2 = (𝑉2, 𝐸2) be two undirected graphs, where 𝑉1 = {1, 2, … , 𝑛} and
𝑉2 = {1, 2, … , 𝑚} and 𝑚 ≥ 𝑛. A monomorphism from 𝐺1 to 𝐺2 is any one-to-one function
from 𝑉1 to 𝑉2 such that for all 𝑥 and 𝑦 in 𝑉1, if 𝑥, 𝑦 is an edge in 𝐸1, then (𝑓 𝑥 , 𝑓 𝑦 ) is an
edge in 𝐸2. Write a backtracking algorithm that generates all monomorphisms from 𝐺1 to 𝐺2.
b. How would you use your algorithm in part (a) to generate all k-edge cycles in an input graph
G, for a given input integer k?
c. How would you use your algorithm in part (a) to generate all k-cliques in an input graph G,
for a given input integer k?
Problem 3 (25 points)
a. A node weighted graph is a graph where every node x has a weight w(x). A k-node
independent set of a graph G is a set of k nodes such that no two nodes in that set are adjacent
in G. The weight of an independent set in a node-weighted graph is the sum of the weights of
the nodes in that set. Give an approximate cost function 𝐶 (other than the “cost so far”) for a
branch-and-bound algorithm that takes as input a node-weighted G and 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 node.
Problem 4: (20 points)
Suppose you have an input of n points in the x-y plane: 𝑥1, 𝑦1 , 𝑥2, 𝑦2 , 𝑥3, 𝑦3 , … , 𝑥𝑛, 𝑦𝑛 .
Treat those points as a weighted graph G where (1) the nodes are the n points, (2) every pair of
nodes is an edge (i.e., the graph is complete), and (3) the weight of every edge is the Euclidean
2
distance between its end points, that is, the weight of the edge between point 𝑥𝑖, 𝑦𝑖 and 𝑥𝑗 , 𝑦𝑗
is (𝑥𝑗 − 𝑥𝑖)2 + (𝑦𝑗 − 𝑦𝑖)2. Such a graph is called a Euclidean graph.
a. Give an approximate cost function 𝐶 (other than the “cost so far”) for a branch-and-bound
algorithm that takes as input a Euclidean graph and returns a minimum-weight Hamiltonian
cycle (where the weight of a Hamiltonian cycle is the sum of the weights of its edges). Prove
the validity of your 𝐶 .
b. Apply your B&B algorithm of (a) to derive a minimum-weight Hamiltonian cycle for the
Euclidean graph made up of the following four points: (0,0), (1,0), (1, 5), and (0,1). Make
sure you show the solution tree and the 𝐶 of each generated node.
Problem 5: (25 points)
a. Give a greedy algorithm that attempts to compute a minimum-weight Hamiltonian cycle in a
Euclidean graph.
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
Hamiltonian cycle in a Euclidean 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)
Derive the time complexity of the branch-and-bound algorithm for the job assignment problem if
the approximate cost function 𝐶 is the cost function 𝐶.