In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence. The transformation can be represented by aligning two alphabets; the cipher alphabet is the plain alphabet rotated left or right by some number of positions. For instance, here is a Caesar cipher using a left rotation of three places, equivalent to a right shift of 23 (the shift parameter is used as the key): Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: XYZABCDEFGHIJKLMNOPQRSTUVW When encrypting, a person looks up each letter of the message in the "plain" line and writes down the corresponding letter in the "cipher" line. Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

The Hill cipher is a polygraphic substitution cipher based on linear algebra. Each letter is represented by a number modulo 26. Though this is not an essential feature of the cipher, this simple scheme is often used: To encrypt a message, each block of n letters (considered as an n-component vector) is multiplied by an invertible n × n matrix, against modulus 26. The matrix used for encryption is the cipher key, and it should be chosen randomly from the set of invertible n × n matrices (modulo 26). The cipher can, of course, be adapted to an alphabet with any number of letters; all arithmetic just needs to be done modulo the number of letters instead of modulo 26. Consider the message ACT, and the key below (or GYB/NQK/URP in letters): Since A is0, C is 2 and T is 19, the message is the vector: Thus, the enciphered vector is given by: which corresponds to a ciphertext of POH. Now, suppose that our message is instead CAT (notice how we're using the same letters as in ACT here), or: This time, the enciphered vector is given by: which corresponds to a ciphertext of FIN. Every letter has changed. To decrypt the message, each block is multiplied by the inverse of the matrix used for encryption. We turn the ciphertext back into a vector, then simply multiply by the inverse matrix of the key matrix (IFK/VIV/VMI in letters). (See matrix inversion for methods to calculate the inverse matrix.) We find that, modulo 26, the inverse of the matrix used in the previous example is: -1 Taking the previous example ciphertext of POH, we get: which gets us back to ACT, as expected. Two complications exist in picking the encrypting matrix: 1. Not all matrices have an inverse. The matrix will have an inverse if and only if its determinant is not zero. 2. The determinant of the encrypting matrix must not have any common factors with the modular base. Thus, if we work modulo 26 as above, the determinant must be nonzero, and must not be divisible by 2 or 13. If the determinant is 0, or has common factors with the modular base, then the matrix cannot be used in the Hill cipher, and another matrix must be chosen (otherwise it will not be possible to decrypt). Fortunately, matrices which satisfy the conditions to be used in the Hill cipher are fairly common.

Hash functions are used to map large data sets of elements of an arbitrary length (the keys) to smaller data sets of elements of a fixed length (the fingerprints). The basic application of hashing is efficient testing of equality of keys by comparing their fingerprints. A collision happens when two different keys have the same fingerprint. The way in which collisions are handled is crucial in most applications of hashing. Hashing is particularly useful in construction of efficient practical algorithms. A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input. A few hash functions allow a rolling hash to be computed very quickly — the new hash value is rapidly calculated given only the following data: An ideal hash function for strings should obviously depend both on the multiset of the symbols present in the key and on the order of the symbols. The most common family of such hash functions treats the symbols of a string as coefficients of a polynomial with an integer variable p and computes its value modulo an integer constant M: The Rabin–Karp string search algorithm is often explained using a very simple rolling hash function that only uses multiplications and additions - polynomial rolling hash: > H(s₀, s₁, ..., s_k) = s₀ * p^k-1 + s₁ * p^k-2 + ... + s_k * p⁰ where p is a constant, and (s₁, ... , s_k) are the input characters. For example we can convert short strings to key numbers by multiplying digit codes by powers of a constant. The three letter word ace could turn into a number by calculating: > key = 1 * 26² + 3 * 26¹ + 5 * 26⁰ In order to avoid manipulating huge H values, all math is done modulo M. > H(s₀, s₁, ..., s_k) = (s₀ * p^k-1 + s₁ * p^k-2 + ... + s_k * p⁰) mod M A careful choice of the parameters M, p is important to obtain “good” properties of the hash function, i.e., low collision rate. This approach has the desirable attribute of involving all the characters in the input string. The calculated key value can then be hashed into an array index in the usual way: function hash(key, arraySize) { const base = 13; let hash = 0; for (let charIndex = 0; charIndex < key.length; charIndex += 1) { const charCode = key.charCodeAt(charIndex); hash += charCode * (base ** (key.length - charIndex - 1)); } return hash % arraySize; } The hash() method is not as efficient as it might be. Other than the character conversion, there are two multiplications and an addition inside the loop. We can eliminate one multiplication by using *Horner's method: > a₄ * x⁴ + a₃ * x³ + a₂ * x² + a₁ * x¹ + a₀ = (((a₄ * x + a₃) * x + a₂) * x + a₁) * x + a₀ In other words: > H_i = (P * H_i-1 + S_i) mod M The hash() cannot handle long strings because the hashVal exceeds the size of int. Notice that the key always ends up being less than the array size. In Horner's method we can apply the modulo (%) operator at each step in the calculation. This gives the same result as applying the modulo operator once at the end, but avoids the overflow. function hash(key, arraySize) { const base = 13; let hash = 0; for (let charIndex = 0; charIndex < key.length; charIndex += 1) { const charCode = key.charCodeAt(charIndex); hash = (hash * base + charCode) % arraySize; } return hash; } Polynomial hashing has a rolling property: the fingerprints can be updated efficiently when symbols are added or removed at the ends of the string (provided that an array of powers of p modulo M of sufficient length is stored). The popular Rabin–Karp pattern matching algorithm is based on this property

The rail fence cipher (also called a zigzag cipher) is a transposition cipher in which the message is split across a set of rails on a fence for encoding. The fence is populated with the message's characters, starting at the top left and adding a character on each position, traversing them diagonally to the bottom. Upon reaching the last rail, the direction should then turn diagonal and upwards up to the very first rail in a zig-zag motion. Rinse and repeat until the message is fully disposed across the fence. The encoded message is the result of concatenating the text in each rail, from top to bottom. From wikipedia, this is what the message WE ARE DISCOVERED. FLEE AT ONCE looks like on a 3-rail fence: W . . . E . . . C . . . R . . . L . . . T . . . E . E . R . D . S . O . E . E . F . E . A . O . C . . . A . . . I . . . V . . . D . . . E . . . N . . WECRLTEERDSOEEFEAOCAIVDEN The message can then be decoded by re-creating the encoded fence, with the same traversal pattern, except characters should only be added on one rail at a time. To illustrate that, a dash can be added on the rails that are not supposed to be populated yet. This is what the fence would look like after populating the first rail, the dashes represent positions that were visited but not populated. W . . . E . . . C . . . R . . . L . . . T . . . E . - . - . - . - . - . - . - . - . - . - . - . - . . . - . . . - . . . - . . . - . . . - . . . - . . It's time to start populating the next rail once the number of visited fence positions is equal to the number of characters in the message.

A vertex in an undirected connected graph is an articulation point (or cut vertex) if removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components. They are useful for designing reliable networks. For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components.

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. Worst-case performance O(|V||E|) Best-case performance O(|E|) Worst-case space complexity O(|V|)

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges. A graph with 16 vertices and 6 bridges (highlighted in red) An undirected connected graph with no cut edges

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself. There are several different types of cycles, principally a closed walk and a simple cycle. A closed walk consists of a sequence of vertices starting and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph. In a directed graph, each edge must be traversed by the walk consistently with its direction: the edge must be oriented from the earlier of two consecutive vertices to the later of the two vertices in the sequence. The choice of starting vertex is not important: traversing the same cyclic sequence of edges from different starting vertices produces the same closed walk. A simple cycle may be defined either as a closed walk with no repetitions of vertices and edges allowed, other than the repetition of the starting and ending vertex, or as the set of edges in such a walk. The two definitions are equivalent in directed graphs, where simple cycles are also called directed cycles: the cyclic sequence of vertices and edges in a walk is completely determined by the set of edges that it uses. In undirected graphs the set of edges of a cycle can be traversed by a walk in either of two directions, giving two possible directed cycles for every undirected cycle. A circuit can be a closed walk allowing repetitions of vertices but not edges; however, it can also be a simple cycle, so explicit definition is recommended when it is used. A graph with edges colored to illustrate path H-A-B (green), closed path or walk with a repeated vertex B-D-E-F-D-C-B (blue) and a cycle with no repeated edge or vertex H-D-G-H (red) General information: Cycles in undirected graphs: Cycles in directed graphs:

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. The algorithm exists in many variants; Dijkstra's original variant found the shortest path between two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree. Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex. Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and stated that connected graphs with all vertices of even degree have an Eulerian circuit. Every vertex of this graph has an even degree. Therefore, this is an Eulerian graph. Following the edges in alphabetical order gives an Eulerian circuit/cycle. For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian. The Königsberg Bridges multigraph. This multigraph is not Eulerian, therefore, a solution does not exist.

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with O(|V|^3) comparisons in a graph. This is remarkable considering that there may be up to |V|^2 edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal. Consider a graph G with vertices V numbered 1 through N. Further consider a function shortestPath(i, j, k) that returns the shortest possible path from i to j using vertices only from the set {1, 2, ..., k} as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each i to each j using only vertices in {1, 2, ..., N}. This formula is the heart of the Floyd–Warshall algorithm. The algorithm above is executed on the graph on the left below: In the tables below i is row numbers and j is column numbers. k = 0 k = 1 k = 2 k = 3 k = 4

Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem. One possible Hamiltonian cycle through every vertex of a dodecahedron is shown in red – like all platonic solids, the dodecahedron is Hamiltonian. Generate all possible configurations of vertices and print a configuration that satisfies the given constraints. There will be n! (n factorial) configurations. while there are untried configurations { generate the next configuration if ( there are edges between two consecutive vertices of this configuration and there is an edge from the last vertex to the first ). { print this configuration; break; } } Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1. Before adding a vertex, check for whether it is adjacent to the previously added vertex and not already added. If we find such a vertex, we add the vertex as part of the solution. If we do not find a vertex then we return false.

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). A demo for Kruskal's algorithm based on Euclidean distance. A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. A planar graph and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to its length. This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex. Prim's algorithm starting at vertex A. In the third step, edges After that step, AB is no longer a candidate for addition to the tree because it links two nodes that are already in the tree. A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted (un)directed graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. A planar graph and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to its length. This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.

A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. In a directed graph G that may not itself be strongly connected, a pair of vertices u and v are said to be strongly connected to each other if there is a path in each direction between them. Graph with strongly connected components marked

In the field of computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. A topological ordering of a directed acyclic graph: every edge goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering. The graph shown above has many valid topological sorts, including: The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies. The jobs are represented by vertices, and there is an edge from x to y if job x must be completed before job y can be started (for example, when washing clothes, the washing machine must finish before we put the clothes in the dryer). Then, a topological sort gives an order in which to perform the jobs. Other application is dependency resolution. Each vertex is a package and each edge is a dependency of package a on package 'b'. Then topological sorting will provide a sequence of installing dependencies in a way that every next dependency has its dependent packages to be installed in prior.

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?" Solution of a travelling salesman problem: the black line shows the shortest possible loop that connects every red dot. TSP can be modelled as an undirected weighted graph, such that cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's weight. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

The task is to traverse the given linked list in reversed order. For example for the following linked list: The order of traversal should be: 37 → 99 → 12 The time complexity is O(n) because we visit every node only once.

The task is to traverse the given linked list in straight order. For example for the following linked list: The order of traversal should be: 12 → 99 → 37 The time complexity is O(n) because we visit every node only once.

This method shifts the relevant bit to the zeroth position. Then we perform AND operation with one which has bit pattern like 0001. This clears all bits from the original number except the relevant one. If the relevant bit is one, the result is 1, otherwise the result is 0. > See getBit.js for further details. This method shifts 1 over by bitPosition bits, creating a value that looks like 00100. Then we perform OR operation that sets specific bit into 1 but it does not affect on other bits of the number. > See setBit.js for further details. This method shifts 1 over by bitPosition bits, creating a value that looks like 00100. Than it inverts this mask to get the number that looks like 11011. Then AND operation is being applied to both the number and the mask. That operation unsets the bit. > See clearBit.js for further details. This method is a combination of "Clear Bit" and "Set Bit" methods. > See updateBit.js for further details. This method determines if the number provided is even. It is based on the fact that odd numbers have their last right bit to be set to 1. Number: 5 = 0b0101 isEven: false Number: 4 = 0b0100 isEven: true > See isEven.js for further details. This method determines if the number is positive. It is based on the fact that all positive numbers have their leftmost bit to be set to 0. However, if the number provided is zero or negative zero, it should still return false. Number: 1 = 0b0001 isPositive: true Number: -1 = -0b0001 isPositive: false > See isPositive.js for further details. This method shifts original number by one bit to the left. Thus all binary number components (powers of two) are being multiplying by two and thus the number itself is being multiplied by two. Before the shift Number: 0b0101 = 5 Powers of two: 0 + 2^2 + 0 + 2^0 After the shift Number: 0b1010 = 10 Powers of two: 2^3 + 0 + 2^1 + 0 > See multiplyByTwo.js for further details. This method shifts original number by one bit to the right. Thus all binary number components (powers of two) are being divided by two and thus the number itself is being divided by two without remainder. Before the shift Number: 0b0101 = 5 Powers of two: 0 + 2^2 + 0 + 2^0 After the shift Number: 0b0010 = 2 Powers of two: 0 + 0 + 2^1 + 0 > See divideByTwo.js for further details. This method make positive numbers to be negative and backwards. To do so it uses "Twos Complement" approach which does it by inverting all of the bits of the number and adding 1 to it. 1101 -3 1110 -2 1111 -1 0000 0 0001 1 0010 2 0011 3 > See switchSign.js for further details. This method multiplies two signed integer numbers using bitwise operators. This method is based on the following facts: a * b can be written in the below formats: 0 if a is zero or b is zero or both a and b are zeroes 2a * (b/2) if b is even 2a * (b - 1)/2 + a if b is odd and positive 2a * (b + 1)/2 - a if b is odd and negative The advantage of this approach is that in each recursive step one of the operands reduces to half its original value. Hence, the run time complexity is O(log(b)) where b is the operand that reduces to half on each recursive step. > See multiply.js for further details. This method multiplies two integer numbers using bitwise operators. This method is based on that "Every number can be denoted as the sum of powers of 2". The main idea of bitwise multiplication is that every number may be split to the sum of powers of two: I.e. 19 = 2^4 + 2^1 + 2^0 Then multiplying number x by 19 is equivalent of: x * 19 = x * 2^4 + x * 2^1 + x * 2^0 Now we need to remember that x * 2^4 is equivalent of shifting x left by 4 bits (x << 4). > See multiplyUnsigned.js for further details. This method counts the number of set bits in a number using bitwise operators. The main idea is that we shift the number right by one bit at a time and check the result of & operation that is 1 if bit is set and 0 otherwise. Number: 5 = 0b0101 Count of set bits = 2 > See countSetBits.js for further details. This methods outputs the number of bits required to convert one number to another. This makes use of property that when numbers are XOR-ed the result will be number of different bits. 5 = 0b0101 1 = 0b0001 Count of Bits to be Flipped: 1 > See bitsDiff.js for further details. To calculate the number of valuable bits we need to shift 1 one bit left each time and see if shifted number is bigger than the input number. 5 = 0b0101 Count of valuable bits is: 3 When we shift 1 four times it will become bigger than 5. > See bitLength.js for further details. This method checks if a number provided is power of two. It uses the following property. Let's say that powerNumber is a number that has been formed as a power of two (i.e. 2, 4, 8, 16 etc.). Then if we'll do & operation between powerNumber and powerNumber - 1 it will return 0 (in case if number is power of two). Number: 4 = 0b0100 Number: 3 = (4 - 1) = 0b0011 4 & 3 = 0b0100 & 0b0011 = 0b0000 <-- Equal to zero, is power of two. Number: 10 = 0b01010 Number: 9 = (10 - 1) = 0b01001 10 & 9 = 0b01010 & 0b01001 = 0b01000 <-- Not equal to zero, not a power of two. > See isPowerOfTwo.js for further details. This method adds up two integer numbers using bitwise operators. It implements full adder electronics circuit logic to sum two 32-bit integers in two's complement format. It's using the boolean logic to cover all possible cases of adding two input bits: with and without a "carry bit" from adding the previous less-significant stage. Legend: A = 3: 011 B = 6: 110 ┌──────┬────┬────┬─────────┬──────────┬─────────┬───────────┬───────────┐ │ bit │ ai │ bi │ carryIn │ carryOut │ bitSum │ resultBin │ resultDec │ ├──────┼────┼────┼─────────┼──────────┼─────────┼───────────┼───────────┤ │ 0 │ 1 │ 0 │ 0 │ 0 │ 1 │ 1 │ 1 │ │ 1 │ 1 │ 1 │ 0 │ 1 │ 0 │ 01 │ 1 │ │ 2 │ 0 │ 1 │ 1 │ 1 │ 0 │ 001 │ 1 │ │ 3 │ 0 │ 0 │ 1 │ 0 │ 1 │ 1001 │ 9 │ └──────┴────┴────┴─────────┴──────────┴─────────┴───────────┴───────────┘ > See fullAdder.js for further details. > See Full Adder on YouTube.

A complex number is a number that can be expressed in the form a + b * i, where a and b are real numbers, and i is a solution of the equation x^2 = −1. Because no real number satisfies this equation, i is called an imaginary number. For the complex number a + b * i, a is called the real part, and b is called the imaginary part. A Complex Number is a combination of a Real Number and an Imaginary Number: Geometrically, complex numbers extend the concept of the one-dimensional number line to the two-dimensional complex plane by using the horizontal axis for the real part and the vertical axis for the imaginary part. The complex number a + b * i can be identified with the point (a, b) in the complex plane. A complex number whose real part is zero is said to be purely imaginary; the points for these numbers lie on the vertical axis of the complex plane. A complex number whose imaginary part is zero can be viewed as a real number; its point lies on the horizontal axis of the complex plane. A complex number can be visually represented as a pair of numbers (a, b) forming a vector on a diagram called an Argand diagram, representing the complex plane. > Complex does not mean complicated. It means the two types of numbers, real and > imaginary, together form a complex, just like a building complex (buildings > joined together). An alternative way of defining a point P in the complex plane, other than using the x- and y-coordinates, is to use the distance of the point from O, the point whose coordinates are (0, 0) (the origin), together with the angle subtended between the positive real axis and the line segment OP in a counterclockwise direction. This idea leads to the polar form of complex numbers. The absolute value (or modulus or magnitude) of a complex number z = x + yi is: The argument of z (in many applications referred to as the "phase") is the angle of the radius OP with the positive real axis, and is written as arg(z). As with the modulus, the argument can be found from the rectangular form x+yi: Together, r and φ give another way of representing complex numbers, the polar form, as the combination of modulus and argument fully specify the position of a point on the plane. Recovering the original rectangular co-ordinates from the polar form is done by the formula called trigonometric form: Using Euler's formula this can be written as: To add two complex numbers we add each part separately: (a + b * i) + (c + d * i) = (a + c) + (b + d) * i Example (3 + 5i) + (4 − 3i) = (3 + 4) + (5 − 3)i = 7 + 2i On complex plane the adding operation will look like the following: To subtract two complex numbers we subtract each part separately: (a + b * i) - (c + d * i) = (a - c) + (b - d) * i Example (3 + 5i) - (4 − 3i) = (3 - 4) + (5 + 3)i = -1 + 8i To multiply complex numbers each part of the first complex number gets multiplied by each part of the second complex number: Just use "FOIL", which stands for "Firsts, Outers, Inners, Lasts" ( see Binomial Multiplication for more details): In general it looks like this: (a + bi)(c + di) = ac + adi + bci + bdi^2 But there is also a quicker way! Use this rule: (a + bi)(c + di) = (ac − bd) + (ad + bc)i Example (3 + 2i)(1 + 7i) = 3×1 + 3×7i + 2i×1+ 2i×7i = 3 + 21i + 2i + 14i^2 = 3 + 21i + 2i − 14 (because i^2 = −1) = −11 + 23i (3 + 2i)(1 + 7i) = (3×1 − 2×7) + (3×7 + 2×1)i = −11 + 23i We will need to know about conjugates in a minute! A conjugate is where we change the sign in the middle like this: A conjugate is often written with a bar over it: 5 − 3i = 5 + 3i On the complex plane the conjugate number will be mirrored against real axes. The conjugate is used to help complex division. The trick is to multiply both top and bottom by the conjugate of the bottom. Example 2 + 3i 4 − 5i Multiply top and bottom by the conjugate of 4 − 5i: (2 + 3i) * (4 + 5i) 8 + 10i + 12i + 15i^2 = ------------------- = ---------------------- (4 − 5i) * (4 + 5i) 16 + 20i − 20i − 25i^2 Now remember that i^2 = −1, so: 8 + 10i + 12i − 15 −7 + 22i −7 22 = ------------------- = -------- = -- + -- * i 16 + 20i − 20i + 25 41 41 41 There is a faster way though. In the previous example, what happened on the bottom was interesting: (4 − 5i)(4 + 5i) = 16 + 20i − 20i − 25i The middle terms (20i − 20i) cancel out! Also i^2 = −1 so we end up with this: (4 − 5i)(4 + 5i) = 4^2 + 5^2 Which is really quite a simple result. The general rule is: (a + bi)(a − bi) = a^2 + b^2

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By reversing the steps, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252. The fact that the GCD can always be expressed in this way is known as Bézout's identity. Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC being shorter, it is used to "measure" BA, but only once because remainder EA is less than DC. EA now measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right Nicomachus' example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath 1908:300). A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a-by-b rectangle can be covered with square tiles of side-length c only if c is a common divisor of a and b. Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.

In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore occasionally being called the Pythagorean distance. The distance between any two points on the real line is the absolute value of the numerical difference of their coordinates In three dimensions, for points given by their Cartesian coordinates, the distance is Example: the distance between the two points (8,2,6) and (3,5,7): In general, for points given by Cartesian coordinates in n-dimensional Euclidean space, the distance is

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example: 5! = 5 * 4 * 3 * 2 * 1 = 120

