What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues? Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle).

It requires that for each pair of processes $P$ and $Q$ all messages send by $P$ to $Q$ are received and processed by $Q$ in the same order. E.g. if $P$ sends messages $m_1$ and $m_2$ in that order, $Q$ cannot receive $m_2$ before receiving $m_1$.

I would like to see how it breaks if I remove that First-In-First-Out condition and allow reordering. The only counterexample I was able to built uses two processes who want to acquire the shared resource:

$P$ starts with clock 10 and sends request $m_1$ to $Q$
$Q$ starts with clock 1 and sends request $m_2$ to $P$
$Q$ receives request $m_1$ with timestamp 10 and sends acknowledge message $m_3$ to $P$
$P$ receives message $m_3$ before $m_2$ and enters critical section. As  far as $P$ is concerned, it's the only process wanting the resource
$P$ receives message $m_2$ and responds to $Q$ with acknowledge
$Q$ enter critical section as $Q$'s request has timestamp 1 and $P$'s request has timestamp 10, so $Q$ has priority

However, that requires $P$ to respond to $Q$'s request $m_2$ while in critical section. Otherwise, $Q$ will receive acknowledgment when $P$ is no longer in critical section and there will be no conflict.

Question being: how to construct a counterexample where processes do not respond to external messages while in critical section?

Looks like this modification is correct. Proof is similar to proof of Lamport algorithm and follows.

Consider two processes $P_i$ and $P_k$ who entered critical sections at moments $e$ and $f$, correspondingly, requested them at moments $e'$ and $f'$, and exited at moments $e''$ and $f''$.

At moment $e$ process $P_i$ have received a confirmation from $P_k$. Suppose it was sent by $P_k$ at moment $g \to e$.

Case 1: $g < f'$. In that case, process $P_k$ has both itself and $P_i$ in queue, and $P_k$'s ticket is greater than $P_i$'s (because we use logical clock as tickets). So process $P_k$ cannot enter the critical section until it receives a release from $P_i$, and we have a correct mutual exclusion.

Case 2: $f' < f < f'' < g$. In that case, $f'' \to g \to e$, and we have a correct mutual correct mutual exclusion.

Case 3: $f' < f < g < f''$. That case is impossible as $P_k$ have sent a confirmation while in critical section.

Case 4: $f' < g < f < f''$. In that case, process $P_k$ should've received a confirmation from process $P_i$ by $f$. Suppose it was sent by $P_i$ at moment $h$. If $h > e$, then $h > e''$ and we have a correct mutual exclusion ($e''
\to h \to f$). Otherwise, $h < e$, so process $P_i$ learns about $P_k$'s wish before entering the critical section. Similarly, as $g < f$, $P_k$ learns about $P_i$'s wish before entering the critical section. But only one of them has lower priority, hence, their critical sections happen in order.


What is Harrison hashing, its applications in web search engines? What is Harrison hashing and what are its applications in web searching?
Can some one give me some relevant information?

Update:

I found it here , and is a part of M.Tech syllabus of a friend of mine. I need to explain him this concept and then see how it can be applied in web applications.
Many thanks for spending your precious time.

I think you are looking for Implementation of the Substring Test by Hashing by Malcolm C. Harrison. It describes a fast implementation, which determines if one string contains a specified substring. This technique is appropriate in searching of large static text files.

Also you can find in String Searching Algorithms By Graham A. Stephen.


Show a sequence of distinct Primes number is O(log n) Suppose I have a sequence:

$$n = \prod_{i=1}^{r(n)} p_i^{d_i}$$

for some primes $p_1 < p_2 < \dots < p_{r(n)}$, and each $d_i \geq 1$ an integer. The function $r(n)$ denotes the number of distinct primes divisor of $n$.

I'm trying to show $r(n) = O(\log n)$.

What I have tried:
I think I can establish an upper bound on $\prod_{i=1}^{r(n)} p_i^{d_i}$ to show its asymptotic bound.

To simplify and without loss of generality, let $d_i = 1$. Then,

$$n = \prod_{i=1}^{r(n)} p_i$$
$$\log n = \log (\prod_{i=1}^{r(n)} p_i)$$
$$\log n \geq \Sigma_{i=1}^{r(n)} \log p_i$$

Then not sure where to go from here.

I think I want to show something like:

$$\log n \geq \frac{r(n) + 1}{2}$$

Since each of the prime numbers is at least 2, we have
$$n \geq \prod_{i=1}^{r(n)} p_i \geq \prod_{i=1}^{r(n)} 2 = 2^{r(n)}, $$
from which it follows that $r(n) \leq \log_2 n$.

In fact, since the prime numbers are generally larger than 2, we can obtain a better bound, namely $$ r(n) \lesssim \frac{\log n}{\log \log n}. $$
See for example MathWorld, which states the number of distinct prime factors in a primorial.


What is the role of Numerical Gradient Computation in Backpropagation algorithm? I was listening CS231n (2017) lectures and noted that there is a lot of attention to Numerical Gradient Computation (NGC). It starts @5:53 in this video and appears a few times later.

Also, looking at the batch normalization materials (example), I found a lot of attention drawn to exactly the same topic (well, probably because it is the same backpropagation...).

As I understood, gradients we use in various optimization methods (vanilla SGD, Adam) require us to know activation function derivative. I suppose, if the activation function is complex or we are lazy enough to take derivative analytically, we need to compute gradient numerically and that is where we use NGC.

Questions:

Is that the only purpose of NGC in backpropagation?
Isn't it faster to use analytically form of the activation function derivative to calculate gradients?

The purpose is pure educational. Students that jump straight to mid- or high-level libraries like tensorflow, keras, theano, etc don't have to compute the gradients themselves. On the one hand, it saves a lot of time, but on the other hand, it is makes it very easy to abstract away the learning process.

Here's how Andrej Karpathy puts it (the lecturer of the previous cs231n classes at Stanford):

  When we offered CS231n (Deep Learning class) at Stanford, we intentionally designed the programming assignments to include explicit calculations involved in backpropagation on the lowest level. The students had to implement the forward and the backward pass of each layer in raw numpy. Inevitably, some students complained on the class message boards:

  “Why do we have to write the backward pass when frameworks in the real
  world, such as TensorFlow, compute them for you automatically?”

  ...

  The problem with Backpropagation is that it is a leaky abstraction.

  In other words, it is easy to fall into the trap of abstracting away the learning process — believing that you can simply stack arbitrary layers together and backprop will “magically make them work” on your data.

I recommend to read the whole post, it's very interesting.

So, you try to compute gradients manually. And when you do that you find that it's pretty hard to assess if the code is right: it's just a raw formula that takes a bunch of floating numbers and returns another bunch of floating numbers. And here you find the alternative numerical method that you can compare to very useful.

Of course, analytical formulas are faster and more precise and they are used in practice whenever possible. But while studying neural networks and back-propagation, it's very useful to get through manual computation at least once. Besides, it sometimes helps to find the bugs.


I do not understand why finding the minimum of elements take O(n) time I know that sorting the array take O(logn) time. But why finding the minimum of elements take O(n) time, which is more expensive? If I sort the array, I simply output the first element and this would be my minimum.

Sorting the array using comparison-based method takes $\Omega(n \log n)$. So sorting is obviously more expensive than finding minimum in $\mathcal O(n)$.

In fact finding minimum or sorting takes $\Omega(n)$ to at least read the whole array. For finding minimum it is actually $\Theta(n)$.

If it were true that sorting takes $\mathcal O(\log n)$ then you would be right to use sorting instead.


Decidability of halting problem for DPDAs with $\epsilon$-transitions? For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space.

But what about PDAs with $\epsilon$-transitions?  Is the halting problem decidable for deterministic PDA's with $\epsilon$-transitions?  Given such a DPDA $P$ and an input $x$, can we decide whether $P$ will halt on input $x$?

The stack may be infinitely large, so it seems like it might be much harder here to see if the PDA is in an infinite loop or not.

I don't think it's as easy as answered here for non-$\epsilon$ PDAs:

  [For] DFAs or PDAs, the halting problem is decidable: the machine
  always halts because it halts when it reaches the end of its input,
  the input is finite and the machine consumes one character of input at
  every step.

  Is the halting problem specific to Turing machines?)

