(1)​Define Time complexity and Space complexity.

Ans:
Time Complexity:
●​ Time complexity is a measure of the amount of time an algorithm takes to complete as
a function of the input size (usually denoted as n).
●​ It helps estimate the efficiency of an algorithm and compare it with others without
actually running the program.
Notation Examples:
●​
O(1) – Constant time
●​
O(n) – Linear time
●​
O(n²) – Quadratic time
●​
O(log n) – Logarithmic time
Example: A loop that runs n times has time complexity O(n).

Space Complexity:
●​ Space complexity is a measure of the amount of memory an algorithm uses during its
execution, including input storage, auxiliary space, and temporary variables.
●​ It tells us how efficiently an algorithm uses memory as the input size grows.
Notation Examples:
●​ O(1) – Constant space
●​ O(n) – Linear space
Example: Storing an array of n elements requires O(n) space.

(2)​List out applications of data structure and explain any one.

Ans:
●​ Data structures are essential in computer science and software development.
●​ They provide a way to organize and manage data efficiently for different types of
operations. Here are some key applications:
Common Applications of Data Structures:
1.​ Databases & Operating Systems
2.​ Artificial Intelligence (AI) & Machine Learning (ML)
3.​ Computer Networks
4.​ Compilers and Interpreters
5.​ Web Browsers
6.​ Search Engines
7.​ Blockchain and Cryptography
8.​ Graphics and Gaming
9.​ File Systems
Web Browsers (Using Stack Data Structure)
Example: The "Back" and "Forward" navigation in web browsers.
●​ When you visit a new webpage, the current page is pushed onto a stack.
●​ When you click the "Back" button, the browser pops the current page from the stack
and loads the previous one.
●​ A second stack may be used to store "Forward" history, enabling the Forward button.
●​ Stack is a Last In First Out (LIFO) structure.
●​ Perfect for managing pages in the order they were accessed—last visited page is the
first to come back when you hit “Back”.​

(3)​Explain linear and non-linear data structures.

Ans:
1. Linear Data Structures: A linear data structure is a structure where data elements are
arranged sequentially, and each element is connected to the next and/or previous element.
Characteristics:
●​ Elements are stored in a single level (line).
●​ Easy to implement and manage.
●​ Memory is utilized in a sequential fashion.
Examples:
●​ Array , Linked List , Stack , Queue
Example: Array
Index: 0 1 2 3
Values: 5 8 12 20
Each element has a fixed position and follows a linear order.

2. Non-Linear Data Structures: A non-linear data structure is a structure where data

elements are not arranged sequentially; instead, they are arranged in a hierarchical or
interconnected manner.
Characteristics:
●​ Elements may have multiple relationships.
●​ Better suited for complex tasks (e.g., hierarchical data, graphs).
●​ Memory is used dynamically.
Examples:
●​ Tree (e.g., Binary Tree, BST) , Graph , Heap , Trie
Example: Tree
10
/ \
20 30
/\ \
40 50 60
Each node can have multiple children—data is organized hierarchically, not linearly.
 (4)​Explain best case and worst case for an algorithm.

Ans:
1. Best Case: The best case describes the minimum time or resources an algorithm will take
to complete, given the most favorable input.
●​ The input is in the most optimal condition.
●​ The algorithm finishes its task with minimum effort.
Example: Linear Search
●​ If you're searching for an element and it's the first item in the list:
○​ Time complexity: O(1) (only one comparison).

2. Worst Case: The worst case describes the maximum time or resources an algorithm may
take, given the least favorable or most complex input.
●​ The input causes the algorithm to do the most work possible.
Example: Linear Search
●​ If the element is the last item or not present at all:
○​ Time complexity: O(n) (check all elements).

(5)​Explain data structure with brief introduction about primitive and Non-
primitive.

Ans:
●​ A data structure is a way of organizing and storing data in a computer so that it can be
used efficiently.
●​ It defines the relationship between data, the operations that can be performed on it,
and how data is stored and retrieved.
Types of Data Structures
1. Primitive Data Structures
●​ These are the basic building blocks of data manipulation, provided by most
programming languages.
Characteristics:
●​ Simple and predefined
●​ Directly operated upon by machine instructions
Examples:
●​ Integer (int) , Float (decimal numbers) , Character (char)
●​ Boolean (true/false) , Pointer
Example in C:
int age = 25;
char grade = 'A';
2. Non-Primitive Data Structures
●​ These are more complex and are derived from primitive data types.
●​ They are used to store multiple values and organize large amounts of data efficiently.
Types of Non-Primitive Data Structures:

A. Linear Data Structures

●​ Elements are stored in a sequence.
●​ Easy to traverse and implement.
Examples:
●​ Array , Linked List , Stack , Queue

B. Non-Linear Data Structures

●​ Elements are stored in a hierarchical or interconnected manner.
●​ Suitable for complex data relationships.
Examples:
●​ Tree , Graph , Heap , Trie

Use of Data Structures:

●​ Efficient data access and manipulation
●​ Better use of memory and processing power
●​ Essential for designing optimized algorithms
●​ Foundation for databases, compilers, operating systems, etc.

(6)​Define Algorithms. Explain Key features of an algorithm.

Ans:
●​ An algorithm is a step-by-step, finite sequence of instructions designed to solve a
specific problem or perform a particular task.
●​ An algorithm is like a recipe — it tells you exactly what to do, in what order, to get
the desired result.

Example of a Simple Algorithm (to add two numbers):

1.​ Start
2.​ Input two numbers: a and b
3.​ Calculate sum: sum = a + b
4.​ Output the result
5.​ End

Key Features of an Algorithm: To be effective, an algorithm must have the following

essential characteristics:
1. Finiteness
●​ The algorithm must end after a finite number of steps.
●​ It should not go into an infinite loop.
Example: After 5 steps, the program stops execution.

