h2. the discrete logarithm problem
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.

 
This problem can be solved using the baby step, giant step algorithm which uses the meet in the middle trick.

The baby step, giant step uses the meet in the middle principle.

We can write k = i ([sqrt(n)] + 1) + 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.
Now the application of meet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a match.

The algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.

This algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.

h2. Additional problems

1. (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))

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

1. (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. (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. (O(3^n/2))

Try the to solve these problems in the comment section.

Try the to solve these two problems in the comment section.

private

public