First of all, this problem is (weakly) NP-hard, see this paper by Ekberg and Yi, because it generalizes the problem of deciding which task sets are schedulable by Rate Monotonic.

However, assuming that your periods and execution times are integers, you can find the answer in pseudopolynomial time. Simply try all values of $X$ from $0$ to $p$, where $p$ is the period of the task with variable execution time. For each of these values, simulate the Rate Monotonic algorithm until time $\max_{i=1}^n p_i$ (that is, the largest period in your task set), to check that the task set is schedulable. The largest value of $X$ for which your task set results schedulable in the simulation will give you the answer.

You might be able to do somewhat better if you have more information about your tasks. For example, if the variable task is the one with largest period (not true in your example), I think the following will work:

Simply simulate the Rate Monotonic algorithm time step by time step, as if $X$ was infinitely large, and doing the following in addition:

Initialize a counter $K$ to zero.
At every time unit in which Rate Monotonic tells you to run the lowest priority task, you increase the counter $K$ by one.
After $p_n$ time units (where $p_n$ is the period of your lowest-priority task), stop the simulation.

The value of $K$ at the end of the simulation will be the largest possible value of $X$.


What does apostrophe-like symbol in the superscript mean?

That's a prime.

  In mathematics, statistics, and science, the prime is generally used to generate more variable names for things which are similar, without resorting to subscripts – $x'$ generally means something related to or derived from $x$.


Find a CFG for the set of prefixes of a CFL

If you know how to do Suffix, then you also know how to do Prefix. Explicitly, show how transform a context-free grammar for a language $L$ to a context-free grammar of its reverse $L^R = \{x^R : x \in L \}$, where $x^R$ is the word $x$ in reverse (for example, $(for)^R = rof$). Then use the fact that
$$ \mathit{Prefix}(L) = \mathit{Suffix}(L^R)^R. $$
If you unroll this definition, you will actually get a direct construction for Prefix.


$X \vdash Y$ means "The information in $X$ lets you prove that $Y$ is true." This is true in logic in general, as well as in type theory specifically. I often read this as "$X$ says that $Y$ is true."

So,

  If $\Gamma\vdash t\colon T$ and $x\notin\mathrm{dom}(\Gamma)$, then $\Gamma,x\colon S\vdash t\colon T$

translates as

  If we can prove that that $t$ has type $T$ using $\Gamma$, and $\Gamma$ doesn't directly assign a type to $x$, then adding to $\Gamma$ the assumption that $x$ has type $S$ doesn't change the type of $t$,

which is just my way of writing what you wrote.


Results on the difficulty of specific random 3-SAT problems?

Research has concentrated not on the number of satisfying assignments, but on the clause density $\alpha$. It is (more or less) known that:

Below a certain threshold, the problem is easy. Moreover, the solution set is "continuous" (with high probability), in that all solutions are (more or less) connected.
After a certain threshold, there are no satisfying assignments (with high probability).
Between the two thresholds, the instance is satisfiable (with high probability), but a satisfying assignment is conjectured to be hard to find. Moreover, the solutions belong to exponentially many small clusters that are "far away" from each other: any path connecting them goes through an assignment that satisfies a relatively small fraction of clauses.

These thresholds have been calculated by physicists, but their work is not mathematically rigorous. Rigorously much is known, especially for random $k$-SAT and similar problems for large $k$, but the actual behavior for 3SAT hasn't been rigorously proven.

The literature on the area is enormous, but unfortunately I can't find a recent survey, though these probably do exist. You can start by reading a very short, relatively recent survey by Coja-Oghlan. A recent important rigorous result is Ding, Sly and Sun, who prove rigorously that the unsatisfiability threshold for $k$-SAT exists for large enough $k$.


What can't you do without Turing-completeness?

Real world computers are not Turing complete (they have a finite amount of memory) and are equiparable to Linear Bounded Automata.

So the easiest way to design a non-Turing-complete language is to design a language that has only a limited amount of memory (the memory can also be a function of the input length) and don't worry about other restrictions.

But as soon as you allow some kind of unboundness it's not an easy task to avoid Turing completeness, for example two variables that can store an arbitratrily large integer, a JUMP operator, an IF condition and a + operator already defines a  Turing complete language (Counter mmachines).

It's curious that even some games (Chess, Magic The Gathering, Minecraft, ...) if you allow level/boards of unbounded size.

The common way is to use bounded loops or bounded recursion; you can take a look to some real-world non Turing-complete languages: SQL, data languages (e.g. Regular expressions,HTML,...), LOOP language, Charity, ...


This is the circuit minimization / logic optimization problem.   You have a circuit with some number of inputs (one per predicate p1, .., pn; or based on the representation of x)  and ~ 1k outputs (one per formula f1, .., fm).  Now the goal is to construct another equivalent circuit that computes the same output, as efficiently as possible.  That's a circuit minimization problem.  The problem is hard in general, but there are some heuristics and tools that may be effective in many situations (e.g., Espresso, Quine-McClusky, BDDs, and more).  I suggest reading about that subject and trying out one of those tools or techniques.


Shortest Minimax Path via Floyd-Warshall

No need to introduce two arrays. In the original algorithm the distance equals the minimum (over all paths) of the sum of edges (in the path). The new variant defines a distance as the minimum (over all paths) of the maximum of edges (in the path).

Then one only needs to rethink the instruction

       final int d = ds[i][k] + ds[k][j];

In my understanding of Floyd-Warshall the array ns stores the highest number of the shortest path: it is updated to k each time a shorter path is found. To retrieve the path itself I would use a recursive procedure short[i,j] = short[i,k] + short[k,j] where k=ns[i,j] and provided k<>i and k<>j. (adapted to your programming syntax)

In that way no vertex will be repeated on a shortest path, but that part of Foyd-Warshall I always find hard to explain.


What are examples of inconsistency and incompleteness in Unix/C?

The question's title suggests that some basic user interface inconsistencies may interest you:

Unix commands don't follow any particular syntax for specifying options and flags. For example, most commands use single letters preceded by '-' as flag: cat -n some_file, but exceptions like tar tf some_file.tar and dd in=some_file out=some_other_file count=2 exist in commonly used commands.

Unix and its descendants and relatives have multiple slightly different regular expression syntaxes.  Shells use "*" where other programs (grep, egrep, vi) use '.*'.  egrep has '+' and '|' as operators, grep does not.

The basic "everything is a file" system call interface could be viewed as incomplete: read/write/seek/close doesn't fit every I/O device.  Badly needed exceptions get lumped into "ioctl" calls, but devices like sound cards don't even fit that very well.


Do problems that have unary encodings automatically become unary languages?

A unary language is a subset of $\sigma^*$ for some letter $\sigma$. If your language is of this form, then it is unary. Otherwise it isn't.

A unary encoding is an encoding of some data as a subset of $\sigma^*$. For example, one possible unary encoding of the natural numbers is $n \mapsto 1^n$. Any language in which instances are unary encoded is a unary language, simply because it is a subset of $\sigma^*$. For example, the language of all primes encoded in unary is a unary language.


Examples of interesting semantics to study during a small project for a graduate Semantics course

You could add more flow control to IMP, like (simple) exceptions, or break to exit early from a while loop.

You could some partial operators (division, square root) requiring you to handle runtime errors.

You could add more complex data types, like pairs. Make it so that e.g. projecting a value out of a non-pair value causes a runtime error. Craft a (first-order) simple type system e.g. using T ::= int | (T*T) as types, and prove that "typeable programs do not go wrong", i.e. executing them never lead to runtime errors.

You could add functions / procedures. This is not so trivial at first, especially if you want to consider several ways for parameter passing (e.g. pass-by-value, pass-by-reference).

You could prove that a suitable restriction of IMP (say, sans while, or with a constrained while) is always terminating.


Correctness of the Betweenness centrality formula

However it doesn't seem to me that the formula calculates what is defined.

The formula is right. The betweenness centrality is a value in an interval $[0, \ldots, 1]$. Thus, if the betweenness centrality of node $v$ is equal to $1$, then all shortest paths between two nodes of this graph pass through $v$. I will explain the correctness of this summation below.

  Why do we divide by the total number of shortest paths between s and t each time?

You are developing a summation of the percentages. This is needed to ensure that this sum will never exceed $1$. Suppose that you have $m$ different $s$-$t$ pairs of vertices in your graph. Thus, $\sigma_{st} = m$ and your summation goes through all $m$ $s$-$t$ pairs.
One can note that the term $\sigma_{st}(v)$ on this equation is binary (the shortest $s$-$t$ path passes through $v$ or not). Thus, if all $s$-$t$ paths go through $v$, you will have $m \cdot \frac{1}{m} = 1$.

  Shouldn't we just divide by 2 to compensate the fact that s and t will appear twice in different orders?

Indirectly, you're right. This formula measures the percentage of the shortest $s$-$t$ paths that pass through node $v$. In fact, a simple optimization of this algorithm for undirected graphs is to consider only $s$-$t$ paths where $s < t$. However, you can't divide it by $2$.

Curiosity: The only graph topology who has a node with betweenness centrality equal to $1$ is a star graph, like the examples shown in the figure below.


How to calculate information gain in ID3?

It's important to use the current partition.  See, e.g., the pseudocode in Wikipedia: https://en.wikipedia.org/wiki/ID3_algorithm#Pseudocode

Typically, this is implemented as a recursive algorithm.  When you recurse, you don't recurse on the entire training set; you  recurse on the subset of examples that reach the tree node you're trying to build.


When does strong duality fail in linear programming?

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.


Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm

Absolutely they can. The approximation algorithms give a formal guarantee that the solution won't be too bad and they quantify what this means whereas with a metaheuristic such as GA all bets are off. Really, the only guarantee you have with GA is that the solution is valid, but that's it.
Your best bet is to just implement the GA and give it a try. Much will depend on the details and choices you make inside the method as well as on your instances and their structure.


Theoretical worst case running time of finding a path through a maze?

If you are only interested by the worst-case scenario, you need to consider an algorithm always picking the worst possible move at any point in time. The answer is intrinsic to both the method used to find the path through the maze and the maze topology. In fact, two randomly generated mazes might be very different from each other, one could have a path from start to end with no dead end while the other might have a lot of path intersection and dead ends. In the latter, a naive algorithm might perform worse if hitting a dead end mean searching backward to the last intersection before to attempt another path. Again, the answer is intrinsic to the algorithm used to traverse the maze and the maze topology.


