Some questions on parallel computing and the class NC I have a number of related questions about these two topics.

First, most complexity texts only gloss over the class $\mathbb{NC}$.  Is there a good resource that covers the research more in depth?  For example, something that discusses all of my questions below.  Also, I'm assuming that $\mathbb{NC}$ still sees a fair amount of research due to its link to parallelization, but I could be wrong.    The section in the complexity zoo isn't much help.

Second, computation over a semigroup is in $\mathbb{NC}^1$ if we assume the semigroup operation takes constant time.  But what if the operation does not take constant time, as is the case for unbounded integers?  Are there any known $\mathbb{NC}^i$-complete problems?

Third, since $\mathbb{L} \subseteq \mathbb{NC}^2$, is there an algorithm to convert any logspace algorithm into a parallel version?

Fourth, it sounds like most people assume that $\mathbb{NC} \ne \mathbb{P}$ in the same way that $\mathbb{P} \ne \mathbb{NP}$.  What is the intuition behind this?

Fifth, every text I've read mentions the class $\mathbb{RNC}$ but gives no examples of problems it contains.  Are there any?

Finally, this answer mentions problems in $\mathbb{P}$ with sublinear parallel execution time.  What are some examples of these problems?  Are there other complexity classes that contain parallel algorithms that are not known to be in $\mathbb{NC}$?

Third, since $\sf{L} \subseteq \sf{NC}^2$, is there an algorithm to convert any logspace algorithm into a parallel version?

It can be shown (Arora and Barak textbook) given a $t(n)$-time TM $M$, that an oblivious TM $M'$ (i.e. a TM whose head movement is independent of its input $x$) can construct a circuit $C_n$ to compute $M(x)$ where $|x| = n$.

The proof sketch is along the lines of having $M'$ simulate $M$ and defining "snapshots" of its state (i.e. head positions, symbols at heads) at each time-step $t_i$ (think of a computational log). Each step $t_i$ can be computed from $x$ and the state $t_{i-1}$. Because each snapshot involves only a constant-sized string, and there exist only a constant amount of strings of that size, the snapshot at $t_i$ can be computed by a constant-sized circuit.

If you compose the constant-sized circuits for each $t_i$ we have a circuit that computes $M(x)$. Using this fact, along with the restriction that the language of $M$ is in $\sf{L}$ we see that our circuit $C_n$ is by definition logspace-uniform, where uniformity just means that our circuits in our circuit family $\{C_n\}$ computing $M(x)$ all have the same algorithm. Not a custom-made algorithm for each circuit operating on input size $n$.

Again, from the definition of uniformity we see that circuits deciding any language in $\sf{L}$ must have a function $\text{size}(n)$ computable in $O(\log n).$ The circuit family $\sf{AC}^1$ has at most $O(\log n)$ depth.

Finally it can be shown that $\sf{AC}^1 \subseteq \sf{NC}^2$ giving the relation in question.

  Fourth, it sounds like most people assume that $\sf{NC} \neq \sf{P}$ in the same way that $\sf{P} \neq \sf{NP}$. What is the intuition behind this?

Before we go further, let us define what $\sf{P}$-completeness means.

A language $L$ is $\sf{P}$-complete if $L \in \sf{P}$ and every language in $\sf{P}$ is logspace reducible to it. Additionally, if $L$ is $\sf{P}$-complete then the following are true

$L \in \sf{NC} \iff \sf{P} = \sf{NC}$
$L \in \sf{L} \iff \sf{P} = \sf{L}$

Now we consider $\sf{NC}$ to be the class of languages efficiently decided by a parallel computer (our circuit). There are some problems in $\sf{P}$ that seem to resist any attempt at parallelization (i.e. Linear Programming, and Circuit Value Problem). That is to say, certain problems require computation to be done in a step-wise fashion.

For example, the Circuit Value Problem is defined as:

  Given a circuit $C$, input $x$, and a gate $g \in C$, what is the output of $g$ on $C(x)$?

We do not know how to compute this any better than computing all the gates $g'$ that come before $g$. Given some of them may be computed in parallel, for example if they all occur at some time-step $t_i$, but we dont know how compute the output of gates at timestep $t_i$ and time-step $t_{i+1}$ for the obvious difficulty that gates at $t_{i+1}$ require the output of gates at $t_i$!

This is the intuition behind $\sf{NC} \neq \sf{P}$.

Limits to Parallel Computation is a book about $\sf{P}$-Completeness in similar vein of Garey & Johnson's $\sf{NP}$-Completeness book.


String matching for wildcard-based records Let's say that we have a string "1.2.3" and want to find a match for it in the following records:

1.2.9
1.4.5
1.*.3

For each record:

The . is a separator that divides the string into segments.
Each segment can have a static value or * that matches any segment value.
There are no duplicated records. If there are multiple matches for a given string, only one is returned, following an exact match and left to right rule. So, for the following hypothetical matches for 1.2.3, the previous has priority over the latter: 1.2.3 > 1.2.* > 1.*.3 > *.2.3.

In the initial example, the matching record will be "1.*.3".

Note: here, the numbers used to represent a record are a simplification of a more complex, unpredictable, variable-sized value, such as abc.wxyz.fghijklm. So it is not possible to build tables for possible wildcard values.

I'm looking for the (theoretically) fastest lookup algorithm to find a matching record in memory given these non-requirements:

Longest prefix matches are not a requirement;
Only lookup speed matters: record insertion or deletion are not required to be fast;
Memory space efficiency is not a requirement.

I experimented a range of trie variants and I am guessing (sorry if this sounds naive) that tries, or any datastructure, can't find a match for the proposed problem without backtracking. I'd appreciate some comments on this.

So, which datastructure would best fit my (non-)criteria?

