texts: IS Array of Positive Integers Always 'Equalizable' With This Strategy?

texts:
A little bit of history first. I have asked this question here some days ago. Quoting from there:

  An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\{2,2,3,7\}$ and $D=\{1,2,5\}$ we can equalize $A$ in two steps, first adding $A=\{5,5,5,0\}$ to get $A=\{7,7,8,7\}$ and then adding $\{1,1,0,1\}$ to get $A=\{8,8,8,8\}$.

If $A$ has just two elements, this reduces to something like a change-making problem. If $\Delta=min(A[0],A[1])$, if I can make change for $\Delta$ using only the given steps from $D=\{1,2,5\}$, I can equalize the array by holding the larger element constant while incrementing the smaller element by the same values that I used to make change for $\Delta$. However,if it's not possible to make change for delta, it's not clear if the two elements can converge two some larger value following this strategy.

I would like to know if this strategy of withholding one element and incrementing the rest by a chosen 'delta' will always make all elements equal in some finite number of steps.


texts: A TM that doesn't decide Σ*, and a TM that doesn't decide the empty set?

texts:
I was wondering if it was possible to create a TM that semi-decides (but doesn't decide) either of the following two languages:

$\emptyset$
$\Sigma^{*}$

I assume for 2, a one-state TM that just automatically accepts would be fine? I don't think it's possible for any input not to halt, or be rejected, so technically the TM would just semi-decide?

However, for 1, I'm not 100% sure what that TM would look like. Would I just have to figure out a way to have at least one input (or, more simply, all inputs), not halt, since none could possibly accept?

Edit: I know such TMs must exist, I'm more so confused as to what they look like.


texts: Connection between max independent set and graph coloring

texts: Is there any connection between the size of the largest independent set in a graph, and the minimum number of colors required to color the graph? I know that we can potentially color all the vertices in the largest independent set in the same color, but we know nothing about the rest of the vertices (besides being a vertex cover). Am I wrong?


texts: How to transform a Infinite decimal of $\frac{23}{6}$ into binary?

texts:
How to transform a decimal of $\frac{23}{6}$  into binary?

$\frac{23}{6}$ is equal to $3.83333\bar{33}$, where the digit $3$s are repeated forever.

I do know how to translate finite decimal into binary, but
is there any procedure to translate such Infinite decimal like $\frac{23}{6}$ into binary?

Any hint is appreciated!


texts: Why are so many internet protocols text-based?

texts:
From what I have found, a very large amount of protocols that travel over the internet are "text-based" rather than binary. The protocols in question include, but are not limited to HTTP, SMTP, FTP (I think this one is all text-based?), WHOIS, IRC.
In fact, some of these protocols jump through some hoops whenever they want to transmit binary data.
Is there a reason behind this? Text-based protocols obviously have a bit of an overhead as they require sending more data to transmit the same amount of information (see example below). What benefits outweigh this?

By text-based, I mean most of the characters used in the protocol are between 0x20 (space) and 0x7E (~), with the occasional "special character" used for very special purposes, such as the newlines, null, ETX, and EOT. This is opposed to transmitting raw, binary data over the connection.
For instance, transmitting the integer 123456 as text would involve sending the string 123456 (represented in hex as 31 32 33 34 35 36), whereas the 32-bit binary value would be sent as (represented in hex) 0x0001E240 (and as you can see, "contains" the special null character.


texts: Paging operations research people: how is the field evolving?

texts:
I asked this question to the OR community (https://or.stackexchange.com/questions/1498/how-is-the-field-of-operations-research-evolving) but, since there are quite a few CS people working in OR, I would like to get the perspective of the community.

Classically, it seems the problems that OR people studied (at least the ones I am most familiar with) were related to decision theory, optimization and scheduling, and queuing theory with the general sentiment that solving these problems would be of interest to a company's operations.

More recently, the lines between OR and other fields have gotten a bit more blurry for me. I am seeing more venues that focus on the intersection between OR, economics (game theory), and computer science. For example, see the recent talks at EC. Also see a new INFORMS conference on the intersection of OR and security.

Question(s): My main question concerns the current trajectory of the OR field and OR departments. Is the focus of OR becoming blurry or has the underlying motivation for the field changed? What's the future for OR: as problems traditionally studied under OR become more central in society, will other fields (e.g. computer science) begin to take over/cannibalize OR departments?


texts: What is the relation between functors in SML and Category theory?

texts:
Along the same thinking as this statement by Andrej Bauer in this answer

  The Haskell community has developed a number of techniques inspired by
  category theory, of which monads are best known but should not be
  confused with monads.

What is the relation between functors in SML and functors in Category theory?

Since I don't know about the details of functors in other languages such as Haskell or OCaml, if there is info of value then please also add sections for other languages.


texts:
Hello, all,

First time poster, here.
Anyways, here is my question from the textbook Introduction to the Theory of Computation, 2nd Ed. (Sipser, 2006). Question 1.19 is asking us to convert a regular expression to a nondeterministic finite automaton. The regular expression is given as:

(0 union 1)* 000 (0 union 1)*

Which I interpret as:

"Any number of 0's or 1's, followed by 000, followed by any number of 0's or 1's."

This is the solution that I came up with:

However, the professor of this course I am taking provided a solution, albeit unsimplified, that is different from mine. I am wondering where I went wrong. I have asked this same question to my professor via e-mail (distance ed.), but since I am not expecting a reply based on past experience, I have also asked this question here. Any help you can provide would be greatly appreciated.


texts: Does a greedy strategy exist for this instance of the Bin Packing Problem?

texts: I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 dimensions. Can a solution be found where each item is assigned to a container so that it fits inside? I can have containers left over; however, all of the items must be assigned. Assuming a solution exist, is there a greedy choice I can make for assigning an item to a container?


texts: How to compute Jacobi symbol efficiently?

texts:
How do I compute the Jacobi symbol $(N|A)$ efficiently?

In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod_i Q_{p_i}(A)$ where $p_1, \dots , p_k$ are all the (not necessarily distinct) prime factors of $N$ (i.e., $N =\prod_i p_i$), and where $Q_p(A)$ is defined as below (i.e., $Q_p(A)$ is the Legendre symbol $(A|p)$).

Arora and Barak claim that the Jacobi symbol is computable in time $O(\log A \cdot \log N)$.  How do I see this?  What algorithm can be used to compute the Jacobi symbol like this?

Motivation:

Sanjeev Arora and Barak sketch a proof that $PRIMES$ is in $BPP$. First they define a function $Q_N(A)$

$$Q_N(A) = \begin{cases}
  0, & \text{if } \gcd(N,A) \ne 1, \\
  1, & \text{if } A \text{ is a quadratic residue modulo $N$} \\
  -1, & \text{otherwise}.
\end{cases}$$

Then they state the following properties:

For every odd prime $N$ and $A ∈ [N − 1]$, $QR_N (A) = A^{\frac{(N−1)}{2}}
\pmod N$.
The Jacobi symbol is computable in time $O(\log A \cdot \log N)$.
For every odd composite $N$, $|\{A ∈ [N − 1] : gcd(N, A) = 1 \text{ and } (A|N) = A^{\frac{(N−1)}{2}}\}| \le \frac{1}{2}|\{A ∈[N − 1] : gcd(N, A) = 1\}|$

Then they give the corresponding algorithm :
Choose a random $1 \le A \le N$, if $gcd(N, A) > 1$ or $(A|N) = A^{\frac{(N−1)}{2}}
\pmod N$ then output “composite”, otherwise output “prime”.

If all the above 3 properties hold then I can see that $PRIMES$ is in $BPP$, but I am unable to prove property 2, regarding the Jacobi symbol.


texts: Does this algorithm (least Hamiltonian path, checking vertex count, and no duplicates) decide Hamiltonian paths? If so, what is its space complexity?

texts:
Let G be a graph
Suppose G has N vertices
Let H be the set of Hamiltonian paths in G
If G has a Hamiltonian path, then by systemically changing our start vertex and then nondeterministically walking the remaining N vertices, we will find it (i.e. take a "random walk").
Can we nondeterministically walk such that if there's a Hamiltonian path, we'll choose the least next vertex? Let's call this the least Hamiltonian path.
For example, let G1 be a graph with 3 vertices and all possible edges
Then there are 6 elements of H: 123, 132, 213, 231, 312, 321
In G1, if our start vertex is 3, then there are 2 Hamiltonian paths: 312 and 321.
By nondeterministically choosing the least next vertex of the Hamiltonian if one exists, then we'll always choose the same Hamiltonian path: 312 in this case (because our start is 3 and 1 < 2).
If we are allowed to nondeterministically choose the least next vertex, then we can nondeterministically traverse the  same Hamiltonian path multiple times.
We ensure the least Hamiltonian path has no duplicate vertices. Pseudocode:
function hasDuplicates(leastHPath):
  for (j in N):
    for (k in N):
      if (k == j) continue;
      if (leastHPath[j] == leastHPath[k]:
        return false;
  return true;

Does this algorithm (nondeterministically choosing the least Hamiltonian path if one exists, ensuring the count of vertices = N and ensuring there are no duplicates) decide Hamiltonian paths? If so, what is its space complexity?


texts:
How does the NFA decide in a state where there are multiple equally valid "next states"?

Such as here:

How does it decide on which state it takes to with 1?


texts: Proving that a certain graph contains a 4-cycle

texts:
Show that if $G$ is a graph with $|E| \geq 2|V|^{3/2}$, then $G$ must contain a $4$-cycle

Can someone explain/point me in the right direction on this?
Let's say we say $|V|= 4$, using the equation above we get $|E|= 16$.

I drew it out and I was unable to come up with $16$ edges. Do I completely misunderstand the graph equation?


texts: Context free grammar to Chomsky normal form

texts:
I have a hard time understanding how to convert the following context free grammar to Chomsky Normal Form:
S $\rightarrow$ aSX | B
B $\rightarrow$ bBX | ε
X $\rightarrow$ a | b
I have a solution
S $\rightarrow$ EY | EZ | FY | FZ | ε
E $\rightarrow$ YS
F $\rightarrow$ ZB
Y $\rightarrow$ a
Z $\rightarrow$ b
that does not work and can't figure out why. Any solutions and explanations would be helpful.


texts: How to write suitable three address code for switch-case statements?

texts:
I want to translate a java switch-case statement to intermediate representation of the three address code form. Three address code or TAC is a form of intermediate representation where each instruction contains at most three addresses and one operator. An address is a name such as x (stored in the symbol table), compiler generated temporary such as $t_{1}$ or a constant such as 3.14 or ‘s’. A name could refer to a variable, label, etc.
If you have an arithmetic statement

(3 * w) + y

then the corresponding TAC would be

$t_{1}$ = 3 * w
$t_{2}$ = $t_{1}$ + y

Now, when it comes to switch statements, my textbook (the Dragon Book for Compilers), gives a translation of this form:

for a switch-case statement of this type:
switch E
case V1: S1
...
case Vn-1: Sn-1
default: Sn
Assuming the first translation is used, at the code generation stage (when we convert 3AC to machine code), the code generator will interpret the instructions as a sequence of conditional and unconditional jumps with intervening labeled statement blocks. It would translate them into the machine code (say x86) version of the same. When these instructions are executed by the processor, it handles each jump sequentially to determine the correct labeled block to be executed.
But, I have also read that the machine code translation of a switch-case statement includes a jump table that allows the processor to execute the entire switch statement in one go. So, then which version is used?
I wanted to post this on stackoverflow but I do not have enough reputation to post an image.


texts:
How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time?

Having an undirected graph, I am trying to partition all its vertices into cliques so that the number of cliques is the smallest. The problem can be formulated as an integer program, where every vertex corresponds to an integer variable (index of its clique), and the objective function is to minimize the sum of all these variables. For every edge not in the graph, a condition is created to ensure the corresponding vertex variables are not equal, like this:

$$b_k \in \{0, 1\}$$
$$x_i - x_j + M*b_k >= 1$$
$$x_j - x_i + M*(1-b_k) >= 1$$

$b_k$ indicates the relation between the values of $x_i$ and $x_j$. With a sufficiently large $M$, one of the conditions is always true, in which case the other one ensures the distance between the values is at least 1.

However, this approach seems to have exponential complexity, making it work only on very small graphs.

Assuming the number of cliques is expected to be small, and usually no edges exist across cliques, is there a better approach to this problem? I am thinking about finding the maximum independent set first and use it to fix certain variables (since they are guaranteed to be in different cliques). Will that help in increasing the speed?


texts:
Is language {M | M halts and print "Hello World"} recursively enumerable?
I'm not sure my proof is correct.
Let universal Turing machine U start another Turing machine M2 that reads result of work of given Turing machine M1, which halts on "Hello World" and goes to infinite loop otherwise. Then M2(M1) halts if and only if M1 prints hello  "Hello World".


texts: Techniques to create a PDA for a language that is the conjunction of two languages

texts:
When I was working with finite automata, I figured out that we can put together two FA two build a new one that is the intersection between the two. This is possible because regular languages are closed under intersection. Now, I am having many difficulties in drawing PDAs especially the ones that are apparently the intersection of two other PDAs. For example, suppose I am asked to build the PDA for $$\{w \mid w \text{ is a palindrome and w has at most two 0s } \}$$

I think I would be able to build a PDA that recognises palindromes (which is one of the easiest ones), and also one that recognises a language that has at most two $0$s. But I am having many difficulties in building a PDA for the language above.

Apparently CFG are not closed under intersection, so I suppose there's no mechanical way of coming out with a solution for an intersection of two languages. Since this might be the case, do you have any suggestions on how could I start thinking on how to draw a PDA that is apparently the intersection of two other languages?

Note that I am asking for techniques to come up with PDAs for languages that are the conjunction of other simpler languages and not for a solution for the particular case above.


texts: Finding the average time complexity for a max algorithm

texts:
I'm trying to find the average-case number of times that max is assigned a value by the below algorithm find_max.
find_max(L):
     max = -oo # negative infinity
     for k = 0 to len(L)-1:
          if L[k] > max:
               max = L[k]
     return max

However, I'm struggling to come to a solution.  So far, this is what I have done:
I'm defining the sample space to be L containing values which are between 1 and 100, and having them uniformly distributed.
The worst-case running time is $T(n) = n + 1$ because of the initial max assignment, and the case where every element is larger than the previous one.
The best-case running time is $T(n) = 2$ which is the case where all elements have the same value, so there is the initial max assignment and one assignment in the for loop.
So, the running time is distributed between 2 and n+1 inclusive.
Then, the average-case running time is:
$E[t_{n}] = \sum_{2}^{n+1} t \cdot P(t)$
However, I am having difficulty defining the Random Variable T and the probability formula for values of T.


texts: What does ⊢ mean in operational semantics?

texts:
I have been reading a couple of texts on operational semantics.

In [1], the evaluation of expressions is done as in this rule:

$\frac{<e_1,s>\;\Rightarrow \;n_1\;\;\;<e_2,s>\;\Rightarrow \;n_2}
{<e_1+e_2,s> \;\Rightarrow \; n_3}$,

where $n_3 = n_1+n_2$.

That is, the state $s$ is represented in a tuple with the expression to be evaluated.

But in [2] a rule for evaluation of a function as this:

$\frac{\rho\; \vdash\; e \;\Rightarrow\; v, \;\;\;\;\rho[v'/x]\;\vdash\;e \;\Rightarrow\; v}
{\rho\; \vdash \;F(e) \Rightarrow v}$

I am confused: why in the first case, the state $s$ was passed along with the expression as a pair, and in the second case, the environment $\rho$ was not (it was to the left of $\vdash$). Does $\vdash$ here have the same meaning as in formal logic? Are the two notations that I have shown (using a pair/tuple and using $\vdash$) interchangeable in operational semantics?

In this text ([2]), the author writes, before the first time he uses $\vdash$,

  In a given environment an expression will evaluate to a numeral. We will write this as $\rho \; \vdash\; e \;\Rightarrow \;v$

But he doesn't explain why, and in another text ([1]) the same author uses the pair notation for the same purpose.

[1] Matthew Hennessy, "Semantics of Programming Languages (CS3017), course notes"
[2] Matthew Hennessy, "The Semantics of Programming Languages: an elementary introduction using structural operational semantics"


texts: Is UTF-8 the final character encoding for all future time?

texts:
It seems to me that Unicode is the "final" character encoding. I cannot imagine anything else replacing it at this point. I'm frankly confused about why UTF-16 and UTF-32 etc. exist at all, not to mention all the non-Unicode character encodings (unless for legacy purposes).

In my system, I've hardcoded UTF-8 as the one and only supported character encoding for my database, my source code files, and any data I create or import to my system. My system internally works solely in UTF-8. I cannot imagine ever needing to change this, for any reason.

Is there a reason I should expect this to change at some point? Will UTF-8 ever become "obsolete" and replaced by "UniversalCode-128" or something, which also includes the alphabets of later discovered nearby galaxies' civilizations?


texts:
some questions have been popping up recently on ambiguity in CFLs/CFGs which can have subtleties (eg languages vs grammars & ambiguity vs inherent ambiguity). wikipedia states:

  Many [context free?] languages admit both ambiguous and unambiguous grammars, while some languages admit only ambiguous grammars.

the sentence is phrased in wikipedia without the "CFL" inserted but am now wondering what effect it has on the logic. after pondering the technical defn of ambiguity (on wikipedia pg) & thinking about it a bit my question:

  does every CFL have an ambiguous CFG? if not what is a counterexample ie a CFL that does not have (any) ambiguous CFG?

(the question arose in that every CFL has multiple CFGs, ie a CFG is only unique to a CFL under additional restrictions, and it seems that given any (unambiguous) CFG one could add small chgs/productions rules to get an equivalent ambiguous CFG...? is this trivial? but rarely pointed out anywhere?)

somewhat related question somewhat involved in sparking this one: Are there inherently ambiguous and deterministic context-free languages?


texts: A "packing" optimisation problem with application in dynamic programming

texts:
I'm interested in the following problem :

Input : an integer $n$, and $k$ increasing functions $f_i:\mathbb{N}\rightarrow\mathbb{R}$, such that $f_i(0)=0$ for all $1\le i \le k$

Output : $k$ integers $n_1,\dots,n_k$, such that $n_1+\dots+n_k=n$, with $0\le n_i\le n$

Goal : Maximize $\sum_{i}f_i(n_i)$

My question is : If we suppose that $k=n$, or simply $k=\Omega(n^\delta)$ for some $\delta>0$, is it possible to find the optimal solution in polynomial time (in $n$) ?

What if we first consider very simple functions like : $\forall i,m, f_i(m+1)-f_i(m)\in\{0,1\}$ ?

Such a result could possibly have interesting applications for dynamic programming


texts: Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?

texts:
I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating push-down automatons from context-free grammars are not always phrased in the same way, with mostly two variations:

For the given grammar G, define a push-down automaton M such that L(M) = L(G)
For the given grammar G, define a push-down automaton M equivalent to grammar G.

In Introduction to Automata Theory Languages and Computation by John Hopcroft, in section 6.3.1 a method to obtain the equivalent push-down automaton for a context-free grammar is defined. Since the book is widely available and very well known, I will not copy the method here.

Of course, it is also possible to figure out the language produced by the grammar and work from there to define an automaton which accepts that language (this would be similar to the first phrasing).

These two method would produce equivalent automatons (i.e. automatons which accept the same language), but I am not sure if there is something that tells them apart.

Is there a theoretical difference between "the push-down automaton equivalent to a context-free grammar" and "the push-down automaton which accepts the language defined by a context-free grammar"?


texts: Generate a random magic square on a large field

texts:
If consecutive natural numbers 1 .. n^2 are placed in a n*n grid so that sum of numbers in each column and in each row is a constant then we call it a magic square.
I would like to generate magic squares of size 16x16 and 256x256 for not skewed byte mapping. Maps arranged as magic squares tend to have better distribution properties. Algo should produce a map that depends on the seed, rather than yield the same result each time.

expectedSum = ((1+n*n)*n)/2). I can shuffle an array using some form of SecureRandom that accepts a seed. Then in case of a small square I can go for a brute force for loop.I can just brute force 3x3 magic square. Considering symmetries I need to check less than 8*(7!) or about 40k possibilities.

This approach wouldn't work for 16x16 board because 256! > 10^500 is quite large. My best guess is to find two row_column pairs such that sums along row and column are greater than the expected sum  in first pair and lower in second pair. If shared element in first pair is greater than in the second pair - swap elements.  This algo seems better than bruteforce (can complete in reasonable time), but there is no guarantee that it halts. Consider 2x2 square to see how it fails.

What is a good Monte-Carlo approach to solve a large magic square?


texts: "Dense" regular expressions generate $\Sigma^*$?

texts:
Here's a conjecture for regular expressions:

  For regular expression $R$, let the length $|R|$ be the number of symbols in it,
  ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^*| = 2$

  Conjecture: If $|R| > 1$ and $L(R)$ contains every string of length $|R|$ or less, then $L(R) = \Sigma^*$.

That is, if $L(R)$ is 'dense' up to $R$'s length, then $R$ actually generates everything.

Some things that may be relevant:

Only a small part of $R$ is needed to generate all strings. For example in binary, $R = (0 \cup 1)^* \cup S$ will work for any $S$.
There needs to be a Kleene star in $R$ at some point. If there isn't, it will miss some string of size less than $|R|$.

It would be nice to see a proof or counterexample. Is there some case where it's obviously wrong that I missed? Has anyone seen this (or something similar) before?


texts: $P/Poly \setminus P$. What langugage does reside there?

texts: What language is in $P/Poly \setminus P$? I was thinking of it by hours but I cannot come with an idea. Please help.


texts: If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

texts:
I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular
So far I know that:

There are examples where $L$ is regular and $L^{|2|}$ is regular (for example $L=\{a,b\}$)
There are examples where $L$ is regular and $L^{|2|}$ is not (for example $L=\{w \mid w=a^N \text{ or } w= b^N\ , N\ge0\}$)

But I am not sure how to prove that it's context-free regardless of which regular language I use. I have found similar problems with the same language without imposing restrictions on which words to use, but I am not sure if those apply to this one.


texts:
I'm new to coding theory and formal proofs, and am struggling to understand how to construct and reason about prefix-free encoding algorithms on algebraic data types. I hope it's clear if I use notation from haskell below.

I'm tasked with writing a generic prefix encoding algorithm (encode) on ADTs, as well as giving guidance to my users in defining their own implementations of encode for their own types if they wish (this being a major reason I want to understand things better).

I've been jumping around sections of Berstel and Perrin's Theory of Codes which has been very helpful, but it's slow going and my goals are pretty narrow here.

One implementation

I believe I have one obvious implementation, which works like this:

  for products, concatenate the results of applying encode to each of
  the children (arguments to the constructor):

data P a b c ... = P a b c ...

encode (P a b c...) = encode a <> encode b <> encode c <> ...

  for coproducts (or a sum of products), assign to each constructor a
  distinct number tag (using a prefix encoding, to be pedantic) which
  will start the code word, then apply the product rule above

data XYZ a b c d... = X a b ... | Y c d ... | Z ...

encode (X a b...) = encode 1 <> encode a <> encode b <> ...
encode (Y c d...) = encode 2 <> encode c <> encode d <> ...
encode (Z ...)    = encode 3 <> ...
...

The product rule I'm comfortable with: I've proved to myself that the cartesian product of two independent prefix codes is also prefix.

The coproduct rule also seems to be obviously correct if we're thinking in terms of sums-of-products, and if the product rule holds.

Where I'm struggling, I think is in reasoning about recursion, for instance for inductively-defined lists:

List a = Cons a (List a) | Empty

I believe my algorithm works in the presence of recursion, but how can I go about proving this using induction? I think my trouble is that "prefix" is a property of the (infinite) set of code words, not any one.

Other possibly-better algorithms

A proof of the algorithm above would be helpful, but my goal is to have an algorithm that tends to generate compact code words (in fact I don't care about decoding at all; only that the range of encode be prefix), and so I want to understand this more fully.

For instance there is a better algorithm for List. An alternative would be:

encode l = encode (length l) <> map encode l

It occurred to me that maybe this is just a special case of a run-length encoding of a variation of the algorithm in section 1, where constructor tags are all concatenated before the concatenation of encoding the list elements.

But why should it be valid to do that? Can this algorithm for lists be generalized to produce better (more compact) prefix codes for arbitrary ADTs?


texts: Algorthm: Given a set of points, width around line, find line to capture maximum points

texts:
I want to know if there is an algorithm for this problem.

I have a list of points given as (x,y) values and a given distance. I want to draw a line through the set of data points so that the size of the set of points that is within the given distance from the line is maximized. That is, this line

Does an algorithm for this problem exist?


texts: Visualization of Lamport's three-dimensional "space-time diagram" with introduced "tick lines"

texts:
In the third page (the third paragraph in the right column) of the paper "Time, Clocks, and the Ordering of Events in a Distributed System" by Leslie Lamport, it says that

  The reader may find it helpful to visualize a two-dimensional spatial network of processes, which yields a three-dimensional space-time diagram. Processes and messages are still represented by lines, but tick lines become two-dimensional surfaces.

However I failed to visualize them in my head, especially the two-dimensional surfaces. Could anyone make more explanations? An illustrative picture would be excellent.


texts: How you can find the number of balanced binary tree knowing only the number of nodes? Is there a method better than generate all possible balanced trees and if not how can i generate those trees based only on the number of nodes?


texts:
Recently while solving programming challenges for the fun of it, I encountered a challenge which left me kind of puzzled and yearning for a proper solution, other than brute forcing. The problem (stated in my own words) is as follows:

In each testcase you are given N (6 <= N <= 10) sticks.
Each stick has length L (1 <= L <= 20) provided. The lengths are represented by space separated integers.
Print the maximum area that can be created by forming a rectangle from these sticks.
Example input:
1 // testcase count
6 // number of sticks
1 1 2 2 3 1 // lengths

I have managed to solve this problem using brute-force method (which's complexity I didn't dare estimate), stacking multiple for loops and lots of if conditional statements.
However, I believe there must be some algorithm that would be suitable for this kind of a problem - there usually is one smart solution in those algorithm puzzles.
I tried to think of a solution for the past few days and didn't come to any meaningful conclussion.
I would greatly appreciate any suggestions - I don't need no code or ready solutions, only a hint about whether there is some algorithm that could be used here to make the solution more elegant, and with better computational complexity than a simple brute force.
EDIT
You are supposed to form 4 edges of a rectangle. Sticks can be stacked on top of each other to form a longer stick. Eg.

a1 = 2+2
a2 = 3+1
b1 = 1
b2 = 1
a*b = 4

The problem is to maximise the value of a*b.


texts: What is the most used way to write for-loop as pseudocode?

texts:
for $e\leftarrow1$ to 8 do
for $e\in[1,8]$ do
for $e\in\{x\in\mathbb{N}|1\le x\le8\}$ do

What is more preferred?


texts: How can I prove this language is not context-free?

texts:
I have the following language

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-sensitive grammar so I know it is atleast context-sensitive. It seems like it wouldn't be possible to make with a context-free grammar, but I'm having a problem proving that.

It seems to pass the fork-pumping lemma because if $uvwxy$ is all placed in the third part of any word (the section with all of the $2$s). It could pump the $v$ and $x$ as many times as you want and it would stay in the language. If I'm wrong could you tell me why, if I'm right, I still think this language is not context-free, so how could I prove that?


texts: Finding all rows of 2 variables using Gaussian Elimination

texts:
Suppose I have a system of linear equations. Using Gaussian elimination, I can determine whether a solution exists, and even find a valid solution.

During the elimination, I can combine rows together, to produce new rows with different number of variables. Is there a method to find all possible rows that contain exactly 2 variables? For example, I may want to find all equalities between variables. This is equivalent to finding all rows that contain exactly 2 variables. Is it possible to do this without trying all (exponentially many) combinations of rows?

For example if I have:

Row 1: A xor B xor C = 1

Row 2: A xor B xor D = 1

I can combine row 1 and row 2 to say that C xor D = 0

If I have a large amount of rows, and they require large combinations of large rows to produce smaller rows, is it trivial or hard to find all rows of size 2? Can I do better than adding random pairs to the system and checking it still has a solution?


texts: Having Moore's law is it worth looking for more algorithms?

texts: knowing that Moore's law states that is the observation that the number of transistors in a dense integrated circuit (IC) doubles about every two years. is it worth looking for more algorithms?


texts: Graph problem known to be $NP$-complete only under Cook reduction

texts:
The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a Karp reduction since there is no restriction on the number of calls to the oracle. So, I am interested in NP-complete graph problem that does not have a known Karp reduction from a NP-complete problem.

  Is there a natural graph problem known to be $NP$-complete only under Cook reduction, but not known to be NP-complete under Karp reductions?

Naturalness should disallow specific features of feasible solutions, for otherwise it is quite easy to start from well-known problem and make it a little easier by allowing specific features.


texts:
I'm trying to come up with a good algorithm for the following decision problem:

Let $G=(V,A)$ be a directed graph and let $s,t \in V$. Are there at-least 2 non-intersecting paths from $s$ to $t$?

By non-intersecting I mean that if $P_1$ and $P_2$ are non-intersecting paths from $s$ to $t$ then $\forall e\in P_1\in A, e\notin P_2$ (can share vertices but not edges).

I thought of the following algorithm:

Find the shortest path $P\in A$ in $G$ from $s$ to $t$. if no such path exist, return false;
Find the shortest path $P'\in A-P$ in $G$ from $s$ to $t$. if no such path exists, return false; else return true.

I didn't find a contradicting example but so far I was unable to prove its correctness.

Ideas about proof approaches for this algorithm or suggesting other algorithms is welcome.


texts:
im looking for some guidance on how to get started with sorting an array of booleans so that the falses would be in front of the trues.

so if given this:
a = {true, true, false, true, false}

it would return:
a = {false, false, true, true, true}

here is the exact question:
     Suppose you have an array of booleans of size n. Give an algorithm that sorts the array so that all false elements come before all true elements.

Thanks for any help you can give me!


texts:
How might indexes be represented in the context of relational algebra?

How would an optimizer transform a query to use indexes?


texts: What is the "shortest path heuristic" for the Steiner problem in graphs?

texts:
I keep encountering citations of the following article:

Takahashi  and  A.  Matsuyama,  “An  approximate  solution  for  the Steiner  problem  in  graphs,” Math. Japonica,  vol.  24,  no.  6,  pp.  573–577, 1980

For example, Yahui Sun refers to it here as "a widely-used Steiner tree approximation algorithm".
But... what is the actual algorithm?
The website of Mathematica Japonica only goes back to 1994, and I can't find the article anywhere else either.
Wikipedia contains this description, but without a citation:

The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices. The metric closure of a graph G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G. This algorithm produces a tree whose weight is within a 2 − 2/t factor of the weight of the optimal Steiner tree where t is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. The approximate solution is computable in polynomial time by first solving the all-pairs shortest paths problem to compute the metric closure, then by solving the minimum spanning tree problem.

Is this the algorithm that Sun and others refer to?


texts: Does the category of functors possess a coexponential?

texts:
Suppose I have maps
lam : (u -> u) -> u
app : u -> (u -> u)

One sort of dual concept would be
lam : (u -< u) -> u
app : u -> (u -< u)

What would it mean to map to and from a coexponential?
lamMap : ? -> hom (lam f) (lam g)
appMap : hom a b -> ? (app f) (app g)

My intuition is one would encode a sort of coexponential via negation.
lamMap : hom a b -> (forall x. void (f x) (g x)) -> hom (lam a f) (lam b g)

But this doesn't seem to really work to me.
I think you could also try switching around variance but that also gets rapidly confusing.


texts: Reccurrence equation and finding suitable algorithm

texts:
I'm given the following recurrence equation:

$$\begin{align*}
    T(1) &= 0\\
    T(n) &= T(n/2) + 1  && \text{when $n > 1$ is even}\\
    T(n) &= T((n+1)/2) + 1 && \text{when $n > 1$ is odd.}
\end{align*}$$

The problems I have are the following:

1) What does $T(1) = 0$ mean when it comes to writing computer program? It cannot be

return some_constant;

because this gives the complexity of $T(1) = 1$. Am I right?

2) I'm supposed to find an algorithm whose time complexity can be described using the given equation. I was thinking of Fast Power algorithm, because it has the same $O(n) = \log(n)$, but it's described differently:

$$\begin{align*}
    T(1) &= 1\\
    T(n) &= T(n/2) + 1 &&\text{when $n > 1$ is even}\\
    T(n) &= T((n-1)/2) + 1 &&\text{when $n > 1$ is odd.}
\end{align*}$$


texts: Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

texts:
We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently:

$$T(n)=\begin{cases}
0 &\text{ if } n=0,\\
3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.}
\end{cases}$$

Prove that for each $n\in\mathbb{N}_0$: $T(n) \leq 8n^2$

How can I prove such statement? I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach. Any help appreciated


texts:
I have to convert "A = B C + D E + ×" from reverse polish notation to infix. I'm a bit confused because of the equals sign. Is that an operator too?

This is my answer: A = (B+C) × (D+E)
Is this correct or would this be written another way?


texts: What's de minimum DFA that L recognizes?

texts:
If a language L on Σ = {a, b, c}, such that L = {w | #a(w) is even and #b(w) is even and #c(w) is even and | w | is even}. Where #a(w) represents the quantity of a's in w and | w | is the length of the string w. How many states have the minimum DFA that recognizes L?

Help me please!


texts:
I have been given this  Nondeterministic pushdown automata and I need to convert it to deterministic pushdown automata, I have been stuck with this for a while now, I know that there cant be transitions where the pda doesnt read anything from the stack but i dont know how to solve this.

Thanks in advance!


texts: Is it incorrect too say that this function problem cannot be in $FNP$?

texts:
Decision Problem:
Is $2^k$ + $M$ NOT a prime?
$K$ and $M$ are our inputs represented as integers.
Function Variant: Output the result of $2^k$ + $m$
We can consider, $M$ = $0$.
Proof that calculating 2^n requires an exponential amount of digits as the result
Question
Is it true that a non-deterministic machine cannot output $2^n$ (exponential) digits in polynomial time?
Does this mean that the problem is not in $FNP$?


texts: Prove Halting on all Inputs is not in RE simulation

texts:
I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine that the halting problem receives as input) on w(the word received as input) for n steps.

Can somebody explain to me who is n and why do we need to simulate M for n steps? Why not only once?

For proving that halting on all inputs problem is not in RE, the complement of halting problem is used. Supposed we take M(w) as the turing machine used for halting problem, I get the next simulation:

M'= simulate M(w) for n steps;
        if M(w) halts, make it loop
        else, stop.

I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

N stands for the length of the word. I don't understand the simulation for a number of steps. Why is that?


texts:
I saw a Computerphile video explaining how a simple circuit could store memory using some logic gates.

However, I couldn't wrap my mind around
 how one could find the value of q if one needs not, which in turn needs q, etc.

EDIT:
q is the output of a logic gate and at the same time the input of another logic gate. not q is also an input and an output.


texts:
Lets $L_z \ := \{ a^i b^i c^i : 0 \leq i < z \}$

$\{a,b,c\} \in \sum^*$

there is a DFA with $\frac{z(z+1)}{2}+1$ states - How can I prove this?

And I need largest possible number $n_z$, for which i can prove that every NFA, which accepts $L_z$, have $n_z$ states, at least!

But first I need to show that $n_z = \frac{z(z+1)}{2}$
 right?


texts: Number of nodes of a parse tree when the Grammar is in CNF?

texts:
There happened to be a following question -

  In any Chomsky Normal Form grammar $G$, how many nodes will all parse trees for terminal strings of length $n>0$ generated by G have?

I tried for some examples & arrived at the answer $2^{n}+1$ but it is incorrect & obviously trying examples is not a sophisticated way. The correct answer given is $3^{n}-1.$ Can anyone explain how this answer comes?


texts: Decidability of a problem concerning polynomials

texts:
I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite exact representation of these polynomials). If needed, we may suppose that the degree of both polynomials is equal. Let us denote by $x_p$ (resp. $x_q$) the greatest absolute value of some (real or complex) root of the polynomial $p$ (resp. $q$). Is the property $x_p = x_q$ decidable?

If not, does this property hold for some restricted families of polynomials? In the context from which this problem arises, the polynomials are characteristic polynomials of matrices, and their roots are eigenvalues.

I am aware of some numerical algorithms for computing roots of polynomials / eigenvalues, however these seem to be of no use here, since the output of these algorithms is only approximate. It seems to me that computer algebra might be useful here, however, unfortunately, I do not have almost any knowledge in that field.

I am not searching for a detailed solution to this problem, however any intuition and ideas where to search for the solution would be helpful.

Thank you in advance.


texts:
Prove that the following language is not a regular language:
$L = \{ 0^x1^y | x, y \geq 1\text{ and } x \geq y\vee (x < y \wedge y \mod x = 0)\}$
Is there anyone to prove this ?


texts: For each vertex of a tree count vertices closer than a specified value

texts:
We have a weighted tree of $n\leq 10^5$ nodes, and for every node $v$, value $L(v)$. The goal is to calculate, for every vertex $v$, number of vertices $u$ such that $\mathrm{dist}(v,u)\leq L(v)$. This is a task from a programming contest. Judging by the limit on $n$, and also specifics of time limits on this contest, the desired complexity should be close to linear, i.e. $O(n \log n)$.

If the tree was rooted, and we were asked to count vertices $u$ that are also in a subtree of $v$, then the task could be solved by in-order traversal and a segment tree. However, this doesn't seem to help with this more general problem.


texts: Structure for getting $| \{ a,b \} \subset S : a+b \le d|$ in O(1)

texts:
I am struggling with exercise from the old algorithmic exam:
$d$ is const for the whole structure.
Propose a structure for which you can do:

Init(S) //called only 1 time
Insert(x, S)::  $ S := S \cup \{x\}$ in O(log(|S|)
Delete(x, S):: $ S := S \setminus \{x\}$ in O(log(|S|)
Get(S) = $| \{ a,b \} \subset S : a+b \le d|$  in O(1)

I am trying to that with AVL Tree with additional members like number of nodes such that $v.value+u.value \le d$.
 Could somebody give me some hint?


texts: How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)?

texts: Let's say I have to do n jobs, and each job can be done at or after a time T(i) (1<=i<=n). And we have 1 machine and the machine takes a time M to do any job whatsoever. The machine once started can be used again only after it's job is done. What's the optimal way to schedule these jobs on the machines?


texts: Encoding the sequence 0110 and determining parity, data bit and value

texts:
I've been struggling with several Hamming code/error detection questions because the logic behind it doesn't seem to make sense.
eg.1

eg.2

I don't really understand the above two examples and the calculations taking place.
How were the conclusions reached concerning the categories of bin position (dec/bin), parity/data bit and value in e.g 1?
Secondly I don't understand the process taking place in e.g. 2 at all. Does it follow that:

General rule: For any code C,

errors of less than $d(C)$ bits can be detected,
errors of less than $d(C)/2$ bits can be corrected.

Definition: A code C with $d(C) \geq 3$ is called error-correcting.

If this is correct then how would I put it into practice. Would really appreciate some assistance!


texts: Recursive-descent parser for the grammar S -> S(S)S | ε

texts:
I'm studying (for self-betterment - I don't go to school) the 2nd edition of Compilers: Principles, Techniques and Tools by Aho et al. I'm not sure how to do Exercise 2.4.1 (b), which is to construct a recursive-descent parser, starting with the grammar:

$S\to S(S)S \mid \epsilon$.

It seem to me that the simpler grammar

$S\to (S)S \mid \epsilon$

can generate the same language as the given grammar, and if that's the case, I can construct a parser for it in a similar manner to the example that was shown in the previous section, without difficulty. Is that the right approach? (Keep in mind that I'm only in chapter 2, at around page 70 of this 1000+ page book, so the solution shouldn't be too "advanced".)


texts:
I came across the following problem in a exam.

We choose a permutation of n elements $[1,n]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ initially. Now during our inspection if we see a smaller value than MIN, then MIN is updated to the new value.

For example, if we consider the permutation,

$$5\ 9\ 4\ 2\ 6\ 8\ 0\ 3\ 1\ 7$$
the MIN is updated 4 times as $5,4,2,0$. Then the expected no. of times MIN is updated?

I tried to find the no. of permutations, for which MIN is updated $i$ times, so that I can find the value by $\sum_{i=1}^{n}iN(i)$, where $N(i)$, is the no. of permutations for which MIN is updated $i$ times.

But for $i\geq2$, $N(i)$ is getting very complicated and unable to find the total sum.


texts: Theory of Turing machine which outputs Turing machine?

texts:
I understand the notion of the universal Turing machine ($U$), which receives a pair of Turing machine ($M$) and an input to $M$ ($x$). If $M$, which obtains $x$, outputs $y$, $U$, which obtains $(M, x)$, outputs $y$ as follows:

$M: x \mapsto y \\
U: (M, x) \mapsto y$

My question is whether there is a theory of another type of Turing machine where the output (not input) of Turing machine is another Turing machine like:

$U': x' \mapsto M$

I guess a program which generates another program can be regarded as this kind of Turing machine $U'$. If so, automatic code generator and machine learning algorithm might be regarded as this type of Turing machine.

(Maybe, brains of human programmers can be modeled using a theory of such Turing machines because a source code seems a form of Turing machine.)


texts: Why S=1, R=1 Is forbidden in RS-Flip Flop

texts:
I have come across about RS Flip Flop & I have tried implementing that on a simulator & using actual logic gates. But I'm still not sure whether I have correctly understood the case unstable or the forbidden case S=1, R=1 in Flip flop. Can anyone tell me what exactly is that?

By the way I have used 2-INPUT NAND Gates to implement the flip Flop. What is the difference between the NAND Gate Flip Flop & NOR Gate Flip Flop, ?


texts: Is it legal to use non-terminal twice in Backus-Naur grammar

texts:
It's a school assignment:
The problem is:
Write a BN grammar for +67.

The given solution I have been given is following:

<digit>  ::= 6 | 7
<number> ::= <digit> | <digit> <number>
<+67>    ::= + <number>

My question is, when given this simple task, could it be derived like this?

<digit>  ::= 6 | 7
<number> ::= <digit> <digit>
<+67>    ::= + <number>

More precisely, can I use same non-terminal twice in same rule?


texts: Computing every possible sum of integers taken from different sets

texts:
I'm trying to proove $NP$-membership for a problem from the following certificate.
I have $n$ sets of integers :
$$(S_i)_{i \in \{1,\dots,n\}}$$
Each set has a number $m_i$ of integers.
I make "combination" from those sets by taking at most one element in each set.
A "combination" has between $0$ and $n$ elements (assuming sets are not empty).
A "combination" has a value : the sum of its elements.
I have to compute the sum of every possible "combination" values,
and look if it is greater than a given value.
An analytical formula would be nice, but I'm not sure it exists.
Otherwise, do you think this sum is easily computable ?


texts: Knapsack problem with diminishing prices

texts:
I wonder if the knapsack problem with diminishing prices is already studied?
The problem is similar to the regular knapsack problem, except the price of each item is a decreasing function of the total size of the already selected items.

Given $n$ items each with size $s_i$ and price $v_i(s)$, where $s$ is the total size of the already selected items, a size limit $S$ and a total price $V$, we want to find a sequence of items $\langle e_1,\cdots,e_k \rangle$ so that $\sum_{i=1}^k s_{e_i} \le S$ and $\sum_{i=1}^k v_{e_i}(\sum_{j=1}^{i-1}s_{e_j})\ge  V$.

The problem is obviously at least as hard as the regular Knapsack problem (i.e., weakly NP-hard). I wonder if the problem is any harder? Can the dynamic programming solution for the regular problem be used for this problem as well.


texts:
If I understand correctly, $\mathsf{NC}^0$ reductions are taken as the formalization of the concept of "local" reduction, i.e., a reduction that acts locally on substructures of the instances of the problem to be reduced: they map fixed-size "gadgets" of the source problem to fixed-size structures of the target problem.  It is my (hopefully correct) understanding that this kind of reductions occur ubiquitously in structural complexity theory.

An example: to reduce CIRCUIT VALUE to MONOTONE CIRCUIT VALUE (or MCV), one applies the following local transformations, which "double" every gate and every input (see e.g. Cook and Nguyen's Logical Foundations of Proof Complexity, proof of Theorem VIII.1.7, or slide 6 of this):
$$
\begin{align*}
a &\mapsto (a_+,a_-) \\
0 &\mapsto (0,1) \\
1 &\mapsto (1,0) \\
\lor(a,b) &\mapsto (\lor(a_+,b_+),\land(a_-,b_-)) \\
\land(a,b) &\mapsto (\land(a_+,b_+),\lor(a_-,b_-)) \\
\lnot(a) &\mapsto (\land(a_-,a_-),\land(a_+,a_+))
\end{align*}
$$
After applying this transformation, we obtain a monotone circuit with $2$ outputs, call them $o_+$ and $o_-$, such that the value of the output $o_+$ is exactly the value of the original circuit ($o_-$ is its negation). To obtain an instance of MCV (a circuit with only one output), one simply projects on $o_+$, which means plugging a constant (i.e., independent of the original circuit) $2$-input, $1$-output circuit to the outputs of the circuit obtained above.

The whole operation is obviously in $\mathsf{NC}^0$, because bounded-depth circuits can not only implement the local transformation above (taking gadgets to substructures) but can also add arbitrary "constant" substructures (in this case, circuits), where "constant" means depending only on the size of the source instance.

I am interested in reductions which are, so to speak, "purely functorial", in the sense that they map gadgets to substructures but are not allowed to add any "constant".  In the above example, the first part of the reduction would be functorial, whereas projecting on the $o_+$ output breaks functoriality.  My question is:

  Have "functorial" reductions ever been considered and, if so, under what name and for what purpose?

(The term "functorial" comes from the identity $F(f\circ g)=F(f)\circ F(g)$ which is at the basis of the definition of functor. If one sees problem instances as freely built out of basic gadgets, then functoriality means exactly "gadget to substructure". One could also say "homomorphic". Another analogy may be made with linear algebra: functorial reductions would be linear maps wheras $\mathsf{NC}^0$ reductions are affine maps).

I am pretty sure that "functorial" reductions are too restrictive to be of general interest.  For instance, I do not see how CIRCUIT VALUE could be $\mathsf P$-complete under such reductions. However, the variant of CIRCUIT VALUE in which one asks for the value of a specified output out of possibly many, would still be $\mathsf P$-complete (this "multi-output" variant is of course equivalent to CIRCUIT VALUE under $\mathsf{NC}^0$-reductions), as well as the similar variant of MCV.  So the notion is not completely void of significance.  Also note that "functorial" reductions are incomparable w.r.t. projections: they are more general in one sense (the local dependence is not necessarily "bitwise") but more restrictive in another (projections are still allowed to add arbitrary substructures, i.e., break functoriality).


texts: What determines valid and invalid turing machines?

texts: According to my understanding, a Turing machine that's valid has to have finite steps to finish a certain step. If this is right, what else determines the validity of a turing machine?


texts: What is the time complexity of a binary multiplication using Karatsuba Algorithm?

texts:
My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity.

In general, the Karatsuba Multiplication is said to have a time complexity of O(n^1.5...).
The algorithm assumes that the addition and subtraction take about O(1) each. However, for binary addition and subtraction, I don't think it will be O(1). If I'm not mistaken, a typical addition or subtraction of two binary numbers takes O(n) time.

What will be the total time complexity of the following program then that multiplies two binary numbers using Karatsuba Algo that in turn performs binary addition and subtraction?

long multKaratsuba(long num1, long num2) {
 if ((num1>=0 && num1<=1) && (num2>=0 && num2<=1)) {
   return num1*num2;
 }

 int length1 = String.valueOf(num1).length(); //takes O(n)? Not sure
 int length2 = String.valueOf(num2).length(); //takes O(n)? Not sure

 int max = length1 > length2 ? length1 : length2;
 int halfMax = max/2;

 // x = xHigh + xLow
 long num1High = findHigh(num1, halfMax); // takes O(1)
 long num1Low = findLow(num1, halfMax); // takes O(1)

 // y = yHigh + yLow
 long num2High = findHigh(num2, halfMax); // takes O(1)
 long num2Low = findLow(num2, halfMax); // takes O(1)

 // a = (xHigh*yHigh)
 long a = multKaratsuba(num1High, num2High);

 // b = (xLow*yLow)
 long b = multKaratsuba(num1Low, num2Low);

 //c = (xHigh + xLow)*(yHigh + yLow) - (a + b);
 long cX = add(xHigh,xLow); // this ideally takes O(n) time
 long cY = add(yHigh,yLow); // this ideally takes O(n) time
 long cXY = multKaratsuba(cX, cY);
 long cAB = add(a, b) // this ideally takes O(n) time
 long c = subtract(cXY, cAB) // this ideally takes O(n) time

 // res = a*(10^(2*m)) + c*(10^m) + b
 long resA = a * (long) Math.pow(10, (2*halfMax)); // takes O(1)
 long resC = c * (long) Math.pow(10, halfMax); // takes O(1)
 long resAC = add(resA, resC); // takes O(n)
 long res = add(resAC, b); // takes O(n)

 return res;
}


texts: alphabet of a single tape turing machine that simulates a multitape TM

texts:
First of all sorry, if this question already exists, in that case, pointing to the right direction will be appreciated.

Secondly, sorry, if the question is below the expected level of Niveau, but all help appreciated.

In the textbook by J. Hromkovic, named "Theoretical Computer Science, Introduction to Automata, Computability, Complexity, Algorithmics", in Page 110, in the 2003 edition, i note that the alphabet of a single tape TM which simulates a multitape TM is given by

$$
\Gamma_{single\ tape} = (\Sigma_{multi\ tape} \cup \{¢,␣ , $ \})\times \{\uparrow , ␣ \} \times (\Gamma_{multi\ tape}\cup\{ ␣,\uparrow\})^{k} \cup \Sigma_{multi\ tape} \cup \{¢\}
$$

should that not be, instead:

$$
(\Gamma_{multi\ tape} \cup \{¢,␣ , $ \})\times \{\uparrow , ␣ \} \times (\Gamma_{multi\ tape}\cup\{ ␣,\uparrow\})^{k}  \cup \{¢\} ?
$$

according to the book, the single tape TM splits its tape in "tracks" , see image i scanned from the book: http://imgur.com/CwnyS

because, the last $¢$ is the primary left end marker, the first two terms of the Cartesian product series is responsible for the top two track, the rest $k$ tracks are constructed by the term which has k in exponent.

all help is appreciated. sorry for the dummy question. i am a meteorologist, who takes his past time in computer programming.

ps, i can neither embed (is that the correct term?) the ¢ character by \cent nor the ␣ by \textvisiblespace in a post like this. does stackexchange use a different command for those? thank you


texts: Expressing the language of squares as a concatenation of two languages

texts: Can the language $L = \{ vv : v \in \Sigma^* \}$ be expressed as the concatenation of two nontrivial languages? (A language is nontrivial if it differs from $\{\epsilon\}$.)


texts: What are thin-core and fat-core processors

texts:
I am reading a paper called Back to Thin-Core Massively
Parallel Processors by Ami Marowka (Computer, 44(12):49–54, 2011; IEEE Xplore).

However I have a question about the title of the article: what does "thin core" (and for that matter, "fat core") mean?

Thank you!


texts: Relation between digraph and NP-Complete problem

texts:
Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem.
If we consider this problem for instance:
Input: A digraph $G=(V,E)$ and two nodes $u,v \in V$
Question: Is there a path in $G$ from $u$ to $v$?
Can we say this problem is NP-Complete problem since the digraph have only two nodes that they have a path from one another and this makes it be a Hamiltonian Path. Hints are appreciated!


texts: Searching for a string of numbers in a large digit sequence

texts:
How would one search for a string of digits in a large digit sequence? For example, I'd like to search for 351814 in Euler's number. I'm not too keen on computer science, I'm a pure math major, so I don't really know how to begin. I also wouldn't know how to run said code.

Any help would be greatly appreciated.


texts: How can random array access be considered $O(1)$ if bits must be stored in space and light travels at finite speed?

texts: Bits are usually stored linearly in space. We can say, thus, that the length of a memory chip, for example, is linearly proportional to the number of bits it can hold. Since signals must travel at finite speed in our universe, the time it takes to read the last element an array will always be proportional to the length of the array. Am I missing something?


texts: While converting from NFA to DFA why 2^n states

texts:
folks.

Hope you all doing well. I have a question regarding to the topic Equivalence of NFA and DFAs.

While converting from NFA to DFA why we always say we'll have 2^n states, and should it be always 2^n ?

Thanks in advance.


texts: Distributed consensus feasibility from graph structure

texts:
Consider a consensus process in which participants

Initially take a position
Receive positions only from their neighbors
Accept a new position that is a super-majority of neighbors positions.

Under what conditions is it possible for any participants to accept different new positions, regardless of whether they are neighbors?

More formally, consider a connected directed graph $G=(V,E)$ where vertices represent participants, and the  in-neighbors of a vertex $N(v) = \{u : (u,v) \in E\}$ represent the peers participant $v$ listens to.

Suppose there are $1,\ldots, K \leq |V|$ distinct positions and each node initially takes one position; i.e. $p(v,k)= 1 $ if node $v$ takes position $k$ and is 0 otherwise.

Each node tabulates the position votes of its neighbors and itself

$$o(v,k) = \frac{1}{|N(v)|+1}\left(p(v,k) + \sum_{u\in N(v)}p(u,k) \right)$$

From these votes, a node accepts a new position if $o(v,k) > t$.  It takes no position if $o(v,k) \leq t \forall k$.  Assuming a threshold $t > 0.5$, there can be at most one $k$ such that $o(v,k) > t$.  Let $f(v) \in \{0,\ldots,K\}$ be the accepted position of node $v$, with $0$ indicating the no accept case.

I'm interested in exploring how the properties of $G$ and the value of $t$ impact when it is possible for disagreement in the final outcome $f(v) \neq f(u) \neq 0$ for at least one pair $u,v$.

If the graph is fully connected, the peers must agree since they perform the same operation.  If the graph is not connected, then the independent components don't communicate and can clearly diverge.

I've struggled formulating this as a feasibility test for a binary linear program, but haven't figured out a way to use the structure of this problem to make it tractable.


texts: Is there a research name for "systems that steadily grow in complexity as they are computed"?

texts:
I have an intuitive concept of systems that grows in complexity steadily as it computes. I can think in some examples:

Nature. Given the physical laws, some initial conditions (say, the Earth planet at the beginning of life) and enough time, the system eventually evolves in complexity, all the way from dinosaurs fighting over territory to humans building castles.
Cellular automatas. Given a set of automata rules, some initial conditions (a grid with specific cells set) and enough time, some automatas eventually evolve complex structures.
AI applications such as genetic programming (to some extent). The issue is that most of those evolve towards a specific goal and often reach a tipping point and stop.

The kind of system I'm talking about is supposed to grow in complexity indefinitely. That is, one can expect that, given enough time, such system will eventually develop complex structures such as "lifeforms" that defend their own existence. It is also not goal oriented, it is supposed to grow in complexity because their own internal structures are more stable when they are more complex. We know nature/physical laws satisfy that criteria, but I'm not sure about cellular automatas and genetic programming. That is a very vague concept and hard to define (there is no accepted definition of complexity, after all). Yet, is there any name/formalization for this kind of system? Do we know any examples of systems/specific automatas that, as far as our observation goes, never reach a "tipping point" where they stop becoming more complex?


texts: How does the cpu know which process to wake?

texts:
In general, my understanding is: the cpu is executing a process/thread until either it is interrupted, the scheduler kicks it out, or it's waiting for something else (I/O for example), when it's put in different queues (ready, waiting, etc). (Correct me if I'm wrong)

My question is, when one process is waiting information from another process (I guess, sleeping until a signal for it has been received). How does the cpu know how to wake that process? When it receives the signal will it be attempting to wake up all the processes with it? Is it marked somehow which processes are expecting which signals? What if the interrupt doesn't have this process id, but a general message to which the process is the only one waiting for it?

I've been trying to find a concrete response and read:
https://learning.oreilly.com/library/view/operating-system-concepts/9781118063330/10_chapter03.html#chap3
https://medium.com/cracking-the-data-science-interview/how-operating-systems-work-10-concepts-you-should-know-as-a-developer-8d63bb38331f

Thanks in advance!


texts: Numbers of ways of expressing the sum of a number between [a,b]

texts: I need an algorithm to calculate the number of ways of expressing a number N as sum of numbers inside the interval [a, b]


texts:
We defined the class $\text{DP}$ like this:

$$\text{DP} := \{ A \setminus B : A, B \in \text{NP} \}$$

We say a problem $P$ is $\text{DP}$ complete iff $P \in \text{DP}$ and $X \leq P \forall X \in \text{DP}$, meaning that every language $X \in \text{DP}$ can be reduced to $P$ in polynomial time.

For a particular problem (which I do not expect you to solve, so I won't explain all the details), I already proved that $P \in \text{DP}$, but I do not know how to continue. Also, I could not find more information about this class.

Could someone give me a hint how to start such a proof or point me to further information about this complexity class which might help me to achieve it?

Edit: The definition is from a lecture about complexity of algorithms. The task is to prove that

$$\text{SAT-UNSAT} = \{\, (F,G) : F \text{ is satisfiable}, G \text{ is not}\, \}$$

is DP-complete. I proved that $\text{SAT-UNSAT} \in \text{DP}$, but I failed to prove the completeness.


texts: Average number of comparisons for a successful search of a prime number in a binary search tree

texts:
A binary search tree is constructed by inserting the following value sequentially:
$$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$
Let $p_v$ be the probability to search for the value $v$ in the binary search tree (for $1\leq v\leq10)$.
$p_v = \frac{1}{25}$ if $v$ is an even number and $p_v = \frac{1}{10}$ if $v$ is an odd number. Determine the average number of comparisons for a successful search of a prime number in a binary search tree.

I know that I have to calculate the expected value, but I don't know where to start. Any help to solve this problem is greatly appreciated.
This is what I have tried:

To search for number 3, it takes 1 comparison.
To search for number 7, it takes 5 comparisons.
To search for number 2, it takes 3 comparisons.
To search for number 5, it takes 5 comparisons.

So the average number of comparison to search for a prime number is:
$$\frac{1+5+3+5}{33} = \frac{14}{33}$$


texts: It's necessary to replace all the population each generation in a genetic algorithm?

texts:
I'm creating a timetable generator using GA's, and I'm stuck in the crossover part.

Each generation, I just basically copy the best individuals (the 50% fittest individuals inside the population), and perform my crossover operator between them.

I'm using a 2 point crossover. I represent all my TT courses as a List. Each course has an assigned teacher, and an assigned position. The position is the index inside a 2D array. The first dimension represents times and the second represents classrooms.

When I perform the crossover, I choose a middle point inside the Course's list of each parent. Then I create 2 individuals mixing this Course's. If there are overlaps or other constraint violation, I repair the new individual.

My question is this, How can I ensure an optimal offspring?

Sometimes after the crossover and/or after the repair, the new offspring is not better than his parents. This makes the population gets stuck in high fitness values (I'm minimizing the errors, so, a low fitness score means a good individual), so, the GA never reach an optimal solution.

I've been reading an article about copy the fittest individuals in to the next generation, then perform the crossover, but I don't know if this is correct.


texts: Efficient method for finding 1's in binary representations

texts:
Say I have a binary number of N bits, and I need to find every combination that have M 1's. For example, if N = 3 and M = 1, then 100, 010, 001 are the allowed combinations. I have read that a more efficient way of finding these combinations for large N is by dividing the bits into two halves, and then combining combinations from each half such that the total number of 1's is M. For example, if N = 3 and M = 2, and we divide the bits into lengths of two and one, the half with one only has the combinations 0 and 1, while the half with two have the combinations 00, 01, 10, 11. 0 can only be combined with 11, and 1 can only be combined with 01 and 10. Thus the only total combinations are 011, 101, and 110.
Why is this method more effficient?


texts: State complexity of homomorphisms of regular languages

texts:
Given a DFA $A = (Q, \Sigma, \delta, q_0, F)$ with $n$ states and a homomorphism $h: \Sigma \to \Gamma^*$. It is easy to see that the family of regular languages is closed under homomorphisms using regular expressions or by construction of a grammar.

My problem now is to analyze how many states are needed for a DFA $A' = (Q',\Gamma, \delta',q_0',F')$ to accept $h(L)$. First of all I tried to think of a basic construction method to get the automaton.

Let $a \in \Sigma$:

If $h(a) = \varepsilon$ then all the transitions of $a$ in $A'$ can be removed.
If $|h(a)| = 1$ then all the transitions with $a$ can be replaced with $h(a)$.
If $|h(a)| \geq 2$ then the transition of $a$ in $A'$ has to be replaced with $h(a)$ and split into $|h(a)|-1$ states each with a one symbol transition

a. If the prefixes of two unique symbols of $\Sigma$ do not share the same prefix then the resulting automaton can be extended into a DFA without adding any states(?).

b. If prefixes are shared then the resulting automaton would be an NFA, therefore it has to be converted into a DFA (using power set construction) and minimizing it.

Therefore my estimation for the state complexity in case $3a$ would be:
$$\begin{align*}|Q'| &\leq |Q| + |Q|\cdot\left(\sum_{a \in \Sigma} |h(a)| - 1\right)\\ &= |Q|\cdot(1- |\Sigma|+\sum_{a \in \Sigma} |h(a)| )\end{align*}$$

However, I'm not convinced about my construction as mentioned in step 3 and was not able to find an example of a language where the upper boundary is met. Therefore I'd be happy to see any advices.


texts: How do i prove that Is {$↔,⊕$} not a complete set  ? I have no clue how to prove it .


texts: Period of a pseudo-random sequence generated using an LFSR

texts:
I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR).
I have read from many sources that the length of the pseudo random sequence generated from the LFSR would be maximum if and only if the corresponding feedback polynomial is primitive.

I have tried to generate the pseudo random sequence for the primitive polynomial (4,1,0) (corresponding to polynomial $x^4 + x + 1$) by tapping at bits 4 and 1, and it has resulted in a sequence with a period of $2^4$ - 1 = 15. Similarly I have tried primitive polynomial given by (3, 1, 0) (corresponding to polynomial $x^3 + x + 1$) by tapping at bits 3 and 1 and it has resulted in a sequence of period $2^3$ - 1 = 7.

When I tried to apply this same logic to the primitive polynomial (5, 2, 0) (corresponding to polynomial $x^5 + x^2 + 1$) it yields a sequence with period 15. While it should have yielded a sequence with period 2^5 -1 = 31. Following is the circuit diagram for (5, 2, 0)

1) What is the exact procedure to convert the given polynomial into a maximal length LFSR?

2) How do I determine the correct tap bits for a given polynomial?


texts:
Can't seem to answer these questions, I'm sure the answers are out there somewhere but I don't really know what keywords to use to find them. Any answers or good sites/ documentation would be much appreciated. And please don't say wikipedia, the language used is a bit out of my comprehension at this moment.

Is it correct to assume that an NFA can be converted into multiple
versions of a DFA?
Are there different methods for doing so and would they all be
considered correct assuming they give different answers?
If an NFA has the transition relation d{ (q0,e,q1), (q1,e,q1),
(q1,e,q2) } would it be correct to write it out as d(q0,e,q2)?
(e standing for epsilon, q0 being initial state and q2 being final)
Is it correct to assume that every state in an NFA has a "hidden" e
transition? Essentially can you assume that every state in an NFA has an e* transition.
Is it bad practice when converting to have multiple NFA states as one
DFA state?

Alternatively is there some way I can test my conversions out and make sure they are correct either using a program or some other way.

Apologies for the noobiness of the questions.


texts: Retroactively ordering actors' concurrent activity on disjoint sections of a data-structure

texts:
Hi! I'm new here, a terrible computer-scientist, and have no idea what I'm doing; I'm more expecting / hoping for links to research on algorithms or data-structures that contribute to problems like this, than a straightforward answer (I don't even know how to properly ask the question.)

In some programming-language work of mine, I've got a ginormous, homogenous, directed graph, on disjoint subgraphs of which multiple actors operate concurrently.

One such operation is to add an element to an ordered set, supplicants, on a given node (it's a behaviour to declare “I'm waiting for write-access to this structure”, basically.) That membership is cascaded through the graph to some extent (i.e. adding an element to $a$'s supplicants, when $a⇸b$, places that same element in $b$'s supplicants as well.)

Now, normally, in my situation, the above bit where these two subgraphs are disjoint is guaranteed — at the time. However, there's an edge case¹ where two such subgraphs both have different values added to supplicants while disjoint, and are then joined. In this situation, I'm not sure how to deterministically order the two sets of supplicants amongst one-another.

I've heard of things like vertex clocks that I'd hoped might help with this, but after looking into it a bit today, none of the mechanisms I'm aware of are very helpful in this situation. The actors are unaware of eachother working ‘adjacently’ (or soon-to-be-adjacently, when they're joined). To make them aware of eachother would defeat the point (i.e. if participant $\text{foo}$ had to walk over (all|most) of the graph leaving supplicants hints that currently-working-disjoint-but-maybe-someday-not participants could find, and order themselves against, would be as pointless as just having a single globally-locked set shared amongst all threads); so I'm looking for some sort of lockless algorithm or distributed-systems solution for them to collaborate without(?) explicit communication.

(i.e., all of programming. :P)


texts: Is There a Complete Problem for the Class of Turing Decidable Problems?

texts:
Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is  trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes inbetween $\text{ELEM}$ and $\text{REC}$. They present complete problems for these classes under specifically crafted reductions.

Are there complete problems for $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ (aka $\textsf{REC}$) relative to weaker reductions? Turing reductions are inappropriate because they are capable of doing all the work. Should we expect such reductions to be contrived or not so (e.g. many-one reductions that are restricted to primitive recursion)?

[1] Sylvain Schmitz Complexity Hierarchies Beyond Elementary 2013 http://arxiv.org/abs/1312.5686


texts: Pseudo-number generation compared to Blum-Micali

texts:
A few years ago I made a pseudo-random number generator to use in a monte carlo simulation for a lecture in my University.

My instructor ask me why I did that generator instead of using C equivalent rand.

The algorithm is $x_{n+1} = e^{x_n + k} \mod 1$ using float point values with $K$ big enough to contain a complete cycle inside $\epsilon$ (a very small value).

Yesterday I find another PRNG using a similar formula: Blum-Micali algorithm

$x_{n+1} = g^{x_n} \mod p$

The answers are... could my algorithm be based on the Blum-Micali one?

Could my algorithm contain the Blum-Micali properties?

Thanks in advance.


texts:
$STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$
$Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$

I've tried the following proof:
Let $S\in NL$, and let $S^\complement \in coNL$. ($S^\complement$ complement is $S$)
Let $M_S$ be the NDTM  that solves $S$.
$x\in S \iff x\notin S^\complement$, so If I can decide membership in $S^\complement$, I can decide membership in $S$. Then I claim that $x\in S^\complement \iff(G_x,v_0,v_{acc}) \in Co-STCON$, where $G_x$ is the configuration graph of $M_S(x)$, $v_0$ is starting configuration, and $V_{acc}$ is a single accepting configuration.

The problem I have with the proof above is that it has the form $x\in S \iff (G_x,v_0,v_{acc}) \notin Co-STCON$, so I feel like I'm missing something essential here. Is it correct?


texts:
I have a quick question on implementing the Bhandari algorithm.  I do not have the textbook where the algorithm is originally given (Bhandari, Ramesh (1999). Survivable networks: algorithms for diverse routing), and the online resources I've found are a little ambiguous on this point...

Say I want to obtain k disjoint paths.  I run the algorithm k times and get P1, P2, P3, ..., Pk paths.  I then look through these paths and remove edges that 'overlap'.  The ambiguity is once I find an overlap, do I completely neglect that edge, or, do I alternate including it/excluding it based on the number of times the edge is traversed?  i.e) if an edge is travered once: include, twice: exclude, 3 times: include, 4 times: exclude, etc...

One additional question.  Can I run the algorithm k times, and do the edge exclusion once at the very end on all Pk paths, or do I have the modify each path as it is created.  The paper I found (Iqbal, F. and Kuipers, F. A. 2015. Disjoint Paths in Networks. Wiley Encyclopedia of Electrical and Electronics Engineering. 1–11.) suggests I need to modify the path edges as I create the paths, but from what I can tell about the algorithm it seems like I can just exclude the edges once at the very end.  Thanks!


texts: Is $\{a^nb^m \mid n,m\ge 0, n\ne m\}$ regular or not?

texts:
Possible Duplicate:
  Prove that the complement of  $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

Is $L=\{ a^nb^m \mid n,m \ge 0, n\ne m\}$ a regular language?

I think it is but can't prove it.


texts: Merging two splay trees whose ranges may overlap in $O(\log N)$

texts:
I have two splay trees, $A$ and $B$.

When every element in $A$ is smaller than every element in $B$, we can merge them in $O(\log N)$.

My question is; when all elements of $A$ are not necessarily smaller than all elements of $B$, how can we still merge $A$ and $B$ in $O(\log N)$?

What I have already tried:

Splay $A$'s largest element, splay $B$'s smallest element. The root $R_A$ of $A$ doesn't have a right child anymore, and the root $R_B$ of $B$ doesn't have a left child anymore. Compare $R_A$ and $R_B$. If $R_B$ is bigger than $R_A$,  make $R_B$ the right child of $R_A$, which fails when $R_A$ is larger than $R_B$.


