CSC 202: Principles of Problem-Solving and Algorithm Development

Introduction to Problem-Solving and Algorithm Development

• Definition of Computerisation: This term indicates the use of computers to develop software to automate routine human tasks efficiently.

• The Role of Humans in Problem-Solving: Computers do not solve problems independently. They require precise, step-by-step instructions. Success depends on how correctly and precisely a problem is defined, how a solution (algorithm) is designed, and how that solution is implemented (program) using a programming language.

• Problem-Solving Process: This is a three-stage activity:

  • Identifying a problem.

  • Developing an algorithm for that problem.

  • Implementing the algorithm as a computer program.

• Complexity Management: While straightforward problems are easy to solve, complex problems require a methodical approach using specific problem-solving techniques. This starts with identification and ends with a complete working solution.

Concepts of Algorithm

• Abstraction and Decomposition: Problem-solving involves breaking down a large amount of information into smaller, manageable subtasks that can be handled independently.

• Definition of Algorithm: A sequential set of instructions followed to solve a problem using a finite amount of data in a finite amount of time.

• The Programming Roadmap: An algorithm serves as a building block and a roadmap for a programmer. Without it, a programmer might not be able to visualize instructions clearly, leading to programs that do not work as expected.

• Factors for Algorithm Selection: Since multiple algorithms can exist for one problem, selection is based on:

  • Reliability.

  • Accuracy.

  • Ease of modification.

  • Execution time when converted into a high-level language.

• Real-World Examples: Algorithms underpin modern activities such as searching via search engines, messaging, finding words in documents, booking taxis via apps, online banking, and gaming.

• Purpose: Using algorithms increases the reliability, accuracy, and efficiency of obtaining solutions.

Major Components and Properties of Algorithms

Major Sections

Most algorithms consist of three primary sections:

• Input: Represents data sent for processing. Algorithms typically provide variables and a description of the data those variables handle.

• Processing: The actions performed on data to produce results, including computation, selection, and iteration.

• Output: The result produced after processing. In a program, this is usually displayed through an output device, such as a monitor.

Core Properties

• Input/Output: The algorithm must produce output value(s) from a set of specified input value(s), maintaining a clear relationship between them.

• Finiteness: Processing must terminate after a finite number of instructions; it cannot run forever.

• Definiteness: Each step must be precise and easy to understand.

• Effectiveness: The algorithm must be in a form that is easy to convert into a programming statement in a finite amount of time.

• Generality: The algorithm must produce the same output quality when given different types of valid data from a specified domain.

Strategic Roles

• Evaluation: Helps determine if a problem is solvable via computational means.

• Identification: Identifies steps, decision points, and variables needed for program development.

• Decomposition: Reduces complexity by breaking tasks into manageable parts.

• Rational Decision-Making: The atomic nature of subtasks makes decisions fact-based and rational.

Expressions of Algorithms

• Natural Language: Uses everyday languages like English. It is often disadvantageous because it is wordy and confusing.

• Pseudocode: Closely related to programming languages but without strict syntax restrictions. It is less ambiguous than natural language.

• Flowchart: Uses specialized symbols to represent the sequence of instructions. It follows standard rules and requires specialized tools for modification.

Flowchart Symbols and Functions

Algorithm Development Methodologies

Top-Down Design

• This approach uses the "Divide and Conquer" principle.

• Functional Decomposition: A large problem is split into smaller, manageable parts (modules) that are solved independently and then integrated.

• Structure Chart: Problems are arranged in a hierarchical tree structure.

  • Level 0: The top-level abstract step describing the overall problem.

  • Modules: Self-contained sets of steps numbered according to hierarchy level. Numbering starts at zero.

  • Concrete Step: The final module at the bottom that cannot be decomposed further.

Software Development Method (SDM)

Programmers use a specialized software development approach consisting of several phases:

1. Requirement Specification: Critical examination and restating of the problem to eliminate unimportant aspects and ensure clarity.

