1.2.4. Modelling Problems

An important part of problem solving in any domain and in particular algorithms is the art of modelling the problem at a suitable level of detail.

When tackling problems, especially in algorithms, it's crucial to represent the problem accurately. 'Modelling' involves creating a simplified version of the problem that captures its essential characteristics. This helps in understanding the structure and dynamics of the problem, which is vital for finding an effective solution.

Think of modelling like creating a blueprint before building a house. Just as a blueprint outlines the key features and layout of a house, modelling outlines the critical aspects of a problem that need addressing.

In most algorithms that we will see we need to find a suitable mathematical model. One of these will be graphs.

Mathematical models help us represent complex problems in a more manageable form. For instance, in many cases, graphs serve as a powerful model. A graph consists of nodes (or vertices) that are connected by edges, making it useful for representing relationships and connections, such as in networking or pathfinding problems.

Imagine you are planning a trip and need to visit multiple cities. A map where cities are nodes and roads are edges is a graph representation. This helps you easily visualize and determine the best route.

Of course typically in order to solve a problem we need to break it down into manageable sub problems.

Complex problems can often be overwhelming. By breaking a larger problem into smaller, more manageable subproblems, we can tackle each part systematically. This strategy not only simplifies the problem-solving process but also allows us to reuse solutions to subproblems in conjunction with the original problem.

Consider baking a cake. Instead of trying to bake an entire cake all at once, you break it down: first gather the ingredients, then mix them, bake the cake, and finally frost it. Each step builds toward the final product.

Over the course of time, many generic techniques have been developed to solve the large number of problems.

In computer science, generic techniques are broad strategies that can be applied to various problems. For example, the divide and conquer method splits problems into non-overlapping parts, solves each part independently, and then combines the results. Identifying and applying these techniques can significantly enhance the problem-solving process.

It's like assembling a puzzle. You separate pieces by color or edges (divide the problem) and work on each subsection before putting everything together to solve the entire puzzle.

Among the techniques are divide and conquer. Where, we break up the problem into individual components which do not overlap with each other and then combine these solutions in order to get the solution for the overall problems.

The divide and conquer method focuses on dividing the problem into smaller isolated parts, solving each part independently, and then merging the results. This approach is efficient as it allows for more straightforward solutions and can reduce the overall complexity of the problem.

Think about organizing a large event. Instead of handling everything at once, you delegate tasks to different teams (like catering, invitations, and entertainment). Each team works separately, and once they complete their tasks, you piece everything together for the final event.

In some cases, we can identify a strategy which looks at the local state of the problem and chooses an optimal path and arrives at the final solution without having to look at all possibilities.

Greedy algorithms make decisions based on the best available option at each step, without considering future consequences. This approach works well for specific types of problems where a local optimum leads to a global optimum.

Imagine walking in a maze where at every junction you choose the direction that seems to get you closest to the exit. You make the best choice available each time, hoping to find the quickest path out of the maze.

When greedy does not work, we need a systematic way of exploring all the possibilities and choosing the best one.

Dynamic programming is a method used when problems can be broken down into overlapping subproblems. Instead of recalculating solutions for these subproblems, we store them to avoid redundancy. This technique is particularly useful for optimization problems where previous solutions provide critical insights into the best possible outcome.

Consider someone planning their route for many stops. Instead of calculating the best path for each stop from scratch each time (which would be inefficient), they save the best paths taken previously so they can refer back, saving time and effort.

--