texts: Proving that $L = \{a^m b^n | m \% n = 0 \}$ is not context-free

texts:
For language $L = \{a^m\, b^n\: |\: m \:\%\: n = 0 \}$, that is, $m$ is a multiple of $n$, I'm trying to find a proof that it isn't a context free. I know it isn't regular, but it also doesn't seem to be context-free to me. However, I am not sure how I would go about proving that it isn't context-free. My quick attempt follows:

First, assume to contrary that $L$ is context-free. Let $p$ be the guaranteed pumping length. Choose string $s\,=\,a^{\,p+1}\,b^{\,p+1}$, where $s\,\in\,L$. By the pumping lemma, we can write $s$ as $s\,=\,uxwvy$.

If $vx$ contains either $a's$ or $b's$, then $uv^2wx^2y\:\not\in\:L$.

If $vx$ contains both $a's$ and $b's$, then $uv^2wx^2y\:\not\in\:L$.

Therefore, we have a contradiction and $L$ cannot be context-free.

However, I don't believe I have the proof completely right, and I would like an elaboration how this proof could be better presented.

EDIT: Is this language context-free? Why or why not?


texts: How can I show that the function f(u, v) = uv is computable in programming language S_n. Here uv is concatenation of the words u and v

texts: This is in reference to a question I found in chapter 5 (Calculation on strings) Computability, Complexity, and Language by Martin D. Davis


texts: Can we define a program by means of a walk of a graph induced by the category of types?

texts:
After reading about Category Theory at https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ I was wondering whether we can represent any program by means of a walk of a graph induced by the category of types.

EDIT: rephrasing the question a little bit.

So, given the category of types where the objects belong to a set of types $V$ and the morphisms are a set of functions $F$ with $f : a \rightarrow b$, if we define a walk on this category as a sequence $v_0, e_{0,1}, v_1, ..., v_n$, with $v_i \in V$ and $e_{i,j} \in E \subset F$, with $E$ as the default set of functions of any given programming language (add, mul, <, etc.), the pure part of a program could be defined as a walk on this set $E$.

So, for example, a program to return the greatest of two integers could be represented as:

v0 -> e1 -> v1 -> e2 -> v2
(Int, Int) -> e1 -> (Bool, Int, Int) -> e2 -> Int

with:

e1 : (Int, Int) -> (Bool, Int, Int)
e1 x y = (x>y, x, y)

e2 : (Bool, Int, Int) -> (Int, Int)
e2 b x y = if b then x else y

given that e1 and e2 are part of the subset of morphisms.

So, is the definition of a walk and this set $E$  sufficient to represent the pure part of any program?


texts:
I know that the CPU has a program counter which takes instructions that are required to execute a program, from the memory, one by one. I also know that once the first instruction is executed, the program counter automatically increments by 1 and accesses the data in the cell with the corresponding address.

Now my question is, what if the next instruction in the memory cell, i.e. the instruction in the memory cell after incrementing the counter by 1 is not the required instruction to execute the given program? And what if the next instruction that is required is, in a memory cell who's address can be got to only after 'n' increments?

If it helps I used this video as a reference

EDIT: If it isn't clear, what I'm trying to ask is this:
Suppose to execute a given program I need 5 instructions- A,B,C,D,E.

Now suppose instruction A is loaded in a  memory cell with address 0000H. So when the program counter reads 0000, it takes the instruction from 0000H, and when the counter reads 0001, it takes the memory from 0001H and so on. Now what if instruction C is in 0007? After 0001H the program counter would increment to 0002. But i don't need the instruction from 0002H. I need it from 0007. So what does the counter do in such a situation?


texts: Proving that whether a Linear Bounded Automaton runs in polynomial time or not is undecidable

texts:
How would one prove that whether a Linearly Bounded Automaton (i.e a Turing Machine where the number of tape cells you can visit is not infinite but is bounded by the size of the input, i.e if the input has size n, you can visit only n tape cells, there is a right endmarker on the tape after the input ends that you cannot cross) runs in polynomial time is undecidable? I have a homework question and I can't for the life of me figure out how I'd do this.
Even if we don't consider LBAs, how would I show the undecidability of this for Turing Machines in general, i.e how would I show that it is undecidable to find whether a Turing Machine runs in polynomial time.
I was given a hint, that says "encode the Halting problem for regular Turing Machines. Given a Turing Machine M and input x, where we want to find out if M halts on x, construct an LBA N, which on any input y, erases y, and does something interesting with M and x." I can't for the life of me figure out what the "interesting thing" is supposed to be. I know that the total number of tape cells which M can access is bounded by the size of the input y, but I don't know what else to do here.
One possible approach I've tried is to construct the LBA N to halt and accept/reject iff the execution of M on x stops at most n steps, and to enter a trivial loop iff it takes more than n steps. But, this does not give me the proper implication I need. I need to construct an LBA that runs in polynomial time iff M halts on x, and does not run in polynomial time iff M loops (i.e does not halt) on x. However, with this construction, we only get the result that M loops on x implies that N does not run in polynomial time (because it loops on the input), however, I cannot prove the opposite implication, i.e M halts on x implies that N runs in polynomial time.
One more thing that's throwing me off was that since you only have a fixed number of input cells you can visit, let's say n, which is the size of the input y to the LBA, and if the size of input x is larger than n, then you have no way to simulate M on the full input x, what would I do in that case? Also even if the size of the input x is smaller than n but it's some machine that writes an output much longer than n, then what am i supposed to do? I can't possibly end up actually simulating the full work of the TM, so what would I do?


texts: Why is non-determinism a useful concept?

texts:
An automaton is an abstract model of a digital computer. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state.

When we are trying to model real systems, why include nondeterminism in Automata theory?


texts: Grouping n points into groups of size m with objective to have least traveling distance in each group

texts:
Assumptions:

There are "n" jobs which are distributed over the city.
Company has "k" available workers.
Each worker can do "x" jobs per day.
"x" is dependent to the worker skills and the distance he travels each day so it's not a constant.
Workers have no initial traveling distance.
"s" is a set that shows each workers can do how many jobs based on the distance he travels
"d" is the number of days that takes for company to do all the jobs.

Objective: Minimize the "d"

I know this problem is probably NP-hard so I don't need the exact answer. I think it's kinda a variation of Traveling salesman problem combining with scheduling and assignment problems.

My algorithm for this problem is to "some how" efficiently ( of course not the most efficient way ) grouping the jobs based on their traveling distance in the groups in to groups of "m" which is the mean of set "s". Then after each day rerun the algorithm to get better results.

My question is what is the best way to do that grouping? Anyway if you know a better algorithm I would be more than happy to know them.


texts: How to apply "verification" and "decision" for the SUBSET SUM problem?

texts:
The SUBSET SUM problem states that:

Given finite set S of integers, is there a subset whose sum is exactly t?

Can someone show me why verification is simpler than decision for this problem?


texts: Understanding Dijkstra's notation $f.x.y$

texts:
I recently discovered that I have a fondness for the work of Dijkstra. I am currently reading random EWDs, and stumbled across one with some notation that I couldn't quite grasp.

Dijkstra states that $[ x < y \implies f.x.y < f.y.x]$

OK, so. This isn't a list comprehension, right? Why the brackets?

Also, how could this be read aloud? What does $\implies$ mean?

And finally, what does $f.x.y$ and $f.y.x$ mean?

And how could this statement be written more conventionally? And does Dijkstra's notation derive from anything, or is it entirely his own invention?


texts:
I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here.

Ques1. If $x,y$ are two vertices such that distance between them is $D$, then is it true that any shortest path between them will contain at least one centre?

Ques2. If $D=2R$, then does the graph contains only one centre?

Ques3. Also, can we say that if $D<<2R$, then graph would contain a lot of centres?
(Intuitively I feel so because in figure below, $D$ is smaller than $2R$, and graph contains a lot of centres, the red coloured vertices.)


texts: How hard is finding the shortest path in a graph matching a given regular language?

texts:
Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some alphabet $\Sigma$. We are also given a description of an NFA $M$ (or DFA, or regular expression) accepting some regular language $L(M) \subseteq \Sigma^*$, and two vertices $s, t \in V$.

The problem is to find the shortest path in $G$ from $s$ to $t$ whose edge labels form a string that is a member of $L(M)$. That is, we only consider paths $e_1, e_2, \dots, e_k$ where $\ell(e_1) \ell(e_2) \dots \ell(e_k) \in L(M)$.

Can this problem be solved in time polynomial in $|V|$, $|E|$, and $|M|$?

This question was inspired by these other questions about special cases of this problem.


texts: What guarantees do "soft" real-time operating systems actually provide

texts:
I think I know what a "hard" real-time operating system is.  It is an operating system with a scheduler that provides a contract with the application programmer.  An application provides a deadline with each resource allocation request.  If the deadline requests are feasible, the scheduler guarantees that each resource will be allocated to the requesting application before the deadline.  The guarantee is sufficient to enable an application programmer to reason about the maximum latencies and minimum throughputs of specific requests.

All the definitions I find of "soft" real-time systems seem vacuous to me.  Wikipedia says

  the usefulness of a result degrades after its deadline, thereby degrading the system's quality of service.

Uhhhh.  Okay.  By that criteria Windows 95 was a soft real time system and so was 3BSD and so is Linux.  Wikipedia is not a great source, but the next couple of Google hits aren't much better.  For example http://users.ece.cmu.edu/~koopman/des_s99/real_time/ says

  In a soft real-time system, a degraded operation in a rarely occurring peak load can be tolerated.

That's not a contract, that's a fancy way of saying nothing.

What are examples of real soft real-time guarantees/contracts offered by real operating systems?

I'm looking for answers of the form:

  In (OS-name) if programmer does (what-programmer-needs-to-do) then the operating system guarantees (what-the-system-guarantees).


texts: Job sites for applied/interdisciplinary mathematics related to computer science?

texts:
I'm looking for job sites in applied/interdisciplinary mathematics, more specially, say postdocs or higher positions in mathematics and medical imaging, mathematics and computer vision. I'm aware of mostly all the popular job sites, mathjobs, euro math jobs, jobs.ac.uk, nordic math jobs etc etc, but most of the jobs there are of 'pure' nature, with very few for applied/interdisciplinary.

I'm trying to find postdoctoral position in mathematical imaging problems, which would use significant amount of conformal/quasiconformal mappings, Riemann surfaces, differential geometry etc. Looking into individual group's webpage is too much work. But if there's an webpage containing all the information, that'll be much better!

