TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

Introduction to Data Structures and Algorithms

Basic terminology

 Data − Unprocessed facts/raw facts that can be values sets of values or otherwise.
 Data Item − Data item refers to single unit of values.
 Group Items − Data items that are divided into sub items are called as Group Items.
 Elementary Items − Data items that cannot be divided are called as Elementary Items.
 Attribute and Entity − an entity is that which contains certain attributes or properties,
which may be assigned values.
 Entity Set − Entities of similar attributes form an entity set.
 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 Structure is a way of collecting and organizing data in such a way that we can perform
operations on these data in an effective way. Data Structures is about rendering data elements in
terms of some relationship, for better organization and storage.

Example: Data that has two attributes; player's name "Michael" and age 25. Here " Michael " is
of String data type and 25 is of integer data type. We can organize this data as a record
like Player record, which will have both player's name and age in it. Now we can collect and
store player's records in a file or database as a data structure.

Object Oriented programming concepts, such as Class also does the same thing, it collects
different type of data under one single entity. The only difference being, data structures provides
for techniques to access and manipulate data efficiently.

Therefore, Data Structures are structures programmed to store ordered data, so that various
operations can be performed on it easily. It represents the knowledge of data to be organized in
memory. It should be designed and implemented in such a way that it reduces the complexity
and increases the efficiency.

1
 TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

Note: Using data structures, we can reduce the time complexity of various operations like
insert/search/update/delete, etc.

Characteristics of a Data Structure

 Correctness − Data structure implementation should implement its interface correctly.

 Time Complexity − Running time or the execution time of operations of data structure
must be as small as possible.

 Space Complexity − Memory usage of a data structure operation should be as little as

possible.

Basic types of Data Structures

As seen earlier, anything that can store data can be called a data structure, hence Integer, Float,
Boolean, Char etc, all are data structures. They are known as Primitive Data Structures.

Then we also have some complex Data Structures, which are used to store large and connected
data. Some example of Abstract Data Structure are:

 Linked List
 Tree
 Graph
 Stack, Queue etc.
All these data structures allow us to perform different operations on data. We select these data
structures based on which type of operation is required.

2
 TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

The data structures can also be classified on the basis of the following characteristics:

Characteristic Description

In Linear data structures, the data items are arranged in a linear sequence.
Linear
Example: Array

In Non-Linear data structures, the data items are not in sequence.

Non-Linear
Example: Tree, Graph

In homogeneous data structures, all the elements are of same type.

Homogeneous
Example: Array

Non- In Non-Homogeneous data structure, the elements may or may not be of

Homogeneous the same type. Example: Structures

Static data structures are those whose sizes and structures associated
Static
memory locations are fixed, at compile time. Example: Array

Dynamic structures are those which expands or shrinks depending upon

the program need and its execution. Also, their associated memory
Dynamic
locations changes. Example: Linked List created using pointers, trees,
queues, and stacks.

3
 TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

Features of Static Data Structures

1. The size of a static data structure is fixed and determined at compile-time.

2. Memory allocation for static data structures is done at compile-time and cannot be
changed during runtime.
3. Static data structures can be accessed randomly or sequentially, and access time is usually
faster than dynamic data structures.
4. Static data structures are best suited for applications that have a known maximum size
and a fixed number of elements.
5. Insertion and deletion operations can be slower in static data structures, especially if the
structure needs to be resized or elements need to be shifted.

Features of Dynamic Data Structures

1. The size of a dynamic data structure is not fixed and can change during runtime.
2. Memory allocation for dynamic data structures is done during runtime using techniques
such as heap memory allocation or pointer-based data structures.
3. Dynamic data structures can grow or shrink as needed and are best suited for applications
that have varying sizes or a changing number of elements.
4. Insertion and deletion operations are generally faster in dynamic data structures since
elements can be added or removed without the need to shift other elements.
5. Accessing elements in a dynamic data structure may be slower than in a static data
structure since memory may be spread out in different locations.

Data type

Data type, in programming, is a classification that specifies which type of value a variable has
and what type of mathematical, relational or logical operations can be applied to it without
causing an error. A string, for example, is a data type that is used to classify text and an integer
is a data type used to classify whole numbers.

When a program language requires a variable to only be used in ways that respect its data type,
that language is said to be strongly typed. This prevents errors, because while it is logical to ask
the computer to multiply a float by an integer (1.5 x 5), it is illogical to ask the computer to
multiply a float by a string (1.5 x Alice). When a programming language allows a variable of one
data type to be used as if it were a value of another data type, the language is said to be weakly
typed.

