This week we covered breadth first search, depth first search, brute force and exhaustive algorithms, and divide and conquer. I was curious about real world applications of BFS and DFS and learned that BFS is useful for GPS/mapping algorithms for finding the nearest instance of some destination. For example, finding the nearest gas station or restaurant. Since it walks outward from the start location, it guarantees an optimal solution. I learned that some forms of DFS are useful for dependency mapping for software trees like the Linux kernel. They also have clever ways of parallelizing operations. Bitbake builds the Linux kernel but it does it in multiple threads without stumbling and minimizing the time that any module has to wait for another module to build. I.e. it uses the build machine's resources efficiently.
I feel like brute force algorithms may be the way most of us initially approach a problem since it's so direct. That said, I think that divide and conquer algorithms are really interesting. I'm thinking that complex problems where d&c can be applied, they can really benefit from modern computer systems where multi-threading and multiprocessing are commonplace. I look forward to exploring merge sort next week.
No comments:
Post a Comment