So, if you know any such website for the above (for Europe(preferable) and US), I'd appreciate if you could pass them onto me. Thanks!


texts: Are poly-reductions to PSPACE problems for following problems are known?

texts:
List of problems I'm interested in:

$\oplus$SAT
#SAT-decision
Permanent-decision (YES if permanent is greater than given number $k$)

I have discovered poly-reduction for MAJSAT (and MAJQBF). However, I don't know such reduction (practical) for these problems.

How can I solve any of these problems with polynomial runs of TQBF? Or can I make a special TQBF to solve them. The special TQBF length should increase (not more than) polynomially compared to original problem.


texts: Asymptotic behavior of functions with not analytic expression

texts:
Is it in general acceptable by computer science community, if the run-time or space consumption of an algorithm is derived by experiment and not analytically?

For example let's say we have an algorithm for which it's running time is given by function $f(n)$, where $n$ is the size of the problem. There is no way to derive its asymptotic behaviour (respecting run time) analytically but only using numerical methods. In other words we have no analytical expression for $f(n)$ but we can probe it using specific values for $n$. Making some trials (trying a wide range of n) we see that run time follows for example very closely a line. Let's say that doing least square method we observe that $t= an+b$ is a good fit for the run time t of the problem (of size n). Good fit is a vague term, and I mean that residuals are within acceptable ranges.

So is it safe to say that the run time of this algorithm is $\Theta(n)$, at least in the range we made the trials?
Moreover can we state that this algorithm is faster than another one whose asymptotic behavior is for example $O(n^2)$.

If the answer is negative, what other methods should I search for?


texts:
Say I have a dynamic array of the proper length $n$. A sort pivot is given.

I run the sort algorithm, wait, and get $j$ unbalanced pivots. Is the time complexity $O(n\log n)$ or has it destabilized to quadratic in the best case? I believe that it will be useful to use recurrences to model each scenario, but not sure how to set up from there.


texts: Ordering Multicasting in Distributed Systems

texts: We know that Causal ordering in ordering multicasting implies FIFO ordering. But does FIFO ordering implies Casual Ordering?


texts: Obtaining max set interval intersection using Divide and Conquer

texts:
Given an array with $n>2$ elements  of integer sets intervals, where each set is represented  as a tuple of the form  $(inf, sup)$  (with $inf $ ínfimum and $sup $ maximum of the set), we want to obtain the two intervals such that the number of elements of the intersection is maximum.

$e.g: A=[(1,2),(1,4),(3,7),(4,7)]$

The maximum intersection is given by the elements  $(3,7)$ and $ (4,7) $ with $4$ elements {4,5,6,7}.

The algorithm is required to be implemented using the Divide and Conquer strategy and running in time $O (n\log n) $.

Any ideas?


texts: Hypothesis space in AdaBoost or general Machine learning

texts: I was curious about the following: in most learning algorithms, when an algorithm is said to learn a concept class $C$ then the algorithm outputs a function from the  hypothesis space $H$ and often the complexity of the learning algorithm is stated in terms of the VC dimension of $H$. I was wondering, what is an assumption on $H$, for example, does it include all possible functions or does it only include $C$, is there any reference which talks about the properties of function in $H$ that I can assume? Say, for every $c\in C$, does there always exist an $h\in H$ for which $Pr_{x} [h(x)=c(x)]\geq 1-\varepsilon$ for every $\varepsilon>0$. Is this fair to assume?


texts: Evaluation semantics: reduction rule for a split statement

texts:
Assume a language with statements such as $x := e$, $\text{assume}(e)$, etc., and particularly a $\text{split}\ stmt_1 ... stmt_n$ statement, constructed from $n$ statements. Informally, the semantics of this statement is that each statement is evaluated separately, and if exactly one such evaluation terminates (i.e. is not stuck) then the result of the split statement (expressed as the new state) is the result of that evaluation. I'm trying to express this semantic formally using a big-step evaluation rule. Here is my try:

$$
\dfrac
{stmt_i\ |\ \mu \Downarrow \mu_i' \wedge \forall j \neq i. (\not\exists \mu_j'.\ stmt_j\ |\ \mu\ \Downarrow \mu_j')}
{\textbf{split}\ stmt_1 ... stmt_n\ |\ \mu \Downarrow \mu_i'}\text{E-Split-i}
$$

Read:

  The statement "$\textbf{split}\ stmt_1 ... stmt_n$" evaluated in context $\mu$ results in context $\mu_i'$ if its $i$th statement evaluated in context $\mu$ results in context $\mu_i'$ and there is no other statement among $\{stmt_1, ..., stmt_{i-1}, stmt_{i+1}, ..., stmt_n\}$ for which there exists a context $\mu_j'$ such that evaluating this statement in context $\mu$ results in context $\mu_j'$. (Implying that the evaluation of every other statement is stuck at some point.)

Is my rule correctly formalized? Is there a better way of writing it?


texts: Kolmogorov complexity of a sequence of n bits with k ones

texts:
Let Program P be :"Generate, in lexicographic order, all sequences with k ones and n bit length;
Of these sequences, print the ith sequence."

Apparently the length of this program is $\log(n) + \log(\binom{n}{k}) + c$ where $c$ is a constant. Where $i$ can be represented in $\log(n)$ bits and
k in $\log(\binom{n}{k})$ bits. Why does the length of the program not take into account that we will be generating all of these sequences in lexicographic order, does the length of the sequences and the number of sequences not depend on $n$. Don't you have to hold those in an array? Does that not take space?

Thank you.


texts: Checking Divisibility Using Minimal Bits

texts:
Suppose we're given an infinite stream of integers, $x_1, x_2, \dots$.

  a) Show that we can compute whether the sum of all integers seen so far is divisible by some fixed integer $N$ using $O(\log N)$ bits of memory.

  b) Let $N$ be an arbitrary number, and suppose we're given $N$'s prime factorization: $N = p_1 ^{k_1} p_2 ^{k_2} \dots p_r ^{k_r}$. How would you check whether $N$ divides the product of all integers $x_i$ seen so far, using as few bits of memory as possible? Write down the number of bits used in terms of $k_1, ..., k_r$.

For part a), we know that for any prime $p \ne 2, 5$, there is an integer
$r$ such that in order to see if $p$ divides a decimal number $n$, we break $n$ into $r$-tuples of decimal digits, add up these $r$-tuples, and check if the sum is divisible by $p$. But $N$ is a fixed integer, and not necessarily a prime. Is there some way to connect the theorem above to any arbitrary integer?

