King Khalid University

Applied College
Applied Information Systems Dept.

1333 CIS-4

Algorithms and
Data Structures
Prepared by:

Maha al Otiabi
Level 3

1
‫دبلوم أنظمة اإلنترنت الذكية – المستوى األول‬
 Algorithms and Data Structures

1333 CIS-4

Algorithms and Data Structures

Course Description

This course enhances the programming skills of the students. Data Structures
(Array, Stacks, queues, strings, graph and trees) are described as abstract data types
with their methods by training extensive examples and applications. Designing and
analyzing different searching and sorting algorithms in terms of time and space,
which must be taken into consideration in any program. Brief introduction to binary
trees and graphs is also covered.

Course Objectives

Our focus in this course is to:

• Familiarize with the concepts and fundamentals of basics Data structures and
algorithms.
• Describe generic principles for data representation and manipulation with
a view for efficiency, maintainability, and code-reuse.
• Demonstrate analytical comprehension of concepts such as abstract data types
(Arrays, Vectors and Linked lists), algorithms (Stacks, Queues, Searching and
sorting techniques), and Complexity Analysis and Asymptotic notations.
• Categorize complexities of algorithms and data structures. Select appropriate
methods for organizing data files and implement file-based data structures.
• Design, write and analysis the performance of programs that handle
structured data and perform more complex tasks and software projects.
• Recent research on Algorithms and Data Structures will be incorporated

2
 Algorithms and Data Structures

Contents
Course Description ..................................................................................................... 2
Course Objectives ........................................................................................................ 2
Contents .......................................................................................................................... 3
Chapter 1 ......................................................................................................................... 6
Algorithms & ....................................................................................................................... 6
Complexity Analysis ........................................................................................................... 6
Properties of an Algorithm? .......................................................................................................................8
Examples of Algorithm .................................................................................................................................8
Algorithms Categories ............................................................................................................................... 10
Algorithm Complexity................................................................................................................................ 10
Asymptotic Notations: ............................................................................................................................... 10
Big Oh Notation, Ο: ................................................................................................................................ 11
OMEGA NOTATION, Ω: .................................................................................................................... 11
Theta Notation, Θ: ................................................................................................................................... 12
Time Complexity: ........................................................................................................................................ 12
COMMON ASYMPTOTIC NOTATIONS: ..................................................................................... 14
ORDER OF GROWTH : ....................................................................................................................... 15

Chapter 2 ...................................................................................................................... 16
Arrays-vectors .................................................................................................................. 16
Introduction ................................................................................................................................................. 17
Data Structure............................................................................................................................................. 17
Multidimensional Arrays ......................................................................................................................... 21

Chapter 3 ...................................................................................................................... 23
Introduction ................................................................................................................................................. 24
Introduction ................................................................................................................................................. 24
Objects in Java ............................................................................................................................................. 25
Classes in Java ............................................................................................................................................. 25
Constructors ................................................................................................................................................. 27
Imports ........................................................................................................................................................... 28

3
 Algorithms and Data Structures

Creating an Object...................................................................................................................................... 29

Chapter 4 ...................................................................................................................... 30
Linked Lists ....................................................................................................................... 30
Introduction ................................................................................................................................................. 31
Types of Linked List .................................................................................................................................. 32
Singly Linked List ...................................................................................................................................... 32
Doubly Linked List .................................................................................................................................... 40
Circular Linked List .................................................................................................................................. 46

Chapter 5 ...................................................................................................................... 53
Stacks ............................................................................................................................... 53
Introduction ................................................................................................................................................. 54
Basic Operations performed on Stack................................................................................................. 55

Chapter 6 ...................................................................................................................... 60
Queue ................................................................................................................................ 60
Introduction ................................................................................................................................................. 61
Queues Definition....................................................................................................................................... 61

Chapter 7 ...................................................................................................................... 67
Introduction to.................................................................................................................. 67
Tree and Graph ................................................................................................................. 67
Tree.................................................................................................................................................................. 68
Trees Basic terminology : .................................................................................................................... 68
Binary Tree ................................................................................................................................................... 71
Advantages of trees ................................................................................................................................. 76
Introduction to Graphs ............................................................................................................................ 77
Graph Terminologies ................................................................................................................................ 80
Types of Graphs........................................................................................................................................... 80
Graph Traversal Algorithms ................................................................................................................... 85
Depth First Search (DFS) .................................................................................................................. 86
Breadth First Search (BFS) .............................................................................................................. 86

Chapter 8 ...................................................................................................................... 88

4
 Algorithms and Data Structures

Searching ......................................................................................................................... 88
Introduction ................................................................................................................................................. 89
Linear Search .............................................................................................................................................. 90
Binary Search .............................................................................................................................................. 91

5
 CH01 –algorithms & complexity analysis

Chapter 1

Algorithms &
Complexity Analysis
1
By the end of teaching this chapter, the student will be able to
Understand:
➢ What is Algorithm ?
➢ Properties of an Algorithm
➢ Examples of Algorithm
➢ S asymptotic notations O, Ω, θ
➢ Time Complexity
➢ Running time

6
 CH01 –algorithms & complexity analysis

Chapter 1

ALGORITHMS &
Complexity Analysis

Introduction To Algorithms

Algorithm is a step-by-step 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, i.e. an algorithm can be implemented in more than one
programming language. An algorithm is written in simple English and is not a formal
document. An Algorithm is independent of programming language.

An algorithm is an effective method expressed as a finite list of well-defined

instructions for calculating a function. Starting from an initial state and initial input
(perhaps empty), the instructions describe a computation that, when executed, proceeds
through a finite number of well-defined successive states, eventually producing
"output" and terminating at a final ending state.

The transition from one state to the next is not necessarily deterministic; some algorithms,
known as randomized algorithms, incorporate random input. Investing additional money
or time to buy and install a new computer holds the potential for speeding up a program
by perhaps a factor of only 10 or 100. Careful algorithm design is an extremely effective
part of the process of solving a huge problem, whatever the applications area.

7
 CH01 –algorithms & complexity analysis

Algorithm is a step-by-step procedure, which defines a set of

instructions to be executed in a certain order to get the desired output.

Properties of an Algorithm?

 Finiteness: An algorithm should have finite number of steps.

 Definiteness: Any step of an algorithm should be definite and unambiguous.
 Effectiveness: An algorithm should be effective in solving the problem that it is
meant for.
 Input: It should have zero or more inputs.
 Output: It should have 1 or more outputs.

Examples of Algorithm

Algorithm to add two numbers:

Start:

Input: Two Numbers

1. Add the two numbers.

2. Print Add.

End

Algorithm to find average of two numbers:

Start:

Input: Two Numbers

1. Add two numbers.

2. Divide the Result by 2.
3. Print the Result.

End

8
 CH01 –algorithms & complexity analysis

Algorithm to find Cube of a number:

Start:

Input: One Number

1. Number X Number X Number

2. Print the Result.

End

Algorithm to find even or odd number:

Start:

Input: One Number

1. If(number /2==0)
Then
1.1. Print : Even Number.

Else

1.2. Print: Odd Number.

End if

End

Algorithm for finding Largest of two Numbers:

Start:

Input: Two Numbers

1. If(First number is greater than second number)

Then
1.1. Print: Largest is first number.

Else

1.2. Print: Largest is second number.

End if

End

9
 CH01 –algorithms & complexity analysis

Algorithms Categories

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

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

Algorithm Complexity

Suppose X is an algorithm and n is the size of input data, the time and space used by the
algorithm X are the two main factors, which decide the efficiency of X.

– Time Factor −Time is measured by counting the number of key

operations such as comparisons in the sorting algorithm.

– Space Factor − Space is measured by counting the maximum memory

space required by the algorithm. The complexity of an algorithm f(n)
gives the running time and/or the storage space required by the algorithm
in terms of n as the size of input data.

Asymptotic Notations:

 Asymptotic analysis of an algorithm refers to defining the mathematical

boundaries/framing of its run-time performance. Using asymptotic analysis, we can
very well conclude the best case, average case, and worst-case scenario of an
algorithm.
 Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is
concluded to work in a constant time = O(1)

10
 CH01 –algorithms & complexity analysis

What do these symbols mean O,Ω,ø?

Usually, the time required by an algorithm falls under three types −

