Lesson Greedy algorithms
Greedy algorithms
- Greedy algorithms make the best possible choice at each step, aiming for an optimal solution, but they only work effectively for problems that exhibit the greedy choice property and optimal substructure. They are useful in various applications like minimizing the number of coins for change, scheduling non-overlapping activities, or wrapping lines of text to fit within a given width. Evelyn Berezin, known for inventing the first word processor, exemplifies the impact of computational solutions like these in practical tasks.
- Recommended reading:
- Greedy Algorithms: Choose the best option at each step, ensuring an optimal solution for specific types of problems.
- Evelyn Berezin: Pioneering physicist who invented the first word processor, leading to the development of modern word-processing software.
- Line Wrap Problem: Uses a greedy approach to break text into lines that fit the available page width.