Description

Why brute force?
Find the cases …
Enumerate them …
Then just do it!
We call brute force algorithms the class of algorithms that we do not search for tricks and clever shortcuts, but instead we just try to enumerate the cases to analyze, and we just go one by one, without much wit, just sheer computations, and this relates to brute force solutions.
Brute force, in this sense, is not a lack of sophistication, just a solution relying on sheer processing power.
● Enumeration versus Ingenuity
● Basics Concepts
○ Combinatorics and
○ Summations (again)
CSC 6013 – Week 3

The term
Brute Force Search is frequently employed.
Enumeration versus Ingenuity
Brute Force is not a bad thing…
● Brute Force is a straightforward approach to solve a problem, usually directly based on the problem statement and definitions of the concepts involved.
● Brute Force algorithms are based on solving the problem directly by doing the work to be done just doing the tasks directly;
O(n)
● The Counting positive elements in an array algorithm seem last week is a Brute Force one, as we pass by all elements of the array and we check if they are positive, counting plus one.
Wikipedia: Brute-force search.
Enumeration versus Ingenuity
Brute Force is not clever…
but it is not necessarily a bad choice.
O(n)
● There is no other way to count the number of positive number in an array, so the brute force solution is the best one can do.
Doing a assignment, sometimes you need to think, sometimes you just have to do it!
● In Brute Force we just enumerates what needs to be done:
○ For counting positive elements, we just go over the n elements of the array.
● However, some problems may benefit from a clever approach.
Text: Brute Force Approach and its pros and cons.
Enumeration versus Ingenuity
Let’s see a different problem…
○ The brute force approach would be verify to all possible pairs of people if they have the same dob:
■ The algorithm return True if one pair has the same dob, or False otherwise
○ Such algorithm will have to go through n choose 2 pairs, which is pairs.
○ … it is not that too bad, but there is a clever way…
Text: Birthday Paradox.

Why brute force?
Find the cases …
Enumerate them …
Then just do it!
We call brute force algorithms the class of algorithms that we do not search for tricks and clever shortcuts, but instead we just try to enumerate the cases to analyze, and we just go one by one, without much wit, just sheer computations, and this relates to brute force solutions.
Brute force, in this sense, is not a lack of sophistication, just a solution relying on sheer processing power.
● Enumeration versus Ingenuity
● Basics
○ Combinatorics and
○ Summations (again)
CSC 6013 – Week 3

Basic concepts – Combinatorics
Arrangements states how many ways to sort a certain number of elements of a set.
For example, you bought four Boxes, A, B, and C, and now you need pick two of them, one for the kitchen, and one for the garage, how many choices do you have?
○ There are six possible choices!
■ A for the kitchen and B for the garage ■ A for the kitchen and C for the garage ■ B for the kitchen and A for the garage ■ B for the kitchen and C for the garage ■ C for the kitchen and A for the garage
■ C for the kitchen and B for the garage
Wikipedia: Partial permutation.

Example 2 – Bubble Sort
● Giving an array A = [ a1, a2, … an ]
● Deliver a permutation of A where ai <= aj if i < j
One brute force method is:
● Walk through the array comparing adjacent elements, exchanging them if they are out of order;
● After the first pass the largest element will be in the last position, so, the next time it is possible to stop before it;
● Thus, Bubble sort places one element in the right position position at each pass;
● In such way, the sorted elements grow in a bubble from the end to the front.
Starting [6, 5, 3, 1, 8, 7, 2, 4] and ending [1, 2, 3, 4, 5, 6, 7, 8].

Third Coding Project – P#3
1. Adapt the Selection Sort algorithm seem in class to sort the elements being the largest ones selected to go to the last positions first, instead of the version presented in class, where the smallest ones where selected to go to the first positions. Trace your algorithm execution printing:
a. at each iteration of the outer loop count the number of times two array elements are compared and the number of times two array elements were swapped, plus the current status of the array.
b. test your algorithm for the arrays:
i. A1 = [63, 44, 17, 77, 20, 6, 99, 84, 52, 39]
ii. A2 = [84, 52, 39, 6, 20, 17, 77, 99, 63, 44] iii. A3 = [99, 84, 77, 63, 52, 44, 39, 20, 17, 6]
To both programs you have to submit the code (.py file) of your adapted algorithm and a .pdf with the test cases outputs.
Two algorithms to adapt, this is the first.
Third Coding Project – P#3
2. Adapt the Bubble Sort algorithm seem to stop the outer loop if no swap was made during the last iteration (thus, the array is already sorted). Trace your algorithm execution printing:
a. at each iteration of the outer loop count the number of times two array elements are compared and the number of times two array elements were swapped, plus the current status of the array.
b. test your algorithm for the arrays:
i. A4 = [44, 63, 77, 17, 20, 99, 84, 6, 39, 52]
ii. A5 = [52, 84, 6, 39, 20, 77, 17, 99, 44, 63]
iii. A6 = [6, 17, 20, 39, 44, 52, 63, 77, 84, 99]
Your task:
Third Quiz – Q#3
● The third quiz in this course covers the topics of Week 3;
● The quiz will be available this Friday, and it is composed by 10 questions;
● The quiz should be taken on Canvas (Module 3), 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: