how to defend against DOS caused by SYN cookies? i have read about SYN cookies and i understood that they help to avoid DOS .. BUt my prof wants an answer as how SYN cookies can be used to cause DOS and how can it be avoided ? any help woul dbe really appreciated.. thanks in advance

Computing syncookies requires taking a hash of the server and client's IPs and ports... These hashes may not be inexpensive esp if they are to be cryptographically secure. One way to DOS the syncookie code is to make so many requests that the CPU of the server is exhausted.  I believe that Linux uses a less expensive (and not cryptographically secure) hash function, so this is less of an issue.

You could probably also spoof sender IP and use syncookies to be sent to a victim. But that is not that useful/ interesting.


Do all Regular Expressions describe Regular Languages? I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent regular language? Or is the set of regular languages a subset of regular expressions?

If this is not the case, is there a good example of a regular expression that does not have an equivalent regular language?

It's a standard part of any automata theory course that regular expressions, deterministic finite automata and nondeterministic automata all define the same class of languages. Any individual exposition will take one of those three things as defining the class of regular languages.

So, yes, all regular expressions define regular languages, and every regular language is the set of strings that match some regular expression.

At least, the above is true for regular expressions as used in computer science. Perhaps the confusion in the question arises from the fact that many computer systems such as text editors, programming languages/libraries and command shells have pattern-matching features that they call "regular expressions" but which are more powerful than CS regular expressions. @reinierpost provides the example that egrep '^(.*)\1 matches the non-regular language $\{ww\mid w\in\Sigma^*\}$.


Algorithm for determining if a statement is a paradox Please bear with me, since I have just started working on this.

Assuming that the laws of thought apply.

The basic goal of the algorithm is to recast the statement into true or false premises and check if a true and false clashes. If there is a clash then the statement or the set of statements is/contains a paradox. This is the rule for determining if a statement or a set of statements is/contains a paradox.

When I say clash, it means that a statement upon recasting cannot be said to have both true and false attributes.

Rule 1:

"This statement is true" is true.
"This statement is false" is true.

The set of both statements is a paradoxical set.

Rule 2:

If in a statement there is a clash between true and false statements then it is a paradoxical statement.

"This statement is false" is true

Russell’s paradox:

"R, which is the set of all sets which are not members of themselves, is a member of itself" is True
"R is a set of all sets which are not members of themselves" is true.
"R is a set of all sets which are members of themselves" is false.
"R is a member of itself" is true.
Collectively it cannot be true, because there is a clash.

Now, we only need to recast the statement into true and false using the "not" operator to evaluate if a statement is true or false. We can evaluate all truth values and find if there is a clash between a true and false somewhere. If there is a clash then the collective set of statements or the statement is a paradox.

I got a couple in there. Can anyone throw me a paradox where this fails? I am trying to make it even simpler. Thank you so much! I think you will need some logic to recast more complicated statements, but this should identify the simple ones.

If nothing else, could you please verify this to be correct, and let me know if there is any procedure for finding if a set of statements contains a paradox currently exists. I think the general procedure detailing a clash between true and false in a paradox is absolutely correct.

I just came to know that there is a boolean procedure for finding self reference paradoxes, but it seems to me that my method might just be slightly more efficient, since it does not require solving for the entire set of statements but can halt whenever a clash is found. It could be hard to find if the set of statements has a solution or a clash or not, in the case of Wen's paper on the same, which recasts statements as boolean statements.

I can use this to disprove strong AI. Can someone please tell me if it is already proven that a human like intelligence cannot be recreated on a Turing machine.

So, there are a few problems with this.

First, what is your formal definition of a paradox? Is it just a statement that can be found to be both true and false in some system? Paradox tends to be a bit of an informal term, so in CS we usually just refer to this as a contradiction, or an unsound logical system.

For example, Russel's paradox isn't actually a paradox, it's a proof by contradiction. We assume a premise i.e. "any set characterized by a logical proposition exists.", and show that we can prove falsehood from it, thus concluding that the premise must be false. (In intuitionist logic, this is actually how falsehood is defined).
How are you encoding your logic statements? Traditional propositional logic doesn't give much in the way for describing self reference, so you probably need something higher order. Starting with natural language statements and converting them into logic is a whole separate problem.
Your problem seems undecidable, since you could use it to determine if one can prove false from an arbitrary proposition, which means you can use it to determine if an arbitrary statement is true, which means you can use it to determine if a Turing Machine halts on given input.


How does RAMDAC get notified about framebuffer write? I'm learning computer graphics, and I read this course lecture in order to understand how graphics I/O works under the hood. But the following explanation was not very clear to me:

  The values in the framebuffer are converted from a digital (1s and 0s
  representation, the bits) to an analog signal that goes out to the
  monitor.  A video card’s RAMDAC performs this operation, once per
  frame.  This is done automatically (not controlled by your code), and
  the conversion can be done while writing to the framebuffer.

How does RAMDAC get notified about the framebuffer write? Is there an IOCTL required from OS? or there is a circuitry somewhere that maps the write to RAMDAC input?

It probably depends on the architecture in general, but bear in mind that the phrase "the conversion can be done while writing to the framebuffer" is quite vague. The important point is that generating the video signal is a hard real-time operation, and the graphics hardware is designed to ensure that it always happens, even if someone is trying to write to the framebuffer at the same time.

There are a few ways this could be achieved. Some possibilities include:

Reads and writes to the framebuffer might always happen at different times. If you consider a square wave clock, for example, writes could happen on the leading edge of the clock signal and reads could happen on the trailing edge. This way, the result of the write is always available when the read occurs.
If there is contention between a read and a write, the write could stall or be buffered somewhere.
Reads from the framebuffer to generate the video signal could be buffered in a FIFO or something like that. If a write occurs, it could be allowed to happen as long as the FIFO hasn't drained.

It's possible that there could (as you say) be some kind of bypass circuitry, similar to forwarding logic in CPUs. The input to the RAMDAC could be a multiplexer, with one input directly from framebuffer RAM and another from somewhere else.

I think this is unlikely, because it seems excessive to implement extra circuitry just to ensure that a write that is happening right now appears on this frame. A buffer or stall seems much more likely.


What's the time complexity of Monte Carlo Tree Search? I'm trying to find the time complexity of Monte Carlo Tree Search (MCTS). Googling doesn't help, so I'm trying to see how far I get calculating it myself.
It does four steps for n iterations, or before the time runs out. So we'll have

O(n*(selection+expansion+simulation+backpropagation))

Expansion just adds a child to the currently selected node. Assuming you're not using a singly linked list or something like that to store tree children, this can happen in constant time, so we can exclude it:

O(n*(selection+simulation+backpropagation))

Given the branching factor b, and d as the depth of our tree, I'm assuming the selection phase runs in O(b*d), because at each level, the selection phase goes to all the children of the previous node.
So our time complexity becomes

O(n*(b*d+simulation+backpropagation))

Backpropagation takes time proportional to the depth of the tree as well, so that becomes:

O(n*(b*d+simulation+d))

But now I'm not sure how to add  the simulation phase to this. It'll be proportional to the depth of the tree, but for each iteration, the running time depends heavily on the implementation as far as I know.
What's monte carlo tree search
Monte Carlo Tree Search (MCTS) is a tree search algorithm that tries to find the best path down a decision tree, mostly used for game playing. In games with a high branching factor, it can often go deeper than algorithms like Minimax, even with Alpha-Beta pruning, because it only looks into nodes that look promising. For a certain number of iterations (or a certain amount of time), the algorithm goes through these four phases:
Selection Starting at the root node, go down the tree until you find a node that is not fully expanded, or a leaf node. At each level, select the child that looks most promising. There are many ways of making this selection, but most implementations (including mine) use UCB1.
expansion Expand the selected child by looking at one of its unexplored children.
simulation Simulate a "rollout" from the newly discovered child. Again, there are many ways to do this, but many implementations just take a random child until it reaches an end node. Take note of whether the simulation resulted in a success or a failure (win or loss in the case of a game).
backpropagation update the information about this node, and all nodes along the path back to the root. Most implementations store two values at each node: the number of times it was part of a selection path that lead to a success, and the total number of times it was part of a selection path. These values are used during the selection phase.
After you've run this for as long as you can, the child node of the root that looks most promising is the action to take next.

According to http://stanford.edu/~rezab/classes/cme323/S15/projects/montecarlo_search_tree_report.pdf

  Time Complexity
  The runtime of the algorithm can be simply be computed as
  $O(mkI/C)$
  where $m$ is the number of random children to consider per search and $k$ is the number of parallel searches, and
  $I$
  is the number of iterations and
  $C$
  is the number of cores available.

  Memory Complexity
  The memory complexity is
  $O(mk)$ since in each iteration we map
  $mk$
  states over the cluster.


Which of the following is recursive Consider below two Languages

$L1=\{<M>|$M takes atleast 2000 steps on some input $\}$

$L2=\{<M>|$M takes atleast 2000 steps on all inputs$\}$

Where for each Turing machine M, $<M>$ denotes specific encoding of M.

Here I think both are recursive, because let's say I bound the number of steps the Turing machine runs to 2000, then Turing machine will only be able to process inputs of length atmost 2000.

Now, there are finite number of inputs of length 2000, I can check whether for all such inputs, my Turing machine is making 2000 steps or not.This answer L2.

And when L2 is answered, I have an answer to L1, making L1 and L2 both recursive.

Am I correct in my reasoning?

No, your reasoning is not correct, but I think you are very close to a correct answer.

A Turing machine in 2000 steps can only read the first 2000 symbols in the input tape, but is not forced to reject a longer input. In fact, it can accept it. So, the TM can process longer inputs, but its behavior is determined by the first 2000 symbols on the tape.

If $x$ and $y$ are words which are identical on their first 2000 symbols, then they are both accepted/rejected/neither in 2000 steps.

Because of this, we can partition the possible inputs according to their first 2000 symbols. For each of the finitely many partitions, we can extract any element and test for that one, only.

So, our decision procedure is the one given by the OP. The argument for correctness is a bit different, though.


Exact amount of loop iterations here? What is the exact number of loop iterations here and how do you find out?

def func(n):
  i = 4

  while i < n:
    print(i)

  i = i + 1

The solution says max(n-4,0) which is theta(n), but I am confused about how they reached this. I see it starts from 4 and can guess that this relates to the n-4, but would like to be sure.

It will iterate $n-4$ steps if $n>4$ . If  $n\leq4$  there will be no iteration since the condition is not satisfied. The important thing is that the linear search runtime grows like the sequence size in the worst case. The notation we use for works like $c_1.n+c_2$ is Θ (n).


