1.1 Data types, Data structure and Abstract date type

1. Data Types:

• Definition: A data type defines the kind of value a variable can hold and the operations that can be performed on that value.
• Examples:
  • Primitive Data Types: Basic types provided by a programming language.
    • Integer: Whole numbers (e.g., int in Python, int in C).
    • Float: Numbers with decimal points (e.g., float in Python, double in C).
    • Boolean: True or False values (e.g., bool in Python).
    • Character: Single characters (e.g., char in C).
  • Composite Data Types: Made by combining basic types.
    • Arrays, Strings, etc.

2. Data Structures:

• Definition: A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently.
• Types:
  • Linear Data Structures: Data elements are arranged sequentially.
    • Arrays: Fixed-size collection of elements of the same type.
    • Linked Lists: Collection of elements where each element points to the next.
    • Stacks: Follows Last-In-First-Out (LIFO) principle.
    • Queues: Follows First-In-First-Out (FIFO) principle.
  • Non-Linear Data Structures: Data elements are not arranged sequentially.
    • Trees: Hierarchical structure (e.g., Binary Trees, Binary Search Trees).
    • Graphs: Consists of nodes (vertices) and edges (lines connecting nodes).
    • Hash Tables: Uses a hash function to map keys to values for efficient lookup.

3. Abstract Data Types (ADT):

• Definition: An abstract data type (ADT) defines a data structure purely by its behavior (operations) from the point of view of a user, ignoring implementation details.
• Characteristics:
  • Focuses on what operations are performed, rather than how they are implemented.
  • Can be implemented using various data structures.
• Examples:
  • Stack ADT:
    • Operations: push, pop, peek, isEmpty.
    • Can be implemented using arrays or linked lists.
  • Queue ADT:
    • Operations: enqueue, dequeue, peek, isEmpty.
    • Can be implemented using arrays or linked lists.
  • List ADT:
    • Operations: insert, delete, find, traverse.
    • Can be implemented using arrays, linked lists, etc.

1.2 Dynamic memory allocation in C

Dynamic memory allocation in C refers to allocating memory during the execution of a program (runtime), as opposed to static memory allocation, which occurs at compile time. This is particularly useful when the size of the data structure is not known in advance or may change during the execution of the program.

C provides a set of standard library functions to perform dynamic memory allocation from the heap, which include malloc(), calloc(), realloc(), and free().

Key Functions for Dynamic Memory Allocation:

1. malloc() (Memory Allocation)
   • Allocates a specified number of bytes and returns a pointer to the first byte of the allocated memory.
   • The memory block contains garbage (uninitialized) values.
   • Syntax:
     void* malloc(size_t size);
   • Example:
     int* ptr = (int*) malloc(5 * sizeof(int)); // Allocates memory for 5 integers
2. calloc() (Contiguous Allocation)
   • Allocates memory for an array of elements, initializes all bytes to zero, and returns a pointer to the memory.
   • Syntax:
     void* calloc(size_t num, size_t size);
   • Example:
     int* ptr = (int*) calloc(5, sizeof(int)); // Allocates memory for 5 integers and initializes them to 0
3. realloc() (Reallocation)
   • Resizes a previously allocated block of memory to a new size.
   • If the new size is larger, it may move the block to a new location and the additional memory is uninitialized.
   • If the new size is smaller, it may shrink the block in place or move it.
   • Syntax:
     void* realloc(void* ptr, size_t new_size);
   • Example:
     ptr = realloc(ptr, 10 * sizeof(int)); // Resizes the memory block to hold 10 integers
4. free() (Deallocation)
   • Frees the dynamically allocated memory and makes it available for future use.
   • It is important to free memory when it is no longer needed to avoid memory leaks.
   • Syntax:
     void free(void* ptr);
   • Example:
     free(ptr); // Frees the memory allocated to `ptr`

How Dynamic Memory Allocation Works in C:

• Memory is allocated from the heap at runtime.
• The heap grows dynamically and the allocated memory remains allocated until explicitly freed.
• If the program uses more memory than available in the heap, memory leaks or heap overflow can occur.

Example of Dynamic Memory Allocation:

Here’s a full example using malloc() and free():

Key Concepts:

1. Memory Leaks:
   • A memory leak occurs when dynamically allocated memory is not freed, leading to memory being used unnecessarily, potentially causing the program to run out of memory.
2. Dangling Pointers:
   • A dangling pointer refers to a pointer that still holds the address of memory that has been freed. Accessing this memory after it has been freed can result in undefined behavior.

Advantages of Dynamic Memory Allocation:

• Efficient use of memory, especially when the size of data structures cannot be predetermined.
• Flexibility in managing memory during runtime.

Disadvantages:

• It requires careful management to prevent memory leaks and dangling pointers.
• Can be slower compared to static allocation due to the overhead of managing heap memory.

1.3 Introduction to Algorithms

An algorithm is a well-defined, step-by-step process or set of rules for solving a problem or performing a task. Algorithms form the core of computer programming and software development, as they dictate the logical sequence in which operations must be carried out.

Characteristics of Algorithms

A good algorithm should have the following key properties:

