0% found this document useful (0 votes)

17 views296 pages

Data Structures and Algorithms

The document provides an overview of data structures and algorithms, explaining the organization of data in computers and the various types of data structures, including primitive and non-primitive types. It discusses operations on data structures, such as creating, inserting, and deleting, as well as the concept of abstract data types and dynamic memory allocation in C. Overall, it emphasizes the importance of selecting appropriate data structures for efficient programming.

Uploaded by

giria4621

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

17 views296 pages

Data Structures and Algorithms

Uploaded by

giria4621

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Data Structures and Algorithms

P
R
E
P
R
E
D

S INTRODUCTION TO DATA STRUCTURES & ALGORITHMS

U
L
A
V

N
E
P
A
L

2
P
R
E Data
P
A
R
E ⚫ Data are the raw facts that needs to be processed to form
D
an information.
B
Y

S AND
U
L
A
V ⚫ Computeris an electronic devicethat storesand processdata in the
N
formof binary digits.
E
P
A
L

3 11/14/2022 10:59AM
P
R
E How Computer Stores Data?
P
A
R
E ⚫ Bit (i.e. Binary Digit) is the smallest unit of computer storage.
D

B
Y ⚫ It contains either 0 or 1.
S
U
L ⚫ 1 𝑏𝑖𝑡 × 8 = 1 𝑏𝑦𝑡𝑒
A
V

N
E
P ⚫ 1 𝑏𝑦𝑡𝑒 × 1024 = 1 𝐾𝑖𝑙𝑜𝐵𝑦𝑡𝑒
A
L

4 1 𝐾𝑖𝑙𝑜𝐵𝑦𝑡𝑒 × 1024 = 1 𝑀𝑒𝑔𝑎𝐵𝑦𝑡𝑒 11/14/2022 10:59AM

P
R
E Computer Storage
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L Imagine 1 squareis equal to 1 byte
5 11/14/2022 10:59AM
P
R
E Computer Storage
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L Imagine if there arethousands of numbers stored in computer
6 11/14/2022 10:59AM
P
R
E Data Structure
P
A
R
E
D

B
Y

S So,a data structure is a particular way of organizing data

U
L in a computer so that it can be used effectively.
A
V

N
E
P
A
L

7 11/14/2022 10:59AM
P
R
E Computer Storage
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L This is howdata in an array is stored in computer.
8 11/14/2022 10:59AM
P
R
E Data Structure
P
A
R
⚫ Data aresimply value or set of values.
E
D

B
⚫ Adata itemrefersto a single unit of values.
Y

S ⚫ Data structure is the wayof organizing data items by considering its

U
L relationship to eachother.
A
V

N ⚫ Data structure can also bedefined as the logical or mathematical

E model of a particular organization of data.
P
A
L
⚫ Data structures arethe building blocks of a program.
9 11/14/2022 10:59AM
P
R
E Data Structure
P
A
R
⚫ Data structure mainly specifies the following four things:
E ⚫ Organization of data
D
⚫ Accessing methods
B
Y ⚫ Degreeof associativity
⚫ Processing alternativesfor information
S
U
L
A ⚫ To develop a program of an algorithm, we should select
V
an appropriatedata structure for that algorithm.
N
E
P
A ⚫ Therefore,data structure is represented as:
L
𝐴𝑙𝑔𝑜𝑟𝑖𝑡ℎ𝑚 + 𝐷𝑎𝑡𝑎 𝑆𝑡𝑟𝑢𝑐𝑡𝑢𝑟𝑒 = 𝑃𝑟𝑜𝑔𝑟𝑎𝑚
10 11/14/2022 10:59AM
P
R
E Data Structure
P
A
R
⚫ Toconclude,data structure is an agreementabout:
E ⚫ Howto store a collectionof objects in memory?
D

B
Y ⚫ What operations we can performon that data?

S
U ⚫ The algorithms for all those operations.
L
A
V
⚫ Howtime and space efficient those algorithms are?
N
E
P
A
L

11 11/14/2022 10:59AM
P
R
E Classification of Data Structure
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

12 11/14/2022 10:59AM
P
R
E Classification of Data Structure
P
A
R
⚫ Primitivedata structures
E ⚫ Fundamental (built-in) data types which are supported by a
D
programming language.
B
Y
⚫ Somebasicdata types are integer,character,Boolean,real,etc.
S
U
L
A
⚫ Theterms‘data type’, ‘basicdatatypes’, and‘primitive datatypes’are
V often usedinterchangeably.
N
E
P
A
L

13 11/14/2022 10:59AM
P
R
E Classification of Data Structure
P
A
R
⚫ Non-primitive data structures
E ⚫ Those data structures which are created using primitive data structures;
D
i.e. user-defined data type.
B
Y
⚫ Somenon-primitive data types are linked list,stack,tree,graph,etc.
S
U
L
A
⚫ Non-primitive data structures can be further classified into
V two categories:
N ⚫ Lineardata structure
E ⚫ Non-lineardata structure
P
A
L

14 11/14/2022 10:59AM
P
R
E Classification of Data Structure
P
A
R
⚫ Linear data structure
E ⚫ Elements of a data structure arestored in a linear or sequential order.
D

B
Y ⚫ Forexample:array,linked list,stack,queue,etc.

S
U ⚫ Linear data structures can berepresented in memoryin two different
L
A
ways:
V ⚫ Onewayis to havealinear relationship betweenelementsbymeansof sequential
memory locations (static memory location).
N
E
P ⚫ Theotherwayistohavealinearrelationshipbetweenelementsbymeansoflinks
A
L
(dynamic memory location).

15 11/14/2022 10:59AM
P
R
E Classification of Data Structure
P
A
R
⚫ Non-linear data structure
E ⚫ Elements of a data structure are not stored in a linear or sequential
D
order.
B
Y
⚫ The relationship of adjacencyis not maintained betweenelementsof a
S
U non-linear data structure.
L
A
V ⚫ Examples includetreeand graph.
N
E
P
A
L

16 11/14/2022 10:59AM
P
R
E Classification of Data Structure
P
A ⚫ Array
R ⚫ Lineardatastructurethatcollectselementsofthesamedata type and stores them in contiguous and adjacent
E memorylocations.
D
⚫ Linked list
B ⚫ Asequenceof data structureswhichareconnectedtogethervia links.Eachlink containsa connection to another
link.
Y

S ⚫ Stack
U ⚫ Linear data structurethat follows the principle of Last In First Out (LIFO).
L
A ⚫ Queue
V ⚫ Linear data structurethat follows the principle of First In First Out (FIFO).

N ⚫ Tree
E ⚫ Non-linear hierarchical data structuredefined as a collectionof nodes whichare connectedbyedges.
P
A ⚫ Graph
L ⚫ Non-linear hierarchical data structurethat consistsof a finite set of nodes and a set of edgesconnectingthem.

17 11/14/2022 10:59AM
P
R
E Operations on Data Structure
P
A ⚫ Mandatory Operations
R
⚫ Creating
E
D

B
⚫ Inserting
Y

S
U ⚫ Traversing
L
A
V
⚫ Updating
N
E
P
A ⚫ Deleting
L

18 11/14/2022 10:59AM
P
R
E Operations on Data Structure
P
A ⚫ Non-mandatory Operations
R
E ⚫ Searching
D ⚫ Used to find locationof one ormoredata items that satisfy the given constraint.
B
Y ⚫ Sorting
S ⚫ Used to arrangedata in someorderlike ascending ordescending.
U
L
A ⚫ Merging
V ⚫ Usedto combinelistsoftwosorteddataitemstoform a single list of sorted data
item.
N
E
P
⚫ Splitting
A
L ⚫ Used to separateasinglelist ofsorted data itemto formalists oftwodifferent
sorted data items.
19 11/14/2022 10:59AM
P
R
E Data Types
P
A
R
⚫ A data type, in programming, is a classification that specifies which
E type of value a variable has and what type of mathematical,
D
relational or logical operations can be applied to it without causing
B an error.
Y

S
U ⚫ An integer,for example,is a data type used to classify whole numbers
L
A and a string is a data type that is used to classify text.
V

N
E ⚫ For example,
P
⚫ Csupports int, float, char, double,etc.
A
L ⚫ Pythonsupports String,List,Tuple,etc.
21 ⚫ . . . and soon. 11/14/2022 10:59AM
P
R
E Data Types
P
A
R
⚫ Primitive
E ⚫ Basic building block (int, float,char, Boolean,etc.)
D

B
Y ⚫ Composite
S
⚫ Any data type (array, string, struct, etc.) composed of primitives or
U composite types.
L
A
V
⚫ Abstract
N ⚫ Data type that is defined by its behavior (tuple,set,stack,queue,graph,
E
P etc.)
A
L

22 11/14/2022 10:59AM
P
R
E Data Types
P
A ⚫ In a broad sense,there are three types of data types:
R
E ⚫ Fundamental (Basics) data types
D ⚫ Predefineddata types whichareusedbythe programmerdirectly to storeonly one
B
value asper requirement;i.e.integer type,charactertype,etc.
Y

S
⚫ Derived data types
U ⚫ Derivedusing built in datatypewhich aredesignedbythe programmer to store
L multiple valuesof sametypeas per their requirement.
A
⚫ Forexample:array,functions,pointers,etc.
V

N
⚫ User-defined data types
E
P ⚫ Derived using built-in data types which are wrapped into a single data type to
A store multiple values of either same type or different type or both as per their
L requirement.
⚫ For example:class, structure,etc.
23 11/14/2022 10:59AM
P
R
E Data Types
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

23 11/14/2022 10:59AM
P
R
E Abstract Data Types
P
A ⚫ AbstractDataTypes(ADT)areentities that aredefinitions ofdata
R
E and operations but do not have implementation details.
D

B ⚫ ADTis adata type whoserepresentation is hidden from, andof no

Y
concern to the application code.
S
U
L ⚫ ADTisausefultool forspecifyingthelogicalproperties of a data
A
V type.
N
E ⚫ For example, when writing application code, we don’t care how
P
A strings are represented; we just declare variables of type string, and
L manipulate them by using string operations.
24 11/14/2022 10:59AM
P
R
E Abstract Data Types
P
A
R
⚫ Once an abstract data type has been designed, the programmer
E responsible for implementing that type is concerned only with
D
choosing a suitable data structure and coding up the methods.
B
Y

S ⚫ On the other hand, application programmers are concerned only with

U using that type and calling its methods without worrying much
L
A about howthe type is implemented.
V

N
E what to do by hiding how to do it !!
P
A
L

25 11/14/2022 10:59AM
P
R
E Abstract Data Types
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

26 11/14/2022 10:59AM
P
R
E Abstract Data Types
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

27 11/14/2022 10:59AM
P
R
E Dynamic Memory Allocation in C
P
A ⚫ The process of allocating and freeing memory at run time is known as
R
E dynamic memory allocation.
D

B ⚫ This reserves the memory required by the program and returns

Y
valuable resources to the system once the use of reserved space is
S utilized.
U
L
A
V ⚫ Though arrayscan beused for data storage,they are of fixed size.
#definem5
N
E void main()
P
A
{ int x[m];
L printf(“%lu\n”,sizeof(x));
29
} 11/14/2022 10:59AM
P
R
E Dynamic Memory Allocation in C
P
A
R
⚫ Consideran array size of 100 to store marks of 100 student.
E
D
⚫ If the number of students is less than 100 say 10, only 10 memory
B
Y locations will be used and rest 90 locations are reserved but will not
S be used. i.e. wastageof memory will occur.
U
L
A
V
⚫ In such situation DMAwill beuseful.

N
E
P
A
L

30 11/14/2022 10:59AM
P
R
E Dynamic Memory Allocation in C
P
A ⚫ Since an array name is actually a pointer to the first element within
R
E the array, it is possible to define the array as a pointer variable rather
D than as a conventional array.
B
Y
⚫ While defining conventional array, system reserves fixed block of
S memory at the beginning of program execution which is inefficient
U
L but this does not occur if the array is represented in terms of a
A pointer variable.
V

N
E ⚫ The use of pointer variable to represent an array requires sometype of
P initial memory assignment before the array elements are processed.
A
L

31
⚫ This is known as DynamicMemoryAllocation (DMA). 11/14/2022 10:59AM
P
R
E Dynamic Memory Allocation in C
P
A ⚫ At execution time, a program can request more memory froma free memory
R
E pool and freesif not required usingDMA.
D

B ⚫ Thus, DMArefersallocatingandfreeingmemoryat executiontimeorrun

Y time.
S
U
L ⚫ There are four library functions for memory management:
A ⚫ malloc()
V
⚫ calloc()
N ⚫ free()
E ⚫ realloc()
P
A
L
⚫ Thesefunctions are defined within header file stdlib.h and alloc.h
31 11/14/2022 10:59AM
P
R
E Dynamic Memory Allocation in C
P
A
R
⚫ There are four library functions for memory management:
E ⚫ malloc()
D
⚫ Used to allocate memoryto structures
B
Y
⚫ calloc()
S
U ⚫ Used to allocate memoryto arrays
L
A
V ⚫ realloc()
⚫ Used to increaseor decreasethe sizeof array
N
E
P
A ⚫ free()
L ⚫ Used to delete the memory
32 11/14/2022 10:59AM
P
R
E DMA in C – malloc()
P
A
R
⚫ It allocates requestedsize of bytesand returnsapointer to the first
E byte of the allocated space.
D
ptr=(data_type*) malloc(size_of_block);
B
Y

S ⚫ Here, ptr is a pointer of type data_type. The malloc() returns

U a pointer to an areaof memory with size size_of_block.
L
A x=(void*) malloc(100*sizeof(int));
V

N
E ⚫ A memory space equivalent to 100 times the size of an integer is
P
A
reserved and the address of the first byte of the memory allocated is
L assigned to the pointer x of type int. (i.e. x refers to the first address
34
of allocated memory). 11/14/2022 10:59AM
P
R
E DMA in C – malloc()
P
A void main()
R
#include<stdio.h> {
E #include<stdlib.h> struct Emp *ptr;
D ptr=(struct Emp*)malloc(sizeof(struct Emp));
struct Emp if(ptr==NULL)
B {
Y { printf("Memory allocation failed\n");
}
S int eno; else
U {
L char ename[20]; printf("Enter Employee Number:\ n");
A scanf("%d",&ptr->eno);
V float esal; printf("Enter Employee Name:\ n");
scanf("%s",ptr->ename);
N }; printf("Enter Employee Salary:\ n");
E scanf("%f",&ptr->esal);
P printf("\nEmployee Number = %d\nEmployee Name =
%s\nEmployee Salary = %f",ptr->eno,ptr-
A >ename,ptr->esal);
L }
}
35 11/14/2022 10:59AM
P
R
E DMA in C – calloc()
P
A ⚫ Thefunction providesaccessto the Cmemory heap, whichisavailablefordynamicallocationof
R variable-sized blocks of memory.
E
D ⚫ Unlike malloc(),it accepts two arguments:no_of_blocks and size_of_each_block specifies the size of
each item.
B
Y
⚫ Thefunction callocallocatesmultiple blocks of storage, each of the same size and then sets all bytes
to zero.
S
U
L ⚫ Calloc initializes all bytes in the allocatedblock to zero.
A ptr=(data_type*) calloc(no_of_blocks,size_of_each_block);
V
⚫ For example:
N
x=(int*) calloc(5,10* sizeof(int)); OR
E
x=(int*) calloc(5,20);
P
A
L ⚫ The above statement allocatescontiguous space for 5 blocks,each of size 20 bytes.i.e.wecan store 5
arrays, each of 10 elements of integertypes.
36 11/14/2022 10:59AM
P
R
E DMA in C – calloc()
P
A #include<stdio.h>
R #include<stdlib.h>
E void main()
D {
int n,*arr, i;
B printf("Entersizeof anarray:\ n");
Y
scanf("%d",&n);
arr=(int*)calloc(n,sizeof(int));
S
U if(arr==NULL)
L printf("MemoryallocationFAILED!!");
A else
V {
printf("Array elementsare:\ n");
N for(i=0;i<n;i++)
E {
P
printf("%d\n",*(arr+i));
A
L }
}
37
} 11/14/2022 10:59AM
P
R
E DMA in C – realloc()
P
A ⚫ This function is used to modify the size of previouslyallocated space.
R
E
D ⚫ Sometimesthepreviouslyallocatedmemoryisnotsufficient; weneed additional
space and sometimethe allocated memoryis much largerthan necessary.
B
Y
⚫ Wecanchange memorysize alreadyallocated with the help of function realloc().
S
U
L ⚫ If the original allocation is done bythe statement: ptr=malloc(size);
A
V
⚫ Then, reallocation of space may be done by the statement:
N ptr=realloc(ptr,newsize);
E
P ⚫ This function allocates a new memory space of size newsize to the pointer variable
A
L
ptr and returns a pointer to the first byte of the new memory block and on failure
the function return NULL.
38 11/14/2022 10:59AM
P
R
E DMA in C – realloc()
P
A #include<stdio.h>
R #include<stdlib.h>
E void main()
D {
int n, *arr,i;
B printf("Enter size:\n");
Y scanf("%d",&n);
arr=(int*)calloc(n,sizeof(int));
S n++;
U arr=(int*)realloc(arr,n*sizeof(int));
L if(arr==NULL)
A printf("Memory allocation FAILED!!");
V else
{
N printf("Array elements are:\n");
E for(i=0;i<n;i++)
P {
A printf("%d\n",*(arr+i));
L }
}
39 } 11/14/2022 10:59AM
P
R
E DMA in C – free()
P
A
R
⚫ Freespreviously allocated space by calloc,malloc or realloc functions.
E
D
⚫ The memory dynamically allocated is not returned to the system
B
Y until the programmer returns the memory explicitly. This can be done
S using free() function.
U
L
A
V
⚫ This function is used to releasethe space when not required.