The power of a number says how many times to use the number in a multiplication. It is written as a small number to the right and above the base number. How to find a raised to the power b? We multiply a to itself, b times. That is, a^b = a * a * a * ... * a (b occurrences of a). This operation will take O(n) time since we need to do multiplication operation exactly n times. Can we do better than naive algorithm does? Yes we may solve the task of powering in O(log(n)) time. The algorithm uses divide and conquer approach to compute power. Currently the algorithm work for two positive integers X and Y. The idea behind the algorithm is based on the fact that: For even Y: X^Y = X^(Y/2) * X^(Y/2) For odd Y: X^Y = X^(Y//2) * X^(Y//2) * X where Y//2 is result of division of Y by 2 without reminder. For example 2^4 = (2 * 2) * (2 * 2) = (2^2) * (2^2) 2^5 = (2 * 2) * (2 * 2) * 2 = (2^2) * (2^2) * (2) Now, since on each step we need to compute the same X^(Y/2) power twice we may optimise it by saving it to some intermediate variable to avoid its duplicate calculation. Time Complexity Since each iteration we split the power by half then we will call function recursively log(n) times. This the time complexity of the algorithm is reduced to: O(log(n))

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones: A tiling with squares whose side lengths are successive Fibonacci numbers The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling;[4] this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13 and 21.

The Fourier Transform (FT) decomposes a function of time (a signal) into the frequencies that make it up, in a way similar to how a musical chord can be expressed as the frequencies (or pitches) of its constituent notes. The Discrete Fourier Transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous (and periodic), and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle. The Discrete Fourier transform transforms a sequence of N complex numbers: {x_n} = x₀, x₁, x₂ ..., x_N-1 into another sequence of complex numbers: {X_k} = X₀, X₁, X₂ ..., X_N-1 which is defined by: The Discrete-Time Fourier Transform (DTFT) is a form of Fourier analysis that is applicable to the uniformly-spaced samples of a continuous function. The term discrete-time refers to the fact that the transform operates on discrete data (samples) whose interval often has units of time. From only the samples, it produces a function of frequency that is a periodic summation of the continuous Fourier transform of the original continuous function. A Fast Fourier Transform (FFT) is an algorithm that samples a signal over a period of time (or space) and divides it into its frequency components. These components are single sinusoidal oscillations at distinct frequencies each with their own amplitude and phase. This transformation is illustrated in Diagram below. Over the time period measured in the diagram, the signal contains 3 distinct dominant frequencies. View of a signal in the time and frequency domain: An FFT algorithm computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IFFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from O(n²), which arises if one simply applies the definition of DFT, to O(n log n), where n is the data size. Here a discrete Fourier analysis of a sum of cosine waves at 10, 20, 30, 40, and 50 Hz: The Fourier Transform is one of deepest insights ever made. Unfortunately, the meaning is buried within dense equations: and Rather than jumping into the symbols, let's experience the key idea firsthand. Here's a plain-English metaphor: Think With Circles, Not Just Sinusoids The Fourier Transform is about circular paths (not 1-d sinusoids) and Euler's formula is a clever way to generate one: Must we use imaginary exponents to move in a circle? Nope. But it's convenient and compact. And sure, we can describe our path as coordinated motion in two dimensions (real and imaginary), but don't forget the big picture: we're just moving in a circle. Discovering The Full Transform The big insight: our signal is just a bunch of time spikes! If we merge the recipes for each time spike, we should get the recipe for the full signal. The Fourier Transform builds the recipe frequency-by-frequency: A few notes: Stuart Riffle has a great interpretation of the Fourier Transform: - FT - DFT - DTFT - FFT

In mathematics, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. With this method, it is possible to evaluate a polynomial with only n additions and n multiplications. Hence, its storage requirements are n times the number of bits of x. Horner's method can be based on the following identity: This identity is called Horner's rule. To solve the right part of the identity above, for a given x, we start by iterating through the polynomial from the inside out, accumulating each iteration result. After n iterations, with n being the order of the polynomial, the accumulated result gives us the polynomial evaluation. Using the polynomial: Now, using the same scenario but with Horner's rule, the polynomial can be re-written as x * (x * (x * (4 * x + 2) + 3) + 1) + 3, representing it as [4, 2, 3, 1, 3] it is possible to save the first iteration as acc = arr[0] * (x=2) + arr[1], and then finish iterations for acc *= (x=2) + arr[index]. In the same scenario but using Horner's rule, a total of 10 operations would have happened, composed of only 4 additions and 4 multiplications.

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be partitioned in five distinct ways: 4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 The order-dependent composition 1 + 3 is the same partition as 3 + 1, while the two distinct compositions 1 + 2 + 1 and 1 + 1 + 2 represent the same partition 2 + 1 + 1. Young diagrams associated to the partitions of the positive integers 1 through 8. They are arranged so that images under the reflection about the main diagonal of the square are conjugate partitions.

Given a positive integer, write a function to find if it is a power of two or not. Naive solution In naive solution we just keep dividing the number by two unless the number becomes 1 and every time we do so, we check that remainder after division is always 0. Otherwise, the number can't be a power of two. Bitwise solution Powers of two in binary form always have just one bit set. The only exception is with a signed integer (e.g. an 8-bit signed integer with a value of -128 looks like: 10000000) 1: 0001 2: 0010 4: 0100 8: 1000 So after checking that the number is greater than zero, we can use a bitwise hack to test that one and only one bit is set. number & (number - 1) For example for number 8 that operations will look like: 1000 ---- 0111 1000 & 0111 ---- 0000

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a,0) as 0 for all a, which is the result of taking the lcm to be the least upper bound in the lattice of divisibility. What is the LCM of 4 and 6? Multiples of 4 are: 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ... and the multiples of 6 are: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ... Common multiples of 4 and 6 are simply the numbers that are in both lists: 12, 24, 36, 48, 60, 72, .... So, from this list of the first few common multiples of the numbers 4 and 6, their least common multiple is 12. The following formula reduces the problem of computing the least common multiple to the problem of computing the greatest common divisor (GCD), also known as the greatest common factor: lcm(a, b) = |a * b| / gcd(a, b) A Venn diagram showing the least common multiples of combinations of 2, 3, 4, 5 and 7 (6 is skipped as it is 2 × 3, both of which are already represented). For example, a card game which requires its cards to be divided equally among up to 5 players requires at least 60 cards, the number at the intersection of the 2, 3, 4 and 5 sets, but not the 7 set.

Liu Hui remarked in his commentary to The Nine Chapters on the Mathematical Art, that the ratio of the circumference of an inscribed hexagon to the diameter of the circle was three, hence π must be greater than three. He went on to provide a detailed step-by-step description of an iterative algorithm to calculate π to any required accuracy based on bisecting polygons; he calculated π to between 3.141024 and 3.142708 with a 96-gon; he suggested that 3.14 was a good enough approximation, and expressed π as 157/50; he admitted that this number was a bit small. Later he invented an ingenious quick method to improve on it, and obtained π ≈ 3.1416 with only a 96-gon, with an accuracy comparable to that from a 1536-gon. His most important contribution in this area was his simple iterative π algorithm. Liu Hui argued: > Multiply one side of a hexagon by the radius (of its circumcircle), then multiply this by three, to yield the area of a dodecagon; if we cut a hexagon into a dodecagon, multiply its side by its radius, then again multiply by six, we get the area of a 24-gon; the finer we cut, the smaller the loss with respect to the area of circle, thus with further cut after cut, the area of the resulting polygon will coincide and become one with the circle; there will be no loss Liu Hui's method of calculating the area of a circle. Further, Liu Hui proved that the area of a circle is half of its circumference multiplied by its radius. He said: > Between a polygon and a circle, there is excess radius. Multiply the excess radius by a side of the polygon. The resulting area exceeds the boundary of the circle In the diagram d = excess radius. Multiplying d by one side results in oblong ABCD which exceeds the boundary of the circle. If a side of the polygon is small (i.e. there is a very large number of sides), then the excess radius will be small, hence excess area will be small. > Multiply the side of a polygon by its radius, and the area doubles; hence multiply half the circumference by the radius to yield the area of circle. The area within a circle is equal to the radius multiplied by half the circumference, or A = r x C/2 = r x r x π. Liu Hui began with an inscribed hexagon. Let M be the length of one side AB of hexagon, r is the radius of circle. Bisect AB with line OPC, AC becomes one side of dodecagon (12-gon), let its length be m. Let the length of PC be j and the length of OP be G. the Gou Gu (Pythagorean theorem) theorem repetitively: From here, there is now a technique to determine m from M, which gives the side length for a polygon with twice the number of edges. Starting with a hexagon, Liu Hui could determine the side length of a dodecagon using this formula. Then continue repetitively to determine the side length of a 24-gon given the side length of a dodecagon. He could do this recursively as many times as necessary. Knowing how to determine the area of these polygons, Liu Hui could then approximate π.

In mathematics, a matrix (plural matrices) is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns. For example, the dimension of the matrix below is 2 × 3 (read "two by three"), because there are two rows and three columns: An m × n matrix: the m rows are horizontal, and the n columns are vertical. Each element of a matrix is often denoted by a variable with two subscripts. For example, <i>a_2,1</i> represents the element at the second row and first column of the matrix To add two matrices: add the numbers in the matching positions: The two matrices must be the same size, i.e. the rows must match in size, and the columns must match in size. To subtract two matrices: subtract the numbers in the matching positions: We can multiply a matrix by a constant (the value 2 in this case): To multiply a matrix by another matrix we need to do the dot product of rows and columns. To work out the answer for the 1st row and 1st column: Here it is for the 1st row and 2nd column: If we'll do the same for the rest of the rows and columns we'll get the following resulting matrix: To "transpose" a matrix, swap the rows and columns. We put a "T" in the top right-hand corner to mean transpose:

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients. The rows of Pascal's triangle are conventionally enumerated starting with row n = 0 at the top (the 0th row). The entries in each row are numbered from the left beginning with k = 0 and are usually staggered relative to the numbers in the adjacent rows. The triangle may be constructed in the following manner: In row 0 (the topmost row), there is a unique nonzero entry 1. Each entry of each subsequent row is constructed by adding the number above and to the left with the number above and to the right, treating blank entries as 0. For example, the initial number in the first (or any other) row is 1 (the sum of 0 and 1), whereas the numbers 1 and 3 in the third row are added to produce the number 4 in the fourth row. The entry in the nth row and kth column of Pascal's triangle is denoted . For example, the unique nonzero entry in the topmost row is . With this notation, the construction of the previous paragraph may be written as follows: for any non-negative integer n and any integer k between 0 and n, inclusive. We know that i-th entry in a line number lineNumber is Binomial Coefficient C(lineNumber, i) and all lines start with value 1. The idea is to calculate C(lineNumber, i) using C(lineNumber, i-1). It can be calculated in O(1) time using the following: C(lineNumber, i) = lineNumber! / ((lineNumber - i)! * i!) C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!) We can derive following expression from above two expressions: C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i So C(lineNumber, i) can be calculated from C(lineNumber, i - 1) in O(1) time.

A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 6 is composite because it is the product of two numbers (2 × 3) that are both smaller than 6. A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input).

Prime number is a whole number greater than 1 that cannot be made by multiplying other whole numbers. The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19 and so on. If we can make it by multiplying other whole numbers it is a Composite Number. Prime factors are those prime numbers which multiply together to give the original number. For example 39 will have prime factors of 3 and 13 which are also prime numbers. Another example is 15 whose prime factors are 3 and 5. The approach is to keep on dividing the natural number n by indexes from i = 2 to i = n (by prime indexes only). The value of n is being overridden by (n / i) on each iteration. The time complexity till now is O(n) in the worst case scenario since the loop runs from index i = 2 to i = n. This time complexity can be reduced from O(n) to O(sqrt(n)). The optimisation is achievable when loop runs from i = 2 to i = sqrt(n). Now, we go only till O(sqrt(n)) because when i becomes greater than sqrt(n), we have the confirmation that there is no index i left which can divide n completely other than n itself. In 1917, a theorem was formulated by G.H Hardy and Srinivasa Ramanujan which states that the normal order of the number ω(n) of distinct prime factors of a number n is log(log(n)). Roughly speaking, this means that most numbers have about this number of distinct prime factors.

The radian (symbol rad) is the unit for measuring angles, and is the standard unit of angular measure used in many areas of mathematics. The length of an arc of a unit circle is numerically equal to the measurement in radians of the angle that it subtends; one radian is just under 57.3 degrees. An arc of a circle with the same length as the radius of that circle subtends an angle of 1 radian. The circumference subtends an angle of 2π radians. A complete revolution is 2π radians (shown here with a circle of radius one and thus circumference 2π). Conversions

The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to some limit n. It is attributed to Eratosthenes of Cyrene, an ancient Greek mathematician. 1. Create a boolean array of n + 1 positions (to represent the numbers 0 through n) 2. Set positions 0 and 1 to false, and the rest to true 3. Start at position p = 2 (the first prime number) 4. Mark as false all the multiples of p (that is, positions 2 * p, 3 * p, 4 * p... until you reach the end of the array) 5. Find the first position greater than p that is true in the array. If there is no such position, stop. Otherwise, let p equal this new number (which is the next prime), and repeat from step 4 When the algorithm terminates, the numbers remaining true in the array are all the primes below n. An improvement of this algorithm is, in step 4, start marking multiples of p from p * p, and not from 2 * p. The reason why this works is because, at that point, smaller multiples of p will have already been marked false. The algorithm has a complexity of O(n log(log n)).

In numerical analysis, a branch of mathematics, there are several square root algorithms or methods of computing the principal square root of a non-negative real number. As, generally, the roots of a function cannot be computed exactly. The root-finding algorithms provide approximations to roots expressed as floating point numbers. Finding is the same as solving the equation for a positive x. Therefore, any general numerical root-finding algorithm can be used. Newton's method (also known as the Newton–Raphson method), named after method for finding successively better approximations to the roots of a real-valued function. Let's start by explaining the general idea of Newton's method and then apply it to our particular case with finding a square root of the number. The Newton–Raphson method in one variable is implemented as follows: The method starts with a function f defined over the real numbers x, the function's derivative f', and an initial guess x0 for a root of the function f. If the function satisfies the assumptions made in the derivation of the formula and the initial guess is close, then a better approximation x1 is: Geometrically, (x1, 0) is the intersection of the x-axis and the tangent of the graph of f at (x0, f (x0)). The process is repeated as: until a sufficiently accurate value is reached. As it was mentioned above, finding is the same as solving the equation for a positive x. The derivative of the function f(x) in case of square root problem is 2x. After applying the Newton's formula (see above) we get the following equation for our algorithm iterations: x := x - (x² - S) / (2x) The x² − S above is how far away x² is from where it needs to be, and the division by 2x is the derivative of x², to scale how much we adjust x by how quickly x² is changing.

The k-Means algorithm is an unsupervised Machine Learning algorithm. It's a clustering algorithm, which groups the sample data on the basis of similarity between dimensions of vectors. In k-Means classification, the output is a set of classes assigned to each vector. Each cluster location is continuously optimized in order to get the accurate locations of each cluster such that they represent each group clearly. The idea is to calculate the similarity between cluster location and data vectors, and reassign clusters based on it. Euclidean distance is used mostly for this task. The algorithm is as follows: 1. Check for errors like invalid/inconsistent data 2. Initialize the k cluster locations with initial/random k points 3. Calculate the distance of each data point from each cluster 4. Assign the cluster label of each data point equal to that of the cluster at its minimum distance 5. Calculate the centroid of each cluster based on the data points it contains 6. Repeat each of the above steps until the centroid locations are varying Here is a visualization of k-Means clustering for better understanding: The centroids are moving continuously in order to create better distinction between the different set of data points. As we can see, after a few iterations, the difference in centroids is quite low between iterations. For example between iterations 13 and 14 the difference is quite small because there the optimizer is tuning boundary cases.

The k-nearest neighbors algorithm (k-NN) is a supervised Machine Learning algorithm. It's a classification algorithm, determining the class of a sample vector using a sample data. In k-NN classification, the output is a class membership. An object is classified by a plurality vote of its neighbors, with the object being assigned to the class most common among its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of that single nearest neighbor. The idea is to calculate the similarity between two data points on the basis of a distance metric. Euclidean distance is used mostly for this task. The algorithm is as follows: 1. Check for errors like invalid data/labels. 2. Calculate the euclidean distance of all the data points in training data with the classification point 3. Sort the distances of points along with their classes in ascending order 4. Take the initial K classes and find the mode to get the most similar class 5. Report the most similar class Here is a visualization of k-NN classification for better understanding: The test sample (green dot) should be classified either to blue squares or to red triangles. If k = 3 (solid line circle) it is assigned to the red triangles because there are 2 triangles and only 1 square inside the inner circle. If k = 5 (dashed line circle) it is assigned to the blue squares (3 squares vs. 2 triangles inside the outer circle). Another k-NN classification example: Here, as we can see, the classification of unknown points will be judged by their proximity to other points. It is important to note that K is preferred to have odd values in order to break ties. Usually K is taken as 3 or 5.

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array. Time Complexity: O(log(n)) - since we split search area by two for every next iteration.

Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). For example we have a sorted array of n uniformly distributed values arr[], and we need to write a function to search for a particular element x in the array. Linear Search finds the element in O(n) time, Jump Search takes O(√ n) time and Binary Search take O(Log n) time. The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side. To find the position to be searched, it uses following formula: // The idea of formula is to return higher value of pos // when element to be searched is closer to arr[hi]. And // smaller value when closer to arr[lo] pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo])) arr[] - Array where elements need to be searched x - Element to be searched lo - Starting index in arr[] hi - Ending index in arr[] Time complexity: O(log(log(n))

Like Binary Search, Jump Search (or Block Search) is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements. For example, suppose we have an array arr[] of size n and block (to be jumped) of size m. Then we search at the indexes arr[0], arr[m], arr[2 * m], ..., arr[k * m] and so on. Once we find the interval arr[k * m] < x < arr[(k+1) * m], we perform a linear search operation from the index k * m to find the element x. What is the optimal block size to be skipped? In the worst case, we have to do n/m jumps and if the last checked value is greater than the element to be searched for, we perform m - 1 comparisons more for linear search. Therefore the total number of comparisons in the worst case will be ((n/m) + m - 1). The value of the function ((n/m) + m - 1) will be minimum when m = √n. Therefore, the best step size is m = √n. Time complexity: O(√n) - because we do search by blocks of size √n.

In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. Linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. Time Complexity: O(n) - since in worst case we're checking each element exactly once.

In set theory a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. Cartesian product AxB of two sets A={x,y,z} and B={1,2,3}

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: Input: candidates = [2,3,6,7], target = 7, A solution set is: [7], [2,2,3] ] Input: candidates = [2,3,5], target = 8, A solution set is: [2,2,2,2], [2,3,3], [3,5] ] Since the problem is to get all the possible results, not the best or the number of result, thus we don’t need to consider DP (dynamic programming), backtracking approach using recursion is needed to handle it. Here is an example of decision tree for the situation when candidates = [2, 3] and target = 6: 0 / \ +2 +3 / \ \ +2 +3 +3 / \ / \ \ +2 ✘ ✘ ✘ ✓ / \ ✓ ✘

