Find minimum distance match in sub-linear time in a data base The title seems a little vague. So let me explain the question in detail.

Suppose you have a data base. Each record in the data base is $<\mathbf{x},data>$, where $\mathbf{x}$ is an $n$-dimensional index vector.

A query is also an $n$-dimensional vector $\mathbf{y}$. So given the query $\mathbf{y}$, the data base will return the record $i$ such that $\mathbf{x}_i$ and $\mathbf{y}$ have minimum distance. (It can be any distance. But let's focus on Euclidean distance here).

The trivial solution is to scan every record in the data base and compute the distance. This will introduce linear complexity with regard to the number of total records in the data base.

So is there any sub-linear algorithms to solve this problem (approximately)?
For example, if the dimension $n=1$, we can organize the index in data structure such as binary search tree. But for dimension $n>1$, can we also organize the index into some special data structure?

Thanks for you time.

This problem is exactly solved by the k-d tree, which organizes points in $k$ dimensions with logarithmic lookup time.


Why is the number of comparisons in a BST missing key lookup about 2 ln N? In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1.39 lg N) compares, on the average. I didn't get it well, even after I read their explanation, can you help to understand it by simplifying the idea to me? I mean why do we have 2 ln N compares?

The 2 comes from doing 2 comparisons at each node visited by the algorithm. The lg(n) comes from having to examine one node from each generation, or one node at each height in the tree. So, if we need to examine lg(n) nodes, and preform 2 operations at each node, we preform a total of 2lg(n) operations.


Maximum variance and useful information of dataset I am reading through PCA and it says that the maximum variance principal component has most of the information. Can we apply that to any data set? If a data set has n attributes and most of the attributes show high variance then can we infer that the dataset has captured lot of useful information?

I am trying to understand how a high variance dataset contains useful information?

I'll answer this, even thought the question is not well defined and would possibly be better suited for cross validated. But since it has some connection to information it's not totally off topic here.

Short version: Now, we can't apply that to any data set. Variance alone is not a good measure of information. PCA chooses the components with the highest eigenvalue, because they explain the input variance (i.e. euclidean distance from the origin). That's why you should normalize your input, if you don't want to emphasize a certain input component.

Long version:

Let's say you have two random variables $X$ and $Y:=10X$ where $E(X)=E(Y)=0$, $\mathrm{Var}(X)=1$ and thus $\mathrm{Var}(Y) = 100$. Now assume a third variable $K$ uniformly distributed among $\{1,\dots,k\}$ (this models drawing a random individual form your sample).

The variance before the PCA is not a sufficient measure for information, e.g. if we use $X$ and $Y$ to distinguish the individuals:
$$P(K=k|X=x) = P(K=k|Y=10x)$$

The covariance matrix looks like this:
$$\left(\matrix{1&10\\10 & 100}\right)$$

Using R's "eigen" we get:

$values
[1] 101   0

$vectors
           [,1]        [,2]
[1,] 0.09950372 -0.99503719
[2,] 0.99503719  0.09950372

If we now transform $X$ and $Y$ to $X'=M_{11}\cdot X + M_{21}\cdot Y$ and $Y'=M_{12}\cdot X + M_{22}\cdot Y$ (where $M$ is "vectors" from $R$), $X'$ contains "all the information":
$$\forall y\;:P(K=k|X'=x) \neq P(K=k|Y'=y)=P(K=k)$$

But, of course, again $X''=10^{-100}\cdot X'$ contains "the same information".


Isn't a small monolithic kernel a micro-kernel, and a big micro-kernal a monolithic kernel? I don't understand the last para. I corrected its typos. Please explain like I'm 5. If micro-kernels can be big, and monolithic kernels can be small, doesn't this size gradation collapse the distinction between monolithic kernels and micro-kernels? Is this what a hybrid kernel means?

So.. that's the ELI5 version. Things change, microkernels was going to be the cool logical way to do it, that argument between Tovalds and Tanenbaum really is worth a read. But Monolithic kernels appear (for now) to have won, as they want speed, instant access to resources (like kitchens or GFX cards) and rely on the OS managing processes a bit smarter to figure out who gets what type of access at what time. But just because a kernel is micro doesn't mean it won't take a lot of room up, as it'll then still need all the drivers to do things and be useful. So you can have a monolithic kernel that's small (compiled with only the drivers it needs into the kernel), and a microkernel that's big (compiled for a certain architecture/memory configuration with lots of modules available to handle all sorts of odd hardware to be plugged in). Google will provide more details and far more pros/cons that we can throw here. But again, read that linked Torvalds/Tannenbaum argument, it's the kind of thing that still goes on today.

The distinction between monolithic kernels and microkernels has nothing to do with the size.
In a monolithic kernel, all services are provided by a single piece of code running in a single, flat, shared address space. There are monolithic kernels which support dynamically loadable modules now (actually most monolithic kernels do), but when these modules are loaded, they still become part of the single monolithic (hence the name!) blob of code running in the single address space. All communication between these different services is done by accessing shared memory, or another way of looking at it is that there is no communication because it's all just one singular monolithic blob of code.
In a microkernel, only the most basic, fundamental services are provided by the kernel. Everything else is provided by separate programs, which are separate pieces of code, running in separate address spaces. All communication between the services is done through a well-defined messaging protocol.
So, in a monolithic kernel, you have a single piece of code which manages memory, schedules tasks, accesses the disk, accesses the filesystem, accesses the network card, implements the TCP/IP stack, implements Ethernet, implements WiFi, access the graphics card, etc.
In a microkernel, the kernel only implements the very basics: memory management, task scheduling, and a simple messaging protocol that allows the programs to talk to each other and to the kernel. The disk driver is a separate program. The filesystem driver is a separate program. The network card driver is a separate program. The implementation of the IP protocol is a separate program, TCP is a separate program, UDP, IPv6, etc. are all separate programs. The Ethernet implementation is a separate program, actually probably a set of separate programs for the PHY layer, the LLC layer, the MAC layer, etc. Same for WiFi, that's going to be a whole set of separate programs. The graphics driver is a separate program. And so on, and so forth.
These "separate programs" are sometimes calls "services" or "deamons".
The relationship between a microkernel and its daemons is analogous to the relationship between an Operating System and the user programs: Your browser, your email program, your first-person shooter, your music software, your text editor, your chess program, your video editor, your drone controller, your video chat program, they are not part of the Operating System. They are all separate programs that run in separate processes in separate address spaces. One of them can crash without taking the entire system down.
But none of this has anything to do with size: the sum of a microkernel and many services that provide many features can be larger than a simple monolithic kernel that doesn't provide many features. If a system doesn't support networking, for example, then it doesn't need code for networking, regardless of whether that is a microkernel or a monolithic kernel. So, it is easily possible for a microkernel system that supports networking to be larger than a monolithic kernel system that does not support networking.


Is my simplified explaination of the XOR swap correct? The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows:

a = a ^ b
b = a ^ b
a = a ^ b

Now, I was thinking to myself if I can find a way to help with my intuition regarding this algorithm. And here's what I thought of:

Bitwise XOR is the same as bitwise addition (1 + 1 = 0, as the carry is lost). Hence, if we write down the operations as addition, we get:

a = a + b
b = a + b + b
a = a + b + a + b + b

I then cancel any matching pair, i.e. b simply becomes a and a becomes b + b + b, which becomes b.

This is all very simple, so does it hold up to scrutiny?

Your proof is correct in intention, but the style is not adequate.

Of course, there is no perfect style, and most of us could improve
their style, myself included.

Still, hoping readers will not be too harsh, here is an attempt at
writing it, as an example, following your own proof. It may be too
verbose, one of my own failings. (it is also a bit intentional here)

Actually the style usually depends also on the audience you are addressing. If the intended audience is very competent in the field, you can skip a lot of details. Nevertheless, careful notation always helps (like the indexing $a_0$ below).

The XOR swap is a well-known in-place algorithm to swap two values, by
XOR:ing them bitwise. It goes as follows for two variables a and b, using the notation of the C programming language:

a = a^b

b = a^b

a = a^b

Correctness proof

We note the XOR operation $\oplus$ as is common in mathematical uses. This notation is justified by the isomorphism between XOR on the booleans and the addition in $\mathbb{Z}/2$.

The algebraic properties of XOR extend to bitwise operations on bit
vectors (i.e., sequences of bits) of equal sizes. In particular it
remains associative and commutative, and we have for any sequence $x$
of bits: $x\oplus x=\vec{0}$ where $\vec{0}$ is a bit vector of $0$´s of the
same length, and $x\oplus\vec{0}=x$.

Assume the initial values of a and b are respectively $a_0$ and
$b_0$.

The 3 assigments above are then equivalent to:

a =$a_0\oplus b_0$

b =$(a_0\oplus b_0)\oplus b_0$   which simplifies algebraically to $a_0$ as indicated above

a =$(a_0\oplus b_0)\oplus a_0$   which simplifies to $b_0$

The initials values of a and b have been swapped bitwise. $\;\Box$

Though I may be in some disagreement over this with other users, I do not
see the usefulness for this proof of insisting on the relation between
XOR and addition (other than for justifying the notation). Of course,
the generalized view of Yuval Filmus]1 brings wider understanding, but
the point for me is to have a simple proof, not to write a treatise.

Note that I have been using distinct notation for syntax (taken fron
C) and for the semantics of these operations. This justifies having
two notations for the XOR operator, and gives a cleaner presentation
of the proof, which may sometimes be important.

Of course, one is not always that careful, but it is better to have
these principles in mind, without overdoing it, depending on the
purpose and audience of what is being written. I think the most important here was to distinguish a and $a_0$.

Hoping this version will satisfy most readers. Further comments welcome.

With my thanks to all for all the very useful comments. Perfection is not of this world.


Why did RSA encryption become popular for key exchange? This is a soft question.  I don't know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message (e.g., the description of iMessage here).  Isn't this exactly the thing that Diffie-Hellman key exchange, which is older (and to me seems simpler) is for?  Looking at Wikipedia, they were also both patented, so this wouldn't have been responsible for the choice.

To be clear, I'm not asking whether it's theoretically important that public key cryptography is possible.  I'm asking why it became a standard method in practice for doing key exchange.  (To a non-cryptographer, DH looks easier to implement, and also isn't tied to the details of the group used.)

There is no strong technical reason.  We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA.

So why RSA?  As far as I can tell, non-technical historical reasons dominated.  RSA was patented and there was a company behind it, marketing and advocating for RSA.  Also, there were good libraries, and RSA was easy to understand and familiar to developers.  For these reasons, RSA was chosen, and once it was the popular choice, it stayed that way due to inertia.

These days, the main driver that has caused an increase of usage of Diffie-Hellman is the desire for perfect forward secrecy, something that is easy to achieve by using Diffie-Hellman but is slower with RSA.

Incidentally: It's Diffie-Hellman key exchange, not Diffie-Hellman secret sharing.  Secret sharing is something else entirely.


Edge-connectivity of a weighted undirected graph My question consists of two parts.

Let say the edge connectivity of a graph is K. I would like to change the edge connectivity value to L (> K). What is the best possible way to do so?

My guess: Obviously, we have to increase the edge weight of one of the critical edges (edges of the min-cut), but among the set of critical edges which edge should we choose?

After changing the weight of one of the critical edges, how could we find the new edge connectivity of the graph [assume we have already computed the edge connectivity of the previous graph]?

This is generally known as "edge connectivity augmentation", and there is a lot of literature on the subject. There are several fast algorithms for the task, and they come in different flavors depending on what you know about your graph, or what you specifically care about.

A basic question is "what is the minimum number of edges (or minimum cost of edges) to be added to the graph $G$ to increase its edge connectivity to a certain value?".


Why are dependently typed languages such as Agda used for proofs, if supercompilers for simpler typed languages can do the same? Proof assistants such as Agda can be used to assert properties about programs, such as "the double of a number is even". Interestingly, supercompilers can be used for the same purpose, creating typeless proofs. Even more interestingly, macro tree transducers can, too. My question is: what is the relationship between those? What does a dependently typed language have that makes it more powerful than other type systems as far as theorem proving goes, considering proofs can be done without types?

I think you're confusing two things: dependently typed languages are convenient for specifying properties and giving proofs about functional programs. The techniques you mention are possible decision procedures for certain properties of functional programs.

The ability to specify program properties usually takes place within a logic. Dependent types are a kind of logic, when viewed through the propositions-as-types lens. The nice thing about this logic is that it is naturally suited to talk about functional programs, which also can be used as a proof language. But there are other logics as well capable of doing this, and some are not based on dependent types.

Supercompilation type proofs are essentially a way to prove that two functions are observationally equal i.e. send identical inputs to outputs. But the fact that a supercompiled function $\mathrm{S}(f)$ is observationally equal to $f$ is not obvious: it has to be proven. Usually this is done with pen and paper, but of course Agda could be used for such a purpose.

Some things to note:

Agda is sufficiently powerful to prove (almost) all the program equivalences you could be interested in. The drawback is that you have to supply the proof yourself.
The things that can be proven automatically using SC or transducers are nice, but they only cover a tiny percent of what people want to prove about their functional programs. In particular, these techniques will fail with any slightly complex property (say, always returning a prime number) and even expressing the desired property may be hard (e.g. always returning a prime number).
There are a number of decision procedures for functional programs which are well-studied and offer similar or additional power as the techniques you mention. In particular ACL2 has been around for quite some time and is (I hear) quite powerful for these kinds of things.
In theory, we could integrate these kinds of procedures to help the user produce a proof in a system like Agda or Coq. There are a number of technical and social reasons for which this hasn't happened yet. There's still hope though! Note also that Coq has a fair number of automated techniques already.


number of subsegments that contain A[i] as the minimum I've recently been thinking about this problem.

Given an array $A$ containing $n$ integers and an index $i$, find the number of subgements of $A$ containing $A[i]$ as their minimum.

To better illustrate the problem, consider the array $A = [5, 1, 7]$ and we want to find the number of subsegments containing $A[1] = 1$ as their minimum. Clearly the answer is 4 and we can easily enumerate them: $[1], [5, 1],[5, 1, 7], [1, 7]$.

What the fastest way to compute the number of subsegments?

You haven't stated what a subsegment is, but I assume that you mean a "contiguous subsequence", that is, $A[s],A[s+1],\ldots,A[t]$. Also, I'm assuming that $A[i]$ is still a minimum if there are other equal values (you can easily adapt the algorithm for the other option).

Let $\ell \leq i$ be the smallest index such that $A[s] \leq A[i]$ for all $\ell \leq s \leq i$, and let $r \geq i$ be the largest index such that $A[r] \leq A[i]$ for all $i \leq s \leq r$. Then $A[i]$ is a minimum of $A[s],\ldots,A[t]$ iff $\ell \leq s$ and $t \leq r$. Thus there are $i-\ell+1$ options for $s$, namely $\ell,\ell+1,\ldots,i$, and similarly $r-i+1$ options for $t$, for a total of $(i-\ell+1)(r-i+1)$.

You can easily find $\ell,r$ in linear time by scanning left of and right of $i$ (respectively), so this algorithm runs in linear time.


Complexity of finding Exact Size Cut-Sets in Bipartite Graphs I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part of the input). Note that this is different from the problems of MINCUT and MAXCUT which simply ask to find the minimum and maximum sized cutsets.

For general graphs, the MINCUT problem can be solved in polynomial time while the MAXCUT problem is NP-Hard. It follows that deciding if a cutset of a particular size exists in a general graph is also NP-Hard since we could use it to find the maximum sized cutset.

For bipartite graphs however, the MAXCUT problem is trivial -- all the edges in the graph constitute the MAXCUT. Moreover, if it helps, I think I can show that for bipartite graphs, the edge - complement of a cutset is also a cutset. That is if $E_c \subseteq E$ is a cutset of a bipartite graph $G = (U\cup V, E)$ then $E-E_c$ is also a cutset of $G$.

However, I have not been able to determine if deciding if a cutset of some size $k$ exists is in P or is NP-Complete or something else. If it is Np-Complete, is there a family of graphs for which it is in P? Any pointers will be helpful.

This is a partial answer that proves the NP-completeness of your problem, by a reduction from the EXACT-CUT problem for general graphs1.

Given an instance $(G=(V,E),k)$ of the EXACT-CUT problem (that asks whether there is a cut of size $k$ in the graph $G$), we construct a new graph $G'$ as follows.

For each vertex $v\in V$, construct vertices $v_0^0,\ldots,v_m^0,v_0^1,\ldots,v_m^1$ as well as edges $(v_i^0, v_j^1)$ for all $i,j\in\{0,\ldots,m\}$ (so that they form a biclique). Denote $V_v=\{v_0^0,\ldots,v_m^0,v_0^1,\ldots,v_m^1\}$.
For each edge $(u,v)\in E$, construct two edges $(u_0^0, v_0^1)$ and $(u_0^1, v_0^0)$.

Here $m=2k$. Note $G'$ is a bipartite graph.

Now we can see if $(A,B)$ is a cut of size $k$ in $G$, then $(\cup_{v\in A}V_v,\cup_{v\in B}V_v)$ is a cut of size $2k$ in $G'$.

On the other hand, suppose there is a cut $(A',B')$ of size $2k$ in $G'$. Now consider a vertex $v$. Assume $|A'\cap\{v_0^0,\ldots,v_m^0\}|=a$ and $|A'\cap\{v_0^1,\ldots,v_m^1\}|=b$, then we have
\begin{align}
m=2k&\ge a(m+1-b)+b(m+1-a)\\
&=(m+1)(a+b)+\frac{1}{2}(a-b)^2-\frac{1}{2}(a+b)^2\\
&\ge(m+1)(a+b)-\frac{1}{2}(a+b)^2,
\end{align}
which implies $a+b<1$ or $a+b>2m+1$, i.e. $a=b=0$ or $a=b=m+1$. This means all vertices in $V_v$ must belong to the same cut-set. Hence $(\{v\mid V_v\subseteq A'\}, \{v\mid V_v\subseteq B'\})$ is a cut of size $k$ in $G$.

Now we have shown that there is a cut of size $k$ in $G$ if and only if there is a cut of size $2k$ in $G'$, which concludes the proof of the NP-completeness of the EXACT-CUT problem on bipartite graphs.

1 Your reasoning for the NP-completeness of the EXACT-CUT problem is incorrect because you used a Turing reduction while a many-one reduction is required. However, it is not hard to find such a polynomial-time many-one reduction.


Construction of fair teams let's say we have a set of players that we want to match into teams of aproximatly same strength, so that no team is much stronger than another team.

Each team consists of two players. One player is taking a defense position, another player is taking an offense position. The teams can decide for themself which of the players if playing at what position. We can assume that the teams try to win and will take the best possible combination of defense/offense player.

Each player has an offense rating (e.g. discrete number between 0 and 10) and a defense rating (same scale) that describes how strong the player is in the offense or defense position.

The strength of a team is determined by the defense strength of the player in the defense position and the offense strength of the player in the offense position. So we can assume:

TeamStrength = max(PlayerADefense + PlayerBOffense, PlayerAOffense + PlayerBDefense)

The question is, what is a good algorithm to find teams of similar strength using above metric.

My thinking is that I can easily evaluate a single result by calculating an average team strength and build the sum of difference (square).

Based on this it is obvious that I can just create random matches and then choose a "good" solution. However I'm curious if there is a way to find an optimal solution without brute forcing of all variants.

Any ideas?

Edit: There seems to be some confusion about the metric of optimal strength / average strength.

The goal is to have teams of similar strength, nothing more nothing less. Specifically I don't care if there are other combinations where the total strength of all teams is higher.

I can imagine various metrics to achieve this goal. One idea I presented was to use the following metric:

For each team t calculate its strength by calculating:
    strength_t = max(PlayerADefense_t + PlayerBOffense_t, PlayerAOffense_t + PlayerBDefense_t)
Calculate the average team strength: avgStrength = sum(strength_t) / teamCount
For each team t calculate its deviation from the average squared and sum it:
    m = m + (avgStrength - strength_t) ^ 2
m should be minimal

I want to minimize the value $m$. I want to emphazize that I'm open to other metrics if they provide comparable results.

This can be expressed as a weighted maximum matching problem.

Suppose we want the average team strength to be $x$.  If the actual team strength is $s$, we apply a penalty of $(x-s)^2$.  In this way, for any proposed partitioning of the players into teams, we obtain a total penalty (the sum of the penalties for each of the teams).  The goal is to find an assignment of teams that minimize the total penalty.  I think this is what you are asking for.

So, here is how we express this as a maximum matching problem.  If you have $n$ players, form a graph with $n$ vertices, one vertex per player.  For each pair of players $v,w$, add an edge from $v$ to $w$ whose weight is $-(x-s_{v,w})^2$, where $s_{v,w}$ is the strength of the team obtained by putting $v$ and $w$ onto the same team.  Now any division of the people into $n/2$ teams is a matching in this graph.  By maximizing the total weight of the matching, we are minimizing the total penalty of the corresponding teams, so the maximum matching gives us a solution to your problem.  Finally, there are polynomial-time algorithms for finding a maximum matching in a weighted graph, so you can just use one of them.

How do we find $x$?  I initially interpreted your comments to imply that $x$ should be the optimal team strength, by which I assume you mean the average strength of the teams in the assignment that maximizes this average (without trying to make the team strengths as similar as possible).  This too can be computed by solving a maximum matching problem, where now the weight on the edge from $v$ to $w$ is simply $s_{v,w}$.  So, the total algorithm is: first find $x$, using an algorithm for maximum matching, then find the best partitioning of teams according to your original matching, by applying the maximum matching algorithm a second time.

However, after reading megas' comments, I now suspect that interpretation was incorrect.  As megas correctly explains, a more reasonable interpretation would be to make $x$ be the average strength of the teams in the partitioning selected to make team strength as close as possible.  That's a harder problem.

However, here's an approach that might work reasonably well in practice.  Sweep $x$ over a range of candidate values, say, over 100 candidate values.  (You can probably get some reasonable guess for a range $[\ell,u]$ that is likely to contain the optimal value for $x$; now try a bunch of different values of $x$ in that range, say the values $\ell, \ell+0.01(u-\ell), \ell+0.02(u-\ell), \dots,u$.)  For each such hypothesized value of $x$, solve the maximum matching problem (with weights $-(x-s_{v,w})^2$ on the edges) to get an assignment of players to teams.  In this way, we get 100 candidate assignments.  Now for each we can calculate the average team strength and the total penalty, and see which assignment is best.

Why do I expect this will give close to an optimal answer?  Well, there is some real optimum.  Let $x_\text{opt}$ be the average team strength for this actual optimum.  When we use a candidate value for $x$ that is sufficiently close to $x_\text{opt}$, we can expect to get an assignment that matches the optimum (or is close to it).  So, if the step size for the candidate values of $x$ is small enough, this procedure seems like it should find the optimum.  In practice, this is only a heuristic, and it might or might not find the actual optimum, but I suspect it will enable you to find an assignment that's pretty close to optimal, even if it's not exactly the optimum.


Probability of Attaining the/a Global Optimum Suppose for a given optimization problem, $A$, the size of the search space $S$ is |$S$|.
If the fitness landscape defined by $A$ is unimodal, then there is clearly only one global optimum. Given that $G$ is the event "reach the global optimum", can we then infer that $P(G) = \frac{1}{|S|}$, where $P(G)$ denotes the probability of reaching the/a global optimum?
For $N$ ($N < |S|$) such global optima (in the case of a multimodal landscape), the probability increases to $P(G) = \frac{N}{|S|}$
Is this a valid argument or can we not conclude anything regarding the probability of attaining the/a global optimum on the basis of the number of optima and the size of the search space?
I realize that often one cannot know in advance the number of global optima, but say, if the problem was to maximize a simple continuous function over some domain, then the function of interest could easily be plotted and the number of (local) optima examined.

No, you can't infer that.  You seem to be assuming that the optimization process tries one element of the search space, chosen uniformly at random, and hopes that it got lucky.  But that's not how real optimization algorithms work.  They try multiple solutions, and they're not chosen uniformly at random; they're typically chosen in some way that we hope is more likely to hit a good solution.
In general, you cannot conclude anything about the probability of hitting the optimum after some amount of optimization, without further information.  The probability might be much larger than $N/|S|$ (e.g., if the optimization problem is easy or the optimization algorithm is effective on this kind of problem).
In the kinds of optimization problems we typically use a computer to solve, often you can't just "plot it out" as often we're working with a multidimensional search space.


Linked List in Maximal Scoring Subsequences Algorithm For a project, I'm implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, when doing the search for the rightmost value of $j$ that satisfies $L_j < L_k$, we can search a linked list with monotonically decreasing $L_j$ values.

I'm slightly confused on how this works. If we store a pointer to the element $j$ we found during Step 3, then we must start iterating with some element in Step 1. What element would operate as the head of the linked list in this case? In other words, in Step 1, instead of searching through the whole list, what element do we start searching with?

I found these lectures notes easier to read than the actual paper. I also implemented a $O(n^2)$ version of the algorithm in Go here, which anyone may use to reference. However, I would like some help cutting the complexity down to $O(n)$. Any help would be appreciated!

What element would operate as the head of the linked list in this case?

That's of course $L_{k-1}$.

If you are surprised why this works in $O(n)$, that paper has already explained:

  Once a list element has been by-passed by this chain, it will be examined again only if it is being deleted from the list, either in Step 2 or Step 4. The work done in the “reconsider” loop of Step 4 can be amortized over the list item(s) being deleted. Hence, in effect, each list item is examined a bounded number of times, and the total running time is linear.

Let's consider the example given in the paper. The sequence is $(4, -5, 3, -3, 1, 2, -2, 2, -2, 1, 5)$. The list is initially empty. The first subsequence $(4)$ comes, we keep a pointer to the head of the list, like

H <- (4)

Next, we sWe add it to the end of the list. We search $I_1$ and find $L_1>L_2$, so we keep a pointer to the head, like

H <- (4)  (3)
^         /
 \       /
  -------

Next, we skip $-3$ and the subsequence $(1)$ comes. We search $I_2$ and find $L_2=L_3$. Since $I_2$ points to the head, we assert there is no such $j$ such that $L_j<L_3$ and keep a pointer to the head, like

H <- (4)  (3)  (1)
^         /    /
 \       /    /
  ------------

Next, the subsequence $(2)$ comes. We search $I_3$ and find $L_3<L_4, R_3<R_4$, so we apply step 4 and get (note $I_3$ need to be reconsidered after merging while no change is needed here since it points to the head)

H <- (4)  (3)  (1,2)
^         /    /
 \       /    /
  ------------

Next, we skip $-2$ and the subsequence $(2)$ comes. We search $I_3$ and find $L_3<L_4, R_3=R_4$, so we keep a pointer to $I_3$, like

H <- (4)  (3)  (1,2) <- (2)
^         /    /
 \       /    /
  ------------

Next, we skip $-2$ and the subsequence $(1)$ comes. We search $I_4$ and find $L_4=L_5$, then search $I_3$ and find $L_3<L_5, R_3>R_5$. We keep a pointer to $I_3$, like

H <- (4)  (3)  (1,2) <- (2)  (1)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------

Next, the last subsequence $(5)$ comes. We search $I_5$ and find $L_5<L_6, R_5<R_6$, then we merge $I_5$ and $I_6$ and get

H <- (4)  (3)  (1,2) <- (2)  (1,5)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------

Note $I_5$ needs to be reconsidered. Since $I_5$ points to $I_3$, we search $I_3$ first and find $L_3<L_5, R_3<R_5$, so we merge $I_3,I_4,I_5$ and get

H <- (4)  (3)  (1,2,−2,2,−2,1,5)
^         /    /
 \       /    /
  ------------

We then reconsider $I_3$ and no change is needed since it points to the head.


Why does x86 has explicit register definitions, and RISC's doesn't? For example, on x86, we have a set of general registers, each named to the function it carries out.

We have an Accumulator, which is a storage for a results of different fixed point operations, we have a Base register, which is used for addressing elements in the array, a Cycle register, which holds a incremented or decremented counter for cycles, we have a Data register, which can hold an operand for arithmetic operations, and many many others (like base and stack pointers, indexes, and etc.)

But on typical RISC architectures, like SH4, for example, you won't find such an explicit names for registers. On Sh4, for example, there's no explicit name for register, which must hold a stack pointer, so you can store it elsewhere upon your choice from 16 available registers. Same for arithmetic operations, and so on.

So why it is that?
It is simply a matter of design, choices, taken by Intel engineers, or some significant sign of RISC processors?

