Message receipt verification in a cluster At my current project I had a network problem come up for which I could not find a solution. In a peer-to-peer network I needed to send an action to all peers, and each peer was to act on it only if it could verify that all other peers would also act on it.

That is, given a network of peers $P = { P_1, ..., P_n }$. We wish to send, from some source peer $P_s$ a message to all other peers. This message contains an action which must be performed. The peer should perform this action if and only if every other peer will perform the action. That is, it performs the action if it can verify that all other peers will also have receipt of the action and can perform the same verification.

The problem is subject to these conditions:

There is no implicit message delivery guarantee: if $P_x$ sends a message to $P_y$ there is no way for $P_x$ to know if $P_y$ gets the message. (Of course $P_y$ can send a receipt, but that receipt is subject to the same constraint)
Additional messages with any payload may be created.
There is no total ordering on the messages received by peers. Messages can arrive in a different time-order than which they were sent. This time-order may be unique per peer. Two messages sent in order from $P_x$ to $P_y$ are very unlikely to arrive out of order.
Messages can arrive at any point in the future (so not only are they not ordered, they can be indefintely delayed). A message cannot inherently be detected as lost. Most messages will be delivered quickly, or truly lost.
Each peer has a synchronized clock. It is accurate enough in the domain of scheduling an action and to approximately measure transmission delays. It is however not accurate enough to establish a total ordering on messages using timestamps.

I was not able to find a solution. I'm interested in a guarantee and not simply a high probability of being correct (which can be done simply be repeatedly sending confirmations from peer to peer and rejections upon any likely loss.) My stumbling block is the inability to verify that any particular message actually arrived. So even if $P_x$ determines there is an erorr, there is no guaranteed way to tell the other peers about it.

A negative confirmation is also acceptable. I have a suspicion that a guarantee cannot actually be achieved, only an arbitrarily high probability.

Your suspicion is correct: under these conditions, there is no way to guarantee a solution. Yours is a consensus problem, and there is a general result that states the impossibility of consensus in an asynchronous network with failures. This result is sometimes known as FLP after its authors (Fischer, Lynch and Paterson) [FLP].

The original consensus states roughly this (see [FLP] or [L96] or [T00]): suppose you have $N$ processes with $N \ge 3$. The processes can communicate by sending asynchronous messages: there is no notion of real time, messages can take arbitrarily long in transit. Furthermore, a process may fail (it stops emitting messages). Define a configuration as an assignment of boolean values (0 or 1) to each process, and consensus as a configuration in which all non-failed processes have the same value. Each process may change its assigned value based deterministically on the messages it has received; the collection of algorithms executing on each process defines a distributed algorithm. The FLP result states that there is no algorithm that can reach a consensus from an arbitrary initial configuration, such that there is always at least one process that keeps its initial value. (In other words, the only solutions are the trivial one where all processes pick the same value.)

In your case, the failures are in transmissions rather than in processes, but this only makes the situation more difficult: you can simulate a process failure by losing all the messages to and from that process.

The FLP result implies that there is no distributed algorithm that will always (given sufficiently many received messages) lead to either all processes deciding on taking the action, or no process taking the action, unless they are all primed to act or all primed not to act.

Having clocks does not help: they are part of the local algorithm. They would help if you could put a bound on the message travel times: timeouts in transmissions are the usual way of solving consensus in practice.

Bibliography

[FLP] Michael J. Fischer and Nancy A. Lynch and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process". April 1985. Journal of the ACM 32 (2). DOI:10.1145/3149.214121

[L96] Nancy Lynch. Distributed Algorithms. Elsevier, 1996. 1-55860-348-4. http://groups.csail.mit.edu/tds/distalgs.html

[T00] Gerard Tel. Introduction to Distributed Algorithms. 2nd ed. Cambridge University Press, 2000. 0521794838.


Is $\frac{n}{3}$-CLIQUE NP-complete? Consider the problem
$\frac{n}{3}$-CLIQUE:
determining whether a graph contains a clique with at least $n/3$ vertices.

I want to prove it is NP-complete using a polynomial transformation from CLIQUE.

How can I approach this problem?

Let me explain how to solve this, leaving all details to you.

Given an instance $(G,k)$ of CLIQUE, we want to construct an equivalent instance of $\frac{n}{3}$-CLIQUE, say $G'$. Let us denote by $|G|$ the number of vertices in $G$. There are several cases to consider:

Case 1: $k = |G|/3$. In this case you can take $G' = G$.
Case 2: $k > |G|/3$. In this case you want to increase the number of vertices to $3k$ without changing the size of the maximum clique.
Case 3: $k < |G|/3$. This is the most complicated case. You want to increase the number of vertices to some $n'$ while increasing the size of the maximum clique by some $\Delta$. You are done if you can ensure that $k+\Delta = n'/3$. (In fact, it suffices to have $k+\Delta > n'/3$, since then we can use Case 2.)

You take it from here.


Algorithm for converting (coordinates + reach radius) data to directed graph I am trying to find a solution better than O(n2) for the following problem:

There are N points on a 2-D plane (N $\le$ 106), with integer coordinates between -105 and 105. Each point has an associated integer "reach radius" Ri (0 < Ri < 105).

Build a directed graph (represented by adjacency lists) in which these points are the vertices and there is an edge from A to B if and only if point B falls in the reach of point A (i.e. euclidean_distance(A,B) $\le$ RA).

I am thinking of dividing the plane into 4 equal regions, and solving the same problem for the regions, but don't know how to combine the partial solutions...

Thanks in advance for any ideas!

If all pairs of points are within each other's reach, you can not optimize the construction below $O(N^2)$. However, you can optimize for sparser graphs by ordering pairs of points by distance from smallest distance to largest. Once you find a pair $(A, B)$ where $d(A, B) > R_{max}$, you are done. A technique you can use for this can be found here. This technique makes use of divide and conquer.

This is more a heuristic. I do not think there is a way (with or without use of divide and conquer) to reduce the worst case complexity.


Interval Scheduling Confusion I am reading some notes about interval scheduling. I gives the following diagram:

and states that:

r2 is compatible with r3, while r2 and r1 are conflicting. Similarly, the set {r1, r3, r4} is compatible, while {r2, r3, r4} is not compatible.

I can understand that set (r1, r3, r4) is compatible. How (r2, r3, r4) are not compatible. Since they are not overlapping, isn't they are compatible?

That looks like an error in your notes.  {r2,r3,r4} are compatible.


Why is c) a combinational circuit, but d) not? I am doing practice after just learning what combinational circuits are, yet I am unsure of why (c) is combinational, but (d) is not.  Can someone please explain to me why this is? The Solution mentions that for (d) node n6 connects to the output terminals of both I3 and I4, but how is this different from the circuit in (c)?

A combinatorial circuit corresponds to a "straight-line program" that computes the outputs of the circuit given its inputs. (It has to satisfy some constraints that will exclude circuit (f) among others.)
As an example, if we denote the inputs of circuit (c) by $x_1,x_2,x_3,x_4$ (top to bottom) and the output by $o$, then using $g_1,g_2$ for the intermediate gates, the circuit corresponds to the program

$g_1 = x_1 \land x_2$
$g_2 = x_3 \land x_4$
$o = g_1 \lor g_2$

It also corresponds to the formula $(x_1 \land x_2) \lor (x_3 \land x_4)$. However, not every circuit corresponds to a formula. (The difference is that in some circuits, the output of a gate can appear as an input to more than one gate.)
Circuit (d) cannot be written in this form, since the outputs of I3 and I4 are wired together. What is the relation between the input to the rightmost gate and the outputs of I3 and I4? Not something that can be described combinatorially.
The difference between circuit (c) and circuit (d) is that in circuit (c) wires are not joined together. Rather, the output of each of the AND gates is connected to its own input of the OR gate. In contrast, in circuit (d) the rightmost NOT gate has only one input, but two incoming wires that must share the same input pin.


How do hand-written lexers work? Im studying a book called "Engineering a compiler" by Linda Torczon and Margaret Cooper. In the second chapter which discusses lexical analysis they mention three aproaches to writing a lexical analyser: 1. Table-driven, 2. Direct coded and 3. Hand coded.

My question is: how do hand coded lexers generally work ? Are they similar to either table-driven or direct-coded ones ? Where can i find simple examples of hand coded lexers ?

How do hand coded lexers generally work?

That depends on whose hand coded them :-). But:

Are they similar to either table-driven or direct-coded ones?

Table-driven hand-coded lexers are rare in my experience (if you were going to use a table anyway, why not use a tool to generate the table). Torczon & Cooper use "direct-coded scanner" to mean a scanner which effectively embodies the state machine (DFA) in code, so that the program counter is the state.
Most hand-coded lexers implement a state machine of some kind, although they are often not very rigid in their model. For example, a common approach is to use a switch on the first character of the token, and then, depending on the token type, use some standard library function to parse the rest of the token. While some hand-coded parsers implement a direct-coded trie for keywords, others just recognize identifiers and then check the token in a hashtable. And a large variety of other variations on the theme.
[Note 1]

Where can I find simple examples of hand coded lexers?

Check out the Bison manual, which has a number of simple examples which do not depend on lex.

Notes:

Some machine-generated lexers -- see Ragel or re2c, for example -- are direct-coded state machines. This was once believed to improve scanner speed, a theory also endorsed by the textbook. However, I'm not convinced that it is still the case with modern pipelined processors. In any event, it is very rare for scanner speed to be a noticeable part of compilation time.


"Which complexity represents a majority of algorithms?" Student asked me this question. During lectures on algorithm complexity I've shown similar picture (source):

After I've explained and gave examples for each category, a student asked: "Which of these represent a majority of algorithms?" I guess that the question is not right in a sense that we are creating new algorithms and that it depends on the field - majority of sorting algorithms are more complex than nlogn.

What would be your answer?

This question is only about the Big O as that was the end of the lecture.

Thanks!

My answer would be that there is no running time that represents the majority of algorithms. Some common algorithms (for example, BFS and DFS) run in linear time; some run in loglinear time (for example, sorting); dynamic programming algorithms run in superlinear polynomial time (for example, the standard algorithm for edit distance runs in quadratic time); algorithms involving matrix multiplication run (practically) in cubic time, and theoretically faster; SAT solvers have worst case exponential running time; and some algorithms involved in verification have even faster growing worst case running time, or are not guaranteed to terminate at all.


Is the following CFG ambiguous? I was given the following CFG :

$S \rightarrow A\ |\ B$

