Is this language semidecidable? I recently started self studying about algorithms and decision problem, so I don't have a firm grasp on this particular area. In this context I found myself thinking about the following .

If $L_1$ is semidecidable and $L_2$ is decidable, what can one say about the language set defined by their difference $L_3 = L_1 \text{ \ }L_2$ ?

I'm inclined to believ that $L_3$ is semidecidable, but I can't think of a way to prove it.

Any ideas?

If $L_1$ is semidecidable, there's a TM $M_1$ that takes a string $x$ and always reliably halts and answers "yes" if $x\in L_1$. If $L_2$ is decidable, there's a TM $M_2$ that always halts and reliably answers "yes" if $x\in L_2$ and "no" if $x\notin L_2$.

Make a new machine $M$  that when given an input string $x$ first runs $M_2(x)$. If the answer is "yes" then you know $x\notin L_1\setminus L_2$ so have $M$ halt and answer "no". If, on the other hand, $M_2(x) = "no"$ then $x$ may or may not be in $L_1\setminus L_2$, so then run $M_1(x)$ and do whatever $M_1$ does. It may never halt or it may answer "no", but if $x\in L_1\setminus L_2$ your $M$ will correctly answer "yes", proving that $L_1\setminus L_2$ is indeed semidecidable.


Proving DOUBLE-SAT is NP-complete The well known SAT problem is defined here for reference sake.

The DOUBLE-SAT problem is defined as

$\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least two satisfying assignments}\}$

How do we prove it to be NP-complete?

More than one way to prove will be appreciated.

Here is one solution:

Clearly Double-SAT belongs to ${\sf NP}$, since a NTM can decide Double-SAT as follows: On a Boolean input formula $\phi(x_1,\ldots,x_n)$, nondeterministically guess 2 assignments and verify whether both satisfy $\phi$.

To show that Double-SAT is ${\sf NP}$-Complete, we give a reduction from SAT to Double-SAT, as follows:

On input $\phi(x_1,\ldots,x_n)$:

Introduce a new variable $y$.
Output formula $\phi'(x_1,\ldots,x_n, y) = \phi(x_1,\ldots,x_n) \wedge (y \vee \bar y)$.

If $\phi (x_1,\ldots,x_n)$ belongs to SAT, then $\phi$ has at least 1 satisfying assignment, and therefore $\phi'(x_1,\ldots,x_n, y)$ has at least 2 satisfying assignments as we can satisfy the new clause ($y \vee \bar y$) by assigning either $y = 1$ or $y = 0$ to the new variable $y$, so $\phi'$($x_1$, ... ,$x_n$, $y$) $\in$ Double-SAT.

On the other hand, if $\phi(x_1,\ldots,x_n)\notin \text{SAT}$, then clearly $\phi' (x_1,\ldots,x_n, y) = \phi (x_1,\ldots,x_n) \wedge (y \vee \bar y)$ has no satisfying assignment either, so $\phi'(x_1,\ldots,x_n,y) \notin  \text{Double-SAT}$.

Therefore, $\text{SAT} \leq_p \text{Double-SAT}$, and hence Double-SAT is ${\sf NP}$-Complete.


A question on the graph induced by the transition function of a deterministic Turing machine Let $M$ be a deterministic Turing machine with totally defined transition function $\delta$ and working alphabet $\Gamma$.  Let $Q$ denote the statespace of $M$'s finite control. Let $G_M$ be the graph induced by $\delta$ which is defined as $G_M = (V,E)$ with $V = Q$ and $(q,q') \in E$ iff there exist $a,b \in \Gamma$ and $m \in \{\pm 1\}$ such that $\delta(q,a) = (q',b,m)$.
Are there any results which translate properties of the machine $M$ to graph theoretic properties of $G_M$ and vice versa?

Not likely: almost every property of a Turing Machine is undecidable, and almost every property of a graph is decidable.

If you ignore tape contents, you don't have Turing machines, you have finite automata. But graphs can't really represent tape content.

You can perform some trivial dead code analysis, but there may be unreachable states which are reachable in your graph.


What does it mean to "construct a PCP"? I am referring to section 8.1 of this paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf. Can someone kindly give me a concrete definition of what it means to "construct a PCP" and if that is the same as a "PCP verifier". Are they the same things?

Its not clear to me as to what it means to say that "Let the bits in the proof be vertices of a graph and the tests of the verifier be the edges of the graph." How can one encode vertices of a graph as single bits?

I am trying to match this to the concepts in the lecture notes by one of the authors, https://courses.cs.washington.edu/courses/cse533/05au/ but its not clear as to how to go about doing it. If someone can help identify the correspondence that would also be a great help!

A PCP is a probabilistically checkable proof, and the PCP verifier is the algorithm that checks it. In our case, we are given an instance of Unique Label Cover which is promised to be either at least $(1-\eta)$-satisfiable (Yes instance) or at most $\gamma$-satisfiable (No instance). The (polynomial size) proof, which is similar to a witness in an NP verifier, purports to show that the instance is a Yes instance. It is given by a sequence of bits. The verifier is a probabilistic algorithm which checks the proof. If the instance is a Yes instance then there is a proof which convinces the verifier with probability at least $c$ (the completeness), and if the instance is a No instance then every proof convinces the verifier with probability at most $s$ (the soundness).

This particular verifier chooses two bits $\pi_i, \pi_j$ of the proof $\pi$ according to some complicated distribution, and checks that $\pi_i \neq \pi_j$. Every Yes instance has a proof such that $\Pi[\pi_i \neq \pi_j] \geq c$, and for No instances, all proofs satisfy $\Pr[\pi_i \neq \pi_j] \leq s$.

You can encode this verifier as an instance of Max Cut. The vertices $v_1,\ldots,v_N$ correspond to the bits of the proof $\pi_1,\ldots,\pi_N$, and two vertices $v_i,v_j$ are connected with an edge whose weight is the probability that the verifier chooses to check the two bits $\pi_i,\pi_j$. A cut in the graph can be though of encoding a proof: vertices on one side of the cut are 0 bits, and vertices on the other size are 1 bits. Under this encoding, an edge $(v_i,v_j)$ is cut iff in the corresponding proof, $\pi_i \neq \pi_j$.

The upshot is that if the Unique Label Cover instance is a Yes instance, then the Max Cut instance has a cut whose value is at least $c$, whereas if the Unique Label Cover instance is a No instance, all cuts of the Max Cut instance have value at most $s$. Therefore any approximation algorithm for Max Cut whose approximation ratio is better than $c/s$ would be able to solve Unique Label Cover, which is UGC-hard.


Proving that the cover time for graph is exponential in the worst case How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$?

The cover time is the expected length of a random walk that visits all vertices.

You do it in two steps:

First you think of a graph which you can expect to be difficult.
Then you prove your suspicion.

Let's start with the first step - do you have any graph in mind?


liskov substitution principle seems to have two conventional meanings This is a question about the semantics of the name, rather than about the principle itself. What is the Liskov Substitution Principle (LSP)?

LSP seems to have two meanings in the literature I've seen.   One statement is the rule that determines whether one function type is a subtype of another?   I.e, A->Y is a subtype of B->X, if B is a subtype of A and Y is a subtype of X.  The other statement is that in an object oriented language, a method in subclasses should be element of the subtype of the type of the method in the parent class.

The principle that B<:A, X<:Y implies A->X <: B->Y was a known principle well before the name "Liskov Substitution Principle" was ever coined.  I have found references to this principle from the early 80s.

For example, https://cl-su-ai.cddddr.org/msg04614.html, here is an email from 1987 where the author describes what he calls "PROBLEM II".  It is the definition and justification for the definition of arrow types described above.   Furthermore, this presentation, http://www.softwarepreservation.org/projects/LISP/crisp_ibm370_sdc/CRISP-talk.pdf, claims it was known in the early 1970s.

I don't think either of these is the Liskov substitution principle. My understanding of the principle is that for $S$ to be a subtype of $T$, it must be the case that we can substitute a value of type $S$ anywhere a value of type $T$ is required without compromising the correctness of our program.

Now, the subtyping rule for functions is probably a sufficient condition for the Liskov principle to be satisfied, as long as functions are sufficiently abstract. But this is not "the" principle, because it says nothing about anything that isn't functions.

Also, this page argues that subclassing in most OOP languages is insufficient to ensure the Liskov principle is satisfied. That is, it only ensures that the principle is satisfied with respect to other simple, declared subtyping relationships like you mentioned. It does not ensure that implicit invariants are respected, and indeed, it is possible to violate these invariants in a subclass. So the Liskov principle would say that sometimes sub-class does not imply sub-type.

It's probably also possible for this second argument to apply to "functions" in a language as well (although it would be pretty unsatisfactory), in which case the Liskov principle would not validate the induced subtyping rule.


Machine learning: do the benefits of more data plateau after a certain point? This question is both general in nature and also specific to computer vision. If this is the wrong forum, apologies in advance and suggestions on where to post would be much appreciated.

After a certain point, do the benefits of more data plateau for machine learning algorithms?

For instance, let's say the goal is object recognition of a basketball. Is there a plateau, say, after training on 1M images of basketballs? Or is the plateau lower at like 100K images? Or is there no plateau at all?

More concretely, can you detect basketballs with 99% accuracy after 100K samples, meaning the next 900K samples only nets an additional 1% in accuracy at most?

How about for non-image domains such as speech recognition of all words related to the weather in the English language?

It seems that if there is a plateau, it would hinge on the complexity of the domain. Assuming the data plateau exists, is there a principle for generalizing what the plateau is for a given domain (e.g., to recognize one type of object with no variations, you need about 100K images from every angle and under different lighting conditions)?

Yes, typically there will be a plateau.  There's usually no way to guess exactly where the plateau will be, a priori; the only way to find out is to build larger and larger data sets and see what happens.

The size of the data set needed to reach a "plateau" is dependent on many factors, including the specific classification task you're trying to solve, the machine learning algorithm you're using, the set of features you've chosen, and maybe other considerations.  For some tasks, a fairly small training set might be sufficient to reach the "plateau".  For others, you might need an incredibly enormous training set -- so large that you'll never reach it in practice, so effectively you'll never hit a plateau in practice.

There's absolutely no way to answer your specific questions about how many images are needed for particular domains.  I know you're hoping there will be some rule of thumb that'll help you predict how many images you need for some new classification task, but I've got bad news for you; there's not really any useful rules of thumb that I'm aware of.  The only way to find out is to try it, or to read research papers or experience reports from others who have tried to solve the same task or a similar task.

It's also worth keeping in mind that the notion of a plateau should not be taken too seriously.  Rather, you should think of it as diminishing returns.  After some point, increasing the size of the training set will give diminishing returns in accuracy.  It's not to say that there's necessarily a point where you get literally zero improvement; it's just that the improvement available from a larger training set might be extremely small, i.e., where the accuracy curve starts to become nearly horizontal, when graphed as a function of the size of the training set.

In the comments you separately talk about "the point when a classifier reaches 95% of human accuracy".  That's not the same thing as a plateau; that's a totally different measure.  For some classification tasks, humans are way better than any classifier we know of; we don't know of any machine learning approach that will get anywhere near human accuracy, let alone 95% of human accuracy, no matter how large a training set you have.  For other classification tasks, machine learning can do better than any human -- so the classifier gets not just 95% of human accuracy, but maybe 200% of human accuracy.  Comparing a classifier's accuracy to human accuracy is unrelated to the existence and location of a plateau (i.e., diminishing returns as you increase the size of the training set).


Prove/disprove - reverse topological sort transpose graph I need to prove or disprove the following statement:

"Let $G$ be a directed acyclic graph, and $v_1v_2...v_k$ a topological sort of $G$.
Then $v_kv_{k-1}...v_1$ is a valid topological sort of the transposed graph $G^T$."

(The algorithm used is the one presented in CLRS 22.4)

I think the statement is correct.

My logic is that for every two vertices $v_i,v_j$ s.t $v_i<v_j$ in the sorting of $G$, one of two conditions hold:

A) $v_j$ is a decedent of $v_i$ in $G$, so in every topological sort of $G$, $v_i$ will be before $v_j$ in the sort.

B) or there's no path from $v_i$ to $v_j$ or the contrary, so $v_i$ and $v_j$ can switch places in the sorting, depending on the order that the DFS run on $G$.

From here, if condition A held then in the sorting of $G^T$, $v_j<v_i$, because now there's a path from $v_j$ to $v_i$, and if condition B held, then the order $v_j<v_i$ is valid for some topological sort of $G^T$. And so the sorting $v_kv_{k-1}...v_1$ is valid sort of $G^T$.

Something still doesn't feel right about this... would appreciate any help or comment.

A topological sort of a graph $G$ is an order $\pi$ such that if there is a directed path from $x$ to $y$ in $G$, then $x$ precedes $y$ in $\pi$.

Let us now show that $\pi^R$ is a topological sort of $G^R$. If there is a path from $x$ to $y$ in $G^R$ then there is a path from $y$ to $x$ in $G$, and so $y$ precedes $x$ in $\pi$, and so $x$ precedes $y$ in $\pi^R$.


Optimal algorithm to traverse all paths in the order of shortest path I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path.

The simplest way that comes to mind is to do a depth-first search (DFS) for all paths, accumulating their edge costs as I traverse the paths, and then doing an NlogN sort on the result.

But I wondering if there is a better way to do this task. Are there any algorithms that could optimize this problem (combining DFS and a shortest path algorithm such as Dijkstra's maybe?).

The goal is to find all paths from $s$ to $t$ in a directed, acyclic graph with edge costs. Let $n$ the number of nodes, $m$ the number of edges and $p$ the number of $s$-$t$-paths. Let's look at what we have.

Naive enumeration

Use any graph traversal from $s$ to find all paths.
Sort them by length.

You can interleave the steps, but you'll end up with runtime $\Omega(n + p \log p)$ if there are $n$ nodes and $p$ paths.

Note that this algorithm is easy to parallelise.

Eppstein's Algorithm [1]

This one has runtime $O(m + n \log n + p)$ (from skimming the paper, I assume the bound is sharp, i.e. $\Theta$ holds). Note that paths are not represented explicitly.

I have no idea how well this algorithm can be parallelised.

Lower bounds

First of all, $p \in \Omega(2^n)$ in the worst case even in DAGs, see for instance this class of graphs:

[source]

Note that all nodes have small out-degree and all paths have the same length.

Therefore, $p$ dominates any algorithm for this problem (in the worst case) if we can not make further assumptions.

When you go for a traversal over all paths, you clearly have runtime $\Omega(p)$.

Conclusion

Eppstein's algorithm is asymptotically optimal even in the setting you describe. However, asymptotic analysis at this level is rough and hides "extra" work that may or may not pay off in practice (since $n$ does not tend to infinity). The naive version may very well be competitive in an application, depending on $n$, $m$ and $p$, and maybe even structural features.

Another thing to keep in mind is that above figures are all worst-case but you are probably after average runtime on some specific input set².

TCS papers are unlikely to contain a rigorous analysis that helps you decide (and it's hard to do, too). Your question reads as if your goal is a real-world application, so I recommend a pragmatic approach. If the naive approach is too slow for you, try parallelising it. If that is still to slow, you can invest the time, implement Eppstein and run some tests.

Finding the k Shortest Paths by D. Eppstein (1998) [preprint]
My group developed a method for semi-automated average-case analysis and a tool to perform it. Have a look, maybe it can help you find out more about performance on your data.


Does there exist standardized language-agnostic data structure notation? I wonder if there exists language-agnostic data structure notation. Preferably a standard, allowing to describe data structures and basic data types. e.g. something like a subset of WebIDL.
A motivation is to describe data structures (a model) in a way that is standardized and language-agnostic. Then have a set of mappings of those data structures into various representations (XML, JSON, YAML)

In terms of notation:

Isn't XSD exactly what you are looking for? (barring all the "severe criticism" ...). Also not sure if you are looking for a notation convenient to hand-write, that's certainly NOT XML :-).
Typedefs and preserves seem to have more of a mathematical basis, perhaps closer to what you are looking for. A related HN thread.

I suspect you already know a lot of these projects, usually the focus is in serialization:

The IDL list at wikipedia ...
Amazon's Smithy and Ion.
Microsoft's Bond.
And of course Google's protobuf and flatbuffers, but also Mojo, oriented to IPC, and Fuchsia FIDL which seems similar.

Investigating this space I found Arrow, "a language-independent columnar memory format" for sharing memory between programs, with libraries for a dozen of languages. Turns out it uses flatbuffers under the hood.
Now that I came up with this list and I suspect you may be familiar with a lot of them, perhaps will be useful to know in which way the thing you are looking for is different. I think the keyword "notation" on your question is the key.
Cheers!


Compact, reversible mapping from set partitions of length k to integers Given a set $S$ of length $n$, I'm looking to map all the $k$-length partitions of $S$ onto the set of integers such that these integers are as close to 0 as possible. Ideally the range would be $\left[0, {n \brace k}\right)$.

Ideally this mapping and its inverse would be easy to compute.

The idea is to use the recurrence
$$
\newcommand{\stirling}{\genfrac{\{}{\}}{0pt}{}} \stirling{n}{k} = k \stirling{n-1}{k} + \stirling{n-1}{k-1}.
$$
This recurrence holds since either element $n$ belongs to one of the $k$ partitions of a partition of $1,\ldots,n-1$ into $k$ parts (say, ordered by minimal element), or it forms a singleton partition, joining a partition of $1,\ldots,n-1$ into $k-1$ parts.

Accordingly, partition the range $[0,\stirling{n}{k})$ into $k$ parts of length $\stirling{n-1}{k}$ and one of length $\stirling{n-1}{k-1}$. Given a partition, determine which of the $k+1$ intervals you belong to, remove $n$, encode the remaining partition of $n-1$ recursively, and locate it inside the chosen interval. The base cases are $\stirling{0}{0} = 1$ and $\stirling{n}{0} = \stirling{0}{n} = 0$ for $n > 0$.

The same algorithm can be reversed and be used to decode a number in $[0,\stirling{n}{k})$ into a partition of $1,\ldots,n$ into $k$ parts.


How to evaluate a Kleene's Closure through CFG and attribute grammars For a CFG with the production rules that can represent a regular expression. How can one calculate all the set of strings that regular expression would produce.
For T = {a, b,*,(,)}
and an arbitrary production rule I created to represent a simple regular expression
S->SS | S* | (S) | a | b | ∅
What would be an attribute grammar which can calculate the set of all strings that the regex can evaluate.
For example if we generate b(a)*
Then the output generated by regular expression would be a set of infinte strings {b,baa,ba,baaa......}
using set valued expression in the attribute grammar.
I am not sure how to represent set valued concatenation and Kleene closure.

Any "interesting" regular expression (i.e., one that includes Kleene star) represents an infinite set. Thus to "calculate the set of all strings" won't work so well. In a sense, the regular expression is a compact description of the language. What other kind of description do you expect to construct?
It is rather easy to construct regular expressions that represent very complex languages, that the reader needs to descypher to make sense of it.


What is the big-o of the function 2 log(log n) + 3 n log(n) + 5 log(n)? What is the big-O of the function $2\log(\log(n)) + 3n\log(n) + 5\log(n)$?
Is it just $O(n\log(n))$ for the whole function? I'm not sure how to represent $2\log(\log(n))$.

Starting with an analytical assessment of the function's terms, we'll first format all terms as similarly as possible to each other, in order to more easily compare with one another. To do so, all constants will be removed, leaving only the variable elements of each term. This is acceptable to do since we're ultimately seeking Big O classification, which typically sets all constants within its expression to a value of $1$.

$2log(log(n)) \geq log(log(n))$
$3n\: log(n) \geq n\: log(n)$
$5log(n) \geq log(n)$

Rewriting,

$\quad f(n) = log(log(n)) + n\: log(n) + log(n)$,

where

$\quad n \in \mathbb{N}$

Now, since each term varies only by their logarithmic arguments, we can establish an inequality by direct comparison of those arguments, resulting in

$\quad log(log(n)) \lt log(n) \lt n\: log(n), \forall n \gt 1$

Therefore, it follows that

$\quad f(n) \in O(n\:log(n))$


Is a single symbol, not in a set, a language? I was reading about Turing machines and realized I'm not sure about the difference between the following scenario. Given the alphabet $\Sigma = \{a, b \}$, we have the following assertions:

$a \in R $
$\{a\} \in R$

I think that assertion $1$ is incorrect because $a$ is just a symbol, not a language. On the other hand $\{a\}$ is the language which contains only the $a$ symbol. Given that information, we can prove that $\{a\} \in R$ by trivially building a TM. Here, $R$ denotes the set of recursive languages.

Is my reasoning wrong? Thanks in advance.

By the standard definitions, a language is always a set of (finite-length) words. This means that "$a$" is not a language, but either a symbol or a word.

If $R$ denotes all the regular languages (or alternatively, all the recursive languages), then indeed $a \notin R$. On the other hand, $\{a\}$ is a language, which is also regular (and recursive).

To complete the standard definitions:

an alphabet is a finite set of symbols
a word is a finite-length string of symbols
a language is a set of words (and can be finite or infinite)

of course, there are many possible extensions to the above definitions, such as infinite-alphabet, infinite-length words, etc.


Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$
$$L=\{a^nb^m\mid 2n<m<3n\}$$

Hint: Can you do $$L=\{a^nb^m\mid m=3n\}$$

Try it also for: $$L=\{a^nb^m\mid m=3n-1\}$$

Then you might want to be able not to always have that many $b$.

And there is a bit more to take care of.


Functional Abbreviation for Inst Expression in Turing's 1936 Paper In Turing's 1936 paper On Computable Numbers Page 30-31, and its Correction Page 1-2 :
For a Turing Machine $M$, $Inst(q_i  S_j  S_k  L  q_l ) $ means that if $M$ scans symbol $S_j $ under $m-configuration$ $q_i$, then the symbol on the  square under scanner (with symbol $S_j $ ) is to be replaced by symbol $S_k$, and the scanner/header moves one unit $Left$, and its new $m-configuration$ becomes $q_l$.

At any stage of the motion of the machine, the number of the scanned
square, the complete sequence of all symbols on the tape, and the
m-configuration will be said to describe the complete configuration at
that stage. The changes of the machine and tape between successive
complete configurations will be called the moves of the machine.

The interpretations of the propositional functions involved are as follows :
${R_S}_j(x,y)$ is to be interpreted as "In the complete configuration
$x$ (of $M$) the symbol on the square $y$ is $S_j$.
$I(x,y)$ is to be interpreted as "In the complete configuration $x$
(of $M$) the square $y$ is scanned".
${K_q}_m(x)$ is to be interpreted as "In the complete configuration
$x$ (of $M$) the m-configuration is $q_m$".
$F(x,y)$ is to be interpreted as "$y$ is the immediate successor of
$x$".

Then, for establishing equivalence between Turing Machine and restricted
Hilbert functional calculus, it is written:

$Inst(q_i  S_j  S_k  L  q_l ) $ is to be an abbreviation for:
$(x,y,x',y')$ {
($ {R_S}_j(x,y) \,\&\, I(x,y)\,\&\, {K_q}_i(x) \,\&\,  F(x,x') \,\&\, F(y',y)) \to   $ $( I(x',y') \,\&\, {R_S}_k(x',y) \,\&\, {K_q}_l(x') \,\&\, F(y',z)  ∨  [(
 {R_S}_0(x,z) \to {R_S}_0(x',z))  \,\&\, ({R_S}_1(x,z) \to {R_S}_1(x',z))  \,\&\, ... \,\&\, ({R_S}_M(x,z) \to {R_S}_M(x',z))])$
}  $ S_0, S_1, ..., S_M $ being the symbols $M$ can print.

I am unable to convince myself of the exact correctness of the above formula w.r.t. to the meaning of $Inst(q_i  S_j  S_k  L  q_l ) $. More specifically, why do we have the following expression included? What is he trying to "cover" by including it?

$ ... \,\&\, F(y',z) ∨ [({R_S}_0(x,z) \to {R_S}_0(x',z))  \,\&\, ({R_S}_1(x,z) \to {R_S}_1(x',z))  \,\&\, ... \,\&\, ({R_S}_M(x,z) \to {R_S}_M(x',z))] $

The first part of the disjunction is for stating that the next "state/m-configuration" of the machine is the one established in $Inst(q_i, S_j, S_k, L, q_l)$ (in case z takes as value the next cell of y', i.e., y), the second part of the disjunct is used to say that the part of the tape not scanned by the machine preserves its value.


When can you ignore certain numbers in a recurrence relation? I am trying to understand how to work out time complexities given certain recurrence relation, however I know that in certain recurrence relation some numbers can be omitted since they make no difference when $n$ gets very large. The problem i'm having is being able to identify the numbers that can be omitted.

For example

$T(n) = 3T(n/3 - 2) + n/2$ Can we omit the 2's here and use the master theorem on

$T(n)=3T(n/3) + n$ ?

What about the following

$T(n) = T(n-2) + n^2$ can we say that $T(n) = T(n) + n^2$ and once again use the master theorem?

Not really clear to me when it is OK to omit numbers.

It depends on what you want to reach and on the recurrence relation.

For example, consider the following recurrence relation
$$T(n) = T(n/2 - 1) + 6n,  T(1) =1$$
and assume we are interested on its asymptotic growth.
If we remove the factors $\frac{1}{2}$ in $T(n/2 - 1)$ and $6$ from $6n$ then we have the following relation

$$T(n) = T(n-1) + n$$
that is a closed formula for the sum of the first $n$ positive integers and is $\Theta(n^2)$.

If we omit only $-1$, then we are left with
$$T(n) = T(n/2) + 6n$$
which is $O(n)$. Thus, omitting factors may result in asymptotically different recurrence relations.

As for your examples, $T(n) = 3T(n/3 - 2) + n/2$ is clearly less than or equal to $T(n)=3T(n/3) + n$, so in order to obtain an upper bound for $3T(n/3 - 2) + n/2$ you can use the later relation, but their exact values for each $n$ is certainly differ. However, I don't see any meaning in the relation $T(n) = T(n) + n^2$ unless $n=0$.


What is the difference between radix trees and Patricia tries? I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a normal (uncompressed) trie by merging nodes with their parents when the nodes are the only child. This also holds for Patricia tries. In what ways are the two data structures different?

For example, NIST lists the two as the same:

  Patricia tree

  (data structure)

  Definition: A compact representation of a trie in which any node that
  is an only child is merged with its parent.

  Also known as radix tree.

Many sources on the web claim the same. However, apparently Patricia tries are a special case of radix trees. Wikipedia entry says:

  PATRICIA tries are radix tries with radix equals 2, which means that
  each bit of the key is compared individually and each node is a
  two-way (i.e., left versus right) branch.

I don't really understand this. Is the difference only in the way comparisons are made when doing look-ups? How can each node be a "two-way branch"? Shouldn't there be at most ALPHABET_SIZE possible branches for a given node?

Can someone clarify this? For practical purposes, are radix tries typically implemented as Patricia tries (and, hence, often considered the same)? Or can no such generalizations be made?

I found this post very helpful.

To see the difference between Patricia tries and radix trees, it is important to understand:

The notion of radix, since Patricia tries are radix trees with radix equal to 2.
The way keys are treated: as streams of bits. Keys are compared $r$ bits at a time, where $2^r$ is the radix of the trie.

Suppose that we insert the keys smile, smiled, and smiles (in this order) in a Patricia trie. The binary representation of these keys is the following:

Note that smile is a prefix of smiled, and, analyzing the binary representation, we can see that the first bit that differs (from left to right) is 0 (highlighted in red in the second row); for this reason, smiled will be the left child of smile. Similarly, smiles will be the right child of smiled because they share the same prefix up to a bit whose value is 1 (highlighted in red in the third row). The resulting Patricia trie after inserting the three keys is the following:

If the radix was, for example, 4, then internal nodes could have, at most, four children (with their edges labeled 00, 01, 10, and 11, respectively). In this case, keys would be compared by chunks of 2 bits, and not 1 (as in Patricia tries).

  In what ways are the two data structures different?

To my understanding, the only difference is the radix, which is equal to 2 in the case of Patricia tries. This value can be any power of 2 in regular radix trees.

  Is the difference only in the way comparisons are made when doing look-ups?

In both data structures, the comparison operation is bitwise. However, the number of bits that are checked atomically varies according to the radix. In the case of Patricia tries, bits are compared individually (since radix = 2). This is not necessarily the case in radix trees. In general, bits are checked in chunks of size $\log_2{R}$, where $R$ is the radix of the trie.

  How can each node be a "two-way branch"? Shouldn't there be at most ALPHABET_SIZE possible branches for a given node?

The radix establishes the maximum number of children that the nodes of a radix tree can have. For example, when radix = 2, each node can have at most two children. This is the case of Patricia tries (also known as binary radix trees).

  Are radix tries typically implemented as Patricia tries (and, hence, often considered the same)? Or can no such generalizations be made?

To be honest, I do not have an answer for this question. It seems that both data structures were proposed around the same time by different authors. For historical reasons that I am unaware of, both terms still live today.


What does $L$-uniformity mean? I've understood that $L$-uniformity means that there's a TM that can output the description of $C_n$ in $O(\log n)$ space. Now, that seems odd to me since the description itself (as far as I understand) must be a $O(n)$. I'd be glad for clarification.

Also, in that context: What does $L$-uniform $NC^k$ means?

Thanks!

What is usually meant by saying that a (not necessarily binary) function  is computable in $O(\log n)$ space, is that there exists a Turing machine computing it which uses only $O(\log n)$ space in its work tape. This limitation does not concern the output tape, which is write only. You can also think of this condition as being able to, given $i$, output the $i$'th bit of the circuits description using only $O(\log n)$ space.

A circuit family $\{c_n\}_{n\in\mathbb{N}}$ is logspace uniform $NC^k$ iff $c_n$ is a circuit with $n$ inputs of size $poly(n)$ and depth $O(\log ^k n)$, and additionally, there exists a logspace Turing machine such that given $1^n$ as input, outputs a description of $c_n$.


A greedy approximation algorithm for max k-cut The max k-cut problem is: Given an undirected graph G= (V;E) with nonnegative edge costs, and an integer k, find a partition of V into sets $S_1,\cdots,S_k$
so that the total cost of edges running between these sets
is maximized. The aim is to find a greedy algorithm for this problem that achieves a factor of $(1-\frac{1}{k})$.

My algorithm is: at the beginning, all the vertices of V is seperated in to $S_1,S_2,\cdots,S_n$. Once we have $S_1,\cdots,S_{t+1}$, we find $S_p,S_q$ s.t. $c(S_p,S_q)=min_{\{i,j\}}c(S_i,S_j)$ and merge $S_p,S_q$ together to get $t$ parts until $t=k$.
Let $ALG_t$ be the solution given by this algorithm for $t$ parts. $OPT_t$ is the optimum value for $t$ parts.
By induction, $ALG_n=OPT_n\ge(1-\frac{1}{n})OPT_n$.
Since there are $\binom{t+1}{2}$ sets of edges between $S_1,\cdots,S_{t+1}$, at least one of these sets with cost $\le\frac{1}{\binom{t+1}{2}}ALG_{t+1}$.
By the construction of the algorithm, we merge these two sets of vertices together, then we have $ALG_t\ge ALG_{t+1}-\frac{1}{\binom{t+1}{2}}ALG_{t+1}=(1-\frac{1}{\binom{t+1}{2}})ALG_{t+1}\ge(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})OPT_{t+1}\ge(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})OPT_{t}$
But it's not true that $(1-\frac{1}{\binom{t+1}{2}})(1-\frac{1}{t+1})\ge(1-\frac{1}{t})$.
Therefore I wonder if there is some other arguments or algorithm?

The natural greedy approach goes roughly like this:

  Go over the vertices one by one. For each one, allocate it to a part in a way maximizing the total cost of edges cut.

There are at least two natural ways of defining total cost of edges cut:

Total cost of edges between the vertex and vertices already allocated to different partitions.
Same as 1, together with the expected cost of cut edges to vertices not already allocated.

In this case both ways are the same, but the second shows the connection between the greedy algorithm and the trivial randomized algorithm, which allocates the vertices completely randomly.


Converse of pumping lemma for regular expressions I want to come up with a language that satisfies the pumping lemma while not being a regular expression.

I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is not a regular expression, as  it would not be possible to create an automata that recognizes it. This last part is where I'm having a bit of trouble, as I think I have the right idea, but can't formalize it. This language is just a regular expression $\big(\{0^i : i \in \mathbb{N}\}\big)$ concatenated with something that is not a regular expression $\big(\{0^i1^i: i \in \mathbb{N}\}\big)$.

Is my thought process correct? Can this be generalized? If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE? I believe so, because we know that if $L$ is a RE then so is $L^r$. And so we end up with  $(L')^rL^r$, and we can use the contrapositive of the pumping lemma to prove this language is not regular. Any insight would be helpful!

Yes, $L_>=\{0^i1^j: i > j > 0\} $ is a non-regular language.

However, it does not satisfy the pumping lemma for regular languages. Assume for the sake of contradiction that $p$ is a pumping length for $L_>$. Consider $w=0^{p+1}1^p$. Let $w=xyz$ with $|y|>1$ and $|xy|<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$. That contradicts that $p$ is a pumping length.

The most we can say is that all words in $L_>$ can be pumped up.

  If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE?

No. A simple counterexample is $L=\Sigma^*$, the language of all words while $L'$ is any non-regular language that contains the empty word such as $\{a^{n^2}\mid n\in \Bbb N_0\}$. $LL'$ is still the language of all words, which is regular.

Exercise 1. Find two languages $A$ and $B$ such that

$A$ is regular
$B$ is not regular
$A\subsetneq B$
$AB$ is regular.

Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.


Determine if there are 2 integers in 2 separate arrays add up to a given number If I'm given 2 unsorted arrays A and B of n distinct integers and an integer z, how can I determine if there exists an integer in A and an integer in B that add up to z with an expected run time of O(n)?

I'm pretty sure that I would have to use a hash table(s) of some sort since I'm dealing with expected run time but I'm not sure how the algorithm would work.

Any help would be really appreciated! Thanks!

Insert the elements of the first array into a hashset S by subtracting from z. I.e., if 3 is an element of the first array, instert z - 3 into S. Then for each element in the second array, check if z - element is already in S. This procedure is O(n).


Something I don't understand about Genetic Algorithms I've had a bit of experience programming Neural networks but I am fairly new with genetic algorithms (I'm only 17). I have a major issue that I can't understand. If a child get's one chromatid from one parent and another from another parent, then the genes are crossed over, how do you determine which alleles are active in the child? How do other people go about mating with genetic algorithms. No need to go deep into it because I also want to work somethings out for myself but a general idea would be good enough. Thanks in advance.

Generally speaking, evolutionary algorithms stop well short of trying to model real biology, and this is one example of something that occurs in nature but not in commonly used evolutionary algorithms.

Instead, we tend to use a system where all individuals have only one value for each gene, and they're all "active". Replication, mutation, and recombination are considered to be atomic operations with no concern given to any intermediate stages. Consider the simplest case of a binary encoding. You might have two parents, A and B, as

A = 0101101001
B = 1001010010

To do crossover, we simply create an offspring by choosing exactly one parent for each bit in the offspring to copy from. We can formalize this a bit with something called a mask -- a bit string where a 1 indicates that we choose the value from A and a 0 indicates we choose from B. Thus, one point crossover might have a mask like

M = 0000001111

with our parents A and B, we would then get a child C as

A = 0101101001
          ^^^^
B = 1001010010
    ^^^^^^
C = 1001011001

So here, the offspring C has gotten copies of the first six genes of parent B and the last four of parent A, but at no point do we consider the process by which chromosomes would be copied in a biological system. We simply allocated a new variable and did a memory copy to instantaneously duplicate parts of the parents.

If we want to mutate the offspring, we might simply pick a bit at random and flip it. Again, we don't worry about biology here and how mutations actually occur in nature. We just define mutation to be the flipping of a single bit in memory and do it.

One point crossover is about the simplest thing you could do, but essentially all commonly used methods look similar in that the child gets a single value for each position and no explicit notion of binding or connection to the parents is considered. We don't really think of crossover in terms of chromatids -- we just directly copy allele values using some well-defined (but probably not biologically plausible) crossover operator. So there's never any question of which allele values are active -- they all are.


Dynamic Programming - Thief Variation Probem I've encountered a Dynamic Programming problem which is a variation of the thief one.

Say you are a thief and you are given a number of houses in a row you should rob :

$$House_1,House_2 \dots House_N$$

with each house having the following values : $$(x_i \geq y_i \geq z_i \gt0)$$

You profit X  if you rob a house but none of the adjacent houses.

You profit Y  if you rob a house and exactly one of the adjacent houses.

You profit Z  if you rob a house and both of the adjacent houses.

Cases with houses A-B-C would be :

$$Profit(001)=0+0+C_x$$
$$Profit(101)=A_x+0+C_x$$
$$Profit(110)=A_y+B_y+0$$
$$Profit(111)=A_y+B_z+C_y$$

Where 1 stands for robbing the house and 0 for not robbing the house

Obviously you can't utilize the Z value for the first and the last house and each set of values is random.

Now the question is : Which houses should you rob to get the maximum profit?

My main issue is that i can't establish a base case for this problem.

At first i thought of creating a N*M array with M being the maximum amount of houses i can rob from 0-N when every house is not robbed and think like : Rob it - Don't rob it but came up with nothing.

Any tips or directions would be appreciated.

Thanks in advance.

For $i=1,\dots,N$, and $r \in \{S,R,B\}$
define $OPT[i,r]$ as
the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints:

If $x=S$  (as in Skip) then house $i$ must not be robbed.
If $x=R$ then house $i$ must be Robbed while house $i+1$ will not be robbed (to avoid a case distinction later we pretend that house $i+1$ exists even when $i=N$).
If $x=B$ then Both house $i$ and house $i+1$ need to be robbed.

For $i=1$ you have $OPT[1,S] = 0$, $OPT[1,R] = x_1$, $OPT[1,B] = y_1$.

For $i>1$ you have:
$$
OPT[i, S] = \max\{ OPT[i-1, S], OPT[i-1, R] \},
$$
$$
OPT[i, R] = \max\{ x_i + OPT[i-1, S], y_i + OPT[i-1, B] \},
$$
$$
OPT[i, B] = \max\{ y_i + OPT[i-1, S], z_i + OPT[i-1, B] \}.
$$

The optimal profit is then:
$\max\{OPT[N, S], OPT[N, R] \}$ and can be computed in $O(N)$ overall time using the above formulas.


Maximizing the Sum of a Subset with Excluding pairs I have a set of nodes S where all the nodes of an arbitrary integer value.  I Also have a set of pairs of nodes from S, indicating that those node cannot be in the same subset.  Given a subset of S, how can I determine the largest possible Sum of that subset taking into account the exclusion pairs.

Example:

S = (x1:50, x2:20, x3:30, x4:15, x5:70)

Exclusion = {(x1,x2), (x4,x5), (x2,x4)}

Starting set = (x1,x2,x4,x5)

Best Possible Sum = (x1,x5)

Your problem is known as maximum-weight independent set (more often, simply maximum independent set). We think of the $x_i$ as vertices in a graph, each constraint corresponding to an edge $(x_i,x_j)$. An independent set is a set of vertices with no edges, which is exactly your condition.

Unfortunately, maximum-weight independent set is NP-complete, and $n^{1-\epsilon}$-hard to approximate (for every $\epsilon>0$) even when all weights are the same.


The origin and the meaning of "Abstract Syntax Tree" This question is closely related to Does an abstract syntax tree have to be a tree? and is partially answered there, but I would like to be more precise and to have more concise answers.

What is the origin of the term?
Are there any formal definitions of AST?
If I understand correctly the spirit of the use of "AST" term, it is a misnomer: an AST is any combinatorial object or datum that one tries to represent by strings of characters using more or less simple syntax that should ideally reflect the internal structure of the object/datum.  For example, in first-order logic and in lambda calculus, expressions like
$(\forall x)(x = x)$ or $(\lambda x.x)$
do not really represent trees because bound variables introduce loops.
Do I understand correctly?

Basically, I broke up here in simpler pieces a single question: What is AST?
Without answering parts (1) and (2) the answer will probably be incomplete or hard to verify, and if (1) and (2) are answered, an answer to (3) probably should follow.

Update

I have realized that it is not the "syntax tree" that is abstract, but the syntax.  This clarifies the terminology to me and makes this question less relevant.  Basically, I parsed "abstract syntax tree" incorrectly.

I also provided an answer to the related question.

You are asking three questions.  I will answer one.

I don't think "abstract syntax tree" is a misnomer.  It aims to represent the syntax of the expression.  It is not claimed to represent all of the meaning (semantics) of the expression.  The issue with bound variables that you mention relates to semantics rather than syntax.

Also, remember that names are merely that: references to some concept, to serve as an aid to communication.  Sometimes the concept is subtle or nuanced enough that no name is going to fully represent all the complexities of the concept, so we choose the best name we can (while keeping it fairly short).  And a name is just an aid to communication, so not all concepts have a fully precise, rigorous definition -- if it is used in a way that aids understanding and facilitates communication, that is often  OK.


Is there a more efficient algorithm than backtracking/dynamic programming? Consider the following game:

One day a castle is attacked at sunrise (by surprise) by n soldiers.

Each soldier carries a canon and a rifle.

The castle has strength s.

On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points).
After all the soldiers have fired, the castle sends dpw defenders to battle them.

In the ensuing days the castle and the soldiers battle it out following these rules:

All the soldiers fire first. A soldier can fire his canon at the
castle or his rifle at one of the defenders (but not both and each
soldier can only shoot once). One shot at a defender kills him. One
shot at the castle decreases its strength by 1.
Then each of the d defenders shoots at one soldier (and only
one) killing him.
If the castle still has strength points (i.e. s>0) it sends a
new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.
Repeat 1 through 3 on each new day.
If all soldiers are killed by the defenders, the castle wins.
If there are zero defenders after the soldiers shoot and the
castle strength is zero, the soldiers win.

We would like to know the minimum number of rounds the soldiers need to win the game (or if not possible the minimum number of rounds for the castle to win the game).

We would also like to know the number of soldiers, defenders and castle strength at the beginning of each round for the minimum number of rounds solution.

An easy way to solve this problem seems to me to be by recursive backtracking/depth first search or dynamic programming.

The problem however seems simple enough that a better/faster solution seems likely to exist (one that doesnt involve a large search or maybe even a search at all).

Is it obvious what that better strategy/algorithm might be?

(Throughout this answer I use $\phi = \frac{1+\sqrt{5}}{2}$, which is the Golden Ratio.)

Solution:

If $s\leq n$, the attackers can win in one day.
If $s+dpw<\phi^2n$ and $s<2n$, the attackers can win in $2+\max(k,0)$ days, where
$$k=\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$
If $dpw<n$, the attackers can win in $c+\max(k,0)$ days, where
$$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$
and
$$k = \left\lceil\frac{\log_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$
If the attackers cannot win, the minimum number of days for the castle to win is $2$ (the attackers all fire their cannons and are wiped out on day two).

Proof:

For a given day $i$, let $s_i$ be the remaining castle strength, $a_i$ be the remaining attacking force, and $d_i$ be the remaining defending force.

First consider the case that $d_i = dpw$ (that is, the attackers killed all defenders the day before). Assume that the attackers leave $x$ defenders alive but do not destroy the castle; then
$$a_{i+1} = a_i-x;$$
$$d_{i+1} = dpw+x;$$
$$s_{i+1} = s_i-(a_i-(dpw-x)) = (s_i+dpw)-(a_i+x).$$
On day $i+1$, the defending force is larger than on day $i$ and the attacking force is smaller than on day $i$. Furthermore, even if the attackers return to the strategy of wiping out the defending force on day $i+1$,
$$a_{i+2} = a_i-x;$$
$$d_{i+2} = dpw;$$
$$s_{i+2} = s_{i+1}-(a_{i+1}-d_{i+1}) = s_i+2dpw+x-2a_i.$$
If, instead, the attackers had wiped the defending force on day $i$, the castle's strength would be $s_i+2dpw-2a_i$. Therefore, it is never advantageous to leave both defenders and the castle alive on the same day.
(Note that if $s_i+2dpw+x-2a_i<0$ -- that is, they destroyed the castle on day $i+1$ -- they could have have done the same thing without losing troops; therefore, while it might not always be disadvantageous, it is never advantageous.)

Now the question is, when the attackers do destroy the castle, how many days will it take to kill the remaining defenders (with the obvious assumption that the attackers would not make a final push on the castle unless they can still win)? Assume, without loss of generality, that the castle is destroyed on day $q$ and that there are $x$ defenders remaining alive. So
$$d_{q+1} = x;$$
$$a_{q+1} = n-x;$$
$$d_{q+2} = d_{q+1}-a_{q+1} = 2x-n;$$
$$a_{q+2} = a_{q+1}-d_{q+2} = 2n-3x;$$
$$d_{q+3} = d_{q+2}-a_{q+2} = 5x-3n;$$
$$\dots$$
From this we can see that $d_{q+i+1} = Fib(2i+1)x-Fib(2i)n$. Therefore, (finding the closed form of $Fib(\cdot)$ and four pages of algebra later), the attackers will win
$$k = \left\lceil\frac{\log_\phi{\left(\frac{n+x\phi^{-1}}{n-x\phi}\right)}}{4}\right\rceil$$
days after destroying the castle. $x = s'+dpw-n$, where $s'$ is the strength of the castle on the day it is destroyed.

On every day that the attackers can make a final push on the castle, the question is, "Would it be advantageous to wait until tomorrow?" Every day (after the first) that the attackers do not make a final push, the castle's strength decreases by $n-dpw$. Therefore, at the beginning of the day of the final push (day $i$), $s' = s-n-(i-1)(n-dpw)$, so $x_i = dpw-(n-s') = $ $s + i\cdot dpw-(i+1)n$ (where $x_i$ is the remaining defending force if the attackers pushed on day $i$). It is advantageous to wait another day if
$$
\frac{\log_\phi{\left(\frac{n+x_{i+1}\phi^{-1}}{n-x_{i+1}\phi}\right)}}{4} + 1
<
\frac{\log_\phi{\left(\frac{n+x_i\phi^{-1}}{n-x_i\phi}\right)}}{4},$$
that is, when one more than the number of days to destroy the $x$ beginning on day $i+1$ is less than the number of days to destroy $x$ beginning on day $i$. Three pages of algebra later, we find that it becomes advantageous to destroy the castle on the day
$$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil.$$

After destroying the castle, we still have to kill the troops, so the total number of days is $c+k$, using $i=c$ to find $k$.

Finally, we must handle the edge case that $dpw \geq n$. Intuitively, the attackers can only be victorious only if they can destroy the castle on the first day of fighting (day 2) with enough troops left to defeat the remaining defenders. This can only happen if $s<2n$ (they can destroy the castle by the end of the second day) and if $s+dpw<(\phi+1)n$ (they can destroy the castle and do enough damage that the defenders cannot effectively retaliate); it will take $\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil$ days to kill the rest of the defenders.


Capacity of the Deletion Channel Consider a Binary Deletion Channel with a deletion probability p of 1/2 and the channel has no error correction coding at all and that any given message can only be sent once. I want to conjecture that the capacity for the aforementioned channel is zero ( channel capacity for the Deletion Channel is presently unknown), can anyone point to any known complexity results that would point me in the direction of proving or disproving my conjecture?

The capacity of a deletion channel with deletion probability $p$ is still not fully understood, however it is known to be somewhere between $1-h(p)$ and $(1-p)/9$.

See a survey by Michael Mitzenmacher on deletion channels: A survey of results for deletion channels and related synchronization channels.


Which grammar is this? Having the grammar G = (V,P,S) with variable V = {S,A} over the alphabet {a,b} with the rules:

S->aA
A->Sbb|b

How can i recognize which kind of grammar is this? I think that's not "regular expression" because in the second rule there are 2 letters (bb) instead of one, so i think it's a "context free" grammar. Am i right?

Technically it is a linear grammar, where every production is of the form $A\to uBv$ where $A,B$ are variables, and $u,v$ are terminal strings. The linear languages are in between the regular and context-free languages.

The power of these grammars is reduced because in every string (sentential from) derived there is (at most) one variable. They are more powerful than right-linear grammars because the terminal strings that are generated during the derivation can appear both left end right from the variable. An example of a linear language that is not regular is $\{a^nb^n \mid n\ge 1\}$.
An example of a language that is context-free, but not linear, is $\{ w\in\{a,b\}^* \mid w \text{ contains the same number of $a$ and $b$}\}$.


Decidability. $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$ I'm trying to understand decidable languages. In particular, I would like to show that
$$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \,.\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$
I don't quite understand the process of proving these. I know that $a^kb^k$ is not regular, so then no DFA accepts it. I also know that $A_{DFA}$ (acceptance DFA) is decidable, I also know several other decidable languages like $E_{DFA}$ and $EQ_{DFA}$. How can I use these to prove that $B$ is decidable?

If no DFA accepts $a^kb^k$, doesn't that mean that $A_{DFA}$ will reject? So if $A_{DFA}$ rejects then shouldn't the decider for $B$ accept?

Corollary 3.19 from "An Introduction to the Theory of Computation": "A language is decidable if and only if some nondeterministic Turing machine decides it."

You can construct a nondeterministic Turing machine, $TM_A$, which is a decider for the language : $A_DFA = \lbrace \langle B,w \rangle \mid \text{$B$ is a DFA accepting $w$}\rangle$.

$TM_A$ works as follows on input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is a string:

Simulate $B$ on input $w$.
If the simulation ends in an accept state, accept. If it ends in an non-accepting state, reject.

Update:
The string $a^kb^k$ is not regular and cannot be accepted by a DFA. A CFG for that string would be something like : $A \to aAb \mid \varepsilon$.


Maximum cost path in integer matrix In preparation for my design and algorithms exam, I encountered the following problem.

  Given a $2  \times N$ integer  matrix $(a[i][j] \in [-1000, 1000])$ and an unsigned integer $k$, find the maximum cost path from the top left corner $(a[1][1])$ and the bottom right corner $a[2][N]$, given the following:

$\bullet$ The path may not go through the same element more than once

$\bullet$ You can move from one cell to the other vertically or horizontally

$\bullet$ The path may not contain more than $k$ consecutive elements from the same line

$\bullet$ The cost of the path is determined by the sum of all the values stored within the cells it passes through

I've been thinking of a simple greedy approach that seems to work for the test cases I've tried, but I'm not sure if it's always optimal. Namely, while traversing the matrix, I select a the maximum cost cell on the vertical or horizontal and then go from there. I've got a counter I only increment if the current cell is on the same line with the previously examined one and reset it otherwise. If at some point the selected element happens to be one that makes the counter go over the given value of $k$, I simply go with the other option that's left.

However, I feel that I'm missing out on something terribly important here, but I just can't see what. Is there some known algorithm or approach that may be used here?

Also, the problem asks for an optimal solution (regarding temporal complexity).

This problem was basically made for dynamic programming (DP). Just review it and follow a couple of examples and solving this problem is straight-forward.

Your simple greedy approach does not always work. Consider:

[ begin ] [  2 ]
[ 3 ]     [ 10 ]
[ 1 ]     [ -1000 ]
[ 1 ]     [ end ]

The optimal solution would be to go right, down, left, down, down, right.


Constructing logical sentences that involve negative integers over the nonnegative integers Consider the following statement:

  If $x$ and $y$ are integers and $z$ is a nonnegative integer and $x + z = y$, then $x$ is at most $y$.

I'd like to build a sentence for this statement in the model of $(\mathbb{N}, +)$, where $\mathbb{N}$ is the set of nonnegative integers and $+$ is just the relation (where here I define a relation as a mapping from tuples to a boolean value): $\{(a,b,c): a + b = c\}$. By "sentence", I mean a logical formula with no free variables.

How can I write the highlighted statement in terms of the given model if variables in this model can only take only take on nonnegative integers? It seems at best I can only build a sentence in this model for the following statement:

  If $x$ and $y$ are nonnegative integers and $z$ is a nonnegative integer and $x + z = y$, then $x$ is at most $y$.

Or is it possible to define negative quantities in the model of $(\mathbb{N}, +)$?

Any integer $x \in \mathbb{Z}$ can be expressed in the form $x = x_+ - x_-$ where $x_+ \in \mathbb{N}$  and $x_- \in \mathbb{N}$ (i.e., every integer can be expressed as the difference of two natural numbers; and conversely, the difference of any two natural numbers is always an integer).

Try using that to formulate your statement.  You'll need to work out how to define the $\le$ operator, but that's a separate issue.


Undecidable Problem for Regular Languages It might seems weird, but, Are there any undecidable problems concerning regular languages? I mean questions concerning the regular languages, not the problems like "Is the language of a TM regular?".

Clarification: By the questions regarding regular languages, I mean that the problem consists of regular languages, i.e. the relation between two or more regular languages, and/or about the properties of a regular language.

Thanks in advance

Yes, there are undecidable problems like the Post Correspondence Problem that can be coded into the language of a finite state automaton, as explained in my earlier answer to a (slightly broader) question: https://cs.stackexchange.com/a/6198

The result can be traced to a paper by Engelfriet and Rozenberg dealing with the so called twin shuffle operation.
Fixed Point Languages, Equality Languages, and Representation of
Recursively Enumerable Languages (J. ACM)
doi:10.1145/322203.322211

Recently Endrullis, Shallit and Smith presented the paper Undecidability and Finite Automata at the conference DLT2017 (doi:10.1007/978-3-319-62809-7_11, arxiv:1702.01394) which deals with your question:

  Abstract. Using a novel rewriting problem, we show that several natural decision
  problems about finite automata are undecidable (i.e., recursively
  unsolvable). In contrast, we also prove three related problems are
  decidable. We apply one result to prove the undecidability of a
  related problem about k-automatic sets of rational numbers.

I am very proud that one of the references in this paper is to my earlier SE answer!


Proof of non-receipt of the file The condition of the problem and the statement of the problem: Alice pays Bob for the fact that he, at the request of users, gives out files of interest to users. For example, the user is interested in the file #hash1. The user learns from Alice that this file is stored by Bob. The user connects to Bob and asks to start downloading the file #hash1 to his computer. Then there are two possible bad outcomes. Either Bob is dishonest and refuses to transfer the file to the user, or the user is dishonest and, after receiving the file #hash1 from Bob, lies to Alice and tells her that Bob did not send him anything.

My question is: are there any algorithms in cryptography that Alice will be able to determine the truth and not pay money to Bob (if he lies) or not stop cooperating with Bob (if the user lies)? At least partially. Thank you.

Personally, I thought that my problem relates to the topic of fair exchange (when the two sides exchange bit by bit interesting information and if one side begins to behave dishonestly, the second party immediately stops exchanging and the damage for it is minimal). However, this does not solve the problem that the user can simply lie and say that Bob did not send anything.
I just want to know if it's possible to control the work of a third-party server for Alice.

Some partial idea: You want to avoid a situation where the user receives the file and claims they didn't.

Bob adds some random padding to the file so that the user doesn't know the size. Bob sends part of the data and waits for a receipt, then sends more data and waits for a receipt. When the file is sent completely, the user doesn't know this. So refusing to send the receipt means they might never get the complete file. When Bob claims the whole file has been received, the user contacts Alice, who has a key to unlock the file.


Is my reasoning wrong that $PSPACE$ should not equal $EXPTIME$? It's impossible for a problem to require exponential space without being exponential-time.

Consider that if an $EXPSPACE~~complete$ problem can be solved in $2^n$ time. It will now fall into the class $EXPTIME$.
Then $EXPSPACE~~complete$ problems are in $EXP$ if they can be solved in $2^n$ time. This means they can reduce into $EXP~~complete$ problems and vice versa.

To me, this should be easy to write a proof that $EXPTIME$  = $EXPSPACE$.
My intuition tells me that if $Exptime$ = $Expspace$; then $PSPACE$ != $EXPTIME$,
Because $PSPACE$ already is not equal to $EXPSPACE$.
Question
As an amateur, what would make this reasoning be wrong or right?

I did not understand the first part of the question, but just so you know, its unknown whether $EXPTIME=EXPSPACE$ or not. What is known is that $EXPSPACE\subseteq \bigcup _cDTIME(2^{2^{n^c}})$ from the relations shown here.
The second part of the question: If $EXPTIME=EXPSPACE$ then $PSPACE\neq EXPTIME$, is absolutely correct: by the space hierarchy theorem, $PSPACE\subsetneq EXPSPACE$ and therefore $PSPACE\subsetneq EXPTIME$ as $EXPSPACE=EXPTIME$ (by our assumption).


Generating integer vectors sorted by total weight I am trying to implement an algorithm that finds the key of the RC4 cipher from the inner permutation. For each key byte I have several options, each with different weight. Is there any way, to test first the possibilities with highest weight, than with second highest, and so on?

Basically what I need is to generate vectors like this (for 3 byte key):

[0,0,0]
[1,0,0]
[0,1,0]
[0,0,1]
[1,1,0]
[1,0,1]
[0,1,1]
[1,1,1]
[2,1,1]
...

So it is sorted by sum.

(I have the bytes stored in a table sorted by weight, highest weight on the top.)

A similar problem is solved here: application of Dijkstra's algorithm, but I don't know how to apply it to my problem.

The paper only mentions that they do it in iterative depth manner.

Is there any algorithm which solves this problem?

I'm assuming the following version of the problem. We are considering all vectors in the set $[N_1] \times \cdots \times [N_d]$ (of which there are $N_1\cdots N_d$). We are given weights $w_{i,1} \leq \cdots \leq w_{i,N_i}$ for each of the $d$ sets (if you prefer, you can index the elements starting from 0 instead of starting from 1). Our goal is to enumerate $[N_1] \times \cdots \times [N_d]$ in non-decreasing order of weight, where the weight of $(x_1,\ldots,x_d)$ is $w_{1,x_1} + \cdots + w_{d,x_d}$.

One possible approach uses a heap. The heap is initialized with $(1,\ldots,1)$. At each step, we extract the element $(x_1,\ldots,x_d)$, output it, and insert the up to $d$ elements obtained by increasing each of the coordinates by 1 (unless it equals its maximum). It is hard to estimate the complexity of this algorithm, but it might work reasonably well in practice.


SVM optimization objective: why are we maximizing $\frac{1}{\|w\|}$? I'm learning about Support Vector Machines(SVM).
I understood that their objective is to maximize the margin between the decision line and the closest point to it.
For simplicity, let's assume we have a linear SVM and linearly separable data X.
We would like to find the maximum distance D and vector W, such that

$\dfrac{W^T \cdot X_i+W_0}{\|W\|}\geq D$ for all $X_i$ in the first class

$\dfrac{W^T \cdot X_i+W_0}{\|W\|}\leq-D$ for all $X_i$ in the second class.

Why is the problem equivalent to maximizing $\frac{1}{\|W\|}$, given the following constraints are satisfied:

$W^T\cdot X_i+W_0\geq1$ for all $X_i$ in the first class

$W^T\cdot X_i+W_0\leq-1$ for all $X_i$ in the second class.

I'm more interested in a formal proof than in the intuition.

Let's slightly rewrite the condition you give: the quantity
$$ \frac{W^T \cdot X_i + W_0}{\|W\|} \mp D $$
is non-negative for $X_i$ in the first class (with $-D$), non-positive for $X_i$ in the second class (with $+D$). Now suppose $\lambda > 0$. Then the quantity
$$ \frac{(\lambda W)^T \cdot X_i + (\lambda W_0)}{\|\lambda W\|} \mp \lambda D $$
satisfies the same properties as before; in fact the two sets of inequalities are equivalent. Therefore we can assume without loss of generality that $\|W\| = 1$ (choose $\lambda = 1/\|W\|$), and so the quantity in question becomes
$$ W^T \cdot X_i + W_0 \mp D, $$
where we are promised that $\|W\| = 1$. Now divide everything by $D$ to get another quantity satisfying the same properties:
$$ (D^{-1}W)^T \cdot X_i + (D^{-1}W_0) \mp 1. $$
Maximizing $D$ is the same as minimizing $D^{-1} = \| D^{-1} W \|$, which is the same as maximizing $1/\|D^{-1} W \|$. Now imagine that instead of $W,W_0$, you were optimizing over $W'=D^{-1}W,W'_0=D^{-1}W_0$; for each choice of $W',W'_0$ you can recover $D = 1/\|W'\|$ and so $W,W_0$, which shows that both problems are equivalent. In these terms, you want the following quantity to satisfy the required properties:
$$ W'^T \cdot X_i + W'_0 \mp 1. $$
Under these conditions, you want to maximize $1/\|W'\|$.


Prove or disprove the following proposition $L_1^*∪L_2^*⊆(L_1∪L_2)^*$ $L_1^*∪L_2^*⊆(L_1∪L_2)^*$

I actually disproved the opposite proposition $[(L_1∪L_2)^*⊆L_1^*∪L_2^*]$ and my intuition tells me that this is actually true... I tried to show that the combinations of words in the right group $[(L_1∪L_2)^*]$ obviously contain all the words from the left group $[L_1^*∪L_2^*]$ and it's also very plain to see, but I have no idea how to formalize it.

Any idea how to formally prove it?
Thanks.

This is true.
You only have to prove the following staments:

if $A\subseteq B$ then $A^{*} \subseteq B^{*}$,
If $A\subseteq C$ and $B\subseteq C$ then $A \cup B \subseteq C$.

We know $L_1 \subseteq L_1 \cup L_2$ for 1. we can conclude $L_1^{*} \subseteq (L_1 \cup L_2)^{*}$, analogously $L_2^{*} \subseteq (L_1 \cup L_2)^{*}$. For 2. we can conclude $L_1^{*} \cup L_2^{*} \subseteq (L_1 \cup L_2)^{*}$.


Undergraduate studies: Math or CS? hope it's possible for this question to be answered in an objective manner.

I'm not studying in a liberal arts college so basically I only get to study one subject. Which would be the better preparation for future research (probably grad school) into theoretical CS? The standard undergraduate math course with analysis and algebra, or the standard undergraduate CS course with algos and concurrency and the like.

Echoing Raphael's comments, this is highly subjective without knowing you personally. However, here are the things I'd consider:

Many schools are flexible for your undergrad program, meaning that what you choose likely won't affect your graduate career too too much, particularly if you take a good number of classes in each subject.

Do you like calculus/real analysis, or only discrete math? It varies from school to school, but if you're not into calculus at all, probably better to stick with CS.

Likewise, do you want to learn programming? If you have no interest in learning about caching, hardware, programming language concepts, or more "applied" aspects of computer science, then Math might suit you better. Many undergraduate CS programs serve the dual purpose of preparing coders for industry and preparing future grad students. You will likely have to take non-theoretical classes at some point.

Are you more interested in creating new algorithms, or analysing discrete structures? My guess is that CS will beter prepare you for creating new algorithms and solving problems, while Math will better prepare you for detailed proofs about discrete structure.

I would reccomend at least taking a few comp-sci classes. My experience is that people with a math backgorund, but not a computer science background, aren't equipped as well to communicate about things like algorithms and pseudocode. As an example, when talking about Breadth First Search in a math Graph Theory class, the professor had to go and define what a queue was. In a CS class, data structures will be something you cover once and then can keep using later on. Likewise, the pseudocode I've encountered in such classes was full of numbered steps and GOTOs, as apposed to the clean iterative or recursive definitions from CS classes.


How do genetic algorithms work exactly? I was looking at the basic genetic algorithm here

http://www.ai-junkie.com/ga/intro/gat1.html

But I have some questions about things I didn't get.

To reiterate:

You have a problem you want a good enough solution to.

You create N random solutions (encoded as bits of 0 and 1)

You evaluate a fitness or score for each for how good a solution it is.

Pick randomly 2 different of them. Based on each score, they have a higher chance of being picked. (i.e. higher score = higher chance of being picked, but the sum of all probabilities add to 100%)

Then for those 2 (call it A and B) picked, there is a cross over step.
There is a chance associated with a crossover. The link uses 70%. So if the crossover happens, then we pick a random point and exchange the bits of both A and B after the point. This creates C.

We created a new solution. Do we remove one of the existing ones? If so, which one?

Then there is a mutation step. This is the part that confuses me most.

Does mutation step occur regardless of if the crossover step happened or not?
What do we mutate? A or B or C?
For whatever we mutate, does mutate mean we iterate over each bit, and for each bit there is a 0.1% chance to flip the bit?

Finally reevaluate the score for all and repeat all of this until you find a good enough solution.

Does anyone know?

Looking at the code the tutorial provides answers your questions. First of all, as it's described/implemented, crossover doesn't create a new string, it just modifies the two selected ones. So,

Yes, mutation always occurs
You mutate both A and B. There is no C
Yes.


Peterson Algorithm for process synchronisation Consider Peterson's algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

repeat

flag[i] = true;
turn = j;
while (P) do no-op;
Enter critical section, perform actions, then
exit critical section
Flag[i] = false;
Perform other non-critical section actions.

Until false;

For the program to guarantee mutual exclusion, the predicate P in the while loop should be

a) flag[j] = true and turn = i

b) flag[j] = true and turn = j

c) flag[i] = true and turn = j

d) flag[i] = true and turn = i

