Program Design: Algorithms and Data Structures

How to Design/Create Programs

• Designing a program is a creative process with specific steps and techniques.
• The program design process involves input and output specifications.
• It also entails algorithm and data structure design.
• It requires translation of the algorithm into a programming language.
• Testing and debugging the program makes up part of the design process as well.

Input and Output Specification

• Programmers need to know precisely the required input and output for a program.
• Specifications are accurate descriptions of the desired program input and output.

Algorithm and Data Structure Design

• Algorithm is a finite sequence of instructions to solve a problem within a finite time.
• Pseudo Language represents algorithms using a combination of informal English statements and programming language constructs.
• Data type refers to the kind of data a variable can hold in a programming language.
• A variable’s data type represents the set of values it can assume; for example, an integer variable can typically hold values from -32768 to 32767.
• Data structure is a way to organize data, referring to a collection of variables of possibly different data types connected in various ways.
• Data structure and algorithm are equally important and should be considered a unit.
• Algorithm design may depend on how data are stored, and data structure design depends on how we want to manipulate the data.
• Designing data structure and algorithm is expressed in pseudocode or pseudo-language.

Translation to Programming Language

• A program expressed in pseudocode or pseudo-language cannot be run on a computer.
• It must be translated into a programming language.

Program Testing and Debugging

• Program testing and debugging should not be the most time-consuming part of programming.
• Careful algorithm and data structure design can reduce the need for debugging.
• Even experienced programmers use testing techniques to discover and correct errors.

Algorithms

• Algorithm is a recipe for solving a problem.
• An algorithm is a finite set of instructions that accomplish a particular task if followed.
• Everyday encounters with algorithms include following directions or instructions for using products or recipes.

Criteria for Algorithms

• Every algorithm must meet these criteria: Input, Output, Definiteness, Finiteness, and Effectiveness.

Algorithm 1-1 Example

• The problem is to compute the sum of N inputted positive integers (N is a positive integer).
• First a positive number representing the number of integers to add is inputted (N).
• A COUNTER is set up to represent the number of integers read (COUNT).
• COUNT is initialized to 0.
• A variable named SUM is assigned and set to 0.
• If COUNT equals N, the value of SUM is displayed, and the process exits.
• Otherwise, COUNT is incremented by 1.
• A number A is inputted, its value is added to SUM, and the result is stored in SUM.
• Steps repeat from step 6.

Input

• An algorithm may have zero or more quantities that are externally supplied.
• Algorithm 1-1 accepts a minimum of zero input value.

Output

• Outputs are data items resulting from the execution of an algorithm, with at least one quantity processed.
• The output in Algorithm 1-1 is an integer representing the SUM of all numbers inputted by the user.

Definiteness

• The same inputs should yield the same results every time the algorithm is executed.
• There must be a unique initial instruction and successor for each instruction in an algorithm.
• Most instructions are performed from top to bottom unless specified otherwise, and all algorithms must follow a specific sequence of instructions.
• Algorithm 1-1 starts execution on step 1, then step 2, and so on, potentially leading to step 5 or exiting depending on the value of COUNT, with no ambiguous instruction.

Finiteness

• An algorithm will terminate after a finite number of steps.
• Based on Algorithm 1-1, since N is finite, the execution of the algorithm will be completed after a finite number of steps.

Effectiveness

• Effectiveness of an algorithm is measured by whether it performs what it is supposed to do.
• A computer cannot perform an instruction if it has insufficient information or if the result of the execution could be inherently undefined.
• For example, division by zero would render an instruction undefined.