$A\rightarrow aAa\ |\ abAb\ |\ bAc\ |\ aca\ |\ abcb\ |\ bcc$

$B \rightarrow bBa\ |\ aBb\ |\ babBc\ |\ bca\ |\ acb\ |\ babcc$

And I have to show if it is ambiguous by giving two leftmost derivations for the same word.

I am pretty sure that there are two leftmost derivations but I can not find them.

I do not need the solution, just a tip where to start with would be enough.

Is unambiguous because there is no string of rule A which is a string or substring of B. And viceversa.


How to compare SURF points in two images I know how to find SURF feature points and have code to find them, but I have no idea how to find the same point in 2 different images, I have
laplacian, scale, orientation, descriptor, response and x, y. If i give it a very simple image, a triangle with no bottom and place it in two different places in two different images none of the info about the points are the same, Any help appreciated on how to compare points.

You compare the descriptors. The simplest approach is for every descriptor in image 1, you find its nearest neighbor in image 2. There are various strategies for discarding ambiguous matches, ensuring uniqueness of matches, using kd-trees for speed, etc. See the documentation for the matchFeatures function in MATLAB.


If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$ I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right direction. Thank you for your help.

My idea for demonstrating regularity of the square root language was to try to consider two machines running in tandem. One of them accepts the original language $L$ and the other runs the same machine backwards (I expect that this will be an NFA). I then wanted to accept words that met in the middle (i.e ${(q,q):q∈Q}$  where $Q$  are the states of the DFA accepting $L$ ). However, I do not think this will work.

Here is how to implement your solution. Let $A = \langle Q, q_0, F, \delta \rangle$ be a DFA for $L$. We will construct an NFA $A' = \langle Q', q'_0, F', \delta' \rangle$ as follows:

$Q' = \{q'_0\} \cup Q^3$. The state $(q_1,q_2,q_3)$ means that we have guessed that when $A$ finishes reading the first copy of $w$, it will be in state $q_1$; the first copy of $A$, started at $q_0$, is at state $q_2$; and the second copy of $A$, started at $q_1$, is at state $q_3$.
$F' = \{(q_1,q_1,q_2) : q_1 \in Q, q_2 \in F\}$. Thus we accept if the first copy of $A$ is in the guessed state, and the second copy of $A$ is at an accepting state.
$\delta'(q'_0,\epsilon) = \{(q,q_0,q) : q \in Q\}$. This initializes the simulation of the two copies of $A$.
$\delta'((q_1,q_2,q_3),a) = \{(q_1,\delta(q_2,a),\delta(q_3,a))\}$. This simulates both copies of $A$, while keeping the guessed state.

We leave the reader the formal proof that $L(A') = \sqrt{L(A)}$.

Here is another solution, which creates a DFA. We now run $|Q|$ copies of $A$ in parallel, starting at each state of $A$:

$Q' = Q^Q$.
$q'_0 = q \mapsto q$, the identity function.
$\delta'(f,a) = q \mapsto \delta(q,a)$.
$F' = \{ f \in Q' : f(f(q_0)) \in F \}$.

What is the meaning of the condition $f(f(q_0)) \in F$? After reading a word $w$, the automaton $A'$ is in a state $f$ given by $f(q) = \delta(q,w)$. Thus $f(f(q_0)) = \delta(\delta(q_0,w),w) = \delta(q_0,w^2)$.


B-Tree and how it is used in practice I understand what a B-Tree is (I already implemented a B-Tree in Java with insert and delete methods that preserve the invariant).

However I do not understand exactly how it is used for example for file systems or databases.

How do you choose the keys in these 2 scenarios? And what is the data?
Are data and keys the same?
I can't think of a good key that is able to order the data in a way that it is easily accessible. If I want to find an entry containing some string.
how useful would be a key that gives information about the size of each entry? or the alphabetical order? I don't exactly understand the concept.

I have to add that I don't understand much of file systems or databases which is probably why I'm confused.

A B-Tree is a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set for the sort of operations we're talking about), but is most commonly used to implement a map (ditto for java.util.Map). So let's just look at maps for a moment.

If you think about a linguistic dictionary, it's ordered by "word", and associated with each word is a definition. You look up a word, and get a definition.

So the context of a map data structure is that you have keys ("words") and you want to map this to values ("definitions").

B-trees are like other kinds of search tree (e.g. binary search trees) in that keys can be accessed in sorted order. This has an advantage for certain types of query. For example you can do range queries, say if you want to find all entries where the key is between two values (e.g. all words in the dictionary starting with "q").

The main advantage of B-trees over other kinds of search tree is that it is particularly efficient when represented on disk. B-trees are page-structured (meaning they can be implemented on top of fixed-size disk pages; this also avoids fragmentation), and have a wide ply, which minimises the number of disk accesses needed to perform a query.

A typical use in a database server is to implement indexes. An index is, once again, much like the index in a paper book. Some books have multiple indexes (e.g. there might be a general index and an index of names of people). Given a key, the index in a book returns a set of pages on where you can find references to whatever is indexed (be it a concept, name, or whatever).

A database index typically maps a key to a set of database records. In a typical organisation, there is one data structure in which records are stored, and multiple indexes which map keys to record identifiers. To find records, you query the index, which gives you a collection of record identifiers. Then you can use those record identifiers to find the records in the store.

A typical use in a modern filesystem is to implement directories ("folders" if you're more used to GUIs). A directory is, logically, a map from names (file names or directory names) to filesystem objects. A filesystem object may be a file, or another directory, or what have you.

As has been pointed out elsewhere, you might want to do some reading on this. Any "introduction to databases" textbook will probably do.


Complexity of finding a spanning tree that minimizes the maximum interference Given $n$ nodes in the plane, connect the nodes by a spanning tree.
For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning tree. The interference of a node $v$ is then deﬁned as the number of such disks that include the node $v$.

The problem I'm interested is to find a spanning tree that minimizes the maximum interference.

What is known about the problem in terms of computational complexity? Is it NP-hard? Can it be solved efficiently? What is its inapproximability threshold?

Apparently this problem is still not understood well. I do not know the complexity of the problem (solvable optimally in polynomial time, or NP-complete), and as far as I know it is unknown whether efficient approximation algorithms exist.

This problem already is known, and is NP-Hard, but if you like to know more about the interference related problems I'd offer you to read this book.

The Problem 1, in the Buchin work is as follow:

  Problem 1 (Locher, von Rickenbach, Wattenhofer[5]). Given n nodes in
  the plane. Connect the nodes by a spanning tree. For each node v we
  construct a disk centering at v with radius equal to the distance to
  v's furthest neighbor in the spanning tree. The interference of a node
  v is then defined as the number of disks that include node v (not
  counting the disk of v itself ). Find a spanning tree that minimizes
  the maximum interference.


Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$ I've been stuck on this problem for a while. Any hints would be appreciated!

Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A_w = \{x \in \Sigma^\star\:|\: \langle x, w \rangle \in A\}.$$
Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$.

Here is a hint. Let $w\in B$ if $w\not\in A_w$ and let $w\not\in B$ if $w\in A_w$.


Is there any reason why the modulo operator is denoted as %? I would like to know if there is any reason why many programming languages use the notation % for the modulo operator?
It is used in the most "famous" languages:

C
C++
C#
Go
Java
Julia
Lua
Perl
Python

The earliest known use of % for modulo was in B, which was the progenitor of C, which was the ancestor (or at least godparent) of most languages that do the same, hence the operator's ubiquity.
Why did Thompson and Richie pick %? It had to be a printable ASCII character that wouldn't conflict with B's other features. % was available, and it resembles the / division operator, making it the obvious choice.
p.s. the creator of ASCII invented \ to represent "reverse division", so it wasn't a candidate for modulo.


What are the most expressive, terminating languages? I'm less interested in languages where you can write almost anything, but then are required to write an accompanying proof that what you wrote terminates.

I'm more interested in the design space of languages inherently confined to certain complexity classes by construction.

Is there any sort of theory hierarchy for sub-turing-complete languages?

There are plenty of classes of programming languages where all programs terminate. The most common form of enforcing termination is by way of types. The most well-developed theory of typing systems for terminating computation might be that of Barendregt's Lambda cube, which decomposes typing into three orthogonal axes:

Parametric polymorphism
Higher kinds
Value-dependency of types

Starting from a terminating languages such as the simply typed $\lambda$-calculus, one can add any combination of those three axes and retain termination.

This has close connections with logic, via the Curry-Howard correspondence.

There are many extensions and refinements, including types that capture complexity classes.


Can a computational complexity class be redefined by using any complete (decision) problem? Let $\mathcal{C}$ be a basic complexity class (such as $\mathrm{NP}, \mathrm{PSPACE}$).
And $\mathcal{C}$ is closed under a reduction "$\leq$" (such as polynomial time many-one reduction "$\leq_{m}^{p}$", polynomial time Turing reduction "$\leq_{T}^{p}$").
Suppose that a decision problem $L \subseteq \Sigma^{*}$ is complete for $\mathcal{C}$ under reduction "$\leq$".
Let $[L]^{\leq}$ denote the closure of $L$ under reduction "$\leq$", which means that $[L]^{\leq}$ is a class consists all the languages that can be reduced to $L$.
$$[L]^{\leq} = \{ L' \in \Sigma^{*}| L' \leq L \}$$
Does $\mathcal{C} = [L]^{\leq}$ hold true?
Here is my proof.
Firstly, $L \in \mathcal{C}$, thus for every $L' \in [L]^{\leq}$, we have $L' \in \mathcal{C}$ which leads that $[L]^{\leq} \subseteq \mathcal{C}$.
In the other hand, since $L$ is complete, for every $L' \in \mathcal{C}$, $L' \leq L$. We conclude that $L' \in [L]^{\leq}$ which means that $\mathcal{C} \subseteq [L]^{\leq}$.
Now, I have proved that $\mathcal{C} = [L]^{\leq}$.
If this is correct, I can say that
$$[\text{SAT}]^{\leq_{m}^{p}} = [\text{3-SAT}]^{\leq_{m}^{p}} = \mathrm{NP}$$
Am I right?

If $X$ is any NP-complete decision problem, then NP consists of all decision problems which are polytime many-one reducible to $X$.
We cannot replace polytime many-one reductions with polytime Turing reductions, however (unless NP=coNP), since coSAT is polytime Turing reducible to SAT.


Name of Bomberman algorithm? Last couple of days I've been pulling my hair trying to find the name of a
bomberman-esque algorithm which finds solutions to the question of where to place a single bomb so as to blow all targets up, either directly if all targets are within the blast radius (and axis) of a single bomb (placed in an empty cell) or via a chain-reaction by exploding nearby bombs which share the same x- or y-axis within the blast radius (hence the graph exploration issue).

I can describe the situation as following: given a square cell matrix S (the board state) of order n, containing symbols which differentiate between different objects(empty cells, rocks, targets and bombs), identify all empty cells P where a bomb with blast radius R can be placed so that all targets T will be destroyed. The other initially untriggered bombs also share the same blast radius.

Edit: The objects function as follows:

Empty cell; The only place where a bomb could be placed. Allows explosions to pass through.
Rocks; Blocks explosion waves.
Bombs; Sits passively in a cell until reached by an explosion wave, at which point it explodes and sends an explosion wave outwards in the the x- and y- axis, up to the defined blast radius-length away.
Targets; If reached by an explosion will be destroyed and counts towards the end goal of finding a solution where all targets are destroyed. Allows explosions to pass through.

I started out with a brute-force variant which simply went through all empty cells and started a search from there, which is quite inefficient if all objects are in one corner of a huge board. I came to the following pre-processing insight:

  Since a solution is only regarded as valid if all targets have been
  destroyed, I can therefore begin my search from any random T and if
  the path generated from that initial T does not destroy all T
  then there is no solution to that particular S.

I've made an algorithm which manages to find some solutions, but not for all boardstates I'm testing with. (currently only works if no other target is within a blastradius-length from the starting target).

Is this description ringing any bells for you?

My first instinct was an MST, but I've been unable to merge that algorithm with my description above.

As an example, Yellow denotes a target, red cells indicate the radius of the target such that if a bomb was placed in any of the red cells, it would blow up a target.

We can see from the picture that if we listed all the co-ordinates that are red

Pseudocode // Note that this tries to add the centre, or the x,y of the target twice
for target in targets:
    for i in range(-radius, radius):
        set[target].add(target.x + i, target.y)
        set[target].add(target.x, target.y + i)

Then compare two sets for overlap, and if there is overlap between all of them, then we have an answer.

Pinky Purple is a bomb, and the blue is the radius that if another bomb explodes within, it will detonate too

Note that now we have to do a check before adding the co-ordinate to the set

If it is a blank cell it is easy, just add it.

If it is a bomb, dont add it, but add all the possible co-ordinates that will set off the bomb, and if during our checks, we encounter another bomb, we need to add that list too. I would make a recursive method here

def bombLinks(candidate.x, candidate.y, bombSet):
    for i in range(-radius): //0 to the -radius shouldn't be checked for bombs, since thats where we came from
        candidateType = blockAtCell(candidate.x + i, candidate.y)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x + i, candidate.y)
        candidateType = blockAtCell(candidate.x, candidate.y + i)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x, candidate.y + i)

    for j in range(radius):
        candidateType = blockAtCell(candidate.x + j, candidate.y)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x + j, candidate.y)
        else if(candidateType = "Bomb"):
            bombSet.add(bombLinks(candidate.x + j, candidate.y, bombSet))
        candidateType = blockAtCell(candidate.x, candidate.y + j)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x, candidate.y + j)
        else if(candidateType = "Bomb"):
            bombSet.add(bombLinks(candidate.x, candidate.y + j, bombSet))
    return bombSet