The answer to my earlier question (Is a PDA's stack size linear bounded in input size?) also seems to point in a direction of a higher difficulty of proving this.

Let $L_1$ be the language of all $(M, p, y)$ such that if we start $M$ (a DPDA with $\epsilon$ transitions) in state $p$ with a stack consisting of only $y$ (which is either a single symbol or nothing), then reading an empty string as input would cause $M$ to eventually return to state $p$, with a $y$ on top of its stack if $y$ was a symbol rather than nothing (if $y$ was originally nothing, we don't care about what's on the top of stack after $M$ returns to $p$; anything is fine).
claim: $L_1$ is decidable.
proof: modify $M$ as follows: make a copy $p_0$ of $p$ with the same outgoing transitions but no incoming transitions, and start the DPDA in $p_0$ with a symbol $y$ (or empty) in its stack. If $y$ is empty, then make $p$ the only accept state. Otherwise if $y$ is a symbol, then after creating $p_0$, modify the outgoing transition of $p$ with $y$ on the top of its stack to instantly go to a state $w$ that is now the only accept state (see note 1). Now use the standard CFL emptiness decider on this modified DPDA and we are done.
Note 1: If there is no such transition to modify due to determinism of $M$, i.e. $p$ only has one outgoing $\epsilon$ transition that either does nothing or pushes some symbol onto the stack, then do the following instead: delete the transition, add one that pops $y$ and goes to $w$ and also add trivial no-op transition that pops then immediately pushes back all other symbols that are not $y$.
Next, let $L_2$ be the language of all $(N, q, x)$ such that if we start the DPDA $N$ in state $q$ with a stack having only a single symbol $x$ (or empty), then with an empty input string, it will run forever without ever attempting to pop an empty stack. Note Sipser calls $(q, x)$ a "looping situation".
claim: $L_2$ is decidable (Sipser third edition problem 4.32 asks to prove this)
proof: take $N$ and delete all its input-reading transitions (leaving only $\epsilon$ transitions). Then, start $N$ in state $q$ with an $x$ on its stack, and for every state $p$ it enters, take its stack top $y$ and run the decider for $L_1$ on $(N, p, y)$. This procedure is guaranteed to terminate in either an accept for $L_1$ for some $p$ and $y$, or $N$ itself will terminate (either by attempting to pop an empty stack or by running out of $\epsilon$ transitions to follow). (Why?  Suppose $N$ runs forever.  Consider all of the pairs $(p,y)$ that it encounters at each step during execution.  Since there are only finitely many states and symbols, by the pigeonhole principle, there must be some pair $(p,y)$ that is encountered infinitely often during execution; consider all the time points where we encounter $(p,y)$.  Since the size of the stack cannot decrease forever, there must be some adjacent pair of such time points where the stack is larger at the second than at the first.  Now consider the execution between between those two times, and find the time in that range when the stack is smallest.  Let $p'$ be the state of the DPDA and $y'$ the value on the top of its stack.  Then starting the DPDA at state $p'$  and just $y'$ on the stack and running forward will eventually return to state $p'$ with $y'$ on the top of the stack.  Why?  Well, we start $(p',y')$, then reach a point with state $p$ and $y$ on the top of the stack, then continues on to a point with state $p'$ and $y'$ on the top of the stack, and we never pop off the initial $y'$.  Basically, we've decomposed the trajectory $(p,y) \leadsto (p',y') \leadsto (p,y)$ into its second part $(p',y') \leadsto (p,y)$ followed by its first part $(p,y) \leadsto (p',y')$, but with things chosen so that we can start with just the symbol $y'$ on the stack and nothing more, and it will never get popped off.  It follows that $(N,p',y')$ is accepted by $L_1$, i.e., if $N$ runs forever, it will visit a pair that is accepted by $L_1$.)
Finally, we get to the problem in the main question: define $L_3$ as the language of $(M, x)$ where $x$ is some input string such that the DPDA $M$ halts on input $x$.
claim: $L_3$ is decidable.
proof: run $M$ on input $x$, and after every input symbol read, run the decider for $L_2$ on the current state and stack top: either $M$ itself will halt or the $L_2$ decider will return an acceptance. (Why?  Suppose $M$ never halts normally. Then consider the configuration $(q,s)$ where $s$ is the shortest stack among all configurations, resolving ties arbitrarily. Since $s$ is among the shortest stacks, it will never pop below the element on top of $s$.  Consequently, $(q,y)$ is accepted by the decider for $L_2$, where $y$ is the top of $s$.)
Note 2: it's probably not necessary to run $L_2$ decider to prove decidability of $L_3$: we can just run the $L_1$ decider instead.


Who invented the state elimination algorithm for converting finite automata into regular expressions? The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. However, I can't seem to find any references to who first invented this algorithm.

Does anyone know who invented the state elimination algorithm? Ideally, I'd like a reference to a specific paper or textbook.

Thanks!

According to my information the technique is by J.A. Brzozowski and E.J. McCluskey. The method is described in Signal Flow Graph Techniques for Sequential Circuit State Diagrams, IEEE Transactions on Electronic Computers, 67 - 76, 1963.


Origin of theta-joins I've taken an introductory database course where like many good database courses, they taught relational algebra, including $\theta$-joins. However, I've recently read E. F. Codd's 1970 paper, A Relational Model of Data for Large Shared Databanks, and the concept of $\theta$-joins is nowhere to be found. He does use the symbol  $\theta$ in the paper in section 2.2 though, but to refer to something much more general than joins.

In fact, Natural Joins are even defined slightly differently then the definition I'm familiar with. It requires that the original relations be completely recoverable from the joined relation.

So my question is when/in what paper/by who was the modern notion of the $\theta$-join introduced that is often taught by universities?

(A link to Wikipedia's definition of a $\theta$-join, similar to the one I learned in my course)

Section 2.3.3 in :

Codd, E.F. (1972). "Relational Completeness of Data Base Sublanguages" is what you need.


Witness length independent $\exists$-Operator Short version:

Is there an operator $\exists$ (on complexity classes) s.t. $\exists P = NP$ and $\exists REC=RE$, i.e. you can use the same operator on multiple interesting classes without explicitly stating a class of functions that limits the length of the witnesses?
The construction should not rely on the existence of a definition of the class using any specific computation model (like Turing machines), i.e. it should be defined for any class of languages.

Long Version:

For any complexity class $\mathcal{C}$, any language $L$ and any class of functions $F\subseteq\{f|f:\mathbb{N}\rightarrow\mathbb{N}\}$ define

$$\exists^{f,\#} L =\{x \in (\Sigma\setminus\{\#\})^*|\exists w\in(\Sigma\setminus\{\#\})^*: x\#w \in L, |w| \leq f(|x|) \}$$
$$\exists^F \mathcal{C} =\{L|\exists\#\exists f\in F\exists L'\in\mathcal{C}:L=\exists^{f,\#} L'\} \qquad .$$

Note: If $F=\mathbb{N}^{\mathbb{N}} = \{f|f:\mathbb{N}\rightarrow\mathbb{N}\}$ the length of the witness $w$ becomes unrestricted (set $f(n)$ to be the maximum length of a witness for all inputs of size $n$).

It is well known that $NP=\exists^pP$, where $p$ is the set of all polynomials (see WP:Polynomial hierarchy) and $\exists^{\mathbb{N}^{\mathbb{N}}}REC=RE$ (see WP:Arithmetical hierarchy).

Now I'd like to know, if one could get rid of the class of functions $F$ or define $F$ depending on the class $\mathcal{C}$ without using a certain way to define the class (Not: If $\mathcal{C}$ is the class of languages accepted by a TM in $\mathrm{DTIME}(\dots)$, then $F:=\dots$)

Things I've tried so far:

$\exists\mathcal{C} = \exists^F\mathcal{C} \text{ where } \exists^{o(F)}\mathcal{C} \subseteq \mathcal{C} \text{ and } \exists^F\mathcal{C}\nsubseteq \mathcal{C}$
$\exists\mathcal{C} = \exists^{F'}\mathcal{C} \text{ where } F'=\{2^f|f\in F\} \text{ and } F \text{ maximal s.t. } \exists^{F}\mathcal{C} \subseteq \mathcal{C}$

(added:) $\exists\mathcal{C} = \exists^F\mathcal{C} \text{ where } F=\{f\,|\,\forall L\forall\#\notin\Sigma(L):\, \{\#^{f(|w|)}w|w\in L\} \in \mathcal{C} \Leftrightarrow L \in \mathcal{C}\}$, i.e. those functions s.t. $\mathcal{C}$ is "invariant" under padding ($\Sigma(L)=\{a|\exists i\exists w_1,\dots,w_k \in L:\, w_i = a \}$).

1 and 2 don't work for P, I'm not sure about 3.

You don't need a witness at all. You can allow the Turing machine to make a non-deterministic "guess" at any time. A string is accepted iff there is a sequence of guesses that make the Turing machine accept it, otherwise it is rejected.

Edit: If you want a definition which does not rely on the machine model, then it would be a bit awkward. Here is one example, which includes a cheat - using the associated function class. Given a (time) complexity $C$ and its associated function class $FC$, the allowed witness lengths are parametrized by $f \in FC$: the lengths are given by $n \mapsto |f(0^n)|$.


Efficiently finding key sets A few years ago I participated in  German highschool computer science competition. One of the problems was this (slightly abbreviated):

  A somewhat unusual electronic lock consists of $n$ switches than can be turned on ($1$) or off ($0$). For economic reasons only $k$ of these switches are actually connected to the lock, the rest are dummies. It's impossible to tell these apart. The lock opens when all $k$ connected switches are set to the right combination, regardless of the setting of the dummy switches.

  If you want to open the lock without knowing the right combination, you could repeatedly setup the switches into different positions and then press open until the lock actually opens. Construct an algorithm that for a given pair $(n,k)$ finds a set of setups for all keys such that regardless of which keys are connected to the lock and of regardless what combination of those actually opens the lock, one of the setups will open the lock. Try to construct an algorithm that computes a minimal set.

The solution that I coded (which is more or less equal to the reference solution) works like this:

Let $S$ be the set of all setups in the output.
Generate $M$, a set of $m$ setups randomly where $m$ is a customizeable parameter
For each element of $M$, compute how many combinations it covers that were not already covered
Add the element of $M$ that covers the most new solutions to $S$
For each element of $S$, check if if you remove it from $S$, the number of solutions covered by $S$ would fall. If that is not the case, remove that setup from $S$.
If $S$ covers all possible combinations, terminate.

Can somebody explain me better ways to solve this problem? Is it possible to find a minimal set of setups in reasonable aka polynomial time (the reference solution hints that this is not possible)?

Your problem is discussed in the paper Efficient construction of a small hitting set for combinatorial rectangles in high dimension by Linial, Luby, Saks and Zuckerman. The object you're after is called a $(2,n,2^{-k})$-hitting set in the paper (this notation is not standard). They construct such a set of size $\mathrm{poly}(2^k\log n)$ in time $\mathrm{poly}(2^k n)$, and give a lower bound of $\Omega(2^{k+1} + \log n)$. Their construction certainly doesn't produce a minimal hitting set, and they're not necessarily interested in your range of parameters, but perhaps you could chase the literature from there on and find more relevant material.


What is the name of the problem? (partitioning graph into three covers) I was wondering if this problem has a name:

Given a simple graph whose edges are colored red, blue and green, $G=(V,B\cup R\cup G)$, is there a vertex-coloring $c:V\to \{B,R,G\}$ such that every edge has an endpoint with the same color?

Also, is this known to be NP-complete?

This can also be viewed as a special case of CSP (or a generalization of 2SAT) where each constraint is a disjunction of 2 variables that could take one of three values, and there are no two constraints on the same variables-pair.

Your problem can be solved in linear time, by reduction to 2SAT. For each vertex $v$ we will have three variables $v_R,v_B,v_G$ and clauses $\lnot v_R \lor \lnot v_B,\lnot v_R \lor \lnot v_G, \lnot v_B \lor \lnot v_G$. These ensure that at most one of $v_R,v_B,v_G$ is true. For each edge $(v,w)$ labeled $R$, we will add the clause $v_R \lor w_R$. If there is a valid vertex coloring in your sense, then it clearly translates to a solution of this 2SAT instance. Conversely, any solution to the 2SAT instance corresponds to a partial coloring in which each edge is incident to a vertex with the same color. Coloring the other vertices arbitrarily, we obtain a valid vertex coloring in your sense.


One-time-pad possible solutions I am having a very difficult time trying to understand what exactly this question is asking.

  How many valid English plaintexts are there for the ciphertext message CJU using a length-3, one-time pad of cyclic shifts, (i, j, k)?

If the encrypted question message is CJU and the one time pad is i, j, k would there not be exactly 1 solution? We are given the one time pad i, j, k so we can derive the plaintext simply by some alagebra

(x + 9) % 26 = 3

(y + 10) % 26 = 10

(z + 11) % 26 = 21

Where x, y, and z are the plaintext letters T, Z, J?

I feel like this is a trick question that I am not understanding

$(i,j,k)$ is not a specific OPT. It's three variable names that you can use to talk about the key. The question is just asking, "Given all possible three-character OTPs, how many valid English plaintexts are there for the ciphertext CJU?"

In other words, how many different values are there for the triple $(i,j,k)$ such that "CJU" decrypts to an actual English word.


Situation where FFD < BFD I am practicing for an exam and one of the exercises is:

  Find an example sequence where FFD (offline) performs better than BFD (offline).

Intuitively I would say no such sequence exists as the sequence is sorted, but I have not managed to find a counterexample or proof.

Isn't First/Best Fit Decreasing always considered offline (requiring sorting the input assumed unsorted)?
Anyway, let me assume "performs better" to mean uses less bins.
I find it annoyingly hard to try to find an example using a minimum number of items, of item values and minimum item values - and to argue convincingly that it is minimal, but

   try a bin size of 16 and items of 11, 6, 6, 3, 2, 2, 2. Bin contents after adding each item:
 - FF: 11 11,6 11,12 14,12 16,12 16,14 16,16
 - BF: 11 11,6 11,12 11,15 13,15 15,15 15,15,2


Minimizing the SUM algorithm We are given $2n$ positive integers $a_1,a_2\ldots,a_n$ and and $$b_1,b_2,\ldots,b_n$$ as input.

The question is to find a permutation $O$ on $\{1,2,\ldots,n\}$
that minimizes $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right).$$

For example, take $n = 3$, $a_1 = 10, a_2 = 1, a_3 = 100, b_1 = 10, b_2 = 100$, and $b_3 = 1$.
  If we take $O$ so that $O(1) = 1, O(2) = 3$, and $O(3) = 2$, we have $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 1311.$$

The desired output is $O(1) = 3, O(2) = 1$, and $O(3) = 2$, which yields $$\sum_{i=1}^n \left(a_{O(i)} \cdot \sum_{j=1}^i b_{O(j)}\right) = 321.$$

Trying all possibility is exponential.
How can I find an optimal permutation $O$?

Did you check what's the class of your problem? I'd try a reduction to a scheduling problem.

If you want to have something so you solve it today, use Branch and Bound. Bounds should be easy to find.


Binary Floating Point Range/Precision for 4-bit Mantissa and 4-bit Exponent I'm trying to understand binary floating point and using just a 4-bit mantissa and a 4-bit exponent (both 2s compliment) to keep things simple.

As far as I can tell, the largest denary number I can represent is 112: 0111 0111

So why do I have trouble representing denary 11 (eleven) in this system? I get that the largest (positive) mantissa is 7 in denary (0111). So I'm inferring that I can't represent consecutive positive integers between 0 and the maximum value of 112.

Is that correct? If so, can someone help me to see why please? Which numbers in this range can I represent?

Yes, that is correct. Your mantissa has only three magnitude bits, so you can only represent numbers from -8 to 7, multiplied of course by any power of 2 from $2^{-8}$ to $2^7$. 11 is impossible to represent, because any positive exponent gets you multiples of 2, any negative exponent gets you numbers less or equal to $7*2^{-1}=3.5$, and exponent 0 is just numbers from -8 to 7.


For two large (10^6) integers A and B, find the number of set bits in the result of their multiplication I've recently stumbled upon a problem that I struggle realy hard with ever since.
There are two large decimal integers, order of magnitude $10^6$. The task is to find how many bits in the binary representation of $A*B$ are set (how many 1s are there in the binary representation). Now, for small numbers, that's trivial. You just multiply them, and then using bit-shifts compare each bit with a 1, incrementing a 1-counter every time bit & 1 is true. However, for very large numbers, hardly any programming language will allow the user to perform such multiplication. So how to achieve thet without any high-level languages and fancy libraries?
I think the proper start here is to create arrays for both numbers, to store them as separate digits. That can be done in a number of ways, from using sprintf and then transcribing the char array to int array using intarr[i] = chararr[i] - '0', or by a simple loop which divides the number modulo 10 and then divides it by 10. Either way, we're left with two arrays of the respective numbers' digits, and we can multiply them by each other quite easily. Now, we're left with and int array of the multiplication result's digits. Where do we go from here? How to get a binary representation of a very large number stored like that? How to count the 1s in its binary representation? Is there any trick for that?

I would assume that a very large product is at least say up to 128 bits (product of two 64 bit integers). In that case there are simple algorithms that calculate the higher and the lower 64 bits of the result, and then you count individually how many bits are set in the higher 64 bits, and how many in the lower 64 bits, and add the two numbers.
If your very large product is the product of say two numbers of $10^6$ bits each, these numbers could each be split into say 15,625 64 bit integers, and the product can be calculated easily with O(n^2) operations for n = 15,625. Or it can be calculated faster but with much more difficulty with a more complicated algorithm. This gives a result of 31,250 64 bit integers, and you can easily count the number of bits set in each integer, and add those numbers.


What is the simplest way to understand Turing machines and the busy beaver problem? The Wikipedia description has way too much math.

From quora.com:

A Turing machine is a computer (PC, Mac, iPhone or Conway's Game of Life - pick whichever is most familiar) with unlimited storage (memory, hard disk, doesn't matter). Assume you can program the computer in some programming language, and that you're interested in what it can and cannot compute. "Compute" means "read some input, do stuff, write some output".
This is not the usual description of a Turing machine, of course, but for the study of computability - which is mostly what Turing machines are good for - it's completely equivalent.
The Busy Beaver problem is this: suppose I challenge you to write a computer program (again, pick your favorite programming language) whose sole purpose in life is to print a long string of dots and then stop. If the length of your program is limited to k characters, how long of a string can you make?
It should be clear that this question has an answer, for any choice of programming language and any given limit k. After all, there are only finitely many possible computer programs of length, say, 10,000 characters in, say, C++; some of them print finite strings of dots, and of all the ones that do, we can pick the one (or ones) that print the absolutely longest string.
If you happen to know something about programming, it should also be clear that as soon as k becomes reasonably large to accommodate some non-trivial programs, the answer will be incredibly humungous. It's quite easy, for example, to write a computer program that prints 100^{100} dots and then stops, and in most reasonable programming languages this shouldn't take up more than a few hundred characters to implement. With some cleverness you can get much higher numbers.
The Busy Beaver function is a table that lists, for any given k, the answer to this problem - the length of the longest string of dots you can achieve with a program of length k that prints such a string and stops. This function, or table, is pretty wild: it can be shown that it grows faster than any computable function. Therefore it is itself non-computable. It's unknowable in a pretty strong sense.
If you don't know what "programming language" means or what programming languages can do, you can just imagine that you're giving a friend a notebook with very precise instructions such that, if your friend follows those instructions, she will end up writing a great number of dots on a very large piece of paper. You needn't assume the friend is a math genius, but you may assume she's immortal, very patient and capable of following simple instructions like "write the number 6 on the yellow sticky note" or "read the number on the orange sticky note, erase it and replace it with the next counting number". It's fine if she can't count beyond a billion herself: with enough sticky notes we can help her overcome that.


Analyzing space complexity of passing data to function by reference I have some difficulties with understanding the space complexity of the following algorithm.
I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^N), where N - the length of the initial vector. In all those cases all the subsets (vectors) are passed by value, so we contain every subset in the recursion stack. But i passed everything by reference. This is my code:
class Solution {
public:
vector<vector<int>> result;
void rec(vector<int>& nums, int &position, vector<int> &currentSubset) {
    if (position == nums.size()) {
        result.push_back(currentSubset);
        return;
    }

    currentSubset.push_back(nums[position]);
    position++;
    rec(nums, position, currentSubset);
    currentSubset.pop_back();
    rec(nums, position, currentSubset);
    position--;
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector <int> currentSubset;
    int position = 0;
    rec(nums, position, currentSubset);
    return result;
}
};

Would the space complexity be O(N)? As far as i know, passing by reference doesn't allocate new memory, so every possible subset would be contained in the same vector, which was created before the recursion calls.
I would also appreciate, if you told me how to estimate the space complexity, when working with references in general. Those are the only cases, where i hesitate about the correctness of my reasonings.
Thank you.

All the computations of complexity depend on your model of computation, in other words on what you would like to count.
You may, as you say, only count memory that your code itself allocates. You should be aware that this way of counting space used can become useless easily. You can modify any algorithm to delegate all allocation to the caller. It is not very informative to say that you can solve any problem in constant space.
Another possibility is to count all memory space that gets accessed. If an algorithm accesses all the memory to store the input, do we count it? Some people do.
A more common way to define memory complexity is to measure the memory that the program modifies. Whether the program allocates it or the caller does, it doesn't matter in this case.
Relevant to the computation is also the units in which the memory is measured. You could count bits. This assumption leads to the claim that storing an integer $n$ will require $O(\log(n))$ of space. But this is not the only model used. You could assume that your model of a computer stores integers. In this model storing an integer requires just one unit of space. This is common when the size of the integers involved at not going to be large compared to other sizes of the inputs. These assumptions are relevant to the discussion in the comments. You both are right, but are using different units to quantify memory. These are not even the only options. Some models assume that a unit of memory can store an infinite precision real number, for example.
There are other aspects that sometimes are also taken into account. For example, in real world computers not all memory is the same. In some models memory is separated in a hierarchy. For example, according to response time. Registers and cache are faster than hard drive or magnetic tape. The space complexity can take into account how much of the different  types of memory is used.
It is very common to just mention an $O$ class to which the amount of space used, as a function of some size of the input, belongs. To not be wrong it is better to clarify what is being counted and in what units.


Clarification on Solving Recurrence Relations (Linear) I'm trying to understand how to find the asymptotic complexity of a linear recurrence relation. So far, what I understand is that if only one linear recurrence call is made (ex. cn + T(n-4)), substitution or the recurrence tree can be used. However, what should one do if there are 2 or more linear recurrence calls? For the example I got in class (shown below), I got that T(n) = T(n-4) + logn + T(n-10). I tried setting a lower bound of T(n)> log n + 2T(n-10) since that's how we solved Fibbonacci Numbers, but I wound up with a complex summation that I could not solve. Any help is appreciated, thank you!

The first step is to solve the easier recurrence
$$
T(n) = T(n-4) + T(n-10).
$$
This is explained in our reference question. The solution to your recurrence will likely be larger by a factor of $\log n$, roughly speaking.

Indeed, you can consider a recursion tree in which the root is $n$, and a node $m$ has children $m-4$ and $m-10$ (you stop the recursion at some constant $m$). The solution to the recurrence $T(n) = T(n-4) + T(n-10)$ is proportional to the number of leaves, which we expect to be proportional to the number of nodes. For all $m \geq \sqrt{n}$ (say), $\log n = \Theta(\log m)$, which leads us to expect that the solution of your non-homogeneous recurrence is larger by a factor of $\log n$ than the solution of the corresponding homogeneous recurrence $T(n) = T(n-4) + T(n-10)$.

The preceding paragraph contains some intuition which will need to be proven. But whether or not the $\log n$ factor appears in the final formula makes little difference, since the growth rate of the recurrence is exponential.


Greedy algorithm to find Minimum Dominating Set in a tree Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?

Any negative answer that says that no greedy algorithm will work cannot be proved rigorously since we do not have a definition of an greedy algorithm. So I will just say, no, it is very unlikely that there is a greedy algorithm that will always yield a minimum dominating set if it is given a tree graph as input.

The most common greedy algorithm for dominating set is to repeatedly selecting a vertex with the maximum number of adjacent vertices that are not selected and that are not connected to any vertices selected (not dominated) so far until all vertices are dominated. The following graph illustrates how soon it fails. In the first step we will select vertex 0, the only vertex whose degree is greater than 2. Then we will select vertex 2, 4, 6 for our dominating set. However, the minimal dominating set, {vertex 1, vertex 3, vertex 5} has only three vertices.

Furthermore, any strategy that avoids selecting a vertex that has been dominated might not succeed at all. According to Do Almost All Trees Have No Perfect Dominating Set? by BQ Yue, the average number of perfect dominating sets among all trees of order $n$ is likely approaching zero as $n$ goes to infinity.

A proper strategy to find a minimal dominating set for a tree is dynamic programming. Root the tree at an arbitrary vertex if it is not rooted yet. Now you start computing recursively the minimal dominating set for each subtree with its root included in the set as well as with its root not included in the set.


Correctness of Linearizability vs Sequential consistency in replication I'm currently studying Sequential consistency vs linearizability:
I know that SC has to be consistent with the order of how the individual client issued them, and for linearizability, it's with the real-time ordering.
What I don't understand is:
"The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. "
Which is the first property of both Sequential consistency and linearizability
For me, it sounds like that if 2 clients communicate with some system, the state of the objects should be the same on a single server and on a system with multiple replica managers RM.
But if that is true, how is this example SC:
Client 1:
SetBalance x in RM B to 1
Client 2:
getBalance y in RM A = 0
getBalance x in RM A = 0
Client 1:
SetBalance y in RM A to 2
But if the above example is true, that means my understanding of "The interleaved sequence..." is wrong. since that would imply that the second get balance of client 2 should be 1 ( but at the same time, that means that the system is linearizable since that follows real-time ordering).
So what does:
"The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. "
Mean? and why is it used to determine the correctness of replication

A Sequential Consistent (SC) system should behave as if there is just a single copy of the data.
So lets try to determine a possible memory order for your scenario:
1:client2:read(y=0)
2:client2:read(x=0)
3:client1:write(x=1)
4:client1:write(y=2)

This is valid according to SC. Keep in mind that the real time order of requests, doesn't need to preserved. So perhaps the client2.read(x=1) happened later than the client1.write(x=1), it can be ordered in the memory order before the write.
Lets change the example a bit to make it more interesting:
1:client1:write(x=1)
2:client1:write(y=2)
3:client2:read(y=2)
4:client2:read(x=0)

This example isn't SC because the read of x=0, doesn't see the most recent write before it in the memory order. It should have seen x=1. And this is the consequence of the lack of coherence (so what you could get with replicas being out of sync).


Transforming an arbitrary cover into a vertex cover Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$.
I have furthermore a set $C$ of points where each point $c \in C$ is contained in $\mathcal{G}$. Furthermore, it holds  for any point $p$ in $\mathcal{G}$ that there exists a $c \in C$ with  geodesic distance to $p$ at most one. (The distance is measured as the shortest distance within $\mathcal{G}$.)

I want to argue that given a $C$ for which the above condition holds, I can easily transform it into a vertex cover, or put differently, transform it into a $C'$ of same cardinality s.t any $c \in C'$ is placed in $\mathcal{G}$  at a vertex of $G$, and $C'$ still covers $G$.

My approach was to orient the edges and move the points in $C$ at the end vertex of the arc. But so far I did not find a correct orientation which yields $C'$ from $C$.

Does anybody have an idea?

If no points in $C$ lie exactly on the mid-point of an edge in $\mathcal{G}$, then it suffices to associate each point in $C$ to the nearest vertex in $\mathcal{G}$. I will leave it as an exercise to the reader to prove this (hint: prove by contradiction).

On the other hand, if points in $C$ are allowed to lie on the mid-point of edges, then we can provide a counter-example:

The blue lines and circles are $\mathcal{G}$ and the red crosses are $C$.

EDITED TO ADD: An example with a biconnected graph


Is the problem that determines whenever the word member $\in$ L(M) decidable or not? Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M).
You must realize that M is not one specific machine and can be any turing Machine with the same alphabet.
My goal is to determine whenever this problem is decidable or not.
My idea was to use mapping reducibility. The goal was to see if we can translate all problems from $A_{TM}$ which is known to be undecidable into our current problem. This would make our current problem undecidable by contagion. However I'm struggling in doing so because I'm not sure if it's possible. $A_{TM}$ is defined as a Turing machine M that accepts the word w.
Any help to get unstuck would be appreciated.

I would try it like this:
Reduction from $A_{TM}$: Given TM $A$ und word $w$.
Use that to define a new machine $A'$ that works as follows:

Run like $A$ on input $w$
If $A$ rejects $w$, go into eternal loop.
If $A$ accepts, delete the band content and write "member"


About showing algorithmic gap instance for the Goemans-Williamson SDP Using usual notation we have,

$SDP(G) \geq OPT(G) \geq Alg_{GW}(G) \geq \alpha_{GW} SDP(G) \geq \alpha_{GW} OPT(G)$

where we mean,

$SDP(G)$ = The maximum value that the SDP finds of the objective function $\sum_{(u,v) \in E} w_{uv}( 1-\vec{y_u}.\vec{y_v})/2$  (one unit vector $\vec{y_v}$ in $\mathbb{R}^d$ for each vertex $v$ for some $d$) And $w_{uv}$ are the given edge weights such that $\sum_{(u,v) \in E} w_{uv} =1$

$OPT(G)$ = The actual size of the max-cut for the graph

$Alg_{GW}(G)$ = The value of the max-cut returned by the randomized rounding prescription of Goemans-Williamson

$\alpha_{GW}$ = the famous constant of $\sim 0.878$

If say someone shows that for every $\epsilon$ there is a graph $G(\epsilon)$ such that $(\alpha_{GW}+\epsilon)OPT(G(\epsilon)) \geq Alg_{GW}(G(\epsilon))$ then does this imply that this is a class of graphs on which the algorithm is performing as bad as it could?
Why does showing the existence of such a family of graphs as above also  necessarily imply that on this family $SDP(G(\epsilon)) = OPT(G(\epsilon))$ ?

A graph for which $Alg(G) = \beta OPT(G)$ is, by definition, a graph on which the algorithm has approximation ratio $\beta$. You can use this insight to answer the first question.

As to your second question, suppose that $Alg(G) \leq (\alpha_{GW}+\epsilon) OPT(G)$. Since $Alg(G) \geq \alpha_{GW} SDP(G)$, we deduce that
$$
\alpha_{GW} SDP(G) \leq Alg(G) \leq (\alpha_{GW}+\epsilon) OPT(G).
$$
Therefore $SDP(G) \leq (1+O(\epsilon)) OPT(G)$.


Reasoning on Efficiency (3) This is my third installation of my "Reasoning on Efficiency" series. This question builds on my first question in the series: "Reasoning on Efficiency (1)"

The question in this installment builds on the ideas developed in the first question.

Advertising out of the way, let's proceed. My question is this:

  Giving a particular problem $P_i$. Let the most optimum possible algorithm* for solving $P_i$ be $A_{ij}$,
  $$A_{ij} \rightarrow H(x)$$

  My question is this: Is it possible to prove that $$H(x) = \Theta\left(f(x)\right)$$
  Where $f(x)$ is a function with known time complexity.

*If for any Problem $P_i$, $K_i$ is the set of all possible algorithms(both known and unknown) for solving $P_i$. A given algorithm $A_{ij} \in K_i$ is said to be the "most optimum possible" if:
$$\forall A_{ix} \in K_i, A_{ij} = o\left(A_{ix}\right)$$

The answer depends on your computation model. Let's consider the case of Turing machines, and the language $L$ over $\{0,1\}$ of words ending in $1$. This language has time complexity $n+1$.

Blum's speedup theorem states that optimal algorithms don't exist for all problems, in a very strong sense (which is explained in the Wikipedia article).

Finally, let me mention that your notion of optimality is too restrictive. Given an algorithm with running time $T(n)$ for any problem, it is easy to construct (in the Turing machine model) another algorithm whose running time is also $T(n)$. So no language can have an optimal algorithm in this very strong sense. Even if you consider only running times, it is easy to construct (in the same model) another algorithm with the different running time $T(n)+1$. So no non-trivial language can have an optimal running time in your very strong sense.


Complex property of sparse horner polynomials by induction I'm following this article to do a formal proof on elliptic curve cryptography. My question here addresses only a property "easily proved by induction".

Definitions (the important part is the addition definition at the bottom)

Let assume the following hierarchy:

abstract class shf;
case class const(c: Integer) extends shf
case class POP(i: nat, p: shf) extends shf
case class POW(i: nat, p: shf, q: shf) extends shf

where nat is the type for naturals including zero. We state also a property on the hierarchy called normality given by the function:

def normal(p: shf) = p match {
 case const(c) => true
 case POP(i,p) => i > 0 && normal(p) && p = POW(_,_,_)
 case POW(i,p,q) => i > 0 && normal(p) && normal(q) && p != POW(_,_,0)
}

Assume we have some type shfn to say that we have a shf with the normality property. Then also define these functions:

def pop(i: nat, p: shfn) = {
 case i = 0 or p = const(_) => p
 case p = POP(j,q) => POP(i+j,q)
 case _ => POP(i,p)
}

Denote nat* the naturals without zero:

def pow(i: nat*, p: shfn) = {
 case p = 0 => pop(1,q)
 case p = POW(j,r,0) => POW(i+j,r,q)
 case _ => POW(i,p,q)
}

Finally, define the addition operation:

if (x = const(c1)) {
 if(y = const(c2))       c1+c2 (over the integers)
 else if(y = POP(i,p))   POP(i,x+p)
 else if(y = POW(i,p,q)) POW(i,p,x+q)
}

if(y = const(c)) y+x

if(x = POP(i,p) && y = POP(j,q)){
 if(i=j)        pop(i,p+q)
 else if(i > j) pop(j,POP(i-j,p)+q)
 else if(i < j) pop(j,POP(j-i,q)+p)
}

if(x = POP(i,p) && y = POW(j,q,r)){
 if(i=1) POW(j,q,r+p)
 else    POW(j,q,r+POP(i-1,p))
}

if(y = POP(i,p) && x = POW(j,q,r)) y+x

if(x = POW(i,p,q) && y = POW(j,r,s)){
 if(i=j)        pow(i,p+r,q+s)
 else if(i > j) pow(j,POW(i-j,p,0)+r,q+s)
 else           pow(i,POW(j-i,r,0)+p,s+q)
}

The problem

I'm trying to prove that if $x,y$ are normal then $x+y$ is also normal. But the induction is not trivial to me.

I tried to split it. First I consider $x$ to be constant and everything went well by using the corresponding induction hypothesis.

The problem appears when I consider $x$ to be $POP$ and I do induction on $y$. When $y$ is also $POP$ I have to rely on the $POW$ case because note that as $x,y$ are normal and instances of $POP$ then their second components need to be instances of pow. The other cases for this situation then need the $POP-POW$ case. But proving the $POP-POW$ case could potentially lead to a $POP-POP$ case again.

How can I structure my proof to succeed?

You may want to look at the actual proof on ACL2 here. Also, if you have any ideas to simplify the problem (to make it more easy to reason about and describe it) please let me know.

Intuition

Intuitively a POP construct represents a jump in the list of variables where our shf form is evaluated and a POW represents a polynomial in current variable x of the form $x^i \cdot p + q$. So normality for POP means that the jumping index is as big as possible (there cannot be nested POPs) and normality for POW means the power index $i$ is as big as possible.

You need to use induction on some complexity measure $\mu(x,y)$ (on some well-ordered domain) which has the following property:

  When running the addition procedure on $x,y$, all recursive calls are on pairs $z,w$ for which $\mu(z,w) < \mu(x,y)$.

A complexity measure satisfying this property shows that the addition procedure terminates, and will also allow you to do a proof by induction. Note that you are not splitting into cases according to the coarse structure of $x,y$.

It is often the case that you can take $\mu(x,y)$ to be the total description length of $x,y$, so you might start by checking whether this works here. Another possibility is to take the sum of the total degrees of all monomials in $x,y$.

Finally, how should you approach the problem? I suggest forgetting about the formalism (in particular, ignoring POP completely) and writing out the simplification steps in their barest forms. Using $N(p,q)$ for the normal form of $p+q$ (themselves already in normal form), the rules are:

$N(c_1,c_2) = c_1+c_2$.
$N(c,x_i^jp+q) = x_i^jp+N(c,q)$.
$N(x_i^{j_1}p_1+q_1,x_i^{j_2}p_2+q_2) = x_i^{j_2}N(x_i^{j_1-j_2}p_1+0,p_2)+N(q_1,q_2)$, where $j_1 > j_2$.
$N(x_i^jp_1+q_1,x_i^jp_2+q_2) = x_i^jN(p_1,p_2)+N(q_1,q_2)$.
$N(x_{i_1}^{j_1}p_1+q_1,x_{i_2}^{j_2}p_2+q_2) = x_{i_1}^{j_1}p_1+N(q_1,x_{i_2}^{j_2}p_2+q_2)$, where $i_1 < i_2$.

Here we are conflating POP and POW, which makes things a littler more concrete.

We want to prove that these rules are correct, namely:

  If $p,q$ are in normal form then $N(p,q)$ terminates, is in normal form, and agrees as a function with $p+q$.

This can be split into several tasks. First, assuming that $p,q$ are in normal form, show that they match exactly one rule. Second, show that in each recursive invocation $N(r,s)$ on the right-hand side, (i) $\mu(r,s) < \mu(p,q)$, and (ii) $r,s$ are in normal form. Third, show that the right-hand side agrees with $p+q$ as a polynomials (using the inductive hypothesis). Fourth, show that the right-hand side is in normal form (again using the inductive hypothesis).

Proving that the addition procedure as given is valid is similar, only we need to take into account the different encoding which separates POW and POP.


Is a language regular Given a regular language $L$ (so there is an automaton $A$ which recognizes $L$), I need to determine whether $ L'$ is also regular, where $L'$ is given by
$$  L' = \{ \alpha \in \Sigma^* \mid (\exists \beta \in \Sigma^*)[ |\alpha| = 2 |\beta| \wedge  \alpha\beta \in L \}.$$
As far as I understand, I have to construct an automaton $A'$ that recognizes the language $L$.

I was thinking of making the automaton so it has two pointers, one pointing at the beginning states and one at the final states, and the automaton states are the cartesian product of the automaton states from $A$, and the left pointer is going to move 2 states to the right, and the right pointer 1 state to the left. Any suggestions?

(I think by pointers you mean the "pebbles" that are described in Kozen's Automata and Computability.)

The language $L'$ is regular.

You can prove that as follows: Consider the DFA $D_1 = (Q, \delta, F, q_0)$ for $L$. We will create another automata $D_2 = (Q \times Q \times Q \times \{0,1\}, \Delta_2, F_2, I)$.

$I = \{(q_0, q, q, 0) : q,q_0 \in Q\}$

$F = \{q, q_F, q, 0 : q_F \in F, q \in Q \}$

Let's first understand the intuition before defining the transition function $\Delta_2$:

We are constructing two layers: all the transitions in the first layer will be to some state in the second layer, and all those in the second layer will be toward the first layer.
On reading an alphabet when on a state of the form $(q_1, q_2,q_2, 0)$, the state in the first entry will change as per the transition function of $D_1$. The state in the second entry will also follow $D_1$, but it will be symbol agnostic, in the sense that it can change to any state irrespective of the symbol. The third entry will remain the same. (It is used to save the state at which we started the second pebble). The fourth entry will change from 0 to 1 which is equivalent to moving from one layer to another.
When on a state of the form $(q_1, q_2,q, 1)$, all the transitions are $\epsilon$ transitions and move us back to $(q_1, q_2',q_2, 0)$ where $q_2'$ is a state which is reachable from the state $q_2$ in $D_1$.

So in this automata, we first non-deterministically choose a start state of the form $(q_0, q, q,0)$. The state $q$ is the state from which we are reading $\beta$, and from $q_0$ we are reading the actual input $\alpha$. As the automata reads the word, for each letter of $\alpha$, we non-deterministically choose two letters for $\beta$ and run the same automata from that state in the second component. If on reading $\alpha$ we end up in the state we started reading $\beta$ (which is chosen non-deterministically), and the second component reaches a final state in $D_1$, then it means that the $\exists  \beta : \alpha \beta \in L$. And hence we accept.

Formally,
\begin{equation}
\Delta_2((q_1, q_2, q, 0),a) = \{(\delta_1(q_1, a), \delta(q_2, x), q, 1) : x \in \Sigma)\}\\
\Delta_2((q_1, q_2, q, 1),\epsilon) = \{(q_1, \delta(q_2, x), q, 0) : x \in \Sigma)\}
\end{equation}.

There is an easier way (as OP described):
Let $D_1'$ be the NFA obtained by reversing all the transitions in $D_1$ and allowing all symbols for each transitions (i.e., make it symbol agnostic). Take the states to be 3-tuples from $Q \times Q \times \{0,1\}$. Start from $(q_0, q_f, 0)$ where $q_f \in F$. On reading a letter, move from state $q_0$ as per $D_1$, and move two steps from $q_f$ according to the $D_1'$. The final states can be $(q,q,0)$ where $q\in Q$.

You can try figuring out why this works.


Scheduling distributed computational graph I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete.

The common way to improve simulation performance is to use a suitable distributed linear algebra library, a big computer with Infiniband, tweek some parameters and hope for the best.

Most of my simulations can be seen as many iterations of a single big "computational graph" of mul/div/add, without a single branch. It seems that finding a optimal scheduling for this computation could be seen as a optimization problem.

The absence of branch, the complete knowledge of the architecture (Memory hierarchy, number of functional units, communication interface...) and the fact that the same graph will be used many time make me think that some very aggressive optimization could be done ahead of time.

As some work been done in computer science to find a optimal scheduling for a "computational graph" and a given architecture?

The general problem of mapping a graph, where nodes are computational  operations and edges are transfers of data (i.e. dependencies), to computational resources is known as graph partitioning.

The general graph partitioning problem is NP-hard and therefore not directly solvable. However, there are good heuristic approaches. There are a number of open-source frameworks for graph partitioning, for example Metis, Scotch and Zoltan.


expected pairwise square euclidean distance between points How can I show that the expected pairwise square euclidean distance between points in $X$ is $Θ(d)$?

Where $X$ is a $(x_1,...x_n)$ of points generated uniformly at random in the unit, d is d-dimensional cube , $x=(x(1),...x(d))$ the generic point has its -th component $x(i)$ chosen uniformly at random in$ [0,1] $independently of other components and points.

$\Theta(d)$ represent the largest possible distance is d.

I try to reconduct this problem to Bertrand Paradox but i dont think is right. Maybe I that show that $E(||x−y||2)=Θ(d)$ , because is a hint but i dont know how.

i m following this path: https://stats.stackexchange.com/questions/22488/probability-that-uniformly-random-points-in-a-rectangle-have-euclidean-distance

but is different to my point.

Thanks.

Let $\vec{x},\vec{y}$ be two random $d$-dimensional vectors chosen uniformly and independently from $[0,1]^d$. That is, $x_1,\ldots,x_d,y_1,\ldots,y_d$ are all uniform random samples of the uniform distribution over $[0,1]$. Then
$$
\mathbb{E}[\|\vec{x}-\vec{y}\|^2] =
\mathbb{E}\left[\sum_{i=1}^d (x_i-y_i)^2\right] =
\sum_{i=1}^d \mathbb{E}[(x_i-y_i)]^2 =
d \operatorname*{\mathbb{E}}_{x,y \sim [0,1]} [(x-y)^2].
$$
Let $C = \mathbb{E}[(x-y)^2]$. Then the expected squared distance of two points in $[0,1]^d$ is $Cd$.

It is not hard to calculate $C$ explicitly:
$$
C = \mathbb{E}[((x-1/2) - (y-1/2))^2] =
\mathbb{E}[(x-1/2)^2] + 2\mathbb{E}[(x-1/2)(y-1/2)] + \mathbb{E}[(y-1/2)^2] = \\
2\mathbb{E}[(x-1/2)^2] + 2\mathbb{E}[x-1/2] \mathbb{E}[y-1/2] =
2\mathbb{E}[(x-1/2)^2] = \\ 2\int_0^1 (x-1/2)^2 \, dx = 2\int_0^1 x^2-x+\frac{1}{4} \, dx =
2\left(\frac{1}{3} - \frac{1}{2} + \frac{1}{4}\right) = \frac{1}{6}.
$$


What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale? Background:

The pool ball weighing problem is a classic CS question thrown at students, typically to demonstrate a binary search (alternative to ripping phonebooks in half).

Pool Ball Problem: Given $n$ pool balls where exactly 1 weighs more than the rest, find that pool ball using a scale.

The common approach is to split the balls into two groups, then weighing each group. You can narrow it down to one ball in roughly $\log_2(n)$ rounds. You can modify the algorithm to change the resulting base of the logarithm. This can be done by changing how many groups the scale can weigh. For example, if you had a scale that determined the heaviest of 4 groups (plus sign shaped on a pivot), then you would only need roughly $\log_4(n)$ rounds.

Problem: Consider the pool ball weighing problem but allow us to grow the number of groups we can split the set of pool balls into.

Instead of using a scale that compares a predetermined constant number, $k$, of pool ball groups, suppose we are allowed to vary and modify it during execution. For example, you are allowed to start with a split into 2 groups, then 3 groups next round, then 4, etc. It is not bounded apriori. Let's say that comparing $k$ groups takes $O(k)$ time. As a result, we know the heaviest of the $k$ groups or know if they weigh the same. If we grow the number of splits with each successive round, then we would require much fewer than $log(n)$ weigh-ins. There are divisibility issues that come up when doing the splits, but assume they are trivial to resolve.

$f(i) = \text{# of splits in $i^{\text{th}}$ round}$
(This is a positive, increasing function. We are required to spend the time/space to compute this.)

Let $t_f(i)$ be the time complexity of computing $f(i)$ given $\langle f(1), \dots, f(i-1)\rangle$ or subset of.

$N(i) = \begin{cases} n  & \text{if } i = 0 \\
\frac{N(i-1)}{f(i)} & \text{if } i \geq 1 \end{cases} = \text{# of pool balls after round $i$}$

We narrow our search down to one ball in $j$ rounds when:
$N(i) = 1 \geq \frac{n}{f(1)\cdot f(2)\cdot \dots \cdot f(j)}$

Or alternatively:

$\prod_{k=0}^{j}f(k) \geq n$ for some $j(n)$ dependent on $f$

Question: What can we say for the optimal time complexity of this algorithm? What are some properties of an optimal $f(i)$ we should expect? I realize this heavily depends on which models of computation we use (computing a fast growing $f$ can be expensive on some models while cheap on others). I'm willing to be reasonably flexible and not picky about it. Perhaps you guys could suggest a fruitful/interesting choice. For instance, the undergrad version of the problem trivializes the complexity by ignoring the complexity of grouping the balls together and probably considers $+, \times$ to take constant time.

The tricky part here is to pick a fast growing $f(i)$ that does not end up becoming too expensive to compute. The faster a chosen $f$ grows, the more that the time complexity decreases. On the flip side, the longer $f$ takes to compute, the longer the algorithm ends up running. We're looking for ways to balance these two.

Example:
I could simply increment the number of groups I split the pool balls into each round. Here, $f(i) = i + 1$. The total number of uses of the scale is $O(\Gamma^{-1}(n))$ (inverse factorial). The overall asymptotic time complexity is $(2+3+\dots+\Gamma^{-1}(n)) + \Gamma^{-1}(n) = O\left( \binom{\Gamma^{-1}(n)}{2} \right)$ (this takes into account the time complexity of handling the k-scale and incrementing the number of rounds each time). I'm assuming integer addition is a constant time operation.

The asymptotically optimal algorithm is to split in 2 groups at each step.  In other words, the ability to split into more than 2 groups does not allow us to find an asymptotically more efficient algorithm.

Suppose we split into $k$ at each step.  Then we get an algorithm whose running time is given by the following recurrence relation:

$$T(n) = T(n/k) + O(k).$$

We do $\lg(n)/\lg(k)$ recursive calls to reach the base case, so the solution to this recurrence relation is

$$T(n) = O(k \lg(n)/\lg(k)).$$

Now the function $f(k) = k / \lg(k)$ attains its minimum at $k=2$; for larger $k$, it is strictly increasing.  Therefore, the optimal choice of $k$, if we split by the same ratio at each level and disregard constant factors, is $k=2$.

Splitting by a different amount at each level doesn't help.  The above argument applies to all $n$, so it applies no matter the number of balls -- i.e., no matter what level we split at.

Here is another way to think about it.  Suppose we split into $k_1,k_2,k_3,\dots,k_m$ groups at each level ($k_1$ groups in the first call, $k_2$ in the second recursive call, and so on).  Let's count the number of bits of information we've gained.

How many bits of information do we get after applying the scale when we've split into $k$ groups?  $\lg k$ bits of information, since there were $k$ possibilities.  So, we get $b_i$ bits of information at the $i$th call, where $b_i= \lg k_i$.

Now we need a total of $\lg n$ bits of information to uniquely identify the ball.  Therefore, we need to select $b_1,\dots,b_m$ so that

$$b_1 + b_2 + \dots + b_m \ge \lg n.$$

What is the running time for any particular choice of $b_1,\dots,b_m$?  Well, in the $i$th call, we split into $k_i = 2^{b_i}$ groups, and the time to use the scale is $O(k_i)$, i.e., $O(2^{b_i})$.  Therefore, the total running time for a particular choice of $b_1,\dots,b_m$ is

$$O(2^{b_1} + 2^{b_2} + \dots + 2^{b_m}).$$

Now we want to find the optimal choice of $b_1,\dots,b_m$.  This requires us to minimize $2^{b_1} + + \dots + 2^{b_m}$ subject to the constraint that $b_1 + \dots + b_m \ge \lg n$.  One can compute that the minimum is attained for $b_1= \dots = b_m = 1$.

At the end of your post, you propose an algorithm that increments the number of splits at each step.  You didn't compute the asymptotic running time of your algorithm or compare it to binary search, but if carry through that analysis, it turns out that your algorithm is asymptotically slower than binary search.  Therefore, your proposed algorithm is worse than straightforward binary search.  It does not contradict any of the above analysis.

Details:   By Stirling's approximation, $\Gamma^{-1}(n) = O(\lg n)$ (roughly, ignoring log-log factors), so your proposed algorithm's running time is something like $O((\lg n)^2)$ (roughly, ignoring log-log factors), i.e., worse than binary search.


Sorting algorithm which sorts half the possible inputs in linear time Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time.
  (For the other half the algorithm can return anything, even a completely unsorted array.)

I know that using comparison model of sorting algorithms there is a lower bound of $\Omega(n \log n)$ so I try to make a proof by contradiction and to get to the fact that if such an algorithm exist then we can sort by comparison sort in linear time.

Suppose that a comparison-based sorting algorithm sorts the set of permutations $\Pi$ correctly. Construct the comparison decision tree underlying the algorithm, with permutations as leaves. Each permutation in $\Pi$ must appear as a leaf (why?), hence the tree must have depth at least $\log_2 |\Pi|$ (why?).


What CS Textbooks should I buy? I am preparing to graduate high school. Although I do not intend to study computer science in college, I feel like it might be useful to familiarize myself with the theoretical CS concepts taught in academia (eg. algorithms, structures, compilers). Can you recommend books that are either frequently used in current CS curricula or equate what one would learn in a CS curriculum?

Right now, I am planning on buying The C Programming Language, The Algorithm Design Manual, Algorithms + Data Structures = Programs, and Compilers: Principles, Techniques, and Tools.

For Computer Science, I would recommend you

  Computer Science: An Overview 11th J. G. Brookshear.

If you are more interested, you can attend one of the online courses, you can register for free and finish these courses online with exercises. I recommend you one of these:

An Introduction to Computer Science from Harvard, more informations you can find here EDX
Computer Science from Stanford, more info here

Algorithms, you can find relevant online courses following these books on EDX and Coursera as well. Depends on how much time you have and want to spend on these subjecs, and how deep you want to go.

  Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne

or

  Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein


Proving the equivalence of an LTL and a CTL formula For a lecture I am attending, we have to prove that

$$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \big(a \textsf{U} (b \land \square a)\big).$$

That is, we need to prove that for the CTL formula $\forall \big(a \textsf{U} (b \land \forall \square a)\big)$, the LTL formula $\big(a \textsf{U} (b \land \square a)\big)$ is equivalent to it. I know how I would go about trying to disprove it, that is, by providing a transition system that fulfils one but not the other, but I am at a complete loss about how to prove something like this.

Note that we use $\square$ instead of $\textsf{G}$.

Edit:

I managed to prove $$\big(a\textsf{U}(b\land\square a)
\big) \equiv \square a \land \lozenge b$$ if that's any help.

First, it is important to understand what the statement

$$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \big(a \textsf{U} (b \land \square a)\big)$$

means. Hear LTL is interpreted over a transition system, and the semantics then is that all paths of the system satisfy the LTL formula. This is tightly connected to the CTL operator $\forall$.

Lets use the equivalence you have shown and prove
$$\forall \big(a \textsf{U} (b \land \forall \square a)\big) \equiv \square a \land \lozenge b$$

To prove the statement, first take a transition system $\mathcal{T}$ that satisfies $\forall \big(a \textsf{U} (b \land \forall \square a)\big)$ and show that it satisfies $\square a \land \lozenge b$.
Take arbitrary path $p$ of $\mathcal{T}$.
By the CTL semantics you know that $p$ satisfies the path formula $\big(a \textsf{U} (b \land \forall \square a)\big)$.
It will have a prefix labeled by $a$ and the state $s$ at the end of this prefix will satisfy the state formula $b \land \square a$. Thus all possible paths starting in $s$ are globally labeled by $a$. In particular, the suffix of the part $p$ we are considering will be labeled by $a$ globally. Also the state $s$ is labeled by $b$. Thus we can conclude that the path $p$ satisfies $\square a \land \lozenge b$.

The other direction is similar. Assume that all paths of $\mathcal{T}$ satisfy $\square a \land \lozenge b$ and show for arbitrary path $p$ of $\mathcal{T}$ that it satisfies $a \textsf{U}(b \land \forall \square a)$. It will be labeled by $b$ at some point, and as all paths of $\mathcal{T}$ are labeled by $a$ globally, in particular all suffixes of $p$ are. So the state on the path $p$ that is labeled by $b$ satisfies the state formula $b \land \forall \square a$.

There is an interesting result connected to your question:
let $\varphi$ be a CTL formula. If the property $\varphi$ is definable by an LTL formula (i.e. there exists an LTL formula $\psi$ such that $\varphi \equiv \psi$), then the LTL formula you get by simply deleting all path quantifiers in $\varphi$ is equivalent to $\psi$.
See the discussion in Equivalence preserving operator from CTL* to LTL.


Tools for modelling compilers I'm a wannabe mathematician, whose master's thesis is (by the looks of it) going to focus on a certain "compiler", used to produce learning materials from a subset of $\LaTeX$, in the context of mathematics education. I'm of course going to have to talk about the compilation process in general, and was planning to discuss the mathematical abstractions related to it (this being a master's thesis in mathematics), and then use those to describe the compiler.

I have no experience in the field whatsoever, however, and was wondering whether the concepts of regular expressions and languages, automata and the like are actually used to model (and|or) describe the functionality of compilers in a professional setting. Is it typical (even in the industry) to use these methods of modelling compilers, or are there better alternatives available?

I simply stumbled upon these basic concepts in a certain course handout, and they seem useful, but I want to be certain.

Be careful. Even mastering the tools for compiler construction, handling a very complex preexisting language (which LaTeX certainly is) is an arduous task. Add that there is no firm syntax for LaTeX (there are certain overall conventions, but lots of special cases) makes it worse.

But to really be of any guidance, we'd need a whole lot further detail: What kind of documents? Can you define the format, or is it a corpus of preexisting texts? Do they use the same packages? Are they written to some rigid format or "anything goes? What do you want to extract? (If it is e.g. all the "exercise" environments it is very simple ---but the contents will depend on all sorts of external definitions, finding/including that isn't simple. Solution is to require manual fixups, but that negates the "automation" aspect).

Go also to TeX.SE for LaTeX related questions.

Good luck!


Perfect matching in a graph and complete matching in bipartite graph When I google for complete matching, first link points to perfect matching on wolfram.

It defines perfect matching as follows:

  A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching.  A perfect matching is therefore a matching containing $n/2$ edges (the largest possible), meaning perfect matchings are only possible on graphs with an even number of vertices.

However below graph contains even number of vertices (10 vertices), but still I cant guess the perfect matching - in which every vertex of of the graph is incident to exactly one edge. One of the matching can be $\{E_1,E_4,E_6\}$. However not every vertex (here, $\{V_5,V_6,V_9,V_{10}\}$) is incident to exactly one edge in this matching as required by above definition. So this is not definitely a perfect matching as desired by wolfram's definition. Also I cannot add any other edge to this matching as it will make two edges to share a vertex.

Q1. Is perfect matching possible with this graph?

I am also reading the same topic from the book by Narsingh Deo. It defines the complete matching in the context of bipartite graph:

  In a bipartite graph having a vertex partition $V_1$ and $V_2$ a complete matching of vertices in set $V_1$ into those in $V_2$ is a matching in which there is one edge incident with every vertex in $V_1$. In other words, every vertex in $V_1$ is matched against some vertex in $V_2$.

I am not able to understand if these two (wolfram's and book's) definitions point to two different concepts or they are one and same.

By my understanding, according to Deo's definition, $V_2$ may contain more vertices than that in $V_1$, thus the size matching may be less than $n/2$. However, wolfram says perfect matching contains $n/2$ edges. For example in above graph the complete matching of vertices in set $P_1$ into those in $P_2$ can be $\{E_1,E_4,E_6\}$ as one edge in this matching is incident with every vertex in $P_1$.

Q2. So the two definitions (wolfram's and book's) must be different concepts. Am I correct?

These are two different concepts. A perfect matching is a matching involving all the vertices. A bipartite perfect matching (especially in the context of Hall's theorem) is a matching in a bipartite graph which involves completely one of the bipartitions. If the bipartite graph is balanced – both bipartitions have the same number of vertices – then the concepts coincide.

The term bipartite perfect matching is not standard – in fact I just made it up. Usually perfect matching just means a matching involving all the vertices.


Good introduction to Turing's work and complexity theory? I'm currently an undergrad whose been amazed by what Turing has done for the world. I know there are plenty of other amazing individuals, but Turing's work specifically has always sounded the most interesting to me and I'm finally at the point where I can understand some of it. So my question is, where do I really begin to dive into his work? I have yet to take an official theory course, but I'm determined enough to go through important works that will help me get where I need. I'm currently reading his 1936 thesis and I find it mostly understandable, but I want to go deeper into the mathematics behind it all.

On a similar note, I think what I overall am interested in is complexity theory. I have some experience with basic abstract algebra, and some mathematical maturity. Can anyone list some books/papers to read, some introductions and some deeper, that can help me fully understand the implications of some topics, i.e. P=NP? How T.M.s were and are currently being used as foundational tools to prove and disprove ideas? I realize these are vague questions, but I want people to suggest books/papers that have been most influential to them that are related to these topics (or any other influential reads that one might have).

If I said anything incorrectly please feel free to correct me!

Some popular books are Computational Complexity by Papadimitriou and Introduction to the Theory of Computation by Sipser. If you are very ambitious, you can also try Computational Complexity: A Modern Approach by Arora and Barak, which is an advanced textbook.

I would recommend against the historical approach of reading old papers. While some old papers are a good read (some of Turing's papers, Shannon's 1948 paper), old papers tend not to follow modern conventions, have a somewhat different focus, are less streamlined than modern treatments, could contain weaker results, and (in some cases) wrong results or at least wrong proofs. A good textbook is much preferable.

Regarding Turing machines, while they have some theoretical advantages in some circumstances, they are poor models of actual computers. Indeed, even in the theoretical computer science community, algorithms are usually described in the so-called RAM machine model which conforms much more closely to actual computers. Even historically speaking, Turing's model wasn't the first universal computation model, though (if I remember correctly) it was the first one that Gödel found convincing (Gödel's own general recursive functions, for example, predates it).

On your way to complexity theory, don't forget to stop at recursion theory (sometimes called computability theory), which had been practiced for a few decades before modern complexity theory started in the early 1970s. The usual course sequence indeed starts at (very basic) recursion theory and progresses to complexity theory.


How to estimate the computational cost in a neural network? Given a neural network(assuming no regularisation/dropout), I want to determine the computational cost of doing a forward and a backward pass of a datapoint. I want the measure to be of independent of the programming language/operating system involved. I can think of it as a graph model, with some activations applied on nodes, then I think it can be estimated by hand.
Also is there any online tool/package which would do the estimate if I input the neural network ?
I am new to computer science, so probably it is a very naive question to most of the users, I am offering my apologies it is so.

It takes $O(n)$ time, where $n$ is the size of the neural network (e.g., number of nodes plus number of connections; in a graph model, number of vertices plus number of edges).


Complete resolution rule for 1-in-k SAT In CNF SAT, each clause (A or B or C or...) must contain at least one true literal. The resolution rule applies to pair of clauses who have exactly one opposite literal.

(A or B or C) and (!A or D or E) => (B or C or D or E)

I say that this rule is complete, in the sense that if a formula is unsatisfiable, I can prove it by applying the rule exhaustively (on hard instances, an exponential amount of times) until one empty clause is produced. If a formula has a unique solution, I can apply the rule until every unit clause is produced.

1-in-k SAT is a NP-complete variant where exactly one variable per clause (A,B,C,....)=1 is true. Given a pair of clause with one opposite literal, and no common literal, I can also produce a third one:

(A,B,C)=1 and (!A,D,E)=1 => (B,C,D,E)=1

Question: Is this rule complete for unsatisfiable and uniquely satisfiable 1-in-k formulas?

You're treating resolution as if it were a purely syntactic rule.  It works that way with traditional CNF clauses because that corresponds with the underlying rule of inference.  But a CNF clause with the added restriction of only one literal allowed to be true no longer corresponds to what the resolution rule can be validly applied to.

The Boolean expression $(a \lor b) \land (\lnot{a} \lor \lnot{b}) \land (\lnot{a} \lor b)$ is unsatisfiable as a 1-in-k-SAT formula but naively applying the resolution rule produces $a = false, b = true$ as a (wrong) solution.