Difference between ways to compare floating-point numbers There seems to be many approaches to judge whether two floating-point numbers are identical. Here are some examples I've found:

fabs(x - y) < n * FLT_EPSILON * fabs(x) OR fabs(x - y) < n * FLT_EPSILON * fabs(y)
fabs(x - y) < n * FLT_EPSILON * fabs(x + y)
fabs(x - y) < n * FLT_EPSILON * fabs(x + y) || fabs(x - y) < FLT_MIN)
fabs(x - y) < n * FLT_EPSILON * sqrt(x * x + y * y + FLT_EPSILON * FLT_EPSILON)

I'm really confused about them. Suppose there is a best way to compare two floating-point numbers, which is the simplest as well as the most accurate, the other approaches shouldn't even exist. So these different ways must have there own pros and cons.

My question is: To do "real computations", which approach is the most accurate one?

Reference links:

http://accu.org/index.php/journals/1558 (1 and 4)

https://stackoverflow.com/a/10335601/5399734 (2 and 3)

You are rightfully confused, because these answers mix up incompatible concepts into a right mess.

If you want to know whether two floating point numbers are equal then you use the "==" operator, which will tell you absolutely correctly whether they are equal.

If you want to know whether they are identical, that's slightly more tricky: There are +0 and -0 which are equal but not identical, and there are NaNs (Not-a-Number) which are not equal, not even equal to themselves, but can be identical.

Now if you perform floating-point arithmetic, then it can happen that two calculations that should have given the same mathematical result do give different results due to rounding errors. It can also happen that two calculations that should have given different mathematical results do give the same result.

There is no quick and easy rule. You need to think about what your goal is, and how to achieve it. And every case is different.

PS. (4) is just awful. Totally, totally wrong. If you use double precision and one of x, y is greater than 10^160, then almost any two numbers will be considered "equal" by this code.

PS. (1-3) are equally awful, because they claim that 0 ≠ 0.

PS. (3) is awful - it completely destroys the idea of gradual underflow.

PS. As a rule, you should use double precision instead of single precision, unless you have a very good reason not to; a reason that you can explain and defend.


How can I generate Rubik's cube algorithms equivalent to a given algorithm? I am developing a computer program that solves the Rubik's cube. It is not anything advanced nor fast. It solves the cube by the Friedrich method, using algorithms that I use in real life to solve the cube. Because of that, the output solving algorithm is quite a long one and I was wondering is there is a way to transform the output to an equivalent algorithm, but shorter. This might actually be impossible, but I think this is a question worth asking. For example here is a list of equivalent algorithms that orient the corners of the last layer of that cube state shown in the image.

L.E.:
Friedrich splits the solve in 4 steps(cross, inserting corners and their corresponding edges(F2L), orienting the last layer(OLL) and permuting the last layer(PLL)). So far my program only solves the cross, and I am now beginning to code the algorithms for the second step(F2L). All the algorithms I find online for F2L, OLL and PLL are designed to be remembered and/or executed as easily and naturally as possible, so they are not necessarily the shortest ones. Using Kociemba's program I can find shorter algorithms equivalent to those used by humans only for PLL, where the entire cube stays the same except for the edges and corners of the last layer. This is because Kociemba only gives the algorithms that leads to complete solve of the cube(and only for PLL we need this solution). For F2L for example I don't know what configurations I should put the cube in in order to output the algorithm that only inserts the desired pair(corner and edge) in the correct place and doesn't care about the cubies in the last layer, or the cubies in the other corners(that are not solved yet). I hope that makes sense. I make this program for a project for my Algorithms course, first year in CS and the requirements are that it must solve any given state of the 3x3x3 cube and output the shortest solution. I know group theory can be used, but it is much more complex and requires more time than I was given to finish the project, so I thought that Friedrich would be easier to achieve.

So far my outputs an algorithm for solving the cross that averages at 10 moves with a maximum of 19 in half turn metric. The execution time varies from 0.02 to 0.03 seconds per cube. This data was obtained from running the program on 1500 randomly generated cube states.

Solutions

Finding solutions of a Rubik's cube is infeasible by enumeration (BFS - too much space required), DFS takes too much time and does not guarantee the optimal solution, I highly doubt that optimal solution would be required.

There are at least three algorithms worth noting: Kociemba's algorithm, Thistlewaite's algorithm and Iterative deepening $A^*$ (Korf's). Here is a methods comparison. Iterative deepening needs admissible heuristic, which for Rubik's cube is the sum of 3D Manhattan distances calculated separately for corners and cubies. Due to Korf, it also needs pattern database to achieve optimal solution in reasonable time.

Algorithm Optimization

For optimizing any given algorithm all above will work in reasonable time, including BFS for short algorithms. To make small number of turns in overall solution the structured system should yield low number of turns in average, Friedrich method is mainly used for manual solving with medium number of algorithms (more than 100 is huge number to learn at once, not that challenging to program), so instead of optimizing single steps it would be better to find system that scores better. For example ZBLL method with 493 algorithms (including mirrors) with average about 40 turns, Friedrich scores about 56.

Solving Between States

This step is inevitable: the modification of the stop condition in the search tree - at some point while processing partial algorithm the stop condition should be changed to check only target pieces and already solved ones. There is no good way to mitigate this effect, at initial phases enumerating all possible permutations of the cube is too memory and time consuming. Searching for shorter algorithm without changed condition (via ready to use solver or own algorithm) will yield very long solution, because all pieces will be preserved e.g. the last layer while solving the middle layer. To really improve the overall score instead of shortening given moves it is far more valuable to implement look ahead (e.g. better last layer orientation while solving the second one, or increasing number of algorithms possibly merging phases together).

There is also Hamilton circuit for Rubik's cube with included graph for cosets - this is not a full solution, but still worth reading.


Meaning of topological distance between 2 pixels I came across the notion of topology and topological distance in the context of image processing several times (especially when it came to mathematical morphology). I looked for a not too abstract explanation of "topological distance" but haven't found one yet. Can you please explain (in layaman's terms) the notion of topological distance between 2 pixels? And what's the difference between a euclidean distance and a topological distance in image-processing?

Nonlinear Signal and Image Processing: Theory, Methods, and Applications defines topological distance as follows. First, you have to define when two pixels are neighbors. The book offers two possibilities:

The neighbors of a pixel are the 4 "cardinal" pixels around it.
The neighbors of a pixel are the 8 pixels surrounding it.

This defines a graph (two pixels are connected by an edge if they are neighbors). The topological distance between two pixels $p,q$ is then the graph distance between $p$ and $q$.

The first choice above corresponds to $L^1$ ("Manhattan") distance, and the second choice to $L^\infty$ distance. This contrasts with the usual $L^2$ (Euclidean) distance.


First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS I am trying to state, whether the statement is true: During a DFS/BFS, first time visited nodes form a spanning tree, that has the same number of edges whether you use DFS or BFS. Is it true?

What I tried was to do both DFS and BFS on a couple of graph and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ, that's why I ask here.

Thanks

What I tried was to do both DFS and BFS on a couple of graphs and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ.

Indeed, the spanning trees formed by the first-visited nodes might be different from DFS and BFS. For example, try a cycle graph of four vertices. When the spanning tree are different, the number of edges is still the same for both.

You might have noticed that the number of edges is always one less than the number of vertices of the graph, either by concentration or by luck, had you been playing with connected graphs long enough.

In fact, the number of edges in every spanning tree of a connected graph is always one less than the number of vertices in that graph. This comes from the following two facts.

The number of edges in a tree is one less than the number of vertice of that tree.
The vertices in a spanning tree of a connected graph are the vertices of that graph.

Exercise. What about disconnected graphs?


Need help optimizing the loading of passengers on small airplanes I work for a small non-profit that provides transportation for people who need medical treatment. We connect volunteer private pilots who fly people in their own (small) aircraft, typically 3-5 seats.

Several times each year, we provide flights for kids to go to special needs camps. In this scenario, we have a number of kids (say 20-30) going from multiple origins to one destination, and several pilots who have expressed an interest in flying one of the routes. We'd like to create an algorithm to optimize the loading and travel of each aircraft. The number of seats is a constraint, in other words, we can't have more passengers than there are seats. Optimizing loading would mean (I think) minimizing the difference between the airplane's load capability and the total weight of the passengers. A second factor would be how far the pilot would need to go out of their way to complete the trip, based on where the plane is based. For that, we can look at a multiple of the trip distance. So, if the plane is based at either the origin or the destination of the route, the multiple would be 1 (total distance divided by trip distance), whereas the multiple will grow the more they have to go out of their way.

I'm a programmer and not a mathematician, and I would love to have any guidance anyone is willing to provide as to an approach.

This is an optimization problem.

The first step is to work out more precisely what your objective function is.  In other words, given a candidate assignment of pilots, you need a well-specified way to compute a single "goodness value" for that assignment.  That's your objective function: an objective function maps a candidate solution to a number indicating how good the candidate solution is.  Once you have defined an objective function, you then have a well-defined optimization problem.

Right now, it sounds like you haven't yet settled on a specific objective function.  You mention some possible factors, but the question isn't completely precise about how exactly those factors should be measured or how to weight the individual factors and combine them to get a single number.  Generally you can't solve the optimization problem until you formulate an objective function that gives you a single number (otherwise the notion of a "best" solution isn't well-defined).

Once you can do that, you could look at expressing this as an integer linear programming problem.  See, e.g., integer-programming.

The kind of problem you mention generally falls into the field known as "operations research".

Alternatively, with only 15-20 kids, you might even be able to write a program that exhaustively enumerates all candidate solutions and scores each one.  There will be exponentially many candidate solutions but if the number of kids is small enough it might be feasible to enumerate them all.  15-20 kids is probably on the edge of what could be computed in a reasonable amount of time, so this might fail badly, and you might need to resort to combinatorial optimization methods, such as integer linear programming.


is there a sorting algorithm of order $\log n!$ Is there any sorting algorithm that takes order of $\log n!$ in the worst case? I know that this is the lower bound for sorting algorithms using comparison based sorting. I know that there are algorithms of order $n\log n$, but since $n!$ grows much slower than $n^n$, I wish to know of there is any algorithm of this order.

By Stirling's approximation, $$\log(n!) = n\log n - n + O(\log n) = \Theta(n\log n)\,,$$
so, yes, there are lots of sorting algorithms that run in time $O(\log(n!))$.


