In-Depth Notes on Problem Solving and Algorithms

Problem Solving and Algorithms (Based on Chapter 7)

Chapter Goals

  • Describe the computer problem-solving process and relate it to Polya’s How to Solve It List.
  • Distinguish between a simple type and a composite type.
  • Describe two composite data-structuring mechanisms.

Problem Solving

  • Definition: The act of finding a solution to a perplexing, distressing, vexing, or unsettled question.

Polya’s How to Solve It

  • Reference: How to Solve It: A New Aspect of Mathematical Method by George Polya.
  • The "How to Solve It List" is originally contexted in mathematical problems but is applicable to computer-related issues.

Problem Solving Steps (How to Solve It)

  1. Understand the problem: Carefully analyze the problem statement.
  2. Devise a plan: Create a strategy for solving the problem.
  3. Carry out the plan: Implement the solution.
  4. Look back: Reflect on the solution and the process used.

Strategies for Problem Solving

  • Ask Questions:

  • What do I know about the problem?

  • What information do I have to process to find the solution?

  • What does the solution look like?

  • Are there any special cases?

  • How will I recognize that I've found the solution?

  • Reuse Solutions:

  • Never reinvent the wheel; utilize pre-existing solutions for similar problems.

  • Recognizing tasks or subtasks that have been solved before can save time and effort.

  • Divide and Conquer:

  • Break larger problems into manageable subtasks, solving each smaller problem gradually.

  • This method leverages abstraction and can be applied recursively until all subtasks are simplified.

Computer Problem-Solving Phases

  1. Analysis and Specification Phase:
  • Analyze the problem.
  • Specify requirements.
  1. Algorithm Development Phase:
  • Develop the algorithm.
  • Test the algorithm.
  1. Implementation Phase:
  • Code the algorithm.
  • Test the code.
  1. Maintenance Phase:
  • Use the solution.
  • Maintain the system as necessary.

Phase Interactions

  • Each phase interacts significantly:
  • Analysis feeds into algorithm development, implementation of solutions requires consideration of prior phases, and maintenance influences future analysis and implementation revisions.

Algorithms

  • Definition: A set of unambiguous instructions for solving a problem or subproblem within finite time and data.
  • Abstract Step: Contains unspecified details.
  • Concrete Step: All details are specified, leading to direct implementation instructions.

Methodologies for Developing Algorithms

  1. Top-Down Design: Focuses on the tasks that must be completed.
  2. Object-Oriented Design: Concentrates on the data involved in the solution.

Summary of Methodology

  • Analyze the Problem: Ensure a clear understanding of the issue.
  • List Main Tasks (Main Module): Break down the problem into smaller, manageable tasks that will each become modules.
  • Write Remaining Modules: Further detail each abstract module into tasks.
  • Re-sequence and Revise: Ensure that all modules are concrete, adjusting as necessary.

Control Structures

  • Definition: An instruction that determines the order of operations in a program, influencing the flow of the execution of instructions.