texts: how can I calculate the complexity algorithm for my algorithm?

texts:
I had developed a system for fruit grading whose steps are segmentation, feature extraction, classification.
the dimension of image n*n
Number of images m
then segmented image has complexity O(m.n^2)
IF (n.k is a segmented part) features are extracted then complexity after feature extraction is O(m.n.k)
if p is the number of features extracted then complexity after classification is O(m.p)
Total Complexity=o(m(n^2+n.k+p))
I want to ask for different segmentation technique used, different number of features, different classifier used what are the changes in total complexity


texts: short text categorization with spelling correction

texts:
I am building a classifier for short texts in a chat system. My features are words and pairs of words.

Naturally, the sentences contain spelling mistakes. If a particular wrong spelling of a certain word hasn't appeared in the training corpus, the classifier has no chance to identify it.

I consider taking an existing spelling corrector, and integrate it with my current classifier, but I am not sure how to do it.

Do you know of a paper that integrates an automatic spelling correction tool with a short text classifier?


texts: Find interval sums with minimum number of operation

texts:
Input:

A list $A=a_1,\ldots,a_n$, with $\oplus$ a associative operation on $M$, and $A\subset M$.
pairs $(s_i,t_i)$ for all $1\leq i\leq m$.

Output:
The list $b_1,\ldots,b_m$, where $b_i = \bigoplus_{j=s_i}^{t_i} a_j$.

We want an efficient algorithm to compute the output, such that it uses minimum number of $\oplus$ operations.

For example, if we have $m=2$ and want to find the sum on interval $(1,n-1)$ and $(2,n)$, then the best way is to first compute $t = a_2\oplus \ldots \oplus a_{n-1}$, then compute $b_1 = a_1\oplus t$ and $b_2 = t \oplus a_n$, using $n-1$ operations.

Note it is possible that we have to use $\omega(n)$ operations, consider we have the input that contain all pairs $(i,j)$, where $1\leq i\leq j\leq n$. This would require at least ${n \choose 2}$ operations, because there could be ${n \choose 2}$ different values.

Assume all elements in $M$ take $O(1)$ space. We also want to use as little additional memory as possible.


texts: Forward checking with conflict directed backjumping

texts:
Can somebody explain me how can I join forward checking with conflict directed backjumping in my CSP solver? I understand that when the consistency fails when I add a value to a variable, I should save all the instantiated variables of the restriction that fails, on the conflict set of the variable to which I gave a value. But what happens when there's no consistency failure but when I'm doing the inferences of the forward checking I found a contradiction? Do I need to know which restrictions failed and add the variables to the current variable conflict set?

My current approach:

My function that solves the CSP is recursive. So right now I'm doing the following, for each the current variable (the one I'm in the recursive step) I'm checking if the value that I give to her is consistent, if not, I add all the attributed variables of the restriction that fails to the conflict set of this variable. When I'm backjumping in the recursivity, I return this conflict set, and if any variable is contained in this set, it will try to change his value. (this implements the basic backjumping and with some other small changes I put my algorithm using conflict directed backjumping). I tested this part and it's working.

Now, when I add the forward checking, I need to get from the forward checking some informations when it finds contradictions (and this is the problem). Right now, I'm getting the variable where the contradiction occurs and all the attributed variables related to restrictions that failed.

Is this all the infromation I need from the backjumping?


texts: Is the language $\{f(x)\mid \mbox{$x$ is the code of a machine accepting $f(x)$}\}$ recursively enumerable and undecidable?

texts:
This is text of an exercise I am working on:

Given a binary encoding scheme for the set of the  deterministic Turing machines with alphabet $\{0,1\}$ and a bijective and computable function $f: \{0,1\}^* \rightarrow \{0,1\}^*$, prove that the language
$$L=\{f(x)\mid \mbox{$x$ is an encoding of a machine that accepts $f(x)$}\}$$ is recursively enumerable and undecidable.

I don't know how to prove it, and I don't know where to start.


texts:
Hello I am a new Computer Science student
Ok, so I am trying to sort the 2D array I know you can actually sort a 2D array by copying it into a 1D array sort it using any Algorithm, and then place back into the 2D array but here is the problem aren't we using more space and time because we have to copy the array back.
What I have tried so far
#include<stdio.h>

#include<stdlib.h>
#include<time.h>

#define ROWS 3
#define COL 5

void sort(int array[], int size);
void random(int rows, int col, int array[][col]);
void print(int rows, int col, int array[][col]);

int main(void)
{
    int set = ROWS*COL;
    int array[ROWS][COL];
    random(ROWS, COL, array);
    print(ROWS, COL, array);
    sort(array[0], set);
    printf("\n\n\n");
    print(ROWS, COL, array);
    return 0;

}
void print(int rows, int col, int array[][col])
{
    int idx, kdx;

    for(idx = 0; idx < rows; idx++)
    {
        for(kdx = 0; kdx < col; kdx++)
        {
            printf("%d ", array[idx][kdx]);
        }
        printf("\n");
    }
}
void random(int rows, int col, int array[][col])
{
    int idx, kdx;

    for(idx = 0; idx < rows; idx++)
    {
        for(kdx = 0; kdx < col; kdx++)
        {
            array[idx][kdx] = rand() % 10;
        }
    }
}
void sort(int array[], int size)
{
    int temp, idx, kdx;
    for(idx = 0; idx < size; idx++)
    {
        for(kdx = 0; kdx < size; kdx++)
        {
            if(array[kdx] > array[kdx+1])
            {
                temp = array[kdx + 1];
                array[kdx + 1] = array[kdx];
                array[kdx] = temp;
            }
        }
    }
}

But it's not any kind of algorithm and it will not work with dynamic memory you can say since it is just taking benefit of the way c store arrays. But things are different for dynamic arrays in c
Is there any Algorithm to sort 2D array.


texts: Why does an admissible heuristic mean A* is optimal?

texts:
An admissible heuristic never overestimates the cost to reach the goal. However, isn't that only the relative difference between heuristics for two different paths matter?

Say we have optimal path A (cost 100 to reach goal) and sub-optimal path Z (cost 120 to reach goal). Even if the heuristic is admissible, say it gives A a heuristic of cost 99 while it gives Z a heuristic of cost 10.

In both cases, the heuristic is admissible since it's lower than the actual cost it'll take to reach the goal, but still under this, Z is optimal since the heuristic gives a cost of 10 to Z and a cost of 99 to A.

It seems to me then it doesn't even matter that the heuristic is admissible. You still get the suboptimal solution.

What am I missing?


texts: Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?

texts:
Given an alphabet $\Sigma$, let $c=|\Sigma|$.  Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states?

I'm having trouble creating an $L_k$ such that any DFA for it has $\Omega(c^k)$ states.  There are constructions that require $\Theta(2^k)$ states, but here $c$ is an arbitrary constant, so if $c>2$ those constructions do not suffice.

Is the language of strings with a suffix of $s_k, |s_k|=k$ such a language? Following is a draft proof of that.

Proof by contradiction: let a DFA $\langle Q, \Sigma, \delta, q_0, F\rangle$ have $|Q|<c^{k-1}$. Let $a, b$ be strings of length $k$ and $a_k=(s_k)_1\not=b_k$

Let $q_a$ and $q_b$ denote $\delta(q_0, a)$ and $\delta(q_0, b)$, respectively.

There are two cases:

I. there are no $a,b$ such that $q_a=q_b$. Then each string corresponds to a different state, but there are $c^{k-1}$ such strings, therefore $|Q|\geq c^{k-1}$, which is not possilbe.

II. There are $a,b$ such that $q_a=q_b$. Then $\delta(q_a, s_2s_3\ldots s_k)=\delta(q_b, s_2s_3\ldots s_k)=q_c$. $as_2s_3\ldots s_k$ should be accepted and $bs_2s_3\ldots s_k$ shouldn't, therefore $q_c$ is both an accepting state and not an accepting state, which is not possible.

This seems to prove that any DFA for $L_k$ has at least $c^{k-1}$ nodes, which is sufficient for $\Omega(c^k)$. If my proof is correct, the only task left is to prove that a NFA containing $O(k)$ nodes exists for $L_k$.

The simplest way to do this is to create such a NFA, however I'm not sure how to do that. $O(k)$ suggests that $i$-th node should correspond to the state of "prefix of $s$ of length $i$ matches the suffix of the input string", however I do not follow how such a NFA can be created.


texts: D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$

texts:
Given that a language D has a polynomial verifier,

and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space.

How can I prove that $D\in P$ ?

My idea was to create a TM that takes a word w and runs the verifier on all the strings that are potentially a certificate but I don't know how to claim that such a machine will stop? How can I limit the number of certificates my machine will generate?


texts: Is this sparsity constrained convex projection problem NP-hard?

texts:
Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$ and an integer $m$ where $m<d+1$, we want to choose $m$ out of the $n$ points so that the residual of the projection of $y$ onto the convex hull of the $m$ points is minimized, out of all $n \choose m$ ways to choose $m$ points. If $d,n,m$ are part of the input, is this problem NP-hard?

Definition: The residual of a projection from $y$ to $x$ is the Euclidean distance between two points $x$ and $y$, namely, $\sqrt{ \sum_{j=1}^d (x_j - y_j)^2}$.   The residual of a projection from $y$ to a convex hull $H$ is the minimum of the residual of the project from $y$ to $h$, where $h$ ranges over all points on the perimeter of the convex hull.


texts: Grammar of words with exactly $k$ prefixes in another grammar

texts:
Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that

$$ L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\} $$

where $\text{Pref}(w)$ is the set of $|w|+1$ prefixes of $w$? Assume $G$ is unambiguous, if needed.


texts: How to find all tuples in which some attribute appears more than three times

texts:
im havin trouble with this exercise. I have a table like this and i can only use relational algebra without aggregate function like sum, count, etc.
Name | x
a   ~~   1
b   ~~   2
c   ~~   1
d   ~~   1
e   ~~   2
f   ~~   2
g   ~~   3
h   ~~   3
i   ~~   4
i need to get the values of x if it appears three times or more. In this case the output would be {1,2}
I have this
R1 = π x1←x, name1←name table
R2 = π x1, name (R1 ⨝ x1 = x ∧ name1 ≠ name table)
but this just gets the values of x that appear more than once.
Thanks.


texts: Is everything that is turing computable an element of NPSPACE?

texts:
So, if there is something that is turing computable, I know it is in NP (is that right?).

If M is computable, does it mean M is in NP?