1. Input: It should take zero or more inputs.
2. Output: It should produce at least one output.
3. Definiteness: Each step must be clearly and unambiguously defined.
4. Finiteness: It must have a finite number of steps, and it must terminate.
5. Effectiveness: Every step must be basic enough to be carried out with finite resources (e.g., time, memory).

Importance of Algorithms

• Algorithms provide a clear path to solving problems.
• They optimize performance and resource utilization (e.g., time, space).
• They form the foundation of software development and computational tasks.
• Algorithms are necessary to ensure that tasks are performed in the most efficient way possible, especially when dealing with large amounts of data.

Basic Structure of an Algorithm

An algorithm typically follows this general structure:

1. Start: Initialize the process.
2. Input: Accept inputs (if any).
3. Process: Perform a series of computations.
4. Output: Produce the desired result or output.
5. End: Terminate the process.

Types of Algorithms

Algorithms can be classified into different categories based on the type of problem they solve or the approach they use. Some of the common types include:

1. Search Algorithms:
   • Used to find an element in a data structure.
   • Examples:
     • Linear Search: Searches each element sequentially.
     • Binary Search: Efficient search in a sorted array, divides the search space in half each time.
2. Sorting Algorithms:
   • Used to arrange elements in a specific order (ascending or descending).
   • Examples:
     • Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order.
     • Merge Sort: Divides the array into smaller sub-arrays, sorts them, and merges them.
     • Quick Sort: Uses divide-and-conquer by selecting a pivot and partitioning the array.
3. Divide and Conquer Algorithms:
   • Breaks the problem into smaller subproblems, solves them independently, and combines their results.
   • Examples:
     • Merge Sort, Quick Sort.
4. Greedy Algorithms:
   • Makes locally optimal choices at each step, aiming to find a global optimum.
   • Examples:
     • Dijkstra’s Shortest Path Algorithm.
     • Kruskal’s Algorithm for finding the Minimum Spanning Tree.
5. Dynamic Programming:
   • Breaks down problems into overlapping subproblems, solves each only once, and stores their results to avoid redundant work.
   • Examples:
     • Fibonacci Series computation.
     • Knapsack Problem.
     • Longest Common Subsequence.
6. Backtracking Algorithms:
   • Attempts to build a solution incrementally, and if a solution path doesn’t work, it backtracks to previous steps.
   • Example:
     • N-Queens Problem.
     • Sudoku Solver.
7. Recursive Algorithms:
   • Solves the problem by calling itself with a smaller input, until a base case is reached.
   • Example:
     • Factorial Calculation.
     • Tower of Hanoi.
8. Graph Algorithms:
   • Deals with problems related to graph theory, such as finding the shortest path, connectivity, or spanning trees.
   • Examples:
     • Dijkstra’s Algorithm for shortest paths.
     • Depth First Search (DFS) and Breadth First Search (BFS) for traversing graphs.

Algorithm Complexity

Understanding the complexity of an algorithm is essential for evaluating its efficiency. Complexity measures the resources (time and space) that an algorithm consumes, especially in terms of input size.

1. Time Complexity: Refers to the time required for an algorithm to complete as a function of the size of the input.
   • Common Notations:
     • O(1): Constant time.
     • O(n): Linear time.
     • O(log n): Logarithmic time.
     • O(n²): Quadratic time.
2. Space Complexity: Refers to the amount of memory an algorithm uses relative to the input size.

Big-O Notation

Big-O notation is used to describe the worst-case performance of an algorithm in terms of time or space. It helps in understanding how the algorithm scales as the input size increases.

• O(1): Constant time, regardless of input size.
• O(n): Linear time; performance grows directly with the size of the input.
• O(log n): Logarithmic time; decreases the input size exponentially.
• O(n²): Quadratic time; performance grows with the square of the input size (e.g., nested loops).

Example Algorithm: Bubble Sort

Problem: Sort an array of integers in ascending order using Bubble Sort.

Algorithm:

1. Start.
2. Take an array of n elements.
3. Repeat the following steps for n-1 times:
   • Compare adjacent elements.
   • If the current element is greater than the next, swap them.
4. If no elements were swapped in a pass, the array is sorted.
5. Stop.

Pseudocode:

1.4 Asymptotic notations and common functions

Write a program to implement dynamic memory management functions(malloc(),calloc(),realloc() and free())

Here’s a C program that demonstrates the use of dynamic memory management functions: malloc(), calloc(), realloc(), and free(). Each of these functions is used to allocate and manage memory dynamically during the program execution.

Program: Implementing Dynamic Memory Management

Explanation:

1. Using malloc():
   • Memory is dynamically allocated for n integers using malloc(), and user input is stored in that memory.
   • Since malloc() does not initialize the allocated memory, it contains garbage values until we explicitly assign values.
2. Using calloc():
   • Memory is allocated for n integers using calloc(), which initializes the allocated memory to zero.
   • This step demonstrates how calloc() initializes the memory to 0, unlike malloc().
3. Using realloc():
   • The previously allocated memory (from malloc()) is resized using realloc() to hold a new number of integers.
   • This allows us to expand or shrink dynamically allocated memory.
4. Using free():
   • The memory allocated by both malloc(), calloc(), and realloc() is released using free() to prevent memory leaks.

Output Example: