2.2 Algorithms

 

     Programming in C    

2 - 6  MARKS 

What is an Algorithm?

An algorithm is a finite sequence of well-defined, logical steps used to solve a given problem or to perform a specific task. Each step of an algorithm is precise, unambiguous, and executable, ensuring that the problem is solved correctly.

According to computer scientist Niklaus Wirth,
Program = Algorithm + Data,
which indicates that an algorithm forms the logical foundation of any computer program.

A well-designed algorithm must always terminate after a finite number of steps and produce at least one output for the given input. Algorithms are language-independent, meaning they can be implemented using any programming language.

Algorithms are essential because they help in systematic problem-solving, improve clarity of logic, reduce errors, and make program development easier and more efficient.

Key Features of an Algorithm:

1. Finite – Ends after a limited number of steps

2. Definite – Each step is clear and unambiguous

3. Input – Accepts zero or more inputs

4. Output – Produces at least one output

5. Effective – Steps are simple and feasible to execute

Example: Algorithm to Program Conversion 

Problem

Add two integers and display the result.

Algorithm

1. START

2. PRINT “ENTER TWO NUMBERS”

3. INPUT A, B

4. R = A + B

5. PRINT “RESULT =”

6. PRINT R

7. STOP

C Program

int main()
{
    int A, B, R;
    printf("\n ENTER TWO NUMBERS:");
    scanf("%d%d", &A, &B);
    R = A + B;
    printf("\n RESULT = %d", R);
    return 0;
}

    16 MARKS 

Algorithms 

Introduction

To solve any problem systematically, a plan is required. This plan defines a procedure to solve the problem using logic and reasoning. In computer science, such a procedure-wise plan is known as an algorithm.

Computer scientist Niklaus Wirth stated:

Program = Algorithm + Data

This means that a program is formed by combining a logical procedure (algorithm) with the data on which it operates.

---

What is an Algorithm?

An algorithm is defined as:

“An effective procedure for solving a problem in a finite number of steps.”

Key characteristics of an algorithm:

• It must be effective, i.e., produce a result

• It must have a finite number of steps

• It is guaranteed to terminate

• It always provides an answer, even if the answer is “no solution exists”

A well-designed algorithm never runs indefinitely.

---

Different Ways of Representing Algorithms

Algorithms can be represented in four different ways:

1. Step-form

2. Pseudo-code

3. Flowchart

4. Nassi–Schneiderman technique

Step-form

• Uses simple natural language

• Each step performs a specific action

• Steps are logically ordered

Pseudo-code

• Written using restricted vocabulary

• More precise than natural language

• Easy to convert into programming code

Flowchart

• Graphical representation

• Uses symbols to show:

  • Sequence

  • Decision

  • Repetition

Nassi–Schneiderman

• Graphical technique

• Beyond the scope of this discussion

---

Key Features of an Algorithm

An algorithm consists of three basic constructs:

1. Sequence (Process)

2. Decision (Selection)

3. Repetition (Iteration / Looping)

---

Example: Algorithm for Making Tea (Step-form)

1. If the kettle does not contain water, fill the kettle

2. Switch on the kettle

3. If the teapot is not empty, empty it

4. Place tea leaves in the teapot

5. If water is not boiling, repeat step 5

6. Switch off the kettle

7. Pour water into the teapot

This example shows:

• Decision (checking conditions)

• Repetition (waiting until boiling)

• Sequence (ordered execution)

---

Sequence Construct

Sequence means executing steps in the given order.
If the order is changed, the algorithm may fail.

---

Decision Constructs

Decision constructs work on true or false propositions.

if…then

if proposition then process

if…then…else

if proposition
   then process1
else
   process2

A proposition is a condition that evaluates to true or false, never both.

---

Repetition Constructs

Repetition allows steps to be executed multiple times.

Repeat Loop

repeat
   process
until proposition

✔ Condition is checked after execution
⚠ May cause errors if condition is already satisfied

---

While Loop

while proposition
   process

✔ Condition is checked before execution
✔ Prevents unnecessary repetition
✔ Safer than repeat loop

---

if…then…goto Loop

process
if proposition then goto process

✔ Repeats steps while condition is true
⚠ Makes logic harder to read

---

Termination

An algorithm must terminate after finite steps.

• Algorithms that never terminate are called computational methods

• Analyzing whether an algorithm will terminate is called termination analysis

• Non-terminating algorithms are considered undecidable

---

Correctness of an Algorithm

Correctness refers to how well an algorithm satisfies its intended purpose.

Correctness requires:

• Clearly defined logic

• Traceable steps

• Properly specified data structures

• Correct interfaces between modules

A common measure of correctness is:

Defects per Kilo Lines of Code (KLOC)

---

Developing Algorithms Using Step-form

General Conventions

• START and STOP define algorithm boundaries

• INPUT / READ accept data

• PRINT displays output

• Steps execute sequentially

Arithmetic Operators Used

• ← Assignment

• + Addition

• - Subtraction

• * Multiplication

• / Division (quotient only)

---

Relational Operators in Algorithms

• > Greater than

• < Less than

• <= Less than or equal to

• >= Greater than or equal to

• = Equality

• != Not equal

⚠ ← is preferred for assignment to avoid confusion with equality =

---

Logical Operators

• AND – true if both conditions are true

• OR – true if any condition is true

• NOT – negates the condition

Used to form composite propositions.

---

Strategy for Designing Algorithms

Investigation Phase

1. Identify required outputs

2. Identify input variables

3. Identify decisions and conditions

4. Identify transformation processes

5. Identify execution environment

---

Top-Down Development

• Break the problem into manageable modules

• Ensure modules cooperate logically

• Best suited for large and complex systems

---

Stepwise Refinement

• Decompose modules into smaller procedures

• Define input-output details

• Verify correctness

• Group related processes and variables

• Test each module independently

---

Tracing an Algorithm (Desk Check / Dry Run)

Tracing involves:

• Executing steps one by one

• Verifying intermediate results

• Ensuring logic matches requirements

Used to validate correctness before coding.

---

Converting Algorithms into Programs

Steps involved:

1. Code the algorithm using a programming language

2. Desk-check the program

3. Modify algorithm or code if required

4. Reuse existing logic when possible

---

Algorithm to Program Conversion Example

Problem

Add two integers and display the result.

Algorithm

1. START

2. PRINT “ENTER TWO NUMBERS”

3. INPUT A, B

4. R = A + B

5. PRINT “RESULT =”

6. PRINT R

7. STOP

C Program

int main()
{
    int A, B, R;
    printf("\n ENTER TWO NUMBERS:");
    scanf("%d%d", &A, &B);
    R = A + B;
    printf("\n RESULT = %d", R);
    return 0;
}

---

Conclusion

Algorithms form the foundation of programming. A well-designed algorithm ensures correctness, efficiency, and clarity. Understanding algorithm representation, logic constructs, and design strategies is essential before writing any program.

---

📖 Reference

The content for this topic is prepared by referring to the standard textbook
“Computer Fundamentals and Programming in C”
by Pradip Dey and Manas Ghosh,
Second Edition, Oxford University Press (2018).

---

🌱 About Aivette

Aivette-coi is created with the intention of helping college students learn smartly, revise quickly, and approach exams with confidence.

With love and care,
by Aivette 💙