2. The problem with the simple backtracking algorithm we derived in class is tha

Question

2. The problem with the simple backtracking algorithm we derived in class is that it first gen- erates ALL strings of length n and then checks to see if they fit the criteria of S m-length substrings of 1's. A better algorithm would "check" the strings as they are being built and stop building strings if they already contain more than m 1's in a row. This is an example of the type of backtracking known as Branch and Bound To modify this algorithm, we will add in a fourth int parameter to the recursive solve method called numOnes. It's purpose is to record the current number of 1's at the end of the string s (e.g., if the string was "010111011", the value of numOnes would be 2). To implement this modification, you must answer the following questions: . What should the initial value for numOnes be when solve is called from the main method? What value for numOnes should be passed to each of the two recursive calls to solve? The answer here will depend on the current value of numOnes and the digit we are adding to the end of the string . How can you use the value of numOnes to prematurely stop the code from making one . How does the current base case (which is reached when string s has length n) change Implement this scheme, and rerun the code for some values of n and m. For what values of or both recursive calls? (this is the bound on the recursive branching). after the modifications above are made? n and m do you expect these modification to make a difference? 3. If you have time, add in code to determine the number of recursive calls used to solve the problem for a given n and m. Then create a chart for various values of n when m 1 and see if you can experimentally determine the time complexity (we'll prove what it is in class soon).

Explanation / Answer

Ans:

1.The initial value for numOnes will be zero when solve is called from the main method.
2.)numOnes received from last call plus one if next digit is one or zero when next digit zero.
3.)By checking the lenght of the m-length string and numOnes.
4. We will check the value of n and numOnes, if both are equal we will exit from program.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.