Lesson 4.1: Algorithms, Pseudocode and Flowcharts

Introduction

In this lesson, we will explore fundamental concepts of programming that form the foundation of any coded solution: algorithms, pseudocode, and flowcharts. By the end of this lesson, students will be able to understand what constitutes a good algorithm, write pseudocode in a structured format, represent algorithms visually through flowcharts, and predict the output of algorithms using trace tables.

Learning Objectives

1. Understand the properties of a good algorithm: correct, unambiguous, finite, and ordered.
2. Write algorithms in structured pseudocode using the concepts of sequence, selection, and iteration.
3. Represent algorithms as flowcharts using standard symbols.
4. Hand-trace or dry-run an algorithm with a trace table to predict its output.
5. Express a solution as clear, unambiguous pseudocode and as a flowchart.

What is an Algorithm?

An algorithm is a finite sequence of well-defined instructions that provide a step-by-step procedure for solving a problem. Whether it's performing a calculation, processing data, or automating tasks, algorithms are crucial in programming.

Properties of a Good Algorithm

To be effective, an algorithm must possess the following properties:

• Correctness: The algorithm should produce the correct output for all valid inputs.
• Unambiguity: Each step of the algorithm must be clear and unambiguous.
• Finiteness: An algorithm must terminate after a finite number of steps.
• Ordered: The steps should be sequenced in a logical order to produce the desired outcome.

Example of Algorithm Properties

Consider an algorithm to find the maximum of two numbers:

1. Start with two numbers, let's say $a$ and $b$.
2. Compare $a$ and $b$:
3. If $a$ is greater than $b$, the maximum is $a$.
4. Otherwise, the maximum is $b$.
5. Output the maximum.
6. End.

This algorithm is correct, unambiguous, finite (it terminates), and ordered.

Writing Pseudocode

Pseudocode is a simplified version of programming code that focuses on the logic of the algorithm rather than adhering strictly to syntax rules of a programming language. It provides a way to express the algorithm in a structured manner.

Structured Pseudocode

Structured pseudocode typically includes three basic constructs:

• Sequence: Executing steps in a linear order.
• Selection: Making a decision based on conditions (e.g., if-else statements).
• Iteration: Repeating steps (e.g., loops).

Example of Pseudocode

Let’s write pseudocode for the maximum number algorithm we discussed earlier:

Algorithm FindMax(a, b)  
  If a > b then  
    max = a  
  Else  
    max = b  
  End If  
  Output max  
End Algorithm

This pseudocode is clear, structured, and conveys the logic of finding the maximum number.

Flowcharts

A flowchart is a visual representation of an algorithm. It uses various symbols to denote operations, decisions, and flow of control. Here are the basic symbols used in flowcharts:

• Oval: Start/End
• Rectangle: Process (instruction)
• Diamond: Decision (condition)
• Arrow: Flow of control

Example Flowchart for Finding Maximum

The flowchart for the algorithm to find the maximum of two numbers is illustrated below:

1. Start (Oval)
2. Input $a$ and $b$ (Rectangle)
3. Diamond: Is $a > b$?

• If Yes: Point to a rectangle labeled $max = a$
• If No: Point to another rectangle labeled $max = b$

1. Output $max$ (Rectangle)
2. End (Oval)

This flowchart corresponds directly to the pseudocode provided earlier, facilitating a visual understanding of how the algorithm proceeds.

Hand-Tracing Algorithms

To ensure that an algorithm works as intended, programmers often perform a hand trace or dry run of the algorithm. This process involves manually walking through the algorithm with a set of test inputs and tracking the variable states at each step.

Example of Hand-Tracing

Let’s dry run the FindMax algorithm with inputs $a = 10$ and $b = 5$:

1. Start
2. Input $a = 10$, $b = 5$
3. Compare: Is $10 > 5$? Yes

• Set $max = 10$

1. Output $max$ (which is 10)
2. End

Trace Table

To further illustrate this, we can use a trace table:

Step	a	b	max	Decision
1	10	5	-	Start
2	10	5	-	Compare $a$ and $b$, $10 > 5$
3	10	5	10	Set $max = a$
4	10	5	10	Output $max$
5	10	5	10	End

Using this approach ensures that we can validate the correctness of the algorithm before coding it.

Conclusion

In this lesson, students learned about algorithms and their properties, how to write structured pseudocode, the use of flowcharts for visual representation, and the importance of hand-tracing algorithms. These foundational concepts are crucial as you continue your programming journey.

Study Notes

• An algorithm is a finite sequence of well-defined instructions that solves a problem.
• Good algorithms are correct, unambiguous, finite, and ordered.
• Pseudocode simplifies programming code to focus on logic.
• Flowcharts use symbols like ovals, rectangles, and diamonds to represent algorithms visually.
• Hand-tracing or dry-running algorithms helps ensure they work as intended before coding.