12 IT in Society

1- How do you think a business could make use of data mining when hiring staff?

The business could mine data about what kind of qualifications and what kind of people are employed by its competitors. The business could use data mining to find out what characteristics of an employee are a good match for their company

Exam-style questions 

 1. Explain what is meant by a cryptocurrency. (3)

All of the following [3]: 

• A cryptocurrency is a type of digital currency. 

• A cryptocurrency is decentralised. 

• A cryptocurrency uses encryption algorithms and cryptographic techniques as a security method. 

 2. Explain two advantages and two disadvantages of the use of digital currency. (4)

Four from the following (two per advantage and disadvantage) [4]: 

 Advantages • Don’t need to carry physical money. 

 • User can stop transactions if digital method is lost/stolen. 

 • All transactions are encrypted.

 • Can speed up payment. 

 • Don’t need to exchange physical currency in foreign countries. Disadvantages

 • Always the risk that a transaction can be hacked. 

 • Some people may lose track of their spending as they don’t hand over actual money. 

 • Some people are anxious about using digital payment methods, especially contactless ones

3. Explain the difference between a chat room and a forum. [4] 

Four from [4]:

 • A chatroom is an online service that allows multiple users to send each other instant messages Review Copy - Cambridge University Press - Review Copy 

 • … whereas a forum allows users to post questions and thoughts for other users to respond to. 

 • A chatroom is designed to be a live conversation 

 • … whereas a forum is designed to allow user to return to the forum at any time to see what other users have posed as a response. 

 • A chatroom is not normally monitored by a moderator

 • whereas a forum will often have a moderator checking the posts meet the rules.

4. Describe the process of data mining. [8] 

Eight from [8]: 

 • Stage 1 is the business understanding stage 

 • … it is where the objectives are set and the criteria for success are established. 

 • Stage 2 is the data understanding stage

•… this involves the initial collection of data from the various sources available. 

 • Stage 3 is the data preparation stage 

 • … this is where the data is taken through a whole process of selection, cleansing, construction and formatting. 

 • Stage 4 is the data modelling stage 

 • … during this stage various test scenarios are generated to model the data. 

 • Stage 5 is the evaluation stage 

 • … this is when the results generated by the models are evaluated. 

 • Stage 6 is the deployment stage 

 • … this is when a report is created to present the findings of the data mining to stakeholders.

5. Explain two ways that data mining can be used. [4] 

Four from [4]: 

 • It can be used by businesses to aid planning 

 • … informing any actions that are taken on a daily basis. 

 • It can be used by governments to aid national security 

 • … by analysing intelligence gathered to highlight current activity in a country. 

 • It can be used in surveillance 

 • … surveillance data can be analysed to predict issues such as criminal activity.

6. Explain two advantages and one disadvantage of learners using a MOOC to improve their work-based skill set. [6] 

 Six from (max four for advantages) [6]:

 Advantages 

 • A large selection of courses are available 

 • … so a user can enhance their learning in anything that they are interested it. 

 • Can provide an employee with a competitive advantage 

* … as it demonstrates their motivation to learn and improve in their own time. 

 • They are free of cost 

 • … so all users who can access them will be able to learn. 

 • The number of people on a course is often unlimited

 • … so people do not have to wait for a place to become available. 

 • User can learn at their own rate 

 • … this means that users are more able to fit the learning around the own schedule. 

 Disadvantages 

 • There are a huge selection of courses available 

 • … this may overwhelm a learner if they do not know which one to choose. • There are often a large number of people on a course 

 • … so the tutor/educator may not have a lot of dedicated time to help each person on the course. 

 • … it may also be difficult for a tutor/education to keep track of the progress of each person on the course. 

 • Some learners may struggle to complete the tasks 

 • … and may choose to only complete those ones that they know will be assessed. 

7. Discuss the impact of the central bank moving to a digital based currency only. [6] 

Six from [6]: 

• This would mean that banks create their own version of a digital currency. 

 • This may mean that physical currency disappears altogether. 

• This could save money for the government as they do not need to think about the cost of creating the physical currency. 

• This could save the bank money as they do not need to have huge security system in places, like vaults, in which physical currency is stored. 

• This could cost the banks money as they will need to have very strong security systems for their digital currency. 

 * The speed of the exchange of money from bank to bank could be improved. 

 • Criminal activity such as money laundering may decrease. 

 • Some people do not like the idea of the invasion of privacy that will exist by tracking each digital currency transaction.

