Total functional programming language without an static type checker All papers with the subject of total functional programming make use of some kind of static type checking to ensure totality. This make sense considering hoy easily is to make a language Turing-complete. The question is: Is there any untyped/dynamically-typed formalism that ensures total functions?

Edit

In other words, there exist any formalism that only allows to construct total functions, with the impossibility of construction of partial functions, so there is no need of a filtering stage like a type checker or a termination analysis?

The question is, how do you eliminate terms that run forever:

In particular, things like $(\lambda x \ldotp x\ x)(\lambda x \ldotp x\ x)$ and the Y combinator must NOT be in your language, since they can be used to construct computations that do not halt.

Static typing in things like System F eliminates these: they start with a full lambda calculus, and then filter out ill-typed terms.

But, do do this in an untyped setting, you need to eliminate these terms by construction. They cannot be expressible in your language.

I can think of some silly ways to do this, like the language of imperative programs with no functions or and only loops over lists. But in general, as soon as you have higher order functions, these problematic constructs are constructible. So while I won't say that it's impossible, it's probably very difficult to do in a way that makes much sense.

It's possible for you to statically filter out these things with something that isn't a type system, with termination checkers, but these will always throw false positives, and while they aren't static typing, they are still very much a static filter on your programs.

Note that, depending on what you consider "dynamically typed," you could eliminate programs like this by keeping track of types using inference, but only throwing errors at runtime. Thus something like the Y combinator is still rejected, just later. This is dynamically typed, but probably not what you are looking for.


What's the time complexity of this function? Consider the below function:

Considering that print(a) and swap(a, b) are of complexity $\theta(1)$, what is the time complexity of the above code?
The answer that comes to my mind is $\theta((n-k)!)$ or $\mathcal{O}(n!)$.
However in the book that I'm reading it says it's of order $\theta(n!)$. What am I missing here?

Denote the time complexity of $f$ on inputs $a,k,n$ by $T(k,n)$ (the time complexity doesn't depend on $a$ in your model). The time complexity satisfies the recurrence
$$
T(k,n) = (n-k+1)T(k+1,n) + \Theta(n-k+1).
$$
with base case $T(n,n) = \Theta(1)$. Define
$$
S(k,n) = \frac{T(k,n)}{(n-k+1)!}.
$$
Then $S(n,n) = \Theta(1)$ and for $k < n$,
$$
S(k,n) = S(k+1,n) + \Theta\left(\frac{1}{(n-k)!}\right).
$$
It follows that
$$
S(k,n) = \Theta\left(\frac{1}{(n-k)!} + \cdots + \frac{1}{1!} + 1\right) = \Theta(1),
$$
and so $T(k,n) = \Theta((n-k+1)!)$.
If you take $T(n) = \max_{1 \leq k \leq n} T(k,n)$, then indeed $T(n) = \Theta(n!)$.


GCD Strongly Polynomial Time I don't understand why GCD is not Strongly Polynomial Time?

Can you explain in an example, why the storage size cannot be Polynomial Bounded?

So is GCD in the Complexity Class P?

The GCD can be computed in polynomial time. Strongly Polynomial is a much more restrictive classification. Taking the definition from here:

  An algorithm runs in strongly polynomial time if

  the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input
  instance; and
  the space used by the algorithm is bounded by a polynomial in the size of the input.

The input to GCD is two integers. Thus, in order to be solvable in strongly polynomial time, GCD would need to be solvable with a constant number of aritmethic operations since the input size is constant.


Are programming languages ultimately procedural? I'm studying a declarative programming language (Prolog) and in thinking about how certain things are programmed at a low level, a question came to me:

are programming languages ultimately procedural ?

I imagine that by "procedural" you mean languages whose statements refer to changes of state in one ore more objects, but these references are implicit, not explicit (they follow a fixed pattern, for instance, the state change made by the execution of a statement is delivered to the next, resembling a procedure).

You may be referring to the fact that our computers, at a low level of abstraction, are usually state machines - so to speak - so all programming languages would have to be procedural languages disguised as something else.

This has happened for technical and economical reasons, it's not a theoretical imperative. It doesn't have to be that way. Inside your head there is a computational device that isn't like that, and we've been experimenting with all kinds of different models for low level implementation of general-purpose computers for decades. It is not unlikely that, at some point, one of these alternative models becomes commercially viable.


What does it mean that a core supports 2 threads? I understand that a process may have multiple threads, and that a processor may have multiple cores to run processes in parallel.

But I can't understand how a core may allow multiple threads, what does it change from a core with one thread support?

See Wikipedia on Computer Multitasking and Time-sharing, which have an explanation of how operating systems allow this.  Basically, they switch between multiple threads.

Read also about hardware multithreading.  This allows a single core to execute multiple threads concurrently, without switching between them.


Sum of zero nim sum series The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\binom{n-k-\sum\limits_{i=0}^kx_i}k$$ in $O(nk·\log n)$ time, where $⊕$ is exclusive or.

Let $\sum_{i=0}^{k}x_i=S$.
The straightforward method is enumerating $S$ from $0$ to $n-2k$, and using dynamic programming to count nonnegative solutions to $\begin{cases}&x_0 ⊕x_1⊕\cdots⊕x_k=0 \\&\sum_{i=0}^{k}x_i=S \end{cases}$ (this is the number of winning positions for the first player of a Nim with $k$ piles and a total of $S$ stones, allowing empty piles). But it runs in $O(n^3 k)$ which is too large.

I think there may be some other dynamic programming technique to solve it, but cannot work out that. Any thoughts are welcome.

I finally figure out an answer. This paper "Nim Fractals" by Tanya Khovanova and Joshua Xiong gives a formula to count the solutions to $$\begin{cases} x_0 \oplus \cdots \oplus x_k =0 \\\sum_{i=0}^{k}x_i=S\end{cases}$$ in $O(kS)$. Denote the number as $f(k,S)$. We may utilize $f$ to see that the problem reduces to $\sum_{S=0}^{n-2k}\binom{n-k-S}{k}f(k,S)$. The overall complexity is $O(nk\cdot log(n))$.


How to relate circuit size to the running time of Turing machine From http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/,

  Define, $M_{[x,c]}$ as the deterministic Turing machine that operates
  as follows on an input $y$. The machine treats $x$ as a deterministic
  program, and simulates $x$ on input $y$. At the same time the machine
  runs a counter that stops its execution after steps $|y|^c$. If the
  machine accepts before the counter stops, then it accepts; otherwise,
  it rejects.

  Let $f(i,c)$ be the smallest natural number so that $M_{[i,c]}$makes a
  mistake on the input $y$. Then, if $P \neq NP$ is true, the function
  $f(i,c)$ is always defined.

  Theorem: Suppose that there are infinite number of $i$ for which there exists a $c$ so that $$f(i,c) > 2^{2^{|i|+c}}$$ Then, for infinitely many $n$, SAT has circuit size $n^{O(\log n)}$.

  Proof: Let $i>1$ and $c$ be so that $$f(i,c) > 2^{2^{|i|+c}}$$ Define
  $n = 2^{|i|+c-1}$. Note, that $c$ is at most $\log n$. Then,
  $M_{[i,c]}$ on all $y$ of length $n$ is correct, since $y \leq 2^n = 2^{2^{|i|+c-1}} < f(i,c)$.
  The size of the circuit that simulates this Turing machine on inputs
  of length $n$ is polynomial in $|i|$, $n$, and the running time of the
  machine. The machine, by definition, runs in time $|y|^c \leq n^c \leq n^{\log n}$

I am not getting this part. Can anyone explain this (to specify, “The size of the circuit that simulates this Turing machine on inputs of length $n$ is polynomial in $|i|$, $n$, and the running time of the machine” in the quote)? (So the question is how can we relate the running time of Turing machine to the size of the circuit.)

The way to show that circuits are equivalent to TMs is as follows: for a TM, you encode it in binary (i.e states, transitions, etc.)

Then, you construct a circuit whose gates represent the transitions between each configuration of the TM. Since configuration transitions are local, then you only need local gates (i.e gates that depend on a constant number of inputs).

The idea is that you can compute configuration $c_i$ from configuration $c_{i-1}$ by examining the contents of 3 adjacent cells, and if the head of the machine is there, update them accordingly. It's rather technical to write formally, but it's a generally simple proof (See "Computational complexity" by Arora and Barak for a proof).

Using this proof, you see that the size of the circuit is polynomial in the running time of the machine and the input length, because the circuit is constructed in "levels", where each level corresponds to a configuration of the TM.


Reconstructing a screen of permuted pixels Reconstructing a screen of permuted pixels

Summary

Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture?

Let:

$n=w\times h$ pixels.
$m=\text{number of frames}$

Details

You are given an LCD screen with $n = w \times h$ pixels, that has been altered so that the pixel locations are permuted, once, in some random manner.
Watching a video on this LCD screen would obviously result in quite a garbled picture.
The permutation is mapped by some unknown function, we shall call $\text{permute}\left(x_0,y_0\right) \implies (x,y)$
Each pixel on the screen has some permuted coordinate $(x,y)$ and some unknown original coordinate $(x_0,y_0)$ (such that $\text{permute}\left(x_0,y_0\right)=(x,y)$).
You (and your computer) are given to watch a particular video of an average film (movie) of average length, with $m$ frames, and having the same resolution as the LCD screen; however for simplicity, assume the video will be in grayscale (for example, each pixel is a single color in the range $[0,256)$).
You do not know *which* film is being played.
You (and your computer) can rewatch the garbled film as many times as you like.
As a frame of reference, you are also informed which pixel is the lowest location in the original non-permuted screen (i.e you are given the values $x$ and $y$, such that $(x_0,y_0) =(0,0)$, and $\text{permute}\left(0,0\right)=(x,y)$).

Goal

Algorithm to (efficiently) compute the mapping of the pixels to their original locations.
Can this be done in $o\left(n^2\right)$ space (i.e in better than $\mathcal O\left(n^2\right)$ space?)
Can this be done in $o\left(n^2f(m)\right)$ time?

I'm not sure how to ask this question correctly, but I am mostly wondering about reducing the $n^2$ factor.

Is this a known problem, or similar to any known problems?

PS. What about same question but for the case of binary images for each frame instead of grayscale.

Appendix

Figure 1 Example permuted "LCD screen", side view

Figure 2 Example permuted "LCD screen", front view

Figure 3 Example video frame (color)

Figure 4 Example permuted video frame (color)

Figure 5 Example video frame (grayscale)

Figure 6 Example permuted video frame (grayscale)

Figure 7 Example video frame (binary, using most-significant-bitplane)

Figure 8 Example permuted video frame (binary)

Related source codes are on gist.github.com

Credits:

Images courtesy of NASA (NASA GoPro footage from EVA 30).
More info on archive.org.
Licensed under the Creative Commons Public Domain Mark 1.0 license)

One approach is to exploit fact that if two pixels are adjacent, then their intensities will be highly correlated: the intensity of the first pixel (as a time series) will be highly correlated to the intensity of the second pixel (as a time series).

In other words, let $I(p,t)$ denote the intensity of pixel $p$ at time $t$.  Then you can compute a correlation coefficient between $p,q$ as

$$C(p,q) = \sum_t I(p,t) I(q,t).$$

(Detail: you probably actually want to use the normalized correlation coefficient, as explained at bottom.)

For each pair of pixels $p,q$, compute $C(p,q)$, the correlation between these two pixels.

Next, for each pixel $p$, you could identify the four other pixels $p_1,\dots,p_4$ that have the highest correlation to $p$ (i.e., that maximize $C(p,p_i)$).  A reasonable heuristic would be to assume that those are the four neighbors of $p$.  Do this for every pixel.

Now you have a pretty good guess at which pairs of pixels are adjacent.  At this point, you several options.  One approach would be to pick a random pixel, then start trying to expand outward from there: find its four neighbors, then find their neighbors, and so on.

At each step you will need to decide how to orient the neighbors.  Here a plausible heuristic might be: the distance between two pixels $p,q$ in the original image is likely to be related to the correlation $C(p,q)$: larger $C(p,q)$ is associated with pixels that are further apart.  Thus, given a pixel $p$ and its four neighbors $p_1,p_2,p_3,p_4$, I expect you can tell which pairs of those neighbors are on opposite sides of $p$ vs which pairs are kitty-corner to each other (as opposite pixels are at distance 2 apart while kitty-corner pixels are at distance 2).  You probably won't be able to tell which is up and which is right, so just make an arbitrary guess; later you can have a human tell you whether the picture appears to be reflected.

So now suppose that you've mapped some pixels to their original locations, and you want to add one more to the set.  You can get at most three candidates for what it might be, then use the distance heuristic to form a guess about which of the three this is.

Continue this process until you've mapped out a guess at how to reconstruct a large patch of the original image.  Now have a human look at the unpermuted video (unscrambled using your guess at the mapping for those pixels).  If you're lucky, most of that will be correct.  A human should be able to tell you whether this looks correct, and identify the region that appears to be correct.

So, you have a process that given a starting pixel, finds a region surrounding it that appears to have been correctly unscrambled.  Repeat from multiple starting pixels until you have a large collection of such regions.  Now fitting those regions together is basically just a jigsaw puzzle, so should be solvable.

I would expect that the longer the image is, the more effective this will be -- the fewer mistakes this approach will make, and the larger these regions will be and the easier the jigsaw reconstruction process will be.

But the only way to find out for sure is to test this.  Ultimately, this is probably not a question that can be answered by proving a theorem, as the effectiveness of the technique depends on empirical facts about the properties of typical videos.

Footnote: In computer vision applications, it is usually more effective to use the normalized correlation coefficient (NCC).  So, I recommend that you use NCC for this.  The NCC is essentially

$$C(p,q) = \sum_t {(I(p,t) - \mu(p)) (I(q,t) - \mu(q) \over \sigma(p) \sigma(q)},$$

where

$$\begin{align*}
\mu(p) &= {1 \over m} \sum_t I(p,t)\\
\sigma(p) &= {1 \over m-1} \sum_t (I(p,t) - \mu(p))^2
\end{align*}$$

What's the running time of this approach?  The most expensive part is to compute the correlation between every pair of pixels.  Naively, this takes $O(n^2 m)$ time.

However, if computation time is at a premium, it might be possible to speed that up using locality-sensitive hashing or K-D trees to find pairs of pixels for which $C(p,q)$ is larger than some threshold.

If you're looking for research literature on this problem, I would look into video descrambling.  Some video scrambling methods (e.g., for copy protection or cheap video "encryption") permute the pixels, basically along the lines you outlined.  I think there might be work in the research literature on descrambling such videos; a literature search might turn up something useful.


Assuming that P=NP - Finding an optimal algorithm for 3SAT Let assume that P=NP so we have both search and decision algorithms for 3SAT at polynomial time.
Can you help me to find an optimal algorithm for optimize 3SAT, i.e.: to find the maximum number of clauses in $\varphi$ that can be satisfied.

Thank you!

P.S.
You can assume that you have search and decision algorithms for 3SAT at polynomial time - so you can use them...

The following language is in NP (why?):
$$
\{ (\phi,k) : \text{$\phi$ is a CNF and there is an assignment satisfying at least $k$ clauses of $\phi$} \}.
$$
I’ll let you finish the proof.


Integer programming with indicators I have the following question, and I need to write it as an integer programming problem:
A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different suppliers:

Every present costs 110\$. For any present above 500, the manager would have to pay 5\$ extra for insurance (for example, for 502 presents, there will be 10\$ extra for insurance).
Every present costs 120$. For any present above 300, there is a discount of 30% (each present above 300 costs 84\$).

I need to find how many presents he should buy from each supplier, in order to spend the minimal amount of money.
I defined:
$x_1, x_2$ - The number of presents to buy from each supplier.
$z_1$ - Indicator which represents whether or not $x_1 \ge501$
$z_2$ - Indicator which represents whether or not $x_2 \ge301$
I know how to represents the indicators using linear functions, but I don't know how to find a linear objective function.
My best suggestion is:
$$ 110x_1+5z_1(x_1-500)+120x_2-36z_2(x_2-300) $$
However, this is not a linear function, because I multiply the decision variables.
How can I turn it into a linear function?

You can multiply variables in ILP with https://blog.adamfurmanek.pl/2015/08/29/ilp-part-2/ and https://blog.adamfurmanek.pl/2015/09/26/ilp-part-6/ and https://blog.adamfurmanek.pl/2015/10/03/ilp-part-7/
You don't need multiplication, though. Your objective function is effectively:
$
\min(500, x_1) \cdot 110 + \max(x_1 - 500, 0) \cdot 115 + \min(300, x_2) \cdot 120 + \max(x_2 - 300, 0) \cdot 84
$
You can represent max/min functions as comparison + absolute value, as explained in https://blog.adamfurmanek.pl/2015/09/19/ilp-part-5/


Resolving many to many relationships? I'm trying to separate a weird relationship. It goes like this:

One waiter can serve more than one kind of drink and one kind of drink can be served by more than one waiter.
One waiter can wear more than one kind of shirt (eg different uniforms daily, or random uniform assignments, etc), and one kind of shirt can be worn by more than one waiter.

There are two many-to-many relationships here that share the waiters, but can be separately resolved. But because they share the waiters entity, then many kinds of drinks can be served while wearing many kinds of shirts.

The relational model looks like this:

My question is, how do I resolve this? It doesn't look like it lends itself easily to being decomposed into one-to-many relationships.

Edit: I changed the image to fit in better with the description, but the problem that results here is the waiter-drinks and waiter-shirt entities still exist as a result of normalizing the drinks and waiters relationship (that is many-to many) and the waiter and shirt (also many-to-many). The resulting entities then have a many-to-many relationship as waiter-drinks and waiter-shirt.

Where am I wrong?

If i rightly assume that you are trying to convert the E-R diagrams to relations (tables), then the procedure to convert a many-to-many relationship into relations is to create one more table, apart from the 2 tables that you will create for the 2 entities (waiter-drinks and waiter-shirt). This new table created for the relationship will have its attributes (columns) as the PKey of the constituting entities. In your case, this table will contain 3 attributes; namely waiter_number, drink_number and shirt_number.

Had you been working on a one-to-one or one-to-many relationship, you would augment one more column to the table on many sides instead of creating another relation.


Express a number with a combination of arithmetic operations and a single number Today I ran into a this relatively simple (At least from my perspective ) problem. Basically the task is to be able to express any number using only a single number an any combination of arithmetic operations, square roots, exponentiation or factorials. To further elaborate I will make an example.

The input of the program would be a number 57 and a 8. The solution would be expressing the number 57 using only 8s and any of the defined operations.

In this case the number 57 could be expressed as
57 = (8+8+8+8+8+8+8)+8/8
Alternatively if we had the number
25 and 3 as an input, we could also do
25 = 3^3 - 3/3 - 3/3

The task is to define the input number with a similar method mentioned above, using the least amount of operations.

The person who created this problem defined it as difficult and no matter how hard I think about it, I just can not find a reason why. In most cases the problem will spin around simple integer factorization and in special cases, using factorials (With big numbers) or exponentiation will yield a less lengthy result.

What I am asking for is if there is any better, more efficient method to solve this problem and whether I am missing something obvious which would make this problem look as "Difficult" as it was defined.

Thanks for the answers in advance.

If you have any number at all, say $N$, then you can write it as $\frac 8 8$ followed by $N-1$ occurrences of $+\frac 8 8$.

The difficulty of the problem lies in finding short sequences of 8s that will work. The best known way is to enumerate all the possibilities.

For instance, with six 8s, write them out in a row and then insert operators between them and after them, to generate all valid reverse-Polish notation expressions which lead to a single result.

As well as the usual arithmetic operators, include a “concatenate” one which, immediately following two 8s, produces 88.

Enumerating all conceivable RPN strings is not hard: there can only ever be five dyadic operators. Filtering them to select just the valid ones is not hard either: probably the best way is to include that process in the process of evaluating each one.


Why is this problem listed as "Dynamic Programming" I found a problem in the dynamic programming section of hackerrank but its not clear why dynamic programming should be used to solve it. The problem is as follows:

  Nikita just came up with a new array game. The rules are as follows:
   Initially, there is an array, , containing integers.
  In each move, Nikita must partition the array into non-empty parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets point; otherwise, the game ends.
  After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array .
  Nikita loves this game and wants your help getting the best score possible. Given , can you find and print the maximum number of points she can score?

In going over the algorithm that would be used to solve the problem, it seemed evident to me that you could simply write a recursive function where each recursive call would be made iff the sums of the elements in both halves of the array are equal. Otherwise, the game (the algorithm) ends. Since you would, in the worst case (running time wise), be dividing the array log(n) times where n is the array length, you would get a running time of O(logn).

The only thing that I could see dynamic programming helping with here may be the recalculation of the sums which I guess could be avoided by calculating the sums from the bottom up but I'm not really seeing an optimal substructure here. Also, you would be increasing the space complexity seemingly unnecessarily.

So why/how is dynamic programming being used here?

How do you choose which partition is best (there could be several partitions if you allow negative numbers or zeroes), and which side of the partition to choose? You have to examine all partitions and both sides of each partition, and then choose the best one. Naively, the complexity of this algorithm is exponential. With dynamic programming you can find the solution in polynomial time – I'll let you figure out how.


Convert a polygon mesh into a b-spline surface $\textbf{Problem:}$

Getting a $\textit{polygon-mesh}$ as input, I have to construct a surface that looks exactly to the given input. My task is to generate a $\textit{b-spline}$ surface that exactly looks like the connected polygon mesh. It is obvious that my $\textit{b-spline}$ surface has to have a degree of one in both directions $\textit{u}$ and $\textit{v}$.

$\textbf{Output:}$

As an output for my solution. I have to generate a matrix of $\textit{control point}$ that represent that generated surface.

One property of this matrix is that each elements of each row and column are connected with each others.
If our control points matrix is a $ n \times m$ matrix, then let $C_i$ a column of this matrix with $C_i = <e_{1i}, e_{2i}, \dots, e_{mi}>$ then there must exist path in the polygon from $e_{1i}$ to $e_{mi}$.

One thing to consider if there is no edge between  $e_{ji}$ to $e_{(j+1)i}$, we can construct one as long as this edge lies inside the polygon.

$\textbf{my trivial idea}$

Assuming that the polygon has $n$ nodes. I create $n$ other nodes inside the polygon near each original node. I create then a $2 \times n$ matrix. The first row contains all the points constructing the polygon. Second row contains the corresponding additional inserted node. In order to connect two additional inserted nodes, i have to make sure that the line between two nodes is kept inside the polygon.

This idea works only for simple structure and the complexer is the polygon the hard to find these additional points.

Any good solutions maybe ?.

Without any assumptions on the input mesh, you cannot in general get a single b-spline surface that replicates an arbitrary polygon mesh. You would need the mesh to be connected, but you would also need some fairly significant assumptions about the mesh topology. At the very least, you would want the input mesh to be manifold. (It might be possible to contrive a method for creating a single b-spline that exactly matches an arbitrary polygon mesh except on a set of measure zero, but in many cases the spline would have to be extremely degenerate and overlap with itself in strange ways.)

On the other hand, if you are allowed to use multiple disconnected b-spline surfaces in the output, then the problem is easy.

A degree-1 b-spline surface with a 2x2 control point matrix and no internal knots is just a quadrilateral with bilinear interpolation in the interior. In particular, if you set two adjacent control points to the same location in 3D space, you get a triangle. (c.f. Bézier triangle)

Any polygon mesh can be subdivided into a triangle mesh through well-known methods. Once you have done that, you can just separately convert each triangle into a 2x2 b-spline surface.


Speed of a microprocessor I was just wondering why are are new generation microprocessors faster at the same clock speed as the old ones.
For instance a 2.66Ghz dual core i5 is faster than the a device with clock speed of 2.66Ghz but core 2 dual.

If executing each instruction took a single clock-cycle, then your confusion would have been understandable, as a higher clock frequency would imply shorter cycle time, hence, more instructions per unit time.
However, the reality is quite different. Modern CPUs are usually pipelined, meaning that a single instruction takes multiple number or core-clocks, and that multiple instructions are executed simultaneously at the same time (each occupies different parts of the CPU pipeline). Complex instructions, such as calling a function or "jumping" to a different part of the code interfere with this pipeline and cause the CPU to temporarily halt its execution until the offensive instruction completes (known as a pipeline stall).
The picture is even more complex. Recent processors have multiple pipelines running on the same "core" (say, one clock advances pipeline 1 while the next clock advances pipeline 2). Of course, sometimes the program running on one pipeline affects (stalls) the progress of the other pipeline. This is "multithreading". Other approaches to make the CPU perform better are superscalar processing and other paralleling approaches.
As you can figure out, the number of instruction a CPU performs at any time unit is very complex to compute or even estimate, and is affected by the clock frequency, but also by the architecture of the CPU as well as by the program itself (e.g., how many "jumps" instructions it contains, or how well it parallelizes). All of these together determine the "speed" of the CPU, which is measured in the (average) number of instructions it can perform in a second, known as IPS. As said, the clock frequency is only one factor to the IPS, but in modern CPUs the specific architecture (rather than small differences in their clock frequency) dominates the IPS.


How is $ n^{log(n)} > n^c $ always for any c? I was going through the questions in MIT quiz : Question 2 g
and I found this

How is  $ n^{log(n)} > n^c $ always for any c ?

what if c > log(n) ?

In these exercises, you are asked to compare functions only according to their asymptotic behavior.

In this case, $c$ is a constant function of $n$, while $\log(n)$ is a function of $n$ that approaches $+\infty$ when $n$ becomes large.

So, $c > \log(n)$ can only hold for finitely many values of $n$.


What is more important in an algorithm, small runtime or small memory usage? I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same type). The size on which are based the complexities is $n$.

In the fist one, the server has to send only one object and the client has to perform $n$ operations.
In the second one, the server has to send $\log n$ objects and the client has to perform $\log n$ operations.

What is the best algorithm ? Does it depend on the environment of execution ?

The best algorithm must certainly depend on the environment. What type of system is your client? What type of system is your server? What kind of transport system stands between them?

If, for example, your clients are Raspberry Pis then it is likely you want to reduce the amount of work you need to do on the client end - take the log(n) option.

If, your client is a Mars Rover you want to minimise the amount of data you need to send and minimise the computation required at the client. Perhaps use the log(n) option, perhaps not - depends on the cost of transporting the data and the computation cost at the other end.

If, however, your server is the LHC then use the n approach - you have probably the largest data bandwidth on the planet and the least amount of time to offload that data you've just collected.


Sipser exercise : variant of CNF is NL-complete I'm stuck rather badly on a Sipser exercise, 8.21 in my edition:

  8.21 Let $CNF_{H1}$ = {<$\phi$> | $\phi$ is a satisfiable cnf-formula where each clause contains any number of positive literals and at most one negated literal. Furthermore, each negated literal has at most one occurrence in $\phi$}. Show that $CNF_{H1}$ is $NL$-complete.

My problem is, if we remove the second condition (each negated literal occurs at most once), the language becomes $P$-complete, so we must use that second condition to get anywhere, but I have no idea whatsoever how to do that? I can't even prove that the language is in $NL$.

To deal with a clause $\lnot x_1 \lor x_2 \lor ... \lor x_n$, all of my efficient algorithms convert it to the equivalent $\lnot x_2 \land ... \lnot x_n \Rightarrow \lnot x_1$, and use that form to deduce in some cases that $x_1$ must be false. With such an approach, however, the second condition can't possibly help. If the negated $\lnot x_1$ appears twice, it simply means that we have more opportunities to deduce that $x_1$ is false, which can't hurt the algorithm?

Let's assume for simplicity that each negated literal appears exactly once. Let $C_i$ be the clause containing $\lnot x_i$. Consider the graph whose vertices are the variables, and $x_i$ is connected to $x_j$ if $x_j \in C_i$. This is a kind of implication graph: in order to deduce that $x_i$ is false from $C_i$, we must have first deduced that $x_j$ was false from $C_j$.

Show that $x_i$ is forced to be false (i.e., unit propagation shows that $x_i$ has to be false) iff the set of vertices reachable from $x_i$ contains no directed cycle, something which can be checked in NL (using coNL=NL). The formula is unsatisfiable iff there exists a positive clause in which all variables are forced to be false (and so unit propagation gets stuck at this clause).

This shows that your problem is in NL. To show that it is NL-complete, reduce from directed reachability. Encode all edges incoming to $x_i$ by a clause of the form $\lnot x_i \lor \cdots$.


Decomposing the n-cube into vertex-disjoint paths I am not sure if this question is better suited for cs.stackexchange or math.stackexchange - This is of interested to me in the context of a data structure problem, but the question itself may be better suited elsewhere. If so, please feel free to move my question.

Let $\mathcal{Q}_n$ denote the $n$-cube graph. Given a set of vertices $S = \{s_1, \ldots s_k \}$ and $T = \{t_1, \ldots t_k\}$, we would like to decompose $\mathcal{Q}_n$ into $k$ vertex disjoint paths $P_1, \ldots P_k$, such that each $P_i$ begins with $s_i$ and ends with $t_i$. Here, two paths are vertex-disjoint if they do not share any vertices. In addition, I require that every vertex in $\mathcal{Q}_n$ be part of some path $P_j$. I would like to know under what conditions (particularly on $S$ and $T$) can we guarantee that such a decomposition exists?

Also, I would like to know the name of this problem so that I can better search for references.

I found the following result due to Gregor and Dvorak. They show that if the sets $S$ and $T$ are balanced (in the sense that they contain the same amount of vertices from both bi-partitions of the $n$-cube), then such paths exists whenever $2k-e < n$, where $e$ is the number of pairs $(s_i, t_i)$ that form edges in $\mathcal{Q}_n$. The paper can be found here: http://www.sciencedirect.com/science/article/pii/S0020019008002238

I can construct an example when $k = 2$, $e=0$ and $n=3$, so this result isn't completely tight, however.


Overhead cost of spawning child processes I am curious as to the overhead cost of spawning child processes using fork in a Linux environment.  Suppose I have a C program such as
void run_computation(int x);

int main() {
    for (int k=0; k<10; k++) {
        if ( fork() == 0 ) {
            run_computation(k);
            break;
        }
    }

    return 0;
}

Assuming that no global state is modified by run_computation, how efficient in terms of overhead is the setting up of the child processes?
To help understand where I'm coming from, I'd like to write my own regex engine (for self-learning) and am imagining using fork to implement the NFA.  So, am I incurring an unreasonable cost in such an implementation compared to other methods?

The (non-negligible) cost is the set up of the in-kernel structures to keep track of the new process (setting up page tables and so on).
You can easily measure it: Write a small program just like the one you have:
#include <unistd.h>

/* Define FORK for forking version */

#ifdef FORK
#define ROUNDS 10000
#else
#define ROUNDS 10000000
#endif

int main(void)
{
        for(int i = 0; i < ROUNDS; i++) {
#ifdef FORK
                if(fork() == 0) /* Child */
                        return 0;
#endif
        }
}