What's the time complexity bound for the Knapsack with real weights?

If you have n random real numbers, then you have 2^n possible real sums. If your knapsack has size S, you would expect 2k different sums in an interval $S-k\cdot 2^{-n}, S+k\cdot 2^{-n}]$, in other words calculating sums with a precision of $k\cdot 2^{-n}$ isn't enough to give the optimal sum.

With random integers, you can find an optimal sum because of the $2^n$ possible sums, there will be gazillions getting the same result. You wouldn't be able to list all choices that fill the knapsack exactly because there are to many of them, but you can find one.

You can most likely solve the problem "find items that fit in the knapsack, and have a total size at most eps less than the optimal size".


If you bring the functional dependencies of R in a canonical form, you can have only dependencies in which the right part is constituted only by a single attribute, which is prime, so we are sure that the relation is in 3NF. More, we can divide those dependencies into three sets:

The dependencies where the LHS is a single attribute candidate key;
Those where the LHS is the (only) compound candidate key;
Those where the LHS is a strict subset of the compound candidate key.

The first two kinds of dependencies are compatible with the BCNF, while the third one is not.

It is easy to show that the last set is empty. In fact, if there were a dependency X -> A, with X a strict subset of the compound candidate key, since A is a candidate key, that is determines all the other attributes, then also X determines all the other attributes, and so it is a candidate key. But this is a contradiction with the hypothesis, so no dependency X -> A where is X is not a superkey can exists, and the BCNF is surely satisfied.


Is there a limit to data compression without mentioning Kolmogorov complexity?

For any fixed piece of data, you can create an encoding where that specific piece of data is encoded by 1 (or possibly zero) bits. So yes you can most definitely compress things down to 1 bit. This is, of course, silly. We want to know how the compression algorithm behaves on multiple pieces of data because we want to use the same algorithm (or the same shared piece of data) multiple times.

Any compression algorithm must be bigger on some inputs than the original data. In fact, if you consider every possible input there is no net compression but there might be a net increase in size. So if we look at everything compression isn't even possible. The trick is that some data is more probable than other data and we can design algorithms that are smaller in the probable case. So each individual algorithm only really has a "compression ratio" if you can give a probability distribution over the inputs, then you can say what the expected output size is or what the expected compression ratio is. If your probability distribution has maximum entropy you'll see an expected compression ratio of at least 1. Importantly the entropy of this distribution tells us how much we can compress this sort of data. You don't get to just throw it out; it always applies.

Shannon's source coding theorem tells us what the theoretical limits are for compression algorithms not just compression algorithms on streams of data of a particular sort. Say you have some data with some distribution then you can compute how "good" this compression algorithm is by sampling data and seeing what the compression ratio is on average. Well, this is the same thing as compressing one giant file that meets Shannon's source coding theorem's requirements! So the entropy of the data still tells us how much we can compress it on average.

If your data is such that it's the concatenation of a fixed number of independent fixed size samples then Huffman encoding is optimal no matter what distribution the fixed size samples come from. 1) these properties seldom hold in practice and 2) when they do the optimality will only kick in for very large data. For instance, say you sample a bunch of IEEE double precision floating point numbers from an approximation of a normal distribution. Huffman encoding is technically optimal in this case but you're unlikely to see the same data more than once unless your data set is huge. I think other compression algorithms are known to be optimal for different groups of distributions over data but you'll have to do some digging to find them; I am not aware of any others off the top of my head. So as long as your data has a certain known distribution that fits one of the cases we know the optimal algorithm for AND your data is sufficiently large (or the entropy of your distribution sufficiently low) so as to have this result even be meaningful.

Generally, we don't even know what the distribution of the data is! We can make statistical inferences based on the data we have but properly fitting a probability distribution is a hard problem. Without specifying a probability distribution we don't have a sensible way to specify how good a compression algorithm is. The quality of practical compression algorithms is basically just due to algorithm designers being good at guessing what sorts of distributions your data might be sampled from and also being good at fitting which specific distribution it was sampled from in cases where that makes sense. For instance, the gzip algorithm effectively wagers that your data will have repeated values in it (especially after some transformations are performed on it). This is clearly just a guess the designers made but it happens to be a damned good guess in practice. If you assume that your data is a stream of independently sampled symbols from the same distribution then you can fit the distribution and construct a Huffman encoding for the data; this has a lot of flaws in practice but it's a lot better than nothing in practice as well. There is no reason in general that that has to be true.

So is there a limit? Well given the only consistent notion of a "compression ratio" that I know of the answer is given by Shannon's source coding theorem.


Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime.

Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose is $2N$.

Now consider the set of points $\{(i,i^2\ mod\ n)\ |\ 0\leq i \leq n-1 \}$.

For any set of 3 points to be collinear (Lets call them $(x_1,y_1),(x_2,y_2),(x_3,y_3) , x_1 < x_2 < x_3$ ) we must have $\frac{y_3 - y_2}{x_3 - x_2} = \frac{y_2 - y_1}{x_2 - x_1}$ , putting in $y_i = x_i^2\ mod\ n$ , we obtain $x_3 + x_2 \equiv x_2 + x_1 \mod n$ and this is only possible when $x_1 = x_3$.

Hence we have a set of $N$ points where no 3 points are collinear and it is the best we can obtain upto a constant factor.

Since this is a deterministic construction , to get a random family of points , instead of choosing $i^2$ , we can take any random quadratic polynomial $p$ and take the set of points $\{(i , p(i)) \ mod\ n \ |\ 0 \leq i \leq n-1 \}$.


Efficiently enumerating all paths from i to j of given length in a graph

It's not possible to solve this problem "efficiently". There can be exponentially many paths of a given length, so enumerating all of them is not feasible in large graphs.

Your dynamic programming approach is a pretty good one, though you might be able to improve it by not storing the paths explicitly but instead storing the paths as linked lists or using pointers, so that you only use $O(1)$ storage per path, letting paths share their common suffixes (if you do not do this already).


Turing machine with a countably infinite alphabet

Your model accepts all possible languages over the countably infinite alphabet.

The first step is to convert the input word to a single symbol, in some one-to-one fashion. We can do that since $\bigcup_{n=0}^\infty \aleph_0^n = \aleph_0$. You can then encode your language in the transition function.

More generally, to get a non-trivial model you need to ensure that the description length of the machine is smaller in cardinality than the number of words over the alphabet.


Equivalence of independent set and set packing

The exact meaning of "equivalent" isn't obvious but you have shown something deeper than the normal equivalence under reductions considered for NP-complete problems.

You've demonstrated what's known as a parsimonious reduction between the two problems.  Ordinarily, reductions between NP-complete problems are many-one reductions: they only have the property that problem A has a solution if, and only if, problem B has a solution. For example, when you reduce 3SAT to 3-Colourability, you produce a graph $G$ that is 3-colourable if, and only if, the original formula $\varphi$ is satisfiable. However, if $\varphi$ has $N$ variables, the number of satisfying assignments could be anything between zero and $2^N$, inclusive, whereas the number of 3-colourings of any graph is a multiple of six because of permutations of the set of colours.

The point about parsimonious reductions is that they're one-to-one. Your reduction sets up a bijection between solutions of the independent set problem and solutions of the corresponding set packing problem. Parsimonious reductions are useful because they preserve optimization and (approximate) counting versions of the problem. So your reduction also shows that the problem of finding the biggest independent set is as hard as finding the set packing using the most sets and that the problem of counting all the independent sets is as hard as to counting all the set packings.

There is a wider class of reductions that also preserve counting and approximate counting. These are the approximation-preserving reductions of Dyer et al. [1]. These are oracle reductions and relax the one-to-one requirement of parsimonious reductions to what is, essentially, "If you know (an approximation of) one, you can easily compute (an approximation of) the other." In particular, AP reductions can easily deal with the factor of $q!$ that's inherent in any reduction to the $q$-colouring problem.  As the name suggests, AP reductions preserve approximability, in the sense that, if there's an AP-reduction from A to B and there's an FPRAS for B, then there's an FPRAS for A, too.

[1] Dyer, Goldberg, Greenhill, Jerrum. The relative complexity of approximate counting problems. Algorithmica 38(3):471–500, 2003. DOI; free PDF


I'm assuming that items are always traded 1-for-1.

  How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?"

If you are only looking for one long path, then you are looking for a Hamiltonian circuit if one exists, so the decision version of the problem is NP-complete.  If you are open to having multiple disjoint cycles of exchange and just looking for as many items as possible involved in the exchange, then it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature, and it is solvable in polynomial time.

P. Biro, D. F. Manlove, and R. Rizzi. Maximum weight cycle packing in
directed graphs, with application to kidney exchange programs. Discrete
Mathematics, Algorithms and Applications, 1(04):499–517, 2009.


One of the popular models is the Bag of Words model

Also, you can model the words as integers.. they have 'relative distance metrics' for that, and capture the very essence of the classification process. However a downside to that is the preprocessing step is expensive and also you need to have some domain knowledge.

A pretty famous distance metric is the Levenshtein distance which is based on the the number of single character edits. eg. that is, $d(walk,talk)<d(walk,plod)$.

The metrics depend upon the context of the classification process.. for example your distance metric for classifying rhyming words will be different from those designed to classify synonyms/words conveying similar meanings.For a list of string metrics, take a look at this wikipedia article.

Also, you can take a look at this review paper.


How can I do a subtraction with a two tape Turing machine

Copy the second number (from the second tape) to the first tape, and then use the already existing TM that subtracts the numbers


Can a 1-tape turing machine simulate a stack?

Machines that have only a stack are called pushdown automata. They are less powerful than Turing machine, so yes: TMs can simulate stacks.

Turing machines are a fairly simplistic model of computation, which can make programming in them hard. Try to start with simple things; for instance, implement a counter. If you feel ambitious, try implementing the basic building blocks of (Turing-complete) imperative programming as Turing machines. This should convince you, then, that TMs are as powerful as any other¹ model.

As for your question, you don't need pointers for a stack. TM tapes have a direction, and you can easily label cells by introducing special alphabet symbols; the TM can then move over the tape and look for these labels. It's all a matter of encoding.

Ignoring hyper-computation.


Difference between Sequential ,Direct and Random acess with their acess time