8. Discuss the impact of the use of IT in banking and finance. [6]
All of the following [6]: 
• Banks heavily rely on IT to keep all the records about their customers. If they had to store paper versions of this data, it would take up huge amounts of physical storage space. 
• IT can be used in the form of ATMs to access physical currency that we have stored in our bank account. This means that a user no longer needs to go into a bank branch to queue to get money out of their account.
 • IT can be used for online banking, allowing a user to access many financial and banking facilities online, without the need to go into a bank branch. 
• IT can be used for online banking, allowing users to access many banking and financial services 24/7. 
• IT can be used for online banking, allowing users to see all the transactions instantly, without needing to wait for a paper statement to be delivered. 
• People can use comparison websites to compare the offers of banks and financial services. This means they can easily find the best and right deal for their circumstances

DATA STRUCTURE IN C

 1. Basic Concepts of Data Structures

1.1 DefinitionsWhat: A data structure is a way to organize and store data to enable efficient operations (e.g., insertion, deletion, search). Examples include arrays, linked lists, stacks, queues, trees, and graphs.Why: In mobile software, data structures manage device information (e.g., lists of connected devices), optimize performance (e.g., fast searches for device IDs), and reduce resource usage on resource-constrained devices like smartphones.How: No specific code is needed for definitions, but we’ll use arrays as a basic example to store device IDs.
Code Example (Array for Device IDs):

#include <stdio.h>
#define MAX_DEVICES 5

// Array to store device IDs
int deviceIds[MAX_DEVICES] = {101, 102, 103, 104, 105};

int main() {
    // Print device IDs
    printf("Device IDs: ");
    for (int i = 0; i < MAX_DEVICES; i++) {
        printf("%d ", deviceIds[i]);
    }
    printf("\n");
    return 0;
}

Explanation:

• What: The array deviceIds is a simple data structure storing integers.
• Why: Arrays provide fast access (O(1)) for device IDs in a mobile system.
• How: Fixed-size array stores IDs, accessed by index. In mobile software, arrays could store device configurations or status codes.

---

1.2 Data AbstractionWhat: Data abstraction hides implementation details, exposing only essential operations (e.g., a stack’s push/pop without showing the underlying array).Why: Simplifies code for mobile developers, allowing focus on functionality (e.g., managing a call stack) without worrying about internal storage.How: Use a struct with functions to abstract a stack.Code Example (Stack Abstraction):

#include <stdio.h>
#define MAX_SIZE 5

// Stack structure
typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

// Initialize stack
void initStack(Stack *s) {
    s->top = -1; // Empty stack
}

// Push operation
void push(Stack *s, int value) {
    if (s->top < MAX_SIZE - 1) {
        s->items[++(s->top)] = value;
        printf("Pushed %d\n", value);
    } else {
        printf("Stack overflow\n");
    }
}

// Pop operation
int pop(Stack *s) {
    if (s->top >= 0) {
        return s->items[(s->top)--];
    }
    printf("Stack underflow\n");
    return -1;
}

int main() {
    Stack s;
    initStack(&s);
    push(&s, 1); // Push device status code
    push(&s, 2);
    printf("Popped: %d\n", pop(&s)); // Retrieve status
    return 0;
}

Explanation:

• What: The Stack struct and functions (push, pop) hide the array implementation.
• Why: Abstraction allows mobile developers to use a stack for tasks like managing undo operations in a device app without handling array indices.
• How: Users call push/pop without accessing items directly, ensuring safe usage.

---

1.3 Performance Analysis - Time & Space ComplexityWhat: Time complexity measures the execution time of an algorithm (e.g., O(n) for linear search). Space complexity measures memory usage.Why: Critical in mobile software to ensure fast performance (e.g., quick device searches) and low memory usage on constrained devices.How: Analyze a simple linear search for a device ID.Code Example (Linear Search):

#include <stdio.h>
#define MAX_DEVICES 5

int linearSearch(int arr[], int size, int key) {
    for (int i = 0; i < size; i++) { // O(n) time
        if (arr[i] == key) {
            return i; // Found device ID
        }
    }
    return -1; // Not found
}