and run it under time(1). Here I get (Intel(R) Core(TM) m5-6Y57 CPU @ 1.10GHz,   Fedora 32, kernel 5.7.15-200.fc32.x86_64, gcc-10.2.1-1.fc32, no optimization; just checked that the non-forking code does it's rounds) for non-forking:
real    0m0.027s
user    0m0.024s
sys     0m0.004s

For forking:
real    0m0.436s
user    0m0.016s
sys     0m0.414s

Very definitely not advisable.


The importance of the membership problem Given a word $w$ and a language $L$, we want to check if $w\in L$.  This is called the membership problem. Why is the membership problem important?

The importance is that any computational problem where the answer is yes or no can be phrased as a membership problem in a language. The language is the set of strings for which the answer is yes.


Set of $\mathsf{NP}$-hard languages closed under set inclusion? As the title says, my question is whether the set of $\mathsf{NP}$-hard languages is closed under set inclusion, i.e. whether for any $\mathsf{NP}$-hard language $L$, all subsets of $L$ are also $\mathsf{NP}$-hard. This question is related since $\emptyset$ is not $\mathsf{NP}$-hard as there is nothing we could map "yes"-instances to and $\emptyset \subseteq L$ for all $\mathsf{NP}$-hard $L$.

However, what about non-trivial subsets, i.e. languages $L'$ of the form $\emptyset \neq L' \subsetneq L$ for $\mathsf{NP}$-hard $L$? We know that $\emptyset \neq 2SAT \subsetneq SAT$ and while $SAT$ is $\mathsf{NP}$-hard, $2SAT$ is in $\mathsf{P}$. This suggests to me that whether the set of $\mathsf{NP}$-hard is closed under "non-trivial" inclusions depends on whether $\mathsf{P} = \mathsf{NP}$. Am I mistaken here?

In one sentence, my question is this: is the set of $\mathsf{NP}$-hard languages closed under nontrivial set inclusion (1) assuming $\mathsf{P} = \mathsf{NP}$ and (2) assuming $\mathsf{P} \neq \mathsf{NP}$?

Indeed, if NP=P then every nontrivial problem is NP-hard, and in particular every nontrivial subset of an NP-hard problem (thus closing it to inclusion).


Proof Idea: How to prove the intersection of regular language and CFL is a CFL? I know that the intersection of a regular language and a context free language is a context free language. I've seen this fact proven on here and other websites. However, after spending hours reading through proofs, I don't really understand the general idea of the proof itself. I'm not looking for a formal proof, but I am more concerned with understanding the high level idea. This is my basic idea for a proof, but there are some issues:

Given a regular language $R$ and a context free language $L$, the intersection of $R$ and $L$ is a context free language $L_1$. We know that there exists a DFA $D$ that recognizes $R$, as $R$ is a regular language. We also know that there exists a PDA $P$ that recognizes $L$, as $L$ is a context free language. Since it is a fact that $D$ can be converted into a PDA $P_1$, we know that $R$ is also a context free language. Next, we create a PDA with states as pairs of states from $P$ and $P_1$.

This is where I am getting stuck. How are the transitions modified to simulate both PDAs? And what happens to the stack?

Look at the product construction for DFAs, it will give you a hint of what the state space of a PDA accepting the intersection will look like.
You can convert $D$ to a PDA, but you have more information than that. It doesn't need to touch the stack at all, since it can be accepted by a DFA.

These should get you close to the answer.


Computational Irreducibility Define $Tape_M(t, i)$ as the symbol in the $i$-th cell of the tape of Turing machine $M$ with empty input at step $t$.

  Does there exist a Turing machine $M$ such that no algorithm can compute $Tape_M(t, i)$ within $o(t)$ (or $o(t/\log(t))$ ) time?

Actually, it is inspired by the celebrated time hierarchy theorem. I believe that it is true but I have trouble proving it. I think diagonalization may be a right direction (like what we do for time hierarchy theorem), but I am not certain how to diagonalize.

I will assume that the alphabet is binary (not really important), and show that $Tape_M(t,i)$ cannot be computed in $o(t/\log t)$ time for every $M$.

Consider a Turing machine $M$, which on the empty input, loops for all integers $i$ and does the following:

Simulate the $i$'th Turing machine $M_i$ on the input $\left(g(i),i\right)$ for $\frac{g(i)}{\log g(i)}$ steps (the function $g$ will be determined later). If it produced output $r$, then write $\overline{r}$ in the $i$'th cell and never change that cell again (you can move forward on the tape and preform the next iterations on the rest of the tape).

Suppose for the purpose of contradiction that there exists a Turing machine $A$ which computes $Tape_M(t,i)$ in $f(t)=o(t/\log t)$ time. Let $j$ be a large enough index of $A$, i.e. $M_j=A$, such that for $t\ge j$ : $f(t)<t/\log t$ (one can encode Turing machines in such a way that every machine has infinitely many representations, e.g. by allowing redundant zeros at the end). When $M$'s loop reaches $j$, it executes $Tape_M(g(j),j)$, which according to our assumption, halts within $\frac{g(j)}{\log g(j)}$ steps with some symbol $r\in\{0,1\}$. $M$ then writes $\overline{r}$ in the $j$'th cell, and it is never changed again. Now suppose that up until the $j$'th iteration, $M$ used less than $g(j)$ time, then after $g(j)$ steps, $M$ has $\overline{r}$ written in the $j$'th cell, which contradicts the fact that $Tape_M(g(j),j)=r$.

It remains to pick $g$ in such a way that until the $j$'th iteration, $M$ uses less than $g(j)$ time. The time required for $j$ iterations is $T_j=\sum\limits_{i=1}^j \frac{g(i)}{\log g(i)}\le j\frac{g(j)}{\log g(j)}$, assuming $\frac{g(i)}{\log g(i)}$ is monotonically non decreasing. Now, we want to pick $j$ such that $T_j\le g(j)$, which is satisfied when $\frac{jg(j)}{\log g(j)}\le g(j)$, or equivalently $g(j)\ge 2^j$.


Is there a name for this infinite language? Is there a name for this infinite language?

$$L = \{ 0(,1)^*(,2)^*(,3)^*....(,n)^* \;\mid n \geq 1\}$$

A string $w \in L$ is simply an ordered list of increasing integers in which every integer  $\geq 1$ can be repeated 0 or more times, for example "0", "0,1", "0,1,2,2", "0,1,2,3", "0,1,1,4,4,4,21,21".

Or perhaps a name for its unary variant: $L_U = \{ 1^{x_1}(,1^{x_1})^*,1^{x_2}(,1^{x_2})^*,...,1^{x_n}(,1^{x_n})^* \mid x_1<x_2<...<x_n\}$

Non-decreasing sequences of natural numbers.


How to approach Dynamic graph related problems I asked this question at generic stackoverflow and I was directed here.

It will be great if some one can explain how to approach partial or fully dynamic graph problems in general.

For example:

Find Shortest Path between two vertices $(u,v)$ in a undirected weighted graph for $n$ instances, when an edge is removed at each instance.
Find number of connected components in an undirected graph for n instances when an edge is remove at each instance, etc.

I recently encountered this genre of problems in a programming contest. I searched through the web and I found lot of research papers concerning with dynamic graphs [1,2]. I read couple of them and and I couldnt find anything straight forward (clustering, sparsification etc). Sorry for being vague.

I really appreciate if some can provide pointers to understand these concepts better.

Dynamic Graph Algorithms by D. Eppstein , Z. Galil , G. F. Italiano (1999)
Shortest paths on dynamic graphs by G. Nannicini, L. Liberti (2008)

It's hard to give you concrete techniques because "dynamic" could mean a wide variety of things, and the algorithms/results depend on your model. Below is an overview of the concerns. Here is a paper that gives an overview of some different concerns and models (related to what Peter cited in another answer).

For dynamic problems in general, the key issues are:

do you want an exact solution in all cases, or is approximation allowed?
do you know anything about what changes will occur (e.g. a probability distribution), or are they all equally likely?
how does the algorithm learn about the changes?

A typical dynamic model is something like the following:

Given a graph, you want to compute some property. You are allowed to compute a solution for the initial graph.
You are then told one modification: edge $(e,f)$ is deleted. Compute the property on the new graph using limited resources.
Repeat 2 for $n$ times.

And here are 3 possible modifications:

You aren't allowed to compute the complete solution at the beginning because of information / time / space limitations (one example of which is online algorithms)
In step 2, the algorithm is not "told" the modification, but has to find the modification in the graph by querying a data structure or something.
A distributed model (like Peter discusses in another answer), where the information is discovered locally and the computation/changes are made locally.

Dynamic models are typically interesting because of resource (e.g. time/space) limitations. In step 2, if I was allowed to compute a complete answer (like I did in step 1) then the problem is easy, since it's just a repeated static graph problem. We're more interested in the smallest amount of resources necessary to compute the change.


Pumping lemma for 0^n and n>0 When applying the pumping lemma to $L = \{ 0^n \mid n>0\}$ I do the following:

$S = 0^p$
$x = \varepsilon$
$y = 0^p$
$z = \varepsilon$

so $S = xyz = (\varepsilon)0^p(\varepsilon)$

For $x y^i z$ if i choose $i = 0$ (pumping down)
i get $S = \varepsilon$, which is not an element of $L$.

Therefore according to the pumping lemma this language is not regular.
But since I am able to draw a DFA for $L$, I know it is regular.

I would like to know what rules I am violating by trying to apply the pumping lemma to $L$ in this manner.

The pumping lemma says that you can split the word into $xyz$. It doesn't say that every such split works. For instance, if you take $|x|=1$ in your example, the pumping works up and down. This would be a "correct split" that makes the pumping lemma hold.

As a reference, recall the definition of the pumping language for regular languages (from Wikipedia):

  Let $L$ be a regular language. Then there exists an integer $p\ge  1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

  $|y| \ge 1$
  $|xy| \le p$ and
  for all $i \ge 0$, $xy^iz \in L$.
  $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).


What is the meaning of this pseudo-code function? While reading the paper Holistic twig joins: optimal XML pattern matching I came across the pseudo code for liststack algorithm. (available through google scholar)

A function in the algorithm confused me, since I can understand what it is supposed to do, but can't deconstruct the notation:

$\qquad \mathtt{Function}\ \mathtt{end}(q\mathtt) \\
 \qquad\qquad \mathtt{return}\ \forall q_i \in \mathtt{subtreeNodes}(q) : \mathtt{isLeaf}(q_i) \implies \mathtt{eof}(T_{q_i})$

This function is supposed to return a single boolean result. It is supposed to be true when all lists associated to leaf nodes of a query pattern node are at their end. So true means there are no more nodes in the query pattern to process.

But what is the meaning of the set builder(ish?) notation here? Is it

$\qquad$ "for all subtree nodes of $q$ for which $\mathtt{isLeaf}(q_i)$ is true $\mathtt{eof}(T_{q_i})$ is also true"

(which means that the list is at the end position)?

Or is it

$\qquad$ "for all subtree nodes of $q$, $\mathtt{isLeaf}(q_i)$ implies $\mathtt{eof}(T_{q_i})$ is true"?

Is double arrow representing implies with its truth table?

As you can see, I'm having a bit difficulty in associating the colon and its precedence.