One candidate approach would be build a BDD or a deterministic finite-state automaton that accepts all strings that match at least one of the records in your set of records.  These data structures can handle wildcards.  To use a BDD, treat each segment as a bit string, so the alphabet is $\{0,1,.\}$ (perhaps it's now a trinary decision diagram rather than a binary decision diagram, but the ideas remain the same).

An alternative approach (if the number of segments per string will always be relatively small): You can solve your problem by building a set of indices, one index for each subset of possible segments.

Suppose we're guaranteed that every string will have exactly 3 segments, call them segments ABC.  We're now going to build seven indices:

The ABC index contains the set of all records with no wildcard.  e.g., 1.2.3
The AB index contains the set of all records with a single wildcard, in the 3rd (C) segment. e.g., 1.2.*
The AC index contains the set of all records with a single wildcard, in the 2nd (B) segment. e.g., 1.*.3
The BC index contains the set of all records with a single wildcard, in the 1st (A) segment. e.g., *.2.3
The A index contains the set of all records with two wildcards, in the 2nd and 3rd (B and C) segments. e.g., 1.*.*
The B index contains the set of all records with two wildcards, in the 1st and 3rd (A and C) segments. e.g., *.2.*
The C index contains the set of all records with two wildcards, in the 1st and 2nd (A and B) segments. e.g., *.*.3
I assume you won't have any records with three wildcards (*.*.*), but if that was possible, you'd have an 8th index that records whether you have such a record or not.

Each index is stored as a hash table, so given a string you can quickly (in $O(1)$ time) check whether that string is present in that index.

Now, when you receive a string 4.5.6, you look it up in each index.  For instance, you look up 4.5.6 in the ABC index, 4.5.* in the AB index, 4.*.6 in the AC index, and so on.  If any of these lookups succeeds, then you know that 4.5.6 matches one of the records.  Otherwise, 4.5.6 does not match any of the records.  The running time for a lookup is $O(1)$.

If you know that every string will have exactly 5 segments, you'll need 31 indices and the time for a lookup is $O(1)$ (31 lookups into 31 hashtables).
If every string has exactly 5 segments and you know that no record will have more than 2 wildcards, then it's enough to have $1+5+10=16$ indices.

This will probably be OK for your particular parameters, where every string has at most 5 segments.  Obviously, though, if the number of segments is too large, this will be extremely slow and inefficient.


NLP - Deep belief neural networks or logic? The NLP progresses seems to me that has split in two big group of thoughts:

Deep learning have a neural network with multiple layers that has been trained and learned to represent knowledge and understand the meaning of sentences. However, such system would be difficult to debug and correct
Logic and inference, label parts of speech and learn by inference and using tools such as Natural logic.

Can someone point out if anything is wrong in these conclusions? Is there any other stream of thoughts that I should be taking into consideration?

Very briefly:

Option 1 faces difficulties since certain connectionist models are incapable of learning natural languages.

Option 2 faces grave difficulties due to many negative results, notably Gold's theorem.
There's a nice overview which includes a discussion of probabilistic approaches.

Generally, the response to these difficulties has been to look at other sources of information beyond the linguistic input alone.


can virtual address map any on virtual memory on disk? I was reading a textbook which says that:

If the valid bit is set, the address field indicates the start of the corresponding physical page in DRAM where the virtual page is cached. If the valid bit is not set, then a null address indicates that the virtual page has not yet been allocated. Otherwise, the address points to the start of the virtual page on disk.

My question is, does each page tabe entry(PTE) need to be match the same offset one in disk? for example, PTE 1 has VP 1 in physical memory, but can PTE 1 originally mapped to VP 3? or PTE 1 has to map VP 1,  PTE 2 has to map VP 2,  PTE 3 has to map VP 3 and so on?
if PTE x has to map VP x, then why when valid bit is not set then the address points to the start of the virtual page on disk? can't we use the offset x in PTE x to infer that it maps to VP x?

My question is, does each page tabe entry(PTE) need to be match the same offset one in disk?

No. They can map to anywhere in physical memory and they can map to anywhere on the disk. If they had to map to the same offset, there would be no point using virtual memory.


Integer log2 as a catamorphism? Recursion schemes are structured methods for expressing recursive functions, of increasing interest due to their ubiquity in functional programming. For example, catamorphisms (familiar in the guise of 'fold' on lists) can be defined for all inductively-defined (i.e. algebraic) data types and in the particular case below, for natural numbers ("A natural number is either zero, or the successor of a natural number).

Q. Can (floor) log2 on the natural numbers (setting log2(0) to be 0) be readily expressed as a single recursion scheme (e.g. a catamorphism), as opposed to via a hylomorphism (which is an anamorphism followed by catamorphism)?

A formulation of log2 via metamorphisms is given in Martin Erwig's Metamorphic Programming. Can it instead be expressed simply as a catamorphism?

recNat :: (Integer -> a -> a) -> a -> Integer -> a
recNat s z n | n <= 0    = z
             | otherwise = s (n-1) (recNat s z (n-1))
-- Exercise: Express this in terms of foldNat.

log2 :: Integer -> Integer
log2 = fst . recNat (\n (c, p) -> if 2*p > n+1 then (c, p) else (c+1, 2*p)) (0, 1)


Use a pathfinding algorithm, such as BFS, A*, or some other suitable algorithm.  Here each rectangle is treated as a vertex of the graph, and you imagine an edge from rectangle r1 to rectangle r2 if that's an allowed move (if you currently have rectangle r1, you can get to r2 in a single step).

Think of the rectangle as the "state" of the system at any point in time.  When you want to explore the statespace of a system, pathfinding algorithms are often worth a try.


Is there a naming convention for the left child of a right child (and vice versa)? That is, the right child of a left child, or the left child of a right child. The best that I can come up with is the "opposing child" but I was wondering if anyone has come across an existing naming convention for this.

You can use 'sibling' (or 'brother'/'sister' if you prefer to gender the vertices). It's somewhat commonly used, but you may want to redefine it quickly when using it extensively.

NB: this terminology can be used for non-binary tree, the sibling of a vertex is any other vertex with the same parent/father.

While you may want to find a more reliable source, Wikipedia agrees with me at the moment: https://en.m.wikipedia.org/wiki/Tree_structure


3-Dimensional Matching with at Most $2n$ Hyperedges In 3 dimensional matching, we are given a set $M\subseteq X\times Y\times Z$ where $|X|=|Y|=|Z|=n$. A matching in $M$ is a subset $T⊆M$ such that no elements in $T$ agree in any coordinate. The goal is to find a matching in $M$ of size $n$.

If we assume that $n\leq|M|=m<2n$, can we solve 3DM in polynomial-time?

I know that in a 2-bounded instance of 3DM, 3DM can be solved in polynomial-time. The 2-bounded instance is when no element appears in more than two triples in $M$. For $m<2n$, we do not necessarily have a 2-bounded instance.

Further, in a 3-bounded instance of 3DM, 3DM is NP-hard. The 3-bounded instance is when no element appears in more than three triples in $M$, that is $m\leq3n$.

The restriction $m < 2n$ does not help to solve the problem in polynomial time. Note that any 3-dimensional matching instance can be polynomially reduced into an instance with $m < 2n$ by adding $m$ elements to the sets $X$, $Y$ and $Z$ and $m$ hyperedges to connect these new elements. The resulting instance has $n' = n + m$ and $m' = 2m$, so $m' < 2n'$ assuming $n>0$. Also, this reduction can be generalized for any constant $c > 1$ to show that 3-dimensional matching is NP-complete with the restriction that $m < cn$.

For solving the problem faster I suggest to find some other restrictions in the instances you have. For example in graphs, the natural parameter to express sparseness would be degeneracy.


A metaphor for recursive enumerability In his commentary on a case involving pornography in 1964, U.S. Supreme Court Justice Potter Stewart sidestepped the question of defining what it meant for a work to be pornographic, but then said "I know it when I see it." It struck me that this was a pretty good description of recursive enumerability (recognizability): he was asserting that he was a recognizer for the set of all creative events, broadly construed, that were pornographic. By saying that he wouldn't, and perhaps couldn't, define pornography, he was saying that as far as he was concerned, pornography was not recursive, in that while he could answer "yes" to the question "is this work pornographic?" he couldn't correctly answer "no" in all cases, saying, in effect, that the set of pornographic events wasn't recursive (decidable). In short, he claimed, metaphorically, the set PORN was in $RE\setminus R$.

Pedagogically, this metaphor might work well as an aside when I introduce $RE$ and $R$ to my students, but I'm not entirely happy with it, since it seems feasible that another jurist might very well assert that s/he could indeed determine, for all possible creative events, $e$, whether $e$ was not pornographic. The question is, is there a "tighter" real-world metaphor, where we could agree that determining whether $e$ is a member of $P$ is obviously possible, but determining that $e\notin P$ for all $e$ is obviously impossible?

I was first taken by your metaphore, but I do not think it works.
Actually he is saying that he is himself a decision procedure, though
he cannot describe his own internal program. Hence Justice Stewart
decisions are recursive, not recursively enumerable, at least where
pornography is concerned. I would indeed expect anyone capable of such
an arrogant statement to be computationally limited.

Now for other examples taken from the real world, the first that comes
to mind is actually co-RE, though that amounts to the complement being
RE.  It is the buggy program problem. If a program has a bug, it will
show some day, provided we use it long enough. But we cannot be sure
thre are no bugs, even when none has been found. Well, that was before
we could prove program correct (not that we are really there yet).

A close problem is falsifiability of scientific theories, as defined by
Karl Popper. The idea is that science is primarily co-RE:

A theory in the empirical sciences can never be proven, but it nust
be falsifiable, meaning that it can and should be scrutinised by
decisive experiments that could prove it wrong.

In other words, all we can know for certain, is that some empirical
science theories are false, because some consequences have been
experimentally proved false.
Whatever remain might be good theories, unless later proved false.

False theories form a RE set. Good theories are the co-RE complement.

But I am not sure this last example will make things clearer for your
students.

And the relations between scientific theories, or their correctness
status are a bit more subtle than that.

P.S. I think mortal people form an RE set.


Minimum frame size in ethernet Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 μs. The minimum frame size is:

a) 94

b) 416

c) 464

d) 512

My approach:- I have read in the book that minimum frame transmission time is atleast twice the round trip time.So by that logic i can say that the answer will be 464.As soon as the first bit of jamming signal reaches the sender,it know about the collision. But I need to know whether time to transmit jamming signal over the link should also be included in this case?I mean whether the first bit of the jamming signal is sufficient to for the sender to detect the collision or the complete jamming signal needs to be received at sender side,which will make the answer as 512.

I dont have the answer as this question was in some exam in 2005 and there was no answers available to this.

This might not be the correct answer to your question(as I am not sure about jamming signal), but it might resolve the query.

As Ethernet uses CSMA/CD for error detection, the time taken to transmit the data must be greater than or equal to twice the time taken to propagate the data. Only then the station will come to know if there had been a collision.

Tt >= 2*Tp


Maximum matching using linear programming In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to solve the following LP:

$$
\text{maximize}~~\sum_{e\in E} w_e x_e
\\
\text{subject to}~~\sum_{e\in E: v\in e}x_e=1\text{ for all }v\in V
\\
0\le x_{e}\le 1\text{ for }e\in E.
$$

If some value $x_e$ in the optimal solution is fractional, then there must be another fractional $x_{e'}$ near the same vertex (since the sum of all edges near each vertex is 1). By following these fractional edges, we eventually find a cycle of fractional edges. We can then move value along the edges in the cycle until at least one edge becomes integral (0 or 1).

A crucial aspect in this solution is that all such cycles are of even length, since the graph is bipartite. If the graph is not bipartite, then the above scheme does not work since we might have odd-length cycles.

QUESTION: Is there a similar algorithm for finding a maximum-cardinality matching, even in unweighted graphs, based on rounding a fractional solution to the above LP?

(I know that this problem can be solved by the blossom algorithm, but it is very complicated and I am hoping that the LP approach can yield a simpler algorithm).

This approach is described by Grötschel, Lovász and Schrijver in their paper The ellipsoid method and its consequences in combinatorial optimization, as well as in their book Geometric algorithms and combinatorial optimization. Edmonds gave a description of the general matching polytope, which has exponentially many defining linear inequalities. While the simplex method cannot be used to optimize the corresponding linear program, other approaches, such as the ellipsoid algorithm and some interior point methods, can use a separation oracle for efficient optimization (at least theoretically).

There is a third algorithm, due to Micali and V. Vazirani, which is however also quite complicated; see the recent exposition by Vazirani.


Number of 5-cycles and 6-cycles in a simple graph Is there any formula for computing the number of 5-cycles and 6-cycles in a simple undirected graph?

I'll suppose that you looking for $k$ -cycle, and in the following $f(k)$ is a computable function which belongs to $O(k!)$.

One simple algorithm is considering all possible k+1 vertices, to check whether they are part of a some cycle or not, this algorithm is $O(|V|^{k+1})$ (If we consider corresponding edge, running time can be improved on sparse graphs). This idea can be improved by using matrix multiplication algorithm, we know that in the level $m$ of (adjacency) matrix multiplication we have the number of paths of length $m$ starting from each node. Then we can calculate $M^k$, this can be done in $O(f(k)\cdot M^{\omega+1})$ (where $M^\omega$ is the lower bound for running time of matrix multiplication for adjacency matrix $M$ of input graph). But converting this to a cycle is a little bit tricky task and you can find one algorithm here, running time of exponential part still is independent of size of graph and is depend to $f$, but sure in the cycle case $f$ is bigger ($k!$ in the first paper). There are faster but more complicated algorithms like what described in this, all of them are consequence of these simple ideas.

P.S: I hope to be clear that the bound that I mentioned is not tight, e.g in both Monien and Alan's papers, upper bounds are better than general thing that I wrote.


Simplifying an upper O-bound in two variables I have an algorithm that depends on two input sizes n and m. The complexity breaks down to the following equation:

$\frac{nm - 1}{n-1} = O(?)$

Is Big-O of the Formula $O(mn)$ or $O(m)$ because $n$ cancels out? Thank you in advance!

PS: I know that if $O(m)$ is the upper bound $O(mn)$ is an upper bound too, I want to find the tightest.

I assume that $n\ge 2$, which implies $1/(n-1)\le 2/n$. Then

$$ \frac{nm-1}{n-1} \le \frac{nm}{n-1} \le 2  \frac{nm}{n} \le 2m.   $$

Thus your expression is bounded by $O(m)$.


What's the purpose of Karger's algorithm? Suppose I'm given an undirected graph and two nodes: v and u.

If I understand Karger's algorithm correctly, it's used to find a minimum cut of a graph, not the ("the" because there is only one for any given graph) minimum cut such that v is in one part of graph and u is in the other part.

Why don't we simply find the vertex with the minimum number of edges and remove those edges. Thus, we "partition" the graph into two subgraphs: the node which had the minimum number of edges and the rest of the original graph. What am I missing?

Even in an unweighted graph, your suggested algorithm doesn't work:  take a graph of 6 vertices with triangle a, b, c, and triangle d, e, f, with an edge between c and d.  Vertices a, b, e, and f each have minimal degrees of 2, but cutting the graph between the two triangles gives a cut of 1.


Finding all circuits that contain a given edge Given a directed graph $G = (V, E)$ and an edge $e \in E$, I'm trying to come up with an algorithm to construct the minimum induced subgraph $H$ of $G$ with the property that every circuit in $G$ that traverses $e$ is in also in $H$.

As an example, suppose graph $G$ has vertices $V = \{1,2,3,4\}$ and edges $\{(1,2), (2,1), (2,3), (3,2), (3,1), (2,4), (4,3)\}$, and $e = (4, 3)$. The subgraph $H$ that the algorithm should output consists of the two circuits $2,4,3,2$ and $2,4,3,1,2$.

Of course, this problem can be solved by enumerating all circuits of $G$, but I'm hoping that someone here can come up with something better (that is, with strongly polynomial complexity, in the size of the graph) than that.

EDIT: I just found this post that solves the problem for undirected graphs, but it doesn't provide any directions for directed graphs. I don't see a straightforward generalisation to directed graphs from that post.

It should be NP-complete to compute, given an arc $e = uv$ of a directed graph $D = (V,A)$ whether there is a cycle containing some vertex $w$ using the arc $e$.  The instance to this problem is $(D,e,w)$.

By reducing from back-and-forth (two-disjoint paths from $a$ to $b$ and from $b$ to $a$), given an instance $(D',a,b)$ of back-and-forth, construct the instance $D$ where you make two copies of $a$, $a_1$ and $a_2$ and an arc going from $a_1$ to $a_2$.  The constructed instance is $(D,(a_1a_2),b)$.

Now, suppose there are two-disjoint paths from $a$ to $b$ and back, then there is a cycle from $a_2$ to $b$ and from $b$ to $a_1$, hence $b$ is on a cycle containing the arc $a_1a_2$.  For the reverse direction suppose that $b$ is on a cycle traversing the arc $a_1a_2$.  Then, in the original graph, there is a path from $a$ to $b$ and one from $b$ to $a$.  qed


Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$ I have been working on the following homework question, and I just can't seem to make any progress:

Construct a finite automaton having fewer than 36 states that recognizes the language $\{s \in a^* : \operatorname{gcd}(|s|, 504) \geq 6\}$, where $|s|$ is the length of $s$.

So far I have been trying to figure out a regular pattern in $504$ and have broken it down to the prime factorization $504 = 2^3 \cdot 3^2 \cdot 7$, which means that all divisors must be multiples of 2, 3, or 7. However I don't know how to create the finite automaton (NFA or DFA). Any help is appreciated!

The number $504$ has $4\cdot3\cdot2=24$ divisors:
$$1,
 2,
 3,
 4,
 6,
 7,
 8,
 9,
 12,
 14,
 18,
 21,
 24,
 28,
 36,
 42,
 56,
 63,
 72,
 84,
 126,
 168,
 252,
 504$$
Out of these, $20$ are at least $6$:
$$
 6,
 7,
 8,
 9,
 12,
 14,
 18,
 21,
 24,
 28,
 36,
 42,
 56,
 63,
 72,
 84,
 126,
 168,
 252,
 504$$
For an integer $n$, $\operatorname{gcd}(n,504) \geq 6$ iff $n$ is a multiple of one of these numbers. To check this, we don't really need to go over all $20$ possibilities. For example, if $n$ is divisible by $12$ then it is also divisible by $6$, so we can remove $12$ from the list. The list narrows down to only $4$ options:
$$
6,7,8,9
$$
That is,
$$
\operatorname{gcd}(n,504) \geq 6 \Leftrightarrow 6 \mid n \text{ or } 7 \mid n \text{ or } 8 \mid n \text{ or } 9 \mid n
$$
You can check the condition on the right using an NFA with $6+7+8+9 = 30$ states (or $31$ states if you do not allow multiple initial states).


Modular exponentiation is a well-known algorithm. It is routinely available in libraries and languages that can manipulate large integers, including Wolfram Alpha.

When making computations modulo a large number, one does not first make the whole computation in $\mathbb{N}$ and then take the remainder of the result, because for something like an exponentiation the intermediate result would be exceedingly large. Rather, the result is calculated with reductions modulo $n$ at each step. The basic idea for exponentiation is to write down the exponent $d$ in binary, and proceed one digit at a time, with the rules
$$ \begin{align*}
  x^{2d} &= (x^d)^2 & \text{adding a binary digit \(0\) to the right of \(d\)} \\
  x^{2d+1} &= (x^d)^2 \cdot x & \text{adding a binary digit \(1\) to the right of \(d\)} \\
\end{align*} $$
All computations are multiplications modulo $n$, it is never necessary to make computations involving larger numbers. There are variations on this algorithm, including iterating over the digits of $d$ from right to left instead of left to right. The number of multiplications is at most twice the number of digits of $d$.

There are techniques to perform a multiplication $a \cdot b \pmod n$ without calculating $a \cdot b$ which could be as large as $(n-1)^2$, the most popular being Montgomery reduction. Multiplication modulo $n$ can be done in time $O(\ell^2)$ where $\ell$ is the number of digits of $n$; it follows that exponentiation modulo $n$ can be done in time $O(\ell^3)$.

You can easily verify whether the value of $F(m)$ computed by Wolfram Alpha satisfies the equation $F(m)^d \equiv m \pmod n$ by running the modular exponentiation algorithm. (Easily with a computer, not by hand, for numbers of this size.)

We've seen how to compute $m^d \pmod n$ knowing $m$, $d$ and $n$. Solving the equation $F(m)^d = m \pmod n$ where $F(m)$ is the unknown is a different matter. Computing the $d$th root modulo $n$ is a hard problem in general, for which the only known methods are exponential in $\ell$ in the worst case. The problem is tractable (i.e. has polynomial complexity) when $n$ is prime, or more generally given a factorization of $n$.

It is apparent given the notations and the value of $e$ that these numbers are an example of an RSA key pair. An RSA key pair is generated starting with a number $n$ of the form $n = p \cdot q$ where $p$ and $q$ are (probable) primes and with a number $e$ satisfying certain conditions that I won't go into here; the knowledge of the factorization of $n$ makes it easy to compute a number $d$ such that $\forall m, (m^d)^e \equiv m \pmod n$ and $\forall m, (m^e)^d \equiv m \pmod n$. (If the factorization of $n$ was not known, then finding $d$ given $n$ and $e$ or equivalently finding $e$ given $n$ and $d$ would be a hard problem: it would be literally breaking the RSA cryptosystem.)

Given this supplementary knowledge, the $d$th root of $m$ modulo $n$ can be computed with a tractable operation: exponentiation. The solution $F(m)$ is $m^e \pmod n$.

The Python programming environment provides a convenient way of making calculations on large integers.

% python
Python 2.7.3 (default, Mar 13 2014, 11:03:55)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> m=112951412120151619251851615182016118201
>>> n=145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
>>> d=89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713
>>> e=65537
>>> pow(m,e,n)
141781201173392662619041096248902274075236734827860244551641082388116267289894721928886528279400665340976615948053755946789302972467196231829204061441862114262117040263042768989461016645192295451421289297123899909172989906731037919155114663997141846344255396618911673987467404521083471325973763420396488985050L
>>> pow(pow(m,e,n),d,n)
112951412120151619251851615182016118201L
>>> pow(pow(m,e,n),d,n) == m
True


The Ising Model and Computational Complexity I've been told recently that one can use the Ising model can find solutions to certain NP-hard problems, such as Clique, although it doesn't do so in polynomial time.

Googling gets a few Arxiv results but where might I find an introduction to this interesting relationship?

Finding the minimal energy configuration in the Ising model is NP-hard, and many problems can be directly reduced to it. For a list, including Karp's original 21 NP-hard problem see e.g. Ising formulations of many NP problems. The Ising model is also equivalent to unconstrained quadratic binary optimization which also can be used to model a large number of other NP-complete problems, see e.g. A unified modeling and solution framework for combinatorial optimization problems.


Finding median of three sorted array (the same length) I think about following problem:
There are given three sorted arrays $A,B,C$ (each of them is length $n$).
Every array has distinct elements.
Find median of union $A,B,C$.

I consider following approach:
Let's consider $A_i, B_i, C_i$, where $i=n/2$. There are six cases - but I consider only one (rest of them is analogous). Let $A_i\le B_i\le C_i$:
Now we may dispse $1/3$ elements - $A[1...n/2]$ and $C[n/2 + 1... n]$.
Unfortunately I can't estimate time of run this algorithm.
I should solve recusrion equality: $T(n) = T(2/3n) + 1$
$(T(0) = T(1) = 1$, but I can't.

I am thinking about better algorithm.  Can you suggest something ?

Edit
I am goint to say more about this algorithm. The key idea is using Divide and conquer method. In each step we may dispose $\frac{1}{3}$ elements.   Lets $i = n/2$.   Let suppose that $A_i \le B_i \le C_i$ (rest of cases is analogous). Look at example:

In every case I dispose $1/3$ elements and get smaller problem.

The recurrence relation can be solved as follows: for large $n$,

$$T(n) = T\left(\frac{2}{3}n\right) + 1 = T\left(\frac{2^{2}}{3^{2}}n\right) + 2 = \cdots = T\left(\left(\frac{2}{3}\right)^kn\right)+k$$

This iterative process ends when a $T(m)$ is called with $m \leq 1$. Now for what $k$ do we have $\frac{2^{k}}{3^{k}}n \leq 1$? It is $ ^{\frac{3}{2}}log(n)$. (verify this for yourself)

A good way to do this is using an insight from the $\texttt{MergeSort}$ algorithm. It sorts an algorithm by consequtively merging increasingly long sorted substrings. Here's how it goes: you keep three indices, say $i,j,k$, which start at $0$. You iterate them over the three arrays, each time incrementing the index which points to the highest value of its respective array, until you've encountered half of all elements, i.e. $i+j+k=\frac{3n}{2}$. When that has happened, you have encountered the median. Here's this algorithm as pseudocode:

$\texttt{TernaryMedian}(\texttt{array } A, \texttt{array } B, \texttt{array } C):$

int $i, j, k :=0$

while $i+j+k < \frac{3n}{2}$ do

$\quad$ if $A_i > B_j$ then

$\quad\quad$ if $A_i > C_k$ then $i := i + 1$

$\quad\quad$ else $k := k + 1$

$\quad$ else if $B_j > C_k$ then $j := j + 1$

$\quad$ else $k := k + 1$

end while

$median := max(A_i, B_j, C_k)$

This algorithm runs in time $O(n)$ and makes $3n$ comparisons in the best case and $\frac{9}{2}n$ comparisons in the worst; I'll leave the average case to you. This algorithm can be improved if you keep a pointer to the array containing the highest value of any of the pointers but which was not the subject of last iteration's increment. I'll leave it up to you to figure out why. Then you get $\frac{3}{2}n+1$ comparisons in the best case and $3n$ comparisons in the worst.

It may help to first look up $\texttt{MergeSort}$ on Wikipedia for merging two substrings, and then think about how you would merge three substrings. Hope this helps.


Neural Networks: Simulate the working of Dynamic Fixed Point representation of the weights on hardware I am looking to implement a neural network on hardware using Verilog. I have completed and tested with floating point representation and a 20 bit fixed point representation. I want to further reduce the memory utilisation by using dynamic fixed point. I want to identify the less important weights, and assign them a smaller bit-width, while keeping the more important weights with a higher bit-length.
How can I identify the more/less important weights?
What I can think of is, reducing bit-width for all the small weights [-0.001, 0.001]. But isn't that like pruning?
Thanks!

Start by reading the research literature on this topic.  There's a large number of published papers that discuss how to quantize the weights or intermediate values used in deep learning.  For instance, here are a few papers:

https://arxiv.org/abs/1412.7024, https://arxiv.org/abs/1605.06402, https://arxiv.org/abs/1612.01064, https://arxiv.org/abs/1701.08978

Start by reading them, and do a literature search to identify other relevant papers (e.g., read their related work section and find other earlier papers that are relevant; find papers that cite them using Google Scholar and read them; repeat).

You might also look at the Ristretto tool and this project.


Hash table collisions: why use a linked list if we can use a hash set? One way to deal with the problem of collisions for a hash table is to have a linked list for each bucket. But then the lookup time is no longer constant. Why not use a hash set instead of a linked list? The lookup time would then be constant. For example, in C++ the hash table could be defined as:

unordered_map<int, unordered_set<int>> m;

An hash set is an hash table.  Using an hash set to handle collisions in an hash table is equivalent to using a bigger hash table, with an hashing function which is a combination of the hashing functions of both level.

In other words, you'd probably be better with a bigger initial table (for instance there is no risk of resonance between the two hash functions which could lead to an higher collision rate than expected at the second level).


P reduction between np-complete to np-complete given 2 lagnauges A,B which are npc.
is there a reduction function from A to B $A \leq_PB$ ?

my idea was to say that since they are decideable,
we can do this:
$$
f(x) = \begin{cases} y \in B & \text{ } if x \in A \\y \notin B & \text{if }x \notin A.\end{cases}
$$

is this is correct? or its not something that can be true? / depands on p equal or not equal to np

Hint: What is the definition of "NP-complete"?


What does "If P1 is reduced to P2, then P2 is at least as hard as P1" mean? I am having trouble understanding the following statement regarding Turing reduction:

"If P1 is reduced to P2, then P2 is at least as hard as P1."

Does this mean that
(i) P2 can be harder or as hard as P1, or
(ii) P2 can be easier or as hard as P1?
To represent this visually...

I would appreciate any insight on the matter. Thank you.

Interpretation (i) is correct: "$A$ is at least as hard as $B$" means that $A$ is as hard as or strictly harder than $B$. (Think about numbers: "$a$ is at least as big as $b$" means "$a=b$ or $a>b$.")
Note that not only does "$A$ is at least as hard as $B$" rule out $A$ being strictly weaker than $B$, it also rules out $A$ and $B$ being of incomparable complexity. Complexity isn't a linear order; we can find problems such that neither helps us solve the other.


Proper terminology in Prolog/logical programming theory? I have a good understanding of how to program using logic languages, but I'm currently writing up a paper describing some of my work, and I wanted to ensure that I wasn't abusing the proper terminology when describing logic languages. I have a few questions:

What exactly is a predicate? How does a predicate relate to rules/facts? I.e. are rules predicates but not all predicates facts and rules?
What is a clause, and how does it relate to a predicate?
When describing how a rule is tested/proven, what is the equivalent term for "calling a function"? Do we say that the rule is called, or that a goal is called?
What exactly is a goal? Is a goal equivalent to a query?

Like I said, I have a very good understanding of how Prolog works, just not a good knowledge of the right terms to describe the right things.

If you understand Prolog then you're probably fine. The jargon in Prolog-land is not as fixed as you'd expect, because we really only have three things to refer to, with a dozen or more pieces of jargon to use on. These are my working definitions arrived at from reading books and reading/answering questions about Prolog on Stack Overflow. I may have a misconception in here.

This is a Horn clause:

foo(X) :- bar(X).

It has two components: the head, which is foo(X), and the body, which is bar(Y).

A fact is a Horn clause consisting of just a head:

uncle(bob).

In ISO Prolog, this is transformed into the equivalent clause:

uncle(bob) :- true.

Similarly, a Horn clause with only a body is just a goal or a query:

:- uncle(X).

A predicate is defined by a set of clauses. For instance:

foo(true).
foo(X) :- bar(X).
foo(X) :- succ(X0, X).

The predicate foo/1 is thus defined. The 1 there is the arity. Every clause is a rule. I can talk about a bug in the second rule of the predicate or the second clause of the predicate, and in either case I am clearly referring to foo(X) :- bar(X).

"Goal" and "query" can be used interchangeably. You can prove or call a goal. I would "issue" a query, not sure if others would say that. When a Variable is given a value, I would say the variable unifies with value or the variable receives value. A goal, query or call can succeed or fail (not "return true" or "return false"). When it succeeds, its variables will be bound.

So to answer your questions directly:

A predicate is a unit of code with a name and arity. Its definition is composed of one or more clauses. Each clause can be a rule or a fact, but that distinction is trivial and fairly useless. A predicate is made up of facts and rules. Every fact and every rule is a clause and implies a predicate.
Every clause is an alternative of some predicate. Every predicate has at least one clause.
Predicates can be called. Goals can be proven or called. Queries can be satisfied. Rules are not called (instead, they are chosen out of the set of alternatives while evaluating some query). (foo(X), bar(X)) is a compound goal, more likely called a query (but never called a predicate).
Goal and query are the same.

This is confusing in Prolog because the same syntax is used everywhere. So when you see foo(X), it might be a fact, or it might be a query. It can be given to a meta-predicate to be proven or it can be used simply as a structure. For instance:

foo(X).           % 1. "fact": foo(X) always succeeds.
foo(X) :- true.   % 2. "predicate", same as above
:- foo(X).        % 3. goal: prove foo(X). Will succeed without establishing binding.
:- call(foo(X)).  % 4. goal, same as above
:- write(foo(X)). % 5. struct: print out "foo(_G1657)" (or some other gensym variable name)

For me, what's still vague is when we refer to a term as a structure versus as a functor. I think these usages are basically interchangeable, but I'm not sure.


Numbering of computable functions Is there a numbering (not Gödel numbering) of all computable functions $U(p, x)$, such that the set of numbers of functions defined in zero is exactly the set of even numbers. More formally: $I = \{p,\ |\ U(p, 0)\  \mathrm{defined}\} = 2\mathbb{N}$.

My guess that it's true. But I'm not sure how to prove it.

Ideas:

We can construct a numbering of all computable functions, defined in zero using the function $F(p, x, t)$ which is equal to $0$ if $U(p, x)$ hasn't finished work in $t$ steps and $1$ in other case. We can do it because set of pairs $(p, t)$ is enumerable.

Then, having this function $V(p, x)$ and some other numbering $U(p, x)$ we can construct numbering

$$
U'(p, x) =
\begin{cases}
V(\frac{p}{2}, x)\ \ if\ p \vdots 2\\
U(\frac{p + 1}{2}, x)\ \ if\ p \not\vdots 2
\end{cases}
$$

Hint:

There are countably many computable functions defined at zero, and countably many computable functions undefined at zero.
There are countably many natural numbers divisible by 2, and countably many natural numbers not divisible by 2.

Put the two facts together.


Path in a vertex-weighted undirected graph Is it an $NP$-hard problem?

You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$.

Does there exists a path in $G$ with total weight $W$ that does not visit any vertex $v$ more than $\mathrm{max}$-$\mathrm{visit}(v)$ times?

So this is a simple solution to this question. Given an instance of Hamiltonian path problem $G(V, E)$. Just set $w$ and $\mathrm{max-visit}$ to be equal to $1$ everywhere and $W=|V|$. A path in $G$ satisfies the requirements in our problem now corresponds to a Hamiltonian path in the original instance, and vice versa.


Why is the object destructor paradigm in garbage collected languages pervasively absent? Looking for insight into decisions around garbage collected language design. Perhaps a language expert could enlighten me? I come from a C++ background, so this area is baffling to me.

It seems nearly all modern garbage collected languages with OOPy object support like Ruby, Javascript/ES6/ES7, Actionscript, Lua, etc. completely omit the destructor/finalize paradigm. Python seems to be the only one with its class __del__() method. Why is this? Are there functional/theoretical limitations within languages with automatic garbage collection which prevent effective implementations of a destructor/finalize method on objects?

I find it extremely lacking that these languages consider memory as the only resource worth managing. What about sockets, file handles, application states? Without the ability to implement custom logic to clean up non-memory resources and states on object finalization, I'm required to litter my application with custom myObject.destroy() style calls, placing the cleanup logic outside my "class", breaking attempted encapsulation, and relegating my application to resource leaks due to human error rather than automatically being handled by the gc.

What are the language design decisions which lead to these languages not having any way to execute custom logic on object disposal? I have to imagine there is a good reason. I'd like to better understand the technical and theoretical decisions that resulted in these languages not having support for object destruction/finalization.

Update:

Perhaps a better way to phrase my question:

Why would a language have the built-in concept of object instances with class or class-like structures along with custom instantiation (constructors), yet completely omit the destruction/finalize functionality? Languages which offer automatic garbage collection seem to be prime candidates to support object destruction/finalization as they know with 100% certainty when an object is no longer in use. Yet most of those languages do not support it.

I don't think it's a case where the destructor may never get called, as that would be a core memory leak, which gcs are designed to avoid. I could see a possible argument being that the destructor/finalizer may not get called until some indeterminate time in the future, but that didn't stop Java or Python from supporting the functionality.

What are the core language design reasons to not support any form of object finalization?

The pattern you're talking about, where objects know how to clean their resources up, falls into three relevant categories.  Let's not conflate destructors with finalizers - only one is related to garbage collection:

The finalizer pattern: cleanup method declared automatically, defined by programmer, called automatically.
Finalizers are called automatically before deallocation by a garbage collector.  The term applies if the garbage collection algorithm employed can determine object life cycles.

The destructor pattern: cleanup method declared automatically, defined by programmer, called automatically only sometimes.
Destructors can be called automatically for stack-allocated objects (because object lifetime is deterministic), but must be explicitly called on all possible execution paths for heap-allocated objects (because object lifetime is nondeterministic).

The disposer pattern: cleanup method declared, defined, and called by programmer.
Programmers make a disposal method and call it themselves - this is where your custom myObject.destroy() method falls.  If disposal is absolutely required, then disposers must be called on all possible execution paths.

Finalizers are the droids you're looking for.
The finalizer pattern (the pattern your question is asking about) is the mechanism for associating objects with system resources (sockets, file descriptors, etc.) for mutual reclamation by a garbage collector. But, finalizers are fundamentally at the mercy of the garbage collection algorithm in use.
Consider this assumption of yours:

Languages which offer automatic garbage collection ... know with 100% certainty when an object is no longer in use.

Technically false (thank you, @babou).  Garbage collection is fundamentally about memory, not objects.  If or when a collection algorithm realizes an object's memory is no longer in use depends on the algorithm and (possibly) how your objects refer to each other.  Let's talk about two types of runtime garbage collectors.  There are lots of ways to alter and augment these to basic techniques:

Tracing GC.  These trace memory, not objects.  Unless augmented to do so, they don't maintain back references to objects from memory.  Unless augmented, these GCs won't know when an object can be finalized, even if they know when its memory is unreachable.  Hence, finalizer calls aren't guaranteed.

Reference Counting GC. These use objects to track memory.  They model object reachability with a directed graph of references.  If there is a cycle in your object reference graph, then all objects in the cycle will never have their finalizer called (until program termination, obviously).  Again, finalizer calls are not guaranteed.

TLDR
Garbage collection is difficult and diverse.  A finalizer call cannot be guaranteed before program termination.


Cracking code with clues I am trying to solve this code cracking problem. The solution is either the code or all possible solutions if you can't narrow the possibilities.

We have a 5 character code that is consisting of digits {0,1, ..., 7}. We have 10 attempts and for each attempt we have the amount of correctly guessed digits on the right indexes, and the number of correctly guessed digits on an incorrect index.

What I did what to generate all 5 digit numbers consisting of digits {0,1, ..., 7}., however I failed to find any way to narrow the attempts down. Could you help me find the right algorithm? Thanks!

Your problem is a variant of Mastermind. In particular, it is "Super Mastermind". Wikipedia contains some relevant pointers, and you can find many more by searching for Super Mastermind. For example, Temporel and Kovacs describes a heuristic algorithm that solves Super Mastermind using roughly 5–7 guesses. The same work also contains pointers to other algorithms.


Why is the language of TMs that have some quadratic time bound undecidable? The language in question is $L = \{M : M \text{ is a Turing machine that halts in } 100n^2 + 200 \text{ time}\}$.

Attempt 1

Suppose $L$ is decidable. Let $M_1, M_2, \ldots$ be the Turing machines in $L$. Now construct a new Turing machine $M$ that works as follows:

on input of length $n$ run $M_n$ and output the opposite answer

On the one hand, $M \in L$ since it halts in the appropriate time. On the other hand, $M \notin L$ because it is different from every machine in $L$. Therefore $L$ is undecidable.

Is this correct?

Something that bothers me: I think I am only using the fact that there are countably many Turing machines; I never used the fact that there is some TM that decides $L$.

Attempt 2

As suggested, here's a new Turing machine $M'$:

M'(M,x,1^n):
    if M is not a valid Turing machine then halt
    otherwise
        run M(x) for 100n^2+200 steps
        if it halts, then run forever
        otherwise halt

Ask oracle: does $M'(M,x, 1^n)$ halt on all inputs within $100n^2+200$ steps?

If yes, then $M$ doesn't halt on input $x$.

If no, then some input causes it to loop forever, which means $M$ halted on $x$ in a certain amount of time.

This would allow us to decide the halting problem, which we know is undecidable.

Is this correct? If so, I still think of the details are a bit fuzzy... For example, it's a bit unclear to me as to what happens with the inputs $M$ and $x$ are very large...

The fundamental reason for this is because your function $100n^2+200$ is $\Omega(n)$. Additionally, this result holds for any function $f\in\Omega(n)$.

Your problem is that you can't just "run $M_n$". It's possible to describe a turing machine that runs a specific machine, but to have the turing machine depend on the input requires that you actually compute the machine you're using. This is actually equivalent to the negation of what you are trying to prove, and additionally makes $M$ take longer so that it won't halt in the correct amount of time in the case that $M_n$ does even if you had an algorithm to find $M_n$.

Assuming you are using $M$ in your second attempt as a general TM rather than the one for attempt one, then the problem here is the same (except it's caused by the fact that the machine has to use some extra time to compute which step it's one rather than compute the machine it will simulate). Normally, this problem wouldn't come into play if you do $O(f(n))$ analysis because your new TM $M'$ would still run within a constant time factor of the old one, but in your problem you have to be a bit more clever.

If you know a bit of complexity theory, you can do that by using the linear speedup theorem, which basically says that given a TM which runs in at least linear time $f(n)$ you can create one with a constant factor $r>0$ as small as you'd like that runs in time $r\cdot f(n)$. The drawback is that the tape input is no longer just $0$'s and $1$'s but will also include some added symbols, but the same methods can prove this for any $f\in\Omega(n)$, so it's still a pretty neat result.


How many snakes there can be in the "snakes and ladders" game? How to calculate the maximum allowed number of snakes in the game of "snakes and ladders" from mathematical/algorithmic point of view assuming that there is a nxn board?

UPD: My thoughts are simple, but they might be incorrect:
I suppose once any two fields on the board cannot be involved twice forming a snake it means that in nxn board there can be nxn/2 snakes

If we assume any given square can be the head or tail (but not both) of at most one snake then clearly an upper limit on the number of snakes on a $n \times n$ board is $\frac {n^2} 2$. For a $m \times n$ board we can generalise this to $\frac {mn} 2$. And we can reach this upper limit if either $m$ or $n$ is even. What happens if $m$ and $n$ are both odd ?


Compression functions are only practical because "The bit strings which occur in practice are far from random"? I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question.

Andrej explains that given the set of all bit strings of length 3 or less, a lossless compression function can only "compress" some of them. The others, for instance "01" would have to actually be compressed to a string such as "0001", with length 4. The compression ratio is simply the average compression across the input set.

This makes lossless compression seem impractical, but the important quote is this:

  The bit strings which occur in practice are far from random and exhibit a lot of regularity.

I have a hard time believing that, for instance, multimedia files are represented by anything other than random bit strings. Is there truly a pattern that compression functions leverage to make the algorithm useful in reality?

First of all, you're right: Multimedia files are represented (more or less) as random files. The reason for that is that those files are already compressed (lossy). Note that mp3, for example, is nothing but a compression algorithm!
A consequence is that further compression will not yield any noticeable compression (and indeed, lossless compression on already compressed (multimedia) files has never been a road to success).

You're also right on your other point: Lossless compression cannot compress on the average. To see that, say, your possible data set consists of $2^n$ different elements. How many bits do you need per file to always be able to distinguish elements from your set? Right, $n$. In total all files will be represented by no less than $n \cdot 2^n$ bits. Now if you represent some of those files by less than $n$ bits, some files will be represented by more than $n$ bits. That's about all there is to say.

In short, lossless compression works because text files are far from random (just consider the letter distribution of my answer and compare the number of e's with the number of z's!), and compressing random data (e.g. already compressed data or encrypted data) does not make any sense.


Complexity of pattern matching for modus ponens logical conclusions Is a Turing machine with added the following contant-time operation equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) to a (usual) Turing machine:
By predicates I will mean predicates in first-order predicate calculus. (Note that predicates may have free variables.)

constant-time modus-ponens resolution (yes or no) and then adding $y$ to the end of this array if yes, for given predicates $x$ and $y$ and an array (or a linked list) of predicates. By definition of modus ponens, it's yes, if and only if some element of the arrays is $X\Rightarrow y$ where $X$ is a pattern matching $x$.

Remark: The above operation is a part of the standard procedure of proof-checking is first-order predicate logic.
If the above hypothesis is false, then what is the running time upped bounds of the above operation in different kinds of Turning machine equivalents (such as Turing machine, Markov algorithms, von Neumann architecture with infinitely many infinitely big words of memory, etc.)?
BTW, is von Neumann architecture with infinitely many infinitely big words of memory a Turning machine equivalent? (I think yes, but not 100% sure.)

This boils down to the question of whether there exists a polynomial-time algorithm for your matching operation.
If there exists such an algorithm, call it $A$, then the answer to your question is yes: given an augmented Turing machine that uses these operations, you can convert it to an ordinary Turing machine by simulating those operations using $A$.  This blows up the running time by at most a polynomial.  (Invoking a polynomial-time subroutine at most polynomially many times leaves with a running time that remains polynomial.)
If there is no such algorithm, then the answer to your question is no: the matching problem can be solved in polynomial time (indeed, constant time) on an augmented Turing machine, but cannot be solved in polynomial time on an ordinary Turing machine.
I'm not clear on the definition of your matching operation, and I'm not an expert in computational logic, so I don't know what is the computational complexity of the matching operation you have in mind.


constructing a DFA and a regular expression for a given regular language This is the question 1.12 from Introduction to the Theory of Computation 3rd Edition by Michael Sipser. The questions says,

  Let $D=\{w\mid w$ contains an even number of $\texttt{a}$'s and an odd
  number of $\texttt{b}$'s and does not contain the substring
  $\texttt{ab}$}. Give a DFA with five states that recognizes $D$ and a
  regular expression that generates $D$.

I was able to construct a  by using the intersection operation on the three simpler parts of $D$. I think that the regular expression that would generate $D$ is b(bb)*(aa)* but I'm not sure about it.

Is my regular expression correct? If yes, then if I apply the subset construction algorithm on  diagram (eps denotes ε) and minimize the resultant DFA, I should get the minimal DFA that I constructed through intersection, right?

I was able to solve this question using two possible routes.

The 1st route involves constructing the DFA by using the intersection operation on the simpler parts of $D$, i.e.,

$\{$even number of $a$'s$\} \cap\{$odd number of $b$'s$\}\cap\{$does not contain the substring $ab\}$

After that, I was able to reduce the DFA into a RegEx using the State Elimination Method and Arden's Lemma. The regular expression can be achieved by using Arden's Lemma as follows.

$$1\to a2+b4$$

$$2\to a2+b2$$

$$3\to a5+b2+\varepsilon$$

$$4\to a5+b1+\varepsilon$$

$$5\to a3+b2$$

Note that $2\to a2+b2$ will resolve as $2\to \varnothing$ and not $2\to (a+b)^*$.

The 2nd route involves "knowing" that the regular expression is $b(bb)^*(aa)^*$ by analyzing the language $D$. This RegEx can be converted to an ε-NFA. After that, we can convert this ε-NFA to get a DFA which when minimized would give us this.


Finding the path of a negative weight cycle using Bellman-Ford I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, which path do I actually trace to get to the original vertex having traveled a negative amount.

So to be clear say I have a graph with vertexes, a, b, c, and d and there is a negative cycle between a, b, and d, then when I check for negative weight cycles

// Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           "Graph contains a negative-weight cycle"

Instead of it just telling me that a negative cycle is there, I would like it to tell me, go from a -> b -> d -> a.  After the relaxing step what do I have to change in my check for negative weight cycles to get it to output this information?

Here is the best information I've been able to find, but I'm still having trouble making sense of it.
Also this which suggests that I need to run breadth first search on the predecessor array to find the information, but I'm not exactly sure where to start (what do I queue first?)
Here is a stack overflow question which shows how to find one of the nodes in the path.

Per Kleinberg–Tardos, you want to run Bellman–Ford for n iterations and find a cycle in the predecessor array.

To find a cycle in the predecessor array, start by coloring every node white. For each node u in an arbitrary order, set v := u, and, while v is white and has a predecessor, recolor v gray and set v := predecessor[v]. Upon exiting the loop, if v is gray, we found a cycle; loop through again to read it off. Otherwise, none of the gray nodes are involved in a cycle; loop through again to recolor them black.


Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method I'm trying to solve this recurrence. I applied the iterative method:
$$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum_{i=0}^{k-1}(n-2i)^2$$ So $n-2k=1$ when $n=2k+1$ and we have: $$\sum_{i=0}^{(n-3)/2}(n-2i)^2$$ Now how can I demonstrate that this series is $\Theta(n^3)$?


The number of connected components in the context of cyclomatic complexity Cyclomatic Complexity is defined with reference to the control flow graph of the program through this formula (borrowed from Wikipedia):
M = E − N + 2P,
where
E = the number of edges of the graph.
N = the number of nodes of the graph.
P = the number of connected components.

I can't understand the last. What is "the number of connected components" in this context? Wikipedia itself uses the notion of (connected) components in relation to undirected graphs only.
There is also the concept of strongly connected component: a directed graph is said to be strongly connected if every vertex is reachable from every other vertex. So one can guess that the number of connected components is the number of strongly connected components of the control flow graph. Is it right? If not, can someone provide samples of control flow graphs with differerent numbers of connected components?

When they say connected component, they mean a weakly connected component. Take a look at the third formula they provide in the Wiki.

For a single program (or subroutine or method), P is always equal to 1. So a simpler formula for a single subroutine is M = E − N + 2.

This implies that for $P > 1$ is used for multiple programs. In other words, it is used for programs with multiple start points with distinct end points.
So for the first formula, it takes in consideration of multiple programs, subroutines, or methods that are completely disconnected from each other (i.e. they do not call upon or interfere with each other) in a single program control graph.
The following is an example where the first formula would be applied. Here $M = 9 - 8 + 2*2 = 5$.


How to evaluate the clock cycle for MIPS single cycle CPU The Situation

I'm trying to read the book 'Digital Design Computer Architecture'.
In the part of Performance Analysis(7.3.4 in the book), Author refers to clock cycle for MIPS single cycle processor. But I think there's something wrong with author's evaluating clock cycle.

Author says,

T(Clock cycle) = T(pcq_pc) + T(mem) + Max[tRfread, t(sext)] + t(Mux)
                 + T(ALU) + T(mem) + t(mux) + T(RFsetup)

But I think clock cycle 'T' would be ( if T(RFread) > T(mux) + T(sext) )

T(Clock cycle) = T(pcq_pc) + T(mem) + T(RFread) + T(ALU) + T(mem) + T(mux) + T(Rfsetup)

Since I think the MUX followed by ALU already selects known sign-extend immediate before register value(the pin RD1 in below diagram) is known.

and if T(RFread) is less than T(mux) plus T(sext).

T(Clock cycle) = T(pcq_pc) + T(mem) + T(sext) + T(Mux)
                 + T(ALU) + T(mem) + T(mux) + T(RFsetup)

Some referenced information by the book.

T(pcq_pc) is propagation delay for PC.
T(mem) is read-propagation delay for instruction memory and data memory.
T(sext) is propagation delay for Sign Extend logic.
T(RFread) is read-progagation delay for register file.
T(mux) is propagation delay for MUX.
T(ALU) is propagation delay for ALU.
T(RFsetup) is setup time for Register file.(Register value is written on positive clock edge)

Here is Diagram for MIPS single cycle CPU.

Is my thought correct? If you think author is right, Could you tell my why?
Any help would be awesome!

Now that you have (dramatically) modified your question:

The author of the book is correct.  RD1 can not be on the critical path because the time to read RD1 is the same as the time to read RD2, but then RD2 needs to go through the mux in front of the ALU.  If the time to read RD2 > T(Sext) then RD2 is on the critical path, if T(Sext) > T(RFread) then Sext is on the critical path.  That's what the Max() operator does.  Either way T(mux) needs to be in the expression.

Your last expression with T(Sext) +T(mux) is the same as what the author's expression gives in the case that T(Sext) > T(RFread).  But your middle expression is wrong: if T(RFread (the read of RD1)) > T(Sext) + T(mux) then T(RFread (the read of RD2)) + T(mux) > T(Sext) + T(mux) + T(mux) > T(Sext) + T(mux).  So you need to have T(mux) in the expression no matter which T(RFread) or T(Sext) is larger.

The basic rule (which you are mostly correctly following) is: use Max() for things that proceed in parallel, + for things that follow in sequence.  The mux comes after both the Sign extend and after the read of RD2.


Variant of an approximation algorithm for vertex cover Here is an approximation algorithm that finds vertex cover of a graph.

 C = {}
 E' = {Edge set}
 while E' =/ 0
   Let (u,v) be an arbitrarily edge of E'
    C = C U {u,v}
    remove E' incident on u and v.
return C

A variant: what if instead of removing edges incident on both $u$ and $v$, we removed only $u$. Would this affect the optimal vertex cover? If so, how?

I somehow feel the optimal vertex cover remains the same whereas only the number of steps to remove the edges would increase increasing time and space complexity. Am I right?

Consider a star consisting of a center $x$ connected to the vertices $y_1,\ldots,y_n$.
Your modified algorithm could act as follows:

Choose the edge $(x,y_1)$; add $x,y_1$ to the vertex cover; remove all edges incident to $y_1$.
Choose the edge $(x,y_2)$; add $x,y_2$ to the vertex cover; remove all edges incident to $y_2$.
...

I'll let you take it from here.


Models of computation: the arithmetic model, Turing machine (and ...) How is an arithmetic model defined?

What relations are between it and Turing machine? Are they equivalent in some sense?

Is it true that

in the arithmetic model of computation, the basic arithmetic operations (addition, subtraction, multiplication, division, and
comparison) take a constant unit time step to perform, regardless of
the sizes of the operands.
in the Turing machine, the time each operation takes will depends on the storage size of the operands?

What is the point of having these two different computational models?
Are there other models of computation distinct from the Turing
machine and the arithmetic model?
There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic
model. The
Euclidean algorithm for computing the greatest common divisor of two
integers is one example.

If an algorithm runs in polynomial time in the Turing machine, will
it run in polynomial time in the arithmetic model?
Is an algorithm running in polynomial storage space defined the same under the Turing machine and the arithmetic model?

Thanks and regards!

3. There are algorithms which run in polynomial time in the Turing machine model, but not in the arithmetic model. The Euclidean algorithm for computing the greatest common divisor of two integers is one example. If an algorithm runs in polynomial time in the Turing machine, will it run in polynomial time in the arithmetic model?

Polynomial TM running time does not imply polynomial arithmetic running time, nor vice-a-versa.

The issue in the above question lies in the definition of the running time that we are trying to bound. If we expand, we have to say: "...runs (or doesn't run) in the number of steps that is polynomial in the length of encoded input". The catch is that the "steps" and "length of encoded input" are defined differently for the two models.

For a Turing Machine, the encoded input is taken as some concatenation of the binary representations of the input integers with separators. A step is an action of the TM head.
For an arithmetic model, the length of encoded input is defined as the number of numbers occurring in the input. A step is an arithmetic operation.

1. "Polynomial time under TM, but not under AM"

Euclid's GCD is indeed an example. For $a,b, a>b$, input integers, regardless of the model the algorithm takes $O(\log b)$ iterations, with a division at each iteration.

TM: Length of encoded input is then $l_{TM} = 2\log a + 1$ where $a$ is the larger of the two integers. The division in a TM takes $O(\log^2 a)$ steps. Hence, the total number of TM steps is $O(\log^2 a\log b)=O(l_{TM}^3)$ (conservatively speaking). That is, the polynomial $P_{TM}(l_{TM})=l_{TM}^3$ in the length of encoded input bounds the TM running time.
AM: Length of encoded input is constant $l_{AM}=2$. The number of steps is equal to the number of divisions $O(\log b)$. Since the value of any polynomial $P(l_{AM})$ is constant, for any choice of $P(l_{AM})$ we can always find a problem instance that takes more divisions than $P(l_{AM})$. That is, we cannot bound the running time with a polynomial in the length of encoded input.

2. "Polynomial time under AM, but not under TM"

One example is the algorithm that computes $2^{2^n}$ using repeated-squaring where $n$ is given as input in unary encoding (and we treat each unary "tick" as an input number). For both models, input length is $n$ and we need $\log 2^n = n$ multiplications and each multiplication will eventually be multiplying $2^n$-bit numbers.

AM: $P(n)=n$ is a polynomial bound on the number of arithmetic operations
TM: $O(n2^{2n})$ steps, since each $2^n$-bit multiplication takes $O(2^{2n})$

Drawn from a reading of Wikipedia's primary source (and corrected Wikipedia accordingly):

[1] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.


Giving a regular expression for a situation of a question I have the following question regarding a situation given and we are then required to derive a regular expression out of it.

What i have to do now i to give a regular expression for this language described by the knob movement from A,B and C. Because i have to go through B if i were to traverse to C, and vice versa, i know that B must be present as part of the expression.

Here's what i attempted:

ABC U ABA U BAB U BCB U CBA U CBC

Simplifying it:

AB(C U A) U B(AB U CB) U CB(A U C)

I'm not entirely sure if I'm doing it right as I find out that I'm brute forcing. I'm terrible at deriving regular expressions so I'll appreciate some corrections.

Here's a rough sketch: let $S_a, S_b, S_c$ be the set of valid strings of the language starting with $a, b, c$ respectively. Observe that:

$\qquad S_b = ((a^* + c^*)b)^*$

Furthermore:

$\qquad S_a = aS_a + bS_b$

and symmetrically for $S_c$. Therefore we may replace $S_b$ in the latter, obtaining a "recursive" equation solvable by Arden's lemma.


Sampling Multiple Times From a Markov Chain In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. Lets fix some $\varepsilon\in (0,1]$ as our closeness parameter.

Now suppose that we have a Markov Chain M with mixing time T, and suppose that
we want to draw 10 independent samples from the stationary distribution of M. What is the correct way to do that?

Do we have to apply the Markov chain for $10\cdot T$ steps, and pick the
resulting states at time $T, 2T, ...,10T$ as my samples, or...
is it enough to apply the Markov chain for T+10 steps, and pick the    resulting states at time $T+1,T+2,...,T+10$ as my samples?

The justification for the first alternative is that once we have drawn a sample state $s$ at time $T$, then the immediate samples following $s$ will be correlated with $s$ according to the transition matrix of the chain.

On the other hand, maybe it is possible to use some property about Markov chains to show that alternative 2 is enough? For instance, by arguing that the distribution at time T+i is close to uniform with respect to the initial state anyways. This leads to question 3 below...

3) Is there some class of Markov chains for which alternative 2 is enough?

One correct way is to repeat the following 10 times: pick a random starting state, and apply the Markov chain for $T$ steps.

I don't know whether your first proposal gives the correct distribution in all cases.  You can consider the Markov chain $A \leftarrow B \rightarrow C$ with self-loops $A \to A$ and $C \to C$ and more complicated examples in that vein.

Your second proposal doesn't give the correct distribution.  The $T$th and $T+1$th state are highly correlated: for instance, they will always be adjacent -- something that wouldn't be true of 10 independent samples from the steady state distribution.


What is meant when we say that divergence is the only side-effect of the lambda-calculus? In the simply typed lambda-calculus, I was told that behavioral equivalence is taken in terms of divergence because "divergence is the only side-effect of such language".

How should I understand this quotation? What does it mean that divergence is a side-effect? Perhaps that it is a phenomenon that is not directly encoded in the evaluation rules? But then, how do we know there are no other kinds of side-effects?

I think it is better to speak of computational effects than side effects, as some of them are not really on the side but rather directly in your face.

Computational effects are aspects of a program which are not just "mathematical computing", i.e., not just internal processing of data: I/O, access to mutable memory, exceptions, etc. The notion is a bit open-ended and difficult to make completely precise (because people invent new ways of computing things -- in 1970 nobody would have thought to include quantum super-position into the list of possible side-effects). Nevertheless, any sort of interaction between a program and the external environment is usually counted as a compuational effect.

Is program divergence, i.e., running forever, a side effects? In a sense it is, because it definitely is a form of "interaction" with the external environment, albeit a very annoying and useless one. Waiting forever to find out the result of a computation has several side effects, such as a high electricity bill, death of one's pets, and the thermal death of the universe. There are also deeper theoretical reasons why divergence should be counted as a side effect, but you did not explicitly ask about that.

You stated that the pure simply-typed $\lambda$-calculus has only one computational effect, namely divergence. But this is not the case! In the simply-typed $\lambda$-calculus every program terminates! You have to pass to the untyped $\lambda$-calculus to get divergence.

You also ask how to implement computational effects in $\lambda$-calculus. There are two ways:

You can extend the calculus with new primitives, for example primitive operations print, read, etc. You then have to give an operational account of what these operations do. ML-style languages do this.
You can simulate effects using the calculus. For example, instead of actually printing things, you can collect the things that would get printed in a list (suitably implemented in $\lambda$-calculus). Most effects can be simulated in such a way. In this approach your language is still pure, but your programs look like they are using computational effects. Haskell does this.


Bottleneck TSP with repeated nodes I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also NP-hard. However, I was not able to find a reference for the complexity of the bottleneck TSP problem with repeated nodes for complete graphs.
Also, I am curious if continuously removing the most costly edges until all nodes are not strongly connected actually solves this problem. I think that this method should solve this problem, but I was not sure about it.

The problem is in P.
You can solve the decision problem in $O(n^2)$ time, where $n$ is the number of vertices (i.e., linear time in the size of the input).  Delete all edge whose weight is above the bottleneck threshold.  Form the strongly connected components of the resulting graph, and examine its metagraph.  The original decision problem has a bottleneck TSP iff the metagraph is a simple path, i.e., it has the form $w_1 \to w_2 \to \dots \to w_k$ where $w_1,\dots,w_k$ are the components and the only edges are $w_i \to w_{i+1}$.
You can solve the optimization problem in $O(n^2 \log n)$ time.  Sort the set of edge weights, and remove duplicates.  Then, use binary search on this set of weights to find the smallest bottleneck threshold such that the decision problem has a solution.  You will do $O(\lg n)$ iterations, and each iteration runs the decision problem above, so the total running time is $O(n^2 \lg n)$.


Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes? When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set of functions
$$O(g(n))= \left\{ f(n):\text{ there exist positive constants }c\text{ and }n_0\text{ such that},\\ 0\leq f(n)\leq cg(n),\text{ for all }n\geq n_0 \right\}$$
This excerpt has been taken from introduction to algorithms 3rd edition. What I fail to understand is that how can algorithms with a linear runtime have an asymptotic upper bound when linear functions don't have asymptotes or is there a loophole in my thinking?

Word "asymptotic" is used to emphasize the condition $\exists n_0\in \mathbb{N}$ $\forall n> n_0$ for inequality $0\leqslant f(n)  \leqslant C g(n)$ and generally does not contain any mention of limit or asymptotic. Even well known definition of O big, using $\lim\sup \frac{f}{g}$, have sense only when limit point for O big is not limit point for $g$'s zeros.
As to linear function, for example $f(n)=an+b$, then it easy to find solution for $an+b \leqslant C n $ finding $C>a$ and taking $ n \geqslant n_0= \lfloor \frac{b}{C-a} \rfloor+1 >0$. So we obtain $f(n)=an+b \in O(n)$ i.e. linear function is O-big $n$.


How to write grammar production rules to describe recursive structures? I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $A$ made of elements of type $A$ or $B$.

Writing the grammar, I build this:

  $(S \rightarrow AS|ε)$
  $(A \rightarrow AA|bA|ε)$

where $b$ is a terminal representing element $B$ of my list.

The production $A \rightarrow AA$ got me a little baffled... is there something right? Thank you.

Yes, you can use context-free grammars to describe data structures, but only if the data structure is linear (e.g., a linked list of integers).  Context-free grammars are not well-suited for trees or graphs (for those, you need something more powerful).

There's nothing wrong with a production like $A \to AA$; that's a valid rule that can appear in a context-free grammar.


Counting $k$-Colorings $\mathcal{O}(\phi^{n + m})$ Solution Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, how many $k$-colorings of $G$ exist? A $k$-coloring is a function $c: V \to \{ 1, 2, \dots, k \}$ such that $c(u) \neq c(v)$ for all edges $\{ u, v \} \in E$. Let $f(G, k)$ denote the number of $k$-colorings of $G$.

There is a well-known formula, sometimes called Fundamental Reduction Theorem:

$\displaystyle f(G, k) = f(G - e, k) - f(G\,/\, e, k)$ for all $e \in E$.

Note that $G - e$ is $G$ without edge $e$ and $G\,/\,e$ is $G$ with edge $e$ contracted.

Using this formula, it is easy to figure out a recursive algorithm. We just need to choose an arbitrary edge and recurse on $G - e$ and $G\,/\, e$. The base case is a graph without edges. If $T(n + m)$ denotes the time complexity, we have $T(n + m) \le T(n + m - 1) + T(n + m - 2)$ which is just fibonacci recurrence and establishes a time complexity of $\mathcal{O}(\phi^{n + m})$ where $\displaystyle \phi = \frac{1 + \sqrt{5}}{2}$ denotes the golden ratio. So far, so good.

But we made an assumption: Can $G - e$ and $G\,/\,e$ really be obtained from $G$ in $\mathcal{O}(1)$ time? It seems like we cannot avoid a polynomial factor:

If $G$ is represented by an adjacency matrix, vertex removal (needed for contraction) does not shrink the matrix and we always need $\mathcal{O}(n)$ time to access the edges of a single vertex. And another problem: How to select an arbitrary edge fast?
If $G$ is represented by adjacency lists, edge removal is fast. But edge contraction requires moving/copying neighbour vertices to another adjacency lists which is expensive.
If $G$ is represented by an edge list, edge selecting is fast. Edge removal is also fast, because the edge is arbitrary and we can always take the first edge in the list. But again, edge contraction causes many edges to be updated (i.e. assigned another endpoint)...

Is there a way to really achieve $\mathcal{O}(\phi^{n + m})$ without a factor of $n$, $m$ or $n + m$ using an appropiate data structure or modification of the algorithm?

Use an adjacency list representation, together with a Union-Find data structure on the vertices.  Augment the Union-Find data structure so you can quickly enumerate the list of all edges incident on any vertex within a particular partition (you can keep track of them with a doubly linked list, and splice the lists together whenever you do a Union operation).  Now edge contraction can be done in $O(\alpha(n))$ time, by simply doing a Union operation on the two vertices.  Edge removal can be done in $O(1)$ time, due to the adjacency list representation.  You can also find an arbitrary edge in $O(1)$ time, thanks to the augmentation of the Union-Find data structure.

This avoids the factor of $n$.  You still pay a factor of $O(\alpha(n))$ instead of $O(1)$, but $O(\alpha(n))$ is so small that it might as well be $O(1)$ for all practical purposes, and in any case it is far smaller than $n$.

Actually, I think you pay more than that, because you'll need to undo the Union operations after returning from the recursive call.  To deal with that, you can use a persistent Union-Find data structure.  I'm not familiar with the asymptotic running time for those data structures, but I think given how it is used here it will be pretty close to as efficient as the plain Union-Find.

Usually we don't worry too much about polynomial factors when analyzing exponential-time algorithms, because the polynomial factor is tiny compared to the exponential factor, so a polynomial speedup won't change much in practice.  But here is a case where the polynomial speedup you desired can be achieved.


Is "Solving two-variable quadratic polynomials over the Integers" is an NP-Complete Problem? On this Wikipedia article, they claim that given $A, B, C \geq 0, \; \in \mathbb{Z}$, deciding whether there exist $x, \,y \geq 0, \, \in \mathbb{Z}$ such that $Ax^2+By-C=0$ is NP-complete?
Given by how easy I can solve some (with nothing but Wolfram), it doesn't seem right. I'm sure it's either written incorrectly or I'm just misunderstanding something.

As you noted, solving that Diophantine equation is not complicated, mathematically.
All is needed is to find the necessary remainders $r$ of $x$ modulo $B$ such that $Ax^2-C$ is a multiple of $B$, then all integer solutions are of the form $x=Bn+r$ and $y=(C-Ax^2)/B=(C-A(Bn+r)^2)/B$.
One way to find the remainders $r$ is to

factor $B=\prod_i q_i^{a_i}$, where $q_i$ are different primes,
solve the congruences $Ax^2-C\equiv 0\pmod{q_i}$, which in the worst case have two solutions $\pm t_i$,
lift these solutions to solutions $\pm\theta_i$ of $Ax^2-C\equiv 0\pmod{q_i^{a_i}}$ and
glue these solutions, using the Chinese Remainder Theorem to get a solution of $Ax^2-C\equiv0\pmod{B}$. Note all the $\pm$ choices.

Factoring $B$ is possibly hard, but maybe it isn't. My outdated knowledge is that nobody knows. Also maybe it is also possible to find the remainders $r$ without factoring $B$. What the proof that I saw exploits to conclude that the problem is NP-complete is the decision that still remains to be made.
The original decision problem becomes checking if one of the choices of $\pm$ is such that the interval $x\geq0$, in other words $n\geq -r/B$, intersects (and intersection contains an integer) the interval where $n$ is such that $y\geq0$. Compared to the bit size of $(A,B,C)$ there can be many remainders $r$ to test. I will not quantify this claim. Let the proof of its NP-completeness give evidence of it.
In Moore and Mertens' The Nature of Computation, section 5.4.4 there is a reduction (with parts left as exercises) of the SUBSET SUM decision problem to this decision problem (let's call it QDE).