int main() {
    int deviceIds[MAX_DEVICES] = {101, 102, 103, 104, 105}; // O(n) space
    int key = 103;
    int result = linearSearch(deviceIds, MAX_SIZE, key);
    printf(result >= 0 ? "Device found at index %d\n" : "Device not found\n", result);
    return 0;
}

Explanation:

• What: Time complexity is O(n) (linear scan), space complexity is O(1) (no extra space beyond input array).
• Why: In mobile software, understanding complexity helps choose algorithms (e.g., linear search vs. binary search) for device lookups.
• How: The code iterates through the array, checking each element, demonstrating linear time.

---

1.4 Asymptotic Notations - Big Oh, Omega, ThetaWhat: Asymptotic notations describe algorithm performance:

• Big Oh (O): Upper bound (worst-case time/space).
• Omega (Ω): Lower bound (best-case).
• Theta (Θ): Tight bound (average case).

Why: Helps predict performance in mobile software, ensuring scalability for large device datasets (e.g., thousands of connected devices).How: Analyze insertion into an array.Code Example (Array Insertion at End):

#include <stdio.h>
#define MAX_SIZE 5

typedef struct {
    int items[MAX_SIZE];
    int size;
} DeviceList;

// Insert at end: O(1) time
void insertDevice(DeviceList *list, int deviceId) {
    if (list->size < MAX_SIZE) {
        list->items[list->size++] = deviceId; // O(1)
        printf("Inserted %d\n", deviceId);
    } else {
        printf("List full\n");
    }
}

int main() {
    DeviceList list = {{0}, 0};
    insertDevice(&list, 101); // O(1)
    insertDevice(&list, 102);
    return 0;
}

Explanation:

• What: Insertion at the end is O(1) (Big Oh), as it’s constant time. Best case (Ω) and average case (Θ) are also O(1) for this operation.
• Why: In mobile software, O(1) operations are preferred for real-time tasks like adding a device to a list.
• How: The code appends to the array’s end, requiring only one operation.

Big Oh Problem Example: If insertion required shifting elements (e.g., sorted array), time complexity is O(n) due to shifting:

// Insert into sorted array: O(n)
void insertSorted(DeviceList *list, int deviceId) {
    if (list->size < MAX_SIZE) {
        int i = list->size - 1;
        while (i >= 0 && list->items[i] > deviceId) { // Shift elements
            list->items[i + 1] = list->items[i];
            i--;
        }
        list->items[i + 1] = deviceId; // Insert
        list->size++;
    }
}

---

1.5 Polynomial Representation Using ArraysWhat: Polynomials (e.g., 3x² + 2x + 1) are represented as arrays where each index corresponds to a degree and stores the coefficient.Why: Useful in mobile software for calculations, like signal processing or battery usage models.How: Store coefficients in an array.Code Example:

#include <stdio.h>
#define MAX_DEGREE 10

typedef struct {
    int coeffs[MAX_DEGREE + 1]; // coeffs[i] is coefficient of x^i
    int degree;
} Polynomial;

// Evaluate polynomial at x
double evaluatePolynomial(Polynomial *p, double x) {
    double result = 0;
    for (int i = 0; i <= p->degree; i++) {
        result += p->coeffs[i] * pow(x, i); // O(n) time
    }
    return result;
}

int main() {
    Polynomial p = {{1, 2, 3}, 2}; // 3x² + 2x + 1
    printf("Value at x=2: %.2f\n", evaluatePolynomial(&p, 2.0)); // 3*4 + 2*2 + 1 = 17
    return 0;
}

Explanation:

• What: Array coeffs stores coefficients (e.g., {1, 2, 3} for 3x² + 2x + 1).
• Why: Efficient for polynomial operations in mobile apps (e.g., modeling battery drain).
• How: The code evaluates the polynomial by computing each term, with O(n) time complexity.

---

1.6 Sparse Matrix (Tuple Representation)What: A sparse matrix (mostly zeros) is stored as a list of tuples (row, col, value) to save space.Why: In mobile software, sparse matrices optimize storage for large datasets, like network connectivity maps.How: Use an array of structs for tuples.Code Example:

#include <stdio.h>
#define MAX_ELEMENTS 10

typedef struct {
    int row, col, value;
} Tuple;

typedef struct {
    Tuple elements[MAX_ELEMENTS];
    int numElements, rows, cols;
} SparseMatrix;