N
E ⚫ Syntax:
P
A free(ptr);
L

40 11/14/2022 10:59AM
P
R
E DMA in C – free()
P
A #include<stdlib.h>
R
E #include <stdio.h>
D int main()
B {
Y int* ptr = malloc(10 * sizeof(*ptr));
S if (ptr != NULL)
U {
L
A *(ptr + 2) = 50;
V printf("Valueof the 3rd integer is %d\ n",*(ptr + 2));
N }
E //*(ptr + 2) = 50;
P
A free(ptr);
L printf("Valueof the 3rdinteger is %d",*(ptr + 2));
41
} 11/14/2022 10:59AM
P
R
E Algorithm
P
A ⚫ Algorithm is a finite set of instructions or logic, written in order,to
R
E accomplish a certain predefined task.
D

B ⚫ Algorithm is not the complete code or program, it is just the core logic
Y (solution) of a problem, which can be expressed either as an informal high
S level description as pseudocode or usinga flowchart.
U
L
A ⚫ Every algorithmmust satisfy the following properties:
V
⚫ Input
N ⚫ Output
E ⚫ Definiteness
P
A ⚫ Finiteness
L ⚫ Correctness
⚫ Effectiveness 11/14/2022 10:59AM
42
P
R
E Algorithm
P
A ⚫ Input
R ⚫ There should be 0 or more inputs suppliedexternally to the algorithm.
E
D
⚫ Output
B ⚫ There should beat least 1 output obtained.
Y

S ⚫ Definiteness
U ⚫ Every step of the algorithmshould be clearand well defined.
L
A ⚫ Finiteness
V
⚫ The algorithm should havefinite numberof steps.
N
E ⚫ Correctness
P ⚫ Every step of the algorithmmust generate a correct output.
A
L
⚫ Effectiveness
43 ⚫ Each step must be carried out in a finite time. 11/14/2022 10:59AM
P
R
E Algorithm
P
A
R
⚫ Design an algorithm to add two numbers and display the result:
E ⚫ Start
D
⚫ Declare three integers num1,num2,and num3
B
Y ⚫ Define valuesof num1 and num2
⚫ Add values of num1 and num2 and store the value to num3
S
U ⚫ Print num3
L
A ⚫ Stop
V

N
E ⚫ An algorithm is said to beefficient and fast, it takes less time to
P execute and consumes less memory space.
A
L

44 11/14/2022 10:59AM
P
R
E Algorithm Complexity
P
A ⚫ Analyzing analgorithm meansdetermining the amountofresources
R
E (such as time and memory) neededto execute it.
D

B ⚫ Algorithms are generally designed to work with an arbitrary number

Y
of inputs, so the efficiency or complexity of an algorithm is stated in
S terms of time complexity and spacecomplexity.
U
L
A
V ⚫ The time complexity of an algorithm is basically the running time of
a program as a function of the input size.
N
E
P
A ⚫ Similarly, the space complexity of an algorithm is the amount
L of computer memorythat is required during the programexecution as
45
afunction of the input size. 11/14/2022 10:59AM
P
R
E Time Complexity of an Algorithm
P
A
R
⚫ Timecomplexityisdefinedas the number of steps required to solve
E the entire problem using someefficient algorithm.
D

B
Y 𝑇 𝑃 = 𝑐 + 𝑡𝑝 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒
S
U Where, 𝑇 𝑃 is the time complexity of the program 𝑃, 𝑐 is the compile
L
A time, and 𝑡𝑝 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒 is the run time.
V

N
E
P
A
L

45 11/14/2022 10:59AM
P
R
E Time Complexity of an Algorithm
P
A
R
⚫ Algorithm:
E
D
sum(a[],n) // 0
B
Y { // 0
s=0; // 1
S
U for i=1 to n // n+1
L
A s=s+a[i]; // n
V // 1
return s;
N } // 0
E
P
A
L Time Complexity = 1+n+1+n+1 = 2n+3

46 11/14/2022 10:59AM
P
R
E Space Complexity of an Algorithm
P
A
R
⚫ Space complexity is defined as the amount of space and memory
E requiredby an algorithm to solve the problem.
D

B
Y 𝑆 𝑃 = 𝑐 + 𝑠𝑝 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒
S
U Where, 𝑆 𝑃 is the spacecomplexityof the program 𝑃, 𝑐 is the fixed
L
A part,and 𝑠𝑝 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒 is the variable part.
V

N
E
P
A
L

47 11/14/2022 10:59AM
P
R
E Space Complexity of an Algorithm
P
A
R
⚫ Algorithm:
E
D
abc(a,b,c)
B
Y {
return a+b+b*c+(a+b+c)/(a+b)+40;
S
U }
L
A
V
Forevery instance,only 3 variables are required to store variables a,b,and
N c.
E
P
A Total Space Complexity = 1+1+1 = 3
L

48 11/14/2022 10:59AM
P
R
E Space Complexity of an Algorithm
P
A
R
⚫ Algorithm:
E
D
sum(a[],n)
B
Y {
s=0;
S
U for i=1 to n
L
A s=s+a[i];
V
return s;
N }
E
P Tostorea[] = n space; to storei, s, &n = 3 space
A
L
Space Complexity = n+3
50 11/14/2022 10:59AM
P
R
E Algorithm Complexity
P
A
R
⚫ Worst-case running time
E ⚫ The worst case running time of an algorithm is an upper bound on the
D
running time for any input.
B
Y
⚫ Therefore, havingthe knowledgeofworstcaserunning timegivesusan
S
U assurance that the algorithm will never gobeyond this time limit.
L
A
V

N
E
P
A
L

50 11/14/2022 10:59AM
P
R
E Algorithm Complexity
P
A
R
⚫ Average-case running time
E ⚫ The average case running time of an algorithm is an estimate of the
D
running time for an‘average’input.
B
Y
⚫ It specifiestheexpectedbehaviorofthealgorithmwhentheinput is
S
U randomly drawnfrom a given distribution.
L
A
V ⚫ Averagecase running time assumes that all inputsofagivensizeare
N
equally likely.
E
P
A
L

51 11/14/2022 10:59AM
P
R
E Algorithm Complexity
P
A
R
⚫ Best-case running time
E ⚫ The term best case performance is used to analyze an algorithm under
D
optimal conditions.
B
Y
⚫ Forexample,the best casefor a simple linear searchon an arrayoccurs
S
U when the desired element is the first in the list.
L
A
V

N
E
P
A
L

52 11/14/2022 10:59AM
P
R
E Asymptotic Notation
P
A ⚫ Asymptotic analysis of an algorithm refers defining the
R
E to mathematical framing of its run-time
D performance.
B ⚫ Asymptotic analysis is input bound; i.e. if there is no input to the
Y
algorithm, it is concluded to work in a constraint time. Other than
S the“input”all other factorsareconsidered constant.
U
L
A
V ⚫ Asymptotic analysis refers to computing the running time of any
operation in mathematical units of computation.
N
E
P
A ⚫ Therunning timeofalgorithm isdefinedasthetimeneededbyan
L algorithm in orderto deliver its output whenpresentedwith logical
54
input. 11/14/2022 10:59AM
P
R
E Asymptotic Notation
P
A
R
⚫ In asymptotic notation,algorithm is treated as a function.
E
D

B
⚫ Usually,the time required by an algorithm falls under three types:
Y

S ⚫ Best Case – minimum time required for programexecution

U
L
A ⚫ AverageCase – averagetimerequired for programexecution
V

N
E ⚫ Worst Case – maximum timerequired for programexecution
P
A
L

54 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
⚫ Followingarethe commonly usedasymptoticnotationsto calculate
E the running time complexity of an algorithm:
D

B
Y ⚫ 𝑂 Notation (Big – ONotation)

S
U ⚫ Ω Notation (Big – Omega Notation)
L
A
V
⚫ 𝜃 Notation (Theta Notation)
N
E
P
A
L

55 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D

B
⚫ To analyzecode performance
Y

S ⚫ For comparing morethan one approachesto solve a problem

U
L
A
V ⚫ To help find areas to improve/fix bugs in functions which makes the
N system slow.
E
P
A
L

56 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A Big – O Notation (𝑶 Notation)
R
E
D
⚫ Forexample:writeafunction to calculatesumof all numbersfrom1 to
B that number (n) including itself.
Y addUpTo(n) addUpTo(n)
S { {
U
L let sum = 0; return 0.5 * n * (n+1) ;
A
V
for (i = 1;i <= n;i++) }
sum += i;
N
E return sum;
P
A }
L ⚫ Now,which one is better in terms of execution speed (time complexity) and
58
memory efficient (space complexity)? 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D
⚫ Number of Operations: addUpTo(n)
B
Y ⚫ Assignment = 1 + 1 + n + n {
S ⚫ Addition = n + n let sum = 0;
U
L
⚫ Comparison = n for (i = 1;i <= n;i++)
A sum += i;
V
⚫ Total = 5n + 2 return sum;
N
E }
P
A
L

58 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D
⚫ Number of Operations: addUpTo(n)
B
Y ⚫ Addition= 1 {
S ⚫ Multiplication = 2 return 0.5 * n * (n+1) ;
U
L }
A ⚫ Total = 0n + 3 (only 3)
V

N
E
P
A
L

59 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D

B
⚫ It formalizes the fuzzy counting method.
Y

S ⚫ We say,an algorithm is 𝑂 𝑓 𝑛 if the numberof operationsthe

U
L computer has to do is less than a constant time 𝑓 𝑛 , as 𝑛 increases.
A
V Where,
N
𝑓 𝑛 could belinear; 𝑓 𝑛 =𝑛
E 𝑓 𝑛 could bequadratic; 𝑓 𝑛 = 𝑛2
P
A 𝑓 𝑛 could beconstant; 𝑓 𝑛 =1
L
𝑓 𝑛 could besomething different !!
60 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D
⚫ Big – Orule:
B
Y ⚫ Smaller termsdoesn’t matter !!
S
U
L
A
V

N
E
P
A
L

61 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D
⚫ Number of Operations: addUpTo(n)
B
Y ⚫ Assignment = 1 + 1 + n + n {
S ⚫ Addition = n + n let sum = 0;
U
L
⚫ Comparison = n for (i = 1;i <= n;i++)
A sum += i;
V
⚫ Total = 5n + 2 return sum;
N
E }
P
A
L
TIME COMPLEXITY = 𝑶 𝒏
62 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D
⚫ Number of Operations: addUpTo(n)
B
Y ⚫ Addition= 1 {
S ⚫ Multiplication = 2 return 0.5 * n * (n+1) ;
U
L }
A ⚫ Total = 0n + 3 (only 3)
V

N
E
P
A TIME COMPLEXITY = 𝑶 𝟏
L

63 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D ⚫ Big – O notation represents the upper
bound of the running time of an
B algorithm.
Y

S ⚫ Thus, it gives the worst-case

U complexity of an algorithm.
L
A
V ⚫𝑓 𝑛 =𝑂 𝑔 𝑛 is read as f of n
is the Big – Oof g of n.
N
E
P ⚫ 𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist
A positiveconstants 𝑐 and 𝑛0 suchthat
L 0 ≤ 𝑓 𝑛 ≤ 𝑐. 𝑔(𝑛) for all 𝑛 ≥
𝑛0}
64 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – O Notation (𝑶 Notation)
E
D

B
⚫ Example:Suppose 𝑓 𝑛 = 4𝑛2 + 5𝑛 + 3. Is 𝑓 𝑛 is 𝑂 𝑛2 ?
Y

S ⚫ Solution:
U
L 𝑓 𝑛 = 4𝑛2 + 5𝑛 + 3
A
V
≤ 4𝑛2 + 5𝑛 + 3, 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑛 > 0
≤ 4𝑛2 + 5𝑛2 + 3𝑛2 , 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑛 > 1
N
E
≤ 12𝑛2 , 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑛 > 1
P 4𝑛2 + 5𝑛 + 3 ≤ 12𝑛2
A
L
Hence,𝒇 𝒏 = 𝑶 𝒏𝟐
65 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – Omega Notation (Big Ω Notation)
E
D ⚫ Big – Omega notation represents the
lower bound of the running time of an
B algorithm.
Y

S ⚫ Thus, it gives the best-case complexity

U of an algorithm.
L
A
V ⚫𝑓 𝑛 =Ω 𝑔 𝑛 is read as f of n
is the Omega of gof n.
N
E
P ⚫ Ω(𝑔(𝑛)) = {𝑓(𝑛): there exist
A positiveconstants 𝑐 and 𝑛0 suchthat
L 0 ≥ 𝑓 𝑛 ≥ 𝑐. 𝑔(𝑛) for all 𝑛 ≥
𝑛0}
66 11/14/2022 10:59AM
P
R
E Types of Asymptotic Notation
P
A
R
Big – Theta Notation (Big 𝜃 Notation)
E
D ⚫ Big – Theta notation represents both
lower and upper bound of the running
B timeof an algorithm.
Y

S ⚫ Thus, it gives the average-case

U complexity of an algorithm.
L
A
V ⚫𝑓 𝑛 =𝜃 𝑔 𝑛 is read as f of n
is the theta of gof n.
N
E
P ⚫ 𝜃(𝑔(𝑛)) = {𝑓(𝑛): there exist
A positive constants 𝑐1, 𝑐2, and 𝑛0
L such that 𝑐1. 𝑔 𝑛 ≤ 𝑓 𝑛 ≤
𝑐2 . 𝑔(𝑛) for all 𝑛 ≥ 𝑛0 }
67 11/14/2022 10:59AM
P
R
E Common Asymptotic Notation
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

68 11/14/2022 10:59AM
P
R
E
P
A
R
E
D

B
Y

S STACK
U
L
A
V

N
E
P
A
L

69 11/14/2022 10:59AM
P
R
E Stack
P
A ⚫ Stack is a simple algorithm that works based on a rule Last In First Out
R (LIFO).
E
D
⚫ Elements are added to and removedfrom the top of the stack calledTOP.
B
Y
⚫ The last element addedis the first to beremoved.
S
U
L
⚫ Push() function is used to insertnew elements into the stack and Pop()
A
V function is usedto remove an element from the stack.
N
E ⚫ Both insertion and removal are allowed at only one end of stack.i.e.Top.
P
A
L ⚫ Stack is said to bein Overflowstate whenit is completely full and is said
to bein Underflowstate if it is completely empty.
70 11/14/2022 10:59AM
P
R
E Stack
P
A ⚫ Consider an example of plates stacked overoneanother in the reception party.
R
E
D ⚫ In suchastack, only the top plate is visible andaccessibleto the user,all other
plates remain hidden.
B
Y
⚫ As new plates are added (pushed), each new plate becomes the top of the stack,
S and hideseachplate below.
U
L
A ⚫ Asplates areremoved(popped) from the stack,they can beused,and secondplate
V becomesthe topof the stack.
N
E ⚫ Twoimportant principles areillustrated bythis metaphor.
P ⚫ Thelast in first out principle
A ⚫ Contents of the stack arehidden,only the top plate is visible – to seewhat is onthe
L third plate, the first and secondplateswill haveto beremoved.
71 11/14/2022 10:59AM
P
R
E Stack
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

