Week 9: Problem Solving Algorithm for Linked Data Structures

       In the previous post, I said that I was in ‘pretty good shape’ with regards to my comfort with the material.  This week, I will have to eat my words.  While the concepts are still manageable, the problems that we have to solve in the labs are now unbearably difficult.  I have no choice but to take action before it is too late.
          The topic of this week is problem solving.  This topic choice is inspired by the linked data structures that the professor introduced to us over the last three weeks (linked lists, binary trees and binary search trees).  Although the professor introduced us to binary search trees with linked lists in the previous week, I decided to focus on linked lists only. What a mistake that was.  Binary trees are trees with an arity of two.  Binary search trees are a special case of binary trees in that for every node in the tree, every node in the left subtree is less than the node and every node in the right subtree is greater than the node.  Although the concept is simple enough, the problems that we have to solve can be challenging.  I believe that the difficulties lie in structuring the solutions.  Therefore, I developed a problem solving algorithm that represents a systematic approach to solving problems that involve linked data structures.  Here is the algorithm:

Step 1:  Determine the parameters and return value of the function that will solve the problem.  This sounds trivial but it helps us stay organized for complicated problems.

Step 2:  Decide if we need a helper function.  A clear instance of when we need a helper function is if parts of the problem can only be solved by a function with a different return type than the final return value.  If a helper function is necessary, then follow the problem solving algorithm recursively.  Return to step 1 for the helper function and go through every step.  Then proceed to step 3 for the parent function.

Step 3:  Decide if while loops or recursion is necessary.  In the post, Running with Recursion, I argue that iteration is better for simpler problems and recursion is better for complex problems.  Just like the decision with helper functions, making the right choice can ease the difficulty of problem.

Step 4:  Determine the terminating condition(s).  For while loops, under what condition will the loop terminate?  For recursion, under what condition will the function or method assume as the base case?  Be mindful that for certain problems, there may be multiple terminating conditions.

Step 5:  Determine how the function will put the solution together.  For while loops, what variables do we need?  Which variables will be inside the loop?  Which will be outside?  For recursion, will the function put the solution together on the way to the base case or on the way back?