Sorting algorithms are a classic example of polynomial time problems. These algorithms, such as Quick Sort and Merge Sort, can sort a list of elements in O(n log n) time.


public class QuickSort {
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1); 
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
    void sort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }
}

Explanation

The Quick Sort algorithm works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Polynomial Time Problems - Graph Traversal

Graph Traversal

Graph traversal algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS) are polynomial time problems. They explore the nodes and edges of a graph in O(V + E) time.


import java.util.*;

public class BFS {
    private LinkedList adjLists[];
    private boolean visited[];

    BFS(int vertices) {
        adjLists = new LinkedList[vertices];
        visited = new boolean[vertices];
        for (int i = 0; i < vertices; i++)
            adjLists[i] = new LinkedList();
    }

    void addEdge(int src, int dest) {
        adjLists[src].add(dest);
    }

    void BFS(int vertex) {
        LinkedList queue = new LinkedList();
        visited[vertex] = true;
        queue.add(vertex);

        while (queue.size() != 0) {
            vertex = queue.poll();
            System.out.print(vertex + " ");

            Iterator i = adjLists[vertex].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

Explanation

BFS is a graph traversal method that explores all the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. It uses a queue data structure to keep track of the nodes to be explored next.

Polynomial Time Problems - Pathfinding Algorithms

Pathfinding Algorithms

Pathfinding algorithms like Dijkstra's Algorithm are used to find the shortest path between nodes in a graph. These algorithms operate in polynomial time, typically O(V^2).


import java.util.*;

public class Dijkstra {
    static final int V = 9;
    int minDistance(int dist[], Boolean sptSet[]) {
        int min = Integer.MAX_VALUE, min_index = -1;
        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        return min_index;
    }

    void dijkstra(int graph[][], int src) {
        int dist[] = new int[V];
        Boolean sptSet[] = new Boolean[V];
        for (int i = 0; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }
        dist[src] = 0;
        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, sptSet);
            sptSet[u] = true;
            for (int v = 0; v < V; v++)
                if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }
    }
}

Explanation

Dijkstra's algorithm finds the shortest paths between nodes in a graph, which may represent, for example, road networks. It works by iteratively selecting the node with the smallest tentative distance, updating its neighbors, and marking it as processed.

Polynomial Time Problems - Dynamic Programming

Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure.


public class Fibonacci {
    static int fib(int n) {
        int f[] = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= n; i++)
            f[i] = f[i - 1] + f[i - 2];
        return f[n];
    }
}

Explanation

The Fibonacci sequence is a classic example of dynamic programming. Instead of recalculating Fibonacci numbers multiple times, dynamic programming stores the results of subproblems (in this case, Fibonacci numbers) to avoid redundant calculations.

Polynomial Time Problems - Matrix Multiplication

Matrix Multiplication

Matrix multiplication is a fundamental operation in many algorithms, including those in graphics and scientific computing. The standard algorithm runs in O(n^3) time complexity.


public class MatrixMultiplication {
    static void multiply(int A[][], int B[][], int C[][], int n) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    C[i][j] += A[i][k] * B[k][j];
    }
}

Explanation

Matrix multiplication involves multiplying rows of the first matrix by columns of the second matrix and summing the results. The algorithm iterates over each element and performs the necessary multiplications and additions.