2. Definiteness (Clarity)
●​ Every step must be clear and unambiguous.
●​ Instructions should be precisely defined.
Not definite: “Sort the data”​
Definite: “Use bubble sort to compare each pair and swap if needed”

3. Input
●​ An algorithm should have zero or more inputs.
●​ Inputs are the values supplied to the algorithm initially.
Example: Two numbers to add — a and b.

4. Output
●​ It must produce at least one output.
●​ Output is the result or solution produced by the algorithm.
Example: The sum of two numbers.

5. Effectiveness
●​ Each step should be simple enough to be carried out using basic operations.
●​ No step should require superhuman effort or infinite computation.
Example: Use basic arithmetic, not complex unknown logic.

6. Generality
●​ The algorithm should be applicable to a class of problems, not just one specific
instance.
Example: An algorithm to sort a list should work for any list of numbers, not just [3, 1, 4].
 (7)​Explain best case, worst case and average case.

Ans:
1. Best Case: The best case is the scenario where the algorithm takes the minimum possible
time or resources to complete.

Characteristics:
●​ Input is in the most favorable condition.
●​ Represents optimistic performance.
●​ Not reliable alone for real-world performance evaluation.

Example (Linear Search):If the element to be found is the first item in the array:
●​ Time Complexity: O(1)

2. Worst Case: The worst case is the scenario where the algorithm takes the maximum
possible time or resources to complete.

Characteristics:
●​ Input is in the least favorable condition.
●​ Represents the maximum workload for the algorithm.
●​ Useful for performance guarantees.

Example (Linear Search): If the element is the last item or not present at all:
●​ Time Complexity: O(n)

3. Average Case: The average case represents the algorithm's performance on typical or
random inputs.

Characteristics:
●​ Calculates the expected time taken over all possible inputs.
●​ More realistic measure than best or worst case.
●​ Often requires probability analysis.

Example (Linear Search): If the element is equally likely to be anywhere in the array:
●​ Average Time Complexity: O(n/2) → simplified to O(n)
 (8)​Differentiate primitive and non-primitive data structures

Ans:

Primitive Data Structures Non-Primitive Data Structures

Basic data types provided by programming More complex data types built using
languages primitive types

Simple and easy to use Complex and used to store large or related
data

Can store only single value Can store multiple values

Examples: int, char, float, boolean Examples: Array, List, Stack, Queue, Tree,
Graph

Basic operations (arithmetic, logical, etc.) Various operations (insert, delete, search,
sort, etc.)

Uses less memory May use more memory depending on the

structure

Simple, individual data values Organizing and managing complex

collections of data

(9)​Write a C program in a programming language of your choice to

implement a binary search algorithm for a given array.

Ans:
#include <stdio.h> //Includes the Standard Input/Output library. Needed for
functions like printf() and scanf()

int binarySearch(int arr[], int size, int target) { //Declares a function named
binarySearch.
●​ It takes:
○​ arr[]: the sorted array,
○​ size: number of elements in the array,
○​ target: the number to search for.

int low = 0; //Sets the starting index of the search to the first element of the array.

int high = size - 1; //Sets the end index of the search to the last element of the array.
 while (low <= high) { //Loop runs as long as there are elements to check (i.e.,
valid search range). If low > high, the search ends (element not found).

int mid = (low + high) / 2; //Finds the middle index between low and high.

if (arr[mid] == target) { //Checks if the middle element is the one we're

searching for. If yes, it returns the mid index.

return mid;
}
else if (arr[mid] < target) { //If the target is greater than the middle element, It
means the target must be in the right half, so we set: low = mid + 1

low = mid + 1;
} // If target is smaller, ignore the right half
else { //else
●​ If the target is less than the middle element,
●​ It must be in the left half, so we set: high = mid - 1

high = mid - 1;
}
}

return -1; // If the loop finishes without finding the target, return -1 to indicate
not found.
}