For part b), for the product of $x_i$ (call it $y$) is divisible by $N$, then $y$ must be divisible by each $p_i ^{k_i}$ (call it $a_i$. Since we're given the prime factorization, we can just check if $y$ is divisible by $N$ by dividing $y$ by each $a_i$ and halting when it fails, right? Would this result in using $k_1 \times \dots \times k_r$ bits?

Am I at least on the right track, or am I completely wrong? Any help understanding this problem would be tremendously helpful.


texts: Randomized algorithm to make a Binary Search Tree from an array of $n$ distinct elements

texts:
An array $\mathcal{A}$ of $n$ distinct integers $\{a_1,a_2,\ldots,a_n\}$ is given. I'm asked to design a randomized (esp. Las Vegas) algorithm to make a Binary Search Tree out of these elements, such that the height of the tree is $\lceil \log{_{2-\epsilon}n}\rceil$, where $\epsilon=\frac{2}{9}$.

If we had to make a perfectly balanced binary search tree, we need to choose the median of the $n$ elements as root in every recursive call. But the height is not exactly $\lceil \log{_{2}n}\rceil$; there is a relaxation by $\epsilon$. So instead of choosing the median we need to choose any value (randomly) from the middle $x\%$ of the sorted version of $\mathcal{A}$. For example, suppose$\mathcal{A}=\{4,2,3,6,1,5,7,10,9,8\}$, $\therefore\mathcal{A_{sorted}}=\{1,2,3,4,5,6,7,8,9,10\}$. Now because the height is not exactly $\lceil\lg n\rceil$, so instead of choosing the median, we need to choose one element randomly from the middle $30\%$ of the elements (say for example), $i.e$ one element randomly from $\{4,5,6\}$. Here this value $30\%(x\%)$ will depend on $\epsilon\ (\frac{2}{9})$. My question is how to derive this $x\%$ from the height information given $i.e$ $\lceil\log{_{2-\epsilon}n}\rceil$ ?
$$\lceil\log{_{2-\epsilon}n}\rceil = \left\lceil\frac{\log{_{2}n}}{\log{_{2}{(2-\epsilon)}}}\right\rceil=\left\lceil\frac{\log{_{2}n}}{0.83}\right\rceil$$

I don't need a full explanation, any hint would suffice.


texts: Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

texts:
I am having difficulties in understanding why the recurrence

$$T(n)=3T(n/4) + n\log n$$

is solvable with Master Method but

$$T(n)=2T(n/2) + n\log n$$

isn't?

Despite they both look very similar except the values of coefficient '$a$' and size cutter '$b$'.

I understand that the work function '$f(n)$' must be polynomially larger/smaller than $n^{\log_ba}$. And that in second recurrence $n^{\log_22}=n$ is not polynomially comparable to $f(n)=n\log n$. So Master Method cannot be applied. But why can it be applied to the first recurrence?

I found these examples in CLRS Intro to Algo book, and can't understand them. Can you please explain.


texts: How to Know Whether a Topic is Publishable in Computer Science

texts:
Forgive my ignorance, but I am very new to the publishing process in Computer Science. I have some research that I have done involving analyzing data formats used in web-based image processing applications being presented in various IEEE papers. Some are conference papers and some actual IEEE transactions. They all seem to proposing the use of XML or in very few cases JSON as the data formats of choice.

I have read a few IEEE papers done on data traversal speeds involving comparisons made between XML and JSON or one of those two with that of CSVs, but not all three. And I have not found anything that give clear direction for one's reasoning for selecting a particular data format and why. Have I simply missed something? Tis likely, but I wanted to confirm with others first.

I have developed a small proof of concept here, and found some interesting results that I wrote about it here and wanted to see if this is worth trying to publish. Is this a good place to get insights, and share ideas that could be publishable? If so, does anyone have any insight into whether the material I have here is of interest to the scientific computing community? Or is this just a clever IT solution?

I am in the process of refining the paper to include tests done in compiled as well as an interpreted languages. Not to mention the reasoning behind selecting other data formats like CSV or TSV, which appear to much faster to traverse than JSON or XML, but less flexible. JSON appears to be the best choice on average, but more testing is required.

If this is not appropriate, let me know and I will remove this posting. Please also let me know if it is indeed appropriate and if you need more information or less and more of a synopsis.

Thank you in advance.


texts: How many states in a 2 delay (or n delay) transducer (using DFA)?

texts:
An n delay transducer in the context of the problem simply means that the output is same as the input but after waiting for 2 more symbols in the input.

2-delay transducer: We can't show any result till we see 2 symbols. So, to store in DFA we need states 00 01 10 11.
But in order to create 00 01 10 11, we need another starting state: S0, state 0, state 1. That makes it 7 states.

The book says the following:

  If input is a1a2... then output is (lambda)^n a1a2...

  Construct a 2
  day transducer over {a,b}

  Prove that n delay transducer takes
  |{a,b}|^n states.

What I don't understand is that if we add the states that ultimately let us go to the states from where output can be given (for example, 00 01 10 11), then we get more than 2^n states for {a,b} alphabet.

Am I missing something or is the book not clear about this?

Question has been taken from peter linz's "An Introduction to Formal Languages and Automata" 5th Edition. Exercise 1.3 Problem No. 9


texts: How to generate the LR(0) finite state machine for a grammar

texts:
Here is a context-free grammar with a single nonterminal symbol S and three terminal symbols +, *, and s:

S -> + S S | * S S| s

My purpose is to build the LR state machine for this grammar.  My attempt:

[State 0]      ->     [State 1]       ->       [State 2]
S -> . + S S   (+)    S -> + . S S    (*)      S -> * . S S
S -> . * S S          S -> . * S S             S -> . + S S //leads to loop
S -> .s               S -> .s

When I get to state 2, I see that an infinite loop begins to form. I think I am missing/misunderstanding part of the algorithm to form the machine. Can you ignore a production if it already exists somewhere else?


texts:
Wikipedia's solution for multi Producer-Consumer problem uses both mutexes and semaphores.

mutex buffer_mutex;
semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;

procedure producer()
{
    while (true)
    {
        item = produceItem();
        down(emptyCount);
        down(buffer_mutex);
        putItemIntoBuffer(item);
        up(buffer_mutex);
        up(fillCount);
    }
}

procedure consumer()
{
    while (true)
    {
        down(fillCount);
        down(buffer_mutex);
        item = removeItemFromBuffer();
        up(buffer_mutex);
        up(emptyCount);
        consumeItem(item);
    }
}

The reason given for using a mutex is to enforce mutual exclusion when multiple producers and consumers are in the critical section. My question is, since the goal is to have a single thread in the critical section anyway, why not just use a binary semaphore, which ensures this? That is, can we do away with the mutexes if we use binary semaphores in that example?

Can we have something like this instead?

semaphore empty = 1
semaphore full = 0
procedure producer()
{
    while (true)
    {
        down(empty);
        putItemIntoBuffer(item);
        up(full);
    }
}

procedure consumer()
{
    while (true)
    {
        down(full);
        item = removeItemFromBuffer();
        up(empty);
    }

}


texts: Is it possible to solve maximum weight independent set in linear time for a cycle?

texts:
Given a cycle of $n$ vertices and each vertices of the input graph $G$ assigned a weight.

We want to find an independent set of cycle such that weight of the vertices taken in the independent set is maximum.

A brute force way is consider cycle as a set of three consecutive vertices and pick the one with max weight, but the runtime of this algorithm will be $O(2^\frac{n}{3})$.


texts: What is the time complexity of MATLAB's ode solvers?

texts:
Say I have a system that is $n$ differential equations that are all coupled together, over a time interval $[a,b]$ with timestep $t$. Is there a straightforward time complexity for MATLAB's built in differential equation solvers ode45, ode23, ode15s? Particularly I am interested in how ode15s grows as the size of $n$ increases. Any help is appreciated!

ode15s is "Variable-timestep, variable-order" method, so I have no idea how to determine the complexity


texts: Adding words to DFA, maintaining minimality

texts:
How can we add new words to DFA, maintaining minimality?

Maybe, you can advise some completely different approach to solve the following problem:

  A program must process two types of queries:

  Add new word to the language.
  Check if some word of the language occurs in the input string as a substring.

  Time and space complexity should be as low as possible.

The only solution that I know so far is to rebuild an automaton from scratch every time, using Aho-Corasick algorithm, but, you know, it's really-really inefficient.

I've performed some search on Internet and found some papers like "Incremental Construction of Minimal Acyclic Finite-State Automata", but, unfortunately, algorithm described there produces and maintains just a minimal trie (not a complete FSM with suffix links, like an automaton produced by Aho-Corasick algo).


texts:
When reading about shortest paths in Cormen . I came across this paragraph which says that 'shortest path cannot contain' positive edge path even. But I don't understand the logic behind their explanation

  Can a shortest path contain a cycle? As we have just seen, it cannot contain a
  negative-weight cycle. Nor can it contain a positive-weight cycle, since removing the cycle from the path produces a path with the same source and destination
  vertices and a lower path weight. That is, if p {vo,v1,v2,.... vk} is a path and
  c = {vi; v(i+1)....vj) is a positive-weight cycle on this path (so that vi = vj and
  w(c) > 0), then the path pnew =  {v0,v1,.... vi, v(j+1) , ... vk} has weight
  w(pnew) = w(p)-w(c) < w(p), and so p cannot be a shortest path from v0 to vk.

The original snip from the book is here.

Could someone explain why it is so ?
I don't understand because any way removing an edge will cause the path length to decrease right ? why are they seeing removing positive edge cycle as different ?

For eg in the following diagram

How are they removing cycle and connecting vi and v(j+1) ?


texts: Complexity of finding the shortest simple even s-t-path

texts:
Consider a graph $G=(V,E)$ and two vertices $s,t$.

What is the complexity of finding the length of the shortest simple $s-t$ path that has even length?
Does the problem become harder if the graph is edge weighted?

Note that the requirement that the path is simple makes it harder than to simply to use two copies of the graph


texts:
Question:

  Given a tree representing a neighbourhood where each node is a house.
  Assign an antenna to each node such that the whole tree is covered.

  An antenna of strength 0 can only provide a signal to itself.
  An antenna of strength j can provide a signal to itself and nodes
  that are j steps away from it. The cost of building an antenna at
  a house is given by a cost function f(ni, j) where
  ni is the i'th node and j is the signal strength. Additionally the cost of an antenna with strength j has to be less or equal the cost of an antenna with strength i if j is weaker than i.

     7
     |
     6
   / | \
  3  4  5
 / \
1   2

For example an optimal solution in this tree for a cost function f(ni, j) = j + 1 would be to place an antenna of strength 2 at node 6.

This is a school assignment and the ultimate goal is to write a dynamic programm that can solve it in O(n^2). As far as my understanding goes the 'trick' of dynamic programming is to find a recursive algorithm that can solve the problem in exp. time and then use a table to cache the intermediate answers that build upon each other to improve the time complexity.

I fail in seeing a recurrence in the problem and and would appreciate if someone could point me in the right direction.


texts: What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization?

texts: I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am assuming it means a path from s to t with maximum total capacities once you sum the capacities across the path. However, I am not sure what the term bottleneck adds to the definition nor was I sure if that was correct. Is that the correct definition?


texts: What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end?

texts:
Here are some sequences:

'0.66666'
[3,0,1,2,2,2,0,1]
'banana'
'bandana'
'11221122'

I would like to find the index and length of the substring in each which is repeated (even if partially) for the most terms and which repeats until the end.

I wrote a function in JavaScript that successfully returns the
expected output:

'0.66666'           After occurring at index 2, '6' repeats for 4 terms.
[3,0,1,2,2,2,0,1]   After occurring at index 1, [0,1,2,2,2] repeats for 2 terms.
'banana'            After occurring at index 1, 'an' repeats for 3 terms.
'bandana'           After occurring at index 4, 'an' repeats for 1 terms.
'11221122'          After occurring at index 0, '1122' repeats for 4 terms.

Explanation:

[3,0,1,2,2,2,0,1] is a sequence with 8 terms. [0,1,2,2,2] is the longest substring which repeats at least partially to the end of the sequence, because after its first occurrence it repeats directly after for another 2 terms. Then the sequence terminates.
If we were to input [3,0,2,2,2,0], you might think the substring [2] wins because it repeats for 2 terms following its first occurrence, but it doesn't repeat to the end so the substring [0,2,2,2] wins as the term that follows the only occurrence of this substring (0) is also the first term in the substring meaning that it repeats for 1 term following the first occurance.

Repetition must continue to the end so for the second example [2,2,2] is not valid though it also repeats for two terms

Here's the function (JS Bin):

function longestRepeatedSuffix(sequence) {
    var repeatStart;
    var blockLength;
    var maxRepeatLength = 0;

    // Go through each suffix from length 1 to the length of the sequence - 1.
    suffixLoop: for (var suffixI = sequence.length - 1; suffixI > 0; suffixI--) {
        var len = sequence.length - suffixI;
        var repeatLength = 0;

        // Go right to left through adjacent substrings the length of suffix.
        // substringI may be negative on the last iteration.
        for (var substringI = suffixI - len; substringI >= 1 - len; substringI -= len) {

            // Go right to left through characters in the suffix and current substring.
            for (var charI = len - 1; charI >= 0 && substringI + charI >= 0; charI--) {

                // See how many characters match.
                if (sequence[substringI + charI] === sequence[suffixI + charI]) {
                    repeatLength++;
                    if (repeatLength > maxRepeatLength) {
                        maxRepeatLength = repeatLength;
                        repeatStart = substringI + charI;
                        blockLength = len;
                    }
                } else {
                    continue suffixLoop;
                }
            }
        }
    }
    return 'After occurring at index ' + repeatStart + ', "' +
        sequence.slice(repeatStart, repeatStart + blockLength) +
        '" repeats for ' + maxRepeatLength + ' terms.';
}

I believe this is an O(n^2) implementation even though I used 3 nested for-loops. So my question is: how can I use something like a suffix-tree to get even better time complexity?

Similar algorithm:

Longest repeated substring: This is different, as it includes repetitions which overlap and those which are not adjacent (not just consecutive repetitions) and it doesn't require repetition to continue to the end.


texts: Is it possible to have multiple languages accepted by a DFA?

texts: Is it possible to have multiple languages in a DFA? in my example in the image, I think the language L={w | w = 0x where x is {0}* } is accepted and the language L={w | w = 0x11 where x is {0}* } could be accepted as well.


texts: Determine whether two languages are context free

texts:
(1) $L_1 = \{a^ib^{i+j}c^j|i,j\geq 0\} $

(2) $L_2 = \{xy | x,y \in \{0,1\}^*, x \neq y, |x| = |y| \}$

I doubt that $L_1$ is CFL. I've been trying to go with the string $s$ = $a^pb^{2p}c^p$. Thus, we can write $s$ as $uvxyz$. Now I'm trying to show $uv^2xy^2z$ is not in $L_1$.

I really have no idea how to approach (2). And if it is context free, how in the world would you draw a pda?


texts: Graph searching: Breadth-first vs. depth-first

texts:
When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).

Now, are there any advantages of one over another?

The ones I could think of:

If you expect your data to be pretty far down inside the graph, depth-first might find it earlier, as you are going down into the deeper parts of the graph very fast.
Conversely, if you expect your data to be pretty far up in the graph, breadth-first might give the result earlier.

Is there anything I have missed or does it mostly come down to personal preference?


texts:
What does x-bit binary number mean?
for example:

if x = 8

is 8-bit means:
any number consists of 8 bits, like : 10101110

or it has another meaning??


texts: Propositional formula in DNF can be decided in polynomial time?

texts:
For a given propositional formula f in DNF, one can decide in polynomial time, if the formula is satisfiable:
Just walk through all subformulas (l_1 and ... and l_k) and check, wheter it has NO complementary pair of literals. Formula f is satisfiable iff such subformula exists.

Is my approach above correct ?

If yes, I'm wondering why all modern SAT solvers get a CNF as input format, and don't just use DNF.


texts: Combining TWO Monte Carlo algorithms to get a Las Vegas algorithm that solves the same problem

texts:
I came across a problem that I have no clue how to solve.

Consider two Monte Carlo algorithms, called A and B that both solve the same problem.
A is true-biased and t-correct, while B is false-biased and z-correct.
Show that you can combine both A and B to obtain a Las Vegas algorithm to solve the same problem.

Also, how would I find the best value of R, which is the probability of the las vegas algorithm to find the right answer? For this second part, how would I find this fictional value of R with no concrete example or data set, this question seems completely out of left field.

Thank you kindly for your time :)


texts: Reduction from $L_{nonuniversal}$ to $L_{finite}$

texts:
As I'm currently preparing for my Algorithms and Complexity exam, I was facing today an other reduction and I'm not quite sure if I solved it correctly.

Given are two languages $L_{finite}$ and $L_{nonuniversal}$:

$L_{finite} = \{\langle M \rangle \mid \vert L(M) \vert < \infty \}$

$L_{nonuniversal} = \{\langle M \rangle \mid L(M) \neq \{0,1\}^* \} $

I'm trying to proof the following reduction: $ L_{nonuniversal} \le_T L_{finite} $

Given $M$ let $M'$ be the Turing Machine that on input $w$ simulates $w$  on $M$. It then takes $w$ after $M$ halted and removes it from its tape and replaces it with a static word $v$ (let this be "1" for example, anything that is $\neq \{0,1\}^*$).

Give $M$ and $M'$ to the $finite$ oracle and return its answer.

I'm trying to show here that if $w$ can only be a static string, then it's $\in finite$.


texts: Does checking the middle bit of an input require a log(n) space pointer?

texts:
Let n be an even integer.

Let i be an input of length n.

Positions start at 0: the first bit is bit 0. The second bit is bit 1. etc.

The decision problem is, "Is bit n/2 equal to 1"?

The input is on a tape.

We have a single pointer to the input. We cannot overwrite the input tape.

We have finite amount of working-memory tapes to compute with (in case more than 1 is useful).

Space-complexity is the maximum amount of non-empty tape cells to ever appear across all work tapes at any point during the execution.

(That way, in practice, this can correspond to virtualizing a Turing machine and adding or removing physical hard drives to back each logical working-memory tape.)

Each pointer can be moved left or right one cell.

One way to decide the problem is with a counter of length O(log(n)): Initialize to 0's, then increment until the counter equals n/2, then check the bit.

That takes O(log(n)) space.

Can we do better? Or is O(log(n)) the best space-complexity we can do?

If we can do better, in general, then there's a system of representing integers more space-efficient than polynomial bases (decimal, binary, etc.).

For example, if we had access to the corresponding busy-beaver machine for n/2, then we could use that (and instead of printing out a 0, we could move our input tape by 1). However, in general, we cannot compute the (optimal) busy-beaver for n/2.

So, is there a way to compute a "sub-optimal busy-beaver" and use that to get to n/2 instead of a O(log(n)) counter?


texts: Are NP-complete sets formed from two other sets only if at least one is NP-hard?

texts:
This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets:

If the set resulting from the union, intersection, or Cartesian
product of two decidable sets $L_1$  and $L_2$ is NP-complete, is at
least one of $L_1, L_2$ necessarily NP-hard?  I know that they cannot
both be in P (assuming P != NP) since P is closed under these set operations.  I also
know that the conditions of "decidable" and "NP-hard" are necessary
since if we consider any NP-complete set $L$ and another set $B$ outside
of NP (whether just NP-hard or undecidable) then we can form two
new NP-hard sets not in NP whose intersection is NP-complete.  For
example: $L_1:= 01L \cup 11B$, and $L_2:= 01L \cup 00B$.  However,
I don't know how to proceed after that.

I'm thinking that the case of union might not be true since we can take a NP-complete set $A$ and perform the construction in Ladner's Theorem to get a set $B \in$ NPI which is a subset of $A$.  Then $B \cup (A \setminus B) =  A$ is the original NP-complete set.  However, I don't know if $A \setminus B$ is still in NPI or NP-hard.  I don't even know where to start for the case of intersection and Cartesian product.


texts: How does "Greedy Stays Ahead" Prove an Optimal Greedy Algorithm?

texts:
I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem.

On the second page of Cornell's Greedy Stays Ahead handout, I don't understand a few things:

All of the proofs make the base case seem so trivial (when r=1). I don't understand the context behind the base case - perhaps in more easy to understand terms.
Are we essentially proving that the number of maximum activities in A cannot exceed the number of activities in O?

In short, are we saying that if A is not optimal, then there would be at least 1 more activity in the optimal solution, O, which would contradict our assumption that O is optimal and that A is the set of requests made by the greedy algorithm?  Because we don't say that A is optimal.  But we know that it's the set of requests selected by the greedy algorithm.  So, if it doesn't include the same number of requests than O, then we know that it couldn't have been selected by the greedy algorithm?


texts: How is the RKHS norm related to sample complexity or other learning theory properties?

texts:
This is a somewhat soft question. Given two reproducing kernel Hilbert spaces (RKHSs) $H_1$ and $H_2$, if their RKHS norms only differ by a constant, i.e., $C_1\|f\|_{H_1}\le \|f\|_{H_2} \le C_2\|f\|_{H_1}$, where $C_1,C_2>0$. What can we say about the sample complexity or other learning theory properties?
Thank you!


texts: What type of virus protections are available and their suitability to a cyber-security company.  I'm talking about top notch stuff. Are there any methods or techniques that are rare or unusual? Othere than Anti-Virus softwares, are there other ways to keep your systems protected from virus?


texts: Search string excluding longer string containing substring that contains string, not exclusively longer string

texts:
How you define a search of text to find a string A, but exclude results that contains B only (which contains A), but not the both string A and string B?

For example:

String A : "Great Wall"
String B : "Great Wall of China"
Text 1: "The Great Wall"
Text 2: "The Great Wall of China"
Text 3: "The Great Wall of China is a Great Wall"
Text 4: "Lorem Ipsum"

I've used Bold to indicate when String A is present and Italics when String B is present.

We would like to search for Texts that contains A, and A + B, but not B only.

So the results should be the Texts 1 and 3.

What approach would enable us to find these results?

Also, we are using a search that can provide us only a list of items that contains a string.


texts: Defining the polynomial hierarchy using $\Pi_i^p$ instead of $\Sigma_i^p$

texts:
From Computational Complexity - A Modern Approach, it is claimed in a remark that the following holds true.

Remark 5.5
Note that $\mathbf\Sigma_1^p = \mathbf{NP}$ and $\mathbf\Pi_1^p = \mathbf{coNP}$. More generally, for every $i \geq 1$, $\mathbf\Pi_i^p = \mathbf{co\Sigma}_i^p = \{ \overline{L} : L \in \mathbf\Sigma_i^p\}$. Note also that $\mathbf\Sigma_i^p \subseteq \mathbf\Pi_{i+1}^p$, and so we can also define the polynomial hierarchy as $\cup_{i>0} \mathbf\Pi_i^p$.

However, I am having trouble understanding this. Similar claims are made in lecture notes found on the web, but none of them give a proof since they are all left as exercise. Would it be possible to prove this using NTM instead of verifiers?


texts: Efficient algorithm to compute the diameter of a convex set?

texts:
Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the set is described by the intersection of linear equations in high dimensional space, so the number of vertices of the set can be exponential in the number of inequalities.
Given a direction, we can easily compute the distance of furthest points along that direction using linear programming. The question is how do we find that direction?


texts: How to categorize an undirected triangular graph with top, bottom, and intertwining paths

texts:
Background:
I worked on finding the maximum path from the top to the bottom of a tree-like graph. During the process I found that the algorithm for finding the maximum path from the top to bottom of a binary tree also worked for my graph. My problem arose when trying to name the program, because the graph it works on is clearly not a binary tree.

The problem:
My graph looks like this:
    ·······a······
    ······/··\·····
    ·····b···c····
    ····/··\··/··\···
    ···d···e····f··
    ··/··\·/··\··/··\·
    g····h····i····j
Due to that all the inner nodes at lower levels have multiple "parents" from the level above, it cannot be classified as a binary tree. From the perspective of finding the maximum path from the top to the bottom, it could be classified as a DAG, but because there strictly are no directed edges in the input graph, this also seems wrong. If presented in the following way:
a - c - f - j
|····|····|·
b - e - i
|····|·
d - h
|··
g
It could be argued that it is a lattice graph. But that would conceal that it has a defined "top" and "bottom", and that I have worked with a root and leaves. One could always fall back to calling it a general graph I guess, but that would conceal that it follows a very rigid structure.

My question:
What should I call this bastard that can be processed by many of the algorithms applied to binary trees but violates some of the properties of trees, for the sake of my problem can be considered a DAG but has no directed edges, and somehow resembles a lattice?


