1. What is Data?

Answer:

Data refers to raw, unorganized facts (e.g., numbers, characters) that can be
processed to produce meaningful information.

Example in C:

c
int age = 25; // Integer data
char name[] = "Alice"; // String (character array) data
2. What is a Data Structure?
Answer:

A data structure is a way to organize and store data for efficient access and
modification.

Types: Arrays, linked lists, stacks, queues, trees, graphs.

Example (Array in C):

c
int arr[5] = {10, 20, 30, 40, 50}; // Static array
3. What is an Abstract Data Type (ADT)?
Answer:

An ADT is a mathematical model for data structures defined by its behavior

(operations) rather than implementation.

Example (Stack ADT):

c
// Operations: push(), pop(), peek()
struct Stack {
int top;
int items[MAX];
};
4. What is Algorithm Complexity?
Answer:

Algorithm complexity measures the resources (time/space) required by an algorithm

as input size grows.

Types:

Time Complexity: Steps needed (e.g., O(n)).

Space Complexity: Memory used (e.g., O(1)).

5. What are Time and Space Complexities?

Answer:

Time Complexity: Count of operations (e.g., O(n²) for nested loops).

Space Complexity: Memory usage (e.g., O(n) for an array of size n).

Example (Linear Search):

c
// Time: O(n), Space: O(1)
int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) return i;
}
return -1;
}
6. Asymptotic Notations & Algorithm Complexity
Answer:

Big-O (O): Upper bound (worst-case).

Theta (Θ): Tight bound (average-case).

Omega (Ω): Lower bound (best-case).

Example (Binary Search):

c
// Time: O(log n), Space: O(1)
int binarySearch(int arr[], int l, int r, int key) {
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] < key) l = mid + 1;
else r = mid - 1;
}
return -1;
}
7. What are Strings?
Answer:

Strings are sequences of characters terminated by \0 (null character).

C Implementation:

c
char str[] = "Hello"; // Stored as {'H', 'e', 'l', 'l', 'o', '\0'}
Operations:

c
#include <string.h>
strlen(str); // Length
strcpy(dest, src); // Copy
strcat(str1, str2); // Concatenation
Key Takeaways
Data Structures organize data (e.g., arrays, linked lists).

ADTs define behavior (e.g., stack operations).

Complexity measures efficiency (time/space).

Strings are character arrays in C.

8. Seven String Operations with C Programs (5 Marks)

1. String Length (strlen)
Purpose: Returns the length of a string (excluding \0).
Program:

c
#include <stdio.h>
#include <string.h>

int main() {
char str[] = "Hello";
printf("Length: %lu\n", strlen(str)); // Output: 5
return 0;
}
2. String Copy (strcpy)
Purpose: Copies a string to another.
Program:

c
#include <stdio.h>
#include <string.h>

int main() {
char src[] = "Copy Me";
char dest[20];
strcpy(dest, src);
printf("Copied: %s\n", dest); // Output: "Copy Me"
return 0;
}
3. String Concatenation (strcat)
Purpose: Appends one string to another.
Program:

c
#include <stdio.h>
#include <string.h>

int main() {
char str1[20] = "Hello";
char str2[] = " World";
strcat(str1, str2);
printf("Concatenated: %s\n", str1); // Output: "Hello World"
return 0;
}
4. String Comparison (strcmp)
Purpose: Compares two strings lexicographically.
Program:

c
#include <stdio.h>
#include <string.h>

int main() {
char str1[] = "apple";
char str2[] = "banana";
int result = strcmp(str1, str2);
printf("Comparison: %d\n", result); // Output: -1 (str1 < str2)
return 0;
}
5. Substring Search (strstr)
Purpose: Finds the first occurrence of a substring.
Program:
c
#include <stdio.h>
#include <string.h>

int main() {
char str[] = "Hello World";
char sub[] = "World";
char *pos = strstr(str, sub);
printf("Found at: %s\n", pos); // Output: "World"
return 0;
}
6. String Reversal
Purpose: Reverses a string in-place.
Program:

c
#include <stdio.h>
#include <string.h>

void reverse(char *str) {

int n = strlen(str);
for (int i = 0; i < n / 2; i++) {
char temp = str[i];
str[i] = str[n - i - 1];
str[n - i - 1] = temp;
}
}

int main() {
char str[] = "Hello";
reverse(str);
printf("Reversed: %s\n", str); // Output: "olleH"
return 0;
}
7. String Tokenization (strtok)
Purpose: Splits a string into tokens using delimiters.
Program:

c
#include <stdio.h>
#include <string.h>

