1.3. Techniques for Solving 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. In most algorithms that we will see we need to find a suitable mathematical model. One of these will be graphs. We need a way of representing the concepts of these models in our algorithm. For this, we need appropriate data structures. And of course typically in order to solve a problem we need to break it down into manageable sub problems.

Problem decomposition is a crucial skill in algorithm design. It involves breaking a complex problem into smaller, manageable parts that are easier to solve. By modeling the problem mathematically, we can better understand its components. Graphs are often used as models to represent relationships between elements distinctly. Appropriate data structures, such as arrays or trees, are also required for effectively manipulating the data. The goal is to simplify the problem-solving process, making it less overwhelming and more systematic.

Imagine you're planning a large family reunion. Instead of trying to organize everything at once, you break it down into smaller tasks: first choose the date, then decide on the venue, next prepare the guest list, etc. Each of these smaller tasks is easier to handle and contributes to the overall success of the reunion.

Over the course of time, many generic techniques have been developed to solve the large number of problems. And we will see examples of how these techniques can be applied to very standard problems that we come across repeatedly. Among the techniques are divide and conquer, greedy algorithms, and dynamic programming.

Several well-established techniques have emerged for tackling a variety of problems in algorithms. Key among these are:

1. Divide and Conquer: This technique involves breaking a problem into smaller parts, solving each independently, and then combining solutions.
2. Greedy Algorithms: These algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.
3. Dynamic Programming: This strategy is used when a problem can be broken down into overlapping subproblems, where solutions to subproblems can be stored and reused to avoid redundant calculations. Each technique has its own applicable scenarios and offers different advantages in terms of efficiency.

Think of a jigsaw puzzle. With the divide and conquer method, you might group pieces by color or edge vs. middle pieces (breaking the problem down). A greedy algorithm would mean you look for the pieces that fit next into your current section of the puzzle, without considering future placements. Dynamic programming is like noting which pieces fit where as you go along, so you don’t keep trying pieces that don’t work.

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 strategy is tailored for problems that can be split into smaller, non-overlapping subproblems. For instance, in sorting algorithms like merge sort, the array is divided into two halves, each sorted independently, and then combined to create a fully sorted array. This approach significantly reduces the complexity of the problem and allows for efficient computing. The main steps involve dividing the problem, conquering by solving the smaller subproblems, and then combining the results to achieve the final solution.

Imagine you are assembling a large piece of furniture. Instead of trying to put the whole thing together at once, you first assemble the legs, then the tabletop, and finally attach the legs to the tabletop. Each assembly step focuses on smaller tasks, eventually leading to the complete piece without confusion.

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. These kind of greedy algorithms are there. It is important to know how to prove such an algorithms correct. But if a greedy algorithms does exists, it is typically much more efficient than other types of algorithms.

Greedy algorithms work on the principle of making the best choice at each step, believing that these local optimal choices will lead to a global optimum. These algorithms tend to be more efficient because they don't require exploring all possible solutions. However, it's essential to validate that the greedy choice leads to an optimal solution for the given problem. Proving the correctness of greedy algorithms can sometimes be challenging, and there are problems where greedy algorithms do not yield the optimal solution.

Consider a vending machine: if you want to buy a snack that costs 80 cents and you have a 1-dollar bill, the 'greedy' choice is to seek the least number of coins back (like getting a quarter and a dime) rather than considering all possible options of change. This direct approach resonates with how greedy algorithms typically operate.

When greedy does not work, we need a systematic way of exploring all the possibilities and choosing the best one. In this process, sometimes we have to discard overlapping problems and make sure that we do not waste fully recomputed things. So, this is covered by the concept of dynamic programming.

Dynamic programming is a method used to solve problems that exhibit overlapping subproblems and optimal substructure properties. It involves breaking a problem down into simpler subproblems, solving each just once, and storing their solutions, typically using a table, to avoid recalculating them. Unlike greedy algorithms that might fail for some problems, dynamic programming ensures that we find the best overall solution by keeping track of all possible states.

Think about planning multiple steps for a long road trip where you need to consider distance, gas stations, and rest breaks. Instead of recalculating the best route every time you consider a stop, you keep a record of the best distances between points in a table. This way, you can efficiently choose your stops without repeatedly calculating the entire route.

--