You must partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and such that the sum of the total distances travelled by A and B is minimized.

Two-Person Traversal of a Sequence of Cities. You are given an ordered sequence of n cities, and the distances between every pair of cities. You must partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and such that the sum of the total distances travelled by A and B is minimized. Assume that person A and person B start initially at the first city in their respective subsequences.

Recursion Relation: We recurse on C(i; j), the minimum distance traveled if person A ends at city
i and person B ends at city j. Assume WLOG i < j. The relation is:
{ to j-1 //end
{ sum d(k, k + 1) if i = 0
{ for (k=1) //start
C(i; j) =
{ min 0
where d(i; j) is the distance between cities i and j.
Running Time: There are n2 entries in C(i; j) and lling in each entry takes O(n) for a total of O(n3).

Refrence http://people.csail.mit.edu/bdean/6.046/dp/
http://courses.csail.mit.edu/6.006/fall10/handouts/dpproblems-sol.pdf

Given a number, come up with all of the possible ways to insert '+' and '-' in that number.

for example given 123, possible answer would be

1+23
1+2+3
1-23
1-2+3
1-2-3
1+2-3
12+3
12-3

Stacking The Box Give an algorithm for creating the highest possible stack of boxes with the constraint that if box bj is stacked on box bi,

You are given a set of boxes b1 to bn. Each box bj has an associated width wj , height hj and depth dj. Give an algorithm for creating the highest possible stack of boxes with the constraint that if box bj is stacked on box bi, the 2D base of bi must be larger in both dimensions than the base of bj . You can of course, rotate the boxes to decide which face is the base, but you can use each box only once.
For example, given two boxes with h1 = 5;w1 = 5; d1 = 1 and h2 = 4;w2 = 5; h2 = 2, you should orient box 1 so that it has a base of 5x5 and a height of 1 and stack box 2 on top of it oriented so that it has a height of 5 for a total stack height of 6.

You are given a String number containing the digits of a phone number.Divide the number into groups such that the quality is maximized.Design an efficient algorithm to return the solution that maximizes the quality.

You are given a String number containing the digits of a phone number
(the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example, 000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.
• Usual: A group in which all the digits are distinct. For example, 123 or 90.
The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups)
Divide the number into groups such that the quality is maximized.
Design an efficient algorithm to return the solution that maximizes the quality.

Determine whether the Singly Linked List loops back or ends at a null location in time proportional to the length of the list

You are having a pointer to the head of singly linked list. The list either terminates at null pointer or it loops back to some previous location(not necessarily to the head of the list). You have to determine whether the list loops back or ends at a null location in time proportional to the length of the list. You can use at most a constant amount of extra storage.

Design a Data Structure of size O(n) (e.g. of Given Tree Size n) so that you can answer any such query in O(log n) time.

Given a rooted tree of size n . You receive a series of online queries : "Give nearest common ancestor of u,v " . Your objective is to preprocess the tree in O(n) time to get a data structure of size O(n) so that you can answer any such query in O(log n) time.

Give a data-structure which will guarantee O(log n) time per operation.

Complete binary tree as an efficient data-structure

You are given an array of size n(n being a power of two). All the entries of the array are initialized to zero. You have to perform a sequence of the following online operations :

* (i) Add(i,x) which adds x to the entry A[i].
* (ii) Report sum(i,j) = sum of the entries in the array from indices i to j for any 0 < i < j <= n.

It can be seen easily that we can perform the first operation in O(1) time whereas the second operation may cost O(n) in worst case. Your objective is to perform these operations efficiently. Give a data-structure which will guarantee O(log n) time per operation. (The title of the problem is a hint).

Merge the two Binary Search Trees in time O(log m + log n)

You are given two height balanced binary search trees T and T', storing m and n elements respectively. Every element of tree T is smaller than every element of tree T'. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)?

Determine whether the kth largest element of the heap is greater than x or not.

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.

Searching for a friend

You are standing at a crossing from where there emerge four roads extending to infinity. Your friend is somewhere on one of the four roads. You do not know on which road he is and how far he is from you. You have to walk to your friend and the total distance traveled by you must be at most a constant times the actual distance of your friend from you. In terminology of algorithms, you should traverse O(d) distance, where d is the distance of your friend from you.