"Implies" in the English language indicates that there is room for subjectivity. But this is not standard English you're looking at. When you read A⟹B as "A implies B" in Discrete Mathematics, it is just another way to say, "If A is true, then B is true." Formally, this is called material implication.

So the two ways you thought to read it are the same - as far as Comp.Sci. goes. Left to right and minimal imagination it reads (out loud),
"Return the truth of this assertion: For all q-sub-i that are members of subtreeNodes of q, isLeaf of q-sub-i implies eof of T-sub-sub-i."


How correct was Justin Trudeau's explanation of Quantum Computing? Recently, Canada's Prime Minister - Justin Trudeau - gave an impromptu explanation of Quantum Computing, much to the crowd's astonishment. I certainly thought that I "got" Quantum Computing a little bit more, even though it was a simplified explanation.

Here's the YouTube link to the actual press conference.

https://www.youtube.com/watch?v=Eak_ogYMprk

However, some are claiming that we shouldn't jump for joy at his explanation.

I'm wondering, as someone who doesn't exactly understand Quantum Computing, how accurate was Justin Trudeau's explanation of Quantum Computing?

Trudeau's explanation wasn't wrong, but it also wasn't very informative.
Scott Aaronson, a well-known quantum computational complexity theorist, made a blog post discussing it:

What marks does Trudeau get for this? [...] Trudeau doesn’t really assert much here: basically, he just says that normal computers work using 1’s and 0’s, and that quantum computers are more complicated than that in some hard-to-explain way. [...]
[...] I’d grade Trudeau’s explanation as substantially more accurate than what you’d get from a typical popular article. [...] clearly suggests that he knows it’s more subtle than just “0 and 1 at the same time,” and he also knows that he doesn’t really get it and that the journalists in the audience don’t either. [...]
[Grade: B+].

There's a lot of discussion in the comments of that post.


Fast searching through bitarray? I've been thinking for some time but can't figure a way out.
I have big bitarray i.e. 1000+ items of 10_000 bits strings, I'm searching them now linearly. (currently it is stored in one chunk of memory).

I'm looking for some better algorithm for searching/matching !

Do you have any idea ?

bitarray looks like this :

 0) 1011.... <= 10_000 bits
 1) 1100....
 2) 0010....
 3) ........
 ...........

now find index of "1100...." :

 find(1100....) = 1

50% of bits are 1, 50% are 0, always.

I could probably sort it by hamming distance, but will be time consuming! (and array grows dynamically, so i have to re-sort) and the search will still be slower if I search one by one (probably because python overhead).
Currently the search is binary op+, but as you expect doesn't scale well i.e.

#duplicate the search item to the size of array
si_dup = search_item * array_size
dist's = (array ^ si_dup).count_by_row(1s)
top_idx = dist's.argmin()

The bad thing is that this is parallelize-able (I can process it in chunks), but python is not multi-threaded :(.
Also can seem to find a DB which handle large binary-strings, that will be a way out for large sets, I think!

thanks, "locality sensitive hashing" was the key, I researched it a bit and that seem will be the solution for large bitarrays (LSH via BitSampling).
For small ones the current approach I think will be faster.

If you want to look for an exact match, use a hashtable.  Choose a hash function that hashes a 10,000-bit string to a short hashcode.  This approach will be simple and highly efficient: the running time will basically be the time to compute the hash of the 10,000-bit value that you are searching for.


Is it viable to use an HMM to evaluate how well a catalogue is used? I was interested on evaluating a catalogue that students would be using to observe how is it being used probabilistically.

The catalogue works by choosing cells in a temporal sequence, so for example:

Student A has: ($t_1$,$Cell_3$),($t_2$,$Cell_4$)
Student B has: $(t_1,Cell_5),(t_2,Cell_3),(t_3,Cell_7)$.

Assume that the cells of the table are states of a Hidden Markov Model, so the transition between states would map in the real world to a student going from a given cell to another.

Assuming that the catalogue is nothing more than guidance, it is expected to have a certain kind of phenomenon to occur on a given artifact. Consider this artifact to be unique, say, for example a program.

What happens to this program is a finite list of observations, thus, for a given cell we have a finite list of observations for following the suggestion mentioned on that cell. On a HMM this would be then the probability associated to a state to generate a given observation in this artifact.

Finally, consider the catalogue to be structured in a way that initially it is expected that the probability to start in a given cell is equal. The catalogue does not suggest any starting point.

Question 1: Is the mapping between the catalogue and the HMM appropriate?
Question 2: Assuming question 1 holds true. Consider now that we train the HMM using as entries $(t_1,Cell_1), (t_2,Cell_3) , ... (t_n,Cell_n)$ for the students. Would the trained HMM, once asked to generate the transition between states that it is most likely yields as result what is the most used way by the people who used the catalogue for a given experiment $\epsilon$?

Ad Question 1: Assuming that your assumptions on how the catalogue is used -- that is the choice of the next cell only depends on the current (or constantly many preceeding) cell(s), not the (full) history -- then yes, you can use a Markov Chain to model it.

However, you do not seem to need the "Hidden" part; this is only useful if you have (probabilistic) output in the states which you observe. In contrast, you want to observe the students' cell states directly.

Imagine you can not observe which cells students are in but only how much they like the current cell; this could be implemented by notorious "Was this useful to you?" buttons; in general, assume every students gives feedback from $\{1, \dots, k\}$ in every cell but you do not know which cell they are in. Then you can use a HMM to estimate their cell sequence given their feedback sequence.

Ad Question 2: Let me illustrate the use continuing above train of thought. For $n=k=3$, we have the following Markov chain:

[source]

$p_{i,j}$ is the probability to transition from state $i$ to state $j$; note that $p_{i,0}=0$ for all $i$ and those edges have been left out¹. Let $p_{i,\bot}$ the probability of terminating in state $i$ (we leave out another dummy state for clarity). $q_{i,l}$ is the probability to emit $l$ when entering (or, equivalently, leaving) state $i$; this models our feedback. Of course, we require $\sum_j p_{i,j} + p_{i,\bot} = \sum_l q_{i,l} = 1$ for all $i$.

Note that the state sequence $0,1,2$ has probability $p_{0,1} \cdot p_{1,2}$ -- that is a central property of Markov chains. The output sequence $1,2$, on the other hand, has probability $q_{0,1}\cdot p_{0,1}\cdot q_{1,2} + q_{0,1}\cdot p_{0,2}\cdot q_{2,2} + q_{0,1}\cdot p_{0,3}\cdot q_{3,2}$.

In a real world scenario, we would have to train our Markov chain. Let us assume we have some sequences of both state and output²:

$\qquad \begin{align} &(0,1), (1,1), (2,1), (3,1) \\
                      &(0,2), (1,3), (3,1) \\
                      &(0,1), (3,3), (1,2)
\end{align}$

Now we just count how often each transition and output happened and set our probabilities to the relative frequencies³:

[source]

Now you can do the interesting stuff. Ignoring the output, you can determine the path with highest probability, you can determine the output sequence with highest probability but most importantly, and here the hidden part comes into play, you can find the most likely state sequence given an output sequence with Viterbi algorithm.

Bottom line: yes, you can use Markov chains resp. hidden Markov models (depending on your needs) to model your scenario. Wether the fundamental assumption -- the probability for the next cell only depends on the current cell -- makes sense is another question entirely.

We need a starting state, but we can make it a dummy by never going back. We can ignore its output or introduce a dummy output that is only and always emitted in state $0$.
If we have only output sequences, we can use the forward-backward algorithm.
Due to our low number of observations, we have a number of impossible transitions/emissions. Usually you assume that everything is possible and has just not been observed due to low probability. We can compensate for this by adding $1$ to all counts; this way, all sequences have probability $\gt 0$.


Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS? In section 9.2 of CLRS (Introduction to Algorithms; page 185 in the 2nd edition and page 215 in the 3rd edition), a randomized selection algorithm is presented.

For its analysis, $T(n)$ is a random variable denoting the time required on an input array $A[p \cdots r]$ of $n$ elements and $X_k$ is an indicator random variable $X_k = I \{ \text{the subarray } A[p \cdots q] \text{ has exactly } k \text{ elements (due to the pivot)} \}$.

It has been claimed that $X_k$ and $T(\max(k-1, n-k))$ are independent (page 187 in the 2nd edition and page 218 in the 3rd edition). However, I find it quite counter-intuitive to understand. How to verify it?

The two random variables $X_k$ and $T(\max(k-1, n-k))$ are independent because in each recursive call to RANDOMIZED-SELECT() we invoke RANDOMIZED-PARTITION(), a pivot is randomly selected, and the choice of the pivot in one recursive call is independent from the choice of the pivot in another recursive call. Remember that in the analysis we assume that the elements are distinct, so that each element in a particular subarray has the same probability of being selected as the pivot. Moreover, simply stated, the value of $\max(k-1,n-k)$ does not depend on $X_k$: it is the same independently of $X_k$ being equal to zero or one.


Parallized algorithm for getting the frequencies of numbers in an array I have an array $A$ of length $n$, containing integers between $0$ and $n-1$ inclusively. I would like to convert this to an array of frequencies $F$, that is, $F[i]$ should be the number of times $i$ appears in the array $A$. For example, $A=[1,3,1,1,0]$ would be mapped to $F=[1,3,0,1,0]$. There is an easy algorithm for this, however I would like to do this efficiently in parallel. Here is my first attempt at doing so:
Let $n = p*k$ where $p$ is the number of threads, $k$ is the number of indices each thread will process and $n$ is the total number of indices (length of A). Each thread is given a range containing $k$ indices and all threads have access to an array $F$ that will be the frequency list. $F[i]$ starts off containing $0$ but after successfully running the algorithm, will contain the frequency of index $i$ in the array $A$.
Each thread runs the following pseudo code:
for i in given range:
  F[A[i]] += 1

Assuming a mutex is used, I think this algorithm works fine, however it runs into efficiency problems because all threads may want to increase the same index of $F$ at the same time. For example, this would happen if every index of $A$ contains the same number.
I would like an algorithm which avoids this problem and is deterministic. Ideally the time complexity should be something like $O(n/p)$. This is probably not possible of course, but I would like to be able to take at least some advantage of the parallelism, even when assuming a worst case input.

It is common problem in parallel computing. Many parallel framework have "reduction operator" for such processing. Idea is simple.
Use separate local copies of F[A[i]] in each threads. Calculate frequency in parallel for each sub-array block in parallel. Now since each thread is updating only its local copy of frequency array F[A[i]], no mutex is required. After the completion of all threads, join all the per thread F[[A]] array's into a single application array, i.e., reduce. You will get almost O(n/p) time complexity. The actual time complexity will depend on Size of your array (larger, the better) and the number of threads (creating and joining threads takes time).


What the difference between the Fourier Transform of an image and an image histogram? Consider this small picture of a sunflower, and its histogram:

  What would the Fourier transform of the first picture look like?  Is there any relationship between the histogram and the Fourier transform?

This post is a copy from the top voted answer to the question What does the Fourier Transform mean in the context of images?
The answer is math.sx user due to dls.

In sound processing, the Fourier Transform has a physically intuitive meaning. A sound or function $f : [0,b] \rightarrow [-1,1]$ can be represented as a trigonometric series. And each term of the series corresponds to a frequency which you perceive. Many effects (like filtering, reverb, etc.) have an interpretation in the frequency domain which is useful for analysis. Unfortunately, the physical interpretation isn't as simple when we start talking about images. But on the analytic usefulness transfers over.

If we're talking about grey-scale, then an image is simply a function $f : [0,1]^2 \rightarrow [0,1]$. It takes a point in the square $[0,1]\times[0,1]$ and produces a value between 0 and 1, the intensity. The Fourier Transform just says we can represent this function in the frequency domain using a countable basis of trigonometric functions. Say you want to blur an image; this corresponds to a low-pass filter in the frequency domain. The following link shows many examples of Fourier transforms of images, gives an explanation of the physical interpretation (which I don't claim to understand entirely) and shows examples of basic image processing. This website shows more illustrative examples.

