STCON is NL complete - but why is the reduction in L?

You don't need to do DFS. Each branch on the nondeterministic TM corresponds to each possible path from $s$ to any node $v$ of length at most $n$. You also maintain the index of the vertex it is at which takes $O(\log{n})$ space. If at some step the NDTM has reached the node $t$ then you it halts with ACCEPT. If the NDTM has checked $n$ nodes and it has not reached the node $t$ then it REJECTs. So, if $t$ is reachable from $s$ then there is a path from $s$ to $t$ which would correspond to some branch on the NDTM. In this case the NDTM will halt with ACCEPT.

In simple words, each branch of computation needs to maintain a constant number of variables of size $\log n$: current node, counter for number nodes explored so far, etc. We don't care which nodes we have visited, the only thing we care about is the current node and the number of nodes we have visited in order to stop as soon as we visit $n$ nodes (all nodes).

In order to prove that STCON is NL-complete, given a string $w$ we need to convert it into STCON instance using log-space. Let $M$ be a log-space NDTM accepting $L$. We convert the configurations of computation of $M$ on $w$ into a directed graph. Each node corresponds to a single configuration and if there is a legal transition from a configuration $C_{i}$ into a configuration $C_j$ there is an edge between $C_{i}$ and $C_j$. The size of each configuration is $O(\log{|w|})$ since $M$ computes using $O(\log{|w|})$ space. Generating all possible configurations (nodes) and verifying that $C_i$ yields $C_j$, i.e., adding edge, take $O(\log{|w|})$ space.

Note also that we could generate all possible nodes/configurations of length $\log{|w|}$ by going through all possible strings of length $\log{|w|}$ and test if the generated string is a legal configuration. If it is legal then the TM writes it to its output tape. All this is done in $O(\log{|w|})$ space. Similarly you could generate all pairs $(C_i, C_j)$ and check if $C_i$ yields $C_j$. If $C_i$ yields $C_j$ then write it to the output tape as an edge of the output graph. This also takes $O(\log{|w|})$ space.

The key thing is that you don't need to worry about the time complexity whether it takes linear or exponential time. The output space isn't restricted to $O(\log{|w|})$ space either. Once you convert $w$ to an instance of STCON problem, STCON can decide if this instance belongs to $L_{STCON}$.


Monograph or survey paper on smoothed analysis of algorithms

To the best of my knowledge, the most recent survey is the following:

Spielman, Daniel A., and Shang-Hua Teng. "Smoothed analysis: an attempt to explain the behavior of algorithms in practice." Communications of the ACM 52.10 (2009): 76-84.

It contains a lot of discussion.


Getting maximum number of pairs in a set

Your problem is an instance of maximum matching, for which there exist efficient algorithms. The vertices in the graph are the entries of the list, and the edges correspond to allowable pairs.


I think the question is asking how to translate $f(n)$ into Big-Theta notation to be used for the Master Theorem. You have the right idea about switching between notations.

Another way to write the Master Theorem is as follows:

$T(n) = aT(n/b) + \Theta(n^d)$

So, yes, if you have a linearly growing function, then $f(n)$ may be substituted with $\Theta(n)$.

Then you may proceed with your comparisons.


The fact that $1^{\text{nan}}= 1.0$ is by definition, and not by proof, more specifically, it is by definition of the standard IEEE 754, IEEE Standard for Floating-Point Arithmetic.
From the definition of floating-point arithmetic, as specified in IEEE 754 revision 2008, 9.2.1 Special values:

pow(+1, y) is 1 for any y (even a quiet NaN).

Here is the full list of special values for pow:

For the pow function (integral exponents get special treatment):

pow(x, ±0) is 1 for any x (even a zero, quiet NaN, or infinity)
pow(±0, y) is ±∞s and signals the divideByZero exception for y an odd integer < 0
pow(±0, −∞) is +∞ with no exception
pow(±0, +∞) is +0 with no exception
pow(±0, y) is +∞ and signals the divideByZero exception for finite y < 0 and not an odd integer
pow(±0, y) is ±0 for finite y > 0 an odd integer
pow(±0, y) is +0 for finite y > 0 and not an odd integer
pow(−1, ±∞) is 1 with no exception
pow(+1, y) is 1 for any y (even a quiet NaN)
pow(x, y) signals the invalid operation exception for finite x < 0 and finite non-integer y.


Logic Question - Why is This an Implication?

Because $\neg\forall x\,(\text{Comp}(x) \wedge \text{Study}(x,l))$ means "It is not true that every student is both a computing student and studying logic." In particular, that would be true if there is at least one student who is not a computing student, regardless of whether all computing students do or do not study logic.


Let's show that $\{a^n b^n : n \geq 0\}$ is not regular using Myhill's criterion (there are infinitely many equivalence classes):

  The pumping lemma shows that $\{a^n b^n : n \geq 0\}$ is not regular. According to Myhill's criterion, if a language is not regular then it has infinitely many equivalence classes. Therefore the language has infinitely many equivalence classes, and consequently, by Myhill's criterion is not regular.

This may sound silly, but it is very similar to how you are using vectors to solve questions "using linked lists".

The alternative is to look for algorithms that can be implemented directly on linked lists. For example, one sorting algorithm which can be implemented directly is merge sort. Merge sort consists of the following operations:

Divide the input into two sublists of nearly equal size. Easy to do on a linked list using a simple scan.
Recursively sort each sublist.
Merge the two sorted sublists. The merge algorithm is also easy to implement on a linked list.

In contrast, an algorithm like quicksort seems hard to implement directly without having random access.


Computation time of a Binom matlab (or C) routine

If you can avoid it, you don't want to compute sums like that at all.

If you compute terms like $p^k$ directly, you'll get big errors due to floating-point precision (because your result will be almost zero).

If you haven't seen it, one common way to handle small probabilities is to apply the logarithm trick:

$\qquad \displaystyle p^k(1-p)^{n-k}\ \leadsto\ k \cdot \log p + (n-k) \cdot \log(1-p)$.
If possible, apply well-known closed forms for sums to eliminate them entirely. Computing that is less problematic, both in terms of numerical issues and running time.
Failing that, find an approximation that you can tune to the required precision.

And also:

Computing running times with an algorithm is not computable in general. You will have to apply algorithm analysis yourself. After implementing an actual algorithm, that is. See a good textbook or our reference questions for starters.


How do we fix area of detectors in object detection?

If you want to only look for matches in part of the image and ignore the rest, crop out the part you want to look in (removing the rest of the image), then apply the object detector to the cropped image.


$MAX-CLIQUE \in \mathsf{coNP \Leftrightarrow NP = coNP}$.
The answer is yes: your variant of $MAX-CLIQUE$ is in $\mathsf{P^{NP}}$, since knowing the size of max clique you can solve your problem.

There is no polynomial verifier (if $\mathsf{NP \neq P^{NP}}$) for this problem, because it is not in $\mathsf{NP}$.

Classic $MAX-CLIQUE$ which only asks if there is a clique of size at least $k$ is $\mathsf{NP}$-complete. But if $\mathsf{P = NP}$ you can ask a machine if there is a clique of size $|V|, |V| - 1, |V|-2...$ until the answer is "YES" to find max clique. Of course, you can use binary search instead of linear.

So, $\mathsf{P = NP}\Leftrightarrow MAX-CLIQUE\in \mathsf{P}$.


Which of the following is a more appropriate complexity for this reccursive function?

You can show that if the binary expansion of $A>0$ contains $N_0$ zeroes and $N_1$ ones then $h(A) = 2N_1 + N_0$. Since $N_0 + N_1 = \lfloor \log_2 A \rfloor + 1$, this shows that $h(A) = \Theta(\log A)$.


Which are the cases where the "pumping lemma" doesn't work?

The standard formulations of the regular pumping lemma all force the pumped part to be at a specific place -usually the beginning of the word- and of a very restricted length. Thus you can trick the lemma by contructing a language that allows just about anything in the first part of the string and gets complicated in the second part. Take for example:

$$\{wba^nb^n\mid w\in\{a,b\}^+,\ n>0\}\,.$$
Since the pumping lemma just states the existence of its constants, you can pump anything in the first part of the language without leaving it. However, due to the last component the language is not regular.


This is a standard problem in Natural Language Processing (NLP).

Classifying whether each word is a noun, verb, etc., is known as "part-of-speech tagging".  Searching on that term should turn up a lot of information about how to do that.

If you want to tag the words in some other way, you might be able to use other tagging algorithms.  They generally use some sort of machine learning approach and will probably require a large training set (200 words won't be enough).


Is the Kleene star of an intersection always equal to the intersection of kleene stars?

Clearly not.

Let $A=\{a\}$ and $B=\{aa\}$.

Now,

$A\cap B =  \emptyset$

so

$(A\cap B)^* = \{\epsilon\}$

but

$A^*\cap B^*=B^*=\{a^{2i} : i \in \mathbb{N}\}$

(all strings consisting of an even number of $a$).


Pick parameter function that minimises whole function

This is probably not possible. Let $n_1,\ldots,n_k$ be the sequence of $n$s encountered in the recurrence, starting with $n_1 = n$. Using the concavity of $\log$ (and eliminating the big $O$), we get that
$$ T(n) \geq k \log \frac{f(n_1) + \cdots + f(n_k)}{k}. $$
Assuming $f$ is monotone, we have $k \geq \log n_1/\log (n_1/n_2) = \log n/\log f(n)$. This monotonicity also shows that $n_{(k+1)/2} \geq \sqrt{n}$. Therefore
$$ T(n) \geq \log n \frac{\log f(\sqrt{n}) - 1}{\log f(n)}. $$
For all $f(n)$ I can think of, $\log f(\sqrt{n})/\log f(n) = \Theta(1)$, so they can't give you anything better than $\log n$. This also says that if you're looking for a monotone $f$ which beats $\log n$, then it must satisfy $\log f(\sqrt{n}) = o(\log f(n))$.


No. The logarithmic overhead comes from the fact that the machine you're simulating could have an arbitrarily large state set $Q$ and arbitrarily large tape alphabet $\Gamma$. To simulate any such machine using a fixed, constant number of states and a fixed, constant tape alphabet, you need to code $Q$ and $\Gamma$ as multiple symbols in the universal machine's tape alphabet: specifically, you need $\log |Q|$ symbols to write down the current state of the simulated machine, and each character of the simulated tape will take $\log |\Gamma|$ symbols on the universal machine's tape.  (The base of the logarithm will depend on how many symbols you use: for example, simulating in binary will give logs to base 2.)

Because of this, the logarithmic slowdown is unavoidable, even if you use multiple tapes.  Indeed, if you only use a single tape, it'll be even worse than logarithmic.

However, see Shreesh's answer for a more significant source of logarithmic overhead, which is logarithmic in the running time of the simulated machine, not just the length of its description.


Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages)

The letter $e$ stands the empty word, which is usually denoted by the symbol $\varepsilon$.
A hint of this is that, according to step 6, if $S \to e$ then the initial state $S$ is also a final state.


Compare phase and magnitude spectrum results of 2 Images

The images are mostly noise with a recognizable cross in the middle, that means that there is nothing in the image that repeats. The first image however shows some patterns (circles), not just the cross, those are probable the wall on the top-left which has some repeating pattern on it.


Why is there so little literature on partial order production?

This is a very well-known problem, known as topological sorting.
Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such as this.


Horn formulas are always satisfiable unless there is at least one unit clause that contains a positive literal.  (Otherwise assigning false to all the variables guarantees the formula would be satisfied.)  The procedure in that case is to unit propagate all unit clauses that contain a positive literal and unit propagate any such new clauses as they occur.  Once this task is completed, if the remaining formula contains no empty clauses then the Horn formula is satisfiable.


Given a set, partition it into ordered triples

If you select two elements from $Z$, then by the pigeonhole principle, there must be a triple that does not contain any element from $Z$, which is impossible.


Think about it. You can sort an array by adding all the items to a priority queue, then removing the items in sorted order.

If you could run a priority queue in constant time, you could sort in linear time. But you can't.


Given a set of intervals on the real line, find a minimum set of points that "cover" all the intervals

The problem is in $\mathbf{P}$.

In fact, there is even a (very) efficient algorithm for it:

Let $[a_1, b_1], \dots, [a_n, b_n]$ be the input intervals and assume $a_i \le b_i$ for all $i$. Additionally, let us assume (for now) that the intervals are given in sorted order as a list, sorted firstly respective to the $a_i$ and secondly to the $b_i$.

An optimal solution can be found as follows: Set $r$ to $a_1$. Then, starting with $i = 1$, check if $a_{i+1} \le b_i$; if that is the case, set $r$ to $a_{i+1}$ and increment $i$; otherwise, add $r$ to the solution and eliminate all intervals from $[a_1, b_1]$ up to $[a_i, b_i]$. Repeat until no more intervals are left.

Why is this an optimal solution? $[a_1, b_1]$ must be covered, so there must be some $r \in [a_1, b_1]$ in the solution. Then, either $r$ covers all $n$ intervals or there is $i$ such that $r < a_{i+1}$. The way our solution is constructed, $r$ is chosen so as to cover a maximal number of intervals while preserving these two conditions for $r$ (i.e., $a_1 \le r \le b_1$ and $r < a_{i+1}$). Apply induction on the remaining intervals (i.e., $[a_j, b_j]$ with $j \ge i + 1$).

The above procedure runs in linear time in $n$. The bulk of the time complexity, thus, lies in sorting the intervals, which can be done in $O(n \log n)$. I do not believe there is a better solution than this (though how to prove it does not occur to me at the moment).

A note

After some thought, the solution you have given also seems to be optimal (in fact, the only significant difference is you pick end times instead of start times). Proving it is optimal is analogous to the argument above: Set $r$ to $b_1$; if $a_2 \le b_1$, then $r$ already covers $[a_2, b_2]$, so disconsider it; otherwise, $a_2 > b_1$ and there is no $r$ covering both $[a_1, b_1]$ and $[a_2, b_2]$. Apply induction.

The time complexity is still $O(n \log n)$, though, since you require sorting the end times first.


Comparisons of functions, their big-oh and their implications

As a counterexample you can take $f(n)=n$ and $g(n)=\sqrt{n}$. You can think that $f(n)=O(n^2)$ means that an upper bound for $f(n)$ is $n^2$ (of course, without considering multiplicative constant), so the fact that both $f$ and $g$ are bounded by $n^2$ does not implies nothing about the relative behavior of $f$ and $g$.


Questions on Sipser's NP implying verifiability?

Essentially, yes. Though I usually find it easier to think of nondeterministic machines as guessing what to do. So, as the machine runs, it starts by repeatedly doing the following: either it guesses that the current string is good, and verifies it, or it guesses what the next character should be, and it repeats. Thus, if there's some string that the verifier will accept, some sequence of guesses will lead to the machine producing that exact string and then deciding to verify it, so the machine will accept. (Also, the machine needs to keep track of how long the string is, so it can stop if it gets too long.)

We have a nondeterministic Turing machine $N$ and the guesses it makes lead it down some path of the tree of possible computations. If that path ends in an accepting state, the machine is defined to accept its input; if no path ends in an accepting state, it is defined to reject. There's no circularity: that's just the definition of what it means for a nondeterministic machine to accept or reject.
From this machine, we build a verifier. The input to the verifier is a description of a computation path, and the verifier checks that each action taken on that path is a thing that $N$ could do in that state, and that the path ends in an accepting state. If those conditions are met, the verifier has verified that $N$ really would accept the given input.


Is two arrows on each state necessary in DFA?

You are correct.

In an NFA, there might be more arrows (for epsilon transitions, or multiple transitions on the same symbol) or fewer arrows (for undefined transitions) than there are symbols in the alphabet. In a DFA, neither of these is allowed: in fact, a DFA is specifically defined as an NFA where neither of these things happens.

Therefore a DFA will always have exactly as many arrows from each state as there are symbols in the alphabet.


You have to be very careful of what you mean when you say "deep-copying". This came up in a thread at StackOverflow in relation to C++. The first question you need to address is can an automatic "deep-copy" even be done?  Consider just a few basic quesetions:

If the type of a data element is a referential type can you determine whether a deep copy implies copying the reference or the referred to type? That is, can you identify the ownership of these items?
Does the presence of a singleton, or external resource, prevent a deep copy, or does the copy refer to the same resource?
Given that data relations often form graphs with cycles. Could such a relationship automatically be detected? Even if yes, what would if mean to start the deep copy at an inner-node of such a structure?

This is likely why you only find references which are very language specific. Each language has its own notion of copying. This default copy is not likely to match the expected notion of a deep-copy in all situations.

I would say it is not possible to even specify what deep-copy is without explicitly enumerating the types available in a given language. This would essentially require that all research about deep-copying is specific to a particular language (even if that language is theoretical).

If you are looking for efficiency comparisons you would then also be stuck in the domain of a very particular language. You could possible define a reduced compound data type common to several languages and evaluate the efficiency of copying such structures. Such results however would not be applicable to any language with more complex data types.


Is CS more like software and CE more like hardware?

This is actually an easy one, particularly if you just want to see some meaningful distinction drawn by an organization people listen to. Consider the ACM/IEEE guidelines on computing curricula.

The differences between Computer Science and Computer Engineering can be seen when comparing the respective bodies of knowledge:

Computer Science (2008)

Discrete Structures, 43 core hours
Programming Fundamentals, 47 core hours
Algorithms and Complexity, 31 core hours
Architecture and Organization, 36 core hours
Operating Systems, 18 core hours
Net-Centric Computing, 15 core hours
Programming Languages, 21 core hours
Human-Computer Interaction, 8 core hours
Graphics and Visual Computing, 3 core hours
Intelligent Systems, 10 core hours
Information Management, 11 core hours
Social and Professional Issues, 16 core hours
Software Engineering, 31 core hours
Computational Science, no core hours

The total core hours for CS add up to 290 hours.

Computer Engineering (2004)

Algorithms, 30 core hours
Computer Architecture and Organization, 63 core hours
Computer Systems Engineering, 18 core hours
Circuits and Signals, 43 core hours
Database Systems, 5 core hours
Digital Logic, 57 core hours
Digital Signal Processing, 17 core hours
Electronics, 40 core hours
Embedded Systems, 20 core hours
Human-Computer Interaction, 8 core hours
Computer Networks, 21 core hours
Operating Systems, 20 core hours
Programming Fundamentals, 39 core hours
Social and Professional Issues, 16 core hours
Software Engineering, 13 core hours
VLSI Design and Fabrication, 10 core hours
Discrete Structures, 33 core hours
Probability and Statistics, 33 core hours

The total core hours for CmpE add up to 486.

A fair way to compare the two might be to find a percentage makeup based on the above curricula. The conclusion would seem to be that CS is at or above CmpE in subjects they have in common, and has fewer other subjects, whereas CmpE is lower in common areas to both programs, but has more subjects not studied in CS, mostly related to EE. This seems to be consistent with the distinction I normally draw, so I'm happy with the overall result of the analysis, but you might draw your own conclusions.


Since SET COVER can be reduced to this problem, you can't expect it to have an efficient solution. To reduce SET COVER to your problem, add a dummy user $u$ covering an auxiliary element, add the other users corresponding to the sets in the instance of SET COVER, determine the counts as in your problem, and then you can tell whether there is a set cover of given size.


Time complexity of languages that are polynomial time reducible to NP complete languages

You are right.  You can't draw that inference.  Given the assumption that SAT can be solved in $O(2^{\sqrt{n}})$ time, it does not follow that all NP-complete problems can be solved in $O(2^{\sqrt{n}})$ time.

For instance, the reduction from the NP-complete problem to SAT might transform a problem instance of size $n$ to a SAT instance of size $n^2$, so applying the SAT algorithm to that would take $O(2^n)$ time.  There are some reductions that preserve the size of the problem instance, and for those reductions, you will be able to solve them about as fast as SAT -- but as far as we know, not all NP-complete problems fall into that category.

You might enjoy reading about the exponential time hypothesis, which is the hypothesis that there is no such subexponential-time algorithm for SAT.  Folks have studied the consequences of the exponential time hypothesis in depth (as well as the consequences of the negation of the exponential time hypothesis).


Confirmation of Dijsktra application explanation

It's more traditional to describe dijkstra with the open and closed sets:

You start with an empty closed set and an open set containing $ \{ (A,0) \}$

You select the node with the lowest cost and remove it from the open set, then you expand the neighbours and add them to the open set $ \{ \{B,1\}  \{D,2\} \}$ or update the elements in the open set and Add the selected node to the closed set

step1:
open = $ \{ (B,1, A),  (D,2, A) \}$
closed = $\{(A)\}$

step2:
open = $ \{ (C,4, B),  (D,2, A) \}$
closed = $\{(A),(B,A)\}$

step3:
open = $ \{ (C,3, D)  \}$
closed = $\{(A),(B,A),(D,A)\}$

There is no actual sense of "backtracking" because you are considering all the open nodes in parallel.

Many other search algorithms work in the same way with the only difference in how a node is selected from the open set. Breadth-first takes the oldest node in the set, depth-first takes the youngest, Dijkstra takes the node with the lowest cost, A* takes the node with the lowest cost+heuristic.


The function

$$f(h) = \left( {k \over 4h-1} \right)^h$$

is monotonically decreasing for $h < k+1/4$, and monotonically increasing for $h>k+1/4$.  (How do I know?  Set $f'(h)=0$ and solve for $h$.)

Therefore, one approach is to use a binary search on $h$ within the range $[0, \min(k+1/4,n)]$ to search for $h$ such that $f(h)=n$, followed by another binary search on $h$ within the range $[k+1/4, n]$.  You could also replace the binary search with a method with faster convergence, such as Newton's method.


Your problem can be posed more formally as follows: Is there a weak reduction from XORSAT to 2SAT? Here weak can be, for example, logspace or AC$^0$.

We know that 2SAT is NL-complete under AC$^0$ reductions, while restricted versions of XORSAT (say 3XORSAT) are $\oplus$L-complete under AC$^0$ reductions, see this paper proving a refined Schaefer dichotomy theorem. Although NL$\subseteq \oplus$L non-uniformly (see this answer), we don't expect the converse to hold, and in particular we don't expect there to be a weak reduction from $\oplus$L to NL. Unfortunately I'm unaware of any concrete results in this direction.

Summarizing, it is expected that there is no weak reduction from XORSAT to 2SAT, but I'm not sure there's much technical work supporting this conjecture.


The book states the following definition of a cut:

a cut is defined by a partition of $V$ into two sets say $V^{l}$  and $V \setminus V^{l}$ and consists of all edges that have one endpoint in each partition.

Therefore, removing a cut from the graph should mean that we are removing the edges that go across the cut.
Also, consider the following definition of the "cut associated with an edge $(u,v) \in T$ in $G$".

Each edge $(u,v)$ in $T$ denotes a partition of $V$ given by the two connected components obtained by removing $(u,v)$ from $T$. Consider the cut defined in $G$ by this partition. We will say that this is the cut associated with $(u,v)$ in $G$.

Now, let us consider your example of Gomory-Hu tree for $K_{4}$. We want to find the cut associated with the edge $(3,0) \in T$. If we remove $(3,0)$ from $T$, we obtain the partitioning $\{1,2,3\}$ and $\{0\}$. This defines the cut in $G$.
Therefore, you should be removing the edges of $G$ that goes across this cut i.e., $(0,1)$ $(0,2)$ and $(0,3)$.
Similarly for the edge $(3,1) \in T$, you should be removing the edges: $(1,0)$, $(1,2)$, and $(1,3)$.
And, for the edge $(3,2) \in T$, you should be removing the edges: $(2,0)$, $(2,1)$, and $(2,3)$.
It means we are removing all edges from the graph. Therefore, the number of connected components in the remaning graph would be $4 = (n + 1)$, for $n = 3$.


Algorithm to solve job assignment problem

Instead of putting x, put some very high cost values in those cells.
Then the Hungarian algorithm avoids selecting those cells automatically (if that's possible).


Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization

This can be reduced to an instance of the minimum-cost flow problem.

Build a flow network from your graph, with an edge from each donor to each recipient whose maximum flow is $1$ and whose cost is the negation of the value of that matching.  Add a source vertex $s$, with an edge of weight $\text{maxd}(d)$ and cost $0$ to each donor $d \in D$.  Add a sink vertex $t$ with an edge of cost $0$ and maximum weight $\infty$ from each recipient to $t$.  Now compute the minimum-cost flow.  This can be done in polynomial time, so your problem can be solved in polynomial time.

So your question boils down to asking whether there are parallel algorithms for min-cost flow.  Searching the literature will turn up a bunch of algorithms for that.  If you use Google Scholar, you can find a number of papers on that subject.


Running an application that needs 6 threads on dual core processor

If there are $2$ cores and $4$ threads, two threads will be assigned to each core. Similarly, if there are $6$ threads, three threads will be assigned to each core. For example, suppose $6$ threads are $T_1,T_2,T_3,T_4,T_5,T_6$. Then, say $T_1,T_2,T_3$ are assigned to core $1$ and $T_4,T_5,T_6$ are assigned to core $2$.
As you are saying, $T_1,T_2,T_3$ will switch back and forth on core $1$ to give an illusion of parallel. However, note that $T_1$ and $T_4$ are indeed running in parallel on different cores.


Fixed size set to contain the maximum number of given sets

The decision version of the problem can be formulated as follows:

Given a collection of sets of numbers $S$. Each number is drawn from a set $U$.
You want to know if there is a way to pick $k$ numbers from $U$ to form a set $X$ which is the superset of $s$ sets in $S$.

The following is a reduction from k-clique which is an NP-complete problem.

The k-clique problem has an input as a graph and asks if there is a way to pick $k$ nodes so that there is an edge between any two of the $k$ nodes.

We turn each node into a number. These numbers form the set $U$. We turn each edge into a set containing two numbers representing the corresponding two nodes of the edge. These sets form the set $S$.

The question to the original problem is: Is there a way to pick $k$ numbers from $U$ to form a set $X$ such that $X$ is the superset of $C_{2}^k$ sets in $S$

The proof has two directions.

If there is a k-clique in the graph, then we can pick the $k$ numbers corresponding to $k$ nodes in the clique to form $X$. Because of the way we transform the graph, we know there will be $C_{2}^k$ sets in $S$ each corresponds to an edge in the original graph and thus is a subset of $X$. So the answer to the original problem is positive.
If there is no clique of size $k$, then for any set of $k$ nodes chosen from the graph one can only have less than $C_{2}^k$ undirected edges between any two picked nodes. Otherwise, we will have a clique of size $k$. This means that there can only be less than $C_{2}^k$ subsets of $S$ which is a subset of the set $X$ formed by any $k$ chosen numbers. So the answer to the original problem is not positive.

The transformation is in poly-time. The reduction is proven, so the problem is NP-hard.
The problem is clearly in NP because we check how many sets covered by $k$ numbers in poly time. This means the original problem is NP-complete.


Why not decide coNP language L with same NDTM used for $L^c$?

I assume that you want to "decide if $x\in L^c$ and output the complement". Tell me if I misunderstand.

$L^c$ is in NP if there's an NDTM accepts $x$ in "at least one" branch iff $x\in L^c$. So $x\in L$, i.e. $x\notin L^c$ means the NDTM rejects $x$ in "all" branches. Think more carefully about these quantifiers.

NDTM can always find the accepted branch if it exists, but this doesn't means the NDTM has checked all branches. So we can't decide if $x\in L$ with the same NDTM in the trivial way you mentioned.

Edit: If you want to prove $L\subseteq NP$, you should construct "one NDTM" such that there exists a polynomially long path to an accepting state iff $x\in L$. You might think flipping the answer is quite simple, but where's the answer? There doesn't even exist a state representing "NO". This is the problem. You can't add another Turing machine which read the output of $M$ and output its complement either since the whole structure is not a valid NDTM.


Constructing a deterministic one way infinite single tape Turing machine

Here is a rather reasonable way to implement this in Turing machines:

Sort the bs and the as so that the input tape is composed of bs followed by as.
Repeatedly perform the following operation: remove $B$ as from the end of the input tape, where $B$ is the number of bs.
Accept if you never got stuck perform an iteration of the previous step.

The second step can be implemented without explicitly counting $B$. For the first step, you can implement the simplest algorithm you can think of, say bubble sort.


How does IEEE 754 decimal encoding work?

Fair question. First of all, it's worth noting that the IEEE decimal formats are fairly modern and not used particularly often—they're meant for the rare use cases where things need to round in a specific way, mostly in finances.

But, there are various ways to encode a truly decimal number (i.e. a number stored as a series of base-10 digits) in binary. The simplest is called BCD (Binary Coded Decimal), which uses four bits to represent each digit. Many early computers used this system because humans are used to decimal and found it more intuitive.

BCD is kind of wasteful, because four bits can represent any number from 0 to 15, and a single digit only need to represent a number from 0 to 9. So IEEE uses slightly different packings, called Binary Integer Decimal and Densely Packed Decimal. They're somewhat more complicated, but the idea is the same: you have a one-to-one mapping between decimal digits and binary bits, wasting as few bits as possible.


Intuition for PH notation in Arora-Barak's Computational Complexity

The notation $M(x,u_1,\ldots,u_i)$ stands for a polytime Turing machine with $i+1$ inputs, applied to the inputs $x,u_1,\ldots,u_i$. There are many ways of implementing Turing machines with several different inputs, and from this perspective they are all equivalent, so pick one. (Some examples: several input tapes, inputs separated by special separator symbol, oracle mechanism for obtaining $j$th input.)

Your definition is for languages in $\Sigma_i^P$. When $i = 1$, you get $\mathsf{NP}$. A language $L$ is in $\mathsf{NP}$ is we can verify that $x \in L$ using a polytime Turing machine given a polysize hint $\alpha$. If the verifier is $M$, then this means that
$$ x \in L \Leftrightarrow \exists \alpha \in \{0,1\}^{q(|x|)} M(x,\alpha) = 1, $$
where $q$ is a polynomial bounding the size of the witness.

For $i > 1$ there are more quantifier alternations, and you can think of it as a game between two players: the existential player is trying to prove that $x \in L$, while the universal player is trying to prove that $x \notin L$. The game proceeds in $i$ rounds, in which the players alternate giving polysize "witnesses" $u_1,\ldots,u_i$. After $i$ rounds, a judge $M$ is shown the transcript, and makes a verdict; $M(x,u_1,\ldots,u_i)=1$ means that the judge thinks that $x \in L$. A winning strategy for either player is a strategy that guarantees that the verdict will be favorable to them. A language is in $\Sigma_i^P$ if there exists such a polytime judge $M$ such that if $x \in L$ then the existential player has a winning strategy, while if $x \notin L$ then the universal player has a winning strategy.

Here are two examples:

$SAT \in \Sigma_1^P$. In this case the judge $M$ takes as input a formula $x$ and a witness $w$, and checks that $w$ is a satisfying assignment for $x$. If $x \in SAT$ then there is a satisfying assignment, and so the existential player can guarantee that the judge declares $x \in SAT$. If there is no satisfying assignment then the universal player (who is silent) can guarantee that the judge declares $x \notin SAT$.
Circuit minimization $CMIN \in \Sigma_2^P$: a pair $(A,k)$ is in $CMIN$ if $A$ is a circuit encoding a function $f$ which can be computed by a circuit of size at most $k$. The judge $M$ takes as input the pair $(A,k)$, a witness $B$ from the existential player, and a witness $x$ from the universal player, and accepts if $B$ is a circuit of size at most $k$ that agrees with $A$ on the input $x$. If $(A,k) \in CMIN$ then the winning strategy of the existential player is to produce a circuit $B$ of size at most $k$. If $(A,k) \notin CMIN$ then the winning strategy of the universal player is, for each circuit $B$ of size at most $k$, to find an input $x$ on which $A$ and $B$ disagree.


What are cases where we cannot perform LR parsing without augmented grammar?

Once we have a parsing table, we can parse (or reject) any sentence without any reference to the grammar. So at that point, the fact that the grammar was or was not augmented is essentially moot. (It would be meaningful if there were a user semantic action attached to the augmented start symbol's sole production, but that seems impossible, since the augmented start symbol's production was added automatically, not by the user.)
And it is indeed the case that most parser generators do in fact optimise their parse table by making the shift of the end-of-input marker the accept action, rather than waiting for the augmented start symbol's production to be reduced. With that optimisation, the augmented start symbol is never used in a parser action, so the symbol itself need not exist. If the parser generator augmented the grammar, that augmentation has essentially been undone, except for one little mystery: what is this end-of-input symbol which can be shifted? It doesn't appear in any reducible right-hand side.
Anyway, the point is that it's not parsing which requires an augmented grammar; the augmented grammar is necessary to create the parsing table. The cases where it is necessary are essentially the cases in which there is some non-default reduction action associated with an end-of-input symbol lookahead. That reduction action could only have been correctly added to the parsing table through the analysis of a state which includes the augmented start symbol's production.
(Strictly speaking, as alluded to earlier, the end-of-input symbol can't really exist in the parsing table unless it is present in some right-hand-side in the grammar, and it isn't present until the grammar is augmented; the augmentation not only adds an additional non-terminal, it also adds the end-of-input symbol itself.)


Your problem is decidable. If $M$ always executes less than 5 steps, then it never sees more than the first 4 symbols of its input. Hence it suffices to run $M$ on all inputs of length at most 4.


Directed cyclic graph with node rewards and arc costs

I think this problem is NP-Complete via reduction to Knapsack Problem

An instance of the Decision Problem involves: a  Graph g, time alloted, sum_reward, and two nodes s,t
: Is there path from s to t with sum of rewards>=sum_reward within the alloted time period?

Reduction

Add nodes $s,t$ and an edge $s->t$ with reward,weight =0.
For every item a=(value(a),weight(a))
create a node  $n_{a}$ and the following two edges:

$e_{a}= s->n_{a}$ with $reward(e_{a})=value(a)$ and $cost(e_{a})=weight(a)$
$e_{b}= n_{a}->s$ with both values zero

I just noticed that rewards are on nodes instead of edges. But  this does not change the reduction(just transfer reward from edge to node)

Now run the algo for input ($G',knapsack$ $size$,$sum$ $reward,s,t$)$

IFF proof

=> if knapsack is feasible, simply iterate over edges of nodes contained in the knapsack and finally hop from s to t. This will give the desired sum_reward

<= More or less, the same idea.

I hope this helps you somehow :)

Since your data is kind of special, perhaps someone can provide  an exact algorithm instead of an approximation one. I cannot (yet :P)


How turing machine can be used as enumerator

As your language $L$ is decidable ( lets its decider be $D$ ), you can build an enumerator $E$ for it ( which disregards its own input ). $E$  gives strings  ( with alphabet being $\sum =\{a,b\}$ ) in increasing order ( lexicological order, which is possible as $\sum^{*}$ is a countable set ) to $D$ and if $D$ accepts an input $E$ prints it, if $D$ rejects an input $E$ does not print it. If your language is undecidable but  recognizable
  this method won't work for making an enumerator for such a language.
EDIT

If $L$ is a recognizable but not a decidable language we can build an enumerator for it in the following way. Let $R$ be the recognizer for the language and $E$ the enumerator. The strings in $\sum^{*}$ are denoted as $s_1,s_2,....$ ( again in lexicological order ).

i = 1
while ( True )
  j = 1
  while ( j <= i )
     Give the string s_j as input to R and let R run for i steps,if R halts on
     s_j in at most i steps and accepts it, E prints the string s_j

     j = j + 1
  i = i + 1

Note with above method if a string belongs to $L$ it may be printed several times ( which can be avoided ). But unlike a decidable language there is no way to guarantee that strings are enumerated in lexicological order.


Given regular expression construct regex for the complement language

The problem with your attempt is that you've only looked at what happens when the regexp to transform is a simple one. For example, you've looked at what the complement of $a^*$ looks at. But in order to write a compositional complementation algorithm, you need to figure out how to compute a regular expression that recognizes the complement of the language of $r^*$, for an arbitrary regular expression $r$.

The bad news is that your approach to build a complement for $a^*$ does not generalize easily. Consider for example the regular expression $(a + b + c)$. A regular expression that recognizes its complement language is $\epsilon + (a + b + c) (a + b + c) (a + b + c)^*$ — but this isn't really useful to know if you're looking for the complement of $(a + b + c)^*$, which is the empty language. You can't reach the complement of $(a+b+c)^*$ from starring something related to the complement of $(a+b+c)$.

You can approach this problem by adding a complement operator to regular expressions, in which case the algorithm you're looking for is an algorithm to remove the complement operator from such generalized regular expressions. It turns out that this brings you close to an open problem, the generalized star height problem: it's unknown whether you can eliminate nested stars in such generalized regular expressions, which shows that the interaction between the star operator and the complement operator is poorly understood.

Your idea of transforming the regular expression into a DFA and back is a good one. It's perfectly reasonable a different representation of an object where the operation you're interested in is easier. In fact, this is the usual algorithm to find a regular expression for the complement language of a regular expression:

Build a DFA that recognizes the language of the regular expression.
Transform the DFA into one that recognizes the complement language.
Build a regular expression whose language is that of the second DFA.

   Step 2 is very easy: just swap accepting and non-accepting states. Note that this doesn't work on an NFA!


Does |xy| ≤ p in the pumping lemma count for all i?

Your mistake is in the following step:

  Split $w$ into $xyz$ as $x = \epsilon$, $y = a^p$, $z = 0^p 1$.

You're not allowed to choose how $w$ splits into $xyz$. You should show that for any way of splitting $w$ into $xyz$ such that $|xy| \leq p$ and $y \neq \epsilon$, there exists $i$ such that $xy^iz \notin L$.

Here is a similar "proof" that the language $01^*$ isn't regular:

Pick $w$ as $01^p$.
Split $w$ into $xyz$ as $x = \epsilon$, $y = 0$, $z = 1^p$.
Show that $xy^2z = 0^21^p$ is not in the language.

The proof of the pumping lemma will choose a different splitting, for example $x = 0$, $y = 1$, $z = 1^{p-1}$.


Algorithms for graph generation using given properties

There are no general algorithms for your problem but what one usually does (for graphs of small orders) is

Use nauty to generate graphs satisfying some rough constraints (you can make nauty generate only (bi)connected graphs, regular graphs, triangle/quadrangle free graphs,..)
Use an external program to extract only the graphs you need with respect to some additional  properties that you want.

You can do both 1 and 2 in sage! For example consider that you want to generate all connected 5-regular graphs of order 20 that have average distance 10 (Wiener index??) and some clustering coefficient. You do the following

for G in graphs.nauty_geng(" 20 -c -d5 -D5" ):
    if G.wiener_index() == 10 and G.clustering_coeff() == SOMETHING:
       print G.adjacency_matrix()

Let me know if you need some more specific answers related to sage.


How to select a binary tree node uniformly at random

The algorithm works just fine.

Note that each node's size field tells you the total number of nodes in the subtree rooted at that node. Throughout this answer, I'm just going to assume that a child's size is zero if the child is null.  Thus, for any node in the tree, we have

this.size == left.size + 1 + right.size

Consider the root of the tree.  If we choose a node of the tree uniformly at random, then it should be in the left subtree with probability left.size/size, it should be the root node with probability 1/size and it should be in the right subtree with probability right.size/size.  By the equation above, these three probabilities add up to 1.  If you look at lines 15–22, the algorithm implements exactly this probability distribution.  It generates a uniform random integer in the range 0 .. size-1.  If this number is in the range 0 .. left.size-1, the algorithm picks a random node from the left subtree; if it's equal to left.size, it picks the root and, otherwise, it picks a random node from the right subtree.

And the argument I gave doesn't depend on the node you consider being the root, so the recursive calls behave as they should.  The algorithm doesn't care about the depth of the nodes: it just recurses down the subtree and chooses subtrees with the correct probability.


By the max flow min cut theorem, the maximum value of a flow equals the minimum capacity of a cut. The capacity of a cut is of the form 12x+18y, which can’t equal 56 because 56 is not a multiple of 6.


What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG?

As far as I know, it is an open problem whether one can do significantly better (in an asymptotic sense).

This is known as the reachability query problem for DAGs.  You want to do some precomputation, after which you can answer queries of the form Reachable$(u,v)$ (which should return true if $v$ is reachable via some path from $u$, i.e., if $u$ is an ancestor of $v$).

There are two trivial algorithms:

With no precomputation, you can answer each reachability query in $O(|V|+|E|)$ time by just using DFA.
With a $O(|V| \cdot |E|)$-time precomputation and $O(|V|^2)$ space, you can precompute the transitive closure of the DAG and then answer each query in $O(1)$ time.

Apparently it is an open problem to do significantly better than this: e.g., to precompute something with less than $O(|V|^2)$ space that enables you to answer reachability queries efficiently.  See https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038.


Running time of naive recursive implementation of unbounded knapsack problem

You will be trying every sequence of items that fit, adding the same item multiple times if that is possible. So first you need to check if you actually wanted the same item to be used multiple times. Whether you did or not, you can make the algorithm a lot more efficient if you only add items in ascending order, that is if you added item k, then you only add further items k, k+1, k+2, ... or only items k+1, k+2, ... depending on whether you wanted to allow the same item multiple times.

You could also save substantial time again by sorting the items for example in descending order. If you do that, you can try adding items with the smallest first, and when an item doesn't fit, you know further items won't fit either - so you can stop the search there.

Anyway, the time depends entirely on the data. If all the items are in size between capacity/2 and capacity then it's $O (n^2)$ (could be $O (n)$ with improvements described earlier). If any item has weight 0, then your algorithm never ends; you should check that first. In the worst case where all n items have size 1 and the capacity is W, your algorithm takes $n^W$ steps - that's especially bad because that particular problem is trivial.


Is maximum matching problem equivalent to maximum independent set problem in its dual graph?

To start with possible NP-hardness (where for each problem, we want a matching/independent set of size at least $k$):

Independent set is NP-hard on "normal" graphs (and also on hypergraphs)
Maximum matching is polynomial-time solvable on "normal" graphs, see the wikipedia page on matching.
Maximum matching is NP-hard in hypergraphs (as shown in this wikipedia page, it is even hard for hypergraphs where each edge contains only 3 vertices).

I believe both problems are equivalent in the following sense:  set $S \subseteq E(H)$ is a matching in $H$, if and only if $S$ forms an independent set in $H^*$.

(If you need further explanation or if this is not your definition of equivalance, please clarify)


Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $W = k$. There is a subset of sum at least $k$ and at most $W$ iff there is a subset of sum exactly $k$.

In the other direction, the idea is to add to the collection a small set of items satisfying the following two properties:

The total weight of the new items is $W-k$.
Every weight between $0$ and $W-k$ can be represented as a sum of a subset of the new items.

Having added this collection, we ask whether there is a subset summing to exactly $W$. It is not hard to check that there is a subset of the original collection whose sum is between $k$ and $W-k$ if there is a subset of the enlarged collection summing to $W$ exactly.

How do we add these items? The simplest case is when $W - k = 2^t$, in which case we can simply add $1,2,4,\ldots,2^{t-1}$. More generally, suppose $2^t \leq W-k < 2^{t+1}$, and let $W-k = 2^t + C$. We then add $1,2,4,\ldots,2^{t-1},C$.


Modified Counting Inversions problem using divide and conquer

Hint:

   Can you count the number of pairs $(i,j)$ such that $A[i]=A[j]$?


Reduction variation for the q-coloring problem

When proving that $q\text{-}\textsf{COL} \leq_m^P q\text{-}\textsf{COL}_{2q-1}$, what you are really showing is that checking whether a graph with maximal degree $2q-1$ is $q$-colorable isn't any easier than checking whether an arbitrary graph is $q$-colorable. Why is this an interesting statement? Since if we replace $2q-1$ with a small enough number, then checking whether a graph is $q$-colorable does become easier. For example, any graph with maximal degree $q-1$ is $q$-colorable, so checking whether such a graph is $q$-colorable is easy, whereas checking whether an arbitrary graph is $q$-colorable is NP-hard for all $q \geq 3$.

How do you show that $q\text{-}\textsf{COL} \leq_m^P q\text{-}\textsf{COL}_{2q-1}$? You need to transform a given graph $G$ to a graph $H$ with maximum degree $2q-1$ such that $H$ is $q$-colorable iff $G$ is $q$-colorable. The most natural way of doing this is by splitting high-degree vertices. I'll illustrate how to do it for the case $q=2$ (which in reality isn't so interesting — why?), and will let you generalize the construction. Once you do that, you'll also see where $2q-1$ is coming from.

Suppose therefore that $q = 2$. First of all, we number the neighbors of all vertices. For each edge $(v,w)$, there are numbers $i,j$ such that $w$ is the $i$th neighbor of $v$, and $v$ is the $j$th neighbor of $w$. Now, we replace each vertex $v$ of degree $d$ with a path $v_0,\ldots,v_{2d}$, and connect $v_{2i}$ and $w_{2j}$ if $w$ is the $i$th neighbor of $v$ and $v$ is the $j$th neighbor of $w$. Note that all vertices now have degree at most 3. The construction works basically since the vertices $v_0,v_2,\ldots,v_{2d}$ all get the same color — I'll let you work out the details.


You are looking for an optimal 1-dimensional k-means algorithm.  The k-means objective function for partitioning the data $x_1, \ldots, x_n$ into $k$ sets $S = \{S_1, \ldots, S_k\}$.

$$
\sum\limits_{i=1}^k \sum\limits_{x \in S_i}\lVert x - \mu_i \rVert^2
$$

where $\mu_i$ is the mean of $S_i$ [1].

You can apply a dynamic programming algorithm to the problem [2].

Let the data $x_1, \ldots, x_n$ be sorted in non-decreasing order.
Fill a $(n + 1) \times (k + 1)$ array, $D$, with the minimum sum of squared errors, for the first $i$ entries, using $m$ clusters.  This can be calculated as

$$
   D[i,m] := \min\limits_{m \le j \le i} \left\{ D[j-1,m-1] + d(x_j, \ldots, x_i) \right\}
   $$

where $d(x_j, \ldots, x_i)$ is the sum of squared errors from their mean.  For $1 \le i \le n$ and $1 \le m \le k$, and the base cases are $d[i,m] = 0$ if $i=0$ or $m=0$.

Thus, the entry $D[n,k]$ contains the optimal sum of squared errors for the original problem, now all that is left to do is to extract the answer.

Note that $d(x_j, \ldots, x_i)$ can be computed iteratively to speed up the algorithm, as

$$\begin{align*}
   d(x_j, \ldots, x_i) &= d(x_j, \ldots, x_{i-1}) + \frac{i-1}{i} (x_i - \mu_{i-1})^2 \\
   \mu_i &= \frac{x_i + (i - 1) \mu_{i-1}}{i}\end{align*}
   $$

Thus, $D$ can be computed in $O\left(n^2k\right)$ time, since there are $nk$ entries, and each takes $O(n)$ time to compute.
Now, we fill a $n \times k$ array, $B$, whose entries, $B[i,m]$, contain the index of the smallest (first) element in the cluster that contains entry $i$, which can be calculated as

$$
   B[i,m] := \arg\min\limits_{m \le j \le i} \left\{ D[j-1,m-1] + d(x_j, \ldots, x_i) \right\}
   $$

for $1 \le i \le n$ and $1 \le m \le k$.  This takes $O\left(n^2k\right)$ time.

Thus, we can backtrack from $B[n,k]$ to find the clustering.  The clusters are defined recursively as

$$\begin{align*}
   S_k &= \{B[n,k], \ldots, x_n\} \\
   S_i &= \{B[x_j,k], \ldots, x_j \mid x_{j+1} := \min S_{i+1}\}
   \end{align*}$$

The backtracking takes $O(k)$ time.

The algorithm runs in $O\left(n^2k\right)$ time, and requires $O(nk)$ space.

[1] http://en.wikipedia.org/wiki/K-means_clustering

[2] http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf


Primes not dividing sequence $a_{n+1} = 1 + a_0 a_1 \cdots a_n$

Let me write it here, because I had a typo in the comment.
First observe that
$$
\begin{align}
a_{n+2}&=1+a_0a_1\dotsm a_na_{n+1}\\
&=1+a_0a_1\dotsm a_n(1+a_0a_1\dotsm a_n)
\end{align}$$
So $$4a_{n+2}=(2a_0a_1\dotsm a_n+1)^2+3$$
This implies that for an odd prime $p$ that divides $a_{n+2}$, we must have that $-3$ is a quadratic residue modulo $p$. By quadratic reciprocity, $-3$ is a quadratic residue modulo $p$, when $p$ itself is a quadratic residue modulo $3$. Therefore, any odd prime of the form $3K+2$, with $K\in\mathbb{Z}$ doesn't have $-3$ as quadratic residue and  cannot divide $4a_{n+2}$ for any $n\geq0$.
Since there are infinitely many primes of the form $3K+2$ (see here for example), then an infinite collection of primes that don't divide any of the elements of the sequence are the primes of the form $3K+2$, excluding from them $2$, the primes that divide $a_0$ and the primes that divide $a_1$.


DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

Here is a quick and dirty proof using Pumping Lemma that language $L$ consisting of $3^n$ in binary is not regular (note: it is regular if represented in ternary, so representation is important).

I will use the notation from Wikipedia article re Pumping Lemma. Assume for contradiction that $L$ is regular. Let $w \in L$ be any string with $|w| \ge p$ (pumping length). By Pumping Lemma, write $w = x y z$ with $|y| \ge 1, |xy| \le p$ and for all $i \ge 0$ $xy^i z \in L$. I will write $x$, $y$, and $z$ also for numerical values of corresponding parts, and $|x|, |y|, |z|$ for their lengths in $w$. Numerically we have $w = 3^{k_0}$ for some $k_0 \in \mathbb{N}$. At the same time we have numerically $w = z + 2^{|z|} y + 2^{|z|+|y|}x$. Thus, we have

$$ z + 2^{|z|}y+2^{|z|+|y|} x = 3^{k_0}$$

Now, let's pump $w$ to get for all $i \ge 0$

$$ z + 2^{|z|} y \left( \sum_{j=0}^{i-1} (2^{|y|})^j \right) + 2^{|z|+i|y|} x = 3^{k_i}, $$

where $k_0 < k_1 < k_2 < \ldots$. Simplifying we get for $i \ge 1$

$$ z + 2^{|z|} y (2^{i |y|} - 1) / (2^{|y|}-1) + 2^{|z|+i|y|} x = 3^{k_i}.$$

Let $C = z - 2^{|z|} y / (2^{|y|}-1)$. Then we have

$$ 3^{k_i} = 2^{|z|+i |y|} y / (2^{|y|}-1) + 2^{|z|+i|y|} x + C. $$

Now, observe that

$$ 3^{k_i} - 3^{k_{i-1}} = (2^{|y|}-1)(3^{k_{i-1}} - C). $$

Therefore, we have $C (2^{|y|}-1) = 3^{k_{i-1}} (2^{|y|} - 3^{k_i - k_{i-1}}).$ Note that $|2^{|y|} - 3^{k_i - k_{i-1}}| \ge 1$. Thus, on one hand, the absolute value of the right hand side grows at least as $3^{k_{i-1}}$, which goes to infinity with $i$. On the other hand $C(2^{|y|}-1)$ is independent of $i$ and is a constant. This gives a contradiction.


Smallest multiple of a number that gives a specific remainder modulo another number

Using Congruent Modulo Notation, one can rewrite the problem as:

$$a*k \equiv c\pmod{b}$$
This is a simple linear congruence, that can be solved using the Extended Euclidean Algorithm

There are other algorithms, but this one is the simplest.

According to Wikipedia:

  In big O notation, this algorithm runs in time $O(\log(m)^2)$, assuming
  $|a| < m$, and is considered to be very fast and generally more
  efficient than its alternative, exponentiation.

Where $m$ is the letter $b$ in your example


Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

Because, if you only use $f(n)$ tape cells, there are at most $|\Sigma|^{f(n)}$ possible strings you can have written on the tape, at most $f(n)$ different places the tape head could be, and at most $|Q|$ different states the Turing machine could be in.  That means there are at most $|Q|\,f(n)\,|\Sigma|^{f(n)}$ different configurations for the machine.  If the machine runs for more steps than that, it must visit the same configuration twice.

For a moment, let's pretend the machine is deterministic. If it visits the same configuration twice, it will take exactly the same sequence of steps and visit a third time, and infinitely often, so it cannot terminate.  However, we know that it does terminate for all inputs.  Therefore, it runs for at most $|Q|\,f(n)\,|\Sigma|^{f(n)}=2^{O(f(n))}$ steps.

But, actually, the machine is nondeterministic. Still, if some computation path visits the same configuration twice, we know that there is a computation path in which, by making the same nondeterministic choices again, the machine reaches the configuration a third time, and so on. Since we're told that every computation path terminates, we know that no computation path visits the same configuration twice, so we're done as in the deterministic case.


What does it mean to add up O-terms with different variables?

Yes, this is true.

The LHS means that for some $N$, $M$ and some constants $c_n,c_k$,

$$n\ge N,k\ge M\implies f(n,k)\le c_nn+c_kk.$$

The RHS means that for some $N'$, $M'$ and some constant $c$,

$$n\ge N',k\ge M'\implies f(n,k)\le c(n+k).$$

These two statements are equivalent if you take $c\leftarrow\max(c_n,c_k),N'\leftarrow N,M'\leftarrow M$ one way and $c_n=c_k\leftarrow c,N\leftarrow N',M \leftarrow M'$ the other.


What's wrong with my pumping lemma proof?

The problem is in the quantifiers. The pumping lemma says that any string $s$ with $|s|\geq p$ can be written as $xyz$ such that the three properties hold. It doesn't say that every way of writing it as $xyz$ that makes the first two properties hold also makes the third one hold.

For the language $\{0^{2n}\mid n\geq 0\}$, we proceed as follows. First, note that we must have $p\geq 2$, since if $p=1$, we're forced to take $x=\epsilon$, $y=0$, $z=0^{2p-1}$ and you already showed in the question that this doesn't work.  So, with $p\geq 2$, we can write $s = 0^{2p}$ as $s=\epsilon\,00\,0^{2(p-1)}$ ($x=\epsilon$, $y=00$, $z=0^{2(p-1)}$). We have $|\epsilon00| \leq p$, $|00|>1$ and $(00)^i\,0^{2(p-1)}\in L$ for all $i\geq 0$. Thus, there exists some way of decomposing the string as $xyz$ that satisfies all the properties, even though the first decomposition you thought of didn't work.

To show that a language isn't regular, you need to show that every decomposition into $xyz$ that satisfies the first two properties fails to satisfy the third one. It's not enough to just show that one decomposition doesn't work.

To understand why the pumping lemma is the way it is, it helps to think about the proof. If a language is regular, it is accepted by some DFA. That DFA has some number of states: call it $p$. By the pigeonhole principle, whenever that DFA reads a string longer than $p$, it must visit some state twice: say state $q$. Now, $x$ is the part of the input read upto (and including) the first visit to $q$, $y$ is the part read after the first visit and upto and including the second (which must be at least one character) and $z$ is the rest. But now you can see that $xz$ must be accepted: $x$ takes you from the start state to $q$ and $z$ takes you from $q$ to an accepting state. Likewise, $xy^iz$ must be accepted for any positive $i$, since each repetition of $y$ takes you from $q$ back to $q$.  Note that the decomposition of the input into $x$, $y$ and $z$ is entirely determined by the automaton which is, in turn, determined (but not uniquely) by the language. So you don't get to choose the decomposition: if the langauge is regular, some decomposition exists; to show that a language is not regular, you must show that every decomposition fails.


How do I find the max and min value of an array in 3n/2−2 comparisons?

Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. The maximum value of the original array must be the max of the larger group and the minimum value of the original array must be the min of the smaller group. Initially, you do n/2 comparisons to make the split, and from there you need to find the max and min of two groups of n/2 elements each, which can be done with a total of n/2 - 1 comparisons per group. Overall, this is 3n / 2 - 2 compares.

... assuming, of course, you have an even total number of elements. Think about what happens if that isn't the case.


Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?

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

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

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

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

The output is

true
abbabbc
true
a
a
c

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


Finding unique cubiods with given volume

Hint. Once you've chosen the first two dimensions, it's trivial to calculate what (if any) range of values for the third dimension give a volume within your interval.


What is the relation between functors in SML and Category theory?

Categories form a (large) category whose objects are the (small) categories and whose morphisms are functors between small categories. In this sense functors in category theory are "higher size morphisms".

ML functors are not functors in the categorical sense of the word. But they are "higher size functions" in a type-theoretic sense.

Think of concrete datatypes in a typical programming language as "small". Thus int, bool, int -> int, etc are small, classes in java are small, as well structs in C.
We may collect all the datatypes into a large collection called Type. A type constructor, such as list or array is a function from Type to Type. So it is a "large" function.
An ML functor is just a slightly more complicated large function: it accepts as an argument several small things and it returns several small things. "Several small things put together" is known as structure in ML. In terms of Martin-Löf type theory we have a universe Type of small types. The large types are usually called kinds. So we have:

values are elements of types (example: 42 : int)
types are elements of Type (example: int : Type)
ML signatures are kinds (example: OrderedType)
type constructors are elements of kinds (example: list : Type -> Type)
ML stuctures are elements of kinds (example: String : OrderedType)
ML functors are functions between kinds (example: Map.Make : Map.OrderedType -> Make.S)

Now we can draw an analogy between ML and categories, under which functors correspond to functors. But we also notice that datatypes in ML are like "small categories without morphisms", in other words they are like sets more than they are like categories. We could use an analogy between ML and set theory then:

datatypes are like sets
kinds are like set-theoretic classes
functors are like class-sized functions


Does word addressable memory have more bytes than byte addressable memory?

If you had a byte addressable architecture where pointers have a fixed size, and every or almost every bit pattern is a valid pointer to a distinct byte address, and a word addressable architecture where pointers have the same fixed size, and every or almost every bit pattern is a valid pointer to a distinct word address, then the second architecture could address more memory. Which means you could buy more RAM for more money and put it into a computer and use it.

That second architecture would be in big trouble with lots of data structures that require byte pointers, like typical implementations of strings, compressed data, etc. Writing an mp3 player with word addressable memory wouldn't be my kind of fun.

In practice, even mobile phones are using 64 bit processors with pointers taking up 64 bits of memory, and the addressable amount of memory right now so much exceeds what anyone could reasonably pay, that it just doesn't matter. 4 GB of memory cost around 20 dollars, multiply by 4 billion, that's 80 billion dollars, and that's what you can address with byte addressability and 64 bit pointers.

(An analogy: You have an order form that allows you to order boxes of eggs. There are only six digits space, so you can order at most 999,999 boxes. If you order boxes of 18 eggs instead of boxes of 6 eggs, you can order three times as many eggs. You also pay three times as much money. Now you look at your form and it has space for 20 digits. That's more than the whole worlds egg production, whether you order them in boxes of 6 or 18. )


Should we eliminate left recursion before using NPDA to simulate CFG?

As stated in the second paragraph following the one you quote, the PDA being constructed is non-deterministic, which greatly simplifies the construction.

A non-deterministic machine is allowed to have points at which more than one action is possible, without any procedure for determining which one is correct. It is only necessary to prove that one possible action leads to correct termination.

Such machines are easy to construct in formal theory but building them in the real world is trickier. A back-tracking parser must explore alternatives in some order; if it chooses an alternative which fails to terminate, then it will never get around to trying another possibility.

In contrast, the non-deterministic machine terminates acts as if it took all possible branches at the same time. If any branch terminates in an accepting state, the machine can can terminate and accept the input. This can be simulated by making copies of the machine at every branch, and simulating the progress of all currently active copies by repeatedly advancing each one by one step. (More copies might be made at each step of each copy, so it can get a little closer unwieldy.)

Consequently, it does not matter to the PDA if there is left-recursion in the grammar. To be sure, the left-recursion means that some of the possible execution paths will never terminate, but as long as there is a path which terminates, the PDA will choose it.

There is a subtle but important point which I left out of the first version of this answer, which is that the definition of the language recognised by the PDA is the set of inputs for which the PDA terminates in an accepting state. Nothing guarantees that the PDA will eventually terminate on other inputs, and it is quite possible that the PDA will never halt if it is given a input which is not in the language it recognises. (This is another reason why non-deterministic PDAs aren't much use in practical parsers.)

This should not be surprising. If the machine were guaranteed to halt, then there would exist a machine which recognised the complement of the language. But if that were the case, the complement of every context-free language would be context-free, and we know that not to be true.


A median of an AVL. How to take advantage of the AVL?

If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To accomplish this, you write a more general procedure Select which accepts a node $v$ and a number $k$, and finds the $k$th smallest node at the subtree rooted at $v$.

Suppose that the left subtree (if any) has $L$ nodes. If $k \leq L$ then we recurse to the left subtree. If $k = L+1$ then we return $v$. Otherwise we recurse to the right subtree, reducing $k$ by $L+1$.

The running time of this algorithm is linear in the height of the tree, which is $O(\log n)$.


How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$?

The line of thought that I find the most fruitful is: try to come up with a (semi)algorithm for the problem. If you succeed, great. If you don’t, it’s probably impossible.

Let’s apply it to your problem: determining whether a Turing machine accepts only palindromes. The trivial way to solve this problem is to go over all non-palindromes, and check whether your Turing machine accepts any of them. This shows that your problem is co-r.e., since you can enumerate all Turing machines which accept some non-palindrome.

There doesn’t seem to be a matching algorithm for enumerating Yes instances of your problem, so your problem is probably not r.e. Indeed, Rice’s theorem shows that your problem isn’t recursive, and so we can deduce that it is not r.e.

With a bit more work, you can show that your problem is $\Pi_1$-complete, that is, every problem in co-r.e. can be (effectively) reduced to it. To show this, it suffices to show a reduction from the non-halting problem to your problem. In this problem, given a machine $M$ and an input $x$, the goal is to determine whether $M$ does not halt on $x$. Given an instance $\langle M,x \rangle$ of this problem, construct a machine $M’$ which goes into an infinite loop (or rejects) unless the input is $10$ (an arbitrary non-palindrome), in which case it simulates $M$ on $x$, and then accepts (if $M$ ever halts). The new machine $M’$ accepts only palindromes if and only if $M$ doesn’t halt on $x$.


Implementing a Boolean function with NOR gates

Hint: you know it's a two-level circuit using only NOR gates. There is only one such circuit:

  OUT
   |
  NOR
  / \
 |   |
NOR NOR
/ \ / \
? ? ? ?

Can you now figure out where to place a, b and d to correctly construct the circuit? Since you have to repeat (at least) one input, does looking at symmetry help?


Time complexity analysis of 2 arbitrary algorithms - prove or disprove

It is possible. Example $g_A(n)=1$, $g_B(n)=2$, and $f(n)=1$.

It is also necessary, since $g_B(n) = 2 g_A(n) \in\Omega(f(n))$.

To see that $ 2 g_A(n) \in\Omega(f(n))$ you can use the definition of $\Omega(\cdot)$.

From $g_A(n) = \Omega(f(n))$ you know that here is some $n_0$ and some $c>0$ such that, $\forall n \ge n_0$, $g_A(n) \ge c f(n)$.
This implies that, for the same value of $n_0$ and $c$, $2 g_A(n) \ge 2 c f(n) \ge c f(n)$, i.e.,  $ 2 g_A(n) \in\Omega(f(n))$.


A* doesn't backtrack. It just keeps expanding the node with the least value of $f$ until it finds a solution. The properties of the heuristic used guarantee that the first solution found is optimal.


Merging $k$ sorted lists in $O(n\log k)$ time

Yes, you are right.

$O(c \cdot f(n)) = O(f(n))$ for any constant $c$.

It may also be written (maybe even more clear) in the form
$$O(k) + O(n \lg k) + O(n \lg k) = O(n \lg k)$$


I'm going to first assume that your graph is connected; that is, every node of the graph is reachable from $s$. We'll relax this condition down the line, but for now, it simplifies the problem.

Now, let's start with what we know. If $G$ is connected, then we can visit every vertex; that is, there's some path $p$ that goes to each vertex $t$.

Let's examine such a path $p = (p_0 = s), p_1, \dots, p_{n-1}, (p_n = t)$. By definition, we know that the value of such a path is just $R(p_0, \dots, p_n) = \bigotimes_k N_{p_k}$. In addition, if at $p_n = t$, we immediately turn back and travel backwards on $-p$ (the reverse path of $p$), then we would eventually arrive back on $s$ with a value of
\begin{align*}
R(p, -p) &= R(s, \dots, p_{n-1}, t, p_{n-1}, \dots, s)\\
&= \left(\bigotimes_{0 \le k \le n} N_{p_k}\right) \otimes \left(\bigotimes_{0 \le k \le \bf n-1} N_{p_k}\right) \\
&= (N_{p_0} \otimes N_{p_0)} \otimes (N_{p_1} \otimes N_{p_1)} \otimes \dots \otimes (N_{p_{n-1}} \otimes N_{p_{n-1}}) \otimes N_t
\end{align*}

Recall that xor has the property that $x \otimes x = 0$, the identity. therefore, any path from $s$ to $t$ and back to $s$ just gives a value of $N_t$. In fact, any conjunction of paths
$$
s \stackrel{p_1}{\to} v_1 \stackrel{-p_1}{\to} s \stackrel{p_2}{\to} v_2 \stackrel{-p_2}{\to} s \stackrel{p_3}{\to} \dots \stackrel{-p_n}{\to} s
$$
gives a value of
$$
N_s^{n + 1} \otimes \bigotimes_k^n N_{v_k}
$$
Furthermore, we can get rid of the $s^{n+1}$ term by deciding to stop the final path immediately before the terminal vertex if it falls on an even $n$.

In essence, this tells us that it is possible to construct a walk starting at $s$ such that the value of this walk is $\bigotimes_{v \in S \subseteq V(G)} N_v$ for any subset of vertices of $G$.

This then suggests that your problem reduces down to finding a subset of vertices $S \subseteq V(G)$ such that $\bigotimes_{s \in S} N_s$ is maximum over $V(G)$.

At first glance, this might seem like a non-trivial covering/knapsack problem. For one thing, the naive strategy here seems to be to try out every subset of $V(G)$. In addition, there doesn't seem to be any sort of monotonicity, continuity, or even some form of "optimal substructure" property for us to exploit.

Fortunately for us, this problem admits a relatively nice representation in terms of a linear algebraic system, and its solution process is equivalent to finding the rank of an induced matrix, or alternatively, Gaussian Elimination.

Now, suppose that we have a set of annotated vertices $N = \{N_v \mid v \in V(G)\}$, how do we represent this as a linear system?

Well, given an integer $N_v = 1011\cdots01_2$ in binary, then we can think of it as the column vector
$$
[\![N_v]\!] = \left(\begin{array}{c}1\\0\\ \vdots \\ 0 \\ 1\end{array}\right)
$$
Now, let's consider the semi-ring $(+ = \otimes, \times = \max = \times_{\mathbb{N}})$ over bits (0, 1). Here the addition operation is bit xor and the multiplication operation is the usual integer multiplication, which also happens to be the $\max$ operation or the $\wedge$ conjunction operation.

We wish to find coefficients $c_0, c_1, \dots, c_n$ such that
$$
c_0 [\![N_{v_0}]\!] + \dots + c_n [\![N_{v_n}]\!]
$$
is "maximized". In particular, we wish to analyze the $A_N: k \times n$ system
$$
\left(A_N = \left(\begin{array}{ccc}[\![N_{v_0}]\!] & \cdots & [\![N_{v_n}]\!]\end{array}\right)\right) \left(\begin{array}{c} c_0 \\ \vdots \\ c_n \end{array}\right)
$$
where $k$ is the size of your bit-vectors (likely $32$ or $64$). Now, chances are, this system is over-determined (but also rank-deficient). Therefore, our first instinct will be to reduce this system to reveal its rank structure.

Doing this ends up giving us an efficient algorithm: Gaussian Elimination.

The idea is as follows. We try to solve the problem of
$$
A_N c = \left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)
$$
through Gaussian Elimination. Now, I need to emphasize that we are only trying to solve this problem because, chances are, there is no solution! Think about it, $A_N c$ gives the bit-vector that corresponds to the final value of a walk, so if $A_n c = 1$ always has a solution, then it means that our problem is trivial: always return $2^{32} - 1$. In fact, in pretty much all interesting cases, there's no way to satisfy this attempted equality.

"What? Why are you doing this to me then?"

Simple, we actually inspect a trace of the algorithm rather than the final solution. In particular, at each iteration of Gaussian Elimination, we might find ourselves in one of two situations. Either everything still goes fine and dandy, and we can continue elimination, or we reach a contradictory state where we realize that we can't proceed. In the latter case, this corresponds to a case where you need to add a row of zeros and somehow magically pull a one out. In such cases, rather than aborting, we will just concede the impossibility and replace that row in the output with a zero.

More concretely, after $m$ iterations of elimination, we are left with a subproblem in which we only have to analyze the subsystem starting at the $m^{th}$ row. All of the prior rows will be zeros or part of the identity grid.

At the $m^{th}$ row, either there is some column $[\![N_{v_i}]\!]$ in our intermediate matrix that has a leading $1$ in that row, or it's impossible to fill that row in the output.

In the former case, we will select one such column to pivot (and with a bit of thought, you should choose the largest column), and add (subtract, since the inverse of $\otimes$ is still $\otimes$) it from every other column that still has a leading $1$ in that row.
Otherwise, we will be forced to concede that the only solution is to place a $0$ in the output at that row and move on.

This then gives an algorithm find a maximum subset with respect to $\otimes$:

for each i from 31 down to 0, do
  if there's some maximal vertex v such that N(v) >= 2^i, then
    select v as a pivot and remove it from future considerations
    for every other vertex u such that N(u) >= 2^i, do
      N(u) := N(u) xor N(v)
    end for
  else,
    // Here, we can't possibly hope to fill this row with a one, so
    do nothing
  end if
end for

Now, the set of pivots that you have selected will give you the maximum xor-subset; just xor them together to find the maximum. The number of pivots also corresponds to the rank of your system, and if there are 32 pivots, then that immediately means that your maximum value is $2^{32} - 1$. If there are 31 pivots, then that means that there's a single 0 somewhere in your bit vector; 30 pivots means that there are two holes; etc.

Finally, we relax the restriction that our graph be connected. Rather, we will simply preprocess the graph and identify the connected component that contains the vertex $s$, and proceed similarly afterwards.

Best of luck!


is the intersection of a context free language and a regular language a two way street?

Your clam is false even in the special case where $L_1 \cap L_2$ is regular.
To construct a counterexample let $L_1$ be a language that is not context free (e.g.,  $L_1 = \{a^n b^n  c^n: n \ge 0\}$) and pick $L_2 =\emptyset$ (other choices for $L_2$ work too).
Both $L_2 = \emptyset$ and $L_1 \cap L_2 = \emptyset$ are regular (and hence also context-free), but $L_1$ was chosen as a non-context free language.


How do I sort these elements in O(n) time?

If you want to implement this on a RAM with integer math (ie. a real computer if your n is smaller than $2^{32}$), you can have a look at Upper bounds for sorting integers on random access machines. The authors show that integers in the range [0,$n^c$] can be sorted in $O(n(1 + \log c))$. Word RAM models add some loglog factors to that runtime.


How did early computers handle variable word length?

I've recently programmed an IBM 1401, so I can explain how its variable length words work.

For the motivation, remember that the IBM 1401 was a low-cost ($2500/month) 1960's computer for business applications on punched cards, for example payroll processing or inventory processing. The 1401 typically reads a file of punched cards, where each card holds fixed-length fields for one data record. The computer does some processing on each card, and prints out a report on the line printer, with fixed-length fields. Thus, it is convenient if the computer can easily manipulate fields of characters or numbers where each field has an arbitrary but fixed length.

The 1401's variable-width words are how it supports fixed-length fields. The programmer initializes the field lengths at the beginning of the program. Then a single "move" instruction will move a string field, regardless of how long it is. You don't need to loop over each character; the processor does that automatically. And you can add two numbers with a single "add" instruction, whether a 2-digit number or a 40-digit number. This is efficient, saves very expensive program memory, and is a good match for card-based applications.

Now, for the 1401's implementation of variable-length words (or fields). The IBM 1401 uses 6-bit characters (coded in BCDIC, precursor to EBCDIC), holding a text character or a decimal digit. (Note that the 1401 did decimal arithmetic, which worked well for business applications.) Each location in core memory has an additional "word mark" bit, which you can think of as a "metadata" bit. The programmer sets the word mark bit on the leftmost (high-order) character in a field. An instruction will typically process an entire field from right to left, until it hits a word mark, and then stops.

The important thing is that word marks aren't part of the 6-bit character. When you read a card, move a field, or so forth, the word marks are unchanged. Thus, the programmer can initialize the word marks once (with special word mark instructions), and then they stay put while you process the data.

Word marks are also used in the 1401 for variable-length instructions (1 to 7 characters), with a word mark after each instruction. One puzzle is that word marks aren't stored on the punched card, so how can you read in a program from cards? The solution is that when you load a program, you're actually loading and running a loader program that inserts the word marks as necessary for the program you actually want to run.

There is no limit on the size of a 1401 word, other than memory size. As a test, I created two 1000-digit numbers and multiplied them with a single "multiply" instruction. The computer churned away for literally a minute on this one instruction before generating the result.

The 1401 Reference Manual is online and provides more information, in case you didn't get enough here.


Can a program language be malleable enough to allow programs to extend language semantics

Converge has some pretty impressive meta-programming facilities.

  At a simple level, this can be seen as a macro-like facility, although it is more powerful than most existing macro facilities as arbitrary code can be run at compile-time. Using this, one can interact with the compiler, and generate code safely and easily as ITrees (a.k.a. abstract syntax trees).

which is a step up from Scheme's hygienic macros that allow referentially transparent macro definitions.

Mechanisms like quasiliterals have allowed constructing and destructuring of parse trees in other languages, but those are more often used for interacting with domain-specific languages (DSLs) instead of self-modification.

Newspeak's reflection allow exceptions to be implemented as library code.

  7.6 Exception Handling

  Because Newspeak provides reflective access (7.2) to the activation records(3.6), exception handling is purely a library issue. The platform will provide a standard
  library that supports throwing, catching and resuming exceptions, much as in
  Smalltalk.

Perligata:Romana demonstrates how an entirely new syntax can be skinned onto a language.

  This paper describes a Perl module -- Lingua::Romana::Perligata -- that makes it possible to write Perl programs in Latin.

Arguably not semantically significant, PyPy is an interpreter generator for languages whose semantics are specified in a highly statically-analyzable subset of Python, and they use it to experiment with new language constructs in Python like adding thunks to the language.

Also of interest might be Ometa.

  This dissertation focuses on experimentation in computer science. In particular,
  I will show that new programming languages and constructs designed specifically to
  support experimentation can substantially simplify the jobs of researchers and programmers alike.

  I present work that addresses two very different kinds of experimentation. The ﬁrst
  aims to help programming language researchers experiment with their ideas, by making it easier for them to prototype new programming languages and extensions to existing languages. The other investigates experimentation as a programming paradigm, by
  enabling programs themselves to experiment with different actions and possibilities—
  in other words, it is an attempt to provide language support for what if...? or possible
  worlds reasoning.

Alex Warth's dissertation demonstrates using an Ometa to define significantly new semantics (transactional semantics via worlds) in JavaScript+Ometa.


Algorithm for clustering points in $\mathbb{R}^2$ based on pairwise distance (percolation graphs)

The following algorithm does unfortunately does not allow you to get the $n^2$ factor out (see comment below).

Superimpose an $r/\sqrt 2$-by-$r/\sqrt 2$ grid on the unit square: notice that every point within the same grid cell is automatically within the same cluster.  Also notice that there can be at most $n$ grid cells containing one or more points; these are the only grid cells we need to consider from this point on.

Map each point to its grid cell.
For each grid cell, throw all contained points into the same cluster.
For each pair of neighbouring grid cells $P$, $Q$ (each grid cell, apart from those at edges and corners, has 8 such neighbours), determine the closest pair of points $p, q$ having $p \in P$ and $q \in Q$ using this $O(n\log n)$ algorithm.  If $d(p, q) < r$ then combine $C(P)$ and $C(Q)$, otherwise not.

You can use a union/find disjoint set data structure to maintain the clusters in close-to-linear time, just as per the Kruskal algorithm.


Decision Problem vs. Optimization Problem

We don't know that $\mathrm{P}\neq\mathrm{NP}$ so we don't know that the decision problem itself can't be solved in polynomial time!

But, under the assumption that $\mathrm{P}\neq\mathrm{NP}$, the optimization version of an $\mathrm{NP}$-complete problem can't be solved in polynomial time. If we could, for example, compute the shortest travelling salesman tour in polynomial time, we could certainly tell in polynomial time whether there's a tour of length at most $d$


Quasigroups, congruences and recognizable subsets

(1) for any function $\varphi:E\to F$, the relation $R_\varphi$ as you define it is always an equivalence relation on elements of $E$. But the notion of congruence depends of the laws you have on your sets, and $R_\varphi$ will be a congruence for the operations that are preserved by $\varphi$. Notice that your formulation with $usv$ is not anymore well-defined without associativity: you have to state it separately for $us$ and $sv$.

(2) Let us weaken even more the hypotheseses. Let $\varphi:E\to F$ be any function, without any structure assumed on $E$ and $F$.
Then if we take the definitions you wrote for "recognised" and "saturated", the 3 propositions are still equivalent, as your proofs still work.

The thing you will lose by considering arbitrary sets (or groupoids or loops) is that you won't carry out the nice monoid structure of $\Sigma^*$, so you lose almost all the tools of regular languages theory, like Myhill-Nerode equivalence, Green relations, and so on...

For (3), I think Jean-Eric Pin's webpage (including the document you mention) contains good surveys of this field.


Not sure if my solution to following recurrence is correct

$c=1\gt \ln 2\approx0.7$. That's case 3 of the master theorem. It follows that:

$$T(n)=\Theta(n)$$

Your solution is fine.


Determining most efficient algorithm for a problem

Note that there is a problem with no maximally efficient algorithm.

The problem "Is it the case that x has an even number of 1s and

the Turing machine M halts within length(x) steps?" is such that

$\:$ if M halts then the problem takes linear time to solve, since for inputs whose length exceeds

$\:$ the amount of time it takes for M to halt, the algorithm will have to look at each bit of x
 $\;\;\;\;$ and
$\:$ if M does not halt then the problem can be solved

$\:$ in constant time, since the answer is no for all x

.
Therefore, deciding how efficient the most efficient algorithm for some problem is, to the

extent that makes sense, is at least as hard as the halting problem. $\:$ On the other hand,

you may be interested in the circuit minimization problem and/or DFA minimization.


Identifying/equating constants in a term rewrite system

Counterexample:

$f(c) \rightarrow f(d)$

In general, there are some modularity theorems for termination and confluence that may apply if, e.g. your constants do not appear at all in any rule.

There are probably some weaker assumptions that can make this work though.


Context-free and context-sensitive grammars in FSM with counters

These counter automata have power incomparable to pushdown automata. In particular they are strictly weaker than counter machines as they have no proper zero test (if zero then .. else ..).
Technically they are known as partially blind multicounter. Blind as they cannot act on zero, partially as they store only nonnegative numbers, and block when a counter is less than zero.
As a language accepting device they are equivalent to Petri nets.
They have been studied for instance by Greibach.


Relation/use of irrational or transcedental numbers in computer science?

On the surface that does not strike me as a high-quality paper.  I wouldn't recommend it.

I don't think irrational/transcendental numbers are a good approach to building PRNGs.  Building PRNGs is tricky business.  There are standard PRNGs; I suggest using one of them, rather than trying to invent your own.  They all ensure that the output is extremely unlikely to repeat within any reasonable time period.

There is no one theory of irrational/transcendental numbers, and not just one connection to CS; irrational numbers show up in a variety of areas of CS.  It's not feasible to give you a complete list; such a list would be far too long.  If you just want one example, you might read about the Fibonacci numbers and their connection to the golden ratio (which is an irrational number).


Can agent be autonomous without having consciousness?

Here is a glimpse.

Concerning agents you're trying to elaborate here,I would like to give you some insights of these following key aspects,which might help in your future research nor knowledge;

Consciousness
Here an agent is capable of understanding its own existence nor selfawareness.
Intelligence
An agent is capable solving problem based reasoning with no help from third-party knowledge.
Autonomous
An agent has the ability to solve problems basing on the third-party knowledge for instance,self driving car does its own problem solving basing on the existing knowledge it discovers from the environment.

  Therefore,for any agent to be autonomous,it doesn't mean its selfaware
  or conscious,otherwise. For your information,do further reading on the
  above three terminologies.


You need to show that with that arbitrary pumping length $P$, for any partition $c^{(P+1)}d^P = xyz$ such that $|y|>0$ and $|xy|\leq P$, there is some $i$ such that $xy^iz \not\in A$.

Since for any partition we require that $|xy|\leq P$, then $x$ and $y$ necessarily consist only of $c$'s. Also, you know that $|y| >0$ (it's also a requirement). Can you find an $i\in\mathbb{N}$ such that the amount of $c$'s in $xy^iz$ is less than or equal to the amount of $d$'s?


Modeling tiling problems as SAT problems

One example of a tiling problem that was successfully attacked by reducing it to a SAT instance was rectangular grid coloring.  In "Extremely Complex 4-Colored Rectangle-Free Grids:
Solution of Open Multiple-Valued Problems" the authors describe how they tackled 17x17, 17x18, and 18x18 grid colorings using a SAT solver plus some previous knowledge of grid coloring theory to pare down the search space.


Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula

Yes.  If the 3CNF formula is satisfiable, here is an equisatisfiable 2CNF formula: True.  If the 3CNF formula is not satisfiable, here is an equisatisfiable 2CNF formula: False.  So yes, every 3CNF formula has an equisatisfiable 2CNF formula.

If you want to actually find that formula in a reasonable amount of time, then we don't know of any way to find such a formula in polynomial time (existence of such a method would prove that P = NP).


This Quantum Information Science and Technology Roadmapping Project is a very detailed roadmap prepared under ARDA (Advanced Research and Development Activity) around ~2004 with further refinements. Here is the introduction/overview. It had a panel of about 19 elite academic scientists/experts.

For a completely contrasting recent overview/review on progress to date/future prospects see this [controversial] paper State of the Art and Prospects for Quantum Computing, M. I. Dyakonov (2012).


Basic questions about network flow calculations

I think all your questions are answered by examining the actual algorithm to compute the max flow.

With regards to your Q1: in the max flow problem your input is a graph and capacities on edges, your output is the max flow. Thus, max flow is a function of the graph and capacities.

The basic algorithm for computing max flow is as follows. Your capacities are $c: E \rightarrow \mathbb{R}$. We shall incrementally compute the flow $f: E \rightarrow \mathbb{R}$. Let $f^i$ be the flow in iteration $i$. To begin with set $f^0 = 0$. In iteration $i$ construct the residual capacities $c^i(e) = c(e) - f^i(e)$ - this is how much capacity is left on edge $e$ given that we are already sending $f^i(e)$ flow through it. Find an augmenting path from $s$ to $t$, i.e., any path $p$ from $s$ to $t$ such that all edges on that path have positive residual capacity. How much flow can you push on this path? Clearly it's the minimum capacity along an edge of that path $f_{add} = \min_{e \in p} c^i(e)$. Update your flow by pushing $f_{add}$ flow along path $p$. This process naturally stops when your residual graph does not have an augmenting path from $s$ to $t$. It's a fact that at that point the flow you constructed is, indeed, the maximum flow. This fact requires a proof. This is a meta-algorithm (called Ford-Fulkerson), because I have not specified how to choose augmenting paths. Certain choices are better than others. Using BFS (in which case, this max flow algorithm has a name of Edmonds-Karp) to choose the augmenting path results in a polynomial time algorithm, but it again requires proof.


What do `i` and `Number` represent in the Bakery Algorithm?

As the Wikipedia page says, (emphasis mine),

  Lamport envisioned a bakery with a numbering machine at its entrance so each customer is given a unique number. Numbers increase by one as customers enter the store. A global counter displays the number of the customer that is currently being served. All other customers must wait in a queue until the baker finishes serving the current customer and the next number is displayed. When the customer is done shopping and has disposed of his or her number, the clerk increments the number, allowing the next customer to be served. That customer must draw another number from the numbering machine in order to shop again.

  According to the analogy, the "customers" are threads, identified by the letter i, obtained from a global variable.


Decidability of equivalence to existential formulas

Surely, no such algorithm can exist in the general case: for a statement of the form $\forall x.\varphi$ statement in arithmetic, with $\varphi$ quantifier-free, there is a $\exists y.\psi$ statement such that

$$ \forall x.\varphi\ \Leftrightarrow \exists y.\psi$$

if and only if the statement is $\Delta_0$, aka decidable. Because $\forall$ statements are undecidable in general, such an algorithm cannot exist.

Edit: The above reasoning is wrong! Indeed, the Bernays-Shönfinkel class of formulas includes the set of $\forall^*\exists^*$ formulas without function symbols (but with arbitrary relational symbols) and is decidable. The $\Delta_0$ statements of arithmetic are not strictly speaking, quantifier free, but only contain bounded quantifiers (which are still quantifiers in FOL!)

However, this suggests an alternate proof: if there were a decision procedure which decides whether an arbitrary sentence were equivalent to some $\exists^*$ sentence, then there would be a decision procedure for arbitrary (function-free) formulas as follows:

Given $\phi$ check whether it is equivalent to an existential formula $\psi$. If it is not, $\phi$ is not provable (otherwise it would be equivalent to the formula $\exists x.\top$).

If it is, then find such a $\psi$ (it's easy to show this is possible) and apply the decision procedure for the B-S class.

Finally, an exercise: repair the above proof using the undecidability of arithmetic.


It is mostly used in the sense of "writing instructions to the program being built". Note that what is being "emitted" might still be massaged before ending up in the compiler output.


Algorithm to mimimally pair up points in 3D space

As an approximate solution in $O(n^2)$ you can construct the cost matrix $M$ and then solve the stable marriage problem.


Time Complexity of Basic Primality Test Algorithm

The problem with your statement is that you assume that all the basic arithmetic operations are $O(1)$ and that the amount of numbers you will have to check is $O(\sqrt{n})$, relative to the size of the input.

This is wrong because $\text{PRIMES}$ is the language of all the prime numbers, given in a binary format. So an input of length $n$ will be a number of size $O(2^n)$. Then, if the input is some number $x$, in order to check all the numbers up to $\sqrt x$ you will have to go over $O(\sqrt{2^n})$ numbers, which is $O(2^{n/2})$ numbers. Even with $O(1)$ operations this will not take a polynomial amount of time.