The Mastery of Computer Programming: Primary Algorithms - Sykalo Eugene 2023

Pipelining and parallel processing
Algorithms and Architecture

Sorting Algorithms

Sorting algorithms are used to arrange a list of elements in a specific order. The most common orders are ascending and descending. There are many sorting algorithms available, each with its own advantages and disadvantages. Some of the most popular sorting algorithms are:

Bubble Sort

Bubble Sort is a simple and inefficient sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order. It has a time complexity of O(n^2), which makes it unsuitable for sorting large arrays.

Merge Sort

Merge Sort is a divide and conquer algorithm that splits the input array into two halves, sorts each half recursively, and then merges the sorted halves. It has a time complexity of O(n log n), which makes it suitable for sorting large arrays.

Quick Sort

Quick Sort is another divide and conquer algorithm that selects an element as a pivot and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. It then recursively sorts the sub-arrays. It has a time complexity of O(n log n) on average, but can have a worst-case time complexity of O(n^2) if the pivot selection is not optimal.

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It has a time complexity of O(n log n), which makes it suitable for sorting large arrays. However, it is not as fast as Quick Sort in practice.

Table of all known Sorting Algorithms

Searching Algorithms

Searching algorithms are used to find the location of a specific element in a list of elements. The most common searching algorithms are:

Linear Search

Linear Search is a simple searching algorithm that sequentially checks each element in the list until a match is found. It has a time complexity of O(n), where n is the size of the list.

Binary Search

Binary Search is a more efficient searching algorithm that works by dividing the list in half at each step and checking whether the middle element is equal to the target element. If the middle element is greater than the target element, the algorithm searches the left half of the list; otherwise, it searches the right half. It has a time complexity of O(log n), where n is the size of the list. However, it requires the list to be sorted.

Hashing

Hashing is a technique used to map a large and arbitrary data set to a small and fixed-size data set. A hash function is used to convert the input data into a fixed-size value, which is used as an index to access an array of elements. The time complexity of searching using hashing is O(1) on average, but it can degrade to O(n) in the worst case if there are collisions.

Graph Algorithms

Graph algorithms are used to traverse and manipulate graphs, which are mathematical structures consisting of vertices/nodes and edges/links. The most common graph algorithms are:

Depth-First Search

Depth-First Search (DFS) is a graph traversal algorithm that starts at a specified vertex and explores as far as possible along each branch before backtracking. It can be implemented recursively or iteratively using a stack data structure. DFS is used to search for a specific vertex or to explore the entire graph.

Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that starts at a specified vertex and explores all the vertices at the current level before moving on to the vertices at the next level. It can be implemented using a queue data structure. BFS is used to search for the shortest path between two vertices or to explore the entire graph.

Dijkstra's Algorithm

Dijkstra's Algorithm is a shortest path algorithm that finds the shortest path between a specified vertex and every other vertex in the graph. It works by maintaining a priority queue of vertices and their distances from the starting vertex, and repeatedly selecting the vertex with the smallest distance and updating its neighbors' distances. Dijkstra's Algorithm is commonly used in routing and network optimization.

Dynamic Programming

Dynamic programming is a technique used to solve problems by breaking them down into smaller subproblems. It is particularly useful for problems that exhibit overlapping subproblems and optimal substructure. The key idea behind dynamic programming is to store the solutions to subproblems in a table and reuse them as necessary to solve larger subproblems. This can result in significant performance improvements over naive recursive solutions.

Steps of Dynamic Programming

The steps involved in solving a problem using dynamic programming are as follows:

1. Identify the problem as one that can be solved using dynamic programming. Dynamic programming is particularly useful for problems that exhibit overlapping subproblems and optimal substructure. Overlapping subproblems occur when the solution to a problem can be obtained by combining the solutions to similar subproblems. Optimal substructure occurs when the optimal solution to a problem can be obtained by combining the optimal solutions to its subproblems.
2. Break the problem down into smaller subproblems. This involves identifying the recursive structure of the problem and determining the base case(s) and the recursive case(s).
3. Define a table to store the solutions to subproblems. The table should have as many dimensions as there are independent variables in the problem. The entries in the table should correspond to the values of the variables, and the values in the table should correspond to the solutions to the subproblems.
4. Fill in the table using the recursive structure of the problem. This involves computing the solutions to the subproblems in a bottom-up fashion, starting from the base case(s) and working up to the desired solution.
5. Use the filled-in table to obtain the solution to the original problem. This involves combining the solutions to the subproblems as necessary to obtain the desired solution.

Examples of Dynamic Programming

Dynamic programming can be used to solve a wide variety of problems, including:

• The Knapsack Problem: Given a set of items, each with a weight and a value, determine the items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
• The Longest Common Subsequence Problem: Given two sequences, find the longest subsequence that is common to both sequences.
• The Edit Distance Problem: Given two strings, find the minimum number of operations required to convert one string into the other, where an operation is defined as an insertion, deletion, or substitution of a single character.

Dynamic programming can also be used to optimize recursive algorithms by storing the results of previous function calls in a table and reusing them as necessary. This technique is known as memoization.

String Algorithms

String algorithms are used to manipulate and analyze text strings. The most common string algorithms are:

Pattern Matching

Pattern matching is the process of finding one or more occurrences of a pattern within a text string. The most common pattern matching algorithms are:

• Naive String Matching: This algorithm compares each character in the pattern to each character in the text string sequentially. It has a time complexity of O(mn), where m and n are the lengths of the pattern and text string, respectively.
• Knuth-Morris-Pratt Algorithm: This algorithm uses a prefix function to avoid unnecessary character comparisons. It has a time complexity of O(m+n), where m and n are the lengths of the pattern and text string, respectively.
• Boyer-Moore Algorithm: This algorithm uses a heuristic to skip ahead in the text string whenever a mismatch occurs. It has a time complexity of O(mn), but is often faster in practice due to the heuristic.

String Compression

String compression is the process of encoding a text string in a smaller number of bits than the original representation. The most common string compression algorithms are:

• Run-Length Encoding: This algorithm replaces repeated substrings with a single symbol and a count of the number of repetitions. It is particularly effective for compressing runs of repeated characters.
• Huffman Encoding: This algorithm uses a variable-length code to represent each character in the text string. The code is designed to be more efficient for characters that occur more frequently in the text string.

Regular Expressions

Regular expressions are a powerful tool for pattern matching and text manipulation. They provide a concise and flexible syntax for specifying patterns of text. Common regular expression operations include:

• Matching: This operation tests whether a text string matches a given regular expression.
• Searching: This operation finds the first occurrence of a regular expression within a text string.
• Substitution: This operation replaces all occurrences of a regular expression within a text string with a specified replacement string.

Numerical Algorithms

Numerical algorithms are used to solve mathematical problems that involve numerical data, such as equations, optimization problems, and simulation. The most common numerical algorithms are:

Newton's Method

Newton's Method is a root-finding algorithm that uses an iterative process to find the roots of a function. It works by starting with an initial estimate of the root and then refining the estimate by using the function and its derivative. Newton's Method is commonly used to find roots of nonlinear equations.

Monte Carlo Method

Monte Carlo Method is a statistical sampling technique that uses random numbers to simulate complex systems. It is used to estimate the value of an unknown quantity by generating random samples and computing the average value. Monte Carlo Method is commonly used in financial modeling, physics, and engineering.

Linear Programming

Linear Programming is an optimization technique used to find the best solution to a problem that involves linear constraints and a linear objective function. It works by finding the optimal values of the decision variables that satisfy the constraints and maximize or minimize the objective function. Linear Programming is commonly used in operations research, economics, and engineering.