texts: How to decrease the confidence of a Monte Carlo algorithm in its answer?

texts:
Recall that a Monte Carlo algorithm is $p$-correct if it outputs a correct answer with probability at least $p$. In the case of decision problems, where the answer is binary, repeating the MC algorithm can increase the confidence that a correct answer is obtained.

However, in the case where more than 1 possible answer is correct, this confidence can actually decrease. I'm wondering how many times $k$ does such an algorithm have to be run to obtain a confidence in the answer that is less than 50%.

Here's what I've done:

Suppose that $k=3$ and I have a 75%-correct MC algorithm that outputs 5 possible answers, 4 of which are right, and 1 is wrong. I think in this case, the 75% "correctness" of the algorithm is split between all possible right answers, such that each correct answer has a "probability" of 75%/4.

Suppose the right answers are $a, b, c, d$ and a wrong answer is $e$.

In this case, if I list all possible combinations of outputs of an MC algorithm that I run $k=3$ times, I get a list of tuples $(a, a, a)$, $(a, a, b)$... and so on, each of which is associated with a probability of occurring. So for instance $(a, a, a)$ has probability $(0.75/4)^3$ of occurring and $(a, a, e)$ has probability $(0.75/4)^2 * 0.25$.

So if I build a table associating each possible tuple to its probability of occurring, and sum the probabilities of all events where the algorithm would output the correct answer by majority voting (ties are split by choosing randomly), this should give me the final "confidence" of the algorithm. In this case, I get numbers around 0.65-0.75 (because of the randomness in tying splits).

However, I haven't been able to find a $k$ that gets this value to below 50%.

Any ideas if I'm doing something wrong? Help is much appreciated.


texts: Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., with states going to a looping non-final state whenever there are no possible words to be made beginning with the letters you have already gone through. Then make every state that ends on a word final.


texts: A heuristic for finding a disjoint set of representatives

texts:
This is my problem:

There are n collections of M geometric shapes (not necessarily disjoint).
Pick a single shape from each collection,
     such that the n selected shapes are pairwise interior-disjoint.

This problem is NP-complete even when the shapes are restricted to axis-parallel squares (see this cstheory.SE question ). The naive algorithm is to check all $M^n$ combinations in the cartesian product. Assuming we can check intersection of two shapes in time O(1), the naive algorithm takes time $O(n\cdot M^n)$. What heuristics can be used to reduce the run-time?

NOTE: About 2 months ago I asked a related question, in which there is only a single collection of candidate shapes. In that case, I used a geometerically-based divide-and-conquer heuristic, combined with branch-and-bound as recommended by D.W. Careful tuning lead to a dramatic reduction in run-time (50-80 times faster).

However, I don't see a way to use divide-and-conquer in the current problem. I can partition the collections, but, a disjoint set in one partition won't necessarily be compatible with a disjoint set in the other partition (the sets might contain shapes from the same collection...)

Can you suggest any heuristics, either divide-and-conquer or otherwise, for solving this problem more efficiently?


texts: Is there an equivalent of "control flow" in deep learning systems?

texts:
Traditional programs work significantly through control flow. I know that there are simple algorithms that have no control flow at all (i.e. they just perform a fixed sequence of executions), but I cannot imagine anyone building a large complex program without any control flow.

However, as far as I understand, there is no control flow in standard deep learning systems. They execute the same calculations for every input.

Are there deep learning/NN-based systems with something similar to control flow?


texts: Is an NP-hard problem which is in NP is NP-complete?

texts:
I'm reading Combinatorial Optimization book by Bernhard Korte and Jens Vygen. There's a part that they said:

It is an open question whether each $NP$-hard decision problem $A \in NP$ is $NP$-Complete, because of the difference between polynomial reduction and polynomial transformation.

I understand that, but when I read wikipedia article about NP-complete, I see this picture
According to wikipedia, a decision problem is $NP$-complete when it is both in $NP$ and $NP$-hard, which make me confused. Can someone help me understand the difference between the book and wikipedia?

Definition 15.15. Let P1 and P2 = (X, Y) be decision problems. Let f : X → {0, 1} with f (x) = 1 for x ∈ Y and f (x) = 0 for x ∈ X \ Y . We say that P1 polynomially reduces to P2 if there exists a polynomial-time oracle algorithm for P1 using f
Definition 15.17. Let P1 = (X1, Y1) and P2 = (X2, Y2) be decision problems. We say that P1 polynomially transforms to P2 if there is a function f : X1 → X2 computable in polynomial time such that f (x1) ∈ Y2 for all x1 ∈ Y1 and f (x1) ∈ X2 \ Y2 for all x1 ∈ X1 \ Y1.


texts: Enumerate all paths of length 3 in a given tree T

texts: Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.


texts: Minimum cost circulation problem with bounded number of edges

texts:
During an article I am writing, I encountered the following problem:
Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:E\to R$ and an integer capacity function $C:E \to N$.
Find a circulation $f$ with minimal cost $W(f)$ such that the number of edges used by the  circulation (i.e., edges $e$ s.t. $f(e)> 0$) is smaller than or equal to a parameter $r$.

Note that if $r=|E|$, the problem is simply the well-known circulation, which is solvable in  polynomial time.

I tried to search "Google Scholar" and use variations of the cycle  canceling (and other min cost flow) algorithms to solve the problem but with no successes.


texts: How would one prove the pigeonhole principle with a SAT solver?

texts: Suppose I wanted to find a proof of the pigeonhole principle or show that no  proof shorter than $L$ exists. I understand that proof-checking is in NP, so I could write a CNF formula that is satisfiable iff. such a proof exists. What I want to know is, how exactly would one do that? I understand I would assume a set of axioms about sets or something and also the axioms of first-order predicate calculus, and probably also modus ponens and stuff... but how exactly does one do something like this? Can anyone give a construction of such a CNF formula? References to papers or general explanations would be appreciated.


texts: Pros and cons of representing strings as lists of characters

texts:
I am writing a compiler for my programming language (both almost complete), but they are stuck in the, I would call, "String vs List-of-Char dilemma".
Maybe some more experienced compiler programmer could help.

It is a functional, strongly typed (with inference) and almost pure (immutable vars) language.
As I could perceive, using a list of chars is better for simplicity/generality of the language. But it adds complexity to the runtime/stdlib, because the user may require sometimes to print a List-of-Char as a text and sometimes as a list.

Perhaps a built-in function just to print a List-of-Char as text would be a good compromise? I may be missing something here.

In the other hand, defining a "String" type different from "List", requires duplicity of all list functions like "head", "tail", "replace" etc. to preserve the soundness and simplicity of the type system. It also requires duplicity from the user when implementing similar methods.

Perhaps a built-in function just to convert a List-of-Char to String and vice-versa would be a good compromise? I may also be missing something here.

obs.: The code is in github if anyone has interest into delving in the problem.


texts: Proving a language is not context free using the Pumping Lemma

texts:
To prove that $L=\{0^m1^n|n \text{ divides } m,\text{ } m,n\gt0\}$ is not a CFG, I applied the pumping lemma. I chose $w=0^{21p}1^{7p}$ for the pumping constant p. By the pumping lemma, $w=xyuvz, |yuv|\leq p, |w|\geq p, |yv|>0, xy^iuv^iz \in L \forall i>0$

Take $i=0$ then consider 3 cases:

Case 1:$yuv$ is only a substring of $0s$.

Then $w'=0^a1^{7p} \text{ with } 21p>a\geq 20p$. In this case, $a$ is not divided by $7p$

Case 2:$yuv$ is only a substring of $1s$.

Then $w'=0^{21p}1^{b} \text{ with } 7p>b\geq 6p$. In this case, $21p$ is not divided by $b$

Case 3:$yuv$ contains both $0s$ and $1s$.

Now I am quite sure this also works when $yuv$ includes both $1s$ and $0s$.
We get $w'=0^{21p-a}1^{7p-b} \text{ with }p>a>0, p>b>0 \text{ and } p\geq a+b$.

I just can't figure out how to formally state how a contradiction arises from case 3. How can I prove that case 3 also fails? Thanks!


texts: Reduction PSPACE language to DSPACE(O(1))

texts:
We have a language $L \in PSPACE$.  Is it possible to reduce it with $f \in LOGSPACE$ to $L'$ and $L' \in DSPACE(O(1))$?
Why/why not?


texts:
what is the difference between memory access and data memory access?

for example, here are the examples of register transfer language instructions:

     $R1 ←[18]$
     $R2 ←[R1 +3]$
     $R1 ← R1 +2$
     $[8] ← R1$

From my understanding, memory access is where load/store occurs, like these instructions $R1 ←[18]$$R2 ←[R1 +3]$$[8] ←R1$

But what about data memory access? what is it?

thanks!


texts: Decremental reachability in a grid graph

texts:
Consider an $n$ by $n$ grid graph. For example, the following.

You can of course reach the top left corner from the bottom right.  Now consider the graph dynamically with an arbitrary number of edges deleted at each step.

  What is the time complexity of determining whether you can still reach
  the top left corner from the bottom right after edge deletions?

Further clarification.

Queries. There is exactly one type of query which gives a Boolean output.  That is whether there is a path from the top left corner to the bottom right.

Updates. An update can delete an arbitrary number of edges greater than $0$.

Complexity.  Each update is followed by a query. The complexity I am interested in is the amortized time over all updates and queries.  The best this could possibly be would be proportional to the number of deleted edges I assume.

I found these lecture notes which say you can get $O(\log{n})$ time for planar graphs per individual edge deletion (the Eppstein et al. reference). However this paper supports many more operations than I need, my graph is a special case of a planar graph and my updates are in batches in a sense.  The most important difference may just be that I am only interested in the decremental version. I haven't found anything specialized for batched, decremental connectivity in a grid graph.

Is there anything simpler than the Eppstein et al. paper for my special case or alternatively faster than $O(\log{n})$ time per edge deletion?


texts: How to calculate probability of packet loss and drop rate?

texts:
In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a rate $\lambda$ and are served at rate $\mu$ (using the Poisson distribution).

My attempt at a solution:

Probability of packet loss = Probability that the system has exactly $n$ packets (i.e., it is at its capacity)?

I also have a formula from my notes where probability of packet loss is approximated at $(1 - \frac{\lambda}{\mu})(\frac{\lambda}{\mu})^z$ (so this is most likely correct but can someone please explain why?).

I'm not sure how to calculate the rate at which packets are dropped. I already know the probabilities $P(n)$ that there are $n$ packets in the system where $n = 0, 1, ..., z$ packets.


texts:
I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought of applying it. I came across a weired situation. Someone please tell me where I went wrong.

So our language is $a^nb^n$. Let $m$ be the pumping length. Pumping lemma says that any sufficiently long string can be divided in $uvxyz$, where $v$ and $y$ can be pumped.

we take our string to be $a^mb^m$ and we can split it into $uxvyz$. Also we know that $|vxy|\le m$. Also $u$ can be $\epsilon$. In that case $vxy$ consists only of $a$, since $|vxy|\le m$ and there are $m$, $a$'s. So when we pump $v$ and $y$, the resulting string wont be in the language!

So where I got wrong? Is it wrong to take $u$ is $\epsilon$ and proceed from there?


texts: Reference request: Learning runtime analysis (Complete material)

texts:
I am very curious about learning runtime analysis more than just what MIT courseware provides (The course with Erik Demaine 6.006) And what CLRS offers, which is a nice explanation about asymptotic notations, and the master theorem (+ its proof). The book I have (which is a guide to CLRS) also provides a little bit of the Akra-Bazzi method.
I would like to learn more about this topic, all the way down to its core, and more methods (other than the iterations method, master theorem and all other methods CLRS provides) to compute the runtime, and would also contain some known exercises (or even bizarre ones).
If you have a good resource (Preferably an open-free PDF book) that would be amazing!
The resources I have now, read/watched:

CLRS (Second edition) I know there is a third edition, but they did not add anything to runtime analysis

Guide to CLRS (It is not an open book, I have a hard cover) which contain a really really small paragraph about Akra-Bazzi

MIT courseware 6.006 Into to Algorithms (Erik Demaine & Srini Devades) youtube playlist (The part about runtime + other videos I found interesting)

MIT courseware 6.006 Into to Algorithms Class notes and questions

I tried to look up on the internet but this topic is like a ghost, I cannot find a PDF book about this, in a complete version (About all the stuff there is to know about runtime analysis, just like there is a complete book for number theory or calculus for example..)
(1) By complete I don't mean 100% of-course, just so it would be a wide book on this specific topic, and deeper explanations.
Thank you for reading, and suggesting!


texts: Data Analysis: Have 70 data parameters, how many different classes of 3 are possible?

texts: The order of the classes of three does not matter. Example: 1,2,3 and 3,2,1 would be considered one class. I am trying to do fisher discriminant analysis on a set of data and want to begin reducing the parameters to better help with classification. As of now I cannot tell which parameters are the most pertinent, so looping every combination through and then having MATLAB take out the LDA analysis with the MisIDs on the lower end in my algorithm will help to isolate the parameters. Can someone refresh me on the math behind this/suggest a way to code this in MATLAB?


texts: How do you prove that polynomial reductions are not symmetric?

texts: How would I go about showing that L $\leq_p$ L' does not necessarily imply L' $\leq_p$ L? I was thinking I should show an example of two problems, where one can reduce to the other but not the other way round, but am not sure what such problems could be.


texts: Why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, $p$ and $q$ prime

texts:
I am going through Computational Complexity by Arora and Barak, and there I came across the proof of why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, where $p$ and $q$ are distinct primes. The book proves it for $p=2$ and $q=3$, and I am facing difficulties generalizing this result for arbitrary $p$ and $q$.
The proof uses two lemmas. The first one states that any $ACC^0[3]$ circuit can be approximated via a low degree polynomial $\in F_3[x]$. The change in the first lemma to generalize it to arbitrary primes, $p$ and $q$, is straightforward.
But in the second lemma, where they changed $f\colon\{0,1\}^n\to\{0,1\}$ to $f\colon\{-1,1\}^n\to\{-1,1\}$ and defined a function $\prod_{i=1}^n y_i$ which represents parity, I do not quite get how to generalize to arbitrary $p$ and $q$.


texts: Which of the following instructions can reference a memory location that is #1000 locations from the instruction?

texts:
I am working on a question from a practice computer organization exam. The answer key to one of the questions says that both LD and LEA instructions of the LC-3 processor can access memory at an arbitrary distance (say #1000) from the instruction.

How is this correct?

I think that LD uses PC relative mode, meaning it has 9 bits for offset or can access a memory location 256 spots away from the address in the program counter register(address of next instruction). That's not far enough for the criterion in the question.  The argument for LEA is the same.

Can anyone explain why I get a different answer to the key?


texts: Maximum entropy probability distribution among Solomonoff priors

texts:
If we take Solomonoff's prior $m$, defined here and normalize it we get a probability mass function on all finite words.
But, the pmf isn't completely determined until we fix a universal Turing machine (UTM) $U$.
Say $m_U$ is the normalized prior with respect to a UTM $U$.
Is there a $U$ such that $m_U$ has maximum entropy?


texts: show that if L is a regular, then drop(L) is a regular

texts:
I am trying to prove the following problem, but honestly I don't know what "proof" is considered a good proof.

I tried to prove it by constructing an NFA that start with w1 and ends with wk, but I feel something is missing.

I also tried to prove it by showing that w1 ∈ L1, w2 ∈ L2, …, wk ∈ Lk and a ∈ La.

thus Language L can be represented by:

L = L1*La*L2*La*…LaLk
If L is regular then L1,L2,...,Lk and La are also regular.

Finally drop(L) can be presented as follow:
drop(L) = L1*L2*…*Lk, since L1,L2,...Lk are regular is drop(L) (because we know that it is closed under concatenation)

I feel that there are some notation that I am not using correctly, I don't know why I feel something is missing but can't figure it out.


texts: $\epsilon$-approximation Sub-linear time monotonicity testing

texts:
I have the following exercise I have been staring at for several hours to no avail.
Question:
Testing the monotonicity of a function - the case of bits: Given a function $f: [n] \rightarrow \{0,1\}$ and a parameter $0 < \epsilon < 1$, show an algorithm that runs in $O(\frac{1}{poly(\epsilon)})$ queries to $f$, with the following behavior:

if $f$ is monotone (i.e $\forall x, y \in [n]$ if $x \le y$ then $f(x) \le f(y)$, then the algorithm always outputs "yes"
if $f$ is $\epsilon$ far from monotone, then the algorithm outputs "No" with probability at least $\frac {3}{4}$.

Definition of $\epsilon$-far:
A list $a$ is $\epsilon$-far from a list $b$, both of length $n$ iff they differ in more than $\epsilon n$ indices.
I will greatly appreciate help, and show my (stale) thought process.

My thoughts:
Consider the following algorithms
Alg1

Pick a uniformly random position $i$ between $1$ and $n$.
let $v_i$ be the value at position $i$ in the list.
Use binary search to look for the value $v_i$ in the list.
If the binary search reported $i$ as the position of $v_i$ then
return Yes
else
return No

which is proven to always return "Yes" for sorted lists, and
given a list which is $\epsilon$-far from being sorted, it returns "No" with probability at least $\epsilon$.

Alg 2

Let $ h \leftarrow \lceil \frac{2}{\epsilon} \rceil $
Execute $h$ independent copies of Alg1 on the input list.
If all the copies answer "Yes"
Return Yes
Else
Return No

which is proven to always return "Yes" for sorted lists, and
given a list which is $\epsilon$-far from being sorted, Algorithm 3 detects it is not sorted, with probability at least $\frac{2}{3}$
It is also proven to be of (query) complexity
$h lon(n) =  \lceil \frac{2}{\epsilon} \rceil O(log(n)) = O(\epsilon ^{-1} log(n))$

What to do with all that?
I thought I could use Alg 2 for the case of the binary function $f$, and to find out if it is non-decreasing.
The problem is, binary search has too many queries.
So I have to skip the search, and probably use some kind of sampling.

Let's say I uniformly sample $k$ indices of the list, and later force $k=o(\frac{1}{\epsilon})$.
I will then test monotonicity on the sample, and return an answer accordingly.
I haven't the slightest idea if this holds the required probability constraint, or how to augment so it does.
I thought maybe it would make prooving easier if I were to use the number of indices in the sample, between the leftmost "1" to the rightmost "0" as a proxy for the probability bound, but this is as far as I went.

I will appreciate direction to this, or even a solution at this point.


texts:
Consider the following language: $$ L = \{ \langle M \rangle \ |\ M \text { accepts } w \text { whenever it accepts } w^R \}$$

I am trying to understand the following proof that this language $L$ is undecidable.

The proof proceeds by contradiction, by reducing to $L$ the language  $A_{TM}=\{\langle M,w \rangle\mid M\text{ accepts }w\}$ known to be undecidable. It goes as follows:

Suppose that $L$ is decidable, then there's a TM $M_L$, that decides $L$

Thus we can build $M_{ATM}$ to decide $A_{TM}$ as follows:

Let $\langle M, w \rangle$ be an input for $M_{ATM}$.
Construct a machine, $M_1$ which on input $x$: Simulate $M$ on $w$; if $M$ rejects $w$, $reject$.  If $M$ accepts $w$, $accept$ if $x=01$, $reject$ otherwise.
Simulate $M_L$ on input $\langle M_1 \rangle$.
$accept$ if $M_L$ rejects. $reject$ otherwise.

Since $A_{TM}$ is not decidable, we have a contradiction, which implies that $L$ cannot be decidable.

However there is a point of the proof I do not understand.

My question is: What happens if $M$ gets into a loop on some $w$?


texts:
When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve:

$ TARGET = \{<G, t> : t\ is\ reachable\ from\ every\ other\ node\ in\ G\}$

Now we are allowed to use any standardly known problems that are NL-Hard in this part of the question. I considered between reducing from $REACH$ or $\overline{REACH}$, its complement - where $REACH$ is the standard NL-Complete problem. I thought perhaps $\overline{REACH}$ would reduce more naturally to $TARGET$ as the negation of $REACH$'s membership logical formula would be "$<G,s,t>$ where for all paths $P$ originating from $s$, $t$ is not on $P$".

However, I did not get very far from here. Then again, it is quite late in the evening and perhaps I am missing an obvious reduction here.

Many thanks for any hints and pointers!


texts:
I'm studying Context free Grammar and I have a question to a specific Exercise:

Why is i. True? How is this possible?


texts: Turing machine with a countably infinite alphabet

texts:
Suppose you have a Turing machine, but with a countably infinite alphabet.

How does such a Turing machine differ from an ordinary Turing machine, either in terms of computability or of complexity classes?

Do complexity classes for ordinary Turing machines hold up in such a model?

Edit: quick addendum - it seems obvious that the existence of a countably infinite alphabet leads to uncountably many state transition functions. I'm curious for the answer to both my original question, and to the restriction in which the only transitions allowed are recursive.


texts: Are there any efficient algorithms to find the shortest homotopy between two paths in a $2$-complex?


texts: Rolling Hash calculation with Horner's method

texts:
I understood how Horner's method reduces the complexity(number of operations) while evaluating a polynomial.

I have a character array derived from a string

String s = "hi how are you"

char[] array = {'h' , 'i', ' ',  'h', 'o', 'w', ' ',  'a', 'r', 'e,' ' ', 'y', 'o', 'u'}

I want to generate hash for set of characters, in successive windows of same size, example 0..3, 1..4, 2..5 etc.

Let's say I want to generate hash for characters 0(inclusive) through 3(exclusive), polynomial is $ax^2+bx+c$ where $a = array[0], b = array[1], c = array[2] $ . I am using following code.

int BASE = 31, MOD = 1000000007;

public long firstHash(char[] array, int start, int end) {
    long hash = 0;
    for (int i = start; i < end; i++) {
        hash = (hash * BASE + array[i]) % MOD;
    }
    return hash;
}

I can see how this function evaluates the polynomial. I am using MOD to prevent overflows.

Now, if I want to generate hash for characters 1(inclusive) through 4(exclusive), it should be in constant time if we use hash generated for 0..3. New equation would be $bx^2+cx+d$. All that I have to do is subtract $ax^2$, multiply the result with x and add new element which is array[3]

$$
previousHash = ax^2+bx+c\\
newHash = x\times (previousHash - ax^2)+d \\
= x\times (ax^2+bx+c-ax^2)+d \\
= bx^2+cx+d \\
$$

I am using following code for successive hash generations

int BASE = 31, MOD = 1000000007;

public long successiveHash(char[] array, int start, int end, long previousHash) {
    long base = 1;
    for (int i = start; i < end - 1; i++) {
        base = (base * BASE) % MOD;
    }
    return ((previousHash - ((array[start - 1] * base) % MOD)) * BASE + array[end - 1]) % MOD;
}

But, I am confused because of MOD. Although I know the multiplication and addition rule for % operator, I couldn't prove the successiveHash function. For smaller windows, it seems fine. But, if I generate hash for larger windows like 1..7, it is giving me negative values for hash.

I think I get the math part correct but implementation wrong.

Any help in correcting this function is of great help.


texts: Divide N sticks among M boys as homogeneously as possible (ignoring order)

texts:
There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is difficult for me to think through. Can someone suggest an algorithm? Similar questions exist on this site, but I could not find an answer that solves this problem, though it is possible that I overlooked something.

EDIT:

The sticks are all homogeneous, the same in every respect. What I mean by "as evenly as possible" is that if there are 6 sticks and 3 boys, the division algorithm should output 2-2-2. If there are 5 sticks among 3 boys, it should output 1-2-2. The disparity between the minimum stick holder and maximum stick holder should be minimized. Ordering does not matter (e.g. 1-2-2 is the same as 2-1-2).


texts: Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable

texts:
I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma_1$ is Turing recognizable.
I'm not sure what's the general way to approach this, but I noticed $A_{TM}$ is in $\Sigma_1$ by described in follows.

First note $\Sigma_1$ = the language of the form $\{x | \exists y R(x,y)\}$, where $R(x,y)$ is decidable predicate.

$A_{TM}$ = $\{\big \langle M, w \big \rangle| \exists t [M \text{ accept $w$ in $t$ steps}]\}$, where $M \text{ accept $w$ in $t$ steps}$ is decidable predicate.

$A_{TM}$ = $\{\big \langle M, w \big \rangle| \exists t T(\big \langle M \big \rangle, w, t)\}$

So we show that $A_{TM} \in \Sigma_1$, but does it sufficient to show that $\Sigma_1$ is in r.e.? Any suggestion?


texts: ANN architectures that perform faster/efficient prediction over time?

texts:
ANN when compared to biological neural systems have this common concept of reducing error in prediction over time (training) and becoming more good at predicting correctly. But there is one behavior of biological neural system where the prediction do become good over time but it also becomes fast and uses less energy, it seems like the system is able to do the prediction based on few input rather than requiring all the inputs. For example when you start to learn to read, you have to look at each character and then then brain predicts what the word is but over a period of time you don't even look at the whole word and the prediction becomes more fast and efficient by using just a small portion of the input.

Are there any ANN architectures with their corresponding learning methods that have this aspect of becoming more efficient in prediction along with more correct prediction?.


texts: Literature: comparison on books on "Systems Analysis and Design with UML"

texts:
I have been recommended a book called "Systems Analysis and Design with UML" by Tegarden.
When researching for this title, I discovered what seem two different books with deceivingly similar titles:

Systems Analysis and Design with UML Version 2.0: An Object-oriented Approach (example on Amazon here)
SYSTEMS ANALYSIS & DESIGN: An Object-Oriented Approach with UML (example on the publisher website)

Now, I think I managed to find the latest edition of both. The latest for (1) seems to be dating from 2009 (third edition); (2) seems to have had far more editions: on the publisher website there is a 6th edition from October 2020.
Could anyone:

confirm whether these are two separate, different books or not
if so, there one is better/most recommended than the other
if you have read it, express your opinion on this source.


texts: How Dynamic programming can be used for Coin Change problem?

texts:
As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of coin-change problem by truncating some search branches with caching.

Here is the problem, by the way

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

I prefer the Scala translation

  def countWithoutRepetitions(s: Int, dimes: List[Int]): Int = {
    if (s == 0) 1 else
       if (s < 0 || dimes.isEmpty) 0
        else dimes match {
          case d :: ds => {countWithoutRepetitions(s, ds) + countWithoutRepetitions(s-d, ds)}
        }
  }

Odersky also asks for cache-based trimming algorithm in his course (pdf for those who are not enrolled). Yet, I do not understand what do people discuss at all.

The search tree never repeats itslef. It never calls the function with the same (sum, available_coins) arguments. What are you going to cache?


texts: Is there any polynomial time algorithm for a restricted EXP-time problem?

texts:
Let we fix $<T>$ and $w$, where $<T>$ is its binary representation of a Turing machine and $w$ is input.

We want to check if $T$ doesn't halt over $w$ before $2^{|w|}$ steps. A trivial solution is to use a universal Turing machine which simulates $T$ on $w$ and counts its steps, but this method uses exponential time.

I wish to know do we have any polynomial time algorithm to check this for the fixed Turing machine and input?

If we had a high-level program or pseudo code, then we had the possibility to analyze it and figure out the time complexity without simulation. But by Rice theorem, we know that it is not possible to understand the behaviour of a Turing machine using its binary representation string. So it seems impossible to have a Turing machine which runs in polynomial time and understand that $T$ doesn't halt less than $2^{|w|}$ steps even for a fixed $T$ and $w$. I don't know how to prove it.

Edit (In order to be more clear about inputs and outputs):

There are two possible ways to think of it:

We want a Turing machine $M$ that runs in polynomial time over its empty tape and outputs 0 if $T$ halts over $w$ before $2^{|w|}$ steps and outputs 1 otherwise.
We want a Turing machine $M$ that runs in polynomial time over input $<T>w$ and outputs 0 if $T$ halts over $w$ before $2^{|w|}$ steps and outputs 1 otherwise. It's not important for us that what is $M$ output for other inputs.

I believe there is no such $M$ since it is not possible to understand what is a Turing machine doing without simulation of its steps. If such $M$ exists, then it is understanding somehow how $T$ acts on $w$ without simulation of $T$ on $w$. Of course for special cases like pseudo-code, we can estimate the running time. But the $T$ which we fix is not always a pseudo-code.

Edit 2: In order to fix the point Ariel mentioned in his answer,

We want a Turing machine $M$ with the second formulation that works correctly as we stated (it understand T takes exponential time running its input) for two inputs $<T>w_1$ and $<T>w_2$.


texts: Mapping many transition functions into two transition functions

texts:
Continuing from this answer: https://cs.stackexchange.com/a/56072/43035

I don't understand how it's possible to map many transition functions $\delta_1,...,\delta_n$ of a NDTM into just two transition functions $\delta_0',\delta_1'$. How will conflicts be handled?

For example: $\delta_1(q_1, a) = (q_2, b, R)\\ \delta_2(q_1, a) = (q_3, c, L)\\ \delta_3(q_1, a) = (q_4, d, R)$

How can you map $\delta_3$?


texts: What sort of algorithm/communication model/data structure do collaborative real time editors use?

texts:
I am researching collaborative editing systems for some work, but so far my search is turning up blank.

Collaborative real-time editing systems almost all have features like:

Many users can edit the document at the same time
All changes are dated and saved in a linear revision history
Edits are visible in semi-real time
Who-wrote-what is tracked for all content

I cannot think of a data- and procedure model to encompass all of these without huge inefficiencies, for example:

Take user input as a few typestrokes at a time, thus enabling real-time visibility but with horrible server loads.
Take user input as element changes, thus disabling real-time visibility and complicating many-user-editing of one paragraph.
Edit a XML Document Model Object in place responding to inputs, but making it difficult to version/revision track.
Edit linear text stored in an appropriate editing structure responding to inputs, making it difficult to verify that correct markup is being generated.
Store revision history accumulating, requiring computational resources but easing on space.
Store revision history whole, requiring space but easing on computation.

Am I off track? Does there exist good solutions to these problems? What, if any, is the relevant litterature?


texts: Variable elimination in Bayesian network

texts:
I'm trying to check if my understanding of variable elimination is correct.

Assume the above Bayesian network is factorized as:

$p(a,b,d,e,l,s,t,x) = p(a)p(t|a)p(e|t,l)p(x|e)p(l|s)p(b|s)p(d|b,e)p(s)$

Suppose I want to find $p(e|s)$, this means performing $p(e|s) = \sum_{t,l}p(e|l,t)p(t)p(l|s)$

Now, $p(e|l,t)p(t)= \frac{p(e,l,t)}{p(l,t)}p(t) = \frac{p(e,l,t)}{p(l|t)} = \frac{p(e,l,t)}{p(l)} = p(e,t|l)$. The third equality is due to the unconditioned collider $e$. Marginalizing over $t$ gives us $p(e|l)$.

Subsequently, $p(e|l)p(l|s) = p(e|l,s)p(l|s) = \frac{p(e|l,s)p(s)}{p(s)}p(l|s) = \frac{p(e,l,s)}{p(s)} = p(e,l|s)$, where the first equality is because conditioning on $l$ makes $s$ irrelevant, i.e. $p(e|l,s) = p(e|l)$. And marginalizing over $l$ finally gives $p(e|s)$.

Is this correct?

Also and on to the larger picture, is there a faster way of deriving or 'seeing' this equality? It seems to me that the faster approach is moving the conditioned variables over the conditioning bar, and then marginalizing, that is  $\sum_{t,l}p(e|l,t)p(t)p(l|s) = \sum_{t,l}p(e,l,t|s) = p(e|s)$. Is this valid?

Thank you.


texts:
In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-chosen heuristics. These heuristics are not proven to be the optimal heuristics.  (they're not optimal obviously).

I am wondering however:

  Is there some kind of search problem (ideally a non-trivial one), where (1) there is a specific known algorithm that solves it, and (2) a proof that the algorithm is optimal in the sense that there does not exist an algorithm that solves it faster in expectation, where (3) the probability distribution for that expectation is the relevant one for that practical search problem?

I'm interested in anything related to this. If you know something that seems partially relevant, please say so.

EDIT: Alternatively, please suggest a different notion of "optimality" if you think it is more relevant. I am not sure how relevant my notion of optimality is.

EDIT 2: I'm also interested in how this question relates to the 'No free lunch' theorems in search and optimization.


texts: How to setup a model for a guillotine cutting stock problem?

texts:
Backgroud.
I'm reading papers about cutting stock problem (CSP).

Said Ben Messaoud, Chengbin Chu, Marie-Laure Espinouse (2008)
Characterization and modelling of guillotine constraints.
European Journal of Operational Research 191 (2008) 112–126.
D.A. Wuttke, H.S. Heese (2017) Two-dimensional cutting stock
problem    with sequence dependent setup times, European Journal
of    Operational Research

Problem

There is a square canvas, the side of the canvas is $n\times a$.

It is required to cut this canvas into $n^2$ equivalent squares with the side, $a$.

For $n = 3$, we can easily get the solution: $9$ squares with the side $a_1=a_2=...=a_9=a$, where $a_i$ the side of $i$-th square, $i \in I = \{1,2,\ldots, n^2\}$. If we remove any square, we will have a classic $8$-puzzle (left figure below, $n=3$).

At first, let us now omit the constraint on squares' side size, they can be different: $$a_1 <a_2 <... <a_i <... <a_{n ^ 2}. \tag{1}$$

At second, let us add the following constraints on squares' sides (right figure above, $n=3$):

The sum of any two consecutive elements of the set $(1)$ must be greater  the following element.
Any element of the set $(1)$ must be less than half of the canvas, $n\times a$.
The first element of the set $(1)$ must be greater than the half of equivalent solution, $a$.

The task is to prove:

a) the problem will have a solution (integer or real),

b) the solution is $(n^2-1)$-puzzle.

Question. How to setup a model for an optimization problem?

My attempt is:

I think I have a case of guillotine cutting stock problem.

I have tried to write the constrains (C1)-(C3):

$$ s.t. \left\{%
\begin{array}{ll}
a_ {i + 2} < a_i + a_ {i + 1} ,& i = 1,2, ..., n ^ 2-2; \\
a_i <\frac{n\times a}{2}, & \forall i \in I;  \\
0 < a/2 < a_1. \\
\end{array}%
\right.$$

Update.

Here is the list of software (see at bottom of page) to design, test, and solve your own original sliding block puzzles.


texts:
I am trying to find out how they calculated the time complexity of this small function .
I am studying for an exam and found this question and the final answer is given, but I am trying to understand how they got to this answer,
I tried solving this problem using Iterative but when I tried to find the number of Iterations of this function I got stuck !

What I tried: let $T(n,k)$ represent the time complexity of $g$. It satisfies the recurrence

$$    T(n,k)=ck+\sum_{j=1}^i(2^j-1)k + T(n-i,2^ik)$$

when $i$ is the number of iteration in this function, so according to this function the iteration ends when $n\le k$, which means $n-i=2^ik$,
but I couldn't extract $i$ from the equation.

Here is the function, whose time and space complexity are stated to be $\Theta(n)$ and $\Theta(\log n)$:

   int g(int n, int k) {
      if (n <= k) return 1;

      int result = 0;
      for (int i = k; i > 0; --i, ++result);

      return result + g(n - 1, 2 * k);
    }

    int f2(int n) {
      return g(n, 2);
    }


texts: array median transformation using the min number of steps

texts:
Let $A[1...N]$ be an Array of size $N$ with maximum element $\max$.

I want to transform array $A$ such that after transformations all elements of $A$ contain $\max$, i.e. after transformation $A = [\max,\max,\max,\max,\dots,\max]$.

In one step, I can apply the following operation to any consecutive sub-array $A[x..y]$:

  Assign to all $A[i]$ with $x \leq i \leq y$ the median of subarray $A[x..y]$.

We consider as median always the $\left\lceil \frac{n+1}{2} \right\rceil$-th element in an increasingly sorted version of $A$.

What is the minimum number of steps needed to transform $A$ as desired? If it helps, assume that $N\leq 30$.

Example 1:

Let $A = [1, 2, 3]$. We need to change it to $[3, 3, 3]$. The  minium number of steps is two, first for subarray $A[2..3]$ (after that $A$ equals to $[1, 3, 3]$), then operation to $A[1..3]$.

Example 2:

$A=[2,1,1,2]$.The  min step is  two. The median of subarray $A[1..4]$ is $2$ (3rd element in $[1,1,2,2]$. Apply the operation to $A[1..4]$ once and we get $[2,2,2,2]$.


texts:
I need help to understand Chaitin's elegant program proof. An elegant program is the shortest program that produces a given output.
Here is the proof:

Construct a program $B$ that takes as input a number $N$ and enumerates all possible programs $P_k$ longer than $N$. $B$ runs the elegance tester $\mathrm{ET}$ on each enumerated program $P_k$ in turn until it finds some $P_k$ which $\mathrm{ET}$ claims is elegant. $B$ then runs that $P_k$, thus producing the same output as that $P_k$.
Lemma: B must produce some output.
Proof: There are an infinite number of elegant programs, as noted earlier. So if $\mathrm{ET}$ works as assumed, $B$ must eventually find one of those elegant programs whereupon it will produce that program's output.
Now run $B$ with $N$ set to $|B| + 1$ (See note 1). (This is the "threshold size" mentioned in the theorem.) $B$ now will produce the same output as some program $P_k$ which $\mathrm{ET}$ claimed was elegant. But $P_k$ is longer than $B$, so $P_k$ cannot be elegant because $B$, which is shorter, produced the same output. Therefore, $\mathrm{ET}$ was wrong when it claimed $P_k$ was elegant. QED.

My question is: The proof begins with a program $B$ that is a program "that takes as input a number $N$ and enumerates all possible programs $P_k$ longer than $N$" But because of the halting problem such a program is not possible, so the proof starts dead? There is something I'm not understanding here.


texts: Find If a node exists in all maximum bipartite matchings

texts:
Given a bipartite graph, I need to find for each node, If this node exists in all the possible maximum matchings of the given graph or not.

Note that there can be multiple maximum matchings  of a given bipartite graph with the same value of matching but different set of edges.

What is an efficient way to do this?


texts: What is "orthogonality" in the context of Instruction Encoding?

texts:
What does it mean by "orthogonality" in the context of Instruction Encoding?

Why CISC Architecture is orthogonal while RISC is not?


texts:
I am picking up from this thread for which I have no privileges to comment on:

Is C actually Turing-complete?

I was wondering if there's any progress on this and what the conclusion actually was. This is not a duplicate of the Is-c-actually-Turing-Complete but a continuation, with the following third possible solution that was not outlined there.

Kinda confused at the three options which were based on the 'C implementation' of the C99 standard.

a) one answer suggested that with the C11 implementation we can obtain Turing completeness through the optional threading libraries

b) another answer which @Gilles suggested as valid answer was postulated by
a comment by @Jukka:
"For example, overflow by X = write X/3 on the tape and move in direction X%3, underflow = trigger the signal corresponding to the symbol on the tape. It feels a bit like an abuse, but it's definitely in the spirit of my question. Could you write it as an answer? (@others: Not that I want to discourage other such clever suggestions!)."
That would mean through a clever overflow we could obtain turing completeness ? But I didn't see that as an answer choice ... and it seems not like it resolved the underlying problem completely.

c) There was another option not mentioned there, which I outline here.
Is it possible to simulate a gigantic pointer perhaps the way a large integer can be simulated ?