int main() {
char str[] = "Hello,World,C";
char *token = strtok(str, ",");
while (token != NULL) {
printf("Token: %s\n", token);
token = strtok(NULL, ",");
}
return 0;
}
Output:

text
Token: Hello
Token: World
Token: C
9. Pattern-Matching Algorithms with C Programs (5 Marks)
1. Naive Pattern Matching
Purpose: Checks for a pattern by sliding it over the text.
Program:

c
#include <stdio.h>
#include <string.h>

void naiveSearch(char *text, char *pattern) {

int n = strlen(text);
int m = strlen(pattern);
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) break;
}
if (j == m) printf("Pattern found at index %d\n", i);
}
}

int main() {
char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABC";
naiveSearch(text, pattern); // Output: "Pattern found at index 10"
return 0;
}
2. Knuth-Morris-Pratt (KMP) Algorithm
Purpose: Optimizes pattern matching using the LPS (Longest Prefix Suffix) array.
Program:

c
#include <stdio.h>
#include <string.h>

void computeLPS(char *pattern, int m, int *lps) {

int len = 0;
lps[0] = 0;
for (int i = 1; i < m; ) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) len = lps[len - 1];
else lps[i++] = 0;
}
}
}

void KMPSearch(char *text, char *pattern) {

int n = strlen(text);
int m = strlen(pattern);
int lps[m];
computeLPS(pattern, m, lps);
int i = 0, j = 0;
while (i < n) {
if (pattern[j] == text[i]) { i++; j++; }
if (j == m) {
printf("Pattern found at index %d\n", i - j);
 j = lps[j - 1];
} else if (i < n && pattern[j] != text[i]) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
}

int main() {
char text[] = "ABABDABACDABABCABAB";
char pattern[] = "ABABC";
KMPSearch(text, pattern); // Output: "Pattern found at index 10"
return 0;
}
10. Word Processing: Operations & Examples (5 Marks)
Definition:
Word processing involves creating, editing, formatting, and printing text documents
using software (e.g., MS Word, Google Docs).

Operations with Examples:

Text Editing:

Insert/delete characters.

Example: Correcting "Teh" → "The".

Formatting:

Font styles (bold, italic), alignment.

Example: Making headings bold and centered.

Spell Check:

Detects misspelled words (e.g., "recieve" → "receive").

Page Layout:

Margins, page size, columns.

Example: Setting 1-inch margins for a report.

Save & Print:

Save as .docx, .pdf, or print hard copies.

Example Workflow:
Draft a letter.

Edit text (fix typos).

Format with Arial font.

Spell-check.

Save as "Letter.docx".

Key Takeaways
String Operations: Use string.h functions for efficient manipulation.
Pattern Matching:

Naive: Simple but slow (O(mn)).

KMP: Optimized (O(n + m)).

Word Processing: Essential for document management in offices/education.

11. Syntax and Examples for if, if-else, while, for (5 Marks)
1. if Statement
Syntax:

c
if (condition) {
// Code to execute if condition is true
}
Example:

c
int x = 10;
if (x > 5) {
printf("x is greater than 5\n"); // Output: "x is greater than 5"
}
2. if-else Statement
Syntax:

c
if (condition) {
// Code if true
} else {
// Code if false
}
Example:

c
int age = 17;
if (age >= 18) {
printf("Adult\n");
} else {
printf("Minor\n"); // Output: "Minor"
}
3. while Loop
Syntax:

c
while (condition) {
// Code to repeat while condition is true
}
Example:

c
int i = 1;
while (i <= 3) {
printf("%d ", i); // Output: "1 2 3 "
i++;
}
4. for Loop
Syntax:

c
for (initialization; condition; update) {
// Code to repeat
}
Example:

c
for (int i = 0; i < 3; i++) {
printf("%d ", i); // Output: "0 1 2 "
}
12. Worst, Best, and Average Case Efficiency with Graphs (5 Marks)
1. Worst Case
Definition: Maximum time/space required for the largest input.

Example: Linear search when the key is not present (O(n)).

Graph:

plaintext
Time
↑
| Worst Case (O(n))
| /
| /
|____/________→ Input Size
2. Best Case
Definition: Minimum time/space required for the smallest input.

Example: Linear search when the key is at the first index (O(1)).

Graph:

plaintext
Time
↑
| Best Case (O(1))
| /
|_____/________→ Input Size
3. Average Case
Definition: Expected time/space for random inputs.

Example: Quicksort (O(n log n) on average).

Graph:

plaintext
Time
↑
| Average Case (O(n log n))
| /
| /
|____/________→ Input Size
Key Points:
Worst Case: Used for guarantees (e.g., real-time systems).

Best Case: Rarely used (optimistic scenarios).

Average Case: Most practical for general analysis.

13. malloc, calloc, realloc, free (5 Marks)

1. malloc (Memory Allocation)
Purpose: Allocates uninitialized memory.

Syntax:

c
ptr = (datatype*) malloc(size_in_bytes);
Example:

c
int *arr = (int*) malloc(5 * sizeof(int)); // Allocates 20 bytes (5 ints)
2. calloc (Contiguous Allocation)
Purpose: Allocates zero-initialized memory.

Syntax:

c
ptr = (datatype*) calloc(num_items, size_per_item);
Example:

c
int *arr = (int*) calloc(5, sizeof(int)); // Allocates and initializes to 0
3. realloc (Reallocation)
Purpose: Resizes previously allocated memory.

Syntax:

c
ptr = (datatype*) realloc(ptr, new_size_in_bytes);
Example:

c
arr = (int*) realloc(arr, 10 * sizeof(int)); // Resizes to 40 bytes
4. free (Deallocation)
Purpose: Releases allocated memory to prevent leaks.

Syntax:

c
free(ptr);
Example:

c
free(arr); // Frees the memory
arr = NULL; // Prevents dangling pointer
Key Differences:
Function Initialization Use Case
malloc No Dynamic arrays
calloc Yes (zero) Arrays needing zeros
realloc No Resizing memory
Key Takeaways
Control Structures:

if/else for decisions, while/for for loops.

Complexity Analysis:

Graphs show how time scales with input size.

Memory Management:

Always pair malloc/calloc with free to avoid leaks.

14. Different Storage Representations of Strings (5 Marks)

1. Fixed-Length (Array-Based) Representation
Description:

Strings are stored in fixed-size arrays with a null terminator (\0).

Max length is predefined (e.g., char str[100]).

Example:

c
char str[10] = "Hello"; // Stored as {'H', 'e', 'l', 'l', 'o', '\0', ...}
Pros:

Fast random access (O(1)).

Cons:

Wastes memory if unused.

2. Dynamic (Heap-Based) Representation

Description:

Strings are allocated dynamically using malloc/calloc.

Size can be adjusted with realloc.

Example:

c
char *str = (char*)malloc(6 * sizeof(char));
strcpy(str, "Hello"); // Stored as {'H', 'e', 'l', 'l', 'o', '\0'}
Pros:

Flexible size.

Cons:

Manual memory management (free required).

3. Linked List Representation

Description:

Each character is stored in a linked list node.

Example:

c
struct Node {
char data;
struct Node *next;
};
Pros:

No size limit.

Cons:

Slow random access (O(n)).

4. Length-Prefixed Representation
Description:

The first byte stores the string length.

Example:

c
char str[] = {5, 'H', 'e', 'l', 'l', 'o'}; // Length = 5
Pros:

Faster length calculation (O(1)).

Cons:

Limited to 255 characters (1-byte length).

15. Insert and Delete a String (Algorithm & Program) (5 Marks)

1. Insert a String
Algorithm:

Allocate memory for the new string (if dynamic).

Concatenate the new string at the desired position.

Program:

c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void insertString(char **mainStr, const char *insertStr, int pos) {

int mainLen = strlen(*mainStr);
int insertLen = strlen(insertStr);
char *newStr = (char*)malloc(mainLen + insertLen + 1);

strncpy(newStr, *mainStr, pos); // Copy first part

newStr[pos] = '\0';
strcat(newStr, insertStr); // Insert new string
strcat(newStr, *mainStr + pos); // Append remaining part

free(*mainStr); // Free old string

*mainStr = newStr;
}

int main() {
 char *str = strdup("Hello World"); // Dynamic string
insertString(&str, "C ", 6);
printf("After insertion: %s\n", str); // Output: "Hello C World"
free(str);
return 0;
}
2. Delete a Substring
Algorithm:

Find the substring using strstr.

Shift characters left to overwrite the substring.

Program:

c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void deleteSubstring(char *str, const char *sub) {

char *pos = strstr(str, sub);
if (pos) {
int subLen = strlen(sub);
memmove(pos, pos + subLen, strlen(pos + subLen) + 1); // +1 for '\0'
}
}

int main() {
char str[] = "Hello World";
deleteSubstring(str, "World");
printf("After deletion: %s\n", str); // Output: "Hello "
return 0;
}
Key Takeaways
String Storage:

Fixed arrays for simplicity, dynamic for flexibility.

Insert/Delete:

Use strcat/memmove for efficient operations.

Dynamic strings require manual memory management.