If it is anything else, we could ignore it, or if we want it so that explosions can't pass through certain blocks, we can do some more checks here

for target in targets:
    for i in range(-radius, radius):
        candidate.x, candidate.y = target.x + i, target.y
        candidateType = blockAtCell(candidate.x, candidate.y)
        if(candidateType == "Blank"):
            set[target].add(candidate.x, candidate.y)
        else if(candidateType == "Bomb):
            set[target].add(bombLinks(candidate.x, candidate.y, []))

        candidate.x, candidate.y = target.x, target.y + i
        candidateType = blockAtCell(candidate.x, candidate.y)
        if(candidateType == "Blank"):
            set[target].add(candidate.x, candidate.y)
        else if(candidateType == "Bomb):
            set[target].add(bombLinks(candidate.x, candidate.y, []))

Whew, thats a lot of code, and you may have a better way of traversing the list of possible bomb locations, just don't forget that you can end up in an infinite loop if you check for bombs both directions

After all that, check the overlap between the sets. If there is an answer, great, otherwise pick the location that came up the most

Please excuse my terrible pseudo code, especially the loops


Directed HAM Cycles with Additional Constraints to SAT The $n$ dimensional hypercube $Q_n$ is a graph that has a vertex $v_s$ for each string $s \in \{0, 1\}^n$ and an edge between two vertices $v_s$ and $v_t$ if and only if the Hamming distance between $s$ and $t$ is $1$.

I would like to find directed hamiltonian cycles in this graph that satisfy a certain property, and was thinking of feeding my problem to a SAT solver. The problem can be encoded as follows. We define a variable $x_{si}$ to denote that the vertex $v_s$ appears in the $i$-th position of the cycle. Then, for each $s \in \{0,1\}^n$, we define the contraints $\bigvee_{i} x_{si}$ (each vertex appears in one position of the cycle) and  $\neg x_{si} \vee \neg x_{sj}$ for all $i \neq j$ (each vertex appears at most once in the cycle). Finally, we also require the constraints  $\neg x_{si} \vee \neg x_{t(i+1)}$ for all pairs of strings $s$ and $t$ that have Hamming distance greater than $1$ (i.e pairs of vertices that do not have an edge cannot appear consecutively in the cycle ordering).

Now, I would like to add the following requirement on my cycle. For some specified integer parameter $k$, we must be able to partition the vertices of the graph into vertex disjoint copies of $Q_k$ such that the vertices in a specific copy of $Q_k$ are all assigned the same "direction". How can I capture this set of requirements easily in my reduction?

Encodings like this are notoriously slippery, so (of course) please carefully verify any outputs in case I've made a mistake somewhere.

Please assume that all unbound variables are universally quantified; i.e., I write $\bigvee_i\ p_{si}$ instead of $\forall s\ \bigvee_i\ p_{si}$.

Defining the partitions

First, define partition variables:

$p_{si} = \text{vertex $s$ is in partition $i$}$.

Basic partition constraints

Partitions are disjoint:

for $s \neq t$: $\lnot (p_{si} \land p_{ti})$.

Every string is part of one partition:

$\bigvee_i\ p_{si}$.

Coordinate matching within partitions

This is a little tricky.  First, we need to define which hypercube each partition corresponds to.  We specify this by defining which coordinates each partition matches on:

$m_{ij} = \text{partition $i$ requires coordinate $j$ to match}$.

Now we need to say that partition $i$ requires exactly $n-r$ coordinates to match (I'm going to use $r$ where OP uses $k$, because I need to use k as an index below):

$\sum_j m_{ij} = n - r$.

Computing the sum

Sums, of course, are not directly supported in the SAT model.  We can handle this by computing the sum with propositional logic:

$a_{ijk} = \text{for partition $i$, the sum over the first $j$ bits of $m$ is $k$}$.

The sum across the first $j$ bits for partition $i$ must be uniquely defined:

for $k_1 \neq k_2$, $\lnot (a_{ijk_1} \land a_{ijk_2})$.

We could require each sum to be defined at least once, but we don't need to; we take care of that for free when we define how addition works:

$a_{i1k} \iff m_{i1}$

$a_{ijk} \land m_{ij} \implies a_{i(j+1)(k+1)}$

$a_{ijk} \land \lnot m_{ij} \implies a_{i(j+1)k}$

Now we can set what the sum needs to be:

$a_{in(n-r)} = \texttt{true}$

(Again, I use $r$ where OP uses $k$ to avoid confusion with $k$ as an index.)

Constraining matches

Strings in the same partition match at the required coordinates:

$(m_{ij} \land p_{si} \land p_{ti}) \implies \text{strings $s$ and $t$ match at position $j$}$.

The RHS of that implication is just a set of constants that we can precompute as true or false.

Enforcing cycle direction within partitions

To encode direction, we can precompute constants for a neighbor relation between strings:

$d_{sti} = \text{$s$ and $t$ are identical, except at position $i$, where $s$ is 0 and $t$ is 1}$.

We'll also define a variable to encode which strings follow which strings:

$f_{st} = \text{$t$ immediately follows $s$ in the cycle}$.

$f_{st} \iff \bigvee_i x_{si} \land x_{t(i+1)}$.

Now we're ready to encode cycle direction:

$[\bigvee_i (p_{si} \land p_{ti})] \implies [\bigvee_{uvj}\ (f_{su} \land f_{tv} \land [(d_{suj} \land d_{tvj}) \lor (d_{usj} \land d_{vtj})]$.

If $s$ and $t$ are in the same partition, then there is one specific bit position $j$ where the strings $u$ and $v$ that follow $s$ and $t$ in the cycle differ (and specifically differ in the same direction: 0 to 1 or 1 to 0).

I don't know that much about SAT solvers, but it may be that the last line produces an unwieldy number of terms.  It may be possible to define further 'intermediate' variables like $f_{st}$ that break things up more and reduce the combinatorial explosion.


What's wrong with this Here's the question: Do more baby names start with "A" or "B"? Write code to count and print those two counts ("A" count, then "B" count).

I then write this code down:

table = new SimpleTable("baby-2010.csv");

count1 = 0;

count2 = 0;

for (row: table) {

// your code here

if (row.getField("name").startsWith("A")) {

count1 = count1 + 1; }

if (row.getField("name").startsWith("B")) {

count2 = count2 + 2; }

}
print("A count:",count1)
print("B count:",count2)

I ran the code which then came out like this: A count: 258
B count: 198

Any ideas as to why this might be wrong?

First off, I don't think this is the appropriate place for this question.

Second; why are you incrementing count2 by 2 each time you find a "name" field that begins with a B? Surely this should be incremented by 1, like count 1 is.

Out of interest, do you know what the correct results should be?

Could you post them?


Given a set of points, find the one closest to a given point So, I'm given an arbitrary set of points $(p_1, p_2, p_3,\ldots)$ with an $x$ and $y$ coordinate. I have no information about the order they're given to me.

I need to write code that will take in a point, $p_0$, and will find the point $(p_1, p_2, p_3\ldots)$ closet to $p_0$. This will of course be found my minimizing $R$ in $R^2 = (x - x_0)^2 + (y - y_0)^2$.

I could implement this easily if I linearly search the list of points each time (always $O(n)$ complexity). However, I would prefer something that could be an average of $\log(n)$ complexity. Does anyone have a suggestion on a search algorithm?

If we make no assumptions on input and want an exact answer to the question what the minimum distance is to $p_0$, any algorithm must take at least $\Omega(n)$ time in the worst case. To see this, suppose $p_0$ is in your input points. In the worst case, the final point we see in our list is this point! So we must inspect all our input points and hence take $\Omega(n)$ time.

For the same reason, an approximation algorithm must also use $\Omega(n)$ time, as the difference in distance to $p_0$ between the inspected points in the list and the points we haven't inspected yet may be arbitrarily large.

The only way I see to be faster than linear is to take a random sample from your list to get the right answer with a certain probability. However, I think the running time would heavily depend on the probability you would want in the list.


In what situations should a particular sorting algorithm, such as heap sort, be chosen over others? In my algorithm class my teacher said that we should always use counting sort when we want to sort integers. After he said this I was curious to know in which situations I should choose one sort algorithm over another.

Looking at the complexities of the worst cases of the algorithms I know (heapsort, mergesort, quicksort and countingsort), excentuating the case where I want to sort integers, I will choose mergesort when I want a stable sorting algorithm or I will choose heapsort when I want to save memory.

Searching a little I found flashsort, but I still do not understand very well when I should implement it instead of others. Since I am beginning to study algorithms, I would like to know at this initial moment when a sort algorithm is preferable over others.

Most programming language standard libraries come equipped with one or more built-in sort routines these days. Most of the time, that's what you want.

"Library sort" algorithms tend to use a combination of basic sort algorithms that you've seen in class, and tune themselves either at compile time or at run time.

That's why, for example, the standard library sort in C++ might use merge sort on linked lists and quick sort on arrays. And a typical industrial-strength quick sort implementation will revert to insertion sort on small intervals, or heap sort if the partitioning strategy seems to be going awry.

Most library sorts are comparison-based because of external constraints. They must work on user-defined data types, for example, and it's typically much easier for the user of such a sort algorithm to supply a comparison operation than, say, a radix extraction operation. Moreover, users often want to sort on secondary keys if primary keys are equal (e.g. surname then first name). It's much easier to express this in terms of comparison rather than some other formulation.

I've been in the business a long time, and there's really only a few times I can think of where writing my own sort was the best option. Two examples that are easy to explain:

First example: I wrote the sort subsystem for a database server. It me about six months. As with library sorts, it used a combination of sort algorithms and adjusted its behaviour depending on what situation it found itself in. Sorting database records is an interesting case because accessing the sort key is sometimes the most expensive operation; disk seeks are one of the most expensive things there is, especially if the disk is network-attached.

The main idea which cracked this problem was to use the fact that users almost always wanted to sort on multiple keys. So I used partitioning sort algorithms which discovered "ranges" where the primary sort key was the same. Secondary keys are only needed to resolve those ranges. Many sort algorithms (e.g. ternary quick sort, radix sort) can be adapted to return ranges.

Second example: I wrote some firmware which needed to read about 1000 values from a hardware device, and then do quantile extraction. The complication is that the microcontroller that this ran on had essentially no extra read-write memory available, so algorithms like radix sort or quick sort were not an option. I used Shell sort, which was by far the best tradeoff.

There's a bunch of special-case information that everyone who has worked with sorting knows, such as "bubble sort is always worse than insertion sort", and "heap sort has terrible constant factors; last resort only". But this general advice is probably all you need to know:

The best sort algorithm is the one that fits the peculiarities of your data and your platform.
The second-best sort algorithm is one you didn't have to write.
Make sure that sort is a bottleneck before getting fancy.

Knowing lots of sort algorithms is good for you, but not necessarily to the point where you can implement them from memory. Knowing that there is a tradeoff is more valuable knowledge than what the tradeoffs actually are. Then, when you come across one of those few times where you need to write your own sort, you'll know where to look.


A version of the longest simple cycle problem - NP-completeness reduction proof I've been learning about proving NP-completeness via reduction, and came across the following problem:

Prove via reduction the following: whether a graph $G = (V, E)$ contains a simple cycle using $\ge \frac{1}{2}$ of the vertices is a NP-Complete problem.

The first part is to show that the above problem is in NP. That's simple enough, since a solution is verifiable in linear time by just traversing through the vertices to ensure they form a cycle, and that the no. of vertices in the solution set are $\ge \frac{1}{2}$ of the total no. of vertices.

As far as polynomial-time reduction...my thoughts so far are that you can probably reduce Hamiltonian circuit problem to it, but I'm unsure how to proceed. I suppose that, given the original graph $G$, you could first check whether the entire graph is a Hamiltonian circuit. Then if not, you could delete a random vertex from $G$ (there are a total of $|V|$ ways of doing this), and check for Hamiltonian circuit again...then if not, delete two vertices from G (there are $\binom{|V|}{ 2}$ ways of doing this), and check again for Hamiltonian circuit...and so on, all the way down to deleting $\frac{|V|}{2}$ vertices from $G$.  But reducing it this way sounds cumbersome, and may even be an exponential-time reduction.

Any help would be appreciated.

In order to prove NP-completeness of a given problem $\Pi$, it is enough to prove that $\Pi \in$ NP and that there exists a polynomial time reduction from any NP-complete problem $\Pi^*$ to $\Pi$.  The reduction must take instances of $\Pi^*$ and return instances of $\Pi$, in polynomial time, such that the answer is the same in both $\Pi^*$ and $\Pi$.

A suitable reduction from Hamiltonian Circuit has been proposed in a comment to the question: just add enough (that is $n$) isolated vertices to the graph.


Showing asymptotic lower bound on log of recurrence I'm trying to prove a lower bound on some computational problem, but in order to do it, I need an $\Omega(n\log(n))$ lower bound on $\log(T(n))$, where $T(n)$ is a recurrence defined as follows:
$T(1) = 1$
$T(n) = \sum_{k=1}^{n-1} T(k)T(n-k)$
Does this recurrence have a known solution? If not, just giving a lower bound on $\log(T(n))$ would suffice for me. Optimally, I would want an $n\log(n)$ bound, but I don't know if its possible to achieve. So, any lower bound bigger than a linear one would be appreciated! Thanks in advance for helping me out!

Your sequence $T(n)$ is, in fact, the Catalan numbers, as show on the On-Line Encyclopedia of Integer Sequences. You can also take a look at the Wikipedia article on Catalan numbers, which shows its many applications in combinatorics.
$$T(n)=C(n-1)=\frac{(2(n-1))!}{n!(n-1)!}\sim \frac{4^{n-1}}{n^{3/2}\sqrt{\pi}}.$$
In particular,
$$\log T(n) = (n-1)\log 4 - \frac32\log n - \frac12\log\pi + o(1),$$
or,$$\log T(n) \sim n\log 4.$$


Branchless function equivalent Does every pure function have a branchless equivalent?

By pure function I understand a function that uses only its input values and no global state to produce the output.

By branchless function I understand a function that does not use if/else during its execution. A loop contains a branch with and unconditional jump. Constant loops can be unrolled.

As an example, here is the signum function:

function signum(x):
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;

And here is a branchless version of the same function:

function signum(x):
  return (x > 0) - (x < 0);

The general answer to your question is no. Consider a function which measures the length of a linked list. How would you implement that without a branch?

But if you just stick with functions which (say) take a machine word and return a machine word (which your example does) then the answer is "yes, sort of". In fact, when analysing algorithms in the word-RAM model, we conventionally assume that any function which takes a fixed number of machine words and returns a fixed number of machine words is constant-time, because it could (in principle, at least) be implemented with a lookup table or a new CPU instruction.

Whether the branch-free version is more practical or not depends partly on the function and partly on the CPU's instruction set.

Don't forget, by the way, that pretty much all modern CPUs have a conditional move instruction. Some ISAs (e.g. ARM) can do conditional execution of all, or almost all, instructions. So there's even more ways to implement branch-free code there.


Covering a graph with non-overlapping cliques I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows:

Every subgraph must be a complete graph/clique
No vertex can be part of two or more subgraphs
Subgraphs that can be merged with other subgraphs while remaining complete cannot exist
When multiple possible complete subgraphs/cliques are present, chose the one with highest within-clique edge weight

Below is an obvious example. Multiple maximal cliques exists, but it is very clear to the beholder which two should constitute the subgraphs.

Community detection are not a good fit (at least the algorithms I've looked into) because they don't enforce completeness within the communities. Furthermore the graphs that I'm working with are quite small and dense, and community detection algorithms will often just find one large community.

My main approach now is thus to find all maximal cliques, and then somehow remove unwanted cliques based on edge weights but I'm at a loss as to what the best approach for the latter part is...

Edit: This is my current implementation

Detect maximal cliques in the graph.
Sort the cliques in descending order based on their minimum edge weight within the clique.
Iterate over the sorted cliques, adding cliques to my result list if, and only if, its member vertices are not present in any already selected clique.
After iteration see if any vertices in the original graph are present in any of the selected cliques.

If all vertices are present, exit.
If not create a subgraph of the original graph containing the missing vertices and repeat 1-4.

This is sort of similar to @kurtosis answer but handles edge weights as well as the case where vertices are left out of the initial iteration.

Edit 2: To clarify what I'm asking (because it might be less obvious after the first edit). My problem remains as described in the first part. After posing the question I've developed a solution as described in the first edit, that seems to get the job done, but it is, in my view, not very elegant. It might be the only way to solve the given problem, but I wouldn't know as graph theory is not my main area. Thus I'm still curious if there are other more efficient approaches to solving the problem.

Thus I'm still curious if there are other more efficient approaches to solving the problem.

If you take the complement graph $\overline{G}$, then your problem corresponds to a coloring problem.  Cover by cliques in $G$ is the same as covering by independent set in $\overline{G}$.

The problem is para-NP-hard in the unweighted case and the problem is just hard no matter what you do.

There is an algorithm computing the chromatic number in time $O^*(2^n)$ using exponential space, and in time $O(2.2461^n)$ using polynomial space.

The fastest algorithm I know to get the coloring runs in time $O^*((1+\sqrt[3] 3)^n) = O(2.4423^n)$.

[1] Fomin, F. V., & Kratsch, D. (2010). Exact exponential algorithms. An EATCS Series — Texts in Theoretical Computer Science.  Springer.


Acyclic Tournament Digraphs and Hamiltonian Paths I am studying MIT OCW lecture notes but they do not have solutions for the following problem.

Directed Acyclic Tournaments

In a round-robin tournament, every two distinct players play against each other
just once. For a round-robin tournament with no tied games, a record of who beat
whom can be described with a tournament digraph, where the vertices correspond
to players and there is an edge $x \rightarrow y$ iff $x$ beat $y$ in their game.

A ranking is a path that includes all the players. So in a ranking, each player won
the game against the next lowest ranked player, but may very well have lost their
games against much lower ranked players —whoever does the ranking may have a
lot of room to play favorites.

Give an example of a tournament digraph with more than one ranking.
Prove that if a tournament digraph is a DAG, then it has at most one ranking.
Prove that every finite tournament digraph has a ranking.
Prove that the greater-than relation, $>$, on the rational numbers,
$Q$, is a DAG and a tournament graph that has no ranking.

I got stuck at  questions 2, 3, and 4. I have no idea how to solve it. I tried induction on b without a luck but still induction does not even help for infinite DAG cases.

I am completing Nicholas's answer because I think there are problems with his answers to 3 and 4 and explaining why is a bit too long for comments.

For 3. you need to show there is a simple path in the tournament that visits every vertex (this is called a hamiltonian path). You can do this simply by induction. Clearly this is true for a tournament on 2 vertices. Now assume you have a tournament $T = (V, A)$ on $n$ vertices.  Remove some arbitrary $v$ from $V$ and find a hamiltonian path $v_1, \ldots, v_{n-1}$ in the induced tournament on $V \setminus \{v\}$. If for all $i \leq n-1$, $(v_i, v) \in A$, then $(v_{n-1}, v) \in A$ and you can append $v$ to the existing path. Otherwise, there exists some edge from $v$ to the $\{v_1, \ldots, v_{n-1}\}$; let $i$ be the smallest integer such that $(v, v_i) \in A$. Either $i = 1$ and you can pre-pend $v$ to the existing path, or, since $i$ was the smallest $i$ such that $(v, v_i) \in A$, you know that $(v_{i-1}, v) \in A$, and, therefore, you can take the path $v_1, \ldots, v_{i-1}, v, v_i, v_{i+1}, \ldots, v_{n-1}$.

For 4., I also don't think it's enough to say that the rationals have no infimum or supremum. That's true of the integers too, but there exists a path through the integers which is infinite in both directions. I think the crucial property of the rationals that causes problems is that they are dense: there is a rational between every two rationals. In particular, assume for contradiction there exists a path that visits all rationals in the graph defined in the question. Take any edge $(x, y)$ in the path: $x < \frac{x+y}{2} <y$, so $\frac{x+y}{2}$ cannot precede $x$ in the path and it cannot succeed $y$, so it cannot be in the path - a contradiction.


How to calculate the average depth of a binary tree? My professor has said that the average depth of all possible binary trees which can be formed with $n$ nodes would be $O(\sqrt n)$ and has assigned the proof of this as homework. How do I approach this problem?

You haven't stated which distribution of random binary trees you are interested in, but in many cases the answer is indeed $\Theta(\sqrt{n})$. See for example Flajolet and Odlyzko, The average height of binary trees and other simple trees.


Covering the unit square by smaller squares of variable sizes I'm trying to find whether a property $\mathcal{P}$ is true for all points of the unit square (in 2D). At each step I can query for a point of my choice. An oracle then answers me by either:

telling me $\mathcal{P}$ doesn't hold for this point and thus the problem is solved: the property doesn't hold for all points in the unit square.
tells me $\mathcal P$ holds for not only my query point but also for a small square containing my point. Thus I don't need to query for other points in this small square.

The problem is the small squares returned by the oracle are of variables sizes. What data structure and algorithm can I use to store the small squares returned? How can I track efficiently whether I have enough small squares to cover the unit square (and can thus stop the algorithm since I know the property holds for the whole unit square)? Or compute new points to query?

Edit: Okay, I realized my description of the problem is over-complicated. Basically this is the problem:

I have a certain number of squares of variable sizes and positions. How do I check whether they completely cover the unit square, or if not, how do I obtain the coordinates of a point of the unit square not covered ? PS: The problem is online.

I'd suggest a 2-dimensional k-d tree storing one point for each corner of each rectangle returned.  A quadtree or 2-dimensional interval tree might also work.  More generally, you might consider a 2-dimensional binary space partitioning tree, where you partition based on one of the edges of one of the squares returned (extended horizontally or vertically out to infinity in both directions).

How would you partition, in a binary space partitioning tree?  Each square gives you two horizontal lines and two vertical lines (obtained by extending each edge of the square out to the full unit square).  For instance, imagine sorting all of those vertical lines from left-to-right, and picking the median line, and using that to partition.  Continue splitting recursively.  This gives you a nested tree of regions.  Then, associate each square with the lowest (deepest) node/region that fully contains it.  When you are picking a split for a particular region of space, you use all of the lines that fall within that region (from all squares that have any overlap with that region).


Edge Constraint satisfaction in a Directed Graph Path? Given a directed Graph and two vertices $S$ and $D$ (source and destination) such that each of its edges has a weight of the form:

$A_i+B_ix_i = V$

where $A_0$ is a non negative integer, $B_0$ is a positive integer, $x_i$ a variable that can take non negative integer values (each variable used only once in the graph).

Find a positive value $V$ such that it there exists a path from $S$ to $D$ in Graph such that $V$ satisfies all edges in that path.

Of course the trivial method would be testing each positive integer value of $V$. But this might take an exponential time. Is there something better we can do to achieve the solution in polynomial time, or that is the best we have ?

Assume first that the $x_i$ can take any arbitrary values. Then the constraint $A_i + B_i x_i = V$ just states that $V \equiv A_i \pmod{B_i}$. Two such constraints are contradictory if $A_i\not\equiv A_j \pmod{(B_i,B_j)}$, where $(B_i,B_j)$ is the GCD of $B_i$ and $B_j$. The Chinese Remainder Theorem should show (after some work) that any set of constraints in which no two are contradictory can be simultaneously satisfied. (Prove or refute!)

The constraint that $x_i \geq 0$ doesn't actually impose any further constraints. Indeed, take a solution $V$ to the original problem. By adding to $V$ a large enough multiply of $\prod_i B_i$, we obtain another solution in which all $x_i$ are non-negative.

This reduces your problem to the following problem:

  Given a directed graph and a set of forbidden pairs of edges, does there exist a path from $s$ to $t$ that doesn't contain a forbidden pair of edges?

Unfortunately, this problem is NP-complete, by reduction from SAT. Given $m$ clauses $\varphi_1,\ldots,\varphi_m$, there will be $m+1$ vertices $v_0,\ldots,v_m$. For each literal $\ell \in \varphi_i$, there is a corresponding edge from $v_{i-1}$ to $v_i$. Two complementary literals form a forbidden pair. A legal path from $v_0$ to $v_m$ exists iff the instance is satisfiable.

There are now two options:

Either your particular instance has more structure, which you can employ to get a more efficient solution;
Or your original problem is also NP-hard.


How to use adversary arguments for selection and insertion sort? I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere.

I have some doubts regarding this. I understand that adversary arguments are usually used for finding lower bounds for certain "problems" rather than "algorithms".

I understand the merging problem. But how could I write one for selection and insertion sort?

From your comment, it seems you are confusing the meaning of lower bounds, upper bounds and asymptotic notation. For instance, take Insertion Sort. Its best-case running time is $\Theta(n)$ (this happens when the input is already sorted). Its worst-case running time is $\Theta(n^2)$ (this happens when the input is in reverse sorted order). So, since the running time falls between a linear function of $n$ and a quadratic function of $n$, you can say that the running time of Insertion Sort is both $\Omega(n)$ and $O(n^2)$. It's important to understand in this case that you cannot say that the running time is $\Omega(n^2)$. Why? Because there exists an input that causes the algorithm to run in $O(n)$. However, you may say that the worst-case running time is $\Omega(n^2)$, again because there exists an input that causes the algorithm to run in $\Omega(n^2)$. We usually use the $O$ notation for the worst-case though, since we are interested in an upper bound on the number of operations done by the algorithm.

Now, let's think about an adversary argument for Insertion Sort (you may try to derive one for Selection Sort by applying the same ideas).

Consider the Insertion Sort algorithm playing against an opponent that we will call the adversary. The aim of the adversary is to provide an input X for the algorithm that maximizes the number of comparisons done by the algorithm. This is usually analyzed in the context of decision trees. A decision tree shows all possible sequences of comparisons that the algorithm could make. Each interior node of a decision tree represents a single comparison. The two children of a node represent the two outcomes of the comparison (yes/no or true/false). Each leaf represents a possible output. For sorting algorithms, the leaves are permutations of the keys. The algorithm starts at the root and follows a path down to a leaf. At each internal node, the answer for the comparison done tells the algorithm which node must be visited next. When the algorithm reaches a leaf, it outputs its corresponding permutation. The running time of an algorithm (seen as a decision tree) for a given input is the number of comparisons done in the path from the root to the output leaf. Now, the adversary has a simple strategy that will work against any comparison-based sorting algorithm, including Insertion Sort: whenever the algorithm makes a comparison, the adversary chooses the answer that will eliminate the fewest possible permutations.

In general, owing to the fact that with $n$ elements there are $n!$ possible permutations, any decision tree for sorting must have at least $n!$ leaves, and so must have depth $\Omega(\log(n!)) = \Omega(n\log n)$ (by Stirling’s approximation).
For Insertion Sort, the adversary may craft a particular input that causes the corresponding decision tree to have depth of at least $\Omega(n^2)$.

The algorithm uses an array $A[1 .. n]$ to store the input elements and is based on the following invariant:

At the start of each iteration of the for loop, the subarray $A[1 .. j-1]$ consists of the elements originally in $A[1 .. j-1]$, but in sorted order.

In each iteration, the elements in $A[1 .. j-1]$ are therefore already in sorted order, and the algorithm examines $A[j]$ and inserts it in its final proper place, by comparing the value of $A[j]$ against the value of the elements in $A[1 .. j-1]$, starting from $A[j-1]$ and proceeding back to $A[j-2]$ and so on until $A[j]$ is no longer the greatest one in the comparison. The elements in $A[j+1  .. n]$ are in an unknown state (with regard to the sort order) and will be processed in later iterations.

Here is the strategy of the adversary. Knowing that the algorithm works by inserting $A[j]$ in its proper place by moving the elements in $A[1 .. j-1]$, then the obvious strategy is to maximize in the $j$-th iteration the number of elements that must be moved in order to accommodate $A[j]$. This is easily accomplished by carefully choosing the input so that it is in reverse sorted order. Indeed, in this case, the number of elements that must be moved in each iteration is $j-1$. This leads to the $\Omega(n^2)$ worst-case running time (determined by the corresponding arithmetic series).


How to find a good saw function for PRNG? As part of an assignment I have to write a PRNG using a sin (or any other trigonometric function) and a saw function which I'm struggling a bit with. So how would you find a good saw function with about equal distribution?

This is what it is supposed to look like:

There are two functions I've got now,

y=(seed/1000*state*49) mod 101 and

z=(y-1 % 10) / 10)

and distribution looks like this (I'm not fine with that 1 and 0 distribution):

I think this is an effect of the rounding in your implementation or in the histogram.

Let's say your histogram contains 100 columns. Each represents a width of 0.01. The column at 10 shows how many items fall between 9.995 and 10.005. The column at 0 shows how many items fall between -0.005 and 0.005. However, there are no items below 0, so there is nothing between -0.005 and 0. This column will only show halve of the items in the other columns.


The running time of algorithm is at most $O(n^2)$ The problem is that if an algorithm is $O(n^2)$ then it is also $O(n^3)$ and $O(n^4), O(n^n), \ldots$ and the phrase 'at most' does not make sense in this situation.
For this reason, I am not sure whether this statement is correct or not.

The two phrases

The running time is $O(n^2)$

and

The running time is at most $O(n^2)$

mean the same thing.
This is similar to the following two equivalent claims:

$x = y$ for some $y \leq z$.
$x \leq y$ for some $y \leq z$.

Why would we ever use "at most $O(n^2)$", then? Sometimes we want to stress that the bound $O(n^2)$ is loose, and then it makes sense to use "at most $O(n^2)$". For example, suppose that we have a multi-part algorithm, which we want to show runs in time $O(n^2)$. Suppose that we can bound the running time of the first step by $O(n)$. We could say "the first part runs in $O(n)$, which is at most $O(n^2)$".


Parse forest from an ambiguous grammar Parser-generators like nearleyjs can return a parse forest instead of a parse tree.
Since not all input may result in a parse forest (eg, the input may exercise only a non-ambiguous subset of the grammar), how do you programmatically choose the 'correct' parse tree from the forest?
One option is to always choose the first element from the array of parse-trees returned.
Another option is to flag the returning of a parse-forest (instead of a single tree) as an error. But then, this would defy the whole point of having Earley-like parsers that allow parsing of ambiguous grammars!
Also, since only some input may result in a parse-forest (instead of a single parse-tree), how do you rule out surprises in a live/Production environment? Assumption: For non-trivial or non-trivially long grammars, it's not humanly possible to create tests that cover all inputs.

To use such a parser, you need some external way to select among the possible trees in the forest.  Typically there are additional constraints beyond what is encoded in the context-free grammar, which can be used to identify the correct parse.  In other words, there are some rules that are part of the syntax (they are part of the context-free grammar, and thus handled by the parser), and some rules that are part of the semantics; there may be multiple parses that are compatable with the syntax rules, and then the semantic rules are used to select which one complies with the semantic rules.


What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$? Suppose I have a function $f$ on sets.

What is the property of $f$ called when,

for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$

i.e.

$$\forall x,y : x\supseteq y \Rightarrow f(x) \supseteq f(y)$$

It is called monotonicity with respect to the inclusion ordering of sets.

More precisely, it is in this case increasing monotonicity since the order is preserved. If the order was reversed, it would be decreasing monotonicity.

It can also be called direct monotonicity and reverse monotonicity,  as increasing/decreasing seems used mostly for numeric functions.

The function is said to be strictly monotone iff (in the direct case)

$$\forall x,y : x\supsetneq y \Rightarrow f(x) \supsetneq f(y)$$


Proof that multi-armed bandit optimization has exponential regret if loss function is general I was reading Robert Kelinberg's paper on Nearly Tight Bounds for the Continuum-Armed Bandit Problem
There is a section where he says:

"For a d-dimensional strategy space, any multi-armed bandit algorithm must suffer regret depending exponentially on $d$ unless the cost functions are further constrained. (This is demonstrated by a simple counterexample in which the cost function is identically zero in all but one orthant of $R^d$, takes a negative value somewhere in that orthant, and does not vary over time.)"

Here $d$ is the dimension of the set of strategies (values that we can pick at each time step).

I can't really see why that is the case, that with that given cost function you get exponential regret. Can you please help me understand how the proof would go?

I'm not exactly sure what he means, but here's a very similar example in a discrete version. Imagine the strategy space weren't continuous but instead consisted of all points in $\{\pm 1\}^d$, one point in each of the $2^d$ orthants. The cost function $C$ is $0$ in all but one of those locations, where it is $-10$.

In order to get any decent regret, you have to figure out which point is the one with cost $-10$ and start choosing it repeatedly. But how will you figure it out? Your only way is to just try different points until you find the right one. But it will take on the order of $2^d$ tries to find it since that are the number of options.

This raises the question - how can a restriction like making $C$ convex rule out this kind of example?


Grammar is LL(1) or not? S -> AS | b

A -> SA | a

I get FIRST of S = {a,b} for S->AS
and FIRST of S = {b} for S->b

Hence FIRST(AS) ∩ FIRST (b) is not a disjoint
This is not LL(1)

But I checked this site http://smlweb.cpsc.ucalgary.ca/start.html
and this shows the grammar is LL(1).

Here I am confused!

Is it LL(1) or not?

That website uses a different notation than what you assumed. This would be the correct input:

S -> A S | b.
A -> S A | a.

You entered AS (and SA) which it does not recognize as A followed by S, but as a single nonterminal named AS.

With that input it correctly says that the language is not $\text{LL}(1)$.


Is any language that can express its own compiler Turing-complete? A comment over on tex.SE made me wonder. The statement is essentially:

  If I can write a compiler for language X in language X, then X is Turing-complete.

In computability and formal languages terms, this is:

  If $M$ decides $L \subseteq L_{\mathrm{TM}}$ and $\langle M \rangle \in L$, then $F_L = \mathrm{RE}$.

Here $L_{\mathrm{TM}}$ denotes the language of all Turing machine encodings and $F_L$ denotes the set of functions computed by machines in $L$.

Is this true?

The informal statement is not true, as shown by the following programming language.  Any string of, say, ASCII characters is a valid program and the meaning of every program is, "Output a program that just outputs a copy of its input." Thus, every program in this language is a compiler for the language but the language is not Turing-complete.

I'm not sure if your "computability theory version" is equivalent but it is also not true. By Kleene's second recursion theorem, for any coding of Turing machines, there is a TM that accepts its own coding and rejects all others.1 This machine is a counterexample to the proposition.
More concretely, we can achieve the result by choosing a coding. For example, let every odd number code the machine $M$ defined by "If my input is odd, accept it; otherwise, reject" and let the number $2x$ code the machine coded by $x$ in your own favourite coding scheme for Turing machines. $\langle M\rangle$ is in the language $L$ accepted by $M$ but $F_L$ is not Turing complete.

1 Kleene's second recursion theorem says that, for any enumeration $(\phi_i)_{i\geq 0}$ of the partial recursive functions (i.e., for any coding of programs as integers), and any partial recursive function $Q(x,y)$, there is an integer $p$ such that $\phi_p$ is the function that maps $y$ to $Q(p,y)$. So, in particular, let $Q$ be the function that accepts if $x=y$ and rejects otherwise. By the theorem, there is an integer $p$ that codes the program $\phi_p(y) = Q(p,y)$. That is, $\phi_p$ accepts its own coding $p$ and rejects all other inputs.


Is purely functional programming in some situations less efficient than imperative programming? I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that some of the data types don't exist in functional languages. For example, it may be hard to implement hash data structures or mutable arrays.

With that in mind, is purely functional programming in some situations algorithmically more expensive than imperative programming? For example,

If I want to implement timer heap with O(1) peeking of next timer to expire, O(log N) removal of next timer to expire, O(log N) addition of new timer, O(log N) removal of arbitrary timer and O(log N) adjustment of timer expiration time, can I implement the timer heap in a purely functional programming language?
If I want to implement a timer wheel, can I do so in a purely functional programming language?
If I want to implement O(1) lookup in a set or a map, meaning in practice hash structures are needed, can I do so in a purely functional programming language?
If I want to implement a ring buffer for efficient communication between threads in a producer-consumer pattern, can I do so?
If I want to maintain a a list of free TCP ports in a firewall, doubly linked list would be a suitable O(1) data structure for that, allowing O(1) removal of an arbitrary port, but can I do so in a purely functional language?
If I want to have a fast and efficient O(1) bit set, can I have such a construct in a purely functional language?

Note I'm not interested in large vs small constant in the runtime. I'm interested in runtime becoming fundamentally different, e.g. O(log N) instead of O(1). Of course functional algorithms may be less efficient due to the extra overheads of added abstraction in terms of runtime constant.

Yes.  There are problems where we can prove there is a $\Omega(\lg \lg n)$ factor slowdown.  We also know that the slowdown is at most $O(\lg n)$ in all cases.  See What classes of data structures can be made persistent?.


Why is reduction mostly associated with proving hardness? Reduction is a powerful problem solving technique that is helpful in solving problems in terms of the solution to other problems, it can also be used for complexity analysis. Why does most of the literature restrict mentioning reduction to proving hardness which seems to be a pessimistic point of view for reduction (unless P=NP ofcourse :) )?

EDIT: Just to make sure my question is well understood. I am aware that reduction is used for problem solving and designing or analyzing algorithms, I have solved hundreds of contest problems with reduction which leads to my question of why is a random search for reduction lead to the NP completeness context with book chapters and papers illustrating its power from the complexity theory point of view when the same basic definition for reduction can be used for designing algorithms but just rarely (or implicitly) mentioned. In other words, why does a random sampling of the occurrences of the term "reduction" show a clear bias towards its use in complexity theory.

Actually, people do commonly use reductions for both purposes: both for proving lower bounds, and for designing algorithms to handle a certain problem.

For instance, it's very common to reduce a problem to linear programming, to a max-flow problem, or to another well-studied problem.  This is using reductions for solving problems.

Any particular textbook might focus more one or the other use of reductions.  That's a philosophical choice on the part of the author.


Pumping Lemma vs Myhill-Nerode I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much.

Let us take the following as an example:

$$ L = \{ a^n b^n \mid n \ge 0\} $$

Could someone tell me the differences between both theories and how to prove the language I brought is not regular according to each approach.

I know this is a basic example – that is the reason I chose it, make it simple rather than make it harder.

Thank you in advance!

The main difference between the pumping lemma and Myhill–Nerode theory is that the non-regularity criterion of Myhill–Nerode theory always holds for non-regular languages, whereas the same isn't true for the pumping lemma.

In other words, both the pumping lemma and Myhill–Nerode theory give you conditions which imply that a given language is not regular. If a language is not regular, then it is guaranteed that the Myhill–Nerode criterion will hold, but it is not guaranteed that the pumping lemma condition will hold. You can see an example in this question.

There are extensions of the pumping lemma which are guaranteed to work:

Jaffe's pumping lemma: a language $L$ is regular iff all long enough words $w \in L$ can be decomposed as $w = xyz$, with $y \neq \epsilon$, such that for all $i \geq 0$ and all words $v$,
$$xyzv \in L \text{ iff } xy^izv \in L.$$
Block pumping lemma: a language $L$ is regular iff there exists a constant $k$ such that for all words $u,v,w_1,\ldots,w_k$ there are $1 \leq i < j \leq k$ such that for all $\ell \geq 0$,
$$
uw_1\ldots w_k v \in L \text{ iff } u w_1 \ldots w_i (w_{i+1} \ldots w_j)^\ell w_{j+1} \ldots w_k v \in L.
$$

In both cases, it in fact suffices to allow only $i = 0$.

(This material is from Handbook of Formal Languages, Volume 1: Word, Language, Grammar, Chapter 4 by Sheng Yu, Section 4.1.)


Can area-partitioning lose included points due to floating point precision? I'm currently partitioning a big area $A$ into $n$  areas $B_i$ such that
 $$\bigcup_{i=1}^n B_i  = A$$

I have geo-coordinates which I know are in $A$ (also with the finite precision of floats).

Obviously, for every point $p$ in $A$ there has to be an area $B_i$ such that the point is in $B_i$. Formally:

$$p \in A \Rightarrow \exists i: p \in B_i$$

But due to floating point precision, I wonder if it could happen that for all $B_i$ the B_i.intersects(p) method returns false. Formally:

$$\forall i: \neg B_i.\texttt{intersects}(p)$$

All areas are polygons and neighboring polygons share some points which define the polygons.

If the answer is yes, then an example would be good. It would be awesome if one could also quantify the probability of this.

(In my current case, I use shapely.)

This is a problem for anyone making graphics cards: To draw an area, it will usually be split into triangles, and for many drawing methods it is important that every point is drawn exactly once.

At some point you'll have use an algorithm that decides whether a point x is on or above a line l, and at some other point you'll have an algorithm that decides whether x is below the line l. For good results, you need to design this algorithm carefully so it is guaranteed to say "YES" once and "NO" once. It doesn't matter too much whether the result is correct (not saying YES when the point is actually just a tiny bit below the curve), what's important is that the answer is "YES" exactly once and not twice.


Language equivalency for modified CFG closed over intersection Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both between CFGs and between other CFG+'s.
Consider non-context-free language:
$$
\{ a^nb^nc^n|n≥0\}
$$
With the addition of intersections, consider the following "CFG+":
$$
S\rightarrow AB\ \&\ CD
$$
$$
A\rightarrow aAb\ |\ \epsilon
$$
$$
B\rightarrow cB\ |\ \epsilon
$$
$$
C\rightarrow aC\ |\ \epsilon
$$
$$
D\rightarrow bDc\ |\ \epsilon
$$
As AB covers when #a = #b, and CD when #b = #c, this intersection will match the non-context-free language given above.
It is obvious that context-free languages are a strict subset of the languages described by CFG+. However, how does this compare with other languages? Is this equivalent to a context sensitive grammar? An unrestricted grammar? Is there already a language category I should be recognizing this as?

It looks like by describing your "CFG+" grammar, you have independently reinvented/rediscovered the conjunctive grammar.
Here is more quote from that article on Wikipedia.

The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure under complement and under $\epsilon$-free string homomorphism are still open problems.

Since context-sensitive languages are closed under complement, the family of conjunctive languages is a strict subset of the family of context-sensitive languages. In fact, the family of languages generated by boolean grammars, grammars that extends conjunction grammars with negation operations, is also a strict subset of the family of the context-sensitive languages.

A related problem is the expressive power of intersections of context-free languages.
An infinite hierarchy of intersections of context-free languages by Liu and Weiner shows that ($d$-1)-intersection closure of context-free languages is strictly contained in the $d$-intersection closure of context-free languages, since the language $\{a_1^{n_1} a_2^{n_2} \cdots a_{d}^{n_{d}} b_1^{n_1} b_2^{n_2} \cdots b_d^{n_d} \mid n_1,n_2,\ldots ,n_d\ge 0\}$ is contained in the latter family of languages but not in the former family of languages for all $d\ge2$.


What does it mean when a dot appears in a logic gate other than the NOT gate? (in logic diagrams) For example, this gate:

looks like an OR gate, except there's a dot to the right. The dot is reminiscent of the fact that there's a dot in the NOT gate, so I wonder if it has something to do with that. There's no NOT after this gate in the diagram I'm looking at, so this doesn't to be implementing NOT OR or something like that...

This is a NOR gate. You can implement a NOR gate using a combination of a OR and a NOT gate. However, in MOSFET implementation or other technologies (i.e. electrical hardware architecture), we can build a NOR gate directly and more efficiently (i.e. more efficient than using a OR and a NOT gate). That's why we use NOR as well.


How would you implement truly random hash functions in practice? Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$.

A hash function $h:[U]\rightarrow[m]$ is truly random if

For any set of distincts elements $\{x_{1},...,x_{k}\} \subseteq [U]$ and any set of values $u_{1},...,u_{k} \subseteq [m]$ we have $Pr_{h}[h(x_{1}) = u_{1} \wedge ... \wedge h(x_{k}) = u_{k}] = \frac{1}{m^{k}}$. This of course implies  that $h(x_{i})$ is uniform random and independent of $h(x_{1}),...,h(x_{i-1}),h(x_{i+1}),...,h(x_{k})$.

I was trying to understand why this is not possible to implement efficiently in practice, and found this paper where at some point they write in the abstract:

  Hashing is fundamental to many algorithms and data structures widely
  used in practice. For theoretical analysis of hashing, there have been
  two main approaches. First, one can assume that the hash function is
  truly random, mapping each data item independently and uniformly to
  the range. This idealized model is unrealistic because a truly random
  hash function requires an exponential number of bits to describe.

I do not see how using exponential number of bits can help us come up with a truly random hash function when the universe is $[U]$ and the hash table can store at most $m$ elements.

How would you use an exponential number of bits to come up with a function that can guarantee the probabilities described above?

The number of bits required to describe a function from $[U]$ to $[m]$ is $m \times 2^U$. This is exponential in $U$.


Caesar Cipher - logic circuit my teacher asked the class to do a digial circuit that encrypted a message using cesar's cipher, and a circuit to decrypt, but my only idea is to solve it using a circuit that does P + K mod N, where P is The position of the letter in the alphabet, K the value of the key, and N is the number of letters in the alphabet. Or use an adder circuit, for example, when P and K have 4 bits, and N equals 8. Even if an overflow occurs, the sum between them would still give me a result within my representation. However, in my case I am using an alphabet with 94 symbols, so how can I solve this problem?

I appreciate any help.

You can instead subtract $N-K$ and test if you go negative and then add $N$ again. Or test the number against $N/2$ and if greater subtract $N-K$ otherwise add $K$.

With 94 symbols you only need 7 bits. If you go with the post check you'll need to add a bit to account for overflows for certain values of input and $K$.


How is this problem related to the study of algorithms and big O notation? I'm taking a graduate computer science course on algorithms and analysis. The current subject is big O notation and recursion. How is the following problem related to the study of algorithms, recursion, and big O notation? I know and understand the solution to the problem, but I just don't see how this is relevant to the subject matter.

Given an $x$, show that $x^{62}$ can be computed with only eight multiplications (A general algorithm can not accomplish it).

You need to be more patient. This problem is hinting at the repeated squaring algorithm for powering. The more general question is: How long does it take to compute $x^n$? Naively, you might think that it takes $n$ multiplications, but the repeated squaring algorithm can do it using $O(\log n)$ multiplications.

Repeated squaring is very important for cryptographic applications. Many cryptographic algorithms rely on computing modular powers: $x^p \pmod{n}$, where in general $p$ and $n$ could be very large (say roughly $2^{1024}$). It makes a huge difference whether you do it in $O(p)$ or in $O(\log p)$ time.


Recommender System - Binary Ratings without explicit dislike I'm currently looking into developing a system in which media from various sources is collected, with the notion that the media collected for each user is media they 'like'. This results in a set of n users, each with their own respective set of m liked items.

Most papers on recommender systems I find either require explicit ratings, or work within a binary domain with likes and dislikes.

How would I go about making recommendations based mainly on what is in a users preferred / liked set, without information on what they dislike?

Thanks.

You can use one-class classification, in which the learner is given only positive examples, but must later on classify new instance into positive and negative. An example is intrusion detection – the learner is given the network in its working state, and tries to identify outlying behavior.


Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables In distributed systems we use the Chord algorithm to create a p2p distributed hash table. While this algorithm is very useful and efficient wouldn't it be better if we used an AVL tree? Chord algorithm relies a lot to the hash function (in order for the nodes to be distributed evenly).

An AVL tree on the other is always balanced so in the worst case it will take $O(h)$ time to search for something, whereas h is the height of the tree and given that AVL trees are always balanced the height of the tree is at most $logN$ (whereas N is the number of living nodes in the network).

In my opinion AVL trees can give the same search speed (or maybe even better). So what is the need to use Chord algorithm instead of an AVL tree? I understand that Chord Algorithm is more of a Peer to peer system as many nodes know many others while in an AVL tree each node knows two descendants. Is this the sole purpose of not using AVL trees?

Is there an issue with handling churns that makes one better than the other?

Chord is meant to be used in a distributed system where we need to be concerned with load balancing and handling failures of individual machines.

If you try to maintain an AVL tree in a distributed system by spreading the nodes among the available machines, the machine that has to take care of the root node will have a very high load as it is involved in every single request. Moreover, if this machine failed, the AVL tree would be partitioned, which requires you to introduce additional pointers for redundancy (similarly to what is done in Chord using "fingers").

A data structure that is suitable for distributed systems are Skip Graphs, which essentially have the same functionality as balanced trees, in particular, they provide $O(\log n)$-time operations. Moreover, a Skip Graph has built-in fault-tolerance (i.e. can handle churn), as it contains an expander graph as a subgraph (with high probability), and therefore can withstand even a constant fraction of node failures.


Do recursive algorithms generally perform better than their for-loop counterpart? I'm sure this is not a challenge for you but it remains an open question for me:

Is it wise to prefer a recursive algorithm over its for-loop counterpart?

E.g. take the evaluation of the natural logarithm of a number $N + 1$

$$ \ln (N+1) = \ln N + \Delta N, $$

where

$$ \Delta N = 2 \sum_{k=0}^{\infty} \frac{1}{(2k+1)(2N+1)^{2k+1}}. $$

While one could implement it as a recursive function with an appropriate terminating condition (e.g. relative error tolerance), you could as well put it in a for-loop and break when desired.

The answer will depend on the compiler.  As @vonbrand wrote, "Given a good enough compiler, you might even get the very same object code."  In particular, good compilers will do tail-call elimination.  In some cases this can effectively transform the code into a for-loop.  Your example looks like a good example of an instance where this could happen.

As @vonbrand says, "And unless circumstances are exceptional, your time is much more valuable than the computer's, so think first in terms of ease of writing/understanding the program".  Or, to quote Tony Hoare and Donald Knuth: "Premature optimization is the root of all evil."  To this I'd add, focus first on algorithm and data structure improvements (where one can often make the biggest improvements) and on user needs: and then if performance of this particular part of the code is really critical, try both a loop and recursion and measure.  Don't rely on your intuition; measure.


If the strings of a language can be enumerated in lexicographic order, is it recursive? If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?

Lexicographic order is not such a good order since its order type is not $\omega$. Instead of explaining formally what that means, let me give an example. Consider the language $(a+b)^*$. If you enumerate the words in lexicographic order, you get
$$
\epsilon, a, aa, aaa, \ldots, ab, \ldots
$$
The first $\ldots$ signify infinitely many terms. So it isn't really clear what it means to enumerate a language in lexicographic order. There could be two interpretations: either the language $L$ doesn't suffer from this problem, or you really mean a slightly different order. Since the precise answer doesn't matter for all that follows, we will just assume that you can effectively enumerate $L$ in some (effective) order whose order type is $\omega$ (i.e., when the problem above doesn't happen).

The proof that $L$ is recursive can be a bit subtle, due to a certain ambiguity: what happens if $L$ is a finite language? There are two reasonable interpretations of effective enumerability in this case: either the enumerator will eventually halt, or it won't, but at some point would stop outputting strings. Fortunately, this ambiguity doesn't affect the proof.

For the proof that $L$ is recursive, we consider two cases. If $L$ is finite, then it is trivially recursive. If $L$ is infinite, then to decide whether $x \in L$ and wait until either $x$ is output, or a string larger than $x$ is output (if $x \notin L$ then this will happen eventually since $L$ is infinite). In the first case $x \in L$, in the second $x \notin L$.

To see that $L$ is not necessarily context-free, you can consider your favorite non-context-free language $\{c^nb^na^n : n \geq 0\}$ which is effectively enumerable in (plain vanilla) lexicographic order.


DFA Infiniteness Testing Why is it that the test for an infinite language on the DFA $M$ has an upper bound of $2n$?

That is to say, when testing for a string of length $k$, why does the theorem say:

$$n \leq k < 2n$$

I understand the lower bound of $n$ IAW the Pumping Lemma of $|w| \geq n$. I'm just not sure why $2n$ was chosen and I think I'm over complicating it.

The upper bound comes also from the proof of the pumping lemma. If you have a DFA with $n$ states, you know that if it accepts a word in length $\ge n$ then the word passes through a circle in the states, thus you can repeat the circle as many times as you like and get an infinite language.

Now, for the upper bound, assume the DFA is infinite, and accepts a word of length $\ge2n$. Now, when you run the word on the DFA, and since the DFA has only $n$ states, there must be a cycle. That cycle must be of length $\le n$. You can now remove a number iterations from that circle such that you will get a word $w$ of length $n\le |w| < 2n$.

The proof is even easier when you use the pumping length $n$ derived from the pumping lemma. Just show that for a word $w=xyz$ where $|w|\ge 2n$, since $|xy|\le n$ and $|y|>0$ there exists an $i\in \mathbb{N}$ such that $n\le |xy^iz| < 2n$.


Speed-up of two-tape Turing machine I try to figure out linear speed-up of Turing machine.

Prove that any problem that can be solved by a two-tape Turing machine that has time complexity t can be solved by another two-tape Turing machine having time complexity $t′$, where $t′(n) = O(n) + (t(n)/2)$.

The idea seems to show that what the first machine does within two steps the second machine is capable to do within one step. Time complexity $O(n)$  seems to be complexity of encoding input of first machine to input of second machine.

I have a problem with proving this statement and will appreciate any help.

In addition, why only two-tape Turing machine was mentioned, what about one-tape Turing machine.

The single tape case is known as the Linear speedup theorem. It has a nice little trick by compressing the tape and using overlapping chunks of the tape. Try whether it also works in the two-tape case.


Would the following grammar be ambiguous? I have the grammar $S = aSbS|bSaS|\varepsilon$. When I was first looking at the problem I thought it was unambiguous. When I looked at the answer it said that it was ambiguous. The solution it gave was:

$S \rightarrow aSbS \rightarrow a\varepsilon bS \rightarrow a\varepsilon b\varepsilon \rightarrow ab$

$S \rightarrow aSbS \rightarrow aSb\varepsilon \rightarrow a\varepsilon b\varepsilon \rightarrow ab$

This doesn't make sense to me though because aren't these both producing the same parse tree?

Indeed, both of those derivations produce the same parse tree.

A grammar is ambiguous iff it has two different leftmost derivations for a sentence. (Equivalently, if it has two different rightmost derivations.) Only one of the provided derivations is leftmost, so these two derivations do not constitute a demonstration of ambiguity.

The grammar is ambiguous, though:

$$\begin{align}&S\to aSbS \to abS \to abaSbS\to ababS \to abab\\
&S\to aSbS \to abSaSbS \to abaSbS \to ababS \to abab\\
\end{align}$$


How to compare/cluster millions of strings? I have around 1,000,000 of strings of variable length (from 200 to 50000) that can contain 5 characters (A, B, C, D, E).

What I actually want is to cluster them together if they are similar enough. By similar enough I mean they have an edit distance < $t$. This $t$ should be dependent on the length of the strings being compared. So for example, if I'm comparing two 200-length strings, $t$ could be 20, while comparing two 1000-length strings $t$ could be $100$

I've been reading a lot of literature lately but can only seem to find approaches that are not actually viable for so many strings, and I'm not much into probabilistic approaches so maybe you can help me out there.

The problem is that comparing them in pairs to cluster them would already be very costly even if the comparison was performed in $O(1)$ time (which is obviously not the case).

I've been reading about using indexes such as BWT and mixing it with things like the pigeonhole principle (Given two strings $P$ and $T$, let $p_1$, $p_2$, ..., $p_{k+1}$ be a partitioning of $P$ into $k+1$ non-overlapping non-empty substrings.  If $P$ occurrs in $T$ with up to $k$ edits, then at least one of $p_1$, $p_2$, ..., $p_{k+1}$ must match exactly) but as I said before, I think it is unfeasible because of the quantity of strings and their length.

Also, some algorithms perform comparison in $O(t \cdot min(m,n))$ where $t$ is the desired edit distance (they will be clustered together if edit distance <= $t$) and $m$ and $n$ are the length of the strings. But this can also be a problem because with large strings, $t$ could also be large.

So, do you know about anything that could help me in my case? Also, algorithms that can be made parallel are very welcome, as I intend to run this in a very large cluster with 400+ cores. Is there any fast probabilistic algorithm that can reduce the amount of comparisons needed for example?

The length of each string is at least 200, and you only consider two strings similar if their edit distance is less than 20.  So if $S,T$ are similar, then there must exist $U$ such that (1) $U$ is a substring of $S$, (2) $U$ is a substring of $T$, and (3) the length of $U$ is at least 10.

This suggests that one heuristic is to find all length-10 substrings and look for collisions.  In other words, build a hashmap whose keys are substrings and values are the containing strings; for each string $S$, compute all length-10 substrings $U$, and add a mapping from key $U$ to string $S$ into a hashmap.  This can be done in linear time; a rolling hash may improve efficiency.

Now iterate through the hashmap and find all pairs of strings $S,T$ that share a common length-10 substring.  For each pair $S,T$, compute the edit distance and check whether the edit distance is < 20.  I suggest using the optimized edit distance computation with "early out": if the edit distance is $\ge 20$ you don't care what its actual value is.  This computation can be done in $O(20 \cdot (n+m)) = O(n+m)$ time per pair, where $m,n$ are the lengths of $S,T$.  Length 10 is large enough that probably won't be too many pairs $S,T$ that contain a common length-10 substring but whose edit distance is $\ge 20$, so you probably won't waste too much time computing the edit distance on pairs you aren't interested in.

There are other approaches, based on metric trees, BK trees, and other methods.  See, e.g., Efficient map data structure supporting approximate lookup.  You might also look into the computational biology literature, which deals with a similar problem when clustering DNA sequences.  There the alphabet has 4 characters, rather than 5 characters, and strings can be much longer, but they also want to find similar pairs from a large database, and they have developed practical and efficient algorithms.


Given a network flow find if there's a min cut that only one of the given edges lay on it Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$,
and given 2 edges $e_1 , e_2 $.

Find if there exists a min-cut such that only one of the edges belongs to the min-cut.

Hope to get help.

First, compute the minimum cut value $c$ of the network.

Second, remove edge $e_1$ and increase the capacity of $e_2$ to infinity, then compute the minimum cut value $c_1$ of the new network.

Third, remove edge $e_2$ and increase the capacity of $e_1$ to infinity, then compute the minimum cut value $c_2$ of the new network.

Now you can check if $c-c_1\ge c(e_1)$ or $c-c_2\ge c(e_2)$ to see if there exists a min-cut in the initial network that contains exactly one of $e_1,e_2$.