Brute force — exhaustive search, when acceptable: Exercises

3.7.1 · D4 · Coding › Algorithm Paradigms › Brute force — exhaustive search, when acceptable

Shuru karne se pehle, yeh mental picture hai jo hum baar baar use karte hain — poora game candidates ke pile ka size count karna hai, phir poochna ki pile itni choti hai ki usse walk-through kiya ja sake.

Figure — Brute force — exhaustive search, when acceptable

Level 1 — Recognition

Goal: ek constraint padho aur search-space size + verdict batao. Koi coding nahi.

Exercise 1.1

Ek problem kehti hai: " $n \leq 22$ items diye hain, har subset consider karo." Kitne subsets hain, aur kya brute force $1 0^{8}$ ke andar fit hoga?

Recall Solution 1.1

KYA count karte hain: har subset. KYUN $2^{n}$ : $n$ items mein se har ek independently in ya out hai — yeh $2$ choices hain, $n$ baar li jaati hain, isliye $n 2 \cdot 2 \dots 2 = 2^{n}$ . $n = 22$ ke saath: $2^{22} = 4194304 \approx 4.19 \times 1 0^{6}$ . Kyunki $4.19 \times 1 0^{6} < 1 0^{8}$ , brute force theek hai (chaahe har subset par thoda extra cost bhi ho).

Exercise 1.2

Ek problem mein $n \leq 12$ hai aur yeh items ki har ordering (permutation) try karne ko kehti hai. Size? Verdict?

Recall Solution 1.2

KYUN $n!$ : pehle slot mein $n$ choices hain, agle mein $n - 1$ (ek item use ho gayi), aur aise neeche $1$ tak. Multiply karo: $n \cdot (n - 1) \dots 1 = n!$ . $12! = 479001600 \approx 4.79 \times 1 0^{8}$ . Yeh $1 0^{8}$ se upar hai. Isliye seedha permutation brute force borderline-to-risky hai — likely bahut slow hoga jab tak verification trivial na ho aur constants bahut chote na hon. Yahaan pruning (backtracking) ya DP prefer karo.

Exercise 1.3

" $n \leq 5000$ mein koi bhi do indices $i < j$ dhundho jahan $a_{i} + a_{j} = t$ ho." Kaun si enumeration, kya size, verdict?

Recall Solution 1.3

KYA: saare unordered distinct pairs enumerate karo. KYUN $(2 n)$ : slot 1 chuno ( $n$ ways) aur slot 2 ( $n - 1$ ways), phir $2$ se divide karo kyunki $(i, j)$ aur $(j, i)$ same pair hai: $\frac{n ( n - 1 )}{2}$ . $n = 5000$ : $\frac{5000 \cdot 4999}{2} = 12497500 \approx 1.25 \times 1 0^{7} < 1 0^{8}$ . Brute force OK.

Level 2 — Application

Goal: enumeration loop / mask likho aur uska cost count karo.

Exercise 2.1

Ek brute force likho jo saare index pairs $(i, j)$ , $i < j$ , return kare jahan $a_{i} + a_{j} = t$ ho. General $n$ ke liye exact pair-checks ka number batao.

Recall Solution 2.1

def all_pairs(a, t):
    n = len(a)
    out = []
    for i in range(n):              # first index
        for j in range(i+1, n):     # second index, strictly after i
            if a[i] + a[j] == t:
                out.append((i, j))
    return out

KYUN j ko i+1 se start karo: yeh $i < j$ enforce karta hai, isliye har unordered pair exactly ek baar visit hoti hai — na self-pairs, na duplicates. Checks ka number: inner loop $(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2} = (2 n)$ baar chalta hai. Yahi $Θ (n^{2})$ hai jo humne derive kiya. $n = 5$ ke liye yeh exactly $10$ checks hain.

Exercise 2.2

Bitmasks use karke count karo ki ${0, 1, 2, 3}$ ke kitne subsets ka sum $= 3$ hai. Masks dikhao.

Recall Solution 2.2

KYUN masks: ek number mask $0$ se $2^{4} - 1 = 15$ tak ek subset encode karta hai — bit $i$ set $\Leftrightarrow$ element $i$ chosen hai. Yeh $2^{4} = 16$ count realise karta hai. Subsets jinका sum $3$ hai:

${3}$ → mask $100 0_{2} = 8$ , sum $3$ ✓
${0, 3}$ → mask $100 1_{2} = 9$ , sum $0 + 3 = 3$ ✓
${1, 2}$ → mask $011 0_{2} = 6$ , sum $1 + 2 = 3$ ✓
${0, 1, 2}$ → mask $011 1_{2} = 7$ , sum $0 + 1 + 2 = 3$ ✓

Yeh 4 subsets hain. (Check: ${0, 1, 2, 3}$ ka koi aur combination $3$ total nahi karta.)

Exercise 2.3

