texts: Proof: "If the list is then k-sorted for some smaller integer k, then the list remains h-sorted"

texts:
Shellsort is a generalization of insertion sort that allows the
  exchange of items that are far apart. The idea is to arrange the list
  of elements so that, starting anywhere, considering every hth element
  gives a sorted list. Such a list is said to be h-sorted. Equivalently,
  it can be thought of as h interleaved lists, each individually
  sorted. Beginning with large values of h, this rearrangement allows
  elements to move long distances in the original list, reducing large
  amounts of disorder quickly, and leaving less work for smaller h-sort
  steps to do. If the list is then k-sorted for some smaller integer
  k, then the list remains h-sorted. Following this idea for a
  decreasing sequence of h values ending in 1 is guaranteed to leave a
  sorted list in the end.

[Source]

What is the mathematical proof for the quoted claim (in bold)?

An attempt at the proof (for the case when number of elements is $2n+1$):

My initial array is $A = \{x_0, \cdots, x_n\}$ and i have $x_0 < x_n$. Say that after first pass $x_0$ switches place with $x_m$, so the final array $B$ starts with the entry $x_m$ regardless of the position of $x_0$ (which can further switch place with $x_{2m}$ and so on). Thus, $x_m < x_0$. Now, in the final pass $x_n$ can switch place with $x_k$ (which, before the last pass, is in the $(n-m)$-th position in the array). We don't care about $k$, but we just know that $x_n < x_k$. So the last entry in the final $m$-sorted array $B$ is $x_k$.
Sum it up: $x_m < x_0 < x_n < x_k$.

That means $B$ is $n$-sorted.
If we assumed the switchings of $x_0$ and $x_n$ didn't happen during $m$-sorting, we are trivially done, because the starting and final entries of $B$ are $x_0$ and $x_n$ respectively, and since $x_0 < x_n$, $B$ is $n$-sorted.

Say $A = \{x_0, \cdots, x_n, \cdots, x_{2n}\}$ is $n$-sorted. We can assume the subarray $\{x_0, \cdots, x_n\}$ is $m$-sorted WLOG and because of what we proved earlier. Suppose now that while $m$-sorting, $x_n$ and $x_{n+m}$ are switched; then $x_{n+m} < x_n$. And then on the last entry, $x_k$ (in the $2n-m$ th position) and $x_{2n}$ are switched. Then $x_{2n} < x_k$.

After the $m$-sorting is over, the $n$-gap subarray starting at $x_0$ is $\{x_0, x_{n+m}, x_k\}$. We have $x_0 < x_m < x_{n+m} < x_n < x_{2n} < x_k$, where $x_m < x_{n+m}$ is because $A$ is $n$-sorted.

So, this is proof that if a $2n+1$ array is $m$-sorted after being $n$-sorted, it remains $n$ sorted.

However, I don't know how to generalize that for any size of array.


texts: Variation of rank selection in genetic algorithm

texts:
I'm looking for a specific variation of rank selection in genetic algorithms.

I came across a python program tailored for a specific problem that uses a variant of "rank" selection.  In normal rank selection, all individuals are sorted by fitness (in descending order) so that worst chromosome gets a weight of 1 and the best gets a weight of the population size.  Then, usual roulette wheel selection is used based on those "weights".

In the case of that program, a slightly different variation of rank selection is used.  Instead of relying on rouletted wheel selection after the chromosomes have beed sorted by rank, that program just pairs chromosome 1 with 2, 3 with 4, 5 with 6 and so on for crossover.  Does that rank selection method have a particular name and/or can anyone pinpoint me to a link describing that variation.  I googled it but haven't been able to find anything similar so far...


texts: Proof of Co-Problem being in NP if Problem is in NP using negated output

texts:
Given any problem $P$ that we know of being in $NP-\text{complete}$, where is the flaw in the following proof?
Given a problem $Co-P$ which is the co-problem of $P \in NP-\text{complete}$, $Co-P$ is at least in $NP$ because the following algorithm can always be given:
Co-P(J):
    bool res = P(J)
    return !res

Where $Co-P(J)$ is the algorithm solving $Co-P$ and $P(J)$ is the nondeterministic polynomial algorithm solving P.
Why is this not correct?


texts: How do you apply a multi qubit gate to specific qubits in a multi qubit circuit?

texts:
Let's say that you have a 6 qubit system and you want to apply a Hadamard gate to qubits 2 and 4.

How would you construct a matrix that did that, while leaving the state of the other qubits alone?


texts:
I was reading BFT from CLRS. This is the example given in the book:

(Figure:The operation of BFS on an undirected graph. Tree edges are shown shaded as they are produced by BFS. The value of $u.d$ appears within each vertex $u$. The queue $Q$ is shown at the beginning of each iteration. Vertex distances appear below vertices in the queue.)

Then it gives following lemma:

  Suppose that during the execution of BFS on a graph $G=(V,E)$, the queue $Q$
  contains the vertices $<v_1,v_2,...,v_r>$, where $v_1$ is the head of $Q$ and $v_r$ is the tail. Then, $v_r.d\leq v_1.d+1$ and $v_i.d\leq v_{i+1}.d$ for $I=1,2,...,r-1$.

I am ok with $v_i.d\leq v_{i+1}.d$ for $I=1,2,...,r-1$ as I can observe this in all queue instances above. But I am not able to understand how $v_r.d\leq v_1.d+1$ aligns with above, as $i<i+1$, but $r>1$. How that $+1$ is making whole difference?


texts: Learning Image Processing/Computer Vision

texts:
What do I need to learn dense correspondence?
I am a newbie in Image processing/CV.
Please help me by suggesting a kind of syllabus or show me a way to learn about Dense Matching. What are the things I really need to work on it.


texts: Why is GFp -> GFq false in LTL, even though GFp and GFq are false?

texts:
Consider the Kripke structure:
$$
\begin{array}{ccccccc}
  \to & (p, \neg q) & \to & (\neg p, \neg q) & \to & (\neg p, q) \\
  & \circlearrowright & & \circlearrowright & & \circlearrowright & \\
\end{array}
$$

where $(p, \neg q)$ means “$p$ and not $q$” and $\circlearrowright$ is a self loop. We number the states $s_1, s_2, s_3$ from left to right.
Now consider the three LTL properties:
$$
\begin{array}{ll}
  M \vDash \mathbf{G}\,\mathbf{F}\,p \to \mathbf{G}\,\mathbf{F}\,q & \text{false} \\
  M \vDash \mathbf{G}\,\mathbf{F}\,p & \text{false} \\
  M \vDash \mathbf{G}\,\mathbf{F}\,q & \text{false} \\
\end{array}$$

The oddity is this: how can $\text{false} \to \text{false}$ be false?

P.S.: I am sure of the results because I used NuSMV with the following code:

MODULE main
VAR
   state : {a, b, c};
   p : boolean;
   q : boolean;

ASSIGN
   init(state) := a;
   next(state) :=
       case
         state=a : {a,b};
         state=b : c;
         state=c : c;
   esac;
p :=
  case
    state=a : TRUE;
    state=b : FALSE;
    state=c : FALSE;
  esac;
q :=
  case
    state=a : FALSE;
    state=b : FALSE;
    state=c : TRUE;
  esac;

LTLSPEC
   ((G ( F p = TRUE)) ->  (G ( F q = TRUE)))
LTLSPEC
   (G ( F p = TRUE))
LTLSPEC
   (G ( F q = TRUE))


texts:
Look at this excerpt from the Algorithm Design Manual by Skiena, 2nd Edition

The sum of the first $n$ even integers? Surely, the two sums given do not include only even numbers, right? Is this a mistake on the author's part, or am I missing something?


texts: Max-min of a nonconvex quadratic problem

texts:
I am trying to solve the following problem, which is a simplification of our original question:

$\max\limits_{x,y}\min \{x_iy_i-b_i \mbox{ for } i=1,\ldots, n: x,y\in \Delta_n\}$

where $\Delta_n$ is n-dimensional unit simplex and $b_i$'s are arbitrary nonnegative numbers. $x_i,y_i$ is the $i^\mbox{th}$ entry of $x,y$ resp..

When all $b_i=0$, I can argue the optimum is $\frac1{n^2}$. But in general I have no progress. On the other hand, it would also be nice to show that this problem is NP-hard, but I am unable to think of a reduction from a combinatorial problem. It would be awesome to hear some suggestions! Thanks in advance.

Orion


texts:
I'm trying to analyze an algorithm of a function, I can express the function in term of summation, but I have no clues on how I could simplify this summation down to get the run-time in tern of big $O$ or $\Theta$. I have this pseudo-code below:

f(n)
    for int i = 1 to n
        for int j = i to n
           doThis(n - j)
        end
    end
end

Assuming that doThis(k) takes $c \cdot k$ operations for some constant $c > 0$. I can express the nested for loop in summation as follow:

$\sum_{i=1}^n \sum_{j=i}^n c\cdot(n-j)$

How does one simplify this summation? It has been a while since I touch math so I'm trying to get an idea here. Any help would be appreciated, thank you!


texts: Converting a digraph to an undirected graph in a reversible way

texts:
I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I understand that this will come in expense of the undirected graph having more vertices but I do not mind.

Does one know how to do this or can suggest any references? Thanks in advance.

Update: Regarding the answer of AdrianN below. It might be a good starting point but I don't think it works in its current form. Here is an image of why I think it doesn't:

Update after D.W.'s comment: I consider the vertices of the graphs to be unlabeled. If a solution involves labeling the vertices (like AdrianN's does), then it should give the same (isomorphic) undirected graph no matter how the labeling is done. My definition of "isomorphic" for graphs with labeled vertices is that there is a permutation of the labeling that relates the two graphs, but I am not sure of the exact definition for unlabeled graphs...


texts:
We have $n$ numbers lying on a circle, where $n$ is even. We want to compute the maximum of any $n/2$ consecutive numbers (so, we should get $n$ values in total).

One algorithm is to compute the maximum of every $n/2$ consecutive numbers separately. This leads to an $O(n^2)$ algorithm.

Can we do better? Perhaps using a heap or an appropriate data structure?


texts: I am trying to find a description for canonical form (labelling) for a graph. Specifically, how do we arrive at canonical form for a given graph?


texts: On maximum independent set of line graphs

texts: Are there any special algorithms for maximum independent set of line graphs? Could this special case be in $\mathsf{P}$?


texts: Is this grammar right associative (why?)

texts:
Given a grammar as follows:

$\left<stmt\right> \rightarrow \left<id\right> = \left<expr\right>$

$\left<const\right> \rightarrow A | B$

$\left<expr\right> \rightarrow \left<term\right> \times \left<expr\right> | \left<term\right>$

$\left<term\right> \rightarrow \left<factor\right> + \left<term\right> | \left<factor\right>$

$\left<factor\right> \rightarrow (\left<expr\right>) | \left<id\right>$

I think this grammar is right associative because it expands on the right. Where I am confused is it can be expanded using other non-terminals on the left. For example,

$\left<expr\right> \rightarrow \left<term\right> \times \left<expr\right> | \left<term\right>$

Could be expanded via $\left<term\right>$ on the left, I think. Does this make the associativity ambiguous? Assuming it could be ambiguous, how would I fix this to make the grammar completely right associative?


texts: What standardized formats (if any) exist for boolean circuits?

texts:
Being able to represent a Boolean circuit is useful in a number of areas of Computer Science, such as Circuit Satisfiability, Zero-Knowledge Proofs and Garbled Circuits.

Are there any standards for how such a circuit should be represented in a text file?
By a standard I mean very specific instructions about how wires should be labeled, how gates should be denoted and how any metadata (e.g. total number of gates) should be stored. In other words, an API which would allow different programs that used circuits as inputs/outputs to communicate with each other directly. For instance, say you were building a circuit optimizer that you wanted to be usable by all the applications I mentioned above. What format should you use?

I searched for RFCs but didn't find any (https://tools.ietf.org/).

(Feel free to migrate this question to another SE site if appropriate.)


texts: Why in the Map Reduce Implementation, why not stream the records to the reducer (via TCP) as they are being produced by the mappers?

texts: In the Map-Reduce implementation, the reducers start when all mappers finish their jobs. Why don't we stream the records from mappers to reducers while they are being processed instead? I think there are two reasons: (i) if we use streaming method, if a reducer fails, all the mappers have to recompute the map function because the results are lost; (ii) if we want to sort the keys in each partition, streaming will have bigger time complexity than waiting for mappers finish task and sort the key. Are these reasons correct and are there any reasons that they didn't use streaming implementation?


texts: Is it an open problem if generalized resolution is always possible?

texts:
Let we have a 3CNF under following restriction: each variable occurs 3 times.

Then I apply generalized resolution (GR) (I don't know which name would fit more) technique (number of clauses can be arbitrary large, just an example):

$(x\lor A)\land(x\lor B)\land(\overline x\lor C)=(A\lor C)\land(B\lor C)$. Here $A,B,C$ are some clauses. Neither $A$ and $C$ nor $B$ and $C$ have opposing literals (like in original resolution, the reason is not to exponentially increase length of formula).

Is it an open problem if there is such a sequence of choices (which variable to choose for GR) that will return 'NO' if formula is unsatisfiable? Or there is a proof that some unsatisfiable formulas (with given restrictions) have no such sequences? Meaning that for every pair of literals $x,y$ on some step it will be possible to find a clause $(A\lor x\lor y)\land(B\lor\overline x\lor\overline y)$.

We assume that we can use any known polynomial technique such as unit propagation, absorption rules $(x\lor A)\land(\overline x\lor A)=A; A\land(x\lor A)=A$, pure literal rule (if variable always occur as positive or negative, remove all clauses where it is contained), changing equal literals, finding strongly connected components in a graph for 2-clauses, etc.


texts: Polynomial time algorithms for rank 1 elliptic curves over Q

texts:
As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves.  Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a rational point of infinite order on the curve.

However, as an outsider, it is hard to understand what properties are feasible to obtain computationally.

So I would like to know, given an elliptic curve in minimal Weierstrass form, and assuming the factors of the discriminant are known (so that we don't need to get into complexity of factoring), what properties can be efficiently calculated about the curve? (let efficient = calculating in a time polynomial of the data size of values specifying the minimal model of the curve.)

Discriminant - yes, obviously
Conductor - it sounds like yes, if you know the factors of the discriminant? (I don't fully understand this concept yet, so may be misunderstanding some details (especially regarding the different notations that include a 16 or not in the discriminant). But it sounds like Tate's algorithm is sufficient to obtain the conductor if we have the factors of the discriminant.)
Torsion points - it sounds like yes, if you know the factors of the discriminant, via Nagell-Lutz theorem
Determine if curve is at least rank 1 - Sounds like yes, via computing the sign of the functional equation related to the L function (called the "global root number"? Not sure how computing this works, but sounds like info from Tate's algorithm is enough? see this Determining elliptic curve analytic rank even/odd )
Determine if curve is rank 1 - For rank 1 it is known this can be checked from analytic rank, but I don't know time complexity of calculating this.
Calculate a rational point of infinite order - Heegner points work for rank 1, but I don't know if there are more efficient ways, or what is the computational complexity of calculating Heegner points.
Calculating a basis point modulo torsion - ?? At least as hard as the above.
Calculating a basis point modulo torsion, given a rational point of infinite order - ?? Possibly simpler than above. Again, unsure what the best algorithms are.
Details of Tate–Shafarevich group - Unfortunately, I don't even know what this is, or is used for. But it is commonly referred to in some computational packages. It is referred to in BSD conjecture, so may be resolved for rank 1 now? Although, I'm unsure complexity of calculating the necessary derivative of the L function.
Details of Selmer group - Commonly referred to in some computational packages.
Other useful properties ...

It is likely there is an amazing intro in some review paper that I haven't found yet, which covers all of this. That would be perfect.

Of most interest to me are the computations of the rank and finding a point of infinite order. For point finding I've tried looking into the internals of some libraries, but it looks like a lot of them do something to limit a search range and then do a lot of searching (its very possible I am mistaken here). This quickly becomes daunting for larger values, and am unsure if nothing better is known, or if algorithms that scale well just run way too slow for the small values so are not useful for most calculations.

In short, it would be nice to have a quick run down of what currently is and is not computationally efficient for basic properties of rank 1 elliptic curves over Q.


texts: Why are we interested in negative edge weight cycles when finding out SSSP. In a path, we are not allowed to traverse a node more than once.


texts: What is the algorithm with lowest time-complexity for a get operation over Multi Key Multi Value Dictionary?

texts:
Multi Key Multi Value Dictionary is a dictionary in which each value is associated with a set of keys and each key is associated with a set of values. Several values can be associated with the same key, and several keys can be associated with the same value.

Let's define a $get$ operation over Multi Key Multi Value Dictionary accepting set of keys as an input and returning set of all values from the dictionary such that every value in the resulting set is associated with all of the input Keys; i.e. for each key in its input $get$ operation takes the set of its associated values and produces intersection of all those recorded sets of values.

Naïve algorithm's time-complexity would be $\mathrm{O} (\min\limits_{i \in 1...N} (n_i) \cdot k \cdot \log (N))$. The naïve algorithm finds out the key from input with the highest selectivity, go through its set of values and add only these values to result that have all other keys as well.

But is there any better algorithm in which there is no $\min\limits_{i \in 1...N} (n_i)$ component in its time complexity, but the number of values in result instead of it? E.g. is time-complexity $\mathrm{O} (n \cdot \log (N) + k \cdot \log (N))$ feasible for $get$? Also I assume that the space-complexity of the algorithm must be strictly less than $\mathrm{O} (N \cdot 2^K)$.

Here:

$n$ - number of values returned by $get$ operation,
$n_i$ - number of values associated with $i$th key from input,
$N$ - number of values in the dictionary,
$k$ – number of keys provided as an input to $get$ operation,
$K$ – number of keys in the dictionary.

Here is the motivation for such an algorithm. Let's say we are looking for a person in a dictionary using several traits like First Name, Last Name, Zip code and so on. There could be millions of people for each single trait. But there would be only couple of people having all the traits at the same time. So the lookup algorithm shouldn’t iterate over all values of one trait, even if the trait with highest selectivity is chosen. There could be no Key with good enough selectivity by its own.


texts: Why store self and parent links (. and ..) in a directory entry?

texts:
Consider an filesystem targeted at some embedded devices that does little more than store files in a hierarchical directory structure. This filesystem lacks many of the operations you may be used to in systems such as unix and Windows (for example, its access permissions are completely different and not tied to metadata stored in directories). This filesystem does not allow any kind of hard link or soft link, so every file has a unique name in a strict tree structure.

Is there any benefit to storing a link to the directory itself and to its parent in the on-disk data structure that represents a directory?

Most unix filesystems have . and .. entries on disk. I wonder why they don't handle those at the VFS (generic filesystem driver) layer. Is this a historical artifact? Is there a good reason, and if so, which precisely, so I can determine whether it's relevant to my embedded system?


texts:
I'd like to preface this question by saying that it is not a homework question. However, it is a question regarding the course material. In the rod-cutting example an equation is presented to determine the maximum possible revenue attainable for give rod length:

$r_{n} = max(p_{i} + r_{n-i})$ (15.2)

I'm trying to prove by induction that this equation does in-fact output the optimal revenue.

It's stated that, "A simple
induction on n proves that this answer is equal to the desired answer $r_{ n}$, using
equation. 15.2"

While not required, I'm attempting to perform this induction and I'm stuck on the inductive step. Here is what I have so far:

Base Case n = 3, where $r_{n}$ represents the maximum revenue attainable from a rod of length $n$ (note the following references a price list p, which corresponds to the price of a rod for a given length, and a list r which corresponds to the maximum revenue given a rod length).

$i = 1, p_{1} + r_{3-1} = 6 $

$i = 2, p_{2} + r_{3-2} = 6 $

$i = 3, p_{3} + r_{3-3} = 8 $

Assume,
$r_{k} = max(p_{i} + r_{k-i})$

Inductive Step,
$r_{k+1} = max(p_{i} + r_{(k+1)-i})$

I'm am unclear on how to proceed from here. I realize that the optimal revenue for a give rod length is defined in terms the optimal revenue for smaller rod lengths, which I believe means this problem displays optimal sub-structure. But i'm unclear on how to proceed. I'm prefer to not be given an answer but rather some direction.


texts: Finding $k$-th element in prefix of size $i$

texts:
Let's say we are given array $A$ of size $n$. We need to answer some numbers of queries. For each query we are given index $i$ and integer value $k$, $k \le i$. If we take the first $i$ elements of the array $A$ and we sort them we should return the one on index $k$ (we assume everything is 1 indexed).

I know that this can be solved in $O(Q\log N)$ if $Q$ is the number of our queries in offline way (we sort all queries by their index) and if we use persistent segment trees we can even make it work in online way (we can answer queries immediately), however I was wondering if there is simpler solution?


texts: How fast can 10 integer multiplications be executed?

texts:
This is self study, but not homework. I am reviewing some slides I found online and have come across the following question.

Question:
If the latency of integer multiply is $3$ and the cycles/issue is $1$ then

How fast can 10 independent int mults be executed?
$$t_1 = a_1*b_1 \quad t_2 = a_2*b_2 \quad t_3 = a_3*b_3 \quad \cdots \quad t_{10} = a_{10}*b_{10}$$
How fast can $10$ sequentially dependent int mults be executed?
$$t_1 = a_1*b_1 \quad t_2 = t_1*b_2 \quad t_3 = t_2*b_3 \quad \cdots\quad t_{10} = t_9*b_{10}$$

Attempt:
Obviously the sequentially dependent case will take longer, because each multiply must wait for the previous multiply to finish. I'm not sure exactly how to interpret latency and cycles/issue in this context. My attempt.

Each multiply takes $3$ cycles, but we can start a new multiply each cycle (can we?), so we need $3 + 10 - 1 = 12$ cycles?

Naively, this would take $30$ cycles if we wait for the previous one to finish. It seems that we could do better though. For instance

$t_1$ first
$b_2*b_3$
wait a cycle
$t_2 = t_1* b_2$
$t_3 = t_1*(b_2*b_3)$

So the first $3$ mutliplys can be done in $7$ cycles instead of $9$. I think I just need to see a problem worked out and I'll be able to pick up whats going on.


texts:
I wanted to give the following as a homework question, but my first few attempts to solve it failed, so now I'm just curios for a solution:

For two words $x,y\in \Sigma^*$ and for a letter $\sigma\in \Sigma$ we define the glue-concatenation of $x\sigma$ and $\sigma y$ to be $g(x\sigma,\sigma y)=x\sigma y$, and for words $w,z$ such that the last letter in $w$ differs from the first letter in $z$, the glue concatenation is undefined.

For languages $A,B\subseteq \Sigma^*$, we lift the glue operator such that $g(A,B)=\{g(w\sigma,\sigma z):w\sigma \in A, \sigma z\in B\}$ (note that we only consider words for which $g$ is defined).

  The question: is it always true that $|g(A,B)|\le |A\cdot B|$?

Observe that trying to prove that if $g(x,y)\neq g(w,z)$ then $xy\neq wz$ will fail, since for example, $g(a,abb)\neq g(aab,b)$, but $a\cdot abb=aab\cdot b$.


texts:
I am studying cache coherence MESI protocol with "intervention" (cache can send to other cache without use the Main Memory).

On my notes I wrote that in case of a processor has a block in M (modified state) and read on the bus a Write operation done by an other Cpu, the processor sends the block directly to the cache that want to write (intervention) AND to the Main memory and then change the state to I (invalid)

But why it has to send the block even to the main memory? I mean, it could simply send the block to the other cache (and then will be that cache the will send the block to MM in case of an other CPU want so read the block).


texts: how to write a program that display the total running time of a given algorithm based on different situations such as processor speed, input size, processor load, and software environment?


texts:
There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose any number of topics. There will be only one session on a given day per hall.

The problem is to finish the seminar in minimum time with as least as possible, members missing on their topics (so that we have most utilization of halls).

  My Solution:

For strictly no one missing on the topics there can be only one session on a day in only one hall and rest halls to be left unused. This takes longest possible time to finish the event. Only when all the k halls are utilized simultaneously, we can do it fastest.

Lets assume that ti is the set of all members interested in the i-th topic.

I am looking at a brute force solution in which we observe combinations of k topics (one topic per hall) to be scheduled at once. The effort is to find out intersection of groups in which cardinality of set with members choosing all those k-topics is minimum. Initially, there are nCk combinations, and after we schedule the first k-topics we can look for next n-kCk and then n-2kCk, n-3kCk... topics and so on.

As we see here, the main effort here is to find the intersection of k-sets. To me it looks like there should be some dynamic programming mechanism to reduce the repeated effort which I am unable to figure out. Do we have some thing absolutely different?

It is not a homework.


texts: Computing all possible partial sum-function of a given set of numbers

texts: Let there be $N$ positive numbers given as $\lambda_1\geq\dots\geq\lambda_N$. Now I am interested in the following numbers given as $$\alpha_i=\exp(\frac{\lambda_i}{\lambda})$$ for some positive constant $\lambda$. Define the function $\mathcal{S}(..)$ which takes a subset of these numbers (let me call me them as a sequence) and calculate their products. For example$$\mathcal{S}(\alpha_1,\alpha_2)=\alpha_1\alpha_2$$Also note that $$S(\alpha_1,\alpha_2,\alpha_3)=S(\alpha_1,\alpha_2)S(\alpha_3)$$Also $$\mathcal{S}(\alpha_1,\alpha_3,\alpha_4)={\mathcal{S}(\alpha_1,\alpha_2,\alpha_3,\alpha_4) \over \mathcal{S}(\alpha_2)}$$ and so on. For given $K$ and $N$, we have $NC_K$ possible subsequences of $\alpha_i$'s. Is there a really efficient way of computing $\mathcal{S}(.)$ for all such sequences.


texts: Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)

texts:
If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because of this video: https://www.youtube.com/watch?v=QGVCnjXmrNg (1:20 starts discussing the solution), where it says it can be lowered through using a trie with all of the words, but I think the creation of the trie would take O(n*t) complexity, where t is the average length of the words. Assume that all words will be at least as long as d (any word which has length smaller than d is disregarded immediately in the solution below, but is still considered during the creation of the trie in the video).
My idea for the solution is the simple one: go through each word and check if it starts with the same prefix. If it does, add it to the list of words which start with that prefix, otherwise don't. The reason I think this is the best solution possible in terms of worst-case complexity is as follows: if we skip even one character or one string, we may return the wrong answer. This is the minimum input that is to be considered and in any other case, it is also considered (for example, in the solution that input is considered during the creation of the trie).
Example javascript code:
function solve(prefix, words) {
    //startsWith has worst-case complexity O(d) where d is the length of the prefix
    function startsWith(word, prefix) {
        //this doesn't change worst-case complexity but means that the only disregardable input is disregarded
        if (prefix.length > word.length) return false;

        for (let i = 0; i < prefix.length; i++) {
            if (prefix[i] !== word[i]) {
                return false;
            }
        }

        return true;
    }

    const wordsArray = [];

    //since there are n (n is the length of the words array) and every iteration has worst-case complexity O(d),
    // we have a worst-case complexity of O(n*d)
    for (let i = 0; i < words.length; i++) {
        if (startsWith(words[i], prefix)) {
            wordsArray.push(words[i]);
        }
    }

    return wordsArray;
}

console.log(solve("do", ["dog", "dark", "cat", "door", "dodge"]));

I'm asking that because in the video it was mentioned that it can be faster than O(n*d), but I believe the solution was wrongly analyzed. I, however, am just a hobbyist and feel like it is more likely I'm missing something here.


texts: Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?

texts: I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the unknowns $x_i$. What is the least expensive way to find a solution that minimizes the amount of $x_i$'s such that $x_i = 1$, or equivalently, a solution of minimal norm? Is this solution unique?


texts: Scheduling algorithm for overlapping jobs - single resource?

texts:
I have a single resource that will need to shared for running multiple parallel jobs. Think of the resource as a straight line numbered from 1 to 100. The jobs occupy part of the line while they are running.
Each job has a start and end unit associated with it and it can only be run between those ranges.

For example lets say we have 3 jobs waiting to run -

JOB-A is defined to run between 30 (start) to 70(end) units on the
line
JOB-B between 40 to 90
JOB-C between 10 to 20 etc

We can run as many parallel jobs as we want but none of them should overlap with the other one thats running. So in this case we can only run either JOB-A and JOB-C or JOB-B and JOB-C at the same time as JOB-A and JOB-B overlap each other in their range.

The time taken by the job to finish running is based on its length. For example JOB-A runs for 40 seconds (70 minus 30). Once a job is done, it is removed and we get free space that we can allocate to other newer jobs.

So in the above example, if we were to pick JOB-A and JOB-C to run in parallel, we have to wait 40 seconds for JOB-A to complete before we can run JOB-B (since JOB-B's range overlaps with JOB-A). We cannot break up the jobs into pieces.

Is there an algorithm that fits this problem? What do you think would be a good way to approach this?


texts: How do you marginalize in graphical model elimination?

texts:
I'm reading Michael I. Jordan's book on probabilistic graphical models, and I don't understand the elimination algorithm presented in chapter 3. To narrow the question down, consider page 6. In equation (3.10), we see that
$$m_5(x_2,x_3) = \sum_{x_5}p(x_5|x_3)p(\bar{x}_6|x_2,x_5)$$

where the $x_i$ are random variables and $\bar{x}_i$ indicates a fixed/realized value of $x_i$.

Given that all $x_i$ are discrete random variables (as is the case in chapter 3), both $p(x_5|x_3)$ and $p(\bar{x}_6|x_2,x_5)$ are represented by two-dimensional matrices. And since $m_5$ is a function of as-yet unrealized variables $x_2$ and $x_3$, it is also a two-dimensional matrix.

How then do we perform the multiplication and the summation above?


texts: I want to make a simple application that input is an image and output must be 0 if image is dog and 1 if image is cat. Is it possible to detect cats from dogs in image with single layer perceptron?


texts: Reducing randomness needed by turing machine

texts:
I am reading an article related to streaming algorithms named "Turnstile streaming algorithms might as well be linear sketched" by Yi Li, Huy Nguyen and David Woodruff,

At some point they have a random algorithm (uses a tape of random bits) that solved a problem over $\mathbb Z_{|m|}^{n} = \{-m,..,m\}^n$ that succeeds with probability $1-\delta$

They want to reduce the number of bits needed for randomness used by that algorithm using via the following statement:

  Theorem 9: Let A be a randomized automaton solving problem P on
  $\mathbb Z_{|m|}^{n}$ with failure probability at most $\delta$. There
  is a ranomized automaton B that only needs to pick uniformly at random
  one of $O(\delta ^{-2}nlogm)$ deterministic instances of A and solves
  P on $\mathbb Z_{|m|}^{n}$ with failure probability at most $2\delta$

  Proof: Let $A_1 ,A_2 ,.., A_{O(n\delta ^{-2}logm)}$ be independent
  draws of deterministic automata picked by B.

  Fix an input $x\in \mathbb Z_{|m|}^{n}$.

  Let $p_A(x)$ be the fraction of automata among $A_1 ,A_2 ,..,
> A_{O(n\delta ^{-2}logm)}$ that solve problem P correctly on x and
  $p_B(x)$ be the probability that B solves P on x correctly.

  By a Chernoff bound, we have that $Pr\{|p_A(x)-p_B(x)|\geq \delta\}
\leq exp(-O(nlogm)) < (2m+1)^{-2n}$.

  Taking a union bound over all choices of $x\in \mathbb Z_{|m|}^{n}$,
  we have  $Pr\{|p_A(x)-p_B(x)|\geq \delta \ for\  all\  x\} > 0$.

  Therefore, there exists a set of $A_1 ,A_2 ,.., A_{O(n\delta
> ^{-2}logm)}$ such that $|p_A(x)-p_B(x)|\leq \delta$ for all $x\in
> \mathbb Z_{|m|}^{n}$. The automaton B simply samples uniformly at
  random from this set of deterministic automata

I am having trouble understanding some parts of the proof:

the random variable $p_A(x)$ should be the amount of $A_i$'s that succeeds divided by the amount of them that B has sampled?

if so than by the low of total probability its easy to see that:

  $p_B(x) = \sum_{i}P[B\ choose\ A_i] P[B\  succeeds\  on\  x\  |\ B\ choose'  A_i] = \sum_{i}\frac{1}{O(\delta^{-2}nlogm)} P[A_i\ succeeds\
on\  x] = p_A(x)$

where the last move comes from the fact the each instance $A_i$ is deterministic so its either 1 for success or 0 for failure.

So the whole $|p_A(x)-p_B(x)|$ they use is actually 0

I understand from the end of the proof that $|p_A(x)-p_B(x)|$ should some how represent the distance between A's success to B's success but could not see how this happen.

Also I did not understand the use of Chernoff the way they did.


texts: What semantical is there in attribute grammars?

texts:
I've been reading about attribute grammars since I'm trying to extend CFGs to semantics.
What I'm finding difficult to grasp is the use of the word "semantics" in the context of attribute grammars.
For example here:

One can see the term semantic rule. But isn't this just arithmetic?What semantical is here?
Can you give a clearer sense of how attribute grammars can describe semantics? Or what semantics means in the context of attribute grammars?


texts:
I was trying to prove the following:

  if  x%(x/2) != 0 or x%(x/2) == 0

  then x%(x/y) != 0 or x%(x/y) == 0  such that y = [2,4)

So I am trying to figure out whether a number can have a factor in between its half and its fourth.  I am trying to use it in a factoring algorithm.


texts:
Reading this question "Natural RE undecidable problems but not Turing-complete" the following language came to my mind:

If $\Sigma(\cdot)$ is the busy beaver function (maximum attainable score among all halting 2-symbol n-state Turing machines of the above-described type, when started on a blank tape), define the function:

$$BB(\langle M \rangle) =
\begin{cases}
1 & \text{$\langle M \rangle$ computes $\Sigma(\cdot)$}\\
0 & \text{ otherwise}
\end{cases}$$

Now define the language:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

  Is $L$ recursively enumerable? (it should be r.e.: just simulate in parallel M with all TMs of the same length, and if $M$ halts and another $M'$ halts with a higher score add M to the enumeration).

  Can we reduce the halting problem to $L$ ? (it seems that it cannot "capture" the halting of the busy beavers)


texts:
Can the same node appear twice in a tree?

I'm asking about the node object itself, not the node's value. For example, in the following code, a's left and right are the same node, b.

a = new TreeNode(1);
b = new TreeNode(2);
a.left = b;
a.right = b;

Is this valid? Why or why not?


texts: What happens when an internet connection is faster than the storage write speed?

texts: If one attempted to download a file at a speed of 800 Mb/s (100 MB/s) onto a hard drive with a write speed of 500 Mb/s (62.5 MB/s), what would happen? Would the system cap the download speed?


texts: Make a tag system simulate a finite automaton?

texts:
Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end just one output symbol "A" for accepting the initial input or "R" for rejecting it.

I guess a solution would be to make a Tag system simulate a specific Turing machine that simulates a finite automaton but that seems too much and too complicated. Is there perhaps a direct way from tag systems to finite automata?


texts: Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$

texts:
I'd really like your help with proving the following.

If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$.

Here, $\mathrm{NTime}(n^{100})$ is the class of all languages which can be decided by nondeterministic Turing machine in polynomial time of $O(n^{100})$ and $\mathrm{DTime}(n^{1000})$  is the class of all languages which can be decided by a deterministic Turing machine in polynomial time of $O(n^{1000})$.

Any help/suggestions?


texts: When should I move beyond k nearest neighbour

texts:
For many machine learning projects that we do, we start with the k Nearest Neighbour classifier. This is an ideal starting classifier as we usually have sufficient time to calculate all distances and the number of parameters is limited (k, distance metric and weighting)

However, this has often the effect that we stick with the knn classifier as later in the project there is no room for switching to another classifier. What would be good reason to try a new classifier. Obvious ones are memory and time restraints, but are there cases when another classifier can actually improve the accuracy?


texts: Detecting all cycles in un-directed graph

texts: I would like to detect all the cycles(non duplicate) in a given graph, I mean if A-B-C-A is a cycle, then A-C-B-A is a duplicate of previous one and need to be considered.I could use DFS and detect a cycle, but what if i want to continue to find other cycles? how would i make any node to be considered for other cycle?


texts: Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

texts:
The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux.

But, since every permutation has a unique Young's tableau, there seems no reason as to why it cannot be done in $O(n \log n)$ time, which is the optimal time to identify a permutation.

Are there any known non-trivial lower bounds for this?

Any assistance/guidance towards any of the questions is much appreciated.
Thanks in advance

Sample input permutation

5,7,2,3,4,1,6

Output Young's Tableaux

1,3,4,6
2,7
5


texts:
How can we construct TMs such that it accepts(Give description only):

a + b = c
a . b = c

Input is of the form a#b#c.
a,b and c belongs to {0,1}* and are positive binary unsigned integers.
I know that we can construct TMs if the input has unary representation but how to solve if it has binary representation?


texts: Is an integer variable constant or logarithmic space?

texts:
My lecturer says that a variable takes up one memory position in RAM. This is the slide in question:

But CLRS (Introduction to Algorithms by Cormen, end of page 23) says an integer is represented by $c\ lg\ n$.
Are both statements true? How can that be?


texts: Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?


texts: Dealing with intractability: NP-complete problems

texts: Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?


texts: Suppose we are given a CNF formula $F$ with $n$ variables and $m$ clauses. The question is whether we can represent $\lnot F$ as a CNF formula with the number of clauses polynomial in $n$ and $m$?


texts:
You are given n jobs, m workstations and an n × m two-dimensional task matrix T of the time each job will spend at each workstation. Each job becomes available at a specified time and may be processed in only one workstation at a time. Each workstation may process only one job at a time. The goal is to assign a start time for each job at each workstation that minimizes the finish time
of the last job.

How can I solve this problem optimally?
(I think we must use  dynamic programming.)


texts: How to quickly solve a linear equation for 7000 times?

texts:
I need to solve a linear equation Ax=b for 7000 times (A is sparse and complex square matrix), and at each time only 4 elements (A(i,k), A(i,m), A(j,k) and A(j,m)) are changed while all other elements are the same (at each time the indices i,j,k,m are different). I used block to obtain the updated inverse of matrix A. The total CPU time is more than 20 minutes. I am wondering if there is a faster way to solve this equation and control the CPU time within 1 minute.

Thanks a lot in advance.

Benson from Texas


texts: m-CNF formulas satisfiability approximation

texts:
I am reviewing for a test, and i am stuck on this question.

the problem is to show it is hard to approximate (for any constant) the following problem:

given m CNF formulas f1,..,fm over variables x1,..,xn find the assignment which maximizes the number of satisfied formulas.

I believe I need to reduce this problem to some kind of graph problem (CSG,IS,CLIQUE), which I know cannot be approximated for any constant. I can't find a way to do this. To what problem do I reduce this to?

thank you.


texts: Is the internal structure of a red-black-tree dependent on the insertion order?

texts:
Is the internal structure of a red-black tree (which nodes are red or black, the disposition of the branches, the location of each value...) dependent on the order in which the elements were inserted? Or does it only depend on the set of inserted elements, without taking the order into account? Do different insertion orders always result in the same tree?

In case the order does indeed matter, is there an algorithm that, given a red-black tree, returns a sequence of elements such that inserting them in that same order gives back a tree structurally identical to the one with which we started?

Edit: As John L suggests in the comments, merely inserting two different values in different order already generates different trees.

And the question of finding a sequence of elements that results in the same tree is easy enough if we allow solutions of any complexity whatsoever. So let's say that we are interested in solutions of complexity equal or below   $O(n \times \log(n))$ where $n$ is the number of elements.

Also fix the algorithm to the one described in the paper Red-Black Trees in a Functional Setting by Chris Okasaki.


texts: Grouping numbers so they approximate their total divided by two

texts:
Given an array of numbers, I would like to find an algorithm which divides them into two groups, such that the sum of the numbers in each group is as close as possible to half of the sum of all numbers, meaning I am looking for two groups whose sums are as similar as possible to each other.

As an example, given the array [120, 100, 33, 57], the goal would be

(120 + 100 + 33 + 57) / 2 = 155

The subgroups whose sums best approximate this number are [120, 33] and [100, 57], as they result in a sum of 153 and 157, respectively, for a distance of 2 from the goal. If we were to go with e.g. [120, 57] and [100, 33], their distance of 22 from the goal would be quite a bit bigger and thus less ideal.

One more example:

array = [44, 18, 71, 109, 29]
goal = 135.5
subgroups = [[109, 29], [44, 18, 71]]
distance = 2.5

Is there a way to do this, besides brute forcing it?


texts: Sum of divisors summatory function with Erathosthenes' sieve

texts:
I ran across the following problem from an online problem bank: there are up to $~10^5~$ queries each of which asks to compute the sum
$$\sum_{k = L}^{R} \sigma(k)$$
where $\sigma(k)$ is the sum of divisors of $k$. It is given that $1 \leq L \leq R \leq 5\cdot 10^6$.

My solution (described below) is based on Erathosthenes's sieve. I've implemented it in C++ and it works in about $0.9$ seconds on average which is too slow. I know that this problem can be solved at least twice faster but don't know how.

So here is my solution (arrays are 0-based):

M = 5 * 1e6
M = array of zeroes of size M + 1
A[1] = 1
for (k = 2; k <= M; k += 1)
    for (j = k; j <= M; j += k)
        A[j] += k

I precalculate $\sigma(k)$ via Erathosthenes' sieve for each $k$ below max possible value. When the main loop reaches $k$,  $A[k]$ keeps the value of $\sigma(k)$. Then I reassign $A[k]$ to be $\sum_{i=1}^{k}\sigma(i)$. After such preprocessing all queries can be computed in $O(1)$ time by computing $A[R] - A[L-1]$.

How can I make it faster? I know two formulas:
$$ (a) ~~~~~ \sigma(p_{1}^{a_1} \cdots p_{s}^{a_s}) = \prod_{i=1}^{s} \frac{p_{i}^{a_i + 1} - 1}{p_{i} - 1}$$
$$ (b) ~~~~~ \sum_{k=1}^{n} \sigma(k) = \sum_{k=1}^{n} k \left \lfloor \frac{n}{k} \right \rfloor$$

The problem with (a) is that computing it (at least in my implementation) is slower than given above. The problem with (b) is that I don't understand how to compute prefix sum with such approach faster than in $O(n^2)$ time.

Is there a more efficient algorithm for this problem?

(The problem bank credits the original source of the problem as 2012 Kharkiv, Winter School, Day of Sergey Kopelovich, Problem H.)


texts: Algorithm to construct a parabola that hits a given target and avoids given boundaries

texts:
I'm working on a video game and I'm struggling with the math behind one of the enemies.  The enemy is a grenade launcher mounted on a vertical rail, which can slide up and down, and lob a grenade at any angle with any amount of force.  The grenade's path will be a parabola which must hit the player, but there are line segment boundaries in the way represented by their two endpoints which the parabola must avoid.
Here is a drawing:

What I'd like to do is calculate the equation for the parabola of the grenade which hits a target and misses all of the boundaries, from which I can figure out the position, angle, and force for the launcher to use.  The parabola must be subject to these three constraints:

The parabola must pass through the target point $(x_T, y_T)$
The parabola must pass through the line segment $\overline{RS}$
For each boundary $\overline{EF}$, if the parabola passes through the segment, it must not happen between the line $\overline{RS}$ and the target point.

Depending on where the target is, there may be no solution, in which case I'd like it to return that information.  If there is any solution there will be multiple; I would only need one.
What I've tried so far:
We can represent the parabola as $y-y_T=A(x-x_T)^2+B(x-x_T)$, which takes care of the first constraint, and means we need to find values for $A$ and $B$ that satisfy the other two constraints (we know $A$ must be negative because of the direction of gravity).  Then for each boundary $\overline{EF}$ on the map, with endpoints $(x_E,y_E)$ and $(x_F,y_F)$, we can represent the boundary line as $(y_E-y_F)x+(x_F-x_E)y+(x_E y_F-x_F y_E)=0$.  From that I can find the points of intersection between the line and the parabola, and make sure that for every boundary, the x-values of the points are either not between $x_E$ and $x_F$, or they are not between $x_S$ and $x_T$.  This quickly becomes a nasty quadratic equation, which then creates a system of linear inequalities that I don't know how to solve.  Can anyone think of a better way to approach the problem?


texts: Having trouble in understanding the definition of a clique

texts:
My definition says

  A clique is a graph that has an edge connecting every pair of vertices

but as I understand, an edge connects only two vertices. Like $A-B$.

If we want to connect three vertices, we need at least two edges. For example, $A-B-C$.

I don't understand how an edge can connect every pair of vertices.


texts: Joining points of polygon in correct order

texts:
I have a point's array of some 2d shape(polygon). The polygon could be either crossed or convex, I don't know it. And I want to join those points in the correct order.

My first thought was to take some point as an origin and start looking for the closest one and so on. But this approach doesn't work for some crossed polygons, for example: on Image1, it would go from x3 to x5 because it is closer than to x4, but what I really want is to join x1-x2-x3-x4-x5-x6.

After some thinking, I've realized that my requirement correct order is very unclear because on Image2 red lines are in the correct order too. So let's add the requirement that polygon lines shouldn't at least cross.

I really confused, can someone point me in what direction I should move? Maybe it's some famous algorithm but I just don't know how to google it properly. Thanks.

Image1:

Image2:


texts: What does "AC0 many-one reduction" mean?

texts:
What does $\mathsf{AC^0}$ many-one reduction mean?

I know about polynomial time reductions, but I'm not familiar with $\mathsf{AC^0}$ reductions.


texts: what is the general name of this problem?

texts: what is the general name of a problems where learning agent observe new data as a learning goes on. For example when playing platformer games one must incrementally learn new level areas and states while remembering all previous states so as to successfully proceed through the level.


texts: Regular expressions for set of all strings on alphabet $\{a, b\}$

texts:
I came across following regular expressions which equals $(a+b)^*$ (set of all strings on alphabet $\{a, b\}$):

$(a^*+bb^*)^*$
$(a^*b+b^*a)^*$
$(a^*bb^*+b^*ab^*)^*(a^*b+b^*a)^*b^*a^*$

I want to generalise different ways in which we can append to original regular expression $(a+b)^*$, to not to change its meaning and still get set of all strings on alphabet $\{a, b\}$. I think we can do this in two ways :

P1: We can concatenate anything to $a$ and $b$ inside brackets of $(a+b)^*$
P2: We can concatenate $(a+b)^*$ with any regular expression which has star at most outer level ($(...)^*$)
P3: I know $(a+b)^* = (a^*+b)^* = (a+b^*)^*= (a^*+b^*)^*$. So I guess P1 and P2 also applies to them.

Am I correct with P's?

Q. Also I know $(a+b)^*=(a^*b^*)^*=b^*(a^*b)^*=(ab^*)^*a^*$. Can we append some pattern of regular expressions to these also to not to change their original meaning?


texts:
I understand the concept behind Divide and Conquer, making one problem into sub problems and then merging the solutions together. However, from looking at a past paper a question has occured where it asks how 2^11 can be found using Divide and Conquer, I'm just confused how finding a power can be divided into sub problems =/

pow(2, 11) = 2 * pow(2, 5) * pow(2, 5)

pow(2, 5) = 2 * pow(2, 2) * pow(2,2)

pow(2, 2) = pow(2, 1) * pow(2, 1)

pow(2, 1) = 2

would this be correct?


texts:
How can I make a finite automaton which does not end in string ab.

With the alphabet a,b

I made 3 states. For the first one it is accepting states and thus accept the empty string.

So here is a table I made. State 1 is initial state

        input   goes to state input goes to state

State 1

         b       1             a      2

state 2

          b       3             a       2

state 3

            b       3              a      3

But will it work?


texts: Is the Theory of Computation Necessary for a General-Purpose Beginner?

texts:
I'm interested in developing a solid CS/Electrical Engineering foundation that would enable me to branch out in the future to any CS-related field. I've read other literature recommendations and have recently gotten ahold of Sipser's second edition Intro. to the Theory of Computation, contains the theories of finite automata, complexity, and computability.

As a noobie, I didn't expect the book to read like a math textbook, and I found it difficult to stay interested in the material as it was difficult to feel it's relevance to any kind of practical computation. I'm not terribly interested in theory, but I want to develop a deep understanding of computers.

Is there some other platform missing that would enable me to appreciate the TOC? Is the TOC simply a starting point that I must grind through?


texts: Sorting lower bounds for almost sorted array

texts:
Can't find a good way to tackle the problem. Would appreciate any help.

$A$ is an $n$ items array from an ordered set, in which every item is at most
 $\log n $ indices away from its position in the sorted array.

Show that:

The array can be sorted in $O(n\log\log n)$.
There is a lower bound of $\Omega(n\log\log n)$ for sorting $A$ using comparisons.

The general idea is more important than details for both assertions.


texts: Existence of Optimal Policy for infinite-state MDPs

texts: It is well-know from Puterman's book (1994) that in any finite-state MDP, if there exists an optimal policy, then that policy is stationary and deterministic. How about MDPs with continuous state spaces with finite-action space? Assume that the rewards are bounded.


texts: Polynomial time approximation of NPC problem

texts: I have found a polynomial time solution of an NPC problem. My algorithm give exact result in most cases. For example if I run my algorithm for 20000 problem instances, then it fails 10 times to give correct result. But, I am unable to prove the approximation ratio mathematically. Is it feasible to show it with the experimental results? I am waiting to hear the possible solutions for it.


texts: Which attributes to consider for credit card fraud detection on an ATM?

texts:
I am working on a project in which I am supposed to come up with a system that detects fraud from a credit card transaction. I read about techniques that others have used and decided to use Artificial Neural Networks for their adaptability.

WHAT THE SYSTEM MUST DO

My system is supposed to detect fraud on a credit card used on an ATM, that is, I am assuming that the user has already been granted access to the account by entering their PIN on an ATM. In other words, I am saying before the transaction is authorized, pass it through the fraud detection system so  we can check if it is fraudulent or not.

ATTRIBUTES THAT I AM THINKING TO CONSIDER

The amount of money to be withdrawn  - here I am assuming that each
user has a certain range of money that they usually withdraws; any
deviations are treated a suspicious.
Time taken to input PIN - here I am thinking that each user has a range of time that they usually take to input PIN; any deviation is treated as suspicious.

Questions

Which attributes can I take into consideration that enables me tell whether a  transaction is fraudulent or not?
What others have considered to solve this problem?
What do you recommend me?
What can be inputs to my Neural network?

Thanks for your ideas.


texts:
I was just researching Fibonacci encoding of integers. Numbers are encoded in binary and where no two consecutive bits are equal to 1 - other than to terminate the number.

Now other schemes are possible, for example having three or more 1's terminating the number. These representations are more efficient (shorter) for larger numbers but less so for small numbers.

My question is, is it possible to have an optimal scheme where the number of terminating 1's increase as the size of the number increases? And have no ambiguity.

Some examples to clarify:

a. 0 = '1', 1 = '01', 2 =  '001', 3 = '0001', 4 = '00001', 5 = '000001', 6 = '0000001'

b. 0 = '11', 1 = '011', 2 = '0011', 3 = '1011', 4 = '00011', 5 = '10011', 6 = '01011'

c. 0 = '111', 1 = '0111', 2 = '00111', 3 = '10111', 4 = '000111', 5 = '100111', 6 = '010111'

These use 1, 2, and 3 terminating 1's respectively.


texts: Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$

texts:
More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) represent this structure. Let's call this hypothetical structure $S$. I need the structure to support just a single function $p : S \times \{1 \ldots N\} \rightarrow \{1 \ldots M\}$.

It's also safe to assume that I will call this function in order, meaning I will be interested first in $p(S, 1)$, then in $p(S,2)$, etc.

I can represent this structure as an array of $N \times \lceil log_2(M)\rceil$ bits, but that seems too memory inefficient when $M$ is small and $N$ is in billions. I have a hunch that perfect-hashing might be of use here.


texts: Compendium of approximation ratios, with narrower scope and more up to date than the NP-compendium?

texts:
I usually check the NP-compendium from Pierluigi Crescenzi, and Viggo Kann when I want to know the APX status and approximability results of a problem.

However, I understand that maintaining it is a lot of work, which explains why it is not up to date in some cases. By not up to date, I do not mean non-exhaustive, but that better results on some problems are not included.

Does anyone know an equivalent and more specific website focused only on approximation, which would be more up to date ?

I am not really asking the same question as this one, or this one, but I understand that they may bring the same answer.

Remark: The last example I found was on the Minimum Steiner Tree with distance 1 and 2 on complete graphs, which is said to be approximable in 1.28, but there is a paper from 2009 which provides a 1.25 ratio. It may have been updated.


texts: What is the purpose of Bayesian networks?

texts:
I have seen a lot of explanations of what Bayesian networks are, but I simply cannot wrap my head around their use in code. So here is my three part question.

Am I right in my definition of Bayes nets? Bayesian networks are a way to (visually) portray how variables/events are linked and how they will affect each other. Probabilities can be added to each node to give you a greater sense of what will happen. In conjunction with an acting AI, Bayes nets are used to predict the AI's actions and inform what it should be doing, i.e. giving minimax a better prediction.
Can you give a pseudo code representation of a Bayes net?
Let's get a little more specific. I have a creature simulator, the creature has a home where he sleeps and, there are patches of grass where he eats. There are other creatures out there that he wants to avoid because they will fight him. So his action -> reaction set is:

{hungry->find food -> eat food
tiered -> go to shelter -> sleep
in danger -> avoid other creature
under attack -> run to shelter}

I am trying to express this as an mdp so that it will learn what actions are best when; and what are the best spots (most prosperous & least dangerous) on the map.

How, if at all, am I supposed to use a Bayes net? If the situation requires probabilities feel free to add your own, pseudo code also appreciated.


texts: How to convert a string (number representation) to an arbitrary base using custom alphabet?

texts:
I'm trying to figure out an efficient way (without recursion) to convert a string (number representation) from one arbitrary base to another using custom alphabet. But I cannot think of a very fast efficient method (byte shift?) to do it:
def convert_base(target, base_from, base_to):
  alphabet = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
  base_to_alphabet_slice = alphabet[:base_to]
  base_from_alphabet_slice = alphabet[:base_from]
  result = ''
  for char in target:
    result += ...
  return result

# Expected results:
print(convert_base('E', 16, 2))
# Output: '1110'

print(convert_base('1110', 2, 16))
# Output: 'E'

print(convert_base('E', 16, 10))
# Output: '14'

Can someone suggest a good method for this?


texts: Question about proof of Kannan's Theorem

texts:
The wikipedia page (here) assumes the existence of some $L \in \Sigma_4 - SIZE(n^k)$. How can one show that such a language exists?

This is related to a homework question, I'd prefer some hint to the answer. Using the hierarchy theorems, we can find some language $L \in SIZE(n^{k+1})$ for which $L \not \in SIZE(n^k)$. I doubt all such languages would be in $\Sigma_4$, but maybe some of them with a special property may be?

It seems we could just as well take something in $\Sigma_3$. Could we maybe take the language $L$ decided by the smallest such circuit? So then we could make a sentence like

$x \in L \iff \exists C_n $ such that for $\forall$ circuit families $C'_n \exists x'$ so that $C_n(x) = 1$ and $(|C'_n| > |C_n|$ OR $C'_n(x') != C_n(x'))$?

But it seems like this choice depends on $|x|$.


texts: What is the difference between SIZE(n^k) and P/poly?

texts:
What is the difference between $\text{SIZE}(n^k)$ and $\text{P}/\text{poly}$?
For reference:

$\text{SIZE}(n^k)$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with $O(n^k)$ gates.

$\text{P}/\text{poly}$ is defined as those problems over $\{0,1\}^*$ which can be solved by an infinite family of polynomial-size circuits ${C_n}$.

What is the difference between these classes?


texts: Looking for algorithm to iterate over matrix

texts:
I have such a product example:

{
  "color": ["red", "blue"],
  "material": ["metal", "textile", "plastic"],
  "options": ["handle", "wire", "bt"],
  "textile": ["silk", "cotton"]
}

I need to know what algorithm can help me to produce all options possible for such product, f.e.:

{
  "color": "red",
  "material": "metal",
  "options": "handle",
  "textile": "cotton"
}

Each option can be single for a product.

Obviously, I don't want to use tons of for loops.
It should be possible to easily add new options and new variations, f.e.:

{
  "color": ["red", "blue", "new"],
  "material": ["metal", "textile", "plastic", "new"],
  "options": ["handle", "wire", "bt", "new"],
  "textile": ["silk", "cotton", "new"],
  "newOption": ["new option]
}


texts: How to derive an algorithms that generates check sums

texts:
Column S contains the check sums of the values given in columns R and Xc. Does anyone here have an idea about how to find the corresponding algorithm to calculate the check sums? Thanks in advance

    R    Xc   S
   647   72   218
   441   47   618
   594   67   188
   581   55   517
   497   58   865
   553   65   661
   541   52   309

Best regards,

Holzi


texts: Proving that max flows of undirected graph and equivalent directed graph are equal

texts:
There is an undirected graph $G$. A graph $H$ is constructed by changing each edge $(a,b)$ in $G$ to a pair of directed edges $(a,b)$ and $(b,a)$. How to prove that the maximum flow in $H$ is equal to the maximum flow in $G$?

I don't really have any idea how to start it. I just know that I can use Ford-Fulkerson on $H$ and update the reverse edge such that $f(a,b)+f(b,a)=c(a,b)$ but that's it.


texts: References on comparison between quantum computers and Turing machines

texts:
I was told that quantum computers are not computationally more powerful than Turing machines.
Could someone kindly help in giving some literature references explaining that fact?


texts: Does preparing min DFA by combining equivalent states always result in min DFA

texts:
I know the following fact:

  If $Ma_N=\{w:n_a (w)=Nk,k≥0\}$, then
  Number of states in
  $$Ma_{N1}×Ma_{N2}
=Ma_{N1}∪Ma_{N2}
=Ma_{N1}∩Ma_{N2}
=Ma_{N1}-Ma_{N2}
=LCM(N1,N2)$$
  where $n_a (w)$ is the number of occurrences of $a$ in $w$

I recalled the example I solved: the DFA for the language $(111+11111)^*$. It was given as follows:

It was backed by the fact that Any number greater than 8 can be factored into sum of 3s and 5s.

Q.1 Can we interpret this language as union of two: $(111)^*\cup (11111)^*$?

Q.2 If yes, then should forming union DFA by forming product DFA (and making desired states final as required by union operation) of above two languages $(111)^*$ and $(11111)^*$ and then applying DFA minimization by finding equivalent states result in 9 states? I tried it as below using JFLAP (product DFA on left and auto generated min DFA on right). But I didnt get 9 states. Instead I got number of states $=LCM(3,5)=15$ states.

Q.3 So can we conclude we cannot always get minimum DFA by the approach of combining equivalent states (may be especially when the DFA can be simplified using some mathematical insights)? Or did I made some mistake?


texts: Equally distributed/packed spheres within a sphere

texts:
I need to equally distribute a variable number of spheres within a larger sphere (the volume of the spheres depends on how many there are).  Are there any algorithms for doing this? An approximate solution would be acceptable.

When searching, I was only able to find material about equally distributing points on the surface of a sphere, whereas I want to distribute the points within the volume of the sphere.


texts:
The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window.

arr = 1, 3, 5, 10, 6, 9, 2

k = 3

would yield a result of 3, 5, 6, 9, 6

Using std::priority_queue (in C++) for the heap implementation, there's a minHeap and maxHeap.  In a single iteration, insert the value entering our window in the correct heap, rebalance as necessary, add the median to the result (if the window is big enough), then remove the value which is leaving the window from whatever heap it's in: This could require moving all but 1 heap element to the other heap, then moving them back.

The lesson I saw this on actually inherits from priority queue and implements remove functionality: Linear search [O(k)], then removes the item [O(log k)].  It claims O(n * k) complexity as at each iteration the insertion is O(log k) and the search to remove is O(k). I assume in an interview extending a heap beyond it's traditional form is not only unnecessary but probably frowned upon.

I'm curious of the complexity at which the version w/o the direct removal would run.  The O(n) part is obvious but the sub operations not as clear to me.  A heap will generally have k/2 items in it.  In the worst case you delete [O(log k)] and then insert [O(1)] each one.  My mind is telling me O(n * k log k) but I wouldn't bet my house on it.

For the record: Not looking for an optimal solution - just the runtime of this one.

insert(num):

  if maxHeap is empty or maxHeap.top > num:
    push num on maxHeap
  else
    push num on minHeap

  // rebalance
  if maxHeap.size > minHeap.size + 1:
    move maxHeap.top to minHeap
  else if minHeap.size > minHeap.size
    move minHeap.top to maxHeap

get Median:
  if maxHeap.size == minHeap.size:
    return maxHeap.top + minHeap.top / 2.0
  else if maxHeap.size > minHeap.size
    return maxHeap.top
  else
    return minHeap.top

remove(num):

  if maxHeap.top >= num:
    move maxHeap.top to minHeap until maxHeap.top == n;
    remove maxHeap.top
    move minHeap.top to maxHeap until balanced
  else
    move minHeap.top to maxHeap until minHeap.top == n;
    remove minHeap.top
    move maxHeap.top to minHeap until balanced

findSlidingWindowMedian(arr, k):
  // This is where the mystery is.  Worst case we have to remove
  // a number at the bottom of a k/2 sized heap.  So that would be
  // log k for k/2 operations then O(1) for k/2-1 operations?
  left = 0
  for right = 0 to arr.size
    insert(arr[right]):

    if right >= k-1
      add median for current window to result
      remove(arr[left])
      left += 1

  return result


texts: How is the control unit affected by pipelining?

texts: Compared to not using instruction pipelining. What is different?


texts: What does it mean for a random number generator's sequence to be only 1-dimensionally equidistributed?

texts:
Whilst reading up on Xorshift I came across the following (emphases added):

The following xorshift+ generator, instead, has 128 bits of state, a maximal period of 2^128 − 1 and passes BigCrush:
[snip code]
This generator is one of the fastest generator passing BigCrush; however, it is only 1-dimensionally equidistributed.

Earlier in the article there's the following:

[snip code]
Both generators, as all xorshift* generators of maximal period, emit a sequence of 64-bit values that is equidistributed in the maximum possible dimension.

What does it mean for a sequence to be equidistributed in one dimension vs. multiple dimensions vs. not at all?


texts: Algorithm to color the edges of the square of a cycle

texts:
It is known that any power of cycle on even vertices is in Class 1, that is, can be edge colored in $\Delta$ colors, where $\Delta$ is its maximum degree which equals twice the power. But, I wish to know a specific algorithm to edge color the powers of cycles of even order.
Say, I have the square of a $18$ cycle. Now, this graph consists of a disjoint $18$ cycle, and two disjoint $9$cycles.  The $18$ cycle can be easily colored with $2$ colors. But, the two disjoint $9$ cycles being odd, must require $3$ colors each, which are in turn distinct from the two colors used on the $18$ cycle. This implies that the graph is not a Class 1 graph, that is requires one more color than its degree. So, is the first premise that all powers of cycles of even order are class 1 false. And, if true, what can be a general algorithm to do so for any power of a cycle? Any hints? Thanks beforehand.


texts: Edit distance (Levenshtein-Distance) algorithm explanation

texts:
I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo».

According to this site we'll get the result matrix:

What I don't understand is: In case of comparison the last «o» from «solo» with the first «o» of «oslo» will see the submatrix:

3 2
4 3

As far as I understand, in order to calculate the bottom right value, which is equal in this example to 3 of this submatrix, we'll get the min(3, 2, 4) + (0 if the letters are the same, otherwise 1). So, why in this example the bottom right value is equal to 3 and not to 2?


texts: Convert a decimal floating-point number into a binary floating-point number

texts:
Let's say I have a decimal floating-point number, i.e. a mantissa and precision (negative exponent), both represented as integers. How do I convert this into a binary floating point number (of the sort you find in most programming languages, with only the standard operations available). This should be done with maximum precision, ideally. The naive method of simply calculating $m \cdot 10^e$, where $m$ is the mantissa and $e$ the exponent, turns out to be very imprecise when $e$ is large, unfortunately.

I was also wondering how to do the reverse. I suspect the algorithm can't simply be reversed, due to the different representations.


texts: Is O((n^2)*log(n)) greater than O(n^(2.5))?

texts: I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?


texts: How do I manage flow control with no ELSE statement? (on Turing machine)

texts:
I have been given the problem of writing a turing machine with the commands:

if, while, whileNot, read X, write X, goLeft, goRight, HALT

The problem was simply "calculate a two's complement number, from number with \$ on the left and # on the right, ex: $10110100#"

I started by writing this pseudocode to flip the bits:

whileNot read #
    if read 1
        write 0
    if read 0
        write 1
    goRight

But then I realized once 'write 0' executes, 'if read 0' will immediately be true and undo my work. I need a statement that is effectively 'else if read 0', is there any turing trickery that I can employ to do something like this?


texts:
I need to determine whether the following problem $X$ is in coNP:

  Given a graph $ G=(V,E) $ and a positive integer $s\leq|V| $, is there an independent set that is the largest for $G$ of size at least $s$?

My solution for this was that in fact the above problem is in coNP because we can provide an NP solution for $\overline{X}$ which has the following certificate and certifier.

The certificate being a set of vertices $V'$.

The certifier does two things:

Checks if  $V' \subseteq V$.
Checks for each pair of vertices in $V'$ if there exists no edge.
Checks if  $|V'|<s$.

The certifier computes this in $O(V+E)+O(1)$.

Is this the right way to show if X is in coNP?

Edit: The independent set is required to be the largest possible for graph $G$.


texts: Woman optimal Gale Shapley Stable Matching

texts:
I am learning about Gale Shapley Algorithm now, and I understand that it is Man Optimal and that all possible executions will yield a stable matching where each man gets the best partner that he can have. I was thinking is it possible to have a woman optimal solution with a guaranteed stable matching? Let's say each woman has a different man as her most preferred partner. Then can we say that we can ensure stable matching by simply assigning the most preferred man to each woman?

I am having problem understanding that, since by definition the matching is stable if no man or woman prefer another to their current situation. Wouldn't it give as stable matching if each woman has the most preferred man, considering they all unique?


texts:
I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...)
I am really out of thoughts

I have X number of classes each with starting, and finishing time, and N number of free classrooms.
And I want to find the maximum number of non-conflicting classes that can be scheduled in those N classrooms.

What I've tries so far :

- First algorithm:

Sort Classes in ascending order according to the finishing time of each class.
Starting with the minimal finishing time, pick all the intervals that don't conflict with it and save it in a subset.
Repeat the first two steps on the very next interval that conflicts with the one we were working on before.

Why wrong?

Ex: we have 4 classes (1,4) (2,6) (6,7) (4,8) and we want to find the maximum number of non-conflicting ones that can be fit in 2 classes.

Starting the algorithm on (1,4) will give me subset {(1,4)(6,7)} that can be fit in the first classroom, and in the second classroom i need to put either (2,6) or (4,8) but not both since they conflict, so in total 3 of those classes can be fit in 2 classrooms using this approach.
However in real life you can put {(1,4),(4,8)} in a room and {(2,6),(6,7)} in the other, so all of the classes can be held in the 2 rooms.

- Second algorithm

Sort Classes in ascending order according to the starting time of each class.
Starting with the minimal starting time, pick all the intervals that don't conflict with it and save it in a subset.
Repeat the first two steps on the very next interval that conflicts with the one we were working on before.

Why wrong?

Ex: we have 4 classes (1,2) (2,1000) (6,7) (7,8) and we want to find the maximum number of non-conflicting ones that can be fit in 1 class.

Starting the algorithm on (1,2) will give me subset {(1,2)(2,1000)} that can be fit in the first classroom, and that's it, so in total 2 of those classes can be fit in a classroom using this approach.
However in real life you can put {(1,2),(6,7),(7,8)} in a room and, so 3 of the classes can be held in a room.


texts: How many shortest distances change when adding an edge to a graph?

texts:
Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in total.

Every time we add one edge $(u,v)$ to $E'$, we consider the shortest distances between all pairs in $(V, E')$ and $(V, E' \cup \{ (u,v) \})$. We count how many of these shortest distances have changed as a consequence of adding $(u,v)$. Let $C_i$ be the number of shortest distances that change when we add the $i$th edge, and let $n$ be the number of edges we add in total.

  How big is $C = \frac{\sum_i C_i}{n}$?

As $C_i = O(|V|^2)=O(n^2)$, $C=O(n^2)$ as well. Can this bound be improved? Note that I define $C$ to be the average over all edges that were added, so a single round in which a lot of distances change is not that interesting, though it proves that $C = \Omega(n)$.

I have an algorithm for computing a geometric t-spanner greedily that works in $O(C n \log n)$ time, so if $C$ is $o(n^2)$, my algorithm is faster than the original greedy algorithm, and if $C$ is really small, potentially faster than the best known algorithm (though I doubt that).

Some problem-specific properties that might help with a good bound: the edge $(u,v)$ that is added always has larger weight than any edge already in the graph (not necessarily strictly larger). Furthermore, its weight is shorter than the shortest path between $u$ and $v$.

You may assume that the vertices correspond to points in a 2d plane and the distances between vertices are the Euclidian distances between these points. That is, every vertex $v$ corresponds to some point $(x,y)$ in the plane, and for an edge $(u,v)=((x_1,y_1),(x_2,y_2))$ its weight is equal to $\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2.}$


texts: Is this known as a fact or from some analysis that the MNIST data-set is almost as if its sampled from some low (~10?) dimensional manifold? Is there a locally linear embedding to a low-dimensional space?  Of course I don't expect the data will be exactly on some low dimensional manifold; there will be some noise.


texts:
Let $L = \{xyx \mid \text{ for some }x,y \in \{0,1\}^+\}$. Is this language regular?

So I was trying to construct a DFA, but I don't how to do this with this language.


texts:
In CNF SAT, each clause (A or B or C or...) must contain at least one true literal. The resolution rule applies to pair of clauses who have exactly one opposite literal.

(A or B or C) and (!A or D or E) => (B or C or D or E)

I say that this rule is complete, in the sense that if a formula is unsatisfiable, I can prove it by applying the rule exhaustively (on hard instances, an exponential amount of times) until one empty clause is produced. If a formula has a unique solution, I can apply the rule until every unit clause is produced.

1-in-k SAT is a NP-complete variant where exactly one variable per clause (A,B,C,....)=1 is true. Given a pair of clause with one opposite literal, and no common literal, I can also produce a third one:

(A,B,C)=1 and (!A,D,E)=1 => (B,C,D,E)=1

Question: Is this rule complete for unsatisfiable and uniquely satisfiable 1-in-k formulas?


texts: Demonstrate that DPDA is closed under complement by construction

texts:
I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I got has something that at the end does not fit. Could you give me a hand?

The main problem happens with the ε-moves. A PDA could finish reading its input in a non-final (rejecting state) but can still move to a final (accepting) state through an ε-move and end up accepting the string. This means that just adding a dead state and complementing the states does not work. I already solved the problem of possible infinite sequences of ε-moves, so that is not a main part of my question.

EDIT: As far as I understand, if the DPDA reaches end of input and is in an accepting state and moves to a rejecting state through an ε-move it would still accept it (as it reached a final state with no input symbol left to read).

Please let me know if I can be more clear.


texts: Can POSIX BRE express all regular languages?

texts:
It appears that "Basic Regular Expressions" as defined by POSIX.1-2008 do not support alternation, a|b (although some grep implementations recognize the escaped version, \|).

Since the regular languages are closed under union by definition, does this mean that POSIX BRE has less expressive power than a finite automaton? Or is there some way to simulate alternation using other constructs?


texts:
Does removing the leading(or trailing) n bits of any given hash have any negative effects other then increasing the likeliness of collisions? Does appending 2 hashes of the same object with different seeds have have any negative effects?

For some context I am building a Bloom filter that has a variable size and would like to either increase or decrease the standard 32/64 bit hashes to fit the required size of the bloom filter


texts: Recovering the transition function of a Turing machine with a known number of states

texts:
Suppose we have a Turing Machine and know how many states it has as well as bound on its running time, but do not initially know its transition function.  Is it possible to determine its transition function (up to a relabeling of its states and disregard for inaccessible states) by noting its behavior on only finitely many strings?  (By behavior I mean  a record of its computation histories leaving out the information of which state it is in at any particular step.)

On the one hand, there are only finitely many Turing machines with a set number of states, so we could definitely run them on all of the finitely many given strings to determine if a given transition function is not a candidate.  However, I realize that Rice's Theorem might prevent us from determining the behavior on all inputs given only its behavior on inputs up to a given length.  Even if it is not possible for Turing machines to recover its transition function, is it possible for simpler computation models like DFA's and PDA's?  Thanks for your help.


texts: Constructing Context Free Grammar with 3 terminal symbols, with two dependent pairs

texts:
I am new to Context Free Grammars and am having trouble wrapping my head around how to approach writing a CFG for the following language:

L = {a^n b^m+n c^m | n>=0, m>=1}

I have a basic understanding of how this should work, but the examples we went over in class usually only had either 2 symbols dependent on each other, or completely independent. Having to determine the number of b's based on the number of a's + c's is throwing me for a loop.

I am thinking this will involve the union of several grammars.

s1 - no a's, equal b'c and c's
s2 - equal a's and c's, 2x b's
s3 - more a's than c's
s4 - more c's than a's

I believe I know how to approach the first two, but the second two I am a bit fuzzy on how to proceed.


texts: Create a potential function for an abstract queue data structure to show constant amortized-time complexity

texts:
Consider a variation of a Queue called MaxQueue, Q, that has the following operations:

dequeue(Q): removes and returns the first element of Q
enqueue(Q, s): Appends the integer s to the end of Q
maximum(Q): returns the largest integer in Q (but does not delete it)

The MaxQueue data structure also contains a sequence called the "suffix maxima". An element, x, is a "suffix maximum" in a sequence if all elements that occur after x are smaller in value.
MaxQueue is implemented using a singly linked list to represent the sequence with additional pointers to the front and back of the queue, and to have doubly linked list of the suffix maxima (which are arranged in the same order as they are in the sequence).
See this link for an example: https://ibb.co/f2KBtHN

Question: Prove that the amortized time complexity of the three operations are all O(1). (Define a potential function based on the number of suffix maxima in the sequence.)

I don't really know how to start this question. I know a potential function tends to be of the form $an + bm$ where $a$ and $b$ are constants and $n$ and $m$ are variables you set depending on the question. The hint suggests basing it off of the number of suffix maxima in the sequence which I believe should be reflected in these variables but I'm not sure how.


texts: Approximating the dominating set on a certain kind of DAG

texts:
A dominating set on a directed graph $G=(V,E)$ is a subset $D$ of $V$ such that for all $v\in V$ it holds that $v\in D$ or there is an $u\in D$ such that  $(u,v)\in E.$

For a concrete problem (size reduction of endgame tablebases), I want to approximate the dominating set of a directed acyclic graph with the following properties:

Each vertex $v\in V$ has a nonnegative integer $\mathop{\mathrm{DTM}}(v)$ assigned to it (with DTM standing for distance to mate)
For each pair of vertices $(u,v)$, if $(u,v)\in E$, then $1+\mathop{\mathrm{DTM}}(u)=\mathop{\mathrm{DTM}}(v)$ (if a move leads from $v$ to $u$, then the distance to mate from $v$ is one larger than that from $u$)
For each vertex $v\in V,$ there exists a vertex $z\in V$ with $\mathop{\mathrm{DTM}}(z)=0$ such that a path from $z$ to $v$ exists (each position can be brought to mate)

Given these boundary conditions, is there an efficient way to approximate $D$ for large graphs (more than 100'000'000 nodes?)


texts: Proving formula for derivative of Kleene star

texts:
Prove that for any symbol $a$ and regular expression $r$ it is true that:

  $$\partial a(r^* ) =  \partial .a(r)(r^* )$$

My attempt:

Induction on regular expression $r$

Base cases:

1) $\emptyset $

$\partial a(\emptyset^* ) =  \partial a(\varepsilon) = \emptyset$

$\partial a(\emptyset) (\emptyset^* ) =  \emptyset \emptyset^* = \emptyset \varepsilon = \emptyset$

2) $\varepsilon $

$\partial a(\varepsilon^* ) =  \partial a(\varepsilon)$ = $\emptyset$

$\partial a(\varepsilon) (\varepsilon^* ) =  \emptyset \varepsilon^* = \emptyset \varepsilon = \emptyset$

3) $a\in\Sigma$

Case $a=b$:

$\partial a(a^* ) =  $

$\partial a(a) (a^* ) = \varepsilon (a^*) = a^*$

Case $a \neq b$:

$\partial a(b^* ) =  $

$\partial a(b) (b^* ) = \emptyset (b^*) = \emptyset$

But how to prove for Inductive Step when regular expression $r$ is:

1) Concatenation: $r=\alpha\beta$

2) Union: $r=\alpha + \beta$

3) Kleene Star: $r=\alpha^*$


texts:
An indexed file contains at most $2^6$ records. The indexed file is stored in a memory with $2^{14}$ cells. What is the maximum size of the index in bits?

If I would like to find the maximum size of the memory in bits I can simply just:

$2^{14} \ast 8 \text{ bit } = 131072 \text{ bit}$

I found the solution but no explanation was given to it:

6 + 14 = 20 bits
For each entry: $2^6 \ast 20 = 64 \text{ bits } \ast 20 \text{ bits}$
Result being: 1280 bits

I know that an Index contains a list of keys stored in the file together with entries that point to where the record containing each key is stored. It is the very first thing to be transferred to the memory to allow memory access to these records.


texts: identities property of squaring functor?

texts:
From page 31 of The algebra of programming :

  Next, consider the squaring functor $()^2: Fun \leftarrow Fun$ defined
  by

  $$ A^2 = \{(a, b) | a \in A, b \in B\} \\ f^2(a, b) = (f a, f b) $$

