texts: How do NFA's make program design any better when converted DFA form can't remember original states?

texts:
Here is some content from the book by Peter-Linz I read

"Consider a game-playing program where the machine needs to make the decision for the next move [say for tic-tac-toe]. Since there are multiple moves possible, we deterministically choose each move and evaluate the move and opt for the best one. Even though the selection process was deterministic and there were many possible moves, the final move made was a single one and was chose as best move while hiding all the tried move-computations from the opponent. [Here we assume that the evaluation process of each possible move was hidden from the opponent].
Hence only one choice was made and opponent is given a illusion such that the move was non-deterministic."

My question is: if an NFA is translated to a DFA for implementation purpose ,how does the DFA make(remember) the correct transitions to the states defined in the original NFA(the game)? My confusion stems from the fact that when an NFA is translated to an DFA it's states get mixed up.
Suppose in a simple game below ,Player is at center position and he wins if he moves leftwards:

if the above DFA is implemented it surely finds a winning state on a "m"(move),but how does it decide whether it was right or left move?


texts: Do Rank-1 (prenex) polymorphism and Predicative polymorphism mean the same?

texts:
https://en.wikipedia.org/wiki/Parametric_polymorphism says:

  Rank-1 (prenex) polymorphism

  In a prenex polymorphic system, type variables may not be instantiated with polymorphic types.[4] This is very similar to what is called "ML-style" or
  "Let-polymorphism" (technically ML's Let-polymorphism has a few other
  syntactic restrictions). This restriction makes the distinction
  between polymorphic and non-polymorphic types very important; thus in
  predicative systems polymorphic types are sometimes referred to as
  type schemas to distinguish them from ordinary (monomorphic) types,
  which are sometimes called monotypes. A consequence is that all
  types can be written in a form that places all quantifiers at the
  outermost (prenex) position. For example, consider the append
  function described above, which has type

forall a. [a] × [a] -> [a]

  In order to apply this function to a pair of lists, a type must be
  substituted for the variable a in the type of the function such that
  the type of the arguments matches up with the resulting function type.
  In an impredicative system, the type being substituted may be any type
  whatsoever, including a type that is itself polymorphic; thus append
  can be applied to pairs of lists with elements of any type—even to
  lists of polymorphic functions such as append itself. Polymorphism in
  the language ML is predicative.[citation needed] This is because
  predicativity, together with other restrictions, makes the type system
  simple enough that full type inference is always possible.

  As a practical example, OCaml (a descendant or dialect of ML) performs
  type inference and supports impredicative polymorphism, but in some
  cases when impredicative polymorphism is used, the system's type
  inference is incomplete unless some explicit type annotations are
  provided by the programmer.

  ...

  Predicative polymorphism

  In a predicative parametric polymorphic system, a type τ containing
  a type variable α may not be used in such a way that α is
  instantiated to a polymorphic type. Predicative type theories include
  Martin-Löf Type Theory and NuPRL.

According to the highlighted sentences,

Are Rank-1 (prenex) polymorphism and Predicative polymorphism defined  in the same way as "a type variable can't be instantiated to a polymoprhic type"?
In Rank-1 (prenex) polymorphism, how does "a type variable can't be instantiated to a polymoprhic type" imply "all types can be written in a form that places all quantifiers at the outermost (prenex) position"?

Thanks.


texts: Fastest way to compute a path from a known cycle with unordered edges and vertices

texts: I have an (undirected) graph isomorphic to $C_n$ with unordered edges/vertices in some data structure (in particular, a list of tuples representing the edges), etc. I was wondering what is the fastest algorithm to compute a path which begins and ends at some given node in the cycle, given this set of nodes? The simplest thing seems to be to just use DFS, but that seems like overkill for what I'm sure is a relatively simple algorithm.


texts: Overhead cost of spawning child processes

texts:
I am curious as to the overhead cost of spawning child processes using fork in a Linux environment.  Suppose I have a C program such as
void run_computation(int x);

int main() {
    for (int k=0; k<10; k++) {
        if ( fork() == 0 ) {
            run_computation(k);
            break;
        }
    }

    return 0;
}

Assuming that no global state is modified by run_computation, how efficient in terms of overhead is the setting up of the child processes?
To help understand where I'm coming from, I'd like to write my own regex engine (for self-learning) and am imagining using fork to implement the NFA.  So, am I incurring an unreasonable cost in such an implementation compared to other methods?


texts: Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$

texts: I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a annulus made from wood and then to string yarn between them. Since $K_{37}$ is a complete graph, it has a Hamiltonian path. My knowledge of computational graph theory is nil, and I am aware that this is not exactly an easy problem (see wikipedia: Hamiltonian Path Problem, for instance)


texts: Simple elementary cellular automata with high period?

texts:
I'm looking for a simple rewrite system which displays high period.

In order to do that, I've ran a brute-force search on every elementary cellular automata, for a few fixed memory lengths L. The result is that, when L=7, there are rules with the max possible period (128). Yet, for L=8, no matter which rule is used, I couldn't get a period > 180. For L=9, the maximum period of 133.

I've, then, tried a few variations of the core idea. For example, I tried using 3 symbols instead of just 2 and do a similar brute-force search, but the results are similar.

Thus, I ask: is there any similar system with a rewrite rule which displays high period?


texts: Why NP is not closed under Turing reduction

texts:
The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine.

For example, by stating "$A$ is polynomial time Turing reduced to $B$", we indicate that we can solve the problem $A$ in a polynomial number of steps by making use of an algorithm which can solve the problem $B$.

Then if $B$ is in $\mathsf{NP}$, why not $A$?


texts: Compare phase and magnitude spectrum results of 2 Images

texts:
I have read that from Fourier transform we obtain magnitude and phase spectrum. The magnitude spectrum tells you how strong are the harmonics in a image and the phase spectrum tells where this harmonic lies in space.

I have used Matlab to compute the magnitude and phase spectrum of the 2 grayscale images of babies using fftn function, but the all spectrum are difficult to understand.

Can anyone please explain the features given in 1st paragraph by comparing the spectrums of both images of babies?

1.phase spectrum

and

2.magnitude spectrum

(If you have results other than in Matlab, explaining with your method is also okay)

image1=imread('D:\baby1.jpg');%Read colour image
image1=rgb2gray(image1);%covert colour image into Gray scale

image2=imread('D:\baby2.jpg');%Read colour image
image2=rgb2gray(image2);%covert colour image into Gray scale

figure,
subplot(1,3,1);
imshow(image1);
title('Gray scale Image of Baby1');

%Apply Fourier transform on Gray scale image
fft1=fftn(image1);
fft1=log(1+fftshift(fft1));%Use log function for scaling

%Find the magnitude spectrum
magnitude1=abs(fft1);
subplot(1,3,2);
imshow(magnitude1,[]);
title('Amplitude Spectrum 1');

%Find the phase spectrum
phase1=angle(fft1);
subplot(1,3,3);
imshow(phase1,[]);
title('Phase Spectrum 1');

figure,
subplot(1,3,1);
imshow(image2);
title('Gray scale Image of Baby2');

%Apply Fourier transform on Gray scale image
fft2=fftn(image2);
fft2=log(1+fftshift(fft2));%Use log function for scaling

%Find the magnitude spectrum
magnitude2=abs(fft2);
subplot(1,3,2);
imshow(magnitude2,[]);
title('Amplitude Spectrum 2');

%Find the phase spectrum
phase2=angle(fft2);
subplot(1,3,3);
imshow(phase2,[]);
title('Phase Spectrum 2');


texts: How to select a loop nesting trees for irreducible loops?

texts:
I am trying to understand the process of analyzing a control flow graph and building a tree of loops, both reducible (single entrypoint) and irreducible (multiple entrypoint), using the algorithm described in Nesting of Reducible and Irreducible Loops

Given the following control flow graph:

              ----> 3
             /     ^ \
            /     /   v
      0 -> 1     4 <-> 5
            \     ^   /
             \     \ v
              ----> 2

It seems to me that there are three ways you could define a loop nesting tree:

(0, 1)

(2, 3)

(4, 5)

(0, 1)

(2)

(3, 4, 5)

(0, 1)

(3)

(2, 4, 5)

I initially imagined nesting (1.), but it seems that nestings (2.) and (3.) may be valid as well. However, nestings (2.) and (3.) include an edge that "jumps" straight from the top-level code (at node 1) to the innermost loop (at node 3). Furthermore, taking nesting (2.) as an example, it seems odd to have the second loop have only a single entrypoint node (2), despite clearly being an irreducible loop with two entrypoints from node (1), because one of the entrypoints goes straight into it's inner loop at node (3).

Are all three of these nestings valid loop-trees for the given control flow graph, or only the first one? If they are all valid, is there any reason to prefer one over the others?


texts: Is every von neumann machine turing complete?

texts:
I understand that TM is a 'Model of Computation' which tells us about the computational power of a machine while Von Neumann Architecture is a 'System Architecture' that tells us about how the machine is actually been implemented. Also, I think of 'Programming Paradigms' as how a problem is modelled in a High-Level Language. But I see a lot of conflicts over the connection between these terms all over the internet. Can someone please enlighten me on the below points:

i. In many places, I happen to see phrases like 'Von Neumann Systems are always Turing Complete' and so on. But I am unable to find a reason why a less powerful model of computation - say a DFA could be implemented using Von Neumann Architecture

ii. Imperative Programming Model is called all over the internet as 'Von Neumann Model'. I am totally clueless about this. Why can't we call it 'Howard Model' then?


texts: Set partition with an allowable difference

texts: I have a variation of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is smaller than K. I wonder if this is also a NP hard problem?


texts: Given matrix, count paths visiting each number exactly once

texts:
We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in the matrix.

We want to count paths that start in some cell, then moving in one of the four directions (up, down, left, right) visit all $21$ number exactly once.

It is impossible to move on cells marked as $-1$.

For example:

1,  2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, -1, 21
-1,-1,-1,-1,-1,-1,-1,-1,-1, -1, -1, -1, -1, -1, -1, -1, 18, 19, 20
We can start in the upper-left cell, move right until 17 then down, right again, and up on the end.
The second path is the same as the first path but reversed (starting from 21).

My idea is to use dynamic programming with three states $i, j$, coordinates of the current point, and bitmask of the visited cells. However this is pretty slow for numbers up to 21. Is there any way to speed up this calculation.

Link from the task that appeared on the contest: mendo.club/Task.do?id=647


texts: The extension of a code is itself a code

