IIT-JEE Computer Science Exam Prep

JEE Pattern: 1-2 questions on arrays, linked lists, and memory concepts. Focus on implementation and tradeoffs.

// Array vs Linked List
Array (Static):
- Access: O(1) direct indexing arr[i]
- Insert/Delete: O(n) requires shifting
- Memory: Contiguous block, cache-friendly
- Use: When frequent access needed

Linked List (Dynamic):
- Access: O(n) must traverse
- Insert/Delete: O(1) if position known, else O(n)
- Memory: Scattered, pointer overhead (8-16 bytes per node)
- Use: When frequent insertions/deletions needed

// Stack (LIFO)
Array-based: O(1) push, pop; O(n) space
Operations: push(x), pop(), peek(), isEmpty()
Use: Function calls, undo-redo, bracket matching

// Queue (FIFO)
Array-based (circular): O(1) enqueue, dequeue
Operations: enqueue(x), dequeue(), front(), isEmpty()
Use: BFS, task scheduling, printer queue

// Deque (Double-ended)
Allows insertion/deletion from both ends: O(1)
Use: Sliding window problems, A* algorithm

Key Exam Focus: Analyzing Big-O, comparing algorithms, recognizing patterns in code.

// Big-O Notation (Worst Case)
O(1):      Constant   - array access, hash lookup
O(log n):  Logarithmic - binary search, balanced tree
O(n):      Linear     - simple loop, linear search
O(n log n): - merge sort, quick sort average
O(n²):     Quadratic  - nested loops, bubble sort
O(2ⁿ):     Exponential - recursion without memoization
O(n!):     Factorial  - permutations

// Space Complexity (Extra space, not input)
Recursive Fibonacci: O(2ⁿ) time, O(n) stack space
Merge Sort: O(n log n) time, O(n) extra space
Quick Sort: O(n log n) average, O(log n) stack space
Hash Table: O(n) space for n elements

// Master Theorem (for divide & conquer)
T(n) = aT(n/b) + f(n)
1. If f(n) = O(n^(log_b(a) - ε)): T(n) = O(n^log_b(a))
2. If f(n) = Θ(n^log_b(a)): T(n) = O(n^log_b(a) × log n)
3. If f(n) = Ω(n^(log_b(a) + ε)): T(n) = O(f(n))

Example: Merge Sort
a=2, b=2, f(n)=n
log_b(a) = log₂(2) = 1
f(n) = n = Θ(n^1) → Case 2
T(n) = O(n log n)

JEE asks 2-3 questions: Simplification, gate combinations, De Morgan's laws, XOR/XNOR patterns.

// Basic Operations
AND (·):  1·1=1, 1·0=0, 0·0=0
OR (+):   1+1=1, 1+0=1, 0+0=0
NOT ('):  1'=0, 0'=1
XOR (⊕):  1⊕1=0, 1⊕0=1, 0⊕0=0 (different=1)
XNOR (⊙): 1⊙1=1, 1⊙0=0, 0⊙0=1 (same=1)

// De Morgan's Laws (CRITICAL)
(A·B)' = A' + B'
(A+B)' = A'·B'
Proof by truth table always works!

// Boolean Identities
A + 0 = A           (OR with 0)
A · 1 = A           (AND with 1)
A + A = A           (Idempotent)
A · A = A
A + A' = 1          (Complement)
A · A' = 0
A + 1 = 1           (Domination)
A · 0 = 0
A + (B+C) = (A+B)+C (Associative)
A · (B·C) = (A·B)·C
A·B + A·C = A·(B+C) (Distributive)

// Common Patterns
Even parity check: A ⊕ B ⊕ C (odd 1s → 1)
Odd parity check:  A ⊙ B ⊙ C (even 1s → 1)
Majority gate: AB + BC + AC (2+ of 3 are 1)

Exam Pattern: 1-2 questions on binary/hex conversion, floating point representation, two's complement.

// Base Conversion
Decimal to Binary: Repeated division by 2
13 (dec) = 1101 (bin)   [8+4+1]

Binary to Decimal: Sum of 2^position
1101 = 1·2³ + 1·2² + 0·2¹ + 1·2⁰ = 13

Hex <-> Binary: Direct (4 bits per hex digit)
A3F (hex) = 1010 0011 1111 (bin)
A=10=1010, 3=0011, F=15=1111

Octal <-> Binary: Direct (3 bits per octal digit)
723 (oct) = 111 010 011 (bin)
7=111, 2=010, 3=011

// Two's Complement (signed integers)
Positive: Normal binary (sign bit = 0)
Negative: Invert bits + add 1
Example (8-bit):
5 = 0000 0101
-5: Invert→1111 1010, Add 1→1111 1011

Range for n-bit: -2^(n-1) to 2^(n-1) - 1
8-bit: -128 to 127
16-bit: -32768 to 32767

// Floating Point (IEEE 754)
32-bit: Sign(1) | Exponent(8) | Mantissa(23)
64-bit: Sign(1) | Exponent(11) | Mantissa(52)
Value = (-1)^sign × 1.mantissa × 2^(exponent-bias)
Bias for 32-bit = 127, for 64-bit = 1023

JEE Favorite: Compare efficiency, trace execution, identify algorithm from pseudocode.

Algorithm	Best	Average	Worst	Space	Stable	Notes
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Easiest, slowest
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	Minimal writes
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Good for nearly sorted
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Always fast, extra space
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Usually fastest, in-place
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Guaranteed fast
Binary Search	O(log n)			O(1)	-	Must be sorted!

// Quick Sort Pattern (Divide & Conquer)
Choose pivot, partition into smaller/larger
Recursively sort partitions
Average: O(n log n), Worst: O(n²) if pivot always min/max

// Merge Sort (Always O(n log n))
Divide array into halves
Recursively merge sorted halves
Stable, requires O(n) extra space

// Binary Search (must be sorted)
while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: left = mid + 1
    else: right = mid - 1
Time: O(log n)

Critical for JEE: DFS/BFS, shortest paths, spanning trees. 1-2 questions typical.

// Graph Representations
Adjacency Matrix: 2D array, O(V²) space, O(1) edge check
Adjacency List: For each vertex, list of neighbors
    Sparse graphs: O(V+E) space
    Dense graphs: Still O(V²) in worst case

// Depth-First Search (DFS)
def dfs(vertex, visited, graph):
    visited[vertex] = True
    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            dfs(neighbor, visited, graph)

Time: O(V+E), Space: O(V) recursion stack
Use: Topological sort, cycle detection, connected components

// Breadth-First Search (BFS)
from collections import deque
def bfs(start, graph):
    visited = set([start])
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Time: O(V+E), Space: O(V)
Use: Shortest path (unweighted), level-order traversal

// Shortest Path (Dijkstra for weighted)
Use priority queue, always visit nearest unvisited
dist[start] = 0, dist[others] = ∞
Time: O((V+E) log V) with min-heap

// Minimum Spanning Tree (Kruskal)
Sort edges by weight
Use Union-Find to avoid cycles
Add edge if connects different components
Time: O(E log E)

JEE heavily tests: Recursion traces, identifying DP problems, memoization vs tabulation.

// Recursion Pattern
def recur(n):
    if n == 0: return base_case  # Base case!
    return f(n) + recur(n-1)

// Fibonacci (overlapping subproblems!)
Naive: O(2^n) - exponential
fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)
fib(3) calculated twice! (redundant work)