Functors are required to preserve identities and composition:

$$
F(id_A) = id_{FA} \\
F(f \circ g) = Ff \circ Fg
$$

The second property is easy:

$$
(f \circ g)^2 (a, b) = ((f\circ g) (a), (f\circ g) b) \\
(f^2 \circ g^2) (a, b) = f^2 (g (a), g (b)) = ((f\circ g) (a), (f\circ g) (b))
$$

But I can't figure out how the squaring functor preserve the identity property. Could anyone help?


texts:
When software boils down to assembly, it is just a sequence of instructions like this:

mov rax, 1
mov rdi, 1
mov rsi, message
mov rdx, 13
syscall
mov rax, 60
xor rdi, rdi
syscall

I am not sure exactly how the program evaluator works (the thing navigating about the assembly / machine code), but I think it just goes sequentially through the assembly code, jumping to different locations in the assembly / machine code when it encounters a jump/branch instruction.

Essentially, it is sequential computation. The information on the ordering of instructions is inherent in the fact that they are written next to each other in the code (they have an adjacent location).

I understand there could be parallel computation, but not too much interested in that for this question.

In cognitive architectures, instead of sequential computation, it is as if they make a bunch of decisions, and then perform the action. So instead of the next "instruction" being adjacent to the current instruction, the next instruction is computed dynamically. Not sure how to explain this any deeper.