// Add non-zero element
void addElement(SparseMatrix *m, int row, int col, int value) {
    if (m->numElements < MAX_ELEMENTS && value != 0) {
        m->elements[m->numElements].row = row;
        m->elements[m->numElements].col = col;
        m->elements[m->numElements].value = value;
        m->numElements++;
    }
}

int main() {
    SparseMatrix m = {{0}, 0, 3, 3}; // 3x3 matrix
    addElement(&m, 0, 1, 5); // Matrix[0][1] = 5
    addElement(&m, 2, 2, 7); // Matrix[2][2] = 7
    for (int i = 0; i < m.numElements; i++) {
        printf("(%d, %d, %d)\n", m.elements[i].row, m.elements[i].col, m.elements[i].value);
    }
    return 0;
}

Explanation:

• What: Stores non-zero elements as tuples (e.g., (0, 1, 5)).
• Why: Saves memory in mobile apps for large, sparse datasets (e.g., device network graphs).
• How: The code stores only non-zero values, reducing space from O(rows * cols) to O(non-zero elements).

---

1.7 Stacks and QueuesWhat:

• Stack: LIFO (Last In, First Out) structure (e.g., push/pop).
• Queue: FIFO (First In, First Out) structure (e.g., enqueue/dequeue).
• Circular Queue: Queue with wrap-around to reuse space.
• Double-Ended Queue (Deque): Allows insertion/deletion at both ends.

Why: Stacks manage function calls or undo operations in mobile apps; queues handle tasks like message processing; circular queues optimize memory; deques support flexible operations.How: Implement a stack using an array.Code Example (Stack):

#include <stdio.h>
#define MAX_SIZE 5

typedef struct {
    int items[MAX_SIZE];
    int top;
} Stack;

void push(Stack *s, int value) {
    if (s->top < MAX_SIZE - 1) {
        s->items[++(s->top)] = value;
    }
}

int pop(Stack *s) {
    if (s->top >= 0) {
        return s->items[(s->top)--];
    }
    return -1;
}

int main() {
    Stack s = {{0}, -1};
    push(&s, 1); // Push device task
    push(&s, 2);
    printf("Popped: %d\n", pop(&s)); // Process task
    return 0;
}

Explanation:

• What: Stack uses an array with top to track the last element.
• Why: Useful for mobile apps to manage call stacks or undo actions (e.g., navigation history).
• How: Push adds to the top (O(1)); pop removes from the top (O(1)).

---

1.8 Evaluation of Expressions (Infix to Postfix, Postfix Evaluation)What: Convert infix expressions (e.g., 3 + 4 * 2) to postfix (e.g., 3 4 2 * +) and evaluate postfix expressions.Why: In mobile software, expression evaluation is used in calculators or configuration parsers.How: Implement infix to postfix conversion.Code Example:

#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100

typedef struct {
    char items[MAX_SIZE];
    int top;
} Stack;

void push(Stack *s, char c) {
    if (s->top < MAX_SIZE - 1) s->items[++(s->top)] = c;
}

char pop(Stack *s) {
    if (s->top >= 0) return s->items[(s->top)--];
    return '\0';
}

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

void infixToPostfix(char *infix, char *postfix) {
    Stack s = {{0}, -1};
    int k = 0;
    for (int i = 0; infix[i]; i++) {
        if (infix[i] >= '0' && infix[i] <= '9') {
            postfix[k++] = infix[i]; // Operand
        } else if (infix[i] == '(') {
            push(&s, infix[i]);
        } else if (infix[i] == ')') {
            while (s.top >= 0 && s.items[s.top] != '(') {
                postfix[k++] = pop(&s);
            }
            pop(&s); // Remove '('
        } else { // Operator
            while (s.top >= 0 && precedence(s.items[s.top]) >= precedence(infix[i])) {
                postfix[k++] = pop(&s);
            }
            push(&s, infix[i]);
        }
    }
    while (s.top >= 0) {
        postfix[k++] = pop(&s);
    }
    postfix[k] = '\0';
}

int main() {
    char infix[] = "3+4*2";
    char postfix[MAX_SIZE];
    infixToPostfix(infix, postfix);
    printf("Postfix: %s\n", postfix); // Output: 342*+
    return 0;
}

Explanation:

• What: Converts infix to postfix using a stack to manage operators.
• Why: Postfix eliminates parentheses, simplifying evaluation in mobile apps.
• How: Operands go directly to output; operators are pushed/popped based on precedence.

---

2. Linked List and Memory Management2.1 Singly Linked ListWhat: A linked list is a sequence of nodes, each containing data and a pointer to the next node.Why: In mobile software, linked lists manage dynamic data (e.g., a list of active devices) with flexible size.How: Implement insertion and display.Code Example:

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

typedef struct Node {
    int deviceId;
    struct Node *next;
} Node;

Node* createNode(int deviceId) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->deviceId = deviceId;
    newNode->next = NULL;
    return newNode;
}

void insertNode(Node **head, int deviceId) {
    Node *newNode = createNode(deviceId);
    newNode->next = *head; // Insert at head
    *head = newNode;
}

void displayList(Node *head) {
    Node *current = head;
    while (current) {
        printf("%d -> ", current->deviceId);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    Node *head = NULL;
    insertNode(&head, 101);
    insertNode(&head, 102);
    displayList(head); // Output: 102 -> 101 -> NULL
    return 0;
}

Explanation:

• What: Each node holds a device ID and a pointer to the next node.
• Why: Linked lists allow dynamic resizing, unlike arrays, for managing device lists.
• How: insertNode adds at the head (O(1)); displayList traverses the list (O(n)).

---

2.2 Stacks and Queues Using Linked ListWhat: Stacks and queues implemented with linked lists for dynamic size.Why: More flexible than array-based stacks/queues for mobile apps handling variable tasks.How: Implement a linked list-based stack.Code Example:

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

void push(Stack *s, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = s->top;
    s->top = newNode;
}

int pop(Stack *s) {
    if (!s->top) return -1;
    Node *temp = s->top;
    int data = temp->data;
    s->top = s->top->next;
    free(temp);
    return data;
}

int main() {
    Stack s = {NULL};
    push(&s, 1); // Push task
    push(&s, 2);
    printf("Popped: %d\n", pop(&s)); // Output: 2
    return 0;
}

Explanation:

• What: Stack uses linked list nodes for LIFO operations.
• Why: Dynamic size is ideal for mobile apps with unpredictable task counts.
• How: push adds at the head (O(1)); pop removes from the head (O(1)).

---

2.3 Polynomial Representation Using Linked ListWhat: Polynomials are represented as linked lists where each node stores a coefficient and degree.Why: More efficient for sparse polynomials in mobile apps (e.g., signal processing).How: Implement evaluation.Code Example:

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

typedef struct Node {
    int coeff, degree;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
} Polynomial;

void addTerm(Polynomial *p, int coeff, int degree) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->coeff = coeff;
    newNode->degree = degree;
    newNode->next = p->head;
    p->head = newNode;
}

double evaluatePolynomial(Polynomial *p, double x) {
    double result = 0;
    Node *current = p->head;
    while (current) {
        result += current->coeff * pow(x, current->degree);
        current = current->next;
    }
    return result;
}

int main() {
    Polynomial p = {NULL};
    addTerm(&p, 3, 2); // 3x²
    addTerm(&p, 2, 1); // 2x
    addTerm(&p, 1, 0); // 1
    printf("Value at x=2: %.2f\n", evaluatePolynomial(&p, 2.0)); // 17.00
    return 0;
}

Explanation:

• What: Each node stores a term (coefficient, degree).
• Why: Saves space for sparse polynomials in mobile calculations.
• How: addTerm inserts terms; evaluatePolynomial computes the value (O(n)).

---

2.4 Doubly Linked ListWhat: A linked list where each node has pointers to both the next and previous nodes.Why: Allows bidirectional traversal, useful for mobile apps navigating device lists.How: Implement insertion.Code Example:

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

typedef struct Node {
    int data;
    struct Node *prev, *next;
} Node;

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

void insertNode(Node **head, int data) {
    Node *newNode = createNode(data);
    if (!*head) {
        *head = newNode;
    } else {
        newNode->next = *head;
        (*head)->prev = newNode;
        *head = newNode;
    }
}

int main() {
    Node *head = NULL;
    insertNode(&head, 101);
    insertNode(&head, 102);
    for (Node *current = head; current; current = current->next) {
        printf("%d ", current->data);
    }
    printf("\n"); // Output: 102 101
    return 0;
}

Explanation:

• What: Nodes have prev and next pointers.
• Why: Useful for mobile apps needing to traverse device lists backward/forward.
• How: insertNode adds at the head, updating pointers (O(1)).

---

2.5 Circular Linked ListWhat: A linked list where the last node points to the first, forming a loop.Why: Useful for cyclic tasks in mobile apps, like rotating device status checks.How: Implement display.Code Example:

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

void insertNode(Node **head, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    if (!*head) {
        *head = newNode;
        newNode->next = newNode;
    } else {
        newNode->next = (*head)->next;
        (*head)->next = newNode;
    }
}

void displayList(Node *head) {
    if (!head) return;
    Node *current = head;
    do {
        printf("%d ", current->data);
        current = current->next;
    } while (current != head);
    printf("\n");
}

int main() {
    Node *head = NULL;
    insertNode(&head, 101);
    insertNode(&head, 102);
    displayList(head); // Output: 101 102
    return 0;
}

Explanation:

• What: Last node links to the first.
• Why: Ideal for cyclic operations in mobile apps (e.g., polling devices).
• How: displayList loops until it reaches the head again.

---

2.6 Memory Allocation (First-Fit, Best-Fit, Worst-Fit)What: Memory allocation schemes assign memory blocks to processes:

• First-Fit: Allocates the first block large enough.
• Best-Fit: Allocates the smallest block that fits.
• Worst-Fit: Allocates the largest block.

Why: In mobile software, efficient memory allocation optimizes resource usage on devices with limited RAM.How: Simulate first-fit allocation.Code Example:

#include <stdio.h>
#define MAX_BLOCKS 5

typedef struct {
    int size;
    int allocated;
} Block;

void firstFit(Block blocks[], int n, int processSize) {
    for (int i = 0; i < n; i++) {
        if (!blocks[i].allocated && blocks[i].size >= processSize) {
            blocks[i].allocated = 1;
            printf("Allocated %d to block %d (size %d)\n", processSize, i, blocks[i].size);
            return;
        }
    }
    printf("No block found for size %d\n", processSize);
}

int main() {
    Block blocks[MAX_BLOCKS] = {{100, 0}, {50, 0}, {200, 0}, {150, 0}, {300, 0}};
    firstFit(blocks, MAX_BLOCKS, 120); // Allocates to block 2 (200)
    return 0;
}

Explanation:

• What: firstFit finds the first block large enough.
• Why: Simple and fast for mobile apps allocating memory for tasks.
• How: Iterates blocks, allocates the first suitable one (O(n)).

---

3. Trees and Graphs3.1 Trees - Representation and Binary TreesWhat: A tree is a hierarchical structure with nodes connected by edges. A binary tree has at most two children per node.Why: In mobile software, trees organize hierarchical data (e.g., file systems, device menus).How: Implement a binary tree.Code Example:

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

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    Node *root = createNode(1); // Root
    root->left = createNode(2); // Left child
    root->right = createNode(3); // Right child
    printf("Root: %d, Left: %d, Right: %d\n", root->data, root->left->data, root->right->data);
    return 0;
}

Explanation:

• What: Each node has data and pointers to left/right children.
• Why: Binary trees are used in mobile apps for efficient data organization.
• How: createNode builds a tree structure.

---

3.2 Tree Traversals (Inorder, Preorder, Postorder)What: Traversals visit nodes in specific orders:

• Inorder: Left, Root, Right.
• Preorder: Root, Left, Right.
• Postorder: Left, Right, Root.

Why: Used in mobile apps for tasks like rendering menu hierarchies.How: Implement inorder traversal.Code Example:

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

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void inorder(Node *root) {
    if (root) {
        inorder(root->left);
        printf("%d ", root->data); // Visit root
        inorder(root->right);
    }
}

int main() {
    Node *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    inorder(root); // Output: 2 1 3
    printf("\n");
    return 0;
}

Explanation:

• What: Inorder visits left subtree, root, then right subtree.
• Why: Produces sorted output for binary search trees, useful in mobile apps.
• How: Recursive function traverses the tree (O(n)).

---

3.3 Binary Search Trees (BST)What: A binary tree where left child < root < right child, enabling efficient search.Why: In mobile software, BSTs enable fast lookups (e.g., finding a device by ID).How: Implement search.Code Example:

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

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

