texts: Random paths from one point to another going through all the cells of a square grid

texts:
I am looking for a very specific algorithm, so I think it doesn't exist yet. I would be satisfied if anyone was able to give me some hints to develop it.

My problem is about a square grid of size n x n, where n is an odd natural number ≥3. For instance, it can be a 5 by 5 grid:

.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.

The middle cell of the first column and the middle cell of the last column must be found:

.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
| ● |   |   |   | ● |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.
|   |   |   |   |   |
.---.---.---.---.---.

Then, and this is the hardest part of the algorithm, I want to get a path from the left-most point to the right-most one, that goes through every cell of the grid.

For example, this is one possibility:

  > > v   > > > > v
  ^   v   ^       v
  ^   v   ^   v < <
  ^   v   ^   v
  ●   v   ^   v   ●
      v   ^   v   ^
  v < <   ^   v   ^
  v       ^   v   ^
  > > > > ^   > > ^

and this is another:

  > > > > v   > > v
  ^       v   ^   v
  < < <   v   ^   v
      ^   v   ^   v
  ● > ^   v   ^   ●
          v   ^
  v < < < <   ^ < <
  v               ^
  > > > > > > > > ^

This implies directly some obviousnesses. Let a be the number of up displacements, b down, c left and d right, we can know that:

a + b + c + d = n^2 - 1
a = b
d - c = n - 1

I also want to randomize the creation of this path, and the best would be a uniform distribution amongst all the possibilities (I don't know their number but I am almost sure it increases as n increases).

I think it can be solved thanks to graph theory since my grid can be considered as an unoriented graph where the vertices are the cells and where two adjacent cells are linked with an edge. The problem is now equivalent to making a non-redundant graph traversal, but I have no idea where to begin.

I hope my question was clear enough, thanks in advance.


texts: simulation of PDA with 2-tape Turing machine

texts: Can someone give me suggestions how can I construct a 2-tape Turing machine which simulates PDA ?


texts: Recurrent relation for algorithms with two stages

texts:
I am trying to do the recurrence relation for my algorithm, but it has two variables $T(n,m)$. For sufficiently small $n$, $m$ is practically the same as $n$, but $m$ cannot grow beyond some constant $k$. So once $n$ grows beyond $k$, $m$ turns to constant $k$. So it has two different stages.

I have done the relation in both cases: when $m$ is another variable, and when $m$ is a constant, but how do I put them together?

Using $a=2, b=2$ as an example: this recurrence relation with $m$ as a variable like $n$:
$$T(1)=1$$
$$\begin{equation*}
\begin{split}
T(n) & = 2T(\frac{n}{2})+m \\
& = 2T(\frac{n}{2})+n\\
& = n+nlog_2n
\end{split}
\end{equation*}$$

Treating $m$ as a constant:
$$\begin{equation*}
\begin{split}
T(n) &= 2T(\frac{n}{2})+m \\
&= n+mn-m
\end{split}\end{equation*}$$

Please feel free to check my math. Now how do I represent this as one recurrence relation? $m$ cannot grow beyond constant $k$.


texts: Terminology - the reason for symbol reuse in programming languages

texts:
What is the term in programming language creation that is the rationale for symbol reuse? Though potentially confused with overloading, it is not so much the application of symbol reuse, but the logical result of a limited vocabulary in the world of common symbols.

I seem to recall running in to the term when reading about the development of C - that one eventually runs out of simple symbols, so the language designers took a reasonable approach to use familiar symbols to mean different things, rather than invent new symbols for every new need. Additionally, they desired to stay within the 7-bit ASCII alphabet. The particular meaning is determined by the number/type of operators used or the broader context.

An example is from C/C++ where < is used as

a delimiter in template definitions (template <int N>)
#include delimiter, searching system headers first (#include <filename>)
a less-than comparison operator (x < y)
left bit shifts (x << n)
the ostream operator (std::cout << val << std::endl)

Point - there are cases of symbol reuse beyond strict overloading, and I believe that there is a one-word term whose definition is something like "the condition of using the same symbols for different purposes by necessity or for the sake of maintaining familiarity."


texts: Are there inverse terms in term-rewriting systems?

texts:
Let
$S$ a set,
$f$ a bijective function in $S$,
$\phi$ the inverse of $f$.
Because $f$ and $\phi$ are the inverse of each other, $f\circ\phi=\phi\circ f=id$ (or $f(\phi(z))=\phi(f(z))=z$).
$f$ and $\phi$ are represented by terms in a term-algebra $T$ whose operations are unary and/or multiary mathematical functions.
What are the term-rewriting rules for representing the above interrelations?
Let a term $t_f\in T$ representing $f$ be given. How are the inverse terms of $t_f$ defined?
I already know the article Wikipadia: Rewriting and the keywords therein.


texts: Should I go for computer science or maths?

texts:
I am in 11th grade. The only subject which I love the most is solving alegebraic equations and questions related to it. I enjoy doing trigonometry but hate the part of proving theorems. I opted computer science for the first time. This is just basic. But whenever I can't understand a CS question, I doubt that I should go for cs or for maths in my bachelors. I don't know which subject is more related to my interest and talent. Would somebody please explain it?

Sorry for the tags!!


texts:
Let's consider the following formula:
$\square (\neg A \cup B)$.

Does the following computation satisfy it?

The numbers in brackets are number of state.

(0) $\neg A, \neg B$

(1) $\neg A, B$

(2) $A, \neg B$

$\square$ means that for every state in computation the formula $\neg A \cup B$ is satisfied, so: In $0$ state it is satisfied. In $1$ it is satfisfied. But, in $2$ state it is unsatisfied because $\cup$ says that $A$ must be false until $B$ is true.

So, the formula is not satisfied.

But, it seems that my reasoning is incorrect because I test it for simple program in Promela and my tests suggest that the formula is satisified, though, my reasoning is incorrect.

Please help me .

inline test_and_set(addr, old) {
  d_step{
    old = addr;
    addr = 1;
  }
}
byte lock;
active [2] proctype proc(){
  byte old;
  do
  :: true ->
    wait:
      test_and_set(lock, old);
      do
      :: old != 0 -> test_and_set(lock, old);
      :: else -> break;
      od
    cs:
    lock = 0;
  od
}

ltl prop {((!proc[0]@cs) W proc[0]@wait) // (***)

And I verified it with
spin -a test.pml  ; gcc -O2 pan.c -o pan ; ./pan -a -f

And it has 0 errors. When I replace (***) with ltl prop{([](!proc[0]@cs) W proc[0]@wait))}
I've got an error.

Why?


texts:
I am struggling to analyze the runtime complexity of the following algorithm formally:

Given a string s and a dictionary of words dict(wordDict), add spaces in s to
construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s = "catsanddog", dict = ["cat", "cats", "and",
"sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

The proposed algorithm:
    wordBreak(s, wordDict) {
        res; //a container used to store the final result.
        if(the length of s is zero or s is invalid) {
            just output res directly.
        }
        if(we have already encountered s before) {
            return the res that s corresponds to.
        }
        if(wordDict contains s) {
            add s to res.
        }
        (looping index from 0 to the length of s) {
            t = the substring of s starting from index to the end of s
            if(wordDict contains t) {
                temp = wordBreak(substring of s from 0 to index , wordDict);
                if(temp is not empty) {
                    (looping index j from 0 to the length of temp) {
                        cancatenate the jth element of temp with t and add it to res.
                    }
                }
            }
        }
        store the result of s to storage.
        return res;
    }
}

My analysis:
Giving the algorithm, denote the length of $s$ by n. Suppose the runtime complexity is $T(n)$, then we would have something like $T(n) = T(n - 1) + T(n - 2) + \ldots + T(0) + n + 2^{n-1} - 1$, where I add $n$ because we are looping through $s$. In the meantime we are looping through temp which is a list of results. In the worst case temp can contain $2^{n-1} - 1$ results(subdivisions coming from a string of length $n - 1$). However this does not take into consideration the effect of memoization and I do not know how to achieve that. Specifically my question are:

What is the correct time complexity analysis? My guess is that it is at least $n 2^{n-1}$ which is the time taken to create the result list but this is a wild guess without formal proof.

How does the analysis differ from the case where there is no memoization.


texts: How to resize a large, distributed hash table?

texts:
Many hash table implementations found in programming languages (such as Java's HashMap or Python's dict) dynamically increase the size of the hash table once the number of items reaches a certain threshold. In these cases, resizing the hash table means allocating a new, larger memory area, re-hashing all the items and moving them from the old to the new memory region. Because resizing is done "rarely", insertion is still O(1) amortized.

This may be fine if the hash table is stored in memory and if the number of items is relatively small, however what about large distributed hash tables?

Suppose that I have a cluster of 100 PostgreSQL databases, each one containing terabytes of data. What happens if I add a new database to the cluster? Will all the items be re-hashed and moved around? I strongly doubt that, as the operation could take several days to complete.

Hence my question: what is the strategy adopted in those cases?


texts: What does it mean by putting (\alpha-\beta) in front of the authors of a paper

texts: When I was searching the publication list of some CS researchers, I sometimes saw them putting a ($\alpha-\beta$) or ($\alpha-\beta$ order) in front of the authors of a paper. What does this mean?


texts:
How does exactly 1 in 3 sat work given the variables Xi, Xy, Xz if one of the variables in the formula are negative.
We know that the results are if they are all positive given that:
R(Xi, Xy, Xz) =
TFF
FTF
FFT

How would the result look like if one or two of the variables were negative? R(-Xi, Xy, Xz) or R(-Xi, Xy, -Xz)


texts: Extended Compact Genetic Algorithm question

texts:
I have a question regarding the ECGA algorithm. This is what I'm currently studying. If ECGA builds a model of the parent pool using the 'minimum description length' (MDL) measure, why cannot we simply choose the model which has the most likely fit of the parents?

Thanks.


texts: Understanding a binary classifier problem

texts:
I'm trying to understand a problem that's more mathematical in nature that I'm accustomed to. Below I'll try to present the problem and what I have so far understood of it.

The problem

We have $X_1,..,X_n$ i.i.d. binary outcomes distributed according to Bernoulli distribution. The probability that $X_i = 1$ is given by $E[X_i] = p$. Hoeffding's inequality is somehow useful in solving the problem. It tells us that the total number of outcomes with value $1$ divided by $n$ is not too far from its expectation, which is $E[\frac{1}{n} \sum_{i=1}^n X_i] = \frac{1}{n} \sum_{i=1}^n E[X_i] = p$:

$Pr[|p-\frac{1}{n}\sum_{i=1}^n X_i| > \epsilon] \le 2exp(-2n\epsilon^2)$

Now I have to solve for the value $\epsilon$ for which the above probability equals $\alpha$. E.g. $n = 10$, $\alpha = 0.05$ this provides a bound that guarantees that with 95 % probability, the observed number of occurrences of $X_i = 1$ is within the interval $[n(p − \epsilon), n(p + \epsilon)]$. I must also evalute the width of this interval.

My understanding right now

The outcomes $X_1,..,X_n$ are something like coin tosses with a biased coin. We have some expectation $p$ for the coin toss to equal heads. The Hoeffding's inequality part says that if we take the sum of all of the expected values and multiply it with $\frac{1}{n}$ we get something close to $p$ (but why is it not $\frac{np}{n} = p$?) and the probability for it to be greater than $\epsilon$ is some (rather small?) number.

Now if we use the values of the example, the inequality would look like $0.05 \le 2^{-20\epsilon^2}$. I suppose I could solve that $\epsilon$ but the result is still an inequality and I think I need a concrete value to calculate $[10(p - \epsilon), 10(p + \epsilon)]$.

And if I'm correct the answer to the problem is some real valued range like $[5, 8]$ which says that there's a 95% possibility to get from 5 to 8 heads in 10 tosses, but I have no idea how to come up with the true range using that inequality.

I'm also not sure whether it's good to apply any real world scenarios in to this kind of abstract problems, or should I just try to learn to think on an abstract level and forget about the physical world? Especially if I'm to see a lot more problems like this.

Do you know of any materials that could possibly show me what's actually going on in that kind of equations? It's ok if I can't solve the problem but I would love to understand it on a level that doesn't make me want to scream and run away.

tl;dr

I'm having a hard time understanding probability distributions and inequalities with greek letters, but I would like to. Right now I'm stuck and I could use a pointer to the right direction.

I'll try to post updates as I go on.

Update

Ok so this is what I gathered:

So what the inequality is essentially saying is that when the amount of trials grows, the probability that we would deviate from our expected average by over some number $\epsilon$ decreases. And higher deviation also means smaller probability. It makes sense if I consider those coin tosses, because it's easy to see that during a large amount of trials the distribution should follow the the bias (if the coin has some).

Now if I estimate this $\alpha = 0.05$ for $100$ trials, I get that $2e^{-2*100*0.136^2} = 0.0494 \le 0.05$, which allows me to claim that in 95% of the cases I would deviate from the expected average by at most $0.136$.

How we arrive in to this conclusion without knowing anything about the initial probabilities is still beyond me. If I do not know them, the interval in the problem will take the form of $[100p-0.136, 100p+0.136]$ if I'm not mistaken?

Thanks for the explanation, I hope I understood it correctly and my apologies in advance if I didn't.


texts: Relation between determinant and matrix multiplication

texts: I remember reading somewhere that if matrix multiplication can be done in $O(n^\omega)$ time then determinants can be computed in $O(n^\omega)$ time. I am unable to find the reduction and would it be possible for someone to share the reference?


texts: Formulating an arrangement problem with STRIPS

texts:
The problem is rearranging furniture in a flat.
We are given rectangular rooms of natural width and height with doors between them, (the walls have no width)
and rectangular furniture at starting positions and goal positions.
The operations are moving each piece of furniture one block each direction (up,down,right, left), and rotating it 90 degrees at each direction.

Information about the STRIPS language:
1. The state of the world consists of first order ground atoms: Only positive predicates on ground objects.
2. Operations consist of: a list of bound variables, and the following sets: preconditions (with positive or negative atoms) and effects (with positive or negative atoms) with no free variables.
3. An operation can to be turned into an action using substitution of all variables of the operation, resulting in preconditions and effects with positive or negative ground atoms
4. A relevant operation is one that given the current goal state, can be turned into an action such that the effects hold in the state.

How can I formulate preconditions to these operations?
What I came up with up until now is that I need to represent each 1x1 square as an object in the propositions.

The main thing I don't understand how to model is that each operation's precondition needs to depend on the furniture size - the amount and position of blocks that need to be clear to move a piece of furniture depends on it's dimentions.

Rotating would be even more complex; some of the new positions of the piece of furniture would need to be checked to be empty (what is currently not taken by the piece of furniture) and some would not (what is currently taken by the piece of furniture).

How is it possible to model it into the form of STRIPS?


texts:
I have been looking for a method to find the width of a line.

I found the solution(link: http://www.mathworks.com/matlabcentral/answers/88645-average-width-of-lines),

"sum up the image to get the area, then skeletonize the image and sum up that image to get the total length.Then divide the area by the length."

Can anyone please explain the following?
1. what is summing up to get image area?
2. what is summing up skeletoniized image to get length?
I did not get this.

I have to find the thickness of a string from a given image. I can take the image of any dimension and quality I want. How do i measure the thickness of a string? That is what I was trying to resemble as width of a line. Essentially, thickness of a string can be thought as width of a line, I think.

Moreover, I can not assign any unit to my measurement i.e., m/cm/mm. So I have to measure some sort of ratio to represent the thickness and reach a decision.

My outcome should be Yes or No based on the thickness. For example, if the thickness is greater that a certain value I would not take the string to process.

The string can be made of anything.


texts: How convert instances of a language efficiently into 3SAT instances?

texts:
The following question is from Sanjeev Arora and Boaz Barak ( not homework )

  Show that for every time constructible
  $T:N \to N$, if $L \in NTIME(T(n))$ then we can give a polynomial-time Karp reduction from $L$ to $3SAT$ that transforms instances of size $n$
  into 3CNF formulae of size $O(T(n)logT(n))$. Can you make this reduction also run in $O(T(n)logT(n))$?

The best I could come up with is a $O(T(n)^3)$ formula. We take each configuration to be of at most length $T(n)$ and the machine runs for $T(n)$ steps. So we have a grid of $T(n)$ rows each with $T(n)$ columns. Each row represents a configuration. We just impose the condition that each row follows from the previous by using $M's$ ( where $M$ is a machine deciding $L$ in $O(T(n))$ time ) transition function in at most one step. The first row should represents start configuration and last row represents the accept configuration. Thus an $O(T(n)^3)$ formula is formed by this approach.
How can I do better ?


texts: What do we do instead of DFS on directed graphs?

texts:
All the example of DFS I've seen so far are for undirected graph.
In a directed graph the basic DFS algorithm won't work because some vertex will be unreachable.

The algorithm I'm talking about :
https://en.wikipedia.org/wiki/Depth-first_search

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do
9                  S.push(w)

Example :

So let's say I start with '1' I will never access 4,5,6 with this algorithm.

For directed graph it looks like we have to know all the vertex and iterate through them.

And so we cannot use a DFS for directed graph ?

Is there a DFS variant or another algorithm ?


texts: How can a one-counter machine accept $a^n b^n c^n$?

texts:
It is mentioned in Which languages are recognized by one-counter machines?
that a one-counter machine can accept $\{a^n b^n c^n\mid n\geq 0\}$. Can someone please explain how this is done?


texts:
As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages.

$$L_1=\{w│w^R∈A\}$$
$$L_2=\{w│w=a_1 b_1,…,a_k b_k;a_i∈A,b_i∈B\}$$
$$L_3=\{xy│yx∈0A\}$$
$$L_4=\{w│w∈A,∄y∈B:w=xyz for some x,z∈Σ^* \}$$
$$L_5=\{w│∃x∈B:wx∈A\}$$

I've already come up with answers for the first two, but I've no idea about the rest. For L3 no information on what x and y are is provided, so I thought they must be strings concatenated together.

My main question is, is there any generalized algorithm which by using it one can derive an appropriate NFA or RegEx to prove that such languages are regular? Could these things be broken down into primitive structures or operators by some rules or methods so the corresponding NFA or RegEx for the constructive proof be derived from it?


texts: Validating attempt on NFA to Regular Expression

texts:
So i tried turning the following NFA into a GNFA (first attempt).

Please don't ask why i chose to do such a complex NFA on my first try, i just like the challenge i guess?

ab is the concatenation of a and b, the language consists of a, b and c.

$L = \{a, b, c\}$

I calculated the following to be the Regular Expression of the NFA:

$b^{+}c$ $\cup$ $(((a$ $\cup$ $b^{+}ab)\cup(b^{+}c(b$ $\cup$ $cb^{*}c)))(a$ $\cup$ $cb^{*}ab)^{*}(b$ $\cup$ $cb^{*}c))$


texts: EQtm is not mapping reducible to its complement

texts:
This is a problem from Sipser's book (marked with an asterisk).

$EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$

We know that neither $EQ_{TM}$ nor $\overline{EQ_{TM}}$ are recognizable so unsure how to go about proving there can't be a mapping reduction from one to the other.

Any hints?


texts: Proving satisfiability using resolution and variable elimination

texts:
I don't 100% understand this. But I have a entailment, and I want to prove whether it is satisfiable or not, and I will do this using resolution and variable elimination.
Here is the formula:
$$
(x_1 \lor x_2 \lor x_6) \land (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) \land \\ (\lnot x_4 \lor x_5 \lor x_7) \land (\lnot x_4 \lor x_6 \lor x_8) \land ( x_5 \lor \lnot x_6) \land \\(\lnot x_6 \lor x_7 \lor \lnot x_8) \land (x_7 \lor \lnot x_8 \lor \lnot x_{10}) \vDash \lnot(x_7 \lor \lnot x_9 \lor x_{10})
$$
First I negate the conclusion and move it into the premises. If I can prove this to be ⊥ using Resolution, I have proven that the original entailment IS satisfiable. So this is what I want to refute by using resolutin (and variable elimination to simplify).
$$
(x_1 \lor x_2 \lor x_6) \land (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) \land \\ (\lnot x_4 \lor x_5 \lor x_7) \land (\lnot x_4 \lor x_6 \lor x_8) \land ( x_5 \lor \lnot x_6) \land \\(\lnot x_6 \lor x_7 \lor \lnot x_8) \land (x_7 \lor \lnot x_8 \lor \lnot x_{10}) \lor (x_7 \lor \lnot x_9 \lor x_{10})
$$
So I start off by eliminating all clauses with $x_7$ since it's a pure literal, which leaves me with
$$ (x_1 \lor x_2 \lor x_6) \land (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) \land \\ (\lnot x_4 \lor x_6 \lor x_8) \land (x_5 \lor \lnot x_6) $$
Here $x_5$ is a pure literal, so that one clause can be removed.
$$ (x_1 \lor x_2 \lor x_6) \land (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) \land (\lnot x_4 \lor x_6 \lor x_8) $$
Now $x_6$ is a pure literal, which would leave just the two clauses
$$ (\lnot x_1 \lor x_3 \lor x_8) \land (\lnot x_2 \lor \lnot x_3 \lor x_4) $$
However, here $x_8$ is a pure literal, thus leaving us with only one clause, and that clause contains pure literals. Can it really be simplified into nothing? It feels like I'm doing something wrong but I'm not sure what it is that's wrong.
If I really can simplify into nothing, would that mean that the original formula is satisfiable or not satisfiable?
Since all the clauses contain a pure literal, wouldn't that make it impossible to resolve?


texts: Finding a reduction for two-Subset sum problem

texts:
I'd like to prove that the following problem is NP-complete. I'd just like to know what reduction I should do:

Two Subset Sum: Given a set S of integers and an integer T, determine whether there are two subsets of S such that the sum of the numbers of one is T and the other is 2T. The subsets do NOT have to be disjoint.

And I want to use the classic subset problem to prove this:

Subset Sum: Given a set S of integers and an integer T, determine whether there is a subset of S such that the sum of the numbers is T.

I'm slightly struggling with the reduction from Subset-Sum to 2-Subset-Sum, as simply adding to the set the double of each number and using the same T does not work, e.g S = {1,7,8,5} and S'={1,2,5,10,7,8,14,16} with T = 10 wouldn't work, as S' would return "true" and S should return "false".

Thank you.


texts:
I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident with it to say so. Well on average we go $\log n$ deep and need at max $|\Sigma|$ steps to find a corresponding node that matches (or not). Thus I would come up with $O(n \cdot |\Sigma| \cdot \log n)$.

  Repeat the following for all suffixes of the given string, right to left.

  Scan if its in tree

  Not in tree -> add it as new node
  Is partly in tree -> fork here, such that the matching part remains

  Go back to step 1 until the sequence that was observed equals the source


texts:
I drew a Push-down Automata, accepting the following language:
$$
\{ xcy : x,y \in (a+b)^*, \#_a(x) > \#_{bb}(y) \}.
$$
Here $\#_{bb}(y)$ counts the number of times that $bb$ appears in $y$, with overlaps. For example, $\#_{bb}(bbb) = 2$.
My question here. Is it possible to reduce my PDA to less states? Thanks.


texts:
Whenever I've come across this question whether on the internet or in my class everybody mentions the 4 address sequencing capabilities required in a control memory and the steps of address sequencing:
1. Incrementing of the control address register
2. Unconditional branch
... Etc.
But what is the "definition" of address sequencing?
How do I explain it in 1-2 lines ?


texts:
I came across this implementation of PJW and it seems incorrect:

  h = ( h << 4 ) + ( k );
  if( ( g = ( h & 0xf0000000 ) ) != 0 )
  {
    h = ( h ^ ( g >> 24 ) ) ^ g;
  }

In a more readable form:

  h = ( h << 4 ) + k;
  g = h & 0xf0000000;
  if( g != 0 )
      h = h ^ ( g >> 24 ) ^ g;

(Syntax: << and >> are bit shift operators, & is bitwise and, | is bitwise or, ^ is bitwise xor, ~ is bitwise negation, = is assignment, != is not-equal.)

Should it resemble this instead?

    h = ( h << 4 ) + s;
    s = s + 1;
    high = h & 0xF0000000;
    if ( high != 0 )
        h = h ^ (high >> 24);
    h = h & ~high;

A DrDobbs article says "Unfortunately, Holub's version contains an error that was picked up in subsequent texts (including the first printing of Practical Algorithms for Programmers, by John Rex and myself). The bug does not prevent the code from working, it simply gives suboptimal hashes." and I'm wondering if the difference between the top and bottom (edited) is that misprint.


texts: When can theta be used for different values?

texts:
On the course material I am following we have been given an explanation for theta as being when omega and Oh 'sandwich' the run time, so it is bounded between the two values, at least I think this is how it is explained based on my interpretation.
So I was surprised to then find this as I have gotten further through the course:
Given the worst case running time for MAX-HEAPIFY - Ө(lgn), what do you think is the best case for MAX-HEAPIFY and what is the running time for the best case?
Answer:
The best case is that heap property is already in place so the time cost is constant Ө(1)
I dont understand how the theta notation can be used for both values, can someone explain this to me? When I think of the graph used to help me understand theta it might have O(1) as the 'lower bound' and O(log n) as the upper bound and the functions runtime would be somewhere between these values (is this correct?), but why is it o.k to say the worst case run time is THETA(log n) and the best case is THETA(1)? Why would they not use O for the upper and Omega for the lower?
I am still really confused about when I should O or Theta or Omega to describe something. I have read loads of posts and blogs about this and it still doesn't seem to sink in properly for me.


texts: Are all countable partial functions computable?

texts: I know all computable partial functions are countable. Wondering if it is the the other way around as well.


texts: Why can any polynomial and exponential be represented as a recurrence?

texts:
I posted this question on math.SE but I haven't got any reply so I'm posting here also.

I am reading The Algorithm Design Manual by Steven S Skiena.

In Section 4.10.1 Recurrence Relations, I understand what a recurrence relation is, but after that following statements have been given:

  Any polynomial can be represented by a recurrence, such as the linear function:
  $a_n = a_{n-1} + 1, a_1 = 1 \implies a_n = n$

  Any exponential can be represented by a recurrence:
  $a_n = 2a_{n-1}, a_1 = 1 \implies a_n = 2^{n-1}$

Can anyone explain me the above statements by proving them for any linear function and exponential function, respectively?

EDITED : After help from Raphael and Yuval Filmus , I concluded following prove. Correct me if I am wrong

For any Liner function, General form is $a_n = \alpha n + \beta$
$a_n - a_{n-1} = \alpha n + \beta - (\alpha (n-1) + \beta)$
$a_n - a_{n-1} = \alpha n + \beta - \alpha n + \alpha - \beta$
$a_n - a_{n-1} = \alpha \implies a_n = a_{n-1} +\alpha $
As relation holds in question,  $a_n = a_{n-1} + 1 \implies \alpha = 1 $
Now,
$a_{n-1} = a_{n-2} + \alpha , a_{n-2} = a_{n-3} + \alpha , a_{n-3} = a_{n-4} + \alpha , ...$
Therefore, we can expres $a_{n}$ in terms of $a_{n-2}$ and so on
$a_{n} = a_{n-2} + \alpha + \alpha \implies a_{n} = a_{n-2} + 2\alpha $
We can generalize
$a_{n} = \alpha + (n-1)\alpha  \implies a_{n} = n\alpha $
As $\alpha = 1 \implies a_{n} = n$

For Exponential, General form is $a_n = cb^n$
$a_n - a_{n-1} = cb^n - cb^{n-1} \implies a_n - a_{n-1} = cb^n - cb^n . b^{-1}$
$a_n - a_{n-1} = cb^n\left(1 - \dfrac{1}{b}\right) $
Substitute  $a_n = cb^n$
$a_n - a_{n-1} = a_n\left(1 - \dfrac{1}{b}\right) $
$a_{n-1} = \dfrac{a_n}{b} \implies a_{n} = ba_{n-1}  $
As relation holds in question,  $a_n = 2a_{n-1}  \implies b = 2 $
Now, $a_n = cb^n \implies a_1 = cb^1$
Substitute $a_1 = 1$ and $b=2 \implies c = \dfrac{1}{2}$
Substitute c and b in general form i.e. $a_n = cb^n$
$a_n = \dfrac{1}{2}2^n \implies a_n =2^n2^{-1} \implies a_n = 2^{n-1} $


texts: Drawing a planar intersection from stereo camera

texts:
I wanted to recreate the results of this paper, where the authors draw the boundary between two parts of a building from stereo images. The authors mention that the epipole and the intersection of the two planes (two sides of a building) from two cameras can be found from the eigenvectors and the eigenvalues of the homology, and use this to plot some nice images in Figure 4 whereby the building can be divided by the planes.
When I try to reproduce this though, I am unable to recreate the results. My intersection is completely wrong. I tried to recreate by first finding the eigenvectors of the pair of similar eigenvalues, which according to the paper correspond to the intersection line of the planes. Then I take the cross product of the eigenvectors to get the axis, and then draw this line to my image by getting its intersection with the borders using the dot product. My line however seems to bear no relation at all to the real intersection. Is there another step that isn't mentioned here that I am missing?


texts: Table of incompatible turns in an intersection (steps to writing a program)

texts:
I just began reading Data Structures and Algorithms (Aho, Hopcraft, and Ullman). At the beginning, there is an example that discusses designing a traffic light for a complicated intersection of roads.

A visual is given of the intersection along with a table of incompatible turns ("turns" are considered to be any movement from one part of the intersection to another).

Here is the intersection:

Here is the table of incompatible turns:

I'm confused by some of the data shown here. If we just take the first column as an example, the turns listed as "incompatible" make sense i.e. a turn from A to B (AB) cannot be safely performed while a turn is being made from B to C (BC). Likewise, the turn AB clearly cannot be made safely while turn BD is being made.

However, the turns AB and DB are listed as compatible turns. Also, AB and EB are listed as compatible. Why?

I realize collisions can potentially be avoided here if people observe the "right-of-way," but I still don't see how these are considered compatible. They seem like collision courses.

I see how the listed incompatible turns cannot be avoided with the "right-of-way," while the turns I am questioning can potentially be avoided. However, the book mentions nothing about "right-of-way," so I'm simply making an assumption here.

Am I missing something obvious?

Note: I posted my question here because this book is on computer science, and there isn't a stack exchange site for algorithms. This also seems too theoretical to be posted on the engineering site, but I wasn't exactly sure where to post it.

Thank you for your help. I'd rather not read a book on algorithms with uncertainty. This book is recommended by Carnegie Mellon's Department of Software Engineering, so I'm assuming it's a fine source of information.

Update:

Here is another graph of the incompatible turns:


texts: If a sparse language is NP-complete then are all NP languages sparse?

texts: If a Sparse Language is NP-complete then are all NP languages sparse? We say a language is sparse if $\forall n \in \mathbb{N}, |L \cap \{ 0,1 \} ^{n}| \leq p(n)$, for some polynomial $p(n)$?


texts: Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems

texts:
I have a method to solve the $\mathsf{\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an example here.

  How many solutions does $\phi=\left(x_1 \vee x_2 \right) \wedge
 \left(\neg x_1 \vee x_3 \right) \wedge \left(\neg x_2 \vee \neg x_3
 \right)$ have?

First convert to a boolean polynomial:
$$\phi=\left(x_1 + x_2 -x_1x_2\right) \left(1-x_1+x_1x_3\right) \left(1-x_2x_3 \right)$$

Expand and simplify (using, e.g., $x^2=x$ for Boolean values):
$$\phi = x_2 - x_1x_2 + x_1x_3 - x_2x_3$$

Substitute $x_1 = x_2 = x_3 = \frac{1}{2}$ and multiply by $2^n$ where $n$ is the number of variables:
$$|\phi| = 2^n\left(\frac{1}{2} - \frac{1}{4} + \frac{1}{4} - \frac{1}{4}\right) = 2^3\frac{1}{4} = 2$$

where $|\phi|$ is the number of solutions that $\phi$ has.

And indeed, those 2 solutions are $(0,1,0)$ and $(1,0,1)$.

I have proven that this works for any logical expression. Does this have any use/bearing on  $\mathsf{\#P}$ vs $\mathsf{NP}$?


texts: Relation between type-checking decidability, typability decidability and strong normalization

texts:
Yo! This is probably a stupid question, however I've never seen it written down explicitly if, for instance, decidability of type-checking is equivalent to the strong normalization property. Therefore I'm asking this question to clarify all possible relations between type-checking, typability and strong normalization.

Let me explain my motivation. For type theories (I'm being intentionally vague here, but I'm interested mainly in dependent type theories), strong normalization is used to prove the decidability of type-checking. On the other side, any typed systems that I know that have one of these properties also have the other one. However I've never seen explicitly stated that strong normalization is equivalent to decidability of type-checking.

Analogously, to prove typability, one usually (maybe always), reduces a term to a normal form. However it's know that typability is not true for dependent type theories, whereas strong normalization may hold.

By decidability of type-checking, I mean that for any given type $A$, context $\Gamma$ and untyped term $a$, it's possible to decide in a finite number of steps whether $\Gamma \vdash a: A$ is true or not.

By decidability of typability, I mean that for any given untyped term $a$, it's possible to decide in a finite number of steps whether there exist a context $\Gamma$ and a type $A$ such that $\Gamma \vdash a: A$ is true.

1)Is it true that decidability of type-checking is equivalent to every term being strongly normalizable?

2)More generally, what's the relation between decidability of type-checking, typability and strong normalization? Which one implies the other?

Thanks in advance.

EDIT

Given the unsatisfaction regarding the level of generality of my question (which I was unaware of), I would like to delimit it only to Pure Type Systems. Of course, additional comments or counterexamples regarding other type theories will be of great utility.


texts: there exists a O(n) algorithm for subset sum under certain conditions?

texts:
I was wondering if anybody knows if there is an algorithm for Subset-sum, preferably exact, having a $O(n)$ Time Complexity or near-linear ($n$ = number of elements in the input set)

I remember that some time ago I read a paper (from Psinger? I can't find it again..) stating that there is a linear or near-linear time complexity algorithm when the target value is bounded to a constant.

Can somebody explain to how this algorithm can achieve such TC when the target value is bounded to a constant?


texts: Lower bound of disjointness by discrepancy?

texts:
I need to show that $Disc_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \{0,1\}^n \times \{0,1\}^n \to [0,1]$.
Disjointness is defined as

$Disj(X,Y)=\left\{ \begin{array}[ll]+1 & \text{if $X \cap Y = \emptyset$} \\ 0 & \text{otherwise}\end{array}\right.$

The discrepancy for a function is defined as  $Disc_\mu(f) = \max_R \{Disc_\mu(R,f)\}$ over all rectangles $R$ and further

$$Disc_\mu(R,f) = |\Pr_\mu [(x,y) \in R \wedge f(x,y)=1] - \Pr_\mu[(x,y) \in R \wedge f(x,y) =0] |.$$

I don't understand where the $\frac{1}{2n+1}$ comes from and how to define a proper rectangle $R$.

The problem is given as an exercise without a solution in the book Communication Complexity by E. Kushilevitz and N. Nisan on page 40.


texts: If a deterministic finite automaton recognizes a language, must that language contain every accepting input?

texts:
May a DFA recognize a language which is a proper subset of the set of all accepted inputs?

For instance, if there is a DFA which decides if an input $W$ has $w_0 = w_n$, can it recognize a language $L$ where there is some $\sigma \in \Sigma$ that does not exist in any element of $L$?


texts: Efficient way to choose set from including conditions on sets

texts:
Let $m, n \in \mathbb{N}$ and $n \le m$. Given $k$ subsets $X_1, X_2, \dots, X_k$ of $\{ 1, 2, \dots, m \}$ and $k$ nonnegative integers $a_1, a_2, \dots, a_k$, find all subsets $Y$ of $\{ 1, 2, \dots, m \}$ satisfying the following conditions:

The set $Y$ contains exactly $n$ elements: $|Y| = n$
The set $X_i$ has exactly $a_i$ elements with $Y$ in common: $\forall 1 \le i \le k: |X_i \cap Y| = a_i$

EXAMPLE. Let $m = 5$, $n = 2$. We are given the following conditions. Set $Y$ contains...

1 element out of $\{ 2, 3, 4, 5 \}$, $\quad$ ($a_1 = 1$)
2 elements out of $\{ 1, 2, 3, 4 \}$, $\quad$ ($a_2 = 2$)
1 element out of $\{ 1, 3, 4, 5 \}$. $\quad$ ($a_3 = 1$)

$Y = \{ 1, 2 \}$ is a unique solution. It is necessary to have $1 \in Y$, else we must select two elements of $\{ 2, 3, 4 \}$ (2nd set without $1$), which is a subset of the 1st set. Now consider the 3rd set. If we select $3, 4$ or $5$ instead of $2$, $Y$ would contain two elements from 3rd set.

Of course, there may be many solutions, up to $\binom{m}{n}$ to be specific.

QUESTIONS. I have the following two questions:

Are there any algorithms better than trivial brute-force to find all solutions to an instance of this problem? Do these algorithms fulfill known lower bounds?
Given that there exists a unique solution, can we use this extra knowledge to do better than in the general case in terms of time complexity?

MY APPROACHES. Obviously, it is possible to enumerate all $\binom{m}{n}$ subsets and check the conditions. At least for the last step (I know, the first step causes the lack of efficiency) I can think of some improvements. First, we may represent the sets as boolean arrays of size $m$. When iterating over the possible solutions, we may compute $X_i \cap Y$ in time $\mathcal{O}(m)$ resulting in an $\mathcal{O}\left(m\binom{m}{n}\right)$ solution. Additionally, if there is a set $X_i$ with $|X_i| = a_i$ we are lucky. In this case, we know $X_i \subseteq Y$ and may erase all elements of $X_i$ in the other subsets $X_j$ replacing $a_j$ by $a_j - |X_i \cap X_j|$. But in general, this special case does not occur with certainty.

I would appreciate any kind of help and material.


texts: Imperfection in randomness in VLC shuffle playlist - why?

texts:
Whenever I play a playlist of music using VLC (possibly other software too), I notice that some songs never get played while others get played repeatedly (even for a playlist of just 8 songs).

I know from my days as a computer science undergrad student that practical randomness is often good enough so we don't bother with true randomness for many applications. But I'd like to understand this better.

why is real randomness not worth the effort?
does pseudo-randomness not follow a uniform distribution?
are software developers perfectly aware of behavior like I see in VLC and just see a tiny market segment as caring about it?

EDIT: actually, my VLC issue might be because of a broken link! But I'm sure I've seen this behavior with other music players like Apple Music. So apologies to the good folks who develop VLC.


texts: What are logical addresses and where do they actually reside?

texts:
While studying about memory management, paging and segmentation there is a lot of usage of phrases like CPU generates logical addresses and logical addresses are converted to physical addresses etc. I know that the term physical address refers to actual RAM, but I do not have clear idea about what logical address is and where does it reside.

So my questions are:

What is meant by CPU generates logical address?
Where do logical addresses reside (in RAM or somewhere else)?

Can anyone please explain these things.


texts: converting each element in a group/list of number into other base

texts:
I am new to python programming. I am now trying to build a program which convert every element in a list of numbers of base 10 into its base 4. For example here, say i have numbers from 0 to 20 or more, I want to convert every number starting from 0 to numbers of base 4. The result should be like this

[[0,0],[0,1],...[1,1,0]

for numbers starting from 0 to 20. Here is what I wrote so far

for n in range(21):
       def base(n,b):
          result = []
          while n > 0:
                 result.insert(0, n % b)
                 n = n // b
          return result

print(base(n, 4))

For the result I got only for number 20 which is

[1,1,0]

Did I missed something here or there is another option to make it work?


texts:
I  have a question about the equivalence of different automata. I looked up the similiar questions but sadly none of them are exactly, what I need or am looking for.

I know some of these are equivalent ( or not ) but for which language class pairs does a real inclusion apply?

DFA = NFA ⊋ ? DPDA ≠ PDA ⊋ ? LBA = DTM = NTM

I want to know, if this is correct or not.

Hint:" C is the class of all languages accepted by a C-type machine" - If this is important.

I apologize, if my question isn't in a correct format, therefor forgive me, I am trying to settle in.


texts: Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

texts:
I am studying "An Introduction to the Theory of Computation" by Sipser -- there is a problem *3.17 (p.161) which I can not solve.
Any hints (not answers) from which side to attack it?

  Let $B=\{M_1, M_2, ...\}$ be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent machine in C and vice versa.


texts: What is the significance of ⟨B, s⟩ -> ⟨B', s'⟩ as the initial rule in this question about small-step semantics?

texts:
Revising for an exam and I'm trying to get to grips with operational semantics. Here's the exam question that prompted me posting this:

Exam Question:

We add to the language $\mathsf{SIMP}$ two new commands, with abstract syntax defined by the grammar rule:

$$C ::= \mathsf{assert}\ B\ \mathsf{before}\ C \mid \mathsf{abort}$$

The small step semantics of $\mathsf{SIMP}$ is extended with the following rules:

$$\frac{\langle B, s \rangle \to \!\, \langle B', s' \rangle}{\langle \mathsf{assert}\ B\ \mathsf{before}\ C, s \rangle \to \!\, \langle \mathsf{assert}\ B'\ \mathsf{before}\ C, s' \rangle}$$

$$\frac{}{\langle \mathsf{assert}\ \mathsf{True}\ \mathsf{before}\ C, s\rangle \to \!\, \langle C, s \rangle}$$

$$\frac{}{\langle \mathsf{assert}\ \mathsf{False}\ \mathsf{before}\ C, s\rangle \to \!\, \langle \mathsf{abort}, s \rangle}$$

The configuration $\langle \mathsf{abort}, s \rangle$ is stuck (no transitions are available from this configuration). Explain with your own words the behaviour of the new commands.

Given $\mathsf{SIMP}$ Language:

$$
\begin{align*}
C &::= \mathsf{skip} \mid l\ \mathsf{:=}\ E \mid C;\, C \mid \mathsf{if}\ B\ \mathsf{then}\ C\ \mathsf{else}\ C \mid \mathsf{while}\ B\ \mathsf{do}\ C \\
E &::= \mathsf{!}l \mid n \mid E\ op\ E \\
op &::= \mathsf{+} \mid \mathsf{-} \mid \mathsf{*} \mid \mathsf{/} \\
B &::= \mathsf{True} \mid \mathsf{False} \mid E\ bop\ E \mid \neg B \mid B \wedge B \\
bop &::= \mathsf{>} \mid \mathsf{<} \mid \mathsf{=} \\
\end{align*}
$$

My Question:

Firstly let me get my understanding of the question out of the way: We're adding a new command $(C)$ to the list of commands we have defined in our $\mathsf{SIMP}$ language. $C$ asserts $B$ before $C$ or aborts the program/process running. Using small step semantics the question has shown us each step of the process as it runs. Here's my issue:

Assuming my knowledge is correct, every rule written below the line holds if what is written above it holds. If this is the case, what is the importance of the first line

$$\langle B,\ s \rangle \ \to \!\ \ \langle B',\ s' \rangle$$

The rule we have implemented makes no reference of a $B$ in some state $s$ becoming/transitioning into $B'$ in some state $s'$. How can that suddenly be what decides the rule

$$\langle \mathsf{assert}\ B\ \mathsf{before}\ C,\ s \rangle\ \to \!\ \ \langle \mathsf{assert}\ B'\ \mathsf{before}\ C,\ s' \rangle$$

I feel like that rule should be what we start with, not what comes in second. The rule we decided to add to $\mathsf{SIMP}$'s grammar seemed to be more about checking with $B$ before we continue on to $C$, not checking with $B$ so we can go to $B$ (or something to that effect?).

I know that it's not directly related to the exam question at hand but I feel like understanding why might clear up some gaps in my knowledge regarding operational semantics on the whole. That said, here is my answer to the exam question itself:

'The behaviour of the command $C$ ($C ::= \mathsf{assert}\ B\ \mathsf{before}\ C \mid \mathsf{abort}$) is such that when $B$ is asserted it must return either $\mathsf{True}$ or $\mathsf{False}$, as it is a Boolean command. When it returns $\mathsf{False}$ the program/process is aborted, meaning to transitions from this state cannot be made. If it returns $\mathsf{True}$ then you are able to continue on to $C$ in some state $s$.'

Is this correct? If not, where did I go wrong? Like I said, I don't understand the top two rules and as such I feel it hurts my answer not being able to include them in my reasoning.


texts: No need to rename a free variable in substitution?

texts:
I wonder if the following two substitutions are correct:
$$(x\,y)[x:=y] = (y\,y)$$

$$ \lambda y. (x\,y) [x:=y] = \lambda z.(y\,z)$$

They are what I understand from http://en.wikipedia.org/wiki/Lambda_calculus#Substitution.

Although I can follow the rules there mechanically, I wonder why there is no renaming of $y$ to $z$ in the first substitution, while there is in the second?

Is it  correct that in substitution $E[x:=M]$, if both $E$ and $M$ have some free variable with the same name, there is no need to rename the free variable in $E$, just as in the first substitution? Thanks.


texts:
The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots.

It is well known that picking a random pivot does not work as good as taking the median of three, or the ninther of the array.

Obviously, for comparison we need to fix a model of computation / cost per operation.

Assume we are working in a model where each comparison between elements costs $1$, while swapping two elements costs $\gamma$ for some $\gamma>0$.

If we invest more effort in finding a good pivot (e.g., take the median of $k$ random samples), we might make more comparisons, but swap less elements.

  Under this model, what is the optimal (in terms of expected cost) pivot choosing strategy (i.e., if our array is of size $n$, how many elements $k$ should we sample before deciding which pivot to use)?

(We assume that the input might be adversarial, so taking as pivot the median of uniformly sampled elements seems like the right thing to do).


texts: Achieving better than the theoretical False Positive Rate for Bloom Filters

texts:
I implemented a standard Bloom Filter in C++, and tested it on different sizes, with varying values of the ratio ${c = n/m}$ where ${n}$ is the size of the filter, and ${m}$ is the number of elements inserted.

For a Bloom Filter, I created ${k}$ Hash functions, and set the value in the filter for each Hash Index returned. Here's a graph of the results I obtained from my tests:

The problem from the graph is clear, I am getting False Positive rates that are better than the Theoretical value. The theoretical value is based on the assumption that each Hash Index is equally likely, which is:

$
Pr(H(a) = 1)^k = 1 - Pr(H(a) = 0)\\
               = (1 - (1 - 1/n)^{km})^{k}\\
               = (1 - e^{-k/c})^{k}
$

Using $k = c \ln(2)$

$
Pr(H(a) = 1)^{k} = (1 - e^{-\ln(2)})^{k}\\
                 = (1/2)^{c \ln(2)}\\
                 = 0.6185^{c}
$

All my tests are based on the optimal value of $k = c \ln(2)$, and the theoretical line is a plot of $0.6185^{c}$. My concern is that my False Positive rates are consistently better than the theoretical. Does this mean that my implementation is incorrect, or is it a likely possibility given the large sizes of the Bloom Filters and the efficiency of the hashing algorithm?

I appreciate any guidance on this.


texts: Difference between linear bound automata and a Turing machine

texts: Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a Turing machine?


texts:
I have a time series which represent the sine curve. Now I want a regressor to learn this curve, and being able to predict for future values.

PS:
Sine curve is only for testing purposes. What I want is to learn that function and its parameters as well which need not be sine.


texts: How hard is it to find the length of multiplicative 2-partition?

texts:
Some terminology at first:

Multiplicative 2-partition for number $N$ - a pair of numbers $\{A, B\}$ such that $AB=N$.
Minimal multiplicative 2-partition length (denoted $l$) - minimal total number of bits needed to encode multiplicative one of 2-partitions.

Example:

Let $N = 36$. Then possible multiplicative 2-partitions are $\{2, 18\}, \{3, 12\}, \{4, 9\}, \{6, 6\}$. Their lengths are 7=2+5, 6=2+4, 7=3+4, 6=3+3 respectively. Minimal length here is 6, so $l=6$.

The input: non-prime $n$-bit number $N$.

The problem: find out if $n = l$.

YES-instance:

$N$ = 49, since $n$ = 6 and each multiplier takes 3 bits.

NO-instance:

$N$ = 25, since $n$ = 5 and each multiplier takes 3 bits.

The question: what is the complexity for  this problem? It's trivial that it's not harder than factoring and I guess it's $PL$-hard. But is it even known to be in $P$?


texts: Algorithm to find longest path in a tree that is smaller than x

texts:
Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any town to any other town within some time $x$.

There are three paths to consider for each node $v$.

Path to the right subtree of $v$
Path to the left subtree of $v$
Path that goes from the left to the right subtree including $v$

My approach to solving this problem is to use dynamic programming and start at leaf nodes to calculate a travel time $T_l$ for every leaf $l$ and set $T_l = 0$. Then work my way up the tree and compute $T_v = max(T_c + w(v,c))$ for every other node where $c$ are the child nodes of $v$ and check if that value is smaller than the given $x$. This would cover the first two cases and would require us to iterate over every node and edge once which is in $O(V+E)$

Where Im not sure is how to cover the third case, i.e. if I wanted to compute the travel time from one leaf node to another. Is that still possible in linear time and how would I do that?


texts: Why does Pascal have a high code density?

texts:
The plots in http://blog.wolfram.com/2014/06/04/how-the-wolfram-language-measures-up/ seems to indicate that Pascal has a relatively high code density.  What features of the language makes it so?

Follow-up question:

Does this explain why Pascal are often introduced in high schools as one of the first programming languages?


texts: Where does the decimal to binary "Divide by 2" algorithm come from?

texts: I don't know if this board would be an appropriate place for this question, but I have been trying to figure out how the divide-by-2 decimal to binary conversion trick works: in which you divide the number by 2, record its remainder and in the end write out the remainders in reverse to the get the final binary string. I have been using this for a long time but have never really considered why this works. Is there any explanation that could serve as a "proof" or even a basis for how people came up with this in the first place ? Thanks!


texts: sets of axioms for LADR automated theorem provers

texts:
I am pretty new to ATP, but I'm really enjoying playing around with prover9. I have found a nice set of axioms for basic information-theoretic proofs here, I was wondering if there are some collections of axioms for other purposes too, e.g. probability theory.

I found a gigantic set of axioms for TPTP programs here, but prover9 is a LADR program...


texts: Find simple cycles pass through a vertex in drected graph

texts:
I want to find all the simple cycles with bounded length that pass through a vertex in a directed graph. Enumerating all the cycles in large graph takes exponential time. Since I need to find only the cycles that passes through a given vertex and I can save the running time. But I am not getting any proper algorithm to do this sub-problem.

In my problem I can limit the length of cycles as 20 irrespective of the size of the graph. My graph contains 5569 vertices and 29782 directed edges.

I have modified the implementation of tarjan's algorithm presented here.

The modified code is as follows,

import sys
import nltk
from copy import deepcopy

class Cycles:
  def __init__(self,graph):
    self.A=graph
    self.point_stack = list()
    self.marked = dict()
    self.marked_stack = list()
    self.cycles =list()

  def backtrack(self,v,s):
    f = False
    self.point_stack.append(v)
    self.marked[v] = True
    self.marked_stack.append(v)
    if v not in self.A:
      return f
    for w in self.A[v]:
        if w not in self.marked:
          self.marked[w]=False
        if w==s:
            self.cycles.append(deepcopy(self.point_stack))
            f = True
        elif not self.marked[w] and len(self.point_stack)<20: # to bound the cycle length
            f = self.backtrack(w,s) or f
    if f:
        while self.marked_stack[-1] != v:
            u = self.marked_stack.pop()
            self.marked[u] = False
        self.marked_stack.pop()
        self.marked[v] = False
    self.point_stack.pop()
    return f

  def getCycles(self,word):
    for i in self.A:
      self.marked[i] = False
    self.backtrack(word,word)
    return self.cycles

This runs very fastly. But many simple cycles are missing.


texts: Mathematical conjectures equivalent to the halting of a Turing machine

texts:
This question is about whether every mathematical theorem can be reduced to the question of whether a single Turing machine halts. In particular, I'm interested in conjectures that are currently unproven.

For example: Wikipedia says that it's currently unknown whether there are any odd perfect numbers. Since it's decidable whether a given number is perfect, one could write a Turing machine that checks each odd number in turn and halts if it finds one that's perfect. (This Turing machine does not take any input.) If we knew whether that Turing machine halts, then we would know whether the conjecture is true, and vice versa.

However, as another example, what about the twin primes conjecture? It's decidable whether a given number is the first prime in a twin pair, but in this case we can't just halt when we find the first one, because the question is about whether there are an infinite number. It's not clear to me whether it's possible to make a Turing machine that halts if and only if the twin primes conjecture is true.

We can surely make a Turing machine that halts if and only if the twin primes conjecture is provable within Peano arithmetic or some other formal system, but that's a different question, since it might be true but not provable in the particular system we choose.

So my questions are

Is it possible to make a Turing machine that halts if and only if the twin primes conjecture is true? (And if so, how?)
Is it possible, in general, to make a Turing machine that halts if and only if some given mathematical statement is true? Can this Turing machine be constructed algorithmically from the formal statement?
If it's not possible in general, is there some way to classify mathematical statements into whether they're equivalent to the halting of a single Turing machine, or a turing machine with an oracle, etc.? If so, is this classification decidable for a given statement?


texts: Maximum bipartite matching with extra reward for covering certain sets

texts:
Consider the following variation of Bipartite Maximum Matching.  As usual, we have a bipartite graph $G$.  In addition, there is an  additional collection of sets $S_1,S_2,\dots,S_k$, with each set $S_{i}$ being defined as a collection of nodes from the right side of the  graph $G$ as well as a weight.

Suppose that in a matching all nodes which $S_{i}$ describes are matched. Then an extra bonus of weight($S_{i}$) is gained.

Given a certain matching, define as $Y$ the set of all indexes $i$ such that  $S_{i}$ is fully covered by the matching (i.e all its nodes are matched).  Then the profit of this matching is

$$\text{# edges} + \sum_{a \in  Y} \text{weight}(S_{a}),$$

where $\text{# edges}$ is the number of edges in the matching.

The problem is, of course, to find the matching which maximizes the above quantity.

I instantly thought of the following exponential time algorithm.  The algorithm works as follows:

For i in [0,2^k -1]:
    Define X= a subset containing all S_{j} such that  j-bit in i is 1.
    Try to find a maximum matching  only for the nodes which are defined by the elements of X
    If it is a maximum matching(I.e all elements in the right side are matched)
       Add all the other nodes not already present and continue the augmenting path algorihtm
Pick the maximum for all i

As I remember from my algorithm class, in the augmenting path algorithm, once a node in the left side has been  assigned to the matching it  never leaves it. Hence, the algorithm  tries to make sure that in each iteration  certain  sets will be satisfied. Essentially, it is  brute force. Therefore, optimality is proven easily. Unless of course my assumption is wrong.

The running time is $O(2^{k}\text{poly}(V,E))$ which is fine for my needs as $k$ is only 7.

But  I am wondering whether there exists a  polynomial algorithm for this or if the problem is NP-hard. Its clearly in NP but I have not had much success proving NP-completeness.


texts: Given a sorted dictionary of words, find order of precedence of letters

texts:
This question is found at: https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/

Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.

Examples:

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa"
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'

Notice that the solution calls for comparison of adjacent word-pairs only, when discovering new edges. It is unnecessary to add edges from comparing non-adjacent words. This seems straightforward and intuitive to me, but how do we prove it?

An edge-discovery is done by comparing two strings, iterating through their characters, and finding the first pair of characters which differ. The former string's character precedes the latter string's character. In the case of the former string being a substring of the latter, then the edge discovery fails to return a pair. (It's impossible for the latter string to be a substring of the former)

Given a directed acyclic graph built from pairwise edge-discoveries of adjacent pairs <word[1], word[2]>, <word[2], word[3]>, ..., <word[n-1], word[n]>. Prove that comparing any two words which are not adjacent will not yield any new information, i.e. the edge-ordering discovered by the new comparison will already have been present, or implied by transitivity of edge-orderings in the existing graph.

Edit to add: I have a prefix-tree-based proof, but I'm no good at writing proofs and would welcome better-written proofs.


texts:
Here I have a proof related to strongly connected graph from Algorithms book.

However, when I run DFS on the following 2 strongrly connected graph, I get different result than the proof.

According to property, highest post number in C is bigger than the highest post number in D but it is not. Where am I making mistake?


texts: Build Automatic Speech Recognition (ASR) from scratch

texts:
I want to build a Automatic Speech Recognition (ASR) engine for myself, but I've no idea from where to start.

I've read that most ASR's are build upon Hidden Markov Models, but also I've read that HMM is limited somehow and a better approach is to build a ASR upon Machine Learning features.

Overall I am confused.

Can someone recommend me books on topics from which I can start?

Thanks (:


texts: How to write the turing machine processing operations?

texts:
I have this Turing machine example given in my book:

For the language $0^n1^n$. I understand how it works because it's very similar to a Finite State Machine.
But what I want to know is the following:

What is the $|-$ symbol is for what are the states $q_0$, $q_1$ doing in middle of everything. Unfortunately my textbook doesn't explain any of it.


texts: In my opinion it seems fairly obvious that a $k$ nearest neighbours (KNN) Classifier would be fairly expensive in terms of memory, as the model is the training set itself. However, any notes I've read have only mentioned that the KNN-Classifier is computationally expensive, and have not mentioned any memory requirements as a disadvantage. I assume this to be true, but I wouldn't want to mention it in any exams or anything without proper confirmation. Are the memory requirements implicit and not worth mentioning, or am I overlooking something?


texts: Does splitting a process across 4 terminal windows decrease the time it takes?

texts:
Basically, I using an algorithm called 'miranda' to look at miRNA targets and it only runs on a single thread. It compares everything in one file against everything in another file, produces a file as an output and runs off of the command line in terminal. The process took roughly 20 hours to create the output file.

I was advised by my supervisor that if i split one of the files up into say 4 equally sized parts, and ran them in four separate terminal windows this would decrease the overall time it took for the process to be completed.

I found that when I was using a single terminal window, the process would take up about 100-120% of the CPU. However, when running four terminal windows, each individual process only takes between 30-40% of the CPU.

How much effect does splitting the file up like this have in the overall time it takes to run the process? Although I split it across four threads, will the effect only be an increase in speed of about 1.5 times?


texts:
Our teacher gave us the following definition of Big O notation:

O(f(n)): A function g(n) is in O(f(n)) (“big O of f(n)”) if there exist
constants c > 0 and N such that |g(n)| ≤ c |f(n)| for all n > N.
I'm trying to tease apart the various components of this definition. First of all, I'm confused by what it means for g(n) to be in O(f(n)). What does in mean?

Next, I'm confused by the overall second portion of the statement. Why does saying that the absolute value of g(n) less than or equal f(n) for all n > N mean anything about Big O Notation?

My general intuition for what Big O Notation means is that it is a way to describe the runtime of an algorithm. For example, if bubble sort runs in O(n^2) in the worst case, this means that it takes the time of n^2 operations (in this case comparisons) to complete the algorithm. I don't see how this intuition follows from the above definition.


texts: How to solve recurrence $T(n) \le 2T(n/3) + c\log_3 n$ using substitution method

texts:
Show by induction that any solution to a recurrence of the form
  $ T(n) \le 2T(n/3) + c\log_3 n $ is $O(n\log_3 n)$.

Hoping someone can help me with the correct solution.  I attempted two ways to get the solution (but I think that they're both incorrect):

SOLUTION A

\begin{align}
T(n) &\le 2T(n/3) + c \log_3 n \\
&\leq 2[k(n/3)\log_3(n/3)] + c\log_3 n \\
&= (2/3)kn(\log_3 n-1) + c\log_3 n \\
&= (2/3)(kn)\log_3 n \\
&= (2/3)kn + c\log_3n \\
&= [(2/3)kn + c]\log_3n - (2/3)kn
\end{align}

SOLUTION B

\begin{align}
T(n) &\le 2T(n/3) + c \log_3n \\
&\le 2 [ k(n/3)\log_3(n/3) ] + c \log_3n \\
&= (kn - kn/3)(\log_3n - 1) + c \log_3n \\
&= (kn)\log_3n - (kn/3)\log_3n - kn + c\log_3n \\
&= (kn)\log_3n - (2/3)kn + (c - kn/3)\log_3n
\end{align}


texts: Substitution method for $T(n) = 2T(7n/10) + O (1)$

texts:
I want to solve $T(n) = 2T(7n/10) + O (1)$ using the substitution method.

I think the solution should be $T(n) = O(n\log n)$, but I am having trouble constructing a proof by substitution.


texts: How does the hardware of a while loop work?

texts: I know get how logical operators for if logic gates work, but I am trying to understand how while loops fit into that picture. I realize that this question is a bit vague. It all started because I was wondering if one could write a while-loop with a series of if statements. Then I realized there had to be something deeper in our programming languages.


texts: Denial of Service(DoS) and withdraw.pendingReturns[msg.sender]=0;

texts:
I am trying to understand the role of
withdraw.pendingReturns[msg.sender]=0;

in detecting DoS vulnerability. The following paper:VeriSolid says that:

withdraw.pendingReturns[msg.sender]=0; will eventually happen after
withdraw.msg.sender.transfer(amount);

how this can help us to detect DoS vulnerability because after ‘transfer’ we can’t execute anything so how this technique can help in determining DoS vulnerability.
However, in the following code :
withdrawals[msg.sender].amount = 0; is done before transfer which is different as in the paper:
function withdraw() public {
   if(withdrawals[msg.sender].amount > 0
      uint amount = withdrawals[msg.sender].amount;
      withdrawals[msg.sender].amount = 0;
      msg.sender.transfer(amount);
   }
}

Can we use this strategy for determining DoS vulnerability?
Zulfi.


texts:
I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets.

$\qquad\begin{align}
 S &\to [S] \\
 S &\to (S) \\
 S &\to SS \\
 S &\to \varepsilon
\end{align}$

Not sure if this is correct, or how to make the PDA from it?


texts: Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?

texts:
Tomorrow is my presentation and I want to clear my concepts…

I've read that in DFA, "For each state, transition on all possible symbols (alphabet) should be defined."

Is for each state, defining transition on all possible symbols mandatory in DFA? If its not, then please give any examples?


texts: What is the difference between rateless and online encoding?

texts:
Definitions of Rateless encoding and Online encoding are as follows.

Error-correcting codes that employ no fixed block length are called rateless or fountain codes.

Online encoding refers to the property that a symbol is encoded at once and without knowledge of previous encodings.

Do both properties indicate the same thing? Are Fountain codes both rateless and online?


texts: Is there an approximation algorithm for Minimum Test Collection Problem?

texts:
The problem is defined as follows:

Instance: A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J≤|C|$.

Question: Is there a subcollection $C′⊆ C$ with $|C′|≤ J$ such that, for every pair $a_{i},a_{j}$ of possible diagnoses from $A$, there is some test $c∈C′$ for which $|{a_{i},a_{j}}|∩ c|=1$ (that is, a test $c$ that "distinguishes" between $a_{i}$ and $a_{j}$)?

And we know that MTC is $NP$-complete, it has been proved by reducing it to 3 Dimensional Matching problem in the Garey & Johnson's book.

Thanks.


texts:
So I recently had a problem where I had to create a regular language. After consulting my professor on my solution he told me it was close to correct but to check my definition of a regular language. I am somewhat lost on why my solution is not regular?

From my understanding it meets the requirements of being a right regular language since there is only one non-terminal on the right side of the expression and the non-terminal is the rightmost symbol on the right side of the expression. Are pipe symbols not allowed?


texts: Are there any implementations of computability logic?

texts:
I'm currently looking into Japridze's computability logic. It looks great, but I was wondering whether any programming languages or systems implement it.

Does anyone know of any implementation?

Thanks.


texts: AVL tree as dictionary, find highest value in interval

texts: I have the AVL tree used as a dictionary: each vertex resides a key and some integer value. How can I edit the tree so that it can quickly find the largest value assigned to a key from the interval [a; b]?


texts: Performance gain by implementing streamlined simplex

texts:
I have to solve linear transportation problems for a research project. Ideally, I should design an application that will recieve the problem data as an input and then show some results. The size of the problems are in the order of N=10.000 sources and N=10.000 destinations, and 2N=20.000 restrictions of equality, one for each source and one for each destination.

I've been using Python's PuLP with the standard solver(COIN-OR) and with GLPK. As a general rule, the performance of COIN-OR is superior than that of GLPK, but even with COIN-OR the problems are taking too long to be solved. As far I as know, there's a streamlined version of the simplex algorithm for transportation problems, but I ignore the magnitude of the improvement in performance I should expect by using that streamlined version of simplex algorithm.

So, my first question is if those solvers identify the transportation problem structure of the problems I'm dealing with and act accordingly.

If the answer turns out to be no, then my second question is if I can exploit that particular structure of the transportation problems with a free solver that has a Python interface.

Also, will I note some improvement if I implement myself the streamlined version of the simplex algorithm? Or implementations must be too far from naive to really beat a well-established simplex solver like the ones I mentioned before?


texts: first order logic resolution unification

texts:
Assuming I have shown part of the knowledge base in the clausal format:

[1] p1(banana).

[2] not p1(X) or p2(Y).
[3] p1(X) or not p3(F).

... and more rules.

Most of the books, would do something like this:

[1,2] {X=banana} p2(Y).

and more steps.

First question: is it equally correct to do something like follows:

[2,3] {X=X} p2(Y) or not p3(F).

and then continue with resolution.

Second question: What if different variables were used in each clause, could I do the same as above, for example we had:

[2] not p1(X1) or p2(Y1).
[3] p1(X2) or not p3(F2).

[2,3] {X1=X2} p2(Y) or not p3(F2).

Thank you in advance


texts:
I'm curious about the way text recognition works in machine learning(or more generally, the question of object vs not object) in computer vision.

How are systems trained when the not-object data set is so much greater in quantity and apparently lacks structure?

One approach is having the algorithm first searches for a text box and once it finds one applies character recognition. Thus the initial classification comes down to "text" or "not text". "Not text" doesn't have any particular structure though and in fact almost everything is "not text"...so how is this dealt with?

What would the "not text" training set be? Random images? Clearly you need negative examples.


texts: Linearithmic lower bound for 1-D "distinct" closest pair of points problem

texts:
The 1-D distinct closest pair of points problem is as follows: Given a set of n distinct integer points on real line, find a pair of points with the smallest distance between them, here the distance between two points p_i and p_j is absolute difference of their values, i.e, |p_i-p_j|.

A naive way to solve this problem is to sort the points and check distance of each consecutive points in sorted order and take the minimum of such distances and this takes O(nlog n) time.

My question is can we do better than that? Can we solve it in o(n log n)(note the little-oh) time? If not, then how to show an omega(nlog n) time bound for this problem?

Note that, if the distinctness criteria was not there we could have shown a lower bound using Element Distinctness Problem.


texts: Break and Continue in Structured Programming?

texts:
One of the ways to ensure following the structured programming paradigm is by having all control flows having only one entry and one exit point. Does skipping iterations by using break and continue in languages like Java count as a second exit point (like a GOTO-statement) or not?

I am aware that Java has no (working) goto statement but a break and continue. The question was whether using them violates the structured programming paradigm or not, i.e. is it bad code style or not (in all languages having break and continue, not just Java).


texts: What is the difference between a Bus clock and a System Clock? Do they function the same way? I have been reading about System clocks but I can't really find anything about bus clocks in my book to compare the two.


texts: model directed graph as undirected graph

texts:
I have a directed graph, and some algorithms in networkx I want to apply to it. Unfortunately when I try to use the algorithms, python tells me that they're only implemented for undirected graphs so far, not directed graphs yet. I don't really want to reimplement these algorithms myself, is there a way to model my directed graph as an undirected graph?

Ultimately, my goal is to identify nodes in the graph that can be removed with minimum disruption. I could just perform reference counting, but this would fail because of cycles. My cycle detection algorithm is one that wasn't yet implemented for digraphs. Likewise for the community detection algorithms. My graph is relatively sparse: it has 1600 nodes but most node has less than 10 outgoing edges, and no node has more than 100.


texts:
Random walks are well known from probability theory.  I have the idea for hash walks.  If h(x) is a hash function and a,b,c,d,e,f is a boolean sequence then the sort of hash walk I am talking about is h(x+a), h(h(x+a)+b), h(h(h(x+a)+b)+c),....

At each step in the hash walk there are only two possible next states.  If the input data is sparse then you will frequently have walks that are the same.  I use the idea to construct prediction trees.  At the moment I am working on the idea of using Bloom filters to greatly reduce the amount of memory needed to store hash walks.

In information theory terms could you get even better generalization using less than 1 bit of input per walk step?
Is there any prior literature on this topic?


texts: Algorithm for constructing BST from post-order traversal

texts:
Given a post-order traversal of Binary Search tree with $k$ nodes, find an algorithm that constructs the BST.

My Algortihm

  Let $n$ represent the next element to be inserted.

  Let $P(y)$ represent the parent of node $y$.

  We will read the traversal in reverse. The last element of the traversal is the root. Let $l = root$. $l$ will represent the element
  last inserted in the BST (except for the 3rd case below- where it will
  change to the parent).

  Loop the following till there's no element left to be inserted

  if $l<n$ then $n$ is the right child of $l$. For the next insertion,
  $l$ changes to it's right child and $n$ becomes the next element(in
  reverse order of traversal ).
  else, if $l>n$ and $P(l)<n$ then $n$ is the left child of $l$. For the next
  insertion, $l$ changes to it's left child and $n$ becomes the next
  element(in reverse order of traversal).
  else, if $l>n$ and $P(l)>n$ then  $l$ becomes $P(l)$.($n$ hasn't been inserted - we loop with $l$ changed)

  [Let $P(root)=- \infty$, so that the $2^{nd}$ case applies]

Complexity Analysis : Every element  may contribute at max 3 comparisons, 1 each for - left child, right child and for finally leaving i.e. subtree has been constructed. Even if I missed a comparison or two, It should be constant no. of comparisons per element and no. of operations for node construction will also be constant per element. Hence, giving $O(k)$ time complexity.

Actual Question

If the algorithm is correct, I need the correctness proof for it. Yes, I thought I had the proof but then brain got fried and I am stuck and unable to reason succinctly.
If the algorithm is incorrect, then why? And what is time complexity of the most efficient algorithm for the same question?

Also, is the $O(k)$ complexity correctly calculated - irrespective of the correctness of the algorithm?


texts:
I am programmer with a grip on automata, but not on logic.

I read in papers that the two are very tightly related.
Deterministic Finite Automata (DFA), Tree Automata and Visibly Pushdown Automata are all related to Monadic Second Order Logic (MSO).
Although, I understand the automata and people (in papers) have tried to explain the relation to MSO to me, they always assume a strong background in logic and an understanding of MSO.

When I look at books and courses on logic, they mostly only handle first order logic, which seems pretty simple and consisting of only a few concepts: variables, or, and, not, implies, for all, exists, etc.

Can someone explain or point me to a resource that can explain:

What is second order logic in contrast to first order logic?
What is monadic vs non monadic logic?
Why is it important for a second order logic to be monadic to be decidable OR why is this the wrong question?
Why is monadic second order logic decidable?
The relation to at least DFAs?

If it is a resource it would be nice if it assumes that I am a programmer and not a logician.
This means that I would like to understand how I would implement it as code, because until then math feels like magic to me ;)

Thank you for any help you can give me.  I would really appreciate it.


texts: Tried to derive the Z combinator and instead derived another

texts:
I was working to derive the Z-Combinator by starting with the factorial function and ended up deriving a different fixed-point combinator. What did I derive? Did I make a subtle mistake?
Here are the steps I performed (in JavaScript)
1. Declare factorial function
let fact = n =>
    n < 2 ? 1 : n * fact(n - 1)

2. Convert to combinator (closed expression)
let fact = (self, n) =>
    n < 2 ? 1 : n * self(n - 1)

3. Thread self call
Based on signature fact(?, 7), passing fact as first argument seems reasonable fact(fact,7). So thread the parameter through the tail call:
let fact = (self, n) =>
    n < 2 ? 1 : n * self(self, n - 1)

Usage is now fact(fact,7) → 5040
4. Refactor to curried form
let fact = self =>
    n => n < 2 ? 1 : n * self(self)(n - 1)

5. Move self application to local declaration
let fact = self => {
    let f = n => self(self)(n)
    return n => n < 2 ? 1 : n * f(n - 1)
}

6. Convert let declaration to lambda expression
let fact = self =>
    (f =>
        n => n < 2 ? 1 : n * f(n - 1)
    )(
        n => self(self)(n)
    )

Usage is still fact(fact)(7) → 5040
7. Separate the factorial expression
let _fact = f => n =>
    n < 2 ? 1 : n * f(n - 1)

let fact = self =>
    (
        _fact
    )(
        n => self(self)(n)
    )

8. Move self-application from caller to body
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    let innerFact = self =>
        (
            _fact
        )(
            n => self(self)(n)
        )
    return innerFact(innerFact)
})()

Usage is now fact(7) → 5040
9. Convert let declaration to lambda expression
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    return (
        innerFact => innerFact(innerFact)
    )(
        self => (_fact)(n => self(self)(n))
    )
})()

10. Simplify expression
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (innerFact => innerFact(innerFact))
    (self => (_fact)(n => self(self)(n)))

Sanity check. Usage is still fact(7) → 5040
11. Rename variables
The usage of innerFact and self look suspiciously similar. Rename to the same variable to discover a pattern. Separate lexical scopes so safe to do:
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (u => u(u))
    (u => (_fact)(n => u(u)(n)))

12. Abstract _fact usage and rename fact
Rename fact to setup and abstract _fact in body by replacing with parameter f
let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

let fact = setup(_fact)

No need for separate _fact declaration so inline:
let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

let fact = setup(
    f => n => n < 2 ? 1 : n * f(n - 1)
)

13. Rename setup
Rename it to what? What combinator is this? According to Wikipedia The Z combinator is:
let Z = f =>
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

But what I've derived is:
let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

Defining fact in terms of either seems equivalent in behavior. Did I make a mistake? Did I accidentally rediscover another well-known combinator?


texts: Proof that PDA's with different definitions have same expressive power

texts:
Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$,
where

$Q$ is the set of states,
$\Sigma$ is the input alphabet
$\Gamma$ is the stack alphabet
$\delta$ is the transition function with signature $Q\times(\Sigma\cup\{\epsilon\})\times(\Gamma\cup\{\epsilon\})\to\mathcal{P}(Q\times(\Gamma\cup\{\epsilon\}))$
$q_s$ is the initial state
$F$ is the set of acceptable states.

We suppose that at every transition at 1 symbol of the input string is read, 1 symbol of the stack is popped, 1 symbol is pushed and we can change our state. A general (informal) definition of the acceptance of a string is: we accept the string when we end in an acceptable state with an empty string (whatever the stack contains).

However, there are other possible definitions of the acceptance of a string by $P$. Some possibilities:

The string is accepted when both the string and stack are empty (even when the current state would not be an acceptable state).
The string is accepted when both the string and stack are empty and we are in an acceptable state.

One could also change the definition of the PDA as follows:

One can push more than 1 symbol to the stack in 1 transition.

My question is, how can 1 (both formally and informally) proof that the power of the PDA does not change by using another definition? Alternatively, one could say that the languages determined by the different PDA's are the same.


texts:
What is a bicriteria approximation algorithm? This keeps coming up in the case of data stream clustering. Is this related to multi-objective optimization?

This is where I came across it: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. The paper is about a streaming version of the k-means algorithm. There are references in the paper but none of them give an explanation as to what a bicriteria approximation algorithm is. I cannot seem to find anything on Google that will give me a precise definition either.


texts: Why are basic feasible solutions the same as vertices geometrically?

texts:
The first line on the Wikipedia page for basic feasible solutions reads, In the theory of linear programming, a basic feasible solution (BFS) is, intuitively, a solution with a minimal number of non-zero variables.

I do not understand this, I could always have the origin within a convex polyhedron, but it is not necessary that the origin is a vertex of my polyhedron, is it? What am I getting wrong here?


texts: Cost in time of constructing and running an NFA vs DFA for a given regex

texts:
Repost from Stack Overflow:

I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated.

The question I'm having problems with at the moment is as follows:

  Given a regular expression (a|bb)*, derive an estimate of the cost in time for
  converting it to a corresponding NFA and a DFA. Your answer should refer to
  the size of the regular expression.

A similar question from another year is:

  Given that, for the above example, you know the size of the original regular
  expression, |r| and the size of the input string |x|, explain how you would calculate the cost in time for constructing and running the NFA versus constructing
  and running an equivalent DFA.

The resulting NFA for (a|bb)* has 9 states, while the DFA has 4. Even knowing this, I have no idea how to approach the question.


texts: Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

texts:
I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural (for-loop/array-based) counterparts. But, after thinking about it, I don't see how that could be true. Mind this for loop

int arbitrary_sum(int* arr, int size, int n){
    int sum = 0;
    for (int i=0; i<n; ++i)
         sum += arr[(int)(random()*size)];
    return sum;
}

That sums N random elements of an array. You'd saiy this is O(N), but that is taking in account array indexing is O(1), which can't be true. For simplicity, assume memory cells are stored linearly. Since that chip must occupy a linear amount of space, and since a signal requires a linear amount of time to travel given space, then it is obvious an indexing operation takes at least O(S) time to complete. That is the time a signal takes to go from the CPU to the memory cell and come back. This means that the complexity of a for-loop is O(N*S), where N is the number of interactions and S is the size of the state that is visible on that for-loop. This way, the textbook int sum(int* array, int size) function, for example, can't be O(N) - it is, actually, O(N^2), for any reasonable implementation of for, as far as physical laws apply. Using layers of caches we are able to shrink the initial S factor and amend this effects, but that has a runtime cost and doesn't change the asymptotics. Now, lets look at the functional counterpart. The most obvious way to sum a container of numbers functionally is folding over a list. For simplicity, lets examine the sum of 0 to 4 using church lists:

((λc.(λn.(c 0 (c 1 (c 2 (c 3 (c 4 n))))))) + 0)

We can optimally evaluate a λ program is using an interaction net, so, lets encode that program as one:

Now, let me propose a new model of computer. Instead of separating the CPU and the memory, we instead store a simplistic computing unit together with each memory cell, each one capable of sending/receiving signals and processing local reductions. On this system, we can reduce the ((λ ...list...) +) abstraction by sending parallel signals from the topmost λ node to each corresponding application. We can also reduce the outermost abstraction by sending 0 to the last application of the list. All that takes no more than 2 runs through the list, and the result is:

From here on, it is clear that the rest of the computation will take a linear amount of time to complete. After all, each redex is local, and the redexes are reduced one by one, producing the result from the tail of the list up to its head.

Under this point of view, it seems to me that functional programs are actually asymptotically faster than imperative counterparts, so, why is the opposite considered the truth?


texts: How do you calculate when effective access time is greater than cache access time?

texts:
I'm having trouble understanding how to calculate effective access time, hit ratios and cache access times. I'm unfamiliar with the concepts and would love help, or an explanation on how to solve this problem:

  Consider a memory system with a main memory of 16 MB and a cache memory of 8,192 bytes. The cache cost is 0.02 cents/bit while the memory cost is 0.001 cents /bit.  The cache access time is 50 nanoseconds whereas the memory access time is 400 nanoseconds.  If the cache hit ratio is 90% what percent is the effective access time greater than the cache access time?  What is the average cost per byte of memory for the system?

Any help is truly appreciated.


texts:
I know that $\emptyset$ is a an empty language, i.e. language containing no string.

A law involving empty language is:

  $\emptyset L = L\emptyset = \emptyset$

It correctly states that we cannot concatenate non empty language $L$ with a language $\emptyset$ containing no string  (as their is no string to concatenate in $\emptyset$), it yields empty language.

Then how concatenating a language containing no string with itself any number of times can yield even empty string? That is, how following law exist:

  $\emptyset^* = \{\epsilon\}$


texts:
In Computer Architecture course, I have learnt how computer performs numerical computations.
While using MATLAB, I was introduced to symbolic mathematics toolbox.
I was amazed to see it manipulating trigonometric expressions, indefinite integration etc.
What sorts type of algorithms are used for doing symbolic mathematics.
Is there any text or article available of how symbolic mathematics is performed in computer algebra systems.


texts: Understanding google's user level threads in kernel threads

texts:
I came across Paul Turner work on increasing efficiency of M:N threading model. I am not able to grasp the concept at slide 18 of LPC-User-Threading

It says : for two threads A and B :

Minimal scheduling operation.
● B inherits A’s virtual runtime.
● B was not runnable, so we don’t need to remove it from runqueues.
● B holds references on same objects as A

What does virtual runtime mean in this case ?

Will not a random thread B inheriting A's environment and referencing same objects cause any problems ?

The video is present at video for the interested.


texts:
I am reading a free  algorithms textbook   http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf
and on  page 13 i am stuck on an example they give.

"At this time, the fastest computer in the world is the NEC Earth Simulator, which clocks 40 trillion steps per second. Even on this machine, fib1(200) would take at least 2^92 seconds"

im stuck on how the got 2^92

here is the relevant information:

pseudo code:

given that:

T(n) ≤ 2 for n ≤ 1.

T(n) = T(n − 1) + T(n − 2) + 3 for n > 1

So i think we start by plugging n = 200

T(200) = T(199) + T(198) + 3

and then i do not know where to go from here

Any help on this is much appreciated


texts:
I was wondering if you could double check on the following statements being true, false or non-conclusive (as in in some cases true, but false in others). Here they are:

1) $F(n) = \log (n^n)$ implies $F(n) = \Theta(\log n)$.

Answer: It is a tough one? It is confusing because of $n^n$. My assumption would be to have it as non-conclusive. It is because for some cases, where $n$ is even a bit large, $\log$ will greatly decrease $F(n)$'s value. For abysmally large numbers, it will be significant, i.e. $n = 10000000$. Maybe I am wrong?

2) $F(n) = n \log n + n^2$ implies $F(n) = \Omega(n \log n)$.

Answer: True. We drop $n \log n$ (since it is not significant) and indeed $n^2$ will grow asymptotically faster (it is slower) than $n \log n$.

3) $F(n) = n!$ implies that $F(n) = O(2^n)$.

Answer: False. $n!$ grows faster than $2^n$. Therefore it would be $\Omega(2^n)$ not $O(2^n)$.


texts:
I found this question here but I don't think the answer is correct.
Here is the original word break question:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

One way to do it is to use backtracking:
vector<string> wordBreak(string s, vector<string>& wordDict) {
    vector<string> sentences;
    string prefix = "";
    findWords(prefix, 0, s, wordDict, sentences);
    return sentences;
}

void findWords(string prefix, int start, const string s, const vector<string> &wordDict, vector<string> &sentences) {
    if (start == s.size()) {
        sentences.push_back(prefix);
        return;
    }
    for (int i = start; i < s.size(); i++) {
        string word = s.substr(start, i - start + 1);
        if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
            string new_prefix = prefix == "" ? word : prefix + " " + word;
            findWords(new_prefix, i + 1, s, wordDict, sentences);
        }
    }
}

In the worst case, the dictionary contains all prefix of s. From my understanding, in this case, the time complexity is
T(n) = T(n-1) + T(n-2) + ... + T(1) = 2T(n-1) = O(2^n)

I'm not sure if this is correct because I see some threads say it is O(n^n)?
The other way is to use backtracking with memorization:
vector<string> wordBreak(string s, vector<string>& wordDict) {
    return constructSentences(0, s, wordDict);
}

// Return all sentences that can be constructed using substring s[start, ...]
vector<string> constructSentences(int start, const string s, const vector<string> &wordDict) {
    if (dict.count(start)) {
        return dict[start];
    }
    vector<string> sentences;
    if (start == s.size()) {
        sentences.push_back("");
        return sentences;
    }
    for (int i = start; i < s.size(); i++) {
        string word = s.substr(start, i - start + 1);
        if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
            vector<string> subsentences = constructSentences(i + 1, s, wordDict);
            dict[i + 1] = subsentences;
            for (const auto elem : subsentences) {
                sentences.push_back(elem == "" ? word : word + " " + elem);
            }
        }
    }
    return sentences;
}

I'm not sure how to analyze the time complexity of this approach since some subproblem can be solved in constant time by dictionary lookup but some cannot.
Furthermore, I'm not sure how to analyze the space complexity of these two approaches. From my understanding, the space is bounded by the final output. Since we have O(2^n) final sentence and each sentence have size O(n), does it mean the space complexity for both approach is O(2^n * n) ?


texts: Can you increase data rate by increasing number of bits?

texts:
My question is on data rate and baud rate.

data rate = baud rate * n

The question is, can you keep on increasing the data rate by increasing baud rate or number of bits.

I believe it can be increased by increasing the baud rate but what about the latter part?