Unit 1: Introduction to Data Structures & Algorithms
1.1 Data types, Data structure, and Abstract data type
Data:
Computer data is information processed or stored by a computer. The information may be in the form of text documents, images, audio clips, software programs, or other types of data. Computer data may be processed by the computer's CPU and is stored in files and flowers on the computer's hard disk.
Data Types:
Simply said and explained, the term data type refers to the type of data. It is the data storage format that can contain a specific type or range of values.
Each variable should be assigned with the specific data type whenever the computer program stores data in variables. Some common data types are:
- Integer
- Floating Point Numbers
- Characters
- Strings
- Arrays
Going more specifically, they may be classified as dates, timestamps, boolean values, varchar (variable character) formats.
Data Structure:
A data structure is a specialized format for organizing, processing, retrieving, and storing data. While there are several basic and advanced structure types, any data structure is designed to arrange data to suit a specific purpose so that it can be accessed and worked within appropriate ways.
Thinking about the types of data structures, we can categorize them into four types:
- Linear: arrays, list
- Tree: binary, heaps, space partitioning, etc.
- Hash: distributed hash table, hash tree, etc.
- Graphs: decision, directed, acyclic, etc.
Abstract Data Type:
An abstract data type is a type with associated operations , but whose representation is hidden. It is called "abstract" because it gives an implementation-independent view. The process of providing only the essentials and hiding the details is known as abstraction. A common example of abstract data types is the built-in types in Haskell, Integer, and Float.
1.2 Dynamic memory allocation in C
An array is a collection of a fixed number of values. Oncle the size of an array is declared, you cannot change it.
Sometimes the size of the array you declared may be insufficient. To solve this issue, you can allocate memory manually during run-time. This is known as dynamic memory allocation in C programming.
To allocate memory dynamically, library functions like malloc(), calloc(), realloc() and free() are used. These functions are defined in the <stdlib.h> header file.
C malloc() :
The name "malloc" stands for memory allocation.
The malloc() function reserves a block of memory of the specified number of bytes. And, it returns a pointer of void which can be cast into pointers of any form.
Syntax of malloc()
ptr = (castType*) malloc(size);Example
ptr = (float*) malloc(100 * sizeof(float));The above statement allocated 400 bytes of memory. It's because the size of the float is 4 bytes. And the pointer ptr holds the address of the first byte in the allocated memory.
The expression results in a NULL pointer if he memory cannot be allocated.
C calloc() :
The name "calloc" stands for contiguous allocation.
The malloc() function allocated memory and leaves the memory uninitialized. Whereas, the calloc() function allocated memory and initialized all bits to zero.
Syntax of calloc()
ptr = (castType*) calloc(n, size);Example
ptr = (float*) calloc(25 * sizeof(float));The above statement allocates contiguous space in memory for 25 elements of type float.
C free() :
Dynamically allocated memory created with either calloc() or malloc() doesn't get freed on their own. We must explicitly use free() to release the space.
Syntax of free()
free(ptr);This space frees the space allocated in the memory pointed by ptr.
C realloc() :
If the dynamically allocated memory is insufficient or more than required, we can change the size f previously allocated memory using the realloc() function.
Syntax of realloc()
ptr = realloc(ptr, x);Here, ptr is reallocated with a new size x.
1.3 Introduction to Algorithms
An algorithm is a step by step procedure to solve logical and mathematical problems. A recipe to cook food is a good example of an algorithm because it says what must done, step by step. An algorithm can also be called a "list of steps". An algorithm can be written in ordinary language, and that maybe all a person needs.
Properties of algorithms:
- Input: The inputs used in an algorithm must come from a specified set of elements, where the amount and type of inputs are specified.
- Output: The algorithm must specify the output and how it is related to the input.
- Definiteness: The steps in the algorithm must be clearly defined and detailed.
- Effectiveness: The steps in the algorithm must be doable and effective.
- Finiteness: The algorithm must come to an end after a specific number of steps.
1.4 Asymptotic notations and common functions
Asymptotic notions are the expressions that are used to represent the complexity of an algorithm. It describes the algorithm efficiency and performance in a meaningful way. It describes the behavior of time or space complexity for large instance characteristics.
The order of growth of the running time of an algorithm gives a simple character of the algorithm's efficiency and also allows us to compare the relative performance of the alternative algorithm.
We call it growth functions as we ignore the very small constant.
The asymptotic running time of an algorithm is defined in terms of functions.
The asymptotic notation of an algorithm is classified into 3 types.
- Big Oh notation (O)/ Asymptotic upper bound
- Big Omega notation (Ω) / Asymptotic upper bound
- Big Theta notation (θ) / Asymptotic tight bound
(i) Big Oh notation(O): (Asymptotic Upper bound)
The function f(n)=O(g(n)), if and only if there exists a positive constant C and K such that f(n) ≤ C * g(n) for all n, n≥K.
 |