When the order doesn't matter, it is a Combination. When the order does matter it is a Permutation. "My fruit salad is a combination of apples, grapes and bananas" We don't care what order the fruits are in, they could also be "bananas, grapes and apples" or "grapes, apples and bananas", its the same fruit salad. This is how lotteries work. The numbers are drawn one at a time, and if we have the lucky numbers (no matter what order) we win! No Repetition: such as lottery numbers (2,14,15,27,30,33) Number of combinations where n is the number of things to choose from, and we choose r of them, no repetition, order doesn't matter. It is often called "n choose r" (such as "16 choose 3"). And is also known as the Binomial Coefficient. Repetition is Allowed: such as coins in your pocket (5,5,5,10,10) Or let us say there are five flavours of ice cream: We can have three scoops. How many variations will there be? Let's use letters for the flavours: {b, c, l, s, v}. Example selections include: Number of combinations Where n is the number of things to choose from, and we choose r of them. Repetition allowed, order doesn't matter. Permutations cheat sheet Combinations cheat sheet Permutations/combinations algorithm ideas.

The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place.

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item 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. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? The most common problem being solved is the 0/1 knapsack problem, which restricts the number xi of copies of each kind of item to zero or one. Given a set of n items numbered from 1 up to n, each with a weight wi and a value vi, along with a maximum weight capacity W, maximize subject to and Here xi represents the number of instances of item i to include in the knapsack. Informally, the problem is to maximize the sum of the values of the items in the knapsack so that the sum of the weights is less than or equal to the knapsack's capacity. The bounded knapsack problem (BKP) removes the restriction that there is only one of each item, but restricts the number integer value c: maximize subject to and The unbounded knapsack problem (UKP) places no upper bound on the number of copies of each kind of item and can be formulated as above except for that the only restriction on xi is that it is a non-negative integer. maximize subject to and

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. The longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence. Dynamic programming approach has complexity O(n * n). In the first 16 terms of the binary Van der Corput sequence 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 a longest increasing subsequence is 0, 2, 6, 9, 11, 15. This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance, 0, 4, 6, 9, 11, 15 or 0, 2, 6, 9, 13, 15 or 0, 4, 6, 9, 13, 15 are other increasing subsequences of equal length in the same input sequence.

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array, a[1...n], of numbers which has the largest sum, where, The list usually contains both positive and negative numbers along with 0. For example, for the array of values −2, 1, −3, 4, −1, 2, 1, −5, 4 the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

When the order doesn't matter, it is a Combination. When the order does matter it is a Permutation. "The combination to the safe is 472". We do care about the order. 724 won't work, nor will 247. It has to be exactly 4-7-2. A permutation, also called an “arrangement number” or “order”, is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. Below are the permutations of string ABC. Or for example the first three people in a running race: you can't be first and second. Number of combinations n * (n-1) * (n -2) * ... * 1 = n! When repetition is allowed we have permutations with repetitions. For example the the lock below: it could be 333. Number of combinations n * n * n ... (r times) = n^r Permutations cheat sheet Combinations cheat sheet Permutations/combinations algorithm ideas.

