1.

1 Data Types System defines data types, User defined data types

Data Types
A data type specifies the type of data that a variable can store such as integer, floating, character,
etc.

There are the following data types in C language.

Types Data Types

Basic Data Type int, char, float, double

Derived Data Type array, pointer, structure, union

Enumeration Data Type enum

Void Data Type void

Basic Data Types

The basic data types are integer-based and floating-point based. C language supports both signed
and unsigned literals.

The memory size of the basic data types may change according to 32 or 64-bit operating system.

Let's see the basic data types. Its size is given according to 32-bit architecture.

Data Types Memory Size Range

Char 1 byte −128 to 127

signed char 1 byte −128 to 127

unsigned char 1 byte 0 to 255

short 2 byte −32,768 to 32,767

 signed short 2 byte −32,768 to 32,767

unsigned short 2 byte 0 to 65,535

Int 2 byte −32,768 to 32,767

signed int 2 byte −32,768 to 32,767

unsigned int 2 byte 0 to 65,535

short int 2 byte −32,768 to 32,767

signed short int 2 byte −32,768 to 32,767

unsigned short int 2 byte 0 to 65,535

long int 4 byte -2,147,483,648 to 2,147,483,647

signed long int 4 byte -2,147,483,648 to 2,147,483,647

unsigned long int 4 byte 0 to 4,294,967,295

Float 4 byte

double 8 byte

long double 10 byte

Int:
Integers are entire numbers without any fractional or decimal parts, and the int data type is used
to represent them.

It is frequently applied to variables that include values, such as counts, indices, or other
numerical numbers. The int data type may represent both positive and negative numbers because
it is signed by default.
 An int takes up 4 bytes of memory on most devices, allowing it to store values between around -2
billion and +2 billion.

Char:
Individual characters are represented by the char data type. Typically used to
hold ASCII or UTF-8 encoding scheme characters, such as letters, numbers, symbols,
or commas. There are 256 characters that can be represented by a single char, which takes up
one byte of memory. Characters such as 'A', 'b', '5', or '$' are enclosed in single quotes.

Float:
To represent integers, use the floating data type. Floating numbers can be used to represent
fractional units or numbers with decimal places.

The float type is usually used for variables that require very good precision but may not be very
precise. It can store values with an accuracy of about 6 decimal places and a range of about 3.4 x
1038 in 4 bytes of memory.

Double:
Use two data types to represent two floating integers. When additional precision is needed, such
as in scientific calculations or financial applications, it provides greater accuracy compared to
float.

Double type, which uses 8 bytes of memory and has an accuracy of about 15 decimal places,
yields larger values. C treats floating point numbers as doubles by default if no explicit type is
supplied.

1. int age = 25;

2. char grade = 'A';
3. float temperature = 98.6;
4. double pi = 3.14159265359;
Test it Now
In the example above, we declare four variables: an int variable for the person's age, a char
variable for the student's grade, a float variable for the temperature reading, and two variables for
the number pi.

Derived Data Type

Beyond the fundamental data types, C also supports derived data types, including arrays,
pointers, structures, and unions. These data types give programmers the ability to handle
heterogeneous data, directly modify memory, and build complicated data structures.

Array:
An array, a derived data type, lets you store a sequence of fixed-size elements of the same type.
It provides a mechanism for joining multiple targets of the same data under the same name.
 The index is used to access the elements of the array, with a 0 index for the first entry. The size
of the array is fixed at declaration time and cannot be changed during program execution. The
array components are placed in adjacent memory regions.

System defines data types

A system-defined data type is a data object that is set up for housekeeping during program
execution and is not directly accessible by the program. For example, run-time storage stacks
are system-defined data objects.
Data types are attributes that can be predefined or created by the user to help a program
detect different types of information. They are useful because computers can only understand
binary language, which is made up of 0s and 1s. Data types are used to tell the Memory
Management Unit (MMU) how much memory is required to store data before the program
compiles.

User defined data types

A user-defined data type (UDT) is a data type that is created by extending an existing data
type to create a customized data type. UDTs are separate and incompatible from the built-in
data types they are derived from.

