Graph

 graph is non linear ds. it consisting of vertices and edges.

it denote by G(V,E) 

types

null graph ( graph have no edges)

trival graph ( have only one vertex)

undirected graph

directed graph

connected graph

disconnected graph

regular graph

complete graph(there is an edge to each other node)

cycle graph

cyclic graph(graph have at least one cycle ) 

directed Acyclic graph(directed graph not contain any cycle)

bipartite graph

weighted graph

 

Representation of graph ds

 => adjacency matrix

=> adjacency list 

 

Binary Tree Data Structure

 > organize the data in hierarchical structure.

 

 

 

types of Binary Tree in Data Structure

 

    > Full Binary Tree

 

         A full binary tree is a tree where every node has either 0 or 2 children.

 

> Complete Binary Tree

   A complete binary tree is a tree where all levels are fully filled except possibly the last level, which is filled from left to right. 

 

 >Perfect Binary Tree

     A perfect binary tree is a tree where all internal nodes have exactly two children and all leaf nodes are at the same level.

   

> 

• Balanced Binary Tree

A balanced binary tree is a tree where the height of the left and right subtrees of any node differ by at most one.

 

• Degenerate (or Pathological) Binary Tree

A degenerate binary tree is a tree where each parent node has only one child. This makes the tree look like a linked list.

 

 

 

 

 

 

 

aug - 4

 import java.util.*;

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] job = new int[n][3];
        for(int i = 0; i < n; i++){
            job[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }

        Arrays.sort(job, Comparator.comparingInt(a -> a[1]));

        int[] dp = new int[n];
        dp[0] = job[0][2];

        for(int i = 1; i < n; i++){
            int includeProfit = job[i][2];
            int l = binarySearch(job, i);

            if(l != -1){
                includeProfit += dp[l];  // ✅ FIXED
            }

            dp[i] = Math.max(dp[i - 1], includeProfit);
        }

        return dp[n - 1];
    }

    private int binarySearch(int[][] job, int index){
        int l = 0, h = index - 1;
        int res = -1;

        while(l <= h){
            int mid = l + (h - l) / 2;
            if(job[mid][1] <= job[index][0]){
                res = mid;
                l = mid + 1;
            } else {
                h = mid - 1;
            }
        }

        return res;
    }
}

INTRO OF DS AND ALGO

🧱 DATA STRUCTURES – "How data is organized"

Core Goal: Efficiently store, access, and manipulate data.

 

Category	Concepts You Must Master	Real-Life Analogy
Array	Indexing, Iteration, Static size	Shelf with fixed compartments
Linked List	Nodes, Pointers, Dynamic size	Train cars linked together
Stack	LIFO, Push/Pop	Plates stacked in a cafeteria
Queue	FIFO, Enqueue/Dequeue	Waiting line at a ticket counter
Hash Map / Hash Table	Key-value pairs, Hash functions	Dictionary
Tree	Hierarchy, Traversals (DFS, BFS)	Family tree
Binary Search Tree (BST)	Ordered nodes, Search in O(log n)	Sorted filing system
Heap (Min/Max)	Priority Queue, Top-K	Task manager prioritizing  processes
Trie	Prefix tree, String search	Phonebook with prefix-based lookup
Graph	Nodes + Edges, Directed/Undirected	Road map or social network