Thanks.


texts: Can you solve 3D Tic Tac Toe with Minimax?

texts:
I have implemented a 3d Tic Tac Toe game with AI, where the computer is unbeatable.

The only thing is that the board looks like this:

_ _ _
 _ _
_ _ _

rather than this:

_ _ _
_ _ _
_ _ _

There are a total of 3 boards stacked on top of each other, and any lines of 3 x's or o's grant a point. When the board is full, all points are tallied and the winner is announced.

I used the minimax algorithm with alpha-beta pruning.

But my algorithm is only able to get the optimal move if the board is full to a certain degree. When there are less moves, it takes a really, really long time to find the optimal move.

Is there some way to speed up my minimax? I have already researched ways to speed up minimax, but I need an answer specifically related to my situation.

Is it possible to solve to optimal move quickly using minimax? Or do I have to use a different algorithm?

EDIT: Please note that the game uses gravity, like in the connect-four game. I.e. the x's and y's stack.


texts: Regular expression of a language over {a,b,c} which does not contain substring bbb

texts:
I'm trying to figure out how to build a regular expression for a language that doesn't contain substring bbb. The alphabet is {a,b,c}. I'm trying to construct a DFA and convert to help me get the Regular Expression but still stuck as I found the DFA a bit complicated. I appreciate any help. Thanks!!!

Ok, here is the Regular Expression I've worked on to help me solve the above question.
ac[(acb)* U (acbb)]ac*

Test:
aaaa ccccc acbacbacb aaaaaaa ccccc (OK)
aa acbb acbb acbb acbb cccccccc (OK)

But how about cab or cabb?
I then modified the above expression to:
ac[(acb)* U (acbb)* U (cab)* U (cabb)]ac*

I'm I heading to the right direction?

Thanks again!


texts: Understanding Dynamic Programming through this example

texts:
I have trouble understanding The classic Mailbox Manufacturers Problem. You can read it here: https://open.kattis.com/problems/mailbox I have also found a solution text: http://www.ida.liu.se/projects/progcontest/progsm/2002/prognm2002-hints.pdf

I just cant get my head around this problem and i cant even understand the solution given above. For example what does "minimum number of fire-crackers that is needed, in the worst case" mean? What is the worst case? If i have 2 boxes each fitting 4 crackers, how can the answer be 7?

I have also looked at codes that solved this problems but couldt understand the solution either and yes i am familiar with recursion and some DP but still cant get this one. Anyone care to explaing? Thanks in advance!


texts: Data strucutre for finite graphs on a cylinder

texts:
My problem is to find an efficient data structure that allows the encoding of a (non-directed) graph on the surface of a cylinder (without top and bottom discs).  Usually I would store a graph as a list of edges, which are pairs $(a,b)$ of vertices. My problem is that I can have two kinds of edge from $a$ to $b$ either by taking the shortest path or going around the cylinder. These two edges should be considered as being different.

My set of vertices is fixed ($n$ vertices on the top circle, $n$ vertices on the bottom circle of the cylinder) and I requires that, for any vertex, there exists precisely one edge to another vertex. Furthermore crossings of edges are not allowed (that is why it is important to be able of "going around" the cylinder; taking a "longer" way).

The aim then is to glue two such cylinders together (the bottom of one goes on the top of the other) and compute the connected components of the "glued" graphs, which will produce another graph on a cylinder.

Of course one could just tag the edges, depending whether one goes the shortest or longest way, but maybe someone has a better idea!?


texts: Why, intuitively, does the Ackermann function require $\mu$-minimisation?

texts:
I have read proofs that the function is not primitive recursive and I (think) I understand them. Most I've seen show that the set of functions dominated by the Ackermann are exactly the primitive recursive functions etc.
But, coming at it from the point of view of the 'ground requirements' which define the collection of recursive functions, I am having a hard time making the link between the (current) definition for the Ackermann function, and why it requires unbounded minimisation/search.
I am unfamiliar with a lot of theoretical computer science so I hope my question makes sense!


texts:
Is the language of the set of descriptions of all Turing machines recognizable?  I'm thinking not, but I can't quite define why.

A language is Turing-recognizable if some Turing machine recognizes it.  So I guess I'm wondering if the language L of all Turing machine descriptions is Turing-recognizable.


texts: Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm?

texts: I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and operations such as swap are ignored. Link to selection sort analysis. Please help me understand.


texts:
Coming from a C++ background I don't understand why one needs types / type expressions as first class citizen?
The only language I know that supports this feature is Aldor.

Does anybody have some literature about types as first class citizen or know some reasons why it's useful?


texts: Min-cut in a network with zero flow from source to sink

texts:
The max-flow min-cut theorem guarantees that the min-cut of a directed network equals the maximum flow. And we can compute $S$ and $T$, are disjoint subsets containing source node and sink node respectively from the residual graph.

What will be $S$ and $T$ if the max-flow from source to sink is 0, that is, there is no directed path from $s$ to $t$? Is $S$ going to be the singleton set {s} or its the empty set $\phi$ and $T$ be the vertex set $V$?


texts: combine divergent persistent red-black tree instances

texts:
Given a persistent red-black tree, I've been searching for an algorithm, approach, or equivalent data structure that allows me to efficiently merge two instances of the tree produced by divergent modification of a common ancestor.

For instance, tree instances v1 and v2 produced by mutating the common instance v0, are combined merge(v1, v2) to produce v3. The problem is slightly simplified by restricting the merge of trees to apply only when (1) the divergence is bound such that the length of a branch is at most 1, although many merges may occur between a branch point and it being merged. (2) v1 and v2 do not have merge conflicts. what i mean by this is that they do not both update the same keys, and changes in v2 take precedence.

I suspect that the best solution will involve augmenting the red-black tree with additional metadata such as node versioning information.

I've been navigating the literature on persistent data structures now for a while, and need some guidance to help restrict this search.


texts: Is $f$ which returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ computable?

texts:
The question itself:

  Let $f:\mathbb{N}\to\Sigma^\star$ be such that $f(n)$ returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ (which is the complement of the language of TMs which accept $\epsilon$, i.e. the TMs which reject or do not halt on $\epsilon$). Prove/disprove: $f$ is computable.

My approach:

I started to disprove this one by contradiction. I know that $H_{TM,\epsilon}\in \mathcal{RE}\setminus\mathcal{R}$ and thus, $H_{TM,\epsilon}\not\in co-\mathcal{RE} $, so $\overline{H_{TM,\epsilon}}\not\in\mathcal{RE}$. Then we get that there is no TM $M$ such that $L(M)=\overline{H_{TM,\epsilon}}$ but if $f$ is computable we can contruct a TM which accepts $\overline{H_{TM,\epsilon}}$:

The TM on input $\langle M\rangle$ (encoding of a valid TM) will run $f(n)$ for $n=1$ and on and if $f(n)=\langle M\rangle$ it will accept otherwise continue.

Then if $\langle M\rangle\in\overline{H_{TM,\epsilon}}$ there exists some n such that $f(n)=\langle M\rangle$ otherwise the new TM will not halt. So we contructed a TM for a language that is not recursively enumerable, contradiction.

Please tell me if my approach is good and if not help me understand my mistake and get to the right answer.


texts:
I am wondering whether the language $$L_{\textrm{hanoi}} = \{\langle k,s \rangle \mid \text{$s$ is a solution of Tower of Hanoi problem on $k$ rings}\}$$ is in $R\setminus \mathit{NP}$.
I want to claim that there is a Turing machine that solves the problem, therefore, $L_{\mathrm{hanoi}} \in R$, but given a solution to the problem, verifying that it is a valid solution takes $\Omega (2^k)$. However, $2^k$ could be be linear to the length of the input (number and sequence).
Is my solution valid? If not, how can I construct a language in $R \setminus \mathit{NP}$?


texts: Priority queue with a buffer for delayed insertion and other tweaks

texts:
I was thinking of ways to optimise a (heap-based) priority queue in certain scenarios, like in best-first path search algorithms (Dijkstra, A*, etc.).

One possible optimisation is to delay insertions until the next extraction.  The inserted elements can be kept in a buffer (a simple stack) until the next extractions, and then inserted with some kind of optimised "bulk insertion" method.

Another possible tweak is to check if the element to be inserted has a higher priority than all the waiting ones, and if so, to store it in a second stack, which is to be used for the subsequent extraction.  If the priority of the element to be inserted is not the highest but higher than the priorities of all the elements in the heap, then the elements from the second stack can replace the elements at the top of the heap, while the replaced elements are moved to the buffer for delayed insertion.  This tweak however would add a noticeable overhead, so it is not clear if it would be an optimisation in any scenario.

Has such or similar modifications of (heap-based) priority queues been studied or used in practice?


texts: Is it compulsory that every infinite set be non regular?

texts:
I am confused regarding the statements provided by one of our faculty regarding
   "Is it compulsory that every infinite set is non regular
    though every finite set is a regular set".
Providing this  example:

  $$L= \{ 0^n 1^n | n>=0 \} $$     its  formal as $\Sigma=\{0,1\}$ and
  thus we've a formal meaning as $\{\epsilon,01,0011,000111,....\}$

                               no. of 0's = no. of 1's

The above language should be a non-regular as we need to keep track the value of 'n' in order to make it a equal no, of 0's & 1's and FA has no memory.

or am i mistaken.

Please, provide some oxygen regarding this confusion.thank you.


texts: Good algorithm to compress down connections of graph nodes?

texts:
I have a collection of graph nodes which are connected to each other.

I wrote a DFS algorithm to recursively search the connectivity of the graph to find all connected nodes, however due to the size of the network, it is taking too long.

To improve the performance, I wanted to assign tags to the nodes, as MAJOR and NOT-MAJOR, such that I can create a new graph that only contains the connections from MAJOR nodes to other MAJOR nodes, sort of illustrated in the photo below where the big circle denotes MAJOR and the red dot denotes NOT-MAJOR:

The desired result would be taking the left graph and compressing it down to the right.

The data I am working through is very large, and there are a lot of interconnections, many islands, and always at least 1 major node.

I have written a second version of my DFS function to take the graph and a major node, traverse each connected node to the major and check if the connected node is a major node, if so then append that major node to a new list, and return the list as the new connections, otherwise return a list only containing the major node itself.

But this is still taking a very long time to pass through the entire network, with the program sometimes crashing due to maximum recursion depth exceeded (Which tells me I have not implemented this very well).

Is there a better way I can approach this compression problem?


texts: Alternatives for finding sources in a DAG

texts:
I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states:

Property Every dag has at least one source and at least one sink.
The guaranteed existence of a source suggests an alternative approach to linearization:

Find a source, output it, and delete it from the graph.
Repeat until the graph is empty.

However, we can linearize the DAG by arranging the post numbers in decreasing order. Isn't this the alternative above the same thing? How else can we find sources if we don't have to pick the largest post number, which is the source?
Isn't deleting the source an extra step and therefore unnecessary? I assume that we have already run depth-first search to obtain the pre and post numbers.


texts: Algorithm - Checking if an unconnected graph is cyclical

texts: I have an algorithm for finding if there is a cycle in a connected graph by depth first path creation of a graph until there is a duplicate in the path. Beside simply starting this algorithm at all possible points for an unconnected graph, how can I find if an unconnected graph is cyclical in good time and in a simple way?


texts: How should we interpret a transition rule $\epsilon,b\to c$ in a Pushdown Automata as Sipser defined in his book?

texts:
After defining pushdown automaton in Sipser's book at p. 113:

at the bottom of p.114, he tries to describe a way to make a diagram for pushdown automaton as following:

My question is about the part "If $a$ is $\epsilon$, the machine may make this transition
without reading any symbol from the input." But in many examples in the book, it seems some $\epsilon$s which are in place of $a$ must be interpreted as an empty string to show that the pointer is reached to the end of input. For example in the following diagram, we must interpret the first $\epsilon$ in the label of the transition between $q_3$ and $q_4$ to an empty string which shows the end of input string:

Otherwise, it can accept $01^2$. Since, if we interpret $\epsilon,\$\to\epsilon$ as to make this transition from $q_3$ to $q_4$ without reading the second 1, then $01^2$ would be accepted.

Now my question is how a PDA decides if that $\epsilon$ is for moving without reading any symbol from input or that $\epsilon$ is an empty string?


texts: Proving that the continuation of a non-regular language is not ω-regular

texts:
I want to prove that a language is not $\omega$-regular.

The language I'm working with can be defined as:

$$L = \{ a_1 \dots a_n x^\omega ~ | ~ n > 0, a_1 \dots a_n \in L^\prime \}$$

where $L^\prime$ is a specific non regular language (I omit the definition $L^\prime$ because I think it is of no help for my problem), $a_i$ are symbols in $L^\prime$ alphabet and $x$ is any symbol not in $L^\prime$ alphabet.

I'm aware of several proof techniques for proving a language is not regular (see e.g. How to prove that a language is not regular? ).

Are there similar proof techniques for proving that a language is not $\omega$-regular?


texts: Partition algorithm average-case complexity analysis

texts:
I was given the following algorithm:

PARTITION(A,p,r)
x <- A[p]
i <- p
j <- r
repeat
    while A[i]<x
        do i<-i+1
    while A[j]>x
        do j<-j-1
    if i <= j
        then exchange A[i] <-> A[j]
until i>j
return i,j

quicksort(A, p, r):
    if p<r
    then i,j <- PARTITION(A,p,r)
    QUICKSORT(A, p, j)
    QUICKSORT(A, i, r)

And I was asked to find the quicksort run time at best, worst and average cases.
I did okay for the best and worst, however I'm having difficulties with the average case. I'm pretty sure it's still $O(nlgn)$, but I can't prove it formally, mainly showing how many time the partition method is called at most.

Could anyone help me with that?
Thanks!


texts: How can I quickly guess if L is context-free or det. context-free?

texts:
I have a language, for example

$\{a^m b^n c^n \mid m, n \in \mathbb{N}, m = 2n\}$
$\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\}$

How can I see at a glance whether the language is deterministic context-free, context-free or not context-free?  I'm not willing to try to prove the language to be context-free.  I just want a heuristic -- a quick test I can apply by inspection, without use of a computer, that will often be correct.


texts:
I'm surprised that people keep adding new types in type theories but no one seems to mention a minimal theory (or I can't find it). I thought mathaticians love minimal stuff, don't they?

If I understand correctly, in a type theory with a impredicative Prop, λ-abstraction and Π-types suffice. By saying suffice I mean it could be used as intuitionistic logic. Other types can be defined as following:

$$
\bot \stackrel{def}{=} \Pi \alpha: Prop. \alpha \\
\neg A \stackrel{def}{=} A \to \bot \\
A \land B \stackrel{def}{=} \Pi C: Prop. (A \to B \to C) \to C \\
A \lor B \stackrel{def}{=} \Pi C: Prop. (A \to C) \to (B \to C) \to C \\
\exists_{x: S}(P(x)) \stackrel{def}{=} \Pi \alpha: Prop. (\Pi x: S. P x \to  \alpha) \to \alpha \\
$$

My first question is, do they (λ, Π) really suffice?
My second question is, what do we need minimally if we don't have an impredicative Prop, such as in MLTT? In MLTT, Church/Scott/whatever encoding doesn't work.

Edit: related


texts: Creating arrays of object of abstract class in statically-typed object-oriented languages

texts:
In statically-typed object-oriented languages (like Java, C++, C#, ...), suppose I declare an abstract class:

public abstract class myclass1 {
 .................
}

Most of these languages (like Java) wouldn't allow us to create an Object of an Abstract class, but they do allow us create an Array of Object of an Abstract class.
Like,

myclass1 arr[] = new myclass1[10];

We can create an array of 10 objects.

I have some confusion about how this kind of array works.  How do I use this array?
What is the actual use of this array in real-life projects?
Any explanation with an example will be very useful.


texts: Is string spliting formally defined when the string delimiter is an empty string?

texts:
Depending on the API/language you use, splitting the string "ABCD" using "" as a delimiter gets you:

["A", "B", "C", "D"] in Java, Javascript, and Go
["", "A", "B", "C", "D", ""] in Rust
["ABCD"] in C#
Fails with an Exception in Python3

From the perspective of formal language design, what is the correct result of such an operation? Is it defined?
Disclosure: This question was posted at stack overflow but was closed as opinion-based. I was directed to post my question here instead.


texts: Is it possible to compute how many iterations this algorithm will take?

texts:
I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always guaranteed to terminate.)

Let $x$, $y$, and $z$ be some positive integers.
The values of $x$, $y$, and $z$ are chosen such that neither $y$ nor $z$ will become $\le 0$ before the loop terminates.

$\text{do}$

$\qquad \text{if } (x+y) \text{ mod } z = 0 \text{ then done}$

$\qquad x \leftarrow x + y$

$\qquad y \leftarrow y - 4$

$\qquad z \leftarrow z - 2$

$\text{loop}$

For example, if we let $x =184$, $y = 376$, and $z = 187$, this algorithm terminates in $19$ loops.

Here is a plot of $(x+y) \text{ mod  } z$ for some real inputs. Here is another plot for larger inputs.


texts: Equivalence between two definitions of Tree width

texts:
Treewidth :

1) By chordal graphs : size of the largest clique $(\omega (G))$ - 1 in a chordal completion of the graph $G$.

2)  By tree decomposition :

A tree decomposition of $G = (V , E)$ consists of a tree $T$ (on a different node set from $G$), and a subset $V_t ⊆ V$ associated with each node $t$ of $T$. (We will call these subsets $V_t$ the “pieces” of the tree decomposition.) We will sometimes write this as the ordered pair $(T , {V_t : t ∈ T })$. The tree T and the collection of pieces $\{V_t : t ∈ T \}$ must satisfy the following three properties

(Node Coverage) Every node of $G$ belongs to at least one piece $V_t$.

(Edge Coverage) For every edge $e$ of $G$, there is some piece $V_t$ containing both ends of $e$.

(Coherence) Let $t_1, t_2,$ and $t_3$ be three nodes of $T$ such that $t_2$ lies on the path from $t_1$ to $t_3$. Then, if a node $v$ of $G$ belongs to both $V_{t_{1}}$ and $V_{t_{3}}$, it also belongs to $V_{t_2}$

So we define the width of a tree decomposition $(T , {V_t })$ to be one less than the maximum size of any piece $V_t$ (over all $t$):
$$width (T , {V_t}) = max |V_t| − 1$$

Claim 1: If size of largest clique in a chordal decomposition of graph is  say $k$ then by tree decomposition we will get tree width $k$

Proof : let us assume that largest clique size in chordal completion graph is $k$, so there exist a bag (subset of vertices of graph) that contain the clique ( due to edge coverage ). so we are done.

claim 2 : If tree width is $k$ by tree decomposition method then by chordal completion method also is $k$

  Question : How to prove the claim 2 ?High level proof will be welcomed.


texts: Order of Traversal in Bidirectional Dataflow Analysis

texts: Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?


texts: Comparison between IDA* and Recursive best first search

texts:
How does IDA* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity?

Both algorithms are intended to be memory-efficient heuristic search algorithms.  From my understanding, RBFS just updates the $F(n)$ value for the parent node for which the current execution was stopped in comparison to IDA*, so it avoids redundant computation to a certain extent, but I'm not sure what exactly this means for the number of nodes expanded or its space complexity.

My main motive of this question was to identify all possible reasons that led to development of RBFS (which can be considered as a successor of IDA*).


texts: Is the exponent in floating point numbers signed or unsigned

texts:
This may be sound like a stupid question, because, of course, it can be negative and, as Wikipedia states:

  A numeric variable is signed if it can represent both positive and negative numbers, and unsigned if it can only represent non-negative numbers (zero or positive numbers).

But is it really? Because it doesn't work like normal signed integer, because doesn't really have a sign, it's just an unsigned integer starting at a negative point, it seems to me. I guess the first character could indicate whether it's negative xor positive / zero.

For people who don't remember CS class:

exponent of -127: 0000 0000
exponent of zero: 0111 1111
exponent of one:  1000 0000
exponent of 128:  1111 1111


texts: How to find the minimal path cost from left edge of a grid to the right edge using dynamic programming?

texts:
I need to find the minimal path cost from left edge of a $n\times n$ grid to the right edge where each node has some non-negative weight $cost(i,j)$. $i$ represents horizontal coordinates while $j$ represents vertical coordinates. Only the following movements are allowed in the grid:
  $$
(i,j)\to(i+1, j-1) \quad\text{aka diagonal down}\\
(i,j)\to(i+1, j) \quad\text{aka right}\\
(i,j)\to(i+1, j+1) \quad\text{aka diagonal up}\
$$
  The algorithm must run in $\Theta(n^2)$ time and use dynamic programming.

I thought:

1) first to select the minimal cost node in the left-most column, that is find $min(cost(i, 1))$. Let the node be $s$ (start node).

2) Now we can use Bellman-Ford algorithm as described here (page 53) in order to find the minimal cost path from $s$ to any other node. The recurrence for Bellman-Ford would be:
$$
opt(i,j) = cost(i,j) + min(opt(i+1,j-1),\\ opt(i+1, j),\\ opt(i+1,j+1))
$$

3) We'd get a $n\times n$ matrix in the end where the right-most column would represent the right-most edge of the grid. Therefore the minimal cost path from left edge to the right edge would be the minimal cost in the right column.

Is my logic on the right track? I'm really not sure regarding the steps 1) and 3). Also because Bellman-Ford calculates edges costs do I need to perform any reduction in this algorithm because costs are not stored on edges but rather on nodes?


texts:
I'm a fledgling computer science scholar, and I'm being asked to write a paper which involves integer factorization. As a result, I'm having to look into Shor's algorithm on quantum computers.

For the other algorithms, I was able to find specific equations to calculate the number of instructions of the algorithm for a given input size (from which I could calculate the time required to calculate on a machine with a given speed). However, for Shor's algorithm, the most I can find is its complexity: O( (log N)^3 ).

Is there either some way I can find its speed/actual complexity from its Big-O Notation? If not, is there someone who can tell me what I want, or how to find it?


texts: Closure properties of Alternating Circuit 1 level

texts:
Recall that $\mathsf{AC^1}$ is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth.
Is this class closed under Kleene star?
I thought it would be simple since it is easy to check every subword (using a polynomial number of gates), but the part where I have to check every partition makes the circuit linear in depth.


texts:
I am working on a simulated annealing algorithm for graph coloring. The model I follow is the following: http://riad.pk.edu.pl/~zk/pubs/PPAM07_2.pdf. I have troubles understanding the cooling schedule and more particularly, the part with the variable M. In my understanding M represents the number of iterations after which the temperature should be changed.

Also, as I understand it, the algorithm focuses on finding a proper color distribution, given the chromatic number and not on finding its value. Since there is no focus on finding the chromatic number, but rather on a coloring with cost low enough, I decided to try "repurpose" the algorithm by setting an upper boundary of colors via Brook's Theorem and using binary search to adjust the target cost and eventually find a solution with low enough chromatic number. This model, however, may prove slower, so I wanted to ask if you could suggest any better solutions?


texts:
Having read all these posts

Constant-depth threshold circuit for $\mathrm{PP}$

Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$

I wonder about the weakest possible reduction for 3-$\mathrm{SAT}$ to be complete for $\mathrm{NP}$?


texts: Integer Linear (ILP / MILP) Formulation for Collision Avoidance of Convex Polytopes / Polyhedra

texts:
I am looking for a possibility to avoid the collision of two convex polytopes using (mixed integer) linear programming. I know how I can detect a collision (Akgunduz, A., Banerjee, P., and Mehrotra, S. (March 14, 2005). "A Linear Programming Solution for Exact Collision Detection ." ASME. J. Comput. Inf. Sci. Eng. March 2005; 5(1): 48–55. https://doi.org/10.1115/1.1846053):
Vertices of polytopes are given: vj, wj
Weights are variables: αj ⩾ 0, βj ⩾ 0
∑vj αj − ∑wj βj = 0 (1)
∑αj = 1 (2)
∑βj = 1 (3)
Equation (1) applies to each of the x, y, and z coordinates of the vertices for P1 and  P2. Here the presence of a feasible solution indicates a collision. If no solution is found, no collision exists. What I am now looking for is the opposite. I am looking for a feasible solution for no-collision and a not feasible solution if the polytopes collide. How can I change the equations to get this? It is also important for me, that the collision avoidance is not included in the objective function, since the objective parameters are others. The equations should just create a feasible solution space for non-collsion solutions.
Thanks in advance.


texts: Spotting the difference between two arrays using divide-and-conquer

texts:
Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index.

For simplicity, assume we can use two subroutines that can sum any subarray in our first and second arrays, respectively.

How would we use this to find a suitable algorithm using a divide-and-conquer approach? And if so, how many times would it have to call the subroutines? I assume we can start by dividing our arrays into two and solving our problem recursively from there.


texts: Are there any algorithms for extracting functions from expressions?

texts:
Suppose you have an expression like this:

sqrt(x) * 6 + sqrt(x + 1) * 6 + sqrt(x + 2) * 6

Are there any well-known or published algorithms that can find the repeated partial expressions and extract a function like this?

let f(x) = sqrt(x) * 6
 in f(x) + f(x + 1) + f(x + 2)

I imagine there are some clever schemes in either the automatic vectorization literature or in automatically finding duplicate code. This is also somewhat similar to common subexpression elimination.


texts: NP-hardness of maximum set cover with even/odd coverage requirement

texts:
Given universal set $U=X \cup Y = \{x_1, \ldots, x_{n_1} \} \cup \{y_1, \ldots, y_{n_2}\}$ where $X \cap Y = \emptyset$
and sets $\mathcal{S}=\{s_1, \ldots, s_m\}$ such that $s_i \subseteq U$ for all $i=1,\ldots,m$ and integer $k \in \mathbb{Z}^{+}$.

Find $\mathcal{C} \subseteq \mathcal{S}$ (denote $Z = \cup_{s \in \mathcal{C}} s$) that maximizes

$|\{ z \in Z \mid (z \in X \text{ and is covered even times by } \mathcal{C}) \text{ or } (z \in Y \text{ and is covered odd times by } \mathcal{C} )\}|$

s.t

$|\mathcal{C}| = k$

In other words, we consider an element to be covered if it satisfies the odd/even coverage requirement according to its membership ($X$ or $Y$).

This problem differs from the standard maximum set cover in the definition of "covering an element".

Is this problem NP-hard? Is so, how to prove it?


texts: What is the maths name for a set which contains the Domain and Codomain of a function?

texts:
Im interested in this so that I can name a type parameter in a program I'm writing.

There is function that that has three parameters.

D, Domain

C, Codomain

X, where D is a subset of X and C is a subset of X

What is the special name for X, if there is one at all?

This is interesting from a program security prespective as by setting X we can constrain information to only flow within X.

Maybe I should be using category theory names here instead? If so what would these names be?


texts: How to convert finite automata to regular expressions?

texts:
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and sometimes the resulting expressions are messy.

What algorithms are there for converting NFA into equivalent regular expressions? Are there advantages regarding time complexity or result size?

This is supposed to be a reference question. Please include a general decription of your method as well as a non-trivial example.


texts: How to Apply Elementary Axioms from Kleene Star to an Inequality

texts:
Axioms For *

\begin{align}
1 + aa^* &\leq a^* \\
1 + a^*a &\leq a^* \\
b + ax &\leq x \to a^*b \leq x \\
b + xa &\leq x \to ba^* \leq x \\
\end{align}

Elementary Results

\begin{align}
a \leq b &\to a + c \leq b + c \\
a \leq b &\to ac \leq bc\, \wedge\, ca \leq cb \\
a \leq b &\to a^* \leq b^*
\end{align}

Problem

Prove the following identity in a Kleene algebra using only the axioms
    and elementary results. $$(a + ab + b)^* = (a + b)^*$$

Solution:
\begin{align}
  (a + b)^* &= (a + ab + b)^* \\
  (a + b)^* &\leq (a + ab + b)^* \\
  1 + (a + b)(a + b)^* &\leq 1 + (a + ab + b)(a + ab + b)^* \\
  (a + b)(a + b)^* &\leq (a + ab + b)(a + ab + b)^* \\
\end{align}

Quesiton

So for them to be equal the sets should be contained in each other. At which point do I transition to an inequality?
Is it right to say a $*$ cannot be removed since it has no inverse?
Can I distribute into a $*$? Say $(a +b)(a + b)^*$ or do they need to have the same $*$ height?

Some hints to get further would be greatly appreciated.


texts:
I am currently watching a lecture on Bloom filters, and the professor is doing a heuristic analysis of Bloom filters.

It's all based on the following assumption:

  All $h_{i}(x)$'s are uniformly random and independent (across different $i$'s and $x$'s)

Setup:

Bloom filter of length $n$ bits.
Data set $S$ is inserted into the Bloom filters.

The professors claims that for each bit of array $A$, the probability that it has been set to 1 is (under above assumption, and after data set has been inserted): $1 - (1 - 1/n)^{k|S|}$, where $k$ is the number of hash functions.

I am trying to understand why that's the probability.

He explains that as each of the $|S|$ objects gets inserted (0 or 1), there are $k$ "darts" thrown uniformly at random and independent from each other thrown into the array, so that gives me the intuition of why $k$ is being multiplied by $|S|$. He then says the probability that a given "dart" is one of the $n$ bits is $1/n$. Since there are a total of $k|S|$ "darts" thrown at the end, it makes sense that after the whole set $S$ has been inserted, the probability that a given bit has been hit is $(1/n)^{k|S|}$, and the probability that it hasn't been hit is $(1-1/n)^{k|S|}$. But I don't understand why all that is being subtracted from $1$ at the end to end up being $1 - (1 - 1/n)^{k|S|}$, so clearly I'm missing something...

Can somebody explain this to me?


texts:
Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$?  What's known about the complexity class of this problem as a function of $n$?

Perhaps I'm missing something trivial here, but other than listing some recurrent definitions of this function and some of their asymptotics, I don't see this precise information (complexity class, and known algorithms with their runtime/space complexity) in either of these articles:

Partition (number theory)
Partition function (number theory)


texts: what does it mean by problem of size $0$?

texts:
I am having problems understanding a basic concept in CLRS, it is about worst case partitioning during quicksort --

  The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with $n − 1$ elements and one with $0$ elements.

What does it mean by subproblem of size $0$? But what I see is there will be two subproblems, one with size $n-1$ and another with size $1$. I fail to grasp the idea of $0$ size.

Can someone explain?


texts:
In my last exam this question got asked and i just cant find a clear answer:

If P=NP, which two languages are NOT NP-complete?

So I assume there are two special languages, but which?

Thanks in advance


texts: Where does the base come from in a subsequence count?

texts:
If sequence X has m symbols, then X has 2m possible subsequences.

Where does the base (2) come from?

The origin of this question is the following paragraph:

  We are given two ordered sequences of symbols, and we wish to find a longest common subsequence of $X$ and $Y$.

  A subsequence of $X$ is just $X$ with some (or possibly all
  or none) of its elements removed. For example, one subsequence of A; B; C; D; E; F; G would be B; C; E; G.

  The length of a longest
  common subsequence of $X$ and $Y$ gives one measure of how similar these
  two sequences are. For example, if the two sequences are base pairs in
  DNA strands, then we might consider them similar if they have a long
  common subsequence.

  If $X$ has $m$ symbols and $Y$ has $n$ symbols, then $X$ and
  $Y$ have $2^m$ and $2^n$ possible subsequences
  respectively.


texts: Expressing statements on elephants in propositional logic

texts:
If I wanted to create a sentence like:

  African elephants can carry coconuts; Asian elephants cannot.

How would I do that with propositional logic?


texts: Proving a language is not decideable using a reduction from Busy Beaver?

texts:
I was given this function:
$F(n)$ returns the smallest TM (measured in number of states) such that on input $\epsilon$, the TM makes at least $n$ steps before eventually halting ($n$ is a natural number). I was asked to prove that this function is uncomputable using a reduction from the Busy Beaver. I'm still new to reductions and after sitting on this problem for a while I've gotten nowhere. I'd appreciate any help/guidance.


texts: Algorithm for dividing items into buckets while minimizing total weight

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

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

For example, if our rocks are

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

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

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

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

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


texts: If P=NP, are there cryptosystems that would require n^2 time to break?

texts: If P does equal NP, will it still be possible do design a cryptosystem where the optimal cryptanalysis algorithm takes, say, the square of the time taken up by the legitimate encryption and decryption algorithms? Do any such algorithms already exist?


texts: Some questions regarding methods for solving pushdown automata problems

texts:
I have found some problems whose solving "patterns" appear quite recently, and I am not sure if the way I'm solving them is the most correct/efficient one:
For example, take this language:
$\{w | w\in\{a,b,c\}^* \text{ with }|w|_a=|w|_b \text{ or } |w|_b=|w|_c\}$
The solution would be as follows, where $\\\$$ is the bottom of the stack, and $\epsilon$ the empty string:
The top part is $|w|_a=|w|_b$ and the bottom is $|w|_b=|w|_c$
Taking the top part as an example (the other one is almost identical), what I do is to push $A$ whenever $a$ is read and $A$ is in the top of the stack, or remove $B$ if $B$ is in the top.
Whenever $b$ is read, I push $B$ if I don't find any $A$'s, or remove an $A$ if it's found.
Then, the rest of the characters without restrictions are read between those, leaving the stack alone.
The string would be accepted if input stops and the stack is empty.
I am not sure if this is the most graceful solution since I basically cram all possible cases in one state, though I think this works. This pattern is used basically whenever I find a restriction such as $|w|_x=|w|_y$

The other pattern I found that I'm unsure about is the following one, taking this language as an example:
$\{a^nb^m | n=3m\}$
In this one, I push one symbol into the pile only whenever 3 consecutive $a$'s are read, which will be then equal to $m$ and be consumed by reading $b$'s, accepting the string again if input is done and the stack is empty.
In these cases, I create a series of states where there is only one symbol pushed (when we enter into them), and the rest force to read a certain number of symbols without pushing of popping anything.
I am uncertain if this is the good way to do it. What if it were to be $n=56m$, would I need 55 sub-states?


texts: Is the language of all ucv with u ≠ v context-free?

texts:
Is $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^* , w_1 \neq w_2 \}$ a CFL?

In my opinion it is not since if we want to know the inequality of $w_1$ and $w_2$ we must be aware of their equality and that is not a $CFG$.


texts: Proving Big Omega of a polynomial without limits

texts:
Here is the definition of $\Omega$:

  $f(n) = Ω(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for all $n\ge n_0$.

Here is one theorem:

  If $f(n) = a_m n^m + \cdots + a_1 n + a_0$ and $a_m > 0$, then $f(n) = \Omega(n^m)$.

I want to prove this, without using limits. Despite many hours of searching across the internet, all I could find is proofs using limits. Is there any other way?


texts: Which of the boolean expressions is a max-/minterm?

texts:
I have a exercise where I have to decide whether a term is a max-/minterm and reduce the expression to its corresponding max-/mintern or neither of them and for the following expression I do not know the answer, so could you help me out here.

$!X$ (I think both but what would be the reduced expression)
$Y$ (I think both but what would be the reduced expression)
$X \land (Z \land Y \lor (!Z \land Y \lor !Y)) $ (I think neither of them)

Important is that every expression consists of all existing variables, e.g. the second expression has $only$ the variable $Y$, $X$ and $Z$ do $not$ exist in this expression.
If one of them is a maxterm and/or minterm, could you reduce the expression to its corresponding max-/minterm?


texts: Given a set of points, find the one closest to a given point

texts:
So, I'm given an arbitrary set of points $(p_1, p_2, p_3,\ldots)$ with an $x$ and $y$ coordinate. I have no information about the order they're given to me.

I need to write code that will take in a point, $p_0$, and will find the point $(p_1, p_2, p_3\ldots)$ closet to $p_0$. This will of course be found my minimizing $R$ in $R^2 = (x - x_0)^2 + (y - y_0)^2$.

I could implement this easily if I linearly search the list of points each time (always $O(n)$ complexity). However, I would prefer something that could be an average of $\log(n)$ complexity. Does anyone have a suggestion on a search algorithm?


texts: Prove the following language is regular using closures

texts:
How can I prove this language is regular using just closures and homomorphism?
$$
L = \{a_1b_1a_2b_2\dotsm a_nb_n \mid a_i \in L_1 , b_i \in L_2\}
$$
and we know $L_1$ and $L_2$ are regular.


texts: What data structure should I use for storing my data?

texts:
I am currently looking for a way in which I can store my data, and quickly look it up.

What currently seem to be the best idea is to use a hash map.

reasons:

To identify what item I am looking for, one need to extract a certain
set of features from the data, which can be used as a key to extract
the item.

Problem here is that the features could contain noise,
   making the key <-> item match not 100% perfect.

In such case I need to find the key which matches the feature set the best? Or a set of keys which matches the feature set the best. But how do i do that?

The feature vector is 512 long.

sorting would be a possibility? but how should I sort such a matrix?

And given the complications I am facing, is using a hash map the right choice? or is something better?


texts:
I'm trying to separate a weird relationship. It goes like this:

One waiter can serve more than one kind of drink and one kind of drink can be served by more than one waiter.
One waiter can wear more than one kind of shirt (eg different uniforms daily, or random uniform assignments, etc), and one kind of shirt can be worn by more than one waiter.

There are two many-to-many relationships here that share the waiters, but can be separately resolved. But because they share the waiters entity, then many kinds of drinks can be served while wearing many kinds of shirts.

The relational model looks like this:

My question is, how do I resolve this? It doesn't look like it lends itself easily to being decomposed into one-to-many relationships.

Edit: I changed the image to fit in better with the description, but the problem that results here is the waiter-drinks and waiter-shirt entities still exist as a result of normalizing the drinks and waiters relationship (that is many-to many) and the waiter and shirt (also many-to-many). The resulting entities then have a many-to-many relationship as waiter-drinks and waiter-shirt.

Where am I wrong?


texts: Computer vision: Why do random filters perform similar to edge detectors?

texts: I read here that "a randomly initialized filter acts very much like an edge detector!". I want to know if there are any papers describing and explaining this phenomenon.


texts: Help in understanding the implementation/application of scope trees

texts:
I’m learning (self-taught) about language implementation and compiler design, and I’m implementing a toy language to cement the concepts in my mind. However, I’m having trouble understanding how scope trees are meant to be used.

In my toy language, I’m using the Visitor pattern to traverse the syntax tree as a simple interpreter. I assign a pointer to a given symbol table to a member of the syntax node to make the various symbols available at “run time”. The symbol tables are hash tables on a stack, and I resolve symbols defined in a parent scope by inspecting the stack.

But the literature I’ve read (specifically Language Implementation Patterns by Terence Parr) talks about a scope tree as a distinct tree structure, like the syntax tree, and traversing the scope tree. Does a scope tree stand separately and alongside the syntax tree, and if so how does one track the current position in the scope tree while traversing the syntax tree? Is it simply a global pointer to a scope node/symbol table that’s adjusted whenever a scope-affecting node is encountered in the syntax tree? Or, Is it okay for the scope tree’s tree structure to be implicitly defined by piggy-backing the syntax tree as I have done? I feel I am polluting the syntax nodes definitions by adding a symbol table member.


texts: Searching for an item over a non-uniform query distribution

texts:
If I have a static set of $n$ items in a database that are all queried with uniform probability it makes sense to put them in a binary search tree. This way any given search will take, on average, $O(\ln n)$.

What happens now, if the items are not queried uniformly? As a silly example, say that one item is queried 1000 more frequently than any other item. Would it make sense check for that item first and independently, before looking in a search tree of the other items (the so-called LenPEG method)?

For concreteness, let's say the items are queried with a likelyhood that is static, and drawn from a Poisson distribution. What would be the optimal way to structure the data so that the average search time is minimized?


texts:
Let $n \in \mathbb{Z^+}$. Find, with proof, the number of distinct graphs with the
vertex set $V = \{1, 2, \ldots,n\}$. We say two such graphs are distinct if one of them has an edge $(u, v)$ and the other one does not have this edge with the same vertices.


texts: Algorithm to estimate the probability that a "0 and 1 matrix" fills up following the bootstrap percolation rules

texts:
Presentation of the model: we consider the regular lattice created from $\mathbb{Z}^2$ (It's no more, no less a square lattice).

At $t=0$, each site is said "active" independently with a probability $p$, "inactive" otherwise.
At $t$, if a site is inactive, it becomes active if at least $2$ of its neighbours are active.

We call neighbour of $x$ each element of $V(x)=\{y\in\mathbb{Z}^2, ||x-y||=1\}$ (or, if I have a matrix M in python, a neighbour of $M[i][j]$ is $M[i\pm1][j]$ or $M[i][j\pm 1]$).

My problem: I consider a $n\times n$ matrix filled with 0s and 1s, (0 = inactive ; 1 = active), and I want to estimate the probability $p_c$ that a matrix, following the rules above, fills up (at $t\rightarrow \infty$, but this happen really fast in reality). The probability $p_c$ depend on $n$. I want to test it for $n=2$ to $n=100$ at least.

What I already have: I have a program, matrix_creation(n,p) that creates a $n\times n$  matrix with the probability $p$ for each coefficient to be 1, and another, test(M), to test if "M" fills up.


texts:
Lets suppose that 20 percent of the instructions in a program are branch instructions.The static prediction of the jumps supposes that the jumps don't happen.

I should find the execution time in two cases : When 30 percent of the branches happen and when 70 percent of the branches happen I also should find the speedup of one case compared to the other and express it in percentage.

Thing is,how do I find the execution time here ? I usually find the execution time where the pipeline is separated in different phases and there is given the time for each phase ....

Edit : This is NOT homework.I found this in my computer architecture textbook and its not a familiar exercise.


texts: Is there a way to convert a program into a Boolean formula?

texts:
Let's say I have a program P, in form of a binary code for x86 architecture.

I want to find a Boolean formula F (in form of CNF, or something like that), such that

F(input,output) = true iff P(input) = output

So to answer a question "what output does the program produce on given input" I will only need to run a SAT/SMT solver for X on formula

F(input,X) == true.

I understand that this problem is undecidable in general case, but I only care for some practical cases.

What keywords should I google to find more about this topic?


texts: Finding the number of distinct strings in regular expression

texts: Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from looking at the regular expression? Do I have to generate a table of all possible combinations or is there a more straightforward way?


texts:
I am trying to understand A star algorithm. I am aware that it follows the sum of the current cost and heuristic, therefore f(n) = c(n) + h(n) in order to expand a new node. So every time the code with the smallest f(n) from the root is expanded. However, I am confused about the backtracking of the algorithm when it does not find the best solution. I tried to follow the example explained here. Therefore, by only using the f(n) the algorithm should have expanded: S-B-C-G. Firstly B then C and then G. Then declare that find a solution. How, the backtracking works?

The example is as follows:

In the left, there is the graph and in the table is the heuristic cost. What is going to be the a star expand in this graph?


texts: Algorithmic type checking for Calculus of Inductive Constructions

texts: So from reading "Advanced Topics in Types and Programming Languages" (ATTPL) I know of the calculus of constructions (CoC). It also presents the "algorithmic" type checking rules. Reading Coq's documentation on the Calculus of Inductive Constructions (CioC) you can get a sense of things but it is far from algorithmic. Is there any reference on algorithmic type checking for CioC?


texts: Show that f(x,y)=x+y (with |x|=|y|) isn't a one way function

texts: I have to prove that the function $f\colon \mathbb N × \mathbb N \to \mathbb N$ defined by $f(x, y) = x + y$ and $|x| = |y|$ isn't a one-way function. How do I go around doing that?


texts:
suppose for $n$ elements we using mergesort.
each number compared at most $O(\log n)$ = False
in average each element compared with $O(\log n)$ elements = True
there exist an element compared with $\Omega (\log n)$ elements = True
is there anyone can share idea about these facts (i.e: why first is false and others is true).