Given an array of size n, create a sub array with given conditions using dynamic programming We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level:
1. skip the number in original array and go to the next
2. insert the number in the start of the sub array
3. insert the number in the end of the sub array.
And at last we want the sub array to be the longest one that can be created with the conditions above and sorted.
For example we have A={10,3,13}
now we can insert 10 in the beginning, then 3 at the beginning and finally insert 13 in the end.
so the size of sub array is 3.

I know that I must solve this using dynamic programming but I do not know how to do it exactly.

In other words, the procedure produces two subsequences of the given array such that

the only shared element between the two is their first elements
one of them is non-decreasing.
one of them is non-increasing.

Let the given array be $a[0], a[1], \cdots, a[n-1]$. Here are the subproblems. $DP[i][j][[k]$ is the maximal number of elements in any such two subsequences such that their shared element is $a[i]$, the non-decreasing sequence ends at $a[j]$ and the non-increasing sequence ends at $a[k]$. Here $0\le i$, $i\le j\lt n$ , $i\le k\lt n$ and, unless $i=j=k$, $j\not=k$.

The wanted number is the maximum of all $DP[i][j][k]$.

The base cases are $DP[i][i][i]=1$, where $0\le i\lt n$.

What is the recurrence relation? $DP[i][j][k]$ is, basically, the larger of the following two numbers.

the maximum of $DP[i][\ell][k] + 1$ for all $\ell$ such that $i\le\ell\lt j$, $a[\ell]\le a[j]$.
the maximum of $DP[i][j][\ell] + 1$ for all $\ell$ such that $i\le\ell\lt k$, $a[\ell]\ge a[k]$.

How will we fill the 3-dimensional table $DP[i][j][k]$? Roughly, for a fixed $i$, we will find

$DP[i][i][i] = 1$,
then $DP[i][i][i+1]$ and $DP[i][i+1][i]$,
then $DP[i][i][i+2]$, (not including $DP[i][i+1][i+1]$ since $i+1 = i+1$) and $DP[i][i][i+2]$,
$\cdots$,
Finally, $DP[i][n-2][n-1]$ and $DP[i][n-1][n-2]$ (there is no $DP[i][n-1][n-1]$ for $i\not=n-1$ and $DP[n-1][n-1][n-1]=1$ is not helpful.)


Multiple knapsack problem with equal profit and different weight I am doing a research about the load balancing problem in 5G system, but I am not sure if my problem is a NP-complete problem.

The problem is:

given a set of n items and a set of m knapsack
capacity of knapsacks are equal
the weight of item j in knapsack i is w[i][j],that means weight of a item in each knapsack are different
each profit of items are equal

I am not trying to put all item in least knapsack like bin packing problem.
I saw some similar question answered, but no one is identical to this case.
In this case, the goal is to put as more as possible item with m knapsacks.
Is the problem a NP-complete problem?

This problem can be shown to be NP-complete via reduction from PARTITION. Simply take $m=2$, the weights of each item to be the same across both knapsacks, and the capacities of each knapsack to be half the total weight across all items.


Is there an algorithm to minimize working set during a topological traversal? I have a dependency graph of tasks, which forms a DAG. I'm looking for an algorithm to calculate the optimal topological traverse to minimize the "working set". Specifically, I define the current working set as the set of nodes which have been visited, and which have at least one outgoing edge which is untraversed.

Even more useful would be an algorithm to calculate the optimal topological traversal which minimizes the number of cache evictions, given a fixed size cache for the working set.

Is there an algorithm to calculate this topological traversal? I can do it greedily from the topological ordering, but suspect that's suboptimal.

Deciding if a topological ordering with working set of size $\le k$ exists is NP-complete, even in bipartite graphs.

We can reduce pathwidth computation to this problem. Let $G$ be a undirected graph, whose pathwidth we want to compute. Now create an directed graph $H$, with vertex $v'$ for each vertex $v$ of $G$. For each edge $(u, v)$ of $G$, create a vertex $e_{(u,v)}$ and directed edges $(v', e_{(u,v)}'), (u', e_{(u,v)}')$.

Now consider a topological ordering of $H$. Define the corresponding sequence of working sets as $X_1, \ldots, X_p$. We prove that $X_1, \ldots, X_p$ is a path-decomposition of $G$. The working sets include only vertices of type $v'$, because the other vertices do not have outgoing edges. The working sets by definition satisfy the intersection property $i \le j \le k \rightarrow X_i \cap X_k \subseteq X_j$. If there is an edge $(u, v)$ in $G$, then there are edges in $H$ from both $v'$ and $u'$ to $e_{(u,v)}'$ so there must be a working set $X_i$ with $v', u' \in X_i$. Therefore each edge is a subset of some bag of the path decomposition and therefore $X_1, \ldots, X_p$ is a path decomposition of $G$.

We can also show that any path-decomposition of $G$ corresponds to a topological ordering of $H$ (consider the elimination ordering of the underlying interval graph). $\square$

For positive results, I would suggest at looking at some analogies of pathwidth for DAGs in literature. With a quick search I found the notions of directed pathwidth and DAG-width, but seems that they are not relevant here as they are trivial for DAGs.


An almost surely finite time game of coin toss where you win with probability $p$ Given a fair coin and a number $p\in(0,1)$. How do you design a game that finishes in a finite number of tosses with probability $1$, and further, with probability $p$ you win the game?
I thought about random walks where head, you add 1, tail you subtract 1. And you want to get to $n$. But that gives an approximation to $p$ and not $p$.

Let $x_1,x_2,x_3,\ldots$ be the coin tosses, and let $p=0.y_1y_2y_3\ldots$ be the binary expansion of $p$. Halt once either of the following events happens:

$x_1=y_1,\ldots,x_{n-1}=y_{n-1}$ but $x_n < y_n$. In that case, declare a win.
$x_1=y_1,\ldots,x_{n-1}=y_{n-1}$ but $x_n > y_n$. In that case, declare a loss.

The game halts with probability $1$, since at any step it has a probability of $1/2$ to end. Let us now compute the probability of winning at the $n$'th step. If $y_n = 0$ then this event has probability $0$, and if $y_n = 1$ then it has probability $2^{-n}$. In total, the probability to win at the $n$'th step is $y_n 2^{-n}$. Since these events are disjoint, we deduce that the winning probability is
$$
\sum_{n=1}^\infty y_n 2^{-n} = p.
$$
What is happening here? We can imagine the coin being tossed infinitely many times, generating a value $q \in [0,1]$ whose binary expansion is $0.x_1x_2x_3\ldots \in [0,1]$. Clearly, $q$ is uniformly distributed in $[0,1]$. The game is a win if $q < p$ and a loss if $q > p$ (the probability that $q = p$ is zero). We can halt the game without generating all digits of $q$ if a prefix of its binary expansion suffices to determine that $q < p$ or that $q > p$.


Proving that a context-free grammar is unambiguous I have to find an unambiguous context-free grammar that generates the following language. $$L= \{ w \in \{a,b\}^+ : |w|_a = |w|_b\}$$
I think I have found the context-free one, it should be this one.
$$S \to aS'bS'|bS'aS'$$
$$S' \to aS'bS' | bS'aS' | \lambda$$
Now I am stuck with proving whether it is unambiguous or not. I think it is but how should I do that?

Consider the word $abab$. It has two derivation trees (rendered using syntree):

Hence your grammar is ambiguous. In order to make an unambiguous grammar, we have to force the parse to be unique. We identify the word with a path in which $a$ corresponds to $\nearrow$ and $b$ to $\searrow$. We're looking for a non-empty path that ends at level ground.

If the path starts with $\nearrow$, then we can look at the first time at which it returns to level ground, and decompose the path accordingly: $\nearrow x \searrow y$, where $x$ is a path that never goes below level ground, and $y$ is an arbitrary path that ends at level ground. Hence we need a way to capture paths that end at level ground and never go below level ground. Such a path can also be decomposed uniquely as $\nearrow x \searrow y$, where this time both $x$ and $y$ never go below level ground.

The considerations above lead to the following unambiguous grammar:
$$
\begin{align*}
&S \to aAbS' \mid bBaS' \\
&S' \to aAbS' \mid bBaS' \mid \lambda \\
&A \to aAbA \mid \lambda \\
&B \to bBaB \mid \lambda
\end{align*}
$$

As a somewhat degenerate example, the derivation tree for $abab$ is:

The proof that this grammar is unambiguous goes along the description above, though the formal proof by induction is somewhat challenging.


Why does the time/space tradeoff exist I'd like to know why when choosing how to optimize an algorithm that there almost always (always?) exists a time/space tradeoff.

Definition: https://simple.wikipedia.org/wiki/Space-time_tradeoff.

My favorite example is a karnaugh map for simplifying boolean logic. It abstracts boolean logic away with just clever geometry:

Is there some sort of law from some mathematical theory to explain why this exists? Intuitively it seems to make sense, but the math would be nice.

Is this some property of information/computation? Is it guaranteed for any computation that can be performed? What about computations theoretically possible with infinite time, is a reciprocal guaranteed to exist that instead uses infinite space (or a middle ground that makes the time axis not go to infinity anymore)?

It doesn't. You're biased to results you find interesting.

If we measure a particular algorithm's space $s$ and time $t$ complexity, and then improve the algorithm. One of the following things can and does happen:

We reduce $s$ and leave $t$ unchanged.
We reduce $t$ and leave $s$ unchanged.
We reduce both $s$ and $t$.
We reduce $s$ and $t$ increases. WOW!
We reduce $t$ and $s$ increases. WOW!

Now 1, 2 and 3 happen all the time. Why are you not asking for a "mathematical principle" for them?

Because they are boring. Since we strictly improved the algorithm it must mean the previous algorithm was suboptimal, and is immediately forgotten. Only in cases 4 and 5 we suddenly have two algorithms which do not have a clear winner, and only then do you start comparing them and wondering about a "mathematical principle" behind this difference.

What's happening is that given two objectives, you get a plot of possible solutions:

Anything above and to the right of the critical red line is immediately forgotten as non-interesting, as there are algorithms that are strictly better in both $s$ and $t$. Your mind only looks at the red line (also known as the Pareto frontier), ignoring the rest of the plot.


Can quantum computer become perfect chess player? Can quantum computer become perfect chess player?

Can it determine whether (when both players are perfect) win white or black? (or is it dead heat?)

I've already answered essentially this question, on Chess Stack Exchange. The executive summary is that chess doesn't seem particularly well-suited to quantum computation's strengths so there's no particular reason to believe that a quantum computer would be any better at it than a classical one.


Can you prevent a man in the middle from reading the message? I have heard about all these Man-In-The-Middle Attack preventions and I am wondering, how this can possibly work if the man in the middle only listens to your stream and does not want to change the message itself.

Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again?

How can a certificate prevent this?

Edit:

I have heard that the certificate authority generally says: "Yeah, that is the other ones key". But how can I be certain, that the signature of the certificate is not fudged?

Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again?

Yes, they can.

A key exchange protocol like (the "textbook" version of) DH is secure against eavesdropping (i.e., simply observing what is being transmitted on the channel), but completely breaks down against man-in-the-middle (MITM) attacks, as you have stated.

Certificates are an attempt remedy this, but another problem arises: How can you ensure both parties receive the correct certificate? Obviously you cannot just send the certificates over the insecure channel since this is again susceptible to a MITM attack.

The solution is the existence of an alternative, (completely) secure channel. This would be either the two parties meeting in person and exchanging their certificates physically or over some alternative, trusted channel (e.g., over telephone, if it can be trusted).

In computer networks, the alternative channel is usually a public-key infrastructure (PKI). This means your operating system or browser has a set of preconfigured root certificates from which other certificates are signed (and possibly even further certificates using these as intermediate certificates). Hence, when you visit some website, it presents a signed certificate, which is signed using (a chain of) certificates which you already trust. Then, by using this certificate, an authenticated key exchange is possible (e.g., to agree on an ephemeral key to use with ordinary symmetric encryption).


Can a classical supercomputer solve a large Max-Cut Problem? The Fugaku is the most powerful computer. Its performance is 442,010 TFlop/s. That number does not mean much to a layman like me. I want to know how fast it can solve a hard problem. For example, can it solve the Max-Cut Problem of 1,000 vertices in minutes, hours,...,years?
By the way, what is the best record of solving the Max-Cut Problem by any classical computers?

It's not that straightforward. NP-hardness means worst case intractability. This means that there are plenty of easy instances of Max-Cut with a huge number of vertices (i.e. much more than just one thousand), but also rather tiny instances that are extremely hard in practice. So you can't measure hardness by the size of an instance.
If you want to see examples & runtimes, have a look at the results from the yearly competitions around the Boolean satisfiability problem (SAT).


How to create an algorithm when given the invariant I am given the following invariant:

Invariant The greatest $i$ keys of an Array are always in sorted order on the last $i$ indices of the Array.

I am supposed to create a sorting Algortihm using this invariant. But I seem to have understood the concept of an Invariant differently, because with the information I find online, I can't find an idea for starting this problem.
Do I have to create an algorithm that sorts the first $n-1$ elements in the array? Thanks for your help

Observations:

For $i=0$, you don't know anything about the array.
For $i=n$, the array is sorted.

So the idea is to go from $i=0$ to $n$ while maintaining the invariant. This is similar to an inductive proof; in fact, you'll get an inductive algorithm.

Start with the input array and $i=0$; clearly, the invariant is maintained.
For some $i \geq 0$, assume that the invariant holds. What do you do to ensure the invariant holds for $i+1$?

I'll let you take it from here.


How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem? $\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
                           $\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt
                           $\mid \textbf{other} $

This grammar is called as Dangling Else Problem . However the ambiguity is resolved by parser as described as follows

  In all programming languages with conditional statements of this form, the first parse tree is preferred.
  The general rule is, "Match each else with the  closest unmatched then"

It is rarely built into productions

$\textbf{stmt} \to$ $ \textbf{matched_stmt}$
                          $\mid $ $\textbf{open_stmt}$

$\textbf{matched_stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ matched_stmt $ \textbf{else}$ matched_stmt
                          $\mid $ $\textbf{other}$

$\textbf{open_stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
                           $\mid $ $\textbf{if}$ expr $ \textbf{then}$ matched_stmt$ \textbf{else}$ open_stmt

However this grammar is also ambiguous . Moreover no grammar is there that could eliminate ambiguity problem of Dangling else problem . Hence we can say that dangling else problem in also inherently ambiguous

Source : Compilers: Principles, Techniques, & Tools -Aho & Ullman

My question is How to prove that  Ambiguity is still present  in this resolved Production of Dangling Else Problem   ? What I know is that if two different parse trees are possible then the grammar in ambiguous . Does any such parse trees possible for the resolved grammar ? If so could u please give an example parse tree for the same

A grammar $G$ for a language $L$ is ambiguous if there is a string $w \in L$ which has two different parse trees (with respect to $G$). Hence in order to show that ambiguity is still present, all you have to do is to come up with a string generated by your grammar that has two different parse trees.


Check if a NFA accepts a string of non-prime length Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number.

My obvious [edit: wrong] answer is that, if $A$ has $n$ states, then I can simply check if it accepts any word of composite length $\le n$. This violently works, since the input alphabet is defined as finite.
Is there a more refined solution? And would that entail some involved graph search?
P.S. To give some context, this comes from an exercise that previously asked to find algorithms that solved the emptiness problem for regular languages, and the problem of equivalence between two NFAs. I solved those in an analogously simple fashion.

The basic idea is that if a regular language is infinite, then it contains a word of infinite length. Indeed, the pumping lemma shows that the set of lengths of words in the language contains an arithmetic progression, and every arithmetic progression contains a composite integer.
We can check whether the language accepted by an NFA is infinite as follows:

Remove all states which are unreachable form an initial state, or from which a final state cannot be reached.
Check whether the remaining graph contains a cycle.

If the language is infinite, you can immediately answer "Yes". Otherwise, the NFA only accepts words of length at most $n-1$ (where $n$ is the number of states), and you can use the algorithm that you suggest. Your algorithm can be slightly optimized by identifying all letters in the alphabet.


Proving simple bound on coupon collector I came across this paper which gives bounds on coupon colloector problem. Page 451 contains a table where reference to U1 is given as 'folklore'. I presume this is trivial to follow from the definition but I can't see the logic behind this. Does anyone have hints for me? I tried to get this bound by taking the limit of probability that some coupon is not found after n tries but that needs n to be infinity.

Divide the process into $n$ phases. The $m$th phase ($m=1,\ldots,n$) starts when the $(m-1)$st cell has been occupied, and ends when the $m$th cell has been occupied. The first phase takes time $1$. Suppose that the occupied cell is $i_1$. The second phase then takes expected time $1/(1-p_{i_1})$. Suppose that the occupied cell is $i_2$. The third phase then takes expected time $1/(1-p_{i_1}-p_{i_2})$. And so on. Overall, the expected time is
$$
1 + \frac{1}{1-p_{i_1}} + \frac{1}{1-p_{i_1}-p_{i_2}} + \cdots + \frac{1}{1-p_{i_1}-\cdots-p_{i_{n-1}}} = \\
\frac{1}{p_{i_1}+\cdots+p_{i_n}} + \frac{1}{p_{i_2}+\cdots+p_{i_n}} + \cdots + \frac{1}{p_{i_n}} \leq = \\
\frac{1}{np_1} + \frac{1}{(n-1)p_1} + \cdots + \frac{1}{p_1} = \\
\frac{H_n}{p_1} \leq \frac{\ln n + 1}{p_1}.
$$


Is there any example of Regression Tree driven optimization (or active learning)? Bayesian Optimization is the classic example of meta-model driven optimization where new observations are used to train a Gaussian process that provides a clue to where to optimize next.

LEM (Learnable Evolution Models) are evolutionary models where rather than recombining observations (like GAs) a population is fit to a classifier to find out which areas are more promising (although the method itself has quite a lot of non-statistical operations on top of this).

I was looking for something simpler where the optimization is driven by a simple regression tree (sample from most promising leaf or through some bandit algorithm on the leaves). However I can't seem to find any reference on the subject. It must have been tried before.

An active learning approach using which combines an incrementally-learned Regression Tree with bandit-style sampling from leaf nodes to determine which instance to request a label for next is described in the “Adapting to Concept Drift in Credit Card Transaction Data Streams Using Contextual Bandits and Decision Trees” paper (disclaimer: I'm an author on the paper).

A short summary:

A regression tree is learned to predict targets $\hat{y}$ based on feature vectors $x$. This is done with an incremental tree learner, it can grow over time as labelled data becomes available (for instance due to active learning)
Every node in the regression tree also contains linear models that are trained such that we can additionally distinguish between different instances within the same leaf nodes. Training linear models in all nodes, rather than only the leaf nodes or only the root node, allows us to both generalize across the tree as well as specialize for subsets of the tree.
Predictions made by linear models be treated as "ground truth" labels for unlabelled instances and plugged into the Regression Tree Learner to allow the tree to grow more quickly than it could if we only used data with real labels (Semi-Supervised Learning).
Leaf nodes are treated as arms of a Contextual Multi-Armed Bandit (contextual because we also happen to have feature vectors for instances drawn from leaf nodes)
A Contextual Multi-Armed Bandit algorithm is used to select unlabelled instances for which we'd like to obtain labels (i.e. active learning)


Compression of sequence with Direct Access I have a sequence of $n$ integers in a small range $[0, k)$ and all the integers have the same frequency $f$ (so the size of the sequence is $n = f * k$). What I'm trying to do now is to compress this sequence while providing random access (what is the $i$-th integer). I'm more interested in achieving high compression at the expense of higher random access times.

I haven't tried with Huffman coding since it assigns codes based on frequencies (and all my frequencies are the same). Perhaps I'm missing some simple encoding for this particular case.

Any help or pointers would be appreciated.

Thanks in advance.

You can use the so-called "binomial encoding", described in one of my answers on math.stackexchange. You have to consider, though, whether it will be worthwhile. The naive encoding takes $n \log_2 k$ bits, and the best encoding saves about $O(\log n)$ bits (the best encoding uses $\log_2 \frac{n!}{f!^k}$ bits). Plug in your actual numbers to see what kind of saving you can expect.

Edit: I can't find my supposed post on math.stackexchange, so here is a summary of binomial coding (or rather multinomial coding), as it applies in this case. For a vector $x$ of length $k$, define
$$ w(x) = \frac{(\sum_i x_i)!}{\prod_i x_i!}. $$
Note that for $x \neq 0$,
$$ w(x) = \sum_{i\colon x_i > 0} w(x-e_i), $$
where $e_i$ is the $i$th basis vector. For example, if $k = 2$ and $x_1,x_2>0$ then
$$ w(x_1,x_2) = w(x_1-1,x_2) + w(x_1,x_2-1). $$
This is just Pascal's identity
$$ \binom{x_1+x_2}{x_1} = \binom{x_1+x_2}{x_1-1} + \binom{x_1+x_2}{x_1}. $$

For every vector $x$ and every $i$ such that $x_i > 0$, define
$$ w(x,i) = \sum_{j < i\colon x_j > 0} w(x-e_j). $$
Given a sequence $\sigma$ of letters in $\{1,\ldots,k\}$, let $H(\sigma)$ be its histogram, a vector of length $k$. For a non-empty word $\sigma \neq \epsilon$, let $\sigma_1$ be the first symbol, and $\sigma_{>1}$ be the rest, so that $\sigma = \sigma_1 \sigma_{>1}$. We are now ready to define the encoding:
$$ C(\sigma) = \begin{cases} w(H(\sigma),\sigma_1) + C(\sigma_{>1}) & \sigma \neq \epsilon \\ 0 & \sigma = \epsilon. \end{cases} $$
$C(\sigma)$ is an integer between $0$ and $\frac{n!}{f!^k}-1$.

Here is an example, with $k=f=2$. Let us encode $\sigma = 0101$:
$$
\begin{align*}
C(0101) &= w((2,2),0) + w((1,2),1) + w((1,1),0) + w((0,1),1) \\ &=
0 + w(0,2) + 0 + 0 = 1.
\end{align*}
$$
You can check that the inverse images of $0,1,2,3,4,5$ are
$$
0011,0101,0110,1001,1010,1100.
$$
These are just all the solution in increasing lexicography order.

How do we decode? By reversing the encoding procedure. We know the initial histogram $H_1$. Given an input $c_1$, we find the unique symbol $\sigma_1$ such that $w(H_1,\sigma_1) \leq c_1 < w(H_1,\sigma_1+1)$. We then put $H_2 = H_1 - e_{\sigma_1}$, $c_2 = c_1 - w(H_1,\sigma_1)$, and continue. To test your understanding, try to decode $0101$ back from its encoding $1$.


Where can I find good study material on Role Mining? I need to cover these topics in Role Mining. If anyone knows good site which well summarizes the topics and concepts are well explained please help out.

Basic role mining problem
• Delta-approx RMP
• Min-noise RMP
• Nature of the RMP problems
• Mapping RMP to database tiling problem
• Minimum tiling problem
• Mapping min-noise RMP to database tiling problem
• Mapping RMP to minimum biclique cover problem

The paper The Role Mining Problem: Finding a Minimal Descriptive
Set of Roles by Jaideep Vaidya, Vijayalakshmi Atluri and Qi Guo covers the basic definitions and some variants and includes a mapping to the minimum tiling problem. This is explored in more detail in the third author's PhD thesis (found by Googling "A formal approach to the role mining problem.)

An alternative formal definition of the Role Mining problem is found in the paper On the Deﬁnition of Role Mining by
Mario Frank, Joachim M. Buhmann, and David Basin. This is another good starting point;  it also contains references to much of the earlier work.

These tutorial slides cover many of the topics you mention. They also contain a load of references for you to follow up. The author of these slides has a small page describing the basics of role mining.

Optimal Boolean Matrix Decomposition: Application to Role Engineering by Haibing Lu, Jaideep Vaidya and Vijayalakshmi Atluri covers basic RMP along with min-noise RMP, $\delta$-approximate RMP and edge-RMP using boolean matrix decomposition as the basic formalism.


How is this formula for dynamic array reached? I am reading through Skiena's "The Algorithm Design Manual". He analyses the number of copy operations performed in a dynamic array.

  "Suppose we start with an array of size 1, and double its size from $m$ to $2m$ each time we run out of space. This doubling process involves allocating a new contiguous array of size $2m$, copying the contents of the old array into the lower half of the new one. The apparent waste is in the recopying of the old contents, on each expansion."

Skiena then asks:

  "How many times might an element have to be recopied after a total of $n$ insertions?".

He then gives a formula for calculating the total number of movements $M$, for $n$ insertions, which is

$$\mathbf{M}=\sum_{i=1}^{\log n} i\cdot\frac{n}{2^i}.$$

His explanation is:

  "Well, the first inserted element will have been recopied when the array expands after the first, second, fourth, eighth, ...insertions. It will take $\log_{2}n$ doublings until the array gets to have n positions. However, most elements do not suffer much upheaval. Indeed, the $(n/2 + 1)$st through $n$th elements will move at most once and might never have to move at all."

But I really don't understand how he draws the formula from that. Can anyone help me understand how he reaches it? Mainly what I can't understand is why he is multiplying $\frac{n}{2^i}$ by $i$.

Let's look at the moment just after we copy the array to insert element $2^k + 1$, so we're doubling the array size from $2^k$ to $2^{k+1}$. There are $n = 2^k$ elements in the array at this moment.

The first term in the sum is $1 \cdot n/2$, representing the fact that $n/2$ elements (namely, elements $(n/2+1), \ldots, n$) have been copied exactly once (just now!).

The next term is $2 \cdot n/4$. The previous $n/4$ elements - that is, elements $(n/4) + 1, \ldots, n/2$ - will have been copied exactly twice, once just now and once when we expanded the array from size $n/2$ to $n$.

The next term is $3 \cdot n/8$. The previous $n/8$ elements will have been copied three times: now, at the last expansion and at the second-to-last expansion when we expanded from size $n/4$ to $n/2$. You can probably see where this is going by now.

The thing to remember is that each element gets copied every time the array expands after the element in question has been inserted, and the copies happen every time the size exceeds a power of two.


Picking the most cost efficient sets I have two 2D arrays: $P[n][s]$ and $C[n][s]$, $s \leq n$.
P contains sets of nodes and $C$ the cost of a set in $P$, e.g. the cost of $P[2][2]$ is $C[2][2]$ and a set $p \in P = \{ s_0, s_1, ..., s_{n-1} \}^q, q \leq n$, e.g. $p=\{s_0, s_3\}$.
For every row I can pick at most one set but in the end the union of the picked sets needs to contain all nodes $\{s_0, s_1, ..., s_{n-1} \}$.
How do I find the least expensive picks in linear time?

If you are able to find the least expensive picks in linear (or even polynomial) time then $P=NP$.
Your problem is a generalization of the set-cover problem: given a set $X$ of items and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^X$ of subsets of $X$, find $S' \subseteq S$ such that $\cup_{S_i \in S'} S_i = X$ and $|S'|$ is minimized.
This is exactly your problem once you set $n=|X|$, $s=1$, $P[i][1] = S_i$, and $C[i][1]=1$.


Complexity classes of undecidable Turing Machines I'm finding it difficult to find the information online and I can't find the information in my college notes but i'm wondering what complexity-class languages like Atm and Halttm (The TM that always accepts, the TM that always halts respectively) are in. If anyone could explain which class they're in an why that would be great.
Also what about languages like NEtm(langague of TM no equal to null). What langague would that fall into and why. Thanks in advance

The correct measure for the complexity of undecidable problems is the arithmetical hierarchy and its extensions. Undecidable problems sit outside all of the complexity classes defined by time or space constraints.


What is the XNOR of 3 or more inputs? We know that for 3 variables (A=0,B=1,C=1), f$_1$ = (A XNOR B XNOR C) = 1, since the input has even number of 1's.

But if we were to do this step by step, f$_2$ = (A XNOR (B XNOR C)) = (A XNOR (1 XNOR 1))

Now, 1 XNOR 1 = 1. So, f$_2$ = (A XNOR 1) = 0 XNOR 1 = 0.

Why is f$_1 \neq$ f$_2$ ?

Also, which is true : "XNOR operation gives a value of 1 for " : Even number of 1's in the input OR Even number of 0's in the input. (Sorry, but a certain professor implied the later, so have to confirm).

There is no standard definition for the XNOR of more than two inputs (indeed, nor is there a standard definition for less than two inputs). Since XNOR is associative, one possible definition is
$$
A_1 \text{ XNOR } A_2 \text{ XNOR } \cdots \text{ XNOR } A_n = A_1 \text{ XNOR } (A_2 \text{ XNOR } (A_3 \cdots )\cdots).
$$
Another reasonable definition defines the XNOR of $A_1,\ldots,A_n$ as the negation of the XOR of $A_1,\ldots,A_n$. Both definitions agree with the usual definition of XNOR when $n = 2$, or indeed when $n$ is even, but give complementary results when $n$ is odd.

The XOR of a given number of inputs is $1$ if the number of $1$s in the input is odd. Given that you can work out a similar formula for the XNOR of any number of inputs, under both definitions.


Proving grammar only generate strings that is multiple of 3 Hello I have an exercise for homework and I was hopping to get some hints in order to solve it.

num-> 11 | 10 num' 01 | num 0 | num num
num'-> 00 num' | 1 num' | ε

I need to prove that my grammar produces only strings that is multiply of 3.
What i know is:

11 is 3 so no problem there
adding 0 to the end of the num is irrelevant because it will be still dividable by 3.
same with num num
I know that is something about the 10 num' 01 pattern. (1001 is divided by 3)

I was thinking to try to prove it with sums (this is how i solve a previous exercise). However i am not sure that i can solve it that way.

Hint: num' generates (1) numbers of even length which are divisible by 3 and (2) numbers of odd length which equal 1 mod 3. For the rule num → 10 num' 01, consider the parity of the length of the number generated by num'.


Order of storage of pointers for a linked list of length n I have a linked list in which I have kept the elements in order (increasing/decreasing). I want to be able to perform a binary search on this linked list. For this I am keeping pointers to the middle element of list of length n, n/2, n/4 so on. I am not able to figure out what would be the order of storage in this case. Any ideas?

Let $T(n)$ be the number of middle-of-list pointers you need to store for a list of length $n$.  For a list of length $n$, you need to store one pointer to the middle, plus however many middle-of-list pointers you need for the first half, plus however many you need for the second half.  This gives
$$T(n) = 1 + 2T(n/2)\,,$$
and we can take $T(1) = 0$, since a list of length $1$ probably doesn't need a middle-of-list pointer.

We have a reference question on formally solving recurrences like this but, for a rough-and-ready approach, we see that $T(2)=1$, $T(4)=3$, $T(8)=7$ so it's pretty clear that $T(n)=O(n)$ and, more to the point, $T(n)$ is about equal to $n$.

Well, now we wonder if a linked list was really the right data structure to be using.  First off, programming a linked list with middle-of-list pointers seems to be quite difficult.  Appending an item to the list sounds like it'll be awkward because you have all those pointers to update. Actually, I'm not sure what the data structure would even look like. But, anyway, maintaining the middle-of-list pointers costs us time so we'd better hope get something back for our investment of time, such as a saving in space.  Nope. Storing the linked list needs about $n$ "next" pointers and about $n$ middle of list pointers, for a total of about $2n$. But just storing your data in a binary tree would require $n$ nodes, each with a pointer to the left child and one to the right child, again giving a total of $2n$ pointers.


Interpretation of "expected cost" of an algorithm I'm studying randomized algorithms and I sometimes come across results like

  (1) The algorithm has an expected $O(f(n))$ cost.

and

  (2) With constant probability, the cost is bounded by $O(f(n))$.

I'm perfectly fine with statements like (2), but I'm puzzled to what extent a statement like (1) is useful:
For certain probability distributions of a random variable, the expected value itself occurs with less than constant probability; for other distributions, it occurs with $1-1/n$ probability. Of course, in many cases, (1) is extended via concentration bounds to show high probability, but in cases where this isn't done, it doesn't seem that a statement on the "expected cost" lets us derive any implications on the actual performance of the algorithm, right?

If you have a cost of $1$ with probability one half and $0$ with probability one half, you never reach the expected cost of $\frac{1}{2}$.

But what the expected cost gives you is the average of costs. If you repeat the algorithm and make the average of the cost (after an infinite number of times) you will get an average cost equal to the expected cost.

I hope it's clear ...


Log-space reduction - How to calculate overall space needed? Assume A, B are two decision problems. Given a reduction from A to B that uses log^c1(n) space and an algorithm that solves B in log^c2(n) space, Can we determine some lower bound to the space needed by an algorithm which solves A using this reduction?

The answer depends on how large the output of the reduction $f$ is. Usually, in the context of log-space reductions, there are two main variants of composing reductions (or, in this case, composing a reduction with an algorithm solving the reduced problem directly). Goldreich ("Computational Complexity: A Conceptual Perspective") names these naive and emulative compositions, though I don't believe there is a widely agreed terminology for them. (Please correct me if I'm wrong.)

Let $x$ denote a problem instance of $A$.

Naive composition. If $|f(x)|$ is small, then we can compute the entirety of $f(x)$ and then apply the algorithm solving $B$, reusing the space used to compute $f$. This means the space complexity is on the order of
$$\max(\log(|x|)^{c_1}, \log(|f(x)|)^{c_2}) + |f(x)|$$
plus some minor factors to organize things (e.g., keep track of whether we are performing the reduction or running the algorithm solving $B$).

Emulative composition. If $|f(x)|$ is large, then it makes sense not to generate the entirety of it in a single batch but, rather, to generate it bit-by-bit on the fly (i.e., as the algorithm solving $B$ needs it). Hence, whenever the algorithm solving $B$ needs bit number $i$ of $f(x)$, we run the reduction from scratch up to the point where bit number $i$ is produced and then pass this over to $B$. This means $f(x)$ is a virtual value which we provide to the algorithm for $B$ only on a bit-by-bit basis. Reusing space like this gives a space complexity on the order of
$$\log(|x|)^{c_1} + \log(|f(x)|)^{c_2} + O(\log(|f(x)|))$$
plus some minor factors, as before (e.g., to keep track of what bit of $f(x)$ we have last provided). Note how this is a big improvement whenever $|f(x)|$ is large.


Is it possible to use an adjacency matrix for Bellman-Ford algorithm? I have created a function that generates a complete, directed, and weighted graph, represented in an adjacency matrix but most Bellman-Ford implementations use an adjacency list. Is it even possible to use an adjacency matrix for Bellman-Ford without increasing significant time complexity? What would be the simplest way to use my graph-generating algorithm to the Bellman-Ford algorithm? Am I required to convert my matrix into a list?

It is possible to use an adjacency matrix, but you will increase the runtime in most cases.
The main core of the algorithm is, that you iterate over all edges and try to relax the distance approximations.
If you have an adjacency list, you can efficiently iterate over all edges in $O(|E|)$ time, and get the the worst case complexity $O(|V| \cdot |E|)$ in total.
If you however use an adjacency matrix, in most cases you cannot iterate over all edges as efficiently. You could iterate over all entries in the matrix, and check for each one if the edge exists (e.g. check if the distance stored is infinity), however that will require $O(|V|^2)$ time and therefore lead to a total complexity of $O(|V|^3)$.
If you have a dense matrix $|E| \approx |V|^2$, then this will result in the same time complexity $O(|V| \cdot |E|) = O(|V|^3)$, but if you have a sparse graph, $|E| \approx |V|$, then iterating over all edges will take significant slower and you get the complexity $O(|V|^3)$ even though with a with an adjacency list you would have the complexity $O(|V| \cdot |E|) = O(|V|^2)$.
So it would be better, to simply convert the adjacency matrix into an adjacency list, or just a simple list of all edges.


Difference between multi-agent systems and distributed systems What is the difference between multi-agent systems (MAS) and distributed systems, in the context of control with agents?

What is the difference between multi-agent systems (MAS) and distributed systems, in the context of control with agents?

Multi Agent System
According to the book;  Innovations,theories in  multi agent systems and applications, September,2015

It states that in multi agent system,agents have the ability to solve complex real world problems besides being autonomous and interlinked. thus exhibiting some intelligence

Therefore,MAS falls under the umbrella of Distributed Artificial intelligence.e.g. Autonomous cars,SoftBots to mention but a few.

On the otherhand in Distributed systems,agents perform a specific task with the centralised agent taking control of the goal,that's achieved.e.g cellular network applications controlled by NOC,aircraft system that is controlled by Area Control Centres.

Therefore,Distributed systems,fall under the umbrella of  Distributed Computing


Master theorem for $T(n) = 2T(n/2) + n^{2}\log n$ Would I use the third case of the Master Theorem for the recurrence equation $T(n) = 2T(n/2) + n^{2}\log n$?

The condition given for the third case by Wikipedia is $f(n) = \Theta(n^c)$ when $c > \log_{b}a$.

Yes and no. The form of the Master Theorem given on Wikipedia is a bit more restrictive than a fuller version of the theorem, essentially limiting itself to the cases where $f(n)$ is a polynomial.

In this case, where $f(n) \notin \Theta(n^{c})$ for any $c$ (though we do have $f(n) \in \Omega(n^{2})$ and $f(n) \in O(n^{2+\varepsilon})$ for any $\varepsilon > 0$), the condition given on Wikipedia is insufficient.

A more useful (but slightly mathematically harder to work with, sometimes) formulation can be found in Cormen et al.'s "Introduction to Algorithms", or in this convenient worksheet from MIT.

The third case in this version is now

  If
  $$
f(n) \in \Omega(n^{\log_{b}(a)+\varepsilon}) \text{ with } \varepsilon > 0
$$
  where $f(n)$ also has to satisfy a "regularity condition":
  $$
a f(\frac{n}{b}) \leq cf(n) \text{ for some } c>1 \text{ and } n \text{ large enough}
$$
  then
  $$
T(n) \in \Theta(f(n))
$$

For the recurrence $T(n) = 2T(\frac{n}{2})+n^{2}\log n$, we have $\log_{b}a = 1$, so we can pick any $\varepsilon \in (0,1]$ (say for the sake of argument we pick $\varepsilon = 1$) and we have $f(n) \in \Omega(n^{1+\varepsilon}) = \Omega(n^{2})$.

Thus we can conclude $T(n) \in \Theta(n^{2}\log n)$.

In this case we don't need to worry too much about the regularity condition as $n^{2}\log n$ is well behaved - the condition is there to stop tricky things like the ones mentioned in the Wikipedia article, such as $f(n)=n\cdot(2-\cos n)$.


Hardness of maximizing difference of functions Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP_HARD. What can be said about the problem of maximizing $f-g$, with $g$ being another function over $D$? Is it possible to characterize $g$ in relation to $f$ in a way that can be assured that maximizing $f-g$ is also NP-HARD?

I suspect there's not likely to be any characterization that is very useful.  The optimization problems can be hard or easy depending on $g$.
To give an analogy: you could ask for a characterization of functions $f$ for which it is NP-hard to maximize $f$.  Well, you're probably not going to find a useful one.


Show that the language of strings not in the union of two regular languages is regular Given languages $L_1,L_2$, defines $X(L_1,L_2)$ by

$\qquad X(L_1,L_2) = \{w \mid w \not\in L_1 \cup L_2 \}$

If $L_1$ and $L_2$ are regular, how can we show that $X(L_1,L2)$ is also regular?

There are several ways to show that a language is regular (check the question How to prove a language is regular?)

Specifically for the language in your question, start with DFAs for $L_1$ and $L_2$ and try to construct an NFA for $X(L_1,L_2)$ using them. More details below:

   Note that $X(L_1,L_2) = \overline{L_1} \cap \overline{L_2}$.
 From the DFA of $L_1$ construct the DFA of $\overline {L_1}$ (making any final state not-final, and vice-versa). Do the same for $L_2$.  Intersection of regular languages can be constructed via product machine (see this question).
 [Of course, if you already know that a complement of a regular language is also regular, and so the intersection of two regular languages – you are done without constructing those DFAs..]


Need help with this runtime of algorithm with double loops that results in 0 I know with absolute certainty that this is the wrong runtime, but I just wanted to show you how I got to it.

for (i = 0; i <= n; i++) do
     j = 2*i
     while j <= n do
         j = j + 1
         print("Hello World")
end

Then I get the runtime
$Θ(\sum_{i=1}^n 1 + n -2i)=Θ(n+n^2-n(n+1))=Θ(0)$??

The result you state is clearly wrong, since the second line (for example) runs $n+1$ times. The problem is in your sum, which you don't explain how you got to.
Here is the code again, with line numbers:
1: for i in 0,...,n:
2:   j = 2*i
3:   while j ≤ n:
4:     j = j + 1
5:     print "hello world"
6:   end while
7: end for

The running time heavily depends on the model. However, assuming that $n \geq 0$, the running time will be proportional to the number of times that lines 2 and 4 are executed. Line 2 is executed $n+1$ times. As for line 4, for a given value of $i$, it is executed $\max(n-2i+1,0)$ times (for example, if $2i = n$ it is executed once). In total, it is executed this many times:
$$
\sum_{i=0}^n \max(n-2i+1,0).
$$
In order to calculate this sum, it will be easier to consider separately the cases $n$ even and $n$ odd. If $n = 2m$ then the maximal $i$ for which $n-2i+1>0$ is $m$. Furthermore, the summand goes from $n+1$ down to $1$ in jumps of $2$; there are $m+1=n/2+1$ summands in total. Therefore the sum equals
$$
1 + 3 + 5 + \cdots + (n + 1) = \frac{(n/2+1)(1+(n+1))}{2} = \frac{(n+2)^2}{4} = \Theta(n^2).
$$
If $n = 2m+1$ then the maximal $i$ for which $n-2i+1>0$ is also $m$. This time, the summand goes from $n+1$ down to $2$, and there are $m+1 = (n+1)/2$ summands. Therefore the sum equals
$$
2 + 4 + 6 + \cdots + (n+1) = \frac{((n+1)/2)(2+(n+1))}{2} = \frac{(n+1)(n+3)}{4} = \Theta(n^2).
$$
In total, we get that the number of times that line 4 is executed is $\Theta(n^2)$ in both cases, and so $\Theta(n^2)$ overall (this is a subtle point, and requires a short argument).
We conclude that the total running time is $\Theta(n^2)$. (This may need the assumption $n>0$, depending on your exact definition; you can take $\Theta(n^2+1)$ if you want to be extra sure.)


Enumerating the set of polynomial time Turing machines I was checking this question and wondered how to apply it to the following language to prove it is in $RE$:
$$ L = \{ \langle M \rangle : \exists P \text{ such that } M \text{ halts on every input } w \text{ within } P(|w|) \text{ steps}  \},$$

where $P(x)$ is a polynomial with coefficients $a_1,\ldots,a_n \in \mathbb{N}$.

Those are the two approaches I am thinking of so far, in order to build a Turing Machine $M_L$ which accepts $L$ above:

Let $d$ be the degree of the polynomial $P$. For each $d=1,2,3,\ldots$, iterate over all possible $d$ coefficients, and check whether the current $P$ satisfies $L$'s condition above. I think it might work because if there is no such $P$, then the Turing machine $M$ won't stop and this is OK.
Here I am taking $P$ to be a constant (i.e. $P(x)=k \in \mathbb{N}$), and then iterate over all $k$ and apply the Turing machine from the question I linked at the beginning, where the language at the question above is in $R$ then there is a Turing machine $M_k$ which decides it, thus, while we get Rejection from $M_k$ for the $k$ values we're iterating on, $M_L$ does not stop.

I am not sure even where I made a mistake above, since the concept of iterating over all $k \in \mathbb{N}$ does not seems robust.

Does the approach of building a Turing machine work?
Since I could not get to a reduction which proves that $L \in RE$.

The halting problem reduces to $\overline{L}$: given a machine $T$, create a new machine that on input $n$ simulates $T$ for $n$ steps, and if $T$ halts then it enters an infinite loop. (I leave you the details.)

Since the halting problem is complete for $\mathsf{RE}$, it cannot be the case that $\overline{L} \in \mathsf{coRE}$, and so it cannot be the case that $L \in \mathsf{RE}$.


DFS algorithm and how do I show/put it into practice? I'm new to DFS algorithm and I'm trying to figure it out.

The main concepts I get from it is that you have a stack of nodes, and they have a value, and can contain children-nodes (Even called branches or leaves) that can contains nodes with values.

So let's say that I have a Tree containing 15 nodes like this.

I would understand that the algorithm goes A-N-O-B-D-J-L-M-K-C-E-F-H-G-I, If you were to go in alphabetic order.

My confusion is this how to put this algorithm into practice (such as coding it). How should I see this tree like (Array, List?)

And if some of the children are connected to each other can it still be a DFS algorithm?

The first thing you need to do is pick a data structure - i.e a representation for your node graph.  For this I suggest you pick up any undergraduate-level book on data structures and read it carefully, and choose something appropriate.  For example, given the tree above, I would represent each node with a record containing whatever data is to be stored in that node (e.g the name - A, B, etc) plus a list of (pointers to) child nodes.  E.g your root would have the list {A, B, C}, node A would have the list {N}, node J would have the list {K, L, M}, and so on.  Each childless node ('leaf') would have an empty list.

Then you code your DFS procedure, which you may find easier to do if you use recursion to process children (although there are ways to make this non-recursive if you insist).  Regardless of implementation, the core behavior of DFS is: To process each node, you must do something with the node, then scan the list of children and process each child -and its entire subtree- before processing the next child.  You can get different effects according to whether you process each node before its children, or after [if each node has at most two children AND explicitly distinguishes 'left' child from 'right' child, then there is also the option of processing each node -between- left and right].

And yes, you can still perform DFS if there are cross-connections.  The key new thing to do here is to keep track of whether the node you are about to process has already been processed; generally what you will want to do in that case is skip that node and go back up to the parent.  This is particularly true if 'children' really means 'neighbors', so the edges between nodes aren't directed; then you really need to avoid running in cycles.


Isn't Functional Programming just Imperative Programming in disguise? A YouTube video I was watching explained the differences between Imperative and Functional programming by demonstrating how the numbers from 1 to 10 are summed up in Java and in Haskell respectively.

In Java, you must explicitly state each step and assign the result of each step to a variable - something like the following

int total = 0;
     for (int i = 1; i <= 10; i++){
         total = total + i;
     }
return total;

In Haskell, you can simply say:

sum(1..10)

My question is: There obviously is something going on in the background of a Functional language, and that something must be some sort of Imperative process.
It seems like Functional Languages are really just some sort of Imperative-Language APIs.
For example, I can create part of a functional language by defining a method sum(int start, int end) in Java. Did I really create a new type of language right there, or did I just define a set of Imperative method calls that hide imperative instructions from you?

I hope it's clear what I am struggling to understand.

If we peel off the syntactic sugar on the front and the code generation on the back and compare what happens in between when converting source to running code for imperative languages, such as C or Java with functional languages such as ML or OCaml we will generally find the following differences in what, why, and how.

Mutable vs. immutable

With functional programming one tends to use immutable values which means that we don't have to worry if a value changes by a means external to our current function. When used correctly this removes any problems related to side effects.

Focus: Data versus function.

When one thinks of coding in imperative one first thinks of data structures and then what methods they need, when working with functional programming one first thinks of what functions are needed and then makes the data types needed. Most of the data types are either lazy list, (think stream or infinite list) or discriminated unions. When the discriminated union is recursive you instantly have created a tree or graph without having to write all of walking code.

Generics/Parametric polymorphism

This one is interesting, and if I have my facts correct, was invented with functional programming and then transplanted to imperative programming. So if you like generics thank the functional language designers.

Referential transparency/Parallelization

Because of referential transparency functional code can be more easily ported to parallel computing.

Higher order function/compositionality

Since functions can create new functions and return functions, creating new functions is based on other functions is as easy as creating new expressions instead of writing entire new methods. This leads to morphisms which are very useful if the problem you are solving can be expessed with math. Doing set transformations, think SQL and updates, is so much easier with functional programming. As Wandering Logic noted this is where functional programming languages excel.

Typing: Static versus inference.

Since the types are inferred as opposed being set by the programmer during writing, more checks can be to ensure the correctness of the code and often the functions will be made generic as opposed to being of a set type.

Pattern Matching vs switch statement

When combining matching with discriminated unions, your matching is checked to ensure you have covered every outcome. How many times have you had a run time error because you missed a case with a switch statement.


Is DSPACE properly contained in NSPACE? It may be a dumb question, but is $\mathsf{DSPACE}(f(n)) \subset \mathsf{NSPACE}(f(n))$ or is $\mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n))$?  In other words, is the containment relation proper or not?  Wikipedia says the first one, while the ComplexityZoo says the other one.

