Data Structures & Algorithms: Core Concepts, Definitions & Analysis

TAKEAWAYS:

• Data structures are memory layouts (arrays, trees, graphs) that optimize access, insertion, and deletion operations.
• Algorithms are logical procedures (searching, sorting, traversing) designed to solve problems efficiently.
• Time complexity (Big-O) measures how runtime grows with input size, while space complexity measures memory usage.
• Trade-offs exist between time and space efficiency (e.g., binary search vs. linear search).
• Abstraction lets us design high-level solutions without worrying about low-level implementation details.
• Real-world systems (e.g., eSewa’s transaction queues, Daraz’s search algorithms) rely on these concepts for performance.

1. What Are Data Structures?

Data structures are organized ways to store and manage data in a computer’s memory. They determine:

• How data is physically stored (contiguous vs. linked).
• How operations (insertion, deletion, search) are performed.
• The trade-offs between time and space efficiency.

Types of Data Structures

mindmap
  root((Data Structures))
    Arrays
    Linked Lists
    Stacks
    Queues
    Trees
      Binary Trees
      BSTs
      AVL Trees
    Graphs
    Hash Tables
    Heaps

2. What Are Algorithms?

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.

Examples of Algorithms

3. Representation of Data Structures

Data structures can be represented in multiple ways, each with trade-offs:

A. Arrays

• Definition: Contiguous memory locations storing elements of the same type.
• Operations:
  • Access: $O(1)$ (direct indexing).
  • Insertion/Deletion: $O(n)$ (shifting required).
• Example:

  int arr[5] = {10, 20, 30, 40, 50};
  

  Visualization (After Insertion at Index 2):

B. Linked Lists

• Definition: Non-contiguous nodes where each node points to the next.
• Types:
  • Singly linked list
  • Doubly linked list
  • Circular linked list
• Operations:
  • Access: $O(n)$ (traversal required).
  • Insertion/Deletion: $O(1)$ (if head/tail is known).
• Example (Singly Linked List):

  flowchart LR
    A["Node 10"] --> B["Node 20"]
    B --> C["Node 30"]
    C --> D["Node 40"]

  After Insertion (50 at Head):

  flowchart LR
    E["Node 50"] --> A["Node 10"]
    A --> B["Node 20"]
    B --> C["Node 30"]

4. Algorithm Design Techniques

Common strategies to design algorithms:

Example: Binary Search (Divide and Conquer)

flowchart TD
  A["Start"] --> B["Check mid"]
  B -->|"x == target"| C["Found"]
  B -->|"x < target"| D["Search left half"]
  B -->|"x > target"| E["Search right half"]
  D --> B
  E --> B

Code Implementation:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Trace for arr = [1, 3, 5, 7, 9], target = 5:

5. Algorithm Analysis: Time and Space Complexity

A. Time Complexity (Big-O Notation)

Measures how runtime grows with input size $n$. Common notations:

• $O(1)$: Constant time (e.g., array access).
• $O(\log n)$: Logarithmic (e.g., binary search).
• $O(n)$: Linear (e.g., linear search).
• $O(n\log n)$: Linearithmic (e.g., merge sort).
• $O(n^2)$: Quadratic (e.g., bubble sort).
• $O(2^n)$: Exponential (e.g., recursive Fibonacci).

Example: Comparing Search Algorithms

B. Space Complexity

Measures memory usage. Examples:

• $O(1)$: Constant (e.g., iterative algorithms).
• $O(n)$: Linear (e.g., storing an array).
• $O(n^2)$: Quadratic (e.g., adjacency matrix for graphs).

Example: Space Complexity of Recursive vs. Iterative Fibonacci

6. Real-World Applications

A. eSewa (Nepal)

• Data Structure: Queues (FIFO) for processing transactions.
  • When you pay a bill, your request is added to a queue.
  • Servers process transactions in order, ensuring fairness.
• Algorithm: Priority Queues for urgent payments (e.g., electricity bills).

B. Daraz (Nepal/E-commerce)

