texts:
One of the main benefits of algorithm analysis, is that it offers asymptotic improvements to complexity as opposed to hardware, which offers only constant improvements. E.g switching to a super computer from a workstation might give a $\times 1,000,000$ increase in speed, but if that supercomputer is running a linear search on a sorted array, it will eventually be trumped by a desktop running a binary search for large enough problem sizes.

My question is this:

  Are there any improvements in hardware(theoretical or practical) that could offer an asymptotic speedup over pre-existing hardware?

In this case pre-existing refers to at least 3rd generation computing technology. I'm not really interested in speedups over vacuum tubes.


texts: Message passing inter process communication

texts:
I was reading a book on OS by Galvin. I well understood that blocking send will wait until it has loaded the message into the kernel buffer. In contrast, the non-blocking send system call will return a check value indicating a successful or unsuccessful event.

Please can someone explain the difference between blocking and non-blocking send system call in the scenario when we are using zero buffer capacity in the kernel? Please answer. Thanks in advance.


texts:
What is a possible data structure $X$ which stores non-negative integers $x_1, x_2, ..., x_n$ which supports the following operations:

$index(k, X)$ returns the biggest $i$ so that $\sum_{i=1}^n x_i \leq k$
$sum(j, X)$ returns $\sum_{i=1}^j x_i$

The data structure should support every operation in $O(1)$ (worst case) and use minimum bits as possible.

All that under the assumption :  $\sum_{i=1}^{n} x_i= 4n.$


texts: Finding a good loop invariant for a powering procedure

texts:
Consider the following algorithm for computing integer powers:

Procedure power(integer x, integer n)
    power := 1
    for i := 1 to n
        power := power * x
    return power

Can we say that the loop invariant is $power \leq x^n$ ?
Before the loop $power$ is initialized to $1$ so its equal to $1 \leq x^n$.

How do we prove maintenance of the invariant?


texts: Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?

texts:
Basic sanity check on NP-complete solutions:

Suppose there was a polynomial time solution for an NP-complete problem,
but the size of NP-complete problems that could be solved is still
relatively small (i.e. N = 32-64) due to limits in technology.

Would this show that P = NP? Or would this be more like the
pseudo-solution that the unary subset sum is in P?


texts: Loading a word from byte-addressable cache

texts:
I have asked a similar question at stack-overflow, but then I found this question here, and figured it should go here instead..
So, my question is pretty much the same as the one in the question I linked:
I know that in a byte-addressable cache, a byte-offset (usually the LSB of the address) is used to determine which byte to access out of the designated cache block.
But, if the offset allows the selection of 1 byte out of the block, we would need 4 subsequent accesses to the cache in order to access a single word (assuming a word equals 4 bytes), and I somehow doubt that's the way things execute in real time.. Any clarification regarding that will be appreciated, as I didn't find an answer to that in the previous question).
Thanks in advance :)
Edit:
To clarify my question - I'm trying to understand how can a Byte-Addressable memory output more than 1 Byte at a time.
I'd understand it if the memory Always outputs a whole word, for example, and the byte is then extracted by the CPU according to the requested address by specifying an offset of 0x0 to indicate that it needs 2 bytes - the 1st and 2nd bytes, 0x1 to indicate it needs the 3rd and 4th bytes, 0x00 to indicate it needs only 1 byte - the first byte, 0x01 to extract only the 2nd byte, 0x02 to extract only the 3rd byte, 0x03 to extract only the 4th byte, and specifying no offset at all to tell the CPU "do not extract any specific bytes - process the word as a whole".  That will make for a nice explanation - But I've seen no indication of anything of the sorts while looking at various CPU implementations..


texts:
I'm solving the end of the chapter problems of Morris Mano's Digital Design (4th Edition, if that's relevant). In one of the problems, it is asked to simply find the 1's and 2's complement of 00000000. It's 1's complement would be 11111111. Now, for 2's complement, adding 1 to will give 100000000. But in the answer key, the answer is 00000000.

I know that if i'm working with a hardware that is only capable of handling 8 bits, the 1 will not be stored. But, in theory, the 2's complement of 00000000 should  be 100000000, right? Or is there something i missed? In the question there was no mention of hardware limitations, or even something like "use only 8 bits".


texts:
Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

This question seems very trivial, but I don't know if the statement is necessarily true for all N > 1 where N is the number of values. It seems intuitively true because any expression with more than one binary operator can be expressed as a combination of two different expressions through induction, but I'm not very confident.


texts: Why is finding minimum number of comparisons to sort $n$ elements so difficult?

texts:
In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as:

  $S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements.

Further, the book regards $\lceil \lg n! \rceil$ as the information theoretic lower bound for $S(n)$.

Using merge insertion they also upper bound the number of comparisons by $F(n)$ where

$$F(n) = \sum_{k = 1}^{n} \lceil \lg \tfrac{3}{4} k \rceil$$

So you can get the bound $\lceil \lg n! \rceil \leq S(n) \leq F(n)$, and for any values $n$ where $\lceil \lg n! \rceil = F(n)$ you can find the exact value of $S(n)$.

My questions are:

Why does $S(n)$ not always match the information theoretic lower bound $\lceil \lg n! \rceil$? It seems like if this is all the bits of information we should need, that this is all the comparisons we would need. Why do they differ?
Why is $S(n)$ so difficult to compute? It's discussed in the book some but the reasons are still unclear to me. Do you have to brute force and create every possible decision tree for a given $n$ and determine the longest path? Is there not a more efficient way? It seems that $S(n)$ has only been exactly computed for $n \leq 22$ (See A036604 here).


texts: Tree - how much elements have the subtree got?

texts:
It's the continuation of the exercise: https://cs.stackexchange.com/questions/65384/tree-elements-influence-on-another-elements-searching-for-specific-elements

I need to say how many elements do I have in specific subtrees.

Input: n - how many elements are in the tree, k - around how many elements should be in the subtree, and then I have got n-1 numbers p, which are saying who is the parent from the node. Node number is the number of the line.

Example Input:

11 4
1
1
2
2
2
3
7
3
9
9
                          1
                        /   \
                       2     3
                     / | \   | \
                    4  5  6  7  9
                             |  | \
                             8  10 11

The question is: how many elements have got the subtree(1) and subtree(2). The subtree(2) should be also the subtree of subtree(1). Subtree(1) has got a number of elements which is greater than k, but the number of elements should be as near as possible to k. Subtree(2) should be the subtree of subtree(1) and its number of elements is equal or less than k, also it should be the as near as possible to k.

                    3
                    | \
                    7  9               subtree(1) - 6 elements >k
                    |  | \
                    8  10 11

                           9               subtree(2) - 3 elements <= k
                           | \
                           10 11

For the Example Input, the answer is: 6 - subtree(1) and 3 - subtree(2).

Why not the subtree which starts from 2? Because:

            2      It has got 4 elements <= k, so I must then take the whole
          / | \    tree which has got 11 elements >k. The subtree(1) has got
         4  5  6   less elements - 6, where k = 4. 6-4 < 11-4.

Why not the subtree which starts from 7? Because:

        7     It has got 2 elements <= k, this is the subtree of
        |     subtree(1), where k = 4. But beside we have got a subtree(2),
        8     which has got 3 elements. 4-3 < 4-2.

I was thinking about:

Storing all the childrens, indirect and direct childrens, for
example, that the node 3 has got 5 childrens, node 9 has got 2
childrens. But I think it's quite slow if I would get the max number
n = 500000, and all of the nodes would have got 1 direct parent,
that would be probably too slow.
Making a normal tree data structure with std::vector, but I don't have any further idea to this.


texts: Are qubits written in a big-endian or little-endian order when grouped?

texts:
Say for instance you layout a quantum simulator like follows:

amps = [0] * 8  # 3 qubits

Therefore you are left with the following in binary:
000, 001, 010, 011, 100, 101, 110, 111

Does the third digit in binary represent the third qubit or the first?

One would assume it would be the third but I'm not certain and I don't want to get the model wrong.


texts:
According to
asked question in this post.
Suppose $T(n,k)=T(n-1,k-1)+T(n-1,k)+1$, now let  $C(n,k)=T(n,k)+1$.
As a result $C(n,k)=C(n-1,k-1)+C(n-1,k)$.
I want to prove
$C(n,k)=2\binom{n}{k}$, now on that post mentioned that use induction to prove equality such that
induction on $k+n$. My problem is when i use induction on $k+n=m$, And define $P(m)$ I can't accurately prove.
For example: when i try to prove $P(2)$, i set  $k=0,n=2$ or $k=1,n=1$ and for $P(2)$ we have two cases. Anyone can help me to prove it
?
$P(m)$  states that whenever $0≤k≤n$ and $k+n=m$ then $C(n,k)=2\binom{n}{k}$


texts: Can I use breadth-first search for topological sorting?

texts:
Can I use breadth-first search for topologicallly sort vertices and finding strongly connected components in a graph?

If yes, how can I do that? If not, why?

I tried with a simple acyclic graph of 3 vertices, gave the start and finish time as we do in DFS and then sorted them in non-increasing order. There was a conflict. The result was topologically sorted.

I find in all books that we use depth first search here. Is there any way that I can modify BFS so that I can topologically sort vertices?


texts: why this recurrence can be solved by Master method?

texts:
I have studied the following recurrence. The ratio between f(n) and n^log_b(a) is log n so there is non polynomial difference but I have studied from book that it can be solved by master method.

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

On the other hand ratio in   $T (n) = 2T (n/2) + n /log n$  is  $1/log n$  so this also has non polynomial difference but it can not be solved by master method. Because of this, I am having confusion in recognizing recurrences which can be solved by master method.
I know what Master method is and how it works. I just want to understand why both of above recurrences cannot be solved by master theorem.


texts: Algorithm of finding relationships between two sets given a bijection relationship between their cosets to another set

texts:
Let $C$ be the set of all available classes, $S$ be the set of all available students, $P$ be the set of all available phone numbers.

Each student many have zero to many phone numbers, but each phone number can only belong to zero or one student. There may have little chance that some phone numbers have no owners at all. To formalize this relationship, there exists a mapping $f:S \to 2^P$, where $2^P$ is the power set, or set of subsets of $P$. In addition, $\underset{s \in S}{\bigcup} f(s) \subseteq P$, and $\forall s_i, s_j \in S$ where $i \ne j$, $f(s_i) \cap f(s_j) = \emptyset$.

Each class can have zero to many students, and each student can take zero to many classes. To formalize this relationship, there exists mappings $g:C \to 2^S$ and $h:S \to 2^C$. In addition, followings hold:

$\underset{c \in C}{\bigcup} g(c) \subseteq S$
$\forall c_i, c_j \in C$ where $i \ne j, g(c_i) \cap g(c_j) \in 2^S$
$\underset{s \in S}{\bigcup} h(s) \subseteq C$
$\forall s_i, s_j \in S$ where $i \ne j, h(s_i) \cap h(s_j) \in 2^C$

Now we have a data set contains records for each class $c \in C$, a subset of students in that class $\sigma \in 2^{g(c) \cup \epsilon_\sigma}$, and a subset of phone numbers owned by all the students in that class $\phi \in 2^{\underset{s \in g(c)}{\bigcup} f(s) \cup \epsilon_\phi}$.

Note that $\epsilon_\sigma$ and $\epsilon_\phi$ are error sets explained later.

Thus, the whole data set is given by

$\{ (c,\sigma,\phi) | c \in C, \sigma \in 2^{g(c) \cup \epsilon_\sigma}, \phi \in 2^{\underset{s \in g(c)}{\bigcup} f(s) \cup \epsilon_\phi} \}$

For a class $c \in C$, there may have little chance that a student actually taking the class $s \in g(c)$ not appeared on the record, $s \notin \sigma$. Thus, we used the notation $\sigma \in 2^{g(c)}$ to denote such absence.
For a class $c \in C$, a student in the class $s \in g(c)$ usually only provides zero or one of his phone numbers, but there may have some odds that a student provided more than one phone numbers on the record.
For a class $c \in C$, there may have little chance that a student not taking the class $s \notin g(c)$ actually appeared on the record, $s \in \sigma$. Thus, we used an error set $\epsilon_\sigma$ to accommodate such odds.
For a class $c \in C$, there may have little chance that a phone number $p \in P$ not belong to any student in the class $p \notin \underset{s \in g(c)}{\bigcup} f(s)$ actually appeared on the record, $p \in \phi$. Thus, we used an error set $\epsilon_\phi$ to accommodate such odds.

Now, we want to find a matching algorithm, let's say, $M:S \to 2^P$. $M$ takes any student $s \in S$, and outputs a set of phone numbers $\Phi \in 2^P$ that seems to have high probability of belonging to $s$, that is, $\forall p \in \Phi, \mathrm{P}(p \in f(s)) \gg \mathrm{P}(p' \in f(s))$ for any $p' \notin \Phi$.

The problem is approximately similar to finding relationships $f$ between $S$ and $P$, given a bijection relationship between their cosets to another set $C$, $\psi : S/C \to P/C$.

I already know a way to implement this algorithm, but I want to know what category of problems it is, or what type of algorithm it’s called, in order to find some papers or implementations for optimizations.


texts:
As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I have roughly understood what matroids are. But how do you use the concept of a matroid for solving a given optimisation problem?

Take, for example, the activity selection problem. What are the steps to use matroid theory for solving the problem?


texts: How are programs split up into pages in Memory Paging?

texts:
I am a bit confused about how the logical addresses are generated in a paging memory architecture and where and when a program is split up into pages.
I understand how logical addresses are translated to physical addresses and everything that happens after that. I just don't understand how a program is split into distinct pages and where and how this happens.
For example, if we consider a non-paging architecture which uses contiguous memory and execution-time binding, a CPU instruction like JUMP 8, where 8 is a logical address, I understand how an MMU with a base register can dynamically relocate a program anywhere in main memory by changing the value stored in base register, while the object code stored in memory is still using the logical address of 8. However, how is this JUMP 8 instruction handled in a paging architecture, as in when will all these simple logical addresses like 8 be converted into logical addresses suitable for paging (with a page number and offset value), does the compiler split the program into pages?
Also, how is the program stored in memory, are the simple logical addresses stored like in execution-time binding, or is the program in memory stored with the paging logical addresses?


texts:
Regarding Processor Direct Cache, what is the proper mathematical technique for discovering how many words are loaded on a cache miss?

For example if you have a direct mapped cache with a total data cache size of 32 words and a direct mapped cache of 4-word blocks. I believe I have a cache index of 8 cache blocks:

32/4 = 8

Example: Finding a block in python:

var1 = 56
print ((var1 / 8)% 8)

The answer: 7

So finding where to store the blocks is simple enough but I'm uncertain on a miss exactly how MANY words will be loaded?


texts: Time Complexity of Simulating CA with TM

texts:
This question is a follow up to the question: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines.

To simulate a CA with a TM, I used a construction which placed a marker on the ends of the input, and modeled each "step" with the transition function. Assuming that $\rho(\text{''blank''}, \text{''blank''}, \text{''blank''}) = \text{''blank''}$, what is the time complexity of simulating a CA? I'm only concerned with the upper bound.

I'm really stuck, any hints would be really appreciated.

Edit: As recommended, I am adding a better description of the algorithm:

On input $w = w_1 w_2 \dots w_n$, have the TM place unique begin and end characters on each side of the input. We model a single timestamp in the CA by multiple steps of the TM. The head sweeps through the taps, replacing its contents with the contents of the CA tape in the next timestamp. We write each character one place to teh right of where it would have been in the CA. Formally, this is:

  there are states $q_{a,b}$ for all pairs of CA states, with transitions in the form:
  $$ q_{a,b} \to^{c \to \rho(a, b, c), R} q_{b,c}$$

after completing a single sweep, return the head to the start of the tape and repeat. Continue unless an accept character is written, in which case, enter the TM accept state.


texts:
Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?
According to what I studied, every DCFL is guaranteed to have an unambiguous grammar though there are multiple grammars generating them.
Every regular language is also DCFL, hence they will follow the same, but I doubt if every grammar corresponding to a DFA is non-ambiguous and that of NFA is ambiguous.


texts: Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)

texts:
Full question: Numbers of the form $a+b\sqrt{q}$, where $a$ and $b$ are nonnegative integers, and $q$ is an integer which is not he square of another integer, have special properties, e.g. they are closed under addition and multiplication. For $q=2$, some of the first few numbers of this form are given: $0 + 0\sqrt{2}, 1 + 0\sqrt{2}, 0 + 1\sqrt{2},\ldots$

Design an algorithm for efficiently computing the $k$ smallest numbers of the form $a+b\sqrt{2}$ for nonnegative integers $a$ and $b$.

(Hint: systematically enumerate points.)

I have the solution available. The first paragraph is: "A key fact about $\sqrt{2}$ is that it is irrational, i.e., it cannot equal to $a/b$ for any integers $a,b$. This implies that if $x + y\sqrt{2} = x' + y'\sqrt{2}$, where $x$ and $y$ are integers, then $x = x'$ and $y = y'$ (since otherwise $\sqrt{2} = (x-x')/(y-y')$).

I just don't see how knowing that $\sqrt{2}$ is irrational helps to reason about the problem, especially how it's a "key fact".


texts: Is finding if a graph has k isolated nodes a NP-Complete problem?

texts:
I was wondering if finding if a graph has k or more isolated nodes is a NP-Complete problem. I found the following problem:

  Prove that the following problem is NP-Complete. Given a set of T
  transactions: $T = \{t_1,t_2,\dots,t_m\}$ where each transaction $t_i$ is a
  pair of banks $(b_{i1},b_{i2})$.  Find if, given an integer value k, there
  is a group of k banks that doesn't perform any of the given T transactions.

I was thinking to proceed this way:

Input complete graph with all the Banks: $G=(B,E)$
Subtract to E the T set, I obtain a new graph, $G'=(B,E\setminus T)$
Find if there's an existing k-clique in $G'$

Is there any more effective way to solve this problem?


texts: Sort arrays $A$ and $B$ of the same elements using only comparisons between an element of $A$ and one of $B$

texts:
Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in different orders.)

$A$ and $B$ are of different types, thus it is not allowed to mix them in the same data structure.

It is not possible to compare two elements that are from the same array with each other. However, given is an ordering $A \times B \rightarrow \{<, >, =\}$ (in words: it is possible to compare an $a \in A$ with a $b \in B$ which will tell whether $a > b$, $a = b$ or $a<b$).

There are no restrictions on space being used.

The task is to sort both arrays.

I think I have found a solution analogous to QuickSort that also has $\Theta(n~\,log\,n)$ best case and $\Theta(n^2)$ worst case time complexity.

My question: Is there an algorithm that runs in $\Theta(n~\,log\,n)$ in the worst case aswell?

My approach:

Facilitate $A[1] = B[1]$ by iterating through $B[2, ..., n]$ and
swapping the element that is equal to $A[1]$ to $B[1]$.
Use that element as a Pivot and, in the fashion of QuickSort, go through $A[2..n]$ comparing the elements with $B[1]$ and vice versa for $B[2..n]$.
Rearrange the pivot so that to the left of it there are only elements that are smaller than the Pivot and all others to the right of them. At this point it is guaranteed that
Do this recursively until reaching a base case in which there is only a single element to be sorted.

Now, as far as I can see, similarly to QuickSort, in the best case we require $log~n$ layers of recursion and in each we have a total of $n$ required for recombination.

However, this has the weakness that if the input is already sorted, we will end up with quadratic runtime.

When using a D&C approach, one has to take care that the two arrays are divided so that the resulting smaller arrays still contain the same elements.


texts: How to solve the following left recursion?

texts:
A common left recursion:

A -> Aa | B

can be solve by transforming it into:

A  -> BA'
A' -> aA' | E

However, I face another similar yet different left recursion when I'm writing my compiler:

A -> (A|B) a

So, my question is, how to solve such left recursion?


texts: Butterfly diagram from Cooley-Tukey algorithm

texts:
I am trying to understand the logic of this algorithm so I can implement my own but I am not understanding this diagram I see appearing many times in a fair few articles on the topic. I am teaching myself so I don't have a computer science degree to help. I understand the general idea behind the algorithm, but this butterfly diagram is confusing me.

How do you interpret this diagram from left to right mathematically speaking? It's so confusing... what are the arrows telling me to do in terms of math operations on the functions?


texts: Shortest path where weights are computationally expensive to calculate

texts:
Suppose we have a function, CalculateEdgeWeight, which is computationally expensive. We want to find the shortest path between two nodes $s$ and $t$ in a simple edge-weighted digraph $G= (V,E)$ where weights of $ij \in E$ are calculated with CalculateEdgeWeight($ij$).

Is there a shortest path algorithm that does not require the knowledge of all edge weights by the end of the algorithm so that the use of CalculateEdgeWeight is minimized? What if we have bounds on the possible weights?


texts: I had a simple probability question: suppose we have two coins, coin 1 is heads with probability $= 10\epsilon$ and coin 2 is heads with probability $=\epsilon/10$. Given an unknown coin, how many times do I need to flip the coin to decide which coin I have been given? I feel the right answer is $\Theta(1/\epsilon^2)$, but I don't see how to prove it.


texts: Is there any difference between expected polynomial time and randomized polynomial time algorithm?


texts: Proof that "the last vertex in any postordering (in a DFS) of G lies in a source component of G"

texts:
From the book Algorithms (Jeff Erickson), there's a lemma that states:

The last vertex in any postordering of G lies in a source component
of G

My initial reaction to this was that the proof would look something like this:
A DFS creates an acyclic directed graph.
A postordering of an acyclic directed graph is a reverse topological sort.
Say that the last vertex in a postordering of a graph G, vl, is not in the source component S.
Choose a vertex vs in the source component. Since vs is in a source component, it must be able to reach all vertices in the graph.
If vl is last in the postordering, then it is first in the topological sort of the DFS spanning tree, meaning that there exists a path from vl to any vertex after it, which must include vs. If vl can reach vs and vs can reach vl, then S must be the same component as C.
The proof in the book is not very similar, so I want to know if any part of my proof in wrong.


texts: Given a graph $G$, I want to find a shortest tour visiting each vertex. Different to the classical formulation of TSP, my tour needs to be divided into several subtours, each upper-bounded by a certain length. We can imagine that the salesman needs to return to the starting point to refill its car. The problem is to find the globally shortest TSP tour. Is there any TSP variant that is related to my formulation? My problem is clearly NP-hard, I'd like to design constant-factor approximate algorithm approaching the optimum.


texts: How to prove that if the set and its complement are recursively enumerable, then both are recursive?

texts:
How to prove that if the set and its complement are recursively enumerable, then this set and its complement are recursive?
My idea is that we can make the characteristic function of recursively enumerable set to be a total function using characteristic function of the complement (we can compute both $\chi_A$ and $\chi_\overline{A}$ step by step, alternating steps between them, and when either one stops, we can determine if the element belongs to the set $A$ or its complement).
Is it right?


texts: Local variables get assigned global addresses based upon call tree

texts:
When working with certain low-powered / embedded CPUs that are bad at using the stack, I need to avoid putting local variables there, instead opting to make them static variables. But this can waste a lot of address spaces since not every local in every function needs their own unique address. Rather, by looking at the call tree, functions that do call each other can share memory space.

For example, given code such as this:

void A() {
    int x;
    // ...
    B();
    C();
    // ...
}

void B() {
    int y;
    // ...
}

void C() {
    int z;
    // ...
}

The variables y and z can be assigned the same address, while x should be unique so that calls to B() and C() don't clobber it.

Obviously this breaks recursion and multi-threading, but neither of those are a problem for the use cases I'm working in.

Is there a name for this algorithm? I'm assuming that it's well known, but it's very hard to search for information about this specific problem.


texts: Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular?

texts:
I have no idea how to approach this problem, could I get at least a hint on how to go about proving/disproving this?

I've tried the pumping lemma but I don't think it applies here. I've also tried reasoning about closure properties, but I think my reasoning is faulty. My thought process so far is a string (with length divisible by 3) that is in L can be denoted as a regular expression. As such, the machine M for L can be broken down into M1, M2 and M3, each a machine for handling the first, middle and last thirds of the string. M2 would therefore be the machine corresponding to J, so J is regular.


texts:
Soon I will have an exam where I will be asked to calculate pagerank. So far, I have been thought to use power iteration. However, this can be a very expensive operation to do during an exam, especially when most of the times, the number of nodes is just 3.

Is there any better algorithm to calculate the pagerank of only 3 websites involved?


texts:
There is a language:
$L=\{w: w\in \{a,b\}^*, |w|_a\ \equiv |w|_b \equiv  0$ $(mod$ $5) \}$. My idea for DFA is - we count number of $a$$\pmod{5}$ and separately we count number of $b$$\pmod{5}$. So we end up with $5*5=25$ states, because each state have to keep track for both number of $a$ and $b$$\pmod{5}$. Is there any better aproach to this DFA ? Because for example when we have$\pmod{10}$ we end up with 100 states. I would appreciate any sugestions.


texts:
We know that for problems in NP if the problem is an yes version then there is a short certificate and for coNP if the problem is a no version then there is a short certificate.

Is there a short certficate analogy for higher levels in Polynomial Hierarchy?


texts: PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

texts:
On my compilation theory exam we had the following problem:
Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,m \geq 0$$
I cant think of any solution. My approach was as follows: I would put in the stack  $m+n$ symbols of $a$. Then, for every $b$ in $b^n$ I would remove one $a$. Then I would be left with $m$ symbols of $a$ in the stack. After, that, I would emit two symbols of $x$ and I would empty the stack. For every $a$ that was left I would emit two symbols of $x$.
I could not figure out how to obtain the second part because in order to determine $m$ I would need subtract the $n$ from $b^n$.
By PDA translator I mean a regular PDA but instead of accepting/rejecting a language, we use it to transform a language into another (every transition in the automaton can emit some symbols).


texts: Issues with using greedy algorithm (Interval scheduling variant)

texts:
I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.

I have a set of jobs with start and finish time and I want to find the smallest subset of this jobs such that all the jobs are incompatible with at least one job of this subset.

Suppose

job  start   end
1    1       3
2    2       11
3    4       6
4    7       8

My required job set J is {2} since  all the jobs are incompatible with at least one job of the job set J. I tried to use greedy algorithm like sorting jobs by start time, end time ( adding one  and removing all the ones incompatible and so on) But it is not optimal. As you can see in this example. If I add job 1 and then remove all the job incompatible with it, I will remove job 2, Then I will have to add 3 and 4 in the jobset J.

Am I going the right way?


texts: Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part

texts:
I have the following problem in mind. Suppose we have an $n$-dimensional point cloud with $m$ points. Each point in the cloud is associated with a value $X_i,1\leq i\leq m$. I would like to use a hyperplane to partition this point cloud into two parts, $S$ and $S^c$, in order to maximize $\sum_{i\in S} X_i$. Are there any efficient ways to do it?

Any advice would be greatly appreciated. If this cannot be solved efficiently, do there exist a good approximation algorithm?


texts: Sorting Algorithm: Probability Bound For Randomized Inversion Swapping

texts:
Let $A = (a_1, a_2, \dots, a_n)$ denote an array of distinct values with an order defined. Consider the following randomized sorting algorithm.

Let $m := 0$.
Select a pair $(i, j)$ with $1 \le i < j \le n$ uniformly at random.
If $a_i > a_j$, swap $a_i$ and $a_j$.
If $m < m_{max}$, let $m := m + 1$ and go to step 2.

It can obviously happen that the algorithm does not completely sort the array. But if $m_{max}$ is chosen large enough, it sorts the array with high probability.

  How to estimate this probability depending on $n, m_{max}$ and the number of inversions?

I have the following approach which yields only a recurrence, but no closed-form. It would be great to know at least a good bound.

Let $P(m, k)$ be the probability that the array $A$ is sorted correctly if there are $m$ iterations and $k$ inversions left. Thus, $P(m, 0) = 1$ for all $m$ and $P(0, k) = 0$ for $k > 0$. If  $m, k \ge 1$, it holds

$\displaystyle P(m, k) \ge \frac{k}{\binom{n}{2}} P(m - 1, k - 1) + \left( 1 - \frac{k}{\binom{n}{2}}\right) P(m - 1, k)$,

because $k$ of $\displaystyle \binom{n}{2}$ pairs $(i, j)$ are inversions and executing step 3 of the above algorithm reduces the inversion count by at least 1. This recurrence allows us to estimate $P(m_{max}, k)$ by dynamic programming. Does anyone have a good idea to express this in closed-form or suggest another estimate?


texts: Algorithm that shifts points in the x-y plane to maximize distance but keep one axis constant

texts:
Suppose I am running an experiment with some subjects, and I obtain some numerical data from them. The subjects are divided into 2 experimental groups. Rather than display the means of each group in a bar graph, I would like to show their individual data. So I plot the data like so:

This is all fine and good, but let's say some individuals within a group have the same data. In this case, you would not be able to see each individual's data in a plot like this because their datapoints would completely overlap. Even individuals with data that was almost-the-same-but-not-quite would have some overlap, and it could be confusing to someone looking at the graph because they wouldn't see all the data.

In such a scenario, it would be useful to plot the data with individuals that have the same data just slightly offset from each other on the X-axis, like so:

This makes it so each datapoint is clear and visible for the reader.

Now comes the question: if I have a dataset that looks similar to the figure above, and I want to choose "x axis values" for each point to properly plot my data so that each datapoint is visible to the user, is there an algorithm that will essentially maximize distance of points from each other on the x-axis (within some pre-defined bounds, of course) while keeping their y-axis values constant?


texts: Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised

texts:
Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. Assume each character in the set has a cost associated with it, consider the costs to be a=1, b=3, c=4, d=5, e=7.

for example

m = ['a', 'b', 'c', 'd', 'd', 'e', 'a']
n = ['b', 'b', 'b', 'a', 'c', 'e', 'd']

Suppose we would like to merge m and n to form a larger array s.

An example of s array could be

s = ['a', 'b', 'c', 'd', 'd', 'e', 'a', 'b', 'b', 'b', 'a', 'c', 'e', 'd']

or

s = ['b', 'a', 'd', 'd', 'd', 'b', 'e', 'c', 'b', 'a', 'b', 'a', 'c', 'e']

If there are two or more identical characters adjacent to eachother a penalty is applied which is equal to: number of adjacent characters of the same type * the cost for that character. Consider the second example for s above which contains a sub-array ['d', 'd', 'd']. In this case a penalty of 3*5 will be applied because the cost associated with d is 5 and the number of repetitions of d is 3.

I need to design a dynamic programming algorithm which minimises the cost associated with s.

Does anyone have any resources, papers, or algorithms they could share to help point me in the right direction?


texts: Generating all directed acyclic graphs with constraints

texts:
I am interested in listing all the unlabeled1 acyclic digraphs with n vertices which satisfy some additional constraints, such as (a) the resulting graph is connected and (b) except for R identified root vertices, all vertices have two incoming edges and zero or one outgoing edges.

There may also be additional domain-specific constraints, but they are probably easy enough to implement by simply generating and rejecting graphs that do not meet the constraints. In principle, conditions (a) and (b) above could be satisfied in this way above, but at least in the case of (b) it seems very advantageous to consider them directly in generating process since the output is likely to be quite sparse (i.e., a large majority of graphs will fail to satisfy (b) and this ration increases with increasing n).

My problem is twofold:

Even ignoring the constraints part, I have not be able to determine how to efficiently generate DAGs. I know there are a lot of them so I'll mostly be dealing with smallish n, let's say n < 15. There seem to be some promising papers, although may of them are focused on the closed-form counting of the number of graphs rather than actual generation, and any remaining ones are paywalled.
I want to apply the at least enough of the constraint part during the generation to avoid the case where nearly all generated graphs are simply rejected. That is, I hope the generation of the constrained graphs is considerably faster than the generation of the much larger number without constraints.

You can find lots of information on random generation of such graphs, but not much on exhaustive generation (which seems like the easier of the two problems).

1 That is, I want to exclude generation of isomorphic graphs.


texts: What is Follow(X) when there's a rule, A -> XBCD where First(B) and First(C) contain empty, but First(D) do not

texts:
I have a question about follow sets.

Suppose there's a rule,

  A -> XBCD

  B -> $\beta$ | $\epsilon$

  C -> $\gamma$ | $\epsilon$

  D -> $\delta$

What is Follow(X)?

Is it (First(B) - $\epsilon$) $\cup$  (First(C) - $\epsilon$) $\cup$ First(D) = {$\beta$ , $\gamma$, $\delta$ } ?


texts: Can every context free language written as a intersection of another context free language and a regular language?

texts:
I'm preparing an Formal language exam, One question from previous year's final is:

Prove or disprove:If L is a context free language, then there exists a language P that is generated by a pure context-free grammar and a regular language R so that $L = P \cap R$.

My solution to this question is quite simple. Assume context-free language P is equal to context free language L, and let regular language R to be $\Sigma^*$, where $\Sigma$ is the alphabet set. $\Sigma^*$ is definitely a regular language. So the answer to this question is yes.

However, I do came up with a more difficult problem. What if I add a limitation $P \neq L?$ Will this statement still hold? I current have no idea about this.


texts: Finding simpler equivalent regular expressions

texts:
I'm doing an exercise from my book that says:

Let $r$ and $s$ be arbitrary regular expressions over the alphabet $\Sigma$. Find a simpler equivalent regular expression:
a. $r(r^*r + r^*) + r^*$
b. $(r + \Lambda)^*$
c. $(r + s)^*rs(r + s)^* + s^*r^*$

The book doesn't cover how to simplify regular expressions, so I searched online and I presumed you would use the algebraic laws for regular expressions. I was able to use these laws to come up with something for part a. only:
a. $r(r^*r + r^*) + r^*$
$r(r^+ + r^*)+r^*$
$r(r^+ + r^+ + \Lambda) + r^*$
$r(r^++\Lambda)+r^*$
$rr^+ + r\Lambda + r^*$
$rr^+ + r + r^*$
I don't know how to approach b. or c., because b. has $(r + \Lambda)^*$ and c. has $(r+s)^*$, and I couldn't find how to deal with these. Any hints?


texts:
Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words,
$$\max_{S \subset U\\ |S| = k} \sum_{i = 1}^n \mathbb{1}_{S_i \subseteq S}$$
Where $\mathbb{1}$ is an indicator function.
For my application, $n, m \approx 10000$, $k = 16$, and $|S_i| = 3$. Thus the naive brute-force approach will not work. (I think this is an NP-hard problem in general if you allow $k$ to vary).
Question: Find algorithm that get closest to the optimal solution within reasonable time ( ex $O(n^2)$)
As an approximation algorithm, I have tried the following greedy algorithm, but I would like a solution that gets closer to the optimal solution.
We will start with $S = \emptyset$ and add one element at a time to $S$.
Take $U = \{e_1,\ldots, e_m\}$. Rank each element using the following.
Define $H_{j,c}$ as number of sets $S_i$ such that $|S_i \setminus (S\cup \{e_j\}| = c$. i.e.
$$H_{i,j} = \sum_{i = 1}^n \mathbb{1}_{|S_i \setminus (S\cup \{e_j\}| = c} $$
Add that element $e_j$ to $S$ which has the maximum ordered value $(H_{j,1}, H_{j,2}, \ldots, H_{j, m})$ as per the lexigraphical ordering. (Use $H_{j,1}$ as the main score, and use $H_{j,2}$ as a tie breaker and so forth).
Repeat until $|S| = k$.
PS.

I think I did a poor job of explaining the problem and my attempt at the problem. I would appreciate any edits to make this question clearer.
I am trying to use this problem, as a greedy approach to my previous question Graph partition that maximize the number of triangles within its parts. But I think this question is interesting as well.


texts:
An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$).

The item are now randomly distributed into $2x$ bins (you may assume $2x\in \mathbb{N}$).

What's the probability (i.e. what can we guarantee to achieve for any adversarial choice)  no bin contains items with total size > 1?

For example, if the adversary chose all items (except for the last one) to be of size $\frac{1}{2} + \epsilon$ , then we have $2x-1$ items that no two of them can fit in a single bin. The last item can fit everywhere. hence the probability is bounded by (relaxing to $2x-1$ bins):

$\frac{(2x-1)!}{(2x-1)^{2x-1}} < e^{-(2x-1)}$ .

On the other hand, all I know for a general item set is that a "good" coloring exist (easy to see using the first fit algorithm).

Any ideas?


texts: Why we need EEPROM in this micro-controller

texts:
PIC16F887 Block Diagram

According to the block diagram above, since we already have Program Memory, which may be used to store our program, why should we still need EEPROM? What is it for?


texts: Solving/mitigating the free rider problem without requiring identification?

texts:
Is there any algorithm/protocol out there to solve/mitigate the free rider problem without requiring identification?

In a web system, I want to distribute exactly one virtual dollar per day to each person, without requiring identification when a person creates an account.

A solution of mitigation, would mean for example that a specific person may get up to $2 per day (in case he created more than one account), but not much more.

The algorithm needs to distribute to every person about the same amount of money per day. So the ratio between the money distributed to every two different people per day should be around 1.


texts: CFG of all regular expressions over a binary alphabet

texts:
I'm working on creating a rather difficult CFG and I am getting stuck on finishing it. The CFG in question is meant to contain all valid regular expressions using the alphabet {0, 1, (, ), *, +, e} (e for epsilon).
Some examples I know that should be accepted are things like:

e
0
01
1010
0*1*0*1*
0*11+(10)*+(e+1*0*)
((100*)*(10*)*)*

While things such as these would be rejected:

ee
)(e+1*)*
(10)*++(

et cetera
I've been building up case by case and I have this rather ugly looking CFG that prevents most incorrect cases, but it does not come close to getting all the correct ones
S → (N) | M+M | N | (N)*
M → 0N | 1N | 0N | 1N | (N) | (N)* | M+M | e
N → 0N | 1N | 0N | 1N | ɛ
Apologies if this has been asked before, I tried searching everywhere here and on Google and I was not able to find someone else trying to create the same or similar CFG, but if this is a repeat I'd appreciate being pointed to the original!!
If helpful, I've been using this tool to test my CFG: https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/


texts: Is F(F(s,x), x) necessarily a PRF if F is?

texts:
Given a PRF - F, is $G_s(x)=F_{F_s(x)}(x)$ necessarily a PRF?

First I thought how to tackle this problem. First I tried using a hybrid argument:
$|\mathbb P[F_{F_s(x)}(x)] -\mathbb P[f(x)]|\leq |\mathbb P[F_{F_s(x)}(x)] -\mathbb P[F_{f(x)}(x)]| + |\mathbb P[F_{f(x)}(x)] -\mathbb P[f(x)]|$ so I can contradict the possibility that the first part of the is not negligible but the second part of the sum is problematic.
Then I tried to think of counter examples. But it seems to me that because I dont know what the key of F will be if I could break G then I could break F with one single query..
So i'm pretty stuck and would appreciate help.


texts: What is the "spatial information" in convolutional neural network

texts: deep learning research papers always claim that deeper layers of CNN have good "semantic information" but poor "spatial information". What is the spatial information exactly. Is that some activations in deeper layers?


texts: Algorithm to solve job assignment problem

texts:
Can someone suggest an algorithm to solve job assignment problem with condition?

With condition means that some jobs cannot be done by some workers. For example table as shown below:

In this table x - means that it is impossible to do. For example, worker 1 cannot do jobs 1,3 and 5.

I encountered such situation and there may be cases as shown above when usual Hungarian algorithm seems cannot solve such task because there is no way to complete all tasks by distributing one task per worker.

However, my main case it is allowed that one worker wil do several tasks (tasks, which worker can do). Main task is to complete all jobs using existing workers, but it is desirable that, all workers do roughly same number of tasks.

So is there some solution of such problem? May be any algorithms do exist?


texts:
In the Min-Ones-2-SAT problem, we are given a 2-CNF formula φ and an integer k, and the objective is to decide whether there exists a satisfying assignment for φ with at most k variables set to true.Show that Min-Ones-2-SAT admits a polynomial kernel.

What I did

check if I can satisfy a 2-CNF Sat with k variables set to true.
Read about 2-CNF Sat and deduced that I need to get the directed implication graph.
Transform the implication graph to a undirected graph (by reducing the 2-CNF Sat boolean formula)
The problem now looks like a vertex cover problem

My Question
How do I get from the implication graph to the undirected graph? I did some research and found out that I needed to get φ* and then derive the undirected graph from φ*+ which includes only the positive literals from φ* but I am not quite sure I understand what is happening there (resource: https://www.sciencedirect.com/science/article/pii/S0304397513005355#br0030)


texts:
A friend of mine is studying business analytics, currently on the topic for Microsoft DAX, but he is very new to the technological field. He mentioned yesterday, during a conversation, the term "sideways recursion". Does anyone have idea what that means? I know a regular recursion(maybe direct recursion is the more proper term), where a function calls itself directly. I know of indirect recursion, where a function calls another and then the other calls the first one back. I also know that direct recursion has some sub-types - head / tail recursion - the tail recursion is when the inner call does not participate in any calculations including the current context (e.g. the recursive call is the last statement in the function) - this is very useful lately in functional languages to optimize recursive calls, by not keeping the current context in the stack, since it will not be needed when returning back from the recursive call. Those optimizations make functional languages as effective as imperative programming languages and allow the immutability of functional languages to become practical for traditional tasks, but also allows to implement parallelism automatically to some extent ... as far as I know this is why functional programming languages started to become modern lately. I have also heard of variadic template recursive functions in C++, which allow to write recursive function with arbitrary number of arguments (not sure if arbitrary type is allowed as well). But I cannot find anything about "sideways recursion" ... is there a chance Microsoft is using this term instead of one of the above mentioned? E.g. instead of "tail recursion" ... or maybe instead of "variadic template recursive function" (even though this one is not exactly separate type of recursion, but more a technology paradigm from the language C++)?
Any help on making my knowledge on recursion classification and technology paradigms around different types of recursion would be appreciated! Thanks in advance! :)


texts: How to implement the synchronous part of the paper "Concurrent Cycle Collection in Reference Counted Systems"

texts:
I have been looking at how to implement this paper, which I've outlined the main algorithm below. This paper is about how to implement reference counting in a way that handles cycles.
What I'm wondering though is (a) if I have accurately captured it in what I'm about to write, and (b) if it could be simplified down (i.e. don't use all the colors).
My notes (and summarization and simplification I think) are:

If reference count goes to zero, add to clear linked list (release pool).
Otherwise, add to check pool (potential garbage collection candidates). (set check flag so we don't add it twice, or as they call it, the buffer flag).
If reference count is increased, remove from candidate pool.
Occasionally, traverse check pool to look for those that have gone to zero, then move to clear pool.
Then traverse them DFS in the candidate pool, if count > 1, then it is live so remove from check pool and undo check flag. If count is 1, then remove from check the pool and send to clear pool. Mark it with the traversal flag on DFS traversal (instead of using the gray color).

Does that pretty much summarize what is being said in this paper?
They used colors but I don't think they needed to add all that complexity. Essentially they are just setting flags and doing a simple DFS on the nodes that didn't get a reference count of zero upon decrementing. Is that it? What am I missing?
That being said, I don't know if this would really work in practice, though I am hopeful.


texts: Proving a language with $(ab)^n$ is not regular with pumping lemma?

texts:
I have been working to understand the pumping lemma better, but I am quite stuck at proving these two languages is not regular:
\begin{align}
L_1 &= \{(ab)^n c^m \mid n\ge 1,  m\ge 2n \} \\
L_2 &= \{(ab)^n a^k (ba)^n \mid k<3\}
\end{align}
For $L_2$ my approach was:

Let us be given a number $p$. Let $z = (ab)^p a^k (ba)^p$, which satisfies $|z| = 2p > p$, and let $z = uvw$ be its decomposition satisfying $|uv| \leq p$ and $|v| > 0$. This means that $v = (ab)^j$ for some $0 \le j \le p$. We choose $i = 2$ for $uv^iw$, which equals $(ab)^{p+j} a^k (ba)^p$. This word has more $ab$ than $ba$, which means that it doesn't belong to the language. Therefore $L_2$ is not regular.

Mainly I am actually confused with the $(ab)^n$, we should decomposed it so that we can pump $v$, but it is necessary to consider different cases of $v$, or is this sufficient?


texts: What is the difference between radix trees and Patricia tries?

texts:
I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a normal (uncompressed) trie by merging nodes with their parents when the nodes are the only child. This also holds for Patricia tries. In what ways are the two data structures different?

For example, NIST lists the two as the same:

  Patricia tree

  (data structure)

  Definition: A compact representation of a trie in which any node that
  is an only child is merged with its parent.

  Also known as radix tree.

Many sources on the web claim the same. However, apparently Patricia tries are a special case of radix trees. Wikipedia entry says:

  PATRICIA tries are radix tries with radix equals 2, which means that
  each bit of the key is compared individually and each node is a
  two-way (i.e., left versus right) branch.

I don't really understand this. Is the difference only in the way comparisons are made when doing look-ups? How can each node be a "two-way branch"? Shouldn't there be at most ALPHABET_SIZE possible branches for a given node?

Can someone clarify this? For practical purposes, are radix tries typically implemented as Patricia tries (and, hence, often considered the same)? Or can no such generalizations be made?


texts: How to reduce number of move operations in an array?

texts:
Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my disposal, I have a single method that I can use:

move(fromIndex, toIndex)

Thus, to achieve my desired array, I could call the method a number of times:

move(2, 0); // [2, 0, 1, 3, 4, 5]
move(1, 2); // [2, 1, 0, 3, 4, 5] (swapped 2 with 0)

move(4, 2); // [2, 1, 4, 0, 3, 5]
move(3, 4); // [2, 1, 4, 3, 0, 5] (swapped 4 with 0)

move(4, 3); // [2, 1, 4, 0, 3, 5] (swapped 0 with 3)

move(5, 4); // [2, 1, 4, 0, 5, 3] (swapped 5 with 3)

Thus, I also have a list of move() operations to achieve my desired result. The list of move() operations can possibly be reduced in size by changing the order and the indexes, to end up with the same result.

Is there an algorithm that I can use on my list of move() operations to reduce its size to a minimum?


texts: Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L?

texts:
$L\subseteq \{0,1\}^*$

Since the language is r.e. there is definitely at least one Turing Machine that semi-decides the language. I'm thinking that if you have one Turing Machine that semi-decides the language, you can arbitrarily extend this Turing Machine (by adding redundant states), which means there are a countably infinite number of Turing Machines that semi-decide L. Does this reasoning sound right, or does the answer depend on what the language L is?


texts:
I have a problem and I guess it NP-hard, but I cannot prove it.

Here is a layer graph, where layer 0 is the hignest layer and layer L the lowest.

there are some directed edge between layers, where an edge (A, B) indicates that node A can [cover] node B. And when A can cover B, every node on any path from A to B can cover B, B can cover itself.

Finally here comes a set of node S. I need to choose another set of node ANS, and ensure that for each node q in S, there exists a node p in ANS and p covers q.

For every node there is a cost, and I need to make the total cost of set ANS minimal.

Is this a NP-hard problem? I think so but I cannot prove it.

Could you help me?

Thank you very much.


texts: Constructing a PDA for the language $\{a^mb^n | m > n\}$

texts: i saw in a book how to construct a PDA for a case with m is equal to n . It's pretty simple, just push a symbol for every a and pop this symbol for every b that the PDA reads. But, i don't found a way to construct a PDA for this particular case. Every help is welcome.


texts: Is there a model of computation based on discrete event dynamic systems?

texts:
I asked a question here about discrete event dynamic systems. They are systems whose state evolution depends on asynchronous events. It can be combined with flow to produce a hybrid system.

There must be an event-based model of computation, since it is so applicable to user interactions. Could someone point me in the right direction? Is there a canonical model of computation for event-based systems?


texts: Produce all unordered unique combinations of N-sized subsets of an m·N-sized set

texts:
Say there is a set of m·N named elements. How to produce all the (unordered) combinations of N-sized subsets?
For example, m=2 and N=2, the elements are called A, B, C and D. There will be 3 combinations: AB+CD, AC+BD and AD+BC.
For m=2 and N=3 there will be 10 combinations. In general, it will be:
$$\frac{(mN)!}{(N!)^m\cdot m!}$$
(thanks to Ross Millikan)
How to approach creating an algorithm that produces / iterates over the whole set of combinations?


texts: Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?

texts: I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?


texts: Is there a functional specification of alpha-beta search that makes it easy to prove by induction that the algorithm works?


texts:
In the field of Cryptography and Computation Complexity there is a notion of negligible function.
I have some difficulties in understanding intuition behind this notion. The following are some definitions from Chapter 9. Cryptography from the textbook Computation Complexity. A modern approach by Arora and Barak with extensive use of negligible function. There my question after every definition about negligible function.

Before proceeding further, we make a simple definition that will greatly  simplify notation throughout this chapter.
Definition of negligible function. a function $\epsilon : \mathbb{N} \rightarrow [0,1]$ is called negligible if $\epsilon(n)=n^{-\omega(1)}$.
Because negligible functions tend to zero very fast as their input grows, events that happen with negligible probability can be safely ignored in most practical and theoretical settings.

So far so good, it's just the definition of negligible function, the only point is why do we need to care about this function if it "can be safely ignored".

The notion of computational secure function.$k \in_R \{0,1\}^n, x \in_R \{0,1\}^m, Pr [A(E_k(x))=(i,b) s.t. x_i=b] \leq \frac{1}{2}+\epsilon(n)$.

Less intuitive usage of negligible function. As I understood, in general, $A$ can with probability 0.5 guess uniformly distributed $x_i$, therefore it makes sence to expected lower bound of success to be $\leq \frac{1}{2}$, however it's $\leq \frac{1}{2} + \epsilon(n)$, it we can "safely ignore" $\epsilon(n)$ why to mention it, and the second point is it possible to run $A$ some fixed finite number of times to get probability infinitely close to 1?

Definition of one-way function. $x\in_R\{0,1\}^n, y=f(x), Pr[A(y)=x' s.t. f(x')=y] < \epsilon(n)$

In this case, the usage of negligible function is very intuitive, the success probability is upper bounded by negligible function $\epsilon(n)$. I am not sure how it's correlated with existence of computationally secure encryption scheme (of course =0 is preferable by encryption scheme), however if $\epsilon(n)$ can be safely ignored than it's ok.
The problem is I am not quite understand why do we need negligible function. By mentioning few definition I tried to be more specific about what exactly I don't understand.
I would appreciate if anyone can shed the light on the usage of negligible function


texts:
How we calculate the answer of following recurrence?

$$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n\,.$$

Any nice solution would be highly appreciated.

My solution is to substitute $n=3^m$, giving
$$T(3^m)=4T\left(\frac{3^{m/2}}{3}\right)+\log^2 3^m = F(m)=4F((m/2)-1)+m^2=O(m^2logm)= O(\log^2 n \log n \log n)\,.$$


texts: How can I choose good hash function for PCY algorithm

texts:
As far as I understand from PCY (Park, Chen, and Yu) algo is that the algo uses hashing during the first pass to reduce the number of CANDIDATE pairs that are considered in the second pass. I have 2 concerns.

1/ How can I chose a good hash function? since I noticed that if we chose a bad func, it turns out to make many "false noisy" bucket which is the home of many failed (pair) candidates.

For example: (3,5) and (6,10) are not frequent itemsets but what if h (3,5) = h (6,10) and make that bucket reach the support threshold = 2. (given {3} , {5}, {6}, {10} are all singleton itemsets already)

2/ In the filtering phase of the algo, I guess each candidate also has to loop over all the baskets to verify if it satisfy the threshold right? so the filtering part also thrashing disk as h*ll right?

Thank you all.


texts: Theorem Prover for complexity theoretic reductions

texts:
Can complexity theoretic reductions that lead to proofs of say NP completeness be formalized using an existing theorem prover such as Coq?

If so, can you provide an outline of how to formalize a simple reduction argument? I’d also appreciate pointers to the literature.


texts: Merge two series of sorted number, one much longer than the other

texts:
This is the problem:

  Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$
  comparisons.

I have come up with this algorithm:

1. Choose n/m "special" elements among n elements.
2. for i = 1 to m do
    2.1 Using binary search find block (between two special elements)
        where m_i should be inserted - time O(log(n/m))

    2.2 Using binary search in found block, find exact position for $m_i$. -
       O(log m)

Step 2.1 takes time $O(\log(n/m)$ and step 2.2 time $O(\log m)$, so I get in total a runtime in $O(m (\log n/m + \log m))$. How do I get rid of the $O(\log m)$ term?

Here's a sketch of the algorithm:

As you can see I have a problem - O(log m). How to eleminate it ?


texts: Distributivity of $\omega$-regular expressions

texts:
Recall that a language is $\omega$-regular if and only if it is recognized by a Büchi automaton. How can I prove that

$\qquad (E_1 + E_2).F^\omega$

is equivalent to

$\qquad {E_1.(F^\omega)+E_2.(F^\omega)}$

where

both expressions are omega regular expressions, and
$E_1$, $E_2$ and $F$ are arbitrary regular expressions with
 $\epsilon \notin L(F)$.

One way I could think of is to convert expression to a DFA and check
if it is equivalent.

Or I will really appreciate a hint on how to do the equivalence
proof, but how to represent $E_1$, $E_2$ and $F$ in DFA.


texts:
first of all this is a homework question and I don't want the solution. I just want a reference to how to solve similar questions like this. I believe it's explained my course textbook, "Computer Organization & Architecture: Themes and Variations" but I currently cannot afford the textbook.

Here's the question:

For each of the following numbers, state the base in use; that is, what are the values of r, s, and t?

a. $25_r = 23_{10}$

b. $1001_s = 19684_{10}$

c. $1011_t = 4931_{10}$

I recognize it's similar to solving an equation. I'm guessing I have to find r, s and t and they will be a specific base that matches the base ten number. I tried searching online for similar questions but I'm not sure what to search for so I have no clue where to start for solving these equations.

Any help would be appreciated.


texts:
Suppose there's an entity which produces files. User A has one of those files and decides to send it to user B.

How can user B validate the authenticity of the file without communicating with the producer? Is it even possible?


texts: Downsides of using convex layers for listing and counting points inside a triangle

texts: Given a set of points S and a triangle, what are the various reasons for which constructing and using the convex layers of S is not optimal for counting and listing the points inside the triangle?


texts:
I am trying to build a LL(1) parse table for the following grammar:

S -> L
L -> L : L
L -> id R
R -> ( L )
R -> ( )
R -> Epsilon

There are two problems here. First, the L rules are a left recursion and the R rules have ( as the same prefix.

So I modified the Grammar to this one:

S -> L
L -> id R X
X -> : L X
X -> Epsilon
R -> ( P
R -> Epsilon
P -> L )
P -> )

I then checked the grammar with the JFLAP Tool and it says that my grammar is not LL(1). But I just don't see the problem.

Can somebody help me out here?


texts: How to solve this combinatoric problem without bruteforce

texts:
I'm trying to solve the following problem :
A tile results of a number and a color.

a tile can be black, red, orange or blue.
a tile number is >= 1 and <= 15.

Given a random set a tiles (a same tile cannot be present more than twice in the set, so we have 15 * 4 * 2 = 120 tiles maximum), find if all the tiles can be grouped in valid subsets at one time.
There are two types of valids subsets :

The first one is a group. A group is a set of either three or four tiles of the same number but in different colors. (ex. 8 black, 8 red, 8 blue, 8 orange)
The second is a run. A run is a set of three or more consecutive numbers, all in the same color. (ex. 5 red, 6 red, 7 red).

My first try was a bruteforce/backtracking attempt : find all valid subsets, remove one from the set, find all valid subsets again (backtrack if none found and try another), remove one again ... but there are too many possibilities for my cpu (i7 8700).
How could i solve this problem ?
Thanks for help,


texts: Movement on Labyrinth with Best First Search

texts:
I have the following labyrinth where R is the robot(the parent node), red blocks are the obstacles where the R cannot move and GOAL is the node where we want the robot to go. Every node should be written in this form R(1,2,4), 1 is the row, 2 is the column and 4 is the distance from the current node to the goal node GOAL.

I am in a position where the solution tree looks like this

Now, I don't know which node should I select C or D ? Both of them have the same distance to the goal.


texts: Is the clique problem NP-complete also on bipartite or planar graphs?

texts: We know that the clique problem is NP-complete. Is the restriction of the problem to bipartite graphs or planar graphs still NP-complete?


texts:
I have some questions regarding acceptance of a language by DFA

Whether more that one dfa accept a language
Whether a dfa can accept more than one language


texts: Show that moving one symbol to the end still makes a regular language

texts:
Question
For any string $\sigma$ over alphabet $\Sigma$, we define the operation $\texttt{MOVE}$ as following

For $\sigma = aw$ ($a \in \Sigma, w\in \Sigma^*$), $\texttt{MOVE}(\sigma)=wa$

This is equivalent to moving the starting symbol to the end. For example, $\texttt{MOVE}(10110)=01101$.
Show that for a regular language $L$, the language $\texttt{MOVE}(L) = \{\texttt{MOVE}(\sigma): \sigma \in L\}$ is also regular.
My Attempt
After reading this post, I know I could prove a language $L$ is regular by showing that $L$ could be expressed as a DFA, NFA, or regular expression.
I tried different (vaguely related) directions

I have proved that: if $L$ is regular, then its reverse $L^R$ is also regular. However, in terms of $\texttt{MOVE}(L)$, only one symbol is reversed while the order of others is preserved.
$\texttt{MOVE}(L)$ seems to be related to converting between left and right quotients. But I do not how to proceed as quotients are defined upon two languages rather than one.

$$
L_1/L_2 = \{w\vert \exists x: x\in L_2 \wedge wx \in L_1\}\\
L_1\backslash L_2 = \{w\vert \exists x: x\in L_2 \wedge xw \in L_1\}
$$
Except these attempts, I do not know how to approach this problem. It would be great if anyone provide some pointer for me.


texts: Counting involving equivalence classes and languages

texts:
Let $\Sigma$ be the alphabet $\{a, b, c, d\}$ and let $R$ be the following relation on $\Sigma^*$: $R(x, y)$ is true if every letter in string $x$ also occurs in $y$, and every letter in string $y$ also occurs in $x$.  (For example, $R(abba, babbb)$ is true and $R(abcb, cbbcb)$ is false.)  How many (non-empty) sets are in the partition of $\Sigma^*$ corresponding to $R$?  (That is, how many equivalence classes does R have?)

Any help will help.


texts: Minimum number of steps to sort 3x3 matrix in a given way

texts:
So I started practicing some algorithms and programming before university starts and I ran into this problem:

Given a 3x3 matrix containing the numbers from 0 to 8, find the minimum number of steps required to sort the matrix in the following format:

1 2 3
4 5 6
7 8 0

In one move it is only allowed to pick a cell that is adjacent to the cell which contains the 0 and swap those two cells.

Now, I am really stuck with this one and have no idea how to begin. Any tips and ideas to get me started are appreciated.


texts:
Suppose we have two markets. Each market has various buy & sell orders that we can sell to or buy from respectively. Each order represents a specific number of a particular item type  that someone is selling or buying for a specific price per item and we can buy/sell any amount of items from/to any order. Each item type has its own volume per item (m3).

We have transportion that can transport a specific amount of volume and some budget amount.

Our goal is to form such transport cargo load of items that would maximize our profit by going from station A to station B assuming our limited cargo capacity and budget.

The algorithm I'm using is the following:

Sort sell orders of the source station by price_per_item in ascending order and group them by item_type.
Sort buy orders of the destination station by price_per_item in descending order and group them by item_type.
For each item type, form pairs of sell-buy orders based on the amount available in both markets (e.g. [Item, Quantity, Buy At, Sell At]: [Apple, 25, 50, 75], [Apple, 5, 50, 70], [Apple, 20, 60, 70])
Perform one of the following actions based on user input:

(A) Sort pairs by profit per m3 (sell_price - buy_price / volume_per_item) in descending order.
(B) Sort pairs by profit / buy price ratio ((sell_price - buy_price / volume_per_item) / buy_price in descending order.

Take as many items as possible from each pair of the sorted list until either budget = 0 or cargo_capacity = 0 or there are no pairs left.

When using option (A), the described algorithm doesn't take the budget into account while forming the list of most profitable pairs so it gives poor results with a limited budget. When the budget is high, due to the variety of the market the following algorithm uses a full budget amount while cargo space is usually almost empty (which I don't consider the acceptable result as I need to mitigate risks of losing cargo and having large losses due to low ROI).

When using option (B), the gives good profit compared to the amount used to buy the items but it doesn't utilize available budget efficiently.

So the task is to maximize total_profit / total_buy_price ratio while utilizing available budget_amount and cargo_capacity as much as possible.

Does this fall under some type of mathematical problem that can be solved in a mathematical way, and if so, can you suggest some sources to read up on in detail? Thanks.


texts: Given a maze, check if set of points is forming some-type of closed shape

texts:
Let's say we have given 2-dimensional maze in form of matrix, conisting only of the letters  x and .. For example the following maze:

xxxxx 11111    .....
x...x 1...1    .xxx.
x.x.x 1.2.1    .x.x.
x...x 1...1    .x.x.
xxxxx 11111    .....

Let's group those elements, we will group x's only, such that two elements will be in one group if they share at least one of the 8 sides (4 regular and 4 diagonal). Up here is one way how to group them, now for each of those groups we want to check if they are forming closed figure (in the first maze there is closed figure and in the second there isn't because the area of x's isn't closed).

What I think for the solution

I was thinking that we should find 4 points first that are important for each figure, those are: the top right, top left, bottom left and bottom right nodes, and now check if there is path from the top right to top left and bottom right,
from the top left to bottom left and from the bottom left to the bottom right. But, it turns out that this is not working always.


texts: Proving that quantum circuits not involving entanglement are inefficient

texts: I heard in a video that it can be proven that quantum circuits not involving entanglement can be efficiently simulated on a classical computer; i.e., that there is no point to building quantum circuits not involving entanglement. I have heard this referenced elsewhere in google searches, but nowhere can I find this proof mentioned. What is the proof of this?


texts: assign points to non-overlapping rectangles

texts:
I have N (~100M) points in 2D and M (~10k) non-overlapping axis-parallel rectangles. I'm looking for an algorithm to assign each point to a rectangle it is contained in (or say that it is outside of any rectangle). I'm looking for a solution that works faster than bruteforce.

In 1D, it is achievable in N * log(M) using binary search. is something like that possible in 2D?

I care about practical performance. Two or more points can and often would be in the same rectangle, but the opposite never happens as rectangles are non-overlapping.


texts: Cost of find operation on a tree data-structure

texts:
I implement my data sets with a tree data-structure.

The tree data-structure has a method named MakeSet which creates a set with one node. The tree data-structure has also a method named Merge(i,j) which merges trees of set i and set j in this way: the set with smaller depth becomes a child of the root of the set with larger depth.

I do MakeSet $n$ times and I do MergeSet $n-1$  times with a random order. Then I do a Find operation. What is the cost of Find in a worst case scenario?

I feel like the answer might be $O(n\log{n})$, because after doing $n$ MakeSet and $n-1$ MergeSet, it might be safe to say that we have a tree with $n$ nodes and height of $\log{n}$. I'm not sure.


texts: Minimum number of comparision to find the third largest element in an array of distinct integers?

texts:
For the second largest element, I know that the formula is $n+ \lceil\log n \rceil -2 $

Is there any formula for the third largest element? and if so, what is the derivation?


texts: Why are there more non-computable functions than computable ones?

texts:
I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are non-computable than computable, in fact the majority is non-computable it says. In some sense I can intuitively accept that but the book does not give a formal proof nor does it  elaborate much on the topic.

I just wanted to see a proof/let someone here elaborate about it/understand more strictly why there are so many more non-computable functions than computable ones.


texts: Performance of Recursive vs Iterative Solution to "Maximum Depth of a Binary Tree"

texts:
I am looking at this question from LeetCode.

There are two solutions to this question - the recursive solution and the iterative / breadth-first traversal solution.

My question is in regards to the memory requirements of each solution.

In the case of the recursive solution, we are going to be using the call stack. The call stack will, at its max, be the height of the binary tree. In a worst-case scenario, the tree is skewed, the height is the number of nodes, and our space requirement becomes linear - O(n).

In the case of the recursive solution, we use an explicit queue, instead of an implicit call stack. The largest number of elements that the call stack will hold is when the tree is a perfect binary tree (a complete binary tree has the same analysis), in which case, the queue will hold 2^h, where h is the height of the tree (indexed at 0). However, in a perfect binary tree, we also know that h = log(n + 1), so 2^h ~ 2^log(n +1), which means that the space requirements for the iterative case is O(2^(log n)).

My question is, which one of these is smaller? Can we make a determination that one of these two algorithms is better than the other in terms of memory?


texts: Enumerate all non-isomorphic graphs of size n

texts:
I am trying to enumerate all non-isomorphic graphs of size n and found this question: Enumerate all non-isomorphic graphs of a certain size

The accepted answer describes a method to do this:

Assume we know all non-isomorphic graphs of size n-1. Take each of them and add a new vertex in all possible ways. Then for all these graphs calculate a canonical labeling and check whether the new vertex has label 1 (or is in the same orbit of the automorphism group as the vertex with label 1). In that case, save the graph. Otherwise stop and try the next extension of the graph with n-1 vertices.

However, there's a problem: Say n=3 and we are currently considering the graph P2:

Now there are 4 ways to add a third vertex:

However, two of them create the same graph, P3. Using a canonical labeling as explained above doesn't solve this issue. So the extensions themselves need to be canonical, somehow. I assume I need to use the automorphism group of the graph of size n-1 somehow.

So that's my question. How can I make sure that all my extensions give non-isomorphic graphs?

I know how to find canonical labelings and automorphism group generators, so your answer can use them as much as you like :)

Thanks!


texts: Advantage of using generating functions in analyzing an algorithm

texts:
I'm reading through the first chapters of "Introduction to the analysis of algorithm" by Sedgewick. I wasn't familiar with the use of generating functions, and complex analysis in general to analyse algorithms. I do understand the use of the tool is in practice simple (at least it seems to me in that way from what I read so far).

I still don't get though what's the particular advantage of using a generating function over standard techniques of difference equations when analysing some recurrence extrapolated by some algorithm.

What's the benefit of using generating functions?

I can also see "analytic combinatoric" as topic, I haven't read through that yet, what's the advantage of that formalism instead? Is there some case where analysing in that way is really easy while using standard technique isn't?


texts: Are there improvements on Dana Angluin's algorithm for learning regular sets

texts:
In her 1987 seminal paper Dana Angluin presents a polynomial time algorithm for learning a DFA from membership queries and theory queries (counterexamples to a proposed DFA).
She shows that if you are trying to learn a minimal DFA with $n$ states, and your largest countexample is of length $m$, then you need to make $O(mn^2)$ membership-queries and at most $n - 1$ theory-queries.
Have there been significant improvements on the number of queries needed to learn a regular set?

References and Related Questions

Dana Angluin (1987) "Learning Regular Sets from Queries and Counterexamples", Infortmation and Computation 75: 87-106

Lower bounds for learning in the membership query and counterexample model


texts:
The maximum number of edges possible in an undirected graph with 5 nodes, when DFS call made on any random node in the graph result stack size 5 i.e. 5 function call present in stack simultaneously are ____________________

How graph edges can be converted to a function call ? Is that mean here we have to do a recursive call. I am not getting clear, what is function call here. Plz help


texts:
What is the price paid for the vast virtual address space provided to
programmers for their applications? Or in other words, what is the overhead due to virtual memory?

Is there any other overhead from implementing virtual memory, beyond memory consumed by the kernel?


texts: Hash Table: Relation between position of a value and Hash table size

texts:
I need to know whether hash table size, $S$ has any impact on distribution of a value in hash table.

At the moment I'm using SHA512 and I can tolerate up to 50 elements in any bucket, and I have $10^6$ elements; I set hash table length to $S=50000$. This is far more larger than what is suggested in the literature [1]. However, if I reduce the table length I would get overflow (as I have tested and saw it).

To find position of an element in hash table I do $hash(val) mod S$.

Question: Does $S$ play any role in distribution of the value in hash table?
In other words, do I need to set $S$ as a prime number or power of two ?

[1]. http://www14.in.tum.de/personen/raab/publ/balls.pdf


texts: Are all NP-complete languages downward self-reducible?

texts: Arora-Barak says that using the Cook-Levin reduction, one can show that all NP-complete problems are downward self-reducible. I know that SAT is downward self-reducible but I am not able to see how we can use this fact together with the Cook-Levin theorem to prove that all NP-complete languages are downward self-reducible.


texts: Shortest path with a start vertex that touches all nodes at least once with repeats allowed

texts: I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I believe). Maybe I am over thinking this though? I'm not looking for the fastest solution, but I fear a brute-force algorithm may take an extremely long time to perform this on a undirected graph with say 30 nodes. I'm personally trying to figure out on a video game the fastest way to traverse through every spawn point of a monster on a given zone (with a start point of course) so I can find him faster. I've already constructed a graph and figured out the distances assuming a complete graph. I guess on my part, one way to reduce the run time of such an algorithm is to remove realistically what edges wouldn't and probably wouldn't be included in a optimal path. I assume adding lots of constraints could help too. Might anyone know if there's a specific name for this problem, or if there is a simpler approach aside from just the standard brute-force? Thank you!


texts: Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms

texts:
While trying to analyse the runtime of an algorithm, I arrive to a recurrence of the following type :

$$\begin{cases}
  T(n) = \Theta(1), & \text{for small enough $n$;}\\
  T(n) \leq T(a_n n + h(n)) + T((1-a_n)n+h(n)) + f(n), & \text{for larger $n$.}
\end{cases}$$
Where:

$a_n$ is unknown and can depend on $n$ but is bounded by two constants $0<c_1\leq a_n \leq c_2 < 1$.
$h(n)$ is some "fudge term" which is negligeable compared to $n$ (say $O(n^\epsilon)$ for $0\leq \epsilon < 1$).

If $a_n$ was a constant, then I could use the Akra-Bazzi method to get a result. On the other hand, if the fudge term didn't exist, then some type of recursion-tree analysis would be straight-forward.

To make things a bit more concrete, here is the recurrence I want to get the asymptotic growth of:

$$\begin{cases}
  T(n) = 1, & \text{for n = 1;}\\
  T(n) \leq T(a_n n + \sqrt n) + T((1-a_n)n+\sqrt n) + n, & \text{for $n \geq 2$}
\end{cases}$$
Where $\frac{1}{4} \leq a_n \leq \frac{3}{4}$ for all $n\geq 1$.

I tried various guesses on upper bounds or transformations. Everything tells me this should work out to $O(n\log(n))$ and I can argue informaly that it does (although I might be wrong). But I can only prove $O(n^{1+\epsilon})$ (for any $\epsilon>0$), and this feels like something that some generalization of the Master theorem à la Akra-Bazzi should be able to take care of.

Any suggestions on how to tackle this type of recurrence?


texts:
I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\ \Gamma$ for $[pXq]$ we have include the sequence of derivations which would pop X
from the stack.
I partially understand what is going on but I cannot seem to understand how do I unroll the productions to form strings so I can understand it clearly. Take the production (5) in the example for instance. From what I understand it we are in state p we want to pop A and in the end we should be in state p with empty stack. As we are reading 0 we have zero in the production followed by $[pAq][qAp]$, this is the thing which I am not understanding because if we look at the PDA there is no way of going to q on reading 0. I would like to know what really is going on.
A related question is answered here
but I cannot understand it how to clear my confusion.


texts: The path between any two nodes in cyclic directed graph

texts:
G{V, E} is directed, cyclic, weighted graph. What is the algorithm of finding all paths between any given two nodes?
Can you suggest any good reading?


texts: How are epipolar lines useful in computer vision?

texts:
Why do use epipolar lines and what are it's benefits in computer vision ?I am unable to find the uses of epiploar lines and how they are helpful although i am aware of epiploar geometry concepts.

I would be so helpful if someone could pin point one or two uses of epipolar lines in computer vision .


texts: For the langauge L={0^i1^i | i>=0} DFA possible or not?

texts:
At many places I have read that the following language is not a regular, and thus it is impossible to express this in terms of  Finite Automata.

  L={0^i1^i | i>=0}

But I tried  this as follows.

Can somebody explain the fallacy?


texts:
3-SAT with at most 3 occurences per variable is $\mathsf{NP}$-hard.

Now I'll try to solve it using these:

Theorem: SAT where all clauses have length 3 and variables occur 3 times, is satisfiable.
Double propagation. If there is a clause $(a\lor b)$ and no clause $(\overline a\lor\overline b)$: change all occurences of $\overline a$ by $b$ and $\overline b$ by $a$. Also, remove clause $(a\lor b)$. This will result in two occurences for $a$ and $b$.
If there is a pair of clauses $(a\lor b)\land(\overline a\lor\overline b)$, replace occurence (there will be only one) of $b$ to $\overline a$. Remove that pair of clauses. This will result in two occurences of $a$ and no occurences of $b$.

Using this technique we either must get an empty clause or all clauses will have length 3 and formula will be satisfiable. It is also possible that formula will become 2-SAT.

Can this even work?


texts: Distributed Storage for Access and Preservation

texts: My organization wants to maintain multiple copies of data in order to preserve access in the case of localized disasters as well as for the purpose of long term preservation. Are there accepted formal models for determining the appropriate variety of media (eg tape, disk) and their placement in the network? Are currently operating distributed solutions (eg LOCKSS) viable long term solutions for large collections of data?


texts: Finding a segment which has equal number of segments before and after it

texts:
I got this question in a past test that I'm trying to solve but i don't have the solutions to check my self:

Given a set of n segments $[a_i ,b_i]$ where $i=1,..,n$ and $a_i < b_i$.
write an algorithm which find a segment that the number of segments $[a_l ,b_l]$ before it $(b_l < a_i)$ are equal to the number of segments $[a_r ,b_r]$ after it $(b_i < a_r)$
the algorithm will return its index if found else null

The algorithm should work in $O(n\log n)$ in worst case.

My solution is:

 running heapsort by $a_i$ (runs in $O(n\log n)$)
 running bucket sort by $b_i$ which each bucket is $a_i$ (runs in $(O(n))$)
 loop on each member (X) in reverse order and finding using binary-sort on the rest of the set the segment (Y) which its $b_i$ is equal or max close to $a_i$ and writing in the Y the distance of X from the end of list (number of segments which are right of Y) and writing in X the index of Y (number of segments which are left of X). that happens in (runs in $O(nlgn)$)
 loop on each member the looking up for an element with (left_count equals right_count) not equals zero and return it  (runs in $O(n)$)
 if nothing found - return null

So finally the algorithm works in $2lgn + 2n$ which is $O(nlgn)$

Am I right? There is a better solution?


texts: Is a String with no parantheses considered having balanced parantheses?

texts:
Say I have a language over the alphabet {x,y,(,)} . The language's rules are: any string over that alphabet with balanced parentheses.

Clearly    x(),  (xy)  , ()()xxx, ((xx)) are accepted. BUT

My question is, is a string with no parentheses considered as having balanced parentheses? For example are:   y, xxyy, xyxyxxx  accepted?

And then also what about an empty String?


texts:
A skip list

Let C(k) = the expected length of the path that raises k levels backwards.

Thus C(0) = 0

For any node P in the path, with k levels higher to go, there are two cases:

P is a node of level i and proceeds backwards to a node of at least level i and still k levels to go
P is a node at a level higher than i and must yet rise (k-1) levels

Each of these two cases has a probability of 0.5

Why C(k) = 2k and how to interpret this formula? Is the analysis formula in the figure right?


texts: Blum's speedup theorem showing unclassifiable complexity languages?

texts: Do any of Blum's theorems prove that there exist decidable languages that are unclassifiable anywhere in the time hierarchy? In other words, asserting they (mentioned in the proofs) are computable within any time $O(f(n))$ for some time-constructable function $f(n)$ leads to a contradiction?


texts: Proof of commonality of acceptors in majorities

texts:
In the Paxos consensus protocol, a fact that follows from its construction is "any two majority sets of acceptors will have at least one acceptor in common". This observation can be extended to any N majority sets of acceptors having either at least one acceptor in common, or acceptors that are distinctly present in each N-1 sets of acceptors.

"Therefore if two proposals are agreed to by a majority, there must be at least one acceptor that agreed to both. This means that when another proposal, for example, is made, a third majority is guaranteed to include either the acceptor that saw both previous proposals or two acceptors that saw one each."

I have an intuitive understanding of why this is so (should be a simple pigeonhole principle application), but I am having difficulty proving this formally. I would like a formal proof.


texts:
Given a program consisting of variables and instructions which modify these variables, and a synchronization primitive (a monitor, mutex, java's synchronized or C#'s lock), is it possible to prove that such a program is thread safe?

Is there even a formal model for describing things like thread safety or racing conditions?


texts: Time complexity of a hybrid merge and selection sort algorithm

texts:
I'm trying to analyse the time and space complexity of the following algorithm, which is essentially a hybrid of a merge and selection sort. The algorithm is defined as follows:

def hybrid_merge_selection(L, k = 0):
    N = len(L)
    if N == 1:
        return L
    elif N <= k:
        return selection_sort(L)
    else:
        left_sublist = hybrid_merge_selection(L[:N // 2])
        right_sublist = hybrid_merge_selection(L[N // 2:])
        return merge(left_sublist, right_sublist)

My thinking is that the worst case scenario occurs when $k$ is extremely large, which means that the insertion sort algorithm is always applied resulting in a time complexity of $O(n^{2})$, where $n$ is the length of the list and the best case scenario occurs when $N$ when $k == 0$, so the merge sort algorithm is only applied resulting in a time complexity of $O(n\log_{2}n)$. However, could somebody give me a more detailed and mathematical explanation of the time complexity, for all scenarios, namely worst, best, average.


texts: Pseudo random generator that is non injective

texts:
I was reading answer to https://crypto.stackexchange.com/questions/24941/prove-there-is-prg-that-is-not-necessarily-one-to-one
Here assuming existence of G: from n bit to l(n) bits non injective G' is created from n+1 bits to l(n) bits
 I was wondering if it is possible to construct G with domain of n bits instead of n+1.


texts: Construct DFA given oracle access to the language

texts:
I was given the following question.

Given a minimal DFA $A$ with $m$ states over some alphabet $\Sigma$ which is a "black box" (you can only run words to it and it tells you if it accepts or not):
a) describe an algorithm that allows you to find the equivalence classes of the Myhill-Nerode relation and then,
b) describe how you can reconstruct $A$ using the equivalence classes.

I managed to solve the first part using a brute force algorithm that checks all the words with length at most $m$. So now I have the equivalence classes but I don't know how to solve (b), how to reconstruct the DFA and its transition function. I think of looking at the representing words of the classes in lexicographic order then choosing the $m$ states from left to right corresponding to the words as an encoding, then the accepting states will be the states of the words which the black box automaton accepts and $q_0$ will be the state of $\epsilon$'s equivalence class which clearly is an equivalence class. But now the hard part is the transition function.


texts:
$INFINITE_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\}$

Here $ (A) $ denotes the encoding of DFA

Is above language regular, CFL or recursive ?

I know that above language is recursive for sure. I am not able to decide whether it's regular or not.

For regular, we know that regular languages are not closed under infinite union. So maybe above language is not regular but I couldn't think of an example where Union of infinite regular languages is not regular.

Can someone help me?


texts: propositional Modal logic filtration definition

texts:
Hello I have a slightly unusual question which relates to a definition of filtration structure. The following is my current state of the definition:

$ \mathcal{M} = (W, R, L) $, W is a set of worlds,
$R$ is a binary relation on the worlds, $ R \subseteq W \times W$, and
$L$ is a labelling function $ L : W \rightarrow\ \mathcal{P} (PropAtoms) $, here $PropAtoms$ is the set of atomic formulas.

Let $ \mathcal{M} = (W, R, L) $ be a Kripke model and let $\Gamma$ be a set of formulas that is closed under subformulas. Now, for each world $ w \in W$ we define the following:
$ \Gamma_{w} = \{ \psi \in \Gamma : (\mathcal{M},w) \vDash \psi \}$,

that is, $\Gamma_{w} $ contains formulas from $ \Gamma $ that are true at $w$ and consequently in model $\mathcal{M}$. Next we define an equivalence relation $\sim_{\Gamma} $ on worlds $w, w' \in W$,
$ \sim_{\Gamma} w w' $ if and only if $\Gamma_{w} \sqsubset \Gamma_{w'}$,
that is, worlds $w$ and $w'$ are equivalent if and only if they satisfy the same formulas in $\Gamma$. We also have equivalence classes $[w]$ of worlds $w$ with respect to $\sim_{\Gamma}$.

Lets now present the following quotient structure $ \mathcal{M}_{\Gamma} = (W_{\Gamma}, R_{\Gamma}, L_{\Gamma})$ which is in fact filtration of $\mathcal{M}$ with respect to $\Gamma$. $\mathcal{M}_{\Gamma}$ is defined as follows:
.........

Here is the bit I need help with, I am struggling to define my filtration model. This is mainly because the definitions online don't use the same labelling function but rather use a valuation function which is of the form $v(p)$. And such function takes an atomic formula whearas my labelling function takes in a specific world written $L(x)$. Could someone please help me our here and try providing correct definition which will match my model $M$ definition?


texts:
Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$.
This is an assignment problem and can be solved in $O(n^3+n^2d)$ time using the Hungarian algorithm.
Suppose $x_i\sim N(0, I_d)$ and let $v=\mathbb{E}_{x_1,...,x_n}\left[\min_{P\in\mathbb{S}_d} \sum_{ij} P |x_i-y_j|\right]$. Does anyone know of an algorithm that can compute $v$?
I'm also interested in algorithms for other distributions, e.g., $x_i\sim U(0,1)^d$ or $x_i\sim L(0,1)^d$.


texts: Trouble implementing back-tracking in RBFS

texts:
I'm trying to implement an rbfs search algorithm  for the 15 puzzle (pseudo code below).

link to the paper where i found the pseudo code:
https://www.aaai.org/ocs/index.php/SOCS/SOCS15/paper/viewFile/10911/10632

I do not understand what line 11 is suppose to do.
Any clue appreciated

Also, it start with a bound, and in the recursive call, use (min, B, f(n2))

Does this mean that you start with infinity in the first call to rbfs as the bound?
And so, the bound can only decrease, and never increase ?

    RBFS(n, B)
1. if n is a goal
2. solution ← n; exit()
3. C ← expand(n)
4. if C is empty, return ∞
5. for each child ni in C
6.   if f(n) < F(n) then F(ni) ← max(F(n), f(ni))
7.   else F(ni) ← f(ni)
8. (n1, n2) ← bestF(C)
9. while (F(n1) ≤ B and F(n1) < ∞)
10.  F(n1) ← RBFS(n1, min(B, F(n2)))
11.  (n1, n2) ← bestF(C)
12. return F(n1)

And here is another pseudo-code implementation

RBFS (node: N, value: F(N), bound: B) IF f(N)>B, return f(N)
IF N is a goal, EXIT algorithm
IF N has no children, RETURN infinity
FOR each child Ni of N,
   IF f(N)<F(N) THEN F[i] := MAX(F(N),f(Ni))
   ELSE F[i] := f(Ni)
sort Ni and F[i] in increasing order of F[i]
IF only one child, F[2] := infinity
WHILE (F[I] <= B and F[I] < infinity)
  F[I] := RBFS(NI, F[I], MIN(B, F[2]))
  insert N1 and F[I] in sorted order
return F[I]

What I don't understand here is this : insert N1 and f[I] in sorted order

Does this mean that rbfs does not maintain an open list (since it uses the recursion stack) but it does keep a closed list?