texts: coloring of an interval graph with constraints

texts:
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total duration of the tasks corresponding to each color does not exceed a constant $W$ and there exists, for each color, at least to successive activities where the elapsed time between them is greater than or equal a constant $R$

I don't know how to solve this problem or how to transform it to a know problem.


texts: How to convert DFA to regular expression using arden's rule

texts:
I generally use state removal method to convert DFA to regular expressions. But I want to try other methods like using algebraic methods and arden's rule.

How to solve a DFA with multiple final states using algebraic method?
I refered this link
https://cs.stackexchange.com/questions/2016/how-to-convert-finite-automata-to-regular-expressions and arrived at this solution which I think is wrong since a can be followed by only a or c not b.

I used state removal method and arrived at below regular expression which seems to be correct as the language won't contain ab.


texts: Resource Reservation: No Greedy Approach?

texts:
I'm considering the general resource reservation problem: n processes, m resources. Each process requests a set of resources and each resource can be used by exactly one process. Processes are only active if they have all requested resources.

Instance: A set of processes P, a set of resources R, the set of resource requests for each process, and an int k.
Question: Is it possible to allocate resources so that at least k processes are active at the same time?

My initial inclination was that a greedy approach makes sense here. Sort the jobs in increasing order of number of resources requested, then allocate resources to processes until all resources are allocated or all processes have been attempted to be scheduled, as below:

procedure reserve_resources(P, R, k):
  int jobs_active = 0;
  Order processes in ascending order of number of resources requested;
  for each process:
    if (all of the processes' requested resources are available):
      allocate resources to that process;
      jobs_active++;
    end if;
  end for;

  if (jobs_active >= k):
    return "YES";
  else:
    return "NO";
  end if;
end procedure;

I've come across an answer for this problem which shows NP-completeness by reducing Independent Set to this resource reservation problem. For the IS instance G = (V, E), it makes the set of resources equal to E, the set of process equal to V, and any edge incident to an vertex is a resource requested by that process. If k processes have disjoint resource requests, then the vertices corresponding to those processes form an independent set.

This reduction makes sense to me and I know that IS is NP. I believe that P != NP, and I certainly don't think I've just proven the opposite while working on homework in my undergrad algorithms class. But I also can't find a counterexample to the algorithm I've presented. My question is, where does this algorithm fail?


texts:
There are two stacks A and B.

A :  a,b,c,d   ('a' is on top and 'd' is at the bottom of the stack)
B :  (empty)

There are two rules.

If an element of A is popped, it must be printed immediately or pushed into B.
If an element of B is popped, it can only be printed.

So, how many permutations of a,b,c,d are possible?  (continue reading)

P.S. Well, I did calculations manually(didn't use any formula) and got 14 as the answer. However, it took around 10 minutes to do the lengthy steps. So, is there an easy way to do this?


texts:
I studied algorithm for converting grammars to GNF and was wondering about
a proof that any CFG can be converted into GNF. I found this paper - ENGELFRIET, Joost. An Elementary Proof of Double Greibach Normal Form, 1992, but I do not understand the proof at all.

Any CFG can be converted into CNF, so we try to prove that any grammar in CNF can be converted into GNF.

At first, a grammar H (not GNF, but can be easily converted into GNF by substitution and by removing rules containing empty string) is constructed from original CNF denoted G as follows:

  1) for rules Y → a
   $$ A \rightarrow  a[Y,A] $$
  2) for rules C → DQ $$ [D,  A] \rightarrow  Q[C,  A] $$
  3) $$ [A,  A] \rightarrow \epsilon $$

Than there are mentioned two statements about this new grammar. These statements are essential for the proof, because they show that the grammar H is equivalent to G. And I do not know why they are right:

  $$
([Y,A] \rightarrow^*_H w) \iff (A \rightarrow ^*_G Y w)
$$
  and
  $$
(A \rightarrow^*_H w) \iff (A \rightarrow ^*_G w)
$$

There is also written that these statements can be shown by induction. I tried to prove them but it seems to me that to prove one of them, I also need to prove the second. So I am stuck at cycle.

Could somebody please explain it to me?


texts: Find the size of the maximum cycle in a MPS

texts:
Consider the following problem to be solved in a distributed context:

  Find for each processor the size of the biggest cycle of which it is member.

My algorithm is the following (for synchronous MPS):

procedure findMaxCycleSize
cycle_size := 0
send(my_id, 1) to all my neighbors
for i:=1 to n do
    receive(id, size)
    if id = my_id then
        if size > cycle_size then
            cycle_size := size
        end if
    else
        send to all my neighbors except sender (id, size+1)
    end if
done

Analisys

$n+1$ rounds are enough, in fact a cycle can have size at most $n$, so the time complexity is $\Theta(n)$

Message complexity is very high, $O(n*n^n)$, this because every processor is responsible of at most $n^n$ message.
The best case is when every processor has degree exactly $2$ (ring topology) and we would have $O(n^2)$ messages.

The problem is that this algorithm is wrong, suppose the following case,

it will return for $p_1$ 5 but this is not true.

improvement #1
The first message has another field "destination node", so the processor can check if the message comes from the processor to which he initially forwarded the message

procedure findMaxCycleSize
cycle_size := 0
send(my_id, v, 1) to all v neighbors
for i:=1 to n do
    receive(id,v, size)
    if id = my_id then
        if sender_id is not v and size > cycle_size then
            cycle_size := size
        end if
    else
        send to all my neighbors except sender (id,v, size+1)
    end if
done

I have 2 questions:

Is my analisys correct?
How can I fix the algorithm to improve message complexity?


texts: Calculating integral without quadratures

texts: Is there any other options of calculating integral instead of using quadratures? I know that also we can calculate spline function or use monte-carlo method but do you know something else?


texts: Why the given statement can't be expressed using predicates and quantifiers in the way described in details?

texts:
Suppose there is a statement -

  Some students in this class has visited Mexico.

Solution given is: considering the universe of discourse for the variable $x$ consists of all the people. Our solution becomes $\exists{x}[S(x)\land{M(X)}]$ where the predicate $S(x)$ tells $x$ is a student in the class and $M(x)$ tells $x$ has visited Mexico.

The solution also tells $\exists{x}[S(x)\implies{M(X)}]$ is wrong because this expression is true when there is not someone in the class. So the statement can't be described in this way.

My questions is that only - What's wrong in giving true when there is not someone in the class (or true even when the someone is not student) ? Why exactly can't the statement be expressed using implication?


texts:
Assume that $x_1,\dots,x_n$ are $n$ integer variables which takes values in a subset of given numbers, say $x_i\in\{5,6,\dots,5000\}$. Let $f_i(x_i)$ and $g_i(x_i)$ both be non-decreasing non-negative functions of $x_i$. Values of both functions are given for all values of $x_i$. Now consider the optimization problem
\begin{align}\max_{x_1,\dots,x_n}&\sum_jf_j(x_j) \\\text{s.t.}&\sum_jg_j(x_j)\leq B&\end{align}where $B$ is a given positive constant. The straightforward solution is to do a brute-force search. However, this will be exponentially complex. Is this problem studied in literature? What are the known approaches to this? If you are familiar with solution approaches or relevant references, please point them out.


texts:
I need to prove or disprove that $L^* = L^*L^*$.
Intuitively, I know this is true, and I know I need to prove that $L^*$ is subset of $L^*L^*$ and that $L^*L^*$ is a subset of $L^*$.
But I am really struggling to prove that.


texts: Does $\mathsf{P} \ne \mathsf{NP}$ imply that $|\mathsf{NP}| > |\mathsf{P}|$?

texts: Is it possible that $\mathsf{P} \not = \mathsf{NP}$ and the cardinality of $\mathsf{P}$ is the same as the cardinality of $\mathsf{NP}$?  Or does $\mathsf{P} \not = \mathsf{NP}$ mean that $\mathsf{P}$ and $\mathsf{NP}$ must have different cardinalities?


texts: Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true

texts:
Given $S$ of positive integers $>$ $1$ is there some combination with even $SUM$ > $2$ that is NOT the sum of two primes?
$SUM$ = 10
$S$ = $[4,6]$
$No$,
Sum of Two Primes
$5 + 5 = 10$.
Combination $4+6=10$
It has an $O(1)$ algorithm if Goldbach is True (always output $NO$). Otherwise, it would seem to be NP-complete because it would require solving Subset-Sum.
Question
Will a many-one-reduction from $Subset-sum$ work for this decision problem in poly-time?


texts: Can any Mixed Integer Quadratic Program be approximately solved with Semi Definite Programming relaxation?

texts:
I understand that we can approximate solutions to Integer Quadratic Programming optimization problems containing just a positive semi definite matrix, as outlined here (i.e. the Q matrix):
https://learning-modules.mit.edu/service/materials/groups/116310/files/c33fb8f4-417a-46b2-9772-7c44b8912290/link?errorRedirect=/materials/index.html

However, I'm wondering if the Semi Definite Programming relaxation method extends to more general Mixed Integer Quadratic Programming problems that also contain a vector scalar product in the objective function, e.g. as described here:
http://www.orsj.or.jp/ramp/2014/paper/4-3.pdf


texts: Give context-free grammars that generate formulas in:

texts:
Give context-free grammars that generate formulas in propositional calculus, taking into account:

variables represented by single lowercase letter
Operations are conjunction (∧), disjunction (∨), negation (¬),implication (→) and double implication (↔)
Parse trees should reflect the following precedence order,
1: Formulas in parentheses
2: ¬
3: → and ↔
4: ∧,
5: ∨

My attempt led me to:

Create a set grammar
G = (V; E; R; S)

with V = {S, a, b, (, ), ¬,→, ↔, ∧, ∨},

E = {a,b,(, ), ¬,→, ↔, ∧, ∨},

R =
{S→ epsilon,

S→(a)|(b)|(ab)|¬a|¬b|¬(ab)|

S→(a→b)|¬(a→b),

S→(a↔b)|¬(a↔b),

S→(a∧b)|¬(a∧b),

S→ (a∨b)|¬(a∨b),

}


texts:
What data structure is best to use to facilitate a text search and a filter (by tag, for example)
Lots of sites support something similar: on StackExchange you can write in the search box
[tag] this phrase

