Data Structures, Algorithms, and Abstract Data Types (ADTs)

Core Concepts: Data Structures and Algorithms

1. What is a Data Structure?

A data structure is a way of organizing and storing data to enable efficient access and modification. It defines how data is laid out in memory and how operations (insertion, deletion, search) are performed.

Types of Data Structures

mindmap
  root((Data Structures))
    Arrays
    Linked Lists
    Stacks
    Queues
    Trees
    Graphs
    Hash Tables
    Advanced (Heaps, AVL Trees, Tries)

Why Use Data Structures?

• Efficiency: Optimize time and space complexity.
• Abstraction: Hide implementation details (e.g., how a stack is stored).
• Modularity: Reuse code for different problems.

2. What is an Algorithm?

An algorithm is a finite sequence of well-defined steps to solve a problem or perform a computation. Key properties:

• Finiteness: Must terminate after a finite number of steps.
• Definiteness: Each step must be unambiguous.
• Input: Takes zero or more inputs.
• Output: Produces at least one result.

Example: Linear Search Algorithm

flowchart TD
    A["Start"] --> B["Input: Array A[n], Target x"]
    B --> C["Set i = 0"]
    C --> D["While i < n"]
    D --> E["If A[i] == x"]
    E --> F["Return i"]
    E --> G["Increment i"]
    G --> D
    D --> H["Return -1 (Not Found)"]

Code Example (Python)

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

Trace Example

In the Real World

1. eSewa (Nepal):

   • Uses hash tables to store user credentials (email → password) for O(1) login verification.
   • Example: When you log in, eSewa checks your email in a hash table to retrieve your password instantly.

2. Pathao (Ride-Hailing App):

   • Uses priority queues to assign the nearest available driver to a rider.
   • Example: When you request a ride, Pathao’s algorithm picks the driver closest to you (highest priority) from a queue of drivers.

3. NTC (Nepal Telecom):

   • Uses graphs to model network topology for efficient routing of calls/data.
   • Example: When you call from Kathmandu to Pokhara, NTC’s algorithm finds the shortest path (lowest latency) using Dijkstra’s algorithm.

4. Khalti (Digital Wallet):

   • Uses binary search trees (BSTs) to maintain transaction records in sorted order for quick fraud detection.
   • Example: If a transaction amount exceeds ₹50,000, Khalti’s BST quickly flags it for review.

5. Daraz (E-Commerce):

   • Uses queues to manage order processing (FIFO: First-In-First-Out).
   • Example: Your order #12345 is placed in a queue and processed before order #12346.

3. Abstract Data Type (ADT)

An ADT defines a logical model of data without specifying implementation details. Examples:

• Stack (LIFO): Last-In-First-Out (e.g., undo operations in MS Word).
• Queue (FIFO): First-In-First-Out (e.g., printer job scheduling).
• List: Ordered collection (e.g., shopping cart in Daraz).

ADT vs. Data Structure

4. Time Complexity (Preview)

While fully covered in Unit 2, this unit introduces the idea:

• Big-O Notation: Describes how runtime grows with input size (e.g., O(n) for linear search, O(log n) for binary search).
• Example: Searching in an unsorted array is O(n), but in a sorted array (binary search), it’s O(log n).

Exam Tip

1. Define Clearly:

   • For ADTs, always state operations (e.g., "A stack supports push, pop, and peek").
   • For data structures, mention storage method (e.g., "An array is a contiguous memory block").

2. Draw Diagrams:

   • Past exam questions often ask to construct data structures (e.g., AVL trees, BSTs). Practice drawing step-by-step insertions/deletions.

3. Compare and Contrast:

   • Questions may ask to differentiate between similar structures (e.g., stack vs. queue, array vs. linked list).

4. Real-World Links:

   • Connect concepts to Nepali apps/companies (e.g., "Khalti uses BSTs for fraud detection").
   • Example answer for "Why is Huffman coding used?":

     "Huffman coding is used in WhatsApp to compress messages before sending, reducing data usage. It assigns shorter binary codes to frequent characters (e.g., space = 0, 'e' = 10), saving bandwidth."

5. Algorithm Steps:

   • For questions like "Write an algorithm to find factorial using recursion," use:
     • Pseudocode (clear steps).
     • Trace table (show variable changes).
     • Base case (e.g., factorial(0) = 1).

Practice Questions (TU-Style)

1. Define an AVL tree and construct one from the data: 14, 16, 22, 19, 15, 12, 21.
   • Hint: After each insertion, check balance factor (BF) and rotate if BF = ±2.
   • Visual Trace:

2. Explain Abstract Data Type with an example.

   • Answer:

     An ADT is a logical model of data. Example: Queue (ADT) defines operations like enqueue() and dequeue(), but doesn’t specify if it’s implemented using an array or linked list. Real-world use: NTC’s call routing system uses a queue to manage incoming calls (FIFO: first call gets connected first).

3. List two sorting algorithms and compare their time complexity.

   • Answer:

     Algorithm	Time Complexity (Avg)	Use Case
     Quick Sort	O(n log n)	Large datasets (e.g., sorting NEPSE stock prices)
     Bubble Sort	O(n²)	Small or nearly sorted data

Key Formulas to Remember

1. Factorial (Recursion): $$n!=\{\begin{array}{ll}1& \text{if }n=0\\ n\times (n-1)!& \text{otherwise}\end{array}$$
2. Binary Search Time Complexity: $O(\log n)$ (halves search space each step).

Common Mistakes to Avoid

• Confusing ADT and Data Structure: Don’t say "array is an ADT" (it’s a data structure; "list" is the ADT).
• Incorrect Rotations in AVL Trees: Always check left-left (LL), left-right (LR), right-right (RR), and right-left (RL) cases.
• Ignoring Edge Cases: For algorithms, test with:
  • Empty input (e.g., linear_search([], 5) should return -1).
  • Single-element input (e.g., factorial(1) = 1).