Tutorial - Design and Analysis of Algorithms II

1.) Greedy Algorithms works by making the decision that seems most promising at any moment; it never reconsiders this decision, whatever situation may arise later.
Consider the problem of "Making Change".
Coins that are available are:
· dollars (100 cents)
· quarters (25 cents)
· dimes (10 cents)
· nickels (5 cents)
· pennies (1 cent)
Problem  :  Make a change of a given amount using the smallest possible number of coins.
Example  :  
Make a change for $2.89 (289 cents), here n = 2.89 and the solution contains 2 dollars, 3 quarters, 1 dime and 4 pennies. The algorithm is greedy because at every stage it chooses the largest coin without worrying about the consequences. Moreover, it never changes its mind in the sense that once a coin has been included in the solution set, it remains there.
Design an algorithm to solve the above problem using the greedy strategy.
2.) A thief robbing a store can carry a maximum weight of W in his knapsack. There are n items, and the i^th item weighs w_i and is worth v_i dollars. What items should the thief take in order make the maximum money out of them?
There are two versions of this problem:
Fractional knapsack problem: The setup is same, but the thief can take fractions of each item, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of x_i of item i, where 0 ≤ x_i ≤ 1.

0-1 knapsack problem: The setup is the same, but the items may not be broken into smaller pieces, so the thief may decide either to take an item or to leave it (binary choice) behind.
Fractional knapsack problem
· Exhibit greedy choice property.
        => Greedy algorithm exists.
· Exhibit optimal substructure property.
0-1 knapsack problem
· Does not Exhibit greedy choice property.
        => No greedy algorithm exists.
· Exhibit optimal substructure property.
· Only dynamic programming algorithm exists.
Design a Greedy algorithm solution and a Dynamic programming solution to the fractional knapsack problem and the 0-1 knapsack problem respectively.
3.) Does backtracking make an algorithm non-deterministic? Explain your answer.
4.) Design an algorithm using backtracking, to position n queens on an n x n chess board so that no two queens threaten the others.
Input: positive integer n
Output: all possible ways n queens can be placed on an n x n chess board so that no two queens threaten each other. Each output consists of an array of integers ‘col’ indexed from 1 to n, where col[i] is the column where the queen in i^th row is placed.

5.) Design an algorithm for the breadth first search using the branch and bound approach.