=============================================================================================

Now, in original peterson algorith, we have -

I'm writing just the important lines from the algorithm and not the whole algorithm -

  1) flag [process] = 1;

  2) turn = process ;

  3) while (interested [other] == True && turn == process);

  4) ///////***CS///////

  5) flag [process] = false;

  out of CS

  Now, according to given question -

  flag[i] = true;
      turn = j; i.e process i is interested as flag[i] = true, but turn = j i.e turn is of process J.

So, which process is exactly currently executing?

Question 1) Process i or Process j

Question 2) Which process are we blocking in while loop i.e stopping to enter CS?

  Also, at exit of CS - flag[i] = false;

  this means, Process i, is already in CS?

Now Pi is already in CS, this means, process j is executing and we should hold it in while loop and not let process j eneter CS.

  So, according to know peterson algo I mentioned above -

  line 3) while (flag [other] == True && turn == process);

  while(flag [i] ==true && turn = j);

  both are true so, while loop is true and process Pj should spin here
  and not go to CS.

  and this matches with option c. but answer is option b)

  Also, folks are saying that option c) will allow both Pi and Pj into
  CS.

May you guys please explain, how option b) is answer!

Firstly, since the program at the start the question starts with "flag[$i$] = true", it should be run by Process $i$. Here is the full program again formatted slightly better. Note that the I replace "Enter critical section" and "exit critical section" with comment "// inside the critical section", since there is no code that actually corresponds to them. Once the process breaks out of the "while (P)  do no-op" loop, it is in the critical section (CS). The process is exiting the critical section at the exact point of time when it is executing "flag[$i$] = false".

  repeat

  flag[$i$] = true;
  turn = $j$;
  while ($P$) do no-op;
  Perform some actions  // inside the critical section
  flag[$i$] = false;
  Perform other non-critical section actions.

  Until false;

The following is the full program run by Process $j$. You should be able to figure out the code represented by $Q$ once you have accepted my answer. :)

  repeat

  flag[$j$] = true;
  turn = $i$;
  while ($Q$) do no-op;
  Perform some actions   // inside the critical section
  flag[$j$] = false;
  Perform other non-critical section actions.

  Until false;

These two different programs together that are run by two different processes respectively at the same time competing for (some resources inside) the critical section (CS) is Peterson's algorithm.

Secondly, there is a fatal typo in the "important lines from the algorithm" with line numbers in the question. The second line

  2) turn = process ;

should be

  2) turn = other ;

Indeed, this line is the key to understand how Peterson's algorithm ensures mutual exclusion. Please note "the important lines from the algorithm" are executed sequentially at the same time by two processes, each considering itself as the "process" and the other process as "other" in those "important lines".  By executing this line, each process tries letting the other process to have a higher priority over itself to enter CS..

A minor typo in OP's question is "while (interested [other] == True" should be "while flag [other] == True".

Thirdly, OP asks which process is exactly currently executing. The answer is not just Process $i$. The answer is not just Process $j$. The answer is both processes. In fact, we can assume both process are executing at all times, each executing a different program. That is what we mean by concurrent processes or concurrent programming. Is it surprising? Please note, however, if the question is which process is exactly executing the program written at the start of OP's question, then, as I have said at first, the answer is Process $i$.

Fourthly, OP asks "which process are we blocking in while loop i.e stopping to enter CS?". Of course, the answer is the current process, that is, the process that is currently executing that line of code. It is the other process if you write the loop uniformly as "while (flag [other] == True && turn == process)", which can be either Process $i$ or $i$. It can only be Process $i$ if the loop is "while (flag[$j$] = true and turn = $j$)". It can only be Process $j$ if the while loop is "flag[$i$] = true and turn = $i$)".

Lastly, the "option b) flag[$j$] = true and turn = $j$" should be what $P$ stands for. Here "flag[$j$] = true" means process $j$, the other process, is interested in entering or staying in the critical section(CS) while "turn = $j$" say that the other process is either holding CS or, if other process is interested in entering CS, it has the priority over the current process to enter CS. Both conditions together imply the current process cannot enter CS. Once Process $j$ is not interested in CS by setting flag[$j$] to false, or once the value of variable "turn" is $i$, meaning Process $i$ has a higher priority over Process $j$ to enter CS, the "while (P)" loop is broken and Process $i$ is in CS. (I am avoiding to say "enter CS" here, just to emphasize the fact that there is no other code that enables or represents the act of entering CS. Process $i$ enters CS by breaking out of that while loop.)

All other options, (a), (c) and (d), are apparently wrong. For more detailed analysis, please check Peterson algorithm at Wikipedia.


What are some fundamental issues computer science tries to address? I was wondering, if physics has the origins of the universe or the nature of space, time, and matter, biology has the existence of the cell and the origin of life, are there mysteries that computer science could seek to unravel?

This question does not concern the theories and technologies developed by computer science, but more existential, ontological issues.

Computer science addresses the mystery of computation (but not computers): what is computable, what is not-computable, how difficult it is to solve certain problems, when are programs correct, how can programs be effectively written, what's the best way of solving problem X (for many Xs), ...


Is $DSPACE(f) \subseteq DTIME(f)$ always? Is $DSPACE(f) \subseteq DTIME(f)$ always?

For example, if we have a language $A\in DSPACE(log^2(n))$ can we say that $A\in P$ (and  subsequently in NP and coNP) since $DSPACE(log^2(n))\subseteq DSPACE(n^3) \subseteq DTIME(n^3)$?

I know about $ DTIME(f) \subseteq DSPACE(f) \subseteq DTIME(2^{O(f)})$ but $DTIME(2^{O(f)})$ is too big in this case.

We don't know that $\mathrm{DSPACE}[f(n)]\subseteq\mathrm{DTIME}[f(n)]$ is ever true and we suspect that it's never true.

A Turing machine that uses space $f(n)$ can run for $2^{O(f(n))}$ steps without getting stuck in an infinite loop, so it should be able to do much more than a Turing machine that can only run for $f(n)$ steps.  As you've observed, if $\mathrm{DSPACE}[f(n)]\subseteq\mathrm{DTIME}[f(n)]$, then $\mathrm{DSPACE}[f(n)]=\mathrm{DTIME}[f(n)]$ and we have no reason to think that would ever be true for reasonable functions.


Online set cover variant? Routing of requests We have a set of $k$ path requests from $src$ to $dst$ that arrive sequentially.

Each request may have multiple paths, but can choose only one of them. For example, in the Figure shown, there are two paths from $s1$ to $s4$ i.e., path1 : $s1-s2-s3-s4$ and path 2: $s1-s5-s6-s4$.

Further, each node on the path has an associated table that records entries. When a path is chosen, an entry may or may not be added to each node on the path. Whether an entry is added or not depends on the nature of the request, but that is not relevant here. Also, the node tables are independent of each other.

Each table has a limit on the number of entries. Suppose each table can hold a maximum of $n$ entries. When a table is full, that node cannot be chosen on any path. The blue boxes in the figure represent the percent full of each table. The node $s3$ is more utilised than the other nodes. If $s3$ becomes full, the path $s1-s2-s3-s4$ cannot be used to route any more requests.

Now, the challenge is to route the maximum number of requests, as they arrive sequentially. Here is what I have so far.

Heuristic 1: Choose the path with the least total new table entries added. Using this heuristic, however, can lead to non-uniform utilisation of the tables. Suppose that on the $s1-s2-s3-s4$ path, entries are added only at $s3$. And using the other path, entries are added at $s1$, $s5$, and $s6$. Heuristic 1 will choose path 1, but this may lead to faster fill-up of $s3$ and path1 cannot be used to route more requests.
Heuristic 2: Choose a cost function for each node based on a) cost to add new entry and b) percentage utilisation of table. Then choose the path with least total cost.

Let us define the cost metric as $ cost_{node} = cost_{new\;entry} + \frac{|existing\;entries|}{n}$

Using this heuristic, path 2 will be chosen, given the conditions stated above.

Now my question is two fold:

Is there a better way of going about this?
Given the two heuristics, how would I go about showing the competitive ratio?

Any help in this regard is appreciated.

Edited:
For the sake of simplicity, let us consider for each node on a candidate path, a new table entry is added with a probability $p_i$ and not added with probability $1-p_i$.

Note:

When a request arrives, and we get a set of candidate paths, we can know in $\mathcal{O}(1)$ time for each node in the path, whether it will have an entry added to its table or not. So in $\mathcal{O}(l)$ time we can know the number of  new table entries for a path, where $l$ is the length of the path.
We have global knowledge about the number of entries in a table of each node at every time instant.

In general, there are two approaches you can take here:

Empirical evaluation. Pick a realistic workload (a data set with a bunch of scenarios, where each scenario is a sequence of requests).  Use this as a benchmark.  Test each candidate heuristic on that benchmark, and see which one performs the best on this benchmark.

Theoretical analysis. Alternatively, you can try to prove a theorem about the competitive ratio of these two heuristics.  That may be very difficult.

I suspect it's going to be a lot more feasible -- and potentially more useful -- to take the former approach.  It does require you to have a dataset of representative requests.

I can suggest another plausible heuristic.  Given a graph, you can find use bottleneck shortest paths to find the best path from $s$ to $t$, where "best" is measured by the number of slots in the least empty node that's visited along that path.  The larger that number, the better (it means there exists a path with plenty of spare capacity).  So, one possible heuristic is to choose whichever path reduces this number the least.

There are probably many other heuristics you could come up with.  I suggest brainstorming a few, then evaluating them empirically using the approach listed above.


Intuitive proof for Floyd's cycle detection algorithm I am trying to understand Floyd's cycle detection algorithm. I can see why the algorithm works.

  When the Hare moves twice as fast as Tortoise, if there is cycle, they will meet definitely at some point in the cycle.

Is there any proof that proves the above point? I mean, without assuming that Hare and Tortoise meet at some point when Hare moves twice the speed of Tortoise and then proving.

In the wiki, I can understand the following paragraph.

  The key insight in the algorithm is that, for any integers $i ≥ μ$ and $k ≥ 0, x_i = x_{i + kλ}$, where λ is the length of the loop to be found and μ is the index of the first element of the cycle

But it is followed by the following point which I could not understand.

  in particular, $i = kλ ≥ μ$, if and only if $x_i = x_{2i}$. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ

How does the author come to conclusion that $i = kλ ≥ μ$, if and only if $x_i = x_{2i}$

Can somebody please help me in understanding this?

By definition, $x_0,\ldots,x_{\mu+\lambda-1}$ are all distinct, and for $i \geq \mu$, we have $x_{i+\lambda} = x_i$. Now let us prove the claim:

  Let $i \geq 1$. Then $x_i = x_{2i}$ if and only if $i \geq \mu$ and $i = k\lambda$ for some $k \geq 1$.

$\Longleftarrow$ Suppose that $i \geq \mu$ and $i = k\lambda$. Since $i \geq \mu$, we have $x_{i+t\lambda} = x_i$ for all $t \geq 0$. In particular, choosing $t := k$, we get $x_{2i} = x_{i+k\lambda} = x_i$.

$\Longrightarrow$ Suppose that $x_i = x_{2i}$. If $i < \mu$ then $x_j = x_i$ if and only if $j = i$. Since $2i \neq i$ (as $i \neq 0$), this contradicts the assumption $x_i = x_{2i}$, showing that $i \geq \mu$.

Since $i \geq \mu$, $x_i = x_{\mu + [(i-\mu) \bmod \lambda]}$. Similarly, $x_{2i} = x_{\mu + [(2i-\mu) \bmod \lambda]}$. Since $x_\mu,\ldots,x_{\mu+\lambda-1}$ are all distinct, it follows that $i-\mu \bmod \lambda = 2i-\mu \bmod \lambda$, and so $i$ is a multiple of $\lambda$.


Problems showing the constraint of master theorem case three holds Prove or disprove the following statements:

$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = \theta \left( {f\left( n \right)} \right) $ for all $ {\rm{ n = }}{{\rm{2}}^k}$
$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \Omega \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = O\left( {f\left( n \right)} \right)$ for all $ {\rm{ n = }}{{\rm{2}}^k}$

I think I should use the third case of the master theorem to check these equations.

But I have not been able to check this constraint for these inequations:

$\qquad af\left( {\frac{n}{b}} \right) \le cf\left( n \right)$

How do I do that?

The following shows that the second statement is false.

Define $f$ as follows:
$$ f(n) = \begin{cases} 4n^3 & n \text{ is a power of }4, \\ n^2 & \text{otherwise}. \end{cases} $$
Let $n = 2^{2k+1}$. Then $f(n) = n^2$ while
$$ T(n) \geq 2T(n/2) \geq 2f(n/2) = n^3. $$


How to solve an ILP problem with conditions in an objective function? I have came accross this link.

I have an integer linear programming (ILP) problem
$$\max_{(x_1, x_2,\ldots, x_n)}\sum_{i=1}^n x_i\cdot f(x_i),$$

