# Question
Title: Why would you use a monitor instead of a semaphore?
I am currently attending the concurrent programming course in my university and we recently started talking about the concept of a monitor. While I understand the necessity of mutual exclusion, I do not understand why I would use a monitor for that.

As I understand it, a monitor guarantees that exactly one or no process is in the critical section at all times. We can achieve exactly that with a semaphore. Furthermore we implement monitors (or at least one possibility to implement them is) with semaphores.

So why would I implement something that does exactly the same thing as a semaphore with a semaphore? What benefits do I get?

# Answer
We finally discussed why you would use a monitor instead of a semaphore in the lecture today.

It basically comes down to this: The monitor and the semaphore are equally expressive, meaning you can find a solution for a problem with a monitor where originally a semaphore was used and vice versa.

Well, we already knew that, so why would you use a monitor instead of a semaphore?

Personal preference. Normally a desktop application would use monitors, leaving less possibilities for mistakes, but, as a trade off, having a relativly bloated structure. Semaphores on the other hand are often used in operating systems, as they are a lightweight structure, but leaving more possibilities for mistakes.

I guess we can conclude that it is a situational decision wether or not you need/want to use a monitor or a semaphore. If you build a real time system you might want to go with a semaphore, if you are building an office programm you might aswell go with a monitor.
> 7 votes

# Answer
They are nearly interchangeable and one can be built out of the other. It is somewhat language dependent which is implemented/ preferred (eg Java has built-in monitors using "synchronize" keyword). However the semaphore is considered a "lower level" entity than the monitor for the following reasons & differences:

> Both Monitors and Semaphores are used for the same purpose – thread synchronization. But, monitors are simpler to use than semaphores because they handle all of the details of lock acquisition and release. An application using semaphores has to release any locks a thread has acquired when the application terminates – this must be done by the application itself. If the application does not do this, then any other thread that needs the shared resource will not be able to proceed.
>
> Another difference when using semaphores is that every routine accessing a shared resource has to explicitly acquire a a lock before using the resource. This can be easily forgotten when coding the routines dealing with multithreading . Monitors, unlike semaphores, automatically acquire the necessary locks.\[1\]

See also the highly voted Stack Overflow answer Semaphore vs. Monitors - what's the difference? with a great/ memorable analogy to public toilets & bike stands.
> 11 votes

