Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i.e., implement rand7() using rand5()).

First, observe that we cannot do this in a guaranteed finite amount of time. Why? Let’s see bya parallel example: How would you use rand2() to create rand3()?
Observe that each call of rand2() and the corresponding decision you make can be represented by a decision tree. On each node, you have two branches. You take the left one when
rand2() equals 0 (which happens with 1/2 probability). You take the right one when rand2() equals 1 (which happens with 1/2 probability). You continue branching left and right as you continue to call 1/2. When you reach a leaf, you return a result of 1, 2 or 3 (your rand3() results).
»»    What’s the probability of taking each branch? 1/2.
»»    What’s the probability to reach a particular leaf node? 1/2^j (for some j).
»»    What the probability of returning 3 (for example)? We could compute this by summing up the probabilities of reaching each leaf node with value 3. Each of these paths has   probability 1/2^j, so we know that the total probability of returning 3 must be a series of terms of reciprocal powers of 2 (e.g., 1/2^x + 1/2^y + 1/2^z + ...).
We also know, however, that the probability of returning 3 must be 1/3 (because rand3() should be perfectly random). Can you find a series of reciprocal powers of 2 that sum to 1/3?

No, because 3 and 2 are relatively prime.
We can similarly conclude that to solve this problem, we will need to accept a small (infinitesimally small) chance that this process will repeat forever. That’s ok.
So, how do we solve this?
In order to generate a random number between 1 and 7, we just need to uniformly generate a larger range than we are looking for and then repeatedly sample until we get a number that is good for us. We will generate a base 5 number with two places with two calls to the RNG.

      public static int rand7() {
              while (true) {
                      int num = 5 * (rand5() - 1) + (rand5() - 1);
                      if (num < 21) return (num % 7 + 1);
              }
      }

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions
(i.e., sub-problems). Let’s say n = 100, so we want to compute the number of ways of making change of 100 cents. What’s the relationship to its sub-problems?

We know that makeChange(100):
= makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100
using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)
Can we reduce this further? Yes!
= makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1

Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dimes.
This leads to a recursive algorithm that looks like this:
1         public static int makeChange(int           n, int denom) {
2                 int next_denom = 0;
3                 switch (denom) {
4                 case 25:
5                         next_denom = 10;
6                         break;
7                 case 10:
8                         next_denom = 5;
9                         break;
10                case 5:
11                        next_denom = 1;
12                        break;
13                case 1:
14                        return 1;
15                }
16                int ways = 0;
17                for (int i = 0; i * denom <=          n; i++) {
18                        ways += makeChange(n - i         * denom, next_denom);
19                }
20                return ways;
21        }
22           
23        System.out.writeln(makeChange(n,           25));

8 queens pblm

We will use a backtracking algorithm. For each row, the column where we want to put the queen is based on checking that it does not violate the required condition.
1. For this, we need to store the column of the queen in each row as soon as we have finalized it. Let ColumnForRow[] be the array which stores the column number for each row.
2. The checks that are required for the three given conditions are:
»»    On same Column :             ColumnForRow[i] == ColumnForRow[j]
»»    On same Diagonal:            (ColumnForRow[i] - ColumnForRow[j] ) == ( i- j) or                                                (ColumnForRow[j] - ColumnForRow[i]) == (i - j)

1        int columnForRow[] = new int [8];
2        boolean check(int row) {
3                for (int i = 0; i < row; i++) {
4                         int diff = Math.abs(columnForRow[i] - columnForRow[row]);
5                      if (diff == 0 || diff == row - i) return false;
6                }
7                return true;
8        }
9   
10       void PlaceQueen(int row){
11               if (row == 8) {
12                     printBoard();
13                     return;
14               }
15               for (int i = 0; i < 8; i++) {
16                     columnForRow[row]=i;
17                     if(check(row)){
18                               PlaceQueen(row+1);
19                     }
20               }
21       }

Implement an algorithm to print all valid (e.g., properly opened and closed) combi- nations of n-pairs of parentheses.

We can solve this problem recursively by recursing through the string. On each iteration, we
have the index for a particular character in the string. We need to select either a left or a right
paren. When can we use left, and when can we use a right paren?
»»    Left: As long as we haven’t used up all the left parentheses, we can always insert a left
      paren.
»»    Right: We can insert a right paren as long as it won’t lead to a syntax error. When will we
      get a syntax error? We will get a syntax error if there are more right parentheses than
      left.
So, we simply keep track of the number of left and right parentheses allowed. If there are left parens remaining, we’ll insert a left paren and recurse. If there are more right parens remaining than left (eg, if there are more left parens used), then we’ll insert a right paren and recurse.

1        public static void printPar(int l, int r, char[] str, int count) {
2                 if (l < 0 || r < l) return; // invalid state
3                 if (l == 0 && r == 0) {
4                         System.out.println(str); // found one, so print it
5                 } else {
6                         if (l > 0) { // try a left paren, if there are some available
7                                str[count] = ‘(‘;
8                                printPar(l - 1, r, str, count + 1);
9                         }
10                        if (r > l) { // try a right paren, if there’s a matching left
11                               str[count] = ‘)’;
12                               printPar(l, r - 1, str, count + 1);
13                        }
14                }   
15       }
16          
17       public static void printPar(int count) {
18                char[] str = new char[count*2];
19                printPar(count, count, str, 0);
20       }