DEV Community: Khushi

Generative AI vs Agentic AI

Khushi — Wed, 21 Jan 2026 07:44:42 +0000

Generative AI vs Agentic AI: Capability vs Behavior

Generative AI and Agentic AI are often discussed together, but they represent two very different layers of intelligence.

Generative AI is primarily about creation.

It reacts to a prompt and generates content-text, images, code, or audio-based on learned patterns. Its role is largely responsive: it waits for instructions and delivers an output. In this sense, Generative AI acts as a powerful capability, not an independent decision-maker.

Agentic AI, on the other hand, is about achieving goals.

Instead of simply responding to a single prompt, Agentic AI can plan, reason, take actions, evaluate outcomes, and iterate until a goal is accomplished. It is proactive and autonomous, capable of deciding what to do next without continuous human intervention.

Think of it this way:
Generative AI answers questions
Agentic AI solves problems

Importantly, Generative AI is a building block of Agentic AI. Agentic systems often rely on generative models for reasoning, communication, and content generation-but they go beyond generation by adding decision-making, memory, and control loops.

In short:
Generative AI = Capability (what the system can do)
Agentic AI = Behavior (how the system acts to achieve goals)

As AI systems evolve, the shift from purely generative tools to agentic systems marks a move from assistance to autonomy-and that distinction will define the next generation of intelligent applications.

What is Generative AI?

Generative AI focuses on creating human-like content such as text, images, code, or videos-only when prompted.

Examples:

ChatGPT → text & code
DALL·E → images
Sora → video
Nature: Reactive You ask a question → it generates a response No initiative, no long-term goal tracking

Generative AI is incredibly powerful, but it operates in a request-response loop. It does not decide what needs to be done next.

What is Agentic AI?

Agentic AI is designed to achieve goals autonomously.
Instead of waiting for prompts,

it Understands a high-level objective
Breaks it into steps
Uses tools and data
Executes actions
Monitors results and adapts
Nature: Proactive You give a goal → it plans, executes, and iterates Can seek approvals, retry failed steps, and optimize outcomes

In short, Agentic AI behaves more like a digital worker than a smart assistant.

Evolution Through Hiring Example

The video shows 4 stages improving a chatbot for hiring a backend engineer:

Basic GenAI: Helps draft JD, emails, questions → You do all actions manually.
RAG (Retrieval-Augmented): Uses company docs → Tailored JDs, questions.
Tools Added: APIs for LinkedIn, email, calendar → Auto-posts jobs, schedules.
Agentic AI: Understands goal → Plans entire flow, monitors applications, adapts (boosts job if low apps), handles onboarding.

Interview Points (1-Minute Pitch)

"Generative AI creates content reactively. Agentic AI achieves goals proactively."

GenAI: Prompt → Output (ChatGPT drafts email).
Agentic: Goal → Plan → Execute → Adapt (Hire engineer end-to-end).
Built using: GenAI (LLMs) + RAG + Tools + Planning/Memory.

RAG - The Smart Way to Improve AI Answers

Khushi — Thu, 20 Nov 2025 14:57:36 +0000

Retrieval-Augmented Generation (RAG) is transforming how we use AI by allowing models to think with real, live information instead of relying only on what they were trained on.

What is RAG ?

Retrieval-Augmented Generation (RAG) is an AI architecture that enhances large language models by retrieving up-to-date, domain-specific information from external knowledge sources and combining it with the model’s generation capabilities to produce accurate, factual, and context-aware responses.

To operationalize this concept, I built an end-to-end RAG pipeline that implements multi-modal PDF parsing (native text, tables, OCR), semantic chunking and sentence-transformer embeddings stored in FAISS for sub-second vector similarity search. Retrieved passages are reranked via cross-encoders and injected into LLM context, producing source-grounded responses with citation tracking—transforming static language models into retrieval-aware systems capable of handling enterprise document QA with verifiable, hallucination-resistant answers.

Why RAG was introduced ?

RAG was introduced to solve the limitations of traditional Large Language Models.Even though LLMs are powerful, they have major problems:

LLMs hallucinate-LLMs generate answers based on patterns they learned during training, not on real-time facts. So they sometimes produce confident but incorrect answers.
LLMs cannot store enterprise-specific knowledge.
LLMs have context-length limitations.
Fine-tuning alone is expensive and slow.

RAG was introduced to make LLMs more accurate, up-to-date, and trustworthy by giving them access to real-time, external knowledge.

Understanding RAG Components

1) Retriever (Search System):

What it does:

Takes your query (question)
Searches a knowledge base or vector database
Retrieves the most relevant documents based on similarity

2) Knowledge Store:

This is where all your information is stored.

What it contains:

Text documents
FAQ answers
PDFs
Website content
Company policies
Any internal data
Each document is broken into chunks and converted into embeddings.
- Common vector stores: Pinecone, FAISS, Weaviate, Chroma DB

3) Generator:

This is the AI model that generates the final answer using the retrieved information.

What it does:
It takes:

User question
Retrieved documents Then Combines both and gives a factual, accurate answer

How RAG works — step-by-step

Ingest documents - Collect the text sources you want the system to use (PDFs, docs, emails, wiki pages).
Chunking - Split long documents into smaller passages (e.g., 200–1,000 tokens) so retrieval can return precise context.
Embed the chunks - Convert each chunk into a numeric vector using an embedding model (semantic representation).
Index / store vectors - Put those vectors into a vector index (ANN/FAISS/Weaviate/Pinecone/Qdrant) for fast similarity search.
User query → embed - When a user asks something, convert the query into an embedding with the same model used for documents.
Vector search (retrieve) - Use the query embedding to find the top-k most similar document chunks from the index (e.g., top 5–50).
Optional rerank - Reorder the retrieved chunks with a stronger cross-encoder or heuristic to improve relevance (at the cost of extra latency).
Construct prompt / context - Build the prompt for the LLM by combining the user query and the selected retrieved chunks (with any instructions or system message).
LLM generation - Send the prompt to the language model; the model generates an answer grounded in the retrieved context.
Post-process & cite - Optionally filter the output, extract sources, add citations/footnotes, or run a verifier to check factuality.
Cache & feedback loop - Cache frequent query results, log user feedback, and update the index or rerank models to improve future results.