Roughly, instead of the next instruction being found by looking ahead in some location space, the instruction is found by analyzing some information and selecting it based on some decision. Rule-based systems seem to be somewhat similar, but I haven't seen them described as models of computation.

Wondering if there is any research on this topic. Alternatives to the sequential computation method, such as this dynamically-computed-instruction method (like rule-based systems).


texts: Is function application actually a memory manipulation algorithm?

texts:
I thought about how in lambda calculus (and many implementations of functional programming languages) function (lambda) application and lambda itself, as a construct, are "primitive things", usually somehow implemented by an interpeter. Then I thought, can you "boil-down" these two things to more primitve stuff.
For instance, we have a following expression (apply is usually implicit by the syntax convetions, but whatever)

(apply (\x.\y.x) (a b))

The interpreter:
1. Constructs a new environment, where arguments are bound to lambda's terms, i.e. new_env = this_env.append({"x":a, "y":b, "body":"x"})
2. Performs a rewrite of the whole application term with lambda's body, i.e.
  new_env["body"]

Given only the environment manipualtion "primitives", like: "construct", "append", and "get", doesn't that make whole lambda calculus just a clever trick to hide memory ("tape") mutations? Now I know that turing machine and lambda calculus are equivalent, but is there something more to LC than just what I've described? What have I missed?