Node* insertBST(Node *root, int data) {
    if (!root) return createNode(data);
    if (data < root->data)
        root->left = insertBST(root->left, data);
    else
        root->right = insertBST(root->right, data);
    return root;
}

Node* searchBST(Node *root, int key) {
    if (!root || root->data == key) return root;
    if (key < root->data) return searchBST(root->left, key);
    return searchBST(root->right, key);
}

int main() {
    Node *root = NULL;
    root = insertBST(root, 50);
    insertBST(root, 30);
    insertBST(root, 70);
    Node *result = searchBST(root, 30);
    printf(result ? "Found %d\n" : "Not found\n", 30);
    return 0;
}

Explanation:

• What: BST organizes data for O(log n) average-case search.
• Why: Efficient for mobile apps searching device IDs.
• How: searchBST recursively navigates based on comparisons.

---

3.4 Binary HeapsWhat: A complete binary tree where parent nodes are smaller (min-heap) or larger (max-heap) than children.Why: Used in mobile software for priority queues (e.g., scheduling device tasks).How: Implement min-heap insertion.Code Example:

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int size;
} Heap;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(Heap *h, int index) {
    int parent = (index - 1) / 2;
    if (index > 0 && h->items[index] < h->items[parent]) {
        swap(&h->items[index], &h->items[parent]);
        heapifyUp(h, parent);
    }
}

void insertHeap(Heap *h, int data) {
    if (h->size < MAX_SIZE) {
        h->items[h->size] = data;
        heapifyUp(h, h->size++);
    }
}

int main() {
    Heap h = {{0}, 0};
    insertHeap(&h, 10);
    insertHeap(&h, 5);
    printf("Min heap root: %d\n", h.items[0]); // Output: 5
    return 0;
}

Explanation:

• What: Min-heap ensures the smallest element is at the root.
• Why: Useful for prioritizing tasks in mobile apps (e.g., urgent device updates).
• How: insertHeap adds an element and restores heap property (O(log n)).

---

3.5 Graphs - Representation, DFS, BFSWhat: A graph is a set of nodes (vertices) connected by edges. Represented as adjacency lists or matrices. DFS (Depth-First Search) and BFS (Breadth-First Search) traverse graphs.Why: In mobile software, graphs model networks (e.g., device connections).How: Implement BFS using an adjacency list.Code Example:

#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 5

typedef struct Node {
    int vertex;
    struct Node *next;
} Node;

typedef struct {
    Node *adjList[MAX_NODES];
} Graph;

void addEdge(Graph *g, int src, int dest) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = g->adjList[src];
    g->adjList[src] = newNode;
}

void bfs(Graph *g, int start) {
    int visited[MAX_NODES] = {0};
    int queue[MAX_NODES], front = 0, rear = 0;
    queue[rear++] = start;
    visited[start] = 1;
    while (front < rear) {
        int v = queue[front++];
        printf("%d ", v);
        for (Node *current = g->adjList[v]; current; current = current->next) {
            if (!visited[current->vertex]) {
                queue[rear++] = current->vertex;
                visited[current->vertex] = 1;
            }
        }
    }
    printf("\n");
}

int main() {
    Graph g = {{NULL}};
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    bfs(&g, 0); // Output: 0 1 2
    return 0;
}

Explanation:

• What: BFS explores nodes level by level using a queue.
• Why: Useful for finding shortest paths in device networks.
• How: Adjacency list stores edges; BFS uses a queue (O(V + E)).

---

4. Sorting and Searching4.1 Sorting TechniquesWhat: Sorting arranges data in order (e.g., ascending). Techniques include:

• Selection Sort: Repeatedly selects the smallest element (O(n²)).
• Insertion Sort: Builds sorted array incrementally (O(n²)).
• Quick Sort: Uses divide-and-conquer (O(n log n) average).
• Merge Sort: Divides and merges sorted halves (O(n log n)).
• Heap Sort: Uses a heap (O(n log n)).
• Radix Sort: Sorts by digits (O(dn)).

Why: In mobile software, sorting organizes device lists (e.g., by battery level) for efficient display or processing.How: Implement Quick Sort.Code Example:

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22};
    int n = 5;
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]); // Output: 12 22 25 34 64
    }
    printf("\n");
    return 0;
}

Explanation:

• What: Quick Sort selects a pivot and partitions the array.
• Why: Fast (O(n log n)) for sorting device data in mobile apps.
• How: Recursive partitioning sorts the array.

---

4.2 Searching TechniquesWhat: Searching finds an element in a dataset:

• Linear Search: Checks each element (O(n)).
• Binary Search: Works on sorted arrays, dividing search space (O(log n)).
• Hashing: Maps keys to indices for fast lookup (O(1) average).

Why: Critical for mobile apps to quickly find devices or settings.How: Implement Binary Search.Code Example:

#include <stdio.h>

int binarySearch(int arr[], int size, int key) {
    int low = 0, high = size - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) return mid;
        if (arr[mid] < key) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int arr[] = {12, 22, 25, 34, 64};
    int key = 25;
    int result = binarySearch(arr, 5, key);
    printf(result >= 0 ? "Found at index %d\n" : "Not found\n", result);
    return 0;
}

Explanation:

• What: Binary Search divides the sorted array to find the key.
• Why: Efficient (O(log n)) for mobile apps searching sorted device IDs.
• How: Iterative search narrows the range.

---

4.3 HashingWhat: Hashing maps keys to indices using a hash function. Collisions (multiple keys mapping to the same index) are resolved using techniques like linear probing, quadratic probing, double hashing, or open hashing (chaining).Why: Provides O(1) average-case lookup for mobile apps (e.g., device ID lookups).How: Implement hashing with linear probing.Code Example:

#include <stdio.h>
#define TABLE_SIZE 10

typedef struct {
    int data;
    int occupied;
} HashTable;

void initTable(HashTable table[]) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        table[i].occupied = 0;
    }
}

int hashFunction(int key) {
    return key % TABLE_SIZE; // Division method
}

void insert(HashTable table[], int key) {
    int index = hashFunction(key);
    int i = 0;
    while (table[(index + i) % TABLE_SIZE].occupied && i < TABLE_SIZE) {
        i++; // Linear probing
    }
    if (i < TABLE_SIZE) {
        table[(index + i) % TABLE_SIZE].data = key;
        table[(index + i) % TABLE_SIZE].occupied = 1;
    }
}

int search(HashTable table[], int key) {
    int index = hashFunction(key);
    int i = 0;
    while (table[(index + i) % TABLE_SIZE].occupied && i < TABLE_SIZE) {
        if (table[(index + i) % TABLE_SIZE].data == key) {
            return (index + i) % TABLE_SIZE;
        }
        i++;
    }
    return -1;
}

int main() {
    HashTable table[TABLE_SIZE];
    initTable(table);
    insert(table, 15);
    insert(table, 25); // Collision with 15
    int result = search(table, 25);
    printf(result >= 0 ? "Found at index %d\n" : "Not found\n", result);
    return 0;
}

Explanation:

• What: Hash table uses division method; linear probing resolves collisions.
• Why: Fast lookups for mobile apps managing device IDs.
• How: insert and search use linear probing to handle collisions (O(1) average).

---

Teaching Session Plan (90–120 Minutes)

1. Introduction (10–15 minutes):
   • Context: “Data structures are critical for mobile software to manage devices, optimize performance, and save resources.”
   • Objective: “Learn basic data structures, linked lists, trees, graphs, sorting, and searching with C examples.”
   • Relevance: “Used in device management systems for tasks like searching devices or scheduling updates.”
2. Explain Concepts (30–40 minutes):
   • Basic Concepts: Define data structures, abstraction, complexity, and notations with array/stack examples.
   • Linked Lists: Show singly, doubly, circular lists, and memory allocation.
   • Trees/Graphs: Explain binary trees, BST, heaps, and BFS with examples.
   • Sorting/Searching: Cover quick sort, binary search, and hashing.
   • Use diagrams (e.g., tree structure, hash table) to visualize.
3. Live Coding (30–40 minutes):
   • Use a C compiler (e.g., GCC, Code::Blocks).
   • Demonstrate:
     • Stack push/pop (Basic Concepts).
     • Linked list insertion (Linked Lists).
     • BST search (Trees).
     • Quick sort and hashing (Sorting/Searching).
   • Show outputs and explain time complexities.
4. Hands-On Practice (15–20 minutes):
   • Tasks:
     • Implement a queue using a linked list.
     • Add deletion to the BST code.
     • Modify the hash table to use quadratic probing.

---

• 
  .