Backtrack Problems

Design a backtracking algorithm for generating all bit strings of length n that do not have two consecutive 0s. Compute the complexity of the algorithm.
Solution



Algorithm no00_backtrack(b[1..k],n)
1. for $j\leftarrow 1$ to n
2. do
3. if $(b[k-1]+j\neq 0)$ then $b[k]=j$
4. if(k=n) print (b[1..k])
5. else
6. no00_backtrack(b[1..k+1],n)


$T(n)=2T(n-1)+O(1)=O(2^n)$


Design a backtracking algorithm for generating all bit strings of length n that do not have two consecutive 1s. Compute the complexity of the algorithm.

Algorithm no1_backtrack(b[1..k],n)
1. for $i\leftarrow 1$ to n
2. do
3. if($b[k-1]+j\neq 2$) then $b[k]=j$
4. if(k=n) print (b[1..k])
5. else
6. no1_backtrack(b[1..k+1],n)