Another very important use of (variants of) the 2d-Fourier transform is image compression. The Wikipedia page for the JPEG codec lists the basis functions used to represent images.

Finally, note that if you're talking about an RGB image you can represent the image using the Fourier transform on each color component.


Algorithm for estimating lossless compression factor Is there any algorithm for estimating how well certain array of bytes could be compressed in lossless manner?

Usage for me is to automatically choose "best" data reorder method without knowing what compression method end user is going to use. I don't need perfect/optimal result, I just need some kind of numerical result that I can use to compare different permutation runs.

For example string "AAAABBBBCCCCDDDD" should compress better than "ABDABBABCDCCDACD" but if I use e.g. Shannon Entropy for estimation then I get identical results.

In general the only way to know what the compression factor with a particular compression method is to compress the data using that compression method and see what the compression ratio is.

Some compression algorithms have different levels of compression (e.g., 0-9), which allow the algorithm to spend a lot more CPU time to try to get a bit better compression.  You might be able to use the compression factor at a lower compression level as a predictor of the compression factor at a higher level, though this won't be perfect.


Preprocess an array for counting an element in a slice (reduction to RMQ?) Given an array $a_1,\ldots,a_n$ of natural numbers $\leq k$, where $k$ is a constant, I want to answer in $O(1)$ queries of the form: "how many times does $m$ appear in the array between indices $i$ and $j$"?

The array should be preprocessed in linear time. In particular I'd like to know if there's a reduction to Range Minimum Query.

This is equivalent to RMQ in the case where $k=1$ and you want to query the number of ones within an interval. So we can use it.
I couldn't answer my own question because of limits of SE.

Since $k$ is constant, we can store the count of each element in the range $0..m$  for $0\leq m \lt n$ in $0..n$ in $O(nk) = O(n)$ time and space. The primary observation is that you can make a two-dimensional array count[pos][elem] = occurences of 'elem' in the indices 0..pos in $O(nk)$ time, then query ranges by finding the difference in $i,j$ indices in constant time.

Preprocessing

initialise count[pos][elem] to 0 for all elem, pos
for pos=0 to n
  for num=0 to k
      count[pos][num] = (0 if pos==0 else count[pos-1][num])
  count[pos][arr[pos]] ++

Query

(assumes i,j are both inclusive bounds)

if i == 0
  return count[j][m]
else
  return count[j][m] - count[i-1][m]

If the array is also getting updated throughout the query process, you can use $k$ Fenwick (binary index) trees in place of the count array. This lets you update in $O(\log n)$ and query in $O(\log n)$.

Apologies for any issues with this answer, it's my first.


Check for common element in two arrays using FFT My task asks me to check whether there is a common element in two sets $\{x_1,x_2,...,x_n\}$, $\{y_1,y_2,...,y_n\}$ with $x_i,y_i\in\mathbb{N}$ using the Fast Fourier Transform (FFT).
(I'm aware that there is a simple $O(n\log(n))$ algorithm to solve this problem using sorting and binary search.)
The tasks hints that we should consider the following product to solve the problem:
$$
\prod_{1\leq i,j \leq n} (x_i-y_j)
$$
The product is obviously zero if there is a common element, but I am still not sure how I could compute it faster via FFT.
I know how to use FFT to multiply polynomials efficiently, but somehow I seem to overlook something.

This one is a bit esoteric, but:
$$
\prod_{1\leq i,j \leq n} (x_i-y_j)
$$
Could be decomposed to (as noted by @NotDijkstra)
$$
\prod_{i=1}^{n} p(x_i)
$$
where
$$
p (x) = \prod_{j=1}^{n} (x - y_j)
$$
reduces to a polynomial with roots $y_i$. Coefficients of this polynomial could be computed with FFT, see https://arxiv.org/pdf/1608.01357.pdf. It could be done even faster using divide and conquer strategy - recursively split the formula into two polynomials and multiply them with FFT (see answers).
Polynomial representation in its turn would allow fast exponentiation of x, or even multi-point evaluation
Although, I don't see any advantages over traditional approach in terms of speed or complexity except if it's implemented on specialised ASICs/FPGAs/GPUs.


Flaw in linear programming solution for multi-commodity flow problem? The multi-commodity flow problem problem statement - wiki

According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. The linear program form of this problem as given in clrs is

f is flow, c is capacity, u and v are vertices, d is demand, s is source, t is target(sink). We are given k commodities. i corresponds to ith commodity.

Now How does these constraints guarantee that i commodity will end up only in target of i (ti) with its respective demand (di)

Why It works for single commodity case

In single commodity case it includes all the constraints. This is popularly known as the Maximum Flow problem. The first constraint is capacity constraint, the second one is flow conservation. The fourth implies flow is non-negative.

Why There is Problem for the multi-commodity case ?

There is no constraint on target which guarantees that flow will only go into its respective case.

For instance, this seems like a simple counter example:

The linear programming formulation from CLRS is fine.  There is no problem with it.

Your purported counterexample isn't a valid counterexample -- it  doesn't satisfy all of the inequalities.  Take a closer look at the specification of the second inequality.  For instance, when we are dealing with commodity $a$ ($i=a$) it says that we should have

$$\sum_{v \in V} f_{auv} - \sum_{v \in V} f_{avu} = 0$$

for all $u \in V \setminus \{s_a,t_a\}$.  In particular, consider the case $u = t_b$.  We have

$$\sum_{v \in V} f_{at_bv} - \sum_{v \in V} f_{avt_b} = 0 - 2 \ne 0,$$

so the inequality is violated.

To put it in English: the second inequality requires conservation of flow for each commodity, except at that commodity's source and sink.  For example, for commodity $a$, we must have conservation of flow at every vertex except $s_a$ and $t_a$.  In your proposed counterexample, conservation of flow for commodity $a$ is violated at vertices $s_b$ and $t_b$; that's not allowed.


Computability - The language of all strings of even length Define a language $L$ as follows:
$$L = \{\langle M \rangle \in \{0, 1\}^* | M\text{ is a TM that halts on all strings of even length} \}$$

I can prove that $L$ is not decidable/recursive, but is it recognisable/recursively enumerable? My intuition is that $L$ is unrecognisable because suppose there exists a TM $N$ that recognises $L$, $N$ would have to test all strings of even length which is countably infinite.

I have tried reducing $HALT^-$ to $L$ but not succeeded. Is it unrecognisable or not? How would you prove it?

Thanks.

$L$ is not recognizable. To avoid confusion, my assumption is that by $\text{HALT}^-$ you mean the language $\{\text{code}(M) \ w \mid M \text{ does not halt on } w\}$. We know that $\text{HALT}^-$ is not recognizable, thus showing $\text{HALT}^- \leq  L$ implies that $L$ is not recognizable.

For showing that $\text{HALT}^- \leq L$, we have to give a computable mapping $\text{code}(M)\ w \mapsto \text{code}(M')$ such that $M$ does not halt on w iff $M'$ halts on all input of even length. For a given $M$ and $w$, define $M'$ to be the TM that behaves as follows: It checks the length $l$ of its input. If $l$ is uneven, it does something arbitrary. If $l$ is even, $M'$ simulates $M$ for $l/2$ steps on $w$. If $M$ halts during this simulation, $M'$ goes into an infinite loop, otherwise $M'$ halts.

You can easily verify that this mapping has the desired properties. It is clearly computable and:

If $M$ does not halt on w, then $M'$ will for any input of even length $l$ simulate $M$ for $l/2$ steps on $w$ without the simulation halting, thus by definition $M'$ will halt afterwards.
If $M$ does halt on $w$ (after $k$ steps), then $M'$ does not halt on all inputs of even length, because for inputs of length $2k$ it will simulate $M$ on $w$ for $2k$ steps, with the simulation halting, thus by definiton of $M'$ it will go into an infinite loop.


Is there a guaranteed min-cut algorithm for weighted graph or weighted cyclical digraph? I'm looking for find the min-cut of a fully-connected directed graph (with cycles), or an undirected graph.

Karger's works but is not guaranteed to produce the correct solution. Is there a guaranteed algorithm?

I came across max-flow algorithms. Do these only work if the graph is acyclic?

Thanks.

Directed graphs: Use any max-flow algorithm together with the max-flow min-cut theorem.  There are any number of algorithms for max-flow in an arbitrary directed graph.  This is bog-standard stuff that should be covered in any algorithms textbook.  See also minimum cut.

Undirected graphs: Use a min-cut algorithm for undirected graphs, e.g., Karger's algorithm or this lecture.  I don't know what you mean by "it is not guaranteed to provide a solution"; the probability that it fails to find a solution is exponentially small, e.g., you can make this probability smaller than the chance that a cosmic ray hits your computer, makes it compute the wrong answer, and then you get struck by lightning and die anyway.  Tough luck about that lightning, by the way.

Next time do more research before asking.


What guarantees Paxos to converge (terminate)? (i.e. not run forever without a consensus) I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and was wondering, what guarantees Paxos to converge and not run forever without a consensus/agreement on a value? Is it guaranteed to converge always or is it a probabilistic bound that the probability that it does not converge is really really small?

Because I was reading condition $P2^c$ and it seems possible to me that because of that condition, Paxos might loop forever if we are not careful (I think, maybe I am wrong, but I would love to know why!) Take the following case:

I was a little worried about the case when, say that a majority was close to forming but there is a new node that wants to propose his new value but was unlucky and did not happen to communicate with that growing set that nearly formed a majority (its not a majority yet, but it was reaalllyyy close!). That node was ready to prepare his value but was that unlucky and reasoned "Ok, none of the nodes I spoke to had a value, thus, time to propose my value!" but his sequence number is much higher than the previous one that was forming on the other side and it starts to spread, wouldn't it be because we want to satisfy (b) in $P2^c$? i.e. doesn't it damage the convergence to a decision (never mind the run time, it might never converge...)? Even in the case of a very good quality network..?

Because now this new node has a higher value and his value spreads like a disease and it could happen again, right before it was about to form a majority with his own value. That situation could happen again and again and again no value is decided! Right? What prevents Paxos from being in this situation? Or what is the argument to convince me that its really unlikely to happen many times and that it converges in polynomial time most of the time?

Recall condition $P2^c$ is the following:

$P2^c$

"For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that
(a) no acceptor in S has accepted any proposal numbered less than n,
or
(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S."

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

There is no guarantee that Paxos will converge. In fact, more strongly, it can be shown that it is impossible to guarantee convergence of a distributed consensus algorithm in an asynchronous network. See for example Fischer, Lynch and Patterson's short paper ‘Impossibility of Distributed Consensus with One Faulty Process’.

In practical implementations it is usual to rely on the fact that, as long as enough nodes are working and communicating with each other, if exactly one node sends out a PREPARE (phase 1a) message for a sufficiently large ballot, and there are no other messages in flight, then the system will converge in a small number of round-trips. These conditions can be arranged, eventually-almost-certainly, by using randomised timeouts and maybe some kind of backoff.


Changing a complete undecidable turing machine language $L = \{\langle M\rangle\mid \text{M is a TM and }L(M) = \{101\}\}$ meaning M accepts only the string $101$. Which is neither co-recognizable / recognizable. Can be proven easily by $HALT \leq_m L (\text{ or } \bar{L})$ mapping reduction. Reasoning being its very to prove for all TM that none accepts 101 or none rejects 101. How do I tweak this to make this either recognizable or co-recognizable but not both?

My attempt:

$L = \{\langle M,w\rangle\mid \text{M is a TM and for some }L(M) = \{101\}\}$

$\bar{L} = \{\langle M,w\rangle\mid\text{M is a TM and for none }L(M) = \{101\}\}$

I'm trying to change it to it can accept 101 instead of it only accepts 101. And the complement is that it cant accepts 101. I'm stuck at the complament i don't think its proper and the wording of the language. I don't know if theres a easy way to change this language.

Well, lets start with your $L$ first. Claim: $L$ is undecidable.#

Clear: $L$ is not empty (there exist TM that accept that input) and not trvial (there exist a input w on some $M$ where $w \notin L(M)$ by definition of $L$. Thus, $L$ ist not trival and no property of $M$, so by Rice'S Theorem $L$ is not decidable.

For your $L^C$ the argumentation is basically the same, it is also undecidable.

To make a language r.e (recursive enumerable), in your terms co-recognizable we need a aditional property:

Termination properties of your TM
For the recursive languages, we need this also, because REC is a subclass of RE.

A language $L$ is r.e. iff. for each $w \in L$ there exists a TM M, such that M halts and accepts. For recursive language you need more, here the TM must even halt and decline the input if it is not part of the language.

A recursive language would be:

$L_{rec} = \{<M> |$ for each input $w$ M halts and accepts, if $w = 101$, otherwise M halts and declines. $\}$

EDIT: Language is not reursive (but r.e). If $L_{rec}$ would be recursive, it would be co-recognizable.
Given a word $x = <U>w$ (coding of U and input word w for U). Chose $U$ as a TM that never halts and $w=101$.

Assume there exists a TM $M$ which could compute that $<U>w \notin L_{rec}$. That is if $U$ does not halt. So, $M$ has to know if $U$ halts and thus never halts (it always waits for U to stop). A contradiction.

I will let this answer stay here to clarify the pitfall between decidability and recognizability. Recognizablity is a weaker property of a language then decidability.


How to compute the TF-IDF scores for a handful of documents, but without my own corpus? I have a small number of documents (I could probably get 4 or 5 documents) and want to assign terms in these documents a score based on its importance to the document.  I want to find which terms are simultaneously important to all of these documents.

These documents have different authors but are written about the same topic, and I want to filter out keywords that are artifacts of the authors' writing styles.

TF-IDF seems like a well-established scoring function.  However, the documents I have do not belong to a large corpus of documents, prohibiting the computation of IDF-values.

Q: How can I compute the TF-IDF score of terms within a handful of documents, but without my own corpus?

I'm open to alternative suggests that do not involve TF-IDF.

Answer

What do you value in a ranking function? If you don't value TF or IDF, then it'll be difficult for you to achieve what you want to achieve.

Without a corpus however, you could use a frequency chart as a substitute for TF:

http://www.wordfrequency.info/free.asp?s=y

I had trouble finding a similar list for IDF online. However, you could just remove the IDF term from the TF-IDF equation. Finding an alternative for IDF is difficult.

Your Situation

4-5 documents isn't much, but it's still a corpus. Of course, it'll likely have more error than a larger corpus, but I see no reason why you can't use it. Also, why can't you use IDF? If the term exists in one document, then IDF can be computed, otherwise it shouldn't be in your controlled vocabulary anyway. Although if you're worried about error, then you could probably just discard it at this point.

If you just use your documents as the corpus, you can take advantage their context, which seems to be what you want here. Basically, many words will be more/less common in your subset than in the English language in general due to the specific domain and small sample size.


What is a genuine atomic multicast? What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?

Atomic multicast is a generalisation of atomic broadcast. In atomic multicast, there are $M \geq 1$ groups of processes $\Gamma = \{ G_1, G_2, \dots, G_M \}$, where $G_i$ is a non-empty group. The groups are usually defined to be non-overlapping or disjoint, that is, groups do not have processes in common. A message $m$ can be sent to one or more groups. The destination groups of a message $m$ are usually defined to be the groups inside the set $m.dst$, that is, m will be delivered by all processes inside the groups which are inside the set $m.dst$. Atomic broadcast is a special case of atomic multicast, where there is only one group which contains all processes.

To be more precise, let us more formally define the atomic multicast (AM) problem. An AM is a reliable multicast, which also requires a "total order" property to be satisfied. Let us first defined a reliable multicast.

A reliable multicast (RM) is defined in terms of two primitive operations, often denoted by R-multicast(m, m.dst) and R-deliver, where $m.dst$ is the set of groups to which $m$ is multicast. R-multicast is used to reliably multicast, that is, to send message $m$ to the groups in $m.dst$, and R-deliver is used to reliably deliver the message $m$ once it has been received by those same groups.

These primitive operations, R-multicast and R-deliver, and, in general, any algorithm which implements RM must satisfy 3 properties:

Validity: If a correct process multicasts $m$, then all correct processes that belong to a group of $m.dst$ deliver $m$
Uniform Agreement: If a process delivers a message m, then all correct processes that belong to a group of $m.dst$ deliver $m$
Uniform Integrity: A process $p$ delivers a message $m$ at most once and only if the group of $p$ is in $m.dst$ and some process has previously multicast $m$.

In addition to these 3 properties, the atomic multicast problem also requires the following property to be satisfied

Local total order: If processes $p$ and $q$ both deliver messages $m$ and $m'$ and $m.dst = {m'}.dst$, then $p$ delivers $m$ before $m'$ if and only if $q$ delivers $m$ before $m'$.

In other words, if the destination groups of the messages $m$ and $m'$ are the same and there are two processes which deliver both $m$ and $m'$, then they must deliver these messages in the same order (or in "total order").

In reality, there are other "total order" properties: for example, there is the "global total order" property. An atomic multicast problem defined in terms of the "global total order" property is different than the atomic multicast problem defined in terms of the "local total order" property. See section 2.2 of the paper "Fault-tolerant Genuine Atomic Multicast" by Carole Delporte-Gallet and Hugues Fauconnier for more details.

I stated that an atomic multicast is a generalization of an atomic broadcast. However, an atomic broadcast can actually be used to implement an atomic multicast. More specifically, to do that, we can atomically broadcast the messages and then only the groups inside $m.dst$ would atomically deliver $m$. However, this would send $m$ to all groups in the system, even though they may not be in $m.dst$. In other words, if we implemented an atomic multicast using the modified version of the atomic broadcast algorithm just explained, all groups and processes in the system would be involved. This implementation would be as costly as the implementation of an atomic broadcast algorithm. We want to avoid this!

A genuine atomic multicast algorithm is an algorithm which solves the atomic multicast problem where only the sender of the message $m$ and the processes in destination groups ($m.dst$) are "concerned" by (or involved in) the atomic multicast of the message $m$.

Thus the adjective "genuine" is associated with the algorithms which solve the atomic multicast problem and not with the problem itself.


Proving that co-finite languages can be decided in constant time I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$.

If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$.

I'm not sure how to proceed from here. Any hints?

Your observation that co-finite languages are regular and hence in linear time is absolutely correct. Unfortunately, it's not enough, since there are definitely regular languages that require linear, and not constant, time (e.g., even checking if your input matches $0^*$ requires you to look at the whole input, unless $\Sigma=\{0\}$).

There are only finitely many strings not in a co-finite language. So, how much input do you need to read before you know whether the input is one of those?


How to solve F(n)+1 = (F(n-1)+1)*(F(n-2)+1) this recurrence relation? I am trying to solve this recurrence relation for a while but not getting anywhere. Actually, the sequence is given as,

  F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2)

where, F(0) and F(1) will be given. I added 1 on both sides to factorize it. I tried to solve it by taking log on both sides but unable to come to a conclusion.

P.S. I can't use simple for loop as n can go upto 10^9 so it'll result into a timeout.

It can be computed in a completely analytical way. Take:

$$
F_n = F_{n-1} + F_{n-2} + F_{n-1}F_{n-2}
$$

Adding $1$ to both sides and factorizing we obtain:

$$
F_n + 1 = (F_{n-1} +1)(F_{n-2}+1)
$$

Now let $G_n = F_n + 1$ :

$$
G_n = G_{n-1} G_{n-2}$$

Taking the logarithm in some base $b$ :

$$
\log_b{G_n} = \log_b G_{n-1} + \log_b G_{n-2}$$

Which we rewrite, letting $H_n = \log_b{G_n}$ , as:

$$
H_n = H_{n-1} + H_{n-2}
$$

This suggests an effective way to compute $F_n$ . First of all we compute $H_0 = \log_b(1 + F_0)$ and similarly $H_1$. Then we determine $H_n$ in closed form. Since $H$ is a second-order recurrence with constant coefficients, $H_n$ is in the form:

$$
H_n = A\phi^n + B\psi^n
$$

where $\phi, \psi$ are the solutions to the associated polynomial equation $h^2 = h +1$, namely $\frac{1 \pm \sqrt{5}}{2}$. Knowing $H_0$, $H_1$, we can determine $A, B$ as the solutions to the following system:

$$
\left \{
\begin{array}{r c l}
H_1 & = & A\left( \frac{1 - \sqrt{5}}{2} \right) + B\left( \frac{1 - \sqrt{5}}{2} \right) \\
H_0 & = & A + B
\end{array}
\right .
$$

Now, remembering that $H_n = \log_b{G_n}$ and $G_n = F_n + 1$, we can finally compute:

$$
F_n = b^{H_n} -1
$$


Selecting k "special" nodes in a graph such that the min distance is maximized? Lets say we have a graph $G$ with $|V|$ nodes. We wish to select $k$ such nodes while optimizing the following attribute:

maximize: for each $i$ and $j$, where $i \neq j$,  $min(distance(v_i, v_j))$

Hope that makes sense. We'd like to pick $k$ nodes such that the distance between the closest pair of distinct nodes is maximal.

Currently, my plan is to pick a node in random, find the node furthest away from it $v_0$ and the one furthest away from that node $v_1$. Now recursively look for nodes such that maximize the minimal distance from the selected node set. Meaning, nodes that have the greatest distance possible from the any selected node and specifically the member closest to them of the previously selected set of nodes.

The issue with this is that it's greedy and therefore possibly very inaccurate.

Assuming $k$ is part of the input, the problem is NP-hard (by reduction from Independent Set; there's an independent set of size $k$ if and only if there's a way to solve your problem and achieve a minimum distance of 2 or greater).

Your current plan is known as the furthest-point heuristic.  It's a heuristic, because it won't necessarily give the optimal solution, though often it gives a solution that's reasonably good.  The furthest-point heuristic has been used, among other things, as a technique to select the initial values for $k$-means clustering.

If you want to find an exact solution, you could express this as an instance of of ILP or SAT.  Suppose we want to test whether min-distance $t$ is achievable.  For each variable $v$, you have a boolean variable $x_v$ that's 1 if $v$ is selected or 0 otherwise.  Now for each pair of nodes $u,v$ such that $d(u,v)<t$, you add a constraint saying that you cannot choose both $u$ and $v$ (e.g., the constraint $x_u+x_v \le 1$ or $(\neg x_u \lor \neg x_v)$).  Finally, you add a constraint that exactly $k$ nodes much be selected, and then you test whether these constraints are satisfiable.  If they are, min-distance $t$ is achievable.  Now repeat using binary search to find the largest $t$ such that the instance is satisfiable.


Definition of "properly partial" versus "total" value types In the Foundations chapter of Elements of Programming (Stepanov and McJones, 2009), this paragraph appears:

  A value type is properly partial if its values represent a proper subset of the abstract entities in the corresponding species; otherwise it is total. For example, the type int is properly partial, while the type bool is total.

I have a hard time understanding what this means and have been unable to find any good explanations of these terms on the Internet. What are properly partial and total value types?

$
\newcommand{\llbracket}{[\![}
\newcommand{\rrbracket}{]\!]}
$First, a proper subset is a subset that is not equal to the whole set. In other words, $A$ is a proper subset of $B$ iff $A \subseteq B$ and $A \ne B$.

If you formulate a denotational semantics for a language, then each type $T$ has an associated set $\llbracket T \rrbracket$ which is called the denotation of $T$. Stepanov and McJones calls this set the abstract species corresponding to the type $T$ (in this particular semantics). For example, it is natural to associate the set of integers $\mathbb{Z}$ to the type $\mathtt{int}$, with value semantics $\llbracket \mathtt{0} \rrbracket = 0$, $\llbracket \mathtt{1} \rrbracket = 1$, $\llbracket \mathtt{-1} \rrbracket = -1$, etc. and the set of truth values $\{\mathsf{T},\mathsf{F}\}$ to the type $\mathtt{bool}$ with value semantics $\llbracket \mathtt{false} \rrbracket = \mathsf{F}$ and  $\llbracket \mathtt{true} \rrbracket = \mathsf{T}$.

A type is total under a denotational semantics iff the set of denotations of values of that type is equal to the denotation of the type. A type is properly partial iff is it not total, that is, iff the set of denotations of values is a proper subset of the denotation of the type. (The denotation of a value must be a member of the denotation of the type, otherwise the semantics is not valid, thus the denotations of values always form subset of the denotation of the type.)

For example, the set of denotations of values of the type $\mathtt{bool}$ under the semantics above is $\{\llbracket \mathtt{false} \rrbracket, \llbracket \mathtt{true} \rrbracket\} = \{\mathsf{F}, \mathsf{T}\} = \llbracket \mathtt{bool} \rrbracket$ so the type $\mathtt{bool}$ is total under this semantics. On the other hand, the set of denotations of values of type $\mathtt{int}$ consists only of values in the range $[-2^{N-1}, 2^{N-1}-1]$, assuming a typical implementation of the type $\mathtt{int}$ with $N$ bits, therefore $\mathtt{int}$ is properly partial under this semantics.

Note that the totality of a type depends on the chosen semantics. For example, under a semantics where the denotation of $\mathtt{int}$ is the integer range $[-2^{N-1}, 2^{N-1}-1]$, the type $\mathtt{int}$ is total.

”Abstract species“ and “properly partial” are not widespread terminology. As far as I know, they were coined by these authors.


What's the least signifcant bit of a mantissa system? If Mantissa is a 1-dot-M fixed-point number whose most significant bit is always  1 then, how is the least significant bit calculated?

I know the least and most significant bit of the mantissa results in the following range:

1.0 <_ Mantissa <_ (2.0 - 1/2^M)

But specifically, I don't understand where the 2 comes from.


Why is a Knapsack problem not an LP problem? We know that LP can solve optimization problems that have linear constraints and linear objective functions.

A knapsack problem can be formulated into a linear objective function (because it is just a summation of Pi*Xi) and linear constraints (because it is just a summation of the items weights which should be <= the knapsack weight), so why can't we consider it an LP problem?

You can set up the knapsack problem as an integer linear program: To each item associate a 1/0 variable (include/exclude that item). Setting up the restrictions and the objective function from here is straightforward.

The point here is that the variables are restricted to be integers, while (regular) linear programming assumes real variables. They look similar, but are quite different beasts, computationally.

One successful technique to construct an approximate solution to the knapsack problem makes up a (continuous) linear programming problem, solve that one and tweaks the resulting values.


Algorithm for generate all solutions to a linear Diophantine equation Consider the linear Diophantine equation of the form:
$$\sum_{i=1}^{k}a_ix_i=n.$$
My goal is to list all the non-negative solutions to this equation. I wrote the following recursive algorithm, but I am not sure if it is the most efficient way to build the solutions. Here is the current version:

def recsolve(n, L, cursol, result = []):
if len(L) == 1:
    ak = L[0]
    if n%ak == 0:
        result.append(cursol + [n//ak])
    return

else:
    a1 = L[0]
    end = math.floor(n/a1)
    for k in range(0, end + 1):
        recsolve(n-k*a1,L[1:], cursol + [k],result)

result = []
n = 5
L = [1,2,3]
recsolve(n, L, [], result)
print(result, "; Number of solutions:", len(result))

I would be grateful if someone could suggest more efficient approaches to finding all solutions to a linear Diophantine equation.

Your current recursive solution is pretty solid. It is, I believe, about the most efficient recursive approaches we can have for the general situation.

Somehow I prefer the code in you first solution since it is easier to read. All we need to make it correct is to change return [None] to return [] and if None not in res: to if res:

Implementation-wise, we could change it to use an iterative method which should run faster. Also, we could sort $a_i$ in descending order which may improve the listing speed. For example, solutions for $100x_1+100x_2+x_3=1000$ will be found much faster than $x_1+100x_2+100x_3=1000$.

In some special cases, we might be able to speed up the performance. For example, for $15x_1+10x_2+6x_3=100000$, $x_1$ must be a multiple of 2, $x_2$ must be a multiple of 3, $x_3$ must be a multiple of 5. These restriction could help us to improve the speed if they are given or they can be found by factorization easily.


Universal hashing function probability Can somebody explain the following:

U is a universe of keys, and H is a finite collection of hash functions mapping U to {0, 1, … , m-1}.

I do not understand definition 2, and thus why amount of funtions that map x and y to the same location is given by |H|/m.

Let’s begin by talking about the intuition for universal hash families. Intuitively, a family of hash functions is universal if for any distinct objects x and y that you’d like to hash, if you select a random hash function from the hash family, the probability that you get a collision between those two elements is at most 1/m, where m is the number of buckets. In other words, universal hash families tend to spread elements out in a way where the probability of a pair colliding is the same as if the elements were distributed randomly.

Let’s see how the definition accomplishes this. Here’s the definition from your question:

  H is universal if ∀ x, y ∈ U where x ≠ y | { h in H : h(x) = h(y) } | = |H| / m.

For starters, I’m assuming that we’re talking about hash functions that map from some set U to the integers 1 through m or 0 through m-1. With that in mind, let’s unpack some of this notation.

If we replace the universal quantifier (∀) with the plain English “for all,” this definition says “H is universal if for every choice of two different items x and y to hash, some inequality is true.” So let’s look at that inequality. First, what is this bit?

  | { h in H : h(x) = h(y) } |

The vertical bars here represent the size of a set, and the set in question is this one:

  { h in H : h(x) = h(y) }

Read literally, this is the set of all hash functions h in the family H where h(x) = h(y). Keeping in mind that we’re talking about hash collisions here, we can think of h(x) = h(y) as saying that hash function h causes x and y to collide with one another (have the same hash code). With that in mind, the complex expression

  | { h in H : h(x) = h(y) } |

means “the number of hash functions in H where x and y collide.”
Combining that with our earlier bit, we can rewrite the entire definition as

  H is universal if for any two distinct elements x and y that we want to hash, the number of hash functions in H where x and y collide is at most |H| / m.

So what’s |H| / m? That’s the total number of hash functions (|H|) divided by the number of possible outputs for any one single hash function (m). It might help to divide the entire expression through by |H|, which would then give this final definition:

  H is universal if for any two distinct elements x and y that we want to hash, the probability of picking a hash function h where x and y collide (that is, the total number of hash functions where x and y collide divided by the total number of hash functions) is at most 1/m.

Hope this helps!