Introduction to Problem Solving and Algorithmic Processes

Overview of COS 102: Introduction to Problem Solving

Course Identification: COS 102 - Introduction to Problem Solving.
Credit Units: 3 Units.
Module and Unit: Module 1 (Overview of Problem Solving), Unit 2 (The Problem Solving Process and the Role of Algorithm in the Problem Solving Process).
Primary Learning Objectives: * Demonstrate comprehensive knowledge of the problem-solving process. * Demonstrate a clear understanding of the role an algorithm plays within the problem-solving process.

Defining Problem Solving and the Process

Problem Solving Definition: Problem solving is formally defined as the act of obtaining a solution to a specific difficulty, constraint, or challenge.
The Process: This refers to the specific, sequential steps followed to achieve the solution.
Human Approaches to Problems: * Humans utilize various methods to approach challenges, though not all are systematic or reliable for algorithmic development. * Natural Endowment: Solving issues intuitively or "just doing it naturally." * Guesswork-and-Luck: Reaching a solution through non-methodical estimations and chance. * Trial-and-Error: Repeated, varied attempts until a successful outcome is reached.
Systematic Effectiveness: Methods like guesswork or trial-and-error are not the focus of algorithm design because they are not systematically effective or reliable (meaning they cannot be guaranteed true for every instance). For algorithm design, focus is placed on methods that are useful to everyone through systematic effectiveness.

Systematic Problem Solving and Algorithms

Experience as a Blueprint: Formulating a systematic solution often relies on following a "blueprint" or instructions derived from experience to solve a particular problem; this is the core of what an algorithm is.
Process Models: A process model defines specific scientific steps used to solve a problem. The algorithm is an integral part of these systematic ways of solving problems, including the standard problem-solving process model.
The Computer's Role: To solve problems using computers, it is essential to understand the standard information processing model. Computer science is fundamentally about utilizing computers to solve problems originating from the real world or abstract worlds.

Computer Information Processing Model

The Input-Process-Output Cycle: The computer functions as a model of computation where input data is provided to produce a desired output solution.
Input: Obtaining data via user input devices such as a keyboard, mouse, or game control.
Processing: The data is handled by the Central Processing Unit (CPU). In a typical single-CPU computer, user inputs are processed to calculate or transform the data.
Output: The resulting data is produced via output devices, such as display units (monitors), printers, or speakers. This output can take the form of numbers, images, text, or sound.
Storage and Networking: Input and output data can also be transmitted via network devices and storage drives (such as USB flash drives or hard disks).

Example: Calculating the Average Grade

1. Input: Gather all student grades through a keyboard or by reading data from a USB flash drive/hard disk.
2. Process: The CPU performs the mathematical function of adding all individual grades together and computing the average grade.
3. Output: The result (the average) is displayed on a screen, sent to a printer, or both.

The Six Steps of the Problem Solving Process

The systematic process followed in problem-solving involves six distinct stages: 1. Understanding the Problem. 2. Formulating a Model. 3. Developing an Algorithm. 4. Writing the Program. 5. Testing the Program. 6. Evaluating the Solution.

Step 1: Understanding the Problem

Initial Analysis: The first step to solving any problem is ensuring a thorough understanding of the challenge. This involves identifying: * What input data/information is available? * What does that data represent? * What is the specific format of the data (e.g., integers vs. real numbers)? * Are there any pieces of data missing? * Does the person solving the problem have all necessary resources? * What specific output information must be produced? * What format should the result take (text, picture, or graph)? * What are the other computational requirements?
Example Nuances (Grades): * Format: Grades could be integers (e.g., $73$ ) or real numbers (e.g., $73.42$ ). They could be numerical ( $0$ to $100$ ) or letter-based ( $A$ to $F$ ). * Output Choice: The output could be a whole number, a real number, a letter grade, or even a visual representation like a pie chart. * Handling Missing Data: If a student was absent for a test, the solver must decide whether to assign a $0$ and include them in the average or ignore them entirely during computation.

Step 2: Formulating a Model

The Concept of Modeling: This step involves understanding the processing logic. Many complex problems are broken down into smaller mathematical computations. A model (or formula) must be identified or developed if one does not exist.
Numerical Data Model: If input grades are integers or real numbers represented as $x_1, x_2, \text{...}, x_n$ , then the model for the average $A_1$ is: * $A_1 = \frac{x_1 + x_2 + x_3 + \text{...} + x_n}{n}$
Handling Non-Numerical Data (Letter Grades): * Mathematical operations like addition and division cannot be performed directly on letters (e.g., $A+$ , $B-$ ). * Mapping Strategy: A numerical value must be assigned to each letter grade to make computation possible. Example mapping: * $A+ = 12$ * $A = 11$ * $A- = 10$ * $B+ = 9$ * $B = 8$ * $B- = 7$ * $C+ = 6$ * $C = 5$ * $C- = 4$ * $D+ = 3$ * $D = 2$ * $D- = 1$ * $F = 0$ * Letter Grade Model: Using the new assigned integer values $x_1, x_2, \text{...}, x_n$ , the model becomes: * $A_2 = \frac{x_1 + x_2 + x_3 + \text{...} + x_n}{n}$
Refining the Output: If the final result needs to be a percentage but the model produced a number from $0$ to $12$ , the formula must be adjusted using a ratio such as $(A_2 / 12)$ . If a letter grade output is desired from a numerical average, the solver may use a "lookup table" to map numbers back to letters.

Step 3: Developing an Algorithm

Representation: Algorithms must be represented in a way that is understandable to humans. The two most common formats are Pseudo-code and Flowcharts.
Example (DisplayGrades Algorithm in Pseudo-code): 1. Set the sum of the grade values to $0$ . 2. Load all grades $x_1, x_2, \text{...}, x_n$ from a file. 3. Repeat $n$ times: 4. Get grade $x_i$ . 5. Add $x_i$ to the sum. 6. Compute the average to be $sum / n$ . 7. Print the average.
Example (The Broken Lamp Problem): * Logic (Pseudo-code): 1. IF lamp works, go to step 7. 2. Check if lamp is plugged in. 3. IF not plugged in, plug in lamp. 4. Check if bulb is burnt out. 5. IF bulb is burnt, replace bulb. 6. IF lamp doesn’t work, buy new lamp. 7. Quit (problem solved).

Step 4: Writing the Computer Program

Implementation: This step involves translating the algorithm into a language the computer can execute.
Coding Example (Java/Processing style): int sum = 0; byte[] x = loadBytes("numbers"); for (int i=0; i<x.length; i++) { sum = sum + x[i]; } int avg = sum / x.length; print(avg);

Step 5: Testing the Program

Verification: Once written and compiled, the program must be tested to ensure it solves the problem correctly.
Execution: Running the program tells the computer to evaluate the instructions. A successful run should yield the correct output.
Debugging: Programs may fail or produce incorrect results for certain sets of input. These issues are called bugs.
Potential Failures: * Instructions performed out of sequence. * Algorithm not properly converted into code. * The algorithm itself was flawed and did not account for all situations (e.g., edge cases).

Step 6: Evaluating the Solution

Re-evaluating Objectives: After obtaining a result that seems correct, the solver must reconsider the original problem. Does the solution meet the original expectations?
Formatting and Visualization: Simple lists of numbers may not suffice if the goal was to identify patterns or features. Charts or graphs may be needed for better visualization.
Iterative Nature: If data was missing or the results are incomplete, it may be necessary to go back to earlier steps, even returning to Step 1.
Conclusion: A computer only does what it is explicitly told to do. The human problem solver is responsible for interpreting results meaningfully and ensuring they solve the actual problem.