Algo Cheat Sheet by lavas

Takes a root node and sets the distance to 0 and puts it in a queue(­FIFO), while every other node is set to infinity. Iterat­ively explores the neighbors of the dequeued node and adds them to queue and updates their distance. O(V+E)

In any DFS of a graph G = (V, E), for any two vertices u and v, exactly one of the followings holds:
1. The interval [d[u], f[u]] and [d[v], f[v]] are entirely disjoint
2. The interval [d[u], f[u]] is contained entirely within the interval [d[v], f[v]], and u is a descendant of v in the depth-­first tree
3. The interval [d[v], f[v]] is contained entirely within the interval [d[u], f[u]], and v is a descendant of u in the depth-­first tree

DFS can be used to classify edges of G:
1. Tree edges: edges in the depth-­first forest G . Edge (u, v) is a tree edge if v was first discovered by exploring edge (u, v).
2. Back edges: edges (u, v) connecting a vertex u to an ancestor v in a depth-­first tree. Self-loops are considered to be back edges.
3. Forward edges: nontree edges (u, v) connecting a vertex u to a descendant v in a depth-­first tree.
4. Cross edges: all other edges.

Modify DFS so that each edge (u, v) can be classified by the color of the vertex v that is reachable when the edge is first explored:
1. WHITE indicates a tree edge
2. GRAY indicates a back edge
3. BLACK indicates a forward or cross edges

1. Call DFS(G) to compute finishing time f[v] for each vertex
2. As each vertex is finished, insert it onto the front of linked list
3. Return the linked list of vertices
O(V+E)

Greedy algorithms are typically used to solve optimi­zation problems & normally consist of
Set of candidates
Set of candidates that have already been used
Function that checks whether a particular set of candidates provides a solution to the problem
Function that checks if a set of candidates is feasible
Selection function indicating at any time which is the most promising candidate not yet used
Objective function giving the value of a solution; this is the function we are trying to optimize

Similar to divide­-an­d-c­onquer, it breaks problems down into smaller problems that are solved recurs­ively.
In contrast, DP is applicable when the sub-pr­oblems are not indepe­ndent, i.e. when sub-pr­oblems share sub-su­b-p­rob­lems. It solves every sub-su­b-p­roblem just once and save the results in a table to avoid duplicated comput­ation.

Optimal sub-st­ructure (principle of optima­lity): for the global problem to be solved optimally, each sub-pr­oblem should be solved optimally. This is often violated due to sub-pr­oblem overlaps. Often by being “less optimal” on one problem, we may make a big savings on another sub-pr­oblem.
Small number of sub-pr­oblems: Many NP-hard problems can be formulated as DP problems, but these formul­ations are not efficient, because the number of sub-pr­oblems is expone­ntially large. Ideally, the number of sub-pr­oblems should be at most a polynomial number

Decision variables - mathem­atical symbols repres­enting levels of activity of a firm.
Objective function - a linear mathem­atical relati­onship describing an objective of the firm, in terms of decision variables - this function is to be maximized or minimized.
Constr­aints – requir­ements or restri­ctions placed on the firm by the operating enviro­nment, stated in linear relati­onships of the decision variables.
Parameters - numerical coeffi­cients and constants used in the objective function and constr­aints.

Divide the n elements of input array into n/5 groups of 5 elements each and at most one group made up of the remaining (n mod 5) elements.
Find the median of each group by insertion sort & take its middle element (smaller of 2 if even number input).
Use Select recurs­ively to find the median x of the n/5 medians found in step 2.
Partition the input array around the median­-of­-me­dians x using a modified Partition. Let k be the number of elements on the low side and n-k on the high side.
Use Select recurs­ively to find the ith smallest element on the low side if i  k , or the (i-k)th smallest element on the high side if i > k

P is a complexity class that represents the set of all decision problems that can be solved in polynomial time. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.
Given a graph connected G, can its vertices be coloured using two colours so that no edge is monoch­rom­atic?
Algorithm: start with an arbitrary vertex, color it red and all of its neighbours blue and continue. Stop when you run out of vertices or you are forced to make an edge have both of its endpoints be the same color.

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "­yes­" have proofs that can be verified in polynomial time.
This means that if someone gives us an instance of the problem and a certif­icate to the answer being yes, we can check that it is correct in polynomial time.

NP-Com­plete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.

Intuit­ively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X, if there is a polynomial time algorithm f to transform instances y of Y to instances x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes.
It can be shown that every NP problem can be reduced to 3-SAT. The proof of this is technical and requires use of the technical definition of NP (based on non-de­ter­min­istic Turing machines). This is known as Cook's theorem.
What makes NP-com­plete problems important is that if a determ­inistic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time.

Intuit­ively, these are the problems that are at least as hard as the NP-com­plete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.
The precise definition here is that a problem X is NP-hard, if there is an NP-com­plete problem Y, such that Y is reducible to X in polynomial time.
But since any NP-com­plete problem can be reduced to any other NP-com­plete problem in polynomial time, all NP-com­plete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.
The halting problem is an NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-com­plete problem can be reduced to this one. As another example, any NP-com­plete problem is NP-hard.