CS21003 Algorithms ICS29003 Algorithms Laboratory |
Autumn 2012, L-T-P: 3-1-0 L-T-P: 0-0-3 |

## Warm-up Assignment

You are given

Rred marbles andBblue marbles. Your task is to arrange theR+Bmarbles in a line such that certain restrictions are satisfied (see below). You print all possible arrangements under the given restrictions, and the total count of arrangements possible.## Part 1

In this part, the restriction is that no two red marbles may be placed consecutively. Write a single recursive function to print the arrangements and return the count of possibilities. Do not use any global or static variables. Place the available marbles one by one in an array of size

R+B. Whenured andvblue marbles are placed, find out the options (red and/or blue) at the (u+v+ 1)-st position. For each available option, recursively compute the acceptable configurations withu+v+ 1 marbles placed in the array.## Part 2

In this part, two red marbles may appear in consecutive positions, but three or more red marbles are not allowed to come consecutively. Write a second recursive function following the same line of programming logic as in Part 1.

## Sample output

Enter number of red marbles (R) : 2 Enter number of blue marbles (B) : 4 Part 1 rbrbbb rbbrbb rbbbrb rbbbbr brbrbb brbbrb brbbbr bbrbrb bbrbbr bbbrbr Total number of possibilities is 10 Part 2 rrbbbb rbrbbb rbbrbb rbbbrb rbbbbr brrbbb brbrbb brbbrb brbbbr bbrrbb bbrbrb bbrbbr bbbrrb bbbrbr bbbbrr Total number of possibilities is 15## Theoretical exercises

- Construct recurrence relations for computing these counts of arrangements.
- Analyze the running times of these recursive algorithms.