Algorithm Design and Problem Solving Notes

Analysis

Coding

Chapter 7: Algorithm Design and Problem Solving
C7.1 Program Development Life Cycle
IGCSE Computer Science

Program Development Life Cycle

DEFINITION

  • The program development life cycle refers to the structured process of planning, designing, developing, testing, deploying, and maintaining software applications.

Overview of Software Development Process

  • Every software that has been developed follows a similar process, although the specifics can vary according to the company. The main phases include:

    • Analysis

    • Coding

    • Design

    • Testing

    • Launch

Mini Software Exam Scenario

Problem Description

  • The task involves processing and storing data for students in a class within the following arrays:

    • 1D array: StudentName[] containing student names.

    • 2D array: StudentMark[][] containing marks for each subject for each student.

    • Variables:

    • ClassSize: number of students in the class

    • SubjectNo: number of subjects studied (constant for all students)

Task Requirements

  • Write a program that fulfills the following requirements:

    • Calculate the combined total marks for each student across all subjects.

    • Calculate the average marks rounded to the nearest whole number.

    • Output for each student:

    • Name

    • Combined total mark

    • Average mark

    • Grade awarded:

      • Distinction for average marks >= 70

      • Merit for average marks between 55 and 70

      • Pass for average marks between 40 and 55

      • Fail for average marks < 40

    • Count and output total distinctions, merits, passes, and fails for the entire class.

  • Note: Use pseudocode or program code and include comments to explain functionality. Data initialization is not required in the arrays.

Analysis

REQUIREMENTS SPECIFICATION

  • The analysis phase involves gathering requirements, understanding the problem domain, and defining the objectives and scope of the software project.

Gaining Insight into Client Needs

  • Engaging in effective discussions and data gathering is crucial to accurately understand client's needs and prevent endless cycles of revisions and corrections in project development.

Two Steps of Analysis

  • The analysis consists mainly of two steps:

    1. Decomposition

    2. Abstraction

Decomposition

Definition

  • Decomposition involves breaking down a complex problem or system into manageable parts.

Example

  • Organizing a Hangout:

    • Sub Task 1: Confirmation of attendees

    • Sub Task 2: Finding a location

    • Sub Task 3: Arranging transportation

Abstraction

Definition

  • Abstraction focuses on simplifying complexity by hiding unnecessary details and emphasizing relevant information.

Example

  • Organizing a Hangout:

    • Sub Task 1: Confirm attendees

    • Sub Task 2: Identify potential locations

  • Prioritize confirming who is going before finalizing a location.

Abstraction - Teaching Scenario

Levels of Detail

  1. Level 1: Program Development Life Cycle

  2. Level 2:

    • Analysis

    • Design

    • Coding

    • Testing

  3. Level 3:

    • Requirements specification focuses on clearly defining the problem and understanding client needs through data exchanges and discussions.

    • Utilization of abstraction and decomposition in identifying program requirements.

Design

Definition

  • The design phase involves planning the structure, architecture, and functionality of the software based on requirements gathered during analysis.

Design Tools

  • W1: Structured diagram

  • W2: Flowchart

  • W3: Pseudocode

Coding

Definition

  • Coding is the implementation stage where design specifications are translated into executable code following appropriate coding standards and practices.

Example: E-commerce Application

  • A detailed description of an e-commerce application can be provided, focusing on how modules like seller center, product listing, and notifications should function.

Testing

Definition

  • Testing involves executing the software to identify defects, verify functionality, and ensure that requirements are met.

Test Types

  1. Unit Testing: Each code part is tested individually.

  2. Integration Testing: Entire program is tested as a whole after components are integrated.

Example in Testing

  • Verify functionality such as the item count increasing after a sale.

The Iterative Nature of the Development Cycle

  • The program development life cycle is often iterative rather than linear, where issues during development may necessitate revisiting earlier stages of the process.

Computer Systems Overview

Definition

  • A computer system consists of software, data, hardware, communications, and people.

Sub-Systems

  • The system can be broken down into sub-systems until each performs a specific function.

Examples of Sub-Systems

  1. Software: The application code

  2. Data: User preferences

  3. Hardware: Servers for data storage

  4. Communication and People: Staff managing the system

Algorithms and Flowcharts

Definition of Algorithm

  • An algorithm is a step-by-step procedure or set of rules designed to perform a specific task or solve a problem.

Examples of Algorithms

  1. Real-Life Scenario: Driving a Car

    • Steps: Walk to car → Open the door → Start the engine → Drive away

  2. Software Example: Alarm Clock

    • Steps: Every second check if time matches; if yes, initiate alarm sound.

Components of a Flowchart

  • Terminator: Marks start or end of flowchart

  • Process: Represents an action step

  • Input/Output: Indicates data entry or output

  • Decision: Directs flow based on conditions

  • Subroutine: Smaller procedure executed within a larger program

Example: Input Validation Program

  • Write a program to output voting eligibility based on age input.

Flowchart:

  1. Start

  2. Input Age

  3. If Age < 18, Output "You cannot vote yet"

  4. Otherwise, Output "You can vote"

  5. End

Assignment Statements

Definition

  • An assignment statement assigns a value to a variable.

  • Example: Price = Cost * 2

Concepts

  • Variables store values, which can be constants or dynamic based on conditions.

Input and Output

Definitions

Input

  • Used for data entry followed by variable storage.

Output

  • Displays information on a screen.

Conditional Statements

  • Allow algorithms to take different paths based on input.

Example:

  • If age is under 18, output "Child". If not, output "Adult".

Iterative Statements

  • Allow repetition of actions until a condition is met.

Types:

  1. FOR…TO…NEXT: Fixed iterations

  2. REPEAT…UNTIL: At least one execution

  3. WHILE…DO…ENDWHILE: Execution may vary

Sorting Algorithms

Bubble Sort

  • Organizes items in a logical sequence, such as alphabetical or numerical order.

Example Code Structure

  • Implement sorting via comparisons and swapping items in the dataset until fully sorted.

Validation and Verification

Validation

  • Ensures that the data entered meets specified requirements. Common validation types include:

    • Range Check: Verifies values fall under acceptable limits.

    • Length Check: Confirms data length meets specifications.

    • Type Check: Ensures data type is as expected.

Verification

  • Confirms that data entered matches the original source. Techniques include double entry and visual checks.

Testing Methodologies

Types of Test Data

  • Normal Data: Expected range of values.

  • Abnormal Data: Values that fall outside normal ranges, indicating error conditions.

  • Extreme Data: Tests upper/lower limits of accepted values.

  • Boundary Data: Values on the thresholds between acceptable and unacceptable input ranges.

Trace Table

  • A method for analysing the purpose of algorithms by documenting the results of each algorithm step with specific test inputs.

Writing and Amending Algorithms

Common Debugging

  • Identifying errors using trace tables and test data evaluation to ensure algorithms function as intended.

Example Problem

  • Write a pseudocode that calculates total cost for ticket purchases and incorporates discount logic based on quantity.

Conclusion

  • These structured methodologies represent effective problem-solving techniques in computer science, enhancing algorithm implementation and ensuring software quality.