Is concept of virtual memory about memory isolation or about ability to swap? Or both?

I would say virtual memory is not only about making memory appear bigger than it is, but also about providing many other memory related abstractions, like dealing with pages that are currently not in main memory, adding properties to memory (i.e. non-executability), and standardizing the memory layout of each process. It also allows easy relative addressing in large continuous blocks of data, which might not be able to be allocated contiguously if there was no memory virtualization.

Overcommit in my opinion is less about making it appear as if you had more memory, but more about not actually allocating physical memory if there is no need to do so, like when you allocate a huge chunk of memory "just for safety" which you have no intention of actually using.

Also, you might be confused about what sets apart overcommit and virtual memory, as they are not really two different things, but overcommit is just a part of how Linux and other operating systems implement their virtual memory.

About your last question, I would say that this is just an instantiation of process isolation (https://en.wikipedia.org/wiki/Process_isolation), using the technology of virtual address space.


As you pointed out, the reason for splitting the term into two pieces is to be able to cancel the $an$ term. If we go directly from $(8/9)cn^2 + an \leq cn^2 + an$, then we get stuck as we cannot do anything with the $an$ term. By splitting it in the way described, this allows the $(1/9)cn^2$ to be larger than $an$ when $c \geq 9a$, which then gives you the desired result since $an - (1/9)cn^2 \leq 0$ for such values of $c$.


DP recurrence relations: Coin change vs Knapsack

The knapsack problem only allows you to add each item once.  Subtracting from $k$ is, in a sense, iterating through the items and resolving a different one each recursion.

Put another way, if you didn't subtract 1 from $k$, you'd be able to add the same element multiple times.


M is a Determinstic TM with one tape, c2 is c1 reachable, if it's reachable within finite positive time

Since no answer has been posted I will attempt the answer my self:
Since Giacomo explained why $L$ is TR(I thank him for that) I won't talk about it.

I will prove $L$ is not decidable:

We do that by building a machine $K$ that will decide the halting problem $L_{1}$ using $G$ the decider of $L$ that we assume exists.

$L_{1}$={< $R$, $w$ > | $R$ is a TM; $w \in \Sigma^{*} $; $R$ halts on $w$ }

Description of $K$:

Build TR $H$ that has a configuration $c$ as follows:

"Configuration $c$": On input <$R$, $w$ > if $R$ halts on $w$ go to configuration $d$ which on any input goes back to configuration $c$.
else go to configuration $e$ and loop forever.

Run $G$ on input <$H$,$c$ > if $G$ accepts, accept else reject.(if $H$ accepts $K$ accepts and vice-versa)

Giving < $R$,$w$> to $K$ as input, $K$ will decide if $R$ halts on $w$  if and only if (iff) $G$ decides if $c$ is reachable from $c$ in $H$.

But we know that the halting problem is not decidable in contradiction to what we have assumed in the first place, so $G$ cannot exist there for $L$ is not decidable.


Question about ε-moves at $\varepsilon NFA$

In an $\varepsilon NFA$, when processing an $\varepsilon$ character, we can move on an $\varepsilon$-edge or we can stay on the state we are currently in.
And for example since $a= \varepsilon a \varepsilon\varepsilon$, in your $NFA$ these two paths are both correct:

$$p \rightarrow^{\varepsilon} p \rightarrow^{a} q \rightarrow^{\varepsilon} s \rightarrow^{\varepsilon} s$$

and

$$p \rightarrow^{\varepsilon} p \rightarrow^{a} q \rightarrow^{\varepsilon} q \rightarrow^{\varepsilon} s$$

Therefore, with the character $a$ we have $\delta(p,a)=q$ and for the word $a$ we have $\hat{\delta}(p,a)=\{q,s\}.$


Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

I think you are mistaken, they are needed but the dot look-ahead there is so obvious that you have not paid attention to the fact it is used.

First, let's remark that there are three kinds of items:

those in which the dot is just before a non-terminal. They never participate in an ambiguous situation: when a non-terminal has been produced, it is shifted.
those in which the dot is at the end. They have the item look-ahead and the dot look-ahead which are equal (what may follow the dot is what may follow the produced non-terminal when the production is reduced as the dot is at the end of the item).
those in which the dot is just before a terminal.  They have the item look-ahead and the dot look-ahead which are different.  The item look-ahead is what may follow the non-terminal when the production is reduced, the dot look-ahead start by the terminal which follow the dot and continue with what can be generated after that terminal.

Now, with a look-ahead of 1 or less, the dot look-ahead is trivial: either it is the item look-ahead or the terminal which is just after the dot and that's what you are using to solve a conflict (or decide that there is no way with the limited look-ahead you have).  With a look-ahead of 2 or more, you have to compute the dot look-head or you may not know if you have to shift or to reduce as in the example provided by Grune and Jacobs:

$$\begin{array}{l}
S \rightarrow Aa \; | \; Bb \;| \;Cec \;|\; Ded \\
A \rightarrow qE \\
B \rightarrow qE \\
C \rightarrow q \\
D \rightarrow q \\
E \rightarrow e \\
\end{array}$$

which has the state:
$$\begin{array}{lcc}
&\textrm{item look-ahead}&\textrm{dot look-ahead}\\
A \rightarrow q \cdot E & a\#  & ea\\
B \rightarrow q \cdot E & b \# & eb\\
C \rightarrow q \cdot   & ec   & ec\\
D \rightarrow q \cdot   & ed   & ed\\
E \rightarrow \cdot e   & a \# & ea\\
E \rightarrow \cdot e   & b \# & eb\\
\end{array}$$


Prove that two different concatenations of relations are equivalent

This is best carried out using notations from algebra of relations.

You're asked to prove $RSRRSR \leq RSRSRS$. That $R$ is transitive means $RR\leq R$, so  $RSRRSR \leq RSRSR$ by monotonicity of composition. That $S$ is reflexive means $I\leq S$, where $I$, the identity relation, is neutral element for composition: $I\leq S$ entails $(RSRSR)I\leq (RSRSR)S$ (monotonicity of composition again). Finally, you have

$(RSR)^2 = RSRRSR \leq RSRSR = RSRSRI \leq RSRSRS = (RS)^3$

as required.


I think your interpretation is correct. $q_i$ and $q_{ii}$ are states that guarantee that $10$ and $100$ will be correctly accepted. It is clear that any other input of size $\leq 3$ will be rejected.
Now suppose you are in state $q_s$, the tape is $1Z^{2^k}u$ (with $u\in \{0,1\}^*$), and the head is in position of the first $Z$ of the tape. The cycle $q_s, q_d, q_r, q_l$ will let you do round trips, each trip transforming a $Z$ in $Y$, and a $0$ in $X$.
On the last trip, you will transform the last $Z$ in $Y$, then cross all $X$'s (in $q_{pf}$), and transform a zero in $X$. Therefore, if $u\neq 0^{2^k}v$, the Turing machine will reject. If not, we will get in $q_f$.
If $u = 0^{2^k}v$, then three cases are presented:

$v = \varepsilon$, we finish in $q_{acc}$ so the word is accepted (and the input was necessarily $10^{2^{k+1}}$);
$v = 1w$, we reject;
$v = 0w$, we transform all $X$'s and $Y$'s into $Z$'s, reach the left most symbol (which must be 1), and finish in $q_s$. The tape is then $1Z^{2^{k+1}}v$ and we are in the first situation.


Is final state mandatory in DFA(Deterministic Finite Automata)

The definition of DFAs calls for a set of final (aka accepting) states. Nothing requires that set to be non-empty.  But note that a DFA without an accepting states can't accept any input, so all such DFAs are essentially equivalent to the one you drew.

Having said that, the class of languages accepted by DFAs wouldn't change if you insisted that every DFA must have at least one accepting state. You could still accept the empty language with an automaton whose state graph was disconnected, with all accepting states unreachable from the initial state. If you insisted on at least one accepting state and a connected state graph, the empty language wouldn't be accepted by any DFA.


Is it possible to do Dependent Types in Typed Racket?

Dependent Types in Racket are being worked on by Andrew Kent at Indiana University.

There is a set of slides. There is a talk.

Of interest, this potentially also impacts Typed Clojure, which is strongly modeled on Typed Racket.


Yes, a 3-SAT formula $\phi$ can be transformed into a 1-in-3 SAT formula $\phi'$ while preserving the number of satisfying assignments.  To avoid ambiguities I will use "$\vee$" between literals of a 3-SAT clause, and commas between literals of a 1-in-3 SAT clause.

Let me preliminarily show that, given two literals $a$ and $b$, we can simulate a new type of clause $(x = a \wedge b)$ that forces the value of a new variable $x$ to be $a \wedge b$ using only 1-in-3 SAT constraints, without introducing any new solution.

Consider the cluases:
$$
(\overline{b}, c, x) \wedge
(a, c, d) \wedge
(\overline{a}, e, x) \wedge
(b, e, f)
$$

If $a=\top$, and $b=\top$, then the 2nd and 4th clauses ensures that $c=d=e=f=\bot$. The 1st and 3rd clauses then ensures that $x=\top$.

If $a=\top$, and $b=\bot$, then the 2nd clause ensures that $c=d=\bot$. The 1st clause then ensures that $x=\bot$.
The 3rd clause ensures that $e=\top$, and the 4th clause implies $f=\bot$.

The case $a=\bot$, and $b=\top$ is symmetric.

If $a=\bot$ and $b=\bot$, then the 1st and 3rd clauses imply $c=e=x=\bot$.
The 2nd and 4th clauses ensure $d=f=\top$.

I am now ready to transform a formula $\phi$ of 3SAT to a formula $\phi'$ of 1-in-3 SAT.
Consider now a clause $(a \vee b \vee c)$ of $\phi$. This can be transformed into the following equivalent 1-in-3 SAT clauses:

Add a new variable $x$ that is true iff $a$ is false and $b$ is true. This is encoded by the clause $(x = \overline{a} \wedge b)$.
Add a new variable $y$ that is true iff $a$ is false, $b$ is false, and $c$ is true. We will need an additional variable $z$. The clause $(z = \overline{a} \wedge \overline{b})$ ensures that $z$ is true if and only if $a$ is false and $b$ is false. Then, the value of $y$ can be enforced by the clause $(y = z \wedge c)$.
If $(a \vee b \vee c)$ is true then at least one of $a$, $b$, or $c$ is true. This means that exactly one of $a$, $x$, and $y$ is true. On the converse, if  $(a \vee b \vee c)$ is false, then at all of $a$, $x$, and $y$ are false. This shows that $(a \vee b \vee c)$  is satisfiable if and only if $(a, x, y$) is satisfiable.

We have then constructed an equivalent 1-in-3 SAT formula $\phi'$ that uses a superset of the variables of the original 3 SAT formula $\phi$.
A truth assignment to the variables of $\phi'$ satisfies $\phi'$ if and only if the assignment restricted to the variables of $\phi$ satisfies $\phi$.
Therefore, if any new solution to $\phi'$ is introduced, it must be because of the newly added variables $x$, $y$, and $z$ (one set for each clause). However, the values of these variables are completely determined by the values of the variables of $\phi$.


How to implement a prolog interpreter in a purely functional language?

Since Prolog = Syntactic Unification + Backward chaining + REPL

All three parts can be found in Artificial intelligence: structures and strategies for complex problem solving by George F. Luger. In the fourth edition of the book all three parts are implemented in LISP in Section 15.8, Logic Programming in LISP. He also puts the same code in his other books, but I don't have all of them for noting here. The code for his books can be found here.

Another source with all three parts can be found in Paradigms of artificial intelligence programming: case studies in Common Lisp by Peter Norvig. See Chapters 11, Logic Programming and 12, Compiling Logic Programs. The code for his book can be found here.

Another source is Structure and interpretation of computer programs by Hal Abelson, Jerry Sussman and Julie Sussman. See Section 4.4  Logic Programming. The site for the book is here and the code for the book is here.

It is not uncommon to find the unification algorithm with back chaining implemented in many applications if you know where to look; it is especially prevalent in type inferencing in functional compilers. Using the keywords unification or occurs helps to spot the functions. Also most implementations use unif for the name of the unification function.

For a version of Prolog, less the REPL, done in OCaml see Code and resources for "Handbook of Practical Logic and Automated Reasoning" - prolog.ml

A translation of the book code to F# can be found here.
A translation of the book code to Haskell can be found here.

In terms of finding the code, the unification algorithm is easiest to find, then implementations with back chaining imbedded in applications. Finding a fully functional implementation of Prolog in a functional language with an REPL is the hardest. Most of the time the code is not in a format for direct use within PROLOG; it is heavily customized to enhance performance, so you may find the code but it will not be worth the price to tease out the parts you want. My advice would be to read Luger's book and build it up from scratch in your language of choice, even if it means installing and learning LISP and translating to do so.

EDIT

Since this is a duplicate question from StackOverflow and the OP is new and in the comments says:

  To give more context, I'm attempting to implement type inference,
  however the intricate features in the type system of my language
  (Dependent types, refinement types, linear typing to name a few of the
  less common ones) make me feel that it would be useful to base my type
  inference off of the algorithms driving Prolog as to obtain a very
  general algorithm. I will note that I'm entirely self taught, so my
  knowledge is lacking in large areas.

I'll expand on this here, but realize the OP should ask a new question.

For some intro stuff see implementing type inference.

The best book I know on this is Types and programming languages by Benjamin C. Pierce.
The book's site is here. The resources with links to OCaml code is here. And recently started but mostly complete translation of this to F# is here.

Dependent types: pg. 462
Refinement types: pg. 207
Linear logic and type systems: pg. 109


It is really inefficient to access a certain index in a linked list, which is what many sorting algorithms rely on. MergeSort, however, divides and merges lists, which LLs do efficiently. You can find some code and an explanation here.


You normally started by entering a little loader program one word at a time by setting the bits with a line of toggle switches on the front panel, like this:

Wikipedia has a bit of explanation of the process. (Yes, it was tedious.) The little program would then read a larger program off of some convenient input device, which could be a card reader, although the machines I used in those days used paper tape.

It could even be magnetic tape or some other magnetic storage device.

The larger program was the equivalent to the boot loader which is on sector zero of the persistent storage of whatever computer you used to ask this question, so the process is not that different.

A useful innovation was storing the initial boot loader loader in hardwired persistent memory (aka BIOS).

The use of symbolic codes to replace individual binary toggle switches (or equivalent) grew over time, and the distinction between assemblers and "higher level" languages is not a clear line. Fortran was certainly not the first higher level language, but it was extremely important.

(Some of the images come from David Gesswein's wonderfully nostalgic PDP-8 site.)


Textbooks about non-RE languages for undergraduate students

Despite its name, Soare's book Recursively enumerable sets and degrees has lots of information about this. In particular, it covers in pretty good detail the arithmetical hierarchy.
(Incidentally, note that the non-r.e. elements of the arithmetical hierarchy aren't all "r.e.-hard." For example, consider any minimal $\Delta^0_2$ degree, that is any Turing degree $\le_T{\bf 0'}$ which is nonzero but not strictly above any nonzero Turing degree. There are infinitely many minimal $\Delta^0_2$ degrees; by the Sacks Density Theorem, they are all non-r.e. and hence by minimality don't compute any nonrecursive r.e. sets. The way in which the r.e. degrees sit inside the $\Delta^0_2$ degrees is actually fairly complicated.)


How to use an algorithm to find a satisfying assignment in polynomial time?

The algorithm that decides 3-SAT just answers yes or no, satisfiable or not. It doesn't (directly) give you an assignment for the variables. You have to use the decision algorithm as a black box to find an assignment of the variables. You should try adding a something to your formula that lets you deduce the assignment of a particular variable without changing the satisfiability.


A transaction in database management system is a collection of tasks to be done by the system with certain guarantees on results depending on the type of the transactions.
A process in OS is an implementation for a container which runs programs/code. Different kinds of processes (often just two types) have different capabilities.

There is a clear similarity between the two. However, they are different in several ways.

Transactions do not create new transactions. They have a beginning and an end.
Processes can create new processes, they have the beginning but they might not have an end

I believe that with PL/SQL, one can manage to accomplish a lot with transaction and with this a transaction might have a close resemblance to a process. For example, with PL/SQL, one can declare variables and use them in the same way that a process stores values and states in its virtual memory address. So in this way, a transaction and a process are very similar. This is about Turing completeness of PL/SQL. Transaction performs task written in PL/SQL language, and process performs task in the OS's programming language (which is the binary code of that OS).

One difference between the two is the way they communicate with each other. Transactions can only communicate indirectly with each other via the results of tasks stored in the database. Process can directly communicate with each other as well as indirectly with each other via side effect on the file system (or similar objects).

So the answer to your question:

Transaction is not a process in OS. They are similar concepts, but not the same
A program is not a process. This is because a program might be run by multiple processes
Of course, there are mathematical models behind transaction. Graphs are often used together with many other things. They use a lot of things in database management system theory. If you want to know more, perhaps a new, specific question will be more appropriate.


Pumping lemma for regular languages vs. Pumping lemma for context-free languages

The pumping lemma of context-free languages means finding $x,y,z,v,u$ such $w=xvyuz, |vu|>0,|vxu|\le p$, and for all $n\in\mathbb N$, $xv^nyu^nz$
The regular pumping lemma means finding only $v,y,u$ where $w=abc,|b|>0,|ab|\le p$ and $ab^nc\in L$. ("a","b","c" here are representing sub-words of w)
So, simply take $x=a,v=b,y=c,u=\epsilon,z=\epsilon$


Using Graphs to construct semi-supervised learning solution

One way to express this as a graph is to draw an edge from the document (1984 by George Orwell) to the topic (Surveillance), labelled with the user who approved that relationship (e.g., the label might be: user_believes_doc_is_related_to: "Karl").


Decision problem which belongs to P reduced to a decision problem which belongs to NP?

Of course. Just take B=A, since every P problem is in NP.


Are all known algorithms for solving NP-complete problems constructive?

As I understand it, you are asking two questions: (1) are there e.g. SAT algorithms that are more clever than naive brute force, and (2) are there algorithms that simply give a YES/NO answer when solving an NP-complete problem without actually finding the solution. I'll answer both questions in this order.

(1) It is perfectly possible to solve a problem without brute force, i.e. without naively trying all possibilities. To take your example, modern complete SAT solvers can apply clever algorithms that infer or prove certain (partial) assignments can't lead to a solution, so they don't even examine that part.

More generally, even NP-hard problems often exhibit some kind of algorithmic foothold that allows us to design algorithm faster than brute force. The field of this research is exact (exponential) algorithms. Such algorithms take exponential time, but are still faster than naive algorithms. For instance, you can solve TSP in roughly $n!$ time, where $n$ is the number of cities to visit. This method won't scale to even moderate values of $n$, but there is a classic dynamic programming $O(2^nn^2)$ time algorithm due to Held & Karp. For general techniques, see e.g. branch & bound.

(2) There are "oracle algorithms" for NP-complete problems that just output YES/NO with no explicit certificate. For instance, consider the $k$-path problem:

  (The $k$-path problem) Given a graph $G$ and an integer $k$, is there a simple path in $G$ on $k$ vertices?

The above problem is easily seen to be NP-complete. An $O^*(2^k)$ algorithm for the problem is given in [1]. The algorithm itself only gives a YES/NO answer to the problem, but we can use additional tricks to construct the actual $k$-path itself. More generally, when given such an "oracle algorithm", one can use tools from combinatorial group testing for extracting the witness itself.

[1] Williams, Ryan. "Finding paths of length $k$ in $O^*(2^k)$ time." Information Processing Letters 109.6 (2009): 315-318. publisher link, PDF


Are there programs that can 'translate' source code between any two languages?

TLDR; this is possible but not practical.

  (assuming the translator has access to the requisite libraries)?

This ends up being the tricky bit, and is part of why things like this don't end up being used in practice.

All compilers are translators. Translating from one language to another is definitely possible, and this is literally all a compiler is doing. The language that a compiler spits out as output is generally machine code or assembly, but this is just another language, and there are compilers (sometimes called transpilers or transcompilers) which translate between two languages. For example, there's a gamut of compile-to-Javascript languages like PureScript, Elm, ClojureScript, etc.
Translating between any two Turing Complete languages is always possible. Ignoring things like library calls and FFI and other nasty practical bits that get in the way, that is. If a language is Turing Complete, then you have:

A translation that converts a Turing Machine to code in this language
A translation from this language into a Turing Machine

So to translate from language A to language B, you convert the A code into a Turing Machine, then convert that machine into B code.

Of course, in practice, the practical bits get in the way, and this also requires you having the translations accessible to you. They exist for basically every language, but that doesn't mean someone has taken the time to write them out.
Doing this translation efficiently is hard. Different language prioritize different things. For example, if you translate from C to Python, you're probably going to have to end up simulating C's memory as a Python dictionary, so that you can do pointer arithmetic. There will be overhead associated with this, because you're now not accessing the bare metal memory instructions.

Different languages have difference performance priorities, so something that one language optimizes (or rather, an implementation of one language optimizes) might be impossible to do quickly in another language. Translating a functional language with proper tail calls will have slowdown if you translate it into a language without proper tail calls.
Doing this translation doesn't make the code readable. It's easy to get a piece of code in language B that behaves the same as the code from language A. It's hard to make it look like code a human would have written in B, for a number of reasons. A and B might have different abstraction tools, and the computer has no idea what makes code readable. This will be particularly true if you end up using the Turing Machine translation I described earlier.

This raises the question: what's the point of such a translation? If all you get at the end us a block of slow, unreadable code, why not just compile it to machine code and use some kind of FFI or inter-process communication to link the pieces together?

There are some exceptions to this. Sometimes you need things in a certain language (like JavaScript). Sometimes language are similar, and a sensible translation is easy. Sometimes a language is not meant to be run, but to have its code extracted into another language (such as Coq).

But in general, it's not a very practical thing.


Why do Alice and Bob get the same key even after modular reduction in Diffie-Hellman Cryptography?

In general, we have that $a\cdot b \mod n = (a\mod n) \cdot (b\mod n) \mod n$ for any positive integers $a,b,n$. To see this, we write $a= k n +r_a$ and $b=ln+r_b$, where $r_a= a \mod n$ and $r_b = b\mod n$.
So, we get
\begin{align}
a\cdot b \mod n &= (kn +r_a) (ln+r_b) \mod n \\
&= kln^2 +knr_b + ln r_a + r_ar_b \mod n\\
&= n (kln +kr_b + lr_a) + r_ar_b \mod n\\
&= r_ar_b \mod n\\
&= (a\mod n) \cdot (b\mod n) \mod n
\end{align}

From this, it follows that $a^b \mod n = (a\mod n)^b \mod n$ for any positive $a,b,n$. Using this equality, we can 'move' exponents through modular reductions, from which your equality follows.


Is it possible to obtain a total function by composition of partial functions?

The theorem should be read as "If you compose computable functions, you get a computable function; if you compose partial computable functions, you get a partial computable function."

Note that, perhaps confusingly, partial computable is a larger class of functions: every computable function is partial computable.  One could reduce the confusion at the cost of verbiage by calling them total computable functions and partial-or-total computable functions.  If you compose total computable functions, the result is a total computable function.  If you compose partial-or-total computable functions, the result is a partial-or-total computable function.

Your example in the question shows that it's possible to combine a total function and a non-total function to get a total function. Notice that both examples actually only apply total functions directly to the inputs and at least one of the inputs to the non-total function is the output of a total function. In those circumstances, it's still possible to get a total function as the result of the composition.  Conversely, if you apply a non-total function directly to your inputs (and none of its inputs is the output of some total function), your composition is guaranteed to be non-total.


How does one show $(\lambda x . (\lambda y.x))yx \equiv_{\beta} y$ in lambda calculus?

I will make my answer more sophisticated by using parentheses. The first thing to realize is that $(\lambda x . (\lambda y . x)) y x$ is the same thing as $((\lambda x . (\lambda y . x)) y) x$ because in $\lambda$-calculus application associates to the left, which means that $A B C = (A B) C$. As you can see, $x y$ does not even appear in your expression.

After that, I would follow Yuval's observation that it is impolite to use the same variable for two different purposes: the $x$ and $y$ inside $\lambda$'s are not the same as the outer $x$ and $y$. We should rename bound variables to get
$$((\lambda a . (\lambda b . a)) y) x$$
Can you do it from here?

P.S. Please stop pelting us with questions about $\lambda$-calculus that all look alike. Take them one at a time, wait for the answers, and think about them. It is likely subsequent questions will become redundant.


A variant of the set cover problem: Is that a known problem?

Hint: Form a bipartite graph which has the sets $S_1,\ldots,S_n$ on one side and the numbers $1,\ldots,n$ on the other. Connect $S_i$ to $a$ if $S_i$ contains $a$. You are looking for a perfect matching in this graph.


I can't believe I didn't see this before — but yes, with an oracle for $L$ you can solve the halting problem.  Obviously an oracle for $L$ gives us 'recursively' all non-Busy Beaver halting machines, so the question is 'can we figure out recursively in $L$ what the busy beavers are?'.  Define $\Sigma_2(n)$ as the count function of the 'second busiest beaver'; that is, the second-highest attainable score among all halting two-symbol $n$-state TMs.  The trick here is that there's a recursive function $f()$ such that $\Sigma(n)\leq\Sigma_2(f(n))$ (it's almost certain that $f(n)=n+1$ will do the trick, in fact, but that requires knowing that the BB function is strictly increasing) : given a machine $M$ of size $n$ that prints $\Sigma(M)$ 1s on its tape and then halts, there's some $c\gt 1$ and two machines each of size $\leq cn$ that print exactly $\Sigma(M)$ 1s and exactly $\Sigma(M)+1$ 1s, respectively, on their tapes — and this holds true for a 'busy beaver' machine $M$ even though we don't know $M$ explicitly.  This means that having a bound on the 'second busy beaver' function for $f(n)$ gives a bound for the busy beaver function on $n$; but then having this, it's easy to solve the halting problem for a TM $M$ of size $n$ - if $\langle M\rangle\in L$ then say that $M$ halts; otherwise, find the longest-running machine of size $f(n)$ in $L$ (which can be done recursively since there are only finitely many machines of size $\leq f(n)$) and simulate $M$ for as many steps as that machine takes to halt.  If $M$ doesn't halt within that time then $M$ can't possibly halt.


Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?

Consider the following series

$S = n + \lceil n/2 \rceil + \lceil n/4 \rceil + ... + 1$

There are $\lceil \log_2 n \rceil + 1$ terms but the sum is less than $2^{\lceil \log_2 n \rceil+1} < 4n$ always.

Similarly, in your algorithm even though you have $\log n$ recursions, each recursion successively does a fraction of work. Hence the total work done in linear in $n$, rather than $\Theta(n \log n)$ as the naive analysis suggests, just similar to the sum of the series above. '

Also note that $T(n)$ is $O(n)$ as well as $O(n\log n)$. This is because $O(n\log n)$ is also an upper bound to $T(n)$ and therefore it is incorrect to say, for example, "Why  is $T(n)$ not $O(n\log n)$?".


How can a 64KiB computer do the same task as a modern computer?

The key considerations are infinite memory and unlimited time.  If those two considerations were met, then all modern computers are equivalent.  Since no real computers have infinite memory, and no real humans can afford to wait forever for a calculation, that equivalence is more conceptual than real.


Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?

A problem size of $N$ encoded in unary is size $N$ and $\log N$ if binary. If the time taken is $F(N)$, this is $F(\text{size})$ in the first case and $F(2^{\text{size}})$ in the second case. So an algorithm that is polynomial for the first case will probably be exponential for the second. The encoding of the problem can so change the complexity of an algorithm radically.


A simple answer is "binary search". Keep track of a lower bound (starts out with 1) and an upper bound (starts out with $n$). In each iteration compute the midpoint $m$. In polytime check if $m∗m=n$. If so, terminate. Otherwise, if $m∗m>n$ reduce the upper bound to $m$, else increase the lower bound to $m$. If the upper bound and the lower bound become the same and the midpoint squared is not equal to $n$, then $n$ is not a perfect square. This terminates in $\log n$ steps, which is polynomial in the bit size of $n$, i.e., the length of the input. Each iteration runs in polynomial time as well, so the overall algorithm runs in polytime.


Enumerating every "partnering" without repeating partners

If $|S|=2N$, then the largest "partnering" is a $1$-factorisation of the complete graph, or a round-robin tournament schedule. There always exists a schedule that pairs all people exactly once in $2N-1$ rounds without repeating pairs. There are various algorithms to find such a schedule, see the previous link.


Half precision floating point question -- smallest non-zero number

In this example, $2^{-10}$ is the mantissa, and $2^{-14}$ is the exponent.
For a fuller explanation of subnormal numbers in IEEE-754 floating point, see this previous answer.
Your example binary16 (i.e. half-precision) floating point number is a subnormal number because the exponent field is the "all zeroes" pattern. This means:

The significand field contains the fractional part of the mantissa, with an implicit "0" to the left of the binary point.
The exponent is set to $2^{-14}$. For binary32 (i.e. single precision) this would be $2^{-126}$ and for binary64 (i.e. double precision) it would be $2^{-1022}$.

So the number is $+0.0000000001_2 \times 2^{-14} = 2^{-24}$.


how do you define functions with denotational semantics?

People have been writing denotational semantics for all kinds of
languages since the late seventies.  The list must now be quite long,
and include large real languages, but I never tried to check what is in
it. The number of books is probably large too.  What you want is to look at toy
examples.  Anything real is not a good idea for a start. Some are probably in (text)books.

There were some references to such examples in A simple programming language?
You may try it ... I did not check the answers.

In some cases people had to write a formal semantics because they
wanted to prove correctness of the compiler. Still much research on this.

  Denotational semantics are abstract functions that give meaning to
  statements of a programming language. They accept an expression and
  return a value.

Well, only in the sense that any well formed program fragment may be seen syntactically as an expression (a formula), and anything may be seen as a value in
denotational semantics, including functions (values belong to domains ... which you can understand approximately as types). Actually the semantics
function takes a syntactic formula (you can read "formula" as
"abstract syntax tree") and returns a function expressing what that
formula is supposed to mean ...  or to do when run as (part of) a complete
program.

How you write the semantics, and what domains you use is highly
dependent on what kind of features exist in you language. For example,
if you have exceptions, things may get a bit more complicated.

But just try toy examples to begin with.  And then more.


Recursive definition for the length of a string?

Strings are concatenations of characters. Hence, any non-empty string $w$ has a first character $x$ and can be written as $w = x w'$, where $w'$ is the tail string. It follows from the definition of a string's length that $|w| = |x w'| = |x| + |w'| = 1 + |w'|$.


What is the time complexity of a binary multiplication using Karatsuba Algorithm?

You're mistaken.
The analysis of the Karatsuba algorithm takes addition and subtraction into account.

If you analyze your pseudo-code, you can see that you have exactly 3 recursive function calls with arguments of size $n/2$, and all other operations like addition, subtraction, extracting the higher and lower bits, ...,  run in $O(n)$.

Therefore you get the recursion $T(n) = 3 \cdot T(n/2) + O(n)$ for the complexity, which gives the following according to the Master theorem: $$T(n) = \Theta(n^{\log_2 3}) = \Theta(n^{1.58...})$$

Fun fact: even if you assume that all the bitwise operations (addition, subtraction, ...) take $O(1)$, the code will still have the same complexity.
Since the number of calls to the three subproblems dominates the other work. But I doubt, that any book/lecturer would assume that the bitwise operations are constant, since the whole point of the algorithm is that you want to multiply large numbers.

Btw, you have some small errors in your pseudo-code/analyze.
E.g. here:

long resA = a * (long) Math.pow(10, (2*halfMax)); // takes O(1)

You want to multiply with a power of 2, to make it efficient (since you are working with binary numbers). And even corrected it will not run in $O(1)$, because you need to copy/move $O(n)$ bits. So this line will also run in $O(n)$.


Example of a simple recognizable language, whose complement is not recognizable

The set of recognizable languages whose complement is not recognizable is $RE\setminus R$. This holds since if $L,\overline{L}\in RE$, you can run the machines for $L,\overline{L}$ simultaneously and decide $L$. An example of a language in this set is the famous halting problem.


Number and probability of random allocations of n processes to n servers

The number $n^n$ can be easily obtained if you think the problem in the other direction: each process has $n$ choices and therefore $n$ processes has $n^n$ possible choices in total. Of course it is impossible that two servers have $n$ processes. If a process can be assigned to more than one server, the number of possible assignments is far more than $n^n$.


Since NP-Complete problems can be reduced to each other, If we can reduce a problem to a specific NP-Complete problem. It means that we can reduce it to any NP-Complete problem.
The reason is All problems in NP-Complete can be reduced to SAT and SAT to 3-SAT and 3-SAT to CLIQUE and so forth. So reducing to a problem in NP-Complete means reducing to all problems in NP-Complete.


You can count the number of times the innermost for loop is executed by counting
the number of triplets $(i,j,k)$ for which it is executed.

By the loop conditions we know that: $1 \leq i \leq j \leq k \leq n$ . We can reduce it to the following simple combinatorics problem.

Imagine $n+2$ boxes of red colour placed in an array from left to right.
Pick any 3 boxes from the $n+2$ boxes and paint them blue.
Form a triplet $(i,j,k)$ as follows:

$i$ = 1 + number of red coloured boxes to the left of first blue box.
$j$ = 1 + number of red coloured boxes to the left of second blue box.
$k$ = 1 + number of red coloured boxes to the left of third blue box.

So, we just need to count the number of ways of picking 3 boxes from $n+2$ boxes which is $n+2 \choose 3$.


Every language can be partitioned into a countable union of singleton languages (languages of the form $\{w\}$). Since singleton languages are regular, we get that every language can be partitioned into infinitely many regular languages.


PDA and CFG of language of regular expressions

Hint:  Let us assume an alphabet $\Sigma$. Now, the following are regular expressions (at least according to some textbooks):

$a$ is a regular expression, if $a \in \Sigma$
$\emptyset$ is a regular expression
$r_1 \cup r_2$ is a regular expression, if $r_1$ and $r_2$ are regular expressions
$r_1 \circ r_2$ is a regular expression, if $r_1$ and $r_2$ are regular expressions
Nothing else is a regular expression.

How can you summarize these formation rules as a collection of context-free production rules where $r$ is a nonterminal?


Boolean circuit with two inputs and advice input is hard-wired

Just imagine the circuit $D_n(x,\alpha)$ has $n+a(n)$ bits of input, where the first $n$ bits are treated as the first parameter for the machine $M$, and the last $a(n)$ bits are treated as the advice. To forget about this separation and have a simpler notation, we just say $D_n$ accepts two inputs. Now fix the "second parameter" with the correct advice $\alpha_n$, and this induces a polynomial circuit for $L$ with $n$ inputs.


No. If I have three symbols with probabilities A = 0.5, B = 0.25 and C = 0.25 then A=0, B=10, C=11 is complete and optimal. B=0, A=10, C=11 is complete but absolutely not optimal.

An optimal code on the other hand must be complete, because otherwise you can shorten the encoding of some symbol.


What did Turing's mysterious small programme on the Manchester computer calculate?

You're right that this has to do with encryption, but it's not encryption per se. It's something called hashing. What his program does is take a number, hash it, and output the hash. What Turing created is now called a cryptographically secure hash.

A modern cryptographically secure hash must do the following. It should be easy to hash the input, but very difficult to 'unhash' an output to get the input. In this case, "very difficult" usually means "it would take months or years on a supercomputer, if not even longer."


Efficiently generating a uniformly random list of unique integers in a range

Here is a solution in $O(n\log n)$ (with high probability). We consider two cases: $n\log n \geq m$ and $n\log n \leq m$. In the first case, we choose a random permutation of $[0,m)$ and take only the first $n$ elements. This takes time $O(m) = O(n\log n)$. In the second case, we maintain a balanced binary search tree (or equivalent), adding to it random elements from $[0,m)$ one by one, checking for duplicates each time. In expectation we need to try at most $1/\log n = o(1)$ extra times for each element, so the expected running time of this algorithm is $O(n\log n)$. In fact, the running time is $O(n\log n)$ also with high probability.

We can obtain an expected $O(n)$ solution by replacing the balanced binary search tree with a hash table, and changing the cutoff to $n \geq m/2$ versus $n \leq m/2$.


An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Some keywords to help you search for related work: dynamic transitive closure, dynamic reachability problem, dynamic cycle detection.  Because you want to allow both insertions and deletions, this is known as fully dynamic transitive closure.

Alternatively, you might want to consider whether there could be some structure in the particular graphs that arise in your setting that might help you build schemes that are faster than the general case.


What is the Big Theta of $(\log n)^2-9\log n+7$?

There is no such thing as "the" big $\Theta$ of a function. For a given function $f(n)$, many functions $g(n)$ satisfy $f(n) = \Theta(g(n))$. For example, every function satisfied $f(n) = \Theta(f(n))$.

However, usually we are interested in a "succinct", "canonical" or "simple" expression $g(n)$, for example of the form $c^n n^a (\log n)^b$, for some $c \geq 1$. In your case $g(n) = (\log n)^2$: your function is $\Theta((\log n)^2)$, which is not too hard to show.

Setting the proof apart, how do I know that your function is $\Theta((\log n)^2)$? Since $(\log n)^2$ is the dominant term: all other terms ($\log n$ and $1$) grow slower than $(\log n)^2$. The constants in front of them don't matter asymptotically.


Is there any difference between the terms userland and userspace?

Taken from yourdictionary.com

  Userland: (computing, informal) A conceptual space outside the kernel in which a user's applications can run without the risk of damage to the operating system.

  Userspace: (computing) The area of memory used for a user's applications, etc., as opposed to that reserved for the operating system


You're almost there, but you need the right notation. Let's start with the alphabet $\Sigma = \{a,b\}$. Then the regular expression $(a+b)$ represents a set of two strings, namely $\{a,b\}$. The expression $(a+b)^2$ represents the set of the strings $\{aa, ab, ba, bb\}$. The expression $(a+b)^3 \ldots$ The expression $\{a,b\}^*$, also denoted $\Sigma^*$, represents the union of all these sets. Each of these sets is called a language, and so $\Sigma^*$ is also a language. So $\Sigma^*$ is one language, not the set of all languages, over the alphabet $\Sigma$, and it contains all the strings you can form out of that alphabet.

The set of all languages you can form using that alphabet is the power set of $\Sigma^*$, denoted by $\mathcal{P}(\Sigma^*) = \{L | L \subseteq \Sigma^*\}$. That is, if $L$ contains only strings from your alphabet, then $L$ is a language over $\Sigma$, so $L$ is an element of the set $\mathcal{P}(\Sigma^*)$. Now, some of these languages are regular, and some are not. Certainly the language $\Sigma^*$ is a regular language, and $\emptyset$ is a regular language (you can draw their finite automata and see that they are the two simplest automata). Other languages, such as $\{a^nb^m|n+m \text{ is prime}\}$ are not regular. I hope that clears some things up.


Given the logical address, how to extract the page number?

Your logical address is made of 16 bits, that means you have a addressable space of $2^{16}$ bits. The page size is typically a power of 2, $2^n$, in this case $2^n = 256 \Rightarrow n = 8$.

The page number is calculated by substracting $n$ from the size of your logical address: $16 - 8 = 8$, so the first 8 bits of the address are your missing page number, that is 0xAE


Access a tree by level without traversing

To support the operations mentioned - especially level-order traversal (or walk) - in time bounded by the depth, you don't need an extra attribute for each node.

For a "semi-static" tree¹, you could use an array of nodes to store it:
For every level, keep the index just beyond.
For every node, keep parent, for non-leaf nodes, children ("first" child), too:
siblings are successive nodes with same parent.

For a "dynamic" tree, modify the [typical] tree structure keeping children, siblings and optionally parent to support level-order traversal:
Change sibling to next in same level - not a sibling iff different parent.
You may need support for first in level, or "the list of nodes in the same level" to be circular to be able to access all of them starting from any-one thereof.

[1]: semi-static tree: only structural change is addition of nodes.
(The task sketched may have another restriction: no node with children will get another child once a different node gets one.)
(or even static: [once] the tree is completely initialized)


How is the loop invariant obtained in this square root bound finding algorithm?

Gilles is right that the general technique is to go fishing for interesting observations.

In this case, you may observe that the program is an instance of binary search, because it has the following shape:

while i + 1 != k
  j := strictly_between(i, k)
  if f(j) <= X then i := j
  if f(j) > X then k := j

Then you just plug in your particular f, X, ... into the general invariant for binary search.  Dijkstra has a nice discussion of binary search.


How does strong NP-completeness agree with encoding complexity?

I figured it out after looking at this paper. My error in thinking came from generally assuming some direct (i.e. linear) relationship between the numbers in the source problem and those in the target problem to which the reduction is mapping. However, producing unary output in the reduction in polytime requires that such a connection must only exist in those cases where the source problem is a number problem which has its numerical values polynomially bound in its binary input length. If, on the other hand, the source problem is allowed to have exponentially large numbers, the #bits required to encode the numbers in the target problem may only scale logarithmically with the #bits required for the numbers in the source problem, ensuring polynomial boundedness of the maximum value and enabling changing from binary to unary encoding in polytime.


Maximizing the minimum of $k$ submodular functions

Krause, McMahan, Guestrin and Gupta, who call this problem Robust Submodular Observation Selection show that is is NP-hard to approximate this problem to within any constant.


Number of n-node binary trees containing an m-node binary subtree

You haven't defined what a subtree is, so let's assume that $S$ is a subtree of $T$ if there is a node $x \in T$ whose subtree is isomorphic to $S$ (the notion of isomorphism depends on the definition of subtree).

Now suppose $S_1,S_2$ are two trees on $m$ of vertices. For any tree $T$, mark all the nodes whose subtrees contain $m$ vertices. Define $\pi(T)$ by replacing all such nodes whose subtree is isomorphic to $S_1$ by a subtree isomorphic to $S_2$, and vice versa. For any $n$, this is an involution on the set of trees on $n$ vertices which satisfies the following property: $T$ contains $S_1$ iff $\pi(T)$ contains $S_2$. This shows that the number of trees of size $n$ containing $S_1$ is the same as the number of trees of size $n$ containing $S_2$.


Request for examples regarding PAC learnability

You can find a proof for the equivalence between PAC and agnostic PAC learning in theorem 6.7 of "Understanding Machine Learning" by Shai Ben-David and Shai Shalev-Shwartz. The proof goes through showing:

$\mathcal{H}$ is PAC learnable $\Rightarrow$ $\mathcal{H}$ has finite VC dimension (lower bound on sample complexity).
$\mathcal{H}$ has finite VC dimension $\Rightarrow$ $\mathcal{H}$ is agnostic PAC learnable (upper bound on sample complexity)

If you don't care about the bounds being sharp, $1$ is not too hard, but $2$ is definitely beyond the scope of this site. Combining the above results with the fact that agnostic PAC learnability implies PAC learnability concludes the proof.

In regard to your second question, let $l_1$ be the 0-1 loss function and $l_2$ be a loss function which is nonzero only on a finite subset of $\mathcal{X}$ and is the 0-1 loss in that region (suppose you only care about very specific mistakes). Take any class with infinite VC dimension, then it is not agnostic PAC learnable with respect to $l_1$, but is learnable with respect to $l_2$ (If the loss function is nonzero only on a finite region, you can treat this case like having a finite hypothesis class).


Relationship between Higher Kinded Polymorphism, type inference, and Currying

I imagine what the comment writer is referring to is this...

Consider type inference in Haskell. At some point, we may be asked to solve the unification problem f a = Maybe Int. This is very easy to solve (f = Maybe, a = Int), but only because we have restricted the allowable solutions. The solution to f may only be built out of (partial) applications of type 'constructors' (like Maybe) and variables. Another example is f a = (b, a) with solution f = (,) b. I suspect this partial application is what is meant by "currying". Note that f Int = (Int, Double) just fails.

Now consider (until somewhat recently) Scala. For one, there was no inherent notion of left-to-right partial application like the above. To even write a partially applied type required giving it a name via some rather baroque syntax. But more importantly, it made no commitment to the restrictions that made things easy in the last paragraph. This has the 'advantage' that you can make f Int = (Int, Double) work. A solution is f = λa. (a, Double). However, note that we had to solve for f with a lambda term. This means inference must solve a problem called, "higher-order unification," which is bad, because it's undecidable.

Another (related, I think) problem is that my last solution above wasn't actually unique. Another solution is f = λ_. (Int, Double). Neither of these solutions is more general than the other, they're simply different. So, I suspect it's also the case that higher-order unification doesn't have most-general solutions. This means (I think) that even if it were a solvable problem, the 'right' solution would not be a local property, and would depend on the rest of the program (because some of the multiple possible solutions might not be compatible with other parts of the program where the solution is used).

So, to avoid these problems, it is much easier to restrict the solution space the way Haskell does. It isn't terribly inconvenient to organize things according to this discipline such that you get good inference most of the time. And when unification fails, it's obvious what the problem was, whereas it can get complicated to figure out how to guide the system using higher-order unification with the right annotations.

However, I've heard that newer versions of Scala actually have adopted this type inference methodology. But I still don't think their type functions look "curried" exactly like Haskell's do (i.e. they still look like F[A,B]). So it's probably not essential to do that. The left-to-right partial application rule is the essential part.


Is there a formalization for the trade-off between the expressiveness and the speed of a programming language?

This is a really interesting problem and I don't think there are definitive answers. There are two important, and distinct dimensions to this problem.

What does expressivity actually mean? In the light of the
Church-Turing thesis, which states that all programming languages
are the same (can be compiled into each other). Nevertheless it
seems pretty clear that e.g. assembler programming is quite
different from programming in Python. There is a research field that
studies this. It was pioneered by (1), but much ink has been spilled
since.

In computational complexity theory speedup theorems show that for
any algorithm solving a problem, there is a faster algorithm  solving the same problem. Examples are
Blum's speedup theorem  and the linear speedup theorem. Basically, what those speedup theorems tell you is that you can
always speed up computers (Turing machines) a bit by adding more
powerful commands. In processors we went from 4 bit CPUs to 8 bit,
then 16 bit, the 32 bit and nowadays 64 bit.

Neither quite answers your question, I'm afraid!

(1)  M. Felleisen, On the Expressive Power of Programming Languages.


Doing beta reduction while constructing the boolean expression in lambda calculus

It is helpful to look at $\lambda$ abstractions as functions, e.g. $T \equiv \lambda x y. x$ "is" a function that takes $2$ variables as arguments ($x,y$; those between "$\lambda$" and ".") and returns the first of them - $x$ (expression after the "."). On the other hand, we define $F$ to also take $2$ arguments and return the second one - $y$.

In this sense, $\beta$-reduction is a process of evaluating a function at given values (the ones that abstraction is applied to). One should be careful about $\alpha$-renaming and have in mind currying, but we will not go into that here.

Let's now define the $AND$ operator.

What does it take as arguments?
We can also think of it as a function, and therefore it must take $2$ arguments (truth values), so we would define it something like
\begin{equation}
AND := \lambda a b.\ <body,\ i.e. what\ it\ returns>.
\end{equation}

What does it need to return?
If it receives $T$ and $T$ for it's arguments, it must return $T$. Otherwise, it returns $F$.

Constructing the body.
Having in mind that $a$ and $b$ will be substituted with $T$ or $F$, we can use them in the body of $AND$. We will use their property of returning the first or second argument. Consider the following definition;
\begin{equation}
AND := \lambda a b.\ a\ b\ F
\end{equation}
Upon receiving its arguments $a$ and $b$, operator $AND$ is returning the application of its first argument (and we know it will be a "function" of $2$ arguments that returns either its first or the second argument) onto its second argument and $F$. Therefore, if the first argument ($a$) happens to be $T$, we return the second argument ($b$) as a solution (in other words, the result of $AND\ T\ b$ is $b$). If the first argument ($a$) happens to be $F$, we return $F$.

Cases. There are $4$ cases that can happen.

$AND\ F\ F$. This will evaluate as follows:
\begin{equation}
(\lambda a b.\ a\ b\ F)\ F\ F = F\ F\ F = (\lambda x y.\ y)\ F\ F = F
\end{equation}
$AND\ F\ T$. This will evaluate as follows:
\begin{equation}
(\lambda a b.\ a\ b\ F)\ F\ T = F\ T\ F = (\lambda x y.\ y)\ T\ F = F
\end{equation}
$AND\ T\ F$. This will evaluate as follows:
\begin{equation}
(\lambda a b.\ a\ b\ F)\ T\ F = T\ F\ F = (\lambda x y.\ x)\ F\ F = F
\end{equation}
$AND\ T\ T$. This will evaluate as follows:
\begin{equation}
(\lambda a b.\ a\ b\ F)\ T\ T = T\ T\ F = (\lambda x y.\ x)\ T\ F = T
\end{equation}

This is a somewhat friendly $\lambda$-calculus workflow I presented here, but I think it is the right approach for someone who is starting to learn about it and needs some intuitive notes on its nature.

For further research, following links should be useful as a starting point;

definitions of logical operators: https://en.wikipedia.org/wiki/Church_encoding#Church_Booleans
$\lambda$-calculus interpreter to try out your ideas and see reduction steps; http://jacksongl.github.io/files/demo/lambda/index.htm


Construct this two-taped Turing Machine {(u#,v#):u,v E {a,b}* , |u| = 2|v|}

One possible solution running in linear time:

1) Move head of the first tape to the right until you reach end of $u$ while copying each symbol of $u$ to the second tape. But first write a blank symbol on the second tape as the first symbol.

2) Read $v$ by two symbols and for each pair of symbol of $v$ erase one symbol of $u$ on the second tape (starting from the last symbol and moving backward).

3.1) If all symbols (of $u$) on the second tape has been erased then check if the first head has reached end of the string (of $v$). If "no" then REJECT else ACCEPT.

3.2) If the TM has reached end of the string of $v$ (on the first tape) then check if the second tape is empty. If "yes" then ACCEPT else REJECT.


Can the notation for polynomial reduction, A ≤p B be reversed in computability theory?

The notation $A \le_pB$ means problem $A$ can be reduced to problem $B$ in polynomial time, and that $B$ is at least as hard as $A$, because solving $B$ means solving $A$.

$A \le_pB$ $\equiv$ $B \ge_pA$

It does $\mathbf{not}$, however, mean $B \le_pA$, and to claim as much you would have to show the appropriate reduction.


QuickSort of linked lists optimised for duplicates

The point is that with linked lists you can reorganize them in-place. So, your partition method should return three separate lists: lower, middle and higher. Each list contains nodes from source list, only pointers are manipulated.


What is the time complexity in big-O notation of Algorithm X?

Its worst-case running time is exponential.

By "nondeterministic", this essentially means "try all possibilities".


How to modify Bellman-Ford algorithm for this specific Minimum Cost Flow problem?

Minimum cost path

If you're looking for a minimum cost path, you can find that directly with Bellman-Ford.  Just let the weight on each edge $(i,j)$ be the cost $c_{ij}$, and ask Bellman-Ford to find for you the shortest path from the source to the sink; this will be exactly the minimum cost path (assuming there are no negative cycles in the graph).

Minimum cost flow

If you're looking for a minimum cost flow, one natural approach is to try using the Ford-Fulkerson method.  In each iteration of Ford-Fulkerson, you must find an augmenting path in the residual network.  In your particular case, you might try computing a minimum-cost augmenting path from the source to the sink.  Now what algorithm do you know that can compute a minimum-cost augmenting path in a digraph (potentially with cycles and potentially with negative-weight edges)?  That should be enough of a hint to give you something you can try.  Since it's your exercise problem, I'll let you work out the details and see if you can prove whether it works or not.

Alternatively, if conceptual simplicity is the goal, linear programming (LP) is one approach that is conceptually very simple and might apply to your porblem, and it has a polynomial running time.  LP immediately gives a solution to your problem (though possibly not with integer $x_{ij}$'s), and it's a well-known theorem that you can solve LP in polynomial time.  Of course, LP might be a "bigger hammer" than you want to throw at this.  Also, I don't know if LP will give you an integral flow, which you seem to want.  There's a standard theorem that says that, for the linear program associated with a maximum flow problem, there is always an integral solution to the LP that is optimal (you can't do better with non-integral flows).  I don't know if that carries over to the minimum-cost flow setting as well.


The range of significance in Type Theory

Comes from Russell, and it's actually about the domain, not the codomain, if I understand ol' Bertie correctly. A propositional function like "x>3" only has significance if we limit the possible values of x to numbers.  Today we would call that the domain, but his choice of words is defensible: the range of significance of a propositional fn  is the set of values that make it meaningful - i.e. true or false - as opposed to meaningless nonsense, like "Pegasus>3".  The range of significance of a numeric fn is the set of values for which it yields a value, rather than crashing, so to speak.

The relation to types is fairly obvious: the range of significance of a fn $f: A\rightarrow B$ is just the "values" of type $A$ to which $f$ can be meaningfully applied.  The concept and term "type" is just a more commodious way of expressing the same basic concept.  Google "propositional function range of significance" and you'll get links to his original paper and lots more.


Before I explain what went wrong, notice the following red flag:
Let $T(n)$ be some arbitrary function representing some run-time. What would not work from this "proof" if we replace $n^k$ by $T(n)$? From what I see, pretty much nothing. Does that mean that $SAT$ is not solveable in any run-time? of course not!

Now to the actual problem: Each $\Phi_k$ depends on $n$, so let us call it instead $\Phi_k^n$. Notice, that the size of $\Phi_k^n$ would not be $n$, since it takes a lot of "space" to represent this formula. In fact, its size woul most likely be way bigger than $n^k$. When you run $M$ on $\Phi_k^n$, the runtime would take $O(|\Phi_k^n|^k)\approx O((n^k)^k)$ and not $O(n^k)$, since the runtime depends on the size of the input $\Phi_k^n$. This completely nullifies your argument that this is a contradiction.

As a side note, if you do actually manage to encode $\Phi_k^n$ in some magical way with size $O(n)$, then congratulations! Your argument holds and $P\neq NP$. But clearly its not easy to encode it like that... good luck :)


Why clear the child's and not the parent's mark in Fibonacci heaps?

To understand Fibonacci heaps, it may help to understand binomial heaps first.

A binomial heap is a forest of heap-ordered binomial trees. A binomial tree of degree k is a node whose children are binomial trees of degree k-1, k-2, ... 0. Note that the number of nodes in a binomial tree of degree k is $2^k$.

If you never do any decrease key operations (or delete operations of nodes other than the minimum), then the Fibonacci heap is a binomial heap.

Conceptually, a Fibonacci tree is a binomial tree which allows for a controlled amount of "damage".

The degree of a Fibonacci heap node is redefined to be the number of children that it has. The structural constraint is designed so that the tree can tolerate a certain amount of deviation from the binomial heap constraint. Most textbooks don't precisely define it, but the key property is this:

  Suppose that x is any node in a Fibonacci heap. If you order its children in the order that they were linked to x, then the ith child has a degree at least i-2. If it has degree equal to i-2, the node must be marked. If it is greater than i-2, then it may or may not be marked.

In particular, a mark signifies that a node may be one degree too "small" for its parent. (Note that this property is almost lemma 1 from the original paper.)

The first thing to notice is that when we cut a node, we unmark it. The reason for this should be obvious: it has no parent, so it can't possibly be too "small".

Now think about the link operation. We only ever link two nodes together if they have the same degree. Let's suppose that d is the degree of x and y, and we want to make x the new parent of y.

Since we are adding a child to x, so this changes the degree of x to d+1. The node y is the (d+1)th child linked to x, so to preserve the structural constraint, it must be marked if it has degree d-1. However, by construction it has degree d. It is not too "small", so we unmark it.

Of course, the structural constraint is preserved whether or not y is marked. Why, then, do we clear the mark? Intuitively, it's because encountering a mark during an unlink operation triggers a cascading cut. We want to avoid those, so we want to have as few nodes marked as possible. At any point, if we can tell that a node doesn't have to be marked, we make sure it's not marked.

Did that help?


The final constraint you need to encode is that $k$ or fewer variables in the set ${x_1, x_2, ..., x_n}$ is set true.  There is a good reference question that outlines several methods for encoding a 1-out-of-$n$ constraint.  Those methods can be extended to fit your constraint.  Using a chain of adder circuits plus a comparison circuit seems the most straightforward method to me.


Is it NP complete to decide whether a graph has $k$ disjoint triangles?

For the special case where $n$ is a multiple of 3 and $k=n/3$, this is the PARTITION-INTO-TRIANGLES problem, which is proved to be NP-complete here.
The idea is to reduce 3-DIMENSIONAL-MATCHING (3DM) to PARTITION-INTO-TRIANGLES. I quote the construction here.

Let $X = \{x_1, x_2, \ldots, x_q\}$, $Y = \{y_1, y_2, \ldots, y_q\}$, $W = \{w_1, w_2, \ldots, w_q\}$ and $M \subseteq X\times Y\times Z$ be the generic input instance of 3DM. Construct an initial set of vertices $V$, called the "public vertices", as the union of $X$, $Y$ and $W$. For every triple $m = (x_a, y_b, w_c)$ in $M$, construct the graph $G_m = (V_m, E_m)$, depicted in Figure 1. Here $V_m$ contains the three public vertices $x_a$, $y_b$ and $w_c$ plus three "private vertices" $v_m^1$, $v_m^2$ and $v_m^3$. The ten edges in $E_m$ are $v_m^1v_m^2$, $v_m^1v_m^3$, $v_m^2v_m^3$, $x_av_m^3$, $x_av_m^2$, $y_bv_m^3$, $y_bv_m^1$, $w_cv_m^1$, $w_cv_m^2$ and $x_1y_b$. The whole graph $G_M$ is obtained from the union of all the gadgets $G_m$ as follows: $G_M = (V_M, E_M) = (\cup_m V_m,\cup_m E_m)$.


What is the language of Sigma^n? Confused about meanining

By definition $\Sigma^n$ is simply $\underbrace{\Sigma\times \Sigma \times \cdots \times\Sigma}_{n \ \text{times}} = \{(\sigma_1, \sigma_2, \ldots, \sigma_n): \forall \ i\in [n], \sigma_i \in \Sigma \}$ which is the set of ordered tuples of length $n$ over $\Sigma$. Usually, when we refer to a tuple $w = (\sigma_1, \sigma_2, \ldots, \sigma_n)$, we omit the commas "," and the parenthesis "(" and ")", so the tuple $w$ is written as $\sigma_1\cdot \sigma_2\cdots \sigma_n$ to which we refer as a word of length $n$ over $\Sigma$. In other words, $\Sigma^n$ is the set of all words of length $n$ over $\Sigma$.
Formally, the map that maps a tuple in $\Sigma^n$ to the word that we get by omitting the commas and the parenthesis from the tuples, is a bijection from $\Sigma^n$ to the words of length $n$ over $\Sigma$.


Is a set system an independence system, if and only if it is an accessible system, and has the Interval Property without Lower Bounds

Suppose that a set system $F$ is accessible and satisfies the interval property. We show that it is hereditary. Let $C = \{x_1,\ldots,x_n\}$ be any set. Without loss of generality, by accessibility we can assume that for all $t \in \{0,\ldots,n\}$, $\{x_1,\ldots,x_t\} \in F$. We show by induction that all subsets $B$ of $C$ are in $F$. If $|B| = 0$ then $B = \emptyset \in F$ (the case $t = 0$ above). Now suppose $B = \{x_{i_1}, \ldots, x_{i_k}\}$, where $i_1 < i_2 < \cdots < i_k$. By assumption, $A = \{x_{i_1},\ldots,x_{i_{k-1}}\} \in F$. Now $A \subseteq \{x_1,\ldots,x_{i_k-1}\}$ and both $\{x_1,\ldots,x_{i_k-1}\},\{x_1,\ldots,x_{i_k}\} \in F$, and so by the interval property, $B = A \cup \{x_{i_k}\} \in F$.


How to implement the regret matching algorithm?

The index set of the max operation is $A_i$, the actions of player $i$. The formula says: take each such action $a_i \in A_i$ and compute its regret (with the sub-formula you say you can implement easily), and then take the maximum of those regrets.

The reason for the $\max(R,0)$ is that actions with negative regrets are performing worse than the action currently chosen.

To implement this in code, just set a temporary variable $t$ to be 0. Now loop through the actions one by one, and for each action $a$, compute its regret $r$, and set $t$ as $\max(r,t)$. Note that this approach includes the $\max(R,0)$ operation; to do this without that, set $t$ initially to $-\infty$.


Basic approximation algorithms understanding

According to your definition (which is the standard definition), an algorithm solving a certain minimization problem is an $\alpha$-approximation algorithm for any $\alpha \geq 1$.

Consider a minimization problem solvable in polynomial time, for example minimum cut. Let Alg1 and Alg2 be algorithms solving this problem exactly. Alg1 is a 2-approximation algorithm and Alg2 is a 4-approximation algorithm, yet there is no input on which Alg2 performs worse than Alg1.


How to describe the languages of these regular expressions in plain English?

The first regular expression captures all strings over $\{0,1\}$ not containing two consecutive 1s. It is not hard to check that any string in the language of the given regular expression has this property, and with some more work you can show the converse.

The second regular expression captures all strings over $\{a,b\}$ containing $aaa$ as a (consecutive) substring, as you also noticed.

The third regular expression captures all strings over $\{a,b\}$ not containing $bba$ as a (consecutive) substring, though this perhaps requires some verification.


There are specific applications for which GPUs are useful. For example, they are useful when we want to perform same operation(use same instructions) but for many different data elements in parallel. For example, add 1K elements in parallel. Such workloads are said to have Data Parallelism.

This is not the case with FPGAs. They are highly customisable and can be made to do anything you want and not just highly data parallel operations. Hence, FPGAs offers much more freedom for designers than GPUs.


A variant of travel salesman problem in grid graph

This is similar (but not identical) to the game Zen Puzzle Garden. The important difference for the purposes of your question is that in ZPG you can also have “walkable” squares which the robot (or rather monk, in that game) can walk freely across without leaving a trace.

It is known that ZPG is NP-complete, but our proof makes critical use of these walkable squares and so it does not extend to this problem.

When I was working on the proof above, I spent some time thinking about whether it was possible to show NP-hardness without using walkable squares, but without success. As far as I know the question is still open.


How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$

Your expression is

$$ E = \frac{cn^2}{\log \frac{n(n+1)}{2}}$$

where $c$ is some constant. The simple upper bound for $E$ is

$$ E\le c n^2$$

which implies that $\mathcal{O}(n^2)$. For a better bound

$$E  = \frac{cn^2}{\log \frac{n(n+1)}{2}} = \frac{cn^2}{ 2 \log n + \log n - \log 2 } $$

Now it is an easy verification that $E$ is $\mathcal{O}(\frac{n^2}{\log n})$. In other words $E$ is $o(n^2)$(weaker statement as compare to the previous one).


Why Right-Division of regular language with RE\E language is regualr?

In fact, if $L_1$ is regular then $L_1/L_2$ is regular for any $L_2$.

Indeed, consider a DFA for $L_1$ with transition function $\delta$ and accepting states $F$. We modify the set of accepting states to
$$
F' = \{ q : \delta(q,w) \in F \text{ for some } w \in L_2 \}.
$$

You might object that "$F'$ cannot be computed". So what? We never said that you can compute a DFA for $L_1/L_2$ given one for $L_1$ and some reasonable representation of $L_2$. All we claim is that $L_1/L_2$ is regular.

Check out this question for a similar but simpler situation.


Consider an algorithm with some running time bounded by $f(n)$ and suppose that $f(n) \in O(1/n)$. That means that there is some constant $c$ such that for sufficiently large values of $n$, it holds that $$f(n) \leq c\frac{1}{n}.$$ Clearly, for any fixed $c$ and sufficiently large $n$, the right side will be strictly less than $1$, which requires $f(n)=0$, since $f$ maps to $\mathbb{N}$.
In my understanding, even an algorithm that immediately terminates, takes at least $1$ step (namely to terminate), i.e., $\forall n\colon f(n)\ge 1$. So no such algorithm can exist.


Is Karp Reduction identical to Levin Reduction

No. First note that Levin reduction only makes sense with respect to classes which certificate has a meaning, e.g. $\mathsf{NP}$ while Karp reduction is general. The word "certificate" for a problem makes sense only when a verifier is fixed. Levin's reduction assumes that the verifiers are fixed. You cannot change the verifiers. (In the following I assume that certificate verifiers are fixed as required by definition of Levin reduction.)

Second, Levin reduction means that one can find the certificate for one from the certificate for the other. It is true that the well-known Karp reductions between natural problems turn out to be Levin reduction but this does not need to be true in general.

If we can reduce instances of a problem $A$ to problem $B$ it doesn't mean we have a way of computing a certificate for one from a certificate for the other.

For this to be true we need the fact that a certificate search problem corresponding to the decision problem is polynomial time reducible to the decision problem. This is true for $\mathsf{NP\text{-}complete}$ problems but not known to be true generally even for $\mathsf{NP}$ problems.


In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Finite automatas (either) DFA or NFA, must be process the entire input string.
DFAs will keep track of a single state while processing a string. Think of it as a pointer to the current state. It will transition (i.e. move that pointer) according to its rules while processing a string. Remember that for a DFA, all states must have a transition for each symbol in the alphabet. Thus, the DFA will have a unique path to the final state after processing the entire input string. If final state is an accepting state after processing the entire input string, the string is accepted; otherwise, it is rejected.
NFAs on the other hand will keep track of a set of states while processing a string. Think of it as having a set of pointers to all possible states for which the NFA could have transitioned to after processing a certain number of symbols. This allows for the NFA to not have all transitions defined, the inclusion of $\epsilon$ on transitions, and having a symbol on more than one transition out of a state. If the set of states contains an accepting state after processing the entire input string, the string is accepted; otherwise, it is rejected.
Take the following example:
$L = \{0,1\}^*00^+1 + \{0,1\}^*01^+0$. The following NFA accepts this language.

We can make a chart that shows how the NFA will process an input string. The left column indicates the current set of states (when we start processing we start with {A}). The middle column is the set of states possible from the current set of states after processing a 0, and similarly for the right column with 1.
              0         1
_________ | ________ | _______
{A}       | {A,B,C}    {A}
{A,B,C}   | {A,B,C,D}  {A,C,D}
{A,B,C,D} | {A,B,C,D}  {A,C,D}
{A,C,D}   | {A,B,C,D}  {A,C}
{A,C}     | {A,B,C,D}  {A,C}

Suppose we have an input string 001. The NFA will process the input:
0 from {A}       -> {A,B,C}
0 from {A,B,C}   -> {A,B,C,D}
1 from {A,B,C,D} -> {A,C,D}

We see that the final set of states is {A,B,C,D} which does contain an accepting state. Thus, $001 \in L$. Notices while processing the string, the NFA did not record the way it got to the accepting state; it just records that it is possible to get to one.
Suppose however we have an input string of 0011. The NFA will process the input:
0 from {A}       -> {A,B,C}
0 from {A,B,C}   -> {A,B,C,D}
1 from {A,B,C,D} -> {A,C,D}
1 from {A,C,D}   -> {A,C}

We see then that the final set of states is {A,C} which does not contain an accepteing state. Thus, $0011 \notin L$.

TL;DR
FAs must process the entire input. For NFAs, if the final set of possible state the machine could end in contains a final state, then the input string is accepted; otherwise, it is rejected.


Are all functions with constant space complexity in $REG$?

A regular automaton can do anything a Turing machine can do, as long as the TM uses only O(1) memory. This is because with finite memory, the number of possible states the TM can be in is also finite (It's the number of possible tape contents * the number of possible head positions * the number of states of your TM). You can encode the whole computation graph as one big finite automaton.


Your problem is NP-hard. Consider an instance of Hamiltonian path graph $G=(V,E)$ in which the degree of each vertex is at most $3$ and we are given a starting vertex $s$ and ending vertex $t$ both of degree at most $2$ (the problem remains hard in this case).
W.l.o.g., let $V=\{3,\dots,k-4\}$, $s=3$, and $t=k-4$.
Create the dominoes $(0,1)$, $(1,2)$, $(2,3)$, $(k-4, k-3)$, $(k-3, k-2)$, and $(k-2, k-1)$. Create one "edge" domino $(a,b)$ for each edge $(a,b) \in E$.
There exists an Hamiltonian path in $G$ if and only if there is a sequence of $k-1$ dominoes.
Indeed, notice that any sequence of dominoes that only uses the dominoes from $E$ traces a (not-necessarily simple) path $P$ in $G$.
But then, all vertices except the endpoints of $P$ must be traversed at most once (since their degree is at most $3$). The two endpoints can extend the path by at most $2$. Then the number of edges of $P$ can be at most $|V|+1 = k-6+1 = k-5$. This implies that a sequence of $k-1$ dominoes must use all "non-edge" dominoes, i.e., the sequence of dominoes must start with $(0,1), \dots, (2,3)$ and end with $(k-4, k-4), \dots, (k-2, k-1)$.
Then, the path induced by the sub-sequence obtained by dropping the "non-edge" dominoes must be simple and traverses $k-1-6 = k-7 = |V|-1$ edges of $G$, i.e., it is an Hamiltonian path in $G$.
Conversely, we can create a sequence of $\ell+6$ dominoes from any simple path of length $\ell$ from $s$ to $t$ in $G$ (simply prepend $(0,1), \dots, (2,3)$ and append  $(k-4, k-4), \dots, (k-2, k-1)$). For an Hamiltoniam path we have $\ell=|V|-1=k-7$, therefore the sequence has length $k-1$.


Why doesn't the C/C++ compilers create different tokens for different types of numbers?

This is in fact an implementation detail of the compiler. The page you referenced only shows one way of assigning types to tokens, while there are also others. The compiler could have a lexer that distinguishes between integral and non-integral constants and the parser then cannot match the declaration

int A[10.5];

to any rule. But giving an error message stating exactly this to the programmer is not very helpful. Modern C++ compilers have quite complex parsing and compiling routines that give more information in case of errors. As an example, GCC will yield:

me@my-computer:/tmp$ g++ test.cpp
test.cpp: In function ‘int main()’:
test.cpp:9:15: error: size of array ‘A’ has non-integral type ‘double’
     int A[10.5];
           ^

So you will get quite a good error message, and for obtaining it, some semantic interpretation was actually performed.


Complexity of many constant time steps with occasional logarithmic steps

If every $k$th operation takes $O(\log n)$ time, then the best bound you can get on the amortized complexity is $O(1 + \frac{\log n}{k})$. This follows from the definition of amortized complexity.


Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits?

Circuits with fan-out 1 are called formulas.
Polynomial-size fan-in 2 formulas of arbitrary depth can be rebalanced to depth $O(\log n)$ by Spira’s lemma, hence they compute exactly nonuniform $\mathrm{NC}^1$. (The restriction that layers alternate between AND and OR is immaterial, as one can always insert dummy nodes to make it true, while at most doubling the depth.) Thus, your model with $k\ge1$ collapses to $k=1$.
Satisfiability is NP-complete already for 3-CNF. These can be written as depth $O(\log n)$ fan-in 2 formulas by arranging the outer conjunction as a balanced binary tree. (Again, one might insert dummy OR gates to make the connectives alternate if desired.)
For $k<1$, the formula only depends on $2^{(\log n)^k}$ variables, and therefore its satisfiability is computable in time $2^{O(2^{(\log n)^k})}$. Thus, it cannot be NP-complete unless ETH fails. There is no special complexity class for it, it is just NP scaled down to inputs of size $2^{(\log n)^k}$.
Better, satisfiability of circuits of depth $(\log n)^k$ for $k<1$ is not NP-complete unless P = NP: if it is NP-complete, then there exists a poly-time reduction $f$ of CIRCUIT-SAT to itself that maps a circuit of size $n$ to a circuit of size $2^{O((\log n)^k)}$. Using $\log\log\log n/\log(k^{-1})$ iterations of $f$ (which are computable in polynomial time), we reduce CIRCUIT-SAT to satisfiability of a constant-size circuit, which is trivial to decide.


Assuming the replies are guaranteed to be below the lines they're replying to, you can do this.

if (reply_to != 0)
{
    array[i].indent = array[reply_to].indent + 1;
}


Pass by Value or by Reference and Impure or pure functions

Pass by value and pass by reference are about function calls (method calls in case of OOP).

Pass by value means that variable is copied in function and any changes to variable are visible only within scope, where it was changed, if you pass reference then any modification to variable in the function is preserved after function call.

int x = 5;
void PassByValue(y) {
   y = 6;
  // some code
}
void PassByReference(&y) {
  y = 6;
  // some code here
}
PassByValue(x);
// here x is still 5
PassByReference(ix);
// here x is equal 6

Let O be object {x: 8}, that it's private variable x and setter method O.set(y) with code this.x = y;
If you pass by value or pass by reference, it doesn't matter, the state of object is changed.

Impure function has side effects outside of it's scope, so:

void Impure() {
  x = 6;
}

It does not get any parameters, but changes variable in outer scope, this is side effect.

Another property of impure function is that they do not solely rely on input parameters, one canonical example is:

int rand(int x) {
  return rand() * x;
}

Pure function returns the same result at every call, so for example math functions obey this property.
Any observable side effect: I/O operation, mutation, outer scope modification, network trafic, and so on, are impure.


Why not use Right Recursion to avoid Left Recursion?

The left recursive and the right recursive grammars describe the same language. But grammars do more than give the set of allowed strings in the language, they also give a structure to such strings and that structure is sometimes meaningful. Consider a+b+c; the structure implied by the left recursive grammar is {a+b}+c (I'm using braces and not parenthesis to show the structure to avoid confusion with the common mathematical meaning of parenthesis) the structure implied by the right recursive grammar is a+{b+c}.  If mathematically both are equivalent for addition, it is not the case for all operations. Consider subtraction a-{b-c} is not equal to {a-b}-c and that is the later that we usually consider the value of a-b-c.

The version with left-recursion removed is also right-recursive.  But its structure is different, and easier to map to the desired structure.  With a-b-c-d we have {{a-b}-c}-d for the left-recursive structure, a-{b-{c-d}} for the right-recursive and a{-b{-c{-d}}} for the result of left-recursion removal; that structure allow more easily than the right recursive one to get the intended meaning.


You should first build the binary expression tree of the given boolean expression. You can then do a Depth First Search on this tree, and start computing the answers from the leaves to the root (bottom to top), similar to the way you've done in your approach.

But instead of $S(i)$ denoting the number of assignments of the first $i$ $X$s which evaluate to 0, it will now be $S(u)$ denoting the number of assignments of the $X$s which lie in the subtree of $u$, which evaluate the expression until $u$ to be 0. Here $u$ refers to a node in the tree. Similarly $T(u)$ is defined for evaluation to 1.

The base case would be when $u$ is a leaf (which would happen when it corresponds to an operand), and both $S(u)$ and $T(u)$ would be equal to 1 in that case. Else, if $u$ is an internal node (which corresponds to an operator), you compute the $S$ and $T$ values by looking at the $S$ and $T$ values of its children, $c_1$ and $c_2$, and applying recursion similar to what you had in your answer:

If $u$ is an OR node,

$S(u) = S(c_1)  S(c_2)$

$T(u) = S(c_1)  T(c_2) + T(c_1)  S(c_2) + T(c_1)  T(c_2)$

If $u$ is an AND node,

$S(u) = S(c_1)  T(c_2) + T(c_1)  S(c_2) + S(c_1)  S(c_2)$

$T(u) = T(c_1)  T(c_2)$

If $u$ is an XOR node,

$S(u) = S(c_1)  S(c_2) + T(c_1)  T(c_2)$

$T(u) = S(c_1)  T(c_2)  + T(c_1)  S(c_2)$

And the final answer would be $S(\mathit{root})$ and $T(\mathit{root})$.


How to calculate time complexity of a randomized search algorithm?

Best case is $O(1)$, that is when you find the element in the first check.

Worst case is $O(n)$, and it happens when the element is in the first position, and in each check you get the last position, thus going through the whole array.

Average case is a little bit more tricky to get, since we need to solve a recurrence to get the expected value.
Let $T(n)$ be the expected time for an array of size n. The pivot is chosen randomly, so each posible pivot has a probability $p = \frac{1}{n}$. So, we have this:

$T(n) = T(1)/n + T(2)/n + ... + T(n-1)/n + 1$

We add that 1 at the end, because that's the constant time we have for checking at each step. Now we multiply each side by n:

$nT(n) = T(1) + T(2) + ... + T(n-1) + n$

Which also gives:

$(n-1)*T(n-1) = T(1) + T(2) + ... + T(n-2) + (n-1)$

So we can subtract those equations and we get

$n*T(n) - (n-1)*T(n-1) = T(n-1) +1$

$n*T(n) = (n-1)*T(n-1) + T(n-1) +1$

$n*T(n) = n*T(n-1) + 1$

$T(n) = T(n-1) + 1/n$

And "unrolling" this equation, we have:

$T(n) = 1 + 1/2 + 1/3 + ... + 1/n$

And the right side of the equation is the nth harmonic number. We can show that the nth harmonic number is $\Theta(\log n)$
So we have that the average time for the algorithm is $\Theta(\log n)$


I built a mechanical computer powered by marbles. What are its theoretical limitations?

What you have right now is a concrete computer. We cannot compare it to a computational model until it is properly formalized.

My intuition is that the board could be modeled as a dataflow architecture. Computational models conceived according to this paradigm can be Turing-complete, but (as was said in the comments) no concrete computer will ever be Turing-equivalent, and I don't think you should worry about this. All real computers are just (imperfect) working metaphors of formal computational models.

Should you come around to the idea of more closely imitating a Turing-equivalent dataflow machine, there are a few issues that could be addressed in order to "strengthen the metaphor", so to speak. Introducing cycles and composition of machines would be the two most important things, in my opinion, but I think your machine is already pretty amazing. It serves its purpose very well, and these "improvements" could sacrifice its usability.


Complexity of nearest codeword in cyclic codes

The general Nearest Codeword Problem problem for an arbitrary code is NP-hard. It is known that the problem is in NP if you only need to check whether there is a codeword within some fixed distance $\delta.$

Moreover there some efficient approximation algorithms given by Alon, Panigrahy and Yekhanin available here.

I am unaware of any work using the cyclicity property. The above apply to arbitrary linear codes.


First I suggest you to read the original article "Reevaluating Amdahl's Law" (CACM'1988) by John L. Gustafson when you have difficulty with the wiki article. Notice that I will use the notations from the original article: $s$ for serial time; $p$ for parallel time; $N$ for number of processors.

In the original article, the author mentioned that Amdahl's Law is based on an unrealistic assumption that "$p$ is independent of $N$", where $p$ is the amount of time spent (by a serial processor) on parts of the program that can be done in parallel.

Then, the author pointed out two key observations:

  In practice, the problem size scales with the number of processors.
  As a first approximation, we have found that it is the parallel or vector part of a program that scales with the problem size.

More explicitly, times for vector startup, program loading, serial bottlenecks and I/O that make up the $s$ (serial) component of the run do not grow with problem size; however, the amount of work that can be done in parallel varies linearly with the number of processors.

As a result, as $N$ (the number of processors; together with the problem size) increases, the portion of parallel time ($p$) increases according to the two observations given above, and the portion ($\alpha$) of serial time ($s$) diminishes (in most/common cases).


The series $\frac{1}{2^k}$ is a geometric progression. Hence, $\sum_{k=0}^m \frac{1}{2^k} = \frac{1-\left(\frac{1}{2}\right)^m}{1-\left(\frac{1}{2}\right)}$
You can continue from here.


Algorithm(s) for creating balanced 5-a-side teams?

This is a modelling question.  One plausible model might be as follows.  Each player as a strength, which is a real number.  The strength of a team is the sum of the strengths of the players on the team.  If team A plays team B, then team A will win with probability $f(s_A - s_B)$, where $f$ is the logistic function, $s_A$ is the strength of team A, and $s_B$ is the strength of team B.

This is an example of a possible model.  It might or might not be a good model.  But if we assume this model is correct, then it is possible to infer the approximate strength of each player, given the outcomes of a bunch of matches.  If $s$ is a vector that describes the strengths of all players, define $L(s)$ to be the likelihood of this vector.  In particular, $L(s)$ is formed by computing the product of the likelihood for each match that was played.  To compute the likelihood of a match between $A$ and $B$, you use $s$ to calculate the probability $p$ that A wins (assuming $s$ is the correct strength); if A actually won, the likelihood of that outcome is $p$, otherwise it is $1-p$.  (I assume there are no ties.)  For any particular $s$, you can calculate the likelihood of each match outcome like this, multiply them together, and get $L(s)$.  Now, to find the "best fit", you find the vector $s$ that maximizes $L(s)$.  This is known as a maximum-likelihood method.

How do you find the vector $s$ that maximizes $L(s)$?  Basically, you use some mathematical optimization method, like gradient descent.

If you assume this model is correct, another procedure to find the strengths of the players would be to use logistic regression.  However, ultimately this will end up being equivalent to what I articulated above.

Of course, you might find that the model I outlined is not a good model.  In that case, your task is to find a better probabilistic model that describes the probability that team A will beat team B, as a function of the strengths of the players.  Then, you can use the techniques sketched above to infer the strengths of each player.

Finally, once you have the strength of each player, the probabilistic model will let you evaluate different ways of assigning people to teams and figure out which one is most balanced (where the probability of winning for team A is as close to one-half as possible).

This approach assumes you only take into account who won, but not the score.  It would be possible to consider more sophisticated probabilistic models that also try to describe the distribution of scores as a function of the strengths of the players, but this will be more complex.  I suggest you stay simple for now.

You could also look at the Elo rating system and research whether there's any way to generalize it to apply to your setting, where each team has multiple players and you want to rate the strength of each individual player.


If a Ptime function loses x bits of data at every call, is it a one way function?

A one-way function is a function which is easy to compute but hard to invert. More accurate, it is a polytime function $f$ such that given a random $y$, it is hard to find a preimage $x$ satisfying $f(x) = y$. The exact sense of hardness isn't important here.

Your function is not one-way since it fails the first requirement: it is not easy to compute. If you use your recursive definition, computing $f(x)$ takes $x$ applications of the function $g$, which is exponential time.

It also fails the second requirement, since its range is finite. You can hardcode one preimage for each possible value in the image, and so invert the function efficiently.


How to apply the Ford Fulkerson algorithm to the assignment problem

I suggest you start with a simpler problem: there are only two (possibly overlapping) subsets, A and B; and every group must have two objects: one from subset A, and one from B.
Once I figured out how to solve that, it was clear to me how to solve your original question.
Hint on how to solve that:

 Have one left vertex per object.  Have two right vertices per group, one to represent which object is chosen from subset A, and one to represent which object is chosen from subset B.  Now figure out how to fill in the edges...


The task of recognizing game units in the screenshot

Machine learning doesn't seem needed, since the image of each unit is always identical.  One approach is to obtain a clean image of each unit, and then use template matching to find all locations where the template occurs in the screenshot.  You might be able to check all locations in the screenshot whether they exactly match the template image (you will probably want to mask out the part where the health appears, as that will obscure the image).  This can be done very efficiently.

To recover the health, you might also be able to do template matching on the numbers 0-10.

The way to tell what resolution you can downsize to is empirically: you experiment with different resolutions and measure the accuracy for each.  There's probably no way to predict without trying it.

If you want to try machine learning, you could try a CNN, or better yet, you could try retraining the YOLOv3 object detector for your particular images (see, e.g., the YOLO project page or here).  You will probably need a larger training set this way, and you'll have to do a bunch of manual annotation of sample screenshots.

Tool and library recommendations are off-topic here.


It depends. If you have a planar embedding, and you want to find faces on it, just pick an edge, and keep walking on the face that's on the 'left' side of the edge when looked at in the direction you were walking. If you want to find a cycle of nodes for which there exists a planar embedding in which those cycles are a face, that's even easier, because in planar graphs, every cycle is a face in some embedding.

Here's a simple algorithm for finding a cycle, but you can think of your own one. Suppose you have a graph that you know is planar, and you want to find a face. Start at some vertex $v$ and perform a breadth-first search. In iteration $k$, you find the vertices at distance $k$ from $v$ and for each vertex at distance $k$ that you add, you count how many nodes at distance $k-1$ were connected to that node. If there is just one, then continue. Otherwise, if two nodes at distance $k-1$ are connected to a node $w$ at distance $k$, then you have found a cycle in the graph (it is possible that you count three or more, in that case, select two). Node $w$ lies on a face in the graph, in some planar embedding of the graph. It may lie on the same face as $v$, but not necessarily, for example, you can have a cycle with a tail, and you accidentally started in the tail.

To find a face, backtrack from $w$ within the nodes that you explored so far with your breadth-first search: first, two nodes $x_1, x_2$ at distance $k-1$ (like I described above). Then, in each iteration, for $x_1$, find the node $x_1'$ which is connected to $x_1$ and is at distance $k-2$ from $v$ (why is there guaranteed to be only one? Because we identified $w$ as most nearby node with two paths leading to it from $v$), and repeat this until at some distance $d$ you find that your $x_1$ ancestor and your $x_2$ ancestor are the same node $y$.

You now have a face! That is, a cycle for which there is some planar embedding. The face has $w$ on one side, $y$ on the other side, and they are connected with two paths. One path is the series of $x_1$ nodes that you just found, and the other is the series of $x_2$ nodes. If you found $y=v$, then $v$ is on the face. You are not guaranteed to find a face with $v$ on it, but are other algorithms that find one if there is one. I can modify this algorithm to do that, and I'm sure you can too.


Registers can be thought of as collections of flip-flops. These have inputs which, when activated, change the stored value. When not activated, the stored value stays the same. Look at the truth tables in the Wikipedia article.


No, this isn't a hypergraph.  I don't think it has a standard "name".  Call it whatever you like: as long as you define your terms clearly, you should be fine.

Yes, you can implement this efficiently using any standard data structure for representing graphs: e.g., adjacency lists.  Each node of the "outer" graph will contain a pointer to a data structure that describes the "inner" graph it represents.


Minimize sequence storage by overlapping prefixes

This problem is known as "Shortest Common Superstring" (or sometimes just "Shortest Superstring"). It is an NP-complete problem in general, though good approximations are known (e.g.: via approximations of weighted set cover, as outlined in the linked Wikipedia article).


What is the most compact (space efficient) method of storing an array of distinct integers?

If your integers have small difference between them you can use a bitset with an offset. In this way if the difference between the largest and the smallest is n you need n bits + the size of the offset in bits. If your integer set is sparse you can use a sparse bitset implementation like Roaring bitmap .