The main historical trend that accounts for the change in instruction sets is the dropping cost of memory.  The x86 instruction set derives from the 8080, which derived from the 8008.  The 8008 was first sold in 1972, when the cost of memory was about US\$0.05 per bit.  1 MByte would have cost about US\$400000, and even a KByte cost about \$400.    Now you can get 4GB of DRAM for less than $40 (US\$0.00000000125 per bit) so the price has dropped by a factor of about 40 million in 40 years. (I may have missed a decimal place somewhere, and it also doesn't account for inflation (another factor of 5 or 6).  But you get the idea.)

Expensive memory meant you needed to try to make the instructions as small as possible.   There are a couple of ways you can do that.  One way is using variable length instructions. The 8008 and 8080 had 1 byte instructions.  If an instruction needed immediate data, the constant would be stored in the following byte (or bytes for 16-bit constants in the 8080).  So instructions could vary between 1 byte and 3 bytes.

Another is to make the register operands implicit.  The 8008 and 8080 each had 8 registers, so to specify two source registers and a destination register would have consumed 9 bits (already more than a byte!)  Instead of having three operands, you can try to get away with 2.  Most x86 instructions have 2 operands, one is the destination and also one of the sources, while the other is a source.  But you can do still better.  By assuming that all arithmetic instructions use the accumulator register as both the first source and the destination you only need to specify a single source operand.  Similarly if you assume that all the stack manipulation instructions work on a specific stack register you can get away with not specifying the register holding the stack pointer.  Similarly with loop counter increments and tests you can get away with no register specifiers if you have a dedicated loop counter.

Instruction compression of this kind is good but it comes at a couple of costs.  The most important cost is that the instructions are variable length and hard to decode.  The 8080 took several cycles to decode each instruction.  By the 1980s the cost of memory had come down considerably, and people started to realize that by making instructions easier to decode it would be easier to design high-performance pipelined processors.  RISC instructions are designed to be easy to decode (and to not have more than one memory operation so that they can be pipelined).

Instruction set design still has a small effect, mainly seen in power consumption.  In general the decoders on x86 machines consume more area, and also more power, per instruction decoded than do machines with RISC instruction sets.  On the other hand the x86 power consumption can be reduced somewhat during tight loops by caching a small number of decoded instructions.  Additionally the number of instructions to encode a program in x86 is about half that to encode the same program with a RISC instruction set, so the instruction fetch bandwidth (and thus the power consumption for instruction fetch) is a bit lower with x86 than it is with RISC instruction sets.


How would you model Rust procedural macros? In Rust programming language one can write a compiler extension function that works on abstract syntax tree, effectively modifying source code before it gets converted into machine instructions.
In other words, macro function has signature
 Abstract Syntax Tree -> Abstract Syntax Tree

Can these be thought of as higher order functions? Usually higher order functions use function composition to produce their output, not source code manipulation.

I wouldn't consider it a higher-order function.  A higher-order function takes a function as input, or yields a function as its output.  In contrast, it sounds to me like your compiler extension is accepting data as input (the abstract syntax tree) and producing data on its output.
I suppose you could consider the AST a specification of a function, but that seems like a stretch to me.
I'm not sure that what name you attach to it matters much, from a computer science perspective.  A rose by any other name, and all that.


Can an instruction with a dependency read the register in same cycle as it's being written? I'm learning about superscalar processors and struggling with it a bit. I wrote an assembly program and now must move it through in-order in-issue completion and I have a question about instructions as they move through the latter stages of the pipeline.

I have two instructions I1 and I2. I1 performs an operation on R1 and R2 and then loads the result in to R1. I2 needs read the new result of R1 and then overwrite R1, but obviously cannot do so until R1 is finished, otherwise I1 will be incorrect. At what point will I2 be able to correctly read the new result of R1? While I1 is in the WB stage or once I1 has finished the WB stage?

Thanks! I also realize this may not be an ideal design, but it's what I have to work with. Also, if this is not CS related and belongs in a different stack exchange, please move.

With modern processors, arithmetic units tend to be able to deliver results simultaneously to a register, and to another arithmetic unit that requires that result.

There is a limit to this, so if you have three add instructions "x = a + b, y = x + x, z = x + x", then the a+b operation is unlikely to be able to send the result to a register, and to four inputs of two more additions. Even reading from a register is likely limited, so in this extreme example you could have (assuming an adder can forward to one input and a register, and registers can be read by two inputs):

Cycle 0: Adds a+b, sends result to x and first input of y = x + x.
Cycle 1: y = x + x reads second input from x; z = x + x reads first input from x
Cycle 2: Adds x + x, sends result to y. z = x + x reads second input
Cycle 3: Adds x + x, sends result to z.

On the other hand, take x = a + b, y = x + a, z = x + b:

Cycle 0: Adds a + b, sends result to x and first input of y = x + a
         y = x + a reads a, z = x + b reads b.
Cycle 1: Adds x + a, sends result to y. z = x + b reads x.
Cycle 2: Adds x + b, sends to z.

So an instruction cannot read a register at the time it is written to, but often results can be forwarded to an instruction at the same time they are written to a register.


About a universal (functionally complete) function producing a constant I read in a note the following:

Suppose we have a boolean function $f(x,y,z,w)$, if $f(a,a,a,a)=1$ then $f$ can't be functionally complete.

Why is that? how does it imply that $f$ can't produce nand or nor?

The claim is false if you're allowed to use constants. Take $f(x,y,0,0) = f(x,y,1,1) = 1$ and $f(x,y,0,1) = f(x,y,1,0) = x \text{ NAND } y$. If you're not allowed to use constants, then every function that you can get by composing $f$ with itself will have the property that if all inputs are 1, then so is the output. NAND doesn't have that property.


Algorithms: Difference Constraints I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem:

  Consider the following set of difference constraints:

x1 - x4 <= 1
x2 - x1 <= 2
x2 - x4 <= 0
x3 - x1 <= 1
x4 - x1 <= -1
x4 - x3 <= -2

  What is the solution that will be provided by the shortest path based algorithm for this set of constraints?

I know that you are supposed to create a graph using these constraints, so that there is one edge per constraint and one node per variable. So, for this problem, there would be four nodes: x1, x2, x3, and x4. There would also be six edges because there are six constraints. The first constraint should make an edge from x4 to x1 with a weight of 1. The second constraint should make an edge from x1 to x2 with a weight of 2. The rest of the constraints are made into edges following the same pattern.

So after you create the graph, you're supposed to run a shortest path algorithm on it, and it somehow gives you the values for each variable. This is the part that I am unsure about.

The answer that I got when I did this was that x1 = 0, x2 = -1, x3 = 0, and x4 = -2. Unfortunately, this doesn't work because of the first and third constraints.

Can someone walk me through how to get the right answer using the shortest path based algorithm for this question? Thanks!

You seem to already know the correct procedure but you have calculated the shortest paths incorrectly.

Procedure:

Create a source vertex ($s$) and add zero-weight edges from the source to all vertices.
Compute single-source shortest path from the source to each vertex. (If a negative-weight cycle exists, there is no solution to the set of constraints.)
The constraints are solved by assignments $x_i = \delta(s, x_i)$ where $\delta(s, x_i)$ is the shortest path from $s$ to $x_i$.

x1 = -1 (s -> x3 -> x4 -> x1)
x2 = -2 (s -> x3 -> x4 -> x2)
x3 =  0 (s -> x3)
x4 = -2 (s -> x3 -> x4)

Source: See slides 6-10 of http://courses.csail.mit.edu/6.006/spring11/lectures/lec17.pdf


What does the $O^*$ notation mean? I'm recently reading some papers on the maximum independent set problem, all the algorithms' time complexity is donated by $O^*()$ notation, like $O^*(1.0836^n)$. One paper says "the $O^*$notation suppresses polynomial factors in the input size."  I'm a little bit confused and couldn't find helpful materials on the Internet. Could you guys clarify it for me? Any related literature or links will be appreciated.

Thanks in advance!

Similarly as $O$ notation which "ignores constant factor", $O^*$ notation "ignores polynomial factor" that is: $f(n) = O^*(g(n))$ if there exists some polynomial $p$ such that $f(n) \leq p(n) g(n)$ for $n$ large enough. This is mainly used to compare functions which are growing exponentially, in which case polynomial factors are less important.

This notation is not as standard as $O,o,\Omega, \omega$. Sometimes, this notation or $\tilde{O}$, as observed by @Raphael, is used to ignore polylogarithmic factor when people focus on ptime algorithms.


Is it decidable that a context free language contains a given regular language? I've been asked to solve this problem, but I'm completely stuck now.

  Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable?

I know I've to find a reduction, and as a hint they told me that it is related to Acceptance Problem or Post Correspondence Problem, or probably with Non-empty Intersection problem ( $\{\langle G1, G2\rangle \in \text{CFG} \times \text{CFG} \mid L(G1) \cap L(G2) \not= \emptyset\}$), which are undecidable.

I've been reading about these problems for hours, and reading about reductions from these problems to others trying to find any idea, but I'm stuck.

I'd really appreciate any help, whether some hints or the answer.

Indeed, it is undecidable whether a context-free grammar generates all strings over its alphabet. But I guess you want to know how such a result is obtained.

The classical result "undecidable $L(G) = \Delta^*$ for CFG $G$" was obtained by Bar-Hillel, Perles and Shamir in 1961 using a coding of Turing Machine computations. They showed that the set of strings that where not codings of valid TM computations form a context-free language. Of course if there are no valid computations then that language is $\Delta^*$.

You can do the same with codings of solutions of the Post Correspondence Problem. Given set of pairs $(u_1,v_1), \dots, (u_n,v_n)$ you can code PCP "solutions" as strings $u_{i_1}\dots u_{i_k}\#v^R_{i_k}\dots v^R_{i_1}$ such that both sides are equal (or rather, mirror image).

Argue that the non-solutions form a context-free language.


Intuitive explanation on why stochastic encoding performs better in channel coding I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can achieve nearly 0 probability of error when using $O( \log \log M)$ bits, where $M$ is the total number of messages. Instead, deterministic encoding would require us to use at least $O(\log M)$ bits instead.
Can anyone give an intuitive explanation of why stochastic encoding is so effective? One possible idea which opposes the result is that the stochastic code would result in many possible codes for a single message which should make it more difficult for the decoder as the codes are now more 'tightly packed', i.e., there are many more valid codes possible for the same number of bits transmitted.

Well, I think you are conflating two things. It is correct that in a lot of settings probabilistic encoding (e.g., Polar Codes, Convolutional Codes, LDPC Codes) [assuming you know a good model for the noise process of the channel] does much better than algebraic coding, intuitively because channels have memory and block codes ignore that memory.
However, Ahlswede's Identification Problem is quite different. It is NOT a traditional channel coding problem There is a good review  here
The author states

In the problem of identification via channels, introduced by Ahlswede and Dueck the receiver is only
interested in testing whether a particular message was sent, but the encoder does not know which message
the decoder wants. Errors are now considered in terms of false alarm and missed identification. It turns out
that for this case, one can design systems such that the number of different messages one can identify grows
doubly exponentially with the blocklength. The trick is that each message can map into a list of codewords
and the encoder selects one randomly. As long as the fraction of the pairwise overlap of these lists is small,
the error probabilities will be small


Is there an example of an AVL tree that is taller than a binary heap? I am curious because I took a quiz and answered false to the question:

"The height of an AVL tree may be greater than the height of a binary heap with the same elements."

I have been trying to think of an example, but I just cannot figure it out. Does anyone know when this is the case?

Consider the following AVL-tree with 7-nodes. It has 4 levels.
The form of a binary heap is determined by the number of its nodes. With seven nodes it would be the perfectly balanced binary tree with 3 levels.

An AVL-tree is height balanced, in the sense that the height of two sibling subtrees never differs by more than one. Leaves however may exist on several levels. Binary heaps are much more rigidly structured. Leaves exist only on two  levels, and nodes are added level by level, from left to right.

The example tree is of a special type: it has the minimal number of nodes to get a tree of this height.

OK for an exercise, but it is quite uncommon to compare AVL-trees and binary heaps. The value of the nodes are ordered in completely different ways. Also binary heaps are in fact implemented as arrays, not as pointer structures.


Proving closure under complementation of languages accepted by min-heap automata This is a follow-up question of this one.

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that the regular languages are closed under a variety of operations (we may limit ourselves to basic operations such as union, intersection, complement, difference, concatenation, Kleene star, and reversal), whereas the context-free languages have different closure properties (these are closed under union, concatenation, Kleene star, and reversal).

  Is HAL closed under complementation?

Claim: $\mathrm{HAL}$ is not closed against complement.

Proof Idea: We have agreed that $\mathrm{EPAL}$ (the language of even palindromes over a non-unary alphabet) is not in $\mathrm{HAL}$. We show that $\overline{\mathrm{EPAL}} \in \mathrm{HAL}$.
This works for type-1 only (as type-2 can accept $\mathrm{EPAL}$); the proof can be adapted to suit type-2 though, see below.

Proof: Note that

$\qquad \displaystyle \begin{align*}
  \overline{\mathrm{EPAL}} &= \{vw : |v|=|w|, v\neq w^R\} \\
                           &\cup\ \,\{w : |w| \in 2\mathbb{N}\!+\!1\}
\end{align*}$

We construct a min-heap automaton with two heap symbols $b < a$ that works like this:

In the starting state, decide nondeterministically wether the input's length is even.
On the uneven path, use finite control to accept the input if and only if its length is odd.
On the even path, proceed like this:
$$ \underbrace{v_1\ \dots\ \mathbf{v_{i}}}_{+a}\ \underbrace{v_{i+1}\ \dots\ v_n}_{+b}\ \underbrace{w_n\ \dots\ w_{i+1}}_{-b}\ \underbrace{\mathbf{w_i}\ \dots\ w_1}_{-a}$$

Start by adding one $a$ to heap for every read symbol.
At a nondeterministically determined position, store the current symbol in finite control and start adding one $b$ (and no $a$) to heap for every read symbol.
At a nondeterministically determined position, stop adding symbols and consume one $b$ per input symbol.
When all $b$ are consumed, compare the current symbol with the one stored in control. If they are unequal, continue; else reject the input.
Consume one $a$ per input symbol. If the heap is empty at the same time the input ends, accept the word; reject otherwise.

The described min-heap automaton accepts $\overline{\mathrm{EPAL}}$. As its complement, $\mathrm{EPAL}$, is not in $\mathrm{HAL}$, we have proven the claim.

Note: The proof can be performed in the same way with $\{ww \mid w \in \{a,b\}^*\}$ (which is in $\mathrm{CSL} \setminus \mathrm{HAL}$) and its complement. This extends above result to type-2.


Distributed algorithm can be executed in a single process Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency primitives (i.e channels and goroutines)

AFAIK "distributed" means things are happening on multiple machines. But this is running in a single process. (the fact that all threads are sharing memory is irrelevant since the algorithm's implementation doesn't depend or make use of it)

So can we call the system consisting of the threads + channels a distributed system?
This seems to have all characteristics:
- threads run independently and in parallel much like nodes (assuming enough processors)
- communication via message-passing

If we choose to not call it a distributed system, then why is the algorithm labeled distributed if it can run on a non-distributed system?

From Wiki:

  Distributed algorithms are a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing.

It is inherent type of algorithm to be run independently with no requirement that processors are in the same machine. Think of it as the type of workload being cut into independent pieces.

From Wiki:

  A distributed system is a network that consists of autonomous computers that are connected using a distribution middleware. They help in sharing different resources and capabilities to provide users with a single and integrated coherent network.

So the algorithm is distributed, but the system you have described is not. This is just algorithm with different purpose run in less distributed environment with potential to be sub-optimal in such setting.

Another example: you can run sorting network (say bitonic sort) in one thread, it doesn't make it serial algorithm, but overhead is costly in such case.


Minimum spanning tree - Prim's algorithm I have to demonstrate Prim's algorithm for an assignment and I'm surprised that I found two different solutions, with different MSTs as an outcome. Now I now that shouldn't happen, so I wonder what I did wrong ?

Here is the exercise:

The first solution (using Prim's) is visiting the nodes in the following order: v0,v1,v8,v7,v6,v3,v2,v4,v5 Here the MST has a weight of 37, which is the same result that I got by using Kruskal's on the same graph.

The second solution (again using Prim's) however is the following order of visited notes: v0,v1,v3,v2,v7,v8,v6,v4,v5 , which leads to a MST with a weight of 39. How can this be ? Where is my mistake ?

Thanks in advance

Prim's algorithm could give different solutions (depending on how you resolve "ties"), but all solutions should give a MST with the same (minimal) weight, which is not the case here.

Your second solution: $v_0,v_1,v_3,v_2,v_7,v_8,v_6,v_4,v_5$ is incorrect. After adding $v_0,v_1,v_3,v_2$ you add $v_7$. But the minimum distance between $v_7$ and any existing vertex in the tree is $6$. Vertex $v_6$ however has a distance of only $4$, and should thereby be added first.

You could continue this, and end up with a solution that is indeed different from your solution 1, but has the same weight. For example, $v_0,v_1,v_3,v_2, v_6, v_7,v_8,v_4,v_5$, which gives an MST of weight $37$, as expected.


How to write a closed term with this type? X→Y →(X+Y)×Y

I'm confused about how to get the type (X + Y).
If I assume m: (X + Y), n: X, k: Y
then I can get $${m:X+Y \vdash \lambda n:X.\lambda k:Y.<m, k>}$$
which get the right type. But I can't reduce the context m: X + Y.
So, could anyone tell me how to make it? Thanks a lot.

Whenever a new type constructor is defined, it comes with introduction and elimination terms. These are part of the definition.

In the case of sums, the following are part of the definition of what it means to have $X + Y$:

given types $X$ and $Y$ there is a type $X + Y$
given a term $e : X$ there is a term $\mathsf{inl}(e) : X + Y$
given a term $e' : Y$ there is a term $\mathsf{inr}(e') : X + Y$
(there is also an eliminator and equations which I am not writing down here)

So I think this is the point you missed: we do not just say "there is a type $X + Y$" without anything else, as that would be completely useless. We also provide ways of constructing (introducing) and deconstructing (eliminating) terms of the new type.

Now that we know that $\mathsf{inl}$ and $\mathsf{inr}$ are there by definition of sum types, it is easy:
$$\lambda x : X . \lambda y : Y . \langle \mathsf{inr}(y), y\rangle.$$
By the way, Haskell's djinn package can help you with this (I'd show a demo but OSX El Capitan broke cabal).


Subset-sum variation, multiple sums Subset-sum problem is NP-complete. I presume so is the problem of determining, given a positive integer $p$, whether in a set of positive integers $\{x_1,x_2,...,x_n\}$ there is a subset which sums to one of the numbers $\{p-1,p,p+1\}$. Am I correct?

I've been struggling to reduce standard Subset-sum to this variation, but for no good so far. Can you see any other reduction? Or could give me a hint on this  one? Perhaps I'm fixed for that Subset-sum and don't some other obvious possibility.

Hint: Given an instance $\{x_1,\ldots,x_n\},T$ of SUBSET-SUM, construct the instance $\{2x_1,\ldots,2x_n\},2T$ of your problem.


Unranking paths in a graph/lattice A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified rank. Thus, ranking and unranking can be considered as inverse operations.

The following lattice has 9 unique max length paths from {} to {1,2,3,4,5}, which can be obtained by a depth first search.

(The graph is directed, with arrows pointing down)

Is it possible to write a function that generates the N'th path without enumerating paths 1..N-1.

see: https://math.stackexchange.com/questions/510911/computing-all-simple-paths-in-a-distributive-lattice-in-parallel for more problem details.

Suppose without loss of generality that there is one source $\emptyset$ and one sink $S$. For each node $v$ in your digraph, you can compute recursively the number $N_v$ of unique maximum length paths from $\emptyset$ to $v$: at $\emptyset$ we have $N_\emptyset = 1$, and at other points, $N_v = \sum_u N_u$, where the sum goes over all immediate predecessors of $u$.

This suggests the following encoding for maximal paths at a node $v$. Suppose the immediate predecessors of $v$ are $u_1,\ldots,u_k$, in some arbitrary but fixed order. We will encode all paths as numbers in the range $[0,N_v)$ ($=\{0,\ldots,N_v-1\}$) in the following way: all paths through $u_1$ will be encoded in $[0,N_{u_1})$, all paths through $u_2$ will be encoded in $[N_{u_1},N_{u_1}+N_{u_2})$, and so on. Inside each interval, we apply the same encoding scheme recursively. By applying this scheme for $v = S$ (the sink), we get an efficient encoding system for all maximal paths.


Find longest common subsequence in limited space Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS).