M computable IFF in NP (is that true)?

And does all computable machines exist under NPSPACE?


texts:
From what I read in the preliminary version of a chapter of the book “Lectures on Scheduling”
edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D.

This is the PTAS Definition:

  A polynomial time approximation scheme (PTAS) for problem $X$ is an
  approximation scheme whose time complexity is polynomial in the input
  size.

and FPTAS definition

  A fully polynomial time approximation scheme (FPTAS) for problem $X$
  is an approximation scheme whose time complexity is polynomial in the
  input size and also polynomial in 1/$\epsilon$.

Then the writer says:

Hence, for a PTAS it would be acceptable to have a time complexity proportional to $|I|^{1/\epsilon}$ where $|I|$ is the input size;although this time complexity is exponential in $1/\epsilon$. An FPTAS cannot have a time complexity that grows exponentially in $1/\epsilon$ but a time complexity proportional to $|I|^8/\epsilon^3$ would be fine. With respect to
worst case approximation, an FPTAS is the strongest possible result that we can derive for an NP-hard problem.

Then he suggested the following figure to illustrates the relationships between the classes of problems:

Here is my questions:

From the PTAS and the FPTAS definition, how does the writer conclude that the FPTAS cannot have a time complexity that grows exponentially in $1/\epsilon$? and what difference does it make if it can have such time complexity?
A time complexity like $(n+1/\epsilon)^3$ is acceptable for FPTAS but it is not for PTAS, then why FPTAS is considered to be a subset of PTAS?
What does he mean by: an FPTAS is the strongest possible result that we can derive for an NP-hard problem.
In the aggregate I would like to know what exactly these to concepts mean and, what are their distinct properties.

Thanks in advance.


texts: Buying ingredients for a cake from many different stores and need to minimise the number of stores - algorithm name?

texts:
So let's say I'm baking a cake and it has a few ingredients (including multiples):

ingredients = {sugar, sugar, baking powder, chocolate, flour, egg, egg}

I can go to a bunch of different stores to buy the ingredients. Each store has a different collection of ingredients to offer:

store_1 = {sugar, vanilla extract, olive oil, chocolate}
store_2 = {chocolate, chocolate, flour, egg}
store_3 = {flour, baking powder, sugar, sugar, sugar, egg}

Problem: I want to buy all the ingredients for the cake from the minimum number of stores

I'm sure this is a common problem with existing algorithms, but I can't seem to find anything besides the bin packing problem. It is a similar problem but not quite the same.

Any ideas would be appreciated.


texts: Proving that DFA equivalence is decidable

texts:
The following question is taken from Sipser:

  Prove that $EQ_{\mathsf{DFA}}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.

Here is the answer:

  For any DFAs $A$ and $B$, $L(A) = L(B)$ if and only if $A$ and $B$ accept the same strings up to length $mn$, where $m$ and $n$ are the numbers of states of $A$ and $B$, respectively. Obviously, if $L(A) = L(B)$, $A$ and $B$ will accept the same strings. If $L(A) \neq L(B)$, we need to show that the languages differ on some string $s$ of length at most $mn.$ Let $t$ be a shortest string on which the languages differ. Let $l$ be the length of $t$. If $l \leq mn$ we are done. If not, consider the sequence of states $q_0,q_1,\dots,q_l$ that $A$ enters on input $t$, and the sequences of states $r_0,r_1,\dots,r_l$ that $B$ enters on input $t$. Because $A$ has $m$ states and $B$ has $n$ states, only $mn$ distinct pairs $(q,r)$ exist, where $q$ is a state of $A$ and $r$ is a state of $B$. By the pigeon hole principle, two pairs of states $(q_i,r_i)$ and $(q_j,r_j)$ must be identical. If we remove the portion of $t$ from $i$ to $j-1$, we obtain a shorter string on which $A$ and $B$ behave as they would on $t$. Hence we have found a shorter string on which the two languages differ, even though $t$ was supposed to be shortest. Hence $t$ must be no longer than $mn$.

Unfortunately, I do not understand the sequence of steps in the answer. Could anyone explain the answer for me in a simpler way?


texts: A string representation of any Turing machine

texts:
The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble seeing how this could be true.

If we formally define a Turing machine as having a tape language $\{0, 1, \sqcup, x\}$ and input language $\{0, 1\}$, then I can sort of see how any Turing machine could be encoded.

However, many books allow other symbols, such as $a$ or $3$, etc., to be part of the input language. I've heard people say that this is okay because we could represent such characters as a string like $0101$ or $1011$ or whatever, much like how Unicode represents code points consisting of multiple code units, or just how any computer represents anything at all!

But here is my problem with this. If we are trying to construct an actual function $f$ from the set of all Turing machines $\mathscr{M}$ to $\mathbb{N}$, then every Turing machine must be encoded in the same way. That is, we can't have encodings of different lengths, so that 01 represents $01$ for one Turing machine and represents $3$ for another. That is, unless we have some encoding at the beginning of each Turing machine which explains how the machine is to be decoded. But even then, this encoding itself must be universal.

The problem is much like the charset problem for HTML pages. That is, that a web browser must know the encoding of the page before it can decipher a command in the HTML to encode the page a certain way. This was solved for web pages by having the encoding command characters (meta charset=utf-8 for example) be the same in all encodings. But then the encoding itself is stored elsewhere.

Anyway, my question is how we resolve this apparent conundrum. How does one encode a Turing machine with a finite input language of any length so that one can make one function from $\mathscr{M}$ to $\mathbb{N}$?


texts:
Given two graphs one needs to decide if one of them has a subgraph isomorphic to the other.
Given a subset of a graph one needs to decide if the induced subgraph is  triangle free.

Can someone kindly help prove that both of these are NP-Complete?


texts: Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?

texts:
Imagine I have an ordering on a bunch of elements like so:

Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: $\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(X < Z\right)$.

In order efficiently answer queries like $A \stackrel {?}{<} D$, some sort of labeling or data structure is required. For example, you could number the nodes from left to right, and thus you can simply do integer comparison to answer the query: $A \stackrel {?}{<} D \implies 1 < 4 \implies T$. It would look something like this:

Where the number is the ordering, and the letter is just a name.

But what if you needed to insert elements "in between" two other elements in the ordering, like so:

How can you maintain such an ordering? With simple numbering, you run into the problem that there are no integers "in between" $2,3$ to use.


texts:
Assuming we have two integers a and b, if we do bitwise operations like a & b or a | b, is the running time O(1) (constant) or is it O(b) where b is the number of bits in a and b?
Thanks!


texts: Generating inputs for random-testing graph algorithms?

texts:
When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness. Modern testing frameworks can generate inputs automatically given the algorithms signature, with some restrictions.

If the inputs are numbers, lists or strings, generating such inputs in straight-forward. Trees are harder, but still easy (using stochastic context-free grammars or similar approaches).

How can you generate random graphs (efficiently)? Usually, picking graphs uniformly at random is not what you want: they should be connected, or planar, or cycle-free, or fulfill any other property. Rejection sampling seems suboptimal, due to the potentially huge set of undesirable graphs.

What are useful distributions to look at? Useful here means that

the graphs are likely to test the algorithm at hand well and
they can be generated effectively and efficiently.

I know that there are many models for random graphs, so I'd appreciate some insight into which are best for graph generation in this regard.

If "some algorithm" is too general, please use shortest-path finding algorithms as a concrete class of algorithms under test. Graphs for testing should be connected and rather dense (with high probability, or at least in expectation). For testing, the optimal solution would be to create random graphs around a shortest path so we know the desired result (without having to employ another algorithm).


texts: Find a minimal regular expression for the languge of the words that does not contain bbb

texts:
Let's say my dictionary is {a,b}
I want to ccind a regular expression for the languge of the words that does not contain bbb in the most minimal way.
All I can think about is '+'ing between prefixes but I think that there is a way to get a shorter answer.


texts: Mahaney's theorem and converting SAT to equivalent language

texts:
Language $L$ is sparse if there exists a polynomial $p$ such that $|L ∩ \{0,1\}^n| ≤ p(n)$. Thus, if there are at most polynomial number of strings for each length $n$ in the set $S$ (where $S$ represents the language $L$), the set $S$ is a sparse set.

Mahaney's theorem states that if an NP-complete language is Karp-reducible to a sparse language then P=NP.

As I understand, the $S$ would consist strings of form $\langle Q_i, x_i\rangle$ where $Q_i$ is a 3SAT instance, and $x_i$ is one of its variables. Thus, for all $k$ inputs accepted by any $Q_i$, we would have $k$ strings of the form above (one for each accepted input $x_i$). And the length would be the size of the resultant string for $\langle Q_i, x_i \rangle$.

If my understanding is correct, can someone help with a small example how to  convert a SAT problem into equivalent string. The inputs $x_i$'s would be in binary already, but not clear how to get the string equivalent to $\langle Q_i, x_i\rangle$?


texts: Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles

texts: Given a 4-regular graph, is it NP-complete to test whether it can be decomposed into two edge-disjoint Hamiltonian cycles?


texts: Do the SLR and LALR parsers of a same CF grammar have the same shift actions?

texts:
In theory, given that:

The LALR parser can be constructed by merging LR(1) states with the same core;
If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$;

the SLR and LALR automata should be isomorphic.


texts: Methods of turning a decision problem into finding the certificate?

texts:
I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If it's yes, how can we go from that to finding a polynomial-time algorithm that gives the certificate?

For example, let's say I have a CNF formula. Let's assume we have an algorithm that outputs whether a formula is satisfiable, in polynomial time. I want to know what the actual assignment is. So I'd do a for loop (for i from 1 to n, where n is the number of variables). At each step, I can do one more assignment (assign the i'th variable to be true) and check if the new formula with the i'th value set, is still satisfiable. If yes, continue. Otherwise, assign the i'th variable to be false, and then continue. By saving each of these assignments, at the end I can output a list.

My question is, are there some good methods (in general) of finding the certificate? Perhaps some "token problems" where if you know what to do with one problem of that type, you can do all problems of that type (eg, graph theory, network design, sets/partitions, algebra/number theory, satisfiability)?


texts: Uniform sampling from general simplex with a twist

texts:
This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.

Given $a_1,\dots,a_D$ (all strictly positive), I want to draw points uniformly from

$\qquad X =\{(x_1, x_2, ..., x_D) \mid 0 \leq x_1 \leq x_2 \leq \dots \leq x_D\leq 1, \sum_{i=1}^D a_i x_i  = 1 \} $