Here are some examples of UDTs:

 Distinct type
A UDT that shares its internal representation with a built-in data type, but is considered a
separate data type for most operations.
 Array type
A UDT that consists of an ordered set of elements from a single built-in data type.
Here are some things to keep in mind about UDTs:
 UDTs cannot be used as arguments for most built-in functions. To use UDTs with built-in
functions, user-defined functions must be provided.
 When reading from or writing to a relational source or target that contains UDTs, a
conversion method must be provided so that the data can be processed correctly.
 A properties file can be configured to define how to convert UDTs. A separate properties file
is required for each type of database used as a source or target.

1.2 Basic concept of data structure

An Introduction to Data Structures

Since the invention of computers, people have been using the term "Data" to refer to Computer
Information, either transmitted or stored. However, there is data that exists in order types as well.
Data can be numbers or texts written on a piece of paper, in the form of bits and bytes stored
inside the memory of electronic devices, or facts stored within a person's mind. As the world
started modernizing, this data became a significant aspect of everyone's day-to-day life, and
various implementations allowed them to store it differently.

Data is a collection of facts and figures or a set of values or values of a specific format that refers
to a single set of item values. The data items are then classified into sub-items, which is the group
of items that are not known as the simple primary form of the item.

Let us consider an example where an employee name can be broken down into three sub-items:
First, Middle, and Last. However, an ID assigned to an employee will generally be considered a
single item.

Figure 1: Representation of Data Items

What is Data Structure?

Data Structure is a branch of Computer Science. The study of data structure allows us to
understand the organization of data and the management of the data flow in order to increase the
efficiency of any process or program. Data Structure is a particular way of storing and organizing
data in the memory of the computer so that these data can easily be retrieved and efficiently
utilized in the future when required. The data can be managed in various ways, like the logical or
mathematical model for a specific organization of data is known as a data structure.

The scope of a particular data model depends on two factors:

1. First, it must be loaded enough into the structure to reflect the definite correlation of the data with
a real-world object.
2. Second, the formation should be so straightforward that one can adapt to process the data
efficiently whenever necessary.

Linear data structure

A linear data structure is a structure in which the elements are stored sequentially, and the
elements are connected to the previous and the next element. As the elements are stored
sequentially, so they can be traversed or accessed in a single run. The implementation of linear
data structures is easier as the elements are sequentially organized in memory. The data elements
in an array are traversed one after another and can access only one element at a time.

The types of linear data structures are Array, Queue, Stack, Linked List.
Let's discuss each linear data structure in detail.

o Array: An array consists of data elements of a same data type. For example, if we want to
store the roll numbers of 10 students, so instead of creating 10 integer type variables, we will
create an array having size 10. Therefore, we can say that an array saves a lot of memory and
reduces the length of the code.
o Stack: It is linear data structure that uses the LIFO (Last In-First Out) rule in which the data
added last will be removed first. The addition of data element in a stack is known as a push
operation, and the deletion of data element form the list is known as pop operation.
o Queue: It is a data structure that uses the FIFO rule (First In-First Out). In this rule, the
element which is added first will be removed first. There are two terms used in the
queue front end and rear The insertion operation performed at the back end is known ad
enqueue, and the deletion operation performed at the front end is known as dequeue.
o Linked list: It is a collection of nodes that are made up of two parts, i.e., data element and
reference to the next node in the sequence.
Non-linear data structure
A non-linear data structure is also another type of data structure in which the data elements are
not arranged in a contiguous manner. As the arrangement is nonsequential, so the data elements
cannot be traversed or accessed in a single run. In the case of linear data structure, element is
connected to two elements (previous and the next element), whereas, in the non-linear data
structure, an element can be connected to more than two elements.

Trees and Graphs are the types of non-linear data structure.

Let's discuss both the data structures in detail.

o Tree
It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree
structure that forms a parent-child relationship. The diagrammatic representation of a tree data
structure is shown below:
For example, the posts of employees are arranged in a tree data structure like managers, officers,
clerk. In the above figure, A represents a manager, B and C represent the officers, and other
nodes represent the clerks.

o Graph
A graph is a non-linear data structure that has a finite number of vertices and edges, and these
edges are used to connect the vertices. The vertices are used to store the data elements, while the
edges represent the relationship between the vertices. A graph is used in various real-world
problems like telephone networks, circuit networks, social networks like LinkedIn, Facebook. In
the case of facebook, a single user can be considered as a node, and the connection of a user with
others is known as edges.

Differences between the Linear data structure and non-linear data

structure.
 Abstract data types

What is abstract data type?

An abstract data type is an abstraction of a data structure that provides only the interface to which
the data structure must adhere. The interface does not give any specific details about something
should be implemented or in what programming language.

In other words, we can say that abstract data types are the entities that are definitions of data and
operations but do not have implementation details. In this case, we know the data that we are
storing and the operations that can be performed on the data, but we don't know about the
implementation details. The reason for not having implementation details is that every
programming language has a different implementation strategy for example; a C data structure is
implemented using structures while a C++ data structure is implemented using objects and
classes.

For example, a List is an abstract data type that is implemented using a dynamic array and linked
list. A queue is implemented using linked list-based queue, array-based queue, and stack-based
queue. A Map is implemented using Tree map, hash map, or hash table.

Abstract data type model

Before knowing about the abstract data type model, we should know about abstraction and
encapsulation.

Abstraction: It is a technique of hiding the internal details from the user and only showing the
necessary details to the user.

Encapsulation: It is a technique of combining the data and the member function in a single unit is
known as encapsulation.

The above figure shows the ADT model. There are two types of models in the ADT
1.3 Algorithm and its analysis -

Introduction of algorithm
An algorithm is a process or a set of rules required to perform calculations or some other
problem-solving operations especially by a computer. The formal definition of an algorithm is
that it contains the finite set of instructions which are being carried in a specific order to perform
the specific task. It is not the complete program or code; it is just a solution (logic) of a problem,
which can be represented either as an informal description using a Flowchart or Pseudocode.

Characteristics of an Algorithm
The following are the characteristics of an algorithm:

o Input: An algorithm has some input values. We can pass 0 or some input value to an
algorithm.
o Output: We will get 1 or more output at the end of an algorithm.
o Unambiguity: An algorithm should be unambiguous which means that the
instructions in an algorithm should be clear and simple.
o Finiteness: An algorithm should have finiteness. Here, finiteness means that the
algorithm should contain a limited number of instructions, i.e., the instructions should
be countable.
o Effectiveness: An algorithm should be effective as each instruction in an algorithm
affects the overall process.
o Language independent: An algorithm must be language-independent so that the
instructions in an algorithm can be implemented in any of the languages with the
same output.

Dataflow of an Algorithm
o Problem: A problem can be a real-world problem or any instance from the real-world
problem for which we need to create a program or the set of instructions. The set of
instructions is known as an algorithm.
o Algorithm: An algorithm will be designed for a problem which is a step by step
procedure.
o Input: After designing an algorithm, the required and the desired inputs are provided
to the algorithm.
o Processing unit: The input will be given to the processing unit, and the processing
unit will produce the desired output.
o Output: The output is the outcome or the result of the program.

Why do we need Algorithms?

We need algorithms because of the following reasons:

o Scalability: It helps us to understand the scalability. When we have a big real-world

problem, we need to scale it down into small-small steps to easily analyze the
problem.
 o Performance: The real-world is not easily broken down into smaller steps. If the
problem can be easily broken into smaller steps means that the problem is feasible.
Let's understand the algorithm through a real-world example. Suppose we want to make a lemon
juice, so following are the steps required to make a lemon juice:

Step 1: First, we will cut the lemon into half.

Step 2: Squeeze the lemon as much you can and take out its juice in a container.

Step 3: Add two tablespoon sugar in it.

Step 4: Stir the container until the sugar gets dissolved.

Step 5: When sugar gets dissolved, add some water and ice in it.

Step 6: Store the juice in a fridge for 5 to minutes.

Step 7: Now, it's ready to drink.

Time Complexity of algorithm

o Time complexity: The time complexity of an algorithm is the amount of time
required to complete the execution. The time complexity of an algorithm is denoted
by the big O notation. Here, big O notation is the asymptotic notation to represent the
time complexity. The time complexity is mainly calculated by counting the number of
steps to finish the execution. Let's understand the time complexity through an
example.
1. sum=0;
2. // Suppose we have to calculate the sum of n numbers.
3. for i=1 to n
4. sum=sum+i;
5. // when the loop ends then sum holds the sum of the n numbers
6. return sum;
In the above code, the time complexity of the loop statement will be atleast n, and if the value of
n increases, then the time complexity also increases. While the complexity of the code, i.e., return
sum will be constant as its value is not dependent on the value of n and will provide the result in
one step only. We generally consider the worst-time complexity as it is the maximum time taken
for any given input size.

Space Complexity of algorithm

o Space complexity: An algorithm's space complexity is the amount of space required
to solve a problem and produce an output. Similar to the time complexity, space
complexity is also expressed in big O notation.
 For an algorithm, the space is required for the following purposes:

1. To store program instructions

2. To store constant values
3. To store variable values
4. To track the function calls, jumping statements, etc.

Auxiliary space: The extra space required by the algorithm, excluding the input size, is known as
an auxiliary space. The space complexity considers both the spaces, i.e., auxiliary space, and
space used by the input.

Worst case analysis, Best case analysis, Average case analysis

Best case, worst case, and average case analyses are methods used in computer
science to evaluate an algorithm's efficiency under different conditions:
 Best case analysis
Determines the minimum time or resources required for an algorithm to complete its
task. This is the scenario where the algorithm performs its task under the most favorable
conditions.
 Worst case analysis
Determines the maximum time or resources required for an algorithm to complete its
task. This is the scenario where the algorithm experiences instability or has inputs that
produce particularly bad results.
 Average case analysis
Determines the algorithm's performance under "typical" or "average" conditions. This is
often more complex to compute than the other analyses because it requires understanding of
how the inputs are distributed.
The resource being considered is usually running time, but could also be memory
or some other resource.
1.4 Asymptotic Notation Big-O Notation, Omega- Ω Notation, Theta
Notation

1. Theta Notation (Θ-Notation) :

Theta notation encloses the function from above and below. Since it represents
the upper and the lower bound of the running time of an algorithm, it is used for
analyzing the average-case complexity of an algorithm.
.Theta (Average Case) You add the running times for each possible input
combination and take the average in the average case.
Let g and f be the function from the set of natural numbers to itself. The function
f is said to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such
that c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0

Theta notation

Mathematical Representation of Theta notation:

Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 *
g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
Note: Θ(g) is a set
The above expression can be described as if f(n) is theta of g(n), then the value
f(n) is always between c1 * g(n) and c2 * g(n) for large values of n (n ≥ n0). The
definition of theta also requires that f(n) must be non-negative for values of n
greater than n0.
The execution time serves as both a lower and upper bound on the
algorithm’s time complexity.
It exist as both, most, and least boundaries for a given input value.
A simple way to get the Theta notation of an expression is to drop low-order
terms and ignore leading constants. For example, Consider the expression 3n3 +
6n2 + 6000 = Θ(n3), the dropping lower order terms is always fine because there
will always be a number(n) after which Θ(n 3) has higher values than Θ(n2)
irrespective of the constants involved. For a given function g(n), we denote
Θ(g(n)) is following set of functions.
Examples :
{ 100 , log (2000) , 10^4 } belongs to Θ(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Θ(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Θ( n2)
Note: Θ provides exact bounds.
2. Big-O Notation (O-notation) :
Big-O notation represents the upper bound of the running time of an algorithm.
Therefore, it gives the worst-case complexity of an algorithm.
.It is the most widely used notation for Asymptotic analysis.
.It specifies the upper bound of a function.
.The maximum time required by an algorithm or the worst-case time complexity.
.It returns the highest possible output value(big-O) for a given input.
.Big-O(Worst Case) It is defined as the condition that allows an algorithm to
complete statement execution in the longest amount of time possible.

If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a
positive constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
It returns the highest possible output value (big-O)for a given input.
The execution time serves as an upper bound on the algorithm’s time
complexity.

Mathematical Representation of Big-O Notation:

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n)
for all n ≥ n0 }
For example, Consider the case of Insertion Sort. It takes linear time in the best
case and quadratic time in the worst case. We can safely say that the time
complexity of the Insertion sort is O(n 2).
Note: O(n2) also covers linear time.
If we use Θ notation to represent the time complexity of Insertion sort, we have to
use two statements for best and worst cases:
 The worst-case time complexity of Insertion Sort is Θ(n 2).
 The best case time complexity of Insertion Sort is Θ(n).
