Discrete Mathematics is a branch of mathematics that deals with discrete structures, which are structures that have distinct, separate, and countable elements. It is used to study algorithms, logic, and mathematical reasoning. The subject covers a range of topics, including set theory, graph theory...
What is the Brute Force Approach?
• A straightforward approach, usually based
directly on the problem’s statement and
definitions of the concepts involved
• Examples:
1. Computing an (a > 0, n a nonnegative integer)
2. Computing n!
3. Multiplying two matrices
4. Searching for a key of a given value in a list
, Brute-Force Sorting Algorithm
• Selection Sort
– Scan the array to find its smallest element and swap it with
the first element.
– Starting with the second element, scan the elements after it
to find the smallest among them and swap it with the
second elements.
– Generally, on pass i (0 ≤ i ≤ n-2), find the smallest element
after A[i] and swap it with A[i]:
A[0] ≤ . . . ≤ A[i-1] | A[i], . . . , A[min], . . ., A[n-1]
in their final positions
• Example: 7 3 2 5
Selection Sort
// selectionSort() - The selection sort where we
// seek the ith smallest value and
// swap it into its proper place
void selectionSort(int x[], int n) {
int i, j, min;
for (i = 0; i < n-1; i++) {
min = i;
for (j = i; j < n; j++) {
if (x[j] < x[min])
min = j;
swap(x[i], x[min]);
}
}
}
, Analysis of Selection Sort
• Time efficiency:
• Space efficiency:
• Stability:
Decrease and Conquer
1. Reduce problem instance to smaller instance of the
same problem
2. Solve smaller instance
3. Extend solution of smaller instance to obtain solution
to original instance
• Can be implemented either top-down or bottom-up
• Also referred to as inductive or incremental approach
, 3 Types of Decrease and Conquer
• Decrease by a constant (usually by 1):
– insertion sort
• Decrease by a constant factor (usually by half)
– binary search
– exponentiation by squaring
• Variable-size decrease
– Euclid’s algorithm
– Nim-like games
Insertion Sort
• To sort array A[0..n-1], sort A[0..n-2] recursively and
then insert A[n-1] in its proper place among the
sorted A[0..n-2]
• Usually implemented bottom up (nonrecursively)
• Example: Sort 6, 4, 1, 8, 5
6|4 1 8 5
4 6|1 8 5
1 4 6|8 5
1 4 6 8|5
1 4 5 6 8
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller kuldipkorat. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
