Algorithms

Contents
1 Binary Powering Algorithm 4
1.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Karatsuba’s Algorithm 5
2.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Strassen’s Algorithm for Matrix Multiplication 6

3.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.4 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Quickselect Algorithm and Median of Medians 9

4.1 Quickselect Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.4 Median of Medians Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.5 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.6 Time Complexity Analysis of Median of Medians . . . . . . . . . . . . . . . . . . . . 11
4.7 Combining Quickselect and Median of Medians . . . . . . . . . . . . . . . . . . . . . 11

5 Closest Pair of Points Algorithm 12

5.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.4 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1
6 Quicksort Algorithm 14
6.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.4 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

7 Karger’s Contraction Algorithm for Global Minimum Cut 16

7.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.4 Space Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.5 Randomization and Success Probability . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

8 Random Walk Algorithm for Maze Navigation 18

8.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.4 Properties and Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
8.6 Comparison to Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
8.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

9 WalkSAT Algorithm for Boolean Satisfiability (SAT) 20

9.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
9.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
9.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
9.4 Probabilistic Behavior and Success Guarantee . . . . . . . . . . . . . . . . . . . . . . 21
9.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
9.6 Comparison to Other Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
9.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

10 Union-Find Algorithm with Path Compression and Amortization 22

10.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
10.2 Optimization Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
10.3 Time Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
10.4 Amortized Analysis Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
10.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
10.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
10.7 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2
11 Lempel-Ziv-Welsh (LZW) Compression Algorithm 24
11.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
11.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
11.3 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
11.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

12 Huffman Encoding Algorithm 25

12.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
12.2 Explanation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
12.3 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
12.4 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
12.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

13 Comparison of LZW and Huffman Encoding 26

13.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3
1 Binary Powering Algorithm
The Binary Powering Algorithm, also known as Exponentiation by Squaring, is an efficient algorithm
to compute xn for integers x and n.

1.1 Algorithm Description

Below is the pseudocode for the Binary Powering Algorithm:

Listing 1: Binary Powering Algorithm

def binary_power (x , n ):
result = 1
base = x

while n > 0:
if n % 2 == 1: # If n is odd
result *= base
base *= base
n //= 2

return result