Following this architecture, I implemented a production-ready system that handles the complexity of real-world documents—processing heterogeneous PDFs through multi-modal extraction, chunking semantically at 512-token boundaries, and indexing with FAISS for millisecond retrieval. The addition of cross-encoder reranking and structured citation extraction ensures responses aren't just accurate, but verifiable and trustworthy for enterprise use cases.

🔗 Implementation:https://github.com/khushi2488/RAG_Document_QA_System

Challenges :

Handling Noisy or Incomplete Knowledge Bases - RAG depends completely on the quality of the data stored in the knowledge base (documents, PDFs, text, etc.).
Latency and scalability bottlenecks occur in RAG because every query requires multiple steps—embedding, vector search, reranking, and LLM generation—which slows down responses. As data volumes and user traffic grow, these pipelines become harder and more expensive to scale, making fast, real-time RAG performance a key challenge in today’s AI systems.
RAG systems must balance retrieving many documents (breadth) with retrieving only the most relevant ones (depth). Too much breadth increases noise and slows down the model, while too much depth risks missing important context—making this trade-off a critical challenge for building accurate and efficient RAG pipelines.

How People Are Using RAG

Retrieval-Augmented Generation (RAG) lets users “talk” to their data. By connecting an LLM with a knowledge base—like manuals, documents, logs, or videos—RAG can deliver accurate, context-rich answers.

Where RAG is used:

Healthcare: Doctors and nurses get quick, reliable support from systems connected to medical indexes.
Finance: Analysts can query real-time or historical market data for insights.
Businesses: Any company can turn internal documents into smart assistants that help with:
- Customer and field support
- Employee training
- Developer and IT productivity

Because RAG can work with any dataset, its applications are multiplying. This is why major companies like AWS, IBM, Google, Microsoft, NVIDIA, Oracle, Glean, and Pinecone are adopting RAG widely.

RAG Vs Fine Tuning:

Tools & Frameworks for Building RAG

RAG systems rely on several key tools working together to retrieve the right information and generate accurate answers.

Embedding Models: OpenAI, Sentence Transformers, Cohere, Google Vertex
Vector Databases: Pinecone, Weaviate, Qdrant, Milvus, FAISS
RAG Frameworks: LangChain, LlamaIndex, Haystack, DSPy
LLMs: GPT, Llama 3, Gemini, Mistral, Claude
Document Processing: Apache Tika, PyPDF2, Unstructured.io
Evaluation & Monitoring: TruLens, RAGAS, Arize Phoenix, Weights & Biases

Future of the RAG:

The future of RAG is moving toward faster, smarter, and more autonomous AI systems. RAG will become more efficient with advanced vector databases, better retrieval algorithms, and larger context windows, allowing AI to use massive knowledge sources without slowing down. It will also evolve into RAG 2.0 and 3.0 architectures, where models combine retrieval, reasoning, and verification to produce more accurate, trustworthy outputs. As companies adopt AI at scale, RAG will play a key role in keeping enterprise systems up-to-date, cost-effective, and grounded in reliable information.

Cycle Detection in the Directed Graph using the DFS

Khushi — Sun, 31 Aug 2025 17:12:34 +0000

Cycle detection in a directed graph is a classic algorithm problem and must-know for backend and platform engineers.

What is a cycle in a directed graph?

The edges of a directed graph, which resemble arrows pointing from one node to another, have a specified direction.
When you can begin at a node, follow the directed edges, and ultimately return to the same node without retracing any edges backward, you have a cycle.

In simple terms: A cycle is a loop of dependencies.
Imagine tasks A, B, and C with these relationships:
A → B (A must be done before B)
B → C (B must be done before C)
C → A (C must be done before A)
Here, you’re stuck in a loop:
A depends on B → B depends on C → C depends on A.
There’s no valid starting point — that’s a cycle

Why cycle detection is important?

Cycles mean circular dependencies → no valid ordering is possible
When you can continue following arrows and go back to the beginning point, you have a cycle in a directed graph. Tasks or dependencies cannot be arranged in a valid sequence because of this loop.

Why DFS for Cycle Detection?

Because it thoroughly examines each path before turning around, Depth-First Search (DFS) is especially well-suited for identifying cycles in a directed graph and aids in the effective detection of loops.
Because it tracks the current traversal, follows the paths naturally, and effectively detects cycles in directed graphs, DFS is recommended.

Intuition for DFS-based Cycle Detection

Step 1: Select any node that hasn't been investigated yet and launch DFS from it.

This guarantees that every disconnected graph element is examined.

Step 2: Add it to the recursion stack and mark it as visited.

Nodes that we've seen at least once are indicated by Visited[].
Nodes that are a component of the current DFS path are marked by the Recursion Stack (PathVisited[]).
Why are there two arrays?

Visited[] stops unnecessary node revisits.
Cycles along the present path are detected with the use of the recursion stack.

Step 3: Recursively examine every neighbor

Visit each of the current node's neighbors.
For every neighbor:
- Call DFS about it if it hasn't been visited.
- A cycle is identified if it is in the recursion stack (we're revisiting a node in the current path).
- Repeat for everyone.

Step 4: Identifying the Cycle - We may identify a loop as soon as we discover a neighbor that is already on the recursion stack.

An illustration of intuition
- Imagine traversing a maze.
- You are going around in circles if you enter a room that you have already visited on this journey.

Step 5: Backtracking - Take the node out of the recursion stack after exploring all of its neighbors.

This stage guarantees that the recursion stack only includes nodes that are presently being explored and not ones that have been fully processed.

Step 6: Do this for every node that hasn't been visited.

Start DFS on the unconnected components that haven't been visited yet.This guarantees full cycle detection throughout the graph.

Important Point to Keep in Mind

The key to identifying cycles is the recursion stack.
Visited[] by itself is insufficient.
You can only determine whether a cycle is present by monitoring the nodes in the current DFS path.
Consider this: "I'm in a loop if I go back to a node that's still on my current path!"

Let's understand through the Dry Run,

Let’s take 4 nodes (0, 1, 2, 3) with edges:
0 → 1
1 → 2
2 → 3
3 → 1 (Back edge → creates cycle)

Initial State

1.Start DFS at Node 0
Mark 0 visited & in recursion stack.

Neighbors of 0: 1

2: DFS(1)
Mark 1 visited & in recursion stack.

Neighbors of 1: 2

3: DFS(2)
Mark 2 visited & in recursion stack.

Neighbors of 2: 3

4: DFS(3)
Mark 3 visited & in recursion stack.

Neighbors of 3: 1

But 1 is already in recursion stack → Cycle Detected!

Why this detects a cycle:

When a DFS from node u sees an edge u → v where v is already on the current recursion stack, it means there is a path from v down to u (because v is an ancestor in the recursion), and now u points back to v — so we have a directed cycle.

Backtracking (after detection)

After detecting the cycle, typical DFS cycle-detection code will return True up the call chain to stop further exploration (or record the cycle).
Recursion unwinds, and recStack entries are cleared (set back to False) as each call returns.

C++ Code: Cycle Detection in Directed Graph (DFS)

#include <bits/stdc++.h>
using namespace std;

bool dfsCycle(int node, vector<vector<int>> &graph, vector<bool> &visited, vector<bool> &recStack) {
    visited[node] = true;
    recStack[node] = true;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            if (dfsCycle(neighbor, graph, visited, recStack))
                return true;
        }
        else if (recStack[neighbor]) {
            // Found a back edge → cycle
            return true;
        }
    }

    recStack[node] = false; // backtrack
    return false;
}

bool isCyclic(int V, vector<pair<int,int>> &edges) {
    vector<vector<int>> graph(V);
    for (auto &e : edges) {
        graph[e.first].push_back(e.second);
    }

    vector<bool> visited(V, false);
    vector<bool> recStack(V, false);

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfsCycle(i, graph, visited, recStack))
                return true;
        }
    }
    return false;
}

int main() {
    int V = 4;
    vector<pair<int,int>> edges = {
        {0, 1},
        {1, 2},
        {2, 3},
        {3, 1} // cycle here
    };

    if (isCyclic(V, edges))
        cout << "Cycle detected in the graph!" << endl;
    else
        cout << "No cycle found." << endl;

    return 0;
}

Time Complexity
We perform a DFS traversal of the graph.
In DFS, each vertex (V) is visited once, and each edge (E) is explored once.
Thus, total complexity: O(V+E)

Space Complexity
Visited Array → O(V)
Recursion Stack Array → O(V)
Recursive Call Stack (function calls) → O(V) in the worst case (when the graph is like a long chain).
So, total space complexity: O(V)

Topological Sort

Khushi — Sun, 31 Aug 2025 17:02:57 +0000

What is Topological Sorting?

Topological Sorting is a method to organize the vertices of a Directed Acyclic Graph (DAG) in a sequence where, for every directed edge u → v, vertex u precedes vertex v in the sequence.
Topological sorting is the act of sequencing “items with prerequisites”
in an order such that each thing comes only after everything it depends on.

Why only DAGs?
First let's understand ,

1) Why Directed?

Dependencies always exhibit a specific direction: If A → B, it means “A must come before B.” in an undirected graph the relationship can be unclear.
If A and B are connected, does A depend on B or B depend on A? There’s no way to tell. Therefore, directed edges are necessary to clearly indicate which task is dependent on which.

2)Why Acyclic?

A cycle refers to a situation where tasks are mutually dependent on one another in a circular manner.

For instance:
A → B (A precedes B)
B → C (B precedes C)
C → A (C precedes A)
At this point, we're in a stalemate:
A needs to occur before B,
B before C,
C before A.
This presents a paradox → no permissible sequence can be determined.
This is why cycles render topological sorting unachievable.

Real-life example:-

1) Software Development (Compilation Sequence)
During the compilation of extensive software projects, it is crucial for the compiler to adhere to file dependencies.

For instance:

Utility.h needs to be compiled prior to Main.cpp (since Main.cpp includes it).
Math.cpp relies on Math.h (which means Math.h must be compiled first).
Neglecting these dependencies will result in compilation errors.

👉 The compiler uses topological sorting internally to determine the appropriate order for compiling files.

2) Project Management (Task Scheduling)
In project tasks, there are often dependencies, similar to nodes in a graph.

Example Project Flow:
Task A: Collect requirements.
Task B: Design system architecture (depends on A).
Task C: Develop code (depends on B).
Task D: Conduct software testing (depends on C).
Task E: Create documentation (depends on B, but is independent of C/D).
In this case, a suitable sequence could be:
A → B → C → D and B → E (allowing E to proceed in parallel after B).

Approaches for Topological Sorting

There are two primary methods:
1.The In-degree Method (BFS) or Kahn's Algorithm
2.The Depth-First Search (DFS) method