How do I achieve this? I would also like to understand how $x_1$ might be distributed over $[\frac {1} {\sum_i a_i}, \frac {1} {a_1}$] (a theoretical query).

This question solves it for $a_i=1$ and without the $x_i$'s having a prior order, but I do not see any obvious way to generalize from that answer.

There is a similar question on MO, but without the weights $a_1,\dots,a_D$.


texts:
I read an article https://www.geeksforgeeks.org/maximum-bipartite-matching/ to solve the maximum bipartite problem. In this article, two solutions are given.

In the first solution, they have explained that we can use edmond-karp algorithm to find the maximum bipartite matching and that would take $O(|E|^2|V|)$ and then there's an another solution given which works in $O(|E||V|)$.

Moreover, if there are problems like a job can be given to multiple people or a person can do multiple jobs can also be done using both methods.

I read over many online resources and the first method seems to be quite popular. So, are there any problems where I would want to use the first method over the second method?


texts:
Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.

I was trying to understand this. So far, I was able to prove that for,

Maximum sum of m integers among n integer.
Minimum spanning tree.

However, The classical greedy algorithm Activity Selection seems to fail having both independence and base exchange property.

Let,
E = {1-3, 2-4, 3-5, 4-6, 5-7}

Now, Take two independent set,
I = {2-4, 4-6} and J = {1-3, 3-5, 5-7}

There is no activity in J which can extend I. Which fails the independence exchange property of matroid, if I understood it correctly. Thus, it is not matroid and shouldn't have a greedy algorithms. But this problem has a greedy solution.

Where am I wrong?


texts: Gap between the average length of a Huffman code and its entropy

texts:
Difference between “average length” and “entropy” gives the percent of optimal. The optimal case is when the average length of a code is equal to the entropy. For example if average length is 1 and entropy is 0.72: (1- 0.72) = 0.28 -> 28% worse than optimal.

If both “average length” and “entropy” are 1, the compression is optimal.

But what does it mean if the result is negative value?

Note: entropy : -(pr*lg(pr)).
Average length: probability*number of bit


texts:
I'm trying to understand DPLL algorithm for solving SAT problem. And here it is:

Algorithm DPLL
  Input: A set of clauses Φ.
  Output: A Truth Value.
function DPLL(Φ)
   if Φ is a consistent set of literals
       then return true;
   if Φ contains an empty clause
       then return false;
   for every unit clause l in Φ
      Φ ← unit-propagate(l, Φ);
   for every literal l that occurs pure in Φ
      Φ ← pure-literal-assign(l, Φ);
   l ← choose-literal(Φ);
   return DPLL(Φ ∧ l) or DPLL(Φ ∧ not(l));

At first, I don't clearly understand how unit-propagate(l, Φ), pure-literal-assign(l, Φ) and choose-literal(Φ) work. I'll try to guess on particular examples. Correct me please if I do something wrong.

For the first one

unit-propagate(a, (0 v -a) ∧ (a v b) ∧ (b v d) ∧ (f v g) v ...)

we will have

((0 v -0) ∧ (0 or 1) ∧ (1 v d) ∧ (f v g) ∧ ... = (f v g) v ...,

having a = 0, b = 1.
For second procedure

pure-literal-assign(a, (a v b v c) ∧ (d v -b v a) ∧ (-d v b))

result is

(b v c) ∧ (d v -b) ∧ (-d v b),

assigning a = 1.
And finally choose-literal(Φ) just returns some random (in common case) unassigned literal for further computations.

Now, I don't understand why algorithm has such strange conditions for finishing? Why does it work?

Thanks!


texts: Solving/Optimizing a linear system in a finite field (Z/2Z)

texts:
I'm trying to solve the following optimization problem.

A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y are vectors). And I'm looking for X such that the Hamming weight of Y is maximal.

In the best case, there would be a solution with Y_i = 1 for all i, and I would find it using the Gauss algorithm.  But I know it's not the case.

So far, I haven't found a better algorithm than a random/greedy local search, but I'm sure I can use some maths to get a better solution. I've considered running a Gauss algorithm starting with B = (1,...,1) and  somehow backtrack when a run into a contradiction (and switch the b_i that prevent me to get a solution). Could matrix factorization help somehow?


texts: Can you delete-min from fibonacci heap in O(1) amortized?

texts:
I just had a data-structures exam. One of the questions asked us to create a data structure which allowed insert operations in O(logn) amortized and delete-max (or min, doesn't matter) in O(1) amortized.
The official answer was to use a regular fibonacci heap, and then to change the potential s.t. for every insert we increase the potential by logn (instead of 1) and then for every delete max we can decrease the potential by logn.
In other words, we pay for the deletions with the insertions.
To me, this seems a illegitimate, because at the end of the day each deletion will still cost O(logn) at least. Am I misunderstanding something, or is this really a bad question?


texts: NP-hardness of existence of spanning tree with given maximal degree

texts:
I am trying to solve the following exercise:

Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:

$G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.

$G$ has a spanning tree where every node has at most 5 neighbors.

It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.
I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?


texts:
Input: A max binomial heap $H$, and a pointer to a node $V$.
Output: A max binomial heap, where all the children of $V$ are multiplied by 2.

I have tried solving this by taking out the node $V$ together with it's sub-tree, multiplying all the children of V by $2$, rearranging the heap to close the hole, and adding V's children to the heap.

It sums up to $O(k\log n )$, where $k$ is the number on nodes in the tree containing $V.$
Can I do better than this? I'm sure I can but I don't know how.


texts: Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

texts:
I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to the other one.

I know that each graph can be mapped to a graph with only two outgoing edges for each node, but i can't find a way to convert from many edges to two edges that allows me to perform the reduction. If I convert a node with 3 edges to something like

A----B-OUT1
|    |
OUT3 OUT2

Then the mimimun edge set will contain AB instead of B-OUT2 and B-OUT1, provided that OUT1 and OUT2 are generating a cycle, since by cutting AB it will save a point in the objective function.

Is this reduction possible?


texts: Transforming a multidimensional 0-1 knapsack problem to a maximum weighted clique problem

texts:
Just out of theoretical curiosity, is there a way to transform a 0-1 multimensional knapsack problem to a maximum clique problem? Or maybe even easier, to a maximum weighted clique problem (the weights in nodes)?
I assume that since the decision counterparts of both problems are NP-complete, and all NP-complete can be transformed to each other, there must be a way to transform their functional counterparts as well, although I don't know whether that assumption is in general true.
I have already found a way to transform a maximum weighted clique problem (if the graph is connected) to a multidimensional 0-1 knapsack by creating a variable and a restriction for each (undirected) pair, but I cannot think a way to do the inverse transformation, because the knapsack problem doesn't have a "transitive" property, in the sense that if items a and b fit together, and b and c fit together, and a and c fit together, doesn't mean that all three fit together at once, while the clique problem does indeed have this "transitive" property (if three nodes are connected to each other two-by-two, a solution containing all three is feasible).


texts: Why will the Hindley-Milner algorithm never yield a type like t1 -> t2?

texts:
I'm reading about the Hindley-Milner typing algorithm while writing an implementation, and see that, as long as every variable is bound, you'll always get either atomic types or types where the arguments will determine the final type, such as t1 -> t1 or (t1 -> t2) -> (t1 -> t2) where t1 and t2 are type variables.

I cannot think of a way you'd get something like t1 -> t2 or simply t1, which I understand would mean the algorithm is broken since there would be no way to determine the actual type of the expression. How do you know you'll never get a type such as these "broken" ones as long as every variable is bound?

I know the algorithm yields types with variables, but these are always resolved once you pass the arguments to the function, which wouldn't be the case in a function with type t1 -> t2. This is why I want to know how we know for sure the algorithm will never yield such types.

(It seems that you can get these "broken" types in ML, but I'm asking about lambda calculus.)


texts: Which are the cases where the "pumping lemma" doesn't work?

texts: Are there some languages not regular and/or not context-free in which the proof by contradiction fails? Why we need a "more specific" version of pumping lemma?


texts: How do you create a sentential form in a given grammar?

texts:
I am given the following grammar:
$$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$
I need to decide whether $aBaabda$ can be produced in the given grammar.
I am unsure how the grammar can actually be read. For example, under what circumstances can you read $abT$ in $S$? Can you skip past $aBS$ and go to $abT$ or $a$?
I understand that deciding whether $aBaabda$ can be produced is a theoretical question, so you can theoretically create anything as long as its within the bounds/rules of a language. But I don't fully understand the rules of producing a sentential form.
And on not understanding rules fully: can you stop reading input on a non-terminal? It's name, of course, implies not. For example, without creating a derivation tree can you tell that something like $aaaabdaaaaBS$ or $aabdaB$ can't be made because it ends in a non-terminal? Except, writing this I realised that a non-terminal such as $B$ has ϵ, so that implies you can end on $B$, right?
Or can you end simply when you have matched a sentential form? For example, if you create a derivation tree and have a node for $S$, do you have to carry on reading or can you simply end?


texts:
I need to get the asymptotic runtime for an algorithm and I'm just stuck.

A python implementation:

def alg3(n):
    for i in range(1, n+1):
        for j in range(1, n+1):
            k = j
            while k <= n:
                k = k*3

I think it should somehow be $\Theta(n^2\log(n))$ but that isn't quadratic.
Can you help?

import time

def alg3(n):
    count = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            k = j
            while k <= n:
                count = count + 1
                k = k*3
    print(count)

n = 10
for i in range(0, 6):
    start_time = time.time()
    # run two times then calculate average time
    for i in range(0, 100):
        alg3(n)
    print("time with size %s: %s seconds" % (n, (time.time() - start_time)/100))
    n = n*2

If you calculate the factors given they give about 4.1.


texts: How to find degree of polynomial represented as a circuit?

texts:
I know very little about arithmetic circuits, so maybe it is something well-known.

Given a small circuit consisted of $\{1,x,-,+,*\}$ defining one variable polynomial. Let be additionally known that degree of this polynomial does not exceed $d$ and all the coefficients are small. I wonder if exists a fast way to find actual degree of this polynomial?
Using FFT and some small field, one can do it in $O(d)$ time (regardless $polylog$ factors), but this time is sufficiently to reconstruct the the entire polynomial, so I hope computing degree only can be done more efficient.


texts: Is Bin-Packing with only 2 types of objects polynomial?

texts:
Is the following problem polynomial ? Or NP-Complete ?

Problem: Bin packing with 2 types of objects.

Input: $C$, the capacity of each bin, $N_a, N_b$ the numbers of objects $a$ and $b$, $w_a,w_b$ the weight of the objects, $k$, the maximum number of bins.

Output: Yes if all objects fit in the $k$ bins without exceeding the capacity of any bin or cutting objects, No otherwise

My first intuition was that with only two types of objects, there must be less solution and maybe enumeration is polynomial, so I tried count them.

For an instance of size $n$ (with $n$ objects), we can encode solutions as $n$-tuples $[0,1,1...,0,1]$ (the first objects being in the first bin until it's full, then the second, etc). For instances of size $n$, there are $2^n$ distinct solutions.
Since there are $n$ instances of size $n$ (I mean, $n$ pairs $(N_a,N_b)$ such that $N_a+N_b=n$), and by the pigeonhole principle, there must be an instance with at least $2^n/n$ solutions. So a simple enumeration of solutions doesn't work.

Then, I started thinking that the problem may be NP-Complete. Reducing a graph problem seems no to be a good idea: graphs are big structures, and this problem as only a few numbers as an input. At this point, I realized that all the NP-Complete problems I've heard of had biggers inputs.

Now, I'm a bit confused. I can't figure out a good algorithm or a reduction.


texts: Distinction between paging and segmentation?

texts:
In my operating systems textbook, there is a paragraph which states:

As for the contents of each PTE, we have a number of different bits
in there worth understanding at some level. A valid bit is common to
indicate whether the particular translation is valid; for example, when
a program starts running, it will have code and heap at one end of its
address space, and the stack at the other. All the unused space in-between
will be marked invalid, and if the process tries to access such memory, it
will generate a trap to the OS which will likely terminate the process.
Thus, the valid bit is crucial for supporting a sparse address space; by
simply marking all the unused pages in the address space invalid, we
remove the need to allocate physical frames for those pages and thus save
a great deal of memory.

However, the bold sentences confuse me. I thought the whole point of paging was that you do away with the contiguous regions of logical code segments like stacks and heaps? With paging, couldn't the stack and heap be anywhere and non-contiguous? What guarantee do you have that the code, heap and stack will be separated to the top and bottom of the address space,as they say?


texts:
Given:

a quadrilateral mesh that forms the surface of a sphere
a linear projection from 3D to 2D  (a 2x3 matrix)

The mesh is not convex in general, but it is regular enough
that we know that the projected image of the mesh in the plane is a
polygon without holes (the image is simply connected).

Is there a fast method for computing the area of this polygon ?

I can compute an approximate area by scan converting
all the quadrilaterals,
but maybe there is a clever algorithm that can
give a more precise number.
A method for computing this polygon explicitly would be OK.


texts: Why do we consider enumeration up to $\omega$ instead of leaving it to as many ordinal numbers?

texts:
A few minutes ago I asked a question about a "proof" that $\mathbb{R}$ is enumerable that crossed my mind: What's wrong with this "proof" that $\mathbb{R}$ is enumerable?
I was told to look into ordinal numbers, and that after crossing $\omega$ we stop considering something to be an enumeration.
Why is this the case? Are there negative consequences if we don't put this limitation?
Edit:
I always thought of $\mathbb{N}$ as the "counting numbers" - but... when we cross over to ordinals like $\omega$, $\omega+1$, etc, aren't we still effectively counting?


texts:
I'm trying to interpolate a logarithmic function but it always reaches a singularity due to $\log(0)$ being $-\infty$

is there a correct way to interpolate logarithmic functions? (as in correct parameters)

What i'm currently going for is

$y=a+b \log(cx)$

with initial values

$a=0$,
$b=1$,
$c=0$


texts:
Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary
notation on its tape. Explain how it can count down from n to 0 in O(n) steps.

Here's my logic to approach this problem, but I am not sure if the time complexity of part b is O(n log n).
For unary notation on the given tape, the tape has 1's of length n >= 1. The machine on each configuration prints out the contents written in unary notation in the tape and then moves its head one step to the right by replacing 1 to x. Thus, we can intuitively see that the machine that counts down from n to 0 passes through all configurations in O(n) steps during its computation, printing out the number of 1's in the tape on each configuration (i.e. n, n-1, n-2,..., 0).
For binary notation, if we have a binary counter representing the number n, then there will be a total of O(log n) different bits (since each bit represents exponentially smaller and smaller values). And we should pass all elements in the tape to update the value between 0 and 1, which takes O(n). Thus, the time complexity, in this case, ends up being O(n log n).


texts: How to cluster nodes based on the number of dependencies

texts:
I have a problem where, there are a set of nodes and dependencies between them. I want to cluster them based on the maximum number of dependencies.  Dependencies can be thought of as number of edges connected.  I want to group those with maximum dependencies.

For example in the set $\{1,2,3\}$ and $\{3,5,7\}$ if $\{3,5,7\}$ have more dependencies i need to group $\{3,5,7\}$. I know the dependencies beforehand.

  Which algorithm will help to solve this problem?


texts: How to analyse the complexity of a problem with two or more size measures

texts:
Consider this example: a problem of dimension $n$ and $m$ ($m,n$: any given integers).
has a search space of size $O(n^n * m^n)$.
It is clear that this problem is exponential in $n$,
whatsoever $m$ may be.
My question: is this same problem polynomial in $m$?
what are the assumptions if we can say that?
is this way of complexity analysis correct?


texts:
I was reading about the concept of quine and in particolar of "reciprocal Quines" for example a Program $A$ that output the code of a program $B$ and vice versa, with the two being written in the same programming language.

Thinking of this particular case I have come to the conclusion that these two program must necessarily submit to certain properties. The first thing that came to my mind is the fact that they cannot have different cardinalities, the reason is easily understood: lets take the case that one of the two (lets say $A$) has a $\gt$ cardinality, so  $\mid A \mid\gt\mid B \mid$.

Now we codify this example in a trivial way: $A = 1111$ (|A|=4) and $B = 111$ (|B|=3).
It is evident that $A$ can produce the $B$ code but the reverse cannot happen as $B$ has fewer bits than $A$. The only way for the game to work is that the programs have the exact same length and all the practical examples I have seen online (through high-level programming languages) seem to respect this "supposition" of mine.
A second thing I noticed is the fact that these two codes differ only by a short number of characters.

Am I making any mistakes in these considerations?
Is there a way to calculate the maximum number of difference characters that can exist between the two codes?

I would also appreciate if someone could indicate me some sources for the theoretical study of this particular case of quines, searching online I found only practical examples
accompanied by brief explanations on the syntax of programming languages.


texts: Where should we place action symbols in a grammar?

texts:
In the following grammar that is used for math expressions(and other grammars) how do I know where should I place action symbols(@add, @mul, @pushID)? Is there a algorithm for it?

E -> TE`
E'-> +T @add E'|ϵ
T -> FT`
T'-> xF @mul T'|ϵ
F -> (E)|@pushID id

For example why @add is between +T and E' and not after E'?
I searched for it's algorithm but didn't find anything useful.


texts: Approximate Matching - two plane geometries with n points

texts:
I'm trying to do approximate matching of one plane geometry with n points to a big set of other plane geometries. The aim is to get the closest shape (rotation and scale agnostic)

My idea would be to "normalize" all the shapes coordinates in the database to [0-1, 0-1] to omit the scaling correction and than compare it to the given (blue) geometry.

I've looked at a couple of papers of Helmut Alt, especially Discrete Geometric Shapes - Matching, Interpolation and Approximation (under 3.2Approximate Matching) but I can't extract the correct math to a function (I'm trying to do this in javascript)

Maybe someone has an idea on how to do this or a different approach.

Thanks!


texts: Structure of numbers in descriptive complexity

texts:
Descriptive complexity is a useful way to free yourself from computational considerations when studying complexity. One of those considerations is the encoding of the structures you are working on.

However, the way we usually see integers in descriptive complexity is exactly the same way we're used to with Turing machines : $n$ is an ordered set of $\log_2 n$ elements, together with a unary relation that is true on the $i$-th element iff the $i$-th bit is 1 in the binary representation of $n$. This means we see integers exactly as their encodings.

Moreover, one of the main questions in descriptive complexity is Chandra-Harel conjecture, i.e. is there a logic for P on unordered structures. As such, is there a way to see integers as unordered structure ? Such a way should still ensure that the encoding of an integer is (at least poly-)logarithmic in $n$.


texts: Optimal Page Replacement Algorithm - If more than one frame will not be used again, which one gets replaced?

texts:
This may not make a difference in the end, but not knowing is driving me insane. When using the Optimal algorithm for page replacement, if you need to put something new into a frame and you have more than one frame that will not be used again, how does it prioritize which one to replace? In other words, if you have three frames and you enter in 1, 1, 2, 3, and neither 1 or 2 ever appears again, which one gets bumped when you try to put in 4?

Does it go by FIFO and kick out 1, does it go by most used and kick out 2 or does it go by least recently used and kick out 1?


texts: Let u and v be two strings. What about the reverse order of their concatenaited string?

texts:
let $u$ and $v$ be two strings. Is $(u.v)^R$ equals to $u^R.v^R$?

Note: The $R$ notation means reverse order and the $.(dot)$ notation means concatenation.


texts: Either find a perfect matching, or return a witness that none exist

texts:
I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options:

If a perfect matching exists, it returns the matching;
Otherwise, it returns a witness based on Hall's theorem, i.e., a set $S\subseteq X$ such that the number of neighbors of $S$ is smaller than $|S|$.

I found in wikipedia various algorithms for finding a maximum matching in an unweighted bipartite graph. Such algorithms can be used to determine if a perfect matching exists. But does any of these algorithms also return an evidence in case of failure?

EDIT: I have read the links in the answer of Yuval Filmus below, but it took me some time to fill in the missing details. For future reference, here is a detailed solution. Below, let $n := |X| = |Y|$.

Step 1. Define a flow network with $2n+2$ nodes in the following structure:

$$ s \rightrightarrows X \rightrightarrows Y \rightrightarrows t $$

where:

$s$ is a new source node connected to all vertices in $X$ with capacity 1;
every original edge of $E$ is directed from $X$ to $Y$ with capacity $\infty$;
each vertex in $Y$ is connected with capacity 1 to a new sink node $t$.

Step 2. Use the Ford-Fulkerson algorithm to find a maximum flow in that graph. Suppose the maximum flow size is $m$ (which must be at most $n$).

Step 3. If $m = n$ then we are done - the flow induces a matching of size $n$ which is perfect.

Step 4. Otherwise, $m < n$.
The FF algorithm also returns an $s$-$t$ minimum cut of size $m$ - a partition $(C,C')$ of the vertices in the graph, such that $s\in C$, $t\in C'$, and the sum of capacities of edges directed from $C$ to $C'$ is $m$.

This cut cannot cross any edge of $E$, since these edges have infinite capacity. Hence, the cut size is determined by edges from $s$ to $X\cap C'$ and from $Y\cap C$ to $t$. So $m = |X\cap C'| + |Y\cap C| = (n-|X\cap C|)+|Y\cap C|$. Hence: $|X\cap C| = |Y\cap C| + (n-m) > |Y\cap C|$. Since the cut cannot cross edges of $E$, all neighbors of $|X\cap C|$ must be in $|Y\cap C|$, so $|X\cap C|$ is the desired Hall-violator.


texts: Prove that there exists a machine which decides an infinite subset of halting problem

texts: We already know that $H:=\{\langle M,w\rangle | M$ halts on $w\}$ is undecidable, then how can there possibly be a machine that decides any infinite subset of $H$?


texts: Why are all polymorphic functions between functors natural transformations?

texts:
Bartosz Milewski's Category Theory for Programmers says the following:

  A parametrically polymorphic function between two functors (including the edge case of the Const functor) is always a natural transformation.

Why is this true?

Something along the lines of an informal proof would help me.
It would also help to have an intuition about this.
Milewski says that naturality can be thought of as "separation of concerns" and provides an eggy metaphor:

  One [functor] moves the eggs, the other boils them.

How could ad-hoc polymorphism mix the concern of moving the eggs with the concern of boiling the eggs?

As you can see, I'm pretty fuzzy on this topic.


texts: Do different variants of Mergesort have different runtime?

texts:
One of my courses introduced the following question:

Given the recurrence relation for mergesort:
$T(n) = 2T(n/2) + n$
How would the following parameter passing strategies influence the relation and running time of the algorithm:

A pointer to the array is passed to the sorting function,

The entire array is copied to a separate location before applying the sorting function,

A subsection of the array is copied to a separate location before applying the sorting function on that subsection.

For 1., since this is how mergesort is used most of the time, we can solve it easily using the master theorem.
$f(n) = \Theta(n^{\log_b a}) = \Theta(n) \implies T(n) = \Theta(n \log n)$
For 2. however, I am a bit baffled. Although we do an additional work of $O(n)$, we are only doing so once at the beginning of the sort. Hence, doing one additional instance of $O(n)$ work should not influence the order of the running time (because it already is of a larger order). Hence, for both 2. and 3. the running time would remain at $T(n) = \Theta(n \log n)$.
Is this reasoning valid? Something tells me that the $O(n)$ copying should have more of an impact, but I can't seem to give myself a good enough reason that it should be responsible to slow it down enough so that it would worse (i.e. $O(n^2)$).
Any thoughts or hints would be quite appreciated!


texts: History/Etymology- Map/[Hash]Map vs map()

texts:
Forgive me/delete this question if it doesn't qualify as Computer Science:

I've always wondered about the relationship between Map the data structure and map() the function. I know they are two different things. Why share the name?


texts: Show that this language is not regular by Pumping Lemma

texts:
Over the alphabet $\Sigma=\{a,b\}$, we define
$$L=\{a^pb^m: p\text{ is prime }, m>0\}+\{a^r:r\geq 0\}.$$

I must show that this laguage is not regular using the pumping lemma. I guess I should apply it to a word of the form $a^pb^m$, and my intuition is that I should come to the contradiction of $p$ not being prime. But I'm not very familiar with the pumping lemma, this is my first try, so I'll appreciate any hint in order to choose a word $x=a^pb^m$ with $p+m\geq n$ ($n$ from the lemma) which yields a contradiction.


texts: Forming polylines from a list of individual lines

texts:
I want to optimize a SVG path made entirely of lines. Given a list of lines, each made of two 2D points connected together, I want to find an equivalent list of polylines. For example:

M10,10 L20,10 M20,10 L20,20 becomes M10,10 L20,10 L20,20.One line ends where there other begins, it can become a polyline.
M10,10 L20,10 M20,10 L30,10 becomes M10,10 L30,10.The second line extends the first line, they can be merged into one line.

I found a basic way to do it in $O(n^2)$.

Start with an empty list of polylines.
Loop over all invidivual lines. If a point of the line is the same as one of the polylines head or tail, extend the polyline. If the slope between the new and last points is the same as the slope between the last and before last points, then only replace the last point with the new point.
Remove the line from the list.
Repeat until list is empty.

As you can guess this algorithm performs quite badly, taking forever with as little as 20,000 lines.

How to do it in $O(n)$?


texts:
Do functions with the following properties exists for x being arbitrary stream of bytes:

op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation and op is an easily computable operation
f(x) is fixed length of about 160-512 bytes
f does not need to be hard to revert, but should be useful at finding transmission errors or duplicates.

Could you provide any names/articles/pointers?


texts: Solve Travelling Salesman once you know the distance of the shortest possible route

texts:
I am trying to solve the TSP (Travelling Salesman Problem), but not in a traditional way. I am following these steps.

  1) First I change the TSP to a true / false problem.

The definition of this problem is now: "Is there a route by all the cities with a total distance less or equals than k?" Let's assume I have an algorithm TSP_tf(k) to solve it.

  2) Then I search the minimum k.

This is, I search "which is the distance of the shortest possible route".

An efficient algorithm to solve it would be with a dichotomic search. I begin with k=1, and I call TSP_tf(k). If it returns false, I multiply k by 2, and keep calling TSP_tf until true is returned. When this happens, search the minimum k that returns true in the interval (k/2 - k], also with a dichotomic search.

I will get then the minimum distance min_k.

  3) Return the shortest route of the TSP knowing its distance is min_k.

And here is where my question comes. How would be an efficient algorithm to solve this? By efficient I mean a good approach :) It is obvious that TSP will remain being NP.


texts: Proving that $a^{2^kp}$ isn't context-free (where $p$ goes over all primes)

texts:
I have this language and have to prove that its not context free:

$$L = \{a^{2^kp } \mid k \in \mathbb{N}, p \text{ is prime number}\}.$$

Because it's unary, a context free language is also regular, so it should be enough to prove that this language isn't regular.

Proving $a^p$ and $a^{2^k}$ aren't regular is simple. But how do I prove it with the "product" of these two?

My thought was, because $a^{2^k}$ isn't regular and also not context free,
if $a^{2^k}$ were regular/context free, concatenating this language $p$ times, we would deduce that the above language would also be regular/contextfree, because regular and CFL are closed under concatenation. But because $a^{2^k}$ isn't regular/context free, the $p$-times concatenation of this also isn't regular/context free.

Is my attempt correct?


texts: Regular expression with out the substring bab or abb?

texts:
I'm having a problem coming up with a regular expression for a language L = {a,b} with out the substring bab or abb?
I can come up with the one for just one substring, like

a*(b* aaa* )* b* a* to eliminates the bab and b*(a+ab)* to eliminates the abb substrings.

But putting them together is a huge animal :(


texts: Dynamic programming: how to solve a problem with multiple constraints?

texts:
I've got a real-world issue that I'm trying to come up with a dynamic programming algorithm to solve. It's similar in appearance to the knapsack problem, but it has more constraints, which has got me stumped. A simplified version of the problem:

Suppose I need to fill a basket with an arbitrary number of items c. The items have four properties: w, x, y, and z, each of which has a positive or negative number, with z being equal to the mean of the other three properties. My goal is to pick items such that the average z of my c items is at a maximum, but also

min(avg(w), avg(x), avg(y)) > d

for some arbitrary value d.

So, for example, c items each with w, x, and y (respectively) of (1000, 1000, -1), would have a very high average z (666.3), but would fail the second constraint if we set d >= 0, as the average y is -1.

The input would be the set of items from which to choose and the values of c and d, and the output would be a list of the c items I need to select to make the optimum full basket. Note that an item can only be selected once (no duplicates).

As I mentioned, I can see an obvious similarity to the knapsack problem, but I'm having trouble wrapping my mind around how to modify its basic structure to account for these different constraints. Or perhaps I am barking up the wrong tree trying to use the knapsack problem as a model?

Any input/pseudocode would be appreciated!


texts: Consequences from a lower bound of SAT problem

texts:
I'm not sure how lower bounds affect the question to the P=NP problem.
I.e. :
Let a SAT instance with a size of n be transformed into an instance of a problem X with a size of n3.

If you find a lower bound of the SAT problem which is
$$\Omega(c^n) \ \ \ \ c > 1 $$

What would be the consequence to the problem P=NP?

We already know that SAT has an at exponential lower bound time complexity. But what would be the complexity of the problem X? Will it be $$\Omega((c^n)^3)$$

Will X's complexity affect the problem N=NP in any way? (assuming that the lower bound for SAT exists).

My thought are that since SAT is NP-complete there should be no problem in having an exponential lower bound.
Any thoughts?


texts: Is a LBA with stack more powerful than a LBA without?

texts:
Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful.

A LBA with stack should not be Turing complete, because its halting problem should be decidable. (It seems to be equivalent to the halting problem for a PDA).

Can a deterministic LBA with stack decide all problems decided by a nondeterministic LBA?

Or on the other hand, maybe a LBA with stack is (provably) not more powerful than a LBA?

Edit I think I found out how a deterministic LBA with stack can simulate a nondeterministic LBA. The stack can be used to store and recall the current state of the external memory (the linear bounded memory) as often as needed. The internal state is finite, so there is a global bound for the maximal number of nondeterministic moves available in a single step. So backtracking can be used to recursively simulate the result of each nondeterministic move.

I will have to think about how to make these two observations (halting problem is decidable, nondeterministic LBA can be simulated deterministically) more rigorous, before self-answering. I'm away next week, so don't hold your breath.


texts: Language is non-empty is recursively enumerable (intuitive way)

texts:
$M$ is some Turing machine, $\left<M\right>$ is the code of the Turing machine.

$L =\{\left<T\right> | L(T) \ne \emptyset\}$

How to see intuitively that $L$ is partially decidable?

We can try running a given $M$ on all strings and accept if $M$ accepts.
However, what if the simulated $M$ gets into an infinite loop?


texts: Algorithm to enclose a 2D-gridbased-room efficient

texts:
I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort.

Here a little Example:

In this example black squares are not passable, white ones are and the ones with the arrows are the exits that should not be able to be reached.

I wan't to enclose the yellow square by converting white squares into black ones. I want to use as few conversions as possible.

Two ideas I found until now:

1 The fastest algorithm in my opinion would be to just convert all squares around the exits but it would not be the most efficient algorithm since in this example it would cost 9 conversions (13 if diagonal movement is possible) but its possible to enclose the yellow block with only 3 (5) conversions.

2 I found the Flood fill Algorithm, which would enable me to check if the area around the yellow square is enclosed but I can't think of a (cpu-)efficient method to try out possible conversions until I find the solution with the least conversions needed.

The Method should be able to enclose more then one targets, since otherwise an optimal solution would be often to just enclose the yellow block with 9 conversions around him. Therefore I added to my picture the green block, so the algorithm should be able to enclose all targets.

If you don't have an idea how to solve it but a hint where I could look into to find a possible solution I would be happy to hear it!

Thanks,
Niko


texts: Is there a largest class of halting programs?

texts:
The halting problem says that a Turing machine cannot decide if another Turing machine halts.

However, we know that it is possible to determine if some programs halt. For example, FORTRAN DO statements are simple to formally verify. FORTRAN is however not Turing complete.

What is the largest subset or class of halting programs that can be decided?
Is there a class of such languages?

This blog entry
seems to hint at the fact that since the compiler optimized the code by eleminating the while(1) loop, Fermat's last theorem is disproved by a compiler.


texts: Finding the closed form of this recurrence

texts:
We have the following recurrence $T$:
  $$
T(n,k) = \left\{
        \begin{array}{ll}
            \alpha n^2 + \beta n + \delta & \quad \text{if }\; n \le k \\
            T(\lceil n / 2 \rceil, k) + T(\lfloor n / 2 \rfloor, k) + \gamma n + \zeta & \quad \text{if }\; n > k \\
        \end{array}
    \right.
$$

  for all positive integers $n$ and $k$

I want to find a closed-form of $T$.

I at least know that when $n > k$, then

If $n$ is even, then $T(n,k) \;=\; 2T(\frac{n}{2}) + \gamma n + \zeta$
If $n$ is odd, then $T(n,k) \;=\; T((n-1)/2) + T((n+1)/2) + \gamma n + \zeta$

Usually I would enter a range of inputs $n$ to find a pattern. However, there are so many constants here, I cannot find a consistent pattern to get a closed-form.


texts: Proving that Max Weighted Independent Set is in NP

texts:
What I'm trying to do is to show a problem in NP can be reduced to the min weight vertex cover problem

I've chosen the max independent weight problem =
input: A graph G with weights on each vertex,
output: An independent set with the max total weight

Before reducing, I've tried to show that the max indep. weight problem is in NP (which is usually the first step in these reductions). I'm trying to construct a verification algorithm for this problem; but I'm stuck on trying to show that the verification algorithm can check if a certificate is the max indep. set in polynomial time.

Any guidance or comments would be greatly appreciated.
Thanks


texts: NP-completeness of a problem with pretty fast algorithm

texts: Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?


texts: Split a list of numbers into multiple groups, constrained by a maximum range, while minimizing variance in resulting lists

texts:
Problem:

Given a list of numbers, and a single number representing the maximum range in a list, break that list up into the fewest lists that can fit all numbers, while grouping such that each list has the lowest variance possible.

Examples:

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, with a max range of 10 can be returned as is since 10-1 is 9 which is less than 10.

With a max range of 5 it could be grouped as {1, 2, 3, 4, 5, 6}, {7, 8, 9, 10}, but since the variance could be minimized should be returned as {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}.

A more real world example of the data this algorithm might be processing (though still vastly simplified) would be: {50, 45, 55, 50, 10, 15, 95} with a max range of 10.  Which should return {50, 45, 55, 50}, {10, 15}, {95}.

Thoughts:

I'm really struggling with determining the 'center point' for each list.  Dividing the lists into a minimum number of possible lists would be fairly easy by iterating from 1 and incrementing, but those resulting divisions seem useless because I can't determine if they're the best possible groupings.


texts: DAG Shortest Path -- original citation for academic paper

texts:
I am writing to see if someone can point me to the original citation (assuming that a single work can be pointed to) for the single-source shortest path problem in directed-acyclic graphs (DAGs). Below is one candidate citation, which I came up with after digging around on google scholar (somehow, though, 1977 already seems a bit late):

Donald Johnson. 1977. Efficient Algorithms for Shortest Paths in Sparse Networks. Journal of ACM

As a more general point and question, I always find it quite hard as an outsider (I work in machine learning) to navigate the graph algorithms literature, given the interdisciplinary nature of the field. I imagine there might be some paper prior to the one cited above from pure maths or physics that uses non-standard notation (from today's standards), which makes it hard to verify that the algorithms are the same. Perhaps it makes sense to cite earlier review articles, such as the one above, that use modern notation (in which case, I can maybe just stick with citing Cormen). I'm curious what others think.


texts: Calculating Time Complexity of Quadratic Diophantine Equation

texts:
The particular quadratic Diophantine equation:

$$
R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY - c = 0
$$

is NP-complete. (a, b, and c are given in their binary representations. a, b, c, X, and Y are positive integers).

Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Quadratic Polynomials. STOC 1976: 23-29

Since, I do not have the access to the stated paper, can someone help with how the time complexity (clearly exponential) varies/depends on the size of a, b, and c?


texts: What is Pumping length for Union of Regular languages?

texts:
This is an exam question.
For E = {a,b}. let us consider the regular language
$L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$
Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
A)3
B)9
C)5
D)24
Ans is 24.
As per me pumping length is the length which gets actually repeated.
So, basically it's the length of y as per pumping lemma statement.
Now, for the first regular language, $a^{2+3k}$
How I visualized?
There would be sure 2 states which accept min 2 'a' ( since k>=0).
Now, then I have $a^{3k}$
Means, which should definitely have a loop of length 3.
So, I choose x=2 (first 2 states) y=3 (the repeating part) and z=0.
So this first language must have atleast 3 as the pumping length.
And in similar lines the other must have. Atleast 12 as pumping length.
(X=10, y=12, z=0)
And that's why as per me 24 is right.
(Still sketchy at concluding)
Plz tell me if my understanding of Pumping length is right?
If no plz try suggesting some links/references.
If yes then have I applied the Concept right?


texts: A vector-like data structure with allocation table; O(1) indexing time required

texts:
I am a beginner in data structures and recently came across a vector implemented on an array, which is extended on demand. Of course the table cannot be extended "in place", we must allocate a new array, then copy elements from the previous one which is a linear operation itself (invoked log(n) times, where n is the number of insertion operations). Are there better implementations of such data structure while preserving constant item access time? For example, how about implementing a concept known from disk file systems - an allocation table; whenever we need to extend our array, an allocation table entry is created for newly reserved memory, without touching previously inserted items. Indexing time could still be constant, if only the allocation table would be implemented wisely (for example with using constant "page" size)
What I've written could be complete nonsense; it's just an idea.


texts:
Is there any example of any natural problem which is known to be in MA, but not yet to known to be in NP?

I am aware that Graph Nonisomorphism (GNI) is known to be in AM which is considered a superset of MA. Can we construct a language (which may be non-natural) which is in MA, but not in NP?


texts: Can somebody explain the characteristics for a BFS Tree from a complete graph?. Thanks in advance. I would need the shape of the tree, explain me a little bit how the algorithm would work in this certain graph


texts: "Huffman coding is unsuitable for text files"?

texts:
My lecturer for information theory says that "Huffman coding produces efficient codes but is unsuitable for text files where the letters are represented by a fixed length ASCII code".

I do not understand this statement. I understand that as you change the text file, you'll have to update the probabilities and thus the Huffman table/code itself but I don't think this is what is being referred to here.

Can someone explain?

Thank you so much for all your help


texts: Reverse An Array whats wrong with this type of code?

texts:
import java.io.*;
import java.util.*;
public class reverseAnArray2
{
    public static void main(String args[])throws IOException
    {
        Scanner sc  = new Scanner(System.in);
        System.out.println("Enter size");
        int  n = sc.nextInt();
        int a [] = new int [n] ;
        int b [] = new int [n] ;
        System.out.println("Enter elements");
        for(int i=0;i<n;i++)
        {

            a[i]=sc.nextInt() ;
        }
        int size = n;
        System.out.println("Reverse array is : ");
        int p=0;
        while(n>=0 && p<n)
        {

            a[--n] = a[p] ;
            ++p;
        }
        for(int i =0;i<size;i++)
        {
             System.out.println(+ a[i]);
        }

}
}

The output comes correct but only up to the last $n/2$ terms, rest of it gets repeated. The output was correct when I used another fresh array to store data. But that's not an optimal code. I want to reverse it without using another array.


texts: Necessity of convolution operations for product of two polynomials via brute force method

texts:
Reference: Page 4 of this document

Given two polynomials $p(x)$ and $q(x)$ each of degree $n$ represented in coefficient form, it takes $\mathcal{\Theta}(n)$ time to evaluate given some input $x$.

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} \right)$ which takes $\mathcal{\Theta}(n^2)$ time.

However, if we wanted to evaluate this product with some given input $x$, we can evaluate the two polynomials $p(x)$ and $q(x)$ separately and then multiply the two scalar results. Overall, this would take $\mathcal{\Theta}(n)$ time for two evaluations and a scalar multiplication. This lets us avoid having to do convolutions and would be faster than $\mathcal{\Theta}(n^2)$.

Question: When it comes to evaluation of the product of two polynomials, is it actually $\mathcal{\Theta}(n)$ using the method above or are we somehow still doomed to $\mathcal{\Theta}(n^2)$?

I'm aware there's a faster way to do this in $\mathcal{O}(n \log n)$ time via Fast Fourier Transform, but I'm more curious about the necessity of the convolution calculations. I suspect it's more if we care about getting the coefficients of the product than the actual evaluation, as in we more care about knowing $\{c_0, c_1, c_2, \dotsc\}$ than $c(x) = p(x)q(x)$.


texts: Results on number of solutions to random 3-SAT?

texts:
I'm looking for some published results, either empirical or theoretical, on the number of solutions to random 3-SAT problems.  Given $N$ variables and a clause-to-variable ratio $\alpha$, how does the number of solutions to 3-SAT scale vs. $N$ and $\alpha$?  What is the distribution of the number of solutions?

Thanks!


texts: From the above image, while trying to maintain an AVL tree data structure, how would the tree look after inserting the value 10? Also, if anyone has any suggestions or simple method of rotating, feel free to share. I am a bit lost with this idea of maintaining a certain height in this data structure.


texts: Is Mersenne primality testing necessarily EXPTIME?

texts:
The computational complexity of primality testing is usually specified in relation to the bit length of the number being tested.

However, Mersenne numbers have the special property that the characterizing instance exponent $p$ is exponentially more succinct than the number it signifies. Surprisingly, most of the literature I've found appears to assume a unary representation of $p$ rather than binary.

The Great Internet Mersenne Prime Search, for example, aims to identify very large Mersene primes via an optimized distributed Lucas–Lehmer primality test. GIMPS as a virtual computer has at times ranked among the TOP500 in terms of expended computational capacity.

So is all this distributed computing truly necessary? Do we really need to expand $p$ to its verbose representation to verify its primality?

Or is there still a possibility that primality testing for Mersenne numbers could be decidable in polynomial time in the size of the instance $p$ via some clever certificate tree?


texts: How are programming paradigms classified?

texts: When I started to learn about imperative programming and declarative programming it raised many doubts, like, how are structured, modular and object-oriented programming classified: declarative or imperative?


texts: Turing machine that accepts $L = \{a^{n^2}|n\geq 1\}$

texts:
I have the following language:
$L = \{a^{n^2}|n\geq 1\}$
Hey i have been stuck on this problem for a few days now and even going through sample problems in my textbook as well as sample solutions i cant figure out how to make this turing machine to work.
I know it may be a vague question but i really could use some help figuring this one out.
Thanks in advance!


texts: Showing that a language is not recursive

texts:
I was given the next function CH(x) that is defined like this:

$CH(<M>)$ outputs the computation history of the run of M on epsilon if M halts on epsilon. If it doesn't the function returns epsilon.
 I was asked to prove that the language

{$ M, CH(<M>) |$ M  is a turing machine } is in co-RE\R

I can't seem to understand why the language isn't recursive enumerable
I do see why it's not in R (The halting problem becomes decidable)


texts: Finding context free grammar for this language?

texts:
I needed help finding the context free grammar of this string

$$
10^{n}10^{n}1
$$

So far an idea I have is
$$
S\rightarrow 1S1S1\mid 0S \mid \varepsilon
$$

Any assistance you can provide would be greatly appreciated!


texts:
I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent.

Then $P(A=B)=1/2+1/2\times 1/2=3/4$, so $P(HH)=P(TT)=3/8$ and $P(HT)=P(TH)=1/8$.

Total information is then $E(-\log_2 p) = 1.81$.

Therefore mutual information is $H(X)+H(Y)-I(X;Y)=1+1-1.81=0.19$ bits.

Is this correct? Because intuitively in this case one might expect, as 50% of the times the coins are equal, the mutual information is $0.5$ bits.

Is there any simple intuition why it is less than $0.5$ bits?


texts: What does the "principle of deferred decisions" formally mean

texts:
I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my understanding, it seems to be an intuitive way of using conditional probability:

$\Pr(\bigcap_{i = 1}^{n} E_i) = \prod_{i = 1}^{n} \Pr(E_i | E_{i-1},\dots,E_{0})$ where $E_0 = \emptyset$.

Is my understanding right?


texts:
Given a DAG N, if an edge $(U \rightarrow V)$ is added between any existing nodes U and V. Then, by performing DFS from the node $U$ and checking whether there is a cycle or a not, should be sufficient to conclude that this addition of edge didn't violate the acyclic property of the given DAG. Is it correct?

Or there is a need to perform DFS from other nodes in the network to verify the cyclic property of DAG?

Trying to find the most efficient way to verify whether addition of an edge to an existing DAG introduces cycles or not?


texts: Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm?

texts:
The following algorithm for computing the number of nodes in a linked list appears in this thesis on common algorithms in the PRAM model for parallel computation.

The author then argues that this is a $log(n)$ time algorithm (where $n$ is the number of nodes in the list) because the span of nodes covered by the "far" pointer doubles on every iteration of the innermost loop. What I don't understand is why the author doesn't seem to factor in the time required for the first two lines of code after the begin statement, where a processor is assigned to each node in the list. Assuming the input to the algorithm is just a pointer to the header node to the linked list, wouldn't the assignment of processors require traversing each node in the linked list and thus take time linear in $n$? After all, each node in the linked list may be stored in some highly non-contiguous locations in memory identifiable only by following the chain of pointers from predecessor nodes in the list one at a time.


texts: Should Kolmogorov complexity include all resources or just program size?

texts:
I've been thinking about pi and Kolmogorov complexity (Kc).

As the digits of pi are randomly distributed (and infinite) , they can't be compressed with a typical compression program.  Through the prism of Kc, it would seem that a generating program (e.g. Gauss-Legendre algorithm) is much smaller than the output sequence hence characterising pi as not random.

The usual semantics revolving around Kc only mention program size so the above definition holds.  Running the Gauss-Legendre algorithm comes at the cost of huge storage, processing power and some electricity.  These resources increase (towards infinity) in some relation to the number of digits generated.  If Kc is redefined as overall resources and not program size, pi becomes random.

Should Kc be restated as being resource based and not solely program size based, or is that an abstraction too far?

P.S. This is not a question of whether pi is random, but about a definition of Kolmogorov complexity.


texts: Regular expression notation clarification

texts:
For the alphabet $Σ$={a,b,c}

I was wondering how you would say:

  T that has elements from Σ, so could be T=a, T=bc

I was considering maybe $Σ^*$ or $Σ^+$ would describe that, but I am not sure what both of them mean.

I guess $Σ^*$={aa, aaa, ba, abc, ...} and not sure what $Σ^+$ is.


texts: Non repeating pseudo random number generator for a dynamic range

texts:
Algorithms like Knuth's algorithm or this one, works for a range that is known in advance(like shuffling numbers 1 to 11), in this case the range will never change. You'll always get a random no. between 1 to 11.

But in my case the range can increase like if the generator generates 2 random numbers {3,5} from the range 1 to 11, and then the range becomes 1 to 13, the next random number should be from this new range but shouldn't repeat 3 or 5.

Is it possible without making a large record of every used number and then iterating to find out if it is unique or not.

Edit:

If I have to find a random number between 1 and 11 I can easily shuffle these numbers and pick them by index 0,1,2,... and I'll get non-repeating pseudo random numbers. But after picking 3 index from the list that can be 3,5,4 and after this, the algorithm have to find random numbers between 1 and 13.

Now If I reshuffle the new list that contains numbers 1 to 13. There is no guarantee that the generated numbers will not repeat. and if I simply append these 2 numbers (12,13) to the shuffled list of numbers 1 to 11, they are not random.

Is there a way to still get the pseudo random numbers without repetition?


texts: N-Dimensional method lookup: sender vs context

texts:
So, there is an idea about multi-dimensional behaviour selectors that goes like follows (based on paper by R.Hirschfeld and P.Costanza : "Context oriented programming"):

"selector": in 1D lookup we only have a name for our behaviour, which directly selects the function (i.e. in procedural languages, like C)
"selector", "target": 2D lookup is classic OOP. Which method is being executed is also specific to the target, i.e. obj_instance.method(args) - obj_instance (the prototype of that, or, usually, the class) selects the appropriate method to execute based on the selector supplied by sender (method name)
"selector", "target", "sender": This confuses me. Why would selected method be dependent on WHO asked to execute that method? How this can be useful, when the sender (the current method body) usually "knows" what method should be executed, as this is usually the programmers intent.
"selector", "target", "sender", "context": this confuses me a lot more! I've seen the examples on this and I cannot comprehend why sender != context.

Could anyone elaborate on practical differences between 3 and 4 dimensional method lookup?

(asking this on CS exchange as this question is more research-related than a practical one)


texts:
I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point.

I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot (15) into its appropriate position.

Example: [15, -7, 22, 7, 21, 34, -13, 19]

My understanding:

15, -7, 22, 7, 34, -13, 19
#   ^                   ^

Move left-pointer to first element larger than the pivot. 1 comparison (move to 22).
Move right-pointer to first element smaller than the pivot. 1 comparison (move to -13).

15, -7, 22, 7, 34, -13, 19
#       ^           ^

Swap elements at the pointers (22, -13).

15, -7, -13, 7, 34, 22, -13, 19
#       ^           ^

Move left-pointer to first element larger than the pivot. 2 comparisons (move to 34).
Unable to move right-pointer to first element smaller than the pivot (cannot past the left-pointer.

15, -7, -13, 7, 34, 22, -13, 19
#               ^   ^

Swap elements at the pointers (34, 22).

15, -7, -13, 7, 22, 34, -13, 19
#               ^   ^

This is where I am stuck. My understanding is that the pivot should then be swapped with 22, but that doesn't seem correct?

How do I move the pivot (15) into its appropriate position?


texts: Construct Turing Machine which accepts the language $ww$

texts:
I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$.

Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second $w$ begins.

Is there a trick for this?


texts: Application for large graphs compression

texts:
I am looking for an application in which it is desired to perform an efficient lossy compression of very large graphs, that preserve the general structure of the graph but may delete some edges.
Can you think of any such applications?


texts: Do the "virtual memory"s mentioned in the 2 articles refer to different things?

texts:
I've read the following 2 articles explaining the difference between virtual memory and physical memory. One thing that I found confusing is that the term virtual memory seems to mean different things in these 2 articles.

What Is the Difference Between Virtual Memory & Physical Memory? says Virtual memory is used when the RAM is filled.

While Wikipedia says virtual memory is used to tell programs where the physical memory is.

Is one of the articles wrong? Or does virtual memory have different meaning in different context?


texts:
How do I derive a regular grammars from this regular expression?

(a or b)*ba(ba)*

I'm stuck with the last part
so

S -> A | B | C
A -> aA | bA
B -> bC
C -> cD
D->bE ?
E->af | ^ ?

Any help would be appreciated thanks!


texts: Regular languages and constructing a regular grammar

texts:
I'm pretty new to computer science and just read about the concept of grammars. Now, I have a practical problem to solve. Here is the alphabet {a, b, c, d}.

How can I determine if the language consisting of all strings a^k b^n c^m d^l, where all k,n,m,l >= 1 is regular. I need to do this because as far as I got all regular languages may be parsed by a regular expression. So, to avoid generating my own parser and lexer, is it possible to do so?

My first attempt was to construct a regular grammar generating the language. I failed, but that doesn't mean that the grammar does not exist. I would appreciate any advice.


texts: Finding recurrence relation for running time of an algorithm

texts:
I am pretty new to this, consider the following algorithm:

Calc_a(n):
    if n ==1: return 1
    else:
    sum = 0
    for i=1 to n-1:
        sum = sum + calc_a(i)
    return sum

So after running this algorithm a few times I see it basically finds the n'th element in a sequence defined by this recurrence relation:

$a_n = \sum_{i=1}^{n-1}a_i $

I need to find the recurrence relation for this algorithm running time per input. Walk me through it :)

Lets define running time as $T(n)$.
So the base case n=1 is $O(1)$ (theta?), as we just return 1.
Then we iterate (n-1) times , each time performing addition and calling the function on the current index, this is where I get confused.
I know how to deal with loops and recursion individually, not together.

My homework specifies that I should use constants rather than asymptotic notations. Does that means I should define the running time of Calc_a(i) as some constant?

How should I go about this?

*** EDIT ****
The answer I've come up with:

$
T(n) =
\begin{cases}
1,  & \text{if $n = 1$} \\
\sum_{i=1}^{n-1}( T(i) + B) & \text{else}
\end{cases}
$

For some constant B.


texts: On FPTAS and many one parsimonious reductions

texts:
We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose  $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction.

If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have?
If $\Pi_2$ has an FPTAS then does $\Pi_1$ also have?


texts: Closure of CFL against right-quotient with regular languages

texts:
Let $A/B$ = $\{ w \mid wx \in A$ for some $x \in B \}$.  Show that if A is context free and B is regular, then $A/B$ is context free.

My interpretation of this is is that we need to show that if a string $wx$ is accepted by a CFG, and we know that $x$ is accepted by a regular language (and therefore is also accepted by a context-free language), then $w$ must also be accepted by a CFG.

My initial thought on how to solve this would be a proof by contradiction in which we assume that $A$ is context free, $B$ is regular, and then assume that $A/B$ is not context-free.  Since $A$ is context free, we can construct an equivalent PDA that accepts $A$.

From here, my thought was to take an arbitrary $wx$ that is accepted by $A$, such that $x \in B$.  We can then construct another PDA based on the first that only accepts $wx$.  We could then break the PDA into two pieces: one that accepts $w$ and one that accepts $x$ (with the two pieces concatenated together).  Since there then would exist a PDA that accepts just $w$, and $w$ is arbitrary insofar as $wx$ was arbitrary, $A/B$ must therefore be context-free after all (contradiction).

Will this approach work? (Is this a good general approach?)  If so, how would I go about breaking the PDA that accepts $wx$ into chunks formally?


texts:
I am a self taught programmer, with no formal degree in CS. I have read couple of papers which were recommended on some or other blog and found them interesting. Where can I read papers on computer science ? Are these papers available for free?
If not papers are there any essays on any popular blog posts?


texts:
I am collecting data from a sensor over time, and I'm trying to figure out how to detect "events" in the data - specifically, when a given event begins and ends. The frequency, duration, and amplitude of these events varies.

Rather than using some rules-based scheme that proves to be rather ineffective, I want to train a model to detect these events for me. An example of my data (in only one dimension; I have multiple variables that I'm reading) looks like this:

There's one event here and some baseline data on either side.

My raw data before and during this event looks like:

1/1/2016 12:48:03   14.2
1/1/2016 12:48:04   12.8
1/1/2016 12:48:05   13.6
1/1/2016 12:48:06   13.5
1/1/2016 12:48:07   12.9
1/1/2016 12:48:08   15
...
1/1/2016 12:48:34   27.7
1/1/2016 12:48:35   30.3
1/1/2016 12:48:36   31
1/1/2016 12:48:37   32.8
1/1/2016 12:48:38   31.1
1/1/2016 12:48:39   28.7
1/1/2016 12:48:40   32.1
...

I have training data consisting of raw readings and timestamps that I can correlate to a truthset of event start and end times, but I don't know how I should go about featurizing to build a model. I assume I would keep a window of, say, 30 seconds or a minute of readings. (Events are typically more than a minute long, but I don't know whether I would need my window to contain the entire event.)

I'm familiar (but not an expert) with regression and boosted trees, and I know of tools that can generate code I can use without third-party libraries. But I don't know whether these are feasible approaches to solving my problem.

How can I go about detecting these events?

Edit: After some discussion, I've created the following graph to show what more data might look like from different signals. The duration of the manually labeled event is in blue (using the right axis labeled 0/1). Three signals show up strongly:

Red covers the overall event reasonably well and is essentially the above example
Purple-blue has an even stronger signal but only for the first half or so of the event
Yellow-green has a stronger signal than reed for maybe a third of the event, but basically after purple-blue dies off.

Some signals (eg, the bottom-most orange on the left side) have an increase during the event. These either have a weak signal that should be captured or have no signal; however, it's not obvious whether any correlations between these signals and events exist, and if so, how to extract them.


texts: What does normalizing with hidden bit really mean?

texts:
I have  a question related to representing numbers in base 2 with floating point. For example, if I have such a number $$0.000011 \cdot 2^3$$ then is its normalized form this?
$$1.1\cdot 2^{-2}$$
Generally speaking about normalizing, normalizing with hidden bit, does it imply that the first number of mantissa should always be zero, or does hidden bit just mean that a "one" should be taken left to the point?


texts: Are there any systems that operate primarily by punch cards (loading/saving data) in production usage today? (Or at least up to the year 2000?)


texts: Context-free languages not closed under making them "extension-free"

texts:
For a language $L$, define:
$$
NE(L) = \{x \in L : x \text{ is not the proper prefix of any string in } L\}
$$

I'm trying to show context-free languages are not closed under this operation.
I've been struggling for a long time now trying to find a counterexample, that is, a language $L$ such that $L$ is context-free but $NE(L)$ is not context-free, and have come up with nothing. I'd appreciate ideas or hints about languages to look into.

Edit: For the vast majority of context-free languages, it seems that either $NE(L) = L$ or $NE(L) = \varnothing$. I'm having trouble even finding candidate languages.


texts: Do approximation results for CSPs hold even when domains are of finite but different size?

texts:
We need to have a precise definition for what a constraint satisfaction problem (CSP) is to study it formally. Looking at a survey by Libor Barto, titled "The Constraint Satisfaction Problem and Universal Algebra", a definition is given in Definition 2.1. Further, it is claimed this is a "standard formal definition of an instance of the CSP over a finite domain".

In particular, the definition says a CSP problem is a triple $(V,D,\mathcal{C})$, where $D$ is a finite domain. In other words, every variable takes a value from the same domain. Tracing back some earlier references from the survey, many papers define $D$ in the same way (i.e., it's the same for each variable).

I'm interested in a definition where each variable $x_i$ has a finite domain $D_i$ of size at most $k$, for some constant $k$. Surely when CSPs are defined like this, it's still NP-complete to decide whether there's a satisfying assingment, and NP-hard to maximize the number of constraints satisfied.

But: can one safely assume approximation results still hold for this definition? More generally, are there approxation results (or other algorithmic results) that break down when domains are of size at most $k$ instead of exactly the same for each variable? It feels strange the "standard formal definition" is not allowing this, so it makes me wonder if there's a reason for this limitation of generality.


texts: Why does the concatenation of the empty set with any language give the empty set?

texts: Why does the concatenation of $\emptyset$ with any language give $\emptyset$. I would like to know the intuitive explanation for it.


texts: CFG with regular expression terminals on RHS

texts:
Suppose that we expand our idea of context free grammar rules to allow regular expressions of terminals on the right hand side. For example, consider $G_1$:

$\begin{align*}
S & \rightarrow (a \mid b) S (c \mid d) \\
S & \rightarrow (a \mid b) A (c \mid d) \\
A & \rightarrow (f \mid g)^*
\end{align*}
$

Then the language of $G_1$ is the following:
$$L(G_1) = \{(a \mid b)^n (f \mid g)^* (c \mid d)^n \mid n > 0\}$$

Give a standard CFG that has the same language as $G_1$, is your grammar weakly equivalent to $G_1'$, strongly equivalent to $G_1'$, or both? Why?

Secondly, how can I transform any CFG with regular expressions of terminals on the right hand side to a normal context free grammar?


texts: Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

texts:
I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }.

This is really confusing me, I'm having trouble with making sure that b is always in the middle. Any help?


texts: Trying to find two CFGs for the following languages

texts:
I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet:
$L = \{ a^kb^ra^m | m=k+r\}$
$L = \{ a^nb^m | 1\leq n\leq 2m\}$
With the first one, I thought of this:
$$S\rightarrow aSa | T$$
$$T\rightarrow b T a | \epsilon$$
but what if $k>r$ or $r>k$?
With the second one, I think it is really simple but I cannot wrap my mind with $1\leq n\leq 2m$ (maybe I'm special...), should I have at least as many $a's$ as the double of $b's$ but not strictly? how could I specify that?


texts: Why does Shellsort work well on Sorted and Reverse ordered lists?

texts:
I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists.

Results:
        Random Reverse Order AlmostOrder
  time    24      5      4        29

The problem that is confusing me is that Shellsort performs insertion sorts on lists separated by gaps, and insertion sort only runs very fast on ordered lists, not reversed lists.

So my question is why does Shellsort work well on ordered and reversed lists when it uses insertion sort and insertion sort doesn't work well on reversed lists?


texts: Operating System: Busy waiting is not eliminated with semaphore?

texts:
Why the busy waiting is not eliminated even after we put the current process into the process list and "block()"ed it? So even if the process is in waiting state we still call it "busy waiting"?

I'm reading Operating System Concepts, Silberschatz, 9th ed., pages 215~217.


texts: What is the difference between the choice operator and nondeterminism in CSP?

texts:
I'm learning CSP now for my research. First time doing formal work in CS. I'm having a hard time understanding the difference between choice $\square$ operator and the nondeterminism $\sqcap$ operator. Does the former perform a completely deterministic choice only based on the inputs from the environment, while the latter can make a nondeterministic choice arbitrarily?

My book says that $(a \rightarrow P) \space \square \space Stop $ is not the same thing as $(a \rightarrow P) \space \sqcap \space Stop $, because the former is the same as $P$, but I don't see how that is if $P$ cannot decide to stop based on an input.


texts:
Given a graph with $n \leq 50 $ vertices. Count all $k$-cliques of this graph, where $k = 1, \ldots , n$.

I need the most efficient algorithm.