texts: Reducing a non-RE language to its complement

texts:
Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them?
I couldn't find one...


texts:
I am reading Data Structures and Algorithms by Alfred Aho, Jeffrey Ullman, et al. In the section about lists it's said:

We should note that a position in a linked-list implementation of a list behaves
differently from a position in an array implementation. Suppose we have a list with
three elements a, b, c and a variable p, of type position, which currently has position
3 as its value; i.e., it points to the cell holding b, and thus represents the position of c.
If we execute a command to insert x at position 2, the list becomes a, x, b, c, and
element b now occupies position 3. If we use the array implementation of lists
described earlier, b and c would be moved down the array, so b would indeed occupy
the third position.
However, if the linked-list implementation is used, the value of p, which is a pointer
to the cell containing b, does not change because of the insertion, so afterward, the
value of p is "position 4," not 3. This position variable must be updated, if it is to be
used subsequently as the position of b.†

I don't understand how do position works? It's said that position works differently in pointer implementation that that of array but, the result seems to be the same on both. In both implementation position (pointer) moves forward. Then, what's the difference? I appreciate your answers.


texts: Why would this be a deterministic context free language? $L = \{a^n b^n | n>0 \}$ $\cup$ $\{ a^n b^{2n} | n < 100 \}$

texts:
so the book that I'm reading says this is a deterministic context free language
 $L = \{a^n b^n | n>0 \}$ $\cup$ $\{  a^n b^{2n} | n < 100 \}$