Let’s understand Kahn’s Algorithm in detail in this blog.
Core Concept:
Kahn’s Algorithm is a BFS-based technique that builds a topological order by repeatedly removing nodes with no incoming edges (in-degree = 0).

Intuition:

Nodes with in-degree = 0 represent tasks with no pending prerequisites → they can be executed immediately.
Once such a task is completed, we update the in-degree of its dependent tasks.
If any dependent task’s in-degree becomes 0, it is ready to execute next. This process continues until all nodes are processed.

Steps in Kahn’s Algorithm

Step 1: Compute In-Degree of Each Node

In-degree = number of incoming edges to a node.
For every edge A → B, increment in-degree of B by 1.
Store in-degree values in an array or hash map.

Step 2: Initialize a Queue with All In-degree 0 Nodes

These nodes have no dependencies → they can be done right away.
Use a queue (FIFO) to process them.
If multiple nodes have in-degree 0, any order is valid

Step 3: Process Queue Iteratively

While the queue is not empty:
1.Remove a node u from the queue.
2.Append u to the topological order result list.
3.For each outgoing edge (u → v):

Decrease the in-degree of v by 1 (since u is processed).
If v’s in-degree becomes 0, add it to the queue.

Step 4: Check for Cycles

Following processing, if there are less nodes in the result list than there are nodes in the graph overall, then:
In-degree = 0 was never reached by some nodes.
This indicates that a cycle (circular dependency) exists.Topological sorting is therefore impossible.

Let’s walk through a dry run to better understand how this algorithm works in practice

Let’s say we have 6 tasks (nodes):
0, 1, 2, 3, 4, 5
5 → 2
5 → 0
4 → 0
4 → 1
2 → 3
3 → 1

Step 1: Compute In-degree of Each Node

Count incoming edges for each node:
Node 0: in-degree = 2 (from 5, 4)
Node 1: in-degree = 2 (from 4, 3)
Node 2: in-degree = 1 (from 5)
Node 3: in-degree = 1 (from 2)
Node 4: in-degree = 0
Node 5: in-degree = 0
📌 In-degree array: [2, 2, 1, 1, 0, 0]

Step 2: Initialize Queue with In-degree = 0 nodes

Nodes 4 and 5 have in-degree = 0 → enqueue them.

Step 3: Process Queue Iteratively

Iteration 1
- Dequeue 4 → add to result.
- For edges from 4:
  - 4 → 0: reduce in-degree[0] → 1
  - 4 → 1: reduce in-degree[1] → 1

Iteration 2
- Dequeue 5 → add to result.
- For edges from 5:
- 5 → 2: reduce in-degree[2] → 0 → enqueue 2
- 5 → 0: reduce in-degree[0] → 0 → enqueue 0

Iteration 3
- Dequeue 2 → add to result.
- For edges from 2:
  - 2 → 3: reduce in-degree[3] → 0 → enqueue 3

Iteration 4
- Dequeue 0 → add to result.
- Node 0 has no outgoing edges.

Iteration 5
- Dequeue 3 → add to result.
- For edges from 3:
  - 3 → 1: reduce in-degree[1] → 0 → enqueue 1

Iteration 6
- Dequeue 1 → add to result.
- Node 1 has no outgoing edges.

Step 4:Check for Cycles
All 6 nodes are processed → no cycle.
✅ Valid topological order found.
[4, 5, 2, 0, 3, 1]
Also note that different valid orders are possible depending on queue processing order.

Code snippet

#include <bits/stdc++.h>
using namespace std;

vector<int> topologicalSortKahn(int V, vector<pair<int,int>> &edges) {
    // Step 1: Build graph and compute in-degree
    vector<vector<int>> graph(V);
    vector<int> in_degree(V, 0);

    for (auto &edge : edges) {
        int u = edge.first, v = edge.second;
        graph[u].push_back(v);
        in_degree[v]++;
    }

    // Step 2: Initialize queue with in-degree = 0 nodes
    queue<int> q;
    for (int i = 0; i < V; i++) {
        if (in_degree[i] == 0)
            q.push(i);
    }

    vector<int> topo_order;

    // Step 3: Process queue
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        topo_order.push_back(node);

        // Reduce in-degree of neighbors
        for (int neighbor : graph[node]) {
            in_degree[neighbor]--;
            if (in_degree[neighbor] == 0)
                q.push(neighbor);
        }
    }

    // Step 4: Check for cycle
    if ((int)topo_order.size() != V) {
        cout << "Cycle detected! Topological sort not possible." << endl;
        return {};
    }

    return topo_order;
}

int main() {
    int V = 6;
    vector<pair<int,int>> edges = {
        {5, 2},
        {5, 0},
        {4, 0},
        {4, 1},
        {2, 3},
        {3, 1}
    };

    vector<int> order = topologicalSortKahn(V, edges);

    cout << "Topological Order: ";
    for (int node : order)
        cout << node << " ";
    cout << endl;

    return 0;
}

Let's analyze the time complexity and space complexity
Each node is enqueued/dequeued exactly once.
Each edge is processed exactly once (when decreasing in-degree).
so time complexity is Time Complexity: O(V + E)
We use in-degree array and queue.
so Space Complexity :O(V)

Kahn’s Algorithm (BFS-based) is iterative, so it doesn’t face recursion depth issues that can occur in the DFS approach.

Sorting and Bubble Sort Explained

Khushi — Sun, 24 Aug 2025 08:55:06 +0000

Sorting: What Is It?

Sorting is the process of placing data according to one or more criteria in a certain order, usually either descending (biggest → smallest) or ascending (smallest → largest).

Why Does Sorting Matter in Practical Uses?

In computer science, sorting algorithms are vital because they help with effective data organization. Sorting is used behind the scenes everywhere, from refining social media feeds to powering search engines.

Faster Searching: Binary Search and other effective searches are made possible by sorted data.
Improved User Experience: Products are shown in e-commerce apps according to factors like price and rating.
Effective Processing: Sorted data is necessary for many algorithms to function better.
Clear Visualization: Charts and trends are easier to comprehend when data is sorted.
Real-World Use Cases: Healthcare (organized appointments), Banking (organized transactions), etc.

The table below shows the time complexity, stability, and other properties of popular sorting algorithms. It helps to quickly compare which algorithm to use based on the problem requirements.

Introduction to Bubble Sort

Bubble Sort is one of the simplest and easiest-to-understand sorting algorithms. It is usually the first algorithm taught to beginners due to its clear logic and step-by-step process.

How it works:

Compare adjacent elements.
If the current element is greater than the next, swap them.
After each pass, the largest element “bubbles up” to its correct position at the end.
Repeat until no swaps are needed (array is sorted).

Bubble Sort Example – Step-by-Step Dry Run
👉 Input Array: [64, 34, 25, 12, 22, 11, 90]

Pass 1 (i = 0)

Largest element 90 is placed at the end.

Pass 2 (i = 1)
Now last element (90) is already sorted, so we check till n-2.

Second largest element 64 is now in place.

Pass 3 (i = 2)

Check till n-3 (last 2 sorted).

Third largest element 34 is fixed.

Pass 4 (i = 3)

Check till n-4.

25 is in position.

Pass 5 (i = 4)

Check till n-5.

22 is placed.

Pass 6 (i = 5)

Check till n-6.

Compare 11 & 12 → no swap.
Already sorted → algorithm stops.

Final Sorted Array:
[11, 12, 22, 25, 34, 64, 90]

Bubble Sort in C++

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;  // Optimization: check if swap happens
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // If no swaps in this pass, array is already sorted
        if (!swapped)
            break;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    bubbleSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Time and Space Complexity

Best Case (Already Sorted): O(n)
Worst Case: O(n²)
Average Case: O(n²)
Space Complexity: O(1) (in-place)
Stability: ✅ Yes (does not change relative order of equal elements)

Depth-First Search

Khushi — Fri, 25 Apr 2025 04:11:22 +0000

🔁Quick BFS Recap

In Breadth-First Search (BFS), you explore the graph level by level.
You visit all immediate neighbors first, then move on to their neighbors, and so on.
Uses a queue (FIFO)
Best for shortest path in unweighted graphs
Real-life: friend suggestions, web crawling, peer-to-peer networks

Now, Let’s Dive into DFS – Depth-First Search

No more level-by-level. It’s time to go DEEP!
In DFS, you pick a path and go as deep as possible, only backtracking when there’s nowhere left to go.

Let's Imagine this,

You enter a maze and just keep walking forward till you hit a dead-end, then backtrack and explore the next path.

It Uses recursion or a stack and best for the Exploring complete paths, Detecting cycles, Maze solving, Topological sort.

What is DFS?
Depth-First Search (DFS) is a classic graph traversal algorithm.
Instead of exploring layer by layer like BFS, it dives deep into each branch of a graph or tree before backtracking.

How It Works:

1.Start from a source node

Choose a node to begin with (say, node 0).
This will be the root of your traversal.

2.Use a stack (or recursion) to track the path

DFS relies on a stack data structure.
You can either explicitly use a stack or let recursion handle it for you (since function calls internally use a call stack).

3.Maintain a visited[] array

To avoid infinite loops (especially in cyclic graphs), keep track of nodes you’ve already visited.
This ensures each node is processed only once.

4.Process nodes deeply before backtracking

Visit the current node and mark it as visited.
Then, move to its first unvisited neighbor.
Continue this process until there are no unvisited neighbors left.
When stuck, backtrack to the most recent node that still has unvisited neighbors, and repeat.

🧠 Graph Structure (Adjacency List based on the image):
From the graph:
1: [2, 3]
2: [1, 4]
3: [1, 5]
4: [2, 5]
5: [3, 4]

We’ll assume:
It’s an undirected graph.

Step 1

Start DFS at 1.
Mark 1 as visited → Visited = [1].
Explore first neighbor → 2.

Step 2

At node 2.
Mark 2 as visited → Visited = [1, 2].
Explore first neighbor → 4.

Step 3

At node 4.
Mark 4 as visited → Visited = [1, 2, 4].
Neighbors of 4 = (2, 5).
- 2 already visited → skip.
- Move to neighbor 5.

Step 4

At node 5.
Mark 5 as visited → Visited = [1, 2, 4, 5].
Neighbors of 5 = (3, 4).
- 4 already visited → skip.
- Next is 3.

Step 5

At node 3.
Mark 3 as visited → Visited = [1, 2, 4, 5, 3].
Neighbors of 3 = (1, 5). Both already visited → backtrack.

Step-by-Step (Recursive DFS)
Start at 1, mark visited → dfs = [1]
Go to neighbor 2 (first unvisited of 1) → dfs = [1, 2]
Go to neighbor 4 (from 2) → dfs = [1, 2, 4]
Go to neighbor 5 (from 4) → dfs = [1, 2, 4, 5]
Go to neighbor 3 (from 5) → dfs = [1, 2, 4, 5, 3]
All neighbors visited. Backtrack until all paths are done.

🔄 Final DFS Traversal Order:
1 → 2 → 4 → 5 → 3

DFS Code in C++

#include <iostream>
#include <vector>
using namespace std;

// Helper method to perform DFS recursively
void dfsHelper(int node, vector<int> adj[], vector<bool>& visited, vector<int>& dfs) {
    visited[node] = true;
    dfs.push_back(node);

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfsHelper(neighbor, adj, visited, dfs);
        }
    }
}

// DFS function that calls the helper
vector<int> dfsOfGraph(int V, vector<int> adj[]) {
    vector<int> dfs;
    vector<bool> visited(V, false);
    dfsHelper(0, adj, visited, dfs); // starting from node 0
    return dfs;
}

int main() {
    int V = 5;
    vector<int> adj[V];


    // 1-2, 1-3, 2-4, 3-5, 4-5
    adj[0] = {1, 2};    // node 1 -> 2, 3
    adj[1] = {0, 3};    // node 2 -> 1, 4
    adj[2] = {0, 4};    // node 3 -> 1, 5
    adj[3] = {1, 4};    // node 4 -> 2, 5
    adj[4] = {2, 3};    // node 5 -> 3, 4

    vector<int> result = dfsOfGraph(V, adj);

    cout << "DFS Traversal: ";
    for (int node : result)
        cout << node + 1 << " ";  
    cout << endl;

    return 0;
}

⏱ Time Complexity → O(V + E)

V (Vertices):
- Every vertex is visited exactly once.
- Visiting a node + marking as visited = O(1) each → overall O(V).
E (Edges):
- For every node, DFS explores its adjacency list (all connected edges).
- Across the whole graph, each edge is checked at most twice (once from each endpoint in an undirected graph, once in a directed graph).
- Total edge exploration = O(E).

So, the total time = O(V + E).

Space Complexity → O(V)
DFS requires memory for:

Visited array → To keep track of visited nodes (size = V).
Recursion stack (or explicit stack) →
In the worst case (graph shaped like a linked list), recursion depth can go up to V.

So, maximum call stack size = O(V).

Breadth-First Search (BFS) Algorithm

Khushi — Mon, 14 Apr 2025 03:46:49 +0000

Let's Imagine This first,
You’re in a maze of rooms. You want to find the shortest way out. So you start from the first room, check all the adjacent rooms, then go to the next layer of rooms, and keep expanding until you reach the exit.

That’s Breadth-First Search (BFS) – you explore layer by layer, level by level.

What is BFS?
Breadth-First Search (BFS) is one of the most fundamental graph traversal algorithms. Instead of diving deep into a single path, BFS explores nodes level by level, ensuring that all neighbors of a node are visited before moving deeper.

It’s especially powerful when you need to find the shortest path in an unweighted graph

How It Works
1.Start from a source node

Choose a node to begin with (for example, node 0).
This node will be the root of your traversal.

2.Use a queue (FIFO) to track nodes to visit next

A queue is the ideal data structure because BFS needs to process nodes in the same order they are discovered.
First In → First Out ensures that we finish exploring one "level" of neighbors before moving on to the next.

3.Keep a visited[] array (or set)

To avoid infinite loops (e.g., in cyclic graphs), we maintain a record of which nodes we have already visited.
This ensures we never process the same node twice.

4.Process nodes one by one

Take the front node from the queue.
Look at all of its neighbors:
- If a neighbor has not been visited → mark it visited and add it to the queue.
Continue this until the queue becomes empty.

Let's understand With Dry Run of Simple Example (Graph)

Step 1
Visited Node: 1

We start with node 1, mark it visited, and add its neighbors (2 and 3) to the queue.

Step 2
Visited Node: 2 (front of queue is dequeued)

From node 2, we explore its neighbors. Node 4 is unvisited, so it is added to the queue.

Step 3
Visited Node: 3

From node 3, we explore neighbors. Node 5 is unvisited, so it gets added to the queue.

Step 4
Visited Node: 4

Node 4 has neighbors (2 and 5). Both are already visited/queued, so nothing new is added.

Step 5
Visited Node: 5

Node 5 has neighbors (3 and 4). Both are already visited, so BFS traversal is complete.

✅ Traversal Order: 1 → 2 → 3 → 4 → 5

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> bfsOfGraph(int V, vector<int> adj[]) {
    vector<int> bfs;
    vector<bool> visited(V, false);
    queue<int> q;

    // Start BFS from node 0
    q.push(0);
    visited[0] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        bfs.push_back(node);

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }

    return bfs;
}

int main() {
    int V = 5;
    vector<int> adj[V];

    // Undirected Graph Example
    adj[0] = {1, 2};
    adj[1] = {0, 3};
    adj[2] = {0, 4};
    adj[3] = {1};
    adj[4] = {2};

    vector<int> result = bfsOfGraph(V, adj);

    cout << "BFS Traversal: ";
    for (int node : result)
        cout << node << " ";
    cout << endl;

    return 0;
}

📈 Time & Space Complexity of BFS

⏱ Time Complexity → O(V + E)
V (Vertices):

Each vertex is enqueued and dequeued at most once.
Visiting and marking a node takes constant time → O(V). E (Edges):
For each vertex, BFS explores its adjacency list (all connected edges).
Across the entire graph, every edge is considered once (in undirected graphs, twice — but still O(E)).

Therefore, the total work done = O(V) + O(E) = O(V + E).

Space Complexity → O(V)

BFS requires extra memory for:

Visited array → To track whether a node has already been explored (size = V).
Queue → In the worst case, the queue may hold all vertices of a level at once (up to V).
Together, this means BFS uses memory proportional to the number of vertices → O(V).

Use-Cases of BFS
1.Shortest Path in Unweighted Graphs

BFS is the go-to algorithm when you need the minimum number of steps to move from one node to another. Example:
In a city represented as a graph (intersections = nodes, roads = edges), BFS can find the shortest route if all roads have equal weight (like equal distance or equal travel cost).
That’s why BFS is widely used in GPS navigation systems (when edge weights are uniform).

2.Peer-to-Peer (P2P) Networks

In P2P systems (like BitTorrent), BFS helps in discovering nearby peers efficiently. Example:
A node starts with a small list of peers.
BFS can explore connections level by level to quickly discover all reachable peers in the network.
This ensures faster file sharing and efficient resource discovery.

🔍 Rabin-Karp Algorithm

Khushi — Sun, 13 Apr 2025 16:35:59 +0000

Ever tried finding a word in a huge chunk of text and thought,
There has to be a faster way than checking every single character!😩
Enter the Rabin-Karp Algorithm — a smart and efficient way to search for patterns in strings using a clever trick called rolling hash 🪄
Let’s break it down step by step — no jargon, no confusion, just clarity and fun. 🧠✨
🤔 The Problem
You’re given:
Text → "geeksforgeeks"
Pattern → "geek"
And your task is to find all positions where the pattern appears in the text.
✅ Expected Output:
[1, 9] // Using 1-based indexing (because humans count from 1 😅)

🧠 The Big Idea (Why Rabin-Karp Is Smart?)
Instead of comparing every letter of the pattern with every possible substring of the text, what if we could:
1.Convert the pattern into a number (hash)
2.Convert parts of the text into numbers too
3.Compare those numbers instead of characters
→ Much faster than checking each letter!
If the hashes match, we double-check the actual characters — just to be sure (because different strings can sometimes have the same hash — that's called a collision).

🔢 What's a Hash Anyway?
Think of a hash as a string’s fingerprint:
Same strings → same hash
Different strings → usually different hashes
Rabin-Karp uses a rolling hash, which is just a clever way of updating the hash as we move through the text, without recalculating everything from scratch.

🔄Rolling Hash — The Star of the Show🌟
Let’s say we’ve already calculated the hash for "geek" — now we want the hash for the next window: "eeks".
Instead of this:
Recalculate hash("eeks") from scratch 😩

We do this:
t_new = (d * (t_old - old_char * h) + new_char) % q
Where:
-t_old is the previous window’s hash
-old_char is the character sliding out of the window
-new_char is the character sliding into the window
-d is the number of characters in the alphabet (e.g., 256 for extended -ASCII)
-h = d^(M-1) % q is used to remove the effect of the oldest character
-q is a large prime number used to reduce hash collisions

We move the window and get a new hash in constant time! 🔥

💥Why Rabin-Karp is Awesome
✅ Fast search using hashing
✅ Great for multiple pattern searches
✅ Average time complexity: O(N + M)
✅ Used in:
1.Plagiarism detection 🧑‍🎓
2.Big text search engines
3.DNA sequence matching 🧬
4.Intrusion detection systems 🔐

🧾 Dry Run: Let’s See It in Action
🔸 Input:
Text: "geeksforgeeks"
Pattern: "geek"

Step 1: Initialize Variables
M = 4 // length of pattern
N = 13 // length of text
d = 256 // characters in the alphabet
q = 101 // prime number for hashing

Step 2: Compute Hash Multiplier
h = pow(d, M-1) % q = (256^3) % 101 = 88

Step 3: Calculate Initial Hashes
p = hash("geek") % q = 27
t = hash("geek") % q = 27

Step 4: Slide the Window and Compare
Iteration 1: "geek" → Match found ✅ at index 1
Iteration 2: "eeks" → Hash ≠ 27 → skip ❌
Iteration 3: "eksf" → Hash ≠ 27 → skip ❌
...
Iteration 9: "geek" → Match found ✅ at index 9

🧑‍💻Final Result:
[1, 9]

👨‍💻 C++ Code: Rabin-Karp Algorithm

#include <iostream>
#include <vector>
using namespace std;

// Your Rabin-Karp search function
vector<int> search(string pattern, string text) {
    vector<int> result;
    int d = 256;   // Total characters (ASCII)
    int q = 101;   // Prime number to avoid collision
    int M = pattern.length();
    int N = text.length();
    int p = 0;     // hash for pattern
    int t = 0;     // hash for text window
    int h = 1;

    // Step 1: Calculate hash multiplier h = pow(d, M-1) % q
    for (int i = 0; i < M - 1; i++)
        h = (h * d) % q;

    // Step 2: Initial hash values
    for (int i = 0; i < M; i++) {
        p = (d * p + pattern[i]) % q;
        t = (d * t + text[i]) % q;
    }

    // Step 3: Slide pattern over text
    for (int i = 0; i <= N - M; i++) {
        // If hash values match, check characters one by one
        if (p == t) {
            bool match = true;
            for (int j = 0; j < M; j++) {
                if (text[i + j] != pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match)
                result.push_back(i + 1); // 1-based indexing
        }

        // Step 4: Update hash using rolling hash
        if (i < N - M) {
            t = (d * (t - text[i] * h) + text[i + M]) % q;
            if (t < 0)
                t = t + q; // Make sure hash stays positive
        }
    }

    return result;
}

// Main Function
int main() {
    string text = "ababcabcabababd";
    string pattern = "ababd";

    vector<int> positions = search(pattern, text);

    if (!positions.empty()) {
        cout << "Pattern found at position(s): ";
        for (int pos : positions)
            cout << pos << " ";
        cout << endl;
    } else {
        cout << "Pattern not found in the text." << endl;
    }

    return 0;
}

🧠 Key Takeaways
Rabin-Karp is a hash-based string searching algorithm.
It uses a rolling hash to speed up window comparisons.
Perfect for situations where you need to find multiple patterns efficiently.

🔍 Let's Find It – Binary Search! 🚀

Khushi — Sat, 12 Apr 2025 04:05:53 +0000

🧠 The Magic of Smart Searching
A Tale of Sorted Boxes & Smart Moves
A Tale of Two Halves: The Smart Snack Box 🍫
You're back in your room and spot your snack stash – but this time
it’s super organized.
All your chocolates are sorted in alphabetical order:
[5-Star, Dairy Milk, KitKat, Munch, Perk]
Now, you want to grab your fav – Munch.
But wait! 🤔 Instead of checking each one (like in linear search),
you’ve got a smarter plan this time!

🧠 What is Binary Search?
Binary Search is like being a smart detective in a sorted list.
Rather than checking one-by-one, you go straight to the middle!
You divide and conquer!
Cut the list in half
🔍 Check the middle item
👉 Decide: Go left? Or go right?
Repeat till you find it (or not)!

🎯 Let’s Do a Dry Run:
Snack box = [5-Star, Dairy Milk, KitKat, Munch, Perk]
You're searching for Munch 🍫
Let’s turn the story into steps:

❓ What if it’s not there?
Snack box: [5-Star, Dairy Milk, KitKat, Munch, Perk]
You search for Snickers 🍫 (not in list)
You do the same process:
Middle = KitKat → not Snickers
Move right or left → check → still not there ❌
Eventually, you return -1 = Not Found.

📌 Steps to Remember:
Check if the array is sorted ✅
Set two pointers → low and high
While low <= high:
Find mid = (low + high)/2
Is it the target? → 🎯 Return index!
If target < mid → Move high = mid - 1
If target > mid → Move low = mid + 1
If not found → return -1 ❌

🧑‍💻 Code Time! (C++)

int binarySearch(vector<string>& arr, string target) {
    int low = 0, high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1; // Not Found
}

💡 Quick Recap:
✅ Binary Search works only on sorted arrays
Cut the search space in half every time
⚡ Time Complexity: O(log n)
🚀 Way faster than Linear Search!
Real-World Analogy:
Imagine finding a name in a phone book 📖
Do you start from page 1?
Nope! You flip to the middle 📖 → Then go left or right!
That’s Binary Search 💡

💬 Wrapping Up
Binary Search is like Sherlock Holmes — it doesn’t check everything, it thinks, splits, and finds smartly!
So next time you’re searching something in a sorted list —
Don't be slow… go Binary! 🧠

🔍Linear Search Made Easy – Find Like a Detective!

Khushi — Fri, 11 Apr 2025 13:09:39 +0000

🍫 A Chocolate Hunt Story
Imagine you're hungry (like really hungry 😋) and craving your favorite chocolate...
You open your snack box, and here’s what you see:[KitKat, Dairy Milk, Munch, Perk, 5-Star]
Now, you don’t know where Dairy Milk is, so what do you do?
👉 Start checking one by one!
KitKat? → ❌ Nope
Dairy Milk? → ✅ Yesss! Found it

That's exactly what Linear Search does in coding too!
🧠 What is Linear Search?
Linear Search is like going through each item one-by-one until you find the one you want.
No shortcuts. No tricks. Just pure checking — start to end! 🚶‍♀️

💡Real Example :
Let's say you have:
arr = [10, 25, 30, 45, 50]
target = 30

We want to find the number 30.
Let’s dry run this:

📢 Result: Found at index 2.

❓ What if it’s not there?
arr = [10, 25, 30, 45, 50]
target = 100

We check all… and nope! It’s not there
👉 In that case, we return -1 (means "Not Found").

📌 Simple Steps to Remember:

Start from the first item
Check: Is this the one?
If yes → 🎉 return the index!
If not → move to next
Repeat until: You find the item ✔️ Or reach the end ❌ (return -1)

🧑‍💻Code Time! (C++)

#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Found!
        }
    }
    return -1; // Not found
}
int main() {
    int chocoBox[] = {4, 8, 15, 23, 42};
    int size = sizeof(chocoBox) / sizeof(chocoBox[0]);
    int myFavorite = 23;
     int result = linearSearch(chocoBox, size, myFavorite);
     if (result != -1)
       cout << "Yay! Found your favorite chocolate at position: " << result;
    else
        cout << "Oops! Your chocolate isn't in the box!" << endl;
        return 0;
}

🖥️ Output :Yay! Found your favorite chocolate at position: 3

💬 Wrapping Up
Linear Search = The simplest way to find something — one step at a time.
No rocket science. Just like finding your Dairy Milk 🍫 in a snack box!
Want more fun DSA stuff like this daily?
✨ Follow me — I’m Khushi, a fellow learner sharing daily bite-sized DSA logic, patterns & stories 💛
Let’s learn & grow together 🚀

Let’s Solve DSA Together – With Khushi! 🎯

Khushi — Thu, 10 Apr 2025 17:53:47 +0000

Hey awesome minds! 👋
I’m Khushi — a fellow learner on this wild ride called DSA 🚀
And guess what? I’m not a pro (yet 😉), but I believe DSA becomes fun when we solve it together. So I’m starting this series where…

👉 We crack logic together, like teammates
👉 We grow, one bug at a time 🐞
🧩 Why “DSA with Khushi”?
Because Khushi means joy — and I want to bring joy to problem solving 💛
No boring explanations. Just clear logic, real learning, and a pinch of fun.
Let’s skip the stress and high-fives the success!
💡 What’s Coming?
🔍 1 Pattern a Day (with real problems)
✨ Explained simply (no rocket science!)
🤝 Solve-along style — you + me + logic!
🔄 Practice = Progress = Confidence!

So if you’re learning DSA too, come join me!
Let’s make this our logic ritual 🧠
Drop a 💥 if you're in — and see you in the next post where we’ll start with our first DSA pattern!