Unlike all the other sections, the subsections here do not share a unifying concept1. Rather, each topic represents a unique algorithmic technique. This can be challenging because readers need to quickly shift between disparate mental states. However, it’s also highly engaging for the same reason. Mastering the algorithms in this section will prepare students to tackle a wide variety of real-world applications.
One of the challenges associated with the software profession is the sheer magnitude of the problem space. Every application domain (systems, embedded, finance, commerce, etc…) appears to be unique from a computing perspective. However, upon closer investigation, several common patterns start to emerge. A relatively meager quantity of algorithms can solve a plethora of problems.
It’s rare to encounter an algorithm that’s solely appropriate for a single context. For instance, closest pair is applicable to collision detection (air traffic control, CAD, gaming, robotics, etc…) as well as combinatorial optimization (NP-hard problems) even though they appear to be totally unrelated. This is why it’s absolutely crucial to cultivate a generous algorithm repertoire. That’s the purpose of this section: to endow your algorithm toolbox.
As has been stated repeatedly throughout this material, it’s highly unlikely that a software professional will need to implement an algorithm exactly as laid out here. However, it’s almost certain that they will need to implement some variation. Unlike the previous sections, these algorithms are not available as high-level programming language primitives. Readers are encouraged to keep this in mind: they need to understand the concepts well enough to apply them in various non-obvious contexts.
Source Code
Relevant Directories:
- quick_select
- matrix_operations
- running_median
- closest_pair
- inversion_count
- schedule_optimizer
- huffman_codes
- sequence_alignment