Important Questions - Theory of Computation

Example: Mealy Machine

Design a Mealy machine that outputs 1 when it receives two consecutive 1's, otherwise outputs 0.

State Diagram:

States: q₀ (initial), q₁ (seen one 1)

Transitions (format: input/output):
q₀ --0/0--> q₀
q₀ --1/0--> q₁
q₁ --0/0--> q₀
q₁ --1/1--> q₁
                

Transition Table:

Example Run:

Input: 01101

• Start: q₀
• Read 0: q₀ → q₀, output 0
• Read 1: q₀ → q₁, output 0
• Read 1: q₁ → q₁, output 1 ✓ (two consecutive 1's)
• Read 0: q₁ → q₀, output 0
• Read 1: q₀ → q₁, output 0

Output: 00100

Example: Moore Machine

Design a Moore machine that outputs 1 when it has seen two consecutive 1's, otherwise outputs 0.

State Diagram:

States: 
q₀ (initial, output 0)
q₁ (seen one 1, output 0)
q₂ (seen two 1's, output 1)

Transitions:
q₀ --0--> q₀
q₀ --1--> q₁
q₁ --0--> q₀
q₁ --1--> q₂
q₂ --0--> q₀
q₂ --1--> q₂

Outputs:
λ(q₀) = 0
λ(q₁) = 0
λ(q₂) = 1
                

Transition Table:

Example Run:

Input: 0110

• Start: q₀, output 0
• Read 0: q₀ → q₀, output 0
• Read 1: q₀ → q₁, output 0
• Read 1: q₁ → q₂, output 1 ✓ (in state that saw two 1's)
• Read 0: q₂ → q₀, output 0

Output: 00010 (5 outputs for 4 inputs)

Components of Transition Graph:

• Circles/Nodes: Represent states
• Arrows/Edges: Represent transitions
• Edge Labels: Input symbols causing transition
• Incoming Arrow: Indicates start state (no source)
• Double Circle: Indicates final/accepting state

Example 1: FSM that accepts strings ending with '01'

Transition Graph:

      0         1
  ┌───────┐  ┌──┐
  │       ↓  │  │
  →(q₀)──0──→(q₁)
      ↑       │
      │   1   │
      └───────┘

  q₁──1──→((q₂))
      ↑      │
      │  0   │
      └──────┘

States: Q = {q₀, q₁, q₂}
Start: q₀ (indicated by →)
Final: q₂ (indicated by double circle (( )))
Alphabet: Σ = {0, 1}
                

Explanation:

• q₀: Initial state (haven't seen required pattern)
• q₁: Just read a '0' (waiting for '1' to complete '01')
• q₂: Accepting state (string ends with '01')

Transitions:

• From q₀: Read 0 → go to q₁; Read 1 → stay in q₀
• From q₁: Read 0 → stay in q₁; Read 1 → go to q₂
• From q₂: Read 0 → go to q₁; Read 1 → go to q₀

Test Strings:

• "01" → q₀→q₁→q₂ ✓ Accepted
• "101" → q₀→q₀→q₁→q₂ ✓ Accepted
• "001" → q₀→q₁→q₁→q₂ ✓ Accepted
• "10" → q₀→q₀→q₁ ✗ Rejected (ends in q₁)
• "11" → q₀→q₀→q₀ ✗ Rejected (ends in q₀)

Transition Table for Above FSM:

Legend:

• → indicates start state
• * indicates final/accepting state
• Each cell shows the next state for given input

Matrix Form:

For input '0':

M₀ = | q₁  q₁  q₁ |
     (states after reading 0 from q₀, q₁, q₂)
                

For input '1':

M₁ = | q₀  q₂  q₀ |
     (states after reading 1 from q₀, q₁, q₂)
                

Example 2: Even Number of 1's

Design FSM that accepts strings with even number of 1's.

Transition Graph:

       1         1
    ┌─────┐   ┌─────┐
    ↓     │   ↓     │
  →((q₀))     (q₁)
    │  ↑  └───┘  ↑
    │  └─────────┘
    │      0
    └──────────────┐
         0         │
                   ↓
States: {q₀ (even), q₁ (odd)}
Start: q₀
Final: {q₀}
                

Transition Table:

Working:

• Start in q₀ (0 ones = even)
• Every '1' toggles between even/odd
• '0' doesn't affect count
• Accept if end in q₀ (even count)

Examples:

• "011" → even 1's ✓
• "1001" → even 1's ✓
• "0" → even 1's (zero) ✓
• "101" → odd 1's ✗

Example 3: Divisible by 3 (in binary)

FSM that accepts binary numbers divisible by 3.

Transition Table:

Logic: When reading binary left-to-right, new value = (old_value × 2 + new_bit) mod 3

Examples:

• "11" (3 in decimal) → q₀→q₁→q₀ ✓
• "110" (6 in decimal) → q₀→q₁→q₀→q₀ ✓
• "1001" (9 in decimal) → q₀→q₁→q₂→q₁→q₀ ✓

Application 1: L = {0ⁿ1ⁿ | n ≥ 0} is NOT Regular

Language: Equal number of 0's followed by equal number of 1's

Examples: ε, 01, 0011, 000111, ...

Proof:

1. Assume L is regular with pumping length n
2. Choose w = 0ⁿ1ⁿ (clearly w ∈ L and |w| = 2n ≥ n)
3. By Pumping Lemma, w = xyz where:
   • |y| > 0
   • |xy| ≤ n
4. Analysis: Since |xy| ≤ n, both x and y consist only of 0's (they're in the first n symbols)
   • So y = 0^k for some k > 0
5. Pump with i = 2: xy²z = 0^n+k1ⁿ
   • This has MORE 0's than 1's
   • Therefore xy²z ∉ L
6. Pump with i = 0: xy⁰z = xz = 0^n-k1ⁿ
   • This has FEWER 0's than 1's
   • Therefore xz ∉ L
7. Contradiction! Therefore L is NOT regular ✓

Application 2: L = {a^p | p is prime} is NOT Regular

Language: Strings of a's where length is a prime number

Examples: aa, aaa, aaaaa, aaaaaaa (lengths 2, 3, 5, 7, ...)

Proof:

1. Assume L is regular with pumping length n
2. Choose w = a^p where p is a prime ≥ n (such prime exists by Euclid)
3. By Pumping Lemma, w = xyz where |y| > 0 and |xy| ≤ n
4. Let |y| = k where 1 ≤ k ≤ n < p
5. Pump with i = p: xy^pz has length:
   • |xyz| + (p-1)|y| = p + (p-1)k = p + pk - k = p(1+k) - k
   • If we choose i = p+1: length = p + p·k = p(1+k)
6. This is composite (divisible by p and 1+k), not prime!
7. Contradiction! Therefore L is NOT regular ✓

Application 3: L = {ww | w ∈ {0,1}*} is NOT Regular

Language: Strings that are a word repeated twice

Examples: ε, 00, 11, 0101, 1010, 001001, ...

Proof:

1. Assume L is regular with pumping length n
2. Choose w = 0ⁿ10ⁿ1 (w = (0ⁿ1)(0ⁿ1), so w ∈ L)
3. By Pumping Lemma, w = xyz where |y| > 0 and |xy| ≤ n
4. Since |xy| ≤ n, y consists only of 0's from first part
5. Pump with i = 2: xy²z adds more 0's to first occurrence
   • First part: 0^n+k1 (where k = |y| > 0)
   • Second part: 0ⁿ1 (unchanged)
   • Not of form ww anymore!
6. Contradiction! Therefore L is NOT regular ✓

Application 4: L = {0ⁿ1^m | n ≠ m} is NOT Regular

Language: Strings with unequal number of 0's and 1's

Proof (using closure properties):

1. Assume L is regular
2. Regular languages are closed under complement
3. So L̄ = {0ⁿ1^m | n = m} ∪ {strings not of form 0*1*} would be regular
4. Regular languages are closed under intersection with regular languages
5. L̄ ∩ 0*1* = {0ⁿ1ⁿ | n ≥ 0} would be regular
6. But we proved {0ⁿ1ⁿ} is NOT regular!
7. Contradiction! Therefore L is NOT regular ✓

Application 5: L = {0ⁱ1^j | i > j} is NOT Regular

Language: More 0's than 1's

Proof:

1. Assume L is regular with pumping length n
2. Choose w = 0ⁿ⁺¹1ⁿ ∈ L (n+1 > n)
3. By Pumping Lemma, w = xyz where |xy| ≤ n, |y| > 0
4. So y = 0^k for some k > 0
5. Pump with i = 0: xz = 0^n+1-k1ⁿ
   • If k = 1: we get 0ⁿ1ⁿ where n = n, not i > j!
   • If k > 1: we get 0^n+1-k1ⁿ where n+1-k ≤ n
   • Either way, xz ∉ L
6. Contradiction! Therefore L is NOT regular ✓

Example 1: Balanced Parentheses

S → ε
S → (S)
S → SS
                

Generates: ε, (), (()), ()(), ((())), (())(), ()(()), ...

Derivation of "(()())":

S ⇒ (S)           [Apply S → (S)]
  ⇒ (SS)          [Apply S → SS]
  ⇒ ((S)S)        [Apply first S → (S)]
  ⇒ ((S)(S))      [Apply second S → (S)]
  ⇒ (()())        [Apply both S → ε]
                

Example 2: Arithmetic Expressions

E → E + E
E → E * E
E → (E)
E → id
                

Generates: id, id+id, id*id, (id+id)*id, ...

Note: This grammar is ambiguous (multiple parse trees possible)

Example 3: {0ⁿ1ⁿ | n ≥ 0}

S → 0S1
S → ε
                

Derivations:

• n=0: S ⇒ ε
• n=1: S ⇒ 0S1 ⇒ 01
• n=2: S ⇒ 0S1 ⇒ 00S11 ⇒ 0011
• n=3: S ⇒ 0S1 ⇒ 00S11 ⇒ 000S111 ⇒ 000111

This language is NOT regular but IS context-free!

Example 1: Right-Linear Grammar

Language: Strings ending with 'ab'

S → aS | bS | aB
B → b
                

Analysis:

• S → aS or bS: Read any symbol, stay in S
• S → aB: Read 'a', prepare for final 'b'
• B → b: Generate final 'b'

Generates: ab, aab, bab, aaab, abab, ababab, ...

Example 2: Left-Linear Grammar

Language: (ab)*

S → Sab | ε
                

Generates: ε, ab, abab, ababab, ...

Example 3: Binary Strings with Even 0's

S → 1S | 0A | ε
A → 1A | 0S
                

Analysis:

• S: even number of 0's seen
• A: odd number of 0's seen
• Reading 1 doesn't change state
• Reading 0 toggles between S and A

Parse Tree for "id + id":

           E
          /|\
         / | \
        E  +  T
        |     |
        T     F
        |     |
        F     id
        |
       id
                

Properties:

• Root: Start symbol (E)
• Internal nodes: Variables
• Leaves: Terminals
• Reading leaves left-to-right gives the derived string
• Same parse tree for both leftmost and rightmost derivations!

Example: Ambiguous Grammar

E → E + E | E * E | id
                

String "id + id * id" has TWO parse trees:

Tree 1: (id + id) * id [add first]

Tree 2: id + (id * id) [multiply first]

This is ambiguous! Need to rewrite with precedence levels.

Example 1: Simple CNF Grammar

S → AB
S → BC
A → BA
A → a
B → CC
B → b
C → AB
C → a
                

✓ All productions are either A → BC or A → a form

Step 1: Add New Start Symbol

Create new start S₀ → S to ensure start doesn't appear on right side

Original: S → ASA | aB
Add: S₀ → S
                

Step 2: Eliminate ε-Productions

Remove all A → ε (except possibly S → ε)

Original:
S → ASA | aB
A → B | ε
B → b | ε

After eliminating ε:
S → ASA | SA | AS | S | aB | a
A → B
B → b
                

Step 3: Eliminate Unit Productions

Remove all A → B (single variable productions)

Before: A → B, B → b
After: A → b (substitute)

Result:
S → ASA | SA | AS | S | aB | a
A → b
B → b
                

Step 4: Replace Terminals in Long Productions

For productions with terminals mixed with variables, create new variables for terminals

S → ASA becomes S → A₁SA₁ with A₁ → a
S → aB becomes S → A₁B with A₁ → a

After:
S → A₁SA₁ | SA | AS | A₁B
A₁ → a
A → b
B → b
                

Step 5: Break Long Productions

Productions with >2 variables broken into binary productions

S → A₁SA₁ (3 variables) breaks into:
S → A₁C₁
C₁ → SA₁

Final CNF:
S → A₁C₁ | SA | AS | A₁B
C₁ → SA₁
A₁ → a
A → b
B → b
                

Complete Example: Convert to CNF

Original Grammar:

S → ASA | aB
A → B | S
B → b | ε
                

Step 1: New start

S₀ → S
S → ASA | aB
A → B | S
B → b | ε
                

Step 2: Eliminate ε (B → ε makes B nullable)

S₀ → S
S → ASA | aB | a
A → B | S
B → b
                

Step 3: Eliminate unit productions

S₀ → ASA | aB | a
S → ASA | aB | a
A → b | ASA | aB | a
B → b
                

Step 4: Replace terminals

T_a → a
T_b → b
S₀ → ASA | T_aB | a
S → ASA | T_aB | a
A → b | ASA | T_aB | a
B → b
                

Step 5: Break long productions (ASA has 3 symbols)

S₀ → AC₁ | T_aB | a
S → AC₁ | T_aB | a
C₁ → SA
A → b | AC₁ | T_aB | a
B → b
T_a → a
                

Final CNF ✓

Example 1: Simple GNF Grammar

S → aAB | bB | a
A → aA | bB | a
B → bB | b
                

✓ Every production starts with terminal

✓ Followed by zero or more variables

Derivation of "aba":

S ⇒ aAB     [Produce 'a']
  ⇒ abB     [Produce 'b']
  ⇒ aba     [Produce 'a']
                

Exactly 3 steps for 3 terminals!

Example 2: L = {0ⁿ1ⁿ | n ≥ 1} in GNF

S → 0S1 | 01
                

Wait, this is NOT in GNF! (has terminal at end)

Correct GNF:

S → 0A
A → 0A1 | 01
                

Or better:

S → 0SA₁ | 0A₁
A₁ → 1
                

Now every production starts with terminal ✓

Example: Eliminate Left Recursion

Original (has left recursion):

A → Aα | β (where β doesn't start with A)
                

Converted (no left recursion):

A → βA'
A' → αA' | ε
                

For GNF, further transform to start with terminal

Example 1: PDA for L = {0ⁿ1ⁿ | n ≥ 1}

Idea: Push all 0's onto stack, pop one for each 1

PDA Design:

States: {q₀, q₁, q₂}
Stack Alphabet: {0, Z₀}
                

Transitions:

Trace for "0011":

(q₀, 0011, Z₀)   [Start]
⊢ (q₀, 011, 0Z₀)  [Push 0]
⊢ (q₀, 11, 00Z₀)  [Push 0]
⊢ (q₁, 1, 0Z₀)    [Pop 0]
⊢ (q₁, ε, Z₀)     [Pop 0]
⊢ (q₂, ε, ε)      [Accept - reached final state]
                

Example 2: PDA for Balanced Parentheses

Language: Well-formed parentheses

Transitions:

• δ(q, '(', Z₀) = {(q, (Z₀)} - Push ( on empty stack
• δ(q, '(', '(') = {(q, (()} - Push ( on stack
• δ(q, ')', '(') = {(q, ε)} - Pop ( when seeing )
• δ(q, ε, Z₀) = {(f, Z₀)} - Accept if stack has only Z₀

Examples:

• "(())" ✓ - Balanced
• "()()" ✓ - Balanced
• "(()" ✗ - Too many open
• "())" ✗ - Too many close

Example: DPDA for {0ⁿ1ⁿ | n ≥ 1}

δ(q₀, 0, Z₀) = (q₀, 0Z₀)     ✓ Only one choice
δ(q₀, 0, 0) = (q₀, 00)       ✓ Only one choice
δ(q₀, 1, 0) = (q₁, ε)        ✓ Only one choice
δ(q₁, 1, 0) = (q₁, ε)        ✓ Only one choice
δ(q₁, ε, Z₀) = (q₂, Z₀)      ✓ Only one ε-transition
                                 and no input transition
                                 from (q₁, Z₀)

This is DETERMINISTIC ✓
                

L = {wwᴿ | w ∈ {a,b}*} (Even Palindromes)

Problem: DPDA cannot determine the middle point!

• NPDA can nondeterministically guess middle
• DPDA has no way to know when to switch from pushing to popping
• Example: "abba" - when to stop pushing and start popping?

Conclusion: {wwᴿ} is CFL but NOT DCFL

Visual Representation:

    Finite Control
    +----------+
    | State: q |
    +----------+
         ↓
    ... B | 0 | 1 | 0 | B | B ...
              ↑
           Tape Head
           (currently at position with '1')
                

Example 1: TM for L = {0ⁿ1ⁿ | n ≥ 1}

Idea: Match each 0 with corresponding 1

Algorithm:

1. Replace leftmost 0 with X
2. Move right past all 0's and 1's
3. Replace leftmost 1 with Y
4. Move left back to start
5. Repeat until all 0's matched with 1's
6. Accept if tape has only X's and Y's

States:

• q₀: Start state
• q₁: After replacing 0 with X, searching for 1
• q₂: After replacing 1 with Y, going back
• q₃: Checking if done
• q₄: Accept state

Transition Table:

Trace for input "0011":

1. q₀0011B     [Start]
2. Xq₁011B     [Replace 0 with X, move right]
3. X0q₁11B     [Skip 0]
4. X0q₂Y1B     [Replace 1 with Y, move left]
5. Xq₂0Y1B     [Move left]
6. q₂X0Y1B     [Move left]
7. Xq₀0Y1B     [Back at X, move right]
8. XXq₁Y1B     [Replace 0 with X, move right]
9. XXYq₁1B     [Skip Y]
10. XXq₂YYB    [Replace 1 with Y, move left]
11. Xq₂XYYB    [Move left]
12. XXq₀YYB    [Back at X, move right]
13. XXYq₃YB    [No more 0's, check]
14. XXYYq₃B    [Move right]
15. XXYYBq₄    [Accept! ✓]
                

Example 2: TM for Addition

Language: Binary addition (compute m + n)

Input: 0ᵐ10ⁿ (m and n in unary)

Output: 0ᵐ⁺ⁿ

Algorithm:

1. Replace the separator '1' with '0'
2. Erase the rightmost '0'

Example: 000100 → 000000 → 00000 (3+2=5)

Examples of P Problems:

Examples of NP Problems:

Note: All these problems have exponential time solutions but polynomial time verification!

Common NP-Complete Problems:

Examples of NP-Hard (but not NP-Complete):

┌─────────────────────────────────────┐
│           NP-Hard                   │
│  ┌──────────────────────────────┐   │
│  │         NP                   │   │
│  │  ┌─────────────────────┐     │   │
│  │  │    NP-Complete      │     │   │
│  │  │  (Hardest in NP)    │     │   │
│  │  └─────────────────────┘     │   │
│  │  ┌──────────┐                │   │
│  │  │    P     │                │   │
│  │  │  (Easy)  │                │   │
│  │  └──────────┘                │   │
│  └──────────────────────────────┘   │
│  Optimization TSP, etc.             │
└─────────────────────────────────────┘
                

Example 1: Graph WITH Hamiltonian Cycle

Graph:
        A ---- B
        |      |
        |      |
        D ---- C

Edges: {(A,B), (B,C), (C,D), (D,A)}

Hamiltonian Cycle: A → B → C → D → A ✓
    - Visits all 4 vertices exactly once
    - Returns to starting vertex A
    - This is a Hamiltonian Cycle!

Other Hamiltonian Cycles:
    B → C → D → A → B
    C → D → A → B → C
    D → A → B → C → D
    (All are rotations/reflections of same cycle)
                

Example 2: Graph WITHOUT Hamiltonian Cycle

Graph:
        A ---- B ---- C
        |             |
        |             |
        D ----------- E

Edges: {(A,B), (B,C), (C,E), (E,D), (D,A)}

Try all possible paths starting from A:
    A → B → C → E → D → ? (need to return to A, but no edge from D to A)
    A → D → E → C → B → ? (need to return to A, but no edge from B to A)
    
Problem: After visiting all vertices, cannot return to start!
Hamiltonian Cycle: DOES NOT EXIST ✗

However, Hamiltonian PATH exists:
    B → A → D → E → C ✓ (visits all vertices once)
                

Example 3: Complete Graph K₅

Complete graph with 5 vertices (every vertex connected to every other):

        A
       /|\\\
      / | \\\
     /  |  \\\
    B---+---C
     \  |  /
      \ | /
       \|/
        D---E

Every pair of vertices connected!

Hamiltonian Cycle exists: A → B → C → D → E → A ✓

In fact, complete graph Kₙ (n ≥ 3) ALWAYS has Hamiltonian cycle!

Number of distinct Hamiltonian cycles in Kₙ: (n-1)!/2
For K₅: (5-1)!/2 = 24/2 = 12 distinct cycles
                

Example 4: Detailed Trace

Graph:

        1 ---- 2
       /|      |\\
      / |      | \\
     /  |      |  \\
    5   |      |   3
     \  |      |  /
      \ |      | /
       \|      |/
        6 ---- 4

Edges: {(1,2), (1,5), (1,6), (2,3), (2,4), (3,4), (4,6), (5,6)}
                

Find Hamiltonian Cycle:

Try starting from vertex 1:

Attempt 1: 1 → 2 → 3 → 4 → 6 → 5 → ?
    Need edge (5,1) but doesn't exist ✗

Attempt 2: 1 → 2 → 4 → 3 → ?
    Stuck, can't reach remaining vertices ✗

Attempt 3: 1 → 2 → 4 → 6 → 5 → ?
    Need edge (5,3) but doesn't exist ✗

Attempt 4: 1 → 5 → 6 → 4 → 3 → 2 → ?
    Need edge (2,1) - YES, exists! ✓

Hamiltonian Cycle Found: 1 → 5 → 6 → 4 → 3 → 2 → 1 ✓
                

Backtracking Algorithm:

HamiltonianCycle(graph G, path, pos):
    if pos == n:  // All vertices included
        if edge exists from path[pos-1] to path[0]:
            return true  // Cycle found!
        else:
            return false
    
    for each vertex v in G:
        if isSafe(v, graph, path, pos):
            path[pos] = v
            if HamiltonianCycle(G, path, pos+1):
                return true
            path[pos] = -1  // Backtrack
    
    return false

isSafe(v, graph, path, pos):
    // Check if vertex v can be added at position pos
    if edge doesn't exist from path[pos-1] to v:
        return false
    if v already in path:
        return false
    return true
                

Example 1: Small TSP Instance (4 Cities)

Cities: A, B, C, D

Distance Matrix:

All Possible Tours (starting from A):

Tour 1: A → B → C → D → A
    Distance: 10 + 35 + 30 + 20 = 95

Tour 2: A → B → D → C → A
    Distance: 10 + 25 + 30 + 15 = 80 ✓ BEST!

Tour 3: A → C → B → D → A
    Distance: 15 + 35 + 25 + 20 = 95

Tour 4: A → C → D → B → A
    Distance: 15 + 30 + 25 + 10 = 80 ✓ BEST!

Tour 5: A → D → B → C → A
    Distance: 20 + 25 + 35 + 15 = 95

Tour 6: A → D → C → B → A
    Distance: 20 + 30 + 35 + 10 = 95

Optimal Tour: A → B → D → C → A (or reverse)
Optimal Distance: 80
                

Note: For n=4 cities, there are (4-1)!/2 = 3 unique tours

Example 2: Geometric TSP (Cities on Plane)

Cities with (x,y) coordinates:
    A = (0, 0)
    B = (3, 0)
    C = (3, 4)
    D = (0, 4)

This forms a rectangle!

Calculate Euclidean distances:
    d(A,B) = √[(3-0)² + (0-0)²] = 3
    d(B,C) = √[(3-3)² + (4-0)²] = 4
    d(C,D) = √[(0-3)² + (4-4)²] = 3
    d(D,A) = √[(0-0)² + (4-0)²] = 4
    d(A,C) = √[(3-0)² + (4-0)²] = 5
    d(B,D) = √[(0-3)² + (4-0)²] = 5

Compare tours:
    A → B → C → D → A: 3 + 4 + 3 + 4 = 14 ✓ OPTIMAL
    A → B → D → C → A: 3 + 5 + 3 + 5 = 16
    A → C → B → D → A: 5 + 4 + 5 + 4 = 18

Optimal: Follow rectangle perimeter = 14
                

Brute Force Algorithm:

TSP_BruteForce(cities[], dist[][]):
    min_distance = ∞
    best_tour = null
    
    for each permutation P of cities:
        current_distance = 0
        for i = 0 to n-1:
            current_distance += dist[P[i]][P[(i+1) % n]]
        
        if current_distance < min_distance:
            min_distance = current_distance
            best_tour = P
    
    return (best_tour, min_distance)

Time Complexity: O(n!) - try all (n-1)! tours
Space: O(n)
Practical limit: ~15 cities
                

Nearest Neighbor Heuristic:

Greedy approach: Always go to nearest unvisited city

NearestNeighbor(start_city):
    current = start_city
    visited = {start_city}
    tour = [start_city]
    total_distance = 0
    
    while visited.size < n:
        nearest = city with minimum dist[current][city]
                  where city not in visited
        tour.append(nearest)
        visited.add(nearest)
        total_distance += dist[current][nearest]
        current = nearest
    
    total_distance += dist[current][start_city]  // Return home
    return (tour, total_distance)

Time Complexity: O(n²)
Approximation: No guarantee (can be arbitrarily bad!)
                

Example with 4 cities:

Start at A:
    Nearest to A: B (distance 10)
    Nearest to B: D (distance 25, C=35)
    Nearest to D: C (distance 30, only unvisited)
    Return to A: distance 15
    
Tour: A → B → D → C → A
Total: 10 + 25 + 30 + 15 = 80 ✓ (happens to be optimal!)

Note: Nearest neighbor doesn't always find optimal!
                

2-Approximation Algorithm (MST-based):

For metric TSP: Guarantees tour ≤ 2 × optimal

Algorithm:
1. Find Minimum Spanning Tree (MST) of cities
2. Do DFS traversal of MST (visits each edge twice)
3. Create shortcut tour by skipping repeated vertices

Guarantee: Tour length ≤ 2 × OPT
Time: O(n² log n) using Prim's algorithm

Why it works:
- MST cost ≤ OPT (removing one edge from optimal tour gives spanning tree)
- DFS traversal = 2 × MST cost
- Shortcuts only reduce distance (triangle inequality)
- Therefore: Final tour ≤ 2 × MST ≤ 2 × OPT
                

Christofides Algorithm (1.5-approximation):

Best known approximation for metric TSP

Algorithm:
1. Find MST of graph
2. Find vertices with odd degree in MST
3. Find minimum-weight perfect matching on odd-degree vertices
4. Combine MST and matching to form Eulerian graph
5. Find Eulerian tour
6. Convert to Hamiltonian tour by skipping repeated vertices

Guarantee: Tour length ≤ 1.5 × OPT
Time: O(n³)

This is the best known polynomial-time approximation!