72 11/14/2022 10:59AM
P
R
E Stack Operations
P
A
R
⚫ Creation Operation ⚫ isEmpty Operation
E ⚫ To create an empty stack ⚫ To check whether the stack is
D
empty or not
B
Y ⚫ Push Operation
⚫ Toaddelements at the top of a ⚫ isFull Operation
S
stack
U ⚫ To check whether the stack is
L
A full or not
V ⚫ Pop Operation
N ⚫ To removeor delete the top element
E fromthe stack ⚫ Size Operation
P
A
⚫ To check the sizeof stack
L
⚫ Traverse Operation
76 ⚫ To display all the elements of stack 11/14/2022 10:59AM
P
R
E Stack as an ADT
P
A ⚫ Astack of elements of type T is a finite sequence of elements of T togetherwith the
R operations:
E ⚫ createEmptyStack(S)
D ⚫ Createor makestack S asan empty stack.

B
⚫ push(S,x)
Y
⚫ Insert x at oneendof thestack S,calledtop.

S
U ⚫ top(S)
L ⚫ If stack S is notempty;thenretrieve the element at its top.
A
V ⚫ pop(S)
⚫ If stack S is not empty;thendeletethe element at its top.
N
E
⚫ isFull(S)
P
⚫ Determine if S is full ornot.Return true if S is full;return falseotherwise.
A
L
⚫ isEmpty(S)
77 ⚫ Determine if S is empty or not.Return true if S is empty;return falseotherwise. 11/14/2022 10:59AM
P
R
E Stack Implementation
P
A
R
Creation of Stack
E
D

B
Y #define CAPACITY 5
S
U
L int top = -1;
A
V

N int initStack[CAPACITY];
E
P
A
L

75 11/14/2022 10:59AM
P
R
E Stack Implementation
P
A
R
push operation
E
D void push(int element)
B {
Y if(isFull())
{
S
U
printf(“Stack is full”);
L }
A else
V
{
N top++;
E initStack[top]=element;
P printf(“%d”inserted\ n”,element);
A }
L
}
76 11/14/2022 10:59AM
P
R
E Stack Implementation
P
A
R
isFull Operation
E
D
int isFull()
B
Y {
if(top == CAPACITY- 1)
S
U {
L return 1;
A
V }
else
N
E {
P return 0;
A
L }
} 11/14/2022 10:59AM
80
P
R
E Stack Implementation
P
A
R
pop operation
E
D int pop()
B {
Y int element;
if(isEmpty())
S
U
{
L return 0;
A }
V else
N {
E return initStack[top--];
P }
A
L
return top;
}
81 11/14/2022 10:59AM
P
R
E Stack Implementation
P
A
R
isEmpty Operation
E
D
int isEmpty()
B
Y {
if(top == -1)
S
U {
L return 1;
A
V }
else
N
E {
P return 0;
A
L }
} 11/14/2022 10:59AM
79
P
R
E Stack Implementation
P
A
R
peek operation
E
D
int peek()
B
Y {
if(isEmpty())
S
U {
L return 0;
A
V }
else
N
E {
P return initStack[top];
A
L }
} 11/14/2022 10:59AM
80
P
R
E Stack Implementation
P
A
R
traverse operation
E
D void traverse()
{
B
Y
int i;
if(isEmpty())
S {
U printf(“NoElements\ n”);
L }
A else
V
{
N printf(“Stack Elements are:\n”);
E for(i=0;i<=top;i++)
P {
A printf(“%d\n”,initStack[i]);
L }
}
84 11/14/2022 10:59AM
}
P
R
E Stack Application
P
A ⚫ Can beused forexpressionevaluation. ⚫ To keep the page-visited history in a
R webbrowser.
E
D ⚫ Can be used to check parenthesis
⚫ To perform the undo sequence in
B matching in an expression.
a text editor.
Y

S
⚫ Can be used for conversion from one ⚫ Usedin recursion
U formof expressionto another.
L
A ⚫ To pass the parameters between
V ⚫ Can beused for memorymanagement. the functionsin a Cprogram.
N
E ⚫ Stack data structures are used in ⚫ Can be used as an auxiliary data
P backtracking problems. structure for implementing algorithms
A
L
⚫ Can be used as a component of other
⚫ To evaluate the expressions (prefix, data structures.
86 11/14/2022 10:59AM
postfix).
P
R
E Arithmetic Expression
P
A
R
⚫ Infix Notation
E ⚫ The expression which is in normal format; i.e. the operator lies in
D
between the operand.
B
⚫ For example:𝐴 + 𝐵, 𝐴 ∗ 𝐵, 𝐴/𝐵, etc.
Y

S
U ⚫ Prefix Notation or Polish Notation
L
A ⚫ The operatorcomesfirst followedbythe operands.
V
⚫ For example:+𝐴𝐵,∗ 𝐴𝐵,/𝐴𝐵, etc.
N
E
P
A
⚫ Postfix (Suffix) Notation or Reverse Polish Notation
L ⚫ The operand comesfirst followedby the operator.
87 ⚫ For example:𝐴𝐵+, 𝐴𝐵 ∗, 𝐴𝐵/, etc. 11/14/2022 10:59AM
P
R
E Precedence Level (Priorities)
P
A
R
⚫ Highest – Exponentiation (^)
E
D

B
⚫ Next Highest – Multiplication (*) and Division (/)
Y

S ⚫ Lowest – Addition (+) and Subtraction (-)

U
L
A
V

N
E
P
A
L

84 11/14/2022 10:59AM
P
R
E
Algorithm – Infix to Postfix Conversion
P
A ⚫ Scaninput string from left to right character by character.
R
E ⚫ If the characteris an operand,put it into output stack.
D
⚫ If the character is an operator and operator'sstack is empty,pushoperator into operators' stack.
B
Y
⚫ If the operator'sstack is not empty,there maybefollowingpossibilities:
⚫ If the precedenceof scanned operator is greater than the top most operator of operator's stack,push this operator
S intooperand's stack.
U
L ⚫ If the precedence of scanned operator is less than or equal to the top most operator of operator's stack, pop the
A operators from operand's stack until we find a low precedence operator than the scanned character. Never pop out (
V '(' ) or( ')' ) whatevermaybethe precedencelevel of scannedcharacter.

⚫ If the characteris opening round bracket( '(' ),push it into operator's stack.
N
E
⚫ If the character is closing round bracket ( ')' ), pop out operators from operator's stack untill we find an opening
P bracket('(' ).
A
L ⚫ Nowpop out all the remainingoperatorsfromthe operator's stack and push into output stack.

85 11/14/2022 10:59AM
P
R
E Infix to Postfix Conversion
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

86 11/14/2022 10:59AM
P
R
E
Algorithm – Infix to Prefix Conversion
P
A
R
⚫ Reversethe infix expression.i.e.A+B*C will becomeC*B+A
E
D
⚫ Obtain the “nearly”postfix expressionof the modified expression.i.e.
B
Y CB*A+
S
U
L ⚫ Reverse the postfix expression. Hence in our example, prefix is
A
V
+A*BC
N
E
P
A
L

87 11/14/2022 10:59AM
P
R
E Infix to Prefix Conversion
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

88 11/14/2022 10:59AM
P
R
E
Algorithm – Postfix to Infix Conversion
P
A ⚫ Scan the given postfix expressionfrom left to right character by character.
R
E
D
⚫ If the character is an operand,push it into the stack.
B
Y
⚫ But if the character is an operator,popthe top two values from stack.
S
U
L ⚫ Concatenate this operator with these two values (2nd
A
V top value+operator+1st top value) to get a new string.
N
E ⚫ Nowpushthis resulting string back into the stack.
P
A
L ⚫ Repeat this processuntil the end of postfix expression.Now the value in the
93
stack is the infixexpression. 11/14/2022 10:59AM
P
R
E Postfix to Infix Conversion
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

94 11/14/2022 10:59AM
P
R
E
Algorithm – Prefix to Infix Conversion
P
A ⚫ Scan the given prefix expressionfrom right to left character by character.
R
E
D
⚫ If the character is an operand,push it into the stack.
B
Y
⚫ But if the character is an operator,popthe top two values from stack.
S
U
L ⚫ Concatenate this operator with these two values (1st
A
V top value+operator+2nd top value) to get a new string.
N
E ⚫ Nowpushthis resulting string back into the stack.
P
A
L ⚫ Repeat this process until the end of prefix expression.Now the value in the
95
stack is the desired infix expression. 11/14/2022 10:59AM
P
R
E Prefix to Infix Conversion
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

92 11/14/2022 10:59AM
P
R
E Evaluation of Postfix Expression
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

93 11/14/2022 10:59AM
P
R
E Evaluation of Prefix Expression
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

94 11/14/2022 10:59AM
P
R
E
P
A
R
E
D

B
Y

S QUEUE
U
L
A
V

N
E
P
A
L

95 11/14/2022 10:59AM
P
R
E Queue
P
A ⚫ Queue is a linear list of elements in which deletion of an element can
R
E take place at one end, called the front and insertion can take place at
D the other end,called the rear.
B
Y
⚫ The first element in a queue will bethe first oneto beremovedfrom
S the list.
U
L
A
V ⚫ QueuesarealsocalledFIFO(First In FirstOut), i.e. the data item
stored first will beaccessedfirst.
N
E
P
A ⚫ The process to add an element into queue is called enqueue and the
L process of removal of an element from queue is called dequeue.
96 11/14/2022 10:59AM
P
R
E Queue Representation
P
A
R
⚫ In queue,weaccess both ends for different reasons.
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

97 11/14/2022 10:59AM
P
R
E Stack vs. Queue Representation
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

98 11/14/2022 10:59AM
P
R
E Queue Operations
P
A ⚫ enqueue operation ⚫ isFull operation
R ⚫ It inserts the element at the end
E ⚫ Return true when the queueis full.
D (rear) of the queue.

B
Y
⚫ dequeue operation ⚫ isEmpty operation
⚫ It deletes the element from the ⚫ Return true when the queueis empty.
S front of the queue.
U
L ⚫ viewQueue operation
A ⚫ getFront operation
V ⚫ It returns the element at the front ⚫ Viewall the elements in queue.

N
of the queue.
E
P
⚫ getRear operation
A
L ⚫ It returnsthe element at the end of
the queue.
99 11/14/2022 10:59AM
P
R
E Queue as an ADT
P
A ⚫ Aqueueq of type T is a finite sequenceof elements with the operations:
R ⚫ makeEmpty(q)
E
⚫ To make q as an empty queue
D

B ⚫ isEmpty(q)
Y ⚫ Tocheckwhether the queue qis empty ornot. Return true if qis empty and return false
otherwise.
S
U ⚫ isFull(q)
L ⚫ Tocheck whether the queueq is full ornot.Return true if q is full and returnfalse otherwise.
A
V
⚫ enqueue(q,x)
N ⚫ Toinsert an item x at the rearof the queue,if and only if q is not full.
E
P ⚫ dequeue(q)
A ⚫ Todelete an item from the front of the queueq if and only if q is not empty.
L
⚫ traverse(q)
106 11/14/2022 10:59AM
⚫ Toreadentire queue;i.e.display the content of the queue.
P
R
E Queue Implementation
P
A
R
Creation of Queue
E
D

B
#define CAPACITY 5
Y

S int queue[CAPACITY];
U
L
A
V int front = 0;
N
E
P int rear = 0;
A
L

107 11/14/2022 10:59AM

P
R
E Queue Implementation
P
A
R
Insertion Operation
E
D void insert()
B
{
Y if(rear == CAPACITY)
{
S
U printf("Queueis full");
L }
A
V
else
{
N int ele;
E
queue[rear] = ele;
P
A rear++;
L }

102 } 11/14/2022 10:59AM

P
R
E Queue Implementation
P
A
R
Deletion Operation
E
D void del()
{
B if(front == rear)
Y
{
printf("Queueis empty");
S
U }
L else
A {
V printf("%dis deleted\ n",queue[front]);
for(i=1;i<rear;i++)
N {
E queue[i-1]=queue[i];
P
}
A
rear--;
L
}
103 } 11/14/2022 10:59AM
P
R
E Queue Implementation
P
A
R
Traverse Operation
E
D void traverse()
B
{
Y if(front == rear)
{
S
U printf("Queueis empty");
L }
A
V
else
{
N for(i=front;i<rear;i++)
E
P
{
A printf("%d\t",queue[i]);
L }

110
} 11/14/2022 10:59AM
P
R
E Why Circular Queue?
P
A ⚫ Implementation of a linear queuebringsthe drawbackof memorywastage.
R
E
D ⚫ However, memory is a crucial resource that you should always protect
by analyzing all the implications while designing algorithms orsolutions.
B
Y
⚫ In the case of a linear queue, when the rear pointer reaches the maxSize of a
S queue, there might be a possibility that after certain number of dequeue()
U operations,it will createempty space at the start of a queue.
L
A
V ⚫ Toutilize the empty space,eachdequeue() operation needsto befollowed by
shifting all elementsoncetowardsfront.
N
E
P ⚫ This processwill result in moretimecomplexity.
A
L
⚫ Hence, experts introduced the concept of the circular queue to overcome this
112
limitation. 11/14/2022 10:59AM
P
R
E Circular Queue
P
A
R
⚫ Acircular queue is an extended version of a linear queue as it follows
E the First In First Out (FIFO) principle with the exception that it
D
connects the last node of a queue to its first by forming a circular
B link.
Y

S
U ⚫ It is also called a Ring Buffer.
L
A
V

N
E
P
A
L

106 11/14/2022 10:59AM

P
R
E Operations in Circular Queue
P
A
R
⚫ Front – used to get the starting element of the circular queue
E
D

B
⚫ Rear – used to get the end element of the circular queue
Y

S ⚫ enQueue(value) – used to insert a new value in the circular

U
L queue.This operation takes place fromthe end of the Queue.
A
V

N ⚫ deQueue() – usedto delete avalue fromthe circular queue. This

E operation takes place fromthe front of the Queue.
P
A
L

107 11/14/2022 10:59AM

P
R
E Operations in Circular Queue
P
A ⚫ enQueue(x) Operation:
R
E ⚫ Step 1:Checkif the queue is full ((𝑟𝑒𝑎𝑟 + 1)%𝑆𝐼𝑍𝐸 = 𝑓𝑟𝑜𝑛𝑡)
D

B ⚫ Step 2:If the queueis full,there will bean overflow error

S
U ⚫ Some of the applications of queuesrelated to computer science are:
L ⚫ Data getting transferredbetweenthe IO buffers (Input Output Buffers)
A
V ⚫ CPUscheduling and Disk scheduling
⚫ Managing shared resources between various processes
N
E ⚫ Jobscheduling algorithms
P ⚫ Round Robin scheduling
A
L ⚫ Recognizinga palindrome
⚫ Traffic system
123 11/14/2022 10:59AM
P
R
E Applications of Queue
P
A ⚫ Buffer in Computer systems
R
E ⚫ Computer systems supply a holding area for maintaining communication
D between two processes,two programs,oreven two systems.
⚫ This memoryareais also knownas a ring buffer.
B
Y

S
⚫ CPU Scheduling
U ⚫ In the Round-Robin Scheduling algorithm, a circular queue is utilized to
L maintain processesthat arein a ready state.
A
V

N
⚫ Traffic System
E ⚫ Circular queue is also utilized in traffic systems that are controlled
P by computers.
A
L ⚫ Each traffic light turns ON in a circular incrementation pattern in a constant
interval of time.
124 11/14/2022 10:59AM
P
R
E Priority Queue
P
A ⚫ Priority Queue is an ADT that
R
E
performs operations on data elements
D per their priority.

B
Y ⚫ The hospital emergency queue is an
ideal real-life example of a priority
S queue.
U
L
A ⚫ In this queue of patients, the patient
V
with the most critical situation is the
N first in a queue, and the patient who
E doesn’t need immediate medical
P attention will beat the last.
A
L
⚫ In this queue, the priority depends on
125 11/14/2022 10:59AM
the medical conditionof the patients.
P
R
E Priority Queue
P
A ⚫ It is highly used in
R
E sorting algorithms.
D

B ⚫ It behaves similar to a linear

Y
queue except for the fact that
S each element has some priority
U
L assigned to it.
A
V
⚫ The priority of element
N
E determines the order of removal
P in a queue; i.e. the element with
A
L higher priority will leave the
queue first, whereas the element
126 11/14/2022 10:59AM
with the lowest priority at last.
P
R
E Characteristics of Priority Queue
P
A
R
⚫ Every element has a certain priority assigned to it.
E
D

B
⚫ Every element of this queue must be comparable.
Y

S ⚫ It will delete the element with higher priority before the element with
U
L lower priority.
A
V

N ⚫ If multiple elements have the samepriority,it does their removal from

E the queue according to the FCFSprinciple.
P
A
L

119 11/14/2022 10:59AM

P
R
E Characteristics of Priority Queue
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

120 11/14/2022 10:59AM

P
R
E Types of Priority Queue
P
A
R
⚫ There are two types of priority queues based on the priority
E of elements:
D

B
Y ⚫ If the element with the smallest value has the highest priority,then that
priority queue is called the min priority queue (ascending).
S
U
L
A ⚫ If the element with the higher value hasthe highest priority,then that
V priority queue is called the max priority queue (descending).
N
E
P
A
L

121 11/14/2022 10:59AM

P
R
E Types of Priority Queue
P
A
R
⚫ Ascending Priority Queue
E ⚫ In this type of priority queue, elements can be inserted into any order
D
but only the smallest element can beremoved.
B
Y
⚫ In ascending order priority queue,a lower priority number is given asa
S
U higher priority in a priority.
L
A
V ⚫ Forexample, wetake the numbers arranged in an ascending order like 2,
N
6, 7, 10, 11; therefore, the smallest number, i.e. 2, is given as the
E highest priority in a priority queue.
P
A
L

122 11/14/2022 10:59AM

P
R
E Types of Priority Queue
P
A ⚫ Descending Priority Queue
R
E ⚫ In this type of priority queue,elements can be inserted into any order but only
D the largest element canberemoved.
B
Y ⚫ In descendingorder priorityqueue, a higher prioritynumber is given asa
higher priority in a priority.
S
U
L ⚫ Forexample, we take the numbers arranged in an descending order like 10, 9,
A 8, 7, 6; therefore, the smallest number, i.e. 10, is given as the highest priority
V
in a priority queue.
N
E
P
A
L

123 11/14/2022 10:59AM

P
R
E Operations in Priority Queue
P
A ⚫ Inserting the element in a Priority Queue
R
⚫ Step 1 – Askthe data and its priority fromthe user.
E
D
⚫ Step 2 – If front is equal to 0 and rearis equal to n-1,then queue is full.
B
Y
⚫ Step 3 – Else if front is equal to the -1 then queue is empty so we have to
S initializefront and rearwith 0.
U
L
⚫ Step 4 – Insert the data enteredby the user in queueusing rear.
A
V
⚫ Step 5 – If rear is equal to n-1 and front is not equal to 0, then there is empty
N space in queue before the front for using that space we will shift the elements
E of the queuewith the help of front and rear.
P
A
L ⚫ Step 6 – Insert the data in the queue beforeat the position wheregiven
priority is greater then priority of the element in queue.
124 11/14/2022 10:59AM
P
R
E Operations in Priority Queue
P
A
R
⚫ Deleting the element from a Priority Queue
E ⚫ Step 1 – Remove the element and the priority from the front of the
D
queue.
B
Y
⚫ Step 2 – Increase front with 1.
S
U
L
A
V

N
E
P
A
L

125 11/14/2022 10:59AM

P
R
E Application of Priority Queue
P
A ⚫ Priority queues areused in many computing applications.
R
E ⚫ For example, many operating systems uses a scheduling algorithm where
D the next process executed is the one with the shortest execution time or
B the highest priority.
Y

S ⚫ For another example, consider the problem of sorting a file of data

U representingpersons.
L
⚫ We can first add all the personsto a queue
A
V ⚫ Sort data in certain orderaccordingto the specified priority,and then
⚫ Removethem in turn from the priority queue(front element first).
N
E
P
A
⚫ Thebestapplication ofpriority queueisobservedin CPUscheduling. A
L short job is given higher priority over the longer one.
126 11/14/2022 10:59AM
P
R
E
P
A
R
E
D

B
Y

S Linear List
U
L
A
V

N
E
P
A
L

127 11/14/2022 10:59AM

P
R
E List
P
A
R
⚫ List is a sequential data structure in which addition and removalof
E data items can be donefrom any position.
D

B
Y ⚫ List is a collection of nodes.
S
U
L ⚫ The list is an:
A
V
⚫ Orderedsequenceof data items called elements
⚫ A1,A2,A3, … ,ANis a list of sizeN
N
E ⚫ Sizeof an empty list is 0
P
A ⚫ First elementA1 is called head
L ⚫ Last element AN is called tail
128 11/14/2022 10:59AM
P
R
E List Operations
P
A ⚫ Add – adds a new node
R
E
D ⚫ Set – update the contents of a node
B
Y ⚫ Remove– removesa node
S
U ⚫ isEmpty – reports whether the list is empty
L
A
V ⚫ isFull – reports whether the list is full
N
E ⚫ Initialize – creates/initializes the list
P
A
L ⚫ Destroy – deletes the contents of the list (may be implemented by re-
initializing the list) 11/14/2022 10:59AM
129
P
R
E List Operations
P
A
R
⚫ Initialize(L)
E ⚫ Creates a new empty list named L.
D

B
Y

S ⚫ Add(1, X, L)
U
L ⚫ Addsthe value X to list Lat position 1 (the start of the list is position
A 0),shifting subsequent elements up.
V

N
E ⚫ Set(2, Z, L)
P
A ⚫ Updates the values at position 2 to beZ.
L

130 11/14/2022 10:59AM

P
R
E List Operations
P
A
R
⚫ Remove(Z, L)
E ⚫ Removes the nodewith valueZ.
D

B
Y

S ⚫ Get(2, L)
U
L ⚫ Returns the valueof the third node. i.e. C
A
V

N
E
P
⚫ IndexOf(X, L)
A ⚫ Returns the index of the nodewith value X. i.e.1
L

131 11/14/2022 10:59AM

P
R
E Illustration / Example
P
A
S.N. Operations List’s Contents ReturnValue
R
E 1. Initialize(L) <empty> -
D
2. Add(0,A, L) A -
B 3. Add(0, B,L) BA -
Y
4. Add(1, C, L) BCA -
S 5. Set(1, N, L) BNA -
U
6. Add(1, D, L) BDNA -
L
A 7. Remove(A, L) BDN A
V
8. Set(3, I, L) BDNI -
N 9. Remove(D, L) BNI D
E
P
10. Remove(N, L) BI N
A
L

132 11/14/2022 10:59AM

P
R
E List as an ADT
P
A
R
⚫ Weshould beable to store a given number of elements of a given data
E type.
D

B
Y ⚫ Weshould beable to write/modify elements at any position.
S
U
L ⚫ Weshould beable to readelements at any position.
A
V

N An array gives all these features.

E
P
A
L

133 11/14/2022 10:59AM

P
R
E List as an ADT
P
A ⚫ My list can beempty when sizeis zero.
R
E
D ⚫ I should beable to insert elementsin any position of the list.
B
Y ⚫ I should beable to remove elementsfrom any position of the list.
S
U ⚫ I should beable to count the number of elementsfrom the list.
L
A
V ⚫ I should beable to read ormodify elementsat any position of the list.
N
E ⚫ I should beable to specify data type of myelementsof the list.
P
A
L An array still does this all but with some complexities !!
134 11/14/2022 10:59AM
P
R
E Static List Structure
P
A
R
⚫ Static implementation of list stores the items in an array.
E
D
⚫ The position of element is given by an index starting from 0 to 𝑛 −
B
Y 1, where 𝑛 is the number of elements.
S
U
L ⚫ Static list is of fixed size.
A
V

N
E
P
A
L

135 11/14/2022 10:59AM

P
R
E Static List Structure
P
A ⚫ The different operations within the static list and their complexities areas
R
E follows:
D
⚫ Givenan index,the element at that position can beaccessedat constant time,
B without any relation with the sizeof list.
Y

S ⚫ Toadd an element at the end of the list,it canalso bedone at constant time.
U
L
A ⚫ Toaddanelementat anyother position involves shifting up one position of all
V
the subsequentelements,sothe time complexity depends on the size of the list.
N
E
P ⚫ To remove an element from the list, all the subsequent elements should be
A shifted down one position, so the time complexity depends on the size of the
L
list.
136 11/14/2022 10:59AM
P
R
E Dynamic List Structure
P
A
R
⚫ In dynamicdatastructure, thesizeofthestructure is not fixed and
E can bemodified during the operations performedon it.
D

B
Y ⚫ Dynamic data structures are designed to facilitate change of data
S structures in the run time.
U
L
A
V
⚫ Example of dynamic data structure is a Linked List.

N
E
P
A
L

137 11/14/2022 10:59AM

P
R
E Array Implementation of List
P
A
R
⚫ Advantages ofArray Implementation
E ⚫ Variables arestored in contiguous memory.
D
⚫ Easy to handle data.
B
Y

S ⚫ Limitations ofArray Implementation

U
L
⚫ Hard to add/removeelements
A ⚫ Can not bedynamically resized
V
⚫ Memory loss
N
E
P
A
L

138 11/14/2022 10:59AM

P
R
E Linked List
P
A
R
⚫ It is also a linear data structure.
E
D
⚫ It doesn’t store the elements contiguously in location,instead it stores
B
Y the elements and links them using pointers.
S
U
L ⚫ A linked list is a linear collection of data elements, called nodes,
A
V
wherethe linear order is given by meansof pointers.
N
E
P
A
L

139 11/14/2022 10:59AM

P
R
E Linked List
P
A
R
⚫ Each node is divided into twoparts:
E ⚫ The first part containsthe information of the element
D

B
Y ⚫ The secondpart contains the addressof the next nodein the list.

S
U
L
A
V

N
E
P
A
L

140 11/14/2022 10:59AM

P
R
E Linked List
P
A
R
⚫ Linkedlist canbevisualized asachainof nodes, whereeverynode
E points to the next node.
D

B
Y ⚫ The first node is called head.
S
U
L ⚫ If the linked list is empty, then value of head is NULL.
A
V

N
E
P
A
L

141 11/14/2022 10:59AM

P
R
E Linked List
P
A
R
E
D

B
Y

S ⚫ Asper the above illustration,following are the important points to be

U
L considered:
A
V
⚫ Linked List containsa link element called first.
⚫ Each link carries a data field(s) and a link field called next.
N
E ⚫ Eachlink is linked with its next link using its next link.
P
A ⚫ Last link carries a link as null to markthe end of the list.
L

142 11/14/2022 10:59AM

P
R
E Introduction to Linked List ADT
P
A
R
⚫ Data structures can be added to or removed from the linked list
E during execution.
D

B
Y

S
U
L ⚫ Linked Lists can grow and shrink as needed, unlike arrays, which
A
V
have a fixed size. Linked List can insert a node between other nodes
easily.
N
E
P
A
L

143 11/14/2022 10:59AM

P
R
E Implementation of Linked List
P
A
R
⚫ Structure is usedto define anodewhichis acollection of data and
E addressto the next node.
D

B
Y ⚫ Address of next node can be stored in pointer type variable.
S
U
L ⚫ For example:
A
V
struct node
{
N
E int data;
P
A struct node*next;
L } nodes;
144 11/14/2022 10:59AM
P
R
E Implementation of Linked List
P
A
R
⚫ Memory allocation for node using malloc( ) function:
E node*p;
D
p = (node *) malloc(sizeof(node));
B
Y p -> data = 40;
p ->next = NULL;
S
U
L
A
V

N
E ⚫ It is assumedthat,type of data stored in eachnode is of integer type.
P
A
L

145 11/14/2022 10:59AM

P
R
E Why Linked List?
P
A
R
⚫ Arrayscanbe usedto store lineardataof similar types, but arrays
E have following limitations:
D

B
Y
⚫ The size of the arrays is fixed. So, we must know the upper limit on the
number of elements in advance. Also, generally, the allocated memory is
S
U
equal to the upper limit irrespectiveof the usage.
L
A
V ⚫ Inserting new element in an array of elements is expensive, because room
N
has to be created for the new elements and to create room existing
E elements haveto beshifted.
P
A
L

146 11/14/2022 10:59AM

P
R
E Why Linked List?
P
A ⚫ Forexample, in asystemif wemaintain asortedlist of IDsin an
R
E array id[ ].
D id[ ] = [1000, 1010, 1050, 2000, 2040]
B
Y
⚫ And if wewant to insert a new ID 1005, then to maintain the sorted
S order, we have to move all the elements after 1000 (excluding
U
L 1000).
A
V
⚫ Deletion is also expensive with arrays until unless some special
N
E techniques areused.
P
A
L ⚫ Forexample,to delete 1010 in id[ ],everything after 1010 has to be
184 moved. 11/14/2022 10:59AM
P
R
E Linked List
P
A
R
⚫ Advantages of Linked List over Arrays:
E ⚫ Dynamic size
D
⚫ Easeof insertion/deletion
B
Y

S ⚫ Drawbacks of Linked List

U
L
⚫ Random access is not allowed. We have to access elements sequentially
A starting from the first node. So, we cannot do binary search with linked
V
list.
N ⚫ Extra memory space for a pointer is required with each element of the
E
P list.
A
L

185 11/14/2022 10:59AM

P
R
E Array vs. Linked List
P
A Array Linked List
R
E Array is a collection of elements having samedata Linked List is an ordered collection of elements
D type with common name. which are connected by links/pointers.
In linked list, elements can be stored at any
B In array,elements are stored in consecutivemanner
Y
available place as address of node is stored in
in memory.
previous node.
S Insertion &deletion takes more time in array as
U Insertion and deletion are fast and easy
elements are stored in consecutive memory
L in linked list asonly value of pointer is needed
locations.
A to change.
V In array, memory is allocated at compile In linked list,memoryis allocated at run time.i.e.
time. i.e. static memory allocation. dynamic memory allocation.
N
E Array can be single dimensional, two
Linked list can besingly,doubly,orcircular.
P dimensional, or multidimensional.
A In array, each element is independent, no
L In linked list, location or address of elements is
connection with previous element or with its
stored in the link part of previouselement/node.
location. 11/14/2022 10:59
AM
P
R
E Application of Linked List
P
A
R
⚫ Linked list are frequently used to implement other data structures like
E tree,graphs, and heaps.
D

B
Y ⚫ Linked list can beused to create dynamic stack and queue which can
S growand shrink at run time.
U
L
A
V
⚫ Linked list can beused to store and process the polynomials
⚫ Coefficientand powerstored as data; and link pointer points to next
N
E termin the polynomial.
P
A
L

150 11/14/2022 10:59AM

P
R
E Primitive Operation of Linked List
P
A ⚫ Creating LinkedList
R
E
D ⚫ TraversingLinkedList

B ⚫ Printing LinkedList
Y

S ⚫ CountingNumberof Nodesin LinkedList

U
L
⚫ SearchingElements in LinkedList
A
V
⚫ Concatenating two LinkedLists
N
E
P ⚫ Inserting element into Linked List (Start, end,and specificposition)
A
L ⚫ Deleting elements fromLinked List (Start, end,and specificposition)
151 11/14/2022 10:59AM
P
R
E Primitive Operation of Linked List
P
A Create Function Display Function
R
E void create() void display()
D { {
struct node *temp,*ptr; struct node *ptr;
printf("nEnter the data value for the node:t"); if(start==NULL)
B
Y scanf("%d",&temp->info); {
temp->next=NULL; printf("nList is empty:n");
S if(start==NULL) return;
U { }
L start=temp; else
A } {
V else ptr=start;
{ printf("nThe List elements are:n");
N ptr=start; while(ptr!=NULL)
E while(ptr->next!=NULL) {
P { printf("%dt",ptr->info );
A ptr=ptr->next; ptr=ptr->next ;
L } }
ptr->next=temp; }
189 } } 11/14/2022 10:59AM
}
P
R
E Primitive Operation of Linked List
P
A Delete Function

R void delete_pos()
E { else
D int i,pos;
{
struct node*temp,*ptr;
B if(start==NULL) ptr=start;
Y { for(i=0;i<pos;i++) { temp=ptr;ptr=ptr->next ;
printf("nThe List is Empty:n"); if(ptr==NULL)
S exit(0);
{
U }
printf("nPosition not Found:n");
else
L
{ return;
A printf("nEnter the positionof the node to bedeleted:t");
V scanf("%d",&pos);
}
if(pos==0) }
N { temp->next =ptr->next ;
E ptr=start;
printf("nThe deletedelement is:%dt",ptr->info );
P start=start->next ;
free(ptr);
A printf("nThe deleted elementis:%dt",ptr->info);
L free(ptr); }
} }
190 } 11/14/2022 10:59AM
P
R
E Types of Linked List
P
A
R
⚫ Singly Linked List
E
D

B
⚫ Doubly Linked List
Y

S ⚫ Circular Linked List

U
L ⚫ Singly Circular Linked List
A
V ⚫ Doubly Circular Linked List

N
E
P
A
L

154 11/14/2022 10:59AM

P
R
E Singly Linked List
P
A ⚫ In any single linked list,the individual element is called as“node”.
R
E
D ⚫ Every“node”contains twofields;data and next.

B
Y ⚫ The data field is used to storeactual value of that node and the next field is used
to storethe addressof the next node in the sequence.
S
U
L ⚫ In this type of linked list,the link points to the next node in the list and the last
A nodehasa NULLpointer.
V

N
E
P
A typedef struct node
L { int data;
struct node*next;
193 11/14/2022 10:59AM
} node;
P
R
E Operation of Singly Linked List
P
A ⚫ To create a new node, we use the malloc function to dynamically
R
E allocate memory for the newnode.
D

B ⚫ After creating the node,wecan store the newitem in the node using
Y
a pointer to that node.
S
U
L ⚫ Steps requiredto create a node and storing an item:
A
V NodeType *p;
N
p = (NodeType*) malloc(sizeof(NodeType));
E p -> info= 50;
P
A p -> next = NULL;
L

194
Note that p is not a node;instead it is a pointer to a node.11/14/2022 10:59AM
P
R
E Operation of Singly Linked List
P
A
R
⚫ The getNode function:
E ⚫ We can define a function getNode() to allocate the memory for a node
D
dynamically.
B
Y
⚫ It is user-definedfunctionthat return apointer tothenewlycreated
S
U node.
L
A
V NodeType *getNode()
{ NodeType *p;
N
E
p = (NodeType*) malloc(sizeof(NodeType));
P return (p);
A
}
L

157 11/14/2022 10:59AM

P
R
E Operation of Singly Linked List
P
A
R
⚫ Creating the empty list:
E
D
voidcreateEmptyList(NodeType *head)
B {
Y
head = NULL;
S }
U
L
A
V

N
E
P
A
L

158 11/14/2022 10:59AM

P
R
E Operation of Singly Linked List
P
A
R
⚫ Inserting Nodes:
E ⚫ To insert an element or a node in a linked list, the following three
D
thingsneeds to bedone:
B ⚫ Allocating a node
Y
⚫ Assigninga data to infofield of the node
S ⚫ Adjusting a pointerand a newnodemaybeinserted
U
L
A
V
⚫ In a linked list, the insertion operation can beperformedin three ways.
They are:
N
⚫ Inserting at beginningof the list
E
P ⚫ Inserting at end of the list
A
⚫ Inserting at specific location in the list
L

159 11/14/2022 10:59AM

P
R
E Operation of Singly Linked List
P
A
R
⚫ Inserting Nodes:
E ⚫ We can use the following steps to insert a new node at beginning of the
D
single linked list.
B ⚫ Create a newNode with given value
Y

S ⚫ Check whether list is Empty (head == NULL)

U
L
A ⚫ If it is Empty,then set newNode -> next = NULL and head = newNode
V

N ⚫ If it is Not Empty,then set newNode ->next = head and head = newNode

E
P
A
L

160 11/14/2022 10:59AM

P
R
E Operation of Singly Linked List
P
A
R
⚫ Inserting Nodes:
E
D

B
Y

S
U
L
A
V

N
E
P Inserting node at the beginning
A
L

161 11/14/2022 10:59AM

P
R
E Operation of Singly Linked List
P
A ⚫ Inserting Nodes:
R
E ⚫ We can use the following steps to insert a new node at the end of the
D single linked list.
⚫ Create a newNode with given valueand newNode -> next as NULL
B
Y
⚫ Check whether list is Empty (head == NULL)
S
U
L ⚫ If it is Empty, then set head = newNode
A
V
⚫ If it is Not Empty,then definea nodepointer temp and initialize with head.
N
E ⚫ Keepmovingthe temp to its next nodeuntil it reachesto the last nodein the list
P
A
(until temp -> next is equal to NULL)
L
⚫ Set temp ->next = newNode
162 11/14/2022 10:59AM
P
R
E Operation of Singly Linked List
P
A
R
⚫ Inserting Nodes:
E
D

B
Y

S
U
L
A
V

N
E
P Inserting node at the end
A
L

163 11/14/2022 10:59AM

P
R
E Operation of Singly Linked List
P
A ⚫ Inserting Nodes:
R ⚫ Wecanusethe following stepsto insert a newnodeafter a nodein the single linked
E list.
D
⚫ Create a newNodewith given value

B
⚫ Checkwhether list is Empty(head == NULL)
Y

S ⚫ If it is Empty, then set newNode-> next = NULL and head = newNode

U
L ⚫ If it is Not Empty,then define anodepointer temp and initialize with head.
A
V ⚫ Keep moving the temp to its next node until it reaches to the node after which we want to insert
the newNode (until temp -> data is equal to location, here location is the node value after which
N we want to insert the newNode)
E
P ⚫ Every time check whether temp is reached to last node or not. If it is reached to last node then
A display “Given node is not found in the list. Insertion not possible.” and terminate the function;
L otherwise,movethe temp to next node.

⚫ Finally, set newNode-> next = tempand temp -> next = newNode

202 11/14/2022 10:59AM
P
R
E Operation of Singly Linked List
P
A
R
⚫ Inserting Nodes:
E
D

P
R
E Operation of Doubly Linked List
P
A ⚫ Inserting Nodes:
R ⚫ Wecan usethe following steps to insert a newnodeafter a nodein the doubly linked list.
E ⚫ Create a newNodewith givenvalue
D
⚫ Check whetherlist is Empty (head== NULL)
B
Y ⚫ If it is Empty,thenassignNULLto newNode-> previousand newNode-> next and newNodeto head

S
⚫ If it is Not Empty,thendefine twonode pointerstemp1and temp2and initialize temp1 with head.
U
L
⚫ Keep moving the temp1 to its next node until it reaches to the node after which we want to insert the
A newNode (until temp1 -> data is equal to location, here location is the node value after which wewant
V to insert the newNode)

N ⚫ Every time check whether temp1 is reached to last node or not. If it is reached to last node then display
E “Given node is not found in the list. Insertion not possible.” and terminate the function; otherwise, move
P the temp1 to next node.
A
L ⚫ Assign temp1 -> next to temp2, newNode to temp1 -> next, temp1 to newNode -> previous, temp2 to
newNode-> next and newNodeto temp2-> previous

178 11/14/2022 10:59AM

P
R
E Operation of Doubly Linked List
P
A
R
⚫ Inserting Nodes:
E
D

B
Y

S
U
L
A
V

N
E
P
A
L
Inserting node after a node
217 11/14/2022 10:59AM
P
R
E Operation of Doubly Linked List
P
A ⚫ Inserting Nodes:
R
E ⚫ We can use the following steps to insert a new node at the end of the
D doubly linked list.
⚫ Create a newNode with given valueand newNode -> next as NULL
B
Y
⚫ Check whether list is Empty (head == NULL)
S
U
L ⚫ If it is Empty,then assignNULLto newNode -> previous and newNode to head
A
V
⚫ If it is Not Empty,then definea nodepointer temp and initialize with head.
N
E ⚫ Keepmovingthe temp to its next nodeuntil it reachesto the last nodein the list
P
A
(until temp -> next is equal to NULL)
L
⚫ AssignnewNode to temp ->next and temp to newNode -> previous
180 11/14/2022 10:59AM
P
R
E Operation of Doubly Linked List
P
A
R
⚫ Inserting Nodes:
E
D

B
Y

S
U
L
A
V

N
E
P Inserting node at the end
A
L

181 11/14/2022 10:59AM

P
R
E Operation of Doubly Linked List
P
A ⚫ Deleting Node:
R
E ⚫ We can use the following steps to delete a node from beginning of the doubly
D linkedlist.
⚫ Check whetherlist is Empty (head== NULL)
B
Y
⚫ If it is Empty then, display “List is Empty! Deletion is not possible”and terminate the
S function
U
L
⚫ If it is not Empty then,define a Node pointer‘temp’and initialize with head.
A
V
⚫ Checkwhetherlist is havingonly one node(temp -> previous is equal to temp -> next)
N
E
P ⚫ If it isTRUE,then set head= NULLand deletetemp
A
L ⚫ If it is FALSE,then set head= temp-> next, NULL= head-> previousand delete
temp
182 11/14/2022 10:59AM
P
R
E Operation of Doubly Linked List
P
A
R
⚫ Deleting Node:
E
D

B
Y

S
U
L
A
V

N
E
P Deleting nodefrom the beginning
A
L

183 11/14/2022 10:59AM

P
R
E Operation of Doubly Linked List
P
A
R
⚫ Deleting Node:
E ⚫ We can use the following steps to delete a node from end of the doubly
D
linked list.
B ⚫ Check whether list is Empty (head == NULL)
Y
⚫ If it is Empty then,display “List is Empty! Deletion is not possible”and terminate
S the function
U
⚫ If it is not Emptythen,definetwo Node pointer‘temp’and initialize with head.
L
A ⚫ Check whether list is having only onenode(temp -> next == NULL and temp ->
V previous == NULL)
N ⚫ If it is TRUE, then assign head = NULL and delete temp and terminate the
E function
P ⚫ If it is FALSE,then keepmovingtempuntil it reachesto the last nodein the list
A
L
(until temp -> next == NULL)
⚫ Finally, assigntemp->next = NULLand delete temp
184 11/14/2022 10:59AM
P
R
E Operation of Doubly Linked List
P
A
R
⚫ Deleting Node:
E
D

B
Y

S
U
L
A
V

N
E
P Deleting nodefromthe end
A
L

185 11/14/2022 10:59AM

P
R
E Operation of Doubly Linked List
P
A ⚫ Deleting Node:
R ⚫ Wecan use the following steps to delete a specificnodeof the doublylinked list.
E
⚫ Check whetherlist is Empty (head== NULL)
D
⚫ If it is Empty then,display“Listis Empty! Deletion is not possible”and terminate the function
⚫ If it is not Emptythen,definea Node pointer‘temp’and initialize with head.
B
⚫ Keepmoving the temp until it reachesto the exact nodeto bedeleted orto the last node.
Y
⚫ If it isreachedtothelastnodethendisplay“Givennodenotfound in the list! Deletion not
possible”and terminatethe function
S
⚫ If it is reached to the exact node which wewant to delete,then checkwhether list is having only
U onenodeornot
L ⚫ If list hasonly onenode and that node is to bedeleted,then set head = NULLand delete temp
A (free (temp))
V ⚫ If list containsmultiplenodes,thencheckwhethertempisthefirst node in the list (temp ==
head)
N ⚫ If temp is the first nodethen movethe head to the next node (head = head -> next) and set head
E of previous to NULL (head -> previous = NULL) and delete temp
P ⚫ If temp is not first nodethen check whether it is last nodein the list (temp -> next == NULL)
A ⚫ If tempis last nodethen settemp-> previous-> next = temp-> next anddelete temp(free
L (temp))
⚫ If temp1 is not first node and not last node then set temp -> previous -> next = temp -> next
224 and temp = temp-> next -> previous and delete temp (free (temp)) 11/14/2022 10:59AM
P
R
E Operation of Doubly Linked List
P
A
R
⚫ Deleting Node:
E
D

B
Y

S
U
L
A
V

N Deleting nodefroma specific position

E
P
A
L

187 11/14/2022 10:59AM

P
R
E Operation of Doubly Linked List
P
A
R
⚫ Displaying Node:
E ⚫ We can use the following steps to display the elements of the doubly
D
linked list.
B ⚫ Check whether list is Empty (head == NULL)
Y
⚫ If it is Empty then,display“List is Empty!”and terminate the function
S ⚫ If it is not Emptythen,definea Node pointer‘temp’and initialize with head.
U
L ⚫ Display“NULL <- … … ”
A ⚫ Keep displayingtemp -> data with an arrowuntil temp reachesto the last node.
V
⚫ Finally display temp -> data with arrow pointing to NULL (temp -> data ->
N NULL)
E
P
A
L

188 11/14/2022 10:59AM

P
R
E Applications of Doubly Linked List
P
A
R
⚫ Redo and undo functionality in software
E
D

B
⚫ Forwardand backwardnavigation in browsers
Y

S ⚫ For navigation systems where forward and backward navigation

U
L is required
A
V

N
E
P
A
L

189 11/14/2022 10:59AM

P
R
E Circular Linked List
P
A
R
⚫ Acircular linked list is basically a linear linked list that may be
E single or double-linked.
D

B
Y ⚫ The only difference is that there is noany NULLvalue terminating
S the list.
U
L
A
V
⚫ In fact in the list, everynodepoints to the next nodeand last node
points to the first node,thus forming a circle.
N
E
P
A ⚫ Since it forms a circle with no endto stop it is called as circular
L
linked list.
190 11/14/2022 10:59AM
P
R
E Circular Linked List
P
A
R
⚫ In circularlinked list therecanbenostarting orendingnode, whole
E node can be traversed fromany node.
D

B
Y ⚫ In order to traverse the circular linked list, only once we need
S to traverseentire list until the starting node is not traversedagain.
U
L
A
V
⚫ Acircularlinked list canbeimplemented using both singly linked
list and doubly linked list.
N
E
P
A
L

191 11/14/2022 10:59AM

P
R
E Circular Linked List
P
A
R
E
D

B
Y Basic structure of singlycircularlinked list
S
U
L
A
V

N Basic structure of doubly circularlinked list

E
P
A
L

192 11/14/2022 10:59AM

P
R
E Circular Linked List
P
A
R
⚫ Advantages of a Circular Linked List
E ⚫ Entire list can betraversedfrom any node.
D

B
Y ⚫ Circular lists arethe required data structure whenwewant a list to be
accessed in a circle or loop.
S
U
L
A
⚫ Despiteof beingsingly circular linked list wecaneasily traverseto its
V previous node,which is not possiblein singly linked list.
N
E
P
A
L

193 11/14/2022 10:59AM

P
R
E Circular Linked List
P
A
R
⚫ Disadvantages of a Circular Linked List
E ⚫ Circular list are complexas compared to singly linked lists.
D

B
Y ⚫ Reversingof circular list is acomplexascompared to singly ordoubly
lists.
S
U
L
A
⚫ If not traversedcarefully,then wecould end up in an infinite loop.
V

N ⚫ Like singly and doubly lists, circular linked lists also doesn’t support
E
P
direct accessing of elements.
A
L

194 11/14/2022 10:59AM

P
R
E Operations on Circular Linked List
P
A
R
⚫ Followingare the important operations supported by a circular list:
E ⚫ insert – inserts an element at the start of the list
D

B
Y ⚫ delete – deletes an element from the start of the list

S
U ⚫ display – displays the list
L
A
V

N
E
P
A
L

195 11/14/2022 10:59AM

P
R
E STACK as LINKED LIST
P
A
R
⚫ The majorproblemwith the stack implemented using an arrayis, it
E works only for a fixed number of data values.
D

B
Y ⚫ That means the amount of data must bespecified at the beginning of
S the implementation itself.
U
L
A
V
⚫ Stack implemented using an array is not suitable, when we don’t
knowthe size of data which we aregoing to use.
N
E
P
A ⚫ Astack data structure can beimplemented by using a linked list data
L
structure.
196 11/14/2022 10:59AM
P
R
E STACK as LINKED LIST
P
A
R
⚫ Thestackimplementedusinglinked list canworkforanunlimited
E number of values.
D

B
Y ⚫ That means, stack implemented using linked list works for
S the variable size of data.
U
L
A
V
⚫ So, there is no need to fix the size at the beginning of
the implementation.
N
E
P
A ⚫ The stack implemented using linked list can organize as many data
L
values as we want.
197 11/14/2022 10:59AM
P
R
E STACK as LINKED LIST
P
A
R
⚫ In linked list implementation of a stack, every new element is inserted
E as ‘top’element; That means every newly inserted element is pointed
D
by‘top’.
B
Y

S ⚫ Whenever we want to remove an element from the stack, simply

U remove the node which is pointed by ‘top’ by moving ‘top’ to its
L
A previous node in the list.
V

N
E ⚫ The next field of the first element must bealwaysNULL.
P
A
L

198 11/14/2022 10:59AM

P
R
E STACK as LINKED LIST
P
A
R
⚫ In the given example,
E ⚫ The last inserted nodeis 99
D

B
Y ⚫ The first inserted nodeis 25

S
U ⚫ The order of elements inserted is:
L
A ⚫ 25
V ⚫ 32
⚫ 50
N
E 99
P
A
L

199 11/14/2022 10:59AM

P
R
E STACK as LINKED LIST
P
A
R
⚫ To implement a stack using a linked list, we need to set the following
E things before implementing actual operations:
D
⚫ Include all the header files which are used in the program. And declare
B all the user defined functions.
Y

S
U ⚫ Define a‘Node’structure with two members;data and next.
L
A
V ⚫ Define a Node pointer‘top’and set it to NULL.
N
E
P ⚫ ImplementthemainmethodbydisplayingMenuwith list of operations
A and make suitable function calls in the main method.
L

238 11/14/2022 10:59AM

P
R
E STACK as LINKED LIST
P
A
R
⚫ To insert a new node into the stack – push(value)
E
D
⚫ Create a newNode with given value
B
Y
⚫ Check whether stack is Empty (𝑡𝑜𝑝 == 𝑁𝑈𝐿𝐿)
S
U
L
A ⚫ If it is Empty,then set 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑛𝑒𝑥𝑡 = 𝑁𝑈𝐿𝐿
V

N ⚫ If it is not Empty,then set 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑛𝑒𝑥𝑡 = 𝑡𝑜𝑝

E
P
A
L ⚫ Finally, set 𝑡𝑜𝑝 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒

201 11/14/2022 10:59AM

P
R
E STACK as LINKED LIST
P
A
R
⚫ To delete a new node from the stack – pop()
E
D
⚫ Check whether stack is Empty (𝑡𝑜𝑝 == 𝑁𝑈𝐿𝐿)
B
Y
⚫ If it is Empty, then display “Stack is Empty. Deletion is not
S
U possible.” and terminate the function.
L
A
V ⚫ If it is not Empty, then define a Node pointer‘temp’and set it to‘top’
N
E
P ⚫ Then set 𝑡𝑜𝑝 = 𝑡𝑜𝑝 → 𝑛𝑒𝑥𝑡
A
L
⚫ Finally, delete‘temp’(𝑓𝑟𝑒𝑒(𝑡𝑒𝑚𝑝))
202 11/14/2022 10:59AM
P
R
E STACK as LINKED LIST
P
A ⚫ To display the elements (nodes) of a stack – display()
R
E
D
⚫ Check whether stackis Empty (𝑡𝑜𝑝 == 𝑁𝑈𝐿𝐿)
B
Y
⚫ If it is Empty,then display“Stack is Empty.” and terminate the function.
S
U
L ⚫ If it is not Empty,then definea Node pointer‘temp’and initialize with‘top’
A
V
⚫ Display 𝑡𝑒𝑚𝑝 → 𝑑𝑎𝑡𝑎 −−→ and move it to the next node. Repeat the
N
E
same until temp reaches to the first node in the stack. (𝑡𝑒𝑚𝑝 → 𝑛𝑒𝑥𝑡 ! =
P 𝑁𝑈𝐿𝐿)
A
L
⚫ Finally,display 𝑡𝑒𝑚𝑝 → 𝑑𝑎𝑡𝑎 −−→ 𝑁𝑈𝐿𝐿
241 11/14/2022 10:59AM
P
R
E QUEUE as LINKED LIST
P
A
R
⚫ Themajorproblemwith the queueimplementedusinganarray is, it
E will work for an only fixed number of data values.
D

B
Y ⚫ That means,theamountofdatamustbespecified at thebeginning
S itself.
U
L
A
V
⚫ Queueusing an array is not suitable when wedon’t knowthe size of
data which we aregoing to use.
N
E
P
A ⚫ Aqueuedatastructurecanbeimplementedusingalinked list data
L
structure.
204 11/14/2022 10:59AM
P
R
E QUEUE as LINKED LIST
P
A
R
⚫ The queue which is implemented using a linked list canworkfor an
E unlimited number of values.
D

B
Y ⚫ That means,queue using linked list can work for the variable size of
S data (no need to fix the size at the beginning of the
U implementation).
L
A
V
⚫ The queue implemented using linked list can organize asmanydata
N
E values as we want.
P
A
L

205 11/14/2022 10:59AM

P
R
E QUEUE as LINKED LIST
P
A
R
⚫ In linked list implementation of a queue, the last inserted node is
E always pointed by ‘rear’ and the first node is always pointed by
D
‘front’.
B
Y

S
U
L
A
V
⚫ In above figure,
N
E ⚫ The last inserted nodeis 50 and it is pointed by‘rear’
P
A ⚫ The first inserted nodeis 10 and it is pointed by‘front’
L
⚫ The order of elements inserted is 10, 15, 22, and 50.
206 11/14/2022 10:59AM
P
R
E QUEUE as LINKED LIST
P
A
R
⚫ Toimplementqueueusinglinked list, weneed to setthefollowing
E things before implementing actual operations:
D
⚫ Include all the header files which are used in the program. And declare
B all the user defined functions.
Y

S
U ⚫ Define a‘Node’structure with two members;data and next.
L
A
V ⚫ Define two Node pointers‘front’and‘rear’and set both to NULL.
N
E
P ⚫ Implement the main methodby displayingMenu of list of operations
A andmake suitablefunction callsin the mainmethodto performuser
L
selected operation.
207 11/14/2022 10:59AM
P
R
E QUEUE as LINKED LIST
P
A
R
⚫ To insert a new node into the queue – enQueue(value)
E
D
⚫ Create a newNode with given value and set 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 → 𝑛𝑒𝑥𝑡 to
B
Y
NULL.

S
U ⚫ Check whether queue is Empty (𝑟𝑒𝑎𝑟 == 𝑁𝑈𝐿𝐿)
L
A
V ⚫ If it is Empty, then set 𝑓𝑟𝑜𝑛𝑡 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 and 𝑟𝑒𝑎𝑟 =
N 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
E
P
A ⚫ If it is not Empty, then set 𝑟𝑒𝑎𝑟 → 𝑛𝑒𝑥𝑡 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒 and
L
𝑟𝑒𝑎𝑟 = 𝑛𝑒𝑤𝑁𝑜𝑑𝑒
208 11/14/2022 10:59AM
P
R
E QUEUE as LINKED LIST
P
A
R
⚫ To delete a node from the queue – deQueue()
E
D
⚫ Check whether queue is Empty (𝑓𝑟𝑜𝑛𝑡 == 𝑁𝑈𝐿𝐿)
B
Y
⚫ If it isEmpty, then display“QueueisEmpty. Deletionisnot possible.”
S
U and terminate from the function.
L
A
V ⚫ If it is not Empty,then define a Node pointer‘temp’and set it to‘front’.
N
E
P ⚫ Then set 𝑓𝑟𝑜𝑛𝑡 = 𝑓𝑟𝑜𝑛𝑡 → 𝑛𝑒𝑥𝑡 and delete ‘temp’
A (𝑓𝑟𝑒𝑒 𝑡𝑒𝑚𝑝 )
L

209 11/14/2022 10:59AM

P
R
E QUEUE as LINKED LIST
P
A ⚫ To display the elements (node) of the queue – display()
R
E
D
⚫ Check whether queue is Empty (𝑓𝑟𝑜𝑛𝑡 == 𝑁𝑈𝐿𝐿)
B
Y
⚫ If it isEmpty, then display“QueueisEmpty.”andterminate fromthe
S function.
U
L
A ⚫ If it is not Empty, then define a Node pointer ‘temp’and initializewith
V ‘front’.
N
E
P ⚫ Display 𝑡𝑒𝑚𝑝 → 𝑑𝑎𝑡𝑎 −−→ and moveit to the next node.Repeat
A the sameuntil‘temp’reachesto‘rear’(𝑡𝑒𝑚𝑝 → 𝑛𝑒𝑥𝑡 ! = 𝑁𝑈𝐿𝐿)
L

210 Finally, display 𝑡𝑒𝑚𝑝 → 𝑑𝑎𝑡𝑎 −−→ 𝑁𝑈𝐿𝐿 11/14/2022 10:59AM

P
R
E
P
A
R
E
D

B
Y

S RECURSION
U
L
A
V

N
E
P
A
L

211 11/14/2022 10:59AM

P
R
E Recursion
P
A ⚫ Recursion is a process by which a function calls itself repeatedly, until some
R
E
specified condition hasbeen satisfied.
D

B
⚫ Theprocessisusedforrepetitivecomputationsin whicheachaction is stated in
Y terms of a previous result.
S
U ⚫ In orderto solvea problemrecursively,two conditions must besatisfied:
L ⚫ First,the problemmust bewritten in a recursiveform.
A
V ⚫ Second,the problem statement must includea stopping condition.

N
E ⚫ Weuserecursionto solvebiggerproblemconverting it into smallersub-problems.
P
A
L ⚫ Onething wehaveto keep in mind is that if eachsub-problem is following same
kind of patterns,then only wecan usethe recursive approach.
212 11/14/2022 10:59AM
P
R
E Recursion
P
A
R
⚫ Advantages of Recursion:
E ⚫ The codemay bemuch easier to write.
D
⚫ Tosolvesomeproblemswhichare naturallyrecursivesuchastower of
B Hanoi.
Y

S
U ⚫ Disadvantages of Recursion:
L
A ⚫ Recursive functions are generally slowerthan non-recursivefunctions.
V
⚫ Mayrequire a lot of memoryto hold intermediate results onthe system
N stack.
E
P ⚫ It isdifficult tothink recursivelysoone must bevery careful when
A
L
writing recursivefunctions.

213 11/14/2022 10:59AM

P
R
E Recursion vs. Iteration
P
A Recursion Iteration
R
E Iteration is the process of executing a statement or
Recursion is the technique of defining
D a set of statements repeatedly, until some specified
anything in terms of itself.
condition is satisfied.
B
Y
Iterations is like bottom-up approach; it begins
Recursion isatop-downapproach to problem
with what is known and from this it constructs the
solving;it divides the problem into
S solution step by step.
pieces.
U
L
Theremustbeanexclusiveif statementinsidethe Iteration involvesfour clear-cutsteps
A recursive function,specifying stoppingcondition. like initialization,condition,
V execution, and updating.
Problemcouldbewritten ordefinedin termofits It isnotnecessaryto define a problem in term of
N previousresult to solve a problem using recursion. its previousresult to solve using iteration.
E
P
Not all problemshave recursive solution. Any recursive problem can besolved iteratively.
A Recursion is generally a worse option to go for Iterative counterpart of a problem is more efficient
L simple problems, or problems not recursive in in terms of memory, utilization and execution
nature. speed.
11/14/2022 10:59AM
P
R
E Tail Recursion
P
A
R
⚫ Arecursivemethodisreferredtoastail-recursive when the recursive
E call is the last thing executed by that method.
D

B
Y ⚫ Otherwise,it’s known as head-recursive.
S
U
L
A
V

N
E
P Head-recursivemethod Tail-recursivemethod
A
L

142 11/14/2022 10:59AM

P
R
E Benefits of Tail-recursive Method
P
A
R
⚫ Tail-recursive methods are optimized by certain compilers.
E
D

B
⚫ These compilers execute recursive calls with the help of stack.
Y

S ⚫ In case of tail-recursive methods, there is no need to reserve a place in

U
L the stack for the recursive call because there is nothing left to do in
A
V
the current method and wewon’t bereturning to the parent call.
N
E ⚫ This is referred to as tail-call optimization or elimination.
P
A
L

143 11/14/2022 10:59AM

P
R
E Factorial
P
A
R
⚫ The factorial of a number is the product of all the integers from 1 to
E that particular number.
D
⚫ For example,the factorial of 5 is 1*2*3*4*5,which is equal to 120.
B
Y

S ⚫ Factorialis not defined foranegativenumbersandthe factorial of

U zero is 1. i.e. 0! = 1
L
A
V
⚫ Recursive definition of the factorial function 𝑓 is given as:
N
E 𝑓 0 = 1 & 𝑓 1 = 1 ← 𝐵𝑎𝑠𝑒 𝐶𝑎𝑠𝑒
P 𝑓(𝑛) = 𝑛 ∗ 𝑓(𝑛 − 1) ← 𝑅𝑒𝑐𝑢𝑟𝑠𝑖𝑣𝑒 𝐶𝑎𝑠𝑒
A
L

144 11/14/2022 10:59AM

P
R
E Factorial
P
A
R
/* Recursive function of factorial * /
E
D
int fact(int n) / / say, 𝑛 = 5
{
B
Y int res;
S if(n == 1 | | n == 0)
U
L return 1;
A
V else
N return n*fact(n-1);
E
P }
A
L

145 11/14/2022 10:59AM

P
R
E Fibonacci Series
P
A
R
⚫ Fibonacciseries starts from two numbers 0 and 1.
E
D
⚫ It then generates the subsequent number by adding two previous
B
Y numbers. i.e. 0+1=1 is the third number; 1+1=2 is the fourth
S number;2+1=3 is the fifth number;and soon.
U
L
A
V
⚫ The Fibonacci sequenceare the following integer sequence:0, 1, 1, 2,
3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …
N
E
P
A ⚫ In mathematical terms, the sequence 𝐹𝑛 of Fibonacci numbers is
L
defined by the recurrence relation 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 with seed
146 values𝐹0 = 0 and 𝐹1 = 1. 11/14/2022 10:59AM
P
R
E Fibonacci Series
P
A
R
/* Recursive function of Fibonacci sequence * /
E int fibo(int x) / / say, x=7
D

B
{
Y if(x==0)
S return 0;
U
L else if(x==1)
A
V return 1;
N else
E
P return (fibo(x-1) + fibo(x-2));
A
L }
220 11/14/2022 10:59AM
P
R
E Greatest Common Divisor (GCD)
P
A
R
⚫ GreatestCommonDivisor(GCD) or Highest Common Factor (HCF)
E of two numbers is the largest number that divides both of them.
D

B
Y ⚫ For example:let us assume twonumbers 63 and 42
S ⚫ 63 = 7 ∗ 3 ∗ 3
U
⚫ 42 = 7 ∗ 3 ∗ 2
L
A ⚫ So, the GCDof 63 and 42 is 21.
V

N
E
P
A
L

221 11/14/2022 10:59AM

P
R
E Greatest Common Divisor (GCD)
P
A
R
/* Recursive function of gcd * /
E
D
int gcd(int n1, int n2) / / say 𝑛1 = 63 &𝑛2 = 42
{
B
Y if (n2 != 0)
S return gcd(n2, n1 % n2);
U
L else
A
V return n1;
N }
E
P
A
L

222 11/14/2022 10:59AM

P
R
E Tower of Hanoi
P
A
R
⚫ Tower of Hanoi is a mathematical puzzle which consists of three
E tower pegsand morethan one rings.
D

B
Y ⚫ Theseringsareof different sizesandstackeduponin an ascending
S order.i.e.the smaller ring sits over the larger one.
U
L
A
V
⚫ Thereareothervariationsofthepuzzle wherethenumberofdisks
increase,but the tower count remains the same.
N
E
P
A
L

223 11/14/2022 10:59AM

P
R
E Tower of Hanoi
P
A
R
⚫ Rules: The mission is to moveall the disks from sourcetower to
E destination tower without violating the sequenceof arrangement.
D

B
Y ⚫ Only one disk can bemovedamong the towers at any given time.

S
U ⚫ Only the“top”disk can beremoved.
L
A
V
⚫ No largedisk can sit over a small disk.
N
E
P ⚫ Only 3 stacks can beused for solvingthe puzzle.
A
L

224 11/14/2022 10:59AM

P
R
E Tower of Hanoi
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

225 11/14/2022 10:59AM

P
R
E Tower of Hanoi
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

226 11/14/2022 10:59AM

P
R
E Tower of Hanoi – Algorithm
P
A
R
E ⚫ Step 1:
D
⚫ Move𝑛 − 1 disks fromsourceto auxiliary
B
Y

S ⚫ Step 2:
U
L ⚫ Move𝑛𝑡ℎ disk from source to destination
A
V

N ⚫ Step 3:
E ⚫ Move𝑛 − 1 disks fromauxiliary to destination
P
A
L
Number of steps required = 𝟐𝒏 − 𝟏
227 11/14/2022 10:59AM
P
R
E Tower of Hanoi – Algorithm
P
A
R
E
D
voidTOH(int n,int a,int b,int c) ⚫ Move n-1 disks from A to B
B
Y { using C
S
if(n>0)
U {
L ⚫ Move 𝒏𝒕𝒉 disk fromAto C
A TOH(n-1,A, C,B);
V print (A, C);
N TOH(n-1, B,A,C); ⚫ Move n-1 disks from B to C
E }
P using A
A }
L

228 11/14/2022 10:59AM

P
R
E Applications of Recursion
P
A ⚫ Chess Games
R ⚫ If you have ever played chess on your mobile
E or laptop then you must beawareof the auto-
D suggestionforeachmoveonthe chessboard.

B ⚫ And if you have not played it yet then you

Y can take the referencefromthe image.

S ⚫ The green dots that you are able to seen in

U the image are generated with the help of
L recursions.
A
V ⚫ Here recursion is used to generate all possible
safe and unsafe moves of a particular piece of
the chessgame.
N
E
⚫ Generally, the safe moves are represented with
P
the help of a green dot and red for the unsafe
A ones.
L

229 11/14/2022 10:59AM

P
R
E Applications of Recursion
P
A ⚫ Bubble Shooter Game
R ⚫ The very popular Bubble Shooter game
E also implies or uses the concept of
D recursionin it.
B
Y ⚫ It generally finds all possible bubbles
of the same color in all the four
S directions and both the diagonals
U which are connected to each other and
L blast them if the same color bubble is
A thrown on them.
V
⚫ The game is same as the flood fill
N problemof the recursion.
E
P
A
⚫ Some other popular games that use the
L
concept of recursion are Candy Crush,
Sudoku,etc.
230 11/14/2022 10:59AM
P
R
E Applications of Recursion
P
A ⚫ Windows Paint Application
R
E
D
⚫ Windows paint is the most
B popular application that uses
Y
the concept of recursion while
S filling the color in a particular
U
L area of the drawing/model.
A
V
⚫ It uses the concept of flood fill
N
E while coloring a particular area
P of the drawing.
A
L

231 11/14/2022 10:59AM

P
R
E Applications of Recursion
P
A
R
⚫ Tree Data Structure
E ⚫ The most important data structure‘tree’doesn’t exist without recursion.
D

B
Y ⚫ Wecan solve that in an iterative wayalso but that will bea very tough
task.
S
U
L
A
⚫ For smaller problems the iterative way will work fine but for the larger
V tree the iterative way will become the headache to use because as the tree
N
sizewill increase the sizeof the code too will increase.
E
P
A ⚫ But with the help of recursion the size of the code will become
L
drastically small.
232 11/14/2022 10:59AM
P
R
E Applications of Recursion
P
A
R
⚫ Sorting Algorithms
E ⚫ Most of the sorting algorithms uses the concept of recursion to sort the
D
data according to the given condition.
B
Y
⚫ Manyof the sorting algorithms like quick sort,mergesort,etc.usesthe
S
U recursion to sort the data.
L
A
V ⚫ Some searching algorithms like Binary search uses the concept of
N
recursion.
E
P
A
L

233 11/14/2022 10:59AM

P
R
E
P
A
R
E
D

B
Y

S SORTING
U
L
A
V

N
E
P
A
L

234 11/14/2022 10:59AM

P
R
E Sorting
P
A
R
⚫ Sorting is a technique to rearrange the elements of a list in ascending
E or descending order, which can be numerical, lexicographical, or any
D
user defined order.
B
Y

S ⚫ The complexity of a sorting algorithm can bemeasured in termsof:

U ⚫ Number of algorithmsteps to sort n records
L
A ⚫ Numberof comparisons betweenkeys (appropriate when thekeys are
V
long character strings)
N ⚫ Number of times records must be moved (appropriate when record size is
E
P large)
A
L

252 11/14/2022 10:59AM

P
R
E Sorting
P
A
R
⚫ Example:
E ⚫ 1, 3, 4, 6, 8, 9 are in increasing order, as every next element is greater
D
than the previous element.
B ⚫ 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less than
Y
the previous element.
S
U ⚫ Forexample, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next
L element is less than or equal to (in case of 3) but not greater than the
A
V previous element.
⚫ Forexample, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next
N
E element is greater than or equal to (in case of 3) but not less than the
P previous element.
A
L

236 11/14/2022 10:59AM

P
R
E Sorting
P
A ⚫ Sorting algorithms may require some extra space for comparison
R and temporary storageof fewdata elements.
E
D
⚫ Those algorithms that do not require any extra space and sorting is said to
B
Y
happenin-place, orforexample,within thearrayitself iscallediscalled in-
placesorting. For example,Bubble sort.
S
U
L ⚫ Sorting whichusesequal ormorespaceis called not-in-place sorting.For
A example,Merge sort.
V

N ⚫ If a sorting algorithm, after sorting the contents, does not change the
E sequence of similar content in which they appear;it is called stable sorting.
P
A
L ⚫ If asortingalgorithm, aftersortingthecontents, changesthesequenceof
similar content in which they appear;it is called unstable sorting.
11/14/2022 10:59AM
237
P
R
E Sorting
P
A
R
⚫ Stable sorting
E
D

B
Y

S
U
L ⚫ Unstable sorting
A
V

N
E
P
A
L

238 11/14/2022 10:59AM

P
R
E Internal & External Sorting
P
A
R
⚫ Aninternal sort is any data sorting processthat takes place entirely
E within the main memory of a computer.
D

B
Y ⚫ This is possible wheneverthe data to besorted is small enough to all
S be held in the main memory.
U
L
A
V
⚫ There are3 types of internal sort:
⚫ Selection sort – for example,HeapSortAlgorithm
N
E ⚫ Insertion sort – for example,Shell Sort Algorithm
P
A ⚫ Exchange sort – for example,BubbleSort Algorithm, Quick Sort
L Algorithm
239 11/14/2022 10:59AM
P
R
E Internal & External Sorting
P
A
R
⚫ Sorting large amount of data requires external or secondarymemory.
E
D
⚫ This processuses external memory such as HDDto store the data
B
Y which is not fit into the main memory.
S
U
L ⚫ All external sorts arebasedon processof merging.
A
V

N ⚫ For example,MergeSort.
E
P
A
L

240 11/14/2022 10:59AM

P
R
E Insertion Sort
P
A
R
⚫ Insertion sortisasimplesorting algorithm that workssimilar to the
E way you sort playing cards in your hands.
D

B
Y ⚫ The array is virtually split into a sorted and an unsorted part.
S
U
L ⚫ Values fromthe unsorted part arepickedandplacedat the correct
A
V
position in the sorted part.
N
E
P
A
L

241 11/14/2022 10:59AM

P
R
E Insertion Sort
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

242 11/14/2022 10:59AM

P
R
E Insertion Sort: Algorithm
P
A ⚫ Step 1 - If the element is the first element,assume that it is already sorted.
R Return 1.
E
D
⚫ Step2 - Pickthe next element,and store it separatelyin a key.
B
Y
⚫ Step3 - Now,compare the key with all elementsin the sorted array.
S
U
L
⚫ Step 4 - If the element in the sorted array is smaller than the current
A
V element, then move to the next element. Else, shift greater elements in the
array towardsthe right.
N
E
P ⚫ Step 5 - Insert the value.
A
L
⚫ Step 6 - Repeat until the array is sorted.
243 11/14/2022 10:59AM
P
R
E Insertion Sort: Algorithm
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

244 11/14/2022 10:59AM

P
R
E Insertion Sort: Implementation
P
A
R
void insertionSort(int a[],int n)
E {
D
for(int i=1;i<n;i++)
B
Y {
int next = a[i]; / / next is the itemto beinserted
S
U int j;
L for(j=i-1;j>=0 &&a[j]>next;j--)
A
V a[j+1] = a[j]; / / shift sorted items to make placefor next
a[j+1] = next; / / insert next to the correct location
N
E }
P
A }
L

245 11/14/2022 10:59AM

P
R
E Insertion Sort: Analysis
P
A
R
⚫ Outer loop executes (n-1) times
E
D
⚫ Number of times inner loop is executed dependson the input
B
Y ⚫ Best Case:the array is already sorted and (𝑎[𝑗] > 𝑛𝑒𝑥𝑡) is always
S false.i.e. no shifting of data is necessary.Best casetime is 𝑂(𝑛).
U
L
A ⚫ Worst Case: the array is reversely sorted and (𝑎[𝑗] > 𝑛𝑒𝑥𝑡) is
V
alwaystrue. i.e. insertion alwaysoccur at the front. Worstcasetime is
N 𝑂(𝑛2).
E
P
A ⚫ Average Case: we have to look at all possible initial data
L
organization.Averagecase time is 𝑂(𝑛2 ).
246 11/14/2022 10:59AM
P
R
E Selection Sort
P
A
R
⚫ The selection sort algorithm sorts an array by repeatedly finding the
E minimum element (considering ascending order) from unsorted part
D
and putting it at the beginning.
B
Y

S ⚫ Algorithm:
U ⚫ Step 1 − Set MIN to location 0
L
A ⚫ Step 2 − Search the minimum element in the list
V
⚫ Step 3 − Swap with valueat location MIN
N
⚫ Step 4 − Increment MIN to point to next element
E
P ⚫ Step 5 − Repeat until list is sorted
A
L

247 11/14/2022 10:59AM

P
R
E Selection Sort
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

248 11/14/2022 10:59AM

P
R
E Selection Sort
P
A Thearray beforethe selection sort operationbegins.
R
E
D Thesmallestnumber12 isswappedinto thefirst element in the
structure.
B
Y In the data that remains,16 is the smallest and it doesnot needto be
moved.
S
U
L 26 is the next smallest numberand it is swappedinto the third position.
A
V 42 is the next smallest numberand it is alreadyin the correct position.

N
E 53 is the smallest number in the data that remains and it is swappedto
P theappropriateposition.
A
L Ofthetworemainingdataitems,77 isthe smaller. The items areswapped
and the selectionsortis completed.
266 11/14/2022 10:59AM
P
R
E Selection Sort: Analysis
P
A ⚫ Selecting the lowest element requires scanning all 𝑛 elements (this takes
R
E 𝑛 − 1 comparisons)and then swappingit into the first position.
D

B ⚫ Finding the next lowest element requires scanning all 𝑛 − 1 elements and
Y
so on; for (𝑛 − 1) + (𝑛 − 2) + ⋯ + 2 + 1 𝑂 𝑛2
S comparisons.
U
L
A ⚫ Each of these scansrequires oneswapfor 𝑛 − 1 elements.
V

N
E
⚫ Therefore,
P ⚫ Best caseperformance:𝑂 𝑛 2
A
⚫ Worst case performance:𝑂 𝑛2
L
⚫ Averagecaseperformance:𝑂 𝑛2
250 11/14/2022 10:59AM
P
R
E Bubble Sort
P
A
R
⚫ Bubble sort is the simplest sorting algorithm that works by repeatedly
E swapping the adjacent elementsif they are in wrong order.
D

B
Y ⚫ Algorithm:
S ⚫ Step 1 – Compare each pair of adjacent elements in the list
U ⚫ Step 2 – Swap twoelement if necessary
L
A ⚫ Step 3 – Repeat this processfor all the elements until the entire array
V
is sorted
N ⚫ Step 4 – Reduce n by 1 and go to Step 1
E
P
A
L

251 11/14/2022 10:59AM

P
R
E Bubble Sort
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

252 11/14/2022 10:59AM

P
R
E Bubble Sort – Analysis
P
A ⚫ Oneiteration of the innerloop (test and swap)requires time boundedbya constantc.
R
E
D ⚫ Twonested loops:
⚫ Outer loop – exactly n iterations
B ⚫ Inner loop
Y ⚫ Wheni=0, (n-1) iterations
⚫ Wheni=1, (n-2) iterations
S ⚫ ……
U ⚫ Wheni=(n-1),0 iterations
L
A
V ⚫ Total number of iterations= 0 + 1 + ⋯ + (𝑛 − 1) = 𝑛(𝑛 − 1)/2

N ⚫ Total time = 𝑐 ∗ 𝑛(𝑛 − 1)/2 = 𝑂(𝑛 2 )

E
P
A ⚫ Therefore,
L ⚫ Worst case– 𝑂(𝑛2 )
⚫ Best case– 𝑂(𝑛)
253 11/14/2022 10:59AM
P
R
E Shell Sort
P
A
R
⚫ Shell sort is a highly efficient sorting algorithm and is based on
E insertion sort algorithm.
D

B
Y ⚫ This algorithm avoids large shifts as in case of insertion sort, if the
S smaller value is to the far right and has to be movedto the far left.
U
L
A
V
⚫ Thisalgorithm uses insertion sort on a widely spread elements, first
to sort them and then sorts the less widely spacedelements.
N
E
P
A ⚫ This spacing is termed as interval.
L

254 11/14/2022 10:59AM

P
R
E Shell Sort – Algorithm
P
A
R
⚫ Step 1 – Initializethe gap size
E
D

B
⚫ Step 2 – Divide the array into sub-arrays of equal gap size
Y

S ⚫ Step 3 – Apply insertion sort on the sub-arrays

U
L
A
V ⚫ Step 4 – Repeat the above steps until the gap size becomes 0
N resulting into a sorted array.
E
P
A
L

P
R
E Shell Sort – Example
P
A ⚫ Example 1:
R 81 94 11 96 12 35 17
E
95 28
D 58

B
Y
⚫ Example 2:
35 33 42 10 14 19 27 44
S
U
L ⚫ Example 3:
A 12 34 54 2 3
V

N ⚫ Example 4:
E
P 80 50 60 30 10 20 40 70
A
L
⚫ Example 5:
276 60 40 10 30 50 20 11/14/2022 10:59AM
P
R
E Divide and Conquer Algorithm
P
A ⚫ Divide and Conquer is an algorithmic pattern where the designs is to take
R
E a dispute on a huge input, break the input into minor pieces, decide the
D problem on each of the small pieces, and then merge the piecewise solutions
into a global solution.
B
Y

S
⚫ This mechanism of solving the problem is called the Divide and Conquer
U Strategy.
L
A
V ⚫ Divide andConqueralgorithm consists of a disputeusingthe following
N threesteps:
E ⚫ Divide the original probleminto a set of subproblems.
P
A ⚫ Conquer– Solve every subproblemindividually,recursively.
L ⚫ Combine– Put together the solutions of the subproblemsto get the solution to
the whole problem.
260 11/14/2022 10:59AM
P
R
E Divide and Conquer Algorithm
P
A
R
E
D

B
Y

S
U
L
A
V

N
E
P
A
L

261 11/14/2022 10:59AM

P
R
E Divide and Conquer Algorithm
P
A
R
⚫ Advantages:
E ⚫ It successfully solves one of the biggest problems,such as Towerof Hanoi,
D
a mathematical puzzle.
B
Y
⚫ It efficiently uses cache memory without occupying much space because
S
U it solves simple subproblems within the cache memory instead of
L accessing the slower main memory.
A
V

N
⚫ It is more proficient than that of its counterpart Brute Forcetechnique.
E
P
A ⚫ Since these algorithms inhibit parallelism, it does not involve any
L
modification and is handled by systems incorporating parallel
279 processing. 11/14/2022 10:59AM
P
R
E Divide and Conquer Algorithm
P
A
R
⚫ Disadvantages:
E ⚫ Since most of its algorithms are designed by incorporating recursion, it
D
necessitates high memory management.
B
Y
⚫ An explicit stack mayoverusethe space.
S
U
L
A
⚫ It may even crash the system if the recursion is performed rigorously
V greater than the stack present in the CPU.
N
E
P
A
L

263 11/14/2022 10:59AM

P
R
E Divide and Conquer Algorithm
P
A
R
⚫ Examples – The specific computer algorithms are based on
E the Divide and Conquer approach
D
⚫ Maximum and Minimumproblem
B
Y
⚫ Binary search
S
U
L
A ⚫ Sorting (Merge sort, Quick sort)
V

N ⚫ Towerof Hanoi
E
P
A
L

S
U ⚫ This algorithm divides the list into three main parts:
L
A
⚫ Elements less than the Pivot element
V ⚫ Pivot element (Central element)
N ⚫ Elements greater than the pivot element
E
P
A ⚫ Pivotelementcanbeanyelementfromthearray; it canbethefirst
L
element, the last element, or any randomelement.
271 11/14/2022 10:59AM
P
R
E Quick Sort – Algorithm
P
A ⚫ Step 1 – Select a random element as a pivot and define two variables i
R
E and j as first and last elementsof the list respectively.
D

B ⚫ Step 2 – Increment i until 𝑙𝑖𝑠𝑡[𝑖] > 𝑝𝑖𝑣𝑜𝑡 then stop.

S ⚫ Step 3 – Decrement j until 𝑙𝑖𝑠𝑡[𝑗] < 𝑝𝑖𝑣𝑜𝑡 then stop.

U
L
A
V ⚫ Step 4 – If i<j then exchange list[i] and list[j].

N
E ⚫ Step 5 – Repeat steps 2, 3, and 4 until i>j.
P
A
L ⚫ Step 6 – Exchange the pivot element with list[j] element.
289 11/14/2022 10:59AM
P
R
E Quick Sort – Example
P
A ⚫ Example 1:
R
E
35 50 15 25 80 20 90 45
D
⚫ Example 2:
B
Y 7 1 3 5 2 6 4
S
U ⚫ Example 3:
L 7 6 10 5 9 2 1 15 7
A
V
⚫ Example 4:
N
E
10 15 1 2 9 6 11
P
A
⚫ Example 5:
L
60 40 10 30 50 20
273 11/14/2022 10:59AM
P
R
E Quick Sort – Analysis
P
A
R
⚫ Best Case – Pivot is alwaysthe median.
E ⚫ 𝑂 𝑛 log 𝑛
D

B
Y ⚫ Worst Case – Pivot is alwayssmallest or largest element.
S ⚫ 𝑂 𝑛2
U
L
A
V ⚫ Average Case – Pivot is random.
⚫ 𝑂 𝑛 log 𝑛
N
E
P
A
L

274 11/14/2022 10:59AM

P
R
E Heap
P
A
R
⚫ Heap is a data structure that stores a collection of objects (with keys),
E and has the following properties:
D
⚫ Complete BinaryTree
B
Y
⚫ Heap Order

S
U ⚫ The heap sort algorithmhas twomajor steps:
L
A ⚫ The first major step involvestransforming the complete tree into a heap.
V
⚫ The second major step is to perform the actual sort by extracting the
N largest or lowest element from the root and transforming the remaining
E
P treeinto a heap.
A
L

275 11/14/2022 10:59AM

P
R
E Binary Heap
P
A
R
Shape Property
E ⚫ Heap data structure is alwaysa CompleteBinaryTree.
D

B
Y ⚫ The Complete Binary Tree is a binary tree which is completely filled
S (means all the nodes has 2 children) except the last level which might
U
L
not becompletely full.
A
V

N
E
P
A
L

276 11/14/2022 10:59AM

P
R
E Binary Heap
P
A
R
Heap Property
E ⚫ All nodesareeithergreaterthan equalto (Max-Heap)or lessthan
D
equal to (Min-Heap) to eachof its child nodes.
B
Y

S ⚫ This is called heap property.

U
L
A
V

N
E
P
A
L

277 11/14/2022 10:59AM

P
R
E Heap
P
A
R
⚫ Heap is a special case of balanced binary tree data structure where
E the root-node key is compared with its children and arranged
D
accordingly.
B
Y

S ⚫ If 𝛼 has child node 𝛽, then – 𝑘𝑒𝑦 𝛼 ≥ 𝑘𝑒𝑦 𝛽

P
R
E Heap Sort – Example
P
A
R
𝑰𝒏𝒑𝒖𝒕 → 𝟒, 𝟑, 𝟕, 𝟏, 𝟖, 𝟓
E
D

B
Y

S
U
L
A
V

N
E
P
A
L 𝑺𝒐𝒓𝒕𝒆𝒅 𝑨𝒓𝒓𝒂𝒚 − 𝟏, 𝟑, 𝟒, 𝟓, 𝟕, 𝟖
293 11/14/2022 10:59AM
P
R
E Efficiency of Sorting Algorithm
P
A ⚫ The complexity of a sorting algorithm measuresthe running time of
R
E a function in which 𝑛 number of items are to besorted.
D

B
Y ⚫ The choice of sorting method depends on efficiency considerations for
S different problems.
U
L
A
V
⚫ The most important of these considerations are:
⚫ The length of time spent byprogrammerin coding a particular sorting
N
E program.
P ⚫ Amount of machine time necessary for running the program.
A
L ⚫ The amount of memory necessary for running the program.
294 11/14/2022 10:59AM
P
R
E Efficiency of Sorting Algorithm
P
A ⚫ Varioussortingmethodsareanalyzedin thecaseslike – best case, averagecase, or worst
R case.
E
D
⚫ Mostof the sort methods we consider have requirements that range from 𝑂(𝑛 log 𝑛) to
B 𝑂 𝑛2 .
Y
⚫ Asort should not be selected only becauseits sorting time is 𝑂(𝑛 log 𝑛); the relation of
S the file size 𝑛 and the other factorsaffecting the actual sorting time must beconsidered.
U
L
A ⚫ Determining the time requirementof sorting technique is to actually run the programand
V measureits efficiency.

N
⚫ Once a particular sorting technique is selected the needis to make the programasefficient
E
P
as possible.
A
L ⚫ Any improvement in sortingtimesignificantlyaffect the overall efficiency and savesa
great deal of computer time.
295 11/14/2022 10:59AM
P
R
E Efficiency of Sorting Algorithm
P
A
R Time Complexity
E Algorithm Data Structure
D Best Average Worst
B
Y Quick Sort Array 𝑂 𝑛 log 𝑛 𝑂 𝑛 log 𝑛 𝑂 𝑛2

S Merge Sort Array 𝑂 𝑛 log 𝑛 𝑂 𝑛 log 𝑛 𝑂 𝑛 log 𝑛

U
L
A
Heap Sort Array 𝑂 𝑛 log 𝑛 𝑂 𝑛 log 𝑛 𝑂 𝑛 log 𝑛
V
Bubble Sort Array 𝑂 𝑛 𝑂 𝑛2 𝑂 𝑛2
N
E Array
Insertion Sort 𝑂 𝑛 𝑂 𝑛2 𝑂 𝑛2
P
A
L Selection Sort Array 𝑂 𝑛2 𝑂 𝑛2 𝑂 𝑛2

296 11/14/2022 10:59AM

n-gl.com

CH 1 Introduction
No ratings yet
CH 1 Introduction
45 pages
DSA Notes 3rd Sem
No ratings yet
DSA Notes 3rd Sem
32 pages
Data Structure Module 1
No ratings yet
Data Structure Module 1
87 pages
Module I
No ratings yet
Module I
115 pages
24BTPCCX22 - Data Structure Notes - FINAL
No ratings yet
24BTPCCX22 - Data Structure Notes - FINAL
57 pages
Data Structure Lecture 1
No ratings yet
Data Structure Lecture 1
39 pages
Introduction 1
No ratings yet
Introduction 1
20 pages
Introduction To Data Structure
No ratings yet
Introduction To Data Structure
131 pages
CH 1 DSA-1
No ratings yet
CH 1 DSA-1
48 pages
Data Structures for CS Students
No ratings yet
Data Structures for CS Students
40 pages
Ilovepdf Merged
No ratings yet
Ilovepdf Merged
111 pages
DataStructure and AlgorithmEDITED
No ratings yet
DataStructure and AlgorithmEDITED
22 pages
DS Unit - 1
No ratings yet
DS Unit - 1
47 pages
DS Module 01 Part 01
No ratings yet
DS Module 01 Part 01
38 pages
Tos 055126
No ratings yet
Tos 055126
21 pages
Introduction to Data Structures
No ratings yet
Introduction to Data Structures
21 pages
Introduction of Data Structure
No ratings yet
Introduction of Data Structure
25 pages
E-Note 4003 Content Document 20240914115506AM
No ratings yet
E-Note 4003 Content Document 20240914115506AM
42 pages
Unit 1 Notes
No ratings yet
Unit 1 Notes
25 pages
DD 34
No ratings yet
DD 34
21 pages
Introduction To DataStructurePpt
No ratings yet
Introduction To DataStructurePpt
27 pages
Lecture # 0 Data - Structures - and - Algorithm
No ratings yet
Lecture # 0 Data - Structures - and - Algorithm
53 pages
Unit-1 Notes - Data Structure
No ratings yet
Unit-1 Notes - Data Structure
149 pages
Overview of Data Structures
No ratings yet
Overview of Data Structures
16 pages
Lecture 1 Introduction To DSA
No ratings yet
Lecture 1 Introduction To DSA
27 pages
ch#1
No ratings yet
ch#1
37 pages
Unit 1.1 Introduction
No ratings yet
Unit 1.1 Introduction
41 pages
Data Structure PP T
No ratings yet
Data Structure PP T
16 pages
Unit 1 Part 1 Revised 2024
No ratings yet
Unit 1 Part 1 Revised 2024
138 pages
DSA M01 C01 SLM Basics of Data Structure
No ratings yet
DSA M01 C01 SLM Basics of Data Structure
40 pages
DS Unit 1
No ratings yet
DS Unit 1
50 pages
Introduction to Data Structures
No ratings yet
Introduction to Data Structures
146 pages
5.algorithm Design and Data Structures
No ratings yet
5.algorithm Design and Data Structures
64 pages
Lecture-01-03 (Data Structures, Types and Operations) - 1
No ratings yet
Lecture-01-03 (Data Structures, Types and Operations) - 1
41 pages
5.algorithm Design and Data Structures
No ratings yet
5.algorithm Design and Data Structures
106 pages
Introduction
No ratings yet
Introduction
41 pages
MSA Data Structure Presentation
No ratings yet
MSA Data Structure Presentation
25 pages
Data Structures and Algorithms Overview
No ratings yet
Data Structures and Algorithms Overview
35 pages
Data Structure PPT
No ratings yet
Data Structure PPT
20 pages
Dcap201 Fundamentals of Data Structures
No ratings yet
Dcap201 Fundamentals of Data Structures
270 pages
Introduction
No ratings yet
Introduction
22 pages
Introdunction of Data Structure
No ratings yet
Introdunction of Data Structure
5 pages
Ok CMPE 30052 DATA STRUCTURES AND ALGORITHM 1
No ratings yet
Ok CMPE 30052 DATA STRUCTURES AND ALGORITHM 1
90 pages
0.introduction To DS - Sorting - Searching
No ratings yet
0.introduction To DS - Sorting - Searching
79 pages
Introduction to Data Structures Basics
No ratings yet
Introduction to Data Structures Basics
17 pages
Chapter 1 - Overview of Algorithm and Data Structures
No ratings yet
Chapter 1 - Overview of Algorithm and Data Structures
32 pages
Inroduction To DSA
No ratings yet
Inroduction To DSA
33 pages
Lecture 01 Intro
No ratings yet
Lecture 01 Intro
27 pages
Introduction to Data Structures & Algorithms
No ratings yet
Introduction to Data Structures & Algorithms
76 pages
Basics of Data Structure
No ratings yet
Basics of Data Structure
11 pages
Double Hashing in Open Addressing
No ratings yet
Double Hashing in Open Addressing
131 pages
Ds Notes
No ratings yet
Ds Notes
131 pages
Data Structures & Algorithms Guide
No ratings yet
Data Structures & Algorithms Guide
46 pages
Introduction to Data Structures in C
No ratings yet
Introduction to Data Structures in C
9 pages
Array Element Representation Explained
No ratings yet
Array Element Representation Explained
34 pages
Data Structures & Algorithms Guide
No ratings yet
Data Structures & Algorithms Guide
4 pages
Data Structures and Algorithm-1
No ratings yet
Data Structures and Algorithm-1
306 pages
Determine Sample Size
No ratings yet
Determine Sample Size
1 page
Introduction To Probability
No ratings yet
Introduction To Probability
14 pages
Theory
No ratings yet
Theory
11 pages
Introduction To Statistics
No ratings yet
Introduction To Statistics
17 pages
Schematic Lenovo A706 PDF
No ratings yet
Schematic Lenovo A706 PDF
27 pages
Integrated Marketing Strategy for FBC
No ratings yet
Integrated Marketing Strategy for FBC
5 pages
Unidad 10: Formas Perfectas: Textos
No ratings yet
Unidad 10: Formas Perfectas: Textos
23 pages
Cash Back Model List
No ratings yet
Cash Back Model List
5 pages
Shopify Affiliate
No ratings yet
Shopify Affiliate
12 pages
IC Packaging and Assembly Overview
100% (2)
IC Packaging and Assembly Overview
115 pages
117FZ112017
No ratings yet
117FZ112017
3 pages
Doc-0116 Pads Generic
100% (1)
Doc-0116 Pads Generic
126 pages
Gafunk Pricelist
No ratings yet
Gafunk Pricelist
2 pages
10-Volume of Pyramids and Cones
No ratings yet
10-Volume of Pyramids and Cones
4 pages
TEAM 11 LOT 72 - Case 2 - Miroglio Fashion
No ratings yet
TEAM 11 LOT 72 - Case 2 - Miroglio Fashion
5 pages
Memory Management: Practice Exercise
No ratings yet
Memory Management: Practice Exercise
3 pages
Question Bank For Microsoft Word
No ratings yet
Question Bank For Microsoft Word
9 pages
Tech Enthusiasts' RAM & Storage Guide
No ratings yet
Tech Enthusiasts' RAM & Storage Guide
4 pages
B Frames
No ratings yet
B Frames
2 pages
Log
No ratings yet
Log
268 pages
NGO Darpan
No ratings yet
NGO Darpan
13 pages
PC Pro - May 2024 UK
No ratings yet
PC Pro - May 2024 UK
132 pages
EPay Registration: Document Guidelines
No ratings yet
EPay Registration: Document Guidelines
2 pages
Informatica Tutorial
No ratings yet
Informatica Tutorial
91 pages
Xen Virtualization Guide
No ratings yet
Xen Virtualization Guide
5 pages
Digital Channels Issues
No ratings yet
Digital Channels Issues
6 pages
221TCS100 Advanced Machine Learning, December 2023
No ratings yet
221TCS100 Advanced Machine Learning, December 2023
4 pages
40646EN Cantar Automat Siloz
No ratings yet
40646EN Cantar Automat Siloz
6 pages
GIS Database Design for Village Land
No ratings yet
GIS Database Design for Village Land
10 pages
DiscreteTime Fourier Transform - PDF
No ratings yet
DiscreteTime Fourier Transform - PDF
5 pages
Price List
No ratings yet
Price List
1 page
DIY Pirate Impulse Metal Detector Guide
100% (2)
DIY Pirate Impulse Metal Detector Guide
12 pages
FYP THESIS Uet PDF
No ratings yet
FYP THESIS Uet PDF
45 pages
CO2 Corrosion Rate Calculation Model
No ratings yet
CO2 Corrosion Rate Calculation Model
18 pages