1.2 Explanation
The algorithm works as follows:
1. Initialize ‘result‘ to 1 and ‘base‘ to x. 2. While n > 0: - If n is odd, multiply ‘result‘ by
‘base‘. - Square the ‘base‘. - Halve n (using integer division). 3. Return the ‘result‘.
The key idea is that we break down the computation of xn into smaller problems using the
properties of exponents: (
n (xn/2 )2 if n is even,
x = (n−1)/2 2
x · (x ) if n is odd.

1.3 Time Complexity Analysis

The time complexity of the Binary Powering Algorithm is O(log n):

• At each step, the algorithm reduces the problem size by halving n.

• The number of steps is proportional to the number of times n can be divided by 2, which is
⌊log2 n⌋ + 1.
• Each step involves a constant number of operations (multiplication and squaring), leading to
an overall complexity of O(log n).

1.4 Space Complexity

The space complexity is O(1) because the algorithm uses a constant amount of extra space regardless
of the size of n.

4
2 Karatsuba’s Algorithm
Karatsuba’s Algorithm is an efficient algorithm for multiplying large integers or polynomials. It
reduces the complexity of multiplication from the naive O(n2 ) to O(nlog2 3 ) ≈ O(n1.585 ).

2.1 Algorithm Description

Below is the pseudocode for Karatsuba’s Algorithm:

Listing 2: Karatsuba’s Algorithm for Multiplication

def karatsuba (x , y ):
# Base case for recursion
if x < 10 or y < 10:
return x * y

# Calculate the size of the numbers

n = max ( len ( str ( x )) , len ( str ( y )))
half = n // 2

# Split the numbers into two halves

x_high = x // 10** half
x_low = x % 10** half
y_high = y // 10** half
y_low = y % 10** half

# Recursively calculate three products

z0 = karatsuba ( x_low , y_low )
z1 = karatsuba ( x_low + x_high , y_low + y_high )
z2 = karatsuba ( x_high , y_high )

# Combine the results

return ( z2 * 10**(2* half )) + (( z1 - z2 - z0 ) * 10** half ) + z0

2.2 Explanation
The algorithm works as follows:
1. If the numbers are small (single-digit), multiply them directly. 2. Otherwise, split each
number into two halves: - x = xhigh · 10half + xlow - y = yhigh · 10half + ylow 3. Compute three
recursive products: - z0 = xlow · ylow - z1 = (xlow + xhigh ) · (ylow + yhigh ) - z2 = xhigh · yhigh 4.
Combine the results using the formula:

x · y = z2 · 102·half + (z1 − z2 − z0 ) · 10half + z0

2.3 Time Complexity Analysis

The time complexity of Karatsuba’s Algorithm is O(nlog2 3 ) ≈ O(n1.585 ):

• Each recursive step splits the problem into three smaller subproblems of half the size.

5
 • The depth of the recursion tree is log2 n.
• Combining results at each level takes O(n).
• Thus, the total complexity is O(nlog2 3 ).

2.4 Space Complexity

The space complexity is O(log n) due to the recursion stack.

3 Strassen’s Algorithm for Matrix Multiplication

Strassen’s Algorithm is an efficient method for matrix multiplication that improves the naive O(n3 )
complexity to approximately O(n2.81 ). It uses a divide-and-conquer approach to multiply two
square matrices.

3.1 Algorithm Description

Below is the pseudocode for Strassen’s Algorithm:

Listing 3: Strassen’s Algorithm for Matrix Multiplication

def strassen (A , B ):
# Base case for recursion
if len ( A ) == 1:
return [[ A [0][0] * B [0][0]]]

# Split matrices into quadrants

n = len ( A )
half = n // 2
A11 , A12 , A21 , A22 = split_matrix ( A )
B11 , B12 , B21 , B22 = split_matrix ( B )

# Compute the 7 products

M1 = strassen ( add ( A11 , A22 ) , add ( B11 , B22 ))
M2 = strassen ( add ( A21 , A22 ) , B11 )
M3 = strassen ( A11 , subtract ( B12 , B22 ))
M4 = strassen ( A22 , subtract ( B21 , B11 ))
M5 = strassen ( add ( A11 , A12 ) , B22 )
M6 = strassen ( subtract ( A21 , A11 ) , add ( B11 , B12 ))
M7 = strassen ( subtract ( A12 , A22 ) , add ( B21 , B22 ))

# Combine the results into the final matrix

C11 = add ( subtract ( add ( M1 , M4 ) , M5 ) , M7 )
C12 = add ( M3 , M5 )
C21 = add ( M2 , M4 )
C22 = add ( subtract ( add ( M1 , M3 ) , M2 ) , M6 )

return combine_matrix ( C11 , C12 , C21 , C22 )

6
# Helper functions for matrix operations ( split , add , subtract , combine )
are omitted for brevity .

3.2 Explanation
The algorithm works as follows: 1. Divide the input matrices A and B into four equal-sized
submatrices:    
A11 A12 B11 B12
A= , B=
A21 A22 B21 B22
2. Compute seven products:

M1 = (A11 + A22 )(B11 + B22 )

M2 = (A21 + A22 )B11

M3 = A11 (B12 − B22 )

M4 = A22 (B21 − B11 )

M5 = (A11 + A12 )B22

M6 = (A21 − A11 )(B11 + B12 )

M7 = (A12 − A22 )(B21 + B22 )

3. Combine these products to compute the resulting matrix C:

 
C11 C12
C= , where:
C21 C22

C11 = M1 + M4 − M5 + M7

C12 = M3 + M5

C21 = M2 + M4

C22 = M1 − M2 + M3 + M6

3.3 Time Complexity Analysis

The time complexity of Strassen’s Algorithm is O(nlog2 7 ) ≈ O(n2.81 ):

7
 • The algorithm divides the matrices into four submatrices of size n/2 × n/2.
• Seven recursive calls are made, and combining the results requires O(n2 ) operations.
• The overall complexity is T (n) = 7T (n/2) + O(n2 ), which solves to O(nlog2 7 ).

3.4 Space Complexity

The space complexity is O(n2 ) for storing intermediate matrices and results, plus additional space
for the recursion stack, which has a depth of O(log n).

8
4 Quickselect Algorithm and Median of Medians
The Quickselect algorithm is an efficient algorithm to find the k-th smallest element in an unsorted
array. To improve its worst-case behavior, the Median of Medians algorithm can be used as a pivot
selection strategy.

4.1 Quickselect Algorithm

Quickselect is based on the same partitioning logic as Quicksort but focuses only on the part of the
array containing the desired k-th smallest element.

Listing 4: Quickselect Algorithm

def quickselect ( arr , k ):
if len ( arr ) == 1: # Base case
return arr [0]

# Choose a pivot ( could be improved using Median of Medians )

pivot = arr [ len ( arr ) // 2]

# Partition the array into three groups

low = [ x for x in arr if x < pivot ]
high = [ x for x in arr if x > pivot ]
equal = [ x for x in arr if x == pivot ]

if k < len ( low ): # If k is in the low partition

return quickselect ( low , k )
elif k < len ( low ) + len ( equal ): # If k is in the pivot group
return pivot
else : # If k is in the high partition
return quickselect ( high , k - len ( low ) - len ( equal ))

4.2 Explanation
The algorithm works as follows: 1. Select a pivot element from the array (randomly or determin-
istically). 2. Partition the array into: - ‘low‘: Elements less than the pivot. - ‘equal‘: Elements
equal to the pivot. - ‘high‘: Elements greater than the pivot. 3. Recurse into the part of the array
containing the k-th smallest element: - If k lies in ‘low‘, recurse on ‘low‘. - If k lies in ‘equal‘, return
the pivot. - If k lies in ‘high‘, recurse on ‘high‘.

4.3 Time Complexity Analysis

The average-case time complexity of Quickselect is O(n):
• At each step, the array is partitioned around a pivot, which splits the array into two smaller
subarrays.

• On average, the size of the subarray is halved at each step, leading to O(n+n/2+n/4+. . .) =
O(n).

9
The worst-case complexity is O(n2 ) if the pivot selection is poor (e.g., always selecting the smallest
or largest element).

10
4.4 Median of Medians Algorithm
The Median of Medians algorithm improves the pivot selection to ensure a good split and guarantee
O(n) worst-case complexity for Quickselect.

Listing 5: Median of Medians Algorithm

def m edian_of_medians ( arr ):
# Divide array into groups of 5
groups = [ arr [ i : i + 5] for i in range (0 , len ( arr ) , 5)]
medians = [ sorted ( group )[ len ( group ) // 2] for group in groups ]

# Recursively find the median of medians

if len ( medians ) <= 5:
return sorted ( medians )[ len ( medians ) // 2]
return median_of_medians ( medians )

4.5 Explanation
The algorithm works as follows: 1. Divide the array into groups of at most 5 elements. 2. Find the
median of each group (sort each group and pick the middle element). 3. Recursively compute the
median of the medians to use as the pivot.

4.6 Time Complexity Analysis of Median of Medians

• Partitioning the array into groups of 5 takes O(n).
• Finding the median of each group takes O(n).
• Recursing on the medians takes O(n/5), and partitioning takes O(n).

• Solving the recurrence T (n) = T (n/5) + T (7n/10) + O(n) leads to T (n) = O(n).

4.7 Combining Quickselect and Median of Medians

By using the Median of Medians to select the pivot in Quickselect, the worst-case time complexity
of Quickselect is reduced to O(n). However, this comes at the cost of a larger constant factor in
practice.

11
5 Closest Pair of Points Algorithm
The Closest Pair of Points algorithm is used to find the two points in a set of points (in a plane)
that are closest to each other. A naive approach has O(n2 ) complexity, but the divide-and-conquer
approach reduces this to O(n log n).

5.1 Algorithm Description

The algorithm divides the points into two halves, recursively solves for each half, and then combines
the results to find the closest pair.

Listing 6: Closest Pair Algorithm

import math

def closest_pair ( points ):

# Helper function to calculate Euclidean distance
def distance ( p1 , p2 ):
return math . sqrt (( p1 [0] - p2 [0])**2 + ( p1 [1] - p2 [1])**2)

# Recursive function to find the closest pair

def closest_util ( px , py ):
# Base case : use brute force for small inputs
if len ( px ) <= 3:
return min (( distance ( px [ i ] , px [ j ]) , ( px [ i ] , px [ j ]))
for i in range ( len ( px )) for j in range ( i + 1 , len ( px )))

# Divide the points into two halves

mid = len ( px ) // 2
midpoint = px [ mid ]

Qx , Rx = px [: mid ] , px [ mid :]
Qy , Ry = [ p for p in py if p in Qx ] , [ p for p in py if p in Rx ]

# Recursively find the closest pairs in each half

( d1 , pair1 ) = closest_util ( Qx , Qy )
( d2 , pair2 ) = closest_util ( Rx , Ry )

# Find the smaller distance

d = min ( d1 , d2 )
best_pair = pair1 if d1 < d2 else pair2

# Check the strip around the midpoint

strip = [ p for p in py if abs ( p [0] - midpoint [0]) < d ]
for i in range ( len ( strip )):
for j in range ( i + 1 , min ( i + 7 , len ( strip ))): # At most 6 points
need to be checked
d_strip = distance ( strip [ i ] , strip [ j ])
if d_strip < d :
d = d_strip
best_pair = ( strip [ i ] , strip [ j ])

12
 return d , best_pair

# Pre - sort the points by x and y coordinates

px = sorted ( points , key = lambda p : p [0])
py = sorted ( points , key = lambda p : p [1])

# Call the recursive function

return closest_util ( px , py )[1]

5.2 Explanation
The algorithm works as follows: 1. **Base Case**: If the number of points is 3 or fewer, compute
the distances using brute force. 2. **Divide**: Split the points into two halves based on their
x-coordinates. 3. **Recur**: Recursively find the closest pairs in the left and right halves. 4.
**Combine**: - The closest pair could lie across the two halves. To find this, examine a ”strip” of
points around the dividing line. - In this strip, only points within d (the smaller of the distances
from the two halves) need to be checked. - Further, only at most 6 points in the strip need to be
compared for each point, reducing the time complexity.

5.3 Time Complexity Analysis

The time complexity of the algorithm is O(n log n):
• Sorting the points by x and y coordinates takes O(n log n).
• The recursive division and conquering takes T (n) = 2T (n/2) + O(n) due to the merge step
(processing the strip).

• Solving this recurrence gives T (n) = O(n log n).

The space complexity is O(n) for storing the sorted arrays and temporary arrays used during
recursion.

5.4 Example
If the input is:
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
√
The closest pair of points is (2, 3) and (3, 4), with a distance of 2.

13
6 Quicksort Algorithm
Quicksort is a divide-and-conquer algorithm for sorting an array or list. It works by selecting a
pivot, partitioning the array around the pivot, and recursively sorting the subarrays. Quicksort has
an average-case time complexity of O(n log n), making it one of the most efficient sorting algorithms
in practice.

6.1 Algorithm Description

Below is the pseudocode for the Quicksort algorithm:
Listing 7: Quicksort Algorithm
def quicksort ( arr ):
if len ( arr ) <= 1: # Base case : arrays w / 0 or 1 elements are alr sorted
return arr

# Choose a pivot ( e . g . , the last element )

pivot = arr [ -1]

# Partition the array into elements

# less than , equal to , and greater than the pivot
less = [ x for x in arr [: -1] if x < pivot ]
equal = [ x for x in arr if x == pivot ]
greater = [ x for x in arr [: -1] if x > pivot ]

# Recursively sort the partitions and combine them

return quicksort ( less ) + equal + quicksort ( greater )

6.2 Explanation
The algorithm works as follows: 1. **Base Case**: If the array has one or no elements, it is already
sorted. 2. **Choose a Pivot**: Select a pivot element (e.g., the last element of the array). 3.
**Partition**: - Divide the array into three subarrays: - ‘less‘: Elements less than the pivot. -
‘equal‘: Elements equal to the pivot. - ‘greater‘: Elements greater than the pivot. 4. **Recur**:
- Recursively sort the ‘less‘ and ‘greater‘ subarrays. 5. **Combine**: - Concatenate the results of
the recursive calls with the pivot to produce the sorted array.

6.3 Time Complexity Analysis

The time complexity of Quicksort depends on the pivot selection:
• **Best Case (O(n log n))**: - The pivot splits the array into two equal halves at every step.
- Recurrence: T (n) = 2T (n/2) + O(n), which solves to O(n log n).
• **Worst Case (O(n2 ))**: - The pivot is always the smallest or largest element, resulting in
unbalanced partitions. - Recurrence: T (n) = T (n − 1) + O(n), which solves to O(n2 ).
• **Average Case (O(n log n))**: - The pivot splits the array into reasonably balanced parti-
tions on average.

14
6.4 Space Complexity
The space complexity depends on the recursion stack:
• **Average Case**: O(log n) for balanced partitions.

• **Worst Case**: O(n) for unbalanced partitions.

6.5 Example
If the input array is:
arr = [3, 6, 8, 10, 1, 2, 1]
The steps of Quicksort are:

• Choose pivot: 1.
• Partition into:
less = [], equal = [1, 1], greater = [3, 6, 8, 10, 2].

• Recursively sort ‘less‘ and ‘greater‘:

sorted = [] + [1, 1] + [2, 3, 6, 8, 10].

The final sorted array is:

[1, 1, 2, 3, 6, 8, 10].

15
7 Karger’s Contraction Algorithm for Global Minimum Cut
Karger’s Contraction Algorithm is a randomized algorithm used to compute the global minimum
cut of a connected, undirected graph. It achieves this by iteratively contracting edges and reducing
the graph until only two vertices remain.

7.1 Algorithm Description

Below is the pseudocode for Karger’s Contraction Algorithm:

Listing 8: Karger’s Contraction Algorithm

import random

def karger_min_cut ( graph ):

# While more than 2 vertices remain
while len ( graph ) > 2:
# Choose a random edge (u , v )
u , v = random . choice ([( u , v ) for u in graph for v in graph [ u ]])

# Merge vertex v into vertex u

graph [ u ]. extend ( graph [ v ])

# Replace all occurrences of v with u in the graph

for neighbor in graph [ v ]:
graph [ neighbor ] = [ u if x == v else x for x in graph [ neighbor ]]

# Remove self - loops

graph [ u ] = [ x for x in graph [ u ] if x != u ]

# Remove vertex v from the graph

del graph [ v ]

# Return the number of edges between the two remaining vertices

re maining_vertices = list ( graph . keys ())
return len ( graph [ remaining_vertices [0]])

7.2 Explanation
The algorithm works as follows: 1. **Input**: A connected, undirected graph represented as an
adjacency list. 2. **Random Edge Selection**: - Choose an edge (u, v) uniformly at random. 3.
**Contraction**: - Merge the two vertices u and v into a single vertex. - Update the adjacency
list to reflect the contraction: - Append the neighbors of v to u’s adjacency list. - Replace all
occurrences of v in the graph with u. - Remove any self-loops (edges where u = v). 4. **Repeat**:
- Continue contracting random edges until only two vertices remain. 5. **Output**: - The number
of edges between the two remaining vertices is the size of the minimum cut.

16
7.3 Time Complexity Analysis
The expected time complexity of the algorithm is O(n2 ):
• Each contraction step takes O(n) time to update the adjacency list.

• There are n − 2 contractions, leading to O(n2 ) in total.

However, to achieve a high probability of finding the minimum cut, the algorithm must be
repeated multiple times, leading to a total complexity of O(n2 log n) with high probability.

7.4 Space Complexity

The space complexity is O(n + m), where n is the number of vertices and m is the number of edges
in the graph.

7.5 Randomization and Success Probability

Karger’s algorithm is a randomized algorithm. The probability of finding the exact minimum cut
in one run is at least 1/ n2 , where n is the number of vertices. To boost the probability of success

to a high constant (e.g., 1 − 1/e), the algorithm must be repeated O(log n) times.

7.6 Example
Consider the following input graph:

Vertices: {A, B, C, D} Edges: {(A, B), (A, C), (B, C), (B, D), (C, D)}
Steps of the algorithm: 1. Randomly select an edge, e.g., (A, B), and contract A and B into a
single vertex. 2. Update the graph and remove self-loops. 3. Repeat until two vertices remain.
The minimum cut is the number of edges between the final two vertices.

7.7 Summary
Karger’s Contraction Algorithm provides an elegant and simple way to compute the global minimum
cut of a graph using randomization. By repeating the algorithm a sufficient number of times, the
minimum cut can be found with high probability.

17
8 Random Walk Algorithm for Maze Navigation
The Random Walk algorithm is a simple probabilistic algorithm used to navigate a graph or a
maze. It selects neighboring vertices uniformly at random to explore the graph.

8.1 Algorithm Description

Below is the pseudocode for the Random Walk algorithm:
Listing 9: Random Walk Algorithm
def random_walk ( graph , start , target , max_steps ):
current = start
steps = 0

while current != target and steps < max_steps :

# Pick a random neighbor of the current vertex
neighbors = graph [ current ]
current = random . choice ( neighbors )
steps += 1

return current == target

8.2 Explanation
The algorithm works as follows: 1. **Input**: A graph G, an initial vertex u, a target vertex v,
and an optional limit on the number of steps. 2. **Random Walk**: - At each step, choose a
random neighbor of the current vertex. - Move to that neighbor. 3. **Termination**: - Stop if the
target vertex is reached or the maximum number of steps is exceeded. 4. **Output**: - Return
whether the target vertex was reached.

8.3 Time Complexity Analysis

The expected runtime of the Random Walk algorithm depends on the structure of the graph and
the distance between vertices:
• **Expected Time to Reach the Target (T (u, v))**: - For an edge (u, v), the expected time is
T (u, v) ≤ 2m − 1, where m is the number of edges. - For general graphs, the expected time
to traverse all nodes is T (u, ·) ≤ 2m(n − 1), where n is the number of vertices.
• **Space Complexity**: O(log n) to track the current vertex and a counter for the steps.

8.4 Properties and Observations

• **Uniformly Random Choices**: - The algorithm relies on selecting neighbors with equal
probability, ensuring simplicity.
• **Stopping Condition**: - The algorithm can terminate early if the target vertex is reached.
• **Spanning Tree Analysis**: - The expected time to traverse the graph is analyzed using the
concept of a spanning tree.

18
8.5 Example
Consider a simple undirected graph with 6 vertices:

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

Starting at vertex 1 and trying to reach vertex 6:

1. Pick a random neighbor of 1 (e.g., vertex 2 or 3).
2. Continue picking random neighbors until vertex 6 is reached.
3. The expected time to traverse all nodes depends on the total edges and the graph’s connec-
tivity.

8.6 Comparison to Depth-First Search

• **DFS**: Deterministic with O(m) time and memory complexity.

• **Random Walk**: Probabilistic with O(nm) time complexity but O(log n) memory com-
plexity.

8.7 Applications
• **Maze Solving**: - Use random walks to find a path out of a maze.
• **Graph Exploration**: - Estimate connectivity and distances in a graph.
• **Markov Chains**: - Basis for modeling random processes on graphs.

19
9 WalkSAT Algorithm for Boolean Satisfiability (SAT)
The WalkSAT algorithm is a probabilistic, local search-based Monte Carlo algorithm used to solve
Boolean satisfiability problems (SAT). It is particularly effective for k-SAT formulas, where each
clause involves at most k variables.

9.1 Algorithm Description

Below is the pseudocode for the WalkSAT algorithm:

Listing 10: WalkSAT Algorithm

def walksat ( formula , max_flips , p =0.5):
# Randomly initialize a truth assignment
assignment = { var : random . choice ([ True , False ]) for var in formula . variables }

for _ in range ( max_flips ):

# Check if the formula is satisfied
if is_satisfied ( formula , assignment ):
return assignment

# Pick a random clause that is not satisfied

unsatisfied_clause = random . choice (
g et _u n sa t is fi e d_ c la us e s ( formula , assignment )
)

# With probability p , flip a random variable in the clause

if random . random () < p :
variable_to_flip = random . choice ( unsatisfied_clause . variables )
else :
# Otherwise , flip the variable that
# maximizes the number of satisfied clauses
variable_to_flip = c h o o s e _ b e s t _ v a r i a b l e _ t o _ f l i p ( unsatisfied_clause ,
formula , assignment )

# Flip the variable

assignment [ variable_to_flip ] = not assignment [ variable_to_flip ]

return " FAIL " # Return failure if no solution is found

9.2 Explanation
The algorithm works as follows: 1. **Initialization**: - Start with a random assignment of truth
values to variables. 2. **Main Loop**: - Check if the current assignment satisfies the formula. -
If not, pick a random clause that is unsatisfied. - Flip a variable in the clause: - With probability
p, flip a random variable. - Otherwise, flip the variable that maximizes the number of satisfied
clauses. 3. **Termination**: - Stop when a satisfying assignment is found or when the maximum
number of flips is reached. 4. **Output**: - Return the satisfying assignment if found; otherwise,
return ”FAIL.”

20
9.3 Time Complexity Analysis
The time complexity of WalkSAT is O(max flips · k):
• **Per Flip**: - Evaluating the unsatisfied clauses and flipping a variable takes O(k) opera-
tions, where k is the maximum clause length.

• **Total**: - For max flips iterations, the total complexity is O(max flips · k).
The algorithm is efficient for practical instances, even with a large number of variables and
clauses.

9.4 Probabilistic Behavior and Success Guarantee

• **Probability of Success**: - If the formula has a satisfying assignment, the probability of
finding it in one execution depends on the choice of p, the structure of the formula, and the
number of flips.

• **Boosting Success Probability**: - The success probability can be amplified by repeating

the algorithm multiple times.

9.5 Example
Consider the formula:

F = (x1 ∨ x2 ∨ ¬x3 ) ∧ (¬x1 ∨ x3 ) ∧ (x2 ∨ ¬x3 )

Steps: 1. Start with a random assignment, e.g., (x1 , x2 , x3 ) = (0, 1, 0). 2. Identify unsatisfied
clauses, e.g., (x1 ∨ x2 ∨ ¬x3 ) is unsatisfied. 3. Flip a variable in the clause, e.g., flip x1 , resulting
in (1, 1, 0). 4. Repeat until the formula is satisfied or the maximum number of flips is reached.

9.6 Comparison to Other Algorithms

• **Brute Force**: - Tries all 2n assignments, with exponential time complexity.

• **WalkSAT**: - Uses randomization and local search, with expected polynomial-time per-
formance for many practical problems.
• **Modern SAT Solvers**: - Combine local search with other techniques to handle much larger
formulas efficiently.

9.7 Applications
WalkSAT is widely used in:
• Hardware and software verification.

• Solving planning problems.

• SAT-based optimization and constraint satisfaction.

21
10 Union-Find Algorithm with Path Compression and Amor-
tization
The Union-Find algorithm is a data structure used to efficiently manage and query disjoint sets.
It supports two primary operations: - **Find**: Determine which set a particular element belongs
to. - **Union**: Merge two sets into one.
With the use of path compression and union by rank, the amortized time complexity becomes
nearly constant per operation.

10.1 Algorithm Description

Below is the pseudocode for the Union-Find algorithm:

Listing 11: Union-Find Algorithm with Path Compression

# Initialize parent and rank arrays
def initialize ( n ):
parent = list ( range ( n )) # Each element is its own parent
rank = [0] * n # Initial rank of each set is 0
return parent , rank

# Path Compression
def find ( parent , x ):
if parent [ x ] != x :
parent [ x ] = find ( parent , parent [ x ]) # Point directly to root
return parent [ x ]

# Union by Rank
def union ( parent , rank , x , y ):
root_x = find ( parent , x )
root_y = find ( parent , y )

if root_x != root_y : # Only union if in different sets

if rank [ root_x ] > rank [ root_y ]:
parent [ root_y ] = root_x
elif rank [ root_x ] < rank [ root_y ]:
parent [ root_x ] = root_y
else :
parent [ root_y ] = root_x
rank [ root_x ] += 1

10.2 Optimization Techniques

1. **Path Compression**: - During the ‘find‘ operation, all nodes along the path to the root are
directly linked to the root. - This flattens the structure of the tree, reducing the time for future
operations.
2. **Union by Rank**: - Attach the smaller tree to the root of the larger tree based on the
rank (height). - This keeps the trees shallow and reduces the worst-case time complexity of ‘find‘.

22
10.3 Time Complexity Analysis
The amortized time complexity of a sequence of m union and find operations on a forest with n
elements is O(m log∗ n):
• **Log-Star Function (log∗ n)**: - log∗ n is the number of times the logarithm function must
be applied before the result is less than or equal to 1. - log∗ 2 = 1, log∗ 4 = 2, log∗ 16 = 3, and
so on. - In practice, log∗ n is extremely small (e.g., log∗ 1019 ≈ 5).
• This results in **near-constant time complexity** for practical purposes.

10.4 Amortized Analysis Strategy

To analyze the amortized cost: 1. **Path Compression** ensures that each node points directly to
its root, reducing the effective height of the tree. 2. **Union by Rank** ensures the tree remains
balanced by attaching smaller trees to larger ones. 3. The combination of these techniques ensures
that the total number of parent changes is bounded by O(m log∗ n).

10.5 Applications
The Union-Find algorithm is widely used in:
• **Kruskal’s Algorithm** for finding the minimum spanning tree.

• **Connected Components** in a graph.

• **Dynamic Connectivity** queries in evolving graphs.

10.6 Example
Consider a graph with 5 vertices: {0, 1, 2, 3, 4}.
1. Initialize: ‘parent = [0, 1, 2, 3, 4], rank = [0, 0, 0, 0, 0]‘.
2. Perform unions: - ‘union(0, 1)‘ → ‘parent = [0, 0, 2, 3, 4]‘, ‘rank = [1, 0, 0, 0, 0]‘. - ‘union(1,
2)‘ → ‘parent = [0, 0, 0, 3, 4]‘, ‘rank = [1, 0, 0, 0, 0]‘.

3. Perform finds: - ‘find(2)‘ → Path compression updates ‘parent = [0, 0, 0, 3, 4]‘.

10.7 Properties
• **Path compression** ensures every node points directly to the root, reducing future ‘find‘
calls.
• **Union by rank** ensures the trees remain shallow.
• Combined, these techniques yield excellent amortized performance.

23
11 Lempel-Ziv-Welsh (LZW) Compression Algorithm
LZW compression is a lossless data compression algorithm that builds a dictionary of substrings
dynamically as it encodes the input. It is efficient for repetitive data and operates in a single pass.

11.1 Algorithm Description

Below is the pseudocode for LZW compression:

Listing 12: LZW Compression

def lzw_compress ( input_string ):
# Initialize the dictionary with single - character strings
dictionary = { chr ( i ): i for i in range (256)}
dict_size = 256
prefix = " "
compressed_data = []

for char in input_string :

combination = prefix + char
if combination in dictionary :
prefix = combination
else :
compressed_data . append ( dictionary [ prefix ])
dictionary [ combination ] = dict_size
dict_size += 1
prefix = char

if prefix :
compressed_data . append ( dictionary [ prefix ])

return compressed_data

11.2 Explanation
1. **Initialization**: - The dictionary starts with all single-character strings. 2. **Encoding**: -
For each character in the input, check if the current string (‘prefix + char‘) exists in the dictionary.
- If it exists, continue building the string. - If it doesn’t, output the code for the prefix, add the
new string to the dictionary, and reset the prefix. 3. **Output**: - Output the remaining string if
any.

11.3 Decoding
Decoding reconstructs the dictionary dynamically as the encoded data is processed. An exceptional
case occurs when a new code needs to be inferred from the existing dictionary.

Listing 13: LZW Decompression

def lzw_decompress ( compressed_data ):
# Initialize the dictionary with single - character strings

24
 dictionary = { i : chr ( i ) for i in range (256)}
dict_size = 256
prefix = chr ( compressed_data . pop (0))
decompressed_data = [ prefix ]

for code in compressed_data :

if code in dictionary :
entry = dictionary [ code ]
elif code == dict_size :
entry = prefix + prefix [0]
else :
raise ValueError ( " Invalid ␣ compressed ␣ data " )

decompressed_data . append ( entry )

dictionary [ dict_size ] = prefix + entry [0]
dict_size += 1
prefix = entry

return ’ ’. join ( decompressed_data )

11.4 Applications
- Used in tools like ‘gzip‘ and GIF image compression. - Effective for data with repetitive patterns.
—

12 Huffman Encoding Algorithm

Huffman encoding is a greedy algorithm that generates prefix-free binary codes for symbols based
on their frequencies. It minimizes the weighted path length of a binary trie, achieving optimal
lossless compression.

12.1 Algorithm Description

Below is the pseudocode for Huffman encoding:

Listing 14: Huffman Encoding

from heapq import heappush , heappop

def huffman_encoding ( frequencies ):

# Create a priority queue for the frequencies
heap = [[ weight , [ symbol , " " ]] for symbol , weight in frequencies . items ()]
while len ( heap ) > 1:
low1 = heappop ( heap )
low2 = heappop ( heap )
for pair in low1 [1:]:
pair [1] = ’0 ’ + pair [1]
for pair in low2 [1:]:
pair [1] = ’1 ’ + pair [1]

25
 heappush ( heap , [ low1 [0] + low2 [0]] + low1 [1:] + low2 [1:])

return sorted ( heappop ( heap )[1:] , key = lambda p : ( len ( p [ -1]) , p ))

# Example input : { ’ a ’: 11 , ’b ’: 4 , ’c ’: 3 , ’d ’: 3 , ’r ’: 4 , ’! ’: 1}

12.2 Explanation
1. **Build a Frequency Table**: - Count the occurrences of each symbol in the input. 2. **Con-
struct a Binary Trie**: - Use a priority queue to repeatedly combine the two least frequent nodes
into a single parent node. 3. **Generate Codes**: - Traverse the binary trie to assign binary codes
to each symbol.

12.3 Decoding
To decode a Huffman-encoded string, traverse the binary trie using the bits of the encoded string
until reaching a leaf node.

12.4 Properties
- **Prefix-Free Codes**: - No code is a prefix of another, ensuring unique decodings. - **Optimal-
ity**: - Produces the shortest average encoding length for a given symbol distribution.

12.5 Applications
- Widely used in compression formats like JPEG, PNG, and MP3. - Useful for transmitting data
efficiently in communication systems.
—

13 Comparison of LZW and Huffman Encoding

• **LZW**: - Efficient for repetitive patterns. - Builds a dictionary dynamically during encod-
ing. - One-pass algorithm.
• **Huffman**: - Exploits frequency differences in symbols. - Requires two passes: one to
compute frequencies, and another to encode. - Produces optimal prefix-free codes.

13.1 Summary
Many compression systems, such as ‘gzip‘, combine both algorithms: first applying LZW to capture
repetitions, and then Huffman encoding to optimize based on symbol frequencies.

26