• Best Case − Minimum time required for program execution.
• Average Case − Average time required for program execution.
• Worst Case − Maximum time required for program execution.

Big Oh Notation, Ο:
The notation Ο(n) is the formal way to express the upper bound of an
algorithm's running time. It measures the worst case time complexity or
the longest amount of time an algorithm can possibly take to complete.
Note: This notation is the most important one that we will try to avoid our
algorithm from taking a big oh case which represent the worst case time
for an algorithm to execute.

Figure 1: O(N)

OMEGA NOTATION, Ω:

The notation Ω(n) is the formal way to express the lower bound of an
algorithm's running time. It measures the best case time complexity or the
best amount of time an algorithm can possibly take to complete.

Figure 2: Ω(n)

11
 CH01 –algorithms & complexity analysis

Theta Notation, Θ:

The notation θ(n) is the formal way to express both the lower bound and
the upper bound of an algorithm's running time. It is represented as
follows

Figure 3: θ(n)

Time Complexity:

The time complexity is the computational complexity that describes the amount of time
it takes to run an algorithm. Time complexity is commonly estimated by counting the
number of elementary operations performed by the algorithm, supposing that each
elementary operation takes a fixed amount of time to perform. Thus, the amount of time
taken and the number of elementary operations performed by the algorithm are taken to
differ by at most a constant factor.

Time Complexity Cases

➢ Best case – The term best-case performance is used in computer science to

describe an algorithm's behavior under optimal conditions. For example, the best
case for a simple linear search on a list occurs when the desired element is the
first element of the list.
➢ Average case – It is the amount of some computational resource (typically time)
used by the algorithm, averaged over all possible inputs. It is frequently
contrasted with worst-case complexity which considers the maximal complexity
of the algorithm over all possible inputs.

12
 CH01 –algorithms & complexity analysis

➢ Worst case – The worst-case execution time of a computational task is the

maximum length of time the task could take to execute on a specific hardware
platform.

Running Time

The running time of an algorithm for a specific input depends on the number of
operations executed. The greater the number of operations, the longer the running time
of an algorithm. We usually want to know how many operations an algorithm will
execute in proportion to the size of its input, which we will call.

How To Calculate Running Time?

1) The running time of an algorithm for a specific input depends on the number of
operations executed (we mean here)
2) The greater the number of operations, the longer the running time of an
algorithm.
3) We usually want to know how many operations an algorithm will execute in
proportion to the size of its input, which we will call.

How much time does it take to run this function?

To write an efficient algorithm to solve a particular programming problem in which

we reduce time execution and consume much less of memory size whatever the
amount of data.

13
 CH01 –algorithms & complexity analysis

Figure 4: Big O Notation and Time/Space Complexity

COMMON ASYMPTOTIC NOTATIONS:

We compute the big-Θ of an algorithm by counting the number of iterations the

algorithm always takes with an input of n. For instance, the loop in the pseudo-code
below will always iterate N times for a list size of N. The runtime can be described as
Θ(N).
for each item in list:
print item

The common algorithmic runtimes from fastest to slowest are:

Constant Ο(1)
logarithmic Ο(log n)
Linear Ο(n)
linearithmic Ο(n log n)
Quadratic Ο(n 2)
Cubic Ο(n 3)
polynomial n Ο(1)
exponential 2 Ο(n)

14
 CH01 –algorithms & complexity analysis

ORDER OF GROWTH :

n Linear function – Example: Search unsorted array

log n Logarithmic function – Example: Binary search

n log n Linearthmic function – Example: Mergesort and quicksort

n2 quadratic – Example: Insertion sort

cubic
n3

15
 CH02 – Arrays-vectors

Chapter 2

Data Structure
Arrays-vectors
2
By the end of teaching this chapter, the student will be able to:
➢ Study and understand Data Structure.
➢ Distinguish the different between Arrays and vectors.
➢ Arrays - Static
➢ Vectors - Dynamic

16
 CH02 – Arrays-vectors

Chapter 2

Data Structure
Arrays-vectors

Introduction

A data structure is a group of data elements that provides the easiest way to store and
perform different actions on the data of the computer. A data structure is a particular
way of organizing data in a computer so that it can be used effectively.
The idea is to reduce the space and time complexities of different tasks.
The choice of a good data structure makes it possible to perform a variety of critical
operations effectively. An efficient data structure also uses minimum memory space and
execution time to process the structure.

Data Structure
➢ A data structure is the logical and mathematical organization of Data.
➢ They are used to organize data and provide various operations upon data.
➢ Examples of Data Structures are:
o Arrays, Stacks, Queues, Trees etc.

17
 CH02 – Arrays-vectors

Array:

Array is a data structure that represents a collection of the same types of data.

➢ An array is a finite collection of similar elements.

➢ Elements are stored in adjacent memory locations.
➢ An array is referenced by using an index that varies from 0-(n-1)
o [Where n is the number of elements in an array].
➢ The lowest index of array is known as Lower Bound.
➢ The highest index of an array is known as Upper Bound.
➢ The number of elements in an array is known as Range.
➢ Arrays are static, it means when you write your code you actually tells the
compiler that how many element you want to store in your array . That means
the array size is fixed in compile time.

 Declaration of an array:
Arrays must be declared before they can be used in the program.

Array declaration is as:

Datatype [ ] name = new Datatype [length of an array];

Example:
int [ ] a =new int [10];

Number of elements in an array (Range).

Name of the array.

Data type.

• Here the range of array starts from 0-9 ,where 0 is the lower bound and 9 is the
upper bound.

18
 CH02 – Arrays-vectors

 Initializing an Array :
Initial values are assigned to each element of an array by enclosing the values in braces {
}.

For example: int a[5]={11,3,5,2,9};

• datatype[] arrayRefVar;
Example: double[] myList;
• datatype arrayRefVar[]; // This style is allowed, but not preferred
Example: double myList[];

 Creating Arrays
arrayRefVar = new datatype[arraySize];
Example: myList = new double[10];
myList[0] references the first element in the array.

myList[9] references the last element in the array.

Declaring and creating in one step:

datatype[] arrayRefVar = new datatype[arraySize];

Example : double[] myList = new double[10];

• datatype arrayRefVar[] = new datatype[arraySize];

Example : double myList[] = new double[10];

IT CAN BE

• int[] myList = new int[10];

• float[] myList = new float[…];

• double[] myList = new double[…];

• char[] myList = new char[…];

• String[] myList = new String[…];

• boolean[] myList = new boolean[…];

19
 CH02 – Arrays-vectors

THE LENGTH OF AN ARRAY

• Once an array is created, its size is fixed. It cannot be changed. You can find its
size using

In java length is used to define the array length : arrayRefVar.length

For example, myList.length

DEFAULT VALUES:

When an array is created, its elements are assigned the default value of

1. 0 for the numeric primitive data types

2. '\u0000' for char types
3. false for boolean types.

INDEXED VARIABLES

The array elements are accessed through the index. The array indices are 0-based, i.e., it
starts from 0 to arrayRefVar.length-1. Each element in the array is represented using the
following syntax, known as an indexed variable: arrayRefVar[index];

USING INDEXED VARIABLES

After an array is created, an indexed variable can be used in the same way as a regular
variable.

 Accessing Value of an Array

**The index of an array always starts with 0.

A[0] A[1] A[2] A[3] A[4]

11 3 5 2 9

To access 5 we will write as:

A [2] = 5.

20
 CH02 – Arrays-vectors

Arrays are static, it means when you write your code you actually tells the compiler that
how many element you want to store in your array. That means the array size is fixed in
compile time.

Multidimensional Arrays
Multidimensional arrays can be defined as "arrays of arrays".

• The most commonly used multidimensional array is Two-Dimensional Array.

• Two-Dimensional Array consists of rows and columns.

• Declaration of Two-Dimensional Array

int [][] class =new [3][4];

Number of columns
Number of rows
Name of Array
Data type

21
 CH02 – Arrays-vectors

Vectors – Dynamic

• Vector implements a dynamic array. It is similar to ArrayList, but with two

differences:

– Vector is synchronized.

– Vector contains many legacy methods that are not part of the collections
framework.

• Vector proves to be very useful if you don't know the size of the array in advance
or you just need one that can change sizes over the lifetime of a program.

VECTORS METHODS

• Vectors have predefine methods or built-in functions that helps to create, remove,
add, edit, capacity, clear, copy, etc.

• We should import java utility class to load all tools of that class.

–import java.util.*;

EXAMPLE:

import java.util.*;

public class Test {

public static void main(String[] args) {

Vector v = new Vector(); System.out.println("Initial size: " + v.size());

System.out.println("Initial capacity: " + v.capacity()); v.add(1);

v.add(2);

v.add(3);

v.add(4);

System.out.println("The Size After: " + v.size());

} }

22
 CH03 – class & object

Chapter 3

Class & object

3
In this chapter, we will look into the concepts - Classes and
Objects.
➢ Class
o Local variables
o Instance variables
o Class variables •
➢ Constructors
➢ imports
➢ Object
o Declaration
o Instantiation
o Initialization

23
 CH03 – class & object

Chapter 3

Class & object

Introduction

This chapter is intended to give you a solid foundation in working with Boolean
Algebra. Boolean Algebra is also sometimes referred to as Boolean Logic or just
Logic. It is a method of representing expressions using only two values (True and
False typically) and was first proposed by George Boole in 1847.

Introduction

In this chapter, we will look into the concepts - Classes and Objects. Object −
Objects have states and behaviors. Example: A dog has states - color, name, breed
as well as behaviors – wagging the tail, barking, eating. An object is an instance of
a class. Class − A class can be defined as a template/blueprint that describes the
behavior/state that the object of its type support.

24
 CH03 – class & object

Objects in Java

Let us now look deep into what are objects. If we consider the real-world, we can
find many objects around us, cars, dogs, humans, etc. All these objects have a state
and a behavior. If we consider a dog, then its state is - name, breed, color, and the
behavior is - barking, wagging the tail, running. If you compare the software object
with a real-world object, they have very similar characteristics.
Software objects also have a state and a behavior. A software object's state is stored
in fields and behavior is shown via methods. So in software development, methods
operate on the internal state of an object and the object-to-object communication is
done via methods.

Classes in Java

A class is a blueprint from which individual objects are created. A class can
have any number of methods to access the value of various kinds of
methods. Example:
• barking( )

• hungry( )
• sleeping( )

 Local variables

Variables defined inside methods, constructors or blocks are called local

variables. The variable will be declared and initialized within the method and the
variable will be destroyed when the method has completed.

25
 CH03 – class & object

– Example:

 Instance variables
Instance variables are variables within a class but outside any method. These
variables are initialized when the class is instantiated. Instance variables can be
accessed from inside any method, constructor or blocks of that particular class.

Example:

26
 CH03 – class & object

 Class variables

Class variables are variables declared within a class, outside any method, with the
static keyword.
Example:

Constructors

In Java, a constructor is a block of codes similar to the method. It is called

when an instance of the class is created. At the time of calling constructor,
memory for the object is allocated in the memory. It is a special type of
method which is used to initialize the object. Every time an object is created
using the new() keyword, at least one constructor is called. It calls a default
constructor if there is no constructor available in the class. In such case, Java
compiler provides a default constructor by default. There are two types of
constructors in Java: no-arg constructor, and parameterized constructor.
Note: It is called constructor because it constructs the values at the time of
object creation. It is not necessary to write a constructor for a class. It is
because java compiler creates a default constructor if your class doesn't have
27
 CH03 – class & object

any. When discussing about classes, one of the most important sub topic
would be constructors.
Rules for creating Java constructor

1. Every class has a constructor. If we do not explicitly write a constructor for

a class, the Java compiler builds a default constructor for that class.
2. A class can have more than one constructor.
3. A constructor with no parameters is referred to as a default constructor.
4. Constructors must have the same name as the class itself.
5. Constructors do not have a return type—not even void.
6. Constructors are invoked using the new operator when an object is created.
7. Constructors play the role of initializing objects.

Example :

Imports

In Java if a fully qualified name, which includes the package and the class name is
given, then the compiler can easily locate the source code or classes. Import
statement is a way of giving the proper location for the compiler to find that
particular class.
For example, the line on next slide would ask the compiler to load all the classes
available in directory java_installation/java/io

28
 CH03 – class & object

Creating an Object

As mentioned previously, a class provides the blueprints for objects. So basically, an

object is created from a class. In Java, the new keyword is used to create new objects.
There are three steps when creating an object from a class −
• Declaration − A variable declaration with a variable name with an object type.
–ClassName objectReference;
• Instantiation − The 'new' keyword is used to create the object.
objectReference = new ClassName();
• Initialization − The 'new' keyword is followed by a call to a constructor. This call
initializes the new object.
ClassName objectReference = new ClassName();
Following is an example of creating an object −
public class Puppy {
public Puppy(String name) {
// This constructor has one parameter, name.
System.out.println("Passed Name is :" + name );
}

public static void main(String []args) {

// Following statement would create an object myPuppy
Puppy myPuppy = new Puppy( "tommy" );
}
}

If we compile and run the above program, then it will produce the following result −
Output : Passed Name is :tommy

29
 CH04 – linked list

Chapter 4

Linked Lists
4
By the end of teaching this chapter, the student will be able to
Introduce the basics:
➢ Linked List
➢ Single linked list
o Create a linked list
o Insert at the beginning
o Remove from the beginning
o Insert at the end
o Remove from the end
o Insert at anywhere
o remove from anywhere
➢ Doubly Linked List
➢ Circular Linked List

30
Prepared by:Maha al Otibi
 CH04 – linked list

Chapter 4

Linked Lists

Introduction

It is a data structure which consists group of nodes that forms a sequence. Linked List
can be defined as collection of objects called nodes that are randomly stored in the
memory. A node contains two fields i.e. data stored at that particular address and the
pointer which contains the address of the next node in the memory.

Uses:

It is a very common data structure that is used to create tree, graph and other abstract
data types. The list is not required to be contiguously present in the memory. The node
can reside any where in the memory and linked together to make a list. This achieves
optimized utilization of space. list size is limited to the memory size and doesn't need to
be declared in advance. Empty node can not be present in the linked list. We can store
values of primitive types or objects in the singly linked list.

Linked List can be defined as collection of objects called nodes that are
randomly stored in the memory. node in the memory.

31
Prepared by:Maha al Otibi
 CH04 – linked list

Types of Linked List

There are three basic types of Linked Lists:

1. Singly Linked List

2. Doubly Linked List
3. Circular Linked List

Singly Linked List

In Singly Linked List Each node in linked lists consists of two parts

• Data Part
• Pointer Point
o Pointer part stores address of next node

Node

Address of
Value
Next Node

• The Head pointer points to the first node and the last node is called
Tail Node.

Singly Linked List is a type of linked list in which each node

contains a pointer to the next element, thus forming a linear
list.

32
Prepared by:Maha al Otibi
 CH04 – linked list

Example of Singly Linked List:

Traversing the single Linked list

Traversing the linked list means visiting each and every node of the Single
linked list.
Steps for Traversing the Single Linked list:
1. Firstly move to first node
2. Fetch the data and perform any operations on it
3. After performing operations advance the pointer and continue again
from step 1 until all nodes are traversed

33
Prepared by:Maha al Otibi
 CH04 – linked list

Operation on a singly Linked list

o Adding a node at the a singular Linked List

1.Adding a node at the beginning of the list:

Step1: Make a head point to the newNode

Step2: Make a newNode point to the firstNode

34
Prepared by:Maha al Otibi
 CH04 – linked list

2.Adding a node at the middle of the list:

Step1: Make the prevNode point to the newNode

Step2: Make the newNode point to the nextNode

35
Prepared by:Maha al Otibi
 CH04 – linked list

3.Adding a node at the End of the list:

Step1: Make a lastNode point to the newNode

Step2: Make a newNode point to the Null

36
Prepared by:Maha al Otibi
 CH04 – linked list

1. Delete a node from the singular Linked list:

1.deleting a node at the beginning of the list:

Step1: Create a temporary node (temp) which will point to the firstNode

Step2: Make head point to the second node

Step3: Delete the firstNode which pointed by temp node.

37
Prepared by:Maha al Otibi
 CH04 – linked list

2.2 Deleting a node from the middle of the list

• Assume that the CurrentNode is the node to be deleted

Step1:Traverse the singly linked list till reach to the node pointed by temp

Step2: Make a PrevNode point to the nextNode

Step3: Delete the CurrentNode which pointed by temp node.

2.3 Deleting a node from the end of list (Tail)

Step1:Traverse the singly linked list till reach to the node pointed by temp
(lastNode).

Step2: make the PrevNode point to Null

38
Prepared by:Maha al Otibi
 CH04 – linked list

Step2: Delete the lastNode which pointed by temp node.

 Exercise

Perform the following Operations on the singular Linked List

given below.

1. Add the new node at the beginning of the list.

2. Add the new node at the middle of the list.
3. Add the new node at the end of the list.
4. Delete a First node from the list.
5. Delete a Second node from the list
6. Delete a Last node from the list

39
Prepared by:Maha al Otibi
 CH04 – linked list

Doubly Linked List

is a type of linked list in which each node contains pointers to the next and
previous node in the list.

doubly Linked List is a type of linked list in which each

node contains pointers to the next and previous node in the
list.

Example of Singly Linked List:

The differences between singly and doubly linked lists

• The doubly linked lists require more space per node as compared to
singly linked list.
• The doubly linked lists are often easier to manipulate than singly linked
list because they allow sequential access to the list in both directions.

Operations on Doubly Linked Lists

40
Prepared by:Maha al Otibi
 CH04 – linked list

o Adding a node at the a Doubly Linked List

1.Adding a node at the beginning of the list:

Steps:

1. Update the next pointer of the newNode to the firstNode

2. Make the prev pointer of the newNode point to head
3. Now update the prev pointer of the firstNode to point to newNode .

2.Adding a node at the middle of the list:

Steps:

41
Prepared by:Maha al Otibi
 CH04 – linked list

1. Make the next pointer of new node points to next node

2. Make the prev pointer of new node point to previous node.
3. Make the next pointer of the previous node points to new node.
4. Make the prev node of next node points to new node.

3.Adding a node at the End of the list:

Steps:

1. Make next pointer of new node to point to NULL .

2. Make the prev pointer of new node to point to node3.
3. Update next pointer of node3 to point to new Node.

2. Delete a node from the list:

1.deleting a node at the beginning of the list:

Steps :

1. Create a temporary node(temp) on the node1 (fist node).

42
Prepared by:Maha al Otibi
 CH04 – linked list

2. Change the prev pointer of the node2 to head.

3. Delete the node pointed by temporary node (node1)

2.2 Deleting a node from the middle of the list

Suppose that the node1 with the value 2 is to be deleted

1. Step1: Traverse the doubly linked list till reach to the node using temp (node2)

43
Prepared by:Maha al Otibi
 CH04 – linked list

2. Step2: Make the pointer next of the node1 to point to the node3 and Make the pointer prev of
the node3 to point to the node1.

3. Delete the node2 which pointed by temp.

2.3 Deleting a node from the end of list (Tail)

Step1: Traverse the doubly linked list till reach to the last node (node3)

Step2: Update the next pointer of node2 to point to NULL.

44
Prepared by:Maha al Otibi
 CH04 – linked list

Step3: delete the Last Node (node3).

Exercise

Perform the following Operations on the doubly Linked List

given below.

7. Add the new node at the beginning of the list.

8. Add the new node at the middle of the list.
9. Add the new node at the end of the list.
10.Delete a First node from the list.
11.Delete a Second node from the list
12.Delete a Last node from the list

45
Prepared by:Maha al Otibi
 CH04 – linked list

Circular Linked List

Circular Linked List is a variation of Linked list in which the first element
points to the last element and the last element points to the first element. Both
Circular Linked List and Doubly Linked List can be made into a circular
linked list.

Circular Linked List is a type of linked list used in data

structure where address of 1st node is stored in the link part
of last node.

Example of Circular Linked List:

Operations on Doubly Linked Lists:

o Adding a node at the a Doubly Linked List

1.Adding a node at the beginning of the list:

Steps:
46
Prepared by:Maha al Otibi
 CH04 – linked list

1. Make a new node point to the first node

2. Make a head point to new node

2.Adding a node at the middle of the list:

Assume that the new node is the one to be added between prevnode and next node

Steps:

1. Make a new node point to next node

2. Make a prevNode point to the new node

3.Adding a node at the End of the list:

47
Prepared by:Maha al Otibi
 CH04 – linked list

Steps:

1. Make a new node point to head

2. Make a last node point to the new node.

2. Delete a node from the list:

1.deleting a node at the beginning of the list:

1. Deletion a node from the beginning of the list

Steps:
1. Create a temporary node (temp) on the first node.
2. Make a head node point to the next node

48
Prepared by:Maha al Otibi
 CH04 – linked list

3. Delete the first node from the list

2. Deletion a node from the middle of the list

Steps:
1. Traverse the doubly linked list till reach to the node using temp (next node)
2. Make the first node point to the last node

3. Delete the node from the list

49
Prepared by:Maha al Otibi
 CH04 – linked list

3. Deletion a node from the last of the list

Steps:
1. Traverse the doubly linked list till reach to the last node.
2. Make a second node point to the head.

3. Delete the node from the list.

50
Prepared by:Maha al Otibi
 CH04 – linked list

Exercise:

Perform the following Operations on the circular Linked List given below.

a. Add the new node at the beginning of the list.

b. Add the new node at the middle of the list.
c. Add the new node at the end of the list.
d. Delete a First node from the list.
e. Delete a Second node from the list
f. Delete a Last node from the list

Advantages of Linked List:

1. Linked list is a Dynamic data structure
2. Insertion and Deletion operations are easier
3. Efficient memory utilization
4. Linked List can be used to implement other data structures (eg. Stacks, Queues)

Disadvantages of Linked list

51
Prepared by:Maha al Otibi
 CH04 – linked list

Differences between Arrays and Linked List:

1. Elements in array are in adjacent memory locations, where nodes in a list don't
have to be in adjacent locations.

2. Arrays offer random access to their elements; lists only offer sequential access
(i.e., you have to walk down the list to find an element).
3. Arrays are (usually) fixed in length - adding elements to or removing elements
from the array doesn't change the array's size. Lists can grow or shrink as
needed.
4. Linked lists can be circular, or doubly-linked (pointers forward and backward),
and new nodes can be inserted anywhere in the chain which is not the case in
Array.

52
Prepared by:Maha al Otibi
 CH05 – Stack

Chapter 5

Stacks
5
By the end of teaching this chapter, the student will be able to:
➢ The fundamental concepts in graph theory.
➢ Define the basic concepts of a Stack (FILO)
➢ Create a Stack
➢ Understand the basic operations are performed in the stack:
o push(item)
o pop( )
o peek( )
o isEmpty( )
o size( )
o search(item).

53
Prepared by:Maha al Otibi
 CH05 – Stack

Chapter 5

Stack

Introduction

Stack is a linear data structure which follows a particular order in which the
operations are performed. The order may be :

LIFO(Last In First Out)

FILO(First In Last Out)

Stack:
• It is a restricted linear data structure.
• Elements can only be inserted and deleted at one end.
• This end is known as Top of the Stack.
• The last index of the stack is known as Top of the stack.
• A stack can be implemented by means of Array or Linked List.
• Stack can either be a fixed size or it may have a sense of dynamic resizing.

54
Prepared by:Maha al Otibi
 CH05 – Stack

Basic Operations performed on Stack

➢ Push
➢ Pop
➢ peek( )
➢ isEmpty( )
➢ size( )

1. Push:
• Push refers to adding an element at the top of stack.
• Push operation is carried out in following two steps
a. First increment variable top so that now it refers to next memory
location.
b. Secondly Add element on to stack by accessing array

Stack Overflow:

55
Prepared by:Maha al Otibi
 CH05 – Stack

When the stack is full there is not enough room to add element at the Top of stack. This
condition is known as Stack Overflow.

The value of Top=n-1 when stack is full. Where N is the number of stack elements

Example of push operation:

Top

2. Pop:
• Allows removing an element from the top of the stack.
• Pop operation is carried out in following two steps
a. Delete the Top most element
b. Decrement Top pointer by 1.

Stack Underflow:

The value of Top is -1 when the stack is empty. This condition is known as Stack
Underflow.

Example of pop operation:

Pop 2 Pop 8 Pop 4 Pop 10

