Algorithm Design Techniques

Algorithm Design Techniques

• Designing an algorithm is straight forward with knowledge of design techniques.
• An algorithm design technique is a strategy or paradigm used to solve problems algorithmically, and can be applied to a variety of problems in computing.
• Algorithm design depends mainly on the chosen model.
• Design techniques provide guidance for designing new algorithms and represent a collection of tools for application.
• The most used techniques are:
• Brute force
• Decrease and conquer
• Divide and conquer
• Greedy technique
• Dynamic programming
• Backtracking

Brute Force Approach

• Brute force is a strategy that systematically tries every possible option until a solution is found or it's confirmed that none exists, enumerating all possibilities without using problem-specific insight or heuristics.
• Key characteristics of the brute force approach are:
• Exhaustive Search: Checks every possible candidate or combination.
• Simplicity: Brute force algorithms are often easy to implement because they follow a direct, straightforward procedure.
• High Time Complexity: It can be very slow, such as searching all permutations of nnn items requires O(n!) time.
• Guaranteed Completeness: It will always find a solution if one exists, since it explores all possibilities.
• String Matching: Checking if a pattern P of length m appears in a text T of length n, which has a O(m×n) worst-case time complexity.
• Traveling Salesman Problem (TSP): Enumerates every possible route visiting all cities to find the route with the smallest total distance, requiring checking O(n!) permutations for nnn cities.
• It is viable for small problem sizes or when you want to ensure correctness and simplicity without a complex optimization.

Sorting algorithms

• Sorting algorithms are used to sort data such as numbers or strings.
• Sorting algorithms can be implemented in places like e-commerce websites and for movie rankings.
• Common sorting algorithms include bubble sort, selection sort, and merge sort.
• Sorting a small amount of data is not a complex task.
• Sorting becomes expensive when inputs become very large, causing considerable expenses for companies should a minor mistake occur.

Sorting Algorithms to be Studied

• There are various sorting algorithms available for study.
• There will be an analysis of bad and efficient sorting algorithms.
• There will be an analysis of their complexities.
• It's important to understand which algorithm to use for what problem.
• Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort will be covered.

Bubble Sort

• This is classified as brute force.
• Bubble sort is described as a very basic algorithm for sorting.
• This method scans the array from left to right, completing one pass per scan.
• The current element is compared with the next element, and if the first is higher, they are swapped.
• After one scan, the largest element is bubbled up to the rightmost position.
• The second pass bubbles the second largest element to the second last position and so on.
• This method has a time complexity of T(n)=O(n^2) using two nested loops.
• There is a better sorting algorithm than this.

Selection Sort

• An option for sorting
• Selection Sort begins by regarding the first element as the item with the smallest value and comparing it with remaining items.
• If another smaller element is found:
• It replaces the existing smallest item.
• Then continues to compare with the remaining elements using this new value.
• At the end of each pass, the smallest item is placed at the first index, and the process restarts from the second element.
• The core steps are:
• Set the first location as the smallest
• Look for the smallest element on the list
• Replace the value at location Min with a different value
• Continue until the list is sorted
• The comparison cost is constant and can be ignored.
• It has the same time complexity as bubble sort at n^2.

Insertion Sort

• Less efficient sorting algorithms will be discussed.
• Insertion sort is not the most efficient sort either.
• The speed is reliant on the data set.
• Insertion sort is useful when the list is almost or fully sorted.
• It is important in computer science.
• It is possible for the best case to get an O(n) time for insertion sort.
• An array of size N in ascending order is sorted via iteration.
• Each array element is compared to its predecessor.
• If it's smaller, it will compare itself to all elements before.
• The greater elements move one position up to make space for the swapped element.
• In the best case, the outer loop won't be executed more than once, giving T(n)=O(n).
• The time complexity is T(n)=O(n^2) for worst cases.
• Insertion Sort performs better than Bubble Sort and Selection Sort for small datasets.
• Bubble Sort and Selection Sort perform better than Insertion Sort for larger datasets.