Click to edit Master title style

Republic of the Philippines

UNIVERSITY OF EASTERN PHILIPPINES
Department of Information Technology
Catarman, Northern Samar, Philippines

Introduction to
Data Structure and
Algorithm
Mar Riel C. Abuke
I.T Instructor

1
What
Click toare
editData
MasterStructure?
title style
Data structure is a storage that is used to store and organize data. It is a way of
a r r a n g i n g d a t a o n a c o m p u t e r s o t h a t i t c a n b e a c c e s s e d a n d u p d a t e d e f f i c i e n t l y.

Depending on your requirement and project, it is important to choose the right data
structure for your project. For example, if you want to store data sequentially in the
m e m o r y, t h e n y o u c a n g o f o r t h e A r r a y d a t a s t r u c t u r e .

Note: Data structure and data types are slightly different. Data structure is the
collection of data types arranged in a specific order.

2 2
Click to edit
Two Main Master
Types titleStructure
of Data style

Primitive Data Structure and Non-Primitive

Data Structure
Primitive Data Structure – These are
predefined data, which are supported by the
programming language , Built-in Data Structure
 String = “this is string”
 Integer = 10
 Float = 34.1
3 3
Click to edit
Two Main Master
Types titleStructure
of Data style

Non-Primitive Data Structure

 These are data structures that are not defined
by the programming language.
 These are created by the programmer
 User defined data structure
Two Types
 Linear List
 Non-Linear List
4 4
Click to edit
Two Main Master
Types titleStructure
of Data style

Linear List – The data items are arranged in a

linear sequence either Vertically or
Horizontally.
Kinds of Linear List
 Array
 Stack
 Queue
 Linked List
5 5
Click to edit
Popular Master
Linear Data title style
Structures
1. Array Data Structure
In an array, elements in memory are arranged in continuous memory.
All the elements of an array are of the same type. And, the type of
elements that can be stored in the form of arrays is determined by the
programming language.

An array with each element represented by an index

6 6
Click to edit
Popular Master
Linear Data title style
Structures
2. Stack Data Structure
In stack data structure, elements are stored in the LIFO principle. That
is, the last element stored in a stack will be removed first.
It works just like a pile of plates where the last plate kept on the pile will
be removed first.
In a stack, operations can be perform only from one end (top here).

7 7
Click to edit
Popular Master
Linear Data title style
Structures
3. Queue Data Structure
Unlike stack, the queue data structure works in the FIFO principle where
first element stored in the queue will be removed first.
It works just like a queue of people in the ticket counter where first
person on the queue will get the ticket first.
In a queue, addition and removal are performed from separate ends.

8 8
Click to edit
Popular Master
Linear Data title style
Structures
4. Linked List Data Structure
In linked list data structure, data elements are connected through a
series of nodes. And, each node contains the data items and address to
the next node.

9 9
Click to edit
Two Main Master
Types titleStructure
of Data style

Non-Linear List – The data items are not in

sequence.
Kinds of Non-Linear List
 Tree
 Graph

10
10
Click to editData
Non Linear Master title style
Structures
1. Graph Data Structure
In graph data structure, each node is called vertex and each vertex is
connected to other vertices through edges.
Popular Graph Based Data Structures:
 Spanning Tree and Minimum Spanning Tree
 Strongly Connected Components
 Adjacency Matrix
 Adjacency List

11
11
Click to editData
Non Linear Master title style
Structures
2. Trees Data Structure
Similar to a graph, a tree is also a collection of vertices and edges.
However, in tree data structure, there can only be one edge between
two vertices.
Popular Tree based Data Structure
 Binary Tree
 Binary Search Tree
 AVL Tree
 B-Tree
 B+ Tree
 Red-Black Tree 12
12
 Click to
Linear Vsedit Master Data
Non-linear title style
Structures

Now that we know about linear and non-linear data structures, let's
see the major differences between them.

Linear Data Structures Non Linear Data Structures

 The data items are arranged in  The data items are arranged in
sequential order, one after the non-sequential order (hierarchical
other. manner).
 All the items are present on the  The data items are present at
single layer. different layers.
 It can be traversed on a single  It requires multiple runs. That is, if
run. That is, if we start from the we start from the first element it
first element, we can traverse all might not be possible to traverse
the elements sequentially in a all the elements in a single pass.
13
13
 Click to
Linear Vsedit Master Data
Non-linear title style
Structures

Now that we know about linear and non-linear data structures, let's
see the major differences between them.

Linear Data Structures Non Linear Data Structures

 The memory utilization is not  Different structures utilize
efficient. memory in different efficient ways
 The time complexity increase with depending on the need.
the data size.  Time complexity remains the
 Example: Arrays, Stack, Queue same.
 Example: Tree, Graph, Map

14
14
Click is
What toan
edit Master title style
Algorithm?

In computer programming terms, an algorithm is a set of

well-defined instructions to solve a particular problem. It
takes a set of input(s) and produces the desired output. For
example

An algorithm to add two numbers:

1. Take two number inputs
2. Add numbers using the + operator
3. Display the result
15
15
 Click to edit Master
Characteristics of an title style
Algorithm?

Input – Zero (0) to more

Output – At least one (1)
Definiteness – Instructions must be clear and
realistic
Finiteness – Must terminate and must have a
stopping point
Effectiveness – Instructions must be efficient
and useful 16
16
Click to edit
Qualities of aMaster title style
Good Algorithm

 Input and output should be defined precisely.

 Each step in the algorithm should be clear and
unambiguous.
 Algorithms should be most effective among many
different ways to solve a problem.
 An algorithm shouldn't include computer code. Instead,
the algorithm should be written in such a way that it can
be used in different programming languages.

17
17
Click to edit
Algorithm Master title style
Examples:

Algorithm 1: Add two numbers entered by the user

18
18
Click to edit
Algorithm Master title style
Examples:

Algorithm 2: Find the largest number among three numbers

19
19
Click to edit
Algorithm Master title style
Examples:

Algorithm 5: Check whether a number is prime or not

20
20
 Click to edit Master title style
Difference between Algorithm, Pseudocode and
Program
Algorithm : Systematic logical approach which is a
well-defined, step-by-step procedure that allows a
computer to solve a problem.
Pseudocode : It is a simpler version of a
programming code in plain English which uses short
phrases to write code for a program before it is
implemented in a specific programming language.
Program : It is exact code written for problem following
all the rules of the programming language.
21
21
 Click to edit Master title style
Difference between Algorithm, Pseudocode and
Program
Algorithm:
An algorithm is used to provide a solution to a particular problem
in form of well-defined steps. Whenever you use a computer to
solve a particular problem, the steps which lead to the solution
should be properly communicated to the computer. While
executing an algorithm on a computer, several operations such
as additions and subtractions are combined to perform more
complex mathematical operations. Algorithms can be expressed
using natural language, flowcharts, etc.
22
22
Difference between
Click to edit MasterAlgorithm,
title style Pseudocode and
Program
Algorithm:
Let’s take a look at an example for a better understanding. As a
programmer, we are all aware of the Linear Search program. (Linear
Search)
Algorithm of linear search :

Here, we can see how the steps of a linear search program are explained
in a simple, English language.
23
23
Difference between
Click to edit MasterAlgorithm,
title style Pseudocode and
Program
Pseudocode:
It is one of the methods which can be used to represent an algorithm for a
program. It does not have a specific syntax like any of the programming
languages and thus cannot be executed on a computer. There are several
formats which are used to write pseudo-codes and most of them take down
the structures from languages such as C, Lisp, FORTRAN, etc.

Many time algorithms are presented using pseudocode since they can be
read and understood by programmers who are familiar with different
programming languages. Pseudocode allows you to include several control
structures such as While, If-then-else, Repeat-until, for and case, which is
present in many high-level languages.
Note: Pseudocode is not an actual programming language. 24
24
Difference between
Click to edit MasterAlgorithm,
title style Pseudocode and
Program
Pseudocode:
Pseudocode for Linear Search :

In here, we haven’t used any specific programming language but wrote the steps of a
linear search in a simpler form which can be further modified into a proper program. 25
25
Difference between
Click to edit MasterAlgorithm,
title style Pseudocode and
Program
Program:
A program is a set of instructions for the computer
to follow. The machine can’t read a program
directly, because it only understands machine
code. But you can write stuff in a computer
language, and then a compiler or interpreter can
make it understandable to the computer.

26
26
Difference between
Click to edit MasterAlgorithm,
title style Pseudocode and
Program
Program:
Program for Linear Search :

27
27
Data
ClickStructure & Algorithm
to edit Master in PHP
title style
Implementation
Informally, an algorithm is nothing but a mention of steps to solve a problem. They
are essentially a solution.
For example, an algorithm to solve the problem of factorials might look something
like this:

Here, the algorithm is written in English. If it was written in a programming

language, we would call it to code instead. Here is a code for finding the factorial of
a number in PHP. 28
28
Data
ClickStructure & Algorithm
to edit Master in PHP
title style
Implementation
Programming is all about data structures and algorithms. Data
structures are used to hold data while algorithms are used to
solve the problem using that data.

Data structures and algorithms (DSA) goes through solutions to

standard problems in detail and gives you an insight into how
efficient it is to use each one of them. It also teaches you the
science of evaluating the efficiency of an algorithm. This enables
you to choose the best of various choices.

29
29
Use of Data Structures and Algorithms to Make
Click to edit Master title style
Your Code Scalable
Time is precious.
Suppose, Alice and Bob are trying to solve a simple problem of finding
the sum of the first 1011 natural numbers. While Bob was writing the
algorithm, Alice implemented it proving that it is as simple as criticizing
Donald Trump.

Code by Bob Code by Alice

30
30
Use of Data Structures and Algorithms to Make
Click to edit Master title style
Your Code Scalable
Alice and Bob are feeling euphoric of themselves that they could build
something of their own in almost no time. Let's sneak into their
workspace and listen to their conversation.

Alice: Let's run this code and find out the sum.
Bob: I ran this code a few minutes back but it's still not showing the output. What's
wrong with it?

Oops, something went wrong! A computer is the most deterministic machine.

Going back and trying to run it again won't help. So let's analyze what's
wrong with this simple code.
Two of the most valuable resources for a computer program are time and
memory.
31
31
Use of Data Structures and Algorithms to Make
Click to edit Master title style
Your Code Scalable
The time taken by the computer to run code is:

The number of instructions depends on the code you used, and the
time taken to execute each code depends on your machine and
compiler.

32
32
Click to edit Master title style

End of
Lesson

33