// Memoization (Top-Down DP)
memo = {}
def fib(n):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
Time: O(n), Space: O(n)

// Tabulation (Bottom-Up DP)
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
Time: O(n), Space: O(n)

// Classic DP Problems (JEE asks variants)
1. Fibonacci: dp[i] = dp[i-1] + dp[i-2]
2. Coin Change: dp[i] = min(dp[i], dp[i-coin]+1)
3. LCS (Longest Common Subsequence):
   if s1[i]==s2[j]: dp[i][j] = dp[i-1][j-1] + 1
   else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. Knapsack: dp[w] = max(dp[w], dp[w-weight]+value)
5. Edit Distance: Levenshtein distance with DP

Exam focuses on: List operations, string manipulation, nested loops, simple algorithms.

// Common JEE Patterns in Python

# 1. Finding max/min in list
arr = [3, 1, 4, 1, 5, 9]
max_val = max(arr)  # 9
min_val = min(arr)  # 1
index_of_max = arr.index(max(arr))  # 4

# 2. Counting occurrences
count = arr.count(1)  # 2
from collections import Counter
freq = Counter(arr)  # {1: 2, 3: 1, 4: 1, ...}

# 3. String reversal & palindrome
s = "hello"
s_rev = s[::-1]  # "olleh"
is_palindrome = s == s[::-1]

# 4. Two-pointer technique
left, right = 0, len(arr)-1
while left < right:
    swap(arr[left], arr[right])
    left += 1
    right -= 1

# 5. Nested loop patterns
for i in range(n):
    for j in range(n):
        # O(n²) - matrix operations

# 6. List slicing
arr[start:end:step]  # subarray from start to end-1, every step
arr[::2]  # every 2nd element
arr[::-1]  # reverse

# 7. Lambda for sorting
students = [("Alice", 85), ("Bob", 92), ("Carol", 78)]
sorted_by_score = sorted(students, key=lambda x: x[1], reverse=True)

# 8. Set operations
set1 = {1, 2, 3}
set2 = {2, 3, 4}
union = set1 | set2  # {1,2,3,4}
intersection = set1 & set2  # {2,3}
difference = set1 - set2  # {1}

Formulas that appear in JEE CS questions:

// Time Complexity Reference
T(n) = O(f(n)) means there exist c, n₀ such that
T(n) ≤ c × f(n) for all n > n₀

// Array & String
Length: n elements, indexed 0 to n-1
Subsequence: any subset preserving order (2^n possible)
Substring: contiguous, n(n+1)/2 possible
Permutation: n! arrangements

// Tree Formulas
Complete binary tree with n levels: 2^n - 1 nodes
Height h binary tree: min 2^h nodes, max 2^(h+1) - 1 nodes
Binary search tree: best O(log n), worst O(n)

// Graph Formulas
Simple graph V vertices: max V(V-1)/2 edges (complete)
Tree: V-1 edges, stays connected
Bipartite: chromatic number = 2
Planar graph: E ≤ 3V - 6

// Recursion Depth
Fibonacci naive: exponential 2^n
Factorial: linear n calls
Tree traversal: log n (balanced) to n (skewed)

// Hashing
Load factor λ = n/m (n items, m slots)
Linear probing: O(1/(1-λ)) average
Chaining: O(1 + λ) average

// Sorting Comparisons
Bubble: n(n-1)/2 comparisons worst case
Merge: n log₂(n) comparisons exactly
Quick: best n log₂(n), worst n(n-1)/2