Power set of a set S is the set of all of the subsets of S, including the empty set and S itself. Power set of set S is denoted as P(S). For example for {x, y, z}, the subsets are: { {}, // (also denoted empty set ∅ or the null set) {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} } Here is how we may illustrate the elements of the power set of the set {x, y, z} ordered with respect to inclusion: Number of Subsets If S is a finite set with |S| = n elements, then the number of subsets of S is |P(S)| = 2^n. This fact, which is the motivation for the notation 2^S, may be demonstrated simply as follows: > First, order the elements of S in any manner. We write any subset of S in the format {γ1, γ2, ..., γn} where γi , 1 ≤ i ≤ n, can take the value of 0 or 1. If γi = 1, the i-th element of S is in the subset; otherwise, the i-th element is not in the subset. Clearly the number of distinct subsets that can be constructed this way is 2^n as γi ∈ {0, 1}. Each number in binary representation in a range from 0 to 2^n does exactly what we need: it shows by its bits (0 or 1) whether to include related element from the set or not. For example, for the set {1, 2, 3} the binary number of 0b010 would mean that we need to include only 2 to the current set. > See bwPowerSet.js file for bitwise solution. In backtracking approach we're constantly trying to add next element of the set to the subset, memorizing it and then removing it and try the same with the next element. > See btPowerSet.js file for backtracking solution. * Wikipedia * Math is Fun

The shortest common supersequence (SCS) of two sequences X and Y is the shortest sequence which has X and Y as subsequences. In other words assume we're given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences. This is a problem closely related to the longest common subsequence problem. Input: str1 = "geek", str2 = "eke" Output: "geeke" Input: str1 = "AGGTAB", str2 = "GXTXAYB" Output: "AGXGTXAYB"

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order (ascending or descending arrangement). The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently. Because counting sort uses key values as indexes into an array, it is not a comparison sort, and the Ω(n log n) lower bound for comparison sorting does not apply to it. Bucket sort may be used for many of the same tasks as counting sort, with a similar time analysis; however, compared to counting sort, bucket sort requires linked lists, dynamic arrays or a large amount of preallocated memory to hold the sets of items within each bucket, whereas counting sort instead stores a single number (the count of items) per bucket. Counting sorting works best when the range of numbers for each array element is very small. Step I In first step we calculate the count of all the elements of the input array A. Then Store the result in the count array C. The way we count is depicted below. Step II In second step we calculate how many elements exist in the input array A which are less than or equals for the given index. Step III In this step we place the input array A element at sorted position by taking help of constructed count array C ,i.e what we constructed in step two. We used the result array B to store the sorted elements. Here we handled the index of B start from zero.

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945. An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged. A recursive merge sort algorithm used to sort an array of 7 integer values. These are the steps a human would take to emulate merge sort (top-down).

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays The steps are: 1. Pick an element, called a pivot, from the array. 2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. 3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values. Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.

In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Where does the name come from? In mathematical numeral systems, the radix or base is the number of unique digits, including the digit zero, used to represent numbers in a positional numeral system. For example, a binary system (using numbers 0 and 1) has a radix of 2 and a decimal system (using numbers 0 to 9) has a radix of 10. The topic of the efficiency of radix sort compared to other sorting algorithms is somewhat tricky and subject to quite a lot of misunderstandings. Whether radix sort is equally efficient, less efficient or more efficient than the best comparison-based algorithms depends on the details of the assumptions made. Radix sort complexity is O(wn) for n keys which are integers of word size w. Sometimes w is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which all perform O(n log n) comparisons to sort n keys. However, in general w cannot be considered a constant: if all n keys are distinct, then w has to be at least log n for a random-access machine to be able to store them in memory, which gives at best a time complexity O(n log n). That would seem to make radix sort at most equally efficient as the best comparison-based sorts (and worse if keys are much longer than log n).

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange For our example and ease of understanding, we take the interval of 4. Make a virtual sub-list of all values located at the interval of 4 positions. Here these values are We compare values in each sub-list and swap them (if necessary) in the original array. After this step, the new array should look like this Then, we take interval of 2 and this gap generates two sub-lists We compare and swap the values, if required, in the original array. After this step, the array should look like this > UPD: On the picture below there is a typo and result array is supposed to be [14, 10, 27, 19, 35, 33, 42, 44]. Finally, we sort the rest of the array using interval of value 1. Shell sort uses insertion sort to sort the array.

the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. The Hamming distance between:

The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" T by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

The Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. Mathematically, the Levenshtein distance between two strings where where is the indicator function equal to 0 when and equal to 1 otherwise, and is the distance between the first i characters of a and the first Note that the first element in the minimum corresponds to deletion (from a to b), the second to insertion and the third to match or mismatch, depending on whether the respective symbols are the same. For example, the Levenshtein distance between kitten and into the other, and there is no way to do it with fewer than three edits: 1. kitten → sitten (substitution of "s" for "k") 2. sitten → sittin (substitution of "i" for "e") 3. sittin → sitting (insertion of "g" at the end). This has a wide range of applications, for instance, spell checkers, correction systems for optical character recognition, fuzzy string searching, and software to assist natural language translation based on translation memory. Let’s take a simple example of finding minimum edit distance between strings ME and MY. Intuitively you already know that minimum edit distance here is 1 operation, which is replacing E with Y. But let’s try to formalize it in a form of the algorithm in order to be able to do more complex examples like transforming Saturday into Sunday. To apply the mathematical formula mentioned above to ME → MY transformation we need to know minimum edit distances of ME → M, M → MY and M → M transformations in prior. Then we will need to pick the minimum one and add one operation to transform last letters E → Y. So minimum edit distance of ME → MY transformation is being calculated based on three previously possible transformations. To explain this further let’s draw the following matrix: transform M to an empty string. And it is by deleting M. This is why this number is red. to transform ME to an empty string. And it is by deleting E and M. to transform an empty string to M. And it is by inserting M. This is why this number is green. to transform an empty string to MY. And it is by inserting Y and M. to transform M into M. to transform ME to M. And it is by deleting E. This looks easy for such small matrix as ours (it is only 3x3). But here you may find basic concepts that may be applied to calculate all those numbers for bigger matrices (let’s say a 9x7 matrix for Saturday → Sunday transformation). According to the formula you only need three adjacent cells (i-1:j), (i-1:j-1), and (i:j-1) to calculate the number for current cell (i:j). All we need to do is to find the minimum of those three cells and then add 1 in case if we have different letters in i's row and j's column. You may clearly see the recursive nature of the problem. Let's draw a decision graph for this problem. You may see a number of overlapping sub-problems on the picture that are marked with red. Also there is no way to reduce the number of operations and make it less than a minimum of those three adjacent cells from the formula. Also you may notice that each cell number in the matrix is being calculated based on previous ones. Thus the tabulation technique (filling the cache in bottom-up direction) is being applied here. Applying this principle further we may solve more complicated cases like with Saturday → Sunday transformation.

The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings. The longest common substring of the strings ABABC, BABCA and ABABC ||| BABCA ||| ABCBA

In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find any one of a set of pattern strings in a text. The Rabin–Karp algorithm seeks to speed up the testing of equality of the pattern to the substrings in the text by using a hash function. A hash function is a function which converts every string into a numeric value, called its hash value; for example, we might have hash('hello') = 5. The algorithm exploits the fact that if two strings are equal, their hash values are also equal. Thus, string matching is reduced (almost) to computing the hash value of the search pattern and then looking for substrings of the input string with that hash value. However, there are two problems with this approach. First, because there are so many different strings and so few hash values, some differing strings will have the same hash value. If the hash values match, the pattern and the substring may not match; consequently, the potential match of search pattern and the substring must be confirmed by comparing them; that comparison can take a long time for long substrings. Luckily, a good hash function on reasonable strings usually does not have many collisions, so the expected search time will be acceptable. The key to the Rabin–Karp algorithm's performance is the efficient computation of hash values of the successive substrings of the text. The Rabin fingerprint is a popular and effective rolling hash function. The polynomial hash function described in this example is not a Rabin fingerprint, but it works equally well. It treats every substring as a number in some base, the base being usually a large prime. For text of length n and p patterns of combined length m, its average and best case running time is O(n + m) in space O(p), but its worst-case time is O(n * m). A practical application of the algorithm is detecting plagiarism. Given source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single-string searching algorithms are impractical.

Given an input string s and a pattern p, implement regular expression matching with support for . and *. The matching should cover the entire input string (not partial). Note Example #1 Input: s = 'aa' p = 'a' Output: false Explanation: a does not match the entire string aa. Example #2 Input: s = 'aa' p = 'a*' Output: true Explanation: * means zero or more of the preceding element, a. Therefore, by repeating a once, it becomes aa. Example #3 Input: s = 'ab' p = '.' Output: true Explanation: .* means "zero or more (*) of any character (.)". Example #4 Input: s = 'aab' p = 'ca*b' Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches aab.

The Z-algorithm finds occurrences of a "word" W within a main "text string" T in linear time O(|W| + |T|). Given a string S of length n, the algorithm produces an array, Z where Z[i] represents the longest substring starting from S[i] which is also a prefix of S. Finding with a nonce character, say $ followed by the text, T, helps with pattern matching, for if there is some index i such that Z[i] equals the pattern length, then the pattern must be present at that point. While the Z array can be computed with two nested loops in O(|W| * |T|) time, the following strategy shows how to obtain it in linear time, based on the idea that as we iterate over the letters in the string (index i from 1 to n - 1), we maintain an interval [L, R] which is the interval with maximum R such that 1 ≤ L ≤ i ≤ R and S[L...R] is a prefix that is also a substring (if no such interval exists, just let L = R =  - 1). For i = 1, we can simply compute L and R by comparing S[0...] to S[1...]. Example of Z array Index 0 1 2 3 4 5 6 7 8 9 10 11 Text a a b c a a b x a a a z Z values X 1 0 0 3 1 0 0 2 2 1 0 Other examples str = a a a a a a Z[] = x 5 4 3 2 1 str = a a b a a c d Z[] = x 1 0 2 1 0 0 str = a b a b a b a b Z[] = x 0 6 0 4 0 2 0 Example of Z box

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors. BFS(root) Pre: root is the node of the BST Post: the nodes in the BST have been visited in breadth first order q ← queue while root = ø yield root.value if root.left = ø q.enqueue(root.left) end if if root.right = ø q.enqueue(root.right) end if if !q.isEmpty() root ← q.dequeue() else root ← ø end if end while end BFS

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Say you have an array prices for which the i-th element is the price of a given stock on day i. Find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). > Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example #1 Input: [7, 1, 5, 3, 6, 4] Output: 7 Example #2 Input: [1, 2, 3, 4, 5] Output: 4 Example #3 Input: [7, 6, 4, 3, 1] Output: 0 We may try all combinations of buying and selling and find out the most profitable one by applying divide and conquer approach. Let's say we have an array of prices [7, 6, 4, 3, 1] and we're on the 1st day of trading (at the very beginning of the array). At this point we may say that the overall maximum profit would be the maximum of two following values: 1. Option 1: Keep the money → profit would equal to the profit from buying/selling the rest of the stocks → keepProfit = profit([6, 4, 3, 1]). 2. Option 2: Buy/sell at current price → profit in this case would equal to the profit from buying/selling the rest of the stocks plus (or minus, depending on whether we're selling or buying) the current stock price → buySellProfit = -7 + profit([6, 4, 3, 1]). The overall profit would be equal to → overalProfit = Max(keepProfit, buySellProfit). As you can see the profit([6, 4, 3, 1]) task is being solved in the same recursive manner. > See the full code example in dqBestTimeToBuySellStocks.js As you may see, every recursive call will produce 2 more recursive branches. The depth of the recursion will be n (size of prices array) and thus, the time complexity will equal to O(2^n). As you may see, this is very inefficient. For example for just 20 prices the number of recursive calls will be somewhere close to 2M! If we avoid cloning the prices array between recursive function calls and will use the array pointer then additional space complexity will be proportional to the depth of the recursion: O(n) If we plot the prices array (i.e. [7, 1, 5, 3, 6, 4]) we may notice that the points of interest are the consecutive valleys and peaks So, if we will track the growing price and will sell the stocks immediately before the price goes down we'll get the maximum profit (remember, we bought the stock in the valley at its low price). > See the full code example in peakvalleyBestTimeToBuySellStocks.js Since the algorithm requires only one pass through the prices array, the time complexity would equal O(n). Except of the prices array itself the algorithm consumes the constant amount of memory. Thus, additional space complexity is O(1). There is even simpler approach exists. Let's say we have the prices array which looks like this [1, 7, 2, 3, 6, 7, 6, 7]: You may notice, that we don't even need to keep tracking of a constantly growing price. Instead, we may simply add the price difference for all growing segments of the chart which eventually sums up to the highest possible profit, > See the full code example in accumulatorBestTimeToBuySellStocks.js Since the algorithm requires only one pass through the prices array, the time complexity would equal O(n). Except of the prices array itself the algorithm consumes the constant amount of memory. Thus, additional space complexity is O(1).

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: stacks and placing it on top of another stack or on an empty rod. Animation of an iterative algorithm solving 6-disk problem With 3 disks, the puzzle can be solved in 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2^n − 1, where n is the number of disks.

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example #1 Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example #2 Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index. We call a position in the array a "good index" if starting at that position, we can reach the last index. Otherwise, that index is called a "bad index". The problem then reduces to whether or not index 0 is a "good index". This is the inefficient solution where we try every single jump pattern that takes us from the first position to the last. We start from the first position and jump to every index that is reachable. We repeat the process until last index is reached. When stuck, backtrack. > See backtrackingJumpGame.js file Time complexity:: O(2^n). There are 2ⁿ (upper bound) ways of jumping from the first position to the last, where n is the length of array nums. Auxiliary Space Complexity: O(n). Recursion requires additional memory for the stack frames. Top-down Dynamic Programming can be thought of as optimized backtracking. It relies on the observation that once we determine that a certain index is good / bad, this result will never change. This means that we can store the result and not need to recompute it every time. Therefore, for each position in the array, we remember whether the index is good or bad. Let's call this array memo and let its values be either one of: GOOD, BAD, UNKNOWN. This technique is called memoization. > See dpTopDownJumpGame.js file Time complexity:: O(n^2). For every element in the array, say i, we are looking at the next nums[i] elements to its right aiming to find a GOOD index. nums[i] can be at most n, where n is the length of array nums. Auxiliary Space Complexity: O(2 * n) = O(n). First n originates from recursion. Second n comes from the usage of the memo table. Top-down to bottom-up conversion is done by eliminating recursion. In practice, this achieves better performance as we no longer have the method stack overhead and might even benefit from some caching. More importantly, this step opens up possibilities for future optimization. The recursion is usually eliminated by trying to reverse the order of the steps from the top-down approach. The observation to make here is that we only ever jump to the right. This means that if we start from the right of the array, every time we will query a position to our right, that position has already be determined as being GOOD or BAD. This means we don't need to recurse anymore, as we will always hit the memo table. > See dpBottomUpJumpGame.js file Time complexity:: O(n^2). For every element in the array, say i, we are looking at the next nums[i] elements to its right aiming to find a GOOD index. nums[i] can be at most n, where n is the length of array nums. Auxiliary Space Complexity: O(n). This comes from the usage of the memo table. Once we have our code in the bottom-up state, we can make one final, important observation. From a given position, when we try to see if we can jump to a GOOD position, we only ever use one - the first one. In other words, the left-most one. If we keep track of this left-most GOOD position as a separate variable, we can avoid searching for it in the array. Not only that, but we can stop using the array altogether. > See greedyJumpGame.js file Time complexity:: O(n). We are doing a single pass through the nums array, hence n steps, where n is the length of array nums. Auxiliary Space Complexity: O(1). We are not using any extra memory.

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open. The knight's tour problem is the mathematical problem of finding a knight's tour. Creating a program to find a knight's tour is a common problem given to computer science students. Variations of the knight's tour problem involve chessboards of different sizes than the usual 8×8, as well as irregular (non-rectangular) boards. The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the Hamiltonian cycle problem. An open knight's tour of a chessboard. An animation of an open knight's tour on a 5 by 5 board.

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3. For example, following is a solution for 4 Queen problem. The expected output is a binary matrix which has 1s for the blocks where queens are placed. For example following is the output matrix for above 4 queen solution. { 0, 1, 0, 0} { 0, 0, 0, 1} { 1, 0, 0, 0} { 0, 0, 1, 0} Generate all possible configurations of queens on board and print a configuration that satisfies the given constraints. while there are untried configurations { generate the next configuration if queens don't attack in this configuration then { print this configuration; } } The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false. 1) Start in the leftmost column 2) If all queens are placed return true 3) Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution. b) If placing queen in [row, column] leads to a solution then return true. c) If placing queen doesn't lead to a solution then umark this [row, column] (Backtrack) and go to step (a) to try other rows. 3) If all rows have been tried and nothing worked, return false to trigger backtracking. Bitwise algorithm basically approaches the problem like this: can only be one queen in each row, one in each column, and at most one on each diagonal. place a queen, then move to the second row, place a second queen, and so on until either a) we reach a valid solution or b) we reach a dead end (ie. we can't place a queen such that it is "safe" from the other queens). horizontal attacks, since no queen will ever be on the same row as another queen. certain square: 1) The square's column doesn't have any other queens on it, 2) the square's left diagonal doesn't have any other queens on it, and 3) the square's right diagonal doesn't have any other queens on it. give up on our current attempt and immediately test out the next possibility. First let's talk about the recursive function. You'll notice that it accepts 3 parameters: leftDiagonal, column, and rightDiagonal. Each of these is technically an integer, but the algorithm takes advantage of the fact that an integer is represented by a sequence of bits. So, think of each of these parameters as a sequence of N bits. Each bit in each of the parameters represents whether the corresponding location on the current row is "available". For example: already occupied by a queen. top-left-to-bottom-right diagonals that pass through columns 4 and 5 of that row are already occupied by queens. Below is a visual aid for leftDiagonal, column, and rightDiagonal. - Wikipedia - Solution by Greg Trowbridge

Given an array of non-negative integers representing terraces in an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. Example #1 Input: arr[] = [2, 0, 2] Output: 2 Structure is like below: We can trap 2 units of water in the middle gap. Example #2 Input: arr[] = [3, 0, 0, 2, 0, 4] Output: 10 Structure is like below: | We can trap "3*2 units" of water between 3 an 2, "1 unit" on top of bar 2 and "3 units" between 2 and 4. See below diagram also. Example #3 Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 Structure is like below: | | || | Trap "1 unit" between first 1 and 2, "4 units" between first 2 and 3 and "1 unit" between second last 1 and last 2. An element of array can store water if there are higher bars on left and right. We can find amount of water to be stored in every element by finding the heights of bars on left and right sides. The idea is to compute amount of water that can be stored in every element of array. For example, consider the array on top of bar 2 and "3 units" between 2 and 4. See below diagram also. Intuition For each element in the array, we find the maximum level of water it can trap after the rain, which is equal to the minimum of maximum height of bars on both the sides minus its own height. Steps - Initialize max_left = 0 and max_right = 0 - Iterate from the current element to the beginning of array updating: max_left = max(max_left, height[j]) - Iterate from the current element to the end of array updating: max_right = max(max_right, height[j]) - Add min(max_left, max_right) − height[i] to answer Complexity Analysis Time complexity: O(n^2). For each element of array, we iterate the left and right parts. Auxiliary space complexity: O(1) extra space. Intuition In brute force, we iterate over the left and right parts again and again just to find the highest bar size up to that index. But, this could be stored. Voila, dynamic programming. So we may pre-compute highest bar on left and right of every bar in O(n) time. Then use these pre-computed values to find the amount of water in every array element. The concept is illustrated as shown: Steps - Add min(max_left[i], max_right[i]) − height[i] to answer. Complexity Analysis Time complexity: O(n). We store the maximum heights upto a point using 2 iterations of O(n) each. We finally update answer using the stored values in O(n). Auxiliary space complexity: O(n) extra space. Additional space for left_max and right_max arrays than in Approach 1.

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 or 2 stairs at a time. Count the number of ways, the person can reach the top. This is an interesting problem because there are several ways of how it may be solved that illustrate different programming paradigms.

You are given an n x n 2D matrix (representing an image). Rotate the matrix by 90 degrees (clockwise). Note You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example #1 Given input matrix: [1, 2, 3], [4, 5, 6], [7, 8, 9], ] Rotate the input matrix in-place such that it becomes: [7, 4, 1], [8, 5, 2], [9, 6, 3], ] Example #2 Given input matrix: [5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16], ] Rotate the input matrix in-place such that it becomes: [15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11], ] We would need to do two reflections of the matrix: Or we also could Furthermore, you can reflect diagonally top-left/bottom-right and reflect horizontally. A common question is how do you even figure out what kind of reflections to do? Simply rip a square piece of paper, write a random word on it so you know its rotation. Then, flip the square piece of paper around until you figure out how to come to the solution. Here is an example of how first line may be rotated using diagonal top-right/bottom-left rotation along with horizontal rotation. Let's say we have a string at the top of the matrix: A B C • • • • • • Let's do top-right/bottom-left diagonal reflection: A B C / / • / • • And now let's do horizontal reflection: A → → B → → C → → The string has been rotated to 90 degree: • • A • • B • • C

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Example #1 Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right Example #2 Input: m = 7, n = 3 Output: 28 First thought that might came to mind is that we need to build a decision tree where D means moving down and R means moving right. For example in case of boars width = 3 and height = 2 we will have the following decision tree: START / \ D R / / \ R D R / / \ R R D END END END We can see three unique branches here that is the answer to our problem. Time Complexity: O(2 ^ n) - roughly in worst case with square board of size n. Auxiliary Space Complexity: O(m + n) - since we need to store current path with positions. Let's treat BOARD[i][j] as our sub-problem. Since we have restriction of moving only to the right and down we might say that number of unique paths to the current cell is a sum of numbers of unique paths to the cell above the current one and to the cell to the left of current one. BOARD[i][j] = BOARD[i - 1][j] + BOARD[i][j - 1]; // since we can only move down or right. Base cases are: BOARD[0][any] = 1; // only one way to reach any top slot. BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column. For the board 3 x 2 our dynamic programming matrix will look like: Each cell contains the number of unique paths to it. We need the bottom right one with number 3. Time Complexity: O(m * n) - since we're going through each cell of the DP matrix. Auxiliary Space Complexity: O(m * n) - since we need to have DP matrix. This question is actually another form of Pascal Triangle. The corner of this rectangle is at m + n - 2 line, and at min(m, n) - 1 position of the Pascal's Triangle.