Proposed Directions

1: Basic Data Structures & Tuples

2: Arrays & Basic Searching

3: Linear Algebra & Matrix Multiplication

4: Elementary Sorting Algorithms

5: Loop Invariants & Search Verification

6: Abstract Data Types

7: Linked Lists

8: Stacks & Queues

9: Tree Data Structures & Traversals

10: Hash Tables & Space-Time Tradeoffs

11: String Matching Algorithms

12: Intermediate & Fast Sorting

13: Object-Oriented Programming Data Abstraction

14: Asymptotic Complexity & Efficiency

15: Core Algorithmic Strategies & Paradigms

16: Advanced Search

17: Recurrence Relations & Intractability

18: Graph Representations & Advanced Graph Algorithms

19: Automata

20: Pushdown Automata & Context-Free Languages

21: Turing Machines & Computability Models

22: Formal Proofs

23: Turing Machine Models of Complexity

24: Advanced & Specialized Algorithms

25: Cryptography & Security Fundamentals

26: Algorithms and Society

Detailed Topics

1. Records/Structs and Tuples

2. Arrays: single and multi-dimensional; Linear and Binary Search

3. Basic Linear Algebra: Matrix Multiplication (Strassen's Matrix Multiplication)

4. Sorting Algorithms: O(n2) Selection, Insertion

5. Invariants (loop, in search algorithms)

6. Abstract Data Types (ADTs) including Bag, Collection, Dictionary, List, and Set properties [SDF/Fundamental Data Structures]

7. Linked Lists: single, doubly linked, and circular

8. Stacks; Queues, Priority Queues, and Deques

9. Trees: Binary, n-ary, Search; Traversals: Depth-First, Breadth-First, Best-First, and Backtracking search; Balanced (2-3, AVL, B, or Red-Black); Heap and Heapsort; Huffman Coding

10. Hash Tables / Maps; Collision resolution: Linear/Quadratic Probing, Chaining, and Rehashing; Space and Time Tradeoffs

11. Strings: String Matching (Boyer-Moore)

12. Sorting Algorithms: O(n log n) Quicksort, Merge, and Heap; O(n) Fast-Sorting: Bucket and Radix; Lexicographical Ordering; Partial Ordering

13. Objects [PL/Object-Oriented Programming]

14. Analysis Framework (Average, Best, and Worst case performance; Empirical and Relative (Order of Growth) Measurements; Input Size and Primitive Operations; Time and Space Efficiency and tradeoffs); Asymptotic complexity analysis (Big O, Little O, Big Omega, and Big Theta; Foundational Complexity/Efficiency classes: Constant, Logarithmic, Linear, Log Linear, Quadratic, Cubic, Exponential, and Factorial); Algorithmic Analysis (using) — [AL / Fundamental Algs and Data Structures]

15. Algorithmic Strategy: Brute-Force/Exhaustive Search, Decrease-and-Conquer, Divide-and-Conquer, Dynamic Programming, Greedy, Iterative, Recursive, Space and Time Tradeoff, Transform-and-Conquer/Reduction, Algorithmic Strategy (example algorithms) — [AL/Fundamental Algorithms and Data Structures]

16. Heuristic & Parallel Strategies

17. Iterative and recursive algorithm analysis (Recurrence Relations, Master Theorem Analysis, Substitution Analysis); Tractability and Intractability (P, NP and NP-C complexity classes: Hamiltonian Circuit, Knapsack, and SAT problems)

18. Graphs [MF/Graphs and Trees]: (un)directed, (a)cyclic, (un)connected, and (un)weighted; Adjacency List and Matrix representations; Graph Algorithms: Breadth-First Search (Connectivity, Shortest-Path), Depth-First Search (Acyclicity, Connectivity, Topological Sort, Transitive Closure), Hamiltonian Circuit, Minimal Spanning Tree (Prim's and Kruskal's algorithms), Shortest-path (Bellman-Ford, Dijkstra's/Uniform-Cost, Floyd-Warshall), Transitive Closure (Warshall's Algorithm)

19. Grammars & Regular Languages

20. Pushdown, Context-Free Grammar/Languages; Pushdown, Context-Free Grammars

21. Turing Machine, Recursively Enumerable (Linear-Bounded, Context-Sensitive); Decidability, Computability, Halting problem, The Church-Turing Thesis; Equivalent Models of Computation (Turing Machine variations, Lambda Calculus, Mu-Recursive Functions)

22. Limits & Space Complexity

23. Turing Machine-Based Models of Complexity (P, NP, and NPC complexity); Space Complexity (NSpace, PSpace, Savitch's Theorem)

24. Consensus Algorithms (e.g. Blockchain); Geometric Algorithms (e.g., Graham Scan for Convex Hull); Linear Programming (e.g., Simplex algorithm); Approximation algorithms (e.g., for Knapsack, Traveling Salesperson); Randomized Algorithms (e.g. MaxCut, Balls and Bins)

25. Cryptography: AES (SHA-256), RSA; Differential Privacy

26. Context-Aware Computing [cross-reference: SEP/Social Context]; Social, Ethical, and Secure Algorithms; Differential Privacy; Algorithmic Fairness [cross-reference AI]

Data: Raw facts, observations, or symbols without interpretation

Representation Technique: Numbers, characters, text, images, audio, video, binary values

Ex: 25, Student, 85

 Identifies individual values, tokens, and symbols

Information: Processed or organized data that has meaning in a particular context

Representation Technique: Tables, records, graphs, reports, databases, JSON/XML

Ex: Student scored 85 marks

Establishes relationships and context among data elements

Knowledge: Information combined with rules, experience, relationships, and interpretation

Representation Technique: Knowledge graphs, ontologies, rules, semantic networks, concept maps

Ex: 85 marks indicate good academic performance

 Identifies concepts, relationships, entities, and rules

Wisdom: Application of knowledge and experience to make appropriate decisions

Representation Technique: Decision models, recommendations, policies, expert systems

Ex: The student should be encouraged to participate in advanced courses

DATA

  ↓

( Processing + Context )

  ↓

INFORMATION

  ↓

(Interpretation + Relationships + Rules )

  ↓

KNOWLEDGE

  ↓

(Experience + Reasoning + Decision Making )

  ↓

WISDOM

Data Processing transforms raw facts into an organized or usable form.

Typical operations:

• Data collection

• Data entry

• Data validation

• Data cleaning

• Sorting

• Searching

• Classification

• Filtering

• Calculation

• Aggregation

• Storage

Example:

Raw Data: 45, 67, 89, 72, 55

        ↓ Data Processing

Sorted Data: 45, 55, 67, 72, 89     Average: 65.6

Information Processing: Information processing gives context and meaning to processed data.

Typical operations:

• Summarization

• Comparison

• Correlation

• Interpretation

• Categorization

• Visualization

• Report generation

• Pattern identification

Example:

Average Student Marks = 65.6 , Class Average = 58

        ↓ Information Processing

Student performance is above the class average.

Knowledge Processing: Knowledge processing uses information together with rules, relationships, concepts, and reasoning to derive new knowledge or make decisions.

Typical operations:

• Knowledge representation

• Semantic analysis

• Rule application

• Logical reasoning

• Inference

• Classification

• Prediction

• Recommendation

• Decision-making

• Knowledge discovery

Example:

Information: Student average = 65.6. and Class average = 58

        +

Knowledge Rule:

IF student performance > class average

THEN performance = "Above Average"

        ↓ Knowledge Processing

Inference: Student performance = Above Average

RAW DATA

   ↓

(DATA PROCESSING)

   ↓

PROCESSED DATA

   ↓

(INFORMATION PROCESSING)

   ↓

MEANINGFUL INFORMATION

   ↓

(KNOWLEDGE PROCESSING)

   ↓

KNOWLEDGE & INFERENCE

   ↓

(DECISION / RECOMMENDATION)

In Semantic Analysis: This distinction is particularly important in Natural Language Processing (NLP):

Data Processing→ text cleaning, tokenization, normalization, stemming

Information Processing→ extracting entities, keywords, relationships, and facts

Knowledge Processing→ understanding meaning, semantic relationships, reasoning, inference, and answering questions

For example:

"Ravi scored 85 marks in Data Structures."

• Data: Ravi, 85, Data Structures

• Information: Ravi scored 85 marks in Data Structures.

• Knowledge: Ravi has demonstrated strong performance in Data Structures, assuming an appropriate performance rule or benchmark.

• Inference: Ravi may be suitable for an advanced Data Structures activity.

A data structure is an organization of data items in a particular manner, together with a set of valid operations applied to this organization.

A data structure is a specialized, systematic format for organizing, storing, and managing data in computer memory so that operations can be executed efficiently.

In literature: 

Data structure is formalized by Niklaus Wirth : Algorithms + Data Structures = Programs

 Thomas H. Cormen et al. (Introduction to Algorithms): A data structure serves as the concrete physical implementation of an Abstract Data Type (ADT)

It is described by the following three core components:

• Data Values: The set of primitive or complex values stored.

• Relationships: The logical arrangement (linear, hierarchical, or network) connecting data elements.

• Operations: The collection of algorithms permitted to manipulate and retrieve stored data.

Operations on Data Structures

• Access / Search-Locates a specific element or value within memory based on a key or index.

• Insertion-Adds a new element into a designated location within the structure.

• Deletion-Removes an existing element and reorganizes remaining memory references.

• Traversal-Accesses and processes every element in the structure sequentially or recursively exactly once.

• Sorting-Rearranges stored items into a specific order (e.g., numerical ascending or alphabetical).

• Merging-Combines elements from two separate structures into a single structure.

• Update-Replaces an existing element's value at a target reference or index.

Types of Data Structures

Primitive vs. Non-Primitive

• Primitive Data Structures: Basic building blocks provided directly by programming languages (e.g., Integer, Float, Character, Boolean, Pointer).

• Non-Primitive Data Structures: Complex structures built from primitive types to aggregate multiple values (e.g., Arrays, Linked Lists, Trees).

Linear vs. Non-Linear

• Linear Data Structures: Elements are linked sequentially in a single sequence, where each element connects directly to its predecessor and successor.

Array: A fixed-size, contiguous block of memory storing elements accessible via index.

Linked List: A sequence of nodes stored in non-contiguous memory connected via pointers (Singly, Doubly, or Circular).

Stack- A Last-In, First-Out (LIFO) structure where insertions (push) and deletions (pop) occur at one end.

Queue- A First-In, First-Out (FIFO) structure where items enter at the rear (enqueue) and exit at the front (dequeue).

• Non-Linear Data Structures: Elements are arranged hierarchically or as a complex network rather than sequentially.

Tree: A hierarchical node-based structure consisting of a root and child subtrees (e.g., Binary Search Tree, AVL Tree, B-Tree).

Graph: A non-linear network of vertices (nodes) linked by edges, representing arbitrary relationships.

Hash Table: An associative dictionary mapping key-value pairs using a hash function for $O(1)$ average lookup time.

Heap- A specialized tree maintaining min or max heap properties for priority queue operations.

Static vs. Dynamic

• Static: Fixed memory size determined at compile time (e.g., standard Arrays).

• Dynamic: Variable memory capacity that grows or shrinks dynamically at runtime via heap allocation (e.g., Dynamic Arrays, Linked Lists).

Stack

A Stack is a linear data structure in which elements are inserted and deleted from one end only, called the TOP. It follows the LIFO (Last In, First Out) principle.
Example: Stack of plates.

Possible Operations:

• Push: Insert an element onto the TOP of the stack.

• Pop: Remove an element from the TOP of the stack.

• Peek/Top: View the TOP element without removing it.

• isEmpty: Check whether the stack is empty.

• isFull: Check whether the stack is full in an array-based implementation.

• Size: Find the number of elements in the stack.

• Display/Traverse: View all elements of the stack.

• Search: Find a specified element in the stack.

• Clear: Remove all elements from the stack.

#define MAX 100

typedef struct {

    int data[MAX];

    int top;

} Stack;

void push(Stack *s, int value);

int pop(Stack *s);

int peek(const Stack *s);

int isEmpty(const Stack *s);

int isFull(const Stack *s);

void display(const Stack *s);

MultiStack

(n=2)

Two stacks can be implemented efficiently in one array by growing the two stacks from opposite ends of the array.

Two Stacks in a Single Array

Suppose the array has size MAX = 10.

• Stack 1 grows from left to right.

• Stack 2 grows from right to left.

• Both stacks share the unused space in the middle.

• Overflow occurs when top1 + 1 == top2.

Array: with 2 stacks

+----+----+----+----+----+----+----+----+----+----+

| S1 | S1 | S1 |    |    |    |    | S2 | S2 | S2 |

+----+----+----+----+----+----+----+----+----+----+

  ↑                         ↑

 top1                      top2

Initialization

#define MAX 10

int stack[MAX];

int top1 = -1;       // Stack 1

int top2 = MAX;      // Stack 2

PUSH Operation

______________________________

Push into Stack 1

void push1(int value)

{

    if (top1 + 1 == top2)

        printf("Stack Overflow");

    else

        stack[++top1] = value;

}

Push into Stack 2

void push2(int value)

{

    if (top1 + 1 == top2)

        printf("Stack Overflow");

    else

        stack[--top2] = value;

}

POP Operation

______________________________

Pop from Stack 1

int pop1()

{

    if (top1 == -1)

        return -1;

    return stack[top1--];

}

Pop from Stack 2

int pop2()

{

    if (top2 == MAX)

        return -1;

    return stack[top2++];

}

Example

If we perform:

push1(10)

push1(20)

push1(30)

push2(90)

push2(80)

push2(70)

The array becomes:

Index:  0    1    2    3    4    5    6    7    8    9

       +----+----+----+----+----+----+----+----+----+----+

       | 10 | 20 | 30 |    |    |    |    | 70 | 80 | 90 |

       +----+----+----+----+----+----+----+----+----+----+

                   ↑                   ↑

                  top1                top2

Main advantage: The unused space of one stack can be used by the other stack. This reduces wastage compared with allocating two separate fixed-size arrays.

Viva Questions

1. Why are two stacks implemented from opposite ends?

2. What is the initial value of top1?

3. What is the initial value of top2?

4. What is the condition for overflow?

5. How does push1() differ from push2()?

6. How does pop1() differ from pop2()?

7. What happens when the two stacks meet?

8. What is the advantage of implementing two stacks in one array?

9. What is the time complexity of push and pop operations?

10. Can the two stacks have different numbers of elements? Why?

Queue

A Queue is a linear data structure in which elements are inserted at the REAR and deleted from the FRONT. It follows the FIFO (First In, First Out) principle.
Example: People standing in a ticket queue.

Possible Operations:

• Enqueue: Insert an element at the REAR of the queue.

• Dequeue: Remove an element from the FRONT of the queue.

• Front/Peek: View the first element without removing it.

• Rear: View the last element in the queue.

• isEmpty: Check whether the queue is empty.

• isFull: Check whether the queue is full in an array-based implementation.

• Size: Find the number of elements in the queue.

• Display/Traverse: View all elements of the queue.

• Search: Find a specified element.

• Clear: Remove all elements from the queue.

#define MAX 100

typedef struct {

    int data[MAX];

    int front;

    int rear;

} Queue;

void enqueue(Queue *q, int value);

int dequeue(Queue *q);

int frontElement(const Queue *q);

int rearElement(const Queue *q);

int isEmptyQueue(const Queue *q);

int isFullQueue(const Queue *q);

void displayQueue(const Queue *q);

Queue Function Headers : A circular queue connects the last position back to the first position.

void initCircularQueue(Queue *q);

void enqueueCircular(Queue *q, int value);

int dequeueCircular(Queue *q);

int frontCircular(const Queue *q);

int rearCircular(const Queue *q);

int isEmptyCircular(const Queue *q);

int isFullCircular(const Queue *q);

void displayCircular(const Queue *q);

Fixed Front Design of Queue

In a Fixed Front Queue, the front of the queue is permanently anchored at index 0 (front = 0),

 while the rear pointer dynamically tracks the total element count (or the next available slot).

Because the front index never moves, removing an item requires shifting every remaining element left by one position to fill index 0.

Core Operations of fixed front queue design & Complexity

_________________________________________________________

Enqueue( &q, val)   O(1)  -Check overflow (rear == Capacity). Place val at arr[rear], then increment rear.

Dequeue(&q)       O(N)      - Check underflow (rear == 0). Save arr[0], shift all elements from index 1 to rear - 1 left by 1 slot, then decrement rear.

Peek(q)   O(1) - Return arr[0] directly without modifying rear.

IsEmpty(q)  O(1)  -Evaluate if rear == 0.

IsFull(q)    O(1)  -Evaluate if rear == Capacity.

C++ Implementation

#include <iostream>

#define CAPACITY 5

class FixedFrontQueue {

private:

    int arr[CAPACITY];

    int rear; // Tracks element count and next available insertion index

public:

    FixedFrontQueue() : rear(0) {}

    bool isFull()  { return rear == CAPACITY; }

    bool isEmpty() { return rear == 0; }

    void enqueue(int val) {

        if (isFull()) {

            std::cout << "Queue Overflow\n";

            return;

        }

        arr[rear++] = val; // Store at current rear, then increment

    }

    int dequeue() {

        if (isEmpty()) {

            std::cout << "Queue Underflow\n";

            return -1;

        }

        int frontValue = arr[0]; // Front is always fixed at index 0

        // Shift remaining elements left by 1 index

        for (int i = 1; i < rear; i++) {

            arr[i - 1] = arr[i];

        }

        rear--; 

        return frontValue;

    }

    int peek() {

        if (isEmpty()) return -1;

        return arr[0];

    }

};

Dry Run Execution

State 0 (Empty): arr = [ _ , _ , _ ], rear = 0

Enqueue(10), Enqueue(20), Enqueue(30):

arr = [ 10, 20, 30 ], rear = 3

Dequeue():

Output = 10 (at arr[0])

Shift elements: arr[0] = arr[1] (20), arr[1] = arr[2] (30)

Decrement rear to 2

Updated array: arr = [ 20, 30, _ ], rear = 2

Key Design Trade-Offs

1. No Wasted Capacity

 Unlike basic moving-front linear queues, this design prevents false overflows without needing modular index calculation. Memory is always tightly packed at the beginning of the array.

2. Performance Penalty

 Dequeuing requires $O(N) data movement due to continuous memory shifting. Standard circular queues achieve $O(1)$ dequeue performance by allowing front to advance instead, making circular queues preferred for high-volume applications.

Floating front design (Circular Queue)

#include <iostream>

class FloatingQueueWithNextPointers {

private:

    static const int N = 5; // Memory array size N (Max capacity = N - 1 = 4)

    int arr[N];

    int front;

    int rear;

    // Helper functions to pre-compute wrapped indices

    int getNextRear() const {

        return (rear + 1) % N;

    }

    int getNextFront() const {

        return (front + 1) % N;

    }

public:

    FloatingQueueWithNextPointers() : front(0), rear(0) {}

    bool isEmpty() const {

        return front == rear;

    }

    bool isFull() const {

        return getNextRear() == front; // Prevents rear from overrunning front

    }

    void enqueue(int val) {

        int nextrear = getNextRear();

        if (nextrear == front) { // Overflow check using explicit nextrear

            std::cout << "Queue Overflow\n";

            return;

        }

        arr[rear] = val;

        rear = nextrear; // Transition to pre-computed index

    }

    int dequeue() {

        if (isEmpty()) {

            std::cout << "Queue Underflow\n";

            return -1;

        }

        int val = arr[front];

        int nextfront = getNextFront();

        front = nextfront; // Transition to pre-computed index

        return val;

    }

    int peek() const {

        if (isEmpty()) return -1;

        return arr[front];

    }

};

Floating-Front Circular Queue — Reserved Slot

Let the circular array have N locations, with front and rear as floating indices.

Define:

NF=(front+1) mod NNF=(front+1)\bmod N NR=(rear+1) mod NNR=(rear+1)\bmod N

The slot immediately after rear is kept as the reserved/free slot. Therefore, the queue can contain at most N − 1 elements.

Condition

Next Front (NF)  NF = (front + 1) % N

Next Rear (NR) NR = (rear + 1) % N

Empty Queue  front == rear

Full Queue  NR == front

Reserved Slot Slot at NR is kept free before insertion

Capacity N − 1 elements

Enqueue 

Before inserting, calculate:

NR=(rear+1) mod N

If  (NR=front )

then the queue is FULL.

Otherwise:

rear = NR

Q[rear] = item

Thus, in this convention, the rear is advanced first, and the item is stored at the new rear position.

Dequeue

Calculate:

NF=(front+1) mod N

If (front=rear )

the queue is EMPTY.

Otherwise:

front = NF

item = Q[front]

So the front is also advanced first, and the item is then read.

Example: N = 6

Initially:

       0   1   2   3   4   5

       ┌───┬───┬───┬───┬───┬───┐

       │   │   │   │   │   │   │

       └───┴───┴───┴───┴───┴───┘

        ↑

      front

      rear

front = 0

rear  = 0

NF = (0 + 1) % 6 = 1

NR = (0 + 1) % 6 = 1

Initially front == rear, so the queue is empty.

After inserting 10:

NR = (0 + 1) % 6 = 1

rear = 1

Q[1] = 10

After inserting 20:

NR = (1 + 1) % 6 = 2

rear = 2

Q[2] = 20

The queue is conceptually:

       0       1       2       3       4       5

      ┌───────┬───────┬───────┬───────┬───────┬───────┐

      │       │  10   │  20   │       │       │       │

      └───────┴───────┴───────┴───────┴───────┴───────┘

        ↑                       ↑

      front                   rear

Here, front itself does not point to the first element. The first element is at:

NF=(front+1) mod N

This is the key idea behind the floating-front representation.

Most important distinction

There are two common circular-queue conventions:

Conventional front:

front → first element

rear  → next insertion position

Floating-front / reserved-slot convention:

front → position BEFORE first element

rear  → last element

Therefore:

NF=(front+1) mod N

gives the first element, while

NR=(rear+1) mod N

gives the reserved/free slot after the rear.

And the two key conditions are:

Empty  ⟺  front=rear\boxed{Empty \iff front=rear} Full  ⟺  NR=front\boxed{Full \iff NR=front}

This convention is particularly useful because empty and full states remain distinguishable without maintaining a separate count variable.

Priority Queue

A Priority Queue is a queue in which each element is associated with a priority, and elements are processed according to priority.

typedef struct {

    PriorityElement data[MAX];

    int size;

} PriorityQueue;

Function Headers

void initPriorityQueue(PriorityQueue *pq);

void insertPriority(PriorityQueue *pq, int value,  int priority);

int deletePriority(PriorityQueue *pq);

int peekPriority(const PriorityQueue *pq);

int isEmptyPriority(const PriorityQueue *pq);

int isFullPriority(const PriorityQueue *pq);

void displayPriority(const PriorityQueue *pq);

Deque : allows insertion and deletion from both ends.

void initDeque(Queue *dq);

void insertFront(Queue *dq, int value);

void insertRear(Queue *dq, int value);

int deleteFront(Queue *dq);

int deleteRear(Queue *dq);

int getFront(const Queue *dq);

int getRear(const Queue *dq);

int isEmptyDeque(const Queue *dq);

int isFullDeque(const Queue *dq);

void displayDeque(const Queue *dq);

Sparse Matrix

A Sparse Matrix is a matrix in which most elements are zero and only a small number of elements are non-zero. Special representations are used to save memory and processing time.

Example:

0  0  5

0  0  0

7  0  0

 can be represented as 

Row   Column   Value

 0      2        5

 2      0        7

A complete triplet representation generally also stores the matrix dimensions and number of non-zero elements.

#define MAX_TERMS 100

typedef struct {

    int row;

    int col;

    int value;

} Term;

typedef struct {

    int rows;

    int cols;

    int terms;

    Term data[MAX_TERMS];

} SparseMatrix;

Possible Operations:

• Create: Create and store a sparse matrix.

• Represent: Represent the matrix using triplet, tuple, or other compact forms.

• Insert: Add a non-zero element at a specified position.

• Delete: Remove a non-zero element or make an element zero.

• Update: Modify the value of an existing element.

• Access/Search: Find the value at a specified row and column.

• Display: Display the sparse matrix in normal or compact form.

• Transpose: Convert rows into columns and columns into rows.

• Fast Transpose: Perform an efficient transpose using compact representation.

• Addition: Add two sparse matrices.

• Subtraction: Subtract one sparse matrix from another.

• Multiplication: Multiply sparse matrices where dimensions are compatible.

• Count Non-Zero Elements: Determine the number of non-zero elements.

• Convert Representation: Convert between normal matrix and sparse/compact representation.

Operation

• Initialize void initSparse(SparseMatrix *s);

• Create void createSparse(SparseMatrix *s);

• Insert void insertSparse(SparseMatrix *s, int row, int col, int value);

• Delete void deleteSparse(SparseMatrix *s, int row, int col);

• Update void updateSparse(SparseMatrix *s, int row, int col, int value);

• Search int searchSparse(const SparseMatrix *s, int row, int col);

• Access int getSparse(const SparseMatrix *s, int row, int col);

• Display void displaySparse(const SparseMatrix *s);

• Transpose void transposeSparse(const SparseMatrix *s, SparseMatrix *t);

• Fast Transpose void fastTranspose(const SparseMatrix *s, SparseMatrix *t);

• Addition int addSparse(const SparseMatrix *a, const SparseMatrix *b, SparseMatrix *c);

• Subtraction int subtractSparse(const SparseMatrix *a, const SparseMatrix *b, SparseMatrix *c);

• Multiplication int multiplySparse(const SparseMatrix *a, const SparseMatrix *b, SparseMatrix *c);

• Count Non-Zero int countNonZero(const SparseMatrix *s);

• Clear void clearSparse(SparseMatrix *s);

List

A List is a linear data structure in which elements are arranged in a sequential order. Lists may be implemented using arrays or linked nodes.

Example:

10 → 20 → 30 → 40

General List Operations:

• Create: Create a new list.

• Insert: Add an element at the beginning, end, or a specified position.

• Delete: Remove an element from the beginning, end, or a specified position.

• Traverse: Visit and process all elements.

• Search: Find a specified element.

• Access/Retrieve: Obtain an element at a specified position.

• Update/Replace: Modify an existing element.

• Size/Length: Find the number of elements.

• isEmpty: Check whether the list is empty.

• Sort: Arrange elements in ascending or descending order.

• Reverse: Reverse the order of elements.

• Merge: Combine two lists.

• Concatenate: Join one list after another.

• Clear: Remove all elements from the list.

• Copy: Create a duplicate of a list.

Array as List

An Array List stores list elements in contiguous memory locations.

Operations:

• Create

• Insert

• Delete

• Search

• Traverse

• Access by index

• Update

• Sort

• Reverse

• Merge

• Concatenate

• Find size

Unordered List

An Unordered List is a list in which elements are not arranged according to any specific order or sorting criterion. Elements can be stored in the order in which they are inserted.

Example:

30 → 10 → 40 → 20

Possible Operations:

• Insert at beginning

• Insert at end

• Insert at a specified position

• Delete an element

• Search for an element

• Traverse the list

• Access an element

• Update an element

• Find size

• Reverse the list

• Sort the list when required

• Merge or concatenate lists

• Clear the list

Ordered List

An Ordered List is a list in which elements are maintained in a specific order, usually ascending or descending according to their values or a defined key.

Example:

10 → 20 → 30 → 40

Possible Operations:

• Ordered Insert: Insert an element at its correct sorted position.

• Delete: Remove an element while maintaining the order.

• Search: Search for an element; efficient searching may be possible depending on implementation.

• Traverse: Visit elements in their sorted order.

• Access: Retrieve an element at a specified position.

• Update: Modify an element and restore the required order if necessary.

• Find Minimum: Retrieve the smallest element.

• Find Maximum: Retrieve the largest element.

• Find Size: Determine the number of elements.

• Merge: Combine two ordered lists while maintaining the order.

• Clear: Remove all elements.

Note: In an Ordered List, every insertion, deletion, or update should preserve the defined ordering criterion.

void initList(ArrayList *list);

int isEmptyList(const ArrayList *list);

int isFullList(const ArrayList *list);

int listSize(const ArrayList *list);

void insertBeginning(ArrayList *list, int value);

void insertEnd(ArrayList *list, int value);

void insertAtPosition(ArrayList *list, int position, int value);

int deleteBeginning(ArrayList *list);

int deleteEnd(ArrayList *list);

int deleteAtPosition(ArrayList *list, int position);

int searchList(const ArrayList *list, int key);

int getElement(const ArrayList *list, int position);

void updateElement(ArrayList *list, int position, int value);

void displayList(const ArrayList *list);

void reverseList(ArrayList *list);

void sortList(ArrayList *list);

void clearList(ArrayList *list);

An Unordered List contains elements that are not maintained according to any particular sorting order.

Example:

30 → 10 → 40 → 20

Operations

void insertUnordered(ArrayList *list, int value);

int deleteUnordered(ArrayList *list, int value);

int searchUnordered(const ArrayList *list, int key);

void updateUnordered(ArrayList *list, int position,int value);

void displayUnordered(const ArrayList *list);

void reverseUnordered(ArrayList *list);

void sortUnordered(ArrayList *list);

void mergeUnordered(const ArrayList *a, const ArrayList *b, ArrayList *result);

int listSize(const ArrayList *list);

void clearUnordered(ArrayList *list);

An Ordered List maintains its elements according to a specified order, generally ascending or descending.

Example: 10 → 20 → 30 → 40

Operations

void insertOrdered(ArrayList *list, int value);

int deleteOrdered(ArrayList *list, int value);

int searchOrdered(const ArrayList *list, int key);

void updateOrdered(ArrayList *list,int position, int value);

int findMinimum(const ArrayList *list);

int findMaximum(const ArrayList *list);

void displayOrdered(const ArrayList *list);

void mergeOrdered(const ArrayList *a, const ArrayList *b, ArrayList *result);

void clearOrdered(ArrayList *list);

Special Operation: Ordered Insertion

Unlike an unordered list: insertOrdered(&list, 25);

The function automatically determines the appropriate position so that the list remains ordered.