texts: How to use an algorithm to find a satisfying assignment in polynomial time?

texts:
I am currently trying to solve the following problem but I am unsure how to go about it. The problem states:

Suppose that someone gives you a polynomial-time algorithm to decide 3-SAT. Describe how to use this algorithm to find a satisfying assignment in polynomial time.

To my understanding the 3-SAT is simply a conjunction of any 3 disjunctions that turns out to be true (i.e. something like (x1 | x2 | x3) & (x4 | x5| x6) where | represent or and & represents and). In this case you could have used any ordering of the variables and you could have negated them at your pleasure. Furthermore You can keep adding conjunctions, but each one has to have 3 variables. Please correct me if I am wrong in any statement above.

Now, they want us to find a satisfying assignment in polynomial time, meaning values of x1, x2, x3, x4, x5, x6 that make the value true. However, isn't that what we are given in the first place? I am confused as to what to do and if I am interpreting the question correctly.


texts: How curves are represented in a computer

texts: I am confused now (in thinking about limits and continuity) how curves are represented in a typical modern computer. Curves are "continuous" in that there is no discrete change from one angle to the next. Wondering how the computer approximates this and/or what equations it uses/approximates.


texts: Notation Conventions for Tree Data Structures

texts:
I'm currently working on a paper describing a new algorithm in computational science. If all goes well, this algorithm will be around for a while (within the specific community). As such, I want to set notation conventions that will not drive other people insane. The primary difference is that this algorithm makes use (logically) of tree data structures while the traditional algorithms in the field have used linear arrays.

The old algorithms therefore could denote specific data as $data_i$ (that is, using LaTex subscripts. Similarly, one could refer to $data_{i-1}$, and it would be clear that that is the "parent" data to $data_i$. Unfortunately, trees do not support this sort of indexing.

Are there any notation conventions for trees that allow clear, concise descriptions of that sort? I want to be able to give talk about an arbitrary bit of data (i.e. $data_i$) and readily discuss parent and child data. The community is mathematician heavy and as such mathematical notation of the sub/superscript y operator sort is favored over the class.property CS style. Note also that these are arbitrary trees; they need not be binary or any other such structure.

Does anyone know of a notation convention that would fit the bill? Alternatively, is there a better place to ask this? Thanks for the help.


texts: How do we fix area of detectors in object detection?

texts:
I have gone through various articles on medium and also some from other sites trying to understand SSD. I am able to figure out most of the things from articles except this one.

They always say that the area and location of detectors/anchors in fixed in the model. They also show us the various shapes of detectors based on aspect ratio. But I can't understand how to fix the location of detectors.

Suppose, I want my detector to focus only on the top-right of the image, how can I achieve that? I mean, the filters learned by CNN are applied to the whole image by sliding through its parts. How can we actually achieve this?

Is this related to 'receptive field' or '1x1 convolution'? I am trying to understand these two concepts too but haven't progressed much.


texts: Maximum Schedulable Set Zero-Lateness Deadline Scheduling

texts:
This is a homework problem for my introduction to algorithms course.

  Recall the scheduling problem from Section 4.2 in which we sought to
  minimize the maximum lateness. There are $n$ jobs, each with a deadline
  $d_i$ and a required processing time $t_i$, and all jobs are available to be
  scheduled starting at time $s$. For a job $i$ to be done, it needs to be assigned
  a period from $s_i \geq s$ to $f_i$ = $s_i + t_i$, and different jobs should be assigned
  nonoverlapping intervals. As usual, such an assignment of times will be
  called a schedule.

  In this problem, we consider the same setup, but want to optimize a
  different objective. In particular, we consider the case in which each job
  must either be done by its deadline or not at all. We’ll say that a subset $J$ of
  the jobs is schedulable if there is a schedule for the jobs in $J$ so that each
  of them finishes by its deadline. Your problem is to select a schedulable
  subset of maximum possible size and give a schedule for this subset that
  allows each job to finish by its deadline.

  (a) Prove that there is an optimal solution $J$ (i.e., a schedulable set of
  maximum size) in which the jobs in $J$ are scheduled in increasing
  order of their deadlines.

  (b) Assume that all deadlines $d_i$ and required times $t_i$ are integers. Give
  an algorithm to find an optimal solution. Your algorithm should
  run in time polynomial in the number of jobs $n$, and the maximum
  deadline $D = \max_i d_i$.

I've solved the problem as worded with the recurrence

$Opt(i, d) = \max\left \{
\begin{array}
 \\ Opt(i-1, d-t_i) + 1 \hspace{20 mm} d\leq d_i
 \\ Opt(i-1, d)
\end{array}
\right \}$

but our instructor added a new requirement that our algorithm must not be dependent on D. This recurrence seems like it would produce an $O(nD)$ running time if implemented with dynamic programming.

I can't figure out how to reduce its running time from $O(nD)$ to $O(n^k)$. To me it seems like it's a variation on the knapsack problem with all values equal to 1. In which case it seems like this is the best that can be done.

If I'm doing something wrong could someone point me in the right direction, or if I've done everything right so far, could someone at least give me a hint as to how I can make an $O(n^k)$ recurrence or algorithm.


texts: What are witnesses C and k for an O-bound?

texts:
Can someone explain the following about big-O from the textbook to me? (I'm trying to catch up after missing classes due to illness.)

  Show that $f(x) \in O(x^2)$ where $f(x) = 8x+9$. List the witnesses $C$ and $k$.

From what I have gathered I am looking at/for a distinct point witnessed by $C$/$k$ wherein there is a (lower bound?) point to where one of the functions ($f(x)$ or $g(x)$) is increasing at a faster rate for any given point $\geq C$?

The textbook talks testing/trying out different $C$ witnesses (ex. 1) to where I then solve for $8x+9\leq(1)x^2$ or (ex. 2) and solve for $8x+9\leq(2)x^2$, but I'm not sure where I go from there. If I'm letting $C=1$ then I get:

\begin{gather*}
8x+9\leq(1)x^2\\
0\leq x^2-8x-9\,.
\end{gather*}

Then from here I have tried the quadratic equation resulting in $(8 \pm \sqrt{100})/(2)$ or I saw where $0\leq x^2-8x-9$ could be factored to $(x+1)(x-9)$ so I know $-1$ and $9$ make zeroes on my number line, and I tried plugging in test points where I found everything less than $-1$ or greater than $9$ yields a positive, and everything between $-1$ and $9$ yields a negative, but from this point I am lost.

Can someone explain what I'm supposed to be doing and how to go about it?


texts: Showing that a language satisfies the pumping lemma

texts:
I am wanting to show that this language fails to show that it is not context-free. So, in essence, it satisfies the pumping lemma

If L = {ambncndn | m,n >= 1 }

Should I have n be the constant of the pumping lemma? Is z=ambncndn and |z|= m+3n>n ?

By the pumping lemma, there exist u,v,w,x,y such that z=uvwxy, |vwx| <=n, |vx|>=1 . I'm just a little thrown off by the two different letters for the exponents, can I treat m and as another n?


texts: Counterexample for simple parity automaton reduction

texts:
I am dealing with deterministic parity automata and state space reduction (not minimization).

If we define $\equiv_L$ to be the equivalence relation that sets two states equal iff starting from those states the automaton recognizes the same $\omega$-language, merging those states is in general not an operation that preserves language. The canonical example is a parity automaton with two states $q_a, q_b$ that moves to $q_a$ whenever reading an $a$ and to $q_b$ whenever reading a $b$. Giving both states a different parity yields a counter example.

Now what if we refine this relation so that $p \sim q$ is true iff $p \equiv_L q$ and in addition the two states have to have the same color assigned to them. I feel like there has to be a counter example but I can't think of one. That is my question; what is a simple counter example that shows that merging states like this can alter the langauge?

(in case it is not clear what I mean by "merging": merging $p$ and $q$ means removing $q$ from the automaton and redirecting all transitions that would move into $q$ to target $p$ instead)


texts: Multiple Weighted Hyerplanes to Classify XOR

texts:
I learned in class that perceptrons cannot simulate the XOR operation. My professor told me that one fix was to left the points onto a higher dimensional space. That is pretty obvious, you just use the feature $x_1x_2$. He also said that you can use multiple weighted hyperplanes and nonlinear functions to do so. I'm not sure how to do that. Here is all the formal definitions and whatnot:

Suppose you have the following four points (with labels) $(1,1): +1; (-1, -1): +1; (-1, 1): -1;$ and $(1, -1): -1$ (i.e. the XOR function).

Find a weighted combination of hyperplanes $\mathrm{Sign}(w_1h_1(x) + · · · + w_kh_k(x))$ that classifies all 4 points correctly. A hyperplane is a function of the form $h_i(x) = \mathrm{Sign}(v_i · x + b_i)$. In other words, $h_i(x) = 1$ when $x$ is on one side, and $h_i(x) = −1$ when $x$ is on the other side.

Now, let’s generalize to $d$ dimensions. There are $2^d$ input points of the form $(±1, ±1, . . . , ±1)$. The label of a point is $+1$ if an even number of coordinates were $−1$, and the label is −1 if an odd number of coordinates were −1. Find a weighted combination of hyperplanes that correctly classifies these
inputs.


texts:
If you look at page 13 of the lecture slides here there is this line

$H(Y) = H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha))$

I don't really understand what the term on right hand side is. At first I thought it's joint probability of binary random variables but that does not make sense. After a while I notice that the first parameter is the probability of $Y = 0$, the second parameter is the probability $Y = e$ and the third parameter is the probability $Y = 1$. However, I still dont really understand what this notation means, and why this equates to

$H(\alpha,(1-\alpha)) + (1-\alpha)H(\pi,(1-\pi))$

Can someone please help me out here?

Thank you!


texts: Optimization problem where penalty is sensitive to permutation

texts:
Say, I have the situation where I am looking into all the possibilities to obtain a value of e.g. 20 (exactly) by taking all possible combinations of sums using values from 1 to 5. While doing this, I want to minimize my penalty P. There is no limit to the amount of values I use (I could do 4x5, 20x1 and any other possibility).

The penalty is not based on the amount of values I use, but instead on the intermediate values of the summation.

In this example, let's assume the penalties are as follows:

1 * k for 0 <= S < 2
2 * k for 2 <= S < 6
3 * k for 6 <= S < 11
4 * k for 11 <= S < 20

where k is the current value being added to my intermediate sum S.

So if I consider e.g. [1,2,3,4,5,5] (in that particular order), my total penalty would be P=1*1+1*2+2*3+3*4+3*5+4*5=56.

However, the penalty changes if I permute my array to e.g. [1,5,4,5,2,3] (P=53) or [2,4,5,1,3,5] (P=61).

In this simple example, we have 192 different sets of values that can together add up to 20. The number of possible permutations per set (taking into account non-unique values) varies between 1 (in case of 20x1, 10x2 etc) and 15840 (7x1, 3x2, 1x3, 1x4). The naive approach would be to just loop through all sets and their permutations, which is doable for the given example.

However, my actual problem has about 2000 possible sets of numbers and the number of permutations goes all the way up to ~1E+8. It is no longer fun to use a naive approach in this case.

I do know that I can greatly reduce my number of permutations, as the order of my values does not matter if I stay within the same range (when I'm at S=11, it no longer matters in what way I add the final 9).

My question is how I can properly implement this knowledge to improve my naive algorithm such that it disregards those permutations a priori (first generating all permutations and then removing is not really an option, as even 8-bit unsigned integers will generate 15 GB arrays for all permutations). Furthermore, I was wondering whether there are any additional improvements that could be made here.


texts: Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle

texts:
Consider the field $GF(p)$, where $p$ is a prime number. If there is a function $f: GF_p \times GF_p \rightarrow GF_p$ which has an unknown degree $d$ polynomial, with $1 < d < p / 4$.

Although $f$ is unkonwn to us, there is an erroneous oracle $O$ satisfy the following property:
$\underset{(x,y)\in GF_p \times GF_p}{Pr}[O(x,y) = f(x,y)]\ge1 - \frac{1}{20d}$.

The question asks us to come up with a randomized algorithm which makes $O(d)$ queries to the oracle $O$ and returns the correct value of $f(0,0)$ with probability at least 0.9.

The following is my thinking process: the probability of $O(0, 0) = f(0, 0)$ is at least $1 - \frac{1}{20d}$ according to the condition before. If the probability is at least 0.9, then $d$ should be $d \ge \frac{1}{2}$. Then $p$ should be larger than $2$. We can assume the expression for $f$ is $a_db_dx^dy^d + a_db_{d-1}x^{d}y^{d-1} + a_{d-1}b_dx^{d-1}y^d + a_{d-1}b_{d-1}x^{d-1}y^{d-1} + ... + a_0b_0$. There are total $d^2$ number of items in the function. The randomized algorithm is that we could randomly select the value of $x$ and $y$ from $GF_p$, and at the following $d^2$ steps, we decide the parameters of the polynomials.

for i from 1 to d steps:
    for j from 1 to d stpes:
         randomly assign the values of other parameters except a_ib_j;
         solve the value of a_ib_j using the randomly assigned x, y and
         the result queried from Oracle with x and y;

This is just my general idea. The problem is I do not know the degree $d$, so I cannot decide the exact number of steps $d^2$. And even if I know the degree $d$, how can I manage to decrease the time from $O(d^2)$ to $O(d)$?

Or maybe I am going in the wrong way. Can somebody help me with this?
Any help would be appreciated. Thanks in advance.


texts: Implication of Berman and Hartmanis conjecture

texts:
I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture :

  All $NP$-Complete languages are $p$-isomorphic.

Then the book says that if the conjecture is True then $P \ne NP$. I am unable to make sense of the proof the book gives, which is:

  If $P=NP$ then all languages in $P$ are $NP$-Complete, but there are finite languages in $P$ and these cannot be $p$-isomorphic to infinite languages.


texts: What is the fastest and most elegant way to change a matrix dimension?

texts:
I have been writing code for a paper and I'm reading an image in RGB space in OpenCV which means that its read as a 3D matrix (HEIGHT x WIDTH x 3 (RGB) ).
I'm reshaping the image into a 2D matrix ( NB_PIXELS x 3 (RGB) ) using this code :
image = image.reshape(len(image) * len(image[0]), len(image[0][0]))

This reshaping process is an important step in the method that I'm going over in the paper.
Since I can't have the paper depend on a library like NumPy I would like a more elegant way to explain the reshaping. Are there any papers that I can reference or any equations, methods ..etc that I can use as a replacement to the code that I shared ?
Thank you!


texts:
Suppose we are given an NFA $M$ (without $\epsilon$-transitions) that we only know the alphabet $\Sigma$ and the number of states $|Q|$ but we do not know any other details of the NFA. We want to develop a black box algorithm that can test if $L(M)=\Sigma^{*}$.
My idea is that we can feed every string up to size $|\Sigma|^{|Q|-1}$, if every strings are accepted, then $L(M)=\Sigma^{*}$. Since all strings up to size $|\Sigma|^{|Q|-1}$ must go through every reachable state in $M$, if all of them get accepted then no matter what string is input, it will be accepted. Am I correct?


texts: Is the following language is a context free grammar language?

texts: The question is to determine whether L is a context free grammar language, what do you think?


texts: What is the whole picture of the NP-hardness proof of Super Mario Bros?

texts:
I am reading the NP-hardness proof of Super Mario Bros. in the paper "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta.

I can get the basic idea of the proof framework presented in Section 2.1. I think I also understand the Start gadget, Finish gadget, Variable gadget, Clause gadget, and Crossover gadget individually used in this proof. See the figure below.

However, I failed to plug these gadgets into the proof framework to construct a complete instance/scenario of Super Mario Bros. Specifically,

In the Variable gadget, Mario chooses the path to fall down. Then Mario goes to some Clause gadget where it hits the item block from below to release a Star. I don't understand how the Variable gadgets are connected to the Clause gadgets so that the orientations (fall down vs. "from below") fit together?
In the Clause gadget, the Firebar is on the right side. However, in the proof framework, the Check path goes from right to left. How can Mario pick the Star as desired in this case?
Where should the Crossover gadgets be plugged in the proof framework? Are the circles between the paths from the Variables to Clauses crossover?


texts: Prove that NP is closed under karp reduction?

texts:
A complexity class $\mathbb{C}$ is said to be closed under a reduction if:

$A$ reduces to $B$ and $B \in \mathbb{C}$ $\implies$ $A \in \mathbb{C}$

How would you go about proving this if $\mathbb{C} = NP$ and the reduction to be the karp reduction? i.e.

Prove that if $A$ karp reduces to $B$ and $B \in NP$ $\implies$ $A \in NP$


texts: A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold?

texts:
I'm looking for a data structure that supports efficient:

Insertion of arbitrary integers.
Value lookup (given a particular value needle, return true if it's currently in the structure).
Removal of all values below a given threshold integer.

I suspect this can be with a self-balancing BST, with insertion and lookup both costing log(n) time. I think the removal operation can be done by pruning an entire subtree out, but I'm not sure this can be done in log(n) time while keeping the tree balanced. If we remove a very large subtree (say the left child of the root node), it seems like it would take basically rebuilding the entire tree, which is O(m log m) with m being the number of remaining nodes, and at any rate no less than O(m).
A cheaper approach would be to use a naturally-ordered self-balancing BST. For removal, we can just start at the smallest node, and keep removing (and rebalancing) until we run out of nodes or hit the threshold. This will cost O(m log n) where m is the number of nodes to be removed.
Bonus question: what if instead of removing below a threshold, we need to support removal of all nodes in a range between upper_bound and lower_bound?


texts:
When using A* (or any other best path finding algorithm), we say that the heuristic used should be admissible, that is, it should never overestimate the actual solution path's length (or moves).

How does an admissible heuristic ensure an optimal solution? I am preferably looking for an intuitive explanation.

If you  want you can explain using the Manhattan distance heuristic of the 8-puzzle.


texts: Does dependent type checkers need to store lambda parameter type in their core language?

texts:
"Core language" refers to the exported well-typed terms that can be evaluated (or reduced).

In the core language of MiniAgda, a dependently-typed language, the parameter type of a lambda is not stored anywhere. So does in Mini-TT and Agda.

However, Idris does store lambda parameter type in its core language.

I wonder do we need/needn't to store parameter type (or, under what condition do we need/needn't to store it)?
Because according the surface syntax of all these languages, they don't have lambdas with their parameters explicitly-annotated.
For Idris here's a link showing that Idris does not have lambda with type annotation.


texts:
We are given two grayscale images, one of which contains a large, mostly contiguous patch from the other one. The patch can be altered with noise, its levels may be stretched, etc.
Here's an example

We would like to determine the region of the image which was copied onto the other image.
My first instinct was to look at the local correlation. I first apply a little bit of blur to eliminate some of the noise. Then, around each point, I can subtract a gaussian average, then look at the covariance weighted by that same Gaussian kernel. I normalize by the variances, measured in the same way, to get a correlation. If $G$ is the Gaussian blur operator, this is:
$$ \frac{G(A \times B) - G(A)G(B)}{\sqrt{(G(A^2)-G(A)^2)(G(B^2)-G(B)^2)}}$$
The result is... not too bad, not great:

Playing with the width of the kernel can help a bit. I've also try correlating Laplacians instead of the images themselves, but it seems to hurt more than it helps. I've also tried using the watershed algorithm on the correlation, and it just didn't give very good results.
I'm thinking part of my problem is not having a strong enough prior for what the patch should be like, perhaps a MRF would help here? Besides MRF, are there some other techniques, perhaps more lightweight that would apply? The other part is that correlation doesn't seem to be all that great at measuring the distance. There are places where the correlation is very high despite the images being very visually distinct. What other metrics could be of use?


texts: Confusion over the complexity of parameter passing in merge sort

texts:
I'm working through CLRS on problem 4-2, which says the following:

  Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself.

  This problem examines the implications of three parameter-passing strategies:

  An array is passed by pointer. Time $ = \Theta (1)$.
  An array is passed by copying. Time $\Theta (N)$, where $N$ is the size of the array.
  An array is passed by copying only the subrange that might be accessed by the called procedure. Time $= \Theta(q-p+1)$ if the subarray $A[p \ldots q]$ is passed.

  Consider the recursive merge sort algorithm. Give recurrences for the worst-case running times
  of binary search when arrays are passed using each of the three methods above,
  and give good upper bounds on the solutions of the recurrences. Let $N$ be the size of the original problem and $n$ be the size of a subproblem.

For part (2), one solution I have seen is:

  $$T(n) = 2T(n/2) + cn + \color{red}{2N} = \color{blue}{4N} + cn + 2c(n/2) + 4T(n/4) = 8N + 2cn + 4c(n/4) + 8T(n/8) = \\ \qquad
     = \sum_{i=0}^{\lg{n}-1}(cn + 2^iN)
     = \sum_{i=0}^{\lg{n}-1}cn + N\sum_{i=0}^{\lg{n}-1}2^i
     = cn\lg{n} + N\frac{2^{\lg{n}} - 1}{2-1}
     = cn\lg{n} + nN - N
     = \Theta(nN) \\ \qquad
     = \Theta(n^2)$$

I don't understand where the $\color{red}{2N}$ has come from. The $2T(n/2)$ is the "conquer" part, and the $cn$ is the "combine" part, leaving the $\color{red}{2N}$ to be the "divide" part, but I'm not sure why it's $2N$ rather than just $N$, as you are only copying the $N$-length arrary over once.

Also, I don't understand where the $\color{blue}{4N}$ has come from (following the previous equality). Surely, $$T(n) = 2T(n/2) + cn +2N \\ = 2\underbrace{[2T(n/4) + c(n/2) + 2N ]}_{T(n/2)} + cn + 2N \\ = 4T(n/4) +2cn + 6N \ ?$$

Finally, am I right in thinking that the last equality holds because $N$ is some subset of $n$, so $n$ = $k N$ (for some constant $k$), so $T(n) = \Theta(n) \cdot  \Theta(N) = n \cdot  n = n^2$?


texts: Closure of Deterministic context-free languages under prefix

texts:
For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be:

$\text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\}$