int main() { //The main function where the program starts execution.

int arr[] = {2, 4, 10, 15, 20, 25, 30}; // Declares and initializes a sorted array of
integers.​

int size = sizeof(arr) / sizeof(arr[0]); //Calculates the number of elements in the

array.
sizeof(arr) = total size of array in bytes
sizeof(arr[0]) = size of one element
Dividing gives the count.

int target; //Declares a variable to store the number the user wants to search.

printf("Enter the number to search: "); //Asks the user to enter a number.

scanf("%d", &target); //Takes user input and stores it in the target variable.

int result = binarySearch(arr, size, target); //Calls the binarySearch function

with the array, its size, and the target.
●​ Stores the returned index (or -1) in the variable result.

if (result != -1) { //If the result is not -1, that means the element was found.
 printf("Element found at index %d\n", result); //Prints the index where the
element was found.

} else {
printf("Element not found in the array.\n"); //If the result is -1, it means the
element isn't in the array.​

return 0; //Indicates that the program ran successfully.

}

Sample Output:
Enter the number to search: 20
Element found at index 4

(10)​ Identify and explain the essential features of an algorithm

Ans:
●​ An algorithm is a step-by-step procedure used to solve a problem or perform a task.
●​ For any set of instructions to be considered a valid algorithm, it must have certain key
features.

Essential Features of an Algorithm

1. Input
●​ The algorithm should accept zero or more inputs.
●​ Inputs provide the data the algorithm needs to work on.
Example: To calculate the sum, you need two numbers as input.

2. Output
●​ The algorithm should produce at least one output.
●​ The output is the result or solution of the problem.
Example: After adding two numbers, the result (sum) is the output.

3. Finiteness
●​ The algorithm must end after a finite number of steps.
●​ If an algorithm runs forever, it's not useful.
Example: A loop that runs exactly 10 times is finite; a loop without an exit condition is not.

4. Definiteness (Clarity)
●​ Each step of the algorithm must be clear, exact, and unambiguous.
●​ Ambiguity can lead to confusion or errors during execution.
Bad instruction: “Do the next step properly.”​
Good instruction: “Add 5 to the current number.”

5. Effectiveness
●​ All operations must be basic enough to be done in a reasonable time using available
resources.
●​ Steps should be practical and doable — not just theoretical.
Example: Adding two numbers is effective; solving a puzzle by guessing infinitely is not.

6. Generality
●​ The algorithm should work for a range of inputs, not just one specific case.
●​ A good algorithm can solve many similar problems, not just one.
Example: A sorting algorithm should work for any list of numbers, not just one list.

(11)​ Write a C program to demonstrate function call by value.

Ans:
●​ In call by value, a copy of the actual argument is passed to the function.
●​ Changes made inside the function do not affect the original variables.

C Program: Call by Value Example

#include <stdio.h> //Includes the Standard Input/Output library. Required to use
functions like printf() and scanf().

void swap(int a, int b) { //Declares a function named swap that takes two integers
as input.These are copies of the actual values passed (call by value).

int temp; //Declares a temporary variable to help with swapping values.

temp = a; //Stores the value of a in temp.
a = b; //Replaces the value of a with the value of b.
b = temp; //Assigns the value stored in temp (original a) to b.​

Now, values of a and b are swapped inside the function only.

printf("Inside swap function:\n"); //Prints a label to indicate you're now inside

the swap function.​

printf("a = %d, b = %d\n", a, b); //Displays the values of a and b after

swapping, inside the function.
}

int main() { //Entry point of the program. The main() function starts the
execution.
 int x = 10, y = 20; //Declares and initializes two integers x and y.

printf("Before calling swap:\n"); //Displays a label before the swap function

is called.

printf("x = %d, y = %d\n", x, y); //Prints the original values of x and y.

swap(x, y); //Calls the swap function and passes copies of x and y.​
Inside the function, a = x and b = y, but changes to a and b don’t affect x and y.

printf("After calling swap:\n"); //Displays a label after the function call.​

printf("x = %d, y = %d\n", x, y); //Prints the values of x and y again, showing
that they are unchanged.

return 0; //Ends the main() function.Returns 0 to the operating system,

indicating that the program ran successfully.

Output:
Before calling swap:
x = 10, y = 20
Inside swap function:
a = 20, b = 10
After calling swap:
x = 10, y = 20

Explanation:
●​ swap(x, y) passes copies of x and y to the function.
●​ Inside swap, the values are swapped, but the original variables in main() remain
unchanged.
●​ This shows how call by value works — it does not affect the original variables.
 (12)​ What is string? What are the common operations performed on string?

Ans:
●​ A string is a sequence of characters used to represent text.
●​ In C and many other languages, a string is an array of characters that ends with a null
character ('\0').
Example of a String in C:
char name[] = "Akash";
Behind the scenes, it is stored as:
A k a s h \0
Common Operations Performed on Strings
1. Finding the Length of a String
●​ Use: To count the number of characters (excluding \0)
●​ Function in C: strlen()
Example:
int len = strlen("Hello"); // len = 5

2. Concatenation (Joining Strings)

●​ Use: To join two strings together
●​ Function in C: strcat()
Example:
strcat(str1, str2); // str1 = str1 + str2

3. Copying One String to Another

●​ Use: To duplicate or overwrite a string
●​ Function in C: strcpy()
Example:
strcpy(dest, source);
​
4. Comparing Two Strings
●​ Use: To check if two strings are equal or to sort them
●​ Function in C: strcmp()
Example:
strcmp("apple", "banana"); // returns a negative value
​
5. Searching a Character or Substring
●​ Use: To find if a character or smaller string exists inside a string
●​ Functions in C:
○​ strchr() – finds a character
○​ strstr() – finds a substring
Example:
strchr("Hello", 'e'); // returns pointer to 'e'
strstr("hello world", "world"); // returns pointer to "world"

6.Converting Case
●​ Use: To convert string to uppercase/lowercase
●​ Functions (not standard C, available in <ctype.h> with loops):
○​ toupper(), tolower() (used character by character)

7. Reversing a String
●​ Use: To get the reverse of the original string
●​ No built-in function in C; typically done with a loop.

(13)​ Write an algorithm to compare two strings without using function

strcmp().

Ans: Algorithm to Compare Two Strings Without strcmp()

Objective: To compare two strings character by character and determine if they are:
●​ Equal , Not equal , Or which one is greater (lexicographically)
Algorithm Steps:
1.​ Start
2.​ Input two strings: str1 and str2
3.​ Initialize a variable i = 0
4.​ Repeat the following steps while both strings have not ended:
○​ If str1[i] is not equal to str2[i]
■​ If str1[i] > str2[i], then str1 is greater → print result and stop
■​ If str1[i] < str2[i], then str2 is greater → print result and stop
○​ Else, increment i by 1
5.​ If both strings end at the same time (i.e., same length and all characters matched):
○​ Print "Strings are equal"
6.​ Else, if one string ends before the other:
○​ The longer string is greater
7.​ End
Example (Dry Run):
Compare "apple" and "apples"
●​ a == a → OK
●​ p == p → OK
●​ p == p → OK
●​ l == l → OK
●​ e == e → OK
●​ \0 vs s → str1 ended first → "apples" is greater
 (14)​ Explain string constant and normal constant functions for string.

Ans:
1. String Constant:
●​ A string constant, also called a string literal, is a fixed sequence of characters enclosed
in double quotes (").
●​ A string constant is a read-only text value written directly in the code, automatically
ending with a null character \0.
Examples:
"Hello"
"123"
"Welcome to C!"
""
Stored as:
The string "Hello" is stored in memory like this:
H e l l o \0

Properties:
●​ Immutable (read-only in many cases)
●​ Automatically null-terminated
●​ Stored in a fixed memory location (usually in read-only segment)

2. Normal Constant Functions for String

●​ I believe you're referring to standard string functions that operate on string constants
or variables (normal strings) — especially those in C language that don’t modify the
original string but just use or return information.
●​ These are normal functions that work with string constants or variables, usually from
the <string.h> library.
Common String Functions (Normal Constant Functions):
Function Purpose Example
strlen() Finds the length of a string strlen("Hello") → 5

strcpy() Copies one string into another strcpy(dest, "World");

strcat() Concatenates two strings strcat(str1, "123");

strcmp() Compares two strings strcmp("abc", "abd") → -1

strchr() Finds the first occurrence of a character strchr("abc", 'b') → "bc"

strstr() Finds a substring in a string strstr("hello world", "world")

Example Code:
#include <stdio.h> //Includes the Standard Input/Output library. Required to use
functions like printf().

#include <string.h> //Includes the String Handling Library in C. Provides

functions like strcpy(), strcat(), strlen(), etc.

int main() { //The main function where the program starts running.

char str1[] = "Hello"; //Declares a character array (string) called str1.

Initializes it with the string "Hello". Internally stored as: H, e, l, l, o, \0

char str2[20]; //Declares a second character array named str2. It can hold up to
19 characters + 1 null character. No initial value is assigned here.

strcpy(str2, "World"); //Copies the string "World" into str2. After this line, str2
contains: "World".

strcat(str1, " "); //Appends a space (" ") to the end of str1. So now str1 becomes
"Hello ".

strcat(str1, str2); // Appends the contents of str2 (which is "World") to the end
of str1. Now str1 becomes "Hello World".

printf("Result: %s\n", str1); //Prints the final content of str1. %s is the format
specifier for strings.
Output: Result: Hello World

return 0; //Ends the main() function. Returns 0 to the operating system,

indicating that the program ran successfully.

Output:
Result: Hello World
 (15)​ Explain STR_CAT() in brief with algorithm

Ans:
●​ strcat() is a standard library function in C used to concatenate (join) two strings.
●​ It appends the second string at the end of the first string.
Header File:
#include <string.h>
Syntax:
char *strcat(char *destination, const char *source);
●​ destination – the string where the second string (source) will be added.
●​ source – the string to be appended.
●​ The destination string must have enough space to hold the final combined result.
Example:
char str1[20] = "Hello ";
char str2[] = "World";

strcat(str1, str2); // str1 becomes "Hello World"

Algorithm of strcat() (STR_CAT)
Goal: To append source string to the end of destination string.

Step-by-Step Algorithm: Algorithm STR_CAT(destination, source)

1. Start
2. Find the end of the destination string (look for '\0')
3. Initialize index i = position after last character of destination
4. Initialize index j = 0
5. While source[j] is not '\0':
a. Set destination[i] = source[j]
b. Increment i and j
6. After loop, set destination[i] = '\0' to mark end of new string
7. End
Example (Dry Run):
Let:
●​ destination = "Hello\0" (stored in a larger array)
●​ source = "World\0"
After STR_CAT(destination, source) → "HelloWorld\0"
Important Notes:
●​ The destination string must have enough memory space to hold both original and
added strings. strcat() modifies the original string; it does not create a new one.
Example:
char str1[20] = "Hi ";
char str2[] = "There";
strcat(str1, str2); // Works fine
 (16)​ Explain STR_TOLOWER() in brief with algorithm

Ans:
●​ STR_TOLOWER() refers to converting all uppercase letters in a string to their
lowercase equivalents.
●​ It’s commonly implemented using the tolower() function from C’s <ctype.h> library
applied to each character in a string.
Header File in C:
#include <ctype.h>

Purpose: To convert a string like "HELLO" to "hello".

Algorithm: STR_TOLOWER(string)
Step-by-Step Algorithm: Algorithm STR_TOLOWER(string)
1. Start
2. Initialize index i = 0
3. While string[i] is not '\0': // Loop until end of string
a. If string[i] is an uppercase letter (A-Z):
i. Convert it to lowercase using: string[i] = string[i] + 32
(OR use: string[i] = tolower(string[i]) if using <ctype.h>)
b. Increment i
4. End

Example Code in C:
#include <stdio.h>
#include <ctype.h> // for tolower()

void str_to_lower(char str[]) {

int i = 0;
while (str[i] != '\0') {
str[i] = tolower(str[i]); // convert each character
i++;
}
}

int main() {
char text[] = "HeLLo WoRLD!";

str_to_lower(text);

printf("Lowercase string: %s\n", text);

return 0;
}
Output:
Lowercase string: hello world!
Key Notes:
●​ Only uppercase letters (A-Z) are affected.
●​ Other characters (like spaces, digits, symbols) remain unchanged.
●​ If you're not allowed to use tolower(), you can use str[i] + 32 for manual conversion.

(17)​ Explain STR_REV() in brief with algorithm

Ans:
●​ STR_REV() refers to a string reversal operation — it takes a string and reverses the
order of its characters.
For example:​
Input: "hello"​
Output: "olleh"

Purpose: To reverse the characters in a string in place (without creating a new string), or by
storing the reversed string into another variable.
Step-by-Step: Algorithm STR_REV(string)

1. Start
2. Initialize two variables:
- left = 0 (start of string)
- right = length of string - 1 (end of string)
3. While left < right:
a. Swap string[left] and string[right]
b. Increment left by 1
c. Decrement right by 1
4. End

Key Idea: Swap characters from the two ends, moving toward the middle, until they meet.
Example (Dry Run):
Input: "ABCD"
●​ Swap A and D → DBCA
●​ Swap B and C → DCBA
Output: "DCBA"

C Code Example:
#include <stdio.h>
#include <string.h>

void str_rev(char str[]) {

int left = 0;
 int right = strlen(str) - 1;
char temp;

while (left < right) {

// Swap characters
temp = str[left];
str[left] = str[right];
str[right] = temp;

// Move pointers
left++;
right--;
}
}

int main() {
char text[] = "hello";

str_rev(text);

printf("Reversed string: %s\n", text); // Output: "olleh"

return 0;
}

Output:
Reversed string: olleh

Key Notes:
●​ Works for any string stored in a character array.
●​ Doesn’t use any built-in reverse function — only logic and swapping.
●​ You must make sure the input string is null-terminated (\0).
 (18)​ Explain STR_COPY() in brief with algorithm

Ans:
●​ STR_COPY() refers to the process of copying one string into another.
●​ It is similar to the standard C function: strcpy(destination, source);
Purpose: To copy each character from the source string to the destination string, including
the null character \0 that marks the end of the string.
Step-by-Step Algorithm: Algorithm STR_COPY(destination, source)

1. Start
2. Initialize index i = 0
3. Repeat until source[i] == '\0':
a. Set destination[i] = source[i]
b. Increment i by 1
4. After the loop, set destination[i] = '\0' // to terminate the string
5. End

Key Idea: Copy all characters from the source to destination, one by one, including the null
terminator.
C Code Example:
#include <stdio.h>
void str_copy(char dest[], const char src[]) {
int i = 0;

// Copy each character including '\0'

while (src[i] != '\0') {
dest[i] = src[i];
i++;
}

dest[i] = '\0'; // Null-terminate the destination string

}

int main() {
char source[] = "OpenAI";
char destination[20]; // Make sure it's big enough

str_copy(destination, source);

printf("Copied string: %s\n", destination); // Output: OpenAI

return 0;
}
Output:
Copied string: OpenAI
Key Notes:
●​ The destination array must be large enough to hold all characters from the source
string including the \0.
●​ You must terminate the copied string with '\0' to mark the end.
●​ This logic is similar to how strcpy() works internally in C.

(19)​ Write an algorithm to pattern matching.

Ans:
●​ Pattern matching is a common problem in computer science where we try to find a
smaller string (called a pattern) inside a larger string (called the text).
Goal of Pattern Matching Algorithm
Given:
●​ A text of length n
●​ A pattern of length m​
Find whether the pattern occurs in the text, and if so, at which position(s).​

Assumptions
We’ll use the Naive (brute-force) pattern matching algorithm, which is the simplest.
Step-by-Step: Algorithm PATTERN_MATCH(text, pattern)

1. Start
2. Let n = length of text
3. Let m = length of pattern
4. For i from 0 to (n - m):
a. Initialize match = true
b. For j from 0 to (m - 1):
i. If text[i + j] ≠ pattern[j], then:
- Set match = false
- Break inner loop
c. If match == true:
- Print "Pattern found at position i"
5. End

Example
Text: "abcabcabc"​
Pattern: "cab"
Dry Run:
●​ At index 0: "abc" ≠ "cab"

✅ Match at index 2​
●​ At index 1: "bca" ≠ "cab"
●​ At index 2: "cab" == "cab" →
C-style Pseudocode
for (i = 0; i <= n - m; i++) {
match = 1;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
match = 0;
break;
}
}
if (match) {
printf("Pattern found at position %d", i);
}
}

Time Complexity
●​ Worst-case: O(n × m)​
(when we compare the pattern at every position)
Advanced Alternatives:
●​ KMP Algorithm (Knuth-Morris-Pratt) → O(n + m)
●​ Rabin-Karp Algorithm
●​ Boyer-Moore Algorithm

(20)​ Write an algorithm to measure string length.

Ans:
●​ In C and many programming languages, strings are arrays of characters ending with a
special null character ('\0').
●​ The string length is the number of characters before the '\0'.
For example: "hello" → length = 5
Step-by-Step Algorithm: Algorithm STRING_LENGTH(str)
1. Start
2. Initialize a counter variable: length = 0
3. While str[length] ≠ '\0':
a. Increment length by 1
4. End While
5. Return length
6. End

Explanation:
●​ Start at the first character.
●​ Keep counting until you hit the null character ('\0').
●​ The value of the counter is the string’s length.
Example (Dry Run)
Input: "cat\0"​
Steps:
●​ str[0] = 'c' → count = 1
●​ str[1] = 'a' → count = 2
●​ str[2] = 't' → count = 3
●​ str[3] = '\0' → stop​
→ Output: 3

C-style Pseudocode
int string_length(char str[]) {
int length = 0;

while (str[length] != '\0') {

length++;
}

return length;
}

(21)​ Write an algorithm to find sub strings.

Ans: A substring is a part or section of a string, made up of consecutive characters.

Example:​
If the string is "abc", possible substrings are:​
"a", "b", "c", "ab", "bc", "abc"

Goal: To find and print all possible substrings of a given string.

Step-by-Step Algorithm: Algorithm FIND_SUBSTRINGS(str)
1. Start
2. Let n = length of str
3. For i from 0 to n - 1: // starting index
a. For j from i to n - 1: // ending index
i. Print characters from str[i] to str[j]
4. End

Explanation:
●​ Use two loops:
○​ The outer loop sets the starting point of the substring.
○​ The inner loop sets the ending point.
●​ Print all characters from the starting to the ending index.
Example:
Input: "abc"​
Substrings:
"a" (i=0, j=0)
"ab" (i=0, j=1)
"abc" (i=0, j=2)
"b" (i=1, j=1)
"bc" (i=1, j=2)
"c" (i=2, j=2)

C-style Pseudocode:
void find_substrings(char str[]) {
int i, j, k;
int len = strlen(str);
char sub[100];

for (i = 0; i < len; i++) {

for (j = i; j < len; j++) {
// Extract and print substring from i to j
for (k = i; k <= j; k++) {
printf("%c", str[k]);
}
printf("\n");
}
}
}

Time Complexity:
●​ O(n²) substrings
●​ O(n³) total time if you print each character individually
 (22)​ Convert infix expression into Prefix/Postfix format showing stack
status after every step in tabular form.
a. (A + B) * C – D * E * (F * G)
b. (A+B)*D+E/(F+G*D)+C
c. A/B$C+D*E/F-G+H
d. A – B / C * D + E * F / G
e. (( A –( B +C))* D) $ ( E + F )

Ans:
1. Infix → Postfix
Key Rules:
1.​ Read tokens left to right.
2.​ Operands → output.
3.​ Operators → push onto stack based on precedence and associativity.
4.​ '(' → push onto stack.
5.​ ')' → pop operators to output until '(' is found and discarded.
6.​ After input ends, pop remaining operators to output.​

2. Infix → Prefix
Key Steps:
1.​ One stack for operators, another for operands.
2.​ For each token:
○​ If '(': push to operators.
○​ If operand: push to operands stack.
○​ If operator: pop higher-or-equal precedence operators, combine top two
operands (op + op1 + op2), push result back; then push current operator.
○​ If ')': pop until '(', combining operands similarly.
3.​ After reading input, apply remaining operators to operands to get final prefix.

a. (A + B) * C – D * E * (F * G)
Part 1: Convert to Postfix
Expression: (A + B) * C – D * E * (F * G)
●​ (A + B) → inside parentheses, convert A + B to postfix → A B +
●​ * C → multiply with C → postfix becomes A B + C *
●​ Then – D * E * (F * G)​
Break down:
○​ D * E → D E *
○​ (F * G) → F G *
○​ D * E * (F * G) → D E * F G * *
●​ Now, subtract A B + C * and D E * F G * *​
So postfix becomes: A B + C * D E * F G * * -
Final postfix: A B + C * D E * F G * * -
Part 2: Convert to Prefix
Using the reverse method:
Step 1: Reverse the infix expression and swap parentheses

Original: (A + B) * C – D * E * (F * G)
Reverse: ) G * F ( * E * D – C * ) B + A (

Swap ( and ): ( G * F ) * E * D – C * ( B + A )

Step 2: Convert this reversed infix to postfix

(G * F) * E * D – C * (B + A)
Convert:
●​ (G * F) → G F *
●​ * E → G F * E *
●​ * D → G F * E * D *
●​ – C * (B + A)
○​ C * (B + A) → C B A + *
○​ So G F * E * D * C B A + * -​

Step 3: Reverse the postfix result

Postfix from step 2:G F * E * D * C B A + * -

Reverse: - * + A B C * D * E * F G

Final prefix: - * + A B C * D * E * F G

b. (A+B)*D+E/(F+G*D)+C
Part 1: Convert to Postfix
Expression: (A + B) * D + E / (F + G * D) + C
Breakdown:
1.​ (A + B) → postfix: A B +
2.​ (A + B) * D → postfix: A B + D *
3.​ (F + G * D) →
○​ G * D → G D *
○​ F + (G D *) → F G D * +
4.​ E / (F + G * D) → postfix: E F G D * + /
5.​ (A + B) * D + E / (F + G * D) → postfix: A B + D * E F G D * + / +
6.​ Add + C → postfix: A B + D * E F G D * + / + C +​

Final Postfix: A B + D * E F G D * + / + C +
Part 2: Convert to Prefix
Using the reverse method:
Step 1: Reverse the infix and swap parentheses
Original: (A + B) * D + E / (F + G * D) + C
Reverse: C + ) D * G + F ( / E + D * ) B + A (
Swap ( and ): C + ( D * G + F ) / E + D * ( B + A )

Step 2: Simplify the reversed expression for clarity:

C + (D * G + F) / E + D * (B + A)

Step 3: Convert this reversed infix to postfix

Let's process:
●​ (D * G + F)
○​ D * G → D G *
○​ D G * + F → D G * F +
●​ (B + A) → B A +
●​ So expression: C + (D G * F +) / E + D * (B A +)

Convert stepwise:
●​ (D G * F +) / E → D G * F + E /
●​ D * (B A +) → D B A + *
●​ Now the full expression: C + (D G * F + E /) + (D B A + *)
●​ Convert (C + ...) + ... → C (D G * F + E /) + (D B A + *) +​

Final postfix for reversed expression: C D G * F + E / + D B A + * +

Step 4: Reverse the postfix to get Prefix

Reverse: + + C / E + F * G D * D + A B

Wait, to get correct prefix, reverse token-wise:

Postfix tokens: C D G * F + E / + D B A + * +

Reverse tokens: + * A B D + / E + F * G D C

So prefix: + * + A B D + / E + F * G D C
Final Prefix: + + * + A B D / E + F * G D C
c. A / B $ C + D * E / F - G + H

Part 1: Convert to Postfix

Expression: A / B $ C + D * E / F - G + H
Scan left to right, maintain operator stack:
1.​ A → operand → output: A
2.​ / → operator → push /
3.​ B → operand → output: B
4.​ $ → operator →
○​ $ has higher precedence than /, so push $
5.​ C → operand → output: C
6.​ Now the next operator? The next token is +. Before pushing +, pop operators with
higher or equal precedence than + from stack.​

Stack currently: / (bottom), $ (top)

●​ $ has higher precedence than +, pop $ → output $
●​ / has higher precedence than +, pop / → output /
●​ Now push +​

Current output: A B C $ /
Stack: +
7.​ D → operand → output: D
8.​ * → operator →
○​ * has higher precedence than +, push *
9.​ E → operand → output: E
10.​/ → operator →
○​ / has equal precedence to * and left-associative → pop * → output *
○​ Push /
11.​F → operand → output: F
12.​- → operator →
○​ Stack: + (bottom), / (top)
○​ / has higher precedence than -, pop / → output /
○​ + has equal precedence to -, pop + → output +
○​ Push -
13.​G → operand → output: G
14.​+ → operator →
○​ - has equal precedence to +, pop - → output -
○​ Push +
15.​H → operand → output: H​

End of expression: Pop remaining operator + → output +

Final Postfix: A B C $ / D E * F / + G - H +
Part 2: Convert to Prefix
Method: Reverse infix, swap parentheses (none here), convert to postfix, reverse result.

Step 1: Reverse infix

Original: A / B $ C + D * E / F - G + H
Reversed (tokens): H + G - F / E * D + C $ B / A

No parentheses to swap.

Step 2: Convert reversed infix to postfix

Expression: H + G - F / E * D + C $ B / A

Operators:
●​ $ highest precedence, right-associative
●​ *, / medium, left-associative
●​ +, - lowest, left-associative

Process left to right:

1.​ H → output
2.​ + → push +
3.​ G → output
4.​ - →
○​ + has equal precedence to -, pop + output
○​ Push -
5.​ F → output
6.​ / → push / (higher precedence than -)
7.​ E → output
8.​ * →
○​ / has equal precedence to *, pop / output
○​ Push *
9.​ D → output
10.​+ →
○​ * has higher precedence than +, pop * output
○​ - has equal precedence to +, pop - output
○​ Push +
11.​C → output
12.​$ → push $ (highest precedence)
13.​B → output
14.​/ →
○​ $ has higher precedence than /, pop $ output
○​ / is pushed
15.​A → output
End of expression:
Pop remaining / → output​
Pop remaining + → output

Postfix of reversed infix: H G + F E / D * - C B $ A / +

Step 3: Reverse this postfix to get prefix

Tokens of postfix: H G + F E / D * - C B $ A / +

Reversed tokens: + / A $ B C - * D / E F + G H

Final Prefix: + / A $ B C - * D / E F + G H

d. A – B / C * D + E * F / G

Part 1: Convert to Postfix

Expression: A – B / C * D + E * F / G
Scan left to right:
1.​ A → operand → output: A
2.​ - → operator → push -
3.​ B → operand → output: B
4.​ / → operator → / has higher precedence than -, push /
5.​ C → operand → output: C
6.​ * → operator → * has same precedence as / (left-associative), so pop / → output /,
push *
7.​ D → operand → output: D
8.​ + → operator →
○​ * has higher precedence than +, pop * → output *
○​ - has same precedence as +, pop - → output -
○​ push +
9.​ E → operand → output: E
10.​* → operator → * has higher precedence than +, push *
11.​F → operand → output: F
12.​/ → operator → / has same precedence as * (left-associative), pop * → output *,
push
13.​G → operand → output: G

End of expression: Pop remaining operators on stack: / then +

Output steps:
 ●​ Operands: A B C / D * - E F * G / +​

Final Postfix: A B C / D * - E F * G / +

Part 2: Convert to Prefix

Method: Reverse infix, swap parentheses (none here), convert reversed infix to postfix,
then reverse result.
Step 1: Reverse infix
Original: A – B / C * D + E * F / G
Reversed tokens: G / F * E + D * C / B – A

Step 2: Convert reversed infix to postfix

Expression: G / F * E + D * C / B – A
Scan left to right:
1.​ G → output
2.​ / → push /
3.​ F → output
4.​ * →
○​ / has equal precedence to *, pop / → output /
○​ push *
5.​ E → output
6.​ + →
○​ * has higher precedence than +, pop * → output *
○​ push +
7.​ D → output
8.​ * → push *
9.​ C → output
10.​/ →
○​ * has equal precedence to /, pop * → output *
○​ push /
11.​B → output
12.​– →
○​ / has higher precedence than –, pop / → output /
○​ + has equal precedence to –, pop + → output +
○​ push –
13.​A → output​

End of expression: Pop remaining operator – → output

Postfix of reversed infix: G F / E * D C * B / + A –

Step 3: Reverse postfix to get prefix

 Reverse tokens: – A + / B C * D E * / F G
Final Prefix: – A + / B C * D E * / F G

e. ( ( A – ( B + C ) ) * D ) $ ( E + F )

Part 1: Convert to Postfix

Stepwise conversion:
●​ (B + C) → postfix: B C +
●​ A – (B + C) → postfix: A B C + -
●​ (A – (B + C)) * D → postfix: A B C + - D *
●​ (E + F) → postfix: E F +
●​ Whole expression: ((A – (B + C)) * D) $ (E + F) → postfix: A B C + - D * E F +
$​

Part 2: Convert to Prefix

Method: Reverse infix, swap parentheses, convert reversed to postfix, reverse result.

Step 1: Reverse infix and swap parentheses

Original: (( A – ( B + C )) * D) $ ( E + F )
Reversed: ( F + E ) $ ( D * ( ( C + B ) – A ) )
Swap ( and ): ( F + E ) $ ( D * ( ( C + B ) – A ) )

Parentheses remain symmetric, so no change here.

Step 2: Convert reversed infix to postfix

Expression: ( F + E ) $ ( D * ( ( C + B ) – A ) )
Break down:
●​ (F + E) → F E +
●​ (C + B) → C B +
●​ ( (C + B) – A ) → C B + A -
●​ D * ( (C + B) – A ) → D C B + A - *
●​ (F + E) $ (D * ((C + B) – A)) → F E + D C B + A - * $​

Step 3: Reverse postfix to get prefix

Postfix tokens: F E + D C B + A - * $
Reverse tokens: $ * - A + B C D + E F

Final Prefix: $ * - A + B C D + E F
 (23)​ Write and explain the POP operation algorithm of a stack.

Ans: POP Operation in a Stack

●​ To remove and return the top element from the stack.
●​ If the stack is empty (underflow condition), it should handle this case properly.

Assumptions:
●​ The stack is implemented using an array (or list).
●​ top is an integer variable indicating the current top position in the stack.
●​ stack is the array holding the elements.

Algorithm (Pseudo-code):
POP(stack):
if top == -1 then // stack is empty (underflow)
print "Stack Underflow"
return ERROR // or appropriate error value
else
element = stack[top] // get the top element
top = top - 1 // decrement top to remove the element
return element // return the popped element

Explanation:
1.​ Check if stack is empty: If top is -1 (or some value indicating empty), the stack is
empty, so POP cannot remove any element. This is called stack underflow.
2.​ Retrieve the element: The element at stack[top] is the current top of the stack.
3.​ Update the top: Decrement top by 1 to reflect the removal of the top element.
4.​ Return the popped element: The element removed from the stack is returned to the
caller.​

Example:
If stack = [10, 20, 30, 40] and top = 3 (pointing to 40), after POP(stack),
●​ The function returns 40,
●​ And the top becomes 2, so the new top is 30.
 (24)​ Write and explain the PUSH operation algorithm of a stack.

Ans:
PUSH Operation
●​ To add (push) an element to the top of the stack.
●​ Handle stack overflow when the stack is full.​

Assumptions:
●​ stack is an array of size MAX.
●​ top points to the current top index; -1 means empty.

Algorithm (Pseudo-code):
PUSH(stack, element):
if top == MAX - 1 then // stack is full
print "Stack Overflow"
return ERROR
else
top = top + 1 // increment top
stack[top] = element // place new element

Explanation:
1.​ Check if the stack is full (top == MAX - 1).
2.​ If full, report overflow and stop.
3.​ Otherwise, increase top and place the new element at stack[top].

POP Operation (Recap)

POP(stack):
if top == -1 then // stack empty
print "Stack Underflow"
return ERROR
else
element = stack[top]
top = top - 1
return element

Example for Both:

Initial: stack = [], top = -1
●​ PUSH 10 → stack = [10], top = 0
●​ PUSH 20 → stack = [10, 20], top = 1
●​ POP → returns 20, stack = [10, 20] (20 is still there but considered out), top = 0
●​ POP → returns 10, top = -1
 (25)​ Enlist and briefly explain various applications of stack.

Ans:
1. Solving Math Expressions
●​ Stacks help change math problems from normal form (like A + B) into easier forms to
calculate, and also help do the calculations step-by-step.

2. Handling Function Calls

●​ When one function calls another (or calls itself), the computer uses a stack to
remember where to come back and keep track of what it’s doing.

3. Undo Button in Programs

●​ When you do something, it gets saved on a stack. Pressing “undo” takes the last thing
you did off the stack and reverses it.

4. Checking Code for Mistakes

●​ Programmers use stacks to make sure brackets and parentheses in code match
correctly.​

5. Trying Different Paths (Backtracking)

●​ Stacks help computers try different options, like finding a way out of a maze by
remembering where they’ve been.​

6. Going Back in Web Browsers

●​ Browsers keep track of pages you visit using a stack so you can go back to the
previous page easily.​

7. Managing Memory
●​ Stacks help the computer organize memory by adding and removing things in order.​

8. Searching in Trees and Graphs

●​ Stacks help computers explore all parts of a tree or network by remembering which
parts to visit next.
 (26)​ Explain pointer with example

Ans:
●​ A pointer is a special variable that stores the address of another variable in memory
instead of the actual data.
Why use pointers?
●​ To directly access or modify variables in memory.
●​ To work efficiently with arrays, strings, and dynamic memory.
●​ To pass large data structures to functions without copying.
Example in C:
int x = 10; // A normal integer variable
int *p; // A pointer to an integer

p = &x; // Store the address of x in pointer p

printf("Value of x: %d\n", x); // Prints 10

printf("Address of x: %p\n", &x); // Prints the address of x
printf("Value stored in p: %p\n", p); // Prints the address stored in p (same as &x)
printf("Value pointed by p: %d\n", *p); // Prints the value at that address, 10

Explanation:
●​ int *p; declares a pointer to an integer.
●​ p = &x; assigns the address of x to the pointer p.
●​ *p means "value at the address stored in p" — so *p is the value of x.
●​ This allows us to access or change x using the pointer.

(27)​ List advantage and disadvantage of pointer

Ans:
Advantages of Pointers Disadvantages of Pointers
Efficient direct access to memory locations Can be complex and hard to understand

Allow dynamic memory allocation and Risk of errors like segmentation faults and
deallocation leaks

Enable passing large data to functions Can cause security vulnerabilities if misused
without copying

Essential for implementing data structures Debugging pointer-related errors is difficult

(linked lists, trees, etc.)

Simplify array and string manipulation via Dangling or null pointers can cause
pointer arithmetic undefined behavior
 (28)​ Difference between static memory allocation and dynamic memory
allocation

Ans:
Static Memory Allocation Dynamic Memory Allocation
Memory is Allocated At compile time Memory is Allocated At runtime

Fixed size, determined before program runs Size can change during program execution

Memory Lifetime Exists throughout the Memory Lifetime Exists until explicitly
program execution freed by the program

Memory Management: Managed Memory Management: Programmer is

automatically by the compiler responsible for allocation and deallocation
(e.g., malloc/free in C)

Examples: Global variables, static variables, Examples: Memory allocated using malloc,
local variables inside functions calloc, realloc in C

Faster allocation Slightly slower due to runtime allocation

Risk of Errors: Less prone to memory leaks Risk of Errors: Can cause memory leaks or
dangling pointers if not managed properly

(29)​ Difference between Link list and Sequential list

Ans:
Linked List Sequential List (Array)
Memory Allocation Dynamic Memory Allocation Static

Consists of nodes linked by pointers Contiguous block of memory storing

elements

Can easily grow by adding/removing nodes Size is fixed (unless dynamically resized)

Sequential access; no direct access to Direct access to any element using index
elements (O(1))

Efficient (especially at beginning or middle) Costly (may require shifting elements)

Uses extra memory for storing pointers Uses memory only for data elements

Poorer cache locality due to scattered Better cache locality due to contiguous
memory storage

More complex due to pointer management Simpler to implement