Can QBF encode #QBF? In another question Initializing non-deterministic variables in QBF, I was interested about translating assertion-based pseudocode to QBF in order to have an exponentially more compact encoding compared to unrolling deeply nested loops into SAT.

While some misunderstandings in the pseudocode for that question ultimately led to several answers adding in 'cheating' simplifications not in the spirit of the original question, D.W. clarified that a full answer depends on the relationship between PSPACE and #PSPACE.

Formally PSPACE and #PSPACE are "incompatible" for comparison in a sense of being a decision problem versus a counting problem, but this artifact can be made consistent in analogy to PH versus #P. Decision classes such as PP and ⊕P find the most-significant bit of the #P counting problem and least-significant bit respectively. Reductions filling in the rest of the bits of #P output should be rather straightforward given a powerful PSPACE-complete oracle, since P#P ⊂ PH ⊂ PSPACE.

Looking at the following assertion pseudocode, it's obvious that counting solutions to either SAT (#SAT) or QBF (#QBF) is trivially possible using polynomial-space. For example, the following pseudocode would naively run in exponential time, but never uses more than a linear O(n) amount of memory. This renders, via abuse of notation, #PSPACE ⊂ PSPACE.

counter = 0
for loop_aux_0 in {0,1}:
  for loop_aux_1 in {0,1}:
    for loop_aux_2 in {0,1}:
      .
        .
          .
            for loop_aux_n in {0,1}:
              counter += f(loop_aux_0, loop_aux_1, .., loop_aux_n)
assert(counter != UINT_MAX)

Here f is an arbitrary PSPACE function that outputs 0 or 1.

If there are no objections that #PSPACE ⊂ PSPACE, how can I actually encode #QBF as part of a QBF instance?

I suggested a QBF implementation (although missing initialization) utilizing an adder circuit for counter with its output fed back in as input alongside f_ouput being the carry-in of the LSB:

∃ counter[n] ∀ loop_aux[n] ∃ f_output[1] (counter += f_output) & (f_output == f(loop_aux_0, loop_aux_1, .., loop_aux_n))

The problem with this encoding is that the counter is incremented non-deterministically without initialization, rendering any value of counter satisfiable. Can this encoding be saved with additional clauses or auxiliary variables to initialize the counter? Or is there a better way to encode #QBF in QBF?

Strictly speaking, this is a category confusion: it's an apples-vs-pears comparison.  You can't compare SAT to #SAT; SAT is a decision problem (determine whether a formula $\varphi$ has a satisfying instance), #SAT is a counting problem (count the number of satisfying assignments to $\varphi$).  They have a different API: they both take a formula $\varphi$ as input, but SAT outputs either "satisfiable" or "not satisfiable", while #SAT outputs a number.  They're not the same, and you can't encode a #SAT instance as a SAT instance.

The same is true for counting the number of values of $x$ that satisfy a formula $\varphi(x)$, where $\varphi$ contains nested quantifiers (e.g., $\varphi(x) = \exists y . \forall z . \psi(x,y,z)$ or something).  It's a category error: one is a decision problem, the other is a counting problem.

However, you might be interested in the following paper:

Richard E. Ladner.  Polynomial Space Counting Problems.  SIAM Journal of Computing, vol 18 no 6, pp.1087--1097, December 1989.

See, for instance, the discussion of $\natural$QBF, $\natural$PSPACE, and FPSPACE(poly).

Definitions:

$\natural$QBF is the following problem: given a QBF instance like $\varphi(x,y,z) = \exists x \forall y \exists z \psi(x,y,z)$, count the number of values $x$ such that $\forall y \exists z \psi(x,y,z)$ is true (except that is for an arbitrary number of quantifiers, not limited to just 3).
A function $f:\{0,1\}^* \to \mathbb{N}$ is in $\natural$PSPACE if there's a polynomial-space nondeterministic Turing machine $x$ such that $f(x)$ counts the number of accepting computations of $M$ on input $x$, and $M$ makes only a polynomial number of nondeterministic choices.
A function $f:\{0,1\}^* \to \mathbb{N}$ is in FPSPACE(poly) if $f(x)$ is bounded by a polynomial in the length of $x$ and there's a deterministic polynomial-space algorithm (Turing machine) that computes $f$.

The paper proves that $\natural$PSPACE = FPSPACE(poly) and that $\natural$QBF is complete for $\natural$PSPACE and that there is a polynomial-space algorithm for computing $\natural$QBF.

We could consider the following problem:

BIT_OF_COUNT:
Input: an index $i$ and a QBF instance $\varphi$
Desired output: the $i$th bit of the solution to this QBF instance.

This is one way to build a decision problem associated with a $\natural$QBF instance.

By the above remarks, BIT_OF_COUNT is in FPSPACE(poly) (since $\natural$QBF is).  Since its output is in 0 or 1, that means BIT_OF_COUNT is actually in PSPACE.  Since QBF is complete for PSPACE, that it must be possible to reduce BIT_OF_COUNT to QBF, i.e., to translate an instance for BIT_OF_COUNT into an instance for QBF, by chaining all the reductions.

It sounds like this might be what you want.  So, if you study that paper and chain all the reductions together, you might get what you want.  It looks a bit intimidating on first glance, but perhaps if you understand the meat of the reductions you'll be able to simplify somehow.  The key trick in the paper seems to be the one used on pages 1091--1092, using ann algorithm to compute the product or sum of two $b$-bit numbers in $O(\lg b)$ space as a subroutine.

I hope someone will be able to give you a better answer.


Can the effective branching factor be negative? I've implemented A* algorithm in Python, after that I calculated the effective branching factor $ B^* $

$$ T+1=1+B^*+(B^*)^2+\dots +(B^*)^L$$

where $T$ is the number of expanded nodes.

My question is: is it possible in theory that the effective branching factor calculated is negative? And if not possible, is the solution to take only positive root?

I don't know what effective branching factor is, but let me make a few comments anyway:

Presumably the effective branching factor is a parameter such that if the branching factor is constant, then it should equal the effective branching factor. It is some kind of average branching factor. Under this interpretation, a negative branching factor makes no sense.
You should focus on understanding what the effective branching factor is before calculating it. It is pointless to calculate something whose significance you don't understand. In real life you don't just "plug and chug" – you have a goal in mind. In this case, presumably the goal in mind is to estimate how difficult the problem is – the larger the effective branching factor is, the shallower you can afford to explore the corresponding tree. You estimate the effective branching factor in order to estimate how deep you can go, and in order to compare the difficulty of various problems. The formula itself is less important.
As $B^*$ increases monotonically from $0$ to infinity, so $1+B^*+\cdots+(B^*)^L$ increases from $1$ to infinity. Therefore your equation has a unique positive root (assuming $T > 0$).
If $B^*$ is "large", then you can estimate $1+\cdots+(B^*)^L$ by just the last term $(B^*)^L$, and so roughly speaking, $B^* \approx T^{1/L}$. You can use this estimate as a basis for an iterative algorithm for calculating $B^*$. The formula for the sum of a geometric series might be useful here.


single tape NTM to single tape DTM equivalence I am having some trouble understanding the equivalence of DTM's and NTM's.
If you have Sipser its under 7.11; where he says that any NTM $N$ that halts after $t(n)$ steps has an equivalent DTM $D$ that halts after $2^{O(t(n))}$
steps.

He says that  $N$ 's "computation tree" has at most $b^{t(n)}$ leaves, where $b$ is the maximum number of choices a transition can have in $N$, and the tree is at most $t(n)$ "levels deep", since $N$ halts after $t(n)$ steps per definition.

Now if one would like to simulate $N$ with $D$ you would have to go through no more than $t(n)b^{t(n)}$ steps to halt.

Then Sipser says that $O(t(n)b^{t(n)})= 2^{O(t(n))}$ which I dont understand.

In my understanding the runtime of $D$ should be $O(b^{t(n)})$ where $b >0$.

Can someone clear this up for me ?

Relevant pages in Sipser are  255-256.

The claim is that for constant $b$, if $f = O(t(n) b^{t(n)})$ then $f = 2^{O(t(n))}$. Indeed, $xb^x \leq b(b+1)^x$, and so
$$
Ct(n) b^{t(n)} \leq Cb (1+b)^{t(n)} = 2^{\log_2(1+b) \cdot t(n) + \log_2 b + \log_2 C}.
$$
From here it's not hard to check that $f = O(t(n)b^{t(n)})$ implies $f = 2^{O(t(n))}$.


$\log^*(n)$ runtime analysis So I know that $\log^*$ means iterated logarithm, so $\log^*(3)$ = $(\log\log\log\log...)$ until $n \leq 1$.

I'm trying to solve the following:

is

  $\log^*(2^{2^n})$

little $o$, little $\omega$, or $\Theta$ of

  ${\log^*(n)}^2$

In terms of the interior functions, $\log^*(2^{2^n})$ is much bigger than $\log^*(n)$, but squaring the $\log^*(n)$ is throwing me off.

I know that $\log(n)^2$ is $O(n)$, but I don't think that property holds for the iterative logarithm.

I tried applying the master method, but I'm having trouble with the properties of a $\log^*(n)$ function. I tried setting n to be max (i.e. $n = 5$), but this didn't really simplify the problem.

Does anyone have any tips as to how I should approach this?

Recall that for $k > 1$, by definition we have $\log^*k = \log^*(\log{k}) + 1$.

By applying the definition twice, we see that $\log^*(2^{2^n}) = \log^*n + 2$.  Now we can compare $\log^*n + 2$ and $(\log^*n)^2$.


Question on the definition of computable function and non-terminating behaviour For example on wikipedia a function $f : \mathbb N^k \to \mathbb N$ is defined to be computable, if there exists an algorithm (in form of a Turing machine, as an $\mu$-recursive function or maybe a C++ programm) such that the following holds:

If $f(x)$ is defined, then the program will terminate on the input $x$ with the value $f(x)$ stored in the computer memory
If $f(x)$ is undefined, then the program never terminates on the input x.

My question concerns the second item, the requirement that for elements $x \notin \operatorname{dom}(f)$ we require the program to end up in an endless loop. But more natural to me would be simply to leave the behaviour unspecified in this case (i.e. just require item 1).

