Algorithms

3.

Algorithmic Design Paradigms

3.1.

Brute-Force Approach

3.1.1.

Exhaustive Search

3.1.1.1.

Generating All Possibilities

3.1.1.2.

Systematic Enumeration

3.1.1.3.

Time Complexity Considerations

3.1.1.4.

Space Complexity

3.1.2.

When to Use Brute-Force

3.1.2.1.

Small Problem Sizes

3.1.2.2.

Correctness Verification

3.1.2.3.

Baseline Solutions

3.1.3.

Applications and Examples

3.1.3.1.

3.1.3.2.

3.1.3.3.

Traveling Salesperson Problem

3.1.4.

3.1.4.1.

Exponential Time Complexity

3.1.4.2.

Scalability Issues

3.2.

Divide and Conquer

3.2.1.

The Divide-and-Conquer Strategy

3.2.1.1.

Problem Decomposition

3.2.1.2.

Dividing the Problem

3.2.1.2.1.

Balanced Division

3.2.1.2.2.

Unbalanced Division

3.2.1.3.

Conquering Subproblems

3.2.1.3.1.

3.2.1.3.2.

Recursive Solutions

3.2.1.4.

Combining Solutions

3.2.1.4.1.

Merge Operations

3.2.1.4.2.

Result Aggregation

3.2.2.

3.2.2.1.

Problem Analysis

3.2.2.2.

Division Strategy

3.2.2.3.

Base Case Identification

3.2.2.4.

Combination Method

3.2.3.

Analysis of Divide-and-Conquer Algorithms

3.2.3.1.

Recurrence Relations

3.2.3.2.

Master Theorem Application

3.2.3.3.

Time Complexity Analysis

3.2.3.4.

Space Complexity Analysis

3.2.4.

Classic Examples

3.2.4.1.

3.2.4.1.1.

Division Process

3.2.4.1.2.

Merging Process

3.2.4.1.3.

3.2.4.2.

3.2.4.2.1.

3.2.4.2.2.

Pivot Selection

3.2.4.2.3.

3.2.4.3.

3.2.4.4.

Maximum Subarray Problem

3.2.4.5.

Closest Pair of Points

3.2.4.6.

Strassen's Matrix Multiplication

3.2.5.

Advantages and Disadvantages

3.2.5.1.

Parallelization Potential

3.2.5.2.

3.2.5.3.

Implementation Complexity

3.3.

Greedy Algorithms

3.3.1.

Greedy Strategy

3.3.1.1.

Local Optimal Choices

3.3.1.2.

Irrevocable Decisions

3.3.1.3.

Hope for Global Optimum

3.3.2.

3.3.2.1.

Greedy-Choice Property

3.3.2.1.1.

Verification Methods

3.3.2.2.

Optimal Substructure

3.3.2.2.1.

Relationship to Dynamic Programming

3.3.3.

Greedy Algorithm Design Steps

3.3.3.1.

Problem Analysis

3.3.3.2.

Greedy Choice Identification

3.3.3.3.

Subproblem Reduction

3.3.3.4.

Correctness Proof

3.3.4.

Proof Techniques

3.3.4.1.

Exchange Arguments

3.3.4.2.

Staying Ahead Arguments

3.3.4.3.

Cut-and-Paste Arguments

3.3.5.

Classic Problems

3.3.5.1.

Activity Selection Problem

3.3.5.1.1.

Problem Statement

3.3.5.1.2.

Greedy Strategy

3.3.5.1.3.

Correctness Proof

3.3.5.2.

Fractional Knapsack Problem

3.3.5.3.

3.3.5.3.1.

Optimal Prefix Codes

3.3.5.3.2.

Tree Construction

3.3.5.3.3.

Encoding and Decoding

3.3.5.4.

Minimum Spanning Tree

3.3.5.4.1.

Kruskal's Algorithm

3.3.5.4.2.

Prim's Algorithm

3.3.5.5.

Single-Source Shortest Paths

3.3.5.5.1.

Dijkstra's Algorithm

3.3.6.

When Greedy Fails

3.3.6.1.

Counterexamples

3.3.6.2.

0/1 Knapsack Problem

3.3.6.3.

Coin Change Problem

3.3.7.

Approximation Algorithms

3.3.7.1.

Performance Ratios

3.3.7.2.

Greedy Approximations

3.4.

Dynamic Programming

3.4.1.

3.4.1.1.

Overlapping Subproblems

3.4.1.1.1.

3.4.1.1.2.

Subproblem Graphs

3.4.1.2.

Optimal Substructure

3.4.1.2.1.

3.4.1.2.2.

Relationship to Greedy Algorithms

3.4.2.

Implementation Approaches

3.4.2.1.

3.4.2.1.1.

Top-Down Approach

3.4.2.1.2.

Recursive Implementation

3.4.2.1.3.

Cache Management

3.4.2.1.4.

Space Complexity

3.4.2.2.

3.4.2.2.1.

Bottom-Up Approach

3.4.2.2.2.

Table Construction

3.4.2.2.3.

Iterative Solutions

3.4.2.2.4.

Space Optimization

3.4.3.

3.4.3.1.

Problem Characterization

3.4.3.2.

Recursive Solution

3.4.3.3.

Subproblem Identification

3.4.3.4.

Recurrence Relation

3.4.3.5.

3.4.3.6.

Implementation Choice

3.4.4.

Classic Problems

3.4.4.1.

Fibonacci Numbers

3.4.4.1.1.

Naive Recursion

3.4.4.1.2.

Memoized Version

3.4.4.1.3.

Tabulated Version

3.4.4.1.4.

Space-Optimized Version

3.4.4.2.

Longest Common Subsequence

3.4.4.2.1.

Problem Definition

3.4.4.2.2.

Recurrence Relation

3.4.4.2.3.

Table Construction

3.4.4.2.4.

Solution Reconstruction

3.4.4.3.

0/1 Knapsack Problem

3.4.4.3.1.

Problem Statement

3.4.4.3.2.

Recurrence Relation

3.4.4.3.3.

3.4.4.3.4.

Space Optimization

3.4.4.4.

3.4.4.4.1.

Problem Definition

3.4.4.4.2.

3.4.4.4.3.

Recurrence Relation

3.4.4.5.

Coin Change Problem

3.4.4.5.1.

3.4.4.5.2.

3.4.4.6.

Longest Increasing Subsequence

3.4.4.7.

Matrix Chain Multiplication

3.4.4.7.1.

Parenthesization Problem

3.4.4.7.2.

Optimal Substructure

3.4.4.7.3.

3.4.5.

Advanced Topics

3.4.5.1.

Space Optimization Techniques

3.4.5.2.

Printing Solutions

3.4.5.3.

Multi-dimensional DP

3.4.5.4.

3.4.5.5.

DP with Bitmasks

3.5.

3.5.1.

Backtracking Concept

3.5.1.1.

State-Space Tree

3.5.1.2.

Systematic Search

3.5.1.3.

Pruning Unsuccessful Paths

3.5.2.

Algorithm Structure

3.5.2.1.

Recursive Framework

3.5.2.2.

3.5.2.3.

Constraint Checking

3.5.2.4.

Backtrack Operation

3.5.3.

Implementation Techniques

3.5.3.1.

Explicit State Representation

3.5.3.2.

Implicit State Representation

3.5.3.3.

Pruning Strategies

3.5.3.3.1.

Constraint Pruning

3.5.3.3.2.

3.5.4.

Classic Problems

3.5.4.1.

N-Queens Problem

3.5.4.1.1.

Problem Statement

3.5.4.1.2.

State Representation

3.5.4.1.3.

Constraint Checking

3.5.4.1.4.

Solution Counting

3.5.4.2.

Subset Sum Problem

3.5.4.2.1.

Problem Definition

3.5.4.2.2.

Backtracking Solution

3.5.4.2.3.

Pruning Optimizations

3.5.4.3.

3.5.4.3.1.

Problem Statement

3.5.4.3.2.

Backtracking Approach

3.5.4.4.

3.5.4.5.

Hamiltonian Path Problem

3.5.4.6.

Knight's Tour Problem

3.5.5.

Optimization Techniques

3.5.5.1.

Constraint Propagation

3.5.5.2.

Variable Ordering

3.5.5.3.

3.5.5.4.

Symmetry Breaking

3.5.6.

3.5.6.1.

Worst-Case Complexity

3.5.6.2.

Average-Case Analysis

3.5.6.3.

Pruning Effectiveness

3.6.

Branch and Bound

3.6.1.

3.6.1.1.

State-Space Tree

3.6.1.2.

Bounding Functions

3.6.1.2.1.

3.6.1.2.2.

3.6.1.3.

Pruning Strategies

3.6.1.3.1.

Bound-Based Pruning

3.6.1.3.2.

Dominance Pruning

3.6.2.

Algorithm Framework

3.6.2.1.

Node Selection Strategies

3.6.2.1.1.

Best-First Search

3.6.2.1.2.

Depth-First Search

3.6.2.1.3.

Breadth-First Search

3.6.2.2.

Bound Calculation

3.6.2.3.

Pruning Decisions

3.6.3.

Implementation Details

3.6.3.1.

Priority Queues

3.6.3.2.

State Representation

3.6.3.3.

Memory Management

3.6.4.

Classic Problems

3.6.4.1.

Traveling Salesperson Problem

3.6.4.1.1.

Problem Statement

3.6.4.1.2.

Bounding Functions

3.6.4.1.3.

3.6.4.2.

0/1 Knapsack Problem

3.6.4.2.1.

Fractional Relaxation

3.6.4.2.2.

Bound Calculation

3.6.4.3.

Job Assignment Problem

3.6.4.4.

Integer Linear Programming

3.6.5.

Comparison with Other Paradigms

3.6.5.1.

vs Backtracking

3.6.5.2.

vs Dynamic Programming

3.6.5.3.

vs Greedy Algorithms

Previous

2. Data Structures

Go to top

Next

4. Sorting and Searching Algorithms