It's open whether $\mathsf{DSPACE}(\log n) = \mathsf{NSPACE}(\log n)$, which is the $\mathsf{L}=\mathsf{NL}$ question. As far as I know, the closest thing we can say are theorems by Savitch $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}(f(n)^2)$ and Immerman–Szelepcsényi's ($\mathsf{NSPACE}$ is closed under complement).

Also see AndrewK's answer regarding the subset symbol, I think this is the issue here.


Programming language where every expression makes sense Per recommendation I am reposting this from Stack Overflow.

Recently I have been thinking about following issue.

Consider the code for a standard "Hello world!" program:

main()
{
    printf("Hello World");

}

Now almost any change in this code will make it completely useless, in fact almost every change will prevent the code from compiling.
For example:

main(5
{
    printf("Hello World");

}

Now to the actual question.
Is there a programming language where every possible combination of symbols - that is, every expression - makes sense?
I tried thinking about some sort of solution and came up with two:

Postfix with a limited number of variables. Essentially all variables are already defined before you write any code and you have to work just with them.
Theoretically you can than perform an arbitrary number of operations by forming a chain of many simple programs, each one of them feeding results to others.
Code could be written as a series of characters in postfix notation;
"Postfix" with a stack of variables. Variables are stored on a stack; every operation takes two variables from the top and puts the result in their place.
The program ends when it reaches the last operation or variable.

Personally I hate both of these. Not only are they limited, they are inelegant.
They are not even real solutions, more like workarounds, essentially "offshoring" some work to an external process.

Does anyone have any other idea how to solve this problem?

Redcode, the assembly language behind codewars, was explicitly written to have very few halting instructions, because the code often gets mangled before it finally gives out, and the more opportunities it has to halt, the less interesting the game is.

You see very few such languages in practice because we don't just want a program to run, we want it to run in the way we expect.  If you can make a typo and change the way the program ran, it must be acceptably close to the original expected behavior, or the programmers with seethe in frustration.

There is some precedence for such things by using natural languages rather than formal languages, but it's not what I would call a large field when you compare it to the use of formal languages.  If you're interested in such programming languages, the natural language processing community is where I'd look.

Another field you could look at is genetics.  There are remarkably few genetic sequences which are simply invalid.  Plenty of them that aren't very effective at reproductions, but very few invalid ones.


What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems? Before asking the question, I should say that I am not sure here is a proper community to ask this question or not.
I have an NP-hard problem and an optimization to deal with the problem. Recently, I have found that the problem has a phase transition where, before a threshold for a property,  the problem can be solved in polynomial time by a greedy approach and, difficult cases are after the threshold.
Now, I want to show this phase transition by some parameters related to the optimization that solves the problem. But, I don't know which parameters can show this phase transition in a valid way, like time-solving, the number of iterations to solve the problem, or .....

There is no contradiction. NP-hard does not mean "large instances can't be solved quickly", rather, it means "there is an infinite number of instances that are hard". Large instances can be easy while small instances can be hard - it's the structure that counts and not size. Put differently, if a problem is NP-hard, it is believed that there is no algorithm which runs in polynomial-time (and is correct) on every instance. It is perfectly possible to have algorithms that are fast on particular instances.
So perhaps you misunderstood what phase transition means. Nevertheless, if you want to learn more about it, remember that it is relevant only for random instances.


I don't understand the case 4 of red-black tree deletion I don't know why case 4 will resolve the issue of the double black of $x$ described in Introduction to algorithm p.329. I know case 1 is transformed into one of {2,3,4} case, and case 2 re-point $x$ to its parent node so it's approaching the root, and case 3 will be transformed into case 4, but both case {3,4} will not change the pointer $x$, anyway so how case 4 work?

Is it because for paths include $C,E$ there is no difference about the number of blacks while for that about $\alpha,\beta$ an extra black node $B$ is passed?

but both case {3,4} will not change the pointer , anyway so how case 4 work?

Let us check case 4. Although the parent pointer of node $x$ is not changed, i.e., the parent node of $x$ is still $B$, the color of $B$ is set to black and node $D$ is lifted to become $B$'s parent with $B$'s original color.

So, going from the graph on the left hand side of case 4 on the image in the question to the graph on the right hand side, we have added that "extra" black node that was supposed to attached to $x$, which is, in your words, an extra black node $B$ is passed for the paths going through $\alpha,\beta$.

Furthermore, for that graph on the right hand side, we can check that all simple paths from the node to descendant leaves that do not pass through $A$ contain the same number of black nodes as before. Since all properties of black-red tree have been restored, case 4 ends the while loop, which ends RB-DELETE-FIXUP$(T, x)$, which ends RB-DELETE$(T, z)$.


Is $L = a^{n}b^{n+m}c^{m} | n,m \geq 0$ a context free or a recursive language? My initial thought is that L can't be context free since I can use the pumping lemma. I also don't think a grammar can be generated since it needs to keep track of the number of c's and a's. However, I'm having a hard time coming up with an algorithm for this language.

Here's a hint:

Could you make a grammar for $a^nb^n$, $n\ge 0$?
Could you make a grammar for $b^mc^m$, $m\ge 0$?
Could you make a production that concatenates the languages in (1) and (2) above?


Build-Max-Heap: Why Start i at floor(A.length/2) rather than A.length? Taken from CLRS third edition, a procedure is given for Build-Max-Heap

function a = build_MaxHeap(a)
for i = floor(length(a)/2): -1 : 1        // i = n downto 1
     a = max_heapify(a,i);
end

My question is why use floor(length(a)/2)? How is it different than using length(a)? Is this the same thing?

function a = build_MaxHeap(a)
for i = length(a): -1 : 1        // i = n downto 1
     a = max_heapify(a,i);
end

It isn't, neither from a complexity nor from a correctness point of view, however, by starting the counter at $n$ you are doing useless work.

Heapify is a procedure that, if invoked on a node $v$ such that the trees rooted in its children are binary heaps, turns the tree rooted in $v$ into a binary heap. Trees that contain only one node are trivially binary heaps, therefore, you may just start running the algorithm from the first non-leaf node: invoking heapify on the leaves wouldn't have done anything, anyway.


Poly-time reduction from ILP to SAT? So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP formulations (which function as reductions from those problems to ILP), because ILP is very usefully general.

Reductions from ILP seem much harder to either do myself or track down.

Thus, my question is, does anyone know a poly-time reduction from ILP to SAT, that is, demonstrating how to solve any 0-1 ILP decision problem using SAT?

0-1 ILP formulated as:
Does there exist a vector $\mathbf{x}$, subject to constraints:
$$
  \left.\begin{array}{rrrrr|rr}
     a_{11} x_1 & + &a_{12} x_2 & ... + & a_{1n} x_n\le b_1 \\
     a_{21} x_1 & + &a_{22} x_2 & ... + & a_{2n} x_n\le b_2 \\
     ...\\
     a_{m1} x_1 & + &a_{m2} x_2 & ... + & a_{mn} x_n\le b_m \\
  \end{array}\right.
$$
Domain of x: $\forall_{x_j \in \mathbf{x}} x_j\in \{0,1\}$
Reduction to k-sat:
First reduce to circuit sat:

Start with the first row, create a boolean variable for representing each bit in $a_{1j}$ and one boolean variable for $x_j$. Then make variable for $b_1$. Make an addition circuit (pick your favorite) adding the row up.

Then make a comparison circuit, declaring the sum to less than $b_1$ (with a lightbulb that lights up if they are).

Convert these two circuits to CNF, filling in the $a_{1j}$ variables and $b_1$ since they are given.

Repeat for all rows, but reuse the $x_j$ variables between them.

Take all the comparison bulbs and AND them together to get a single lightbulb as output. The SAT problem would now be "what inputs for all $x_j$ will make this final ANDed lightbulb light up"

The final CNF will contain all the constraints.


Better results for minimum vertex cover algorithms Currently I'm using the well-known ratio-2 algorithm which is nice and fast, but I'm looking for an intuitive way to improve my results.

All the articles I read so far were way too complicated for me, I'm looking for simple ideas to improve the results.

What I got so far:

def approx_vc(g):
    """
    Find a vertex cover that in the worst case is twice the size of the mvc (ratio 2).
    :param g: Graph object
    :return: Set of integers as vertices.
    """
    c = Set()
    e = g.get_edges()
    while len(e):
        u, v = e.pop()
        c.update([u, v])
        for edge in list(e):
            if u in edge or v in edge:
                e.remove(edge)
    return c

A short trip to wikipedia will tell you that there is no known better approximation algorithm for vertex cover (at least when by "better" we require an improvement by a constant independent of the input).

This is what is known so far:

The best known approximation achieves an approximation factor of $2-\Theta\left(\frac{1}{\sqrt{\log V}}\right)$ [1].
VC is NP-hard to approximate within a factor of $1.3606$ (meaning that if we have a polynomial approximation algorithm with this factor then $\mathsf{P}=\mathsf{NP})$ [2].
If the unique games conjecture holds, then VC is NP-hard to approximate within a factor of $2-\epsilon$, for all $\epsilon>0$ [3]. So if there exists a $2-\epsilon$ approximation for VC, then either $\mathsf{P}=\mathsf{NP}$, or the unique games conjecture fails.

Thus, any better approximations than the naive one you presented will solve open questions in complexity, so you are not likely to find them here (and they might not exist at all).

1. G. Karakostas, A better approximation ratio for the vertex cover problem, ACM Trans. Algorithms (TALG) 5 (4) (2009) 41.

2. Dinur, Irit; Safra, Samuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics. 162 (1): 439–485.

3. Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. 74 (3): 335–349.


Should you post basic computer science homework to your github? I am currently taking computer science coursework as part of a computer science related degree at my University. I was wondering if I should upload the solutions I make for various trivial homework assignments (ie. not more than 20-30 or so lines of code, on basic/fundamental topics) to my GitHub account, or if I should only upload larger course/personal projects to it.
I have only been regularly coding for about a year, and a large portion of the code I have written was for a company where I was under an NDA, so I was wondering if this would be an appropriate way to add more breadth to future job applications.

No, solutions to homework assignments are not likely to impress potential future employers.
Many professors would prefer that you not post solutions to homework assignments to public Github repositories. Why? If they ever reuse those problems in a future semester, then by making the solutions publicly available you are creating a temptation to cheat for other students, and that can be detrimental. So it would be a kindness to avoid publicly posting solutions.
If you are a student, you can get free unlimited private repositories on Github that you could use for homework assignments. Just make sure not to let them revert to public when you graduate.


Different characterization of $\Delta_2^P$ $\Delta_2^P =P^{NP}$, is the set of all languages decidable by a polynomial Turing machine with access to a SAT oracle. I came across a definition of $\Delta_2^P$ as the set of all languages $L$ such that there exists $L_1\in NP, L_2\in coNP$ where $L=L_1\cap L_2$.

I'm trying to prove that a language in $P^{NP}$ can be expressed by such intersection. Let $L$ be some language in $P^{NP}$, $x\in L$ if $M$ (the machine with access to a SAT oracle) accepts $x$ using some transcript $w$ (the answer of the oracle to the queries raised by $M$). I need to make sure $w$ is a valid transcript (i.e. doesn't lie by giving no answers for satisfiable formulas or yes answers for unsatisfiable formulas). I tried somehow encoding this condition in an intersection of a language in $NP$ with a language in $coNP$, but didn't succeed. Can you give a description of $L\in P^{NP}$ using such intersection?

That set is BH2, and BH is a subset of PNP.    If  BH ⊆ BH2  "then the polynomial hierarchy collapses to" BH3(2), where BH3(2) is the 2nd "level of the Boolean hierarchy over $\Sigma_2^P$."

(So, to answer your question:  No, I can't give such a description.)


Counting models satisfying a boolean formula I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–291, 2005). A few lines into the algorithm description the authors denotes a sub algorithm and claims "The function $C_E$ computes #2-SAT by exhaustive search. It will be applied only to formulas of size ≤ 4 and can thus be safely assumed to run in O(1) time". The size of formulas is referred to the number of clauses.

I've been trying to find this exhaustive search algorithm that computes a #2-sat instance with number of clauses less than 4. But the results only returns algorithms for generally solving/counting models for #2 or #3-SAT and does not talk about a special case when size ≤ 4. First of all, is this claim true? Since the paper was published by a well known journal, I guess it is. But if so, does anyone know about this special case?

For any fixed $k$, a $k$-CNF with at most four clauses has at most $4k$ variables. So you can count the satisfying assigments with

count = 0
j = number of variables
for v1 = 0 to 1 do
    for v2 = 0 to 1 do
        ...
        for vj = 0 to 1 do
            if formula_value(phi, v1, ..., vj) == true
                count = count + 1

This runs in time $\Theta(2^j) = O(2^k) = \Theta(1)$, since $k$ is fixed.


How to know the width/size of a IR (Instruction Register) I am trying to learn more about the CPU in embedded systems. As I am studying I learned that the IR (Instruction Register) is kind of a special register.
What I would like to know is how to know the width / size of the IR. So, what I mean is for e.g. if I have a 16-bits CPU with 18 address lines (that means max. 256 Kbyte addressable memory). What is the width of the IR of this CPU? In this example the size of opcode are not given. Is it important to know how many opcodes there are. But if it does matter the size of opcodes is maximum 1 byte.
Could someone give me some insight of how this works.
Thank you.

In a typical scalar in-order issue microcontroller, the instruction register holds however many bits are needed to control the data path.
Modern microcontrollers are typically Harvard architectures, with program memory stored in flash, with a modest amount of data/read-write memory on-chip. This means that, unlike traditional scalar CPUs, the bus width of program memory and the bus width of data memory does not have to be the same.
Microcontroller instruction sets are typically designed so that the instruction as a whole can be understood from the first word fetched from flash. Any additional words contain data only, and hence do not need to participate in instruction decoding.
As an example, here is the AVR block diagram from a data sheet that I picked at random:

The instruction register holds whatever comes out of program memory. Since AVR has 16-bit instructions, we would expect it to be a 16-bit register.
Now consider the PIC instruction set. Different models have different instruction sizes, anything from 12 bit to 16 bit. Modern microcontrollers can handle this just fine because, as noted earlier, instruction memory can have a different word size from data memory. This instruction word contains all of the information needed to understand what the instruction needs to do, so this is the size of the instruction register.
A mid-range core PIC has a 14-bit instruction word, so it will almost certainly have a 14-bit instruction register. And if you look at a data sheet, this turns out to be correct, and is even labelled on the diagram:

So in summary: On a typical modern microcontroller, the IR size is one word of program memory, and the instruction encoding is carefully designed so that this word contains all the information that instruction decoding needs.


How come $REC$ languages are included in $NRE$ How come $REC$ languages are included in $NRE$.

The definition of a language in $REC$ is . $L \in REC$ if there is a turing machine $M$ that recognizes the language $L$ and that stops on any given input.

It makes sense that $REC$ is included in $RE$;

$L \in RE$ if there is a turing machine $M$ that recognizes the language $L$ but may stop on some inputs;

The inclusion still makes sense right now.  But when we go to the $NRE$ i find it hard to understand;

$L \in NRE$ if there DOES NOT EXIST ANY turing machine $M$ that can recognize the language.

How can a language in $REC$ be in $NRE$ if $REC$ assumes that such a language would have a turing machine that stops on every intput yet a language that is $NRE$ must not have any turing machine that can recognize it?

Could the given definition of $NRE$ be wrong?
An explanation would be welcomed!

I've never seen "NRE" defined to mean "not recursively enumerable", which is the short way of saying what you've defined.  If you take it to mean "not recursively enumerable" then no recursive language is in NRE because every recursive language is recursively enumerable.

The only definition of "NRE" that I've seen is that people in the field of DNA and membrane computing seem to use it for the set of Turing-computable sets of natural numbers, i.e., the sets that can be written as $\{|x|\mid x\in L\}$ for some RE language $L$.


3D gift wrapping algorithm: how to find the first face in the convex hull? I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space.

However, all the articles I have read seem to omit the description of the first step of the algorithm; namely, finding a face (that is, a triangle) in the set that will definitely be in the convex hull (and doing so in $O(n^2)$).

Example of such an article: https://www.sciencedirect.com/science/article/pii/S002200000580056X

I do understand how to find a vertex that definitely be in the convex hull: just take one with extreme coordinates.
However, I don’t know how to approach the problem for edges or faces.

For simplicity, let us assume no four points are in the same plane. Otherwise, adapt the following procedure to deal with the degenerated cases.

Define the usual lexicographic order on points. That is, for any two distinct points $P$ and $Q$, $P<Q$ if the $x$ coordinate of $P$ is smaller than that of $Q$, or, if their $x$ coordinates are equal, the $y$ coordinate of $P$ is smaller than that of $Q$, or, if both x coordinates and y coordinates are equal, the $z$ coordinate of $P$ is smaller than that of $Q$.

Iterate through all points, keeping tracking of three smallest points.
At the end of iteration, those three smallest points are the vertices of a triangle in the convex all.


Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$? Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to.

In the 2-dimensional case it's fairly trivial, you simply split the square along its diagonals:

if (x < y) then
    if (x + y < 0) then
        // Side 1
    else
        // Side 2
else
    if (x + y < 0) then
        // Side 3
    else
        // Side 4

In 3-dimensions, this becomes more complex; each face creates a 'volume' of points that are closest to it in the shape of a square based pyramid.

Visualisation of the 6 planes that form the 6 pyramids

Of course, given a point, it's possible to determine which side of the 6 planes it lands on and using that information you can determine which face of the cube is closest. However this would involve running 6 separate checks.

Moving this into higher dimensions, a similar algorithm can be run on hypercubes, however, as the number of faces on a n-cube is $2^{n-2}{n \choose 2}$, this quickly becomes computationally very expensive.

However, theoretically a perfect algorithm could cut the search space in half with every check, discarding half the faces each time.

This would give this hypothetical algorithm a runtime of $O(\log_2(2^{n-2}{n \choose 2}))$ which can be simplified, if my rate of growth calculations worked out, to $O(n\log(n))$

Is my logic correct here; can/does such an algorithm exist?

After a bit more thinking, I realised it's actually doable in $O(n)$

If you normalise your hypercube onto the origin then to find the face the point lies on you simply need to find the axis of the point with the largest magnitude.

So, if the point is at $(0.2, 0.4, 0.7, 0.5)$, the point will be closest to the face facing in the positive z direction.


Problems for which there is no algorithm with smallest time complexity Are there any problems where there is no smallest time complexity, so there is a big-$\mathcal{O}$ but no big-$\Theta$?

More formally, I am looking for any problem $p$ where

for any algorithm that solves $p$ in time $f(n)$
there provably exists another algorithm that solves $p$ in time $g(n)$
where $g(n) = o(f(n))$.

An example would be a problem for which there exist algorithms of complexity $\mathcal{O}(n^k)$ for all $k > 0$, but for which there is no algorithm of lower complexity, like $\mathcal{O}(1)$ or $\mathcal{O}(\log n)$.

The existence of such problems follows from the Blum speedup theorem. The theorem shows, for example, that there exists a problem such that for any algorithm solving it in time $T(n)$, there is another one solving it in time at most $\log T(n)$.


Is There An Established Way To Send Code Over a Network? Let's say I have two computers on a network. I want to write code in some language on machine A, send the code in an efficient way over a network, and run the code on machine B. It seems to me that this would be inherently slow and would run into a bundle of problems (not having required dependencies) but perhaps some work has already been done on this problem? Is there any known processes or systems that already do this?

From memory Java applets and COM components could do this (But mostly discontinued due to security reasons)  The approach was mostly based on a pull strategy.  That is Machine B pulled code from Machine A and then executed in Machine B.

OS and application updates (e.g. Windows Update) also do this approach.  They download the update from a different machine and execute locally.


Intervals Collision Detection Algorithm Given a collection of non-empty intervals [a,b), where a/b are integers in some finite range (ex. 0...100) and a is less than b, can you find an algorithm that will detect all intervals that exhibit some collision/overlap where the worst-case performance of the algorithm is better than O(n^2)?
You can assume that intervals starting at an end of another interval do not overlap, ex [15,22) and [22,30) do not overlap.
For example, given this collection {[12,16),[8,13),[16,34)} the result would be {0,1} because interval at index 0 intersects some interval, and interval at index 1 intersects some interval.
I have an algorithm that in worst case performs O(n^2) but can't figure out one that is faster.  Mine doesn't use binary search trees, simply orders the intervals according to a, and then has a loop over all the elements with an inner loop on the remaining elements checking for intersection -- once an inner loop interval doesn't intersect the inner loop stops and the outer loop proceeds to the next element.
I am not looking for exact code, just a clear explanation of such an algorithm.

As pointed out by the other answer, producing a list of the intersections is not doable in subquadratic time.
However, counting all the intersections can be done in linear time.
The rough idea for that one is to sort all coordinates (starting points and end points of intervals) into one list using counting sort (as the range of the values we are sorting is fixed) and iterate over it, maintaining a counter for the number of intervals intersecting at the current point and another one for the total number of intersections.
If the current coordinate is an end point, reduce the first counter by 1.
Otherwise (i.e. the current coordinate is a starting point), increase the first counter by 1 and increase the total counter by the value of the first counter.


Matrix Max in less than O(n) I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If a better run time is possible, I would also like to find any values over a specific threshold in less than O(n) time. Is any of this possible?

I cannot re-sort and do a binary search or something along those lines as the ordering is important.

If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a simple adversary argument: if you don't look at everything, then you can't distinguish between the cases where the maximum component is/isn't one of the ones you didn't look at. If you want to maintain max-information for a dynamic matrix, then there might be suitable preprocessing and maintenance (for example, a search tree) that can speed things up.


Real time application with DFA or NFA application Can anyone here give an example of DFA or NFA real time application?

And, can I know what are complexity and decidability problems in real time application? Does every real time application have complexity and decidability problems?

DFA/NFA in a real time application ? consider designing a parser for user inputs where each input is a word w="http://some-address.com?key[1]=value1&key[2]=value2..."

consider having each key[i] as the string ##i now you can easily build a regex /##./ to accept all input-strings having key values contained in w.

Since we have a regular expression that recognize this pattern there exists an equivalent NFA that recognizes such words, now your parser server can recognize http requests that holds information valuable to your application
and distinguish them from normal static requests for pages/images.