Like for example consider the following quite artificial function:
$$
 f(n) := \left\{ \begin{array}{ll}
  n^2 & \mbox{ if } n \equiv 0 \pmod{2} \\
  \mbox{undefined} & \mbox{ otherwise }.
 \end{array}\right.
$$
Then intuitively I would say some programming squaring its argument would compute $f : \mathbb N \to \mathbb N$, but not to the above definition as this programm would also give a result on all $n \notin \operatorname{dom}(f)$.

From a theoretical point of view this could be fixed if $\mbox{dom}(f)$
is decidable (or semi-decidable, in which case the infinite loop would be given by definition that each query $x \in \operatorname{dom}(f)$ should end up in an infinite loop by the definition of semi-decidable), as we simply
query if the argument is in $\operatorname{dom}(f)$, and if yes proceed with our algorithm, and if not just enter some idle endless loop.

From another point of view discarding item two above would be easier in proofs, as the case if $f(x)$ is undefined does not needs to be considered. But I can image that someone wants a relationship that the algorithms terminates exactly if $f$ is defined. But does this makes any difference? What would be lost if we just use item one above as the defintion of computability, i.e. $f : \mathbb N^k \to \mathbb N$ is computable, iff there exists an algorithm that computes the correct result if $f(x)$ is defined.

The short answer is that: this part of Wikipedia's explanation kinda sucks.  Hey, it happens.  Wikipedia is pretty good, but it's not perfect.

The relevant part of the Wikipedia article says:

  Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a Turing machine or a register machine. Formally speaking, a partial function $f : \mathbb{N}^k \to \mathbb{N}$ can be calculated if and only if there exists a computer program with the following properties:

  If $f(x)$ is defined, then the program will terminate on the input $x$ with the value $f(x)$ stored in the computer memory.
  If $f(x)$ is undefined, then the program never terminates on the input $x$.

The second sentence is not strictly wrong (that sentence does say that "a partial function can be calculated if...") but it sure seems misleading to include that sentence in an article on computable functions, as computable functions are required to be total functions.  Also, the combination of those two sentences leaves the wrong impression as it omits the requirement that $f$ be a total function.

Advice: if you're reading something in Wikipedia that seems confusing or doesn't seem quite right, check another source.  Check a good textbook -- they are a more definitive source for the precise definition of mathematical concepts.


Why we still need Short Term Memory if Long Term Memory can save temporary data? If RAM is a short term memory and SSD is a long term memory, why don't microarchitecture of computer nowadays use SSD or another long term memory for saving temporary data like hidden variable for programming?
If it's about speed, then SSD can improve its speed, is it possible that SSD will become faster than RAM at some point?
If SSD has address for memory location and data for
opcode/instruction/operand like RAM, then will it possibly act like RAM?

There's two simple reasons, one fundamental and one related to our current technology. First the technical one: volatile storage is (generally) faster than non-volatile storage. It has fewer requirements - it only needs to store the data for a short while until it gets refreshed, so it's not a surprise that it often is faster.
But the fundamental reason is that memory gets slower to access the bigger it is. This is why modern architectures don't just have 'RAM' and 'disk', there's layers upon layers of increasing size memory, with only the topmost layer being non-volatile:

CPU registers
L1 cache
L2 cache
L3 cache
RAM itself
Cache on the disk micro-controller
The disk itself


The stability of log(1+x) I am trying to understand why the formula

$$ \frac{\log(1+x)}{(1+x)-1} \times x,$$

which simply reduces down to $\log(1+x)$, is considered as more stable to compute than $\log(1+x)$.  In my head it doesn't make sense to me as my brain automatically simplifies it to $\log(1+x)$, which I am guessing a computer doesn't do, but then why does adding in "extra" calculations make it more stable for the computer?  My intuition would have been the opposite, the more calculations performed, the more error is introduced.  Why is this not the case here?

Consider the case that x is small. (1 + x) has a rounding error; the result that you get is not (1 + x) but (1 + x') for some x' close to x. If x is very small, the relative difference between x' and x can be quite large. Trying to calculate log (1 + x) will calculate log (1 + x') which can have a large relative error. Instead the better formula calculates log (1 + x') / x' * x.

You can just enter both formulas into a spreadsheet and compare with the Taylor polynomial ln (1 + x) = $x - x^2/2 + x^3/3 - x^4/4...$.

Note that it is easy to calculate ln (z) with very high precision when z is close to 1. The damage is done when 1+x is calculated with a small absolute rounding error which turns into a huge relative error, and that's what the modified formula compensates for.


Hardness of FNP vs Choice of Verifiers A (T)FNP problem is induced by a NP language, say $L$. Usually in the notion of verifers, we define $L=\{x:\exists y,V(x,y)=1\}$, where $V$ is a poly-time verifier. The function version would be finding the certificate $y$ (if exist).

However, the choice of verifier could be arbitrary, for example, the verifier for $HAM-PATH$ problem could be

Determinig whether the computation path of TM configurations is valid and reaches accepting state. (The Cook-Levin way).
Determine whether a path of input graph is Hamiltonian. (The natural way)

In order to make this definition "natural", we should probably show that, undere these different choice of verifier, the definition remains equivalent, i.e. the problem do not suddenly become harder/easier just because we introduce a different verifier.

  So here's my question:
  Is the choice of verifier independent with hardness of its functional
  problem? How do we justify this?

No (unless $P=NP$).  Consider a language $L$ that is in $P$, say, $L$ is the language of prime numbers.

Suppose $V_1$ works as follows: $V_1(x,y_1)$ ignores $y_1$ and checks directly whether $x$ is prime, and if so, outputs 1; otherwise it outputs 0.

Suppose $V_2$ works as follows: $V_2(x,y_2)$ interprets $x$ as a 3CNF formula and checks whether $y_2$ is a satisfying assignment for it; then it checks whether $x$ is prime; and if both are true, it outputs 1, otherwise it outputs 0.

Both verifiers define the same language, namely, $L$.

However, given $x$, the problem of finding $y_1$ that's accepted by $V_1$ can be solved in polynomial time; but the problem of finding $y_2$ that's accepted by $V_2$ is NP-hard.  So, assuming $P \ne NP$, those two function problems have different hardness.


Turing machine halting in at least 100 steps on all inputs L = {< M >  $\mid$ L(M) = M halts on all inputs in atleast 100 steps }.

Answer to this question is given undecidable in my book without any explanation but I think it is decidable.

$\overline{L}$ =  {< M > $\mid$ L(M) = M halts on some input in atmost 100 steps }

For the above language, we can feed strings of length ranging from 1-100 (finite amount of strings)  and run Turing machine for finite amount of steps (100) on each string and check if at least one of them halts in atmost 100 steps.

So, as the complement of L is recursive, L should also be recursive and decidable according to me.

Where am I going wrong ?

You have not correctly computed $\overline{L}$. It contains

machines which halt in less than 100 steps for some input (which is a finite set of possibilities, as you say), and
machines which don't ever halt for some input.

The second part requires a solution to the halting problem, so $\overline{L}$ is not decidable (nor recursively enumerable).


How to represent the interests of a Facebook user I'm trying to figure out a way I could represent a Facebook user as a vector. I decided to go with stacking the different attributes/parameters of the user into one big vector (i.e. age is a vector of size 100, where 100 is the maximum age you can have, if you are lets say 50, the first 50 values of the vector would be 1 just like a thermometer).

Now I want to represent the Facebook interests as a vector too, and I just can't figure out a way. They are a collection of words and the space that represents all the words is huge, I can't go for a model like a bag of words or something similar. How should I proceed? I'm still new to this, any reference would be highly appreciated.

The interests are categorical data and may be modeled as binary variables (a user either likes them or he does not). You can subsume little-used categories under broader categories. For example, a user who likes a little-known horror movie can simply be marked as liking horror movies. You can even subsume such items under multiple categories if it belongs to several.

For what you can do with the data see A Review on Data Clustering Algorithms for Mixed Data


Show that every infinite language has a non-regular subset I'm trying to solve this problem:

  Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular

But can this be correct? If I have the language $\{a\}^*$ for example, that's infinite but you can make a DFA for any sub-language of it, right?

There's a hint that this can be proved using diagonalization, but I think I must be misunderstanding the question.

The powerset of the language contains all the sublanguages. This will be uncountably infinite, but there are only countably many regular languages (for a particular, finite alphabet)


Regular language not accepted by DFA having at most three states Describe a regular language that cannot be accepted by any DFA that has only three states.

I'm not really sure where to start on this and was wondering if someone could give me some tips or advice. I understand that the pumping lemma can be used to prove a language is not regular, but in this case, it should be a regular language. If anyone has any thoughts it would be appreciated.

The pumping lemma can be stated to take into account the number of states in the DFA. Every language $L$ accepted by a DFA with $p$ states satisfies the following pumping lemma:

  Each word $w$ of length at least $p$ can be broken up as $w=xyz$, where $|xy| \leq p$ and $|y| \geq 1$, such that $xy^iz \in L$ for all $i \geq 0$.

You can use this characterization to prove that the language $\{0^p\}$ requires $p+1$ states.

Another method is to use the Myhill--Nerode theorem. Two words $x,y$ are inequivalent (with respect to some language $L$) if for some word $z$, either $xz \in L$ and $yz \notin L$ or the other way around. The Myhill--Nerode theorem states that if there are $p$ pairwise inequivalent words, then every DFA for $L$ has at least $p$ states. For the example $L = \{0^p\}$, you can find $p+1$ pairwise inequivalent words, namely $\epsilon,0,\ldots,0^p$.


Understanding the union of an undecidable language with a finite or decidable language I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable.
This is confusing me because if $L$ were to be a semi-decidable language, then this would be easy to prove (with either pseudocode or TMs), but as I understand not all undecidable languages are semi-decidable, and I don't know what to do with those ones.

If $L$ is undedidable and $A$ is finite, then $L \cup A$ is undecidable.
To see this notice that, given $w \in \Sigma^*$:
$$w \in L \iff (w \in L \cap A) \; \vee \; (w \in L \cup A \;\wedge\; w\not\in A).$$
Since $A$ if finite both $A$ and $L \cap A$ (which is also finite) are decidable. That is, we can test whether $w \in L \cap A$ and whether $w \not\in A$.
If $L \cup A$ were decidable the above formula would then imply that $L$ must also be decidable, a contradiction.
If $L$ is undedidable and $B$ is decidable, then $L \cup B$ might or might not be undecidable, depending on $B$.
An example in which $L \cup B$ is undecidable is the one discussed before: let $B$ be any finite language, e.g., $B=\emptyset$.
An example in which $L \cup B$ is decidable is $B=\Sigma^*$ since $L \cup B = \Sigma^*$.


Shortest path in BST Given a Binary Search Tree and two elements $e1$ and $e2$ which are in the tree, find the length of the shorted path between them. Give the representation of the Binary Search Tree(use a linked representation with dynamic allocation without an attribute for parent or height). Implement the required operation and specify its complexity. Hint: try to find first the Least Common Ancestor of the nodes, the first node which is an ancestor for both nodes.

I thought that for finding the Least Common Ancestor we have to make a preorder traversal for example having the while loop : $while(!(e_1<a == e_2 < a))$, but I don't know how to count the length between them.
How should I count them?

There is a unique shortest path $P_T(u,v)$ between two nodes $u$ and $v$ in a tree $T$. Such a shortest path goes from $u$ to the lowest common ancestor (LCA) $z$ of $u$ and $v$ in $T$, and then goes from $z$ to $v$. Notice that it might be possible for $z$ to coincide with $u$ or $v$.

To find the length $d_T(u,v)$ of $P_T(u,v)$ is therefore sufficient to find the LCA $z$ of $u$ and $v$ in $T$.

There are several ways to do this. One straightforward way that requires time $O(n)$, where $n$ is the number of nodes of $T$, is the following:

Initially all the vertices of $T$ are unmarked.
Start from $u$ and iteratively walk towards the root of $T$. Mark all the encountered vertices.
Start from $v$ and iteratively walk towards the root of $T$. The LCA of $u$
and $v$ is the first marked vertex encountered during this walk.

An easy way to reduce the running time to $O(d_T(u,v))$ is that of alternating the steps of the walk from $u$ with those of the walk from $v$. Assume that $u \neq v$ (otherwise the answer is trivial) and do the following:

Initially all the vertices of $T$ are unmarked except for $u$ and $v$.
Let $p_u = u$, and $p_v = v$.
Repeat the following:

If $p_u$ is not the root of $T$:

Move $p_u$ to its parent in $T$.
If $p_u$ is marked, return $p_u$ as the LCA of $u$ and $v$. Otherwise mark $p_u$.

If $p_v$ is not the root of $T$:

Move $p_v$ to its parent in $T$.
If $p_v$ is marked, return $p_v$ as the LCA of $u$ and $v$. Otherwise mark $p_v$.

Once the LCA $z$ of $u$ and $v$ is known, it takes time $O(d_T(u,v))$ to find the distances from $z$ to $u$ and from $z$ to $v$ in $T$. Therefore $d_T(u,v)$ can be found in time $O(d_T(u,v)) = O(n)$.

If you have to frequently report the distance between pairs of vertices in a static tree then you can do so in constant time per query after a linear time preprocessing:

Build a LCA oracle: a data structure that can report the LCA between two vertces in $T$ in contant time. This data structure can be constructed in time $O(n)$. The construction is very clever and elegant. See this paper for the details.
Augment each node $v$ in the tree by storing its depth depth($v$) in $T$.
Answer a query for the distance between $u$ and $v$ in $T$ by: 1) finding the LCA of $z$ of $u$ and $v$ using the oracle; 2) returning $(\text{depth}(u) - \text{depth}(z)) + (\text{depth}(u) - \text{depth}(z))$.


Generating inputs for random-testing graph algorithms? When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness. Modern testing frameworks can generate inputs automatically given the algorithms signature, with some restrictions.

If the inputs are numbers, lists or strings, generating such inputs in straight-forward. Trees are harder, but still easy (using stochastic context-free grammars or similar approaches).

How can you generate random graphs (efficiently)? Usually, picking graphs uniformly at random is not what you want: they should be connected, or planar, or cycle-free, or fulfill any other property. Rejection sampling seems suboptimal, due to the potentially huge set of undesirable graphs.

What are useful distributions to look at? Useful here means that

the graphs are likely to test the algorithm at hand well and
they can be generated effectively and efficiently.

I know that there are many models for random graphs, so I'd appreciate some insight into which are best for graph generation in this regard.

If "some algorithm" is too general, please use shortest-path finding algorithms as a concrete class of algorithms under test. Graphs for testing should be connected and rather dense (with high probability, or at least in expectation). For testing, the optimal solution would be to create random graphs around a shortest path so we know the desired result (without having to employ another algorithm).

Random graphs with small world topology

In graphs with small world topology, nodes are highly clustered yet the path length between them is small. A topology like this can make search problems very difficult, since local decisions quickly propagate globally. In other words, shortcuts can mislead heuristics. Further is has been shown that many different search problems have a small world topology.

Watts and Strogatz [1] propose a model for small world graphs. First, we start with a regular graph. Disorder is introduced into the graph by randomly rewiring each edge with probability $p$. If $p=0$, the graph is completely regular and ordered. If $p=1$, the graph is completely random and disordered. Values of $0 < p < 1$ produce graphs that are neither completely regular nor completely disordered. Graphs don't have a small world topology for $p=0$ and $p=1$.

Watts and Strogatz start from a ring lattice with $n$ nodes and $k$ nearest neighbours. A node is chosen from the lattice uniformly at random, and a rewired edge is reconnected to it. If rewiring would create a duplicate edge, it is left untouched. For large, sparse graphs they demand $n \gg k \gg \ln(n) \gg 1$, where $k \gg \ln(n)$ ensures the graph remains connected.

The model of Watts and Strogatz is somewhat popular, but does have certain drawbacks. Walsh [2] investigates the effects of randomization and restart strategies in graphs generated using the model. There's also a paper by Virtanen [3], which covers other models motivated by the need of realistic modeling of complex systems.

Random simple planar graphs

Generating random simple planar graphs on $n$ vertices uniformly at random can be done efficiently. The number of planar graphs with $n$ vertices, $g_n$, can be determined using generating functions. The value of $g_n$ for $1 \leq n \leq 9$ is $1,2,8,64,1023,32071,1823707,163947848$ and $20402420291$, respectively.  Since the numbers are too complicated, one is not expected to find a closed formula for them. Giménez and Noy [4] give a precise asymptotic estimate for the growth of $g_n$:
$$g_n \sim g \cdot n^{-7/2} \gamma^n n!,$$
where $g$ and $\gamma$ are constants determined analytically with approximate values $g \approx 0.42609$ and $\gamma \approx 27.22687$.

The proof of the result leads to a very efficient algorithm by Fusy [5]. Fusy gives an approximate size random generator and also a exact size random generator of planar graphs. The approximate size algorithm runs in linear time while the exact size algorithm runs in quadratic time. The algorithms are based on decomposition according to successive levels of connectivity: planar graph $\rightarrow$ connected $\rightarrow$ 2-connected $\rightarrow$ 3-connected $\rightarrow$ binary tree.

The algorithms then operate by translating a decomposition of a planar graph into a random generator using the framework of Boltzmann samplers by Duchon, Flajolet, Louchard and Schaeffer [6]. Given a combinatorial class, a Boltzmann sampler draws an object of size $n$ with probability to $x^n$, where $x$ is certain real parameter tuned by the user. Furthermore, the probability distribution is spread over all the objects of the class, with the property that objects of the same size have the same probability of occurring. Also, the probability distribution is uniform when restricted to a fixed size.

For a lightweight introduction, see a presentation by Fusy.

[1] D.J. Watts and S.H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440-442, 1998.

[2] Toby Walsh. Search in a small world. Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99-Vol2), pages 1172-1177, 1999.

[3] Satu Virtanen. Properties of nonuniform random graph models. Research Report A77, Helsinki University of Technology, Laboratory for Theoretical Computer Science, 2003.

[4] O. Giménez and M. Noy. Asymptotic enumeration and limit laws of planar graphs, arXiv
math.CO/0501269. An extended abstract has appeared in Discrete Mathematics and The-
oretical Computer Science AD (2005), 147-156.

[5] E. Fusy. Quadratic and linear time generation of planar graphs, Discrete Mathematics and Theoretical Computer Science AD (2005), 125-138.

[6] P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Boltzmann sampler for the random generation of combinatorial structures. Combinatorics, Probability and Computing, 13(4-5):577-625, 2004.


Generating bit sequence containing every possible of length 1...n Generating sequence containing every possible bit sequence of lengths from $1$ to $n$ is trivial - just generate every possible sequence of length $n$.

But how do you generate the shortest sequence containing every possible bit subsequence of lengths from $1$ to $n$ (using the fact that subsequences may partially overlap)?

What complexity class does that problem belong to?

Such a sequence (for arbitrary $k$-ary encodings) is known as a De Bruijn sequence. For the case of the binary encodings, the De Bruijn sequence has length $2^n$. As the output is exponential, this problem is clearly not in $P$, but it lies in $EXP$, as it can be constructed via a Hamiltonian path along the De Bruijn graph (see also here)


Partitioning a graph into subgraphs with overlapping nodes I'd like to partition a graph into subgraphs with overlapping nodes.
To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in networkx package.
import networkx as nx
from networkx.algorithms.community.kernighan_lin import kernighan_lin_bisection

if __name__ == '__main__':
     G = nx.gnm_random_graph(n=30, m=55, seed=1)
     A, B = kernighan_lin_bisection(G)

For creating more than two partitions, it is mentioned here, https://stackoverflow.com/questions/63357626/networkx-kernighan-lin-multipartition, that metis can be used. However, I came across an old post that mentions partitioning with overlapping nodes is not supported in metis. I would like to ask for suggestions on references to algorithms/packages that support
partitioning with overlaps.
EDIT:
I'd like to partition into subgraphs with >= 4 overlapping vertices.
e.g. in the subgraphs presented here . i.e.

for any cluster C1 there must be a cluster C2 such that |C1∩C2|≥4

The number of overlap nodes (overlap size) is 3 and 1. But I want the overlap size to be >=4 overlap nodes.
EDIT 2:

For example, why not simply pick another pure-yellow vertex randomly
and add that to the green set, so that yellow and green overlap by
exactly 4? And why not pick the remaining 3 pure-yellow vertices and
add them to the blue set, so that yellow and blue overlap by exactly
4?

Yes, I could do this. I'm trying the óverlapping communities algorithms available in CDLIB to do the same.
 import networkx as nx
 from cdlib import algorithms

if __name__ == '__main__':

    g = nx.karate_club_graph()

    coms = algorithms.angel(g, threshold=4, min_community_size=10)
    print(coms.method_name)
    print(coms.method_parameters)  # Clustering parameters)
    print(coms.communities)
    print(coms.overlap)
    print(coms.node_coverage)

Output:
ANGEL
{'threshold': 4, 'min_community_size': 10}
[[14, 15, 18, 20, 22, 23, 27, 29, 30, 31, 32, 8], [1, 12, 13, 17, 19, 2, 21, 3, 7, 8], [14, 15, 18, 2, 20, 22, 30, 31, 33, 8]]
True
0.6470588235294118

From the communities returned, I understand 1 and 3 have an overlap of 4 nodes but 2 and 3 or 1 and 3 don't have an overlap size of 4 nodes.
It is not clear to me how the overlap threshold (4 overlaps) has to be specified
here algorithms. angel(g, threshold=4, min_community_size=10). Since it is mentioned in the comment below that the "overlap is upper bounded" , I tried setting threshold=4 here. However, from the documentation available for angel

:param threshold: merging threshold in [0,1].

I am not sure how to translate the 4 overlaps to the value that has to be set between the bounds [0, 1].
Could someone please clarify? If there are suggestions on the other overlapping communities algorithms that I could try from CDLIB, I'd be happy to try. I also had a look at the percolation methods implemented in the kclique algorithm of CDLIB. Unfortunately, I am not sure how to specify the overlap threshold here.
I'm really sorry for not being clear, I'm new to this field and I am learning from here.

I never heard of any algorithm with the constraint of having an overlap between communities larger than a given threshold (4 here).
But I suggest the following: turn your graph into its line graph, use a classical node partitioning method that gives a hierarchy of communities, and then choose a partition that fits your requirements.
More details:

the line graph is the graph in which the nodes are the links of your original graph, and these nodes are linked together if corresponding links have an extremity in common, see wikipedia on line graph.
classical community detection algorithms partition nodes into disjoint sets; doing so on the line graph will produce a partition of the edge set, with some nodes in several communities (overlap).
many classical community detection algorithms actually produce a hierarchical decomposition, often encoded as a dendrogram, i.e. a tree of communities, sub-communities, sub-sub-communities, and so on, see wikipedia on dedrograms.
a partition into communities then is a choice of a place to cut this tree, wherever it fits your needs; for instance, one may maximize a quality function and a scale parameter, see e.g. Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
therefore you may choose a cut maximizing a quality function while satisfying your requirement; you may for instance start with the optimal partition regarding the quality function, and then move the cut to fit your overlap requirement.

Good luck, please keep us informed of any progress :)


Prefix Sums in Mutable 2D Array Suppose I have a 2D array M[n][n] of integers (in fact, binary is fine, but I doubt it matters). I am interested in repeated queries of the form: given a coordinate pair $k,l$, what is
$$
\sum_{i = 0}^{k-1} \sum_{j = 0}^{l-1} M[i][j]?
$$
Of course, all these values can be computed in $\mathcal O(n^2)$ time total, and after that queries take $\mathcal O(1)$. However, my array is mutable, and each time I change a value, the obvious solution requires a $\mathcal O(n^2)$ update.

We can create a quad tree over M; the preprocessing takes $\mathcal O(n^2\log(n))$, and this allows us to do queries in $\mathcal O(n\log(n))$, and updates in $\mathcal O(\log(n))$.

My question is:

  Can we improve significantly on the queries without sacrificing too much on the updates?

I am especially interested in getting both the update and query operations sub-linear, and in particular getting them both to $\mathcal O(n^\epsilon)$.

Edit: for some more information, although I think the problem is interesting even without this further restriction, I expect to do roughly $\mathcal O(n^3)$ queries, and about $\mathcal O(n^2)$ updates. The ideal goal is to get the full runtime down to about $\mathcal O(n^{3+\epsilon})$. Thus, a situation where an update takes $\mathcal O(n \log(n))$ while a query takes $\mathcal O(\log(n))$ would also be interesting to me.

There is a relatively straightforward solution where each query and each update can be done in $O(\log^2 n)$ time.  The data structure uses $O(n^2)$ space.

We will have $\lg n$ "granularities" of data structure, one for each power of two $2^m$ such that $1 \le 2^m \le n$.  The data structure for granularity $2^m$ stores the sums

$$\sum_{i=k_0 \cdot 2^m}^{(k_0+1) \cdot 2^m -1} \sum_{j=0}^{l-1} M[i,j]$$

for each $k_0,l$.  This data structure for granularity $2^m$ can in turn be represented using $n/2^m$ balanced trees (one for each possible value of $k_0$) to store prefix sums.

Now to look up the prefix sum for $k,l$, we break up the interval $[0,k-1]$ into a union of intervals of power-of-two length; at most $\lg n$ intervals are needed.  For each such interval of length $2^m$, we do a lookup into the data structure of granularity $2^m$.  Thus queries can be answered by doing $O(\log n)$ lookups into a balanced tree, each of which takes $O(\log n)$ time, for a total time of $O(\log^2 n)$ per query.

Updates can also be done in $O(\log^2 n)$ time.  To update $M[i,j]$, for each granularity $2^m$, you update the appropriate balanced tree in the data structure of granularity $2^m$.  This is $O(\log n)$ updates oin $O(\log n)$ balanced trees; each such takes $O(\log n)$ time, so the total time is $O(\log^2 n)$ time.

Finally, the data structure of granularity $2^m$ contains $n/2^m$ trees, each taking up $O(n)$ space, so the total space usage is $O(n^2 \cdot (1 + 1/2 + 1/4 + \cdots)) = O(n^2)$.


Simulate a fair die with a biased die Given a biased $N$-sided die, how can a random number in the range $[1,N]$ be generated uniformly? The probability distribution of the die faces is not known, all that is known is that each face has a nonzero probability and that the probability distribution is the same on all throws (in particular, the throws are independent). This is the obvious generalization of Fair results with unfair die.

Putting this in computer science terms, we have an oracle representing the die rolls: $D : \mathbb{N} \to [1,N]$ such that $p_i = P(D(k)=i)$ is nonzero and independent of $k$. We're looking for a deterministic algorithm $A$ which is parametrized by $D$ (i.e. $A$ may make calls to $D$) such that $P(A()=i) = 1/N$. The algorithm must terminate with probability 1, i.e. the probability that $A$ makes more than $n$ calls to $D$ must converge to $0$ as $n\to\infty$.

For $N=2$ (simulate a fair coin from coin flips with a biased coin), there is a well-known algorithm:

Repeat “flip twice” until the two throws come up with distinct outcomes ((heads, tails) or (tails, heads)). In other words, loop for $k = 0..\infty$ until $D(2k+1) \ne D(2k)$
Return 0 if the last pair of flips was (heads, tails) and 1 if it was (tails, heads). In other words, return $D(2k)$ where $k$ is the index at which the loop was terminated.

A simplistic way to make an unbiased die from a biased one is to use the coin flip unbiasing method to build a fair coin, and build a fair die with rejection sampling, as in Unbiasing of sequences. But is this optimal (for generic values of the probability distribution)?

Specifically, my question is: what is an algorithm that requires the smallest expected number of calls to the oracle? If the set of reachable expected values is open, what is the lower bound and what is a class of algorithms that converges towards this lower bound?

In case different families of algorithms are optimal for different probability distributions, let's focus on almost-fair dice: I'm looking for an algorithm or a family of algorithms that's optimal for distributions such that $\forall i, \bigl|p_i - 1/N\bigr| \lt \epsilon$ for some $\epsilon \gt 0$.

The following paper answers a close variant of this question: The Efficient Construction of an Unbiased Random Sequence, Elias 1972.

The question there seems to be this: Given access to this biased independent source, output a sequence of random numbers in $[1,N]$ (note the difference from your question in which only one output symbol is requested). As the length of the desired output goes to infinity, the "efficiency" of the scheme in the paper (which seems like a natural generalization of von Neumann) goes to $1$, meaning, I believe, that an input with entropy $h$ is converted to an output of entropy approaching $h$.

The question seems much better behaved when phrased this way, rather than requesting a single output digit, because, for instance, if we draw $N$ samples and end up with an output with lots of information (for instance, all $N$ input symbols are distinct), then we can use all of that information to produce many output symbols, whereas with the question as phrased here, any information beyond that used to produce one output symbol goes to waste.

I believe that the scheme repeatedly takes $N$ draws, looks at the sequence, and maps it some outputs or the empty string. Perhaps there is a way to improve the scheme for your question by looking at prefixes and stopping if we have "enough" information to output a symbol? I don't know.


Is the word problem of CFLs in NC? Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string.

Lets say I have a PRAM and I want it to decide in $\log^k n$ time and $n^c$ space complexity whether $w$ is in $L(G)$ ($c$ and $k$ are both constants) – that is, the complexity stays within Nick's class.

Is there such an algorithm? If so what would be an idea?

The problem is not in NC unless P=NC. Jones and Laaser showed in "Complete Problems for Deterministic Polynomial Time" that the problem (therein called CFMEMBER) is P-complete.
Interestingly, Ullman and Van Gelder showed in "Parallel Complexity of of logical query programs" that the same problem where the input CFG has no epsilon productions is in NC (Corollary 7.2).


Solving System of Equations (Re-posted from StackOverflow as suggested)

I have the following problem.

The functions $f(x),g(x)$ are defined as
$$
f(x) = \begin{cases} f_1(x) & 0 \leq x \leq 10, \\ f_2(x) & 10 < x \leq 20, \\ 0 & \text{otherwise}, \end{cases} \qquad
g(x) = \begin{cases} g_1(x) & 0 \leq x \leq 5, \\ g_2(x) & 5 < x \leq 20, \\ 0 & \text{otherwise}, \end{cases}
$$
In addition, we require the constraints
$$
\int_0^{20} f(x) dx \geq K, \quad \int_0^{20} g(x) dx \geq Q, \quad f(x)+g(x) \leq R \text{ for all $x$}.
$$
where $K,Q,R$ are parameters.

I assume there is quite some elaborate theory behind it, and was wondering if anybody could point me in the right direction to devise an algorithm that can generate $f_1(x), f_2(x), g_1(x), g_2(x)$?

I would like to add that for a given $K$ and $Q$, the interest is to keep $R$ as low as possible.

Let $X$ be a random variable distributed uniformly over $[0,20]$. Your constraints imply
$$ \mathbb{E}[f(X)] \geq \frac{K}{20}, \qquad \mathbb{E}[g(X)] \geq \frac{Q}{20}. $$
We conclude that
$$ \mathbb{E}[f(X)+g(X)] \geq \frac{K+Q}{20}, $$
and so there is some point $x \in [0,20]$ such that $f(x) + g(x) \geq (K+Q)/20$. In particular, $R \geq (K+Q)/20$. This bound is tight, as shown by the functions
$$ f(x) = \frac{K}{20} \mathbf{1}_{x \in [0,20]}, \qquad g(x) = \frac{Q}{20} \mathbf{1}_{x \in [0,20]}. $$


Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k} I had a question regarding the Pumping lemma for regular languages, I have been studying for an exam and came across the question {a^2k w | w ∈ {a, b}*, |w| = k}. In the website it lists the answer and I'm having a little bit of trouble trying to figure out what a specific part of this answer means. It states:

  Assume L is regular. From the pumping lemma there exists a p such that every
  w ∈ L such that |w| ≥ p can be represented as x y z with |y|≠0 and |xy|≤ p. Let
  us choose a^2p b^p. Its length is 3p≥p. Since the length of xy cannot exceed p, y
  must be of the form a^k for some k > 0. From the pumping lemma a^2p-k b^p must
  also be in L but it is not of the right form since the number of a’s cannot be twice
  the number of b’s (Note that you must subtract not add , otherwise some a’s
  could be shifted into w). Hence the language is not regular.

So my issue lies in the very last line of the proof where it states that " you must subtract not add, otherwise some a's could be shifted into w"

Is there anyone that could help me visualize what this could possibly mean, I feel as though it may be trivial but I seem to be having trouble with it.

