texts: Relative pose estimation using epipolar geometry: Wrong translation estimate

texts:
I am trying to use epipolar geometry concepts to estimate the relative pose of cameras between two images. I am currently using a simulator to get my camera images, so the distortion is zero and I know the camera parameters beforehand. I am using OpenCV (through the findEssentialMat, recoverPose, solvePnP functions) for my programming. My pipeline is: Detect features, match, find relative pose, triangulate, scale the point cloud using an initial scale estimate and run PNP on subsequent images (as the cameras move) to get metric poses.

When two images are taken from positions displaced only along the X axis, essential matrix based estimation works perfectly, I get a translation matrix like [-0.9999, 0.0001, 0.0001]. But when the camera is moved along the forward/backward Z axis, I see the t matrix contains a higher than usual value on the Y axis, whereas X and Z are correct. And in the same fashion, if I move purely in X and Y, the translation estimate shows erroneous 'extra' movement on the Z axis. Example results from solvePnP for these two cases are: (units in m)

Image 1 taken from (0, 0, 0) , image 2 from (-2, 0, 0):
t = [-1.988, 0.023, 0.046] (Y and Z are acceptably close to 0)
Image 1 taken from (0, 0, 0) , image 2 from (-2, 0, 4):
t = [-2.028, -0.441, 4.0983] (Y is totally off)

I don't understand where the 0.4m on the Y axis is coming from. The simulator is very accurate in terms of physics and there's absolutely no movement of that magnitude on the Y axis. The same behavior is reflected in the relative R/t output from the essential matrix decomposition.

On the other hand, if I generate a perfect set of 3D points, take them through the projective transformations using the intrinsics and R|t matrices, compute the 2D points, and then compute the essential matrix, I get the expected R and t.

I was reading through David Nister's paper about the 5 point algorithm which I'm using, and it says this:

"The 5-point method significantly outperforms the other non-iterative methods for sideways motion. The 5-point results are quite good, while the results of the other non-iterative methods are virtually useless. As the noise grows large, the other methods are swamped and begin placing the epipole somewhere inside the image regardless of its true position. This phenomenon has been observed previously by e.g. [15]. It is particularly marked for the 6 and 8 point methods. For the forward motion cases, the results are quite different however. This is partly due to a slight deterioration of the results for the 5-point method, but mainly due to a vast improvement of the results for the other methods. In particular the 8-point method gives excellent results on forward motion".

I wonder if the optimal solution is some kind of a 'best of both worlds' scenario? Has anyone worked on similar problems before, who can share some wisdom?


texts:
Firstly, I would like to apologize if I misplaced this topic / i think the theory of coding is close to CS /

I am little bit confused right now, in the school we were learning about Hamming's code, Block codes etc.

I was given a homework, in which I should explain how does the two dimensional parity check finds 3-bit errors. I think the two-dimensional parity check does finds 3-bit erros, but it can't (in every case) correct it.

The second thing is, we were learning about hamming distance and there is a rule, which says that block code finds t-bit error when this equation is right:

t < d (and d stands for hamming distance, its minimum distance between the 2 code words / t stands for t-bit errors).

So for example: a = 110, b = 101, c = 100

1 1 0 | 0
1 0 1 | 0
1 0 0 | 1
_ _ __
1 1 1   1

The numbers behind the 'bars/underscores' are the parity-check bits, it means that in each column/row is even count of number 1.

So the minimum distance equals to 2. That means according to the rule t < d, that this code can detect only a t-bit error, which means 1 ( but that's not true, because it can detect 3 bit erros).

How should I explain that?.

Thanks.


texts: Equivalence rules for LTL - Getting stuck working with $ \square \lozenge $ & Until ($\textsf{ U}$ ) operators

texts:
Need to prove equivalence for (or disprove equivalence for):

$
\hspace{1cm}\square ϕ → \lozenge ψ ≡ ϕ\textsf{ U }(ψ ∨ ¬ϕ) \\
$

My current attempt using the LTL equivalnce rules to determine equivalence:

$
\square ϕ → \lozenge ψ \\
≡\
¬\square ϕ \lor \lozenge ψ \hspace{1cm}(\textsf{"Mutual implication"} ϕ →ψ≡¬ϕ\lor ψ )\\
≡
\lozenge ¬ϕ \lor \lozenge ψ \hspace{1cm}(\textsf{"Duality"} ¬\square≡\lozenge ¬ )\\
≡
\lozenge (¬ϕ \lor ψ) \hspace{1cm}(\textsf{"Distributive law on"}\lozenge )\\
≡true \textsf{ U} (¬ϕ \lor ψ) \hspace{1cm}(\textsf{"Def of"}\lozenge )\\
≡true \textsf{ U} (ψ \lor ¬ϕ) \hspace{1cm}(\textsf{"Symmetry"}\lor)\\
$

After this I got stuck. I am not sure how to proceed from here to get the right side. Are other propositional logic rules allowed to be used in LTL, like for example identity disjunction?


texts:
Given boruvka's algorithm:

MST T <- empty tree
Begin with each vertex v as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

In each phase I'd like to reduce the graph's size, by saying that after each phase - there is actually no need to remember edges that are within each component (because some were inserted to the MST T already and others are not needed). So instead of each component I'd like to put only a single vertex. The only problem comes when I try to construct my edges - an edge between two new vertices (which were two components before) is the one with the smallest weight among all the edges between a vertex in the first component and a vertex in the second. I wanted to implement this in linear time, but I don't see how I can reduce the edges as well, all in linear time?


texts: Infinite Intersection/Union of regular languages

texts:
Hello I'm having trouble understanding how an intersection/union of regular languages can be regular and in other case non-regular.

Can someone please give me some good examples?


texts: Research work on computational models for a "specific" person's behaviors

texts:
Is there active research work on creating computational models of a "specific" person's behaviors (general behaviors, emotions, actions...)? What are some references for such research? I tried google and scopus and did not have much luck.

I have worked on modeling movement behaviors of pedestrians in crowd (for my PhD work), but I am planning to work on the simulation of general behaviors of individuals (based on the historical data of their actions and behaviors).

I am more inclined to use machine learning methods than detailed mathematical models.


texts:
I was solving this question. It is as follows

  Joe picks an integer from the list $1,2,\cdots,N$ with a probability $p_i$ of picking $i$ for all $1\leq i \leq N$. He then gives Jason $K$ attempts to guess his number. On each guess, Joe will tell Jason if his number is higher or lower than Jason's guess. If Jason guesses Joe's number correctly on any of the $K$ guesses, the game terminates and Jason wins. Jason loses otherwise. If Jason knows all $p_i's$ and plays optimally, what is the probability he wins?
  $1\leq N\leq 200000$
  $1\leq K\leq 20$

I tried this problem by dynamic programming. Let $DP[i][j][k]$ stores the winning probability such that the number is between $i$ and $j$ inclusive and only $k$ chances are left. So
$$DP[i][j][k] = \max_{i\leq l\leq j} \{p_l + DP[i][l-1][k-1] + DP[l+1][j][k-1]\}\\DP[i][j][1] = \max_{i\leq l\leq j}p_l\ \quad \quad \text{Base Case}$$
But since the range of $N$ is very high this solution is not feasible. So while I was seeking an $\mathcal{O}(n)$ solution I came across the following solution(on the internet which got accepted)

Sort($p[]$)
$\sum_{i=0}^{\min(n,2^k-1)}p_i$

If we run both the solution on input $N=5,K=2, p=[0.2, 0.3, 0.4, 0.1, 0.0]$ we get the same answer. So, my question is how is the above algorithm working and can we get to the same conclusion starting form my dp formulation{if it is correct}.


texts: Proving ALLTM complement not recognizable

texts:
A few definitions..

$$
\begin{align*}
\mathrm{ALL}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle  \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) = \{0,1\}^{*} \Bigr\}
\\[2ex]
\overline{\mathrm{ALL}}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle  \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) \ne \{0,1\}^{*} \Bigr\}
\\[2ex]
B_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ is a Turing Machine over $\{0,1\}^{*}$},\;\; \varepsilon \in L(M) \Bigr\}
\end{align*}
$$

We are showing a reduction from $B_{\mathrm{TM}}$ to $\overline{\mathrm{ALL}}_{\mathrm{TM}}$. In my notes I have the following solution to this problem which I'm trying to understand.

Let $\alpha \in \{0,1\}^*$. Check that $\alpha$ is of form $\langle M \rangle$, where $M$ is a TM over $\{0,1\}$. Else, let $f(\alpha)$ be anything not in $\overline{\mathrm{ALL}}_{\mathrm{TM}}$.
Let $f(\alpha)$ be $\langle M' \rangle$, where $M'$ on $x$ runs $M$ on $\varepsilon$ (blank string) for up to $|x|$ steps. If $M$ accepts (in that time), then $M'$ rejects. Otherwise, $M'$ accepts.

What I'm trying to understand is why must we run the TM $M'$ for $|x|$ steps for this to work? If we change the part #2 of the transformation to the following, why wouldn't this work?

Let $f(\alpha)$ be $\langle M' \rangle$, where $M'$ on $x$ runs $M$ on $\varepsilon$ (blank string). If $M$ accepts, reject. Otherwise accept.

Which then it follows that $\varepsilon \in L(M) \!\iff\! L(M) = \varnothing$,  that is $L(M) \neq \{0,1\}^*$.


texts: If $m \leq a \log m + b$, why does $m = O(\max\{a \log a, b\})$?

texts: I'm found this claim in something I was reading and I'm having trouble working out the logic. Can someone help me out?


texts:
I have difficulty / doubt in transforming a grammar into LL (1), I tried remove left recursion but grammar still not LL(1).
S → SAB | abA | baC
A → aSb | d
B → bSaC| c
C → cCd | b

Without left recursion
S - > abAS' | baCS'
S ' ABS'| ε
A → aSb | d
B → bSaC| c
C → cCd | b

After removing the left recursion I have a FIRST / FOLLOW SET CONFLICTS on production (S' -> ε)
but if I remove the epsilon production I go into a "loop". What am I doing wrong?


texts: Algorithm to find all acyclic orientations of a graph

texts:
I am working on acyclic orientations of undirected graphs and have the following questions:

Given connected undirected simple graph $G$, how to find all possible acyclic orientations of $G$ ?
What is the number of acyclic orientations?
It is known (from here) to be $(-1)^p\ \chi(G,-\lambda)$ for a graph $G$ with $p$ vertices where $\chi$ is the chromatic polynomial evaluated at $-\lambda$; but I wasn't successful in understanding how to evaluate $\chi$ at a negative value ($-\lambda$).


texts: Given the logical address, how to extract the page number?

texts:
I am studying Computer Systems. I have th following question and its answer:

  Given the logical address 0xAEF9 (in hexadecimal) with a page size of
  256 bytes, what is the page number?

  Answer: 0xAE (I found this answer in the web, but I want to know how can I
  figure it out myself?

How can I figure out the page number for a given logical address?


texts: Is $\Gamma \vdash x x : T$ possible in the simply typed lambda calculus?

texts:
Is $\Gamma \vdash x x : T$ possible?

This problem appears on page 104 of Benjamin Pierce's "Types and Programming Languages".

My conclusion is that it is was the case then we would get $x: T_1 \to T_2$ and $x:  T_1$ and by some axiom, these types are not equal.

The problem is identifying this axiom but I fear it might be possible to have this equality...

Any hints?


texts: What is Temperature in LSTM (and neural networks generally)?

texts: One of the hyperparameters for LSTM networks is temperature. What is it?


texts: What are these questions in the PoplMark challenge asking?

texts:
I was reading the paper Mechanized Metatheory for the Masses: the PoplMark Challenge by Aydemir et al (PDF) and I found the following three questions on page 13 of the PDF a bit confusing.

  Challenge 3: Testing and Animating with respect to semantics.

  Given $\mathrm{F}_{\texttt{<:}}$ terms $t$ and $t'$, decide whether $t\rightarrow t'$.
  Given $\mathrm{F}_{\texttt{<:}}$ terms $t$ and $t'$, decide whether $t \rightarrow^* t' \not\rightarrow$, where $\rightarrow^*$ is the reflexive-transitive closure of $\rightarrow$.
  Given an $\mathrm{F}_{\texttt{<:}}$ term $t$, find a term $t'$ such that $t\rightarrow t'$.

I think question (3) is saying reduce a term $t$ to $t'$ until which is no longer can be reduced (or become a value). What about question (1), are they just saying check the result if it is equal to some term $t'$? and question (2).

Could someone explain me their differences?


texts:
I am working on the following exercise:

Consider a simple and connected undirected graph $G(V,E)$. Show that one can colour the edges of $G$ in polynomial time and with as few colours as possible such that there is no monochromatic cycle in said colouring of $G$.

EDIT 1: OK, my approach turned out to be false. I will leave it here for the sake of completeness. Now I have no idea how to solve this exercise. I guess the following theorem might be helpful:

Theorem: For any undirected simple graph $G(V,E)$ we can decide whether the edge chromatic number is less than $3$ and if yes we can find this optimal colouring in polynomial time.

EDIT 2: I have reread my lecture notes. This exercise is probably meant to be solved with tools from matroid theory. I just do not see how.

My WRONG approach:
I think that 2 colours should be sufficient. (Remember that this is not the classical edge colouring problem, we just want to avoid monochromatic cycles.) My first idea is to formulate a simple greedy algorithm:

Colour all edges in red.
Check the graph for cycles. If there is a cycle delete one edge of the cycle from the graph. Repeat this step until there are no more cycles in $G$.
Colour the deleted edges in blue.

However, the problem with this approach is that the blue edges may form a cylce as the example below shows. While the example below can easily be fixed by recolouring two edges I am not sure if this fix works in general. Could you please give me a hint?


texts: Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

texts:
How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.

$A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the reversed form of $x$.

I understand that since $L$ is regular so does $L^R$.also on my way for a CFG I can reach $w_1$ by the CFG of $L$ concatenation with the one of $L^R$ for making $w_2$. so far I have a CFG, but what promises me that $|w_1|=|w_2|$? how can I generate a grammar that will also keep that in addition to the other conditions?


texts: Sequence to explore the complexity of the NP problem

texts:
Let $X$ be some problem known to be in $NP$. What is the natural next step in exploring the complexity of the problem? Is it trying to prove whether it is in $P$ or try to prove it is $NP$-Hard? Taking the example of the Graph-isomorphism problem it seems to me that after discovering that problem is in $NP$. It is not easy to decide what to do next. Some people suggest me to prove it into $NP \cap CoNP$.

Question : What is worth to try if it is only known that problem is in $NP$? Is there any sequence (like first $NP$, $NP$-Hard, ....) to explore the complexity of the problem?


texts: I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 \log n)$. In our lecture we said that the runtime is $O(n \log n)$ assuming that every comparison is $O(1)$. I think that I have to work with comparison-complexity but I dont know how to create a runtime of $O(n^2 \log n)$ since mergesort has best and worst-case complexity of $O(n \log n)$. Could anybody help me out creating a problem to achieve a runtime of $O(n^2 \log n)$ ?


texts:
Let $\Sigma = \left\{ 0,\,1,\,2\right\}$. I want to look at the following language: $L=\left\{ xyz \, | \,  |x|_0 + |z|_0 = |x|_2 +|z|_2 \wedge y \in \left\{ 1 \right\} ^{*} \right\}$.

I would like to prove or disprove $L$ being context-free

I'm having a very hard time to construct a context-free grammer for $L$, so I attempted to build a non-deterministic PDA.

My attempt goes in the direction of: If i want to sum the zeroes from $x$ and $z$, and fron this sum to substract the  sum of $2$s from both $x$ and $z$, I can do it differently:

I can count the number of $0$s from $x$ by inserting a #, then remove one # for every $2$ I count, if negative I'll push @ . Then I will do the same with $z$.

The points are:

I'm not sure if this idea will work?
If this language is CFL, I have no idea how to begin constructing a CFL grammer for it?


texts:
It's clear that Mathematica uses the Baillie–PSW test for its PrimeQ function (which tests primality), and as I read in the Mathematica documentation, it starts with trial division, then base 2 and 3 Miller–Rabin, and then Lucas pseudoprime test. My question is:

  Can we remove base 2 and 3 and use only a random base?

Also, can any one suggest a good reference about this primality test other than Wikipedia?


texts: What is an efficient way to calculate the biggest system of disjunct sets?

texts:
Let $I$ be a finite set of items and $\mathcal{M} = \{M | M \subseteq I\}$ be a set of subsets of $I$.

The task is to find the biggest subset $\tilde{\mathcal{M}} \subseteq \mathcal{M}$ so that all elements of $\tilde{\mathcal{M}}$ are pairwise disjoint:

$$\text{arg } \max_{\tilde{\mathcal{M}} \subseteq \mathcal{M}} |\tilde{\mathcal{M}}| \text{ with } \bigcap_{M \in \tilde{\mathcal{M}}} M = \emptyset$$

What is an efficient algorithm to do so?

(If $|I| \approx 10\,000$ and $|\mathcal{M}| \approx 100$ )

Example

Let $I = \{a, b, c, d, e\}$ be the set of items and

$$\mathcal{M} = \{A, B, C, D\}$$

with

$$
\begin{align}
A &= \{a\}\\
B &= \{b, c\}\\
C &= \{a, c\}\\
D &= \{b, d\}
\end{align}
$$

Then $$\tilde{\mathcal{M}} = \{A, B\}$$
is one of the solutions. There is no way to have $|\tilde{\mathcal{M}}| \geq 3$.

Ideas

Brute force

M_tilde_max = None
for Mc_tilde in powerset(Mc):
    if Mc_tilde is disjunct and (M_tilde_max is None or M_tilde_max < |Mc_tilde|):
        M_tilde_max = Mc_tilde

This has complexity $\mathcal{O}(2^{|\mathcal{M}|})$.

Apriori

If a set $\tilde{\mathcal{M}}$ has only disjunct items, then all possible subsets have to be disjunct. So one can at first find all sets of size 1 which have this property (which are simply all sets), then all sets of size two, then all of size 3, ...

This has the same worst-case time complexity as brute force as in the worst case $\tilde{\mathcal{M}}$ is just equal to $\mathcal{M}$. It might in some scenarios - if one knows that it will be smaller - be much better. However, the space complexity is quite bad here.

More

I guess one could pre-compute for all $|\mathcal{M}|^2$ combinations of two sets if they are disjunct or not. After that, the table can be used and $\mathcal{M}$ and $I$ don't have to be touched at all. This is the maximum satisfiability problem. Each set $M_i \in \mathcal{M}$ is a boolean variable $x_i$. If $M_i$ and $M_j$ are disjunct, then $(x_i \lor x_j)$ is added. If not, then either $(x_i \lor \neg x_j)$ or $(\neg x_i \lor x_j)$ can be added (I think it doesn't matter which one?). This way, a conjunctive normal form can be produced. All clauses have only two elements, so I think there might be an efficient algorithm for it?

Context

This question is more a brain-teaser for me. It started with the following problem:

I would like to generate a tree of categories for Wikimedia commons. The problem is that categories in Wikimedia Commons are not disjunct. For example, for https://commons.wikimedia.org/wiki/Category:Rosa there is the category "Roses by location", "Rosa by month", "Roses by photographer" which are not what I want. However, to filter those I think just removing categories with the substring " by " might be enough. I have to check it, though.


texts:
My question is about the paper Three is Better than One Ensembling Math Information Retrieval Systems (a system used for math information retrieval - both for finding answers and formula search)(code on github).
Before the questions, the following figures illustrates:
CompuBERT (taken from Three is Better than One Ensembling Math Information Retrieval Systems).
sentence-BERT (taken from Sentence-BERT Sentence Embeddings using Siamese BERT-Networks).

CompuBERT uses sentence-BERT but the paper Three is Better than One Ensembling Math Information Retrieval Systems does not explain the inferece (question answering) step. (the inference step in sentence-BERT is illustrated at the bottom left on the picture)
How can I make inferece with CompuBERT?
(please explain using the implementation on github)


texts: Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?

texts:
Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why?

I think it's undecidable but can't find any undecidable problem to reduce it to.


texts: Pattern detection by stacking convolutions

texts:
CNN use convolutions to perform many tasks. In some architecture, the first layer(s) are basic filters such as Gabor's. Many CNN work by stacking a number of convolution layers to build detectors which are more and more complex.

Now, it's clear that filters are typically learned and that, at a given depth, usually fully connected layers are used to "match" patterns that are coming out of convolutions with classes/probabilities/logits that are required as network output.

But I am wondering, and I don't know anything on this topic so I am sorry if I don't provide any resource, is it possible (and how) to manually craft convolution layers so that one can detect some specific patterns without needing to train a neural network?