Whats the name of this search game? I am struggling in finding the name of this game (in order to find research papers related to it in the literature).

Given an initial word $X$ and a target word $Y$, what is the minimum number of (letter) flips needed for $X$ to reach $Y$ assuming $X$ and $Y$ having the same number of letters, we flip only one letter each time and such sequence(s) of flips exist.

That is, there is a sequence $A_1\rightarrow A_2\rightarrow \dots\rightarrow A_n$ where $X=A_1$ and $Y=A_n$ and every thing in between is a correct word (i.e. has a meaning in a given dictionary).

For instance, $X=Pork\rightarrow Park\rightarrow Dark=Y$

Yes; I do not have the minimum knowledge in games.

I think you are referring to Hamming Distance. See http://en.wikipedia.org/wiki/Hamming_distance.

As for a game, having the extra condition that intermediate modifications must be real words is the Word Ladder. See http://en.wikipedia.org/wiki/Word_ladder.


Is there a total binary computable function that specifies Turing machines with nonempty domain? I am working through Bridge's computablity book and I came across this problem that does not have an answer. I don't know how to precede, any help is much appreciated.

My Tip for you:
Check out the second recursion theorem and plug $\Psi$ in for $Q$.
If you can't continue on you own here is my solution:
The second recursion theorem implies that there is such a $m$ that:
$$\varphi_m \simeq \lambda n.\Psi(m,n)$$
($\simeq$ means that the left and right expression are equal for every input $n$ equal and if an expression in undefined for a certain $n$ this is also true for the other expression)
Case 1: $\Psi(m,n) = 1$
This implies $f(m) = 0$ and thus $\text{domain}(\phi_m) = \emptyset$.
But notice that $\varphi_m \simeq 1$ is implied by our assumption.
Thus the domain of $\varphi_m$ is $\{1\}$. That's a contradiction.
Case 2: $\Psi(m,n) = \text{undefined}$
This implies $f(m) = 1$ and thus $\text{domain}(\phi_m)\neq\emptyset$.
But once again $\varphi_m \simeq \lambda n.\Psi(m,n) \Rightarrow \varphi_m \simeq \text{undefined} \Rightarrow \text{domain}(\phi_m) = \emptyset$, which is a contradiction.


What is this fraction-like "discrete mathematics"–style notation used for formal rules? In the paper "A Conflict-Free Replicated JSON Datatype", I encountered this notation for formally defining "rules":

What is this notation called? How do I read it?

For example:

the DOC rule doesn't have anything in its "numerator" — why not?
the EXEC and GET rules appear to have two separate terms above the line, what does that mean?
the VAR rule stands out a bit as well, since while many other rules use some sort of arrow (which I would take to mean "implies") up top this one only seems to be saying that x is an element of something.
almost everything is peppered with an initial Ap, which the text describes as "the state of replica p is described by Ap, a finite partial function" — how would a savvy reader of this notation tend to "see" that part of every rule?

This site did suggest a related question that has some very similar-looking notation, over on the question What is the significance of ⟨B, s⟩ -> ⟨B', s'⟩ as the initial rule in this question about small-step semantics? — this is tagged as Operational semantics, and that does seem to be a strong lead. Is that indeed the framework under which I should be interpreting these figures? Could you easily summarize this in "crash course" form so that, even if I can't verify the correctness of their proofs, I could at least get a bit more understanding of what they are saying in this section?

This is a standard notation for an inference rule.  The premises are put above a horizontal line, and the conclusion is put below the line.  Thus, it ends up looking like a "fraction", but with one or more logical propositions above the line and a single proposition below the line.  If you see a label (e.g., "LET" or "VAR" in your example) next to it, that's just a human-readable name to identify the particular rule.

You might also see this referred to as natural deduction or Gentzen-style natural deduction.

This is a common notation in the programming languages literature.  You'll see it all over the place.  It's very convenient for the kinds of conclusions and recursive-structured proofs that arise in that field.

You'll see this notation used to express axioms/rules. You can think of each axiom as a template with "meta-variables" (e.g., expr); you can replace each meta-variable with some syntax from the programming language (e.g., any expression that is valid in the programming language), and you'll get an instance of the rule.  The inference rule promises that if all of the propositions are above the line are true (for some instance of the template, where you consistently replace each metavariable with the same value throughout the rule), then the proposition below the line will be true, too.


Why isn't every vertex connected to every other vertex in TextRank? I've been reading up on the automatic text summarization approach TextRank, particularly for generating summaries of a text using sentence extraction as opposed to keyword or phrase extraction.

In the published paper, an example body of text and the resulting ranked graph of all sentences/vertices and their edges is given. I'm unclear as to why every vertex doesn't have an edge connecting it to every other vertex in the graph - shouldn't all sentences be compared with each other?

This doesn't seem to be addressed in the paper. One possible explanation I've produced is that there is no edge if the similarity between two sentences is 0. Does anyone know for sure?

Link to paper: https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf

After getting in touch with the authors of the paper, the reason why every vertex isn't connected to every other vertex in the graph is because only edges with a non-zero weight are added to the graph.


Creating a 2D map of objects given a sparse matrix of pairwise distances I have a set of points on the two-dimensional plane, but their locations are not given to me.  I am given the distance between some pairs of the points.  However, I only know these differences for some pairs: I don't have every pairwise distance between the objects. I would like an algorithm to output the locations of the points.

The complication is that there could be some errors in the distances provided to me, so I want the algorithm to output a location for each point such that the pairwise distances between those locations match the provided distances as closely as possible.

Could anyone point me towards a method of computing a placement in  2-dimensional Euclidean space that would best solve this problem?

It would be nice to be able to provide hard constraints as well. For instance, I might be given that $C$ is exactly at the point $(1,2)$, or that all of the objects must fit in a $10 \times 10$ square.  However, this is not strictly necessary: an algorithm that does not support hard constraints would still be interesting.

This is known as "graph layout" or "graph drawing" (practical methods) or "graph embedding" (theoretical interest).  The relevant techniques are more closely associated with computational geometry and mathematical optimization, not machine learning.   See this Wikipedia article and Recovering a point embedding from a graph with edges weighted by point distance and Efficient algorithm to fulfil a set of coordinate constraints for an overview of some standard techniques.  Pairwise comparisons with confidence might also have some helpful techniques (it is focused on the 1D case, not the 2D case, but it might be possible to generalize Yuval's answer to the 2D case as well).


Powerset generation using recursion and time complexity I have a program that generates power set of a given string, the set being the characters of the string.

public static Set subsets(String s) {
    Set subsets = new HashSet();
    if (s.length() == 0) {
        subsets.add("");
    } else if (s.length() == 1) {
        subsets.add("");
        subsets.add(s);
    } else {
        for (int i = 0; i < s.length() - 1; i++) {
            Set sets = subsets(s.substring(i + 1));
            for (String st : sets) {
                subsets.add(s.substring(0, 1) + st);
            }
            subsets.addAll(sets);
        }
    }
    return subsets;
}

I don't seem to understand how to calculate time complexity of the above implementation.I understand that String.substring and creating Set Objects are pretty expensive, but if I assume these two operations to take constant time, what would be the overall time complexity?

You should have converted you Java code into pseudo code.

In fact, if your code runs exactly as you describe, namely given a set $S$ as a string it generate all subsets of the symbols of the input string, then the running time is trivial. You just need to count the number of different subsets generated by your algorithm/code. Input size is the length of the input string, i.e., number of characters. So, if the number of characters is $n$ then there are total $2^n$ different subsets. So, the time complexity is $O(2^n)$.


lambda expressions, parenthesis, and order of application I am building a lambda applicator in Java, and I have uncovered a bit of misunderstanding.  Either my question at the bottom is what I am asking, or something in the build-up below is wrong.  Either way, I'd appreciate any insight.

So, NOT can be defined as

λb.b (λxy.y) (λuv.u)

If we allow

A1 = λb.b
B1 = (λxy.y)
C1 = (λuv.u)

Now NOT is (A1 B1 C1)

By order of operations, B1 will be applied before C1
So let Not1 = (A1 B1)

NOT can now be rewritten as (Not1 B1) or ((A1 B1) C1).

When we apply the expression

TRUE = (λdw.d)

to NOT, we have

((A1 B1) C1) TRUE

Which, because A1 is the identity function, is supposed to get us

((TRUE B1) C1)

... but why wouldn't we apply B1 to A1 first?

I believe you are misunderstanding what $\lambda$-abstraction represents and are not considering its scope. First; your definition of $NOT$ is correct and $NOT$ is in normal form.

It is not true that $\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)$ is the same as $(A_1\ B_1\ C_1)$ and I give here two reasons why:

The body of $\lambda$-abstraction goes as far right as possible (after ".", until its enclosing brackets, in our case none) and therefore $\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)$ is a $\lambda$-abstraction with variable $b$ and body $b\ (\lambda x y. y)\ (\lambda u v. u)$. The string "$\lambda b. b$" in this case is not representing an identity expression, but is a part of the definition of $\lambda$-abstraction. Its $\lambda$ "belongs" to the whole $NOT$ expression. Written fully parenthesised, your expression for $NOT$ would be
$$\biggl(\lambda b. \Bigl(\bigl(b\ (\lambda x y. y)\bigr)\ (\lambda u v. u)\Bigr)\biggr)$$
If it were in fact the same as $(A_1\ B_1\ C_1)$, this could reduce to $(B_1\ C_1)$ which could then reduce to $\lambda y. y$ which is identity (which is not $NOT$) and $\lambda$-expressions have at most one normal form.

The $NOT$ operator, when applied to some expression $X$ should reduce like this:
$$\bigl(\lambda b. b\ (\lambda x y. y)\ (\lambda u v. u)\bigr)\ X \rightarrow_\beta X\ (\lambda x y. y)\ (\lambda u v. u)$$

You can try your ideas and check existing examples with pLam to help you build a similar tool by yourself. Good luck!


Minimal unsatisfiable core algorithm Wikipedia says that

There are several practical methods of computing minimal unsatisfiable cores.

but I cannot find any. I suppose that “practical methods” means polynomial algorithms. Be careful, a polynomial algorithm, that finds a minimal unsatisfiable core of a given CNF $F$, doesn’t mean that $P=NP$, because the algorithm could output a Boolean formula $G$ such that if $F$ is unsatisfiable, $G$ is a minimal unsatisfiable core of $F$; if $F$ is satisfiable, $G$ is a subset of the clauses of $F$ and  it is satisfiable. Therefore, the output of the algorithm is a CNF but we don’t know if it is satisfiable or not.

