Dynamic programming solves the Traveling Salesperson Problem (TSP) by using a state subset approach. For 4 cities and a cost matrix, represent states by sets of visited cities and the current city. Define a recursive function optimally combining subproblems, where the state cost of visiting each city is minimized recursively. Initialize with base cases where only one city is visited, and iteratively fill a table that tracks minimum path costs, ultimately reconstructing the shortest cycle from accumulated data .

The Floyd-Warshall algorithm is applied to find the shortest paths between all pairs of vertices in a graph by iteratively improving path estimates. Using a distance matrix, each entry represents direct distances, updated iteratively by considering intermediate vertices. Initially, set the diagonal to zero (self-loops) and use given weights, replacing '∞' for absence of direct paths. Proceed by updating distances in a triple nested loop structure, allowing paths through intermediate vertices to reduce path cost, thus ensuring optimality .

Dijkstra’s algorithm calculates the shortest path by initializing distances from the start node, A, to all nodes as infinity, setting A to 0. Use a priority queue to explore nodes with the smallest known distances. Update neighboring node distances if a shorter path is found through the current node. Progressively mark nodes as 'visited' when all potential paths are evaluated. Repeatedly extract and update, ensuring paths are optimized with non-negative weights. For A to D with edges: A-B:1, A-C:4, B-C:2, B-D:6, C-D:3, the algorithm finds paths by expanding from A iteratively .

Kruskal’s algorithm finds the Minimum Spanning Tree (MST) by sorting all edges by weight in non-decreasing order and adding the shortest edge that doesn't form a cycle. For vertices {A, B, C, D}, and edges: A-B(1), A-C(3), B-C(1), B-D(4), C-D(2), first sort edges. Starting with the lightest edges, iteratively add edge A-B, B-C, and C-D to the MST set. Avoid any edge if it creates a cycle, leveraging disjoint set/union-find structures to track and ensure no cycles occur .

For job sequencing with deadlines = {2, 1, 2, 1} and profits = {100, 19, 27, 25}, maximize profit by sorting jobs in descending order of profit. Allocate each job to its latest possible slot before its deadline—an approach inspired by greedy techniques. Prioritize higher profit jobs and adjust placement iteratively, subject to availability and deadlines. This ensures maximum profitability by exploiting the most urgent and profitable opportunities first .

NP-Complete problems are a subset of NP problems that are both in NP and NP-Hard. NP refers to 'nondeterministic polynomial time', where solutions can be verified quickly, although no quick solution is known. NP-Complete problems, like SAT, can be translated from any other NP problem in polynomial time, signifying equivalence in complexity. NP-Hard problems, like the Halting Problem, are at least as hard as NP-Complete problems but don’t necessarily belong to NP because they may lack quick solution verification. The distinction lies primarily in the verification time and applicable transformations .

Tree traversal techniques are applied to binary trees by visiting nodes in a specific sequence. In-order traversal visits the left subtree, root, then right subtree, useful for sorting binary search trees. Pre-order visits the root node, then left and right subtrees, ideal for copying trees or expression tree evaluations. Post-order visits the left and right subtrees, then root, helpful for deleting trees or postfix expression evaluations. Each technique has distinct applications based on the desired node ordering or processing sequence .

The 0/1 Knapsack problem can be solved using dynamic programming by building a table that considers each item and possible capacities up to the maximum specified. For weights = {2, 3, 4}, profits = {4, 6, 7}, and a capacity = 5, use a tabular method to optimize the selection of items to maximize profit without exceeding the capacity. The table entries represent the maximum profit for specific item indices and capacities, where each entry is computed as the maximum of not taking or taking the current item, subject to the capacity constraint .

The fractional knapsack problem is efficiently solved using a greedy strategy by selecting items based on their profit-to-weight ratio. Sort items by this ratio in descending order. Starting from the highest ratio, take as much of each item’s weight as allows within the knapsack’s remaining capacity. If an item's full weight can fit, take the whole item; otherwise, take a fractional amount. This maximizes total profit by ensuring the highest value contribution for each unit of weight within capacity .

Branch and bound solves the TSP by exploring a tree of partial tours using depth-first search. For a cost matrix, represent states by partial tours, branching by adding unvisited cities. Use a cost function to calculate bound for each node and prune branches that exceed the current solution cost. Maintain the best known solution as a reference for pruning. Guide exploration effectively by estimating potential improvements, reducing the search space significantly .