The greedy method and dynamic programming both solve optimization problems but differ in approach. Greedy algorithms make a series of locally optimal choices with the aim of finding a global optimum, sometimes failing for complex problems since they do not consider future consequences. Dynamic programming, on the other hand, breaks problems into subproblems, solves each subproblem once, and stores solutions to avoid recomputation, suitable for problems exhibiting optimal substructure and overlapping subproblems. Greedy algorithms are preferable when problems can be divided into stages with a guaranteed optimal local choice, such as in finding a minimum spanning tree. Dynamic programming is more appropriate when such guarantees cannot be made or need comprehensive exploration, like in the 0/1 knapsack problem .

The branch and bound technique solves the traveling salesman problem by exploring decision tree branches and eliminating paths more expensive than the current best. It begins with the full list of cities, branching by selecting each city for the current route, and calculating a lower bound cost for each partial route. If a partial route's cost exceeds the best known route, it's discarded. This approach prunes the search tree, reducing computational costs. As an example, suppose the cost for the first few visits in a tour exceeds a known complete tour cost; the algorithm backtracks early to explore alternate routes, optimizing through bounding and traversing in a systematic way .

Strassen's algorithm is a recursive divide-and-conquer algorithm for matrix multiplication, which reduces the number of multiplications needed from the conventional O(n^3) to approximately O(n^2.81). This improvement is achieved by breaking down each matrix into smaller sub-matrices and performing multiplications using only 7 instead of 8 recursive matrix multiplications and additional addition operations. Its significance lies in its improved efficiency for large matrices despite increased complexity in implementation. For example, multiplying two 2x2 matrices using Strassen's algorithm requires fewer arithmetic operations, demonstrating the reduction in computational overhead .

Asymptotic notation provides a framework for assessing algorithm performance in terms of time and space complexities. It allows us to describe the limiting behavior of an algorithm's resource usage as the input size grows. The primary forms of asymptotic notation include Big O (O), which describes the upper bound, Theta (Θ) for tight bounds, and Omega (Ω) for the lower bound. Understanding these notations is critical for comparing the efficiency of different algorithms across varied input sizes, allowing for informed decision-making in algorithm design .

A procedure must meet certain criteria to be considered an algorithm: definiteness (each step must be clear and unambiguous), finiteness (it must terminate after a finite number of steps), input (zero or more inputs are supplied), output (one or more outputs are produced), and effectiveness (all operations must be sufficiently basic). These criteria ensure that an algorithm is well-defined and can be implemented effectively to solve computational problems. Defining the criteria helps in standardizing the design process, ensuring that the result is computationally feasible and reliable .

The LC (Least Cost) branch and bound algorithm advances combinatorial problem-solving by selecting nodes with the least estimated cost to explore further, ensuring more promising paths are prioritised over less promising ones. This results in faster convergence to an optimal solution as the search is guided by cost-conscious path selection rather than unoptimized exploration. In contrast, basic branch and bound might explore nodes systematically without cost guidance, potentially examining numerous less-effective paths. LC improves efficiency in situations like identifying the shortest path or solving optimizations like the traveling salesman problem, where cost-effectiveness is crucial .

Deterministic algorithms operate with a predictable set of instructions leading to a single outcome for each input, suitable for problems where precise solutions are necessary—such as within database transactions. Non-deterministic algorithms explore multiple possibilities simultaneously, typical in simulation or exploratory scenarios, such as genetic algorithms or automated reasoning. These algorithms are theoretical constructs more than practical implementations, expressing parallel computation capabilities often used in decision problems where exhaustive search is practical, such as the satisfiability problem. Practical non-determinism is often implemented through randomization or parallelization techniques .

Direct recursion occurs when a function calls itself directly. For example, the classical Fibonacci sequence where a function calls itself to calculate the subsequent number in the sequence. Indirect recursion involves a sequence of function calls where eventually, the original function is called. An example is functions A() and B() where A() calls B() and B() calls A(). Both forms allow problems to be broken down into simpler sub-problems and can be used to solve problems that are naturally recursive, such as those involving hierarchical data structures .

The time complexity of Merge Sort is O(n log n) because it recursively divides the input list in half and then merges the sorted halves. The recursive tree structure helps illustrate this process: each level of the tree represents a division, and the number of levels is logarithmic relative to the input size. Each level requires O(n) operations to merge the lists back together. This efficient division and merging process make Merge Sort particularly suitable for large lists, offering better performance than simpler algorithms like insertion or bubble sort for large datasets .

The assumption P ≠ NP implies that not all problems verifiable in polynomial time can be solved in polynomial time, affecting computational theory significantly. It suggests a barrier between problems easily checkable (NP) and those solvable (P), influencing how algorithms are developed as problems classified as NP-complete cannot have efficient polynomial-time solutions assuming P ≠ NP. This leads to reliance on heuristic or approximation algorithms for NP-complete problems, guiding research towards identifying more tractable subproblems or special cases where polynomial-time solutions may exist. The assumption continues to prompt exploration in computational limits and algorithmic innovation .