| [Big Oh Notation (f(n) ≤ C * g(n))] |
(ii) Big Omega notation(Ω): (Asymptotic Lower bound) The function f(n)=Ω(g(n)), if and only if there exists a positive constant C and K such that f(n)≥C * g(n) for all n, n≥K.
 |
| [Big Omega (f(n)=Ω(g(n))) notation] |
(iii) Big Theta notation(θ): (Asymptotic Tight bound) The function f(n)=θ(g(n)), if and only if there exist a positive constant C1, C2 and K such that C1*g(n) ≤ f(n) ≤ C2 * g(n) for all n, n≥K.
 |
| [Big Theta notation (C1*g(n) ≤ f(n) ≤ C2 * g(n))] |
Lab: Write a program to implement dynamic memory management functions [malloc(), calloc(), realloc() and free()]
Example of malloc() and free() implemented for dynamic memory management.
// Program to calculate the sum of n numbers entered by the user
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, i, *ptr, sum = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
ptr = (int*) malloc(n * sizeof(int));
// if memory cannot be allocated
if(ptr == NULL)
{
printf("Error! memory not allocated.");
exit(0);
}
printf("Enter elements: ");
for(i = 0; i < n; ++i)
{
scanf("%d", ptr + i);
sum += *(ptr + i);
}
printf("Sum = %d", sum);
// deallocating the memory
free(ptr);
return 0;
}
Here, we have dynamically allocated the memory for n number of int.
Example of calloc() and free() implemented for dynamic memory management.
// Program to calculate the sum of n numbers entered by the user
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, i, *ptr, sum = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
ptr = (int*) calloc(n, sizeof(int));
if(ptr == NULL)
{
printf("Error! memory not allocated.");
exit(0);
}
printf("Enter elements: ");
for(i = 0; i < n; ++i)
{
scanf("%d", ptr + i);
sum += *(ptr + i);
}
printf("Sum = %d", sum);
free(ptr);
return 0;
}
Example of realloc() and free() implemented for dynamic memory management.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int *ptr, i , n1, n2;
printf("Enter size: ");
scanf("%d", &n1);
ptr = (int*) malloc(n1 * sizeof(int));
printf("Addresses of previously allocated memory: ");
for(i = 0; i < n1; ++i)
printf("%u\n",ptr + i);
printf("\nEnter the new size: ");
scanf("%d", &n2);
// rellocating the memory
ptr = realloc(ptr, n2 * sizeof(int));
printf("Addresses of newly allocated memory: ");
for(i = 0; i < n2; ++i)
printf("%u\n", ptr + i);
free(ptr);
return 0;
}When we run the program, the output will be:
Enter size: 2 Addresses of previously allocated memory:26855472 26855476 Enter the new size: 4 Addresses of newly allocated memory:26855472 26855476 26855480 26855484
Download printable note of Unit 1 from here
THE-END
Views
0 Comments