Be careful, a polynomial algorithm, that finds a minimal unsatisfiable core of a given CNF , doesn’t mean that =, because the algorithm could output a Boolean formula  such that if  is unsatisfiable,  is a minimal unsatisfiable core of ; if  is satisfiable,  is a subset of the clauses of  and it is satisfiable. Therefore, the output of the algorithm is a CNF but we don’t know if it is satisfiable or not.

The basis of this statement seems to be a slight misunderstanding of the UNSAT to MINIMAL UNSATISFIABILITY reduction given in The complexity of facets resolved.  This reduction is not a way to produce an unsat core even if the original formula is unsatisfiable.  What the reduction does is embed the original formula into a new formula carefully crafted such that satisfiability is unaffected but the new formula's CNF clauses no longer overlap in the assignments that they forbid.  Because each clause forbids different assignments and because the formula's clauses cover all possible assignments, removing any one clause is guaranteed to make the result satisfiable, which is the definition of a minimally unsatisfiable formula.  But this new formula is not an unsat core of the original formula and tells you nothing about how to find such a core.  The original formula and the new formula are equisatisfiable and thus are related, but they aren't related in a way useful in finding an unsat core for the original formula.
As for practicality, by this the Wikipedia article means "easily implemented once you have a certificate of unsatisfiability for a given Boolean formula."  If you already have a tool to generate such a certificate, you can produce an unsat core using a polynomial number of calls to that tool.  If the tool requires exponential-time relative to the size of the formula, then you're still looking at an exponential process to find an unsat core.  But it is just as "practical" as determining whether the formula is unsatisfiable in the first place.


PDA for the language of strings containing the same number of a and b Need idea for solving the following pushdown automata:

$\mathcal{L}=\{w\in\sum ^* | \#a(w)=\#b(w),|w|\geqslant 0\}  \,\,\,\, \sum=\{a,b\}$

In the beginning I thought to PUSH A for input a, and then to POP A for input b, but it doesn't work well for the word ba for example

You have solved half of the task. Now push $B$ for $b$ and pop $B$ for $a$.
To decide which operation to do, handle empty stack, pushing symbol when it is empty and popping otherwise.


O(m+n) Algorithm for Linear Interpolation Problem

Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the linearly interpolated values of the query points according to the data. We assume $q_i \in (\min_j x_j, \max_j x_j)$

I heard off-hand that this problem could be solved in $O(m+n)$ time but can only think of an $O(m \log n)$ algorithm. I can't seem to find this particular problem in any of the algorithm textbooks.

Linearithmic Algorithm

interpolated = []
for q in qs:
    find x[i] such that x[i] <= q <= x[i+1] with binary search
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)

This gives us a runtime of $O(m \log n)$, it's unclear to me how to get this down to $O(m + n)$ as the search for $x_i$ must be done for every query point.

You only need to perform binary search for the first element and then iterate simultaneously through the data points and query points.

Pseudocode

interpolated = []
find x[i] such that x[i] <= q[0] <= x[i+1] with binary search

for q in qs:
    while not x[i] <= q <= x[i+1]:
        i++
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)


Removing epsilon transition from context-free grammar I have the following context-free grammar from which I have to remove epsilon transitions:

$S \to 0A0|0$

$A \to BC|2| CCC$

$B \to 1C | 3D | \epsilon$

$C \to AA3 | \epsilon$

$D \to AAB | 2$

By algorithm, I create $N_{0}$ that will hold all non-terminals that contain $\epsilon$ and in next steps add non-terminals that have rule that contains only non-terminals from the previous iteration of N e.g.

$N_{0} = \{\}$
$N_{1} = \{B,C\}$
$N_{2} = \{B,C,A\}$
$N_{3} = \{B,C,A,D,S\}$

Now I have to adjust rules, we can remove non-terminals in $N_{3}$ object from rules, thus we have to create all combinations without it e.g.

$S \to 0A0 | 00 | 0$

$A \to BC | B | C | CCC | CC$

$B \to 1C | 1 | 3D | 3$

$C \to AA3| A3 | 3$

$D \to AAB | AA | A | AB | B | 2$

We see that no non-terminal isn't useless, so is this the final context-free grammar? Or did I make mistake somewhere?

Thanks for answers and help.

As described in the algorithm to put a given CFG in Chomsky Normal Form:

To remove the $\varepsilon$-rules: Remove a rule $A \to \varepsilon$ if $A \neq S_0$ ($S_0$ being the start-variable). To 'repair' the CFG, add for every occurence of $A$ in the body of a rule, the same rule but with $A$ removed.
Example: if you have rules $A \to B | \varepsilon$ and $B \to BAAB$. To remove the $\varepsilon$ for $A$, add for each ocurrence of A a new rule with A removed. In this case:
$A\to B$ (remove $\varepsilon$) and $B \to BAAB|BAB|BB$.

Finally, for rules of the form $R \to A$, add $R\to \varepsilon$ if you did not remove $R \to \varepsilon$ in a previous iteration.


Can you use a Bayes classifier to determine if something is NOT in a defined class? I know I can use a Bayes classifier to determine if something is one of N classes, but can I also determine if something is NOT in any of the predefined classes?  Or will a Bayes classifier only find the closest class?

Create an extra class whose membership means "belongs to none of the predefined classes".


Conflicting definitions of language accepted by Turing Machine? I am reading Papadimitriou, Computational Complexity, page 24, where it is says

  We say that $M$ accepts $L$ whenever for any string $x \in (\Sigma - \{\sqcup\})^*$, if $x \in L$, then $M(x) =$ ``yes''; however, if $x\notin L$, then $M(x) = \nearrow$.

The key issue is what happens for $x \notin L$. This definition insists that $M$ must not halt for $x \notin L$. Other sources I read, e.g., this says that  if $x\notin L$ then either $M$ does not halt, or $M$ halts at ``no''.

Prima facie this seems to me to be a significant difference. Could someone clarify to me if these definitions are equivalent and if there is no loss of generality in talking of acceptance in the sense of Papadimitriou? Or is only one of these definitions the correct one?

The two definitions are in fact equivalent. Both halt and accept when the word belongs to the language. One is more restricted for strings outside of the language: it is not allowed to halt. Every Turing machine in the "classic" definition (which allows halting with "no") can be changed into a non-halting one easily. Just when the old machine wnat to stop in a no-state, its restricted equivalent moves into a no-sate that actually does not stop but instead keeps walking to the right (or the left, what you want). Both versions of the machine will accept the same language.

Thus, both versions define the class of recursively enumerable languages. Or partially decidable or Turing-acceptable, but I prefer the old terminology.

In conclusion, Papademitriou has a slightly non-standard definition, which is nevertheless equivalent to the commonly used one.


why not just use a random number generator as a hash function? I guess at the heart of this is that I don't really understand hash functions.

One article says any function mapping objects to an object of fixed size:

  A hash function usually means a function that compresses, meaning the
  output is shorter than the input. Often, such a function takes an
  input of arbitrary or almost arbitrary length to one whose length is a
  ﬁxed number, like 160 bits.

Why not just use a random number generator to generate the hash keys?  Wikipedia  suggests SHA1 which maps to $2^{160}\approx 10^{48}$ possible outputs has never experienced a "collision".

I was trying to understand why the hash is necessary in a probabilistic counting algorithm:

class LinearCounter():
    def __init__(self, m, h):
        self.array =  [False for x in range(m)]
        self.hash = h

    def add(value):
        self.array(self.hash[ value ]) = True

Is the hash necessary? Why can't we use a random number generator right away?

def add(value):
    self.array(int(m*random.random()))

If I understand the question correctly, the answer is simple: if Hash(object) returns 27 when you call it this afternoon, we want Hash(object) to return 27 if we call it next week, on a different computer. If you use a random number generator in such a way that this is guaranteed, then go for it. Consider that a key use case for hash functions is implementing hash tables, and we want to be able to access what we put into a hash table tomorrow with the key we used today.

In your example, you might want to add a contains(value) method; using the hash, this would be as easy as checking self.hash[value] =? value. Otherwise, you'd need to iterate through the entire array to see if some position contains value.


Does 'subexponential algorithm' refer to input or number of bits used to represent input? When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N?  Consider the following: trial division for integer factorization (i.e. try all numbers less than $\sqrt N$) is subexponential in terms of N.

Note: here I'm using the definition of 'subexponential' to be $2^{O(n^\epsilon)}$ for some $\epsilon < 1$.

That is it takes $2^{\log_2 \sqrt N}$ steps to factor N.  This is obviously subexponential in terms of N.  However, in terms of the number of bits B needed to represent N this is $2^{\frac B 2}$ which is not subexponential in terms of B.

So would trial division be considered subexponential or not?  Or would it be considered both depending on whether you're referring to N or B?

It refers to the number of bits to represent N.  More generally, the complexity of a problem is normally taken to be a function of the length of the input (the number of bits needed to represent the input).

Trial division is exponential: its running time is $O(N^{1/2})$, i.e., $O(2^{B/2})$ where $B=\lg N$ is the length of the input in bits.  That's an exponential function (of $B$).  See Are there subexponential-time algorithms for NP-complete problems?.


generate all unlabelled trees up to size n Who has published an answer to these problems?

An isomorphism signature is a function s on the set of all trees with the property that s(T1) = s(T2) if and only if T1 and T2 are isomorphic. Define such a signature.

Many thanks
Keith Paton
Independent researcher

If you just want to define such a function, then you can just consider the equivalence relation $\rho$ where $T_1 \rho T_2$  iff $T_1$ and $T_2$ are isomorphic. Partition the set of all trees w.r.t. $\rho$. Let $C(T)$ be the equivalence class in which $T$ belongs and select one representative $T^C$ for each equivalence class $C$. Define $s(T) = T^{C(T)}$.

If you want a signature that can be easily/quickly computed, you can define one recursively. For simplicity I am going to define it over binary strings, but you can interpret this string as an integer. I am also going to assume that you are interested in rooted trees (see below if this is not the case).
If $T$ is a singleton let $s(T)=\epsilon$, where $\epsilon$ is the empty string. Otherwise let $r$ be the root of $T$ and $u_1, u_2, \dots, u_\ell$ be the children of $u$ sorted in nondecreasing order of $s(u_i$). Define: $s(T) = \bigcirc_{i=1}^\ell (1 \circ s(u_i) \circ 0)$, where $\circ$ denotes concatenation.

Algorithmically, this amounts to starting with $s(T)=\epsilon$ and performing a DFS visit of $T$:
every time that an edge $e$ is traversed append a $0$ (resp. $1$) to $s(T)$ iff $e$ is traversed away (resp. towards) the root. The order in which the children $u_1, \dots, u_\ell$ of a vertex are visited is determined by  the values of $s(u_i)$ themselves.

If you are interested in unrooted trees, then you can use the same approach by first rooting $T$ in one of its centers. If $T$ has only one center, then $s(T)$ is unique. If $T$ has two centers, you can select the one that results in the smallest value of $s(T)$ (w.r.t. the lexicographical order).

This has been used, e.g., here in Section 3.1.


When does strong duality fail in linear programming? When does strong duality fail in linear programming? I have considered the case when both primal and dual solutions are infeasible, but then there are no optimal solutions at all.

The strong duality theorem of linear programming states that (quoted from "Algorithms" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, 2006) "If a linear program has a bounded optimum, then so does its dual, and the two optimum values coincide." Hence, it never fails.


Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string? I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is >= 60% of symbol A.

I'm trying to think in terms of what to save on the stack. The problem of telling when there are 50% or more is trivial. You can just pop and push As and Bs on the stack to track which one has the majority. If an A is on the stack at the end, you're solid. however, in this problem we see that an A can be on the stack in the end and still not meet the criteria because it could be a ratio of 6 As to 5 Bs, which is under 60%.

Assume you have to check whether $\#A \ge \frac 43\#B$, then this is equivalent to  $3\#A \ge 4\#B$. This can be solved: just push 3 symbols for every $A$ and pop four of them for every $B$ (changing this a little when the number gets negative).

Adapt this to your fraction.


How to analyze/test a binary search algorithm? I was asked to "Compute the average runtime for a binary search, ordered array, and the key is in the array." I'm not quite sure how to approach this problem. Isn't the runtime of binary search O(log n)? And the average would be something like n + n/2 + n/4... etc?

I'm then asked to "Implement a program performing an empirical test of the binary search (using a fixed number of random arrays for each n), then do a ratio test justifying your analytical answer." How would I go about doing this? Could I perform a basic binary search algorithm on a number of random arrays, counting the basic operations, and compare that to my original analysis from the first question?

I appreciate any help/guidance here.

First, of all, the worst-case running time of binary search is $\Theta(\log n)$. What you are looking for is the average running time of binary search under some reasonable random model, for example the element to be looked for is chosen uniformly at random from the (distinct) elements in the array.

Second, the average running time can't be $n + n/2 + n/4 + \cdots$, since the average running time is lower than the worst-case running time. I'm not sure what exactly you're counting here. The average running time is the average number of operations taken by your algorithm, on a random input. In contrast, the worst-case running time is the maximal number of operations taken by your algorithm on any input.

Perhaps the following example will make things clear. Consider the following task: given an array of size $2n$ containing $n$ zeros and $n$ ones, find the index of a zero. The worst-case running time of any algorithm is $\Omega(n)$. In contrast, consider the algorithm which scans the array from left to right, and returns the first zero index. Its worst-case running time is $\Theta(n)$. Under the assumptions that the input array is chosen randomly among all legal arrays, the average running time is $\Theta(1)$ (why?). You can modify the algorithm to one which probes locations randomly, and then the worst-case expected running time is $\Theta(1)$. (If you don't understand the last remark, wait until you learn about randomized algorithms.)

Finally, you're required to empirically demonstrate the claimed average running time $\Theta(f(n))$. The idea is that for large $n$, the average running time will be $\approx C f(n)$ for some constant $C$ whose units are seconds. In other words, $C$ is the constant "hidden" inside the big O notation. Suppose you calculate for several values of $n$ an average $T(n)$ over several runs of the algorithms. Then you expect $T(n)/f(n)$ to be roughly constant, and that would demonstrate your claim concerning the average running time.


Assumption on weights in threshold circuits A threshold gate implementing a linear threshold function on $n$ boolean inputs $x_1, x_2 \ldots, x_n$ is given by the equation:
$w_1 x_1 + w_2 x_2 + \ldots, w_n x_n \ge t$
where $w_1, \ldots, w_n, t \in \mathbb{R}$. The $w_i$'s are called the weights of the threshold function and $t$ is called the threshold, and naturally, the gate fires a $1$ on an input $x$ if the weighted sum given by the equation above exceeds $t$.

Now, almost everywhere in the literature on threshold circuits, I encounter this fact (which I am guessing, is folklore since I couldn't find a proof anywhere): The $w_i$'s in the linear equation above can be made integers (on $n \log{n}$ bits), and a threshold circuit made up of these gates will still compute whatever was possible with real weights. I have given this some thought, and I think it must be a simple trick, but I have failed to obtain a proof of this fact. Can somebody help or provide me with a reference? (the only reference I could find was a text by Muroga, which I couldn't procure)

Given $w_1,\ldots,w_n,t$, let $X$ be the set of assignments such that $\sum_i w_i x_i \geq t$, and consider the linear program with variables $z_1,\ldots,z_n$ and the $2^n$ constraints
$$
\begin{align*}
\sum_i z_i x_i \geq +1 & (x_1,\ldots,x_n) \in X \\
\sum_i z_i x_i \leq -1 & (x_1,\ldots,x_n) \notin X
\end{align*}
$$
This linear program (with a constant objective function) is feasible (since $z_i = w_i/t$ is a solution), and so has a solution $z_1,\ldots,z_n$ which is a vertex. As such, it is the solution of a system of $n$ equations of the form
$$
\sum_i z_i x_i = \pm 1.
$$
Cramer's rule gives each $z_i$ as a ratio of two $n \times n$ determinants of matrices of $0,\pm 1$ entries; in fact the denominator is the same. Each numerator $N_i$ and the common denominator $D$ is at most $n!$ in magnitude, so multiplying everything by $D$, we get an integral solution $N_1,\ldots,N_n,D$, where all the quantities are at most $n! \leq n^n = 2^{n\log n}$ in magnitude.


Why do we discard the constant 1 in proving that $2^{n+1} = O(2^n)$ In this post
someone said:

  $n + 1$ is approximately equal to 1 for $2^{n+1} = O(2^n)$.

I don't understand this point. For example, in this example:

$$ n + 1 \leq c \cdot n $$

for some $c$ and some $n \geq n_0$, the right-hand side will always be at least the left-hand side.

But here: $$ 2^{n+1} =O(2^n)$$

the left-hand side will always exceed the right-hand side.

No, there exists such a constant. Indeed take $c=2$, then
$$\forall n \in \mathbb{N}\quad 2^{n+1}=2^1 \cdot 2^n \le  c \cdot 2^n.$$
So $2^{n+1}=O(2^n)$.


Why do ACLs (access control lists) have better persistence than capabilities? Although I understand the principles on which both ACLs and Capabilities operate, I do not see why on system restart it would be favourable to store privileges by using ACLs, instead of capabilities lists as it is suggested in the Operating systems course I am taking. In other words, why do ACLs have better persistence than capabilities?

There's a lot of confusion and regrettable writing out there surrounding the comparison between ACLs and capabilities.  Often, when books make a comparison, they are referring to one particular type of ACL system vs one particular type of capability system, but the difference isn't always fundamental.  So, if you see some comparison like this, I wouldn't worry about it too much.

In particular, capabilities can certainly have equal persistence to ACLs.  As an extreme example: If you have a persistent store and all applications are persistent (so that when the machine reboots, all applications are relaunched with the same state as before the crash), then capabilities will be persistent.  You can achieve the same level of persistence.  Historically, people who have built capability systems in the past might not have built them that way (usually), but that isn't always a guide to what is or isn't fundamental.

So, I would take issue with the book's claim that ACLs have better persistence than capabilities.  That's not necessarily true; it'll depend on specifically how the ACLs and capabilities are implemented by the system and used by applications.

(Also note that so-called "POSIX capabilities" are a bit of a misnomer and it's not clear we should really call them capabilities.)

I do realize that this might or might not help you if you're taking a course, as depending on the instructor, the instructor might expect you to go by what the book says and might not appreciate other perspectives (or, more benignly, want you to understand things from the textbook's perspective before taking a broader view).


IP addresses and CIDR suffixes I'm somewhat confused about IP addresses and subnet masks.
Can a same IPv4 address have two different CIDR suffixes ?
for example 95.100.252.115/28 and 95.100.252.115/26 ?

If not, how is the CIDR suffix determined by the IPv4 address?

Yes there can be different suffixes, and the IP absolutely does not determine the suffix. You determine the suffix based on how many other computers you want networked together in that subnet group.


Least number of comparisons to identify 6 numbers with values from 1 to 6 (without repetition) Variabled $x_1, \dots, x_6$ have hidden, distinct integer values from [$1,\dots,6$]. How to identify each variable's value with minimum number of comparison operations?

According to Wikipedia, the minimum number of comparisons needed to sort 6 numbers is 10. The lower bound follows from the usual decision tree argument.


What's the difference between Process Context and Process Control Block? I know that Process Context is something that is stored when a process is preempted, containing all the necessary info to restart the process at a later time.

I also know that the Process Control Block(PCB) contains all the necessary attributes of the process.

So, does that mean that the Process Context is a part of the PCB? Or is it the other way around? Or are these separate all together? Please help me understand where one ends and the other begins - as well as how they're used together.

What exactly is a process boundary?

Also, how is the PCB affected during a context switch (if at all)?

I think you are confusing the concepts of threads and processes.

Threads (aka tasks)
Processes do not get pre-empted, only threads get pre-empted.
A process can contain one or more threads which may run concurrently and/or time-sliced.
As long as there are current threads in the process (some or all of which made be paused) it is said to be running. When the last thread ends the process terminates. When a process is terminated forcibly by the operating system all its threads are terminated as well.

Process control block
The Process Control Block is the collection of information needed to define a process. In modern OS'es processes are (more or less) isolated and run in their own memory space.
The term process control block is not actually in use by any operating system and the various info needed to control a process is not actually stored in a single structure, as such the term is not all that helpful.

Threads are confined to a process
All threads inherit their properties from the process and have little room to alter these. It is the programmer's responsibility to make sure threads do not step on each others toes. Unlike processes there is no isolation between threads inside a process other than a dedicated stack and thread local storage.

Thread context
A thread context is not part of the PCB.
A thread context is simply a dumb of the current machine state (mostly CPU registers) before the thread was interrupted, in additon every thread gets its own dedicated stack and thread local storage.
The context a thread runs under can only be understood in terms of the process state (as defined in the PCB).
E.g. memory addresses inside process X do not make sense outside that process.

Process isolation
I've never heard of process boundary. I'm assuming you mean process isolation.
Every process runs in its own virtual address space and gets access to virtual resources (such as the screen) in such a way that one process cannot access the resources of another process.
In most operating systems this isolation is imperfect and resources in use by other applications can be easily accessed especially when processes have been started with equivalent attributes (e.g. same user id).

  how is the PCB affected during a context switch (if at all)?

The PCB is not affected by a thread context switch.


Incremental compilation over AST Is incremental compilation ever done based on the AST? That is, the compiler would just regenerate code for the parts of the AST that have changed.

I know that many compilers do incremental compilation on a file-basis, but I don't know about on an AST-basis.

The Eclipse Builder infrastructure actually does this, I believe. You might find this link useful.


Is it possible to support .(any symbol) or \d, \w, \W in DFA Is it possible to build DFA that support \d, \w, .(any symbol)?
I understand that we can add each symbol from [0-9] as a separate edge for some of the symbols, but what about the others? for example .(any symbol)? or \S (not white space)?

In other words, can we build equivalent DFA for this NFA

(1) ---a----> (2)
 |
 |
 .(any symbol)
 |
 \/
 (3)

The symbols you mention represent sets of characters. For example, \d represents the set $\{0,1,2,3,4,5,6,7,8,9\}$. Whenever you want to place \d, replace it with 10 parallel edges labeled with all digits instead. The same works for your other examples, as long as each symbol represents one character. (Otherwise you would get a "generalized NFA".)


What does "terms evaluated in related environments yield related values" means in the context of typing judgements? I am reading Theorems for free! by Philip Wadler which is a paper about how to derive theorems from the type signature of a function.

  Parametricity is just a reformulation of Reynolds’ abstraction theorem: terms evaluated in related environments yield related values.

What is an environment in this case ?
More generally, how do I interpret the statement in bold ?

I think I understand the parametricity thing correctly but somehow I cannot map this sentence to something more intuitive.

The environments are related not identical. The context of this statement is logical relations, as described e.g. here. A logical relation is a type-indexed family of relations which follows the structure of the types (in a way I won't elaborate on). If for each type $\tau$, we assign a (binary) relation $R[\tau]$, then given $f:\tau_1\to\tau_2,x:\tau_1\vdash f\, x : \tau_2$ when $R[\tau_1\to\tau_2](f,f')$ and $R[\tau_1](x,x')$ we can ask if it is the case that $R[\tau_2](f\, x,f'\, x')$. This is what it is referring to in "terms evaluated in related environments yield related result".


How to estimate how many assignments satisfy a given DNF formula using Monte Carlo? Admittedly, homework.

For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this formula, for example $C_1=x_1\wedge \neg x_3\wedge x_4$

The tasks is to do this in a little bit more sophisticated way than to choose a random assignment, see if it satisfies the formula, repeat N times. More specifically the tasks tells us to:

Uniformly at random choose a clause $C_i$ in $\phi$.
Set the values of the variables in $C_i$ so that $C_i$ is satisfied.
Set the values of the remaining variables randomly.
In this way sample only satisfying assignments and sample all of them.

I fail to understand: ALL OF THEM? If I want to sample ALL satisfying assignments then I'm not sampling, but rather I'm counting?

Further the task asks:

For a given assignment $p_i$ what is the probability of sampling $p_i$? That's an easy question: $\frac1{2^{n-m}}$ where $n$ is the number or distinct variables in $\phi$ and $m$ is the number of variables in $C_i$. Or am I wrong?
How you can use the result of the previous question (the previous question was to sample trivially as I described above) to construct an estimate for the number of satisfying assignments? I don't know.

Well, I can check if this random assignment satisfies any other clauses than $C_i$. But how can I use the result?

My Googling yielded this page: http://theoryapp.com/dnf-counting-and-the-monte-carlo-method/ But this is even more confusing for me. Instead of choosing the clause $C_i$ uniformly, the site tells us to "pick up a clause $C_i$ with probability $P_i=\frac{\left|S_i\right|}{\sum_{j=1}{l}\left|S_j\right|}$, where $S_i$ is the collection of assignments satisfying $C_i$ and $l$ is the amount of clauses in $\phi$ and then pick up an assignment from $S_i$." But then we are told to "Check whether this assignment satisfies $\phi$. Finally, count the number of satisfying samples; denote the count by $M$". This is nonsense, each assignment that satisfies clause $C_i$ for any $i$ must necessary satisfy the whole formula?

Admittedly, this basic course on probability and statistics is the first course where I feel like a total idiot.

Any tips? I'm loosing hopes to be able to figure this out on my own.

Finally, I'm not sure, is this question more appropriate on scicomp.stackexchange.com?

Let $\alpha$ be a satisfying assignment. Suppose that it satisfies the terms $\{C_j : j \in J\}$. If you choose $C_i$ in the first step, then the probability that you choose $\alpha$ in the third step is 0 if $i \notin J$ and $2^{-(n-|C_j|)}$ if $i \in J$. Hence the probability of sampling $\alpha$, assuming there are $m$ terms, is
$$
p(\alpha) = \frac{2^{-n}}{m} \sum_{j\colon \alpha \text{ satisfies } C_j} 2^{|C_j|}.
$$
Let $A$ be a random satisfying assignment chosen according to the algorithm, and let $X = 1/p(A)$. Then
$$
E[X] = \sum_{\alpha \text{ satisfying}} \frac{\Pr[A=\alpha]}{p(\alpha)} = \sum_{\alpha \text{ satisfying}} = \text{# satisfying assignments}.
$$


Are there regular languages between every two non-regular languages? I have a question regarding regular languages. Given that $L_1$ and $L_2$ are non-regular languages, can a regular language $L$ exist so it is a subset of $L_2$ and $L_1$ subset of $L$?

To be more specific:

$\qquad L_1 \subset L \subset L_2$

for $L_1, L_2$ non-regular Languages.

Hint. Given any sets $A, B, C$ we have $A \cap C \subset C \subset B \cup C$.


How can I solve the recurrence $f(n) = 3f(\frac{n}{4}) + \log(n)$? The master theorem didn't work here. I tried to do the substitution method but I ended up with an additional term: $2Σ(i \cdot 3^i)$. Also I should find the solution $g(n)$ such as $f=\Theta(g)$.

The given recurrence is: $T(n) = 3T(n/4) + \log n$

Using the substitution method, we get:

\begin{align}
T(n) &= 3^2T \left(n/4^2\right) + \log n + 3\log (n/4) \\
     &= 3^3T \left(n/4^3\right) + \log n + 3\log(n/4) + 9 \log(n/4^2)\\
\end{align}
and so on.

Can you see a pattern now?


Modified Counting Inversions problem using divide and conquer Given an array $A$, find the number of pairs $(i, j)$, such that $ i > j$ and $A[i] \ge A[j]$.

This is a modified version of the famous problem of Counting Inversions, only in this version it allows the elements to be equal as well. I have an algorithm for the classical counting inversions problem implemented, so i´d like to know if it can be adapted to solve this version. Thanks ahead.

Link to the algorithm (written in C++):

https://repl.it/@MateusBuarque/CountingInversion

Hint:

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


Enumerate over all halting Turing Machines? I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the natural numbers and checking whether each number describes a syntactically well-defined TM.

I am wondering how it is possible to enumerate over all halting TMs. My intuition tells me that since the halting problem is undecidable, it should not be possible to filter an enumeration of all TM descriptions to only those TM descriptions which describe halting TMs.

Nevertheless, I recently came across a well-reputed Oded Goldreich and Bernd Meyer, Computational Indistinguishability: Algorithms vs Circuits, Theoretical Computer Science 191(1–2):215–218, 2998) that uses an enumeration of all halting Turing Machines (see Proposition 1, pg. 2). I'd appreciate any help in understanding this.

The paper you're referring to is using "enumeration" just to mean "ordered list". Your feeling that such a list can't be computed by a Turing machine is correct. However, the list exists, even though there's no algorithm that will tell us what its members are.

Also, note that it refers to "an enumeration of halting Turing machines", not "an enumeration of the halting Turing machines". So it's just any ordered list of halting Turing machines, not necessarily all of them. It specifically mentions enumerations of polynomial time Turing machines. You might be surprised that these are enumerable, up to equivalence*. This is because you can turn any Turing machine into a polynomial time Turing machine by picking your favourite polynomial and modifying the machine so it rejects if it hasn't in that many steps. Since you can enumerate all polynomials (say, with nonnegative integer coefficients), and you can enumerate all Turing machines, you can combine the two to enumerate all polynomial time Turing machines.

* Two Turing machines are equivalent if they give the same output for every input.


Questions about Amdahl's law? Doing exam papers now and I came across two questions which I cannot get my head around sadly. Both are regarding Amdahl's law and Parallel Computing but they seem rather simple and frustratingly enough I cannot really find a definitive answer to any of those questions.
The questions are:

Why must Amdahl's law always apply to a computation?
Why is the existence of superlinear speedup not in contradiction with Amdahl?

The best description of Amdahl's law I found is this one:

At the most basic level, Amdahl's Law is a way of showing that unless a program (or part of a program) is 100% efficient at using multiple CPU cores, you will receive less and less of a benefit by adding more cores. At a certain point - which can be mathematically calculated once you know the parallelization efficiency - you will receive better performance by using fewer cores that run at a higher frequency than using more cores that run at a lower frequency.

I just cannot find a suitable answer on why the law must be always applied to a computation. And superlinear speedup is just when a parallelised speedup can reach far beyond the speedup of a sequential processor. How would it actually contradict Amdahl's law I do not really know apart from it looking a bit like a glitch in the matrix.

Amdahl's law is used to get an idea about where to optimize while considering parallelism.The theory of doing computational work in parallel has some fundamental laws that place limits on the benefits one can derive from parallelizing a computation. Amdahl's Law have detalied explanation of Amdahl's law and it's use.
Processor comes with some other resources like cache which can affect the performance. So if we add more processor, cache memory also increases. Each processor will get less data size to process that can fit into processor's cache which will increase the Performance(Superlinear speedup). But Amdahl's Law considers processors as the only resource but does not consider cache memory.


Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$ As the title said, prove $T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1 = O(\log(n))$
My approach is to find $c, n_0 \in \mathbb{R}_+$ such that:
$$\forall n \geq n_0, T(n) \leq c\log(n) -d \text{, where d is a constant}$$
Assume the statement is true for every $m < n$, especially $m = \left\lceil{\frac{n}{2}}\right\rceil$, therefore
$$T(\left\lceil{\frac{n}{2}}\right\rceil) \leq c \log(\left\lceil{\frac{n}{2}}\right\rceil) - d $$
$$\iff T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1$$
$$\leq c\log(\left\lceil{\frac{n}{2}}\right\rceil) - d + 1$$
$$= c\log(\left\lfloor{\frac{n}{2}}\right\rfloor + 1) - d + 1$$
$$\leq c\log(\frac{n + 2}{2}) - d + 1$$
$$= c\log(n + 2) - c\log(2) - d + 1$$
$$= c\log(n + 2) - d$$
This is where I stuck and can not go further. I need to eliminate the constant $2$ in $n + 2$. Any help and hint is welcome.
Edit: In term of master theorem. I have to solve this recurrence with substitution method.

If you let T(0) = T(1) = 0, then prove by complete induction for every k >= 1 that T(n) = k for all n such that $2^{k-1} < n <= 2^k$.
k = 1: True because T(2) = 1.
k -> k + 1: Let $2^k < n <= 2^{k+1}$. Then $2^{k-1} < n/2 <= 2^k$, therefore $2^{k-1} < \lceil n/2 \rceil<= 2^k$, therefore $T(\lceil n/2 \rceil) = k$, therefore T(n) = k+1.
So instead of O(log n) you get the much stronger $T(1) + \lceil \log_2 n \rceil$ for all n >= 1.


How can i design this function using only NAND and XOR gates? I have this initial function \begin{split}(\overline{A}+\overline{B})(\overline{D}+\overline{C})+AB\overline{(\overline{C}+\overline{D})}\end{split}
Which i reduced to \begin{split}{\overline{AB}*\overline{CD}}+ABCD \end{split}
The first part is easy to do with NAND but the OR ABCD part i have no ideia how to do...I suspect thats where the XOR comes in and i maybe shouldn't have reduced so much the function.

I have assumed that only 2 input NAND gates are available.

For $\overline {AB}*\overline {CD}$

Take A and B as input and feed them to a NAND gate. U will get $\overline {AB}$.
Similarly u can get $\overline {CD}$.

Now feed $\overline {AB}$ and $\overline {CD}$ as input to another NAND gate . U will get AB + CD using demorgan law.

For ABCD take $\overline {AB}$ and complement it using a NAND gate to get AB.
Take $\overline {CD}$ and complement it to get CD. Now feed AB and CD to NAND gate. You will get $\overline {ABCD}$.

Now feed (AB+CD) and (ABCD)' to NAND gate. U will get $\overline{(AB+CD)\overline{(ABCD})}$.Apply demorgan law. U have ur answer.

The trick is to express the function as a sum of products which u already have. Now derive the complement of each product term. When all product terms have been derived then feed then to a NAND gate. This final NAND gate will complement the already complemented product terms and add them thus giving the desired answer.


Finding the number of distinct permutations of length N with n different symbols I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are.

For example if the string is of length ten as $w = aabbbaabba$, the total number of permutations will be

$\qquad \displaystyle \frac{|w|}{|w|_a! \cdot |w|_b!} = \frac{10!}{5!\cdot 5!}$

Now had the string been of distinct characters, say $w'=abcdefghij$, I would have found the permutations by this algorithm :

for i = 1 to |w|
  w = rotate(w)
w = rotate(w)
return w.head + rotate(w.tail)

Can some one throw new ideas on this - how to find the number of permutations for a string having repeated characters? Is there any other mathematical/scientific name of for what I am trying to do?

The total number of (different) permutations of strings with $n_i$ characters of type $i$ is given by
$$\frac{(\sum_i n_i)!}{\prod_i n_i!}.$$
In other words, if the length of the string is $n=n_1 + n_2 +...$, you have
$\frac{n!}{n_1!n_2!n_3!\ldots}$ different permutations.
Note that the formula fits your simple case.

Why is this formula correct?

Because $n!$ is the number of permutations. But some permutations give the same string (e.g., aa rotated is still aa). Then we need to "remove" all the permutations that give the same string. For a given string, for each letter $i$, there are $n_i$ permutations that are identical to the string we started with. So (for each possible letter $i$) we divide by this number to get the final result.


Why Do Computers Use the Binary Number System (0,1)? Why Do Computers Use the Binary Number System (0,1)? Why don't they use Ternary Number System (0,1,2) or any other number system instead?

Since we're in Computer Science, I'll answer this way: they don't.

What do we mean by a "computer?" There are many definitions, but in computer science as a science, the most common is the Turing machine.

A turing machine is defined by several aspects: a state-set, a transition table, a halting set, and important for our discussion, an alphabet. This alphabet refers to the symbols which the machine can read as input, and that it can write to its tape. (You could have different input and tape alphabets, but let's not worry about that for now.)

So, I can make a Turing machine with input alphabet $\{0,1\}$, or $\{a,b\}$, or $\{0,1,2\}$,
or $\{\uparrow,\downarrow\}$. It doesn't matter. The fact is, I can use any alphabet I choose to encode data.

So, I can say that $0001001$ is 9, or I can say that $\uparrow \uparrow \uparrow \downarrow \uparrow \uparrow \downarrow$ is 9. It doesn't matter, since they're just symbols we can distinguish.

The trick is that binary is enough. Any sequence of bits can be interpreted as a number, so you can convert from binary to any other system and back.

But, it turns out unary is enough too. You can encode 9 as 111111111. This isn't particularly efficient, but it has the same computational power.

Things get even crazier when you look into alternate models of computation, like the Lambda calculus. Here, you can view numbers as functions. In fact, you can view everything as functions. Things are encoded not as bits, 0s and 1s, but as closed mathematical functions with no mutable state. See the Church numerals for how you can do numbers this way.

The point is that, 0s and 1s is a completely hardware specific issue, and the choice is arbitrary. What encoding you're using isn't particularly relevant to computer science, outside of a few subfields like operating systems or networking.


In what sense if any does java have multiple dispatch? I'm trying to get my head around the difference between message passing (with which we are all familiar as by far the most common form of object orientation today) vs generic functions as implemented in CLOS (Common Lisp Object System).

In what sense is it possible to say java has a kind of multiple-dispatch system due to method overloading?

To sketch my understanding, in message passing you might do:

tell obja move objb
tell objb move obja

but where the function is first class and not in any object, you might do:

move obja objb

The part I do think I understand is that with generics there is no dilemma on where to place a function, whereas in message passing you may have to arbitrarily choose which class to put a function on, then just remember which one you put it on. With message passing, if you want to be able to call the behaviour from either, you have to duplicate the code (yes I know there are ways round that, but that's not the point).

I'm not sure I'm really getting the rest of how generics are different yet.

I just found a key reference on this point.

The wiki page on CLOS is also very good.

So, maybe best method is to hold off with the theory and just practice with clojure multi-methods at some point... unless anyone wishes to chip in.

In what sense is it possible to say java has a kind of multiple-dispatch system due to method overloading?

In no sense. What Java's method overloading gives you is dynamic dispatch, not multiple dispatch.

The most commonly seen example of multiple dispatch in Java is its event listener system, where you can register multiple listeners which will all be triggered when an event occurs.


Polynomial Time Reduction - Does 0 calls to the black box still imply a reduction? Using the following definition:

  Reduction: There is a polynomial-time reduction from problem $X$ to
  problem $Y$ if arbitrary instances of problem $X$ can be solved using:

  Polynomial number of standard computational steps, plus
  Polynomial number of calls to oracle that solves problem $Y$.

  Notation $X \leq_{P} Y$

Say we had the case where $X$ can be solved in polynomial time using $O(n\log n)$ of computational steps, with zero calls to the oracle / black box used to solve instances of $Y$.

Can we still say $X \leq_{P} Y$? As 0 still classifies as a polynomial number of calls to the oracle that solves problem $Y$, and a polynomial number of standard computation steps were used to solve $X$.

Yes. As you note, $f(n) = \sum_{i=0}^{k}0\cdot n^{i} = 0$ is a perfectly valid polynomial in $n$ (for every fixed $k$).

What you have left over without the oracle calls is just a polynomial time algorithm. This observation also underlies the fact that any polynomial-time solvable problem has a polynomial-time reduction to any other non-trivial problem.


Simple Representation of Matrices with the Given Equivalence Relationship I'm currently working on an algorithm that requires me to come up with unique matrices. Two matrices are considered equivalent if one's rows and columns can be swapped to make it match the other. For example, $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix} \equiv \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} \not\equiv \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \not\equiv \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}$. I think it would be immensely helpful to find a nice way to represent each matrix so that equivalent matrices have the same representation. The best I could come up with is just making a list of the rows and columns and comparing them. For example, $\begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}=>\{R:((0, 0), (1, 1))\}, \{C:((0, 1), (0, 1))\} $ $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}=>\{R:((0, 1), (0, 1))\}, \{C:((0, 1), (0, 1))\}$ $\begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix}=>\{R:((0, 1), (0, 1))\}, \{C:((0, 0), (1, 1))\}$

but I feel like there's a better way because this looks messy. Any suggestions?

Edit: This is not always binary matrix. Numbers can range from 0-19.

When you are dealing with binary matrices, this is the problem of graph canonization.  There is no known polynomial-time algorithm for this problem, and determining whether it can be done in polynomial time is a famous open problem, but there are techniques that are often reasonably efficient in practice (e.g., Nauty).  (The relationship is that every graph corresponds to a binary matrix, namely, it adjacency matrix, and versa.)

When you have non-binary matrices, you can think of this as a graph with labels on the edges.  There are standard techniques for reducing this to the standard graph canonization problem, by converting each labelled edge to a small subgraph.  See, e.g., Graph isomorphism problem for labeled graphs, On graph isomorphism for weighted graphs, What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?.


Nested loops: Still $\mathcal O(n)$? I have an algorithm similar to this:

i=1
while(i < n) {
  //something in O(1)
  while(i < n && cond) {
    //something in O(1)
    i++
  }
  i++
}

Where "cond" is some condition which can be checked in $\mathcal O(1)$. It is clear that this algorithm is $\mathcal O(n^2)$. But is it also $\mathcal O(n)$?

I'd say yes because the statement "i++" is executed $\mathcal O(n)$-times since both loops end when i reaches n.

Is it possible to rewrite the algorithm in a form with equivalent runtime so that it can be seen more clearly?

What you have there is not a true nested loop. It's one loop with, what is equivalently an if-test in there, like:

while(i<n){
   if(cond)
      //something Θ(1)
   else
      //some other Θ(1) thing
   i++
}

Notice in your case, you have the same variable for both loops with no reset.

So, to answer your question, the running time is $\Theta(n)$.  In particular, it is $O(n)$.

As a commenter states, anything that is $O(n)$ is also $O(n^2)$.


Decider for the family of Turing machines that move infinitly to the right on some input I need help finding an algorithm which, given a Turing machine description $\langle M \rangle$, decides whether there exists an input $w$ such that in the computation of $M(w)$, the head only moves right and $M$ never stops.

Given a Turing machine $M$ for which such an input exists, what does $M$'s state graph look like?

   For some input $w$, there is a computation of the form $q_0 \leadsto q (\leadsto q)^\omega$ whose transitions all have movement $R$ (or $N$, depending on the meaning of "only"). Therefore, the state graph has to have an "$R$-path" from $q_0$ to some $q$ which lies on an "$R$-cycle".

Is this also a sufficient criterion? The answers to both questions lead you towards a decision procedure.


I/O cost to traverse a tree stored in preorder form Let T be a binary tree that is stored in the disk following the preorder layout.

For example if this is $T$:

then $T$ will be stored in the disk as follows:

10, 11, 0, 12, 13, 2, 7, 3, 14, 1, 15, 16, 4, 8, 17, 18, 5, 9, 6

Every node of the tree is a struct that stores the offset of the left child, the offset of the right child, the id of the node and a size variable. If a node is a leaf the offsets are set to -1.

Suppose that now in every node $u \in T$ we want to know what is the size of the subtree rooted on $u$. Assume that the elements between the disk and the memory are transferred in blocks of size $B$, the size of the memory is $M$ and it holds that $M \geq B$. Is it possible to do that in  $O(\frac{N}{B})$ I/Os?

It is possible to do it in $O(\frac{N}{B})$ if you have $B + D$ memory available, where $D$ is the maximum depth of the tree. Algorithm:

Read $B$ nodes into a buffer.
For each node in the buffer:

Push $(node.id, num\_children(node), 0)$ to stack $S$ (respectively $(id, num, d)$).
While $S.peek().num = 0$:

$d = S.peek().d$
Output $(S.peek().id, d)$.
$S.pop()$
$S.peek().num = S.peek().num - 1$
$S.peek().d = max(S.peek().d, d + 1)$.

If there are more nodes to process, go to 1.

The idea behind this algorithm is to associate pushing on the stack with going down a child node, and popping coming back up to a parent node.

If we initialize every node with a counter containing the number of child nodes, and we decrement this counter everytime after popping, it means that once the counter hits 0 we have visited every child node as we visit this node: we are in post-order.

We also store a maximum subtree size $d$ with every node. If we pop (go back to visit the parent node) we store the maximum of $node.d$ and $child\_node.d + 1$ into this node. This means that once we are in post-order we have the maximum size of all child subtrees + 1 stored in $d$.


Prove L to not context free using pumping lemma on language L $L = \{0^i1^j0^i1^j|i,j \geq 0\}$

I've tried letting $s = 0^p1^p0^p1^p$. But not sure where to go from here. Help would be appreciated.

Hints

What is the language $K = L \cap 0^*10^*1$ ?
Apply the pumping lemma to $K$ (or to $L$ directly).


I can verify solutions to my problem in polynomial time, how would a non-deterministic algorithm arrive to a solution if it always takes $2^n$ bits? Decision Problem: Given integers as inputs for $K$ and $M$. Is the sum of $2^k$ + $M$ a $prime$?
Verifier
m = int(input('Enter integer for M: '))
sum_of_2**K+M=int(input('enter the sum of 2^k+m: '))

if AKS.sum_of_2**K+M == True:

  # Powers of 2 can be verified in O(N) time
  # make sure there is all 0-bits after the 1st ONE-bit

  # Use difference to verify problem

  if sum_of_2**K+M - (M) is a power_of_2:
    OUTPUT Solution Verified

The powers of 2 have approximately $2^n$ digits. Consider $2^k$ where $K$ = 100000. Compare the amount of digits in $K$ to the amount of digits in it's solution! Also take note that the powers of 2 have $2^n$ bits as its 0-bit Unary essentially for the exponent $n$.
Question
How would a non-deterministic machine solve this problem in polynomial time?

As I see it, this decision problem is obviously in P. Therefore, there is nothing for non-deterministic Turing machine to guess. Non-deterministic Turing machine would call polynomial-time verifier for a given problem instance and the problem would be solved in polynomial time.


What is the Haskell-style type signature called (i.e., who is it named after)? A type signature in Haskell is written in the following format:

functionName :: arg1Type -> arg2Type -> returnType

There's a (hyphenated, after a person or persons) name for this style of type signature (which predates Haskell), but it's escaping me and I can't find it anywhere.

Is it Hindley-Milner type system by any chance?


Efficient algorithm to simulate dealing cards from a large deck of cards? In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are N players, card i goes to player i mod N). If the number of each type of card is known, is there a way to simulate dealing the cards and get a count of each type of card each player has?

For example, if there are N=3 players, and there are 5 card types and the count of each card is [3000000000, 3000000000, 3000000000, 3000000000, 2], one possible output is [1000000000, 1000000000, 1000000000, 1000000000, 1], [1000000000, 1000000000, 1000000000, 1000000000, 1], [1000000000, 1000000000, 1000000000, 1000000000, 0], which represents the number of cards of each type that each player has.

A naive algorithm is to create a large array of all of the cards, do the Fisher–Yates shuffle on it, and then go through each element and increment the count of the card for the current player and set the current player to the next player. For the example above, this creates an array of size 12000000002 and requires that many iterations, but there are only 5 card types and 3 players (output is size 15).

Is there a more efficient algorithm? It would have to generate the output with the same probability that the naive algorithm would.

In the special case of two players and two card types, this is exactly the hypergeometric distribution. More accurately, the number of cards of the first type that the first player gets is distributed hypergeometrically; and the rest of the deal can be deduced from that.

Conversely, you can simulate the entire dealing process by sampling appropriate hypergeometric distributions. Indeed, the number of cards of the first type that the first player gets had hypergeometric distribution. After deciding that amount, remove these cards and reduce the number of cards that remain for the first player and repeat, until you have detail the first player their entire hand. Then repeat with the other players.

The two problems are thus equivalent. Presumably there are online resources, and probably even libraries, for sampling hypergeometric random variables efficiently.


Computing a partial density matrix from an amplitude vector Suppose you're given the list of $2^{2n}$ complex coefficients defining the state of a $2n$ qubit register. You want to compute the $2^n \times 2^n$ density matrix of the first $n$ qubits.

Is it possible to compute the result in $O(4^n)$ time? That would be optimal, since the output has size $\Theta(4^n)$.

It's easy to hit $O(8^n)$. The naive algorithm that simply computes the density matrix for each possible value of the unrelated qubits and then adds those together achieves that:

def density_matrix_of_first_half(amplitude_vector):
  v = amplitude_vector
  M = new complex[2^n, 2^n]
  for r < 2^n:
    offset = r * 2^n
    for i < 2^n:
      for j < 2^n:
        M[i, j] += (v[i + offset] * v[j + offset]).conjugate()
  return M

But I was hoping it was possible to do better. Are there any papers about this problem?

(The reason I care so much more about $4^n$ vs $8^n$ is because I'm actually computing things with a GPU. My textures can have $2^{2n} = 4^{n}$ pixels, so I get the $4^n$ inner-loop in the application of a single shader. But $8^n$ is far over the max texture size, so the $8^n$ algorithm would require a pipeline of $2^n$ shaders. Or at least might force me to drop the qubit limit another 30%.)

It's a matrix multiplication. Not sure how I didn't notice it right away, but the problem is exactly computing $U \cdot U^\dagger$ for a $U$ whose rows are made up of the chunks of amplitude vector.

def density_matrix_of_first_half(amplitude_vector):
  U = new ComplexMatrix(2^n, 2^n)
  for i < 2^n:
    for j < 2^n:
      U[i, j] = amplitude_vector[i + (j << n)]
  P = U * U.adjoint()  // <-- expensive
  return P

Fancy matrix multiplication does asymptotically better than the naive algorithm

Matrix multiplication can be done in time $O(n^\omega)$, where $n$ is the dimension of the matrix and $\omega$ is known to be below $2.375$. It's conjectured that there may be algorithms where $\omega = 2 + \epsilon$, but no one's managed to find any yet.

In the context of the question with $2^n \times 2^n$ matrices, the complexity is $O(2^{n \omega})$. However, because the asymptotically faster algorithms tend to have large constant factors hidden by the Big-O notation, in practice it's often better to stick with naive multiplication or Strassen multiplication. Also there are probably GPU-optimized matrix multiplication algorithms that would be more relevant given the note at the end of the question.

$U \cdot U^\dagger$ is not easier than $U \cdot V$

General matrix multiplication combines two totally independent matrices $U \cdot V$. Given that our density matrix problem only computes $U \cdot U^\dagger$, where the two inputs are totally dependent, one wonders if this "adjoint-squaring" is easier than general multiplication. Turns out it's not.


is $P_{CTC} = BPP_{path}$? I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic.

This is my reasoning, and I would like to know if (1) this is already known or (2) I misunderstood something or (3) I just found out something useful:

$P_{CTC}$ is the class of problems that can be solved by putting polynomial amounts of data in a time machine.

$BPP_{path}$ is the class of problems that can be solved by postselecting in a probabilistic Turing machine, i.e. ignoring cases you do not care about.

$P_{CTC}\subseteq BPP_{path}$ because you can simulate a closed time-like curve with postselection like this: Scan the entire program in the beginning, both state and memory. Then, after processing, do so again and postselect so that you only return if the state & memory now are exactly equal to the start state & memory (except for a single bit that says whether or not this is the first iteration, to prevent an infinite loop).

$BPP_{path}\subseteq P_{CTC}$ because you can simulate postselection like this: If the message from the future starts with $1$, send the message $0$ into the past. Otherwise proceed as normal. When you get to the step where you would normally post-select, send a 1 into the past iff. you want to ignore this timeline, else a $0$. The only consistent version is now the one where you both receive and send a 0 because you were satisfied with the results.

I believe I have found the answer: The proof is wrong. BPP_PATH is not in P_CTC because P_CTC is required to give a single definite answer, while BPP_PATH is a probabilistic algorithm, so the second reduction does not work. For it to work, one would have to use the time-travel information to count the number of successes of the probabilistic algorithm vs the number of its failures. I have no idea how to do this, or if it even can be done (probably not).


MST and some facts via an example $M$ is an MST of the Weighted Graph - $GR$.
Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}.
Let $A$  be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}.
If $e$ is a edge of $M$ then ($M-${$e$}) is a forest of $M1$ and $M2$ trees such that for $M_i, i=1,2$ is a MST of Induced Graph $GR$ on vertexes $T_i$.
My notes tell me that the first and last is false. I need some idea of how to understand the validity of these sentences in a more simple and concise manner.

