h1. Meet in the middle

Meet in the middle (sometimes called split and merge) is a clever approach which tries to trade off space for time. Let’s discuss a few applications.
 

Meet in the middle (sometimes called split and merge) is a clever approach which tries to trade off space for time. Much like divide et impera it divides the problem in two and then tries to merge the results. The result usually is that you can tackle problems of twice size you could before using the trick. Let’s discuss a few applications.

h2. 4sum

h2. Bidirectional search(interview question)

bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the web graph of the facebook friendship graph, find out the shortest path between them.

bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the facebook friendship graph.

One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. If the distance between two nodes is k and the average branching factor in the network is p then we explore O(p^(k/2)) nodes instead of O(p^k) nodes.

h2. Caveats
Much unlike divide and conquer the trick in meet in the middle can't be applied recursively because the problems
 

h2. Additional problems
# Friend of a friend(inteview question): Given two user names in a social network find an easy way to test if one is a friend of a friend of the other.

# Minimal vertex cover: Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the  graph has at least one node inside the set. (O(3^n/2))
# Square: You're given an array L which represents the sizes of n planks. You have to answer if there's any way to form a square using the planks without breaking them of overlapping them. (complexity O(4^n/2))
# 8 puzzle: Solve 8 puzzle. (Each position is solvable in at most 31 moves.)

# Pancake puzzle: sort pancakes in optimal number of moves.

Try the to solve these problems in the comment section.
http://www.cs.cornell.edu/~wdtseng/icpc/notes/bt3.pdf