texts: Non-Uniform Random Number Generation, from Uniform Random Number Generater

texts:
The project I am currently working on (in C#) requires generating random integer between 0 and Int64.MaxValue.

I have access to a Uniform RNG, which for pseudo-code purposes in the question, I will refer to as:

MyRNG(min, max)

My overall question has to do with how best to use MyRNG(min, max) to create a Non-Uniform RNG that behaves as follows:

0 has the highest chance of occurring.
Int64.MaxValue has a near 0 percent chance of occurring.
The chance of value X occurring is an asymptote approaching 0, as X approaches Int64.MaxValue

From what I have gathered in my research, it seems like the 2 important values needed to achieve this, are:

 The percent chance of the value 0 occurring.
 A description of the slope (possibly wrong word) of the asymptote. (Is this a classic decay problem I vaguely remember from High School?)

What I tried, that almost worked:

Initially, I wrote a recursive function to try and achieve this. It looked something like this:

int difficulty = 10    // <-- This was tuned to get close to desired output.

public int GetNonUniformRand(int remainingDifficulty, int currentMax) {
    if (remainingDifficulty > 0) {
        return GetNonUniformRand(remainingDifficulty-1, MyRNG(0, currentMax));
    }
    return MyRNG(0, currentMax));
}

int finalOutput = GetNonUniformRand(difficulty, Int64.MaxValue);

The behavior of this function when difficulty is 10, would be something like this:

start with rand number between 0 and max... lets say 17024503.
generate random number between 0 and 1702450... lets say 312523.
generate random number between 0 and 312523... and so on.

Using this method worked okay. I assume there is still a very small chance of Int64.MaxValue, but it is very unlikely. The problem with this approach is that it I don't know how to find the probability of getting any particular value. Also, the recursion is not as efficient as I need it to be, as this will be running on a device that isn't very powerful.

Any advice on how to use MyRNG() in an algorithm that will provide the behavior I described, while also allowing me control over the "2 important values" I mention is greatly appreciated. Thank you all in advance.


texts:
I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to understand it:

sum = 0;
for (i = 0; i < n; i++
    for (j = 0; j < i; j++)
        sum++;

The part that's throwing me off is the j < i part. It seems like it would execute almost like a factorial, but with addition. Any hints would be really appreciated.


texts: Are regular and context free languages closed against making them prefix-free?

texts:
For a language L we define:

$\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $

Are regular / context free languages closed under this operation ?

For regular languages I thought about taking the DFA that accepts the language L and create a new NFA by making all accepting states sinks (so the only way of being accepted by the automata is that when reading the last letter we reach an accepting state for the first time).

Can't we make the same thing with a pushdown automata for context free languages ?

Edit (as Raphael pointed out, the example below is wrong):

But here is a strange language that I think implies the opposite:
$L = \{ 0^{i}1^{j}2^{n} \mid i \le n \ \text{ or }\ j \le n \} $
$A(L) = \{ 0^{i}1^{j}2^{n} \mid n = \min(i,j) \} $

$L$ is context free but $A(L)$ isn't. Obviously, at least one of the things I wrote above is wrong. Anyone have any clue what is going on here ?


texts: Number of automorphism for clique of 6 vertices minus two non adjacent edges

texts:
How many automorphism does a clique with 6 vertices have, when we take two edges from it (two edges that don't have the same vertex)?

I thought the answer is 6*(n-2)!
Number of automorphism for a full graph Kn is n!. Clique can be seen as a full graph since all of the vertices must be connected to each other. Since we take away two edges I think it should be (n-2)!. And it has to be multiplied by 6 because there are 6 vertices all together so was still permutate them.

Is this correct? How to find this correctly? What if there are N vertices?


texts:
Given $n$ sets $r_1, r_2, \cdots, r_n$ and a number $\delta$ where $0 \le \delta \le 1$. Let $T=\cup_{i=1}^{n}r_i=\{t_1,t_2,\cdots,t_m\}$. Each $t$ has a value $v(t)$, which is given to us.  The task is to find a subset $S$ of $T$ that minimize the total value $\sum_{t\in S}v(t)$ while guaranteeing $\sum_{i=1}^{n}\frac{|r_i \cap S|}{|r_i|}>\delta n$.

Is this problem NP-complete? If so, which problem should I reduce from?

I've tried reduce it from the knapsack problem. One of the steps is not in P time and the attempt failed.


texts:
Let $n$ be an integer, and let $\mathbb{Z}$ denote the set of all integers.  Let $[a,b]$ denote the interval of integers $\{a,a+1,a+2,\dots,b\}$.

I am looking for a data structure to represent a map $f:[1,n] \to \mathbb{Z}$.  I want the data structure to support the following operations:

$\text{get}(i)$ should return $f(i)$.
$\text{set}([a,b],y)$ should update $f$ so that $f(a)=f(a+1)=\cdots=f(b)=y$, i.e., update $f$ to a new map $f'$ such that $f'(i) = y$ for $i \in [a,b]$ and $f'(i) = f(i)$ for $i \notin [a,b]$.
$\text{stab}(i)$ should return the largest interval $[a,b]$ such that $i \in [a,b]$ and $f$ is constant on $[a,b]$ (i.e., $f(a)=f(a+1)=\cdots=f(b)$).
$\text{add}([a,b],\delta)$ should update $f$ to a new map $f'$ such that $f'(i) = f(i) + \delta$ for $i \in [a,b]$ and $f'(i) = f(i)$ for $i \notin [a,b]$.

I want each of these operations to be efficient.  I would count $O(1)$ or $O(\lg n)$ time as efficient, but $O(n)$ time is too slow.  It's OK if the running times are amortized running times.  Is there a data structure that simultaneously makes all of these operations efficient?

(I've noticed a similar pattern come up in a several programming challenges.  This is a generalization that would suffice for all of those challenge problems.)


texts:
Wordsense.eu defines epilogue as a part of an algorithm that prepares for return.

I’d like to know more & haven’t been able to successfully search for info. Could anyone point me to a source / share their knowledge?


texts: Calculating decimal digits of pi, using something similar to a Bailey–Borwein–Plouffe formula

texts:
I have tried to Use the Bailey–Borwein–Plouffe formula to calculate pi to 3 digits as a test trial, and recieved the digit 4, which is technically correct, as 4 is the 3rd digit of pi in base 16. I would like to get the digit in decimal, as that is the current standard for numbering things in most places, as you don's see many things labelled D5 except in excel spreadsheets. Basically, I need to conduct a Bailey–Borwein–Plouffe formula from 0-6 (intead of 0 - infinity as i only need pi to 6 digits), but in decimal.

Here is what I had for the base 16 computation.

double pi2 = 0;
int n = 0;
while (n < 3)
{
    double a = (1/(Math.pow(16, n)));
    double b = (4/((8*n) + 1));
    double c = (2/((8*n) + 4));
    double d = (1/((8*n) + 5));
    double e = (1/((8*n) + 6));
    pi2 += a*( b - c - d - e );
    n++;
}


texts: Prove that a sequence of increasing find operations on a splay tree takes $\mathcal{O}(n)$ time

texts:
When studying about splay trees, I found the following statement:

  Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $\mathcal{O}(n)$ ($n$ is the number of nodes in the tree).

I looked around, but haven't been able to find anything. Can this be proven formally? Or shown that it is true?


texts:
Following are some definitions from CLRS:

  DEFINITIONS :
  1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.
  2. Light edge:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.
  3. A cut Respects a set A of edges if no edge in A crosses the cut.
  4. Safe edge is the edge which we can add to MST without any violation of MST's property.These are those edges which are the part of final MST.


texts: Crossover topologically identical neural networks

texts:
I have recently learned about artificial neural networks (very interesting) and genetic algorithms (also very interesting). I have read some suggestions concerning how to crossover two parent neural networks to produce a child. For example, randomly selecting weights and biases from either one parent or the other, or selecting the first L layers from one parent and the rest from the other. I was wondering if taking the average weights and biases (such that wij(L) of the child networks equals the average wij(L) of the parents, and similarly for bi(L)) would be a proper crossover operation.

Which of these operations would be best suited for most genetic algorithms involving neural networks? Note that I want to limit the scope of this question only to topologically identical parents producing a child with that same topology.


texts: If Data-Flow Analysis is able to approximate, what does that mean?

texts:
I have been learning about data-flow analysis and have come across the idea of approximations and that the data-flow analysis should be able to under and over approximate a situation. For example, when using available expressions, we under under-approximate if we aren't sure if we can do something by not doing it. I just don't really understand; surely if analysis wasn't sure if it could do something or not, the algorithm would just not report this as a possible available expression?

What does approximation and decidability (which I think is also related) mean in terms of data-flow analysis?


texts: Problems unsolvable by an oracle machine?

texts:
Are there classes of problems that cannot be solved by an oracle machine? If so, are there specific problem examples of that class of problems?

Even the Omega number, at least the first N digits, could be computed as the Oracle could just return TRUE or FALSE for each {0,1}-digits...


texts: What is the only condition that would cause the Insert operation of a dynamic data structure to return a “data structure full” error?

texts: I want to know where can I find some resources on this question, because, after researching for a day and half, I couldn't find information specific to my question. Can anyone help me answer my question? I know that dynamic data structures (such as linked lists) can expand the amount of nodes at runtime, but if that's the case, how could it ever return a "full error" message if has an unlimited amount of storage to get keep holding nodes inside of it?


texts:
I want to compress file size through making my own numbering system which is 80-based number, I do really want to know whether this even possible ? I learnt that Hexadecimal uses symbols like A, B, C, D, E, F to represent 10,11,12,13,14,15 -- and that's what i want to do to my own numbering system but in a bigger scale . Please correct me if i'm missing something .

Is it possible ?


texts: Constructing the matrix of a controlled quantum operation

texts:
How do we construct a matrix that takes into account whether the first qubit is set?

I am trying to construct the controlled-V matrix, but there is no quantum computational paper that describes it so I am looking at CNOT and wondering how the matrix for CNOT determines whether the first bit is set (to apply the NOT part)

Could somebody help?


texts: Are probabilistic search data structures useful?

texts:
A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these bounds only hold as long as the structure of the SkipList is sufficiently "balanced". In particular, with probability $1/n^c$ for some constant $c>0$, the balanced structure might be lost after inserting an element.

Let's say I want to use a skip list as a storage backend in a web application that potentially runs forever. So after some polynomial number of operations, the balanced structure of the SkipList is very likely to be lost.

Is my reasoning correct? Do such probabilistic search/storage data structures have practical applications and if so, how is the above problem avoided?

Edit: I'm aware that there are deterministic variants of the SkipList, which, are much more complicated to implement in comparison to the (classic) randomized SkipList.


texts:
I am referring to section 8.1 of this paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf. Can someone kindly give me a concrete definition of what it means to "construct a PCP" and if that is the same as a "PCP verifier". Are they the same things?

Its not clear to me as to what it means to say that "Let the bits in the proof be vertices of a graph and the tests of the verifier be the edges of the graph." How can one encode vertices of a graph as single bits?

I am trying to match this to the concepts in the lecture notes by one of the authors, https://courses.cs.washington.edu/courses/cse533/05au/ but its not clear as to how to go about doing it. If someone can help identify the correspondence that would also be a great help!


texts:
Let's consider an undirected graph with two special vertices: start and finish. The graph is relatively sparse. The edge count is expected to be three times or four times higher than the vertex count.

I am looking for an algorithm that decides whether there exists some path between start and finish and if it is unique. The output of the algorithm is one of the three possible answers:

There is no path between start and finish.
There is exactly one path between start and finish.
There are two or more paths between start and finish. The two paths need not be disjoint. They just must not be identical.

Currently, I have the following algorithm implemented:
I run breadth-first search from start vertex to find the shortest path from start to finish. If the finish vertex is unreachable, I am done. If I find a path, I iterate over its vertices except start and finish. I remove the vertex and run BFS from start vertex again. If the finish vertex can be reached, I am done as I have found another path from start to finish. If the finish vertex is unreachable, I undo the vertex removal and continue with another vertex. If the finish vertex is always unreachable during this loop, the initial path is unique.

I wonder if there is some more efficient algorithm than running BFS for each vertex of the initial path.

EDIT:
As mentioned in the comment, I am interested only in simple paths, i.e. paths without repeating vertices.


texts: Can Nondet Rabin Tree automaton be determinized?

texts:
In other words, are they equally powerful?

(for word automata the answer is "yes"; this question is about tree automata).

(i am talking about tree automata that work on $in$finite trees)


texts:
Given $N$ points in a grid having some weight, I have to find the side length of a square sub-grid with maximum sum of weight of points contained in that square sub-grid. Also square sub-grid must have side length less than $L$ (given integer).

$ 1\le N \le 100000$, $1 \le L \le 100000$ , $1 \le x_i \le100000$, $1 \le y_i \le 100000$, $1 \le \text{weight}_i \le 10^9$, where $i$ is the $i^{th}$ point.

I have tried using prefix sum array and iterating over all the possible square sub-grids, but this is not efficient.

I need to know in which direction should I start thinking.


texts: when to use preorder, postorder and inorder binary search tree traversal strategies

texts: What are some examples of when to use preorder/postorder practically? When does it make more sense than in-order?


texts: What is the minimum pumping length of the union of two languages?

texts:
If I have two languages L1 and L2 that are pumpable, what is the minimum pumping length for the union of them?
Does it differ if either of them contains just one string like 001?


texts: How is the problem, {⟨G⟩|G has no triangle} in Logspace?

texts:
I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-tuples in the tape, then how come my solution is limited to log-space?

As far as my understanding, listing all the 3-tuples in the tape would need $\binom{n}{3}$ combinations, and hence, $O(n^3)$ space.

I am not able to find the flaw in my understanding, grateful ever for the hint.

P.S. This reference is from our course slide:

  Let $L$ be the language $\{⟨G⟩ \: | \: G\text{ has no triangle}\}$. Then $L$ can be recognized in log-space as follows: On the work tape, the machine $M$ can write all 3-tuples of the vertices of $G$. For each tuple written, the machine checks if there is a triangle passing through those vertices. If all tests fail, then $M$ accepts, otherwise $M$ rejects. The space used by $M$ is enough to store three vertex identifiers, therefore $L$ is in log-space.


texts:
Let $R = \{1, \ldots, n\}$ and $S = \{S_1, \ldots, S_m\}$ a collection of subsets of $R$ such that $R = \bigcup_{i = 1}^m S_i$ and, for $n > 3$, $$3 \leq \vert S_i \vert \leq 4 \, , \enspace i \in \{1, \ldots, m\} \, .$$

Then, I want to know the subset—or subsets, since there may be more than one valid solution—$T$ with minimum cardinality such that every $S_i$ has at least one element in $T$. I suspect this is an NP-hard problem (or NP-complete in its decision version), but I don't know if it's one that has a name.

As an example, consider $R = \{1, 2, 3, 4, 5\}$ and $S = \{S_1, \ldots, S_9\}$, where

$S_1 = \{1, 2, 3\} \, , \enspace S_4 = \{1, 4, 5\} \, , \enspace S_7 = \{1, 2, 3, 4\} \, ,$
$S_2 = \{1, 2, 4\} \, , \enspace S_5 = \{2, 3, 5\} \, , \enspace S_8 = \{1, 3, 4, 5\} \, ,$
$S_3 = \{1, 2, 5\} \, , \enspace S_6 = \{3, 4, 5\} \, , \enspace S_9 = \{2, 3, 4, 5\} \, .$

Here, the solutions are $T = \{\{1, 3\}, \{1, 5\}, \{2, 4\}, \{2, 5\}\}$. (I'd be happy even if I knew just one of them.)

Note that I'm not asking for an algorithm to solve the problem. I just want to know where this is or reduces to a well-known problem.


texts: QBF in APTIME - Why APTIME and not ALOGSPACE?

texts:
I have a brief proof about QBF being $\in$ APTIME, which claims that you can use the additional input of the alternation as values for your QBF formula.

And therefore you can accept, if the quantifier less formula $\psi$ is true, given the additional input.

That makes sense, but if you assume $\psi$ in 3-CNF. I could make that check in SPACE$(\log n)$ and therefore, I could solve QBF in $\mathbf{ALOGSPACE}$, which would place QBF in $\mathbf{P} = \mathbf{ALOGSPACE}$, that obviously can't be true, but I don't see my mistake.

The proof claims runtime: $\mathcal{O}(n^2)$

I know that APTIME = PSPACE and QBF is PSPACE complete therefore QBF is APTIME complete, so what am I missing?


texts: What does the 2 in a 2-approximation algorithm mean?

texts: Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?


texts: How P2P search engines prevent corruption of distributed index by malicious peers?

texts:
As a hobby, I am writing a simple and primitive distributed web search engine. It occurred to me that it currently has no protection against malicious peers trying to skew the search results.

The principle idea of the project is:

To store the inverse indices and ranking factors in a Kad (Kademlia) DHT (Distributed Hash Table).
The peers update the inverse indices as they crawl web.

I used Google Scholar to find a solution. It seems that most of the authors of proposed P2P web search ignores the above-mentioned problem.

I think I need some kind of reputation system or trust metrics. My knowledge in this domain is sufficiently lacking. I would very much appreciate a few pointers.


texts: Why classification represents all computations?

texts:
I'm a computer science student taking a theory of computation class. Recently we were taught about what is computable and what is not and about the Turing machine. As I understood (please correct me if I'm wrong) Turing machine  could do any computation that is possible to compute. But for all examples in computing, what my instructor takes are classification (deciding whether the input has a certain characteristic or not) problems.

Does being able to classify anything mean you can do any computation? For example, addition subtraction etc? What is the connection between classification and computation in general?

I referred few books but I couldn't find an answer. Please help.

Thank you,
PPG


texts:
Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but that would require a c compiler to begin with. If a mistake is made in the making of one of the early iterations of compilers, it could propagate. How do compilers make sure that this doesn't happen? Obviously, no code is flawless, not even the processor is, but if you haven't somehow measured the stability, you don't even know if your compiler is stable. What assumptions are made and how is it justified? I would imagine it would be architecture-dependent too.
Edit: By stability, I mean that the code runs as intended.


texts: How does virtual and physical memory affect cache structure?

texts:
Working with a question that states:

Consider a hypothetical machine in which physical address space is
of 512 words and virtual address space is of 2048 words. The page
size is 8 words. What is number of bits used for: Page offset,
Physical Page Number, Virtual Page Number

Since my course uses MIPS, I'm assuming the word size is 4 bytes, so to determine the byte size of each I multiply them by 4 and get: 32, 2048, 8192 respectively.
The total amount of bits used to represent page offset is just those numbers log base 2 so I get 32 bytes which is 5 bits.
I used those 5 bits to determine the page number for physical and virtual memory

physical memory = 2048 = 11 bits - 5 bits = 6 bits
virtual memory = 8192 = 13 bits - 5 bits = 8 bits

I double-checked those by dividing the words in each space by the words in page size and then logging b2 that number as well and it checked out. Does my logic make sense, does this actually double check my work? Is page offset simply the bits needed to represent page size?

Now, let’s assume the cache size is 128 words in total. Directly
mapped with block size of 2 words(8) each. What is the number of
blocks, sets, and ways for the cache?

I immediately knew it was only 1 way because it was a direct mapped cache.
I determined that there were 64 blocks because there were two words per block and 128 words total so simply 128 / 2.
Since it's directly mapped, I assumed there were 64 sets, one to go with each block.

If cache access and translation need to be done in parallel
How many bits of virtual address are used for byte offset? Which bits?
How many bits of virtual address are used for block offset? Which bits?
How many bits of virtual address are used for index? Which bits?

I assumed 2 byte offsets(at least) for the virtual address because I know that's a given. Why is that a given?
For block offset I said 1 bit because there are two words per block and the offset is needed to represent them both in the same space.
For index I took my number of sets and found the bits needed to represent it (log base 2 64) and found 6.
Are there any flaws in my logic? Could anyone explain where I went wrong?
I'm confused about what I should be taking into consideration from the first half of the problem for the latter half. How are pages with the physical 6 bits stored when the index is larger than the entire address? How do the two problems relate to each other at all?


texts:
I've written a function. I believe the function runs in complexity:

$$  T(m, n) = \begin{cases}
              T(m-1, n) + T(m, n-1) + T(m-1, n-1) + 1 &\text{if $m,n>0$}\\
              0 &\text{otherwise}
              \end{cases}
$$

I have no idea how to simplify this. Can anyone help?

(No, this is not a homework assignment. Well, writing the function was, but after writing it I'm certain that I wrote a very inefficient implementation and am trying to figure out just how bad my version really is.)


texts: In RegExr, why is regex OR in JavaScript sometimes not commutative?

texts:
On https://regexr.com/, using the default JavaScript (Browser) engine, the languages $L(a^*|b^*)$ and $L(b^*|a^*)$ are not the same.
The first one matches only $a$'s and the second one $b$'s.

Is this a bug?
Or does the site something different than evaluating regular expressions, as I learned them in class?


texts: How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?

texts:
I am trying to find the frame check sequence in cyclic redundancy check(CRC). Given that the generator polynomial is $\ g(x)= (x+1)(x^3 + x^2 + 1)$. Let's say the data sequence is $\ 10110001$.

In this case, $\ g(x) = x^4+x^3+x+x^3+x^2+1 $ after multiplying. But how do I handle 2 $\ x^3 $ terms? Is it okay to convert it into binary without worrying about it? For example, $\ 1 1111$ and continue with the division?


texts: TRNG by hamming distance of processor tics

texts:
I hardly remember on a lecture, where it was told, that the distance of the practical actual running-speed of a processor to the previous tic is used, to generated a true random entropy for seeding. But I cannot find any source for proving this memory right.

So my question arises: Is this a way to generate a true random seed and spawn so a trng?


texts: Algorithm for weighted elliptic curve fit

texts:
Background:
I was trying to detect a face solely on the bases of features and the confidence of the features found.
I am using a method to identify the features along with the response (confidence). Stronger features have higher responses.
I was trying to identify rotations of face. So, I was thinking about using ellipse bound to identify single face from image.

Question:
Is there any standard algorithm/standard library that does weighted elliptic curve fit for all the points?

(Mostly, the points would be in and around the ellipse with weights. However, there may be outliers. All points will have to be considered. The outliers will have less weight though.)

Inputs to the algorithm: coordinates of the points and the weights of the points.

Expected output from the algorithm: Minor axis, major axis, 2D orientation angle and the centre of the ellipse (using weighted curve fitting).

If there are 'n' number of features, I could calculate the centre of ellipse using the weighted average of features.
But, how would I determine minor axis, major axis and the rotation of the ellipse?

Attempts:
I tried with circle and it works very well. But, it does not have rotational information (it just draws a circle when face is rotated).
I found literature survey about elliptical curve fits using iterative methods.
I also ideated that rectangular curve fit would also do (as length of the rectangle can be major axis of ellipse and breadth of rectangle can be minor axis of ellipse).

But, I have been unable to observe any 'universal' solution. (For example, if the face is far from the camera, ellipse should be smaller accordingly. Many curve fitting algorithms use parameters which are translation variant)

Images for unweighted and weighted curve fitting:

Unweighted elliptical curve fitting would be as shown in left. It would probably just use least mean square fitting (with iterations for angles). But, this method is not desired as it would not account for the importance of features (for example, a feature of a shirt in an image would be "less important" than the one on face. Hard thresholding or binarising destroys information). Desired weighted elliptic curve fitting is as shown in right.


texts: How to determine time complexity with a simple way?

texts:
I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was: $$f(n) = 4n(n + 2 \log^2 n^2) + e^{−n} + 8 \sin(2πn/256). $$

Is there a simple way how a I can determine which one of this is the true one? Because this look much more complicated then the ones we did in our class.

$f(n) =o(n\log_2n)$
$f(n) =o(2^n)$
$f(n) =o(n^4)$
$f(n) =O(n\log_2 n^n)$
$f(n) =O(2n + 1)$


texts: No compression algorithm can compress all input messages?

texts:
I just started reading a book called Introduction to Data Compression, by Guy E. Blelloch. On page one, he states:

The truth is that if any one message is shortened by an algorithm, then some other message needs to be lengthened. You can verify this in practice by running GZIP on a GIF file. It is, in fact, possible to go further and show that for a set of input messages of fixed length, if one message is compressed, then the average length of the compressed messages over all possible inputs is always going to be longer than the original input messages.
Consider, for example, the 8 possible 3 bit messages. If one is compressed to two bits, it is not hard to convince yourself that two messages will have to expand to 4 bits, giving an average of 3 1/8 bits.

Really? I find it very hard to convince myself of that. In fact, here's a counter example. Consider the algorithm which accepts as input any 3-bit string, and maps to the following outputs:
000 -> 0
001 -> 001
010 -> 010
011 -> 011
100 -> 100
101 -> 101
110 -> 110
111 -> 111

So there you are - no input is mapped to a longer output. There are certainly no "two messages" that have expanded to 4 bits.
So what exactly is the author talking about? I suspect either there's some implicit caveat that just isn't obvious to me, or he's using language that's far too sweeping.
Disclaimer: I realize that if my algorithm is applied iteratively, you do indeed lose data. Try applying it twice to the input 110: 110 -> 000 -> 0, and now you don't know which of 110 and 000 was the original input. However, if you apply it only once, it seems lossless to me. Is that related to what the author's talking about?


texts:
I have a sorted array of integers [x, ..., n, ..., y] so that
x > 0
n - x = random positive integer

The array might look something like this:
[1, 2, 3, 15, 16, 17, 120, 121, 122, 123, 124, 125, 126, 127, 210, 211, 212, 213, 214, 215]

I want to divide this array into segments so that,
1) The difference between last and first element of a segment < 125
2) The number of segments is equal to k (predefined positive integer)
3) Sum of differences between first and last element of all segments is minimal

The end result should be a list of segments with their start and end values.
The minimum size of a segment is 1.

Suppose k = 2, then the given example array could be divided into two such segments:
Option 1) [(1, 125), (126, 215)]
Option 2) [(1, 17), (120, 215)]
Both satisfy requirements 1 and 2.

