texts: How to maximize $f$ while minimizing $g$ at the same time?

texts:
Lately, I have been dealing with a problem that I didn't know how to name it to solve it properly.

The problem is as follow: let's assume that we have a set of elements $A$. And, we have two functions $f$ and $g$, where for any sub-set $B \subset A$ where $\left|B\right| < k$, $k$ is a constraint:

$f(B)$ : estimates the gain obtained by the set $B$.
$g(B)$ : estimates the loss obtained by the set $B$.

In our problem we have two strategies $S_1$, $S_2$ which depend on the circumstances of the environment

$S_1$: selects a set $B_1$ that maximizes the gain
$S_2$: selects a set $B_2$ that minimizes the loss

my strategy is a hybrid strategy selecting sets $B_1$ and $B_2$ where $\left|B_1\right|+\left|B_2\right|<k$, and we aim to maximize the gain and minimize the loss at the same time.
My problem would be: $(max(f(B_1)), min(g(B_2))) s.t. \left|B_1\right|+\left|B_2\right|<k$

NT: given that there are several circumstances sometimes $S_1$ works more efficiently, and some cases $S_2$ works better

Is there anyone who knows what type of problem? Any documentation about it? Since it is an NP-hard problem, is there a way to find an approximation with in the optimal solution?


texts: Interval Scheduling problem with more than 1 machine

texts:
There are 2 machines.
Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine
The list of n tasks are given in [start time, end time], both of which are on top of hours. If we were to order the tasks by non decreasing end time the maximum would be D, but the list given is not sorted.
There is no value difference (1 machine and 2 machine tasks are considered same value). Just schedule as many tasks as possible. Want to find an algorithm that runs within O(nD^2) time
I'm considering DP but can't really get my head clear on how to approach the question. Any suggestion would be helpful.


texts: Why is the base used to compute hashes in Rabin–Karp always primes?

texts:
The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is
$$ h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i, $$
where $b$ is prime (all computations are module $2^w$, where $w$ is the width of a machine word). Why is it important for $b$ to be prime?


texts: Algorithm for finding all the combinations on a boolean array

texts:
I have to design an algorithm to do the next task:

I have one array of booleans. For example:

Array:   [0 1 0 0 1 0 1 1]

I want to obtain all the existing combinations of 1's, having in mind that it is allowed only a maximum of one 0 between 1's.
For example, in the previous case, we would have the outputs (I am using the indices now):
[1] and [4,5,6,7].

But also it should include [4], [6], [7], [4,5,6], [6,7].

Another example:

Array:   [0 1 0 1 0 1 0 0 1]

The output would be: [1], [3], [5]. [8], [1,2,3], [1,2,3,4,5], [3,4,5].

Can you imagine any approach to solve this? The combination explosion could be quite big.

Thank you very much in advance.


texts: Is the language of words with equal number of 010s and 101s as substrings regular?

texts:
Is the language of words containing same number of 101s and 010s regular?
If yes, how can I design a DFA for it?

In general, is the language of words containing equal number of strings which one is "one's complement" of the other one is regular (like the language of words containing equal number of 01s and 10s which is regular)? Is there any counterexample?


texts:
I'm writing a paper for some software that uses combinatorics to generate large result sets. I would like to describe that if I put in $n$ elements, I will get in return $2^n$ elements.

Is there a software metric that describes "data growth" for an algorithm or do I simply write "the data grows exponentially"?

btw: The size of the $2^n$ elements varies , so I cannot determine their size (storage)


texts: sorting a sorted array that has been inc/dec by random numbers

texts:
If given a sorted array of n distinct positive integers. And each element is incremented or decremented by a number between 0 and X. For positive integer X that is a function of n.

Formulate an algorithm that takes the inc/dec array and sort it. Make the run time O(n) when X is constant.

I am unsure with my solution. Firstly, I just choose an random number of buckets... 10. The proof seemed to work out. Is there a way to prove that using X(the variable from above) number of buckets will be better?

In addition, is there a way to utilize the fact the array has been sorted prior to being augmented?

My solution:

1.  Find the minimum and maximum of the array by iteratively going through the array

O(n)

2.  Create intervals for the k buckets (k = number of buckets)
int interval
int k = 10
interval = (Max – Min + 1)/k

3.  Assign each element to the bucket based on the interval
O(n)

4.  Sort each bucket
if there is ni elements in each ith bucket
the sorting using randomized quicksort S(ni) = O(nilogni)

5.  Combine all the elements
O(n)
Runtime Analysis:
•   The time to sort every bucket will be as follows:
•   We assume the elements are uniformly distributed. Thus n/k elements in each bucket.

Since k = n/10, T(n) = n log(10) = O(n)


texts: Minimum number of edges to add such that there are no bridges on a tree

texts: Any edge of a tree is a bridge. What is the minimum number of edges that I will need to add so that there are no more bridges in a tree? I have seen the solution from the internet the answer is $\frac{|V|}{2}$, where $|V|$ is the number of vertices in the tree. How can I prove it?


texts: Find expectation and calculate Chernoff bound

texts:
We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same 2 tasks to every employee and scored their results with 2 values x,y both in [0,1]. The company selects the best employees among the others, if there is no other employee with a better score in both tasks.

Knowing that both scores are uniformly distributed in [0,1], how can i proof that the number of the employees receiving the price is estimated near to logn, with n the number of the employees, having high probability?

I need to use Chernoff bound to bound the probability, that the number of winning employees is higher than logn.


texts:
I am trying to understand the intersection of 2 DFA's. I got the following link:
Intersection of 2 DFAs
I can't understand why they have not used the symbol 'b'. In the DFA's they have symbol 'b' also but they are just talking about symbol 'a'.

  For M', we have...

  1.E' = {a}

  2.Q' = {s0, s1}

  3.q0' = s0

  4.A' = {s0}

  5.f'(s0, a) = s1, f'(s1, a) = s0

For example in line (1) they have just symbol 'a'. However, the DFA uses both 'a' and 'b'.

Similarly:

  For M'', we have...

  1.E'' = {a}

  2.Q'' = {t0, t1, t2}

  3.q0'' = t0

  4.A'' = {t0}

  5.f''(t0, a) = t1, f''(t1, a) = t2, f''(t2, a) = t0

there is no 'b' transition.
Does it mean that we would consider them one by one. For example, we can write (5) above for 'b' also  like:

f''(t0,a) =..

Also I want to know if the states in Machine 1 is not equal to states in Machine2 , what will we do?

Some body please guide me.

Zulfi.


texts: Trying to solve the recurrence relation by comparing 3 cases of master theorem

texts:
I am trying to understand how the master theorem is invoked on the following recurrence relation:

$$ T(n) = \sqrt{6006} T(n/2) + n^{\sqrt{6006}}. $$

So basically, I found the following source where they have Master theorem definition defined.

I found the similar solution (See the Link #1 in the comment below) where they are trying to solve the same problem (Problem #c). I

In the solution, they have mentioned the following :

We have :

n0.5logb(a)  =  nlogb(6006)1/2

=  n0.5log2(6006)1/2

and so on and so forth. I am not able to understand how they compared the results with the given equation.


texts: Divide-and-conquer: Determining the top two candidates and whether these two candidates received more than n/2 votes

texts:
Suppose that each person in a group of n people votes for exactly two people from a set of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes.

Describe a divide-and-conquer algorithm that determines the top two candidates and whether these two candidates received more than n/2 votes.

I have the answer (below), but there's one part I don't understand:

Our algorithm will take a sequence of 2n names (two different names provided by each of n voters) and determine whether the two top vote-getters occur on our list more than n/2 times, and if so, who they are. Actually for technical reasons we will need the top 3 vote-getters.** The votes of each voter are adjacent. Note that we can have at most 3 people (but not 4) with more than half of the votes. Divide the list into two parts, the first half and the second half. (No one could have gotten more than n/2 votes on this list without having more than half votes in one half or the other, since if a candidate got less than or equal to half the votes in each half, then he got less than or equal to half the votes in all.) Thus apply the algorithm recursively to each half to come up with at most six names (three from each half). Then run through the entire list to count the number of occurrences of each of these names to decide which, if any, are the winners. This requires at most 12n additional comparisons for a list of length 2n.

I don't understand why we are coming up with at most six names. I also don't get where the 12n comes from. To be more clear, I sort of understand why the 12n is a thing given the 6 names, but I don't understand why it's 6, and if it means 6 names for each step of recursion, or 6 names after all of the recursion (and if the latter, what happens during each step of recursion?).


texts: Prove that a and b commute if and only if they are powers of the same word

texts:
Two words $a$ and $b$ commute if $ab=ba$.

How to demonstrate that $a$ and $b$ commute if and only if they are powers of
the same word ?

$ab=ba \Leftrightarrow \exists \space  \tau  \in \Sigma^{*} \mid a=\tau^{k} and \space b=\tau^{k'}$

The demonstration in this direction is trivial:

$\space \exists \space  \tau  \in \Sigma^{*} \mid a=\tau^{k} and \space b=\tau^{k'} \Rightarrow ab=ba$

But I don't manage to find an elegant solution for the other direction.


texts: (operationalizable) Cost measure for small problems

texts:
For what I know of complexity measures in CS, they are aimed at rather large problems. With today's computing power, most people don't care about comparing the complexity of simple problems as they would all be solved in about the same time.

Yet, I turn out to be interested in some cost measures for small problems. For instance, although both 12 + 14 and 123503 + 589034 can be solved in the blink of an eye by today's computers, there seems to be a sense in which 123503 + 589034 is still more "costly" than 12 + 14.

So my question is : do you know of any such cost measures that would be appropriate for such small size problems?

Note 1 : I am interested in rather general answer for all kinds of problems, the addition one being just an example.

Note 2 : the best I have found so far is Kolmogorov's complexity, but for what I understand of it, it seems awfully hard to operationalize. First it appears to be dependent on the reference language, and second, once a language is chosen, it seems really hard to prove that a description of a string is of minimal length.

Do you know of any measure which would be easier to implement?
Am I missing something about Kolmogorov's complexity and is it easier to implement than I suggest?


texts: Proving a binary heap has $\lceil n/2 \rceil$ leaves

texts:
I'm trying to prove that a binary heap with $n$ nodes has exactly $\left\lceil \frac{n}{2} \right\rceil$ leaves, given that the heap is built in the following way:

Each new node is inserted via percolate up. This means that each new node must be created at the next available child. What I mean by this is that children are filled level-down, and left to right. For example, the following heap:

    0
   / \
  1   2

would have to have been built in this order: 0, 1, 2. (The numbers are just indexes, they give no indication of the actual data held in that node.)

This has two important implications:

There can exist no node on level $k+1$ without level $k$ being completely filled
Because children are built left to right, there can be no "empty spaces" between the nodes on level $k+1$, or situations like the following:

    0
   / \
  1   2
 / \   \
3  4    6

(This would be an illegal heap by my definition.) Thus, a good way to think of this heap is an array implementation of a heap, where there can't be any "jumps" in indeces of the array.

So, I was thinking induction would probably be a good way to do this... Perhaps something having to deal with even an odd cases for n. For example, some induction using the fact that even heaps built in this fashion must have an internal node with one child for an even n, and no such nodes for an odd n. Ideas?


texts: Using sephamores to solve happens-before requirements

texts:
I have a practice problem that I'm not sure how to solve:

  Use sephamores to solve the following synchronization requirement. We have 4 processes: P1, P2,P3 and P4. P1 must run before any of the other processes, P2 must run before P3 and P2 and P4 run concurrently.

This is how I solved it:

initialize 3 sepahmores s1,s2 and mutex;
s1 ,s2 = 0;
mutex = 1;

Process P1 {
  signal(s1) //sends the signal saying P1 is done
}

Process P2 {
  wait(s1) //locks P2 so it doesn't process until P1 sends the signal
  signal(s2)

  do {
    wait(mutex) //makes sure only one process at a time has access to the Crit section
    //Critical Section
    signal(mutex)
  }  while(TRUE)
}

Process P3 {
  wait(s2) //locks P3 so it doesn't process until P2 sends the signal
}

Process P4 {
  wait(s1)
  do {
    wait(mutex) //makes sure only one process at a time has access to the Crit section
    //Critical Section
    signal(mutex)
  } while(TRUE)
}

Is this the most efficient way to use sephamores for this question? If it is, does this solution satisfy the requirements (P1 before everything else, P2 before P3 and P2 and P4 run concurrently)?


texts: How does the double rotation in AVL tree work?

texts:
I am trying to find out from this visualization how does the AVL trees work. But I am not able to find out how is the algorithm choosing which vertex is the right one to use as "partial root".

The simple rotation is actually very simple, but when it comes to the double rotation it is much worse.

There are some tricks with signs of vertices when inserting a new vertex, but I don't completely understand that either (and also I am not sure if it is important for the rotation).

EDIT:
I add a drawing of my Insertion. I would expect that the double rotation will choose the purple (left) variant (it seems simplier), but the visualization choose the brown one. Why is that?


texts: Define a DFA that accepts all even length binary strings that don't contain the substring "111"?

texts: I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly appreciated!


texts: L = { | M is a TM and halts on every input after 5 steps exactly } - is L decidable?

texts:
in order for M to belong to L, it must halts on all inputs after 5 steps exactly. is the problem not decidable ? how can it be proved ? I could not succeed in doing a reduction from Htm as the attempt to count M(w) steps failed.

update:
apparently the language is in R. can anyone provide a proof?


texts: Computing Von Neumann Entropy Efficiently

texts:
The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda_k$ treated as probabilities. So $S(\rho) = -\sum_k \lambda_k \lg \lambda_k$.

Clearly the Von Neumann entropy can be computed by first extracting the eigenvalues and then doing the sum. But extracting eigenvalues is quite expensive. Is there a faster way to compute the entropy?

(For example, computing the sum of the eigenvalues is much easier than computing the individual eigenvalues. You just return the trace of the matrix. The product of the eigenvalues, the determinant, is also easier to compute than the individual eigenvalues. Is there also a shortcut for the entropy?)


texts: What's the problem of using the clock to generate random numbers?

texts:
If the clock shows 14:15:36.909302, why not just use the fractions of a second part (09302) as a kind of random number?

What is wrong with this form of generating random numbers?

I am aware that obtaining truly random numbers is a difficult task, so I am assuming that there is something wrong with this method.


texts: Prove that for all functions g: N -> R>=0, and all numbers a in R>=0, if g in Omega(1) then a + g in Theta(g)

texts:
Here is a more readable version of the question:

Prove that for all functions $g: \mathbb{N}\to\mathbb{R}^{\geq 0}$, and all numbers $a \in \mathbb{R}^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \Theta(g)$

What I've done so far:

In order for $a + g\in\Theta(g)$, $a+g \in \mathcal{O}(g) \wedge a + g \in \Omega(g)$.

Expanding our assumption, we get:

$\exists c_1, n_1 \in \mathbb{R}^{+}, \forall n \in \mathbb{N}, n \geq n_1 \implies g(n) \geq c_1$

Proving $a + g \in \Omega(g)$:

Expanding the definition, we get:

$\exists c_2,n_2 \in \mathbb{R}^{+}, \forall n \in \mathbb{N}, n \geq n_2 \implies a + g(n) \geq c_2*g(n)$

Let $c_2 = 1$ and $n_2 = n_1$. Let $n \in \mathbb{N}$. Assume $n \geq n_2$. Prove $a + g(n) \geq c_2 * g(n)$.

$g(n) = g(n)\\ \implies g(n) \geq g(n)\\ \Leftrightarrow c_2 * g(n) \geq c_2 * g(n)\\ \Leftrightarrow g(n) \geq g(n) \text{ (since $c_2 = 1$)}\\\Leftrightarrow a+g(n) \geq g(n) \text{ (making left side bigger since $a \in \mathbb{R}^{\geq 0}$)}$

Proving $a+g \in \mathcal{O}(g)$:

Expanding the definition, we get:

$\exists c_3,n_3 \in \mathbb{R}^+, \forall n \in \mathbb{N}, n \geq n_3 \implies a + g(n) \leq c_3 * g(n)$

I'm struggling here since I'm not really sure what value of $c_3$ I should be using or how to derive one. (I've tried using my assumption of $g(n) \geq c_1$ but I don't really know where to go from there). Any help is greatly appreciated and I apologize for any formatting errors in advance. Thank you.


texts: Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?

texts:
I have a set $M$, subsets $L_1,...,L_m$ and natural numbers $k,l\leq m$.
The problem is:
Are there $l$ unique indices $1\leq i_1,...,i_l\leq m$, such that
$\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}\right| \leq k$

Now my question is whether this problem is $NP$-complete or not. What irritates me is the two constraints $l$ and $k$ because the NP-complete problems that were conceptually close to it that I took a look on (set cover, vertex cover) only have one constraint respectively that also appears in this problem.
I then tried to write a polynomial time algorithm that looks at which of the sets $L_1,...,L_m$ share more than $k$ elements with other sets but even if all sets would share more than $k$ elements with other this wouldn't mean that their intersection has more than $k$ elements...
This question kind of comes close but in it there is no restriction on the amount of subsets to use and the size of the intersection should be exactly $k$, but maybe this could be useful anyways.
Can somebody further enlighten me ?


texts:
I'm trying to show that $K_1 \le_1 K$ where $K$ is the diagonal halting set $\{x : \varphi_x(x) \downarrow\}$ and $K_1=\{x: \exists y \,\, \varphi_x(y) \downarrow\}$, then I defined the function
$$\psi(x, y)= \begin{cases} 0 \, \, if \, \, x \in K_1 \\ \uparrow \, if \, x \notin K_1\end{cases}$$
By the Parameter Theorem there is a one to one computable function $f$ such that $\varphi_{f(x)}(y) = \psi(x, y)$ and it's easy to show that $x \in K_1 \leftrightarrow f(x) \in K$. All above works if and only if $\psi$ is partial computable, I think that function is partial computable because $K_1$ is r.e. Is this true? I mean, Can I always define a function computable by
$$\psi_A(x, y)= \begin{cases} 0 \, \, if \, \, x \in A \\ \uparrow \, if \, x \notin A\end{cases}$$
for each r.e. set $A$?


texts: Finding short readable representation of words

texts:
I am looking for Input/Literature on

a readable way to represent words (which are accepted by automata)
an Algorithm, that constructs the Representation

For example, a word $w$ might contain a subsequence $v$ which is repeated $m$ times, i.e. $w= u \, \underbrace{v\cdots v}_{100} \,x$ where $u,v,w,x \in \Sigma^*$

In a readable representation, I would expect this subsequence to occur only once, together with the information about the 100 repetitions.

Motivation:

I am working on an interactive input interface for a tool, that works with words that are accepted by automata.
It requires the user to interact with possibly long words

generated by the system
or select words interactively himself

My Approach:

The representation I currently use structurally can be understood is an ordered tree, where

the leaves are symbols $a \in \Sigma$
the inner nodes are repetition counters $i \in \mathbb{N}$

Example:

$w = ABABAC \, ABABACAC \,ABABACAC \,ABABACAC$

Representations

$\overbrace{AB}^{2}AC\overbrace{\overbrace{AB}^{2}\overbrace{AC}^{2}}^{3}$
$\overbrace{\overbrace{AB}^{2}AC}^{2}\overbrace{AC\overbrace{AB}^{2}AC}^{2}AC$

I have implemented an algorithm which, given $w$, finds the 2. representation.
I would consider 1. more appealing, and I assume, that I would generally prefer representations that are minimal with respect to length (where length is the total amounts of symbols/tree-leaves)

My Questions:

Is there a good algorithm to find representations minimal with respect to length?
Does that have a name? Is there Literature on the topic? (I couldn't find anything useful)
Can someone think of an alternative/better approach?


texts:
The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$.

It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$. Or to put it differently: $\mathcal{o}(n \log(n) + n^2)$.

So I was wondering if this would apply to the generalised problem: Find integers $a_i$ for $i \in [1..k]$ in a set $S$ of size $n$ such that $\sum_{i \in [1..k]} a_i = 0$.

I think you can do this in $\mathcal{o}(n \log(n) + n^{k-1})$ for $k \geq 2$ (it's trivial to generalise the simple $k=3$ algorithm).
But are there better algorithms for other values of $k$?


texts: Characterization of alpha-equivalence in languages with bindings

texts: Following up on this post denoting $(x \leftrightarrow y)$ the permutation of $x$ and $y$ and $P[x \leftrightarrow y]$ the term obtained from the term $P$ by permuting $x$ and $y$ (so for example if $P = \lambda x. \lambda y. x y$ then we have $P[x \leftrightarrow y] = \lambda y. \lambda x. y x$)  (note that such transformation is immune from potential variable capture unlike those based on substitutions $y \leftarrow x$ or $x \leftarrow y$), then it appears to me that when $x \ne y$, a term $\lambda x. P$ is alpha equivalent to a term $\lambda y. Q$ if and only if $y$ is not free in $P$ and $Q$ is alpha equivalent to $P[y \leftrightarrow x]$. I find this observation interesting because it lends itself to a simple recursion in order to establish alpha-equivalence (as opposed to using an algorithm based on de Bruijn indices). I would like to know whether anyone thinks this observation is wrong, or whether it is true (a proof sketch or counterexample is welcome), or whether while true, it is not very interesting because the complexity of the recursive computation would be worse than a solution based on de Bruijn indices (each step requires determining whether $y$ is free in $P$ and permuting variable $x$ and $y$ in $P[x \leftrightarrow y]$).


texts: Finding edges with minimal weight sum, such that every simple cycle contain at least one edge

texts:
Given simple, udirected and connected graph with $n$ verticies. Every edge in this graph has some weight. I have to find (in polynomial time) a set of edges such that :

1.every simple cycle in graph contains at least one edge from this set
2.sum of weights of these edges is the least possible

I have derived the following algorithm to solve this problem.

First, apply DFS algorithm, starting from 1. vertex, to get all back edges. It is known that every simple cycle in this graph will contain at least one back edge, so 1. condition will be satisfied. To satisfy the 2. condition, we must apply DFS algorithm starting from 2. vertex, 3. vertex .... n. vertex, to get different sets of back edges, that all satisfy 1. condition, and choose set with the least sum of weights.

My question is will this algorithm give the right answer ? And if it won't, then why?

I have some doubdts about it, for example, is the set of back edges, given by DFS algorithm, is least possible to satisfy the condition that every simple cycle in the graph contain at least one edge from this set? For example, DFS has given me that $BE =  \left\{ e_1, e_2, e_3, e_4 \right\}$ are the back edges of graph. So every simple cycyle will contain at least one edge from $BE$. But, is it possible that we can throw out, say, $e_3$ and still every simple cycle in graph will contain at least one edge from $\left\{ e_1, e_2, e_4 \right\}$ ?


texts: How to construct XOR gate using only 4 NAND gate?

texts:
xor gate, now I need to construct this gate using only 4 nand gate

a b out
0 0 0
0 1 1
1 0 1
1 1 0

the xor = (a and not b) or (not a and b), which is
\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

I know the answer but how to get the gate diagram from the formula?

EDIT

I mean intuitively, to me, I should get this one if I do it step by step followed by the definition xor = (a and not b) or (not a and b).

\begin{split}\overline{\overline{\overline{A}{B}}\cdot\overline{{A}\overline{B}}}\end{split}

and xor will be constructed with 5 nand gates (first #1 image below)

my question is more like: imagine the first person in history figure out this formula, how can he or she (the thinking process) get the 4 nand soltuion from this formula, step by step.

\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}


texts:
I'm aware that 0-1 integer programming problem is NP-complete, where the problem is stated as: Given some integer matrix A and some integer vector b, determine whether there exists a vector x consisting of 0's and 1's such that Ax >= b. I've seen that 3-CNF SAT is reducible to this problem.

However, here's a slight variant: Given some integer matrix A and some integer vector b, determine whether there exists a vector x consisting of 0's and 2's such that Ax >= b.

The fact that vector x must consist of 0's and 2's kind of throws me off here. For the original problem, we just could reduce from 3-SAT by adding the inequalities 0 <= xi <= 1 for each boolean variable. But here, I can't just add the following inequalities:

0 <= xi <= 2

because x cannot equal 1.

Am I allowed to add an inequality, such as xi != 1? If not, what reduction can I use to show that the given problem is NP-complete? Thanks for any help.


texts: When do we need U(n+2) to solve a problem that can be formulated in U(n)?

texts:
I understand the need for a universe hierarchy, and that each new level brings additionnal proof-theoretic strength.

In the HoTT book there are examples of proofs that need to use the next level in the Universe hierarchy.

Do we have examples of inhabited types A:U(n), where the construction of the inhabitants/proof a:A requires the use of U(n+2) ?


texts: Effect of determinization on the time complexity of Turing machines

texts: Suppose I assume that the complexity of a non-deterministic Turing machine $N$ is $T(n)$, $n$ is the length of the input string. What would be the time complexity of a deterministic Turing machine $D$ equivalent to $N$?


texts: How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?

texts:
I was reading CLRS and in theorem 11.1 it states:

  In a hash table in which collisions are resolved by chaining, an unsuccessful search takes average-case time $\Theta( 1 + \alpha )$, under the assumption of simple uniform hashing.

I was trying to understand how to express this theorem with quantifiers ($\exists, \forall$) and how it relates to "average-case" time (precisely, what they mean with average case time).

Is the theorem a statement that holds for all or any key? Or does it hold for all key on average and what does "on average" mean rigorously?

Usually, I like separating the terms expectation and average because the have different meanings. Expectation usually I think of it as the expected value of something according to some underlying distribution. For Average I think of the average value given a sample. So with these in mind, is the "average-case" scenario the same as the average running time for any key? i.e. Let $T_k$ denote the amount of time to search of a key $k$. This is a random quantity because it depends on the key we search for. Define the average-case runtime for any search to be $Search = \sum^n_{k=1} T_k$. Is the theorem statement in CLRS statement about the random variable $Search$ I just defined? (Which takes into account all keys at once and hence, applied for "any key" I guess). Or what do they mean by average-case precisely?


texts: Reversing a List from a Context-Free Grammar

texts:
Let's say I have a struct_declaration_list of the following type. How do I reverse it?

struct_declaration_list
    : struct_declaration
    | struct_declaration_list struct_declaration
    ;

P.S. Sorry I don't know the exact name of this kind of list so I can't search. I just have this grammar.


texts:
When 54 bytes of data is transferred using the UDP protocol, the efficiency is? (In per cent)

IN UDP, the maximum datagram size can be $2^{16}-1 \, bytes$

Now to this, 8 Bytes of UDP header is included and this together must fit within $65535\, bytes$ IPv4 packet limit(Including 20B IP Header size).

So, maximum data that we can send in 1 UDP datagram-> $65535-8-20=65507\,Bytes$

We could have sent this amount of data, but we are actually sending 54 Bytes, so the efficiency of the protocol is $\frac{54}{65507} \times 100(\,in\,\%)$

Am I correct?


texts:
In B. Pierce's book "Types and Programming Languages", he talks about the size of types (see pictures below).

I searched the book for a definition but could not find one. I only found a definition for the size of terms, but not for the size of types.

Could someone please explain what Pierce means by the expression "$size(T_1)$" (marked by yellow in the image below) ?


texts:
I'm a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I'm fairly confident that 3-Coloring is NP-Complete, while 3-Clique is P. Correct me if I'm wrong (which is very likely), but for any k-clique where the k is fixed, is $V^k$, meaning the 3-clique is $V^3$, right? I asked my professor about this and his response was:

"3-clique is definitely not in P.  You (apparently) have to examine all thrices of vertices to settle the matter."

And I still don't understand how this is not a $V^3$ operation.

If I figured out a way to reduce 3-coloring to 3-clique wouldn't I be millionaire?


texts: Event-based rather than flow-based systems?

texts:
This is a very vague question, so I don't know if people will understand it (I'm not even sure I understand the question myself), but here goes. Also, I'm not sure if this is really the right forum to ask, but I thought that it relates to computer science because of the connection to function calls (see comment at bottom).

Dynamical systems are formulated (in continuous time) as
$$\begin {align}
&\dot x_1=f_1(x_1,...,x_n)\\
&...\\
&\dot x_n=f_n(x_1,...,x_n)
\end {align}$$

These are flows over time. In other words, we have a stock for each variable, and a specified flow at each point in time, from which we will deduce the stock over time.

Situations in applied science that are captured well by this system are for example:

There is an amount of water $x$ in a cup, and we know that every second, an amount $a$ drips through a hole, so that $\dot x=a$.
an object is moving with $x$ meters/s towards the earth, and we know that every second, $x$ increases by $9.8m$.

We can of course do this in discrete time as well, which doesn't fundamentally change the idea:
$$\begin {align}
&\Delta x_1=f_1(x_1,...,x_n)\\
&...\\
&\Delta x_n=f_n(x_1,...,x_n)
\end {align}$$

However, sometimes our logical analysis in an applied setting doesn't start with knowledge of a flow per unit time, but with knowledge of events. For example, we might know that in biology, an event called "birth" can occur, which would cause various things to happen (among other things, an increase in the population with unit $1$).

We generally model births in population science (as we do in most of science) also as a flow. Instead of starting with a formal definition of a birth as an event, we simply state that in a given time interval, the population increases. In other words, the analysis starts with the variable population, and with a formula denoting its change over time. In fact the whole concept of a "birth", being an event, never enters the mathematical model, and is only a kind of informal interpretation that we stick to the model.

I am wondering whether this "informal" leap from the "event" of a birth to a change-over-time, can somehow be formalized.

So my question is:

Is there a (sub-)branch of mathematics that starts its analysis with a formalization of an "event", rather than of a flow?
Is there any mathematical analysis of "events" at all?
I tend to think of events as "function calls" in the programming
sense. i.e. when a birth occurs, a "birth" function is called and
this causes various variable changes, and possibly other events.


texts: Numerical Accuracy & Sorting Algorithms?

texts:
Sedgewick and Wayne talk about how sorting algorithms and, specifically, priority queues are used in devising ways to improve accuracy in floating-point calculations: https://algs4.cs.princeton.edu/25applications/

  Scientific computing is often concerned with accuracy (how close are we to the true answer?). Accuracy is extremely important when we are performing millions of computations with estimated values such as the floating-point representation of real numbers that we commonly use on computers. Some numerical algorithms use priority queues and sorting to control accuracy in calculations.

What "numerical algorithms" use priority queues and sorting like this?


texts: Can I have a "dependent coproduct type"?

texts:
I'm reading through the HoTT book and I have a (probably very naive) question about the stuff in the chapter one.
The chapter introduces the function type
$$ f:A\to B $$
and then generalizes it by making $B$ dependent on $x:A$
$$B:A\to\mathcal{U},\qquad g:\prod_{x:A}B(x)$$
and that is called the dependent function type.
Moving on, the chapter then introduces the product type
$$ f:A\times B$$
and then generalizes it by making $B$ dependent on $x:A$
$$B:A\to\mathcal{U},\qquad g:\sum_{x:A}B(x)$$
and that is called the dependent pair type.
I can definitely see a pattern here.
Moving on, the chapter then introduces the coproduct type
$$ f:A+B$$
and ... combobreaker ... there is no discussion of dependent version of this type.
Is there some fundamental restriction on that or it is just irrelevant for the topic of the book? In any case can someone help me with intuition on why  function and product types?  What makes those two so special that they get to be generalized to dependent types and then used to build up everything else?


texts: Why are regular expression quantifiers greedy by default?

texts:
I can't count the number of times I've seen questions on StackOverflow related to regular expressions where the problem was due to the programmer not understanding the impact of greedy quantifiers. Most recently, Python regex issue — [\S\s]* vs \d*.

I wonder why regular expression quantifiers were defined to be greedy. It seems like this is less intuitive than non-greedy regular expressions. If someone writes a regexp like

BEGIN(.*)END

they intuitively expect the capture group to grab everything between adjacent BEGIN and END brackets. But if there are multiple BEGIN...END pairs, it will span all of them. You have to write

BEGIN(.*?)END

to express this. And I think non-greedy quantifiers like this didn't even exist until PCRE -- matching this was even more complicated then.

Non-greedy quantifiers are not a magic bullet solution for all such problems, but it seems like there would be fewer problems if they were the default.

EDIT:

I think I see a possible reason. If there's nothing after the quantifier, you usually want it to be greedy. My original answer to the above question had a bug, the regexp ended with Answer:\s*(.*?). By making this non-greedy, the last capture group matched an empty string rather than everything after the final Answer: prefix.

And also consider the \* there -- we want that to capture all the whitespace after the prefix, before grabbing the text in the capture group.

So the appropriate default really depends on what (if anything) is after the quantifier. And greediness is also often only an issue with .*, not if you quantify something more specific than ..

Is this all there is to it?


texts:
Suppose we are given a digraph A. We need to calculate its connectivity digraph B.

I conceived two algorithms:

1.

Set X = A.
Loop
Set Y = X*A united with identity
Stop the loop if Y = X
Set X = Y
End loop
B = X

2.

Set X = A. [Or instead "X = A united with identity" and remove "united with identity" in the third step?]
Loop
Set Y = X*X united with identity [or should it be Y = (X united with identity)*(X united with identity)?]
Stop the loop if Y = X
Set X = Y
End loop
B = X

I think that the algorithms are equivalent but the second one is faster.

Are they really calculating connectivity and are really equivalent?

Is the second algorithm faster not only for incidence matrix representation but also for hash-map or like this representation of digraphs?

Is there an even more efficient algorithm?


texts:
This is how I would think it
n^2 = O(log n)

f(n) <= c*g(n)

should c=1 ?

n0 = 1

n^2 <= log n

0 <=  log n - n^2, for all n>=1

we take n=1 then 0 <= log(1) - 1^2

0 <= 0 - 1

0 <= -1

Therefore n^2 = O(logn) false?

Is this correct?


texts: Unambiguous but nondeterministic context-free language?

texts:
Whenever deterministic context-free languages are discussed, the webpage/textbook would always give a side note saying that although deterministic context-free languages are never ambiguous, unambiguous context-free languages may still be nondeterministic.

However, they never give an example. Is there a short, simple example of a context-free language that is

unambiguous
but nondeterministic


texts:
I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness.

This is the problem:

In building an Universal Turing Machine to emulate another Turing Machine, how can we be sure that we are indeed simulating it? ('sure' in the sense of being computationally verified by an algorithm). So I get confused, the problem I found is that Rice's theorem apparently tell us that we can not verify this computationally.. Is not "to emulate" an extensive property?.This lead me to think we could not prove the Universal Turing Machine is doing what it's supposed to do..

EDIT

To expand the topic

I want to expand this point, what I understood from given answers, is you can state that a specific Machine is Universal but not that an arbitrary machine is (nor a family of machines are universal), ok, but I don't ask for arbitrary!, nor a family, but to test algorithmically a single fixed machine. Test, like measuring, is against something, It's hard to think a computer concept without having something to compare with, and according to answers, completeness of a machine seems as something that can't be compared.

How universality is proven? let's say by showing 'look mom I am simulating a TM', so, as she believes TM are universal, then your machine is also universal, but, she can't verify it!, she must believe you because she can't test that single machine you made, not by an algorithm, so that's why I see Rice's theorem rubs against completeness, there is no algorithm to test two fixed machines are doing the same computation.

So what can "universal" mean?, it's seems like saying, your software is doing what you mind, because is written in a Turing Complete language!. 'This is emulating a machine because it can'. I think that's not enough.


texts:
I've a couple of questions that I need answers for. What I am looking for here is the outline of the answers. Not necessarily the exact complete answer. I can do that.
The question is that common operating systems provide support for concurrency through processes and threads.

There are differences between processes and threads and that well documented and easily understood. The issue here is What support does the hardware need to provide for processes and threads?
The initial guess that came to my mind was that it is related to process communication and synchronization. However, these concepts are parts from another question which gets me to think that they are not the right answer. I am aware of the hyper-threading which is a hardware approach for concurrency. Is it ?!

The other question is that Operating systems and programming languages offer various means for communication and synchronization between processes and threads. What are the most
common ones? What support does the hardware need to provide and, in particular, what instructions does a processor need to offer for communication and synchronization?

I know it is a long question but again, I don't seem to figure out the outline for the specific hardware support for (concurrent process and threads, as well as communication and synchronization).

Your help is highly appropriated


texts: How is an OS page stored in a k-way set-associative cache?

texts:
I have been reading about set-associative caches. As far as I have read, in case of n-way set-associative cache each way stores, a block (let's say 16 bytes) and therefore each set will be of size 16n bytes. But what if I have to load a whole page into the cache. Since the size of a page is much larger than a block, how is that distributed over the cache?
Another question is what would be the distribution in case of a shared NUCA cache design? Assume that a single tile has a private L1 cache and shared L2 cache.


texts: Is it possible to modify dijkstra algorithm in order to get the longest path?

texts:
Is it possible to modify Dijkstra´s algorithm in order to get the longest path from $s$ to $t$ ?.

  My intuition says that I´ll need a different algorithm entirely. Finding the longest path is the same as finding the shortest path on a graph with negative weights. However, Dijkstra’s algorithm requires that the weights are positive, so it cannot be modified to calculate the longest path. A better algorithm to use could be: http://en.wikipedia.org/wiki/Longest_path_problem

Any idea of how to modify it?


texts:
One example in my textbook says that

$$\log\log n^n=\log n\log n=\log n+\log\log n = \mathcal{O}(\max(\log n, \log\log n))=\mathcal{O}(\log\log n)$$

and I was wondering why is that true?
I thought that

$$\log n \leq n \Leftrightarrow \log\log n \leq \log n.$$

So, for $C=1$ and $n\geq 1$ we have $\log\log n =\mathcal{O}(\log n)$.

Thanks for any advice.


texts: Tail recursion can't work with dynamic programming programs

texts:
I am doing some exercises on dynamic programming in order to get familar with this concept.
I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic programming since most of the time we are recursively calculating a function $f$.

Let's suppose this function $f$ has $3$ parameters. This function $f$ represent all the subproblems of the problem we want to solve.

Moreover we have a nice recursive definition of $f$, so we are able to link the subproblems between each other and understand how a certain subproblem can help calculating an other subproblem.

Now suppose that the first parameter of our function $f$ can't take a value larger than $n_1$, the second also can't take a value larger than $n_2$ and the third parameter can't take a value larger than $n_3$. Supposing that calculating $f(i,j,k)$ takes $\mathcal{O}(m)$ then the complexity of our program is : (since it's essentially means we have $ n_1 \cdot n_2 \cdot n_3$ subproblems and each of these takes $m$ operations of constant cost to calculate)

$$\mathcal{O}(m \cdot n_1 \cdot n_2 \cdot n_3)$$

Now here comes my problem. If my program wants to calculate the maximum value of something then I can for example do the following :

$$f(i,j,k) = \max\{ f(i+1,j,k) + 1, f(i+1,j,k)\}$$

The problem is that this is not tail recursive. So in order to make the program tail recursive an idea could be to add a forth paramters to the function $f$, hence now we have :

$$f(i,j,k,l) = \max\{f(i+1,j,k,l+1), f(i+1,j,k,l)\}$$

This way the function $f$ is tail recursive.

Yet, my question is : making the function $f$ tail-recursive adds a $4$-th paramaters and hence increase the number of subproblems, so the complexity of our function is now increased (see what I said above about the complexity of a dynamic program), and hence tail recursion is bad on dynamic programs ?

Thank you.


texts: Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?

texts:
When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, but I can never force the product of running time and consumed memory below a clearly palpable limit. This is formally similar to Heisenberg's uncertainty principle: the product of the uncertainty in position and the uncertainty in momentum of a particle cannot be less than a given threshold.

Is there a theorem of computer science, which asserts the same thing? I guess it should be possible to derive something similar from the theory of Turing Machines.

(I asked this question originally on StackOverflow.)


texts: Is $A\odot B\odot C = A\oplus B\oplus C$?

texts:
(The notations used:

$\oplus$ is XOR operator
$\odot$ is XNOR operator)

I was solving a problem, where they asked which of the given options give equation for the difference of full subtractor. The circuit in the solution option was:

For me the first line:

  $(x'y'+xy)'z'+(x'y'+xy)z$

looked more like $x\odot y\odot z$. But I know the difference of full subtractor is $x\oplus y\oplus z$. So I tried to evaluate both separately:

  $x\oplus y\oplus z$
  $= (x'y+xy')\oplus z$
  $= (x'y+xy')'z+(x'y+xy')z'$
  $= (x'y)'(xy)'z+(x'y+xy')z'$
  $= (x+y')(x'+y)z+(x'y+xy')z'$
  $\require{enclose}= \enclose{updiagonalstrike}{xx'z}+xyz+x'y'z+\enclose{updiagonalstrike}{yy'z}+x'yz'+xyz'$
  $= xyz+x'y'z+x'yz'+xy'z'$   ...equation$(I)$

  $x\odot y\odot z$
  $=(x'y'+xy)\odot z$
  $=(x'y'+xy)'z'+(x'y'+xy)z$ (This is same as first line in the equations given in the figure above)
  $=(x'y')'(xy)'z'+(x'y'+xy)z$
  $=(x+y)(x'+y')z'+(x'y'+xy)z$
  $\require{enclose}=\enclose{updiagonalstrike}{xx'z}+xy'z'+x'yz'+\enclose{updiagonalstrike}{yy'z'}+x'y'z+xyz$
  $=xy'z'+x'yz'+x'y'z+xyz$    ...equation$(II)$

To my eyes, both equations $(I)$ and $(II)$ looks the same. So I went to wolframalpha and prepared truth table for both of them.

$x\oplus y\oplus z$

$x\odot y\odot z$

And they correctly look complement of each other. Then why the given answer and my calculations equates $x\odot y\odot z$ with $x\oplus y\oplus z$? What stupidity I am doing here?


texts: Express boolean logic operations in zero-one integer linear programming (ILP)

texts:
I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values.  The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le 1$).

I want to express boolean operations on these 0/1-valued variables, using linear constraints.  How can I do this?

More specifically, I want to set $y_1 = x_1 \land x_2$ (boolean AND), $y_2 = x_1 \lor x_2$ (boolean OR), and $y_3 = \neg x_1$ (boolean NOT).  I am using the obvious interpretation of 0/1 as Boolean values: 0 = false, 1 = true.  How do I write ILP constraints to ensure that the $y_i$'s are related to the $x_i$'s as desired?

(This could be viewed as asking for a reduction from CircuitSAT to ILP, or asking for a way to express SAT as an ILP, but here I want to see an explicit way to encode the logical operations shown above.)


texts:
Recently i was studying removal of useless symbols in productions given in Ullman Hopcroft.

The grammar goes as follows

S-> aAa | aBC

A -> aS | bD

B - > aBa | b

C-> abb | DD

D -> aDa

In the explanation that follows, we eliminate D obviously, but the removal of C still baffles me. As D is non generating, but C is both generating and reachable. So why delete C?

The resultant grammar is shown as

S->aAa

A->aS

B->aBa | b

Here is the link to the photo of the page in the book just in case

Page 240:

Page 241:


texts:
Given a string S of length n and a positive integer k <= n, we want to randomly, and with equal probability, choose a string from the set of all strings of length k that may be formed with a subset of the letters of S. For example, if S = daddy and k = 2, we want to choose each of the strings da, dd, dy, ad, ay, yd and ya with equal probability 1/7.

Obviously, one could do this by calculating all possible permutations. However, is there a more efficient way?


texts: Given a segment (geometry), check if it intersects with another segment in a set of segments

texts:
I have a set of several geometric segments, they can be defined with two points (for example a segment could be (4,6)--(2,7)).

Now, I want to query this set with another segment, and I want the operation to return whether it intersects with any of them or not. (And as a bonus, to return the instance or pointer to that segment).

The algorithm must be in O(1) or O(logn). Algorithms with preprocessing and/or redundant data structures are also welcome. Algorithms that solve a more specific problem (such as a constraint in segment length) are also welcome.

Example:

segment set:
(4,6)--(2,7)
(5,0)--(5,20)

Query:
(4,5)--(6,5)

Returns:
Intersects with (4,6)--(2,7) at point (5,5)

My idea:

I've had several ideas but one of them is to limit the segment length, and therefore do some kind of binary search to a previously sorted point set, so I can find a range of points that I can iterate and try every one of those segments. Since the segments are short, and since I could find an approximate range, the complexity doesn't go all over the place (unless there are too many segments in that same spot!, but that should also be another constraint)


texts: Difficult Cases for 3MaxSAT and 3SAT Approximation Algorithm

texts:
Its known that a polynomial time approximation algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP.
Its also experimentally known that 3SAT has the most difficult known cases when the clause to literal ratio is approximately 4.2.

Q1. Is there a similar result for 3MaxSAT where the approximation algorithm for satisfying some 7/8+e of clauses becomes almost always difficult if 3MaxSAT has some specific format (like 3SAT in 2.) ?

Q2. Is there a benchmark set available for 3MaxSAT approximation algorithms for such cases?

Q3. Is there a similar approximation hardness result for 3SAT (like 3MaxSAT in 1.) if informed that the given 3SAT is satisfiable? Is just the clause to literal ratio is sufficient to represent completely the hardest cases for such approximation algorithms too?


texts: Comparing asymptotics of various functions

texts:
Is the first function big oh, theta or omega of the second function in the following examples.

$(\log n)^{\log n} $ and $ \frac{n}{\log n}$
I am not sure how fast the first function grows.

$n2^n$ and $3^n$
I think the second function grows faster but not sure how to prove it.

$(\log n)^{\log n} $ and $2^{(\log_2n)^2}$
This is just puzzling.

$\sum_{i=1 }^n i^k$ and $n^{k+1}$.
And so is this.

Any help is much appreciated.


texts:
I am working on a Fraudulent Cash Transaction Detection System using DBSCAN and I want to know what is the proper way to identify outliers?
Thank you
##Edite##
I had a problem how to represent the outer points extracted by the DBSCAN algorithm in Python visualization techniques, and found the solution here:
https://www.youtube.com/watch?v=eq1zKgCFwkk
Enjoy your time


texts:
If $X,Y$ are complexity classes in the polynomial hierarchy with $X\subseteq Y$. With abuse of notation assume $X,Y$ also as the TMs that accept languages in classes $X,Y$ respectively.

Then is it always true $X^Z\subseteq Y^Z$ if $Z$ is another complexity class?
If not what is an easy way and example to understand $X^Z\subseteq Y^Z$ need not be true?


texts: How to guess solutions for "divide and conquer" type of recurrences?

texts:
I am trying to solve "divide and conquer" recurrence relations of the type

$T(n) = a T(n/b) + f(n)$

using the Substitution/Inductive Methods ( NOT the Master Theorem ). Every site I see on the web suggests guessing a solution and then proving inductively that the guess is correct. And almost all the sites quote the standard merge sort problem

$T(n) = 2 T(n/2) + n$

And they say, "... as we have seen these kinds of recurrences, lets guess the solution to be of the kind $nlogn$. But my doubt is how to make an educated guess when encountered with different constants $a$ and $b$ and different $f(n)$. For instance I am trying to solve the recurrence relation of n-bit multiplication-

$T(n) = 4T(n/2) + n$

How should I go about?


texts: On the minimum order of a maximal independent set in cycle graphs and path graphs

texts:
I can see from this question that a $K_{r + 1}$-free graph with $n$ vertices and $e$ edges contains an independent set of order at least
$$\frac{n}{2e/n + 1} \tag{1} $$
Since for a $C_{n}$/$P_{n}$ we know how many edges it contains it is easy to determine (1).

However, are there any particularities of cycle graphs and path graphs that would allow me, for such a graph $G$, to determine exactly $\min\{\mathopen|A\mathclose| : A\text{ is a maximal independent set of } G\}$, i.e. the minimum number of vertices that a maximal independent set of $G$ must contain.


texts: How to actually implement universal hashing?

texts: I sort of get what it is, but I don't understand how its actually supposed to be used in algorithms. Suppose the hash function is $h_{ab}(x) = ((ax+b) \mod p ) \mod m$ where $a$ not equal to 0. If I wanted to insert something into the table, would I calculate the bucket to place it in using the hash function and then place it in that bucket? How would I go about retrieving that data later on?


texts:
Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core principal difference between Parallel and Distributed Algorithms? Below are my under standings:

In parallel algorithms (task parallelism), A big task is divided into two or more sub tasks and each sub task is executed by one processing element (PE) parallely. All sub tasks are depended on each other. What I further understand, a parallel algorithm can be coded using OpenMP which runs on multiprocessors as well as can be coded using MPI which runs on message passing systems. on the other hand, in distributed algorithm, every processing element or node executes the same copy of algorithm. They are totally independent and exchange messages to achieve the common goal. I think distributed algorithms are designed only for multi-computer systems.

It is requested to provide parallel and distributed algorithm for a same example problem for better understanding.


texts: Different boolean degrees polynomially related?

texts:
Let $f$ be a Boolean function.

Let $p$ be the minimum degree real polynomial that represents $f$ with degree $d_f$.

Let $p_\epsilon$ be the minimum degree real polynomial with degree $d_{f,\epsilon}$ such that $$|p_\epsilon(x)-f(x)|\leq\epsilon.$$

Let $p_{0,\epsilon}$ be the minimum degree real polynomial with degree $d_{0,f,\epsilon}$ such that $$f(x)=0\implies p_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p_{1,\epsilon}$ be the minimum degree real polynomial with degree $d_{1,f,\epsilon}$ such that $$f(x)=1\implies p_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Are $d_f,d_{f,\epsilon},d_{0,f,\epsilon}$ and $d_{1,f,\epsilon}$ all polynomially related?
It is clear $$d_{f,\epsilon}\leq d_{0,f,\epsilon},d_{1,f,\epsilon}\leq d_f.$$

Does $$d_{f}\leq (d_{0,f,\epsilon})^a,(d_{1,f,\epsilon})^b\leq (d_{f,\epsilon})^c$$ hold for some $a,b,c\in\Bbb N$?

What is a good reference to understand relations among these four degrees?


texts: Are there any computer science encyclopedias?

texts:
Consider the volume "The Princeton Companion to Mathematics" which has the broadest range of topics attempted by any book in the field.

Does a Computer Science counterpart exist?


texts: Given multiple families of sets, select a set from each such that the intersection of selected sets is a correspondence

texts:
Let $X = \{x_1, ... , x_k\}$ and $Y = \{y_1, ... , y_h\}$.

A subset $S \subset X \times Y$ is a correspondence if :

$\forall x, \exists y, (x,y) \in S$ and
$\forall y, \exists x, (x,y) \in S$

That is to say, $S$ fully projects onto $X$ and $Y$.

Now for the problem. Given an $n \times m$ matrix of subsets $(S_{i,j})$, select a subset from each row, (denoted by a selection function $s:\{1,..,n\} \rightarrow \{1,..,m\}$) such that the intersection $\cap_{i=1}^{n} S_{i,s(i)} $ contains a correspondence; or conclude there is no such function.

Is this solvable in polynomial time of $max \{k,h,n,m\}$ ?

I have tried reducing the problem from Set Packing, Set Cover, and Hitting Set with no luck. It is clearly NP, and I suspect it is NP-hard.


texts: How to prove a side effect in a function

texts:
I asked a question earlier about Saving to the Database, which was very general and about the requirements for a proof when you go through many layers of non-verified systems such as the network and databases.

In this question I am wondering about a more middle-level proof, this time about transforming an object $f : A \to B$ with side effect $C$. Say I have as input a string $A$, and as output an Abstract Syntax Tree (AST) $B$. All of this happens in memory with a small string of say a few KB. Right now, ignoring all the details of the hardware implementation and all the details of any particular language.

I am wondering at a high level what it takes to prove something like this. Specifically I wanted to focus on side effects in this question. Say during the parse process, we create a global symbol table to store classes. Then as we are parsing through the code and we encounter the class, we add to the symbol table. So instead of $f : A \to B$, we really have:

\begin{align}
  f : A &\to B\\
  &\downarrow\\
  &C
\end{align}

That is for the symbol table $C$ and AST output $B$. Somewhere in the function $f$ implementation there is another function $g : \{C,c\} \to C'$, which adds the new symbol $c$ to $C$.

What I would like to prove (in this question, just at a high level, some key points) is that the function generates the symbol table $C$, even though the output of the function is the AST $B$. In type theory, the proof for AST $B$ could possibly just be the sequence of type definitions and transformations, similar to Hoare Logic. But to prove that the function $f$ has side effect $C$ seems much harder/trickier.

It seems that you have to go and step through the algorithm one step at a time, and (assuming everything is strongly typed), figure out what the "current state" would look like at that point (of the whole program). Then you would compare your pattern (the assertion of the post-condition if it were Hoare Logic) with the current state of the program at that point, and see if it was a match. And see if that stayed true until the end of the function/algorithm. But this sort of seems like it's becoming Model Checking, which I only know the basics about, not sure if that is correct to assume though. Also, this one-step-at-a-time stepping through the algorithm seems like program simulation, so wondering if that is true or not or if simulation has a role here.

So I'm wondering, at a high level, what is required to prove that function $f$ generates a side effect $C$. As a specification, I would write "$f$ generates the symbol table $C$".


texts: minimize sum of primes with a lower bound on product

texts:
I can't quite figure out an algorithm for this:

Given some integer n, what subset of the primes (so no repeats) would yield the lowest possible sum if their product is at least n?

Example: 6 -> 2*3,

2308 -> 2*3*5*7*11,

14 -> 3*5

Does anybody know how I would do this?

This is part of a research project I'm doing on finite automata right now.


texts: Would limiting the number of operations in a transaction prevent SQL injection?

texts:
In my understanding all SQL injections need to add another operation to the one intended by the programmer.

For example, a badly written query:

query="Select * from Table where name="+name;

User inputs name as: foo; Delete from Table; and this would be an SQL Injection.
But if the programmer would be able to limit the number of operations in a transaction to 1 (the Select in this case) or how much operations he intends to use the SQL Injection would be impossible. Is there a way we can limit the number of operations in most programming languages? Would this be enough to stop SQL Injection?


texts: How does this allow list operations to be applied to lists with elements of any type?

texts:
In Types and Programming Languages by Pierce, Chapter 11 is simple extensions of the simply typed lambda calculus with any simple base types. Section 11.12 introduces Lists.

How does the section allow list operations to be applied to lists with elements of any type? Specifically, my confusions are:

Does Section 11.12 introduce lists and list operations by making use of some kind of polymorphism, or type inference? (The book doesn't introduce type inference till Chapter 22 and parametric polymorphism till Chapter 23.)

Does "When we ﬁrst introduced lists in §11.12, we used “custom” inference rules to allow the operations to be applied to lists with elements of any type" in Section 23.4  mean that Section 11.12 makes use of type inference to achieve similar behavior of "polymorphism"?
Does  "For every type T, the type List T describes ﬁnite-length lists whose elements are drawn from T" in Section 11.12 mean

that  List T is a single literal type name for all possible specific typess for T, or
that List T  should be instantiated differently for different specific types for T, e.g.  List Boolean, List Nat?

Is [T]  part of the  the names of the list operators, e.g. nil[T], cons[T], isnil[T]?

Should [T] in nil[T] be instantiated differently for different specific types for T, e.g. nil[Boolean], nil[Nat]?
Does Section 23.4 use the same type List T as in Section 11.12? Where is List T defined?
I think lists are not simple types but recursive types (not introduced till Chapter 20), so why does Section 11.12  cover lists?

Thanks.

  11 Simple Extensions

  11.12 Lists

  The typing features we have seen can be classiﬁed into base types like
  Bool and Unit, and type constructors like → and × that build new types
  from old ones. Another useful type constructor is List. For every type
  T, the type List T describes ﬁnite-length lists whose elements are
  drawn from T.

  Figure 11-13 summarizes the syntax, semantics, and typing rules for
  lists. Except for syntactic diﬀerences (List T instead of T list,
  etc.) and the explicit type annotations on all the syntactic forms
  in our presentation, these lists are essentially identical to those
  found in ML and other functional languages. The empty list (with
  elements of type T) is written nil[T]. The list formed by adding a
  new element t1 (of type T) to the front of a list t2 is written
  cons[T] t1 t2 . The head and tail of a list t are written head[T] t and tail[T] t. The boolean predicate isnil[T] t yields true iﬀ
  t is empty.

and

  23 Universal Types

  23.4 Examples

  Polymorphic Lists

  As an example of straightforward polymorphic programming, suppose our
  programming language is equipped with a type constructor List and term
  constructors for the usual list manipulation primitives, with the
  following types.

ñ nil : ∀X. List X
cons : ∀X. X → List X → List X
isnil : ∀X. List X → Bool
head : ∀X. List X → X
tail : ∀X. List X → List X

  When we ﬁrst introduced lists in §11.12, we used “custom” inference
  rules to allow the operations to be applied to lists with elements
  of any type. Here, we can give the operations polymorphic types
  expressing exactly the same constraints


texts: I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?


texts: Why is backtracking a necessary step in the Maze problem?

texts:
The problem I am working on is specifically this:

A Maze is given as N*N binary matrix of blocks where source block is
the upper left most block i.e., maze[0][0] and destination block is
lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source
and has to reach the destination. The rat can move only in two
directions: forward and down.

The question essentially asks to find and print the path that exists through a given maze from the top left to the bottom right of the maze. The details of the problem can be found here.
The core of the C/C++ code for this problem's solution is this:
/* A utility function to check if x,
y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y)
{
    // if (x, y outside maze) return false
    if (
        x >= 0 && x < N && y >= 0
        && y < N && maze[x][y] == 1)
        return true;

    return false;
}

/* This function solves the Maze problem
using Backtracking. It mainly uses
solveMazeUtil() to solve the problem.
It returns false if no path is possible,
otherwise return true and prints the path
in the form of 1s. Please note that there
may be more than one solutions, this
function prints one of the feasible
solutions.*/
bool solveMaze(int maze[N][N])
{
    int sol[N][N] = { { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 } };

    if (solveMazeUtil(
            maze, 0, 0, sol)
        == false) {
        printf("Solution doesn't exist");
        return false;
    }

    printSolution(sol);
    return true;
}

/* A recursive utility function
to solve Maze problem */
bool solveMazeUtil(
    int maze[N][N], int x,
    int y, int sol[N][N])
{
    // if (x, y is goal) return true
    if (
        x == N - 1 && y == N - 1
        && maze[x][y] == 1) {
        sol[x][y] = 1;
        return true;
    }

    // Check if maze[x][y] is valid
    if (isSafe(maze, x, y) == true) {
        // mark x, y as part of solution path
        sol[x][y] = 1;

        /* Move forward in x direction */
        if (solveMazeUtil(
                maze, x + 1, y, sol)
            == true)
            return true;

        /* If moving in x direction
           doesn't give solution then
           Move down in y direction  */
        if (solveMazeUtil(
                maze, x, y + 1, sol)
            == true)
            return true;

        /* If none of the above movements
           work then BACKTRACK: unmark
           x, y as part of solution path */
        sol[x][y] = 0;
        return false;
    }

    return false;
}

I am confused about the following part of the solution in the function solveMazeUtil:
/* If none of the above movements
               work then BACKTRACK: unmark
               x, y as part of solution path */
            sol[x][y] = 0;
            return false;

What is the need to reset the value of the cell located at x,y in the solution matrix? The value of sol[x][y] was set to 1 only because it was a valid cell to go to. I don't understand why sol[x][y] has to be reset just because its neighboring cells are invalid?
EDIT:
I thought about this problem a little more and I realized the cell is only reset to zero when the program runs into a dead-end (0s in the maze, in this case) on its right side AND below it. If this cell is reset, the cell is available to be explored again.
What purpose does it serve? If the program encounters this reset cell again, it will perform the same computations for this cell again and encounter the same dead-ends as before.


texts:
I am not experienced in machine learning but I have been looking at the Python toolklit scikit-learn. I have thousands of mammograms and I have written an algorithm to find the outline of the images. I have some cases where the outline of the mammogram is not correct. I would like to be able to take these thousands of outlines of mammograms that are arrays (of different lengths) of the x and y coordinates of the edge and to classify them. This would allow me to find the outliers and also possibly allow me to categorise the images. Does a clustering algorithm exists that would allow me to do this?

Edit 1:

Expected outline

Unwanted outline


texts:
It is proven by Time hierarchy theorem that EXPTIME-complete do not belong to P even if we do not know if NP belong to P.

Before I read wiki, I found EXPTIME algorithm for solving 3-sat, the brute algorithm $O(2^n)$. Could I announced then, that there could not be polynomial solution for 3-sat?

Time hierarchy theorem prove that there are EXPTIME problems that are not in P. But how can you prove that problem is EXPTIME and not super-polynomial time?
Also please tell me what is the deference between super-polynomial and polynomial times in context of polynomial expression.

*If you have solution for just one of the questions it's fine.


texts: Is it possible to construct a C^5(U) with V^2=U and no work qubits (Nielsen & Chuang Exercise 4.28)

texts:
My question is related to the exercise 4.28 in the book of Nielsen and Chuang (Quantum Computation and Quantum Information). Here is the exercise

For $U=V^2$ with $V$ unitary, construct a $C^5(U)$ gate analogous to that
in Figure 4.10, but using no work qubits. You may use controlled-$V$ and
controlled-$V^{\dagger}$ gates.

I think the exercise in the current form is not possible to solved. Since any usage of a controlled-$V$ or $V^{\dagger}$ gate gives even 4 cases (with case I mean a combination of qubits) where $V$ or $V^{\dagger}$ is applied. So we can increase the number of applied $V$ gates with any usage of a controlled-$V$ or decrease the number of applied $V^{\dagger}$ gates with any usage of a controlled-$V^{\dagger}$ by 4. But to obtain the controlled-$U$ gate, we may only have $2$ usages of a $V$ gate. Thus any way we apply the controlled-$V$ or $V^{\dagger}$ gates, in the end we will always have more than 2 cases where a $V$ or $V^{\dagger}$ is applied (with applying I mean that it does not contract with another controlled gate, so it will really be applied at the end).

Note that this problem does not occur for controlled-X gate since an addition can be though as an addition modulo 2, therefore we can decrease the numbers of cases where a qubit is switched.

Since I think that this chapter is heavily influenced by the paper https://arxiv.org/abs/quant-ph/9503016.pdf which constructs a $C^3(U)$ with controlled-$V$ gates where $V^4=U$, I think it should be $V^16=U$ in the exercise. However I am not certain if there really does not exist a solution, maybe one using maybe gates creating a superposition like the Hadamard gate. So my question is, if someone has a solution for this exercise or a proof that it is impossible to do.


texts: Can I program a universal Turing machine to accept arbitrary input encodings?

texts:
I've been reading about building Turing machines for specific purposes, and some sources talk about input encodings and some talk about programming specific machines, but I've been unable to find anything that discusses both. Here's a specific set-up:

  Suppose you have a universal Turing machine. It has a two-sided infinite tape, where the right side encodes a specific function to compute and the left side encodes the input to be provided to that function.

In general, I'm interested in the interaction between the encoding of the input, the specific program for the TM, and which UTM it is. My main question is:

  If I have a fixed underlying UTM, a fixed encoding of the input, and a desired function to compute, can I always find a way to program my UTM to compute that function on the input supplied in the specified encoding?

  For example, if I have the (2, 18) universal Turing machine, I encode the input using the system described here, and know that I want to compute the function $f(x, y, z) = x^3+xy+z^9$ is there guaranteed to be a program I can use to achieve this result?

I am under the impression that the answer is yes, but am not sure enough of my knowledge of Turing machine architecture to prove it.

More generally, if we think of this set up as having four parameters - the specific UTM, the specific input encoding, the specific function, and the specific program - is it always the case that if we fix three of these four parameters there will be a setting for the fourth?


texts: Why a random minimum spanning tree is not an uniform spanning tree?

texts:
A spanning tree chosen randomly from among all the spanning trees with equal probability is called a uniform spanning tree.

A model for generating spanning trees randomly but not uniformly is the random minimum spanning tree. In this model, the edges of the graph are assigned random weights and then the minimum spanning tree of the weighted graph is constructed [Wikipedia].

Why a random minimum spanning tree is not an  uniform spanning tree ?


texts: Does the transitivity of big-O notation hold for asymptotically nonnegative functions?

texts:
I'm reading the book Introduction to Algorithms and in Chapter 3 it is said that if $f(n)$ and $g(n)$ are asymptotically positive then

$$
f(n) = O(g(n)) \text{ and } g(n) = O(h(n)) \text{ implies } f(n) = O(h(n))
$$

However, I don't see why this wouldn't also be valid if you just required $f(n)$ and $g(n)$ to be asymptotically nonnegative.

Edit:
Here is the definition of $O$ used in the book:

$$
\begin{aligned}
O(g(n)) = \{f(n):&\text{ there exist positive constants $c$ and $n_0$ such that}\\
&0 \le f(n) \le cg(n) \text{ for all } n \ge n_0
\}
\end{aligned}
$$


texts:
Possible Duplicate:
  Proof of linear search?

I'm reading the MIT Press, Introduction to Algorithms textbook 3rd edition, and I am a bit confused by an exercise.

2.1-3
Consider the searching problem:
Input: A sequence of n numbers A =  and a value v.
Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.

Write pseudocode for linear search, which scans through the sequence looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure your loop invariant fulfills the three necessary properties.

Earlier in the book I read that "We must show three things about a loop invariant:

Initialization: It is true prior to the first iteration of the loop.

Maintenance: If it is true before an iteration of the loop, it remains true before the
next iteration.

Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
"

I wrote this as my pseudocode

index = nil
j = 1
while j <= A.length and index == nil
  if A[j] == v
    index = j
  j = j + 1

But when it comes to proving using a loop invariant I have no idea what to do. What do I even use as a loop invariant? To be honest I'm not really clear about the entire loop invariant concept. Can someone please help me understand this?

Thanks.


texts:
Given an array of $n$ integers $A$, and some value $m$, determine if it is possible, by using certain amounts of each element, to get a total sum equal to $m$. Consider that you can use any amount of any of the elements.

This is sort of like the subset sum problem, but in this case that sum can contain elements multiplied by some factor, and this factor has no upper-bound. I'm struggling quite a bit with this problem, so does anyone know how can I solve it?


texts: Which Is a Better Way of Obtaining Scales, Gaussian Blur or Down Sampling?

texts:
In computer vision, scales are important when we carry out a scene analysis. Choosing different scales affect the result of the analysis. For example, if a face is relatively small in the scene, then the details including nose, eyes will be omitted. On the other hand, details on larger faces become relatively more salient.

I know both Gaussian Blur with different sigmas and Down Sampling on the image can generate different scales. Which is more reasonable on a cognitive sense?


texts: Why is bias not defined for non-stationary MDP policies?

texts:
The Handbook of Markov Decision Processes 1 defines bias of a stationary deterministic policy as follows:

$h(x, \phi) = \sum_{n = 0}^{\infty} E[r(x_n, \phi(x_n)) - w(x_n , \phi)]$

where $x$ is a state, $\phi$ is a stationary deterministic policy, $r(s, a)$ is the mean reward of taking action $a$ in state $x$ and $w(x, \phi)$ is the expected reward per unit time while following policy $\phi$.

Later the same book also mentions that bias is undefined for non-stationary policies. What is it about non-stationary policies that precludes a bias definition?


texts: Query Logs and evaluation of search engines

texts:
I'm taking a course about Information Retrieval and we had a quiz involving the evaluation of search engines.

We had a problematic question regarding "Query Logs" (basically recording the queries that users searched in the past and their response for the queries e.g links clicked), and I hope you can help me figure out the answer:

Using query logs can improve the retrieval efficiency of the search engine by:

A. Learning common typos in queries
B. Learning the connection between pages the users clicked as the result of different queries
C. Saving popular queries in a cache
D. A + B + C
E. A + B + C doesn't affect the efficiency of retrieval
F. The Collection of query logs can't affect the efficiency of retrieval

I circled option D (A+B+C) and I was wrong.

My Lecturer refuses to reveal the correct answer - I can appeal about her decision but I want to be certain I'm correct.

The explanation for my answer: the question talked about improving the retrieval efficiency, and to the best of my knowledge retrieval efficiency is the time measured from when the user clicked "Search" until the user received the results back.

Therefore, I think A is correct because if we learn common typing mistakes in queries we can create a dictionary of those common errors and create spell correction algorithms. For example if many users typed "bast" instead of "best", we can use a data structure similar to a cache. (However, this might require an enormous amount of memory, but the question didn't mention memory efficiency)

I think C is correct because we can save the results of the popular queries in a cache instead of using the (fairly slow) posting file.

B is the only option that I'm not sure why is correct, but I assumed that if A and C are correct, B can be correct.

Could you please tell me what you think about the question and my answers?

Thank you!


texts:
We are given a tree with $n$ vertices and some of the vertices act as a "hotspot".

We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest hotspot from $c$ such that we do not travel through the edge between nodes $a$ and $b$.

I have tried many data structures like using lowest common ancestor and algorithms like mo's algorithm on a tree, I have also tried to process queries which are closer to root first, but none of these have given me the desired complexity for each query which is anywhere between $O(1)$ to $O(\log n)$.

Is there any better algorithm or perhaps some clever precomputation(in less time than $O(n\log n)$ that can be used to solve this problem?


texts:
I have an Excel with 40columns and 20k rows, and i have to store it in a database but i cant figure the best approach for it, the excel format is like this:

This table has 30 columns for days, then 11 columns for the next 11 weeks and then 9 columns for the next 9 month, in resume the first month is in days the next 3 months are in weeks and the rest of the year is in months.

Each column has the number of pieces that i need to produce certain product in that span of time.

Part number | 1/1/2018 ||||| 30/1/2018 | Week6 ||| Week16 | Month4 ||||||Month12
PART1             2             5          10        12        40          50
PART2             3             4          13        11        50          70
PART3             4             3          13        15        60          60
PART4             1             3          16        12        40          30

This Excel file has to be pasted in to a datagridview and then save it in a DB,
should i use 1 table or more? what shold be my table design to store this data?


texts: Algorithm - How to show Big O for 2 functions

texts:
I believe that Ln(n) is <= 2^(sqrt(2*lg(n))), so I am trying to prove it

I know that you can show Big O by showing Little O, so I am trying to take the limit as n approaches infinity of Ln(n)/2^(sqrt(2*lg(n)))

However I am finding it hard to prove this using the limit definition

I would appreciate any help to see how to solve this! Thanks


texts: Vertex-disjoint cycles passing through a collection of vertices

texts:
I am wondering about the complexity of the following problem: given a directed graph $G=(V,E)$ (which may have self-loops at some vertices) and a subset of the vertices $U \subset V$, does there exist a collection of vertex-disjoint cycles $C_1, C_2, \ldots$ such that each $u \in U$ belongs to some cycle $C_i$?

When $U=V$, I can see how to reduce this to the problem of finding a maximum matching in a bipartite graph. I'm not sure how to handle the case when $U$ is a strict subset of $V$.


texts: The communication complexity of non-equality

texts:
I'm familiar with the fooling set technique to obtain lower bounds for communication complexity protocols. The most basic example is the equality function for which the diagonal matrix gives the fooling set of size $2^n$, because each 1-output needs to be in its own monochromatic rectangle. Also, a similar property seems to be true when looking at 0-outputs: If we have a cover of the 0-outputs by a set of monochromatic rectangles, then no rectangle can contain all 0-outputs of 2 (or more) rows. This implies that we get the same complexity for the NEQ (non-equality) problem.

However, I read that for non-deterministic algorithms, the complexity of NEQ is only $O(\log n)$. This is because we simply need to "guess" an index $i$ where the inputs of Alice and Bob differ, which takes $\log n$ bits and then use $1$ additional bit to encode if $i=0$ or $i=1$.

But the complexity of such a non-deterministic algorithms is lower-bounded by the log of the size of the smallest cover of the $0$-outputs, which would still be $\log(2^n)=n$ (by the above argument that each row in the matrix accounts for at least one rectangle in the cover).

Obviously, I'm missing something here, but I haven't figured out what it is...


texts:
I used this generalized transition graph with 3 states and got an equivalent generalized
transition graph with 2 states:

GTG:

Equivalent with 2 states:

I'm not sure about the regular expressions linking the nodes $q0$ and $q2$, if someone can clarify where I may have gone wrong here.


texts: What is a good rule-of-thumb for the size of leaf nodes in a rope?

texts:
The formal descriptions of ropes I’ve found use very small numbers like 4 or 8 characters per leaf node as the maximum size. Some also mention that this (obviously) is not a very efficient rope size for use in real life, but makes it easier to see the tree in a demonstrative diagram.

The trade-off is between speed of manipulation and memory/access overhead. What’s the correct size for a rope on a real computer?


texts: Genetic Algorithm, Neural Network, Deep Learning, Machine Learning Similarities and Applications?

texts:
I am a computer engineering student and trying to get the idea behind all these Artificial Intelligence Concepts and applications. I know little theoretically about machine learning and some high level brief introduction of artificial intelligence as a whole and neural network. What i am interested in is knowing the similarities or difference between the concepts: Deep Learning, Genetic Algorithm/Programming, Artificial Neural Networks and Machine Learning. How do they relate or how they help each other? What are their particular applications?

I google a bit but could not satisfy myself with the answers i got. As a beginner i would like to know what particular part they each play in Artificial Intelligence field. What type of problem they each solve and how?

Update:

If the question is too broad, i am also expecting a broad answer.Even, if the broad answer is too much then can you please tell me any particular book perhaps that might contain overview of these topics, so that i can relate by myself and go on learning.


texts: Can a RAM calculate its own Gödel number?

texts:
You can get the Gödel number of a RAM by making it a list of commands and making this list an integer.

So, what I thought is something like "The RAM that would return its own Gödel number (say, $x$) would have to have the information $x$ in it, so the integer would be greater than $x$, so it would not return its own Gödel number."

But then I noticed that for specific numbers you could do compressing, such as calculating $10^{9999}$ instead of writing 100000...000 in the code of the RAM. Probably the Gödel number would not be $10^{9999}$ though, but at least it could be.

Question: Is there a RAM that calculates its own Gödel number? Can there be such?


texts:
We have four categories:

  additive constants, multiplicative constants, polynomials, and
  exponentials

When determining the growth order of functions, we only care about polynomials and exponentials and ignore additive/multiplicative constants.

To  determine whether some arbitrary function f(x) is Big-O of another function, say, g(x), we can compute the limit of f(x) / g(x) as x tends to infinity.

However, it might be difficult to to evaluate this limit, and so we can evaluate the limit of log(f(x) / g(x)) instead.

I learned that when we evaluate the logarithm, we have to care about multiplicative constants as well. For instance:

  f(x) = x^2

  g(x) = x^3

  log(f(x)) = 3 log x

  log(g(x)) = 2 log x

In the example above, when using the logarithms to compare the growth order of f(x) to g(x), we have to consider the multiplicative constants in front of the log. This makes sense to me. However, my instructor also stated that conversely, when we exponentiate the term, then we "only care about exponentials." I'm paraphrasing what my instructor said, and I'm awfully confused by what he meant. When we take the logarithm, we consider multiplicative constants, but when we do the opposite--exponentiate--which of the four categories do we care about now?


texts: Effectively compute bound and period of regular expression on single alphabet

texts:
It is known that an infinite language $L\subseteq \{a\}^*$ is regular iff the set $U:=\{x|a^x\in L\}$ is ultimately periodic. (A set $U\subseteq\mathbb{N}$ is said to be ultimately periodic if there exists bound, $n$, and period, $p$, such that $\forall x\ge n, x\in U\iff x+p\in U$)

My question is given a finite formalism (DFA, Regular Expression, Regular Grammar, etc.) of an infinite regular language $L$ over $\Sigma=\{a\}$, is the bound $n$ and period $p$ effectively computable? Let us start with regular expression. Suppose we are given the regular expression $R$ of $L$.

What I have thought till now...
We will proceed inductively. (Structural induction on $R$)

If $R=R_1+R_2$ then let $(bound,period)$ of $R_i$ be $(n_i,p_i)$ for $i=1,2$. I claim, for $R$, $n=max(n_1,n_2)$ and $p=lcm(p_1,p_2)$
If $R=R_1.R_2$ then I claim $(n,p)=(n_1+n_2, p_1+p_2)$
If $R=(R_0)^*$ then I claim $p=min(U)$ where $U=\{x|a^x\in R_0\}$.

Specific Questions:

Are the claims true? What would be a nice formal way to show that?
What if the DFA was given? (The period would be something based on the number of states)
I also suspect that in item 3 above, even if $R_0$ is not regular, then also $R$ is regular. So the bound and period should be independent on the bound and period of $R_0$, if assumed to be regular.


texts:
I know that it can be proven PROLOG is Turing-complete by constructing a program that simulates a Turing machine like this:

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

Source

However, I’m wondering which parts of the PROLOG language one could strip away (esp. function symbols, clause overloading, recursion, unification) without losing Turing completeness. Are function symbols themselves Turing complete?


texts: What is it called when you classify words into categories, but not by part of speech?

texts:
I'm looking to classify words into type categories like sushi to food, baseball to sports, happy to emotions, panda to animals etc.

What is this type of classification called? I see lots of NLP-related articles discussing parts-of-speech classifiers. This isn't helpful.

I know any word has many possible categories. For example, panda could be classified as animal, mammal, Ailuropoda (it's genus), or even algorithms (as in, "Google Panda"). I'm open to any of the above to start. My preference would be colloquial rather than scientific (panda to animal).

Ideally it would return probability for different categories. For example, panda might return 0.8 for animal and 0.3 for bear and 0.1 for algorithm.


texts:
I have a histogram of occurrences, as a list of counts (non-negative integers). For the purposes of a compression algorithm (specifically arithmetic coding) I must quantize these occurrences into a histogram whose entries sum to $2^n-1$.

To maintain sanity, I require some properties of the quantization algorithm:

Any element with 0 occurrences must have 0 occurrences after quantization.
Any element with > 0 occurrences must have > 0 occurrences after quantization.
The sum of the quantized histogram must add up to $2^n-1$.

To guarantee that there is a satisfiable solution there will be no more than $2^n-1$ elements.

Given those constraints the values of the quantized histogram $Q$ must proportionally be as close as possible as the values of the original histogram $H$.

Or more formally:
$$\forall i: H_i > 0 \rightarrow Q_i > 0$$
$$\forall i: H_i = 0 \rightarrow Q_i = 0$$
$$\Sigma Q = 2^n-1$$
$$\min \sum_i (H_i/\Sigma H - Q_i/\Sigma Q)^2$$

Is there a direct algorithm that gives an optimal result? Or perhaps a fast near-optimal approximation?

Without requirement #2 there is a solution by choosing $Q_i = \lfloor H_i/\Sigma H \cdot (2^n-1) \rfloor + a_i$. Where $a_i$ is initially 0 for all $i$. It's easy to see that $\Sigma Q \leq 2^n-1$, and setting $a_i$ = 1 for the $2^n-1 - \Sigma Q$ elements that have the biggest undershoot error solves the problem optimally.

The difficulty lies in the requirement that no element with nonzero occurrences may be floored to zero occurrences in the quantized histogram. Consider [1, 1, 1, 1000]. Without this requirement the most accurate quantization to $n = 3$ is [0, 0, 0, 7]. However the requirement gives us [1, 1, 1, 4].


texts: insert and delete in order statistic tree

texts:
I am having trouble in understanding order-statistics tree .

Definition :
Every node in tree stores the number of descendants of itself .
Can you please explain the Algorithm or pseudocode how to Insert and Delete a node in the tree when tree is to be balanced .

Basically i want to find the rank of an element in the tree in O(log N) time complexity and nodes can be inserted and deleted in between querries .

P.S. I am able to understand the rank(x) operation .


texts: Shortest path from $s$ to $v$ in unweighted simple directed graphs

texts: Let $G=(V,E)$ be an unweighted simple directed graph. Some of the edges are colored red. Let $E'⊆E$ denote the set of red edges. Given a vertex $s∈V$,suggest an efficient algorithm for finding the length of a shortest path from $s$ to every other vertex in the graph, fulfilling the following condition: the path includes at most two red edges. In other words, every $v∈V$ should be labeled with the length of a shortest path from $s$ to $v$ in which there are at most two edges from $E'$ and any number of edges from $E\backslash E'$.


texts: Divide grid so that each box has only one object

texts:
Is there an efficient algorithm to divide a 2D space, which contains several different sized rectangles, such that each partition has only a single object. Please see the attached image.

I have come up with a recursive algorithm that cycles through the 2 axis and divide the boxes until there is only one object in a box/partition. The only problem is that the arrangement that I have in mind is actually inefficient and it seems very hard to handle cases in which the rectangles are overlapping. In the case where the rectangles are overlapping, we want all the overlapping rectangles to be inside the same partition.

Another detail, the boxes will always be axis aligned and the partitions also have to be axis aligned.

Any help will be greatly appreciated. Thank you!


texts: Finding pairs of points that have a given offset

texts:
Problem: Given a set of points $S = \{x_1, x_2, x_3, ..., x_n\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points $(x_i, x_j)$ such that the quantity $|x_i-x_j-v|$ (Euclidean norm) is smaller for any pair $(x_i,x_j) \in Z$ than that of any pair not in $Z$.

One obvious approach would be to maintain a max-heap of size $k$ and run through all pairs of points $(x_i, x_j) \in S^2$, inserting pairs into the heap if $|x_i-x_j-v|$ is smaller than the current maximum.  This algorithm has $O(mn^2 \log k)$ running time.

Is there a faster algorithm?  Is there a lower bound on the complexity of this problem?

This problem is motivated by an application where $50 \leq m \leq 1000$, $10^5 \leq n \leq 10^6$, and $5 \leq k \leq 100$, and the running time should be in seconds, not minutes or hours (which is I the naive approach above is not applicable).


texts: Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem

texts:
I recently came across the sentence in the Book Introduction to Algorithms section 4.1 The maximum sub-array problem:

We still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $n$ days.

Here $n$ is the number of days taken as an example to show the changes in price of stock.
We can consider this is the size of an array A.
Where we are provided with an Array A and we need to find the net change is maximum from the first day to the last day.

To explain more specifically it means for an array $A$ of size $n$ we need to check $\binom{n-1}{2}$ subarrays.

But, I cannot understand how we need $\binom{n-1}{2}$ sub-arrays?
If we take an array of size 5 could someone please explain to me why we need only 6 sub-arrays.
Won't the sub-arrays be:
[1...5]
[1...4]
[1...3]
[1...2]

[2...4]
[2...5]

[3...5]
[4...5]

Please correct me if I am wrong.
References: Maximum Subarray Problem

Thank you.