Why is the usual simulated annealing algorithm using a Boltzmann probability? I've coded a personal version for the simulated annealing problem, and I was wondering why, (other than by analogy to the physics), the probability is
$$ p = e^{-\dfrac{\Delta \text{length}}{T}}$$ (assuming we're applying to the TSP problem, so the parameter is here the length of the circuit).

Is there any way to explain why this law and not another? Is this one optimal?

This formula can more insightfully be written as

$$ p = \frac{1}{e^{\dfrac{\Delta E}{T}}}$$

where, in the context of SA, $\Delta E$ is the difference between the "energy" (or quality) of two possible solutions and $T$ is the temperature (which is either a constant or a function of the input size).

So, the higher the energy difference $\Delta E$, the smaller the probability $p$. In the context of SA, if the cost of the current solution is greater than the cost of the new solution, then you replace the current solution with the new solution. However, if the cost of the current solution is smaller than the new solution, then you do not automatically discard the new solution. More concretely, with probability $p$, you accept the new worse solution. This the stochastic action taken by SA. So, the higher the diffence between the costs of the current and new solutions, the smaller the probability of accepting the new worse solution.

The Boltzman distribution only happens to capture this idea of accepting new worse solutions, provided that they are not extremely worse than the current solution. In theory, you can use other (similar) distributions.


Performance of Recursive vs Iterative Solution to "Maximum Depth of a Binary Tree" I am looking at this question from LeetCode.

There are two solutions to this question - the recursive solution and the iterative / breadth-first traversal solution.

My question is in regards to the memory requirements of each solution.

In the case of the recursive solution, we are going to be using the call stack. The call stack will, at its max, be the height of the binary tree. In a worst-case scenario, the tree is skewed, the height is the number of nodes, and our space requirement becomes linear - O(n).

In the case of the recursive solution, we use an explicit queue, instead of an implicit call stack. The largest number of elements that the call stack will hold is when the tree is a perfect binary tree (a complete binary tree has the same analysis), in which case, the queue will hold 2^h, where h is the height of the tree (indexed at 0). However, in a perfect binary tree, we also know that h = log(n + 1), so 2^h ~ 2^log(n +1), which means that the space requirements for the iterative case is O(2^(log n)).

My question is, which one of these is smaller? Can we make a determination that one of these two algorithms is better than the other in terms of memory?

The obvious recursive solution (compute the maximal depth of both subtrees, add one for the root) has space complexity $O(\operatorname{depth}(T))$ (i.e., $O(\log n)$  for $n$ nodes). If you write it recursively or do the call stack by hand instead of having the language handle it for you is irrelevant.


Balanced Binary Search Tree Two-Sum with Constraints My question spawns from this question. The question is straightforward:

  Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value?

Now the constraints:

Constant additional space in regards to $n$, the size of the tree. By this I mean you can use a constant number of $O(\log n)$ bit words however you wish. Assume references to nodes also take $\log n$ bits to store.
Read-only access to the tree. No modifications are allowed. This prevents a threaded traversal.
A node n has the following attributes: n.left, n.right, n.value. This means we have no access to a node's parent. This prevents a successor and predecessor traversal.
The algorithm must run in worst-case linear time in regards to $n$, the size of the tree.

It's worth noting that if we remove any one of the four constraints, we can satisfy the the other three relatively easily.

My initial thought is that this is not possible. Simply because we can have no memory of where we are in the tree when traversing it.

We could however implement a successor and predecessor in-order traversal using binary searches to find successors and predecessors. This would take $O( n \log n)$.

Another thought was that we could use a non-deterministic algorithm. Possibly a Monte Carlo algorithm with repetition or a Las Vegas algorithm. This randomized algorithm could be used to do a random walk along one path, then have another path search for a compatible node based on the random walk's nodes. I'm not entirely sure if this would work, but these are just some thoughts.

If this is indeed not possible, as I am suspicious, I would also be interested in the following additional modification:

The algorithm must run in average-case linear time.

I don't know how to do this is in $O(n)$ time and $O(1)$ space, but I can show you how to do it in $O(n)$ time and $O(\lg \lg n)$ space.  In particular, given any tree of depth $O(\lg n)$, I'll show how to do an in-order traversal in $O(n)$ time and $O(\lg \lg n)$ space.  That will be enough to solve this problem.

Warmup

Let me first establish some notation.  At any point in the traversal, we'll currently be at some leaf node $x_1$.  Let $x_1,x_2,x_3,\dots,x_d$ be the nodes on the path from $x_1$ to the root (so $x_1$ is the leaf and $x_d$ is the root of the tree), where $d$ denotes the depth of the tree.  Note that since the tree has depth $O(\lg n)$, it follows that this sequence has length $O(\lg n)$.

For convenience, I'll assume that the tree is a complete binary tree, i.e., all leaves are at the same depth.  This simplifies explanation of the main ideas.  All of the techniques here generalize to an arbitrary binary tree, as long as its maximum depth is $O(\lg n)$.

An easy way to do a traversal would be to keep track of the entire sequence $x_1,x_2,x_3,\dots,x_d$.  When you want to find the successor, you update the entire sequence.  For instance, if $x_1$ is the left child of $x_2$, this involves updating just $x_1$ to its right sibling.  If $x_1$ is the right child of $x_2$ and $x_2$ is the left child of $x_3$, this involves updating $x_1$ and $x_2$.  And so on.  Notice that as we repeatedly compute the successor, the first parts of the sequence get updated more often: $x_1$ changes every time, $x_2$ changes half of the time, $x_3$ changes $1/4$ of the time, and so on.  This gives an $O(n)$ time traversal (since $1 + 1/2 + 1/4 + \cdots = O(1)$), but it requires $O(\lg n)$ space.

The main attraction

Our improvement will be to store only part of that sequence: we'll store $x_1,x_2,x_4,x_8,\dots,x_k$ (where $k=2^{\lfloor \lg d \rfloor}$).  In other words, we're only storing the power-of-two-indexed elements of the path from the current leaf to the root.  Since $d=O(\lg n)$, we're only storing $O(\lg \lg n)$ elements of the sequence.

When we want to find the successor, we might need to update one or more of these elements.  As we repeatedly iterate compute successors, the early parts change more often: $x_1$ always changes, $x_2$ changes $1/2$ of the time, $x_4$ changes $1/2^3$ of the time, $x_8$ changes $1/2^7$ of the time, $x_{16}$ changes $1/2^{15}$ of the time, and so on.  How do we do the updates?  To see if $x_2$ needs to change, we go down from $x_2$ to $x_1$ to find the successor to $x_1$.  If $x_2$ doesn't need to change, we're done.  Otherwise, we go down from $x_4$ to $x_2$ to find the successor to $x_2$ (at the same height as $x_2$).  And so on. When $x_{2^i}$ changes, we go down from $x_{2^{i+1}}$ to $x_{2^i}$ to compute the successor to $x_{2^i}$ at the same height, and this takes $2^i$ steps of computation since we have to traverse $2^i$ levels of the tree; this happens for a $1/2^{2^i-1}$ fraction of the successor operations.  Taking all of that into account, the amortized amount of work we do per successor operation is

$$1 + {2 \over 2} + {4 \over 2^3} + {8 \over 2^7} + {16 \over 2^{15}} + \cdots
= O(1).$$

This yields an in-order traversal that takes $O(n)$ time and $O(\lg \lg n)$ space.

Bonus answer

As an extra bonus, I'll show how to do an in-order traversal in $O(n \lg^* n)$ time and $O(\lg^* n)$ space.  $O(\lg^* n)$ "might as well be constant" for all practical purposes, so maybe this is of interest.

The construction is a small modification of the scheme I gave above.  Define $a_1,a_2,a_3,\dots$ by $a_1 = 1$ and $a_{i+1} = 2^{a_i}$.  Now, instead of storing the whole sequence $x_1,\dots,x_d$, we'll store just the elements $x_{a_1},x_{a_2},x_{a_3},\dots,x_{a_\ell}$, where $\ell= \lg^* d = \lg^* (\lg n)$.  Notice that $x_{a_i}$ changes for a $1/2^{a_i-1}$ fraction of the successor operations, and when it does change, we do $a_{i+1} - a_i$ work.  Therefore, the amortized time per successor operation is

$$T = \sum_{i=1}^\ell {a_{i+1} - a_i \over 2^{a_i-1}}.$$

With a bit of manipulation we can show

$$T \le \sum_{i=1}^\ell {a_{i+1} \over 2^{a_i-1}} = \sum_{i=1}^\ell {1 \over 2} = \ell/2 = O(\lg^* (\lg n)) = O(\lg^* n).$$

Therefore, a traversal of the entire tree can be done $O(n \lg^* n)$ time, using $O(\lg^* n)$ time.


Where am I wrong?: "countability" and "recursive enumerability" I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong with the statements/proofs i have made?

Countability (C=Countable): A set $X$ is C when a bijection exists between the set of natural numbers and the set $X$

Recursive Enumerability (RE= Recursively Enumerable): Say set $S'$ is a subset of another set $S$. When there exists a turing machine with alphabet $A$ (where $S$ is a subset of $A^*$) which halts if the input to it belongs to the set $S'$ and does not halt if the input belongs to $S-S'$ then I say that the set $S'$ is recursively enumerable (given the fact that inputs comes only from the set $S$ and not from $A^*-S$ hence the latter will not concern us.) I have referred to the book "Elements of the theory of Computation" by Papadimitrou for this definition, though the introduction of an alphabet A is my own addition to make things more firm

Now I will prove 2 statements:

if a set $X$ is RE then it is C
if a set $X$ is C then it is RE

Hence proving 3. RE iff C

I will prove 2 first.

I can write a Turing Machine $M$ which when asked to check if an element $x$ belongs to $X$ or not will follow the algorithm:

There exists a mapping from the set of natural numbers to $X$ call it $f$. $M$ can search for $x$ (like a linear search algorithm running on $X$) starting from $f(1)$ going to $f(2)$... and it keeps going till it finds $x$. By this method, $M$ terminates iff $x$ belongs to $X$.

The behaviour above proves that $X$ is RE

Now I prove 1- Given a Turing Machine $M$ exists which halts iff $x$ belongs to $X$

I can construct a bijective map from the set of naturals to $X$ as follows: To map $x$ (given it belongs to $X$) , we run it as input against $M$. I take the concatenation of all configurations (Configuration=tape head position+tape content+state) of $M$ which it goes through from the starting of a computation to the end and decode that string as a natural number. It will be unique.

Hence 1. is proven and so is 3.

But then I find certain resources on the internet which tell me that enumerability and recursive enumerability are different things. How is it possible? Furthermore- We know that the power set of a countably infinite set is uncountably infinite. If $X$ was countably infinite, it would be RE (see 2.). Now we know that the subset of a set which is C is also C. Hence all subsets of $X$ would be C hence they would be RE. Now there would be an uncountable number of RE sets.

Now for each RE set, we can write a turing machine (with appropriate halting behaviour) which can be encoded as a natural number implying that the "set of all RE sets" must be C. This contradicts the conclusion of the previous paragraph.

Where exactly am I wrong?
Thankyou in advance!

Your algorithm for recursively enumerating any given set doesn't work since the bijection between a countable set $X$ and the natural numbers can be arbitrarily complicated. For example, consider the following set $X$:
$$ X = \{ P : \text{the program coded by $P$ doesn't halt on the empty string as input} \}. $$
The set $X$ is countable: there are only countably many programs. However, there is no computable bijection between $X$ and the natural numbers, since otherwise RE=coRE (as your argument shows; $X$ is coRE-complete).

Here is a more tangible example of a countable set for which there is no computable bijection:
$$ Y = \{ 2P : \text{program $P$ halts on the empty string} \} \cup \{ 2P+1 : \text{program $P$ doesn't halt on the empty string} \}. $$
If there was a computable bijection between $Y$ and the natural numbers, then you could solve the halting problem (how?).


Formal proof of language accepted by a specific CFG Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules:
\begin{align}
&S \to aS \mid B \\
&B \to abBc \mid \epsilon
\end{align}
Please provide a formal proof for the following claim:
$$
L(G) = \{ a^i (ab)^j c^j : i,j \in \mathbb{N} \}.
$$

Let $L = \{ a^i (ab)^j c^j : i,j \in \mathbb{N} \}$. The proof consists of two steps:

$L \subseteq L(G)$.
$L(G) \subseteq L$.

The first step proceeds by direct construction: we show how to produce each word in $L$ using the grammar. In order to produce the word $a^i (ab)^j c^j$, we first apply $i$ times the rule $S \to aS$, then once the rule $S \to B$, then $j$ times the rule $B \to abBc$, then once the rule $B \to \epsilon$. Formally, we could prove that this works by induction.
For the second step, we first prove by induction that all words generated by $B$ are of the form $(ab)^jc^j$. We show that by induction on the length of a production starting at $B$. If the first step is $B \Rightarrow \epsilon$ then we generate $\epsilon$. Otherwise, the first step is $B \Rightarrow abBc$. By induction, the $B$ on the right produces a word of the form $(ab)^jc^j$, and overall the produced word is $(ab)^{j+1}c^{j+1}$, which is of the same form.
We can now prove the required claim by induction on the length of a production starting at $S$. If the first step is $S \Rightarrow B$, then the preceding paragraph shows that the generated word is of the form $(ab)^jc^j$. Otherwise, the first step is $S \Rightarrow aS$. By induction, the $S$ on the right generates a word of the form $a^i (ab)^j c^j$, and overall the produced word is $a^{i+1} (ab)^j c^j$, which is of the required form.


decidability about NFA accepting an input Let A = {(B,w) | B is an NFA that accepts w}. To prove that N is a decidable language,

M = "on input (B,w) where B is NFA and w is a string, simulate B on w. If B accepts w, accept. Otherwise, reject"

Is this a false proof? The proof from the textbook says that I have to convert NFA into equivalent DFA but I'm not sure why this would be necessary. Is it not possible to simulate NFA directly without conversion?

The textbook probably suggests you convert into a DFA because  it is easier to simulate a DFA than to simulate a NFA and determine whether the DFA accepts the word w.  This is trickier on a NFA (but still possible, if you know how).


Monte-Carlo algorithm for clustering I have written an algorithm for clustering data-points with their nearest neighbours with a Euclidean distance metric. I estimate its complexity to be $\mathcal{O}(n \times k)$ for $n$ data-points with $k$ genuine clusters. The dimension $d$ of the data results in $\mathcal{O}(e^d)$ complexity, though I believe this can be mitigated.

The algorithm is Monte-Carlo, resulting in an approximate solution. In pseudo-code, for data transformed to a unit hypercube:

radius = 0.15 # This should be fine-tuned for problem.
mode_number = 0 # Label for mode currently being investigated.

while length(data) > 0:

    mode_number += 1
    branching = True
    point = data[0] # i.e. first data point.

    while branching:
        within_radius = [] # Make this list empty.
        for item in data:
            if Euclidean_Distance(item,point) < radius:
                within_radius += point # List of points within a sphere.

        if length(within_radius) == 0:
            branching = False
            continue

        point = Pick_Random_From(within_radius) # Next point.
        data = data.Remove_From_Data(within_radius) # Remove neighbouring points from data.
        mode[mode_number] += within_radius # Add points to mode.

Although the for item in data loop contributes a complexity $\times$ length(data) each pass, length(data) shrinks rapidly, resulting in only $\times n$ complexity. In fact, the length(data) shrinks linearly with iteration (with a saw-tooth behaviour), e.g.

where branch is incremented every time while branching is passed, and number of deleted is the number of points removed at that pass of while branching. That result is from 3 Gaussians with 1000 points sampled from each Gaussian. My code identified six modes:

Modes: 6
Mode 5 , points: 1000
Mode 3 , points: 932
Mode 0 , points: 829
Mode 1 , points: 168
Mode 4 , points: 68
Mode 2 , points: 2

though only three substantial, which wasn't too far off.

The algorithm starts at a point, finds its nearby neighbours, and deletes them from the data list, and repeats from a point within those nearest neighbours. If a point has no nearby neighbours, it begins a new mode. If the data-points are spread in many modes, the algorithm requires more iterations to clear all the modes, resulting in $\times k$ complexity.

The dimension of the data limits performance. In higher dimensions of space, points are more "spread-out", e.g. a sphere radius $r$ takes up an $(r/R)^d$ fraction of the space, which shrinks exponentially with increasing $d$. This, I think, could be mitigated somewhat by increasing radius = 0.15 in my algorithm. This is justifiable - with larger $d$, more of the space in a unit hypercube is "around the edges".

So overall I estimate complexity: $\mathcal{O}(n\times k\times e^d)$. Is my analysis reasonable? Is the working of the algorithm clear?

I suspect this clustering algorithm is going to give a poor quality clustering.  The cluster heads are chosen just about arbitrarily (randomly, essentially) and then points are assigned to a cluster if they are near a cluster head or near some other randomly chosen points in the cluster.  The whole algorithm looks unprincipled and I have serious doubts about the quality of the clustering it will produce.

Of course, if the clustering is of low quality, then it just doesn't matter what the running time is.  I can suggest an extremely fast algorithm if you don't care about the quality of its output....

As far as running time, it will depend upon the distribution of the input points.  If the input points are distributed uniformly across the input space, then I would expect that each iteration of the inner loop will remove roughly a $0.15^d$ fraction of the input points.  This suggests that you'll need to do about $1/0.15^d \approx 2^{2.7 d}$ iterations.  Each iteration takes about $O(n)$ distance computations, and each distance computation takes $O(d)$ steps, so I'd expect the running time to be something like $O(n d 2^{2.7d})$.  That's dominated by the exponential factor, so the worst-case running time estimate is very bad, in high dimensions (e.g., $d \approx 100$).  Welcome to the curse of dimensionality.

This algorithm does not look promising to me.  Of course, before drawing any serious conclusions, you'd need to do a serious evaluation of both its running time and the quality of its clustering, on relevant input distributions, as compared to other standard clustering algorithms.  So, if you want to seriously pursue this direction, you need to start studying the state of the art and work on performing such a careful evaluation.  But personally, I think your time would be better spent by starting to look at what's available in the literature and seeing if you can make any standard algorithm work for your application.


What linked list data structure adjustments would give me fast random lookup? I am presently using an doubly linked list (C++ std::list) to hold a bunch of records that each have a unique integer identifier.  The linked list is created in sorted order such that in the list, the next item always has a larger unique identifier than its predecessor.

The issue I'm facing is that occasionally I need to be able to insert an item quickly into its  relative sorted position and using a plain linked list means this operation is $O(n)$ which is causing performance issues for me.  Generally, this would mean I want to use something like a binary tree (C++ std::map), however, I am also depending upon the following feature of a doubly linked list for good performance:

Ability to splice a contiguous section out of one linked list into another in $O(1)$ time. (Amortized $O(1)$ or $O(\log \log n)$ would be good enough.)

One feature of my data that I would like to leverage is that I often have long ranges of contiguous records where each one's unique integer is exactly one more than its predecessor.  When searching for an item's relative sorted position, it would always be outside such contiguous records since there are no duplicate identifiers.

I'd like to find a replacement data structure or augmentation to a doubly linked list that will allow me to continue to splice whole sections from one list to another in constant time but allow me to locate the sorted position in which to insert a new record in better than $O(n)$ time.

Other operations include forward and backward iteration across the items. The record indexes begin at zero and grow upwards towards 64 bits, generally sequentially, and the code works well in such cases. Occasionally some records are not available before subsequent ones, it is the insertion of these missing records that causes the performance issues now.

One possible approach that occurs to me is to cache the location of several indexes.  The cache would get invalidated whenever a splice removes items that might overlap the cached entries.  With this cache, instead of doing a linear search, the search could instead begin from the cache point iterator whose unique index is closest to the one whose position is being  searched for.  However, I'd like to more fully utilize the feature of the contiguous records.  I also thought about a hierarchical linked list where I have a top level linked list of contiguous regions, where each region is a linked list of records that are consecutive, but I didn't see a clean way to adapt a linked list to provide this functionality.  Perhaps something like this has been done before?  I find skip lists to be close, but do not see the splice() functionality, plus a generic skip list would not leverage the fact that insertion never occurs within contiguous records.

One simple approach might be to use a doubly-linked list of extents, where each extent represents a sequence of contiguous records.  The records within each extent could in turn be represented with a doubly linked list.

This preserves your ability to do $O(1)$ time splicing, and now the insert operation takes $O(k)$ time, where $k$ is the number of extents (rather than $O(n)$, where $n$ is the number of records).  If you have many fewer extents than records, this might be a partial improvement.

I don't know whether this will be better than a simple skip list or binary tree.

Note that if you use a binary tree, you can still do efficient splicing.  The splicing operation is no longer $O(1)$ time, but it can be done in $O(\log \ell)$ time, where $\ell$ is the number of records in the spliced segment.  This is not as fast as $O(1)$ time splicing, but depending upon the relative frequency of your different operations, it is another data structure you could consider (e.g., benchmark on realistic data sets).

And, of course, you could combine these ideas, e.g., with a binary tree of extents, where each extent is in turn a doubly-linked list of contiguous records.  Inserts will take $O(\lg k)$ time, and splicing can be done in $O(\lg \ell)$ time (both of which might potentially be better than the $O(\lg n)$ achieved through a simple binary tree).


Longest Common Sequence reduction proof question I'm trying to get at least a laymans understanding of how the Longest Common Sequence (LCS henceforth) can be shown to be NP-Hard and I'm trying to do that by reducing it to an NP-Complete problem like Vertex Cover. I read through this downvoted question on another stack exchange.

  I am trying to understand the demostration of intractability of the
  LCS problem, as stated as a reduction from Vertex-Cover problem, and
  so far, i'm stuck with the demostration of the problem in this paper
  from David Maier

  Anybody know some simple example to reduce LCS from Vertex-Cover?

With a self answer of

  It was as simple as:

  Take a Vertex-Cover problem to convert to LCS
  Create a string template from the Vertex-Cover graph
  Take each vertex from the Vertex-Cover problem and generate an equivalent string for it, ommiting the vertex selected
  Presto, you have a LCS problem equivalent.

  Thanks for the downvotes

I've been trying to work out on paper how this makes sense but keep coming up against a wall. Could someone show me how this is either incorrect or how it is correct with a more worked out example/proof?

We can prove that LCS (with an unbounded number of sequences!) is NP-hard by reduction from 3SAT. Let us be given a CNF $\varphi$ with $m$ clauses $C_j$ of the form
$$
(x_{i_{j,1}} = b_{j,1}) \lor (x_{i_{j,2}} = b_{j,2}) \lor (x_{i_{j,3}} = b_{j,3}).
$$
Here $b(j,c)$ is either T or F, and we assume that $i_{j,1},i_{j,2},i_{j,3}$ are all distinct.

We will consider the following strings:

$S_1 = x_{i_{1,1},1}^{b_{1,1}} x_{i_{1,2},1}^{b_{1,2}} x_{i_{1,3},1}^{b_{1,3}} \ldots x_{i_{m,1},m}^{b_{m,1}} x_{i_{m,2},m}^{b_{m,2}} x_{i_{m,3},m}^{b_{m,3}}$.
$S_2 = x_{i_{1,2},1}^{b_{1,2}} x_{i_{1,3},1}^{b_{1,3}} x_{i_{1,1},1}^{b_{1,1}} \ldots x_{i_{m,2},m}^{b_{m,2}} x_{i_{m,3},m}^{b_{m,3}} x_{i_{m,1},m}^{b_{m,1}}$.
$S_3 = x_{i_{1,3},1}^{b_{1,3}} x_{i_{1,1},1}^{b_{1,1}} x_{i_{1,2},1}^{b_{1,2}} \ldots x_{i_{m,3},m}^{b_{m,3}} x_{i_{m,1},m}^{b_{m,1}} x_{i_{m,2},m}^{b_{m,2}}$.

For each variable $x_i$, let $T_i$ be the string obtained from $S_1$ by removing all occurrences of $x_{i,j}^F$ (for all $j$), and let $F_i$ be the string obtained from $S_1$ by removing all occurrences of $x_{i,j}^T$.

For each variable $x_i$, $TF_i = T_i F_i$ and $FT_i = F_i T_i$.

Let $R$ be a common subsequence of all these strings.

For every $j$, the string $R$ contains at most one of $x_{i_{j,1},j}^{b_{j,1}},x_{i_{j,2},j}^{b_{j,2}},x_{i_{j,3},j}^{b_{j,3}}$. Indeed, suppose that it contained both $x_{i_{j,k_1},j}^{b_{j,k_1}}$ and $x_{i_{j,k_2},j}^{b_{j,k_2}}$, in this order. Since $R$ is a subsequence of $S_1$, we must have $k_1 < k_2$. However, if $k_1 = 1$ then $R$ cannot be a subsequence of $S_2$, and if $k_1 = 2$ then $R$ cannot be a subsequence of $S_3$.

Thus $|R| \leq m$, and if $|R| = m$ then we can associate with $R$ a choice of equation in each clause.

For every $i$, if $R$ contains both $x_{i,j_1}^{b_1}$ and $x_{i,j_2}^{b_2}$ then $b_1 = b_2$. Indeed, in any subsequence of $TF_i$ all symbols $x_{i,j_1}^T$ precede all symbols $x_{i,j_2}^F$, and in any subsequence of $FT_i$ all symbols $x_{i,j_1}^F$ precede all symbols $x_{i,j_2}^T$.

Thus the chosen equations are all compatible.

This shows that if $|R| = m$ then $\varphi$ is satisfiable. The converse is also easy to establish: given a satisfying assignment, we can choose a satisfied equation in each clause, and then concatenate the corresponding symbols.

Let us give an example. Consider the formula
$$
\varphi = [(x_1 = T) \lor (x_2 = T) \lor (x_3 = T)] \land [(x_2 = F) \lor (x_4=F) \lor (x_1 = F)].
$$
The strings are

$S_1 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$S_2 = x_{2,1}^T x_{3,1}^T x_{1,1}^T x_{4,2}^F x_{1,2}^F x_{2,2}^F$.
$S_3 = x_{3,1}^T x_{1,1}^T x_{2,1}^T x_{1,2}^F x_{2,2}^F x_{4,2}^F$.
$TF_1 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_1 = x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F$.
$TF_2 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_2 = x_{1,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{4,2}^F x_{1,2}^F$.
$TF_3 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_3 = x_{1,1}^T x_{2,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$TF_4 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_4 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{1,2}^F$.

One string $R$ of length $m=2$ which is common to all of these is $x_{1,1}^T x_{2,2}^F$. This corresponds to the (partial) truth assignment $x_1=T,x_2=F$, which satisfies $\varphi$.


Algorithm to sample high-dimensional parameter space of expensive cost function I am looking for recommendations for algorithms (apparently this is the right SO site for that) that efficiently scan the high-dimensional parameter space of a cost function that is very expensive to evaluate.

By expensive to evaluate I mean that one can only do O(1) evaluations per second on a modern computer.
By efficiently I mean that the algorithm should learn to avoid regions where there are no solutions: the evaluation of the cost function may fail for certain sets of parameters.
Still under the aspect of efficiency, the algorithm should yield a set of samples that represent a (ideally unbiased) coverage of all solutions in the whole parameter space within a reasonable number of samples.
The parameters are continuous numbers within predefined bounds.
The cost function is "mostly well-behaved".

I am not so much after importance sampling, so I guess I am looking for an improved random sampling that is adaptive in the sense that it learns which parts of parameter space to avoid.
Background information:
I am looking into a specific physics model where from ~20 input parameters a set of outputs (masses and decay probabilities) are computed. This is the bottleneck CPU-wise. My goal is to identify allowed ranges for the input parameters for which the outputs fulfil certain constraints that are implemented in terms of a cost function. Not all possible combinations of input parameters give meaningful physics, therefore a large (but acceptably so) fraction of calculations will fail.
At the moment I am successfully using parallel simulated annealing to find solutions (input parameters) that come very close to the known minimum of the cost function. So finding a (nearly) optimal solution is "easy".
What I would now like to improve is the coverage: sampling from the whole input parameter space (e.g. below some threshold of the cost function).
This would allow projections onto 1-D or 2-D subspaces of the input-parameter space to be done to see where valid models lie.
In this example

the yellow bin holds most of the samples because the cost function depends on this particular output such that it ought to be close to 125. The interesting part though is the dependence of the output on the input. One can guess from the plot that lower values of the input would also give the desired output, and below ~ 1000 we see some structure, where the input apparently is too low to achieve the desired output. However, the statistics is very low. Therefore, I am looking for another algorithm which yields a sampling that covers input-parameter space more evenly (subject to the constraint that invalid input parameter sets should be avoided).

I don't know how to sample from the space of nearly-optimal solutions, but I'll share one approach you could consider.
It appears that you want to estimate the density of good solutions, at different points in the input space.  It appears you are gridding up the parameter space and estimating the density in each cell of the grid.  Here is a possible alternate method to do that.
Suppose we have a cell $C \subseteq \mathbb{R}^{20}$ in the parameter space, which might take the form $C = [\ell_1,u_1] \times \cdots \times [\ell_{20},u_{20}]$, i.e., $\ell_i$ is the lower bound on the $i$th coordinate and $u_i$ the upper bound.   Let $V(C)$ be the volume of cell $C$.  We'll estimate the density of good solutions in $C$.  Pick a volume $v$ that is a fraction of $V(C)$, let $\alpha=v^{1/20}$, and then repeat the following 100 times:

Pick a random point $w \in C$.  Form the smaller cell $C_x = [w_1-\alpha/2,w_1+\alpha/2] \times \cdots \times [w_{20}-\alpha/2,w_{20}+\alpha/2]$.  Use your optimization method to search whether there is a good solution in the cell $C_x$.  (For many optimization methods, it is easy to enforce constraints that set an upper and lower bound on each coordinate in the parameter space.)

Now based on the number of times that you were able to find a good solution, you can form an estimate of the density of good solutions in $C$.  If this count is close to zero, double $v$ and repeat.  If this count is close to 100, halve $v$ and repeat.  Repeat until you get a count that is not too close to 0 or 100, and the result should give you a pretty good estimate of the density in $C$.
You can now iterate this, once per cell $C$, and use that to produce the kind of plot you are hoping for.
Here I've adopted standard methods for #SAT, i.e., for estimating the number of solutions to a SAT instance, to your specific problem.


What is the time complexity of this binomial coefficient algorithm? Here's a naïve algorithm that computes $ \binom{n}k $ (or "n choose k"), with either $k=0$ or $1\le k \le n$:

def coefficient(n, k):
    if k == 0 or k == n:
        return 1
    return coefficient(n-1, k-1) + coefficient(n-1, k)

Now the time complexity has to be bounded by $2^n$, however we have to take $k$ into account. The best cases are when k = 0 or k = n. So, with k and n decrementing, we get the most branching when $k = \frac{n}2$.

I'm looking for the worst case time complexity. I can write the recurrence relation, but I don't know how to go from here:

$T(n,k) = T(n-1, k-1) + T(n-1, k) + constant$

The only way that your algorithm can compute ${n \choose k}$ is by adding ${n \choose k}$ 1's together.

Now prove it.


What types of string properties are verifiable in polynomial time? When given the string and the property in question as a potential certificate. Is there any classification theorem that says something along the lines of: all properties (of strings) that have this property (as a sub property) are verifiable in polynomial time?

Are there any collections of types of patterns in strings that are verifiable in poly time?

A trivial property is that a collection of strings with these properties belong to a language in NP (belonging to NP being the sub property).

I'm looking for something more concrete.

I'm looking for the common thread between string properties like these that makes these properties verifiable in poly time for any string.

i.e. is there a way to pick properties of strings out of a hat in such a way that the properties you pick are guaranteed to be verifiable in poly time in any string.

Maybe there is a way to do this with implicit complexity--where the only properties you can build (in some restricted language) are the ones that are verifiable in poly time?

Verifying a property of strings over an alphabet $\Sigma$ is precisely the same problem as checking whether a string is part of a language, called the Entscheidungsproblem or decision problem.

Language : $\Sigma^* \mapsto \{0,1\}$

What you are interested in are 'properties of strings' or in other words 'classes of languages'.

The class you are probably looking for is 'P', which contains all languages for which the decision problem can be solved in polynomial time on a deterministic Turing machine. Interestingly this class is the same as the class of languages for which the decision problem can be solved by polynomial circuits.

All C programs which contain constantly bounded loops belong to P for example (they can easily be turned into a polynomial circuit).
From there you can extend the language to include other loops that terminate in polynomial time. You have to be careful with nested loops. There are special Hoare-type logics for this purpose.


Determining set of states that satisfy a CTL formulae I'm trying to understand CTL formulae, and until now I've understood everything (or at least I thought I did). I have the following Kripke strucure:

Now given the following CTL formulae A(g U EG (b v y)) , which states does it satisfy?

I know that the answer is {s1,s2,s3} (according to lecture notes), but I don't understand that.

This is what I have tried so far to solve it:

I solve EG(b v y) first and for this I get {s1,s3} because from these states there exists a path where either b or y holds globally.
Then I group it together again and solving A(g U EG(b v y)) which I understand as "Along all paths, g holds until there exist a path where b or y holds" and as I already know the last part of it, I understand it as "Along all paths, g holds until either s1 or s3 holds".

To me s2 is the only obvious answer because g holds in s2 until y holds in s1. I don't understand why s1 or s3, is a part of the answer.

Anyone care to explain? Or at least show the steps you take to derive the answer?

The semantics of the "Until" operator allows for the eventuality to be satisfied immediately. That is, $pUq$ holds both in the computation $ppppq$, but also in $q$.

Thus, in your formula, the eventuality is satisfied immediately in states $s_1,s_3$, and satisfied within 1 step in $s_2$. But all of them satisfy it.


What is a 'dynamic entity' in computer science? I am doing some reading into computer science and how the computing system works in order to be ready for my 1st year at university doing a Computer Science degree. I came across a term within the definition for a computer system that I tried looking up for on the internet called 'dynamic entity'. The problem is, I couldn't specifically find the definition I was looking for that could explain simply what it meant. If there is someone who could explain this term for me in a simple, but easy to understand, explanation, I would be very grateful. Thank you.

The link I got the term from: https://books.google.co.uk/books?id=3ls6K2cJW_0C&printsec=frontcover&dq=computer+science+easy+reading&hl=en&sa=X&ved=0ahUKEwjz2r_cuIfkAhUxonEKHWBZAu8Q6AEIKzAA#v=onepage&q&f=true

The term can be found on page 4 of the book, where they explain what a computing system is.

There are no scientific term "dynamic entity", so meaning of this pair of words can be well stretched. In this particular case they could write something like "A computing system ... is a dynamic system", but apparently they didn't like the repetition, so they have decided to use a fuzzy word "entity". Also, there is a mathematical term Dynamical System, which doesn't have anything in common with what they are trying to say.

Essentially they mean that there is a lot of parts in a real computing system, which can change with time - hardware and software can be installed and uninstalled, software can be configured in many different ways, data comes into the system and gets out of it and so on. Sometimes even users and people, supporting a complex computing system, can be considered as a part of it.


Can we define a program by means of a walk of a graph induced by the category of types? After reading about Category Theory at https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ I was wondering whether we can represent any program by means of a walk of a graph induced by the category of types.

EDIT: rephrasing the question a little bit.

So, given the category of types where the objects belong to a set of types $V$ and the morphisms are a set of functions $F$ with $f : a \rightarrow b$, if we define a walk on this category as a sequence $v_0, e_{0,1}, v_1, ..., v_n$, with $v_i \in V$ and $e_{i,j} \in E \subset F$, with $E$ as the default set of functions of any given programming language (add, mul, <, etc.), the pure part of a program could be defined as a walk on this set $E$.

So, for example, a program to return the greatest of two integers could be represented as:

v0 -> e1 -> v1 -> e2 -> v2
(Int, Int) -> e1 -> (Bool, Int, Int) -> e2 -> Int

with:

e1 : (Int, Int) -> (Bool, Int, Int)
e1 x y = (x>y, x, y)

e2 : (Bool, Int, Int) -> (Int, Int)
e2 b x y = if b then x else y

given that e1 and e2 are part of the subset of morphisms.

So, is the definition of a walk and this set $E$  sufficient to represent the pure part of any program?

Consider the simply-typed $\lambda$ calculus: this is one of the simplest functional languages you can define.

It is very common to interpret it in a Cartesian closed category (CCC). Indeed, CCCs are the "ideal" categorical setting where to interpret simple types.

CCCs, being categories, admit morphisms composition and identity. Taking your definition of "walk" loosely, as a rough idea rather than a rigorous concept, I think you covered this aspect of CCCs.

However, they also allow products, which are not considered by "walking". Given $f:A\to B$ and $g:A\to C$ there is a unique morphism $\langle f,g \rangle: A\to B\times C$ satisfying a certain universal property. This is a way to craft new morphisms from old ones that "walking" does not consider.

There's even more. The main, fundamental property of CCCs is the "currying" adjunction. That is, there's a natural bijection between the set of morphisms $A\times B\to C$ and $A\to C^B$ (where $C^B$ corresponds to the functional type $B\to C$). So, given a morphism in one of this set, we can take the corresponding one in the other set. Doing this is important to interpret $\lambda x. \ldots$, and without that, we do not have a "lambda" calculus.

So, even in the simplest setting, interpreting a functional program is much more than "composing morphisms", or the proposed definition of "walking".


Who converts binary/machine code to electrical signals and how? I went through lots of blogs and posts but could not exactly figure out how the machine code is converted to electrical signals?

Any software program is compiled to machine code which is nothing but lots of 1s and 0s.
1 means high voltage e.g 5V and 0 means comparatively low voltage e.g. 0V or ground, what's the component which understands that okay I got 1(one) so I need to step up up the voltage to 5V and for 0(zero) I need to step down to lower voltage level and how it does that?

In old computer you actually had a row of switches on the front panel
that would allow entering 1s and 0s directly by hand in the registers
of the machines. But this is no longer done.

You never have 1s and 0s, unless you ask the machine to print its
internal information as a sequence of 1s and 0s. All information is
already in the machine encoded as voltage, or magnetic orientation, or
hole in a physical substrate, or some other physical form. Various
devices can perform the translation between these form: magnetic
heads, laser beams, electro-mechanical devices, electronic
circuits,etc.

Some form are better adapted at memorizing or transmission by various
means, while other (electrical signal notably) are better adapted at
processing, usually by complex systems of logical gates (and, or, not,
xor ...) and micro-memories (registers).

In general, binary/machine code is no longer entered by human beings,
but produced by a program (usually a compiler) by the computer itself,
or by another computer and then imported on some memory support or by
network. However, human beings can ask to have it printed as 1s and 0s
to check what the computer is using or producing. However this
requires transforming the single bit 0 or 1 in the computer as a
stream of bits to be interpreted by the printer as a request to print
an actual drawing (on screen or paper) od the symbol representing a 0
or a 1.

It is hard to give more details without your being more specific
regarding the source form and target form of the conversion. But it is
most often from binary to binary, with a different physical
representation.


Finding the Shortest path in undirected weighted graph Is there an algorithm for finding the shortest path in an undirected weighted graph?

All-Pairs-Shortest Path

Given a graph $G = (V, E)$ find the shortest path between any two nodes $u,v \in V$. It can be solved by Floyd-Warshall's Algorithm in time $O(|V|^3).$ Many believe the APSP problem requires $\Omega(n^3)$ time, but it remains open if there exists algorithms taking $O(n^{3 - \delta} \cdot \text{poly}(\log M))$, where $\delta > 0$ and edge weights are in the range $[-M, M]$.

The reasoning for this is upon close examination we see that the APSP problem can be solved by matrix multiplication. If we replace the operators to $\{\text{min}, +\}$ instead of $\{ +, \cdot \}$ we may use the framework for matrix multiplication to compute the solution. What is interesting is if there exists sub-cubic algorithms for the APSP problem, then there exists sub-cubic algorithms for many related graph and matrix problems [1].

[1] Subcubic Equivalences Between Path, Matrix, and Triangle Problems


Is concept of virtual memory about memory isolation or about ability to swap? Or both? Most reading I found about virtual memory, such as http://www.linux-tutorial.info/modules.php?name=MContent&pageid=89 or https://en.wikipedia.org/wiki/Virtual_memory always state that virtual memory is a concept that allows operating system to make it "appear as though you have more memory than you really do".

But isn't that what overcommit is about? Isn't whole virtual memory concept primarily about the fact that each process has an isolated virtual memory pool, thus being unable to read or modify other process memory?

If not, what is this technology of memory isolation within own virtual memory pools called?

I would say virtual memory is not only about making memory appear bigger than it is, but also about providing many other memory related abstractions, like dealing with pages that are currently not in main memory, adding properties to memory (i.e. non-executability), and standardizing the memory layout of each process. It also allows easy relative addressing in large continuous blocks of data, which might not be able to be allocated contiguously if there was no memory virtualization.

Overcommit in my opinion is less about making it appear as if you had more memory, but more about not actually allocating physical memory if there is no need to do so, like when you allocate a huge chunk of memory "just for safety" which you have no intention of actually using.

Also, you might be confused about what sets apart overcommit and virtual memory, as they are not really two different things, but overcommit is just a part of how Linux and other operating systems implement their virtual memory.

About your last question, I would say that this is just an instantiation of process isolation (https://en.wikipedia.org/wiki/Process_isolation), using the technology of virtual address space.


How to restore diagonal-symmetric matrix that has been shuffled? I have a square matrix M, which originally looked like this:

133 199 101 121
142 133 199 101
156 142 133 199
108 156 142 133
 (so symmetric around the diagonal). Not only that, but each diagonal is constant, so M'[i, j] = M'[p, q] if i + j == p + q , however it has been shuffled both row-wise and column wise. The only solution I could think of was brute forcing all permutations of the rows and columns which is O(n!*n!), which is obviously suboptimal. I also thought of the fact that in this specific matrix, the value counts are 1 2 3 4 3 2 1, but the original matrix is way bigger and there are many duplicate values.

The last idea I have is some sort of greedy reshufling that would work like so:

for each column, find the column that has the most similar values (albeit shuffled).
place them together
repeat until convergence
repeat for rows.
repeat 1-4, but this time take into account the ordering too.

That idea seems unsatisfying though.

The full data is not too huge, 5000x5000, and I only need to restore it once, so I'm not nessecarily looking for the most efficient way, just a robust and easy to implement solution.

First, note that the matrix can only be restored up to a permutation of the diagonal.
To illustrate on your example, when we swap two bottom rows and two left columns, the resulting matrix is also diagonal-symmetric:

133 199 101 121                             199 133 101 121
142 133 199 101        transforms to        133 142 199 101
156 142 133 199                             156 108 142 133
108 156 142 133                             142 156 133 199

So, the good news is, instead of searching for a row permutation and a column permutation, we can fix the order of the rows and permute only columns.
Indeed, if we took the original matrix and permuted the rows in any fixed order,
by permuting the columns in the exact same order, we get a diagonal-symmetric matrix.

Next, note that, before the permutations, the multiset of numbers in row $1$ was exactly the same as the multiset of numbers in column $1$.
The same holds for row $2$ and column $2$, and so on.

After permutations, say row $1$ landed at row $i$, and column $1$ landed at column $j$.
Then, the multiset of numbers at row $i$ is still the same as the multiset of numbers at column $j$.

Importantly, the problem seems to be about some large and more-or-less real data, so it is likely that the converse also holds: for any two rows, the multisets of numbers in them are different.
If not, perhaps what follows can be tricked to fail by constructing the appropriate data.
Anyway, the check is straightforward.

Having noted the above, I propose the following simple algorithm:

Write down the multiset of numbers $S_1$ in the bottom row.
(A sorted array will suffice for storage and comparison.)
Search for the column which contains the exact same multiset of numbers $S_1$.
Swap this column with the leftmost one.
Proceed with the next-to-bottom row and find its multiset $S_2$.
Search for the column except the first one which contains the exact same multiset of numbers $S_2$.
Swap this column with the second-to-leftmost one.
Et cetera.

The algorithm can run in $O (n^2 \log n + n^2)$, with some hashing.
First, for each of the $n$ rows and each of the $n$ columns, calculate a hash of the multiset of numbers in it (for example, make a sorted array in $O (n \log n)$ and get its polynomial hash).
Then, we can consider hashes instead of the rows and columns of the real matrix.
After we find the needed permutation of rows, apply it once in $O (n^2)$.


Is the heap in "Data Structures Algorithms in Java" by Goodrich, Tamassia, and Goldwasser missing sentinel leaves? In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an

"Example of a heap storing 13 entries with integer keys. The last position is the one storing entry (13,W)."

I've recreated the a similar image using qtree-tikz with my own depth and height calculations in the box on the left.

According to the book,

A heap T storing n entries has height $h = \lfloor \log n \rfloor$.
Justification: From the fact that T is complete, we know that the number of nodes in levels $0$ through $h-1$ of T is precisely $1+2+4+...+2^{h-1} = 2^{h}-1$, and that the number of nodes in level $h$ is at least 1 and at most $2^h$. Therefore
$n \geq 2^h -1 +1 = 2^h$ and $n \leq 2^h -1 +2^h = 2^{h+1} -1$.

Here is where I see a problem. I added the depths and heights for nodes at each level according to my understanding of trees in the box to the left of the tree. The example tree Figure 9.1 shown above obviously has 7 inner nodes and although depth level 3 would have 8 nodes, it is unfull at 6 nodes.
If I follow the "Justification", I end up with the following

"we know that the number of nodes in levels 0 through $h-1$ of T is $2^h-1$"

$2^2 -1  = 3 \neq 7$.

but my understanding is that the $7$ would match the formula $2^3-1$, which means the $h$ referred to in the text must be $h=4$. But the $h =3$   from my understanding. Herein lies the problem.

I am being forced to conclude that there must be a missing level of sentinels,
$2^3 -1 = 7$ and the only way to get a power of 3 in those formulas is to have a height of 4. But why on earth would the authors, who otherwise explain everything in detail, not make important piece of information explicit? Or, did I miss something? I would appreciate a thorough explanation to help me understand the proof. It also seems that the authors throw around the term "level" loosely, sometimes meaning depth level and sometimes meaning height level.
I should also mention that earlier in the book, on page 286, they provide a definition for the height of a tree without any examples (and it is a bit cryptic).

We next define the height of a tree to be equal to the maximum of the depths of its positions (or zero, if the tree is empty).

If $p$ is a leaf, then the height of $p$ is $0$.
Otherwise, the height of $p$ is one more than the maximum of the heights of $p$'s children.

You have a tree made out of nodes at depths $0, 1, \ldots, h$ where $h$ is the height of the tree. The textbook is saying that the number of nodes at depths $0, \ldots, h - 1$ is equal to $2^h - 1$: notice the difference here between the $h-1$ and the $h$. This is easy to check by just looking at your picture, or using the formula for the sum of a geometric series:
$$ 2^0 + \cdots + 2^{h-1} = \frac{2^h - 1}{2 - 1} = 2^h - 1.$$
I think that a good rule of thumb for distinguishing between height and depth is that depth is the more useful one (the number of nodes on a complete level at depth $d$ is $2^d$, and a node's depth does not change as the tree grows), while the height $h$ is only really useful when looking at the tree as a whole (and is just the upper bound for depths).


Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$ We're asked to prove the above mentioned lemma but I having a hard time proving this rigorously.

We did prove that given $n$ values AVL's height is $\Theta\left (\log \left ( n \right ) \right )$ So I thought that after inserting a $\frac{n}{2}$ values the height of the tree will be at least $\Theta\left (\log \left ( \frac{n}{2} \right ) \right )$ which and because each isertion we make is now on a tree with at least $\frac{n}{2}$ and insertion is $\log \left (h \right ) $ where $h$ is the height of the tree.

So for a function $F$ using the previous logic:

$\begin{align}  F &= \frac{n}{2} \times \log \left (h \right )
\\& \geq \frac{n}{2} \times \log \left (\frac{n}{2} \right )
\\&=\Omega\left( n\log \left (n \right )  \right)
\end{align}$

But I have a few issues with this

This does feel fishy to me don't know why but it doesn't feel like a good well defined calculus proof :)
I'm not sure which way to take it in order to prove the upper boud i.e $\mathcal{O}$

If I haven't given all the required information I'd be glad to.

The upper bound is easy. Because a tree with $n$ nodes has height $\Theta(\log n)$, when inserting the sequence of elements each tree has height at most $O(\log n)$, so the total complexity is $O(n\log n)$.

You're right with the lower bound. After inserting $n$ elements the tree has height $\Theta(\log \frac{n}{2})=\Theta(\log n - \log 2)=\Theta(\log n)$. So we can split the sum into two and bound each part by its lowest element:
\begin{align}
\sum_{i=1}^n \Theta(\log i)
&= \sum_{i=1}^{n/2} \Theta(\log i) + \sum_{i=n/2+1}^n \Theta(\log i) \\
&= \frac{n}{2} \Omega(\log 1) + \frac{n}{2} \Omega(\log\frac{n+1}{2})\\
&= n\,\Omega(\log n) \\
&= \Omega(n \log n)
\end{align}


What does route aggregation is an automatic process means? Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), page 448:

When aggregation is turned on, it is an automatic process. It depends on
which prefixes are located where in the Internet not on the actions of an administrator assigning addresses to networks. Aggregation is heavily used throughout the Internet and can reduce the size of router tables to around 200,000 prefixes.

My question is: in this context, what does "when aggregation is turned on, it is an automatic process" mean? Is aggregation (route aggregation) like a function available in the router which an administrator can simply turn on or off? And what does "automatic process" here means? I mean, aren't processes, especially on the network, always automatic?

Firstly, I assume you know the purpose of route aggregation (if you need more clarification on that, feel free to post another question, as it is another topic by itself).
Secondly, in this context, what Tanenbaum is saying is that aggregation can be done manually, but it is done normally done automatically by the routing processes. Manual aggregation is when a human looks at the various network destinations and decides which ones can be aggregated, and then enters the aggregated network destination info into the router configuration (during the process where we have, as Tanenbaum writes it, "an administrator assigning addresses to networks"). The alternative is, for the routing processes to handle it automatically.
Yes, it can be turned on or off through the router configuration. In fact, it can be turned on or off separately for each routing protocol being run on the router (if more than one routing protocol is operating).  It is perfectly fine to turn aggregation off for edge routers that are not connected to many networks. Then, their routing table will have individual entries for more networks (not aggregated), but would still not be too big. However, for routers in the Internet core, normally aggregation must be turned on so the routing tables don't become too big (200,000 prefixes is the size Tanenbaum mentions; without aggregation, they could be much bigger with many more prefixes).
It is an "automatic process" in the sense that the routers will exchange information as part of the routing protocol(s), and they can figure out the aggregation automatically, as part of their logic. "I mean isn't process especially on network is always automatic?" -> some things can also be configured manually. Hence, Tanenbaum tries to make the point that most aggregation is handled through the processes automatically.


Does a reentrant list for signal queue in a single-thread environment exist? I need to handle Unix signals in a single-threaded application with the following goals:

Signals doesn't mask on receive (thus, the signal handler must be reentrant).
I am not allowed to lose signal data (thus, if a new signal comes before the handler of the previous returned, it also must be handled correctly).

I have the common multi-threaded primitives (spinlocks, semaphores, etc). But they doesn't seem enough, because my higher-level data structures (even a such simple as a list) aren't thread-safe.

My initial idea was the following:

I use a list, in which I store the data of the incoming signal fast,
and process them (call the possibily much slower running handlers) later, out of the critical section.

The main problem with that, that the list data structure isn't thread safe. If I lock it, I can't store a second signal anywhere. I can't wait until the previous handler exits, because on the second signal it is essentially suspended in a critical section.

Simply I don't have any idea, how to handle the following scenario:

signal1 comes, the process suspends, and the handler of signal1 starts
signal2 comes, the handler of signal1 suspends, and the handler of signal2 starts
Handler of signal2 returns, execution returns to the handler signal1
Handler of signal1 returns, execution returns to the main program.

After thinking a lot on it, I have an impression, maybe my problem is unsolvable. Am I right? How do operating systems handle similar problems (for example, possibily bursting interrupts from hardware)?

Finally I found a solution, which handles the whole problem at once. It is relatively easy. They key to the solution: we can use the signal stack as a "to-do stack".

Important to remember, that although this problem is also about race condition eliminiation, its solution differs significantly from the "lock everything what you use, do your task, release everything" solutions. It is because it is not about parallelisation, it is about reentrancy. The common lock-based solutions would lead to deadlock here, because the parent (in the example) signal1 handler will be surely suspended while the whole execution of the handler of signal2.

So, this is a disadvantage, but it is an advantage as well. We can guarantee, that signal1 won't do anything while our signal2 runs. We can't simply lock things, but we also don't need to do them.

So, that blocking locks are closed out, only the nonblocking locks left. What I invented, is the following C code:

#define STORE(a, b) __atomic_store(&(a), &(b), __ATOMIC_SEQ_CST)
#define SWAP(a, b) __atomic_exchange(&(a), &(b), &(b), __ATOMIC_SEQ_CST)

// action handler wrapper
void ss_wrapper(int signum, siginfo_t* siginfo, ucontext_t* ucontext) {
  // currently top element on the signal stack
  static struct ss_hit *top = NULL;

  struct ss_hit *hit = ss_hit_new(signum, siginfo, ucontext);
  struct ss_hit *bkp;

  again:

  bkp = hit;
  SWAP(top, hit);
  if (!hit) { // we got the lock, we are the master
    ss_fire(bkp);
    SWAP(top, &bkp->next); // release the lock, find out if there is new element
    if (bkp->nxt) { // there IS

      hit = bkp;
      free(bkp);
      goto again;

    } else
      free(bkp);
  } else { // we didn't got the lock, but we got the top in hit
    STORE(hit->next, bkp);
  }
}

As we can see, it had been very beautiful to have a separated, reentrant stack (and not list) data structure.

The main problem was to understood, that

adding new element in the stack, AND testing if it is empty, they should be done in a single atomic operation (this is why top serves as both of spinlock and pointer to the top of the stack)
similarly, removing element from the stack, and to know, if it is now empty, should be done also atomically.

I also learned from this some days of thinking, that
* constructing reentrant algorithm is much harder as to contrust a multithread
* the most important thing is that reentrant algos should have only very few variables to interact eachother through them, and all operation should be atomic on them.


Algorithm playing modification of "Hey, That's My Fish!" game Ok, I must admit this a task from my studies but I'm stuck.

Rules of the game are on Wikipedia. However, we have a modified version: on input we have a board with x fields, there are y penguins on some fields, there may be gaps between fields. All penguins are the same, they can move only to the farthest possible location (in a straight line, can't jump over gaps and other penguins). There is one player and he needs to move the penguins in such manner so as to get the maximal number of fish. I have to come up with an algorithm that finds the sequence of moves that leads to the best possible result.

I tried something like guessing the final arrengment of the fields (f.e. all the penguins left on fields with just one fish each) and then reverse-engineer the steps but I didn't go any further with my idea.

I also thought it would be probably good to represent this as a graph, possibly with weighted edges and then do some graph search but again, I don't know what next.

Finally, there was a thought about using Monte Carlo method. However, this just seems too hardcore for a class project like this and that would be too diffult for me.

Any ideas where should I start?

You are probably supposed to use exhaustive search, that is, recursively try all possible moves. They made it easier by restricting the number of possible moves. One optimization which might be needed is storing board positions and the number of fish obtained from them, so that you don't analyze twice the same sub-position; there might be too many of them to store, and in that case you should only store "large" positions. Alpha-beta pruning could also be useful perhaps, but if you haven't learned about that, there is probably no need to use it.


What is the minimal degree $d$ required for a B tree with $44*10^6 $ keys so that it's height is less than or equal to $5$ What is the minimal degree $d$ required so a B - tree with $44*10^6$ keys will have a height $h$, such that $h\leq 5$

My attempt was to build the tallest tree possible with minimum degree $d$ and $n = 44,000,000$ keys and then solve for $d$. That would mean any other tree with a minimal degree $d'$ such that $d'\geq d$ and $n$ keys will be shorter than the one I built:

at depth 0 , we have the root and that's $1$ node

at depth 1, we got exactly $2$ nodes

at depth 2, since we're going for the tallest tree each node will have a minimal number of keys so $d-1$ keys each, that means $d$ children each so a total of $2d$ nodes.

at depth 3, following the same reasoning , $2d^2$ nodes.
...

at depth $h$, there are $2d^{h-1}$ nodes

total number of keys is :

$n = 1+ (d-1)\sum_{k=0}^{h-1} {2d^k} = 1 + (d-1) \frac{2(d^h-1)}{d-1} = 2d^h-1 = 44*10^6 $

so:

$2d^5-1=44,000,000 $

$d= 29.4 $

$d\geq 30$

is that even correct ?


Count number of ways to place ones in an $M \times M$ matrix so that every row and column has $k$ ones? On math.stackexchange, someone asked how to count the number of ways to place $1$'s into a $10 \times 10$ matrix so that every row and column has $5$ $1$'s.  Each element of the matrix must be either zero or one.

I came up with a recursive solution for an $N \times 10$ matrix.  Subproblems are indexed by the counts $c_k$ of how many columns have $k$ $1$'s, for $k =0, 1,2,3,4,5$. The counts $c_k$ have to satisfy $\sum_k c_k = 10$, and they also have to satisfy $\sum_k kc_k = 5N$ and $c_k = 0$ for $k > N$. The complexity of this algorithm basically boils down to how many distinct sets of valid indices $(c_k)_k$ there are.

For a $10 \times 10$ matrix I think this approach should work out nicely, but I worry the complexity might get prohibitively large if we wanted to count how many ways to get $M/2$ $1$'s in every row and column of an $M \times M$ matrix. So I'm wondering, is there a more efficient way to solve this counting problem?  In other words, a better way than solving for $N \times M$ in increasing order of $N$ and keeping track of subcases indexed by $(c_k)_k$ such that $\sum_k c_k = M$ and $\sum_k k c_k = NM/2$? Also, for my solution, can anybody work out a good bound for how many sub-cases I have as a function of $M$?

When $k = 1$ then answer is $M!$ (why?). In the general case, an explicit formula is probably too much to hope for, but it is possible to obtain asymptotics. For example, in this answer Brendan McKay shows that for $k=2$, the number of ways is asymptotically $e^{-5/2} (2n)! 4^{-n}$ when the diagonal is always zero. Without the condition on the diagonal, the answer will be $e^{-1/2} (2n)! 4^{-n}$ (I think). The same method, known as the configuration model, should give asymptotics for arbitrary $k$.


Do "symbols" = terminals in CFGs? Are the "symbols" of a context-free grammar the same thing as the terminals?

Are the set of symbols and set of terminals the same?

In a context-free grammar there are two sets of symbols (two alphabets, if you will). One is the set of symbols that can be replaced by others: these are the non-terminal symbols. The other is the set of terminal symbols, which (you may have guessed) cannot be replaced.

At some point, a derivation is expected to produce a string of symbols that is immutable, and because it is immutable we tend to think of these strings in the same way we think of numbers (as opposed to arithmetic expressions), as elements of a language that is being defined. This is one game that we play.

You can still think of those two sets of symbols as partitions of a bigger set, the "set of all symbols". This would allow you to play other interesting games.


asymptotic notations with two exponents I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like  $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these notations properly. Is there any way (Lecture notes or video lectures with examples) to understand these things clearly.
Thank You.

That syntax is actually rather questionable formally, since it treats the big-O as a function, which it is not. But with a bit of slop the rule to interpret these is rather simple. The big-O stands for some function with the asymptotic behaviour given by the big-O.

I'll start with the full syntax of the big-O notation:

$$ f(n) = O(g(n)) $$

means that

$$ \exists C~\exists n_0~\forall n > n_0: f(n) \leq Cg(n). $$

So when we write "complexity is $O(n)$", we are really saying complexity is $c(n)$ for which $c(n) = O(n)$.

Alternatively we can say $O(g(n))$ is a set of functions defined as

$$ O(g(n)) = \{ f(n) | \exists C~\exists n_0~\forall n>n_0: f(n) \leq Cg(n) \}. $$

And write $f(n) \in O(g(n))$ instead. While this definition is more logical, it seems to be less used in textbooks.

Now if we say that complexity is $2^{O(n)}$, we can't expand it simply as $c(n) = 2^{O(n)}$, because we didn't define that. So instead we replace the big-O with a function that conforms to the big-O. Like this:

$$ c(n) = 2^{f(n)},\ f(n) = O(n) $$

And you can expand any other expression containing big-O. The approach applies to any expression having big-O as subexpression, so $O(n)^n$ is just

$$ c(n) = f(n)^n,\ f(n) = O(n) $$

In the set notation it makes even more sense, because

$$ g(F) = \{ g \circ f | f \ in F \} $$

where $g$ is a function and $f$ is a set of functions with one argument is the only logical definition of expression involving set of functions. So than:

$$ 2^{O(n)} = \{ 2^{f(n)} | f(n) \in O(n) \} $$

and

$$ O(n)^n = \{ f(n)^n | f(n) \in O(n) \}. $$

As for $O(\epsilon^{1/2^n})$, that's just standard big-O notation:

$$ f(n) = O(\epsilon^{1/2^n}) $$
$$ \exists C~\exists n_o~\forall n>n_0: f(n) < C\epsilon^{1/2^n} $$

(which tends to $1$ as $n$ tends to $\infty$). The $\epsilon$ would usually be some tunable parameter in the algorithm.


Relationship between Deterministic Finite Automata languages What this "⊃" superset means? What do I need to prove here. Can someone, please, explain in English?
Do I need to do a cross product?
Plus, in textbooks and online I only see "∩" "∪" these kinda symbols.  What this symbols "⊃" means?

Let M = (K, Σ, δ, s, F) be a deterministic finite automaton. Let M' =
(K, Σ, δ, s, F') be a similar deterministic finite automaton where F is
a proper
subset of F'. For each of the following provide an example to show that
the
relationship between L(M) and L(M') is possible or explain why the
relationship
is not possible.

The problem to prove: L(M) ⊃ L(M')

There are a wealth of set theory symbols that are in wide usage. I have seen or used most of those symbols .

In particular, "$L(M) \supset L(M')$" means $L(M) $ is a superset of $L(M')$, but $L(M)$ is not equal to $L(M')$. This is consistent with the explanation given by Wikipedia. To be more specific, it means all words in $L(M')$ are in $L(M)$, but at least one word is in $L(M)$ but not in $L(M')$.

A simple example of that situation can be the following. $M'$ is the finite automaton depicted at Wikipedia example with $S_0$ being the only accepting state. $M'$ accepts words with even number of 0's. Let $M$ be the same as $M'$ except that both states are accepting states. Then $M$ accepts all words.


Segmented address / normal virtual address In a cpu with segmented memory, can an address only be accessed with a segmented address, or can a normal virtual address also be used?

A virtual address is not normal. It is used with paging. "Normal addresses" are direct physical addresses which access main memory directly. Intel's terminology says that virtual address will be translated by the segmentation unit to a linear address. The linear address will then be translated to physical address by the MMU.
With that said the answer to your question is quite complex since it involves understanding operating-system development concepts.
Real mode
x86 CPUs start with the 8086. Today, the 8086 is emulated at startup of every x86 processor for backward compatibility with older software. This is called real mode. In real mode physical addresses are calculated using the address you specify in the assembly code by implicitly adding ds as the segment selector. They are calculated by the formula ds * 16 + offset. For example,
mov ax, 0
mov ds, ax
mov word [0x1234], 0x1234

will move 0x1234 to the physical address 0x0 * 16 + 0x1234 = 0x1234. With ds set as 0, real mode segmentation is ignored because the address you specify is translated to itself.
Protected mode
After real mode the OS will jump to protected mode. In protected mode there is segmentation and paging available for more recent CPUs. Before paging, there was only segmentation. Paging is more modern than segmentation. For an example on how to set up protected mode in NASM assembly look at the following code:
cli

lgdt[gdtr]

mov eax, cr0
or al, 1
mov cr0, eax

jmp 0x08:protectedMode       ;0x08 = 0b1000, 1 for segment selector
                             ;0 for gdt not ldt and 00 for privilege
bits 32
protectedMode:

gdt_start:
        dq 0x0      ;null descriptor
gdt_code:
        dw 0xFFFF   ;limit 0-15
        dw 0x0      ;base 0-15
        db 0x0      ;base 16-23
        db 10011010b    ;pr, privi (2), s, ex, dc, rw, ac
        db 11001111b    ;gr, sz, limit 16-19
        db 0x0      ;base 24-31
gdt_data:
        dw 0xFFFF
        dw 0x0
        db 0x0
        db 10010010b
        db 11001111b
        db 0x0
gdtr:
        dw 24
        dd gdt_start

The code disables interrupts, loads a GDT, enables protected mode by setting a bit in the CR0 control register then jumps to protected mode in segment 0x08. Segment 0x08 is the code segment. Segment 0 being the null descriptor. Here segmentation is enabled with a flat memory model.
The flat memory model is where you specify a base of 0x0 and a limit of 0xFFFFF with a granularity (gr) of 1. The granularity specify if the limit will be in blocks of 1 byte (0) or 4KB (1). If the limit is in blocks of 4KB and the base is 0 then the segment will span the whole 4GB available address space in protected mode (with a limit of 0xFFFFF). The flat memory model is often used in modern operating systems because it simplifies operations in transition modes before long mode is enabled.
Long mode
To enable long mode, you must enable paging and set certain bits in some registers. The following code enables long mode in NASM assembly:

mov eax, cr4            ;enable PAE-paging
or eax, 1 << 5
mov cr4, eax

mov ecx, 0xC0000080     ;set long mode bit in EFER MSR
rdmsr
or eax, 1 << 8
wrmsr

mov eax, cr0            ;enable paging
or eax, 1 << 31
mov cr0, eax

lgdt[gdtr]          ;load a 64 bit gdt (will be ignored afterwards)

jmp 0x08:longMode

bits 64

longMode:

gdt_start:
        dw 0xFFFF
        dw 0
        db 0
        db 0
        db 1
        db 0
gdt_code:
        dw 0x1111   ;limit 0-15
        dw 0x0      ;base 0-15
        db 0x0      ;base 16-23
        db 10011010b    ;pr, privi (2), s, ex, dc, rw, ac
        db 10101111b    ;gr, sz, limit 16-19
        db 0x0      ;base 24-31
gdt_data:
        dw 0x0000
        dw 0x0
        db 0x0
        db 10010010b
        db 00000000b
        db 0x0
gdtr:
        dw $ - gdt_start - 1
        dq gdt_start

The 64  bits GDT is necessary because as stated on osdev.org

Notice that we set a 4gb limit for code. This is needed because the processor will make a last limit check before the jump, and having a limit of 0 will cause a #GP (tested in bochs). After that, the limit will be ignored.

So basically, before we jump in the 64 bits code selector to enter long mode, the processor makes a last limit check. After that, the limit is ignored. This is evident since the limit is only 20 bits and, with a granularity of 4KB, this limits the segments to 4GB. In long mode you have access to much more RAM than that.
Once in long mode, you have paging enabled and everything but the CR3 register is translated by the MMU to a physical address. Everything is a virtual address. Segmentation is ignored.


Language independent software libraries When trying to decide on the choice of a programming language for a
specific task, people will often tell me: "use this language because it
has the best library for the type of problems you are addressing".

I would rather choose my language for its intrinsic qualities as a
programming medium. That implies that libraries should be more
universally usable.

What work has there been to create programming libraries that could be
programmed and used in different languages, being mechanically adapted
from one to the other on the basis of a standardized interface
language/formalism (or any other mean)? How succesful has it been?

For example, I found one system that claims to do that : Microsoft's .NET
Framework.
They say it is based on a Common Language Specification (CLS) which is defined in the ECMA-335 Standard: Common Language Infrastructure.

Are there others? What about free-software frameworks?

Pointers to relevant papers or web sites are an answer. A survey would
be best.

Note (June 7, 2013): this question is more controversial than is visible.
However, I cannot fathom the nature of the controversy. Some people
support the question and/or make cogent comments. But the people who
seem unhappy about it just downvote without a word of explanation. I
am sure they have a good reason to do so. But it would better help our
understanding of the issues, or possibly of the lack of issues, if
they were a little more explicit as to what irks them.

Java Bytecode

Similar to Microsoft's CLS, the Java Bytecode that the Java virtual machine executes gives you the (theoretical) possibility of using libraries from one JVM-targeting language with another JVM-targeting language. For example, Java libraries can be used in Scala, which IMO is a much better language than Java itself. Libraries written in Scala could be used in Clojure, or in Jython, or in one of these languages.

However, although interoperability is theoretically possible because of the common byte code to which all these languages compile, it is said (my personal experience is fairly limited) to sometimes be complicated to actually get it working.

Another, in the context of your question probably equally big drawback is, that using libraries from other languages often forces you to program in that languages style - and consequently "rip" you out of the style of the language you are actually programming in. For example, due to the lack of closures/anonymous functions and higher-order functions, Java libraries often don't have "nice" interfaces in the functional programming sense. Scala libraries, on the other hand, are usually written in a functional way.

Multi-platform languages

Another way of addressing your problem are multi-platform languages such as Haxe.

  Haxe can be compiled to all popular programming platforms with its
  fast compiler – JavaScript, Flash, NekoVM, PHP, C++, C# and Java
  (soon).

To be fair, I don't have any experience with Haxe, so all I can do is conjecture. That said, I see this approach as a double-edged sword. On the one hand, it allows you to implement libraries only once and then compile them to C++, PHP, etc., and use them from their. On the other hand, if you write a client or a library depending on other libraries in Haxe, you are probably limited to Haxe libraries, and, for example, cannot use the highly appraised C++ library Boost.

A similar, although assumably less powerful approach is followed by Apache Thrift.

  Apache Thrift allows you to define data types and service interfaces
  in a simple definition file. Taking that file as input, the compiler
  generates code to be used to easily build RPC clients and servers that
  communicate seamlessly across programming languages. Instead of
  writing a load of boilerplate code to serialize and transport your
  objects and invoke remote methods, you can get right down to business.

General worries

I assume that the "out of style" problem mentioned in the context of JVM-targeting languages is actually more general and probably something that makes it difficult to truly achieve what you want. If you specify interfaces arbitrarily general, it is likely that they feel out of place when used in any concrete programming language.

A second problem related to interfaces is which data structures to use as input/output data structures. For example, which data structures should a language-independent sorting library accept and return - arrays, sequences, lists, vectors, streams? And how are these mapped from/to data structures that actually exist in a given concrete language?

Another general problem I can see is performance. A library that is implemented in one language and cross-compiled into another is probably of poorer performance than one that is directly implemented in that language - which is not automatically a problem, but can definitely sometimes be one.


Best data structure for storing an ordered list, where each item is located on a separate server? I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible.

The first idea was to implement a basic linked-list where each item of the list is an RSS item. Being on the network, this means that to retrieve the latest 10 feed items, I need to wait sequentially until each node returns from the network (so that I can follow the pointer to the next item in the linked list).

Skip lists make this more concurrent as each node also gives me back pointers to other portions of the list and I can request more items in parallel.

However, I'm looking even further for something that follows more closely my users need: there will be more requests of the latest portion of the feed rather than the older portion. With this requirement in mind, I'd be looking for a structure that can perhaps allow me to achieve higher concurrency closer to the head of the list (where latest feed items are), and less concurrency (with more sequential properties) as users get towards the end of the list.

My thinking is that skip lists achieve the same level of concurrency across the entire list, so perhaps there's something I can use to make it "very concurrent" at the beginning and "less concurrent" at the end rather than "same concurrency" all along.

A standard approach is to have a distributed data structure, and then use a cache for efficiency.  The cache remembers the results of common queries; if you ask the same query again, and the underlying data structure hasn't changed, then you can return the same remembered answer without needing to re-compute it.

For instance, you might store the items spread across networked machines however you like, as a singly linked list.  Then, you'd have a single machine M that is responsible for keeping a cache of the 10 items at the head of the list.  Each time you insert a new item to the head of the list, you also need to notify M to let it know to invalidate its cache.  (As an optimization, instead of throwing away all cached data, M might be able to update the cached information when it receives a notification -- though this does introduce some additional concurrency challenges.)

Now any attempt to read the first items from the queue goes first to M, which can check whether it has the answer cached, before traversing the linked list through the network.

You'll then need to analyze how strict your consistency requirements are.  Do you require that M always return the absolutely correct result?  Or can the cache be temporarily inconsistent with the backing data structure for a short period of time?  That will affect whether you need to use coordination mechanisms like 2-phase commit or whether you can use simpler, higher-performing mechanisms.

I've described this in a particularly simple form, but you can generalize to (a) other backing data structures (not just a singly linked list), and (b) other caches for other kinds of queries that might be performed (not just the top 10 items from the head of the list).