DCRUST DSA Unit I Cheatsheet

Cheatsheet Content

🚀 Unit I: Foundations of Data Structures & Algorithms 1. Algorithm Basics & Asymptotic Analysis (O, Ω, Θ) Concept Intuition: Algorithm matlab ek problem ko solve karne ka step-by-step procedure. Jaise ghar banane ka blueprint, waise hi software banane ka blueprint algorithm hai. Iski efficiency ko measure karna zaroori hai. Real-life Analogy: Imagine aapko Delhi se Mumbai jaana hai. Aapke paas multiple options hain: flight, train, bus, ya cycle. Har option ka apna time (efficiency) aur cost (space) hai. Algorithm analysis bhi yahi karta hai—best option dhundhna. Algorithm Properties: Input: Zero ya more well-defined inputs. Output: At least ek well-defined output. Definiteness: Har step unambiguous aur clear hona chahiye. Finiteness: Algorithm finite number of steps mein terminate hona chahiye. Effectiveness: Har step basic operations mein break ho sake, jo practically performable ho. Asymptotic Notations: Efficiency ka Scale! Exam Pattern Alert (DCRUST): "Explain Big-O, Omega, and Theta notations with examples." (2020, 2022). Direct question aata hai, definitions aur graphical representation must hai. a) Big O Notation ($O$) - Upper Bound (Worst Case) Concept Intuition: Ye batata hai ki worst case mein aapka algorithm kitna time lega. "It will *at most* take this much time." Definition: $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$. Real-life Analogy: Aapne friend ko bola "Main tumhe 1 ghante mein milunga." Matlab, worst case mein 1 ghanta lagega, ho sakta hai 30 min mein hi pahunch jao. The 1-hour is your upper bound. Diagram: n Time $f(n)$ $c \cdot g(n)$ $n_0$ Common Mistakes: Sirf worst case ko hi Big O samajhna, average case ko ignore karna. Big O sirf growth rate batata hai, actual time nahi. b) Omega Notation ($\Omega$) - Lower Bound (Best Case) Concept Intuition: Ye batata hai ki best case mein aapka algorithm *at least* kitna time lega. "It will *at least* take this much time." Definition: $f(n) = \Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$. Real-life Analogy: Friend ne bola "Main tumhe 10 min se pehle nahi milunga." Matlab, best case mein 10 min lagenge, ho sakta hai 30 min lage. The 10-min is your lower bound. Diagram: n Time $f(n)$ $c \cdot g(n)$ $n_0$ c) Theta Notation ($\Theta$) - Tight Bound (Average Case) Concept Intuition: Ye batata hai ki average case mein aapka algorithm kitna time lega. "It will *approximately* take this much time." Ye Big O aur Omega ka combination hai. Definition: $f(n) = \Theta(g(n))$ if there exist positive constants $c_1, c_2$ and $n_0$ such that $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$. Real-life Analogy: Friend ne bola "Main tumhe 10 se 15 min ke beech milunga." Matlab, time bound hai, na bahut kam na bahut zyada. Diagram: n Time $f(n)$ $c_1 \cdot g(n)$ $c_2 \cdot g(n)$ $n_0$ Micro Revision Box: Notation Meaning Analogy $O$ (Big O) Upper Bound (Worst) At most 'X' min $\Omega$ (Omega) Lower Bound (Best) At least 'Y' min $\Theta$ (Theta) Tight Bound (Average) Between 'Y' and 'X' min 2. Abstract Data Types (ADT) Concept Intuition: ADT matlab "What it does" not "How it does it". Yeh ek blueprint hai, ek conceptual model. Jaise ek remote control – aapko sirf buttons ka function pata hai, andar kya circuit hai woh nahi pata. Real-life Analogy: Ek TV remote. Aapko pata hai power button dabane se TV on/off hota hai, volume buttons se sound control hota hai. Aapko internal wiring, chipset ya programming ki details nahi chahiye. Remote ek ADT hai for TV control. Definition: An ADT is a mathematical model for data types where behavior is defined by a set of values and a set of operations. It specifies *what* operations can be performed, but not *how* they are implemented. Data: Values jo store honge. Operations: Functions jo data par perform kiye ja sakte hain (e.g., add, delete, search). Examples: Stack, Queue, List, Tree, Graph are all ADTs. Jab hum inko particular language mein implement karte hain (e.g., C++ mein array use karke stack banana), tab woh Data Structure ban jaate hain. Memory Map: ADT $\rightarrow$ Specification (What) $\rightarrow$ Interface. Data Structure $\rightarrow$ Implementation (How) $\rightarrow$ Concrete. Predictive Exam Question: "Differentiate between Abstract Data Type and Data Structure with suitable examples." 3. Arrays (1D, 2D, 3D) & Address Calculation Concept Intuition: Array matlab ek hi type ke data items ka collection, jo memory mein contiguous (ek ke baad ek) store hote hain. Jaise ek library mein books ek row mein rakhi hoti hain, har book ka ek index hota hai. Real-life Analogy: Ek apartment building jisme saare flats ek hi size ke hain aur unka number 0 se shuru hota hai. Aapko kisi bhi flat ka address pata karna hai toh bas uska number (index) pata hona chahiye, aur pehle flat ka address (base address). a) 1D Array (Vector) Declaration: int arr[5]; Elements: $arr[0], arr[1], arr[2], arr[3], arr[4]$ Address Calculation: `Address of A[i] = Base\_Address + (i - Lower\_Bound) * Size_of_Element` Agar $LB=0$, toh `Address of A[i] = Base_Address + i * Size_of_Element` Example: $Base\_Address = 1000$, $Size = 4$ bytes (for int). $A[3]$ ka address: $1000 + 3 * 4 = 1012$. b) 2D Array (Matrix) Concept Intuition: Rows aur Columns mein arrange kiya hua data. Jaise spreadsheet ya chess board. Declaration: int arr[3][4]; (3 rows, 4 columns) Past-year link (DCRUST Trends): "Derive the formula for row-major and column-major address calculation for a 2D array." (2018, 2021, 2023). This is a guaranteed question! i) Row-Major Order (Default in C/C++) Memory Map: Rows are stored contiguously. Pehle poori Row 0, phir poori Row 1, and so on. Golden Formula: Address of A[i][j] = Base_Address + [(i - R_LB) * Number_of_Columns + (j - C_LB)] * Size_of_Element Agar $R\_LB=0, C\_LB=0$: Address of A[i][j] = Base_Address + [i * Number_of_Columns + j] * Size_of_Element Example: $A[3][4]$ (3 rows, 4 cols). Find $A[1][2]$. $Base\_Address=1000$, $Size=4$. $Address = 1000 + [1 * 4 + 2] * 4 = 1000 + [4+2]*4 = 1000 + 6*4 = 1000 + 24 = 1024$. ii) Column-Major Order (Default in Fortran) Memory Map: Columns are stored contiguously. Pehle poora Column 0, phir poora Column 1, and so on. Golden Formula: Address of A[i][j] = Base_Address + [(j - C_LB) * Number_of_Rows + (i - R_LB)] * Size_of_Element Agar $R\_LB=0, C\_LB=0$: Address of A[i][j] = Base_Address + [j * Number_of_Rows + i] * Size_of_Element Example: $A[3][4]$ (3 rows, 4 cols). Find $A[1][2]$. $Base\_Address=1000$, $Size=4$. $Address = 1000 + [2 * 3 + 1] * 4 = 1000 + [6+1]*4 = 1000 + 7*4 = 1000 + 28 = 1028$. c) 3D Array Concept Intuition: Multiple 2D arrays (planes) stacked together. Jaise Rubik's Cube. Declaration: int arr[D1][D2][D3]; (D1 planes, D2 rows, D3 columns) Golden Formula (Row-Major): Address of A[i][j][k] = Base_Address + [(i * D2 * D3) + (j * D3) + k] * Size_of_Element (assuming $LB=0$ for all dimensions) Common Mistakes: Row-major aur Column-major formulas mein $Number\_of\_Rows$ aur $Number\_of\_Columns$ ko interchange karna. Always remember: Row-major mein row index 'i' pehle multiply hota hai $Number\_of\_Cols$ se, Column-major mein column index 'j' pehle multiply hota hai $Number\_of\_Rows$ se. Micro Revision Box: Array Type Formula (0-indexed) 1D: $A[N]$ $BA + i \cdot S$ 2D (Row-Major): $A[R][C]$ $BA + (i \cdot C + j) \cdot S$ 2D (Col-Major): $A[R][C]$ $BA + (j \cdot R + i) \cdot S$ 3D (Row-Major): $A[D_1][D_2][D_3]$ $BA + (i \cdot D_2 \cdot D_3 + j \cdot D_3 + k) \cdot S$ 4. Sparse Matrix Representation & Transpose Concept Intuition: Sparse matrix woh matrix hoti hai jisme zero elements non-zero elements se bahut zyada hote hain. Agar hum poori matrix store karein, toh bahut memory waste hogi. Isliye, hum sirf non-zero elements ko store karte hain. Real-life Analogy: Ek class mein 100 students hain, lekin sirf 5 students ne project submit kiya hai. Agar hum sabhi 100 students ke project status ko store karein (95 times 'Not Submitted'), toh waste of space hai. Better hai ki sirf un 5 students ka naam aur 'Submitted' status store karein. Representation Methods: a) Triplets (Row, Column, Value) Most common method. Har non-zero element ko ek triplet $(Row, Column, Value)$ ke roop mein store karte hain. Ek 2D array use karte hain, jisme first row matrix ki dimensions aur non-zero count store karta hai. Example: Original Matrix (3x3): 0 0 5 0 8 0 1 0 0 Triplet Representation: Row Col Value 3 3 3 (Matrix dimensions & non-zero count) 0 2 5 1 1 8 2 0 1 Memory Map: $(Row, Col, Value)$ for each non-zero element. Space complexity: $O(N_{non-zero})$. b) Linked List Representation Har non-zero element ke liye ek node banate hain jisme row, col, value store karte hain. Rows ya Columns ke according linked lists maintain ki ja sakti hain. Zyada complex, but dynamic memory allocation ka fayda. Sparse Matrix Transpose Concept Intuition: Transpose matlab rows ko columns aur columns ko rows mein badalna. $(Row, Col, Value)$ triplet $(Col, Row, Value)$ ban jaata hai. Algorithm (Using Triplets): Original sparse matrix (triplet form) ko read karo. Ek naya triplet array banao transpose ke liye. Original matrix ke dimensions ko swap karo (rows becomes cols, cols becomes rows) aur new total non-zero elements ko first row mein daalo. Original matrix ke har $(r, c, v)$ triplet ke liye, naye array mein $(c, r, v)$ store karo. Isme problem ye hai ki final transpose sorted order mein nahi hoga (by row then col). Efficient Transpose (Fast Transpose Algorithm): Exam Pattern Alert (DCRUST): "Explain sparse matrix representation and write an algorithm for its fast transpose." (2019, 2022). This implies you need the fast transpose, not just naive one. Count number of elements in each column of original matrix ( col_counts ). Calculate starting position of each column in the transposed matrix ( col_starts ). `col_starts[0] = 1` (assuming 1-based indexing for data rows) `col_starts[j] = col_starts[j-1] + col_counts[j-1]` Iterate through original matrix triplets: for each $(r, c, v)$: Place $(c, r, v)$ into the transpose matrix at index `col_starts[c]`. Increment `col_starts[c]` to point to the next available slot for that column. Diagram: Visualize `col_counts` array and `col_starts` array facilitating direct placement. Common Mistakes: Naive transpose algorithm use karna instead of fast transpose for exam. Forgetting to swap dimensions in the header row of the transpose matrix. 5. Linked Lists (SLL, DLL, CLL) Concept Intuition: Array mein elements contiguous hote hain, linked list mein scattered. Har element (node) apne next element ka address store karta hai. Jaise ek treasure hunt – ek clue aapko next clue ki location batata hai. Real-life Analogy: Train compartments. Har compartment apne next compartment se juda hota hai. Agar beech mein se ek compartment nikalna hai, toh bas previous compartment ka next pointer update karna hai. a) Singly Linked List (SLL) Structure: `data` aur `next` pointer. Traversal: `head` se shuru karke `next` pointers follow karte hain jab tak `NULL` na mile. Operations: Insertion: Beginning, End, After a specific node. Deletion: Beginning, End, Specific node. Diagram (SLL Node): Data Next Golden Formula (Insertion at Beginning): new_node->next = head; head = new_node; Golden Formula (Deletion at Beginning): temp = head; head = head->next; free(temp); b) Doubly Linked List (DLL) Structure: `data`, `next` pointer, aur `prev` pointer. Advantage: Bidirectional traversal possible. Disadvantage: More memory per node, slightly complex operations. Diagram (DLL Node): Prev Data Next c) Circular Linked List (CLL) Structure: Last node ka `next` pointer `NULL` hone ki bajaye `head` ko point karta hai. Advantage: Traversal from any point, no `NULL` checks, useful for round-robin scheduling. Disadvantage: Infinite loop risk if traversal condition not handled carefully. Diagram (CLL): N1 N2 N3 to Head Common Mistakes: Linked lists mein `NULL` check karna bhool jaana, memory leaks (free na karna), `head` pointer ko update na karna. Micro Revision Box: List Type Structure Traversal Pros Cons Singly Data, Next Forward Simple, less memory No backward, find prev is slow Doubly Data, Prev, Next Forward/Backward Flexible More memory, complex ops Circular Data, Next (last points to head) Continuous No NULL, round-robin Careful with loops 6. Polynomial Addition Using Linked List Concept Intuition: Polynomials ($3x^2 + 2x + 5$) ko linked list se represent karna ek smart tareeka hai, especially jab polynomials mein bahut saare terms missing hon (sparse polynomials). Har term $(coefficient, exponent)$ ko ek node mein store karte hain. Real-life Analogy: Recipe book mein ingredients ki list. Agar aapke paas 2 recipes hain aur unko combine karna hai, toh aap same ingredients ko add karte ho. Polynomial addition bhi similar hai, same exponent wale terms ko add karte hain. Node Structure: struct Node { int coeff; // Coefficient of the term int exp; // Exponent of the term struct Node* next; }; Algorithm for Addition: Exam Pattern Alert (DCRUST): "Implement polynomial addition using linked list with a suitable example." (2017, 2021, 2023). This is a highly repeated practical question! Do input polynomials ko linked lists $P1$ aur $P2$ ke roop mein assume karo, terms descending order of exponents mein sorted hone chahiye. Ek empty linked list $Result$ banao. $P1$ aur $P2$ ke head pointers ko traverse karo: If $P1 \rightarrow exp == P2 \rightarrow exp$: Terms add karo, naya node $Result$ mein add karo, dono pointers aage badhao. If $P1 \rightarrow exp > P2 \rightarrow exp$: $P1$ ka term $Result$ mein add karo, $P1$ pointer aage badhao. If $P1 \rightarrow exp Jab ek list khatam ho jaaye, toh doosri list ke remaining terms ko $Result$ mein copy kar do. Example Walkthrough: $P1 = 5x^2 + 4x^1 + 2x^0 \implies (5,2) \rightarrow (4,1) \rightarrow (2,0)$ $P2 = 3x^2 + 2x^0 \implies (3,2) \rightarrow (2,0)$ Steps: 1. P1(5,2), P2(3,2): exp same (2). Add coeffs (5+3=8). Add (8,2) to Result. P1 moves to (4,1), P2 moves to (2,0). Result: (8,2) 2. P1(4,1), P2(2,0): P1.exp (1) > P2.exp (0). Add P1's term (4,1) to Result. P1 moves to (2,0). Result: (8,2) -> (4,1) 3. P1(2,0), P2(2,0): exp same (0). Add coeffs (2+2=4). Add (4,0) to Result. P1 becomes NULL, P2 becomes NULL. Result: (8,2) -> (4,1) -> (4,0) 4. Both lists exhausted. Final Result: $8x^2 + 4x^1 + 4x^0$ Common Mistakes: Exponents ko descending order mein sort na karna. Same exponent wale terms ko add na karna. Remaining terms ko handle na karna jab ek list pehle khatam ho jaaye. Predictive Exam Question: "Write a C/C++ program to perform polynomial addition using linked lists. Explain your node structure and the addition logic." Micro Revision Box: Node: `(coeff, exp, next)` Assumption: Polynomials are sorted by `exp` (descending). Logic: Compare exponents, add if same, append if different.