Chapter One

Introduction to Data Structures and

Algorithms

1
 Introduction to Data Structures and
Algorithms
Software Engineering
• Is the use of engineering principles in order to develop good
software.
• Human creativity + Computer speed & Reliability = Program.
• There are a number of general principles that apply to many
areas, including aspects of software engineering.
Software Engineering Principles
a) Separation of Concern
– This is a very important principle that has many
applications
– in Software Engineering. Frequently, we have a large,
complex problem with many inter-related aspects.
– To deal with such problems, separate concerns and look
at each concern separately.
b) Modularity
– Every large system must be divided into modules so we
can understand it. 2
– Each module performs a set of tasks.
 Software Engineering Principles....(Continued)

• The important attributes of modules are cohesion and coupli

ng.
• Cohesive
– is a property of modules.
– A cohesive module provides a small number of closely rel
ated services.
• Coupling
– is a property of systems.
– Modules are loosely coupled if the communication betw
een them is simple.
– “Modules form clusters with few interconnections.”
• The goal is: high cohesion and low coupling.

3
Software Engineering Principles....(Continued)

4
 Software Engineering Principles....(Continued)

c) Abstraction
• It is sometimes best to concentrate on general aspects of th
e problem while carefully removing detailed aspects.
d) Anticipating Change
• General rule: write all documents and code under the assump
tion that they will subsequently be corrected, adapted, or cha
nged by somebody else.
e) Generality: A general solution is often:
• Not much harder to write than a special-purpose solution;
• More likely to be re-used; and
• Perhaps a little less efficient.
• Generality needs support from the programming language.
• Current languages do not support generality well; new OO lan
guages may be better (abstract classes, frameworks,. . .).
• Generalization is related to abstraction.
5
 Software Engineering Principles....(Continued)

f) Incrementality
• It is easier to make small changes to a working system than t
o rebuild the system.
• Why? Because if the modified system does not work, the erro
rs must have been introduced by the small changes.
g) Rigor and Formality
• Software engineering is a creative design activity, BUT
• It must be practiced systematically
• Rigor is a necessary complement to creativity that increases
our confidence in our developments
• Formality is rigor at the highest degree
– Software process driven and evaluated by mathematical la
ws
• Rigor: Careful and precise reasoning.

6
 Software Engineering Principles....(Continued)

• Formal: Reasoning based on a mechanical set of rules (“form

al system”).
• Use rigor as much as possible. Use formality when suitable
tools are available (compilers, parser generators, proof check
ers,...).
Definitions for Software Engineering
• Product — What we are trying to build.
• Process — The methods we use to build the product.
• Method — A guideline that describes an activity. Methods are
general, abstract, widely applicable. Example: top-down
design.
• Technique —A precise rule that defines an activity.
Techniques are precise, particular, and limited. Example: loop
termination proof.
• Tool — A mechanical/automated aid to assist in the
application of a methodology. Examples: editor, compiler, . . .
• Methodology — a collection of techniques and tools. 7
 Introduction....(Continued)

Software Engineering
• Is the use of engineering principles in order to develop good
software.
Good software is:
• Correct
– The software performs according to the SRD (Software
Requirements Document).
– The SRD may be too vague (although it should not be) —
in this case, conformance to a specification is needed.
• Reliable
– This is a weaker requirement than “correct”. E-mail is
reliable — messages usually arrive — but probably
incorrect.
• Robust
– The software behaves well when exercised outside the
requirements.
– For example, software designed for 10 users should not
fall apart with 11 users.
8
 Introduction....(Continued)

• Performance
– The software should have good space/time utilization, fast
response times.
– And the worst response time should not be too different fr
om the average response time.
• Friendly
– The software should be easy to use, should not irritate th
e user, and should be consistent.
– The screen always mirrors the state.
– One key — one effect. Example: F1 for help.
• Verifiable
– It should be possible to prove (verify) correctness of
the software.
– A common term that is not easily defined; it is easier to ver
ify a compiler than a word-processor.
• Flexibility
– Ability to accommodate new requirements (new
situations).

9
 Introduction....(Continued)

• Maintainable
– Easy to correct or upgrade.
– Code traceable to design; design traceable to
requirements.
– Clear simple code.
– Good documentation.
– Simple interfaces between modules.
• Reusable
– We need abstract modules that can be used in many
situations.
– Sometimes, we can produce a sequence of products,
each using code from the previous one.
– Example: Accounting systems.
– Object-Oriented techniques aid reuse.

10
 Introduction....(Continued)

• Portable
– The software should be easy to move to different
platforms.
– This implies few Operating System and hardware
dependencies.
– Recent developments in platform standards (PCs,
UNIX, . . .) have aided portability.
– Portability and efficiency are incompatible.
– Highly portable systems consist of many layers, each
layer hiding local details.
– Recent achievements in portability depend on fast
processors and large memories.
• Interoperable
– The software should be able to cooperate with other
software (word-processors, spread-sheets, graphics
packages, . . .).
11
 Introduction....(Continued)

• Visible
– All steps must be documented.

A program

• A set of instruction which is written in order

to solve a problem.

 A solution to a problem actually consists of

two things:
 A way to organize the data
 Sequence of steps to solve the problem

12
 Introduction....(continued)

• The way data are organized in a computers

memory is said to be Data Structure.

• The sequence of computational steps to

solve a problem is said to be an Algorithm.

• Therefore, a program is Data structures

plus Algorithm.
13
 Introduction....(continued)

• Data structures are used to model the world or

part of the world. How?
1. The value held by a data structure represents
some specific characteristic of the world.
2. The characteristic being modeled restricts the
possible values held by a data structure and
the operations to be performed on the data
structure.