Example: A longest common subsequence of bandana, cabana, and magazine is aan.

I'm trying to find an algorithm which uses $O(|x|\cdot |y| \cdot |z|)$ space where $|s|$ denotes the length of the string $s$.

The standard dynamic programming algorithm for the LCS$(x,y)$ problem runs in time $O(|x|\cdot |y|)$. Simply speaking you fill out a $|x| \times |y|$ table $T$ using the recursion
$$T[i,j] =
\begin{cases}
0
& \mbox{ if }\ i = 0 \mbox{ or }  j = 0 \\
 T(i-1,j-1) +  1
& \mbox{ if } x_i = y_j \\
  \max\{T[i,j-1],T[i-1,j]\}
& \mbox{ if } x_i \ne y_j \\
\end{cases}.$$

A natural extension of this recursion leads to an algorithm that fills out an $|x|\times |y|\times |z|$ table and computes the LCS of three strings.

Notice that you can improve the required space even further (while keeping the asymptotic running time) using  Hirschberg's extension.


If $V$, $E$ and $F$ is respectively the number of vertices, edges and faces in a maximally triangulated graph, then why do we have $3F = 2E$? Suppose we have a maximally triangulated graph $G$, where $V$, $E$ and $F$ is respectively the number of vertices, edges and faces. The following graph should be a maximally triangulated graph.

Apparently, the equation $3F = 2E$ holds for $G$. Why (intuitively) is this the case?

Every face is a triangle (hence, the name, "maximally triangulated graph"). Every face is thus composed of three edges (or sides). So, if we have $F$ faces, then we may be tempted to say that there are $3F$ edges. This is not the case because an edge contributes to exactly $2$ faces. So, in $3F$ we are counting every edge twice. So, $\frac{3F}{2} = E \iff 3F = 2E$.


Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length? I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using the pumping lemma (even though I know it applies with our choice of string, since the string is at least $n$ long).

To apply the pumping lemma for regular languages:

You assume some pumping length $p > 0$: Suppose a pumping length $p$.
You pick a string $s$ such that $|s| \geq n$: Indeed, $a^pb^p$ is a good one since $|a^pb^p| = 2p \geq p$.
Now, you have to consider all the partitions of $s$ as $xyz$, such that

$|y|>0$ and
$|xy| \leq p$.

In this case, the 2nd inequality restricts $y$ to contain only $a$'s. Therefore, all the possible partitions are of the form $y = a^k$, $x = a^{p-k-r}$ and $z = a^rb^p$ for $k$ and $r$ such that $k > 0$ and $p \geq k + r$.

For every possible partition of the previous step, you have to show that there is some $i\in\mathbb{N}$ such that $xy^iz$ is not in the language.

Here, consider $i = 0$. Then $xy^0z = xz = a^{p-k-r}a^rb^p = a^{p-k}b^p$.
It is now a matter of showing that $p-k\neq p$, or, equivalently, that $k > 0$ which is already true.


Invariant on "Find K Closest Elements" problem I run across this problem:

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

For example, given [1,2,3,4,5], k=4, x=3, we should have [1,2,3,4]. There is one solution using binary search:

    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0;
    int right = arr.size() - k;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (x - arr[mid] <= arr[mid+k] - x)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return vector<int>(arr.begin() + left, arr.begin() + left + k);
}

I couldn't understand if (x - arr[mid] <= arr[mid+k] - x) part and I try to explain this using precondition, invariant, and postcondition like we do with the
simple binary search problem. But, I have no clue what's the invariant in this case and how we prove the invariant holds through the loop execution. I also follow the article from topcoder but that doesn't help.

My attempt for the invariant: the index of the first number that is among the k closest values for the given target is in [left, right]. However, I cannot fully convince myself this is correct and actually holds during the loop.

If this question belongs to stackoverflow, let me know and I'll post it there instead.

Thanks in advance.

If x - arr[mid] <= arr[mid+k] - x, then for any l that l > mid, we have

x - arr[l-1] <= x - a[mid] <= arr[mid+k] - x <= arr[l+k] - x,
arr[l-1] - x <= arr[l+k] - x,

which means |arr[l-1] - x| <= |arr[l+k] - x|. So for any range [l, l+k] where l > mid, we can move it to left until l == mid while the elements contained are no farther from x, therefore it is safe to set right = mid.

Otherwise, the proof is similar.


efficient algorithm for min cut with specified number of vertices Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to minimize the number of edges going between $C$ and $\bar{C}$. Algorithms are known for this problem which solve it in polynomial time. My question is, what if one additionally specifies the constraint that $|C| = n$ for some $n < |V|$? That is, we wish to find the set of $n$ vertices with the minimal number of edges connecting it to the rest of the vertices. Are there also efficient algorithms for this case? I am interested both in the question of whether this problem is formally solvable in polynomial time (which I would guess that it is) and also in what algorithms are best in practice.

For $n= \frac {|V|} 2$, it's called Minimum Bisection, and it's NP-hard. There exists an $O(\log^{3/2} n)$-approximation: "A polylogarithmic approximation of the minimum bisection".
If you are interested, the more general problem is splitting into multiple components of the same size, and it is called Balanced Graph Partitioning. For more than 2 parts no finite approximation exists unless P=NP: "Balanced Graph Partitioning" (Andreev, Rakke), since you can't efficiently check if the answer is 0.
If the parts are not necessarily exactly balanced (a small imbalance is allowed), an $O(\log n)$-approximation algorithm exists: "Balanced Partitions of Trees and Applications".

Some algorithms (also check https://en.wikipedia.org/wiki/Graph_partition and "references" sections of the following papers):

Local search with various flavors: we start with some partitioning and then try to swap vertices between parts to minimize the cut. E.g. we compute "gain" for each vertex (improvement if we move it to another part), and swap vertices with the maximum gain. Its advantage is that you can apply it after any other algorithm.

Spectral partitioning (see e.g. Spectral Graph Theory and Graph Partitioning): uses the second eigenvector of a Laplacian matrix to approximate the partitioning (e.g. by moving the smallest $|V|/2$ coordinates to the first part). Works surprisingly well. However, I'm not sure it can be adapted to the case when you want an unbalanced bisection (e.g. $1:2$ instead of $1:1$).

Linear embedding: "Distributed Balanced Partitioning via Linear Embedding". We embed vertices into a one-dimensional array while minimizing sum over all pairs of vertices: the distance between them multiplied by the weight of their edge. Then we just split this array into consecutive chunks of required sizes. Didn't work that well in my experience.

(Ads) Our paper: "Multi-Dimensional Balanced Graph Partitioning via
Projected Gradient Descent", where we used gradient descent to find minimum bisection: for each vertex we introduce a variable which roughly represents a probability that the vertex belongs to the first part, and minimizing the cut reduces to constrained optimization of a quadratic function. It's a bit outperformed in practice by a fine-tuned local search, but it works really well when you have multiple balance constraints.

Aside from the spectral method, all of them can be trivially adapted to partitioning the graph in arbitrary proportions.
There are also standard solvers: KaHIP, METIS. In my experience, KaHIP was pretty good. I'm not sure they support splitting into parts of arbitrary sizes though.


Equivalence of regular expressions Is it possible, in general, to determine whether two regular expressions admit the same set of strings?

Also, in particular, is it possible to determine whether a given regular expression admits the same set of strings as the regular expression ".*" (i.e., accepts anything).

This seems like a dupe, but I couldn't find one in a cursory search. Given that, we can solve your problem as follows:

Generate NFAs $N_1$ and $N_2$ for the regular expressions $r_1$ and $r_2$;
Generate DFAs $M_1$ and $M_2$ for the NFAs $N_1$ and $N_2$;
Generate DFAs $D_1$ and $D_2$ such that $L(D_1) = L(M_1) \setminus L(M_2)$ and $L(D_2) = L(M_2) \setminus L(M_1)$;
Determine whether $L(D_1) = L(D_2) = \emptyset$; if so, $L(r_1) = L(r_2)$; else, $L(r_1) \neq L(r_2)$.

You can do (1) by using Kleene's theorem demonstrating that regular expressions and finite automata have the same expressive power. To each of the operations union, concatenation, and Kleene closure, there corresponds an automaton-based construction which accepts what the regular expression generates. By recursivly applying these constructions to subexpressions you can build an NFA to accept the language generated by a regular expression.

To do (2), you typically will want to use the powerset construction (sometimes called the subset construction). This involves constructing a DFA whose set of states equals the set of subsets of stats from the NFA. Transitions now connect subsets of states which are reachable from each other. The resulting DFA may have up to $2^{|Q|}$ states, where $Q$ is the set of states in your NFA.

To do (3), you can use the Cartesian product machine construction to generate machines with up to $|Q_1| \times |Q_2|$ states. Every state in your product machine will correspond to a pair of states from the operand machines. You must choose the set of accepting states to effect the correct operation; in our case, set difference.

To do (4), you can try all strings of length up to and including $|Q|$. If the machine accepts anything, it must accept some string of such a length. If you check all the strings and nothing's accepted, you know that $L(M) = \emptyset$. If that's the case, by construction, then the one language is a subset of the other. If both languages are subsets of each other, the languages are equal, by definition of set equality.


Efficient bandwidth algorithm Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario:

Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 Mbps network card.
Node 3 is connected to 5 at 50 Mbps. Node 3 has 100 Mbps card.
Node 4 is connected to Node 3 at 40 Mbps. Node 4 has 100 Mbps card.

(Sorry about not having a picture)

Problem: If Node 1 starts sending data to its immediate nodes (2 and 3), we can clearly see it's network card capacity will be drained out after Node 3. Whereas if it were to skip node 3 and start sending to node 4, the data will eventually reach to node 3 via 4 and hence, node 5 will be getting data via node 3.
The problem becomes more complicated if all the links were of 50 Mbps and we can clearly see that node 2 and node 4 are the only way to reach all nodes.

Question: Is there an algorithm which gives the optimal path to ALL nodes keeping the network (card) capacity in mind?

I read the shortest path algorithm,max flow algorithms but none of them seem to address my problems. perhaps,im missing something. I'll appreciate if someone can help me out.

According to your description:

Each node in the network can relay a certain amount of traffic per time unit.
Each link has a certain capacity.

In order to convert your problem to an instance of network flow problem, one can do the following transformation. In the underlying graph of network, $G = (V,E)$, for any vertex $u \in V$ that has an outgoing edge $(u,v) \in E$, add an auxiliary vertex $u'$. Next, add an auxiliary edge $(u,u')$ with capacity equal to the capacity of $u$ for any auxiliary vertex $u'$. Finally, replace all $(u,v) \in E$ with $(u',v)$. Below is an illustration of how the network graph looks like before and after transformation.

The transformed graph can be seen as a flow network with node $1$ as source and nodes $2$ and $5$ as sinks. More generally, nodes with no incoming edges can be treated as source(s) and those with no outgoing edges as sink(s). Introducing an additional vertex to which all other sinks are connected with infinite capacity, you can further reduce your problem to a single-source single-sink flow network.

The goal is to find the optimal path to all nodes. Therefore, aside from the value of maximum flow itself, the algorithm you use for finding such a flow is also important. Edmonds-Karp algorithm uses BFS for finding the maximum flow over the shortest path. However, you want your maximum flow to go through as many nodes as possible. Thus, you need to make sure that your flows use longest paths between source and sink.

Luckily, for Directed Acyclic Graphs (DAGs), the longest path problem can be solved in linear time using dynamic programming. Thus, by modifying Edmonds-Karp algorithm such that it uses longest paths for flow augmentation, you ensure that the maximum number of nodes will be visited by each augmenting path.

In your example, the modified algorithm will output the following flows in order:

A flow of value $40$ over path $\langle 1,1',4,4',3,3',5 \rangle$.
A flow of value $10$ over path $\langle 1,1',3,3',5 \rangle$.
A flow of value $50$ over path $\langle 1,1',2 \rangle$.


What is growth of $\psi_q(m) = \min \{ p: m ∣ (q^p−1) \}$ for fixed $q$? I have to estimate the computational complexity of some algorithm that does $\psi_q(m)$ iterations. Assume that all inputs $m$ are coprime to $q$.

So I need to know what growth the $\psi(m)$ has.

Bottom line: I expect the answer to be $\psi_q(m) = O(m)$, and this to be approximately tight: I don't expect you to be able to prove any significantly better upper bound on $\psi_q(m)$.

Basically, $\psi_q(m)$ is the order of $q$ in the multiplicative group of integers modulo $m$, i.e., in $(\mathbb{Z}/m\mathbb{Z})^*$.  In other words, it is the smallest natural number $p$ such that $q^p \equiv 1 \pmod m$.

