texts: Reductions where the number of certificates from one problem can be computed for another to varying degrees

texts:
Let $A$ and $B$ be two decision problems in $NP$. Consider three cases:

(1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same number of solutions as $A$.

(2) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having a fixed number of solutions for every solution of problem $A$. We can, in polynomial time, calculate the number of solutions for $A$ provided an oracle that gives the number of solutions to $B$, and vice versa. What if we can guarantee that the number of solutions for an instance of $A$ will be greater than the number of solutions for the corresponding instance of $B$ or vice versa?

(3) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having a solution if and only if $A$ has a solution. However, we do not have a polynomial time algorithm to compute the number of solutions for $A$ provided some number of solutions for $B$.  We also cannot guarantee that such a polynomial time algorithm does not exist.

What formal names and notation for the above sort of reductions? When is a Levin reduction called parsimonious? Instances one and two only? Is the third example necessarily worth anything?


texts: Generalizing the Comparison Sorting Lower Bound Proof

texts:
Let's start with the comparison sorting lower bound proof, which I'll summarize as follows:

For $n$ distinct numbers, there are $n!$ possible orderings.
There is only one correct sorted sequence of the $n$ numbers.
We are given that comparison ($<$) is the only operation we have that can narrow down the $n!$ possible orderings, and each comparison has only two possible outcomes.
So $\log_2(n!)$ comparisons are required.

Now consider the following generalization of the argument above:

Define a space of possibilities and its size (in the case of sorting, $n!$ orderings)
Define the goal state and its size (in this case, only one correctly sorted answer)
Define the amount of information that is gained at each step of the computation (in this case, one bit since there are only two possible outcomes per comparison)
Calculate the information difference between the space of possibilities (step 1) and the goal space (step 2) and divide by the information gain per step (step 3) to yield the lower bound on the number of steps (in this case, $(\log_2(n!)$ - $\log_2(1))$ / 1 = $\log_2(n!)$).

Please answer all the following questions. I'm less concerned with the correctness of the particulars of step 4 than I am with the correctness of steps 1 - 3.

Are there any problems with the generalized argument?
If the problems can be fixed, what are the fixes?
If the problems can't be fixed, please point out the fatal ones and provide directions to sources which describe these lower-bounds proofs and their pitfalls.


texts: Which data structure to use to solve equations?

texts:
Let's say I have two equations for a geometric object (a rectangle):

$\left\{
    \begin{array}{l}
      x \ge 0 \\
      y \ge 0 \\
      A \ge 0 \\
      P \ge 0 \\
      A = x*y \\
 P = 2*x + 2*y
    \end{array}
\right.$

Now I would like to set the values of some variables, and compute the values of the other ones.

At first, I thought it could be done with simple tree transformations on the AST, but I realized that I was more or less building a full solver.

The easy case is when one side of the equality consists only of constant terms, as it consists of a simple recursive tree evaluation. But the interesting case is when there are several variable bound together in a subtree. For example, for $ (A,P)=(30,11)$ the solution is $(x,y)=(5,6)$ or $(6,5)$

Can arbitrary complex instances of this problem solved just with tree transformations ? Or do I need something more elaborate ?


texts: Finding asymptotically tight bounds $\Theta$ of two procedures

texts:
I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this:

public static int c(int n) {
    int i, j, s = 0;
    if (n > 1) {
        for(i = 0; i < n; i*=2) {
            for(j = n; j > 0; j/=2) {
                s++;
            }
            s+=c(n-2);
        }
    }
}

Now I have set the following recurrence equation:
$T(n)=\log_2n*T(n-2)+\Theta(\log_2n)$

Now the height of the recurrence tree is $n/2$ so the $T(n) = n/2 * (\log_2n+\log_2n)=\Theta(n*\log_2n)$

The next procedure is this:

public static int d(int n, int m) {
    int i, j, k, ss = 0;
    if (n > 1) {
        for(i = 0; i < n; i++) {
            for(j = i; j > n; j+=2) {
                ss+=(i+1)-2*j+m;
            }
        }
        for(k=0; k<8; k++) {
            ss+=d(n/2, m/(k+1))
        }
    }
    return ss;
}

Again I have set this equation:
$T(n, m)=8*T(n/2, m/(k+1))+\Theta(n^2)$

Now I think the $m$ parameter is not important because it is not used in for loop as a counter. Where $n/2$ gives us a recurrence tree of height $\log_2n$. So we get this:
$T(n, m) = 8 * \log_2n*n^2=\Theta(n^2)$

I know that recurrence equations that I have set up are probably right, while the I am not sure about next steps.


texts: Conditional probability in Expectation Maximization (EM)

texts:
I've got the following equation:
$p(j = 1 | x, \theta) = \frac{p(j=1,x | \theta)}{p(x | \theta)}$
Why does it hold? Or maybe, how do I use Bayes Theorem in this case, i.e. if we do not only have $p(j = 1 | x)$ but $p(j = 1 | x, \theta)$?


texts: Determining the existence of a forced win vs determining the best outcome

texts:
A large body of work looks at the computational complexity of games. In particular, identifying a forced win from a given position.

Is this problem equivalent under polynomial-time reduction to identifying the best forced outcome of a game, where that outcome might not be a win?

If necessary, assume that it’s a two player zero-sum game that pays out 1 for a win, 0 for a draw, and -1 for a loss.


texts: Solving recurrences by substitution method: why can I introduce new constants?

texts:
I am solving an exercise from the book of Cormen et al. (Introduction To Algorithms). The task is:

  Show that solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O(\lg n)$

So, by big-O definition I need to prove that, for some $c$,

$$T(n) \le c\lg n\,.$$

My take on it was:
$$\begin{align*}
    T(n) &\leq c\lg(\lceil n/2\rceil) + 1 \\
         &< c\lg(n/2 + 1) + 1 \\
         &= c\lg(n+2) - c + 1\,.
\end{align*}$$
As this doesn't seem satisfactory I looked up a solution and the author after getting to the same stage as me decided to introduce a new arbitrary constant $d$:
$$\begin{align*}
    T(n) &\le c\lg(\lceil n/2-d\rceil) + 1 \\
         &< c\lg(n/2+1-d) + 1 \\
         &< c\lg((n-2d+2)/2) + 1 \\
         &= c\lg(n-2d+2) - c + 1 \\
         &= c\lg(n-d-(d-2)) - c + 1\,.
\end{align*}$$

And now, for $d \ge 2$, $c \ge 1$ and $n > d$,

$$c\lg(n-d-(d-2)) - c + 1 \le c\lg(n-d)\,.$$

What I don't understand is how does it prove that $T(n) \le c\lg n$? Cormen et al. make a big point that you have to prove the exact form of the inductive hypothesis which in this case was $T(n) \le c\lg n$. They then go on to show example similar to one above.

How is that the exact form of the inductive hypothesis? This doesn't seem to fit the big-O definition. When can I omit constants or cheat them away? When is it wrong?


texts: Minimize the total execution time of jobs executed by 3 processors in sequence

texts:
There are 3 processors: $P_1$, $P_2$, $P_3$. $P_1$ can execute only one job while the other two can execute any number of jobs in parallel.

Each job consists of 3 parts, and each part is processed by their respective processor (eg. part 1 by $P_1$). Furthermore part 2 can be executed only after $P_1$ finishes executing part 1, and part 3 can be executed only after $P_2$ finishes executing part 2.

Suppose there are $n$ jobs, and again each job has 3 parts. The processor $P_k$ takes time $T_{i\,k}$ to complete part $k$ of job $i$.
Can anyone suggest an algorithm that takes set of $n$ jobs and determines the the jobs should be processed  so that the total time is minimized?

This is a homework problem and I don't know where ti start


texts: k-center algorithm in one-dimensional space

texts:
I'm aware of the general k-center approximation algorithm, but my professor (this is a question from a CS class) says that in a one-dimensional space, the problem can be solved (optimal solution found, not an approximation) in O(n^2) polynomial time without depending on k or using dynamic programming.

A general description of the k-center problem: Given a set of nodes in an n-dimensional space, cluster them into k clusters such that the "radius" of each cluster (distance from furthest node to its center node) is minimized. A more formal and detailed description can be found at http://en.wikipedia.org/wiki/Metric_k-center

As you might expect, I can't figure out how this is possible. The part currently causing me problems is how the runtime can not rely on k.

The nature of the problem causes me to try to step through the nodes on a sort of number line and try to find points to put boundaries, marking off the edges of each cluster that way. But this would require a runtime based on k.

The O(n^2) runtime though makes me think it might involve filling out an nxn array with the distance between two nodes in each entry.

Any explanation on how this is works or tips on how to figure it out would be very helpful.


texts: How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem

texts:
I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t:

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

A simple path is a path without any repeated vertice, i.e. every vertice can be visited just one time. The length of the path is given from the edges of which it is composed.

So how can I show that LPATH is an NP-Complete problem using the Hamilton path problem as an NP-Hard problem as reference?


texts: Are there some papers or books that compactly elaborate the essential part of the multiple view geometry?

texts:
I am a novice to visual SLAM and computer vision. Recently I've read a paper "A micro Lie theory for state estimation in robotics" dedicated to introducing the essential part that necessary to roboticists.

I am wondering that are there some papers or books that compactly elaborate the essential part of the multiple view geometry in the manner like the former paper?

And as for bundle adjustment, any recommended papers?


texts: Are machine codes always numerical? (WIkipedia is Ambiguous)

texts:
Wikipedia article on machine code and more in general Wikipedia's take on machine code seems pretty amiguous sometimes.
Often it makes me wonder if there's more, or it is just bad generalization.

Look at this:

  Machine code or machine language is ......Numerical
  machine code (i.e., not assembly code) may be regarded as the
  lowest-level representation of a compiled or assembled computer
  program or as a primitive and hardware-dependent programming language.

It seems to treat numerical machine codes as a subset of machine codes.
Does this imply assembly has to be considered a machine code too?
Or...Is it just implying that exists some non-numerical machine code?
Maybe it's just bad-written, or maybe it's me.

Again, article on object code:

  In a general sense an object code is a sequence of statements or
  instructions in a computer language,[2] usually a machine code
  language (i.e., binary) or.....

"i.e, binary" Does this mean that there are non-binary machine codes?

I'm a little bit confused.


texts: Should activation function be monotonic in neural networks?

texts:
A lot of activation functions in neural networks (sigmoid, tanh, softmax) are monotonic, continuous and differentiable (except of may be a couple of points, where derivative does not exist).

I understand the reason for continuity and differentiability, but can not really understand a reason for monotonisity.


texts:
Here is an experiment I came up with (I don't have sufficient material to make it):

Say that, you have a list of $n$ numbers $L = \{l_1, l_2, ..., l_n\}$.
And you have bars representing those numbers like so:

Say that, width of every bar is $w$.
Imagine a line, thatis made up of $n$ line segments, each of them are $w$ long, and they are enough to cover all the bars.
When any of the lines touches a bar, it sends a signal, declaring its ID.
ID of each bar correspods to its position.

If we are able to build a system as described above, we can release the whole line and store the signals respectively in an array, therefore have the real poisitons of each number we want to sort.

Therotically, when does it take more time and energy to sort $n$ numbers with this method than sorting $n$ numbers using a supercomputer?


texts: Is there a discipline studying the prioritizing of repeated tasks?

texts:
Sorting algorithms have a huge literature behind them, and the algorithm I'm planning has some similarities to the topic, but I couldn't even find the correct search terms to know whether a field exists which studies such algorithms.
Imagine the following problem: there is a serial communication channel of a very low throughput, and you have to communicate with a number of devices through it. If all devices had the same priority, the solution would be obvious:
A B C D A B C D A B C D A ...

(In case of 4 devices, where "A" means "communicate with device A")
However, it can happen that some devices have a lower priority, and our goal is to improve the latency of high-priority devices, that is, the time between two consecutive communications with the same device should be small.
For example, we have devices A, B, C, and D with a high priority, and devices e, f, g and h, with a lower priority.
The naive solution would be to process the lower priority devices only every second turn, or every third turn, etc. Let's call this the "skipping factor".
Example: higher-case letters are twice as important:
A B e C D f A B g C D h A B e C D f A B g C D h ...

Example: higher-case letters are three times as important:
A B C e D A B f C D A g B C D h A B C D e ...

However, this solution quickly breaks down if the number of elements in the different priority categories differ greatly.
Take the example of "capital letters are twice as important", but with 8 capital letters and 2 lower case letters:
A B i C D j E F i G H j A B i ...

Here, the lower-case letters occur more often, even though that's opposite to our goal.
A solution would be to multiply the skipping factor by the ratio of the cardinalities of the priority groups. In the above example, the ratio is 8/2 = 4, we multiply it with the skipping factor of two, and we get 8, so after every 8 capital letter there can come a lower case one.
The problem
The above examples were by far not exhaustive. Even the latest solution in the above example breaks down easily if there are more than two priority groups, and especially if the priority of the elements can change over time. This last constraint can be a very difficult one, as even "smarter" algorithms where every element has its own "timeout" counter ticking down can be fooled by cases where an element changes priority back and forth so that it never gets executed. The complexity also grows because we have to crawl through the lists of elements of every priority level on each occasion we select a new element to be sent.
The question
I have many different ways in my mind to solve this problem, but I'm afraid of trying to re-invent the wheel, and arriving to a suboptimal solution. I'm therefore looking for a field of study which works with problems such as the one listed above. Does it have a name? Does it have a literature? I tried searching some terminology I guessed relevant for the topic, but I couldn't find anything.


texts: Relation of Space and Time in Complexity?

texts:
I'm looking for some clarification on some concepts/facts I came across while studying for a class.

I was reading the following wikipedia article. The below specific section and statement intrigued me when looking it over.

http://en.wikipedia.org/wiki/Computational_complexity_theory#Important_complexity_classes
"It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem"

I also read that NTMs can be simulated by DTMs but that the shortest accepting computation of the DTM is exponential with respect to the shortest accepting computation of the target NTM.

My questions are:

1.) Are PSPACE and NPSPACE the set of all problems that require at least polynomial space to be solved on Deterministic and Non-deterministic Turing machines respectively?

2.) If so, is the actual size of the polynomial space required dependent on the size of the input?

3.) For P and NP, they are each the sets of problems that require at least polynomial time to be solved on DTMs and NTMs respectively correct?

4.) Is the reason that the shortest accepting computation of a DTM simulating a target NTM is exponential with respect to the shortest accepting computation of an NTM due to the exponential explosion of the number of configurations that an NTM supports as input grows for a given problem?

5.) My last and overarching question is: Are the differences in the set of problems that can be solved in polynomial time on DTMs versus NTMs related to time/space tradeoffs where DTMs can't run some polynomial NTM algorithms in polynomial time because they don't have the same "space" that an NTM has available to it?

I'd also appreciate any reading you can suggest to me on time/space tradeoffs and NTMs versus DTMs.


texts: Turing machine working only with 1's and blanks - how to encode input?

texts:
Let's say we have a Turing machine which head can only write 1 or blank to the tape (although it can read all symbols from any input alphabet correctly). Can we operate with it on any input?

My approach was that we can rewrite our input tape with unary coding and symbol-codings separated with blanks. If we had, for example, an input

...[][]0123[][]...

we could try to encode 0 as 1[], 1 as 11[] and so on. We would know when we reached the end of our input word when we read two blanks in a row. However, rewriting the example string from above would cause some problems. When we code a single symbol with multiple ones, we overwrite another symbols and need to remember them in state. In the example above, after encoding 0 our tape would be like

...[][]1[]23[][]...

And in our state we'd remember that we need to encode 1 now. Hovever, writing the encoding would overwrite 2, 3 and a blank, so we would need to remember those ones as well in the state. Such an approach leads to creating a lot of states: for n-letter alphabet and unary encoding I proposed it would be $(n+1)^n$ (all possible combinations of symbols on n+1 positions on the tape) "basic states", and for each of those we'd need a few more so that we could write an adequate number of "1" finished by a blank. I am not sure if this is acceptable at all.

Is my approach correct? What other approaches could I take?


texts: How to store $n$ numbers with space $O(n)$ bits and access time $O(1)$?

texts:
I want to store a subset of $\{1,2,\dots,n\}$ in a data structure such that the total space used is $O(n)$ bits and accessing a particular element can be done in $O(1)$ time. I have tried binary search tree and array data structures but they are too slow.

In short I need a data structure with $O\big(\frac {n } { \log \log n}\big)$ many cells and size of each cell should be $O(\log \log n)$ bits.

Model of computation: Input memory and a write only output memory. The computation proper takes place in a working memory of limited size. When stating a problem can be solved with in a certain bits, what we mean is that the working memory comprises that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$, arithmetic and logical operations on $w$-bit words take constant time, and random access to the input and working memories is provided. In the context of inputs of $n$ words,$w= \theta(\log n)$.

Operations: Insert($i$), access($i$), where $i \in [n]$.  The access operation must run in $O(1)$ time.

Motivation: I'd like to store the stack in DFS using this data structure.

I am looking for an deterministic approach, but to me it does not seems working, so probabilistic approach is also fine.


texts: The role of the root switch after Spanning Tree Protocol has established a tree network in a LAN?

texts:
In Spanning Tree Protocol, a root switch is selected at first, and then somehow, the shortest path from each other switch to the root is obtained. Thus we established a tree network.

My questions are:

  After the tree network is established, does the root switch act as a center in the network? In other words, all the traffic originated from other switch would first flow into the root switch along the shortest path and then routed to its destination by the root switch, also along the shortest path.
  If it's not the case, why does the protocol calculate a tree such that the path between each non-root switches and the root is minimized?  As far as I can see, a minimum spanning tree would work better, which is not difficult to calculate.


texts: Book Recommendations for a General Introduction to (Theoretical) Computer Science

texts:
After perusing the web and cs.stackexchange in particular, I've come across many different wonderful resources in Computer Science - from Sipser's "Introduction to the Theory of Computation" to books on Languages or volumes on Cryptography.

However, what I couldn't find was a general introduction to Computer Science, a book that covers some of these topics briefly in distinct chapters. That is to say, a chapter on computational complexity, a chapter on languages, a chapter on logic, a chapter on cryptography, a chapter on algorithms etc, all in one book.

I'm a math major, and whenever I run into things like hash functions or "automata", I have to hit Google and go from there. It'd be nice if I could have a book that could get me reasonably up to speed on many of these foundations and central ideas in (theoretical) computer science without having to read 4 different books about 4 different fields in CS totalling 2000+ pages.

Just to be clear, I'm not really looking for hands-on books on how to write code - this question pertains mostly to the theoretical bases of CS (although I wouldn't mind a chapter on functional programming or "programming concepts"). Also, my preference goes out to a book as opposed to a website or online resource as I travel a lot and usually don't have access to the internet, though I do have the habit of taking a book with me.

In essence, I'm thinking about something equivalent to "University Physics" books (but instead, a fair bit shorter as those tend to be huge tomes of 1400+ pages), or "Mathematical Methods for Scientists" - something like that.


texts: Algorithm to determine whether a given graph is a caterpillar tree

texts:
I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree.

A caterpillar tree is a tree that has a path to which all nodes are connected by a maximum of one edge. So for every vertex v there is a vertex u on the path so that the disctance between v und u is at most 1. In other words, removing all the leaves results in a simple path.

The only progress I've made so far is that I could use breadth-first search or depth-first search to traverse the graph. They have a complexity of $\mathcal O(|V|+|E|)$, but in a caterpillar tree, $|E|=|V|-1$, so I end up in $\mathcal O(2|V|)$ = $\mathcal O(|V|)$.

Is that idea correct? If so, then how can I modify BFS/DFS to do what I want? I am thinking of adding a branch depth counter of some sort and allowing only one branch with length >1 (the central path of the caterpillar), but I have no idea how to implement that without changing the original algorithm too much.


texts: Why is my Forrest-Tomlin update worse than recomputing LU?

texts:
I wrote a simple C++ implementation of the revised simplex method that recomputes the LU decomposition of the basis from scratch on each iteration. I have to solve problems with many variables but few constraints (say, 50 constraints and 5000 variables or more), so I thought that was ok.

Then I decided to implement a basis refactorization approach, so I chose the Forrest-Tomlin basis update approach. I observed that the program became much slower! I would like to understand why and whether this is expected for the kinds of problems (few constraints, many variables) that I consider.

A few words on how I have implemented Forrest-Tomlin. Say that the initial basis matrix is factorized as $B = LU$. After $k$ updates, I have a factorization $B = LR_1\cdots R_k U$ (I am for simplicity ignoring the permutation matrices involved). Then to solve the system $Bx = b$ I have to solve $L R_1 \cdots R_k y = b$ and then $Ux = y$. Solving $L R_1 \cdots R_k y = b$ is easy since the matrices $R_i$ are very special; solving a system $R_i x = b$ takes linear time.

What I have observed after profiling is that most of the time was spent solving systems with the $R_i$ matrices. With Forrest-Tomlin there is an added cost to solve a system, and since I have many more columns than rows, to find the incoming variable I have to solve many systems, which becomes less efficient the more updates I make. And this extra cost is much higher than computing the LU decomposition from scratch.

Does this make sense? Am I missing something?


texts:
Version 1 of the question: I am looking for any correct $O(n)$ algorithm in the literature which will solve the DFA minimization problem referred to in the quote below from [Almeida & Zeitoun 2008]. Whether the algorithm works on strings or automata doesn't matter.

Version 2 of the question: What is the classical algorithm being referred to in the quote below? The closest I've been able to get from reference [9] in the quote is algorithm SCOPES on page 307, but that requires that $k$ be given as an argument.

  Recall that the primitive root of a word $w$ is the shortest word $r$
  such that $w = r^k$ for some $k$. It is easy to see that minimizing a
  cycle
  $s_0 \xrightarrow{a_0} s_1 \xrightarrow{a_2} \ldots \xrightarrow{a_k} s_0$
  amounts to finding a primitive root of its associated circular word:
  this primitive root is itself a circular word, and the cycle
  associated to it is the minimal automaton of the original cycle.
  It is classical
  that this computation can be performed in linear time
  (see e.g. [9] for instance).

[Almeida & Zeitoun 2008] J. Almeida and M. Zeitoun. Description and analysis of a bottom-up DFA minimization algorithm. Inform. Process. Lett., 107(2):52–59, 2008.

[9] M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, 1994.


texts: Time complexity in Big O notation for Harmonic series with first k terms missing

texts:
Firstly, let's suppose there exists an algorithm where $i$ iterates from $1$ to $n$, spending $\frac{n^2}{i}$ time in each iteration.

Thanks to the well known $O(\log n)$ upper bound for the Harmonic series, the big $O$ notation of this algorithm comes to $O(n^2 \log n)$.

Now the actual algorithm that I am working on iterates from $k$ to $n$, where $1 < k < n$, spending $\frac{n^2}{k}$ in the first iteration, then $\frac{n^2}{k+1}$, $\frac{n^2}{k+2}$, $\frac{n^2}{k+3}$, and so on.

I've been trying to deduce the upper bound of this new algorithm, but I keep getting the same $O(n^2 \log n)$ time bound, which to me, is counter intuitive and a bit paradoxical, especially considering that the first terms of the harmonic series are the bigger and more significant terms. The time bound that I was actually expecting to get was $O(\frac{n^2}{k} \cdot \log n)$.

Could anyone please be able to shed some light onto this?

Thanks in advance for any help.


texts: Not sure if my solution to following recurrence is correct

texts:
I have a recurrence relation, it is like the following:

$T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm.

To solve this and find a $\Theta$ bound, I tried the following: I put $k=e^n$, and the equation transforms into:

$$T(k)=2T(k/e)+k$$

Then, I try to use the Master Theorem. According to Master Theorem, $a=2$, $b=e\gt 2$ and $f(k)=k$. So, we have the case where $f(k)=\Omega(n^{\log_b a+ε})$ for some $ε\gt 0$, thus we have $T(k)=\Theta(f(k))=\Theta(k)$. Then put $k=n$, we have $T(n)=\Theta(n)$. Does my solution have any mistakes?


texts: What algorithm to use, least waste when sawing wood planks

texts:
Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 30cm 50cm and 20cm. Is there an algorithm for calculating the least waste? When using brute force it quickly escalates in time :(

Formally we have $N$ wooden planks each $L_1, \dots, L_N$ cm long. And we want to have $M$ pieces, $l_1, l_2, \dots, l_M$ cm long. How to minimize the waste?


texts: Improving heading measurements from low cost compass module

texts:
I have heading measurements of two Sensors (BNO055 and HMC6343) and also accurate measurements from better sensors for comparison from a rotating platform. Most of the measurements are with some kind of potentional error source like passing train, large ferromagnetic materials.

The measurements of the BNO055 can't be used at all since he mostly doesn't even react to changes in angle. The measurements of the HMC have some other problems.

Large Offset at the Start that only converges towards the true value after some movement of the sensor (elevation change) i guess sensors needs to calibrate at the start every time
Sometimes small global offsets towards the true value
Larger periodic deviations and noise (esp. near rails)

If you don't want to read the paragrpahs of my endeavors below. My question is basically is it possible to get major improvements with only positional data from one sensor and the reference data and nothing else?

I'm kind of at a loss how i could improve the measurements. I started to learn about Kalman filter and tried a simple kalman filter with a linear model: x+vt+at^2/2 (x being angle etc.). But neither sensors fusion is an option because of useless BNO measurements and also a filter with just HMC measurements with state vectors (x,v) and (x,v,a) don't really improve my measurements. (x,v,a) vector is actually even worse.

I'm kind of at a loss here. I'm trying to understand unscented/extended kalman filter but atm i don't really see the point since its for nonlienar models and i don't know how i could't describe the angular movement differently than with the simple movement equation above.

I also read something about calibrating with neural networks but are not quite sure if it's worth to invest more time into it since my time is limited.

Edit: I added some pictures of the measurements so people who might want to chip in have a better idea. The blue and red lines are not interesting. Green are the accurate measurements. Orange are the measurements of my sensor. A big problem is also that the sensor doesn't measure the right heading at the start if the antenna hasn't changed elevation yet. He seems to need to calibrate for a bit to reach his estimated value.


texts: LR parsers and ambiguous and non deterministic grammars

texts:
Dragon book says:

  An ambiguous grammar can never be LR.

And then immediately further it says:

  For example, consider the dangling-else grammar:

  $\begin{align} stmt \rightarrow & \textbf{ if  } expr \textbf{ then }stmt   \\
      &| \textbf{ if  } expr \textbf{ then }stmt \textbf{ else } stmt \\
      &|\textbf{ other} \end{align} $

  If we have a shift reduce parser in configuration

  $$
\begin{matrix}
STACK & INPUT \\
...\textbf{if }expr\textbf{ then }stmt  & \textbf{else...}
\end{matrix}
$$

  we cannot tell whether $\textbf{if }expr\textbf{ then }stmt$ is the handle, no matter what appears below it on the stack. Here there is a shiftl reduce conflict. Depending on what follows the $\textbf{else}$** on the input, it might be correct to reduce $\textbf{if }expr\textbf{ then }stmt$, or it might be correct to shift $\textbf{else}$ and then to look for another $stmt$
  to complete the alternative $\textbf{if }expr\textbf{ then }stmt \textbf{ else } stmt$.

My question is quite simple one. The author starts with saying fact about "ambiguous" grammar but then he gives example of problem with same prefix of right sides of two productions (say non deterministic grammar) but not really related to the ambiguousness of grammar.

Am I right? Also what does that mean? LR grammar cannot work with both: Non deterministic and ambiguous grammars?


texts: Language to Construct Finite State Transducer

texts:
I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing.

You typically construct finite automata using regular expressions, for example (a | b).

What language does one typically use to construct Finite State Transducers?

You can't use Regular Expressions alone, because that defines only the input string, but I need some method to map corresponding output symbol.  I have thought about having something like this ((a,x) | (b, y)), where the tuple (a,x) is composed of the component a input value, and the component x is the corresponding output value.  Would that work in general for constructing FST?


texts:
I was reading a book on Operating System by Galvin and came across this :
In the latest version of Solaris, scheduling is controlled by loadable tables. Depending on the table currently loaded, the system can be time-sharing, batch processing, real-time, fair share, or any combination. Making the scheduling mechanism general-purpose allows profound policy changes to be made with a single load-new-table command.
Can someone explain what are these loadable tables.
Thanks in advance :)


texts: Grammar quine - Formal grammar self-definition

texts:
Is it possible to derive a grammar with iself?
Or more precisely, is it possible to conceive a grammar which language contains that grammar?

For example, the Wikipedia article about BNF claims to represent the BNF syntax with BNF.
But if we tried to derive BNF with it, we'd obtain the same BNF, but with each character quoted (double-quotes single-quoted and other characters double-quoted). It's understandable, but it's not exactly the same (actually it's like if the quoted characters were another alphabet).

Here is my attempt to define an unrestricted grammar (ignore white spaces):

P = p P | p ;
p = V n V = A ; ;
A = V | A | V ;
V = v V | ;
v = n | t ;
n = P | p | V | v | n | t ;
t = P | p | V | v | n | t | = | | | ; ;

Another one with less "special characters" (|, A, p, v, n and t are optional but improved readability):

P = V P V = V ; P ;
P = V V V = V ; P ;
P = V P V = V ; ;
P = V V V = V ; ;
V = P V ;
V = V V ;
V = P V ;
V = V V ;
V = = V ;
V = ; V ;
V = ;

And with a regex: ( [ P V P V = ; ]* [ P V ] [ P V P V = ; ]* = [ P V P V = ; ]* ; )+

So we need 3 alphabets to build it (normal for "special characters", bold for variables and code for terminals).

EDIT: Actually we need an infinite number of alphabet... If we try to derive it once, normal is replaced by bold, bold by code, but we need a new alphabet to replace code…

Is it possible to derive it with only one alphabet?

EDIT: A question I'll ask in another post:

Is it possible to design a program able to learn a grammar with just its self-definition?


texts:
In my Artificial Intelligence class we are going over upper and lower bounds in regards to searching a tree, given a state space.

From my understanding, a lower bound is also known as a depth-bound and sets a limit on how far down a tree we can search.

But if that's a lower bound, then what would an upper bound be? We're not searching up the tree.


texts: What does floating point biased notation have to do with 2's complement?

texts:
During lecture the professor talked about Integer Compare for floats and kept mentioning two's complement.

What's the relation between them?

All I understand is that two's complement can take us from a number to its negative.


texts: Is it always possible to arrive at a desired item on Wikipedia starting from a random item?

texts: On Wikipedia, I tried a number of times to find the item I needed, starting from a random page and clicking on various (non-random) hyperlinks. Every time I succeeded in finding my desired item. Is this always possible?


texts: Every circuit of size at most $S$ can be representd as a string of $9S \log S$ bits

texts: I'm trying to understand this claim. I see that if there are $S$ vertices, then we can identify each vertex using $\log S$ bits. Now each vertex can be connected to, let's say, $S$ other ones (is there some sort of restriction to the fan-out that I'm unaware of?). If we use an adjacency list, then for each vertex, we wold need to store up to $S \log S$ bits. Doesn't this lead to $S^2 \log S$ bits, since we need a list for each vertex? And where does the $9$ come from?


texts: Meaning of the notation Typ := TVar | (Typ → Typ)

texts:
In the paper "introduction to type theory" by Herman Geuvers, it states the following definition for the type theory of propositional logic (I've added "convention 2" just for reference):

Given that this is an introduction, I'd assume that he would explain the meaning of a statement like $\mathrm {Typ}:=\mathrm {TVar}|(\mathrm {Typ}\to \mathrm {Typ})$, or what a "type variable" is.

My question is twofold:

What do these two things mean?
What background knowledge is this introduction assuming, that I would need to study before reading this "introductory" text?


texts: Finding values in a space that matches a relational query

texts:
Assume we have 26 vectors ${A,B,C,....,Z}$ all have 1 million integers. given a query:
$$
\vec{query} = (r_a, r_b, r_c, ..., r_c)
$$
I want to find a match vector $\vec{m_{1 \times 26}} = (a, b, c, ..., z)$ that satisfies the following criterias:
$$
a \in A, b \in B, c \in C, ..., z \in Z \\
\text{and} \\
r_{a} = \frac{a}{\sum_{\theta \in m}{\theta}}, r_{b} = \frac{b}{\sum_{\theta \in m}{\theta}}, ..., r_{z} = \frac{z}{\sum_{\theta \in m}{\theta}}
$$
in which $\sum_{\theta \in m}{\theta}$ is basically sum of the values in vector m. In other words, let say given the amount of share each $a, b, c, ..., z$ has in my math vector m, I want to find the elements. Of course, one yet not feasible solution is checking all ${(10^6)^{26}}$ possible combinations and check if there exists any match. There could be multiple answers, but any of them is fine.
Example:
Let say all ${A,B,C,....,Z}$ are equal to each other and contains elements between $1$ and $10^6$ like $\{1,2,3,...,10^6\}$. given query $\vec{query} = (\frac{1}{26}, \frac{1}{26}, \frac{1}{26}, ..., \frac{1}{26})$, $m$ is one of the many possible solutions:
$$
\vec{m} = (1,1,1,...,1).
$$
My question is, what could be the fastest algorithm for solving this problem?


texts: Bounded Quantification: Full F<: intuition

texts:
I'm currently looking into Chapter 26 of Types and Programming Languages and am a bit confused by the "intuition" for Full F<: (p. 395):

  A type T = ∀X<:T1.T2 describes a collection of functions from types to values, each mapping subtypes of T1 to instances of T2. If T1 is a subtype of S1, then the domain of T is smaller than that of S = ∀X<:S1.S2, so S is a stronger constraint and describes a smaller collection of polymorphic values.

Why is S a stronger constraint due to the fact that T's domain is smaller than S's?


texts: How to use WISARD neural network to detect defects in banknotes

texts:
We learned about the WISARD neural network in my machine learning course. We said that for an $n\times k$ image, we would use discriminators having $n$ RAM neurons each of $2^k$ bits. The examples we covered were always simplistic and involved small images, something like $3\times 4$.

I am looking at some past papers in preparation for my exam, and in one particular question we are asked to describe the architecture we would use for a WISARD neural network to detect defective bank notes, having a resolution of $768\times 384$. I'm thinking that $768$ RAM neurons of $2^{384}$ bits each is not feasible. What architecture should be used in this case? Are we perhaps expected to group pixels together to have less neurons with less bits?

Any help is greatly appreciated.


texts:
Show that if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$?

Does this need to be shown through induction or is it sufficient to say:

Let $d(n) = n$ which is $O(f(n))$.

Therefore $ad(n) = an$ which is trivially $O(f(n))$


texts: How can I have constant time initialization for multi-dimensional arrays?

texts:
For a regular array, I understand that if we have the tradeoff of space vs time, and we use more space to implement a Which, Data, and When pointers to the actual array, we can initialize the array in constant time because there are pointers to access and keep track of the elements in the array.

How can I extend the idea of using the Which, Data, and When pointers to have constant time initialization for multi-dimensional arrays? Would I have to have multiple Which, Data, and When pointers to keep track of n-th D array dimensions?

Or is the use of hierarchical tables, which stores multi-dimensional arrays as an array of pointers to tables, where each table contains a row of the array, and implementing the Which, Data, and When pointers to the hierarchical tables a correct way for having constant time initialization of multi-dimensional arrays?

Edit: Use C notation for simplicity. Let's say for a large N we have an array:

SomeType array[N];

If N is very large, and only a few of the array's elements are ever used, just initializing it can become the largest cost of an algorithm. A way around this is to have a self-checking structure that can be filled in on demand. To the above add (I'm not the original poster, so I will use my own names here):

int last_used = -1, place[N], order[N];

The idea is that last_used tells the last used entry, place[i] is the index of the i-th asigned element of array, and order[k] is the order in which the array[k] was initialized. Note that none of array, place and order are initialized, their initial values are arbitrary. place[i] and order[k] serve to check each other. To use array[i], see if order[i] < last_used (it is in the right range, might have been set already; if not, it is clearly garbage) and also place[order[i]] == i. If so, the element has been used, go ahead. If not, do:

last_used++;          /* Another one is in use */
place[last_used] = i; /* The next one in use is array[i] */
order[i] = last_used; /* Point back */
initialize(array[i]); /* Prepare for use */
/* Furiously frob array[i] */

The time of this is bounded by a constant; so the initialization time, amortized over the initialized elements, is constant. For a practical implementation, this can be packaged conveniently in a C++ class (templated on SomeType and N) overloading operator[].

Remark: This can clearly be extended to an array of such arrays.


texts: Relation between sets of vertices in a graph

texts: Suppose I have a graph with vertices of three colors - black, gray, and white. I want to compare the connectivity between sets of vertices to make claims like - the black set is more related to the white set than the gray set, and so on. How are such claims measured? Are there standard metrics or methods for that case?


texts: Need help regarding random password generator: Urgent

texts:
I had generated a random password from a website which unfortunately has put me into trouble.

The password contains 26 characters which includes alphabets, numbers and special characters. My trouble started when it was found that among the 26 characters there was a 4 letter Malayalam word (spelled in English) which is interpreted to be abusive, followed by an exclamation mark and then again followed by 3 alphabets which unfortunately consists of the initials of the person to whom I had sent the password.

How can I make others believe that this can be auto generated using a random password/string generator algorithm?

I request those people who are acquainted with such algorithms to please help me in this regard. Those who can help me may please reply at the earliest.


texts: Can the perceptron classifier achieve perfect accuracy, on any data set?

texts:
I was thinking. Since any data can become linearly seprabale through kernel methods, meaning there is a dimension where this data is linearly seprable, so feed this processed data set into the perceptron algorithm and then it might get to 100 percent accuracy.
Am I correct?


texts: Pushdown Automata for number of a less than 2 times number of b

texts:
Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works?

we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols $\{S,A,B \}$, start state $q_0$, accept state $q_3$, we have rules as following:
$q_0$ accepts nothing and push $S$ onto stack to $q_1$

$q_1$ reads $a$ and pops $B$, remain in $q_1$

$q_1$ reads $a$ and pushes $A$, remain in $q_1$

$q_1$ reads $b$ and pushes $BB$, remain in $q_1$

$q_1$ reads $b$ and pops$AA$, remain in $q_1$

$q_1$ reads $b$ and pops$A$ and pushes $B$, remain in $q_1$

$q_1$ reads nothing and pops $B$, go to $q_2$

$q_2$ reads nothing and pops $B$, remain in $q_2$

$q_2$ reads nothing and pops $S$, go to $p_3$


texts: What is the difference between shortest distance and shortest path?

texts:
I am studying graph currently. I found a question, which asks for

The List A[] which shows shortest distances between $V$ and every
other vertex
The List B[] which shows shortest paths between $V$ and every other vertex

as subpoints. I don't think the question wants me to compute the same values twice, but I don't know what the difference between shortest distance and shortest path is. Can anyody explain?


texts:
From Xiong, Hui, Shashi Shekhar, Pang-Ning Tan, and Vipin Kumar. “TAPER: A Two-Step Approach for All-Strong-Pairs Correlation Query in Large Databases.” Knowledge and Data Engineering, IEEE Transactions on 18, no. 4 (2006): 493–508.
:

  Support measures the fraction of transactions that contain a
  particular subset of items. The notions of support and correlation may
  not necessarily agree with each other. This is because item pairs with
  high support may be poorly correlated while those that are highly
  correlated may have very low support. For instance,
  suppose we have an item pair {A, B}, where supp(A)
  = supp(B) = 0.8 and supp(A, B) = 0.64. Both items are uncorrelated because supp(A, B) = supp(A)supp(B). In contrast, an item pair {A, B}
  with supp(A) = supp(B) = supp(A, B) = 0.001 is perfectly correlated
  despite its low support.

I don't quite follow the example about support. Could anyone give a proof of $supp(A)supp(B) = supp(A, B) \iff A \text{ and } B \text{ are uncorrelated}$ ? I don't even quite understand what $supp(A, B)$ means. Is there a book or paper on support vs correlation?


texts: Recalculating shortest path after changing the weights

texts:
I have a weighted, directed graph. I do the following. Given nodes $s$ and $t$ I compute shortest path. Then, I decrease weights of some edges and want to see if there is now another shortest path. Of course, I can recompute shortest path, but I want something faster.

For example, one approach would be to store shortest paths from $s$ to $t$ for every edge in the graph. Then, when I change the weights it takes constant time to check if the shortest path changed (even though, the first step takes much more time). The drawback is that I have to store many paths and to calculate all simple paths in advance, so I'm seeking for alternatives.

So my question is if it's possible to check if the shortest path changed after we decrease edge weights?

Edit: Apparently, this is a problem of dynamic graphs. I didn't delve into the algorithms, so, which algorithm can I use for this problem? I want to improve on running time Dijkstra algorithm.


texts: How to use structural induction to prove law on lists

texts:
I want to prove that the following equation holds using structural induction on (finite) lists

subs (map f xs) = map (map f) (subs xs)

where subs [] = [[]]                                          (subs.1)
      subs (x:xs) = subs (xs) ++ map (x:) (subs xs)           (subs.2)

      map f [] = []                                           (map.1)
      map f (x:xs) = f x : map f xs                           (map.2)

: is the cons operator and ++ the join operator on lists.

I'm using structural induction on xs, the base step for [] is easy to prove but I hit a wall when trying to solve the inductive step for (x:xs)

subs (map f) (x:xs)                                             (map.2)
subs (f x : map f xs)                                           (subs.2)
subs (map f xs) ++ map ((f x):) (subs (map f xs))               (hyp)
(map (map f) (subs xs)) ++ map ((f x):) (map (map f)(subs xs))

From here I couldn't find a way to proceed so I moved to the right-hand side of the equation and I kind of found a way to find a "proof" but something tells me that it's bogus

map (map f) (subs (x:xs))                     (subs.2)
map (map f) (subs xs ++ map (x:) (subs xs))   (generalise term)
map (map f) ys                                (hyp)
subs (map f ys)                               ???
subs (map f (y:ys))
□

My reasoning here is: (x:xs) is a list with at least length 1, it should be legal to generalise subs xs ++ map (x:) (subs xs) as either (y:ys) or ys (because (x:xs) is not empty) so I chose the latter first to be able to use the induction hypothesis and after that I rewritten ys as (y:ys) to establish the case.

Does this make any sense at all? If not, could anybody show me the right approach to tackle this proof?


texts: A* search tree version - Can a node be in the frontier multiple times

texts:
I took an exam today and it had a question on A* tree search version, we only briefly skimmed over this on the material, focusing more on the graph search version.
In the example in the question text it showed a node being expanded and then a node already in the frontier being added again, due to the expansion, so it was listed twice in the frontier.
I did know about this, and so in my answers, when I needed to show the state of the frontier, and expanding a node meant a node already in the frontier was shown I added it again.
This meant in my answer I had a node in the frontier twice, but I am not sure if this was correct, as the question was long and involved showing the frontier multiple times, and I had the node in there twice, if it is wrong I likely got most of the question wrong.
Could someone tell me if this is something that happens with the tree search version, where there is no explored set, I am wondering if it was just a typo in the question text now.


texts: $a^*b^*c^* \setminus \{a^n b^n c^n | n ≥ 0\}$ is not regular using pumping lemma?

texts:
$L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $\neq$ into smaller and larger. You will have four sets. You can give CFG's for each. Then since CFGs are closed under union, you have your proof.

Now how can I go around proving that $L$ is not regular? If you prove that the each of these four sets are not regular, you still can not prove that the union is not regular, can you?


texts:
for (i=1; i<=n ;i=i*2){

  for (j=1; j<=i ;j++){

  basic_step;

  }
}

Regarding the above nested loops, I can't seem to understand why is the following runtime analysis is correct (specifically the first equality), when $k$ is defined as $\log i$, meaning $i=2^k$.
What is the process that one should come up with, in order to decide this setting and the sigmas' indices? While I do understand that the outer loop runs for $\Theta(\log n)$ times, I still can't grasp the setting of $k$. A clarification will be very much appreciated!

$$\sum_{k=0}^{\log n}\sum_{j=1}^{2^k}1$$


texts: Describing explicitly the MyHill-Nerode classes created by a language

texts:
I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt:

For the language
$$L=\{\omega \in \{a,b\}^* \colon \omega \text{ contains at most 1 } 'a' \}$$
The classes are
$$M_1=\{\omega \in b^*\}$$
$$M_2=\{\omega \in b^*ab^*\}$$
$$M_3=\{\omega \in b^*ab^*a(a\cup b)^*\}$$

Now, the way I understand it I need to prove 2 things:

For each $u,v\in M_i (1\le i\le 3)$ and for each $x\in \Sigma^*$
$$ux\in L \iff vx\in L$$
There exists $u\in M_i,v\in M_j(1\le i \neq j \le 3)$ and $x\in \Sigma^*$ such that
$$ux\in L,vx\notin L$$

Am I right about how I described the classes, and about how to prove it?


texts: What does canonicity property mean in Type Theory?

texts:
The "Computational Component" section of the Type Theory - Wikipedia (as well as a few papers about cubical type theory and 2d type theory) talk about canonicity property.

Would you please explain exactly what this property is and what does
it mean in type theory?
Why and how is it lost in the Homotopy Type Theory with the univalent axiom?


texts: Regular expressions and 'capturing parentheses' with 'backreferences'

texts:
We know that regular expressions (RE) are implemented with finite automata (FA). In some language (like JavaScript) in RE there are features like 'capturing parenthesis' with 'backreferences':

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions#special-capturing-parentheses

(x)
Matches 'x' and remembers the match, as the following example shows. The parentheses are called capturing parentheses.
The '(foo)' and '(bar)' in the pattern /(foo) (bar) \1 \2/ match and remember the first two words in the string "foo bar foo bar". The \1 and \2 in the pattern match the string's last two words.

I want to know if this pattern /(foo) (bar) \1 \2/ is in fact a RE according the definition of RE that we have in theoretical formal language or it is something more powerful. And if it is so I would like to know if this kind of feature is implemented also with FA or in another way (in particualr how it is implemented).


texts: Does this LCS algo generate all the CS or only all the LCSs?

texts:
The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-calculated, if you go up a tad bit. C[i][j] stores the LCSLength for given str1[1...i], str2[1...j].

(screenshot, for a quicker reference)

My understanding is that it generates all the common sequences since either or both if conditions at the end are satisfied, which runs the program for the sub-cases. Once the last letters are matched, every string upto that point (with the current X[i] as the last letter) is printed.

I somewhere fail to digest the algorithm properly and completely. An explanation might help me very much.

In the penultimate if, does changing writing the piece of code as  R := R $\cup$ backtrackAll(C, X, Y, i, j-1) (instead of  R := backtrackAll(C, X, Y, i, j-1)) change anything? I feel that it doesn't, given it's a top down approach and it only unions with the empty set R = {} above. Note that R is already defined above and the if is reached only after going through that empty set definition step, which rules out the possibility of having an error output.


texts:
$\text{Consider the following ANSI C code:}$
int main(){
 Integer x;
 return 0;
}

$\text{What will be the type of error?}$
$\text{a) Lexical}$,
$\text{b) Syntax}$,
$\text{c) Semantic}$,
$\text{d) None}$  $\tag {GATE-CS 2021}$
According to me, Syntax Analysis phase should detect the error as there is no grammar in C which produces Integer x or in tokenized form id id. Any help is appreciated. :)


texts: Why doesn't Quantum Turing Machine contradict with Church-Turing thesis

texts: I studied about Quantum Turing machine and i figured out that the difference between QTM and TM is in transition function and also if a problem is unsolvable by a TM then it is unsolvable by a QTM but I need a justifiable reason to claim QTM does not contradict with Church-Turing thesis.


texts:
I'm trying to prove that if P = NP, then {⟨a, b, c⟩ : a + b = c} (as addition over N) is NP-complete.

I think I managed to prove that it is in NP, but I'm not sure what would be a good NP complete problem to reduce to would be, or what algorithm to use. Any ideas?


texts: what is CFG of $\{a^i b^j c^k \mid k = |i-j| \}$

texts:
what steps should I take to find out what is the context free grammar of

$L(w) = \{a^i b^j c^k \mid k = |i-j| \}$


texts: The meaning of discount factor on reinforcement learning

texts:
After reading of the google deepmind achievements on Atari's games, I am trying to understand the q-learning and q-networks, but I am little bit confused. The confusion arise in the concept of the discount factor.
Brief summary of what I understand.
A deep convolutional neural network is used to estimate the value of the optimal expected value of an action. The network has to minimize the loss function
$$
L_i=\mathbb{E}_{s,a,r}\left[(\mathbb{E}_{s'}\left[y|s,a\right]-Q(s,a;\theta_i))^2\right]
$$
where $\mathbb{E}_{s'}\left[y|s,a\right]$ is
$$
\mathbb{E}\left[r+\gamma max_{a'} Q(s',a';\theta^-_i)\right|s,a]
$$
Where $Q$ is a cumulative score value and $r$ is the score value for the action choose. $s,a$ and $s',a'$ are respectively the state and the action choose at the time $t$ and the state and the action at the time $t'$. The $\theta^-_i$ are the weights of the network at the previous iteration. The $\gamma$ is a discount factor that take into account the temporal difference of the score values. The $i$ subscript is the temporal step.
The problem here is to understand why $\gamma$ does not depends on $\theta$.

From the mathematical point of view $\gamma$ is the discount factor and represents the likelihood to reach the state $s'$ from the state $s$.

I guess that the network actually learn  to rescale the $Q$ according to the true value of $\gamma$, so why not letting $\gamma=1$?


texts: Best data structure for high dimensional nearest neighbor search

texts:
I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I've read that in general, all space-partitioning data structures tends to perform exhaustive search with high dimensional data.

Additionally, there are two important facts to be considered (ordered by  relevance):

Precision: The nearest neighbors must be found (not approximations).
Speed: The search must be as fast as possible. (The time to create the data structure isn't really important).

So, I need some advice about:

The data structure to perform kNN.
If it will be better to use an aNN (approximate nearest neighbor) approach, setting it as accurate as possible?.


texts: Is there a polynomial algorithm for optimal sorting on trees?

texts:
There's the classical problem of sorting numbers in a list with the restriction that you can only swap two neighbouring numbers. It's easy to see that getting an optimal number of needed swaps can be achieved by insertion sort or bubble sort.

We can generalize this problem by changing the underlying structure from a list to a graph. Instead of swapping neighbouring numbers in a list we would be swapping numbers connected by an edge. Formally let's have a graph G=(V, E) with V = {1, ..., N} and an assignment of values f: V -> {1, ..., N} where f is a bijection/permutation. In order to do a swap we select an edge {u, v} from E and switch f(u) with f(v). Our goal is to sort f (that is achieve a state when f is the identity) in the least number of swaps. My question is whether there is a (polynomial) algorithm for this.

Since working on general graphs seems really difficult from what I've tried let's restrict ourselves to G being a tree. This should be a simpler question because each number has a clear path to its target.

Some observations:

When G is a path graph the problem is the same as sorting a list which is simple.

When G is a complete graph the problem is also simple since we only need to decompose each cycle into transpositions. You can actually look at the general problem as decomposing a permutation into as few transpositions as possible with the restriction of which transpositions you are allowed to use.

As long as the graph is connected there's a lower bound of "sum of all distances to targets"/2 because each swap decreases the distance to target of at most two numbers. The upper bound is "sum of all distances to targets" because we can select a number that wants to be in a non-articulation vertex (or simply leaf in trees) and drag it there. Then we can forget about this vertex and reduce the problem to a smaller graph.


texts: Creating artificial NP-Complete problems

texts: Stephen Cook's proof of the NP-completeness of SAT is constructive. Given a Turing machine $M$, one can create a logical formula that is satisfiable if and only if $M$'s computation halts in an accepting state. This suggests that we could take a logical formula and create a Turing machine $M'$ whose computation is described by that formula, thereby creating an artificial problem solved by $M'$. Is it possible to use existing NP-complete problems to create other NP-complete problems? Can this be automated?


texts: Context-free grammar for $L = \{a^{2^k}, k \in\mathbb{N}\}$

texts:
In an exercise, I am asked to find a context free grammar for language $L = \{a^{2^k}, k \in \mathbb{N}\}$.

I have been trying to use a "doubling" variable. If $a^{2n} \in L, n\in\mathbb{N}$ then use this variable to double the $a$'s that have been produced by the other language rules.

Is this thinking valid? So far I haven't been able to get anywhere with it, but it seems logical given the double-stack of powers.


texts: Proof of equivalence of L0 and language accepted by made up machine

texts: I have a made up machine, which has the same definition as Turing machine, but the transition function and the step of computation of the machine. What would be the approach of the proof that the language accepted by this machine is (or is not) equal to L0 (recursively enumerable language)?


texts:
I'm interested in surprising data structures that extend the things people learned in their first algorithm/data structure course. Usually by offering an additional operation at a very low cost.

I learned that one can create a dynamic array with $O(1)$ access and $O(1)$ amortized append a long time ago. I thought there is no way to remove the amortized cost. I saw a data structure only a few months ago that do both operations in $O(1)$ non-amortized time.

What are some other examples?


texts: Building maze to maximize shortest path, may be given waypoints and teleports

texts:
How would you go about solving this problem?  Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores?  (Assuming sizes between 8x8 and 30x30.  Using C or C++ if that matters)  Or, is this so complex that it would take way longer?

There is an area, where an automated traveler follows a shortest path algorithm at all times.  Playing the builder, find the way to maximize the number of points the traveler must visit.

The area is typically between 8x8 and 30x30, given in the form:

.F......
......a.
........
........
.....1X.
........
.A......
........
..O.....
.X......
..X.....
..X.....

Where there is:

Always a single O, the starting point
Always a single F, the ending point
Always many ., empty points that can either be traveled or built on
Sometimes X, points designating they are blocked for traveling or building
Sometimes pairs of letters (i.e. A and a, but never F, O, or X), indicating a teleport when visiting the uppercase letter for the first time to the lowercase letter
Sometimes numbers (i.e. 1), designating waypoints

The automated traveler follows a shortest path algorithm at all times.  It must begin at the starting point, if there are waypoints pass over them in order, and finish at the ending point.  The traveler may pass over the ending point or subsequent waypoints early, but the game doesn't end and the waypoints aren't counted as visited, until they are the active next destination.  If there are any, the traveler must not pay attention to any teleport spots; they must take the shortest path between points as if they cannot see these teleport spots.  The exception to this rule is if there are multiple paths with the shortest length between last source to next destination and one of them travels through an active teleport spot, the path with the teleport must be taken.  (Otherwise, can choose any of the multiple shortest paths.)  If the shortest path forces them into a teleport spot, they teleport the first time they visit the uppercase letter to the corresponding lowercase letter.  The traveler can move horizontally and vertically.  The traveler can move diagonally between two points if the 2x2 square containing both points is clear of blocking points.

So, if the traveler needs to travel from the lower left to upper right point, here they can move diagonally and only count 2 moves:

..
..

But here, again traveling from the lower left to upper right point, they cannot move diagonally and must count 3 moves:

X.
..

The game always starts with an open path to reach all required destinations.

You, the builder, get to take all of your actions first, and none once you decide you are complete and allow the traveler to begin.  The builder can place additional X points that block travel on them, but they cannot make it impossible to reach any of the required destinations.  The builder cannot place any other points, such as more teleports or waypoints.  The builder cannot remove anything given to them already in the area (other than replace empty points.)  Strategy may include blocking points to force: otherwise out of the way travel; backtracking; and traveling between teleports.  Optimal strategy might include trying to connect the starting, ending, and destination teleport spots in short paths, and forcing a long backtracking path to waypoints.

This is to come up with possible strategies for a tower defense game.  Certain aspects of the game, such as multiple waves, limitations on resources, and attack towers, are ignored to simplify and just focus on the maze-like aspect of the game.


texts: Modelling a queue to a resource pool (children queueing for balls)

texts:
I want to develop an algorithm to serve the queue of children queueing to a basket full of balls of different colour, where each ball can be painted within a known time any colour (of several colours offered) requested by the child, and any child would eventually return a ball back to the basket after he/she finished playing with it. Painting of several different balls can happen in parallel.

To me this looks like a scheduling algorithm to serve a queue of requests to access one resource within a shared fixed-size resource pool, where each resource takes some time to prepare. Here are the requirements it should satisfy:

resources can belong to one of several classes (number of classes is low and fixed), each class takes a different (known and fixed) time to prepare;
each customer only requests one resource of a specified class;
we have visibility to the customers' requests for the entire queue, not just its head, i.e. we can see all requested classes before the customer starts being served;
resource preparation can happen on demand, when customers arrive to the queue, as well as in advance, when we see the growing queue and want to "guess" what kind of resource future customers would want;
the maximum number of resource preparation activities we can run in parallel is the same as the pool size;
we want to maximise the queue throughput.

On the first glance, this looks like something we can address using the queuing theory for queues with multiple servers (due to our capacity to prepare several resources in parallel) and work-independent service times. The difference I see here is that each customer eventually returns resource it has obtained from the pool back to the pool. Returned resource can either:

be immediately served to a waiting customer, if the class of resource is what a waiting customer wants; or
be placed back to the pool (hoping we would soon get a customer that would want that resource class), therefore reducing pool's capacity for resources of other classes; or
be converted into another class: this is possible and takes same time it would take to prepare resource of that other class.

If we would know the distribution of time it takes each customer to return its resource back to the pool, can we still model this as a queue with multiple servers? How would this affect the distribution of the serving time? Or maybe there's another model describing what I want? Any help or pointers would be appreciated.


texts: How can I implement locking a range of values in a sorted sequence?

texts:
I am trying to write a general purpose locking algorithm which allows me to lock a range of contiguous values in a sorted array. To start with, these could be exclusive locks - so two concurrent locks must be non-overlapping. What could be a good, scalable algorithm to do this? (Scalable ~ concurrent)

A specific example could be locking a range of contiguous bytes in a file for writing.

Concretely:
Let's say {a_i} is a valid sequence, for i = 0 through N-1, such that:

a_j < a_k for all j, k such that 0 <= j < k < N.
lock(a_j, a_k) locks all elements from a_j through a_k.
While the above lock is held, another request lock(a_x, a_y) will succeed only if either a_x > a_k, or else a_y < a_j.


texts: Time complexity of obtaining the set of distinct elements in a sequence?

texts:
Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known about the worst-case time complexity of producing a sequence of all distinct elements in $s$, in any order?

By randomized hashing, one can do this in expected $O(n)$ time. On the upper bound side, one may sort the elements, then produce the output in a single pass by only copying elements which differ from their predecessors to the output - for a total time of $O(n \log(n))$.

But can one do better than $O(n  \log(n) )$ deterministically?

Note: This is sort-of a "remove duplicates" problem, but since the order is not preserved I'm not sure it should be called that.


texts:
I am wondering if there are any results for the following max-min assignment problem:
Given $n$ machines $C = \{C_1, C_2, \dots, n\}$ with the $k$-th machine has power $C_k$. There are $m$ tasks $T = \{T_1, T_2, \dots, T_m\}$. Each machine can cover a subset of the tasks in $T$. Now we assign each task to a machine that can cover it. The set of tasks assigned to the $k$-th machine is $\mathit{CT}(k)$. If the $j$-th task is assigned to the $k$-th machine, its received power is $C_k/|\mathit{CT}(k)|$. The question is: how to assign each task to a machine that can cover it, such that the minimum received power of all tasks are maximized?


texts: An efficient data structure supporting Insert, Delete, and MostFrequent

texts:
Assume that we have a set $D$ and each member of $D$ is a data and key pair. We want a data structure that would support the following operations:

Insert $(d,k)$ into $D$,
Delete member $e$, (no need to search to find $e$, e.g. $e$ points to a member in $D$),
MostFrequent, which returns a member $e \in D$ such that $e.key$ is one of the most frequent keys in $D$ (note that the most frequent key doesn't need to be unique).

What would be an efficient implementation of this data structure?

My solution is a heap for the keys and their frequencies prioritized by the frequencies plus a hash table where the hash function maps members with the same key to the same slot in the hash table (with pointers from each part to the other).

This can give $\Theta(\lg n)$ for the first two operations and $\Theta(1)$ for the third (worst case running time).

I am wondering if there is more efficient solution? (or a simpler solution with the same efficiency?)


texts: Any problem solved by a finite automaton is in P

texts:
After my Theory of Computation class today this question popped in my mind: If a problem can be solved by a finite automaton, this problem belongs to P.

I think its true, since automata recognize very simple languages, therefore all these languages would have polynomial algorithms to solve them. Thus, is it true that any problem solved by a finite automaton is in P?


texts: Algorithm to find repeated patterns in a large string

texts:
For optimization purposes I'm trying to analyze a large list of executed program commands to find chunks of commands that are executed over and over again. This problem is similar to searching repeated substrings in a string. However, in my case I'm not looking for the longest substrings but rather smaller substrings that occur very often.

For example, say each command is represented by a letter, then a program might look like xabca yabca xabca yabca. If we are looking for the longest repeated substrings, the best result is xabca yabca. A "better" result would be abca, though. While being shorter, it occurs more often in the string. a occurs even more often on its own, but it would be considered a too short match. So an algorithm should be parameterizable by a minimum and maximum chunk length.

Things I have tried so far:

I played with suffix trees to find the longest repeated substrings that occur at least k times. While that is simple to implement, it doesn't work well in my use case, because also overlapping substrings are found. Trying to remove those wasn't very successful either. The approach mentioned in this post either gave wrong or incomplete results (or I misunderstood the approach), and it also doesn't seem to be customizable. Suffix trees still seem the most promissing approach to me. Perhaps someone has an idea how to include the minumim/maximum chunk lengths into the search here?

EDIT: I finally found a working algorithm for the longest non-overlapping repeated substring, explained here. My current implementation works fine for smaller inputs but has an excessive memory consumption for inputs larger than 10 MB (which shouldn't be a problem of the algorithm per se).
Another attempt was using the substring table that is created for the LZW compression algorithm. The problem with this approach is that is doesn't find repeated chunks that occur early and it also creates longer and longer table entries the farer it processes the input (which makes sense for compression but not in my use case).
My best solution so far is the brute-force approach, i.e. building a dictionary of every possible substring and counting how often it occurs in the input. However, this is slow for large inputs and has a huge memory consumption.
Another idea was searching for single commands that occur most frequently, and then somehow inspecting the local environments of those commands for repeated patterns. I didn't come up with a good algorithm here, though.

What else algorithms are there that could be useful in this scenario? What I'm looking for is not necessarily the best match but a good heuristics. My input data is pretty big, strings up to a length of about 100MB; the chunk sizes will usually be in the range from 10 to 50.


texts: partial (and non deterministic) functions in dependently typed lambda calculus

texts:
A partial function is one, that that is only defined on a part of its domain.
Haskell gives examples: https://wiki.haskell.org/Partial_functions

My end goal is to express types

$$
\prod_{D:\mathcal{U}} D
\qquad\qquad\qquad\qquad
\prod_{\mathcal{A}:\mathfrak{A}} \mathcal{L}(\mathcal{A})
$$

The first type should simply represent sort of (polymorphic) choice functions which accecpt a type and return an element of that Type.
The second is assuming, that I can express the Type of Automata $\mathfrak{A}$
as well as the language $\mathcal{L}(\mathcal{A})$ accepted by automaton $\mathcal{A}$. Given an Automaton a function with the given pitype should Select a word accepted by it.

As far as I understand, in a basic dependently typed lambda calculus, both types suffer from the same problem:
Their elements can never be introduced. Neither is it possible to select an element from the type $\bot$ nor select a word accepted by an automaton that doesn't accept any words.

I was wondering, if partial functions may be a solution to that problem.
But how are partial functions are represented in a typed lambda calculus?
An easy way I can imagine would be to be to create expressions, that allow the introduction of partial functions, such that there simply are no computation rules for undefined inputs.

So my questions are:

Does that make any sence, and is it common to solve this kind of problem that way? Is there good literature?
If the approach seems legit, is it possible to distinguish partial function types $A \rightharpoonup B$ from regular ones $A \to B$?

Note on the purpose:
To be honest, I haven't formalized automata in any calculus, since for now I mostly would like to steal the concept and notation of dependent types and use them in my work to get across a concept.
But if what i will do isn't completely bogus, it would maybe at least leave open a possibility to formalize things later.

A choice function of type $\prod_{D:\mathcal{U}} D$ is meant to represent user input - which should be non deterministic .. so there would also be no congruence)

Bonus question: Can non-deterministic functions be represented in a calculus such that this may be expressed?


texts: Is there a term for the inverse of a fixed-point operator?

texts:
When working with recursion it is often useful to find the least or greatest fixed points of a morphism, often using a fixed-point combinator. When working with recursion schemes, the inverse operation — finding a morphism for which a value is a fixed point — is also very useful, in which case the operation is sometimes called parameterizing and its result sometimes called a pattern functor or base functor.
Is there a more general term for this inverse fixed-point operation or its resulting morphism?


texts: Recursive language subtracted from recursively enumerable language

texts:
This is a homework problem but I am awfully confused. The problem reads as follows:

If $L_1$ is recursively enumerable but not recursive, and $L_2$ is recursive, then which of the following is the strongest true statement about the set difference $L_1 - L_2$?

a. It must be recursively enumerable and not recursive.

b. It might be neither recursively enumerable nor recursive.

c. It must be recursively enumerable and it might be recursive.

d. It must be recursive.

I understand exactly what a recursive language and recursively enumerable languages are. A recursive language is one for which there exists a Turing machine which halts and decides whether the string is in the language for all strings of the alphabet. A recursively enumerable language is one for which there exists a Turing machine which halts and accepts if the string is in the language, but may halt and reject or not halt for strings that are not on the language.

So an example of a recursively enumerable language would be all C programs which do not contain an infinite loop (since we obviously won't halt if the program does). I am a tad bit confused on finding an example of a recursive language.

So subtracting a recursive language from a recursively enumerable language means that, if I try to think this through, there exists a turing machine which may halt and accept all strings in the language, and removing a recursive language only means we remove some strings which would be halted on and accepted.

So I am leaning towards c, but I am very fuzzy. Any pointers?


texts: Calculating the Complexity of a Two Part Algorithm

texts:
This is in relation to this post I made. I eventually solved this by the following approach:

Take the un-ordered file with all the purchasing data and use the UNIX sort utility to order the file on the customer identifier. Since the file can be 500 million lines (and grows over time) I used the -T option and directed the utility to use my hard drive to carry out it's sorting computation. The sort utility uses external sort to do the sorting.
I created a program which took this ordered file and in one pass computed the required values (a single for-loop, no nested for-loops)

Step 2 is O(n) clearly. But what about Step 1? What is the complexity here and more to the point of the question, what is the overall complexity of this two-stage solution?


texts: Using Little's law to find the average N of customers

texts:
I'm trying to understand Little's law and can't seem to get past this scenario:

Let's say people arrive at the register at 12 per hour. It takes 10 minutes (1/6 of an hour) to service each one of them. The law says that the long-term average number of customers is 12 * 1/6 = 2. After the first hour, my assumption is that there will be 6 customers not serviced. Then after the second hour, there will be 6 more. Why is the long-term average 2 and not the storeCapacity?

Is my usage of the law wrong because I'm not talking about a stable system?


texts:
I'm a Computer Science student and am currently enrolled in System Simulation & Modelling course. It involves dealing with everyday systems around us and simulating them in different scenarios by generating random numbers in different distributional curves, like IID, Gaussian etc. for instance. I've been working on the boids project and a question just struck me that what exactly "random" really is? I mean, for instance, every random number that we generate, even in our programming languages like via the Math.random() method in Java, essentially is generated following an "algorithm".

How do we really know that a sequence of numbers that we produce is in fact, random and would it help us, to simulate a certain model as accurately as possible?


texts: Should a math major who wants to get into a PhD program in AI take CS classes that are unrelated to AI research?

texts:
I am a 2nd year math major who wants to do a PhD in AI. I already have a little background in programming and CS. I have some experience in game design, app development and computer security. I wouldn't call myself an expert, but I am comfortable with C, C++, Python, Javascript C#, Java and Assembly and have written and sold a couple of commercial software to businesses before. I am also somewhat familiar with amortized analysis, data structures, algorithms and proofs of correctness. My question is, do I still have to take introductory classes in order to prove to graduate schools that I know programming or is it okay if I only take classes related to AI research like algorithms, machine learning and introduction to artifical intelligence? Also, do I need to take "engineering" type classes like digital design, operating systems, databases etc. that are normally required from computer science students but not related to AI research?
Thanks in advance for taking the time to answer these questions.


texts:
As a software engineer, I write a lot of code for industrial products. Relatively complicated stuff with classes, threads, some design efforts, but also some compromises for performance. I do a lot of testing, and I am tired of testing, so I got interested in formal proof tools, such as Coq, Isabelle... Could I use one of these to formally prove that my code is bug-free and be done with it? - but each time I check out one of these tools, I walk away unconvinced that they are usable for everyday software engineering. Now, that could only be me, and I am looking for pointers/opinions/ideas about that :-)

Specifically, I get the impression that to make one of these tools work for me would require a huge investment to properly define to the prover the objects, methods... of the program under consideration. I then wonder if the prover wouldn't just run out of steam given the size of everything it would have to deal with. Or maybe I would have to get rid of side-effects (those prover tools seem to do really well with declarative languages), and I wonder if that would result in "proven code" that could not be used because it would not be fast or small enough. Also, I don't have the luxury of changing the language I work with, it needs to be Java or C++: I can't tell my boss I'm going to code in OXXXml from now on, because it's the only language in which I can prove the correctness of the code...

Could someone with more experience of formal proof tools comment? Again - I would LOVE to use a formal prover tool, I think they are great, but I have the impression they are in an ivory tower that I can't reach from the lowly ditch of Java/C++... (PS: I also LOVE Haskell, OCaml... don't get the wrong idea: I am a fan of declarative languages and formal proof, I am just trying to see how I could realistically make that useful to software engineering)

Update: Since this is fairly broad, let's try the following more specific questions: 1) are there examples of using provers to prove correctness of industrial Java/C++ programs? 2) Would Coq be suitable for that task? 3) If Coq is suitable, should I write the program in Coq first, then generate C++/Java from Coq? 4) Could this approach handle  threading and performance optimizations?


texts: Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype?

texts:
Let the following datatype be defined:

 data T = A | B T | C T T

That is, B, B T, B (B T), C A A, C (B T) A and so on all are members of T. Now, suppose we define two functions that operate on that type:

f :: T -> T
f A = A
f (B x) = B (B (f x))

g :: T -> T
g A = A
g (B x) = B (B (B (g x)))

There are restrictions on the definition of f and g: first, recursive calls can only be applied directly to a subterm of one of the inputs (guaranteeing termination), and second, they can't use any datatype other than T on their bodies (consider T is the only existing type). In this case, we know that the following function:

h :: T -> T
h A = A
h (B x) = B (B (B (B (B (B (h x))))))

works as the composition f . g. My question is, is it possible/decidable to find the composition of f and g in this form - that is, without any reference to f and g themselves? What is the name of the problem I am trying to solve?


texts: Why does it seem as if I can apply the Pumping lemma to a language that is regular?

texts:
We learn about the Pumping Lemma at the class and I tried to make few examples to understand it...

There I make this example:
Let's say: $L=\{w\in L|w=(0+1)^*1\}$ - i.e. - L is the language of all the words that finish with $1$. (The language is regular of course).

Now, I can take the word: $w=0^{n-1} 1$. $w\in L$ and $|w|\ge n$.
I can take: $u=0^{n-1},v=1,z=\varepsilon$.
$|uv|\le n$ and $|v|>0$, but:
$uv^0z\notin L$ because $uv^0z$ ends with $0$...

What I miss here?
I'd like to understand more where is my mistake...


texts:
I have a grammer with the following productions,
S -> aA | bC | b
A -> aS | bB
B -> aC | bA | a
C -> aB | bS

I have to construct regular expression for it. I derived words for this language and which are

b, aab, aba, baa, bbb, aaaab, aaaba, aabbb, abaaa, baaaa, ...

So after I deriving the words I concluded that it's a language of strings having odd number of b and having odd length.
Can you please help me to construct regular expression for it.
I appreciate your help.


texts:
Here is the game's setup:

  You're given a formula for a binary expression using and or not as the connectives. The connectives are combining many variables for which two players will assign truth values to them in the order specified beforehand.
  For Example:

formula: ((x and y) or ((y and z) or (not y and not z)))
turns: AAB
variables: xyz

  In this example Player A will assign a truth to x first, then y, then
  Player B will assign a truth to z. (The variables will always show up
  in the order of appearance in the formula).
  After all of the truth values are assigned to each variable, the formula is evaluated and the truth is returned and a winner is declared. Player A is trying to make it False and B is trying to make it True.

Assume that the other player and will always choose the best value for his variable on all of his turns. If there is no way for a player to make the formula win during his turn, or if choosing either true or false would lead to winning, then false is returned if it is player A’s turn, and true is returned if it is player B’s turn.

Our job is to give the best move for the current turn given a formula the previous moves and the order of moves for the game.

What would the strategy for approaching something this look like? I know this is a homework question but I've spent a week trying to figure this out without any avail. If you need further clarification about the problem as I know it's a big pill to swallow just comment below I'll be sure to reply.

EDIT: For further clarification, variables can show up more than once in the formula


texts: Polynomial reduction proprietries: reflexive, transitive, but not symmetric

texts:
From theory I know the polynomial reduction is:

reflexive $A ≤ A$ (A Language)
transitive $A ≤ B$ and $ B ≤ C$, then $A ≤ C$ (A, B, and C Languages).

What about symmetric? There is an example with two language $L_1$ and $L_2$ to proof the polynomial reduction is not symmetric? i.e. $L_1 ≤ L_2$ but not $L_2 ≤ L_1$.


texts: Understanding simulated annealing information theoretically

texts:
So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's stationary distribution is the distribution produced by normalizing some function. It's a small leap to realize that you can use this to optimize lots of things and you can even keep rejections that happen to be the minimum you've found so far. But further more you could also reshape the cost function so that it rewards the optimum with much higher probability than anything else (say by exponentiation or squaring the function or something). This has the effect of lowering the entropy of the normalized distribution. If we reshape the target distribution too much though our mixing times could be quite bad. We can solve this by gradually reshaping the target distribution to a low entropy distribution however. Further more higher entropy target distributions should (I think? A proof would be appreciated) have lower mixing times so if our actual target function has low entropy and long mixing times we can fix that. After one researches this line of thinking it quickly becomes clear that this is simulated annealing from a different angle than its generally presented.

The notion of entropy used in physics is deeply connected (or so I'm told) to the notion of entropy used in information theory (which is why Shannon named it as such). The physical notion of entropy is deeply connected to temperature. I've never taken thermodynamics so I don't really understand the bridge between information theoretical entropy, and temperature (which has physical entropy in the middle as the bridge).

Can this link be explained? Given a probability distribution can we define the "temperature" of the distribution? Is there an information theoretical way to define temperature? Perhaps only a subset of distributions have a temperature but we can generate probability distributions that correspond to a given temperature? I'm trying to understand the notion of temperature used in simulated annealing without learning about thermodynamics.

To give a better example of what I'm trying to ask I'll ask by analogy. Understanding what a quantum circuit is doesn't require understanding much of anything about quantum physics for a computer scientist. What's the equivalent understanding of temperature for a computer scientist that knows a bit about information theory?


texts: Enumerate all pairs, in order of increasing distance, efficiently

texts:
Given $n$ points in 2D, e.g., $p_1,p_2,....,p_n$, there are $n^2$ possible pairs of points.  I want to output the list of $n^2$ pairs, but sorted according to their distance (e.g., the pair of two points that are closest is the first pair in the output, and so on).

Is there an algorithm to do this with running time better than $O(n^2 \log n)$?  If there was no metric property and the "distance" of each pair of points was unrelated to all other distances, the lower bound would be $\Omega(n^2 \log n^2)$ based on the lower bound for sorting $n^2$ values, but perhaps we can use the properties of the Euclidean distance to do better?


texts: Is at least one of L and L complement Turing recognizable

texts:
Let the alphabet be {0,1}. Is it true that for every language over this alphabet at least
one of L and L_complement is Turing-recognizable


texts: Context Free Grammer and PDA (Palindrome but without characters repeating in a row)

texts:
So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says

"L contains palindromes that don’t ever have the same character occur twice in a row."

Let $\Sigma = \{a, b, c\}$.

Let $L = \{w \in \Sigma^∗| w = w_1w_2\cdots w_n \mbox{ is a palindrome and } w_i \neq w_{i+1} \forall 0 \le i\lt n\}$.

In other words, $L$ contains palindromes that don’t ever have the same character occur twice in a row.

In the second part can someone guide me how to make it's PDA or give an idea?


texts:
Actually it differs from CPU to CPU but it is possible to choose a mainstream CPU technology used in moderate servers or home computers.

How many clock cycles it takes to read a file of 50KB from Ethernet socket and then resend this file to another IP address without saving the file to disk? I assume this operation can be done on RAM. If not, how many clock cycles required if a copy of this 50Kb file is to be stored into the disk (7200 rpm)?

Thank you.


texts:
If $S_1,S_2$ are set of strings, then $S_1S_2 = \{s_1s_2|s_1\in S_1, s_2\in S_2\}$. $S^0=\{\epsilon\}$, $\epsilon$ is the empty string. $S^n = S^{n-1}S$.

Two related problems about represent string as concatenation of other strings.

Given a finite set $S$ of strings, how to decide if there exist a string can be written as concatenations of elements in $S$ in two different ways?
Given a finite set $S$ of strings and $n$, how can one compute the smallest set of strings $T$, such that $S\subset T^n$?

(Bonus: what about infinite $S$, at least when it's regular? For the second problem when $S$ is infinite, we might ask to find a minimal $T$ under set inclusion.)


texts:
Let $F$ be a finite set of real numbers say $\{w_1,\dots,w_k\}$.

Let $G=(V,E)$ be an undirected connected graph and let $w\colon E\to F$ be a weight function.

Describe a linear time algorithm that will find a Minimum spanning tree in $G$.

Assume that $|V|\gg k$, i.e. the number of vertices is much larger than k.

I know that in such a case we can sort the edges in linear time and then use Kruskal's algorithm, but that will be slightly worse than linear time — $O(|E|\alpha(|V|))$.

I have heard about an approach that uses $|F|$ queue's but I couldn't figure it out, please help.


texts: Prove that a set A is semi-decidable if and only if there is a polynomial time relation R(x,y)

texts:
I know if there is a decidable relation R(x,y) for x in A, then A is semi-decidable. But how can I prove the relation is polynomial time?

For R(x,y), x is  where M is a TM, y is the accepting configuration of M. Is this a polynomial-time relation?


texts:
Let L is a regular language then is

L' = {x$_2$x$_1$| x$_1$x$_2$ ∈ L}

regular?

Thus x$_1$x$_2$ is essentially concatenation of two strings, but can reverse concatenation of same two strings yield regular language?


texts: NP completeness proof of a spanning tree problem

texts:
I am looking for some hints in a question asked by my instructor.

So I just figured out this decision problem is $\sf{NP\text{-}complete}$:

In a graph $G$, is there a spanning tree in $G$ that contain an exact set of $S=\{x_1, x_2,\ldots, x_n\}$ as leafs. I figured out we can prove that it is $\sf{NP\text{-}complete}$ by reducing Hamiltonian path to this decisions problem.

But my instructor also asked us in class:

  would it also be $\sf{NP\text{-}complete}$ if instead of "exact set of $S$", we do

  "include the whole set of $S$ and possibly other leafs" or
     "subset of $S$"

I think "subset of S" would be $\sf{NP\text{-}complete}$, but I just can't prove it, I don't know what problem I can reduce it to this. As for "include the set of $S$..." I think it can be solved in polynomial time.


texts: Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$?

texts: I wonder if there is a simple example of sets $A$ and $B$ such that $A$ is Turing-reductible to $B$ but not many-to-one reductible to $B$.


texts: What specifically makes quantum computers useful?

texts:
I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic.

That seems to be what people point to as being what makes quantum computers special or useful.

However after you have processed the superpositional inputs, you have a superpositional result, of which you can only ask a single question and it collapses into a single value.  I also know that it isn't (currently?) possible to clone the superpositional state, so you are stuck with getting an answer to that one question.

In both cases, it looks like that multi processing ability really hasn't gotten you anything since it's effectively as if only one state was processed.

Am i misinterpreting things, or does the real usefulness of quantum computing come from something else?

Can anyone explain what that something else is?