Chapter 1

Introduction

Data Structure & Algorithms

1
 Basic Terminologies
 Data
 Data are simply collection of facts and figures OR
 Data are values or set of values
 Data Item
 A data item refers to a single unit of values
 Group Data Items
 Those data items that are divided into sub items
 Those that are not are called elementary data items
 For example Student’s
 ID, Age, Gender are elementary data items, whereas
 Name (First, Middle, Last), Address (Street, Area) are group
data items
Data Structure & Algorithms
2
 Basic Terminologies (Cont...)
 Entity and Attributes
 An entity is that which contains certain attributes or
properties, which may be assigned values
 Object in the real world
 Entities with similar attributes form an entity set
 For example:
example all the employees in an organization
 Each attribute of an entity set has a range of values
 The set of all possible values that could be assigned to the
particular attribute
 Information
 The term “information” is sometimes used for data with
given attributes OR
 In other words, meaningful or processed data
Data Structure & Algorithms
3
 Basic Terminologies (Cont...)
 Field
 Field is a single elementary unit of information representing an
attribute of an entity
 Record
 Record is a collection of field values of a given entity
 File
 File is a collection of records of the entities in a given entity set
 Data Type
 Data type is a way to classify various types of data such as
integer, string, etc.
 Which determines the values that can be used with the
corresponding type of data

Data Structure & Algorithms

4
 Basic Terminologies (Cont...)
 Specify the type of operations that can be performed on the
corresponding type of data
 There are two data types
1. Built-in Data Type
 Those data types which has built-in support for a language
 For example:
example int, float, string, character, boolean, etc.
2. Derived Data Type
 Those data types which are implementation independent as
they can be implemented in one or the other way
 These data types are normally built by the combination of
primary or built-in data types and associated operations on
them
 For example:
example list, array, stack and queue
Data Structure & Algorithms
5
 Algorithm
 Algorithm is a step-by-step procedure,
procedure which defines a set of
instructions to be executed in a certain order to get the desired output
 Algorithms are generally created independent of underlying languages
 That is, a same algorithm can be implemented in more than one
programming language
 Following are some important categories of algorithms
 Search - Algorithm to search an item in a data structure
 Linear search and binary search
 Sort - Algorithm to sort items in a certain order
 Insert - Algorithm to insert item in a data structure
 Update - to update an existing item in a data structure
 Delete - to delete an existing item from a data structure

Data Structure & Algorithms

6
 Characteristics of an Algorithm
 An algorithm should have the following characteristics
 Unambiguous - Algorithm should be clear and unambiguous.
 Each of its steps (or phases), and their inputs/outputs should
be clear and must lead to only one meaning
 Input - An algorithm should have 0 or more well-defined inputs
 Output - An algorithm should have 1 or more well-defined
outputs, and should match the desired output
 Finiteness - Algorithms must terminate after a finite number of
steps
 Feasibility - Should be feasible with the available resources
 Independent - An algorithm should be independent of any
programming code

Data Structure & Algorithms

7
 Parts of Algorithm
 Algorithm can be divided into two parts
1. Algorithm’s Description
2. Algorithm’s Steps/Statements

 Algorithm’s Description
 Describe the main purpose of the algorithm
 Describe the symbols and abbreviations used
 Describe inputs/outputs, Etc...
 Algorithm’s Statements
 Presents the steps to be executed and perform the tasks
 Which would be implemented using any programming
language
Data Structure & Algorithms
8
 Example “To find largest element in array”
 Algorithm’s Description
 A non-empty array DATA with N numerical values is given.
This algorithm finds the location LOC of the largest value
MAX of DATA.
DATA The variable K is used as counter.

 Algorithm’s Statements
Step 1.
1 [Initialize]
Initialize Set K := 1, LOC := 1 and MAX := DATA[1]
Step 2.
2 [Increment counter]
counter Set K := K + 1
Step 3.
3 [Test counter]
counter if K > N, then:
write: LOC, MAX and Exit
Step 4.
4 [Compare & Update]
Update if MAX < DATA[K], then:
Set LOC := K and MAX := DATA[K]
Step 5.
5 [Repeat loop]
loop Go to Step 2
Data Structure & Algorithms
9
 Example “To find largest element in array”
 OR steps can be written as
 Algorithm’s Statements
Step 1.
1 Set K := 1, LOC := 1 and MAX := DATA[1]
Step 2.
2 Set K := K + 1
Step 3.
3 if K > N, then:
write: LOC, MAX and Exit
Step 4.
4 if MAX < DATA[K], then:
Set LOC := K and MAX := DATA[K]
Step 5.
5 Go to Step 2

 Different steps can be used by number and by nature

 Indentation is best to used
Data Structure & Algorithms
10
 Data Structure
 In computer science
 A data structure is a particular way of storing and organizing
data in a computer’s memory
 So that it can be used efficiently
 We have many data structures

 The choice of a particular data model depends on the two

considerations
1. It must be rich enough in structure to mirror the actual
relationships of the data in the real world
2. The structure should be simple enough that one can
effectively process the data whenever necessary

Data Structure & Algorithms

11
 Categories of Data Structure
 The data structure can be classified in to major types:
1. Linear Data Structure
2. Non-linear Data Structure

 Linear Data Structure

 A data structure is said to be linear if its elements form any
sequence
 There are basically two ways of representing such linear
structure in memory
1. One way is to have the linear relationships between the
elements represented by means of sequential memory
location,
 For example: Array
Data Structure & Algorithms
12
 Categories of Data Structure (Cont...)
2. The other way is to have the linear relationship between
the elements represented by means of pointers or links
 For example:
example linked lists
 Examples:
Examples Array, Queue, Stacks and Link Lists

 Non-linear Data Structure

 This structure is mainly used to represent data containing a
hierarchical relationship between elements
 Examples:
Examples Graphs, Trees and Table of contents

Data Structure & Algorithms

13
 Operations on DS
 The data in the data structures are processed by certain
operations
 The particular data structure chosen largely depends on the
frequency of the operation that needs to be performed on
the data structure
 DS Operations
 Traversing:
Traversing accessing each record/node exactly once so that
certain items in the record may be processed
 This accessing and processing is sometimes called
“visiting” the record
 Searching:
Searching Finding the location of the desired node with a
given key value, or finding the locations of all such nodes
which satisfy one or more conditions.
Data Structure & Algorithms
14
 Operations on DS (Cont...)
 Inserting:
Inserting Adding a new node/record to the structure
 Deleting:
Deleting Removing a node/record from the structure
 Sorting:
Sorting Sorting elements in data structure either in
ascending order or descending order
 Merging:
Merging Merging elements of two or more data structures
after satisfying specified condition

Data Structure & Algorithms

15
 Assignment
 Write 3 - 4 applications of the following data structure with
example
 Array
 Stack
 Queue
 Linked list
 Graph
 Tree

Data Structure & Algorithms

16
 End of Chapter
 Homework
 Study the following in details
 Algorithm Notations and Basic terms
 Pages 21-22
 Control structures
 Pages 23-24
 Sub-algorithm, variables and data types
 Pages 30-31
 Exercise
 Pages 33...

 You may have quiz next week

Data Structure & Algorithms

17