The structure of $(\mathbb{Z}/m\mathbb{Z})^*$ is well-characterized: for instance, when $m$ is prime, it is cyclic of order $m-1$.  As a consequence, $\varphi(m-1)$ of the elements of this group will have order $m-1$ (where $\varphi(\cdot)$ denotes Euler's totient function).  It's known that the typical value of Euler's totient function $\varphi(r)$ for a random value of $r$ near $N$ is about $6N/\pi^2$, i.e., $\Theta(N)$; so heuristically we can expect that the typical value of $\varphi(m-1)$ will be $\Theta(m)$ (roughly some constant times $m$).  See, e.g., this summary on Wikipedia.

In particular, when $m$ is a random prime, close to half of all elements of $(\mathbb{Z}/m\mathbb{Z})^*$ have order $m-1$: or to say this in a more careful way, we should expect that a constant fraction of group elements will have order $m-1$.  This means that, for a randomly chosen element of $(\mathbb{Z}/m\mathbb{Z})^*$, the average order will be $\Theta(m)$.  Of course, $q$ is not a random element -- it is a fixed number -- but as $m$ gets large, we can heuristically treat $q$ as a  random element of $(\mathbb{Z}/m\mathbb{Z})^*$.

Moreover, the primes are relatively dense among all the integers.  (And even for a random composite, I think the same is still true: a randomly chosen element of $(\mathbb{Z}/m\mathbb{Z})^*$ will have expected order $\Theta(m)$.)

Therefore, heuristically, I think $\psi_q(m) = O(m)$ is about the best bound you're going to be able to get.  This entire argument is based upon heuristics and is not something I can prove formally, but I think it should give an estimate that's good enough for evaluating the running time of your algorithm.


Is $L(G) \subseteq L(R)$ decidable? Is the following problem decidable?

  Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \subseteq L(R)$?

It is given that the following problem is undecidable

  Given a context-free grammar G, is $ L(G) = \Sigma ^*$ ? $\ (1)$

and this problem decidable

  Given a context-free grammar G, is $ L(G) = \emptyset $ ? $\ \ \ (2)$

My thought is this:

$L(G) \subseteq L(R)$ is the same as $ L(G) \cap \overline{L(R)} = \emptyset $. So, since regular languages are closed under complement, and the intersection of a $CFL$ with a $RL$ is a $CFL$, $L(G) \cap \overline{L(R)}$ is a $CFL$. Now, $(2)$ is decidable, so if we can create a context-free grammar for $L(G) \cap \overline{L(R)}$ and give it as input to a decider for $(2)$ we have decided our initial problem.

Is my thought correct? And if yes, how can create such a grammar?

Yes, your thought is correct. The only missing part, as you pointed out, is whether or how we can create a CFL algorithmically for the intersection of a CFL with a RL.

If you take a close look at any proof for the fact that the intersection of a CFL with a RL is a CFL, you will find that the proof is constructive or can be made to be constructive easily, giving that there is an algorithm to construct the CFL for a given PDA. Here "constructive" means the same as "algorithmic". It is just by convention or history, we tend to use the word "constructive" instead of "algorithmic" to describe a proof.

You can check your textbook, or this and this.

Exercise. Is the following problem decidable?

  Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \supseteq L(R)$?


In what sense is the Mandelbrot set "computable"? The Mandelbrot set is a beautiful creature in Mathematics.

There are a lot of beautiful images of this set created with high precision, so obviously this set is "computable" in some sense.

However, what concerns me is the fact that it is not even recursively enumerable - simply because the set is uncountable. This could be resolved by requiring some sort of finite representation of the points.

Furthermore, although we know for sure that a lot of points belong to the set and others do not, there are also a lot of points whose membership in the set we don't know. All the images we've seen so far may include a lot of points that "up to n iterations kept in bound," but those points may not actually belong to the set.

So, for a given point with a finite presentation, the problem "Does this point belong to the set?" has not been proved to be decidable yet, if I am right.

Now, in what sense (by which definition) can we say the Mandelbrot set is "computable"?

There are several ways of defining what it means for the Mandelbrot set to be computable. One possible definition is the Blum–Shub–Smale model. In this model, real computation is modelled by a machine similar to a RAM machine, whose access to real numbers is restricted to basic arithmetic and comparisons. Blum and Smale showed that the Mandelbrot set is uncomputable in this model, though its complement can be recursively enumerated using the traditional algorithm used for drawing them.

Another model is computable analysis, in which the Mandelbrot set is probably computable, as shown by Hertling (conditional on a widely believed conjecture, the hyperbolicity conjecture). In this model, computing the Mandelbrot set means being able to compute an approximation to the Mandelbrot set, within any desired accuracy (for the exact definition, see the reference on computable analysis).

Why is it, then, that the computer seems to be able to draw the Mandelbrot set? The main difficulty in showing that the traditional algorithm works is that it is difficult to tell in advance how many iterations to run before we decide that the point belongs to the set. Hertling shows that if the widely believed hyperbolicity conjecture holds, then there is a reasonable such bound. Presumably, the programs simply wait long enough; or they don't wait long enough, but only get a small fraction of the points wrong.


How to replace one symbol with two on Turing machine's tape I want to implement following algorithm on Turing machine:

  rewrite binary numbers to their unary counterparts. For example: 101
  will be rewritten to a string of 5 consecutive bars

(wikipedia)

But I don't know how to make the replacement "|0" -> "0||" because it requires 3 cells. Basically I want to insert additional cell or shift all cell symbols from current position to the left(right). Is there a simple way of doing it?

The way I'd do it is as follows:
The syntax is from the Turing simulator I link to below. It is

[transition name],[symbol]
[next transition],[new symbol],[direction]

The actual code:

name: Binary to Unary
init: moveright2
accept: end

moveright2,_
moveright1,_,>

moveright2,0
moveright2,0,>

moveright2,1
moveright2,1,>

moveright1,_
moveleft,1,<

moveright1,0
moveright1,0,>

moveright1,1
moveright1,1,>

moveleft,_
sub1,_,<

moveleft,0
moveleft,0,<

moveleft,1
moveleft,1,<

sub1,0
sub1,1,<

sub1,1
moveright2,0,>

sub1,_
blankout2,_,>

blankout2,_
blankout1,_,>

blankout2,1
blankout2,_,>

blankout1,1
end,_,>

Basically move till you've passed two blanks(Step 1), then write a 1(Step 2), move left till you find a blank(Step 3), treat the number to the left as a binary number and subtract one from it(see below for details on how this works)(Step 4), Then repeat steps 1-4 until you can't subtract any more(in my case the subtract routine turns all 0's in the number we've been subtracting from to 1 and then hits a blank), go back turning all ones to blanks till you hit a blank, then go one farther turning that one into a blank.

It turns 101 into 11111

Subtraction routine, start at the far right of the number, if it's 0 change it to one and move left doing the same thing to each digit you come across, if it's one see step 1


Constructing an optimal solution to bin packing using a "magical function" $\phi$ I am taking an introductory course in complexity theory, and as an exercise, we were given the following problem.

Consider the bin packing problem, with objects of positive (rational) weights $W = \{w_1, w_2, ..., w_n\}$ ($0 < w_i \leq 1 \forall i$) that should be placed in bins of capacity 1. Imagine that you are given a "magical function" $\phi$ that, given a set $W$ of weights, gives you the minimum number $k$ of bins needed to pack the corresponding objects, i.e., $\phi(W) = k$. Let $T(n)$ denote the running time of the implementation of $\phi(W)$ and construct an algorithm that returns an optimal packing and runs in $O(f(n) + g(n)T(n))$ time, where $f(n)$ and $g(n)$ are polynomials.

First, I tried to recursively make binary partitions of $W$ by using that $\phi(W_1) + \phi(W_2) = \phi(W)$ for any partition $W_1 \cup W_2 = W$ such that $W_1$ and $W_2$ separates objects that are in different bins in an optimal solution (that is, there is an optimal solution such that no weights in $W_1$ share bins with any weight in $W_2$). When we eventually get $\phi(W_j) = 1$, we know that $W_j$ corresponds to the objects in bin $j$ in an optimal solution. However, my attempts here only yield algorithms with $g(n)$ being exponential in $n$.

Second, I tried to construct the bins one by one, using that, for all bins $B_j$, $\phi(B_j) + \phi(W \setminus B_j) = k$. Again, I have yet to find an algorithm where $g(n)$ is polynomial.

It's rather frustrating, as this seems to be a simple problem. Any suggestions on where I should begin?

Starting with $W$, repeatedly try to find two weights $w_i,w_j$ such that merging them (i.e., replacing both of them with $w_i+w_j$) doesn't increase the number of bins needed. Eventually, you will be left with $\phi(W)$ merged weights, which form a solution to the bin packing problem.


Conditional milp formulation I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following constraints are met:

$T_{ts}\geqslant-7$
$T_{it}\leqslant14$
$T_{ts}-T_{it}\geqslant5$
$\alpha_{ts,gshp}=0$

Regards

SR89

I might have found a solution to my problem by using four auxiliary binary variables $\alpha_1$, $\alpha_2$, $\alpha_3$ and  $\alpha_4$     $\epsilon\ \{0,1\} $. The constraints 1.-4. are rewritten using the big-M method.

Constraint 1

$T_{ts}\geqslant -7-M\cdot (1-\alpha_1)$
$T_{ts}\leqslant -7+M\cdot \alpha_1$

Constraint 2

$T_{it}\leqslant 15+M\cdot (1-\alpha_2)$
$T_{it}\geqslant 15-M\cdot \alpha_2$

Constraint 3

$T_{ts}-T_{it}+M\cdot (1-\alpha_3)\geqslant 5$
$T_{ts}-T_{it}-M\cdot \alpha_3\leqslant 5$

Constraint 4

$\alpha_{ts,it}=1-\alpha_{ts,gshp}$

Constraint 5

$\alpha_{ts,it}\geqslant \alpha_1+\alpha_2+\alpha_3+\alpha_4-3$
$\alpha_{ts,it}\leqslant \alpha_1$
$\alpha_{ts,it}\leqslant \alpha_2$
$\alpha_{ts,it}\leqslant \alpha_3$
$\alpha_{ts,it}\leqslant \alpha_4$

This might be a solution. Unfortunately computational time is exploding. Does someone know a less time-consuming workaround?

Best SR89


How to write stack programs for arithmetic terms? I have been given a question about a stack program which I can not solve.

Write a stack program to evaluate the term
$\qquad (((A+B)-(A*B))*C)/(((A-B-C))⁄2)$

How do I approach this problem?

What you want to do is; either first translate the expression into something that is easier for a stack machine to handle (like reverse polish).

The other is to use a modified shunting yard algorithm which can handle parenthesis.

You have 2 stacks: a result stack that holds the numbers where you push the numbers as you encounter them;

and an operator stack that holds operators in decreasing priority order.

When you need to add a operator that is of lower precedence you pop from the operator stack. Then apply that operator to the top 2 values on the result stack and replace them with the result. A parenthesis is of lowest priority but is the only one that can go on top of a higher priority operator.

When you encounter a closing parenthesis you pop from the operator stack and apply to the result stack until you find a closing parenthesis which you pop.


Quicksort vs. insertion sort on linked list: performance I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm.
Does anyone have any idea why this is?
Insertion sort has a complexity of $\Theta(n^2)$ and quicksort $O(n\log n)$ so therefore quicksort should be faster. I tried for random input size and it shows me the contrary. Strange...

Here the code in Java:

public static LinkedList qSort(LinkedList list) {

    LinkedList x, y;
    Node currentNode;
    int size = list.getSize();

    //Create new lists x smaller equal and y greater
    x = new LinkedList();
    y = new LinkedList();

    if (size <= 1)
        return list;
    else {

        Node pivot = getPivot(list);
        // System.out.println("Pivot: " + pivot.value);
        //We start from the head
        currentNode = list.head;

        for (int i = 0; i <= size - 1; i++) {
            //Check that the currentNode is not our pivot
            if (currentNode != pivot) {
                //Nodes with values smaller equal than the pivot goes in x
                if (currentNode.value <= pivot.value) {
                    {
                        x.addNode(currentNode.value);
                        // System.out.print("Elements in x:");
                        // x.printList();
                    }

                }
                //Nodes with values greater than the pivot goes in y
                else if (currentNode.value > pivot.value) {
                    if (currentNode != pivot) {
                        y.addNode(currentNode.value);
                        // System.out.print("Elements in y:");
                        // y.printList();
                    }
                }
            }
            //Set the pointer to the next node
            currentNode = currentNode.next;
        }

        //Recursive calls and concatenation of the Lists and pivot
        return concatenateList(qSort(x), pivot, qSort(y));

    }
}

The problem is that the analysis of Quicksort, as you have implemented it, assumes that accessing any element can be done at a constant cost, i.e. in $\mathcal O(1)$. This is not the case with linked lists.

Note that at the top of the while (right > left) { loop in your code, you cycle through all the elements until left and then repeatedly cycle through all the elements adjusting right. While in Quicksort this should just cost at most $\mathcal O(n)$, in your case it costs at most $\mathcal O(N^2)$, where $n$ is the current level of recursion and $N$ is the total number of elements.

As Louis pointed out in the comments below, there is a linked list analogue of Quicksort, but it needs to be implemented quite differently from what you did.

The bottom line: Linked lists are not arrays, and algorithms that will work well on arrays will not necessarily work well on linked lists. There are several good books on algorithms out there that will point you to good algorithms for each case.

Update

The code in the question has now been modified to reflect the implementation described by Louis below. There are still potential inefficiencies, however, in the selection of the pivot. In essence, any single operation inside the main loop which is not $\mathcal O(1)$ will mess-up the asymptotic behavior.

Oh, and creating new lists in every level of recursion is probably not extremely efficient either.


What is the name the class of functions described by O(n log n)? In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"):

O(1) is "Constant"

O(log n) is "Logarithmic"

O(n) is "Linear"

O(n^2) is "Quadratic"

O(n * log n) is ???

Is it just "n log n" or does it have a special name like the above?

It's called linearithmic time, and is a special case of a more general class known as quasi linear.  As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact they have a lower complexity than algorithms which run in $O(n^k)$ with $k > 1$.


help to find An efficient algorithm I'm trying to find An efficient algorithm for the following problem:

I have $n$ sets of numbers (different sets might have common numbers) and I need to find union combination of $k$ sets that Will yield the biggest set.

For example: if i have the sets $A1=\{1,3,4\},  A2=\{1,2,4\}, A3=\{5,7\}$ in that case $n=3$ and lets say that $k=2$.
 $|A1 \cup A3| =5$ or $|A2 \cup A3| =5$ will yield the biggest set
In contrast to $|A1 \cup A2|$ = 4.

If this is np hard question (i don't know if it is) a good Approximation will be fine
I think that brute force is $O({n \choose k})$ operations.

Your problem is known as the Maximum coverage problem. If $S$ is a solution (a set of at most $k$ sets), then an element is covered if it belongs to $\cup_{X \in S} X$. You want to find a solution that maximizes the number of covered elements. This problem is known to be $\textrm{NP}$-hard (see below for a possible reduction) and admits a greedy approximation algorithm that will cover at least a $\left( 1- \frac{1}{e} \right)$-fraction of the elements covered by an optimal solution.

In addition, there is an easy reduction from $3$-SAT to your problem.

Consider an instance of $3$-SAT with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. You can obtain an instance of your problem by creating two sets $T_i$ and $F_i$ for each variable $x_i$. The sets are defined as follows:

$T_i = \{ j \mid x_i \in C_j \} \cup A_i$ ;
$F_i = \{ j \mid \overline{x_i} \in C_j \} \cup A_i$,

where $A_1, \dots, A_n$ are arbitrary pairwise-disjoint sets, each containing $m+1$ integers between $m+1$ and $m+n(m+1)$.

Deciding whether you can select $n$ sets such that their union has cardinality at least $m+n(m+1)$ is now equivalent to deciding whether the $3$-SAT formula is satisfiable.


is it possible to find the maximal min cut in polynomial time? A maximal minimum cut is a minimum capacity cut with the largest number of edges.

This problem is NP-hard if 0 weight is allowed. We can reduce Not-All-Equal 3SAT to the decision version of this problem.

Given an instance of Not-All-Equal 3SAT with $n$ variables and $m$ clauses, for each variable $x_i$, we create two vertices $v_i$  and $v_i'$ with an edge between them for each variable. In addition, for each clause, for example, $x_1\vee x_2\vee \neg x_3$, we add three edges among $v_1,v_2,v_3'$ (thus they form a triangle). All edges have weight 0. Now we can see there is a minimum cut (in fact, every cut is a minimum cut) with at least $n+2m$ edges if and only if the Not-All-Equal 3SAT instance is satisfiable.


Why is it seemingly easier to resume torrent downloads than browser downloads? I really wonder how torrent downloads can be resumed at later point of time.
If such a technology exists, then why is it not possible in browsers?

It is often not possible to pause a browser download so that it can be resumed at a later point of time. Often, the download will start again from the beginning. But in the case of a torrent download, you can resume anytime.

One reason I could think of is that a browser makes an HTTP connection to the server which contains the file, and when this connection breaks, there is no data regarding how much file was saved so no resume is possible.

Is there a fundamental reason why torrent downloads are easier to resume than web downloads?

The bittorrent protocol was designed to transfer large files out-of-order. It divides files in chunks (pieces in bittorrent terminology), and maintains a map of which participant holds which chunks. One of the elementary commands is for one participant to request a chunk from another participant. If a client crashes or disconnects, it can check which chunks it has already downloaded (the base data includes a cryptographic checksum for each chunk) and request only chunks that it does not already have. I think bittorrent includes a command to request part of a chunk, too, but if worst comes to worst only chunks that have not been fully downloaded need to be re-requested.

The HTTP protocol was designed to transfer mainly small files and to be simple to implement. Its most basic command is to download one file with a minimum of fuss. A simple server may only understand one command, to download a file in full. Hence, if the download is interrupted, there is no choice but to download the whole file again. There is a way for a client to request only part of a file (with the Range: header). Not all servers implement it (because it is not a fundamental feature of HTTP). Web browsers typically don't bother with it (because they are primarily designed to download small files: web pages), but all download managers support it (because they are designed to load large files) and will use it if the server accepts.


How many edges must a graph with N vertices have in order to guarantee that it is connected? Possible Duplicate:
  Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected

At lesson my teacher said that a graph with $n$ vertices to be certainly connected should have
$ {\frac{n(n-1)}{2}+1 \space }$ edges showing that (the follow is taken from the web but says the same thing):

  The non-connected graph on n vertices with the most edges is a complete graph on
  $n-1$ vertices and one isolated vertex. So you must have $ 1+
{\frac{n(n-1)}{2} \space}$ edges to guarantee connectedness.

My idea: a complete graph $K_{n-1}$ with $n-1$ vertices has ${n-1 \choose 2}$edges,  so ${\frac{(n-1)*(n-2)}{2}}$ edges, added to the edge to connect the complete graph to the isolate vertex,

so shouldn't be ${\frac{(n-1)*(n-2)}{2}}+1$ edges?

What am I doing wrong?

Thanks.

The formula is worthless without a proof.

Suppose we have a graph on $n$ vertices which is not connected. Then it is possible to divide into two disjoint subgraphs, say one with $i$ vertices and another with $n - i$ vertices. The component with $i$ vertices has at most $i (i - 1)/2$ edges, while the component with $n - i$ vertices has at most $(n - i) (n - i - 1)/2$ edges (this happens when the two components are complete graphs). Therefore we have at most
$$i (i - 1)/2 + (n - i) (n - i - 1)/2 = i (i - n) + n (n - 1) / 2$$
edges. The number of edges has a fixed part $n (n - 1) / 2$ and a variable part $i (i - n)$ which depends on $i$. We would like an upper bound for the variable part. By using the method of completing the square we can write it as
$$i (i - n) = (i - n/2)^2 - n^2/4.$$
As a function of $i$ this is a parabola whose minimum is at $i = n/2$. Thus, to get the largest possible value in the allowed range $0 < i < n$ we should plug in the value of $i$ which is furthest away from the minimum. This happens when $i = 1$ or $i = n - 1$, and both give us the same estimate:
$$i (i - n) = (i - n/2)^2 - n^2/4 \leq (1 - n/2)^2 - n^2/4 = 1 - n.$$
We may thus estimate the number of edges as
$$i (i - n) + n (n - 1)/2 \leq (1 - n) + n (n - 1)/2 = (n-1)(n-2)/2$$
We conclude that the number of edges in a disconnected graph with $n$ vertices is at most $(n - 1)(n - 2)/2$. This is a tight upper bound which is achieved when one of the subgraphs is a point and the other a complete graph on $n-1$ vertices.


Is a secondary TM sufficient to detect all loops? Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever reaches the same configuration as the first, a loop was detected (obviously).

Claim: All infinite local loops in a TM can be detected in the above manner.

Local loop, in this context, refers to a machine running within a certain tape interval without ever stopping. To clarify, in particular this excludes any machines which extend the tape in any direction without bounds.

Has this been proven? I'm pretty sure I found this claim in a paper, I believe one of Marxen's, though I can't seem to find it.

This is Floyd's cycle finding algorithm, which is an efficient procedure for finding cycles. If you don't care about efficiency, you can use a big table which stores the different states the Turing machine has reached. If it reaches the same state twice, then it's in an infinite loop. What you are describing is just a more efficient way of detecting the same event, which is a particular type of infinite loop.

Turing machines can fail to halt – enter an infinite loop – in other ways. For example, a machine can keep going to the right indefinitely. The machine never halts, yet it doesn't reach the same state twice. A cycle finding algorithm won't detect this situation. Of course, there is no general way of detecting infinite loops, since the halting problem is undecidable.


Big O Algorithm Analysis I'm confused about the complexity of the following code:

for(i=1; i<=n; i = 2*i)
     for(j=1; j<=i; j++)
        print A[j]

I know that the first loop is logn, but I'm confused on what the second for loop would be since j is bound to i. Is this simply O(logn)?

I've plotted out the output as follows and thought it would be O(nlogn):

Assuming n = 8 or higher

i=1  j=1
i=2  j=1,2
i=4  j-1,2,3,4
i=8  j=1,2,3,4,5,6,7,8

The number of iterations for the outer loop is $\lfloor \log n \rfloor$. The number of iterations for the inner loop is $i = 2^k$, where $k$ is the number of current iteration of the outer loop.
So the number of computational steps is proportional to
$$\sum_{k = 0}^{\lfloor \log n \rfloor}{2^k} = 2^{\lfloor \log n \rfloor + 1} - 1.$$
Using the following inequality
$$n - 1 < 2^{\lfloor \log n \rfloor + 1} - 1 < 2n,$$
one can get that the time complexity of the algorithm is $\Theta(n)$.