texts:
From Computer Organisation and Architecture:

  The IAS operates by repetitively performing an instruction cycle. Each
  instruction cycle consists of two sub cycles. During a fetch cycle,
  the opcode of the next instruction is loaded into the IR and the
  address portion is loaded into MAR. This instruction may be taken from
  the IBR, or it can be obtained from memory by loading a word int he
  MBR, and then down to the IBR, IR, and MAR.

Now here, is there part I do not understand:

  Why the indirection? These operations are controlled by electronic circuitry and result in the use of data paths. To simplify the
  electronics, there is only register that is used to specify the
  address in memory for a read or write and only one register used for
  the source or destination.

Can anyone explain this to me more intuitively?  Why is this indirection being used?


texts: Explanation of O(n2^n) time complexity for powerset generation

texts:
I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward:

def power_sets(A):
    """Returns the power set of A as a list of lists"""

    if len(A) == 0:
        return [[]]

    else:
        ps_n1 = power_sets(A[:-1]) # Powerset of set without last element
        # Add nth element to each subset of the powerset of n-1 elements
        ps_n = [sub + [A[-1]] for sub in ps_n1]

        # Combine the two sets and return
        return ps_n1 + ps_n

It's clear that the space complexity is $O(n2^n)$, since there are $n$ items in the set, and each element is in half of the $2^n$ sets.

However, the book that I'm working from says the time complexity is also $O(n2^n)$, which makes perfect intuitive sense, but I'm having a hard time justifying it mathematically.

Other than by saying "there are x number of items to mess with, so time complexity is at least as much", can anyone offer an explanation of the runtime analysis based on the runtime of the statements in my algorithm?

This answer pretty much only says that the runtime is such because of the space complexity (not very satisfying, but as an aside--can the runtime ever be better than the space complexity?)

I saw this answer, but to be honest it is a bit difficult to understand. It seems to suggest in the last line that the runtime is $O(n^2*2^{n!})$ (since (I think) $|P_i| = 2^i$), and that doesn't seem right either.

I tried drawing out the call tree and that didn't help, as there are only $n-1$ recursive calls made, and from what I can tell each spends $O(n^2)$ time.

Anyway, can someone offer a compelling explanation for this runtime?


texts: Is there a single-word term for "the number of edges in a graph"?  Something along the lines of "arity" for function parameters.


texts: Differences in services provided by grid computing and cloud computing

texts:
What are differences in services provided by grid computing and cloud computing?

From http://ccskguide.org/cloud-computing-vs-grid-computing/ and http://www.ibm.com/developerworks/web/library/wa-cloudgrid/

  While grid computing facilitates access to computing resources as if they were public utilities, cloud computing offers on-demand resource provisioning.

The article says grid computing provide computing resources just like public utilities (such as electricity). Are public utilities different from on-demand resources provisioning?

It also says one component of cloud computing is utility computing, just like paying for a public utility such as electricity:

  Cloud computing is a development on grid computing. It requires three
  fundamental components:

  Thin clients (alternatively, clients with a thin-thick switch may be used)
  Grid computing
  Utility computing (i.e. paying for resources used from shared servers, similar to paying for a public utility, such as electricity)

So do both grid computing and cloud computing provide their services just like electricity?

Thanks!


texts: Assume we want to define a context free grammar of say a programming language, where on each line everything after the character # until the end of line is considered a comment and should be ignored. How to express that in a context free grammar?


texts: Is my assumption about non trivial propery correct?

texts:
"make sure you understand why for a non trivial property $S$, $\bar{S}$  is also non trivial"
My assumption is: $S$ is non trivial property: There are L1,L2 such that $L_{1},L_{2}\in RE$ and L1 sattisifies the property whereas L2 doesn't.
If i assign the complement then it still holds the same just reverse the relation between L1 which is now $L_{1}\notin S $ and $L_{2}\in S$ ==>$\bar{S}$ is a non trivial.
Is my assumption correct?


texts: Which of the following words is in the language of the grammar G?

texts:
This is taken from a practice quiz by my university.
I ruled out that aabbbaab is not part of the grammar:
S → aSb → aaSbb... This shows that I can't make this word because it would have to have atleast two b's at the end in order for me to add more letters
Then I tried to see if abbaabb can be derived from the grammar and I experienced the same thing:
S → aSb → aaSbb... This shows that I can't make a word with two b's at the end without having at least two a's in the beginning
Finally, I tried to do aabaabbb:
S → aSb → aaSbb → aaSSbb → aaSaSbbb... I decided it can't be this one because even if I make aaSaSbbb into ϵ, I still need to find a way to make aaSaSbbb into ba so I can derive the word. It doesn't seem like I can do that.
So by elimination I thought the correct answer was aabaabb but I was wrong.
Please show me how to work out whether a word can be derived from a grammar.


texts: Finding edge-optimal reachability-equivalent digraphs to bipartite digraphs

texts:
I'm looking for an algorithm that, given a directed bipartite graph, builds another graph (possibly with additional vertices) that has fewer total edges but the same reachability patterns.  In particular:

The input to the algorithm is a bipartite directed graph $G'=(V,E)$ with all edges directed from $L$ to $R$ (where $V=L\cup R$) and no repeated edges.

The output should be a directed graph $G'=(V',E')$ that satisfies the following conditions, and that minimizes $|E'|$:

$G'$ has all vertices from the input graph and possibly additional ones, i.e., $V \subseteq V'$
$G'$ no edges into $L$ and no edges into $R$
for each edge $\ell \to r$ in $G$, there is a single path $\ell \leadsto r$ in $G'$ (one and only one path)
for each $\ell \in L, r \in r$, if there is a path $\ell \leadsto r$ in $G'$, then there is an edge $\ell \to r$ in $G$

In particular, the output of the algorithm should be the minimal-edge-count graph among the set of all graphs that satisfy the above conditions.

Roughly speaking: given a directed bipartite graph, we want to find another directed graph that's "reachability-equivalent" in some sense and that has the fewest number of edges possible.

Question: is there an efficient algorithm for this task?

Here is a picture of these 'reachability-equivalent' graphs to show that it is possible to achieve a non-trivial reduction in the number of edges:

This is like finding a transitive reduction (or minimum equivalent graph) of a particular kind of dag, but where we're allowed to add additional vertices.


texts: Will an NPDA accept a string that reaches a final state but does not have all its input consumed yet?


texts: Is every language over any alphabets is accepted by automata?

texts:
The answer is no to what i have learned but i am finding difficulties to absorb it reason being . We say for every language we have a grammar as language without grammar makes no sense even in general scenerio also. i have taken this argument as my base for the conclusion of my answer as i found this argument somewhere on stackexchanege please correct me if iam wrong.

coming to point , as there are grammar for every language which also indicate existence of set of rules for the formation of the language. Taking this ahead , i wonder if we can device a set of rules which is indeed a process to derive or generate a solution then why cant we form an automata for the same. Adding more to this point , we know the highest class of automata is turing machines capable of accepting many languages but not all , and we know that the languages not accpeted by turing machines have grammars( as said every language has grammar) means there are some machines automata that does not necessarily satisfies the all the langugaes not accepted by turing machines but do satisfy some but all of them , using this we say there are different classes of machines which are not turing but accept some   languages not accpeted by turing machines if this is not true than there must exist the languages that do not have any grammar but as said every languae has grammar.  adding more woes to this argument , we have not able to identify any machine more powerful then turing , so this means some of the arguments made here are wrong . but i am finding it difficult to understand which one of them is wrong, so please let me know.


texts: Encoding 1-out-of-n constraint for SAT solvers

texts:
I'm using a SAT solver to encode a problem, and as part of the SAT instance, I have boolean variables $x_1,x_2,\dots,x_n$ where it is intended that exactly one of these should be true and the rest should be false.    (I've sometimes seen this  described as a "one-hot" encoding.)

I want to encode the constraint "exactly one out of $x_1,\dots,x_n$ must be true" in SAT.  What is the best way to encode this constraint, to make the SAT solver run as efficiently as possible?

I can see many ways to encode this constraint:

Pairwise constraints. I could add pairwise constraints $\neg x_i \lor \neg x_j$ for all $i,j$ to ensure that at most one $x_i$ is true, and then add $x_1 \lor x_2 \lor \cdots \lor x_n$ to ensure that at least one is true.

This adds $\Theta(n^2)$ clauses and no extra boolean variables.
Binary encoding.  I could introduce $\lg n$ new boolean variables $i_1,i_2,\dots,i_{\lg n}$ to represent (in binary) an integer $i$ such that $1 \le i \le n$ (adding a few boolean constraints to ensure that $i$ is in the desired range).  Then, I can add constraints enforcing that $x_i$ is tree and that all other $x_j$'s are false.  In other words, for each $j$, we add clauses enforcing that $i=j \Leftrightarrow x_j$.

This adds $\Theta(n \lg n)$ clauses and I don't know how many extra boolean variables.
Count the number of true values.  I could implement a tree of boolean adder circuits and require that $x_1+x_2+\dots+x_n=1$, treating each $x_i$ as 0 or 1 instead of false or true, and use the Tseitin transform to convert the circuit to SAT clauses.  A tree of half-adders suffices: constrain the carry output of each half-adder to be 0, and constrain the final output of the final half-adder in the tree to be 1.  The tree can be chosen to be of any shape (balanced binary tree, or unbalanced, or whatever).

This can be done in $\Theta(n)$ gates and thus adds $\Theta(n)$ clauses and $\Theta(n)$ new boolean variables.

A special case of this approach is to introduce boolean variables $y_1,\dots,y_n$, with the idea that $y_i$ should contain the value of $x_1 \lor x_2 \lor \cdots \lor x_i$.  This intent can be enforced by adding the clauses $y_i \lor \neg x_i$, $y_i \lor \neg y_{i-1}$, and $\neg y_i \lor x_i \lor y_{i-1}$ (where we treat $y_0$ as a synonym for false) for $i=1,\dots,n$.  Next, we can add the restrictions $\neg y_i \lor \neg x_{i+1}$ for $i=1,2,\dots,n-1$.  This is basically equivalent to the Tseitin transform of a half-adder tree, where the tree has a maximally unbalanced shape.
Butterfly network. I could build a butterfly network on $n$ bits, constrain the $n$-bit input to be $000\cdots 01$, constrain the $n$-bit output to be $x_1 x_2 \cdots x_n$, and treat each 2-bit butterfly gate as an independent gate that either swaps or does not swap its input with the decision of which to do based upon a fresh new boolean variable that is left unconstrained.  Then, I can apply the Tseitin transform to convert the circuit to SAT clauses.

This requires $\Theta(n \lg n)$ gates and thus adds $\Theta(n \lg n)$ clauses and $\Theta(n \lg n)$ new boolean variables.

Are there any other methods I have overlooked?  Which one should I use?  Has anyone tested this or tried them experimentally, or does anyone have any experience with any of these?  Is the number of clauses and/or the number of new boolean variables a good stand-in metric for estimating the impact of this on SAT solver performance, or if not, what metric would you use?

I just noticed that this answer has some references on enforcing cardinality constraints for SAT, i.e., enforcing the constraint that exactly $k$ out of the $n$ variables are true.  So, my question comes down to a special case where $k=1$.  Maybe the literature on cardinality constraints will help shed light on my question.


texts: Defining a graph decision problem not in NP

texts:
I have been doing some research online looking for graph problems that are decidable but not in NP. I have found the concept of succinct graphs, which if I understand properly, consist of making the input small (i.e. supplying the graph structure using a small amount of memory) so that when properties of the graph are checked, the time taken is larger than polynomial on the size of the input (and so taking problems that are in P into NP, and problems that are in NP into NEXP).

What I was wondering is whether you could do something similar but by suppliying the graph in a "standard" way (i.e. adjacency matrix), but then asking a question with a "large" answer. For instance would the following problem not be in NP?

Given a graph G = (V,E), of size n, does it contain 2^n distinct paths of size n?

To me it feels like a a certificate could not be checked in polynomial time, and so this problem cannot be in NP. I was wondering if anyone has thought of something similar, or whether there is something you could check in polynomial time that would answer this question without explicitly listing out 2^n paths.

Any input is greatly appreciated. Thanks!!


texts: Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)

texts:
NOTE: The statement of this question has a LOT of misconceptions.

Is there any relation between the Complexity Classes (like P or NP) and Language hierarchies (like REC or RE) ?

  Form what I understand: (easy things are the things that can be done in polynomial time span, as opposed to tough things. Tough things require exponential time span or even infinite time to finish).

P

These are the set of problems which can be easily solved. If multiple answers exist, then all those answers can be easily found.

NP

These are the set of problems, for which a tentative answer can be easily verified. Some of these problems can even be easily solved. Others are tough to solve but either way, given a tentative solution, that can be easily verified.

For those which can be easily solved, fall under the P class. Hence P <= NP. The equal sign is something scientists are still working on.

These problems can be solved easily on a non-deterministic Turing Machine. Unfortunately, such a machine does not exist. The real deterministic Turin Machines (our laptops) cant guarantee how much time it would take to solve such a problem. it might even hang.

REC

These are the set of strings (a language) which belong to one family of strings. The family is called The Grammar. Given a Grammar and a string, if we can easily tell whether the string is member of the family, then the family is REC family.

RE

These are an even broader set of strings, which belong to an even broader family. Some of the members of this family are REC, but some are not. That is, given a Grammar and a string, we may or may not easily tell whether the string is a member or not. If we are able, then the family is REC, if we are not, then it is RE family.

Membership in RE family cannot be easily verified but, given such a Grammar, all the members can be easily listed-out. Hence the name- recursively enumerable.

  Now, Question: both (P/NP) and (REC/RE) seem similar. I know they are not the same. One is problem, another is language. But is there any connection between the two?

Also, From what I understand, is there anything wrong in my understanding? I mean certainly there must be things missing. But for the part which is not-missing, is there anything wrong?


texts: Context free grammar for language with even number of $0$'s and $1$'s

texts:
I want to create a Context-Free grammar that generates the language

$$ L = \{ w \in \{0, 1\}^* |\ \text{number of $0$'s is even, and number of $1$'s is also even} \}. $$

I came up with

$$
S \rightarrow 0S0S\ |\ 1S1S\ |\ ABABS\ |\ BABAS\ |\ \epsilon \\
A \rightarrow 0A0A\ |\ 1A1A\ |\ 0\\
B \rightarrow 0B0B\ |\ 1B1B\ |\ 1\\
$$

Looks like it does the job, but how can I be sure that it does indeed generate L.

Any help would be appreciated.


texts: Reachability matrix in time $O(|V| \cdot |E|)$

texts:
Suppose that we are given a directed graph and we want to find out if a vertex $j$ is reachable from another vertex $i$ for all vertex pairs $(i, j)$ in the given graph.
Reachable mean that there is a path from vertex $i$ to $j$.
The reachability matrix is called transitive closure of a graph.

I want to write an algorithm that rus in time $O(|V| \cdot |E|)$ and calculates the transitive closure of a directed graph $G=(V,E)$.

I have tried the following:

 Transitive_Closure(G)
         for v=1 to |V|
               for u=1 to |V|
                        T(v,u)=0
         for v=1 to |V|
                for each u in Adj[v]
                        T(v,u)=1
                        for each w in Adj[u]
                                T(v,w)=1

But isn't the time complexity $O(|V| \cdot |E|^2)$? Or am I wrong?

This algorithm definitely finds the transition matrix, but it's even in $\Omega(|V|^3)$:

    Transitive_Closure(G)
      for i = 1 to |V|
          for j = 1 to |V|
              T[i,j]=A[i,j] // A is the adjacency matrix of G
      for k = 1 to |V|
          for i = 1 to |V|
              for j = 1 to |V|
                  T[i,j]=T[i,j] OR (T[i,k] AND T[k,j])

EDIT: Is the following algorithm right?

Transitive_Closure(G)
1.  for each vertex u in G.V
2.       for each vertex v in G.V
3.            T[u,v]=0
4.   for each vertex u in G.V
5.        BFS(G,u)
6.   return T

BFS(G,s)
1.  for each vertex u in G.V-{s}
2.       color[u]=WHITE
3.       d[u]=inf
4.       pi[u]=NIL
5.  color[s]=GRAY
6.  d[s]=0
7.  pi[s]=NIL
8.  Q=empty set
7.  ENQUEUE(Q,s)
8.  while Q!= empty set
9.          u=DEQUEUE(Q)
10.        for each v in G.Adj[u]
11.             if color[v]==WHITE
12.                color[v]=GRAY
13.                d[v]=d[u]+1
14.                pi[v]=u
17.                ENQUEUE(Q,v)
18.        color[u]=BLACK
19.        T[s,u]=1


texts: Shuffling a file on disk using $O(\log n)$ memory

texts:
How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place?

If the file had size $2^m$, then we can first split the file into 2-byte chunks, shuffle them individually, then shuffle each set of neighboring 2 chunks and merge, doing this recursively. Merging can be done using constant memory by reading the start of a chunk and swapping them with another.

But if the file size is not $2^m$ then the above doesn't really work, as for a 3-byte file the last byte cannot be in the middle position. (the chunks here are [1, 2] and [3]).

[EDIT] This doesn't generate all permutations as Yuval Filmus points out.

[EDIT 2] The paper "Random permutations on distributed, external and hierarchical memory" seems like a close match. Other refs/ideas welcome.


texts: compressing a set of binary strings with fixed length

texts:
I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all matching the following regular expression: [01]{n}).

Insertion and lookup ("Is element x in the S?") should maximally take polynomial time to |S|.

The space complexity should be logarithmic to |S| for large sets. In other words, the space should not be exponential to n if for example 2^n / 2 random and unique strings are inserted, but polynomial to n.

Is such a thing known to exist?


texts: Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable

texts:
Past year paper question:

Let $M_i$ denote the Turing machine with code $i$ using the alphabet $\Sigma=\{a,b\}$.

Show that the following language is not recursively enumerable:

$L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$

I tried to show that we can reduce $L_e$, the set of Turing machines that accept no strings, to $L$. To do this, I need to find a transformation $f$ such that is $\mathrm{Lang}(M)$ is empty, then the machine represented by $f(M)$ has some string $x$ but not $xx$, and if $\mathrm{Lang}(M)$ is not empty, then the machine represented by $f(M)$ contains $xx$ if it contains $x$.

But I am not sure how to find such a transformation. Can someone show a transformation to solve this problem?


texts:
Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free.

I have a grammar like this but there are some strings that are not be able to be generated

$$\begin{align}
S &\to aSbb \;|\; C \\
C &\to cC \;|\; \epsilon
\end{align}$$

One example is the string $abbc$ cannot be generated.


texts: Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?

texts:
$$\log n+\log \frac{n}{2}+\log\frac{n}{4}+\log\frac{n}{8}+\cdots+\log\frac{n}{n}=\Theta (\log^2n).$$
The sum of logarithms is the logarithm of the product $n\cdot\frac{n}{2}\cdot\frac{n}{4}\cdot\frac{n}{8}\cdots\frac{n}{n}$. This equals $n^{\log n}$ divided by what? If the product would just be $n^{\log n}$, then this would make perfect sende since $ \log(n^{\log n})=\log(n)\cdot\log(n)=\log^2 n$. But the divisor equals $\frac{1}{2}\cdot\frac{1}{4}\cdot\frac{1}{8}\cdot\frac{1}{16}\cdots\frac{1}{n}$ so I don't get it.


texts:
If I have a DFA with only one state that is not an accept state, it accepts only the empty set.

I get confused when if the DFA of one state is an accept state. Does this mean it accepts everything? Or could you have it only accept "a" and not "b". I guess I don't understand if not having an arrow out implies there is a second "invisible state"

In other words, for a DFA of one state, are there 2 or 4 distinct machines?

Thanks!


texts: Find original array from array with pairs of adjacent elements

texts:
Given an array composed of pairs, like this:
[[3,5],[1,5],[3,2],[1,4]]
Each element in the array (call it pair) means that pair[0] and pair[1] are adjacent in the original array. Note, they can come in either order. For instance, for the sample array above, the original array would be:
4,1,5,3,2 (or the reversed version of this)
How can I do this quickly? I tried doing this as follows, which works, but it's too slow:
Create a hashmap that maps adjacent elements. Map = {3: [5,2], 1: [5,4], 5: [1,3], 4: [1], 2:[3]}. My algorithm would then start with one of the keys that only has a corresponding value length of 1 (in this case either 4 or 2), and then add to an output array, and go through the hashmap. I.e. First I would add 4 to my output, and then go from key of 4 (with a corresponding value of 1), to the key of 1, with corresponding values of 5 and 4. I'd ignore 4 (since it's already in output), and add 5, then go to the key of 5, and so on and so forth. This is too slow! Is there a better algorithm?


texts:
I need to tell whether $\quad\exists a \quad T(n) = \omega(n^2)$

$T(n) = T(\frac{n}{2}) + aT(\frac{n}{4}) + n^2\\\\
\forall n<10 \quad T(n) = 1$
And if there is such $a$ I need to find the minimum one.

I have tried to use recurrence tree but im unable to generalize $T(n)$ to a finite sum and im quite out of ideas on how to attack this problem.


texts: $\{a^n b^n\} \cap \{a^*b^*\}$ regular or not?

texts:
I have been asked a very interesting question in preparation for my exam coming up. The question is as follows:

Is $L=\{a^n b^n : n \geq 0\} \cap \{a^*b^*\}$ regular or not?

Assume $L$ is regular. Then, $L^c$ should be regular as well. Thus, $L^c = \{a^n b^n : n \lt 0\} = \{\}$, so if I compliment the compliment, I should get $L = U$ (the universal set). So, then $L=\{a^n b^n : n \geq 0\} \cap \{a^*b^*\} \neq U$, because $L$ does not contain words of the form $baba$, or $baaaababa$, etc. Therefore the language is not regular.

Is this an acceptable answer for the upcoming exam? Does this persuade anyone?


texts: Locality-sensitive hashing random projection

texts:
I'm trying to understand how the LSH works for Cosine Similarity metric. For instance, let's say you have $\vec{v} \in \mathbb{R}^d$ and the random vectors $\vec{r_{i}} \sim \mathcal{N}(0, 1)^d$ that will be used for the random projection. So, in LSH for Cosine Similarity, the define the hash function $h_i(\vec{v}) = 1$ only if $\vec{r_i} \cdot \vec{v} \geq 0$ and $h_i(\vec{v}) = 0$ only if $\vec{r_i} \cdot \vec{v} < 0$. There are a lot of places that mention that this dot product of $\vec{v}$ and $\vec{r_i}$ means which side of the line (assuming a 2D dimension for instance) the point in question $\vec{v}$ is (negative for one side and positive for the other side), just like in the image below:

However, to my understanding, what will give which side of the line where the point $\vec{v}$ is, is the dot product of the norm of the $\vec{r_i}$ (let's say that the norm is $\vec{n}$) and the vector $\vec{v}$, so the correct wouldn't be the equation $\vec{n_i} \cdot \vec{v}$ instead of $\vec{r_i} \cdot \vec{v}$ ?


texts: Proof that Turing machines and computers have same power

texts:
How do we prove that any logical circuit can be simulated by a Turing machine?

For example, we take a logical circuit $L$ that is made of gates and, or, and not. This circuit determines a problem, for example, whether the input is an even number. How can we prove that if a problem is decided  by a logical circuit, there is a Turing machine that can decide the problem?

In other words, how do we prove that a CPU is equal in power to a Turing machine? We should not forget that a Turing machine has infinitely many cells.


texts: Shortest path between 2 vertices using at most K edges using Bellman-Ford

texts:
I'm a bit confused about stopping at Kth iteration on the Bellman-Ford algorithm to find the shortest path of at most length k from s to t.
Let me show you a graph and explain you what I understand:

At first iteration, I will have:

Shortest path to get to A is S->A (cost 1)
Shortest path to get to B is S->B (cost 4)
Shortest path to get to T is still unknown

At second iteration I will have:

Shortest path to get to A is S->A (cost 1)
Shortest path to get to B is A->B (cost 2(A->B) + cost 1(S->A) = 3) updated!
Shortest path to get to T is B->T

But now going to B takes 2 edges instead of 1, so going to T is 3 edges away now: S->A->B->T, and this has happened in 2 iterations.

What am I understanding wrong?


texts: Range majority queries - most freqent element in range

texts:
Given N numbers and M range queries (starting and ending points), I need to
compute majority (most frequent element, if it exists) in these ranges.

I'm looking for an algorithm that would answer queries in logarithmic or even constant time.


texts:
I've been finding myself a bit confused with the direction of reductions used to show that certain languages are not recursive. For example, let us say we want to determine if the Halting Problem ($HALT_{TM}$)is undecidable. I know we can assume that it is decidable and then try to build a decider for the acceptance problem, which is impossible. But though we are using the Acceptance Problem ($A_{TM}$) to help solve the decidability of the Halting Problem, we have reduced the Acceptance Problem to the Halting Problem, not the other way around, right?

I sometimes get a little bit confused when I encounter questions that ask me to deploy a reduction; I will be asked to reduce language $x$ to $y$, but what that means is that $y$ is a simpler instance of a problem of $x$, right (or at least should be)? I'm assuming it's impossible to reduce a simpler version of a problem to a more complex version of a problem, am I right in believing that?


texts: CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof

texts:
In Cormen et. al., Introduction to Algorithms (3rd ed.), I don't get a line in the proof of Lemma 26.1  which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| =|f|+|f'|$ (this is pp. 717-718).

My confusion: When arguing flow-conservation they use the definition of $f\uparrow f'$ in the first line to say that for each $u\in V\setminus\{s,t\}$

$$ \sum_{v\in V} (f\uparrow f')(u,v) = \sum_{v\in V} (f(u,v)+f'(u,v) - f'(v,u)), $$

where the augmented path is defined as

$$ (f\uparrow f')(u,v) = \begin{cases} f(u,v)+f'(u,v) - f'(v,u) & \text{if $(u,v)\in E$}, \\
0 & \text{otherwise}. \end{cases} $$

Why can they ignore the 'otherwise' clause in the summation? I don't think the first clause evaluates to zero in all such cases. Do they use flow-conservation of $f$ and $f'$ in some way?


texts:
Assume that a language A is reducible to language B. The claim is true?

if A is decidable then B is decidable too.

The correct answer is:

  This claim is wrong. If A is e.g. the empty language (which is clearly decidable) and B is $A_{TM}$, then surely ∅ is reducible to $A_{TM}$, but $A_{TM}$ is undecidable. The claim is true the other way round: If B is decidable then A is decidable too.

I have problem to understand two points:

A is e.g. the empty language (which is clearly decidable)

Why empty language is ("clearly") decidable and $L_∅$ is not?, where,  $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$

**A is reducible to $A_{TM}$ **

I have difficulties to image a reduction from $∅$ to $A_{TM}$, where $A_{TM} = \{<M,w> | \ M \ is \ a \ TM \ and \ M \ accepts \ w\}$


texts: Proof that a function is not computable by a Turing Machine

texts:
I am going through a problem that I am asked to prove if there is a Turing machine that can compute f for every input a.
The function is the following :
$$f(a) = \begin {cases} 1 & if \ there \ is\  some\ x \ such\ that\ M_a(x)\ halts\ with \ output \ 1 \\
0 & otherwise \end{cases}$$
I am struggling with the proof of this statement. I tried using a proof by contradiction and assumed there is such a Turing machine. I am also assuming I need somehow to use a universal Turing machine that takes $a$ as input but I am not sure how to proceed.
Can someone explain me if I am on the right track or any methodology I can use to prove or disprove this statement?


texts: Assuming NP $\neq$ P, are there NPI languages only P languages reduce to?

texts:
let $L_c$ be the class of all languages that have a polynomial reduction to some language L, for example if $L=SAT$ then $SAT_c=NP$.

Assuming know that $NP\neq P$ we know that there exist languages that are not NP-hard and not in P, i.e. those in NPI. My question is there a language L in NPI such that $L_c \setminus \{L\}=P$?


texts: What is the implication of the sentence: "if any NP complete problem is p time solvable, then all problems in NP are p time solvable"

texts:
I find this quote here on page 13

  Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p time solvable?

This is very unbelievable to me since NP complete problems are so different in nature and comes in a variety of form such as longest path, dominating vertex, halting problem, knapsack problem. Can someone show me how this statement is true?


texts: Complexity of finding a spanning tree that minimizes the maximum interference

texts:
Given $n$ nodes in the plane, connect the nodes by a spanning tree.
For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning tree. The interference of a node $v$ is then deﬁned as the number of such disks that include the node $v$.

The problem I'm interested is to find a spanning tree that minimizes the maximum interference.

What is known about the problem in terms of computational complexity? Is it NP-hard? Can it be solved efficiently? What is its inapproximability threshold?

Apparently this problem is still not understood well. I do not know the complexity of the problem (solvable optimally in polynomial time, or NP-complete), and as far as I know it is unknown whether efficient approximation algorithms exist.


texts:
I am learning about artificial neural networks and I've decided to go with perceptrons. I already made a sample program that can learn based on the learning data, but when I tried to make it recognize the color green it stopped working. The learning data is based off of RGB values.

So at first the perceptron was learning fine. Here are the 17 initial training examples:
$\{\langle(0, 250, 154), 1\rangle, \langle(0, 238, 118), 1\rangle, \langle(0, 205, 102), 1\rangle, \langle(0, 139, 69), 1\rangle, \langle(60, 179, 113), 1\rangle, \langle(84, 255, 159), 1\rangle, \langle(78, 238, 148), 1\rangle, \langle(67, 205, 128), 1\rangle, \langle(46, 139, 87), 1\rangle, \langle(0, 201, 87), 1\rangle, \langle(0, 205, 205), 0\rangle, \langle(47, 79, 79), 0\rangle, \langle(224, 255, 255), 0\rangle, \langle(0, 191, 255), 0\rangle, \langle(255, 165, 0), 0\rangle, \langle(105, 139, 34), 1\rangle, \langle(139, 139, 122), 0\rangle\},$

where $1$'s stand for green and $0$'s stand for not green. For the above training examples it worked fine and the solution that was computed for the weights was $(-18, 28.3, -34.3)$.

However, when I added $\langle (205,205,0), 0\rangle$ to the training examples, the program ran forever.

My question is, if i am teaching the perceptron correctly and it just can't find an answer or if i should try some other method? (By the way, I am not using back propagation and am also wondering if using back propagation would solve this problem.)


texts: Number of permutation cycles in matrix transposition

texts:
I am trying to solve a problem on Sphere Online Judge (SPOJ) link to which is: http://www.spoj.com/problems/TRANSP/

The matrix can be thought of as a permutation and its transposition as another permutation. I need to convert the first one into another. I have found a relation between the Cycles in the Permutation and the number of swaps required as:

Minimum Swaps = Total Elements in Permutation - Number of Cycles

However, I don't know how to calculate the matrix of size $2^a 2^b$ where $a+b \leq 500000$.


texts: What is a good beginner computer science book for a young adult, say, a 15 year old? I want to get started in CS, but have no idea where to start. I have limited experience in programming.


texts: lambda calculus beta reductions: ((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))

texts:
My question is in continuation to lambda calculus reduction: (((lambda f (lambda x (f x))) (lambda y (* y y))) 12)

given the input:

((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))

I want to understand the order of reductions that I should take. in the above mentioned question it was suggested to me to apply left most reduction.

I want to check if this is a valid 1st step towards leftmost reduction:

Or should f= λy.λg.g(*y y) instead ?
What it might boil down to is: am I allowed to solve the sub-trees up before applying the solution from the right subtree on the left sub-tree?


texts:
It holds that if SAT could be solved in poly time, one can also find in poly time the assignment that satisfies most clauses of the original formula.
Does anyone have any idea how to show this?
Let's assume we have algorithm A to decide in poly time if a given formula could be satisfied or not. How one can use this to find in poly time the assignment that satisfies most clauses.
I know that using this assumption leads to also being able to find satisfying assignment in poly time (if the formula is in SAT), but if the formula is not in SAT how can we find what is the sub-formula with maximum clauses that belongs to SAT without iterating over the powerset of the clauses which will lead to exp time algorithm?


texts: Has GPT-3 put web designers out of work yet?

texts:
https://prototypr.io/post/gpt-3-design-hype/
Has GPT-3 had any effect on the how many humans are hired to do web design yet?


texts: How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input?

texts:
I currently have a problem with the following question:

Let $L = \{ \langle M \rangle \mid \exists w: \text{$M$ halts for $w$ in at most $|w|^3$ steps} \}$.
Construct an NTM (non-deterministic Turing machine) that decides $L$.

My idea was to simulate every possible input of length $\le|w|^3$ on a given TM $M$ by using a separate band in my NTM for every single input word. If there is one band where $M$ halts, then the NTM accepts.

Is this the right way to go about it? My problem is that I don't see why I would need a NTM to decide $L$. A standard TM would be able to do the same thing.


texts: Decidability of determining whether a context-free grammar generates all strings in 1*

texts:
How could I prove that the following language is decidable?

$\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S.
It's the problem 4.15 of the third edition of the "Introduction to the Theory of Computation" by Michael Sipser.


texts: What is the time/space complexity of $n!$? Can $n!$ has polynomial space complexity?

texts:
Given an integer $n$, calculate $n!=n\times(n-1)\times(n-2)\dotsc 3\times2\times1$.

What is the best time and space complexity of calculating $n!$?

P.S. I do not have any idea about this topic. I was using MATLAB and I needed to compute $200!$ but it said "Out of memory"!! That's why I am asking.


texts: Understanding the definition of a language

texts:
Could you please help me understand the following Language
$L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$
what does $a_i = a_{i+1}$ mean? Could you please give me an example of word in $L$?


texts: Shortest walk through a given subset of edges

texts:
Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once?

I'd like to know if there is a general approach to this problem. However, additional constraint may be added for my specific scenario.

The graph $G_0 = (V, E)$ initially has only edges that must be crossed, but it's disconnected:

Each connected component is formed by 2 vertices and 1 edge.
Each vertex $v$ is the endpoint of exactly one edge $\in E$. This means that any two edges $e_i, e_j \in E$ don't have a vertex $v$ in common.
The cost of each edge $e \in E$ is $0$.
The number of edges in $E$ is at most 1000, usually between 10 and 100.

Then other edges $f \in F$ are added with to link any two vertices (except the one already linked by $e$), so $G = (V, \{E,F\})$.

The cost of each edge $f \in F$ is $> 0$

Related questions

I found a few related questions, but they doesn't seem to help:

Shortest path from that passes through a set of edges once: edges $e \in E$ must be visited exactly once, not at most once.
Shortest directed path connecting given subset of vertices, Minimum path between two vertices passing through a given set exactly once, Find the shortest path in a graph which visits certain nodes : the constraint is on edges, not on the vertices.

Not working solutions

I tried a few approaches so far, but I'm unable to make them work properly. E.g.:

Convert $G$ to its line graph $L$. I can't figure out how to assign a proper weight to edges in $L$
If I can find a proper way to construct $L$, adding a dummy vertex $s$ on $L$ allows to solve this with TSP. Then I'll know the order of the edges $e$, but not the direction.
I really don't want to use brute-force. It may become impractical very soon.

Almost-Working solutions for the specific case

Since by construction every walk will be of the form: $e_1, f_1, e_2, ... f_n, e_n$:

Compute the weight of the path for each permutation of edges in $E$. The edge $f$ between two edges $e$ will be the mininmum weight one. Pick up the minimum weight path. This solution is brute-force, so not really practical for a large number of edges in E.
Start from an edge $e$. Follow the min-cost edge $f$ starting from the end-vertex in $e$. Repeat until all edges in $E$ are reached. This solution is not guaranteed to find the shortest path.


texts: What does $\sigma(t_0, \ldots, t_{n-1}) \in \mathcal{T}_{\Sigma}^{0}$ in this paper mean?

texts:
The paper is "Mappings and Grammars on Trees" by William C. Rounds. There was a definition of ranked alphabet in page 3 and I can't understand the second part of the definition.

Definition. A ranked alphabet is a pair $(\Sigma, r)$ where $\Sigma$ is finite, and $r: \Sigma \rightarrow \mathbb{N}$.
We set $\Sigma_n = r^{-1}\{n\}$
Let $(\Sigma, r)$ be a ranked alphabet. The set $\mathcal{T}_{\Sigma}^{0}$ (the constant $\Sigma$-terms) is the smallest set of strings such that:
$\ldots$
(b) if $t_0, \ldots, t_{n-1} \in T_{\Sigma}^{0}$, and $\sigma \in \Sigma_{n}$, then $\sigma(t_0, \ldots, t_{n-1}) \in \mathcal{T}_{\Sigma}^{0}$

The $\sigma$ should be set of the alphabet which is ranked $n$, how can a set of alphabet become a function?
Thank you.


texts: What is the expected number of nodes at depth d of a tree after i random insertions

texts:
Suppose one wanted to build a tree at random.  Let the first insertion at step $i = 1$ be the root node.  From here, nodes are inserted into the tree at random one at a time.  How would one go about calculating the expected number of nodes $E(d)$ at depth $d$ after $i$ insertions?

For example, At $i = 1$, it's just the root node, so $E(0) = 1$ and all other depths will have zero nodes.  At $i = 2$, $E(0) = 1$ and $E(1) = 1$ as the inserted node has to be at depth 1 from the root.  At $i = 3$, the next node may either be attached to the root node or the existing node at depth one, so the tree may either look like:

    *
   / \
  *   *

Or:

     *
    /
   *
  /
 *

Depending on what happend at $i = 3$, at $i = 4$ there's either a $2/3$ chance of the new node attaching at depth 2 and $1/3$ attaching at depth 1, or an even $1/3$ probability of the new node attaching at the root, the node at depth 1 or the node at depth 2.  Keeping random insertion in mind (not a binary or balanced tree in any way), how would one go about calculating the expected number of nodes at depth $d$ after $i$ insertions?


texts: Name of technique of counting pixels above geographic center line

texts:
I heard about a technique today which is sometimes used in the classification of 2D images of handwritten glyphs. It goes like this:

Find the highest activated pixel of the image, the lowest activated pixel of the image, and average their heights. This creates a horizon at the "geographic" center of the image. You then count the pixels above and below this line, and return their ratio. Here is a quick sketch I put together:

Does anyone know the name of this technique, and who came up with it?


texts: How to solve this asymptotic complexity problem?

texts:
The increasing order of following functions in terms of asymptotic complexity is:

(A) f1(n) < f4(n) < f2(n) < f3(n)

(B) f1(n) < f2(n) < f3(n) < f4(n)

(C) f2(n) < f1(n) < f4(n) < f3(n)

(D) f1(n) < f2(n) < f4(n) < f3(n)

I saw this question on GeeksQuiz but I am unable to understand its answer. The correct answer is D.

I think that f(2) will have the highest complexity among all because for a given number it will give the maximum output.

Please help and explain how is it solved?


texts: Why no DPDA can accept Palindrome? (according to this proof)

texts:
This proof is from the book "Introduction to Languages and the Theory of Computation" by John C. Martin.

My question is from the pink part at the second page:

  It follows in particular that no sequence of moves can cause M to empty its stack.

and further, it talks about  $y_x$ that is my second question. I can't understand what $y_x$ is.

I'll appreciate it if someone please describe me the whole proof.


texts: What is the difference between Boolean Algebra and Boolean Lattice? I have already searched on Google but could not find a reasonable answer?


texts:
I was researching dynamic programming and read the following:

  Often when using a more naive method, many of the subproblems are
  generated and solved many times.

What is a naive method?


texts: Protecting data unequally using Error Correction Codes

texts:
Say I'd like to transmit a 100-bit packet which has a field containing a continuous value. I'd like to protect this value with an error correction code but an error in the MSB of this value is much more catastrophic than an error in the LSB, so how do I have to design the code so that it will be optimal by means of protection (more redundant bits for the important parts)?

For example, let's assume my continuous field is Temperature. My problem is that the temperature is represented by X bits but they are not equally important. If the temperature is 23.452298 degrees than I can't risk an error in the integer part (23) but if I'll get an error in the fractional part I'll be able to live with it (though I prefer protecting it too, with less "protection" bits).?


texts: Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing)

texts:
Before the Question:
Greene, Parnas and Yao presented a scheme which, for binary data chosen uniformily a random,
 retrieves all points within Hamming distance r of a given point in time $O(d n^{r/d})$ using $O(d n^{1+r/d})$.
The scheme is based on Turán's graph and the complete description can be found
here.

I was reading this paper
Fast Exact Search in Hamming Space with Multi-Index Hashing.
and realised there is nothing written WHEN r=0, that is, how to find an EXACT MATCH using neighbour search.

The question is concerned with EXACT MATCH (r=0) of an exact k-NN search in Hamming Space using Multi-index Hashing.
I'm not interested in the first nearest element.
I would like a data structure that answer the existence of an element inside a set.
Is it possible to make such a data structure?

What is the complexity of the Yao's algorithm or Norouzi's algorithm when r=0?
I think it is not only make r=0 in the above complexities to get the answer...


texts: Question about (in)dependent Haar-features and (Ada)boosting

texts:
I have an old exam question for my pattern recognition course which is stated as follows:

  Consider a pool of Haar features, determine if these Haar features are independent or not. Is it a problem in boosting algorithms (e.g. AdaBoost)? Why (not)?

I have a really hard time figuring out an appropriate response to this question. One could argue that having dependent features is not desirable because then one of two classifiers does not really bring any new information or could possibly perform the same classification as the first one. The more independent features, the more independent, unique (weak) classifiers you have, but I don't know if this even makes sense.


texts: Software Engineering - Waterfall model efficiency

texts:
I study computer science and we have subject named Software Engineering, we learn that each software should pass through a long process starting from requirement engineering and ending with Evoluation (Change Requests, Bug reports, Quality management) all this is based on hierarchy its head is the Project Manager and creating an endless levels. Additionaly many works should be done, filling Forms such assignment forms, creating contracts ... etc

Isn't Class Diagrams enough ? why do we need all these Diagrams (Component, Sequence, Class, Control, Deployment, Interaction, Distribution, Implementation Diagrams ... and more)
Do all Software Engineering Companies work this way ?
Doesn't this increase cost of a Software as we need to employ many people (Managers, Requierment Engineers, System and Software Analysts, Senior and Junior Developers, Testers, ... etc) ?
Doesn't this increase the Time, in which the Software is developed in ? do clients wait ? do they not get disturbed ?
Isn't kind of bureaucracy ?

I don't try to give a personal opinion here,  I really like this subject but i just want to understand and know if this is really economically efficient ?.


texts: Batch sizing for convolution neural networks -- powers of 2 or powers of primes?

texts:
The conventional wisdom for convolution neural networks (CNNs) is to make the batch size a power of 2 because of hardware utilization/optimizations done in the convolution layers.

A similar logic applies to the Fast Fourier Transform (FFT). However, the FFT is actually best used when it is a size of a power of primes (e.g. $2^M3^N5^P$ where $M,N,P$ are positive integers.)  I was wondering if this also applies to CNNs.


texts: Why does the given solution to this problem works? How can it's correctness be proven?

texts:
This is a question asked in Adobe interview:

  Given heights of n towers and a value k. We need to either increase or
  decrease height of every tower by k (only once) where k > 0. The task
  is to minimize the difference between the heights of the longest and
  the shortest tower after modifications, and output this difference.

Link of problem and it's solution: solution and problem

Solution posted at the website(click on the link above):

// C++ program to find the minimum possible
// difference between maximum and minimum
// elements when we have to add/subtract
// every number by k
#include <bits/stdc++.h>
using namespace std;

// Modifies the array by subtracting/adding
// k to every element such that the difference
// between maximum and minimum is minimized
int getMinDiff(int arr[], int n, int k)
{
    if (n == 1)
       return 0;

    // Sort all elements
    sort(arr, arr+n);

    // Initialize result
    int ans = arr[n-1] - arr[0];

    // Handle corner elements
    int small = arr[0] + k;
    int big = arr[n-1] - k;
    if (small > big)
       swap(small, big);

    // Traverse middle elements
    for (int i = 1; i < n-1; i ++)
    {
        int subtract = arr[i] - k;
        int add = arr[i] + k;

        // If both subtraction and addition
        // do not change diff
        if (subtract >= small || add <= big)
            continue;

        // Either subtraction causes a smaller
        // number or addition causes a greater
        // number. Update small or big using
        // greedy approach (If big - subtract
        // causes smaller diff, update small
        // Else update big)
        if (big - subtract <= add - small)
            small = subtract;
        else
            big = add;
    }

    return  min(ans, big - small);
}

// Driver function to test the above function
int main()
{
    int arr[] = {4, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 10;
    cout << "\nMaximum difference is "
        << getMinDiff(arr, n, k);
    return 0;
}

After trying for around an hour. This is the solution I came up with:

  Sort the array in non decreasing order.
  Initialise two pointers, one at the starting(0th index) and other at the end(n-1 th index) of the array. If the difference between the
  values at the two pointers is greater than or equal to twice of k,
  then increment the value at the left pointer by k and decrement the
  value at the left pointer by k. Get the difference between the new
  values and update the variable that stores the minimum answer.
  Increment left pointer and decrement right pointer.
  Repeat steps 2 and 3 until left and right pointers converge to the same address.

But the algorithm I wrote only passed sample test cases. When I looked at the editorial, I could not understand why the solution works the way it does. Can anyone break it down step by step.

Also I read in comments it can be solved in O(N). Would be thankful if someone can put insight if that's possible and how. Also where can I practice similar questions?


texts: Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$

texts:
The proof is in the image below, taken from "Quantum Computing Since Democritus":

Here's what I don't totally get: my understanding of random algorithms is that randomization is not done over the input space; the inputs are still worst case. So that when a random algorithm has some error, what I interpret that to mean is that given any input string to the algorithm, there is at most such-and-such probability of outputting a wrong answer.
If I take the same string $s$ and run it through the random algorithm with error rate $e<1$ an $n$ amount of times, I should expect $ne$ wrong answers.
I haven't been able to reconcile the above with the technique used in the linked proof; in particular, the jump from $2^{-n^2}$ being the error rate of the BPP algorithm to saying that a $2^{-n^2}$ fraction of random strings cause us to err. If someone could explain this proof a little more verbosely I think I'd find that very helpful.


texts: Support of a codeword in a binary linear code proof

texts:
Let $C$ be the binary linear code with the following generator matrix

$G= \begin{bmatrix}
    1 & 1 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 & 1 & 0 & 0  \\
    0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix}$

The support of a codeword is the set of coordinate positions in which the code word has nonzero entries. Let $w$ $\in C$ be a code word of weight $4$. Show that there is no code word of weight $3$ in $C$ whose support is a subset of the support of $w$.

I think I have worked out that the codewords of weight $4$ in $C$ are: $\{(1001011),(0010111),(0111001),(0101110),(1100101),(1110010),(1011100)\}$ so does this mean that the support is $\{(1,4,6,7),(3,5,6,7),(2,3,4,7)$ and so on..$\}$?
Then the codewords of weight $3$ are $\{(1101000),(0110100),(0011010),(0001101),(1000110),(1010001),(010001)\}$ ? with support of  $\{(1,2,4),(2,3,5),(3,4,5)$ and so on..$\}$?

I'm not sure if this is right so far? But this is as far as I can get and do not know what to do next to show that there is no code word of weight $3$ in $C$ whose support is a subset of the support of $w$.


texts:
I need a good data structure to store the following data:

The data are key,value pairs. However, more than one value maps to one key and the key is an n-tuple with n constant. Here's an example:

        key        | values
 (k1, k2, k3, k4)  | v1, v2, v3
 (k5, k6, k7, k8)  | v4, v5

A value is an object. The following characteristics are preferred in the data structure:

The key should be easily searchable and new values should be easily entered. Given a new key value pair, the program should be able to easily search the data structure to see if the key already exists, and if so, the new value should be added to the values list. If not, a new entry in the data structure should be created.

one value should be easily deleted

the entire data structure should be easily deleted

Any suggestions for such data structures are appreciated!


texts: Where do these DRAM row/column calculations come from?

texts:
Let r be the number of rows in a DRAM array, and c be the number of columns.

Apparently, DRAM with organization 16x1 requires least pins when r = c = 4 because fewer address bits are required to represent them, and so does DRAM with organization 16x4. Why are these the same? Doesn't the latter have 4 columns instead of 1?


texts: Regex to match number ranges less than a certain number

texts:
I'm trying to write some code to match numbers below certain bounds. I would much appreciate nay help somebody could give, I'm pretty lost with this one...

NB. I've checked the forums and can find similar questions to this but they are not really helping. Regex is fairly tricky!

$0      <     x     < 500$
$500    \leq    x     < 1000$
$1000   \leq  x     < 1499$
$1500   \leq    x     < 1999$
$2000   \leq    x     < 2500$
$2500   \leq    x     < 5000$
$ x  \ge 5000$

Please not that $~x~$ is a real number, and therefore could be a decimal. (e.g.  $100.4924$).

The furthest I have got is the below. The idea was to match numbers for each bound, and then write a separate criterion to exclude numbers below another certain bound.

I can use two regex matches in the program I'm using. E.g for a regex match for the bound:  $~500 \leq x < 1000~$, I could use a match to be "less than $1000$" and then a not a regex match for the bound:  "Less than $500$"

Less than $500$

$[1-4]?[0-9]?[0-9]?([0-9])?$

Less than $1000$

$[1-9]?[0-9]?[0-9]?([0-9])?$

Less than $1500$

$1?[1-4]?[0-9]?[0-9]?([0-9])?$

Less than $2500$

$[1-2]?[0-4]?[0-9]?[0-9]?([0-9])?$

Less than $5000$

$[1-5]?[0-9]?[0-9]?[0-9]?( [0-9] )?$

The matches are fairly close, but are also returning matches for multiple leading digits - rather than just the $0$ or $1$ that the ?. is supposed to specify :/


texts: How to efficiently find a minimum spanning tree?

texts:
I found this question from CSLR that I'm trying to figure out before my final.

  You are given a weighted, connected, undirected graph G = (V, E) and
  one of its minimum spanning trees T ⊆ E. Now consider the following
  two scenarios where we modify the graph and want to get an updated MST
  efficiently.

  (a) A new edge (u, v) with weight $w_{u,v}$ (u, v ∈ V ) is added to G,
  resulting in a new graph G' = (V, E ∪ {(u, v)}). How do you
  efficiently find a minimum spanning tree T' of G'? The algorithm’s worst-case runtime must be in O(|V|).

  (b) An edge (u, v) ∈ E is removed from G, resulting in a new graph G' =
  (V, E − (u, v)). Assume that G' is still connected. How do you
  efficiently find a minimum spanning tree T' of G'? The algorithm must run as fast as possible.

I know that we're supposed to find a set with the minimum edge weight. For (a), the restriction is set that the runtime should be O(|V|), which implies that we should use an algorithm that goes through the vertices. What I don't get is how to construct such an algorithm. I know, for example, that BFS/DFS run in O(V + E), and they're two of the best algorithms discounting Dijkstra's. Any advice on how to answer the question above?


texts: Maximum Changes that don't Break the Build

texts:
Let's say I have a set of changes, e.g. replacing foo with bar in a codebase, how do I programmatically discover the largest set of replacements that will not break my tests. let's assume that the call-sites are independent.

I can come up with a binary-search-like algorithm which would be worst case O(n) time. Proposed binary-search-like algorithm:

possible_changes = Set(Range(0, n - 1)) // all callsites
working_changes = Set()

while (possible_changes non empty) {
  for (range in possible_changes) {
    remove the range from possible_changes

    if (range causes failures) {
      if (range size == 1) {
        // forget the range
      } else {
        left, right = split the range
        if (range size == 2) {
          if (left does not cause failure) {
            add left to working_changes
            // forget right
          } else if (right does not cause failure) {
            add right to working changes
          }
        } else {
          add left to possible_changes
          add right to possible_changes
        }
      }
    } else {
      add range to working_changes
    }
  }
}

Is there a faster way, besides above to find all changes that would work?


texts:
Consider these 2 languages:

  $L_{\ge5} = \left \{ \left< M \right> : M \text{ accepts at least 5 strings} \right\} $

  $L_{<5} =  \left \{ \left< M \right> : M \text{ accepts fewer than 5 strings} \right\}$

Are these recursive, R.E., or not R.E. sets (languages)?

I would say that they are not recursive, based on applications of Rice's Theorem.

For the first case $L_{e}= \left \{ \left< M \right> :L(M)= \emptyset \right \} \notin L_{\ge5} $ and $L_{\ge5}$ are not empty. For example, I define $L= \left \{ \left< M \right> : M \text{ accepts all palindromes} \right \}$, which is not finite set and accepts an infinite number of strings.
For the second case I would do the same thing. I have $L_{e}=\left\{ \left< M \right>: L(M)= \emptyset \right\} \in L_{<5}$ and $L=\left\{ \left< M \right>:M \text{ accepts all palindromes} \right\} \notin L_{<5} $

So I would say that both are not recursive. Is my reasoning correct?

Now about the R.E. of the languages I don't have an idea of how I can prove it, this should be the beginning (if L is not RE it can't be recursive), how can I check if they are RE or not?

From the definition: "$L$ is RE $\iff$ there exists a TM $M$ that accepts $L$", so I just have to define a TM that accepts each language?


texts: Why is this implementation of the hash function bad?

texts:
I have a task of hashing DNA sequences. Let the DNA be long sequences of four amino acids, which we will denote by the letters $A, T, G$ and $C$.
My hash function $h$ take DNA as an input and return the sum of amino acid numbers by some large simple modulus as a hash, and then add it to a hash table with a public key. Why is this hashing implementation bad?


texts: Probability bounds on size of smaller partition in randomized quicksort

texts:
Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-2a$ the smallest section be greater than $an$.
How we can Calculate this probability?
after 72 hours try i reach to following that means valid area is (1-a)n-an=n(1-2a). by dividing n(1-2a)/ n we get 1-2a.


texts: Is there a standard recently-used algorithm based on time and usage count?

texts:
Everyone is familiar with most recently used files lists in software and in OSs like Windows.

Some programs just sort by time. I've always been fairly annoyed at this. Others like Windows take usage count into consideration. Some move the item halfway to the top each time it is used, which seems to make sense.

Rather than me blindly guessing at what combination of calculations might be nicest for my end users, is there some well-known most helpful standard for end-user recently-used lists?

(My searches turn up information about MRU caching, but I can't tell how applicable any of that is; it's server efficiency facing vs user efficiency facing.)


texts: “Fuzzy” Chinese Remainder Theorem NP-hard?

texts:
I have some "fuzzy" congruences like these:
\begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{0,3\},\\x&\equiv a_3 \mod 7 \text{ with } a_3 \in \{1,2,6\}\\ \end{align}
These example moduli would provide a unique solution for $x \bmod lcm(3,5,7)$, if the $a_i$ were fixed.
Because the $a_i$ are not fixed, these "fuzzy" congruences lead to $2*3*2=12$ possible solutions for $x \bmod lcm(3,5,7)$.

To reduce the number of possible solutions for $x$, I'm also given an additional constraint $x < B$, which provides an upper bound for $x$.

We can assume that all moduli $m_i$ are primes, so $lcm(m_1,m_2,...,m_n) = \prod_i m_i$.
Furthermore each $a_i$ has at most $t$ possible values ($t=3$ in the upper example).

So the general problem is that we are given a constant $t$, primes $m_1,\dots,m_n$, an upper bound $B$, and sets $U_1,\dots,U_m$ (each of size at most $t$), and the goal is to find an integer $x$ such that $x \bmod m_i \in U_i$ for all $i$ and $0 \le x < B$.

Is this problem NP-hard and how can I prove this?

This question is related to another one: "Fuzzy" Chinese Remainder Theorem, but the difference is that here the sets $U_i$ can be arbitrary and need not contain consecutive integers.

My initial approach was to use the k-Vertex-Cover problem for the reduction.
I used the Wikipedia Integer programming NP-hardness proof as a template (https://en.wikipedia.org/wiki/Integer_programming#Proof_of_NP-hardness).

Let $G=(V,E)$ be an undirected graph. Define a linear program as follows:
\begin{align}
\sum_{v \in V} y_v \leq k&  \\ y_v+y_u \geq 1 && \forall uv \in E \\ y_v \geq 0 && \forall v \in V
\end{align}

I tried to define the Vertices as $a_i$.

But I am unable to transform the $y_v+y_u \geq 1 \text{ , } \forall uv \in E$ (set contains at least one vertex of each edge) inequalities into "fuzzy" congruences.


texts: How to find efficiently the minimum modification to avoid close consecutive numbers?

texts:
I have an array of sorted numbers:

arr = [-0.1, 0.0, 0.5, 0.8, 1.2]

I want the difference (dist below) between consecutive numbers for that array to be above or equal a given threshold. For example, if threshold is 0.25:

dist = [0.1, 0.5, 0.3, 0.4] # must be >=0.25 for all elements

arr[0] and arr[1] are too close to each other, so one of them must be modified. In this case the desired array would be:

valid_array = [-0.25, 0.0, 0.5, 0.8, 1.2] # all elements distance >= threshold

In order to obtain valid_array, I want to modify the minimum amount of elements in arr. So I substract 0.15 from arr[0] rather than, say, substract 0.1 from arr[0] and add 0.05 to arr[1]:

[-0.2, 0.05, 0.5, 0.8, 1.2]

Previous array is also valid, but we have modified 2 elements rather than one.
In order to obtain valid_array, I already have a brute force solution which works fine, but it is quite slow for large arrays. My questions are:

What is the time complexity of that brute force solution?

Does a more efficient algorithm even exist?

Edit

First, I need to clarify what I mean by difference, which I define the same way as in here, so out[n] = a[n+1] - a[n].
The fact that all elements in that difference must be above (or equal) threshold implies that valid_array is also sorted.

Second, the number of modifications (which must be minimized) is obtained by comparing elementwise the original arr and valid_array


texts: Converting (math) problems to SAT instances

texts:
What I want to do is turn a math problem I have into a boolean satisfiability problem (SAT) and then solve it using a SAT Solver.  I wonder if someone knows a manual, guide or anything that will help me convert my problem to a SAT instance.

Also, I want to solve this in a better than exponential time. I hope a SAT Solver will help me.


texts: Invariant For Nested Loop in Matrix Multiplication Program

texts:
I'm making a graduate thesis about proving correctness of program for multiplying 2 matrices using Hoare logic. For doing this, I need to generate the invariant for nested loop for this program:

for i = 1:n
    for j = 1:n
        for k = 1:n
            C(i,j) = A(i,k)*B(k,j) + C(i,j);
        end
    end
end

I've tried to find the invariant for inner loop first, but I can't find the true one until now. Is there someone can help me for finding the invariant for above program?


texts: Does $LL(K)$ grammar has one to one correspondence with $DCFL$?

texts:
Does $LL(K)$ grammar has one to one correspondence with $DCFL$ ?

If I am understanding right, then the given statement says that $2$ distinct $LL(k)$ have one to one mapping, i.e they should not generate the same $DCFL$.

Let us say:-

$G1 : S-> aB,B->a$ generates $aa$ and $G2: S->aa$ also generates $aa$.

Here, both the grammars are $LL(1)$, and generate the same language $aa$ implying many to one mapping and not one to one .

Moreover, If we take a $DCFL$, $$a^n\bigcup a^nb^n$$, it has no $LL(k)$ grammar for it and another $DCFL$, say $$a^m b^{m+n}$$, then it also has no $LL(K)$ grammar for it.

Similarly, I think the statement that "Does $LR(K)$ grammar has one to one correspondence with DCFL" is also false.

Am I right in the reasoning of both the above statements ?

If both are false, then what should be the correct interpretation of the above statements ?


texts: Unknown notation "$e^T$" in a machine learning paper

texts:
I'm trying to understand the material in "A Dual Coordinate Descent Method for Large-scale Linear SVM" by Hsieh et. al. (link to paper) There is an equation for the Dual form of an unconstrained optimisation problem,

$$
f(\mathbf{\alpha})=\dfrac{1}{2}\mathbf{\alpha}^T\bar{Q}\alpha-e^T\alpha
$$

I don't understand what the $\mathbf{e}^T$ means, it's not explained in the surronding text, so I assume it's just some common notation. Later in the paper $\mathbf{e}_i$ is defined as $\mathbf{e}_i=[0,\ldots,1,0,\ldots,0]^T$, so maybe it's some sort of selector term? Not sure if this second mention is even related.

Please may someone explain to be what the $\mathbf{e}^T$ bit is doing in this formula? Thank you for your time.


texts: Could PRNGs make use of more internal state?

texts:
In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing):

  Pseudo-random number generators (PRNGs) must have a period since they only have finitely many internal states.

At least for the PRNGs we see in the class, this is certainly a valid argument (assuming a finite target interval). But it begs the question: why do they not use more memory resp. internal state?

Going through this list, it seems to be the case that all PRNGs do indeed use only a few numbers from the target interval (plus some magic constants).

Most use one to $\approx$ 5 of the most recently generated numbers.
Some have parameter that controls how many values to store ("$r$-lag").
A few use rather many numbers (but still constantly many).

The one I can't quite place is Naor-Reingold; I can't tell how it would be used to generate an actual sequence of pseudo-random numbers.

So while the memory usage (i.e. internal state size) of known/used PRNGs depends on the target interval and internal constants, it does not on the amount of (already) generated numbers.

Have there been any attempts to use more memory in order to obtain better generators? If so, why does it not help or not work at all?


texts: I want convert timetable scheduling problems to SAT problems. Suppose there are $t$ time slots and $c$ classes. I will define $t\times c$ variables $x_{ij}$, which is true iff class $j$ takes place in time slot $i$. My problem is: suppose there is a constraint that class $a$ takes place after class $b$. How to encode that efficiently in CNF?


texts: DFS vs. Union Find for computing connected components of a static graph

texts:
According to CLRS,

  When the edges of the graph are static—not changing over time—we can
  compute the connected components faster by using depth-first search.

However, I tried to do some runtime analysis, and in a graph $G(V, E)$ on which we have to answer $Q$ connectivity queries.

DFS would take $O(V+E)$ asymptotic time to calculate the connected components, followed by $O(1)$ to answer each query, which leads to a total running time of $O(V+E+Q)$.

Whereas, an optimised Union Find would take $O(E.α(V))$ time to “add” all the edges, followed by $O(α(V))$ per query, which gives a total running time of $O(α(V).(E+Q))$.

Now, as we, know $α$ can be taken to be a constant factor for all practically conceivable applications, so Union Find works out to be faster,
hence I am confused as to why the authors of CLRS call DFS faster.

Am I making a mistake with my analysis somewhere?


texts: Error correction code without error detection

texts:
Error detection and correction codes require many bits of redundancy for correcting even a modest number of erroneous bits. However, we often have out-of-band methods to determine when and where the errors occured, such as if we observe a voltage spike that exceeds the usual signal levels.

Are there any well-established error correction codes that use less redundancy, but require that the receiver explicitly declares some bits as unknown and corrects only those? In theory, we should be able to correct one erroneous bit for every bit of redundancy.

Are there any such codes which are also able to detect and correct a small number of unknown errors, in addition to the known ones?

Are there any such codes where the receiver augments each bit with some kind of non-binary confidence score, and the code then finds the most likely original sequence?


texts:
I have done an assignment question which asks me to find the average case of pentary search. The one I came up with is:

C(n) = C(n/5) + 14/5

However, I got it wrong and the professor didn't really explain why.

Can you help me?

Thanks!

Edit:

Pentary search is dividing the array into 5 parts and look for a specific key.

In perspective:

1|2|3|4|4

These are the number of comparisons made by the computer from pentary search.

Adding all possible comparisons I get 14 over 5 slots. This is why I have 14/5


texts: How to Prove Undeciability of Overwriting x with y

texts:
Studying for an exam and considering the general set of languages that solve the problem of whether or not some condition is fulfilled while processing a string.

I consider the language L_overwrite which solves the problem of if one arbitrary character overwrites another different one.

I'll call these arbitrary characters x and y. The problem is then: "Does y ever overwrite x?".

To attempt at solving this problem I've tried a reduction from A_tm. I consider altering the input TM by moving all transitions to the q_accept to q_reject; then any time y would be overridden by x move to q_accept. This is what the total function 'f' does. Additionally to handle the case where the input does not encode for a Turing machine M and a valid input string w then the function outputs the empty string.

I'm stuck attempting to prove that where z is a string constructed from the alphabet that: f(z) is an element of Overwrite_tm iff x is an element of A_tm.

Have I shot myself in the foot with my chosen function? If not, how do I move forward?

Thank you for the help.

I've looked at the following two questions:

Determining if a TM decidable or not, with limited information

Turing machine M overwrites a non-blank char by B (Blank)?


texts: Why do we pop the dollar symbol when it's already present in the stack in PDA?

texts:
Could anyone tell the reason for popping the top of stack(dollar symbol) as said in this lecture(p.54) when there's already dollar symbol in the stack.

I would like to know if we could replace the transition given here(p.54) of the form

A,$ $\to$ 0$

with

A,$\epsilon \to$ 0.


texts:
Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be computed only using circuits of size $\Omega(2^n/n)$, we use a counting argument: there are at most $O(2^{k \log k})$ circuits of size $k$, and $2^{2^n}$ such functions.
Suppose that I am interested in counting circuits of size $k$ that compute different functions. The "simple" counting argument won't work since it may be possible that two "syntactically" different circuits actually compute the same function.
In other words, I want to bound the size of the set: $$F =  \{ f: \{0,1\}^n \rightarrow \{0,1\} | f \text{ can be computed using a circuit of size }k \} $$
Then $|F| < $ the number of circuits of size $k$ (since any circuit computes one function), but how can I bound $|F|$ from below? (i.e. $ x <|F|$)


texts: Does there exist a finite automaton for the given language?

texts:
The question is simple and given as, alphabet $A$ is $\{a, b\}$, and language $L$ over $A$:

$L = \{w: w \in \{a, b\}^*, n(a) - n(b) = 1 \mod 3\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of $b$.

My answer is that it's not a regular language because the modular expression can be simplified as. $n(a) =n(b) +3k+1$ and hence there is a comparison in between the two alphabets. Further comparison are infinite but a finite automaton has only finite memory which are associated with states.

So we can say the above language is not regular hence no finite automaton for it. But there is a problem, I have read a book by Linz in which the above question was given stating that find the regular expression for it. I am a bit confused so any help will be appreciated. I would also be interested in a general approach to answer this type of question.


texts:
I have two questions.

After compilation of any C program result is assembly language code which should depend on processor. So my question is: how do different computers with different processor types, for example Intel i3,i5,i7 etc., are able to run the same software, for example, media-player, browser, etc.?
(I guess strangely it depends on Operating System) and on that software site they do not ask for processor type.
Do programs interact with any part of operating system for conversion of assembly code to machine code?


texts: Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n))

texts:
As said in the title, i am quite curious wether
NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n))
I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n))
due to linear space reduction (i.e. some sort of super character representing k characters)
But since neighter n nor n^2 is linear, we cant use this here.
Thanks for your advise!


texts: Why is Heapsort in O(n log n) if not all n operations take time log n?

texts:
let's consider that we already have constructed heap array.

so from this, when we do heap sort, the number of elements that have to be sorted decreased. I mean heap decrease.(which also means heap tree level decreases -> downheap operation level decreases

but nlogn means each n nodes has logn operation. But not all nodes do logn(original down heap operation level) operation because of heap tree level decrease.


texts: Round-robin scheduling: allow listing a process multiple times?

texts:
In a round-robin scheduler, adding a process multiple times to the process list is a cheap way to give it higher priority.

I wonder how practical an approach this might be. What benefit does it have over other techniques such as giving the process a longer time slice (benefit: less switching time) or maintaining a separate list of high-priority processes. In particular, how does listing a process multiple times influence fairness and reactivity?

(From exercise 2.16 in Andrew Tanenbaum's Operating Systems: Design and Implementation 1st ed.)


texts: does cpu time reflect BigO time complexity

texts:
QUESTION
does CPU time reflect Big O time complexity?
WHAT I MADE
I implemented two Fibonacci functions in C programming language. The former has recursive behaviour while the latter has iterative behaviour.
I found out that the worst case scenario for the recursive version is exponential time (i.e. $2^n$) and linear time for the iterative one - since I have a simple loop within.
I then computed the CPU time for both the version using the time.h C library.
WHAT I EXPECT
I expect those CPU values to be somehow related with that time complexity. Generally speaking, I expect way larger CPU times for the recursive version.
WHAT I GOT
I got the foregoing plot using MATLAB (that is a loglog plot of cpu times as function of $n$).

Seems like the CPU time for the recursive function has an exponential behaviour - that is what I was expecting. Though, I'm not completely sure about CPU time for the iterative version since that function does not look like this one (section log-log graphs).
I'd like to answer myself without doubts but I'm quite newbie.


texts: Is a computer without RAM, but with a disk, equivalent to one with RAM?

texts:
Memory is used for many things, as I understand. It serves as a disk-cache, and contains the programs' instructions, and their stack & heap. Here's a thought experiment. If one doesn't care about the speed or time it takes for a computer to do the crunching, what is the bare minimum amount of memory one can have, assuming one has a very large disk? Is it possible to do away with memory, and just have a disk?

Disk-caching is obviously not required. If we set up swap space on the disk, program stack and heap also don't require memory. Is there anything that does require memory to be present?


texts: Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?

texts:
There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is:
There are n tasks, each task t_i has a weight w_i and a length l_i. Find an order of tasks t_1, ... t_j, ..., t_n that minimizes the total cost of completion, where the cost of completion of each task is c_j * w_j, where c_j is the time it has passed since you started working on the first task until you finished the jth task.
If we analyze the problem a bit, we can see that the task that we choose to complete first will impact the cost of all the remaining tasks. For example, say you only have 2 tasks:
task_1 with w_1 = 1 and l_1 = 5 and
task_2 with w_2 = 4 and l_2 = 2
If we started first task_1, its cost would be 5 * 1 = 5 while if we started first task_2, its cost would be 2 * 4 = 8. But, the cost of completing task_2 after task_1 is (5+2) * 4 = 28. This shows clearly that the order of completion of one task affects the cost of completion of all the remaining tasks.
Considering how each task we decide to complete next impacts the cost of all the remaining tasks, it startles me that the best order is simply the order we get by sorting the tasks by their ratio w_i/l_i.
Which part of the problem hints that the solution doesn't require to check all the possible orders?
The problem is taken from Algorithms Illuminated 3 by Tim Roughgarden.


texts: Is there an asymptotically optimal algorithm for unbounded search?

texts: Suppose you have files with size $1,2,3,4\dots$ (which can be arbitrarily large and which have and can have any value that you want) and a USB-stick whose memory size $s$ you don't know, where $s$ is a positive integer and can be arbitrarily large. If $s$ is not smaller than your current file you get a message that it would be possible to write the file on the USB-stick. If your current file is larger than $s$ then you get no message. In each time unit one file can be tested. My question is, is there an algorithm which finds $s$ in as few time units as possible and would this algorithm asymptotically optimal?


texts: When should you disable all interrupts in a program?

texts:
Consider a machine that has nested interrupts (a higher priority interrupt can interrupt a lower priority one, the current instruction's address is saved and later restored). Why would a programmer want to disable all interrupts using instructions like x86's CLI when you know that even when your code gets interrupted it will always return to what you it was doing?

To me it looks like disabling interrupts is bad for performance because a very high priority and thus very important interrupt has to be dealt with as quickly as possible and you are stalling that by disabling interrupts.


texts:
We have a network of sensors organized in tree form, where the sensors
  occupy the nodes. Most of the time the sensors are turned off, until
  the root sensor wakes up the rest of the sensors. This process of
  awakening the nodes requires a certain amount of time since, in a
  unit of time, a sensor can awaken only one of its children. Obviously, the total wake-up time for all sensors depends on the order in which each sensor wakes up your children.

  It is asked to design an efficient algorithm that gives a sorting of
  the children of each node in the tree providing the minimum time to
  wake up all the sensors.

The solution must use dynamic programming.

I have got no clue where to start from; I know dynamic programming exercises are based on suboptimal structure and overlapping problems, and in this case, at least, overlapping problems is quite obvious since the tree structure is used.

Have you got any clue about the underlying recurrence? -- I am not asking you the solution since those are my homework :)

Thanks.


texts: Contradiction in regularity of a language

texts:
Lets say we have $L_1$ which contains all binary numbers divisivle by 2 but not by 4. I would say this language contains all words with a 10 at the end. Ive found a regular grammar $G$ with $L(G) = L_1$ so that $L_1$ must be regular.

Now I have the problem that my teacher told me that $L_2 = \{ww| w \in \{0,1\}*$  and $w$ ends with 10$\}$ is not context free.

But if $L_1$ is regular or context-free, so should $L_1L_1=L_2$ be also regular and context free.

Where is the mistake?


texts: Proving complexity by reduction using strongly NP-hard problem

texts:
I have a decision problem $X$ of which I think I can show its complexity by using a reduction from a problem $Y$ that has been shown to be strongly NP-hard.

I tried to follow the same procedure as for proving NP-completeness which I try to summarize here:

Show that problem $X$ is in NP (polynomial time verifiable)
Make the Karp reduction from a known NP-complete problem by finding a poly-time algorithm that transforms the instances $y$ of $Y$ to instances $x$ of $X$
Show correctness of algorithm: Show that for every yes/no answer to an instance of $Y$, the algorithm also returns yes/no

The problem I'm currently facing concern point 1 and 2:

I'm sure that $X$ is in NP, but $Y$ is not necessarily, right? Is it a problem when I try to reduce an NP-hard problem to an NP-complete one?
The strongly NP-hard problem $Y$ is not necessarily NP-complete, right? Can I still use $Y$ here?

Another open question regards the fact that $Y$ is strongly NP-hard:

Assuming that I can do the reduction as outlined above, is then $X$ also strongly NP-complete?


texts: Does the Longest Common Subsequence problem reduce to its binary version?

texts:
I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by solving LCS for bit-strings we can also solve LCS with an arbitrary (but finite) alphabet cardinal.

It seems reasonable for me that such a reduction exists (based on the complexity of algorithms for various versions of the problem), however, I couldn't find something like that.


texts: How to prove that a system is real-time?

texts:
I'm writing a paper on the system I designed which upon receiving an event, performs a number of calculations and publishes the result to several subscribers. I can calculate the amount of time it takes from the moment the system is informed about the event, to the moment when all subscribers successfully received the calculation results. I perform multiple experiments to measure the amount of time for a various number of subscribers.

In my paper, I'm claiming that my system is capable of real-time responses to the first event. Could you please give me some hints that how I can prove that based on the data I collected? Thanks


texts: Affine transformation to transform a plane into another

texts:
Having the implicit plane equation

$$ax + by + cz + d = 0\,,$$

how do I find the affine transformation that must be applied to transform this plane into the plane with equation

$$x + y = 0\,?$$

Please note in my case this is the horizontal plane as $y$ points up.


texts: What is the difference between a "meta model" and "design patterns"?

texts:
Where is the difference between a "meta model" and "design patterns"?

If you take, for example, Fowlers "Identity Field" from his book "Patterns Of Enterprise Application Architecture": Why is this a pattern and not a meta model?

Thanks!


texts: Is the following intuition valid for understanding $k$-wise independent hash functions?

texts:
I really enjoy reading up on algorithms and data structures and in the course of doing so often come across ones that rely on $k$-wise independent families of hash functions. I'm perfectly comfortable working with these families of hash functions as black boxes (that is, I understand the relevant definitions and how the algorithms and data structures rely on those definitions), but when I look at specific examples of families of $k$-wise independent families of hash functions, I often have a really hard time understanding why they work. I assume that a lot of this is due to the fact that I don't have a super solid grasp of number theory or finite fields.

One trend I've noticed is that to form a $k$-wise independent family of hash functions whose domain and codomain is a set $\{0, 1, 2, 3, \dots, p-1 \}$, where $p$ is a prime, you can choose a random $(k+1)$-degree polynomial by choosing $k+1$ random elements out of $\{0, 1, 2, \dots, p-1\}$, then to have the hash function be "evaluate the polynomial on the given input value." (I assume that this is equivalent to choosing a random $(k+1)$-degree polynomial over $\mathbb{F}_p$, though I may be mistaken about this.)

My intuition behind why this approach works is that, just like a degree-$(k+1)$ polynomial over the reals cannot be determined by $k$ or fewer points, a degree-$(k+1)$ polynomial over $\mathbb{F}_p$ cannot be determined by $k$ or fewer points. As a result, these polynomials work well as hash functions because, with random coefficients, if you see $k-1$ outputs of the hash function, it's impossible to predict any $k$th output of the hash function better than a random guess because you can't determine what the polynomial is.

My questions are the following:

Is this a correct intuition for why these families of hash functions work correctly?
I teach undergraduate courses on algorithms and data structures that do not have number theory or abstract algebra as prerequisites. If this intuition is correct, would it be inappropriate / misleading to use this intuition to explain these families of hash functions?

Thanks!


texts: Variant of an approximation algorithm for vertex cover

texts:
Here is an approximation algorithm that finds vertex cover of a graph.

 C = {}
 E' = {Edge set}
 while E' =/ 0
   Let (u,v) be an arbitrarily edge of E'
    C = C U {u,v}
    remove E' incident on u and v.
return C

A variant: what if instead of removing edges incident on both $u$ and $v$, we removed only $u$. Would this affect the optimal vertex cover? If so, how?

I somehow feel the optimal vertex cover remains the same whereas only the number of steps to remove the edges would increase increasing time and space complexity. Am I right?


texts: Are finite-domain binary constraint satisfaction problems solvable in polynomial time?

texts:
Suppose a CSP has $n$ variables with finite domains of maximal size $d$. Furthermore, all constraints on the variables are binary. Can such a CSP be solved in polynomial time in $n$ and $d$?

This was an exam question on last year’s AI exam, but I’m not sure how to solve it.

I know the problem of graph coloring is easily reduced to such a binary CSP, so solving them is NP-complete. Thus, I’m pretty sure that there is no known polynomial-time algorithm. Can I prove that there isn’t one?


texts: Can we build computer without instruction pointer register (PC/IP)?

texts: I am studying computer architectures in university and my teacher asked me if we can create a computer without PC/IP register?


texts: Is the union of 2 non context free languages always non context free?

texts:
Let $L_1 = \{a^nb^nc^n\}$
and $L_2 = \{a^ib^jc^k \mid i\ne j\text{ or }j\ne k\}$ (which I think is a non Context free but I am not sure)

So, $L_1 \cup L_2$ will give $L_3 = \{a^*b^*c^*\}$ which is a CFG.

Is this correct?


texts: Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?

texts:
Let $L$ be a regular language over alphabet $\Sigma$. $L$ is the result of merging $2$ languages letter by letter that is for $a_1a_2...a_n\in L_1, b_1b_2...b_n\in L_2, L=a_1b_1a_2b_2...a_nb_n$. $\epsilon \in L \iff\epsilon \in L_1,L_2$. Does this mean that $L_1$ is necessarily regular?

At first I tried to prove that this is true using closure properties of regular languages before finding out that the claim is not true (e.g. $L_1=\{a^ib^i|i\ge 0\}, L_2=\{ab\}$).

I'd like to understand though what's wrong with my proof:

1) Define homomorphism $h:\Sigma\to \Sigma^*\cup \Sigma'^*$ as follows: $h(\sigma)=h(\sigma')=\sigma$ for $\sigma,\sigma'\in \Sigma.$

2) Let $X=h^{-1}(L)\cap(\Sigma\Sigma^*)$

3) Define another homomorphism: $f_1:\Sigma^*\cup \Sigma'^*\to \Sigma$ like this:
$$
f_1(\sigma)=\sigma\\f_1(\sigma')=\epsilon
$$
4) Define another homomorphism: $f_2:\Sigma^*\cup \Sigma'^*\to \Sigma$ like this:
$$
f_2(\sigma')=\sigma'\\f_2(\sigma)=\epsilon
$$
Then $L_1=f_1(X), L_2=f_2(X)$. Now if either $L_1$ or $L_2$ is not regular than it's contradiction because by closure properties they should've been regular. Where is my mistake?

EDIT: following one of the comments, the problem with the attempt to use closure properties is that apply the homomorphisms $f_1,f_2$ on $X$ we may get a different language from the original one.


texts:
This is the first time I will be studying compilers in depth. Can someone point me to best online resources (courses, articles, tutorials, video etc ) and books?

My main aim will be to do some practicals instead of just reading theory.-something where theory practical goes in parallel. So the reference must fulfill this expectations.


texts: minimum number of edges that should be added to an undirected graph to make it a tree

texts:
Basically, it's this rosalind problem.
You're given a number of nodes and an adjacency list.
My initial guess was that the answer was the number of connected components minus 1, since by joining every connected component you would have a connected graph, and since it's stated that there are no cycles, that would be a tree.
Why is this approach wrong? The real answer is just the number of nodes-1-number of edges, which I understand, but can't see how is this not equivalent to my answer.
Also, the sample dataset given bugs me. I see three connected components so I don't see why the answer is not 2.
Bear in mind, i'm almost new to graph theory so i'm sorry if i'm missing something simple.


texts: Rearranging strings so that the Hamming distance between them is 1

texts:
This is a question from CodeFights.com:

  Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.

  Example

  For inputArray = ["aba", "bbb", "bab"], the output should be
  stringsRearrangement(inputArray) = false;
  All rearrangements don't satisfy the description condition. (sic)
  For inputArray = ["ab", "bb", "aa"], the output should be
  stringsRearrangement(inputArray) = true.
  Strings can be rearranged in the following way: "aa", "ab", "bb".

I found an exponential-time algorithm, but is there a polynomial-time algorithm? Is this problem NP-complete?

I know that a closely related problem, the Hamming Salesman Problem (HTSP), is NP-complete, and this problem is certainly reducible to HTSP, but I don't know if HTSP is reducible to this one.


texts: Understanding paging and internal fragmentation

texts:
I am currently studing questions but stuck on this one, I hope someone can help me out to understand.

Question: Assume that we have a paged virtual memory with a page size of 4Ki byte. Assume that each process has four segments (for example: code, data, stack, extra) and that these can be of arbitrary but given size. How much will the operating system loose in internal fragmentation?

The answer is: Each segment will in average give rise to 2Ki byte of fragmentation. This will in average mean 8 Ki byte per process. If we for example have 100 processes this is a total loss of 800 Ki byte.

My question:
That 2Ki byte each segment is confusing but I think that is just a guess. Anyway, if we have 8Ki byte per process, that would not even fit in a 4Ki byte page isn't that actually a external fragmentation? Can someone explain the correct answer that is easier to understand?


texts: Why does this grammar derive into $\beta \alpha ^*$ instead of $\alpha ^* \beta$?

texts:
In this video clip the teacher presents a grammar $A \rightarrow A \alpha | \beta$ and after providing the parse tree explains that the regular expression for the language generated is represented as $\beta \alpha ^*$.

Why isn't it $\alpha ^* \beta$ instead? Isn't the grammar left-recursive into terminal $\alpha$ and once terminal $\beta$ is reached the string ends?


texts: Why does the copycat strategy work for two parallel chess games?

texts:
I'm currently looking into computability logic.
Japaridze explain that a game !P v P like !Chess v Chess is always winnable thanks to the copycat strategy (http://www.csc.villanova.edu/~japaridz/CL/3.html#copycat). However, what guarantees that the environment will play the same moves? One game could be e4 e5, but the other one e4 Nf6, and then the machine won't know what to do, right?

I'm probably not getting something, but I don't know what. Could someone help me?

Thanks.


texts: (OCR ) How to Recognise Handwritten fractional numbers using Neural networks

texts:
I want to be able to recognise handwritten math numbers using images of the numbers , i was able to do  create a ANN model for recognising simple decimal numbers , but i have no idea on how to recognise fractional number.
What kind of ML model do i need to recognise fractional numbers (p/q forms). As i am relatively new to machine learning, i have no idea how to do it. Any study material will be appreciated.


texts: Is determining if there is a prime in an interval known to be in P or NP-complete?

texts:
I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval.   However, does this mean that the overall decision problem of: (Does there exists a prime in an interval?) is in P. (There were a lot of answers to that post that I did not read so I apologize if this question is a duplicate or unnecessary).

On the one hand, if the interval is large enough (for example $[N,2N]$) then something like Bertrand's Postulate applies and there is definitely a prime in this interval.  However, I also know that there are arbitrarily large gaps between two primes (for example $[N!,N!+ N]$.

Even if the decision problem is in P I don't see how the corresponding search problem is also tractable because, then we may not be able to draw on the same properties regarding the known distribution of primes when performing binary search.