texts: How can I check constraints on my state machine behaviour?

texts:
My background is fairly practical rather than theoretical, so this question may be a bit basic.

I have a state machine with events, and events may optionally trigger action functions to be called as part of the state transition.  In practice, actions functions do things like lighting LEDs.  The state machine is defined in an in-house domain-specific language, and a tool generates C code from the definition.

I have constraints that need to be satisfied -- eg "when in state A, only LED 1 and 5 should be lit."

What practical techniques are there to check that my state machine design satisfies my constraints?

I considered using Prolog.  If I could enter the side-effects of my action functions, the state machine states, and the valid transitions and action functions, I should be able to query whether the constraints hold true -- is this correct?

Are there other frameworks or tools that could be useful in this situation?


texts:
If one is given $n$ numbers picked uniformly at random from the interval $[0,1]$ then is it possible to sort them in linear time?

It seems to me that some such method exists which uses binary representations of these numbers and compares the sequences of 0s and 1s between any two of them only partially and that somehow is enough!?

What is confusing me is that this somewhere seems to need a source of random bits and that is not clear to me where. How many?

Does one account for the time taken to generate these binary representations?

If the numbers are upper bounded by $n$ then apparently there is some probabilistic way of sorting them in linear time with a success guarantee $\geq 1 - \frac{1}{n^c}$ for some constant $c$.

What is this method?


texts:
I'm currently studying deadlocks and I'm trying to learn myself the bankers algorithm.
In this example my teacher goes to B first, then C and finally A.
He adds (I think) 2 (row b, Has) with 3 (free) and then gets the new Free value 5.
After that he proceeds to row C where he adds 2 (row c, Has) with the free value 5 which gives us a new free value of 7.
After this he goes to the last row A and adds 3 to seven which gives him the free value of 10.
This does not cause a dead lock and I'm wondering why, Isn't he over the Max value of row A?

Here is another example in which the first image is included, but there is also one scenario when we get a dead lock. I don't really understand why since we still get 10 free like the rest of the examples.
Sorry if this is a bit confusing. I can simplify if its needed.


texts: Why do some authors not include summation in the $\pi$-Calculus?

texts:
In Robin Milner's book "Communicating and Mobile Systems: the $\pi$-Calculus", on page 87, the set of expressions of the $\pi$-Calculus is defined as

$$P ::= \sum_{i\in I} \pi_i.P_i\ {\huge|}\ P_1|P_2 \ {\huge|}\ \operatorname{new} a P\ {\huge|}\ !P$$

So in Milner's formulation, the summation of processes is included, just as in CCS. However, some authors do not include it: in Mathew Hennessy's book, "A Distributed $\pi$-Calculus", summation is not used (section 2.1 deals with the language, and summation isn't there).

The Wikipedia article on $\pi$-Calculus also doesn't include summation.

Why is summation not included in these descriptions? Was it somehow abandoned because it can be expressed using the other primitives? If so, how would it be done?


texts: Calculating time it takes to download content

texts: I have a network line that runs at a speed of 400kbps. How long do I have to download 6GB.


texts: Why can level-triggered interrupts be shared but not edge-triggered interrupts?

texts:
A key difference between the edge-triggered and level-triggered interrupts is interrupt sharing. Level-triggered interrupts can be shared. Edge-triggered interrupts cannot be shared.

I read the line above in an IBM document. Need help to understand why is it so.


texts:
Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independent of the input i.e. the data access pattern of the algorithm does not leak any information about the input of the algorithm. Some of the algorithms already looked at include sorting, BFS, minimum spanning tree and convex-hull. These data-oblivious algorithms have various applications for the cloud and efficient secure computation.

My question: Is ORAM a generic method to transform any non-data-oblivious algorithm to its data-oblivious counterpart?


texts: Computing the shortest path in a labyrinth

texts:
I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will generate obstacles within the dimensions and randomly spawned. There is one entrance and at least one exit after finding the shortest path. The way to find the exit and shortest path will be in an order of movements. First it checks if going up is available, then left, then right, and finally down (priority movements: up->left->right->down). The movements must be horizontally and vertically, so diagonal moves are illegal, unfortunately.

My thought was to probably build a backtracking algorithm that will solve this problem; but, there is a catch for this. It says the labyrinth will not be more than a billion square, meaning that it can be a larger X and Y. Thus, the program will timeout and have to allocate more memory to execute with a Gigabyte file. So to reduce this amount of memory, maybe use bitfields to reduce and manipulate bitwise (which I never used it as a data structure).

My weak point is to have a strong foundation of how to approach such a problem that can be devastating to code and how to take care. I was wondering what kind of approach I need to consider too. I'm happy to discuss further and be curious about your approaches. I like to ask a lot of questions just for me to understand efficiently.


texts: Conflicting definitions of quasipolynomial time

texts:
The textbook The Nature of Computation uses the following definition of quasipolynomial time:

  A quasipolynomial is a function of the form $f(n) = 2^{\Theta(\log^k n)}$ for some constant $k > 0$, where $\log^k n$ denotes $(\log n)^k$. Let us define QuasiP as the class of problems that can be solved in quasipolynomial time.

So presumably the definition for QuasiP could be written $TIME(\bigcup_k 2^{\Theta(\log^k n)})$. However every other definition I've found on the web, in particular the one from Wikipedia, suggests the alternative definition $TIME(\bigcup_k 2^{O(\log^k n)})$.
Now I can't see how these definitions are supposed to be equivalent. In fact I can imagine that there's a function $f$ that requires $2^{\log n}$ steps for even values of $n$ and $1$ step for odd values of $n.$ $f$ would fail to be in $2^{\Theta(\log^0 n)}$ because of the even values of $n$ and it would fail to be in $2^{\Theta(\log^k n)}$ for any $k > 0$ because of the odd values of $n$. However $f$ is still in $2^{O(\log^1 n)}$.
So apparently such an $f$ is in QuasiP according to the second definition but not according to the first. Did I make a mistake in the reasoning here? And if not am I correct in assuming that the definition in The Nature of Computation is erroneous?


texts: Why are transcendental functions of large numbers inaccurate on computers?

texts: For instance, why is it hard to accurately compute sin(1e99)? I suspect it has something to do with rounding error.


texts:
I was going through a past paper question but I don't have any answers to know if I'm working out the problems correctly or not.

I need to find the time complexity for:

i) repeat
      n:=n div 2;
   until n=1;

ii) for i:=1 to n do
       begin
          for j:=1 to n do
             begin
                for k:=1 to n do;
             end;
       end;

iii) repeat
        for i:=1 to n do
           begin
              for j:=1 to n do;
           end;
     n:=n div 2
     until n=1

In my opinion, the answer for (ii) is $O(\log n)$ and the answer for (ii) is $O(n^3)$ but I'm not sure about my answers. Regarding question (iii) I have no idea how to come up with a solution.


texts: NP-hardness of maximum set cover with element-level submodular function

texts:
Consider the following generalization of maximum set cover problem:

Given a collection $C$ of subsets of a finite set $S$.

Find $C^{'} \subseteq C$ of cardinality $k$ that maximizes

\[
\sum\limits_{s \in S} f(s, C^{'})
\]

For example:

If $f(s, C^{'})=\begin{cases}1 & \exists c \in C^{'}, s \in c \\ 0 & \text{otherwise}\end{cases}$,

the problem is essentially maximum set cover and it's NP-hard.

However, if $f(s, \cdot)$ is submodular function, for example:

\[
f(s, C^{'})= \frac{|\{c \in C^{'}  \mid s \in c \}| -1}{|\{c \in C^{'}  \mid s \in c \}|}
\]

Is the problem still NP-hard?


texts: Algorithm for real time Coordinate smoothing

texts:
So I get new Coordinates every 10ms even with RTK fixed precision, they jump between 1-3cm. The Coordinates are the current Position of my Vehicle

I have a Vehicle using these Coordinates to follow a drawn Path.

Now as the Coordinates Jump, the Vehicle tries to follow them and is driving in curves instead of a straight line sometimes more sometimes less depending on how sensitive the steering is.

My question now is, what Algorithm is capable of "smoothing" incoming Coordinates in real-time to avoid the jumping around?

Kalman-Filter / Douglas-Peucker or something else?

Does a prediction of the next current position help? -- Maybe with the help of an IMU?


texts: What is the advantage of seperate chaining over open addressing?

texts:
Hash tables resolve collisions through two mechanisms,

separate chaining or open hashing and
open addressing or closed hashing.

Though the first method uses lists (or other fancier data structure) in hash table to maintain more than one entry having same hash values, the other uses complex ways of skipping n elements on collsion.

Since, while searching, both mechanisms requires looking up for more entries on collision and Seperate chaining may require lesser number of searches to find the match.

What kind of advantages does it have over separate chaining?


texts: What is the name for polynomially solvable optimisation problems?

texts:
An optimisation problem that allows to solve a NPC decision problem through a polynomial reduction is called NP-hard. For these optimisation problems no polynomial algorithm is known.

Symmetrically, is there a standard name for all those optimisation problems for which a polynomial algorithm is known?


texts:
Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?

Thank you for any input.


texts: Dependency graph with general (AND/OR) dependencies

texts:
This is similar to Is there such a thing as an "or" case in a dependency graph?

I am trying to represent a dependency graph where the dependencies for an individual node may be a general boolean function of other nodes.

For example, node A may be reachable from node B or node C.

I can't see how to represent this with a DAG. Is there way to represent general boolean dependencies in a DAG? If there isn't, what other sort of structure should I use?


texts: How to generate a random number in a given range with uniform probability

texts:
I have used programming languages which generate a random number in a given range.

Let's say we have a range of 1 to 10 each number has the probability of 1/10 to get selected. What is the criteria on the basis of which a random number is selected with uniform probability by a programming language.


texts: Can someone give a simple but non-toy example of a context-sensitive grammar?

texts:
I'm trying to understand context-sensitive grammars.

I understand why languages like

  $\{ww \mid w \in A^*\}$
  $\{a^n b^n c^n \mid n\in\mathbb{N}\}$

are not context free, but what I'd like to know if a language similar to the untyped lambda calculus is context sensitive.

I'd like to see an example of a simple, but non-toy (I consider the above toy examples), example of a context-sensitive grammar that can, for some production rule, e.g., tell whether or not some string of symbols is in scope currently (e.g. when producing the body of a function).

Are context sensitive grammars powerful enough to make undefined/undeclared/unbound variables a syntactic (rather than semantic) error?


texts: Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$

texts:
I have been working on the following homework question, and I just can't seem to make any progress:

Construct a finite automaton having fewer than 36 states that recognizes the language $\{s \in a^* : \operatorname{gcd}(|s|, 504) \geq 6\}$, where $|s|$ is the length of $s$.

So far I have been trying to figure out a regular pattern in $504$ and have broken it down to the prime factorization $504 = 2^3 \cdot 3^2 \cdot 7$, which means that all divisors must be multiples of 2, 3, or 7. However I don't know how to create the finite automaton (NFA or DFA). Any help is appreciated!


texts: Markov chain probability in a complete graph

texts:
I'm having a hard time understanding the following. Assuming we have a complete graph with $n$ vertices, where initially, one of those has an information. At this point, all we care about is that in each time $t$ a node that has the information chooses randomly one of it's neighboors and sends it the info, only if the receiver does not have it. We don't care how the sending is done.
Let $x_t$ be a random variable representing the number of nodes that have the info at the time $t$. It is indicated that $x_t$ can be modeled by a homogeneous increasing Markov chain. So, if at $t$, if $k$ vertices have he info, then the probability of another vertex receiving the information (using population protocols), that is, to have $k+1$ vertices know it is $\frac{2k(n-k)}{n(n-1)}$. Can someone explain why this stands?

The link to the paper I got this from is this: https://drive.google.com/open?id=0B0RiUAwpE4vnTlFqWmRHdlRYSFp4aDlYcWE5dWxUdWg2ZDA4
and the transition graph of the chain is shown in Figure 2.


texts: Stable matching with asymmetric arrays (gale shapley)

texts:
I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms.

One of the answer suggested to add 5 dummy students to make number of students equal to 10.

Lets suppose before adding the dummy students the preferences are below -:

s1 - d3 d9 d2 d7 d1 d10 d4 d6 d8 d5

s2 - d8 d2 d3 d5 d10 d4 d7 d1 d9 d6

s3 - d2 d9 d1 d8 d4 d3 d10 d6 d5 d7

s4 - d9 d6 d2 d5 d8 d1 d3 d7 d4 d10

s5 - d10 d2 d5 d4 d3 d7 d9 d8 d6 d1

d1 - s1 s5 s3 s4 s2

d2 - s2 s3 s1 s5 s4

d3 - s3 s5 s4 s1 s2

d4 - s3 s5 s4 s2 s1

d5 - s2 s5 s3 s1 s4

d6 - s3 s4 s5 s1 s2

d7 - s2 s4 s5 s1 s3

d8 - s3 s5 s1 s4 s2

d9 - s2 s5 s3 s1 s4

d10 - s5 s2 s1 s3 s4

How should I go about this after adding the dummy students. My approach is below -:
I am putting 5 dummy student in lower preference for dorms and giving random dorms preference to dummy students. Dummy students are denoted by ds.

s1 - d3 d9 d2 d7 d1 d10 d4 d6 d8 d5

s2 - d8 d2 d3 d5 d10 d4 d7 d1 d9 d6

s3 - d2 d9 d1 d8 d4 d3 d10 d6 d5 d7

s4 - d9 d6 d2 d5 d8 d1 d3 d7 d4 d10

s5 - d10 d2 d5 d4 d3 d7 d9 d8 d6 d1

ds1 - d6 d2 d9 d10 d4 d5 d3 d1 d8 d7

ds2 - d4 d2 d6 d3 d10 d9 d5 d7 d1 d8

ds3 - d7 d3 d5 d1 d10 d9 d2 d8 d4 d6

ds4 - d2 d8 d1 d10 d6 d3 d4 d5 d9 d7

ds5 - d10 d2 d6 d3 d4 d5 d1 d7 d9 d8

d1 - s1 s5 s3 s4 s2 ds1 ds2 ds3 ds4 ds5

d2 - s2 s3 s1 s5 s4 ds1 ds2 ds3 ds4 ds5

d3 - s3 s5 s4 s1 s2 ds1 ds2 ds3 ds4 ds5

d4 - s3 s5 s4 s2 s1 ds1 ds2 ds3 ds4 ds5

d5 - s2 s5 s3 s1 s4 ds1 ds2 ds3 ds4 ds5

d6 - s3 s4 s5 s1 s2 ds1 ds2 ds3 ds4 ds5

d7 - s2 s4 s5 s1 s3 ds1 ds2 ds3 ds4 ds5

d8 - s3 s5 s1 s4 s2 ds1 ds2 ds3 ds4 ds5

d9 - s2 s5 s3 s1 s4 ds1 ds2 ds3 ds4 ds5

d10 - s5 s2 s1 s3 s4 ds1 ds2 ds3 ds4 ds5

If i solve the above with gale shapley will I get the right results?? In other words, will I get the stable matching?


texts:
This is what I got for the in-order of the bst but it's wrong because I'm answering some questions about some successors of some of the letters and I got them wrong. so I'm wondering where in this in-order i've gone wrong?

d, b, m, h, i, e, a, j, k, f, g, c

(Sorry if these questions aren't allowed here, please let me know where I can ask it if not!)


texts: Does a Universal Turing Machine have more computational power than a non-universal one?

texts:
I'm a bit confused about these concepts. As far as I understand, something is Turing complete when it can simulate a Turing machine. And there is this thing called a Universal Turing machine which is universal because it can simulate a Turing machine. Which to me, implies there are Turing machines that are not universal and cannot simulate a Turing machine. Does this mean non-universal Turing machines are not Turing complete?

Could anyone clarify this concepts for me?


texts: Has there been a lexer that takes in much more than a regular language?

texts:
I understand the restrictions, because a regular language is expressive enough to allow all types of tokens. And even if some context is needed in many languages to tokenize properly, they all seem to be "approximately" regular languages.

Yet I would be interested if any attempt in any programming language, possibly esoteric language, has been taken to completely eschew the conventional division between type-3 lexers and type-2 parser.