Introduction to Data Structures & Algorithms: Core Concepts

1. Data Types and Abstract Data Types (ADTs)

1.1 What is a Data Type?

A data type defines a set of values and operations on those values. It categorizes data into primitive (e.g., int, char) and derived (e.g., string, array) types.

1.2 What is an Abstract Data Type (ADT)?

An ADT is a mathematical model of a data structure that specifies:

• Operations (e.g., push, pop for a stack).
• Properties (e.g., LIFO for a stack).
• No implementation details (e.g., whether it’s an array or linked list).

Example: Stack ADT

ADT Stack:
  Methods: push(item), pop(), peek(), isEmpty()
  Property: Last-In-First-Out (LIFO)

1.3 Why Use ADTs?

---

2. Algorithms: Definition and Characteristics

2.1 Definition

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

• Be finite (terminate).
• Have clear inputs/outputs.
• Perform definite operations.

2.2 Characteristics of Good Algorithms

2.3 Example: Tower of Hanoi (Recursive Algorithm)

Problem: Move n disks from source to target using an auxiliary peg, following rules:

1. Only one disk moves at a time.
2. A larger disk cannot be placed on top of a smaller one.

Visualization:

    [Disk 1] [Disk 2] [Disk 3]  // Initial state (Source)
               [Auxiliary]
               [Target]

Steps for n=3:

1. Move disk 1 → Auxiliary.
2. Move disk 2 → Target.
3. Move disk 1 → Target.
4. Move disk 3 → Target.
5. Move disk 1 → Source.
6. Move disk 2 → Source.
7. Move disk 1 → Target.

Recursive Pseudocode:

def tower_of_hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
    else:
        tower_of_hanoi(n-1, source, auxiliary, target)
        print(f"Move disk {n} from {source} to {target}")
        tower_of_hanoi(n-1, auxiliary, target, source)

Trace for n=2:

---

3. Problem-Solving Paradigms

3.1 Divide and Conquer

Break a problem into smaller subproblems, solve recursively, and combine results. Example: Merge Sort, Quick Sort.

3.2 Greedy Algorithms

Make locally optimal choices at each step to reach a global optimum. Example: Dijkstra’s shortest path, Huffman coding.

3.3 Dynamic Programming

Store solutions to subproblems to avoid redundant computations. Example: Fibonacci sequence, knapsack problem.

3.4 Backtracking

Explore all possible solutions by incrementally building candidates and abandoning partial solutions that cannot lead to a valid outcome. Example: N-Queens puzzle, Sudoku solver.

---

4. Recursion

4.1 Definition

Recursion is a technique where a function calls itself to solve smaller instances of the same problem.

4.2 Base Case vs. Recursive Case

• Base Case: Stops recursion (e.g., n == 1 in Tower of Hanoi).
• Recursive Case: Breaks problem into smaller subproblems.

4.3 How Stacks Enable Recursion

When a function calls itself, the call stack stores:

• Return address.
• Local variables.
• Parameters.

Visualization:

Call Stack (LIFO)
+---------------------+
| Return Address      |
| Local Variables     |
| Parameters          |
+---------------------+
| ... (previous calls)|
+---------------------+

Example: Factorial Recursion

def factorial(n):
    if n == 0:  # Base case
        return 1
    else:       # Recursive case
        return n * factorial(n-1)

Trace for factorial(3):

---

In the Real World

1. eSewa’s Transaction Queue (Queue ADT)

   • Idea: eSewa uses queues to manage transaction requests in the order they arrive (FIFO).
   • How: When a user initiates a payment, the request is enqueued. The system processes it only after all prior requests are handled, ensuring fairness.

2. Daraz’s Order Processing (Stack ADT)

   • Idea: Daraz uses stacks to manage "undo" operations for orders (e.g., canceling a recent order).
   • How: The last order placed is the first to be undone (LIFO), mimicking a stack’s behavior.

3. Pathao’s Ride Dispatch (Greedy Algorithm)

   • Idea: Pathao’s ride-matching system uses a greedy approach to assign the nearest available driver to a rider’s request.
   • How: It prioritizes the driver closest to the rider’s location at that moment, minimizing wait time.

---

Exam Tip

• Focus on Definitions: TU/PU exams love asking for ADT definitions (e.g., "Define stack as an ADT"). Memorize the operations and properties (e.g., stack: push, pop, LIFO).
• Trace Recursive Algorithms: For Tower of Hanoi or factorial, show the call stack step-by-step. Use a table like the one above.
• Compare Paradigms: Know when to use divide and conquer (e.g., merge sort) vs. greedy (e.g., Dijkstra’s). Example questions often ask for limitations (e.g., "Why isn’t greedy always optimal?").
• Pivot in Quick Sort: For past questions on quick sort’s pivot choice, draw the partition process and explain why a bad pivot (e.g., always first/last element) leads to O(n²) time.
• Stack Operations: For postfix evaluation or infix-to-postfix, show the stack state after each operation. Example:

  Infix: (A+B)*C-D
  Steps:
  1. Push A → Stack: [A]
  2. Push B → Stack: [A, B]
  3. Encounter ‘+’ → Pop B, A → Push 10 (A+B) → Stack: [10]
  4. Push C → Stack: [10, C]
  5. Encounter ‘*’ → Pop C, 10 → Push 20 (10*C) → Stack: [20]
  6. Encounter ‘-’ → Wait for operand (D).
  7. Push D → Stack: [20, D]
  8. Pop D, 20 → Push 10 (20-D) → Stack: [10]
  Postfix: AB+C*D-
  

---

Key Visuals Recap:

1. ADT Stack: Operations (push, pop) and LIFO property.
2. Tower of Hanoi: Disk movements for n=3.
3. Recursion Call Stack: Trace for factorial(3).
4. Postfix Evaluation: Stack state after each step for (A+B)*C-D.