Data Structures & Algorithms: Core Concepts, Definitions & Applications

What Are Data Structures?

Data structures are organized ways of storing and accessing data in a computer’s memory. They determine how efficiently data can be inserted, deleted, searched, or traversed.

Types of Data Structures

Data structures are broadly classified into two categories:

1. Primitive Data Structures

These are basic data types provided by programming languages:

• Integer: Stores whole numbers (e.g., int age = 25;).
• Float/Double: Stores decimal numbers (e.g., float salary = 12000.50;).
• Character: Stores single characters (e.g., char grade = 'A';).
• Boolean: Stores true or false (e.g., bool isLoggedIn = true;).

2. Non-Primitive (Abstract) Data Structures

These are complex structures built using primitive types:

• Linear: Elements follow a sequence (e.g., arrays, linked lists, stacks, queues).
• Non-linear: Elements are not in a sequence (e.g., trees, graphs).
• File Structures: Used for external storage (e.g., indexed files, sequential files).

What Are Algorithms?

An algorithm is a step-by-step procedure to solve a problem or perform a computation. Key characteristics:

• Finiteness: Must terminate after a finite number of steps.
• Definiteness: Each step must be precisely defined.
• Input: Takes zero or more inputs.
• Output: Produces at least one output.
• Effectiveness: Must be executable by a machine.

Example: Algorithm to Add Two Numbers

flowchart TD
    A["Start"] --> B["Input num1, num2"]
    B --> C["sum = num1 + num2"]
    C --> D["Output sum"]
    D --> E["End"]

Code Example (Pseudocode):

def add_numbers(a, b):
    sum = a + b
    return sum

Trace Table:

Why Are Data Structures and Algorithms Important?

Applications in Real-World Systems

1. eSewa (Nepal)

• Data Structure Used: Hash Tables
• How? eSewa stores user credentials (username → password) in a hash table for O(1) lookup time, ensuring fast login verification.
• Example: When you log in, eSewa hashes your password and checks it against stored hashes in milliseconds.

2. Pathao (Ride-Hailing App)

• Data Structure Used: Priority Queue (Min-Heap)
• How? Pathao uses a priority queue to assign the nearest available driver to a rider’s request. The driver with the smallest distance (highest priority) is selected first.
• Example: If Driver A is 2 km away and Driver B is 5 km away, Driver A gets the ride first.

3. NTC (Nepal Telecommunications Corporation)

• Data Structure Used: Graphs
• How? NTC uses graph algorithms (e.g., Dijkstra’s) to optimize fiber-optic cable routing between cities, minimizing costs and latency.
• Example: If NTC needs to connect Kathmandu, Pokhara, and Chitwan, it calculates the shortest path using graph theory.

4. Khalti (Digital Wallet)

• Data Structure Used: Linked Lists (for Transaction History)
• How? Khalti stores transaction records in a doubly linked list for efficient traversal (forward/backward) when users check their history.
• Example: When you view your last 10 transactions, Khalti retrieves them in O(n) time without loading the entire database.

5. Daraz (E-Commerce)

• Data Structure Used: Binary Search Trees (BST) for Product Search
• How? Daraz uses BSTs to organize products by price or category, enabling O(log n) search time for faster filtering.
• Example: If you search for products priced between ₹500 and ₹1000, Daraz quickly narrows down the range using BST properties.

6. NEPSE (Nepal Stock Exchange)

• Data Structure Used: Priority Queue (Max-Heap for Stock Prices)
• How? NEPSE uses a max-heap to track the highest bid prices in real-time, ensuring fair and efficient trading.
• Example: If multiple buyers bid for a stock, the highest bid is executed first using heap properties.

Classification of Data Structures

Data structures can be classified based on their organization and operations:

Classification of Algorithms

Algorithms can be categorized based on their problem-solving approach:

Time and Space Complexity (Preview)

While fully covered in Unit 2, a brief introduction here helps connect algorithms to efficiency:

• Time Complexity: Measures how runtime grows with input size (e.g., O(n), O(log n)).
• Space Complexity: Measures memory usage (e.g., O(1), O(n)).

Example: Linear Search vs. Binary Search

Common Operations on Data Structures

Example: Stack Operations (LIFO Principle)

A stack follows Last-In-First-Out (LIFO). Common operations:

1. Push: Add an element to the top.
2. Pop: Remove the top element.
3. Peek/Top: View the top element without removal.
4. isEmpty: Check if the stack is empty.

Example: Expression Evaluation (Postfix Notation)

Trace Example: Evaluate 3 4 + 2 *

Final Result: 14

Example: Queue Operations (FIFO Principle)

A queue follows First-In-First-Out (FIFO). Common operations:

1. Enqueue: Add an element to the rear.
2. Dequeue: Remove the front element.
3. Front/Peek: View the front element.
4. isEmpty: Check if the queue is empty.

Real-World Example: Printer Queue (Nepal University Exam Hall)

• Scenario: Students submit print jobs for their exam answer sheets.
• Queue Operations:
  • Enqueue: Each print job is added to the rear of the queue.
  • Dequeue: The printer processes the front job first (FIFO).
  • Problem: If a student’s job is at the rear, they must wait for all prior jobs to complete.

Trace Example: Bank Customer Queue

Exam Tip

1. Define Clearly: Always define data structures (e.g., "An array is a contiguous memory allocation for homogeneous data") and algorithms (e.g., "A step-by-step method to solve a problem").
2. Draw Diagrams: For every data structure (stack, queue, tree), show the state after each operation (e.g., insertion, deletion).
3. Compare Algorithms: In exams, you may be asked to compare time/space complexity of two algorithms (e.g., Linear Search vs. Binary Search).
4. Real-World Links: Connect concepts to Nepali apps/companies (e.g., "Khalti uses linked lists for transaction history").
5. Pseudocode + Trace Tables: Always provide pseudocode for algorithms and trace tables to show step-by-step execution.
6. Common Pitfalls:
   • Confusing stack (LIFO) with queue (FIFO).
   • Forgetting to update pointers in linked lists during deletion.
   • Misapplying recursive vs. iterative approaches.

Key Formula to Remember:

• Time Complexity of Linear Search: $O(n)$
• Time Complexity of Binary Search: $O(\log n)$
• Space Complexity of a Stack: $O(n)$ (where $n$ is the number of elements)