• Data Structure: Tries (prefix trees) for autocomplete search.
  • When you type "sho", Daraz suggests "shoes", "shirt", etc., by traversing the trie.
• Algorithm: A Search* for recommendation systems (balances speed and accuracy).

C. Pathao (Ride-Hailing)

• Data Structure: Graphs to model roads and traffic.
  • Pathao uses Dijkstra’s or A* algorithm to find the fastest route.
• Algorithm: Greedy Algorithm for dynamic pricing (adjusts fares based on demand).

D. NTC (Nepal Telecom)

• Data Structure: Hash Tables for storing customer records.
  • Quick lookup of a customer’s phone number using their ID.
• Algorithm: Binary Search in sorted call logs for analytics.

7. Exam Tip: How to Score Full Marks

1. Definitions:

   • Always define terms precisely. For example:

     "A data structure is a way of organizing and storing data in a computer so that it can be accessed and modified efficiently."

   • "An algorithm is a step-by-step procedure to solve a problem in a finite amount of time."

2. Diagrams:

   • Draw state diagrams for operations (e.g., BST insertion, stack push/pop).
   • Example: After inserting 5, 3, 7 into a BST:

     flowchart TD
       A["5"] --> B["3"]
       A --> C["7"]

3. Time Complexity:

   • Memorize common complexities and their scenarios:
     • $O(n\log n)$: Merge sort, quicksort.
     • $O(n^2)$: Bubble sort, insertion sort.
   • Never write $O(n)$ for binary search—it’s $O(\log n)$.

4. Real-World Examples:

   • Link concepts to Nepali apps (eSewa, Daraz, Pathao) or global tech (Google, WhatsApp).
   • Example:

     "Like how Daraz uses tries for fast search, a trie is a tree-like DS where nodes represent prefixes of words."

5. Pseudocode + Trace Tables:

   • For algorithms, provide:
     1. Pseudocode (clear steps).
     2. Trace table (show variable changes step-by-step).
   • Example for Linear Search:

     for i from 0 to n-1:
         if arr[i] == target:
             return i
     return -1
     

     i	arr[i]	Action
     0	10	Not target
     1	20	Found (target=20)

6. Avoid Common Mistakes:

   • ❌ Saying "array is faster than linked list for everything." ✅ Correct: "Arrays have $O(1)$ access but $O(n)$ insertion/deletion, while linked lists have $O(1)$ insertion/deletion at head but $O(n)$ access."
   • ❌ Drawing a BST without balancing. ✅ Correct: Always show left < root < right.

8. Past Exam Questions Solved

Q1: Draw the Binary Tree for Given Traversals

Given:

• Inorder: R Z J T K H N M P
• Preorder: K Z R T J N H P M

Solution:

1. Preorder first element (K) is the root.
2. Split inorder into left (R Z J T) and right (H N M P).
3. Repeat for left and right subtrees.

Final Tree:

flowchart TD
  K --> Z
  K --> H
  Z --> R
  Z --> T
  T --> J
  H --> N
  H --> P
  N --> M

Q2: Define AVL Tree and Construct from Data Set

Definition:

"An AVL tree is a self-balancing BST where the heights of the left and right subtrees of any node differ by at most 1. It ensures $O(\log n)$ operations by rotations."

Construction for {4, 6, 12, 9, 5, 2, 13, 8, 3, 7, 11}:

1. Insert nodes one by one, checking balance factor.
2. Perform rotations if balance factor > 1 or < -1.

Final AVL Tree:

flowchart TD
  6 --> 4
  6 --> 9
  4 --> 2
  4 --> 5
  9 --> 7
  9 --> 12
  7 --> 3
  7 --> 8
  12 --> 11
  12 --> 13

9. Summary Table: Key Concepts

10. Final Checklist for Exams

Before submitting your answer:

1. Did I define all terms clearly?
2. Did I draw diagrams for every operation?
3. Did I compare time/space complexities?
4. Did I relate to real-world examples?
5. Did I trace the algorithm step-by-step?