2
Top [3] [3] [3]
[3]
8 [2] Top8 [2] [2]
[2]
4 [1] 4 Top [1]
[1] 4 [1]
10 [0] 10 [0] 10
Top
10 [0] [0]
4 2 1
3
56
Prepared by:Maha al Otibi
 CH05 – Stack

Example of push and pop operations:

Perform the following operations on the Stack S1 showing values of Top pointer

1. Push(S1,14)
2. Push(S1,20)
3. Push(S1,90)
4. Pop

Push 14 Push 20 Push 90 Pop 90

[3] [3] [3]

[3]
[2] [2] Top [2]
90 [2]
[1] Top Top
20
Top 20 [1] 20 [1] [1]
14 [0] 14 [0] 14
14 [0] [0]

1 2 3 4

3.peek
Stack. peek() method in Java is used to retrieve or fetch the first element of the Stack or the
element present at the top of the Stack. The element retrieved does not get deleted or removed

from the Stack This operation returns the element on the top of the stack, but does
not remove it. The syntax: peek( );

4.isEmpty()
It returns true if nothing is on the top of the stack. Else, returns false. Tests if this stack
is empty. Returns true if the stack is empty, and returns

false if the stack contains elements.

– The syntax: isEmpty( );

57
Prepared by:Maha al Otibi
 CH05 – Stack

5. size( );
This operation displays the number of elements in a Stack. If a Stack is empty, it will
return zero otherwise return the number of the Stack elements.

– The syntax: size( );

Applications of Stacks:

❖ To find Reverse of a string

❖ Converting a decimal number into a binary number:

Converting a decimal number into a binary number:

The logic for transforming a decimal number into a binary number is as follows:

Start

Input: number

1. Iteration (while number is greater than zero)

1.1 Find out the remainder after dividing the number by 2

1.2 Print the remainder

1.3 Divide the number by 2

* End the iteration

End

However, there is a problem with this logic. Suppose the number, whose binary form
we want to find is 23. Using this logic, we get the result as 11101, instead of getting
10111. To solve this problem, we use a stack. We make use of the LIFO property of
the stack. Initially we push the binary digit formed into the stack, instead of printing it
directly. After the entire digit has been converted into the binary form, we pop one

58
Prepared by:Maha al Otibi
 CH05 – Stack

digit at a time from the stack and print it. Therefore we get the decimal number is
converted into its proper binary form.

Algorithm of converting a decimal number into a binary number:

Start

Input: number

1. Create a stack

2. Iteration1 (while number > 0)

2.1 remainder = number % 2

2.2 Push remainder into the stack

2.3 If the stack is full

2.3.1 Print an error

2.3.2 Stop the algorithm

2.4 End the if condition

2.5 Divide the number by 2

3. End iteration1

4. Iteration2 (while stack is not empty)

4.1 Pop digit from the stack

4.2 Print the digit
5. End iteration2
6. End

59
Prepared by:Maha al Otibi
 CH06 – Queues

Chapter 6

Queue 6
By the end of teaching this chapter, the student will be able to
Introduce the basics:
➢ Introduction to a Queue (FIFO)
➢ Create a Queue
➢ The basic operations are performed in the Queue : –
o Enqueue-add(item)
o Dequeue - poll( )
o peek( )
o isEmpty( )
o size( )

60
 CH06 – Queues

Chapter 6

Queues

Introduction

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a

queue is open at both its ends. One end is always used to insert data (enqueue) and
the other is used to remove data (dequeue). Queue follows First-In-First-Out
methodology, i.e., the data item stored first will be accessed first. A real-world
example of queue can be a single-lane one-way road, where the vehicle enters first,
exits first. More real-world examples can be seen as queues at the ticket windows
and bus-stops.

Queues Definition

61
 CH06 – Queues

❖ A queue is also known as FIFO (First in First out) Data Structure.

❖ A queue is a linear data structure.
❖ Data/Elements can only be inserted at one end and deleted at other end.
❖ The end from where insertion of data takes place is called Rear End.
❖ The end from where deletion of element /data takes place is called as Front
End.
❖ As in stacks, a queue can also be implemented using Arrays, Linked-lists,
Pointers and Structures. For the sake of simplicity, we shall implement
queues using one-dimensional array.

A queue is a linear data structure open at both its ends. One end is
always used to insert data (enqueue) and the other is used to remove
data (dequeue). also known as FIFO (First in First out) Data
Structure.

Operations on Queues

➢ Enqueue- add(item)
➢ Dequeue- poll( )
➢ peek( )
➢ isEmpty( )
➢ size( )

62
 CH06 – Queues

 Enqueue

✓ The Insert operation on queue is known as Enqueue.

✓ After the data has been inserted into the queue the new element
becomes the Rear.
✓ After Enqueue operation the value of rear is increased by one

Queue Overflow:

When the Queue is full there is not enough room to add element/value at the
Rear End of Queue. This State is known as Overflow State.
In this state the value of rear==n-1;
Example of enqueue operation:

Enqueue(Q , 23);

Element to be added
Name of the Queue
Add Operation
enqueue (Q,23) enqueue(Q,8) enqueue(Q,10)

23 23 8 23 8 10
[0] [1] [2] [0] [1] [2] [0] [1] [2] [0] [1] [2]

rear=front=-1 rear=front=0 front=0 rear=1 front=0 rear=2

63
 CH06 – Queues

 Dequeue

✓ The delete operation on queue is known as Dequeue.

✓ The deletions in queues always take place from front end.
✓ After every Dequeue operation the value of front is increased by
one

Queue Underflow:

When all elements are removed from the queue and there is no element to be
deleted at front end the state is known as Underflow State.
In this state the value of front==n-1;
The rear and front are initialized to -1 when the queue is empty.
Rear = front = -1

Example of dequeue operation

23 8 10 8 10 10
[2] [2] [0] [1] [2]
[0] [1] [2] [0] rear=2
front=0 [1] front=1[0]rear=2
[1]
front=2 rear=2
front=-1 rear=-1

64
 CH06 – Queues

Example of Enqueue and Dequeue operations:

Perform the following operations on the Queue Q7 showing values of

front and rear pointers.
1. Enqueue(Q7,32)
2. Enqueue(Q7,97)
3. Enqueue(Q7,50)
4. Enqueue(Q7,56)
5. Dequeue
6. Dequeue
0 1 2 3
32
Font=0 Rear=0

0 1 2 3
32 97
Front=0 Rear=1

0 1 2 3
32 97 50
Front=0 Rear=2

0 1 2 3
32 97 50 56
Front=0 Rear=3

0 1 2 3
97 50 56
Front=1 Rear=3

0 1 2 3
50 56
Front=2 Rear=3

65
 CH06 – Queues

3.peek
Queue. peek() method in Java is used to retrieve or fetch the first element of the
Queue or the element present at the top of the Stack. The element retrieved does not
get deleted or removed from the queue. This operation returns the element on the
first of the Queue, but does not remove it

The syntax: peek( );

4.isEmpty()
It returns true if nothing is on the top of the stack. Else, returns false. Tests if this Queue
is empty. Returns true if the stack is empty, and returns

false if the stack contains elements.

– The syntax: isEmpty( );

5. size( );
This operation displays the number of elements in a Queue. If a Queue is empty, it will
return zero otherwise return the number of the Queue elements.

– The syntax: size( );

Applications of Queue Data structure:

❖ O.S CPU FCFS Scheduling

❖ O.S FCFS Disk Scheduling

66
 CH07 – tree and graph

Chapter 7

Introduction to
Tree and Graph
7
By the end of teaching this chapter, the student will be able to:
➢ Define the basic concepts of tree graphs.
➢ Understand the fundamental concepts in tree graph theory.
➢ Learn the different types of graphs.

67
 CH07 – tree and graph

Chapter 7

Introduction to Tree and Graph

Tree

A Tree is a recursive data structure containing the set of one or more data nodes
where one node is designated as the root of the tree while the remaining nodes are
called as the children of the root. o The nodes other than the root node are partitioned
into the non empty sets where each one of them is to be called sub-tree. o Nodes of
a tree either maintain a parent-child relationship between them or they are sister
nodes. o In a general tree, A node can have any number of children nodes but it can
have only a single parent. o The following image shows a tree, where the node A is
the root node of the tree while the other nodes can be seen as the children of A.

A Tree is a recursive data structure containing the set of one

or more data nodes where one node is designated as the root
of the tree while the remaining nodes are called as the children
of the root
Trees Basic terminology :

• A tree is a useful non-linear data structure for rapidly storing data and rapidly
retrieving stored data.
68
 CH07 – tree and graph

• A tree consists of a finite set of elements, called nodes and finite set of directed
lines called branches that connect nodes.
• When a branch is directed towards the nodes it is called an indegree branch.
• When a branch is directed away from the node it is called an outdegree branch.
• Root Node :- The root node is the topmost node in the tree hierarchy. In other
words, the root node is the one which doesn't have any parent.
• Sub Tree :- If the root node is not null, the tree T1, T2 and T3 is called sub-trees
of the root node.
• Leaf Node :- The node of tree, which doesn't have any child node, is called leaf
node.
• Leaf node is the bottom most node of the tree. There can be any number of leaf
nodes present in a general tree. Leaf nodes can also be called external nodes
• . Path :- The sequence of consecutive edges is called path. In the tree shown in the
above image, path to the node E is A→ B → E.
• Ancestor node :- An ancestor of a node is any predecessor node on a path from root
to that node. The root node doesn't have any ancestors. In the tree shown in the
above image, the node F have the ancestors, B and A.
• Degree :- Degree of a node is equal to number of children, a node have. In the tree
shown in the above image, the degree of node B is 2. Degree of a leaf node is always
0 while in a complete binary tree, degree of each node is equal to 2.
• Level Number :- Each node of the tree is assigned a level number in such a way
that each node is present at one level higher than its parent.
• Root node of the tree is always present at level 0

Example:

69
 CH07 – tree and graph

Fig 1.1 Tree Structure

• The first/base node of tree is called the root. The indegree of root is zero (0).
• The nodes that do not have any children are called Leaf Nodes.
• A node with a predecessor is called a Child.
• A node of a tree that has child nodes and is thus not a leaf node is called Internal
node.
• The nodes with the same parent are called Siblings.
• A Path is a sequence of nodes in which each node is adjacent to the next node.
• Distance of one node from its root is called the Level of that node.
• Height is defined as the number of nodes which must be traversed from the root
to reach a leaf of a tree.
• A tree may be divided into Subtrees. A Subtree is any connected structure below
the root.

Level 0

Level 1

Level 2

As in the above figure :

☞ A is the root of the tree

☞ Indegree of A=0,B=1,C=1,D=1,E=1,F=1,G=1

☞ Outdegree of A=2,B=2,C=2,D=0,E=0,F=0,G=0
70
 CH07 – tree and graph

☞ B,C are child nodes of A

☞ D,E are child nodes of B

☞ F,G are child nodes of C

☞ Node A is at Level 0,Node B,C are at Level 1,Nodes D,E,F,G are at Level 2

☞ Path from A to G is given as :A-->C-->G

☞ B,C and D,E and F,G are called Siblings.

☞ D,E,F,G are called the Leaf Nodes.

☞ Height=Number of Levels in a tree=3.

☞ B, C are the internal nodes.

☞ B-D-E,C-F-G are subtrees

Binary Tree

A binary tree is a tree in which has at most two children.

Example:

71
 CH07 – tree and graph

Types of Binary trees:

1. Right skewed binary tree :- a tree in which every node has no left.

Right skewed binary tree

2. Left skewed binary tree – a tree in which every node has no right subtrees

Left skewed binary tree

3. A full binary tree (sometimes proper binary tree or 2-tree or strictly binary
tree) – A binary tree in which each node has exactly zero or two children.

72
 CH07 – tree and graph

full binary tree

4. A complete binary tree - is a binary tree in which every level, except possibly
the last, is completely filled, and all nodes are as far left as possible.

Complete binary tree

5. A perfect binary tree is a full binary tree in which all leaves have the
same depth or same level, and in which every parent has two children.

perfect binary tree

6. Null Tree: A tree with no nodes is called null tree.

Balance Factor: of a tree is the difference in height between its left and right
subtrees.
73
 CH07 – tree and graph

Eg : In above figure the height of left subtree is 2 and that of right is also 2 . So the
balance factor (BF) is given as:

BF=Left Subtree Height – Right Subtree height

BF=3-3=0

So the above tree is balanced. When the balanced factor of a tree is 0 the tree is said to
be balanced and its subtrees are also balanced.

Tree Traversal:

There are 2 basic approaches to traverse a tree:

1. Breadth-first
2. Depth-first.

1. Breadth-first

o There is only one kind of breadth-first traversal:

• The level order traversal. This traversal visits nodes by levels from top to bottom
from left to right and.

LevelOrder Traversal: A, B,C ,D, E, F, G

74
 CH07 – tree and graph

2. Depth-first

o There are three different types of depth-first traversals

• pre-order - node, left-branch, right-branch
• in-order - left-branch, node, right-branch
• post-order - left-branch, right-branch, node

Pre-order Traversal (NLR):

In a preorder traversal, the root node of the tree is processed first, then the left
subtree is traversed, then the right subtree.

Preorder traversal= A,B,D,E,C,F,G

Postorder Traversal (LRN):

In a postorder traversal, the left subtree is traversed, then the right subtree, and then the
root node is processed.

Postorder traversal= D,E,B,F,G,C,A.

Inorder Traversal:
In an inorder traversal, the left subtree is traversed first, then the root node is
processed, then the right subtree is traversed.
Inorder traversal= D,B,E,A,F,C,G

75
 CH07 – tree and graph

Advantages of trees

Trees are so useful and frequently used, because they have some very serious
advantages:

• Trees reflect structural relationships in the data

• Trees are used to represent hierarchies

• Trees provide an efficient insertion and searching

• Trees are very flexible data, allowing to move subtrees around with
minimum effort

76
 CH07 – tree and graph

Introduction to Graphs

Definition: A graph is a set of vertices and a binary

relation between vertices, adjacency.

• A tree is a special case of the more general graph (or net).

• Graphs have many uses from network analysis to spreadsheet operation.
Popular graph-related puzzles include:

▪ Finding whether one can traverse all edges without traversing any twice
(an Euler Path).

▪ The Travelling Salesman Problem - how to visit all the nodes at a

minimal cost

▪ Finding the shortest (least cost) path between 2 vertices

▪ Finding the "minimal spanning tree" - finding a tree (with the least-cost
edges) that includes all nodes

A set of items are connected by edges. Each item is called a vertex or node.

Edges can have a cost associated with them, and the cost may depend on the
direction taken along the edge

There are two important sets of objects, which specify graph and its structure.
First set is V, which is called vertex-set. Each vertex can be drawn as a circle
with vertex's number inside.

77
 CH07 – tree and graph

 Vertices/Nodes
Next important set is E, which is called edge-set. E is a subset of V x V. Simply
speaking, each edge connects two vertices, including a case, when a vertex is connected
to itself (such an edge is called a loop).

All graphs are divided into two big groups: directed and undirected graphs.

 Directed Graph

A directed graph is a graph in which the edges are directed by arrows. Directed
graph is also known as digraphs.

In the above graph, each edge is directed by the arrow. A directed

edge has an arrow from A to B, means A is related to B, but B is
not related to A.

78
 CH07 – tree and graph

 Undirected Graph

An undirected graph is a graph whose edges are not directed.

In the above graph since there is no directed edges, therefore it is

an undirected graph.
Examples

Undirected Graph

Vertex Set of graph:1,2,3,4

Edge set of following graph:1-2,2-4,4-3,3-1

Directed Graph

79
 CH07 – tree and graph

Graph Terminologies

➢ A path can be defined as the sequence of nodes that are followed in order to
reach some terminal node V from the initial node U.
➢ Closed Path A path will be called as closed path if the initial node is same as
terminal node. A path will be closed path if V0=VN.
➢ Isolated vertex (i.e. an “edge-less” vertex);
➢ Loop (i.e. a vertex connected to itself by an edge);
➢ Adjacent vertices (vertices connected by one edge);
➢ Any edge is incident on its (endpoint) vertices;
➢ Adjacent edges (i.e. two edges incident on same vertex);

Types of Graphs
Though, there are a lot of different types of graphs depending upon the number of
vertices, number of edges, interconnectivity, and their overall structure, some of
such common types of graphs are as follows:

80
 CH07 – tree and graph

 Null Graph (Empty Graph)

A null graph is a graph in which there are no edges between its vertices. A null
graph is also called empty graph.

 Trivial Graph
A trivial graph is the graph which has only one vertex.

 Simple Graph

A simple graph is the undirected graph with no parallel edges and no loops.

In the above example, first graph is not a simple graph because it

has two edges between the vertices A and B and it also has a loop.

81
 CH07 – tree and graph

Second graph is a simple graph because it does not contain any loop
and parallel edges.

 Undirected Graph

An undirected graph is a graph whose edges are not directed.

In the above graph since there is no directed edges, therefore it is

an undirected graph.

 Directed Graph

A directed graph is a graph in which the edges are directed by arrows. Directed
graph is also known as digraphs.

82
 CH07 – tree and graph

In the above graph, each edge is directed by the arrow. A directed

edge has an arrow from A to B, means A is related to B, but B is
not related to A.

 Complete Graph

A graph in which every pair of vertices is joined by exactly one edge is called
complete graph. It contains all possible edges.

In the above example, since each vertex in the graph is connected

with all the remaining vertices through exactly one edge therefore,
both graphs are complete graph.

 Connected Graph
A connected graph is a graph in which we can visit from any one vertex to any
other vertex. In a connected graph, at least one edge or path exists between every
pair of vertices.

83
 CH07 – tree and graph

In the above example, we can traverse from any one vertex to any
other vertex. It means there exists at least one path between every
pair of vertices therefore, it a connected graph.

 Disconnected Graph
A disconnected graph is a graph in which any path does not exist between every
pair of vertices.

The above graph consists of two independent components which

are disconnected. Since it is not possible to visit from the vertices
of one component to the vertices of other components therefore, it
is a disconnected graph.

Graph Terminology

Path: A path can be defined as the sequence of nodes that are followed in
order to reach some terminal node V from the initial node U.

Closed Path: A path will be called as closed path if the initial node is same as
terminal node. A path will be closed path if V0=VN.

Simple Path: If all the nodes of the graph are distinct with an exception
V0=VN, then such path P is called as closed simple path.

84
 CH07 – tree and graph

Cycle: A cycle can be defined as the path which has no repeated edges or
vertices except the first and last vertices.

Connected Graph: A connected graph is the one in which some path exists
between every two vertices (u, v) in V. There are no isolated nodes in
connected graph.

graph in which each edge of the graph is associated with some direction and
the traversing can be done only in the specified direction.

Loop :An edge that is associated with the similar end points can be called as
Loop. Adjacent Nodes: If two nodes u and v are connected via an edge e,
then the nodes u and v are called as neighbors or adjacent nodes.

Degree of the Node :A degree of a node is the number of edges that are
connected with that node. A node with degree 0 is called as isolated node.

Complete Graph: A complete graph is the one in which every node is

connected with all other nodes. A complete graph contain n(n-1)/2 edges
where n is the number of nodes in the graph.

Weighted Graph :In a weighted graph, each edge is assigned with some data
such as length or weight. The weight of an edge e can be given as w(e) which
must be a positive (+) value indicating the cost of traversing the edge.

Graph Traversal Algorithms

The breadth first search (BFS) and the depth first search (DFS) are the two
algorithms used for traversing and searching a node in a graph.

85
 CH07 – tree and graph

Depth First Search (DFS)

The aim of DFS algorithm is to traverse the graph in such a way that it tries to
go far from the root node. Stack is used in the implementation of the depth first
search. Let’s see how depth first search works with respect to the following
graph:

As stated before, in DFS, nodes are visited by going through the depth of the
tree from the starting node. If we do the depth first traversal of the above graph
and print the visited node, it will be “A B E F C D”. DFS visits the root node
and then its children nodes until it reaches the end node, i.e. E and F nodes,
then moves up to the parent nodes.

Algorithmic Steps
1. Step 1: Push the root node in the Stack.
2. Step 2: Loop (step3,4,5) until stack is empty.
3. Step 3: Peek the node of the stack.
4. Step 4: If the node has unvisited child nodes, get the unvisited child node,
mark it as traversed and push it on stack.
5. Step 5: If the node does not have any unvisited child nodes, pop the node
from the stack.

Breadth First Search (BFS)

This is a very different approach for traversing the graph nodes. The aim of
BFS algorithm is to traverse the graph as close as possible to the root node.
Queue is used in the implementation of the breadth first search. Let’s see how
BFS traversal works with respect to the following graph:

86
 CH07 – tree and graph

If we do the breadth first traversal of the above graph and print the visited node
as the output, it will print the following output. “A B C D E F”. The BFS visits
the nodes level by level, so it will start with level 0 which is the root node, and
then it moves to the next levels which are B, C and D, then the last levels
which are E and F.

Algorithmic Steps
1. Step 1: Push the root node in the Queue.
2. Step 2: Loop (step3,4,5) until the queue is empty.
3. Step 3: Remove the node from the Queue.
4. Step 4: If the removed node has unvisited child nodes, mark them as visited
and insert the unvisited children in the queue.
Exercise:

Consider the following graph:

1. The vertex set = ………………………………………………..

2. The edge set = …………………………………………………..

3. The output of the graph depth first search= …………………..

4. The output of the graph breadth first search…………………….

87
 CH09 – Sorting

Chapter 8

Searching
8
By the end of teaching this chapter, the student will be able to:

➢ Understand the fundamental concepts of Searching.

➢ Learn the different methods of Searching.
➢ Linear search
➢ Binary search
➢ Which one is the best?

88
 CH09 – Sorting

Chapter 8

Searching

Introduction

Searching is the process of finding some particular element in the list. If the
element is present in the list, then the process is called successful and the
process returns the location of that element, otherwise the search is called
unsuccessful.

 Searching Techniques

• Searching is an operation which finds the location of a given element in a list.

• The search is successful if the element to be searched is found.
• The search is unsuccessful if the element to be searched is not found.
• There are two standard types of searching methods:
o Linear Search
o Binary Search.

89
 CH09 – Sorting

Linear Search

Linear search is the simplest search algorithm and often called sequential search. In this
type of searching, we simply traverse the list completely and match each element of the
list with the item whose location is to be found. If the match found then location of the
item is returned otherwise the algorithm return NULL or -1. Linear search is mostly
used to search an unordered list in which the items are not sorted.

• Linear Search is a search algorithm that searches a list of data for a particular
value.
• It operates by checking every element of a list one at a time in sequence until a
match is found.

a linear search or sequential search is a method for finding an element

within a list. It sequentially checks each element of the list until a match is
found or the whole list has been searched.

 Example
• The array shown in the figure below consists of 6 numbers. Suppose the element
to searched is 5. So 5 is compared with all the elements starting with 0th element
.
• The searching process will end either when 5 is found or the list ends.

21 33 10 3 5 44

21 33 10 3 5 44

21 33 10 3 5 44

21 33 10 3 5 44

21 33 10 3 5 44

Linear Search in an Array

90
 CH09 – Sorting

 Time Complexity

The time complexity of linear search algorithm is O(n). linear search is rarely used
practically because other search algorithms such as the binary search algorithm and hash
tables allow significantly faster searching comparison to Linear search.

Binary Search

Binary search is the search technique which works efficiently on the sorted
lists. Hence, in order to search an element into some list by using binary
search technique, we must ensure that the list is sorted.

• Binary search method is very fast and efficient. This method requires that a list of
elements be in a sorted order.
• In this method, to search an element we compare it with the element present at the
center of the list, if it matches then the search is successful.
• Otherwise, the list is divided into two halves: one from 0th element to center
element and other from center element to the last element.
• If the element to be searched is less than the center element, then it is searched in
first half and if it is greater than the center element then it is to be searched in the
second half of the list.
• Binary search follows divide and conquer approach in which, the list is divided
into two halves and the item is compared with the middle element of the list. If the
match is found then, the location of middle element is returned otherwise, we
search into either of the halves depending upon the result produced through the
match.

91
 CH09 – Sorting

 Example
Binary Search Algorithm can be implemented in two ways which are discussed below.

1. Iterative Method

2. Recursive Method

The recursive method follows the divide and conquer approach.

The general steps for both methods are discussed below.

1. The array in which searching is to be performed is:

Initial array:

Let x = 4 be the element to be searched.

2. Set two pointers low and high at the lowest and the highest positions respectively.
Setting pointers:

3. Find the middle element mid of the array ie. arr[(low + high)/2] = 6.

4. If x == mid, then return mid. Else, compare the element to be searched with m.

5. If x > mid, compare x with the middle element of the elements on the right side of mid. This is
done by setting low to low = mid + 1.
6. Else, compare x with the middle element of the elements on the left side of mid. This is done
by setting high to high = mid - 1.

Finding mid element

7. Repeat steps 3 to 6 until low meets high.

92
 CH09 – Sorting

8. x = 4 is found.

 Time Complexity
The time complexity of binary search algorithm is O(log n). Which means, it does not
visit all element on a list. It will divide the list over and over until get the element and
return the position.

 Which One is The Best

Actually, It depends on the organization of elements in an array or a list.

1. If the elements are ordered, the best way to search is using binary search.

2. If the elements are not ordered, then the only way to search a key through a list is
using linear search which visits all the elements.

93
 CH08 – searching

Chapter 9

Sorting
9
By the end of teaching this chapter, the student will be able to:

➢ Understand the fundamental concepts of Sorting.

➢ Learn the different methods of Sorting.
➢ Insertion Sort
➢ selection Sort
➢ Merge Sort

94
 CH08 – searching

Chapter 5

Sorting

Introduction

Sorting algorithm refers to arranging data in a particular format and order. Most
common orders are in numerical or lexicographical order. The importance of sorting
lies in the fact that data searching can be optimized to a very high level, if data is stored
in a sorted manner. Sorting is also used to represent data in more readable formats.
Sorting means arranging a set of data in some order i.e. ascending (from smallest to
largest) or descending order (from largest to smallest). Following are some of the
examples of sorting in real-life scenarios

Telephone Directory−The telephone directory stores the telephone numbers of people

sorted by their names, so that the names can be searched easily.

Dictionary −The dictionary stores words in an alphabetical order so that searching of

any word becomes easy.

There are two methods of Sorting: Internal Sorting and External Sorting

95
 CH08 – searching

 Internal Sorting

If all the data that is to be sorted is stored in memory then internal sorting methods are
used.The different methods of internal sorting are:

o Bubble sort
o Selection sort
o Insertion Sort
o Quick Sort

 External Sorting

When the data to be sorted is so large that some of the data is present in the memory and
some is kept in auxiliary memory (Hard disk, CD’s, Floppy, Tape, etc.), then external
sorting methods are used. The different methods of external sorting are:

o Sorting with Disks

o Sorting with Tapes

Selection Sort Algorithm

Selection sort is a sorting algorithm that selects the smallest element from an unsorted
list in each iteration and places that element at the beginning of the unsorted list.
Working of Selection Sort

1. Set the first element as minimum.

96
 CH08 – searching

2. Select first element as minimum

Compare minimum with the second element. If the second element is smaller
than minimum, assign the second element as minimum.
Compare minimum with the third element. Again, if the third element is smaller, then
assign minimum to the third element otherwise do nothing. The process goes on until
the last element.

3. After each iteration, minimum is placed in the front of the unsorted list.

4. For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are
repeated until all the elements are placed at their correct positions.

The first iteration

97
 CH08 – searching

The second iteration

The third iteration

98
 CH08 – searching

The fourth iteration

TIME COMPLEXITY – WORST CASE O(n 2)

99
 CH08 – searching

insertion Sort Algorithm

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place
in each iteration.
Insertion sort works similarly as we sort cards in our hand in a card game.

We assume that the first card is already sorted then, we select an unsorted card. If the
unsorted card is greater than the card in hand, it is placed on the right otherwise, to the
left. In the same way, other unsorted cards are taken and put in their right place.

A similar approach is used by insertion sort.

Working of Insertion Sort

Suppose we need to sort the following array.

1. The first element in the array is assumed to be sorted. Take the second element
and store it separately in key.

Compare key with the first element. If the first element is greater than key,
then key is placed in front of the first element.

100
 CH08 – searching

If the first element is greater than key, then key is placed in front of the first
element.
2. Now, the first two elements are sorted.

Take the third element and compare it with the elements on the left of it. Placed it
just behind the element smaller than it. If there is no element smaller than it, then

101
 CH08 – searching

place it at the beginning of the array.

Place 1 at the beginning

102
 CH08 – searching

3. Similarly, place every unsorted element at its correct position.

Place 4 behind 1

103
 CH08 – searching

Place 3 behind 1 and the

array is sorted

TIME COMPLEXITY – WORST CASE O(n 2)

104
 CH08 – searching

merge Sort Algorithm

Merge Sort is one of the most popular sorting algorithms that is based on the principle
of Divide and Conquer Algorithm.

Here, a problem is divided into multiple sub-problems. Each sub-problem is solved

individually. Finally, sub-problems are combined to form the final solution.

Merge Sort example

105
 CH08 – searching

Divide and Conquer Strategy

Using the Divide and Conquer technique, we divide a problem into subproblems.
When the solution to each subproblem is ready, we 'combine' the results from the
subproblems to solve the main problem.
Suppose we had to sort an array A. A subproblem would be to sort a sub-section of this
array starting at index p and ending at index r, denoted as A[p..r].
Divide
If q is the half-way point between p and r, then we can split the subarray A[p..r] into two
arrays A[p..q] and A[q+1, r].
Conquer
In the conquer step, we try to sort both the subarrays A[p..q] and A[q+1, r]. If we haven't
yet reached the base case, we again divide both these subarrays and try to sort them.
Combine
When the conquer step reaches the base step and we get two sorted
subarrays A[p..q] and A[q+1, r] for array A[p..r], we combine the results by creating a
sorted array A[p..r] from two sorted subarrays A[p..q] and A[q+1, r].

MergeSort Algorithm

The MergeSort function repeatedly divides the array into two halves until we reach a
stage where we try to perform MergeSort on a subarray of size 1 i.e. p == r.
After that, the merge function comes into play and combines the sorted arrays into larger
arrays until the whole array is merged.

MergeSort(A, p, r):
if p > r

return

106
 CH08 – searching

q = (p+r)/2

mergeSort(A, p, q)
mergeSort(A, q+1, r)

merge(A, p, q, r)

To sort an entire array, we need to call MergeSort(A, 0, length(A)-1).

As shown in the image below, the merge sort algorithm recursively divides the array
into halves until we reach the base case of array with 1 element. After that, the merge
function picks up the sorted sub-arrays and merges them to gradually sort the entire
array.

Merge sort in action

The merge Step of Merge Sort

Every recursive algorithm is dependent on a base case and the ability to combine the
results from base cases. Merge sort is no different. The most important part of the merge
sort algorithm is, you guessed it, merge step.

107
 CH08 – searching

The merge step is the solution to the simple problem of merging two sorted lists(arrays)
to build one large sorted list(array).

The algorithm maintains three pointers, one for each of the two arrays and one for
maintaining the current index of the final sorted array.

Have we reached the end of any of the arrays?

No:

Compare current elements of both arrays

Copy smaller element into sorted array
Move pointer of element containing smaller element
Yes:

Copy all remaining elements of non-empty array

108
 CH08 – searching

Merge step

Writing the Code for Merge Algorithm

A noticeable difference between the merging step we described above and the one we
use for merge sort is that we only perform the merge function on consecutive sub-arrays.

This is why we only need the array, the first position, the last index of the first
subarray(we can calculate the first index of the second subarray) and the last index of
the second subarray.

109
 CH08 – searching

Our task is to merge two subarrays A[p..q] and A[q+1..r] to create a sorted array A[p..r].
So the inputs to the function are A, p, q and r
The merge function works as follows:

1. Create copies of the subarrays L ← A[p..q] and M ← A[q+1..r].

2. Create three pointers i, j and k
a. i maintains current index of L, starting at 1
b. j maintains current index of M, starting at 1
c. k maintains the current index of A[p..q], starting at p.
3. Until we reach the end of either L or M, pick the larger among the elements
from L and M and place them in the correct position at A[p..q]
4. When we run out of elements in either L or M, pick up the remaining elements
and put in A[p..q]
and return the position.
TIME COMPLEXITY – WORST CASE O(n log n)

110