texts:
I'm reading Cover's "Elements of Information Theory" and I have a problem with the definition of uniquely decodable code.

  A code is said to be singular if there exist two elements that map to
  the same string. In other case it is said to be non singular.

  Let $C$ be a code. The extension of $C$ is the homomorphism $C^{*}$
  between $\chi$ and $D$ with respect to concatenation that is, $C(x_1
> \cdots x_n) = C(x_1) \cdots C(x_n)$.

  Let $C$ be a code. $C$ is uniquely decodable if its extension $C^{*}$
  is non-singular.

According to the last definition the extension of a code is itself a code but as it has domain $\chi^{*}$ where $\chi \subseteq \mathbb{R}$ (that last statement is mine).

How can I view the extension as a code?


texts: The XOR cut-set structure, and combinatorial designs

texts:
Given a graph $G(V,E)$ and a subset of vertices $T \subseteq V$, define $\mathsf{cutset}(T)$ = the set of edges connecting a vertex at $T$ with a vertex at $V\setminus T$.

Our goal is to preprocess $G$ such that, given any set $T$, we can quickly return an edge in $\mathsf{cutset}(T)$, or reply that $\mathsf{cutset}(T)$ is empty. The structure should have space complexity $\widetilde{O}(|V|)$, i.e. we are not allowed to keep all the edges. The query complexity should be $\widetilde{O}(|T|)$.

Kapron et al suggest the following neat solution, which works when the size of each cutset is at most 1.

Give each edge a unique number. For each vertex $v$, keep $\mathsf{xor}(v)$ - the binary XOR of the numbers of all the edges adjacent to it. Given a query on $T$, calculate $\mathsf{xor}(T)$ - the binary XOR of all vertices in T. Every edge which is internal to $T$ (i.e. has both endpoints inside $T$) is XORed twice, and hence is not included in $\mathsf{xor}(T)$. So, $\mathsf{xor}(T)$ is actually a XOR of all edges in $\mathsf{cutset}(T)$.

If the size of each cutset is at most 1, then there are two options: either $\mathsf{xor}(T)=0$, which means that $\mathsf{cutset}(T)$ is empty, or $\mathsf{xor}(T)$ is the number of the single edge in $\mathsf{cutset}(T)$.

The authors then go on and describe a complex, randomized structure to handle the case in which $\mathsf{cutset}(T)$ contains more than a single edge.

But in the conclusion, they say that:

  It is not hard to see that the technique described here can be made deterministic with an additional $\widetilde{O}(k)$ factor in the update time, if we know the cuts are of size no greater than $k$, through the use of combinatorial designs".

Unfortunately, for me this seems to be hard... I don't understand: how can combinatorial designs can be used to solve the problem when the size of all cutsets is at most $k$?


texts: Sharing of two language L1 and L2 regularity question

texts:
We call the sharing of two languages L1 , L2   to be the set of all strings that are in both or neither of L1  and L2 . If L1  and L2  are regular, then the sharing of L1  and L2  is regular. True or false?

Apparently the answer is false but that confuses me because can't the sharing of L1 and L2 be all the strings that are neither in L1 and L2, which means that they could be nonregular strings? Or am I just not understanding this...


texts: How to find the minimum number of vertices whose removal make the graph disjoint

texts:
Given a graph $G = (V,E)$.

Is there any algorithm which finds the minimum number of vertices to be removed from $G$ so that every vertex in the graph becomes disjoint, i.e., every vertex is disconnected from every other vertex?


texts: Some questions on kernels and Reinforcement Learning

texts:
I've a test in a few days and I've a few issues with some of the subjects.

Let's start with kernels, basically I understood that a kernel needs to be positive semi-definite and symmetric in order to be valid. Is that enough? For example the following kernel, $\mathrm{kernel}(x,y) = 2 k(x,y)$ for some $k$ which is a valid kernel. Is that valid? My question is how can I distinguish between a valid kernel and an invalid kernel if I'm given a kernel in the test?

Reinforcement learning - Value iteration, upper bound confidence and Q-learning. I'm trying to figure out the major differences between them, Value Iteration is when we are familiar with the world, with the probabilities and such. And Q-learning is basically learning the world first. Where does upper bound confidence enter?

Thanks.


texts:
Average memory access time = Hit time + Miss rate * miss penalty

Assume a computer with only one cache level. What is the exact meaning of hit time? Is it the number of clock cycles to access data from cache? OR Clock cycles to execute an instruction? How does the number of clock cycle per instruction come into this equation?


texts: More details on a language decided in $\Theta(\log \log n)$ space

texts:
In Language with $\log \log n$ space complexity?, the following non-regular language is described:

$$L = \{b(0) \# b(1) \# \dots \# b(2^k-1) \mid k\in \mathbb{N}\}$$

where $b(i)$ is the $k$-bit binary representation of $i$. This can evidently be computed in $\log \log n$ space, where $n$ is the length of the string, using the typical TM with input-output tapes.

This is apparently a common example used in complexity theory, however I would like some clarification on the method of calculation -- the answer given is very unclear and differs from the method defined in the reported source.

In the answer given, it says we do the check only when $m$ is smaller than the width of the first block. Am I misunderstanding this? If we do this, we never check the MSB of each representation, so for example the string $10\# 11 \# 10 \# 11$ would be accepted since it never checks $m=2$.
Do we check if the $m$ least significant bits form a counter modulo $m$, or modulo $2^m$? The lecture cited checks the ending modulo $2^m$, but the answer says modulo $m$. Wouldn't having a counter that goes up to $2^m$ take $m$ space which is already too much space ($m = O(\log n)$)? If we're supposed to make the counter modulo $m$, how do we take binary numbers modulo $m$ while still satisfying the space requirement? If $m$ is a power of two we can just do addition with overflow, but what about when it's not?I don't see an obvious, space-efficient algorithm for doing this in general.
Furthermore, even if we can do this in the given space, I don't see why the method taking modulo $m$ decides the language. For example, I can give you $00 \# 11 \# 10 \# 11$ and the LSBs form a counter "modulo $1$" and the two LSBs form a counter modulo $2$.

If anyone can clear up my questions that would be greatly appreciated. I think it's likely that there's just one thing I'm fundamentally misunderstanding about the presentation here which is causing everything else to not make any sense.


texts: A two-tape deterministic Turing machine that recognizes an exponential string

texts:
How can I describe a Turing Machine recognizing the language $P=\{a^{2^n} | n \geq 0 \}$?

This Turing Machine is deterministic and uses two tapes, both bidirectional and R / W (read & write)

The computation should be done in linear time.

I've read Counters in Turing machines but it doesn't address my question. It can help but it doesn't answer my question.
Turing Machines with $n$-tapes have the same computability that Turing Machines with one tape, but different behavior. Here I'm asking about the behavior of a two-tape TM.

My approach:

I think I may use the first tape as input tape and copy every character in the second tape. But I don't know how to keep track the exponential behavior.


texts:
In this problem, I want to maximize the number of points of K dance moves. There are N possible dance moves.

Each of the dance moves have a point value associated with it which can be positive or negative.

There are also points from transitioning from one dance move to another. We're given an $N\times N$ matrix that has the points gained from transitioning from one dance move to another.

The brute force solution is easy which is simply try every dance move for the 1st move, then the 2nd move, then the 3rd ... which is $O(N^K)$.

My interviewer says there's a $O(NK^2)$ or $O(KN^2)$ solution (don't quite remember if it's one or the other).

How do I get that solution or what's the best solution to this problem?

Thanks!


texts:
What is does it mean when an argument to a function is called a dummy argument? I have not encountered this term outside Fortran, is it a general term in computer science? What would be examples of arguments passed as dummy and not passed as dummy?

I found this definition, which I am not sure that I understand, but it sounds like a dummy argument is a variable that is passed by reference, in which case in Fortran all variables are dummy variables? (confused)

Edit: I just run into the following essay which helped me to understand better Fortran's argument/function calling teminology: Dortor Fortran: I've come here for an argument


texts: Store a n-bit string using only O(log n) space

texts: Is it possible to somehow store a $n$ bit string using only $\mathcal{O}(\log{n})$ space? I am thinking if the string could be stored using a hash function, but I am not sure if it is even possible.


texts: Translation from Intermediate Language into 'three-address' machine instructions

texts:
I am unsure where to start with this. From what I understand so far, 'VAR(x)' corresponds to Rule 2, ':= VAR(x) ' refers to Rule 5 and '+ NUM (1) refers to link 3.

a := (b+c)*(-e); becomes
t1 = b + c
t2 = – e
a = t1 * t2

I understand the translation above, What I am not that clear about are the recursive rules. How do they influence translations?

Can someone point me towards the right direction?

EDIT: With further research I think I understand the concept of the recursive rules. For rule 1, it seems that the value of 'n' will be stored in R' register.

I think the problem i'm facing is how to formulate an answer with my working.


texts: Generate a random combination in O(k) time and space?

texts:
How to generate a random combination of $k$ numbers from $n$ choices in $O(k)$ time and space, if we can generate a random number between 1 and $O(n)$ in $O(1)$ time?

I know only 3 algorithms: with $O(n)$ time and space, $O(k\log k)$ time and $O(k)$ space, $O(k)$ average time and $O(n)$ space. Is it even possible to solve this task on $O(k)$ both?


texts: Analyzing the time complexity of nested loops

texts:
So I've been given a piece of pseudo code that involves nested loops. The answer to this question is Θ(n^5) but I do not understand why it is so.

What is the time complexity of this code?

for  i = 1 to n
   for  j = 1 to n*n
      for  k = 1 to j
         Task

where the time complexity of Task is Θ(1)

The most inner loop, for k = 1 to j is Θ(j). Then the middle loop, for j = 1 to n^2 I thought, should produce Θ(n^2) as it loops from j = 1 to n^2 but I've been told it's Θ(n^4). I honestly do not understand how it could be Θ(n^4) when it's iterating from 1 to n^2. Can someone explain how this works in simple terms?


texts: Is the language $(a^n)^mb^n$ context free?

texts:
$(a^n)^mb^n$  for $m,n\ge 1$
This can be rewritten as $a^{nm}b^n   $
i.e. number of $a$'s is a multiple of number of $b$'s, or for every m $a$'s there is one $b$. I thnk this language can be accepted by NPDA. For every m $a$'s one a can be pushed into the stack, and similarly one can be popped on encountering a $b$. But the NPDA needs to try this for every possible m, where m varies from 1 to maximum string length of $a$'s.


texts: Difference between algorithm and procedure

texts: I came to know that the important difference between algorithm and procedure is that the algorithm halts and procedure doesn't halts(stops). But i am not able to understand the concept. Please can any one explain with the example?


texts: Constraint solving for scheduling code with complex unspillable register classes?

texts:
I'm currently working on a compiler backend for a custom architecture which has some unusual constraints. The architecture has several super-registers with aliasing between the sub-registers, and none of these special registers can be spilled to memory. The code is initially constructed to ensure that registers can be allocated within these constraints (only one of the super-registers is live at a time).

Instruction scheduling (which is done before register allocation) must ensure that it only generates instruction sequences that have a valid register allocation.

After researching register allocation, it seems that the best fit for register allocation on my 'irregular architecture' is PBQP (partitioned boolean quadratic programming). However, during instruction scheduling, I don't need an (approximately) optimal register allocation, but rather just need to know whether there are any valid register allocations for a sequence of instructions.

Additionally, during scheduling, I'm going to need to repeatedly solve many similar instances of the CSP (constraint satisfaction problem). Any time register allocation is not possible, I'll need to try the problem again with only a few different nodes/edges (for a different instruction), and each time the CSP is satisfied, I'll need to solve it again with a few additional nodes/edges (for the next instruction).

I have not found any literature on solving similar CSPs taking advantage of the similarity, and the best algorithm I've found for solving PBQP approximately (from Nearly optimal register allocation with PBQP) destructively modifies the graph while solving.

Is there a better approach to use for testing register allocatability during instruction scheduling than PBQP, or is there a better algorithm for sequentially solving similar PBQP instances with only zero/infinite costs?


texts: Encoding a list of numbers using gamma coding

texts:
I'm trying to work out how to find the gamma $\gamma -code$ that encodes the postings list (12, 18, 21, 22).

Is the postings list encoded just by a list of the individual $\gamma$-codes for each integer? E.g. for 12 the gamma code is: 0001100, and so the first entry in the $\gamma$-code for the pointing list is just 0001100. Or is there another representation - am I thinking along the right lines?

Thanks in advance for any help!


texts: What is the property of a PL that extracting a subroutine should not change the meaning?

texts:
What is the name of the property of a Programming Language that says that extracting a subprogram into a subroutine and using that subroutine instead of the subprogram should not change the meaning of the program?

I could swear that this exists and that it has a well-known name, but I can't for the life of me remember it. My efforts to search for the name have been thwarted by being swamped with results for the Liskov Substitution Principle or Referential Transparency.

What I am looking for is the property that I should be able to replace

printf("Hello");

with

void hello() {
    printf("Hello");
}

hello();

without changing the meaning of the program.

I think it is named after the person who coined it, but I am not sure. Something like XYZ Equivalence or XYZ Principle where XYZ is the name of a well-known Computer Scientist. I want to say Strachey, but I couldn't find a mention of anything similar in Fundamental Concepts in Programming Languages.


texts: Size of the universe for van Emde Boas Trees

texts: In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size  $u$  is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde Boas trees. Why choose $u$ to be of this specific form ?


texts: How to interpret the execution of distributed computation from time-space diagram?

texts:
I'm following a course on Distributed Systems

http://www.ict.kth.se/courses/ID2203/index.html

and currently learning about asynchronous models. I can't seem to reconcile a given time-space diagram of an execution with the symbolic definition of the execution as a sequence of configurations and events.

In the model, an execution is defined as a sequence of configurations interleaved with events. As in:

<C,E,C,E,C,E...>

Where the C's are configurations (states of the nodes, including their buffers) and the E's are events, which in this model, are either Computation or Delivery events.

A computation event, comp(i), takes place at a single node, indexed by i, and modifies the buffers of node_i and the internal state of node_i and nothing else. A delivery event, del(i,j,m), removes message m from the output buffer of node_i and adds it to the input buffer of node_j.

A time space diagram of a particular execution is given in Slide 11 in this particular lecture: http://www.ict.kth.se/courses/ID2203/material/Lecture_2._Unit_3._Computation_theorem_and_causality.pdf

The arcs on a single timeline are comp(i) events at a particular node. The arcs between timelines are del(i,j,m) events between nodes i and j.

I'd like to interpret this diagram into a sequence of comp and del events, but it seems ambiguous. Specifically, a delivery is initiated from node 1 to node 2 -- del(1,2,m) -- and during the delivery a computation event at node 3 -- comp(3) --  takes place and completes before the delivery event completes.

Since the events in an execution are, by definition, totally ordered, I'm not sure if the comp(3) should precede the del(1,2,m) or vice versa.


texts: A query regarding the Max3SAT Approximation Algorithm's Application

texts:
Its known that a polynomial time Approximation Algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP. If given that the given 3MaxSAT is satisfiable, it is still difficult to find a 7/8+e clause satisfiability in Polynomial Time.

After learning quiet a few Max3SAT Approximation Algorithms I am still very unsure regarding the real world applications of such inexact algorithms other than theoretical perspective (unlike 3SAT).

Can someone point of few of the real world application areas.


texts: Comparing two recurrence relations w.r.t. asymptotic growth

texts:
I have two functions $T_1(n),T_2(n)$. How do I decide which is asymptotically faster?

One is given by the recurrence relation

$$ T_1(n) = \sqrt{n} T_1(\sqrt{n}) + 3 n, \quad T_1(1) = T_1(2) = 1. $$

The other is given by the recurrence relation

$$ T_2(n) = 3 T_2(n/3) + 2n \log n, \quad T_2(1) = T_2(2) = 1. $$

For the first function I guess there is $O(\sqrt{n} \cdot \sqrt{n})$ for loop, and $O(n)$ for the $c$; which becomes $O(n^2)$ in total.

For the second one, the Master's theorem is applicable, but as I assume the complexity becomes $O(n \cdot n \log n) \Leftrightarrow O(n^2 \cdot \log n) \Rightarrow O(n)$ for loop, and $O(n\log n)$ for $c$.

So if I am comparing both $O()$'s, we can in total see that

$$ O(n^2) < O(n^2 \cdot \log n) $$

Was there any mistake, or is this not how recurrence unrolling is done?


texts: Is binomial(n, k)=0 (mod n) when gcd(n, k)=1? When gcd(n, k)>1?

texts:
I was programming the AKS primality test, and I have two questions.

Is it correct that if gcd(n, k)=1, then binomial(n, k)=0 (mod n)?

Is it correct that if gcd(n, k)>1, then binomial(n, k)>0 (mod n)?


texts: Algorithm to determine if recursion was breadth first or depth first

texts:
Given a tree $T$ and a sequence of nodes $S$, with the only constraint on $S$ being that it's done through some type of recursion - that is, a node can only appear in $S$ if all of its ancestors have already appeared, what's a good algorithm to determine if $S$ is a breadth first visit, a depth first visit, or neither?

A brute force approach is to compute every breadth first and depth first sequences and see if any is identical to $S$.  Is there a better approach?

What if we don't want a yes or no answer, but a measure of distance.  E.g. $breadth < S < R < U < depth$; what's a good algorithm to determine distance? (A brute force approach for this is just $max(length(longest{\_}common{\_}subsequence(S, breadth))/length(breadth))$ over every BFS - again, is there a better way to do this?)


texts: Algorithm for creating a map / schematic from a list of travel times?

texts:
I have data for a warehouse that shows when a person was at a particular bin/shelf (location). As the person moves through the warehouse they build up a profile of how long it takes to get from bin X to bin Y.

I have a lot of this data and it occurred to me that I can use it to construct a schematic of the warehouse bin locations and their distances from each other.

Is there a known / named algorithm for this? I know how to do it by triangulation but I'd rather not reinvent the wheel and there may be issues that others have solved already.


texts:
I'm reading Arora Barak and in that it is written that when $O \in \mathrm{P}$, then $\mathrm{P}^O = \mathrm{P}$. Can this be generalized?
Intuitively,  I think that $\mathrm{NP}^\mathrm{NP} \neq \mathrm{NP}$ but $\mathrm{EXP}^\mathrm{EXP} = \mathrm{EXP}$.
Am I right? Any elaboration on the same would be appreciated.


texts: Sphere, triangle, and other primitive shape intersection

texts:
In a three dimensional Cartesian space, given a ray in its parametric form:
$r(t) = [1, 1, 1] + t[-1, -1, -1]$ find the intersection points between the ray and the following primitives.

a) A sphere centered at the origin with a radius of $1$, and

b) a triangle with vertices $\{[1,0,0]^T , [0,1,0]^T , [0,0,1]^T \}$.

Represent the intersections in their Cartesian coordinates as well as the ray parameters. Write down the intermediate steps of your derivations clearly.

The next part asks me to choose another primitive 3D shape, decide on implicit or parametric surface functions, then make an equation for ray-surface intersection and derive the analytic solution.

I am a little confused on this assignment because I haven't had a physics class before and I don't understand the basics of 3D shapes' geometry or vectors. It's not entirely clear to me what I am supposed to find as an answer or in what form the answers should be written. I looked up the formulas for sphere and triangle intersection, but I can't find a similar example, so I don't know how to solve the problems.


texts: Efficient Algorithm for determining who wins a game of Chess

texts:
I was reading Jeff E's lecture notes on Algorithms when I came upon the following question:

Describe and analyze an efficient algorithm that determines, given a legal arrangement of
standard pieces on a standard chess board, which player will win at chess from the given
starting position if both players play perfectly. [Hint: There is a trivial one-line solution!]

My only thought is to form a tree of possibilities and go down every tree to see where it ends. But this is neither one line or efficient. Any help is appreciated(I prefer hints to full solutions, and I will accept a hint as an answer if it leads me to the answer).


texts: McNaughton-Yamada Algotihm (1960) Regular Expression to DFA without passing through NFA

texts:
I have a homework problem here. It asks me to use the McNaughton-Yamada algorithm to first convert a regular expression to a DFA, and then minimize this using a partition argument. I can do the latter. My problem is that I cannot access any actual reference on the algorithm. Their original paper is behind a paywall at IEEE that my university does not have access to.

The algorithm went something like this:
1. For each symbol in the expression, given them a subscript from left to right increasing by one for each instance of that symbol. For example, the expression, aa* would receive a_1 a_2^*.

We proceed to construct a diagram based on the possible lengths of words.

If done appropriately, this produces a DFA. I think the labeling in (1) is to help label the states.

Feel free to come up with your own example if you decide to give an answer. I won't provide any problem here because there is no guarantee that it isn't actually my homework exercise.


texts: NP-completeness of graph isomorphism through edge contractions with an edge validity condition

texts:
Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset of edges are valid for contraction at each step of the sequence. For example when deciding the first edge for contraction, there are only a subset $E'\subset E_1$ of edges eligible for contraction. If you pick $e\in E'$ for contraction and get an intermediate graph then when deciding the second edge for contraction in this intermediate graph there are a subset $E''$ of edges eligible for contraction and so on.

Does this problem stay NP-complete ?


texts: I am reading about this in the context of the K semantic framework. I keep encountering terms such as rewrite-term and rewrite logic. My main aim is to understand what is K doing and how it works, so maybe this would be a bit off-topic.


texts: Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant?

texts:
The standard Post Correspondence Problem concerns tiles with two rows of symbols, and whether a tile arrangement can be made so that the sequence of the top symbols of the tiles is equal to the bottom one.
Let $\text{n-PCP}, \text{n} > 0$ a generalization of the Post Correspondence Problem where the tiles contain $\text{n}$ rows, and the sequences of the symbols have to be equal for all of these rows.
Obviously $\text{1-PCP}$ is decidable (in fact it's trivial because the answer to the problem is always true). $\text{2-PCP}$ is the standard PCP.
But what if $\text{n} > 2$? Is it harder or can it be reduced to the standard PCP (like >3-SAT being reduced to 3-SAT)?


texts:
for every j != i in {0,....,n-1}

How to interpret this for loop? I never seen this type of definition of for loop.

Is it like -  j=0 to n-1; j !=i ; ++j


texts:
In RL, in a game situation, usually the agent is trained by playing against itself.

When we should not depend on this self-training, and switch to train the agent with a real or different player agent other than the agent it self?

I mean is there any characteristics of the environment that would make self-play worse choice than playing against an existing player?


texts: Graph with exactly 2 Minimum Spanning Trees

texts:
Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs).
  Given this condition stipulated, prove that any cycle formed by all
  the edges in both the MSTs (i.e., the union of the edges in of the 2
  MSTs) that at minimum, 2 of the edges in the set which is the union of
  the edges have equal weight. Also show that either this edge is the
  largest weight in the cycle, or not the largest weight in the cycle.

Overall am pretty stuck on this question.

My initial thoughts are the following: In any graph with more than 1 MST, clearly this means that the edge weights can't be distinct, otherwise there wouldn't be multiple MSTs. Also the graph $G$ must contain cycles, otherwise, it wouldn't have multiple MSTs.

My idea for proving that any cycle formed by the union of the edges of the two MSTs would be that in $MST_1$ there is some edge, $e$ that is not in $MST_2$ and there is also some edge $f$ that is not in $MST_1$. Using the cut property if $e$ was not placed in $MST_2$ and $f$ was not placed in $MST_1$ then then we have that the weight of $f$, and $e$, $w(f) = w(e)$.

Having trouble formalizing this though, and wondering if its actually a correct deduction. I feel that it makes sense given some examples and drawing, but not quite certain that's actually true. Then from there I felt that there had to be some node, $z$ such that $z$ had 2 edges with the same weights, and when we combine the edges from $MST_1$ and $MST_2$ we end up with both the edges from $z$ forming a cycle, and the edges are the same weights, so we know at least 2 of the edges form a cycle... Or the union of the edges could form a cycle graph itself which would then show that the 2 edges with the same weights are part of a cycle, I think? Is this somewhat on the right track? Is there some sort of condition for a graph, $G$, in order for it to have exactly 2 MSTs? Or is there some property I'm missing?

If someone could please provide a bit of guidance in the right direction, it would be extremely appreciated. Thanks.


texts:
There is a display of NxN (N<=90) pixels with some blocked pixels and a snake of width = 1 pixel and variable length and two players A and B play a game.

The game proceeds as follows -

Both players take alternate turns.
In each turn, the player has to extend the length of the snake by moving it's head in either of the three directions (left/right/forward) by one pixel thereby increasing the length of the snake by 1 pixel. Therefore, the snake doesn't move from it's initial position but only the length of the snake increases and it's head moves in some direction.
The head of the snake cannot cross it's body or any of the blocked pixels.
The Player who cannot extend the length of the snake anymore loses the game.

The list of blocked pixels is given to you.

Initially the length of the snake is 1 pixel i.e. it occupies only one pixel from the NxN pixels.

I need to know for each unblocked pixel, who will win the game if Player A starts the game by putting the snake on this particular pixel initially.

I tried reducing the problem to apply the Sprague-Grundy theorem but made no progress as the size of the display is too large (90x90) So, calculating the Grundy numbers for each state isn't computationally feasible.

Also, I suspect that there exists a max flow solution to the problem but I failed to construct the flow network for the given problem.

Can someone suggest a solution which works for the given dimensions of the display?


texts: Partially homomorphic encryption (on addition modulo N) not based on prime factorization

texts:
A cryptographic function is homomorphic on some operation if that operation is preserved in the encrypted data.

Such a function is homomorphic on addition modulo if the following holds for some cryptographic function $E$:

$
E(x)\cdot E(y) = E(x+y\mod N)
$

and on xor:

$
E(x)\cdot E(y) = E(x \oplus y)
$

This is called a partially homomorphic encryption.

Such schemes are described on the Wikipedia page:

http://en.wikipedia.org/wiki/Homomorphic_encryption

However, all the partially homomorphic schemes on XOR and addition modulo are based on prime factorization.

Are there partially homomorphic encryption methods on XOR or addition modulo that do not are not based on prime factorization (other than the fully homomorphic system proposed by Gentry based on lattice cryptography).

This paper by Mykletun, Girao and Westhoff suggests the El-Gamal method:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=99E3442A4CF314F9AF334969DF9C7974?doi=10.1.1.61.5322&rep=rep1&type=pdf


texts:
Suppose we have a forest. The leaves have labels. Let's suppose all labels are natural numbers. We would like the forest to support two operations:

rebasing that replaces a leaf on first tree with the second tree.

void rebase(node leaf, node root)
leaf search by the (possibly internal) node of any tree and label we'd like to find in a subtree with a root in that node. It should return either a reference to the leaf that has that label or a failure. In case there are two leaves with the same label, it should return any of them.

optional<node> search(node root, int label)

Which data structure could help implementing both of these operations in sublinear (i.e. O(1) or O(log n)) time? Is there a popular name for this problem?

Currently I'm using an O(N) search that visits via DFS every node of the subtree and compares labels to the given one.

Pretty obvious solution would be to have a double-linked list of leaves for each tree in a forest. Leaves should be listed in a left-to-right traversal order. Every node would store two pointers that mark beginning and the end of the part of that DLL that contains all leaves of the subtree with the root in that node. In such a way rebase could insert one DLL into the middle of the other, and search would need to traverse only leaves of the subtree. But that doesn't decrease complexity of search from linear, because it requires O(N) leaf visits and label comparisons.

Another solution is to have a persistent binary search tree on each node of the original tree. Rebasing would require O(h n) operations to rebuild search trees on all the nodes from the insertion point to the root, and search would be O(log n). But this approach seems overcomplicated and requires garbage collector to implement properly.


texts: For every node of a tree, find the nearest ancestor node such that val[node] is coprime to val[ancestor]

texts:
Problem Statement : Given a tree with N nodes rooted at node 1. Each node is associated with a value. Determine the closest ancestor that contains the value coprime to the current node value. (Note that it is node value and not node number.)
Here is what I did :
Define the lists as : adj[ ] is the adjacency list (a list of lists which is constructed when taking inputs from the user).
Create a list parent[ ] that stores the parent of each node. This can be done in O(N) time.
Our main algorithm is to start at node 1 and mark it as ans[1] = -1 since it can not have an ancestor. Traverse through the nodes in the DFS manner. Check for the coprime ancestor by setting a variable v and a while loop such that if gcd(node, v) == 1 : ans[node] = v else make v = parent[v]. In this way, we check if the parent is coprime, if not, we check if parent[parent] is coprime and so on, till we hit the base case.
Pseudocode for the main problem :
ans[1] = -1
parent[1] = 0
def dfs(root) :
        loop node in adj[root] :
                v = root
                while (5 > 0) :
                    if gcd(val[node],val[v]) == 1 :
                        ans[node] = v
                        dfs(node)
                    else :
                        v = parent[v]
                        if v == 0 :
                            ans[node] = -1
                            dfs(node)

The GCD can be evaluated in O(log_2 max(val[node])) time. The while loop runs in a time proportional to O(depth(node)). Suppose b is the max branching factor of the graph. Then, the overall complexity will be O(|V| + |E| + sum(b^{r <= d} log_2 max(val[node]))) = O(N log_2 max(val)).
1. Is there a more optimized code (average time/space complexity wise)?
2. Is the algorithm correct or there are loop holes in the logic or maybe in some boundary cases?


texts:
Consider the following game (see also this question):
One day a castle is attacked at sunrise (by surprise) by n soldiers.
Each soldier carries a canon and a rifle.
The castle has strength s.
On the first day each soldier shoots his canon at the castle costing the castle n strength points (i.e. the castle ends the first day with s=s-n strength points).
After all the soldiers have fired, the castle sends dpw defenders to battle them.
In the ensuing days the castle and the soldiers battle it out following these rules:

All the soldiers fire first. A soldier can fire his canon at the
castle or his rifle at one of the defenders (but not both and each
soldier can only shoot once). One shot at a defender kills him. One
shot at the castle decreases its strength by 1.

Then each of the d defenders shoots at one soldier (and only
one) killing him.

If the castle still has strength points (i.e. s>0) it sends a
new batch of dpw defenders at this point. The total number of defenders in the next round will be d=d+dpw.

Repeat 1 through 3 on each new day.

If all soldiers are killed by the defenders, the castle wins.

If there are zero defenders after the soldiers shoot and the
castle strength is zero, the soldiers win.

The answer to this question gives the strategy the soldiers should follow to win in a minimum number of rounds.
If $$n\leq s<2n, dpw\geq n, 2n<dpw+s<(\phi+1)n$$, the strategy that leads to a victory for the soldiers in the minimum number of rounds consists of the soldiers shooting only at the castle in the first and second days and destroying it, and from then on, the soldiers trade fire with the remaining defenders winning in a total of
$2+\max(k,0)$ days, where
$$k=\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$
If $dpw<n$, the soldiers can win in a minimum of $c+\max(k,0)$ days, where
$$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$
and
$$k = \left\lceil\frac{\log_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$
In this case they shoot, in each round, at the defenders first then the castle for $c$ days which is the time it takes to destroy the castle.
What is an algorithm to find systematically all the strategies that lead to a win by the soldiers not just the minimum day strategy?
For example if $n=10, s=12, dpw=10$, there are 2 solutions in which the soldiers win:
The first where the number of soldiers, defenders and castle strength goes like this (in 3 rounds)

start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12
round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2
round2:'soldiers': 8, 'defenders': 2, 'castle-strength': 0
round3:'soldiers': 8, 'defenders': 0, 'castle-strength': 0

and the second solution where it goes like this (4 rounds)

start: 'soldiers': 10, 'defenders': 0, 'castle-strength': 12
round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 2
round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 1
round3:'soldiers': 6, 'defenders': 3, 'castle-strength': 0
round4:'soldiers': 6, 'defenders': 0, 'castle-strength': 0

(in the particular case where $dpw=n$, like in the example above, there is an infinite number of solutions as @rotia points out, where the 10 soldiers eliminate the 10 defenders in either the 3rd or 4th or 5th... round before destroying the castle)


texts: Converting a regular expression to a grammar and regular grammar

texts:
I am working on a pretty small lab for my university course and I'm having trouble converting a given regex into a set of regular definitions, then into a grammar and finally a regular grammar. I have reviewed the course material given to me and it has given me some understanding of the process, just enough for me to attempt it but not enough for me to be confident in what I'm doing. I have also tried looking for resources online but I could not find anything that helped me understand the concepts any better, if you have any online resources you recommend please let me know I would love to read more on the topic.
My goal for this question is not to get the answers to my lab but rather to help me understand if I'm doing something wrong and how to do it correctly. I will detail the questions as well as my work so far below.
Note: excuse my formatting, I'm not very good at it.
Question
Regex: $[0−9].[0−9]+e(−)?[0−9]+$
steps
1.Regex into regular definition
2.Regular definition into grammar
3.Grammar into regular grammar and how many productions does it have?
My work so far

I started by converting the regex into definitions, what I ended up with was the following

$DIGIT → [0-9]$
$EXPONENT \rightarrow$ $'e'('-')?DIGIT$
$DECIMAL \rightarrow$ $'.'DIGIT$ $EXPONENT$
$FLOAT \rightarrow DIGIT$ $DECIMAL$
I'm basing this off of the example shown to me in class, it could very well be incorrect. One of my main concerns here is if I am allowed to have the EXPONENT definition embedded within the DECIMAL definition and how that will affect my later work.

My work here is based off of part 1 which could be incorrect, so I will assume my last section was correct and continue working from there.

$FLOAT \rightarrow DIGIT$ $FLOAT2$
$FLOAT2 \rightarrow$ $'.'$ $DIGIT$ $EXPONENT$
$EXPONENT \rightarrow$ $'.'$ $'-'$ $DIGIT$
$EXPONENT \rightarrow$ $'e'DIGIT$
$DIGIT \rightarrow 0|...|9$
$DIGIT \rightarrow DIGIT$ $DIGIT$
This is what I came up with for grammar, I'm not sure about the two $DIGIT$ lines in the bottom, I assumed this is how you handle $[0-9]+$. The question prompt mentions possibly needing alot of $FLOATX$ where $X$ is 1,2,3... The fact that I only needed $FLOAT2$ while the example in my lecture material needed more makes me think that I missed something there as well.

This is the last part where I have to convert the grammar from part 2 into a regular grammar, I will once again be assuming my work in the last step is correct so I can continue on.

This step I'm very lost on, I don't really know where to go to be honest, the work I have on my lecture material does not include enough steps for me to try and understand the logic behind the steps taken. I will leave this one blank.


texts: Which of these algorithms are more efficient in big-θ notation?

texts:
Picture

procedure MatchExistsA
   for i = 2 to n
     for j = 1 to i-1
       if a_j = a_i then return true
   return false

procedure MatchExistsB
 BubbleSort(list)
   for i = 1 to n-1
     if a_i == a_i+1 then return true
   return false

I calculated the worst-case running time of each algorithm using Θ notation, and for the first algorithm, I got Θ(n²).

When i=2, there is 1 iteration in the inner loop. When i=3, there are 2, and so on. At i=n, there are n-1 iterations. Thus, the total is 1+2+...+n-1 => n(n-1)/2 => Θ(n²)

For the second one, the question assumes BubbleSort has Θ(n²) at worst-case. The loop then has n-1 iterations i.e. Θ(n). Thus, max ( Θ(n²) , Θ(n) ) = Θ(n²).

It is right that both of them have the same running time? I feel like I'm doing something wrong or I am not understanding the question correctly.


texts: finding all cyclic substrings of a string

texts:
I have been stuck on this problem for a while now; any help would be appreciated.

Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For example, "abbccbbadad" has 3 because "bb" is composed of 2 "b"s, "cc" is composed of 3 "c"s, and "adad" is composed of 2 "ad"s.

My solution uses hashing and currently runs in n^2 time, which is fine because the length of the string is <= 5000. However, my program uses n^3 space. I am confident that a solution requiring n^2 space and n^2 time will pass. Is there a more efficient solution?


texts: Is the symmetric difference of a non regular language L and a finite language f non regular?

texts:
The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$.

Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric difference yields a non regular language.

Although this looks like it should be a very simple problem and it seems very obvious to me since I’m only changing the language finitely, I can’t seem to prove it.

My progress:

we have: (L-F)U(F-L).
the right hand side is a finite language.
So this problem will be solved if we prove these two statements:
A) L-F is non regular when L and F are non regular and finite (respectively).
B) LUF is non regular when L and F are non regular and finite (respectively).

I originally thought I had a very simple solution for each of these using a proof by contradiction with the pumping lemma (based on the largest length of a word in the finite language) but I later remembered that the pl is not a sufficient condition to be regular thereby invalidating my argument.

Something that seemed like a good approach is the Myhill-Nerode theorem but I can’t seem to get anywhere because I wasn’t able to prove that  there must be an infinite number of  “dividing words” z which would mean the finiteness of F could not account for them.

In the end I came up with a simple proof by contradiction of A using regular expressions, But can’t seem to get B using a similar approach.

So, if you can help me solve B or the original problem that would be great.


texts: How to describe Deterministic Transitive Closure in FOL?

texts:
In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE.
Hence, taking into account that FOL captures LOGSPACE, the following should be possible:

Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
Define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)").

I would like to know how to define such predicate. This would be quite easy in Datalog, using recursion, but it should be possible to define it without recursion, which is the question that puzzles me.


texts: Logarithmic run time for calculating prime numbers?

texts:
Here's the function I'm currently analyzing. I know it's not the most optimal but I'm not understanding the $\theta()$ of this algorithm. I've been told that it's not actually $\theta(n)$ but instead a logarithmic run-time and it had something to do with the bits of the value passed in. I'm not understanding how the bits are causing the logarithmic so if someone can explain that it'd be great.

   function isPrime(n):
1  if n = 2 return true
2  for i from 2 to n
3      if n % i = 0 return false
4  return true


texts: Algorithm to group entities into variable sized groups based on attribute

texts:
I have the following problem:

There are n entities (persons) having a common attribute (weight) and I need to build weight categories (this is for a sports event) grouping people based on their weight. The weight of the people in one group should be as equal as possible.

Problem/Opportunity is that the group size can vary. The groups should usually hold 4 persons, but can be 5 or 3 persons as well if that fits better. 2 or 1 only in exceptions, usually at the upper and lower end.

It sounds somehow like a clustering problem, but I could not find a variant matching this kind of problem.

Example:

Person 1: 15kg
Person 2: 20kg
Person 3: 21kg
Person 4: 27kg
Person 5: 27.5kg
Person 6: 27.7kg
Person 7: 28kg
Person 8: 28.1kg
Person 9: 29kg

This should result in 4 groups:

1: 1
2: 2+3
3: 4-6
4: 7-9

Even though group 3 could also have 4 competitors, group 4 would then be left with two only.

I can probably come up with more rules, but my main question is if there is a algorithm/problem I can use as start point.


texts: Regular expression for the second symbols from the front and the back are equal

texts:
I am practicing for an exam. I am trying to convert a language to a regular expression. The language and my solution is as follows:

$L=\{w∈\{a,b\}^+│|w|≥4\  and\ the\ second\  symbols\  from \ the \ front\  and\   the\  back\  are\ equal\}$

Solution: $(a+b)x(a+b)^* x(a+b)  \ \ where\ x=(a+b)$

Is this correct? If not, can someone correct me. also, am I allowed to use variables in regular expressions?

Thanks in advance


texts: In search for toy relations to test relational algebra

texts: Does anybody know any toy database / relations that are particularly good and also complete to demonstrate and test relational algebra concepts?  I'm hoping some database researchers should have already made that and improved over long time from pedagogical practices.


texts: Direct encoding of the solution into the chromosomes in a Random-Key Genetic Algorithm

texts:
In a random key genetic algorithm1, the chromosomes consist in a sequence of real numbers (initially randomly generated) in the interval $[0,1]$.

I've been told by my teacher that in these kinds of genetic algorithms, one cannot encode the solution directly into the chromosomes, as that would generate "infinitely large" convergence times. Instead, the proposed solution from my teacher is to use the weights in the chromosomes to modullate the construction of a solution through a greedy algorithm. Let me clarify that further with the classical example of the Travelling Salesman Problem:

In a direct encoding (my proposal), with $N=4$ cities, a chromosome with values $[0.1, 0.7, 0.4, 0.9]$ could be decoded in order to determine the order in which to visit the cities, which would become $1 \rightarrow 3 \rightarrow 2 \rightarrow 4$.

The other approach consists in constructing a solution by means of a regular greedy algorithm. For example, starting from the initial location, a simple greedy algorithm for the TSP would select, at each iteration, the closest city for its next step. In order to fit the chromosomes in this schema, when considering going to the next city, one would multiply the distance to the considered location by the value of the allele for that city, essentially changing the values of the greedy function with the chromosome's genes.

So my question would be:

Is this kind of "modullating a greedy" chromosome encoding widespread in the literature? I couldn't find any examples. I find it surprising that it works well, because when using a greedy there's no way to explore the whole solution space, and the variations in the chromosomes arising from crossover are probably going to end up generating the same greedy solutions all the time.
Is the first kind of encoding (the direct one) something unacceptable for a random-key genetic algorithm? Would something similar be unacceptable as well for a regular (as in, more generic) genetic algorithm?


texts: Pumping Lemma for irregular language, how to choose and divide the string

texts:
The language on the alphabet $\{a,b\}$ is $$L=\{ab^nab^{n+1} |n>0\}$$

so i have to take a string w = xyz:

what's the best string to choose such that $|w| > n$? and then what about the division?

like $ w=ab^nab^{n+1}$ is a correct option? Then how can I divide this into three pieces? My attempt:

$ x = ab^s $ with  $ 0 ≤ s ≤ n -1 $

$ y= b^ta $   with   $  0 < t ≤ n - t $

$ z = b^k $   with        $ 0 ≤ k < n - t - s $


texts:
Given a set of two-dimensional rays, how can I determine the probable focal area of the rays?

For simplicity, assume a circle focal area.

Imagine a number of people throwing paper airplanes at a circular target. Some small percent are throwing in the completely wrong direction.

Is there any algorithm that can help me determine a circle (or ideally polygon) of the intended location of the rays?


texts: Solving cycle in undirected graph in log space?

texts:
Setting

Let:
$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$

My Solution

we show $UCYLE \in L$ by constructing $\mathcal M$ that decides $UCYLE$ using $L$ space.

$\mathcal M = $"On input $<G>$ where $G = (\mathbb V, \mathbb E)$:

For each $v_i \in \mathbb V$, for each $v_j \in Neighbor(v_i)$, store the current $v_i$ and $v_j$.
Traverse the edge $(v_i,v_j)$ and then follow all possible paths through $G$ using DFS.
If we encounter $v_k \in Neighbor(v_i) / \{v_j\}$ so that there is an edge $(v_i,v_k) \in \mathbb E$, then ACCEPT. Else REJECT."

First we claim $\mathcal M$ decides $UCYLE$. First, if there exists a cycle in $G$, then it must start and end on some vertex $v_i$, step one of $\mathcal M$ tries all such $v_i$'s and therefore must find the desired vertex. Next, suppose the cycle starts at $v_i$, then there must exists a starting edge $(v_i,v_j)$ so that if we follow the cycle, we come back to $v_i$ through a different edge $(v_k,v_i)$, so we accept in step three. Since the graph is undirected, we can always come back to $v_i$ through $(v_i,v_j)$, but $\mathcal M$ does not accept this case. By construction, neither does $\mathcal M$ accept if we come upon some $v_k \in Neighbor(v_i)/\{v_j\}$ but there is no edge from $v_k$ to $v_i$.\newline

Now we show $\mathcal M \in L$. First if the vertices are labled $1,\ldots,n$ where $|\mathbb V| = n$, then it requires $log(n)$ bits to specify each $v_i$. Next note in $\mathcal M$ we only need to keep track of the current $v_i$ and $v_j$, so $\mathcal M$ is $2 log(n) = O(log ~n) \in L$.

My Problem

My problem is how do you perform DFS on the graph in $log(n)$ space. For example, in the worst case where each vertex has degree $n$, you'd have to keep a counter of which vertex you took on a particular path, which would require $n \log(n)$ space.


texts:
So I have grouped the following formalisms into a power hierarchy (and made classes for them):

Class 1

DFA
NFA
NFAϵ
reg.exp

Class 2 (DCFL expressivity?)

LR(1)
DPDA

Class 3

CFG
PDA

Class 4

TM
NTM