But i think this is wrong Because :

at the beginning of building the DPDA, we have to decide whether we should go with the first one or the second, and considering both of them start with a there is just no way we could build a DPDA right?? or am i wrong?

i also tried solving this by first building the $a^nb^n$ and then going for the second one if the stack is not empty, but still couldn't come up with anything, i tried putting 2 a's for every a input but didn't work

so how is the book saying this can be build with a DPDA?

Also i have to say I KNOW that non infinite languages are regular, but this one is not infinite!


texts: Find median of unsorted array in $O(n)$ time

texts:
To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take $O(n \log n)$ time.

Can we do the same by some method in $O(n)$ time? If we can, then how?


texts: Algorithm for using power series to numerically solve a partial differential equation given a boundary condition?

texts:
Motivation:
Following this discussion about using asymptotic expansions (i.e. polynomial power series) for numerically solving partial differential and algebraic equations (PDAE), I couldn't find any implementation of the method. So I'm thinking of implementing a SymPy function similar to Mathematica's AsymptoticDSolveValue (here)  but for PDEs (here or here). So far I'm able to generate a symbolic multivariate polynomial given a list of non-negative integers D=[d1,...,dm] (here, here and here).
Example:
Now I'm able to use the symbolic multivariate polynomial to numerically solve a PDE. For example (from here) given the PDE:
$$\frac{\partial^2 u}{\partial x_1^2} - \frac{\partial^2 u}{\partial x_2^2}=0 \, ,\tag{1}$$
and the boundary conditions:

$u(x_1,0)=x_1^2+x_1\, , \tag{2}$
$u_{x_2}(x_1,0)=2x_1+1 \, , \tag{3}$

I can generate a 2D symbolic polynomial in Sympy:
from itertools import product
from sympy import IndexedBase, symbols, Poly
D = (5, 5) # 5 and 5 are just some random integers, any non-negative integer should do
d = len(D)
indices=list(product(*map(range, D)))
a = IndexedBase('a')
coeffs = {i: a[i] for i in indices}
vars = symbols(f'x1:{d+1}')
u = Poly(coeffs, *vars)

Equation 1 can be implemented as:
pde=u.diff(0,0).add(-u.diff(1,1))

Implying
$$j(j+1)a_{i,j+1}=(i+1)(i+2)a_{i+2,j} \tag{4}$$
The first boundary condition:
u.eval(1,0)

Implying
$$a_{0,0}=0 \, , \, a_{1,0}=1 \, , \, a_{2,0}=1 \, , \,a_{i,0}=0 \, \forall \,(2<i) \tag{5}$$
and the second boundary condition
u.diff(1).eval(1,0)

giving
$$a_{0,1}=1 \, , \, a_{1,1}=2 \, , \, a_{i,1}=0 \, \forall \, (2<i) \tag{6}$$
Now from this point it is just a system of nonlinear algebraic equation of $a$s (in this specific case linear). Which should be solvable with other analytical/numerical methods.
Question:
I want to automate the process above. I want to have a function:
AsymptoticPdeSolve(eqns,fs,vars,D)

Where eqns is the set of symbolic partial differential expressions, fs are the set of functions we want to solve, vars are the variables and D is the dimension of our multivariate polynomials.
I would appreciate if you could help me know what is the best algorithm for this process. I will use an existing symbolic library/software like SymPy, so anything already existing doesn't need to be reimplemented.
P.S. Axiom-FriCAS has a seriesSolve function which source code can be found here. Also since I posted this question, Nicolas CELLIER was so kind to implement an early version in sympy which can be seen in this Jupyter notebook.