texts: Proving that a (tree) language is not Buchi recognizable

texts:
I'm reviewing some notes about tree automata and I'm trying to conclude a proof that the professor left incomplete. The statement is:

  Let $A = \{a,b\}$ and $T = \{t \in T_A^{\omega} \mid \text{every path in $t$ contains a finite number of $a$}\}$.
  Prove that $T$ isn't Buchi recognizable.

Now we can define the following subsets of trees $t_n \subseteq T$ where $t \in t_n$ has one $a$ at positions: $\epsilon, 1^{m_1}0, 1^{m_1}01^{m_2}0, \ldots, 1^{m_1}01^{m_2}0\ldots1^{m_n}0$ with $m_i > 0$.

Now assume that $\mathcal{A} = (Q, A, \Delta, q_0, F)$ is the Buchi automaton that recognizes $T$ with $|Q| = n+1$ and $q_0$ appears only at the root of its computations. Let $t \in t_n$ and $r$ be a successful run of $\mathcal{A}$ on $t$.

Claim: $\color{red}{\text{There exists $u \leq v < w$ such that $r(u) = r(w) = s \in F$ and $t(v) = a$.}}$

Obviously if we show that the claim is true we can prove the initial statement: take the subtree $t_v$ and obtain a $t' \in t_{n+1}$ by replacing
the subtree $t_w$ with $t_v$. We have that there exist a run $r'$ which is identical to $r$ up to the position for $w$ and will follow the same sequence of states at $w$ as it did at $v$, and hence is accepting. Repeat the process and you obtain a branch with infinite $a$s that is accepted by $\mathcal{A}$. (This is just the rough idea, it requires a bit of formalism, but it's not the point of the question.)

My question is: how do I prove the claim?

I can show that there exist a $t' \in t_{2n}$ with that property (which is actually good enough for the rest of the proof), but not that given a fixed $t_n$ the statement holds for any successful run.

My idea is simply: given that $r$ is accepting there must exist a $s \in F$ repeated infinite times in a path passing through $1^{m_1}01^{m_2}0\ldots1^{m_n}0$. Then take a tree $t'' \in t_{n+1}$ that is
identical to $t_n$ up to the position $x$ where $r(x) = s$ on that path, and add an $a$ below such position. Now this tree is still accepted by the automaton and there exist an accepting run $r'$ identical to $r$ up to the position $x$,
but then $r'$ cannot reuse $s$ for accepting that same path (otherwise we have found the three states of the claim) and so it must use a different state $s'$. Repeat for all final states and you have that $t_{2n}$ must have a run with that property.

Is there any way to apply this kind of reasoning to $t_{n-1}$, $t_{n-2}$ etc to obtain the result for $t_n$? It looks like at most I may be able to prove that there exist a $t'' \in t_n$ with a run with that property, while the claim is stronger. Or am I going in the wrong direction?


texts: are NP Complete languages closed under any regular operations?

texts: I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. Is it also true that NPC languages are not closed under the complement, concatenation, and kleene star operations?


texts: Set of steps that cannot be implemented on a Turing machine

texts: Is there an example of a "set of steps" that we thought was an algorithm, but later was shown not to be an algorithm because it could not be implemented on a Turing machine?


texts:
Construct a push-down automata to recognize the language $ A = \{u\#v \in \{0,1,\#\}^{*} | u = v^{\complement} \} $. Here, $v^{\complement}$ is the bit-complement of v.

I don't see how to perform this with a LIFO stack. I would like some hints (not a solution) if possible.

Thanks,


texts: Can a Turing Machine tell if an input string is a description of itself?

texts:
Can some Turing Machine $M$ with description $\langle M\rangle$, check if an input string $w$ is a description of itself? That is, can $M$ be constructed such that $M$ can tell if $w$ = $\langle M\rangle$?

The closest related problem I could find was: Can I construct a Turing machine that accepts only its own encoding?

But I want to consider the case where $M$ must recognize its own description as an intermediate step, and then accept or reject based on that and some additional criteria. Is this possible?


texts: Why hasn't functional programming researched dynamic trees?

texts:
Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging dictionaries ("A Simple Mergeable Dictionary" by Adam Karczmarz),

By dynamic trees I refer to the definition stated in Sleator & Tarjan's paper "A data structure for dynamic trees" in 1983. Few efforts have been published within the functional programming research area since.

Edward Kmett implemented a version of the ST trees mostly as a translation of the C++ counterpart, see Link-cut trees.
Chris Okasaki wrote a limited implementation of the Splay trees in his renowned book "Purely functional data structures".
Ralf Hinze and Ross Paterson introduced a functional data structure called 2-3 finger trees but with somewhat different aim from that of original definition of dynamic trees.

Implementation (and perhaps performance) of dynamic trees are divided according to three approaches:

Linearization, where ET trees (Euler tour) play a great role. Not found a purely functional study.
Path-decomposition, where ST trees are the flagship, just found the Kmett's version.
Tree contraction, where Top trees, topology trees and RC trees are the players. Not found a purely functional study.

Purely functional analysis and implementation can be found on Splay, AVL, red-black tree, but those are NOT dynamic trees. The former are considered the shadow (also called virtual or auxiliary) data structure of the latter.

So, my question is:

What are the reasons (drawbacks, weaknesses) for the Functional Programming research community not to take part into the dynamic trees data structure?


texts: Fast hashing algorithm for mapping/quantizing a collection of floats onto a small set of sorted floats

texts:
With my application, I have

Collection X: thousands of floating-point numbers with the value range [0, 1], not sorted.
Collection Y: 11 floats ranging from [0, 1], sorted.
The size of X is known. Let it be L.

The goal is to quantize X and map it onto Y, so that we get a hash array of indices of Y for X. Eventually Y will be then quantized onto 10 discrete things pointed to it.
An example to make it a bit clearer,

Y = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
X = [0.678, 0.124, ..., 1.0, ., 0.013, 0.475]

I want the algorithm output to be 0-based indices like these:

H(Y[0]) = H(0.678) = 6
H(Y[1]) = H(0.124) = 1
H(Y[n-2]) = H(0.013) = 0
H(Y[n-1]) = H(0.475) = 4

Attempts
Naively, I've tried linear and binary searching for positioning each element of X in Y so that the element is found between an adjacent pair of elements in Y.
However, the performance is not good enough for my application. This quantization happens in a realtime thread that slow computation is undesirable.
Question
What is the best way of this kind of hashing/quantization? X is not sorted.
Thanks!


texts: What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?

texts:
Let $A$ be an event divided into 4 events $A_i$ with the same probability. Why does the quantity of information of $A_i$ satisfy
$$ I(A_i) = I(A) + \log (4)?$$


texts:
I would like to express $(\sqrt{n})!$ in terms of $Θ()$ notation.

My approach is the following:

$$(\sqrt{n})!=f(n)\Leftrightarrow$$
$$\log(\sqrt{n})!=\log(f(n))$$

Now from Stirling's approximation we get: $$Θ(\sqrt{n}\log(\sqrt{n})=\log(f(n))\Leftrightarrow$$
$$f(n)=Θ(\sqrt{n}^{\sqrt{n}})$$

So, $$(\sqrt{n})!=Θ(\sqrt{n}^{\sqrt{n}})$$

Is this approach correct? I am a bit confused since I used $\log$ equality to prove this and in some cases this doesn't work correctly.

For example, if we get $n!$ and $n^{n}$ we observe that $Θ(\log(n!))=Θ(\log(n^{n})$ .

However we know that $n!=o(n^{n})$ (which means that $n!<n^{n}$ asymptotically)


texts:
Let $G(V, E)$ be a complete undirected graph and $p = v_1, \dots, v_\ell$ a path of unique arbitrary $\ell$ vertices of $V$. Each vertex of $V$ is a point in a two-dimensional discrete space (e.g., $v_i = (x, y)$ with $x, y \in \mathbb{N}$).

Is it possible to find a path $p'$ that contains the same points of $p$ in a different order such that the following properties holds:

every edge does not graphically intersect any other of $p'$;
the starting and the ending point of $p'$ are the same of those of $p$?

I implemented the well-known 2-Opt algorithm but I'm not satisfied with its performance (see, e.g., Englert, Röglin and Vöcking, Worst case and probabilistic analysis of the 2-Opt algorithm, pdf).

Are there any known algorithms faster than the previous one that solve this problem?


texts: Closed-form solution to recurrence equation

texts:
I have a recurrence relation of the form:

$f(0) = f(1) = 1, f(2) = 2$ (initial conditions).

$f(2n) = f(n+1) + f(n) + n$ for $n>1$.

$f(2n+1) = f(n) + f(n-1) + 1$ for $n>1$.

I have been able to simplify this equation a little bit, but I can't seem to find a closed-form solution (and neither can Mathematica with RSolve).

The first few values of $f(n)$ for $n = 0$ to $10$ are:

[1, 1, 2, 3, 7, 4, 13, 6, 15, 11, 22]


texts:
I was asked the below question in a test at school last week and I thought the answer given was incorrect.

You had to give a file format from the options for the below statement:

A file created in software that most users will not have available

You had two options, PDF or DOCX. I answered DOCX but apparently the answer was PDF, what do you think?


texts:
I have the following condition in an LP problem. I have a variable $x_i \in i = 1,2,..7$ and I need to constrain the problem via:
if $x_1$ >5 then $x_2 \leq 30$
I'm stumped on how to formulate that with integer variables.
Thanks


texts:
It is obvious that the representational power of graphs are huge.
Is there a problem that cannot be represented using graph?

I have recently asked this question to my students and no answers came up. I could not answer this either.

For instance:
Problem: Finding the shortest path between two given cities in a country.
Graph type: Directed, weighted.
Vertices: Cities.
Edges: An edge $(i,j)$ indicates there is a way from city $i$ to city $j$ and weight of $(i,j)$ indicates the distance between cities $i$ and $j$.

Problem: Expressing your feelings using crayons.
Graph type: Directed, weighted.
Vertices: Neurons in the brain.
Edges: Values of electronic signals being transmitted among neurons.
Output: Interpretation of the signals by the brain.
(Just kidding)

Edit:
Problem in this post means, a problem that can be solved using computers.


texts: Looking for a set implementation with small memory footprint

texts:
I am looking for implementation of the set data type. That is, we have to

maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with
operations insert(x) (add an element x to $S$) and find(x) (checks whether element x is a member of $S$).

I don't care about other operations. For orientation, in applications I'm working with we have $u \approx 10^{10}$.

I know of implementations that provide both operations in time $O(1)$, so I worry mostly about the size of data structure. I expect billions of entries but want to avoid swapping as much as possible.

I am willing to sacrifice runtime if necessary. Amortised runtime of $O(\log n)$ is what I can admit; expected runtimes or runtimes in $\omega(\log n)$ are not admissable.

One idea I have is that if $S$ can be represented as a union of ranges [xmin, xmax], then we will be able to save on storage size with the price of some performance decrease. Also, some other data patterns are possible, like [0, 2, 4, 6].

Could you please point me to data structures which can do something like that?


texts:
I'm learning about logic circuits and I've come across full adder. In the book they  derived its two carry out expressions -

Cout = x&&y || x&&z || y&&z
and
Cout = x&&y || (x'&&y || x&&y')&&z

I've tried to get the second equation from the first one but couldn't. Any one knows how to do that?


texts: Data structure or algorithm for quickly finding differences between strings

texts:
I have an array of 100,000 strings, all of length $k$.  I want to compare each string to every other string to see if any two strings differ by 1 character.  Right now, as I add each string to the array, I'm checking it against every string already in the array, which has a time complexity of $\frac{n(n-1)}{2}  k$.

Is there a data structure or algorithm that can compare strings to each other faster than what I'm already doing?

Some additional information:

Order matters: abcde and xbcde differ by 1 character, while abcde and edcba differ by 4 characters.
For each pair of strings that differ by one character, I will be removing one of those strings from the array.
Right now, I'm looking for strings that differ by only 1 character, but it would be nice if that 1 character difference could be increased to, say, 2, 3, or 4 characters.  However, in this case, I think efficiency is more important than the ability to increase the character-difference limit.
$k$ is usually in the range of 20-40.


texts: Why don't we use $ as end marker for input in PDA?

texts:
I am reading Theory of Computation by Peter Linz. The transitions for PDA uses $\epsilon$ as end marker for input string. For example if the final state is
 $q_1$ then the transition is written like $\delta(q_0,\epsilon,z)=(q_1,z)$.

Why don't they write the transition as $\delta(q_0,\$,z)=(q_1,z)$.


texts: Proving that no 2-state DFA decides the language A = {x ∈ {0, 1}* | bnum(x) is divisible by 3}

texts:
I am doing a problem where I need to prove that no 2-state DFA decides the language
A = {x ∈ {0, 1}*| bnum(x) is divisible by 3}.

It's seems pretty obvious at first, because aren't there only 4 DFA's with two states that define it? Also, since x is divisible by 3, the DFA would need to have 3 states to define the remainder values.

So I feel like I have a good understanding of the problem, but how do I more formally prove the statement? Any help is appreciated.


texts: Minimization of amount in the change coins problem using the dynamic programing approach

texts:
I'm learning the dynamic programming approach to solve the coins change problem, I don't understand the substitution part

Given: amount=9, coins = [6,5,1],

the instructor simplified it with this function:

minCoins = min {(9-6)+1 , (9-5)+1, (9-1) +1} = min{4, 5, 9} = 4

I don't understand the logic of this min method: why we say that to change amount of 9 coins, we can simply, take the minimum of: 9  - {all coins} +1 ?

here's a Gif that visualizes the instructor's approach: https://i.stack.imgur.com/Zx2cG.gif

(*taken from the Algorithmic Toolbox course/ instructor: Prof. Pavel A. Pevzner)


texts: Given n standard C++ STL maps, can I merge them?

texts:
I was wondering if it is possible to merge standard STL maps in O(log(n)) using DSU trick.

For example, Map a={{1,2},{3,2},{4,3}}, Map b={{2,3},{3,2},{4,1}} and Map c={{2,1},{3,2},{4,4}}

Then the resultant map will be : {{1,2},{2,4},{3,6},{4,8}}

If not achieveable by DSU, is there any other algorithm to achieve this in O(logn) complexity?

Here n is the number of maps and the sum of the sizes of all maps is 10^5.
n can range from 1-10^5.


texts:
In a related post: Algorithm for solving binary quadratic Diophantine equations (BQDE) and its CTC there was a conclusion that with regard to general binary quadratic diophantine equation (with all non-zero coefficients), the solutions (if existent) can be found in exponential time.

However, is this also the case for simple hyperbolic case (i.e. where $A$ and $C$ are zero, leading to form: $Bxy + Dx + Ey + F = 0$)? Alpertron (https://www.alpertron.com.ar/METHODS.HTM) shows a method for such a case which involves finding all integer divisors of $DE-BF$ - a task which can be tricky for large coefficients. For certain, sufficiently large coefficients Alpertron's method would imply that this can be computed in sub-exponential time (using GNFS).

Is there any algorithm to be used for SHCDE which would find the solutions in less than exponential time (unlike standard ones for general BQDE)?


texts:
Let $L_1,L_2$ be any $\Sigma$-Languages, with $l_1\in L_1, l_2\in L_2$

If I have a regular Language $L(l_1(l_2l_1)^*l_2)$ would the word $\omega=l_2$ be recognized? I'm confused because if $\epsilon \in L_1$ then $l_1$could be $\epsilon$, then $L(l_1(l_2l_1)^*l_2)$ would recognize the word with $(l_1 = \epsilon) *((l_2l_1)^0=\epsilon)*l_2 = \omega$

I think this is wrong but I don't know why.


texts: Chernoff-Hoeffding bounds for the number of nonzeros in a submatrix

texts:
Consider a $n \times n$ matrix $A$ with $k$ nonzero entries. Assume every row and every column of $A$ has at most $\sqrt{k}$ nonzeros. Permute uniformly at random the rows and the columns of $A$. Divide $A$ in $k$ submatrices of size $n/\sqrt{k} \times n/\sqrt{k}$ (i.e. $\sqrt{k}$ meta-rows and meta-columns). Enumerate the $k$ nonzeros and define the following indicator random variable:

\begin{equation}
X_{\ell,z} =
\begin{cases}
1 & \text{if the $z$-th nonzero entry is in $A^\ell$} \\
0 & \text{otherwise}
\end{cases}
\end{equation}

The expected number of nonzero entries in a generic submatrix $A^\ell$ is one. Is it possible to prove Chernoff-Hoeffding bounds on the sum $X_\ell = \sum_{z=1}^k X_{\ell,z}$?

My first guess was to prove negative association, following Dubhashi and Panconesi analysis. Unfortunately, $X_{\ell,z}$ and $X_{\ell,z^\prime}$ are not negatively associated (following the book's notation, if $z$ and $z^\prime$ are in the same row/column then $\mathbf{E}[f(X_{\ell,z})g(X_{\ell,z^\prime})] > \mathbf{E}[f(X_{\ell,z})] \mathbf{E}[g(X_{\ell,z^\prime})]$).


texts:
In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\in\{1,\ldots,n\}$ such that, for some assignment, some $k$ clauses $c_{i1},\ldots,c_{ik}$ are true.

In MAX-MIN-SAT, we are given two different formulas and want to find an assignment that maximizes the smaller number of satisfied clauses.
I.e., given two formulas $\phi_a = a_1 \cap \cdots \cap a_n$ and $\phi_b = b_1 \cap \cdots \cap b_n$,  where each $a_i$ and each $b_i$ is a disjunction, we want to find the largest $k\in\{1,\ldots,n\}$ such that, for some assignment, some $k$ clauses $a_{i1},\ldots,a_{ik}$ and some $k$ clauses $b_{j1},\ldots,b_{jk}$ are true.

To illustrate the difference between the problems, suppose we have two assignments: one assignment satisfies 10 clauses in $\phi_a$ and 1 clause in $\phi_b$, while another assignment satisfies 5 clauses in $\phi_a$ and 4 clauses in $\phi_b$. Then, MAX-SAT would prefer the first assignment since it satisfies $11>9$ clauses overall, while MAX-MIN-SAT would prefer the second assignment since it satisfies at least $4>1$ clauses in both formulas.

Has this problem been studied? It is obviously NP-hard; what is known about approximations?

EDIT: Suppose each formula is a conjunction of $n$ clauses, and each clause is a disjunction of $l$ variables. Suppose we set each variable randomly. Then, each clause is unsatisfied with probability $2^{-l}$. So the expected number of unsatisfied clauses in each formula is $2^{-l}n$. So the expected number of unsatisfied clauses in both formulas is $2^{1-l}n$. So there exists an assignment in which the total number of unsatisfied clauses is at most $2^{1-l}n$. In that assignment, in each formula, at least  $(1-2^{1-l})n$ clauses are satisfied.
So we have a constant-factor $(1-2^{1-l})$ approximation to MAX MIN SAT.
Is there a better approximation?


texts: The role of asymptotic notation in $e^x=1++Θ(^2)$?

texts:
I'm reading CLRS and there is the following:

  When x→0, the approximation of $e^x$ by $1+x$ is
  quite good:
  $$e^x=1++Θ(^2)$$

I suppose I understand what means this equation from math perspective and, also, there is an answer in another cs question. But I don't understand some things, so have a few questions.

Why do they use $Θ$ here and why do they use $=$ sign?
Is it possible to explain how the notation here is related to the author's conclusion that $e^x$ is very close to $1 + x$ when $x \rightarrow 0 $?
Also, how is it important here that $x$ tends to $0$ rather than to
$\infty$ as we usually use asymptotic notations?

I'm sorry if there are a lot of questions and if they are stupid, I'm just trying to master this topic.


texts:
Condidering the proof, NLOGSPACE$\subset$PSPACE
I wrote following proof:
NLOGSPACE = NSPACE$(\log n)$ $\hspace{15pt} \because$ Definition of NLOGSPACE
NSPACE$(\log n)$ $\subseteq$ DSPACE$(\log^2 n)$ $\hspace{15pt} \because$ Theorem(1)
We let $m = \log n$, then,
DSPACE$(m^2)$ $\subset$PSPACE $\hspace{15pt} \because$ Definition(2)
Therefore, NLOGSPACE$\subset$PSPACE.
Theorem(1):
If $S$ is a space constructible function and $S(n) \ge \log n$, then NSPACE$(S(n)) \subseteq$ DSPACE$(S^2(n))$.
definition(2): PSPACE = DSPACE$(n)$$\cup$DSPACE$(n^2)$$\cup$DSPACE$(n^3)$$\cup$...$\cup$DSPACE$(n^k)$$\cup$...
But I am still not that sure if that "We let $m = \log n$" is ok, is this proving NLOGSPACE$\subset$PSPACE?


texts: Universal quantification in description logic

texts:
I'm struggling to understand the universal quantification operator in description logic. Here is an example of the problem:

given the DL concept

$\forall R.A $ (where $A$ is an atomic concept and $R$ is an atomic role)

and an interpretation $\mathcal{I}$ such that $\Delta^\mathcal{I} = \{a\}$ and $R^\mathcal{I} = \emptyset$ and $A^\mathcal{I}$ is empty or not , is it true that $(\forall R.A)^\mathcal{I} = \{a\}$?

More generally speaking, is it always the case that if $R^\mathcal{I}$ is empty then $(\forall R.A)^\mathcal{I} = \Delta^\mathcal{I}$?
Is it a vacuous truth?


texts: Optimization Problem when calculating fitness is expensive

texts:
I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, I am only able to calculate the fitness of 100 solutions per run. Each solution is represented by vector in ten dimensions with real values [0..1], such that two similar vectors represent similar solutions and should have similar fitness.

Obviously I have no expectation of finding a solution that is anywhere near optimal, but is there a preferred method for AI search when you're only able to test the fitness of very few solutions? I get the feeling that I'm missing one or two keywords that would point my search in the right direction.

I'm considering calculus-based search as one option, as it's better to find a local maxima than just randomly search the space and not find any good solutions whatsoever.


texts: Known bounds on space complexity of multiplication decision problem

texts:
Given three numbers $m$, $n$ and $p$ in interleaved binary encoding1, it's obviously possible to check in $O(1)$ space whether $m+n=p$. It's less obvious2 that it isn't possible  to check in $O(1)$ space whether $m\cdot n=p$. I wonder whether one can prove that it isn't possible to check in $O(\log N)$ space3 whether $m\cdot n=p$. On the other hand, are there any known non-trivial upper bounds on the space complexity of this problem, like $O(N/\log N)$?

The problem described above is a simplified version of the "Multiplication decision problem: Is the $k$th bit of the product of $m$ and $n$ a one?" Since this problem is more "powerful" (and also better known), I wonder whether one can show that this problem can't be decided in $O((\log N)^2)$ space.

1. The interleaved binary encoding starts with the lowest significant bit, and allows "leading" zeros for the most significant bits.

2. The proof idea I have in mind would use such an algorithm as building block for a decision procedure of Robinson arithmetic. I call this less obvious, because the fact that Robinson arithmetic is undecidable may be well known, but still remains non-trivial.

3. Here $N$ is the length of the input $m$, $n$ and $p$ in binary encoding.


texts: Is SGD used in machine learning libraries?

texts: SGD (Stochastic Gradient Descent) is used in most libraries of different programming languages. Is it also used in machine learning libraries?


texts: Asymptotic approximation of a recurrence relation (Akra-Bazzi doesn't seem to apply)

texts:
Suppose an algorithm has a runtime recurrence relation:

$   T(n) = \left\{
     \begin{array}{lr}
       g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\
       f(n) & : n < n_0
     \end{array}
   \right.
$

for some constant $0 < \delta < 1$. Assume that $g$ is polynomial in $n$, perhaps quadratic. Most likely, $f$ will be exponential in $n$.

How would one go about analyzing the runtime ($\Theta$ would be excellent)? The master theorem and the more general Akra-Bazzi method do not seem to apply.


texts: Balanced vs Unbalanced KD-tree range search/query complexity

texts:
I'm currently reading up on the time complexity of the range search/query for an unbalanced KD-tree.

I see all these different articles where the same the complexity is O(sqrt(N)) where N is the number of points. And this order of growth is proportional to the number of points a vertical line can intersect with in a KD-tree. But if we create a KD-tree with 7 points, the MAX intersects points from a vertical line should be sqrt(7) = 2,64. Let's assume that it's rounded up to 3. While drawing the some "test" kd-tree's you see this relation is true. But when you draw unbalanced kd-trees, this is not true.

How would you go about analyzing the range search complexity of an unbalanced KD-tree?

My thoughts:
An unbalanced KD-tree would be O(N) since the points/nodes are aligned to one side(Like a linked-list)


texts:
Suppose someone will prove lower bound (for NTM) for co-NP, say exp(n/d) for some constant d. Would it in some way imply lower bound (for DTM) for NP?

Thank you


texts: Is this PDA correct for L = {0^m1^n | n ≤ m ≤ 2n}?

texts: I have drawn this transition diagram for the given language. Is this correct?


texts: Quick method for approximate integer square roots

texts:
I'm looking for an algorithm that -- given a positive integer $n$ -- outputs a positive integer $\bar{n}$ with the following two properties:

$(\bar{n}+1)^2>n$;
$(\bar{n}-1)^2<n$;

So we have $\bar{n}=\lfloor\sqrt{n}\rfloor$ or $\bar{n}=\lceil\sqrt{n}\rceil$ for every $n$.  The point is that I don't care which it is, and it needn't be consistently the same one. As long as properties (1) and (2) are always true, it doesn't matter.

I'd like to find a fast algorithm, especially if there exists one faster than simply doing Newton's Method a fixed number of times. As an example, here's an algorithm always satisfying (1), but unfortunately fails (2) [starting at $n=480$.]

Take the first half of the binary representation of $n$ (call it $m$).
Compute $\bar{n}=(m + n/m) / 2$. (that's integer division.)

Here's an example with $n=7$:

$n=111_2$, so $m=11_2=3$.
$\bar{n}=(3+7/3)/2=(3+2)/2=2$.


texts: Decidability of equivalence problem with limit

texts:
I already know, that the language $$L_0 = \{m \mid \text{the Turing machine $m$ does not stop on an empty tape}\}$$ is not decidable.
If I want to know, if $$EQ = \{\langle m, n \rangle \mid L(m) = L(n)\}$$ is decidable I can reduce $L_0$ to $EQ$.
Because $(L_1 \setminus L_2) \cup (L_2 \setminus L_1) = \emptyset$ iff $L_1 = L_2$, $EQ$ is also not decidable.

But what happens if a limit is added? For example the language $$EQ_{\lim} = \{\langle m, n \rangle \mid \exists x_0 \in \mathbb{N}\colon \forall x > x_0\colon m(x) = n(x)\}.$$

Is it (semi-)decidable? I also try to reduce from the halting problem (more specifically the inverse of the halting problem to proof also semi-decidability), but without success.


texts: Is it possible to balance a already constructed un-balanced AVL tree, with no prior information of last insert?

texts:
Im learning about tree data structures, and had a question that i couldnt find answer to so I came here.

Usually when we balance a tree, we insert keys and keep checking balance factor, as soon as it exceeds the given limit of (-1,0,1) we immediately balance it and continue to insert keys, if any.

But lets say, I construct a tree, and I dont check balance factor after each key is inserted and I just completely construct the tree first and then I calculate balance factor for each node and attempt to balance the tree.

Q) Is it possible to balance tree using such approach ? If yes, then how?

Q) If no, then why not? What would be the flaws/problems that would arise using such approach ?


texts: Hardness of ambiguity/non-ambiguity for context-free grammars

texts:
A grammar is ambiguous if at least one of the words in the
language it defines can be parsed in more than one way. A simple example of an ambiguous grammar
$$
   E \rightarrow E+E \ |\ E*E \ |\ 0 \ |\ 1 \ |\ ...
$$
because the string 1+2*3 can be parsed as (1+2)*3 and 1+(2*3).  For
context free grammars (CFGs) ambiguity is not decidable [1, 2]. This implies that non-ambiguity is also not decidable. Moreover, at least one of ambiguity and
non-ambiguity cannot even be recursively enumerable, for otherwise
ambiguity of a given CFG $G$ could be decided by running the
enumeration of ambiguity and non-ambiguity together and seeing which
one contains $G$ (and one of them must).

So which problem is harder in this sense? Ambiguity or non-ambiguity?

D. G. Cantor, On The Ambiguity Problem of Backus Systems.
R. W. Floyd, On ambiguity in phrase structure languages.


texts: Is the following recurrence for this program's runtime correct?

texts:
Let $f$ and $g$ be two functions and $p$ a number. Consider the following program:

Recurs(v,p) :
  find s < v such that f(s,v) < v/2 and g(s,v-s) < p

  if no such s exists then
    return v
  else if s <= v/4 then
    return v-s U Recurs(s,p)
  else if s > v/4 then
    return Recurs(s,p) U Recurs(v-s,p)
end

Can the recurrence for the running time of this recursion be $T(v)=T\left(\frac{v}{4}\right)+T\left(\frac{3v}{4}\right)+1$?


texts: Difference between bit times and milli seconds

texts: The propagation delay between two links is 200 bit time .....i want to know what is the difference between 200 bit time and 200 mill seconds


texts: Need help with recurrence relation and postcondition of a function

texts:
I just wanted to make sure I'm on the right track regarding this.
Here's the function that I'm dealing with:
import math

def Mystery2(A, f, l):
    if f == l:
        return A[f]
    m = math.floor((f+l)/2)
    x = Mystery2(A, f, m)
    c = 0
    i = f
    while i <= l:
        if A[i] == x:
            c = c + 1
        i = i + 1
    if c > (l-f+1)/2:
        return x
    return Mystery2(A, m+1, l)

The precondition is given as: A is an array of integers, and $f$ and $l$ are integers $0 \leq f \leq l < len(A)$.
From what I can see by running the function, the postcondition appears to be that it outputs the element within f and l indices that occurs more than $ \frac{l-f+1}{2}$ times or A[l].
I'm not sure how to find a closed form for the recurrence relation representing the worst case runtime.
So far I figured that with $T(n)$ being the worst runtime of the function and $n = l-f$, $T(n)$ will be constant if $n = 0$ and $T(\left \lfloor \frac{n}{2} \rfloor \right) + T(\left \lceil \frac{n}{2} \right \rceil - 1) + n*c_1 + c$, if $n > 0$. I'm not sure how to convert this into a closed form.
Is it okay to simplify this into $T(\left \lfloor \frac{n}{2} \rfloor \right) + T(\left \lceil \frac{n}{2} \right \rceil) + n*c_1 + c$ for the purpose of comparing it to the master theorem?
Thanks in advance for any help


texts: Understanding lexical grammar for multi-line comments in JavaCC

texts:
I'm struggling to understand why this piece of lexical grammar works for multi-line comments in JavaCC (posted here):

 "/*" (~["*"])* "*" (~["*","/"] (~["*"])* "*" | "*")* "/"

As I read it, the parser scans the input /*, and then zero or more optional occurrences of * can appear, followed by a *, and then zero or more optional occurrences of * and /, then zero or more occurrences of * followed by * or *, ended by a /. Specifically, this part boggles my mind:

 (~["*","/"] (~["*"])* "*" | "*")*

I'd appreciate some help understanding this.


texts:
I understand the idea behind making a MA protocol perfectly complete. In a MA protocol, Merlin sends a proof $\pi$ which Arthur checks with his machine $V$ by plugging in some random bits $r$ such that whenever $x \in L$, $\Pr[V(x,\pi,r)\text{ accepts}]$ is exponentially high and is exponentially low otherwise. Like in the proof of $BPP \in \Sigma_2$, there are relatively few bitvectors $z_1, \cdots z_l$ such that translating the set of "good" random bits with them cover the entire space of such bits. The perfectly complete protocol also requires the prover to provide these strings.

I have seen various sources casually mentioning that any AM protocol can be modified to achieve perfect completeness. How can this be achieved?

Can this also be done for IP?


texts:
Given an N x M matrix. The task is to repeat the following steps K! times.

Add all the elements of the matrix and get a matrix sum (S) % mod 10^9 + 7
Add S to all the elements. % mod 10^9 + 7
Repeat.

What I can think of regarding the complexity it will O(K! x N x M).

But K ranges from 1 to 10^5 and this is a huge number of iterations for a computer to process.

Is there a way to optimize these operations so that these can be performed using less computational resources.

Thank You.


texts: When does the product automaton of two NFAs A and B not decide L(A) U L(B)?

texts:
We are given the following task:

Let $\mathcal{A} = {}(Q_A,\Sigma, \delta_A, s_A, F_A)$ and $\mathcal{B} = {}(Q_B,\Sigma, \delta_B, s_B, F_B)$ be two NFAs and let their product automaton be defined as:
$\mathcal{A} \times \mathcal{B} = {}(Q_A \times Q_B,\Sigma, \delta, (s_A,s_B), F)$ with
$\delta = {}\{ ((p,q),\sigma,(p',q')) \mid (p,\sigma,p') \in \delta_A, (q,\sigma,q') \in \delta_B \}$ and
$F= {}(Q_A \times F_B) \space \cup \space (F_A \times Q_B)$

(So the accepting (combined) states are the ones where at least one of the two individual states of $\mathcal{A}$ or $\mathcal{B}$ is accepting.)

Give an example for two NFAs $\mathcal{A}$ and $\mathcal{B}$ so that their product automaton $\mathcal{A} \times \mathcal{B}$ does not decide the language $L(\mathcal{A}) \space \cup \space L(\mathcal{B})$.

Now the one thing that is by far confusing me the most (and what I want to focus on in this question) is the following tip that is given as well:

Tip: There is an example in which $\mathcal{A}$ only has one state.

I can't see how that could be possible, with the following reasoning:
If $\mathcal{A}$ only has one state - let's call it $q$ - this means two things:

$q$ is either accepting or it is not accepting
All of the transitions of $\mathcal{A}$ start at and directly lead back to $q$.

Based on 1. we have two cases.
Let's first consider the case that $q$ is accepting ($q \in F_\mathcal{A}$). Because of 2. it follows that $\mathcal{A}$ accepts every word $w \in \Sigma ^*$ (so $L(\mathcal{A}) = \{w \in \Sigma^*\}$).
Let $\mathcal{B}$ be an arbitrary NFA. Based on the definition of $F$ and the fact that $q$ is accepting it is clear that all of the states of $\mathcal{A} \times \mathcal{B}$ will be accepting as well, which implies that the product automaton also accepts every $w \in \Sigma ^*$.
This means that $\space L(\mathcal{A} \times \mathcal{B}) = \{w \in \Sigma^*\} = L(\mathcal{A}) \space \cup \space L(\mathcal{B})$.
Now let $q$ be non-accepting ($q \notin F_\mathcal{A})$. Again, based on the definition of $F$ we can see that the accepting states of $\mathcal{A} \times \mathcal{B}$ are going exactly correspond to the accepting states of $\mathcal{B}$.
Point 2 implies that the transitions of $\mathcal{A}$ will "not have any impact on the transitions of $\mathcal{A} \times \mathcal{B}$", by which I mean that the product automaton is going to have the same transitions as $\mathcal{B}$ and therefore be isomorphic to $\mathcal{B}$, which again results in
$L(\mathcal{A} \times \mathcal{B}) = L(\mathcal{B}) = L(\mathcal{B}) \space \cup \space \varnothing = L(\mathcal{B}) \space \cup \space L(\mathcal{A})$
(since $\mathcal{A}$ doesn't accept any input, which means $L(\mathcal{A}) = \varnothing$)
This proof is trying to show that if $\mathcal{A}$ only has one state, then $\mathcal{A} \times \mathcal{B}$ will always decide $L(\mathcal{B}) \space \cup \space L(\mathcal{A})$.
Obviously, there has to be a logic fault in my thinking and in the proof above somewhere, which I can't seem to be able to figure out, so I'd really appreciate if anyone could point out what I'm missing.


texts: what is the best theory/model to use for prediction in multivariate data?

texts:
I use a software for pollutant propagation on rivers that takes as input a set of parameters (p1, p2, ...pn) and creates an output file which is basically a matrix where on each row there is represented the concentration of pollutant in various places along the river at a given timestamp.

\begin{array} {|r|r|r|r|r...|r|}
\hline
TIME &500m&1000m&1500m&2000m&2500m&...&25000m \\
\hline
 2015/12/07 - 4:50:00&0.75&0.71&0.6&0.58&0.55&...&0.12 \\
\hline
\hline
 2015/12/07- 4:55:00&0.71&0.70&0.58&0.56&0.51&...&0.10 \\
\hline
\end{array}

My  question is: what models/theories are suitable to be used to predict, based on a set of given INPUT parameters, to predict the OUTPUT that would be closest to what the software will give as result?
And how many pairs INPUT/OUTPUT will I need to have in order to minimize the error?

P.S: If this is not the right forum to post this please redirect me to the proper one.

Thank you.
Regards,
Sorin


texts: structural operational semantic equivalence

texts:
We add the following derivation rule to the structural operational semantic:

< repeat S until b, s >$\Rightarrow$ < S; if b then skip else (repeat S until b) >

Prove that "repeat S until b" is equivalent to  "S; if b then skip else (repeat S until b)" in the structural operational semantic.

I've tried the following:

In one direction:

Asumming < S; if b then skip else (repeat S until b), s > $\Rightarrow^*$ s'

We can prove < repeat S until b, s > $\Rightarrow$ s'

by using the specified derivation rule and the assumption:

< repeat S until b, s >$\Rightarrow$ < S; if b then skip else (repeat S until b) > $\Rightarrow$  s'

How can we prove the other direction?


texts: Lambda term satisfying two equations using Bohm Trees

texts:
Hi I'm trying to solve this exercise but I can't find any material online, it's not an homework I actually have sort of a solution (it looks incomplete though), but from that I can't really understand much about how to tackle the problem. Anyway we're asked to find a term $\Delta$ such that:
$$
\left\{\begin{matrix}
\Delta(\lambda x y. x (y(\lambda u.yuy)x)x)=y_1
\\
\Delta(\lambda xy.x(y(\lambda u.yu(\lambda abc.cab))x)x) = y_2
\end{matrix}\right.$$

I looked at a similar exercise where the idea was to define $\Delta$ to be an abstraction of the type $\lambda x. x R_3$ where $R_3$ is the ROTATION operation on Bohm Trees (takes the leftmost child of a tree with k+1 subtrees and makes it the new root).

Could someone please explain me how to solve these type of problems? thanks


texts: Partitioning a bipartite graph to get disjoint components of same size

texts:
I have a bipartite graph $G = (V, E)$ where $V = S \cup T$ is the division into the two halves. I want to select $n$ elements from $S$ and $nk$ elements from $T$ such that the graph they generate has $n$ connected components, each of size $k+1$ and containing one element of $S$. To be clear, $n$ and $k$ are inputs to the problem: it's not a maximisation problem.

The naïve brute force algorithm would consider $\binom{S}{n}$ candidate subsets of $S$, and would do $O(E)$ work for each to identify vertices in $T$ which have an edge to exactly one element of the candidate subset of $S$. For fixed $n$ that's $O(S^n E)$.

I'm not optimistic, because it's an independence problem, but is there an algorithm for fixed $n$ and $k$ whose running time is polynomial in $E$ with exponent independent of $n$ and $k$?


texts:
I am developing a chart and graph library and am having trouble developing an algorithm.

**This is not a homework assignment for a student. See my open source project: https://github.com/eddieios/CoreChart

The algorithm is to space the Y axis labels in a given coordinate graphical space. It should space the labels at about 50 pixels apart, but have no less than 5 labels. All data points are assumed to be positive integers. The labels should be multiples of 5 (so as to have nice clean numbers). The last label can be smaller or larger than the maximum possible value, but it should be the closer of the two. The algorithm inputs are 1) the maximum possible value from the chart data, 2) the height of the graphical space. The output is a list of labels and their vertical positions.

For example:

Maximum possible chart value = 79
Height of graphical space = 200

Output would be:

Label: 0, Vertical Position: 0
Label: 20, Vertical Position: 50
Label: 40, Vertical Position: 100
Label: 60, Vertical Position: 150
Label: 80, Vertical Position: 200

I have written the following code (Obj-C). But I'm having trouble handling end-cases. For example, if the maxValue = 39, then the labels are set 5 apart. The optimal case here would be to set labels 10 apart. There's something about I'm deciding how many labels there should be that isn't working for all cases.

int maxValue = 39;
float graphHeight = 259.0f;

int numLevels = (int)(graphHeight / 50.0f);

float offset = (int)(maxValue / (float)numLevels);
offset /= 5;
offset = (float)((int)(offset + 0.5));
offset *= 5;

CGFloat stepY = graphHeight * ((float)offset/maxValue);

for (int i = 0; i <= numLevels; i++) {
    NSLog(@"label %f position %f", i*offset, i*stepY);
}


texts: What are the strengths and limitations of arrays? What considerations go into choosing an array over another data structure, or vice-versa?


texts:
System: Application

OS: Scheduler, VMM, IPC, FS Drivers, dispatchers, VFS

The above would be a monolithic kernel. In a monolithic kernel all core OS functions are separate from user spaaaaaace. Functions such as the FS are handled completely by the kernel. This leaves the end user/dev open to write applications that rely solely on the kernel to emulate and process the functions. The BSD tree, AIX, and HP-UX are good examples of monolithic kernels.

System: Application

User Mode: Application IPC, Unix Server, Drivers, File Server

OS: Basic IPC, VMM, Scheduling

This is a microkernel. A microkernel is responsible solely for physical emulation of the machine code. It provides a more secure functionality, but also allows for better hardware processing. User spaaaaaace is where drivers are handled, sometimes grating DMA. Also, it can improve computing processing time if the user spaaaaaace is streamlined for direct machine emulation. JXOS and various nanokernels are good examples.

System: Application

User Mode: Drivers, Unix Server, Application IPC

OS: Microkernel, Kernel Drivers, IPC, HAL

This is a hybrid kernel. A hybrid kernel is mix between a monolithic kernel and a microkernel. Software drivers are handled in user mode, but hardware drivers are handled by the kernel. This allows for a lot of flexibility in design, as some packages and application functions can run directly against the kernel. However, this leaves the kernel open to a lot of security vulnerabilities. The most well-known hybrid kernel is Windows NT.

My architect was testing my knowledge of kernels, and this is what I sent him. He said that I wasn't wrong, I just have a very different approach to it. When interrogated about it, he just told me it was different. How is it different? Does it look different?


texts: Consistency of a set of bidirectional typing rules

texts:
Main
Is there any way to algorithmically check the consistency of a set of bidirectional typing rules, e.g. the absence of cycles and the uniqueness of the derivation tree? This problem is naturally similar to the problem of grammar unambiguity checking, except you also gotta manage side effects applied to the typing context.
Update
Ok, from reactions I figured that this question needs more context:

I am not building a bidirectional type system.
Instead I am building it's sanity checker.
I presume, that there is a serialized representation for a set of rules, like yaml, json, what have you.
By the time I get an instance of that representation it is presumed to be a syntactically (and schema-wise) valid document.
Now, it is obvious that being a valid document doesn't give any guarantees about rules consistency with one another:

There might be several premise sets for a given conclusion.
There might be several different conclusions from a given premise set.
Premises and corresponding conclusions might be in a cyclic dependency on one another.
Maybe something else.

All in all, having a valid rule set S, just add a wildcard inference rule like $$ \frac{}{\Gamma \vdash a \Rightarrow Int} $$
and you will get the rule set S' that is either ambiguous (if there is no rule ordering) or 'non-minimal' at best (if wildcards go at the end).
So, those bad things can happen, and it seems like there must be a paper or something considering discussed problem.


texts: How to prevent moire artifacts in this light casting algorithm?

texts:
I am writing a 2D light casting algorithm with OpenGL compute shaders.
The algorithm is simple:
For each light source shoot out light rays from it, the ray begins at the light coordinates, it ends at a pixel in a circle around the light source (the light distance). When calculating the ray sample the pixel underneath it to model light colour/alpha changes. The algorithm works well, but a few pixels are missed. The lightrays are calculated in a compute shader parallelly, one thread for each pixel in the light border circle. This means for example for a light with 256 radius, there are 2*256*Pi=1608 threads on the GPU, each calculating a single ray.

Heres the relevant compute shader code:

#define LOCAL_WG_SIZE 128u
const float PI = 3.1415926535897932384626433832795;
const float RAY_LENGTH = 256.0f;

// get the number of the current thread (0...1608)
uint renderNodeNum = local_coords;
// get the endpoint of the ray, it will be on a circle
endPoint.x = int(RAY_LENGTH * sin(float(renderNodeNum) * PI / 1024.0f)) + lightPos.x;
endPoint.y = int(RAY_LENGTH * cos(float(renderNodeNum) * PI / 1024.0f)) + lightPos.y;

// vector approximation. Works, but has moire artifacts.
// I've also tried Bresenham's line algorithm, but it leaves a cross shape as the light fades which looks ugly.
vec2 dt = normalize(vec2(endPoint - lightPos));
vec2 t = vec2(lightPos);
for (int k = 0; k < RAY_LENGTH; k++) {
    coords.x = int(t.x);
    coords.y = int(t.y);

    // calculate transparency
    transpPixel = imageLoad(transpTex, coords);
    currentAlpha = (transpPixel.b + transpPixel.g * 10.0f + transpPixel.r * 100.0f) / 111.0f;
    // calculate color
    colorPixel = imageLoad(colorTex, coords);
    lightRay.rgb = min(colorPixel.rgb, lightRay.rgb) - (1.0f - currentAlpha) - transmit;
    currentOutPixel = imageLoad(img_output, coords);
    currentOutPixel.rgb = max(currentOutPixel.rgb, lightRay.rgb);
    currentOutPixel.a = lightRay.a;
    // write color
    imageStore(img_output, coords, currentOutPixel);

    t += dt;
}

Heres is how it looks:

Another example with coloured background that shows light propagation, with the same artifacts:

So I need a new algorithm to draw these light rays (or any other method that is highly parallellizable) that does not leave out some pixels (the black spots in the pic). I could oversample the lightray (for example shoot twice as many rays), but this would be way too expensive, there must be a cheaper solution.


texts: Polynomial time optimisation algorithm for a poly-time computable function with bounded number of maxima?

texts: Suppose we have a polynomial time algorithm for computing a function (we think of as existing on rational numbers between $0$ and $1$ of limited binary length n). We know that this function is made up of $m$ strictly monotone functions or equivalently that it has up to $m-1$ maxima/minima. Can we find these maxima in time that is polynomial in $m$ and $n$?


texts: Unfeasible linear program becomes feasible if a variable is removed

texts:
Apologies, not a computer scientist by trade but I'm playing with linear programming these days.

Let $\{x_i\}$ be $N$ optimization variables with bounds

$$l_i \leq x_i \leq u_i$$

I'm interested in telling if $\exists$ a feasible region under the constraint

$$\sum_i x_i = C$$

for a fixed value of $C$.

This is pretty easy (just check that $\sum_i l_i \leq C \leq \sum_i u_i$). But sometime it happens that while

$$\sum_i x_i=C\,$$

is too constraining,

$$\sum_{i\notin {\mathcal{S}}} x_i =C\, , $$
has a feasible region for some subset of index $\mathcal{S}$.

But at first sight it's hard to tell because there's $N$ variables, such that a brute force check runs in $2^N$.

Examples: $l_x=l_y=10$, $u_x=u_y=30$ and $C=15$  is not feasible but it would be feasible if one was to remove either $x$ or $y$ from the problem.

Is there some elegant solution to this problem? There's a nice geometrical way of understanding the problem.
In the two variable cases, removing either $x$ or $y$ amounts to projecting the region bounded by $[l_x, u_x],[l_y, u_y]$ onto $y$ or $x$ axis respectively. Then it's only a matter of asking whether the line $x+y=C$ crosses either of the "projected" regions (which are now lines).


texts: Best algorithm / method to determine path length from noisy GPS points

texts: i am analyzing a series of GPS points (with time stamps) which are noisy meaning have an accuracy of about 15 meter radius (sometime even more), and i need to extrapolate the distance the vehicle has gone via those GPS points, what is a good algorithm / method to solve such issues ?


texts:
Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible universal sets of gates that do not utilise the NOT transformation. Thanks!

EDIT: to clarify, you can perform any set of operations you want, but if there is some sequence that you apply these operations in that is equivalent to a NOT operation then they are forbidden. For example, in quantum computing you can take the square root of a not operation, but as applying two of these gives a not operation then this would not be allowed


texts: How would I write a single expression involving count, x and y that has exactly the same effect as shown (below)?

texts:
count=0
x=7
y=3
while(y<x):
     y+=1
     count+=1

I'm having trouble writing this as a single expression.


texts: Linear time algorithm for least positive integer missing from array

texts:
Design a linear time algorithm for finding the least positive integer missing from an unsorted array. Changes in the array are allowed.
For example, for the array -10,-1,2,3,6,30, the answer is 1.

I thought about finding the maximum and minimum numbers in the array (this is $\Theta(n)$), then a loop from the minimum number to the maximum number, and in every iteration, check if the current number is in the array, but this will take $\Theta(n^2)$.


texts: Maximum Expected Fishing Day (Recurrence Relation)

texts:
John joined a meetup where organize day long fishing trip once a
  month. The organizers are vary poor at planning, so will organize
  fishing on a random day of the month without any advance notice.
  Sadly, John needs to inform his boss in order to get time off from
  work at least a day in advance. With this situation, John is forced to
  schedule vacation days and hopping that the fishing will take place on
  them. At the same time, he can be strategic about it. For instance, he
  can wait until the end of the month at which point the fishing would
  have already happened or will guarantee to occur the next day. John
  can use a total of v  day of vacation for the next m months. What is
  the greatest expected number of fishing meetup that he can arrange to
  attend? For simplification, we can assume that a month is only 30 days
  longs.

  It can be approached as: Defining the sub-problems as Maximum Expected
  Fishing Days MEFD: for every situation MEFD(m,d,v), where m is the
  number of months left including the current month, d is the numbers of
  days left in the current one, and v is the number of vacation days
  john left with the assumption that the fishing has not took place in
  the current month.

  Base case: for any (m,d,v) such that i, j or l equals to 0,
  MEFD(m,d,v) =0

  Recurrence Relation: MEFD(m,d,v) = max(MEFD$_{1}$(m,d,v),
  MEFD$_{2}$(m,d,v))

  MEFD$_{1}$(m,d,v)=$\frac{1}{d}$(1+MEFD(m-1,30,v-1))+
  $\frac{d-1}{d}$MEFD(m-1,d-1,v),

  MEFD$_{2}$(m,d,v)=$\frac{1}{d}$(1+MEFD(m,30,v-1))+
  $\frac{d-1}{d}$MEFD(m,d-1,v).

What does $\frac{1}{d}$ or $\frac{d-1}{d}$ means? Why do we need to multiply them ? Let's MEFD$_{1}$ means that the Maximum Expected Fishing Day that John takes a vacation day off in the next day. then it would fall into two cases: 1, fishing meetup take place, 2, it didn't take place.
As we can tell from MEFD$_{1}$,  1 + ing means fishing meetup take place, then we - 1 from the months left and - 1 from vacations left.

What do we also need to -1 from months and vacations of the second part of the equation, + $\frac{d-1}{d}$MEFD(m-1,d-1,v)?

Or am i am reading this recurrence relation completely wrong? any points are really appreciated.


texts:
Say I have total 4 bytes on 1 byte addressable memory, with a 32 bit bus.

If I move value at 0'th address to one of the registers will system grab all 32 bits (all 4 bytes) through bus from memory, reprocess it to extract 0'th address value behind the scenes?

Or will it get exactly one byte through bus?


texts:
Problem:

Looking for an efficient algorithm to find the largest value that exists in all columns.

Constraints:

The values in each column are always decreasing

My algorithm:

Check the first row for match
Use the lowest value from first row to search for match
Use the value from row x, column y to search for match
Increase row index until n
Increase column index until n

Examples:

Best case
$$A=\begin{bmatrix}17 & 17 & 17\\ 14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\end{bmatrix}$$

Select Row1,Col1 to match
17, 17, 17

Result is 17

Average case
$$B=\begin{bmatrix}13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\\ 9 & 5 & 10\end{bmatrix}$$

Select Row1,Col1 to match
13, 10, 15

Select lowest value in Row1 (10)
10, 10, 10

Result is 10

Worst case
$$C=\begin{bmatrix}14 & 14 & 16\\ 13 & 10 & 15\\ 11 & 8 & 13\\ 10 & 7 & 12\end{bmatrix}$$

Select Row1,Col1 to match
14, 14, 16

Select lowest value in Row1 (14)
14, 14, x

Select Row2,Col1 to match
13, x, 13

Select Row2,Col2 to match
10, 10, x

Select Row2,Col3 to match
x, x, 15

Select Row3,Col1 to match
11, x, x

Select Row3,Col2 to match
x, 8, x

Select Row3,Col3 to match
13, x, 13

Select Row4,Col1 to match
10, 10, x
(repeated!)

Select Row4,Col2 to match
x, 7, x

Select Row4,Col3 to match
x, x, 12

Result is no matches


texts: What is context free grammer of $L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$

texts:
I can't find out how to find a context free grammar for bellow language, is there any specific way to solve that?

$L = \{w: n_c(w) \ne  n_a(w) + n_b(w)\}$


texts: How to sample uniformly from a stream of elements, some of which are unsuited?

texts:
I get values $x_t$ in an online fashion and want to buy "good" ones, where "good" means that some measure $P(x_t) >T$. Consider the following simple algorithm.

T = 0.7
N = 100 // or any value N > B
B = 20 // or any value 1 < B < N

l = 0

for t from 1 to N:
    input a new observation x_t
    let P(x_t) the probability associated to x_t

    if P(x_t) > T:
        l = l + 1
        pay 1 dollar to buy y_t the label of x_t
        output immediately the label y_t

If the condition $P(x_t) > T$ is used then we get about $l = 100-70 = 30$, this is ok since the value of $T$ is set to $0.7$.

Now if I want to add a constraint which is: additionally to the fact that elements $x_t$ for which the label $y_t$ is purchased are those for which $P(x_t) > T$, I want also that we do not buy more than $B=20$ labels (for example because we only have 20 dollars as budget).

But the problem is that, if I replace the the condition ($P(x_t) > T$) by ($P(x_t) > T \wedge l < B$), then the elements $x_t$ for which we buy a label are more likely to be among the first elements $t$ that we browse (that is, for an element $x_{95}$ for $t = 95$ for example we will never have a chance to buy its label even if its probability was $P(x_{95}) \gg T$). But I want that all the elements from $t = 1$ to $N$ will have equal chance to buy their label (not advantaging only the first elements).

Note: the condition that $P(x_t) > T$ for buying the label of a new observation $x_t$, should not be removed from my code. This is important for me: only labels of observations for which $P(x_t)$ was higher than $T$ at time $t$, are possibly purchased; and we should not purchase more than our budget $B$. Note also that a purchased label should immediately be output after we buy it, we should not wait until the end to decide if we buy it or not.

Also, note that we do not have the N elements beforehand; at each time $t$ we see just one new observation $x_t$. And note that you pay 1 dollar when you select a given $x_t$ to ask for its label and that you should output answer (label of selected $x_t$) immediately; so you can not select some $B$ elements then replace them with new selected other elements, because your budget $B$ will already be finished.


texts: Is two-coloring parts of a bipartite graph so that for each uncolored vertex, the incoming edges from each color are roughly equal NP-complete?

texts:
Let's say we have a bipartite graph $G=(V_1\dot\cup V_2,E)$.

We're now looking for a two-coloring (red/blue) of the vertices of $V_1$, so that for all vertices $v\in V_2$ the sum of edges coming from red vertices differs at most by 1 from the sum of edges coming from blue vertices.

In other words, we're looking for a two-coloring $c:V_1\to\{-1,1\}$ so that the following formula holds:
$$
\forall v\in V_2:\left( \sum_{v'\in V_1\\\{v,v'\}\in E}c(v')\in \{-1,0,1\}\right)
$$

My question: Is finding such a two-coloring (or showing that no such two-coloring exists) NP-complete?

There's a (somewhat) linear algebra formulation of this problem, though it doesn't seem to be very helpful:

Let $V_1 = \{v_1,...,v_n\}$. Then we can define for every vertex $v\in V_2$ the row vector $(k_{1,v},...,k_{n,v})$ with
$$k_{i,v} =\begin{cases} 1,&\text{if } \{v_i,v'\}\in E\\ 0,&\text{else}\end{cases}$$.

If we now let $c_i\in \{-1,1\}$ be the color of vertex $v_i$, then the requirements for the two-coloring can be written as:
$$
\forall v\in V_2:\qquad (k_{1,v},...,k_{n,v}) \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\}
$$
or equivalently with $V_2 = \{v'_1,...,v'_m\}$:
$$
\pmatrix{k_{1,v'_1}&...&k_{n,v'_1}\\...&...&...\\ k_{1,v'_m}&...&k_{n,v'_m}} \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\}^m
$$


texts: How is electricity brought to the transistors?

texts: I feel like my knowledge of computer science is being hindered by this one concept. I understand the concepts of transistors and how a flow of electricity  can turn a transistor on or off, and with the power of logic gates, this can form the foundation of programming. What I do not understand is how these microscopic transistors are turned on or off, and how  electricity gets there in the first place. Thanks.


texts:
Is there a problem like 3 SAT like problem in P where if we find an algorithm for this problem, we can solve all problems in P?

For instance if we solve this problem in P, may be we can solve prime detection quickly instead of using AKS algorithm or linear programming quickly?


texts: change the info part of each node in binary tree

texts:
i have a binary tree.

         2
       /   \
      3     4
     / \     \
    5  1      8
     \       /
     6      9

I want to change the info part of each node such that the

nodeinfo = nodeinfo + nextInorderNodeInfo

so the actual inorder traversal

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

will change to

5+6,6+3,3+1,1+2,2+4,4+9,9+8,8+0

11, 9,  4,  3,  6,  13, 17, 8

i need to write a function that will modify the binary tree info parts of each node.

i have done the following

calling

change(root,NULL);

function definition

void change(node* n, node *k)
{
 if (n)
  {
    if (n->left) change(n->left,n);
    if (n->right) change(n,n->right);
    n->info + = k->info;
  }
}

in this way i am not able to modify the nodes that are right hand leaf nodes.

can someone give the correct solution..???

thanks in advance


texts: What exactly is a linear function, and what is a nonlinear function?

texts:
I am learning a bit about machine learning, and I frequently see things labeled "linear function" or "nonlinear function."

For example when discussing a neural network created by combining individual logistic regression nodes, a book I read noted that logistic regression is a linear function, and that the entire network would be no more powerful than a linear model except that a nonlinear function (such as relu or tanh) is applied to each node. I don't really appreciate this, because I don't have a firm grasp on the definition of linear function.

To use a simpler (to me) example, I was confused when I learned that both SVM and linear regression are linear models. It is easy for me to see how linear regression is a linear model, because its calculations are similar to the definition of a line, y = mx + b, that I learned in middle school. SVM seems more exotic to me.

So how can we know if something is a linear function/model versus a nonlinear one? Does it have to do with how the inputs are gathered, or the nature of the calculations afterward?


texts: Arithmetic Encoding vs Adaptive Arithmetic Encoding

texts:
I am working on a personal project and I am having some conceptual level questions on arithmetic encoding.

Let's take a scenario where I have an array of sensors and the data collected is transmitted over the internet to Alice. Naturally to decrease transmission cost I would want to transmit data in compressed form. But the data source is non stationary in nature and I have read that we use Adaptive Arithmetic Encoding in such scenario. But I can do this trick that, collect sensor data in a fixed size buffer and when buffer is full then use Normal Arithmetic Encoding and send the encoded sequence over the internet. So my question is why would I want to use Adaptive Arithmetic Encoding in this scenario and what advantage will it serve me? If the above stated scenario is not applicable please explain using other example.
Have I understood both the concepts correctly? (By checking algorithms of both and please point out mistakes if any)

    Arithmetic Encoding

    start
        statistical_model = collect_stats(data) //we need to perform single pass over data to collect stats
        for each symbol in data:
            probability_distribution = statistical_model(symbol) //calculate conditional probability distribution for the current symbol given previous n symbols
            current_state = artimetic_encoding(probability_distribution, previous_state)
        return current_state
    end

    Adaptive Arithmetic Encoding

    start
        statistical_model = init() // initialize the model in such a way which is known to both encoder and decoder (for example: zero initialization)
        for each symbol in data:
            probability_distribution = statistical_model(symbol) //calculate conditional probability distribution for the current symbol given previous n symbols
            current_state = adaptive_artimetic_encoding(probability_distribution, previous_state)
            update_model(statistical_model, symbol)
        return current_state
    end


texts: a conjunctive normal form that is a tautology

texts:
Are there any examples of CNF formulas that are tautologies?
Such that every clause contains different variables so phrases like (a or not a) are rejected?


texts: What the difference between the Fourier Transform of an image and an image histogram?

texts:
Consider this small picture of a sunflower, and its histogram:

  What would the Fourier transform of the first picture look like?  Is there any relationship between the histogram and the Fourier transform?


texts: Enumerating all partial permutations of given length in lexicographic order

texts:
I need to generate all unique tuples of length k chosen from a series of unique, positive integers. In my case n choose k will have n=10, 1 <= k <= 10; and the series I am choosing from is { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }  .
For each chosen tuple, all of its permutations need to be present in the output. For example, for k = 2, the chosen tuple (0, 1) needs to have both (0, 1) and (1, 0) in the output. The output overall needs to be in lexicographic order, which in turn implies that lexicographic ordering of permutations within a given chosen combination is not enough.
I'm following along with
https://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture25.html
which offers a simple recursive algorithm to generate combinations. Their recommendation to do this:

Note that you can get all permutations of n things taken k at a time by simply calling perm (v, maxk, 0); at the base case of combinations. This generates all k! permutations of each of the n C k combinations, taking O(k! n (n C k)) = O((n+1)!/(n-k)!) time.

gets me 90% of the way there, but yields result tuples in an order that is not useful to me. For k=2 it yields
[0, 1]
[1, 0]
[0, 2]
[2, 0]
...

where I would want it to yield
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[0, 5]
[0, 6]
[0, 7]
[0, 8]
[0, 9]
[1, 0]
[1, 2]
...

Is there a modification to this algorithm - or a different one - that will do this? I hope it doesn't require putting everything in memory and then applying an in-place sort.


texts: Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point

texts:
I have a large set of lines in 2D with a known start point and end point, and would like to find the nearest (defined by perpendicular distance) of those edges (or the extension of those edges past their start and end points) to an arbitrary point.

The best I have done so far is to generate a set of sample points along each line and use a KD-tree to solve the nearest neighbor problem for the points - i.e. find the nearest line sample point to the query point. But this is inaccurate and needs a large number of samples for long lines.

I did see this:
Algorithm for nearest edge detection with respect to a point (in all directions)

but it relied on a sweep method and a small number of lines of finite length.


texts: Articulation points (or cut vertices), but only subset of vertices need to be connected

texts:
I know we can find all articulation points efficiently in a graph using DFS.

But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is a path between them). How to efficiently find all nodes (vertices) which removal will cause at least one of the mentioned pairs to be disconnected (can't communicate with each other)?

For example, we can have different cases for image below (undirected graph):

If pairs are A-B and C-D, then 2 is not vertex cut, because pairs
remain connected.
If pairs are A-C and B-D, then 2 is vertex cut,
    because pairs can't communicate (there is no path between them).

If we know set of pairs that need to communicate, what is the most efficient way to find all "vertices cuts"?


texts:
I am working on dense matching using DSP algorithm.
They have used belief propagation to optimize their energy function?
How do we do it?
I mean how do we assign prior belief?
Link: Deformable Spatial Pyramid Matching for Fast Dense Correspondences


texts: Trying to understand the proof of the halting problem presented in Sipser textbook

texts:
I'm having some problems to understand the classic proof of the halting problem.

The Proof:

$A_{tm} = ${$<M,w>$ | $M$ is a $TM$ and $M$ accepts $w$}.

We assume that $A_{tm}$ is decidable and obtain a contradiction.

  I have no problem to imagine that. It's a machine that accepts some string $w$. But it must not accept others strings $not-w$. And if it's decidable, it always halts.

Suppose that $H$ is a decider for $A_{tm}$. On input $<M, w>$, where $M$ is a $TM$ and $w$ is a string, $H$ halts and accept if $M$ accepts $w$. Furthermore, $H$ halts and rejects if $M$ fails to accept $w$. In other words, we assume that $H$ is a $TM$, where

\begin{equation}
  H(<M, w>)=\begin{cases}
    accept  &\text{if $ M$ accepts $w$}.\\
    reject & \text{if $ M$ does not accept $w$}.
  \end{cases}
\end{equation}

  Here I have the impretion that $H$ is doing the same thing that $A_{tm}$ does.
  But If it's saying that $H$ is decider, I can assume that $H$ has some magic power to discover if $A_{tm}$ will halt in input $w$

Now we construct a new Turing machine $D$ with $H$ as a subroutine. This new TM calls H to determine what $M$ does when the input to M is it own description $<M>$. Once $D$ has determined the information, it does the opposite. That is, it rejects if $M$ accpets and accepts if $M$ does not accept. The follow is a descripion of $D$:

  No problem here.

\begin{equation}
  D=\begin{cases}
    1.  &\text{Run $H$ on input <M, <M>>}.\\
    2. & \text{Output the oposite of what $H$ outputs; that is, if $H$ accpets, reject and if $H$ rejects, accept}.
  \end{cases}
\end{equation}

  Here is where I find hard to understand. The input string of $H$ is $<M, w>$, how could it run some thing like $<M, <M>>$ ?

  If was only $<M>$, I could imagine that $w$ is the empty string.

I understand the halting problem with  the following code:

function halts(func) {
  // Insert code here that returns "true" if "func" halts and "false" otherwise.
}

function deceiver() {
  if(halts(deceiver))
    while(true) { }
}


texts: Does there exist standardized language-agnostic data structure notation?

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


texts:
Let the problem of the diophantic equation 0/1 be as follows.

Input : A polynomial equation on n variables whose coefficients are integers (ex : $2x^3_1 x_2 + x_1x^3_3 - 3x_4 = 8$)

Question: Does this equation have a solution in space {0,1}$^n$ ? (can we satisfy the equation by choosing for each variable the value 0 or 1?)

1 - How to prove that this diophantine equation 0/1 is NP-complete?

2 - How to prove that this diophantine equation 0/1 is Strongly NP-complete (ie its restriction to the case where all the coefficients are bounded by a polynomial of the number of variables is already NP-complete)


texts: Bounded Diameter Spanning Tree problem for directed graphs

texts:
The following undirected version of Bounded Diameter Spanning Tree problem is solvable in Polynomial Time.

Undirected Version: Given an undirected Graph $G = (V, E)$ with each edge weight either 1 or 2; 2 positive integers $B$, and $D<=3$.

Problem Statement: Is there a spanning tree $T$ of $G$ such that the sum of weights of the edges in T does not exceed $B$ and such that $T$ contains no simple path with more than $D$ edges?

Directed Version: Now lets consider a same problem for a Directed Graph. With much more simpler constraints: Let each edge have the same weight 1, let $B=\infty$ (thus irrelevant), and let $D<2$.

Problem Statement: Is there a "spanning forest" $T$ of $G$ such that the sum of weights of the edges in T does not exceed $B$ and such that $T$ contains no simple path with more than $D$ edges?

I am struggling with how to approach the problem for the Directed version (though it has much less constraints than the undirected version). Can anyone please provide some inputs on the approach?


texts: Calculate the amount of formal languages

texts:
Statement:

  There are 256 formal languages $L$ with $L \subseteq \{w \in \{a,b\}^*
 \ \vert \ \ \vert w \vert = 3   \}$

Answer:

  True.

My question is why there are 256 formal languages. If I calculate the possible combinations with length 3 I get 6 combinations:

$M =\{aaa, aab, abb, bbb, bba, baa\}$

Calculalting the power set results in: $2^M = 2^6 = 64$

Where did I go wrong the get $64$ as result?


texts: String of minimum length in $\{a, b\}^*$ not in a regular expression

texts:
I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression.

a. $b^*(ab)^*a^*$

My answer: $aab$

b. $(a^* + b^*)(a^* + b^*)(a^* + b^*)$

My answer: $abab$

c. $a^*(baa^*)^*b^*$

My answer: $bba$

d. $b^*(a + ba)^*b^*$

My answer: $abba$

I came up with my answers by trial and error. I don't know for sure if these are the shortest possible strings. Is the best method trial and error, or would there be some better algorithmic way?


texts: Which kind of interrupt has the highest priority on 8086 processors?

texts:
Which of the following interrupts has the highest priority in 8086 micro-processor:

Overflow,
NMI or
Type 255?

The book I read suggests that type 255 has highest priority.
But most of the searches on google showed that it is NMI. Which is true?


texts: Time complexity of writing a number as power of 2's

texts:
I'm wondering about the time complexity of writing a number as power of 2's. For example writing $n=218$ as $2 + 2^3 + 2^4 + 2^6 + 2^7$.
It seems to me that we do $\lceil \log_2n \rceil $ divisions. Each division costs $O(n^2)$ so an upper bound is $O(n^2 \cdot \log_2n)$. However, this seems like a very loose upper bound to me as the number we start with gets smaller with each division. So, what would be a better upper bound on the time complexity of writing an integer $n$ as power of 2's ?


texts:
The class $FPT$ (fixed-parameter tractable) is defined here. However, there is only one "parameter" that is studied from the given problem/language.

Is there an equivalently defined class that can take $O(1)$ parameters? It may be useful for defining this for problems that are not driven by a single parameter. Unfortunately, there does not seem to be any material on extra parameters, including in the book Parameterized Complexity Theory.


texts: CPU scheduling Algorithm SJF VS SRTF average waiting time?

texts:
Let's say we have two CPU scheduling algorithm as SJF and SRTF and we have a arbitrary pool/set of processes with  different ARRIVAL TIME and CPU BURST, then what CPU scheduling algorithm will result in minimum average waiting time?

Note : We know, with processes having same arrival time will make SRTF to SJF and SJF guarantees minimum average waiting time, but here arrival time of processes is not same.

Moreover please consider this screenshot from Galvin - in this screenshot below the avg waiting time of SRTF is less than SJF, but my doubt is, is this valid for only this set of values or when arrival times are different than SRTF will ALWAYS have the less average waiting time over SJF?


texts: What is the intuition behind a λ-term being EAL-Typeable?

texts:
λ-terms can be split in two categories: EAL and non-EAL typeable terms. It is known not only that EAL-typeable terms can be reduced to normal form in polynomial time, but that the reduction can be executed through Lamping's abstract algorithm optimally.

What are the distinct features that make a term EAL-typeable? I've heard words such as "stratifiable", but I'm not sure what that mean. What is the intuitive reasoning behind a term being in EAL?


texts: Is Green's the best 16-input sorting network so far?

texts:
Every paper says that Green's construction is the best 16-input sorting
network as for now.

But why does Wikipedia says: "Size, lower bound: 53"?

I thought "lower bound" meant:"If there exists at least an algorithm that can...". Am I wrong?


texts: predication execution, branch prediction

texts:
Below is a paragraph from a book.

  In an ordinary superscalar processor, we would use branch prediction to guess which of the given instructions is to be executed, and go down that path. If the processor guesses wrong, the pipeline must be flushed.

  Predication execute all of instructions and once the values of the predicate registers are known, commit only the results of the valid instructions. Thus we make use of additional parallel execution units to avoid the delays due to pipeline flushing.

So each predication and branch prediction has disadvantage each.
For predication, we have to WAIT until the values of the predicate registers are known.
For branch prediction, if prediction is wrong, the pipeline must be flushed which will cause a DELAY.
Seems like both predication and branch prediction needs delay..
But to me.. prediction has a chance to avoid delays when prediction is correct leading to conclusion that prediction is better..Predication always needs waiting.

So how do I tell which one is better??
Under what circumstance should I use predication and branch prediction?

Thank you in advance.


texts: MinHeap represented by an array - two simple statements

texts:
I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line.

These are the following statements:

Preface : Let A[n] be an array of min-heap (a min-heap represented by an array], whereas all the elements in the heap are different from each other.
Let i and j be two indexes in the range : $0 \le i, j \le n-1$.

Prove or disprove :

If $i < j $ then $A[i] < A[j]$
If $A[i] < A[j] $ then $i < j$

I believe I managed to disprove both of them using the following heap:

$\qquad [2, 6, 7, 11, 14, 13, 12, 12, 13,15, 16, 71, 72, 13, 81]$

For:

Simply plug in the following indexes: $i = 4$ and $j = 13$.

So $i < j$ but $A[i] > A[j]$.
Simply plug in the following indexes: $i = 13$ and $j = 4$.

So $A[i] < A[j]$ but $i > j$.

Am I missing something here? Or It is really that easy?


texts: How to Optimise the following algorithm? maximum good value of an element in an array

texts:
I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an array element $A_i$ is defined as the total no. of Valid indices $<$ such that $_$ is divisible by $_$. My approach is as follows,

    int maximum=-1;
    for(int i=n-1;i>=0;i--){
        int count=0;
        for(int j=0;j<i;j++){
            if(arr[j]%arr[i]==0)
            count++;
        }
        maximum=max(count,maximum);
     }
     print(maximum);


texts:
I've searched this and was not able to understand the answer.

What's the idea/intuition behind this? What's the purpose and why is it important?

And considering the wikipedia explaination, specifically this part:

  outputs the binary (or unary) representation of f(n), while using only O(f(n)) space

Why does it matter that the binary representation doesn't exceed O(f(n)) space?

And what does it mean to not exceed that space? Why is the function f(n) = c not space constructible?

Sorry if this has been asked before but I didn't find it.


texts: How to analyze the lower bound of the horse racing problem using adversary argument?

texts:
Consider the following problem:

  Give an algorithm to find the $1^{st}, 2^{nd}, 3^{th}$ fastest horses from 25 horses. In each round, at most 5 horses can race and you can get the exact position of these horses. Analyze the lower bound of this problem using adversary argument. One race is considered as one critical operation.

I can figure out a solution using 7 races:

  Divide 25 horses into 5 groups with 5 horses for each: $A: a_1, a_2, a_3, a_4, a_5$; $B: b_1, b_2, b_3, b_4, b_5$; $C: c_1, c_2, c_3, c_4, c_5$; $D: d_1, d_2, d_3, d_4, d_5$; and $E: e_1, e_2, e_3, e_4, e_5$.
  One race within each group. Suppose that the position of each horse in each group is consistent with its index: e.g., $A: a_1 > a_2 > a_3 > a_4 > a_5$.
  One race for $a_1, b_1, c_1, d_1, e_1$ and get $a_1 > b_1 > c_1 > d_1 > e_1$. Thus, $a_1$ is the fastest horse.
  The second and third ones are among $a_2, a_3, b_1, b_2, c_1$. So one more race is enough.

However I have difficulty in analyzing its lower bound using adversary argument.
So my problem is:

  How to analyze its lower bound using adversary argument? What is the adversary strategy?


texts:
Given an undirected graph $G=(V,E)$ a Gomory-Hu tree $T$ for $G$ has the following properties:

$T$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut separating the corresponding pair of vertices of G.
$T$ has the property that the minimum cut between vertices $s$ and $t$ in $G$ is the cut corresponding to the minimum weight edge along the path from $s$ to $t$ in the Gomory-Hu tree.

In $[1]$, the author states the following lemma:

Let $S$ be the union of cuts in $G$ associated with $n$ edges of $T$. Then removal of $S$
from $G$ leaves a graph with at least $n+1$ components.

Consider a complete graph $K_4$ with all the edges having weight $1$.
A (possible) Gomory-Hu Tree $T$ for $K_4$ is the following:

If we remove the cuts associated with all the $n=3$ edges of $T$ we might proceed as follows:

$(3,0) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$
$(3,1) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$
$(3,2) \in T$ $\rightarrow$ remove $\{(3,0),(3,1),(3,2)\} \in G$

A potential result (among the different ones) is a graph with $2 \neq (n+1=4)$ connected components, i.e., $\{3\}$ and $\{1,2,4\}$.
So, my question is, am I missing something in the definition or properties of the Gomory-Hu trees?
Does the author mean that for each $(u,v)$ in $T$, all the minimum weight cuts between $u$ and $v$ in $G$ should be removed in order for the lemma to hold?

[1] Vazirani, Vijay V. Approximation algorithms. Springer Science & Business Media, 2013


texts:
I'm really struggling with the following exercise and I would really appreciate your help:
I have to calculate the expected runtime of a sort Algorithm with the following variants:

Variant   Runtime Behavior
1            n(n-1)
2              n
3            n log(n)

Given is, that the runtime for variant 1 is 1000 elements(n) is 20ms.
With the calculation for the other elements from variant 1, I have no problem because it's O(n^2) but I really don't know how to calculate the values for variant 2 & 3.

Variant    Length n    expected runtime in ms
   1        500          20ms * 0.5^2 = 5ms
   1        4'000        20ms * 4^2   = 320ms
   2        2'000'000    ?
   3        4'096        ?

Thanks for your help in advance

Kind Regards


texts: How does one change the probability bounds in probabilistic complexity classes without changing the class?

texts:
I see this theorem whose proof is not clear to me :

"Let $L \subseteq \{0,1\}^*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \{0,1\}^*$ and $Pr[ M(x) = L(x) ] \geq 1/2 + \vert x \vert ^{-c}$ Then for every constant $d >0$ there exists a polynomial-time PTM M' such that for every $x \in \{0,1\}^*$, $Pr[M(x)=L(x)] \geq 1 - 2^{-\vert x \vert ^d}$"

Even if I assume this above theorem how does this help convert the $2/3$ probability guarantee in the definition of BPP , RP and coRP into $1-2^{-\vert x \vert ^d }$ without changing the class?
I understand that the above theorem is proven by doing a $8\vert x \vert ^{2c +d}$ iterations of the PTM's run and then taking the majority vote and somehow Chernoff bound helps get the exact numbers. But I can't understand the intermediate argument. It would be helpful if someone can help fill in!


texts: Where does the need for conditionals (if, switch, jump tables, etc...) truly arise?

texts:
I know that this question is a bit out-of-the-box, yet i would be glad if someone could help with a good answers for my question because it is something that is troubling my curious mind.

When we program we have no doubt that we need conditionals, like the if statement. I will use the "if" statement as a reference throughout the topic.

I mean, if we have a program like

int main(int argc, char** argv)
{
int n = atoi(*argv);
if(n%2==0)
  printf("even");
else
  printf("odd");
}

Given these conditions, where we can only use what comes after the input is passed to the program to perform our computation, i cannot deny that i need an if statement to distinguish between an even and an odd number. This is just an exemple.

But then i wonder, what if we could mess with what comes before the argument passing occurs?

Let's assume that this program is called oddEven.exe. When the user executes the program by writing oddEven(3) for instance, on the command line, the keyboard sends a signal to the computer with the number 3, which is simply written to memory. No analysis is done on the input, it is simply dumped into memory.

Given this situation, once we run the program, we know only what a number (actually a sequence of characters) was written, but not which one was written. Now let's assume that the hardware itself would be responsible for calling the appropriate branch of the program once the number is written, as if two diferente programs were written.

int mainEven()
{
//code for even numbers;
printf("even");
}

int mainOdd()
{
//code for odd numbers;
printf("odd");
}

The hardware would then be responsible for decoding the signal sent by the keyboard and, treating it as a number, check whether it is odd or even. We could at this point argue that such a machine would make it possible to program without ifs. Yet, haven't we just implemented the if statements at the hardware level? Hence we couldn't get rid of conditionals.

Now, what if the computer was actually made out of several subcomputers, each implementing a diferent branch of the program. We can also see this as if we had 2 computers. Consider that once a button is pushed, computer C1 prints "even" whereas computer C2 prints "odd".

The user would then be responsible for choosing which computer to use based on the output he knows is right for the number he has in mind. At this point, neither the hardware nor the software contain conditionals. Is the problem solved? No! The conditionals are now "running" on the user's brain, who has to decide which computer to use.

My point is, where do conditionals come from? Where do they stop? Can we avoid them somehow? Can you prove me we need them? If we do, why do we put them at the hardware level? Why does the input of a program have to be compared against values to determine the branch to execute?

I am a computer scientist myself, but i feel like i have lost my path once i thought about this subject. I'm having trouble proving that i undeniably need conditionals to perform computation.

I'd be glad for some insightful answers! Thanks in advance


texts: Non-optimal program, bad choice of language or Low-speed system?

texts:
To check some results of an article, I wrote the proposed algorithm from the Coding articles. In the article, some results from the algorithm were obtained. Unfortunately, the performance of my program was very different from what was said in the article.

In the article, results were obtained in 20min but I got quarter of them in 5h. Plus, in article algorithm was written in Matlab and I wrote in Python. In addition, the author mentioned that their system is a desktop computer with 2.4-GHz CPU and 8-GB RAM, but mine is a laptop with 2.13 GHz CPU and 2-GB RAM (Pentium(R)).

Now, which one do you think is the real problem for slow-performance of my program?

1-The non-optimal program that I wrote?

2-Bad choice of language (Python vs. Matlab)?

3-Low-speed system compare to the system of the author?


texts: Binary to ASCII using logical operations

texts:
I am learning Computer Architecture from Introduction to Computing Systems (2nd Edition) and am stuck on this question.

What operations can be used to convert the binary representation of 3 into ASCII representation for 3? What about binary 4 to ASCII or any other digit?

The concepts I have learnt until now are Basic Logic gates and Bit Masking so I have to use them for conversion. Can someone help me understand what my approach should be?


texts: Count the number of integers satisfying two conditions using DP

texts:
Given two integers $n$ and $m$, how many numbers exist such that all integers have all digits from $0$ to $n-1$, the difference between two adjacent digits is exactly $1$, and the number of digits in the integer is at most $m$?

The integer cannot start with a $0$. All digits from $0$ to $n-1$ must be present.

Example: for $n = 3$ and $m = 6$ there are $18$ such numbers ($210, 2101, 21012, 210121 \ldots$)

I know there is a dynamic programming method to solve this. After looking the solution, I am not able to understand it. Can anybody please give any good solution to me?


texts: What is the closest result relating perfect shuffle closure of primitive words?

texts:
A perfect shuffle of two words $u=a_{1}a_{2} \cdots a_{n}$ and $v=b_{1}b_{2} \cdots b_{n}$ where $a_{i}$'s and $b_{j}$'s are letters from the alphabet $\Sigma$ is defined as $u \diamond v=a_{1}b_{1} \cdots a_{n} b_{n}$.

It is obvious that if for two primitive words $u$ and $v$, their shuffle $u \diamond v$ need not be primitive. (e.g., for $u=abc$, $v=cab$, $u \diamond v=acbacb$ is not primitive.

So, my question is is there any result that proves that under certain conditions set of all primitive words is closed under this perfect shuffle? (There are results in the literature that talks about square-free shuffle but not primitivity, at least I didn't come across any.)

Please help.


texts: On graph isomorphism for weighted graphs

texts:
Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.

Basically take an real edge weight set $\{w_1,\dots,w_s\}$

All weights on the graph edges are from this set.


texts: What constant in the latest fast matrix multiplication is hidden by Big-O notation?

texts:
I'm evaluating the theoretical run time of matrix multiplication algorithms as it has improved within the last few decades. Algorithms to solve matrix multiplication run in O(n^w) time, where w has evolved in the following way:

w = 3 if using a brute-force approach,
w = 2.8074 if using Volker Strassen's algorithm [1969],
... (some interesting improvements later :))
w = 2.3729 if using Virginia Vassilevska-Williams analysis of the Coppersmith–Winograd algorithm [2011]
w = 2.3728639 if using François Le Gall's adaptation of the  Coppersmith–Winograd algorithm [2014]

I often hear that the more recent algorithms presented, while theoretically interesting since w approaches 2, are not practical due to the large constant hidden by Big-O. In other words, that the size of the input matrix would need to be extremely large in order for it to be an improvement over Strassen's algorithm, for example. I would like to put a number to this.

What is the rough value of this hidden constant for any of the more recent fast matrix multiplication algorithms? Or, for roughly what input size n of a matrix would the fast matrix multiplication algorithm use less operations than Strassen's algorithm, or the brute force approach?


texts:
Is there a name for graphs which contain oriented and non-oriented edges?

I couldn't find on the internet if there exist a specific name for such graphs.


texts: How to extract a set $C$ that contains $N$ subsets of a set $B$, covers all elements of an external set $A$, but $N$ is minimal?

texts:
Let $A$ denote a set that contains a relatively large number of different strings. Let $S_i$ denote these strings.

Let $B$ denote a set of sets such that each subset contains a (relatively small, usually not greater than 100) number of different strings. Let $B_i$ denote these subsets.

The problem is the following: is it possible to have an efficient way to obtain a set $C$ that contains a minimal number of different subsets of $B$, but for each $n$, a subset of $B$ that contains a string $S_n$ will be present as a subset of $C$?

Example:

A = ["a", "b", "cd", "e", "eeff", "x", "y", "xyz"];
B = [
["aa", "dce", "n", "e", "f", "y"],
["aa", "b", "n", "e", "f", "y"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["b", "t", "a", "h22", "z"],
["i", "cd", "le8", "a", "t", "eeff", "f"],
["aaa0", "x", "b", "a", "t1", "s"],
["xyz", "a", "n"],
["b", "xyz", "n"],
["eeff", "xyz", "dce", "aa"],
],

We can find multiple possibilities here, e.g. a set with five subsets:

C = [
["aa", "dce", "n", "e", "f", "y"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["b", "t", "a", "h22", "z"],
["aaa0", "x", "b", "a", "t1", "s"],
["eeff", "xyz", "dce", "aa"],
]

(note that for each $x$ such that $0 \le x \le 7$, there is an element of $C$ that contains $A_x$), but the possible solution allows to have only four elements in $C$:

C =
["aa", "b", "n", "e", "f", "y"],
["aaa0", "x", "b", "a", "t1", "s"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["eeff", "xyz", "dce", "aa"]
]

Is it possible to have a relatively efficient method of solving such a problem? I only see a factorial-level complexity (testing each possible combination), which quickly becomes physically impossible to implement. But if $A$ contains millions of elements, and $B$ contains billions of elements, we need another solution...


texts: I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete operation--for example: counting Bloom filters. I heard also about another method, which uses a second filter. If I want to remove an element I have to 'insert' it into this second filter. I can't find how this proposed structure operates, any article about it, or even the name of the originator. Maybe someone can share with me with a link to any interesting articles about this method? I found a lot of articles about counting Bloom filters and other methods, but I can't find any description of this one.


texts:
Given a set with $n$ items, find $x$ subsets, each one of them of size $y$, such that every two subsets share exactly one item.

I've tried to solve it with a reduction to a graph, but I got lost...

Thanks.


texts: Why are weights of Neural Networks initialized with random numbers?

texts:
Why are neural networks initial weights initialized as random numbers?
I had read somewhere that this is done to "break the symmetry" and this makes the neural network learn faster.
How does breaking the symmetry make it learn faster?

Would'nt initializing the weights to 0 be a better idea? That way the weights would be able to find their values (whether positive or negative)  faster?

Is there some other underlying philosophy behind randomizing the weights apart from hoping that they would be near their optimum values when initialized?


texts:
Can somebody explain the following:

U is a universe of keys, and H is a finite collection of hash functions mapping U to {0, 1, … , m-1}.

I do not understand definition 2, and thus why amount of funtions that map x and y to the same location is given by |H|/m.


texts:
I think I understand pumping lemma for regular and context free languages, but there is this one, which I have no idea if it is regular or context free or not context free.

$L = \{vwwx : v,w,x \in \{0,1\}^* \wedge w\neq \epsilon\}$ - I think it may be regular, because I think that this is language, which accepts set of all words with $00,11,0101,1010$ substrings. I am sure that $\{vww^Rx : v,ww,x \in \{0,1\}^* \wedge w\neq \epsilon\}$ is regular here is proof, because it is set of all strings, with $00$ or $11$ as substring, but without reversing $w$ I am not so sure. I do not understand if idea of "expanding" $v$ and $x$ in $vww^Rx$ as shown in proof (reducing language to language which accepts set of all string with $00$ or $11$ as substring) also applies to $vwwx$. What do you think ?

I would be glad if you could help me with this one.


texts: Shortest paths from a source in weighted graph with only one negative weighted edge

texts:
Of course assuming there aren't any negative cycles.
I saw this question somewhere. And i saw a complicated solution which says to build three such graphs and connect between them in a very  complicated manner.
My question is why isn't my simple solution good for it?
My simple solution is to first find the negative edge . And then start traversing from that edge with dijkstra.
 I think once you start with that edge, dijextra should work.
So that way i mange it in O(e + vlogV) . So why isn't my easy solution mentioned there. Is my solution correct?