which will search for the text this phrase in questions that have the tag [tag].
It is doing some type of text search and also returning filtered results.
I have implemented text search using a positionally inverted index, which is best stored as a B-Tree if the index will be updated frequently or a dictionary for the fastest possible retrievals.
What's the best way to implement a search + filter? Is it simply querying the index, then iteratively filtering all results? Problems I see with this: filtering is slow O(n) if sequential, still some kind of constant O(n/processors) speed and also unguaranteed order if parallelised.
Alternatively, could have a top-level map of { tag: indexes }, then it is O(1) to look up the index for a tag, and then the index will be queried for the text. The problem now is huge memory consumption (and I guess also the cost of building each index ahead of time)
I bet this problem has been solved before, what are the standard solutions and their benefits and costs?


texts: Is there a binary representation where the encoding distance grows with the arithmetic distance?

texts:
I need to binarily encode/decode small integers (around 10 bits), in such a way that the hamming distance of the encoded number grows monotonically with the (absolute value) arithmetic distance of the numbers.
Edit: the monotonicity doesn't needs to be absolute. There is probably a cost to pay breaking it, but the cost should be as low as possible. Is preferable to reduce the hamming distance at short scales, and if unavoidable, break it at larger scales.
For example:
The question is: Is there already such an encoding (better if it has error correction)?
I need to use it in python, so if there is already a python library to do the encode/decode, it would be perfect.
The "monotonically growing" requirement is a loose requirement. It is not strictly necessary. It just is convenient that the hamming distance reflects the arithmetic distance in some way.
The hamming distance can be replaced wit some other measure of encoding distance, like Jaccard distance.
The requirement is that close integers share most of their binary encoding, and still there is error correction.


texts: Are the words "expression" and "term" interchangeable in programming language theory?

texts: When describing the syntax of a given programming language the words "expression" and "term" are often used to seemingly describe the same things. Are these words interchangeable in the context of programming languages?


texts:
I am trying to understand how to prove that a polynomial will always grow faster than a logarithm.

$\log n = o(n^\epsilon), \epsilon>0$

Intuitively, it is obvious, and plugging in a few numbers always yields true, but how can I prove this?

Maybe this can be done inductively (I would prefer this method if someone would explain it), but I attempted to prove through the use of derivatives and L'Hôpital's rule, namely:

$\lim_{n\rightarrow\infty}\frac{\log n}{n^\epsilon} = \lim_{n\rightarrow\infty}\frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}}$ = 0

Is this getting me in the right direction to prove that the upper bound of $\log n$ it is strictly less than $n^\epsilon$?


texts: Runtime analysis of prime-set computation

texts:
I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is :

we are maintaing a one pointer from node $i$ of the list $L$ to index $i$ of array $N$ and one pointer from index $i$ of $N$ to $i$th node of list $L$. We will use a doubly linked list in such a way that we mark each element of $N$ exacly once.

Pick the smallest unmarked element $i \ge 2$ in $N$ and add $i$ to $Q_{k-1}$.
Starting from the first node, walk up the list $L$ in increasing order until we find the smallest number $r$ in it such that $r\cdot i \ge k-1$.
Walk down the list $L$ (crucially, in decreasing order) from the node $r$, and for each $l$ in $L$, seen, mark the element $N[i\cdot l]$ and delete the node containing $i\cdot l$ from $L$ ( this node in $L$ is accessed through the pointer from the $(i\cdot l)$th location in $N$ ).
If $N$ has any unmarked element $\ge 2$, go back to first step

In the first round all the multiple of 2 will get marked. It is easy to verify that each element in the array will get marked just once.

  Question : How to show that above algorithm has Running time $O(k)$?

After first iteration all multiples of 2 will be marked in the array $N$ and all multiples of 2 will be removed from the list $L$. In the second iteration multiples of 3 and so on.

$$
\begin{align*}
\text{Total time}: &= c_1k + c_2\frac{k}{2} +c_3\frac{k}{2 \times 3} +c_4\frac{k}{2 \times 3 \times 5} + c_5 \frac{k}{2 \times 3 \times 5 \times 7}+\cdots\\
&=k \left(c_1 + c_2\frac{1}{2} +c_3\frac{1}{2 \times 3} +c_4\frac{1}{2 \times 3 \times 5} + c_5 \frac{1}{2 \times 3 \times 5 \times 7}+\cdots \right) \\
&= O(k)
\end{align*}
$$

Reference : link


texts: Capture Avoiding Substitution of multiple variables at once

texts:
In articles you often find the terminus "capture avoiding substitution" that saves the author(s) from the tedious process to re-define a recursive function -including alpha-conversion and the invention of fresh names- in the discussion of dynamic semantics. The terminus is well understood by the readers and somewhat standard.

In order to provide an easy-to-read semantics, I recently defined a group of multiple recursive functions as a map from identifiers to (lambda-) terms. Application of one of these recursive functions then requires to substitute all free occurrences of its "siblings" in its body. It seems quite natural to introduce a generalization of substitution with partial functions instead of the usual univariate meta-function.

As an example consider the following group:

let rec fac n = if n <= 1 then 1 else n * (fac (n-1))
and foo n = fac n

in let fac = 5 in foo fac

This gives a two-element partial function, where each right-hand side is mapped to the recursive group with its body:

$\sigma = \left\{(\mathtt{foo} \mapsto \lambda \mathtt{n}. \mathtt{let\ rec\ ... in\ fac\ n}), (\mathtt{fac} \mapsto \lambda \mathtt{n} . \mathtt{let\ rec ...})\right\}$

This substitution is then applied to the body of the let-rec. It should first rename the bound variable fac, since it occurs freely in the codomain of the partial function i.e.

... let fac0 = 5 in foo fac0

Then, the substitution should replace any mapped variable at once:

... let fac0 = 5 in ((let rec fac = ... and foo = ... in fac) fac0)

When I generalize this, I cannot assume that the right-hand terms are recursive definitions. Any term might occur on the codomain. In particular, they could contain free variables that are bound by the substitution itself. Therefore, the order of replacements matters: I need to ensure that a replacement is not immediately subject to substitution again. This can, of course be defined, but I'd rather just use a sentence similar to the one mentioned above.

Is there a standard definition of capture avoiding substitution of multiple variables?


texts:
Suppose I have 2 possible algorithms: one runs in O(m+n) and the other runs in O(mn). Suppose also that the task is performed on a connected graph with m edges and n vertices. No other information is given about the graph. How do I know which algorithm is faster?

EDIT:
I don't think my question is a duplicate of the question quicksort refers to since that question asks for a definition and I'm asking for a calculation. I did search for a solution before I posted but couldn't find any sufficient solution to my question.


texts: Generating all equal-sized set partitions

texts:
Minor disclaimer: This is my first question here, so I hope it is the
right place to put it.

Question: Is there an algorithm to exhaustively generate all set
partitions of equal size? That is, I want to list all possible ways to
divide a set of $N$ elements into $K$ parts where each part has the same
size $\frac{N}{K}$. At best, I want to generate all of these partitions
sequentially without generating any duplicates. There are many
algorithms to list all divisions of a set into $K$ parts that however do
not impose a size constraint on the parts. But I have not found anything
on generating set partitions of equal size.

I assume that the elements in the set are labeled using labels $1, ...,
K$. For $K = 2$ groups, I can exhaustively list all partitions by
sequentially generating all permutations of the group labels in
lexicographic order and stop as soon as the first element is $2$ [that
is assuming I started with the initial partition $(1, 1, 1, ...., 2, 2,
2)$]. However, for $K > 3$ generating permutations of the labels does
work anymore without generating duplicate partitions.


texts: determine if a turing machine halts in less than n step, in less than n step

texts:
I would like to know if there is a turing machine which can do the following:

take as input a turing machine T and integer n:
return true if the turing machine halts before time n and false otherwise

Clearly such a TM (turning machine) exists. Take the TM that simply runs T for n steps, then if it has halted return true and return false otherwise, however what I would like to know is if there exists a TM that can do better than this. I'm not sure how to formalize this question exactly. so hopefully it is clear what I am asking. Thanks


texts: How to describe an algorithm whose input size diminishes by 1 for each iteration

texts:
To elaborate on the title: I have a recursive algorithm whose input is reduced by 1 for every iteration until the input size is 1.

1st iteration: n

2nd iteration: n-1

3rd iteration: n-2

4th iteration: n-3

.

.

.

nth iteration: n-(n-1)

How can I describe this in asymptotic notation?


texts: Checking if there are 2 elements in an array that sum to X in O(n lg n)

texts:
I have thought about the most useful way of checking an array for 2 elements that sum to X.
The trivial solution is to check the sum of every element with every element, and the complexity of this solution is $O(n^2)$.

My solution is:
Say the array is A.
It's length is N.
Elements are from A[0] to A[N-1]

Pseudo-Code is:

Check_Sum(A,left,right) {
  mid <-- floor( (left+right)/2 )

  if(A[left]+A[right]=X)
    return true

  return Check_Sum(A,left,mid)||Check_Sum(A,mid,Right)
}

My question is: Is the complexity of my solution equal to $O(n \lg n)$?


texts:
Earlier, I asked a question defining disruption in Genetic Algorithms. Given that definition, I'm still confused on how to answer the following question.

  True or false? For  1-point  and  2-point  crossover,  the  schemata
  which  have  bits  that  are  close  together  on  the string encoding
  are more likely to be disrupted by crossover.

From my understanding of cross-over disruption should only be dependant on the number of matching bits strings between parents. So 1001 would be more likely to be disrupted by 0110 then by 1000. So I answered false, but their justification was that bits closer together encourage disruption, which I don't totally understand.

I'm assuming that "bit distance" can be defined as the number of zeros between sequential bits, but based on my proof above, I really don't see how this could affect disruption. Alternatively, I could consider "bit distance" as being the number of bits to flip to reach from one number to another, but based on my proof above, the greater the distance, the greater the chances of disruption.

Where is the mis-understanding between the official answer and my own?


texts:
I have been assigned a homework problem that I cannot figure out:

  Prove that SAT has a polynomial-time reduction to the language of undirected non-negative weighted graphs with simple cycle of weight less that or equal to w.

This bears a resemblance to the all-pairs shortest path problem which has polynomial-time algorithms, but I've read multiple times that this problem is np-hard (plus, I suppose it would be a cruel trick to give such an assignment).

Starting from hamcycle, I have managed to produce a reduction for several variations on this problem (e.g., tsp, longest positive path, shortest negative path), but whenever it comes to this language I can always come up with a counterexample that invalidates my attempt at a reduction.

So, is there a reduction from SAT?  What am I missing?


texts: What is the difference between superposition and paramodulation?

