Divide and Conquer Methods
This video delves deeper into divide and conquer algorithms. Some of these algorithms are recursive. Recursion is a way of decomposing a problem into smaller or simpler problems of the same type. We have discussed the base subproblem and the inductive subproblem when applying recursion. A third consideration is composition – namely, how will simpler subproblems be composed into a solution to the larger problem? Sometimes the decomposition is easy but the composition is hard; sometimes the reverse is true.
In this video, the lecturer uses complexity to compare algorithms – how does the number of steps in a solution to a problem grow as n grows, where n is the number of operations or data elements involved in the inductive step? Formally, that complexity approach is called Big 'O'. The lecturer presents two examples. The takeaway here is that designing and implementing algorithms involves tradeoffs: decomposition versus composition (as seen in the merge sort example), and tradeoff of storage space versus run-time (as seen in the hash function example).
Most of the concepts you encounter in programming languages are related to reusing algorithms or designs and implementations. These are categorized by complexity; for example, the merge sort example has n log n complexity. This helps us decide their appropriateness for certain kinds of problems. The lecture closes by showing how you can enhance the examples using exceptions and assertions (pre- and post-conditions), which were covered in Unit 4 of our course. They help us handle different exceptions that might arise when reusing algorithms.
Source: Eric Grimson and John Guttag, https://www.youtube.com/watch?v=TalbGDwsGVA&feature=emb_logo
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.