texts: Why is Byzantine Generals Problem with traitors possible?

texts:
My question is what makes the Byzantine Generals Problem possible to solve in some cases where traitors exist, for example in the case where there are 4 generals with 1 traitor?

If the generals must either all attack or all retreat at the same time, then surely the traitorous general can simply say "yeah sure we'll attack" and then retreat as the other 3 generals plunge into their deaths.

I suspect the answer has something to do with different variations of the problem, but I was unable to find any other definition for the Byzantine Generals Problem other than "all must either attack or retreat". Almost all of the search results are blockchain related advertisement, and the Wikipedia article doesn't provide a different definition for the goal of the generals.


texts: Correct name for a recursive descent parser that uses loops to handle left recursion?

texts:
This grammar is left recursive:

Expression  ::= AdditionExpression

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

MultiplicationExpression    ::=
    Term
        | MultiplicationExpression '*' Term
        | MultiplicationExpression '/' Term

Term    ::=
    Number
        | '(' AdditionExpression ')'

Number  ::=
    [+-]?[0-9]+(\.[0-9]+)?

So in theory, recursive descent won't work. But by exploiting the properties of the grammar that each left-recursive rule corresponds to a specific precedence level, and that lookahead of a single token is enough to choose the correct production, the left-recursive rules can be individually parsed with while loops.

For example, to parse the AdditionExpression non-terminal, this pseudocode suffices:

function parse_addition_expression() {
    num = parse_multiplication_expression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            num += parse_multiplication_expression()
        else if (current_token == MINUS)
            num -= parse_multiplication_expression()
        else {
            unget_token()
            return num
        }
    }
    return num
}

What is the correct name for this type of parser? This informative article only refers to it as the "Classic Solution": https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

There must be a proper name for this type of parser.


texts: Why are division/floating points inefficient in comparison to integer addition/multiplication/subtraction?

texts: Why does Bresenham's line algorithm eliminate dy/dx division and the multiplication of that (potentially floating point) number?


texts: Do all Regular Expressions describe Regular Languages?

texts:
I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent regular language? Or is the set of regular languages a subset of regular expressions?

If this is not the case, is there a good example of a regular expression that does not have an equivalent regular language?


texts: Parallized algorithm for getting the frequencies of numbers in an array

texts:
I have an array $A$ of length $n$, containing integers between $0$ and $n-1$ inclusively. I would like to convert this to an array of frequencies $F$, that is, $F[i]$ should be the number of times $i$ appears in the array $A$. For example, $A=[1,3,1,1,0]$ would be mapped to $F=[1,3,0,1,0]$. There is an easy algorithm for this, however I would like to do this efficiently in parallel. Here is my first attempt at doing so:
Let $n = p*k$ where $p$ is the number of threads, $k$ is the number of indices each thread will process and $n$ is the total number of indices (length of A). Each thread is given a range containing $k$ indices and all threads have access to an array $F$ that will be the frequency list. $F[i]$ starts off containing $0$ but after successfully running the algorithm, will contain the frequency of index $i$ in the array $A$.
Each thread runs the following pseudo code:
for i in given range:
  F[A[i]] += 1

Assuming a mutex is used, I think this algorithm works fine, however it runs into efficiency problems because all threads may want to increase the same index of $F$ at the same time. For example, this would happen if every index of $A$ contains the same number.
I would like an algorithm which avoids this problem and is deterministic. Ideally the time complexity should be something like $O(n/p)$. This is probably not possible of course, but I would like to be able to take at least some advantage of the parallelism, even when assuming a worst case input.


texts: Functional problem and verifying solutions

texts:
Is there a functional problem for which there is an algorithm that can decide if a solution is a solution or not in polynomial time but we can't find a solution in polynomial time?

Let FP be the class of functional problems.

Update:
Every problem in FP, say $a$, has a correspondent decisione problem $a'$ (the associated decision problem $a'$ is the problem where we ask if a possible solution is a solution), I ask if there is a functional problem $a$ for which $a'$ is in P but $a$ is NOT in FP.

In this link: Hamiltonian cycle, verifying and finding

we have instead a functional problem HC (hamiltonian cycle) for which HC' is P and HC is in FP.

Intuitively I think that the kind of problems I search, should be 'more' the problem of kind of HC. But maybe the hard part, given $a$ (with $a'$ in P), is to prove that $a$ is NOT in FP.


texts: Efficient algorithm for swapping dimensions for an N-dimensional matrix

texts:
I have data stored in N-dimensional matrixes (i.e. Arrays nested N layers deep). Is there a good standard solution - other than brute force - to the following two problems

I want to swap 2 dimensions for each other e.g. a 6 x 5 x 4 x 3 matrix will become a 6 x 4 x 5 x 3 matrix
I want to raise a dimension to being the 0th dimension, or lower it to be the Nth e.g. 6 x 5 x 4 x 3 x 2 goes to 4 x 6 x 5 x 3 x 2 or 6 x 5 x 3 x 4 x 2

I'm writing in JavaScript so a solution involving recursive functional programming would seem like a good route to take, but I'm struggling to think of a way to avoid the process getting overly complex and inefficient.


texts: Dividing students into 4 groups based on preferences is NP-complete

texts:
Given a set of students $H$ of size $n$, and a set $E \subseteq H \times H $ of pairs of students that dislike each other, we want to determine whether it's possible to divide them into $4$ groups such that:

no two students that dislike each other end up in the same group,
the size of each group must be at least $\frac{n}{5}$.

I want to prove that this problem is NP-complete. I suspect that I could use the NP-completeness of  the independence set problem, yet I have some problems with finding an appropriate reduction.
Let $G = (H, E)$ an undirected graph - each edge represents two students that dislike each other.
For the groups to be of the required size, their size must be $k \in \left [\frac{n}{5}, \frac{2n}{5} \right ] \cap \mathbb{N}$. I could then try checking whether there is an independence set of size $k$ (which would mean there are $k$ students that potentially like each other), remove its vertices, and repeat for the next $k$. However, I don't think this would result in a polynomial number of size combinations.
Do you have any advice on constructing this reduction?


texts: Is this variation of set-cover NP-hard to approximate?

texts:
The classic set-cover problem is described as follows:

  Let $S = \{s_1, ..., s_n\}$ be a target set, and let $\Lambda = \{A_1,
 ..., A_m: A_i \subset S\}$ be a collection of subsets of $S$. The
  objective is to find some cover $C \subset \Lambda $ such that
  $\cup_{A\in C}A = S$ and $|C|$ is minimized. That is, find the minimum
  number of $A$'s needed to cover every element of $S$.

The variation we will consider has two key alterations:

Rather than finding some cover $C$ such that $|C|$ is minimized, we want to cover as much of $S$ as possible, given some budget $k$. That is, let $F\subset S$ be the elements that are covered by $C$, our objective is to maximize
$$\big|F \cap S\big|$$
such that $|C| \leq k$.
Rather than considering an element $s \in S$ covered when $s$ appears in at least one $A\in C$, we require that $s$ show up in 2 distinct $A$'s to be considered covered. (Any multiple is also interesting, even heterogeneous ones for each $s\in S$, but for now 2 is good enough).

So far I can show that it is an NP optimization (reduction from set-cover), and that a $n-$approximation exists by simply looking any element $s$ that appears in some $A_i$ and $A_j$ and then selecting $C = \{A_i, A_j\}$, but this is a rather unsatisfying approximation.

Is this variation NP-hard to approximate to a constant factor?


texts: Kolmogorov complexity of a random string conditioned on another random string

texts: Given two strings $x$, $y$, both of length $n$, what is the probability that $K(x|y,n)=K(x|n)$ ? (Bounds on this probability would be very interesting too). Here $K$ is Kolmogorov complexity, $x$ and $y$ are sampled from uniform probability distribution over strings of length $n$, i.e. $P(x)=\frac{1}{2^n}$ for all $x$. Informally, what is the probability that two random strings carry no information about one another?


texts: "Mathematical Physics"'s equivalent for Computer Science

texts:
Mathematical Physics is a well defined scientific fields that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of physics.

Is there a well defined scientific field that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of computer science ?


texts: Finite subsets of the Halting problem are decidable. Can I prove the correctness of Turing machines computing these subsets?

texts:
I am trying to wrap my hand around the undecidability proof of the Halting problem, and to me it really seems to be more of a proof about representation than decidability. Namely, the proof that some languages are undecidable by Turing machines seems to simply state that I cannot find finite representations for arbitrary countably infinite sets. So far so good. However, I do not see how this might ever be a problem in practice.

If I fix some machine $M$ and consider the language $L_M = \{M \mid \textrm{$M$ halts on empty input}\}$. Clearly, $L_M$ is decidable, because it either denotes the singleton set $\{ M \}$ or the empty set, but:

(1.) Can I always prove the correctness of some machine that decides $L_M$?

(2.) Suppose I cannot always find a proof. Can I find some specific machine $M$, for which I can find a proof that I cannot prove or disprove whether it halts on a specific input?

My first question can also be seen from another viewpoint: If I was to formulate the Halting problem in natural language, it would state

"Does there exist a fixed strategy, so I can decide for every TM whether it halts or not."

But I am interested in the problem:

"Given some TM, can I come up with a strategy to decide whether it halts or not."

I guess that that this question is more about provability than decidability, but unfortunately I know very little about the former.


texts:
Problems:

A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, m)$. Let $S$ be the product of numbers the player has met along the way to $(n, m)$. Find maximum number of trailing zeros of $S$ if the player moves optimally.

What I think about this problem is to use Dynamic Programming. $S$ is equal to $2^x\times5^y\times other\ primes$ so the answer should be $min(x, y)$ but finding maximum $x$ or $y$ is not optimal. $min(x, y)$ instead should be maximized. Please help with this problem.


texts: checking '<' for two binary numbers in a cnf-formula

texts:
I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula. I can already construct a formula, which is not in cnf:

Lets say n and m are two-digit binary numbers:

$n = n_2 + n_1$

$m = m_2 + m_1,$

where $n_i, m_i \in \{0,1\}$ for $i \in \{1,2\}$. Then the boolean formula, which will evaluate to true if $n < m$, would be:

$(\neg n_2 \land m_2) \lor (((\neg n_2 \land \neg m_2) \lor (n_2 \land m_2)) \land \neg n_1 \land m_1)$