$$\text{subject to }  \begin{cases}
..., &(1)\\
L≤x_i≤U,&(2)\\
x_i \in \mathbb{Z}, i \in I,&(3)\\
\end{cases}
$$
here $X=\{x_i \in \mathbb{Z}: L \le x_i \le U,  L<0, U>0, i\in I\}$ is the variable, $I=\{1,2, \ldots, n\}$ is the set of indicies, the function $f(x_i)$ is defined as $$f(x_i) = \begin{cases}
a_i \in A, &\text{if } x_i>0, \\
b_i, \in B, &\text{if } x_i<0.\\
\end{cases}
$$
$A=\{a_i \in \mathbb{R}^+: a_i<a_{i+1}, \forall i= 1, 2, \ldots, n-1\}$, $B=\{b_i \in \mathbb{R}^+: b_i<b_{i+1}, \forall i=1,2,\ldots, n-1\}$ are the input (ordered) constants, such that $b_i <  a_i, i \in I$. In the system of constraints mentioned above the Eq.(1) means some extra constraints.

As the result I'd like to have the optimal solution $X^*$ and corresponded values of the $n$ input constants $a_i$ and $b_i$, $i \in I$.

Question. How to solve an ILP problem with the function $f(\cdot)$ in the objective function?

Update 4.

I think, I can obtain the result with next steps:

1) make a precomputing of the input constants: $C=\{c_{ji}, i \in I, j \in J\}$ is the set of permutations of $a_i$ and $b_i$, $J=\{1,2,\dots, 2^n\}$.

Let's  $A=(2.2, 4.4, 6.6)$ and $B=(1.1, 3.3, 5.5)$ then
$$C=\left(%
\begin{array}{ccc}
        1.1 & 3.3 & 5.5 \\
        1.1 & 3.3 & 6.6 \\
        1.1 & 4.4 & 5.5 \\
        1.1 & 4.4 & 6.6\\
        2.2 & 3.3 & 5.5\\
        2.2 & 3.3 & 6.6\\
        2.2 & 4.4 & 5.5\\
        2.2 & 4.4 & 6.6\end{array}%
\right).$$

2) find the optimal solution $X^*_j$ of the $j$-th IPL problem from the set $$\max_{(x_1, x_2,\ldots, x_n)}\{\sum_{i=1}^n x_i\cdot c_{ji}, j \in J\},$$
and apply $f(\cdot)$ to each element of $X^*$. For instance,

$X^*=\left(%
\begin{array}{ccc}
        -1 & 3 & 2 \\
        1 & -3 & 3 \\
        1 & -4 & 2 \\
        -1 & 4 & 1\\
        -2 & 3 & 2\\
        -2 & 3 & 5\\
      2 & -4 & 1\\
        2 & 4 & 1\end{array}%
\right),$
$f(X^*)=\left(%
\begin{array}{ccc}
        1.1 & 4.4 & 6.6 \\
        2.2 & 3.3 & 6.6 \\
        2.2 & 3.3 & 6.6 \\
        1.1 & 4.4 & 6.6\\
        1.1 & 4.4 & 6.6\\
        1.1 & 4.4 & 6.6\\
        2.2 & 3.3 & 5.5\\
        2.2 & 4.4 & 6.6\end{array}%
\right).$

3) match the elements of $C$ and $f(X^*)$ by rows: $Res=if(C==f(X^*),1,0)$. In the example the $4$-th and $6$-th rows were matched only (denoted by 1's):

$$Res=\left(%
\begin{array}{ccc}
        0 & 0 & 0 \\
        0 & 0 & 0 \\
        0 & 0 & 0 \\
        1 & 1 & 1\\
        0 & 0 & 0\\
        0 & 0 & 0\\
        0 & 0 & 0\\
        1 & 1 & 1\end{array}%
\right),$$

4) select the maximum from the values of objective functions for the matched rows only:

$\max_{(x_1, x_2,\ldots, x_n)}\{\sum_{i=1}^n x_i\cdot c_{ji}, j =\{4,6\} \}=\max(-1\cdot 1.1 + 4 \cdot 4.4 + 1 \cdot 6.6, 2\cdot 2.2 + 4 \cdot 4.4 + 1 \cdot 6.6 )=\max(23.1, 28.6)=28.6$. Thus, the optimal solution of the intial ILP is: $X^*=(2,4,6)$ which corresponds to the input constants $(a_1, a_2, a_3)=(2.2,4.4,6.6)$.

The weak points are:

How to prove that you will have at least one matched pair on the step 3?
How to match elements $C$ and $f(X^*)$ if $f(X^*_{ij})=0$ on the step 2?

Introduce integer variables $x^+_i,x^-_i,y_i$, where each $y_i$ is 0 or 1.  The intended meaning of $y_i$ is that $y_i=1$ means $x_i$ is positive, $y_i=0$ means $x_i$ is zero or negative; and that $x^+_i$ captures the positive part of $x_i$ and $x^-_i$ captures the negative part.  We'll enforce that intention by adding the following constraints:

$$\begin{gather*}
x_i = x^+_i + x^-_i\\
0 \le x^+_i \le U \cdot y_i\\
L \cdot (1-y_i) \le x^-_i \le 0\\
0 \le y_i \le 1
\end{gather*}$$

This ensures that the $x_i,y_i,x^+_i,x^-_i$ are consistent.  Finally, note that

$$x_i \cdot f(x_i) = a_i x^+_i + b_i x^-_i,$$

so the objective function can be expressed as

$$\sum_i a_i x^+_i + b_i x^-_i,$$

which is a linear function of the variables.  Now maximize this objective function subject to the constraints above and any other constraints you might have, by feeding it to any ILP solver.

See Express boolean logic operations in zero-one integer linear programming (ILP) for other tricks of the trade.


Algorithm for dividing items into buckets while minimizing total weight Let's say I have two buckets coloured red and blue, both of which can hold two rocks. I need to divide a set of $n$ weighted rocks into these buckets in such a way as to minimize the total weight of the rocks in the buckets, while filling each bucket to its capacity.

An additional constraint is this: the rocks are themselves coloured red or blue, and can only be placed in a bucket of the corresponding colour. Moreover, the rocks can be coloured multiple different colours. In this case, the rock can be placed in any of the buckets with which it shares a colour.

For example, if our rocks are

$$\begin{array}{c|c|c|}
 & \text{Colours} & \text{Weight} \\ \hline
\text{Rock 1} & \text{Red, blue} & 1\\ \hline
\text{Rock 2} & \text{Red} & 2 \\ \hline
\text{Rock 3} & \text{Red} & 3 \\ \hline
\text{Rock 4} & \text{Blue} & 4 \\ \hline
\text{Rock 5} & \text{Blue} & 5 \\ \hline
\end{array}$$
then the optimal solution is
$$\begin{array}{c|c}
\text{Red Bucket} & \text{Blue Bucket} \\ \hline
\text{Rock 2} & \text{Rock 1} \\
\text{Rock 3} & \text{Rock 4}
\end{array}$$
as then the sum of the weights in the buckets is minimized.

One idea for an approximate algorithm as follows. First, sort the rocks in order of increasing weight. We make two passes of this list:

First pass: if the rock has only one colour, and if fewer than 2 rocks in the list so far have had that colour, then we can add that rock to the appropriate bucket. From the above example, we see that this step will place Rock 2 into the Red Bucket and Rock 4 into the Blue Bucket. (This step will never make an incorrect placement.)
Second pass (greedy): if the rock can fit into any of the buckets, put it there.

This algorithm does not generate the optimal solution for the above example, since on the second pass it will incorrectly place Rock 1 into the Red Bucket.

My question is this: does there exist a polynomial time algorithm to solve this problem optimally for $k$ buckets and $n$ rocks? If not, are there any polynomial time algorithms that generate approximate solutions (better than the one I've given here)?

I assume that in the $k$ bucket case, each rock has up to $k$ colors (buckets) associated with it, which are the ones it can be put into.

It seems to me that a polynomial time algorithm can be obtained by reduction to a minimum-cost flow problem, which can be solved in polynomial time. Create a network with $k + n + 1$ nodes: $n$ rock nodes, $k$ bucket nodes, and $1$ source node. The source node is adjacent to each of the rock nodes, with edge capacity 1 and edge cost equal to the weight of the rock. Each rock node is also adjacent to all the bucket nodes it can be put into, with edge capacity 1 and edge cost 0. The source node has a supply of $2k$ units, and each bucket node has a demand of 2 units. Any integer flow of value $2k$ corresponds to a feasible assignment of $2k$ rocks to the buckets. The minimum cost integer flow corresponds to an assignment of minimum weight.


How does this use of "apply" in Coq work? I'm working my way through software foundations. In the Chapter titled "Tactics", I'm able to prove this theorem in Coq:

Theorem silly_ex :
     (∀ n, evenb n = true → oddb (S n) = true) →
     oddb 3 = true →
     evenb 4 = true.
Proof.
  intros H1 H2. apply H2.
Qed.

Even though I was able to get through the example, I don't understand how that is a solution. After performing intros H1 H2 I'm left with proving that evenb 4 = true. The two hypotheses I have at this state are H1 : forall n : nat, evenb n = true -> oddb (S n) = true and H2 : oddb 3 = true.

How can apply H2 solve this? Even knowing that 3 is odd doesn't fulfill the antecedent of the conditional.

You can ask Coq to show you its proof object. Before Qed, type Show Proof.

(fun (_ : forall n : nat, evenb n = true -> oddb (S n) = true)
   (H2 : oddb 3 = true) => H2)

As you can see, H1 is not used at all, and the goal is H2.

It comes from the definition of oddb and evenb, the definition of negb and the definition of the natural numbers and the booleans.

Definition oddb (n:nat) : bool := negb (evenb n).

oddb 3 is equal to negb (evenb 3) by the definition of oddb above.
evenb 3 is equal to evenb (S (S (S O))) by the definition of 3. This is equal to evenb (S O) which is equal to false by the definition of evenb.
Therefore oddb 3 = negb false which is in turn equal to true by the definition of negb.
evenb 4 is equal to evenb (S (S (S (S O)))) by the definition of 4. Applying the definition of evenb three shows that this is equal to evenb (S (S O)), to evenb O, and to true.

All of these equalities come from computation: if $x$ reduces to $y$ then $x$ is equal to $y$ — this is the most basic form of equality¹. The reductions above use the $\beta$ rule (applying a lambda term to an argument), the $\delta$ rule (replacing a name by its definition) and the $\iota$ rule (applying a recursive function fix … and simplifying pattern matching).

Coq has a large set of tactics to perform computations, though they're only needed in advanced cases. For example, after intros H1 H2, you can ask it to expand evenb and oddb, but do nothing else.

cbv delta.
cbv delta in H2.

Integers like 3 and 4 are syntactic sugar, not named constants. 3 is S (S (S O)), not just some term that reduces to it. If you want to see everything that's going on, turn off pretty-printing of notations.

Unset Printing Notations.

(Use Set Printing Notations. to turn them back on.)

You can watch the goal being reduced to its value.

cbn iota. cbn beta. cbn iota. cbn beta. cbn iota. cbn beta. cbn iota. cbn beta. cbn iota.

Of course you don't need to guide Coq so much, this is just if you want to see all the steps. You can simply ask Coq to compute as much as possible. Just after intros H1 H2, run

compute. compute in H2.

and you'll see that both H2 and the goal simplify to true = true.

In this particular case there's no simpler way to go from H2 to the goal than to fully calculate both. If you continue the tutorial a bit, you'll get to recursive proofs, where it's very common to have similar hypotheses and a similar goal, but with a variable instead of constants like 3. There you would typically combine H1 and H2 together (but here H1 is not particularly interesting — since you're proving something about evenb, you'd want the an implication of the form oddb … -> evenb … rather than evenb … -> oddb …).

¹  In a certain sense, it's the only form of equality.