Thank you in advance!

In typical usage of the pumping lemma, you assume that the word you chose for pumping is written as $w=xyz$, with $x,y,z$ satisfying the conditions of the pumping lemma.

Then, in most cases, you reach a contradiction by saying that e.g., $xy^2z$ is not in the language. This is "pumping up", since you "add" copies of $y$.

In this case, however, you reach a contradiction by looking at the word $xz$ (i.e., $xy^0z$). So you are pumping "down", or subtracting copies of $y$.

The reason for this is that if you look at e.g., $xy^2z$, then you get a word of the form $a^{2p+k}b^p$, but this word might be written as $a^{2r} a^lb^p$ with $l+p=r$, so you would not reach a contradiction.


What am I missing in this application of Dijkstra? When running Dijkstra against the following graph:

   1   3
A -- B -- C
 \      /
2 \    / 1
   \  /
    D

...I come up with the following:

   Current
                A      B          C          D
         A      1(via A)   -          2(via A)
         B      1(A)       4(via B)   2(via A)
         C      1(A)       4(via B)   2(via A) (5 via C ignored)

The shortest path from A to B is 1 via A.
The shortest path from A to C is 4 via B.
The shortest path from A to D is 2 via A.

...but there is a path from A to C via D that is of magnitude 3 (2 + 1).

What am I missing here?

current should be the unexplored with the lowest cost. Which means that after you explored $B$ you should have explored $D$ because $2<4$.


How to learn how CPU works in details I've watched multiple videos and read posts regarding modern cpus and how they work.

However, those ones very rarely touch the problem on the very basic level.
Like I've read about transistors and stuff but I would like to spend (a lot I guess) time to actually understand how e.g. programming a math operation like 5^5 is calculated by cpu hardware.

Do you have any ideas where to start?

p.s. my uni background is econometrics which ended up in machine learning job. Unfortunately I have no CS knowledge.

Kind Regards,
Matt

The recommended online resource I found was: Hoow do it know

Today's CPUs are incredibly complex beasts. Sure, you can go rummage in computer architecture books and get a rough idea how a very simple CPU works. Understanding in detail how the CPU in your PC  (or even your smartphone) works will require a lifetime, if not more. I suspect noone at Intel/AMD really undestands their latest CPU fully.

For example, today's processors take instructions from RAM, translate them into microinstructions internally, reorder and schedule those working even on several copies of the programmer-visible registers in parallel where possible (doing more or less the job of an optimizing compiler), and finally executing the resulting stream(s) of microinstructions.

Today's CPUs are much, much faster than RAM (in the time required to fetch a word from memory they can execute hundreds of instructions). Cache memory, and it's efficient use, predicting what will be read next, is crucial. Another area of significant complexity.

Add circuitry to compute the various operations, including floating point and assorted functions, like square roots and trigonometric functions. A box marked "floating point unit" right there.

And this doesn't yet consider the GPU that is integrated in some models...


Select a subset of the columns in $2\times n$ matrix, is it easy? I want to know if this problem is polynomial-time solvable or not?

The problem is: Given a nonnegative integer-valued matrix of size $2\times n$ and two nonnegative integer numbers $b<n$ and $c$.

The question is: Find a subset of the columns of cardinality at most $b$ such that the sum of each row over the subset of the columns is greater than $c$. Return no if no such subset exists.

I cannot show it is NP-hard.

EDIT:

My attempt to prove hardness: According to the suggestions by Filmus, I tried to reduce PARTITION (an instance is given by the set of non-negative integers $\{a_1,\ldots,a_n\}$) to my problem. I failed of course. The think that I did not understand is how partitioning a set of non-negative integers is related to this problem? I mean in my problem I want to choose a subset of $\{1,\ldots,n\}$ in order to maximize something. I cannot see how this is a partition. I tried many thinks but I cannot write them all here:

I tried to create the matrix with only $a_{2i}$ in the first row and $a_{2i+1}$ in the second row.
I tired to make the first row sorted in increasing order and the second row sorted in the decreasing order.
I tried to divide the $a_i$ into two values $\alpha_i$ and $\beta_i$ such that $a_i=\alpha_i+\beta_i$ and then create the matrix with $\alpha_i$ in the first row and $\beta_i$ in the second row.

Can someone explain to me, intuitively, how can I use PARTITION to show the NP-hardness of my problem? You do not have to give the solution.

My solution to solving the problem:

I tried this solution. Suppose, without lose of generality that the first row of the matrix is sorted in increasing order. (The second row of the matrix does not have to be sorted otherwise the problem is trivial.)

Now, take the last $b$ columns of the matrix.

If the sum over the first row is less than $c$ than we are done. No solution exists.
Else, the sum of the first row over the last $b$ columns is greater than $c$, then see the sum of the second row.

If the sum of the second row over the last $b$ columns is greater than $c$ than we are done. Return the last $b$ columns.
Else, the sum of the first row over the $b$ columns is greater than $c$ but the sum of the second row over the $b$ columns is less than $c$. Well, here we have a problem.

Hint: Show that it is NP-hard by reduction from EQUAL-PARTITION, the variant of PARTITION in which we require both parts to have equal sizes (see a question on math.se).

Given an instance $\{x_1,\ldots,x_n\}$ of EQUAL-PARTITION (with $x_i > 0$), consider an instance of your problem with $b = n/2$, $c = \sum_i (M+x_i)/2 - 1$ for large enough $M$ (I think that $M = \max_i x_i$ should suffice), and the matrix
$$
\begin{bmatrix}
M+x_1 & \cdots & M+x_n \\
M+\frac{\sum_i x_i}{n/2}-x_1 & \cdots & M+\frac{\sum_i x_i}{n/2}-x_n
\end{bmatrix}.
$$


Prove that $\neg 0 = 1$ Starting from this definition https://en.wikipedia.org/wiki/Boolean_algebra_%28structure%29#Definition, is the following a valid proof that $\neg 0 = 1$?

Instantiate a ∨ ¬a = 1 with a:=0 to get 0 ∨ ¬0 = 1
Then use pattern matching (and commutativity) against a ∨ 0 = a to get a = ¬0 on the LHS and a=1 on the RHS, thus ¬0 = 1.

To clarify the "pattern matching":
We have

0 ∨ ¬0 = 1
0 ∨ 1 = 1 (from 0 ∨ a = a)
0 ∨ 0 = 0 (also from from 0 ∨ a = a)

If there are only the two elements 0 and 1 available, ¬0 = 1 should follow from this. But then again, if it were not true that ¬0 = 1, we would have that ¬0 = 0, which wouldn't make too much sense...

Are there other/simpler proofs?

It's a valid proof in the sense that it convinces an appropriately skeptical reader that $\neg 0 = 1$. The argument is as follows.

By an axiom $0\vee \neg 0 = 1$.
We know that either $\neg0=0$ or $\neg0=1$.
We can't have $\neg0=0$ because $0\vee0=0$.
So it must be the case that $\neg0=1$.
Actually, let's check that: $0\vee 1=1$. Good.

However, that's not a proof from the axioms. Of the steps that you've used, only 1 is actually an axiom.

Step 2 is the law of excluded middle, which isn't actually one of the axioms. If you think about it, it's not actually obvious that every formula evaluates to exactly one of 0 and 1 (in particular, there are no formulae that evaluate to both 0 and 1, and none that evaluate to either).  The law of excluded middle can be proven from the axioms but it's not an axiom.

Step 3 uses an axiom ($a\vee0=a$ instantiated with $a=0$) to deduce that $0\vee 0=0$ but there's no axiom that says you can use this to conclude that $b\neq 0$ if $a\vee b\neq a$.

Step 4 is restating the law of excluded middle.

In step 5, you could use some axioms to deduce that $0\vee 1=1$ ($0\vee 1 = 1\vee 0 = 1$) but, again, there's no axiom allowing you to draw the ultimate conclusion.

Students often get confused about axiomatic proofs: the usual complaint is "I don't know what I'm allowed to use."  Confusion about that is very understandable: you've spent your whole life "knowing" that $\neg0=1$ and treating that as (half of) the definition of negation. If you're not allowed to "know" something as basic as how negation works, what on earth are you allowed to know?  (Students have exactly the same problems with elementary group theory.)

For an axiomatic proof, it's actually quite simple: you're allowed to use the axioms, instantiated however you please.1 If you can prove something from the axioms, you're allowed to use that repeatedly, as a lemma: for example, I proved above that $0\vee 1=1$ so you could use that as many times as you want, after proving it once. But that's all.

Alexey Romanov included a proof in his comment to the question.  I'll write it out a little more fully.

$$\begin{align*}
    \neg0
        &= \neg0 \vee 0 &\text{($0$ is the identity for $\vee$)}\\
        &= 0 \vee \neg0 &\text{(commutativity of $\vee$)}\\
        &= 1            &\text{(instantiate $a\vee\neg a=1$ with $a=0$).}
\end{align*}$$

Because of the limited resources available to you, axiomatic proofs tend to be rather fiddly and tedious, which is why we don't do them after the first week of the course. Pedagogically, I think it's actually a mistake to start with axiomatic proofs because they confuse the students more than they help. I think it would be better to introduce them later in a course, after the students are already used to proving things.

OK, and transitivity of equality and probably modus ponens. But I'm just putting this here for the experts to think about; for the beginner, this footnote is more likely to confuse than clarify.


Conditional LCS problem A producer wants to arrange couples of boys and girls for a dance.
There are n boys arranged in a row [A1...An] in some certain order and n girls arranged in a different row [B1...Bn], also in some certain order.
Only a couple in which there is a boy and a girl with exactly the same height can dance.
The height of every boy and girl is known.  The producer needs to find the maximum number of couples that can dance (There might be people who can't dance).

Show an algorithm for the general case.
Show an algorithm, in which you can't change the order of the boys and the girls. In other words: If there is a couple (Ai,Bj) then there can't be (Ak,Bp) (so that k > i, p < j or k < i, p > j)

Analyze the complexity in every case.

What I know is that the solution to 1 is sorting the array in $O(nlogn)$.
My idea in approaching 2 is that it's like LCS in a static table, only with numbers and not chars, which takes $O(n^2)$.

Can 2 be done in better complexity that $O(n^2)$?

Longest common subsequence (not necessarily continuous) is the solution for the second problem, not for the first. (For the first problem it is not only slower than necessary, but also gives the wrong result. Consider e.g. $A=[1,2]$, $B=[2,1]$: LCS would give only 1 couple, while actually 2 can be formed.)

For the first problem, as @sai_preet pointed out in a comment, you can sort both arrays and then find the couples with a procedure analoguous to merge. This will take $\Theta(n\log n)$ time.


How to feel intuitively that a language is regular Given a language $ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular?

I could use pumping lemma but some guys are saying just looking at the grammar that this is not regular one. How is it possible?

The main property of DFA's/NFA's is the lack of unbounded memory. If you look at a language and the only algorithm (which should later be translated into a Finite Automaton) you can think of requires this property, that is, you feel that any algorithm that recognizes it will need to remember an arbitrary large number of things (like $n$ in your example) then that language is probably not regular.

Of course, you should always remember that mathematical intuition can be wrong, and the only way to be sure of your intuition is to prove it.

EDIT: I'll answer the last question in the comments here, because of lack of space.

  you guys are talking about unbounded memory which you mean is the reason why it is not regular. but a^nb^m can also have unbounded memory if i want, doesnot it? this is still giving me no peace.

The issue is not how big the words can get (you will usually encounter infinite regular languages, because every finite language is regular, and that's pretty boring) but how much the DFA needs to remember.
In the $a^mb^n$ example, there is no need to remember $m,n$. The algorihm just needs to make sure they are positive and that the word is correctly ordered. This is a finite list, and each of the items on the list requires a constant amount of memory.
Compare this to $a^nb^n$, for which a simple alogrithm is required to remember that the number of $a$'s is equal to the number of $b$'s. This will require unbounded memory.
When I look at a language and see that any algorithm I can think of needs unbounded memory, my intuition that the language is not regular grows stronger. If I can't find a "smart"  algorithm (one that requires a constant amount of memory) in a reasonable amount of time (how much time is reasonable is up to you) I will try proving the language is not regular.
Hope this makes it a bit clearer.


Is this “cut condition" sufficient for unique minimum spanning tree? Given a connected, undirected, weighted graph $G$, the following "cut condition"

  For any partition of the vertices of $G$ into two subsets, the minimum-weight edge with one endpoint in each subset is unique.

is not necessary for $G$ to have a unique minimum spanning tree.

However, is this "cut condition" sufficient for $G$ to have a unique MST?

Related post: Is this "cycle condition" sufficient for unique minimum spanning tree?

Answer my own question: The answer is from here.

For every cut of $G$, the unique light edge crossing the cut must be part of every MST of $G$. Consider the set $T$ of edges, containing the unique light edge crossing each cut $C$ of $G$. Then, we know that $T$ is a subset of every MST.

Now we can show that $T$ must be equal to every MST.

Because there is exactly one edge of $T$ crossing every cut of $G$, the graph $(V, T)$ must have exactly one connected component: if there were two unconnected components $V_1$ and $V − V_1$, then the cut $(V_1, V − V_1)$ would not be crossed by any edge of $T$, which contradicts the definition of $T$.
In addition, $T$ cannot contain any cycles: the heaviest edge on a cycle in $T$ cannot be the unique lightest edge in any cut. Then $T$ itself must be a spanning tree of $G$. Because $T$ is a subset of all minimum spanning trees of $G$, it must be the unique MST of $G$, as any additional edge added to $T$ would form a cycle, making it no longer
be a tree.


Looking for a set implementation with small memory footprint I am looking for implementation of the set data type. That is, we have to

maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with
operations insert(x) (add an element x to $S$) and find(x) (checks whether element x is a member of $S$).

I don't care about other operations. For orientation, in applications I'm working with we have $u \approx 10^{10}$.

I know of implementations that provide both operations in time $O(1)$, so I worry mostly about the size of data structure. I expect billions of entries but want to avoid swapping as much as possible.

I am willing to sacrifice runtime if necessary. Amortised runtime of $O(\log n)$ is what I can admit; expected runtimes or runtimes in $\omega(\log n)$ are not admissable.

One idea I have is that if $S$ can be represented as a union of ranges [xmin, xmax], then we will be able to save on storage size with the price of some performance decrease. Also, some other data patterns are possible, like [0, 2, 4, 6].

Could you please point me to data structures which can do something like that?

Joe's answer is extremely good, and gives you all the important keywords.

You should be aware that succinct data structure research is still in an early stage, and many of the results are largely theoretical. Many of the proposed data structures are quite complex to implement, but most of the complexity is due to the fact that you need to maintain asymptotic complexity both over the universe size and the number of elements stored. If either one of these is relatively constant, then a lot of the complexity goes away.

If the collection is semi-static (that is, inserts are rare, or at least low-volume), then it's certainly worth considering an easy-to-implement static data structure (Sadakane's sdarray is a fine choice) in conjunction with an update cache. Basically, you record updates in a traditional data structure (e.g. B-tree, trie, hash table), and periodically bulk-update the "main" data structure. This is a very popular technique in information retrieval, since inverted indexes have many advantages for searching but are hard to update in-place. If this is the case, please let me know in a comment and I'll amend this answer to give you some pointers.

If inserts are more frequent, then I suggest succinct hashing. The basic idea is straightforward enough to explain here, so I will do so.

So the basic information theoretic result is that if you're storing $n$ elements from a universe of $u$ items, and there is no other information (e.g. no correlation between the elements) then you need $\log {u \choose n} + O(1)$ bits to store it. (All logarithms are base-2 unless otherwise specified.) You need this many bits. There is no way around it.

Now some terminology:

If you have a data structure which can store the data and support your operations in $\log {u \choose n} + O(1)$ bits of space, we call this an implicit data structure.
If you have a data structure which can store the data and support your operations in $\log {u \choose n} + O(\log {u \choose n}) = (1 + O(1)) \log {u \choose n}$ bits of space, we call this a compact data structure. Note that in practice this means that the relative overhead (relative to the theoretical minimum) is within a constant. It could be 5% overhead, or 10% overhead, or 10 times overhead.
If you have a data structure which can store the data and support your operations in $\log {u \choose n} + o(\log {u \choose n}) = (1 + o(1)) \log {u \choose n}$ bits of space, we call this a succinct data structure.

The difference between succinct and compact is the difference between little-oh and big-oh. Ignoring the absolute-value thing for a moment...

$g(n) = O(f(n))$ means that there exists a constant $c$ and a number $n_0$ such that for all $n > n_0$, $g(n) < c \cdot f(n)$.
$g(n) = o(f(n))$ means that for all constants $c$ there exists a number $n_0$ such that for all $n > n_0$, $g(n) < c \cdot f(n)$.

Informally, big-oh and little-oh are both "within a constant factor", but with big-oh the constant is chosen for you (by the algorithm designer, the CPU manufacturer, the laws of physics or whatever), but with little-oh you pick the constant yourself and it can be as small as you like. To put it another way, with succinct data structures, the relative overhead gets arbitrarily small as the size of the problem increases.

Of course, the size of the problem may have to get huge to realise the relative overhead that you want, but you can't have everything.

OK, with that under our belts, let's put some numbers on the problem. Let's supposed that keys are $n$-bit integers (so the universe size is $2^n$), and we want to store $2^m$ of these integers. Let's suppose that we can magically arrange an idealised hash table with full occupancy and no wastage, so that we need exactly $2^m$ hash slots.

A lookup operation would hash the $n$-bit key, mask off $m$ bits to find the hash slots, and then check to see if the value in the table matched the key. So far, so good.

Such a hash table uses $n 2^m$ bits. Can we do better than this?

Suppose that the hash function $h$ is invertible. Then we don't have to store the whole key in each hash slot. The location of the hash slot gives you $m$ bits of the hash value, so if you only stored the $n-m$ remaining bits, you can reconstruct the key from those two pieces of information (the hash slot location and the value stored there). So you would only need $(n - m) 2^m$ bits of storage.

If $2^m$ is small compared with $2^n$, Stirling's approximation and a little arithmetic (proof is an exercise!) reveals that:

$$(n - m) 2^m = \log {2^n \choose 2^m} + o\left(\log {2^n \choose 2^m}\right)$$

So this data structure is succinct.

However, there are two catches.

The first catch is constructing "good" invertible hash functions. Fortunately, this is much easier than it looks; cryptographers make invertible functions all the time, only they call them "cyphers". You could, for example, base a hash function on a Feistel network, which is a straightforward way to construct an invertible hash functions from non-invertible hash functions.

The second catch is that real hash tables are not ideal, thanks to the Birthday paradox. So you'd want to use a more sophisticated type of hash table which gets you closer to full occupancy with no spilling. Cuckoo hashing is perfect for this, as it lets you get arbitrarily close to ideal in theory, and quite close in practice.

Cuckoo hashing does require multiple hash functions, and it requires that values in hash slots be tagged with which hash function was used. So if you use four hash functions, for example, you need to store an additional two bits in each hash slot. This is still succinct as $m$ grows, so it's not a problem in practice, and still beats storing whole keys.

Oh, you might also want to look at van Emde Boas trees.

MORE THOUGHTS

If $n$ is somewhere around $\frac{u}{2}$, then $\log {u \choose n }$ is approximately $u$, so (once again) assuming that there is no further correlation between the values, you basically can't do any better than a bit vector. You will note that the hashing solution above does effectively degenerate to that case (you end up storing one bit per hash slot), but it's cheaper just to use the key as the address rather than using a hash function.

If $n$ is very close to $u$, all of the succinct data structures literature advises you to to invert the sense of the dictionary. Store the values that don't occur in the set. However, now you effectively have to support the delete operation, and to maintain succinct behaviour you also need to be able to shrink the data structure as more elements get "added". Expanding a hash table is a well-understood operation, but contracting it is not.


Is CPU Registers part of Primary Memory? A friend of mine appeared in an exam recently, and one of the question asked was regarding CPU Registers, which has two points:

(a) CPU Registers are part of Primary Memory
(b) They are volatile

And the choices given were:

Both (a) and (b) are true
Only (a) is true
Only (b) is true
None of the above

They are volatile. So the second and forth options can be avoided. The confusion was regarding whether it was part of Primary Memory. To my knowledge, CPU Caches, RAMs and ROMs can be called as primary memory. But will CPU registers would be called as part of primary memory? Or will it be considered as Level0 caches?

CPU registers are often counted as part of primary memory (since they are directly accessed by the CPU - see Wikipedia) and are often volatile, so it seems likely that the expected answer is (1).

However, this is one of those annoyingly ambiguous questions which depend on the student memorising a very specific set of definitions and ignoring any exceptions.


How to determine approximability of a problem when we don't know how good a solution is? As far as I have learned, an approximation algorithm for an optimization problem

Runs in polynomial time, and
Whose cost can be bounded by a function of input in terms of distance from the optimal cost.

If we consider the optimization version of subset-sum problem, it says

  Given a set $A$ of integers, what is the maximum value of $sum(B) \le t$
  where $B \subset A$, $sum(B) = \sum{b\in B}$ and $t \in Z^+$

In this problem, we know that we search for a maximum value that is smaller than or equal to $t$. So, a solution $B_1$ is better than another solution $B_2$ if $\dfrac{sum(B_1)}{sum(OPT)} > \dfrac{sum(B_2)}{sum(OPT)}$, $OPT$ being the optimal subset.

Now, let us consider the WSN localization problem, which is defined as:

We have a set $A = \{1,2,\dots,n\}$ of $n$ points in $d$-dimensions. We only know the coordinates of some points, let us denote them with $B = \{b_1, b_2, \dots, b_m\}$ where $B \subset P$. By using the positions of the nodes in $B$, we aim to assign positions to the nodes in $A$. While doing this, we use the Euclidean distance graph $G = <V,E,W>$ that is given as input. In this graph, each node $i \in V$ corresponds to a point $i \in P$ and each edge $\{i,j\} \in E$ means that there is a distance measurement between the point $i$ and point $j$. The weights of an edge corresponds to the Euclidean distance between two points.

We use a unit disk graph (UDG) model. In a UDG, an edge $\{i,j\}$ exists if and only if the Euclidean distance $\delta_{ij}$ between $i$ and $j$ is smaller than or equal to a specific value $R$. That indicates if there does not exist an edge $\{i,j\}$, then $\delta_{ij} > R$.

We aim to assign coordinates to each node $v \in V$ considering their Euclidean distances. This process is called localization.

As the motivation is wireless sensor nodes, we assume that we cannot measure distances with 100% accuracy. Therefore, each distance $\delta_{ij}$ is altered by adding a value $\epsilon$ to model the environmental noise.
For any two points $i,j$ whose pairwise distance is $\hat{\delta}_{ij} < R$, the given distance is $\delta_{ij} = \hat{\delta}_{ij} + \epsilon$.

$\epsilon$ is up to $\pm P\%$ of the wireless range $R$ selected from a uniform random distribution.
Let us assume that we always can localize %100 of the nodes i.e. the input graph is localizable.
Our objective is to minimize the average localization error.
This is computed by $\dfrac{\sum\limits_{v \in V}||v_{est} - v_{act}||}{|V|}$, where $v_{est}$ is the estimated position of node $v$, $v_{act}$ is the actual position of node $v$ and $||v_{est} - v_{act}||$ denotes the Euclidean distance between two.

The optimal solution for any instance is clearly $\forall v \in V, v_{est} = v_{act}$ and the cost is $cost(OPT) = 0$.

In subset sum, we know how close we are to the value $t$ and can compare two solutions. In traveling salesman problem, we can compare the solutions by their costs. However, in localization problem, we cannot compare two solutions without knowing the actual positions, which is impossible by the definition of the problem.

My question is: Can we anyhow prove if WSN localization problem is approximable or not by not being able to know how good a solution is? Or is it completely irrelevant?

For further reading, here is the NP-hardness proof of the localization problem with noisy distances. This paper defines the formal theory of the same problem.

Definition of a well-formed optimization problem

It seems to me the core problem you have here is that the problem you have defined is not what I'd call a well-formed optimization problem.  Normally, an optimization problem looks something like this:

Input: $x$
Goal: find $y$ that maximizes $\Phi(x,y)$

where $\Phi$ is some objective function that's specified as part of the problem statement.  The key point here is that the objective function has to be computable, as a function of the input and the proposed output.

Your proposed formalization of the WSN localization problem does not have this form: the objective function is not computable as a function of the information known to us.  Therefore, it is not a well-formed optimization problem.

This explains the problem you're having.  The reason you can't compare how good different solutions are is that you don't have a computable way to measure how good a single solution is, given the information available to you.  Consequently, your problem does not fit into the standard framework of optimization problems and approximation algorithms.  This means you can't take advantage of all that theory, and strange things can happen.

So, at this point you have two options.  First, you can try to formulate your problem as a way that does qualify in this framework, i.e., where you do have a computable objective function.  The other option is to accept that you don't fit into this framework and you'll have to develop everything from scratch without being able to use the existing framework as is.

Another way to put this: if your objective function depends on values that aren't known (aren't part of the input), then what you haven't is not purely an algorithmic problem.  To make this an algorithmic task, you need a way to measure success.  One candidate way to do this would be to establish some probability distribution on the locations of the sensors, then frame this as a statistical inference problem, where you want to find the maximum likelihood estimate, or something like that.

Another approach would be to choose a different objective function, that is computable.  For instance, maybe you could evaluate the accuracy of a solution in terms of how closely it matches the givens: for what fraction of edges $\{v,v'\}$ do we have $||v_\text{est}-v'_\text{est}|| < R+\varepsilon$, and what fraction of non-edges $v,v'$ do we have $||v_\text{est}-v'_\text{est}|| > R-\varepsilon$; maybe the objective function is the sum of these two fractions, or something.  Of course, this is a different objective function, so it's maximizing something different, and the solution to that optimization problem might or might not match what you're actually looking for.

For posterity, here's some feedback on an older version of the problem, which has now been addressed by the revised question.

I see some misconceptions in this question, both about how we measure the quality of approximations, and about when approximation algorithms are applicable.  The best answer I can give is to clear up these confusions/misconceptions; that will help you think about this kind of problem more clearly.

Definition of the approximation ratio

You have a confusion about how we normally measure the quality of an approximation, in the standard theory of approximation algorithms.  This shows up in your discussion of approximation algorithms for subset sum.

With subset-sum, the objective function we are maximizing is $\text{sum}(B)$.  In the standard theory of approximability, we measure the quality of an approximation by how good the value of $\text{sum}(B)$ is, compared to the optimal value of that for the optimal choice of $B$ -- not compared to $t$.

When we ask whether there is a $2$-approximation for subset-sum, we ask whether there's an algorithm that outputs a set $B_\text{approx}$ such that

$${\text{sum}(B_\text{approx}) \over \text{sum}(B_\text{opt})} \ge 1/2,$$

where $B_\text{opt}$ is the optimal solution (the one that maximizes $\text{sum}(B)$).  The ratio on the left-hand-side is called the approximation ratio.  Notice how $t$ doesn't appear in this quantity.  The approximation ratio is defined with reference to the optimal solution, not with reference to $t$.

When approximation algorithms are applicable

Approximation algorithms are only applicable to optimization problems.

The "WSN localization problem", as you have defined it, is not an optimization problem: it is a decision problem.    Since it's not an optimization problem, the entire concept of an approximation algorithm doesn't enter into it.

Asking "is it approximable?" is a category error: it's like asking "Is 'flying' a mammal?" -- 'flying' isn't even a noun, let alone an animal.

You then talk about two metrics.  If you pick one of those metrics, you could define an optimization problem that is based upon the "WSN localization problem", where you ask to find the placement of node positions that complies with all the constraints and that maximizes (or minimizes) that metrics.  Then you would have an optimization problem.

However, when you have two metrics, we don't get a well-defined optimization problem, since it's not clear what would count as optimal.  Indeed, there might be multiple solutions that each achieve a different tradeoff between these two metrics, and is "Pareto-optimal".  (See also What is a bicriteria approximation algorithm?.)

So, to count as an optimization function, you have to be maximizing/minimizing a single objective function; the standard theory of approximation algorithms is only applicable when you have a problem that is of this form.  If your problem isn't of this form, it probably doesn't make sense to ask if it is approximable, as standard definitions of approximability don't apply.


How to determine if an automata (DFA) accepts an infinite or finite language? Given an automata [DFA $A=(Q,Σ,δ,q_0,F)$], is there a way to determine whether it accepts an infinite or finite language?

This is well enough known that you should be able to find it in most intro theory texts:

Theorem. The language accepted by a DFA $M$ with $n$ states is infinite if and only if $M$ accepts a string of length $k$, where $n\le k < 2n$.

This makes the decision problem simple: just try all strings of length at least $n$ and less than $2n$ and answer "yes" if $M$ accepts one of them and "no" if there's no string in that range that's accepted.


Traversing the edges of a labeled 2-regular graph based on a binary string Let $G$ be a $2$-regular graph. Each edge of the graph is labeled with either 0 or 1. Given a such a graph and a staring vertex $u$ and $l$ length string of 0 and 1, we have to follow the edges of the graph $G$ based upon given string. We can assume that a solution always exists.

What is the best algorithm for such problem? I can solve this problem in $O(l)$ time. I am looking for an algorithm with better runtime answer.

Note that a 2-regular graph is a disjoint union of cycles. Since you have a designated starting vertex $v$, you can disregard all cycles not containing $v$. Put differently, we can assume that the input graph is a single cycle (whose edges are labeled with zeros and ones).

Your current $\Theta(\ell)$ solution is optimal since even reading the input requires time linear in $\ell$, i.e., there exists no faster algorithm.

As a side note, the problem of finding an alternating 01-path is NP-hard for the general graph. Indeed, looking for such a path of length $m = |E|$ is equivalent to finding an alternating Hamiltonian path which is known to be NP-hard. This problem is easy for cycles of course.


Combining two infinite algorithms to create a single infinite algortihm Suppose I have an algorithm $F$ that, given a numeric input $x$, generates an infinite sequence of numbers that converges to a $f(x)$, where $f$ is some continuous real-valued function.

Similarly, I have an algorithm $G$ that, given a numeric input $y$, generates an infinite sequence of numbers that converges to $g(y)$, where $g$ is another continuous real-valued function.

I would like to have an algorithm $H$ that, given $x$, generates an infinite sequence of numbers that converges to $g(f(x))$. How can I do this?

My current idea is as follows. For every algorithm $A$ and integer $i$, let $A_i(x)$ be the $i$-th value in the sequence returned by algorithm $A$ when run on input $x$.

Then, the algorithm $H$ should return the sequence:

$$G_i(F_i(x))$$

Initially, $H$ runs a single step of $F$ on $x$ and runs a single step of $G$ on the result. Then, $H$ runs two steps of $F$ on $x$ and runs two steps of $G$ on the result. This goes on infinitely.

Is this idea correct? Is there a better idea?

Is this idea correct?

(I apologize for my initial, poorly thought-out response to this question, and thank the commentors for pointing out the flaws.)

Your solution will work if $g(\cdot)$ is differentiable around $f(x)$.

Since $G(y)$ converges to $g(y)$, for any constant $\epsilon_G>0$ there exists some $N_G>0$ such that for any $y$ and all $i>N_G$,
$$-\epsilon_G < G_i(y)-g(y) < \epsilon_G.$$

If $g(\cdot)$ is differentiable around $f(x)$, there exists constant $\epsilon_f>0$ such that $g(y)$ slopes toward $g(f(x))$ for all $y \in \left(f(x)-\epsilon_f, f(x)+\delta_g\right)$. Because $F$ converges to $f(x)$, there exists some $N_F>0$ such that for all $i>N_F$,
$$-\epsilon_f< F_i(x) - f(x) < \epsilon_f.$$

Since $g(\cdot)$ slopes toward $f(x)$ in the neighborhood containing all $F_i(x)$ for $i>N_F$, as $F(x)$ approaches $f(x)$, $g(F(x))$ approaches $g(f(x))$; i.e., $g(F_i(x))$ converges to $g(f(x))$. That is, for any $\epsilon_g>0$, there exists some $N_g>N_F$ such that for all $i>N_g$,
$$-\epsilon_g < g(F_i(x)) - g(f(x)) < \epsilon_g.$$

Now let $y=F_i(x)$. For any $\epsilon>0$, set $\epsilon_G = \epsilon_g = \frac{\epsilon}{2}$. Then for all $i>N$ (where $N=\max(N_G, N_F, N_g)$),
$$-\epsilon = -(\epsilon_G+\epsilon_g) < G_i(F_i(x))-g(F_i(x)) + g(F_i(x)) - g(f(x)) < (\epsilon_G+\epsilon_g) = \epsilon,$$
or,
$$-\epsilon < G_i(F_i(x)) - g(f(x))) < \epsilon.$$
That is, $G_i(F_i(x))$ converges to $g(f(x))$.