texts:
I am currently writing a paper about automated theorem proving in first-order logic. Equality is not uncommon for mathematical problems and almost every theorem prover like VAMPIRE or SPASS has a calculus for equality. But the most paper are always writing about the term "superposition" calculus. A simple google search did not help to find any information about this term, only the wikipedia website which means "it can be used for first-order logic with equality".

Another paper referneced to the Paramodulation-based theorem proving which describes the concept of paramodulation for theorem proving. It seems that the superposition is some modified version of paramodulation, but I don't understand why and in which way.

So, is there any explanation of this calculus or can someone give me some hints what is different from paramodulation?


texts: When would the worst case for Huffman coding occur?

texts:
I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the frequencies of the characters present in the input text, I believe the answer is also going to be related to that.

This is what I got from wiki.

The worst case for Huffman coding can happen when the probability of a symbol exceeds 2^(−1) = 0.5, making the upper limit of inefficiency unbounded.

So if a character appears more in our input text, would it ensure good or bad compression? According to wiki, if the probability of symbol exceeds 0.5 (meaning that if a character appears more in our input text), it would be produce bad compression. But from what I understand, in Huffman coding, the more a character appears, the more better it is for us to get compression right?

Well anyway I just want to know in which type of files or text data, our Huffman coding would get bad compression. Maybe I am overthinking, but a little help would be great.

Thanks.

P.S: I don't think this question is subjective, I know that there is a specific answer to it. All I want is a worst case, I don't presume it's subjective?


texts: What kind of growth is $O(0.24\cdot K\cdot 2^w)$

texts:
I've calculated the running time of an algorithm I'm interested in to be

$$O(0.24\cdot K\cdot 2^{w})\,,$$

where $K$ and $w$ are both variables.  ($K$ is the number of elements in some set, and $w$ is the log of the largest element, so both are variables.)

What kind of growth does this function have? I'll say it is exponential, however I don't know what the 0.24 implies.


texts: What is the difference between ADTs and ASDLs?

texts:
ASDL stands for Abstract Syntax Description Language (ASDL), whereby ADT stands for Algebraic data type.

By looking at Python.asdl it appears to me to be the same thingy, just with different names, which I highly assume is wrong.

Can anyone explain what the difference is?


texts: R-Tree multipath search - remember the path?

texts:
R-Trees can take several paths to retrieve an item because of overlaps in data being indexed or index structure. However, if we run the same search many times on the same unmodified structure, can we remember the correct path and avoid taking the wrong path?

Maybe caching the correct path? But I'm not so sure that R-Tree implementations do this or that R-Trees fully loaded in memory do this either.


texts: Converting regular (Type-3) grammar to a deterministic finite state automaton

texts:
I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to convert RG to DFA.

G = ({S,A,B},{a,b},P,S)
P = {
S -> aA | bB,
A -> aS | a,
B -> bS | b
}

I have found these rules that convert RG to a finite automaton (which might not be deterministic if I think correctly).

1. δ(B, a) = C if B → aC ∈ P
2. δ(B, a) = K if B → a ∈ P
   K ∈ F
3. δ(K, *) = emptySet
   i.e. q0 ∈ F, if S → ε ∈ P
   I dont understand rule 3

Now I am using these rules on G this way.

A -> aS
becomes
δ(A, a)=S
according to
1st rule

A -> aS
becomes
δ(A, a)=K
according to
2nd rule

Now I already have

δ(A, a)=S
δ(A, a)=K

which means the automaton is not deterministic because

δ(A, a)={S,K}

Am I doing something wrong?


texts: Grouping a group of people by their preferences

texts:
I have following problem to solve:

I have a group of people which I have to split up into smaller groups. Some of them have preferences who they want to be in a group with and who they don't want to be in a group with. I have to determine wether it is possible to group them respecting their preferences and if so, I want to build the groups. So for example I have these people:

Tom: wants to be in a group with [Stephen, John], doesn't want to be in a group with [Jennifer]

Stephen: wants to be in a group with [John]

John: wants to be in a group with [Jennifer], doesn't want to be in a group with [Alice]

Jennifer: no preferences

Alice: wants to be in a group with [Tom]

The example above wouldn't work because Tom wants to be in a group with Stephen, Stephen wants to be in a group with John, John wants to be in a group with Jennifer, however Tom doesn't want to be in a group with Jennifer, so it couldn't be solved while respecting all preferences

Another example:

Tom: wants to be in a group with [Alice], doesn't want to be in a group with [Jennifer]

Stephen: no preferences

John: wants to be in a group with [Stephen], doesn't want to be in a group with [Tom]

Jennifer: wants to be in a group with [Stephen]

Alice: doesn't want to be in a group with [Jennifer]

This example would work with the following groups respecting all preferences: [Tom, Alice];   [John,Stephen,Jennifer]

I have been fiddling with this problem for some time now but I can't think of a solution and I also can't find any problem on the internet similar to mine although I am pretty sure that there is a popular problem similar to this one.

I still want to solve this myself, however I would be very happy if you could tell me if there is a popular problem similar to this one or if you could provide me with any hints for an approach that I could take to solve this.


texts: Finding a Hamilton path in a Complete Euclidean Graph is in P

texts: How is it possible to prove that this assert is not true?


texts: How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?

texts:
Suppose we have a simple Bayesian network with two rows of nodes:  $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$.  Each node $x_k$ takes a state of either 0 or 1 with equal probability.  Each node $y_k$ takes state 1 with probability $p_{k,0}$ if $x_k$ is state 0 and probability $p_{k,1}$ if $x_k$ is state 1.

Is exponential time required to compute the probability that all $y_k$ are 1?  Please provide a proof either way.


texts: Everyone keeps claiming that integer factoring is in $NP$ but I just don't get it... Even with the simplest algorithm (division with all integers up to $\sqrt{n}$) the complexity should be $\sqrt{n}\log(n)$... How is that not in $P$? Is there something I'm missing?


texts: Constrain traveling salesman: visit a given city within a given distance from start

texts:
I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say 100) from start. Is there a way to do this? My question is related to this unanswered CS question.

I have a mixed integer program using the R package CVXR that find the shortest route without subroutes (see below). The city order is represent in the vector node_order. The strategy I've pursued so far is:

Re-organize node_order so that the index is the order and the value is the city id
Look up the associated distances in distances
Compute a vector with the cumulative sum of these distances.
Add the constraint that city i must occur before the first index in (3) exceeding the distance constraint for that city.

The issues I've encountered with this approach is that I have not found a way to include finding-index-by-value into the optimization in CVXR. This is needed in both step (1) and (4) above. Maybe this is possible after all, or there is another approach? I am willing to use other packages than CVXR and other software than R.

Current program

library(CVXR)

# Make distances
N = 10
distances = matrix(1:(N*N), ncol = N)

# Flag 1 iff we travel that path. 0 otherwise
do_transition = Variable(N, N, boolean = TRUE)

# Minimize the total duration of the traveled paths.
objective = Minimize(sum(do_transition * distances))

# Only go one tour. Order is 1:(N-1)
node_order = Variable(N-1, integer = TRUE)
ii = t(node_order %*% matrix(1, ncol = N - 1))  # repeat as N rows
jj = node_order %*% matrix(1, ncol = N - 1)  # repeat as N cols

# Constraints
constraints = list(
  do_transition * diag(N) == 0,  # Disallow transitions to self (diagonal elements)
  sum_entries(do_transition, 1) == rep(1, N),  # Exactly one entrance to each node
  sum_entries(do_transition, 2) == rep(1, N),  # Exactly one exit from each node
  (jj - ii) + N * do_transition[2:N, 2:N] <= N - 1,  # One tour constraint (no subtours)
  node_order >= 1,   # This interval represents order as ranks (1 to N-1)
  node_order <= N-1
)

# Find optimum
solution = solve(Problem(objective, constraints))

Unsuccessful attempt

A bit of code pertaining to my current (unsuccessful) attempts:

# Get tour order
#tour = order(c(NA, result$getValue(node_order)))  # R solution
tour = rep(NA, N-1)
tour[result$getValue(node_order)] = 2:N

# Get tour distances
distances_optim = diag(distances[tour, tour[2:N]])

# Tour cumulative distances
distances_cumul = cumsum_axis(distances_optim)


texts: Combine all known ML algorithms into one through Bayes

texts:
Let there be an infinite series of pieces of data we want to predict. Take the set of all algorithms ("hypotheses") ML has discovered; different hyper-parameters count as another algorithm. Give each algorithm a score ("relative prior probability") of 2^(-number of bits to specify algorithm, still including hyper-parameters). For each piece of data, ask each algorithm to predict its value, then reveal the true value. Multiply each algorithm's score by the probability it assigned to the true value. (For probabilities, renormalize.)

Under what assumptions does this converge to the highest-scoring algorithms predicting correctly? If one of the algorithms knows enough about the series to give the best-scoring possible answer, this will converge. If the series is generated by predicting our algorithm and using the data that favors the underdog, this won't converge.

Why isn't there a tool out there that approximates this to let people build classifiers without knowing what algorithms and hyper-parameters to use, if they accept an initial period of overfitting? How long would that period be?


texts: How do you "time" the measure of binary streams?

texts:
This is just something I've been wondering just out of curiosity. I apologize if this doesn't fall under the category of this forum, and if so feel free to divert me :)
Whenever a computer does anything, it always handles a sequence of bits. My question is: how does it actually measure what bit goes in what place? I'm curious of the electric current that gets sent into the transistors, and how these are actually placed correctly in the binary stream. I understand the concept of the transistors and how a threshold voltage determines whether or not a bit is 0 or 1, but how are these bits actually placed in sequence?
Say if we have a binary sequence of 00010010001. How does whatever component handling this stream know how "long" it has to wait with no current before it places a 0-bit, and then moves on? According to my understanding, for the first three 0-bits, there will be no current going into the transistors. But does it have to "wait" for a set amount of time before it determines that a single bit is 0? I'm generally just confused as to how a computer knows the difference between a single 0-bit, and (for example) 10 different 0-bits. When does a computer know to set another bit?. Appreciate any feedback! :)


texts: What does "deterministic" mean in the context of memory management?

texts:
At the time of writing, Wikipedia describes determinism as:

"a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states"

That aligns with my interpretation of determinism as a natural scientist.

If a program contains a benign race condition and its control flow varies depending upon the outcome of the race, is it deterministic? I would say not. However, many people describe thread-safe reference counting, such as shared_ptr in C++, as deterministic even though threads race to decrement the reference count to zero and the winner is responsible for executing the destructor.

