### 1.
Data Structure:
A **data structure** is a way of organizing and storing data in a computer so
that it can be accessed and modified efficiently. Different data structures are
suited to different kinds of applications, and some are highly specialized for
specific tasks.
**Applications of common data structures**:
- **Array**: Used for storing a collection of elements in a linear order; useful
in applications where the size of the data is fixed, such as a static lookup
table.
- **Linked List**: Useful for applications where dynamic memory allocation is
needed, such as implementing stacks and queues.
- **Stack**: Used in expression evaluation, syntax parsing, and backtracking
algorithms.
- **Queue**: Used in scheduling processes in an operating system, or when
handling asynchronous data (like in a printer’s task queue).
- **Tree**: Used for hierarchical data representation, such as file systems, or
for efficient searching and sorting algorithms (binary search trees).
- **Graph**: Used in network routing algorithms, social networks, and
modeling relationships between entities.
### 2. Role of Various Tools in Program Execution:
- **Editor**: Used for writing and editing the source code of a program. It
provides a text interface to write code in a programming language.
- **Loader**: Loads executable programs into memory for execution. It
allocates space and links necessary libraries and modules.
- **Linker**: Combines object files generated by the compiler into a single
executable file, resolving any references to external libraries or functions.
- **Assembler**: Converts assembly language code into machine language
(binary code) that the computer can execute.
- **Compiler**: Transforms source code written in a high-level programming
language into machine code or bytecode.
- **Interpreter**: Directly executes the instructions written in a programming
or scripting language without compiling them into machine code first.
- **Operating System**: Manages hardware resources and provides an
environment where applications and programs can run.
- **Integrated Development Environment (IDE)**: Combines multiple tools
like a code editor, debugger, compiler, and more into a single interface for
programming.
### 3. Heuristics:
**Heuristics** are problem-solving strategies that aim to produce a good
enough solution in a reasonable time frame when finding an exact solution is
impractical. They are often employed when an optimal solution is hard to
compute, but an approximate or “good enough” solution is acceptable.
For the **Travelling Salesman Problem (TSP)**, a heuristic example is the
**Nearest Neighbor Heuristic**:
- Start at a random city.
- Visit the nearest unvisited city.
- Repeat until all cities are visited.
- Return to the starting city.
This method doesn’t guarantee the optimal solution but provides a fast and
reasonable approximation.
### 4. Algorithms and Efficiency:
An **algorithm** is a step-by-step procedure or set of rules to solve a
specific problem or perform a task.
**Efficiency of an algorithm** is typically measured using **time
complexity**, denoted using **Big-O notation**, which describes the upper
bound of the running time of the algorithm as a function of the input size.
- **O(log n)**: Binary Search – The algorithm divides the input space in half
with each iteration.
- **O(n)**: Linear Search – The algorithm examines each element of an input
list once.
- **O(n log n)**: Merge Sort – The algorithm recursively splits the list and
then merges the sorted halves.
- **O(n²)**: Bubble Sort – The algorithm repeatedly compares adjacent
elements and swaps them if they are in the wrong order.
- **O(n³)**: Matrix Multiplication – Multiplying two matrices involves multiple
iterations over the elements.
- **O(2ⁿ)**: Recursive algorithms solving problems like the Fibonacci
sequence or subset problems with exponential growth.
- **O(n!)**: Travelling Salesman Problem (Brute Force) – All possible paths
between cities are calculated.
These complexities give an idea of how the algorithm’s runtime scales with
the size of the input.
Here are the C implementations for each problem you mentioned.
### 1. Sieve of Eratosthenes to find all prime numbers less than 100,000:
```c
#include <stdio.h>
#include <stdbool.h>
Int main() {
Int n = 100000;
Bool isPrime[n+1];
// Initialize all numbers as prime
For (int I = 2; I <= n; i++)
isPrime[i] = true;
// Sieve of Eratosthenes
For (int I = 2; I * I <= n; i++) {
If (isPrime[i]) {
For (int j = I * I; j <= n; j += i)
isPrime[j] = false;
// Print all prime numbers less than 100000
For (int I = 2; I <= n; i++) {
If (isPrime[i])
Printf(“%d “, i);
Return 0;
```
### 2. Advantages of Developing a Program as a Collection of Independent
Functions:
- **Modularity**: Each function is independent and can be tested individually,
making debugging easier.
- **Reusability**: Functions can be reused in different parts of the program or
in different programs.
- **Maintainability**: Changes in one function are less likely to affect other
parts of the code.
- **Simplicity**: Breaking down the problem into smaller functions makes it
easier to understand and manage the program.
### 3. Prime Number Test Function:
```c
#include <stdio.h>
#include <stdbool.h>
Bool isPrime(int n) {
If (n <= 1)
Return false;
For (int I = 2; I * I <= n; i++) {
If (n % I == 0)
Return false;
Return true;
}
Int main() {
Int num;
Printf(“Enter an integer: “);
Scanf(“%d”, &num);
If (isPrime(num))
Printf(“%d is a prime number.\n”, num);
Else
Printf(“%d is not a prime number.\n”, num);
Return 0;
```
**Computational complexity** of this function is **O(√n)** because the loop
runs up to the square root of the given number.
### 4. C Structure for Complex Numbers and Functions for Operations:
```c
#include <stdio.h>
// Structure for representing a complex number
Struct Complex {
Double real;
Double imag;
};
// Function to add two complex numbers
Struct Complex add(struct Complex a, struct Complex b) {
Struct Complex result;
[Link] = [Link] + [Link];
[Link] = [Link] + [Link];
Return result;
// Function to subtract two complex numbers
Struct Complex subtract(struct Complex a, struct Complex b) {
Struct Complex result;
[Link] = [Link] – [Link];
[Link] = [Link] – [Link];
Return result;
// Function to multiply two complex numbers
Struct Complex multiply(struct Complex a, struct Complex b) {
Struct Complex result;
[Link] = [Link] * [Link] – [Link] * [Link];
[Link] = [Link] * [Link] + [Link] * [Link];
Return result;
}
Int main() {
Struct Complex num1, num2, result;
// Input two complex numbers
Printf(“Enter real and imaginary part of first complex number: “);
Scanf(“%lf %lf”, &[Link], &[Link]);
Printf(“Enter real and imaginary part of second complex number: “);
Scanf(“%lf %lf”, &[Link], &[Link]);
// Perform addition
Result = add(num1, num2);
Printf(“Addition: %.2lf + %.2lfi\n”, [Link], [Link]);
// Perform subtraction
Result = subtract(num1, num2);
Printf(“Subtraction: %.2lf + %.2lfi\n”, [Link], [Link]);
// Perform multiplication
Result = multiply(num1, num2);
Printf(“Multiplication: %.2lf + %.2lfi\n”, [Link], [Link]);
Return 0;
```
This code defines a structure `Complex` and provides functions for adding,
subtracting, and multiplying complex numbers.
