texts: Developing invariants for comparing two strings

texts:
The following algorithm is supposed to compare two strings $S_1$ and $S_2$ ("/\" for empty string):

X = S1
Y = S2

E = true
// (1)
while X != /\ and Y != /\ and E == true
  if head(X) == head(Y)
    X = tail(X)
    Y = tail(Y)
  else
    E = false
// (2)
if !(X == /\ and Y == /\)
  E = false
  // (3) S1 != S2 \land E = false
// (4) S1 = S2 <=> E = true
return E

I want to develop invariants at points (1) and (2).

The invariant at (1) I choose is $$S_1 = S_2 \iff X = Y \land E = true.$$

From it, I can derive an invariant at (2):

$$(S_1 = S_2 \iff X = Y \land E = true) \land \lnot(X \neq \Lambda \land Y \neq \Lambda \land E = true).$$

Then I tried to simplify the formula:

$$(S_1 = S_2 \iff X = Y \land E = true) \land (X = \Lambda \lor Y = \Lambda \lor E = false)\\
\equiv
\big((S_1 = S_2 \iff X = Y \land E = true) \land (X = \Lambda)\big) \lor \\ \big((S_1 = S_2 \iff X = Y \land E = true) \land (Y = \Lambda)\big) \lor \\ \big((S_1 = S_2 \iff X = Y \land E = true) \land (E = false)\big) \\
\equiv
(S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true) \lor
\\ (S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true) \lor
\\ \big((S_1 = S_2 \iff X = Y \land E = true) \land (E = false)\big)\\
\equiv
\big(S_1 = S_2 \iff (X = \Lambda \land Y = \Lambda) \land (E = true)\big) \lor \\ \big((S_1 = S_2 \iff X = Y \land E = true) \land (E = false)\big)$$

My problems are

Is the derivation above correct? If so, how to further simplify this formula? In particular, how to deal with the second disjunction? Is it simply $S_1 \neq S_2 \land E = false$?
How does the invariant at (3) and (4) follow from the one at (2)?
Can we obtain an invariant at (2) in a single conjunct instead of multiple disjuncts?


texts: Search for minimum in an array of $k$ monotonic subarrays

texts:
Let $A$ be an array of totally ordered elements. A subarray $A[i..j]$ is decreasing if $A[k]\geq A[k+1]$ for all $i \leq k < j$. It is increasing if $A[k]\leq A[k+1]$ for all $i \leq k < j$. It is monotonic if it's either decreasing or increasing.

We call an array is $k$ monotonic if the array can be partitioned into $k$ monotonic subarrays.

  Given $A$ a $k$ monotonic array of length $n$, and the value $k$, find the
  minimum value in the array.

How many comparisons do we need?

If we let $m$ be the maximum number of times a value occurs in $A$, here are some known cases:

$k=1$, then the array is sorted, the minimum is at either end, a $O(1)$ solution.

$k=2$, then we could solve it in $O(m+ \log \frac{n}{m})$, by take the min of two cases.

First decrease, then increase, use a $O(m+ \log \frac{n}{m})$ solution. Basically do ternary search unless one find a large segment of equal values, which turns into linear search.
First increase, then decrease, just check the boundary values.

$k=n$, then a $O(n)$ time linear search is the best possible.

I believe a $\Omega(m+k \log \frac{n}{k})$ lower bound exists, since even if we are given position for $k/2$ partitions of first decreasing then increasing subarrays, $A_1,\ldots,A_{k/2}$, we still need to spend $O(m_i+\log \frac{|A_i|}{m_i})$ time to search for the minima in each one of them, where $m_i$ is the max number of times a value can appear in $A_i$.


texts:
From http://en.wikipedia.org/wiki/Parse_tree

A concrete syntax tree or parse tree or parsing tree[1] or derivation
tree is an ordered, rooted tree that represents the syntactic
structure of a string according to some context-free grammar.
Parse
trees are usually constructed according to one of two competing
relations, either in terms of the constituency relation of
constituency grammars (= phrase structure grammars) or in terms of the
dependency relation of dependency grammars.

Are constituency grammars and   dependency grammars two different
types of context free grammars?

I went through the wikipedia articles for constituency grammars and
for dependency grammars, but they seem to discuss only for natural
languages.
From the perspective of formal language and grammars, is it correct
that constituency grammars and   dependency grammars seem to be
about semantics, which is not just syntax/formal any more?

Thanks.


texts: What is the time complexity of this Factorization program?

texts:
input: n-bit integer X

output: list of prime factors and their multiplicity

acc = X

for i = 2 ... sqrt( X )

--count = 0

--while acc % i == 0

------acc = acc / i

------count = count + 1

--if count > 0

------print i (count)

I know that for the worst case, a n-bit integer is 2^n maximum.

So the time complexity for for i = 2 ... sqrt( X ) is 2^(n/2)-1

Now I'm really confused with the time complexity of while acc % i == 0

For the worst case, let's say that the n-bit number X is a prime. Then the while loop will not be executed at all. How can I define its time-complexity?

How can I find the Big-O of this algorithm? Is iit O(2^n) or O(2^(n/2))


texts: Non-recursive (iterative) DFS with $O(n)$ size stack

texts:
I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case.

I was wondering if there is an iterative implementation of DFS that requires an $O(n)$ size stack instead of heavy $O(n+m)$ stack. I know that this is a worst case analysis, but I am concerned with this and want this to be really bounded.

Just as a reference, I am copying the algorithm from this solution, where vertices can be pushed into stack more than once and in the worst case, the stack size can be $O(n+m)$:

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)


texts: The relationship between degree of vertex and size of dominating set

texts: I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has degree $\ge n^k \,(k< 1)$, is it possible to bound the size of dominating set, i.e $O(n^k)$? Could anyone point me out any materials/papers/books related to this problem?


texts: How many languages exist over the following alphabets?

texts:
(a) We have alphabet $\Sigma=\lbrace 1 \rbrace$, $\Sigma=\lbrace a,b \rbrace$ and (b) also an alphabet with size $k$ and words with length $n$.

For the first two alphabets in (a), we know that there are countably infinite words:
$$|\Sigma| = |\mathbb{N}|$$

For the alphabet in (b) we know we have $k^n$ number of words.

Now I need to find the number of languages that exist for the symbol set $(a)$ and $(b)$.

I think the number of alphabets is also countably infinite, so it has the same size as the power set of $\Sigma$ which has a cardinality $|\Sigma| = |\mathbb{N}|$, therefore there are $2^{|\mathbb{ℕ}|}$ languages.

Now my question is, does this $k^n$ have a role in this $2^{|\mathbb{ℕ}|}$; does it change anything?


texts: Algorithm for commonalities across related objects

texts:
I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application.

The problem is give the data below (two columns) find those ids where the linkedId matches entirely:

Input

id  linkedId
1   103
2   107
1   107
2   103
4   64
6   120
7   107
8   180
7   64
9   129

Expected output
[1,2] as the linkedIds match entirely for the two ids

As I look at the data, I would envisage a graph of some description so that I can establish the various links between the ids and linkedIds but I am at a loss as to how to approach this.

I do not want a solution but more guiding in the right direction.

Thanks


texts: Decidability of {(M,w); M terminates on input w and tape of M is empty after computation}

texts:
I am currently trying to prove whether the above language is decidable, partially decidable or fully undecidable. I am certain that this language is partially decidable and reducible to the halting problem. However, I am having trouble actually proving it.

Can anyone assist me with constructing the TM that decides this HALT variant?

What I'm thinking is creating a program that takes M and:

if M terminates on w and tape is empty, accept
if M terminates on w and tape is not empty, reject
if M does not terminate on w, reject


texts: Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

texts:
Let $T : \mathbb N \to \mathbb N$ be some computable function. Then by $\mathcal C_T$ we denote the class of languages decidable by a deterministic Turing machine in at most $T(|w|)$ steps for an input $w$.
In On the Computational Complexity of Algorithms by J.Hartmanis and R.E. Stearns it is stated that $\mathcal C_T$ is recursively enumerable (they consider a notion of computable sequences, but this is the same as a $\{0,1,\}$-sequence could be considered a subset of $\mathbb N$, and going from to $\mathbb N$ to $\Sigma^*$ does not change anything) and their proof goes by enumerating all machines, and modifying them in order to stop after $T(|w|)$ moves and print zero (this used the computability of $T$). By this procedure for each element in $\mathcal C_T$ some machine is enumerated for it.

But I noticed that also the complement of $C_T$ is recursively enumerable. A machine to accept this set (and do not halt for elements not in the set) could operate according to the following scheme:

Given a Turing machine $M$ as input, we want to know if it halts in at most $T(n)$ steps on each input. Let $\Sigma^{\ast} = \{w_1, w_2, w_3, \ldots \}$
and $c : \mathbb N \to \mathbb N \times \mathbb N$ be some computable pairing function. Then set up a counter $i = 1, 2, 3, \ldots$ and for each $i$ write $(j,k) = c(i)$. Then simulate the machine $M$ on input $w_j$ for $k$ steps, if $k > T(|w_i|)$ and the $M$ has not halted before $k$ steps (i.e. is still in a non-halting state) then accept it.

A turing machine could operate according to the above algorithm and this would give us a machine that takes another machine and accepts presicely those that run on some input of length $n$ more than $T(n)$ steps (and runs forever for all the others).

Hence it accepts the complement of $\mathcal C_T$. So both sets are recursively enumerable, hence the set $C_T$ is recursive/decidable.

Is this reasoning right? I am just wondering why J.Hartmanis and R.E. Stearns have not included this stronger statement in their paper back then...


texts: Minimizing a multiple output circuit with K-maps - and without

texts:
I'm currently working on learning to minimize a circuit which has multiple outputs using K-maps. My universities script seems rather unhelpful to me which left me in a spot where I have a very rough understanding of the matter without actually being able to pull it through.

I currently am supposed to first minimize the functions on their own and then compare that to minimizing them together.

The resulting functions are:

$Fa = (bc)+(bd)+(\neg acd)$

$Fb = (b\neg c\neg d) + (b\neg cd) + (bc\neg d)$

So now I think I am supposed to minimize them together. My approach is to mark the 1s in the maps that are unique to one function red and group them first.
After that, I look at the ones that are shared. I can now group these the same way in both maps.
The groups bordered by yellow are the ones that are shared. So I now created the functions for these two.

$Fa = (bcd) + (\neg acd) + (b\neg cd) + (bc\neg d)$

$Fb = (b\neg c\neg d) + (b\neg cd) + (bc\neg d)$

Here I count that they use two unique AND gates for Fa, one unique AND gate in Fb, two unique AND gates across the two and then one OR gate for each of these two. So all in all, they use 7 gates. This is exactly the same as before I minimized them together, thought the assignment heavily implies that the amount of gates should go down.
I simply cannot figure out what I am doing wrong here.

Furthermore, they tell me to then do this without K-maps, which is a task that I don't even know how to begin working on.


texts: Expected behavior of an algorithm to minimize rankings

texts:
Suppose $n$ students have preferences over $n$ different notebooks. Their preferences can be represented with a square matrix of size $n$ where each column is a different permutation of the vector $[1:n]$, where the first entry in the column represents the most desirable notebook for student 1, and so on. We are interested in the assignment of the notebooks to students that minimizes the sum of rankings.
For example, such allocation in the problem below
  1    2    2
  2    1    3
  3    3    1

would be the allocation (1,2,3) with a ranking sum of 1+1+2=4.
My two questions are the following. If the matrix with preferences is chosen uniformly at random, what is the expected sum of rankings in the assignment that minimizes the sum of rankings?
Second, I can answer this question by running a simulation, but is there a known algorithm that efficiently finds the allocation that minimizes the sum of rankings?
Idea: In the best-case scenario, this sum is $n$. In the worst-case scenario, where each column is identical, the sum is $n(n+1)/2$. The expectation over all possible cases must be somewhere in between.


texts: Mean number of edges between two equal partitions

texts:
For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is  partitioned into two sets each having $n/2$ nodes.

  What is the order of the number of edges that start in one partition and end in the other?

My back of the napkin calculation is half of total number of edges, $nk/4$. If I place randomly an edge it has $1/4$ chance of having both ends in one partition, $1/4$ chance of having both ends in the other partition and $1/2$ chance of having the ends in both. I find it surprising that it could be half.


texts:
Considering the top answer to the question “If xor-ing a one way function with different input, is it still a one way function?”…

  The function is no longer one-way.

  we build a counter example in the following way. Assume $g$ is a one-way function that preserves size, and define $f$  on input $w=bx_1x_2$ in the following way,
  $$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$$
  (assuming $b\in\{0,1\}$ and $|x_1|=|x_2|$.)
  It is easy to see that $f$ is also one-way — to invert it, you need to either invert $g$ on the first half or invert $g$ on the second half.

  Now we show how to invert $h$. Assume you are given $h(u,v)=Z$, we write it as $h(u,v)= z_1z_2$ with $|z_1|=|z_2|=n$.
  Then a possible preimage of $Z$ is
  $$u=0 \,0^n \,\langle g(0^n)\oplus z_2\rangle$$
  $$v=1 \, \langle g(0^n)\oplus z_1\rangle \, 0^n$$

  because $f(u) = g(0^n)\, \langle g(0^n)\oplus z_2\rangle$ and
  $f(v) = \langle g(0^n)\oplus z_1\rangle \, g(0^n)$ thus their XOR gives
  exactly $z_1\,z_2$ as required.

Wouldn't this counter-example imply that we've inverted $f$?

Consider the reduction where we take in $f(x_1)$ and $f(x_2)$: then we could compute $f(x_1) \oplus f(x_2)$, invert this to $x_1x_2$, and then we have inverted $f$ as well.

Is the quoted answer correct? If so, why, given my considerations outlined above?


texts:
I'm given $L_\cap=\{\langle M_1\rangle\#\langle M_2\rangle\mid L(M_1)\cap L(M_2)\neq\emptyset\}$ and $L_U=\{\langle M\rangle\#w|M \text{ accepts } w\}$.

How can I reduce the former to the latter: $L_\cap\leq_RL_U$? My idea was to build a machine $M$ simulating $M_1$ and $M_2$  in series. $M$ accepts a word if and only if both $M_1$ and $M_2$ do. So we feed all words to the machine taking $M$ and words until we find one, otherwise keep running. But the proplem is the machine is not halting guaranteed since it can run forever. What will be the correct solution?


texts: In BSS model in which one is allowed $\{+,-,\times\}$ operations, how is division and square root handled? Is there a typical procedure dealing with these involved situations?


texts: Finding maximum weighted n disjoint cliques

texts:
Maximum weight clique problem has some attention but i could not find any efficient approaches to this problem yet. I acknowledge that it is np-hard, but are there any known approximations?

Given a fixed n and an undirected graph, the problem can be defined as finding n disjoint cliques which maximize the sum of the vertex weights in these cliques. Disjoint cliques can be defined as cliques that do not have any common vertex.

I have taken a look on this dissertation but did not help much.


texts: How does data travel in a butterfly network?

texts:
I'm trying to learn how communication works in a butterfly network.

The following is a butterfly network of order 3. I'm given the following description:

  Each processor is connected to an output switch in rank 0 and to an input switch in rank k (in this case 3). In other words the switch in column j and rank 0 gets its input message from processor j and the switch in column j and rank k delivers its message to processor j. Messages only travel in one direction - towards switches of increasing rank.

I'm having trouble interpreting what it means by the input and output switches. At first I thought the messages were traveling from bottom to top, but the last statement makes it sound like it's traveling from top to bottom. Is the processor j mentioned found on top in rank 0? I'm trying to grasp how messages travel from one processor to another.


texts:
Suppose the function $f(n)$ is defined as the number of $\ast$ printed in the following code

for(int i = 0; i<n; i++) {
    for(int j = i; j<n; j++) {
        for(int k = j + 200; k<2n; k++) {
            for( int r = k^2; r<n; r++) {
                print(*);
            }
        }
    }
}

I suspect the answer is $\Theta(n^{2.5})$, by running the code at $n=5000$ and $n=50000$, but I do not have a rigid proof.

Can anyone enlighten me? Thank you!


texts:
I want to write an algorithm to find whether a directed circuit whose length is odd exists in a strongly connected digraph.

Can anyone help me how to proceed with this problem???


texts: Can we call deterministic equivalent of all NFA to be finite

texts: Finite automata is defined as a simple machine having small memory. A deterministic equivalent of a NFA with n states will have O(2^n) states,so the number of states grow exponentially. So can we always call the deterministic equivalent to be a finite automata just by saying that as n is finite 2^n will also be finite even though the actual memory will be very large or is there some limitation?


texts:
I have some question about DFA Language properties.

Does closure under intersection and complementation imply closure under union?

Does closure under intersection and union imply closure under complementation?

Thank you


texts: Finding the frequency of each unique value of an attribute in a relation (RELATIONAL ALGEBRA)

texts:
I am trying to figure out how I can use aggregate functions to solve this problem. For example if I had the table

enrolled(student-id, course-id)
123 897
123 645
589 452
009 897

If I wanted to find the number of courses each student is enrolled in, how would I go about doing that? I was thinking of using the count function but I don't know how to separate each student-id


texts: Effects of changes in the proof that $A_{\text{TM}}$ is undecidable

texts:
In the proof that $A_{\text{TM}}$ undecidable we use the following machine:

$D =$ On input $\langle M, w \rangle$:

Simulate $M$ on input $w$.
If $M$ ever enters its accept state, accept. If $M$ ever enters its reject state, reject.

But what will happen if change this so that the input is $\langle w \rangle^R$, that is, if we change the first step from what is written to:

Run $H$ on input $\langle M, \langle M \rangle^R \rangle$

Another thing interests me (and unrelated to the previous modification) is what happen if we change the second step to be:

If $H$ accepts, loop. If $H$ rejects, accept.

What I think based on reading the book "Introduction to the Theory of Computation" and notes:

If only the first step changed like is written and input given to machine is $\langle M, \langle M \rangle^R \rangle$ machine can run and do comparison of $M$ on its reverse by the second time it visit the same letter and do comparison. Since $A_{tm}$ can be recognized by Turing machine, main problem of it not be able to decide is because $M$ loop on $w$. But in this case it is decidable because now instead of run on $\langle M, w \rangle$ it run on $\langle M, \langle M \rangle^R \rangle$ and algorithm can know Turing machine not halt on $\langle M, \langle M \rangle^R \rangle$ so it can reject it. because of it the machine is decidable after given change.
Again, second question is on its own as if previous change not occur. This time, i am no sure. in case of $H$ accepting it loops and it seem like infinite loop. In case it rejects it accept? It seem not to be able to decide based on this change so it is still not decidable. It can not know if $M$ halt on given input $w$ because of infinite loop so it can not reject. So after change still not decidable.


texts: error measure (of ML agos) that takes confidence into account

texts: when calculating the error measure such as mean absolute error, we use the real values and the predicted values. Many machine learning algorithms can give a confidence measure of each value being predicted. Is there a standard error or correlation measure that takes this confidence into account, and penalizes high confidence errors more than low confidence ones? I can write such a function - eg: weighted avg(abs(error)) weighted by confidence. But I'm interested in whether such a measure is standard and known to be in use.


texts:
Like the title says. I can't figure out how to prove this.
I think it probably has to do with the polynomial hierarchy collapsing but I'm not sure.


texts: Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?

texts:
Given a sequence $A$ of $N$ distinct integers, does there exist a strategy to get at least one subsequence with size $\geq \lfloor \frac{N}{2} \rfloor$ of the sequence in sorted order in $O(n)$ time?
For example, let's say that $A = [4, 11, 6, 2, 9, 7]$. Then, one of the required sequences can be $[2, 7, 11]$, which is the sorted version of the subsequence $[11, 2, 7]$. Your strategy can give any such subsequence in a sorted order.
Yes, I think that it's 99.99% impossible. But, I don't know for sure. Can anyone show that there cannot exist such a strategy or prove otherwise?


texts: What happens during the DFA reversal construction if the initial state is final?

texts:
The steps in reversal of DFA are :-

Make final state as initial state. If there are more than 1 final state, then make a new start state with epsilon transitions to these states.
Change all initial states to final states
Reverse the direction of edges.

Now what if I have a state which is both initial and final ? Will it be initial or final state in the reversed dfa?


texts: What is a "wasteful" execution? And a "schedule"?

texts:
I'm trying to understand what this text means in my textbook about distributed leader election algorithms, but I can't make any sense of it. Either they didn't explain what was meant, or I missed it somewhere.

In this section, we show that the leader election algorithm of Section 3.3.2 is asymptotically optimal. That is, we show that any algorithm for electing a leader in and asynchronous ring sends at least $\Omega(n\log n)$ messages. The lower bound we prove is for uniform algorithms, namely, algorithms that do not know the size of the ring.
We prove the lower bound for a special variant of the leader election problem, where the elected leader must be the processor with the maximum identifier in the ring; in addition, all the processors must know the identifier of the elected leader. The proof of the lower bound for the more general definition of the leader election problem follows by reduction.
Assume we are given a uniform algorithm $A$ that solves the above variant of the leader election problem. We will show that there exists an admissible execution of $A$ in which $\Omega(n\log n)$ messages are sent. Intuitively, this is done by building a "wasteful" execution of the algorithm for rings of size $n/2$, in which many messages are sent. Then we "paste together" two different rings of size $n/2$ to form a ring of size $n$, in such a way that we can combine the wasteful executions of the smaller rings and force $\Theta(n)$ additional messages to be received.
Although the preceding discussion referred to pasting together exections, we will actually work with schedules. The reason is that executions include configurations, which pin down the number of processors in the ring. We will want to apply the same sequence of events to different rings, with different numbers of processors. Before presenting the details of the lower bound proof, we first define schedules that can be "pasted together".
A schedule $\sigma$ of $A$ for a particular ring is open if there exists an edge $e$ of the ring such that in $\sigma$ no message is delivered over the edge $e$ in either direction; $e$ is an open edge of $\sigma$.

There is lots more, but I don't know if I should type it all out if only for copyright reasons. I hope this is enough to help clarify my question and get an explanation.


texts: Is there a distinction between pointers and references?

texts: If so, what are the similarities and differences between the two? I’ve only worked with properties while programming.


texts: Are LR(k) languages and DCFLs equivalent?

texts:
In the familiar book of Theory of Computation by M. Sipser, the author proved that for endmarked context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ (denoted as LR(k) languages) is the set of deterministic context-free languages (denoted as DCFL).

My question is also about the relation of those two sets, but in the broader field of all context-free languages. Specifically, are LR(k) languages and DCFLs equivalent? And, in which book can I find a proof?

For now, I just have some surrounding facts as followed. Also in the book, the author proved that LR(0) languages strictly belong to DCFLs, and LR(k) languages belong to DCFLs for all $k \in \mathbb{N} \setminus \{0\}$. In addition, it's obvious that LR(a) languages belong to LR(b) languages for all $0 \le a < b$. Recently, I've got an unchecked fact from here: LR(1) languages and DCFLs are equivalent.


texts: What algorithm may be used to solve the re-assembly of shredded papers?

texts:
I was once given this question in an interview:

  Suppose a piece of paper has 80 columns of alphabets with a fixed size font, and now the paper is shredded vertically, into 80 vertical pieces (so each piece can show a series of alphabets going down vertically), and there are 300 pages of such paper shredded total. Assume they are just English words with no proper names (for people / places). Find a method to reassemble all the papers and give the O() complexity time and space.

I proposed a solution where we take one piece of stripe, and go down the row to match for consecutive occurring alphabets, for a proper stripe. So we would build up a dictionary of all English words, for example, for the word Apple, that will mean ap, pp, pl, and le are all valid. And if we go down both stripes, we should expect most (or all) of them match with each other if they were adjacent.

But doing this way, it looks like it would be (180 * 300)! = 24000! (factorial) steps, before we can finish the task? I can only find a complicated paper about re-constructing non-fixed size font paper (and it seemed way too complicated for a 20 minute interview question), and another paper that is not public.  Is there a good solution to this problem?

(Actually, it seems that if it is not fixed size font, it is a easier problem?  Because we can just look at the left and right edge: along the left edge, for example, if there is ink, we call it as 1, and no ink, we call it a 0. Or we can just scan and collect data: from top edge, go down 3.232cm of blank space, and then 0.012cm of ink, and then 0.027cm of blank space, all the way down to the end of paper, and then we can create a signature.  If we do the signature for all 80 x 300 stripes, now we have 48000 signatures. Now we can actually just match the signatures up to tell which strips is adjacent to which stripe. So that would be a linear O(n) solution?)


texts: Neural Networks: Style transfer for audio

texts:
I just found the paper A Neural Algorithm of Artistic Style which seems to be very cool.

It describes a way to combine two images: Use the content of image A and the style of image B to create a new image. This is done with a CNN (e.g. VGG).

As may be seen on the following page it works very well:
https://deepart.io/latest/

I saw that people use CNNs for audio classification (audio -> spectrogram -> CNN -> classification). Does this mean that this style transfer could also be used for audio? E.g. to change a speaker. Did this already do someone? Or are there any problems and reasons why this does not work that easy for audio?

Thank you very much


texts: What are overlay & underlaying topologies in DHT?

texts:
We are covering Distributed Hash Tables in my "Networks" class and one of the subsections is about the improvements that can be made to increase the performance of the chord. Here, the parameter "Stretch" plays an important role.
$$\text{Stretch} = \frac{\text{latency for each lookup on the overlay topology}}{\text{average latency on the underlying topology}} $$
I am a little confused on what is meant by overlay and underlaying toplogy.


texts: the maximum value for which combination of merge sort and insertion sort works more efficiently than standard merge sort?

texts:
I'm totally new in algorithms and I have a hard time studying how to calculate the time complexity of algorithms.

I'm studying Introduction to Algorithms, by Cormen on my own. Iam doing an exercise and I faced a problem that I couldn't solved it. first, the book asks for the worst time complexity of combination of merge sort and insertion sort. I calculated it truly and the answer is O(nk + nlg(n/k)).

second, it says:

  Given that the modified algorithm runs in O(nk + nlg(n/k)) worst-case
  time, what is the largest value of k as a function of n for which the
  modified algorithm has the same running time as standard merge sort,
  in terms of O notation?

this is the part that I have problem. I said the answer may be obtained in this way:

worst time complexity of standard merge sort = worst time complexity of modified merge sort

nlgn = nk + nlog(n/k)
k = 2 ^ k

but this can never happen and my answer is wrong. how should I solve the problem??

Thanks in advance.


texts: Need help reducing 1-in-3-SAT to show a problem is NP-complete

texts:
This is the original problem:

And this is 1-in-3-SAT:

I am using the 1-in-3-SAT problem (Pc) to reduce from, in order to prove that the original problem (P) is NP-complete. I am stuck at finding a transformation T to prove that Pc <= P, such that every instance X of Pc is transformed into an instance T(X) of P, and runs in polynomial time, and that if the answer to X is YES, so is the answer to T(X), and vice-verso. Same for answer NO.

I've found out that if the number of clauses C is more than or equal to the number of variables x, then the answer is always NO.

I'm struggling in how to generate (transform) the string a (b) input) from in the P problem. So far, from the options I've tried, the best one has been that I generate the a string by concatenating once every variable x met in all the clauses, but I managed to crack it (prove it wrong), and I'm simply stuck atm.


texts: How is Vertex Cover reducable to Independent Set using parametrized reduction with parameter k?

texts:
We have the following Lemma and proof:

Lemma 5.5. If $A$ if FPT, then $A\leq_{\mathrm{fpt}}$ Independent Set.
Proof. We reduce $A$ to Independent Set parametrised by $k'$, where $k'$ is the size of a sought independent set. Given an instance $(x,k)$ of $A$,

solve $(x,k)$ in $f(k)\cdot \mathrm{poly}(|x|)$ time, (the running time of this reduction is using the running time of problem $A$)

if $(x,k)$ is a yes-instance, then output a one-vertex graph and $k'=1$.

if $(x,k)$ is a no-instance, then output a one-vertex graph and $k'=2$. (Could this need more time to compute?)

It is clear that the input instance is a yes-instance if and only if the output IS instance is, and $k'\leq k+2$. $\quad\square$

The definition of parameterized reduction is as follows:

Definition 13.1 (Parameterized reduction). Let $A,B\subseteq \Sigma^*\times\mathbb{N}$ be two parameterized problems. A parameterized reduction from $A$ to $B$ is an algorithm that, given an instance $(x,k)$ of $A$, outputs an instance $(x',k')$ of $B$ such that

$(x,k)$ is a yes-instance of $A$ if and only if $(x',k')$ is a yes-instance of $B$,
$k'\leq g(k)$ for some computable function $g$, and
the running time is $f(k)\cdot |x|^{\mathcal{O}(1)}$ for some computable function $f$.

Now it seems from what he did is: if $(x,k)$ is yes-instance, then output a one vertex with $k'=1$, otherwise if $(x,k)$ is no-instance, then output a one vertex with $k'=2$. This makes the first condition of Parameterized reduction true. Now,for second condition, we should say $k' \leq g(k)$ where $g(k)=1$ if we have yes-instance, and $0$ otherwise. The running time would be just the running time of the parameterized algorithm. Done.
My question is that when I want to do a reduction, I should take the input of $A$ (like vertex cover) and turn it to input of IS instance. For example assume we have clique of $4$, with $k=3$, the vertex cover algorithm will return a yes-instance, now if we want to turn this instance to IS to make it yes-instance, we need to use $n-k$. But he use different way. Also, when we prove IS to VC using parameterized reduction, it gives us wrong reduction (because of $n-k$ isn't a computable function of $k$). I just want to know here how "VC to IS" using parameterized reduction works.


texts: Convert this language to Context Free Grammar

texts:
I'm having trouble understanding how to convert this language to context free grammar.

$\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$

Part im getting stuck on is how to deal with a and c, whenever a c is added, you must also add an a, but with them at opposite ends of the string how do you properly build grammar for it? Since the below is not possible:

\begin{align}
C &\rightarrow aC \\
C &\rightarrow c
\end{align}

I've read the below post many times and tried to apply it but still not able to get it.

How to prove that a language is context-free?

Someone able to show me how this can be done?


texts: Reference request for coding Knight's Tour

texts:
Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly
good efficiency)?


texts: NPC PROBLEM minimum sum of vertex coloring

texts:
For a graph G and a legal vertex-colouring ψ : V(G)→N of G,

let σψ(G) be the sum of ψ(v),

and set σ(G):=min σψ(G),

where the minimum ranges over all valid vertex colourings of G.

Prove that {(G,k): σ(G)≤ k}∈ NPC.

I thought of reduction from subset-sum but my problem is with the min and not with the sum, I don't understand how to do a reduction to check the minimum.
I got a hint to do a reduction from 3-NAE-SAT but I don't understand how.
would appreciate some help. even some source I can read about this problem if you know about something.


texts: Is rejection sampling the only way to get a truly uniform distribution of random numbers?

texts:
Suppose that we have a random generator that outputs
numbers in the range $[0..R-1]$ with uniform distribution and we
need to generate random numbers in the range $[0..N-1]$
with uniform distribution.

Suppose that $N < R$ and $N$ does not evenly divide $R$;
in order to get a truly uniform distribution we can use the
rejection sampling method:

if $k$ is the greatest integer such that $k N < R$
pick a random number $r$ in $[0..R-1]$
if $r < k N$ then output $r \mod N$, otherwise keep trying with other random numbers r', r", ... until the condition is met

Is rejection sampling the only way to get a truly uniform discrete distribution?

If the answer is yes, why?

Note: if $N > R$ the idea is the same: generate a random number $r'$ in $[0..R^m-1], R^m >= N$, for example $r' = R(...R(R r_1 + r_2)...)+r_m$ where $r_i$ is a random number in the range $[0..R-1]$


texts: Why is left recursion and left factoring no problem in bottom up parsing?

texts:
i am asking myself why is LR and LF no problem in bottom up parsing. I do know that we do right most derivation and so the right most non terminal is getting reduced.
But why is this then a problem in LL(k) parsing?


texts: Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$

texts:
This problem is from an exercise sheet so it would be nice if you could guide me to the solution.
The problem:
For $ k \in \mathbb{N}\setminus\{0\}$ let
$$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$$
be the set of words with have at the k-last Position a 1.
(a) How many Myhill-Nerode-equivalence classes does $L_k$ have? Prove your answer.
(b) Construct an minimal DFA for $L_2$ from the equivalence classes.
(c) How many states does a minimal NFA for $L_k$ have? Prove your answer.
What I have:
a) I am pretty clueless, how to approach this problem. I tried to find classes for $k=1, k=2, k=3$ from which I think the amount as a function of k would be $2^k$. But I don't know how to continue.
b) Is pretty easy in comparision, I just added it for the sake of completeness.
c) I think with a) this would be much easier. Because the minimal amount of states is equivalent to the amount of NM classes. But for that I first need a).
Thank you in advance for any advice!


texts:
So, i faced this question during a pratice quiz
i have no idea why " all of the elements are located contiguously in memory " wrong!!
My logic is that priority queues are made of binary heaps and binary heaps are made of arrays ( according to introduction to algorithms by CLRS ) , so this means that elements are located contiguously in memory is true for PQ since it's true for arrays
so, what am i doing wrong ?!


texts: What is the goal of studying all those NP-complete problems?

texts:
So i'm currently reading a lot of things about graph NP-complete problems, and it seems that the goal of a lot of researchers is to find new results about their complexity, results like "independent set is 1.593 approximable for graphs which doesn't contains K4 K5 P3 as a minor" (this is probably a wrong result i just invented something which looks like a result we could find in a paper), approximation algorithms, parameterized complexity etc ...
But i'm wondering : what really is the goal to study independent set, vertex cover, hamiltonian circuit etc ... ? Do they have real case application ? Is there any software that uses independent set algorithms ?
Or is it only for the theory ? To discover something new in the P vs NP problems ?
To sum up : are NP-complete problems (and i'm particularly interested in NP-complete graph problems) useful in the reality ?
PS : sorry if the title may seem offensive, it is not, i know a lot of searchers study things which does not have much applications in reality, i want to know if it is the case for np-complete problems


texts:
As i passed PHD entrance exam, some days ago, i want to find solutions for challenging problem.

In Bayes network on X={X1,...Xn} each random variable has P parents and Q child's. for Xi we want to find minimum number of variable that Xi independent from other variables. at least, how many variable we need?

i think, we use Markov Blanket for this problem. any solution for this problem?

Regards.


texts: Number of edges in a graph with N vertices and K components

texts:
What is the possible biggest and the smallest number of edges in a graph with N vertices and K components?

I think that the smallest is (N-1)K. The biggest one is NK. Is this correct? I think it also may depend on whether we have and even or an odd number of vertices?


texts: Given a set of random variables $X = \{x_1, x_2, \dots, x_n\}$. If the conditional entropy for all $Y \subset X - \{X_i\}$  where $|Y| \leq 5$. How to approximate conditional entropy when $|Y| = 10$ based on the given knowledge? Is it possible to approximate better than  $H(X_i | X - \{X_i\})$  ?


texts:
I have a weighted graph where each edge is a 1d vector eg if weight going from A to B is 1 then from B to A it is -1. In the graph each cycle should add to zero though sometimes the weights have errors  and in that case a cycle will not add to zero.

So for example if the weight from A to B is 1 and B to C is 1 then for the cycle to sum to zero C to A must be -2 and there is an error if it is anything else. Please note that in general the cycles can involve an arbitrary amount of nodes.

What is the best algorithm for detecting these errors? IE what is the best algorithm for finding all weights that have errors and so are causing the cycles to add to a non zero value?


texts: How can a classifier using Laplacian kernel achieve no error on the input samples?

texts:
If we have a sample dataset $S = \{(x_1, y_i),\dots,(x_n,y_n)\}$ where $y_i = \{0,1\}$, how can we tune $\sigma$ such that there is no error on $S$ from a classifier using the Laplacian kernel?

Laplacian Kernel is

$$
K(x,x') = \exp\left(-\dfrac{\| x - x'\|}{\sigma}\right)
$$

If this is true, does it mean that if we run hard-SVM with the Laplacian kernel and $\sigma$ from the above on $S$, we can find no error separating classifier also?

My solution:

For the no error on Laplacian kernel, my approach was to tune $\sigma$, to show that any polynomial predictor over the original space can be learned by using the Laplacian Kernel. Then show that VC dimension of the class all polynomial predictors is infinite, meaning that any labeling can be classified without any error.

For the hard-SVM, I need to find the supporting vectors using this sigma. If the supporting vectors can be correctly found then its ok.

Is this the right approach, please advise.


texts: Compute the mode of an array concurrently

texts:
As an academic exercise, I have to write a parallel algorithm that given a sorted array of $n$ integers computes the mode (i.e. the item with the highest frequency) efficiently using $p$ processors, where $p \le n$ is a constant.

The model we use to describe these algorithms allows lock/unlock primitives to synchronize concurrent access to shared variables.

We cannot use hash tables. Could anyone share any hint on the optimal algorithm to solve this problem?

Edit: rephrased question according to comments.

Edit 2: adding my solution for feedback.
While trying to solve the exercise I thought of an algorithm in the lines of

Declare two global variables, mode and modeFrequency and initialize them appropriately;
For i where $1 \le i \le p$, invoke a concurrent process on a portion of the array.
In each concurrent process:
3.1.. Find the local mode of the partition;
3.2. Store the local mode and its frequency in two local variables;
3.3. Compare the local mode with the global one:
3.3.1. if the mode is the same, add the local frequency to the global one;
3.3.2. if the local mode is different than the global one and the local frequency is higher than the global one, set the local mode/frequency to the global ones
Return the global mode.

but I am not convinced of the correctness of the algorithm. Please note that I omitted locks/unlocks for brevity. Also, can the way I partition the array make any difference on the correctness of the algorithm?


texts: How do IR researchers evaluate the ranks of documents?

texts:
I am developing a new IR system in a specialized context. I understand that a traditional IR system (like a search engine) should rank documents in terms of their relevance for a query. The most relevant documents should come first and the least relevant (perhaps: least relevant above some threshold) should come last.

I want to evaluate my new IR system. How do researchers evaluate document rank? How do they say that this document is more relevant than that document for some query? The most obvious thing to do would be to manually assign such labels and then check the machine against the hand labels. This seems highly subjective. Maybe there is a better way?

I've read section 15.1 Manning's Foundations of Natural Language Processing but it only talks about evaluating precision and recall -- not evaluating rank. Any suggestions on where to look on evaluating rank?


texts:
I'm an entire outsider to computer science eventhough I've been programming for so many years.

As we know, modern audio-visual media codecs are essentially entropy codings of subjective preceptual information. Well known codecs such as AVC, HEVC, AAC, AC3 are highly efficient at compressing AV data.

So I wonder, what about error resilience? How well does HEVC/H.265 handle erroneous code streams, how does it recover from errors? What design decisions (drop malformed code segment or pass it on ignoring error as if it's correct) have been made by its developers?


texts: Expressing that a function converges to 1 with linear rate using Landau notation

texts:
I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is approximately $1/n$.

Initially, I wrote that the algorithm achieves an approximation of:

$$\Omega(1-1/n)$$

But, now I am not sure this notation is correct: it is just like writing $\Omega(1)$ (the smaller element is swallowed in the larger element, which is 1).

Should I write:

$$1-O(1/n)$$

Or maybe:

$$1-1/\Omega(n)$$

Which of these is the correct notation?


texts: Writing a multitasking operating system for a processor without MMU

texts:
I've been thinking of writing a hobby operating system for some of the ARM processors. There are many popular single-board computers with ARM MPU, so I simply wanted to purchase one of those (choosing one with more open documentation). I was surprised when I found out, that even boards with really enough memory do not have MPUs with Memory Management Unit.

As I've always been working with i386+ processors and never anything else (except for some Microchip PICs), I'm now confused and not sure if one can write a working operating system whose functionality wouldn't be limited when comparing to OSes written for MPUs with MMU.

I could think of few solutions for "replacing" or "simulating" MMU and I've got few questions:

On Intel processors in 16 and 32-bit modes there is a way of using segments and segment selectors to use different blocks of memory by different tasks. That means that I could change memory space by changing contents of segment registers when doing a task switch when on x86.
Are there any general concepts for memory segmentation that could be used on ARM architecture?
By loading a linked object file instead of executable I could use relocations (fix-ups) or position independent code to point tasks on pieces of memory in the same way as if I mapped the memory using paging structures. Would this be effective enough?
I have also read something about Memory Protection Units on ARM processors. Could these be helpful?

Are there any "usual" ways of managing tasks on systems without MMU?


texts: What are functions called that yield the same result when applied to one of their result values

texts:
Suppose one of the following holds for all x, or all y, or all z:

f(f(x)) = f(x)
f(f(y)) = f(y)
f(f(f(z))) = f(f(z)) = f(z)

... how do you call such a function?


texts: From where does the Fetch Unit get its instructions?

texts: In the ARM Architecture pipelining stages, we know that the instructions pass from fetch to decode and so on? But, from where does the fetch unit get the instructions?


texts: Automatic tool for resolving left-recursion within CFG

texts:
Though facing the fear that someone might not like my question but does somebody know a useful tool to either

resolve left recursion or to
simplify

a context-free grammar automatically ?

I need to resolve a rather long chain of left-recursion in my grammar.

So far I've tried this algorithm and this tool. But both are only applicable for smaller grammars and provide practically unusable results (1000's of rules).


texts: Efficient way to check if a graph node's children were visited during traversal

texts:
I have a generic traversal algorithm for graphs:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
    }
}

and I want to make a time-efficient "child head count" for nodes that sets a flag for nodes whenever all their children have been visited:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        set close flag on parent nodes if last child to be visited
    }
}

The best ways that i could think of was to have pointers to "visited" booleans of the node's children and just "and" them up as such:

node1 -> [node2(true), node5(false), node7(true)]

node1.all_children_visited() = false

Or iterate through the parents whenever I visit the node for the first time:

Traversal (container) {
    while (container is not empty ){
        visit container.pop()
        push new nodes
        if first visit {
            for each parent {
                increase count
                if count(parent) = number of children {close(parent)}
            }
            if count(this) = number of children {close(this)}
        }
    }
}

Is there a way to do this with lower than O(n) complexity?


texts: How can I represent a set of graphs for learning purposes?

texts:
I have a network of labelled digraphs and a I need to perform a unsupervised learning algorithm on this data.

I am interested in embedding a network of description logic documents in a vector space using the ideas in the paper Co-embedding Attributed Networks (which is a variational auto-encoder). look at the picture:

The first step is to represent each digraph as a feature vector in a vector space.

I have googled a lot but I haven't found good explanations (I also search for supervised algorithms like support vector machine working on a set of labelled digraphs but google doesn't retrieve good results).

My question is: How can I represent a set of labelled digraphs into a vector for learning purposes? (this representation algorithm must have linear complexity)


texts: Simple question about signed integer multiplication

texts:
If you have a signed integer int x = any
And then state that x < 0
Is the following statement true or false?
((x*2) < 0)

The answer is false, which seems counter intuitive. Is it because X can be any negative value, it can also be a very big negative value which will overflow if multiplied by two.
So if I have the number -30768 1000011111010000
which multiplied by 2 is -61536 11111111111111110000111110100000
But because we only have 16 bits the last 16 are taken resulting in 0000111110100000 which is positive.
Is this the correct explanation? I can't seem to find a good source


texts:
For network packets coming over TCP/IP protocol, have you ever confronted a situation where you need to store those network packets in tabular form similar to how tabular tables in databases? For example, keep the dst IP, dst src, TCP/UDP, payload, etc.?
If you ever find yourself in a situation where you need to store network packets over TCP/IP in tabular form, can you please explain the motivation for that from you own experience?


texts: Finding the cheapest buy order with fixed inflation for each product

texts:
Let's say we have a set of products $M$, a total of $|M|=n$ that we want to buy. However, we can only buy one product at a time, so that we need a total of $n$ time-units to buy all items.

Each product $p\in M$ has a base price $b_p$, as well as an inflation rate $r_p$. At time unit $t$, product $p$ therefore has the price $b_p \cdot {r_p}^t $.
 We can assume $b_p\in \mathbb{R}$, $r_p>1$.

I'm looking for an efficient (i.e. polytime) algorithm that returns the optimal buying order which minimizes the total price.

There's an easier variant of the problem (all $b_p=1$) which can be solved using the greedy algorithm
"Always buy the one product with the highest inflation".

Given that the base prices can be vastly different, this algorithm can't be directly transferred, but knowing that an easier version of the problem had a linear-time solution, this one probably still isn't $\mathsf{NP}$-complete.

If we view every product as a function of time $p_i(t) = b_p \cdot {r_p}^t$, the greedy algorithm above tells us, that if for $t_0$ holds $p_i(t_0) = p_j(t_0)$,  then from the point once $t_0$ has passed we should always pick of $p_i, p_j$ the one with the higher inflation.

I'd be open for both hints and solutions.


texts: How to represent/implement the hypotheses class for a DAG learner

texts:
I am implementing a learner to learn a DAG model $G=\langle V,E\rangle$ where $V$ and $E$ represent both variables and dependencies respectively ( similar to Bayesian networks). Each variable $v\in V$ is associated with possible values (domain) $D_v$ and a function $\theta_v$.

I assume the learner knows the number of variables $n$ (i.e. vertices) and their possible values (domain). The goal is to find $E$ (dependencies) and $\theta_v$ for every variable $v$. I also assume there is a target function $c$ exist (the realizable case).

The hypothesis class is defined as the set of consistent hypotheses i.e. $H=\{h|\ h(x)=c(x)\} \forall x\in S$ where $S$ is set of examples seen so far.

I am trying to find a way to represent my hypotheses class. Initially, before receiving any example, it contains:

all possible DAGs over $V$.
all different combinations of $E$ as long as its acyclic.
For every Graph $G$ generated from (1) and (2),all different function values over $G$.

Beside my naive representation, I do not know how to compute (1) precisely. To put my question in another way, how to represent the hypotheses class over Bayesian networks?


texts: What is at least weakly NP-hard problem?

texts: It is known that some problem P is at least weakly NP-hard. What does at least part of the statement mean? Is it possible that problem P is strongly NP-hard? Is this a stronger, i.e. more precise, claim? Can we prove the problem is strongly NP-hard with polynomial time reduction?


texts:
From a youtube video, this PDA can recognize any palindrom.

However, from wikipedia, here is one of the criteria of PDAs.
We clearly see that the transition function can't take an empty stack as input, as epsilon is not a part of Gamma. (but it can use it as output, and also epsilon input is allowed as we see in the union).
But in the video, all transitions from q2 use empty stack as input stack character. What's wrong ?


texts: Could you please resolve a confusion with Schaefer's theorem for me? Namely, why does it not imply many problems in P are NP-complete? For example, primality testing surely cannot be reduced to one of the six classes in the theorem, so why does that not imply it's NP-complete?


texts: Asymptotic runtime for querying an interval tree

texts:
Suppose that we have an array of size n and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have the ranges [0], [1], [2], [3], ... , [n], and merging two of them together we end up having the root node holding the range [0, n]. For example we have the following interval tree for an array of size 6.

The total amount of nodes is O(n).

I'm trying to understand what's the maximum posible  root - internal node paths that we need to make in order to answer a query on any range. I know that the total amount of nodes that we are going to visit for any query is in the order of log n but I can't see why, which is the reason why I'm asking this question.

For example in the picture above, for the query [1, 4] we will do the following visits:

[0,5] => [0,2] => [0,1] => [1] => [0,1] => [0,2] => [2] => [0,2] => [0,5] => [3,5] => [3,4] => [3,5] = > [0,5] => end

We have to travel from the root to some other internal node 3 times in total.

Now let's see a different example:

If our query is [1, 8] we will have to do 4 root to some other internal node paths, so this doesn't look constant to me, it was 3 before, now it's 4.

So I can't understand why querying in an interval tree is O(log n).

How can you formally prove that querying is indeed O(log n), ie the amount of nodes that your algorithm must visit in order to answer any query is in the order of log n?


texts: Genetic Algorithm Getting Stuck on Certain Values

texts:
I'm attempting to teach myself something about genetic algorithms. I found a simple tutorial on it here, and it made enough sense that I was able implement the suggested example of generating a string of single digit numbers and simple arithmetic operators to total 42.

I then attempted the second suggested exercise described at the bottom of the page here. Basically, in a field of randomly placed circles of random size, write a genetic algorithm to find the largest non-overlapping circle you can place in the field.

I have something that seems to work, but I notice that it seems to get hung up on certain values. My "chromosomes" are composed of 3 pieces of data - x position, y position and radius. I'm using crossover and mutation to reproduce in the population. I then rank the results based on how large the resulting circle it is and whether it fits within the field and whether it overlaps other circles or not.

What I'm seeing is that there's a strong tendency for the radius to tend towards values that are just under a power of 2. For example, it will often get stuck bouncing around a radius of 31, 62, 124, etc.

I was trying to determine why this happens. My "genes" are all single precision floating point numbers. Crossover would cause some portion of the bits from one value to replace the corresponding bits of another value. Usually, this will result in the lowest precision bits of one value getting overwritten with those of another value. Occasionally it will cause part of or all of the exponent to get overwritten as well. Once you get a couple generations in, the values are largely of the same magnitude, so this often does very little. Mutation could flip any bit in the float, meaning it could turn a positive to negative 1/32nd of the time. It could change the exponent 7/32nds of the time, and the mantissa the remaining 3/4ths of the time.

Doubling the magnitude (by mutating or crossing over in the exponent, for example) is likely to have a positive effect up to a certain point. But once the generation contains mostly circles that are slightly over 1/2 the maximum value, they'll be less likely to grow by this method. Changes in the mantissa seem to have little effect overall.

My question - is this normal? This seems problematic when trying to generate better generations. I've let my simulation run for millions of generations, and haven't seen it get any better than the next-lowest power-of-2 for the radius. Have I just laid out my data in an unfortunate way, or does this problem come up often in genetic algorithms? Is there a way around it? I tried switching to a 16.16 fixed point representation and it got slightly better. The radiuses would get larger more frequently, but they still seem to hover around powers-of-2.


texts: DFAs are regular languages, but regular languages are closed under concatenation

texts:
I have course notes which claim the following two facts:
First, DFAs recognize exactly the regular languages.
Second, regular languages are closed under union, concatenation, and *.
Now I have as an exercise constructed a DFA which recognizes strings from {0,1} which have an odd number of 1s.  So the language of strings of any odd number of 1s is a regular language.  However, if you concatenate any two words from the language it contains an even number of 1s and is therefore not closed under concatenation.
I must be misunderstanding something, but what?
I think maybe what I'm doing is saying that the language itself is closed under concatenation, when that's not true.  Maybe the claim is actually that the concatenation of one regular language with another regular language is a third regular language?


texts:
Is there any class of NP problems that have one unique solution?
I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.


texts: Which is a type of objects in mainstream OO languages: a class, an interface, an abstract class, a metaclass?

texts:
In Types and Programming Languages by Pierce, Section 18.6 Simple Classes in Chapter 18 Imperative Objects says:

  We should emphasize that these classes are values, not types. Also we can,
  if we like, create many classes that generate objects of exactly the same type.
  In mainstream object-oriented languages like C++ and Java, classes have a more
  complex status—they are used both as compile-time types and as run-time
  data structures. This point is discussed further in §19.3.

The only place which Section 19.3 Nominal and Structural Type Systems says about classes is:

  These type names play a crucial role in Java’s subtype relation. Whenever
  a new name is introduced (in a class or interface deﬁnition), the programmer
  explicitly declares which classes and interfaces the new one extends (or, in
  the case of a new class and an existing interface, “implements”). The compiler
  checks these declarations to make sure that the facilities provided by the new
  class or interface really extend those of each super-class or super-interface—
  this check corresponds to record subtyping in a typed lambda-calculus. The
  subtype relation is now deﬁned between type names as the reﬂexive and tran-
  sitive closure of the declared immediate-subtype relation. If one name has not
  been declared to be a subtype of another, then it is not.

Does the above quote or some other places in Section 19.3 explain the second highlighted sentence in the first quote from Section 18.6, i.e. why

  In mainstream object-oriented languages like C++ and Java, classes have a more
  complex status—they are used both as compile-time types and as run-time
  data structures

? (I don't see Section 19.3 mentions that a class is a type of objects in mainstream OO languages, and even explains it.)

In Chapter 18 Imperative Objects, is an interface a type of objects?

In mainstream OO languages (such as Java, C#, I am not sure if C++ has interface),

is an interface a type of objects?

An interface seems to me a type of classes, since many classes can implement the same interface. Since a class is a type of objects, is an interface a kind?
Is an abstract class essentially the same concept as an interface? (In terms of being a type of classes or something else)
in Python, there is another concept "metaclass". Is a metaclass a type of object, a kind, or something else?

I have a related post a while ago: Is the implementation relation between an interface and a class an instantiation or inheritance relation, or neither?. It also introduces concept "metaclass" of Python, and my confusions between interface, class, abstract class, and metaclass. Appreciate if you could also take that into account.

Thanks.


texts: How an insertion can be decoded in Varshamov and Tenengolts (VT) codes

texts: I have a good idea of how deletion can be decoded in VT codes using Levenshtein algorithm. However, I don't have any idea how can an insertion be decoded? Can anybody give me a small example using a short VT code? Mostly papers say that a 1-deletion code can handle 1-insertion error as well, but I don't know how?


texts: Is a language containing set of binary numbers which are divisible by number N Regular?

texts:
Let N be any positive integer, then is following language regular for every $N$?

$L$ = { $B_n : B_n(modN) == 0$ } where $B_n$ is binary representation of a number.

E.g, $L=\lbrace B_n : B_nmod31 == 0,B_n \ is \ a \ binary \ number \rbrace$ is regular? Will the language be regular for any positive number in place of $31$.


texts: How to approach Dynamic graph related problems

texts:
I asked this question at generic stackoverflow and I was directed here.

It will be great if some one can explain how to approach partial or fully dynamic graph problems in general.

For example:

Find Shortest Path between two vertices $(u,v)$ in a undirected weighted graph for $n$ instances, when an edge is removed at each instance.
Find number of connected components in an undirected graph for n instances when an edge is remove at each instance, etc.

I recently encountered this genre of problems in a programming contest. I searched through the web and I found lot of research papers concerning with dynamic graphs [1,2]. I read couple of them and and I couldnt find anything straight forward (clustering, sparsification etc). Sorry for being vague.

I really appreciate if some can provide pointers to understand these concepts better.

Dynamic Graph Algorithms by D. Eppstein , Z. Galil , G. F. Italiano (1999)
Shortest paths on dynamic graphs by G. Nannicini, L. Liberti (2008)


texts: Convolutional Neural Network Feature Engineering?

texts:
I'm working through the tensorflow tutorial, and I see how you go from 28 x 28 to zero-padding and applying a 5x5x32 convolution to get 28x28x32 and max-pooling etc.  What I'm confused about is the 32 outputs seem to be described as filters acting upon the 5x5 layers.  The description is typically something like these are equivalent to filters being used to feature engineer, but when you set up the network you don't define any filters.  So how do the filters come about?

I read this question as well Intuition for convolution in image processing and although it's informative, it doesn't describe how the filters come about.

This is the tutorial, you can see the description of the layers in the first and second convolutional layers:
https://www.tensorflow.org/versions/r0.7/tutorials/mnist/pros/index.html


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

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

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

My question is how can i proove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv  b \pmod{p}\} \le c \ln(n)/(n^{c-1})$$?


texts: Is every PSPACE-complete problem complete with respect to logspace reductions?

texts:
A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in logspace, i.e. for any $A \in \mathsf{PSPACE}$,
$$
A \le_L TQBF.
$$
(See for example, comment at the end of section 7.4 in these notes.)
Therefore, TQBF is complete with respect to logspace reductions.
It is still possible, however, that there are some other standard PSPACE-complete problems for which this is not true. Of course, the problem would reduce in logspace to TQBF, but maybe the reduction the other way would not go through.

Question: If $A$ is PSPACE-complete, must $A$ be complete with respect to logspace reductions? In other words, if $A \in \textsf{PSPACE}$ and $TQBF \le_p A$, then must $TQBF \le_L A$?

Some thoughts:

I tried the generalized geography problem, and it seems to be true in that case. I'm not sure about universality for NFAs.

To prove it, the most straightforward idea would be to show that if $A \le_p B$ and $B \le_L A$, then $A \le_L B$. But this is false for general $A, B$, assuming $\mathsf{L} \ne \mathsf{P}$. In particular, take $A \in \mathsf{P}$ and $B = \varnothing$.


texts: How to determine if a regular language L* exists

texts:
I'm trying to make sense of regular languages, operations on them, and Kleene operations.

Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that there can be no string in the language that contains the substring 'xx'. Thus, my language could be expressed as L = {y, xy, yx}, since that language conforms to the definition.

Could I then argue that there is no language L* since L* could contain LL? That is, can a particular but arbitrarily chosen finite language that conforms to the definition exist, but since LL can't be in L*, L* cannot exist? Or must any L necessarily omit anything preventing L* from existing?


texts: Is the language of all words of the form $wxw^Rx^R$ context-free?

texts:
Is the language $\{wxw^Rx^R \mid w,x \in \{0,1\}^* \}$ context-free
My thoughts, Let $x = \epsilon$ and we get $ww^R$, which is context-free. Hence the given language must be context-free.
Am I right?


texts: Can Bellman-Ford run with time-complexity of cubic order

texts:
After reviewing the Bellman-Ford algorithm I can see that it runs with time complexity of $O(n^2)$ or, more exactly, $O(VE)$. It is necessary to loop (V-1) times the number of edges which is in fact 2 nested loops. This is true even if it includes the detection of negative cycles because this task only needs a last loop. However, I have seen that the algorithm time complexity is $O(n^3)$ in some sites. Specifically, the site where I saw it explains 2 steps:

A graph is built using 2 nested loops.
Bellman-Ford is applied to detect negative cycles.

Such a site says that $step$ $1$ is $O(n^2)$ (which is logical) and $step$ $2$ is $O(n^3)$

Is this possible? I will very much appreciate your feedback because I cannot find a logical explanation.

Respectfully,
Jorge Maldonado


texts: Knapsack Greedy Approximation: Worst Case

texts:
I am currently studying approximation algorithms and I have run into an issue with a study problem.

The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, where it sorts by the value/weight ratio, and picks the first item in this list that pushes the weight over the limit, and then picks either all the previous items or this particular item, whichever has a greater value.

The claim is that there is at least one case where this algorithm provides a value half that of the optimal value, but after many fruitless attempts I don't see a way to do this.

I have tried many value/weight pairs of 1/1 with a last pair of 5/6, resulting in a ratio of 5/9. Close, but even if I continue this process I am only going to approach a ratio of 1/2, but never achieve it.

Any hints as to how to proceed?


texts: Is there any meaning behind the classification of "λ-terms" in classes such as "church number" and "church list"?

texts:
λ-calculus terms can be informally/intuitively categorized, such as:

(λ f x . (f (f (f x))))) is a church natural (3)
(λ a b . a) is a church boolean (true)
(λ c n . (c 1 (c 2 (c 3 n)))) is a church list ([1,2,3])
(λ s z . (s (λ s z . (s (λ s z . (s (λ s z . z))))))) is a peano natural (3)

That is, while the untyped lambda calculus obviously doesn't have explicit types, one can certainly recognize patterns on terms and categorize them based on their behavior - as if those had a type. When you say: "a church number is a function that applies another function n times to an argument" you are informally characterizing a wide range of λ-terms. My question is: is there any way to formalize that intuition? Any system/theory that meaningfully categorizes (untyped) λ-terms?


texts: Trying to find a substitution to solve a recurrence

texts:
I'm trying to solve the  following recurrence.

\begin{align*}
B(2) &= 1\\
B(n) &= B(\lceil n  / \log_2 n\rceil)+\Theta(n)
\end{align*}

Here is my attempt:

\begin{align*}
B(n)
&= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\
&= 3\big(3B(\lceil n/(\log_2 n)^2\rceil) + \Theta(n)\big) + \Theta(n)\\
&= 3\big(3\big(3B(\lceil n/(\log_2 n)^3\rceil)\big)\big) + 3^2\Theta(n) + 3\Theta(n) + \Theta(n)\\
&\ \ \vdots\\
&= 3^{k-1}B(\lceil n/(\log_2n)^{k-1}\rceil) + (1 + 3 + \dots + 3^{k-1})\Theta(n)\\
&= 3^{k-1} B(\lceil n/(\log_2 n)^{k-1}\rceil) + \frac{3^k-1}{3-1}\Theta(n)\,.
\end{align*}
Is there a substitution that I can use to make the term inside the function become 2?

Or any other smart method I can use to solve this problem?

I realised I made a mistake the expansion should be

\begin{align*}
B(n)
&= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\
&= 3\big(3B(\lceil (n/(\log_2 n))/(\log_2(n/(\log_2 n) \rceil) + \Theta(n)\big) + \Theta(n)\\
&\ \ \vdots\\
\\
,.
\end{align*}


texts:
A power sequence is a sequence containing consecutive powers of a number starting from power one. for example $3^1, 3^2, 3^3$ is a power sequence. The question is to find the length of the longest power sequence in an array in $O(n)$ time. Note that the sequence is a subsequence of the array.
For example, in the array $1,2,3,4,5,6,7,8$,
the longest power sequence is $2,4,8$.
I wanted to write a hash function that gives similar values for powers of the same number, but this does not guarantee that powers are consecutive.


texts: Is Goedel's 1st theorem not algorithmically derivable?

texts:
First let me explain what I mean by algorithmically derivable.
An algorithm must be able to come up with the proof without prior knowledge of the proof, in the same way mathematicians and computer scientists are able to create new proofs without prior knowledge of the proofs.

Our proof deriver enumerates all possible axiomatic systems, and with each system enumerates all possible proofs.
It checks each proof to see if it proves Goedel's 1st theorem.
This algorithm will necessarily derive all finite proofs eventually.

Goedel's 1st theorem states no sufficiently powerful axiomatic system can be complete and consistent at the same time.
The deriver is complete, since it will eventually be able to prove all true statements and disprove all false statements.
This means the deriver is inconsistent, so it cannot know whether a set of axioms used to prove Goedel's 1st are consistent.

Therefore, an algorithmic deriver is unable to derive the proof for Goedel's 1st theorem.

Does this proof succeed in showing Goedel's 1st theorem is not algorithmically derivable?


texts: How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

texts:
How to show that the following language is not regular with the pumping lemma?

$$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$


texts: Computing miss penalty to L1 if block sizes are different in L1 and L2

texts:
I am having trouble computing the miss penalty in a L1 cache if the block size in L1 is different to the block size in L2 cache. Usually,
miss penalty in L1 = hit time to L2 + (miss rate at L2) x (miss penalty to L2)
However, if the problem specifies that block size in L1 is 32B while it is 64B in L2, does it not mean that L1 will be getting two blocks in every fetch from L2? Will this cause the computed miss penalty to be twice of what it actually should be (because we are actually computing miss penalty for 64B i.e. two blocks at L1)?
For example, with the above block size, say that

hit time to L2 is 10 clock cycles
miss penalty at L2 is 100 clock cycles
miss rate at L2 is 20%

is the miss penalty at L1 half of 10 + 0.2 x 100 i.e. 15 clock cycles?


texts: Exact runtime of median of median algorithm

texts:
Consider median of median algorithm. If I make to group of size $7$ instead of $5$ then the recurrence equation will be
$$T(n)=T(n/7)+T(5/7\cdot n+4)+O(n),$$
which can be proven by induction equal to $O(n)$.
Assume it takes around $14$ steps to sort group of $7$ elements. How do I find exact runtime if I want to find $k$th smallest element in sequence, by exact run time I mean a solution for above recurrence.
My idea was that since $T(n)=O(n)$ then $T(n)=an+b$ ,where $a $ or $b$ might be depend on value of $k$. How can I find value of $a$ and $b$ or it is impossible to find value of $b$, as value of $a$ can be found but I am not sure how.


texts: Polynomial time algorithm for a simple machine scheduling problem

texts:
Think about a setting where there are $n$ tasks and $m$ machines. We are interested in task-machine assignment. Let $p_i$ be a non-negative completion time of job $i$. Also, $x_i$ denotes the machine where task $i$ is scheduled. A machine processes the task having the smallest completion time, then the second etc. So for simplicity we assume the tasks available are ordered such that $p_1\leq p_2 \leq \ldots \leq p_n$.

The completion time of each task is given with:

$C_j(x) = \sum_{k \leq j,x_k=x_j}  p_k $.

And the social cost is defined as:

$C(x)= \sum_{j \in [n]}C_j(x)$.

An optimal solution $x^*$ is a strategy that minimizes $C(x)$.

How can we prove that there exists an efficient polynomial time algorithm that computes the optimal solution?


texts: Assignment Problem with Minimum and Maximum constraints

texts:
I have the following problem:
In a school, there are n students and m clubs, with n > m. Each student needs to be assigned a club. The students have preferences, (say top 3 or top 5) of the clubs they wish to be matched to. So far, it's basically just a maximum weight matching in a weighted bipartite graph, which can be done through the Hungarian algorithm.
But now the constraint is that there's both a maximum and a minimum number of slots that each club can accommodate. A way to deal with the maximum constraint would be to have multiple copies of each club, one for each slot, and then run the Hungarian algorithm to calculate the maximum weight matching as before. However, we also want a minimum number of students in each club, say to make the club functional - and this number can be different for different clubs based on popularity. Is there any way to do this? Would it mean a tweak to the main algorithm, or perhaps just a post-algorithm shuffling?


texts: Undecidability of the language of all Turing Machines with repeat strings as their language

texts:
Show that the language consisting of all Turing machines whose language consists of strings that can be broken up into two consecutive and equal strings is undecidable.
I would prefer if reduction was used and not Rice's theorem.


texts: Best sort method for median: median heap or insertion sort on a vector

texts:
I'm trying to decide between two methods of calculating a median, that will optimize the following operations:

Add integer to data structure (insert)
Get the median of all integer (getMedian)

The program will add a random number of integers (no limit on how many, but generally going to be relatively small amount) to the data structure before trying to access the median, and then repeat this process an indefinite amount of times.

With the median heap method, insert will take O(log(n)) on average and getMedian will be O(1).

What I'm wondering is what would happen if instead I simply used a vector. Insert would be amortized O(1). Then when getMedian is called, the vector is sorted with insertion sort, followed by simply accessing the middle element, O(1).

Would this be faster in the long run? There will almost always be more calls to insert than getMedian in the program, but I'm not sure if the insertion sort will be faster. I believe it is a relatively fast sort, O(n), on a partially sorted array, but I'm not sure.

For instance, if I had a vector with 100 million integers that were sorted followed by 4 unsorted elements, would insertion sort be O(n)? What if I had 50 million unsorted elements (very unlikely in the program, but possible)? And at how many unsorted elements would it be better to use another sort, like quicksort?


texts: Finding the time complexity of fibonacci sequence

texts: I tried it as follows and would like to know if it is correct.


texts: How do we distinguish NP-complete problems from other NP problems?

texts:
I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems.

So, the question is how we then distinguish non-NP-complete NP problems from NP-complete problems? It seems that all these problems will have a polynomial algorithm to convert into other problems...


texts: Are synchronous message sends a subset of async. ones?

texts:
Imagine any object oriented PL based around the idea of message sends: some method basically performs something like this:

send(target=someTarget, sender=self, message=someMessage)

Also, most of the PL allow for async message communications, where you can issue multiple messages to multiple targets and then "yield" to scheduler.
My question is: are synchronous communcations a subset of asynchronous ones?
In my head you can break down any synchronous message send into something like this:

asyncSend(target=someTarget, sender=self, message=someMessage)
target.setNotify(self)
self.setBlocked()
yield

Which will be totally aquivalent to a synchronous message send, BUT:

The problem I currently see if you try to mix these two together. When some method issues an async message send and then, before yielding, performs a synchronous message send, which gets kinda messed up. Hence the question :)

Also, sorry if this is wrong stackexchange. I don't think this question applies to the usual SO.

EDIT1: rephrasing the question: which of both concepts is more general? can you even say that?


texts: What are the prerequisites for working on multi agent systems?

texts:
I am starting to study about Multi Agent Systems and I wanted to know which sciences are most used in these systems, I am aware of game theory and Markov statistical relations (Markov Decision Process and Markov Hidden Model).
But I am not aware of all.If someone could name them for me it would be appreciated.

I also want to know the Major Journals On Multi Agent Systems.I have been trying to find them according to the Impact Factors but it seems it's not a good measure for doing so (Because there are some tricks for increasing the impact factor and cheating that journals do).


texts:
I have developed the following pseudocode for the sum of pairs problem:

  Given an array $A$ of integers and an integer $b$, return YES if there are positions $i,j$ in $A$ with $A[i] + A[j] = b$, NO otherwise.

Now I should state a loop invariant that shows that my algorithm is correct. Can someone give me a hint of a valid loop invariant?

PAIRSUM(A,b):
YES := true;
NO := false;
n := length(A);
if n<2 then
  return NO;

SORT(A);
i := 1;
j := n;
while i < j do  // Here I should state my invariant
   currentSum := A[i] + A[j];
   if currentSum = b  then
      return YES;
   else
    if currentSum < b then
      i := i + 1;
    else
      j := j – 1;
return NO;


texts: Prove consistency of maximum of two consistent heuristic functions?

texts:
Suppose we have two heuristic functions $h_1$ and $h_2$ which are both consistent, that is,

$$h_i(n) \leq c(n,a,n') + h_i(n')\qquad \ i\in\{1,2\}\,,$$

where $c(n,a,n')$ denotes cost of reaching the successor node $n'$ with action $a$.
Can we conclude that the $h_3:=\max(h_1,h_2)$ is also consistent?


texts: Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular

texts:
I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular.

This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$. Consider any pumping decomposition $w = xyz$ such that  $|y| >0$ and $|xy| \le p$.

I'm not sure what to do next.

Am I on the right track? Or am I way off?


texts:
Given a bipartite graph $G = (A,B,E)$ where every vertex is colored either red or blue I am trying to minimize the number of blue vertices using the following operation:

Choose a vertex $v_a$ in $A$
Flip the colors of $N[v_a]$, meaning that $v_a$ and every neighbor of $v_a$ will change color.

  Is there a polynomial time algorithm to select a recoloring set $X \subseteq A$ that will minimize the number of blue vertices? The number of recolorings needed is not relevant.

Observe that the order of flipping does not matter, and for every vertex in $A$, you either flip it or you don't.  We can think of the colors as a number which is incremented modulo 2.  This yields a trivial $O(2^{|A|} \cdot n)$ algorithm.


texts: Problems whose decidability status is unknown but known to be less hard than the halting problem

texts: Are there problems the decidability of which is unknown but it is known for certain that the problems are less hard than the halting problem.


texts: Complexity lower bounds via Cook reductions

texts:
Karp reduction (polynomial-time many one) is used in complexity theory to define NP-completeness. However, Cook reductions (polynomial-time Turing) is more powerful and intuitive from information theoretic perspective since it could offer an insight into the information content of hard sets in NP.

Intuitively, if we say problem $A$ Cook reduces to problem $B$ then the information content of set $A$ should be proportional to the number of calls made to $B's$ oracle. For instance, we have a truth-table (Cook) reduction from Graph Automorphism problem to Graph Isomorphism problem but no such reduction in the opposite direction is known. I am interested in techniques for lower bounding the number of calls to GA's oracle (in possible Turing reduction from GI to GA).

  Why is it hard to find lower bounds by lower bounding the required number of calls to $B's$ oracle? Is there an intuition that supports $P^{GI} \ne P^{GA}$?


texts: On an array of sets, Data structure to handle Interval insert, Interval erase, Interval sum of size query

texts:
Consider an array of sets. As you know a set must not have multiple elements. I need a data structure to handle following queries:

Insert element x to all sets on interval [ L, R ].
Erase element x from all sets on interval [ L, R ].
Query the sum of sizes of sets on interval [ L, R ] of the array.

Is there any data structure to handle it in something better than $O(n \cdot q)$ Time/Memory complexity? (Something like $q \cdot log(n)$, $q \cdot \log ^ 2(n)$ or $q \cdot sqrt(n)$ where $q$ is the number of queries and $n$ is the size of the array).

Update: interval [ L, R ] means the interval of indices of the array from index L to index R.


texts:
I've been studying a particular problem recently, and it seems like there might be techniques from statistics or ML that could be applied. Any advice or comments would be appreciated.

We're given some set of values sampled from a particular distribution. The values themselves are hidden to us, but their frequencies are known. We don't know the exact distribution the hidden values are drawn from, but using other information we've developed a model/approximation of it that probably has some errors, both in terms of missing elements and the frequency of a particular element. Our eventual goal is to map elements of our approximate distribution to their hidden counterparts in our target distribution.

For some small number of hidden values, we're also given the actual member of the distribution this value corresponds to. In a sense, a few of the hidden things are 'revealed' to us, but most of them remain hidden.

Is there any way for us to take the information we get from the revelation of the small number of values from our 'real' distribution and use it to refine our approximation of the entire target distribution, and not just the values that were revealed?

Obviously we know with certainty which elements of our approximate distribution correspond to the hidden values that were revealed, but can we use the fact that we also know 'how far off' our approximation was for those values to make our approximation more accurate for other values?


texts: Algorithm to detect if word belongs to pushdown automaton

texts:
I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that.

My thought at first would be to go through all possible transitions, and check if we didn't match this word in accepting state, but got in problem with (epsilon, epsilon)/V where we can put V into stack without reading anything and getting from stack.

Is there any good algorithm which could work, or is this task impossible?


texts:
Why are Hamming codes the best 1-error-correcting codes?
I need references. I know that hamming codes are the best 1-error-correcting codes but I want to know why they are best?


texts:
Here on the page 354 Arora and Barak write below the shaded area

"but in fact $f(\phi)$ $\notin SAT$"

and not

"but in fact $f(\phi) \in SAT$"

While in the last line of the shaded area they write

$Pr[f(\phi)\in SAT]=0$

Shouldn't there be in that last line also not:

$Pr[f(\phi)\notin SAT]=0$

?


texts:
I have a project where I should write the following algorithm :

  Let an integer function $f\colon\{1,2,3,\ldots,n\} \to \mathbb{Z}$ be monotone and suppose that $f(1) > 0$ and $f(n) < 0$. We would like to find the smallest integer $i$ with $f(i) < 0$. Design an algorithm for this purpose that run in time $O(\log n)4.

I tried to search in the middle ($\frac{n+1}2$) and then go in the right half or in the left half (like binary search) but the input is not sorted. Could someone give me an idea of how I can continue?


texts: Dual-pivot Quicksort reference implementation?

texts:
Has some sort of canonical - or reference - implementation of Dual-pivot Quicksort been posted anywhere?

I would like to include that algorithm in a comparison among sorting algorithms for a specialized need that I have, but the Java versions I've seen appear to have various kinds of tweaks applied to them, like using Insertion Sort for small (sub-) arrays, which makes it harder to compare the fundamentals.


texts: PRNG bad seeding and von Neumann unbiasing

texts:
Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is useful in production).  For example, Marsaglia talked about seeding methods in his May 2003 Communications of the ACM article [1].  It feels like a chicken/egg situation.  You need a source of high-quality random bits in order to seed your generator, so you can create a source of high-quality random bits.

I was wondering:

Is von Neumann unbiasing a legitimate way to defend against poor seeding of large-period PRNGs?   In other words, if I apply von Neumann unbiasing to the bitstream output of Mersenne Twister, does the quality of the stream still depend on how I seeded it?

[1] George Marsaglia, "Seeds for random number generators." Communications of the ACM, 46(5):90–93, 2003 (ACM page.)


texts: Extended version of the theory of reals and its decidability

texts:
It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More formally, is the theory $(\mathbb{R},\{\underline{r} \mid r \in \mathbb{R}\} +,\cdot,<,=)$ evaluated in the standard model of the reals decidable? Here, the symbol $\underline{r}$ is such that its interpretation in the standard model is exactly the real $r$.

I guess that the extended version is still decidable, essentially because two reals are different if and only if there exists a rational number between them. Rationals, on the other hand, can be expressed in the usual Tarski fragment.

Can anyone help?


texts: how did they get this answer for the words that don't have bba and abb?

texts:
I am looking at the answer in solution manual which asked , all the words that don't have both substring bba and abb.

and the answer was a*(baa*)*b+b*(a*ab)*a*

and I'm like wait a minute is that right ? but that can't make abb, which is in the language. So it's gotta wrong.

so I came up with my own , would this be all the words that don't have both substring bba and abb ?

(b+^)(ab+a)*+b*

^ is an empty string by the way


texts: How could you "solve" the halting problem if, hypothetically, the busy beaver numbers were "small"?

texts:
I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.

I'm trying to figure out how you could specifically do this. One obvious possibility is to build an n-state Turing machine that looks for a solution to an undecidable problem, then simply waiting for it to pass BB(n) transitions. This should be feasible since BB(n), in this scenario, is small, and surpassing it would prove that the machine loops forever.

But this isn't a satisfactory answer because surely decidability isn't about how feasible a procedure is in practice, but whether it's decidable in theory - what if computers were powerful enough to be able to implement this in our current universe where BB(n) is very large? Shouldn't we just assume that the machine is independent of number theory instead?


texts: Proving Clique Number of a Regular Graph

texts:
I am very new to Graph Theory and I am trying to prove the following statement from a problem set for my class:

Prove that if G is a regular graph on n vertices $(n \ge  2)$, then  $\omega(G) \in \{1, 2, 3,... \lfloor n / 2 \rfloor, n\}$

I am confused by the part where it places the clique number to be in this set: $\omega(G) \in \{1, 2, 3,... \lfloor n / 2 \rfloor, n\}$. Why can the clique number be only in the first half of this set (or it can be n) and why can't it be anything between $\lfloor n / 2 \rfloor$ and $ n$?

How can I go about proving this claim? Any tips would be appreciated.


texts: Which could be a possible time complexity?

texts:
I have the following algorithmen (picture) which calculates a Vertex Cover and gets an undirected $G(V,E)$ Graph as input.

The following task is to find the possible Time complexity (estimate) while $n = |V|$, $m = |E|$,
$n \le m + 1$ and $deg(v) = |N(v)|$:
a) $O(n log n)$
b) $O(n + m)$
c) $O(2^n*m)$
d) $O(n^k*m)$
e) $|V| \choose k$ * $\sum_{v \in V} deg(v) $

Clearly a,b cannot be an estimate running time for the algorithm.
e) looks correct, but c and d?


texts: Running time of a nested loop with $\sum i \log i$ term

texts:
So I have the following pseudo-code:

Function(n):
for (i = 4 to n^2):
    for (j = 5 to floor(3ilog(i))):
        // Some math that executes in constant time

So far, I know that to find this i will be calculating

$\sum_{i=4}^{n^2}\sum_{j=5}^{3i \log_{2}i}C$ where $C$ is a constant, but I am completely lost as to how to proceed past the first summation which, if I'm not mistaken, will give me $3C \cdot (\sum_{i=4}^{n^2}(i \log_{2}i) - 5(n^2 - 4))$, but from here I'm lost.  I don't need exact running time, but the asymptotic complexity.

All help is greatly appreciated!  I realize that this might be a duplicate, but I haven't been able to find a nested for loop problem of this nature anywhere...


texts: Are generational garbage collectors inherently cache-friendly?

texts:
A typical generational garbage collector keeps recently allocated data in a separate memory region. In typical programs, a lot of data is short-lived, so collecting young garbage (a minor GC cycle) frequently and collecting old garbage infrequently is a good compromise between memory overhead and time spent doing GC.

Intuitively, the benefit of a generational garbage collector compared with a single-region collector should increase as the latency ratio of main memory relative to cache increases, because the data in the young region is accessed often and kept all in one place. Do experimental results corroborate this intuition?


texts: Is there a reasonable and studied concept of reduction between regular languages?

texts: Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?


texts: Domain Specific Language for Data Structures

texts:
Question

Does there exist a DSL for describing data structures and their manipulation?  I realize that a "normal" programming language describes data structures, but they also do a lot more (e.g. IO).

I'm curious what the smallest language is required to describe classic data structures like List, Tree, Set, Stack, Queue, Map, Graph, etc. and their operations like append, remove, get, add, remove, poll, offer, etc.

Motivation

I ask this question because I was trying to think of a way to specify a data structure at runtime.

For example, imagine there exists some service which allows its clients to allocate space for a data structure.  This is done by enumerating the possible valid types that the data structure may be as well as the data structure's starting state.  For the list case, it's possible states are the empty and non-empty lists, and the starting state would be the empty list.

Then, clients would specify valid operations, that would modify the state of the data structure.  For example, define append, define remove, etc.  My question appears here: how would a client communicate to the service a valid operation to be performed on the data structure?  It would have to be written in some agreed upon formal language, the simplest DSL used for describing data structures and their operations.


texts: Introductory book on Logic and Computation

texts:
Can you give me some suggestions about a good introductory (but comprehensive) bookabout Logic and Computation?

Some fuzzy topics that I have in mind are:

Presburger artihm., PA, ZF, ZFC, HOL
Set theory, Type theory
Modeling Computation (Turing machines) in different theories
Links with computational complexity (FMT, descriptive complexity)