As described, this formula should only evaluate to true if $n < m$. I know that every boolean formula can be transformed into a cnf formula, but it seems impractical, if i have higher digit binaries.

So is there a way to construct a cnf formula, which does the same?


texts: is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

texts:
I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance!

  Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( usually $N$ is a large number, $K$ is a small number). Each row of the matrix contains distinct values, but each column may contain duplicate values.
  For $i = 1, 2, \cdots, K$, let $m_i$ denote the count of distinct values at $i$-th column and define $\rho := min(m_1, m_2, \cdots, m_K)$.
  If we can swap any two numbers within each row, how to minimize $\rho$ provided you can perform any number of the given operations(swaps)?

  Can this problem be NP-complete in terms of $N$??

For example: in a $4\times3$ matrix
$$
\begin{matrix}
1&2 & 3\\
3&4& 5\\
4&5& 7\\
6&7& 8\\
\end{matrix}
$$
Since only swaps within a row are allowed, we can swap 1 and 2 in the first row,
but cannot swap 1 in the first row with 4 in the second row.
I think after performing a few swaps, one optimal solution we can get is
$$
\begin{matrix}
1&2 & 3\\
4&5& 3\\
4&5& 7\\
6&8& 7\\
\end{matrix}
$$
where $m_1 = 3, m_2=3, m_3 = 2$,
Hence the minimum count of distinct values of all columns is $\rho = 2$.


texts: How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?

texts:
I don't get how to intuitively come up with an example for an ambiguous grammar.

Let's take as an example this grammar:

Declaration ::= Type D ;
         Type ::= "int" | "char"
         D ::= "*" D
            |  D "[" number "]"
            |  D "(" Type ")"
            |  "(" D ")"
            |  name

I am told outright that this grammar is ambiguous. What is expected of me is to find one example that proves that it is. What I'm interested is what is the thought process that allows you to find an example. Our teacher just gave us one example that would show that we would obtain two different derivation tree like:

int *foo[5];  has two derivation tree

            Declaration              Declaration
             /    |   \               /    |   \
           Type   D    ;            Type   D    ;
            |    / \                 |    / \____
           int  *   D               int  /   \ \ \
                   / \____              D    [ 5 ]
                  /   \ \ \            / \
                 D    [ 5 ]           *   D
                 |                        |
                foo                      foo

However I have no idea how he thought to himself that int*foo[5] would be the example before doing the trees. It all boils down to how they did it without trial and error?

How to make that grammar unambiguous?
I was also given the task to make the above grammar unambiguous. However I don't know yet again what is the intuition behind making it unambiguous.

They gave us this solution:

 Declaration ::= Type D ;
       Type ::= "int" | "char"
       D ::= "*" D
          |  "(" D ")" D'
          |  name D'
       D' ::= "[" number "]" D'
           |  "(" Type ")" D'
           |  empty               <== empty string

There must be a pattern in all of this. What it is? What is the general method to solve this type of problem regardless of which grammar is given?


texts: Turing machine halting in at least 100 steps on all inputs

texts:
L = {< M >  $\mid$ L(M) = M halts on all inputs in atleast 100 steps }.

Answer to this question is given undecidable in my book without any explanation but I think it is decidable.

$\overline{L}$ =  {< M > $\mid$ L(M) = M halts on some input in atmost 100 steps }

For the above language, we can feed strings of length ranging from 1-100 (finite amount of strings)  and run Turing machine for finite amount of steps (100) on each string and check if at least one of them halts in atmost 100 steps.

So, as the complement of L is recursive, L should also be recursive and decidable according to me.

Where am I going wrong ?


texts: Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

texts: I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=NP" problem, but I was wondering whether there were any particular instances when people were close to it. I've also heard about the factoring number problem being solved by a quantum computer by Shor's algorithm. Would this count as an algorithm which solved an NP-problem in polynomial time please ? Please do ask if you want me to clarify any parts in my questions. Thanks in advance.


texts: What are the real world applications of set cover problem?

texts: I am studying about set cover problem and wondering that which problems in real world can be solved by set cover. I found that IBM used this problem for their anti-virus problem, so there should be many more others that can be solved by set cover.


texts: Is the word problem for regular languages in ALogTime?

texts: Given a regular language (by a sparse or dense matrix describing the graph of the NFA) (initially the description was supposed to be a regular expression) and a word, can the problem whether the word belongs to the regular language be decided on a (random access) alternating Turing machine in a logarithmic amount of computation time? (The many links above try to compensate for the fact that I didn't find a nice self-contained description of ALogTime.) The length of the input is the length of the description of the regular language plus the length of the word.


texts:
Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order.

I have a question in my Algorithms assignment which asks to prove the lower bound to sort a $k$-sorted array as $\Omega(n\log{k})$. I was trying to approach this question by using the standard comparison sort proof ($\Omega(n!)$), where we have $n!$ total permutations of the sequence [$a_1,a_2,\cdots,a_n$]. My friend told me that there are $k^{(n-k)}k!$ permutations of a $k$-sorted array. I'm finding it difficult to prove the same. How should I go about finding the total permutations of a $k$-sorted array?

Try for $n=5$, $k=2$.

Total permutation is $3\times 3\times 3\times 2\times 1$,
First element has 3 possibilities $\{1,2,3\}$; second has 4 possibilities $\{1,2,3,4\}$, but one position is already taken by the first,so effectively it has $(4-1)$ slots; third has 5 possibilities $\{1,2,3,4,5\}$, but first and second are there in one of these two, hence 3 possibilities; Fouth one has 4 slots $\{2,3,4,5\}$ and 3 of them are taken? (doubt: because 1st position can also be occupied) , hence 2 , and the last has one.


texts: Decidablity with exponential number of solution

texts:
I am trying to understanding this. If a problem has exponential amount of candidate solutions, such as 2^2^n. Is this decidable?
To my understanding, as long as its' verfiable, no matter how big the solutions there are, it's.decidable.

Thanks for clarity


texts:
Are there any guidelines for how to recognize, for a given problem, which approach is more likely to yield good results? SAT solver or SMT solver?
Is there any guidance anyone can offer about which sorts of problems can be handled better by SAT solvers than by SMT solvers, or vice versa?


texts: How can CFGs have epsilon rules if CSG may not have them?

texts:
I am new to theory of computer science and I am currently reading about CTF grammars. In our lecture we defined that a Type 1 grammar is context-free if for $w_1 \to w_2$, $\vert w_1 \vert \leq \vert w_2 \vert$.

I looked on the internet for an example and found this context-free grammar for palindromes: $G = \{\{P\},\{0,1\},A,P\}$ with the production rules: $P \to \epsilon|0|1|0P0|1P1$, but aren't those production rules violating the definition for a CTF? First of all $\vert w_1 \vert \leq \vert w_2 \vert$ is violated by $P\to\epsilon$ and secondly in my notes there is mentioned that we can only use an epsilon transition if P isn't on the right site.


texts:
This question is inspired by this SPOJ problem. That problem asks median of the final array, that can be done in $O(k+n)$, where k is the number of update queries and n is the size of the array.

The variant : Given an array of length N (of the order $10^5$), initially all elements are 0. There are K (of the order $10^5$) queries of type A B, meaning array elements in range $[A,B]$ must be increased by 1. After every query operation, find the median of the array.
Can this be solved efficiently (subquadratic time, ie, better than $\Omega(N^2$)?


texts: The Cut Lemma for graphs with non-distinct edges

texts:
In my introductory algorithms class I recently learned about the Cut Lemma and how it can be used to prove correctness for many Minimum Spanning Tree algorithms like Kruskal's and Prim's.
In class, to simplify these proofs-of-correctness, we assumed that all edge weights in the graphs we were considering were distinct.  This was also a helpful assumption when working with the Cut Lemma, since it guaranteed there will only be one minimum-weight crossing edge between the two disjoint sets of vertices created by the cut.  In fact, we used proof-by-contradiction to prove the Cut Lemma, which required a unique minimum-weight edge.
My question is, what happens if edge weights aren't distinct?  How can we still use the Cut Lemma to prove correctness for MST algorithms if we can no longer guarantee there is one minimum-weight crossing edge between the two sets of a cut?  Is anything materially different?


texts: How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution?

texts:
So usually Sudoku is $9 \times 9$, but this question extends to $n^2 \times n^2$ puzzles with $n > 3$ as well. There are many polynomial time deduction rules that can make progress in finding a solution to a Sudoku puzzle. But then sometimes guessing values and following chains of conclusions might be required to eliminate a cell's value or a combination of cells' values. However, once a valid solution is found, this doesn't guarantee that the solution is UNIQUE. A valid Sudoku puzzle should have only one valid solution but when generating random puzzles, this may take extra computation to verify.

So, my question is, if we allow a certain set of polynomial time deduction rules (say, the most common set described in Sudoku strategy), along with guessing values and following the conclusions, then how much harder can it be to determine there is a unique solution to a given puzzle, versus finding just one solution, in terms of the number of non-unique solutions? Is there an asymptotic difference for certain classes of puzzles?


texts: An interesting metric space related to Turing machines

texts:
In this question we only consider Turing machines that halt on all inputs. If $k \in \mathbb{N}$ then by $T_k$ we denote the Turing machine whose code is $k$.

Consider the following function

$$s(x,y) = \min\{k \mid |L(T_k) \cap \{x,y\}| = 1\}$$

In other words, $s(x,y)$ is the code of the smallest Turing machine that recognizes precisely one of the strings $x,y.$ We can now define the following map

$$d(x,y) = \left\{
    \begin{array}{ll}
  2^{-s(x,y)}  & \mbox{if } x \ne y, \\
  0 & \mbox{otherwise.}
    \end{array}
\right.
$$

It can be quickly verified that $d(x,y)$ induces a metric space (in fact an ultrametrics) on $\Sigma^{*}.$

Now I would like to prove that if $f:\Sigma^{*} \mapsto \Sigma^{*}$ is a uniformly continuous function then for every recursive language L, $f^{-1}(L)$ is recursive as well.

In other words let $f$ be a map such that for every $\epsilon > 0$ there is a $\delta > 0$ such that if for strings $x,y \in \Sigma^{*}$ $$\quad d(x,y) \leq \delta$$ then $$ d(f(x),f(y)) < \epsilon.$$  Then we need to show that $f^{-1}(L)$ is a recursive language given that $L$ is recursive.

Now as already noted in this post one way to approach the problem is to show that there is a Turing machine that given a string $x \in \Sigma^{*}$ computes $f(x).$

I am stuck proving this claim and slowly wondering if there is some other approach to solve this?

Hints, suggestions and solutions are welcome!


texts: Kolmogorov complexity of a decision problem

texts: What's the definition of Kolmogorov complexity for a decision problem? For example, how to define the length of the shortest program that solves the 3SAT problem? Is it the "smallest" Turing machine that recognizes the 3SAT langauge?


texts:
I have come across the following optimisation subproblem:

  Geometric Disjoint Set Cover. Consider a collection $C$ of (not necessarily distinct) ranges taken from a universe range $X \subset \mathbb{R}^d$. Does there exist a $k$-partition of $C$ into set covers of $X$?

I am particularly interested in the case where ranges are axis-parallel rectangles in $\mathbb{R}^2$, and $k$ is small. Does there exist a polynomial time algorithm for fixed $k$ and $d$? Is there a more widely known name I can search by?

Without the geometric constraint, this problem is NP-hard even for $k = 2$, by equivalence to deciding $2$-colourability for hypergraphs. On the other hand, when $d = 1$ there is a simple greedy $O(|C| \log |C|)$ algorithm that works for all $k$: at each step consume up to the $k$-th rightmost endpoint of intervals starting at or before the current position. Can this be generalised to $d = 2$?


texts: Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

texts:
I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. This is the reduction:

$M_f$: Given an input of $\langle M, w\rangle$, where $M$ is a $TM$ and $w$ is a word:

Define a TM $M_1$:

Given the input $x$ do:

Run $M$ on $w$ and return its result
Return $\langle M_1\rangle$

This is correct for $ALL_{TM}$ because if $M$ accepts $w$, $L(M_1)=\Sigma^*$, whereas if it rejects, $L(M_1)=\emptyset$

However, it is also given as a solution for $A_{TM} \leq_M INFINITE_{TM}$, where

$INFINITE_{TM}=\{\langle {M \rangle} |$ $M$ is a $TM$, $L(M)$ is an infinite language $\}$, for example here: http://www.sfu.ca/~kabanets/308/lectures/lec7.pdf

I don't fully understand why theirs, or other similar explanations, are correct. What about infinite languages that aren't $\Sigma^*$? What about finite languages that aren't $\emptyset$?


texts: Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

texts:
Given undirected and connected graph $G = (V,E)$.
Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$

$δ(u,v)$-distance of a shortest path (not necessarily unique) in G

$u.d,v.d$-time, when each vertex was discovered in DFS for the first time.

I know that DFS not necessarily returns the shortest path.And I know that if  $u.d>v.d$ then $u$ discovered after $v$, $v≠u$ and there is path is DFS between vertices, because G is connected.

I have tried to assume by contradiction that
 $u.d-v.d<δ(u,v)$

Given that G is connected and $v.d<u.d$. Then v discovered before $u$  and $u≠v$.
According to the “parenthesis property” theorem: either $u$ is a descendant of $v$, or $u$ and $v$ do not exhibit an ancestor-descendant relation if $G_π$.

In the first case, $u$ is a descendant of $v$.

Let’s assume by contradiction that $u.d-v.d<δ(u,v)$
 $u.d-v.d$ sets distance of simple path $(u,v)$ from $u$ to $v$ in $G_π$.
Because $u$ is a descendant of $v$, the path $(u,v)$ also appears in $G$.
By our assumption this distance is smaller then $δ(u,v)$  and that is in contradiction to the fact that $δ(u,v)$ is a distance of a shortest path (not necessarily unique) in $G$.

In the second case, $u$ and $v$ do not exhibit an ancestor-descendant relation if $G_π$.

Hence, $u$ was not discovered from $v$. It means that there is $w≠v∈V$ such that: $w.d<v.d<v.f<u.d<u.f<w.f$ $(w≠v)$

$w.d<u.d$ then $u.d-w.d≥δ(u,w)$ (proof of the first case)
 $w.d<v.d$ then $v.d-w.d≥δ(v,w)$

And I have no idea how to continue from here..


texts: Is there a connection between the Undecidability Theorem and "software complexity"?

texts:
I was reading Complexity: The Emerging Science at the Edge of Order and
Chaos and a certain passage got me really intrigued.  When discussing
Chris Langton's explorations of artificial life algorithms, the author
paraphrases Langton stating the following about a certain set of
evolutionary algorithms:

This is the undecidability theorem, one of the deepest results of
computer science: unless a computer program is utterly trivial, the
fastest way to find out what it will do is to run it and see.  There
is no general purpose procedure that can scan the code and the input
and give you the answer any faster than that.  That’s why the old saw
about computers only doing what their programmers tell them to do is
both perfectly true and virtually irrelevant; any piece of code that’s
complex enough to be interesting will always surprise its programmers.
That’s why any decent software package has to be endlessly tested and
debugged before it is released and that’s why the users always
discover very quickly that the debugging was never quite perfect.

But I can't easily see how the undecidability theorem allows one to
conclude that "unless a computer program is utterly trivial, the fastest
way to find out what it will do is to run it and see".
Can such a connection be made formally, or was it more of an empirical
observation?


texts:
Let's assume I am trying to find a hidden treasure.

The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is an integer). In order to find the treasure I have to take with me a detector. The detector can spot the treasure only if it is above it.

My starting position is the 0 point and I can move back and front until I cross the treasure, so that my detector can track it. I am always moving on the integer line. Which is the most efficient way to move through the axis in order to track the treasure?? I have to find an algorithm that allows me to find the treasure by covering a distance $O(|x|)$

My approach: After some consideration, I think that the most efficient way to find the treasure is the following: Starting from 0 I move front until I reach number $2$. Then I move back until I reach number $-2^2$. Then I move front until I reach number  $2^3$. Then I go back again until I reach number $-2^4$ and so on...

However, I am having difficulties on proving that there is a constant $c$ (for which I have to calculate an upper bound) so that my algorithm is going to help me find the treasure at $c |x|$ moves at most.
Any help is much appreciated! Thanks in advance!

P.S. I am new at the computer science stack exchange so I am not sure about the tags. Correct them or add more if necessary.


texts:
I have a stream of tuples arriving in the following form: (timestamp,price). There is no pattern in the arrival of these data points (number of data points per minute is random). I need to be able to return the maximum price in the last hour at any point of time. What is the most efficient algorithm in terms of time complexity and space complexity separately to do this ? I thought of the following:

create 1 min candles of prices, which will reduce the storage but then wont be exactly correct
store the top K elements with their price and timestamps and update this list according to the current timestamp


texts: $k$ -center with outliers - but the points are on a line

texts:
The classic $k$-center with outliers problem is NP-hard and there exist approximation algorithms to solve it.

However, what if we assume that the input point are on a line, rather than in an arbitrary metric space?

Does the problem become polytime solvable? Can someone link me to reading on this topic?


texts: Finding negative cycles for cycle-canceling algorithm

texts:
I am implementing the cycle-canceling algorithm to find an optimal solution for the min-cost flow problem. By finding and removing negative cost cycles in the residual network, the total cost is lowered in each round. To find a negative cycle I am using the bellman-ford algorithm.

My Problem is:
Bellman-ford only finds cycles that are reachable from the source, but I also need to find cycles that are not reachable.

Example: In the following network, we already applied a maximum flow. The edge $(A, B)$ makes it very expensive. In the residual network, we have a negative cost cycle with capacity $1$. Removing it, would give us a cheaper solution using edges $(A, C)$ and $(C, T)$, but we cannot reach it from the source $S$.

Labels: Flow/Capacity, Cost

Of course, I could run Bellman-ford repeatedly with each node as source, but that does not sound like a good solution. I'm a little confused because all the papers I read seem to skip this step.

Can you tell me, how to use bellman-ford to find every negative cycle (reachable or not)?
And if not possible, which other algorithm do you propose?


texts: According to wikipedia, Kraft's inequality holds with equality when a code is complete. Huffman encoding produces a complete code that is optimal. Are all complete codes optimal and vice versa?


texts: How to write "∀x.F(x)" for "F(x)=λx.Φ(x)" in one expression (sequel from question about "∀(λφ. (φ x m→ φ y))"?

texts:
This question is sequel from How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"? which further explains the notation and context.
So - I have anonymous Boolean-valued function F(y)=λx.Φ(x) (of course, y and x point to the same variable, I just used different syntactic names, to point out, that x is bound variable) and I would like to write the statement, that F(x) is true for all the values of the argument and it can be written ∀x.F(x). But F(x) is named function, but I would like to write the same expression (that λx.Φ(x) is true for all values of argument, all values of x)  for the anonymous function that uses lambda, so I am with my suggestion: ∀x.λx.Φ(x) or ∀x.λy.Φ(y)? And apparently they both are wrong. What is correct way to express, using quantifier, that expression λx.Φ(x) is true for all values of x?
Generally my concern (and therefore - my question) is valid. Let's consider F(x,y)=λx.λy.Φ(x, y). In that case ∀F is ambigous (there is big difference between ∀x.F(x, y) and ∀y.F(x, y)) and ∀∀F and would be even more ambigous for functions with argument count n>=3. So, ∀ should mention argument explicitly. But I guess - noone can refer to some argument explicitly for the function that is written in anonymous form (with λ) or am I wrong? I am so confused about this notation - how to refere the argument of anonymous function which is referred by ∀?
What I am trying to achieve? I just want to build parser for language that is declared in https://www.isa-afp.org/browser_info/current/AFP/GoedelGod/GoedelGod.html. This language contains expressions like [∀(λΦ. P (λx. m¬ (Φ x)) m→ m¬ (P Φ))].
I am using ANTLR grammar for lambda calculus https://github.com/antlr/grammars-v4/blob/master/lambda/lambda.g4 and I understand that the 1) quantifiers; 2) logical connectives; 3) arithmetic functions are just another lambda functions (it is just syntactic sugar that they are written in the specific non-lambda syntax/prefix form etc.) and as such I express them in the existing lambda.g4 grammar https://github.com/antlr/grammars-v4/blob/master/lambda/lambda.g4. So - my first step is to write the cited expressions with the named functions and then I will just replace them with anonymous functions because lambda.g4 has no options to introduce named functions. But it is so confusing to write anonymous function and the quantifier function for the same argument.
Just side question - maybe there is better ANTLR grammar for lambda calculus with syntactic sugar for quantifiers and connectives?


texts: Definition of the inverse of the Ackermann function

texts:
I am somewhat puzzled by the definition of the inverse of the Ackermann function: The normal Ackermann function $A$ can be used to define a function from $\mathbb{N} \to \mathbb{N}$ via $A(n, n)$. The inverse of this function, denoted by $\alpha$, is known as the inverse Ackermann function.

My problem is: Only bijective functions have an inverse. But I have seen no proof that $A(n, n)$ is indeed bijective. It seems highly unlikely to me that this is the case (since the value of $A(n, n)$ increases very quickly in $n$).

My guess is that $\alpha(m)$ should be defined as $\min \{n \mid A(n, n)  \geq m\}$ or $\max \{n \mid A(n, n)  \leq m\}$. Is that the case?


texts: How to interpret parametric formulation of information bottleneck?

texts:
I'm reading this paper on latent representations with the information bottleneck https://arxiv.org/pdf/1804.06216.pdf and in section three, the authors write that the parametric formulation of the information bottleneck is
$\max\limits_{\phi,\theta} - I_\phi(t;x) + \lambda I_{\phi,\theta}(t;y).$
My question is not about the information bottleneck entirely, but how to understand the first term $\max\limits_{\phi,\theta}$ where $\phi$ and $\theta$ are parameters of a model. This notation doesn't make sense to me as I usually expect something to follow the $\max$. Does it just mean the largest value over all the parameters in the model?


texts:
Consider the following language $$L= \{ \langle M\rangle | \text{ $M$ is a TM, and $L(M)\in coRE$}  \}$$
I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. Indeed, suppose we have a TM $M$, now for input $x$ such that $x\notin L(M)$, it seems that we cannot decide whether $x\notin L(M)$ as $M$ may not halt on $x$.


texts: An efficient algorithm to find a linear transformation between two ternary quadratic forms

texts:
Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms
$$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\
Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$
over the field $\mathbb{F}_p(t)$ of rational functions with coefficients from $\mathbb{F}_p$. For simplicity let $a_1, a_2, b_1, b_2 \in \mathbb{F}_p[t]$ are polynomials without multiple roots and $a_1$, $b_1$ (respectively $a_2$, $b_2$) have no common roots.

Is there an efficient algorithm to find a linear transformation (over $\mathbb{F}_p(t)$) between $Q_1$ and $Q_2$ if it exists?

There is the theory that relates such forms and quaternion algebras (see, for example, $\S$1.4 in Book of Gille, Szamuely - Central Simple Algebras and Galois Cohomology). For example, for any non-zero polynomial $f \in \mathbb{F}_p[t]$ and $p > 2$ the following quadratic forms are isomorphic:
$$
Q_1\!: x^2 - y^2 - f(t)z^2,\\
Q_2\!: x^2 - y^2 - z^2
$$
This is true, because $Q_1$ can be reduced to the quadratic form $Q_3\!: x^\prime y^\prime-(z^\prime)^2$ by the transformation
$$
x := x^\prime+\frac{y^\prime}{4f},\qquad y := x^\prime-\frac{y^\prime}{4f},\qquad z := \frac{z^\prime}{f}.
$$
It is well known that any two conics (including $Q_2$, $Q_3$) over a finite field are isomorphic.


texts: Prove that checking if context free grammar generates word with all symbols is NP-complete - unclear statement about encoing probem in exercise

texts:
Prove that following problem is complete in NP in sense of Karp.
Given: context free grammar $G$
Check if $G$ generates word containing
all symbols from alphabet
Remark
Above problem should be encoded as langauge over finite alphabet,  although alphabet of $G$ can be arbitrarily big. You can assume that symbols of this alphabet are encoded as binary strings.

My main problem at this moment is that I don't understand Remark.  For me, it should be attached also alphabet of grammar.  Can you explain me in human language what this Remark try to say ?
To be more clear I can say that in other task with the same question, but with given regex and alphabet of regex I did deal with it. However, in mentioned task there was no this awkward Remark.


texts: Reference book for Parallel Computing and Parallel algorithms.

texts: Please suggest some books on Parallel Algorithms which teach efficient programming techniques like the ones taught in Udacity course(Introduction to Parallel Programming with CUDA). Also wanted to know that from which reference book or papers are the concepts in the udacity course on Parallel Computing taught...? I wish to study more about such techniques which will make me an efficient parallel programmer...!


texts: how to approximate a very complex optimal policy when the distance function is unknown

texts:
A policy $P$ is defined as a set of parameters. We want to know the optimal policy $O$, which certainly exists but unfortunately unknown.

$D(P)$ shows how far $P$ is from $O$. The function $D$ itself is unfortunately not known. However, $D(P) - D(Q)$ is known. That is, one can always know which among $P$ and $Q$ is closer to $O$.

What kind of approach can be done for such problem?

In my setting, a policy is in a form of a (convolutional) neural network. $D(P) - D(Q)$ is approximated by a simulation involving an agent with policy $P$ and an agent with policy $Q$. We repeatedly play a two-player game with a clear win/loss where $P$ plays against $Q$. The value of $D(P)-D(Q)$ is equal to the number of times $P$ wins against $Q$, divided by the number of games we play.


texts:
I need camera to sign one random line(there are something like 2000 lines) from the frame each second.
At the beginning I have some 64 bits seed with high entropy from physical RNG and a secure channel with camera. How should I generate the needed number?


texts: Is it NP complete to decide whether a graph has bigger clique or bigger independence number?

texts: Is it $\mathsf{NP}$ complete to decide whether a graph $G$ has bigger clique $\omega(G)$ or bigger independence number $\alpha(G)$?


texts: Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?

texts:
If an array $A[1 \ldots N]$ is represented using a segment tree having sets in each interval, why does a range query $[L\ldots R]$ returns at most $\lceil \log_2{N} \rceil$ sets (or disjoint intervals)?

If came across this statement while reading this answer.

To quote:

  Find a disjoint coverage of the query range using the standard segment
  tree query procedure. We get $O(\log n)$ disjoint nodes, the union of
  whose multisets is exactly the multiset of values in the query range.
  Let's call those multisets $s_1, \dots, s_m$ (with $m \le \lceil \log_2 n \rceil$).

I tried searching for a proof, but couldn't find it on any site. Can anyone help me prove it?


texts: Given an CFG determine if $\varepsilon \in L(G)$

texts:
Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ?

The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (Assuming it's not in CNF)

Is my intuition right though?


texts: The validity of the potential function for splay tree

texts:
The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in the splay tree, where the rank of a node $x$ is taken as the logarithm of the size ($s(x)$; i.e., number of nodes in) of the subtree rooted at $x$:

$$\Phi(T_i) = \sum_{x \in T} \log (s(x)).$$

To make sure that the amortized cost is an upper bound of the actual cost, it is required that the final potential is no less than the initial potential $\Phi(T_0)$ (Page 657):

$$\forall 1 \le i \le m: \Phi(T_i) \ge \Phi(T_0).$$

Problem: How to verify the condition above? (I did not find the argument in the paper.) Maybe it is not necessary to verify this condition; if so, why?


texts: I don't understand the case 4 of red-black tree deletion

texts:
I don't know why case 4 will resolve the issue of the double black of $x$ described in Introduction to algorithm p.329. I know case 1 is transformed into one of {2,3,4} case, and case 2 re-point $x$ to its parent node so it's approaching the root, and case 3 will be transformed into case 4, but both case {3,4} will not change the pointer $x$, anyway so how case 4 work?

Is it because for paths include $C,E$ there is no difference about the number of blacks while for that about $\alpha,\beta$ an extra black node $B$ is passed?


texts: Proving simple bound on coupon collector

texts: I came across this paper which gives bounds on coupon colloector problem. Page 451 contains a table where reference to U1 is given as 'folklore'. I presume this is trivial to follow from the definition but I can't see the logic behind this. Does anyone have hints for me? I tried to get this bound by taking the limit of probability that some coupon is not found after n tries but that needs n to be infinity.


texts: How are the 1s and 0s derived by the minimax algorithm for the game called "nim"?

texts:
I'm having trouble figuring out why the 1s and 0s are where they are in this game tree for the game Nim:

There is a statement in the book that explains the numbers but it's still not clear to me,

In implementing minimax, we label each level in the search space according to whose
move it is at that point in the game, MIN or MAX.

In the example, MIN is
allowed to move first. Each leaf node is given a value of 1 or 0, depending on whether it is
a  win  for  MAX  or  for  MIN.  Minimax  propagates  these  values  up  the  graph  through
successive parent nodes according to the rule:

If the parent state is a MAX node, give it the maximum value among its children.
If the parent is a MIN node, give it the minimum value of its children.

If I was to draw the tree by hand how would I know where to put the 1s and 0s?


texts: Affects of altering a line in "stop and wait" protocol(no noises)

texts:
what will happen if we change "to_physical_layer(&s)" to "to_physical_layer(&r)" in the following code(marked in the code where)?

does it make the protocol fail? if so, show a scenario it will fail. if not - explain if there's an advantage or disadvantage in the change.

the code:

(simplex stop and wait protocol from tanenbaum's book):

typedef enum {frame-arrival} event_type;
#include "protocol.h"

void sender2(void){
  frame s;           // buffer for frame
  packet buffer;   // buffer for packet
  event_type event;  // frame_arrival only
  while (true) {
    from_network_layer(&buffer); // get packet
    s.info = buffer;        // copy it into frame
    to_physical_layer(&s);  // send it
    wait_for_event(&event); // wait for ack
  }
}

void receiver2(void) {
  frame r, s;        // buffers for frames
  event_type event;  // frame-arrival only
  while (true) {
    wait_for_event(&event);  // wait for frame
    from_physical_layer(&r);  // get frame
    to_network_layer(&r.info); // pass data
    question is regarding this line--> to_physical_layer(&s);
      // send a dummy frame to awake sender
  }
}

The question is not about programming in c, but about protocol Stop and Wait and the effects of changing a certain parameter in the marked line.


texts: Showing that T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)

texts:
I am doing an exercise which says that this is true:
T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)
So I tried to solve it by substitution, but I am getting a non-sense result.
So would really appreciate some pointer in the right direction.
So I want to show it for $\frac{n}{4}$ (sub-question, I am picking $\frac{n}{4}$ to show it for because the recurrence has $T(\frac{n}{4})$, but this might not be the correct way to go always?)
I substitute $T(n/4)$ for $c\sqrt{n}$ in the original equation and get
T($\frac{n}{4}$) $\leq$ 2 + 2(c $\sqrt{\frac{n}{4}}$) =
2 + 2c$\frac{\sqrt{n}}{\sqrt{4}}$ =
2+2c$\frac{\sqrt{n}}{2}$ =
2+c$\sqrt{n}$ $\leq$ c$\sqrt{n}$
Which is clearly not true.


texts:
I was looking at the question How to convert finite automata to regular expressions? to convert DFA to regex.

The question, I was trying to solve is:

I have got the following equations:

$Q_0=aQ_0 \cup bQ_1 \cup \epsilon$

$Q_1=aQ_1 \cup bQ_1 \cup \epsilon$

When solved, we will get $Q_0=a^*b(a \cup b)^* \cup\ \epsilon$

But my doubt is that, in the DFA starting state is also the final state so, even if we dont give any $b$, it will be accepted, if we give some $a$. But in the regex we have $b$, instead of $b^*$. Why is it so? Is it because,we have that regex $\cup$ $\epsilon$ ?


texts: How to convert regular expression to CFG?

texts:
How can I convert the regular expression (ab*)*b to a context-free grammar?
When I look for examples I keep seeing plus signs in the expression but I don’t have any. Is that just a different way of writing it?


texts: What kind of bigram probability smoothing is this?

texts:
I hope it isn't off topic but I need to understand this example. Given the corpus 12 1 13 12 15 234 2526 and smoothing factor of k=1. The example does the following operations:

Considers OOV(out of vocabulary) words and assigns them a zero times value, after that k=1 is added to the times every words appears, to avoid zero probabilities. So the result of smoothing the bigrams probability will be:

$P(1|12)=(1+k)/(2+2+6*k)=0.2$
$P(15|12)=(1+k)/(2+2+6*k)=0.2$
$P(13|1)=(1+k)/(2+6*k)=0.25$
$P(12|13)=(1+k)/(2+6*k)=0.25$
$P(234|15)=(1+k)/(2+6*k)=0.25$
$P(2526|234)=(1+k)/(2+6*k)=0.25$

My question is, What kind of smoothing is this? shouldn't be for example like this?; $P(1|12)=(1+k)/(2+6*k)=0.25$Besides it also says "If OOV words appear, you need to use smoothing to return a value; $P(234|12)=1/((2/7)*6+6)=0.1296$"

PS: I take this example from a small section of the translated version of this chinese webpage, it is just explaining a code implementation.


texts: Why doesn't parallelism necessarily imply non-determinism?

texts:
I'm a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out.

I understand the difference between concurrency and parallelism. I get that concurrent programs are non-deterministic depending on the precise timing of events. "But parallelism doesn't necessarily imply non-determinism" - as said in the book. Why is that?

Does that imply that it's all dependent on the languages that support parallelism. Which implies that these languages should execute parallel programs in a deterministic manner?

Another question that I have is that the timing of events of concurrent programs depend on what exactly on what exactly? The architecture of the machine?


texts: Algoritm to sample an even subgraph of a graph

texts:
In some problems related to the Ising model in physics and mathematics the following problem comes up:
Suppose I have a graph $G$. Then an even spanning subgraph of $G$ is a subgraph where you keep all the vertices and some of the edges such that each vertex has even degree.There is always at least one since the empty spanning subgraph is always even. Now, among all the even spanning subgraphs of $G$ I want to sample one uniformly at random.
Is there an fast and preferably easy to implement algoritm to do that?
Is this a well studied problem? If yes: could you point me to some references?
Some background: The space of even spanning subgraphs of a graph has some nice structure since if you have two of them then you can take their symmetric difference and it will still be an even spanning subgraph. This means that it is a vector space of the field $\mathbb{F}_2$ and you can pick a basis of that space - in particular this shows that the number of even spanning subgraphs is always a power of 2.
I wonder how difficult it is to find the basis elements since if you have some you just flip coins for each and take the symmetric difference of all the graphs where you get head.
Another point is that there might be a smart low-tech randomized way to do this.


texts: Difference between centralized computing and distributed computing using Client-Server

texts: I already understand that Distributed Computing is the breakup of having multiple clients rely on a single source, and having each client utilize other clients for information. But my confusion comes from a type of distributed computing, where one type is the client server model. From what I know, the client server model has multiple clients using a network to access a server. How does this differentiate from calling it centralized computing?


texts:
Is there any way to find output dependency using delta test?
I know that we can perform flow and anti dependence test using delta test, but to find output dependency for such case?
For example say if this is the piece of code, in which I want to find output dependence using delta test


texts: Find $k$ subsets containing a particular element quickly

texts:
Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $ (< n)$ subsets that contain $e \in U$ (call this Extraction(e)). Elements are integers.

To that effect, I want to preprocess/encode the $n$ subsets so that this extraction operation can occur relatively quickly, regardless of what $e$ is (assume that this item is uniformly selected over queries).

I don't have a good intuition for various methods to do this and after how much prerocessing space/time diminishing returns kick in. I'm certainly looking for something that takes polynomial time/space.

I was thinking about encoding the subsets as hashsets and then hashing together $q$ of these subsets together at a time, so that I end up with $\lceil\frac{n}{q}\rceil$ packaged hashsets. $q$ would be inferred in some fashion from the frequency distribution of all elements in U. Then I could iterate over these packaged hashsets and check for containment of $e$ in constant time (average-case).

Is this problem well-studied?


texts: Complexity class for loop with two inner loops

texts:
I have an algorithm like the following

for(int k) {
    statement1;
    for(int j) {
        statement2;
    }
    for(int m) {
        statement3;
    }
 }

j => m

Is it correct for me to conclude that the complexity class is O(n^2)?


texts: If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?

texts: As posed in the question; the statement naively seems like it should be self-evident but there are no algorithms that come immediately to mind. Suppose I have some domain $A$ (in my case a subset of $\mathbb{Z}^n$ for some $n$, but I would expect any answer to be independent of that structure), and a domain $B\subset A$. If I have an efficient algorithm for uniformly sampling from $A$, and an efficient algorithm for uniformly sampling from $B$, is there any way of 'combining' these to get an efficient algorithm for uniformly sampling $A-B$? I can certainly rejection-sample, but if $|A-B|\ll|A|$ then there's no guarantee that that will be efficient.


texts: Can every CFG be converted into an equivalent CFG of this form?

texts:
Question:

Show that every CF grammar G = (V,T,S,P) can be converted into an equivalent CFG in which every production is of the form A → xBC or A → ϵ, where x ∈ T U {ϵ} and A,B, and C are variables.

For this question, I have considered that it can be proved by using Greibach Normal Form, because we can get the form: A → aABCDEF... which is similar to the form above: A → xBC or A → ϵ.

However,the pre-condition of Greibach Normal Form is that any context-free grammar which doesn’t produce ϵ. I am not sure whether it can prove with GNF.

Can anyone give me suggestions of this proof ?


texts: Checking if a given point is convex hull vertex

texts:
I have a problem in computational geometry: Given $n$ point in 2D space,and given a point $P$, design
an algorithm check that whether $P$ is a vertex of convex hull or not
in $O(n)$.

My idea 1:
I think if all other point inside angel created by $P$ then $P$ is a vertex of convex hull.
But main problem is how we can check all point in angle created by $P$ in $O(n)$?
and how i can prove my claim?
My idea 2:
On the $P$, draw a straight line, so if all point be a on side of $P$ then $P$ is vertex of convex hull, but in proving my claim and design algorithm for both, i get stuck.


texts: What's the best way to combine multiple A* searches?

texts:
I have a graph that looks like this

The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance between each of the nodes.
I want to use A* search for each individual node, then A* search to find the path to the next node, and the next, etc. until the blue node is reached.
What is the best way to work out which order I should visit each node in?
If you notice, the closest pink node to the stick man is D, and so if i use euclidean distance to determine that the D node will be visited first, the stickman will actually go through B instead of C when using A* search to find the best path to D from the stickman, which is obviously the least optimal route. (the distance between B and D is 6.2)
f of C would be 7.35

f of B would be 7.2


texts: SVM optimization objective: why are we maximizing $\frac{1}{\|w\|}$?

texts:
I'm learning about Support Vector Machines(SVM).
I understood that their objective is to maximize the margin between the decision line and the closest point to it.
For simplicity, let's assume we have a linear SVM and linearly separable data X.
We would like to find the maximum distance D and vector W, such that

$\dfrac{W^T \cdot X_i+W_0}{\|W\|}\geq D$ for all $X_i$ in the first class

$\dfrac{W^T \cdot X_i+W_0}{\|W\|}\leq-D$ for all $X_i$ in the second class.

Why is the problem equivalent to maximizing $\frac{1}{\|W\|}$, given the following constraints are satisfied:

$W^T\cdot X_i+W_0\geq1$ for all $X_i$ in the first class

$W^T\cdot X_i+W_0\leq-1$ for all $X_i$ in the second class.

I'm more interested in a formal proof than in the intuition.


texts: Algorithm for finding two smallest numbers in an array

texts:
I was just thinking today that the best approach to find two smallest numbers in any array would be to first sort(ascending order) it with some efficient algorithm like Quicksort(Average case complexity: nlogn) and then access the first two members of the array in O(1).

Is my approach optimal or there are some alternative better approaches?


texts: How do we find the optimal modulus q in Rabin-Karp algorithm?

texts:
I asked a similar question here on Rabin Karp algorithm. My present question is, how do we find the best $q$ (i.e modulus)? What is the criterion? We need to choose a $q$ which will be quick to calculate and also must result in lesser number of spurious hits, right?

Wow do we ensure these things?


texts: We clearly know that 2-QCNF is in $\mathsf{P}$. Since that, if I understand it right, it is possible to solve it with #SAT solver (because $\mathsf{P} \subseteq \mathsf{\#P}$). But how can we only knowing amount of positive assignments for some non-quantified formulae solve 2-QCNF? And why this doesn't hold (at least, assumed so) for general case of TQBF?


texts: Do linearly dependent features in feature vectors improve the feature vector?

texts:
I was reading Wiki on feature vectors, and as far as I can see, it suggests creating new features from already existing features:

  Higher-level features can be obtained from already available features
  and added to the feature vector, for example for the study of diseases
  the feature 'Age' is useful and is defined as Age = 'Year of birth' -
  'Year of death'. This process is referred to as feature construction.

But assuming that you already have included 'Year of birth' and 'Year of Death' as features, will adding 'Age' (that is, 'Year of birth' - 'Year of death') as a feature in the feature vector improve it in any way? I'm thinking not, as the variables are linearly dependent.

If it depends on the machine learning algorithm used, I am mostly interested in SVMs.


texts: Classification of recursively enumerable sets

texts: It's quite easy to show that there are only three recursive sets up to m-equivalence, namely $\emptyset,\{1\},\mathbb N.$ Can we state something "similarly short" for recursively enumerable sets, like there are only 4 recursively enumerable sets up to m-equivalence – $\emptyset,\{1\},K,\mathbb N$ (where $K=\{i\mid\varphi_i(i)\text{ is def.}\}$)? More specifically, is every non-recursive recursively enumerable set m-equivalent to $K$?


texts: What is the name of this problem in Computer Vision?

texts:
My google skills have failed me during research for a college project. Our task is write a program that describes an image in spacial terms, e.g. "Cat on the left of a chair", or for a simple image "Two triangles over a large circle, and a sqaure underneath it".
Suppose that after analysing an image I have a set of objects, with names, coordinates, sizes, orientations. I want to transform this set into sentences like above, i.e. describing relative positions, overlaying and so on.
Unfortunately, I cannot find anything on this subject. "Scene decription" means 3D graphics description languages. "Image description" is about the nouns and, recently, the verbs describing an image. It seems that I have the wrong keywords.
I'd much appreciate any hints about what to look for. Links to scientific papers to peruse (if you have any at hand) would be great too.


texts: What are the design issue with today's micro processor

texts:
I'm just getting started with cs. In school I heard about that modern micro processor are not perfect. So what are the issues? Are does problems related to energy(power draw)/ time /speed(clock speed)? Or is the design faulty?
So if you could design the perfect cpu what would it look like?


texts: Term for a matching which is perfect on one side only

texts:
What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, obviously, not fully matched)?

It is not exactly perfect, but it is "one-sided perfect", or "as perfect as it could be". What is a short term to use for this kind of matching?


texts: Proving that non-regular languages are closed under concatenation

texts: How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\{a^nb^n|n\ge1\}$ ?


texts: How is ARC consistency un-done after a recursive failure condition?

texts:
Taking this as an example:

bool SolveSudoku(int grid[N][N])
{
    int row, col;

    // If there is no unassigned location, we are done
    if (!FindUnassignedLocation(grid, row, col))
       return true; // success!

    // consider digits 1 to 9
    for (int num = 1; num <= 9; num++)
    {
        // if looks promising
        if (isSafe(grid, row, col, num))
        {
            // make tentative assignment
            grid[row][col] = num;

            //RUN ARC CONSISTENCY HERE ......?

            // return, if success, yay!
            if (SolveSudoku(grid))
                return true;

            // failure, unmake & try again
            grid[row][col] = UNASSIGNED;

            ////REMOVE ARC CONSISTENCY HERE ......?
        }
    }
    return false; // this triggers backtracking
}

Given the backtracking algorithm with CSP's, I would like to add ARC consistency to make it smarter.

For example:

  "When we want to assign the digit 'd' to cell s1, we use assign(cells,
  s, d).  ...but I also want to eliminate this possibility from its
  peers  (like Forward Checking does, tell me something new!). If the
  elimination causes one (or some) of the peers going down to only one
  possibility, which we call d2, we want to assign d2 to it, and by
  doing that,  eliminate d2 from all of its peer's peers, and that could
  make another chain  reaction. This chain reaction is simply called
  constraint propagation:  placing a constraint on one cell can cause
  further constraints to be placed on  other cells."

Can the process of arc propagation end up leading to a solution by
itself or even a false solution? What is done in those cases?
In the likely event the next recursive call on the next variable returns false (no values worked out for that variable), how do I
undo all the changes the arc consistency did?


texts: Efficient algorithm for iterated find/replace

texts:
I'm looking for an algorithm for doing iterated find/replace, where the act of finding the replacement list of tokens for a given find is slow.

Specifically: I have a function, f, that maps a sequence of tokens to either a shorter list of tokens or None. However, it is slow.

I want to repeatedly try to replace the (first, in the case of ties) shortest unexplored subsequence in the input with the result of applying the function to it, assuming that there is a valid replacement for it. However, the naive way to do this ends up with exponential runtime. Is there a better algorithm for doing this?

(So, for example, if f maps ba -> b, aaa -> ab, and aba -> bb, and I apply the algorithm to aaaaa, I want to get (aaaaa->abaa->aba->)ab, not (aaaaa->abaa->bba->)bb or any of the other sequences of replacements possible, if any.)

(Note: this example uses characters for simplicity)


texts:
$M$ is an MST of the Weighted Graph - $GR$.
Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}.
Let $A$  be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}.
If $e$ is a edge of $M$ then ($M-${$e$}) is a forest of $M1$ and $M2$ trees such that for $M_i, i=1,2$ is a MST of Induced Graph $GR$ on vertexes $T_i$.
My notes tell me that the first and last is false. I need some idea of how to understand the validity of these sentences in a more simple and concise manner.


texts: How to prove that a transformed language is regular using an NFA

texts:
I am trying to prove that if a language $ L $ of binary strings (i.e. a subset of [01]*) is regular then so is the transformed language $ plus (L) $ consisting of the binary representations of those integers one greater than those represented by the elements of $ L $. That is to say $ plus (L) = \{ plust (l) : l ∈ L \} $ where $ plust $ transforms a binary of an integer $ n $ to a binary of $ n + 1 $, so $ plust ("0111") = "1000" $.

I am trying to prove this by assuming that there is a DFA that accepts $ L $ and using it to build an NFA that accepts $ plus (L) $.

However, I am totally at a loss as to how to do this. What is a good starting point, or what steps can I take to produce such a proof?


texts: Understanding an example of coin toss expectation maximization

texts:
I've been trying to get my head around Expectation maximization algorithms, and I thought I'd start simple. I found this 3-coin example here: http://cs.dartmouth.edu/~cs104/CS104_11.04.22.pdf  I understand the calculation of all of the probabilities but I don't understand how the recalculation of lambda, p1 and p2 is actually done. (Page 18)

I understand how the maximization of a log-likelihood/likelihood function by differentiation works, but can't figure out the recalculation method here.

Can anyone explain why the recalculation of lambda, p1 and p2 take the form they do?


texts: How do computers really communicate with hard-drives on x86_64?

texts:
All of us have saved a file on our computers using a programming language. If I look down through the layers of abstraction, I usually get stuck at a kernel-level call or a C-call like fwrite(); But even at this already deep level things like filesystems and location of storage are hidden from us. For example, one cannot tell on which drive a file is stored when the partition uses more than one drive, nor do you need to care which file-system is used.

This leads me to an extensive set of questions:

Imagine you are a creator of an OS running on x86_64.
You have not yet created an abstraction for working with external devices. Somebody now plugs in a device using a USB - Port.

Does this interrupt the processor or does this change a flag the OS can read?
How would you make sure a routine is set up which will start communicating with the device once plugged in?
After this routine is set up, which protocols are you using to communicate with the device?
Does it matter that the device is plugged in via USB, or would other ports work the same? If it does matter, how does the program know? (x86: Which assembly instructions are achieving communication with any device?)
You have now figured out that the device is indeed a hard-drive. Is communicating with every hard-drive the same? You would now like to - only for the matter of further questions -  do the following: If this device contains another OS (OS-signature in boot section), start the other OS (reading), if however, the disk does not contain another OS you would like to inject your data to the disk at byte disk_size/2. (Writing) How would you accomplish that? (Protocol?, Assembly - Instruction?)
EDIT: In my mind, a UEFI is also a tiny little OS. The boot section -  in my mind - correct me if I am wrong - is a part of a hard drive where Bios or UEFI is searching the actual OS. So any OS could start another OS...

Kind regards!

Disclaimer: I am not asking for assembly code, I am asking for the mechanism in general. However, examples given in x86_64 are welcomed.


texts: Recurrent neural networks (Hopfield-like) with short limit cycles

texts:
Standard Hopfield networks exhibit stable patterns (states) which are attractors of a dynamic system. I wonder how to modify standard Hopfield networks such that they exhibit stable limit cycles as attractors. Since for binary neurons (to which I'd like to restrict my question) each attractor is a limit cycle of some length (because state space is finite), the question asks for "short" limit cycles (significantly shorter than the size of the state space, but longer than $1$).
Is there a simple standard recurrent neural network (of which - optimally -  Hopfield networks would be a special case, e.g. for some parameter $\lambda \rightarrow 0$) that typically gives rise to short limit cycles?
How many of these can there be (compared to the number of neurons), and how big can their added up basins of attraction be (compared to the size of state space)?
Toy example:

This mini network has one stable state $(00)$ with basin of attraction $\{00,11\}$ and one limit cycle $(10,01)$ with basin of attraction $\{10,01\}$


texts: What is the requirement for bubble sort to complete in 1 pass?

texts:
I am working on a problem where you're given $n$ distinct numbers, and you want to find the number of permutations such that it takes bubble sort at most 1 pass to complete.
e.g., if n=3, then the following permutations would only require 1 pass
1 2 3
1 3 2
3 1 2
2 1 3

But
3 2 1
2 3 1

would require more than 1 pass. Apparently the answer is $2^{n - 1}$, but I am not sure how to prove this for the general $n$ case.
My question is, what are the general constraints for a sequence to allow for it to be sorted with 1 pass of bubble sort?
It is difficult for me to come up with a generic formula to generate the permutations for larger $n$.


texts: I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My question is how do I get the average height of a BST with n nodes?


texts: Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently?

texts: And if it is not true, what are the problem classes or characteristics for which genetic algorithms are superior?


texts: $W$-hierarchy and parameterized search problems

texts:
I have two related questions:

What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? I mean, is there a similar classification like for the FPT class, that if there exists an algorithm which runs in a certain complexity then the problem is in $W[1]$ (for instance)?

If I have a decision problem that I know is in $FPT$ (or $W[1]$), does it mean that its matching search problem is also $FPT$ (/$W[1]$)? If not, how should I refer to a parametrized search problem? For instnace, I know that the $k-clique$ problem is in $W[1]$, then what is the correct classification of the problem of finding a clique of size $k$?


texts: Natural occurrences of monads that make use of the category-theoretical framework

texts:
Today, a talk by Henning Kerstan ("Trace Semantics for Probabilistic Transition Systems") confronted me with category theory for the first time. He has built a theoretical framework for describing probablistic transition systems and their behaviour in a general way, i.e. with uncountably infinite state sets and different notions of traces. To this end, he goes up through several layers of abstraction to finally end up with the notion of monads which he combines with measure theory to build the model he needs.

In the end, it took him 45 minutes to (roughly) build a framework to describe a concept he initially explained in 5 minutes. I appreciate the beauty of the approach (it does generalise nicely over different notions of traces) but it strikes me as an odd balance nevertheless.

I struggle to see what a monad really is and how so general a concept can be useful in applications (both in theory and practice). Is it really worth the effort, result-wise?

Therefore this question:

  Are there problems that are natural (in the sense of CS) on which
  the abstract notion of monads can be applied and helps (or is even
  instrumental) to derive desired results (at all or in a nicer way
  than without)?


texts: Decide if a string is in a language without simulating the automata accepting the languge

texts:
Is it possible for a Turing machine with input of a DFA that accepts a finite language and a string to decide whether the string is in the language without "fully simulating" the DFA on the string?

More formally, Is there a TM $M$ with a constant $C_M$ that can decide $L$, where for every input it halts at most $C_M$ steps after reading $w$'s last bit where $L$ is given by:

$L=\{\langle D,w\rangle \mid D\text{ is a DFA that accepts a finite language and $D$ accepts $w$}\}$?

I was thinking it is not possible, though I am not sure because maybe one can deduce from the encoding of the DFA without simulating the DFA what is the language.

I can't see how this can be done but not sure how to prove it can't be done.


texts: Multiple objects in one cell: spread them across multiple cells following the flow of the 3d projection

texts:
I am facing what to me feels an almost impossible problem.
I have some objects living in a 3d space. I want to create an interface with buttons where each buttons selects on of these objects. Since there may be hundreds of objects I am automating the process by projecting those objects onto a plane. I then round the values of x and y to be snapped to the closest cell on an imaginary grid I created. So far the process is easy and intuitive. The problem is I often get multiple objects inside the same cell. Moving them to the nearest empty neighbour would be easy, but I would get in most of cases very unintuitive results which would also be different from the original 3d flow. What I mean is this:

I have actually testes out a bunch of different approaches, like checking where the previous button was created and prioritize that direction, or prioritize one direction over the other based on the x/y position of the control in 3d space etc. All of them ended up having problems somewhere.
What feels like took me closer to the solution than other approaches is if a cell is already filled by another object, compare the bounding boxes of those controls in 3d and determing if I should take a step up/down or left/right or both. And this is what actually is used in the above screenshot but some controls are still messed up.
Especially on the body, where I have to create a lot of controls, this is even more of a problem:

I know that probably, unless you use AI or something like that, it will be impossible getting a perfect result and I am ready to clean up manually what I get in the end. However I also feel like what I have can be improved because I didn't manage to come up with a proper algorithm.
I leave below a screenshot of how it was previously done manually, just for a reference of what would be the very perfect result:

For example, one of the ideas I had to improve areas like the hair was to also add a cylindrical projection as well as a planar one.
Any help will be much appreciated!
thanks!


texts: Decisional problems vs Optimization problems : NP-COMPLETE vs NP-HARD

texts:
I'm studying some of computation theory and i encounter a big question mark. I have an optimization problem and i have to proof that is NP-HARD. I know that my problem can be reduced to another np-complete problem so my problem is np-hard. But my question is: why some algorithms are np-hard for the combinatorial version and the same problem transformed in a decision problem are np-complete?

I mean, if i have an optimization problem, is this np-hard because the decision problem can be reduced in a np-complete problem?


texts: Functional programming with branches that have no order?

texts:
I was wondering if there is any programming style in which the outcome does not depend on the order of statements or groups of statements such as guards. Vaguely, I imagine this would leave room for things like optimization or parallelization. Using the functional language Haskell as an example:

f x
 | x < 0 = -1
 | x > 0 = 1
 | otherwise = 0

is the same as:

f' x
 | x > 0 = 1
 | x < 0 = -1
 | otherwise = 0

Is it possible in some languages or paradigms to make the semantics of the function not dependent on the order in which the branches are defined (probably with special treatment of the otherwise case)?


texts: Does this excerpt from the linear probing Wikipedia page make an assumption?

texts:
Here is the excerpt from the linear probing page at Wikipedia.

  To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and continuing to the adjacent cells h(x) + 1, h(x) + 2, ..., until finding either an empty cell or a cell whose stored key is x. If a cell containing the key is found, the search returns the value from that cell. Otherwise, if an empty cell is found, the key cannot be in the table, because it would have been placed in that cell in preference to any later cell that has not yet been searched. In this case, the search returns as its result that the key is not present in the dictionary.

Does this assume that the linear probing function let's say P(x) is the same for insertion and searching? Must your linear probing function be consistent throughout the hash table? Is there a combination of linear probing functions that work best together?


texts: Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$

texts:
I'm new to writing languages in context-free or regular grammar, so I'm struggling how to do this one. It is a bit more complicated that simpler ones I've practiced doing. The problem is to construct a grammar for the following language:
$$\{a^n (bc)^m \in \{a, b, c\}^* \mid m, n \ge 1 \land m < n/2\}$$
An explanation of how to start and go through the language would be really helpful.


texts:
Given a string $(a_0,a_1,\ldots a_n)$. I want to find the length of the longest common prefix of the substrings $(a_0,a_1,\ldots a_{n-1})$ and $(a_1,a_2,\ldots a_n)$. I know this has atleast $O(n)$ complexity. Lets call this operation as prefix-suffix match.

I want to calculate prefix-suffix match length for all suffixes of a string. Now the naive algorithm which doesn't take into account that all the strings for which I am doing this operation are related has $O(n^2)$ complexity. Now my question is can we do this in better complexity.

Note that what I want is similar to LCP array of a slightly modified suffix array. Where the suffixes are sorted based on length instead of lexicographic ordering.


texts:
Possible Duplicate:
  Prove fingerprinting

Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that
$$\text{prob}(a \equiv  b \pmod{p}) \le c \ln(n)/(n^{c-1}).$$

Hint: As a consequence of the prime number theorem, exactly $n/ \ln(n) \pm O(n/\ln(n))$ many numbers from $\{ 1, \ldots, n \}$ are prime.

Conclusion: we can compress $n$ bits to $O(\log(n))$ bits and get a quite small false-positive rate.


texts: Planar Embedding with Some Nodes Constrained

texts:
I've read about basic planar-graph embedding and about embedding a planar graph onto a set of fixed points, but I was wondering how one might constrain the locations of some nodes—perhaps to a set of points—while allowing others complete freedom.

Is this achievable with a current popular algorithm, or with minor modification thereto? I guess the nature of the problem would lend itself better to grid-based embeddings, right?

I'm entirely new to graph theory, so it's possible the answer is obvious to those familiar with the field. I didn't see anything about it while searching.


texts: Dynamic programming: speed of top down vs bottom up approaches

texts:
I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. Is the top down approach significantly slower because of the recursion?

I thought that bottom up approaches needed to compute everything: eg if we have a result array of size n, we run a loop from i=0 to i=n to find result[i], whereas the top down approach only computes relevant entries (we start at i=n then go down to 0, but we might skip some of the entries in between). So I thought the top down approach would be faster.

Or maybe there was just a bug in my top down approach.

Update:
The problem on LeetCode is:
" You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1."

I defined an array result of size amount+1; result[i] is the minimum number of coins needed to reach amount i (with result[0] = 0).

If we have N coins, and coin j has value V[j], the recursion is:
result[i] = 1 + minimum of result[i-V[j]] for all j=1...N (only the j for which i-V[j]>=0)

I used a bottom up and top down approach to compute result[amount]:

If we don't have a coin of value 1, we won't need to compute result[i] for every i with a top down approach.

The time limit was exceeded for top down with this input: Coins: [186,419,83,408], Amount: 6249


texts:
This is a GRE practice question.

Which of the following regular expressions generate(s) no string with two consecutive 1’s? (Note that ε denotes the empty string.)

I. (1 + ε)(01 + 0)*

II. (01+10)*

III. (0+1)*(0+ε)

(A) I only

(B) II only

(C) III only

(D) I and II only

(E) II and III only

My understanding is that neither I nor III generates strings with 11. In I, a string containing 1 is either 1 or 1 surrounded by 0's. In III, all 1's are preceded by 0's. But the correct answer is A, so III must generate a string with 11 somehow. Please explain. Thanks!


texts: Why does Non Determinism not enhance FA like it does for PDA

texts: Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of context free languages that Non deterministic Push Down Automata can recognize.  Is there any intuitive reason for this? It would seem that NFA's should be more powerful than DFA's but they turn out to be equivalent


texts: Algorithmic complexity of a Maximum Capacity Representatives variant

texts:
I have been trying to find the algorithmic complexity of a problem that I have. I am almost sure it is either NP-hard or NP-complete but I cannot find any proof. Recently, I found that my problem can be something similar to a special instance of the Maximum Capacity Representatives problem, which is NP-complete. However, the objective function to optimize in my case is different than the one in the MCR problem.

The problem that I am trying to solve is the following:

INSTANCE: Disjoint sets  $S_1, \ldots, S_m$ and, for any $i \neq j$, $x \in S_i$, and $y
\in S_j$, a nonnegative capacity $c(x,y)$.

SOLUTION: A system of representatives $T$, i.e., a set $T$ such that, for any $i$,  $\vert T \cap S_i\vert=1$.

MEASURE: $\min \{c(x,y): x,y \in T \}$.

And my goal is to maximize $\min \{c(x,y): x,y \in T \}$.

Do you know any way to determine the complexity of my problem? Is there any well known problem in the literature that can be reduced to this one?,

Thanks in advance.


texts: Double-nested loop with bitwise operation

texts:
I have this little exercise:

for ( i = 0; i < 2 * n; i += 2 )
  for ( j = 1; j <= n; j <<= 1 )
    if ( j & i )
      foo ();

(j <<= 1 means j = (j << 1), where << is the bitwise left shift operator. & is the bitwise and operator.)

I am supposed to determine how many times will the foo function be called for some n. The result should be both an exact number (or the most accurate approximation possible) and asymptotic (like O(n)).


texts: What techniques exist for energy-efficient computing and networking?

texts:
I am currently reviewing the potentials of cloud computing regarding energy efficiency and green IT. In connection with this review I am having a look on techniques for increasing energy-efficiency in data centers (computing), hardware, networking and storage devices.

Specificially for computing/servers I have found already a few:

energy-aware scheduling techniques utilizing frequency and voltage scaling
virtualization to consolidate server resources
energy-saving hardware, e.g. ACPI, several processor techniques, especially for mobile devices etc.

However, for networking devices it is rather hard to get information about energy-saving technologies. I have read that people are thinking about new protocols and alternative routing methods to be able to switch off hardware if the network is under low load. Does anyone know of such examples?

Which other points should be added, either for networking or computing


texts: what is a shearlet/shearlet transform and how can i use it?

texts: from what wikipedia says shearlet is a successor to wavelets(whatever that is) and that they are extremely good at representing complicated data efficiently. But neither wikipedia nor other articles that i found have any layman definition of shearlets in it. A layman definition would be great and algorithm to implement them on say images would be awesome and a python implementation would be godsend.


texts: Show that a language cannot be generated by linear grammar

texts:
I have a language $ L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$  that is a language with even number of b's.

I found a grammar for it with these rules:

$S \rightarrow aS \ | \ bL \ | \ \lambda  $

$L \rightarrow aL \ | \ bS \  $

How could I show that this language cannot be generated by linear grammar?

According to Wikipedia, a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of its productions.


texts: Linear-time algorithm for solving a set of inequalites

texts:
We have a set $A$ of $n$ distinct numbers. We want to determine for all  $x,y,z \in A$ whether the following relations hold.

$$
x+y>z\qquad x+z>y\qquad y+z>x
$$

Anyone could describe $O(n)$ Algorithm?


texts:
I have this task for Analysis of Algorithms module in university

$$
\begin{align*}
W, V &= \{v_1, v_2, v_n\}, S = \{s_1, s_2, s_n\}\\
G(W) &= \max~_{i:w_i\leq w} ~\{G(W-s_i) + v_i\}, G(0)=0\\
\end{align*}
$$

I am not sure what does the marked text mean in this recurrence formula. Because I think $W$ is a variable not an array so $i\colon w_i<w$ does not really make sense to me. Could someone please explain this to me?


texts: anonymous lambda functions (functional programming)

texts:
What are anonymous (lambda) functions? What is the formal definition of an anonymous function in a functional programming language?

In my simple terms, when I am programming in scheme/lisp I would say an anonymous (lambda) function is a function that is not bound to an identifier.

Is that all that you can say formally about a lambda function? I think there is more detail that can be added to this simple definition. Please elaborate, and thank you!


texts: Are there many empirical results about which metaheuristics are well-suited for which problem domains?

texts: One of the nice things about genetic algorithms is that they can easily be used for a diverse array of problem domains, whereas PSO for example seems best-suited for candidates of real-valued vectors (although I am aware of the use of the latter in combinatorial problems). It has, however, occurred to me that, by using genetic algorithms because they are familiar and easy to apply, I could be forgoing a better solution with a different metaheuristic. To avoid subjective discussion, I am of course looking for carefully gathered empirical results about this subject matter. I can't seem to find too many on my own.


texts:
S ::= x
S ::= if E then S
S ::= if E then S else S

This is example if E then if E then x else x proves that it is ambiguous but I don't see why? Isn't it just an if statement within an if statement.


texts:
In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:

  The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.

We define "randomly built binary search tree on $n$ keys" as:

  a binary search tree that arises from inserting the keys in random order into an initially empty tree, where each of the $n!$ permutations of the input keys is equally likely.

In the proof, we defined some random variables:

Let $X_n$ denotes the height of a randomly built binary search tree on $n$ keys and the exponential height $Y_n = 2^{X_n}$. Of the $n$ keys, we choose one key as the root of the tree, and we let $R_n$ denotes the random variable that holds the position that this key would occupy if the set of keys were sorted (also know as 'rank' in the text). If we know that $R_n=i$, it follows that $Y_n=2\cdot max(Y_{i-1},Y_{n-1})$.

We also define indicator random variables $Z_{n,1}, Z_{n,2}, ..., Z_{n,n}$, $Z_{n,i} = I\{R_n=i\}$.

  \begin{equation}
\begin{split}
E[Y_n] & = E\Big[\sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))\Big] \\
& = \sum_{i=1}^{n} E[Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))] && \text{(by linearity of expectation)}\\
& = \sum_{i=1}^{n} E[Z_{n,i}] E[(2\cdot max(Y_{i-1}, Y_{n-i}))] && \text{(by independence)}\\
\end{split}
\end{equation}

I would like to ask why is the last equality correct? In other words, why can we assume independence of $Z_{n,i}$ and $max(Y_{i-1},Y_{n-i})$?

In the proof, there was a brief explanation:

  Having chosen $R_n = i$, the left subtree (whose ranks are less than $i$. This subtree is just like any other randomly built binary search tree on $i-1$ keys. Other than the number of keys it contains, this subtree's structure is not affected at all by the choice of $R_n=i$, and hence the random variables $Y_{i-1}$ and $Z_{n,i}$ are independent. Likewise, the right subtree, whose exponential height is $Y_{n-i}$, is randomly built on the $n-i$ keys whose ranks are greater than $i$.

However, since $R_n$ does affect the number of keys $Y_{i-1}$ and $Y_{n-i}$ contain (as acknowledged by the explanation above), wouldn't it mean that  $Y_{i-1}$ and $Y_{n-i}$ are dependent on $Z_{n,i}$?

A note regarding similar questions posted on CS stackexchange

I have read the answers for the following questions which are very similar to mine:

Proof that a randomly built binary search tree has logarithmic height
Average height of a BST with n Nodes.
Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

For 1 & 2, the question was a more general one which asked for an explanation for the entire proof. Also, the answer for both questions did not attempt to justify the independence and simply used the result.

For 3, the question was based on a MIT lecture, https://www.youtube.com/watch?v=vgELyZ9LXX4 and it lacked some of the details which I have included above. Also, the answer was also not clear.


texts: As a number (base 10) approaches infinity, what would be longer? Represented in BCD or Base-2?

texts:
My professor asked this question in his lecture class and I can't figure out the answer.

My guess is BCD because you can't use up all the numbers (10 to 15), so you eat up space?


texts: Why does Insertion sort take linear time in this case?

texts:
Remove any 5 elements from a sorted array of n items and replace them with 5 new elements.
Why does running Insertion sort again on this array take linear O(n) time, I tried counting the number of swaps when running Insertion sort again, and noticed every element is shifted by at most 5 places(not sure why), I cannot get the intuition behind why this takes linear time?
Wouldn't the new elements affect the position of the unchanged items in the array as well?
Appreciate any explanation on this!


texts:
The activation of a perceptron style neuron is:

$DotProduct(Inputs, Weights)+Bias > 0$

That is essentially classifying what side of a (hyper)plane a point is on (positive or negative side), like the below:

$DotProduct(Point, Normal)+D > 0$

Looking at an N input, M layer perceptron network that has a single output can be seen as classifying a point as inside or outside some hyper shape.

But, it seems like all the tests are linear, and switching to sigmoid activation doesn't seem to add a whole lot of non linearity - like if you were visualizing this NN shape, even a sigmoid activated network would be mostly made up of planes, not curved surfaces.

On the other hand we have support vector machines as a machine learning tool, and using things like the "kernel trick" which can make a non linear classification of points for being inside or outside.

This makes me wonder, is there a version of neural networks that has more free form separation shape?

It seems like it would be possible to have a better performing neural network with fewer neurons and/or layers.


texts:
How do you search related works for your papers? To be concrete I have implemented few techniques of indirect call promotion for pure C and want to share my results. But at first I want to understand if there are some existing papers about it.

I searched with Google, Google shcolar, citeseerx, microsoft academic search, acm library and semanticscholar. I found only papers on C++ devirtualization but not for pure C. I searched the papers referenced to those what I found but I still did not found anything about pure C.

Can I think my research will be uniqe and interesting for scientific community or I just failed to find existing papers?


texts: Compiler that compiles to a Turing machine?

texts: I am interested in finding/writing a compiler that compiles a program written in a simple source language to a Turing machine (instead of assembly).  Does anyone know if there is a good approach for writing such a compiler, or if there is a Turing machine compiler already out there (that would be ideal)?  Of course it is possible to do this in theory; it's just that it's very challenging (for me at least) to work out the details in practice.


texts: Wouldn't a Red-Black tree fix up after insertion mess up the BST ordering?

texts:
I've been reading about fixing up after an insertion into a red black tree. (http://web.cse.ohio-state.edu/~lai/2331/0.Red-Black%20Trees.pdf)

The most surprising part is not that there are 6 things that we need to do after inserting into a red black tree. i.e. if both parent, uncle red, then parent, uncle black, grandparents red, replace inserted value with grandparent. The most surprising part is that wouldn't this blatantly mess up the BST ordering such that a node x is always greater than the left side and less than the right side?

In above link, page 10, the author just replaced grandparent with the newly inserted node x. Wouldn't this completely mess up the BST ordering? Can someone explain if BST ordering should be preserved in a red-black tree and why rotation/fix up after insertion will not have any affect on this ordering?


texts: Algorithm to identify top $\log n$ elements in $O(n)$ time

texts:
Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top $\log(n)$ frequent flyers, where n is the total number of the airlines’ frequent flyers. Their current algorithm runs in $O(n \log(n))$ time to sort the flyers scan the sorted list to pick the top logn flyers. Describe an algorithm that identifies the top $\log(n)$ flyer in $O(n)$ time.

How can I devise an algorithm for this problem? I tried to solve it with priority queue ADT and some well-known sorting, but cannot solve this problem.


texts: Is there any demonstrably uncomputable concrete problem which does not rely on diagonalization?

texts:
So diagonalization as we all know is an extremely productive way of showing uncomputability, the other main tool used by CS people for this task being reduction.

But it has occurred to me that I do not know a single uncomputable problem whose demonstration of uncomputability does not rely on diagonalization or reduction to a problem which relies on diagonalization.

Is there any example out there?