Let me sketch their argument just to get a taste of how the input to SUBSET SUM is encoded in the input to QDE and how the choices of $\pm$ correspond to the subsets that one can consider in SUBSET SUM. Maybe I or someone else can expand the details later.
SUBSET SUM gets a set (or maybe a multi-set) $X=\{x_1,x_2,\ldots x_n\}\subset\mathbb{N}$ and $t\in \mathbb{N}$ and asks if there is a subset $Y\subset X$ such that the sum of its elements is $t$. If one defines $S=2t-\sum_{k=1}^{n}x_k$ then SUBSET SUM is equivalent to the existence of $\sigma_i\in\{-1,1\}$ such that $$S=\sum_{k=1}^{n}\sigma_kx_k$$

Here we have already choices of subsets encoded as choices of $\pm$.

Taking $m$ such that $2^m>\sum_{k=1}^{n}x_k$ this equation is equivalent to $$S\equiv \sum_{k=1}^{n}\sigma_kx_k\pmod{2^m}$$
If we choose $q_1,q_2,...,q_n$ relatively prime odd numbers (the first odd primes suffice), the Chinese Remainder theorem ensures that there are $\theta_1,\theta_2,\ldots,\theta_n$ such that
$$
\begin{align}
\theta_k&\equiv x_k\pmod{2^m}\\\
\theta_i&\equiv0\pmod{\prod_{k=1,k\neq i}^{n}q_k^m}\\\
\theta_k&\not\equiv0\pmod{q_k}
\end{align}
$$

The $\theta_i$ will be, for the QDE problem to be created, the solutions $\theta_i$ that we mentioned at the beginning.

The first group of these congruences imply that SUBSET SUM is equivalent to $$S\equiv \sum_{k=1}^{n}\sigma_k\theta_k\pmod{2^m}\qquad\qquad(*)$$

Now they build the quadratic equation, which solubility is equivalent to the solubility of this congruence.

They define $H=\sum_{k=1}^n\theta_k$ and $K=\prod_{k=1}^{n}q_k^m$. Observe that any $x$ of the form $$x=\sum_{k=1}^{n}\sigma_k\theta_k$$ satisfies $$H^2-x^2\equiv0\pmod{K}$$
Then, through a pair of exercises, they argue why there are choices for picking $q_i$ and a $\lambda_1$ large enough such that $2H<K$, and $|t|<H$, and ensuring that $(*)$ has a solution if and only if the Quadratic Diophantine Equation
$$\underbrace{(\lambda_12^{m+1}+K)}_{A}x^2+\underbrace{2^{m+1}K}_{B}y-\underbrace{(\lambda_12^{m+1}H^2-KS^2)}_C=0$$
has a solution $x,y\geq0$.
Notice how this equation re-writes as
$$\lambda_12^{m+1}(H^2-x^2)-K(S^2-x^2)=2^{m+1}Ky,$$
The choices made in the technical details are such that when there is a solution $x,y\geq0$ for this equation it is always the case that $H^2-x^2$ is already known to be a multiple of $K$ and $S^2-x^2=(S+x)(S-x)$ a multiple of $2^{m+1}$.


Average case complexity of bubble sort vs insertion sort This site already has some questions on this topic but I am confused after reading some of the answers.

Evaluating the average time complexity of a given bubblesort algorithm.

In the above link, answer by "Joe" says that number of swaps in bubble sort on average is same as number of inversions on average which is (n)(n-1) / 4.

However, https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms says that in bubble sort average number of swaps  is $n^2 / 2$ and in insertion sort it is $n^2 /4$ and that's the reason for insertion sort being better than bubble sort.

Which one is correct? Can someone please help me?

There is a big difference between the first answer you quote, on this site, and the second answer you quote, on stackoverflow: while the answer on cs.se contains an argument, the answer on stackoverflow just states the result without any explanation. This means that you can verify the answer on cs.se: you can check whether the proof is correct, and whether the result answers your question. In contrast, there is no way to know whether the answer on stackoverflow is correct or not, apart from trusting its poster.

This highlights a general difference between programmers and computer scientists. Programmers just want to know the answer, and generally don't care whether it's correct or not. Computer scientists, in contrast, want to see some evidence: a proof if one is available, or results of experiments (or both, in some communities).

Two more proofs of the formula $\frac{n(n-1)}{4}$ can be found on math.se and on cs.se. See if any of these convince you of this formula. You have to check both the statement (whether you are counting the correct expectation) and the proof.

Another thing you can do is experimentally determine the veracity of these proofs. This would entail programming both algorithms, and running them on many different arrays of length $n$ for various values of $n$, thus estimating the number of swaps.

A user on stackoverflow did a simpler experiment which suggests that the number of swaps is the same in bubble sort and inversion sort (at least for the user's version of these algorithms, quoted in the question). This would imply, of course, that the average number of swaps is the same in both algorithms.


What algorithm to use for this problem? I was recently faced with a hackerrank interview test where I couldn't solve the following problem correctly. I would not want to name the exact problem for privacy purposes, but I can tell that it was nowhere in Google with this name.

Problem

We want to organize an event with as much performers as possible. We are given a list of possible performer arrival times and performance durations. Our function should return the maximum number of performers that can be selected without conflicts.

Example

N = 5
arrivals = [1, 3, 3, 5, 7] (performers arrive in these times)
durations = [2, 2, 1, 2, 1] (the time needed to finish their performances)
solution = 4

So at time 1 we can accept the performer and will finish at time 3. At time 3 we have two conflicting choices, and doesn't matter which we chose. Time 5 and 7 are not conflicted either.

My solution

Made tuples of the arrivals and durations by zipping. Sorted the tuples first on arrival, then on duration.
Outer for cycle for i from start to finish. Initialize new set in each iter.
Inner for cycle for j from i to finish. Check if j can be added to the set without conflict. If set is longer than max I save.

Python source

Questions

Are there better ways, standard algorithms to solve this problem?
I know that there are some edge cases, for which my algorithm doesn't work. Hackerrank evaluated my algo, and it only passed 7/13 test cases. What could be some edge cases I am missing?
Is this a search problem or an optimization problem?

This is a simple Interval Scheduling Maximization problem, which can be solved in O(n log(n)) time via a simple greedy algorithm. The trick is to sort performances according to end time and not start time.

Here is the description of the solution found on the Wikipedia page I linked:

Several algorithms, that may look promising at first sight, actually do not find the optimal solution:

Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests.
Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal.

Greedy polynomial solution

The following greedy algorithm does find the optimal solution:

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

Whenever we select an interval at step 1, we may have to remove many intervals in step 2. However, all these intervals necessarily cross the finishing time of x, and thus they all cross each other. Hence, at most 1 of these intervals can be in the optimal solution. Hence, for every interval in the optimal solution, there is an interval in the greedy solution. This proves that the greedy algorithm indeed finds an optimal solution.

A more formal explanation is given by a Charging argument.

The greedy algorithm can be executed in time O(n log n), where n is the number of tasks, using a preprocessing step in which the tasks are sorted by their finishing times.


Prove that context free languages aren't closed under DropMiddle The question is simple:

$\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$.
Prove that CFL's aren't closed under $\operatorname{DropMiddle}$.

I should probably be looking for a counter example, but I'm coming up short. I know that the language $ww$ ($w$ is a word in some CFL) isn't a CFL, but I can't figure out if I'm on the right track at all.

First off, you are right about looking for a counter example. However, $ww$ is a dead end, since no matter what you add to the middle, you'll stiil have a language that is not context-free.

Hint 1: If the middle character is in some way special in $L$, you can essentially modify a PDA for $L$ to nondeterministically guess the middle and the removed letter and it will accept $\operatorname{DropMiddle}(L)$. So you should try to look for a language, where the dropping makes the middle special.

Hint 2: If the specialness of the middle is the only feature of $\operatorname{DropMiddle}(L)$, a PDA could just use its stack to determine the middle. So you need to force it to use the stack in a different way.

Solution:

   $L = \{ aw_1aw_2aw_3a\ldots aw_na \mid w_i\in \{(,)\},~ w_1\ldots w_n \text{ is correctly parenthesized} \}$.

 The $w_i$ part forces any PDA for $L$ or $\operatorname{DropMiddle}(L)$ to use its stack to count open parens. Thus it is impossible to check if, the single missing $a$ after dropping is indeed missing from the exact middle of the word.

 Formally proving that $\operatorname{DropMiddle}(L)$ is not context-free should be doable with Ogden's Lemma.
Choose a word $(^k)^k(^k)^k$ (plus the $a$s inbetween) and mark $k$ characters each left and right of the middle.