Extracting regex submatch boundaries without backtracking I'm attempting to develop from scratch a simple regex engine.  I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index  and ending at index ."
It makes sense to me how to accomplish this using recursive backtracking.
However, I'd like my implementation of the search to use Thompson's multi-state approach.  Is this feasible?

It occurred to me after I made this post that I could store the states in a linked list format:
typedef struct stateRecord {
    struct stateRecord *next;
    size_t state;
    size_t startIdx;
    size_t endIdx;
} stateRecord;


Generate random labeled tree with constrained edge lengths Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes in the linear arrangement of the tree. Let the length sequence $L$ of $T$ be the sorted sequence of lengths of all the edges in $T$.

An example tree is shown below. Each edge is marked with its length. The length sequence for this tree is $(1, 1, 1, 1, 2, 2, 3)$.

My question is: Given a length sequence $L$, is there an efficient algorithm to generate a labeled tree $T$ with length sequence $L$, randomly at uniform from the set of all such trees? Or failing that, to enumerate the set of trees with a given length sequence $L$?

To clarify, here is an extremely inefficient algorithm that does what I want. We have a desired length sequence $L$, let's say (1,1,1,1,2,2,3). To generate a random tree with the desired edge lengths:

Generate a random labeled tree $T$ on $n=8$ nodes by sampling a random Prüfer code.
Check if the length sequence of $T$ matches $L=(1,1,1,1,2,2,3)$. If yes, accept $T$. If not, goto 1.

This is very inefficient because there are $n^{n-2}$ possible trees generated in step 1, and only a very small number of those trees matches the desired $L$, especially as the trees get large.

Update: I have an algorithm that seems to work, but it seems like it could be made more efficient.

Algorithm:

Let $T$ be a graph with nodes $V$ and empty edge set $E$.
For each possible edge length $l$ in $\{1, \dots, \text{max}(L)\}$,
Let $k$ be the number of entries in $L$ matching $l$. So for example, if $L=(1,1,1,1,2,2,3)$ and $l=1$, then $k=4$.
If $k=0$, skip to the next $l$.
Generate the set of possible new edges $P = \{(u,v) : u \in V, v \in V, (u,v) \not\in E, u = v+l \text{ or } u = v-l\}$
If $P$ is empty, fail and start over again from 1.
Generate the set $Q$ of all combinations of size $k$ of elements of $P$
Randomly choose an element of $Q$, which is a set of $k$ edges. Add this set of edges to $E$.
If the resulting $T$ is not a forest, fail and start over again from 1. Otherwise, continue to the next $l$.

Basically, this generates the random graphs matching $L$, then filters them to be trees.

I'm not entirely sure of what you're asking for, but I think it might be one of these three:

Permutations that preserve topological structure
The tree you listed in parenthetical notation is (5 (2 (1 4) ) (3) (5 (6 (7 (8) ) ) ). Are you looking for permutations of this tree structure, because you can simply calculate all n! permutations of nodes and put them in the same tree structure:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )
(9 (8 (7 6) ) (5) (4 (3 (1 (2) ) ) )
(9 (8 (7 6) ) (5) (4 (1 (2 (3) ) ) )
(9 (8 (7 6) ) (5) (4 (1 (3 (2) ) ) )
...
(This would yield 362,880 distinct trees).

Note, this class of trees would preserve the sequences of lengths of the current tree. Now, if you have an array of these, simply use a good PRNG.

Permutations that calculate topological isomorphisms
It also would preserve topological properties, so if you want to generate other isomorphic topologies, then you can take the structure of the tree and do permutations on the sequences at the same level. Hence:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )
(9 (8 (7 6) ) (4 (3 (2 (1) ) ) (5) )
(9 (5) (8 (7 6) ) (4 (3 (2 (1) ) ) )
(9 (5) (4 (3 (2 (1) ) ) (8 (7 6) ) )
...
(This will be a variable number of permutations, in this case (3!(1!)(2!)(1!)) or 12 trees.)

Permutations that calculate equivalent lengths

Let your tree be [1 2[1 4] 3 4 *5[2 3 6] 6[7] 7[8] 8] where * represents root, and nodes inside of brackets are pointers. Notice it's possible to calculate lengths by taking the absolute value of the difference between nodes (2[4]->2[[2]] The node two which points to [node four] is a node that has an [[edge length 2]]). Then use [1 2[[1 2]] 3 4 *5[[3 2 1]] 6[[1]] 7[[1]] 8 9] -> {1, 1, 1, 1, 2, 3}. Now we can simply replicate this by traversing the original tree and constructing isomorphisms of length. Hence:

Determine root
Rnd(1-9)->3 -> [1 2 *3 4 5 6 7 8]
Permute first level by taking three lengths and finding candidates
[1 2 *3[[3 2 1]] 4 5 6 7 8 9]->  (note three lengths)
[3]±[[3]]->{0,6} (0 is invalid so don't push on the stack)
[3]±[[2]]->{1,5}
[3]±[[1]]->{2,4}
Note we need to select P(2,1) on all three sets iteratively.
So, randomly, one permutation is {6,1,4} :[1[] 2 *3[1 4 6] 4[] 5 6[] 7 8].
Call this recursively on [1], [4], [6] over the set {with [[1], [[1]], and [[1 2]] with the base case being any tree that satisfies {1, 1, 1, 1, 2, 3}.

Now, I think that preserving the lengths as a function of order of the sequence might yield a very small set, because certain trees, might only have a single isomorphism. Consider:

(1 (2 (3 (4 (5 (6 (7 (8)))))))) ~ (8 (7 (6 (5 (4 (3 (2 (1))))))))
{1 1 1 1 1 1 1} = {1 1 1 1 1 1 1}

There's only one isomophism because of the way a tree when considering edges whose lengths are caculated from sequences partitions. In fact, every tree done in this manner might have at most 1, but I'd have to think about how to prove that after implementing code.

Let me know what you think; if you can clarify what you're seeking, I might be able to help.


Is there an algorithm for converting Turing machines into equivalent Lambda expressions? We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I'm sure.

But is there an algorithm, a systematic way for us to convert a Turing machine into a Lambda Calculus expression? Is it impossible to have such algorithm? (meaning does it go down to undecidability or NP-Completeness?)
if not, are there any papers or algorithms for doing so?

All proofs of the equivalence of these two models of computation are constructive, that is they describe an algorithm for converting a program from one model of computation to the other. However, I caution you that these proofs are probably rather informal, and may not satisfy you. You may get luckier if you consult original work by computing pioneers (Turing, Church, Post, Kleene and their ilk).


Constructive version of decidability? Today at lunch, I brought up this issue with my colleagues, and to my surprise, Jeff E.'s argument that the problem is decidable did not convince them (here's a closely related post on mathoverflow). A problem statement that is easier to explain ("is P = NP?") is also decidable: either yes or no, and so one of the two TMs that always output those answers decides the problem. Formally, we can decide the set $S :=\{|\{P, NP\}|\}$: either the machine that outputs $1$ only for input $1$ and otherwise $0$ decides it, or the machine that does so for input $2$.

One of them boiled it down to basically this objection: if that's how weak the criterion of decidability is - which implies that every question which we can formalize as a language that we can show to be finite is decidable - then we should formalize a criterion that doesn't render any problem with finitely many possible answers that's formalizable in this way decidable. While the following is possibly a stronger criterion, I suggested that maybe this could be made precise by requiring that decidability should depend on being able to show a TM, basically proposing an intuitionist view of the matter (which I don't incline towards - nor do any of my colleagues, all of them accept the law of excluded middle).

Have people formalized and possibly studied a constructive theory of decidability?

I think the question you are trying to ask is "is computability theory constructive?". And this is an interesting question, as you may see by this discussion on the Foundations of Mathematics mailing list.

Unsurprisingly, it has been considered, since a lot of recursion theory was developed by people with constructive sensibilities and vice versa. See e.g. Besson's book and the venerable Introduction to Metamathematics. It's pretty clear that the first couple of chapters of recursion theory survive moving to a constructive setting with minimal changes: e.g. the s-n-m theorem, Rice's theorem or the Kleene recursion theorems survive unchanged.

After the first chapters though, things get a bit tougher. In particular, the higher levels of the arithmetic hierarchy are usually defined by a notion of truth. In particular, widely used theorems such as the Low Basis Theorem seem to be explicitly non-constructive.

Perhaps a more pragmatic response, though, is that these "paradoxically computable languages" are simply an idiosyncrasy, that can (and have!) been studied at great length, like non-measurable sets of reals, but that once the initial surprise has been overcome, one can move on to more interesting things.


Is this possible to solve satisfiability by using Quine McCluskey algorithm to simplify the whole given boolean formula by simplifying subformulas? In this question

Farewell Stack Exchange suggested to use karnaugh maps to solve the satisfiability problem by simplifying the entire/whole boolean formula by simplifying subformulas until you have reached a contradiction or the current boolean formula cannot be simplified anymore.

ratchet freak answered that this method doesn't work on all inputs.

I have new idea:

Instead of using karnaugh maps let's use Quine McCluskey algorithm to simplify the entire/whole boolean formula by simplifying subformulas and if you have reached a contradiction then return "unsatisfiable" as answer.

If the current boolean formula cannot be simplified anymore then return "satisfiable" as answer.

Does the new algorithm work?

If you're planning to apply this to each subformula with 16 variables:

No, that doesn't work for the same reason given in ratchet freak's answer.  As the Wikipedia article states, Quine McCluskey is functionally identical to Karnaugh maps, so your idea has the exact same problem.

If you're planning to apply this to the entire formula:

No, that doesn't work.  Quine McCluskey outputs a DNF formula or CNF formula.  That alone doesn't tell you whether the resulting formula is satisfiable or not.  You haven't said how to test whether there is a "contradiction"; testing for a "contradiction" is exactly the problem of testing satisfiability, so this hasn't gained you anything.

In any case, Quine McCluskey takes exponential time in the worst case.  Therefore, this approach is inefficient for formulas of any substantial size.  As far as asymptotic worst-case running time is concerned, you might as well just enumerate all possible assignments and see if any of them satisfy the algorithm -- that also takes exponential time.


How to reach data segment from global pointer in MIPS? The global pointer is initialized to 01x10008000. The data segment starts at 0x1000000.

I want to load the first word found in the data segment. So I place 0x8000 in the address field of lw.

lw $a0, 8000hex(\$gp)

Apparently 0x8000 in binary is 1000 0000 0000 0000 which is a negative number because the sign bit is 1.

This is the logic my professor provides so that we reach the start of the data segment by subtracting.

But if you convert all the other numbers to binary they also have 1 as the sign bit. So are they all negative?

As Yuval Filmus said, addresses are unsigned.


NP Complete Subset GCD Proof $SubsetGCD$ is described by the following:

instance: A set of positive integers $S$ and an integer $k$
question: does there exist a subset $S'$ of $S$ of size $k$ such that $GCD(S') = GCD(S)$

Prove that $SubsetGCD$ is np complete.

The hint for the problem is to reduce $VertexCover$ to $SubsetGCD$

I know what I'm supposed to do. Given an instance of $VertexCover$ convert it into the form of $SubsetGCD$ such that there exists a vertex cover of size $k$ if and only if there exists a subset $S'$ of size $k$ such that $GCD(S') = GCD(S)$

Since the vertex cover and subset are of size $k$ I feel like the vertices should correspond to the members of $S$ so that the vertex cover itself is the subset $S'$

Therefore, the important part is how to define the edges connecting the verticies. I've tried edges if the GCD of the endpoints is GCD(S), if the GCD of the endpoints is not GCD(S), edges connected to a vertex must be have GCD(S) and can't have a GCD greater than GCD(S) for all immediate neighbours etc.

I've also tried reducing Clique to the Subset GCD problem with no luck. Any help would really be appreciated!

Hint: Associate each edge $e$ with a prime $p_e$, and each vertex $v$ with a number $n_v \in S$. Choose $n_v$ so that the GCD of $\{n_v : v \in A\}$ encodes the set of edges covered by the vertices in $A$.

If you get stuck, try first showing that SubsetLCM is NP-complete. (LCM is Least Common Multiple.)


Language of words that begin and end with same symbol and have equal numbers of a's and b's I wish to find the CFG for a language on two symbols (say a and b) whose words begin and terminate with the same symbol, and have equal quantities of a's and b's.  What is the thought process I should use for finding such a grammar?  What is the most natural or simplest grammar for this language?  I hope you'll explain your answer. Hopefully this will suggest some patterns I should look for when trying to synthesise a grammar for a specified language.

Here's the best solution I could come up with on my own:

$ S \to aTbbTa \mid bTaaTb$

$ T \to abT \mid baT \mid aTb \mid bTa \mid \epsilon$

I think this grammar is correct.  Informal argument: I can see that if the word is $awa$ ($w$ being a substring), then there are at least two $b$'s in $w$ that are adjacent. This suggests the form $aTbbTa$ in the first production rule. (The argument holds if the roles of the two symbols are reversed). The second set of production rules is meant to generate every possible word of the language while keeping the number of $a'$s and $b'$s equal. Symmetry suggests that the rule $abT$ should be accompanied by the rule $baT$, and $aTb$ by $bTa$. Initially was wondering if any of the rules in the second set was redundant, but I don't think so - I can think of words that couldn't be formed if any of the second set of production rules was missing. Rather I need to be sure there aren't any words from the language that my grammar can't generate.

[I guess I would need induction to prove my grammar generates every possible word in the language. But right now I'm more interested in the thought process behind coming up with a grammar, and as far as I know, induction (in general) doesn't help much in synthesising a solution/rule/formula/etc.; it principally serves to verify a purported solution.]

Here is the thought process I would use.  I would notice that your language $L$ can be written as $L= L_1 \cap L_2$, where $L_1$ is the set of words that begin and end with the same symbol, and $L_2$ is the set of words that have equal quantities of a's and b's.

Then, I would note that $L_1$ is regular and so can be expressed by a simple DFA (with 5 states).  Also, I would note that $L_2$ is context-free and can be expressed by a simple CFG: e.g., $S \to \varepsilon \mid aSb \mid bSa \mid SS$.

Finally, I would recall the standard closure property: the intersection of a regular language and a context-free language is context-free.  It follows that $L_2$.  The proof of this standard closure property includes a construction that shows how to construct a CFG for $L_2$, given a DFA for $L_1$ and a CFG for $L_2$.  This gives a CFG for your language.  The resulting CFG will have $5^2=25$ non-terminals; some of them are unreachable and can be pruned, but the result is still quite messy.

The resulting CFG isn't the simplest or smallest CFG for your language.  Whether it is the most natural is open for debate.  But since you asked for the thought process behind coming up with a grammar, this illustrates one general technique for constructing CFG's: separate out the part that requires something more than finite state (equal quantities of a's and b's) from the part that can be handled with a finite-state automaton.


Learning a perceptron from stream data I want to train a Perceptron using stochastic gradient rulefrom the stream data. I have very limited amount of memory and i can store only $N$ examples.

Suppose my population consist of point as show in the following picture:

Now suppose my first $N$ examples come in following fashion and i can classify them correctly as show in the next picture:

Now the problem is if the next $N$ examples come in this way:

and i have classified them as shown. The problem is that since i can't train perceptron for previous $N$ examples(because i can store only $N$ examples and previous $N$ examples need to be thrown away) and training on next $N$ examples contradicts the hyper-plane for previous $N$ examples.

How to train a perceptron from stream data? Do i need to store all examples or there is an alternative way?

I think you're confusing yourself by worrying about a worst case that likely won't happen.  Assuming each element of the stream comes randomly and independently from some distribution, then it is exponentially unlikely that the case you mention happens.

How do you train from a stream?  Easy: each time you see an example, you update the weights of the neural network following the rules of gradient descent, then throw away that example.  In this way, the weights of the neural network change over time, and you don't need to store any past examples.  Over time, as you've seen enough examples, this should converge to a neural network that performs about as well as possible on the data, assuming that all of the data in the stream comes from the same distribution.


How many different heaps are there of a given shape? Let's say we have a tree like this:

Suppose we are given $N$ distinct elements, $N$ being the number of vertices in the tree (in this case, $N=13$).

  In how many ways can we distribute the given $N$ elements in the tree so that it has the max-heap property (any vertex is larger than its children)?

You can compute this recursively as follows. It will be convenient to denote (binary) trees using the following notation: a tree is either a leaf $\ast$ or is formed from two subtrees $(T_1,T_2)$. For a tree $T$, let $|T|$ denote the number of vertices in $T$, defined inductively by $|\ast|=1$ and $|(T_1,T_2)| = |T_1|+|T_2|+1$. Finally, let $N(T)$ denote the number of ways of allocating the integers $1,\ldots,|T|$ to $T$ so that the max-heap property is satisfied.

The base case is $N(\ast)=1$. Now consider a tree $T=(T_1,T_2)$. Clearly we must put $|T|$ at the root. Every filling out of the rest of the tree can be described as follows:

Choosing a set $S_1$ of integers as labels for $T_1$. The other elements $S_2$ function as labels for $T_2$.
Arranging $S_1$ in $T_1$ in a way satisfying the max-heap property.
Same for $S_2$ and $T_2$.

The number of ways of accomplishing the second bullet is $N(|T_1|)$, and the number of ways of accomplishing the third bullet is $N(|T_2|)$; in both cases, the exact contents of $S_1$ and $S_2$ are not important. The number of choices in the first bullet is $\binom{|T|-1}{|T_1|}$, and we conclude that $$ N((T_1,T_2)) = \binom{|T_1|+|T_2|}{|T_1|}N(T_1)N(T_2), $$
with initial case $N(\ast) = 1$.

Using this formula you can easily compute that for your tree the number of possibilities is $304128$ (I believe).

You can also "unroll" the formula:
$$
N(T) = \prod_{x=(x_1,x_2) \in T} \binom{|x_1|+|x_2|}{|x_1|},
$$
where $x$ goes over all internal nodes in $T$. For example, for your tree we get (top to bottom, left to right)
$$
\binom{12}{5} \binom{4}{3} \binom{6}{5} \binom{2}{1} \binom{4}{1} \binom{2}{1} = 304128.
$$


What's wrong with this problem (Inclusion-Exclusion principle) There are 120 students at University College taking the introductory
Java programming class. The students have access to the following
computers:

80 students have access to a PC running Microsoft's Windows operating system.
40 students have access to a computer running the Apple operating system.
10 students have access to a computer running the Linux operating system.
30 students have access to a computer running the Apple or Windows operating system.
7 students have access to a computer running the Windows or Linux operating system.
5 students have access to a computer running the Apple or Linux operating system.

How many have access to computers running all three operating systems?

The solution, using the Inclusion-Exclusion principle for 3 sets wikipedia link, is 32. However, how can it be 32 when the number of students who have access to Linux is only 10?

Let $A$, $B$, and $C$ be the set of pupils that have access to a PC running Windows, Apple, and Linux, respectively.

We know that
\begin{align*}
  |A \cup B \cup C| &= 120 \\
  |A| &= 80 \\
  |B| &= 40 \\
  |C| &= 10
\end{align*}

As @Tom van der Zanden pointed already pointed out in the comments, the wording of "... running the Apple or Windows operating system" is unclear. Thus I will cover all three interpretations of that wording.

Interpretation 1: "... running the Apple or Windows operating system" means the PC has installed both the Apple and Windows OS.

This means
\begin{align*}
  |A \cap B| &= 30 \\
  |A \cap C| &= 7 \\
  |B \cap C| &= 5
\end{align*}
Using inclusion-exclusion, we come to the result that
\begin{align*}
  |A \cap B \cap C| &= |A \cup B \cup C| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C|\\
  &= 120 - 80 - 40 - 10 + 30 + 7 + 5 \\
  &= 32
\end{align*}
So your calculation is correct and there is a contraction. That means that either

the inclusion-exclusion princliple does not hold in general, or
the exercise description is inconsitent, i.e. some of the cardinalities are wrong.

Since the inclusion-exclusion principle is proven to hold for any arbitrary set of sets, the latter case must be true.

Interpretation 2: "... running the Apple or Windows operating system" means that the PC runs either the Apple or the Windows OS.

We can calculate the cardinalities of the intersections $A \cap B$, $A \cap C$, and $B \cap C$. However, we also run into a contradiction by using this interpretation:

\begin{align*}
  & |(A \cup C) \setminus (A \cap C)| = |A \cup C| - |A \cap C| = |A| + |C| - 2|A \cap C| \\
\implies & |A \cap C| = \frac{|(A \cup C) \setminus (A \cap C)| - |A| - |C|}{-2} = \frac{7 - 80 - 10}{-2} = 41.5
\end{align*}
The above is a contradiction, since the cardinality of a finite set must be a natural number.

Interpretation 3: "... running the Apple or Windows operating system" is a regular logic or.

We have $|A| = 80 > 30 = |A \cup B|$. This is also a contradiction, since the cardinality of a set cannot be greater than the cardinality of its superset.

For either interpretation we show that there is a contradiction, therefore there must be a problem in the exercise description


Why analysis of Aloha protocol uses Poisson distribution? Pretty much in all of the analysis of the Aloha protocol that I read, it is assumed that the distribution of packet arrivals is Poisson. What is the rationale behind it? Isn't it actually binomial distribution that is approximated by Poisson because $n$ (number of users) is large and $p$ (transmission probability) is close to zero?

IMO, the biggest reason is that Poisson distribution is more tractable mathematically. Some experimental studies claim that it does follow Poisson. However, there are also other experimental studies show that it does not.

Mathematically, Poisson distribution can be viewed as the approximation of binomial distribution under certain conditions. However, it is not the rationale behind the Aloha protocol.

As a mathematical model, you should consider your own scenario carefully and decide whether to use it or not.


Go Back N ARQ Question I am a computer science under graduation student, and was going through some Go Back N ARQ (Computer Networking) videos on YouTube, and got a doubt in a question, which according to me should have a different answer than what the instructor on the video is arriving at (given that no other comment in the comments section of the video raises the same doubt, I am pretty sure I have had some problem in understanding the protocol). I would be greatful for any help. The question goes as follows:

Given a connection oriented communication between two hosts that are following the Go back N protocol, with sender's window = 3, and assuming that every 5th packet transmitted by the sender is lost (no acknowledgements are lost), what are the total number of transmissions required by the sender host? Assume that the packets to be sent are numbered 1-10.

The sequence of transmissions by the sender that I am getting is (final answer = 16):

1,2,3; 4,5,6; 5,6,7; 8,9,10; 8,9,10; 10

Meanwhile, the instructor in the video gets it like this (final answer = 18):

1,2,3,4,5,6,7,5,6,7,8,9,7,8,9,10,9,10

I would appreciate if someone could point out where I am going wrong in understanding the protocol.
Thanks!

1-2-3 is correctly sent and acknowledged so the sender's window is now over 4-5-6.

4 is received correctly and so it is acknowledged. This makes the window (currently over 4-5-6) slide to 5-6-7. However, since 5 was lost, 5 will not be acknowledged. Therefore, despite 6 being well received, 6 will not be acknowledged as well.  Meanwhile the sender sends 7 because his window allows him to (it looks like you think it doesn't trigger the sender to send 7). It is received well but the recipient doesn't acknowledge it because it's still waiting for 5 to arrive. The sender's timer goes off and therefore it sends 5-6-7 again... (etc).

If you haven't seen it already, this animation is really helpful.


Is it decidable whether a given Turing machine moves its head more than 481 cells away from the left-end marker, on input ε? So, while reading some problems on decidability, I came across the following resource:
https://www.isical.ac.in/~ansuman/flat2018/tm-more-undecidable.pdf

Here, on page no 12, it is written that the problem is decidable and with the following argument:

  "Yes, Simulate M on  for upto m^481 · 482 · k steps. If M visits the
  482nd cell, accept, else reject."

I am quite confused with the step count. Can anyone please explain what does this mean, or maybe point to some resources where I can find a proper explanation!!!!
Image of the slide

A run of a TM is a sequence of configurations, where each configuration states the contents of the tape (from the left marker, up until the point where it is blank all the way to the right), the location of the head, and the state.

An important feature of (deterministic) TMs is that you can uniquely continue a run from a given configuration. That is, a configuration has all the information you need to proceed.

In particular, if a configuration $c$ yields a runs that gets back to $c$, at some point, then the run is stuck in a loop (note that this is not a necessary condition, a run might not halt while never repeating a configuration!).

Now, consider all the possible configurations that use up to 481 cells. There is a finite amount of those, namely $m^{481} \cdot 482 \cdot k$ (where $m$ is the size of the alphabet, and $k$ is the number of states).

Thus, if you simulate the run for that many steps, then either at some point the machine goes beyond 481 cells, in which case you accept, or it doesn't, in which case you know for sure that a configuration must repeat (by the pigeonhole principle), so you can reject.


Doest sorting accept a dynamic programming solution? Are there any known / efficient dynamic programming solutions to sorting?

I understand of course that dynamic programming applies to scenarios where we have overlapping subproblems and optimal substructure, but I wonder if there are transformations and representations of the sorting problem where these conditions are met, and even better, where doing so may actually be useful.

Dynamic programming is an algorithmic technique, algorithms are classified as dynamic programming according to what their high-level structure "looks like", not according to a formal definition. If you really wanted to, you could force some sorting algorithms to fit into the dynamic-programming paradigm.

Let $A[1:n]$ be the array to sort, assume for simplicity that all its elements are distinct, and define $OPT[i]$ as the sorted array containing the smallest $i$ elements of $A$.

According to this definition $OPT[0]$ is the empty array and, if you solve the subproblems in increasing order of $i$, you can recombine them as follows:

$$\displaystyle \forall i=1,\dots,n  \quad\quad OPT[i] = OPT[i-1] \circ \min_{x \in A \setminus OPT[i-1]} x,$$

where $\circ$ denotes concatenation. The optimal solution is in $OPT[n]$. Computing any $OPT[i]$ requires $O(n)$ time, therefore the total time needed is $O(n^2)$. At any point in time, you only need to store one $OPT[i]$, so the space complexity is $O(n)$.

This is essentially an ugly way to describe selection sort.


Proof of $\mathsf{NP}^\mathsf{BPP} \subseteq \mathsf{BPP}^\mathsf{NP}$ How to show that $\mathbf{NP}^{BPP} \subseteq \mathbf{BPP}^{NP}$?

I tried to build $NTM$ $M_{NP1}$, which uses $PTM$ $M_{BPP1}$. Show that there will always be $PTM$ $M_{BPP2}$, which uses $L ($$NTM$ $M_{NP2}$$)$ as the oracle language and repeats the actions of $NTM$ $M_{NP1}$ with the oracle $L ($$PTM$ $M_{BPP1}$$)$. Unfortunately, I could not do this. It turns out that the $NTM$ output that uses $PTM$ will also happen with some probability?

Hope You can help me to show it.

Suppose that $M$ is a machine in $\mathsf{NP}^\mathsf{BPP}$ accepting some language $L$. We can think of $M$ as accepting an input $x$ and a witness $y$. The machine $M$ runs a polytime algorithm, and has oracle access to $\mathsf{BPP}$. We can further assume that the witness contains, for each oracle call to $\mathsf{BPP}$, both the input and the output — the witness might be longer, but it still has polynomial length. Denoting the pairs by $z_i,w_i$ and the $\mathsf{BPP}$ languages by $L_i$, we thus deduce that there is a polytime machine $A$ such that
$$
x \in L \Leftrightarrow \exists y,\vec{z},\vec{w},\vec{L} \; A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i L_i(z_i) = w_i,
$$
where the quantification is over polynomial length strings. (We elide the issue of how $L_i$ is represented.)

Suppose furthermore that $L_i$ is computed by some $\mathsf{BPP}$ machine $A_i$ with small error probability. We can think of $A_i$ as accepting two inputs: the actual input $z_i$, and a randomness string $r_i$.

This suggests the following $\mathsf{BPP}^\mathsf{NP}$ machine for $L$. The machine gets input $x$ and randomness string $\vec{r}$. Using a single oracle call to $\mathsf{NP}$, it checks whether there exist $y,\vec{z},\vec{w},\vec{L}$ such that
$$
A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i A_i(z_i,r_i) = w_i.
$$

If $x \in L$, let $y,\vec{z},\vec{w},\vec{L}$ the $M$-witness for it. For the vast majority of randomness strings $\vec{r}$, we will have
$$
A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i A_i(z_i,r_i) = w_i,
$$
and so our machine will accept $x$.

The other direction is a bit more subtle, and I'll let you work it out carefully. It requires the $\mathsf{BPP}$ machines to have really small error, which can be achieved via repetition.


The importance of the language semantics for code generation and frameworks for code generation in model-driven development I am implementing worflow where the code in industrial programming languages (JavaScript and Java) should be generated from the formal (formally verified) expressions (from ontologies as objects and rule formulas as behaviors). What is the best pratice for such code generation? Are some frameworks available for this?

In my opinion the semantics of the programming language is required. And I should be able to do the code generation in two steps: 1) translate my formal epxressions into semantic expressions of the target language; 2) translate semantic expressions into executable code. In reality I can not find any work that connects semantics of programming language with the code generation.

Is there special kind of semantics of programming languages that is usable not only for the analysis of the programs but also for the generation of the programs?

My guess is that it should be really useful approach for generating formally verified code but I can not find research work about this. Are there trends of better keywords avilable for this?

Maybe - more relevant question is - what kind of compilers/translators the Model Driven Development tools use for the generation of source code (platform dependent code) and how semantics of programming language can be used for the construction of such compilers?

Note added. There already is complete unifying (denotational and operational) semantics of Java, JavaScript and other industrial programmin languages in the K framework. So - this is more question about application of K framework for code generation is that is possible at all?

In general when we talk about code generation (or model-to-model transformation in general), clearly defined semantics is quite important, since such transformations usually make sense when both the source and the target model semantically match according to some criteria. For example, programmers might describe the behaviour of a program with a formal specification, which, according to the semantics, defines possible implementations in the target language (i.e. outputs of code generation). Failing to precisely define the semantics might lead to ambiguous or, in general invalid, transformations.

  Is there special kind of semantics of programming languages that is
  usable not only for the analysis of the programs but also for the
  generation of the programs?

In general, there is no need for a special kind of semantics for targeting generation of programs. However, different code generation systems target different domains of code generation and thus leverage different kinds of programming languages and their semantics. (Some overview of code generation in the context of program synthesis can be found in [1]).

There exists a body of work for which a programming language is coupled with language verification and program synthesis (described below). A seemingly well-fitting example of this is the Leon framework, which uses a subset of Scala as the main programming language, that expresses both programs and formal specifications. The framework allows not only verifying that the program matches the given specification (again, strictly defined by the semantics of the language and the interpretation of the logic used in the specification), but also generating code. In the latter case, programmers can only give formal specifications of the program in terms of its precondition and postcondition and the framework, it's code generation part (i.e. its synthesizer), generates the program that matches the given specification [2].

  My guess is that it should be really useful approach for generating
  formally verified code but I can not find research work about this.
  Are there trends of better keywords avilable for this?

One of the fields that seems to be closely matching what you described is software synthesis. Program synthesis is the task of automatically discovering an executable piece of code given user intent expressed using various forms of constraints such as input-output examples, demonstrations, natural language, etc [1].

  In reality I can not find any work that connects semantics of
  programming language with the code generation.

In general, the compiler for many general-purpose modern (high-level) languages perform some form of code generation that has to satisfy the rules of the language semantics (i.e. its language specification). E.g. the compiler for the Scala programming language emits Java bytecode---which can be thought of as a language which elements semantically closer match the instructions of the actual hardware---according to the Scala language specification.

  [About compiler and other tools for] Model Driven Development useful for
  code generation. What is the best pratice or framework for code
  generation?

Although, in my answer, I was focusing on the connection of the semantics of the programming language and code generation in the context of (general-purpose) program synthesis, these concepts are by all means applicable to other domains or practices such as Model-Driven Development. For general pointers on this direction, it might be useful to check out books that try to summarize them [4], [5].

  So - this is more question about application of K framework for code
  generation is that is possible at all?

Although, it might be the most suitable for your problem and intended use, there are other alternatives that might also work and perhaps could work for you as well, such as some of the transformation languages like Stratego or rewriting systems like Maude.

[1] Gulwani, Sumit. "Dimensions in program synthesis." In Proceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming, pp. 13-24. ACM, 2010.

[2] Kneuss, Etienne, Ivan Kuraj, Viktor Kuncak, and Philippe Suter. "Synthesis modulo recursive functions." Acm Sigplan Notices 48, no. 10 (2013): 407-426.

[3] Scala Language Specification

[4] Brambilla, Marco, Jordi Cabot, and Manuel Wimmer. "Model-driven software engineering in practice." Synthesis Lectures on Software Engineering 1, no. 1 (2012): 1-182.

[5] Milicev, Dragan. Model-driven development with executable UML. John Wiley & Sons, 2009.


How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t:

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

A simple path is a path without any repeated vertice, i.e. every vertice can be visited just one time. The length of the path is given from the edges of which it is composed.

So how can I show that LPATH is an NP-Complete problem using the Hamilton path problem as an NP-Hard problem as reference?

Welcome to the site! Let $G = (V, E)$ be a undirected graph.
If $G$ is Hamiltonian, then there exists a simple cycle $C$ in $G$ containing every vertex, i.e. the length of $C$ is $|V|$.
Note that if you delete any edge $vw$ from $C$, you end up with a path of length $|V| - 1$ between $v$ and $w$.
Conversely, if you find a simple path $P$ of length $|V| - 1$ between two vertices $v, w$ connected by an edge, you can add the edge $vw$ to $P$ to obtain a Hamiltonian cycle (as $P$ cannot contain $vw$ due to being a simple path).
Also observe that the choice of $v$ and $w$ is arbitrary as long as they are connected by an edge.

So we can obtain the following reduction:
Starting from some graph $G = (V, E)$, pick some edge $vw \in E$ and delete it to obtain a new graph $G' = (V, E \setminus \{vw\})$.
Using the observations we made, it follows that $G'$ has a path $P$ between $v$ and $w$ of length $|V| - 1$ if and only if adding $vw$ to $P$ yields a Hamiltonian cycle in the original graph $G$.
As $G'$ can be computed from $G$ in polynomial time, we have a polynomial reduction $\mathrm{Hamiltonian Cycle} \leq_\mathsf{P} \mathrm{Long Path}$, thus showing that your problem is $\mathsf{NP}$-hard (because $\mathrm{Hamiltonian Cycle}$ is $\mathsf{NP}$-hard already).

To show that $\mathrm{Long Path}$ is in $\mathsf{NP}$ we note that a path in a graph can be efficiently encoded as a list of its edges and checking that a string actually encodes a path in the graph and then counting the number of edges to determine whether it is long enough can be done in polynomial time.

Hence we find that $\mathrm{Long Path}$ is $\mathsf{NP}$-complete.


Overfitting in Machine Learning Algorithms I am new in the ML. I know that overfitting is memorizing the data while training. Like in Neural Network, if we make lots of layers and lots of hidden nodes, we can memorize all the data, but it can be bad because train data would not cover the whole space.

Like this, is there any way to overfit in SVM and Logistic Regression? Since they are linear algorithms, they cannot be something curvy, I guess, so I am guessing the answer would be no. But I am not sure.

Any help is appreciated.

Yes, they can overfit too.  Overfitting is especially a risk when the number of features is much larger than the number of samples in the training set.


2d cellular automata Wolfram binary codes This is a similar question to How 2d cellular automata rules works?
However, the answer there did not provide me what I am looking for. Specifically, I want to be able to render these 2d cellular automata forms: https://www.wolframscience.com/nks/p173--cellular-automata/
I cannot find any reference anywhere that explains how to change between a real number and a growth rule. In 1d, the situation is well documented, such as here: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html but in 2d the exact mapping of bits is nowhere to be found. I'd really like to make a program, so that I can for instance enter the number 465 and it will draw the pattern 465 from the Wolfram book. The other stack exchange answer I linked to above provides a possible binary mapping, however the method given there does not produce the same numbers as in the Wolfram reference. The binary value of 465 is 111010001 which does not help me at all. This particular shape is based on adding a cell when exactly one neighbor is currently occupied, so shouldn't we expect to have 4 1's in a row, one for each of the four neighbors? And to make this even more confusing, the last two digits seem to be swapped from the description given on the Wolfram page itself... It seems clear from the other Stack Overflow answer that there is not just one possible binary mapping but many, however given that there already exists a guide with pictures referenced by rule numbers I would really like to actually be able to use those specific rule numbers. Thanks.

The description given on the page you linked to is correct:

"In each case the base 2 digit sequence for the code number specifies the rule as follows. The last digit specifies what color the center cell should be if all its neighbors were white on the previous step, and it too was white. The second-to-last digit specifies what happens if all the neighbors are white, but the center cell itself is black. And each earlier digit then specifies what should happen if progressively more neighbors are black. (Compare page 60.)"

What you might be missing is that, if the rule number is odd, the empty lattice is unstable since white cells surrounded by other white cells will spontaneously turn black.  Specifically, any rules whose number is congruent to 1 modulo 4 (i.e. whose binary form ends in 01), like 465, are "strobing", i.e. the empty lattice will alternate between all white and all black in each successive generation.
In particular, this means that rule 465 cannot correspond to "adding a cell when exactly one neighbor is currently occupied".  (That would presumably be rule 686, or 1010101110 in binary.)
Instead, as you correctly note, 465 equals 111010001 in binary.  Written in five groups of two bits each, that gives 01 11 01 00 01.  In each of these groups the rightmost bit in group $k$ (numbered right-to-left from 0 to 4) is 1 if a white cell with $k$ black neighbors will turn black in the next generation, and the leftmost bit is 1 if a black cells with $k$ black neighbors will stay black.
This means that, under this rule, a white cell will turn black if it has 0, 2, 3 or 4 black neighbors (since the rightmost bit is 1 in groups 0, 2, 3 and 4 counting from the right) and a black cell will stay black if it has exactly 3 black neighbors (since the leftmost bit is 1 only in group 3).
And indeed, simulating this rule for 22 generations, starting from one black pixel on a white background, produces an image matching the one on the linked page.

Ps. It turns out that rule 465 is the "strobing equivalent" of the state-symmetric rule 558 = 010001011102, which differs from rule 686 by exactly one bit and can be described as "add a cell when exactly one neighbor is occupied, remove a cell when exactly one neighbor is empty".
Started from a single cell, it seems that rules 558 and 686 evolve identically, since from this starting point they apparently never generate a live cell with exactly three live neighbors.  Thus, on even-numbered generations, the strobing rule 465 also looks identical to both of them.


k-center problem: proof for Gon algorithm gives a 2-approximation The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following function: $\max_{v\in V}\min_{c\in C}d(v,c)$.
I am trying to understand the proof that the $Gon$ algorithm is a 2-approximation. The algorithm arbitrarily selects the initial center and loops for $k-1$ iterations, where at each iteration it adds the vertex which is furthest away from its nearest center as a new center.
The full proof that this algorithm gives a 2-approximation is described in Gonzalez, Clustering to minimize the maximum intercluster distance. The cost of the optimal solution is $OPT(V)$ and they describe the term "$(k+1)$-clique of weight $h$ for $V$":

Set $T$ is said to form a $(k+1)$-clique of weight $h$ if the cardinality of set $T$ is $k + 1$ and every pair of distinct elements in $T$ are at least $h$ units apart.

The part that I don't understand is the following lemma:

Lemma 2.1: If there is a $(k+1)$-clique of weight $h$ for $S$, then $OPT(V)\geq h$.

My question is, what is the proof for this lemma?

If $k+1$ vertices are at least $h$ units apart, then no ball of diameter $< h$ can cover two of these vertices, hence you would need at least $k+1$ balls.
Since you want to have at most $k$ balls, $h$ must be at least the minimum distance of the $k+1$ vertices (pairwise).
Another way of phrasing it would be:

If you have a set $T$ of $k+1$ points, and at most $k$ balls of diameter $h$, then at least one ball must contain two points.  Let $d$ be the shortest distance between two vertices in $T$ (the two closest vertices).  Then $h \geq d$.

Taking the contra-positive of the lemma:  If $\text{OPT} < h$, then you cannot have $k+1$ points that have pairwise distance $\geq h$, or in other words, if  $\text{OPT} < h$ then

Any set with pairwise distance at least $h$ has at most $k$ vertices
Any set with at least $k+1$ vertices has a pair with distance less than $h$.


Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation? We see that there is a sign, exponent, and mantissa part for the notation. But, there is no location for the significant bit.

Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation?

There are two tricks used here.

The first trick is to realise that any number can be expressed with a single whole digit and a fractional part by modifying the exponent.

eg:

  = 435.32 * 10^3
  = 43.532 * 10^4
  = 4.3532 * 10^5

  = 0.00453 * 10^1
  =  0.0453 * 10^0
  =   0.453 * 10^-1
  =    4.53 * 10^-2

The second trick is to notice that this single whole digit is never zero. So when the number is expressed in binary (0, 1) that digit must always be 1.

Therefore if we mandate that the number is stored in binary, and the exponent is always adjusted to express the number as a single whole digit and a fractional part, the whole digit can be optimised away as it never varies. This leaves just the sign, exponent, and fractional parts of the number to encode.

That being said (as pointed out in the comments), the IEEE754 standard does include "denormalised" numbers which as you might guess do not have a leading implied 1, but are instead lead by an implied 0.

These numbers have the smallest possible exponent making these values truly tiny. The point of presuming a zero here is to allow the storage of even smaller values than could have otherwise been expressed.

Essentially it is a compromise, by altering the rule for the smallest possible exponent a series of even smaller numbers with reducing precision can be stored. The cost for this is that numbers at the 2^smallest-exponent cannot be accurately stored.


Variants of the 3-Partition problem The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known that the 3SAT problem has a plenty of variants. Are there some variants of the 3-Partition problem discussed in the literature?

One variant of 3-partition is the following distinct 3-partition problem, shown to be NP-complete in [1].

Distinct 3-partition
Input: A set $X = \{a_1,a_2,\ldots,a_{3n}\}$ of positive distinct integers, and a positive integer $B$ where $\Sigma_{i=1}^{3n} a_i = nB$, and $B/4 < a_i < B/2$, where $i \in [3n]$.
Question: Is there a partition of $X$ into $n$ triples such that the elements in each triple sum to $B$?

The problem is also NP-complete when $B$ is bounded above by a polynomial in $n$. For an "application", a reduction from the problem is used in [2] to show a certain graph problem is hard.

[1] H. Hulett, T.G. Will, G.J. Woeginger, Multigraph realizations of degree sequences: Maximization is easy, minimization is hard, Operations Research Letters 36 (2008) 594–596.
[2] Bonato, Anthony, Jeannette Janssen, and Elham Roshanbin. "Burning a graph is hard." arXiv preprint arXiv:1511.06774 (2015).


MLP and backpropagation limitations? I have heard a colleague of mine giving the following statements to a student, but I am not quite sure if he is right. The statements were about Multi Layer Perceptron and the Backpropagation algorithm, he said that:

It would be reasonable to check it up if the data to be input to a MLP should be checked first its degree of data normality. It is the first time I heard that and I am not sure about it. I have seen this article:
https://www.researchgate.net/publication/256980936_Assumptions_of_Multiple_Regression_Correcting_Two_Misconceptions

that talks about multiple regression (and I know that a MLP NN can be used for this case) and it says that:

  In this article, we clarify that multiple regression models estimated using ordinary least squares require the assumption of normally distributed errors in order for trustworthy inferences, at least in small samples, but not the assumption of normally distributed response or predictor variables

So a MLP with BP algorithm does it only work when the input data if it has a normal distribution?

Another point that he mentions is that a MLP NN could not work in n-dimensions, but I am pretty sure that is not a limitation, because I have seen in the Andrew Ng course that he talks about data that is in Rn dimensions, and uses MLP and backpropagation to classify it.
So both limitations could exist? in which cases a MLP could fail, regarding the data input.

Thanks

No.  There seem to be multiple misconceptions here.

First, linear regression.  Linear regression assumes that the errors are normally distributed.  It doesn't require that the inputs be normally distributed, and normally they won't be.

Second, neural networks.  Neural networks certainly don't require that the inputs are normally distributed.  I'm not sure where your colleague is getting that from, but it's just not true.

Yes, neural networks work fine in higher dimensions.


Proving a language to be Recursively Enumerable? I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L is representing paths on the Cartesian plane which can begin and end at any point so say begin at (1,3) and end back at (1,3). My Question is, you would be able to represent a Turing Machine for this, right? Hence it would be Recursively Enumerable.

Your language is computable, and so in particular recursively enumerable. Given a path on the Cartesian plane, you can decide whether it goes back where it started: just follow the path and see where it ends. You can program a computer to do that. So it is decidable.


Are these two regular expressions equivalent? $u^*v(w \cup xu^*w)^*$ and $u^*v(w \cup x(u)^*w)^*$

Is that extra set of parentheses around the second $u$ needed?

First, an alternative notation (what I usually use, and it is my personal preference) to join two regular expressions is to use '+' instead of $\cup$ which is used to denote a union of two sets. So your regular expression can be written as
$$ u^*v(w + xu^*w)^* $$
or sometimes
$$ u^*v(w \mid xu^*w)^* $$
instead of
$$ u^*v(w \cup xu^*w)^* $$
That pair of parentheses around the second $u$ is redundant and so not needed since the Kleene star operator applies to only $u$ in $xu^*w$, i.e., $xu^*w$ and $x(u)^*w$ denote the same set.


Which one should I report as total network I/O bytes among Sum(InBound) or Sum(InBound + OutBound)? I have a set of experiments with distributed environments.

I am planning to present a total network I/O bytes usage of the system for each run.

Which one should I report as total network I/O bytes among Sum(InBound Traffic) or Sum(InBound Traffic + OutBound Traffic)?

For example, say there are two machines A and B in my cluster server.

A sends 10 bytes to B.

B sends 15 bytes to A.

What is the total network I/O bytes? Is it 25 or 50 bytes?

I would suggest reporting the sum of both.

As a general principle, the best solution is to define your metrics in the report or paper where you write up your results.  You should describe what you measured and how you measured it.  This includes clarifying whether "total network I/O" includes both inbound+outbound traffic or only inbound traffic.


Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$? I have encountered the following question in my homework assignment in Data Structures course:
"Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$ ?"
I think no such function $f$ exists, but I do not know how to prove it (or give a counter-example if one exists).

Counterexample: $f(n)=n!$ As $f(n)$ is $n$ times bigger  than $f(n-1)$, it is clear that $f(n-1) \neq \Theta(f(n))$.


Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$ I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on  $k$ into my proof.
generalTH(n_disks,k_stacks)
  if n<k:
    ### in 2n-1 moves reassemble ###
    return
  m = n-2
  generalTH(n-m,k)
  generalTH(m,k-1)
  generalTH(n-m,k)

To solve towers of Hanoi, I know it takes the following number of moves:
$$
T_k(n) =
\begin{cases}
2^n-1,  & k=3 \\
2n-1, & n<k \\
2T_k(n-m)+T_{k-1}(m), & n \geq k
\end{cases}
$$
Going through it - how can I show that the boundary case of $k=3$ can be within $\Theta(n)$?
Since $m = n-2$ : When I expand the recursion it seems easy to show that the first half is in $n$ - but I'm not sure how to show the boundary case will be in $n$?
$$T_k(n)=2T_k(n-(n-2))+T_{k-1}(n-2)=2T_k(2)+2T_{k-1}(n-2-(n-4))+T_{k-2}(n-4)$$
$$...$$
$$T_k(n)\approx\Theta(2\cdot\lfloor\frac{k}{2}\rfloor)+\Theta(\text{boundary case})$$

If $n\lt k$, we have $T_k(n)=2n-1$. Let us focus on the remaining case, i.e, assuming $n\ge k$.
One of the recurrence relations is,
$$\quad  T_k(n) =6+T_{k-1}(n-2)\ \ \text{for all }n\ge k\ge\frac {n+3}2\text{ and }n\ge3, $$
where $6$ comes from $2T_k(2)$, since $T_k(2)=3$.
Applying the recurrence relation above repeatedly, we have
$$\begin{align}
T_k(n)&=6\cdot 1+T_{k-1}(n-2\cdot1)\\
&=6\cdot 2+T_{k-1}(n-2\cdot2)\\
&=\cdots\\
&=6\cdot (p-1)+T_{k-(p-1)}(n-2\cdot (p-1))\\
&=6\cdot p+T_{k-p}(n-2\cdot p)\\
(\text{let us apply } T_k(n)=2n-1)\quad&=6\cdot p+2(n-2\cdot p)-1\\
\end{align}$$
if we can choose $p$ such that

$n-2(p-1)\ge k-(p-1)\ge\dfrac{n-2(p-1)+3}2$,
which ensures all equalities except the last one hold, and
$n-2p<k-p$,
which ensures the last equality holds.

Solving $p$ for those inequalities, we find that $p= n-k+1$.
$$T_k(n)=6\cdot p+2(n-2\cdot p)-1=4n-2k+1$$

So, we have
$$T_k(n) =\begin{cases}
  2n-1, & n<k \\
  4n-2k+1, & n \geq k
\end{cases}$$
It is easy to check that $n\le T_k(n)<4n$, so $T_k(n)=\Theta(n)$.

"How can I show that the boundary case of $k=3$ can be within $\Theta(n)$?"
What is the situation when $k=3$ under the assumption $k\ge\dfrac{n+3}2$? That means $n\le3$. So that situation is rather irrelevant since we are interested in the asymptotic behavior of $T_k(n)$.


How is the key in a private key encryption protocol exchanged? Windows NT used a point-to-point protocol where a client can communicate "securely" with a server by using a stream cipher to encrypt an array of messages with some key $k$. The server also encrypts its response with the same key $k$. But how is it aware of this key?

More general: if Alice and Bob use some encryption/decryption algorithm that operates on the same private key $k$, what is a secure way of exchanging this key? (without using a different key ofcourse)

This is something that I've always asked myself whilest studying private key cryptography.

Whenever Alice and Bob wants to agree on a same private key, the most popular method is to use Diffie-Hellman. It works as follows:

Two public values are first chosen lets say $n=13$ and $g=17$.
(These are usually very large prime numbers and known to everyone
using that protocol).
Alice chooses a Private Value $a = 3$ and Bob chooses a Private
Value $b = 7$. These are private to themselves.
Alice computes: $A = g^a\mod n$ and Bob computes: $B = g^b\mod n$,
in this case $A = 12$ and $B = 4$ and they exchange each others
values (may be through chat), i.e. everybody knows the values of $A$
and $B$.
Alice computes: $K = B^a \mod n$ and Bob computes: $K = A^b\mod n$, in this case $K = 12$.

Now Alice and Bob have both agreed upon the value $K$ as their key. Note that since the value $n$ and $g$ and very large prime numbers it is almost impossible for a eavesdropper to factorize them and compute the key himself.

A problem in private key cryptography is man-in-the-middle attack and that is one of the main reasons to choose public key cryptography over private key cryptography.


Reduce Vertex cover to SAT I need to reduce the vertex cover problem to a SAT problem, or rather tell whether a vertex cover of size k exists for a given graph, after solving with a SAT solver. I know how to reduce a 3-SAT problem to vertex cover problem, by constructing the subgraphs for each variable (x, !x) and for each clause (a triable). But I am not getting,how to do other way round?

I was thinking of first forming a DNF ,with electing k vertices at first and then convert it to a CNF, by enumerating all clauses. Is there any other method?

Let's introduce a variable $x_i$ for every node $i$, representing the condition that the node is part of the vertex cover. Then for every edge $\{v,w\}$ we introduce the clause $x_v \lor x_w$.

We have the additional condition $x_1  + x_2 + \ldots \ +\ x_n \leq k$. We can combine an addition circuit  to compute the bits of the sum with a comparator circuit to enforce the inequality. The CNF of the resulting circuit has only polynomially many clauses.


Time Complexity of a selection problem I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem.

[Assuming operations on integers take $O(1)$ time]

We are Given $m$ sets, with $n$ integer numbers each. We want to select exactly one integer from each set, to make a set S, such that $~ l = \max(S) - \min(S)~$ is minimized.

For example, n = 4, m = 3:

$S_1 = \{1, 43, 71, 101\}$

$S_2 = \{18, 53, 80, 107\}$

$S_3 = \{3, 16, 51, 208\}$

Now

$~S = \{43, 53, 51\}$

has one number from each set and

$~l = \max(S) - \min(S) = 53 - 43 = 10 ~$

wich is the minimum possible value of $l$ (I think).

First thing I tried was a reduction to the set cover problem, but I wasn't able to find one.

If you are trying to prove $NP$-Hardness of that problem, you need a reduction from (not to).

Anyway, I don't think this is $NP$-hard (unless $P = NP$, of course)

Suppose the $S_i$ are sorted.

Suppose you decide that element $x \in S_j$ will be minimum. Now in each other set, you can find the smallest element greater (or equal to) $x$ using binary search, and take the maximum among those.

Do this for each of the $mn$ numbers, assuming it is the minimum. Pick the best set you get. This gives you a polynomial time algorithm: $m \log n$ time for each of the $mn$ elements, giving an $O(m^2n \log n)$ time algorithm.


Improvement of algorithm due to constrained graph This algorithm runs natively in O(V * E^2).

The description states that

  The running time of O(V * E^2) is found by showing that each augmenting path can be found in O(E) time, that every time at least one of the E edges becomes saturated (an edge which has the maximum possible flow), [...]

My graph has the property that at there are exactly |V| edges with a limited capacity, that is, all remaining |E|-|V| edges have an unlimited capacity; any amount of flow can pass through them.

Given that those edges with an unlimited capacity can never become saturated, can I safely assume that a maximum of |V| augmenting paths will be found, and therefore the complexity reduced to O(V * E)?

If so, is there an adequat proof for the assumption made in the Wiki article? It only states There is an accessible proof in Introduction to Algorithms.

Edmonds-Karp algorithm works by building successive flows $f_0, \dots, f_n$ where each flow $f_{i+1}$ can be obtained by combining $f_i$ and a path in the "residual graph" $G_{f_i}$ obtained through a BFS (the residual graph is just the original graph where we removed full edges).

Now, the idea of the proof in Introduction to Algorithms is to introduce a distance $\delta_f(s,v)$ from the source node $s$ to all nodes $v\in V$ in the graph $G_f$. Then they prove 4 things:

$\delta_{f_i}(s,v)$ can only increase with $i$ (i.e. $\delta_{f_i}(s,v)\leq \delta_{f_{i+1}}(s,v)$) that is their lemma 26.7;
if an edge $(u,v)$ is not saturated by a flow $f_i$ (i.e. $(u,v)$ is not saturated in $f_{i-1}$ but is in $f_i$) and then unsaturated in the flow $f_j$ with $j>i$ then $\delta_{f_j}(s,v)-\delta_{f_i}(s,v)\geq 2$. That means an edge can become saturated at most $1+|V|/2$ times (since $\delta_{f}(s,v)\leq|V|$);
at each BFS, an edge become saturated.

By combining these, we have that each edge can be saturated at most |V|/2+1 times ($\delta_{f}(s,v)\leq |V|$) and that the Edmonds-Karp algorithm is in $O(E×(E×V))$ where $O(E)$ is the time taken for one BFS and $O(E×V)$ the number of BFS (i.e. the maximum number of times an edge can become saturated).

For you the complexity is O(K×V×E) : finding a path is in $O(E)$ and you might have to find $(|V|/2+1)×K$ times an augmenting path where $K$ is the number of edges that can become saturated (i.e. $K=V$ for you thus $O(E×V^2)$).


A grammar for my context free language {xy | x, y ∈ {a, b} ∗ , |x| =|y| , x != y} This question is given as an exercise to me . I took a look at the solution given by  the instructor which is not the same as my solution .

So I thought it would be wise to ask it here  considering I am a newbie on that topic.

My solution basically is as follow :

S -> aSa | bSb | aTb | bTa

T->   aTa | bTb | aTb | bTa | e

My apporach to the problem is as follows :
If I don't find  any differences (if both characters are the same)  , continue with S until you find  make a difference then you can do whatever you want with the string as long as you obey the rule of x having the same lenght .

There can be multiple grammars for one language, all equally valid.

We generally don't check solutions to exercises here.  The way to tell for yourself whether your answer is correct is to prove it correct: see How to show that L = L(G)? for techniques on how to do that.


What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph? Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently:

$IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise $F$
$ConnectedNodes(N)$ - returns the set of nodes which are reachable from $N$

This is easily done by pre-computing the connected components of the graph. Both queries can run in $O(1)$ time.

If I also need to be able to add edges arbitrarily - $AddEdge(N_1, N_2)$ - then I can store the components in a disjoint-set data structure. Whenever an edge is added, if it connects two nodes in different components, I would merge those components. This adds $O(1)$ cost to $AddEdge$ and $O(InverseAckermann(|Nodes|))$ cost to $IsConnected$ and $ConnectedNodes$ (which might as well be $O(1)$).

If I also need to be able to remove edges arbitrarily, what is the best data structure to handle this situation? Is one known? To summarize, it should support the following operations efficiently:

$IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise $F$.
$ConnectedNodes(N)$ - returns the set of nodes which are reachable from $N$.
$AddEdge(N_1, N_2)$ - adds an edge between two nodes. Note that $N_1$, $N_2$ or both might not have existed before.
$RemoveEdge(N_1, N_2)$ - removes an existing edge between two nodes.

(I am interested in this from the perspective of game development - this problem seems to occur in quite a few situations. Maybe the player can build power lines and we need to know whether a generator is connected to a building. Maybe the player can lock and unlock doors, and we need to know whether an enemy can reach the player. But it's a very general problem, so I've phrased it as such)

This problem is known as dynamic connectivity and it is an active area of research in the theoretical computer science community. Still some important problems are still open here.

To get the terminology clear, you ask for fully-dynamic connectivity  since you want to add and delete edges. There is a result of Holm, de Lichtenberg and Thorup (J.ACM 2001) that achieves $O(\log^2 n)$ update time and $O(\log n / \log\log n)$ query time. From my understanding it seems to be implementable. Simply speaking the data structure maintains a hierarchy of spanning trees - and dynamic connectivity in trees is easier to cover. I can recommend Erik D. Demaine's notes for a good explanation see here for a video. Erik's note also contain pointers to other relevant results. As a note: all these results are theoretical results.

These data structures might not provide ConnectedNodes queries per se, but its easy to achieve this. Just maintain as an additional data structure the graph (say as doubly connected edge list) and the do the depth-first-search to get the nodes that can be reached from a certain node.


Are there practical methods for solving ILP? Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms!
Is solving an ILP easy and fast in practice? Is this solution exact or approximate?

Some ILPs can be solved rapidly (to an exact solution) in practice; some cannot.  Usually when we are talking about solving an ILP, we are looking for an exact solution, though some ILP solvers can find an approximate solution as well (find the best solution they can within the time constraints).  There are no hard-and-fast rules.

Of course, ILP is NP-hard, so you should not expect any ILP solver to be able to efficiently solve all ILP instances.  Rather, what seems to happen in practice is that some instances can be solved in a reasonable amount of time, but others appear to be very hard.  However, ILP solvers incorporate many sophisticated techniques for speeding up the solver, and these are sometimes effective.  There's no good way to know for sure in advance whether your specific instance will be solvable efficiently or not, but to try it.

Why is it useful to reduce some other problem to ILP? That's not always useful or interesting... but in some cases it is.  For example, it lets you take advantage of the sophisticated methods already implemented in ILP solvers, without having to re-invent them in the context of your other problem.


Constructing Context Free Grammar I am stuck and having a hard time with this question. I want to construct a CFG for the language $$L = \{{a^lb^mc^n | l,m\in N, n=|l-m|\}}$$
I know that the language consists of strings where:
1. number of a's = number of b's, so c=0
2. number of a's more than number of b's, c=l-m
3. number of a's less than number of b's, c=-(l-m)

I started with
$$S->ab$$
$$S->aSb$$
This generates all of case one, where number of a's = number of b's and c=0. I know that I could increment a's and c's by having aSc but I cant put that in the second line because it could generate a(aSc)b which is not in the language.

Hint: try to do each language separately, and then your final grammar is S->S1|S2|S3.

To do your case 2, you can write

$S->aSc|X$

$X->aXb|\epsilon$.

I.e. you start by generating the c's and the exceeding a's, and then you generate the b's and the remaining a.


What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets? What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?

What is both the time and space complexity of the naive algorithm that does this computation?

An inefficient recursive algorithm to do this task is:

Where

This results in Θ(2n) exponential blow up time complexity and this is incredibly bad!

Another iterative algorithm to compute the cardinality is:

This formula was taken from this proof wiki webpage, although it doesn't show any proof, but only the formula itself.

But I don't know how to analysis it's both time and space complexity.

EDIT: It appears that the iterative algorithm, unlike the recursive algorithm, iterates over all the different subsets of {S1, ... , Sn} in order to compute the cardinality of the union of all sets from S1 to Sn, but the number of subsets of {S1, ... , Sn} is 2n, so the time complexity of the iterative algorithm is same as the time complexity of the recursive algorithm, i.e. the time complexity of the iterative algorithm is also Θ(2n) exponential time blow up as the time complexity of the recursive algorithm.

Does exist polynomial both time and space algorithm to compute this?

I tried to google an answer to this question for hours, but I didn't find it anywhere.

Yes, there is a polynomial time algorithm.  You simply iterate over all of the elements of each set and add each one to some data structure (e.g., a hashtable, a balanced binary tree) if it's not already present.  Then, you count the number of items in that data structure.

If there are $n$ input sets $S_1,\dots,S_n$, each of size $k$, then the running time of this is $O(nk \log(nk))$ if you use a self-balancing binary tree data structure.  The expected running time is $O(nk)$ if you use a hash table.  The size of the input is $\Theta(nk)$, so this yields an algorithm whose running time is polynomial in the size of the input.


How was the σ function chosen to extend the perceptron? I am just reading about perceptrons in more depth, and now onto Sigmoid Neurons.
Some quotes:

A small change in the weights or bias of any single perceptron in the network can sometimes cause the output of that perceptron to completely flip, say from 0 to 1..... That makes it difficult to see how to gradually modify the weights and biases so that the network gets closer to the desired behaviour. Perhaps there's some clever way of getting around this problem. But it's not immediately obvious how we can get a network of perceptrons to learn. We can overcome this problem by introducing a new type of artificial neuron called a sigmoid neuron. Sigmoid neurons are similar to perceptrons, but modified so that small changes in their weights and bias cause only a small change in their output. That's the crucial fact which will allow a network of sigmoid neurons to learn.
Just like a perceptron, the sigmoid neuron has weights for each input, $w1,w2,…$, and an overall bias, b. But the output is not 0 or 1. Instead, it's $σ(w⋅x+b)$, where σ is called the sigmoid function and is defined by: $σ(z)≡\frac{1}{1+e^{−z}}$.
If σ had in fact been a step function, then the sigmoid neuron would be a perceptron, since the output would be 1 or 0 depending on whether w⋅x+b was positive or negative. By using the actual σ function we get, as already implied above, a smoothed out perceptron. The smoothness of σ means that small changes Δwj in the weights and Δb in the bias will produce a small change Δoutput in the output from the neuron. In fact, calculus tells us that Δoutput is well approximated by:
$$Δoutput≈∑_j\frac{∂output}{∂w_j}Δw_j+\frac{∂output}{∂b}Δb$$
Don't panic if you're not comfortable with partial derivatives!
Δoutput is a linear function of the changes $Δw_j$ and $Δb$ in the weights and bias.  This linearity makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output. So while sigmoid neurons have much of the same qualitative behaviour as perceptrons, they make it much easier to figure out how changing the weights and biases will change the output.
In fact, later in the book we will occasionally consider neurons where the output is f(w⋅x+b) for some other activation function f(⋅). The main thing that changes when we use a different activation function is that the particular values for the partial derivatives in Equation (5) change. It turns out that when we compute those partial derivatives later, using σ will simplify the algebra, simply because exponentials have lovely properties when differentiated. In any case, σ is commonly-used in work on neural nets, and is the activation function we'll use most often in this book. [END]

The first part of my question is, how did they know to pick this "sigmoid shaped" function/equation in the first place? How did they know to pick this one over every other curved or not-curved function? Is that just standard practice for these types of problems in Math class? If I were to try and explain why the sigmoid function was chosen, I would say "because it means you can make small changes to the input correspond to small changes to the output." But how? I don't follow the partial derivative math and don't have a background in partial derivatives (and neither does my audience). Knowing why and how th esigma function was chosen would help demystify why neural networks work.
Unfortunately the partial derivatives weren't explained (maybe they will be somewhere else).
The second part of my question is, How is $Δoutput$ a "linear function"? Why not just a flat slope instead of the sigmoid shape. Why does it have to be so fancy? How does "using σ will simplify the algebra"? Where can I find research papers on the original thinking behind this, or if you know the answer then how can you explain why using sigma will simplify the algebra? This seems like an important part of the explanation on why we are using sigma functions in the first place, so having a laymans explanation would really help.

Answer to first part
The function in the question is called the logistic function. Sometimes it is also called "the" sigmoid function, but some authors use sigmoid to just mean any s-shaped function.
There are a wide variety of activation functions used in practice in neural networks, sigmoid and otherwise. The logistic function is one of the more common ones, because both the logistic function and its derivative are defined for all real inputs, can be written as short expressions in terms of elementary functions, and can be computed efficiently using standard library functions in most programming languages. (This is unlike the step function used as the activation function for a classic perceptron—the derivative of the step function is undefined at the discontinuity.) Another widely-used activation function that has these properties is $\tanh$. There is really no strong reason to prefer one over the other when initially presenting sigmoid neurons. You can pretty much pick any function you learn how to differentiate in a Calculus 1 class and that has a sigmoid shape with asymptotes at $\pm\infty$. They have slightly different performance characteristics in training, but that is not very relevant for an initial explanation.
It is unfortunately very difficult to explain backpropagation without understanding partial derivatives, since backpropagation is literally just gradient descent where the gradient is computed by automatic differentiation. I would recommend watching 3Blue1Brown's excellent series of YouTube videos on how backpropagation works: part 1, part 2, and especially part 3 and part 4.
You mention an audience in the question. If you are going to be presenting this material, I would seriously consider referring your audience to the 4 videos linked above, at least as references. They certainly provide a better explanation than I could give in a lecture.
Answer to second part
The reason for not using a linear function is that a neural network with all linear activation functions is a linear combination of linear functions, and is therefore itself a linear function. So using a linear activation function misses the entire point of training a neural network; you could get the same result faster by doing a least-squares fit of a linear function to the data.
To oversimplify only slightly: a neural network with a linear activation function is just the "fit trendline" feature in Excel.
By contrast, there is a universal approximation theorem that says that, for sufficiently nice nonlinear activation functions, any function can be approximated well by using enough neurons.
The universal approximation theorem was not discovered for many years after when neural networks were first invented, so it was not a motivating factor in their invention. Early neural network research was mainly inspired by biological neurons (the kind in your brain) and control theory.
While the universal approximation theorem says that a sufficently large neural network has the potential to approximate any function well, the actual reason why the standard method of training neural networks (stochastic gradient descent backpropagation) performs so well in practice is still poorly understood and an active area of research.


What is the exact definition of a dictionary in the concept of linear algebra and computer science? I am reading this paper for my master thesis and trying to understand every concept in it. The following sentence confuses me as to what is the exact definition of a dictionary in this concept except for the fact that it holds the atoms as its columns?

  Recall we refer to the columns of the matrix $A$ as atoms that are later used as building blocks in the construction of $b$. Such a matrix that holds the atoms as its columnsis referred to as a dictionary[...].

Yes, as it says, a "dictionary" is just the word they're using for a matrix with entries of a particular type that's used for a particular purpose. They're drfining the term "dictionary" in the text you quote.


Enumerate partitions of a set with blocks of equal size Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$?

In The art of computer programming (Fascicle 3B) by Knuth, there's a mention of an algorithm by Ruskey that can list all partitions with $c$ blocks. I could just use this algorithm and discard all partitions that violate the constraint on the  equal size of blocks, but I would visit many useless partitions.

Is there a better way?

Section 5.10 of Ruskey's book Combinatorial Generation gives a combinatorial Grey code for linear extensions of posets and describes a bijection between set partitions of a chosen shape and linear extensions of a corresponding poset.

  Partitions of Given Type

  Let $P(n_0, n_1, \ldots, n_t)$ be the set of partitions of the set $\{1, 2, \ldots, n\}$ into blocks of sizes $n_0, n_1, \ldots, n_t$, where $n = n_0 + n_1 + \cdots + n_t$. For example, the partition $\{\{2, 8\}, \{3, 5\}, \{6, 12\}, \{1, 10, 11\}, \{4, 7, 9\}\}$ is in $P(2, 2, 2, 3, 3)$. We have listed the elements in order and the blocks of equal size by the magnitude of their smallest element. The problem of generating the elements of $P$ can be reduced to that of generating the linear extensions of a certain forest poset. The cover relations of the poset consist of chains of sizes $n_i$ together with chains of the maximal elements of the previous chains which have equal values of $n_i$. The linear extension corresponding to our example is $7, 1, 3, 10, 4, 5, 11, 2, 12, 8, 9, 6$. The inverse of this permutation is $2, 8, 3, 5, 6, 12, 1, 10, 11, 4, 7, 9$, which is just our original partition but without the curly braces.

  To be a little more precise, assume that the $n_i$ are listed such that $n_0 \le n_1 \le \cdots \le n_t$, and let $s_i = \sum_{j=1}^{i-1} n_i$. The cover relations of the poset are indicated by the $t + 1$ chains $C_i = s_i + 1, s_i + 2, \ldots, s_i + n_i$ and $D_i = s_i + 1, s_{i+1} + 1, \ldots, s_j + 1$, where $n_{i−1} < n_i = n_{i+1} = \ldots = n_j < n_{j+1}$.

The algorithm per se is described in Pruesse and Ruskey, Generating linear extensions fast, SIAM Journal on Computing 23.2 (1994): 373-386.


Convert NURBS curve into Cubic Bezier Curve From this:

  Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials.

I don't understand what it means, and don't yet know if it really means that there is absolutely no way to convert a NURBS curve into a cubic bezier curve (or spline, since I think bezier splines are multiple bezier curves connected together). I get confused because I also read this:

  No matter it is Uniform or Non-uniform, NURBS is just made by one or a bunch of Bezier curve; and if you bear with me, what you need to know about NURBS math is just the Bezier-series-equations.

Even just saw this:

  NURBS curve can always be converted to piecewise Bézier by repeated knot-insertion.

So some say it's possible, others not.

If it is true that you can't model NURBS with Bezier curves, then I would like to know why rational functions and polynomials can't be morphed into one another, at least at a high level (what is preventing the transformation between the two). In that case I would also like to know if there is a way to approximate a NURBS curve with Bezier curves, even though you lose some precision or the curve changes slightly. I would then just like to know how much you lose when approximating a NURBS curve with a Bezier curve, and what the algorithm or technique is called so I can further explore how to do it. If there is a standard algorithm for accomplishing this, that would be cool to know instead too.

I assume that your cubic spline is non-rational, meaning $w$ = 1, then this is in general true that exact conversion is not possible. NURBS are rational, so you can model conics, say circle whereas Bézier cannot. There is special case: rational Bézier curve, which could be used in place of NURBS.

This simply means that you can draw circle, and only approximate it with Bézier.

To approximate, it depends on degree of curve: least squares method is stable and fast for low degrees, but fails (error is not equal along curve and huge) for higher degrees. Another idea is like in de Casteljau, recursively subdivide curve and use piecewise approximation. This idea generates lots of points and is numerically less stable than least squares.

For general NURBS of order 6+, approximation technique must be of order at least 6+, but it converges slowly.

In any case, finding Bézier curve through points from NURBS is way to go.

Another option is lossless conversion from NURBS to piecewise Rational B-Splines (URBS) (after conversion these are uniform, but no precision is lost), then via Boehm algorithm or Greville points convert B-spline to R-Bézier (here again, nothing is lost) and then project it to NR-Bézier (approximation, i.e. https://ieeexplore.ieee.org/document/6658158 or https://arxiv.org/pdf/1212.3385.pdf, here conics are lost).

Errors are seen about five-six places after decimal point for nasty splines (these that cannot be exactly recovered, as oposed to nice, which are wxact), so for any drawing purpose it is not visible, unless this is for milling machine, but hey, CNC supports (G-code G02) arcs anyway.


Find the odd shortest path is NL OddPath be a set of all G, s, t, such that G is a directed graph with a path from node s to node t, and the shortest such path has odd number of edges.

How can I show OddPath is NL?
I think about it for a long time, the main problem is that I don't know how to get length of the shortest path in non-deterministic log place.

I tried to use coNL = NL to attack this problem. The problem become "find G with the shortest path with even number of edges". Again, I can't deal with "shortest path".

The graph is log-space reducible to the same question restricted to a leveled directed graph. We know the problem whether there is a path between s, t can be solved in NL, so the idea is to repeat the question for different distances.  Let G be the leveled directed graph where v(i) denotes vertex v in level i.

i=1
while i<=N where N is the size of the original graph before leveling.
    check if path exists between s(1) and t(i+1) using an NL machine.
    if yes:
        then return Accept if i is odd, else reject
    else: i++

If you have a copy of Sipser checkout page 333 for more about leveled graphs since that is where I got the idea.


How can I show that the Cook-Levin theorem does not relativize? The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) :

  Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not polynomial-time reducible to 3SAT even when the machine computing the reduction is allowed access to $A$.

What I tried was, take $A$ to be the oracle to halting problem and let $L=\{1^n | \;\exists \; \langle M,w \rangle \; \text{s.t.} \; |\langle M,w \rangle|=n \; \text{ and Turing machine M halts on w} \} $.
With this assignment I ensure $L \in NP^{A}$ and $L$ is not polynomial reducible to 3SAT if oracle is not provided to the machine carrying out reduction. Although to map an instance $1^n$ I would have to search through $2^n$ strings even if oracle is provided to the reduction machine. But this does not seem like a proof for absence of polynomial reduction in this case. Is there a way to prove it using the same example ? Is there a simpler example ?

Please refer Does Cook Levin Theorem relativize?.

Also refer to Arora, Implagiazo and Vazirani's paper: Relativizing versus Nonrelativizing Techniques: The Role of local checkability.

In the paper by Baker, Gill and Solovay (BGS) on Relativizations of the P =? N P
question (SIAM Journal on Computing, 4(4):431–442, December 1975) they give a language $B$ and $U_B$ such that $U_B \in NP^B$ and $U_B \not\in P^B$, thus proving that there are oracles $B$ for which $P^B \neq NP^B$.

We shall modify the $U_B$ and $B$ to $U_{B'}$ and $B'$ such that we get a new language that cannot be reduced to 3SAT even if there is availability of $B'$ as an oracle.

First assume that we can pad every $3SAT$ boolean instance $\phi$ to $\phi'$ with some additional dummy 3CNF expressions such that $|\phi'|$ is odd and they are equivalent, i.e., $\phi$ is satisfiable iff $\phi'$ is satisfiable. We can do it in $n+O(1)$ time and with $O(1)$ padding, but even if it takes polynomial time and extra polynomial padding it does not matter.

Now we need to combine the $B$ and $3SAT$ to $B'$ somehow so that BGS theorem still holds but additionally $3SAT \in P^{B'}$. So we do something like the following.

$U_{B'} = \{1^n \ \ |\ \ \exists x \in B, $ such that $|x| = 1^{2n}\}$ and

$B' = B'_{constructed} \ \cup \{\phi \ \ |\ \ \phi \in 3SAT $ and $ |\phi| $ is odd $\}$.

Now we shall construct $B'_{constructed}$ according to the theorem such that if the deterministic machine $M_i^{B'}$ for input $1^n$ ($n$ is determined as in theorem) asks the oracle $B'$ a query of odd length we check if it is in $3SAT$ and answer correctly but if it asks a query of even length we proceed according to the construction, that is, answering correctly if it is already in the table, otherwise answer no every time. Then since we are running for $1^n$ we flip the answers at $2n$ length so that $M_i^{B'}$ does not decide $U_{B'}$.

We can prove similarly as in the BGS theorem that for this $B'$ and $U_{B'}$ too, we have $U_{B'} \in NP^{B'}$ and $U_{B'} \not\in P^{B'}$.

$U_{B'} \in NP^{B'}$ is easy to prove. We construct a non-deterministic Turing Machine which for input $1^n$ creates non-deterministic branches that runs for $2n$ steps to generate a different $2n$-length string and then asks oracle $B'$ if the $2n$-length string is in $B'$, and if the answer is yes it accepts $1^n$ else it  rejects $1^n$. This construction shows that $U_{B'} \in NP^{B'}$.

$U_{B'} \not\in P^{B'}$ can be proved with the help of diagonalization argument. Basically it is different from every $L(M_i^{B'})$ for every oracle Turing Machine that have $B'$ as an oracle. This is because of how we construct $B'_{constructed}$.

Now we shall prove by contradiction that there does not exist a reduction from $U_{B'}$ to $3SAT$ even with the availability of oracle $B'$.

Assume there is a reduction using oracle $B'$, i.e., $U_{B'} \leq^{B'}_P 3SAT$.

That means we can reduce a string of the form $1^n$ to a 3SAT instance $\phi$ using a polynomial-time deterministic machine which uses $B'$ as oracle.

We can now describe a deterministic TM $M^{B'}$ which will decide strings $U_{B'}$ in polynomial time using $B'$ as an oracle. First this machine reduces the input $1^n$ to a 3SAT-instance $\phi$ using $B'$ as an oracle. This can be done because we have the reduction above. Then if $\phi$ is not odd length $M^{B'}$ will pad it to make $\phi'$ which is odd length. Next, it will give this $\phi'$ to oracle $B'$ and get the answer yes/no. It will accept if the answer is yes and reject if the answer is no.

This machine is deterministically polynomial and uses oracle $B'$.

Thus we have proved that $U_{B'} \in P^{B'}$, a contradiction.

Therefore $U_{B'} \not\leq^{B'}_P 3SAT$.


What is a constructor in java? I have checked many websites but did not get the right answer. what is the meaning of constructor in java?

Constructors are used to initialize the object’s state. Like methods of, a constructor also contains collection of statements(i.e. instructions) that are executed at time of Object creation.A constructor is invoked at the time of object or instance creation.


Efficient algorithm for finding weakly connected components We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all weakly connected components (I had to search a bit to actually find the term).

The most obvious solution would be to do a BFS or DFS on all unvisited nodes and the number of connected components would be the number of searches needed. This is actually what Wikipedia suggests for weakly connected components, too.

My question is if there is a known algorithm that can find these components faster? Or is the BFS/DFS version fast enough (not sure exactly what for)?

Replace every directed edge $u \to v$ with an undirected edge $(u,v)$.  Now use any standard algorithm for finding connected components in the resulting undirected graph.

One standard approach for finding connected components is to use DFS.  This runs in linear time, i.e., $O(|V|+|E|)$ time.

You can't hope for any algorithm that will perform asymptotically faster: any correct algorithm will have to examine every vertex and every edge at least once, so will have to take at least $\Theta(|V|+|E|)$ time.


Algorithm to identify top $\log n$ elements in $O(n)$ time Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top $\log(n)$ frequent flyers, where n is the total number of the airlines’ frequent flyers. Their current algorithm runs in $O(n \log(n))$ time to sort the flyers scan the sorted list to pick the top logn flyers. Describe an algorithm that identifies the top $\log(n)$ flyer in $O(n)$ time.

How can I devise an algorithm for this problem? I tried to solve it with priority queue ADT and some well-known sorting, but cannot solve this problem.

For every $k$, you can find the $k$th largest element in $O(n)$, using a linear time selection algorithm. You can then find the $k$ largest elements by scanning the array.


Find number X by asking Hamming distance between X and Y in binary representation We need to find unknown 16-bit integer X. We can ask "how many '1'-bits in number X xor Y" (Y is 16-bit too). What best strategy to find X? Or what minimum number of questions?

For example, if answer for Y=0 is 1, we can do binarysearch-like strategy restoring X in 4 additional operations.

I have found set of 10 numbers {26330, 15436, 4730, 5006, 10083, 227, 2775, 2367, 17754, 25121} such if we ask about all of these, we can uniquely restore X.

One reasonable heuristic would be to use a greedy algorithm, which at each step picks a query that is likely to reduce the space of possibilities as much as possible.

Suppose you care about the maximum number of questions (worst-case).  Then I suggest the following strategy.  At any point, you have a set $S$ of possible values of $X$ that remain.  For each possible query $Y$ and each possible response $R$ to that query, let $n(Y,R)$ denote how many possibilities of $S$ would remain consistent with the response $R$ to query $Y$.  Define $n(Y) = \max_R n(Y,R)$.  Now, choose the query $Y$ that makes $n(Y)$ as small as possible.  [This is basically Knuth's minimax algorithm.]

Alternatively, suppose you care about the expected number of questions asked (average-case).  Then do the same, except now define $h(Y)$ to be the entropy of a random variable that takes on the value $R$ with probability $n(Y,R) / |S|$.  In other words, define

$$h(Y) = - \sum_R {n(Y,R) \over |S|} \lg {n(Y,R) \over |S|}.$$

Then choose the query $Y$ that minimizes $h(Y)$.

There is no guarantee that these procedures are optimal, but I bet they're pretty good.

Related but not the same: you might also be interested in Ulam's game, a generalization of the game of 20 questions.  Also, take a look at this post, which describes an algorithm for 20 questions based on entropy calculations.


AVL-tree insertion complexity proof I tried to figure out the proof of insertion operation in AVL-tree is O(log n), but I do not know how.
I also tried to find it somewhere on the Internet, but I could not find any good results. Do you guys have any ideas how do we proof that?

Interesting question. For a better theoretical understanding of the whole theory I would suggest you to re-read "Introduction to Algorithms, Third Edition, Cormen" Chapter 12 (Trees) and Chapter 13 (Red-Black Trees). Since it is stated there that (page 311):

As an immediate consequence of this lemma, we can implement the
dynamic-set operations SEARCH , MINIMUM , MAXIMUM , SUCCESSOR ,
and PREDECESSOR in $O(\log n)$ time on red-black trees, since each can
run in $O(h)$ time on a binary search tree of height $h$ (as shown in
Chapter 12) and any red-black tree on n nodes is a binary search tree
with height $O(\log n)$.

Red-Black trees do not differ from AVL-trees from a strict computational point of view: https://www.geeksforgeeks.org/red-black-tree-vs-avl-tree/. An AVL tree is a subset of a Red-Black tree: http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948. So from a theoretical point of view, you can map them together (computational-complexity wise).
Regarding a pure understanding of why the INSERTION is $O(\log n)$, check this implementation example. There you can clearly see that what makes an AVL differ from a standard BST are the rotations, that can be performed in constant time. With those you get a balanced tree, and with a balanced tree you get $O(\log n)$ INSERTION.