h1. Meet in the middle
Meet in the middle (sometimes called split and merge) is a clever idea that uses caching to get efficient solutions. Much like divide et impera it splits the problem in two and then tries to merge the results. The benefit is that by using quite a bit of extra memory you can tackle problems of twice the size you could before.
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 benefit is that by using quite a bit of memory you can tackle problems of twice size you could before.
Before we go on I want to mention that the additional problems are the best part of the article. Now let's go through a few applications of the trick.
Let’s discuss a few applications.
h2. 4sum (popular interview question)
h2. 4sum
bq. Given A, an array of integers, find out if there are any four numbers in the array that sum up to zero (the same element can be used multiple times). For example given A = [2, 3, 1, 0, -4, -1] a solution is 3 + 1 + 0 - 4 = 0 or 0 + 0 + 0 + 0 = 0.
bq. Given an array of integers, find out if there are any four numbers such that the sum of the first three equal to the fourth (you can use the same number more than once).
The naive algorithm checks all four number combinations. This solution takes $O(N^4^)$ time.
The naive algorithm is $O(N^4^)$ try all the possible combinations of four numbers. A less naive algorithm brute forces through all $n^3^$ combinations of three numbers and then efficiently checks if their sum is in the original array by using a hash table.
By now, you’ve probably started thinking how meet in the middle can be applied to this problem. The trick is to rewrite the equation as $a + b = d - c$. Store all the $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains $d - c$. This algorithm has $O(n^2^)$ time and space complexity.
A slightly improved algorithm brute forces through all $n^3^$ three number combinations and efficiently checks if -(a + b + c) is in the original array using a hash table. This algorithm has $O(n^3^)$ complexity.
By now, you’re probably wondering how the meet in the middle technique can be applied here. The critical insight comes from rewriting $a + b + c + d = 0$ as $a + b = -(c + d)$.
Now we store all $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains -(c + d).
Here's how the code looks
== code(c) |
def 4sum(A):
sums = {}
for a in A:
for b in A:
sums[a + b] = (a, b)
for c in A:
for d in A:
if -(c + d) in sums:
print (sums[-(c + d)][0], sums[-(c + d)][1], c, d)
return
print "No solution."
==
This algorithm has $O(n^2^)$ time and space complexity. There's no known faster algorithm for this problem.
h2. Bidirectional search
bq. Find the shortest path between two nodes nodes in a large graph, for example the Facebook friendship graph.
!blog/meet-in-the-middle?12fig26.gif!
'img source':http://goo.gl/6zne3
The breadth first search algorithm is a standard approach for this problem. If the distance between two nodes is $k$ and the average degree in the network is $p$ BFS explores $O(p^k^)$ nodes.
A better solution starts from both nodes and sees when the two search frontiers meet. This reduces the number of states explored to $O(p^k/2^)$.
The approach works well with both path finding problems on explicit graphs and with implicit state graphs like the ones you find in games.
h2. Breaking 2DES
DES is an encryption standard which uses 56 bit keys. Today computers can use a brute force approach to break the encryption. One simple approach to make the encryption more secure is to apply it twice, using two different keys. Even this approach is susceptible to the meet in the middle attack developed by Diffie Hellman. 3DES is currently used, and it encrypts the message three times using 3 keys.
!<blog/meet-in-the-middle?2des.png 70%!
DES is an encryption standard which uses 56 bit keys. Today computers can use a brute force approach to break the encryption. One simple approach to make the encryption more secure is to apply it twice, using two different keys. This approach is susceptible to the meet in the middle attack developed by Diffie-Hellman. 3DES works around this problem by encrypting the message 3 times using 2 keys.
Let’s see why 2DES is vulnerable. Let $Ek$ be the encryption function using the secret key $k$ and $Dk$ the decryption function using the secret key $k$. 2DES uses $Ek1(Ek2(p)) = s$ to encrypt and $Dk2(Dk1(s)) = p$ to decrypt.
Let’s see why 2DES is vulnerable. Let $Ek$ be the encryption function using the secret key $k$ and $Dk$ the decryption function using the secret key $k$. 2DES uses two keys, k and K. Ek(EK(p)) = s does the encryption and DK(Dk(s)) = p does the decryption.
Diffie Hellman’s meet in the middle attack trades off space for time to find out the two secret keys.
For the pattern p it tries all the possible keys to obtain a set of numbers corresponding $Ek(p)$. Also for the pattern s it uses all the possible keys to decrypt s, $Dk(s)$.
If we find any match in the two sets it means that $Ek1(p) = Dk2(s)$ so the secret keys are k1 and k2.
The naive brute force algorithm would go through $2^56^ * 2^56^$ iterations by brute forcing through all possible values of k1 and k2 while this algorithm uses $2^56^ * 56$ memory to store $Ek(p)$ and does $O(2^56^)$ work to find a match.
Diffie-Hellman’s meet in the middle attack trades off space for time to find out the two secret keys.
For the pattern p it tries all the possible keys to obtain a set of numbers corresponding Ek(p). Also for the pattern s it uses all the possible keys to decrypt s, Dk(s).
If we find any match in the two sets it means that Eki(p) = Dkj(s) so the secret keys are ki and kj.
The naive brute force algorithm does $2^56^ * 2^56^$ iterations going through all possible values of k1 and k2 while this algorithm uses $2^56^ * 56$ memory to store all Eki(p) and does $2^56^$ work to find a match.
This is quite a bit of space and quite a bit of computation time. But a for a large enough company or country it starts being within the realm of posibility.
h2. Discrete logarithm
The problem DOUBLE the International Olympiad in Informatics 2001 was basically asking to break 2DES for keys of size 24 which is quite feasible.
bq. Given n a prime number and p, q two integer numbers between 0 and n-1 find k such that p^k^ = q modulo n.
h2. Discrete logarithm
This problem can be solved using the baby step, giant step algorithm which uses the meet in the middle trick.
We can write k = $i sqrt(n) + j$
Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$.
Now our equality looks like this $p^(i ([sqrt(n)] + 1) + j)^ = q modulo n$.
We can divide by $p^j^$ and get $p^(i[sqrt(n)] + 1)^ = qp^-j^ modulo n$.
Using meet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a colision.
The algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.
bq. Given n a prime number and p, q two integers between 0 and n-1, find k such that p^k^ = q (mod n).
h2. Bidirectional search(interview question)
The naive solution goes through all possible values of k and takes $O(n)$ time.
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.
The baby-step, giant-step algorithm solves the problem more efficiently using the meet in the middle trick.
Let's write k = $i[sqrt(n)] + j$
Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$.
Replacing k in the equality we get $p^(i[sqrt(n)] + j)^ = q (mod n)$.
Dividing by $p^j^$ we get $p^i[sqrt(n)]^ = qp^-j^ (mod n)$.
At this point we can brute force through the numbers on each side of the equality and find a colision.
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.
The algorithm takes $O(sqrt(n))$ space and $O(sqrt(n))$ time.
h2. Caveats
Unlike divide and conquer the trick in meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.
Unlike divide and conquer meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.
Bidirectional search can be often replaced by some search algorithm that uses some heuristics like A*.
h2. Additional problems
# Friend of a friend(interview question): Given two user names in a social network find design an efficient way to test if one is a friend of a friend of the other.
# Equal partition: Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (Hint: complexity $O(2^n/2^)$)
# 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. (Hint: complexity $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. (Hint: complexity $O(4^n/2^)$)
# 8 puzzle: The 8 puzzle is a sliding tile puzzle of 3x3 slots with 8 tiles and one empty slot. At each step you can move one of the orthogonaly neighbouring tiles to the empty slot. The game starts from a random initial configuration and the purpose is to get to the * in the fewest number of moves. Figure out an efficient algorithm that solves the 8 puzzle. (Hint: Each position is solvable in at most 31 moves) In the picture we see a sequence of moves that solves the puzzle.
!scratch-meet-in-the-middle?8puzzle.png!
# *Friend of a friend*(interview question) Given two user names in a social network design an efficient way to test if one is a friend of a friend of the other.
# *6 degrees of separation* Given two user names in a social network design an efficient way to test if they are at most 6 friends apart.
# *Equal partition* Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (Hint: complexity $O(2^n/2^)$)
# *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. (Hint: complexity $O(3^n/2^)$)
# *Square fence* You're given an array L which represents the lengths of n planks. You have to answer if there's any way to form the edges of a square fence using all the planks without breaking or overlapping them. (Hint: complexity $O(4^n/2^)$)
# *8 puzzle* The 8 puzzle is a sliding tile game of 3x3 slots with 8 tiles and one empty slot. At each step you can move one of the orthogonally neighbouring tiles to the empty slot. The game starts from a random initial configuration and the purpose is to get to the final sorted configuration in the fewest number of moves. Figure out an efficient algorithm that solves the 8 puzzle. (Hint: Each position is solvable in at most 31 moves) In the picture we see a sequence of moves that solves the puzzle.
!blog/meet-in-the-middle?8puzzle.png!
# *4 reversals* We are given two equal length strings S and T. Figure out if we can get string T starting from string S and applying 4 substring reversal operations. (Hint: complexity O(n^5^))
Try the to solve these problems in the comment section.
Try to solve them in the comment section.