For example, given the task to identify triangles (or even lines) in an image, can we manually assemble a non-machine-learning algorithm that uses stacked convolutions to detect and describe the triangles in the image (e.g. by finding it's corners)?

For example, by synthesizing filters that are known to have a certain property holding for a certain family of patterns and therefore we can infer that the result will be of some kind.


texts: Can every problem that uses recursion be solved using iteration?

texts: We all know iterations and recursions are a powerful thing in programming. But this doubt always troubles me whenever I write an iteration or recursion. Can every recursive problem solved using iteration and vice-versa? We can avoid efficiency for simplicity. Only thing is is it possible for all?


texts: Distribution of random Fourier coefficients

texts:
Let $f : \{0, 1\}^{n} \rightarrow \{-1, 1\}$ be a Boolean function. Let the Fourier coefficients of this function be given by
$$ \hat f(z) = \frac{1}{2^{n}} \sum_{x \in \{0, 1\}^{n}} f(x)(-1)^{x \cdot z}$$
for each $z \in \{0, 1\}^{n}$, where $x \cdot z$ is the bitwise inner product between $x$ and $z$. Let me choose a function uniformly at random from the set of all Boolean functions $$\{f : \{0, 1\}^{n} \rightarrow \{-1, 1\}\}. $$
What is the distribution that each Fourier coefficient $\hat f(z)$ is distributed as?


texts: An online parallel algorithm for finding top K elements

texts:
Suppose we have a function on GPU which calculates elements of array from which we need to select top K elements. The number of elements can be quite big so we can't store them in memory and our algorithm should be online. Another requirement for algorithm is its good parallelization so it could be effectively run on GPU.

Is there any classic approach for the problem? I've thought only of building heap/balanced tree with $k$ elements and inserting new elements into it if new elements is better than existing and popping smaller element. It gives O($n$ log$k$) but it fails with parallelisation because requires synchronization between GPU threads on modifying tree.


texts: How to prevent the change of other objects in Z specification?

texts:
I have Z specification of Banking system, whose fragments are:

and

I think that the specification is OK, but my professor says that this specifiction is completely wrong, because AddAccount operation allows to change the information about other clients (i.e. the information about accounts of other clients) and information about bank's customers generally (e.g. he says that operation allows add or delete other customers to the Bank). I can not see this permission and what I need to correct. Maybe some advice is available?


texts: How do I find if a programming language is infinite or finite?

texts: I know that in an infinite language there are infinite number of strings.  I want to know what type of the languages are C, C++ and JAVA? I can have infinite number of variables in all these languages, so I think all these languages are infinite. Please correct me if I am wrong.


texts: algorithm for correctly rounded floating point radix conversion

texts:
Is there any generic algorithm which implements a floating point radix conversion?

Lets say we have a $p$-digit FP number

$A = \sum_{i=0}^{p-1} A_i \beta^{e-i}$

in radix $\beta$ and with $0 \leq A_i < \beta$.

How do we find the $A'_i$, $e'$ values for the $p'$-digit base $\gamma$ FP number

$A' = \sum_{i=0}^{p'-1} A'_i \gamma^{e'-i}$

closest to $A$?

There is one question which explicitly asks about radix 2 to radix 10 conversion, but unfortunately the answers seem to be specific for these radix combination. Here I ask about the general case.

Also is an intermediate arbitrary precision FP calculation really necessary? (as in the function strtod in David Gay's dtoa.c)


texts: What is the error-detection-probability of CRC

texts:
I have a table which stores all serial numbers of devices in my system:

|------------------------|--------------------------|
|            #           |  Serial number (4 bytes) |
|------------------------|--------------------------|
|            1           |        0x????????        |
|------------------------|--------------------------|
|            2           |        0x????????        |
|------------------------|--------------------------|
|           ...          |            ...           |
|------------------------|--------------------------|
|           31           |        0x????????        |
|------------------------|--------------------------|

If I add a device to the system the position in the table is not predictable. If something in the system changes (e.g. add one or more devices, remove one or more devices, replace a device) I want to detect with a "high" propability that the system change. Therefor I want to use a CRC-32. In my system I have at least always 2 devices but max. 31 devcies. Meaning that the input of the CRC can vary between $2^{64}$ to $2^{992}$ different input streams.

As far as I understand:

The minimum input should be at least 32 bits
The most important is to use the right generator polynom. E.g.:

CRC-32
CRC-32-IEEE
CRC-32C

The selection of generator polynom depends on:

Input stream length
Error-detection-feasability
Collision probablility

Detection of a single bit error: All CRC's can do this
Detection of burst errors: All $n$-bit CRC's can detect burst errors up to $n$ consecutive bits. Also meaning appending new $n$-bit to the end of the input stream.

My concerns are the collision probability of the CRC32 is to high and due to that I don't detect a change in the configuration. Therefor I want to calcualte this probabilities and my questions are:

Is CRC the right method to use for my use case? If not what would be the best?
What is the "best" generator polynom for my use case?
How to cacluate the error-detection-feasability or collision probability if more then 32 consecutive bits change?
How to cacluate the error-detection-feasability or collision probability if $x$ not consecutive (different locations in the complete input stream) bits change?


texts: Find proportion of 'important' edge among all edges in a graph

texts:
I met this problem when dealing with a social network problem. It is a subproblem of that. The problem is like that:

We look at a graph $G(V,E)$, where $V$ is the set of vertices and $E$ set of edges. We define $x \in V$ as an 'important' vertex if at least $\frac 1 3 deg(x)$ ($deg(x)$ refers to the degree of $x$)of the vertices in $x$'s neighborhood have degree no more than degree of $x$. We then define 'important ' edge as the edge when either one of the two vertices of the edge or both are 'important' vertices. We define the set of 'important' edge as $E_1$.

We want to show $|E_1| \geq \frac 1 2 |E|$. I cannot really think out any method. Could anyone provide some suggestions?

Many thanks.


texts: CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s}

texts:
I know the answer which is:

\begin{align}
S &\rightarrow aS \mid T\\
T &\rightarrow aTbT\ \mid \varepsilon
\end{align}

Now, $bbaaa$ is in the language. But the given CFG cannot generate it. Is it a possible misunderstanding on my end about the prefix's? Can you explain? And if the CFG given is wrong, what is the correct CFG for the language?

Maybe this is the right grammar?

\begin{align}
S &\rightarrow aS \mid T\\
T &\rightarrow aTbS \mid bTaS\ \mid \varepsilon
\end{align}


texts: What other implementation styles are there besides compilation, interpretation and transpilation?

texts: Obviously there is JIT but it is basically run-time compilation. There is also implementing things in VHDL or ASIC. But my question is more towards software techniques for program building and execution


texts: Show that the halting problem is decidable for one-pass Turing machines

texts:
$L=\{<\!M,x\!>\, \mid M's \text{ transition function can only move right and   } M\text{ halts on } x \}$. I need to show that $L$ is recursive/decidable.

I thought of checking the encoding of $M$ first and determine whether its transition function moves only right (Can I do that?). If so then try to simulate $M$ on $x$ for $|Q|+1$ steps, if it stops then $<\!M,x\!>\, \in L$ otherwise it is not.

Is this correct?


texts:
I realize that each time I have to deal with the Big-O notation I am questioning myself why complexity in time or space share the same formal notation/letter. It is always confusing when I read examples in books because authors don't always give precision about whether the given result is a time or space complexity.

So, when you see that an algorithm has a O(n) complexity, you don't know much. You have to say: this algorithm has a O(n) time complexity.

IHMO I think it would be much more useful to use two separated letters like O(n) and T(1) for instance.

Is there such convention when talking about algorithm complexity?


texts: Proving that picking odd-numbered symbols can create the universal set from a non-regular language

texts:
Let's define the following operations:

$odd(string) = $ odd characters of $string$, $even(string) = $ even characters of $string$

Now say we have some language $L$, we will then define the following languages:

$odd(L) = \{odd(w): w \in L\}$, $even(L) = \{even(w): w \in L\}$

Need to prove that there exists a non-regular language, $L_N$, such that $odd(L_N)$ and $even(L_N)$ are both regular languages.

I thought of a few examples that might produce obvious regular languages with $odd$ and $even$, one of which was the language:

$L_1 = \{w \in \{a,b\}^*: |a|_w = |b|_w\}$, where $|x|_w =$ # of $x$'s in the string $w$

I know how to prove that this is non-regular, and upon inspection of a lot of values of $odd(L_1)$ and $even(L_1)$, it appears both produce the language $\{a,b\}^*$ which is obviously a regular language. Don't really know how I could prove that equality though.


texts: Counting the number of non-overlapping squares and cubes in a string

texts:
Given a string S of length n that contains exactly $\lceil\frac{n}{3}\rceil$
b's and $\lceil\frac{2n}{3}\rceil$ a's:

Suppose the charge is 2 for each non-overlapping occurrence of aaa, and 1 for each non-overlapping occurrence of aa. Note the occurreces of aaa cannot overlap the occurrences of aa. Also, note that the price is the max possible.

Question:
What is the string of length n with the minimum price over all such strings?


texts: Is it possible fo find a vertex-cover of size $\lceil \log |V| \rceil$ in polynomial time?

texts: If we have a graph $G=(V,E)$, can we find a vertex cover with size $\lceil \log |V| \rceil$ in polynomial time?


texts: How to prove that Exact Cover is NP-complete using SAT?

texts:
I found this solution online here, but I do not understand the logic behind transforming the instance of SAT to an instance of Exact Cover.

Here's the solution from the link (where C is the clause(s), A is the universe, and F is the subsets of the universe):

C1=(x1 ∨ x2) C2=(x1 ∨ x2 ∨ x3) C3=(x2) C4=(x2 ∨ x3)

A={x1, x2, x3, C1, C2, C3, C4, p11, p12, p21, p22, p23, p31, p41, p42}

F={{p11},{p12},{p21},{p22},{p23},{p31},{p41},{p42},
X1, f={x1, p11}
X1, t={x1, p21}
X2, f={x2, p22, p31}
X2, t={x2, p12, p41}
X3, f={x3, p23}
X3, t={x3, p42}
{C1, p11},{C1, p12},{C2, p21},{C2, p22},{C2, p23},{C3, p31},{C4, p41},{C4, p422}}

I understand how this proves that it is NP-complete, but I do not understand how A and F was populated. In other words, I am unable to figure out the "algorithm" behind creating the p11...p42 variables.


texts: Coloring grid with flexible number of colors and flexible number of occurrence per color

texts:
Suppose we have an $m \times n$ grid or table, with $m$ being the number of rows and $n$ being the number of columns. The user can select the number of colors (let's say $k$ colors) and how often each color is allowed to occur (i.e., we have a vector of numbers of occurrence of the colors $(i_1, i_2, \dots, i_k)$). The only constraints that apply are pretty obvious: $\sum_j i_j = nm$ and $i_j \leq ⌈nm/2⌉$ for $1 \leq j \leq k$.

I would like to color the vertices/cells in a way that no two adjacent vertices/cells have the same color (adjacence is defined as up, down, left or right; i.e., it is allowed to have the same color on a cell that is on the diagonal of the current cell). If possible, there should be no strict segregation of colors along the field, i.e., each color should be distributed over the field as "randomly" as possible.

So far I've implemented a brute force algorithm based on random selection of the coordinates of the colors. However, this approach is too inefficient.

One thought of mine was to first randomly arrange the colors in a linear list (i.e., as if we would have a $1 \times (nm)$ grid), then to take out the first $n$ elements and re-arrange them into the first row, randomly shuffling the colors until the condition is fulfilled. Then taking the next $n$ elements, arranging them as a second row and shuffling the elements until all conditions are fulfilled, and so on. This way, I would still have a random component, but at each step I would only need to deal with one row, and I might realise at an earlier time point that I got stuck and need to restart. However, I'm not sure whether this approach would really improve the performance.

Is there a better way to achieve the result? And is there a way to early determine whether a valid solution for a given input exists at all?


texts: Algorithms for Counting Number of Triangulations of a Simple Polygon

texts: Recently, I was asked to design an algorithm that counts the number of triangulations in a simple polygon without Steiner points. This is pretty simple to do in $O(n^3)$ time using dynamic programming, where $n$ is the number of vertices in the polygon. However, I would like to know if there is an $O(n^{3-\epsilon})$ algorithm for this problem. I am unable to find a better algorithm in the literature, nor can I find a lower bound. Any references would be appreciated.


texts: Good snapshottable data structure for an in-memory index

texts:
I'm designing an in-memory object database for a very specific use case. It is single writer, but must support efficient concurrent reads. Reads must be isolated. There is no query language, the database only supports:

get object/-s by attribute/set of attributes (there may be support for expressions, e.g. x.count < 5)
get object's attribute

A query is an imperative script composed of an arbitrary number of the above operations. The data size will be << memory, so all the object and indices on most of the attributes should fit comfortably without swapping.

What I need is a data structure for the object's attribute index, which can be O(n) on writes, not support write concurrency, but should support ideally O(1) snapshots (maybe copy on write) and O(logN) access. Ideally it would allow high concurrency on reads with maximal structural sharing between the versions.

I was looking at CTries, Concurrent BSTs and Concurrent Splay Trees but I'm not sure if I'm really looking in the right direction here. The above structures pay a lot of attention to the complexity of inserts which I don't care about.

The question: is there a known data structure that is a good fit for my use case out of the box?

EDIT: after thinking some more it seems that a persistent BST/Splay tree would work. The writer would update the 'master' copy and the queries would get the tree as of the start of execution and throw it away after they are done. However, I'm still interested if there's a better solution.


texts: Counting with constant space bounded TMs

texts:
The problem, coming from an interview question, is:

  You have a stream of incoming numbers in range 0 to 60000 and you have
  a function which will take a number from that range and return the
  count of occurrence of that number till that moment. Give a suitable
  Data structure/algorithm to implement this system.

The stream is infinite, so if fixed size data structures re used, i.e. primitive types in Java or C, they will overflow. So there is the need to use data structures that have a size that grows over time. As pointed by the interviewer, the memory occupied by those data structures will diverge.

The model of computation is a Turing machine with three tapes:

infinite read-only one-way input tape;
constant space bounded read-write two way work tape;
infinite write-only one-way output tape.

The main reason to choose the model above is that in the real world there is virtually no limit to the quantity of input that can be acquired using a keyboard or a network connection. Also, there is virtually no limit to the quantity of information that can be displayed on amonitor over time. But memory is limited and expensive.

I modeled the problem as the problem to recognize the language L of all couples (number,number of occurrences so far).

As a corollary of the Theorem 3.13 in Hopcroft-Ullman I know that every language recognized by a constant space bounded machine is regular.

But, in any given moment, the language L is a finite language, because the number of couples to be recognized is finite: 60001. So I can't use the pumping lemma for regular languages to prove that such language is not regular.

Is there a way I can complete my proof?

The original question is here.


texts: Find fastest sort for given range of numbers

texts:
I encountered a question from a test that I cant understand the answer

  given a range of numbers $[0...(logn)^{logn}-1]$ we need to find the quickest sort available and give his running time

now it seems like something to do with radix sort but if I try to switch bases to $logn$ I get $n$ numbers that each contain $logn\cdot log_{logn}(logn)=log(n)$ numbers. aradix sort in this situation will cost $n\cdot log(n)$ not good enough. if we switch to base n we will get something strange - $$log(n)\cdot log_n(logn)$$ I know that this is smaller number of digits but I have no idea if it will work with radix sort

any Idias?


texts:
I have a homework problem: Calculate the overall speedup of a system that spends 40% of its time in calculations with a processor upgrade that provides for 100% greater throughput.

Which is a pretty straightforward calculation with Amdahl's Law

$S =  \frac{1}{(1-f)+(\frac{f}{k})} $

$f$ = fraction of work performed by component = .40

$k$ = the speedup of new component = 1.00

$S$ = overall system speedup

Plugging in my values I get

$S =  \frac{1}{(1-.4)+(\frac{.4}{1})} $

$S = 1 $

Which from my understanding mean's there is no speed up in the system. I am unsure if my calculation is wrong or my understanding of Amdahl's Law because I would think this processor upgrade would've provided at least some system speedup.

My book gives an example where $S = 1.22$ means a $22\%$ increase in speed so I think I am interpreting the answer correctly, which implies I did my calculation wrong, but that also seems correct.


texts:
I am looking for an algorithm to generate an array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should lie within the triangle:

x + y + z = 1
0 < x < 1
0 < y < 1
0 < z < 1

Ideally I want each point within the area to have equal probability. If it's too hard, I can drop the requirement. Thanks.


texts: Mathematically determine if two strings are permutations of each other

texts:
I've come across many coding exercises that require me to determine whether or not two strings are permutations of each other and I've repeatedly wondered if it would be possible to convert each string to char codes and perform mathematical operations on them to determine equivalence.

My idea was to sum up the char values of each and compare. Then multiply the values of each string and compare. If both the sum and product are the same for both strings then the strings are permutations of each other.

Note: this is assuming strings of equal length. instantly reject strings of different length.

example:
A = "abcd" = [1, 2, 3, 4] -> Sum: 10 -- Product: 24
B = "bcda" = [2, 3, 4, 1] -> Sum: 10 -- Product: 24

Sum A = Sum B and Product A = Product B therefore A is a permutation of B

Is there a case where this would not hold true? how would one go about proving this. I want it to be true because it would be more space efficient than https://stackoverflow.com/a/2145221/2001647 which also runs in O(n)


texts: Two definitions of universal hash functions

texts:
I have seen two definitions of universal hash functions in the literature.

For any $i \geqslant 2$ let $[i]=\{1,\ldots,i\}$.

Definition 1:

  A family $\mathcal H$
  of hash functions from $[n]$ to $[m]$ is a
  $k$-universal family of hash functions if for any distinct $x_1,\ldots,x_k\in[n]$ and any possibly identical
  $v_1,\ldots,v_k\in[m]$, $$ \Pr\limits_{h\in\mathcal H} [h(x_1)=v_1\wedge \cdots \wedge h(x_k) = v_k] \leqslant 1/m^k \enspace . $$

Definition 2:

  A family $\mathcal H$
  of hash functions from $[n]$ to $[m]$ is a
  $k$-universal family of hash functions if for any distinct $x_1,\ldots,x_k\in[n]$, $$ \Pr\limits_{h\in\mathcal H} [h(x_1)=\cdots=h(x_k) ] \leqslant 1/m^{k-1} \enspace . $$

In both definitions if equality holds then it is called strongly $k$-universal or alternatively $k$-wise independent hash family.

Clearly the first definition implies the second. But is the other direction true?

It is easy to see that this is not the case for $n\leqslant m$.

  This is a counter example when $[n]\subseteq [m]$:

  Consider the family $\mathcal H$ composed of only one element, the
  identity function: $x \mapsto x$. It satisfies the second definition
  since for all $x \neq y \in [n], \Pr_{h\in\mathcal H} [h(x) = h(y)] = 0 \leqslant 1/m^{k-1}$. However, it does not satisfy the first definition
  since for all $x,y\in[n], \Pr_{h\in\mathcal H}[h(x) = x \wedge h(y) = y] = 1 > 1/m^k$.

  This answer is inspired by this other answer.

However, hash functions are usually employed in applications where $n>m$. So my question is whether this is also the case for $n>m$.


texts: Why must a Turing Machine that Repeats the Same Configuration Twice be in an Infinite Loop?

texts:
I have seen the following statement, and I don't quite understand the reasoning behind it:

  If a Turing machine repeats the same configuration twice, it must be in an infinite loop.

I thought that a $TM$ can be in a state $q_1$, with the tape on the left 000 and on the right 111. Let's say it moves right and then left, staying in the same state; aren't we in the same configuration?


texts:
The PARTITION problem is NP-complete:

INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$
QUESTION: Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = \sum_{a \in A \setminus A'} s(a)$

The problem remains NP-complete even if the elements are ordered as $a_1,a_2,...,a_{2n}$ and we require that $A'$ contains exactly one of $a_{2i-1},a_{2i}$ for $1 \leq i \leq n$ (Garey and Johnson, Computers and Intractability).

This variant should be known as EVEN-ODD PARTITION.

Do you see a quick reduction to prove its hardness? (or do you know the paper where it was first defined and proved)


texts: Lower bound on approximation degree in Nisan-Szegedy

texts:
In Nisan and Szegedy's 1994 paper "On the degree of boolean functions as real polynomials"[1] Lemma 3.8, how does proof work for $\widetilde{\deg(f)}\geq \sqrt{\,\tfrac16\mathrm{bs}(f)\,}$? It clearly works for $\deg(f)$ and only this portion is shown in Jukna's book [2, Theorem 14.11]. Why does the proof work for $\widetilde{deg(f)}$?

Here $f$ is boolean function, $\widetilde{\deg(f)}$ is the $\tfrac13$-approximation degree of $f$, $\deg(f)$ is real degree of $f$ and $\mathrm{bs}(f)$ is block sensitivity of $f$.

[1] Noam Nisan and Mario Szegedy, "On the degree of boolean functions as real polynomials". Computational Complexity 4(4):301–313, 1994 (SpringerLink)
[2] Stasys Jukna, Boolean Function Complexity. Volume 27 of Algorithms and Combinatorics, Springer, 2012. (Homepage)


texts: Finding the n-best items in a 0/1 Knapsack

texts:
I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: Variant of the Knapsack Problem.

Please read the previous answer for context; also I'm positive that the formula is still correct, but either my use or understanding of it is incorrect.

Let me illustrate the issue:

Item 1: weight=1, value=1
item 2: weight=1, value=4
item 3: weight=1, value=3

The calculated dp table (total items visited denoted in superscript):
$$
\begin{array}{c|ccc}
3 & 1^1 & 5^2 & 8^3 \\
2 & 1^1 & 5^2 & 7^2 \\
1 & 1^1 & 4^1 & 4^1 \\
\hline
 & 1 & 2 & 3
\end{array}
$$

Now to find the best two items out of the three ($p=2$), we use Carlos alternate formula $\max\limits_{p=0,j-1}\{T_{i, p}\}$. The best 2 dp table looks as follows:
$$
\begin{array}{c|ccc}
3 & 1^1 & 5^2 & 4^2 \\
2 & 1^1 & 5^2 & 7^2 \\
1 & 1^1 & 4^1 & 4^1 \\
\hline
 & 1 & 2 & 3
\end{array}
$$
You can clearly see this is wrong--look at the values of $T_{3,3}$ and $T_{2,3}$. Anyway this is how I calculated the table: the first two columns ($j$-items) are identical. The third column ($j=3$) is where we start using the formula.

$T_{1,3} = T_{1,2}$
$T_{2,3} = T_{i-w_j,j-1,k-1}+v_j = T_{1,j-1,k-1}+v_j = T_{1,j-1,k-1}+v_j = \max\limits_{p=0,j-1}\{T_{i, p}\} + v_j = \max\limits_{p=0,1}\{T_{1, p}\} + v_j = \max\{T_{1,1}, T_{1,2}\} + v_j = \max\{1,4\} + 3 = 4 + 3 = 7$
$T_{3,3} = T_{i-w_j,j-1,k-1}+v_j = T_{2,j-1,k-1}+v_j = T_{2,j-1,k-1}+v_j = \max\limits_{p=0,j-1}\{T_{i, p}\} + v_j = \max\limits_{p=0,1}\{T_{2, p}\} + v_j = \max\{T_{2,1}, \require{enclose}\enclose{updiagonalstrike}{T_{2,2}}\} + v_j = \max\{1,\enclose{updiagonalstrike}{5}\} + 3 = 1 + 3 = 4$

Now the reason the $T_{2,2} (5)$ is crossed-out because the total items visited count for that entry is already $2$, so I'm assuming we just skip it? But (un?)fortunately the two best items are $j=2$ and $j=3$.

For reference, I implemented using the k-dimension and that one gives the correct results. However, I'm still curious as to why this specific formula isn't working; I'm sure I'm doing something silly--please help me find it =)

EDIT: Dp tables for $k=1,2,3$

K=1
$
\begin{array}{c|ccc}
3 & 1^1 & 4^1 & 4^1 \\
2 & 1^1 & 4^1 & 4^1 \\
1 & 1^1 & 4^1 & 4^1 \\
\hline
 & 1 & 2 & 3
\end{array}
$

K=2
$
\begin{array}{c|ccc}
3 & 1^1 & 5^2 & 7^2 \\
2 & 1^1 & 5^2 & 7^2 \\
1 & 1^1 & 4^1 & 4^1 \\
\hline
 & 1 & 2 & 3
\end{array}
$

K=3
$
\begin{array}{c|ccc}
3 & 1^1 & 5^2 & 8^3 \\
2 & 1^1 & 5^2 & 7^2 \\
1 & 1^1 & 4^1 & 4^1 \\
\hline
 & 1 & 2 & 3
\end{array}
$


texts: DFA accepts common strings, reduction to NPcomplete

texts:
$B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each $M_i$ is a DFA and
all of the $M_i$ accept some common string.} \}$

I'm trying to show that B is NP-complete. I know I have to reduce it to another NP-complete problem, but I'm having a lot of trouble coming up with the algorithm that decides B.

I was thinking I could keep track of all the DFAs accepted by M1 and then check those in M2, any that accept there I'd feed to M3 and so on until I either ran through all the DFAs (accept) or ran out of accepted strings (reject).
I'm not really convinced this runs in NP time though. How exactly do I prove that it does? Or is this a terrible algorithm?

Thank you!


texts: Enumerating subgraphs containing a given node

texts: Given an undirected graph $G=(V,E)$ and a vertex $v\in V$, is there some algorithms to enumerate all induced subgraphs $G_s=(V_s,E_s)$, such that $v \in V_s$? It's preferred the algorithm doesn't enumerate duplicated subgraphs.


texts: How does one figure out where a class of languages falls under some complexity class?

texts:
I was wondering how can someone prove that one class of languages is of a certain complexity? For example, how could I show the Turing-recognizable languages are in P?

Would I have to come up with an algorithm that runs in deterministic polynomial time?


texts:
I came across this riddle link question:

Your name's Graham.
Bob wanted to send Alice a secret msg m. However, he was concerned about the security. He encrypted his message with a keyword that both of them knew. Several weeks before this, you overheard them exchanging the keyword k = 'EZRA'. Now, Bob has asked you to deliver the letter to Alice. You want to find out what's the letter about. Decrpyt the secret message m using the ciphertext c='MEDMTBJBMAE'.

The answer to this question was HELLO GRAHAM. How could one deduce that without knowing the answer of course.
What can we deduce from the keyword EZRA?


texts: Linear Temporal Logic with non-Boolean propositions (e.g. Integers)?

texts:
LTL works with Boolean propositions.
People probably studied extensions to non-Boolean propositions...
Do you know a good starting reference?

(I am aware of STL, but it also seems to talk about clocks, is there a variant without clocks?)

Update: the question is not about "true, false, maybe" but rather about LTL where we can refer to integers, for example. Example: one might want to write G(i+1 == X(i)), meaning that value i should increment.


texts: Scheduling N variable-time interdependent tasks across M workers

texts:
I have N tasks, each of them requires some time to complete. Time to complete is not the same for all tasks. Each task may depend on a number of other tasks (assume, that no dependency cycles are present). I have M (M is fixed, small and << N) workers that may be used to complete the tasks. I need to find a sequence of tasks, that each worker must complete in order to minimize the total processing time.

How is this problem formalized / modelled?
I am not sure, which textbook or paper I should read in order to understand, how one might approach this problem (looking for keywords here).

If there is a need to "peg" some tasks (not all) to certain workers, how is the problem "affected"? That is, does it become significantly harder to solve or reason about?


texts: Random Forest - Conditional Permutation Importance

texts:
I've been looking for the most unbiased algorithm to find out the feature importances in random forests if there are correlations among the input features.

Besides the most commonly preferred methodologies; gini-impurity reduction, drop-column importance and permutation importance, I found an algorithm called conditional permutation importance, in the given article: (https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-9-307#Sec8)

The steps for calculating the conditional permutation importance are given in the article like this:

In each tree compute the oob-prediction accuracy before the permutation
For all variables Z to be conditioned on: Extract the cutpoints that split this variable in the current tree and create a grid by means of bisecting the sample space in each cutpoint.
Within this grid permute the values of X j and compute the oob-prediction accuracy after permutation
The difference between the prediction accuracy before and after the permutation accuracy again gives the importance of X j for one tree. The importance of X j for the forest is again computed as an average over all trees.

For the first step, I'm having difficulties to reach oob scores of each tree as the default oob_score is calculated for all trees in the forest in scikit's methods. However, since I can still reach single trees as decision trees, I tried test inputs in these trees instead of oob samples but the kernel kept dying...

Sample RF Classiffier

clf=RandomForestClassifier(n_estimators=200,max_depth=3,oob_score = True)
 forest = clf.fit(train_inputs_arr, train_targets_arr)
Reaching single decision tree properties

forest[0].tree_.predict(test_inputs)

forest[0].tree_.predict(test_inputs)

For the second step, I'm having difficulty to understand what is meant by "creating a gird by means of bisecting the sample space at each cutpoint", and didn't really understand if I should determine the cutpoints of the selected Xj or for the other variables Z to be conditioned on.

Additionally, I'm also sharing the permutation importance method structure that I previously used, It simply permutes every feature calculates how the oob score decreases for each feature after permutation and the highest decrease in the oob score means higher feature importance. I wanted to modify this structure but I'm theoretically stuck at this point. What I really want to learn is any implementation of this algorithm on python.

def permutation_importances(rf, x_tr, y_train):
rf.fit(x_tr,y_train)
baseline = rf.oob_score_
imp = []
for col in x_tr.columns:
    rf_ = rf
    save = x_tr[col]
    x_tr.loc[:,col] = np.random.permutation(save)
    rf_.fit(x_tr, y_train)
    m = rf_.oob_score_
    x_tr.loc[:,col] = save
    imp.append(baseline - m)


texts: Implement K-means clustering with Map-Reduce

texts: Recently in an interview I was asked to implement k-means clustering using the Map Reduce architecture. I know how to implement a simple k-means clustering algorithm but couldn't wrap my head around to do it using Map Reduce(I know what Map Reduce is). Can someone provide me an explanation/algorithm of how to do that? More specifically I am looking what Map and Reduce phases will look like for such an implementation? I was also asked how many Mappers and Reducers will I need?


texts: Circuit satisfiability problem : SAT-C to SAT-2C

texts:
I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C.

Prove that $L$ is NP-complete.

1) Proving that $L \in$ NP is pretty simple : given the values of $C_1$, $C_2$, it is possible to verify if the result is true or false. The time required to do so is probably linear to the size of the circuits.

I'm stuck at step (2) of my proof :(

2) Since we know that SAT-C is a NP-Complete, we can try the following reduction : SAT-C $\le_p$ SAT-2C.

So if we have a circuit $\langle c \rangle \in  \text{SAT-C}$, there must be a function $f$ that turns it into two circuits (if we want to prove that the reduction is possible)

$f(c) \rightarrow (c_1,c_2)$.

For example, if our circuit is $(a \land b)$ (logical AND).

The first circuit could be the same as c --- $c_1 = c = (a \land b)$.

But what about the second circuit? How can $c_2$ calculate a different function than $c_1$ BUT at the same time, allow a reduction from the other way (SAT-2C to SAT-C)?

Any helps or suggestions would be greatly appreciated!


texts: Explain Hashed page tables in operating system

texts:
I have a difficult time understanding hashed page tables used in virtual memory management. Here is picture of the slide that I am referring to:

I understand that p is hashed and then the hash is checked in the page table for a match. What is elements referring to here? Is it the page table entry? What does chain mean and where is virtual page number located?

Can someobody help me understand the flow chart? Thanks


texts: Running time of algorithm (effect of j*j in for loops) - Theta Runtime

texts:
In Theta notation what are the running times of these algorithms?
Algorithm 1
for i=1..n
    j=1
    while j*j <= i:
        j = j + 1

Since the outer loop is going to n and the inner loop is going to sqrt(n). My guess is that it is Θ(n^2)
$$
\sum_{i=1}^{n} O(1) \sum_{j=1}^{\sqrt n}O(1)
= \sum_{i=1}^{n} \sqrt j*\sqrt j
= \theta(n^2)
$$
Thought process for the summations: number of terms * max term
Algorithm 2.
for i=1..n
    j=2
    while j <= i
        j = j * j

j performs similar to a log function. Since the outer loop is n. My guess is $Θ(n\log n)$
$$
\sum_{i=1}^{n} O(1) \sum_{j=2}^{\log n}O(1)
= \sum_{i=1}^{n} (\log n -2) * O(1)
= \theta (n * (\log n -2))
= \theta (n\log n)
$$


texts: Intersection of O(n) expanding circles with line from the origin

texts:
I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution.

  Consider yourself as a point located on the origin $(0,0)$ of an infinite
  two-dimensional flat world. There are $n$ sea waves surrounding you,
  each one modeled as a circle with center $(x_i, y_i)$, initial radius $r_i$,
  and propagation speed $s_i$, so that the radius of wave $i$ as a function
  of the time $t ≥ 0$ is $r_i + s_i \cdot t$. You choose any fixed
  direction and run “forever” at speed $p$. Will you be able to scape?

Some helpful restrictions given as assumptions are provided:

  $1 ≤ p ≤ 1000$
  $3 ≤ n ≤ 10^4$ [the number of circles $c_i$]
  $−1000 ≤ x_i,\;y_i ≤ 1000$
  $1 ≤ r_i ≤ 1000$
  $0 ≤ s_i < p$
  Except for $n$, all numbers are real, with at most three digits after the decimal point.
  Initially, you are strictly outside all the waves.
  There are not precision errors.

My solution so far is quite simple (I have programmed it in C++):

Each "fixed direction" to run forever is solely determined by the angle of that line with the X axis, namely $0 \leq \theta < 2 \pi$.
For each $\theta \in [0, 0.001, 0.002, \dots, 2\pi)$:

Recall that the map is within the square $[-1000, -1000]$ to $[1000, 1000]$, and the furthest distance between $(0,0)$ and any point in the map has distance $1000\sqrt{2}$. We advance at $p$ speed, so at most we will compute $1000\sqrt{2}/p \approx 1414/p$ iterations.
For each $t \in [0, 0.001, 0.002, \dots, 1414/p]$:

My position at time $t$ in line $\theta$ is $pos_t = (\cos \theta \cdot t \cdot p, \sin \theta \cdot t \cdot p)$.
Check whether $pos_t$ is inside any sea wave at moment $t$. Basically, check if the distance between $pos_t$ and the center of each circle is less than that circle's radius at moment $t$, namely $r_i + s_i \cdot t$. If so, bad luck; we're done with this $\theta$ and we continue the search.
If not, try with next $t$.

If no intersection is found after iterating all $t$s, then you will be able to scape (through line with angle $\theta$).

If all $\theta$s got some intersections, then we are not able to scape.

This solution has cost $\Theta(6000 \times 1400 \times n)$, which is impractical for $n \leq 10^4$. Informally, and without being precise, the multiplicative term may be $O(n^3)$ if $n \leq 10^4$ is considered.  Plus, it may not be correct, as I am assuming that $\Delta t = 0.001$ is fine; same for the angle.

I have thought about another idea, which is reducing systematically $\theta$. For instance, let's imagine that we've got a circle at $C = (5, 5)$ (in the line of $\theta = \pi/2$) with some small radius. From the beginning, we know that angles $\theta = \pi/2 \pm \alpha$ will never be an option, being $\alpha$ determined by tangent lines from $(0, 0)$ to $C$ and $t$; the more time passes, the higher $\alpha$ will be and thus the wider will be this range of restricted angles.

So, at moment $t$ we have a set of ranges of possible $\theta$s, and that range is reduced as long as $t$ increases (unless all waves have speed 0, for sure).

But how to continue from there? I see the same problems as with my implementation: determining $\Delta t$ and $\Delta \theta$.

I ask for your help to find a better algorithm. I suspect that there may be an algorithm that is just $O(k n)$ or $O(k \cdot n \log n)$ with $k$ being reasonably small.


texts: What should I consider to analyze my proposed ILP in a scientific environment?

texts: I am working on an NP-complete problem and, I have proposed an efficient (as I think) Integer Linear programming to find the solutions in some small instances. My algorithm can work on a greater size instance in comparison to other studies. My tutor does not consider it sufficient to provide just one ILP algorithm and, asks me to analyze it as well. But, I don't know what should I do to show the efficiency of my algorithm, and what measure should be analyzed. In fact, I do not know what else to consider in addition to the ILP programming if I want to show my method in a scientific environment. Any help is appreciated.


texts: Alternate definitions of enumeration machines

texts:
In my textbook, enumeration machines are defined as possessing a special write-only output tape, which they can write characters to, but not move the head of. When they hit the print state, the string on the output tape is enumerated and reset to a blank tape.

Is this equivalent to the model of enumeration machines where they have just one tape, the contents of which is enumerated (but not cleared) whenever they hit the print state? One direction seems easy, but I'm not sure how to prove you wouldn't need the extra tape.


texts: Decidability of equivalence to existential formulas

texts:
I'm looking for an algorithm to decide if a given first order formula over a fixed vocabulary admits a logically equivalent existential one (i.e. a formula in prenex form where all quantifiers are existentials).

Is it known if such an algorithm exists or does not exist? At least when no functions symbols are admitted? And if it actually exists, which is its complexity?

I know that, given a formula, we can build an equivalent one in prenex form. However, here is an example which illustrates that a formula, equivalent to an existential one, admits also an equivalent prenex formula which is not existential:

Consider the vocabulary $L=\{E\}$, where $E$ is a binary relation symbol. Then the formula
$$\exists x\,E(x,x)$$
which states that a directed graph admits a loop, is an existential formula and is equivalent to
$$\exists x\forall y\,\,\,\,x=y\rightarrow E(x,y)$$
which is in prenex form, but not existential. So applying the algorithm to build a prenex form to the second formula would not produce an existential one.


texts: Nomenclature for deterministic algorithms that might fail

texts:
What do you call an algorithm which is

Deterministic
When an answer is returned, it is correct
For some input, the algorithm returns no answer (fails, in bounded time).

Such algorithms crop up a lot in cryptographic attacks, for instance, where a
cipher is deemed broken when an attack (provably or demonstrably) works "most
of the time".

I'm working in a different field (coding theory) with an algorithm of the above kind. For
random, uniformly distributed input, the probability that the algorithm fails
seems to be so low that in practice it can be more or less ignored. However, we
have no succinct characterisation of input which cause failure. Previous work on
this algorithm has called it "a probabilistic algorithm" but I find this an
abuse of the term, since the algorithm is deterministic, once the input is
known.


texts: Importance of space constructability in time space relation in complexity

texts:
I am reading Arora-Barak's Complexity book. In Chapter 4, they state and prove the following theorem.

Why $S$ should be space constructible? Wouldn't all three containments of theorem hold, even if $S$ is not space constructible?

My other question is about Remark 4.3, the book claims that if $S$ is space constructible then you can make an $NSPACE(S(n))$ machine halt on every sequence of non-deterministic choices by keeping a counter till $2^{O(S(n))}$. I am not sure how we can keep such a counter in $S(n)$ space. The space constructability of $S$ implies that we can compute $S(n)$ in $O(S(n))$ space, not $2^{O(S(n))}$ in $O(S(n))$ space.


texts: How will the value, A(2) be available in, line 2, if A(2) is being calculated in, line 3?


texts: Confusion related to calculating time complexity

texts:
I have some confusion related to calculating the time complexity of this algorithm

opt(i)
   for j=i:n
      a = f(i,j) + opt(j+1)
   end

How is the running time of this algorithm $O(n^2)$?


texts:
I am trying to understand why this "proof" of ETM undecidability is wrong.
ALLTM={ < M >|M is a TM, L(M)=∑*}
ETM={< M >|M is a TM, L(M)=∅}
We know that ALLTM is undecidable, lets assume ETM is decidable (T is a TM that decides ETM) and get a contradiction.
 S= "On input < M >, M is a TM:

  1.Construct the following TM M1,

   M1=" On input x:

    1.Run M on x, if M accepts x, reject. otherwise, accept x."

    2.Run T on input < M1 >.

    3.If T accepts, accept, if T rejects, reject.

If ETM is decidable, ALLTM is decidable => ETM is undecidable.
Why this reduction doesn't prove that ETM is undecidable?


texts: How can I translate this following simple statements to prolog

texts:
These are simple statements:

Marcus was a man
Marcus was a Roman
All men are people
Caesar was a ruler
All Romans were either loyal to Caesar or hated him
Everyone is loyal to someone.
People only try to assassinate rulers they are not loyal to
Marcus tried to assassinate Caesar.

I have converted them to First Order Logic statements but I'm stuck in converting them to prolog code.
This is my prolog code up to statement number 5, and I don't know whether what I have done so far is correct or not. Also, I cannot find any docs about negation, for all, there exists in prolog code. How to translate them to prolog code?
man(marcus).
pompeian(marcus).
ruler(caesar).
pompeian(X) :- roman(X).
roman(X):-loyalto(X,caesar);hate(X,caesar).


texts: Difference between greedy and work conserving scheduler for DAG

texts:
For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do.

However, I found two different upper bounds on the computation time of $T$. For the following equations $T_{\infty}$ is the computation time on infinite processors and $T_1$ is the duration on one processor.

[1] Greedy Schduler (Theorem 1): $T = T_1/m + T_\infty$

[2] Work-Conserving Scheduler (Theorem 1): $T = (T_1-T_\infty)/m + T_\infty$

Both consider the scheduling of directed acyclic graphs where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to execute before task $v_j$ if there exists an edge $(v_i,v_j)$ between those two tasks. I have x threads that can execute those tasks. However, I am not 100% sure if [2] considers preemptive scheduling for their upper bound, but it does seem to be the case for their theorem 1.

In this presentation (page 41) I have found both equations for an upper bounds of the greedy scheduler.

Is there by definition any difference between the two schedulers?


texts: Formalism for unambiguous context-sensitive languages?

texts: I know that there are some languages that are unambiguous but not context-free (this is a good fact). Is there any kind of formalism for describing unambiguous context-sensitive languages? Even better yet, is there a parsing algorithm for unambiguous context-sensitive languages?


texts:
What is "Fibonacci" about the Fibonacci LFSR?
If I read right, Fibonacci LFSR means that it depends on its two last states, but from the example in Wikipedia it doesn't look like two states are taken in consideration (ie. XORing the taps in the current state, shifting and inputing the left bit..).
What am I missing?


texts:
An OS contains 10 identical processes that were initiated at the same time.Each process contains 15 identical requests. Each request consume 20 msec of CPU time.A request is followed by an I/O operation which consumes 10 msec.The CPU scheduling overhead is 2 msec. The system uses Round Robin scheduling with the time quantum of 10 msec.

Q1) What is the response time of 1st request of last process ?
  A) 210 msec  B) 140 msec  c) 230 msec  D) 240 msec

Q2) The subsequent request of the processes receives a response times of
 A) 110 msec  B) 220 msec  C) 230 msec  D) 240 msec

Ans: Q1) D

 Q2) C

What I thought :

For 1 process, there are 15 request so
15 * ( 20 + 10) = 450 msec  But all answers are so small than this approach. So no need to think about further i.e. CPU overhead then 2nd...3rd...processes.

Here my problem is I didn't get the concept behind this question properly. CPU overhead ( i.e context switching ) will take place between 10 processes or each process's 15 request.
So please tell how this scenario will work.

I didn't get the meaning of 2nd question.


texts: Is it possible to generate a better random number generator algorithm from an algorithm that use N computers with one that uses N+1 computers?

texts: Is it possible to generate a better random number generator algorithm from an algorithm that use N number of computers with an algorithm that uses N+1 number of computers? I use the word computer here, but I believe you can use the word processor instead as not all computers are single-processor computers although I am not sure if it makes any difference as the answer would be similar I think. The algorithm can be any algorithm, but for the sake of simplicity let's say the fastest one we know, and if you can't generalize for N, let's say N = 1.


texts: Asymptotic of interesting recurrence relation

texts:
I want to study the asymptotic behavior of the following recurrence relation:

$y_1=1$;

$y_{n+1}=y_{n}+(1+\frac{y_n}{n})^{-n}\ \ $ for $n\ge 1$.

I made an initial attempt and guessed that $y_{n} \sim Log(n)$.
Any referrence or hint about this might be helpful. Any help will be greatly appreciated


texts: Why there is no constraint on "Prover" in definition of $IP$?

texts:
According to the definition of $IP$ given in Sanjeev Arora and Barak there is no constraint on the running time of the "Prover" ( when "verifier" sends a message to the "Prover" and expects a message in return from it ). Why is it so  ?
Also the book says the "Prover" might compute some undecidable function. How is that possible ? Am I missing something trivial ?


texts: Can you give me an example word that is in the language $L = \{w | w ∈ \{a,b\}^∗ ∧ |w|_a = |w|_b\} $

texts:
Again, the language is $L = \{w | w ∈ \{a,b\}^∗ ∧ |w|_a = |w|_b\} $
Now I'm unsure about what the '*' indicates. Whether it means that either a or b can be repeated, or only one of them or if you can repeat a pattern made of a and b.
An explanation would also be appreciated but I thought one or more examples of what would be a word in the language and what not would be quicker.


texts: Which is better wording: x grows with $N^2$ or x grows with $O(N^2)$

texts:
Which of the following sounds better (or more rigorously):

x grows with $N^2$ or
x grows with $O(N^2)$ or
x grows quadratically with $N$.


texts: Will the Mersenne Twister PRNG eventually produce all integer sequences of a certain length?

texts:
I'm attempting to use the MT19937 variant of the Mersenne Twister PRNG to accomplish something.  Whether or not this something is feasible depends upon the answers to these two questions:

What is the greatest value of m for which the following statements hold true:

1 - For all seed values, the algorithm eventually produces every integer list of length m.

2 - There exists a seed value for which the algorithm would eventually produce a given integer list of length m.


texts:
I'm studying the issue of FPT algorithms and came to the k-disjoint triangles problem as can be seen
here on slide 60.
The problem summary is given a graph G and variable k, are there k disjoint triangles in the graph.
There are two methods, I want to focus on one of them. (Method 1)
First I randomly color the graph in 3k colors and then go over each permutation of colors and check whether there are k triangles with distinct colors.
What I fail to understand is what the time complexity of such examination (going over all the possible permutations) and how exactly can it be done?


texts: Should compilers automatically translate operations into shortcuts?

texts:
There are several coding operations that (I suspect) most compilers will change into more efficient operations at the assembly or machine code level. I have several questions about whether or not the compiler does any of this work, and if it's even best for the compiler to automatically do so.

(Note: These examples use C and C-like language syntax. However, just because i'm doing examples in C, doesn't mean I only want answers for the C compilers. I'm interested in how most major languages handle these things.)

The first is a += 1; vs a++;, where a is any integer variable. Both these codes ultimately result in the same thing (incrementing by 1), but a++ does it quicker somehow. I was self-taught for my first few languages and just never came across the a++ style, so I use the a += 1 style in all my private programming. However, of course later I discovered that a++ is more common when you only need to increment by 1. I believe the origins of it are from the old days where computers were super slow, therefore finding a shortcut for incrementing (or decrementing) by 1 was a huge deal. Now don't get me wrong, it could still make a difference today like in huge nested loops, and the most common place i see the shortcut is in loops anyway. Is there any reason why you would strictly want the slower a += 1 style? Incidentally, do most compilers automatically translate a a += 1 into a a++?

The second is dividing by a power of 2. b /= 8; can be shortcut to a simple bit shift by 3 bits to the right (towards the least significant bit, and filling in zeros on the MSB side)---as long as b is an integer. Should compilers make this translation, or is there some instance where you want the slower b /= 8 operation? Do compilers typically optimize this?

Can't think of any more simple types of shortcuts, but wouldn't be surprised if some exist.


texts:
For an open-addressing hash table, what is the average time complexity to find an item with a given key:

if the hash table uses linear probing for collision resolution?
if the hash table uses double probing for collision resolution?

From my understanding my answer to the first question would be $O(n)$
but I'm not sure about the double probing question.


texts: Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?

texts:
This "research vignette" (whatever that is) claims that the polynomial hierarchy

  classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of levels: problems at the zeroth level are the “easiest”, and for every integer $k$, problems at the $(k+1)$-st level have logical complexity “one notch higher” than those at level $k$.

Obviously this is just a heuristic explanation rather than any kind of rigorous claim, but is it true that problems higher in the hierarchy should be thought of as harder than problems lower in the hierarchy?

For example, consider the complexity class BQP. It is not believed to contain NP; in fact, many experts consider (Fig. 3) NP-complete problems to be much harder than the hardest problems in BQP. But the same experts also believe that BQP is not contained within the polynomial hierarchy PH (with Recursive Fourier Sampling as a concrete example of a problem believed to be in BQP \ PH). It therefore seems reasonable to say that for any $n$, there exist problems in $\Sigma_n \setminus \Sigma_{n-1}$ that are easier than RFS.

But putting these two results (that any NP-complete problem is harder than RFS, and that RFS is harder than some problem in $\Sigma_n \setminus \Sigma_{n-1}$ for any $n$) together, we find that there are problems in $\Sigma_1$ (namely, any NP-complete problem) that are harder (in fact, much, much harder) than certain problems in $\Sigma_n \setminus \Sigma_{n-1}$ for all $n$. Therefore, I don't see any way in which the polynomial hierarchy actually ranks problems by complexity.

Is there is mistake in my reasoning? Is there any useful sense in which problems higher up in the hierarchy are always harder than problems lower down? (I know this is a soft question, since there are different ways of formalizing the notion that one problem is "harder" than another. Maybe the answer is just that the PH is one way of ranking certain problems by difficulty, but not generally the best way.)


texts: Decision Making using Multiple Variables

texts:
What should I learn if I want to make a decision based on multiple variables? Followings are the example of a problem.

I have a farm. My variables are weather, humidity of air, humidity of soil, size of my fruits, etc.. Every hour, I will capture every data and store it in my database. My possible decisions are "Harvest", "Plant", "Wait". Sorry if this question is too generalized or too broad. I do not know what I want to learn.


texts: How does one calculate the block-sensitivity of a function?

texts:
I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity".

Can someone kindly provide some discussion/examples or such?

I am wondering if there is a way to talk of "block sensitivity" of any function of the form $f:\Sigma ^n \rightarrow \{0,1\}$ where $\Sigma$ is a finite set.

IF the above is possible then I guess given any such function one can Booleanize it to give another function $f' : \{0,1\}^{n \vert \vert \Sigma \vert \vert } \rightarrow \{0,1\}$ where $\vert \vert \Sigma \vert \vert$ is the number of bits required to encode $\Sigma$ in binary.

Then is it true that I can always calculate the "block-sensitivity" of $f$ say $bs(f)$ and from there get $bs(f')$ as $bs(f) = \frac{1}{\vert \vert \Sigma \vert \vert} bs(f')$ ?

(the typical situation I have is where $\vert \vert \Sigma \vert \vert = poly(n)$ and I hope that this doesn't produce any extra complication!)


texts:
Consider the load balancing problem on two machines. Thus we want to distribute a set of $n$ jobs with processing times $t_1,...,t_n$ over two machines such that the makespan (maximum of the processing times of the two machines) is minimized. Professor Smart has designed an approximation algorithm Alg for this problem, and he claims that his algorithm is a $1.05$ approximation algorithm. We run Alg on a problem instance where the total size of all jobs is $200$, and Alg returns a solution whose makespan is $120$.

(i) Suppose that we know that all job sizes are at most $100$. Can we then conclude that professor Smart's claim is false?

(ii) Same question when all job sizes are at most $10$.

Let's talk about the case (i):

We know that $\sum{t_i} = 200$ and that $t_i \leq 100$. The makespan of the Algorithm $Alg = 120$, so $Alg \leq 1.05 * OPT$. We have no other information about the algorithm used. A lower bound would be $LB = max( \frac{\sum{t_i}}{2}, max(t_i)) = max (100,100) = 100$ so I would say for that particular instance we'd have $120 \leq 1.05 * 100 = 105$ which means the claim would be false.

Likewise for the case (ii).

My answer is marked as incorrect, and I am struggling to do the right analysis.

Can anyone help please ?


texts:
An enumerator is defined as a 7-tuple:
https://en.wikipedia.org/wiki/Enumerator_(computer_science)

A Deterministic Turing machine is defined as a 7-tuple:
https://en.wikipedia.org/wiki/Turing_machine

How are these definitions different? Can a DTM M simulate an enumerator E, for part of its computation can it call an enumerator E as a subroutine and run it to some point then do something with its output etc?

I assume the answer is yes, you can do things like enum in normal programming with universal language / universal machine. Since DTM is usual definition of universal machine it can perform an enumeration-- just want to be sure, maybe I'm wrong and its a fundamentally different kind of machine?


texts: Minimal hitting set with respect to set inclusion from a book "Parameterized Complexity Theory"

texts:
In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality.

In Fig. 1.3, the author says a black colored leaf is the minimal with respect to set inclusion and a hitting set consists of the vertices labeling the edges on the path from the root to the leaf. However, both grey and black colored hitting set consists of 3 vertices. Why grey colored leaf is not minimal in this case?

Related question: Given a set of sets, find the smallest set(s) containing at least one element from each set


texts: Are IEEE floating point numbers intervals or point values?

texts:
The context is IEEE 754-2008 floating point number systems. The systems defined by the standard comprise, as far as I understand it, a bit-level representation and a set of guarantees on the precision for a given number of computations.

Now, I am wondering whether floating point numbers, i.e., the objects represented and manipulated in such a system, should be looked at as intervals—a contiguous set real numbers—or as point values—a unique real number. (Which interval? Crudely, with round-to-nearest, the nominal value plus-or-minus half a ulp.)

The arguments for intervals I see come mostly from the representational aspects of the system:

Numbers from ‘outside’ of the system—measurement data, say—are encoded with reduced precision and so the bit-level representation is in general clearly not the ‘true’ value, but—given the information about the rounding rule used—represents an interval in which the ‘true’ value lies.
Numbers from ‘inside’ of the system that are the result of a series of computations within the system have also been subject to the effects of intermediate rounding and so again—given the information about the rounding rule used—represents an interval in which the ‘true’ resulting value of the computation lies.

The arguments for point values I see come from the computational aspects of the system and the typical discussions of floating point:

Computations are performed on the real value that nominally corresponds to the bit-level representation, using some extra bits to enable precision guarantees. They are not applied to the interval bounds implied by the bit-level representation (and information about the rounding rule used in its generation), which would be possible in principle using some extra bits and double the effort (each computational step…).
Put differently: interval analysis is not applied.
If interval analysis were used, rounding rules would not be needed.
In the discussions of floating point I have seen, they are always generally treated as point values, e.g., depicting them as discrete points on the real line.

Now, the above arguments are composed by someone that has not read up on the floating point literature in detail, so they may not represent the common view among knowledgeable people in the field. I would like to learn the views of these people and the arguments used. (So I am not necessarily looking for an answer ‘point values’/‘intervals’ to the binary question of the title of this question.)

I have not specified restrictions to the binary or decimal systems. This may be relevant, I feel: in the binary case, the representations are normalized, so no significance information is available, but in the decimal case, the representation is not normalized. This means, I think, that in the latter case a crude way of doing interval analysis is possible (by reducing the number of significant digits)—not that this means it is actually done—, but in the former case, such crude analysis is not possible (although it would be far less crude, given the small magnitude steps—factors of 2).


texts: Is this a good way of generating diverse solutions to a problem using a genetic algorithm?

texts:
Imagine a complicated blackbox-esque system that has 20 inputs and 5 outputs. I have a set of criteria I am able to use to construct a fitness function. I run a genetic algorithm to deduce values which maximize my fitness function, and I keep iterating until a solution emerges which passes a threshold. Once this threshold is met, the genetic algorithm starts afresh except the fitness function now includes a positive term proportional to the euclidan distance between the candidate solutions and the previously determined solution (the one that exceeded the threshold earliar.)

Once a second set of inputs is found which matches exceeds the threshold, the fitness function is updated to also include a term proportional to the euclidian disance from the second solution. Both terms are divided by two to prevent this euclidan distance derived terms in my fitness function from overpowering the others.

Would a process like this, iterated sufficiently, be an efficient way of generating a diverse set of inputs, each of which represents a set of inputs which achieve a high fitness score?

(Please assume that a diverse of solutions exists for the problem at hand; the goal of the algorithm is to find them)


texts:
Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices. Define CLIQUE as the decision problem

$$\{ \langle G, c \rangle \mid G \text{ has a clique of size } c\}$$

Define the problem $\sqrt{n}$-CLIQUE as follows:

$$\{\langle G \rangle \mid G \text{ has a clique of at least size } \sqrt{n}\}$$

where $n$ is the number of vertices of $G$. It is easy to reduce $\sqrt{n}$-CLIQUE to CLIQUE. How can we go the other way and thereby show that $\sqrt{n}$-CLIQUE is NP-complete?

Idea: If $c \geq \sqrt{n}$, we can add dummy vertices to $G$ until $c = \sqrt{n}$. What do we do if $c < \sqrt{n}$? It seems we need to be able to remove vertices without disturbing the size of the largest clique. My idea in this case to remove a vertex if it has less than $c-1$ edges. Obviously the new graph has a clique of size $c$ if and only if the original graph does. But what happens if we can't remove enough vertices? Can we conclude that if a graph has $n > c^2$ vertices each with degree $\geq c$ then a clique exists?


texts:
It is said that the intuitive meaning of $\mu$ is finite looping where as the intuitive meaning of $\nu$ is infinite looping in $\mu$ calculus. I understand this for finite systems, but why is this true in general?

Is there any theorem which proves this ?


texts: How do we analyze Algorithms with parallelism features

texts:
As I am comparing between two algorithms, I was wondering which is the best approach to use to compare between the both. Big-O seems not the perfect metric for me, as the it's based on the worst-case, while most of cases in the area that I am working on is optimized.
The second though is, I am using "Python-Maps" (and other parallelism features, but let's take just "map no python as an example" to simplify the question) to implement the first algorithm, while I don't use parallelism features in the second algorithm.

What is the approach to compare, abstractly, the both algorithms ?. Can you please give any hint ?


texts: How is A* search superior to Dijkstra's algorithm

texts:
Dijkstra's algorithm is often quoted as being used to find the shortest path route however I was surprised to know that there exist A* search which is a extension of Dijkstra's algorithm.

How is it that A* search algorithm is able to perform better compared to Dijkstra's algorithm , what sort of technique does it used that Dijkstra's algorithm did not use ???


texts:
How to simplify this context-free grammar?
$$
S \to ACD \\ A \to a \\ B \to \varepsilon \\ C \to ED \mid \varepsilon \\ D \to BC \mid b \\E \to b
$$

Can the simplification result in this CFG?

$$
S \to AC \\ S \to A \\ A \to a \\ C \to E \\ E \to b
$$


texts: How to implement GREEDY-SET-COVER in a way that it runs in linear time

texts:
This is an exercise in the book Introduction to Algorithm, 3rd Edition.

The original question is:

Show how to implement GREEDY-SET-COVER in such a way that it runs in time $O(\sum_{S\in\mathcal{F}}|S|)$.

The GREEDY-SET-COVER in the text book is as follows:

Definition for $(X,\mathcal{F})$ is given as:


texts:
What is the difference between dynamic loading and dynamic linking?

Both systems seem to allow shared libraries, but I am struggling to differentiate between them.


texts: Doubt regarding the implications of a 2-SAT constraint

texts:
Consider an example 2-SAT instance with the constraint (x1 ∨ x2).
This CNF has these two implications:
¬x1→x2 and ¬x2→x1.
"They actually mean, if x1 is false then x2 must be true, and if x2 is false then x1 must be true, respectively. Any other case would make the 2-sat problem unsatisfiable."
My doubt is regarding this statement. I can understand the above written two implications, but I don't understand how only those two values of x1 and x2 make this 2-SAT instance satisfiable. Clearly setting both x1 and x2 to true can also satisfy this constraint.
I don't see that case being captured in the two implications written above.
Can someone explain this to me? Apologies if this is a stupid question, I haven't formally studied logic.


texts: Meaning of "number of keys in the range $a$ to $b$"

texts:
Regarding this question:

You are given an unsorted array $A$ of $n$ integers in the range $2^n −10n \leq A[i] \leq 2^n$.
Suggest a data structure that allows to answer in $O(1)$ steps the number of keys in the range $a$ to $b$ (note that $a, b$ are not necessarily integers). The construction of data structure should cost at most $O(n)$ steps.

Describe in few sentences the data structure.
Write a pseudocode for constructing the data structure.
Write a pseudocode for the numberKeys(NewDataStructure,a,b).
Give a short explanation of the time and space complexity of (2) and (3).

Can someone please explain me what "the number of keys in the range $a$ to $b$" means?


texts:
I need help with deciding if $L$ is context-free.

$$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$

Can be rewritten into:

$$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \ge 0\ , s > t\}$$

When we see the first occurrence of $c$, we push the $c$:s onto the stack. But we can't make difference between $d^q$ and $d^t$,  so comparing $s < t$ is impossible when popping the $d$:s.

Hence $L$ is not Context-Free.

Is my reasoning right ?


texts: There are n variables $x_1$, $x_2$,..., $x_n$ and each one of them takes values from 1 to k (k>= n) and all are distinct. How can I represent this in the CNF form? (I tried the trivial way of trying all assignments and then checking if they are distinct, but I think it could be done better)


texts:
I was reading an article about Binary Search on one of the websites on the internet that someone had linked, can't find the link anymore, but this really is bothering me, and I think I am missing something.

function binary_search_alternative(Array, k) is
    L := 0
    R := n − 1
    while L < R do
        m := floor((L + R) / 2)
        if k > A[m] then
            L := m + 1
        else:
            R := m
    if A[L] == k then
        return L
    return unsuccessful

My thinking is that at each iteration we are taking an array (n-1) and after each iteration we are halving it so floor((n-1)2^i), where floor((n-1)2^i) = 1, this is before the last iteration, and my calculations show that the number of comparisons for this one is log(n-1), but the article said that it was log(n) + 1. Wikipedia has a similar code, and they say the same thing. How is that?


texts:
I feel the notion "there are countably many Turing machines" is wrong.
Suppose there is a Turing machine whose input alphabet is {0}. If we replace the input alphabet {0} with {a} and replace every occurrence of "0" with "a" in the transition table, then we get another Turing machine. Obviously, these two machines are different beacause they recognize different languages, but using any one reasonable encoding sheme, they could be encoded into the same string. So claiming Turing machines are countable only by enumerating their encodings is wrong, because actually there isn't a bijection between Turing machines and their encodings.
Is my opinion right?


texts: Operation count: Solving Ax=b with sparse diagonal matrix

texts:
I've seen several tables that list operation counts for matrix-inversion related problems, but none of them actually brought forward the way of computing them.

I'm interested in solving

Ax=b

for x, and k-diagonal sparse matrix A - which is a sparse matrix that has zero elements on all but k many diagonals. On these k diagonals, it can have either zero or non-zero elements.

I'd like to find out the number of operations as a function of N, the length of b, and k, the number of diagonals in A.

Is there an explicit answer? How could I compute it?


texts: Why do the swap step in Prim's algorithm for minimum spanning trees?

texts:
I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees.
Why do we need to do the swap step for proving the theorem that if we choose a set of vertices  in minimum spanning tree of $G(V,E)$and let us call that $A$ such  $A\subset B$,  the edge with the least weight connecting $A$ to $V-A$ will always be in the minimum spanning tree ?  The professor has done the swap step at point 59:07 seconds in the video.


texts:
For a homework assignment I am asked to provide claim sequences to verify that the given conditional does indeed satisfy its speciﬁcation (to compute in r the absolute value of x).

val x: Z = readInt()
var r: Z = x

l"""{ 1. r == x               premise }"""

if (x < 0) {
  l"""{
    1. x < 0              premise
    2. r = x              premise
    3. r < 0              algebra 1 2
  }"""
  r = -x
  l"""{
     1. r = -x                premise
     2. x < 0                 premise
     3. r_old < 0             premise
  }"""
} else {
  l"""{
     //   also in this branch, you must prove all the 3 assertions
  }"""
}
assert(!(x < 0)  | r == -x)   // if x < 0 then r = -x
assert(!(x > 0)  | r ==  x)   // if x > 0 then r = x
assert(!(x == 0) | r ==  0)   // if x = 0 then r = 0

This is the code we are given to start and are asked to prove the 3 assertions. Im having trouble starting out because I am not sure what structure I need to use. Do I need 3 sub proofs in each conditional in order to prove the three assertions?


texts:
I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential.

Do linear/constant/quadratic complexities count as polynomial? An answer in simple English will be appreciated :)


texts: Numerically solving an ode with infinitely many variables of which only finitely many are significant in magnitude

texts:
Suppose I have an ode that involves infinitely many variables, with the property that at any given time, only finitely many of them are large enough to be of interest (say $>10^{-10}$). However, at different times, different variables may become large.
It is also the case that given such a set of interesting variables, only a finite number of equations contain terms that are large. This is somewhat like a generalized version of locality.
The question is, is there any research on solving such equations numerically? My idea is to keep track of the variables of interest, and also "secondary" variables, which are significantly (in magnitude) coupled with the "interesting" variables; we can also keep track of "tertiary" variables and so on. We then go on solving the ode, ignoring the uninteresting variables (assuming them to be 0), and check regularly if a new variable comes into (or goes out of) interest.
To give the background, I'm working on an artificial chemistry simulation. All the reactions, and their reaction rate formulae (following Arrhenius) can be determined by my set of rules. For example, $$A + X \to B\\ B \to X + C$$ simulates the conversion $A \xrightarrow X C$ with catalyst $X$. In this case, $C$ is initially small, but eventually becomes large. This system is finite, and so is solvable by conventional methods. But if the reations are infinite (but recursively enumerable and decidable, and for simplicity, each combination of reactants only result in a finite number or reactions), it creates an infinitely large set of ode.


texts:
I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them):

{0, 1, 2} < {0, 1, 3}
          < {0, 2, 3}
          < {1, 2, 3}
          < {0, 1, 4}
          < {0, 2, 4}
          < {1, 2, 4}
          < {0, 3, 4}
          < {1, 3, 4}
          < {2, 3, 4}
          < {0, 1, 5}
          < ...

The sets are generated recursively: increase the highest number and reset all the other elements to the lowest possible numbers, then apply this algorithm recursively to the remaining numbers.

The position within this ordering is given by:

C(x[1], 1) + C(x[2], 2) + C(x[3], 3) + ...

where x[i] is the i-th element in the sorted set and C(n, k) is the binomial coefficient.

Does anyone know of a name for this kind of total ordering?  Furthermore, what other common ways are there to order sets containing a fixed number of totally ordered elements?