2. Analysis: Identification of input variables (data), expected output (results), and output formats (e.g., tables with headings). Relationships are identified through formulas.

   • Abstraction: The process of modeling a problem by extracting only relevant information and variables.

3. Design: Developing the sequence of steps (algorithm). This often involves:

   • Stepwise Refinement: The process of expanding steps by providing additional detailed instructions for sub-modules.

4. Implementation: Converting every step of the algorithm into an equivalent statement in a programming language (e.g., Java).

5. Testing: Executing the program to verify correct results. This must include diverse data sets to ensure the program does not crash on unrelated or mistaken inputs.

6. Maintenance: Regular updates to handle hardware changes, new operating systems, security challenges, or performance improvements. This requires proper documentation at every stage of development.

Practical Case Studies

Case Study I: Temperature Conversion

• Problem: Convert Celsius readings to Fahrenheit.

• Analysis:

  • Input: Celsius temperature.

  • Output: Fahrenheit temperature.

  • Constants: $SCALERATE = 9.0/5.0$, $TEMPSCALE = 32$.

  • Formula: $Fahrenheit = (Celsius \times SCALERATE) + TEMPSCALE$

• Refined Design:

  • Step 1: Start.

  • Step 2: Write “Enter Celsius temperature value” and Read Celsius temperature.

  • Step 3: Calculate $Fahrenheit = (Celsius \times \frac{9}{2}) + 32$.

  • Step 4: Print Fahrenheit.

  • Step 5: Stop.

Case Study II: Volume Calculation

• Problem: Calculate the volume of a cylinder given radius and height.

• Analysis:

  • Input: radius (float), height (float).

  • Output: volume (float).

  • Constant: $PI = 3.142$.

  • Formulas:

    • $Area = PI \times Radius \times Radius$

    • $Volume = Area \times Height$

• Algorithm Steps:

  • 1: Start.

  • 2: Request and read input for radius and height.

  • 3: Calculate Area, then calculate Volume.

  • 4: Print Volume.

  • 5: Stop.

Java Programming Implementations

Temperature Converter Code

$\text{import java.util.Scanner;}$ $\text{class TemperatureConverter \{}$ $\text{ public static void main(String[] args) \{}$ $\text{ Scanner scan = new Scanner(System.in);}$ $\text{ float celsius, fahrenheit;}$ $\text{ final float SCALERATE = 9 / 5;}$ $\text{ final float TEMPSCALE = 32;}$ $\text{ System.out.println("Enter temperature in Celsius");}$ $\text{ celsius = scan.nextFloat();}$ \text{ fahrenheit = (celsius \times SCALERATE) + TEMPSCALE;} $\text{ System.out.println("The tempature in Fahrenheit: " + fahrenheit);}$ $\text{ \}}$ $\text{\}}$

Volume Calculator Code

$\text{import java.util.Scanner;}$ $\text{class VolumeCalculator \{}$ $\text{ public static void main(String[] args) \{}$ $\text{ Scanner scan = new Scanner(System.in);}$ $\text{ float radius; float height; double area; double volume;}$ $\text{ System.out.println("Enter the radius");}$ $\text{ radius = scan.nextFloat();}$ $\text{ System.out.println("Enter the height");}$ $\text{ height = scan.nextFloat();}$ \text{ area = 3.142 \times radius \times radius;} \text{ volume = area \times height;} $\text{ System.out.println("The volume of the cylinder is: " + volume);}$ $\text{ \}}$ $\text{\}}$

Questions & Exercises

Algorithm Development Exercises

1. Write an algorithm to calculate simple interest.

2. Write an algorithm to calculate the area of a triangle ($Area = \frac{1}{2} \times base \times height$).

3. Write an algorithm to find the largest of three numbers $x$, $y$, and $z$.

4. Write an algorithm to test if a given integer value is prime.

Programming Exercises (Java)

1. Write a Java program to calculate simple interest.

2. Write a Java program to calculate the area of a triangle.

3. Write a Java program to find the largest of three numbers $x$, $y$, and $z$.

4. Write a Java program to test if a given integer value is prime.