# Answer
Take a peek at e.g. "The little book of sempaphores" by Allen B. Downey. it states and solves lots of synchronization problems. Check particularly the botched solutions, and you will see that semaphores are a very low-level mechaism, very powerful but extremely easy to misuse, where simple mistakes have terrible consecuences (made even worse by the inherent nondeterministic operation of concurrent programs). It is e.g. easy to forget enforcing mutual exclusion, operating on the wrong semaphore, and so on. Monitors offer prepackaged solutions to the most often used cases, and carry with them most of the advantages of object oriented programming (i.e., you know the only way to mess with the variables managed by the monitor is through it's operations). The disadvantage is that they can't be retrofitted easily into non-object-oriented languages, and plain object-oriented languages will leave their use optional.
> 2 votes

---
Tags: concurrency, synchronization, mutual-exclusion
---


# Question
Title: Generating graphs such as found on Sedgewick's Algorithms book on the MST chapters
I always wondered what the algorithm might be to generate graphs such as those found on Sedgewick's algorithms books (consider the picture on the left):

Could any one point me to the name (or algorithm) that creates such a graph over a 2D region? I am not interested in how to draw it or display it (or in any library).

From all I can see the (x, y) points are probably just randomly generated, but the edges between vertices don't seem to be randomly connecting any two vertices. Maybe the closer two veritces are the bigger the odds of a connection existing between them is?

Thanks

# Answer
It appears to be a random geometric graph. Points are placed at random within an area, according to some distribution, and an edge is added between every pair of points whose distance is less than some threshold.

A common case is to distribute the points uniformly at random within the unit square and add edges between all pairs of vertices that are at distance at most $d$ from each other, for some constant $d$. In other cases, the threshold might depend on the number of vertices.
> 6 votes

# Answer
Perhaps they generate points at random, and have a fraction of the arcs to "at distance $d$" nodes, or even some probability of a link that (strongly) decreases with distance. You'd have to experiment (and probably they fooled around until some "pleasant" image resulted). Or it is maybe a sliver of a larger graph (say roads between cities). If I was writing a book, I certainly would try several approaches (as the ones I suggest) and select the "nicest" one.
> 1 votes

---
Tags: graphs, sampling
---


# Question
Title: Program transformations for numeric stability
There's tons of research on program transformations for optimization. Is there any research on transformations that improve numeric stability? Examples of such transformations might include:

* Transform $\log(\exp(a)+\exp(b))$ into $\max(a,b)+\log(\exp(a-\max(a,b))+\exp(b-\max(a,b)))$
* Convert multiplication of an inverse matrix times a vector into the solution to a linear system solver.
* Automatically perform multiplications of small numbers in the log domain.

All the tricks I'm aware of for better numeric stability like this are pretty standard and something that every "good" numeric programmer always does. Since the tricks are so standard and always applied, it makes sense that the compiler might be able to do them for us.

# Answer
There actually is some research on improving the numerical stability of floating point expressions, the Herbie project. Herbie is a tool to automatically improve the accuracy of floating point expressions. It's not quite comprehensive, but it will find a lot of accuracy improving transformations automatically.

Cheers,

Alex Sanchez-Stern
> 8 votes

# Answer
A quite interesting piece of work is a *stochastic* approach of Schkufza, Sharma and Aiken. Note that in general, the code is not guaranteed to be correct, but they give a really nice argument for *probabilistic correctness*. Stochastic Optimization of Floating-Point Programs with Tunable Precision, PLDI 2014.

Edit: The above work is designed to optimize for speed while keeping (stochastic) correctness. It may be possible to use it for the opposite purpose though (see my comment below).

---

I just thought of some work more related to Alex Stern's reference, by Thomas Wahl and Jaideep Ramachandran that can be found here.
> 3 votes

---
Tags: compilers, floating-point, numerical-algorithms
---


# Question
Title: Amortized analysis for doubling resizing array is ~3n
I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused:

> Question 2: What if instead we decide to double the size of the array when we resize?
>
> Answer 2: This is much better. Now, in any sequence of n operations, the total cost for resizing is $1 + 2 + 4 + 8 +. . .+ 2^i$ for some $2^i \< n$ (if all operations are pushes then $2^i$ will be the largest power of $2$ less than $n$). This sum is at most $2n−1$. Adding in the additional cost of $n$ for inserting/removing, we get a total cost $\<3n$, and so our amortized cost per operation is $\< 3$.

How did we arrive at $2n-1$?

I know that the sum of powers of $2$ is $2^{n-1}-2$, but does that matter at all here? I know that $2^{n-1} -2$ is **very** different from $2n-1$, but I'm not seeing how you can get $2n-1$ from the sum of $1 + 2 + \dots +2^i$ where $2^i$ is largest power of $2$ before $n$ item.

If anyone can give concrete examples, that would be great because that's how I understand better.

I know where the remaining $n$ comes from which makes this whole operation $3n$.

# Answer
Note that the statement involves two variables $i$ and $n$. The sum of powers of two equals the next power minus one: $\sum\_{k=0}^i 2^k = 2^{i+1}-1$. It is mentioned that $2^i$ is the largest power less than $n$. That means $2^i \< n \le 2^{i+1}$.

As $2^i \< n$ we have that the sum $2\cdot 2^i -1$ is less than $2n-1$.

I am a little confused as the text states "at most" rather than "less than".
> 3 votes

---
Tags: algorithm-analysis, mathematical-analysis, amortized-analysis
---


title: Longest simple walk in a complete graph

text:
# Question
Title: Longest simple walk in a complete graph
A *simple walk* is a path that does not contain the same edge twice. A simple walk can contain circuits and can be a circuit itself. It just shouldn't have the same edge twice.

A *simple undirected graph* is an undirected graph with no loops and multiple edges. A *complete graph* is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A *path of length $n$* is a sequence of n edges $e\_1$,$e\_2,\ldots,e\_n$ such that $e\_1$ is associated with $\\{x\_0,x\_1\\}$, $e\_2$ with $\\{x\_1,x\_2\\},\ldots,e\_n$ with $\\{x\_{n-1},x\_n\\}$.

> What is the length of the longest simple walk in a complete graph with $n$ vertices?

**What I tried:** When $n$ is odd, every vertex has degree $n-1$ which is even. It follows that the graph has a euler circuit (every edge is included), therefore the longest walk length is $n(n-1)/2$, corresponding to the total number of edges.

But when $n$ is even, I try to follow similar reasoning and get stuck. I get a degree sequence, but I can't prove it is graphic. How could we handle the case where $n$ is even?

# Answer
If $n$ is odd, the graph has an Euler trail, i.e., a simple walk on all $\tfrac12n(n-1)$ edges. This is obviously optimal, since it uses every edge in the graph.

If $n$ is even, delete a matching of size $\tfrac12n-1$, i.e., delete a set of that many edges, no two of which share an endpoint. The resulting graph $G$ has two odd-degree vertices and $n-2$ even-degree vertices, so it has an Euler trail, which is a simple walk of length $$\tfrac12n(n-1) - (\tfrac12-1) = \tfrac12n(n-2)+1\\,.$$ This is optimal. Any simple walk is an Euler trail of the graph formed from the vertices and edges of the walk. But any simple walk in $K\_n$ longer than the one just described would have to contain at least four vertices of degree $n-1$, which is odd. And no graph with four odd-degree vertices has an Euler trail.
> 5 votes

---
Tags: graphs
---


title: Proof by Turing Reduction

text:
# Question
Title: Proof by Turing Reduction
I need to proof the following by turing reduction.

Given two languages:

$Q= \\{(\langle M\_1 \rangle , \langle M\_2 \rangle ) \mid L(M\_1) = L(M\_2)\\}$

$I= \\{\langle M \rangle \mid \\;\vert L(M) \vert = \infty \\}$

Where $\langle M\_1 \rangle$ is the encoding of Turing Machine $M\_1$.

I need to show that $ I \le\_T Q $ ($I$ can be reduced to $Q$ using a Turing Machine).

So far I came up with the following idea, which I think isn't correct.

Create Turing Machine $M'$ so that a mapping from $Q$ to $I$ is found:

1. $M'$ takes as input a random word $u$ for example $aab$
2. $M'$ removes the input ($u$) from its tape
3. $M'$ guesses words $v$ and $w$
4. $M'$ checks if $v \in L(M\_1)$ and $ w \in L(M\_2)$ if and only if $v = w$

# Answer
Your solution doesn't quite make sense for many reasons:

1. The reduction should take $\langle M \rangle$ as input, and using an oracle to $Q$, decide whether $\langle M \rangle \in I$.
2. The reduction should be deterministic (so step 3 is invalid).
3. The function of the *arbitrary* word $u$ is not explained; indeed, steps 1 and 2 seem useless.
4. You don't explain what $M\_1,M\_2$ are in step 4 (are you trying to reduce from $Q$ to $I$?).
5. You don't explain how to implement step 4.

Also, you are missing a proof that your reduction works. Without a proof, your solution is wrong even if it could be completed to a correct solution.

One solution goes along the following lines (I'm assuming $L(M)$ consists of all inputs on which $M$ halts; I also say that $n \in L(M)$ is *accepted* by $M$):

1. Given $M$, let $M'$ be the machine that on input $n$, simulates $M$ on $n$, and then (if $M$ halted) tries to find an $m \> n$ accepted by $M$ (if there is no such $M$, it never halts); you can implement this using the technique of dovetailing.
2. Give $M$ and $M'$ to the $Q$ oracle, and return its answer.

The idea is that $L(M)$ is infinite iff $L(M) = L(M')$. I'll leave you the details.
> 5 votes

---
Tags: complexity-theory, turing-machines, reductions
---


# Question
Title: Covering a polygon with n circular rings
Question 1: Why we can/can't solve the following problem using a geometric constraint solver?
Question 2: Is there any algorithm to solve this problem?
Question 3: Can we reduce this problem into some known computational problems?

**Input:**
1. $C\_1, ..., C\_n$: Centres of $n$ circular rings.
2. $S$: A polygon of arbitrary shape in the 2D plane.

**Notations:**
1. $(OR\_i, IR\_i)$: outer radii and inner radii respectively for circular ring $i$
2. $R = \text{ring}\_1 \cap \dots \cap \text{ring}\_n$: the intersection of the rings (i.e., the region of space formed by their intersection: the set of points that are contained in all $n$ of the rings)

**Output:**
Find $(OR\_1, IR\_1),..., (OR\_n, IR\_n)$, such that region $R$ covers the polygon $S$ with minimal *error area*.

*Error area* is defined as: $$\text{Area}(S - R) + \text{Area}(R -S)$$

Intuitively, I want an algorithm to find optimal $(OR, IR)$ for each ring to cover a given shape $S$, so the error area (the parts of $R$ outside the given shape: \[$\text{Area}(R - S)$\] + the parts of the shape not covered by $R$: \[$\text{Area}(S - R)$\]) is minimal.

The problem differs from this problem in following ways:

1. The polygon should be covered by the *ring* formed by two circles with same centre.
2. This is a simpler problem in the sense that it has fewer variables. The position of the centres are given; we only need to find the inner and outer radii.

# Answer
> 2 votes
This problem might be hard to solve exactly. I would suggest you try gradient descent (or another mathematical optimization technique).

---

\[ The stuff below here is obsolete, now that the question has been edited to change the problem statement along these lines. \]

Note that minimizing your error ratio is equivalent to minimizing

$$\text{Area}(S-R) + \text{Area}(R-S),$$

since $S$ is given (so $\text{Area}(S)$ is fixed). This observation does not seem to help very much, though.

---
Tags: np-complete, reductions, computational-geometry
---


title: CPU reading cycles.

text:
# Question
Title: CPU reading cycles.
Assume the CPU has 64 data lines. Then Z reading cycles will be needed to load an array of 12 double-precision floating-point numbers, each number coded in eight bytes, from the main memory into the CPU. Z = ?

So I'm looking at some of the past exam questions to prepare for my exams next year and this question (above) has stumped me. I genuinely don't know how to work this out. I know that a 64 bit machine is a lot faster than a 32 bit one but that's about it. Can anyone explain this? (Assume I am an idiot please)

# Answer
a **double precision floating-point**, is a 64-bit variable (as the question says: 8 bytes each = 64 bits).

If the CPU's bus width is 64bit, and assuming the memory has a data width of 64-bit, then exactly 12 read-cycles are needed to read 12 double-float variables, since at each cycle we can access 64-bits = 1 complete variable.

If, however, the memory has a data-width of 8 bits (every address gives back only 8 bits of data), then 1 double-float variable lays over 8 different addresses, and takes 8 cycles to read. Then, to read 12 different variables, the CPU needs to access 96 different addresses, i.e., 96 read-cycles.

If the parameters of the CPU/Memory are different, so does the answer.
> 1 votes

---
Tags: computer-architecture, memory-access
---


# Question
Title: How to turing reduce equivalent languages $Q$ to infinite language $I$
Given two languages:

$Q= \\{(\langle M\_1 \rangle , \langle M\_2 \rangle ) \mid L(M\_1) = L(M\_2)\\}$

$I= \\{\langle M \rangle \mid \\;\vert L(M) \vert = \infty \\}$

I'm trying to Turing reduce $Q$ to $I$ ($Q \le\_T I$), not the other way around as solved here

Any ideas on how to solve this? What exactly will the Turing machine do here and which part is getting solved by the mysterious Oracle?

# Answer
> 4 votes
Given $M\_1$ and $M\_2$ you construct a machine $M$ that on input $w$ does the following:

1. it runs $M\_1$ on the first $w$ inputs ($\epsilon$,0,1,00,01,..) for $w$ steps each.
    1. if $M\_1$ accepts some input, you run $M\_2$ on the same input and check it accepts too. (note, $M\_2$ may not halt!)
    2. If $M\_1$ rejects some input, you run $M\_2$ for $w$ steps and verify it doesn't accept during that time.
2. you do the same with $M\_2$: run $w$ steps on each of the first $w$ inputs, and verify everything works, or reject otherwise
3. if all checks pass - accept. Otherwise reject.

The idea is the following: as long as $M\_1$ and $M\_2$ behave the same, you will keep accepting all $w$'s. but as long as you find a difference, then you will reject that $w$ and all inputs $w'\>w$, thus the accepted language becomes finite. You should be careful because machines may not halt. For instance, $M\_1$ may reject some input, but $M\_2$ won't halt on it -- still, they both "reject" it, and this case should be carefully analyzed.

---
Tags: complexity-theory, turing-machines, reductions
---


# Question
Title: Is there any example of automatas (or similar) systems that emerge complex internal structures on its own?
Automatas are turing-complete grid-based systems with progression rules on which we can encode arbitrarily complex structures. For example, this is a "glider gun" on Conway's Game of Life:

Due to turing-completeness, with enough efforts, one could encode fully-featured structures, such as machines that claimed territories on the grid and defended those against intrudes. As much as that is possible by human design, the system will not emerge complex structures on its own. That is, you can't start a Game of Life with random initial conditions, leave it running for years and hope that, when you come back, you'll be able to observe gliders and other complex structures emerged naturally.

**My question is: is there any known computing system in which complex structures emerge naturally from just running it for long enough?**

# Answer
It seems very hard to define the phrase "internal structures that defend their own existences" in a rigorous or precise way, so it is not clear that the question is well-defined. However, some very simple systems can admit behavior that might be described in these terms.

For instance, consider Conway's game of life. It is known to allow for replicators: i.e., there are self-replicating patterns which create a complete copy of themselves. Replication can be thought of as a "strategy" for "defending your own existence"; if you spawn many copies of yourself, then even if someone messes up one of the copies, the other copies will still exist.

So, to the extent that the phrase "internal structures that defend their own existence" is well-defined, self-replicators in Conway's game of life might be considered a form of internal structure that will defend its own existence.

Conway's game of life is very simple. Another very simple example is Rule 110, which is an extremely simple cellular automaton. It is known that Rule 110 is Turing complete, which means that it is possible to simulate Conway's game of life in a Rule 110 cellular automaton, which means that a Rule 110 cellular automaton can be argued to allow for "internal structures that defend their own existence". It's probably going to be hard to find a system that's much simpler than a Rule 110 cellular automaton.

---

In general, we should probably be careful about anthromorphicizing the behavior of computational systems like this. Just because they behave in ways that resemble the behavior of people or animals doesn't necessarily mean it's necessarily going to be super-meaningful to describe them as acting with a 'purpose' (like self-defense). Ascribing human motivations or emotions to them runs the risk of misleading our intuition.
> 7 votes

# Answer
It might be worth having a look at Turmites (https://en.wikipedia.org/wiki/Turmite ).

They are state machines on an n-dimensional grid that alter their direction and output based on the current cell. Many configurations of them build 'highways' (repeating structures) and if interrupted many will find a way back to the 'highway' and continue again.
> 3 votes

# Answer
as another answer states, this is a tricky question, but heres another "lead" for you that roughly fits your criteria. solitons are studied in physics and are "persistent wave patterns" that can occur in any dimension (incl physically realistic ones like 3d), based on simple energy dynamics on a lattice. they are composed out of emergent properties of a combined nonlinear propagating and dispersive effects that cancel to leave the patterns. while the study originated in analog systems, it was eventually realized the overall system can be modelled by a (digital) cellular automata with fairly simple local rules.

there is significant study of solitons in physics, where they arise in many different specialized contexts, and there are some major parallels with particle physics, but far less study from a CS orientation. while much research has accumulated over decades, there is not a lot of active work, possibly due to their interdisciplinary/ scientifically crosscutting nature. hence they may be somewhat understudied wrt their importance and there are likely significant undiscovered phenomena in this area. heres an example paper along these lines:
> 2 votes

# Answer
Sorry, cannot comment - this should be one :-/ http://rendell-attic.org/gol/tm.htm Full Universal Turing Machine in Game of Life.

And after reading your question I think that answer will be dissapointing but true. Any system that emerges on its own should be considered "evolving", but instead of giving some recombinations or modification all we include are constraints. Furthermore when we see some "really" evolving system, we would prefer to speed process up, and disable even more randomness in it. Things you have described are random occurences of complicated structures or patterns, but if we treat it as we should - it is fully deterministic but out of reach to expect it in mind or via programming. It looks awesome, but it was already there, so this is not new form, new generator or quality on its own. Every such system has to obey rules. Every truly evolving system that I know of failed. The most beautiful was AI cat with number of neurons equal to real alive cat - and even environment was technically good, well it did not learned any behaviour... There were examples of generators of programs - random but grammatically correct source codes were generated, compiled until they could do something (well, anything that basic program can do), many cpu hours passed as it generated some trivial calculations. What I wanted to add: if you want something to emerge you have to allow it to change its rules, and take enormous amount of time (unfortunatelly for that reason also define rules to decrease failure rate) to observe evolution, which is not practical so it is not popular task. Otherwise, you are looking for very rare occurence of some pattern on machine that could do something unexpected. But if you consider this from deterministic point of view, as continuum theory says, what I added is already the same pointless predetermined process. On the other hand, there is bigger probability that there will be some new quality added if selfmodification of machine is enabled.
> 1 votes

# Answer
I choose to write this as an answer rather than a comment because my feeling is that all answers are rather long comments, and this is going to be too long for a comment. No one is actually saying yes or no to your question. I will not either (I do not know whether there is such a structure that is known as such, but I believe that such a structure can exist, though I have no proof for it).

To begin with, I expect you looked at the wikipedia page on cellular automata, where your animation comes from. But you do not seem to have drawn any other information from that page.

Your question is about order and stability of complex patterns emerging from some chaos based on simple (?) rules. Indeed, one answer comments that you look for complex structures that "*behave in ways that resemble the behavior of people or animals*".

Emergence of order from chaos, and of (more or less) stable complex structures immediately rings a bell in real physical systems: **thermodynamics**. So my first move was to call Google with the words: *automata theory thermodynamics*, and the second answer was the wikipedia page on cellular automata.

Indeed it seem that some researchers (including Stephen Wolfram) have investigated the issue in relation with the thermodynamics aspects found in nature. This is not very detailed, and I guess one would have to analyze thermodynamics of cellular automata models, whatever that may be. This has been done to some extent with reversible cellular automata.

There is probably more to it. The wikipedia page alludes to the creation of large stable structures (class 4 cellular automata), "*reminiscent of the phase transition in thermodynamics*".

That is all I can say about this line of thought, though I believe it should be an important one for the kind of question asked. The work on trying to understand physics and biology from cellular automata model is obviously also relevant.

This said, the page also mentioned the work of John von Neumann who proved the existence of a self replicating system based on cellular automata."*This design is known as the tessellation model, and is called a von Neumann universal constructor.*" Replicators were found more recently fr Conway's game of life.

Building on this, one can imagine that some type $A$ of such structures could have an ability to clear up space to let other $A$ structures find space to reproduce. As you remark yourself, this is to be expected from the Turing completeness of cellular automata.

So one can imagine that the structure you suggest could exists. Which probably means that infinitely many different such structures could exist.

However your question is whether it could emerge spontaneously, if one waits long enough. But **you do not specify an initial state**.

Given an "infinite" cellular universe, and a random initial configuration, I do not see why not, at least for some types of celluler automata. It may take some 13 billion years though (just a randomly chosen duration). But maybe the most interesting pointer in that direction is the class 4 cellular automata of Wolfram classification. See also this reference.
> 1 votes

---
Tags: reference-request, automata, turing-completeness, evolutionary-computing
---


# Question
Title: An application where we always delete the oldest object?
In what king of application, in which we insert or delete objects, we always delete the oldest one (the least recently stored, more precisely which was the first object stored) ?

# Answer
> 3 votes
There are plenty such applications. To give some examples:

* *(windowed) data streams:* Assume a sensor that sends new data every second. You want to know the average of the last minute. You keep the latest 60 elements. Every time you get a new element, the 61-st old element belongs to the previous minute, and you then delete it.
* *queue*: when each elements is a task, and you service them in a FIFO manner, then each time you service a task you delete it. The FIFO ordering guarantees you always deletes the oldest task.
* *staleness*: when space is limited (e.g., in cache memory), when you wish to remove old items in order to make room for a new one, a good heuristic is to remove the oldest accessed element, as it got "stale" and has low probability to be accessed again.

I'm sure there are plenty other examples, but your question is too general to answer. Feel free to edit it if you wish a more specific answer.

# Answer
> 2 votes
You do not define what you mean by oldest. In a cache system, the oldest object may be the one that was first to be introduced in the cache, or the the least recently updated, or the least recently used. This is a fair interpretation since an item that is used is to be loaded when used, if not already in.

So a possible answer would be a cache operating under the LRU strategy, for "Least recently used". It may be a virtual memory cache, or a web cache for example.

Obvious answers are all systems using a FIFO memory, i.e. a queue.

An other example could be a running average on some function, for example when you control the noise bandwidth by averaging the $n$ last measurements, according to some formula.

Another possible example, though probably not best, is a backup systems where you keep only the most recent version.

---
Tags: databases
---


# Question
Title: What is the name of the following algorithm?
I am using the following algorithm to solve an optimization problem I have. I was wondering if there is a proper name for this algorithm in the literature.

Let $f(x)$ be my objective function.

I guess some $x\_0$ and see have it performs.

Next, I **randomly** generate around $x\_0$, some $\\{x\_k \\}$ for $k \in \[1:K\]$ and see how the compare to $x\_0$. If I find $x\_n$ that perform better than $x\_0$. I perform the same procedure again with $x\_n$.

I am only starting to learn about algorithms and would be grateful if you point me to the name and some reference on similar algorithms

# Answer
This is a form of local search. It is similar to hill climbing. It's also reminiscent of stochastic hill climbing, as @Juho suggests.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Binary tree algorithm asymptotic analysis problem
Assume we have a perfectly balanced Binary tree. We have the following algorithm: ***For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child of the node.***

So, the way I try to find the Big-O complexity is this: There are O(N) nodes in the tree and each has O(log2N) ancestors, so overall we'll have **O(N\*log2N)** complexity if we start the algorithm from the root.

Now consider another problem for the same Binary tree: ***For each node, go to its left and right child. If the node doesn't have any children, for each ancestor, go through all the previous ancestors.***

Now my attempt for finding the complexity: We basically keep going through every node until we reach the leafs. There are N/2 leafs in a perfect Binary tree with N nodes and for each leaf we have (log2N) ancestors. Since for each ancestor we have to traverse every previous, the overal compexity when we're on a leaf is O(Log2(N)^2), so overall complexity becomes **O(N\*log2(N)^2)**.

The problem is that I think the algorithms basically do the same thing. Why do I get different complexities for them?

# Answer
> 1 votes
They're not the same thing. Consider some node $x$. Ask yourself how many times the algorithm does the operation "iterate through all the ancestors of $x$".

The first algorithm does this operation once. The second algorithm does this operation $k$ times, where $k$ is the number of descendants of $x$. So, it's no surprise that the second algorithm takes longer: it's doing a lot more repeated work.

---
Tags: algorithms, complexity-theory, asymptotics, binary-trees
---


# Question
Title: Good characterization of unsatisfiable Horn3SAT formula?
Horn3SAT is $P$-complete problem under logspace reductions. Since Horn3SAT is in $P$ its complement must have short witnesses. I am looking for *natural* short proof that a Horn3SAT formula is not satisfiable. Examples for similar problems in $P$ are 2-coloring problem and planarity problem. A graph is not 2-colorable if and only if it contains an odd cycle. A graph is not planar if and only if it contains a subgraph that is a subdivision of $K\_5$ or $K\_{3,3}$.

> Is there a good characterization of Horn3SAT formulas that are not satisfiable? What does constitute a *natural* short witness for unsatisfiable Horn3SAT formulas?

I am not interested in algorithmic proof such as running an algorithm for deciding Horn3SAT problem. I am only interested in good characterizations similar in spirit to the above two examples.

**EDIT**: As illustrated by the two examples above, I am only interested in characterizations of the complement set of Horn3SAT in terms of some *forbidden structure*.

# Answer
> 2 votes
You should not expect a proof that is asymptotically shorter than the formula itself. For instance, consider

$$(x\_1 \implies x\_2) \land (x\_2 \implies x\_3) \land \dots \land (x\_{n-1} \implies x\_n) \land x\_1 \land \neg x\_n.$$

This formula is not satisfiable, but any proof of unsatisfiability will need to have size $\Omega(n)$.

If you're willing to accept a "proof" of size $n$, then the formula itself arguably qualifies as a proof (as it's easy to check that a given formula is not satisfiable).

Alternatively, any chain of deductions that ends in a contradiction qualifies as a proof, where each step in the chain is a variable and its inferred truth value, as justified by a clause in the Horn3SAT formula and previously inferred variable truth values. If the formula is not satisfiable, then there must exist such a chain of deductions of size $O(n)$. The chain of deductions is easily verifiable and thus constitutes a proof of unsatisfiability. In other words, we derive a directed implication graph from the input Horn3SAT formula; the proof of unsatisfiability is then a directed path in the graph from some $x\_i$ to $\neg x\_i$.

If none of these meets your needs, you'll need to define what you're looking for more carefully.

---
Tags: complexity-theory
---


title: Is $H_0$ reducible to $\overline H_0$?

text:
# Question
Title: Is $H_0$ reducible to $\overline H_0$?
Be $H\_0$ the special halting problem with $$H\_0 = \lbrace \langle M \rangle \in \lbrace 0,1 \rbrace^\* | \varepsilon \in L(M)\rbrace$$ and $\overline{H\_0}$ being its complement. Is $H\_0$ reducible to $\overline{H\_0}$? $$H\_0 \leq \overline{H\_0}$$
I guess that this is not possible as $\overline H\_0$ is not semi-decidable, but I am not sure how to approach such questions in general and how I would really prove it in this case in particular.
Are there any properties of problems that forbid the reduction?

# Answer
Such reduction does not exist.

If $H\_0 \le \overline{H\_0}$ then you can simply decide $H\_0$:

given input $\left\<M\right\>$ calculate the reduction $f(\left\<M\right\>)$ and Simultaneously run $\left\<M\right\>$ and $f(\left\<M\right\>)$ with empty input. If $\left\<M\right\>$ halts return the same answer, If $f(\left\<M\right\>)$ halts flip the answer and halt.

We have $\epsilon\in L\left(\left\<M\right\>\right) \iff \epsilon\notin L\left(f\left(\left\<M\right\>\right)\right)$ hence one of the machines has to halt and our newly constructed machine for deciding $H\_0$ always halts.
> 3 votes

---
Tags: computability, turing-machines, reductions
---


# Question
Title: What can a quantum query to a function do?
The $n$-qubit Hadamard gate acts as,

$$H (\otimes^n \vert 0 \rangle ) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum\_{x \in \\{ 0,1\\}^n} |x\rangle $$

So it is capable of producing the uniform superposition state over an exponential number of states in what is to be seen as a \`\`single" step.

* Now if one is given a boolean function $f$ then how is it that the above uniform superposition state can be converted into $\frac{1}{\sqrt{2^n} } \sum\_{x \in \\{ 0,1\\}^n} f(x) |x\rangle$ by a \`\`single query to $f$ in superposition" ?

Can someone give a mathematical or a gate picture of this ''single query to $f$ in superposition" ? What is the unitary operator which corresponds to this ''single query to $f$ in superposition" ?

---

A part of this confusion arises because I am under the impression that if kets are indexed by elements of $\\{0,1\\}^n$ then a ''single" quantum query to a Boolean valued function $f$ is \`\`by definition" a transformation of the form $\vert x \rangle \vert y \rangle \rightarrow \vert x \rangle \vert y \oplus f(x) \rangle$ or which is often thought of as the operator $O\_f(x)$ acting as $O\_f(x) \vert y \rangle = \vert y \oplus f(x) \rangle$

But I can't see the transformation in the question as a any combination of $O\_f(x)$ kind of operators!

# Answer
the gate $f$ performs the transformation $$\rvert x\rangle \rvert0\rangle \to \rvert x\rangle \rvert 0\oplus f(x)\rangle, $$

but $0$ is idempotent for $\oplus$ so you simply get $\rvert x\rangle \rvert f(x)\rangle$. Now, by linearity, if you input a superposition instead of a basis states, you'll get a superposition of the "answers", e.g.,

$$\frac1{\sqrt2}(\rvert 0\rangle \rvert0\rangle+\rvert1\rangle |0\rangle) \to \frac1{\sqrt2}(\rvert 0\rangle \rvert f(0)\rangle+\rvert 1\rangle \rvert f(1)\rangle)$$

Then, if you start with a Hadamard, and get an equal superposition of all basis states, you end up with a superposition of all possible "answers". $$\frac1{N} \sum\_x \rvert x\rangle \rvert 0 \rangle \to \frac1{N} \sum\_x \rvert x\rangle \rvert f(x) \rangle.$$

The fact that $x$ or $0$ are in fact a "string" over $\\{0,1\\}$ doesn't make any difference - treat them as a single quantum system of higher dimension (or treat each qubit as a separate function $f\_i$ where $f\_1()f\_2()\cdots f\_n()=f()$ are the bit-wise functions.
> 5 votes

---
Tags: complexity-theory, quantum-computing
---


# Question
Title: Which of LBA or TM would you choose to express the given language and why?
Both Linear Bound Automata (LBA) and Turing machine (TM) can be used to express the language accepted by below Finite Automaton (FA). Which of LBA or TM would you choose to express the given language and why? Justify your decision with logical reasons.

# Answer
I expect this is an exercise to check how you can read and analyze a finite state automaton, and possibly some other knowledge.

The question is absurd since a FA is trivially expressible as a LBA or a TM, so that the question makes little sense, even more so because a LBA is a TM using linearly bounded tape, which is obviously the case for a FA, where the tape is limited to the size of the input.

But what is more, is that the simplest way to represent the language is to enumerate all its strings, all four of them.

$$L=\\{a,abb,abba,abbaab\\}$$

It may be that this set has some special property, but I do not know it.

Of course, I do not want to spoil the fun of seeing why $L$ is composed of only 4 strings.

> Look well at states 1 and 9.
> 3 votes

---
Tags: automata
---


# Question
Title: How to eliminate for/if/while from algorithms when it's possible
Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive functions, there must be a way to convert the program into ones that do not have for/if/while and so on (which is elementary recursive).

# Answer
For/if/while are the main blocks that will check for a condition. Since a recursive function will keep recurring until a condition is met, you will at least need an if statement to tell the function when to return. Otherwise, you will essentially be stuck in an infinite loop.
> 2 votes

---
Tags: computability, programming-languages, simulation
---


# Question
Title: Understanding the heuristic used for approximate string searching through an FSA
The paper I'm looking at: Fast approximate string matching with finite automata (2009)

Explanation of the algorithm (from my understanding anyway):

A word is inputted into the automaton and from each state, a number of possible actions can be taken depending on the current symbol/character being looked at at position $pos$. These "actions" include:

* Staying at the current state and deleting the character currently being pointed at by $pos$.
* Taking a transition to a next state and substituting the current character at $pos$ with the transition label used.
* Taking a transition to a next state and inserting the transition label at $pos$.

The action is decides to take is based on a cost function $f=g+h$ (where the lowest $f$ is chosen) for each action.

$g = 0$ if no edit operation is performed on the input word (i.e. the transition label taken to a next state, is the same as the current character at pos) and $g=1$ otherwise.

$h$ is the maximum between two heuristic functions $h(2)$ and $h(\infty)$.

* $h(2)$ looks at the transition labels that can be reached within two transitions from that state (note, not the current state) and compares those reachable transitions to the next two characters in the input word after $pos$. $h(2)$ gets $+1$ added for each character in the input word that does not match any of the characters that the state $s$ can reach within two transitions.
* $h(\infty)$ looks at the transition labels that can be reached until the end of the path from that state and compares that to the rest of the input word after pos. As with $h(2)$, $+1$ for each character in the input word that can't be matched to any of the reachable characters from state $s$.

Eventually this algorithm will lead to some accepting state where the path up to that accepting state is the closest accepted word to the input.

I think I understand the algorithm correctly since I tried to implement it from my understanding in Java (I'm doing it for my project, although my project only handles regular expressions of a small alphabet of around 3 different symbols as opposed to a natural language dictionary) and it seems to work to some extent and works fine for the example given in the paper, however my problem is is that I don't understand what priority is used in the case where $f$ values tie for $f=g+h$ (tied $f$ values are actually common).

The example used in the paper, inputs the word "dat" into the automaton, what I don't understand is why the algorithm goes from state 0 to state 3 (I circled this part in red) when $f=g+h$ is also 1 for the state 0 choice (I circled this part in blue).

The paper mentions

> "ties were resolved in the priority queue by giving priority to the highest word position."

but I don't understand what is meant by this.

It also mentioned:

> "In our experiments, the strategy of breaking ties so that the node that has advanced farthest in the word to be matched is given priority has proven to be far superior to any of the tiebreaking strategies we explored."

# Answer
Those two statements are correlated: "giving priority to the highest word position" is the same as "the node that has advanced farthest in the word is given priority".

This appears to be why the algorithm selects state three. State zero does not result in an advancement in word position, whereas the transition to state three is further in the word position and so satisfies their heuristic of highest word position and thus gets priority for first expansion.

To see why this heuristic results in better results, examine the node zero. Deleting 'd' you see all the letters remaining are in the reachable nodes from zero, which means $h = 0$, and we only performed 1 operation, so $f = 1$. However in order to get to the acceptance state along the shortest path we have to take another operation to go to 3 while adding 'c' back, then we transition through the states 5, and 7 making no changes. Obviously the fastest (and shortest) path is to simply swap 'd' to 'c' and transition to state three first, which the heuristic suggests in this case.
> 3 votes

---
Tags: finite-automata, strings, edit-distance
---


# Question
Title: number of comparison in sort algorith with special operation
Let's define: $ a\_i:a\_j \Longleftrightarrow a\_i \< a\_j;\ a\_i=a\_j;\ a\_i \> a\_j $
So it is similiar to normal operation $\<$, but $:$ give information when elements are equal.
I want show that lower bound for sort array of $n$ elements with this operation is $\Omega (n\log n)$.

I know proof for normal comparison. Nevertheless I can't solve it, I thought about it a long time, but without effect. Can you help me ?

(It isn't homework, nowadays I am on holiday :))

# Answer
> 1 votes
Let's suppose that it is possible to sort it with $:$ in time $o(nlogn$). So we use ordinary comparisons: $\<$ and $\>$. If both $a\_i\<a\_j $ and $a\_j \> a\_i$ is not truth then we conclude $a\_i=a\_j$. And now, we can sort in time: $o(2nlogn)=o(nlogn)$ - it is impossible.

---
Tags: sorting, lower-bounds
---


# Question
Title: probablistic procedure to permutate array
input : $array\[1...n\]$
output: permutated array
Our algorithm should be probablistic and complexity should be $O(n)$.

Could you give me hint ? My weakness is probability theory and it is why I have a problem.

# Answer
> 2 votes
First we need to define the algorithm a bit more stringently. I prefer this one.

Choose a $N$-permutation $P$ with probability $U(P)$ where $U$ is a uniform distribution of the space of $N!$ permutations on $N$ values.

I like to solve this in an inductive fashion.

First we think about how we can do this with 1 value. Well how many permutations are there over 1 value? There is 1 such permutations. Because our uniform distribution needs to sum to unity it follows that the permutation must occur with probability. So we select it with probability 1. That is to say we always select it.

Second we think about how we can generate an $N$-permutation given an $(N-1)$-permutation? How can we do this? It isn't hard to see that there are an equal number of $N$-permutations in which a number $X$ occurs in position $i$ as there are where $X$ occurs at position $j$. So if the number is the same and the permutations are uniformly distributed then it must be equally likely for a number $X$ to occur anywhere in the permutation. Thus we just need to figure out how to insert our $N$th number into the smaller permutation in a uniformly distributed way.

If you want to look it up this is called the Fisher-Yates shuffle

# Answer
> 3 votes
I'm not exactly certain what you mean by probabilistic procedure as pertains to array permutation, and I'm going to assume you're looking for a random permutation of the array. I'm basing this off the formulation of the problem being very similar to an algorithm for that purpose.

So lets say as a person I'd like to do this task: Well, I'd probably just write down all the possible numbers, and then pick a random one. Then I'd cross of the one I'd picked and continue until I'd crossed them all off.

Spoiler as to the name of the algorithm which I mentioned:

> See Fisher-Yates Shuffle algorithm or Knuth Shuffle.

# Answer
> 1 votes
Try this: // Shuffle a collection, using the modern version of the // Fisher-Yates shuffle.

translated from: http://underscorejs.org/underscore.js shuffle function

In this case we use $A$ to denote **input** array and $B$ to **shuffled** output array

> *1.* Function $\text{shuffle} : A \mapsto B$:
>
> *2.* let $n$ the length of $A$
>
> *3.* let $B$ shuffled empty array, with $n$ size
>
> *4.* for each index $i \leftarrow 0$ until $n-1$ do:
>
> > *1.* set random value $r \leftarrow \text{random}(0, i)$
> >
> > *2.* if ( $r \neq i$) $\implies$ $B\[i\] \leftarrow B\[r\]$
> >
> > *3.* $B\[r\] \leftarrow A\[i\]$
>
> *5.* end for block;
> *6.* return $B$;

---
Tags: probabilistic-algorithms, permutations
---


# Question
Title: Making a branch-and-bound algorithm more efficient for a large input
I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course).

I tried implementing dynamic programming first, and that worked fine, but ran into memory issues with larger datasets, so I decided to try branch-and-bound.

My implementation works well for small datasets, but when I try and scale it, it hangs up like the DP algorithm, but I can't tell if it is because it is very slow or space inefficient.

The way I have implemented it is as follows (in bad pseudocode)

```
initialise global best value as 0
initialise taken list and leave list
initialise priority queue
initialise root node with take and leave lists
order items by (value/weight)
calculate upper bound of root
put root node in queue
while queue not empty:
    get queue element with highest priority (highest bound)
    if current node bound < global best:
        end because cant do better
    if current node value > global best:
        update global best
    if current node level < item count
        if weight with new item <= capacity
            create new take list by copying current node take list and setting take[level] = 1
            create new "left" node with new take list and old leave list
        create new leave list by copying current node leave list and setting leave[level] = 1
        create new "right" node with old take list and new leave list

```

The node class is:

```
class node(level, take list, leave list):
    set level as argument
    set lists as argument
    set value by iterating over take list and summing values
    calculate room in bag by capacity - total weight calculated with take list
    set bound by calculating using take and leave lists
    left child = none
    right child = none

```

My question is: would it be more efficient to calculate the take and leave lists by traversing the tree rather than to explicitly store the lists in each node? I thought it might be quicker to store the lists and just update them with every new node, but I am thinking now that it might run into memory problems with large inputs.

Is it not such a bad thing to have to traverse the tree every time I want to calculate the bound and should I worry more about space issues?

# Answer
> 1 votes
It isn't clear if you are asking about time or memory efficiency. If you care more about memory, then it would be best to traverse the tree. If you care more about time, then it would be best to copy and modify both lists at each node. However, there are more than two alternatives. You could store a single number at each node, which identifies the items in the knapsack. For example, the binary number 10110 would denote the first, third, and fourth objects as being in the knapsack.

I don't want to do your homework for you, and you didn't ask me to, but I also recommend considering a more memory efficient DP approach if you haven't already. Good Luck!

---
Tags: algorithms, efficiency, knapsack-problems, branch-and-bound
---


title: Complexity of black box satisfiablty

text:
# Question
Title: Complexity of black box satisfiablty
Say I have a black box $f : 2^n \to 2$ and I want to determine if it is satisfiable. That is, does there exist an input how which it returns true. I am for the purposes of this considering $n$ to be the size of the problem. Perhaps that is a bad assumption to make but it seems a reasonable assumption.

Clearly I can reduce SAT to this problem but can I efficiently reduce this problem to SAT? I couldn't think of an efficient way and it doesn't seem possible due to the black box nature. It clearly lies in EXPTIME because I could just try each input. Further still it lies in PSPACE because the I only need to enumerate the linear space assignments. It does not however appear to be in NP as far as I can tell. I can't seem to figure out if it lies in PH either.

Has the complexity of this problem been studied? If so what complexity class does it lie in?

# Answer
> 4 votes
If it's a black box, you *can't* reduce it to SAT. That's exactly what it means to be a black box: a black box is one where you can feed in any input $x$ you like, and get back $f(x)$, but where you know nothing about the structure of $f$ (for instance, you are not given an algorithm for $f$, you do not know the CNF for $f$, and so forth).

In particular, given only black-box access to $f$, in the worst case, you need $2^n$ queries to the black box to determine whether $f$ is satisfiable: you need to evaluate $f$ on every possible input, in the worst case. Consider any algorithm which makes at most $2^n-1$ queries to the black box. Suppose it got back $0$ as the answer to every query. Then there is some input, say $x'$, which has not been queried. Now the correct answer as to whether $f$ is satisfiable depends upon whether $f(x')=0$ or $f(x')=1$, but the algorithm has no clue which is the case. No matter what the algorithm outputs, an adversary could always pick a $f$ (after the fact) that is consistent with all of the queries made to the black box but that makes the algorithm's output wrong. Therefore, no deterministic algorithm can do better than $2^n$ queries, in the worst case.

It's not in EXPTIME, and it's not in NP, because it is an oracle problem, whereas NP and EXPTIME are for non-oracle problems -- but it is in the analogue of EXPTIME for oracle problems.... and in the analogue of NP for oracle problems, too.

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Finding median weights in all paths of an AVL tree with weighted nodes
I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness")

**Given**: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree has the parameter $w\_i$ (which is an integer)

**The task:** To make an algorithm which returns an array of size $n$ such that in the cell $i$ there is the *median* value of all the $w\_i$ of all the nodes from the root of the AVL to the node $i$.

**Running time:** $O(n\log\log n)$

**My solution:**

* For each node among the $n$ nodes in the AVL, I build a separate AVL containing the $O(\log n)$ nodes(because the depth of each node is $O(\log n)$) on the path to it from the root.
* Each insertion to an AVL takes $O(\log n)$ ($n$ = number of nodes), but number of nodes here is $O(\log n)$, therefore, each insertion takes $O(\log\log n)$, and since there are $n$ nodes, then building the $n$ AVLs takes $O(n\log\log n)$
* Finding the median for each AVL takes $O(\log n)$ (using *Select*) since there are $O(\log n)$ values in the tree. Then, we put in the output array at the cell $i$ the median value which we just found.

Thus, building each AVL and finding the median, is done in $O(\log(n) + \log\log n) = O(\log n)$.

**My Question:** I'm uncertain about step 2 in the described algorithm above: does building the $n$ AVL trees takes actually $O(n\log\log n)$ running time?

# Answer
> 3 votes
Your main AVL tree has $n$ nodes. On each you build a small AVL tree with a nomber of nodes bounded by $\log n$, so that the insertion of each node on the small AVL tree has a cost $\log\log n$ steps. Overall that makes $O(n\log n\log\log n)$ steps, not $O(n\log\log n)$ as stated in your step 2.

# Answer
> 1 votes
Maintaining one AVL tree for the whole process is enough, and more efficient.

* Setup another AVL tree T, initially empty.
* Perform DFS on original AVL tree
    + Insert node to T on entering the node,
    + Delete node from T on leaving the node.
    + Find and record the median after inserting each node.

In the DFS process, T actively maintains all nodes along the path from root to current node, similar to the stack (explicitly or implicitly) maintained in DFS.

The size of T is $O(\log n)$ during the whole process, so each insertion/deletion/query cost $O(\log \log n)$. And each node in original AVL is inserted/deleted/queried exactly once. So the overall complexity is $O(n \log \log n)$.

The maintained AVL tree T can be replaced by other running median data structures. A common data structure min heap + max heap, maintaining the 2 halves partitioned by current median, which can report current median in $O(1)$. (insertion/deletion is still $O(\log n)$)

---
Tags: algorithm-analysis, data-structures, binary-trees, balanced-search-trees
---


title: Who coined the term "machine learning"?

text:
# Question
Title: Who coined the term "machine learning"?
I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as:

> the field of study that gives computers the ability to learn without being explicitly programmed

?

You can find many, many references to this definition on the internet, but I haven't been able to track down the source. Some give it as his 1959 paper on checkers, but I don't find any such definition there.

# Answer
> 6 votes
*"Programming computers to learn from experience should eventually eliminate the need for much of this detailed programming effort"* Samuel, A. L. (1959), “Some Studies in Machine Learning Using the Game of Checkers” in IBM Journal of Research and Development (Volume:3, Issue: 3), p. 210

---
Tags: terminology, reference-request, machine-learning, history
---


# Question
Title: find path in directed graph according to word
I have a tricky problem, look:
$n, \le 100, m\le 1000 $ where $m$ is number of edges and $n$ is number of nodes. On every directed edge there is word $w$ such that $|w| \le 1000$. There is given one word $s$ ($|s|\le 100000$). Our task is asnwer to question: Is there transition in this graph such that we build this word $s$ ?

Look at example: answer: YES

Could you help me ?

# Answer
> 1 votes
Let me explain the basics of the solution without details.

Define $T\[u,i\]$ as "Is it possible to make $s\[1..i\]$ when I am at vertex $u$?".

Obviously for all $u$, $T\[u, 0\] = true$.

If there is an edge from vertex $u$ to vertex $v$ and the word on the edge matches with $s\[i+1..j\]$ and $T\[u, i\] = true$, we can infer that $T\[v, j\]$ is also $true$.

So you can repeatedly do this process and calculate $T$ for all $u$ and $i$. If $T\[x, |s|\] = true$ for some $x$, we can make the word!

---
Tags: graphs
---


# Question
Title: Decidable language: set of context-free langauges containing 1 string
ONE = {(G) : G is a CFG such that L(G) contains exactly one string} .

I know to prove this is decidable I need to create a DTM that would recognize it and HALT on all input. I am struggling at coming up with a high level definition.

My Possible Solution:

On input G, where G is a Context-free grammar, If non-terminal has more then one option that it can lead to, reject. Else accept.

# Answer
> 1 votes
Hint: The point of this exercise is that it is decidable whether a context-free grammar generates the empty language. Using this as a black box, you can proceed as follows. On input $G$:

1. Check if $L(G)$ is empty, and if so, reject.
2. Find a word $w \in L(G)$.
3. Check whether $L(G) \cap (\Sigma^\* \setminus w)$ is empty.

I'll let you figure out how to implement the latter two steps; step 2 uses the fact that it is decidable whether a grammar $G$ generates a given word $x$, and step 3 uses the fact that the intersection of a context-free language and a regular language is context-free (constructively).

The same idea can be used to calculate $L(G)$ given that we know that $L(G)$ is finite.

---
Tags: formal-languages, turing-machines, context-free
---


# Question
Title: What's a side-effect free expression in Timed Automata?
I'm trying to get myself more familiar with Timed Automata theory. At some point I came across the expression "side-effect free" like in the following:

> A guard is a side-effect free expression that evaluates to a boolean.

But except for the following definition¹ I couldn't find any good source that explains what it actually means or gives examples with respect to Timed Automata:

> We call an expression side effect free if (\[!\[e\]!\]) is the identity function.

**EDIT**:

babou pointed me to the global meaning of *side-effect* which is:

Wikipedia on Side effect (computer science)

> In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

However, the trouble I've still got is how to interpret *has no effect on states* for *side-effect free* guards. After a guard has been evaluated it will have an effect on states if a transition is taken. In other words, the result of the guard does matter in respect to changing the state or not. But as it seems, the guard itself is called by a higher (side-effect having) instance which makes the state transition (or not).

---

¹ i.e. searching for the terms *side-effect free Timed Automata*

# Answer
Well, I typed *side-effect* in Google, then I chose anser number 4: Side effect (computer science)

The first sentence states:

> In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

From this definition, using elementary logic, I deduce that a "*side-effect free expression*" is an expression that modifies no state, and has no observable interaction with calling functions or the outside world.

In other words, its evaluation is not supposed to have any observable effect on the program. Then what the program does with the result of the evaluation is another matter and the rest of the program may have an observable behavior that depends on that result. But the effect is the same as if you had been given directly the result rather than evaluating the expression to get it.
> 2 votes

---
Tags: automata, model-checking, software-verification
---


# Question
Title: Regular expression for words in a language where each letter appears at least once
What is a regular expression or finite automaton that will accept words in the alphabet $\\{a,b,c \\}$ where each letter appears at least once?

Acceptable words: $ abc, cba, cbcbcba, abbbcaabb$

Unacceptable words: $aab, babababababa, bbbbbaaaaa$

I would be interested in seeing both the regex and the automaton. Then I can place it into **regexper.com**

---

In Regular expression to show that all strings contain each symbol atleast once we find the regex

$$ (a+b+c)^\*a(a+b+c)^\*b(a+b+c)^\*c $$

The word $cba$ does not fit, and the answer raises questions about the complexity or size.
For kicks, I draw the automaton \[\].

---

**COMMENT** It's not clear to me at all this is a duplicate to the linked question. They talk in general about deciding if

$$ \qquad \displaystyle L' := \\{w \in L: uv = w \text{ for } u \in \Sigma^\* \setminus L \text{ and } v \in \Sigma^+ \\} $$

is a regular language. **None of the answers address my specific case in question.** Looking at notes, my guess the alphabet is $\Sigma = \\{ a,b,c\\}$ and $\Sigma^\ast$ is the free monoid. It's unclear to me what choice of $L$ returns the $L'$ I am looking for.

Or if anyone can show me how this is an intersection, complement or other regular language operation please let me know.

# Answer
A DFA for your language is:

The name of the states are self descriptive.

Following comments from D.W., here is a way to compute such an automaton. It is a bit tedious and error prone by hand, but easy to do by computer with the proper algorithms. These ideas are to be found in this reference question.

You define 3 languages on the alphabet $\Sigma^\*=\\{a,b,c\\}$, $L\_a$, $L\_b$, and $L\_c$, such that each contains all string that have at least one occurrence of the subscript symbol.

For example $L\_a=\\{w\mid |w|\_a\geq 1\\}$

The language you want is $L\_a\cap L\_b \cap L\_c$.

The corresponding finite automata are much easier to define. Then you only have to apply twice the standard crossproduct construction to get the automaton for the intersection.

The advantage of using standard construction is that it spares you the need to prove your result correct (if done by a computer ... I would not trust a human being).

A regular expression is:

$$\begin{align} (\\;\\;\\; (aa^\*b & +bb^\*a)(a+b)^\*c \\ +(bb^\*c & +cc^\*b)(b+c)^\*a \\ +(cc^\*a & +aa^\*c)(c+a)^\*b\\;\\;\\;) \\;\\; (a+b+c)^\* \end{align}$$

You can more or less read it from the DFA. Otherwise, just use the standard algorithms, and good luck.
> 6 votes

---
Tags: regular-languages, finite-automata, regular-expressions
---


# Question
Title: L = {w belongs to {0, 1} * ∣ w has at most three 0’s}. Why is this regular language?
L = {w belongs to {0, 1}\* ∣ w has at most three 0’s}. Why is this regular language?

According to pumping lemma, what I think is that.... Suppose $x$=$0^2$, $y$=$0^1$, $z$=$1^n$ ($w=xyz$=${0^2}{0^1}{1^n}$), then if we pump $y$, we may have more than three $0$s. What am I missing?

# Answer
> 1 votes
As the other answers have said, the key is in the statement of the pumping lemma.

The key to understanding how to apply the pumping (and how not to as well) is paying close attention to the quantifiers ("for all" and "there exists") and the order they come in:

> **The Pumping Lemma for Regular Languages**
>
> If the language $L \subseteq \Sigma^{\ast}$ is regular, then ***there exists*** a constant $p \geq 1$ such that ***for every*** string $s \in L$ where $|s| \geq p$, ***there exists*** a division of $s = xyz$ such that:
>
> 1. $|xy| \leq p$,
> 2. $|y| \geq 1$, and
> 3. for all $i \in \mathbb{N}$, $s' = xy^{i}z \in L$.

So if you wanted to show that a language obeyed the pumping lemma (note that is would not prove that it's regular, there are non-regular languages that can also be pumped), you have to first determine the pumping length $p$, then look at every string $s \in L$ and show that *there is some way* that $s$ can be broken down so that it can be pumped according to the conditions.

So in your case, if we ignore that you don't know $p$, the mistake is showing that *one* way of breaking it up doesn't work. So assuming that the pumping length is at least $4$ (it is, but why...?), then the breakdown $x = 000$, $y = 1$, $z = 1^{n-1}$ can quite happily be pumped.

When this has settled in, it also shows how the proofs of non-regularity via the pumping lemma work. You just have to find one string, but you have to show that there is no workable breakdown for that string.

# Answer
> 0 votes
You can't use the pumping lemma to prove that a language is regular.

The pumping lemma can be used to prove that a language is *not* regular, but it doesn't let you prove that a language *is* regular.

(Why? The pumping lemma says something like "If $L$ is regular then (stuff)." If you prove that (stuff) is false, then you can conclude that $L$ is not regular; that follows from the contrapositive of the pumping lemma. But if you prove that (stuff) is true, you can't conclude anything: $L$ might be regular, or it might not; the pumping lemma makes no promises.)

Instead, to prove that a language is regular, you should use the techniques described in How to prove a language is regular?

# Answer
> 0 votes
We use the pumping lemma to prove that a determinate language is not regular.

If you want to prove that a determinate language $L$ is regular then you have to write a regular expression, draw a NFA or draw a DFA that denotes $L$.

For example I can say that $L=\\{w \in \\{0,1\\}|$ $w$ has at most three 0's $\\}$ is regular because I found the regular expression:

$RE$ = $1^\*(0|\epsilon)1^\*(0|\epsilon)1^\*(0|\epsilon)1^\*$

and $\mathscr{L}(RE)=L$

---
Tags: regular-languages, finite-automata
---


# Question
Title: I want to figure out whether my problem described below is reducible to the set cover problem
I have a collection of non-empty sets $S\_i$, where $1 \le i \le n$, which are constructed from elements of a universe $U$.

I need an algorithm that gives me a set $T$ of minimum cardinality ($T \subseteq U$), such that $T \cap S\_i \ne \phi, \forall i$, where $1 \le i \le n$.

I am not sure whether it is an NP-complete problem and can be reduced to minimum set cover in some way. I thought of reducing it to vertex cover, by taking the sets as vertices, and putting an edge between any two sets if their intersection is non-empty, but that doesn't quite seem to work either.

# Answer
> 2 votes
Hint: For each element $x \in U$, let $A\_x = \\{i : x \in S\_i\\}$. Then $T$ is a solution to your problem iff $\\{A\_x : x \in T\\}$ covers all of $\\{1,\ldots,n\\}$. This problem is known as *minimum hitting set*.

---
Tags: algorithms, reductions, set-cover
---


# Question
Title: A question about the polynomial hierarchy
Why does $\Pi\_i^p \subseteq \Sigma\_i^p$ imply $\Pi\_i^p = \Sigma\_i^p$?

# Answer
Hint: $L \in \Sigma\_i^p$ iff $\overline{L} \in \Pi\_i^p$. (Here $\overline{L}$ is the complement of $L$.)
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Problem in Papadimitriou's "Computational Complexity" seems odd
I am studying (on my own, this is not homework) Papadimitriou's "Computational Complexity" textbook, 1st edition.

On page 66, we have:
3.4.1. Problem: For each of the following problems involving Turing machines determine whether or not it is recursive:

(a) Given a Turing machine $M$, does it halt on the empty string?
(b) Given a Turing machine $M$, is there a string for which is halts?
(c) Given a Turing machine $M$, does it ever write symbol $\sigma$?
(d) Given a Turing machine $M$, does it ever write a symbol different from the symbol currently scanned?
(e) Given a Turing machine $M$, is $L(M)$ empty? ($L(M)$ denotes here the language accepted by the Turing machine, *not* decided by it.)
(f) Given a Turing machine $M$, is $L(M)$ finite?
(g) Given two Turing machines $M$ and $M'$, is $L(M)=L(M')$?
Which of the non-recursive languages above are recursively enumerable?

Now, what puzzles me about this problem is that very little of the information it provides needs to be used in order to solve it. It is easy to see that all seven items describe non-trivial properties of Turing machines (that is, they are true for some Turing machines but not others) and, according to Rice's Theorem described on page 62, this means they cannot be recursive. There is barely any need to think at all about the properties described.

It seems a little odd that the author would go through the trouble of describing several different languages in some detail, when those details barely matter. It makes me wonder if my reasoning about Rice's Theorem is correct.

So my question is: is my reasoning correct that, according to Rice's Theorem, none of these described languages are recursive?

Incidentally, I think the last question in the problem is more interesting and does require more thinking about the individual languages. However, it sounds like a very secondary question, so it still makes me wonder about my answer to the main question.

# Answer
> 2 votes
Rice's theorem is about non-trivial properties of *partial functions*. It states that if $P$ is a non-trivial property of partial functions, then no algorithm can decide, given the description of a Turing machine $M$, whether $L(M) \in P$.

Rice's theorem doesn't say anything about the *operation* of Turing machines. A property like "$M$ ever writes $\sigma$" is not a property of $L(M)$, and so Rice's theorem doesn't apply to it.

---
Tags: complexity-theory, turing-machines, undecidability, semi-decidability
---


# Question
Title: What is an array of arrays called when all arrays have the same size?
If I have an array *a* of arrays, in many languages they may have different size. Is there a word for an array of arrays where all the arrays have the same length?

Edit: An array of arrays may have the following form:

```
[
  [ 1, 2, 3 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2 ]
]

```

But in order to convert this to a matrix you would have to assume some default value or trim the arrays. The following array of arrays is possible to convert into a matrix without any asumptions or trimming as all arrays have same length.

```
[
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
]

```

Is there some name or classifier for a matrix of this kind?

# Answer
> 5 votes
In C# world there are 2 kinds of array declarations, and 2 names for it:

1. Jagged:

```
[
  [ 1, 2, 3 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2 ]
]

```
2. Rectangular:

```
[
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2, 4, 4 ]
]

```

# Answer
> 1 votes
An array of arrays, also known as a multi dimensional array :-)

A Matrix is only one of the structures that can be represented by such an array, when all first level elements are of the same size.

# Answer
> 0 votes
I don't think there is a term for this (a "multidimensional array" may or may not be the same thing) but I'm familiar with a term for the opposite: a "ragged array".

# Answer
> 0 votes
I believe "rectangular array" is the most common term and one people aren't likely to misunderstand.

---
Tags: terminology, data-structures, arrays
---


# Question
Title: Creating a list of minimum-distance pairs from two lists
Let's say there are two lists of objects, list1 and list2, and that there is a function that can generate the "distance" between an object in list1 and an object in list2. What I would like to do is create a list of pairs of objects from each list such that the sum of all the distances of each of the pairs is minimal.

The only method that has occurred to me so far is just a brute force solution of creating a matrix of all the distances between list1 and list2 and then examining the sums of the distances of all possible combinations. Obviously, that approach is rather unappealing. I'm sure that many people have come across a similar problem before but I've been having a hard time phrasing my question in such a way that Google can help me out. Anybody have any ideas?

# Answer
> 2 votes
This seems to be a classical example of bipartite weighted maximum matching, for which there are efficient algorithms (you'll have to convert your minimization objective to a maximization one).

---
Tags: algorithms, lists
---


# Question
Title: Average number of comparisons to locate item in BST
This is a GRE practice question.

If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (nodes) in the tree chosen at random?

(A) 1.75

(B) 2

(C) 2.75

(D) 3

(E) 3.25

My answer was 3 because $n=8$ and $\lg(n)$ comparisons should be made, and $\lg(8) = 3$. But the correct answer is 2.75. Can someone explain the correct answer? Thanks!

# Answer
Recall, how *expected value* is defined. You count the for every element $X$ in the tree the number of comparisons it takes to locate it, say $C(X)$. Then $$E\[\text{# of comparisons}\]=\sum\_{X\in\\{A,\ldots,H\\}} p\_X \cdot C(X),$$ where $p\_x$ denotes the probability that $X$ is chosen, which is the same for all $X$, namely $1/8$. In other words, you compute the average over the $C(X)$s.
> 8 votes

# Answer
Find comparisons for every element and total them ie; 22 comparisions for 8 elements so for 1 element 22/8=2.75
> 0 votes

# Answer
1 node at level 1 {E} 2 node at level 2 {C H} 3 node at level 3 {B D F } 2 node at level 4 {A G} 1\*1+2\*2+3\*3+2\*4=22 22/8=2.75(ANS)
> -2 votes

---
Tags: algorithm-analysis, data-structures, binary-trees, search-trees, average-case
---


# Question
Title: Simple algorithm for listing all 6-cycles in a directed graph
What's an easy-to-program way of listing all 6-cycles in a directed graph? I've done some reading on the general case of even cycles, but it's rather complicated. I found a really neat approach for 4-cycles, in this post, and I was wondering if there's something similar for 6-cycles.

My graph isn't that big (maybe a few hundred nodes) so I'm not too worried about computation time.

# Answer
The easiest-to-program method will probably be a straightforward for-loop. In particular, for each combination of six vertices $v\_1,v\_2,\dots,v\_6 \in V$, check whether the following conditions all hold:

* the $v\_1,v\_2,\dots,v\_6$ are all distinct
* $(v\_1,v\_2) \in E$ and $(v\_2,v\_3) \in E$ and ... and $(v\_5,v\_6) \in E$ and $(v\_6,v\_1) \in E$.

If all the conditions hold, then you've found a cycle. Output it. Repeat for each possible combination of vertices.

The running time of this method is $\Theta(|V|^6)$. It is easy to see that in the worst case there can be $\Theta(|V|^6)$ different cycles (consider a complete graph), so any algorithm will have to take at least this long on some graphs.

---

You can also get a very easy-to-program algorithm with running time $\Theta(|E|^3)$. Enumerate all triples of edges $(v\_1,v\_2), (v\_3,v\_4), (v\_5,v\_6) \in E$, and then check the following conditions:

* the $v\_1,v\_2,\dots,v\_6$ are all distinct
* $(v\_2,v\_3) \in E$ and $(v\_4,v\_5) \in E$ and $(v\_6,v\_1) \in E$.

If all the conditions hold, you've found a cycle; output it

This algorithm has $\Theta(|E|^3)$ running time. Again, it's easy to see that there exist graphs where there are $\Theta(|E|^3)$ cycles and thus any algorithm will need to take at least $\Theta(|E|^3)$ time.

---

Both of those algorithms are easy to program. That doesn't mean they are necessarily optimal in running time. One could hope for an output-sensitive algorithm whose running time is a function of the number of 6-cycles as well as of $|V|,|E|$. I suspect there are more complex algorithms that might have better asymptotic running time, for some graphs, when considering all three of those parameters. However, they will be much more complex to program. Therefore, by your stated goal of "easiest-to-program", I recommend one of the two algorithms listed above.
> 2 votes

---
Tags: graphs
---


title: Collisions in independent hashing

text:
# Question
Title: Collisions in independent hashing
Let $H$ be a $s$-wise independent family of hash functions from $\\{1,\ldots,M\\}$ to $\\{1,\ldots,N\\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?

# Answer
You can upper-bound your probability using a union bound. In particular,

$$\Pr\[\exists x \in S . \phi(x)\] \le \sum\_{x \in S} \Pr\[\phi(x)\].$$

Using a union bound we obtain ${M^s \choose 2}$ terms in the sum, and each term is upper-bounded by $1/N^s$, so we find that your probability is at most

$${M^s \choose 2}/N^s.$$

If $M \< \sqrt{N}$, then this probability will be at most $1/2$. If $M \gg \sqrt{N}$, then this probability is close to $1$.

(Qualitatively, this upper bound is fairly close to tight for a wide range of settings of $M,N$. I am not going to prove this fact, but you can take my word on it. So there's not much hope for a significantly better bound using some other proof technique.)

In short: as Yuval Filmus says, unless $M$ is very small, your event is actually pretty likely.

---

No, something stronger than $s$-independence will not help. Even if you assume that $h$ is generated uniformly at random from the set of all hash functions with the right signature (something that is not actually implementable), you don't get a much better bound.

The only plausible approach I can see is to choose a hash function $h$ that does not have any collisions at all: e.g., choose $h$ from a family of injections, or use a perfect hash. Each of these has serious shortcomings: the former requires $M\<N$, and the latter typically requires you to know in advance the full set of values that you will ever compute $h$ on.
> 3 votes

---
Tags: computability, data-structures, probability-theory, hash, hash-tables
---


title: Compression type that can be searched

text:
# Question
Title: Compression type that can be searched
Is there **ANY** compression type that can compress a file, and then that compressed file can be searched **without** uncompressing the file?

# Answer
> 12 votes
Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space. These are essentially compressed suffix arrays or suffix trees, which have a lot of literature.

Basic substring search can be o(k) or o(k log n) in time for length k, depending on what data structures are chosen (different types of rank/select data structures). There are a range of issues that arise depending on whether one wants simple boolean containment predicates, the offset of each occurrence, or more complicated suffix tree operations; the former can be done in less space and time than the latter.

There's also an entire book about searching and selective decompression of strings: "Compressed Data Structures for Strings: On Searching and Extracting Strings" by Rossano Venturini, published 2014 Springer Science & Business Media.

# Answer
> 3 votes
KWillets mentioned the FM index. It's worth noting that the FM index is based on the Burrows-Wheeler transform (also the basis of bzip), along with an index which supports efficient "rank" queries.

BWT-based indexes are self-indexing, in the sense that the index is also a compressed representation of the source string, and can be decompressed into the original file. The decompression can be performed more quickly by adding a select index along with the rank index. Rank/select indexes are an interesting topic, and are worth checking out. There are some excellent resources for practical implementations.

However, the main point that I want to bring up is this is a special case of the more general idea of compressed data structures. A compressed data structure is one that doesn't need to be decompressed (or the amount of decompression required is bounded) in order to perform efficient operations on it.

Compressed data structures can be further analysed in terms of their overhead relative to a theoretical limit. For example, succinct data structures have a relative overhead which decreases as the data structure grows. This is a very active research area at the moment.

The BWT technique can be applied to data structures other than strings. For example, the same idea has been extended to labelled trees, resulting in a compressed searchable representation.

So if you have data that you need to compress and find stuff in, don't necessarily think in terms of files. Your data may have a higher-level structure that you can exploit.

---
Tags: search-algorithms, strings, data-compression
---


# Question
Title: looking for a strongly NP Complete related problem
I'm looking for a problem that is NP-Complete (even) if the number of input values is at most a polylog of the input size. So some or each value in the input should be so large that the number of values is "negligable".

One way to do this is to say that there is only one input value that should be split and represents the input to another NPC problem. But I consider this a bypass and I'm looking for a more conventional problem.

According to Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded? and its answers, I cannot simply take a strongly NP-Complete problem and represent its input as unary.

# Answer
Wikipedia's list of NP-complete problems lists the following problem:

Input: positive integers $A,B,C$
Question: do there exist positive integers $x,y$ such that $Ax^2+By-C=0$?

This is a NP-complete problem that has only 3 input values (which is certainly at most poly-log of the input size).

---

You can find another example of a NP-complete problem with only 3 input values at A Query regarding Quadratic Residuocity Problem.
> 3 votes

---
Tags: np-complete
---


# Question
Title: Difference between "data dependence graph", "data dependency graph", and "data flow graph"
Is there a difference between a "data dependence graph" and a "data dependency graph"? I have seen both terms - sometimes used interchangeably sometimes not.

To make things even more complicated, a "data dependency graph" is sometimes also called a "data flow graph" (see e.g. here).

The term "data dependence graph" is, for example, used on the second slide here.

If there is a difference, could someone give an example of each graph type? If there is no difference, why the two different terms?

# Answer
> 5 votes
*Dependence* and *dependency* are interchangeable terms. In my experience, *dependency* (with a "y") is more common. In my own writing I try to consistently use *dependence* (without a "y") for aesthetic reasons (I think it sounds better). If you look at a dictionary you'll see that the two words are *almost* synonyms. The only difference I'm aware of is that *dependency* (with a "y") means something specific in the field of political science (it means a territory that is controlled, or owned, by some other sovereign state.) (This leads to my aesthetic dislike: the political dependency relation is asymmetric, while the dependence relation we use in program analysis is not.)

There are lots of minor variations between dependence graphs. The dependences can be *must* dependences ("*a* always depends on *b*") or *may* dependences ("*a* could depend on *b*"). The graph might show *control dependences* in addition to data dependences (in which case it will be called a *program dependence graph*, and almost certainly will not be called a *data-flow graph*). The dependence graph might or might not be superimposed on top of a *control-flow graph*.

Whether something is called a *dependenc(e/y)* graph or *data-flow* graph is pretty much also a matter of taste. I try to avoid *data-flow graph* in my own writing, unless I am specifically talking about someone else's research and they have used the term *data-flow graph*. (In particular, research on Dataflow computer architectures.)

---
Tags: terminology, programming-languages, data-flow-analysis
---


# Question
Title: Is there a formal term for functions that have static state across executions?
Two examples, one in PHP:

```
function adder($i){
  static $a = 0;
  $a += $i;
  return $a;
}

```

A similar effect can be achieved with closures in javascript:

```
var adder = (function(){
  var a = 0;
  return function(i){
    a += i;
    return a;
  }
})();

```

In javascript I've really just created an object. Implementation details not withstanding, does stateful-functions have a formal name?

# Answer
> 3 votes
Not that I know of, but "stateful function" is reasonably descriptive. In informal conversation, that's what I'd use, as long as I suspect the audience will understand what I mean. In formal writing, I might still use the same phrase but also provide a careful definition of what I meant by that phrase. Really, that's a large part of what "formal" writing is about: it's about being precise about what you mean.

# Answer
> 1 votes
In the realm of functional programing, functions that give the same result when called with the same arguments are usually called *pure*.

The Wikipedia page explicitly adds the condition that mutable variables should not be modified by the function call, though presumably they mean mutable variables **that can be observed outside of the function scope** which shouldn't be the case for the variable `a` in your adder function (in a sane language).

This would make the result of `adder` an *impure* function, though that might have some negative connotation.

---
Tags: programming-languages, functional-programming, variable-binding, imperative-programming, design-patterns
---


# Question
Title: What is a bicriteria approximation algorithm?
What is a bicriteria approximation algorithm? This keeps coming up in the case of data stream clustering. Is this related to multi-objective optimization?

This is where I came across it: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. The paper is about a streaming version of the k-means algorithm. There are references in the paper but none of them give an explanation as to what a bicriteria approximation algorithm is. I cannot seem to find anything on Google that will give me a precise definition either.

# Answer
> 11 votes
I'll expand on the answer by Yuval Filmus by providing an interpretation based on multi-objective optimization problems.

## Single-objective optimization and approximation

In computer science we often study optimization problems with a single objective (for example, minimize *f*(*x*) subject to some constraint). When proving, say, NP-completeness, it is common to consider the corresponding *budget problem*. For example, in the maximum clique problem, the objective is to maximize the cardinality of the clique, and the budget problem is the problem of deciding whether there is a clique of size at least *k*, where *k* is given as part of the input to the problem.

When it is not possible to compute an optimal solution efficiently, as in the case of the maximum clique problem, we seek an *approximation algorithm*, a function that outputs a solution within a multiplicative factor of an optimal solution. You could also consider an approximation algorithm for the budget problem, a function that outputs a solution that satisfies *f*(*x*) ≥ *ck* in the case of a maximization problem, where *c* is a number less than one. In this situation, the solution may violate the hard constraint *f*(*x*) ≥ *k*, but the "severity" of the violation is bounded by *c*.

## Multi-objective optimization and bi-criterion approximation

In some cases, you may want to optimize two objectives simultaneously. For a rough example, I may want to maximize my "revenue" while minimizing my "cost". In such a situation, there is no single optimal value, as there is a tradeoff between the two objectives; for more information, see the Wikipedia article on Pareto efficiency.

One way of turning a two-objective optimization problem into a single-objective optimization problem (for which we can reason about the optimal value of the objective function) is to consider the two *constraint problems*, one for each objective. If the problem is to simultaneously maximize *f*(*x*) while minimizing *g*(*x*), the first constraint problem is to minimize *g*(*x*) subject to the constraint *f*(*x*) ≥ *k*, where *k* is given as part of the input to this single-objective optimization problem. The second constraint problem is defined similarly.

An (*α*, *β*)-*bicriteria approximation algorithm* for the first constraint problem is a function that takes a budget parameter *k* as input and outputs a solution *x* such that

* $f(x) \geq \alpha k$,
* $g(x) \leq \beta g(x^\*)$,

where $x^\*$ is a solution that achieves the optimal value for *g*. A bicriteria approximation algorithm for the second constraint problem outputs a solution such that

* $f(x) \geq \alpha f(x^\*)$,
* $g(x) \leq \beta \ell$,

In other words, the bicriteria approximation algorithm is simultaneously an appoximation for the budget problem in the first objective and the optimization problem in the second objective. (This definition was adapted from page four of "Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints", by Iyer and Bilmes, 2013.)

The inequalities switch directions when the objectives switch from maximum to minimum or vice versa.

# Answer
> 8 votes
Often, an optimization problem involves several parameters. For example, consider the problem of graph partitioning. Given a weighted graph, an integer $k$, and a parameter $\rho$, we want to partition the vertex set into $k$ parts $V\_1,\ldots,V\_k$ of size at most $\rho$ while minimizing the number of cut edges $E(V\_1,\ldots,V\_k)$ (edges connecting vertices belonging to different parts). Notice that there are two parameters here: $\rho$ and the number of cut edges.

For $f(n),g(n) \geq 1$, a $f(n),g(n)$ bicriteria approximation algorithm would output a partition $V\_1,\ldots,V\_k$ where each part is of size at most $f(n)\rho$, and the number of cut edges is at most $g(n)\mathrm{OPT}$, where $\mathrm{OPT}$ is the optimal number of cut edges *in the original problem*, with the parts constrained to be at size at most $\rho$.

In other words, a bicriteria approximation algorithm achieves a certain approximation ratio while violating some constraint by some bounded amount. For an example of a bicriteria approximation algorithm for the problem just described, see this paper by the Makarychev brothers.

---
Tags: optimization, approximation
---


# Question
Title: Find the number of values between i & j(given as input) in an unsorted array in O(1) time
Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j$, can we find the number of values $i\<k\<j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement is that the preprocessing should be $O(n)$ in both time and space.

I tried calculating an auxiliary array $B$ of size $M$ (where M is the maximum value in $A$) where $B\[i\]$ stores the number of elements smaller than $i$ in the given array. But for this the time and space complexities would be of order $O(M)$. Can one do better than that?

# Answer
No. If you could do that, then you could sort in $O(n)$ time, which seems unlikely to be possible (except in special cases, like where $M=O(n)$).

The sorting algorithm would be:

1. Preprocess $A$.
2. Let $t$ be the index of the smallest element in $A$. Let $i := A\[t\]$. Set $B\[0\] := t$.
3. For $u := 0,1,2,\dots,n-1$:

* Let $j := A\[u\]$. If $u \ne t$: Count the number of array elements $k$ that satisfy $i \< k \< j$; call this number $m$, and set $B\[m+1\] := j$.
4. Output $B$.

The running time of this algorithm is $O(n)$. Also, $B$ is a sorted version of $A$: in each step of the for-loop, you find the index where element $j$ belongs, and put it in that place of $B$. The $O(1)$-time query lets you figure out the location where $j$ belongs in $O(1)$ time.
> 2 votes

# Answer
In $A$, $rank( A\[i\] ) = \left\vert\left\\{ j \in A : -\infty \< j \< A\[i\] \right\\}\right\vert $

So you could sort the array by putting each element at its rank (up to duplicates, which can also be counted with 2 range queries), so if you could answer queries like this in $O(1)$ time and $O(n)$ preprocessing time and space, you would have an $O(n)$ sorting algorithm.

The latter does exist of course, but only under certain constraints, eg on the range of values.
> 2 votes

---
Tags: algorithms, search-algorithms, arrays
---


# Question
Title: Uniform random number generation from random bits
I need to generate random number in a given interval using random bits. For example, If I want to generate a random number between 1 to 6, inclusive, I can concatenate three random bits which gives me a possible range of 000 to 111 (0 to 7), inclusive. My intuition says after concatenating 3 random bits, if the result falls between 000 and 101, inclusive, I can just return that number plus 1 (which essentially gives me a number between 1 and 6, inclusive). If I get 110 or 111 (6 or 7) after concatenating 3 random bits, I can retry again until I the number generated is in my desired range. How can I prove (or disprove) that the number I returned is indeed random?

# Answer
First we need reduce our `rand(from, to)` function just to `rand(n) = returns uniformly random number from [0, n)`; and later we will be able construct original function as `rand(from, to) = rand(to - from) + to`.

> $rand(n)=$
>
> 1. Take $k$ random bits such where $n \le 2 ^ k$ (actually we can choose any $k$ that satisfy this condition, but in practice make sense to choose minimal among all possible $k$) and interpret this sequence as binary integer $r$.
> 2. If $r \< n$ return $r$ else go to step 1.

Now let's calculate probability that some number $r$ will be choosen:

1. Probability that algorithm will stop after one iteration is $\frac{n}{m}$, probability that we will reach 2nd iteration is $\frac{m-n}{m}$; more generally probability that algorithm will reach $step$ interation is $Pr(step) = (\frac{m-n}{m}) ^ {step - 1}$.
2. Probabilities that algorithm will return some $r$ on 1st iteration:

$ Pr(0) = \frac{1}{m}\\ Pr(1) = \frac{1}{m}\\ Pr(2) = \frac{1}{m}\\ ...\\ Pr(n - 1) = \frac{1}{m}\\ $

3. Probabilities that algorithm will return some $r$ on 2nd iteration:

$ Pr(0) = \frac{m-n}{m}\*\frac{1}{m}\\ Pr(1) = \frac{m-n}{m}\*\frac{1}{m}\\ Pr(2) = \frac{m-n}{m}\*\frac{1}{m}\\ ...\\ Pr(n - 1) = \frac{m-n}{m}\*\frac{1}{m}\\ $

4. Probabilities that algorithm will return some $r$ on $step$ iteration:

$ Pr(0) = (\frac{m-n}{m}) ^ {step - 1}\*\frac{1}{m}\\ Pr(1) = (\frac{m-n}{m}) ^ {step - 1}\*\frac{1}{m}\\ Pr(2) = (\frac{m-n}{m}) ^ {step - 1}\*\frac{1}{m}\\ ...\\ Pr(n - 1) = (\frac{m-n}{m}) ^ {step - 1}\*\frac{1}{m}\\ $

5. And probability that some $r$ will be choosen (after any number of interations) will be the same regardless of $r$:

$ Pr(r) = \frac{1}{m} + \frac{m-n}{m}\*\frac{1}{m} + ... + (\frac{m-n}{m}) ^ s\*\frac{1}{m} + ... = \frac{1}{m}\sum\limits\_{s=0}^\infty(\frac{m-n}{m}) ^ s = \frac{1}{m} \frac{1}{1 - \frac{m - n}{m}} = \frac{1}{m} \frac{m}{n} = \frac{1}{n} $
> 3 votes

---
Tags: random-number-generator
---


# Question
Title: About graphs whose edge set decomposes into perfect matchings
Is there a characterization of graphs whose edge set decomposes into a disjoint union of perfect matchings?

---

One trivial class of such graphs are $d$-regular $(n,n)$-bipartite graphs. Their edge set will decompose into $d$ disjoint perfect matchings.

# Answer
> 6 votes
Yes: we call such graphs 1-factorable (a 1-factor is also known as a perfect matching). All such graphs are regular, but the converse is not true. In fact, a $d$-regular graph $G$ is 1-factorable if and only if it is of class one, that is, $\chi'(G) = d$, where $\chi'(G)$ is the chromatic index of $G$.

Deciding if a $d$-regular graph is of class 1 is NP-complete (see e.g. \[1\]), so you likely cannot test this efficiently.

---

\[1\] Leven, Daniel, and Zvi Galil. "NP completeness of finding the chromatic index of regular graphs." Journal of Algorithms 4.1 (1983): 35-44.

---
Tags: graphs
---