Computer Science - Fundamentals of algorithms

Algorithm

An algorithm is a sequence of steps that can be followed to complete a task.

Decomposition

Decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.

Abstraction

Abstraction is the process of removing unnecessary detail from a problem.

Purpose of Simple Algorithms

Perform basic computations (e.g., sum of numbers).

Make decisions (e.g., even or odd check).

Organize data (e.g., sorting).

Search for information (e.g., finding largest number).

Automate repetitive tasks (e.g., counting vowels).

Improve efficiency (e.g., optimized searching).

Linear search algorithm

The Linear Search algorithm works by taking a list of elements and a target value to find. It starts at the first element of the list and compares each element with the target value. If the element matches the target, it returns the index of that element. If the element does not match, the algorithm moves to the next element and continues the process. This is repeated until the target is found or the end of the list is reached. The output is the index of the target value in the list or a message like "not found" if the value doesn't exist in the list.

Binary search algorithm

The binary search algorithm is used to find a specific value in a sorted list by repeatedly dividing the search range in half. It starts by comparing the middle element with the target value. If they match, the index of the middle element is returned. If the target is smaller, the search continues in the left half, and if larger, it continues in the right half. This process is repeated until the target is found or the range becomes empty.

Binary search vs Linear search

Merge sort

Merge sort is a divide-and-conquer algorithm used to sort a list. It begins by dividing the list into two halves repeatedly until each sublist contains a single element. Once the sublists are reduced to individual elements (which are trivially sorted), the algorithm starts merging them back together in sorted order. During the merging process, the smallest elements from each sublist are compared and placed into a new list, and this continues until all sublists are merged into one sorted list.

Bubble sort

Bubble sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated for each pair of adjacent elements until the list is fully sorted. After each complete pass through the list, the largest unsorted element "bubbles up" to its correct position at the end of the list. The algorithm continues to compare and swap elements in the remaining unsorted portion of the list until no more swaps are needed.

Bubble sort vs Merge Sort