Sometimes, depending on the sources,direct access and random access are used to express the same memory access mode and therefore do not present any substantial difference in the speed of data access.

More in detail, the differences between the two modes can be sought in their implementation:
Random Access can be realized directly via RAM memory wiring, while direct access can use secondary storage; in this case is obvious that random access is faster than direct access.


Is there a name for the problem of turning a bipartite graph into two graphs?

You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will contain at least two connected components, corresponding to the two bipartitions.


How create DFA with multiple finished states for lexers?

As Rick Decker rightly noted, real-world lexical analysers produce a DFA with multiple final states.

Lexical analysers created via Lex-like generators differ from theoretical DFAs in several respects, and this is only one of them. Another obvious difference is that they don't stop at the end of the input string.

Instead, lexical analyser generators generally work as if they ran all DFAs corresponding to the lexer rules in parallel (in practice using a DFA with multiple end states), and applying the following rules:

The DFA that "wins" is the one that proceeded the furthest (often called the "maximal munch" rule).
If more than one DFA would accept that maximal-length input, the one that occurred first in the specification file "wins" (the disambiguation rule).

The disambiguation rule is used, for example, to distinguish keywords (e.g. if, else, while) from identifiers. Ignoring underscores for the moment, an identifier is (typically) any lexeme that starts with an alphabetic character followed zero or more alphanumeric characters, but isn't a keyword. You could create a regular expression which matches this, but it's much easier to specify keywords before identifiers and let the lexical analyser generator do the disambiguation for you.


Equivalence between a TM and a changing TM

It is clear that a TM can simulate a changing TM, so you only need to show the converse. Let me allow to use the "stay" movement in the changing Turing machine. It is easy (but tedious) to remove this assumption and keeping it makes the following argument more intuitive.

You can do the following: start from a TM $T$ with set of states $Q$ and tape alphabet $\Gamma$. Then, create a changing TM $T'$ with states $Q' = Q \cup (Q \times \Gamma \times \{L,R\})$ and tape alphabet $\Gamma' = \Gamma \cup \{ \gamma \}$.

Intuitively, state $q \in Q$ of $T'$ represents state $q$ of $T$, while state $(q, a, m) \in Q \times \Gamma \times \{L,R\}$ of $T'$ represents the fact that we plan to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$ (notice that this a state, not a transition, we are just keeping track of our future plans).

Replace each transition $(q, a) \to (q', b, m)$ of $T$ with the following transitions in $T'$:

$(q, a) \to ( (q', b, m), \gamma, S)$, and
$( (q', b, m), \gamma) \to (q',b, m)$

Intuitively, this replaces the writing of a symbol $b$ on the tape with two operations: 1) we write $\gamma$ without moving the head, and 2) we overwrite $\gamma$ with $b$, move the head in the intended direction $m$, and transition to the corresponding state $q'$ of $T$.

This is a tedious simulaton of a TM with a changing TM if the "stay movement" is not allowed.
Define $\Gamma' = \Gamma \cup \{\gamma_1, \gamma_2\}$ and $Q'= Q \cup (Q \times \Gamma \times \{L,R\} \times \Gamma')$.
Replace each transition $(q, a) \to (q', b, m)$ of $T$ with the following transitions in $T'$:

$(q, a) \to ( (q', b, m, \gamma_1), \gamma_1, R)$,
$( (q', b, m, \gamma_1), x) \to ( (q', b, m, x), \gamma_2, L)$ $\quad \forall x \in \Gamma$,
$( (q', b, m, x), \gamma_1) \to ( (q', b, m, x), \gamma_2, R)$ $\quad \forall x \in \Gamma$,
$ ( (q', b, m, x), \gamma_2) \to ( (q', b, m, \gamma_1), x, L)$ $\quad \forall x \in \Gamma$,
$( (q', b, m, \gamma_1), \gamma_2) \to (q', b, m)$

What we are doing is the following: 1) We write $\gamma_1$ and move right,   2) we store the current tape symbol $x$, replace it with $\gamma_2$, and move left, 3) we replace the tape symbol $\gamma_1$ with $\gamma_2$ and move right, 4) we write back the stored type symbol $x$ in place of $\gamma_2$ and move left, 5) we finally write $b$, move according to $m$, and transition to state $q'$.


Are tamper attacks considered side-channel?

A tampering attack can be considered as an active side-channel attack, which is one that involves (physically) interacting with the device under attack. In contrast, passive attacks involve only measurement and observation.

Generally, however, I think tampering attacks are considered as a separate class as the countermeasures against them are quite different than for other side-channel attacks.


Show that Knapsack-like problem on directed graph is NP-hard

$x_i \leq x_j \forall (i,j) \in A$ is a linear constraint that represents your requirement (if $x_i=1$ it would push $x_j$ to take value $1$ as well). You get a constrained knapsack problem. You can easily reduce a knapsack to it by considering a graph that simply has no arrows.


Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part

The special case of your problem in which the points are in $\{-1,1\}^n$ and the values are $\pm 1$ is known as Maximum Agreement for Halfspaces. When talking about approximation, we want a positive objective function, and in this case it is convenient to ask for the number of correctly classified points. A point is correctly classified if either its value is $+1$ and it belongs to $S$, or its value is $-1$ and it belongs to $S^c$.

A trivial $1/2$-approximation algorithm just picks any halfspace and chooses either the halfspace or its complement. One of these satisfies at least half the constraints. Guruswami and Raghavendra showed that no better polynomial time approximation algorithm exists unless $\mathsf{P}=\mathsf{NP}$.

In practice you might be able to use some heuristics, but these of course don't provide any guarantees in the worst case.


Euler graph k-coloring (np-completeness proof)

A major part of proving that a problem is NP-hard by reduction is proving that the reduction works. It's not enough to find some procedure which takes an instance of problem A and transforms it to an instance of problem B; you have to figure out the connection betweens solutions of the one instances and solutions of the other.

In your case, one idea that does work pairs up odd-degree vertices and connects every pair to a new vertex. Now all the degrees are even, and the new graph is $k$-colorable iff the old one is $k$-colorable, assuming $k > 2$. I'll let you figure out why this works.

While this idea is similar to your own idea of connected pairs of odd-degree vertices, your idea is problematic since it is not clear that if the original graph is $k$-colorable then so is the new graph. Indeed, if two vertices that you connected were colored using the same color then you cannot use the same coloring for the new graph. The idea described in the previous paragraph is very similar but doesn't suffer from this shortcoming.


Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?

Expanding on Reza's answer, every recurrence of the form $T(n) = T(n-1) + T(n-2)$, with arbitrary initial values, has a solution of the form
$$ T(n) = A \left( \frac{1+\sqrt{5}}{2} \right)^n + B \left( \frac{1-\sqrt{5}}{2} \right)^n, $$
for some $A,B$. Note that $|(1-\sqrt{5})/2| < 1$, and so the second term tends to zero as $n \longrightarrow \infty$. Assuming that $T(n)$ tends to infinity, $A > 0$ and so
$$ T(n) = \Theta\left( \left( \frac{1+\sqrt{5}}{2} \right)^n \right). $$
Now $(1+\sqrt{5})/2 > \sqrt{2}$, and so $T(n) = \Omega(2^{n/2})$.

Edit: This part is also covered in this answer (see under "A Shortcut").

More generally, for a recurrence of the form $T(n) = \sum_{i=1}^k a_i T(n-i)$, let
$$ P(t) = t^n - \sum_{i=1}^k a_i t^{n-i}. $$
If $P$ has no repeated roots and the (possibly complex) roots are $\lambda_1,\ldots,\lambda_k$, then the solution is always of the form
$$ T(n) = \sum_{i=1}^k A_i \lambda_i^n. $$
If it does have repeated roots, say the roots are $\lambda_1,\ldots,\lambda_l$ with multiplicities $m_1,\ldots,m_l$, then the solution is always of the form
$$ T(n) = \sum_{i=1}^l A_i(n) \lambda_i^n, $$
where $A_i$ is a (possibly complex) polynomial of degree smaller than $m_i$.

In our case, $P(t) = t^2-t-1$ has no repeated roots, and the two roots are $(1\pm\sqrt{5})/2$.

The $A_i$s depend on the initial values, and can be found by solving linear equations. For example, suppose we are given $T(0)$ and $T(1)$ for our recurrence. Then we can find $A,B$ by solving the system
$$
\begin{align*}
T(0) &= A + B, \\
T(1) &= \frac{1+\sqrt{5}}{2} A + \frac{1-\sqrt{5}}{2} B.
\end{align*}
$$
This works even in the case of repeated roots, and $k$ initial values always suffice. Assuming $a_k \neq 0$, $k$ initial values are also necessary.


What does it mean that HDLs "explicitly include the notion of time"?

Programming languages usually don't have a notion of time.  They describe how things are sequenced, but usually they don't go further.  When they do, that's relegated to the library part of the language, and it is to handle time computation or to handle real time measurement and delay.

HDL are used for two purposes: synthesis and simulation.  For the first purpose, there is no more use of time than for a programming language.  For the second purpose, time is inherently part of what is to be simulated.  You need to know after which delay $Q$ will change after a change of $R$, and after which delay $\bar Q$ will do the same.  The time here is thus not the real time, but a simulated one, which has no easy relationship with the real time during which the simulation will occurs.

Your circuit will be described in a VHDL-like syntax:

Q <= not (R or QBar) delay 1ns;
QBar <= not (S or Q) delay 1ns;

You can also write an oscillator, with no stable state:

Clock <= not Clock delay 5ns;

Time is thus present in the syntax of the language, and in its semantic as well (the language clearly states that $\bar Q$ will change 2ns of simulated time after $R$ does).


There are only three high level abstractions in the network stack.

Link Layer: Knows how to transfer data (physically*) across one hop. This layer with deals encoding and framing bits, controlling channel access, detecting and recovering from collisions in the transfer medium. Eg: Ethernet, WiFi etc.

Network Layer: Does forwarding and routing (note: they are different procedures). Knows how to forward a packet to the destination. Has a table of IP-->link mapping. Let's assume your router/switch has three links, it decides (and only knows) which link to take to get closer to the "destination IP". Delegates the physical mechanism of transferring bits on that link (which may be Ethernet or WiFi or whatever) to the link layer. Once your router finds that the "destination IP" matches "your IP" it makes an up-call to the End to End layer, i.e, no more links have to be traversed. Eg: Internet Protocol IP. Just to be concrete, a router has a forwarding table which has the following form,

Forwarding Table
IP address   Link to take
"Your IP"    E2E layer
127.35.*.*   link 2
10.*.*.*     link 3
173.*.*.*    link 1

These individual links may be Ethernet or WiFi or DSL etc. Note: an intermediate gateway/switch may not have E2E layer implemented.

Packets in the network layer may get dropped due to congestion, link failures or may not reach destination due to a wrong route.

The links layer and the network layer taken together is just a "BEST EFFORT" dumb network, that doesn't guarantee: ordered delivery, delay limits, congestion control or any form of reliability that a practical application might require. It tries its best to take the packet through but it is not assured. It does not guarantee end to end delivery.

To answer your question, packet routing is in itself a hard problem which requires implementing an abstraction called the network layer for this purpose. Look for "Path vector routing", "BGP" to understand how network layer prepares these forwarding tables.

End to End Layer: This builds on top of the network layer, requests re-sending of lost messages, acknowledgments, arranges out of order segments, manages resources like timer etc. It works to ensure, whatever the sender sent has arrived intact. Eg, TCP, UDP

*Link layer doesn't always mean physical transmission, for details, read about recursive network stacks like Gnutella


Why is the Nintendo Entertainment System (NES) referred to as an 8-bit system, rather than a 1-byte system?

"Back in the day" computers were defined more by their word size, for example the PDP-8 had 12-bit words composed of two 6-bit "bytes". A "nibble" was half a byte, or 3 bits in this case (and here the op codes were 3 bits).

It is only in recent decades that 8-bit bytes became so prevalent as to make them the default.

Calling the NES 8-bit is less ambiguous than calling it 1 byte, keeping in mind we're talking about a system that came out in 1983.


Prove correctness of iterative LCM algorithm

Assume j, k > 0.

You have your loop invariant. Every iteration, one of c or d gets larger. They cannot forever stay ≤ LCM (i, j), therefore the loop must finish.

Because c and d are multiples of i, j, they cannot change directly from being < LCM (i, j) to > LCM (i, j), instead there must be a step for each of c and d where it is equal.

If both are = LCM (i, j) then c = d and the algorithm exits. If one is = LCM (i, j) then the other one is smaller and gets increased.


What happens when an alphabet is not listed in a Turing Machine?

The behavior of the Turing machine is not defined in this case.  So, the mathematical formalism does not predict or require anything about how the machine will behave in such a circumstance.

Since a Turing machine is only a mathematical construct anyway, it's perfectly reasonable to impose such a limitation and only think about what happens when you run it on a tape that follows all the rules.

Put another way: If it's possible for the symbol b to occur in the tape, then it's your job to make sure that b is included in the alphabet.


RE Construction: Strings of even length in alphabet {a,b,c} that contain exactly one a

The idea is that if a string contains one $a$, then it can be written as $xay$, where $x,y \in (b+c)^*$. Furthermore, $xay$ has even length if either $x$ has even length and $y$ has odd length, or vice versa. Using this, it is straightforward to come up with a regular expression.


How to test for overflow when multiplying floats

I want to further emphasize and underscore gnasher729's comment which is completely correct. NaN and Infinity were added exactly so you wouldn't need to do such checks all the time. That is, they were added to you wouldn't need to do exactly the thing you are suggesting doing. One of the consequences is that it often is the right thing to do to just blindly continue a calculation, checking whether it has overflowed or produced NaN only when you need to make a decision based on the result.

There are at least a few reasons it is this way. First, as you are starting to see, it can complicate your code quite a bit to attempt to preemptively detect potential errors. Second, such checking code tends to significantly slow down computation1. This is especially bad as the vast majority of the time you will not overflow, and so these checks are just wastes of time. Adding early abort code is then optimizing for a very rare case at the significant expense of the vastly more common case. Third, many aspects of IEEE754 have been carefully designed to behave sensibly even in "error" cases. Often this allows correct results despite overflows in intermediate calculations and allows even more error checking code to be eliminated as well as expanding the domain of operations. For example, dividing a finite number by Infinity doesn't cause an error but instead produces a (signed) 0, which is likely the desired result.

So, to reiterate gnasher729's comment, the way you test for overflow when multiplying IEEE754 floating point numbers is by multiplying them and then checking whether they've overflowed. And you shouldn't even do that that often. You should only check for overflow when you need to make a code branch based on the decision2, and otherwise you should just let the error values propagate.

1 This especially true for SIMD architectures such as GPUs. GPUs are much happier doing the same thing to a bunch of data in parallel than doing different things in data dependent ways.

2 These code branches may be hidden, e.g. while calling a print routine may not require a branch in your code, there is one in the print routine to know whether to display "Infinity" or not. Therefore, you should check for overflow before printing assuming you want a behavior other than printing "Infinity", et cetera.


Finding minimal and complete test sets for circuits

Yes.  One can construct a Majella sequence of length $n \cdot 2^n + 1$, recursively.  It's easy to see you can't do any better than this, so this is optimal.

Definition. I'll say that a sequence $x_0,x_1,\dots,x_m$ of $n$-bit values is a $n$-bit Majella sequence if $x_0=x_m$, and for each $y \in \{0,1\}^n$ and each value $e \in \{0,1\}^n$ with a single bit set, the pair $y,y\oplus e$ appears (consecutively) somewhere in the sequence.

Recursive construction. Let $w_0,w_1,\dots,w_m$ be a $n-1$-bit Majella sequence (for $n-1$-bit values).  Consider the following sequence:

$$0w_0, 0w_1,\dots, 0w_{m-1}, 0w_m, 1w_m, 1w_{m-1}, \dots, 1w_1, 1w_0, 0w_0,$$

where $0w$ represents the concatenation of $0$ and $w$.  This sequence is not yet a Majella sequence, but we can modify it to be one.  In particular, for each value $w \in \{0,1\}^{n-1} \setminus \{w_0\}$, replace the first occurrence of $0w$ in the sequence with $0w,1w,0w$ (increasing the length of the sequence by 2).

After this modification, the result is a $n$-bit Majella sequence.

This construction is inspired by the standard recursive construction of a Gray code, but tweaked slightly to satisfy your particular requirements.

Length of the recursive construction.  Let $L(n)$ be the length of the resulting sequence (i.e., the value of $m+1$).  It satisfies the recurrence relation

$$L(n) = 2L(n-1) + 2^n - 1$$

with $L(1) = 3$.  This solves to

$$L(n) = n \cdot 2^n + 1.$$

Algorithms. I don't know if there are any efficient, low-space algorithms for enumerating through such a sequence, like there are for Gray codes.


Are poly-reductions to PSPACE problems for following problems are known?

The reduction you refer to is called Turing reduction. Given $A,B\subseteq \Sigma^*$, we say $A\le_T B$ if there exists a polynomial time Turing machine which decides $A$, given oracle access to $B$. You might call this practical, and in some sense this is the natural way to say $A$ is no harder than $B$ (give me a program for $B$, and i'll write an efficient program for $A$ which uses the previous program as a subroutine).

The standard notion of reduction in complexity theory is Karp reduction (also called many to one reduction). We say $A$ is reducible to $B$ in this sense, if there exists a polynomial time computable function $f$ such that $x\in A \iff f(x)\in B$. Note that this is a weaker condition, i.e. if $A$ is Karp reducible to $B$, it is also Turing reducible to $B$ (apply $f$ on the input, and query the oracle on the result).

Since TQBF is PSPACE complete, then by definition, every language in PSAPCE has a Karp reduction to it (and thus also a Turing reduction). Not only that we know there exists such a reduction, but given a PSPACE machine for some language $L$, then we know how to construct a reduction from $L$ to TQBF (this is done in the proof for the PSPACE completeness of TQBF).

The decision versions of $\#P$ problems are in PSPACE, since you can go over all possible witnesses and count how many are accepting (the only thing you need to store is the counter). This means that all such problems are reducible to TQBF. This is a very precise statement, but intuitively, it says exactly what you want it to. If you can efficiently decide TQBF, then you can efficiently decide all languages in PSPACE, which includes the decision versions of #SAT and permanent.


Longest path in a graph with special property

As Raphael pointed out, this problem is also NP-complete. There is an easy reduction from longest path problem to this problem. Just take the graph of longest path problem and label all of the edges type-0. There won't be any type-1 edge. This labeled graph will have a longest path of length $k$ iff original graph has a longest path of length $k$.

This proves the NP-hardness of the problem.

It is easy to see that the problem is in NP, the NDTM machine for the problem will be similar to the longest path problem. Both this add to make the problem NP-complete.

But if you are happy with any kind of approximation, then you can refer Approximation to longest path and modify the algorithm to suit your purpose. However be prepared that the modification may not be trivial.


What these simple rules of logical implications mean

Contradictions can't happen. If $x$ implies a contradiction, then $x$ can't be true.
Either $y$ is true, or it isn't.  That's still the case even if I first tell you that $x$ is true.


I would suggest you use linear regression, or simply grid search (you can search over all possible number of points for each category, from 1..20; that's only $2^{13}$ possibilities, all of which can be easily tested one-by-one).

Make sure to use cross-validation: split the data set into training and test, and use the training data to derive the best parameters, then evaluate it on the test part.


A closure is a piece of code together with an environments providing a
binding for its identifiers. In the case of a method, the identifiers
(at least some of them) are bound to data in specific instances of the
class, not just to the class itself.

The method provides only the code, of the function (in your first
quote), while the environment is provided by an instance of the class
(an object in your second quote). So it is the method together with
the object (class instance) that forms a closure.

Indeed, the class instance may be seen as the closure, since it
naturally carries the methods with itself formally, considering that
it is a closure for a tuple of functions, rather than a single one.
That is actually necessary, since the code of each function may refer
to the other function, meaning implicitly for the same environment.

Some of the first implementations of object orientation were actually
produced that way with higher order language. The creation of an
instance of a class was done by calling a creation function $Foo$ with
proper parameters. This function would return an instance represented
by a tuple of functions closed over the local environment of $Foo$, each
function being one of the methods for the class. Actuallly these method
function were declared inside $Foo$ so as to see all the local
identifiers in $Foo$, which are the data for this instance being created, and otherwise invisible outside $Foo$.

Each new call of $Foo$ would create a new call instance, i.e. a new
environments on which execute the methods.

But the syntactic sugar may vary significantly.

Historically, afaik, the name closure was used for a function value $g$
returned by a call to a function $F$, though it is created (declared,
to say it approximately) inside $F$ and can thus see and use any
entity $x$ declared in $F$. Normally, what is declared in $F$ ceases
to exist, to be accessible, as soon as $F$ is exited.  But when $F$
returns such a function valued result $g$, the system has to preserve
any identifier $g$ may be using since $g$, as a function value,
survives the termination of the call to $F$. All identifiers used by
$g$ are preserved in an environment and $g$ together with this
environment is called a closure.

Note that $g$ is a function value, not anything being called. The
environment of this closure is preserved as long as the function is
callable. Several function can be closed at the same time on the same environment.


DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

Simple answer No, we cannot sort start time in ascending order to get a reasonable dynamic programming algorithm.
A counterexample

As illustrated above, we are given four jobs aligned in order of ascending start time, each labeled with its wight. Though some computation, we have $p_4=3$ and $OPT(4)=1+OPT(3)$. By definition,  $OPT(3)$ equals to the optimal value in $\{1,2,3\}$. By selecting job $1$ and job $2$, $OPT(3)$ is maximized and is equal to $3$. Then the optimum subset of the four jobs would be $\{1,2,4\}$, which is not a compatible set.
Necessity for sorting by finish time in ascending order: By sorting finishing time in ascending order, we ensure that for job $i$, $\{1,2,\dots, p_i\}$ is compatible with $i$ since they all finish before the start of $i$. But if we sort start time in ascending order instead, we cannot ensure that. As shown in above counterexample, $p_{4} = 3$, thus $\{1,2,\dots, p_4\}=\{1,2,3\}$ is not compatible with $4$. Suppose that $i$ is in the optimal solution $\mathcal{O}_i$ for $\{1,2,\dots, i\}$, then the optimal solution $\mathcal{O}_{p_i}$ for $\{1,2,\dots, p_i\}$ is also included in $\mathcal{O}_i$. specifically, we have $\mathcal{O}_{i} = \mathcal{O}_{p_i}\cup \{i\}$. Since we couldn't ensure that $i$ and $\mathcal{O}_{p_i}$ are compatible, we may get an invalid solution, which also can be seen from above counterexample.


What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)

It will be convenient to distribute the concatenation to get the equivalent RE
$$0(1111)^\ast + 0(00)^\ast + 0001(1111)^\ast + 0001(00)^\ast.$$
Now note that any such string can be writen as $s = s_i(s_r)^\ast$ where $s_i$ denotes the initial part (i.e. $0$ or $0001$) and $s_r$ denotes the repeated part (i.e. $1111$ or $00$).
We see that $s$ can be pumped if and only if $s_r$ is non-empty and hence, the longest non-pumpable string is $0001$ and the answer is $4$.
Indeed any string of length $5$ or more must have a repeatable part as defined above.
The two shortest strings in the language are $0$ and $000$. We see that $0$ clearly cannot be pumped (as $\varepsilon$ is not in the language) but $000$ can be pumped by repeating the last two zeroes arbitrarily often (and importantly we can also delete them to get $0$).
Hence the answer is $3$.


How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits?

Your argument appears to be perfectly valid (Fisher-Yates does indeed require $\log (n!)$ bits of randomness), the discrepancy comes in by making different assumptions about the complexity of the random number generation.

You're assuming generating a random number between $0$ and $n$ takes $O(\log n)$.

But, when saying that the Fisher-Yates shuffle is $O(n)$, one assumes generating a random number takes $O(1)$.

An integer index (which is used in the Fisher-Yates shuffle) is generally considered $O(1)$ space (even though it's technically $O(\log n)$) because you can index way more data with a simple 64-bit integer than can currently reasonably fit into the memory of any computer most of us have access to $^{1}$. And the space complexity per number is same as the complexity for the number of random bits that must be generated for that number.

1: To go beyond the number of elements a 64-bit integer can index, we would require $2^{64}$ = $18446744073709551616$ elements, and, assuming 1 bit (which is obviously very small) per element, this requires 2 exabytes.


An article that claims to introduce it: IELR(1): Practical LR(1) Parser Tables for
Non-LR(1) Grammars with Conflict Resolution (via archive.org) by Joel E. Denny and Brian A. Malloy, Clemson University, is freely available from Malloy's site.

What they are worth is something I can't answer. (Personally I don't understand the need for such crippled CFG parsing - why limit your expressive power when you can just use GLR?  What does make sense to me is something like TAG or PEG (they seem natural and add expressive power) or tree grammars (for languages such as XML, in which recognizing parse trees is unproblematic by design.)


How do I interpret this formal languages definition?

It's the same $w$. You can think of this language in a ``procedural'' way: it is  formed by taking every word $w\in \{a,b\}^+$, and for each such word, adding to the language the word $wcw$.

Typically, sets (and languages in particular) are described as $\{x: \text{condition on } x\}$, which is pretty clear. However, it is sometimes more convenient to ``push'' the condition into the description of an element.

That is, you could describe the same language as:
$$\{x\in \Sigma^*:\ \exists w\in \{a,b\}^+\wedge x=wcw\}$$
Or even worse:
$$\{\sigma_1\cdots \sigma_n: \exists k\ge 1,\ n=2k+1\wedge \sigma_1\cdots\sigma_k=\sigma_{k+2}\cdots\sigma_{2k+1}\wedge \sigma_{k+1}=c\wedge \forall 1\le i\le k,\ \sigma_i\in \{a,b\}\}$$

But obviously this is much more cumbersome than the original description.


In instruction pipelining, can we forward an operand more than one clock cycle?

Paul's Comment is correct:
"Yes. This is one way of avoiding a structural hazard on the write ports of the register file with operations of several different latencies (i.e., having a single writeback stage for all operations). However, adding forwarding paths increases wiring and operand selection complexity."

In general, the amount of hazards and amount of opportunities for forwarding increase with pipeline depth. So a 10-stage pipeline will yield more hazards and more theoretical opportunities for forwarding than a 5-stage pipeline. However, the control logic to detect and schedule all the forwarding increases significantly (likely with a polynomial factor).

The distance of stages you can forward an operand is justified by the minimum of the two following things:

The number of forward stages until the operand enters the register file.
The number of reverse stages where the operand could logically be used.

In other words, it makes no sense to attempt to perform 5 cycles of forwarding on a 5-stage pipeline since all operands would have been in the register file anyway.


A recursive function is only bad if it ends up repeating work and in this case it does not have too. A postorder traversal of the tree is what you want to do here, and the iterative solution exists, but is considerably more difficult to implemant. A post order traversal will only visit each node once, and you will not beat that for complexity.


How does software detect if an interrupt has occurred if it cannot set it's own interrupt handlers?

The interrupt handler adds the new data to an input queue.  Typically the user level process will have a thread waiting for input to appear, or will poll periodically to see if new input is available.  If your process does neither, it would never notice the new data.


Playing video games to solve SAT instances

No. The gamer will basically have to work out the SAT problem in their head.
Think of any video game puzzle you've solved that wasn't easy. You probably solved it by working out a simpler version of the problem and then solving that. If you "complexify" SAT into a video game level, the best way to solve the video game level will be to simplify it back into SAT, then solve SAT.
Example: Perhaps your game lets you create a level where you must collect all the coins from all the rooms but you can only enter each room once. (This is a Hamiltonian Path problem, which SAT can be transformed to). When you collect all the coins, the exit door opens. You then go to the exit door and finish the level. How would you solve it?
Well, you would start by exploring the level and drawing a map. Then you might simplify the map by drawing the rooms as circles and the connections as lines. Then you have to figure out a way to get from the start to the exit while going through every room... i.e. you have to solve the Hamiltonian path yourself. But how do you solve the Hamiltonian path? Well, you might reason that if you go this way, then you can't go that way, and if you go that way, you can't go this way, .... and write down a list of rules about where you can go. Then, you have to logically deduce a path that matches all the rules. Which is SAT. You're back to where you started except with a lot of useless extra work.


Find a source-sink-path that touches a subset of edges

If the path did not have to be cycle free this would be easy: let $s$ and $t$ be the source/sink, take two copies of the graph, say $(V_1, E_1)$ and $(V_2, E_2)$, and for any marked edge $\{v_i, v_j\}$ in the original graph, add $\{v_{1i}, v_{2j}\}$ and $\{v_{2i}, v_{1j} \}$ to the new graphs (connecting them), then find a path from $s_1$ to $t_2$.

For the cycle-less case, the best I can think of is a solution using max flow: iterate over all marked edges $\{u, v\}$, add a supersource and supersink to the graph, add edges from the supersource to the original source and sink $s$ and $t$, and edges from $u$ and $v$ to the supersink. Then find two vertex disjoint paths from the supersource to the supersink (we consider two paths to be vertex disjoint if the only shared vertices are the supersource and supersink, there are at most two of these paths). If no two paths exist, you cannot use the edge $\{u, v\}$, otherwise you can reconstruct the full path using the flow you found.

Finding these vertex disjoint paths is not entirely trivial, you'll need to transform the graph a little (see e.g. here), but it will only increase the size of the graph linearly.


For how large graphs can we still check for isomorphism?

The number of non-isomorphic graphs on $n$ nodes is given by https://oeis.org/A000088. If you only care about connected graphs then it's https://oeis.org/A001349. Programs like nauty can enumerate these graphs for you. That answers your second question.

For your first question, it depends on the meaning on actually. There are algorithms which work for fairly large number of vertices, but fail (take a long time) on some bad examples that supposedly don't happen (or are rare) in practice. The worst-case asymptotic complexity of graph isomorphism is still open. The Wikipedia page has an old (2001) reference which compares real-world algorithms for graph isomorphism. Perhaps you could find a more recent one and update the page.


Difference between approximation scheme and approximation algorithm?

In theoretical computer science, an approximation algorithm is an algorithm that guarantees a certain approximation ratio $\rho$, and an approximation scheme is a (uniform) collection of algorithms that guarantees several different approximation ratios. Since the collection is uniform (all the algorithms look the same but with different parameters), you can also think of an approximation scheme as an algorithm with an auxiliary parameter $\rho$ which then guarantees an approximation ratio of $\rho$; the close $\rho$ is to $1$, the harder the algorithm would have to work, and not all $\rho$ are valid inputs. For example, usually you need $\rho \neq 1$. If the scheme works for $\rho$ arbitrarily close to $1$, and furthermore the scheme is polynomial time (for each $\rho$ separately), then it is a polynomial time approximation scheme (PTAS).


What is a monotone dataset and monotone classification?

A monotone classifier is a classifier that is a monotonic function.

One reasonable definition of monotone data set is that it is a data set that is consistent with some monotone model (i.e., where there exists a monotone classifier that gets 100% accuracy).  I don't know if this is a standard definition so hopefully any text that uses that phrase would provide a definition.

Why use a monotone classifier in the setting you mention? Perhaps we have some a priori reason for believing that, all else being equal, the higher the students rate their satisfaction, the higher the quality of the course.  That amounts to a monotonicity assumption about the underlying model that relates quality to satisfaction.  If we assume that the data was generated from a monotone model, it is reasonable to try to learn a monotone classifier.  Whether this is appropriate in any particular setting depends on whether you have a reason to think that the data does come from a monotone process/model or not.


Why closedness of complement of randomized classes imply containment of complement of contained classes?

Yes, you should follow the definitions, if $L\in \mathcal{C}\subseteq PP$, then $\overline{L}\in PP$. It immediately follows that $co-\mathcal{C}=\{L | \overline{L}\in \mathcal{C}\}\subseteq PP$.


Alternative Method for Computing Two's Complement Binary -> Decimal

No error. in fact, if you add the binary representation of (-38) and 38 as unsigned 7-bit integer without overflowing, you'll get $10000000_2$, then due to overflow the lowest 7 bits is preserved, resulting 0. This property holds for all $0<x<2^6$, ie. denoting $u(x)$ the unsigned value from 2's component representation of $x$, then $$u(-x) + x = 2^7, (x>0)$$ thus $$\begin{align}-x =& u(-x)-2^7\\=&(u(-x)-2^6)+(-2^6)\end{align}$$ ie. subtract the highest bit, and add back the minus bit. This can be extended from 7-bit to n-bit.


Implementation-level of a Turing machine that accepts a specific language

I will use two tapes with deterministic Turing Machine.

Say you have $123321233223321B$ on first tape as input, where B is blank symbol.

At first use three states counter and add some symbol to the second tape, say # every third symbol. Check whether input is divisible by 3 (otherwise reject).

After first iteration you have:
$123321233223321B$
$#####$

Here you do not reject, as it is divisible by 3.
Now move elements from first tape to second one. After this step you have:
$1233223321$
$12332$

Compare elements from second tape with first one (deleting from first one). After that step you have:
$23321$
$12332$

Place head on first tape at the beggining and head of second tape at the end. Compare char by char moving in oposite directions (erasing symbols). If anywhere during comparison there was a mismatch then reject, otherwise accept (if this is required leave something in the first tape at that point).


Numerical Boardgame -- Help with with a pruning method (alpha-beta : minimax)

I'm a bit at a loss for a decent heuristic for pruning moves at this point

You can start from the observation that for the side to move there is almost always a better alternative than doing nothing (at least in the first phase of the game, when there are many moves).

So you can try a "null" move (the side to play passes and lets the opponent get a free move): if the score of the subtree search (depth reduced by a R constant) is still high enough to cause a beta cutoff you can prune the tree.

The pseudo-code is something like:

switch_side_to_play()                                     // Null move
score = -ab_search(-beta, 1 - beta, depth - R - 1)
switch_side_to_play()

if (score >= beta )
  // return score (cutoff) or reduce the search depth

As every heuristic, it sometimes fails. This is an example from Chess but the same problem could happen in your game when there are only few moves available.

If White is to move, he will have to move Kd6, which results in stalemate, or move away from the pawn which loses it.

However if White could pass (null-move), Black would have to play Kc7 (White plays Ke7 and the pawn queens).

I'd start trying null move: if it works there is much to gain. If it doesn't work (Checkers / Othello are two well known examples), ProbCut heuristic would be a good alternative.

The general idea of ProbCut is to perform a shallow search. If the result is far outside the alpha-beta window you trust the search, otherwise you have to re-search to the full depth.

If you assume this relationship (linear model) between the value of a shallow search ($v'$) and the values of a full search ($v$):

$$v = a \cdot v' + b + \mathcal{E} $$

($\mathcal{E}$ is an error variable, normally distributed, with mean 0 and standard deviation $\sigma$)

Then the beta-cutoff condition of the alpha-beta algorithm ($v \ge \beta$) becomes:

$$ v′\ge  \frac{Φ^{−1}(p) \cdot \sigma + \beta − b}{a} $$

(same for $\alpha$, see the linked paper for further details).

The nuisance is that you have to tune many parameters, but this is a very general pruning technique.

  Move ordering is a bit difficult because I can't just choose the highest remaining cell (can I?), since there are plenty of opportunities for the opponent to right-out rush that cell as soon as it's claimed.

This is similar to captures in chess: you can take a piece but the opponent could recapture.

So a complex heuristic to evaluate the result of a sequence of captures on a square is a possibility, but also a simple heuristic like MVV-LVA (Most Valuable Victim - Least Valuable Aggressor) is very effective.

You could try highest remaining cell + sum of cells claimed by rush or highest remaining cell + sum of cells claimed by rush - (number of attacking cells) % 2.

According to this heuristic the last move has a value of 9 + (1 + 10) - 1. This is very coarse but it isn't for pruning, just for ordering.


You can find a solution with an algorithm that requires about $2^{24}$ operations and $2^{22}$ space, and requires only $N=2^{22}$ entries in each list.  (If you have more than that in each list, ignore the rest and use only the first $2^{22}$ entries.)  Here's how.

Step 1. Build a list $L$ of all of the pairs $(a,b)$ such that $a+b \equiv 0 \bmod 2^{22}$.

By the birthday paradox, we expect there will be about $N^2/2^{22} \approx 2^{22}$ such pairs $(a,b)$, since there are $N^2$ possible pairs and each pair has a $1/2^{22}$ chance of satisfying the condition.  To find them, build a sorted list of the values $a \bmod 2^{22}$, a sorted list of the values $-b \bmod 2^{22}$, and merge the sorted lists.  Or, use a hash table.

Step 2. Look for two pairs $(a_1,b_1)$ and $(a_2,b_2)$ in $L$ that have the same sum modulo $2^{64}$.

By the birthday paradox, we expect such a solution should exist with high probability, since we have about $2^{22}$ entries in $L$ (and thus about $2^{43}$ candidate solutions) and the condition holds with probability $1/2^{42}$.  (Why $1/2^{42}$?  Well, their sum is guaranteed to match in the low 22 bits, by the way we constructed $L$.  So, we just need their high 42 bits to match too.)


Decoding a binary linear code given its generator matrix

If you don't want to check all possibilities, you can use row operations to convert four columns of the matrix (of your own choosing) to the identity matrix, which will enable for very quick decoding. The code generated is exactly the same.

In more details, each row operation corresponds to multiplying the generator matrix from the left by some invertible matrix. In all, the effect of row operations is to multiply the original generator matrix by some invertible matrix from the left, say $H = AG$ is the new generator matrix. Since $A$ is invertible, both generator matrices generate the same code. If $r = xH$ then $r = (xA)G$, so if you decode $r$ for $H$, you can also decode it for $G$ very easily.

In your case, the row operations result in the following matrix:
$$
\begin{bmatrix}
1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix} =
\begin{bmatrix}
1 & 1 & 1 & 0 \\
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix}
$$

To decode $\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 1 & 1 \end{bmatrix}$, we simply add the first two rows to get the vector $\begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 0 & 1 \end{bmatrix}$. This shows that the original vector doesn't belong to the code.


What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?

Because it is a very natural set of operations: the full trio operations (morphism, inverse morphism, intersection with regular languages) exactly corresponds to closure under finite state transductions.

We can formulate results for such nice families.
Requiring too many properties would exclude some families of languages.
Who wants to miss the context-free languages?

Likewise the Boolean operations (intersection, union, complement) form a nice set, but we do not always require them.

The notion "intersection closed full AFL" is well studied.


Students in classroom problem - Flow in network

The best way I can see to solve this is with integer linear programming.  This is not a polynomial-time algorithm, but it might work well enough in practice.  (I don't think network flow algorithms will work here.)

In particular, you introduce zero-or-one variables $x_{i,t}$, with the intent that $x_{i,t}=1$ means that student $i$ is scheduled in the room starting at time $t$, or $x_{i,t}=0$ otherwise.  Then you add inequalities to ensure that these meet all of your requirements:

$\sum_t x_{i,t} = 1$: each student is scheduled at a single time.
$x_{i,t} + x_{j,t'} \le 1$ whenever $i \ne j$ and $t,t'$ are within 50 minutes of each other: no two students may be scheduled at an overlapping time.

Then you feed this to an off-the-shelf ILP solver and ask it for a feasible solution.  The result is a valid schedule.

As described above, I have ignored the requirement about the 2nd student of the day.  You can fix this by adding some extra variables and inequalities.  Let $y_{i,t}=1$ if student $i$ is assigned at time $t$ and is the first student assigned that day, and $z_{i,t}=1$ if student $i$ is assigned at time $t$ and is the second student assigned that day.  Then we have additional constraints:

$y_{i,t} \le x_{i,t}$, $y_{i,t} + \sum_j \sum_{t' < t} x_{j,t'} \le 1$, $x_{i,t} - \sum_j \sum_{t' < t} x_{j,t'} \le y_{i,t}$, and $\sum_i \sum_{t \in D_k} y_{i,t} = 1$ where the last sum is over all $t$ that fall on day $k$ (on the same day).  These ensure that the $y$'s are consistent with the $x$'s.
$z_{i,t} \le x_{i,t}$, $z_{i,t} \le \sum_j \sum_{t' < t} y_{j,t'}$, $x_{i,t} - 2 + \sum_j \sum_{t' < t} (x_{j,t'} - M z_{j,t'}) \le z_{i,t}$,  $\sum_i \sum_{t \in D_k} z_{i,t} = 1$ where the last sum is over all $t$ that fall on day $k$ (on the same day) and where $M$ is sufficiently large (e.g., at least the number of students).  These ensure that the $z$'s are consistent with the $x$'s.
$z_{i,t} + x_{j,t'} \le 1$ whenever $i\ne j$ and $t,t'$ are within 110 minutes of each other: this ensures a 20-minute gap after the second student of the day.

This should enforce the additional constraints.  Double-check the formulation; I haven't checked it carefully, and there might be small errors in what I wrote.  In general, Express boolean logic operations in zero-one integer linear programming (ILP) gives some helpful tips on encoding constraints into linear inequalities for ILP.


Elements in a less than a value in a subarray

This is essentially the 2D orthogonal range counting problem from computational geometry, which has attracted a lot of attention over the years. Fractional cascading definitely could be applied to reduce the query time to logarithmic while preserving the other big-O bounds. In a nutshell, the idea is to make auxiliary data structures that relate the positions of elements in each parent array to positions in the child array, so that, given the results of a search in the parent, searching the child for the same key is constant-time.


Changing probabilities to 0/1 in definition of class IP

Suppose you have a (randomized) verifier $V$ such that, for all $Q,w$,

$$\begin{align*}
w\in L &\implies \Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3\\
w\notin L &\implies \Pr[V\leftrightarrow Q\text{ accepts }w]= 0.
\end{align*}$$

Since $P$ is one possible value of $Q$, it follows that

$$w\notin L \implies \Pr[V\leftrightarrow P\text{ accepts }w]= 0.$$

This means that for all $w \notin L$, there is no choice of random bits such that $V\leftrightarrow P$ accepts $w$, while for all $w \in L$, there is a choice of random bits such that $V\leftrightarrow P$ accepts $w$.

This gives you a certificate for the claim that $w \in L$: namely, the random bits used during some accepting execution of $V \leftrightarrow P$ on $w$.  By the above arguments, if $w \in L$, such a certificate is guaranteed to exist, whereas if $w \notin L$, no such certificate exists.  $V \leftrightarrow P$ can be used as a verifier to check the certificate.  Since $V \leftrightarrow P$ runs in polynomial time, we have a polynomial-sized certificate and a polynomial-time verifier for $L$, so it follows that $L$ is in NP.

This also helps answer your second question.  If you change the $2/3$ to $1$ but don't change the $1/3$ to $0$, the above argument doesn't go through: you can't conclude that there is no certificate for $w \notin L$, so you no longer have a certificate and verifier for $L$.


What you describe can happen in a feasible flow. However the net flow across the (undirected) edge $\{u,v\}$ would be $0$. Also, you say that the original graph has flow $2c$, this is false since the amount of flow from a vertex $s$ to a vertex $t$ in a graph is not the sum of the flows across all the edges, but rather the amount of flow leaving $s$ or, equivalently, entering in $t$.


Is there a difference between computational graphs and neural networks?

a computational graph is made of node where is done "operation" on incoming variables. (see first paragraph from the link done in OP)

A neural network use perceptron or "neuron" model for each node. a generic example of neuron model is : Each incoming value is multiply by a "synaptic" weight, then are sum and the result will be pass to an activation function. Which will give an output result that could be project to next nodes. Neural Network can "learn" by adapting synaptic weights thanks to methods such as backpropagation or direct feedback alignment.

Any computational graph where nodes are not a kind of neuron/perceptron model are not neural network.


Name of algorithm: When looking for an optimal element in a list, contionusly adapt the acceptance threshhold

These problems are in the field of optimal stopping theory. There are a large number of approaches to the problem, which can be found using this term.

The example about dating appears in Hannah Fry's Ted Talk "The Mathematics of Love"


Some questions on parallel computing and the class NC

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

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

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

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

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

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

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

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

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

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

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

For example, the Circuit Value Problem is defined as:

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

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

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

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


DLOGTIME complexity class and testing the length of the input string

It is hard to answer the question without further context.

Complexity is typically defined in terms of the size of the input (the number of bits needed to represent the input) and therefor depends on the representation you choose for the inputs. (More formally, a language or a formal computational problem is defined over strings of the alphabet, and the complexity is defined based on that, how you interpret these strings as objects (e.g. graphs, natural numbers, etc.) doesn't have an effect on the complexity, a "problem" corresponds to several (formal) computational problems based on the representations used.)

The complexity class $\mathsf{DLogTime}$ is defined as deterministic logarithmic time in the input size, $n$ is the size of the input. I guess you are confused because we typically use Turing machines for defining complexity classes but that may not make sense for sublinear time since one cannot even read the input. For sublinear time the model of computation is typically considered to be Random Access Machines where one can access any bit of the input directly without going over all previous bits using indexes (kind of similar to how memory works in real computers).

One can find the length of the input in two steps using an index variable (a binary number):

Start from 1 and repeatedly double the value till the memory square corresponding to it is blank (an upper bound on the length of the input),
Do a binary search to find the last nonblank symbol. (Blank symbol is not used in the input.)

If the input is a string of length $n$ then this algorithm will find the size of the input in binary in time $O(\lg n)$.


Why is $n \log \log n$ not tightly bounded by $n$?

As $n$ grows bigger, the ratio between $n\log\log n$ and $n$, namely $\log\log n$, tends to infinity. Hence it is not possible to upper bound $n\log\log n \leq Cn$ for any constant $C$. If you stare at this inequality, you discover that the constant $C$ must satisfy $\log\log n \leq C$ for all $n$, yet the function $\log\log n$ is not bounded.


Finding a maximum-weight base of a a matroid, in reverse

Let $M$ be a matroid with non-negative weight function $w$ and rank function $r$ (the rank of a set of points $S \subseteq M$ is the maximal size of an independent subset of $S$). Suppose that the matroid has rank $m$. You propose the following algorithm:

$S = M$.
While $|S| > m$: remove from $S$ a minimum weight element $x$ such that $r(S-x) = m$.
Return $S$.

This algorithm clearly returns a base. Let $W(S)$ denote the maximum weight of an independent subset of $S$. We prove by induction on the steps of the algorithm that $W(S) = W(M)$. The base case is clear. For the inductive step, suppose that $S$ contains a base $B$ of weight $W(M)$, and suppose that we removed an element $x \in S$ to obtain the new set $S'$. If $x \notin B$ then clearly $W(S') = W(M)$. Otherwise, let $B'$ be a base contained in $S'$ (which exists by the definition of the algorithm). Since $|B'| > |B-x|$, there exists an element $y \in B' \setminus B$ such that $B'' = B-x+y$ is a base. By definition, $w(y) \geq w(x)$, and so $$W(S') \geq w(B'') = w(B)-w(x)+w(y) \geq w(B) = W(M),$$
completing the proof.

Answering your question, it is a classical result that the rank function can be computed efficiently using an independence oracle. Perhaps you can come up with the algorithm.


Determining if a context-free grammar produces even-length strings

There is an algorithm:

Recall that given a CFL $L$ and a regular language $K$, the language $L\cap K$ is also CFL (and a CFG for it is computable given a CFG for $L$ and a DFA for $K$).

Now, observe that the language $K=\{w: |w| \text{ is even}\}$ is regular.

From this we conclude that given a CFG $G$, we can construct a CFG for the language $\{w: |w|\text{ is even and }w\in L(G)\}$, and we observe that this language is nonempty iff $G$ generates a word of even length.

Since checking emptiness of CFG can be done in polynomial time, we can solve the problem in polynomial time.


How does Lamport imply anomalous behavior is impossible given these constraints?

The constraint as written by Lamport is $C_i(t+\mu)-C_j(t)\gt0$ or $C_i(t+\mu)\gt C_j(t)$ which can be re-written  $$C_i(t+\mu) - C_i(t)\gt C_j(t) - C_i(t) \tag{*}\label{*}$$
Given Lamport's previous deductions, we recognise the boundary conditions each side must satisfy namely:
$$(1-\kappa)\mu \lt C_i(t+\mu) - C_i(t)$$
$$ \epsilon \gt C_j(t) - C_i(t)$$
Now, Lamport wants to find out the range of values for 'variables' $\epsilon,\kappa$ ($\mu$ is fixed) that will ensure the strict inequality $\eqref{*}$.
Obviously, for real numbers (Lamport's starting assumption) if $x \lt A$ and $y \gt B$, then as long as $y \leq x$ we know $A\gt B$.
In other words, as long as $\epsilon \leq (1-\kappa)\mu$ then $\eqref{*}$ is true and so $$C_i(t+\mu)-C_j(t)\gt0$$


Sum of 2^Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X

If the set you're using is $X=\{x_1,x_2, \dotsc,x_n\}$, then the expression you want to evaluate is equivalent to
$$
(2^{x_1}+1)(2^{x_2}+1)\dotsm(2^{x_n}+1)\bmod{1000000007}
$$
This isn't too hard to prove; here's an example to help you see what's going on:

Suppose $X=\{a,b,c\}$. Then the subsets of $X$ are, obviously,
$$
\{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}
$$
and the corresponding sums of elements in those subsets will be
$$
0,a,b,c,a+b,a+c,b+c,a+b+c
$$
leading to the sum
$$
2^0+2^a+2^b+2^c+2^{a+b}+2^{a+c}+2^{b+c}+2^{a+b+c}=(2^a+1)(2^b+1)(2^c+1)
$$
The general result can be established by a fairly simple induction proof.


Finding number of memory locations in chip

Here is an actual chip! From the '70s :

Motorola MC6810

https://upload.wikimedia.org/wikipedia/commons/f/f8/Motorola_Microcomputer_Components_1978_pg08.jpg

http://www.icpdf.com/MOTOROLA_datasheet/MCM6810_pdf_874837/#view

128 bytes : 128 * 8bits = 1024 bits = $2^{10}$ "memory cells".

I suppose the author considers each bit in a RAM as a "memory location", the way a memory is addressed, the data bus width, doesn't change its capacity : A 1Mega * 8bits RAM has the same capacity as a 512k * 16bits.

On the MC6810, there are 6 chip select inputs, but they are used to ease the selection of different chips connected in parallel, they don't add to the RAM storage capacity.


Undecidability of "is this CFG prefix-free?"

One endmarker is insufficient to prove this. Instead, we must use multiple endmarkers. Here's the full proof, with the same basic idea taken from the other answer.
Using the notation from Sipser 3rd edition problem 5.21, let the string pairs $(t_i, b_i)$ for $i \in \{1, 2 \ldots k\}$ be an instance of the PCP problem. Define grammar rules $T \rightarrow t_i T \texttt{a}_i$ and $T \rightarrow t_i \texttt{a}_i$ (where $\texttt{a}_i$ are new symbols) along with $B \rightarrow b_i B \texttt{a}_i$ and $B \rightarrow b_i \texttt{a}_i$. This instance of PCP has a solution if and only if $T \cap B$ is non-empty. (This construction can be used to prove many other undecidability properties of CFGs; for more, see Sipser 3rd edition chapter 5 or Hopcroft and Ullman 3rd edition chapter 9).
Define more rules $W \rightarrow T\#$ and $W \rightarrow B\#\#$, where $\#$ is another new symbol. Clearly, $W$ is prefix free if and only if $T \cap B$ is non-empty. Hence, a decider for prefix-free CFGs would also decide any PCP problem. Since PCP is undecidable, we have a contradiction, and thus the language of prefix free CFGs is also undecidable.


There are zillions of papers in coding theory, proposing zillions of codes. Most of them are not used, due to several reasons:

Some of the codes are non-constructive.
Some of the codes don't have efficient decoding procedures.
Some of the codes have bad parameters.

The main reason, however, is that practitioners don't spend their time reading the coding theory literature and thinking up applications of the various codes. Rather, given a concrete problem, they first look up the "standard" solutions they know of. I'm putting "standard" in quotes since different people probably use different types of codes — whatever they are used to. There are many reasons for this:

Known codes are the easier to find out about — they are already familiar.
Code (and sometimes hardware) is already available.
Bosses prefer using known and proven tools.
Practitioners are often interested in properties which are either hard to prove or are simply not completely formal, but could be tested experimentally (for example, recovery from burst errors). These are found in their own literature rather than the theoretical coding theory literature.

If none of the standard codes seem to work, then they are in trouble and probably ask an expert. The expert probably knows some other standard codes which do work.

For a new code or type of code to reach the mainstream requires a lot of publicity to make the community aware of it. Mathematicians working in coding theory don't usually care about the practical side, and indeed, often their constructions have theoretical aims which are not important in practice (this is especially common for researchers in theoretical computer science). Even if a particular code is practical, the researcher is usually not interested enough in promoting it for it to become widely known among the practitioners.

Engineers, on the other hand, might publish new practical codes, and rarely one of them does change the mainstream paradigm. Most papers are, however, small variations on known techniques, and are important mostly for people's resumes, or for the particular project they were developed for.

In your particular case, the paper you are linking to is theoretical, and ignores one of the main questions in coding theory, namely how to efficiently decode. This shows that it's a theoretical paper. The motivation behind the paper is to construct orthogonal codes with good parameters. It mentions that orthogonal codes have applications in mathematics, but not necessarily in "real life". Furthermore, as you mention, the construction seems novel, which makes it more interesting mathematically. Practically speaking, the novelty is not as important as the "usability" of the code in terms of parameters and ease of encoding and decoding, an issue not mentioned at all.


A graph property is an isomorphism-invariant property of graphs. That is, $P$ is a graph property if $P(G_1) \leftrightarrow P(G_2)$ whenever $G_1$ and $G_2$ are isomorphic.
Any property of graphs which doesn't refer to specific names of vertices is a graph property. This includes all the usual properties of graphs: connectivity, diameter (that is, the property of having diameter $D$), chromatic number (that is, the property of having chromatic number $\chi$), and so on. A property of graphs which is not a graph property is: "vertices 1 and 2 are connected".
Let us show that connectivity is a graph property. In the same way, you can show that diameter is one. Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be two isomorphic graphs. This means that there is a bijection $\phi\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(\phi(x),\phi(y)) \in E_2$. We will show that if $G_1$ is connected then $G_2$ is also connected. The same argument (using $\phi^{-1}$) will show the converse, completing the proof.
Suppose that $G_1$ is connected, and let $a,b \in V_2$. Since $G_1$ is connected, there is a path in $G_1$ between $\phi^{-1}(a)$ and $\phi^{-1}(b)$, say $\phi^{-1}(a),v_1,\ldots,v_\ell,\phi^{-1}(b)$. Then $a,\phi(v_1),\ldots,\phi(v_\ell),b$ is a path in $G_2$ connecting $a$ and $b$.


Why is it that the flow value can increased along an augmenting path $p$ in a residual network?

Instead of giving a formal proof I will present some intuition on why augmenting paths increase the flow. Look at the picture below. Let's go through some augmenting path, for example the one painted in black. It increases the flow by some $x$. Then go through another one (that has $c_f(p) = y$) that contains an edge which pulls back some flow (edge $(u, v)$ is present only in residual network). When the red path enters $u$, it increases the flow that comes into $u$ by $y$, but then pulls $y$ units of flow back to $v$, so $v$ can use edge from red path to push those $y$ units somewhere else. So you see that $y$ units came to $u$, $y$ units was withdrawn from $u$, $y$ units came back to $v$ and then $y$ units went through the red path. The property that income flow equals the one that goes out is preserved. Capacity constraints (flow through an edge is not greater than capacity of this edge) are also preserved, because $y$ is the smallest edge weight on the red path. As you can see, going through the red path increases overall flow by exactly $y$, because augmenting path  doesn't decrease the flow anywhere, it rather redirects it in the manner described above. It's like vertex $u$ saying to vertex $v$ "Oh hey, the red path gave me some flow, maybe you ($v$) would take back some of the one you gave me and send it to someone else?". I'd say that adding "redirecting" word somehow to "augmenting path" would clear some misunderstanding about this concepct.

Having this intuition, I think that making a formal proof from it should be fairly easy.


What precisely is infinite ambiguity in a grammar?

From a comment by Sylvain:

A grammar is infinitely ambiguous iff there is a productive and accessible nonterminal $A$ s.t. $A \Rightarrow^+ A$. Nonterminals $A$ and $B$ fulfill this characterization in your first example, and so does $S$ in the second example when you add the rule $S \to \varepsilon$. I'll leave the proof of the characterization as an exercise.

   Consider that a parse tree of infinite size for a finite input sentence must repeat a nonterminal spanning the same interval in the input.


Is it necessary to traverse every letter in the tape of a Turing Machine?

To the title question - no, to the flipped version of the same question in the body - yes. It is typically fine to halt without processing the entire input (however see Raphael's answer for certain technicalities in this respect).

There's not really such a thing as "good" or "bad" practice with a Turing Machine in the sense that there are "good" and "bad" practices when programming on a "real" computer.

As they are theoretical models for computations, they are at their best when they prove (or assist in proving) what you need to prove in as clear and direct manner as possible. In this light, as long as your machine only performs permissible actions, then everything is fine - so no cheating, but beyond that it's all good.


In first order logic, how do we normally represent a statement?

This is a good question and comes down to what you want to achieve with the Mother entity.

In your first example, Mother(x, y) is a (binary) relation.  That means that you can have as many ys as you would like per x.  With Mother as a relation, you can also make formula that checks whether you have two ys that satisfies motherhood for x.

In your other example, hasMother(x) is a predicate that can only be true or false.  How many mothers do x have? Impossible to say.  Who is x's mother?  We can't say.

You could also conceive of a mother(x) → y function that maps an x to its mother y, but then you can have only one mother, and every x needs to have a mother (in the model).

It all comes down to (a) what is a natural representation of "the world" (whatever you want to model), and (b) what you want to achieve (whatever you want to get out of your model).


Here are several ways of solving this recurrence. Throughout, I will assume that $T(0) = 0$.

Method 1: Guessing

Here are some values of $T(n)$:
$$
\begin{array}{c|cccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 \\\hline
T(n) & 0 & 1 & 3 & 7 & 15 & 31
\end{array}
$$
If you're familiar with powers of 2, you will recognize that $T(n) = 2^n-1$. If not, you can look it up on the Online Encyclopedia of Integer Sequences, where you will find it as A000225, under the name Mersenne numbers.

Method 2: Homogenization

We look for a related recurrence without the "$+1$". The first think one could try is replacing $T(n)$ with $S(n) = T(n) + C$, which satisfies the recurrence
$$ S(n) = T(n) + C = 2T(n-1) + C + 1 = 2S(n-1) - C + 1. $$
We see that if $C = 1$ then $S(n) = 2S(n-1)$, and so $S(n) = 2^n S(0) = 2^n$. We conclude that $T(n) = 2^n - 1$.

Method 3: Reduction

The recurrence makes it clear that the first order asymptotics of $T(n)$ should be related to $2^n$, and so suggests considering $R(n) = T(n)/2^n$, which satisfies the recurrence
$$ R(n) = \frac{T(n)}{2^n} = \frac{T(n-1)}{2^{n-1}} + \frac{1}{2^n} = R(n-1) + \frac{1}{2^n}. $$
This shows that
$$
R(n) = R(0) + \sum_{m=1}^n \frac{1}{2^m} = 1 - \frac{1}{2^n},
$$
and so $T(n) = 2^n - 1$.

If we are only interested in the asymptotics, we could notice that since the series $\sum_{n=1}^\infty \frac{1}{2^n}$ converges, we clearly have $R(n) = \Theta(1)$, and so $T(n) = \Theta(2^n)$.

Method 4: Generating series

We could also solve the recurrence automatically using generating series. Let
$$ P(x) = \sum_{n=0}^\infty T(n) x^n. $$
Then
$$ P(x) = T(0) + \sum_{n=1}^\infty T(n) x^n = 2\sum_{n=1}^\infty T(n-1) x^n + \sum_{n=1}^\infty x^n = 2xP(x) + \frac{x}{1-x}. $$
We conclude that
$$ P(x) = \frac{x}{(1-x)(1-2x)} = \frac{1}{1-2x} - \frac{1}{1-x} = \sum_{n=0}^\infty (2^n - 1) x^n. $$
Therefore $T(n) = 2^n - 1$.

Method 5: Combinatorial interpretation

This method is more creative. We find some combinatorial object which we already know how to count, and we show that it satisfies the same recurrence. In this case, we could choose all non-empty subsets of $\{1,\ldots,n\}$. Each such subset is either obtained from a non-empty subset of $\{1,\ldots,n-1\}$ by either adding or not adding $n$, and additionally the subset $\{n\}$, which does not arise in this way. The base cases also match, and so $T(n) = 2^n - 1$.