What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$?

If $p$ is prime, then $x^k\equiv c \pmod p$ has a solution if and only if $c^{(p-1)/g} \equiv 1$ where $g=\gcd(k,p-1)$.  The solution is given by $x \equiv \sqrt[g]{c^h} \pmod p$ where $h^{-1} \equiv k/g \pmod{p-1}$.  You can take $g$th roots in polynomial time using an extension of the Tonelli-Shanks algorithm; see On taking roots in Finite Fields by Adleman, Manders, and Miller.  (Strictly speaking, this algorithm requires either reasonable number theoretic assumptions or randomization.)  Given one solution $x$, the other solutions will have the form $x \beta^i$ where $\beta$ is an element of order $g$ modulo $p$.

If $p^m$ is a prime power and $\gcd(p,k)=1$, then you can use Hensel lifting to test whether $x^k \equiv c \pmod{p^m}$ has a solution.  In particular, let $x_i=x \bmod p^i$ and $c_i=c \bmod p^i$ and $y_i = (x_{i+1} - x_i)/p$ and $d_i = (c_{i+1} - c_i)/p$.  Now find $x_1$ such that $x_1^k \equiv c_1 \pmod p$.  If this has no solution, then neither does $x^k \equiv c \pmod{p^m}$, so we can terminate immediately.  Otherwise, we're next going to try to find $x_2$ such that $x_2^k \equiv c_2 \pmod{p^2}$.  Writing $x_2 = x_1 + p y_1$ and $c_2 = c_1 + p d_1$, we obtain the equation

$$(x_1 + y_1 p)^k \equiv (c_1 + d_1 p) \pmod{p^2},$$

or equivalently,

$$k x_1 y_1 \equiv (c_1 - x_1^k)/p + d_1 \pmod p.$$

If $k x_1 \not\equiv 0 \pmod p$, then we can let $y_1 = ((c_1 - x_1^k)/p  + d_1) \cdot (k x_1)^{-1} \bmod p$ and we have a solution for $x_2$.  Otherwise, test whether $x_1^k \equiv c_2 \pmod{p^2}$; if it is, then setting $x_2=x_1$ gives a solution, otherwise there is no solution and we can terminate.  Repeat the same process to find $x_3$, then $x_4$, etc., until you have found $x_m$.  While there may be multiple possible solutions for $x_1$, there is no need to branch and try all of them, because either all will be extendable to $x_m$ or none will.

I am not sure what to do if $\gcd(p,k)=1$.  Perhaps someone else can fill in this gap.

If $N$ is a product of prime powers $p_1^{m_1} \cdots p_n^{m_n}$, then you can use the Chinese remainder theorem to check for a root modulo each of the $p_j^{m_j}$.  A root exists modulo $N$ if and only if it exists modulo each prime power; and once you've found a solution for each prime power, you can combine them with the CRT to obtain a solution modulo $N$.

Proof for first paragraph: If $p$ is prime, then there exists an element $\alpha$ of order $p-1$; assuming $x \equiv \alpha^X \pmod p$ and $c \equiv \alpha^C \pmod p$, we find that the equation has a solution if and only if $Xk \equiv C \pmod{p-1}$ has a solution, which is equivalent to the stated condition in the first paragraph.


In a floating point, by definition, the point floats. What you're proposing is fixed point (which is occasionally used in practice).

A normal IEEE 754 64-bit double precision can store values in the range from $-10^{308}$ to $10^{308}$. This is a much larger range than your system can store given 64 bits (you would need nearly 800 bits to achieve the same).

The precision loss is often acceptable. When you are dealing with a very large value (like $10^{308}$) what comes at the $10^{\textrm{th}}$ place after the decimal point has no significant impact on the outcome of your calculation. When you are dealing with a very small value (like $10^{-20}$), what comes at the $10^{\textrm{th}}$ place after the decimal point has a huge impact on your calculation.

Using floating point thus makes a lot of sense: you get a level of precision that is appropriate for the range of values you're dealing with, and it can represent a very wide range of values in limited space.


Why is the assignment rule the way it is in Hoare Logic?

So after reading and thinking about it more this is my explanation (thanks software foundations):

The key confusion for me seems to be the meaning of $P[e/x]$ (replaces every free instance of x with e). What this does is wherever you see the symbol $x$ literally remove it and place $e$. e.g. $ P[e/x] = (x+y+1)[e/x] \to P[e/x] = (e+y+1)$ so notice how $x$ literally disappeared from $P$. So what we want is once we do the assignment:

$$ x:= e$$

that the statement is true if we had $x$ instead of $e$. So if the rule is:

$$ \{ P[e/x] \} x:= e \{ P \}$$

then what we want is, when we plug $x$ for $e$ we want the statement in consideration to be true. So before we started the code we have $P[e/x]$. Then we run the assignment and all instances of $e$ disappear and we get $x$'s to replace them. That must be true if the code that ran was assignment (since $x$ now hold the value $e$, so you can remove $e$'s and place $x$).

Thats the explanation of the abstract concept. Lets (shamelessly) use the software foundations (SF) example:

  {{ Y = 1 }}  X ::= Y  {{ X = 1 }} In English: if we start out in a state where the value of Y is 1 and we assign Y to X, then we'll finish in a state where X is 1. That is, the property of being equal to 1 gets transferred from Y to X.

Another useful paragraph from SF:

  Similarly, in
         {{ Y + Z = 1 }}  X ::= Y + Z  {{ X = 1 }}
  the same property (being equal to one) gets transferred to X from the expression Y + Z on the right-hand side of the assignment.
  More generally, if a is any arithmetic expression, then
         {{ a = 1 }}  X ::= a  {{ X = 1 }}
  is a valid Hoare triple.

Addendum from comment's great observation:

  it is important to recognize that the rule
  {
  P
  [
  e
  /
  x
  ]
  }
  x
  :=
  e
  {
  P
  }
   allows both the expression
  e
   and the variable
  x
   to occur in the postcondition. In other words, the inference rule allows you to deduce a postcondition in which any subset of the occurrences of
  e
   in the precondition have been replaced with
  x
  , including none of them. Moreover, it allows you to deduce all of these different postconditions simultaneously.

Reply to bonus why is

1) $ \{P[e/x]\} x:=e \{P\} $

better than

2) $ \{ Q \} x:=e \{Q[x/e]\} $:

Besides the subtle point of replacing x with expressions that might be invisible (e.g. e=0, should we replace $0$ with an infinite number of $x$'s? What if the zeros are not there...the rules should be syntactic but I think it's better to avoid such confusions), I think this is the reason:

  What the rule of assignment should capture is that we are assigning the expression e to the variable x. Thus, only x should be "replaced" by e. Intuitively, in the code (or more precisely the state of the program $\sigma$) when x starts holding the value e, it doesn't randomly mean that everywhere where there might be an e it becomes x after executing the assignment $x:=e$. In fact what it does mean is that now in the post condition we have x's. Now those x's if we did not have the assignment should have the value of $e$ i.e. we only "undo" the replacement/assignment the assignment command did. Not every other random expression e. In short, the only way to know where to place the correct e's is by starting in the post condition after the assignment has been done, then starting from there place e's. If we do it backwards we might be replacing e's we didn't want to replace (even if they were probably true, which I guess they should since we are saying x holds the value e after assigning e to x).


Given an instance $(G, k)$ of DOMINATING SET, we construct our instance of MINESWEEPER as follows.

Add a new vertex $s$, connect $s$ with all the vertices of $V(G)$. Label $s$ with $k$.
For each $v\in V(G)$, add a new vertex $s_v$. Connect $s_v$ to all the vertices of $N(v)\cup\{v\}$ (the neighborhood of $v$ and $v$ itself). Connect $s_v$ to $|N(v)| - 1$ new dummy vertices. Label $s_v$ with $|N(v)|$.

Call the constructed graph $G'$. The produced MINESWEEPER instance is $G'$ itself.

We claim that $(G, k)$ is a YES instance of DOMINATING SET iff. $G'$ is a YES instance of MINESWEEPER.

Proof:
If $(G, k)$ is a YES instance of DOMINATING SET, we have a dominating set $S\subseteq V(G)$ with $|S| = k$. By simply marking all the vertices of $S$, we satisfy the label of $s$ in $G'$. Then, for each $s_v\in V(G')$, according to the number of marked vertices (up to now) in $N(v)\cup\{v\}$, we mark some of the dummy vertices connected with $s_v$. Note that, since $S$ is dominating, $N(v)\cup\{v\}\cap S\neq\emptyset$, so at most $|N(v)|-1$ dummy vertices needs to be marked to satisfy the label of $s_v$, so we always have enough number of dummy vertices connected to $s_v$.

Conversely, if $G'$ is a YES instance of MINESWEEPER, we denote by $S$ the non-dummy vertices (which also means that these are in $V(G)$) in the solution to this instance. We now show that $S$ is a dominating set of $G$ and $|S|=k$, which concludes our proof. Indeed, to satisfy the label of $s$, we have that $|S|=k$. For each vertex $s_v$, at most $|N(v)|-1$ dummy vertices connected to it are marked. So in order to satisfy its label, namely $|N(v)|$, either $v$ or some vertex in $N(v)$ is marked. So, in particular, if $v$ is not marked, i.e. $v\not\in S$, there must be some marked vertex in $N(v)$, i.e. $N(v)\cap S\neq\emptyset$. This suffices to prove that $S$ is a dominating set of $G$.$\square$


Your problem is known as reservoir sampling. The algorithm maintains a currently picked line, whose initial value is the very first line. For $k > 1$, you replace the currently picked line by the $k$th line with probability $1/k$. If there are $n$ lines in total, the probability that the $k$th line is chosen is
$$
\frac{1}{k} \cdot \left(1-\frac{1}{k+1}\right) \left(1-\frac{1}{k+2}\right) \cdots \left(1-\frac{1}{n}\right) = \\
\frac{1}{k} \cdot \frac{k}{k+1} \frac{k+1}{k+2} \cdots \frac{n-1}{n} = \frac{1}{n}.
$$


Is there way to compare computing power used in two blockchains when every one of them is using different mathematical function as a Proof-of-Work?

Short answer - no. Any denominator used to compare computing power spent on two different functions would be subjective to those functions. Therefore it cannot be source of consensus spreading over many functions. It'd like comparing apples to oranges.


Given the hash of a collection, H(X), can I build a proof that F(X) == Y, without having X?

Yes, this is possible.  Use a zero knowledge proof (of knowledge).  If F is computable in polynomial time, then there exists a polynomial-time zero-knowledge proof of the property you want, i.e., given K,Y, the prover can construct a proof that there exists X such that H(X)=K and F(X)=Y.  Amazingly, this proof is "zero-knowledge": it reveals nothing about X (other than the property is true).

If you don't care about the zero knowledge part, you can just use an interactive proof system.

Zero-knowledge proofs can be made non-interactive using standard techniques.

There's tons of work on this in the cryptographic research literature.  I can't explain the ideas in the length of an answer here, so I suggest you spend some quality time studying this material.  However, while the theory is elegant and beautiful, you're probably going to find the generic schemes are not very practical and the performance overhead is significant.  Therefore, if you actually want to do this in practice, you'll want to focus on a specific function F and see whether you can build a custom protocol specialized to that particular function F.


Looking for some more details on "Turing" devices

A Turing machine is a simple theoretical/conceptual computational device based on state.  Computation is done through state transitions based on the machines current state.  It is popular in Computer Science theory due to how models and proofs can be built off of it.  Wikipedia has a far more detailed write up on Turing machines than is practical to put here and a general discussion of Turing machines is probably off topic for IT Security.  Computer Science is probably a good place to ask more about Turing machines in general, since they are a fundamental conceptual device for Computer Science theory.

In case you are a visual-learner, interestingly enough, there exist physical incarnations of the abstract device.


If you sum a sequence with period $a$ and a sequence with period $b$, then you get a sequence which is $\mathsf{LCM}(a,b)$-periodic. But the new sequence might have a smaller period, as the following example demonstrates (addition is modulo 10):

022441133502244113350224411335
000772999611888000772999611888
022113022113022113022113022113

The first sequence has period 10 (0224411335), the second sequence as period 15 (000772999611888), and the sum sequence has period 6 (022113), although the LCM is 30.

More generally, the sum of a sequence of period $i$ and a sequence of period $j$ could have period exactly $k$ iff $\mathsf{LCM}(i,j) = \mathsf{LCM}(i,k) = \mathsf{LCM}(j,k)$. See Restrepo and Chacon, On the period of sums of discrete periodic signals.


Need for random bits in final PCP theorem statement

The statement of the PCP theorem is essentially equivalent to the following statement:

  For every problem in NP there is a reduction $f$ to $O(1)$-FUNCTION-SAT such that if $x$ is a YES instance then $f(x)$ is satisfiable, whereas if $x$ is a NO instance then at most half of the clauses of $f(x)$ can be satisfied.

Here an instance of $k$-FUNCTION-SAT consists of a collection of "clauses", each an arbitrary function on $k$ inputs.

Where did the parameters $O(\log n),O(1)$ in the PCP theorem disappear? The first parameter is the logarithm of the number of clauses, so there are $2^{O(\log n)}$ clauses; the second parameter is the arity of the clauses. Together, these parameters guarantee that the FUNCTION-SAT instance has polynomial size, and so the reduction runs in polynomial time.

PCPs are not always described this way, but the descriptions are equivalent. Proof of the equivalence left to the reader.

You are enumerating over all choices of $O(\log n)$ when you are constructing the FUNCTION-SAT instance. But it only allows you to construct the instance, not to tell whether it is satisfiable or not; that is an NP task.


Is it possible to create a regular language from an non regular language? (details inside)

We have a language $L$ which is non-regular. We subtract a finite subset $S \subset L$ of words in $L$ to get the rest: $R = L \setminus S$.

Assume that $R$ is regular. Since regular languages are closed under union, and finite sets of words are trivially regular, we can construct a language $L' = R \cup S$ which is also regular.

Since $S \subset L$, we have $(L \setminus S) \cup S = L$, thus $L' = L$. But $L'$ is regular while $L$ is not - a contradiction. Thus our assumption that $R$ is regular was wrong.


Is there a sometimes-efficient algorithm to solve #SAT?

Counting in the general case

The problem you are interested in is known as #SAT, or model counting. In a sense, it is the classical #P-complete problem. Model counting is hard, even for $2$-SAT! Not surprisingly, the exact methods can only handle instances with around hundreds of variables. Approximate methods exist too, and they might be able to handle instances with around 1000 variables.

Exact counting methods are often based on DPLL-style exhaustive search or some sort of knowledge compilation. The approximate methods are usually categorized as methods that give fast estimates without any guarantees and methods that provide lower or upper bounds with a correctness guarantee. There are also other methods that might not fit the categories, such as discovering backdoors, or methods that insist on certain structural properties to hold on the formulas (or their constraint graph).

There are practical implementations out there. Some exact model counters are CDP, Relsat, Cachet, sharpSAT, and c2d. The sort of main techniques used by the exact solvers are partial counts, component analysis (of the underying constraint graph), formula and component caching, and smart reasoning at each node. Another method based on knowledge compilation converts the input CNF formula into another logical form. From this form, the model count can be deduced easily (polynomial time in the size of the newly produced formula). For example, one might convert the formula to a binary decision diagram (BDD). One could then traverse the BDD from the "1" leaf back to the root. Or for another example, the c2d employs a compiler that turns CNF formulas into deterministic decomposable negation normal form (d-DNNF).

If your instances get larger or you don't care about being exact, approximate methods exist too. With approximate methods, we care about and consider the quality of the estimate and the correctness confidence associated with the estimate reported by our algorithm. One approach by Wei and Selman [2] uses MCMC sampling to compute an approximation of the true model count for the input formula. The method is based on the fact that if one can sample (near-)uniformly from the set of solution of a formula $\phi$, then one can compute a good estimate of the number of solutions of $\phi$.

Gogate and Dechter [3] use a model counting technique known as SampleMinisat. It's based on sampling from the backtrack-free search space of a boolean formula. The technique builds on the idea of importance re-sampling, using DPLL-based SAT solvers to construct the backtrack-free search space. This might be done either completely or up to an approximation. Sampling for estimates with guarantees is also possible. Building on [2], Gomes et al. [4] showed that using sampling with a modified randomized strategy, one can get provable lower bounds on the total model count with high probabilistic correctness guarantees.

There is also work that builds on belief propagation (BP). See Kroc et al. [5] and the BPCount they introduce. In the same paper, the authors give a second method called MiniCount, for providing upper bounds on the model count. There's also a statistical framework which allows one to compute upper bounds under certain statistical assumptions.

Algorithms for #2-SAT and #3-SAT

If you restrict your attention to #2-SAT or #3-SAT, there are algorithms that run in $O(1.3247^n)$ and $O(1.6894^n)$ for these problems respectively [1]. There are slight improvements for these algorithms. For example, Kutzkov [6] improved upon the upper bound of [1] for #3-SAT with an algorithm running in time $O(1.6423^n)$.

As is in the nature of the problem, if you want to solve instances in practice, a lot depends on the size and structure of your instances. The more you know, the more capable you are in choosing the right method.

[1] Vilhelm Dahllöf, Peter Jonsson, and Magnus Wahlström. Counting Satisfying Assignments in 2-SAT and 3-SAT. In Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON-2002), 535-543, 2002.

[2] W. Wei, and B. Selman. A New Approach to Model Counting. In Proceedings of SAT05: 8th International Conference on Theory and Applications of Satisfiability Testing, volume 3569 of Lecture Notes in Computer Science, 324-339, 2005.

[3] R. Gogate, and R. Dechter. Approximate Counting by Sampling the Backtrack-free Search Space. In Proceedings of AAAI-07: 22nd National Conference on Artificial Intelligence, 198–203, Vancouver, 2007.

[4] C. P. Gomes, J. Hoffmann, A. Sabharwal, and B. Selman. From Sampling to Model Counting. In Proceedings of IJCAI-07: 20th International Joint Conference on Artificial Intelligence, 2293–2299, 2007.

[5] L. Kroc, A. Sabharwal, and B. Selman. Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting. In CPAIOR-08: 5th International Conference on Integration of AI and OR Techniques in Constraint Programming, volume 5015 of Lecture Notes in Computer Science, 127–141, 2008.

[6] K. Kutzkov. New upper bound for the #3-SAT problem. Information Processing Letters 105(1), 1-5, 2007.


Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time

Relax every edge of $$ exactly once, if any distance values change, then the shortest path tree given is wrong, if all stay the same then it is correct.

Referring to this statement: As in Bellman-Ford, we run the algorithm $|V|-1$ times to compute the single-source shortest path. After this, we run the same algorithm once to check whether any relaxation happened in the graph. If there was any relaxation that means there is a negative weight cycle, and we return False. That's not exactly the case here, however you get the idea! If the algorithm given by the professor was right, then there shouldn't have any room for relaxation because relaxation means that the current shortest path $\mathrm{delta}(s,v)$ is not the shortest ($d(s,v) > \mathrm{delta}(s,u) + w(u,v)$). Hence, the algorithm was wrong.


A Turing machine is a tuple consisting of an alphabet, a tape, some transition, etc.

I am not one of those. So no. A human being is not a Turing machine (or at least, I am not).


Determine the number of elements that is divisible by a prime number in an array

Yes if the number of integers and primes is large. Sort the primes in ascending order. Count the number of divisible numbers and remove prime factors until the numbers are all larger than the square of the smallest remaining primes. Now the remaining numbers are all primes. Sort them and check which ones are in the list of primes, in linear order.
This works as long as most primes are greater than the square root of the largest number.


Lock-free, constant update-time concurrent tree data-structures?

$O(1)$ doesn't help in and of itself.  In a lock-free data structure there needs to be a single atomic instance when your data structure appears to change.  All the representation invariants need to be in force both immediately before and immediately after that atomic instant.

This means that if you are doing a modification to the data structure the important characteristic is that you can do all the mods on a private data structure and then swap in the modifications in a single atomic instruction.

Lock-freedom is usually easiest when your data structures are immutable (purely functional).  You simply keep a global pointer to the current version of the data structure.  Readers don't need to lock anything.  Modifications to the data-structure are effected by swapping the global pointer to one immutable data structure to another.

For example: if you have a purely functional tree balanced tree you:

Record the current global pointer to the root of the tree.
Create a new tree that inserts or deletes a node.  (This is logarithmic in time and space in the number of nodes currently in the tree, and involves creating new nodes from the modification point up to the root, and just pointing everything new at the old parts of the previous version of the data structure.)
Atomically compare and swap the global pointer to the root.  (Note that this might fail if another modification has happened between the time you recorded the old root pointer and now.  If this happens you go back to step 1 and try again.  This is so-called "optimistic concurrency control.")

Note that the most important part is what I said above about needing to maintain representation invariants.  It is usually not sufficient to have an algorithm that atomically makes a change in the middle of the tree.  Why?  For example: you might have a reader thread that is in the process of doing a preorder traversal of the tree.  If you modify a node that is an ancestor of the node they are currently reading then you are going to invalidate preconditions that they thought they had enforced.  The reader needs to be able to work with the data structure exactly as it was before you made your change, or exactly as it will be after you've made your change.  Not something in between.

Edit: As @Raphael pointed out there are techniques for making mutable data structures lock-free.  A proof by construction that this can always be done is: As long as you have a single global pointer to the "top" of your data structure, even if it is mutable you can always copy the entire data structure, make your mods to the copy, and then, using optimistic concurrency control, try to compare-and-swap the pointer to your newly minted data structure in for the original.  The beauty of functional tree-based data structures is that they keep the cost of copying down at $O(log(N))$ of a size $O(N)$ data structure.


There are two questions here. Let me start with the second: "I don't understand why the proof of the consensus impossibility doesn't work in this case?".

First, I do not know what proof you are talking about. I suppose you are referring to a proof that consensus is not solvable in a t-resilient SWMR system when $0<t<N$.

If $t<N-1$, the easiest way I know to prove this fact it to reduce t-resilient SWMR consensus to $(N-1)$-resilient consensus (i.e. wait-free consensus). This is done via the BG Simulation, which allows $t+1$ wait-free processors in a SWMR system to simulate a t-resilient SWMR system. The BG simulation does not work if failures are initial. Thus this is where the proof fails when $0<t<N-1$.

Now, let us consider $t=N-1$. In this case, one way to prove the impossibility of consensus is to use the critical-state argument. Let me explain why the critical-state argument does not apply if failures are initial only.

The key is that, in a wait-free SWMR algorithm, there are only finitely many executions given a fixed number of processors (this is a consequence of Koenig's lemma: infinite executions are not allowed and the execution tree is finitely branching, thus the execution tree is finite). In consequence, the set of continuations of an execution prefix is finite, and thus by repeatedly increasing the length of the prefix (and thus ruling out more and more continuations) we eventually arrive at a point at which all remaining continuation have the same consensus outcome. By removing one step from this prefix we have our critical state (assuming that the outcome was not predetermined by the inputs).

If we now assume that failures are initial only, we have to allow busy loops in which a processor reads until it sees a particular processor that it saw before, or otherwise we cannot take  advantage of the fact that failures are initial only. Thus, for any n, we have executions that exceed length n (e.g. when a processors polls n times when busy-waiting for another). Thus we now have infinitely many executions, and the reasoning used above to justify the critical-state argument does not apply anymore.

Now, let me answer your first question: "How could one give a consensus algorithm in this system?"

One way to do it is to use a "doorway": take a MWMR register initialized to 0, called the doorway register, and have all processors (a) announce their participation, then (b) read the doorway register, then (c) close the doorway by setting the doorway register to 1, and then (d) announce whether they successfully entered the doorway (i.e. whether they read 0). Finally, a processor (e) takes a snapshot, (f) waits for all processors it sees are participating to announce whether they successfully entered the doorway (using a read loop), and (g) outputs the value of the processor that has the max identifier among those who entered the doorway (any other deterministic function can be used instead of max).


When should you use the existential and universal quantifiers for Relational Calculus?

This question is related to the very basics of database theory, finite model theory and logics. I would strongly suggest Abiteboul's book on Foundations of Databases, or Libkin's book on Finite Model Theory.

Very roughly stated, a database is a collection of facts, and a query is a logical formula, which is used to specify certain patterns to be matched against the database. The most common database query language is unions of conjunctive queries, which is simply a disjunction of conjunctive queries. These are existentially quantified queries and there is NO universal quantification at all. The query in the question is indeed the simple conjunctive query

$\exists \ x \ {Hotel(x, y, london)} $

where $x$ and $y$ are logical variables and $london$ is a constant. Intuitively, the $x$ variables are to be matched to hotel numbers, and $y$ variables to hotel names. Now, in this formula, $y$ is a free variable, i.e. it is not bound to any quantifier. It is wrong to assume that it is bound to a universal quantifier. Such variables are also called the answer variables as these are the variables for which you want to retrieve answers. Note that $x$ is not an answer variable; so, you are not interested in the hotel numbers. All you want to say with this query is: Give me all the names of the hotels in London! Differently, consider this query

${Hotel(x, y, london)} $

where $x$ is also a free variable. It asks for all names + numbers of the hotels in London. A Boolean query is a special case of a conjunctive query that does not contain any free variables. For instance, the query

$\exists \ x,y \ {Hotel(x, y, london)} $

has no free variables and asks a yes/no question: Is there a hotel in London (with some hotel number and name)? Overall, please have a look at the reference books, and simply learn the query semantics.


What's missing is the way you run the Turing Machine $M$ on strings to get the Enumerator. Rather than generate each string, run $M$, and then output this string if the $M$ accepts – which as you identified will not work – you do something like the following, which
adopts the
 strategy of simulating many instances of the $M$ on different strings "in parallel".

Assume the tape has contents
$\langle w_1,  S_1\rangle \# \cdots \# \langle w_n, S_n\rangle$,
where $w_i$ is some word under consideration and $S_i$ is the current state of $M$
operating on $w_i$. This represents that $n$ copies of $M$ are being simulated. $w_i$ is stored so we know what the original input was.

Now run the following loop

At the end the tape write the next string from $w\in\Sigma^*$, along with the
initial configuration $S$ of $M$, that is, write $\# \langle w, S\rangle$.
Simulate each copy of the $M$ on the tape for one step. (Presumably use another tape.)
If any of the $M$s enters an accepting state, put the corresponding string onto the output tape. Remove this instance of $M$ from the tape.
If any of the $M$s enters a rejecting state, remove that instance of $M$ from the tape.
Goto step 1.

It is not hard to argue that all strings $w\in\Sigma^*$ accepted by $M$ will eventually be output on the tape.


Yes, Papadimitriou in his "The Euclidean Traveling Salesman Problem Is NP-complete" paper reduces from Exact Cover to Euclidean TSP.

All the coordinates of the points are of polynomial magnitude.

And the required precision for the $L_0$ value in page 243 is to be able to distinguish between $a$ and ${(a^2+1)}^\frac12$. And near the end of page 241, he wrote "An adequate value of $a$ is 20." So the required precision is finite. Since you only have $n(4a + 13 + 2^\frac12)$, that would only magnify the difference.

All the page numbers above are in the proceedings containing his paper and can be seen once you have downloaded the paper.


Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form

Let $c = \log p$ and $d = \log q$.  Then $\log (p^a q^b) = ca + db$.  Define the set $S_{c,d} = \{ci+dj : i,j \in \mathbb{N}\}$.  Your problem is equivalent to the following:

  Problem 1. Given $a,b \in \mathbb{N}$ and $c,d \in \mathbb{R}$, find $a',b' \in \mathbb{N}$ so that $ca' + db'$ is the next attainable real number in $S_{c,d}$ after $ca + db$.

This is in turn equivalent to the following problem:

  Problem 2. Given $\alpha \in \mathbb{R}$ and $X,Y \in \mathbb{Z}$, find $x,y \in \mathbb{N}$ that minimizes $x+\alpha y$, subject to the requirements that $x \ge X$, $y \ge Y$, and $(x,y) \ne (0,0)$.

(The equivalence can be seen by letting $\alpha = d/c$, $X=-a$, $Y=-b$, and $x=a'-a$, $y=b'-b$.)

Problem 2 now amounts to finding the best rational approximation $x/y$ of $-\alpha$, subject to constraints on the size of $x,y$.  There are many techniques for that, including continued fractions.  You can also express this as the problem of finding a closest lattice point to $(0,0)$ in a certain two-dimensional lattice.  There are many algorithms for closest lattice point search in lattices, also known as the closest vector problem; in two dimensions, I believe they run in polynomial time, if I remember correctly.  See, e.g., https://mathoverflow.net/q/61897.


what would be the drawbacks of lecturing two programming languages simultaneously?

Avoid technical minutiae at all costs.  Devote your focus to the big concepts you want to teach.  I understand the desire to make the point that there is an underlying similarity between all programming languages, but I (personally) don't think the first course is the place to make that point.  Rather, I would focus on problem solving using real-life applications.

I don't have any references to studies that would confirm or refute your specific hypothesis.

Here is an article by Lenore Blum (CMU) on what CMU has done to increase women's enrollment in computer science.  CMU's experience with their introductory classes is discussed on page 8.

http://www.cs.cmu.edu/~lblum/PAPERS/women_in_computer_science.pdf

And here are several newspaper articles about the changes they have been making at Tufts and Harvey Mudd (both of which have had significant increases in the number of women graduating from their CS programs.)

http://www.boston.com/news/education/higher/articles/2005/12/18/in_computer_science_a_growing_gender_gap/

http://www.nytimes.com/2012/04/03/science/giving-women-the-access-code.html

Here are several analogies that come to mind.  See if you think any of them make any sense.

"We are going to teach Physics 101 by alternating lectures between MKS and cgs (or British Imperial Units).  This will open the students minds to thinking more abstractly."

"We are going to be teaching our high-school students driving safety by having them drive a variety of different vehicles, including a sports car with a manual transmission, a large moving van with an automatic transmission, and an off-road four-wheel drive pickup truck.  This is the only way we can get them to generalize the basic safety concepts from one vehicle to another."

"We've got a group of exchange students arriving from southeast asia that speak very little english.  So we're going to teach their intro calculus class half in German and half in Russian, since so much of the research literature from the early 20th century is in those two languages."

"I'm going to post a few of your assignments on the web.  But I'll also send a few to your university email address.  And you should friend me on Facebook and follow me on Twitter and Instagram, because I'll post at least one of your assignments on each of those platforms.  You need to learn these technologies sooner or later, so better sooner than later!"

"By the time a student graduates they need to be proficient at touch-typing on a keyboard.  But we're not a vocational school, we're a university, so we're going to teach the foundations of touch-typing.  Thus we alternate classes between the traditional QWERTY keyboard and the Dvorak layout, because we want the students to focus on the principles, not the details of one keyboard or another."


How does mathematical software evaluate symbolic sums?

It uses algorithms discussed in the book A=B by Petkovšek, Wilf and Zeilberger. These algorithms can compute a closed-form expression for a summation of rational functions (in your case, the rational function is $j(j-1)/2$), or determine that no such closed-form expression exists.


You are referring to the following problem:
$$H = \{ (\langle M \rangle, w, t) \mid \text{$M$ accepts $w$ in time at most $t$} \}$$
where $t$ is binary encoded. You should note this is not the (classical) halting problem, but, rather, the bounded version of the halting problem. The halting problem itself cannot be complete for $\mathsf{EXP}$ (or any other subclass of the recursive languages).

Now, to answer your question. First, notice that, because $t$ is encoded in binary, the input has length $|\langle M \rangle| + |w| + \log t$. To simulate $M$ on $w$ for $t$ steps we can use a universal TM, which takes time $O(t \log t)$. Since we are doing a worst-case analysis, we can afford to view $|\langle M \rangle|$ as constant. Also, because $t \in O(2^{p(|w|)})$ for some polynomial $p$, $\log t \in O(p(|w|))$. Hence, the input has size $O(|w| + p(|w|))$ while our simulation takes time $O(t \log t) \subset O(p(|w|) 2^{p(|w|)})$ and, in turn, $p(|w|) 2^{p(|w|)} \in 2^{\textrm{poly}(|w|)}$. This proves $H \in \mathsf{EXP}$.

Reducing a problem $P \in \mathsf{EXP}$ to $H$ is also very simple: If $P$ is decidable by $M$ in time bounded by a function $f \in 2^{\textrm{poly}(n)}$, then any instance $x$ of $P$ is a yes-instance if and only if $(\langle M \rangle, x, f(|x|)) \in H$, where $f(|x|)$ is given binary encoded. The time taken by this reduction is dominated by computing $f(|x|)$, which can be performed in time polynomial in $|x|$ (by first converting it to binary and then computing $f(|x|)$ in polynomial time).


Voronoi diagram with given number of vertices and sites

Conceptually, it is maybe easier to construct a Delaunay triangulation tessalation. The DT is the dual to the Voronoi diagramm, so you want to limit the number of faces to $0,1,4,7$. This can be achieved by placing some of the vertices of the DT on a circle, or by picking the right number of vertices on the convex hull.

Here is a picture for the 4 vertex case (black DT, red Voronoi diagramm). Play around to get the solutions of 2. and 4. (You already solved 1.)


Distribution of Ones in a Psuedorandom Sequence

Yup, it's possible.  This generator is easily broken, as each output bit has degree only two.  There's an efficient algorithm that, given the first $n$ bits of output from the generator, will let you predict all the future outputs from the generator with 100% accuracy.

Let $x_1,\dots,x_{128}$ denote the initial state of the first LFSR and $x_{129},\dots,x_{256}$ denote the initial state of the second LFSR.  Then every bit produced by your generator can be expressed as a multivariate polynomial over $x_1,\dots,x_{256}$.  The degree of this polynomial is two: each monomial is of the form $x_i x_j$ or $x_i$.  Here were are working in the finite field $GF(2)$, i.e., working modulo two.  In this field, the AND of $x_i$ and $x_j$ is the term $x_i x_j$ (the product).  It follows that the output of the generator is a polynomial of degree two.  (Why?  Because at any given time, the output from the first LFSR is a linear function of the initial state, i.e., a polynomial $p_1(x_1,\dots,x_{128})$ of degree one; and similarly the output from the second LFSR is a linear function, i.e., a polynomial $p_2(x_{129},\dots,x_{256})$ of degree one.  Now the output of the generator is the AND of these two, i.e., it is the product $p_1(x_1,\dots,x_{128}) p_2(x_{129},\dots,x_{256})$, which is a polynomial of degree two.)

So, if you're given $n$ bits of output from this generator, you receive $n$ quadratic equations in the 256 unknowns $x_1,\dots,x_{256}$.  If $n$ is large enough, there are standard techniques for solving this system of equations, which gives you $x_1,\dots,x_{256}$.  At that point you know the initial state of both LFSRs, so you can predict the future output of the generator for all time -- and the scheme is broken.

How do you solve the system of linear equations?  One simple approach is linearization: if $n > 256^2/2$, then you can replace each monomial $x_i x_j$ by a new unknown $y_{i,j}$; then you get a new system of $n$ linear equations in roughly $C(256,2)$ unknowns, which can be efficiently solved using Gaussian elimination.  If $n$ is smaller than that but still significantly larger than 256, you can use relinearization, which is efficient as long as $n$ is large enough.  (You can also try SAT solvers, Groebner basis algorithms, or other methods, though these are not polynomial-time in general.)  For more details on relinearization, see https://crypto.stackexchange.com/a/3736/351.

To avoid this problem, I suggest using a cryptographic-strength pseudorandom generator -- also known in the cryptographic literature as a "stream cipher".  For instance, you could use AES in CTR mode (counter mode).  This will provide very strong resistance against prediction of future outputs, as long as the AES key is chosen at random and is hard to guess.

By the way, the Cryptography Stack Exchange site has many experts who are knowledgeable about this sort of topic, so you might be interested in checking out the material that's available over there.


The energy usage will vary depending on the machine, but as long as all of your results are from the same setup there's a comparatively low-tech, simple solution: Hook up your computer to an electricity meter and take some measurements with the computer "at rest", to get a baseline of its energy consumption. Then, run several trials with each model you're testing, and adjust the readings by the baseline to get the net difference in energy consumption when the model is running.


You can use generating functions. Let me switch notations to $a = n_1$ and $b = n_2$, noticing that empty boxes make no difference. The generating function for the total number of coins is
$$
\left(\frac{1+x}{2}\right)^a \left(\frac{1+x^2}{2}\right)^b,
$$
that is, the coefficient of $x^m$ is the probability that the boxes contain a total of $m$ coins. The trick is now to substitute cubic roots of $3$ for $x$, using the following observation, where $\omega = e^{2\pi i/3}$:
$$
\frac{1^m + \omega^m + (\omega^2)^m}{3} = \begin{cases} 1 & \text{if } 3 \mid m, \\ 0 & \text{otherwise}. \end{cases}
$$
Using this, we find that the probability that you're after is
$$
\frac{1}{3} + \frac{1}{3} \left(\frac{1+\omega}{2}\right)^a \left(\frac{1+\omega^2}{2}\right)^b + \frac{1}{3} \left(\frac{1+\omega^2}{2}\right)^a \left(\frac{1+\omega}{2}\right)^b.
$$

This formula is not necessarily so helpful. Instead, we can use dynamic programming, which can be succinctly expressed using matrices. Suppose that we open the boxes one by one (each one with probability $1/2$), and keep track of the vector of probabilities of the various residues modulo $3$, a column vectors whose entries correspond to the residues $0,1,2$. An opened box with one coin affects the vector according to the matrix (multiplying the vector on the left)
$$
\begin{pmatrix}
0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0
\end{pmatrix}.
$$
If instead we open the box with probability $1/2$, we get the average of this matrix with the identity matrix:
$$
\begin{pmatrix}
\tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2}
\end{pmatrix}.
$$
We can analyze boxes with two coins similarly, and over all the vector of probabilities is
$$
\begin{pmatrix}
\tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2}
\end{pmatrix}^a
\begin{pmatrix}
\tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} \\ \tfrac{1}{2} & 0 & \tfrac{1}{2}
\end{pmatrix}^b
\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}
$$
You can get your probability by taking the first entry. The matrix expression above can be evaluated in many ways – by multiplying the vector matrix-by-matrix, using repeated squaring to compute the matrix powers, or by diagonalizing the matrices to obtain an even more rapid algorithm (which is identical to the formula obtained above using generating functions).

Finally, let me spell out the dynamic programming algorithm, which just implements the matrix-by-matrix approach hinted to above:

Initially, $(p_0,p_1,p_2) \gets (1,0,0)$.
Repeat $n_1$ times: $(p_0,p_1,p_2) \gets (\frac{p_0+p_2}{2},\frac{p_0+p_1}{2},\frac{p_1+p_2}{2})$.
Repeat $n_2$ times: $(p_0,p_1,p_2) \gets (\frac{p_0+p_1}{2},\frac{p_1+p_2}{2},\frac{p_0+p_2}{2})$.


What is the purpose of manipulating trained layers?

No.  I've never heard of this being used for a published task.  Neural nets are trained with optimization (SGD) rather than by swapping/deleting/repeating layers.


How to find number of permutations of 1-N length, each [1-N] with k values

(Your lock values are all distinct. We could instead consider the locks distinct.)

We add a nil value to each lock, representing the lock not being included. Using your example, we get ...

input = [A,B,C,nil] [1,2,3,4,5,nil] [G,H,nil]

... to choose from. There are ...

$$4 \times 6 \times 3 = 72 $$

... ways to do this.

In general, from sets $Locks$, there are ...(

$$\prod_{l \in Locks} (\vert l \vert + 1)$$

... ways.

So far, so mathematical. Now let's generate the possibilities. I'll have to use a programming language. My choice is Clojure, a Lisp. We should be able to at least verify the above result.

(def locks '[[A,B,C] [1,2,3,4,5] [G,H]])

(defn combos [ls]
  (if (empty? ls)
    [()]
    (let [[l & ls] ls
          sub-list (combos ls)]
      (concat
        sub-list
        (for [x l, y sub-list] (cons x y))))))

Now

(count (combos locks))
=> 72

... as expected.

There are better ways to depict the problem space, but this'll surely do.


What does starvation freedom exactly mean?

You cannot imply starvation freedom as definite waiting just because the definition of starvation says that the low priority processes have to wait indefinitely.
From Raynal,

Starvation freedom means that a process that wants to enter the critical section can be bypassed an arbitrary but finite number of times by each other process.

Concurrent Programming: Algorithms, Principles, and Foundations
By Michel Raynal


Making a grammar ambiguous by applying a morphism

The answer depends on the grammar $G$. If $G$ generates at most one word, then no morphism will make it ambiguous (prove!). If $G$ generates more than one word, then the morphism sending all characters to the empty string will make it ambiguous (why?).


Hints:

In the first case, use the inequalities
$$
1 \leq \sum_{i=0}^n c^i = \frac{1-c^{n+1}}{1-c} \leq \frac{1}{1-c}.
$$
In the second case, use the inequalities
$$
c^n \leq \sum_{i=0}^n c^i = \frac{c^{n+1}-1}{c-1} \leq \frac{c}{c-1} c^n.
$$


Proving that f(N) = N lg N + O(N) implies f(N) = Θ(NlogN)

Your third line (of the proof) doesn't seem to make sense, are you trying to say $f(N) \in O(N)$? If so, that's not true (you're trying to prove that it's not true!). Lines 4 and 5 are not clear, but if you were to write that in an exam or paper, you'd get in trouble.

As usual with asymptotic analysis, we just need to go back to the definitions. $f(N) \in \Theta(N\log N)$ means there exists constants $N_{0}$, $c_{1}$ and $c_{2}$ such that $c_{1}\times Nlog N \leq f(N) \leq c_{2}\times N\log N$ for all $N \geq n_{0}$.

There's a method involving limits that works, but I'll do it the old fashioned way first:

Lower bound ($f(N) \in \Omega(N\log N)$):

As $f(N) = N\log N + O(N)$ (and because we're dealing with CS so we make mathematical unjustified assumptions like everything is non-negative) we have $f(N) \geq N \log N$, so we can pick $c_{1} = 1$ and any $n_{0} \geq 0$ and we have $f(N) \in \Omega(N\log N)$.

Upper bound ($f(N) \in O(N\log N)$):

By the definition of $O(\cdot)$, we know that $f(N) \leq N \log N + b\times N$ for all $N \geq m_{0}$, for some constants $b$ and $m_{0}$. We can assume that we're using base 2 logarithms and that $N > 2$, so we know then that $\log N \geq 1$. Therefore $f(N) \leq N\log N + b\times N \leq N\log N + b\times N \log N$.

Thus we can pick $c_{2} = b+1$ and andy $n_{0} \geq \max\{m_{0},2\}$ and we get $f(N) \in O(N\log N)$.

Putting it together:
So we have $f(N) \in O(N\log N)$ and $f(N) \in \Omega(N\log N)$, which gives $f(N) \in \Theta(N\log N)$ where $c_{1} = 1$, $c_{2} = b+1$ and $n_{0} = \max\{m_{0},2,0\}$ (obviously the $0$ is extraneous).

The Limit Approach:

We can also take the limit of the ratio of two functions to determine some asymptotic relationships. In particular for us, if $\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)} = k$ for some constant $k$, then $f(n) \in \Theta(g(n))$.

So for our two funtion, we take $\lim_{n\rightarrow \infty}\frac{f(N)}{N\log N}$ apply l'Hopital's rule a couple of times, and conclude that $f(N) \in \Theta(N\log N)$.


Algorithm for closest available resource

I would call this problem as closest matching between two equal sets with priority.

Here is an $O(n\log n)$ algorithm, assuming the distance is the 2-dimensional Euclidean distance. It might work with the Manhattan distance as well; however, I have not double checked that.

Build a balanced 2-d tree for all taxis in $O(n\log n)$ time. Attach to each node an inventory number, the number of all points in the rectangle or half plane represented by that node, which can be done in an $O(n)$-time tree traversal.

Now iterate over $P_1, P_2, \cdots, P_n$ in that order. For each person $P$, do the following.

  Find all nearest taxis of $P$, using the inventory number and ignore the unavailable taxis, which takes (amortized) $O(\log n)$ time. Assign the taxi with the lowest index among them to $P$. Mark that taxi as unavailable. Subtract one from the inventory number attached to each node that contain $P$, which takes $O(\log n)$ time.


How to prove that ε-loops are not necessary in PDAs?

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

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

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

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

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


Where would someone find amortized analysis more useful than average analysis and the opposite?

The two are not mutually exclusive. In most situations you're interested in amortized analysis, since usually operations are fast enough so that no user would notice a one time long running time, the real performance being determined by the amortized running time. A good example is garbage collection, essential to many modern computer languages. Garbage collection is extremely slow, but the cost is amortized to be very manageable.

The only notable exception to this is real time applications. For example, if you're operating a hard drive, you need to be fast always. Same goes for some other services provided by the operating system. But that's a specialized area.

Average case analysis is relevant when you can expect the data to be random enough. For example, a long scientific simulation could include a random element, and can be analyzed accordingly. Other data should not be assumed to be random for security reasons. For example, a web server distributing work across other servers can be attacked if load balancing relies only on input randomness.

Sometimes the average case is hard to define. For example, the simplex algorithm and SAT solvers often seen to run much faster than the worst case, but it's hard to attribute this to average case behavior since it's difficult to come up with a relevant average case distribution. Instead, one could point out some relevant features of the input, but doing this rigorously is very hard.


Can we use the same reduction L1 -> L2 for coL1 -> coL2

Yes. If $f$ is a polynomial-time computable function such that $x \in L_1 \iff f(x) \in L_2$ then

$x \in \text{co}L_1 \iff x \not\in L_1 \iff f(x) \not\in L_2 \iff f(x) \in \text{co}L_2.
$


You don't need the Myhill-Nerode theorem.
Suppose that $L$ was regular and let $c>0$ be its pumping length.

The word $b^{5^c}$ is in $L$ and therefore there is some positive constant $k \le c < 5^c$ such that $b^{5^c + ik} \in L$ for all integer values of $i \ge -1$.
For $i =1$ you must have $b^{5^c + k} \in L$ which implies that $5^{c} + k$ is a power of $5$.

This is a contradiction since
$
5^ c < 5^c + k < 5^c + 5^c = 2 \cdot 5^c < 5^{c+1}.
$

If you still want to use the Myhill-Nerode theorem you can proceed as follows:
Pick any two non-negative integers $i,j$ with $i<j$ and consider the two words $x= b^{5^i}$ and $x = {5^j}$.  Let $z = b^{4 \cdot 5^i}$. Notice that $xz = b^{5^i + 4 \cdot 5^i} = b^{5^{i+1}} \in L$ while $yz = b^{ 5^j +  4\cdot 5^i} \not\in L$ since $5^j < 5^j +  4 \cdot 5^i < 5^j +  4 \cdot 5^j = 5^{j+1} $. Therefore $z$ is a distinguishing extension for $x$ and $y$ and they cannot belong to the same equivalence class for the relation $R$ defined by $\alpha R \beta$ iff $\alpha \in \Sigma^*$ and $\beta \in \Sigma^*$ have no distinguishing extension. This shows that the number of equivalence classes in the quotient set $L_{/R}$ is not finite and, by the Myhill-Nerode theorem, $L$ is not regular.


Why use comparisons instead of runtime for comparing two algorithms?

This is actually a deep issue that has some methodic and some pragmatic answers. I assume you want to know something about the algorithm(s) at hand. If you want to know which algorithm works better on a given machine on given inputs, go ahead and measure runtimes. If you want to compare the quality of a compiler for a given algorithm, go ahead and measure runtimes. For learning something about the algorithm, don't do it.

Let me first give some reasons why using runtimes is not a good idea.

Generality
Runtimes measured using one language and one compiler on one machine have little meaning if you change any component. Even slightly different implementations of the same algorithm may perform differently because you trigger some compiler opimisation in on case but not in the other.
Prediction
So you have a couple of runtimes for some inputs. What does that tell about the runtime of some other input? In general, nothing.
Significance
Usually, you won't benchmark all inputs (of some size), so that immediately restricts your ability to compare algorithms: maybe your test set triggered the worst case in one and the best case in the other algorithm? Or maybe your inputs were too small to exhibit the runtime behaviour.
Metering
Measuring runtimes well is not trivial. Is there a JIT? Has there been contention, i.e. are you counting time the algorithm did not even run? Can you reproduce exactly the same machine state for another run (of the other algorithm), in particular concurrent processes and caches? How is memory latency dealt with?

I hope these convinced you that runtimes are a horrible measure to compare algorithms, and that some general, abstract method for investigating algorithm runtime is needed.

On to the second part of the question. Why do we use comparisons or similar elementary operations?

Analytic tractability
Assuming you want to do formal analysis, you have to be able to do it. Counting individual statements is very technical, sometimes even hard; some people do it nevertheless (e.g. Knuth). Counting only some statements -- those that dominate the runtime -- is easier. For the same reason, we often "only" investigate (upper bounds on) worst-case runtime.
Dominance
The selected operation dominates the runtime. That does not mean that it contributes the most runtime -- comparisons clearly do not, e.g. in Quicksort when sorting word-sized integers. But they are executed the most often, so by counting them you count how often the most executed parts of the algorithm are run. Consequently, your asymptotic runtime is proportional to the number of dominant elementary operations. This is why we are comfortable using Landau notation and the word "runtime" even though we only count comparisons.

Note that it can be useful to count more than one operation. For example, some Quicksort variants take more comparisons but less swaps than others (on average).

For what it's worth, after you have done all the theory you might want to revisit runtimes in order to verify that the predictions your theory makes are sound. If they are not, your theory is not useful (in practice) and has to be extended. Memory hierarchy is one of the first things you realise is important but missing in basic analyses.


The complement of $\{w: w\text{ has equal numbers of $a$'s, $b$s' and $c$'s}\}$ is context-free

So let us remember the closure properties of context-free languages, gone over in class and stated by the TFS:

* closed under union
* closed under concatenation
* closed under Kleene Star

Now I will show that my language $L'$ is the same as the language $L$. Let $NE(x,y,z)$ be an operation that generates a language such that the number of x's is not the same as the number of y's, with as many z's as one wants anywhere in the language. Thus my language $L'$ is defined as:

$$ NE(a,b,c) \cup NE(c,a,b) \cup NE(b,c,a) $$

This language is obviously $L$. It is all instances of a not equal to b, b not equal to c, and c not equal to a. The nice thing here is that if we prove $NE()$ is context free, then because of symetry and closure under union operation. Let us represent NE as a PDA here:

$$ (s,\epsilon,\epsilon) \rightarrow (p,\$) $$
$$ (p,a,\epsilon) \rightarrow (p,1) $$
$$ (p,b,1) \rightarrow (p,\epsilon) $$
$$ (p,b,\$) \rightarrow (m,1\$) $$
$$ (p,c,\epsilon) \rightarrow (p,\epsilon) $$
$$ (m,c,\epsilon) \rightarrow (p,\epsilon) $$
$$ (m,b,\epsilon) \rightarrow (m,1) $$
$$ (m,a,1) \rightarrow (m,\epsilon) $$
$$ (m,a,\epsilon) \rightarrow (p,1\$) $$
$$ (p,\epsilon,a) \rightarrow (f,\epsilon) $$
$$ (p,\epsilon,b) \rightarrow (f,\epsilon) $$
$$ (m,\epsilon,a) \rightarrow (f,\epsilon) $$
$$ (m,\epsilon,b) \rightarrow (f,\epsilon) $$

So now that I have represented this language as a PDA, all I need to show is that the language I represented corresponds to $NE()$.

First I will show that my PDA, $X$ is $X \subseteq NE$. This is quite easy to see. The only way that one can enter a final state in $X$ is when, under one of our rules, we hit the end of the string, and there is something left on the stack (meaning that there is an unequal number of either a's or b's). we can see here that this is a subset.

Next I will show that $X \supseteq NE$, or in other words, all strings that are part of $NE()$ can be made by $X$. One can see that one can have as many c's as one wants in this model, by the rules:  $ (p/m,c,\epsilon) \rightarrow (p/m,\epsilon) $, so that is not a problem. But how does it promise that all strings of unequal number of a's and b's are not in this language. Again, the grammar only keeps track of how many excess a's or b's there are, and can accept any string of arbitrary length with any permutation of letters as long as one of a or b, has an excess. Thus $X \supseteq NE$.

I have shown that $NE$ is Context Free by building a PDA, and I have shown that $L$ is a finite union of $NE$s, thus $L$ is context-free.


How do you find a hash function that respects a custom equality function?

The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever language you use) equality, for all $x,y$, we have $x \equiv y$ if and only if $f(x)==f(y)$. We call $f(x)$ the normal form of $x$.

Then, the trick is, instead of computing hashes, you compute hashes of normal forms.

Hash functions are specifically designed to produce large changes in output for small changes in input: that's what makes them well suited to hashtables and cryptography. So there's not likely a way to make a hash function that is invariant over some custom equality, except to have it compute on normal forms.

What you've described might work from a correctness point of view, but there are a few things to consider:

It is not hashing. That is, a hash is essentially a function that takes some variable-sized data and produces a fixed size output (in your case, an int). You haven't designed a function at all, you've just defined a way to assign random identifiers to input.
You lose all the advantages of hashing. One main use case of hashing is quickly comparing two things.

If you hash a bunch of things ahead of time, then you very quickly check that any of those two things are for sure different, and if their hashes are the same, you know with high probability that they are actually the same. With your version, you get fast comparison, but to compute all your hashes you'll have already compared all $n^2$ unhashed pairs at least once, so you will never save work.

The other thing hashes are useful for is indexing complex data in a data structure. That is, you convert your key into a hash, and each time you do a key lookup, you compute the hash and use it to find the key in a data structure, possibly a tree or hashtable. With yours, you end up doing $n$ comparisons each time you lookup the hash key, which means you'd be better to just use an unordered list as your data structure and search through it each time, comparing each element to the key you're looking for.

Using unique identifiers instead of hashes is a fine way to index data, but then you definitely do NOT want to generate random identifiers, since there's still a risk of a collision. Usually you'd just keep a counter and generate one plus the last identifier each time you allocate a new one.


Help with question involving k-regular graphs

There is no 7-regular graph on 15 vertices, since $7\times 15$ is odd.


Counting tokens in compilers, lexical analyser

In C, 458cat is a single ppnumber token. It's not a valid number, so it will eventually produce an error message, but it is tokenised as a single token.

There's a longer explanation of this behaviour in this StackOverflow answer.


To show that $A$ is Turing-reducible to $B$ you need to prove the existence of a Turing Machine that is able to decide $A$ when given access to an oracle for $B$.

In your specific case a possible Turing Machine $M$ takes as input a string $x \in \{0,1\}^*$ encoding the natural number $n$ (I'm assuming $0 \in \mathbb{N}$) in binary and operates as follows:

It flips the last bit of $x$. Now $x$ represents an odd number iff the input number $n$ was even.
It invokes the oracle for $B$ with input $x$.
It accepts iff, according to the oracle, $x \in B$.

Notice that the fact that $M$ has access to an oracle for $B$ does not mean that $M$ must use that oracle. The following is also a valid choice for $M$:

Locate the last bit $y$ of the input string $x$.
If $y=0$ accept. Otherwise reject.


Deterministic algorithms for computational distance between distributions

Hint:

 Every randomized algorithm $A(x)$ can be expressed as a deterministic algorithm $A(x;r)$ where $r$ is randomly chosen.  Now what can you say about the value of that absolute difference for different choices of $r$?  What would you like to be able to say about it?


Can such an operation be done with two stacks?

You do not need more operations. In fact, you do not need DUP and DROP, either. All you need are SWAP, PUSH and PULL.

The list of states of main stack below shows how the initial state 1 a 3 p q r 2 x y is changed to 1 a 2 x y 3 p q r. The auxiliary stack is at left hand side growing to the right from its bottom at the very left. The main stack is at right hand side growing to the left from it bottom at the very right. <- means PUSHing to the auxiliary stack and -> mean PULLing from the auxiliary stack.

   <- 1 a 3 p q r 2 x y  //initial state
 1  <-  a 3 p q r 2 x y
 1 a  <-  3 p q r 2 x y
 1 a 3  <-  p q r 2 x y
 1 a 3 p  <-  q r 2 x y
 1 a 3 p q      r 2 x y  //then SWAP
 1 a 3 p q  ->  2 r x y
 1 a 3 p      q 2 r x y  //then SWAP
 1 a 3 p  ->  2 q r x y
 1 a 3      p 2 q r x y  //then SWAP
 1 a 3  ->  2 p q r x y
 1 a      3 2 p q r x y  //then SWAP
 1 a  <-  2 3 p q r x y
 1 a 2  <-  3 p q r x y
 1 a 2 3  <-  p q r x y
 1 a 2 3 p  <-  q r x y
 1 a 2 3 p q      r x y  //then SWAP
 1 a 2 3 p q  ->  x r y
 1 a 2 3 p      q x r y  //then SWAP
 1 a 2 3 p  ->  x q r y
 1 a 2 3      p x q r y  //then SWAP
 1 a 2 3  ->  x p q r y
 1 a 2      3 x p q r y  //then SWAP
 1 a 2  <-  x 3 p q r y
 1 a 2 x  <-  3 p q r y
 1 a 2 x 3  <-  p q r y
 1 a 2 x 3 p  <-  q r y
 1 a 2 x 3 p q      r y  //then SWAP
 1 a 2 x 3 p q  ->  y r
 1 a 2 x 3 p      q y r  //then SWAP
 1 a 2 x 3 p  ->  y q r
 1 a 2 x 3      p y q r  //then SWAP
 1 a 2 x 3  ->  y p q r
 1 a 2 x      3 y p q r  //then SWAP
 1 a 2 x  ->  y 3 p q r
 1 a 2  ->  x y 3 p q r
 1 a  ->  2 x y 3 p q r
 1  ->  a 2 x y 3 p q r
      1 a 2 x y 3 p q r  //final state

Once you have checked the above procedure, you will understand how to proceed in the general situations. In fact, what have been shown above is, basically, the well-known fact that if you can swap any two adjacent elements in an array, you can sort all elements in the array into any permutation you wanted.


If a decision problem is in $P$, must finding the solution be possible in polynomial-time?

No, and the example you list is a classic example: as far as we know, factoring does not appear to be in $P$, but determining whether a number is prime is definitely in $P$.

Another example: Consider the game Hex.  Consider the decision problem: given $n$, determine whether the first player has a winning strategy for Hex on a $n \times n$ board.  There is a corresponding function problem: given $n$, find such a winning strategy.  Well, the decision problem is trivial (it is known that the answer is always "yes"), but the function problem is believed to be very hard (as far as we know).


Reweight general weighted graph to distinct graph for using Borůvka's

Though the Borůvka's algorithm (wiki) for minimum spanning tree is (sometimes? often?) described for weighted graphs with distinct edge weights, this treatment is only for convenience.

If we have an algorithm that assumes the edge weights are unique, we can use it on graphs where multiple edges have the same weight, as long as we have some way of breaking the ties. For example, in graphs where edges have identical weights, edges with equal weights can be ordered based on the lexicographic order of their endpoints (suggested by the wiki article).

To apply the lexicographic order, assume two edges $(a,b)$ and $(c,d)$ have the same weight $w(a,b) = w(c,d)$, where $a,b,c,d$ are (not necessarily distinct) vertices. Then we can decide which of $w(a,b)$ and $w(c,d)$ have the "smaller" weight by comparing the pair $(a,b)$ and $(c,d)$ in their lexicographic order.

Therefore, you don't need to re-weight the equally-weighted edges. You only need to mark them  distinct.


Blind sorting an array with a singular sort function?

Your approach by mimicking Bubble Sort is pretty good.

Here is a hint. Since we can sort a block, we can raise half a block of the largest elements so far like a bubble each time. For example, when $u=5$, if we have done BlockSort on [0,5], [3,8] and [6,11] successively, we will have placed the largest 6/2=3 elements among the first 12 elements at index 9,10 and 11, the end of subarray so far.


Relation between size of address bus and memory size; memory Segmentation in 8086

That's the beauty of cisc machines.
For starters as you can see address bus is 20bit wide but resisters are 16bit wide, so microprocessor will process 16bit at a time.

Now let's answer your questions :

1) Address size has nothing to do with architecture size. You can have instructions that can map 64bit or 128 bit address space in instructions. For example mov   can be hard coded in hardware itself to fetch next addressing scheme as required which eliminates requirements of same size bus and resistors. The same mov command with proper bit masking can use address of special resistors instead of memory spaces. It drills down to the choice of system architecture. Thus the name complex instruction set.
It goes beyond this simple explanation, but to give an idea, instructions are flexible enough to understand addressing schemes.

So answer is no when you are storing resistor data into memory, it refers to 16bit wide data bus. It is still storing data as usual way. But micro processor can operate on 8bit, 16bit or divide 32bit operation in sub operations as well depending on instruction.

It uses segments to divide memory into  usable chunks which is mapped by combing 16bit address scheme but by shifting it to 4bit and adding offset bits to get actual physical address. Modern cpu uses dedicated hardware called memory management unit having multiple operating mode of direct memory access and IO access as well.

Here's the quote :

  Rather than concatenating the segment register with the address
  register, as in most processors whose address space exceeds their
  register size, the 8086 shifts the 16-bit segment only four bits left
  before adding it to the 16-bit offset (16×segment + offset), therefore
  producing a 20-bit external (or effective or physical) address from
  the 32-bit segment:offset pair. As a result, each external address can
  be referred to by 212 = 4096 different segment:offset pairs.

2) Answer to this question is linked on how 8086 translates address to segments. As you can see it doesn't add offsets immediately but directly uses address schemes to map physical address without adding extra hardware. It's a clever way of addressing and doesn't require offset as it's already mapped to stored address space which is kind of 32bit wide when you add address+offset, enough to store 4GB space which you can see in 80386 models. Making it backward compatible as well.


Converting Moore to Mealy When first Node has Output

Answering my own question like a silly person:
Ok, I learned what I was missing. A Mealy Machine cannot handle a lambda as I thought it could. As a result, my question has no real answer. Things do NOT output at the first node. Only the first traversal after the first node has any real meaning.


Language that fulfills pumping lemma but is not in RE

Usual pumping lemma

Here is an answer when we are talking about the usual pumping lemma for regular languages that is taught in most introductory courses of computation theory.

Let alphabet $\Sigma=\{0,1\}$.
Let $L$ be a non-recursively enumerable language over $\Sigma$. For example, $L$ can be the complement language of a semi-decidable but not decidable language such as $\overline{\{ \langle M \rangle \mid \text{ $M$ halt on empty input}\}}.$

Let $L'=\{00w\mid w\in L\}\cup\{01w\mid w\not\in L\} $. Then both $L'$ and $\overline {L'}$ are non-recursively enumerable languages.

Let $F=\{ 1w \mid w\in L' \} \cup \{ 1^kw \mid k\neq 1, w\in \Sigma^* \}$, following the construction in an answer by Hendrik Jan. Then $F$ is not in RE and not in coRE since its first part is not in RE and not in coRE while its second part is regular. It satisfies the usual pumping lemma for regular languages, since its second part is regular while its first part can be pumped down and up "into" its second part by choosing the first 1 to pump.

General pumping lemma

Here is an answer when we are talking about the general (or generalized) pumping lemma for regular languages.

Let alphabet $\Sigma_4=\{0,1,2,3\}$. Let $D$ be the finite language whose words are of length 3 and having a duplicate character. (In fact, $D$ has $4+4\times3\times3=40$ words.) Let $P=\Sigma_4^*\bullet D\bullet\Sigma_4^*$, the languages of all words that contain a substring in $D$. $P$ is a regular language. Any language over $\Sigma_4$ that contains $P$ satisfies the general pumping lemma.

Let $N$ be a language that is not in RE and not in coRE. For example, we can select language $L'$ constructed in previous section. Then $G=P\cup N$ is a language not in RE and not in coRE that satisfies the general pumping lemma.

Here are several exercises that readers can do so as to fill the gaps in the above sections.

Exercise 1. Show the class of non-recursively enumerable languages is closed under concatenation with a fixed string at the front.

Exercise 2. Show the class of non-recursively enumerable languages is closed under union with a regular language.

Exercise 3. Show any language over $\Sigma_4$ that contains $P$ satisfies the general pumping lemma.


Prove or disprove - graph doesn't exists

If the question is - "Does there exists a directed graph $G=(V,E)$ (whose undirected version is connected) such that each DFS run on $G$ (preferably with different choices of root) always return exactly two trees?", then the answer is No.

Compress all SCCs into supernode, and let $G^*=(V^*, E^*)$ be resulting graph with $V^*=\{S_1,S_2,\ldots, S_k\}$. Each SCC ($S_i$'s) must have either an incoming edge or an outgoing edge. Now,

At least one SCC must have a zero incoming edge (say it is $S_1$).
At least one SCC must have a zero outgoing edge (say it is $S_k$).

If you take a root in SCC $S_k$ as compared to $S_1$, then DFS will give one more tree for sure.


How fast can we decide whether a given DFA is minimal?

This might not be exactly the sort of answer you are looking for, but since you asked about decision problems, I thought you might be interested in the complexity of the problem. It is $\mathsf{NL}$-complete.

Now, what does it mean for a DFA to be minimal? There are two properties:

Every state is reachable: $\forall q \in Q \; \exists w \in \Sigma^*$ such that we can reach $q$ from the start state $s$ by following $w$; in symbols: $s \rightarrow_w q$.
Every pair of states is distinguishable: $\forall q,r \in Q$ with $q \neq r$  $\exists w \in \Sigma^*$ such that $q \rightarrow_w s$ and $r \rightarrow_w t$ and $|\{s,t\} \cap F| = 1$ (only one of $s,t$ is an accept state).

Notice that the $x \rightarrow_w y$ can be computed in log-space (i.e. $\mathsf{L}$; just track your current position as you follow $w$ one letter at a time). Further, there is only a finite number of alternations between $\forall$ and $\exists$ so as a consequence of the Immerman-Szelepcsenyi theorem, we have that the problem is in $\mathsf{NL}$.

The easiest way to see that it is hard for $\mathsf{NL}$ is to notice that property 1 solves $s$-$t$ directed unreachability, which is the prototypical hard problem. But even if you consider only reachable DFAs, the problem is still hard (i.e. property 2 is $\mathsf{NL}$-hard) and you can find a relatively straightforward proof in Lemma 2.2 of Cho & Huynh (1992).

Of course, I used non-determinism, so it is a bit of a cough-out in the way it differs from Hopcroft's algorithm. But we know that $\mathsf{NL} \subseteq \mathsf{L}^2$, so you can use those constructions to get yourself a more space-efficient algorithm than Hopcroft (which by its very nature has to keep track of $n$ many partitions).


Difference between deterministic and nondeterministic universal turing machine

Please refer to the answer in the similar question, "Why is simulation by non deterministic Turing machine faster than a deterministic one?".

Basically, in the non-deterministic universal Turing machine we guess the contents of the tape and check if the guess is correct later on. This allows us to save time going to and fro in the work tape.


Minimally extend a tree such that there are no bridges in the new graph

Start by proving the following statement:

Let $G=(V,E)$ be an undirected graph. There are no $\mathrm{bridges}$ if and only if there are two edge disjoint spanning trees of $G$.

Proof:

Suppose there are two edge disjoint spanning trees, $T_1, T_2$ of $G$.
Now we remove an arbitrary edge. If it belongs to neither $T_1$, or $T_2$, we're done. If it belongs to $T_1$, it is therefore not in $T_2 $ (symmetrical for $T_2$)  $\Rightarrow$ $G$ is still connected $\Rightarrow$ there are no $\mathrm{bridges}$ in $G$.

Suppose there are no two edge disjoint spanning trees. Then there is at least one cut $C^*$ of $G$ s.t $C^*=\{A, \bar{A}\}$ and $\delta(C^*) \leq 1$. Otherwise it is easy to constructively show there are two spanning trees.
Let $e$ denote the edge between $A$ and $\bar{A}$. Since $e$ is the only edge connecting the two subsets, by removing it, $G$ is separated into two unconnected componenets, therefore $e$ is a $\mathrm{bridge}$

If you can add any edge you want, simply extend $G$ s.t there are two edge disjoint spanning trees. If you start from a tree, it means you have exactly $n-1$ edges, and to create another distinct spanning tree you would have at least $n-1$ additional edges.
If you can't add any edge you want, see http://i.stanford.edu/pub/cstr/reports/cs/tr/74/455/CS-TR-74-455.pdf by Tarjan on disjoint spanning trees (with algorithm)


why is every self-reducible language in pspace

You haven't defined self-reducible languages, so I'll take as an example SAT, and let you generalize the idea.

In order to solve SAT, we use the following recursive procedure:

If there are no variables, output the value of the formula.
Set the first variable to TRUE, and simplify the formula. Recurse. If TRUE is returned, return TRUE.
Set the first variable to FALSE, and simplify the formula. Recurse. If TRUE is returned, return TRUE.
Return FALSE.

When we set the first variable to TRUE, we need to keep a copy of the formula. At depth $k$ of the recursion, we have $k$ formulas, the size of each at most the size of the original formula. So for a formula of size $n$ having $m$ variables, the total space usage is $O(nm) = O(n^2)$, which is polynomial in the input size.

For general self-reducible languages the same technique applies, with similar results. The details depend on your notion of self-reducibility.


Generate collision resistant identifiers with two-way hashing

Your assumption is probably false. It can only be true if the size of the hash is at least half the size of the key.

If you want to generate an absolutely unique identifier, why not use the key itself? Another option, if you want an alphanumeric identifier, is to use Base64 (which also uses a few punctuation marks).

If you just want a practically unique identifier, you can just use a hash function – any industry-standard one would do. That's exactly their goal. Since it doesn't seem you care about cryptographic security, you can just use MD5 or SHA1.


Algorithm to generate inputs with certain properties, but not accepted by a given regular language

For your specific question, you are asking to generate a string in $\bar{L} \cap P$.  Note that since $L$ is regular, so is $\bar{L}$; and note that $P$ is context-free.  It is known that the intersection of a regular and context-free language is context-free.  So, you're asking: given a context-free language, how do we generate a word in that language?  This is straightforward.

Concretely: you could represent $L$ as a DFA, then take the complement to get a DFA for $\bar{L}$.  You could represent $P$ as a context-free grammar.  Then, using a product construction, you can obtain a context-free grammar for $\bar{L} \cap P$, remove all non-productive nonterminals, and then generate a random derivation in the grammar (or, if you want to get fancier, you can search for the shortest word in the grammar using a simple algorithm).

The product construction works by replacing each nonterminal $T$ from $P$ with nonterminals of the form ${}_sT_t$, with the intended meaning that $L({}_sT_t)$ is the set of all words $w \in L(T)$ such that if you start the DFA in state $s$ and then feed in $w$, it ends in state $t$.  You can figure out how to modify all the rules of the grammar, e.g., $T \to UV$ becomes the collection of rules ${}_sT_u \to {}_sU_t {}_tV_u$ for all states $s,t,u$.

You can find the shortest word in a context-free grammar by a simple iterative algorithm.  For each grammar symbol $T$, let $\ell(T)$ denote the length of the shortest word generated by $T$, i.e., the shortest word in $L(T)$; we assume $\ell(a)=1$ for all terminals.  As a notational convenience, if $\alpha=\alpha_1\cdots \alpha_k$ is a string of terminals and non-terminals, set $\ell(\alpha)=\ell(\alpha_1)+\dots+\ell(\alpha_k)$.  Initially, set $\ell(T) := \infty$ for all nonterminals $T$ and treat all rules as unmarked.  Then, repeat the following.  Pick an unmarked rule $A \to \alpha$ where $\ell(\alpha)<\infty$, set $\ell(A) := \min(\ell(A), \ell(\alpha))$, and mark that rule.  Repeat until convergence.  After this is finished, $L(S)$ tells you the length of the shortest word output by the grammar, if $S$ is the start symbol of the grammar.  You can augment the algorithm to keep track of the word itself as well as its length, and then you'll be able to output the shortest word in the grammar.

This might be handy for your application, because it gives you the shortest counterexample: the shortest string that has balanced parentheses but isn't accepted by your regexp.


There are two main methods of doing IO (both obviously have variants, and both are often combined, some control information using the first method and the majority of the data using the second).

One is communicating directly from the processor with the IO-device.  In that case there is a data bus between the processor and the device.
The other is going through memory. The processor write (or read) in memory at well known addresses and the device either monitor the memory accesses or use the first method to know that it has to process the data.

In my experience, keyboard controllers are often using the first method and display controllers are often using the first method for control information (which display mode for instance, or the well known address where to find the information to display) and the second method for the information to display (represented either as character code or as a bitmap)


parsing at semantic level due to ambiguities

There is no reason to "distinguish between value_expression and
type_conversion" since, according to the grammar a type_conversion is
a value_expression.

You probably mean to distinguish between indexed_name and
type_conversion ... and possibly also function_call, but you do not
give its syntax, so I am not sure.

I do not know VHDL, but it may be that the syntax you have is the
syntax used to explain the language to users, not the syntax actually
used in the parser. The parser could simply use a grammar that does not distinguish between
indexed_name and type_conversion, and leave the distinction for a
later processing stage, when the lexical entities have been identified
and their "nature" is known: array, type or function name.

Alternatively, and more likely, it is possible that symbol tables are built as the
program is parsed, and when an identifier is found by the lexer
(lexical analyser), the lexer will look in the table and will tell the
parser whether it is a type_mark or a prefix (i.e., array identifier) before
the parentheses. Then the parser can proceed with the proper rule for
type_conversion or indexed_name.


How do I stop "cheating" in reinforcement learning (MLP+Evo. Algorithm)?

You are minimizing the wrong loss function.  In other words, you have picked a poor objective function.

Look up the standard objective functions that are used for training neural networks for boolean classification tasks: e.g., mean-squared error, or cross-entropy loss.  This is covered in standard tutorials.  They don't use the function you show.  The function you picked looks... odd, so I suspect it is the source of your porblem.


2 approximation algorithm for the single machine scheduling problem

This is an error in the book. The earliest deadline condition is not used any where in the analysis. This means that we can achieve the 2-approximation algorithm even if we drop this condition.


Build an implication graph, in the style of solving $\text{2-SAT}$: each literal gets a $x_i$ node and a $\neg x_i$ node. Each clause is turned into implications, each implication gives a directed edge from the antecedent-node to the consequence-node.
Collect all the connected components of this graph.
Each connected component will have only $2$ states: since each relationship is of the forms $x_i=x_j$ or $x_i \ne x_j$; this means if you assign even a single variable, the entire component will be force-assigned. This means you only have $2$ choices for each component.
For each connected component, greedily choose the assignment state that will increase (for $\text{MAX}$; decrease for $\text{MIN}$) the truth values in $\mathbf x$.


$E(X) = something \cdot (k-1)$

That $something$ is $p$. The full formula should be $E(Y)=1+p(k-1)$, where $Y$ is the random variable that is the length for the linked list just before the $k$-th operation is performed.

To convince yourself that $p$ is the right answer, try a few cases. When $p=1$, every operation adds one element to $T$. When $p=0$, no prepend operation will happen. When $p=1/2$, an element is added about half of the times. Make sense?

Here is the simple reason why. Let $Y_i$ be the increase of length in step $i$. Then

$Y_1, Y_2, \cdots, Y_n$ are independent random variables,
$E(Y_i)=p$ for all $i$ since the probability of prepending is $p$ for each operation.

Since the expectation of the sum is the sum of the expectations for independent variables, we have
$$\begin{align}
E(Y)
&=E(1+ Y_1+ Y_2+ \cdots+ Y_{k-1})\\
&=1+ E(Y_1)+E(Y_2)+\cdots+E(Y_{k-1})\\
&=1+ p(k-1)
\end{align}$$
where 1 comes from the initial one element in $T$.


Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum

This is not what amortized analysis means: you can not infer the worst case runtime of an algorithm by plotting the actual execution time on larger and larger instances of some specific structure. Sadly, that doesn't prove you have a polynomial-time algorithm. Even when you want to do experimental work, there are other parameters to vary besides the size of the input that will have a major impact on the runtime of the proposed solution. If you do so, you will have a result that roughly says "here's an algorithm that performs well in practice for instances that look like this, but I can't give any theoretical guarantees".
To summarize, it's not impressive to have an algorithm which solves huge instances belonging to a specific family of instances of an NP-hard problem quickly. What is impressive (or rather extremely remarkable), is to have an algorithm that you can prove runs in time that is polynomial in the size of the input regardless of the structure of the instance.


Correctness of asymptotic expression from exact expression

What you wrote is correct under the assumption that $|\Gamma|$ and $|Q|$ are constant (which, from the context, is indeed the case), but can be taken a bit further, and can be made more explicit:

For every $x>0$ it holds that $x=2^{\log x}$. Therefore you get

$$f(n)|Q||\Gamma|^{f(n)}=2^{\log f(n)}2^{\log |Q|}2^{f(n)\log |\Gamma|}=
2^{\log f(n)+\log |Q|+f(n)\log |\Gamma|}=2^{O(f(n))}$$

which is somewhat cleaner.


f(n) and g(n) are monotonically increasing functions. h(n) = max(f,g) => h = O(f) or h = O(g)?

That's not true. Let's define $f$ and $g$:

$$
f(x) = \left\{\begin{aligned}
&1 && x = 0\\
&2f(x-1) && x \equiv 1 \mod 2\\
&4^xf(x-1) && \text{otherwise}
\end{aligned}
\right.$$
$$
g(x) = \left\{\begin{aligned}
&1 && x = 0\\
&4^xg(x-1) && x \equiv 1 \mod 2\\
&2g(x-1) && \text{otherwise}
\end{aligned}
\right.$$

They look odd, but you can easily proof (by induction), that:
$$
max\{f, g\}(x) = \left\{\begin{aligned}
&2^{x}g(x) && x \equiv 0 \mod 2\\
&2^{x}f(x) && x \equiv 1 \mod 2
\end{aligned}
\right.$$

Intuition behind this is that for each number $x$ we 'increase' value of one function by $2$ and one by $4^x$. Increasing first function is straight forward, just for keeping function strictly increasing. Multiplication of second function is more interesting. Since $4^x = 2 \cdot2^{x-1}\cdot2^x$, we can split this operation into 3 steps:

multiply by $2$ since, another function is multiplied by $2$,
multiply by $2^{x-1}$, because another function was already greater by that factor,
multiply by $2^{x}$, because we want our function to be greater by this factor

Now you can easily see, that there is no constant $c$ for which $$max\{f, g\}(x) < cf(x)$$ nor $$max\{f, g\}(x) < cg(x)$$.


Obviously, with the various forms of operating systems out there, this process can vary (and in some cases, be completely different) but this outlines a general overview.

Step 1: Load the program into memory.

This is pretty basic; grab the contents of the program and load it into memory. Depending on how memory is managed by the operating system and the platform, additional steps might be required. These could include configuring the memory page where the program is loaded to permit code execution as well as mapping page(s) to the application's initial stack.

Also, many operating systems won't load the entire program into memory immediately; they'll often allocate physical pages and load parts of the program into memory on-demand. This is generally an implementation detail that's transparent to the process, though.

Step 2: Begin executing the program.

Once the program is loaded into memory, the operating system will create whatever internal structures are required to manage the process (such as a struct task_struct in Linux) and do any other necessary bookkeeping. When that's through, the operating system will locate the program's entry point (often a main function or similar) and direct the processor to start executing the program at that location.

An operating system will usually start a new process in response to an interrupt (generally a system call of some sort) so in order to return to user mode, where the process will execute, a "return from interrupt" instruction (such as iret in x86 assembly) is typically used to restore the system state prior to the interrupt.

Step 3: Give control to another process.

This part depends heavily upon the multitasking architecture of the operating system, if it even supports multitasking. (If it doesn't, skip ahead to Step 5.)

Step 3a: (Preemptive Multitasking) Suspend the process after a short while.

In a preemptive system, a scheduler allocates a small timeslice for each running process. This timeslice is enforced by a system timer, which will fire an interrupt once a process's time is up. The interrupt will transfer control back to the kernel.

Step 3a: (Cooperative Multitasking) Wait for the process to give up control.

Cooperative systems depend on individual processes to manually give control back to the operating system on a regular basis. Of course, if a process misbehaves and doesn't return control, it would hang the operating system.

Step 3b: Save the relevant state of the process.

Once the operating system has control back from the previously executing process, it saves whatever state is necessary to return to the process at a later time. This includes the address of the next instruction the process would have executed, as well as some or all of the processor registers.

Step 4: Return control to the process.

When it's time to resume the process, the operating system will do the reverse process of the previous step; it will restore the processor registers and start executing code where the process previously left off. Like when a process is started, this is often done with a "return from interrupt" instruction. In a preemptive system, the operating system will also start the timeslice clock again.

Step 5: Handle a process's exit.

Once the process has completed its task, it will return control to the operating system for the last time by exiting. Often, the process will provide the operating system with some exit data; the operating system can do whatever it wants with this exit data. That could include notifying the process's parent of the exit, logging the completion of the process, or any number of other things. Once that's all said and done, the operating system will remove its record of the no-longer-running process and (generally) free the memory and resources the program had allocated during its execution.

Again, your mileage may vary depending on what operating system and platform you're working with. They come in all shapes and sizes, and they all work differently.


Can you apply the induction hypothesis to its outcome?

As stated, the reasoning does not make much sense to me.

You claim that, in your specific case, you have

$a < b \wedge P(a) \Longrightarrow \exists c < b$
$P(a) \wedge P(b) \Longrightarrow P(b)$

but these properties are trivial tautologies -- they tell nothing about your specific case.

In the first one, if $a < b$, we already know $\exists c<b$. We don't even need $P(a)$.

The second one is an instance of the tautology $p \land q \implies q$.

I'm not sure how these two properties help in the induction proof at all.


Running time complexity of Binary Search Trees and Big-Omega

Big $O$ and big $\Omega$ are not about running times, they are about the rate of growth of functions. If $f(n)$ is the worst-case running time of some operation on inputs of length $n$, then $f(n) = \Omega(g(n))$ means that there exists $C > 0$ such that for some input of length $n$, the running time is at least $Cg(n)$. The fact that we are talking about big $\Omega$ rather than big $O$ doesn't mean that we switch from worst case to best case. On the contrary, we are estimating the very same function, but from below rather than from above.


Distinction between paging and segmentation?

There are two different address spaces, let's call them logical and physical.  The addresses a programmer thinks about are the logical addresses, the page table translates logical addresses to physical addresses.

As you point out, paging allows you to sparsely map the logical address space to the physical address space.

But the bold sentences in your quote are talking about the sparsity of the logical address space.  The quote is arguing that the valid bit is necessary for the sparsity of the logical address space.


Precomputation for partial products in monoids

As you say, with $O(n)$ precomputation you can arrange that each access takes $O(\log n)$ time.  You build a binary tree over the elements, and annotate each internal node with the product of the leaves under it.  This takes $O(n)$ precomputation and $O(n)$ storage.

If you are willing to do more precomputation, you can reduce the access time.  In particular, with $O(n \log n)$ precomputation and $O(n \log n)$ storage, you can arrange that each access runs in $O(1)$ time.  The idea is outlined below.

Notationally, we will let $b_{i,j}$ denote the product $a_i a_{i+1} \cdots a_j$, as you define in your question.

First, precompute the products $b_{i,n/2-1}$ for $i=1,2,\dots,n/2-1$ and the products $b_{n/2,j}$ for $j=n/2,\dots,n-1,n$.  This can be done with a $O(n)$ precomputation.  This will let you compute any product $b_{i,j}$ in $O(1)$ time if we have $i < n/2 \le n/2$, i.e., if the range $[i,j]$ spans the midpoint.

We still need a way to handle ranges that don't span the midpoint.  We'll handle that recursively.  Basically, take the sequence $a_1,\dots,a_{n/2-1}$ and recursively build a data structure for it (e.g., find its midpoint $a_{n/4}$, etc.).  Also, recursively build a data structure for $a_{n/2},\dots,a_n$.  This will let us compute all products $b_{i,j}$ where $j<n/2$ or $i\ge n/2$, i.e., where the range $[i,j]$ doesn't span the midpoint.  This covers all the cases.

How much time does the precomputation take?  If $T(n)$ denotes the time for the entire precomputation, it satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n),$$

which solves to $T(n) = O(n \log n)$.  Similarly, we can see that the amount of storage needed is also $O(n \log n)$.  Finally, this data structure will let you compute any product $b_{i,j}$ in $O(1)$ time.

(I'll let you figure out how to compute $b_{i,j}$ from this data structure in $O(1)$ time.  It can be done with some clever bit-shifting tricks.  It may help to think about the data structure in terms of the big-endian binary representation of the indices.  For each index $i$, we compute $b_{i,i'}$ where $i,i'$ share a common prefix and then $i'$ is all ones after the common prefix; and we compute $b_{j',j}$ where $j',j$ share a common prefix and then $j'$ is all zeros after the common prefix.  Given $i,j$, we can find the longest common prefix of $i,j$, then express as the product $b_{i,j} = b_{i,i'} b_{j',j}$, look up the values of $b_{i,i'}$ and $b_{j',j}$, and compute the product.  All of these can be done in $O(1)$ time by placing the precomputed values in an array in the correct order.)


Proving $A$ avoiding $B$ regular if $A$ and $B$ are regular

Yes you are on right track.

We can first define ($A$ avoids $B$) as ($A$ - ($A$ has $B$)), where ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings. Then ($A$ avoids $B$) will be strings of $A$ that do not contain strings of $B$ as substrings.

We can define ($A$ has $B$) as $A \cap (\Sigma^* B \Sigma^*)$. Then ($A$ has $B$) are strings of $A$ which contain strings of $B$ as substrings.

Thus you have ($A$ avoids $B$)  = ($A - (A \cap (\Sigma^* B \Sigma^*))$). Since regular languages are closed under concatenation, intersection, and subtraction they are also closed under operaion avoid.

Above relation also gives ($A$ avoids $B$)  = $A -  \Sigma^* B \Sigma^*$ as pointed out by Hendrik Jan.


Computing square vs computing square-root? Time complexity

There is a simple randomized test: pick a random 32-bit prime $p$, and test whether $x^2 \equiv y \pmod p$.  Do this a few times for a few random primes $p$.  (You can even pick a random number $p$ without requiring it be prime.)  If there is any error in your square root, then it is likely that it will be detected by this test.  The chances of failing to detect an error is exponentially small.


Is there a $O(n\frac{\log{n}}{\log{k}})$ sorting algorithm?

So the answer I ended up going with is making the value the key itself, then adding the key and the value to the registers. Once the registers are full, we will pop the smallest key, and do a binary search on where we should be inserting the value into a new sorted array which we will be returning.


approximation algorithm for Travelling Salesman Problem: with a different inequality and not triangle inequality

Review the standard proof that it's a 2-approximation if the weight function satisfies the triangle inequality.  That suggests a way to upper-bound the total length of the Hamilton cycle $H$ returned by the algorithm.

Adjust that reasoning.  For starters, assume that every edge in $H$ is a "shortcut edge" $(u,w)$ that was taken by skipping a single vertex $v$.  What could you conclude about the cost of $H$, compared to the cost of $T$?  If you do a little bit of algebra you should be able to obtain an expression.

Now generalize to arbitrary $H$.