The Big-O notation is useful when we only have an upper bound on the time
complexity of an algorithm. Many times we easily find an upper bound by simply
looking at the algorithm.
Examples :
{ 100 , log (2000) , 10^4 } belongs to O(1)
U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to O(n)
U { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to O( n^2)
Note: Here, U represents union, we can write it in these manner because O
provides exact or upper bounds .
3. Omega Notation (Ω-Notation):
 Omega notation represents the lower bound of the running time of an algorithm.
Thus, it provides the best case complexity of an algorithm.
The execution time serves as a lower bound on the algorithm’s time
complexity.
It is defined as the condition that allows an algorithm to complete statement
execution in the shortest amount of time.
Let g and f be the function from the set of natural numbers to itself. The function
f is said to be Ω(g), if there is a constant c > 0 and a natural number n0 such that
c*g(n) ≤ f(n) for all n ≥ n0

Mathematical Representation of Omega notation :

Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n)
for all n ≥ n0 }

1.5 Time complexity of recursive algorithm

The time complexity of a recursive algorithm depends on the number of times the
function calls itself:
 O(2^N): If a function calls itself twice
 O(3^N): If a function calls itself three times
 O(N): If a recursive function of input N is called N times
To determine the time complexity of a recursive algorithm, you can consider the
number of operations performed as a function of the input size. For example, the
time complexity of the factorial function is O(n) because the number of
multiplications is directly proportional to n.

Basic concept of recursion

Recursion is defined as a process which calls itself directly or indirectly and the
corresponding function is called a recursive function.

Properties of Recursion:

Recursion has some important properties. Some of which are mentioned below:
 The primary property of recursion is the ability to solve a problem by breaking
it down into smaller sub-problems, each of which can be solved in the same
way.
 A recursive function must have a base case or stopping criteria to avoid
infinite recursion.
 Recursion involves calling the same function within itself, which leads to a
call stack.
 Recursive functions may be less efficient than iterative solutions in terms of
memory and performance.

Types of Recursion:

1. Direct recursion: When a function is called within itself directly it is called

direct recursion. This can be further categorised into four types:
 Tail recursion,
 Head recursion,
 Tree recursion and
 Nested recursion.
2. Indirect recursion: Indirect recursion occurs when a function calls another
function that eventually calls the original function and it forms a cycle.

Applications of Recursion:

Recursion is used in many fields of computer science and mathematics, which

includes:
 Searching and sorting algorithms: Recursive algorithms are used to search and
sort data structures like trees and graphs.
 Mathematical calculations: Recursive algorithms are used to solve problems
such as factorial, Fibonacci sequence, etc.
 Compiler design: Recursion is used in the design of compilers to parse and
analyze programming languages.
 Graphics: many computer graphics algorithms, such as fractals and the
Mandelbrot set, use recursion to generate complex patterns.
 Artificial intelligence: recursive neural networks are used in natural language
processing, computer vision, and other AI applications.
Advantages of Recursion:

 Recursion can simplify complex problems by breaking them down into

smaller, more manageable pieces.
 Recursive code can be more readable and easier to understand than iterative
code.
 Recursion is essential for some algorithms and data structures.
 Also with recursion, we can reduce the length of code and become more
readable and understandable to the user/ programmer.

Disadvantages of Recursion:

 Recursion can be less efficient than iterative solutions in terms of memory and
performance.
 Recursive functions can be more challenging to debug and understand than
iterative solutions.
 Recursion can lead to stack overflow errors if the recursion depth is too high.