Backtracking

Prev: Recursion Next: Dynamic Programming

Exercises

1.

Describe recursive algorithms for the following generalizations of the SubsetSum problem:

(a) Given an array X[1 .. n] of positive integers and an integer T, compute the number of subsets of X whose elements sum to T.

(b) Given two arrays X[1 .. n] and W[1 .. n] of positive integers and an integer T, where each W[i] denotes the weight of the corresponding element X[i], compute the maximum-weight subset of X whose elements sum to T. If no subset of X sums to T, your algorithm should return $-\infty$.

2.

Describe recursive algorithms for the following variants of the text segmentation problem. Assume that you have a subroutine IsWord that takes an array of characters as input and returns True if and only if that string is a “word”.

(a) Given an array A[1 .. n] of characters, compute the number of partitions of A into words. For example, given the string ARTISTOIL, your algorithm should return 2, for the partitions ARTIST·OIL and ART·IS·TOIL.

(b) Given two arrays A[1 .. n] and B[1 .. n] of characters, decide whether A and B can be partitioned into words at the same indices. For example, the strings

BOTHEARTHANDSATURNSPIN
PINSTARTRAPSANDRAGSLAP

can be partitioned into words at the same indices as follows:

BOT·HEART·HAND·SAT·URNS·PIN
PIN·START·RAPS·AND·RAGS·LAP

(c) Given two arrays A[1 .. n] and B[1 .. n] of characters, compute the number of different ways that A and B can be partitioned into words at the same indices.

3.

An addition chain for an integer n is an increasing sequence of integers that starts with 1 and ends with n, such that each entry after the first is the sum of two earlier entries. More formally, the integer sequence

$$x_0<x_1<x_2<\cdots <x_{\ell }$$

is an addition chain for n if and only if:

• $x_0=1$,
• $x_{\ell }=n$, and
• for every index $k>0$, there are indices $i\le j<k$ such that $x_k=x_i+x_j$.

The length of an addition chain is the number of elements minus 1; we do not count the first entry. For example,

<1, 2, 3, 5, 10, 20, 23, 46, 92, 184, 187, 374>

is an addition chain for 374 of length 11.

(a) Describe a recursive backtracking algorithm to compute a minimum-length addition chain for a given positive integer n. Don’t analyze or optimize your algorithm’s running time, except to satisfy your own curiosity. A correct algorithm whose running time is exponential in n is sufficient for full credit. [Hint: This problem is a lot more like n Queens than text segmentation.]

(b) Describe a recursive backtracking algorithm to compute a minimum-length addition chain for a given positive integer n in time that is sub-exponential in n. [Hint: You may find the results of certain Egyptian rope-fasteners, Indus-River prosodists, and Russian peasants helpful.]

4.

(a) Let A[1 .. m] and B[1 .. n] be two arbitrary arrays. A common subsequence of A and B is both a subsequence of A and a subsequence of B. Give a simple recursive definition for the function lcs(A, B), which gives the length of the longest common subsequence of A and B.

(b) Let A[1 .. m] and B[1 .. n] be two arbitrary arrays. A common supersequence of A and B is another sequence that contains both A and B as subsequences. Give a simple recursive definition for the function scs(A, B), which gives the length of the shortest common supersequence of A and B.

(c) Call a sequence X[1 .. n] of numbers bitonic if there is an index i with 1 < i < n, such that the prefix X[1 .. i] is increasing and the suffix X[i .. n] is decreasing. Give a simple recursive definition for the function lbs(A), which gives the length of the longest bitonic subsequence of an arbitrary array A of integers.

(d) Call a sequence X[1 .. n] oscillating if X[i] < X[i + 1] for all even i, and X[i] > X[i + 1] for all odd i. Give a simple recursive definition for the function los(A), which gives the length of the longest oscillating subsequence of an arbitrary array A of integers.

(e) Give a simple recursive definition for the function sos(A), which gives the length of the shortest oscillating supersequence of an arbitrary array A of integers.

(f) Call a sequence X[1 .. n] convex if $2\cdot X[i]<X[i-1]+X[i+1]$ for all i. Give a simple recursive definition for the function lxs(A), which gives the length of the longest convex subsequence of an arbitrary array A of integers.

5.

For each of the following problems, the input consists of two arrays X[1 .. k] and Y[1 .. n] where k <= n.

(a) Describe a recursive backtracking algorithm to determine whether X is a subsequence of Y. For example, the string PPAP is a subsequence of the string PENPINEAPPLEAPPLEPEN.

(b) Describe a recursive backtracking algorithm to find the smallest number of symbols that can be removed from Y so that X is no longer a subsequence. Equivalently, your algorithm should find the longest subsequence of Y that is not a supersequence of X. For example, after removing two symbols from the string PENPINEAPPLEAPPLEPEN, the string PPAP is no longer a subsequence.

(c) Describe a recursive backtracking algorithm to determine whether X occurs as two disjoint subsequences of Y. For example, the string PPAP appears as two disjoint subsequences in the string PENPINEAPPLEAPPLEPEN.

Don’t analyze the running times of your algorithms, except to satisfy your own curiosity. All three algorithms run in exponential time; we’ll improve that later, so the precise running time isn’t particularly important.

6.

This problem asks you to design backtracking algorithms to find the cost of an optimal binary search tree that satisfies additional balance constraints.

Your input consists of a sorted array A[1 .. n] of search keys and an array f[1 .. n] of frequency counts, where f[i] is the number of searches for A[i]. This is exactly the same cost function as described in Section 2.8. But now your task is to compute an optimal tree that satisfies some additional constraints.

(a) AVL trees were the earliest self-balancing binary search trees. An AVL tree is a binary search tree where for every node v, the height of the left subtree of v and the height of the right subtree of v differ by at most one.

Describe a recursive backtracking algorithm to construct an optimal AVL tree for a given set of search keys and frequencies.

(b) Symmetric binary B-trees, better known as red-black trees, are binary search trees with the following additional constraints:

• Every node is either red or black.
• Every red node has a black parent.
• Every root-to-leaf path contains the same number of black nodes.

Describe a recursive backtracking algorithm to construct an optimal red-black tree for a given set of search keys and frequencies.

(c) AA trees are red-black trees with one additional constraint:

• No left child is red.

Describe a recursive backtracking algorithm to construct an optimal AA tree for a given set of search keys and frequencies.

Don’t analyze the running times of your algorithms, except to satisfy your own curiosity. All three algorithms run in exponential time; we’ll improve that later, so the precise running times aren’t particularly important.

Prev: Recursion Next: Dynamic Programming