Reducing max flow to bipartite matching? There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item to be matched, then add appropriate edges.

There's certainly a way to reduce maximum flow to maximum bipartite matching in polynomial time, since both of them can be each individually be solved in polynomial time. However, is there a "nice" polynomial-time reduction from max-flow (in general graphs) to maximum bipartite matching?

Strangely enough, no such reduction is known. However, in a recent paper, Madry (FOCS 2013), showed how to reduce maximum flow in unit-capacity graphs to (logarithmically many instances of) maximum $b$-matching in bipartite graphs.

In case you are unfamiliar with the maximum $b$-matching problem, this is a generalization of the matching, defined as follows: the input is a graph (in our case, a bipartite graph), $G=(V,E)$, and a set of integral demands for each vertex, with the demand of vertex $v$ denoted by $b_v$. The goal is to find a largest possible set of edges $S$ such that no vertex $v$ has more than $b_v$ edges in $S$ incident on $v$. It is a simple exercise to generalize the reduction from bipartite matching to maximum flows and show a similar reduction from bipartite $b$-matching to maximum flows. (One of) the surprising result(s) of Madry's paper is that in some sense these problems are equivalent, giving a simple reduction which reduces maximum flow in unit-capacity graphs (generally, graphs where the sum of capacities, $|u|_1$ is linear in the number of edges, $m$) to a $b$-matching problem in a graph with $O(m)$ nodes, vertices and sum of demands.

If you're interested in details, see section 3, up to Theorem 3.1 and section 4 (and proof of correctness in Appendix C) of the ArXiv version of Madry's paper, here. If the terminology is not self-evident, see section 2.5 for a recap concerning the $b$-matching problem, and bear in mind that $u_e$ is the capacity of edge $e$ in the original max flow instance.

So here is a try at answering your question:

Konig’s theorem on bipartite matchings proved and consequently reduced using the Max-Flow Min-Cut theorem.
Konig’s theorem states the following. If G a bipartite graph, then max{|M| : M is a matching } = min{|C| : C is a cover}. Proof. The part max{|M|} ≤ {|C|} is trivial. Let P and Q be the bipartition classes of G. We add two vertices, r and s to G, and arcs rp for every $p\in P$ and qs for every $q \in Q$, and direct edge pq from $p\in P$ to $q\in Q$. This is a digraph $G_{∗}$. We define capacities u(rp) = 1, u(pq) = $\infty$, u(qs) = 1. Let x be a feasible integral flow x, then x(e) = 0 or 1, so we can define M = {$e \in E$ : x(e) = 1}. M is a matching with |M| = $f_{x}$. Next, a matching M in G gives rise to a feasible integral flow x in $G_{∗}$ with flow value $f_{x}$ = |M| as follows. Define x(pq) = 1 if $pq \in M$, x(rp) = 1 if p is incident to an edge in M, x(qs) = 1 if q is incident to an edge in M, in all other cases x(e) = 0. Thus a maximum size matching M in G corresponds to a maximum flow in $G_{∗}$, whose size equals that of a minimum cut by the Max-Flow Min-Cut theorem. Consider a minimum r − s cut δ(R). It has finite capacity, so it contains no arc pq. Then every edge of G is incident with an element of C = (P\R) $\cup (Q \cap R)$, that is, C is a cover. Moreover, u(C) = |P \R|+$|Q \cap R|$ and so C is a cover of size |M|.

I mean this is everything in my opinion that you asked in the question and this is my potential answer :).


What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size? In a given cellular automaton, such as Conway's Game of Life, is there anything known about how many Garden of Eden patterns there are by pattern size? Say, pattern size is n x n, what's the likelihood that a random pattern is a GoE as n increases?
Also, by the Garden of Eden-theorem, only cellular automata which are non-injective, that is, for which a given pattern may have more than one predecessor, contain Gardens of Eden.

Is it then in general impossible to see whether a given cellular automaton pattern at some time-step is derived from a GoE (since there could also have been a non-GoE ancestor leading to the same state)? That is, does the evolution of the CA 'wash out' the information that it is derived from a GoE? (I hope it's sufficiently clear what I mean.)

Furthermore, is there a relation between GoE-patterns and uncomputability/undecidability? It seems to me that if you consider the CA to be implementing some computation, then the GoEs are 'outputs that could never be produced', at least heuristically, but a brief Google search led nowhere. Perhaps asked another way, is there a relation between the existence of GoEs and the universality of a CA? I know Life is both universal and has GoEs, but I don't know about the general case. Any pointers would be much appreciated.

Having done some additional reading, I think I can strike out the third question: since reversible cellular automata that are computationally universal exist (according to wiki), there doesn't seem to be any connection between computational universality and GoEs. Now, what about universal constructors? Are there reversible universal constructors? Von Neumann's original rule happens not to be reversible, and in fact, has GoEs, but again, this need not say much.
The wikipedia page above mentions a way to emulate d dimensional irreversible CAs within d + 1 dimensional reversible ones, which readily establishes the computational universality of the latter, but I'm not sure if this holds as well for universal construction: the emulated constructor would only construct patterns on a d-dimensional sub-grid of the automaton (?).

as said by vzn, any pattern containing a Garden of Eden pattern is itself a Garden of Eden Pattern, the probability that a random nxn pattern is actually GoE goes to 1 as n goes to infinity (in the case of a non-surjective CA of course, otherwise it's 0). More precisely, it is lower bounded by $1 - \alpha^{n²}$ for some $0<\alpha<1$.
Indeed, consider a fixed GoE pattern P of size $k\times k$, then the probability for a random pattern of size $n\times n$ to be a GoE is at least $1 - (\frac{1}{q^{k^2}})^{(\frac{n}{k})^2}$, where $q$ is the number of states of the CA.
you can generate all the possible pre-image of a given pattern in finite time and you can also test whether a pattern is a GoE so your problem is clearly decidable. It's polynomial-time decidable in 1D and NP-hard in 2D.

in the 1D case, a CA can be seen as a finite state transducer. So the language $L_{GoE}$ of all GoE patterns is a regular language because it is the complement of $T(Q^\ast)$ (where $T$ is the transducer and $Q$ the set of states of the CA) which is itself a regular language as the image of a regular language by a transducer. Then $T(L_{GoE})$ is also regular and its the set you asked.
in the 2D case, I think we can show that it is NP-hard using the classical simulation of Turing machines by Wang tiles. The rough idea is the following. Consider any NP-complete problem $L$ and take a Turing machine $T$ which is a polynomial time verifier for the problem. Then construct a CA that basically checks that the input, if written in some special alphabet $A$, encodes a successful computation $T(x,y)$ of $T$ working on input $x$ and witness $y$. If so erases everything with a special state $a\not\in A$, but keep the input x. If some error is detected produce some special state $b\not\in A$. Finally, the CA does nothing on states which are not in $A$. Now consider a pattern formed by an input $x$ surrounded by many $a$. The pattern as always itself as a preimage, but it as a GoE preimage if and only if there is some $y$ such that $T(x,y)$ says "yes", i.e. iff $x\in L$. CQFD
At the time of writing I don't see how to prove that the problem is NP

as pointed-out Turing-universality is still possible without GoE patterns (in reversible CA for instance). But intrinsic universality requires GoE patterns. This comes from the fact that, first, a surjective CA only admits surjective CA as subautomata, and, second, grouping and iterating a CA doesn't change its surjectivity.

Question 1:

I'd say that it's a function $F(k,r)$ where $k$ is the width of the neighbourhood the rules take into account (say $k=3$ in Conway) and $r$ a measure of the 'injectivity' of the rules (the probability 2 distinct configurations produce 2 distinct new states).
In particular, as a first approximation, I would expect $F \propto k^2, F \propto r$.


What is the optimal way to find unique combinations of N sets of integers This is a simplification of a real world problem and only a small piece at that.

Example sets are

----------------------       ------------------------------------
| Set1 | Set2 | Set3 |  OR   | Set1 | Set2 | Set3 | Set4 | Set5 |
|--------------------|       |--------------------|--------------
| 1    | 10   | 40   |       | 1    | 1    | 1    | 1    | 1    |
| 2    | 12   | 45   |       | 2    | 2    | 2    | 2    | 2    |
| 3    | 13   | 51   |       | 3    | 3    | 3    | 3    | 3    |
| 4    | 20   | 61   |       | 4    | 4    | 4    | 4    | 4    |
| 5    | 25   | 76   |       | 5    | 5    | 5    | 5    | 5    |
|      | 31   | 78   |       ------------------------------------
|      |      | 81   |
----------------------

Real world constraints are

Up to 12 sets
N numbers in each set
Only care about distinct combinations - (112), (211) and (121) are considered the same.

Example with desired result

----------------------
| Set1 | Set2 | Set3 |
|---------------------
| 1    | 1    | 1    |
| 2    | 2    | 2    |
| 3    | 3    | 3    |
----------------------
Results: [1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]

Generally real world examples tend to either be like the first example where there are a variable number in each set and they are different in each set, or like the second where there are the same items in each set. However there are no hard and fast rules.

A real world example of the latter is 10 sets with 40 values in each. To naively iterate that example would be $1x10^{16}$ iterations.

Are there any optimal algorithms I can implement to find distinct combinations? I am hoping that there is something clever that can be done when there are the same items in different sets, somehow excluding them once certain conditions are met, but i have failed to think of or find one.

This may be wrong
I don't follow the multiple set of the set input part of question

Have a loop for each N

Assume N = 3
L is length of array A

for(i = 0; i < L-2; i++)
    for(j = i + 1; j < L-1; j++)
        for(k = j + 1; k < L; k++)
            A[i], A[j], A[k]

I write poker software and this matches the number of combinations


Sums of Landau terms revisited I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success.

Now, over here our recurrence guru JeffE does essentially this:

$\qquad \displaystyle \sum_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H_n)$

While the end result is correct, I think this is wrong. Why? If we add in all the existence of constants implied (only the upper bound), we have

$\qquad \displaystyle \sum_{i=1}^n c_i \cdot \frac{1}{i} \leq c \cdot H_n$.

Now how do we compute $c$ from $c_1, \dots, c_n$? The answer is, I believe, that we can not: $c$ has to bound for all $n$ but we get more $c_i$ as $n$ grows. We don't know anything about them; $c_i$ may very well depend on $i$, so we can not assume a bound: a finite $c$ may not exist.

In addition, there is this subtle issue of which variable goes to infinity on the left-hand side -- $i$ or $n$? Both? If $n$ (for the sake of compatibility), what is the meaning of $\Theta(1/i)$, knowing that $1 \leq i \leq n$? Does it not only mean $\Theta(1)$? If so, we can't bound the sum better than $\Theta(n)$.

So, where does that leave us? It it a blatant mistake? A subtle one? Or is it just the usual abuse of notation and we should not look at $=$ signs like this one out of context? Can we formulate a (rigorously) correct rule to evalutate (certain) sums of Landau terms?

I think that the main question is: what is $i$? If we consider it constant (as it is inside the scope of the sum) we can easily build counterexamples. If it is not constant, I have no idea how to read it.

Looks right to me in the following convention:
$S_n = \sum_{k=1}^{n} \Theta(1/k)$ is convenient notation for

There is an $f(x) \in \Theta(1/x)$ (as $x \to \infty$) such that
$S_n = \sum_{k=1}^{n} f(k)$.

Thus the $c_i$ (or with the notation in this answer $c_k$) you get, are not really dependent on $k$.
Under this interpretation, it is indeed true that $S_n = \Theta(H_n)$.
In fact, in Jeff's answer, he shows that $T(k+1) = f(k) + T(k)$ where $f \in \Theta(1/k)$, so it is consistent with the above interpretation.
The confusion seems to be arising from mentally "unrolling" the $\sum$ and presuming different functions for each occurrence of $\Theta$...

If each $c_i$ is a constant, then there is some $c_{max}$ such that $\forall c_i: c_i\leq c_{max}$. So clearly $$\sum c_i f(i) \leq \sum c_{max} f(i) = c_{max} \sum f(i) = O\left(\sum f(i)\right)$$ Same idea for little o.

I think the problem here is that $1/i\not=\Theta(1)$. It's $o(1/n)$ (since there is no $\epsilon$ such that $\forall i: 1/i>\epsilon$), so the overall sum will be $no(1/n)=o(1)$.  And each term is $O(1)$, meaning the overall sum is $O(n)$. So no tight bounds can be found from this method.

I think your questions are:

Is bounding $\sum_i^n f(i)$ by doing the little o of each term and the big o of each term then multiplying by $n$ acceptable? (Answer: Yes)
Is there a better method? (Answer: Not that I know of.)

Hopefully someone else can answer #2 more clearly.

EDIT: Looking over your question again, I think you are asking

  $\sum_i^n \Theta(f(n)) = \Theta(nf(n))$ ?

To which the answer is yes. In this case though, each term is not $\Theta$ of anything, so that approach falls apart.

EDIT 2: You say "consider $c_i=i$, then there is no $c_{max}$". Unequivocally true. If you say that $c_i$ is a non-constant function of $i$, then it is, by definition, non-constant.

Note that if you define it this way, then $c_i i$ is not $\Theta(i)$, it's $\Theta(i^2)$. Indeed, if you define "constant" to mean "any function of $i$", then any two functions of $i$ differ by a "constant"!

Perhaps this is an easier way to think of it: we have the sequence $1,\frac{1}{2},\dots,\frac{1}{n}$. What's the smallest term in this sequence? Well, it will depend on $n$. So we can't consider the terms as constant.

(Computer scientists are often more familiar with big-O, so it might be more intuitive to ask if $1,\dots,n$ has a constant largest term.)

To provide your proof: let $f(i_{min})$ be the smallest value of $f(i)$ in the range $1,\dots,n$. Then $$\sum_i^n f(i) \geq \sum_i^n f(i_{min}) = n f(i_{min}) = n o(f(n))$$

An analogous proof can be made for the upper bound.

Lastly, you write that $H_n = o(n)$ and as proof give that $H_n = \Theta(\log n)$. This is in fact a counter-proof: if $H_n$ is "bigger" than $n$, then it can't be "smaller" than $\log n$, which is what's required for it to be $\Theta(\log n)$. So it can't be $o(n)$.


Longest possible path from root to a leaf of a red black tree For the worst case of a red-black tree, what would a tree with 10 nodes look like?Since there can not be 2 consecutive red nodes and there is rotation is it safe to say that it balances out the trees leveling it I tried this attempt at creating a tree with 10 nodes:

As you can read as "Properties" in the "Wiki Red-Black Tree", "the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.".

For a Red-Black Tree having 'N' nodes, the mean length path is 'ln(N + 1) + 1' (for 'N=10' 'Lmean = 2.397 + 1 >> 4').

Note: `ln(X) = neperian logarithm'.

So the Longest balanced-path from root to leaf is shorter than the double of the mean length '< 2 * ln(N + 1) + 1'. (for 'N= 10' longest < 8).


Efficiently representing a set of sets (The question is an extension of this unanswered question on stackoverflow)

If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in a DAG instead of a tree that is even more compact.

However, if we have a set of sets (i.e. the order does not matter), there are a lot of possible tries that represent the same set of elements.
An example can be found in the stackoverflow question I linked above.

Edit: For example, assume that we are given the following sets of integers.

{1,2,3,4,5}
{1,2,6,7}
{1,2,4,7}
{1,3,5,7}

Two possible representations are shown below (trie on the left, DAG on the right)

My questions are:

  How hard is the problem of finding an optimal (i.e minimal) such trie?
  Are there any fast algorithms for solving this problem?
  If not, are there any fast algorithms that find "good" tries?
  What about the DAG case?

In the scenario I have in mind there is an additional constraint that no set is a subset of another set.

Any link/paper that is even slightly relevant to any of the questions is helpful.

I suggest you start by looking at BDDs and ZDDs.

Your problem is similar to the problem of finding an optimal BDD.

I'll explain.  Suppose we have sets $S_1,\dots,S_k$ over a universe $U$ containing $n$ items (so $S_i \subseteq U$).  A BDD is a finite-state automaton (a DAG) for recognizing the language of all of the allowed sets, where each set is presented to the finite-state automaton as the $n$-bit string that is the characteristic function of that set.  In other words, given a total order on $U$, each set $S \subseteq U$ corresponds to a binary string $[S] \in \{0,1\}^n$: $[S]_i=1$ if $S$ includes the $i$ element of $U$, otherwise not.  (This order is known in the BDD literature as a "variable ordering".)  Then define the language $L$ by $L=\{[S_1],[S_2],\dots,[S_k]\}$.  A BDD is a finite-state automaton that recognizes the language $L$.

Notice that you have the freedom of what "variable ordering" to choose.  The choice of the variable ordering determines how each set is represented as a binary function, which can affect the size of the BDD.  It is well-known that the problem of choosing the optimal variable ordering (the one that leads to the smallest BDD) is NP-hard.  Nonetheless, there are various heuristics for trying to find a good variable ordering, and in real-world problems, they often work reasonably well.

So, your problem can be framed as the problem of choosing the optimal variable ordering to represent your sets as a BDD.

ZDDs are a variant of BDDs that are better in some circumstances.  ZDDs are especially oriented at representing a set of sets, so they might be particularly helpful for your needs.  ZDDs are especially handy if you need to represent a bunch of sets that are related to each other in some way; ZDDs provide a compact and efficient encoding for that situation.

there is a close connection of the complexity of finding optimal DAGs as "compressions" of sets of sets (hypergraphs) to the P/Poly?=NP question sketched out here. basically/roughly speaking circuits are closely connected to DAGs and if one can find small circuits for sets-of-sets (hypergraphs) built out of NP complete patterns, one could "compress" those patterns into P-size computations. another close angle is that this is also related to hypergraph decompositions (via DAGs). more discussion in chat for anyone interested.


What should I do with a bunch of 16-17 year olds to get them interested in computer science? I'm going to be involved with a sort of 'open day' at my university in a few weeks. As part of this time, I (along with a coworker) am being given a whole bunch of high-school level students for two hours, as well as a computer lab big enough to contain them all, and I have to do some kind of activity or set of activities with them to encourage them to do computer science (at my university, ideally, but in general also). I am at an absolute loss as to what to do here, and welcome any and all suggestions.

You can have them draw pictures using context-free grammar. context free art This also works for people who never programmed before and scales to experienced programmers. The basic language is easy enough to explain in maybe half an hour.
Learning something about geometry using Turtle graphics should be nice too. Logo was designed for children, so highschool students should have no problem. There are nice videos about children using Logo on youtube
If you can get your hands on some MindStorms robots, programming them is lots of fun.
There are a variety of programming games in which you program robots to fight each other, or assembly programs that try to overwrite each other in a virtual machine. Wikipedia on the topic, related stackoverflow question
You can also think about some kind of hardware project. Making a microcontroller blink a LED depending on the number of unread e-mails in your inbox for example.
Have them implement different maze generation algorithms, try to come up with criteria that make mazes "difficult for humans". If time permits extend the algorithms to include not only corridors but also rooms.
Buy a couple of Arduinos and LEDs. Let them program the blinkenlights.

Do anything with facebook, they love it. Maybe this is to difficult for beginners, but u clould let them draw connextions graphs, that show how their profiles are connected to each other. I would recommend Javascript as programming language.


Best case analysis for Shell sort The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my own derivation or one copied from an authoritative source.

I have elaborated upon the same below. Could you let me know if the reasoning is right here?

The least number of comparisons occur when the data is completely sorted.
For a particular value of the increment, say, $h_i$, each of the $h_i$ sub-sequences require at most one less comparison than the number of elements in the sub-sequence(as insertion sort is used) which is,${N \over h_i} - 1$ ,where N is the total number of data items.
For the given data in this situation $h_i \times \left (N \over h_i - 1 \right ) = N - h_i$ number of comparisons are needed as there are $h_i$ sub-sequences.
If the increment sequence selected is has $k$ increments(such that $h_k = 1$), the total number of comparisons required would be $C(N) \ge (N - h_i) + (N - h_2) + ... + (N - h_k) = kN - \sum h_i = O(N)$

The best case for Shell sort is when the array is already sorted.
In that case the inner loop does not need to any work and a simple comparison will be sufficient to skip the inner sort loop.

A best case of $Θ(N)$ is reached by using a constant number of increments.
But the problem is that the best value for the gapping depends on the input. Therefore you cannot choose a single best value for the gap and must suffer a $log^2(N)$ delay due to repeated compares.

So you are almost correct. Obviously there is no way to compare fewer than N-1 elements before we can conclude that the array is already sorted, so $Θ(N\space log^2(N) )$ it is.

Note that this best case is for randomized Shell sort which is subtly different from the original.

See: https://arxiv.org/pdf/0909.1037.pdf

All this means that Shell sort is not a particularly good algorithm for a (nearly) sorted array. The gapping introduces redundant compares whereas other sorting algorithms only have to go over the array once in the best case.
When the array is random, the gapping works in your favor, and these other algorithms that perform so wonderfully on a (nearly) sorted array perform at a dismal $O(N^2)$


Empty intersection of longest path in connected graph Do all longest paths share a common point? (Gallai 1966)

A few years later, Walther  produced a counterexample on 25 vertices (a). The simplest counterexample was found by both Walther and Zamfirescu independently and has 12 vertices (b).

I found this examples in numerous study, but i couldn't find a vertex that does not appear in all longest paths.

Could you explain how should i see these graphs? Where are paths which intersection are empty?

You need not find a vertex that does not appear in all longest paths (in fact you can't). This is neither sufficient nor necessary. It is sufficient to prove that for each vertex $v$, there exists a longest path that does not contain $v$.

Easy to see the length of the longest path is 10. For convenience, let's encode the vertices as follows.

     1
     2
    3 4
   5   6
  7 8 9 10
11        12

Then for vertices 1,2,7,11,10,12, for example, 1, there is a longest path 11-7-8-4-6-5-3-9-10-12 that does not contain 1.

For vertices 3,4,5,6,8,9, for example, 3, there is a longest path 1-2-4-6-5-7-8-9-10-12 that does not contain 3.

It is easy if you consider the property exhibited in the graph that says for each vertex there is a longest path now say for the labelled vertex v_1  there is a
 longest path P_1 and continue for all vertices in this fashion you will get collection of longest paths whose intersection will be empty.


Regular expression with out the substring bab or abb? I'm having a problem coming up with a regular expression for a language L = {a,b} with out the substring bab or abb?
I can come up with the one for just one substring, like

a*(b* aaa* )* b* a* to eliminates the bab and b*(a+ab)* to eliminates the abb substrings.

But putting them together is a huge animal :(

There are a couple tricks required to get this right.

First, this particular problem is a lot easier if you approach it backwards, starting at the end of the sting.

(abb,bab) is an exhaustive list of all the cases in which b is preceded by 2 different letters.  If you want to exclude these cases, you just have to ensure that b is preceded by less than 2 letters, or a double letter.

Second, notice that these rules imply that if there are 2 bs in a row, then they must be preceded by b all the way to the start of the string.  Otherwise the second-to-first b will be preceded by ab.

Working from the end, then, we can have a free mixture of a and aab, and then there are only a few ways to get to the beginning of the string when we encounter a b outside of that pattern:

(ab|b*)(aab|a)*

Thanks for the help, i came up with a solution, although I'm not 100% sure:

0*(1+000*)0*+(1*0*)

Here can use jflap to test a few strings.


What is the Difference Between Many-to-Many (M:M) Threading and Hybrid (M:N) Threading? I have been researching threading and come across several websites which all say contradicting statements about which and how many thread models exist. Some websites say there are only three: 1:1, M:1 and M:M, while others say the three are 1:1, M:1 and hybrid (M:N). Still others say there are four types, including 2-level threading?

Google and stack exchange haven't been able to come up with a clear answer as of yet. I was hoping for someone to shed some light on this situation, namely the difference (i.e pros & cons) between M:M, M:N and two-level threading types.

Go to a website selling computers (or phones). Check how many cores the computers have, and whether they support hyper threading. So there you get the number how many threads can actually run at the same time.

On the other side, your software can use a single active thread, or 100 active threads. Some software can actually make use of many threads, other software can't. Your computer however can run more than one software at the same time, so there will be more active threads.

So everything is M:N. M = 1 or N = 1 is possible but rare. If M < N then some cores are unused and might as well not be there. If M > N then at any point in time, at most N of the M threads are running. And M changes all the time.


How is Dynamic programming different from Brute force I was reading up on Dynamic Programming when I came across the following quote

  A dynamic programming algorithm will examine all possible ways to
  solve the problem and will pick the best solution. Therefore, we can
  roughly think of dynamic programming as an intelligent, brute-force
  method that enables us to go through all possible solutions to pick
  the best one. If the scope of the problem is such that going through
  all possible solutions is possible and fast enough, dynamic
  programming guarantees finding the optimal solution

The following example was given

  For example, let's say that you have to get from point A to point B as
  fast as possible, in a given city, during rush hour. A dynamic
  programming algorithm will look into the entire traffic report,
  looking into all possible combinations of roads you might take, and
  will only then tell you which way is the fastest. Of course, you might
  have to wait for a while until the algorithm finishes, and only then
  can you start driving. The path you will take will be the fastest one
  (assuming that nothing changed in the external environment)

Brute Force is trying every possible solution before deciding on the best solution .

How is Dynamic Programming different from Brute Force if it also goes through all possible solutions before picking the best one , the only difference i see is that Dynamic Programming takes into account the additional factors ( traffic conditions in this case).

Am  i correct to say that Dynamic Programming is a subset of Brute Force method ??

A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution.

This statement is just plain wrong.

Dynamic programming recurrences do (often) consider all possible ways to split the given problem instance into smaller instances according to some scheme. However, it will not combine all solutions to all partial problems with each other and pick the best -- it combines only optimal partial solutions (and picks the best out of those).

The fact that this yield an optimal solution for the original problem is not trivial and does, in fact, only hold for some problems. Namely those that fulfill the Bellman principle of optimality (one of the most fishy, misunderstood "definitions" that are regularly quoted). See here for some more thoughts on that.

As a concrete example, consider the Bellman-Ford algorithm on a complete graph $K_n$ with unit weights: it only ever considers paths of length one and two (i.e. $\Theta(n^2)$ many) because those using one edge are all optimal. But there are infinitely many solutions if you don't bound the maximum number of edges allowed, and still $\gg (n-1)!$ many if you allow every node to be used only once. So clearly, Bellman-Ford -- a dynamic programming algorithm -- does not perform a brute-force search.

This is straightforward.  Dynamic programming is a "search strategy" which uses additional factors to narrow down a search.  If there is no solution in the search space, dynamic programming will (typically) do a search through every element of the search space.  But that does not mean that it is a brute force search.


Translating between coordinate systems Let's say I needed to render an image at 1920 x 1080 and also at 1024 x 768. Instead of drawing two separate images, it might make sense to draw the scene in a common "virtual" coordinate system and then translate that to the appropriate output coordinate system.

Is there a name for this problem? I'm having a hard time figuring out what to start searching for.

I'll try to answer my own question. The solution is an application of matrix transformations.

This lecture tries to explain some of the maths.

https://www.khanacademy.org/math/precalculus/precalc-matrices/matrices-as-transformations/v/transforming-position-vector

I think what I need to do is apply both a translation and scale matrix to each vertex in the "virtual" coordinate system to get them into the "physical" coordinate system.

Still trying to get my head around exactly how to do that.


Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations? I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example:

Assume the following regular expression:

((a(b+))+(a|c))|a|c

Why is it that this accepts the strings:

a
c
abba
abbabbba
abbabbc

etc

But when I flip it around and use the regular expression

a|c|((a(b+))+(a|c))

I can now only ever get the following strings when I check it with a RegExp tester:

a
c

I know it is to do with the order of precedence but I don't understand why, please could somebody enlighten me?

Both the patterns match your given strings and are equivalent. The problem here is that your tester does not try to match the string against the pattern, but tries to find matching substrings, and it does that by trying each of the ORed patterns in order. Hence the second pattern stops when $a$ is matched, but the first one matches the whole string.

To see the difference Look at the below code, written in Java:

public static void main(String[] args) {
    test("((a(b+))+(a|c))|a|c", "abbabbc");
    test("a|c|((a(b+))+(a|c))", "abbabbc");
}

private static void test(String pattern, String str) {
    System.out.println(str.matches(pattern));
    Matcher matcher = Pattern.compile(pattern).matcher(str);
    while(matcher.find())
        System.out.println(str.substring(matcher.start(), matcher.end()));
}

The output is

true
abbabbc
true
a
a
c

which shows that both patterns do match $abbabbc$. They are only different in eyes of a matching-substrings-finder program.

You can't write 3 ORs.

Example:

A or B or C => it will compare A or B and ignore C
((a(b+))+(a|c))|a|c the last "|c" ignored. The proof, does it accept "abcc" ?

likewise a|c|((a(b+))+(a|c))  the "|((a(b+))+(a|c))" ignored and only a|c left.

Good Luck.


NP-hard proof with reduction from two known NP-hard problems As I understand, to show that a certain problem P is NP-hard we can reduce a known NP-hard problem, Q, to problem in P in polynomial time. To show that the problem P is NP-hard in strong sense, we can reduce a know NP-hard problem Q to problem P in pseudo polynomial time.
Is it possible to show that a certain problem P is NP-hard by reducing two known NP-hard problems Q and Q' to a problem in P?

If you can reduce one NP-hard problem to a problem $L$, then $L$ is NP-hard. If you can reduce a second NP-hard problem to $L$, then so what? You already know that $L$ is NP-hard. How could reducing more problems to $L$ make $L$ easier (e.g., not NP-hard)?

It's like saying, "If I have one million dollars, I'm rich. If I have two million dollars, am I still rich?"

A few definitions: a pseudo-polynomial problem is a problem which is polynomial on some parameter but that parameter itself makes the problem NP-complete. For example, unary subset sum is polynomial but the problem size is exponential.

If a problem that is NP-hard can be reduced to a polynomial problem in polynomial time, it would mean that the problem has polynomial complexity P.

To reduce a problem to an NP-hard problem by a polynomial time reduction means that the problem is NP hard.

The Cook-Levin theorem shows that all NP problems can be reduced in polynomial time to a problem in NP-complete.

So there is no guarantee that an NP-hard problem can be reduced to an NP-hard problem, but it may.


Which memory holds the copy of the program that is to be executed? I don't know whether it is RAM or cache; I can say that isn't the registers since their memory capacity is very small.

It's the RAM.

But further, in order to enhance speed, the CACHE stores a shadow of the RAM content, so it may hold a copy of the program as well (similarly, the RAM has a copy of the program that previously was stored on the hard-drive).

Eventually, parts of the code goes into the CPU and gets stored in one of its registers (not the general purpose ones, but rather some designated registers you have no access to; just think about them as flip-flops). From that point, the program is being executed, one instruction at a time, by the CPU hardware.

The whole point of the Von Neumann architecture is that programs and data are treated in the same way. So the answer to your question is that the registers, cache, main memory and backing store are used in exactly the same way as they would be for any other data.


Quicksort Partitioning: Hoare vs. Lomuto There are two quicksort partition methods mentioned in Cormen:

(the argument A is the array, and [p, r] is the range, inclusive, to perform the partition on. The returned value is the index to the pivot after the partition.)

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

and:

Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i + 1], A[r] )
return i + 1

Disregarding the method of choosing the pivot, in what situations is one preferable to the other?  I know for instance that Lomuto preforms relatively poorly when there is a high percentage of duplicate values ( i.e. where say more than 2/3rds the array is the same value ), whereas Hoare performs just fine in that situation.

What other special cases make one partition method significant better than the other?

Pedagogical Dimension

Due to its simplicity Lomuto's partitioning method might be easier to implement. There is a nice anecdote in Jon Bentley's Programming Pearl on Sorting:

  “Most discussions of Quicksort use a partitioning scheme based on two approaching indices [...] [i.e. Hoare's]. Although the basic idea of that scheme is straightforward, I have always found the details tricky - I once spent the better part of two days chasing down a bug hiding in a short partitioning loop. A reader of a preliminary draft complained that the standard two-index method is in fact simpler than Lomuto's and sketched some code to make his point; I stopped looking after I found two bugs.”

Performance Dimension

For practical use, ease of implementation might be sacrificed for the sake of efficiency. On a theoretical basis, we can determine the number of element comparisons and swaps to compare performance. Additionally, actual running time will be influenced by other factors, such as caching performance and branch mispredictions.

As shown below, the algorithms behave very similar on random permutations except for the number of swaps. There Lomuto needs thrice as many as Hoare!

Number of Comparisons

Both methods can be implemented using $n-1$ comparisons to partition an array of length $n$. This is essentially optimal, since we need to compare every element to the pivot for deciding where to put it.

Number of Swaps

The number of swaps is random for both algorithms, depending on the elements in the array. If we assume random permutations, i.e. all elements are distinct and every permutation of the elements is equally likely, we can analyze the expected number of swaps.

As only relative order counts, we assume that the elements are the numbers $1,\ldots,n$. That makes the discussion below easier since the rank of an element and its value coincide.

Lomuto's Method

The index variable $j$ scans the whole array and whenever we find an element $A[j]$ smaller than pivot $x$, we do a swap. Among the elements $1,\ldots,n$, exactly $x-1$ ones are smaller than $x$, so we get $x-1$ swaps if the pivot is $x$.

The overall expectation then results by averaging over all pivots. Each value in $\{1,\ldots,n\}$ is equally likely to become pivot (namely with prob. $\frac1n$), so we have

$$
\frac1n \sum_{x=1}^n (x-1) = \frac n2 - \frac12\;.
$$

swaps on average to partition an array of length $n$ with Lomuto's  method.

Hoare's Method

Here, the analysis is slightly more tricky: Even fixing pivot $x$, the number of swaps remains random.

More precisely: The indices $i$ and $j$ run towards each other until they cross, which always happens at $x$ (by correctness of Hoare's partitioning algorithm!). This effectively divides the array into two parts: A left part which is scanned by $i$ and a right part scanned by $j$.

Now, a swap is done exactly for every pair of “misplaced” elements, i.e. a large element (larger than $x$, thus belonging in the right partition) which is currently located in the left part and a small element located in the right part.
Note that this pair forming always works out, i.e. there the number of small elements initially in the right part equals the number of large elements in the left part.

One can show that the number of these pairs is hypergeometrically $\mathrm{Hyp}(n-1,n-x,x-1)$ distributed: For the $n-x$ large elements we randomly draw their positions in the array and have $x-1$ positions in the left part.
Accordingly, the expected number of pairs is $(n-x)(x-1)/(n-1)$ given that the pivot is $x$.

Finally, we average again over all pivot values to obtain the overall expected number of swaps for Hoare's partitioning:

$$
\frac1n \sum_{x=1}^n \frac{(n-x)(x-1)}{n-1} = \frac n6 - \frac13\;.
$$

(A more detailed description can be found in my master's thesis, page 29.)

Memory Access Pattern

Both algorithms use two pointers into the array that scan it sequentially. Therefore both behave almost optimal w.r.t. caching.

Equal Elements and Already Sorted Lists

As already mentioned by Wandering Logic, the performance of the algorithms differs more drastically for lists that are not random permutations.

On an array that is already sorted, Hoare's method never swaps, as there are no misplaced pairs (see above), whereas Lomuto's method still does its roughly $n/2$ swaps!

The presence of equal elements requires special care in Quicksort.
(I stepped into this trap myself; see my master's thesis, page 36, for a “Tale on Premature Optimization”)
Consider as extreme example an array which filled with $0$s. On such an array, Hoare's method performs a swap for every pair of elements - which is the worst case for Hoare's partitioning - but $i$ and $j$ always meet in the middle of the array. Thus, we have optimal partitioning and the total running time remains in $\mathcal O(n\log n)$.

Lomuto's method behaves much more stupidly on the all $0$ array: The comparison A[j] <= x will always be true, so we do a swap for every single element! But even worse: After the loop, we always have $i=n$, so we observe the worst case partitioning, making the overall performance degrade to $\Theta(n^2)$!

Conclusion

Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.

Some comments added to the excellent Sebastian answer.

I'm going to talk about the partition rearrangements algorithm in general and not about its particular use for Quicksort.

Stability

Lomuto's algorithm is semistable: the relative order of the elements not satisfying the predicate is preserved.
Hoare's algorithm is unstable.

Element Access Pattern

Lomuto's algorithm can be used with singly linked list or similar forward-only data structures.
Hoare's algorithm needs bidirectionality.

Number of Comparisons

Lomuto's algorithm can be implemented performing $n-1$ applications of the predicate to partition a sequence of length $n$. (Hoare's too).

But in order to do this we have to sacrifice 2 properties:

The sequence to be partitioned must not be empty.
The algorithm is unable to return the partition point.

If we need any of these 2 properties, we will have no choice but to implement the algorithm by making $n$ comparisons.


Help wrapping my head around a combinatorial optimization problem Here's the problem I'm trying to solve:

I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight requirement, while maximizing the total number of groups I can form.

Knowing a specific name for this class of problem would be a good start. Help formalizing it would be even better. I did this stuff so long ago in school, I need my memory jogged good and hard. Thanks!

Here is a complete MIP (Mixed Integer Programming) model that should do the trick. I just use some random data (weights) with 100 widgets and 50 possible bins. When solved the variable NumUsedBins gives the maximum number of bins and the variable x gives the assignment. The equation 'order' is to make sure we use lower numbered bins first. The strange statement about optcr is to tell the solver to solve to optimality (for very difficult problems you may want to stop at 5% or so).

With 1000 widgets this becomes somewhat difficult to solve to optimality.

The first thing I would do in order to solve this question is simplify it into a smaller problem:
You have the weights and the min-weight requirement. Now try to match 2 weights in order to reach exactly the min-weight. My approach:

Store every number inside a set.
For each number a calculate - ( a - mid_weight ) = b. Then check if the set already has the number b in it.

Now in the second scenario the pairs don't have to exactly match the min-weight.
My approach would be:

Store every number inside a set.
For each number a calculate its optimal partner - ( a - mid_weight ) = b. Then check the closest element matching b inside the set. In C++ you can find both partners (the partner lower to b and higher to b) using std::set::lower_bounds and std::set::higher_bounds.
Sort all the matching pairs according to their waisted weight from lower to higher: a + b - min-weight = wasted-weight. Then always choose the best pair and reevaluate any new pairs that had a or b as partner.

This is only a quick attempt at your problem, i'm not sure if it's optimal. You have to do the general case. For a similar problem look up 3sum (or 4sum). I hoped this helped a little bit at least.


Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2? I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether
$$AB = C$$
and be correct with high probability.

The algorithm  choose a random $r$ n-bit vector and if
$$A(Br) = Cr$$
then outputs YES, otherwise outputs no.

I want to show that it has has one-sided success probability 1/2. For that I want to show that when $AB = C$ then the algorithm is correct with probability 1 and when $AB \neq C$ then the probability of it being correct is at least 1/2.

When $AB = C$ its clear that the algorithm is always correct because:

$$ A(Br) = (AB)r = Cr$$

So, if $AB=C$, then $A(Br)$ is always equal to $Cr$.

The case when $AB \neq C$ is a little trickier. Let $D = AB - C$. When the multiplication are not equal then $D \neq 0$. Let a good $r$ be a vector that discovers the incorrect multiplication (i.e. $D \neq 0$ and $Dr \neq 0$, multiplying by $r$ makes it still zero). let a bad $r$ be a vector that makes us mess up, i.e. conclude the multiplication is correct when is not. In other words, when $D \neq 0$ (i.e. multiplication was done correctly $AB = C$) but when we use $r$ to check this we get the wrong conclusion (i.e. $Dr = 0$, when in fact $D \neq 0$).

The high level idea of the proof is, if we can show that for every bad $r$ there is a good $r$, then half the $r$'s are good so our algorithm is about 1/2 percent of the time correct. This high level idea of the proof makes sense to me, however, what is not clear to me is the precise detail of the inequality (whether $Pr[error] \geq \frac{1}{2}$ or the other way round).

So consider the case where $D \neq 0 $ i.e. $AB \neq C$. In this case then we have that at least one entry $(i,j)$ in $D$ is not zero (its 1 cuz we are doing mod 2). Let that entry be $d_{i,j}$. Let $v$ be a vector such that it picks up that entry. i.e. $Dv \neq 0$ such that $(Dv)_{i} = d_{i,j}$. In this case, if we have a bad $r$ (i.e. an r such that when $D \neq 0$ yields $Dr = 0$ ) then we could make it into a good vector $r'$ by flipping its $i$ coordinate. i.e.

$$ r' = r +v_i$$

This mapping from Bad to Good is clearly 1 to one. i.e. it clear that the equation $ r' = r +v_i$ only maps to one unique $r'$, so it cannot be one to many. Now lets see that its not many to one either. If there was another $\tilde r$ s.t. $\tilde r = r'$ then that would mean

$$r' = r+ v_i = \tilde r + v_i \;\; (\operatorname{mod} \; 2) \implies r = \tilde r  \;\; (\operatorname{mod} \; 2)$$

So its one to one. Therefore, the for each Bad $r$ there is a good $r'$. However, it is not clear to me why that would imply:

$$ Pr[A(Br) \neq C] = Pr[Dr \neq 0] \geq \frac{1}{2}$$

I see why it would be exactly equal to 1 but it is not clear to me at all why it implies the above inequality.

Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors are equally likely,
$$ \Pr[Dr \neq 0] = \frac{G}{G+B} \geq \frac{1}{2}. $$
The last inequality is a bit of algebra I leave to you.

Let $D=[d_{k,l}]$. If $d_{i,j}\not=0$, then $Prob(Dr\not=0)\geq Prob(i^{th}$ line of $Dr$ is $\not=0)=1/2$.


confusion with worst case for direct addressing In CLRS there is an exercise for direct address table

  Suppose that a dynamic set S is represented by a direct-address table
  T of length m. Describe a procedure that finds the maximum element
  of S. What is the worst-case performance of your procedure?

for this question i have seen a lot of websites indicating the worst case possibility is O(m) by starting and examining every non null slot up to end and then returning the maximum index,
but i think it can be done in a faster way than that.
 If direct addressing tables has m slots , then obviously the highest value should be in the end (i thought keys are treated as indexes in direct addressing,correct me if i am wrong) , so if we start iterating from the end then worst case would be O(m-n) where n is the number of elements examined by our iterator before reaching  non null value from end of the direct addressing table

is something wrong with my approach? Can any one clear this topic?

When iterating from start to end, you always need to examine $m$ items, which is $O(m)$.
When iterating from end to start, in the worst case you need to examine $m - |S|$ items, then the answer depends on the relationship between $|S|$ and $m$.

If $m - |S|$ is const., it takes $O(1)$ time.
Otherwise since $0 \leq |S| \leq m$, we have $m - |S| \leq m$, the upper bound is also $O(m)$.

Then in either cases, as long as $m - |S|$ is not const., both approaches have $O(m)$.

A "direct-address table" maps a subset of keys from 0 to m-1 to values. It would be nonsense if the values were equal to the indices - in that case instead of a "direct-address table" we would just use a bitmap.

So while "dynamic set is represented by a direct-address table" is not defined, I assume the set elements are the values stored in the table. So to find the largest, you need to visit all the entries used for elements of the set, and since we don't know which entries correspond to set elements without checking that they are null, we need to visit all m elements of the direct-address table.


Find all the special graphs which can reduced to the shortest paths graph I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative cycle.

An execution of some algorithms will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. For instance, Floyd–Warshall algorithm is straightforward, and it works. Let us denote the result by $G' = (V, E, W')$.

In $G'$, it is possible that for an edge from $i$ to $j$, $w'(i,j) = w'(i, k_0) + w'(k_0, k_1) + \dots + w'(k_n, j)$. Let us make from $G'$ another graph $G''$ whose any element is same as $G'$ except $w''(i,j) = \infty \neq w'(i,j)$. Therefore we know that an execution of a shortest paths algorithm on $G''$ will give $G'$.

So given a $G'$, I would like to find all the graphs like $G''$, such that for all $i$ and $j$, $w''(i,j) \in \{ w'(i,j), \infty\}$, and $G''$ can be reduced to $G'$ via a shortest paths algorithm.

Hope my question is clear... I do not know if an algorithm for this exists already, does anyone have any idea?

Nearest neighbor, nearest insertion, farthest insertion, and cheapest insertion are just some heuristics to get you started. You can also model the problem as a maximum flow integer program.

http://www.ida.liu.se/~TDDB19/reports_2003/htsp.pdf


Deciding whether a CFG is parity absent Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ odd-parity absent iff $|\{j : \mathcal{I}_j(s) = 0\}|$ is odd. That is, $s$ is odd-parity absent iff an odd number of characters from the alphabet are missing from $s$. Call a language $L \subseteq \Sigma^*$ odd-parity absent iff every string in $L$ is odd-parity absent.

Now, suppose that $G$ is a CFG. I'd like to come up with an algorithm for deciding whether or not $L(G)$ is odd-parity absent.

I thought it'd make things simpler if we first convert $G$ into an equivalent Chomsky-normal form grammar. Now, If I could determine what types of terminal strings each variable yields in the grammar (e.g., variable $A$ yields strings with a's and strings with a's and b's, etc.) then I could just inspect the right-hand sides of the start variable rules. But $A$ of course can yield a whole bunch of different variables along the way to derive a string of terminals, and each of those variables can yield a whole other bunch of different variables along the way, etc.

One option to generate the parse tree of the grammar, and check all the leaf strings if they are odd-parity absent. Even if you have recursive rules, one application of each rule is enough, because multiple occurrences of the same element does not affect the result.

However, there might be an easier way. Consider the following grammar on {a,b,c,d,e} alphabet with the following rules:

S -> A | B
A -> Abc | C
B -> cd | De
C -> aa
D -> b

Now you can assign odd-parity variables to each state. For example, a string at state S has number of missing instances = m (m=5 in this case). Let's denote it with p(S)=5.

From the first rule, p(A)=p(B)=p(S)=5. At the second rule, p(A) becomes 3, because at the first branch it eliminates 2 missing characters. Also p(C)=3, because p(A)=p(C), all other elements are missing.

At the third rule, p(B)=3 and p(D)=4. Fourth rule indicates p(C)=2 (2 a's, but the same element). Finally, p(D)=3.

Checking all ending states, p(B)=3, p(D)=3, and p(C)=2, which means the grammar has odd-parity. Verbally, there might be strings that end up with 3 elements missing, if they end up in state B or D.

In this way, you can decide if the grammar is odd-parity absent, just by looking at the grammar. The pseudo-code would be:

consumed_elements_set(S)={}
for each rule X with L as left-hand side:
    for each state R on the right hand side:
       consumed_elements_set(R)=consumed_elements_set(L)+terminals(X)
       p(R)=m-size(consumed_elements_set(R))
for each final state F:
    if p(F) is odd:
       print "not odd-parity absent!"


Number of "hamiltonian tours" from upper left to lower left corner of a grid graph? I got the following as an interview question:

Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction.  This is the number of Hamiltonian paths from upper left to lower left: a path such that every vertex is visited only once, and (this follows from the first statement) such that each edge is used at most once.

The grid world is a 4x10 matrix (4 rows and 10 columns).

Is it really this hard?

Matrix method for counting Hamiltonian cycles

And:

Number of Hamiltonian Paths from Lower Left to Upper Right

These papers seem dated--94, 97--but are they really asking a question that qualifies for publishing in a combinatorical journal?

Then I ran into this:
SO question: number of Hamiltonian paths

And am thinking dynamic programming, or divide and conquer...but it is really not clear how one would go about doing this. Is there a way to solve this problem in reasonable time?

I think a divide and conquer strategy is going to work here. The asymptotic runtime isn't great, but fortunately our graph is of fixed size. Pick some arbitrary node, $v$, and partition the rest of the nodes into two sets. The number of hamiltonian tours is the number of paths that start at the upper left, go through all nodes in the first side of the partition and end at $v$ multiplied by the number of paths that start at $v$, go through every node in the second half and end at the bottom left corner summed over every possible such partition. Recursively do this for each partition.


Why octal and hexadecimal? Computers use binary and humans decimals Why do we use other bases which are neither binary (for computers) nor decimals (for humans)?

Computers end up representing them in binary, and humans strongly prefer getting their decimal representation. Why not stick to these two bases?

Octal (base-8) and hexadecimal (base-16) numbers are a reasonable compromise between the binary (base-2) system computers use and decimal (base-10) system most humans use.

Computers aren't good at multiple symbols, thus base 2 (where you only have 2 symbols) is suitable for them while longer strings ,numbers with more digits, are less of a problem. Humans are very good with multiple symbols, but aren't that good in remembering longer strings.

Octal and hex use the human advantage that they can work with lots of symbols while it is still easily convertible back and forth between binary, because every hex digit represents 4 binary digits ($16=2^4$) and every octal digit represents 3 ($8=2^3$). I think hex wins over octal because it can easily be used to represent bytes and 16/32/64-bit numbers.

Computers understand binary numbers and in binary, the weights of the number are in power of 2, therefore the number of digits to represent a number may be large depending on the number.

Say, 64 in decimal can be represented by 7 bits whereas to represent number 5000 we require 13 bits.

Octal and hexadecimal number system are compact way of representing a binary number.


Known lower bounds on halting for finite machines? It's possible to determine whether a deterministic machine with finite memory will halt in O(n) time if the machine has n possible states. You simply run the machine until it halts or visits the same state twice, which is guaranteed to happen in no more than n steps.

Can any other algorithm do this in fewer steps? Is there a proof that no such algorithm can exist?

It seems that your machine runs without any further input once it is
started. Whatever input it has is encoded in its starting state. Since
your machine is deterministic, there is at most a single transition
from each state. So the state-transition graph of your automaton is a
directed graph composed of paths that either are isolated cycles or
are simply open linear path from an initial node/state to a final node
(corresponding to a halting state without transition). There may be
any (positive) number of such paths, possibly only one. Actually, only one of these paths is relevant, the one containing the initial state.

Depending on whether the initial state of your automaton is on a
cyclic path or on an open path, the automaton will run for ever or
halt at the end of the open path. The former is identified by checking
whether a state is visited twice. The latter is identified by the fact
that a halting state (without transition) is encountered.

In the question, you do not give any constraint or information on the way states and
transitions are defined, other than the following:

from a given state, there is a transition function that gives you
the next state;
you can know whether two states are the same or not.

So the only way you can map the graph structure to reason about it is
to follow the transition function from state to state, even when
knowing the total number of states $n$.

With $n$ states, you can have a graph $C_n$ composed of one cycle of
$n$ states. You can also have a graph $L_n$ composed of one open
linear path of $n$ states starting with the initial state and ending
with a halting state. The former is non-halting, while the latter is
halting.

Still assuming you know the number of states, and using only the gven
primitives, the only way to find a difference is to follow $n-1$
transition. Then you are either in a halting or a non-halting state.
The former tells you that computation halts, while the latter tells
you it does not halt.

You clearly will not do better when you do not know $n$ in
advance. Actually, you then need only one more transition to detect that
the computation is not halting.

So there is no way to decide whether your automaton halts in fewer
steps, unless you have other means for analyzing the state-transition
graph.

In other words, the only way you can have a faster algorithm is to
have some formalism that structures the state-transition graph with
properties that can be used to analyze it without having to follow the
transitions.

You can do it in constant time.
We already know that the machine halts.
So we just output "YES".

The issue is that you have to explain what is the domain of the inputs to the problem.
If the domain of the inputs only contains machines which halt then the problem is trivial:
all of them halt, there is nothing to check.

(You have to specify what is given as input if you want another answer.)


How do computers keep track of time? How are computers able to tell the correct time and date every time?

Whenever I close the computer (shut it down) all connections and processes inside stop.  How is it that when I open the computer again it tells the exact correct time? Does the computer not shut down completely when I shut it down? Are there some processes still running in it? But then how does my laptop tell the correct time when I take out the battery (and thus forcibly stop all processes) and start it again after a few days?

Computers have a "real-time clock" -- a special hardware device (e.g., containing a quartz crystal) on the motherboard that maintains the time.  It is always powered, even when you shut your computer off.  Also, the motherboard has a small battery that is used to power the clock device even when you disconnect your computer from power.  The battery doesn't last forever, but it will last at least a few weeks.  This helps the computer keep track of the time even when your computer is shut off.  The real-time clock doesn't need much power, so it's not wasting energy. If you take out the clock battery in addition to removing the main battery and disconnecting the power cable then the computer will lose track of time and will ask you to enter the time and date when you restart the computer.

To learn more, see Real-time clock and CMOS battery and Why does my motherboard have a battery.

Also, on many computers, when you connect your computer to an Internet connection, the OS will go find a time server on the network and query the time server for the current time.  The OS can use this to very accurately set your computer's local clock.  This uses the Network Time Protocol, also called NTP.

When you start Windows, it gains direct access to the memory of the Real Time Clock (RTC) and uses its date and time values to set the computer date and time. Timer interrupts maintain the computer time when Windows is running. A Time Daemon in Windows runs approximately once each hour after the Windows starts. The Time Daemon compares the time in Windows with the time in the RTC. If the two times are more than one minute apart, Windows changes the time and date to match the RTC. You cannot change the time interval for the Time Daemon to run.

If you use a time synchronizing service, such as the TimeServ.exe tool included with the Windows NT 4.0 Resource Kit, the tool updates the time in Windows and the computer's RTC.
If the Windows Time Service runs on a Windows 2000 based-computer, the Time Daemon in Windows cannot run approximately one time each hour after the Windows starts.

For more details visit this link:http://msdn2.microsoft.com/en-us/library/ms724936.aspxhttp://msdn2.microsoft.com/en-us/library/ms724942.aspx


Is there an equivalent of lambda calculus for object oriented languages? Lambda calculus serves as a foundation for all sorts of functional languages and its various extensions are compiler targets for languages like Haskell, ML, etc. So what is the equivalent for object oriented languages? Is there a minimal object calculus that serves as the foundation for object oriented languages?

So what is the equivalent for object oriented languages?

Lambda calculus.

I mean, there is Cardelli's object calculus (and a handful of derivatives), but in general, there's nothing fancy about object oriented languages that requires a new approach to computation.

It's well known (see TaPL for example) how to extend/encode Records and Mutation (and sub-typing/dispatch) onto/in lambda calculus. The underlying structures don't need to change, even though there are often layers above it that add semantic restriction and make things more usable (member access, implied this, object layouts, etc).

While not really an answer to your specific question, I will suggest that those OO langs that do have lambdas (or specifically do not) usually do so for practical reasons. The recent inclusion of lambdas/closures in Java 8 is a case-in-point.

This generated a lot of discussion, even well before Java 8. There is a dense website dedicated to this specific implementation that has a lot of technical and theoretical discussion that might be of interest?

Specifically, check out Bloch's "Controversy" slides.


Difference between time complexity and computational complexity For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?

I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.

Computational complexity is just a more general term, as time is not the only resource we might want to consider. The next most obvious is the space that an algorithm uses, and hence we can talk about space complexity, also as a part of computational complexity. Indeed we can do this for any measure you care you use, of course some measures are more useful than others.

So counting the number of steps that an algorithm takes in the worst case gives a time complexity bound for the problem it solves, counting how much memory/how many tape cells it uses gives a space complexity bound etc. etc.

Remember also that if you want to be strict, complexity refers to the problem, not the algorithm, so a problem has complexity bounds, an algorithm has resource bounds (running time, space use...).  It's just a matter of definitional formality, complexity theory deals with problems. Yes, algorithms are a key tool for analysing problems and complexity and algorithmics are closely tied together, but formally we wouldn't say Merge-Sort (an algorithm) is in $P$, it's the problem $\mathsf{Sorting}$ which is in $P$. Merge-Sort uses certain resources ($O(n\log n)$ steps for example). The resource bound and correctness of the algorithm imply the complexity (upper) bound for the problem, but they're different things. $\mathsf{Sorting}$ is also $TC^{0}$-complete under $AC^{0}$-reductions, this complexity bound can only really be stated for a problem (but does have algorithmic implications).

Cyclomatic complexity is often used as the measure of computational complexity a useful example is provided in https://stackoverflow.com/questions/9097987/calculation-of-cyclomatic-complexity

There may be many different (possibly nested) paths through an algorithm giving it a high cyclomatic complexity, but no loops giving it a low time complexity. A program with a single loop would have a low cyclomatic complexity but possibly a high time complexity.

Cyclomatic complexity is often used as a measure of the maintenance required for the code. A more detailed discussion is provided in http://docs.sonarqube.org/display/SONAR/Bad+Distribution+of+Complexity. This is different to time complexity that is run time measurement of the code and may be used to assess the users perception of the effectiveness of the system.


Why does this mergesort variant not do Θ(n) comparisons on average? A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm:

sort(array):
    if length(array) < 2:
        return array
    unsorted ← empty_array
    i ← 0
    while i < length(array) - 1:
        if array[i] > array[i + 1]:
            push(unsorted, pop(array, i + 1))
        else:
            i ← i + 1
    return merge(array, sort(unsorted))

(push(array, element) puts the new element at the end of the array and increases the array’s length by 1. pop(array, index) removes the element at that index from the array, moving all the elements at greater indices and decrementing the array’s length, and returns the removed element. merge is the same as in mergesort.)

Instead of simply splitting the array in the middle like mergesort, it splits it so that one resulting array doesn’t need to be recursively sorted. Let $n$ be the length of the array to be sorted. Applying the Master Theorem gives us

$$\begin{align*}
    T(n) &= T(n / b) + \mathrm{splitComparisons}(n) + \mathrm{mergeComparisons}(n) \\
         &= T(n / b) + (n - 1) + n \\
         &= T(n / b) + 2n - 1\,,
\end{align*}$$

so $f(n) = 2n - 1$ and $a = c = 1$ in the statement of the Master Theorem.

$b$ is one over the probability that an element is greater than the next element and will go into the array to be recursively sorted. For example, if there's a 25% chance that array[i] > array[i + 1] (for all i), $b = 4$. $b$ is clearly greater than $1$, since the length of unsorted array grows smaller with every recursive call, so taking the logarithm with base $b$ of $1$ will always give us $0$, which is less than $c$. Then $T(n) = \Theta(f(n)) = \Theta(n)$.

But that can’t be true, so the Master Theorem isn't applicable for some reason; I suspect because $b$ isn't constant, but I don’t know how to prove that. The worst case of the sorting algorithm obviously requires a quadratic number of comparisons and the best case linear, so by analogy with bubblesort, insertion sort, etc, I’m guessing this algorithm also makes a quadratic number of comparisons on average.

Since you don't do any reordering while splitting, the length of array after the while loop can not be larger than the length of the longest increasing subsequence in the input. Since that one is on average about $2\sqrt{n}$ elements long¹, you keep too many elements in unsorted.

In particular, there is no $b$ so that your ansatz describes the actual number of comparisions.

Assuming that the probability distribution of the length of the longest increasing subsequence survives your splitting, a proper ansatz would be of the form

$\qquad\displaystyle C(n) = C(n - 2\sqrt{n}) + \Theta(n)$

which does not seem to solve² to $C \in O(n)$.

In fact, it's even worse since you keep the "first" increasing subsequence, not the longest (in general); consider for instance $[1,n,2,3,4,\dots,n-1]$; you keep $[1,n]$ and recurse on $[2,3,\dots,n-1]$.

On the distribution of the length of the longest increasing subsequence of random permutations by J. Baik, P. Deift and K. Johansson (1999) [via Wikipedia]
I have not solved it explicitly, but plots suggest as much.

Assuming input array is in decreasing order, then array[i] > array[i+1] is always satisfied, your algorithm would move all but the first item from array to unsorted.  The running time is at least $\Omega(n^2)$.

Let array array' denote the same variable before and after the while loop.  Then array[i] is left in array' if and only array[i] is (one of) the biggest among array[0], ..., array[i].  In expectation, there would be only $O(\log n)$ items left in array', assuming the input array is random.


motivation and idea of defining non-deterministic Turing machine This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms and I also have some basic knowledge of how computers operate. However, I am really interested in the idea of a Turing machine, especially the non-deterministic one.

I have read Wiki about the definitions of a Turing machine (and watched some youtube videos) and I sort of accept that, although I really feel that this is a huge jump from an algorithm to an abstract machine. From my understanding (you are more than welcome to correct me):

A Turing machine is a machine performing works specified on a cookery book (algorithm).
The pages of the cookery book represent the "states" of your machine and each page contains a table saying that which state and which cell your machine will move to given the alphabet the machine read and your current state. (NB. This is not a function but a partial function because it is possible that the machine stops.)
So, to guess the idea and motivation of defining an abstract Turing machine, I imagine that the algorithm corresponds to the partial map, the memory of the computer corresponds to the (infinitely long) tape and what's finally on the tape is the answer to the question you wanna solve.

So, Turing machine looks like a machine to realize any algorithm to solve problems. One just "translates" any algorithm to a set of mysterious simple rules (i.e. the partial function) and let the machine do the laboring job and then we get the solution.

In this respect, Turing machine is always deterministic, because algorithms are deterministic. It tells you what to do next precisely. This is no uncertainty. Turing machine is just a machine to realize any algorithm.

OK, This is very abstract and I sort of accept it. However, then I read something called non-deterministic Turing machine (NTM) and then I was knocked down. A NTM is pretty much similar to a Turing machine except that the partial function is now replaced by a "relation". That is, it is a one-to-multiple map and it is no longer a (partial) function.

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm. It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers? If no, why do we need to allow multiple choices for a Turing machine?

Any help will be appreciated!

update From the linked post, it looks like the introduction of NTM naturally leads to a class of "problems" (not algorithms because a problem can be solved by several algorithms with different efficiencies) called NP problems. Forgive me that I still feel that every step is such a huge jump... Could someone close the gaps a little bit? thanks a lot!

Motivated by @reinierpost's answer, I found this explanation of NP problems on CMI website. The example problem is to choose 100 students from 400 candidates subject to some constraint that some pairs of students cannot be included. In this case, I can imagine that a Turing machine trying to solve this may naturally equip itself with a cloning ability such that it is able to generate the solution with multiple choices in the steps. Then, as long as some choices or branches of the NTM work, the machine finds the solution(s). In this sense, an NTM looks like a multi-threading parallelization to save time?

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm.

I think this is your primary misconception: an NTM is not supposed to be a realistic machine. That is, no one has ever tried to build a NTM, no one knows how to implement it, and algorithms in the real world are not written in this way with "multiple options".

An NTM is, instead, supposed to be a hypothetical more powerful computer; in contrast to the Turing machine, which corresponds to real computers, NTMs can do even more. Why can they do more? Basically, because they can branch off on several different options, or parallel universes; and they accept a string if and only if one of those universes accepts. A regular Turing machine corresponds to just having one parallel universe.

Let's see an example. Consider the following problem: Given as input an integer $x$, is the square root of $x$ an integer? Accept if yes, reject if no.

A Turing machine would have to do some math and figure out how to calculate the square root. So we have to do the hard work of designing a correct algorithm :(
An NTM doesn't have to do any of that hard work, and can just cheat :) It works in the following way: just nondeterministically guess the number $y$. Then check if $y^2 = x$. If so, accept.

This is how NTMs are unrealistic: they can just cheat and try all possibilities in different universes, even though when we know in the real world that this is impossible.
For example, if we input $9$ to the NTM we just described,
then there are lots of parallel universes that try different values of $y$: one tries $y = 1$, one tries $y = 2$, one tries $y = 3$, one tries $y = 4$, and so on. In many of these universes the NTM does the wrong thing: for example, it picks $y = 4$ and finds that $4^2 \ne 9$, and rejects (incorrectly). But those universes are just ignored; we don't care about them. The only thing that matters is that there is some universe where the machine accepts, namely the universe where we picked $y = 3$, and found that $3^2 = 9$.

  It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

It isn't exactly like "choosing for yourself"; it's that each choice is tried in a different parallel universe.

  Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers?

No, they are a little bit different than uncertainty choosing random numbers, mainly because we only care about the parallel universes where the machine accepts (in particular, we care if there is at least one parallel universe where it accepts), and we ignore all the universes where the machine rejects.

  If no, why do we need to allow multiple choices for a Turing machine?

We don't need them to describe real computations, but they are a useful tool for understanding the limits of computation. In particular, there are many problems that NTMs can solve efficiently, that we don't know how to solve efficiently with TMs; these are the famous "NP-complete" problems, and it is useful in practice to know what problems will be hard to design an algorithm for.

  In this sense, an NTM looks like a multi-threading parallelization to save time?

Yes, it is a lot like this, except a little bit less general: the thing is that the multiple parallel universes cannot communicate, but they only work independently, and then we care if at least one universe accepts.

In other words, with a multi-threading machine, you could try lots of different parallel threads, and then at the end you could have all the threads come together, and then decide what to do with all the outputs of the different threads. NTMs can't do that; they just spawn off lots of parallel universes and accept if at least one universe accepts.

Another difference (in terms of practicality) is that multi-threading on a real computer usually only allows for a small (probably constant) number of parallel threads. On the other hand, NTMs can spawn off as many parallel universes as you like; if the input is size $n$, they often might spawn of $2^n$ threads, which is a larger number than is possible in practice. This is why NTMs are not a realistic type of machine, and are just a theoretical object of study.

You're getting caught up in definitions. Algorithms are usually defined to be deterministic because they are usually introduced in a context where deterministic computation is the norm, the vehicle of choice for the task at hand.

Many real-life algorithms are nondeterministic (e.g. many cookbook recipes are very nondeterministic, and many algorithms in pseudo-code have lines that say "pick an x").
If we are denied the option of calling them "algorithms", and thus are left without a useful term to describe what they are, that is purely a matter of definition, it's not because such things do not exist.


What are the conditions for a NFA for its equivalent DFA to be maximal in size? We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in worst case gives us $2^S$ states, if our NFA had $S$ states.

My question is: what is determining the worst case scenario?

Here's a transcription of an algorithm in case of ambiguity:

Let $A = (Q,\Sigma,\delta,q_0,F)$ be a NFA. We construct a DFA $A' = (Q',\Sigma,\delta',q'_0,F')$ where

$Q' = \mathcal{P}(Q)$,
$F' = \{S \in Q' | F \cap S \neq \emptyset \}$,
$\delta'(S,a) =\bigcup_{s \in S} (\delta(s,a) \cup \hat \delta(s,\varepsilon))$, and
$q'_0 = \{q_0\} \cup \hat \delta(q_0, \varepsilon)$,

where $\hat\delta$ is the extended transition function of $A$.

The algorithm you refer to is called the Powerset Construction, and was first published by Michael Rabin and Dana Scott in 1959.

To answer your question as stated in the title, there is no maximal DFA for a regular language, since you can always take a DFA and add as many states as you want with transitions between them, but with no transitions between one of the original states and one of the new ones. Thus, the new states will not be reachable from the initial state $q_0$, so the language accepted by the automaton will not change (since $\hat\delta(q_0,w)$ will remain the same for all $w\in\Sigma^*$).

That said, it is clear that there can be no conditions on a NFA for its equivalent DFA to be maximal, since there is no unique equivalent DFA. In contrast, the minimal DFA is unique up to isomorphism.

A canonical example of a language accepted by a NFA with $n+1$ states with equivalent DFA of $2^n$ states is
$$L=\{w\in\{0,1\}^*:|w|\geq n\text{ and the \(n\)-th symbol from the last one is 1}\}.$$
A NFA for $L$ is $A=\langle Q,\{0,1\},\delta,q_0,\{q_{n+1}\}\rangle$, with $\delta(q_0,0)=\{q_0\}$, $\delta(q_0,1)=\{q_0,q_1\}$ and $\delta(q_i,0)=\delta(q_i,1)=\{q_{i+1}\}$ for $i\in\{1,\ldots,n\}$. The DFA resulting of applying the powerset construction to this NFA will have $2^n$ states, because you need to represent all $2^n$ words of length $n$ as suffixes of a word in $L$.

I believe this is a question at the frontier of knowledge, i.e. basically a research question. From a quick google search, it appears to be mostly open. Also, for many years I have believed it to be important and linked to complexity theory lower bounds. You don't mention directly a statistical analysis but that is what is implied by your question. Here are two examples of statistical studies on DFAs/NFAs that are similar to show the general approach to questions of this type. It appears that basic empirical research into questions like this is still mostly unexplored. Admittedly the 2nd does not relate directly to your question but it's the closest I could find of current research.

To study your question, a statistical attack such as the following could be envisioned. Random NFAs are constructed. Then the minimal DFA is determined. Graph the histogram results of how many DFAs of size $x$ result. Separate out the "large" DFAs based on some threshold. Formulate some metric or measurement of the NFA that gives an estimate of the resulting DFA size.

This metric would be related to graph theory metrics such as edge density etcetera. There is probably some very important graph theory metric or mix of metrics that estimates the "blow-up" but its not immediately obvious to me. I could suggest something like graph coloring metrics or clique metrics maybe. Then test the metric against the two sets "blow-up" vs "not blown-up".

Other answers to your question so far only give an example case of a "blow-up" (useful for a case study) but do not address the key issue of a general metric.

Another area to look at a successfully developed program of empirical research is SAT transition point research. That has developed very deep links to physics and thermodynamics concepts. It seems likely to me that similar concepts are applicable here. For example, one is likely to find analogous transition point type metrics; probably edge density etc. Note parallels to Kolmogorov compressibility theory.

I conjecture also that NFAs that "blow-up" vs those that don't are quite analogous somehow to "hard" vs "easy" instances of NP-complete problems.

Yet another way to study this problem would be to formulate an NFA minimization problem. That is, given a DFA, find the minimal NFA, which last I heard (many years ago) was still an open problem.

[1] On the performance of automata minimization algorithms Marco Almeida, Nelma Moreira, Rogério Reis

[2] Automata Recognizing No Words: A Statistical Approach Cristian S. Calude, Cezar Câmpeanu, Monica Dumitrescu


Decomposing an Algorithm into Local Transformations/Perturbations Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local change/perturbation in a confined neighborhood of the data while fixing the rest?

One benefit of this "breakdown" is improved conceptual understanding, and it also facilitates induction proofs (possibly based on invariants that are preserved by each step). Does this "decomposition" have a name in algorithm design? The idea might be similar to Divide and Conquer.

One might say that every individual step in an algorithm, like deleting an edge or labeling a vertex of a graph, is small enough to be considered "local", but I'm talking more about the "decomposition" in a higher-level description, like how truncating a polyhedron is local but sorting a list is not (even though at the lowest level, comparisons, insertions and deletions are local).

Examples of decomposing into local transformations

Augustin Cauchy's proof of his Rigidity Theorem relied on his "Arm Lemma" that opened up a convex planar chain by sequentially opening at each vertex. Although his proof was found to be wrong, he decomposed the opening algorithm into a series of "local opening moves", and he tried to prove that each local move preserved convexity of the chain. By induction, convexity would still hold after iterating over all vertices.
The pivot algorithm for self-avoiding walks (SAW) transforms a SAW into another by rotating or reflecting part of the original SAW. Markov Chain Monte Carlo can employ this transformation as a transition between SAW states to sample the space of SAWs.
As an application of the above, one technique of protein folding prediction is to force an amino acid chain into several known protein structures, choose the one with the lowest energy (due to intermolecular forces), then let the chosen structure "relax" into a configuation with lower energy. Relaxation involves the prescription of a few "local moves", where small parts of the chain can "wriggle around" (e.g. subchains pivoting around their ends), and random wriggles are allowed for a period of time to let the chain "stabilize". Modelling the chain as an SAW allows pivots to be used as a "wriggle".

there are several ways to measure this "local vs global" decomposition dichotomy of problems which does show up in a wide variety of CS contexts.

how many local minima there are versus a global minimum for optimization problems. if there are many local minima it is harder to find the global minimum. roughly this is also a measure of how effective greedy algorithms are on that problem.
algorithmic speedup due to parallelism. this metric is sensitive to both the problem and the algorithm chosen. for example the problem may not be very "decomposable", or a problem may be decomposable but it is not solved with a most efficient algorithm. for more decomposable problems, algorithmic speedup is nearly linear in increasing processors. for less decomposable problems, it is more an asymptotic sub-linear relationship.
communication overhead of parallel processing. the decomposability is known as "granularity". for problems that are not as granular, there is more communication required between separate parallel threads or processors. problems with very "fine" granularity ie not requiring much or any communication between processors are called embarrassingly parallel.
NC is the class of efficiently parallelizable algorithms. NC=?P is an open question. ie in short are all P-time algorithm efficiently parallelizable, or not?

one paper that does attempt to study these concepts more formally/systematically within the context of parallel computing is Landscape of parallel computing, the view from Berkeley. see eg "7+ dwarves" for the basic algorithmic patterns that seem to appear in practice and commentary on their decomposability wrt parallelism.

another influential researcher recently looking into the inherent limits/ceilings/gains of parallelism in CPU design (ie multicore) which relates to the general decomposability of everyday running code is Esmaeilzadeh.

The transformation that you are talking about is the very definition of Algorithm.

  An algorithm is an effective method expressed as a finite list of
  well-defined instructions(Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987).) for calculating a function.

I don't think that there is a place for local or global definitions, but steps. Once you been able to create a well defined steps of your algorithm, not only that it will be easier to understand/implement it but also to improve it, by looking at each step individually.


Is the credit assignment problem a well-posed one? Credit assignment is the process of assigning credit (or blame) to a particular move in a sequence of moves (temporal credit assignment) or to a particular node (structural credit assignment) among many nodes, for example, in a network.

My question is somewhat philosophical: Does it even make sense to speak of credit assignment as a problem to be solved?

Take the example of a football (soccer) team. (I read in a paper that robo-soccer teams face a version of the credit assignment problem). However, even in the case of a real-life soccer team composed of humans players, it is virtually impossible to separate the performance of an individual in scoring a goal from the contribution of the rest of the team in the most general case. If quantifying and assigning credit to players is so difficult, does it even make sense to try to assign credit to nodes in a complex system, with many pieces that are interacting in subtle ways?

If you can do it well, it is useful.  If you can accurately identify which move was to blame for bad outcomes -- or which one is to credit for good outcomes -- that is useful in helping you learn to make better moves.  I'll let you decide whether that's enough for it to make sense to speak of it as a problem to be solved. I'm not very knowledgeable about philosophy, so I don't know whether that qualifies.

It depends on what the system is used for. I mean, soccer (football) has a strict set of laws and limited number of moves whereas systems with limited laws and a high number of moves credit becomes more important. Like for example, with StackExchange: https://meta.stackexchange.com/questions/17831/whats-the-incentive-to-answer-questions


Is Virtual Memory unreliable? I have a question regarding multilevel page tables. As far as I know, in most 64 bit systems only 48 bits are used in page tables which would allow for 256TB of virtual memory to be addressed.

For personal computers, I don't understand how they would ever be able to support that amount of memory being virtualized. If the processes currently running on your computer think they have a total of 256TB available, if they do end up using all that memory, the contents would eventually need to be flushed back to disk. This is not possible since your disk can't possibly hold that much memory.

I'm thinking on an analogy to a bank that tells its customers they can each take out loans of 1,000 gold bars. They give their customers a note saying they have 1,000 gold bars worth of funds. Now say that the customers have used their loans to obtain different goods which they want to store in the bank. The bank would not be able to hold all those goods, and the people (processes) wouldn't be able to hold those goods either since once a computer is shut off all the memory not on disk is volatile. In a sense the bank is offering more than it can really hold.

For a more practical example, say I have 1GB of disk memory available and my virtual memory system is able to virtualize 3GB of memory. Now say I open 3 text files and start typing stuff into them, eventually reaching that 3GB limit. Now I want to save those files, but I only have 1GB available on disk!

Isn't virtual memory unreliable from a process point of view since it's saying "I can store all this stuff for you" but at the end of the day it doesn't have the resources to do so?

At a hardware level, virtual memory means, essentially, a mapping from a virtual address space to a physical address space, the data structures and instructions to maintain them, and a facility to trap to the operating system if a mapping is not valid. This mapping is at the page level: a page maps to a page frame.

At the operating system level, we usually conceptualise a virtual address space as a collection of segments. A segment could represent part of a file which resides on secondary storage (e.g. disk). This could be program text, or a memory-mapped file. Or it could represent anonymous memory, that is, memory which is allocated by a process and may be swapped to secondary storage if not needed. Anonymous segments are often zero-fill, which isn't backed by physical memory until it is first used. Or it could represent a memory-mapped I/O area, or an operating system device, or an operating system data structure (e.g. the "u area" in Unix).

Segments can be shared between address spaces (e.g. after the Unix fork system call). They can be copy-on-write. And so on and so forth.

There are enough "things" that can be mapped which aren't really "memory" that you can't really say that virtual address space is only as useful as the amount of physical stuff that can be mapped to it.

One more thing: Another advantage of a large virtual address space is reduced external fragmentation. You see, the segments that comprise a virtual address space need to be allocated and deallocated just like anything else, and you can't really move them within the address space. So having a large virtual address makes it easier to allocate within it.

Without virtual memory, an attempt to allocate memory can fail. You can check the documentation for your programming language etc. to find out what exactly happens in that case.

With virtual memory, when attempts to allocate memory go beyond available RAM, virtual memory will be used, which will slow things down. If you have 4 GB of RAM, and your applications require 8 GB, the memory allocations will work, but your system will slow down, eventually to the point of unusability. In practice, memory allocations won't fail - the user will just die of boredom or old age before that happens.

Beyond that, it depends on the operating system and/or which strategies it uses. For some OS, memory allocation will fail or succeed, just as with non-virtual memory. For others, allocations will succeed, and then the whole system may run out of memory if an application tries to actually use this memory.

And beyond that, well, life isn't always easy.