Data Structure and Algorithms(DSA)
.png)
Data Types:
Data type is defined as the way how to represent different types of data in programming is called data type.
•C programming language supports four classes of data types:
a. Primary or fundamental data types
b. User-defined data types [type definition].
c. Derived data types [arrays, structure, union, pointers, functions]
d. Empty data set [void : used in functions]
a. Primary Data Types are:
- Integer:
1. Signed type
• int, short int ,long int
2. Unsigned type
•unsigned int, unsigned short int, unsigned long int
- Character:
1. signed char
2. unsigned char
- Floating Point Type:
float, double, long double
Primary data types and examples:
• int for integer type.
• Example : 12,4,162
•float for fractional number with precision 6
•Example: 65.452136, 85.123
•double for fractional number with precision 14
•Example: 452.12345678987456, 52.3211
•long double for fractional numbers with precision 18
•Example: 987.12345789874563214, 58.123456
•char for character type
•Example : ‘m’, ‘d’, ‘@’, ‘4’, ‘A’
.png)
Memory size of data type
•The memory size occupied by a particular data type is machine dependent based on the world size of the machine. Memory size mentioned in the previous slide is for 16 bit word size.
•For example:
The size of memory for int is equivalent to word size of machine i.e., 2 byte for 16 bit machine and 4 byte for 32 bit machine
User defined type declaration
In C language a user can define an identifier that represents an existing data type. The user defined datatype identifier can later be used to declare variables.
•The general syntax is : typedef type identifier;
-here type represents existing data type and identifier refers to the “new” name given to the data type.
Example: typedef int units;
typedef float average;
•Here units symbolizes int and average symbolizes float.
•They can be later used to declare variables as follows:
units dept1, dept2;
average section1, section2;
Therefore dept1 and dept2 are indirectly declared as integer datatype and section1 and section2 are indirectly float data type.
Tasks involved while writing computer program to solve a problem:
1. Identify the data elements involved in the solution and describe the relationship between them.
2. Decide on the operations that must be performed on these data elements.
3. Choose or decide a best method of representing these data elements in computer’s memory retaining their relationships described in (1) and enabling the operations decided in (2).
4. Choose a programming language that can efficiently code the above representation.
Data Structure :
A data structure is a way of organizing data elements along with the logical relationship between them. Examples of data structures are : arrays, records, lists, files etc. The data types like integer, real, character etc. are considered as primitive data structure. Once the data structure is defined, next we define the operations that can be performed on them. Example: create the data structure, destroy it, insert elements in to it, remove elements from it etc.
The operations can be implemented through basic instructions available in programming language or through special algorithmic process. The third task is representation of the data structure in computer’s memory which is called storage structure. A storage structure is simply a memory configuration of a data structure.
When the storage structure is selected in auxiliary/secondary memory then it is known as file structure. Data structure is an agreement about: how to store a collection of data elements in memory, what operations we can perform on that data, the algorithms for those operations, and how time and space efficient those algorithms are.
Data Structure Applications Example:
Data Structure mainly concerned with “How do we organize information so that we can find, update, add, and delete portions of it efficiently?”
•Example Applications:
•How does Google quickly find web pages that contain a search term?
•What’s the fastest way to broadcast a message to a network of computers?
•How can a subsequence of DNA be quickly found within the genome?
•How does your operating system track which memory (disk or RAM) is free?
Classification of Data Structure:
Data structures are generally categorized into two classes:
1. primitive and
2. non-primitive data structures
1. Primitive Data Structures
Primitive data structures are the fundamental data types which are supported by a programming language. Some basic data types are integer, real, character, and Boolean. The terms ‘data type’, ‘basic data type’, and ‘primitive data type’ are often used interchangeably.
2. Non-Primitive Data Structures
Non-primitive data structures are those data structures which are created using primitive data structures. Examples of such data structures include linked lists, stacks, trees, and graphs. Non-primitive data structures can further be classified into two categories:
a. linear and
b. non-linear data structures.
•Linear and Non-linear Structures
If the elements of a data structure are stored in a linear or sequential order, then it is a linear data structure. Examples include arrays, linked lists, stacks, and queues. Linear data structures can be represented in memory in two different ways.
1. One way is to have to a linear relationship between elements by means of sequential memory locations.
2. The other way is to have a linear relationship between elements by means of links.
However, if the elements of a data structure are not stored in a sequential order, then it is a non-linear data structure. The relationship of adjacency is not maintained between elements of a non-linear data structure. Examples include trees and graphs.
Operations on Data Structure:
a. Traversing
Traversing means to access each data item exactly once so that it can be processed. For example, to print the names of all the students in a class.
b. Searching
Searching is used to find the location of one or more data items that satisfy the given constraint. Such a data item may or may not be present in the given collection of data items. For example, to find the names of all the students who secured 100 marks in mathematics.
c. Inserting
Inserting is used to add new data items to the given list of data items. For example, to add the details of a new student who has recently joined the course.
d. Deleting
Deleting means to remove (delete) a particular data item from the given collection of data items. For example, to delete the name of a student who has left the course.
e. Sorting
In Sorting data items can be arranged in some order like ascending order or descending order depending on the type of application. For example, arranging the names of students in a class in an alphabetical order, or calculating the top three winners by arranging the participants’ scores in descending order and then extracting the top three.
f. Merging
Merging is lists of two sorted data items can be combined to form a single list of sorted data items. Generally, two or more operations are applied simultaneously in a given situation. For example, if we want to delete the details of a student whose name is X, then we first have to search the list of students to find whether the record of X exists or not and if it exists then at which location, so that the details can be deleted from that particular location.
Abstract Data Types (ADT):
•Data type
Data type of a variable is the set of values that the variable can take. Example: primitive/ built-in data type : int, char, float, and double. We actually consider two things: a data item with certain characteristics and the permissible operations on that data. For example, an int variable can contain any whole-number value from –32768 to 32767 and can be operated with the operators +, –, *, and /. The operations that can be performed on a data type are an inseparable part of its identity. Therefore, when we declare a variable of an abstract data type (e.g., stack or a queue), we also need to specify the operations that can be performed on it.
Abstract
The word ‘abstract’ in the context of data structures means considered apart from the detailed specifications or implementation. It can be thought of as a ‘description’ of the data elements with a list of operations that can be performed on the data.
Abstract Data Types (ADT):
An abstract data type (ADT) is the way we look at a data structure, focusing on what it does and ignoring how it does its job. For example, stacks and queues. We can implement both these ADTs using an array or a linked list. The end-user is not concerned about the details of how the methods carry out their tasks. They are only aware of the methods that are available to them.
For example, when users use a stack, the user is concerned only with the type of data and the operations that can be performed on it. Therefore, the fundamentals of how the data is stored should be invisible to the user. The users should just know that to work with stacks, they have push() and pop() functions available to them. Using these functions, they can manipulate the data (insertion or deletion) stored in the stack.
Advantage of using ADTs:
•Encapsulation
The user does not need any technical knowledge of how the implementation works to use the ADT. The implementation may be complex but will be encapsulated in a simple interface when it is actually used.
•Localization of change
Implementations of ADTs can be changed (e.g., for efficiency) without requiring changes to the program that uses the ADTs.
•Flexibility
Different implementations of the ADT, having all the same properties and abilities, are equivalent and may be used somewhat interchangeably in code that uses the ADT. This gives a great deal of flexibility when using ADT objects in different situations. For example, stack can be implemented using array as well as linked list.
Brief introduction to Recursion:
Recursion
Recursion is a process by which a function calls itself repeatedly until some specified condition is satisfied. A recursive function is one that calls itself directly or indirectly to solve a smaller version of its task until a final call which does not require a self-call.
Basic Rules of Recursion
Every recursive solution has two major cases.
a. Base case
Base case in which the problem is simple enough to be solved directly without making any further calls to the same function.
b. Recursive case
Recursive case in which first the problem at hand is divided into simpler sub-parts. Second the function calls itself but with sub-parts of the problem obtained in the first step. Third, the result is obtained by combining the solutions of simpler sub-parts.
Therefore, recursion is defining large and complex problems in terms of smaller and more easily solvable problems.
Example: A program to find the factorial of a number using recursive method.
.png)
Types of Recursions:
Recursion is a technique that breaks a problem into one or more sub-problems that are similar to the original problem. Any recursive function can be characterized based on:
•whether the function calls itself directly or indirectly (direct or indirect recursion), whether any operation is pending at each recursive call (tail recursive or not), and the structure of the calling pattern (linear or tree-recursive).
a. Direct Recursion
A function is said to be directly recursive if it explicitly calls itself. Here, the function Func() calls itself for all positive values of n, so it is said to be a directly recursive function.
.png)
b. Indirect Recursion
A function is said to be indirectly recursive if it contains a call to another function which ultimately calls it. These two functions are indirectly recursive as they both call each other.
.png)
c. Tail Recursion
A recursive function is said to be tail recursive if no operations are pending to be performed when the recursive function returns to its caller. Tail recursive functions are highly desirable because they are much more efficient to use as the amount of information that has to be stored on the system stack is independent of the number of recursive calls.
.png)
Not-tail Recursion Tail Recursion
Linear and Tree Recursion
A recursive function is said to be linearly recursive when the pending operation (if any) does not make another recursive call to the function. For example, The factorial function is linearly recursive as the pending operation involves only multiplication to be performed and does not involve another recursive call to Fact.
On the contrary, a recursive function is said to be tree recursive (or non-linearly recursive) if the pending operation makes another recursive call to the function. For example, the Fibonacci function in which the pending operations recursively call the Fibonacci function.
Tree Recursion
.png)
Tower of Hanoi:
The Tower of Hanoi is defined as a mathematical puzzle that consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The problem is to move all these rings from pole A to pole C while maintaining the same order. The main issue is that the smaller disk must always come above the larger disk.
.png)
Example of Tower of Hanoi
#include <stdio.h>
void mode(int,ahar,ohar,ohar);
int main() {
int n;
printf("\n Enter the number of rings: ");
scanf("%d", #n);
move(n,'A', 'C', 'B');
return 0;
}
"void move (int n, char source, char dest, char spare)"{
if (n==1)
printf("\n Move from %c to %o",source,dest);
else{
move(n-1,source,spare,dest);
move(1,source,dest,spare);
move(n-1,spare,dest,source);
}
}
FAQ:
1. Define Data Structure. Discuss different types of data structure.
2. What do you mean by Abstract Data Type? Write importance of ADT with suitable examples
3. Differentiate between recursion and iteration.
4. Discuss different types of recursion with suitable examples.
5. Write algorithm and programs using recursion for the following problems:
i. To find factorial of given number N.
ii. To generate Fibonacci series up to given number N.
iii. To solve problem of Tower of Hanoi for given rings N.
iv. To find sum of even series up to 20 terms.