14
 Introduction....(continued)

• The first step to solve the problem is obtaining

ones own abstract view, or model, of the
problem.

• This process of modeling is called

abstraction.

15
 Introduction....(continued)

• The model defines an abstract view to the

problem.

• The model should only focus on problem

related stuff
16
 Abstraction
• is a process of classifying characteristics as
relevant and irrelevant for the particular purpose at
hand and ignoring the irrelevant ones.

Example: model students of BDU.

• Relevant:
Char Name[15];
Char ID[11];
Char Dept[20];
int Age, year;
• Non relevant
float hieght, weight;
17
• Using the model, a programmer tries to
define the properties of the problem.

• These properties include

 The data which are affected and
 The operations that are involved in the
problem

• An entity with the properties just described

is called an abstract data type (ADT).
18
 Abstract Data Types
• Consists of data to be stored and operations supported
on them.

• Is a specification that describes a data set and the

operation on that data.

• The ADT specifies:

 What data is stored.
 What operations can be done on the data.

• Does not specify how to store or how to implement the

operation.
• Is independent of any programming language

19
Example: ADT employees of an organization:

 This ADT stores employees with their

relevant attributes and discarding irrelevant
attributes.
Relevant:- Name, ID, Sex, Age, Salary, Dept, Address
Non Relevant :- weight, color, height

 This ADT supports hiring, firing, retiring, …

operations.
20
 Data Structure

• In Contrast a data structure is a language

construct that the programmer has defined in
order to implement an abstract data type.

• What is the purpose of data structures in programs?

– Data structures are used to model a problem.

21
 Data Structure
• Example:
struct Student_Record
{
char name[20];
char ID_NO[10];
char Department[10];
int age;
};
• Attributes of each variable:
– Name: Textual label.
– Address: Location in memory.
– Scope: Visibility in statements of a program.
– Type: Set of values that can be stored + set of operations that can
be performed.
– Size: The amount of storage required to represent the variable.
– Life time: The time interval during execution of a program while the
variable exists.
22
 Algorithm

• Is a concise specification of an operation for solving a

problem.

• is a well-defined computational procedure that takes

some value or a set of values as input and produces
some value or a set of values as output.
Inputs Algorithm Outputs

• An algorithm is a specification of a behavioral process.

It consists of a finite set of instructions that govern
behavior step-by-step.
• Is part of what constitutes a data structure
23
• Data structures model the static part of the world.
They are unchanging while the world is changing.

• In order to model the dynamic part of the world we

need to work with algorithms.

• Algorithms are the dynamic part of a program’s

world model.

24
• An algorithm transforms data structures from one
state to another state.
• What is the purpose of algorithms in programs?
– Take values as input. Example: cin>>age;
– Change the values held by data structures.
Example: age=age+1;
– Change the organization of the data structure:
Example:
• Sort students by name
– Produce outputs:
• Example: Display student’s information

25
• The quality of a data structure is related to its
ability to successfully model the characteristics
of the world (problem).

• Similarly, the quality of an algorithm is related

to its ability to successfully simulate the
changes in the world.

26
• However, the quality of data structure and algorithms
is determined by their ability to work together well.

• Generally speaking, correct data structures lead to

simple and efficient algorithms.

• And correct algorithms lead to accurate and efficient

data structures.

27
 Properties of Algorithms
Finiteness:
 Algorithm must complete after a finite
number of steps.
 Algorithm should have a finite number of
steps.
Finite  int i=0; Infinite while(true){
while(i>10){ cout<<“Hello”;
cout<< i; }
i++;
} 28
Definiteness (Absence of ambiguity):

 Each step must be clearly defined, having

one and only one interpretation.

 At each point in computation, one should be

able to tell exactly what happens next.

29
Sequential:

 Each step must have a uniquely defined

preceding and succeeding step.

 The first step (start step) and last step (halt

step) must be clearly noted.

30
Feasibility:
 It must be possible to perform each
instruction.
 Each instruction should have possibility to
be executed.
1) for(int i=0; i<0; i++){
cout<< i; // there is no possibility
} that this statement to
be executed.
2) if(5>7) {
cout<<“hello”; // not executed.
}
31
Correctness:
 It must compute correct answer for all
possible legal inputs.
 The output should be as expected and required and
correct.
Language Independence:
 It must not depend on any one programming
language.
Completeness:
 It must solve the problem completely.
32
Effectiveness:
 Doing the right thing. It should yield the correct
result all the time for all of the possible cases.

Efficiency:
 It must solve with the least amount of
computational resources such as time and
space.
 Producing an output as per the requirement
within the given resources (constraints).

33
Example: Write a program that takes a number
and displays the square of the number.
1) int x;
cin>>x;
cout<<x*x*x;

2) int x,y;
cin>>x;
y=x*x*x;
cout<<y;

34
Example: Write a program that takes two numbers
and displays the sum of the two.

Program a Program b Program c (the most efficient)

cin>>a; cin>>a; cin>>a;
cin>>b; cin>>b; cin>>b;
sum = a+b; a = a+b; cout<<a+b;
cout<<sum; cout<<a;

All are effective but with different efficiencies.

35
Input/output:
 There must be a specified number of input
values, and one or more result values.
 Zero or more inputs and one or more outputs.

Precision:
 The result should always be the same if the
algorithm is given identical input.

36
Simplicity:
 A good general rule is that each step should carry out one
logical step.
• What is simple to one processor may not be simple to
another.

Levels of abstraction:
 Used to organize the ideas expressed in algorithms.
• Used to hide the details of a given activity and refer to
just a name for those details.
• The simple (detailed) instructions are hidden inside
modules.
• Well-designed algorithms are organized in terms of
levels of abstraction. 37