Concept & Properties of Algorithm lecture 3 Week4

COS 102/CSC 120: Problem Solving - Topic 3: Concept & Properties of Algorithm

Lecture 3 Week 4

Lecturer: Dr. Ufuoma C. Ogude

Department: Computer Sciences, University of Lagos

Outlines of the Course (Week 2-7)

• Concept of Problem Solving
• Introduction to Programming
• Concept & Properties of Algorithm
• Fundamentals of Programming (1): Variable/Variable Naming Convention/Data Types in Python
• Fundamentals of Programming (2): Operators and Expressions
• Fundamentals of Programming (3): Control Structures

Concept & Properties of Algorithms (Detailed Outline)

• Concept & Properties of Algorithm
• Role of Algorithm in Problem Solving
• Design of Algorithms
• Pseudocode
• Flowchart

Problem Solving Steps

1. Understand the Problem
2. Formulate a Model
3. Develop an Algorithm
4. Write the Program
5. Test the Program
6. Evaluate the Solution

Design of Algorithms

A person must translate an algorithm into a computer program.

Algorithm: A sequence of instructions describing how to do a task (or process).

Algorithms are eventually translated into programming languages like Python.

Introduction to Algorithms

In day-to-day life, we perform activities by following a certain sequence of steps (e.g., getting ready for school, making breakfast, solving a puzzle). To complete each activity, a sequence of steps is followed.

What is an Algorithm?

• Every problem solution starts with a plan, called an algorithm.
• An algorithm is a plan for solving a problem.
• It's a step-by-step description of the method to solve a problem.
• It's an effective procedure for solving a problem in a finite number of steps.
• Developing an algorithm is a crucial step in program design.

Better Definition of Algorithm

A precise sequence of a limited number of unambiguous, executable steps that terminates in the form of a solution.

Instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data.

Development Process and Characteristics of a Good Algorithm

An algorithm is part of the blueprint/plan for the computer program.

An algorithm is "an effective procedure for solving a class of problems in a finite number of steps."

Every algorithm should have the following 5 characteristic features:

1. Input: The algorithm receives some input.
2. Output: The algorithm produces some output.
3. Definiteness (Precision): The steps are precisely stated or defined.
4. Effectiveness (Uniqueness): Results of each step are uniquely defined and depend only on the input and preceding steps. Each step must be basic enough to be theoretically executable by a human.
5. Termination (Finiteness): The algorithm always stops after a finite number of steps.

Requirements for Writing an Algorithm

When writing an algorithm, clearly identify:

• The input to be taken from the user.
• Processing or computation to be performed to get the desired result.
• The output desired by the user.

Common Algorithmic Actions (NOTE)

Input Data:

• Read: Read student name
• Get: Get student name

Output Information:

• Print: Print 'Program Complete'
• Write: Write record to file
• Output: Output totalAmount
• Display: Display 'Program Complete'

Perform Arithmetic:

• Add: Add num1 to num2
• Subtract: Subtract num1 from num2
• Multiply: Multiply num1 by num2
• Divide: Divide num1 by num2

Assign Values:

• Initialise: Initialise totalPrice to zero
• Set: Set totalPrice to zero
• Store: Store zero in totalPrice

Compare Values (Selection):

• IF...THEN...ELSE
• Example:

  IF num1 > num2 THEN
      ADD num1 to total
  ELSE
      ADD num2 to total
  ENDIF
          

Repeat Actions (Repetition/Looping):

• DOWHILE
• Example:

  DOWHILE Num1 > Num2
      ADD num1 to total
      Multiply total by 3
      Subtract Num2 by 3
  ENDDO
          

Three Key Requirements (Refined)

1. Sequence is:
   1. Precise
   2. Consists of a limited number of steps
2. Each step is:
   1. Unambiguous (Explicit, Definite, Clear-cut, Clear)
   2. Executable
3. The sequence of steps terminates in the form of a solution.

Example 1: Algorithm for Average Marks

Problem: Compute the average marks of students obtained in a TEST of "Computer Programming".

Human Language Specification (In English):

• Read the number of students.
• Read the marks of each student.
• Sum the marks of all students as total marks.
• Divide the total marks by the number of students.
• Report the result of division as average marks of students.

Pseudocode Specification:

• Input N
• Input N marks: m1, m2, m3,..... mN
• T = (m1 + m2 + m3 +... ... ....+ mN) / N
• A = T/N
• Output A (Note: original slide says 'Output N' which seems like a typo, should be 'Output A' for average).

Example 2: Algorithm to Add Two Numbers

Problem: Design an algorithm to add two numbers and display the result.

Algorithm:

1. START
2. Declare three integers a, b & c
3. Define values of a & b
4. Add values of a & b
5. Store output of step 4 to c
6. Print c
7. STOP

Example 3: Algorithm to Find the Square of a Number

Problem: Write an algorithm to find the square of a number.

Identify Input, Process, Output:

• Input: Number whose square is required.
• Process: Multiply the number by itself to get its square.
• Output: Square of the number.

Algorithm:

1. Input a number and store it to num
2. Compute num * num and store it in square
3. Print square

Representation of Algorithms

Two common methods:

1. Flowchart: Graphical representation.
2. Pseudocode: Human language (e.g., English).

Both methods should:

• Showcase the logic of the problem solution, excluding implementation details.
• Clearly reveal the flow of control during program execution.

Flowchart

• A flowchart is the graphical representation of the algorithm for any problem.
• Useful for developing and representing algorithms.
• Drawn using special-purpose symbols connected by arrows called flow lines.
• Symbols indicate actions, flow lines indicate the order of actions.
• Flow lines have arrows to show direction of flow.

Reasons for Flowchart

• Easier to read
• More closely follows a standard
• Easier to understand

Common Flowchart Symbols

• Start/End (Terminator): An oval shape. Indicates the beginning or end of the algorithm/program.
• Process (Action Symbol): A rectangle. Represents a process, action, or a single step. Indicates processes like mathematical operations.
• Input/Output (Data Symbol): A parallelogram. Used to input or output data. For denoting program inputs and outputs.
• Decision: A diamond shape. A decision or branching point where a yes/no or true/false question is asked. The path splits into two branches based on the answer. Used for decision statements (e.g., IF/ELSE).
• Arrow (Flow Line): A line with an arrow. Connects two shapes to show the order of flow between them. Shows relationships.
• On-page Connector: A small circle. Connects two or more parts of a flowchart on the same page.
• Off-page Connector: A home plate-like shape. Connects two parts of a flowchart spread over different pages.

Example 4: Flowchart for Sum of Two Numbers

Algorithm:

1. Start
2. Display "Enter two numbers".
3. Read A and B
4. C = A + B
5. Display "C as sum of two numbers"
6. Stop

Flowchart Sequence:

1. START (Oval)
2. Read two Numbers, A and B (Parallelogram - Input)
3. C = A + B (Rectangle - Processing)
4. Display C as Sum of A and B (Parallelogram - Output)
5. END (Oval)

Example: Flowchart for Average of Two Numbers

1. Start (Oval)
2. Take num1, num2 (Parallelogram - Input)
3. Average = (num1+num2)/2 (Rectangle - Processing)
4. Print Average (Parallelogram - Output)
5. End (Oval)

Guidelines for Developing Flowcharts

• Flowchart should have only one start and one stop symbol.
• On-page connectors are referenced using numbers.
• Off-page connectors are referenced using alphabets.
• General flow of processes is top to bottom or left to right.
• Only one flow line should enter a decision symbol, but two or three flow lines can leave the decision symbol.
• Arrows should not cross each other.

Pseudocode

• "Pseudo" means "not real", so "pseudocode" means "not real code".
• A Pseudocode is another way of representing an algorithm.
• It is a non-formal language that helps programmers develop algorithms.
• It is a cross between human language and a programming language.
• It is a detailed description of instructions a computer must follow in a particular order.
• It is intended for human reading and cannot be executed directly by the computer.
  • Not an actual programming language.
  • Not actually executed on computers.
• No specific standard for writing pseudocode exists.

Why do you need Pseudocode?

• Helps to "think out" a program before writing it.
• May be converted easily into a corresponding programming language code.
• Similar to a programming language, but not as rigid.
• The method of expression is most suitable for a given situation: at times, plain English; at others, a programming language-like syntax.
• Pseudocode is a language typically used for developing algorithms (helps programmers to develop algorithms).

Pseudocode Constructs (Keywords)

Frequently used keywords:

• INPUT
• COMPUTE
• PRINT
• INCREMENT
• DECREMENT
• IF/ELSE
• WHILE
• TRUE/FALSE

The core of pseudocode is the ability to represent 6 programming constructs (always written in uppercase):

• SEQUENCE: Represents linear tasks sequentially performed one after the other.
• WHILE: A loop with a condition at its beginning.
• REPEAT-UNTIL: A loop with a condition at the bottom.
• FOR: Another way of looping.
• IF-THEN-ELSE: A conditional statement changing the flow of the algorithm.
• CASE: The generalization form of IF-THEN-ELSE.

These constructs are also called keywords and are used to describe the control flow of the algorithm.

Solution to Example 3 (Sum of Two Numbers using Pseudocode and Flowchart)

Pseudocode for the sum of two numbers:

INPUT num1
INPUT num2
COMPUTE Result = num1 + num2
PRINT Result

Flowchart for the sum of two numbers:

1. Start (Oval)
2. Read num1, num2 (Parallelogram - Input)
3. Result = num1 + num2 (Rectangle - Processing)
4. Print Result (Parallelogram - Output)
5. Stop (Oval)

Benefits of Pseudocode

• Helps in representing the basic functionality of the intended program.
• Provides the code first in a human-readable language.
• Helps the programmer safeguard against leaving out any important step.
• Helps to review the steps to confirm that the proposed implementation will achieve the desired output (useful for non-programmers).

Flow of Control / Components of an Algorithm

The flow of control shows the flow of events as represented in a flowchart. Events can flow in a sequence, branch based on a decision, or repeat some part for a finite number of times.

Components of an algorithm:

• Values and Variables
• Instruction
• Sequence (of instructions)
• Procedure (involving instructions)
• Selection (between instructions)
• Repetition (of instructions)
• Documentation (beside instructions)

Further Study

Research the advantages and disadvantages of:

• Flowchart
• Pseudocode

Next Lecture: Week 5 - Fundamentals of Programming (1)

• Variable/variable naming convention/data types in Python

Introduction to Python

• Python is a Scripting programming language known for its simplicity and wide breadth of applications, considered one of the best languages for beginners.
• It is a powerful and flexible programming language.
• Uses concise and easy-to-learn syntax, enabling programmers to write more codes and develop complex programs in a much shorter time.
• Used for everything from Web Development to Scientific Computing.
• Python is a "general purpose" language by the greater programming community.
• Created by Guido Rossum in 1989.
• Ideally designed for rapid prototyping of complex applications.
• Has interfaces to many OS system calls and libraries and is extensible to C or C++.
• Many large companies use Python, including NASA, Google, YouTube, BitTorrent, etc.