Class 4 is the most powerful class and Class 1 is the least powerful.
Now I want to compare them to LR(0) parsers. My current intuition is that LR(0) parsers can handle all of Class 1 (and probably belongs to class 1). Class 2 has more power than LR(0) due to the fact that LR(0) defines a subset of Class 2 (DCFL's with the prefix property).

So I guess the question is, should LR(0) parsers be put into its own class or should it go into Class 1 (which would be my guess).


texts:
I want to write the following constraint:
If A=1 and B <= m then C=1 ( where A and C are binary, m is a constant and B is continuous).


texts:
I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG?

For example: to write CFG for the automata

My attempt:

$S=A_{03}$ because $q_{\color{blue}0}$ is the initial state and $q_{\color{blue}3}$ is the final state.

There are $4$ states so we will have $4^2$ variables:

$$A_{00},A_{01},A_{02},A_{03},\\
A_{10},A_{11},A_{12},A_{13},\\
A_{20},A_{21},A_{22},A_{23},\\
A_{30},A_{31},A_{32},A_{33}$$

for each state $q_{i}$ of the automata $A_{ii}\to\varepsilon$

$$A_{00}\to \varepsilon\\
A_{11}\to \varepsilon\\
A_{22}\to \varepsilon\\
A_{33}\to \varepsilon\\$$

For each triplet of states $q_i,q_j,q_k$, we add the rule $A_{ij}\to A_{ik}A_{jk}$, this gives us $4^3=64$ rules:

$$A_{00}\to A_{00}A_{00}|A_{01}A_{10}|A_{02}A_{20}|A_{03}A_{30}\\
A_{01}\to A_{00}A_{01}|A_{01}A_{11}|A_{02}A_{21}|A_{03}A_{31}\\
A_{02}\to A_{00}A_{02}|A_{01}A_{12}|A_{02}A_{22}|A_{03}A_{32}\\
\vdots\\
A_{33}\to A_{30}A_{03}|A_{31}A_{13}|A_{32}A_{23}|A_{33}A_{33}\\$$

I am stuck here.


texts: In-place matrix transposition using rotations

texts:
Some time ago I invented an algorithm for in-place matrix transposition using rotations.

A matrix of size N×M is represented as a one-dimensional array of size N*M, which is also the future storage for the corresponding transposed M×N matrix.

The algorithm moves an element to its proper position in the representation for the transposed matrix rotating the sub-array of the array 1 element right, starting at the correct and ending at the current position of the element.

Let matrix be the array of size N*M, where N and M are the number of rows and columns in the original matrix (and the number of columns and rows in the transposed). Array indices are from 0 to N*M-1.

Let dst be the proper position for the element in the array for the transposed matrix, src — its current position, src_inc is the value addet to src to point to the "current position" of the next element to be moved. The algorithm starts with dst = 1, src_inc = M and src = dst + src_inc - 1 (which is equal to M) (The element at the 0-th position is already in its right place). After the first rotation, we increment dst by 1 and src by src_inc (which is M) until dst points to an element which should not be moved. This happens when (dst + 1) % N is 0. In this case we skip the element (incrementing dst again), decrease src_inc by one and restore the initial relation between src and dst — src = dst + src_inc - 1.

Let me, instead of writing a pseudo-code, show the C++ code and add a state of the array before each rotation (plus the final result)

#include <algorithm>

template<typename T>
void inplace_transpose_using_rotations(T* matrix, int N, int M)
{
    int dst = 1;
    int src_inc = M;
    int src = dst + src_inc - 1;

    while (src < N*M && dst < src)
    {
        std::rotate(matrix + dst, matrix + src, matrix + src + 1); // rotate right for 1 position
        if ((dst + 1) % N != 0) {
            dst += 1;
            src += src_inc;
        } else {
            dst += 2;
            src_inc -= 1;
            src = dst + src_inc - 1;
        }
    }
}

(https://wandbox.org/permlink/XAWE1Fn64SxvEvth)

Original 3×5 matrix:

11 12 13 14 15
21 22 23 24 25
31 32 33 34 35

The trace (the first row is indices, the matrix is represented linearly, dst and src to the right are shown before the rotation, the result of the rotation is on the next line):

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
11 12 13 14 15 21 22 23 24 25 31 32 33 34 35 | dst = 01, src = 05
11 21 12 13 14 15 22 23 24 25 31 32 33 34 35 | dst = 02, src = 10
11 21 31 12 13 14 15 22 23 24 25 32 33 34 35 | dst = 04, src = 07
11 21 31 12 22 13 14 15 23 24 25 32 33 34 35 | dst = 05, src = 11
11 21 31 12 22 32 13 14 15 23 24 25 33 34 35 | dst = 07, src = 09
11 21 31 12 22 32 13 23 14 15 24 25 33 34 35 | dst = 08, src = 12
11 21 31 12 22 32 13 23 33 14 15 24 25 34 35 | dst = 10, src = 11
11 21 31 12 22 32 13 23 33 14 24 15 25 34 35 | dst = 11, src = 13
11 21 31 12 22 32 13 23 33 14 24 34 15 25 35 | final array

(the code producing the trace https://wandbox.org/permlink/3nhlwYoSz5GnWuUP)

And transposed matrix (reinterpretation of the array as a representation for a 5×3 matrix):

11 21 31
12 22 32
13 23 33
14 24 34
15 25 35

The algorithm is not optimal, it does  swaps (assuming the rotation is implemented as a chain of swaps), but it is short and seems to work.

However, I couldn't prove why it should work. I was just curious to try to transpose a matrix using rotations instead of chain of swaps following cycles and discovered that there is a relatively simple law how to select the next sub-array for rotation. Is this algorithm published anywhere?


texts: Given an antisymmetric matrix, how do I find a set of rows that maximizes function?

texts:
Let $P$ be an $m \times m$ antisymmetric matrix of the form:
$$
\begin{bmatrix}
0 & p_{1,2} & ... & p_{1,m} \\
-p_{1,2} & 0 & ... & p_{2,m} \\
\vdots & \vdots & \ddots & \vdots \\
-p_{1,m} & -p_{2,m} & \dots & 0 \\
\end{bmatrix}$$

with $p_{i,j} \in [+1,-1]$, how can I find a set $I^*$ of matrix rows that maximizes the following function:
$$
f(I) = \left( \sum_{i \in I} \sum_{j=0}^{m} p_{i,j} \right)^2 + \sum_{i \in I} \sum_{j \in M \setminus I} \left(1-p_{i,j}^2\right)
$$

Obviously, an exhaustive search requires $2^m$ steps but I was wondering if it is possible to do better. I was thinking about dynamic programming but was unable to come up with a solution.

Let $I_0^*=\{\ \}$, i.e. the empty set, be the solution for all sets of size zero. For sets containing only one row it is easy to find $I_1^*=\max_k f(I_0^* \cup \{\ k\})$ as one can just compute the function value for each row $k$ separately.

If I do:
$$I_h^* = \max_{k \notin I_{h-1}} f\left( I_{h-1}^* \cup \{\ k\} \right)$$
I end up with a greedy solution which, from testing, does not appear to exhibit the best solution. I am not sure if the problem lacks optimal substructure. So is there any better solution?


texts: Can we solve an EXPTIME-complete problem  in polynomial time given 2^N processors?(N is the size of input).


texts: Changing a matrix to become an ancestry matrix

texts:
An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some rooted tree (and create the tree) or not.
The question is if $X$ is not an ancestry matrix, how hard is the problem of modifying elements of $X$ so that it becomes an ancestry matrix. The aim is to modify as few elements as possible.
Note 1: Stated problem can be seen as using Hamming distance on the matrices. A related problem  would be: "For what metrics on the matrices this problem can be solved efficiently?"
Note 2: $X$ can be assumed to be a matrix containing only 0 and 1 elements. But a more general form of $X$ is more desirable!
Note 3: Any results about some characteristic matrix like adjacency matrix instead of ancestry matrix would be appreciated!


texts:
For a given acyclic graph $G$, a topological sort is an ordering $v_1, \dots, v_n$ of the vertices such that the arrows in the graph are all directed forward under that ordering.

Question: can all topological orders of a graph $G$ be obtained from a single ordering by iteratively swapping two vertices that are not connected by an edge?

Motivation. In a certain context I am trying to prove that all topological sorts of an acyclic graph are in fact "equivalent". I want to do this by comparing $v_1, \dots, v, v', \dots v_n$ and $v_1, \dots, v', v, \dots v_n$ where there is no edge between $v,v'$.


texts:
I'm having some trouble figuring out where the "Carry in" value comes from in respects to a one bit full adder diagram.  I understand the below half adder,

but my question is: is the the output of the bottom-most AND gate in the bottom diagram equal to the output "C" in the top diagram (Assuming A and B are constant throughout) - Is Cin from the bottom diagram equal to C in the top diagram?


texts: Is it possible, at least in theory, to "lockfree-ize" algorithms algorithmically?

texts:
The problem emerged from a practical case, but thinking on it resulted more and more theoretical directions.

Typically, the lock-free algorithms do relative simple things in the practice, but their implementation is already not very simple. It has mainly debuggability reasons. However, it shouldn't be so, if there would be a way to construct lock-free algorithms automatically.

Consider we have:

a (not very big) set of simple atomic operations
a not lock-free algorithm, which uses exclusively these atomic operations, but itself is not lock-free. We can formally specify:

what the algorithm does (= how the result depends on the initial state)
how does it (= essentially the executed operations)

Is it, at least in theory, possible, to construct a lock-free version of the same algorithm algorithmically, if it is possible?

I think, if the answer is "no" in the general case, maybe it can be still possible with an (ideally, not very strict) condition on the algorithms, or on the operations.


texts: DFA for even number of As, odd number of Bs and precisely one C

texts:
Exactly as the title says, I'm looking for a DFA for an even number of A, odd number of B, and exactly one C, can anyone help with this?

Thanks


texts: Finding the shortest path for synchronized pawns in a maze

texts:
I have been trying to wrap my head around this problem, and I just can't get it.

We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, denoted with $X$.
There are two pawns in different locations within the maze, their movements are synchronized and they must leave the maze (it has multiple exits) in the same move.
If one moves and the other is up against a wall, it's a valid move and the other one stays in place.
The goal is to write an algorithm that finds the lowest possible moves to get both out of the maze at the same time, of time complexity $\mathcal O(a^2 b^2)$.

I got some advice to use BFS for this problem, but I don't get how it would deal with all of the backtracking that has to be done. I've included two visualizations with the correct paths labeled to help explain the problem.

Example 1: Pawn starting positions shown as blue squares

Example 2: Pawn starting position shown as blue square and red square


texts: Would models of computation in other conceivable universes be Turing complete?

texts:
I'm interested in gathering some references that discuss the topic of the relationship between computation and physics.

Specifically, I'm interested in investigating two points of view:

our current model of computation -- assuming it describes reality accurately -- impose a limit on what is physically possible. To me this is essentially the argument that Max Tegmark makes with his Mathematical Universe Hypotheses
the physics of our universe put limits on our models for computation. Are the limits of our models for computation a direct consequence of the laws of physics?

It seems to me that these two points of view are not the same, however I lack the necessary background to really tell. I know about Tegmark but I don't know any references on the second point of view.

I am aware of the physical limits of computation in the sense that there are the limits of how fast computers can run, or how small we could theoretically build them; however, our models of computation are substrate independent and their fundamental limits are not imposed by physical properties like speed, or scale. The limits more fundamental, e.g., undecidability, the halting problem.

I wonder if these type of limits of our models are a consequence of the structure of brains, i.e. their physical properties.

Perhaps this question is ill-posed but I'm only looking for reading materials so I can hopefully formulate better questions.


texts: Why are multi-threading programs more prone to errors?

texts: Why are multi-threading programs more prone to errors than single threaded programs ? or why is multi-threading programming one of the areas where developers are (more) prone to errors? Is this in general or is it valid only for scenarios where there are shared resources being used by multiple threads ? Are the difficulties to detect errors or simulate bugs in multi-threaded programs just related to inexperience or immature tool support, or are they fundamentally more difficult than the same tasks for single threaded programs ?


texts: Find set of points with maximum distance inside given intervals?

texts:
Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum distance between all pairs of points is maximized?

Assume that the intervals are bounded by a positive integer $C$.

What's the complexity of this problem?

If the intervals are non-overlapping, I know how to solve this with linear programming (indeed, using a system of difference constraints and Bellman-Ford), but what can we say about the general case where intervals might overlap?

Note: Most comments/answers so far are looking for a polynomial solution. Note that it is possible that this problem is NP-complete. I know that it was  the style of this teacher to include problems for which students had to prove NP-completeness.


texts: Is the minimal number of colors needed to color a graph some fixed number?

texts:
Consider to following decision problem:

Input: Undirected graph $G=(V,E)$
Question: Is the minimum numbers of colors needed to color the vertices  (such that every two adjacent vertices aren't colored the same) exactly 2015?

Note that 2015 could be any fixed number. This number is not part of the input.
I need to understand what is the minimal complexity class that contain this problem, between $\sf P,NP,coNP,NP\cup coNP,\Sigma _{2} \cap \Pi _{2}, \Sigma _{2} \cup \Pi _{2}$.
I don't it's $\sf NP$ or $\sf coNP$ since I can't think of a verifier for both the language or it's complement. The problem is maybe in $\sf \Sigma _{2} \cap \Pi {2}$ since we can think of it as

exists $f$ some 2009-coloring function, for-all $g$, 2008-coloring function, $f$ is a correct coloring and $g$ isn't a correct coloring.

So by the above, it seems that the language is in $\sf \Sigma _{2}$, but the quantifiers order doesn't really matter here, so the language is also in $\sf \Pi _{2}$, I think.
And maybe the there is some deterministic polynomial-time algorithm?


texts: Search Heuristics Where the Search Space Has No Gradient

texts:
If I'm not mistaken, search heuristics rely on problems where the best answer is very close to pretty-good answers. For example, the traveling salesman problem. If there is a route which is the optimal except for a small anomaly somewhere, where the route isn't quite optimal, the algorithms still says that's "pretty good" and continues searching that space until it finds the optimal. I'm going to call this "gradient" because there isn't a sharp difference between optimal and something where everything is optimal except for a small part.

What happens if there is no "gradient"? For example, let's say I wanted to develop some electronic circuitry using a search heuristic. This probably isn't done much, or at all, but bear with me. The optimal circuit would be one which, say, does addition. But, if there is one small difference, like an AND logic gate instead of an OR gate, it doesn't perform at all and produces a terrible result. Now, in traditional search heuristics, it would probably drop this and say "this isn't even close to optimal". It has no way of telling whether something is close to optimal or far away to optimal, because there is really only one circuit that produces good results, and everything else fails miserably.

So what should I do in these situations? By the way, the circuit thing isn't my problem; just a way to demonstrate my issue.

Phrased Differently What does a search heuristic do when it has no way of "grading" how good a given state is, and only the optimal state produces good results? Everything else, no matter how close to the optimal, produces terrible results.

BONUS: What other group of algorithms might perform well in these situations?


texts: Time complexity of rotation array m times using temporary array

texts:
I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the space complexity is O(m) where m is the number of times the array needs to be rotated. But the time complexity is given as O(n) where n is the size of the array. But I found that the time complexity should be O(n+m)

Input arr[] = [1, 2, 3, 4, 5, 6, 7], m = 2, n =7
1) Store d elements in a temp array
   temp[] = [1, 2] // It takes m iterations to copy the array
2) Shift rest of the arr[]
   arr[] = [3, 4, 5, 6, 7, 6, 7] // n-m iteration for shifting
3) Store back the d elements
   arr[] = [3, 4, 5, 6, 7, 1, 2] // m iterations for storing the elements back

Here is how I calculated time complexity

=> m+(n-m)+m

=> O(n+m)

Can anyone help me to figure out what I am doing wrong?


texts: Find all nodes on simple paths between two nodes in cyclic directed graph

texts:
Given two nodes U and V in a cyclic directed graph, how can I find the set of nodes that are part of a simple path from U to V?

Attempt 1

I've tried using a DFS from U that stores the set of visited nodes when V is reached, and backtracks when a cycle is detected. But this algorithm must traverse all paths, and can hence be very slow for large graphs.

I cannot stop the DFS early when a node that has already been deemed to be part of a simple path is reached:

If the DFS goes U -> A -> B -> C -> D -> E -> V, those nodes are deemed to be part of a simple path. After backtracking to E and traversing to F and A, a cycle is found. After backtracking to U and traversing to C, a node that is already part of a simple path is found, but the DFS cannot stop, since further traversal is necessary to figure out that F is also part of a simple path: U -> C -> D -> E -> F -> A -> V.

The same argument shows that I can't stop the DFS early when a node that has already been deemed to be part of a cycle is reached.

Attempt 2

Another idea I've tried is to store on the edges sets of potential cycle root nodes that must be traversed in order to reach V from the edge's sink. For instance for the edge E -> F, A must be traversed in order to reach V. Hence the DFS does not have to traverse this edge if A has already been visited.

It is not straight-forward to decide which nodes are potential cycle roots, and on which edges they need to be stored. My implementation attempts have unfortunately been too slow for large and complex graphs. After the potential cycle roots have been calculated, however, performing the DFS has been fast.

Question

Are there any efficient algorithms for finding the set of nodes that are part of a simple path between two nodes?

Examples

Just to make things really clear, these are the outputs I am looking for for a few different graphs:

Example 1

Nodes that are part of simple paths: U, A and V.

Example 2

Nodes that are part of simple paths: U, A, B, C, D, E and V.

Example 3

Nodes that are part of simple paths: U, A, C, D, E, F and V.

Example 4

Nodes that are part of simple paths: U, A, B, C, D, E, F and V.


texts: Is there relation between K-Framework and structural operational semantics?

texts: K-framework strives to give one (instead of two - operational and denotational) semantics for industrial programming languages. The same unification is done by structural operational semantic as well. Are those two frameworks related somehow? Such relation could be very frutiful, because K-framework has excellent tools and full completed semantics, but SOS has deep theory and connection with category theory.


texts: Deciding whether a Language is Context-free/Regular/Non Context-Free

texts:
I need some help with deciding if a given language is regular, context-free or not context-free.

Lets' say I have the following languages over the alphabet $\mathcal{A} = \{a,b,c,d\}$:
$$ \begin{align}
  L_1 &= \{ w \in \mathcal{A}^* \mid \text{\(\#a(w)\) is even and \(\#b(w) = 1 \mathrel{\mathrm{mod}} 3\)  and  \(w \not\in \mathcal{A}^* abc \mathcal{A}^* \)} \} \\
  L_2 &= \{ w \in \mathcal{A}^* \mid \text{\(\#a(w)\) is even and \(\#b(w) \lt \#c(w)\)} \} \\
  L_3 &= \{ w \in \mathscr{A}^* \mid \#a(w) \lt \#b(w) \lt \#c(w) \} \\
\end{align} $$

This is my solution:

$L_1 = L_4 \cap L_5 \cap L_6$ where
$$ \begin{align}
  L_4 &= \{ w \mid \text{\(w\) does not have a substring \(abc\)} \} \\
  L_5 &= \{ w \mid \#a(w) \text{ is even} \} \\
  L_6 &= \{ w \mid \#b(w) = 1 \mathrel{\mathrm{mod}} 3 \} \\
\end{align} $$

A DFA can be constructed for $L_5$, because $L_5$ does not need infinite memory, so $L_5$ is regular. For $L_6$ the same reasoning as above. And for $L_4$ we can construct a DFA that simply does not accept $abc$, hence regular.

$L_1$ is regular because regular languages are closed under intersection.

For $L_2$ we can divide the language thus: $L_2 = L_5 \cap L_7$ where

$$ \begin{align}
  L_5 &= \{ w \mid \#a(w) \text{ is even} \} \\
  L_7 &= \{ w \mid \#b(w) \lt \#c(w) \} \\
\end{align} $$

We now that a DFA can be constructed for $L_5$, hence $L_5$ is regular.
$L_7$ is context-free because we can construct a PDA where the stack counts the number of $a$s and $b$s.

$L_2$ is hence context-free because the intersection of a regular language and a context-free language result in a context-free language.

For $L_3$ we can see that it's not context-free because where are limited to 1 stack.

Is my reasoning right?


texts:
Suppose $G$ is a connected graph and $S$ is a vertex cover. Prove that $S$ is also a dominating set.

Can I get some help with proving this? I know that a dominating set in an undirected graph $G=(V,E)$ is a subset $S$ subset of $V$ such that every vertex is either in $S$ or has a neighbor in $S$.

I know that a vertex cover is always going to be a dominating set because a vertex cover set is such that every edge has a vertex in the set, which means that a vertex not in the set (so on the other end of the edge) must have a neighbor in the set in order for all edges to be covered...

I just don't know how to write this as a proof.


texts: How computer understand to either represent the original bits or two's complement as value?

texts:
Important note

I know that this question may seem too simple for you scientists; however, here is the best place that I know to post it.

Question

Suppose we have an int with all bits being 0, except for the last which is 11101000. How does my computer understand to return its two's complement i.e. -24 as value and not its original value i.e. 232?

Edit: Question Details

I have written the following simple C++ code which shows unsafe conversions:

int main()
{
    double d = 1000;
    {
        int i = d;
        char c = i;
        cout << c;
    }
}

The code returns -24 for c while the last byte of i which is the value of c is 11101000; Actually -24 is its two's complement, i.e. 00011000.


texts: How Segment trees are used to answer interval stabbing query?

texts:
Can anybody explain to me how segment trees are used to answer interval stabbing queries? I have searched and searched and only come with the beginning of the line.
From my understanding I need to take all the end points of every interval and build a segment tree then what?

How can we know the original intervals now?
How can we check whether a given point is present in any of them and report all those intervals with the point in them?


texts:
I'm trying to map a 12 digit number into a fixed width file.  For a number of reasons, it must be compressed in such a way that it is guaranteed to be less than or equal to 9 characters (alpha numeric is fine).  My first thought was a change of base, but I can't find an equation which gives an upper bound the number of characters needed for a given base.

For example, transforming into base 32

123456789101 -> 3IV9I6JD

Which is 8 digits.  How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?


texts: A greedy algorithm for the bottle filling problem

texts:
(There’s no need to write the algorithm, I just need help with the greedy choice).

Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We want to poor water between the bottles so that as many bottles as possible will be filled (Li = Ci) but doing so while moving a minimal amount of water.
Write a greedy algorithm that will print instructions on how to do so (poor x liters from bottle i into bottle j). Prove correctness of your algorithm, and give its time complexity.

I’m having trouble solving this problem. We need to write a greedy algorithm, and so the solution is of the type:
 “take bottle with certain property x and poor as much as you can (until it’s empty or until the other bottle is full) into bottle with certain property y”.
But putting in all of the simple properties don’t seem to work and can be refuted with a counter example.
Any ideas?


texts: I recently attended a lecture on an introduction to computation complexity and I am looking to find out more, I haven't studied computer science or discrete mathmateics at university and I was wondering if anyone could recommend any relatively simple books or reading material that could help me understand the topic more


texts: Complexity of bitwise AND operation on bit string regular expressions

texts:
Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time of performing a bitwise AND operation on $B_1$ and $B_2$?

For example, given two regular expressions, $B_1 = ((10)^2(01)^2)^2$ and $B_2 = (01)^8$, the resulting pattern $R$ of the AND operation would be $R = ((0^4(01)^2)^2$.

Does there exist an algorithm that will run in polynomial time (with respect to the lengths of the regular expressions)? Note, you can pair every possible combination of groups in $O(n^2)$ time, where $n$ = $\max(|B_1|,|B_2|)$, and $|B_i|$ is the length of regex $B_i$.  However, that still does not give you the resulting bit string regular expression $R$.

The exponent $k$ of a given substring can be stored in binary form, so it only adds $\log(k)$ bits to the representation.  Furthermore, note that given any two groups of size $m$ and $n$, there are at most $\max(m,n)$ bit patterns of length $\min(m,n)$ that can result.  In addition, if there are $g_1$ groups in $B_1$ and $g_2$ groups in $B_2$, then there can only be $g_1 g_2$ unique pairs of groups.  Therefore, I think it can be concluded that the space required is at most $O(g_1 g_2 \max(|group_{i,B_1}|,|group_{j,B_2}|)^2)$, which is polynomial in $n$.  However, I am still missing the proof that the resulting regular expression can be found in polynomial time.

For slightly easier problem, you can assume that every repetition is a power of two.  However, that does not necessarily mean that groups are power of two in size.  For an even further simplification you, could assume the groups are also a power of two in size.

Now that I think of it, I will include this idea which I just came up with.  You can represent the offsets of the 1s every group as set of linear integer equations.  Then you may be able to find solutions to pairs of integer equations with constraints somehow?  Or am I over complicating it?

Another possibility is, as Yuval Filmus suggests, convert to NFA.  However, I am not clear why an NFA would be needed since these are fixed sequences (that is, the number of repetitions is fixed).  Furthermore, I am not sure how one would apply the AND operation after they are in NFA form.


texts: LaTex Text Justification badness penalty

texts: I had been going through dynamic programming concepts and happened to read about text justification problem in which the spaces to the right of the line end are penalized with cubic times the number of spaces. The algorithm also works with quadratic times number of spaces as penalty. I have couple of questions 1) Any idea why this works with both cubic & quadratic? 2) Why it should be cubic or quadratic why not just linear?


texts:
I've been given the following problem in an interview (that I've already failed to solve, not trying to cheat my way past): The game starts with a positive integer number $A_0$. (E.g. $A_0 = 1234$.) This number is converted to binary representation, and $N$ is the number of bits set to $1$. (E.g. $A_0 = b100\ 1101\ 0010$, $N = 5.$)

Player 1 chooses a number $B_0$ lesser than $A_0$. $B_0$ must have only one bit set to 1. (E.g. $B_0 = b10\ 0000\ 0000 = 512$.) Let $A_1 = A_0 - B_0$. (E.g. $A_1 = 1234-512 = 722 = b10 1101 0010$.) A move is valid if $B_0$ satisfies the previous constraints, and if the number of bits set in $A_1$ is still equal to N.

Player 2 continues from $A_1$ by choosing a valid $B_1$, then player 1 continues from $A_2$, and so forth. A player loses if they have no valid moves left.

Assuming both players play optimally, determine the winning player using a reasonably efficient method. (In my problem definition, the constraints on this were that the program has to be able to deliver a solution for a few million input numbers that fit into a signed 32-bit integer.) That is, the solution doesn't need to be fully analytical.

My personal interest here is figuring out whether the expectation of me to have found and implemented the correct solution with no way feedback on correctness in the 120 minutes I was given was reasonable; or if this was one of those "let's see if they've seen this puzzle before" questions.

I'd failed because I chose to implement what seemed like a reasonable strategy, that gave me correct results for the few test cases that I've been given up front, wasted too much time making this run fast, and ended up handing in incorrect full output as my time ran out.

In retrospect I should've implemented a brute-force search and memorized partial solutions for small starting numbers, but hindsight is always 20/20. I'm curious however if there's a different common approach that eluded me as a flunkee.


texts: Thompson's construction, The empty-expression

texts:
Why this case exists in Thompson's construction algorithm?

Isn't just a special case of:

where the symbol a is replaced by ϵ?


texts:
I'm a web developer and I struggle to visualize abstract concepts in my head.

By abstract concept, it can be:
- the backend model of a webapp (with several objects inter-connected to each other)
- repeated actions on a data structure (a sort on a array for example)

For example, I  wanted to implement a bubble sort last week.

At first, I tried to imagine an array, in my head.
It contained numbers and I tried to permute the numbers in my head. It was really hard.

Then I draw the permutations, it was still hard.

Then, I watched this excellent video.

The teacher uses real glasses with numbers drawn on it.

I bought some cheap glasses, I draw numbers on them and I tried all the permutations.
Then, after a while, I was able to grasp a pattern, then I turned it into an algorithm that worked well.

In general, I know that I have a hard time representing mental models in my head.
When I draw it, it becomes A LOT easier
And if use real objects (like the glasses), then it's even more easier.

Unfortunately, there are some situations where I have no choice but representing mental models in my head.
For example, in a meeting with several collaborators, where we brainstorm about the different ways we could adapt the architecture of our web app to accomplish a cool feature.

I really want to improve my brain in this area, but I don't know how to do, apart from doing personal challenges with algorithms and designing web app models.

Do you use some specific methods to represent abstract concepts in your head ?

Do you know some books, some exercices or some ways to improve ?

Thank you very much guys.


texts: prove no DPDA accepts language of even-lengthed palindromes

texts:
How do you prove that the language of even-lengthed palindromes, i.e.,
$L=\left\{ ww^R \mid w\in \left\lbrace 0,1 \right\}^* \right\}$, can not be accepted by a determinsitc Push-Down-Automaton?

Is there any general way to prove that a context-free language can not be accepted by a deterministic PDA? I mean something like pumping lemma maybe?


texts: Can multiple tasks in an RTOS share one stack to save memory?

texts:
Many small embedded systems have a limited amount of RAM, 10k or less. I know you can run an RTOS on such systems, however, a realistic number of tasks in such a system is very low, mainly because every task needs its own stack area.
Is it possible to share the space needed for the stack of some of these tasks?
I understand that this is possible in a cooperative environment, such that a task can report its willingness to relinquish the processor (and refrain from using its stack). But in an RTOS you don't normally use cooperative multitasking.
But then, maybe it is sufficient to use non-preemptive tasks when sharing stack space, in a certain way that's also "cooperative" in my opinion.

Can it be done in an RTOS? How?