There is a big difference from Complexity to Decidability problems,
Decidability problems is a question whether for all inputs w the algorithm A will halt and yield a result, Not every problem is Decidable (i.e loop to infinity doesn't halts), moreover not every problem that is decidable has the same complexity.

problems can be solved by different algorithms Complexity analysis is about trying to understand the time/space complexity of a problem and its boundaries.

Moreover by Complexity analysis we can try and break up different problems into different classes, for example class A could be "All problems that have an algorithm solving them in (some_constant)(nlog(n) time" could be an hypothetical class of problems.

Here is some nice short video trying to summarize some of the ideas of Complexity.
https://www.youtube.com/watch?v=YX40hbAHx3s


Any problem in P can be reduced to the language of odd integers Given $A=\left\{n\in \mathbb{N} \mid \text{$n$ is odd}\right\}$,  we want to prove that if $S \in P$ then there is a Karp reduction from $S$ to $A$.
My attempt:
If $S \in P$ we can solve $S$ with a reduction that converts in polynomial time an input from $S$ to $A$, but I don't know how to prove formally the function and to show that the function is a reduction.

Let $S$ be any language in $\mathsf{P}$. You are looking for a function $f$ with the following properties:

$f$ can be computed in polynomial time.
If $x \in S$ then $f(x) \in A$.
If $x \notin S$ then $f(x) \notin A$.

Since $S$ is in $\mathsf{P}$, we can determine whether $x \in S$ in polynomial time. Therefore, the reduction $f$ can work as follows:

Determine whether $x \in S$.
If $x \in S$ then output something in $A$.
If $x \notin S$ then output something not in $A$.

You take it from here.


What is the importance of the condition "| xy | < p" in pumping lemma? Let L be a language. w $\in$ L , and w could be broken in xyz.

Then if L is regular, there exists a pumping length p such that:

|y| $\gt$ 0
|xy| $\le$ p
$\forall$ i $\ge$ 0, xy$^i$z $\in$ L

I understand that this lemma is based on pigeon hole principle and proof by contradiction.

For conditon (1), I understand that the string we are pumping should be $\ge$ 1.

But I don't understand the significance of condition (2). Why should the legth of xy be equal to or smaller than p . Will not it work otherwise?

$p$ is the number of states in the automaton.  As you say, the pumping lemma is about the pigeonhole principle.  Suppose that $q$ is the first state that's repeated when you read input $w$.  Then $x$ is the string that you read before you reach $q$ for the first time, and $y$ is the string you read between the first and second visits to $q$. Since there are only $p$ states including the start state, you must repeat a state after doing at most $p$ transitions, i.e., reading a string of length at most $p$.  So the condition $|xy|\leq p$ comes from the proof.

In reality, when an automaton reads a particular string $w$, there might be many times when it returns to a state that has already been visited. If you take $w\in L$ any split $w=xyz$ with $|y|\geq 1$, such that the automaton is in the same state at the beginning and end of $y$ then $xy^iz$ will be in $L$ for all $i$, regardless of how long $xy$ is.


Paxos: Accepting Proposals With Different Values and Consensus in Paxos I have a number of questions about Paxos which I can't answer in full confidence from reading the paper (Paxos Made Simple).

My questions are loosely based around the following quote:

  In Paxos, a value is chosen when a single proposal with that value has been accepted by a majority of the acceptors. However, we can allow for multiple proposals to be chosen, but we must guarantee that all chosen proposals have the same value.

The first property, P1, states:

  P1: An acceptor must accept the first proposal that it receives.

Therefore, if we have an proposer, which sends an prepare(n) statement to a majority of acceptors, this majority can always respond to a prepare request, and because this is the first proposal, the majority must accept this proposal.

However, in the case where multiple proposals are proposed at about the same time, it can be possible that no single value is accepted by a majority. For this reason, it is necessary for an acceptor to be able to accept multiple proposals.

Question 1: This means that an acceptor can accept a proposal with a value v2 after it has accepted a proposal with value v1. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?

Now, if we look at P2B:

  If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

And then later:

  If the proposer receives the requested responses from a majority of the acceptors, then it can issue a proposal with number n and value v, where v is the value of the highest-numbered proposal among the responses...

Question 2: Does this mean that if a proposer proposes a value, v1, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, v2? If they want to make a proposal, they must propose the same value, v1? The only way they could propose a different value would be to start a new instance of Paxos. The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?

Question 3: Can an acceptor respond to a proposer with a promise if consensus has already been reached?

Question 4: The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send an proposal, correct?

Question 1: This means that an acceptor can accept a proposal with a value $v_2$ after it has accepted a proposal with value $v_1$. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?

Yes, it is possible for an acceptor to accept a proposal with number $n_2$ and value $v_2$ after it has accepted a proposal with number $n_1$ and value $v_1$. Consider the following scenario where there are two proposers $p_1$ and $p_2$ and three acceptors $a_1, a_2,$ and $a_3$:

$p_1$ proposes $\texttt{propose}(n_1,*)$ to $a_1$ and $a_2$.
both $a_1$ and $a_2$ respond to $p_1$ with (a) a promise never again to accept a proposal numbered less than $n_1$ and (b) no proposal because they have not accepted any ones.
$p_1$ receives the two responses from $a_1$ and $a_2$. Now $p_1$ is free to select its own value $v_1$. $p_1$ sends $\texttt{accept}(n_1, v_1)$ to $a_1$ and $a_2$.
$a_1$ accepts $(n_1, v_1)$ but $a_2$ does not (maybe this message to it has been lost; note that an acceptor can ignore any request without compromising safety).
$p_2$ proposes $\texttt{propose}(n_2, *)$ to $a_2$ and $a_3$ ($n_2 > n_1$).
Because, in 4, $a_2$ does not accept $\texttt{accept}(n_1,v_1)$ from $p_1$, both $a_2$ and $a_3$ respond to $p_2$ with a promise never again to accept a proposal numbered less than $n_2$.
$p_2$ receives the two responses from $a_2$ and $a_3$ and is also free to select its own value $v_2$. $p_2$ sends $\texttt{accept}(n_2, v_2)$ to $a_1$ and $a_3$.
$a_1$ can now accept the proposal $(n_2, v_2)$ from $p_2$.

  Question 2: (1) Does this mean that if a proposer proposes a value, $v_1$, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, $v_2$? (2) If they want to make a proposal, they must propose the same value, $v_1$? (3) The only way they could propose a different value would be to start a new instance of Paxos. (4) The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?

For (1): yes; For (2), yes. The invariant $\texttt{P2B}$ in Paxos is the key to its correctness.

For (3): I think you have confused an instance of Paxos with a round in an instance of Paxos. They are two important concepts. We call a round the collection of all messages labeled with some particular proposal $n$. An instance of Paxos consists of multiple rounds, each round corresponding to a proposal with a different number. If you consider multiple instances of Paxos, please refer to Section 3 "Implementing a State Machine" in the paper. It is often called "multi-Paxos".

For (4): in page 6, it reads "A proposer can make multiple proposals, so long as it follows the algorithm for each one. It can abandon a proposal in the middle of the protocol at any time". That is to say, as a proposer, you are free to make multiple proposals as you want, for no matter what reasons. However, a major reason would be to learn the value already chosen: at phase 2(a), you will have to select the value chosen, if any.

  Question 3: Can an acceptor respond to a proposer with a promise if consensus has already been reached?

Yes, it does no harm. Again, the invariant $\texttt{P2B}$ works.

  Question 4: The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send a proposal, correct?

Are you discussing about the correctness of Paxos? Are you regarding the "promise mechanism" as the key to success? If so, you are almost right: however, it is hard to identify a single factor in Paxos. If it must be done, once again, it is the $\texttt{P2B}$ invariant.


Given a set of string patterns, find which ones match a particular string I have an array of known patterns with optional wildcards. For example this array that has 5 patterns:

ab*e
hkl
abcd*
ab
sdfs?f

now I need to find the elements within the array that match an arbitrary string.

This can be solved with regular expression by converting the patterns to regexp and looping over the array and returning those that match my string. The problem is that this approach is too slow when my patterns array has thousands of patterns.

I'm looking for some sort of hashing to the known patterns array (could be slow as it only happens once), so that the search of matched patterns to a gives string becomes significantly faster. I checked the Rabin Karp and Aho–Corasick algorithms but they don't work for patterns with wildcards.

In the example above if I'm looking for all matched patterns for abcde I would get

ab*d
abcd*

or the values 0,2 which are the indexes in the patterns array matching my string.

Rather than build 5 NFAs (one for each pattern), I suggest you build a single NFA or DFA that represents the parallel composition of all five patterns.  Then you can run the string through this automaton and check what state it ends at.  That state will tell you which of the 5 patterns it matches.

For best performance, build a NFA for each pattern, take the parallel composition using the product construction, and then convert to a DFA.  This should be quite fast.


How will I calculate the time and space complexity for this pyramid algo? This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345":

    1
   121
  12321
 1234321
123454321

Code:

void buildPyramids(string str) {
    size_t len = str.length();

    size_t i, j, k, m;

    for(m=0; m<len; m++) {
        for(i=len-m-1; i > 0; i--) {
            cout << " ";
        }
        for(j=0; j<=m; j++) {
            cout << str[j];
        }
        for(k=1; k<j; k++) {
            cout << str[j-k-1];
        }
        cout << endl;
    }
}

What's the correct way to calculate the space and time complexity for the same?

Could you also guide me to some resources for a deeper understanding of the same?

There is one major for loop in this case

for(m=0; m<len; m++)

It has a complexity of O(len)
Inside this loop, there are 4 other loops, but they are additive in nature and not nested. Each of those loops has a length of <=len. Thus the overall complexity of this program would be O(len*len)
The space complexity will be also be the same.


Is global non-convex optimization NP-complete? Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision problem

Is there a set of points such that f < C?

Where C is some constant. However, I am not sure if these problems are in the class of NP-Complete, and if so, what would you say the size of the input is? Complexity of the function?

Thanks!

Yes, non-convex optimization is NP-hard. For a simple proof, consider the following reduction from Subset-Sum. The Subset-Sum problem asks whether there is a subset of the input integers $a_1, \dots, a_n$ which sums to zero. To reduce to non-convex programming, let $x_1, \dots, x_n$ be variables encoding the subset and consider the following non-convex program:

$$
\begin{align*}
\text{minimize }\quad&(a\cdot x)^2 + \sum_{i=1}^n x_i^2(1 - x_i)^2\\
\text{subject to}\quad& \sum_{i=1}^n x_i \ge 1.
\end{align*}
$$

Note that the optimum of this program is zero iff the Subset-Sum instance has a subset which sums to zero.


If the union and intersection of two NP languages are both in P, prove that the langauges are in co-NP Given $L_1, L_2 \in \mathsf{NP}$, $L_1 \cup L_2 \in \mathsf{P}$ and $L_1 \cap L_2 \in \mathsf{P}$,

Prove: $\ L_1, L_2 \in \mathsf{coNP}$

What I've done so far is:

$$ L_1 \cup L_2 \in \mathsf{P} \Rightarrow (L_1 \cup L_2) ^\complement \in \mathsf{P}
   \Rightarrow L_1^\complement \cap L_2^\complement \in \mathsf{P} $$

$$ L_1 \cap L_2 \in \mathsf{P} \Rightarrow (L_1 \cap L_2) ^\complement \in \mathsf{P}
   \Rightarrow L_1^\complement \cup L_2^\complement \in \mathsf{P} $$

How do I proceed from here?

Hint: You only need to distinguish between two non-trivial cases: $x\in (L_1\setminus L_2)$ and $x\in L_2\setminus L_1$. In these cases, membership-certificates for $L_1$ would be nonmembership-certificates for $L_2$ and vice versa. Hence, you always have nonmembership-certificates for every input string $x$. And conclude that both $L_1$ and $L_2$ are in $\mathrm{co}$-$\mathrm{NP}$.