4
 TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

Abstraction

Abstraction is one of the key concepts of object-oriented programming (OOP) languages. Its
main goal is to handle complexity by hiding unnecessary details from the user. That enables the
user to implement more complex logic on top of the provided abstraction without understanding
or even thinking about all the hidden complexity.

That’s a very generic concept that’s not limited to object-oriented programming. You can find it

everywhere in the real world.

Abstract Data type (ADT)

Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of
values and a set of operations. The definition of ADT only mentions what operations are to be
performed but not how these operations will be implemented. It does not specify how data will
be organized in memory and what algorithms will be used for implementing the operations. It is
called “abstract” because it gives an implementation-independent view.

The process of providing only the essentials and hiding the details is known as abstraction.

Algorithm

An algorithm is a finite set of instructions or logic, written in order, to accomplish a certain

predefined task. Algorithm is not the complete code or program, it is just the core logic (solution)
of a problem, which can be expressed either as an informal high level description
as pseudocode, structured english or using a flowchart.

Algorithm writing is a process and is executed after the problem domain is well-defined. That is,
we should know the problem domain, for which we are designing a solution.

Note: Algorithms are generally created independent of underlying languages, i.e. an algorithm
can be implemented in more than one programming language.

5
 TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

Every Algorithm must satisfy the following properties:

1. Input- There should be 0 or more inputs supplied externally to the algorithm.

2. Output- There should be at least 1 output obtained.
3. Definiteness- Every step of the algorithm should be clear and well defined.
4. Finiteness- The algorithm should have finite number of steps.
5. Correctness- Every step of the algorithm must generate a correct output.
6. Feasibility − Should be feasible with the available resources.

Categories of algorithms

 Search − Algorithm to search an item in a data structure.

 Sort − Algorithm to sort items in a certain order.
 Insert − Algorithm to insert item in a data structure.
 Update − Algorithm to update an existing item in a data structure.
 Delete − Algorithm to delete an existing item from a data structure.

Example 1: Add two numbers entered by the user

Step 1: Start
Step 2: Declare variables num1, num2 and sum.
Step 3: Read values num1 and num2.
Step 4: Add num1 and num2 and assign the result to sum.
sum←num1+num2
Step 5: Display sum
Step 6: Stop

Example 2: Pseudocode, Flowchart, Language

6
 TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

Algorithm Analysis

Algorithm analysis deals with the execution or running time of various operations involved. The
running time of an operation can be defined as the number of computer instructions executed per
operation.

Efficiency of an algorithm can be analyzed at two different stages, before implementation and
after implementation. They are the following −

i. A Priori Analysis − this is a theoretical analysis of an algorithm. Efficiency of an

algorithm is measured by assuming that all other factors, for example, processor speed,
are constant and have no effect on the implementation.
ii. A Posterior Analysis − this is an empirical analysis of an algorithm. The selected
algorithm is implemented using programming language. This is then executed on target
computer machine. In this analysis, actual statistics like running time and space required,
are collected.

Algorithm Complexity

The performance of an algorithm is measured on the basis of following properties:

7
 TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

1. Time Complexity
2. Space Complexity
Time Complexity

Time complexity of an algorithm represents the amount of time required by the algorithm to run
to completion. Time requirements can be defined as a numerical function T(n), where T(n) can
be measured as the number of steps, provided each step consumes constant time.

For example, addition of two n-bit integers takes n steps. Consequently, the total computational
time is T(n) = c ∗ n, where c is the time taken for the addition of two bits. Here, we observe that
T(n) grows linearly as the input size increases.

Space Complexity

Space complexity of an algorithm represents the amount of memory space required by the
algorithm in its life cycle.

An algorithm generally requires space for following components:

 Instruction Space: It’s the space required to store the executable version of the program.
This space is fixed, but varies depending upon the number of lines of code in the
program.
 Data Space: It’s the space required to store all the constants and variables (including
temporary variables) value.
 Environment Space: It’s the space required to store the environment information needed
to resume the suspended function.

Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed part and S(I)
is the variable part of the algorithm, which depends on instance characteristic I. Following is a
simple example that tries to explain the concept −

Algorithm: SUM(A, B)

Step 1 - START

8
 TOPIC 1: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

Step 2 - C ← A + B + 10
Step 3 - Stop
Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3. Now, space
depends on data types of given variables and constant types and it will be multiplied accordingly.