Description

Some of the better known
Divide-and- algorithms belong to the
…-and-conquer family.
Conquer Some of the more effective
algorithms are divide-and-conquer. Algorithms ● Meet the family
○ Decrease-and-Conquer
○ Divide-and-Conquer
○ Transform-and-Conquer
Solve the problem by solving ● Divide-and-Conquer
each of its parts.
○ Basic Principles
○ Recursion and Iteration
CSC 6013 – Week 7
Meet the …-and-conquer family
While in military, politics, management, etc., the usage of divide-and-conquer became extremely popular, and effective, in algorithms we have a subdivision of the algorithm techniques:
● Divide-and-conquer
○ When the original problem is broken into complementary parts;
● Decrease-and-conquer
○ When at each time the problem becomes smaller, but not into complementary problems;
● Transform-and-conquer
○ When the problem not always becomes smaller.
This division is acknowledged by great authors
(as our textbook ones: Cormen, Leiserson, Rivest, and Stein), but it is not unanimous.
The …-and-conquer family
Probably, one of the most known algorithmic techniques is the divide-and-conquer. It has been talked about consistently (documented with this name) at least since the times of Julius Caesar, i.e., 2000 years ago!
However, there are other similar approaches to solve problems, and those are known as the …-and conquer family in the algorithm analysis context.
Divide-and-conquer is the big brother of the …-and-conquer family. Most of the more effective algorithms are divide-and-conquer ones.
Wikipedia: Divide-and-Conquer.
Some of the better known
Divide-and- algorithms belong to the
…-and-conquer family.
Conquer Some of the more effective
algorithms are divide-and-conquer. Algorithms ● Meet the family
○ Decrease-and-Conquer
○ Divide-and-Conquer
○ Transform-and-Conquer
Solve the problem by solving ● Divide-and-Conquer
each of its parts.
○ Basic Principles
○ Recursion and Iteration
CSC 6013 – Week 7
Divide-and-Conquer
Tackling a problem by dividing it into subproblems is so intuitive that sometimes we wonder if this technique can be said to be invented. Splitting our tasks into complementary subtasks has been done perhaps even before we learned how to speak.
If you have to carry a large lego statue, it does make sense to break it into piece to be able to carry it.
If you have a pile of boxes to move upstairs, it makes sense to not carry them all together.
Julius Caesar was very smart, but not the creator of Divide-and-Conquer.
Divide-and-Conquer
While decrease-and-conquer can be implemented recursively or iteratively, the very large majority of divide-and-conquer algorithms are implemented recursively because it is very natural keep on breaking a problem into parts until it becomes trivial.
4 3 6 2 1 8 5 9
Also it is much natural to break into halves, as we will see, it
4 3 6 2 1 8 5 9 makes the algorithms simpler and more efficient.
4 3 6 2 1 8 5 9
With some effort we can always manage, often with large effort and no 4 3 6 2 1 8 5 9 gain, to turn a divide-and-conquer 4 6 8 9
implementation into a non-recursive 6 9
(iterative) version. 9
Text: Introduction to Divide and Conquer Algorithm.

You have to submit a .pdf file with your answers. Feel free to type it or hand write it, but you have to submit a single .pdf with your answers.
In-class Exercise – E#7
Download the pdf (link here also) and perform the following:
● (1) Trace the recursive array sum algorithm for the following arrays. Show to each recursive call the input array, the returned value, and the number of sums executed. At the end of the trace, present the total number of sums executed (the total of sums of all recursive calls.
○ A = [38, 21, 39, 60, -1, 10, 81, 23]
○ B = [2, 97, 5, 88, 9, 72, 12, 64, 17, 56, 21]
○ C = [100, 33, 22, 213, 65, 29, 153, 199, 47, 181, 85]
● (2) Trace the Mergesort algorithm for the following arrays.
Show to each recursive call the two input and output arrays.
○ A = [38, 21, 39, 60, -1, 10, 81, 23]
○ B = [2, 97, 5, 88, 9, 72, 12, 64, 17, 56, 21]
○ C = [100, 33, 22, 213, 65, 29, 153, 199, 47, 181, 85]
Seventh Coding Project – P#7
Develop one Python program to perform the Quicksort, but instead of sorting the elements in ascending order (from the smallest to the largest), the elements are sorted in the decrescent order (from the larger to the smallest). Your program also have to compute and print at the end the number of swaps performed and the number of recursive calls. Test your program over the following arrays:
○ A = [38, 21, 39, 60, -1, 10, 81, 23]
○ B = [2, 97, 5, 88, 9, 72, 12, 64, 17, 56, 21]
○ C = [100, 33, 22, 213, 65, 29, 153, 199, 47, 181, 85]
You have to submit the code (.py file) of your algorithm, plus the .pdf of the trace for the three required tests.
Seventh Quiz – Q#7
● The seventh quiz in this course covers the topics of Week 7;
● The quiz will be available this Friday, and it is composed by 10 questions;
● The quiz should be taken on Canvas (Module 7), and it is not a timed quiz:
○ You can take as long as you want to answer it (a quiz taken in less than one hour is usually a too short time);
● The quiz is open book, open notes, and you can even use any language Interpreter to answer it;
● Yet, the quiz is evaluated and you are allowed to submit it only once.
Your task: