Description

Some of the better known
Decrease-an algorithms belong to the
…-and-conquer family.
d-Conquer ● Basic Definitions
○ Decrease-and-Conquer
Algorithms ○ Divide-and-Conquer
○ Transform-and-Conquer

Each time your problem is a little smaller.

● Kinds of Decrease-and-Conquer
○ Decrease by a constant amount
○ Decrease by a constant factor
○ Decrease by a variable amount and factor
CSC 6013 – Week 6
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.
The more typical kind of algorithm of the family is the Decrease-and-Conquer kind, but let’s talk about the family first, as many authors consider all problems in the family Divide-and-Conquer, and we do not.
Wikipedia: Divide-and-Conquer.
The …-and-conquer family
Julius Caesar became famous and rich because the conquest of Gaul from 58 to 50 bce.
The strategy, as written by Julius Caesar himself, was to divide-and-conquer (in Latin: Divide et Impera), i.e., not attacking Gaul entirely, but attacking and conquering a small tribe here and there until all tribes are vanquished, so he could claim the conquest of Gaul.
In such way, the …-and-conquer family was baptized by Julius Caesar reflecting his own algorithm to conquer a larger enemy with a smaller force.
Wikipedia: Commentarii de Bello Gallico.
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.
Some of the better known
Decrease-an algorithms belong to the
…-and-conquer family.
d-Conquer ● Basic Definitions
○ Decrease-and-Conquer
Algorithms ○ Divide-and-Conquer
○ Transform-and-Conquer

Each time your problem is a little smaller.

● Kinds of Decrease-and-Conquer
○ Decrease by a constant amount
○ Decrease by a constant factor
○ Decrease by a variable amount and factor
CSC 6013 – Week 6
Decrease-and-Conquer
Just like sculpting a block of stone or sharpening a pencil, the decrease-and-conquer algorithms are all about getting closer to the result by taking off bits of the problem until you get a problem that is already solved.
The recursive factorial seen previously was a decrease-and-conquer example:
● If you want to know the factorial of n, and n is large, you can find out how much is the factorial of n-1;
● And you keep on reducing this problem to n-2, n-3, … until you get a problem that is not large anymore, for example the factorial of 1, which has a trivial solution.
The Towers of Hanoi example also was resolved decreasing the problem T(n) = 1 + 2T(n-1) until T(0) = 0.

Decrease-and-Conquer
All Decrease-and-Conquer algorithms reduce the size of the problem repeatedly until you get a trivial problem to solve.
The kinds of Decrease-and-Conquer algorithms are defined according to how the problem size decreases:
● Algorithms that decreases at a ● The Towers of Hanoi always constant amount; decrease 1 size at each step:
● Algorithms that decreases at a ■ T(n) = 2 T(n-1) + 1 constant factor; ● The Binary Search always decrease
● Algorithms that decreases at a to a half at each step:
variable amount and factor. ■ T(n) = T(n/2) + 2
● The Euclid’s algorithm for the GCD
We will consider recursive implementations because it is more intuitive.
Divide-and- ● Decrease by constant amount: The examples that will be seen are:
○ Insertion sort
Conquer ○ Topological sort
● Decrease by constant factor: Algorithms ○ Russian peasants’ ○ Fake coin detection
multiplication
Examples ● Decrease by variable amount
and factor:
○ Euclidean GCD
○ Lomuto partition
○ K-th order statistic
CSC 6013 – Week 6

Example 1 – Insertion Sort
[8][J][9][3][5][10] stays left of [10]
[8][J][9][3][5][10] stays left of [5]
[8][J][9][3][5][10]
to the right of [5]
[8][J][3][5][9][10]
to the right of [10]
[8][3][5][9][10][J]
to the right of [5]
[3][5][8][9][10][J]
● Sorting algorithm that decreases at a constant amount and is not recursive.
● Giving an array A = [ a1 , a2 , … an ]
● Deliver a permutation of A where ai <= aj if i < j ● A decrease-and-conquer solution is:
○ Assume that the last element alone is sorted, then starting from the before last element:
■ Find its place in the last (already sorted) elements and insert it there causing a scootch over behavior;
■ Repeat the process to the element before that and keep on going until places the first element.
At each iteration there are n-i unsorted elements. It decreases by a constant amount (1).
Video: Insertion sort in 2 minutes.

Divide-and- ● Decrease by constant amount: The examples that will be seen are:
○ Insertion sort
Conquer ○ Topological sort
● Decrease by constant factor: Algorithms ○ Russian peasants’ ○ Fake coin detection
multiplication
Examples ● Decrease by variable amount
and factor:
○ Euclidean GCD
○ Lomuto partition
○ K-th order statistic
CSC 6013 – Week 6
Example 2 – Topological Sort
● Given a Directed Acyclic Graph – find an array A of vertices such as if a vertex v appears before vertex w in the array, there is no path from w to v:
○ Conversely, put the vertices in an order that no successor precedes its ancestor. At each call there are 1
● Given a graph defined by a V set of n Vertices and E less vertex to sort.It decreases by a a set of m Edges, each one being a triplet (v, w, 1) constant amount (1).
representing an edge going from v towards w.
[ ]
[E]
[EB]
[EBA]
[EBAC]
[EBACF] [EBACFD]
[EBACFDI]
[EBACFDIK]
[EBACFDIKH]
[EBACFDIKHJ]
[EBACFDIKHJG]
● Main idea:
○ find a vertex with no incoming edges, remove it and insert it into the array A;
○ Repeat the process until all vertices are removed and inserted.
Wikipedia: Topological sorting.
Example 2 – Topological Sort
● Main idea:
[ ]
[E]
[EB]
[EBA]
[EBAC]
[EBACF]
[EBACFD]
[EBACFDI]
[EBACFDIK]
[EBACFDIKH]
[EBACFDIKHJ]
[EBACFDIKHJG]
○ Find a vertex with no incoming edges, remove it and insert it into the array A;
○ Repeat the process until all vertices are removed/inserted.
● Implementation:
○ For all vertices, check if there is an incoming edge from a vertex not yet in A, and if not so, include the vertex in A and consider the recursive call done;
■ If at the end no vertex was included in A, stop it (no DAG); ■ If at the end all vertices are in A, stop it!
■ If at the end not all vertices are in A, At each call there are 1 do another recursive call. less vertex to sort.
It decreases by a constant amount (1).
Video: Topological Sort Visualized and Explained.

Divide-and- ● Decrease by constant amount: The examples that will be seen are:
○ Insertion sort
Conquer ○ Topological sort
● Decrease by constant factor: Algorithms ○ Russian peasants’ ○ Fake coin detection
multiplication
Examples ● Decrease by variable amount
and factor:
○ Euclidean GCD
○ Lomuto partition
○ K-th order statistic
CSC 6013 – Week 6
Example 3 – Fake coin detection

● Given a pile of n coins, where one of them is a fake one that is lighter than the real ones.
● Having only a scale, how fast could you detect the fake one?
● Main idea:
■ If the weight is equal, the faze is the one left out;
■ If one pile is lighter the coin is in there
● Then repeat the process until you have only two coins to weight.
At each call there are half of the coins to analyze.
It decreases by a constant factor (1).

A simple decision exercise.
Example 3 – Fake coin detection
○ If the weight is equal, the faze is the one left out; ○ If one pile is lighter the fake coin is in there.
■ Then repeat the process until you have only two coins to weight.
● This problem recursive relation and stop conditions are:
○ T(n) = 1 + T(n/2) (worst case)
○ T(3) = T(2) = 1
● What is the time complexity of this problem considering the weighting the fundamental unit of work?
Solution by back-substitution or master method.

Divide-and- ● Decrease by constant amount: The examples that will be seen are:
○ Insertion sort
Conquer ○ Topological sort
● Decrease by constant factor: Algorithms ○ Russian peasants’ ○ Fake coin detection
multiplication
Examples ● Decrease by variable amount
and factor:
○ Euclidean GCD
○ Lomuto partition
○ K-th order statistic
CSC 6013 – Week 6

Example 4 – Russian Peasants Multiplication
● Assume that you want to multiply two numbers n and m, and you do not know multiplication facts very well. The only thing you master are sums and multiplications and divisions by 2.
● Assuming p(n,m) the product of n by m, the Russian Peasants method is based on these recursive relations:
At each call there are half of the larger operand to analyze.
It decreases by a constant factor (1). Русские крестьяне умножение
Russkiye krest’yane umnozheniye
Video: Russian Peasant Multiplication.

Example 4 – Russian Peasants Multiplication
Note that the brute force multiplication adding n times the value of m is linear:
O(n)
What is the time complexity of this problem considering the divisions and sums the fundamental units of work?
Possible recurrent relations:
● By back substitution:
Upper bounding and stopping ○ The number of steps is log2 of n
condition: and at each step there are 3 tasks
(division, double, sum):
■ T(n) = log2 n . 3 + T(1) ● By the master method:
■ T(n) = T(n/2) + 3
■ a = 1, b = 2, f(n) = n0
O(log n) – Logarithmic Algorithm
Divide-and- ● Decrease by constant amount: The examples that will be seen are:
○ Insertion sort
Conquer ○ Topological sort
● Decrease by constant factor: Algorithms ○ Russian peasants’ ○ Fake coin detection
multiplication
Examples ● Decrease by variable amount
and factor:
○ Euclidean GCD
○ Lomuto partition
○ K-th order statistic
CSC 6013 – Week 6
m n m%n
60 35 25
35 25 10
25 10 5
10 5 0
5 0 done!
Example 5 – Euclidean GCD Greatest Common Divisor
● The GCD of two numbers n and m is the largest Integer d such that n % d = 0 and m % d = 0.
● This algorithm is attributed to Euclid of Megara, Greek mathematician, author of the text Elements, who lived around 325 bce (about 2,250 years ago).
● The recursive solution is given by the function GCD below:
At each call there is a decrease to the remainder of the Integer division.
It decreases by a variable amount and factor.
Wikipedia: Euclidean algorithm.
Example 5 – Euclidean GCD Greatest Common Divisor
The Euclidean algorithm is one of the oldest ones we will see in the whole Program, and yet it is just a brilliant one with no better known solution.
Yet, it is not an historic proven fact that the algorithm was developed by Euclid, as it is likely that Euclid documented it from previous sources (as this happened with other
concepts, notably to geometry). The GCD 1599650
between The basic principle of the algorithm is that the GCD of two 1599 and 299 numbers does not change if the larger one is replaced by 650 is 13. 52 its difference with the smaller one. 3913
Video: The Euclidean Algorithm Proof.
Example 5 – Euclidean GCD Greatest Common Divisor
What is the time complexity of this problem considering the remainder of Integer division the fundamental unit of work?
This is tricky one … as the recurrence relations are:
● T(n,m) = 1 + T(m, r) where r is m%n, thus r < n
● T(m,0) = 0
There is not an easy way to estimate how much it drops, but in 1844 the French Mathematicien Gabriel Lamé managed to prove that it is O(h) where h is the number of digits in decimal representation of the smaller value between n and m. Thus, a loose upper bound could be O(log10 n) or O(log10 m), which one is smaller.
O(log n) – Logarithmic Algorithm
Divide-and- ● Decrease by constant amount: The examples that will be seen are:
○ Insertion sort
Conquer ○ Topological sort
● Decrease by constant factor: Algorithms ○ Russian peasants’ ○ Fake coin detection
multiplication
Examples ● Decrease by variable amount
and factor:
○ Euclidean GCD
○ Lomuto partition
○ K-th order statistic
CSC 6013 – Week 6
Example 6 – Lomuto Partition
Considering an unsorted array A with n elements, the Lomuto partition algorithm is supposed to, given a specific element p within the array A, put all elements smaller than p before it, and all elements greater than p after it.
The basic idea is to start with two indexes:
● i to the limit between the sorted elements smaller and

greater than p; and
● j to the limit between the already sorted elements. During execution the array would have three regions:
● From 0 to i-1: the sorted elements smaller than p; ● From i to j-1: the sorted elements greater than p;
● From j to n-2: the elements yet to sort.
At each iteration one more element is placed in its belonging partition.
It decreases by a constant amount (1).

Text: Lomuto Partition Algorithm.

Example 6 – Lomuto Partition
The basic idea is to start with two indexes:
● i to the limit between the sorted elements smaller and greater than p; and
● j to the limit between the already sorted elements. During execution the array would have three regions:
Lomuto Partition is not the only
algorithm to
partition elements of an array, it is just the more popular one.
19 13 6 55 42 31 60 36 48 24
0 1 2 3 4 5 6 7 8 9
● From 0 to i-1: the sorted elements smaller than p; ● From i to j-1: the sorted elements greater than p; ● From j to n-2: the elements yet to sort.
i j n-1
Text: Nico Lomuto.
Example 6 – Lomuto Partition
During execution the array would have three regions:
● From 0 to i-1: the sorted elements smaller than p; ● From i to j-1: the sorted elements greater than p; ● From j to n-2: the elements yet to sort.
A function implementing Lomuto Partition could consider the last element the Pivot, and start deciding where each of the other elements (from the first to the last) will be before (smaller) or after (bigger) the Pivot.
The variable i serves as a limit between the smaller and bigger elements. The variable j goes to the first to the before last element.
Video: Learn Lomuto Partition.

Divide-and- ● Decrease by constant amount: The examples that will be seen are:
○ Insertion sort
Conquer ○ Topological sort
● Decrease by constant factor: Algorithms ○ Russian peasants’ ○ Fake coin detection
multiplication
Examples ● Decrease by variable amount
and factor:
○ Euclidean GCD
○ Lomuto partition
○ K-th order statistic
CSC 6013 – Week 6
Example 7 – K-th order statistic
Given an unsorted array, how difficult is to find the smallest element?
● We seen that before, it is an O(n) problem.
What about about finding the k-th smallest element in an array?
● One brute force way is to sort the array and pick the k-th element, but it costs at least O(n log n);
Given the large number of applications for this kind of search, an algorithm called QuickSelect finds the k-th smallest element of an array A of size n with possibly a smaller time complexity than the sort algorithms.
Wikipedia: Quickselect.

Example 7 – K-th order statistic
QuickSelect finds the k-th smallest element of an array A of size n with possibly a smaller time complexity than the sort algorithms.
The basic idea is to use recursively a partition algorithm (Lomuto for instance), until you pinpoint the k-th smallest element in the array.
This approach does not guarantee a better efficiency than sorting, but in general it is much faster.
Actually, the average complexity of QuickSelect is O(n) which is clearly better than the O(n log n) of the more efficient sorting algorithms, but the worst case can be as bad as O(n2).
At each call there is a decrease to the number of elements in the partition to search. It decreases by a variable amount and factor.

This algorithm decreases the size of the problem to one partition, which can be advantageous or not.
Example 7 – K-th order statistic
Let’s say you have a array A of size n and you are looking for the third smaller element in this array.
You can call a Lomuto partition to it and it will give you (according to the pivot chosen) the i-th element of the array. For the example shown before it gives you the fourth smallest element.
31 55 19 13 42 6 60 36 48 24
0 1 2 3 4 5 6 7 8 9
If you are looking for the third one, you can call Lomuto again over the smaller than
19 13 6 24 42 31 60 36 48 55 the pivot partition
0 1 2 3 4 5 6 7 8 9 searching for the third
element.
Searching the smaller than pivot partition is directed.
Example 7 – K-th order statistic
Let’s say you have a array A of size n and you are looking for the sixth smaller element in this array.
You can call a Lomuto partition to it and it will give you (according to the pivot chosen) the i-th element of the array. For the example

31 55 19 13 42 6 60 36 48 24
0 1 2 3 4 5 6 7 8 9
shown before it gives you the fourth smallest element.
19 13 6 24 42 31 60 36 48 55
0 1 2 3 4 5 6 7 8 9
If you are looking for the sixth one, you can call Lomuto again over the greater than the pivot partition searching for the second element (6-4).

Searching the greater than pivot partition requires to adjust considering the position of the pivot.
Example 7 – K-th order statistic
Watch the video linked below that demonstrate step-by-step how to implement it.
Watch attently this video, including the last part where a Python implementation is presented in detail.
However, as in real life, things are not exactly as we would like to be. In this video, intently, I choose to present you an analogous problem: how to find the k-th largest element. So, you will need to adapt what you are seeing to what I described here. In fact, you will need to perform this adaptation (check the coding assignment of this week).
Video: K-th Largest Element in an Array.

In-class Exercise – E#6
Download the pdf (link here also) and perform the following:
● (1) Trace the Russian Peasants Multiplication algorithm for the following products as shown in the live session.
○ 64 * 13 – 60 * 13 – 59 * 13
● (2) Trace the Lomuto partition with the array:
○ A = [100, 33, 22, 213, 65, 29, 153, 199, 47, 181, 85]
In your trace, write down to each change in either i or j, stating: the values of i and j, swaps made, and elements divided into lesser than the pivot, greater than the pivot, and yet to compare.
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.
Fifth Coding Project – P#6
Develop one Python program to perform the Quick Select algorithm and for an array of n elements it should find the k-th smallest element of the array). Inspire yourself by the video example K-th Largest Element in an Array, that needs to be adapted by yourself.
● You must code a function QuickSelect that receives an array and the element the user wants to find (k-th smallest);
● Then the main function of your program should generate a random array of 1000 elements to be searched, ask the user the value of k, call QuickSelect, and display the searched element found.
You have to submit the code (.py file) of your algorithm.
Sixth Quiz – Q#6
● The sixth quiz in this course covers the topics of Week 6;
● The quiz will be available this Friday, and it is composed by 10 questions;
● The quiz should be taken on Canvas (Module 6), 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: