Incremental Problem Solving Strategies in Computer Science

Incremental Problem Solving for CS1100 Karl Lieberherr 1

Incremental Problem Solving is Important in CS Comes under different names Incremental Development Iterative Development Staged Development Stepwise Refinement Problem Solving by Reduction or Simplification Divide and Conquer (as a special case) The theme is: start with a simple subproblem first, build your confidence with the simple subproblem, and then attack the next more complex subproblem. Iterate until you have the problem solved. Very useful for spreadsheet development and for query development and for problem solving in general. 2

Demonstrated with Problem 2 in Assignment 2 Look for a partial solution. Find a solution which satisfies conditions 1 to 4 (called a feasible solution). Once we have such a solution, we improve it also satisfying the maximization constraint. How can we find a feasible solution? Look at dependencies between variables. x2 influences x1 (x1=2*x2). x2 influences x4 (x4=x2-1 minimally satisfying condition 3). x2 influences x3 (sum must be 1000). So let s start with giving x2 only 1 share: x2=1. x2 =1, x1 = 2, x4 = 0, x3 = 997 which gives a total of 1000. Success: A feasible solution. x1 2 x2 1 x3 997 x4 0 total 1000 3

Improve feasible solution We have only a partial solution to the problem: we have a feasible solution. But we must also maximize x4! Before we maximize x4 lets try to find a better x4, again solving a simpler problem. What if we add 1 to x2? x1 4 x2 2 x3 993 x4 1 total 1000 Success: we found a better x4 (1 instead of 0). Check carefully that all constraints are satisfied including x3>x1+x2. 4

Can we repeat this? Let s take a big jump, using the idea of binary search. x2 = 200. x1 x2 x3 total 400 200 201 1000 x4 199 But now we left the region of feasibility. (x3>x1+x2 is violated). Let s go in the middle: x2 = 100. x1 x2 total 100 1000 x3 x4 200 601 99 We are back to feasibility. (x3>x1+x2 is satisfied) The correct maximum must be between 100 and 200. How can you find it? 5

Linear Search versus Binary Search With linear search you try 101, 102, 103, until you exit the feasible region. Why will you exit the feasible region at some point? Notice how the value for x3 monotonically decreases. So eventually, x3 will not get enough shares. With binary search you try 150, if it does not succeed you go again in the middle and try 125. If that is in the feasible region, you go into the middle again and try 137 or 138 etc. The linear search you can easily automate in Excel by dragging your formulas down the spreadsheet. Conditional formatting will tell you when to stop. Linear search works for this problem because we found a simple way to enumerate feasible solutions by incrementing x2 while in the feasible region. 6

Better Solution Use Excel to get intuition Generalize the problem: Solve the Problem for TotalShares. 1000 is one special case. Find maximum solutions satisfying all constraints. x2 x1= 2*x2 x4=x2-1 (minimally satisfy constraint) x3=x1+x2+1 (minimally satisfy constraint) TotalShares = 7*x2 7

Closed Form Solution (Through Excel Inspiration) No need for linear or binary search. Works if TotalShares >= 7. x2 = trunc(TotalShares/7) x1= 2*x2 x3= 3*x2+1+MOD(TotalShares,7) ; Third child gets remaining shares. x4= x2-1 Note that x1+x2+x3+x4=7*trunc(TotalShares/7)+mod(TotalShares,7)=TotalShares 8

Summary We solved the ShareDistribution problem in two incremental steps. First we solved the subproblem of finding feasible solutions which resulted in a systematic and efficient way to enumerate feasible solutions. We then used Linear Search or Binary Search to find the maximum feasible solution. Finally we came up with a closed form solution. We will utilize Incremental Problem Solving several times in this course. 9