Sum of differences between first and last element of all segments:
Option 1) (125-1) + (215 - 126) = 213
Option 2) (17 - 1) + (215 - 120) = 111
Therefore option 2 is the preferred solution.

Python is the used language.

Any suggestions on how to approach this problem are welcome.


texts: How do I show that whether a PDA accepts some string w is decidable? or undecidable?

texts:
Currently studying for an Automata Theory final and can't find an answer to this question anywhere.

Can you simply let w = w!w and show that it is undecidable that way? Like this here: How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

Or do I have to show decidability for arbitrary string w.

Thanks


texts: Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?

texts:
Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges.
In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells.
(i.e., $|x| = O(n^2)$ or $|x| = O(m \log n)$).
Now I want to study the lower bound and the upper bound on the time/space complexity with respect to the number of vertices $n$. Suppose we have found the upper bound is $O(f(|x|))$ and lower bound $\Omega(g(|x|))$. Since $m = O(n^2)$ and $m = \Omega(n)$, we can only conclude that
$$O(f(|x|)) = O(\max\{f(n^2), f(m\log n) \}) = O(f(n^2\log n))$$
and
$$\Omega(g(|x|)) = \Omega(\min \{g(n^2), g(m\log n)\}) = \Omega(g(n\log n))$$
The gap become larger. It is not tight even $f = g$.
Is there way to solve my confusion?
Now I define the graph problem as a pair $(L', O)$ where for every instance $x'$ of $L'$, it is only encoded by the  number of vertices, $O$ is an oracle whose valid input is a pair of vertices $(u,v)$, it returns 1 if $uv$ is an edge in the graph and it returns 0 otherwise. Can I solve my confusion by using this model? (However it seems that $|x'| = O(\log n)$ which is very small.)


texts: State of variables in dynammic programming

texts:
I would like to know  what a state variable is in simple words, and I need to give a lecture about it.

I have chosen the Longest Common Subsequence problem
I found a similar question but it has no answers. I was told that I need to use the "states of variables" (not sure if variable of a state and state variable are the same) when explaining the pseudocode.

I think it has something to do with Hoare logic and state variables but I'm a very confused.

If you can provide useful links or maybe a clear explanation would be great.


texts:
I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers.

After my research, I'm lost between all the algorithms for this problem.

$O(2^N*N)$ for the naive algorithm (I understand)
$O(2^{N/2})$ for advanced algorithm (I understand)
$O(N * C)$ for pseudo-polynomial time algorithm (only positive numbers)

Reference : Wikipedia

$O(N^3 * log(N))$ for an exact resolution but I don't understand the whole process

Reference : Andrea Bianchini paper

I would like to know if my resolution is in polynomial time ?

If it is, the paper of Andrea Bianchini is too.
So it should proove that P=NP, but it's not the case. Why ?


texts:
I'm trying to figure out why NOT and CNOT gates are not sufficient to create all bijective functions in classical circuits. I have been struggling on this for hours, and just can't make sense of it.

I feel it has something to do with the Toffoli gate, as it contains an (implicit) AND operation, and I feel that's what missing in the NOT and CNOT gates. However I can't find a proper way to actually 'show' this.


texts: Minimize the depth of a tree of computation

texts:
Assume you have a binary tree of additions, where each two nodes are added together until the root is the sum of all the nodes. For example:

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

To minimize the depth of this tree is easy: I can just run DSW on it for instance. The reason I can do this is because the addition operator is commutative.

Now what happens if each node has a different operation? *, /, + or -? How can I find an optimal minimal depth of that computation tree? An example tree is shown below:

   3 * 2  1 - 3
    \ /    \ /
     6  /  -2
      \    /
        -3

What I have come up with so far is to check if each subtree consists of commutative operations only, and then I can move nodes around in that specific subtree. However, this is a very crude 1st order heuristic.

Is there work detailing how we can refactor equations in such a way that we can reduce the depth of a computation graph? This would allow for more parallelization of the code required to compute this tree.

Motivation: In my specific case, I am actually not doing this for software. I am building custom hardware to evaluate the arithmetic computation. So one of my optimization objectives is to reduce the hardware tree depth so that I reduce the latency of my pipeline computation.


texts:
I'm studying heap sort and was presented with the following question.

  What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a heap of size 15 for which the minimum is achieved.

There should be at minimum two sorts for this problem which I understand. However, I have trouble figuring out the answer for the second part of the problem,

  Answer the same questions for two and three successive remove the maximum operations.

Would the answer also be 2 because the same process is taking place in which we find the child with the bigger key and see if the child needs to be promoted?


texts: How is a communication protocol a mechanism?

texts:
Given a finite set $\Sigma$ and a positive integer $n$, a mechanism is a set $\{ \mu_x \vert x \in \Sigma^n \}$ such that $\mu_x$ is a probability measure on some $\sigma-$algebra for each $x$.

Now given a communication protocol $P$ between two privately coin-flipping parties $A$ and $B$ who start with the inputs $x$ and $y$ respectively one defines this quantity called the $VIEW^A_P(x,y)$ : ``a joint probability distribution over $x$, the transcript of the protocol $P$, private randomness of the party $A$, where the probability space is private randomness of both parties"

What does the stuff in the quotes mean?
Can someone help understand how is this $VIEW^A_P(x,y)$ a ``mechanism" as defined earlier? (For this to be a mechanism, $VIEW^A_P(x,y)$ for a fixed $x$, has to assign a probability to some set of outcomes and I am unable to see as to which set of outcomes is it assigning a probability and how)

A transcript of a protocol will be a sequence of private coin tosses and bits exchanged in every step. So if one fixes both $x$ and $y$ then I can imagine that a probability can be assigned to a protocol - which would be the probability for that sequences of coin tosses to have happened. But still whaht is an "event" here is not clear since I can't see a natural way to group together these "outcomes" (each of which is now a possible transcript when started with a $x$ and $y$).

But if one fixes only $x$ then nothing is clear to me..

Reference : http://www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/diffprivacy.pdf


texts: Prove that AVL tree has this kind of property with Fibonacci sequence

texts:
Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$)
and has a height of $h$ this property is true:
$n \geq F(h)$  where $F(h)$ is the $h$-th element in the Fibonacci sequence:
$F(0) =0, F(1)=1, F(n) = F(n-1) + F(n-2) ~~~~\forall n \geq 2$

This is my go:

We know it is an AVL tree so $h = \log_2{n}$
Thus we need to prove that $n \geq F( \log_2{n})$

$F(\log_2{n})= F(\log_2{n}-1)+F(\log_2{n}-2)$
However I am stuck from here, I don't know what this helps me with and I am clueless on what to do next..
I would appreciate your help, thank you!


texts: Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?

texts: could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to give a group of talented high schoolers who haven't seen matrices before a sketch/cursory proof of the result, but I couldn't think of a good way to explain it.


texts: What is the difference between finite automata and finite state machines?

texts: I have used FSM in Digital sequential Circuit designs. But I am unfamiliar with Finite Automata. Can somebody help me in understanding 'basic' difference between the two ?


texts: Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

texts:
Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation.
  Assume that $t(n)= \Theta (1)$ for suffucuently small $n$.
  $$t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$$

I am a bit confused on how to approach such question, I did solve questions such as $t(n)=3t(n/4)+nlogn$, but never saw an example where $t(n)=at(\frac{n}{b})+ct(\frac{n}{d})+f(n)$.

Any solutions or hints on how to solve this problem would be appreciated.


texts: How to show the function is not Turing computable?

texts:
Having the function:

$$f(y) = \begin{cases}
         \ 1 &\text{if }\forall n \Phi_y(n)=n\lor \Phi_y(n) \!\uparrow\\
         \ 0 &\text{otherwise.}
\end{cases}$$

By the rule of thumb it should not be computable. How to prove it formally?
If it's computable, I assumed a function like this exists:
$$g(y) = \begin{cases}
         \ 1 &\text{if $f$(y) = 1 }\\
         \ 0 &\text{if $f$(y) = 0}
\end{cases}$$

I assumed $g(y)$ is computable. Now there exists a function $\Phi_{x_0}(x_0)$ which simulates $g(y)$.
This means: $\Phi_{x_0}(x_0) \downarrow$ iff $\Phi_{x_0} (x_0) \uparrow$, which is a contradiction. Is this sufficient as a proof?


texts:
In a previous question there was a definition of weight balanced trees and a question regarding red-black trees.

This question is to ask the same question, but for AVL trees.

The question is, given the definition of $\mu$-balanced trees as in the other question,

  Is there some $\mu \gt 0$ such that all big enough AVL trees are $\mu$-balanced?

I presume there is only one definition of AVL trees and there is no ambiguity.


texts: Levenshtein distance algorithm with bits

texts:
I need to write a function that gets an array of bytes at the input and 2 integers (minDist and maxDist). The calculation algorithm understands this field as a bit sequence starting from the LSB (least significant bit) of the first byte and ending with the MSB (the most significant bit) of the last byte. Therefore, for the input of the length of n bytes, we have a sequence of 8n bits. The task is to test all non-empty prefixes (prefixes) of this bit sequence and all non-empty suffixes of this sequence, for each pair (prefix x suffix), you need to specify their editing distance. The result is the number of pairs whose editing distance belongs to the specified closed interval . The editing distance of a pair of bit strings is the smallest number of bit deletions / insertions / bit changes so that from one bit string we get another one.

I would use Levenshtein's algorithm (https://rosettacode.org/wiki/Levenshtein_distance#C.2B.2B ) with adjustments, which I think would work?

Since prefixes and suffixes altogether sum to 8*n (n is the number of bytes of the problem, we do not test the empty string), the problem can be resolved by testing 64*n^2 string pairs, each comparison consuming n^2 operations. Thus, in total, solving one problem, the function has the complexity of n^4, by appropriate modification the complexity can be reduced to n^3.

If I understand correctly, if I used Levenshtein algorithm I will get complexity of n^4, but how do I go on modifying to n^3?

Maybe I'm completely mistaken, please correct me.


texts: Turing machine deciding $\{1^{2^n} : n \geq 0 \}$

texts:
How can I design a Turing machine that accepts the language $\{1^{2^n} : n \geq 0\}$?

Here is my attempt:

[![enter image description here][1]][1]


texts: Print (not count) all possible path classic climbing stair problem)

texts:
I came across this classic question and found may many solution to it. for loop and DP/ reclusive + memorization.

Also found a twisted version of the questions asking to print all possible path instead of counting.  Wondering for the twisted version, if we have DP solution ?
Q: If there are n stairs, you can either take 1 or 2 steps at a time,  how may way can you finish the stairs. we can just using fib to calculate it.
What if you are ask print out all possible ways(not revision please). For example, if n = 5. we have  as solution.  pseudo code is welcome.

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 1, 1]
[1, 2, 2]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]


texts: Transform grammar for repeating characters into LL(1)

texts:
I have the following simple production rule:

S -> Sa | a

Which is left-recursive, and can recognize strings such as a or aa, etc

I tried to make it right-recursive, but I cannot find a way without creating ambigious grammars
(e.g.
 S -> aS'
S' -> a | aS'
)

Can someone explain how to make this grammar right-recursive and LL(1) form?


texts: What is the average height of a binary tree?

texts:
Is there any formal definition about the average height of a binary tree?

I have a tutorial question about finding the average height of a binary tree using the following two methods:

The natural solution might be to take the average length of all possible
paths from the root to a leaf, that is

$\qquad \displaystyle \operatorname{avh}_1(T) = \frac{1}{\text{# leaves in } T} \cdot \sum_{v \text{ leaf of } T} \operatorname{depth}(v)$.
Another option is to define it recursively, that is the average height for a node is the average over the average heights of the subtrees plus
one, that is

$\qquad \displaystyle \operatorname{avh}_2(N(l,r)) = \frac{\operatorname{avh}_2(l) + \operatorname{avh}_2(r)}{2} + 1$

with $\operatorname{avh}_2(l) = 1$ for leafs $l$ and $\operatorname{avh}_2(\_) = 0$ for empty slots.

Based on my current understanding, for example the average height of the tree $T$

    1
   / \
  2   3
 /
4

is $\operatorname{avh}_2(T) = 1.25$ by the second method, that is using recursion.

However, I still don't quite understand how to do the first one. $\operatorname{avh}_1(T) = (1+2)/2=1.5$ is not correct.


texts:
I am solving the following problem, motived by combinatorial optimization sampling proces.

I have restriction (0,1) matrix to restrict which item (column index) can be on current position (row index) at permutations. For example: 4x4 case (4 position permutations)

 1     1     1     0
 1     1     0     1
 1     0     1     1
 0     1     1     1

So, on position 4 (4th row at restriction matrix) is not allowed items 1, for example.

This restrictions produce the following list of possible permutations (earch row is one possible permutation):

 1     2     3     4
 1     2     4     3
 1     4     3     2
 2     1     3     4
 2     1     4     3
 2     4     1     3
 3     1     4     2
 3     2     1     4
 3     4     1     2

I am looking for algorithm to check if any sub-permutation, which is represented by first N < 4 positions, may correspond to any of possible permutation or not, without need to avaluate all possible permutations.

For example sub-permutation [1 2 3] is OK, but sub-permutation [3 4 2] is not.


texts: Given n drinks, find optimum way to spend money if for each drink the price and the expiration date is given

texts:
Let's say we are given $n$ types of drinks, integer $m$ representing the budget we have and integer $d$ representing the cost of delivery when we order some drinks. For each of the $n$ drinks we are given $P_i \text{ the price of i-th drink and } E_i - \text{expire date}$. For example $(3, 2)$ is representing drink with price $3$ for one bottle and the second number means that this drink can be used at most $2$ days after we buy it. One cannot drink drinks that have expired date of usage and one must drink exactly once per day.

We can order as many drinks as we want from each type, but each time we order we are paying $d$ dollars for delivery. Notice that the delivery doesn't matter in the day, so we can buy drink with exprite date $2$ and used it either today, tomorrow, or the day after tomorrow.

We want to maximize the number of drinks we will buy and drink.

I think that this problem can be solved with greedy strategy, but I'm not able to find anything that can lead to correct result and good time complexity.

Here are some things that I got so far:

We don't want to buy things that will be expired, so from each drink with price $P_i$ we will spend at most $P_i \cdot(E_i + 1)$

Because we may have big budget, it is good to find one way of buying drinks and use it couple times, until we don't run out of money from the budget.

We will first buy the cheaper drinks and for the more expensive ones we should decide should we make a new order, or buy some drinks from the next type.

I didn't got anything that lead to correct strategy, so please share some of your ideas.


texts: Functional Programming and Category Theory

texts:
I'm a math Ph.D. having done research in Algebraic Geometry and Algebraic Topology in grad school for my thesis and I've studied a fair amount of category theory in the process (e.g. having worked through most of "Categories for the Working Mathematician" as well as more specialized topics in Homological Algebra). Is there some good intro to functional programming that emphasizes the link with category theory in the process?
Context: In my workplace I've run into people that are into functional programming and like throwing around category theory jargon, but when you ask for details they typically fail to even be able to define what a category is. I'm hoping that there's more to it in programming than just abstract nonsense. In other words, for someone who actually knows category theory and has done some functional style programming (immutable classes, map, filter, reduce etc.) in imperative languages is there a good intro to FP in the context of category theory?


texts: Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$

texts:
I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement.

I know it's a proof by induction and that the inductive hypothesis is the following:

$
size(l) < 2^{h(l)} \\
size(r)  < 2^{h(r)}
$

where $l$ and $r$ are the left and right subtrees of the tree $t = \langle l,v,r \rangle$. Usually what I'd do is start from $size(\langle l,v,r \rangle)$ and work my way up to $< 2^{h(\langle l,v,r \rangle)}$. However I wasn't able.


texts:
Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices.

Let us define the problem $Clique-k$ as follows:
$$\{ \langle G \rangle \mid G \text{ is an undirected graph that contains a clique of size  } k\}$$

Question: Find a reduction $f$ from $Clique-6$ to $Clique-3$ such that $f$'s input is a graph $G$ with $n$ vertices, $f(G)$ is a graph with $O(n^2)$ vertices, and $$G \in Clique-6 \Leftrightarrow f(G) \in Clique-3$$

The required time complexity for the computation of $f$ is $O(n^4)$.

I am not sure how to approach this problem, and would be thankful if someone can provide insights \ directions to the solution.


texts: Minimal perfect hash function for set of integers

texts:
This might be a trivial question, but I have the following problem: I want to (perfectly) hash a number of lists of integers of length $n$, with all entries between $k_{min}$ and $k_{max}$. How can I construct a perfect hash function $h$ that takes such a list and outputs an $m$-bit number where $m$ is as small as possible? This is of course trivial if $k_{max} - k_{min} + 1$ is a power of two, e.g. if $n = 3$, $k_{max} = 15$ and $k_{min} = 0$, we can choose $m = 4$ and $h$ such that:
$$
\begin{align}
h([0, 0, 0]) &= \mathtt{0x000000} \\
h([0, 0, 1]) &= \mathtt{0x000001} \\
&\dots \\
h([15, 15, 15]) &= \mathtt{0xffffff}
\end{align}
$$
But what if $k_{max} - k_{min} + 1$ is not a power of two and I don't want to "round" up the number of bits used to represent every element because I want to save every single last bit of space?


texts: Does converting algorithms into elementary recursive form preserve runtime bounds?

texts:
There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. NP or P) are converted to elementary recursive function form, would they retain time complexity of the complexity class?

For example, in complexity class P, we know that problems take deterministic polynomial time to solve. Would an elementary recursive form of a solving algorithm retain this complexity?

By converting into elementary recursive form, I mean:

Yes, it is true that NP is in elementary, that is there is an elementary recursive algorithm that can solve NP problems, but what I ask is "will such algorithm retain its time complexity?" For example, complexity P has problems that can be solved in polynomial time complexity; however, it is not clear whether it will retain polynomial time complexity if the algorithm has to be in elementary recursive form.

By my understanding, elementary recursive algorithm would be the one that does not necessarily use "if and else".

Modification to the question: Let us say that for all decision problems we consider, there exist function problems that have same time complexity as their decision problem counterparts. For example, for 3-SAT problem with some input $x$, one satisfying assignment to the variables is treated as output. The reason why some people think this question is not valuable may be because for all decision problems, output is always either zero or one. So let us consider the function version of decision problems (that keeps time complexity).


texts: Prove you computed hash^r(input) for some cryptographic hash function

texts: What is the most efficient way to prove that a person computed r rounds of some cryptographic hash function (ex. sha256) on an input?. The trivial solution seems to be to show all r hashes, where value_i = hash(value_(i-1)) /forall i <= r, but this seems very space inefficient.


texts: When can we assuredly say that a function is little o of some other function?

texts:
I'm trying to determine a function $f(x)$ that is $O(f)$ but not $o(f)$ and also not $\Omega(f)$. Note the $f$ used in the asymptotic notation is not the same as $f(x)$.

Originally I thought of $f(x)=\log(x), O(x)$ but I am not convinced that $o(x)$ is invalid for this function.

Previously I thought it was, because I could always come up with some constant $c$ that would bring the function $x$ below $f(x)$. However, I could say the same for $o(2^x)$ because surely there is some infinitesimally small constant that I can find that will put $2^x$ below $f(x)$ at a given value $x$. Any advice in this matter?


texts: Weighting function for Non Uniform Learning

texts:
Consider a hypothesis class $H = \cup_{n=1}^{\infty} H_n$, where for every $n\in N$, $H_n$ is finite. Find a weighting function $w : H ->[0, 1]$ such that $\sum_{h \in H}  w(h) ≤ 1$ and so that for all $h \in H$, $w(h)$ is determined by $n(h) = min\{n :h \in H_n\} $
and by $|H_n(h)|$.
Since every $H_n$ is finite, it is agnostic PAC learnable. And hence their union  $H$ is non-uniform learnable. However I am unable to proceed from here.


texts:
I wanted to define syntax for a graph path considering it may branch out anywhere.

For instance, I have a path going from a to e following b, c, d: a, b, c, d, e.

Let's consider it (may) branches from b now: a, b, (x | y), d, e which actually means three different paths:

1) a, b, d, e

2) a, b, x, d, e

3) a, b, y, d, e

So, each parenthesis actually means "the path might either go through any of the nodes defined in the parenthesis connecting the node just before parenthesis and right after parenthesis or through none of the nodes defined in the parenthesis".

With more inner parenthesis, a single string line may generate even more paths. For instance: a, b, (x | (z | t) | y), d, e which means these five paths:

1) a, b, d, e

2) a, b, x, d, e

3) a, b, y, d, e

4) a, b, z, d, e

5) a, b, t, d, e

6) a, b, z, y, d, e

7) a, b, t, y, d, e

8) a, b, x, z, d, e

9) a, b, x, t, d, e

So, how can I define this syntax mathematically?


texts: How to define the potential function method for an online maximization problem?

texts:
From Online Computation and Competitive Analysis
By Allan Borodin, Ran El-Yaniv, to prove that an online algorithm $\text{ALG}$ is $c$-competitive for a minimization problem (i.e., there exists a constant $\alpha$ such that $\text{ALG}(I)\leq c\cdot \text{OPT}(I) +\alpha,$), it is sufficient to find a potential function $\Phi$ satisfying the following conditions with respect to any possible event sequence:

If only the adversary $\text{OPT}$ moves (i.e., is active) during event $e_i$ and pays $x$ for this move, then $\Delta\Phi=\Phi_i-\Phi_{i-1}\leqslant cx$; that is, $\Phi$ increases by at most $cx$.
If only $\text{ALG}$ moves during event $e_i$ and pays $x$ for this move, then $\Delta\Phi=\Phi_i-\Phi_{i-1}\leqslant -x$; that is, $\Phi$ decreases by at least $x$.
There exists a constant $b$ independent of the request sequence such that for all $i$, $\Phi_i\geqslant b$.

How this changes if the problem is a maximization problem instead of a minimization one? In other words, we would like to prove that there exists a constant $\beta$ such that $\text{OPT}(I)\leq c\cdot \text{ALG}(I)+\beta,$

I guess that the first bullet becomes "gains $x$ for this move, then $\Phi$ decreases by at least $x$" and the second bullet becomes "and gains $x$ for this move, then $\Phi$ increases by at most $cx$" but I am not sure. How to modify the above definition in order to deal with maximization problems?


texts: Kolmogorov-Complexity of strings in decidable languages

texts:
I just recently learned about Kolmogorov-Complexity and had an idea for giving an upper bound for strings in a decidable language. Is the following statement true?
Say we have a recursive language. Does this imply that there is a Turingmachine $M$ that given a $n\in\mathbb{N}$ as input, outputs the $n$th word in for example length-lexicographic order?
And can we use this TM to give an upper bound for the Kolmogorov-Complexity of a string in $L$, like $\vert\langle M, toBinaryString(n)\rangle\vert \leq c_1log(n)+\mathcal{O}(1) $ where $\langle \bullet, \bullet \rangle$ denotes a pairing function and $c_1$ is some constant?
Are there other ways to give an upper bound for strings in recursive enumerable languages?
Are there good examples for giving upper bounds for Kolmogorov-Complexity in books or papers?


texts: Avoiding correlated values and reduced collision resistance in multiple hash states

texts:
I need to design a hash function that fits this criteria:

Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system)
Produces an n-bit hash digest, greater or equal to 64-bit, with the expected collision probability of a hash of that size. Effectively combining multiple uncorrelated 32-bit states.

However, it seems care must be taken with this approach. I cannot verify it myself, but computing two 32-bit hashes using the same message but a different seed may cause more collisions than expected from a 64-bit hash, due to the two values being correlated.

This issue also seems to extends to the output of a single hash function that outputs two 32-bit results to form a 64-bit (which is exactly what I am trying to do).

I found MurmurHash64B (link to C++ code) which seemed almost ideal for my purpose. It produces a 64-bit hash using 32-bit operations at no significant performance cost.

But on the SMHasher wiki, the author mentions this about what I suspect to be the same function:

  MurmurHash2_x86_64 computes two 32-bit results in parallel and mixes
  them at the end, which is fast but means that collision resistance
  is only as good as a 32-bit hash. I suggest avoiding this variant.

Then I saw this exchange on the subject:

  Hacker News comment by martincmartin:
  Computing two 32-bit results in parallel and mixing them at the end does NOT mean collision resistance is only as good as a 32-bit hash. For that, you need to compute ONE 32-bit result, then transform it into a 64-bit result.

  Hacker News comment (reply) by finnw
  Depends whether the two 32-bit hashes are correlated with each other. If there is no correlation then a pair of 32-bit hashes is no more likely to collide than a single 64-bit hash. But this is difficult to achieve, and you should not assume (for example) running the same algorithm twice with different initial states will produce uncorrelated hashes.

So then, is this function really not as good as a 64-bit hash? A naive test: Searching for a collision in state h1 doesn't seem to cause collisions in state h2. Is it simply not sufficiently mixing the states? It only mixes h1 and h2 at the end, not within the input mixing phase.

MD5 for example which also uses 32-bit arithmetic, computes four hash states which I assume must not suffer from this issue. There also exists a MurmurHash3_x86_128 which computes a 128-bit hash using four 32-bit states and appears to mix it more thoroughly (which has no mention of being weaker by the same author).

So I am wondering how can it be shown that MurmurHash64B (or a similar function) has correlated values that could result in reduced collision resistance than expected of the digest size.


texts:
I try to teach myself the usage of bison. The manpage bison(1) says about bison:

  Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser tables.

What is an IELR-parser? All relevant articles I found on the world wide web are paywalled.


texts: Why do we use stacks and not queues on system-level?

texts:
From low OS-level function calls, to memory allocated to an application, all will primarily take a stack to perform LIFO operations.

Why don't we use queues and FIFO operations? It's just a matter of moving pointers anyway.


texts: Is a regular grammar valid if it only contains production rules that have nonterminals in the right operand?

texts:
For example:

S -> Sa

Let's say the alphabet is {a} and that is the ONLY production rule of the grammar. Is that grammar valid regular grammar ? Or valid grammar at all? Can it be a context free grammar, but not a regular one ?

As far as I can think... a grammar tree built on it will never end, it will never have only leaves so there is NO  string that is accepted or generated by this grammar so it should not be considered a valid grammar.

However I did not see in the definition of grammar this specific constraint of a grammar, that it necessarily should have a production rule with ONLY terminal symbols on the right hand side of a production rule.


texts: If i want to save something in a computer such as a number 1 that would be 001 but if i save 001 in a computer how would the computer know that 001 is 1. Should we first save  the number 1 in memory and tell the computer that hey this is 1 and it is 001 in your language. Basically if we want to save something, how would a computer know what are we saving to determine its output. Like if i say the computer hey i wanna save 10011 and i actually intended it to be The letter A how would the computer know 10011 is A?


texts: Is there any practical trick to mentally count in Gray code?

texts:
When I was fairly young, I taught myself to count in binary. I thought it would be a fun party trick to impress people. I soon found out that it was not.

Over the years I've come to appreciate Gray code/reflected binary code for its property of only flipping one bit for each increment/decrement of the underlying count. But I've always been bothered by the fact that, if I wanted to mentally take any arbitrary Gray code and add or subtract 1 from it, I'd have to either convert it to and then back from its numeric value, or construct a table to work out what the next code should be.

It seems to me that there should be some trick that a person with "average" short term memory and addition skills should be able to do to take any arbitrary value in Gray code and figure out which bit to flip to get the next value... But I've never found it.

Does such a thing exist?


texts: What would dynamically-typed languages actually do if type enforcement was removed?

texts:
I program in Python, which is a well-known dynamically typed language. I understand dynamic typing to mean mainly that "operations" (in a loose sense) in the language are either allowed or denied (raise an exception) based on the type of their operands, and that this type-checking is deferred as long as possible. My question is this: if that is what a fair characterization of dynamic languages, what would happen if the run-time type checking was removed?

It seems to me that if you want to make a meaningful distinction between a dynamically typed language like Python and an untyped language, you would have to define what actually would happen in the untyped language in situations in which the type system of a dynamic language would take action. For example, in Python, if I attempt to subtract an Integer from a String, e.g., "spam" - 5, I receive a TypeError. If that's what makes Python dynamically typed, what would an "untyped Python" do in that situation?


texts:
Written in English, does "the set S contains only members of set T" imply that S does contain some member of set T?

How would this relationship be written formally?


texts: Reinforcement learning - state space and action space

texts:
I am working on a reinforcement learning strategy for parameter control of a local search heuristic.

The complete state for this RL problem can be defined as $S = \{s, p\}$, where $s$ and $p$ are respectively the current solution and the vector of current parameter values.

An action correponds to raplacing or maintaining the vector of parameters $p$ with a new configuration.

Since the above formulation of the state space is impractical, would it be reasonable to represent the state only as $S = p$? In this case, the state space basically becomes equivalent to the action space.


texts: Can bar codes theoretically be considered a type of digital memory?

texts:
Bar codes act just like any other device that contains data that you can read from. Can bar codes thus be considered a type of computer memory?

I believe the principle is quite similar to the optical discs like CDs or DVDs.

They work just like an SD memory card but instead of a card reader we use barcode scanner to read the digital data stored in the bar code.

Can bar codes be useful in other types of applications instead of identifying products? Can barcodes or similar technology be used in computers?


texts: Fastest algorithm to find whether a list contains a word?

texts:
Given an unordered list of words, what's quickest way to test whether a certain word is in that list?

I can't think of another way to do this other than just going through each element in the list and checking whether it's the word I want.


texts: Approximate value iteration for continuous state space MDPs

texts: I have a continuous state space MDP as a generative model. I input the state and action and it outputs the reward and the next state. Assume that I sampled $n$ state-reward-states. I wonder how I can implement value iteration using a function approximator. I couldn't find any implementation example online. Can you please point me some references?


texts: Worst Case Space Complexity of Merge Sort and Bubble Sort

texts: I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(n), linear? All space we need is the exact number of the elements, right? Please enlighten me.


texts: Time complexity for computing the highest degree vertex

texts:
Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format.
What is the time complexity of finding the highest-degree vertex, assuming the vertices are given to you in no particular order?
The answer is $ \mathcal{O}(n^2) $ but I don't know how to get there.
I divided this question in two parts:

time complexity of computing a degree of a given vertex

finding the vertex with highest degree

This is what I think:
It takes $\mathcal{O}(n)$ to compute the degree of a given vertex $i$ (sum $n$ values in row $i$). Doing this for all vertices, we get $\mathcal{O}(n^2)$.
But then we need $n-1$ comparisons in order to conclude which vertex has highest degree, which would take $\mathcal{O}(n)$.
So putting it all together we would get $\mathcal{O(n\times n\times n)}=\mathcal{O}(n^3)$ (or is it $\mathcal{O}(n^2+n)=\mathcal{O}(n^2)$?)
Someting is wrong with my reasoning but I don't know what. Could you tell me my mistake?


texts: Dynamic list for frame pointers and static list of nested activation frames

texts:
I am going through the book Compiler Construction by Niklaus Wirth.  The following is what I feel to be stated summarily by his lesson on procedure calls:

The compilation of a procedure call is the allocation of a block of stack memory. It starts with the base address which is stored in the frame pointer and the local variables are allocated addresses with respect to it with negative offsets.
For every procedure the block of stack memory is termed as its stack frame or the activation frame and a DYNAMIC LIST is maintained of the base pointers of the  stack frame

Then an illustration of an situation is made where nested procedure calls are made with the following code snippet:

PROCEDURE P; P 0
  VAR x: INTEGER; x 1
  PROCEDURE Q; Q 1
  VAR y: INTEGER; y 2
    PROCEDURE R; R 2
    VAR z: INTEGER; z 3
    BEGIN x := y + z
    END R;
  BEGIN R
  END Q ;
  PROCEDURE S; S 1
  BEGIN Q
  END S;
BEGIN Q; S
END P;

Now it is said that  assuming that access of the local variables of R by traversing the dynamic list, it is possible that call to R can be made through the sequence  P → S → Q → R. As such a second list of activation records is necessary, denoting the nestedness of the procedures.

Why is it necessary to have a static list of the activation frames of the procedures and the procedures nested in them?

At the end of a procedure, we can restore the value of the frame pointer by taking the previous value in the dynamic list and the return address would be restored from the register where it was saved. I don't see why a static list linking the activation frames of the nested procedure is required.

It has been suggested that the following question :

Static scope and dynamic scope

might be having the answer to my question and the questions are co-duplicate to each other but I would beg to differ as :

The suggested question is more about evaluation strategy of a function , more focused on the implementation of argument passing to functions , however my question can be said to be  about "returning the control to the calling procedure" or "linking of nested procedures ".
My question basically asks the reasons for which Wirth considers maintaining of one static list as a necessity  . The following is the link to With's book  and my question is centered around the topic "addressing of variables" in pages 72 and 73 .

ON WHY I SAID THAT MY QUESTION IS MORE ABOUT "returning the control to the calling procedure"

I know Wirth starts up the topic with the problem of accessing the variables of an internal procedure or nested procedure but since the dynamic list of frame pointers is maintained to restore the registers from activation frames on return of control to the calling procedure that is why I said that my question is more about the "returning the control to the calling procedure".


texts: What are the minimum memory requirments a microprocessors must have to perform any calculation?

texts:
Please excuse my ignorance in low level things. A lot of the written below might be very wrong.

As far as I understand (and I might be very wrong), there are two types of memory locations a microprocessor can have: registers and stacks.

My question is what is the most basic set of memory locatiins a microprocessor must have to perform an arithmetic calculation of unlimited complexity, such as : 12 / (11 / (4 - 7) * 31) + 8.

For example one register is obviously not enough. What about three registers? Or one stack? Or a stack and a register? Given e.g. one stack and a register, can the CPU perform any calculation?

The CPU should be able to perform any calculation like in the example shown above.


texts: Is the language of turing machines, which return epsilon on its own encoding, decidable?

texts:
Is the language $\{ \langle M\rangle | f(\langle M\rangle)=\epsilon\}$ decidable? $f()$ means, that the turing machine returns $\epsilon$ on its own encoding and $\langle M\rangle$ stands for the encoding (a "string-version" of the TM).

I have no idea how I should start. How can I decide, if I use a reduction, a sub program technique or the diagonalizability? I would really appreciate if you could help me, thanks! :)


texts:
Given a set $S$ of points $p_1,..,p_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear.

The problem is I started with general definition but I cannot continue to actually solving the problem.

What can we say about collinear points in general, 3 points $a,b,c$ are collinear if the distance $d(a,c) = d(a,b)+d(b,c)$ in the case when $b$ is between $a$ and $c$.

The naive approach has $O(n(n-1)(n-2))=O(n^3)$ time complexity.

How to solve this problem, what should be the next step?


texts: Approximate minimum-weighted tree decomposition on complete graphs

texts:
Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By $(d, h)$-tree-decomposition, I mean to divide the vertices $V$ into $k$ trees, such that the height of each tree is $h$, and each non-leaf node has $d$ children.

I know it is definitely $\text{NP}$-Hard, since minimum $(1, |V|-1)$-tree-decomposition is the minimum Hamilton path. But are there any good approximation algorithms?


texts: Difference between Data point, attribute, feature?

texts:
Can anyone tell me the difference between the following in data mining? I am taking a class this semester and the professor is using the terms so frequently, I don't know what these mean anymore.

Data point
attribute
feature


texts:
In the network clearance problem,
we are given a simple undirected graph with a capacity assigned to each edge (and/or to each vertex).
Each edge can transport up to its capacity each time step (i.e., if the edge has capacity 2, it can transport 2 units of flow in each time step).
Each vertex is either a source vertex ($\in S$) or a destination vertex ($\in T$).
Initially, there is a constant, possibly zero, amount of a substance in each of the nodes in $S$.
The capacity of $T$ vertices is infinite.
The question is how long does it take to transfer the substance from all the $S$ vertices to some $T$ vertices.

This can be seen as a network of tanks connected with pipes.
Each tank in set $S$ contains some water.
We want to empty the water from tanks $S$ to tanks $T$ considering the limited capacity of the pipes.

The network clearance problem seems similar to the network flow problem. The main difference is that in the former problem, there is a limited amount of the substance, not a continuous demand and we want to minimize the time rather than maximizing the flow. However, it seems to me that a variation of the residual graph can be used to solve this problem.

I came up with a solution that seems promising. But, I am still interested in related work or better algorithms. So, if you know other related work to this problem or a more efficient algorithm, please inform me.

My algorithm actually works on the decision version of the network clearance problem. Given a time bound $b$, the question is that if it is possible to clear the network in $b$ units of time or not.

The algorithm that I came up with is as follows.
For a given network $G$, create a new graph $G'$ with all the nodes and edges of $G$. Set the capacity of each edge $e$ of $G'$ to $b$ times the capacity of the corresponding edge in $G$.
Add two vertices $s$ and $t$ to $G'$.
For each vertex $v \in S$ add an edge $\langle s,v \rangle$ to $G'$ with capacity equal to demand of $v$ in $G$.
For each $u \in T$ add an edge $\langle u, t \rangle$ to $G'$ with capacity infinity.

The answer to the decision question is yes if and only if the maximum flow between $s$ and $t$ in $G'$ is equal to summation of demands in $G$.

One can simply use one of the known algorithms for Maximum Flow to solve the decision problem.
Having the solution to the decision version, we can binary search over the bound to find the smallest bound for which the answer to the question is yes.

Do you know of a better algorithm, or a reference in the literature where this problem has been considered before?


texts: Checking position of a point relative to convex polygon in $\mathbb{R}^2$

texts:
Just as the title says, I wish to check the position of a point relative to polygon in $\mathbb{R}^2$. My take on this problem is the following:

1) draw a horizontal line to the right of each point and extend it to "infinity".
2) cnt =  number of times the line intersects with polygon edges.
3) if(cnt is odd or point is on edge of polygon )
      point is inside the polygon
   else
      point is outside polygon

Even though this algorithm works for all types of polygons, it does not use the fact that the polygon is convex. Got any idea how can I optimize it so it makes use of its convexity?


texts: When is it best to use the second chance replacement algorithm?

texts:
I'm going through 'Operating Concepts' by Silberschatz, Galvin and Gagne (The Dinosaur Book) and it mentions the Second-Chance Algorithm (not enhanced) as an improvement on the FIFO replacement algorithm.

My question is, is there ever a case where this algorithm would perform better than, say, the Least Recently Used algorithm or even something like the Farthest-in-Future Algorithm? The book describes how the algorithm works but doesn't offer a lot of information on when it would be useful, other than just in improving 'FIFO'.

To add to this, is there ever a case where 'second chance' would out preform LRU? I'm assuming the answer is yes, as no algorithm is perfect for every situation.


texts:
I'm new to writing math notation that describes algorithms and I need to translate some python code. Does the notation structure below correctly describe a nested for-loop that for-each value in p iterates over all other values in p?

Example code
function(p):
    for a in p:
       for b in p:
         // do something with a and b...


texts: Ordering a list of lists subject to constraints

texts:
I have encountered a surprisingly challenging problem arranging a matrix-like (List of Lists) of values subject to the following constraints (or deciding it is not possible):

A matrix of m randomly generated rows with up to n distinct values (no repeats within the row) arrange the matrix such that the following holds (if possible):

1) The matrix must be "lower triangular"; the rows must be ordered in ascending lengths so the only "gaps" are in the top right corner

2) If a value appears in more than one row it must be in the same column (i.e. rearranging the order of values in a row is allowed).

Example 1 - which has a solution

A B
C E D
C A B

becomes (as one solution)

A B
E D C
A B C

since A, B and C all appear in columns 1, 2 and 3, respectively.

Example 2 - which has no solution

A B C
A B D
C B D

has no solution since the constraints require the third row to have the C and D in the third column which is not possible.

In my attempts to solve this naively (e.g. by sorting shortest rows to longest and then trying to order the rows from "most in common" to least and then simple reordering within the row) there are always scenarios that it thinks aren't solvable but are.  In other words backtracking/exhaustive search appears to be required, which is OK but I haven't yet struck onto a nice concise (ideally functional) algorithm for this.


texts: Minimum number of shopping trips for a group of people to buy presents for each other

texts:
We have a group of $n$ people. We are given a list of who must buy presents for whom within the group. Each person might need to buy/receive any number of presents, or possibly none at all. In a shopping trip, a subset of the people travel together to the same store, and buy presents for anyone who is not present at the store. They may not buy presents for someone else on the same shopping trip because then it wouldn't be a surprise. A person may go on multiple shopping trips. We want to minimize the total number of shopping trips required for everyone to buy all the presents they need.

As an example, consider the case where there are 5 people, and each must buy presents for every other person in the group. Let the people be numbered 1 to 5.  This can be done in 4 shopping trips, as shown:

Trip 1: 1, 2, 3 go shopping
Trip 2: 1, 4, 5 go shopping
Trip 3: 2, 4 go shopping
Trip 4: 3, 5 go shopping

How would I go about solving this problem? It is obvious that the input can be represented by a directed graph, but I don't know where to go from there. Someone brought up the biclique cover problem, but while similar, it does not answer this question.

We can think of the input as a directed graph $G$ on $n$ vertices, where the edge $(u,v)$ means that person $u$ must buy a present for person $v$.   The goal is to find a set of bicliques $(S_1,T_1),\dots,(S_k,T_k)$ such that $k$ is minimal and the edge set $E$ of the graph is a subset of $\cup_i (S_i \times T_i)$.  Also, in extending the definition of bicliques to a directed graph, a biclique $(S_i,T_i)$ only contains edges which map $S_i$ to $T_i$.  This differs from the biclique cover problem in that we don't require each biclique to be a subgraph of $G$ (we don't require $S_i \times T_i \subseteq E$ for each $i$).

Specifically, I will accept an answer that either:

Demonstrates that this problem is NP-hard or
Presents a polynomial time algorithm that answers this question exactly (no approximants or upper bounds)

For the record, I did not see this problem anywhere, I am just wondering about it for my own curiousity.


texts: Previous approaches for encoding physical affordances

texts:
From Wikipedia, an affordance is:

  a relation between an object or an environment and an organism, that
  affords the opportunity for that organism to perform an action

Previously what approaches have been used to encode this in an embodied intelligence? In other words, has anyone tried to get a robot to understand the concept of affordances in the real world? If so, how?

A couple examples of tasks that I could imagine to test this concept out:

A robot encoded with the ability to evaluate which objects are stackable understands the affordance of stacking.
A robot encoded with the ability to evaluate which object roll well could choose from a set of objects which would roll the best

For background, I'm coming from a cognitive science perspective where the most effective way I've seen for approaching ambiguous input and trying to find underlying patterns is with Vector Symbolic Architectures, but I couldn't think of a way that they could be applied here.


texts: Is every regular/context free langauge decidable in LogSpace?

texts: I know all the regular languages are decidable but not sure whether it can be done in LogSpace.


texts:
If I have an address bus of 64K, i.e. it can access 64*1024 or 65536 locations, should I also have a memory chip with 65536 locations in it?
What I'm trying to ask is that do all the 65536 locations that the address bus can address have a corresponding memory location? Or can some address bus values go unused? (Like when I have 65536 address locations but my memory chip has only 32768 locations) Is such a combination acceptable?


texts: Complexity simplification for complexity that consists of partial multiplication

texts:
For the algorithm that I have written the complexity is something like:

a * e(A) + b * e(B) + b * e(C) + ...

Where a represents the instance count of some node A and e(A) the edges outgoing of node A. Also if we say:

a + b + c + ... = n

e(A) + e(B) + e(C) + ... = e

Then I can say that the complexity is
O(n*e)

Is there a way to make it tighter? The values for e(...) are usually not too high so doing e*n and counting all edges for each node seems a bit of a high overstatement. This seems like a common situation so I was wondering if there was a good known way to express this complexity to convey that it is not actually that extreme.


texts: Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$

texts:
Possible Duplicate:
  Solving or approximating recurrence relations for sequences of numbers

I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is  $ T(n) = O(n \log(n))$

But how do you get to that point? I don't understand when it says put t into the equation repeatedly until it drops out...

Any help?


texts:
I was wondering how to create a TM that it's $L(M) = 10$, I think it would be recognizable, but I need help building that TM.
so far I have this pseudocode:
$$
N:" ∀x∈sigma^*
$$
$run$ $N$ $on$ $x$
if N acc $then$ $i=i+1$
if i==11 then $stop$
please help solve this


texts: Looking for a dictionary of math/CS notation

texts:
There is an at-times dizzying array of symbols used in math and CS papers. Yet many assume basic familiarity that seems rarely taught in one place. I am looking for a dictionary something like the following, especially from a CS perspective.

It would list all the basic mathematical symbols and give their meanings and examples. It would talk about symbols that are sometimes used in equivalent ways. It would note common beginner mistakes.
It would talk about the subtleties surrounding different meanings of a single symbol (much like multiple definitions of the same word in a dictionary).
It would not merely be a very terse description of each symbol, such as one word descriptions like "subset".
It would show how symbols are sometimes "overloaded". For example, $\binom{x}{y}$ could have $z$ as an integer, but sometimes $z$ can be a set with this notation and it means to choose elements from this set. $[n]$ sometimes means a set of integers $1 \ldots n$, or other times its a one-element array.
It might talk about how to describe all kinds of different "objects" in terms of different symbols or equivalent ways of referring to them (but which are more clear) and the operations possible on those objects. In other words, kind of like an API for math objects.

I.e. it would be also at times a "style manual" for different nuances in how to present mathematical writing. This would be a very helpful resource for anyone writing questions in mathematical stackexchanges, where many questions fail to make sense based on not fitting into tricky mathematical conventions.

Some book introductions have many of these features. however ideally it would be a separate treatment. Also, ideally of course it would be online. There are tables of latex symbols, but they don't really fulfill many of the above criteria.

  Has anyone seen a "dictionary of symbols" that matches these features?

(Alternatively, it seems like an excellent wiki or FAQ project if good references like this don't exist.)


texts: Is Artificial intelligence simply taking decisions on the basis of values produced by a machine learning model

texts:
I am researching on AI and its working. Whenever I try to search for AI algorithms, ML algorithms come up. Then, I read the differences between ML & AI. One of the key points mentioned was "AI is decision making" & "Machine learning is generating values and learn new things".

I come up with a conclusion that ML allows us to take generate some sort of values and using AI we can make decisions with those values.

But I am confused with "The weather forecast" problem. Our machine learning model will directly generate the decision that will it rain or not? Is our ML model lies in the AI domain or I am wrong? Help me!


texts:
I'm trying to decide which of the following statements are true:

$\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$
$\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$
$\mathsf{NSpace}(\sqrt n) = \mathsf{coNSpace}(\sqrt n)$

I thought immediately that (1) is correct since $\lg \lg n < \lg n$, and since $\mathsf{NL} = \mathsf{coNL}$, I thought that the statement yields from it. I thought that since we don't know if $\mathsf{P} = \mathsf{PSPACE}$, we can't say anything about a class which is bigger than $\lg n$ and a subset of $P$.

But it is exactly the opposite. (1) is not necessarily true while (2) and (3) are necessarily true. Why is that?

The question is from a past midterm that I'm solving now.


texts: what are the limitations of definite clause grammars?

texts:
Definite clause grammars have been around for a long time but there are not the answer to every parsing problem or we would not need to invent new formalisms. Are there any languages they cannot express in principle?

Why are they not used more?

https://www3.cs.stonybrook.edu/~warren/xsbbook/node10.html
partially answers the second question but not the first.

  Prolog execution of the underlying deterministic machines and its use
  of a stack to schedule them naturally yields a recursive descent
  parser. And it is well known that a recursive descent parser cannot
  handle left-recursive grammars; it will go into an infinite loop on
  them. So in Prolog we must avoid left-recursive grammars.

  Also a recursive descent parser can be quite inefficient on some
  grammars, because it may re-parse the same substring many times. In
  fact, there are grammars for which recursive descent parsers take time
  exponential in the length of the input string. When using DCGs in
  Prolog, the programmer must be aware of these limitations and program
  around them. It is for this reason that some people respond to the
  claim that "You get a parser for free with Prolog" with "Maybe, but
  it's not a parser I want to use."

Its not clear if its a fundamental limitation of DCGs themselves rather than just the Prolog implementation. I don't see why Prolog couldn't memoize common substrings like a chart parser (most Prolog implementations memoise already).

See also my related question Is there any difference in the expressiveness of boolean grammars versus definite clause grammars?


texts: Given a regular language, calculate its equivalence classes

texts:
I was given the following regular language:

For any $n$, the language $L_{n}$ consists of all words over $Σ = \{0, 1\}$ whose $n$th character
from the end is 1.

I know it's regular because it can be expressed as a regular expression ($\Sigma^{*}1\Sigma^{n-1}$), and I constructed a DFA and an NFA for it. I need to calculate its equivalence classes. I thought that the equivalence classes will be words that have 1 in the same place later in the word - for example one of the classes will be $L(\Sigma^{*}1\Sigma^{n-2})$, because no matter what digit will be added to all these words, the new words will belong to the original language. But I'm not sure I'm on the right track. I would love it if I could understand the process of thinking on this kind of question.


texts: What's the time complexity of this algorithm? And Why?

texts:
I am stuck by analyzing the time complexity of the following algorithm:

def fun (r, k, d, p):
    if d > p:
        return r
    if d = 0 and p = 0:
        r <- r + k
        return r
    if d > 0:
        fun (r, k + 1, d - 1, p)
    if p > 0:
        fun (r, k - 1, d, p - 1)

The root call will be fun (0, 0, n, n), and n is the size of the problem.

I guess that: The recurrence relation is $ T(n, n) = T(n-1, n) + T(n, n-1)$, which is equivalent to $T(2n) = 2T(2n-1) \iff T(m) = 2T(m - 1)$, and so $O(2^m) \iff O(4^n)$.

Is my analysis correct (I know it's not very complete and exact)? If it does have serious flaw, please point it out or show me a correct and complete proof on the time complexity of this algorithm.


texts: What would NP-complete solution in O(2^N/B) mean?

texts:
Suppose we had an algorithm that solved an NP-complete problem (SAT, TSP, etc.) in time $O(2^{N/B})$ where $B>2$ is an input to the algorithm, along with the instance to be solved.

So for $B < N$, we have a reduced exponential growth runtime, but for $B \geq N$ we actually have a constant runtime.

What would this say about P vs NP?  Does this complexity class already exist or would it be a new one?  Would this add anything significant to our current understanding of complexity theory?


texts:
I went through a question asking me to categorize the following grammar.

$$S → AA, S → AB, A → a, A→BB, B → b, B → e$$

From the production rules, clearly it is Context-Free. But it accepts a finite set of strings.
$\{e, a, aa, ab, abb, ba, bba, b, bb, bbb, bbbb\}$
which is regular language.

So, is the above grammar regular? Though it does not follow from the rules.

Basically my question is: Is the grammar $\{S → AA, A → a\}$ regular?.


texts:
I am studying computational complexity and i am trying to solve this problem.
We are given a (non-bipartite) complete graph:

G = (V, W, E)

where the vertices can be divided in two classes V and W and the edges between any two vertices are weighted either 1 or 0.
w(x, y) = {0, 1} ∀ x, y ∊ V ∪ W

We need to:

calculate a subset I ⊆ V ∪ W that maximizes the sum of the weights of the edges that link the elements of I, divided by the I cardinality.
max(1 / |I| ∑ w(x, y) ∀ x, y ∊ I)
The calculated subset I must have the same number of vertices of V and W.
|I ∩ V| = |I ∩ W|

I would need to prove that this problem is NP-complete.

I have thought about reducing the problem to a vertex cover, removing the incident vertices to a 0 edge, but that would compromise the optimal solution.
And even considered this, i have found many difficulties trying to figure out a optimal certifier for the algorithm, which would prove the problem to be at least NP.
Any clues on a strategy to follow?


texts: Is it possible to use a copy-on-write strategy to modify a B+ tree?

texts:
Alright, I'm not sure if this is more of a stack overflow question, but I'm going to try here because you folks seem more suited.

CouchDB makes an interesting claim about using an "append only" B+ tree to index its documents. Specifically...

  "In a B-tree, data is kept only in leaf nodes. CouchDB B-trees append
  data only to the database file that keeps the B-tree on disk and grows
  only at the end. Add a new document? The file grows at the end. Delete
  a document? That gets recorded at the end of the file."

and

  "CouchDB is actually using a B+ tree, which is a slight variation of
  the B-tree that trades a bit of (disk) space for speed. When we say
  B-tree, we mean CouchDB’s B+ tree."

SOURCE: CouchDB Documentation

This paper, describes the problem with an "append only" or "copy on write" implementation of a B+ tree. It suggests that such optimistic concurrency strategies are only available to a standard B tree. Specifically...

  "In a regular b-tree leaves are chained together. This is used for
  tree    rebalancing and range lookups. In a b-tree that is updated
  using copy-on- write leaves cannot be linked together. For example,
  Figure 2 shows a tree whose rightmost leaf node is C and where the
  leaves are linked from left to right. If C is updated the entire tree
  needs to be shadowed. Without leaf-pointers only C, B, and A require
  shadowing."

SOURCE: Rodeh O.

So the actual question...

Is possible to implement a copy-on-write B+ tree?


texts: Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths

texts:
The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below.

  The notation $\delta(u, v)$ is used to denote shortest-path from $u$  to $v$.

Question 1:

  Because of how we chose $v$, we know that the distance of vertex $u$ from the source $s$ did not decrease, i.e., $\delta_{f'}(s, u) \geq \delta_{f}(s, u)$

Why the shortest-path from $s$ to $u$ after the augmentation of flow $f$ must be greater than or equal to the distance before the augmentation ? How it is possible to have greater distance that it was ? The augmentation only removes the edge $(u, v)$. But, the vertex $u$ still in place, isn't it must be strictly equal ?

Question 2:

  If we had $(u, v) \in E_f$, then we would also have $\delta_f(s,v) \leq \delta_f(s, u) + 1$

This looks like ok for me to have such case. We claim that distance from $s$ to $v$ is less than or equal to the distance from $s$ to $u$ plus 1. But in the graph before the first augmentation this case must be true. It is false for less than case, but true for equal case.

Question 3:

  How can we have $(u, v) \notin E_f$ and $(u, v) \in E_{f'}$ ? The augmentation must have increased the flow from $v$ to $u$. The Edmonds-Karp algorithm always augments flow along shortest paths, and therefore the shortest path from $s$ to $u$ in $G_f$ has $(v, u)$ as its last edge.

The edge set $E_f$ is before the first augmentation and $E_{f'}$ is after it. The first augmentation must remove the edge $(u, v)$ and put the reverse edge $(v, u)$ into the edge set $E_{f'}$, but not the same edge $(u, v)$. That is why how we can have $(u, v)$ in $E_{f'}$ ?