Computer Science 15-112, Spring 2012
Class Notes:  Problem-Solving with Top-Down Design


  1. Required Reading
  2. Problem-Solving with Programming
  3. Top-Down Design (Divide-and-Conquer)
  4. Practice, Practice, Practice...

Problem-Solving with Top-Down Design

  1. Required Reading
    1. Wikipedia page on Problem Solving (especially Problem-Solving Techniques)
    2. Wikipedia page on Polya's "How to Solve It"
      Optionally, read the entire book: Polya, How to Solve It
       
  2. Problem-Solving with Programming
    1. Understand the Problem
      • Define the problem precisely
      • Do not skip this step!  Do not skimp on this step!
    2. Devise a Plan
      • Solve the problem without programming!
        1. Use the problem-solving strategies from the required reading
          • Abstraction, analogy, reduction, trial-and-error, proof, etc...
        2. Compare alternative solutions
          • Desirable properties:  clarity, simplicity, efficiency, generality
          • Future concerns (after more CS courses):  usability, accessibility, security, privacy, testability, reliability, scalability, compatibility, extensibility, durability, maintainability, portability, provability, ...
        3. Write your solution so it is amenable to translating into code
          • Use explicit, small, clear steps
            (Do not require human ingenuity or intuition in any step)
          • Make your steps work even for very, very large inputs (this helps with the previous point)
          • Do not require human memory
            • Explicitly write down values you need to remember
            • Give these good names (they will become variables when you translate into code)
    3. Carry out the Plan
      • Translate your solution into code
        1. First write the test cases (this is the first step, not the last step!)
        2. Translate your manual solutions from above, step by step, into code
          • Use top-down design (see below)
        3. Test your solution robotically and manually
          • Look for boundary or edge cases of equivalence classes of input
          • Look for pathological cases (divide by 0, extremely large or small input, ...)
    4. Examine and Review
      • Check your solution with common-sense
      • Discuss and compare your solution with others
      • Store your solution in a searchable archive
         
  3. Top-Down Design (Divide-and-Conquer)
  4. Practice, Practice, Practice...

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem