Algorithm and Problem Solving

ALGORITHM DESIGN AND PROBLEM SOLVING

PROGRAM DEVELOPMENT LIFE CYCLE

The program development life cycle is divided into five stages:
1. Analysis
2. Design
3. Coding
4. Testing
5. Maintenance

Analysis

• The first stage of the program development life cycle that involves investigating the problem.

• This stage uses both decomposition and abstraction.

• Decomposition breaks down a complex problem into smaller parts, which can then be subdivided into even smaller parts, that can be solved easily.

• Abstraction keeps the key elements required for the solution to the problem and discards any unnecessary details and information that is not required.

Design

• The program specification from the analysis stage is used to show to how the program should be developed.

• This stage involves structure charts, flowcharts and pseudocode

Coding and iterative testing

• The program or set of programs is developed. Each module of the program is written using a suitable programming language and then tested to see if it works.

• Iterative testing means that modular tests are conducted, code amended, and tests repeated until the module performs as required.

Testing

• The completed program or set of programs is run many times with different sets of test data. This ensures that all the tasks completed work together as specified in the program design.

Reorder

Reorder the following stages of software development

• Analysis

• Design

• Coding

• Testing

• Maintenance

1

2

3

4

5

• 1
• 2
• 3
• 4
• 5

Match

Match the following

• Analysis

• Design

• Coding

• Testing

Decomposition and Abstraction

structure charts, flowcharts and pseudoc

Code Development

Running a code

• Decomposition and Abstraction

• structure charts, flowcharts and pseudoc

• Code Development

• Running a code

Multiple Choice

Which stage of the SDLC involves gathering and documenting requirements from stakeholders?

• Analysis

• Design

• Coding

• Testing

Multiple Choice

During which phase are algorithms implemented in a specific programming language?

• Analysis

• Design

• Coding

• Testing

Multiple Choice

Which of the following is NOT typically part of the Design phase?

• Creating class diagrams

• Defining the system architecture

• Writing unit tests

• Designing the user interface

Can you answer this?

• There are two sons and 2 fathers in a car. Yet there are only 3 people. Explain how

• There are 2 sons and 2 fathers in a car. Yet there are only 3 people. Explain how

​

​Can you answer this?

Computer Systems, Sub-systems and decomposition

• A computer system is made up of software, data, hardware, communications and people.

• Each computer system can be divided up into a set of sub systems. each sub-systems can be further divided into sub-systems and so on until each sub-system just performs a single action.

Top-down design

• Top-down design is the decomposition of a computer system into a set of sub systems, then breaking each sub-system down into a set of smaller sub-systems, until each sub-system just performs a single action.

• The process of breaking down into smaller sub-systems is called stepwise refinement.

Decomposing a problem.

• The parts of any computer system are

  • Inputs

  • Processes

  • Outputs

  • Storage

Example: An Alarm App

• inputs – time to set the alarm, remove a previously set alarm time, switch an alarm off, press snooze button

• processes – continuously check if the current time matches an alarm time that has been set, storage and removal of alarm times, management of snooze

• outputs – continuous sound/tune (at alarm time or after snooze time expired)

• storage – time(s) for alarms set.

Homework

• Mention one computer system

• identify Input, Processes, Outputs, Storage.

Match

Match the following

• Inputs

• Process

• Output

• Storage

Data to be entered

Task to be performed

Information to be displayed

data that needs to be stored

• Data to be entered

• Task to be performed

• Information to be displayed

• data that needs to be stored

Multiple Choice

Which of the following is NOT typically considered one of the main components of a computer system?

• Hardware

• Software

• People

• Electricity

Multiple Choice

What component of a computer system processes data and controls other parts of the system?

• Memory

• Operating System

• Network Interface Card

• CPU

Multiple Choice

What type of software is designed to perform specific tasks for users?

• Application software
• Firmware
• Utility software
• System software

Multiple Choice

In a computer system, what does the term 'data' primarily refer to?

• The speed at which a computer operates.
• The process of executing commands in a program.
• Physical components of a computer system.
• Information processed or stored by a computer system.

Methods used to design and construct a solution to a problem

• Structure diagrams

• Flowcharts

• Pseudocode.

Structure diagrams

• Structure diagrams can be used to show top-down design in a diagrammatic form.

• The name of the program at the top, below its subprograms

Structure Diagrams

Structure diagram for alarm app

Structure diagram for a calculator

Pair Work

Flowcharts

A Flowchart

• A digramatic representation of an algorithm.

Flowchart symbols

• Begin/End: Terminator flowchart symbols are used at the beginning and end of each flowchart.

Start/Stop (Begin/End)

• Process flowchart symbols are used to show actions, for example, when values are assigned to variables.

Process

• The same flowchart symbol is used to show the input of data and output of information.

Input and output

• Decision Decision flowchart symbols are used to decide which action is to be taken next; these can be used for selection and repetition/iteration.

• There are always two outputs from a decision flowchart symbol.

Decision

Flowchart flow lines use arrows to show the direction of flow, which is usually, but not always, top to bottom and left to right.

Flow lines

​Examples

1. Draw flowchart to find the average of two numbers.

2. Draw a flowchart to allow a user to input the username and password. If the password is correct display the message "Logged in Successfully", Otherwise allow user to re enter the details.

Homework

1. Tickets are sold for a concert at $20 each, if 10 tickets are bought then the discount is 10%, if 20 tickets are bought the discount is 20%. No more than 25 tickets can be bought in a single transaction. Draw a flowchart for this scenario.

2. Draw a flowchart that will accept three numbers from the user, and displays the greatest number among the three numbers.

Multiple Choice

In a program that calculates the area of a circle, what is considered the INPUT?

• The formula πr²

• The radius of the circle

• The calculated area

• The multiplication process

Multiple Choice

In a student grading program, what would be considered an OUTPUT?

• The list of test scores entered

• The calculation of the average

• The final letter grade displayed to the user

• The grading scale used

Multiple Choice

For an ATM withdrawal system, which combination correctly represents the Input-Process-Output sequence?

• Account balance, withdrawal amount, receipt

• PIN verification, money dispensing, new balance calculation

• Card insertion/PIN/amount → Balance verification/transaction processing → Money dispensed/receipt/new balance

• Money dispensed, account update, transaction record

Multiple Choice

In a password validation algorithm, what is NOT typically part of the INPUT?

• he password entered by the user

• The minimum password length requirement

• The error message displayed

• The required character types

Multiple Choice

What does a rectangle represent in a flowchart?

• A decision

• An input or output

• A connector

• A process

Multiple Choice

Which symbol is used to represent a decision in a flowchart?

• Circle
• Square
• Diamond
• Triangle

Multiple Choice

What does an arrow indicate in a flowchart?

• An arrow represents a decision point in a flowchart.
• An arrow indicates the end of a process in a flowchart.
• An arrow shows the start of a flowchart.
• An arrow indicates the direction of flow in a flowchart.

Multiple Choice

Which shape is used for the start and end of a flowchart?

• Triangle
• Diamond
• Rectangle
• Oval

Multiple Choice

In a flowchart, what does the process symbol represent?

• Start/End

• Decision

• Data Input/Output

• Sequential steps or actions

Multiple Choice

What is the output when "a" is 10

• 10

• 9

• 11

Multiple Choice

What will the program print when the value of a is 10

• 10

• 11

• 9

Multiple Choice

What will the program print when the value of "a" is 9

• 9

• 10

• 8

Multiple Choice

What is the output when A is 9 and B is 14

• B is greater

• A is greater

• No output

Multiple Choice

What will be the output when "a" is 15

• a is odd

• a is even

• 16

Pseudocode

​Pseudocode

• Pseudocode is a simple method of showing an algorithm. It describes what the algorithm does by using English key words that are very similar to those used in a high-level programming language.

Principles

1. All keywords (words used to describe a specific action e.g. INPUT) are written in capital letters.

2. Where conditional and loop statements are used, repeated or selected statements are indented by two spaces.

Assignment statement

• A value is assigned to an item/variable using the <--- operator

• Examples

• score <--- 90 score has the value of 90

• age <--- 15 age has the value of 15

• name <--- "Alice" name has the value of Alice

• IsMarried <--- FALSE IsMarried has the value of FALSE

The pseudocode for conditional statements

• When different actions are performed by an algorithm according to the values of the variables, conditional statements can be used to decide which action should be taken.

• There are two types of conditional statement:

  • a condition that can be true or false

  • a choice between several different values

IF … THEN … ELSE … ENDIF

• For an IF condition the THEN path is followed if the condition is true and the ELSE path is followed if the condition is false.

  IF Age < 18

  THEN

  OUTPUT "Child"

  ELSE

  OUTPUT "Adult"

  ENDIF

Discussion questions

• Write a pseudocode for the following scenarios

  1. Determine if the number is even or odd

  2. Check if the grade is pass of fail (pass score>50)

  3. Check if the number is negative or positive

  4. Checking whether its a weekend or not.