Preamble
I'll use the following example to illustrate each statement. The graph below will be $GR$.

Below is the MST $M$ of $GR$. These are the bolded edges.

Statement One
The first statement is false if $A$ is an internal vertex of $M$. In that case, $M-\{A\}$ will result in a forest, which is not an MST.
Suppose we choose $A = d$, then $M-\{A\}$ will result in the following graph which is not a tree.

Statement Two
The second statement is true. It is pretty easy to see why $M-\{A\}$ in this case is still an MST.
Suppose we choose $A = a$ (our only choices are $\{a,g,i\}$), then $M-\{A\}$ (left) will result in the following tree. We can compare it to $GR-\{A\}$ (right) and see that it is an MST.

Statement Three
The third statement is true.
Formal Proof of Statement Three
Proof: Let $GR[T_1]$ and $GR[T_2]$ be induced subgraphs of $GR$ and $M_1'$ and $M_2'$ are their MSTs respectfully. Let $X$ be the set of edges that connect vertices of $T_1$ and $T_2$ in $GR$ (note $e \in X$).
To show $M_1$ and $M_2$ are MSTs, we must show is $M_1 = M_1'$ and $M_2 = M_2'$.
Let $w(M) = w(M_1) + w(e) + w(M_2)$ be the cost of the MST of $GR$.
Let $w(M_1')$ and $w(M_2')$ be the cost of the MST of $GR[T_1]$ and $GR[T_2]$.
Construct the graph $M' = M_1' \cup e \cup M_2'$. This graph is the MSTs of both induced graphs and a single edge that connects them. Note, we could use any edge from $X$, however for it to be a MST, we must select the minimum cost edge of $X$. So $w(M') = w(M_1') + w(e) + w(M_2')$.
Since $w(M_1')$, $w(e)$, and $w(M_2')$ are minimal, then $w(M')$ is minimal. Since $w(M')$ is minimal, then $w(M') = w(M)$. So,
\begin{align}
w(M_1') + w(e) + w(M_2') &= w(M') \\ &= w(M) \\ &= w(M_1) + w(e) + w(M_2).
\end{align}
So $w(M_1') = w(M_1)$ and $w(M_2') = w(M_2)$, thus $M_1' = M_1$ and $M_2' = M_2$. Hence, $M_1$ and $M_2$ are MSTs.
Intuition of Proof
I'll pick $e = \{c,d\}$ to be the edge with weight one for this example. Below is $M-\{e\}$

Let $M_1$ be the tree on the left and $M_2$ be the tree on the right. Then $T_1 = \{a,b,c\}$ is the vertex set of $M_1$ and $T_2 = \{d,e,f,g,h,i\}$ is the vertex set of $M_2$. We need to construct the induced subgraphs of $GR$ on $T_1$ and $T_2$, $GR[T_1]$ and $GR[T_2]$. Below on the left is $GR[T_1]$, and below on the right is $GR[T_2]$.

Now you can see the $M_1$ is the MST of $GR[T_1]$ (similarly for $M_2$).
In the proof, we abuse the fact that the MST of the induced subgraph and the original graph are minimal. We also use the fact that $M$ must contain $e$, the smallest edge that connects $M_1$ and $M_2$. We can conclude the only MST of the induced graphs is $M_1$ (for the left) and $M_2$ (for the right).
I hope this helps!


Free and Bound in Lambda Calculus Here's something from Slonneger's "Syntax and Semantics of Programming Languages":

  A variable may occur both bound and free in the same lambda
  expression: for example, in λx.yλy.yx the first occurrence of y is
  free and the other two are bound.

I assume the free variable is the y right after the λx. and the bound y's are the λy.y which I can sort of intuitively grasp. So ((λx.yλy.yx)a)b) would reduce to (yλy.ya)b) then to bba ? Can someone explain how this came to be? In the end it's the expression b twice. Can someone perhaps provide more examples of bound and free variables?

I've added brackets to disambiguate $$\lambda x.(\color{red}y (\color{green}{\lambda y}.(\color{blue}yx)))$$ the red $y$ is free and the blue one is bound by the green abstraction. I don't think it makes sense to say that the green $y$ is bound, but it together with the lambda is a binder.

We can beta reduce the term once

$$\begin{array}?
&& \lambda x.(y (\lambda y.(yx)))ab \\
&\to_\beta& (y (\lambda y.(ya)))b
\end{array}$$

but no further, as there are no remaining redexes left.


Course teaching time complexities in real life systems Having mis-read What course in CS deals with the study of RAM, CPU, Storage? I now wonder what course in CS deals with time and space complexities including GPUs, CPU caches in multiple levels, seek times on hard disk vs. SSDs, and bandwidth to disk and RAM.
I was taught the big O-notation but it never took into account that I might have a GPU with 100s of cores, or a limited amount of extremely fast cache, or a harddisk that is has a high bandwidth, but a high seek time.
Which class teaches this extended version of algorithm time complexities, which takes real world limitations into account?

I don't think these things are usually treated as a single topic in either research or education, but there are quite a few adjacent topics that are relevant. I'll list some here, starting with...
I/O-complexity
One perspective on the algorithmic analysis of computer storage, memory and caches is the field of I/O-complexity or external memory algorithms. These lecture notes from a course by Mark de Berg are a good introduction (in Part II). Note that this perspective assumes an abstract I/O model that has a two layer memory hierarchy (a small and fast internal memory and a big but slow external memory), which of course is a simplified version of what a modern computer has. Still, this perspective makes it possible to design efficient algorithms for dealing with massive data (think running an algorithm on an array/matrix a few ten GB big, or more!).
Another advantage of treating "external memory" only in the abstract means that we only need to design one algorithm to deal with both SSD's, hard-disks, or even a slow internet connection, as long as we are satisfied with treating our external memory as a monolithic blob. There are many other tricks you may want to try in practice, but this is highly dependent on your specific machine or operating system.
Operating Systems
Okay, but what if I really want to know how to use multiple cache layers, how to ensure seeking goes efficiently on my hard-disk, or how to play nice with my OS's paging? These topics (among others) are usually treated in a course called "Operating systems". Another aspect that frequently is the focus of such a course is concurrency (e.g. how does your OS manage to run all those processes "at the same time"? ), and dealing with multiple processes and threads programmatically. Some mild form of parallelism may also be covered.
Parallelism
So, what about those 100s of computing cores? Making use of those things to compute efficiently is known as parallelism and courses with that word in their title are common. There are quite a few models there to use in the analysis of parallel algorithms, the PRAM model is common. Again, this is an abstract model that may or may not allow you to use the full power of your expensive GPU (or arrays of relative cost-efficient Sony Playstation 3 cores. Cryptanalystist are a rare breed of "mostly theoretical" computer scientists that actually have use of massive computation power, see these slides of Dan Bernstein on some thoughts of using GPU's for crypto).
However, unless you have a very extreme needs for high performance computing, "using GPUs" in practice usually means using one of the APIs/frameworks designed to use them, like OpenGL. There are courses called computer graphics or something similar that teach how to work with these APIs.
Speaking of high performance computing, this is a field of its own, a bit on the intersection of parallel and distributed computing. (see also this answer for the difference between distributed computing, concurrency, and parallelism)
I should also mention that there are also courses on databases that go beyond just teaching how to use them and also teach how all those operations are implemented efficiently.
But nobody will teach you this one simple trick!
We've already covered quite some courses, certainly enough to fill a few semesters, but you may have already gathered from the multiple caveats above that there's always a manner of tricks that simply depend too much on the specifics of your setup that there's no good reason to teach it, or do theoretical research on. Still, having the knowledge of the courses above at least should give you a good idea on when it might be a good idea to depend on some strange trick, or whether there actually is a well-understood way to solve your problem. One interesting trick is to compress everything and make it fit in main memory. (see also the video explaining how their entire system works)


How to prove that ε-loops are not necessary in PDAs? In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a proof that uses only automata; therefore, I have to show that heap automata can be simulated by LBAs (or an equivalent model).

I expect the proof to work similarly to showing that pushdown automata accept a subset the context-sensitive languages. However, all proofs I know work by

using grammars -- here the fact is obvious by definition -- or
are unconvinvingly vague (e.g. here).

My problem is that a PDA (resp. HA) can contain cycles of $\varepsilon$-transitions that may write symbols to the stack (resp. heap). An LBA can not simulate arbitrary iterations of such loops. From the Chomsky hierarchy obtained with grammars, we know that

every context-free language has an $\varepsilon$-cycle-free PDA or
the simulating LBA can prevent iterating $\varepsilon$-cycles too often.

Intuitively, this is clear: such cycles write symbols independently of the input, therefore the stack (heap) content does only hold an amount of information linear in the length of the cycle (disregarding overlapping cycles for now). Also, you don't have a way to get rid of the stuff again (if you need to) other than using another $\varepsilon$-cycle. In essence, such cycles do not contribute to dealing with the input if iterated multiple times, so they are not necessary.

How can this argument be put rigorously/formally, especially considering overlapping $\varepsilon$-cycles?

The removal of $\varepsilon$-transitions has been studied for the more
general model of valence automata by Zetzsche [1].
Valence automata are essentially finite automata with a monoid for storage.

Among other things, Zetzsche shows that for monoids $M$ from a rich class $\mathcal{C}$ of monoids
(which contains (partially) blind counters, stacks, and combinations thereof),
$\varepsilon$-free $M$-automata accept the same class of languages as $M$-automata.

Since PDAs with a $k$-symbol stack alphabet correspond to valence automata over
monoid $\mathbb{B}^{(k)} \in \mathcal{C}$ ($\mathbb{B}$ is the
bicyclic monoid),
the result from Theorem 1 (resp. 7.1 in the preprint) applies here.

The proof is long and technical; the proofs of lemmas 8 and 10 (resp. 7.6 and 7.9)
contain the relevant constructions. Note that while they do not use grammar models
(as required in the question) they do use valence transducers.

Silent Transitions in Automata with Storage by G. Zetzsche (2013) [more elaborate preprint on arXiv]