Dynamic programming and the greedy method are both algorithmic paradigms used for optimization problems but they differ in approach. Dynamic programming solves problems by breaking them into overlapping subproblems and storing solutions to subproblems to avoid redundant computations, which is applicable in problems like the Knapsack problem or Fibonacci sequence. Greedy algorithms, on the other hand, make locally optimal choices at each step with the hope of finding a global optimum, suitable for problems such as Prim's or Kruskal's algorithm for MST. Unlike dynamic programming, the greedy method does not guarantee optimal solutions for all problems, but it is more efficient and simpler if applicable .

Cook's Theorem asserts that the Boolean satisfiability problem (SAT) is NP-complete, meaning it is both in NP and any problem in NP can be reduced to it in polynomial time. This theorem was groundbreaking as it provided the first known NP-complete problem, establishing a cornerstone for studying the class NP-complete. Its significance lies in the fact that solving or optimizing a solution for any NP-complete problem efficiently may lead to a solution for all problems within NP, thus influencing numerous fields from cryptology to optimization .

The graph coloring problem is challenging due to its NP-completeness, where the task is to assign colors to the vertices of a graph so that no two adjacent vertices share the same color, using the minimum number of colors. This complexity arises from the expansive number of possible color assignments to check for validity. A widely used algorithm is the backtracking approach, starting with an initial color assignment and using recursion to assign colors, backtracking whenever a color conflict arises. Although not polynomial, backtracking is practical for small graphs or when used with heuristics for color ordering .

Asymptotic notations provide a means to describe the running time or space requirement in terms of the input size, helping to evaluate an algorithm's efficiency when scaled. Big Oh (O) describes an upper bound on time; Omega (Ω) describes a lower bound; and Theta (Ɵ) gives a tight bound (both upper and lower). Graphically, these notations illustrate these bounds against input sizes on the x-axis and time/space amount on the y-axis. Big Oh is commonly used to describe worst-case scenarios, whereas Omega and Theta describe best-case and average-case scenarios respectively. This facilitates comparing different algorithms and making informed choices .

Quick Sort generally performs better on average with a time complexity of O(n log n), although its worst-case time complexity is O(n^2). However, with a proper choice of pivot, the worst-case is rare, and it typically handles in-place sorting without additional storage, making it space-efficient. Merge Sort, on the other hand, has a guaranteed time complexity of O(n log n) regardless of data input but requires additional space of O(n). Hence, Quick Sort can be more efficient in terms of runtime and space usage if the input is large and the pivot is chosen wisely, while Merge Sort offers stability and predictable performance .

The Branch and Bound method iteratively partitions the problem space into smaller subproblems using upper and lower cost bounds to prune suboptimal paths, thus systematically narrowing the search space for the optimal tour in the Travelling Salesperson Problem (TSP). By keeping track of the least bound cumulative cost routes, it can discard paths that will not yield minimal costs. Branch and Bound, although computationally intensive, effectively finds the exact solution to the TSP as it explores all potential tours while minimizing unnecessary computations by using bounds carefully .

The state space tree represents all possible placements of queens in the 4-Queens problem, where each node at the k-th level in the tree corresponds to a placement of k queens on the board. The bounding function is used to prune branches, eliminating suboptimal solutions (i.e., states where queens threaten each other) to efficiently find valid setups. Backtracking is employed to explore possible placements systematically, abandoning solutions that violate constraints early, which greatly reduces computational efforts by not visiting the entire solution space exhaustively .

Recurrence relations in Quick Sort are used to express its divide-and-conquer strategy: dividing the array and solving each partition. The recurrence relation T(n) = 2T(n/2) + Θ(n) describes Quick Sort when the pivot minimizes divisions, capturing the sum of two subproblem recursions and a linear scan for partitioning. In the best-case scenario, this relation simplifies, reflecting equal-size partitions resulting in a balanced tree of recursions yielding a best-case complexity of O(n log n) by solving the recurrence via the Master Theorem .

The FIFO Branch and Bound method constructs a state space tree breadth-first for the Traveling Salesperson Problem (TSP), sequentially exploring each level of decision nodes. Each node represents a city and an edge represents the cost of the route. The algorithm maintains a queue of nodes, expanding the current node by generating all possible successors, evaluating each's bound. Unproductive nodes (those exceeding a known solution or potential lower bound) are pruned. This systematic expansion using cost bounds ensures a thorough yet efficient search for the shortest possible tour solution .

A Minimum Spanning Tree (MST) of a connected, undirected graph is a tree that connects all the vertices together, without any cycles, and with the minimum possible total edge weight. Prim's algorithm is a popular method to find an MST. It starts from an arbitrary node and grows the spanning tree by adding the lowest weight edge from the tree to a vertex outside of it. This process continues until all vertices are included. Prim's algorithm efficiently finds the MST with a time complexity of O(V^2) using simple array data structures, which can be reduced to O(E log V) using priority queues .