texts: Doubts on Virtually Indexed,Physically tagged Cache

texts:
I tried referring a few material (videos on youtube and this link as well), but I still couldn't wrap my head around the concept.
My (brief) understanding of the Virtually addressed, Physically addressed and Virtually indexed Physically tagged cache:

Virtually addressed cache
The virtual address generated by the CPU is used to perform a cache read/write. In the case of a miss the address is translated into a physical address and the appropriate data is loaded into cache and the cache directory is updated. The Translation Look-aside Buffer (TLB) is only used during a cache miss, i.e. when the virtual address is to be converted to a physical address. The cache directory stores a virtual tag.

Physically addressed cache
The physical address acquired from the TLB translation of the virtual address (virtual number + page offset => physical number + page offset) is   utilised to perform a cache read/write. The tag stored in the cache directory is the physical tag.

Virtually indexed, Physically tagged cache
The virtual address is forwarded to both TLB and cache. The cache uses the index from the virtual address and finds the corresponding physical tag from the cache directory, the TLB finds the corresponding physical tag from the virtual address and the two tags (from cache directory and TLB) are compared to check if it was a hit/miss.

From what I understood, the cache index and block offset values derived from the logical address could either be equal (with respect to size) to the page offset or not, i.e the page offset either contains the index and block offset or not.
When the size of the index plus block offset do not equal the page offset, wouldn't the size of the physical tag of the cache directory not match the physical tag of the TLB ? And if that is true, how are the physical tags from the cache directory and TLB compared ? Further more, I also could not understand how Virtually indexed, Physically tagged cache could have the synonym problem when the size of the index plus block offset dont match the page offset.


texts: Finding a method to classify pixels according to how drastic their intensity change

texts:
I am looking for a method to classify pixels into three groups: (1) Pixels which does not change their intensity much in general (the slight changes may be due to noise only), (2) Pixels which change their intensity very slowly, in general monotonically and gradually, and (3) Pixels which change their intensity drastically over a certain threshold.

I tried using the Running Gaussian Average Method, such as checking how many standard deviations the current pixel is away from the running mean. The pixel is classified as group (1) when the result is very small, as group (3) when the result is very large, and (2) otherwise. But it does not seem to work very well, especially for group (2) because by definition, this group contains pixels which change their intensity moderately instead.

I expect I may need to build 2 or more models, because background subtraction methods normally result in classifying the pixels into 2 groups only, but here I need to classify pixels into 3 groups. Any ideas will be welcome. Thanks!


texts: Product of the entries of the product of two matrices

texts:
Let $A=(a_{ij})$ and $B=(b_{ij})$ be $n \times n$ integer matrices. Then $AB=(\Sigma_{k=1}^n a_{ik}b_{kj})_{ij}$. I am interested in finding the most efficient algorithm for computing the product of the entries of $AB$,

$\Pi_{i,j=1}^n (\Sigma_{k=1 }^n a_{ik}b_{kj}$).

Certainly, the most straightforward way of doing this (by using the above formula) is not the most efficient way of doing this, since there are algorithms like Strassen's algorithm which calculate all of the entries of the matrix $AB$ faster than simply applying the definition $AB=(\Sigma_k a_{ik}b_{kj})_{ij}$ to each entry.

Are there other efficient ways to compute the above product besides using algorithms like Strassen's algorithm?

Extra: What about computing the sum of the entries of $AB$,

$\Sigma_{i,j,k=1}^n a_{ik}b_{kj}$?


texts:
While doing some bibliography on term-rewriting, I often found these two properties to define a term rewrite rule (see for example here and this one):

  A term rewrite rule is a pair $\langle l,r\rangle$ of terms, written $l \rightarrow r$, such that

  1) $l$ is not a variable

  2) all variables in $r$ occur also in $l$.

I fail to understand the reason of these properties, at least for the definition of a rule (I can see why they would matter for termination or confluence proofs). Why a term rewriting system could not contain a rule such as $x \rightarrow x + 1 - 1$ or $x \rightarrow x + y - y$ ? Just to provide some context, I'm trying to use TRS in the context of obfuscation, where such rewritings have meaning.

Can someone explain why rules composing a TRS would need these properties?


texts:
I want to know what is algorithm and time complexity of Hanoi tower with forbidden direct move from source to destination (it means you cannot move disk from source to destination directly and you instead of that should first move disk from source to middle and then from middle to destination) and other rules as normal problem?

I didn't find any article about it.


texts: First problem to be considered np complete?

texts: What is the first problem that was demonstrated to be NP-Complete?


texts: Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language

texts:
For regular languages $A,B\subseteq\{0,1\}^*$, is

$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$

regular, where $|x|_1$  means the number of appearances of 1 in the word $x$?

i need to demonstrate $L_2$ automata.

Thought about using the multiplication automata, not so sure.


texts: How can I prove that if $\chi(G) > k \wedge \vert\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}\vert$ then $G$ has a $k-regular$ induced subgraph?

texts:
I have found an interesting exercise in my introduction to graphs workbook:

Let $ad(G) = \frac{2\vert E(G)\vert}{\vert V(G) \vert}$ and $mad(G) = max\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}$.

Given a graph $G$ and a number $k \geq 3$, prove that if $\chi(G) > k \wedge mad(G) \leq k \Rightarrow \exists A \subseteq V(G)$ such that $[A]_{G}$ is $k - regular$.

I believe this can proved by contradiction:

Given a $G$ and $k$ for which the properties hold, we assume that $G$ has no induced subgraph $H$ that is $k - regular$. We then prove that if $\nexists H$ then at least one of the property is false and thus we contradict ourselves however I can't quite figure out the connection between $H$ and the mentioned properties.

How would you go about solving this?


texts:
I came across this explanation for count to infinity problem

However, i don't understand that after the BC link broke, followed by which B erroneously updated the path to C at a cost of 3; Now why will A update the cost to C as 4 (after getting updates from B) since its current cost to C is 2 which is lesser than that advertised by B?


texts: Does adding S->SS in a context-free grammar change the language to its Kleene star?

texts: Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^*$, why? What about grammars in Chomsky normal form?


texts:
I am trying to solve an equation which I believe cannot be done analytically, but can use a numerical approximation to get a result. The equation is:
$$\frac{2*\sqrt{\pi}*h*s*e^{m^{2}/(2*s^2)}}{\sqrt{2}} = a$$
where $h, m,$ and $a$ are given constants. This is for a project that I'm writing in Java, and it would be infeasible to grab the solution output from another program such as Matlab, Mathematica, or some other scientific computing language for a couple reasons, one of which is that I will have to solve this equation hundreds of times with different values. Basically I am wondering if anybody knows of a library I can easily import and use for this kind of problem, and to possibly spell out how I would go about doing that. So far I have been looking through math libraries such as Apache Commons Math but cannot find out if they are appropriate. Thanks!


texts: Interval density of time bounded Kolmogorov complexity

texts:
The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to produce $x$:

$C^{t}(x) = \min \{|M| : U(M) = x$ in less than $t(n)$ steps $ n = |x| \}$

And for a nice function $f(n) < n$ we can define:

$C[f(n),t(n)] = \{x : C^t(x) \leq f(n), n = |x| \}$

i.e. the set of compressible strings $x$ (whose compressed program has size less than $f(n)$) and that can be generated in time $t(n)$.

For example, for unbounded $f$, we have $C[f(n),n^k] \subseteq C[f(n),n^{k+1}] \subset C[f(n),\infty]$

Is the first inclusion tight?
What is known about the *size* of $C[f(n), n^{k+1}] \setminus C[f(n), n^{k}]$ ?
Are there known results for particular classes like $C[n/2,n^k]$?


texts: What would be the real-world implications of a constructive $P=NP$ proof?

texts:
I have a high-level understanding of the $P=NP$ problem and I understand that if it were absolutely "proven" to be true with a provided solution, it would open the door for solving numerous problems within the realm of computer science.

My question is, if someone were to publish a indisputable, constructive proof of $P=NP$, what are some of the immediate effects that we would see of such a discovery?

I'm not asking for opinionated views of what the world would look like in 5-10 years.  Instead, it is my understanding that this is such a fundamentally unsolvable problem that it could radically change the way we compute... many things (yeah, this is where my ignorance is showing...) that we can't easily calculate today.

What kind of near-immediate effect would a thorough, accurate, and constructive proof of $P=NP$ have on the practical world?


texts: Why is ${n \choose 2}$ a $\Theta(n^2)$ computation?

texts:
In Cormen's Algorithms textbook, the author casually mentions that ${n \choose 2}$ is $\Theta(n^2)$.

Why is this so? In the calculation

$$
{n \choose 2} = \frac{n!}{(n-2)!2!}
$$

there are $n$ multiplication operations in the numerator and $n$ multiplications in the denominator. That means there are at most $2n+1$ computations to here make (one for the division step), no?


texts: Interpolation for maximum likelihood estimate of unigram and bigram

texts:
We are given the following corpus, modified from the one in the chapter:

<s> I am Sam </s>
<s> Sam I am </s>
<s> I am Sam </s>
<s> I do not like green eggs and Sam </s>

If we use linear interpolation smoothing between a maximum-likelihood bigram model and a Maximum-
Likelihood Estimate unigram model with λ1 = 1/2 and λ2 =1/2, what is P(Sam | am)? Include <s> and
</s>\verb in your counts just like any other token.


texts: Linear Programming: algorithm to check if ratios can be combined with n bottles to equal a given ratio

texts:
Say you have n bottles. each with a ratio of $(a_i: b_i: c_i)$.
($a_i/(a_i+b_i+c_i),\cdots$ swap out the numerator for $b_i$ and $c_i$ respectively).

Now you are given a ratio of $(a:b:c)$. Use Linear programming to find an efficient algorithm to this problem. If it's yes, you can output the parts of bottles that gave you the answer. (e.g. 2 parts from one bottle, 1 part from another bottles.)

So it's not clear how to do this. One of my first thoughts was to make a variable $z = \sum(\alpha_i*(a_i,b_i,c_i)) - (a,b,c)$. This, I'm thinking could be the objective function we minimize.

Not sure if this works. Or if it does, where to go from here. Also, I'm not sure if I can have the alphas in the thing I'm trying to minimize. What am I supposed to do with these alphas.

Not sure what it means by algorithm either. That is, even if I could set up the problem as a linear problem, not sure what the algorithm would be.


texts:
I know that:

  Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers

Does this logic hold for higher $k$'s? That is, does following fact hold?

  Point 2: Set of languages accepted by $LR(k)$ parsers $\subset$ Set of languages accepted by $SLR(k+1)$ parsers, for $k=1,2,...$

Also I have just came across the fact that every $LR(k)$ language is parseable by $LR(1)$ parser. So, I guess, point 2 seems trivial for $k>2$ and all we need to prove is:

  Whether $LR(1)\subset SLR(2)$ ?

Is it so?

PS: I have not read this paper and dont know if it is related, but linking it anyway: SLR(k) covering for LR(k) grammars


texts: Starvation in longest remaining time first CPU scheduling

texts:
I want to know if longest remaining time first (LRTF) CPU scheduling has starvation or not. Also give reason how it starve/does not starve a process.

I know longest job first (LJF) may starve a process if all other incoming processes have longer CPU burst.


texts:
I have a treap like the first image and I want to reach the second image to restore min heap order property. I can't understand which kinds of rotations have been done.

Image 1

Image 2


texts: Shortest path tree from each vertex implies a unique MST?

texts:
Given a connected, undirected graph G, edge-weighted (positive), prove that

If G has a spanning tree T which, for each vertex r in G, is a shortest path tree from r, then G has a unique MST.

I know how to show that given a T like that, it is also a MST, but how  can I show that it's unique? I tried to assume by contradiction that it isn't, but I can't see how to get a contradiction from that


texts: can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this video and i am not able to understand the proof


texts:
I am interesting in proving that there is no search problem that is polynomial bounded and  self-reducible, as long as ${\sf P} \neq  {\sf NP} \cap {\sf coNP}$.

The problem is I don't know how to approach the proof, below I wrote few ideas with open questions.

We can start by denoting the search problem in set ${\sf NP} \cap {\sf coNP}$ in terms of search problem relations $R_1$ and $R_2$ such that $S = \left \{ x:R_1(x) \neq \emptyset \right \}  = \left \{ x:R_2(x) = \emptyset \right \} $. But how to present that the decision problem $S$ is not in ${\sf P}$. I don't know (but it seems to be crucial to show that $S$ is not in ${\sf P}$).

Having defined $S$ the next step would be to show that there is a relation $R$ that is self-reducible to $S$, but is not polynomial bounded.

In short, the question is how to define relation $R$ that is self-reducible to $S$. How to prove that $R$ is not polynomial bounded. Actually proving that $R$ is polynomial bounded may be redundant because $S$ is in ${\sf NP} \cap {\sf coNP}$ and it's given that ${\sf NP} \cap {\sf coNP} \neq {\sf P} $.

Addendum: I was given a hint

$R = \left \{ (x,1y):(x,y) \in R_1 \right \} \cup \left \{ (x,0y):(x,y) \in R_2 \right \}$

If I will be able to show that search problem relation R is self-reducible to S, than I think the problem is solved.


texts: I am having problems with algorithms, particularly solving them using recurrence. can anyone suggest an easy to understand basics introduction to this so that I can get my head around the concept.


texts:
Here is a question I encountered:-

Read this section of program code that inputs 10 positive numbers and then outputs the smallest number input. Identify three changes you would need to make to find the largest number input instead of the smallest number.

    Small = 1000
    Counter = 0
    REPEAT
    INPUT Num
    IF Num < Small THEN Small = Num
    Counter = Counter + 1
    UNTIL Counter = 10
    PRINT Small

The question refers to a vague 'program code'-which I do not know of. Neither does this seem like pseudocode due to presence of the equals sign as an assigning operator instead of the arrow '←'.Clearly, not a low-level programming language. So what is it?

Note:I am high school student. This code is part of the 0478 Computer Science IGCSE curriculum here:http://www.cambridgeinternational.org/programmes-and-qualifications/cambridge-igcse-computer-science-0478/past-papers/
If anyone of you know about what this code is and why it is used as part of this IGCSE, please include that in your answer.


texts: Proving parametricity for Gallina functions

texts:
I have the following definitions

Definition nat'' {X : Type} := (X -> X) -> X -> X.
Definition nat' := forall (X : Type), @nat'' X.

And when I wanted to prove a certain property I ended up in the following situation:

  m : nat'
  H : 0 = m nat S 0
  X : Type
  s : X -> X
  z : X
  ============================
  m X s z = z

which should be some kind of free theorem! Specifically, m: (forall X : Type), (X -> X) -> X -> X is a function that should behave parametrically for any instantiation of X, so by knowing that 0 = m nat S 0 I should be able to deduce that x = m X f x for any x : X and f : X -> X.

But I haven't seen such free theorems stated in Coq for Gallina terms. Is there an easy way to go about proving such a result without some deep embedding of a language and proving parametricity for this language?


texts: How to ensure data integrity in General Purpose Registers (GPR registers) given their limited number (for x86 their number is 6),and on the other hand that they are used simultaneously by all processes?


texts: Algorithm to find a path connecting given nodes in a graph

texts: Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for such a scenario?


texts: Zero-knowledge proof of intractibility of NP-complete problems

texts:
I am not an expert in Zero-knowledge proofs and I am interested in its applicability to general mathematical proofs.

Suppose we're willing to assume that NP-complete problems are intractable and require exponential time algorithms.

Can we construct a zero-knowledge proof of the intractability of Hamiltonian cycle problem, under this assumption? Is it possible without assuming the existence of one-way functions?


texts: How can I produce a summation function from this set of production rules for a grammar?

texts:
I am not entirely sure if the title is the correct way to phrase what is occurring. There is a recurring process which I decided to attempt to model using production rules similar to those used in a context-free grammar.

The real world process is a production line. It takes 1 unit, after 2 weeks, produces 1 unit, after 4 weeks, that unit will produce another unit - and also 2 of the starting units. After 4 weeks the "another unit" will produce "that unit" - and also 3 of the starting units. This continues semi indefinitely, but the range I am looking at is roughly 52 weeks.

I came up with this model of production rules

$S\rightarrow A$

$A\rightarrow S^2B$

$B\rightarrow S^3A$

I attempted to expand this so that I could formulate a generating function and solve for n=52 (52 being the 1 year mark).

$S$,$A$,$S^2B$,$S^5A$,$S^7B$, ...

However, I was unable to determine if I was taking the correct approach to solving this situation. I believe that an error here lies in the fact that the duration of time is ignored. Namely that from $S\rightarrow A$ 2 weeks elapse, from $A\rightarrow S^2B$ 4 weeks elapse, and from $B\rightarrow S^3A$ 4 weeks elapse.

In order to better understand this situation, I decided to code an example so I could at least see the totals. However, it did not lend itself to producing a summation function.

So, given all this, how is it possible to come up with a summation function instead of having to manually iterate through it like this c# approach does? Or, is there a similar/alternate approach to modeling this which will allow an easier summation process?

Please feel free to correct any misunderstandings I may have.

edits

For example:

Week 1: We have 1 unit (S). It sits for 2 weeks until it is ready to become 1 of the next type(A).

Week 3: The first unit is now here. It sits for 4 weeks until it is ready to become 1 of the next type(A). At that time, it also becomes 2 of the first type(S).

Week 7: The unit from Week 3 has now become 2 of the first type of unit(S). It also created 1 of the second type(A). The 2 units of type S will now sit for 2 weeks until they make 2 units of type A. The 1 unit of type A will now sit for 4 weeks until it makes 1 unit of type B and 2 units of type S.

Week 9: The 2 units of type S from week 7 have now sat for 2 weeks. Now they have become 2 units of type A. These two units of type A will sit for 4 weeks and produce 4 units of type S and 2 units of type B.

Week 11: The 1 unit of type A from week 7 has now sat for 4 weeks and has now made 1 unit of type B and 2 units of type S. The 1 unit of type B will sit for 4 weeks and then make 1 unit of type A and 3 units of type S. The 2 units of type S will now sit for 2 weeks and make 2 units of type A.

Also, the 2 units of type S from week 9 have now sat for 2 weeks and become 2 units of type A. These two units will sit for 4 weeks and become 2 units of type B and will also become 6 units of type S.

etc.

This can perhaps be represented by a series of recurring relations

$s(n) = a(n) + b(n) + c(n)$

$a(n) = 2*b(n-4) + 3*c(n-4)$

$b(n) = a(n-2) + c(n-4)$

$c(n) = b(n-4)$

where

$s(n) = a(n) = b(n) = c(n) = 0$ for $n < 1$

$a(1) = 1$


texts: Finding the values of x and y using base 8

texts:
In finding the values of x and y, if  (x567) + (2yx5) = (71yx) ( all in base 8) I proceeded as under.

I assumed x=abc and y=def and followed.

  (abc+010 def+101 110+abc 111+101)=(111 001 def abc) //adding ()+()=() and equating LHS=RHS.
  abc=111-010=101 which is 5 in base 8 and then def=001-101 which is -4
  so x=5 and y=-4

Now the Question is that the answer mentioned in my book is x=4 and y=3.


texts: Difference Between Tree Automata and Tree Transducers

texts:
Wondering what the differences are between Tree Automata and Tree Transducers.

Wikipedia says:

  Tree transducers extend tree automata in the same way that word transducers extend word automata.

And about word transducers it says:

  A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton that maps between two sets of symbols.[1] An FST is more general than a finite-state automaton (FSA). An FSA defines a formal language by defining a set of accepted strings while an FST defines relations between sets of strings.

But I don't understand what the implications are and what the differences really are, even though there is the extra tape. Not sure about the tapes in the Tree Transducers.

All I see so far is tree transducers have the extra "output alphabet" for constructing a new tree (which you plug the state into):

$$ {\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}$$

For instance:

$${\displaystyle q(f(x_{1},\dots ,x_{3}))\to g(a,q'(x_{1}),h(q''(x_{3})))}$$

but the automata have pretty much the same signature, just using the input alphabet only:

$$q(f(x_1,...,x_n)) → f(q_1(x_1),...,q_n(x_n))$$


texts: What can I deduce if an NP-complete problem is reducible to its complement?

texts: Let's say I have a decision problem $D$ and its complement $D'$. I know D is poly-time reducible to $D'$ (its complement). Furthermore, I know $D$ is NP-complete. What is the strongest statement I could possibly make about this kind of relationship?


texts: Call‑by‑name will succeeds where call‑by‑value may fails: some example cases?

texts:
I've landed to SML pages, comparing call‑by‑name and call‑by‑value, asserting the former always succeed while the latter may fails. As this seems counter intuitive to me, I feel at least an example case would be useful.

Call-by-value, call-by-name and call-by-need

  Theorem (Church Rosser 1)

  For a purely functional language, if call-by-value evaluation and
  call-by-name evaluation both yield a well-defined result then they yield the
  same result.

  Theorem (Church Rosser 2)

  If a well-defined result exists for an expression then the call-by-name
  evaluation strategy will find it where, in some cases, call-by-value
  evaluation will not.

What make it counter‑intuitive to me, is that call‑by‑name may re‑evaluate expressions multiple times, which I don't understand how it can make it succeed when call‑by‑value and its one‑time evaluation, would fails. If, as the context is FP and its referential transparency, both expression are supposed to evaluated to the same, how evaluating multiple time may make something succeed or alternatively potentially fails if the same expression is evaluated only once? Unless there are side‑effect somewhere?… is this related to side effects and non‑pure FP?

As a reminder, here is what would look like call‑by‑value and call‑by‑name with SML (if there is an error here, feel free to tell), added call‑by‑need to help not confuse one with the others:

(* This, is supposed to sometime fails… *)

fun call_by_value a =
   a + a  (* `a` is evaluated only once *)

(* …when this is supposed to succeed *)

fun call_by_name a =
   a () + a ()  (* `a` is evaluated for each of its reference *)

(* None of the above should be confused with call‑by‑need: *)

fun call_by_need a =
   let val a' = a ()  (* memoization *)
   in fn () => a' + a'  (* to be evaluated when needed *)
   end

val _ = print (Int.toString (call_by_value 2) ^ "\n")
val _ = print (Int.toString (call_by_name (fn () => 2)) ^ "\n")
val r = call_by_need (fn () => 2) ()  (* memoization *)
val _ = print (Int.toString r ^ "\n")


texts: Lower Bounds for the Set Disjointness Problem

texts:
Consider the set disjointness problem. Alice and Bob hold n-bit strings $a$ and $b$ respectively.
They would like to compute the function
$$
\text{Dis}(a,b) =
     \begin{cases}
       0 &\text{if } \exists i : a_i = b_i = 1 \\
       1 & \text{Otherwise}\\
     \end{cases}
$$

It is well known that this problem has communication complexity exactly $\Theta(n)$ (see here for example).
This means that it cannot be solved with communication overhead sublinear in $n$.

Many times this result is informally stated as "Computing disjointness has communication overhead linear in the size of the inputs"

Question:
How do I go from the formal definition and result for set disjointness to the informal statement above.
My issue is the following:
Assume Alice and Bob hold sets of 64-bit integers.
In this case writing them as characteristic bit vectors would require them to send around 2^64 bits.
However, clearly I can trivially solve the problem by sending my total set, which would have a communication overhead of $\text{set-size} \cdot 64$.
How is this communication overhead related to the bit-strings of the set disjointness problem?


texts: What is the most efficient way to find bSmooth values in QS?

texts:
The heaviest part of QS is to search for bSmooth numbers.
So far I thought about two algorithms for solving this.

Trial division

calculate $X$ as a product of all the values in the factor base
speed up the trial division with $gcd(X,Y)$ where $Y$ is a potential bSmooth value


texts: Continue on: Prove that $BPP^{BPP} = BPP$

texts:
regarding the following post: Prove that $BPP^{BPP} = BPP$

Let $L\in BPP^{BPP}$, by definition $BPP^{BPP} =\bigcup_{O\in BPP}BPP^O $, therefore there exists a language $A\in BPP$ such that $L\in BPP^{A}$.
This means that there exists a $\mathsf{PTM} $ $M^{A}(x,r)$ such that $\mathbb{P}_{r}(M(x,r)\neq L(x))\leq \frac{1}{3}$, and $M^A$ runs in polinomial time.
In addition, since $A\in BPP_{[\frac{1}{3},\frac{2}{3}]} \subset BPP_{[2^{-n},1-2^{-n}]}$, there exists a $\mathsf{PTM} $ $M'(x,r)$ such that $\mathbb{P}_{r}(M'(x,r)\neq L(x))\leq 2^{-n}$, and $M'$ runs in polinomial time.
I defiened a $\mathsf{PTM}$ $N$, that on input $x$ does the following:
Simulate $M^A$ on $x$ and every time we need to do an orcale quarey $\alpha_i$, we would simulate $M'$ on  $\alpha_i$ and the answer to the query would be the answer of $M'$.
I understand why $N$ runs in polynomial time, but I was stuck in the probabilistic analysis.
This is what I have so far:
If $x\in L$ then $N$ answer correctly iff $M^A$ answer correctly and $M'$ answer correctly about every query, therefore I got:
$\mathbb{P}_{r}(N(x,r)= 1)= \mathbb{P}_{r}(M(x,r)= 1)\mathbb{P}_{r}(\forall i, M'(\alpha_i,r)$is correct$)\geq \frac{2}{3} \prod_{i}(1-\frac{1}{2^{|\alpha_i|}}) $
How can I prove from here that $\mathbb{P}_{r}(N(x,r)= 1) \geq \frac{2}{3}$?
Would appreciate your help:)


texts:
So I'm studying for a midterm and my professor put out a sample exam with the answers, and I'm stuck on one of the questions.

The answer is Big-O(n^2 log n)

Could someone show me the steps necessary to go from regular time complexity to asymptotic time complexity?


texts: How many times can you pour milk among 3 buckets?

texts:
This is a problem from usaco, which I solved, but I don't know how to estimate the number of times you can pour milk among the jugs, my solutions just uses a big enough number.

Here's the problem statement:

  Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

  Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

  For example, if the input is 8, 9, 10 then the output is 1, 2, 8, 9, 10.

  Another example: if the input is 2, 5, 10 then the output is 5, 6, 7, 8, 9, 10.

My approach is to recursively try all possible move sequences, keeping track of the contents of bucket C each time bucket A is empty. Currently I stop the recursion at the arbitrary depth 200. What is the correct depth to stop the recursion at?


texts: What's the theory behind the operator precedences of common operators?

texts: Could for example the precedence ordering of addition, multiplication, exponentiation, boolean and/or and zip/cross product be inferred from a few rules?


texts:
Lets define a counting PDA as equivalent to a PDA except that the transition relation can use the stack size.

Formally, let's define the transition relation as
$\Delta:Q\times (\Sigma \cup \{ \epsilon \}) \times (\Gamma\cup\{\epsilon\})\times \mathbb{N} \to P(Q\times (\Gamma\cup \{ \epsilon \}) )$

Meaning that $(q,\beta) \in \Delta(r,\sigma, \alpha, n)$ means that when the automaton is in state r reading the symbol $\sigma$, the head of the stack contains $\alpha$ and we have n items in the stack, then we can remove $\alpha$ and insert $\beta$ and transition to q.

My question is whether the family of automata created by this definition of a counting PDA is equivalent to family of PDAs.


texts: Relating indexes for parameters and variables

texts:
I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help.

I have the following binary variable

x(r,m) = 1 if referee r is assigned match m

and the following parameters:

time(m,t) = 1 if match m takes place at time t
avail(r,t) = 1 if referee cannot officiate a game at time t

I want to define my x variable to 0, when avail(r,t)=1, but is this even possible?


texts: For every $\mathrm{NP}$ language $L$, is there a verifier such that, for all the certificates $u$ of other verifiers of $L$, it accepts $(x, u)$?

texts:
Let $L$ be an $\mathrm{NP}$ language.
Then there exists a verifier $V$ of $L$ and a polynomial $p\colon \mathbb{N} \to \mathbb{N}$, such that for every $x \in \Sigma^{*}$, $x \in L$ if and only if there exists a certificate $u \in \Sigma^{p(|x|)}$ for $x$ satisfying $V(x, u) = 1$.
Suppose that $\mathcal{V}_{q}$ be all the verifiers of $L$ such that the length of the certificates of $x$ is $q(|x|)$.
And for every $V \in \mathcal{V}_{q}$, let $V_{x}$ be all the certificates of $x$.
For every polynomial $q\colon \mathbb{N} \to \mathbb{N}$ satisfying $\mathcal{V}_{q} \neq \varnothing$, I want to know whether there is a verifier $\bar{V} \in \mathcal{V}_{q}$ such that for every $x \in L$,
$$\bar{V}_{x} = \bigcup_{V \in \mathcal{V}_{q}} V_{x}.$$


texts: How can we prove that an enumerable/decidable group of languages is closed under an operation?

texts:
For example:

If the XOR operation on two languages, A and B, is described as:
$A\;\mathrm{XOR}\;B = (A \cup B) \setminus (A \cap B)$,

1) How can we prove that the set of enumerable languages is closed under the XOR operation?

2) How can we prove that the set of decidable languages is closed under the XOR operation?


texts: Divide an array into two sub arrays such that their sums are equal and possibly maximum

texts:
Given an array A, we should partition A into two subarrays whose sums are equal, and that maximizes this sum.  We are free to omit items from the subarrays.

For example, [7,2,5,7,12] can be divided as the following:

[5,2][7] = 7
[5,7][12] = 12
[7,7][2,12] = 14

We need the final answer as 14 because the max possible sum is 14.

I initially tried to generate all possible combinations of from length 1 to N and compare the sums and take intersection between two subsets. But it takes pow(2,N) time.

Is there an efficient algorithm to solve this problem?

Please help how to approach this problem. I have tried state space tree with recursion like in the problem subset_sum. But couldn't solve this. Please help.


texts:
I need to transform 2's complement from binary to decimal
The binary integer is 10001001
This is my thought process. Could someone validate my thought process or correct it, please?
10001001 it is a negative integer as the sign magnitude is 1.
Toggle the bits: 01110110
Add 1: 01110111
Binary to decimal 64 + 32 + 16 + 4 + 2 + 1 = 119
Since the original value vas negative, the final result is -119


texts:
So we have two problems:

Problem A: Given a list of positive integers, decide whether the list contains a subset adding to a given number t.

Problem B: Given a list of integers, decide whether the list contains a subset adding to 0.

I have to prove that A can be reduced to B in polynomial time. And a really simple reduction came into mind. Here goes my proof.

So let L be the list of positive integers from the problem A, I just create L' add -t to the it, and pass L' to B, this is the reduction.

To prove this is a reduction, let's see that, L is a positive instance of A if and only if L' is a positive instance of B. Am I doing it right?

So first:

=>) It's just obvious to prove that, given a list of integers which contains a subset adding up to t, this list, along with -t adds up to 0.

<=) Let S be the subset of L' that adds up to 0. Given that, by construction, all integers in L' are positive but one, which is -t, -t must be in S. If S contains the only negative number -t, and S adds up to 0, S{-t}, adds up to t. Then S{-t} is a subset of S{-t} = L that adds up to t.

Question:

Is my proof correct?
Is there any obvious mistake which makes it invalid?
Are there any minor mistakes which could be fixed to "improve" it?

Extra question:

And also, I would like to ask a more generic question. Consider the problem A, but removing the "positive" part, so L can now contain both positive and negative numbers on it. I know A' (the new A) is still reductible to B, because they both belong to the NP-complete problem class. So my other question is:

How can I reduce A' to B?


texts: How can I minimize floating point error when multiplying normal distribution PDFs?

texts:
If you multiply two normal distribution PDFs with means $\mu_1$ and $\mu_2$ and variances $v_1$ and $v_2$, then according to this page, the new mean is

$$\mu = \frac{\mu_1 v_2 + \mu_2 v_1}{v_1 + v_2}$$

and the new variance is

$$v = \frac{v_1 v_2}{v_1 + v_2}.$$

However, if I use those expressions directly to combine several distributions sequentially, the floating point errors quickly pile up. Is there an algorithm for doing this stably?


texts:
Why is the complexity of BFS & DFS frequently written as O(V+E) vs. O(max(V,E)) when the 2 are equivalent?

I feel like the latter conveys more meaning and is more simplified, and we can more easily see that the time grows as a function of the number of vertices OR edges, whichever is greater, whereas the latter reads "the time grows as a function of the number of vertices AND edges"


texts:
I have a matching algorithm that is based on making an comparison score. This score is divided into parts.
Example:

5 - Points for attributes (lets say they have 3 common attributes, would the score be ((3/5)*5) = 3 Points

5 - Points for location

10 - Points for content

Theses points are just something i have set though guessing, and they work well.
But to find what values would be best would i like to implement a kind of AI to test this, i have created 20+ test cases where i know what the correct matching is, so i though that i will be able to train my algorithm to have better values for the different value.
I am no expert in AI, i have only have one course about it, but would a neural network be able to help me here, or should i go with another AI?


texts: How to understand mapping function of kernel?

texts:
For a kernel function, we have two conditions one is that it should be symmetric which is easy to understand intuitively because dot products are symmetric as well and our kernel should also follow this. The other condition is given below
There exists a map $φ:R^d→H$ called kernel feature map into some high dimensional feature space H such that $∀x,x′$ in $R^d:k(x,x′)=\langle φ(x),φ(x′)\rangle $
I understand that this means that there should exist a feature map that will project the data from low dimension to any high dimension D and kernel function will take the dot product in that space.
For example, the Euclidean distance is given as
$d(x,y)=∑_i(x_i−y_i)^2=\langle x,x\rangle+\langle y,y \rangle −2 \langle x,y\rangle $
If I look this in terms of the second condition how do we know that doesn't exist any feature map for euclidean distance? What exactly are we looking in feature maps mathematically?


texts: Can any problem that runs in exponential time on a deterministic RAM be run in polynomial time on a non-deterministic RAM?

texts: If P is a program that can be run in exponential time on a deterministic RAM. Can P always be run in polynomial time on a non-deterministic RAM?


texts: Is #P closed under exponentiation? modulo?

texts:
The complexity class $\newcommand{\sharpp}{\mathsf{\#P}}\sharpp$ is defined as

$\qquad \displaystyle \sharpp = \{f \mid \exists \text{ polynomial-time NTM } M\ \forall x.\, f(x) = \#\operatorname{accept}_{M}(x)\}$.

It is known that $\sharpp$ is closed under addition, multiplication and binomial coefficient. I was wondering if it is closed under power. For example, we are given a $\sharpp$ function $f$ and another $\sharpp$ function $g$. Is it true that $f^{g}$ or $g^{f}$ are $\sharpp$ functions as well?

This is edit after the question has been answered.

Is ($f$ modulo $g$) a $\sharpp$ function? How about when we are given a $\newcommand{\FP}{\mathsf{FP}}\FP$ function $h$. Then is ($f$ modulo $h$) a $\sharpp$ function?


texts: Do industrial automation PLCs have their own special purpose firmware or Instruction Set Architecture?

texts: What is the ISA on the top of which the Programmable Logic Controllers run? Do they have one like in our personal computing devices having Intel x86, amd64 or ARM architecture for smartphones?


texts: Find cycles with specific weights in complete graph

texts:
(this is a cross-post from mathoverflow)
Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.
Let's say I then have an input, $c$ of three edges (e.g $c=[4,7,6]$).
Does an algorithm exist that lets me search $G$ for instances of $c$, and returns the identifiers of the matching nodes?
The cycles it returns must be closed loops, such as $[A, D, B, \text{(then back to A)}]$, rather than $[D, A, B, A]$
Here is a poorly-drawn example:
.


texts: Is it possible to choose such a nontrivial set of queries so that the amortized running time for a hash table with a public key and a function like $(a_{N − 1}k^{N − 1} +... + A_{1}k + a_0) (mod \: p)$ for $N = 2$ is $\Omega(\sqrt{n})$, where $n$ is the total number of keys in the table (as a last resort, at least $\Omega(\log n)$)?


texts:
Take a look at this excerpt from the Algorithm Design Manual, 2nd Edition by Skiena.

I have circled the confusing bit. Basically, everything is understandable to me, until that part. How can $Increment([m+1/2])$ be rewritten as $Increment([m])$? Clearly, if m is an integer, then the algorithm will not treat $m+1/2$ as $m$ and return $m+1$. Instead, $Increment$ is going to go into the $else$ clause and return $m+1/2+1$, which is clearly not $m+1$. Am I missing something here?


texts: Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?

texts: Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation always have a time complexity of $O(n^2)$?


texts: Minimize Deterministic Finite Automata with no accepting states

texts:
I have a finite automaton with no final/accepting states, so F is empty.
How do I minimize it?

I got this on a test and I didn't know how to approach the problem because the automaton had no accepting states.
Is a single initial state with all the transitions into itself the correct answer?


texts: two languages reducible to each other can belong to RE and recursive?

texts:
If two languages L1 and L2 both are reducible to each other in polynomial time then which of the following is false?

A  L1 is decidable and L2 is undecidable.

B  L1 is recursive and l2 is RE

C  both

D  none of these

I know  that both need  to belong to NP or NP hard if they are reducible to each other.
simply solving one solves other.

If L1 is recursive then L2 also needs to be recursive. in context of P-NP if L1 is decidable and by doing extra polynomial work i can get Turing machine for L2 as well ans vice versa .
why one is  decidable and other is  semi-decidable a true statement?


texts: What is this type of consistency called in DataRetrieval?

texts:
I am trying to find the name of this feature that is implemented with SQL Databases:

Given a Record $R^1$ in table having two values for two different fields, e.g.
Let value of field 1 $F_1$ be $V_1$, Let value of field 2 $F_2$ be $V_2$
A any query requiring records s.t. $F_1 = V_1$ should contain $R^1$.
Also any query requiring records s.t. $F_2 = V_2$ should also contain $R^1$.

If a database does not have the above property then it definitely considered broken.

My question is what is the name for this kind of consistency?


texts: What are the basics of CS i should know,before I start my journey into machine learning

texts:
I am myself a non-cs graduate and would love to be a machine learning engineer.

I have learned to code and know the basics of Machine learning as well. Now I would like to know what "basics of CS" I should learn to be completely job ready.

I sometimes have difficulties reading CS documentations and don't know how programs and computers work in background, I am also naiver on topics like memory management, operating systems, networking, electronics stuff like microprocessor, compiler design etc. Are these all necessary for my transition to AI? If they are, would you please recommend me a short learning path or books or videos. I hope I wouldn't need to go deep in these areas. Thanks


texts: Why can't popmin in binomial heap just take the main root value?

texts:
Why is there a need to scan each root node of the binomial trees in a binomial heap to find the minimum?

For example, why can't the true root of the binomial heap, the one that leads to the root nodes of the binomial trees, be the minimum? If it is not the minimum, then what value should it be?


texts: $O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $, with restrictions

texts:
Provide an $O(k)$ algorithm to find $k$- magic pairs of positive integers a and b of type signed int where a magic pair is defined as $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $. You can't use the summation formula $\frac{N \cdot (N+1)}{2}$ as it would result in an overflow. Even you can't run sums such as sum1 and sum2, it's still going to overflow.

Example:
(6,8) (35,49) (204,288) are the first three Magic Pairs.
P.C: This was our recent examination question, I am curious to know the algorithm.


texts: Understanding the flaw in a proof attempt of the Communication Complexity of Equality

texts:
I'm new to communication theory and I've been wondering where the following simple argument fails:

Equality Problem
We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob who gets an $n$-bit vector $Y$. We want one of them to output $1$ if and only if for all indices $i:$ $X[i] = Y[i]$.
Suppose that I choose the inputs $X$ and $Y$ uniformly at random from the set $\{0,1\}^n$. Initially, Alice knows nothing about Bob's input $Y$. Consider a protocol $P$ for equality. Alice and Bob run $P$ and assume that $P$ outputs $1$. By the correctness of $P$, Alice knows that for each index $i$, $Y[i] = X[i]$. Thus Alice has learned $|Y|=n$ bits . Doesn't this immediately imply the $\Omega(n)$ lower bound for $P$?

Note: Of course, I know that the above argument must be flawed since we can solve equality with $O(\log n)$ bits when allowing randomization. I'm just trying to understand why my proof attempt is flawed.


texts: Chernoff bounds and Monte Carlo algorithms

texts:
One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to bound the error probability of $A$ using repeated calls to $A$ and majority agreement.

I don't understand how, to be frank. It would be nice if somebody could break it down piece by piece. Moreover, does it matter whether $A$ is a decision algorithm or can return more values? How are Chernoff bounds in general used for Monte Carlo algorithms?


texts: Understanding the coefficient matrix of Hermite Interpolation

texts:
I was not sure whether this is a computer science question or a math question, so I posted it here, hope that it is alright.
I am trying to learn the technique of Hermite interpolation. I do understand that it is a generalization of Newton polynomial interpolation, which also considers derivatives to ensure continuity of the interpolated curve at the provided points.
In the book Computer Animation — Algorithms and Techniques by Rick Parent, there is a definition of Hermite interpolation that looks like this:

Hermite interpolation generates a cubic polynomial from one point to another. In addition to specifying the beginning and ending points $(P_i,P_{i+1})$, the user needs to supply beginning and ending tangent vectors $(P'_i,P'_{i+1})$ as well.

Here, just the first derivatives are considered, and the aim is to find a polynomial of degree 3 by finding appropriate coefficients $a_3,a_2,a_1,a_0$ such that we have $a_3x^3 + a_2x^2 + a_1x + a_0$. These are found by solving a system of linear equations. So far, so good.
Now, in the book, the matrices look like this:

The general matrix form for a curve is $P(u) = U^TMB$. In the case of Hermite interpolation,
$$
U^T = \begin{bmatrix} u^3 & u^2 & u & 1 \end{bmatrix} \\
M = \begin{bmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \\
B = \begin{bmatrix} P_i \\ P_{i+1} \\ P'_i \\ P'_{i+1} \end{bmatrix}
$$

I do not understand the matrix $M$, I do not see where the values are coming from. Are these fixed, or can I somehow compute them?


texts: Algorithm to find smallest number divisible by N with sum of digits as N

texts:
Problem:

  Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$.

For example:

$n = 1$, answer is $1$
$n = 10$, answer is $190$

There is some dynamic programming algorithm, but I can't find it.
It is sequence https://oeis.org/A002998.


texts: Computation time of a Binom matlab (or C) routine

texts:
I am trying to write a Matlab (or C) routine for the exact probability F of observing K or more successes when a success probability P is expected ($\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$).
I am trying to figure out the following:

  I need to know, if it shoud work for large numbers:
  i.e. K=501000, N=10^6, P=0.5
  Is there a way to calculate how long the computation takes?

Maybe it is possible to perform a computer routine that calculates an approximation? Like Poisson Probability


texts: Creating an K-nary tree that is balanced in both width and depth for N nodes. N known a priori

texts:
Given N items you want to put into a tree, think very generally here like a phone tree, and your goal is to keep the tree from getting "too wide" and "too deep". How many children (K) do you put at each node?

I seem to recall hearing of some proof, many years ago, K was best when set to Euler's number. Therefore in real applications if you must choose a single number you pick 3 children and the tree should end up closely balanced between depth and width. In other words, binary trees tend to be too deep, and 5-trees are "too wide".

Some searching of the 'net and reading some tree designs on Wikipedia has not proved fruitful but perhaps I am dreaming up a false memory?


texts: Lower bound of a summation with an exponential

texts:
For the following (related to a binary tree complexity question):

$$f(n) = \sum_{h=0}^{\lg{}n} h2^h$$

Is there any way to express this only in terms of $n$? Or approximate it?

Put in another way, I figure at worst for an upper bound, we could guess at it in the following way:

$f(n) = 0 + (1 \cdot 2) + (2 \cdot 2^2) + (3 \cdot 2^3) + ... + (\lg{}n \cdot 2^{\lg{}n})$

This means since we go from $0$ to $\lg{}n$, and the largest above when reduced is $n\lg{}n$, I could write $\mathcal{O}(n\lg^2{}n)$.

Supposedly $f(n)$ reduces to $\Theta(n\lg{}n)$ or better (by better I mean closer to $\Theta(1)$) and I'm struggling to show that... and I don't know if it's possible even. I can't prove it though so I can't claim it's not, reducing the summation if possible would hopefully lead to a quick answer.


texts: What does "effective enumeration" in Turing machines mean?

texts:
what is meant by EFFECTIVE ENUMERATION i have comes across this word when I was reading about enumerators for Turing machines is it same as LEXICOGRAPHIC ORDER?
so effective enumeration is possible for recursive sets but no recursively enumerable sets?
i came across this in this question of a competitive exam

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as ω1,ω2,ω3,….
 Define another language L2 over Σ∪{#}

{wi#wj ∣ wi,wj∈L1, i < j}.

Here # is a new symbol.

Consider the following assertions.

S1:L1 is recursive implies L2 is recursive

S2:L2 is recursive implies L1 is recursive

which of the following is true ?


texts: Are all finite strings over some infinite alphabet countable?

texts: Over some infinite alphabet $\Sigma$, can we state that the set of all possible finite strings is countable?


texts: Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

texts:
I am working on proving the time complexity for the following problem, but believe I am stuck:

$$T(n) = 2T(n/3 + 1) + n$$

I have checked out this link here on time complexity on cs.stackexchange

However, I still cannot seem to find the answer. Using this proof from a Dartmouth course:

$a = 2, b = 3, c = 1$

In this case, I know logb a is .63, which is less than 1, so the complexity is $Θ(n)$. However, I don't know how to prove that.

I am trying to practice with the methods that I "know" - Master Theorem, Substitution, Iteration, or a Recursion Tree. And using one of those 4 methods, I can't find a way to prove the complexity is $Θ(n)$, even though I know that's the answer.

Would anyone be able to assist?


texts:
I am trying to solve the exercise 3.3 in Approximation Algorithms by Vazirani, pg 34. It states

  3.3 Give an approximation factor preserving reduction from the set cover
  problem to the following problem, thereby showing that it is unlikely to have a better approximation guarantee than $O(\log{n})$.

  Problem 3.14 (Directed Steiner tree) $G = (V,E)$ is a directed graph
  with nonnegative edge costs. The vertex set $V$ is partitioned into two sets, required and Steiner. One of the required vertices, $r$, is special. The problem is to find a minimum cost tree in $G$ rooted into $r$ that contains all the required vertices and any subset of the Steiner vertices.

My (related) questions

How do we define a tree in a directed graph? I searched on the Internet and found that a tree is defined for only undirected tree, in particular on Wikipedia.
What does it mean "rooted into $r$"? Does it mean out-degree of $r$ is zero?


texts: Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

texts:
Given a sorted array $A[1,\ldots,n]$ and element $x$ that located at
  position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity.

Any ideas how to solve this?


texts:
An almost complete graph of n vertices is obtained from the removal of two edges of the complete graph
of n vertices. For which values of n are there almost complete graphs that admit Eulerian paths?
I'm having difficulty with this issue that I saw on an internet site, please help me.


texts: Are all proof techniques which only look at black box behaviour of a TM relativizing?

texts:
I am currently working on a seminar on $\mathbf{P \stackrel{?}{=} NP}$ and one of the points I want to adress is the Relativization barrier.

However, it is hard to find a concrete definition of a "relativizing" proof. The best defintion I have found is as follows:
"A relativizing proof is any proof that is insensitive to the presence of oracles". So any proof technique that cannot tell if a TM used an oracle is relativizing.

Now my question is: Does this imply that all relativizing proofs only look at the black box behaviour of TMs? Moreover, are all proofs which only look at the black box behaviour of TMs also relativizing? Or are there cases where a proof is relativizing but is not looking at the black box behaviour of a TM, or vice-versa?


texts: Finding the two edge-disjoint paths, minimizing the sum of their lengths

texts:
Given an undirected graph and a start and end node, I am trying to find two edge-disjoint paths such that the sum of their lengths is minimized.  In particular, each path must start at the start node, end at the end node, and no edge can be traversed by both nodes.  Is there an efficient algorithm to solve this problem?
I know that if I just need the shortest path, I can use Dijkstra's algorithm, but finding one path with Dijkstra's algorithm and then searching for another is sometimes not optimal at all, since edges in the first path may have blocked a possible and way shorter path.
I have tried implementing the edge_disjoint_path algorithm from the Python networkx package. But I must say that the result is very varying from okay to really bad.  My network is not that big. "Only" 6000 nodes and 7500 edges.


texts: What are the differences between LCF's Theorem and Automath's Prop?

texts:
How are the fundamental approaches to proving theorems by LCF and Automath different? Considering their modern descendants - Isabelle for LCF and Coq for Automath, both rely on type checking to do proof checking.
Theorems in Isabelle have a theorem type and the only functions that can create instances of this theorem type are inference rules of the logic.
Theorems in Coq have a Prop type and the only way to create Props is by creating proof terms that have the proposition as their types.
If I'm not wrong, LCF and Automath were developed independently around the same time so there wasn't an influence from one to the other, but perhaps by coincidence, is LCF's (Isabelle's) Theorem just a more generic version of Automath's (Coq's) Prop?
I would appreciate it if you could also point out any other fundamental differences between LCF and Automath that have manifested into their modern successors.


texts: Finding an exactly weighted st-path in a digraph

texts:
I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic.

The question is: given 2 nodes $v_1$ and $v_2$, is there a path from $v_1$ to $v_2$ with a weight $w$.

I would like to know if there are any known complexity results for this problem, or even anything related to this but with a specific weight, and not just shortest path, longest path etc.


texts: The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages

texts:
Can the following two statistics be bounded:

the proportion of halting programs vs non-halting programs
the proportion of decidable vs undecidable languages

For example, can we say that one class is much larger than the other, almost all problems are such and such, or both are similar in size?

By Chaitin's argument on the Omega number, we know that the halting probability is undecidable, so it is difficult to obtain an exact statistic on the number (if not impossible). However, Omega numbers have been computed for specific universal machines for prefix-free programs using probability measures decreasing in length (cf. Calude et al.).

So are there known valid statements about these proportions? My intuition (following the argument of the scarcity of life in the universe) would lead me to believe that there are much more undecidable languages than decidable ones. But it is only an intuition that is not backed.


texts:
Connect 4 is a classical game in computer science. Recently I found a web game where one could play the game on a 3d board. One version can be found here

https://www.mathsisfun.com/games/connect3d.html

I know Connect 4 has been completed, and developed algorothms for solving it. Like the minmax strategy.

Algorithms for Connect 4?

My question is: Is there written any articles / done research on connect 4 in 3D before? Has there been developed any algorithms etc?


texts: Is it possible to make a grammar LL($1$) which recognizes palindroms?

texts: Is it possible to make an algebraic grammar LL($1$) which recognizes palindroms for an alphabet $\{a,b\}$?


texts:
I am not a formally trained guy on Complexity theory, but due to interest I am learning it. Based on different feedbacks, I have started my journey with Micheal Sipser's "Theory of Computation" (2013 edition). My question is based upon some statements from the book. My sincere apologies if the question is meaningless.

Here it goes:

On page 298, it is written as "We are unable to prove the existence of a single language in NP that is not in P". That implies all the NP languages are also in P.
Theorem 7.27 says $SAT\in P$ iff $P=NP$, and it's an implication in both directions.
From cook's theorem, $SAT$ is NP-complete. Hence, from the NP-complete definition $SAT \in NP$.
Now, from the point 3 and 1, as $SAT \in NP$ it should also be $SAT \in P$, and therefore from point 2 it should be $P=NP$.

I got stuck here, I know there is some flaw in this logical deduction (because it is not that easy to prove), but I am unable to find it. Please help me in understanding this concept, so that I can proceed further. Thanks in advance.


texts: How can i compute tag-index-displacement bits of an address if cache size is not a power of two?

texts:
How can i compute tag-index-displacement bits from an address if cache size is not a power of two?
Intuitively, i would be inclined to think that i can not directly indicate which bits of the address are used to tag, index blocks and displacement. Instead, i think that i should do some conversion such that it appears that the sum of the bits of tag, index and displacement must be greater than the bits of address. This because for the index i need a number i of bits such that i ≥ log_2(number of blocks), for displacement i need a number d of bits such that d ≥ log_2(dimension of each block in bytes) if i suppose a byte addressable cache. Some suggestions?

As suggested by maverick1989, i explicate the data of the part of the exercise that give me trouble. I have a cache direct-mapped of 5256KB with 32B blocks. Assume a 32-bit addressing mode. This mean that i have (5256*1024)/32 = 168192 blocks. Thus, i need log_2(32)=5 bits of displacement to address a single byte in a block and log_2(168192)=17.3597... bits of index to address a block in the cache. Obviously i have to use 18 bits instead of 17.35.... Now i have some trouble to find the value of these 18 bits, given the address. And after that, what about tag bits?


texts: Dynamic Knapsack Problem - Algorithms and References

texts:
I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be misleading). Anyways, my question is this:

We are initially given a list of "items" to be filled in a knapsack of fixed size. Each item has a weight (bounded, integral) and value, and we need to maximize the total value of items in the knapsack. So far, this is identical to the 0/1 Knapsack problem. Now, at each step, we perform one of the following:

Remove the first item in the list (first means encountered earliest)
Add a new item to the list at the end.

To keep the solution space small, we can assume that the maximum size of the list is fixed, so that it will behave like a fixed size buffer overflow - oldest item is removed before new item is added.

Now, the list is smallish, so the initial instance of the knapsack on the original list can be performed to obtain the first solution. Now, after every operation on the list (addition or removal of items), we again want to find out the best way to fill a new (empty) knapsack with the items in the new list. And we want to do it without repeating a full knapsack algorithm on this slightly modified list (since there will be many such operations).

Is there some way the results of the previous state can be utilized to speed up the process? Is there some information from the previous state that can usually speed up the process? Is there any research on this or some related problem?

The pseudo-polynomial time DP algorithm can be adapted for the case where an item is added (since the table depends on the previous items), but I could not figure out how to deal with it in case the first item is removed from the list. Similarly, a branch-and-bound approach seems pointless. Any ideas or references?


texts: Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs?

texts:
I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa".
Is the even possible? As far as I understand NFA is processing a superspositon of all sub-inputs. So then, if given automaton accepts "a" or "b", it would always accept "ab" just like it accepts "b". Is there a way around, am I missing something?

Would it work? After reading n*'a' and then 'b' the automaton leaves accepting state but in the same time it is entering another accepting state.


texts:
I get the proof of going from an enumerator to a Turing Machine (keep running enumerator and see if it matches input) but I don't see how the other way works.

According to my notes and the book (Intro to the Theory of Computation - Sipser), to get Turing enumerator from a Turing machine, we basically write all combinations of the alphabet. You then run the TM on this input, if it accepts print it out, replace with new string repeat ad infinitum.

The problem I am having is surely this requires the language to be decidable. Otherwise it might get stuck on the third word in some infinite loop doomed never to accept or reject and certainly never print out the whole language.

What am I missing?


texts: Proving monad laws for flatMap and unit, given laws for compose and unit

texts:
I'll use scala notation but hopefully things will make sense in general (I'm trying to prove that you can define a monad using either [flatMap (aka bind) and unit] or [compose and unit])

The book Functional Programming in Scala (github at https://github.com/fpinscala/fpinscala) makes the claim that if we have a type constructor M and functions compose and unit

compose(f: A => M[B], g: B => M[C]): A => M[C]
unit(a: A): M[A]

satisfying

compose(compose(f, g), h) == compose(f, compose(g, h))
compose(f, unit) == f
compose(unit, f) == f

then defining a function flatMap

flatMap(x: M[A])(f: A => M[B]) = compose(_: Unit => x, f)(())

will satisfy

flatMap(flatMap(x)(f))(g) == flatMap(x)(a => flatMap(f(a))(g)
flatMap(x)(unit) == x
flatMap(unit(y))(f) == f(y)

I can't prove this. The easiest place to see my confusion is trying to show the last identity. We have

flatMap(unit(y))(f) = compose(_: Unit => unit(y), f)(())

If there was some rule like

compose(_: Unit => unit(y), f)(()) = compose(unit, f)(y)

or more generally

compose(f∘g, h)(a) = compose(f, h)(g(a))

then we could conclude that the identity is true, but as is, I don't see any move I'm allowed to make. Any ideas?

The solutions for this question https://github.com/fpinscala/fpinscala/blob/master/answerkey/monads/10.answer.scala only do the case where compose is defined in terms of flatMap but the questions asks "Prove that these two statements of the identity laws are equivalent" so I think the solutions should include both implications.


texts: Multiplication of two binary numbers in fixed point arithmetic

texts:
So I'm performing some operations with fractional numbers in a 16-bit FIXED-POINT processor.
I have to multiply the numbers $\ x=-6.35$, represented in $\ Q_{11}$, and  $\ y=-0.1$, represented in $\ Q_{14}$.
First I represent the numbers in the respective notation in binary. The MSB is the sign bit.
So $\ x=11001.10100110011$ and $\ y=11.11100110011001$. I know the binary point is just in our mind and the processor treats this numbers as integers.
Ok then we multiply the numbers and get $\ x*y=11001000000100010011111001111011$. We elimnate the repeated sign bit and save the 16 MSB and represent the result in the appropriate format $\ Q_{10}$: $\ x*y=100100.0000100010$. This number corresponds to $\ - 27.966796875$. But this doesn't make any sense, the result should be $\ 0.635$.
What is going on here? Why is the result different? Am I missing something?


texts: Find a maximum sum in matrix, subject to special constraint

texts:
I have a matrix of size $N \cdot M$ filled with integer values $A[i][j]$. I want to choose some numbers so that their sum is maximal. But there is one very important constraint. If I choose numbers in the $i$-th row from interval $[a, b]$, then I have to also take the interval $[\max(1, a - 1), \min(b + 1, M)]$ in the $i + 1$-th row.  In other words, if I use all of $A[i][a], \dots, A[i][b]$, then I also have to use the elements $A[i+1][\max (1, a-1)],\dots ,A[i+1][\min (b+1, M)]$.

I can't think of any algorithm for this.  I don't even have any idea how to brute-force it. Could someone please help me solve that? I think the optimal solution should have $O(N \cdot M)$ complexity or something like that.

Example input: $N=4$, $M=7$, and
$$A =
\left(\begin{matrix}
&-1 &4 &-6 &-1 &-2 &-5 &10 \\
&5 &-7 &2 &1 &-9 &-13 &2 \\
&2 &4 &-10 &3 &1 &2 &6 \\
&3 &2 &7 &1 &-7 &4 &5
\end{matrix}\right).
$$

For this problem instance, the maximal sum is $40$. This can be achieved by taking the 5 in the first column, the 3 in the fourth column, the 1 in the fifth column and the 2 in the last column as the summits of the triangles.


texts: Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?

texts:
I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem.

  Halting function: The Halt function takes an input a pair $<\alpha, x>$ and outputs 1 if and only if the TM $M_{\alpha}$ represented by $\alpha$ halts on input $x$ within a finite number of steps.

The undecidability of Halting function is proved by reduction from another undecidable function $UC$, which is defined as follows Book by Arora and Barak.

  $UC$: For every $\alpha \in \lbrace 0,1 \rbrace^{\ast}$, if $M_{\alpha}(\alpha) = 1$, then $UC(\alpha) = 0$; otherwise (if $M_{\alpha}(\alpha)$ outputs a different value or enters an infinite loop), $UC(\alpha) = 1$.

The undecidability of $UC$ is proved by the also well-known "diagonalization" technique. I can understand the technique. However, I am puzzling over a more basic problem involving the definition of $UC$.

  My Problem: The definition of $UC$ is based on the value of $M_{\alpha}(\alpha)$. Especially, it seem to be based on whether a Turing Machine halts on an input. However, the latter is undecidable (Worse still, it is undecidable due to the undecidability of $UC$!). In this sense, is the $UC$ function well-defined?

What is wrong with my opinion? How should I understand the definition of $UC$ and the relation between $UC$ and Halting Problem?

Thank for your help.


texts:
I came across a bridge crossing problem. It got me wondering: Can it be reduced to some sort of scheduling problem. If not, is there any other general problem it can be reduced to?

Here is the problem:

  John, Paul, George and Ringo are standing at one end of a bridge crossing. All four must get to the other side. Each can cross in 1, 2, 5 and 10 minutes respectively. There are the following constraints:

  The bridge is rickety and can hold a maximum of two people at once.
  There is exactly one torch.
  It is dark and too dangerous to cross without a torch.
  The crossing is too long for the torch to be thrown across.
  When two cross, they go at the speed of the slowest.

  Task: Minimise the length of time spent for all four to cross.


texts: What happens when the words transfered on the bus are smaller than its width?

texts: So what happens if we're transfering  lots of 8 bit words in a 32 bit bus? Does each bus cycle only transfers 8 bit at the time, wasting the other 24 lines of the bus? Or does it transfer 4 words in each bus cycle?


texts: Finding a string with some specified hamming distances from other strings

texts:
I'm searching the space of length $n$ strings (a-z lowercase), which I suppose we could represent as a large graph of strings and hamming distances between the strings.

I'm given some pairs of strings and distances $v_i, d_i$ . I need to find a string which has distance $d_i$ from each each string $v_i$ .

Does there exist an efficient algorithm for finding this? Perhaps it's possible to triangulate to the right string?


texts: Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

texts:
Let's assume the following definition of a red-black tree:

It is a binary search tree.
Each node is colored either red or black. The root is black.
Two nodes connected by an edge cannot be red at the same time.
Here should be a good definition of a NIL leaf, like on wiki. The NIL leaf is colored black.
A path from the root to any NIL leaf contains the same number of black nodes.

Question

Suppose that you have implemented the insert and delete operations for the red-black tree. Now, if you are given a valid red-black tree, is there always a sequence of insert and delete operations that constructs it?

Motivation

This question is motivated by this question and by the discussion from this question.

Personally, I do believe that if you imagine a valid red-black tree consisting only of black nodes (which implies that you are imagining a perfectly balanced tree), there is a sequence of insert and delete operations that constructs it. However,

I do not know how to accurately prove that
I am also interested in the more general case


texts: Cyclic deterministic finite automata, exponential advantage over DFA

texts:
Let's define Cyclic deterministic finite automata (CDFA) as a DFA that treats its input a bit differently -- namely, CDFA when given input $w$, firstly transforms its input into $w@$, where $@$ is a special character outside the alphabet that acts as a loop, gluing end of $w$ to the beginning of $w$. So, when CDFA reads $@$ and is currently in state $q$, it then reads whole input (i.e. $w@$) again (so CDFA acts as if it was reading infinite word $w@w@w@w@\ldots$), starting this time from the state $q$. CDFA accepts iff during reading symbol $@$ it is in accepting state.

How to show the following:

  For every $n$ natural, there is language $L_n$ and CDFA $C_n$ such that $C_n$ has less than $3n$ states, but every DFA recognizing $L_n$ has at least $2^n$ states.

?

I tried firstly to find some regular language that I know requires approximately $2^n$ states, but the only candidate that springs to my mind is

  $L = \{w \in \{0,1\}^{\star} : \text{n-th symbol counting from the end is 0}\}$

However, I'm not sure whether there exists CDFA having less than $3n$ states. To be honest, I have no idea why it is $3n$ and not other $kn$.


texts: Partitions of a directed graph - common prey and common enemy partitions

texts:
Let $D=(V,E)$ be a finite directed graph with no isolated nodes(from every node there is at least one edge entering and one exiting). For $v \in V$ define the following sets: $$v^+= \left\{w \in V|(v,w)\in E \right\}, v^-= \left\{w \in V|(w,v)\in E \right\}$$

For some $S \subseteq V$ we have, $S^+= \bigcup_{v \in S} v^+, S^-= \bigcup_{v \in S} v^-$.

Now define two related graphs, $G_{cp}=(V,E_{cp}),G_{ce}=(V,E_{ce})$ such that for two distinct nodes $v,w \in V$ we have $vw \in E_{cp}$ iff $v^+ \cap w^+ \neq \emptyset$ (we identify this by condition $C(p)$,  and $vw \in E_{ce}$ iff  $v^- \cap w^- \neq \emptyset$ (condition $C'(p)$ (The notations cp and ce come from "common prey" and "common enemy" )

Let $B_1,B_2,...,B_p$ be the sets of nodes of the connected components of $G_{cp}$ and $A_1,A_2,...,A_k$ be the set of connected components of $G_{ce}$. Obviously those sets are two partitions of $V$

Prove that $(B^+_1,B^+_2,...,B^+_p)$ and $(A^-_1,A^-_2,...,A^-_k)$ represent partitions of $V$. Also prove that $p=k$ (that is both graphs have the same number of connected components).

To prove the first part I thought about taking some arbitrary $v \in V$ and than proving that $v$ is in $(B^+_1,B^+_2,...,B^+_p)$. Then a proof by contradiction may be required to complete the first part, but I can't quite seem to make the connection. I don't even know how to start proving $p=k$. Could you help, give me some hints that I miss or something?

UPDATE

So, after some research, it seems that $G_{cp}$ is a competition graph.


texts:
Using this grammar, over the alphabet $\Sigma=\{a\}$
$$
S \rightarrow a \\
S\rightarrow CD \\
C\rightarrow ACB \\
C\rightarrow AB \\
AB\rightarrow aBA \\
Aa\rightarrow aA \\
Ba\rightarrow aB \\
AD\rightarrow Da \\
BD\rightarrow Ea \\
BE\rightarrow Ea \\
E\rightarrow a \\
$$
Im trying to show that the working string $aaaaaaaaaBBBAAAD$ or $a^{n^2} B^nA^nD$ generates the word $a^{(n+1)^2}$


texts: Given $T(n) = \sum_{i = 0}^{\log n} i 2^i$, what is $O(T(n))$?

texts:
I'm trying to perform an asymptotic analysis on a function:

$T(n) = \sum_{i = 0}^{\log n} i 2^i$

The above expression came about when I began with:

$T(n) = \sum_{i = 0}^{\log n} 2^i \log (2^i)$

Is there a tight, closed-form expression for $O(T(n))$?


texts: Two's complement max with a different base

texts:
Working with fixed size integer representations,
use a number system with b-complement notation, base b = 9 and
n = 4 digits.
 What is the smallest number that can be represented in this number system?
State the number in decimal, and also express it in this number
system.
I assume that it will be 0888 for max, and 8000 for min. If I am right, then what is the max number of integers that I can represent using this notation.


texts: Examples of simple/common problems with quadratic running time

texts:
Are there some examples of simple or common problems which have (in a practical sense) quadratic complexity? I would have thought there were a lot of them, but upon further investigation, I can't seem to find any. (see https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations)

Bubble sort / insertion sort are $O(n^2)$ worst-case, but there are tons of simple $O(n \log n)$ sort algorithms
Multiplication of $n$-bit numbers is $O(n^2)$ for the conventional method, but then you have Karatsuba multiplication which is $O(n^{log_2 3} \approx n^{1.58})$
Matrix multiplication is $O(n^3)$ for conventional implementation but in the $O(n^{2.376})$ to $O(n^{2.807})$ range for more clever implementations
Fast Fourier Transform is $O(n \log n)$ instead of the simple $O(n^2)$ DFT
Dijkstra's algorithm was $O(|V|^2)$ but someone thought of a $O(|E|+|V| \log |V|)$ implementation


texts:
Source alphabet: $\{a, b, c, d, e, f\}$

Code alphabet: $\{0, 1\}$

$a\colon 0101$
$b\colon 1001$
$c\colon 10$
$d\colon 000$
$e\colon 11$
$f\colon 100$

I thought that for a code to be uniquely decodable, it had to be prefix-free.
But in this code, the codeword $c$ is the prefix of codeword $f$ for example, so it is not prefix-free. However my textbook tells me that its reverse is prefix free (I don't understand this), and therefore it is uniquely decodable. Can someone explain what this means, or why it is uniquely decodable? I know it satisfies Kraft's inequality, but that is only a necessary condition, not a sufficient condition.


texts: How to solve this summation of ceiling function in BUILD-MAX-HEAP algorithm

texts:
I am stuck on solving this problem and cannot understand how is the ceiling function omitted or solved.
Please help.

The equation:

$\sum_{h=0}^{\lfloor\lg n\rfloor} \lceil\frac{n}{2^{h+1}}\rceil O(h) $.

But this transformed to:

$O\left(n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{h}{2^h}\right)$

My question concerns on omitting the ceiling function. I'm not clear on whether it was omitted or solved.

This has been taken from CLRS Section $6.3$ Building a Heap.

Please help me out.
Thank you.


texts: How to find a good saw function for PRNG?

texts:
As part of an assignment I have to write a PRNG using a sin (or any other trigonometric function) and a saw function which I'm struggling a bit with. So how would you find a good saw function with about equal distribution?

This is what it is supposed to look like:

There are two functions I've got now,

y=(seed/1000*state*49) mod 101 and

z=(y-1 % 10) / 10)

and distribution looks like this (I'm not fine with that 1 and 0 distribution):


texts: Any way to optimize this with subset caching?

texts:
I have some algorithm and I wonder whether there is a way to optimize it beyond the naive approach.

Basically I have time steps and the current time is $t_c$. At any given time step, a couple of "ranges" are active from now up to some given time $t_i$ (i.e. $\forall t\leq t_i: r_i\in R(t)$).

   now       -time->
   v
r1 ****
r2 ***************
r3 *******
r4 *****************************
r5 ************

At each time $t$ I have to calculate some expensive function of all currently active ranges $f(\{r|r\in R(t)\})$ (in the diagram I'd have to calculated $f(r_1, r_2, r_3, r_4, r_5)$ now and given nothing changes I need $f(r_2, r_4, r_5)$ 9 steps later). Afterwards new ranges are generated and the time moves one step further. Therefore the existing ranges slowly change. Of course, past ranges are irrelevant. That's it.

    now      -time->
    v
r1 ****
r2 ***************
r3 *******
r4 *****************************
r5 ************
r6 **********

My function is associative and cumutative, which means I could make use of any cached function results on subsets of the currently active set. It also time-scales with the number of arguments. Therefore given $f(a,b,c)$ I can calculate $f(d,a,b,c,e)$ in only two calculations rather than five.

Can you see any way to optimize this which is faster than calculating the function at each time for each active range?


texts: Showing the the language represented by a set is regular

texts:
Is the language $L = \{ w \mid w $ is $ 3^n - 1 $ in some given representation $, n > 0 \}$ regular? I know that it is regular. If each element in $L$ is represented as decimal numbers, $L = \{ 2, 8, 26, 80, 242, \ldots \}$. If in binary, $L = \{ 10, 1000, 11010, 1010000, 11110010, \ldots \}$. However, if in ternary, $L = \{ 2, 22, 222, 2222, 22222, \ldots \}$. From there, it is clear that a DFA can be designed to show that $L$ is regular. But what if it wasn't ternary that it became clear, but instead base 59 or base 1009?

My question is that for other sets, does there exist a clear method to determine if the language based on that set is regular or not? Or does it just depend on the cleverness of the solver?


texts:
I have a discrete distribution of reference. For the example let's say:

P(X=1)=0.2
P(X=2)=0.7
P(X=3)=0.1

Now I am given n numbers, and I want to group (sum) those numbers into 3 bins and approximate as close as possible the above distribution in the sense of minimizing the sum of squared error. So let's say I have those numbers: 10, 25, 25 50 (total sum =100). So I want to group them into 3 bins, and ideally the sum of each bin would be 20, 70, 10 and that would perfectly match the distribution. Unfortunately that's not possible and the best here would be 25, 75 (50+25), 10. The error here is (25-20)²+(75-70)²+(10-10)²=50

What is the algorithm solving the general problem?


texts: Describe in words how a NTM can simulate a DTM

texts:
I have this assignment

Describe in words how a DTM can simulate a NTM
Describe in wordshow a NTM can simulate a DTM

I'm working on this request and I'm crushing with the comparison.

1-I understand that every NTM can be represented by a DTM with a tree structure, that represents every step of the different possibilities of a NTM. Every step should simulate with n tapes the configuration states of the NTM with the DTM etc.

2-For this I'm a little lost, I think you can't have a DTM simulated by an NTM, the multiplicity of states allowed in NTM with guesses makes difficult to create a deterministic process o linear, ¿I'm going in the right path?.


texts: A question on decidable formal languages and turing machines

texts:
Let $L' \subseteq L \subseteq \Sigma^*$ be decidable languages with deterministic Turing machines $M'$ and $M$ which decide the languages. Typically we have $t_M(w) \le t_{M'}(w)$ for all $w \in \Sigma^*$, where $t_M(w)$ is the time of $M$ on input $w$.

Suppose furthermore that $M$ and $M'$ have minimum length when interpreted on some chosen universal Turing machine $U$.
So if $M''$ decides $L'$ then $l(M'')\ge l(M')$ where $l(M)$ is the length of $M$ when interpreted on $U$.

Is this just a coincidence of the chosen Turing machines, or does this property hold for all deciders of $L$ and $L'$ with minimum length?

"Typically" here means the following situation:

For instance if $L'$ is a decision problem on graphs and $L$ is the language of graphs (meaning that words correspond to adjacency matrix of a directed graph), then first for a word $w\in \Sigma^*$ one must decide if this word corresponds to an adjacency matrix of a graph, then decide if that graph has the property one is looking for. If you know a counterexample to that, that would also answer the question.


texts: Can a regular expression be any string from the language described by it?

texts: Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?


texts: Dynamic Programming formulation for hotel problem

texts:
There are n hotels given at a0, a1, ..., an such that 0 < a0 < a1 < ... < an. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. Moreover, you are required to complete your journey in exactly d days (i.e have to make d-1 stops in between). If you travel x miles during a day, the cost for that day is x^2. You want to plan your trip so as to minimize the total cost - that is, the sum, over all travel days, of the daily cost. Find the optimal sequence of hotels at which to stop.

I came up with this dp solution:

Let dp(i) be the minimum cost such that the last stop is hotel i.
Base case: dp(0)=0.

To compute dp(i), I consider all possible places 0<=k<i, that we might have stopped before. Thus, the recurrence relation becomes:

for i=1;i<=n;i++
  dp(i)=inf
  prev(i)=undefined
  for k=0;k<i;k++
    if (dp(i)>dp(k)+(ai-ak)^2)
      dp(i) = dp(k)+(ai-ak)^2)
      prev(i) = k

How do we make sure that this algorithm takes exactly d stops?


texts: Decidable language: set of context-free langauges containing 1 string

texts:
ONE = {(G) : G is a CFG such that L(G) contains exactly one string} .

I know to prove this is decidable I need to create a DTM that would recognize it and HALT on all input.
I am struggling at coming up with a high level definition.

My Possible Solution:

On input G, where G is a Context-free grammar,
If non-terminal has more then one option that it can lead to, reject.
Else accept.


texts: Minimum length of string using chars appearing in a given string but not a substring of that string

texts:
Suppose we're given a string like "aabaccbbca", and want to find a short string that's not a substring of this string. However, we're limited to using the characters that appear in the string: in this case we can use 'a's, 'b's, and 'c's, but nothing else.

In that example case, there's no length-0, length-1, or length-2 solutions. There's lots of length-3 solutions. Actually, finding the minimum length is a lot more interesting than finding a specific solution.

So my question is: how can we efficiently compute the minimum length for which solutions exist to this 'find string with same alphabet that doesn't appear as a substring' problem?

Examples:

 minLengthMissingSubstring("") == 1
 minLengthMissingSubstring("a") == 2
 minLengthMissingSubstring("abc") == 2
 minLengthMissingSubstring("aabaccbbca") == 3
 minLengthMissingSubstring("abbaccbbca") == 2
 minLengthMissingSubstring(
    "0001002003004011012013014021022" +
    "0230240310320330340410420430441" +
    "1121131141221231241321331341421" +
    "22423323424324433343444431442223") == 4


texts:
I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form

$$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$

but I don't know the values of $i_1,\dots,i_k$.  I am given many pairs $(x,f(x))$ for random values of $x$ (chosen uniformly and independently at random).

I'm looking for an efficient algorithm to recover $i_1,\dots,i_k$, given this information.  How efficiently can this be done?  How many pairs are needed?  Randomized algorithms are OK.  I'm particularly interested in the regime where $k \ll n$.

This is similar to the learning juntas problem, but it might be much easier.  With the learning juntas problem, we know that $f(x_1,\dots,x_n) = g(x_{i_1},\dots,x_{i_k})$ but neither $i_1,\dots,i_k$ nor $g$ are known.  Here, we know $g$ and know that it is a disjunction, so it seems like the problem might be much easier.

I can see an information-theoretic lower bound: $\Omega(k \lg n)$ pairs are needed.  There are ${n \choose k}$ possible candidates for $f$, and each pair gives us only one bit of information about $f$, so we need at least $\lg {n \choose k}$ pairs; for small $k$, ${n \choose k} = \Theta(k \lg n)$.  How close to this can one get?

This is motivated by an application in inferring input-output relationships in programs (black-box taint analysis).


texts: how does the shap algorithm work in polynomial time?

texts:
I'm trying to understand how the shap algorithm calculates in polynomial time an estimation to the feature attribution function that satisfies the shapely value attributes (specifically for tree based models!).
A simplified version of the feature attribution function for the feature $i$ of the model $f$  prediction for the input instance $x$ is: $\phi_i(f, x)=\sum_{S \in N /\{i\}}[f_x(S\bigcup{i})-f_x(S)]$ - i.e. sum the change in the model prediction for every set of features $S$ that does not include the feature $i$ from the same set when $i$ is introduced.
The naive exponential estimation for a tree based model (Algorithm 1 in the paper), estimates $f_x(S)$ by recursively following the decision path for $x$ if the split feature is in $S$, and taking the weighted average of both branches if the split feature is not in $S$ (weights are the coverage of train samples in that branch). We do that for every set $S$ in the powerset of features.
So far so good. But now the paper describes Algorithm 2 - a polynomial method for computing the same values, basically by "running simultaneously for all $2^N$ subsets"! I can't understand that, no matter how much I try (see my notebook).
Can someone enlighten me and explain how is that working? how are we tracking the number of sets and the coverage in every path?
Note that the real algorithm is much more complex than what I'm presenting here, as the real feature attribution function weights each set $S$ proportionally to the number of features in it $|S|$ - but I'm not interested in that complexity, only in the basic simplified setup I've presented here.
Thanks for your efforts, this is something that's eluding me for years


texts: Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

texts:
My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof.

I've tried to prove it myself but I got stuck at the Inductive Step.

Let $G=(V,T,P,S)$ be a context free grammar.

Prove by induction on $n$ where $n\geq 1$ that:

For every $w\in T^*$ and for every $\alpha\in (V\cup T)^+$ , if $\alpha \Rightarrow^n w$ then $\alpha \overset{_{lm}}{\Rightarrow}^n w$

I.e

$\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^n w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^n w$

(The leftmost derivation relation is denoted as $\overset{_{lm}}{\Rightarrow}$)

(From a high level point of view the claim says that if some terminal word $w$ can be derived form $\alpha\in (V\cup T)^+$ then there exist a leftmost derivation to derive $w$ from $\alpha$)

My try:

Basis

If $n=1$ then we must show that $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^1 w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^1 w$:

Let $w\in T^*$ and let $\alpha\in (V\cup T)^+$ such that $\alpha \Rightarrow^1 w$.

by definition of the $\Rightarrow$ relation we get that:

$\exists \psi,\chi,\gamma\in(V\cup T)^*, \exists A\in V, \alpha = \psi A \chi \land w=\psi \gamma \chi \land (A\rightarrow \gamma)\in P$

Now since $w\in T^*$ and since $w=\psi\gamma\chi$ we get that $\psi \in T^*$ and so:

$\exists \psi\in T^*,\exists \chi,\gamma\in(V\cup T)^*, \exists A\in V, \alpha = \psi A \chi \land w=\psi \gamma \chi \land (A\rightarrow \gamma)\in P$

And we get by definition of $\overset{_{lm}}{\Rightarrow}$ relation that $\alpha \overset{_{lm}}{\Rightarrow} w$ as was to be shown.

Induction hypothesis

Suppose that for some $n=k\geq 1$ we get: $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^k w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^k w$

Induction step

Now we'll prove that: $\forall w\in T^*, \forall \alpha\in (V\cup T)^+, \alpha \Rightarrow^{k+1} w \rightarrow \alpha \overset{_{lm}}{\Rightarrow}^{k+1} w$

Let $w\in T^*$ and let $\alpha \in (V\cup T)^+$ such that $\alpha \Rightarrow^{k+1} w$,
And so we get that $\exists \beta \in (V\cup T)^*$ such that $\alpha\Rightarrow\beta\Rightarrow^k w$. Since $k\geq 1$ we get that $\beta \in (V\cup T)^*V(V\cup T)^*$ and so $\beta\in(V\cup T)^+$.
Now since $w\in T^*$ and since $\beta \Rightarrow^k w$ we get by the induction hypothesis that $\beta \overset{_{lm}}{\Rightarrow}^k w$

Now I do not know how to proceed.

I got that $\alpha \Rightarrow^1 \beta$ but how can I show that $\alpha \overset{_{lm}}{\Rightarrow}^1 \beta$ and from there conclude that $\alpha \overset{_{lm}}{\Rightarrow}^{k+1} w$ using the facts I've shown above?

thanks for any help.


texts: What's the connection between the two "Fast Walsh Transform"?

texts:
First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$ in $O(n \log n)$ time, using an algorithm called Fast Walsh Transform, where $n$ represents the length of the binary digits.

However, when looking at wikipedia page, it says that the Walsh Transform is to accelerate the evaluation of an $n \times n$ Matrix called Walsh Matrix. I also found it reasonable.

My question is, what's the connection between the two evaluations? I know that a convolution is a linear transformation and can be represented as a vector multiplied by a matrix. But where's the matrix in the First convolution? I am so confused, and does it represent that some multiplications with specified matrixed could be accelerated to $O(n \log n)$? (Thus the matrix is $n \times n$)


texts: Multitape Turing machines against single tape Turing machines

texts:
Introduction: I recently learned that a multi-tape Turing Machine $\text{TM}_k$  is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that  $\text{TM}_k \equiv \text{TM}$ is based on the idea that a $\text{TM}$ can simulate a $\text{TM}_k$ by using a unique character to separate the respective areas of each of the $k$ tapes.

Given this idea, how would we prove that a process taking $t(n)$ time on a $\text{TM}_k$ can be simulated by a 2-tape Turing machine $\text{TM}_2$ with $ O(t(n))\log(t(n))$ time?


texts: Difference between computation in proposition proof and definitional computation?

texts:
As stated in equality at nLab, "computational equality" is about computational steps which take for example, $s(s(0))+ s(0)$ to $s(s(s(0)))$ and it acts exactly and can be considered same as definitional equality (at least in type theory).

But then if we consider $p$ in $p:Id_\mathbb{N}(a+b, b+a)$ as computation steps taking $a+b$ to $b+a$ then what is the difference between computation steps in $p$ and computation steps in above mentioned computational equality which prevents $p$ to be considered sort of a definitional equality? Are they of different computation level/form?
Or in other words, if I have got it correctly, what is the difference between $p$ in $p:Id_\mathbb{N}(a+b, b+a)$ and $p'$ in $p':Id_\mathbb{N}(s(s(0))+s(0), s(s(s(0)))) $ so that one can be considered almost the same thing as definitional equality but not the other one?
As an example following are the Agda codes in proving above mentioned reactions from Programming language foundations in Agda: Natural Numbers and [Programming language foundations in Agda: Proof by induction][3]correspondingly:

_ : 2 + 3 ≡ 5
  =
-
  begin
    2+3
  ≡⟨⟩    -- is shorthand for
    (suc (suc zero)) + (suc (suc (suc zero)))
  ≡⟨⟩    -- inductive case
    suc ((suc zero) + (suc (suc (suc zero))))
  ≡⟨⟩    -- inductive case
    suc (suc (zero + (suc (suc (suc zero)))))
  ≡⟨⟩    -- base case
    suc (suc (suc (suc (suc zero))))
  ≡⟨⟩    -- is longhand for
    5
  ∎

+-comm : ∀ (m n : ℕ) → m + n ≡ n + m
+-comm m zero =
  begin
    m + zero
  ≡⟨ +-identityʳ m ⟩
    m
  ≡⟨⟩
    zero + m
  ∎
+-comm m (suc n) =
  begin
    m + suc n
  ≡⟨ +-suc m n ⟩
    suc (m + n)
  ≡⟨ cong suc (+-comm m n) ⟩
    suc (n + m)
  ≡⟨⟩
    suc n + m
  ∎

In my understanding both thing are computational steps that take you from left hand side to the right hand side!
 Would you please answer it both intuitively and technically?

P.S. I found the following piece in Homotopy Type Theory(§1.1 p.22) which I thought might be the answer to part of my own question:

  Whether or not two expressions are equal by definition is just a matter of expanding out the definitions; in particular, it is algorithmically decidable (though the algorithm is necessarily meta-theoretic, not internal to the theory).

I guess the above paragraph is talking about $\alpha$ and $\beta$ expansions. But if that is true then it raises the question that: What does a proof of a proposition has in addition to function application that makes it a different equality? Is it that beside application we do have function definitions as well in a proof definition?!


texts:
Say we have two (NP-)optimization problems $A$, resp. $B$, such that it is NP-hard to approximate within a factor $\alpha$ resp. $\beta$.

Now define problem $C$ whose input consists of pair inputs from $A$ and $B$, and a solution as pair of solutions of $A$ and $B$, but the objective function as the product of objective functions of $A$ and $B$.

Can we conclude that $C$ is NP-hard to approximate within a factor $\alpha\beta$?  If not, can we prove anything stronger than that there is no approximation within $\max\{\alpha, \beta\}$? If yes, does it matter if the hardness depends on, for example, the unique games conjecture?

Intuitively, I would think: unless $P=NP$, for any polytime approximation algorithm for $A$ there is an input such that it gives a solution of cost more than $\alpha OPT$, and likewise for $B$. Any algorithm for $C$ can be used almost directly as an algorithm for either $A$ or $B$, so we can find an input that produces a solution of cost more than $\alpha \beta OPT$ on that algorithm as well. I am not sure if you can reason like this though.