Is there a better idea?

Probably. Your algorithm generates $O(i)$ numbers to create the $i$th output number.

Consider if the algorithms were finite (i.e., you stopped at the $n$th output). Then, you would run $F$ to $F_n(x)$, then run $G$ using this as your input. This would only take generating $O(n)$ numbers. Your problem is not finite, though.

However, you can choose some constant $c$ and only restart $G$ after every $c$ steps. That is, the $i$th output will be $G_i(F_{c\lfloor i/c\rfloor}(x))$. This will make the convergence less smooth, but it will help your running time; it will now only generate $O(i/c)$ (amortized) numbers to create the $i$th output number.


The optimal way to find leaves in a weighted full binary tree Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b

How do I find optimal paths to all leaves from the root. I don't think classical graph traversals are helpful in this context as I don't need to visit all nodes.

Hint: How many paths are there from a given leaf to the root?


Understanding multi-variable big O (time complexity) I have something of this kind:

$$(n-1) d m + m + 2m*v+2v^2 + v$$

Where all n,d,m,v are variables.

My little knowledge of computational complexity leads to do this kind of approximation:

$$ O( (n-1) d m + mv + v^2 )$$

However I feel I could further simplify into

$$ O( n d m + mv + v^2 )$$

and

$$ O( n d m + v^2 )$$

hence

$$ O(v^2)$$

Are my assumptions correct?

can I remove the $-1$ from $(n-1)$?
can I remove $mv$ since $v$ will grow $v^2$ any way?

You can remove the $-1$ from $(n-1)$, since $(n-1)dm=ndm-dm\leq ndm$. On the other hand, you can not simplify beyond $O(ndm+mv+v^2)$ unless you know more about the relations between the variables. $mv$ and $v^2$ are incomparable, depending on the ratio between $m$ and $v$ one may grow faster than the other. Similarly, your last step (removing $ndm$ in favor of $v^2$) is also incorrect.


Potential method for dynamic binary search I'm trying to solve 17-2(b) problem from Cormen(CLRS) using potential method.

Problem from Cormen:

17-2 Making binary search dynamic
Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.

Specifically, suppose that we wish to support SEARCH and INSERT on a set
of $n$ elements. Let $k = \lceil \log_2(n + 1) \rceil$, and let the binary representation of n be $\langle n_{k-1}, n_{k-2}, \dots , n_0 \rangle$. We have $k$ sorted arrays $A_0, A_1, \dots, A_{k - 1}$, where for $i = 0, 1, \dots, k - 1$, the length of array $A_i$ is $2^i$. Each array is either full or empty,
depending on whether $n_i = 1$ or $n_i = 0$, respectively. The total number of elements held in all $k$ arrays is therefore $\sum^{k-1}_{i=0}n_i 2^i = n$. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other.

Describe how to perform the SEARCH operation for this data structure. Analyze its worst-case running time.
Describe how to perform the INSERT operation. Analyze its worst-case and amortized running times.
Discuss how to implement DELETE.

So I'm trying to solve point b.
Working time: we have $k = \log_2(n)$ sorted arrays $A_i$ and corresponding bits $b_i$. Size of array $A_i$ is $2^i$. If it's full then $b_i = 1$ else $b_i = 0$.

If first $r$ arrays are full then we can place all elements from them to empty array $A_r$. And we need $2^{r+1} - 2$ time(we merge first arrays: $2 \cdot (2^0 + 2^1 + \dots + 2^{r-1}) = 2^{r+1} - 2$).

Let potential function be $\Phi_i = 2^{r+1} - 2$, where r is number of first bits which are 1. For example, if we have bit string 111110110101 then $r=5$. If $r = 0$ then $\Phi_i = 0$.

Now suppose that we want to calculate amortized cost $\hat{c}_i$ when first $r > 0$ bits are 1. Thus, $\hat{c}_i = 2^{r+1} - 2 + (0 - (2^{r+1} - 2)) = 0$

If $r = 0$ then $\hat{c}_i = 3$.

So we can insert $n$ elements for $\mathcal{O}(n)$ time and they will be sorted. But this is contradicts to lower bound of compare-based sorting.

Could you please help me to find a mistake in my reasoning. I know that correct amortized time is $\hat{c}_i = \mathcal{O}(\log_2(n))$ if we use account method(I found the solution).

Thank you very much!

What about this potential function

$$\Phi = \sum_{i=0}^{k-1} n_i \cdot 2^i \cdot \left((k-1) - i \right),$$

where $k = \lceil \lg(n+1) \rceil$ (please check the details related to the stuff of $\lg$ and $\lceil \rceil$).

That is, each element in "depth" $n_i (i = 0, \cdots, k-1)$ has its "individual potential" $(k-1) - i$. The intuition is the higher the element is, the more potential it has and the higher price you pay to move it down (until the bottom). The whole potential of the data structure at any state is the sum of the potential of its all elements.

With this potential function, the amortized cost for the insertion of an element which does not cause any merge (i.e., the element is inserted into the empty subarray $A_0$) is

$$\hat{c} = 1 \quad (\text{actual cost for creation}) + (k-1) \quad (\text{increment of the potential function}) \\ = k = \lceil \lg(n+1) \rceil.$$

On the other hand, the amortized cost for the insertion of an element which causes $t$ merges is (please check the computation):

$$\hat{c} = 1 + \sum_{i=1}^{t} 2^t - (\sum_{i=0}^{i=t-1} 2^i (t-i)) \quad (\text{the potential decreases}) \\ = (2^{t+1} - 1) - (t(2^t-1) - (2^t t-2^{t+1} +2)) \\ = t + 1 \le k = \lceil \lg(n+1) \rceil.$$

Therefore, the amortized cost for each insertion is $O(\lg n)$.

Explanation for the decrement of the potential function $\sum_{i=0}^{i=t-1} 2^i (t-i)$:
First, each subarray $A_i,i=0,⋯,t−1$ contains $2^i$ elements. Secondly, each element in $A_i$ will be moved down to the $t$-th level subarray $A_t$, decreasing its potential by $t−i$, i.e., from $(k−1)−i$ to $(k−1)−t$. Summing them up, we obtain the total decrement of the potential function.


Finding maximal independent sets in an independence system An independence system is a collection $I$ of subsets of $\Omega$ such that if $A\in I$, then any subset of $A$ is in $I$. These sets are called independent.

Suppose I have an oracle for testing independence. In particular I have an ambient set $\Omega$ and an independence system $I$ of subsets of $\Omega$. I pass a subset $A$ of $\Omega$ to the oracle, and it tells me if $A\in I$.  Is there an efficient algorithm for finding all maximal independent sets?  I especially care about minimizing the number of calls to the oracle, which is expensive.

I implemented a brute force method (just looping over the powerset) which chokes for inputs sizes above about $n=6$. On the other hand, the Bron-Kerbosch algorithm solves exactly this problem in a special case, and my implementation of it runs quite happily up to around $n=30$. That would be plenty satisfactory to me.

This looks equivalent to finding all maximal zeroes of a monotone function, given ability to make oracle queries to the function.  Let $f:\{0,1\}^n \to \{0,1\}$ be a monotone Boolean function, and call $x$ a maximal zero if $f(x)=0$ and $f(y)=1$ for all $y\ge x$ (i.e., $y_i \ge x_i$ for all $i$).

This problem has been studied extensively.  I believe there are no known polynomial time algorithms.  See https://cstheory.stackexchange.com/q/14772/5038, Maximal Elements in a Lower Set, https://cstheory.stackexchange.com/q/18047/5038,
How to enumerate minimal covers of a set, and https://cstheory.stackexchange.com/q/14772/5038.  I think the concepts of learning DNF representations for monotone boolean functions and monotone dualization will be relevant. I confess I don't fully understand the literature and don't know if there are any algorithms that are good-enough-in-practice.

The relationship: Suppose $\Omega=\{1,2,\dots,n\}$.  We can identify the set $A$ with its characteristic vector, which is an element of $\{0,1\}^n$.  Now an independence system $I$ determines a function $f$ given by $f(A)=0$ if $A \in I$, otherwise $f(A)=1$.  You have oracle access to $f$, and want to find all maximal sets $A$ such that $f(A)=0$.


What is the point in hashing a value? I apologise if this is not the right place for this question... I didn't want to ask on Stackoverflow or CodeReview as it will closed in minutes as "too broad".

A client of mine is writing an API that takes a piece of personal-identifying information as the parameter in the URL, and has asked that the value is hashed using SHA512.

Normally when I deal with anything that involves personal information in this way, I'd encrypt it using a shared private key... but I'm really fuzzy on the whole idea of hashing.

My understanding of hashing was effectively...

take the input value and create a hash from it
when checking the value, create a hash from the new input value and compare them

What I'm struggling to understand (and I don't want to ask the client and show my ignorance) is how does the client take the hashed value and turn it back into the original input value?

And in particular, if the client can convert the hash back to the original input, what is stopping anybody else doing it?

And if other people can convert it back, what's the point in hashing it in the first place?

Update

After speak to the client, the answer (as many of you guessed) is that they are storing the hash of the PII in their database, and doing a match-search against the value I will be sending through.

The purpose of a hash in this scenario to be able to uniquely identify an entity.   It's not strictly unique, only probabilistically unique.

Hashes are not reversible functions, so your client can't know the data that was encoded with it.  It could be guessed by brute force and maybe some know attacks to the hash assuming the type/format of data is known, but in principle is not reversible).

So process A (system or organization) A can work with the facts of the entity uniquely identified by the hash without knowing the personal identity value.  Process A can then pass the processed information back to process B, that knows the personal identity value and then can combine the information given to Process A and the information it already has and carry out another processing.

The advantage in this case from a security perspective is that you have less security issues as process A (system or organization) will never has access to that personal identity.  Even if A is hacked, the personal data is safe*.