3.7 KiB
| title | TARGET DECK | FILE TAGS | tags | |
|---|---|---|---|---|
| Algorithms | Obsidian::STEM | algorithm |
|
Overview
An incremental approach to algorithm design involves acting on a single element at a time. In contrast, the divide-and-conquer approach breaks problems into subproblems that are easier to solve.
%%ANKI Basic What does an incremental approach to algorithm design refer to? Back: An algorithm that acts on a single element at a time. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic What does a divide-and-conquer approach to algorithm design refer to? Back: An algorithm that breaks a problem into similar but simpler subproblems. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic What does it mean for a divide-and-conquer algorithm to "bottom out"? Back: An input that cannot (or should not) be divided any further is encountered. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic In the context of algorithms, what does a "sentinel" refer to? Back: A special value used to simplify code. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Cloze Insertion sort is to an {incremental} design approach whereas merge sort is to a {divide-and-conquer} design approach. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic What ideas does the term "divide-and-conquer" invoke? Back: Breaking a problem into subproblems that are easier to solve. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic According to Cormen et al., what three steps do divide-and-conquer algorithms take? Back: Divide, conquer, and combine. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic What is the "divide" step of a divide-and-conquer algorithm? Back: Breaking the problem into smaller instances of the same problem. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic What is the "conquer" step of a divide-and-conquer algorithm? Back: Solving subproblems recursively or, if small enough, in a straightforward manner. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic What is the "combine" step of a divide-and-conquer algorithm? Back: Manipulating solutions to smaller problems into a solution for the original problem. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
%%ANKI Basic What is a running time recurrence? Back: A formula that describes overall running time in terms of running time on smaller inputs. Reference: Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).
END%%
Bibliography
- Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).