ie. the set of all (not necessarily proper) prefixes of words in $L$. I know that if $L$ is context-free then pref(L) is context-free but if $L$ is deterministic context-free then is pref(L) deterministic context-free?

I am sure this is known but I cannot find the answer anywhere and it's not in Hopcroft and Ullman.


texts: Generation of pseudorandom floating point numbers on floating point vector DSP

texts:
I am working on a custom IEEE754 floating point vector signal processor with 64 cores and need to generate pseudo-random floating point numbers at high rate. The only numerical operation available to me is a vector wide floating point multiply-add. I cannot therefore use any of the conventional algorithms based on feedback shift registers, linear congruential operations etc. I cannot do any vector integer or bitwise operations... just a 32 bit IEEE754 vector floating point MAC on all 64 cores.

The only approach I have found that maps to the architecture is an iterated chaotic logistic map and related variants but I don't like these since they inevitably converge to a stable fixed point. They do have the advantage, however, of returning 64 pseudo-random numbers every clock cycle. Can anyone offer suggestions for a better algorithm suited to the architecture?


texts: Basic classical linear error correcting code for bits exercice (from Nielsen & Chuang)

texts:
I am learning about quantum error correction which is for a part based on classical linear error correcting code.

There is a very basic answer on an exercice I do not understand. Here is the problem (From Nielsen & Chuang, page 450, exercice 10.25)

  Let $C$ be a linear code.
  Show that if $x \in C^{\perp} $, then: $\sum_{y \in C} (-1)^{x.y} = |C|$
  Show that if $x \notin  C^{\perp}$, then: $\sum_{y \in C} (-1)^{x.y}=0$

I can show the first one using the definition, basically if $x \in C^{\perp}$ by definition $\forall y \in C$ I have $x.y=0$

Thus: $\sum_{y \in C} (-1)^{x.y} = \sum_{y \in C} (-1)^0 = |C|$ (where I assume that what is called $|C|$ is the number of element in the linear code which is $2^k$ if we want to encode $k$ bits an information right ?

However I don't understand the second one. Indeed, if $x \notin C^{\perp}$ then $x.y=1$ (We work with modulo 2 scalar product). And we have:

$$\sum_{y \in C} (-1)^{x.y}=\sum_{y \in C} (-1)=-|C|$$

Where is my mistake ?

In summary my questions are:

Do you agree with me that if we want to encode $k$ bits of info, then $|C|=2^k$
Why for $x \notin C^{\perp}$ $\sum_{y \in C} (-1)^{x.y}=0$


texts: Why does this mergesort variant not do Θ(n) comparisons on average?

texts:
A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm:

sort(array):
    if length(array) < 2:
        return array
    unsorted ← empty_array
    i ← 0
    while i < length(array) - 1:
        if array[i] > array[i + 1]:
            push(unsorted, pop(array, i + 1))
        else:
            i ← i + 1
    return merge(array, sort(unsorted))

(push(array, element) puts the new element at the end of the array and increases the array’s length by 1. pop(array, index) removes the element at that index from the array, moving all the elements at greater indices and decrementing the array’s length, and returns the removed element. merge is the same as in mergesort.)

Instead of simply splitting the array in the middle like mergesort, it splits it so that one resulting array doesn’t need to be recursively sorted. Let $n$ be the length of the array to be sorted. Applying the Master Theorem gives us

$$\begin{align*}
    T(n) &= T(n / b) + \mathrm{splitComparisons}(n) + \mathrm{mergeComparisons}(n) \\
         &= T(n / b) + (n - 1) + n \\
         &= T(n / b) + 2n - 1\,,
\end{align*}$$

so $f(n) = 2n - 1$ and $a = c = 1$ in the statement of the Master Theorem.

$b$ is one over the probability that an element is greater than the next element and will go into the array to be recursively sorted. For example, if there's a 25% chance that array[i] > array[i + 1] (for all i), $b = 4$. $b$ is clearly greater than $1$, since the length of unsorted array grows smaller with every recursive call, so taking the logarithm with base $b$ of $1$ will always give us $0$, which is less than $c$. Then $T(n) = \Theta(f(n)) = \Theta(n)$.

But that can’t be true, so the Master Theorem isn't applicable for some reason; I suspect because $b$ isn't constant, but I don’t know how to prove that. The worst case of the sorting algorithm obviously requires a quadratic number of comparisons and the best case linear, so by analogy with bubblesort, insertion sort, etc, I’m guessing this algorithm also makes a quadratic number of comparisons on average.


texts: How many possible assignments does  a CNF sentence have?

texts:
I'm having some trouble understanding the following:

When we look at satisfiability problems in conjunctive normal form, an underconstrained problem is one with relatively few clauses constraining the variables. For eg. here is a randomly generated 3-CNF sentence with five symbols and five clauses. (Each clause contains 3 randomly selected distinct symbols, each of which is negated with 50% probability.)

(¬D ∨ ¬B ∨ C) ∧ (B ∨ ¬A ∨ ¬C) ∧ (¬C ∨ ¬B ∨ E) ∧ (E ∨ ¬D ∨ B) ∧ (B ∨ E ∨ ¬C)

16 of the 32 possible assignments are models of this sentence, so, on an average, it would take just 2 random guesses to find the model.

I don't understand the last line- saying that there are 32 possible assignments. How is it 32? And how are only 16 of them models of the sentence? Thanks.


texts: Fast generalised suffix array construction: lower than O(n^2 log n)

texts:
There is a lot in the literature about linear time constructions for suffix arrays; DC3, radixSA46, and more...

However, these, I believe, are only for suffix arrays; with a single string input.
Are there fast algorithms for generalised suffix arrays, which have multiple string inputs?

for example

strings = ["maps$", "maps$, "mops$"]

GSA = createGenSuf(strings)

for (suffix in GSA) {
    print suffix;
    print strings[suffix]
}

where the output would be:

(0,4)
$

(1,4)
$

(2,4)
$

(0,1)
aps$

(1,1)
aps$

(0,0)
maps$

(1,0)
maps$

(2,0)
mops$

(2,1)
ops$

(0,2)
ps$

(1,2)
ps$

(2,2)
ps$

(0,3)
s$

(1,3)
s$

(2,3)
s$

I'm currently using the naive O(n^2 * log n) merge sort. Where n is the number of characters. There must be something faster available but i'm having a hard time identifying it in literature.

Regards to all who read, and anyone who offers a better algorithm


texts:
I want to find a comparison sorting algorithm that can almost sort a set of data, using the least comparisons possible.
What I mean by "almost" is that if the perfectly sorted data is $[x_1, x_2, …, x_n]$ and the almost sorted data is $[x_{i_1}, x_{i_2}, …, x_{i_n}]$, then $\forall j \in [\![1, n]\!], |i_j - j| \leq C$, $C$ being a parameter of the algorithm.
I want to emphasize that I want to minimize the number of comparisons. Other operations don't matter in the complexity. I would like to know if a number of comparisons next to $\frac{n\log_2 n}{C}$ can be possible.
In practice, I have to work with $n \simeq 1000$ and $C \simeq 10$ and only the comparisons are done by a human.
Are there any algorithm of the kind? Could I have some insight about it? Thanks.
EDIT: I got two ideas to almost sort:

The first one is to quicksort the array, and stop when I have to sort a sub-array of $\leq C$ data. The best case scenario requires roughly $\sum\limits_{k=0}^{\log_2(n/C)}2^k\frac{n}{2^k} = n\log_2(n/C)$ comparisons.
The algorithm is correct because sub-arrays are relatively sorted, and since they are of size $\leq C$, a value can't be farther than $C$ from its sorted position. The problem is that the worst case scenario is still in $\Omega(n^2)$ ;
The second idea is to sort using an insertion sort with a dichotomic search, and stop the search when the bounds of the search are distant of at most $C$. With this method, I get roughly $\sum\limits_{k=1}^{n-1}\log_2(k/C) = \log_2((n-1)!) - n\log_2(C)\simeq n\log_2(n/C) - n$ in the worst case, which is better than the previous algorithm, but I am not quite sure that the array will be $C$-almost sorted.

EDIT 2: I found that the second algorithm is not correct. If, during the first insertion, $x_n$ is put before $x_1$, then their relative order will not change during the rest of the execution, therefore one of them will be farther than $C$ from its sorted index if $n > 2C$.


texts: Algorithm for identifying polygons (set of points)

texts:
Are there any known algorithms for uniquely identifying some set of points despite scaling, moving and with some amount of threshold?

I have an "ideal" set of points with coordinates and I need to check if other set matches the ideal one. Other set could be rotated, scaled or distorted a bit (points could be placed with slight offset).

All sets have one common property: there are 2 points located farthest apart. This can be used to, at least, negate rotation. We do know angle (45deg) that line between farthest points create with axis, and we do know needed distance between them.

I've tried following algorithm:

Rotate "other" set to some point (so that farthest points create
line that is 45 degrees to "x" axis);
Scale set so farthest points distance = "ideal" distance;
Use sort of GeoHashing algorithm to get point hash with some accuracy (like threshold).

But that approach gave nothing. "GeoHashing" produces semi random results and probably not suitable for 1000x1000 calculations. And using geometric operations furthermore reduced accuracy (initial distortion of points + inaccuracy of some geometric methods).

EDIT:

I want to add some details to it:

Points set contains only 5 points (including those distant ones);
There could be several "ideal" point sets and I want to find if given set matches something (that's why I used GeoHash);
Basically task is to find matching polygon/set of points with given accuracy. If points do not match exactly (not located in the same coordinates), but are pretty close to ideal location (like +-2) it's a match.


texts: Sequence of total languages whose limit is turing complete

texts:
First let me clarify what I mean by a number of things.
A language is a decidable set of natural numbers which encode functions from natural numbers to natural numbers $ \mathbb{N} \to \mathbb{N}$. A language is said to be total if it only encodes total functions from naturals to naturals. A language is turing complete if it can encode all functions from natural numbers to natural numbers that a universal turing machine can. Because I can make a turing machine than infinitely loops on some inputs I can encode a non-total function with a turing machine. So being turing complete implies being non-total.

An interpreter of a language $L$ is a function $I_L : \mathbb{N} \to \mathbb{N}$ such that $n \in \mathbb{N} \mapsto I_L(pair(p, n))$ is the same function that $p$ encodes forall $p \in L$. A nice theorem says that if a language is total, it cannot encode such a function.

A while back I was wondering "is there a language that could only be interpreted by a turing complete language". Now the answer seems obvious to me (thanks to some help from stack exchange); no, no such things exists. You can always just add an interpreter for the language to get a total language that can't be interpreted by the previous one.

Clearly this gives raise to a sequence of total languages. Namely the first language you pick, then that language plus its interpreter, then that language plus its interpreter, etc...

But I have no reason to believe that this sequence is even particularly useful. I have some vague intuitive sense of a the limit of this sequence but I can't seem to pin down what a limit of a sequence of languages is. I do not think the limit of this sequence is turing complete. I do think the limit of this sequence is a partial language however. Namely, it seems the limit language should be able to interpret itself (perhaps this is not a good intuition?).

Does such a notion of a limit exist? If it does is there a sequence of total languages whose limit is turing complete? If such a limit exists is it computable? If it is computable, why does no one use such a language?

Bonus: Since we are talking limits anyhow. Is there a topology of languages to be considered here?


texts: On computing the factor-free basis of a regular language

texts:
The problem is as follows.

Background: Given an alphabet $\varSigma$. If $u,v,w,x \in \varSigma^*$ and $w=uxv$ then $x$ is a factor (substring or infix) of $w$. A language $L$ is factor-free if, for all distinct words $x, y \in \varSigma^*$, $x \in L$ and $y \in L$ imply that $x$ and $y$ are not factors of each other. Given a regular language $L$, we define $basis(L)$ as $L' \subseteq L$ such that $L'$ is factor-free and for every word $x \in L$ there exists a word $y \in L'$ such that $y$ is a factor of $x$.

Question: Is $basis(L)$ efficiently computable, given (say) a DFA for $L$? If so, do you have any ideas about the algorithm that computes it?

Example: Consider the language $L=\{ab,abab,ababab,abababab,\ldots\}=\{(ab)^i|i>0\}$. Then, $basis(L)=\{ab\}$.

Let me give you my insights on the subject, it may help.

It has been proven that checking factor-freeness is tractable for regular languages1.

Also, in a trivial way, $L=basis(L)$ if $L$ is factor-free. This leads to the fact that $basis(L)$ is not always finite. Because for an infinite factor-free language the basis is also infinite. Here is an example from the Handbook of Formal Language Theory (vol. 1, p. 19): $L=\{ba^ib | i > 0\}$.

For finite languages, it seems that a basis always exists because a language $L$ is either factor-free thus $basis(L)=L$ or not factor-free. The latter necessarily means that $L$ contains a sublanguage $L'$ for which some words are factors of each others, consequently $basis(L)=basis(L') \cup (L \setminus L')$.

1 Han YS, Wang, YJ , Wood, D. Infix-free regular expressions and languages.  International journal of foundations of computer science. 2006.


texts: Using 4-SUM to improve Subset Sum $O(2^{n/2})$ runtime

texts:
I read k-Sum $k \geq 3$ can be solved in $\approx O(n^{k/2})$

If this is right, why do not have a subset sum solver with a time complexity $O(2^{n/4})$ or better?

That is, enumerating all the subsets from 4 splits, then apply 4-sum to find if some of the four partial lists add up to the target value?


texts: How to wiggle sort an array in linear time complexity?

texts:
The wiggle sort is nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ...

For an input: nums = [1, 5, 1, 1, 6, 4], the expected output is [1, 4, 1, 5, 1, 6] and there can be many other possible outputs satisfying the aforementioned criteria.

I realised that the problem has a pattern:
nums[1] will be greatest among nums[0:3], nums[3] will be greatest among nums[3:6],...

So, I targeted at getting the next greatest element. This made me implement the heap:

import heapq

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums_heap = []
        for num in nums:
            heapq.heappush(nums_heap, -1*num)
        i = 1
        while i < len(nums):
            nums[i] = -1 * heapq.heappop(nums_heap)
            i += 2
        i = 0
        while i<len(nums):
            nums[i] = -1 * heapq.heappop(nums_heap)
            i += 2

However, the time complexity of my solution is O(n) along with O(n) space complexity. I want to solve this in O(1) space complexity and that would require me to not use heap(extra space).

How to do that?

The complete question is also posted here.


texts:
How can we prove that the language $COF=\{M\mid L(M)\text{ is cofinite}\}$ is m-complete for the class $ Σ_3^0$ ?
I have shown that $COF\inΣ_3^0$ but I can't prove that $COF$ is m-hard for $Σ_3^0$ which means that every other problem $L\in Σ_3^0$ satisfies $L\leq_m COF$.


texts: Separate arithmetic codes closed under addition

texts:
For error detection purpose I am looking for separate arithmetic codes which are closed under integer addition.

By separate, I mean the code word $C$ for message $x$ is a tuple $(x,f(x))$ where $f(x)$ is the redundancy part. In contrast to that, a non-separate code word $C$ would be $f_2(x)$ where $f_2$ encodes the word to a redundant representation such as e.g. AN-codes.

So far, I know (multi) residue codes. I found another form of residue codes in http://mark.bu.edu/papers/192.pdf where $f(x) = x^2 \text{ mod } p$ but I haven't found any others. Can someone point me to information to other codes of that type?


texts:
I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence:

$$T(n) = 3T(n-1) + 2, \quad\quad T(1) = 1$$

My work at solving it:
$$\begin{align*}
T(n) &= 3^2T(n-2) + 3*2 + 2 \\
     &= 3^3 T(n-3) + 3^2*2+ 3*2 + 2 \\
     &= 3^4 T(n-4) + 3^3*2 + 3^2*2 + 3*2 + 2 \\
    &= \dots \\
  &= 3^k T(n-k) + 3^{k-1}*2+3^{k-2}*2 +\dots+3*2+2 \\
 &= 3^k + 3^{k-1}*2+3^{k-2}*2 +\dots+3*2+2 \\
&= 3^k +[\sum_{i=1}^{k-1} 3^i*2 ] + 2
\end{align*}$$

where $k = n - 1$.

I guess the Big O would be exponential since the above would be less than $3^n$ which is $O(c^n)$?

I am stuck on how to finish this and find out what the time complexity is in Big O notation.


texts: Universality of $(+, \oplus)$ over $\mathbb{Z}_2^n$

texts:
Let $\mathbb{Z}_2^n$ be the field of bitvectors of length $n$ and define the xor operator $\oplus$ and the addition operator $+$ over this field, with $+$ having the usual overflow semantics (take addition modulo $2^n$).
Is it possible to express any mapping $f: \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$ entirely in terms of $\oplus$ and $+$? It seems like it might be possible due to the nonlinearity of $+$.

For instance, if we were given $n=2$ and that $f(0) = 3, f(1) = 1, f(2) = 3, f(3) = 1$, then we could construct $f$ as $f(x) = x\oplus(x+3)$.


texts: can anyone explain What modifications should be done to the Chandy–Lamport snapshot protocol so that it records a strongly consistent snapshot (i.e., all channel states are recorded empty).


texts:
I was wondering what kind of groups could be constructed with Lambda terms, where the group operation is application? For example, $a* b =c$ would mean $ab\to_{\beta}^{*} c$. Is this even possible?

EDIT: I don't think groups are possible, but I did find a group of sets which are closed under application:

Let $I_0=\lambda x.x$ and $I_{n+1}=\lambda y.I_n$, where $y\not\in\text{bv}\left(I_n\right)$.
Then $S_n=\bigcup_{i=0}^{n}\left\{I_i\right\}$ is closed under application for all $n\in\mathbb{N}$.


texts: Origin of using ">" to represent child in a tree

texts:
What are the earliest known uses of the "greater than"/"chevron" symbol (>) to denote a parent-child relationship in a tree structure? i.e. parent > child

e.g.

CSS Child Combinator (initial definition)
Breadcrumbs


texts: Can the solution to a POMDP be found using linear programming?

texts:
It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is:

$$min_{V(x)} \sum_x \alpha(x)V(x)\\
\text{subject to: } V(x) \ge R(x,a) + \gamma\sum_{x'}P(x'|x,a)V(x')\text{ for all }x\in X, a\in A$$

where $V(x)$ is the value of starting at state $x$ (note that $V(x)$ is the decision variable), parameters $\alpha(x)>0$ for all $x$ which are termed state relevance weights and are typically normalized, that is $\sum_x\alpha(x)=1$ (the solution of the above LP is actually, surprisingly, independent of the exact choice of $\alpha$), $R(x,a)$ is the reward obtained in state $x$ when action $a$ is taken, and $P(x'|x,a)$ is the probability that transition to state $x'$ when we take action $a$ in state $x$.

Question: does anyone know of a similar linear programming formulation for solving partially observable Markov decision processes (POMDPs)?


texts: Reference requested for a prime sieve variant

texts:
Apologies for this edit (8.13).  I encourage those interested in the math side of this variant to view the MathOverflow post mentioned below, and contact me at that forum.  This version is an attempt to find a CS reference.

I am researching mathematical properties of a variant of the sieve of Eratosthenes.  Has anyone seen this particular variant before in the computer science literature?  If so, can I have a reference please?

The mathematical version of this question for those interested has been asked at https://mathoverflow.net/q/243490 with some further followup questions.  Some time has passed without an answer containing a reference, so I post here.

Below is the algorithm for the variant implemented in an AWK fragment:

for (n=1;  (n++) < Search_Limit;  S[m]=p ) {
       if ( (m=n) in S) { for (p=S[m]; (m+=p) in S ; ) { } }
       else m+=(p=n) }. #### n is prime

This uses an associative array S, with keys which turn out to be composite numbers and values which turn out to be a prime dividing the numerical value represented by the key.  When you run it, S[15] gets the value 3 and S[35] gets the value 5, for example.

I have looked at O'Neill's 2009 paper about a Haskell variant, a blog post from January 2011 of van Emden which refers to a 1972 paper of Dijkstra which has a version that anticipates this variant but does not implement it, and a 2015 paper of Sorenson which mentions a hopping sieve of Bennion from the 1970's, which is close to this variant but not quite. (Bennion's version has p "push" a value q out of S[m], so S[m] gets p and the prime q ends up in S[m+q]; this version has p jump over filled slots in S and finds an empty slot to land in.). None of these quite fit this variant.

Even finding this somewhere on the web (by someone other than me) would be useful. Do you know where?

To respond to a comment (as I can't comment on my own post yet):  I am willing to provide a different implementation or explanation if needed. The code above is similar to C syntax, with the exception of "in".  'expr in S' returns true if there is a key with value of expr and that key is in the array. Once the assignment statement S[m]=p is executed, (m in S) returns true.  The MathOverflow post linked above contains a pseudocode version of the variant.

Here is another implementation which depends on the operation "k in A" returning true if the associative array has an entry with key k, and returns false otherwise.  As above, if A[35]=5 occurs, then k=35 occurs, then (as no delete operation is used) (k in A) is an expression that will evaluate to true.  A feature of this variant is that no key is used in an assignment more than once, and is used for reference less than log(Search limit) times when Search limit is not small.

For n = 2 to Search limit  step 1
      m = n
      p = n
      If (n in S)
            p = S[n]
            while (m in S) m = m + p
      else m = m + p
      S[m] = p

I hope readers understand the "for ... step ..." construct.

Also here are some references:

O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 09 Oct 2008 doi:10.1017/S0956796808007004
https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

A blog post by Van Emden entitled "Another Scoop By Dijkstra?" at

https://vanemden.wordpress.com/2011/01/15/another-scoop-by-dijkstra/

An ArXiv posting by Jonathan Sorenson on two compact incremental sieves, which mentions Bennion's sieve:

https://arxiv.org/abs/1503.02592

I hope these links help others in considering this question.


texts:
I have computed the average code length using the Huffman encoding. Now, I am asked to compare the average code length with Absolute limit but I ain't sure about the absolute limit here is :(
Could someone assist me here with the what the absolute limit ??


texts: Run time of product of polynomially bounded numbers

texts:
Let $M$ denote a set of $n$ positive integers, each less than $n^c$.

What is the runtime of computing $\prod_{m \in M} m$ with a deterministic Turing machine?


texts: Secondary Storage in Von Neumann Achitecture

texts:
For an assignment, I need to draw a diagram of Von Neumann architecture, and explain each part of it.

All the diagrams and explanations I've seen have a distinct "Memory" block that holds both the code and the program data of running processes. What I can't find information on however is if this memory refers to only primary memory (like RAM), or if it also includes secondary memory (like a SSD or HDD).

Does Von Neumann Architecture specifically refer to only primary memory, or does it also include secondary storage?

I'd also like to know if I'm using any terminology incorrectly above.


texts:
I work on a web project that handles region based user submissions.  We currently have about 50 regions, some receive a large number of submissions, some receive next to none.

We also ingest case data for these submissions from a system, again some regions may supply lots of data, others not so much.

The number of cases ingested and submissions will differ during a weekday and a weekend, and holiday periods (e.g Christmas) will be quieter.

I'm wondering what algorithm I can use to detect and alert on an unexpected variance in the data?  E.g if we've been receiving 100 submissions for region X each day, then suddenly that number halves.  But that number may be low anyway during the weekend.

I was thinking about possibly alerting on the intersection of two moving averages - maybe a 7 day and a three day, but that might be too slow / unresponsive.  Another option may be detecting a %age variance based on the figures for the same day for the past few weeks. What is the best solution?


texts: Difference between fully-reduced BDD and quasi-reduced BDD

texts:
I am trying to figure out difference between fully- and quasi-reduced BDDs. I have read a lot of material but still it is not very clear. As I am trying to figure out the quasi reduced version for union between two BDDs.
The algorithm for union between two fully-reduced BDDs is

bdd Union(bdd p, bdd q)
   //fully-reduced version
   local bdd r;
1  if p=0 or q=1 then return q;
2  if q=0 or p=1 then return p;
3  if p=q then return p;
4  if Cachecontainsentry⟨UnionCODE,{p,q}:r⟩ then return r;
5  if p.lvl = q.lvl then
6    r ← UniqueTableInsert(p.lvl, Union(p[0], q[0]), Union(p[1], q[1]));
7  else if p.lvl > q.lvl then
8    r ← UniqueTableInsert(p.lvl, Union(p[0], q), Union(p[1], q));
9  else since p.lvl < q.lvl then
10   r ← UniqueTableInsert(q.lvl, Union(p, q[0]), Union(p, q[1]));
11 enter⟨UnionCODE,{p,q}:r⟩inCache;
12 return r;

I have read the paper Binary decision diagrams in theory and practice by Rolf Drechsler, Detlef Sieling for basics of BDD, and Data Representation and Efficient Solution: A Decision Diagram Approach by Gianfranco Ciardo for quasi-reduced and fully reduced definitions. Then I read more papers with more or less same description of quasi- and fully-reduced BDDs. In the former paper I mentioned the authors talk about reduced BDDs, I am not clear whether these BDDs are fully reduced. Quasi-reduced BDDs has no variable skipping so how come they are reduced when they have redundant nodes. I am pretty confused between BDD, quasi-reduced BDD and fully-reduced BDD. Yes, I am trying to find the difference between union algorithm for quasi-reduced and fully-reduced, for this I need to look at the quasi-reduced version of union algorithm.

I figured out an algorithm for union of two quasi reduced BDDs p and q resulting in r.

bdd Union(bdd p, bdd q)
  local bdd r;
1 if p=0 or q=1 then return q;
2 if q=0 or p=1 then return p;
3 if p=q then return p;
4 if Cachecontainsentry⟨UnionCODE,{p,q}:r⟩ then return r;
  //p.lvl = q.lvl in case of quasi reduced BDDs
5 r ← UniqueTableInsert(p.lvl, Union(p[0], q[0]), Union(p[1], q[1]));
6 enter⟨UnionCODE,{p,q}:r⟩ in Cache;
7 return r;

Since there is no variable skipping, p.lvl is always equal to q.lvl. I have a question about this algorithm.

If I want to implement Xor or Xnor for quasi-reduced BDDs, can it be done the same way as union or should I implement the expression pq' + p'q where q' = !q.


texts:
Say I have 2 Gaussian sources X and Y. They are generated with mutivariate gaussian distribution with mean = [0, 0] and co-variance = [1, 0.9;0.9, 1] with 100 observations
That is: means is zero and both X and Y are correlated with 0.9 and in total there are 100 variables for each of them.

I wanted to convert these correlated Gaussian variables X and Y into Binary, such that total bits for X and Y should be near to differential entropies H(X) and H(Y). This could be achieved using some best source coding schemes. I tried to find open source LZW compression code. But couldn't find one for integers (mostly are based for text compression)

But the point is after converting them into binary and arranging them as long codeword, I want their Hamming distance as small as possible. How to do that?

Because they are correlated, their hamming distance should be less.I am not able to achieve this. any help would be appreciated..

Edit part:

[1] For instance, 255≈256 but 011111111 and 100000000 are as different. This can be solved by using gray coding, then it will be having hamming distance of 1.

[2] I have tried using lloyd max quantizer(say 4 bit) on gaussians and then converting their indices into bits(gray coding). But still hamming distance is very high.

[3] 100 observations are just an example.(not significant)

[4] H(x) is the differential entropy for X and it is mathematically equal to(1/2)(ln((2*pi*e)(det(cov_matrice)))).

Thank you for all responses


texts: Prove that a language is undecidable by reducing HALT to it

texts:
Let

$L = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} \textrm{x is the only string accepted by}\mathrel{}M_\alpha \right\}$

and

$HALT = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} M_\alpha \mathrel{} \textrm{halts on input x} \right\}$

How can I prove that $L$ is undeciable by reducing $HALT$ to it?

I appreciate the fact that similar proofs use the fact that if we could decide $L$, then we could compute $HALT$ as a way to prove contradiction, but I don't understand how $L$ and $HALT$are related and how we can prove that one is not decidable ($L$) by saying that, by nature, the other one ($HALT$) is not.


texts: Is there an algorithm or shortcut for continually updating and summing sub-sections of arrays?

texts:
Let's say I have an NxN array if integers. I want to continually update it, but also continually query for the sum of an arbitrary sub-section. So example would be as follows:
We start with a 3x3 array of all 0s.
Operations:

update 1,1 to 3
update 1,2 to 1
update 0,0 to 2
update 2,2 to 6
print sub-section starting at 1,1 going to 2,2 (should print 10)
more updates...
more queries...

The array looks like this at the time of first query:
2 0 0
0 3 0
0 1 6

I want to do this for much larger arrays, and much more queries in a reasonable amount of time. I believe less than O(N^2) per query is possible. Any ideas?
EDIT: I'm asking this because Hackerrank has several of these types of questions and I was banging my head against a wall trying to come up with a strategy.


texts:
I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph:

  We will first of all briefly review the LR(1) parsing and parser construction algorithms. In this paper the symbols of a grammar are denoted by Roman letters while Greek letters are employed to denote strings. $\epsilon$ is the null-string. $\alpha \Rightarrow^* \beta$ means $\beta$ is derivable from $\alpha$ (which is considered to be true if $\beta = \alpha$). By $THEADS(\alpha)$ we refer to the set $\{b \mid b \text{ is the head of a terminal string derivable
from $\alpha$}\}$.

From what I can see $THEADS$ here is what is usually called $FIRST$. Is this correct? Does $THEADS$ predate $FIRST$?


texts: Find subset with minimal sum under constraints

texts:
Let $M$ be a finite set of even cardinality. Define $C=\{\{a,b\}:a,b \in M, a \neq b\}$ the set of all pairs over $M$. Let $w:C \rightarrow \mathbb{R}^+_0$ be a function.

Now find $C' \subset C$ with the following constraints:

$$
\bigcup C' = M \\
\forall x,y \in C': x \cap y = \emptyset \\
\sum_{x \in C'}w(x) \text{ minimal}
$$

In words: Find a subset $C'$ of pair-wise disjunctive pairs over $M$ that covers $M$, with the sum of these pairs being minimal. Any element of $M$ must appear in exactly one pair.

I could not find an efficient algorithmic solution, and I also fail to relate this to any other known (optimization) problem. I was thinking of the subset sum problem, but I don't see any relation.

So the questions is: Can you find an efficient algorithm to find $C'$? A good approximation might also be sufficient. If not, can you reduce this to any other known computer science problem?


texts: Algorithm for automatic construction of natural deduction proofs

texts:
I was wondering if there exists any algorithm for automatic construction of nautral deduction proofs. I'm interested in propositional logic and first order logic.

If there is no algoritm, can you provide some proof of this fact?

PD0: I'm not interested in any page for solving these kind of problems. My question is more theorical.

PD1: This is not homework, just personal interest.


texts:
I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ iff they are vertex cover of $G'$.
I understood that a polynomial algorithm exists, it's mean without finding the vertex cover of $G$, but I found only a non-polynomial one.


texts: Context free grammar for a palindrome of even length + cc

texts:
Suppose the language is $\{AA^R: A \in \{a,b\}^*\}$.

I know that I can make a context free grammar for it:

$$S\to aSa \mid bSb\mid\epsilon$$

Now if the language was $\{AA^Rcc: A \in \{a,b\}^*\}$, so the same thing but with $cc$ at the end. Would the following context free grammar work?

$$\begin{aligned}
S&\to aS \mid bS\mid\epsilon\mid T\\
T&\to  cc\\
\end{aligned}$$

I think it works cause you have the options to make the original string and its reverse, but unlike in the first example, the grammar doesn't fit how the output is suppose to be and so you kind of have to remember what the original string was to make the reverse and then append $cc$ at the end. But then I remember that automata doesn't have memory of previous states so what would be correct grammar?


texts:
I have this question I found regarding n-gram modelling in the textbook Speech and Language Processing:

Suppose we didn't use the end symbol </s>. Train an unsmoothed bigram grammar on the following corpus without using the end-symbol </s>.

<s> a b
<s> b b
<s> b a
<s> a a

Demonstrate that your bigram model does not assign a single probability distribution across all sentence lengths by showing that the sum of the probability of the four possible 2 word sentences over the alphabet {a, b} is 1.0 and the sum of the probability of all possible 3 word sentences over the alphabet {a, b} is also 1.0.
Note:
<s> means beginning of sentence.
</s> means end of sentence.
Speech and Language Processing, Daniel Jarafsky and James H. Martin, 3rd ed., Exercise 3.5, p.55

My attempt was:
Two word sentences:
P(a | b) = count(b a) / count(b) = 1 / 4
P(b | a) = count(a b) / count(a) = 1 / 4
P(a | a) = count(a a) / count(a) = 1 / 4
P(b | b) = count(b b) / count(b) = 1 / 4

sum = 1
but when I get to 3 word sentences:
P(a | a, a) = count(a a a) / count(a) = 1 / 64
Now, you get 8 three word sentences which sums to 8 / 64
This is where I am getting lost. I need some pointing in the right direction.


texts: CISC and RISC - synchronous and asynchronous

texts:
I have two opposing ideas. I think that all the instructions in a RISC take the same time what makes me believe RISC is associated with synchronous.

At the same time i think that CISC should be synchronous and RISC should be asynchronous.

Can you tell me if RISC is associated with asynchronous and CISC is associated with synchronous? Why?


texts:
so I have this code:

for (int i=1; i < n; i=i*5)
      for (j=i; j < n; j++)
        sum = i+j;

And I'm wondering, what's the time complexity of this for loop?

To start off, I know the first line is logn base 5, with an additional check to exit out of the for loop.

Then, for the second line, I have the following:

i = 1
    j = 1, 2, 3,…, n        (n-5^0)+1
i = 5
    j = 5, 6, 7, …, n       (n-5^1)+1
i = 25
    j = 25, 26, 27,…, n     (n-5^2)+1
…
i = n
    j = n                   (n-5^k)+1

But now, I'm stuck. Any help is appreciated.


texts: minimum moves to be made to get out of convex hull

texts: Given a convex hull in $XY$ plane. and we have $n$ points sitting inside it. In one move we can move all the points to right by $1$ or move all the points to up by $1$. what are the minimum number of moves that are required to get all the points outside the convex hull?


texts: Finding coprimes closest to a certain target

texts:
Given an input $m$, I am trying to find an algorithm that will give me the number $p$ that is closest to $\tfrac47 m$ and co-prime with $m$.

Where $m$ is odd, I have no problem producing an outcome close to the target, simply by squaring $2$ until close enough to the target.

When $m$ is even, I have a bit more trouble. I have tried a few different methods with no success. I have tried starting with $p = 3$, then multiplied $p\cdot\mathrm{gcd}(p-1, m)$ until $p$ and $m$ share all factors (in other words, until $\mathrm{gcd}(p-1, m) = 1$). This eventually finds a coprime, but there is no guarantee that it is close to the target, and I'm not sure how to operate on the number from here to get another coprime closer to the target.

The algorithm needs to be able to handle massive numbers with hundreds of digits, so it needs to be pretty efficient.

I'm not sure if I'm missing a necessary fact about coprime numbers, or if I'm just misinterpreting the info I have. Can anyone point me in the right direction? Maybe a fact about coprime numbers that I'm missing?


texts:
A graph is dense when |E| (edges) is closest to $|V|^2$.
A graph is sparse when |E| is closer to $|V|$.

What does it mean to take the magnitude of the vertices? Secondly, I am having a hard time conceptualizing why the above two rules are true.

Also can someone elaborate on why if a graph is sparse, it should be represented with an adj list and why if it is dense, it is best to use an adjacency matrix instead?


texts: We know that the lower bound is the minimum amount of work needed to solve a problem.  So for a given problem say x it has the best algorithm ( the most efficient algorithm to solve this problem ) say algorithm y, then the lower bound efficiency calculated  from this algorithm y is the least time this problem x can be solved through . So why do we calculate the lower bound efficiency for this algorithm on the worst case input ? why not on the best case input ? I mean lower bound is the minimum amount of work which therefore occurs on the best case scenario . Every time I see a decision tree algorithm problem to solve the lower bound of some sorting algorithm , the usual word is always mentioned "the worst case lower bound is blah blah blah" which confuse me so much ! Someone please fix my understanding :( .


texts: Relation between covering radius and columns of parity check matrix

texts:
Let $C$ be a $[n,k]$ linear Code over  $\mathbb{F}_q$ .

I want to show that each vector of $\mathbb{F}_q^{n-k} $ is written as a linear combination of $m$ columns of $H$ iff $\rho \leq m$.

I have thought the following:

$$ d(C)=\min \{ d \in \mathbb{N} | \text{ there are d linearly dependent columns of  H}\} $$

So $H$  has $ d-1 $ linearly independent columns , so each vector of $\mathbb{F}_q^n$ can be written as a linear combination of these columns.

But what can we say about the vectors of  $ \mathbb{F}_q^{n-k}$?


texts: Closure of regular languages under deleting a 1 from each even run of 1s

texts:
Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using closure
  properties for the class of regular sets.

Current Approach:

For the first part, using a machine construction, I was thinking that you take a simple FA that accepts only strings with an odd number of 1's (let's call this language $S$). This would be the simplest way of forcing strings in $R$ to have blocks of 1 of odd length. Then I would have some sort of $\epsilon/1$ transition to the original machines states where I would see if a string $x$ that is in the language $S$ would also be in $R$ if I were to add a 1 to any odd block of 1s.

I am unsure of how to describe that using the 5-tuple, $M = (Q, \{0,1\}, \delta, q_0, F)$, or if my methodology is correct. Any advice on where I should go and how I might prove closure in the two different ways is welcome.


texts: Why can't fibers utilize multiple processors?

texts:
It seems that the distinction between fibers and threads is that fibers are cooperatively scheduled, whereas threads are preemptively scheduled.  The point of the scheduler seems like a way to make an otherwise serial processor resource act in a parallel way, by "time-sharing" the CPU.  However, on a dual-core processor with each core running its own thread, I assume there's no need to pause the execution of one thread for the other to continue because they're not "time-sharing" a single processor.

So, if the difference between threads and fibers is the way they are interrupted by the scheduler, and interrupting is not necessary when running on physically separate cores, why can't fibers take advantage of multiple processor cores when threads can?

Sources of confusion:

..mainly wikipedia

http://en.wikipedia.org/wiki/Fiber_%28computer_science%29

  A disadvantage is that fibers cannot utilize multiprocessor machines without also using preemptive threads

http://en.wikipedia.org/wiki/Computer_multitasking#Multithreading

  ...[fibers] tend to lose some or all of the benefits of threads on machines with multiple processors.


texts: A question on instruction executing speed

texts:
I am new to computer science, so excuse me if the question is inappropriate or sounds absurd to you.
In the textbook, it says that a typical laptop can execute 1 billion instructions per second. Therefore, I thought that if I wrote a never-ending piece of algorithm, it would generate tons lines in the program counsel after running it for 10 seconds. Taking into account the time it needs to convert to machine instructions, and the fact that other programs needed to be executed as well, the number I expected was some where about one million of instructions per second and thus 10 millions per 10 second.
I tried to run something like this:
        While 1+1=2:
               Print(0)

To my surprise, I found that the print instruction had been executed for less than 4,000 times within 10 seconds. I know that my original estimation was not meant to be accurate but I was not expecting the speed to be this slow. I think maybe the read-writing speed of my ssd was the major drawback. I know that sending instruction to the screen is even slower, but that should not affect the CPU's performance.
So, here are my questions:

What are the major factors that slow down the speed?

Are there any other factors that I overlook?

Is there a way to know exactly or make reasonably accurate estimation of the Python code execution rate?

And are there any suggestions to speed up the execution rate?

Even if it takes time to send instructions to the monitor, the processor can still utilize the gap in between to execute other instructions. So, does that exclude slow I/O speed as a drawback?

If the hidden layer between me and the machine already figures out what to do in the beginning, is it going to repeat the same instruction without executing extra instructions?

It is possible to have the processor focus on a piece program without executing any other program at all?

Thank you for your help in advance.


texts: Parenthesizing a product using dynamic programming

texts:
Here is a problem that I've been given to solve in time $O(n^2|\Sigma|)$.

  Given an alphabet $\Sigma$ and the product of every two elements in this alphabet (i.e., an arbitrary mapping $\cdot\colon \Sigma^2 \to \Sigma$), find an algorithm that determines whether we can parenthesize the expression $x_1 \cdot x_2 ֿ\cdot \cdots \cdot x_n$ (where $x_1,\ldots,x_n \in \Sigma$) so that the product equals a given element $x \in \Sigma$.

What I have tried so far is solving it like matrix chain multiplication,
but that gives an algorithm running in $O(n^3|\Sigma|^2)$. How can this problem be solved in $O(n^2|\Sigma|)$?


texts: Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular

texts:
Prove that $L = \{ xy \in \{a,b\}^* \mid |x|_a = 2|y|_b
\}$ is not regular.

I have already tried to prove it by using the pumping lemma and reduction to absurdity, but have been unsuccesful on both. Could someone please help me?

I tried to use the pumping lemma with the word $w=a^{2p}b^p$. It is easy to see that for $p=1$ it cannot be "pumped". However, for the case $p=2$ and, particularly,  splitting the string $w=aaaabb$ into $x=\lambda$, $y=aa$ and $c=aabb$, it is true that $\forall i \quad xy^iz\in L$ . Examples for the case $p=2$ are: $i=0 \mid w=aabb$ which can be split into $x=aab$ and $y=b$, $ i =1 \mid w=aaaabb$ into $x=aaaa$ and $y = bb$, $ i =2 \mid w=aaaaaabb$ into $x=aaaa$ and $y = aabb$, etc. So we can't reach to a contradiction.


texts: cancel out parts of a formula in CNF (conjunctive normal form)

texts: In this image there is a given formula in DNF and CNF. When I check it on Wolfram Alpha I see that it cancel out (E or D) because of (not A or A) which is colored in red. My question is if it is allowed to cancel out (not A or D) because of (not E or E) which is colored in green instead. THX


texts: Name of algorithm: When looking for an optimal element in a list, contionusly adapt the acceptance threshhold

texts:
I'm looking for one of two closely related algorithms. In both, you have a list of elements, of which you have to choose one by some scoring method. In the first variation, the list is infinite and you can't go trough it all, but you can choose any item. In the second, you must choose to accept or reject an item permanently, so if you get to the end, and the last item is a dud, you're stuck with it.

You have no prior knowledge of the range of scores found in the list. As you look at elements of the list, continuously adapt your threshold for acceptance, until you are able to choose an item without having exhausted the list.

For the second variation (finite list), I've seen it in some semi-joking context about dating, where you spend up until age 35 dating people as "samples" and rejecting them all in due time, then past age 35, take the first person who is above the threshold learned from the previous samples.


texts: how to prove correctness of this greedy algorithm?

texts:
I did exercise problem from Pittsburgh university cs department.
homework.

Question 8 is somewhat exciting. Q8 is solved using greedy algorithm but I have no idea how to prove. Below is Question.

Consider the following problem. The input consists of the lengths $l_1, \cdots, l_n, $ and access probabilities $p_1, \cdots, p_n, $ for $n$ files $F_1, \cdots, F_n.$ The problem is to order these files on a tape so as to
minimize the expected access time. If the files are placed in the order $F_{s(1)}, \cdots, F_{s(n)} $ then the expected access time is
$$\sum_{i=1}^{n} \Big\{ p_{s(i)} * \sum_{j=1}^{i}l_{s(j)}\Big\}$$

Don't let this formula throw you. The term $p_{s(i)} * \sum_{j=1}^{i}l_{s(j)}$ is the probability that you access the $i$th file times the length of the first i files.

Greedy solution to solve this problem is to order the files from smallest ratio of length over access probability to largest ratio of length over access probability. That is, $\frac{l_i}{p_i} < \frac{l_j}{p_j}$ implies that $s(i) < s(j)$.

How to prove correctness of this algorithm?
(I know I need to show Greedy choice property and optimal substructure)


texts: Sufficient condition for simple graph isomorphism?

texts:
Say I have two simple graphs, $A$ and $B$

In $A$, I know:

one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc.
one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc.
etc.

In $B$, I know:

one node has 3 nodes at distance of 1, 4 nodes at distance 2, etc.
one node has 4 nodes at distance of 1, 1 nodes at distance 2, etc.
etc.

Can I derive that graph $A$ and $B$ are isomorphic to each other? Or is there a counter-example where two graphs look the same from this distance point of view, but are not isomorphic?

It is a necessary condition, so if these simple graphs are isomorphic, they will share these distances. I am wondering if this is a sufficient condition as well.


texts: What are potential pitfalls with having a minimal kernel that runs managed code?

texts:
Suppose I want to build an operating system based on a very small native lower kernel that acts as a managed code interpreter/runtime and a larger upper kernel compiled to a non-native machine language (Java bytecode, CIL, etc.). Examples of similar operating systems would be Singularity and Cosmos.

What pitfalls and development challenges exist writing an OS with this sort of infrastructure in contrast to a purely-native solution?


texts: What is meant by a full abstract model of a lambda-calculus like language?

texts:
The simply typed lambda-calculus with numbers and fix has long been a favorite experimental subject for programming language researchers, since it is the simplest language in which a range of subtle semantic phenomena such as full abstraction arise.

I tried to find a definition for full-abstract model but I haven't found such. This quote is from Pierce's TAPL book. Note that there is also a related question: What is a "model" of lambda calculus? on the site that has not been answered.


texts: If a B+ tree has an occupancy of 67%, does that mean the tree holds all of an index, and has additional empty nodes taking up the remaining 1/3rd?


texts:
Is this variant of the subset sum problem easy/known?

Given an integer $m$, and a set of positive integers $A = \{x_1, x_2, ..., x_n\}$ such that every $x_i$ has at most $k=2$ bits set to $1$ ($x_i = 2^{b_{i_1}}+2^{b_{i_2}},\;\; b_{i_1},b_{i_2}\geq 0$); is there a subset $A' \subseteq A$ such that the sum of its elements is equal to $m$ ?

Is it in $\sf{P}$? Is it still $\sf{NP}$-complete?

And if every $x_i$ has at most $k=3$ bits set to $1$? For $k=1$ the problem is trivial.


texts: The most efficient way of finding/storing neighbourhood info during octree creation

texts:
Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box intersection check.

Since that is causing a bottleneck in my program I am looking to optimise this stage by somehow assigning the neighbours during octree-creation stage.

I am building a 'depth-first' recursive octree, which means that I go to the deepest level for every node, before moving on to it's neighbour...

What would be the best way to do something like this?

EDIT: The definition of 'neighbours' is the following. A neighbour is each node of the same level/depth which shares a face with the current node. Nodes which only share an edge or vertex should not be considered as neighbours. The picture below provides more clarity...


texts: Generalization of formal grammars - production rules with more general functions?

texts: Usually formal grammars have production rules in the format N=tNt where simple concatenation function is used for the expansion of the nonterminal. https://www.grammaticalframework.org/ has concrete grammars (e.g. FoodEng https://www.grammaticalframework.org/doc/tutorial/gf-tutorial.html#toc19 grammar) with more general production rules which involve special functions for handling inflextion, gender agreement and so on. Are there grammars (and corresponding deterministic finite automata) that can handle grammars whose production rules involve functions beyond simple concatenation?


texts: Four way competition for Machine Learning PhD admission. Which background increases the odds of getting in?

texts:
Let's say there are students from four backgrounds (Mathematics, Applied Mathematics, Computer Science and Statistics) all from top programs. They are applying to a machine learning PhD program at a top American university.

In terms of getting in, which background is most favorable?
What can the pure math student do to improve their chances of getting in?
Would a double degree in any combination of the above fields be more favorable?


texts: For AVL Trees why is keeping a trit (left heavy, right heavy or balanced) sufficient?

texts: I was listening to Eric Demaine's video lecture on AVL trees and there was a claim that comes up that keeping a trit on each node (to indicate whether the node is left heavy, right heavy or balanced) should be sufficient for all AVL tree operations, so essentially we don't need to keep heights of the node for every node. Can anyone prove to me why that would be the case?


texts: Fetching multi word instruction from memory

texts:
A per, from my understanding, instruction decode is a subcycle of Instruction fetch. Now say I have a three-word instruction to be fetched from memory(1 word opcode and remaining words operand address).

My doubt here is: will fetch cycle makes one memory reference and remaining instruction will be fetched in ID stage of Execute cycle or fetch itself fetches the complete 3 word instruction?

With this knowledge I am trying to answer the following question:

Consider a three word machine instruction

ADD A[R0], @B

The first operand (destination) A[R0] uses indexed addressing mode with R0 as the index register. The second operand (source) @B uses indirect addressing mode.

A and B are memory addresses residing at the second and third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During the execution of ADD instruction, the two operands are added and stored in the destination (first operand).

The number of memory cycles needed during the execution cycle of the instruction is:

3 Cycles
4 Cycles
5 Cycles
6 Cycles

The total cycle can be 4 or 6 depending on how many cycles fetch is taking. If fetch takes one then Execute will take 6; if fetches take 3 cycles(to fetch complete instruction) then execution will take 4 cycles.


texts: Conflict Driven Clause Learning backtracking clarification

texts:
On the wikipedia page here it describes pretty well the CDCL algorithm (and it seems the pictures were taken from slides created by Sharad Malik at Princeton). However when describing how to backtrack all it says is "to the appropriate point". MiniSAT also uses a variant of the CDCL algorithm so I read this paper. What they seem to say is that you should backtrack until the learned clause is a unit clause. That is certainly clarification but it doesn't make sense to me. The last assignment is definitely going to be part of the learned conflict clause as far as I can tell (perhaps I am wrong here?) so when you backtrack one step you will immediately make the learned clause unit, the last assigned value will flip, and the algorithm will proceed exactly as DPLL without ever backtracking sufficiently far. Additionally the wikipedia page doesn't follow this rule, it backtracks much further as seems desirable.

How far is one supposed to backtrack?


texts: Ford Fulkerson maximum flow for all vertices

texts: Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, once for each $t$. I feel like there must be a faster way to compute all $|V|-1$ max flows that makes use of dynamic programming techniques. Any ideas?


texts: Path cover with paths of bounded length, in the plane

texts:
I have a weighted, undirected, Euclidean complete graph $G$, a special vertex $r$, and an upper bound $b$.  I want to find a minimum-cost path cover that covers all vertices of $G$, subject to the restriction that every path must have length at most $b$ and every path must start at the vertex $r$.  In other words, I want to minimize the sum of the lengths of the paths, subject to the requirement that the paths cover every vertex at least once and each path starts at $r$ and has bounded length.

Are there any algorithms for this problem that will be effective on medium-size graphs (with, say, at most 200 vertices)?  This problem smells likely to be NP-hard; if so, are there exact algorithms that are more efficient than naive exhaustive search or heuristics that are likely to work well in practice?

Recall that the length of a path is the sum of the lengths of the edges it contains.  Also, a path cover is a collection of paths such that every vertex belongs to at least one path.  A Euclidean complete graph is a graph where each vertex represents a point in the plane, there is an edge between every pair of vertices, and the length of that edge whose length is given by the Euclidean distance between those two points.  (It follows that, without loss of generality, we can assume no two paths have any vertex in common other than $r$.)

This question is motivated by Location Selection Algorithm in Solar Engineering.


texts: Proof NP-Complete for Single machine Job Scheduling Problem specific version

texts:
Problem: given a set of n tasks with execution time Ti, due date Di, and a profit Vi (given only if is enden before due date), is there a task schedule that returns a total profit greater or equal than k knowing that tasks must be executed one at a time?

I am asked to proof that this problem is NP-Complete, can anyone help?

Thanks.


texts: Construct a DFA which accepts a string of length 5 with at least 2 0's

texts: How to design a DFA of all strings over (0,1) such that every block of 5 consecutive symbols contains at least 2 0's?


texts: How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?


texts:
How can I find the serial number of an n-choose-k combination?

I would like a function that gets as input:

$n$,
$k$,
a set of $k$ elements out of the set ${0, 1, ... n-1}$.

The output should be a number in the range $[0, C(n,k)-1]$, such that:

Each different combination gets a different number;
All numbers in the range are covered (i.e. no holes in the index).

For example, for $n=3$, $k=2$, the function could be:

$serial(3, 2, {a,b}) = (a+b-1)$

Since there are only 3 combinations, and their sum is different. Obviously, this doesn't generalize to larger n and k.

One solution is: at the beginning of the program, loop over all combinations, and create a static map from a combination to its index. However, this is very inefficient when n is large.


texts: Why is A* considered as a recursive search algorithm?

texts:
I'm currently studying informed search algorithms.

I've found a paper telling that A* is a recursive algorithm but I can't see where's the recursion part of this algorithm.

Why is A* considered as a recursive algorithm?


texts: Building segment tree without adding extra elements to its size

texts:
I recently learned about segment trees as data structures, and what I learned was that we are always building segment tree with size $N$ such that $N$ is power of two. If $N$ is not power of two we can add more elements to the end of the tree.

However, I was wondering is the segment tree going to work normally if we don't add more elements to make its size power of two.

Example

If the size of segment tree is 8, then we have array of size 15, $15 = 2 \cdot 8-1$
In this array we keep track of the intervals, where we have the interval $[1,8]$ on index 1, and on index $2\cdot 1$ we keep the left child, and the right child is on index $2\cdot1+1$.

So our array looks like following:

index $1: [1, 8], 2: [1, 4], 3: [5, 8], 4: [1,2], 5:[3, 4],6:[5, 6], 7:[7, 8]$,  $8[1, 1], 9:[2, 2], 10:[3,3], 11:[4,4], 12:[5,5], 13:[6,6], 14:[7, 7], 15:[8,8]$

Now my question is this: If we run this algorithm for dividing and building the segment tree for numbers that are not power of two (ex. 7, 11, 15).. is it going to build the segment tree normaly, because the segment tree  is not going to be full balanced then.


texts: What is the minimum square partition of an almost-square rectangle?

texts:
This question is motivated by an older question about tiling an orthogonal polygon with squares.
It is a generalisation of my former question about how to prove that the minimum square partition of a 3X2 rectangle has 3 squares).
Let:

An almost-square-rectangle be a rectangle that has a width  $w$ and height $h=w-1$.
A square partitioning be a covering by non-overlapping squares; the entire rectangle must be covered, all the squares must be disjoint.
A minimum-square-partitioning be a square partitioning, for which is no square partitioning that is made of a lesser number of squares.

Illustration:

Top row: The almost-square-rectangles of widths $3$, $4$ and $5$. Bottom row: Are these miminum-square-partitions of their corresponding rectangles?
My question is now:

What is the minimum-square-partitioning of an almost-square-rectangle?
Can we prove ${\rm M{\small IN}S{\small QUARES}}(R_{w,h=w-1})=w$?

Note a follow-up question, Minimum square partitions for 4x3 and 5x4 rectangles.


texts: Find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one)

texts:
Given a directed and strongly connected graph $G=(V,E)$, weight function $w: E \to \mathbb{R}$ and two distinct vertices $u,v \in V$. We know that there aren't negative cycles.
I need to find algorithm, efficient as possible,such that for every value of $k$, $2 \leq k \leq |V|-1$, it will find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one).

I don't know what to do. I want to use Bellman Ford somehow, I just don't sure how.

Thanks a lot.


texts: Alternatives to SVD for rank factorization

texts:
I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k \times m}$.

A popular approach is to compute the singular value decomposition (SVD) $M = UDV^*$ and keep the columns of $U$ and rows of $V$ corresponding to the non-zero singular values. This is a great approach, especially since it behaves nicely under noise. However, SVD seems to compute more than I need for just rank factorization (and the noise tolerance is cool, but not necessary).

What are the other approaches I can use? In particular, I am interested in algorithms that have one (or more) of the following properties:

Outperform SVD asymptotically.
Outperform SVD in practice, or on special inputs (for a reasonably interesting class of special inputs).
Performance under small perturbation of $M$ is well understood.

I am fine with giving $k$ to the algorithm ahead of time. Note that SVD does not require this (unless we are doing a perturbation analysis, but even then we usually give a bound on perturbation size and determine $k$ at run-time based on that).


texts: decision diagram and decision tree difference

texts: What are the difference between decision diagram and decision tree? Is BDD a type of DD? what are the other type of DD? what are the algorithms used for it


texts: Is this partitioning problem NP-complete?

texts:
I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this sequence into partitions of consecutive subsequences so that the sum of $f$ on each partition is maximized.

For example, suppose the sequence is $(1, 5, 6)$ and $f$ is defined as:
$f(1) = 1, f(1,5) = 13, f(1,5,6) = 0, f(5) = 2, f(5,6) = 9, f(6) = 6$

Then partitioning the sequence as $\{(1,5), (6)\}$ achieves the maximum possible value of $f(1,5) + f(6) = 19$.

Is this problem NP-hard? I can come up with some greedy algorithms to find an approximate solution, but I don't think they always get the correct answer. But I can't figure out how to prove that it's NP-hard either. Any hints on how to make the reduction?


texts: Relational query for universally quantified formula

texts:
My university is participating in the implementation of a library borrowing managing system at Richelieu National Library in France.

I received the order to formulate the query: "find all users having borrowed every book" in relational Algebra, in relational Calculus and in SQL (which would probably not happen, probably librarians want to test the limits of the database).

The database has the following pattern (the primary keys are in bold):

Borrowing(People, Book, DateBorrowing, ExpectedReturnDate, EffectiveReturnDate)
Lateness(People, Book, DateBorrowing, LatenessFee)

I tried

$$\Pi_{People}(Borrowing)\div\Pi_{People}(\sigma_{Book} (Borrowing))$$

But It seemed to be wrong as far as to do  $r\div s$, $S\subseteq R$  is needed, which seems not to be the case, but why? I'm still talking about people, isn't it?

I then tried the following relational calculus formula:

$$\{t.People|Borrowing(t)\wedge(\forall u Borrowing(u)\Rightarrow t.DateBorrowing)\}$$

To find every books that have a borrowing date. I know this calcuation is false but I don't know how to do better...

Then in SQL:

SELECT People FROM Borrowing
    WHERE FORALL Books EXISTS DateBorrowing

That is what I tried and I know that is not the right way to "find all users having borrowed every book". Can you help me expressing correctely such a querry?


texts: Do we know something about this refutation method for SAT?

texts:
Let we have a formula $\varphi(x_1,x_2...x_k)$. Now we apply a refutation method: $\varphi(x_1,x_2...x_k)\Leftrightarrow(\varphi(x_1=1,x_2...x_k)\lor\varphi(x_1=0,x_2...x_k))$. Latter formula seems to be longer, but no, good algorithm reduces number of literal occurences. On each step we can modify the formula without changing it's solution space. This gives much more power than resolution has. For example, Tseytin contradiction can be refuted this way in linear time using deterministic algorithm.

But what is the worst case for this algorithm?

Example:

$$\varphi=(x\lor y\lor z)(x\lor\overline y\lor t)(x\lor\overline z\lor\overline v)(\overline x\lor\overline t\lor\overline v)(\overline x\lor\overline z\lor v)(y\lor\overline z\lor v)(\overline y\lor\overline t\lor\overline v)\land(\overline y\lor z\lor t)$$

Step 1. Getting rid of $t$.

Putting $t$. Affected remaining clauses: $(\overline x\lor\overline v)(\overline y\lor\overline v)$. Reducing them: $\overline v\lor \overline x\overline y$.

Putting $\overline t$. Affected remaining clauses: $(x\lor\overline y)(\overline y\lor z)$. Reducing them: $\overline y\lor xz$.

Combining them using OR: $\overline v\lor\overline y\lor xz$.

Step 2. Getting rid of $y$.

Putting $y$. Affected subformula: $\overline v\lor xz$.

Putting $\overline y$. Affected subformula: $(x\lor z)(\overline z\lor v)$.

Combining them: $\overline v\lor xz\lor(x\lor z)(\overline z\lor v)$. Reduction: $x\lor z\lor\overline v$.

Step 3. Getting rid of $x$.

Putting $x$. Affected subformula: $\overline z\lor v$.

Putting $\overline x$. Affected subformula: $(z\lor \overline v)(\overline z\lor\overline v)$. Reduction: $\overline v$.

Combining them: $1$.

All clauses are covered, formula is satisfiable.

But what would be the hardest case for this and is it possible to break exponential bound using this method? Is this method general enough (we can modify formula by any ways until solution space is unchanged and this is checkable in polynomial time) that saying it requires superpolynomial time (for unsatisfiable formula) will imply $\mathsf{NP\ne coNP}$?

Note that for unsatisfiable formula it's possible to non-deterministically ignore some clauses if refutation can be done without their usage.


texts: Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$

texts:
Hope you had a fantastic christmas break :)
I am trying to find an algorithm in polynomial time that finds the shortest arithmetical expression (the one with the least amount of 1 symbols) to express any natural number, while only using the elements of $\Sigma=\{(,),1,+,\times\}$.
As an example there are multiple ways to express $6\in \mathbb{N}$. but we want the one with the least amount of 1 symbols.
1+1+1+1+1+1
(1+1)*(1+1+1)
(1+1)*1+1+1+1+1
Algorithm:
My current algorithm GetExpression(n) uses a recursive mechanism to get the expression for a number $n\in \mathbb{N}$.

if $n=1$ return "1"
trying to find a divider for n (for loop from i=2 to $\lceil \sqrt{n} \rceil$ with trying $n\mod i=0$)
if there is a divider return "(GetExpression(divider)$\times$GetExpression($\frac{n}{divider}$))"
if n is prime return "(1+GetExpresion(n-1))"

Runtime:
Due to the loop trying to find the divider going in $\mathcal{O}(n)$ and both options of recursive calls having $0<\alpha_1=\frac{n-1}{n}<1$ (in the prime case) and $0<\alpha_2+\alpha_3<1$ (in the non-prime case) we can use the master theorem to see, that our agorithm runs in $\mathcal{O}(n)$ (since we only make one of both options at a time we dont need to look for $\sum_{i=1}^3\alpha_i<1$ but only for $\alpha_1<1$ and $\sum_{i=2}^3\alpha_i<1$)
(actually we need to make a special case for $divider=2$ since there couldbe $\alpha_2+\alpha_3=\frac{1}{2}+\frac{2}{4}=1$ if $n=4$ but we don't care right now).
Correctness:
My problem is how to proof that this algorithm is correct. I was thinking about a induction but i have no glue how to build it.


texts: If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

texts:
$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$
  $T(1)=1$
  The value of $T(m^2)$ for m ≥ 1 is?

Clearly you cannot apply master theorem because it is not of the form $T(n)=aT(\frac{n}{b})+f(n)$
So I tried Back Substitution:
$T(n)=T(n-1)+\lfloor\sqrt{n}\rfloor$
$T(n-1)=T(n-2)+\lfloor\sqrt{n-1}\rfloor$
therefore,
$T(n)=T(n-2)+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(n-3)+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(n-(n-1))+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(1)+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(1)+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
I'm stuck up here and the answer is given as -

  $T(m^2)=\frac{m}{6}(4m^2 - 3m + 5)$

how to solve and reach the answer?


texts:
I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set cover problem.

One of the problem set questions is a basic probability question and is as follows:

You ask ten of your friends to give you one dollar (coin) each so that you can buy your favourite pizza.

When you reach the pizza place you realize that it's closed. So you return the coins to your friends by giving each of them a random coin.

1) How likely is that each of them gets the coin they put back?

2) How many of them will get in expectation the coin they put back? (Try to prove this elegantly using techniques discussed in the course)Define the random variables you use.

3) Now suppose that you take one coin to buy a coffee somewhere else. You redistribute the others dollar coins giving each of your friends one coin chosen uniformly at random. How many of your friends will get in expectation the coin they put back?

I've solved the first two parts and I'm thinking for the third part that I should define a random variable Xi that represents whether or not persion i get the coin back that she put in and E[Xi] is the probability that she gets it back.

The probability that she gets it back is 9 / 10 * 1 / 10 = 9 / 100. There's a 9 / 10 chance that her coin was not the coin that I bought coffee with and a 1 / 10 chance that she picks her coin or is left out as there are 9 coins for 10 remaining people.

Taking X as the number of folks that get their coins back I have

E[X] = sum(E[Xi]) over all persons E[X] = 90 / 100 = .9 people are expected to get their coin back.

Is my reasoning sound here? If not, can somebody show me the error of my ways?

Thanks so much,

Stead


texts: Is there a software algorithm that can generate a non-deterministic chaos pattern?

texts: Is there a software algorithm can generate a non-deterministic pattern or sequence? In Chaos theory, simple processes can create deterministic patterns, and psudo-random number generators can generate deterministic numbers with the same seed. Is there a software algorithm that can create completely non-deterministic patterns or sequences? Does it require hardware such as a quantum random number generator?