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 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.

# *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 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!
Try the to solve these problems in the comment section.