Ek length-3 password lowercase letters $a$ – $z$ use karta hai. Worst case mein brute force ko kitne candidates try karne padenge? Kya yeh instant hai?

Recall Solution 2.3

KYUN $b^{k}$ : $k = 3$ positions mein se har ek size $b = 26$ ke alphabet se independently fill hoti hai, isliye $26 \times 26 \times 26 = 2 6^{3}$ . $2 6^{3} = 17576$ . Yeh $1 0^{8}$ se bahut neeche hai — practically instant. (Isliye hi 3-character passwords bekaar hote hain.)

Level 3 — Analysis

Goal: enumeration cost aur verify cost ko alag karo, aur totals ke baare mein reason karo.

Exercise 3.1

Ek brute force saare $2^{n}$ subsets enumerate karta hai, aur har subset ke liye $Θ (n)$ time spend karta hai bits scan karke weight compute karne mein. Total cost batao aur sabse bada $n$ jo $1 0^{8}$ ke andar rehta hai.

Recall Solution 3.1

Total cost $= (candidates) \times (verify each) = 2^{n} \cdot n$ . Hum chahte hain $2^{n} \cdot n \leq 1 0^{8}$ .

$n = 20$ : $2^{20} \cdot 20 = 1048576 \cdot 20 = 20971520 \approx 2.1 \times 1 0^{7}$ ✓
$n = 21$ : $2^{21} \cdot 21 = 2097152 \cdot 21 = 44040192 \approx 4.4 \times 1 0^{7}$ ✓
$n = 22$ : $2^{22} \cdot 22 = 4194304 \cdot 22 = 92274688 \approx 9.23 \times 1 0^{7}$ ✓ (just under)
$n = 23$ : $2^{23} \cdot 23 = 8388608 \cdot 23 = 192937984 \approx 1.93 \times 1 0^{8}$ ✗

Isliye sabse bada safe $n$ hai $22$ .

Exercise 3.2

Same problem ke do solutions: (A) brute force $O (2^{n})$ diye gaye bound $n = 18$ ke saath; (B) ek "clever" $O (n^{2})$ algorithm ek alag problem par jahan $n = 1 0^{5}$ . Kaun kam operations karta hai?

Recall Solution 3.2

(A): $2^{18} = 262144 \approx 2.6 \times 1 0^{5}$ .
(B): $(1 0^{5})^{2} = 1 0^{10}$ . (A) ~ $40000 \times$ kam operations karta hai. Moral: "exponential" automatically "polynomial" se slow nahi hota — input bound decide karta hai. Chhota $n$ exponential ko tame kar deta hai.

Exercise 3.3

Ek subset-sum brute force apna running best aise update karta hai:

best = max(best, val)   # <-- placed BEFORE the weight check
if wt <= W:
    pass

Kya galat hai, aur worst case mein yeh kya return karta hai?

Recall Solution 3.3

Bug: yeh subset ko score karta hai (max(best, val)) subset feasible hai yah confirm karne se pehle (wt <= W). Isliye yeh ek overweight, illegal subset ki value adopt kar sakta hai. Worst case: sabse bhaari, sabse zyada value wala subset — jo $W$ violate karta hai — jeet jaata hai, aur ek aisi value return hoti hai jo koi bhi legal packing achieve nahi kar sakta. Answer ek over-estimate hai. Fix: pehle constraint verify karo, phir score karo:

if wt <= W:
    best = max(best, val)

Level 4 — Synthesis

Goal: enumeration + pruning + feasibility decision ko ek complete plan mein combine karo.

Exercise 4.1

Knapsack-style: weights=[2,3,4,5], values=[3,4,5,6], cap W=5. Full subset enumeration se, max value dhundho jahan total weight $\leq 5$ ho. Reasoning dikhao.

Recall Solution 4.1

Saare $2^{4} = 16$ subsets enumerate karo; sirf woh rakho jinka weight $\leq 5$ ho; best value lo. Feasible subsets aur unka (weight, value):

${}$ → (0, 0)
${0}$ → (2, 3)
${1}$ → (3, 4)
${2}$ → (4, 5)
${3}$ → (5, 6)
${0, 1}$ → (5, 7) ← weight exactly 5, value 7
${0, 2}$ → (6, —) infeasible
saare bade subsets 5 exceed karte hain.

Best feasible value = 7, items $0$ aur $1$ lene se (weight $2 + 3 = 5$ , value $3 + 4 = 7$ ).

Exercise 4.2

Same knapsack $n = 40$ items ke saath solve karna hai. Pure brute force ko $2^{40} \cdot 40$ operations chahiye. Estimate karo, decide karo acceptable hai ya nahi, aur sahi paradigm batao.

Recall Solution 4.2

$2^{40} \approx 1.0995 \times 1 0^{12}$ , times $40 \approx 4.4 \times 1 0^{13}$ operations. Yeh $1 0^{8}$ budget se $\sim 440000 \times$ zyada hai — brute force se hopeless. Structure exist karta hai (overlapping subproblems / optimal substructure), isliye DP use karo: knapsack $O (nW)$ mein. Moderate $W$ ke saath yeh trivial hai. (Agar $n \leq 40$ hai par chota $W$ nahi, toh meet-in-the-middle via Bitmasking do halves of $2^{20}$ mein split karta hai.)

Exercise 4.3

Ek brute force design karo jo saare $n$ cities ek baar visit karne ka shortest route dhundhe (Travelling Salesman). Kya enumerate karte ho, size kya hai, aur kis $n$ ke liye acceptable hai?

Recall Solution 4.3

Enumerate: cities ki saari orderings (permutations); start city fix karo rotational duplicates khatam karne ke liye, jo $(n - 1)!$ tours deta hai. Verify: $n$ leg-distances sum karo, har ek $Θ (n)$ . Total $\approx (n - 1)! \cdot n = n!$ order of work.

$n = 10$ : $10! = 3628800 \approx 3.6 \times 1 0^{6}$ ✓ theek hai.
$n = 11$ : $11! = 39916800 \approx 4.0 \times 1 0^{7}$ ✓ abhi bhi OK.
$n = 12$ : $12! \approx 4.8 \times 1 0^{8}$ ✗ borderline/too slow.

TSP NP-hard hai, isliye ~ $n = 12$ se aage Bitmasking-DP (Held–Karp, $O (2^{n} n^{2})$ , ~ $n = 20$ tak acha) ya heuristics/Backtracking with pruning use karo.

Level 5 — Mastery

Goal: trade-offs judge karo aur sirf constraints se paradigm chuno.

Exercise 5.1

Har constraint ke liye, intended complexity batao aur kya brute force survive karta hai. $1 0^{8}$ rule se justify karo. (a) $n \leq 11$ (b) $n \leq 24$ , subsets (c) $n \leq 500$ (d) $n \leq 1 0^{5}$ .

Recall Solution 5.1

(a) $n \leq 11$ → $O (n!)$ ka hint; $11! \approx 4.0 \times 1 0^{7} < 1 0^{8}$ → brute force (permutations) OK. (b) $n \leq 24$ , subsets → $2^{24} = 16777216 \approx 1.68 \times 1 0^{7}$ ; $\times 24$ bhi $\approx 4.0 \times 1 0^{8}$ hai (thoda over), isliye plain $O (2^{n})$ OK, $O (2^{n} \cdot n)$ borderline — agar verify heavy hai toh meet-in-the-middle use karo. (c) $n \leq 500$ → $O (n^{3}) = 1.25 \times 1 0^{8}$ ; borderline par usually light constants ke saath acceptable. (d) $n \leq 1 0^{5}$ → $O (n^{2}) = 1 0^{10}$ ✗; brute force mar jaata hai. Target $O (n lo g n) \approx 1.7 \times 1 0^{6}$ ✓.

Exercise 5.2

Ek judge $n \leq 20$ deta hai aur best subset kisi constraint ke under maangta hai, bit tricks hint karta hua. Kaun se do paradigms dono viable hain, aur kaise choose karo?

Recall Solution 5.2

$2^{20} \approx 1 0^{6}$ , isliye saare subsets par Bitmasking brute force viable hai aur sahi karna sabse simple bhi. Agar constraint mein knapsack-jaisi weight structure hai, DP ( $O (nW)$ ) bhi viable hai aur large $W$ -free structure ke liye faster ho sakta hai. Choose karo: (i) agar enumeration count $\leq 1 0^{8}$ hai aur correctness sabse zyada matter karti hai → bitmask brute force; (ii) agar $n$ badh sakta hai ya $W$ chota hai → DP. Jab sure na ho, pehle brute force code karo aur ise DP ke liye reference tester ki tarah use karo.

Exercise 5.3

Tumne ek fast DP likha hai aur chahte ho ki $n \leq 15$ cases par confidence ho ki sahi hai. Describe karo ki brute force yahaan apni value kaise prove karta hai chahe "real" solution DP ho.

Recall Solution 5.3

Brute force ko differential tester ki tarah use karo: bahut saare random small inputs ( $n \leq 15$ , jahan $2^{15} = 32768$ instant hai) ke liye, brute force aur DP dono chalao aur assert karo ki unke answers match karte hain. Kyunki complete enumeration guaranteed correct hai, koi bhi mismatch DP mein ek bug locate karta hai. Brute force ki slowness $n \leq 15$ par irrelevant hai; uski correctness-for-free hi poora point hai.

Recall Wrap-up: ek-line procedure (EVE)

Enumerate the candidates, Verify each, Estimate size×cost vs $1 0^{8}$ . Agar estimate haare, structure dhundho: recurrence → DP, exchange → greedy, prune-partial → Backtracking, all-subsets small → Bitmasking. Poori complexity language Time Complexity & Big-O se hai.