The Wikipedia page about garbage collection lists determinism as an advantage of reference counting compared to tracing collection and determinism is also referred to here. On the other hand, people have blogged rants explaining why this is wrong.

So what does "reference counting is deterministic" mean, if anything?


texts: Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free?

texts:
I'm trying to show that $L=\left\{w^rww^r:w \in \{0,1\}^*\right\}$ is not context free using the pumping lemma.

I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but someone told me I might want to consider another string. Why is this? Any way in which I divide the string and then pump the string results in the balances between the $w^r$on either side of the string being thrown off, no?


texts: "Archiving" byte sequence into human-readable set of chars

texts:
Ok, lets assume we  have sequence of  1000 bytes.
So the possible  number of value variations is 2^100.

Is there a way to "index" each variation with letters and decimal numbers (A-Z, 0-9), having as shortest length as possible?

So the person can dictate sequence of letters and numbers by phone and it can be recreated into bytes on the other side.

Im really bad at math, and found how to shorten that string up to about 100 symbols. Any way to di it shorter?


texts: Find pairs of integers (a, b) in an array such that a = b + k in linear time - elements are not unique

texts:
A while ago, I was asked to solve a question similar to this:

  We are given an array arr and we would like to find all pairs of items (a, b) where a = b + k. The items are NOT unique and it is also possible to have k = 0.

I know that if items are unique, this problem can be solved in linear time by using a hashmap. However, when items are NOT unique, I think that the problem becomes very different.

See this example:

arr = [1, 1, 1, 1, 1]
k = 0

The expected output is:

(1, 1), (1, 1), (1, 1), (1, 1) // For the first element
(1, 1), (1, 1), (1, 1)         // For the second element
(1, 1), (1, 1)                 // For the third element
(1, 1)                         // For the fourth element

As it is obvious to me, in the worst case (the above example) the output is of size $n \choose 2$, which is $\Theta (n^2)$. How is it possible to have a linear algorithm, when the output size is definitely $\Theta (n^2)$?

My interviewer insisted that it is possible to still solve it in linear time, if the correct data structure is used.


texts: Two-State Turing Machine for Parenthesis Matching

texts:
In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet (symbols), you can reduce the number of states down to only 2.

I was looking for examples of different Turing Machines and a common example presented is the Parenthesis matcher/checker. Essentially it checks if a string of parentheses, e.g (()()()))()()() is balanced (the previous example would return 0 for unbalanced).

Try as I may I can only get this to be a three state machine. I would love to know if anyone can reduce this down to the theoretical minimum of 2 and what their approach/states/symbols was!

Just to clarify, the parentheses are "sandwiched" between blank tape so in the above example
- - - - - - - (()()()))()()() - - - - - - - would be the input on the tape. The alphabet would include (,),1,0,-, and the *halt* state does not count as a state.

For reference the three state approach I have is as follows:
Description of states:

 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X

Transitions Listed as:

Action: State Symbol NewState WriteSymbol Motion

// Termination behavior
Action: s2 - *halt* 0  -
Action: s1 -  s3    -  r

//Transitions of TM
Action: s1 (  s1  (   l
Action: s1 )  s2  X  r
Action: s1 X  s1  X  l
Action: s2 ( s1 X  l
Action: s2 X  s2 X r
Action: s3 (  *halt* 0 -
Action: s3 X  s3     X r
Action: s3 -  *halt* 1 -

Forgive the informal way of writing all this down. I am still learning the theoretical constructs behind this.


texts: What changes do I need to make to my algorithm to make this scene from a different angle?

texts:
The code below is in F#. It creates a scene which looks like a perspective coming from the top left. I thought if I would change i % j = w then it would come from the top right instead, but that doesn't work. So what change do I need to make for it to be able to come from the top right, bottom left, bottom right and even the top centre?

open System

let w = Console.WindowWidth
let h = Console.WindowHeight

for i in 1 .. w - 1 do
    for j in 1 .. h - 1 do
        Console.SetCursorPosition(i, j)
        if i % j = 0 then printf "."

Console.Read() |> ignore

Here is what the program looks like.

 .......................................................................................................................  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
     .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .
      .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .
       .      .      .      .      .      .      .      .      .      .      .      .      .      .      .      .      .        .       .       .       .       .       .       .       .       .       .       .       .       .       .
         .        .        .        .        .        .        .        .        .        .        .        .        .
          .         .         .         .         .         .         .         .         .         .         .
           .          .          .          .          .          .          .          .          .          .
            .           .           .           .           .           .           .           .           .
             .            .            .            .            .            .            .            .            .
              .             .             .             .             .             .             .             .
               .              .              .              .              .              .              .
                .               .               .               .               .               .               .
                 .                .                .                .                .                .                .                  .                 .                 .                 .                 .                 .
                   .                  .                  .                  .                  .                  .
                    .                   .                   .                   .                   .
                     .                    .                    .                    .                    .
                      .                     .                     .                     .                     .
                       .                      .                      .                      .                      .
                        .                       .                       .                       .
                         .                        .                        .                        .
                          .                         .                         .                         .
                           .                          .                          .                          .
                            .                           .                           .                           .
                             .                            .                            .                            .


texts: Finding the k-shortest path between two nodes

texts:
Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-shortest path, the $3^{rd}$-shortest, and so on.
Questions:

Is there an efficient algorithm to get the i-th-most-shortest-path between two nodes in a weighted graph?
Is there an efficient algorithm to get the k-most-shortest-paths between two nodes in a weighted graph?

An answer to either one is OK, though I wonder if an answer to the second question can be done more efficiently than $k$ calls to an answer to the first question.


texts: Prove that half(L) is also regular if L is a regular language

texts:
Given a regular language $L \subseteq \sum^*$ prove that the language

$half(L) = \{w \space | \space ww \space \in \space L \}$

is also a regular language.

--

Please give a hint or two. Have thought about it a lot already.

--

While trying to make one for $half(L)$, I came up with a DFA which uses the DFA for $reverse(L)$, but that one, it turns out, accepts a different regular language called $reflect(L) = \{w \space | \space ww^R \in L\}$. The idea was to make a DFA by first making an NFA using the standard "first reverse transitions, add new start state, make previous start state the sole accept state, etc." technique. Then we make a DFA where the states are a pair of the states of the original DFA and this reverse(L) DFA's states. However, I won't digress into that because this doesn't accept $half(L)$.


texts: Lower bound the difference between distinct values of a function over a discrete domain?

texts:
I have a function $f: X \to \mathbb{R}$ where the domain $X$ is a (small) discrete set, such as $X = \mathbb{Z}^d \cap [-10,10]^d$ (i.e., the set of $d$-dimensional integer vectors all of whose coordinates are in the range $-10..10$, inclusive).

I'm interested in computing a non-trivial lower bound on the value of

$$\min_{\substack{x_1 \neq x_2 \\ x_1,x_2 \in X}} \big|~f(x_1) - f(x_2)~\big|$$

One possible approach is exhaustive search. Say there are $N = |X|$ distinct elements in the domain. Then I would compute $f(x)$ for each $x \in X$, and then calculate the difference between the $f(x_1)-f(x_2)$ for each pair of distinct values $(x_1,x_2) \in X$. This would require $N$ evaluations of $f$ and $N(N-1)$ operations between the values.

My questions are:

Has someone has seen this type of problem before. I'd like to find out more about related problems, but I just don't know what are the right terms to look for in the literature.
Is it possible to do better by exploiting properties of $f$? I'm looking to compute the "minimum difference in function values" for a functions such as $\log(1+\exp(-s^Tx))$ (i.e., convex, continuous, monotonically decreasing in $s^Tx$ where $s \in \mathbb{R}^d$; this is the logistic loss function that is optimized in machine learning applications).


texts: Why is reflexivity enough in this HoTT formulation of quotient types?

texts:
In this formulation of quotient types in cubical type theory I was able to implement an eliminator and use that to implement basically curried function application. However, in all this, the only requirement on the factoring relation is that it is reflexive.

I find this surprising. I would have expected transitivity and symmetry to also be needed somewhere along the way. Is there an intuitive explanation for why reflexivity is enough?


texts: Separation guarantee in Goemans Williamson algorithm

texts:
In the original paper in Goemans-Williamson paper for max-cut, we need to sample a random vector r and
we output
$$
S = \{i : r^{T}x_{i} \geq 0\}
$$
where $x_{i}$ are column vector of a feasible solution of the SDP relaxation.

My question is are we guaranteed that there exists a certain $r$ such that the output is max-cut ?


texts: Combinations (repetition not allowed & order not important)

texts:
How to compute a table of numbers (all possibilities), where repetition is not allowed and order is not important.
Example:
I have a set of prime numbers. In this example I have four: {3,5,7,11}, but it can be anything, and I want to choose every pair out of that set.
To make things easier, I want to compute the indices to get those pairs of prime numbers. The set of indices is then {0,1,2,3}. We pick 2 out of 4 elements. So how do we compute the permutations or combinations:
0,1   (3,5)
0,2   (3,7)
0,3   (3,11)
1,2   (5,7)
1,3   (5,11)
2,3   (7,11)

?
It was difficult to find examples on the web, because they either allowed repetitions or were order was important. Pls answer with pseudocode or c/c++ if you can.


texts: why DFA to regex by two different methods differ

texts:
I was learning converting DFA to regex.
I came across Arden's method which solve given DFA as follows:

Ardens method

Let us form the equations

$q_1 = q_10 + q_30 + є$

$q_2 = q_11 + q_21 + q_31$

$q_3 = q_20$

Solving the eq_uations

$q_2 = q_11 + q_21 + (q_20)1 = q_11 + q_2(1 + 01)$

$q_2 = q_11 (1 + 01)^*$

So, $q_1 = q_10 + q_30 + є$

$q_1= q_10 + q_11(1 + 01)^*00 + є$

$= q_1(0 + 1(1 + 01)^*00) + є$

$= є (0 + 1(1 + 01)^*00)^*$

$q_1=(0 + 1(1 + 01)^*00)^*$

So the regular expression for the given automata is $=(0 + 1(1 + 01)^*00)^*$

When I solved above using state reduction method I got different answer:

State Reduction method

So final regex was $0+11^*0(11^*0)^*0$

However this is different from what we get from Arden's method. Am I making any mistake?
Or both are correct?
If correct, is there any way to get same regex as Arden's using state reduction?
Does Arden's method gives shortest regex?
Any other observations about two methods?