texts: Why do Benes networks form bipartite graphs when you build a constraint graph for them?

texts:
I was learning about Benes networks and was wondering why they formed bipartite graphs (and thus are two colorable) when one draws a constraint graph for them. The constraint graph is based on the intuition that we don't want two paths for packets to intersect because we want to show that the congestion is 1 (i.e. that even in the worst case, packet paths don't collide). This is what at least I think is implied from the following OCW notes:

If one looks at page 3 of the notes it says:

  Color (i.e., label) the vertices of your graph red and blue so that
  adjacent vertices get different colors. Why must this be possible,
  regardless of the permutation π?

I understand it maybe for this small example, but why would the above be true in general?

I guess I didn't really understand why every constraint graph had to be bipartite or why it had to be 2 colorable.

For example, how do I know that as I form the constraint graph, that I will not have a some clique of size 3 or more? If this were the case it would be bad, because I would for sure need 3 colors at least!

I did notice that when we form the constraints, we form them by first considering a matching of the output packets that might collide and another set of constraint about packets that might collide when arriving to the destination. This two constraints adds two matching to the graph. Maybe the union of matchings forms bipartite graphs?


texts: Efficient algorithm for retrieving the transitive closure of a directed acyclic graph

texts: I'm trying to solve a graph problem (it's not for homework, just to practice my skills). A DAG $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an adjacency list, so $A_v$ is a set containing all the connections of $v$. My task is to find which vertices are reachable from each vertex $v\in V$. The solution I use has a complexity of  $O(V^3)$, with transitive closure, but i read that in a blog it can be faster, although it didn't reveal how. Could anyone tell me another way (with better complexity) to solve the transitive closure problem in a DAG?


texts: Verification of extendible hashing proof

texts:
I have to proof this theorem: "An extendible hashing table always contains at least one bucket where only one pointer points to after an element is added". I made this proof, but I'm not completely sure if it's correct.

Note: The expand-operation on an extendible hashing table works by first doubling the pointer array. Then, the $2*i$-th and $2*i + 1$-th pointers should now point to the $i$-th bucket after expansion.

We deliver a proof by induction on the number of operations on a (initially) empty extendible hashing table.

Basis: The extendible hashing table contains 2 buckets with each one pointer that points to them when no operations are performed. The theorem holds.

Induction hypothesis: Suppose the theorem holds for n operations on an (initially) empty extendible hashing table.

Induction step: We are now going to proof that the theorem also holds for n + 1 operations on an initially empty extendible hashing table. Suppose the (n+1)th operation is an addition of a new element to the table. Now there are 2 possible cases:

First case: The element should be added to a bucket that's not full. The element can then simply be added to this bucket, and no changes occur to the hash-table that was created due to n operations. The theorem holds (induction).

Second case: The element should be added to a bucket that's full. When more than one pointer points to this bucket, it can be split up. If there's room in the bucket, than it can be placed and the theorem holds (induction) because none of the buckets where one pointer points to has been changed. When there's still no room in the bucket and it cannot be split up anymore, the pointerarray has to be doubled. Now this filled bucket has 2 pointers pointing to it and needs to be split to be able to add the element to this full bucket. But by splitting it, only one pointer points to the 2 new buckets, prooving the theorem.

QED

I'm not completely sure if this proof is valid. I'm not sure what I should do with the fact that when a bucket has been split (second case in the induction step) and there's still no room. Can I just say that it has to be split again an indeterminate amount of times, or is this not the way to go?


texts:
Is this Correct, the existence of cryptography requires  $UP \cap Co-UP \not\subseteq BPP$?
Or does it require $UP \not\subseteq BPP$?


texts: Is “A -> aAA” convertible to regular grammar?

texts:
I have a simple grammar as below and wonder if it is convertible to regular grammar?
If yes, what is the conversion sequence? If no, how can we prove it?
S -> A
A -> aAA | b | c

In which S is the start symbol; A is non-terminal; a b c are terminals.
Any help or suggestion is appreciated.


texts: Relationship between left identity and associativity

texts:
In an effort to better-grok monads I have reviewed many "Everything you need to know about Monads" tutorials out in the wild, but I feel like my understanding is still coming up a bit short.

While every one of the above faithfully recites the 3 laws of monads: right identity, left identity, and associativity along with their respective signatures (which I understand), the most prevalent deficit is a complete lack of application. That is, in practice, when creating a monadic structure, what are things that you can do wrong that will violate the 3 laws.

This brings us to my question. Given the following monad (TypeScript):

type Func<T, R> = (a: T) => R

export class Mutation<T extends number>
{
    constructor(readonly value: T) {}

    static unit<R extends number>(value: R)
    {
        let inValue = value;

        // the following line breaks right identity
        //inValue = inValue * inValue as R

        return new Mutation<R>(inValue);
    }

    flatMap(f: Func<T, Mutation<T>>): Mutation<T>
    {
        let inValue = this.value

        // the following line breaks left identity (but not associativity)
        //inValue = inValue * inValue as T

        let m = f(inValue)

        let outValue = m.value;

        // the following line breaks associativity (AND left identity)
        //outValue = outValue * outValue as T

        return new Mutation<T>(outValue)
    }
}

Embedded into the above monad are lines that can be un-commented to break the rules. Each of these lines is located in one of the 3 "regions" where "state" could be modified (thereby breaking the rules):

In the unit constructor
In flatMap before the function f is applied
In flatMap after the function f is applied

Now we can write a short script to verify each of the laws as follows:

let m = Mutation.unit(2 as number);

let f = (x: number) => Mutation.unit(x * x);

let g = (x: number) => Mutation.unit(x * x);

// assert that the creation of a new monad does not alter the value
let right = Mutation.unit(m.value).value === m.value

// assert that `flatMap` does not alter the wrapped value before or after it is passed to `f`
let left = f(m.value).value === m.flatMap(f).value

// assert that `flatMap` does not alter the wrapped value after it is passed to `f`
let assoc = m.flatMap(f).flatMap(g).value === m.flatMap((x) => f(x).flatMap(g)).value

console.log({right, left, assoc});

Here's my problem: I am able to produce results that look like:

{right: ..., left: false, assoc: true} // this is possible
{right: ..., left: false, assoc: false} // this is possible

but unable to produce a result like:

{right: ..., left: true, assoc: false} // this is not possible

That is, I cannot find a way to break the law of associativity that does not also break left identity. Said another way, my findings above indicate that it is possible to break left identity and preserve associativity, but not the other way around.

This leads me to conclude that associativity implies left identity and therefore the law of left identity is redundant. Clearly, this cannot be true or every tutorial/wiki is imprecise (which I find hard to believe).

How can I modify the monad above such that it breaks the law of associativity without also breaking the law of left identity?

To be clear, I believe I understand monads (as the abstraction of a strategy for combining computations). My question is really focused on the relationship between the laws of associativity and left identity. I would like to be shown that they are, in fact, independent. Specifically through modifying my example above if possible. But hey, if I'm misunderstanding some critical property I am also open to being corrected!


texts: Sharp concentration for selection via random partitioning?

texts:
The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is:

Sample $n^{3/4}$ elements from $A$ with replacement into $B$
Sort $B$ and find the rank $|B|\pm \sqrt{n}$ elements $l$ and $r$ of $B$
Check that $l$ and $r$ are on opposite sides of the median of $A$ and that there are at most $C\sqrt{n}$ elements in $A$ between $l$ and $r$ for some appropriate constant $C > 0$.  Fail if this doesn't happen.
Otherwise, find the median by sorting the elements of $A$ between $l$ and $r$

It's not hard to see that this runs in linear time and that it succeeds with high probability. (All the bad events are large deviations away from the expectation of a binomial.)

An alternate algorithm for the same problem, which is more natural to teach to students who have seen quick sort is the one described here: Randomized Selection

It is also easy to see that this one has linear expected running time: say that a "round" is a sequence of recursive calls that ends when one gives a 1/4-3/4 split, and then observe that the expected length of a round is at most 2.  (In the first draw of a round, the probability of getting a good split is 1/2 and then after actually increases, as the algorithm was described so round length is dominated by a  geometric random variable.)

So now the question:

  Is it possible to show that randomized selection runs in linear time with high probability?

We have $O(\log n)$ rounds, and each round has length at least $k$ with probability at most $2^{-k+1}$, so a union bound gives that the running time is $O(n\log\log n)$ with probability $1-1/O(\log n)$.

This is kind of unsatisfying, but is it actually the truth?


texts: Minimizing total distance to a point from a set of points

texts:
I've read about a problem:

  There are $n$ houses that are placed randomly. Place a parking lot so that the (straight-line) distance to all houses is minimal.

I've written a Monte-Carlo algorithm, but that can't be the optimal approach.

Is there a solution other than approximating the position with Monte-Carlo method? Especially by using a graph or is that a wrong approach?

Is there a way to calculate the optimal position?

What is the name of this problem?


texts:
Let's say we are given this table of the relation Person(name, hobby)

name   hobby
bob    hockey
alice  basketball
mary   cricket
mark   basketball
rick   snowboarding
andy   hockey

How would I use relational algebra to find the hobby that had only one person had.

It should give me

hobby
cricket
snowboarding

My ATTEMPT:

$R1 := \rho_{P2}(Person)$

$R2 := R1 \bowtie_{P2.hobby = P1.hobby \text{ } AND \text{ } P2.name <> P1.name} R2$

$R3 := \pi_{hobby} (R2)$


texts:
In a certain robotics application, I encountered a problem in which we need to determine the order of positions of several robots on $\mathbb{R}$. Each measurement that we take of robot positions is subject to random errors beyond our control. I've formalised the algorithmic part of the problem as follows. This part has been reformulated as per D.W.'s comments.

The positions of $n$ robots are given to us in a $3\times n$ array, each row being of the form $[i, A, \epsilon]$.This row states   that the position of the robot with id $i$ is uniformly distributed on the interval $A \pm \epsilon$.

Problem : Output the most probable ordering (MPO) of the robot positions,
or one such if this is non-unique.

Example Input:
$\begin{bmatrix} \mathrm{id} & A & \epsilon \\ \hline  1 & 1& 0.5 \\ 2& 1.5 & 2 \end{bmatrix}$.

Associate the two robot positions with random variables $X_1$ and $X_2$. Note that the pair $(X_1,X_2)$ is uniform on the rectangle $[0.5,1.5] \times [-0.5,3.5]$.  The probability $p_1$ (resp. $p_2$) that $X_1\leq X_2$ (resp. $X_1 \geq X_2$) is the area of this rectangle below (resp. above) the line $x_1\leq x_2$. If $p_1 \leq p_2$, then the MPO is $[1,2]$ , else $[2,1]$.

  What data structure efficiently computes the MPO?

I'm most interested in the range $n\in [10,1000]$.

Simple idea that doesn't work (thanks to D.W.): When $n\geq 3$, the MPO isn't equal to the sorted order of the means $A_i$. For example, the input $(1, 0.4\pm0), (2,0.5\pm 0.5), (3,0.7 \pm 0)$ has the MPO $[2,1,3]$ and not $[1,2,3]$ as the $A$'s would have us think.

One possible approach uses the Sweep Line algorithm. Think of a robot position as a rectangle corresponding to its uniform pdf. Compute all intersecting rectangles using the Priority Queue of the sweep line, and reorder them as per the probability calculation above. (It may be possible to reduce the $O(n^2)$ pairwise comparison of probabilities to $O(n \log n)$; I haven't checked this though.) Non-overlapping rectangles leave their ordering intact.

Intuitively, large error bounds lead to long rectangles and potentially more overlaps, consequently increasing the running time. Likewise, small error bounds cause few overlaps, speeding up computations. This fact will be reflected in the sweep line.


texts: Proving that no finite automaton can recognize a Dyck language

texts:
I was reading up on finite automata and I came across an interesting fact near the end of the Wikipedia page.

  The classic example of a simply described language that no DFA can
  recognize is bracket or Dyck language, i.e., the language that
  consists of properly paired brackets such as word "(()())".
  Intuitively, no DFA can recognize the Dyck language because DFAs are
  not capable of counting: [...]

Although it is very intuitive the argument they gave, I was wondering if there were a formal proof I could read for this, or if simple enough, reconstruct.

I tried Googling around for a proof, but I think I am missing some sort of a keyword in my search because nothing useful is coming up, it this proof trivial or intuitive enough that no papers have been published on it?


texts:
I know that MAX2SAT is NP-complete in general but I'm wondering about if certain restricted cases are known to be in P. Certainly the languages
$L_k:=\{ \phi \,|\, \phi\,\text{is an instance of 2SAT which has an assignment satisfying at least k clauses.}\}$
can be solved in $O(n^k)$ through brute force search since for each language $k$ is fixed. However, I'm wondering about the case when a fraction of the clauses is specified. Does any fraction yield an NP-hard problem? Specifically I'm wondering about the case of satisfying at least half of the clauses of a 2SAT instance.
The reduction I saw from 3SAT to MAX2SAT constructs 10 clauses from each clause in 3SAT such that out of these ten, exactly 7 are satisfied when the original 3SAT clause is satisfied and at most 6 are satisfied when the original clause is not satisfied. So in this reduction the fraction of $7/10$ works but $1/2$ does not because unsatisfying truth assignments of a 3SAT instance can still yield an instance of 2SAT that has an assignment satisfying more than half of the clauses. I thought about another construction or adding extra clauses to an instance of 2SAT but I've been unsuccessful so far.


texts:
Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same.

I have ideas on how i would do this with a context-free grammar but i don't know how to so this under the restriction of a regular grammar.


texts:
Given two positive integers $c_1$ and $c_2$ such that $c_1 < c_2$, it's easy to prove that $n^{c_1}$ is $\mathcal{O}(n^{c_2})$ while $n^{c_2}$ is not $\mathcal{O}(n^{c_1})$. In general, for any functions $f(n)$ and $g(n)$ it is possible to determine which one (or both) is true, $f \in \mathcal{O}(g)$ or $g \in \mathcal{O}(f)$ using only definition of big-O notation. Thus it is not hard to see that TIME($n^{c_1}) \subsetneq$ TIME($n^{c_2})$ without using the Time Hierarchy theorem.

So, what is the meaning of the Time Hierarchy theorem and how and where can I use it?


texts: Definition of Disjointness for binary strings

texts:
Basically, most of the definition for disjointness are such that $DISJ(A, B) = 1$ if $A \cap B = \emptyset $ and $DISJ(A, B) = 0$ for other case. My confusion is how is $0$'s influence in here. For example, is all-zeros string considered as $\emptyset$ and therefore the result will be $1$ no matter what the other string is ? Another case is if two disjoint string, e.g., $01$ and $10$ becomes not disjoint after same number of $0$ appended to each string.
Currently my thought is, based on most research papers in communication complexity field, that $DISJ(A, B) = 0$ iff there exists one entry is $1$ for both $A, B$. Would like some clarification and related detailed definition with source.


texts: Enumerate all valid orders of subset sums

texts:
Given an positive integer $n$, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of $\{1,\ldots,n\}$. For example, when $n=2$, the sequence $\emptyset,\{1\},\{2\},\{1,2\}$ is an order.

We call an order $S_1,\ldots,S_{2^n}$ valid if there exist real numbers $0<x_1<\cdots<x_n$ such that $\sum_{i\in S_1}x_i<\cdots<\sum_{i\in S_{2^n}}x_i$. For example, when $n=2$, the sequence $\emptyset,\{1\},\{2\},\{1,2\}$ is a valid order, but the sequence $\emptyset,\{1\},\{1,2\},\{2\}$ is not because we cannot make $x_1+x_2<x_2$.

The question is, given $n$, how to enumerate all possible valid orders. To output an order $S_1,\ldots,S_{2^n}$, it is sufficient to output an algorithm that generates this order, i.e., an algorithm with no input (the parameter $n$ is built-in) that outputs $S_1,\ldots,S_{2^n}$ in order, as long as the algorithm runs in $O(n2^n)$ time. Even so, this problem still cannot be solved in time polynomial in $n$, because there may be exponentially many valid orders, thus an algorithm running in exponential time is welcome.

A trivial algorithm would be to iterate over all possible orders, and check for each one if it is valid. But I cannot even find an (efficient) way to check if an order is valid.


texts: Why does the program counter increment before an instruction is completed?

texts:
During the fetch, decode, execute cycle, the Program Counter (PC) increments after the operand is copied from the Memory Data Register (MDR), and then carries on with the processing of the instruction.

Why does the PC increment in the middle of the cycle rather than at the end?

My only guess would be that it relates to jump instructions being incremented but I cannot find any sources on this.


texts: How to find the matched SIFT features that are spatially consistent?

texts:
I have extracted DenseSIFT from the query and database image and quantized by kmeans. The challenge is to find those SIFT features that quantized to the same visual words and be spatially consistent (have a similar position to object centers). I have tried few techniques:

using FLANN() on the SIFT (normal SIFT) coordinates on both query and database image and find the nearest neighbor and then comparing the visual words (NOTE: this gave few points that did not work).
Using Coherent-Point-Drift (CPD) on SIFT coordinates to find the matched points (I am not sure about this whether it is a right solution or not).

I am struggling with it for many days, and I hope experts can guide me with this. What are the possible solutions or algorithms that I can use for solving this?


texts: Selecting items from two arrays without duplicate indices to get maximum sum

texts:
Given two arrays both of length n, you have to choose exactly k values from the array 1 and n-k values from the other array, such that the sum of these values is maximum, with constraint that if you choose a value from some index of any of the array you cannot choose from same index of second array.

I have encountered this type of question in many places but never able to solve it, and I always have an Intuition that this is a dynamic programming problem but never able to prove it. I do not quite understand If there exist a dynamic solution or not?


texts: What is the best algorithm for detecting the texture of a person's clothes in real-time for a mobile robot?

texts: I am working on the human following robot. the robot extracts a feature of clothes's texture and distinguishes between the people that they stand up in front of the robot. So, the robot needs that it will be robust and fast.


texts: Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages?

texts:
Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations.

Is there an alternative proof that goes on to show that regular languages are also closed under concatenation using DFAs?


texts: Ontology Editor or Something Else (in my case)?

texts:
Does there exist a system, e.g., software, an environment, a programming language, or the like, to represent knowledge and to reason with it, to query with, where the (descriptive) language used is at least predicate logic with modal operators, using standard logical symbols (⊃, ≡, ◇, ∧, etc.)? It has to follow the rules and practices of standard logic that have already been established. It must also have the capacity to quickly spit out a desktop application that can be used to query the knowledge database easily.

My interest at this point is especially experimental and personal. I have not yet come across anything in the software world that is what I seek.

What I have come across so far, are for example:

Prolog. I have used it before (some years ago) and I find its syntax (with symbols unlike what I seek) not suitable (and ugly) and, as far as I know, there are no modality operators.
Other logic-based programming languages. Most of them seem to imitate Prolog or are not in use or maintained, or lack what I seek, and so on.
Multi-paradigm programming languages including logic-based paradigm. Seems to be overkill for me, for I have no need of such a full-blown programming language. Even if I were to only use the parts for my purposes, then it still does not look as though it is a match to me: they do not use standard logical symbols, for example.
OWL and the like. This seems to be closer to what I seek, but it seems as though it is fairly new or not much used (at least relatively). (This might not be a problem.) It seems difficult to make choices in this case, as it seems that in my quest I have not simple direct answers. In this case I also have found applications such as Fluent Editor and Protégé. I would appreciate any relevant knowledge on this, their strengths and weaknesses, a comparison, and so on. Can they be used totally offline? And is OWL2 (or whatever usable syntax (Manchester, etc.)), e.g, sufficiently expressive to represent any knowledge a human might think of using, e.g, predicate and modal logic and even extra operators for greater expression? From what it looks like so far, the whole thing uses some descriptive logical language in-between propositional logic and predicate logic (so it is not standard in the sense that I mean). Furthermore, Fluent Editor seems to use a kind of subset of English as their language, which is perhaps nice, though I still prefer something that looks more like what I described earlier.

And is there some system where one could even assign one's own operators to replace the default ones?

So far only Fluent Editor and Protégé with some sort of OWL nature seem to be the best candidates. Can they be used offline and can they compile desktop query applications?

You can understand that I am in this quest not satisfied. It has been a search without sufficient result, and so somewhat frustrating. Is my quest in vain? Must I create the system I seek myself?


texts: Morse code is a ternary human-optimised code, is there a binary, non-machine optimised code?

texts:
Is Morse code without spaces uniquely decipherable?

Discusses how Morse code isn't very clear without the third (usually)
unseen element, the space.

Is there a (historical?) human-optimised (vs. say, ascii or something)
binary (on vs. off) code for transmitting information?

After sleeping on it, I recall one code used by Vietnam-era POWs, based on
a 5x5 grid reference, optimised for decoding/learning (alphabetical order)
vs. optimised for use. But, I'm not sure that it didn't also use spaces.

From history/pre-computer: ie: I don't really want to hear ASCII, or
machine language - very few people (excludng Seymour Cray) can do that in
their head.

Human-optimized: something that's designed around human/language foibles,
ie: Morse is intended to have the fewest keys for the most used
characters.

History has decided this is not a history question:

https://history.stackexchange.com/questions/17531/morse-code-is-a-ternary-human-optimised-code-is-there-a-binary-non-machine-opt

Suggestions:

T.E.D. suggests smoke signals, but uses an example in which both the
question, and the answers are pre-known:

There's the smoke signal that the Vatican Council uses to communicate when
they are voting. Black smoke means they haven't elected a new Pope yet,
and white smoke means they have. I'd imagine a lot of other smoke signal
systems can be thought of a binary communications as well, as the medium
has many similarities to telegraph.

However, smoke signals in general sound intriguing.  Does anyone have any
references?  Wikipedia mentions "Polybius square" which was the basis for
the POW communication mentioned above.  Knock or tap codes are another
name for them.

Thanks T.E.D. for indirectly pointing me to a place (Thanks Wikipedia) to find the name(s) for one answer to the question.

March Ho suggests:

http://en.wikipedia.org/wiki/Braille , in its various language formats, is
a binary human-optimised code. http://en.wikipedia.org/wiki/Night_writing
, Braille's precursor, also fits your description request. Both codes are
fixed-length, and therefore do not suffer from the problem as quoted in
the question.


texts: How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method

texts:
The guess solution to the

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

is $\Theta(n \log{\log n})$. This is my solution:
$$
T(n) \leq 2c\left(\frac{n}{2}\right) \log{\log {\frac{n}{2}}} + \frac{n}{\log n} \\
\leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\
\leq cn \log{\log {n}} + \frac{n}{\log n}
$$

that fails to for the $T(n) \leq cn \log{\log {n}}$

Now I try to solve the $T(n) \leq c(\log \log n - \frac{n}{\log n})$, we have
$$
T(n) \leq 2c\left(\left(\frac{n}{2}\right) \log \log {\frac{n}{2}} - \frac{\frac{n}{2}}{\log {\frac{n}{2}}}\right) + \frac{n}{\log n}\\
\leq cn \log \log {\frac{n}{2}} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\
\leq cn \log \log {n} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\
$$
and it will never be $\leq cn \log \log {n} - \dfrac{n}{\log n}$

How can I solve the recurrence?


texts: What is the difference between the semantic and syntactic views of function types?

texts:
Edit: My original question referred to nonconstructive and constructive definitions of function types.  I changed the terminology in the question and the title to semantic and syntactic, which the answer indicates is the correct terminology for this distinction.

I can recall two ways of defining functions in set theory and programming languages with set-theoretic foundations.  The function type $\tau \to \sigma$ can be defined semantically as the set of all maps from $\tau$ to $\sigma \cup \{\bot\}$, i.e., all objects $f$ such that if $x \in \tau$ then $f(x) \in \sigma \cup \{\bot\}$.  Alternatively, the function type $\tau \to \sigma$ can be defined syntactically as the set of all terms in a given language whose type is $\tau \to \sigma$ (possibly modulo some equivalence relationship).  As a programmer, I work with the latter definition, but I often pretend that I'm working with the former definition.

What are the differences between the inhabitants of $\tau \to \sigma$ according to the two definitions above?  For instance, are uncomputable functions included in the first but not the second definition?

To be precise, I'm interested in the situation where terms are strongly typed, functions are side effect free and may be nonterminating, and functions are equal iff, for all inputs, they both diverge or both return the same value.


texts: Which model to apply on such panel data with so may rows but for each unique id rows are 6-8 rows per unique id?

texts:
I am new to such panel data where I have multiple observation for same ID in different Quarter and I am not sure what kind of machine learning algorithm I can apply.
I have data from Q1-18 till Q4-2020
I have 2,000,000 rows and 200,000 unique id and 20 columns
For each id I have only 6-8 past quarter values, max quarter for each id are 8 quarters and for some id I have only 6 quarters where few quarter value are not available for that id
Below is the basic idea of what my data set look like
Quarter - respective business quarter for that year
Target - is the sales volume in ratio
I am trying to Predict - Target column for 2021 Q1 quarter
I have 8-10 different numeric columns and state , quarter and ID as category columns
I would appreciate if someone could suggest me what kind of modelling could be performed


texts: How to efficiently search a list of data structures with filtering support

texts:
I'm working on a project where I need to create search functionality that can efficiently search a list of data structures like:
json1 = [
  {
    "name": "bob",
    "age": 55,
    "active": false,
    "location": {
      "state": "FF",
      "country": "NZ"
    }
  {,
  {
    "name": "susan",
    "age": 30,
    "active": true,
    "location": {
      "state": "BB",
      "country": "USA"
    }
  {
]
json2 = [...]

The user would in put something like categories: [json1, json2], fields: [name, location], search_term: "bob"
It needs to support complex queries. I've looked at inverted indexing used in search engines but all the implementations I see are for text searching, not searching data structures and they don't appear to be suitable for filtering based on a data structure field etc. I have the following requirements:

Needs to be able to search based on a field (ie name/age/active)
It very likely will need to support searching like search value > 40 IN json1 FIELD age
Needs to support nested structures like location

Are there any data structures more suitable than an inverted index? If inverted indexing is the way to go can you please provide guidance on how the structure should look in order to support my requirements? Any general reading suggestions on the matter would also be great.


texts: What learning algorithm is appropriate for predicting one time-series from another?

texts:
I have eye-tracking data on two subjects -- a teacher, and a student. It's in the form (x, y, time), so there is a series of these for each subject. What the teacher looks at influences what the student looks at. What method would I use to predict what the student is looking at, using only teacher data? Lets say I can train some learning algorithm using a gold standard set of student and teacher data.

I was thinking hidden markov model would be appropriate, given the definition in Wikipedia, but I am not sure how to put this into practice over my dataset.

More detail: I have data about how a teacher and student each look at a map and some readings. I have 40 of these datasets, which look like [(366,234,0), (386,234,5), ...] which means the teacher looked at point (366,234) at time 0 and then 5 seconds later moved up to look at coordinate (386, 234). I can to learn a model to understand the relationship between how a teacher looks at content, to predict how a student will look at the same content. So maybe the student looks at the content in the same order as the teacher but slower. Or perhaps the student doesn't look around as much but the teacher scans more of the content. I have both sets of data and want to see how accurate of a model I can get -- would I be able to predict the student's looking behavior within 50px of the teacher's looking behavior?


texts: $O(n^{k-1}$) algorithm for K-clique problem

texts:
Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is constant). I'm interested in the best known upper bounds when k is constant.

  Is there an algorithm with run time $O(n^{k-1})$? A $o(n^k)$-time algorithm is also acceptable. Also, Is there any complexity-theoretic consequence for the existence of such algorithms?


texts: Determine if a graph has exactly 1 cycle using a SAT solver

texts:
I have a connected undirected graph whose edges are either enabled or disabled. I want to create a set of clauses that are SAT iff all enabled edges are part of a single loop.

If I assert that each vertex has either 0 or 2 enabled edges, then graphs where all enabled edges are part of a single loop will satisfy the clauses. However, graphs with multiple disjoint loops can will also satisfy those clauses. How can I make sure that only 1 loop graphs satisfy the clauses?


texts: Given a set of (x,y) coordinates, give the set of edges to draw a simple polygon

texts:
Let's say I give you the following array of points:

(1,1) (1,3), (2,2), (4,1), (4,3)

My (terrible) mspaint drawing of the shape that would be created by these looks like this:

How, given an arbitrary set of coordinates, can I define the edges which constitute a shape with no overlapping edges?


texts: Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)

texts:
What i mean is that can we code each CFL ( the same way we code each turing machine in the Universal Turing Machine ) and build a Linear bounded Automata in such a way that for each input ( which is a code of a particular CFL) decides whether this is a context free language ( accept ) or not?

I hope my question makes sense or maybe I'm confused, because i know that set of all regular expressions(regular languages) is a Context sensitive language because we can make a context sensitive grammar for it so i was wondering what can we say about the set of all context free languages?


texts: When does the IEEE-754 64-bit float break as a counter

texts:
As a matter of curiosity I've been trying to determine at what point a 64-bit float no longer reflects the addition of 1 as expected; that is, at what point the digits as printed do not correspond to the digits of a 64-bit integer that is incremented in sync.

Around 1e15 I can continually add 1 or subtract 1 and the result seems right. At 1e16 the addition or subtraction of 1 has no effect on the value as printed. However, 1e16 - 2 gives 9.999999999999998e+15 (at least, as printed by go's fmt package).

I wonder whether there are discontinuities in the sequence of sums of n+=1 while n < 1e15. At what point does n+=1 no longer produce a result corresponding to the expected integer?


texts: How to do high performance string matching when comparing unordered sets of tokens

texts:
This is the problem:

I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one time in a string).

I want to know if a new string matches any of them without taking token order into account.

The metric I think about is something like this (comparing two strings at the time, this is the first thing that came to my mind when trying to solve the problem and don't know if it is already used), a matching percentage calculated like this:

Match_Metric(A, B) = number_of_matched_tokens(A, B) / max_number_of_tokens_in_any_of_two_strings(A,B) * 100.

Example:

String 1: "abc, cde, ghi, adc, dca, aab"

String 2: "cd, r, a, x"
String 3: "aab, cde, ghi, abc, adc, dca"
String 4: "aab, cde, ghi, abc, adc, dca, rrrm, a"

1 vs 2 = 0%
1 vs 3 = 100%
1 vs 4 = 75%

What I am trying to avoid is to perform a one to one comparison between tokens, but I am finding that other techniques like edit distance won't give me an exact match in the case of 1 vs 3 unless I first order the tokens.

The problem can be extended to do a string search within the tokens, for example:

String 1: "abc, cde, ghi, adc, dca, aab"

String 2: "cd, r, a, x"

As "d" appears in one token in 2 and three tokens in 1, that can affect the metric. In this case an approximate string matching technique such as "edit distance" would be useful but in a token versus token approach. The formula would be more complicated in this case, instead of having an integer representing the number of matched tokens it would be a fraction number and could be calculated like this:

Comparing two tokens at the time one from the string A and one from the string B:

token_match(a,b) = 1 - edit_distance(a,b) / length_of_largest_token(a,b)

So the general metric would be:

String A = {a0, ..., an}
String B = {b0, ..., bm}

i = {0, ..., n}
j = {0, ..., m}

Match_Metric(A, B) = sum(token_match(ai, bj)) / max_number_of_tokens_in_any_of_two_strings(A,B) * 100

Any ideas on what technique/algorithm is more broadly adopted/used for this problem?


texts: Equivalence of Büchi automata and linear $\mu$-calculus

texts:
It's a known fact that every LTL formula can be expressed by a Büchi $\omega$-automaton. But, apparently, Büchi automata are a more powerful, expressive model. I've heard somewhere that Büchi automata are equivalent to linear-time $\mu$-calculus (that is, $\mu$-calculus with usual fixpoints and only one temporal operator: $\mathbf{X}$).

Is there an algorithm (constructive proof) of this equality?


texts: Hash size: Are prime numbers "near" powers of two a poor choice for the modulus?

texts:
Cormen et al.'s "Introduction to Algorithms" says the following about the division method hash function $h(k)=k \text{ mod } m$:

  A prime not too close to an exact power of 2 is often a good choice for $m$. For example, suppose we wish to allocate a hash table, with collisions resolved by chaining, to hold roughly $n=2000$ character strings, where a character has 8 bits. We don't mind examining an average of 3 elements in an unsuccesful search, so we allocate a table of size $m=701$. The number $701$ is chose because it is a prime near $2000/3$ but not near any power of 2.

The book, however, does not explain what it means by "near". Is $701$ preferrable over, say, $661$ because $661-512<701-512$? I do not understand how this is relevant to the modulo function involved in the calculation of $h(k)$.


texts:
I have this algorithm taken out from the Manual of Algorithms Analysis:

function pesky (n)
r:=0
for i:=1 to n do
  for j:=1 to i do
    for k:= j to i + j do
      r := r + 1
return (r)

I understand the time complexity of this algorithm for any given input size n > 0 will be O(n^3) since the 3 for loops will always be executed and the inner loop carries out the sum operation n x n x n times (this is of course not exact, but I say it in asymptotic terms taking out constants and lower degree terms of n); however, during a lecture we were asked to express the complexity of the worst-case in terms of n instead of in big oh notation (they left this exercise for next session).

The worst case I can think about for this algorithm would a really large integer as input n which in fact could be so large that it approaches infinity (since no restrictions for the input were stated). Even in this worst case we know time complexity would behave in O(n^3), but how would I express this "in terms of n", the best thing I could come up with is this:

But I feel like I'm just making that up and that there might be another more correct way to express it. Does anyone know the correct way to express worst-case complexity in terms of n?

EDIT: I must make it clear that I found the equation that puts n in function to the r output by means of summation resolving, however I did not consider that function as the time complexity function (and hence not the answer for "worst-case in terms of n") since that function describes output on a given input and not the time it takes to run the algorithm itself.

Moreover I had the idea to try to calculate the complexity counting each operation and I got something like this.

I am not sure if thats correct, if it is I could use that expression to state the worst-case complexity in terms of n, and also I could make my initial statement about big oh notation for the worst case more precise since this would be O(n).


texts: Is (λx.FV(A)) and (λx.FV(B)) β-equivalent?

texts:
Does free variables have some meaning in lambda calculus? If I follow this β-reduction
(λx.λz.y x) y
    -> (λz.y x){x/y}        (variable FV(y) captured)
    -> ((λz.y x){a/y}){x/y} (rename FV(y) -> FV(a)){
    -> (λz.a x){x/y}
    -> (λz.a y)

Here we have FV(y) captured during the β-reduction, so I rename it to FV(a) and continue the reduction. Is this result even valid?
I would rename the y argument instead
(λx.λz.y x) y
    -> (λz.y x){x/y}        (variable FV(y) captured)
    -> (λz.y x)({x/y}{y/a}) (rename argument FV(y) -> FV(a)
    -> (λz.y x){x/a}
    -> (λz.y a)

If I use De Bruijin index notation for both outputs I would get:
(λz.a y) -> (λ.1 2)
(λz.y a) -> (λ.1 2)

so they seem β-equivalent for me.
This means that FV has no meaning at all, FV(a) β= FV(b) β= FV(c) ...  is my understanding right?
I'm asking because when applying lambda calculus I would like to have some global variables that are not bound by the expression but are bound by the context, things like *, +, sqrt, etc, in this case I cant just replace free variables because they may have a meaning, what would I do so?

Thanks @lemontree for your answer, I'm implementing a lambda calcualtor so I need to take care of every single step. I write things in the math notation (λx.x) y and then translate to the expected code Appl(Lamb('x', 'x'), 'y'), M[x/y] m.replace('x', 'y'), so having a notation for every step help me a lot :).
I search but can't find any special notation for ɑ-conversion so I came up with M[BV(x)/y] to denote that x is not free in M and to make it distinct from M[x/y]. And a special function NX that returns the next available variables. Here is how I reduced your example (thank you!)
    (λx.λy.y x) y
        -> (λy.y x)[y/x]
        -> (λy.y[y/x] x[y/x])               CAPTURE ERROR on y (backtrack)
        -> (λy.y x)[BV(y)/NX(x, y)][y/x]    NX(FV ∪ BV) returns the next available variable
        -> (λy.y x)[BV(y)/z][y/x]
        -> (λz.z x)[y/x]
        -> (λz.z[y/x] x[y/x])
        -> (λz.z y)

The bits that I missed

A definition of available variables not (FV ∪ BV). I need this to implement ɑ-conversion
A formal notation for ɑ-conversion

Is there anything like this in the literature? Thanks in advance :)


texts: Decidability for $ \exists w´, w´´\in L:$ so that |w´´| - |w´| is prime

texts:
I tried to decide wheter the given Language $ L = \{ \langle M \rangle  | M \space is \space TM \space and \space \exists \space w´,w´´\in L(M):|w´´|-|w´| \space is \space prime \}  $ is recursive or recursive enumerable.
I tried to prove not recursive (undecidability) through Rice's theorem, since there exists $M_1, M_2$ so that $L(M_1) = \{ a, aaaa \}$ and $L(M_2) = \{ a \}$ and $L(M_1) \in S \space and \space L(M_2) \notin S$
So then for recursive enumerable (semi-decidability) I tried to show through constructing a TM. Given a computable sequence of $w_1, w_2,... \in \Sigma^*$ I would run the first i words on M for i steps, i+1 words for i+1 steps and so on and every word which is in the Language, I would put it on a different tape and with every word which comes to the tape I would try on another tape for every pair $(i, j) \in \mathbb{N}$ wheter $|w_i|-|w_j|$ is prime. So if w´ and w´´ exist I would find them in finite time.
Do you think that this might work for the proof? Any thoughts or improved solutions on this one?


texts: Does the the undecidability of the Halting Problem eliminate the possibility of 'Hard AI'?

texts:
I'm defining 'Hard AI' as a human-equivalent intelligent machine, or beyond that. Contrast with 'Soft AI' the type of software that runs on your email filter for example.

I've been chewing on this problem for a little while now, and would like some feedback on my logic. This is the only place I could think to put it, so please feel free to move/remove if this is not appropriate.

My argument hinges on the definition of 'human-equivalent intelligence' as 'capable of solving any given instance of the Halting Problem'. This is something no machine can ever do - while they may be able to solve for sub-sets of the Halting Problem, they can never accept an arbitrary instance of it (ie, specific inputs I for a specific program P) and produce an answer.

Humans, however, do this all the time! The entire profession of programming revolves around fixing incarnations of the Halting Problem that pop up in one's own codebase. There are problem-tracking instances full of real-world examples of the Halting Problem - "Subsystem Z stops responding after receiving A with B options", etc. These examples are fixed by humans, and the problem goes away. Sometimes instructions are written for the machine to verify that the problem hasn't returned, taking advantage of the recognizability of solutions to the Halting Problem.

Since any 'Hard AI' would need to be just as capable as humans in any intellectual pursuit, and we KNOW that a machine that solves the Halting Problem cannot exist, we must conclude that there can never be human-intelligent machines.


texts: Optimizing for maximum intervals given a distance bound

texts:
Given an interval set $X = \{(s_1, e_1), \dotsc, (s_N, e_N)\}$ ordered such that $s_i \leq s_j$ and $e_i \leq e_j$ for all $i < j$ and an integer $b$, I would like to find a maximum sized subset $X' \subseteq X$ such that $\text{end}(X') - \text{start}(X') \leq b$. Here the $\text{start}, \text{end}$ functions are defined to be the start position of the first interval and the end position of the final interval.

A simple $O(N^2)$ solution would be to set $b' = b + s_i$ and scan all elements to see how many fit within the new bound $b'$. However, given the sorted structure of the problem it seems amenable to a fast solution.

First we can built an interval tree and perform the same set of queries as earlier, but result in an $O(N \log N)$ runtime.

I am curious if this is still suboptimal given that the data already are sorted. Is there a linear time dynamic programming solution?


texts: How to prove Transitive property of Reducibility with a TM?

texts:
How can we prove that $h(x) = g(f(x))$ is a reduction function for $A \leq_m C$,

if $f$ is the reduction function of  $A \leq_m B$ and $g$ is the reduction function for  $B \leq_m C$

The given Proposition is: $A \leq_m B, B \leq_m C \Rightarrow A \leq_m C$

I was thinking about using $HALT_{TM}$ for A. So on input $\langle M, w\rangle \in A$ if and only if $\langle M'',w'' \rangle \in  C$

The output of A would be $ \langle M', w' \rangle$ and the output of B would be $\langle M'',w'' \rangle$

If the constructed $M$ rejects the input $x$, then it loops forever, so $C$ is not recursive if $A$ is not recursive

If this isn't sufficient, then what am I missing?


texts:
Suppose there exists a list of unsorted int numbers [91,89,90,90,90,89,91].
I need to maximize the profit by selecting an element, in as many steps as needed, which satisfies the condition that,
when element(i) is chosen, the profit would be value of element(i) multiplied by its frequency/occurrence in list, an extra condition is that element(i), element(i)-1 and element(i)+1 should be removed as well.
So for the given array [91,89,90,90,90,89,91], if I choose 90 and remove it, my profit will be 90*3=270 and my array reduces to [], because I remove (90-1) and (90+1) in the same step.
However, if I had chosen, 89 then profit would be 89*2 and upon removing 89 and 89+1(There is no element corresponding to (89-1)), I am left with [91,91]. In the next step, I remove 91, this results in a total profit of 89*2+91*2. The profit is greater than the one obtained after selecting 90.

Another example is list [3,4,2], suppose I select 3, this means profit is 3*1 and I remove 3, 2 and 4 which results in empty list and profit is 3. Now, I choose 2, this results in removal of 2 and 3, profit will be 2*1. List will be [4]. Next step profit will be 4*1, so total profit will be 2+4=6.

I tried to select max element in array and remove it, but it will not work for list [1,1,1,1,1,1,1,1,1,2]. Here, 1 needs to be selected, instead of 2.
Because selecting 2, would result in a profit of 1 versus selecting 1 which would give 1*9.
What approach would be ideal to solve this? Please provide your opinions.
Thank you


texts:
When computing statistics on a list of data it occurred to me that most of the standard statistic functions, such as mean, min, max can be computed in O(N) time with O(1) space. They can also be computed incrementally, or "online", in O(1) space. That is, if the data were a stream we could compute the statistic without needing to store every previously seen item.

However, for computing the median O(N) space is required. There is no way to compute the median in a "rolling" fashion without maintaining all values in memory.

My question is, do these different classes of functions have a classification to describe them (beyond simply saying O(1) or O(N) space)? If I wanted to find more functions like median that require all elements to be present in memory to compute, what would I search for?


texts: Time complexity of a problem in probabilistic inference on a Bayesian network

texts:
Suppose we have a simple Bayesian network with two rows of nodes:  $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$.  Each node $x_k$ takes a state of either 0 or 1 with equal probability.  Each node $y_k$ takes state 1 with probability $p_{k,0}$ if $x_k$ is state 0 and probability $p_{k,1}$ if $x_k$ is state 1.

We would like to find the probability of the joint event $E$ that both (i) all $y_k$ are 1 and (ii) the total assignment of states on the network has a probability above $\epsilon$.

Is exponential time required to compute the probability of $E$, and if so (or not), how do we prove this?

In case it is helpful, let me give a low-$n$ example:

Suppose $n = 3$.  If we just want to compute the probability of (i), then this is
$$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0}p_{2,0}p_{3,0} + p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,0} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,0}p_{3,1} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$
We can factor the right-hand side so that rather than a sum of $2^3$ terms we just have a product of $3$ factors:
$$\Pr(\forall k: y_k = 1) = 2^{-3}(p_{1,0} + p_{1,1})(p_{2,0} + p_{2,1})(p_{3,0} + p_{3,1}).$$
This reduces our computational time from $O(2^n)$ to $O(n)$ (as shown here for arbitrary $n$).

However, now consider the case that the terms $p_{1,0}p_{2,0}p_{3,0}$, $p_{1,0}p_{2,1}p_{3,0}$, and $p_{1,1}p_{2,0}p_{3,1}$ are quite small -- each less than $\epsilon$ -- and we would like our overall probability to 'ignore' such small terms.  Then we want to compute:
$$\Pr(E) = 2^{-3}(p_{1,0}p_{2,0}p_{3,1} + p_{1,0}p_{2,1}p_{3,1} + p_{1,1}p_{2,0}p_{3,0} + p_{1,1}p_{2,1}p_{3,0} + p_{1,1}p_{2,1}p_{3,1}).$$

Of course, no generalizable factorization seems possible for the right-hand side.  This motivates the above question:  how can we prove (or disprove) that computing $\Pr(E)$ in the case of arbitrary $n$, $p_{k,0}$, $p_{k,1}$, and $\epsilon$ is indeed $\Omega(2^n)$?


texts: Girth of Undirected Graph with Positive Integer Weights

texts:
Let $G = (V, E)$ be an undirected graph without self loops and with edge weights $w: E \to \mathbb{N}$. The girth $g(G)$ of $G$ is defined as the length of the shortest cycle in $G$, i.e.

$g(G) := \min\left\{ n \in \mathbb{N} \mid \exists \text{ cycle }(e_1, e_2, \dots, e_k) \text{ in $G$ satisfying } n = \sum_{i = 1}^k w(e_i) \right\}$.

GOAL. Determine $g(G)$ algorithmically and as efficient as possible in terms of time complexity. Note that it's not necessary to find corresponding cycle, length is sufficient.

I present my thoughts on this problem as following. If the graph is unweight, i.e. $w(v) = 1$ for all $v \in V$, we may start a breadth-first search traversal keeping track of the depth of each vertex. Once we detect an edge which leads to an already visited vertex $v$, a cycle is found. The length of the cycle is the difference of the current depth and the depth of $v$. BFS from each vertex and taking minimum should do the job, time complexity is $\mathcal{O}(|V| \times (|V| + |E|))$.

How to deal with edge weights? It seems natural to modify Dijkstra, but I do not see how, because the cycle with least edges may be different from the cycle of minimum weight, the shortest cycle. Is there still a way to use Dijkstra in order to solve this problem?

Can we adapt an all-pairs shortest path algorithm? I would appreciate a solution based on Floyd-Warshall, because of it's simplicity (if there is no faster algorithm). One may assume the graph to be dense, i.e. $|E| = \mathcal{O}(|V|^2)$, so the above solution is $\mathcal{O}(|V|^3)$.


texts: Difference between Tail-Recursion and structural recursion

texts: Is there any difference between structural-recursion and Tail-recursion or they both are same? I see that in both of these recursions , the recursive function is called on the subset of the orignal items.


texts: Halting problem for fixed Turing machine and fixed input

texts:
It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.

What if we fixed both the machine and the input? I.e., is it decidable for every fixed Turing machine $M_0$ and every fixed input $w_0$ that $M_0$ will halt on $w_0$ as input?


texts:
While writing array index in an algorithm $a[i]\gets v$ is conventionally used. Is the notation $a_{i}\gets v$ also used ?

If the algorithm uses struct or equivalent, some notation is required for property access. In some occasions $p(s)$ is used where $p$ is the property. Using $s \rightarrow p$ messes up with the assignment arrow. Using $s_{p}$ looks like $p$ is an index and $p\in \mathbb{Z}^{+}$. Should $s["p"]$ be used ? What is the convention to denote property access in algorithm ?

Is there any reference where I can check different notations of these two scenarios ?


texts: what is the name for the space between the leaves of a tree

texts: I am trying to write a data-type not for a tree, but for the spaces in between the leaves of thee tree.  In number theory (a part of math) this is known as a topograph does it have a name in CS?


texts: Asking for your help with LFSR, linear automaton

texts:
I am a software developer new to the site. I am currently learning about LFSR (linear feedback shift register). Every day I solve a question which is given to me, but today I am lost. I can not solve this one, so I am asking for your help, for hints, or for any thoughts.

  TASK:
  Make a linear automaton with the help of LFSR of this recurrent sequence:

  $s_{n+4} = s_{n+3}+s_{n+1}+s_{n} $

  $ f(x)=x^{4}+x^{3}+x+1$

The plus sign stands for XOR I think $\oplus$

I think that's how it starts and I basically need to design a linear automaton with zeros and ones.
Its period is 15? I am thinking of $0^{3}110010101^{4}|0^{3}1\ldots$

How do I construct a linear automaton from here?


texts: Where is the epipole if one camera center is not in view of the other?

texts:
In the book multiple view geometry, the epipole is defined as follows:

  The epipole is the point of intersection of the line joining the
  camera centres (the baseline) with the image plane. Equivalently, the
  epipole is the image in one view of the camera centre of the other
  view. It is also the vanishing point of the baseline (translation)
  direction.

The image of one camera center could easily not be in view of another camera center without the cameras being parallel. So, in this case, the line connecting the camera centers would not intersect at least one of the image planes. So, where is the epipole in this case?


texts: Proof that whether a regular language is finite is decidable

texts:
I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When you generate all strings from length 0 to n, if the machine accepts any of them then the language is non-empty. We don't have to check words with length > n because of the pumping lemma.
The question claims that you can solve the decision problem for finiteness in a similar way.

I know intuitively that a regular language is finite if its finite, well-formed regular expression does not contain a Kleene star, but I don't know how to convert this notion around. My thought is that we have to know if there are any words in the language whose length is greather than n, but that requires checking all words.

Then I thought:
Have the machine count the number of states n in the FSM. Generate all of the strings of length 0 to n. Then, check every word to see if the only possible way to pump this word xyz is to make y≡λ. If every word pumps only according to this condition, then the language is finite. However, this feels somehow incomplete.

Could someone give me a hint or push me in the right direction? Thanks.


texts: Explain auto continue passing style transformations

texts:
Recently I saw 3 cps transformation rules, but no explanations were given.

expressions: $e :=x\left|e e^{\prime}\right| \lambda x \cdot e$

rules:
$$
\begin{array}{l}{[[x]]=\lambda \kappa \cdot \kappa x} \\ {[[\lambda x \cdot M]]=\lambda \kappa \cdot \kappa(\lambda x \cdot[[M]])} \\ {[[M N]]=\lambda \kappa \cdot[[M]](\lambda m \cdot[[N]]](\lambda n \cdot(m n) \kappa)}\end{array}
$$

When transforming fib, fib n = ... is transformed into fib n k = ..., but if we use the second rule, the first param of the transformed function will be k which differs

fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fib_cps 0 k = k 1
fib_cps 1 k = k 1
fib_cps n k = fib_cps (n - 1) (\x -> fib_cps (n - 2) (\y -> k (x + y)))

Could someone please explain it for me?

About the 3rd rule, why we need to transform both fn and arg when transforming function application, and why it's like this?


texts:
I have this question in my homework. Its an a multiple choice question and goes as following:
Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$

** the answers have been checked with the teachers note **

C and K are the constants

$(C,K) = (10,0)$
$(C,K) = (6,1)$
$(C,K) = (9, 1)$
$(C,K) = (12,1)$
$(C,K) = (3,2)$
$(C,K) = (5,2)$

I know that $(10,0)$ is false since $K = 1$.

$(6,1)$ I also know is wrong because it's smaller than the statement.

But  since $3x^3 + 2x^3 + 4x^3 = 9$, then $(9,1)$ is true.

$(12,1)$ is true because I assume its okay that is bigger just not smaller?

$(3,2)$ is false
$(5,2)$ is true.

My question here is :Why is it that $(5,2)$ is true?  And can anyone tell me whether my thinking is correct or not?

Thank you for any kind of help


texts: Amount of classes for a semantic segmentation neural network

texts:
I am currently working on implementation of semantic segmentation of images neural network, and try to implement one of the already existing solution such as Fully Convolutional Neural Network 1.

Data that I am using is based on Pascal-Context dataset [2], which has additional labeling  to original 20-class PASCAL VOC dataset. This results in a dataset with over 450-classes.

Problem

Initial 20-classes do not not match classes that I would like to achieve for indoor scenes. Therefore, I have created a short list of 12-classes that I would like to capture, which are in Pascal Context 450-classes dataset.

I managed to convert the data and now trying to start training. I am following this tutorial [3] on Matlab, which provides an example of an Image with classes overlay and all pixels colored.

However, in my scenario, I only want to be able to distinguish elements such as tvmonitor, sofa, wall and ignoring all other elements, which might be there. Matlab tutorial states: "Areas with no color overlay do not have pixel labels and are not used during training."[

As you can see above, I have two classes present in the picture, but I am not sure whether I should also include class Background, which would put overlay on everything that is not within my list of classes, and include that as an additional class in my training or not.

In summary, I am wondering whether Background needs to be provided as an additional class to my list of the classes that I would like to classify or not, even if this background class usually takes majority of each of images. Would that result in everything being classified as background?

References:

1 https://github.com/shelhamer/fcn.berkeleyvision.org

[2] https://www.cs.stanford.edu/~roozbeh/pascal-context/

[3] https://uk.mathworks.com/help/vision/examples/semantic-segmentation-using-deep-learning.html#d119e321


texts: Did 'Eugene Goostman' really pass the Turing test?

texts:
It is being said that 'Eugene Goostman', a computer programme developed to simulate a 13-year-old boy, managed to convince 33 per cent of the judges that it was human, and thus passed the Turing Test.

The computer programme, aka a chatbot, was pretending to be a 13-year-old Ukranian boy for whom English was a second language – something very different indeed.

For me, Eugene sounds exactly like a mediocre chatbot should: repetitive, nonsensical, and littered with non-sequiturs. I don't know how it convinced the judges (which seem unprofessional).

Many people have criticized Eugene like Prof Stevan Harnad who said "It's nonsense" and "We have not passed the Turing test. We are not even close."

Opinions differ, but I would really like to know if it officially passed the test?

It is also being said that:

  Two one-time-only prizes that have never been
  awarded. 25K is offered for the first chatterbot that judges
  cannot distinguish from a real human and which can convince judges
  that the human is the computer program. $100,000 is the reward for the
  first chatterbot that judges cannot distinguish from a real human in a
  Turing test that includes deciphering and understanding text, visual,
  and auditory input. Once this is achieved, the annual competition will
  end.

Does it mean Eugene won $25,000?


texts: Writing the coherence conditions for a monad in a functional laguage

texts:
i recently asked a related question about the relationship between monads in category theory and Haskell. The answerer showed me the following classes and instances:

class MyMonad t where
  fun :: (a -> b) -> (t a -> t b) -- functorial action, known as fmap
  eta :: a -> t a
  mu :: t (t a) -> t a

class KleisliTriple t where
  ret :: a -> t a
  (>>==) :: t a -> (a -> t b) -> t b

instance KleisliTriple t => MyMonad t where
  fun f m = m >>== (ret . f)
  eta     = ret
  mu m    = m >>== id

instance MyMonad t => KleisliTriple t where
   ret      = eta
   m >>== f = mu (fun f m)

And told me I should show that the rules for each class are equivalent. I've finally gotten around to this exercise but I've already run into some confusion.

I know that the "laws" for a Kleisli Triple are as follows:

return x >>= f  = f x
m >>= return    = m
(m >>= f) >>= g = m >>= (\x -> f x >>= g)

And I know that the coherence conditions for a monad can be written
$$\mu \circ \eta T = \mu \circ T \eta = id_C$$
$$\mu \circ \mu T = \mu \circ T \mu$$
Where $T$ is the endofunctor, fun in the Haskell class.

I know $(\eta T)_x = \eta_{T\, x}$ and $(T\eta)_x=T(\eta_x)$, so I think the rules for MyMonad could be written as follows:

mu . eta . (fun f) = f
mu . (fun eta) = id
mu . mu . (fun id) = mu . (fun mu)

Writing any of these expressions as a function with the desired type signatures loads in GHCI, but I don't think I'm right.

It's mainly associativity that I'm not confident about. Unwrapping associativity for the Kleisli triple yields

mu (fun g (mu (fun f m))) = mu (fun (\x -> mu (fun g (f x))) m)

Which seems  over-complicated, but unlike my attempt to express the category-theoretic constraints, this equation universally quantifies over the functions

f :: a -> m b
g :: b -> m c`

How close am I to coming to the correct conclusion? Hints would be appreciated.


texts: Topological sort, but with some fixed values

texts:
I'm working on a problem similar to topological sorting, but with an additional constraint: I want to order the nodes by assigning a positive integer index to each, and, in additional to the relative constraints the graph defines, some nodes have a predefined index assigned.

That is, the input is a set of nodes $V$, a set of relative constraints each of the form $X_a < X_b; a \in V, b \in V$, and a set of absolute constraints $X_a = i, i \in \mathbb{Z}^+$.

The output is a map $X$ such that $X_a \in \mathbb{Z}^+$ for each $a \in V$, and all relative and absolute constraints specified in the input are satisfied. The values $X_a$ need not be unique; it's acceptable that $X_a = X_b$ given $a \neq b$, so long as all the specified constraints are satisfied. If no such $X$ exists, the output is an error value.

Not sure what to search for; does such an algorithm exist? If not, is there a good way to map this problem to a known problem? I'm working on it, too, but just wanted to see if this set off any lightbulbs for anyone in the community before I go too deep :)

(In case this helps, I'm working on a solver to manage the z-indexes of my web application.)


texts: Is square numbers written in binary a regular language?

texts:
I'm having problem trying to determine if all square numbers (1, 4, 9, 16, ...) written in binary form (1, 100, 1001, ...) is a regular language.

After some attempts to find a common pattern of those numbers, I found out that for any square number $n^2$, $n^2 mod 4$ either equals to 0 or 1, and so I am able to draw a DFA graph with 4 states to recognize this language. But apparently, the DFA I drew actually recognizes a superset of the square number language in question. I'm stuck here.

Anyone could give me some clues on this problem? If it's not a regular language, how should I prove it?

I am also very interested to know how I should approach to this kind of question the best way in the future. I know that in many cases, if we have the intuition that the automata has to keep a track of what is has seen already (like $a^i b^i$), then there's an undetermined states needed for the automata to compute, thus it's not finite or regular. We can then use Pumping lemma to prove it's not regular. However, I can't tell if this language is regular yet, so I don't really have an idea what to do next.

Thanks!


texts: Maximum flow with edge demands: can't understand the example of transition to transformed graph in the lecture notes

texts:
TL;DR:
There're lecture notes about a very simple reduction from "maximum flow with edge demands problem to the maximum flow problem. But I can't get the new capacities at the picture:

E.g., look at the diagonal: 15 - 0 = 14 (?). From my point of view there're a lot of off-by-one errors.


texts: Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language?

texts:
Continuing https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (n-ary Dijkstra choice, U+2AFF) in the context of the Guarded Command Language (GCL) of Dijkstra? In other words, when do you use ⫾ and when ⫿ for typesetting GCL programs?

Related:

http://latex.org/forum/viewtopic.php?t=32939
Barbara's take on GCL


texts: Techniques/tools for constructing hard instances of a puzzle game

texts:
Are there techniques and/or software tools that can be used to
  construct hard instances of a simple puzzle game (or a simple planning
  problem)?

With "hard" I mean that any solution of the instance is "long" with respect to the input size.

What I have in mind:

model the puzzle game using a constraint programming language (or even STRIPS);
the tool starts with assigning some random values to the model parameters to construct an instance;
solve the instance and if solutions are "easy" (shorter than a fixed length) or no solution is found in a specified amount of time, try to adjust it using some heuristics (or other techniques such as GA or simulated annealing).


texts: recurrence - Iteration method T(n)=T(n-a)+n

texts:
I really need help to solve the following: T(n)=T(n-a)+n where a is a constant greather or equal 1.

So I started to iterate
T(n)=T(n-a)+n
    =T(((n-a)+n)-a)+n
    =T(3n-3a)+n
    =T(((3n-3a)+n)-a)+n
    =T(4n-4a)+n

this brings me to the Basic: T(kn-ka)+n.

Is it right ? I am not sure how to solve such Terms with a constant ?
thank you for your help !!


texts: Could quantum computing eventually be used to make modern day hashing trivial to break?

texts:
Simply put, if one were to build a quantum computing device with the power of, say, 20 qubits,  could such a computer be used to make any kind of modern hashing algorithm useless?

Would it even be possible to harness the power of quantum computing in a traditional computing application?


texts: Intuition behind approximation algorithm

texts: If you already have an approximation algorithm in hand, it's usually easier to prove that it is an α-approximation algorithm by merely analyzing the algorithm, than designing an approximation algorithm to achieve a α-approximation. That being said, what procedure or intuition should I have in mind to design a α-approximation algorithm?


texts:
I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph.

In this generalized version, instead of finding a set of edges that would break the graph into two components, it would break it in r components.
The approach used for the 2-way cut-set is to contract edges until only two vertices remain, and treat the edges remaining as the cut-set $C$.

The question then is

  Explain how the randomized min-cut algorithm can be used to find minimum r-way cut-sets, and bound the probability that it succeeds in one iteration.

My idea is to instead of stopping when there are r vertices remaining, instead of 2. But I am unable to bound its success probability.
A possible approach would be to find the probability of contracting an edge $\in C$. To do so, I define $|C|=k$, and based on that, $d(v)\ge k-r+2$, $\forall v \in V$. Thus, $|E|\ge \frac{(k-r+2) \cdot (n)}{2}$. But i can't remove this $k$ from the equation latter...

Any ideas here?


texts: Computational complexity of the clique problem

texts: What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?


texts: What are the #P-hard version of Latin square and sudoku?

texts: I know that filling partial latin square and solving sudoku are NP-hard. But what are the counting versions of these two problems?


texts: Analysis of Union Find with path compresson and rank

texts:
I have been given that $n$ make-sets and $m \ge k$ finds and $k$ unions can be performed in $O(n + m \log^*(k))$ time (I'm aware of the ackermann function but am not interested in proving that). Where $log^*(k)$ is $0$ if $k \le 1$ and $1 + log^*(log(k))$ otherwise.

The $n$ part is easy -- that's due to the number of make-sets. I'm having problems with the $m \log^*(k)$ part, which must then encompass union and find. Union is a constant cost + 2 finds.

I have been given the proof idea of spending $2^p$ credits when a node $x$ of rank $r \in \{p+1, ..., 2^p\}$ ("group p") stops being a root. $2^p$ ensures we're always in credit because it prepays for the potential $2^p$ existing children following a parent pointer to x (each kid can follow its parent pointer once before it's just added onto the root, where we pretend it's a constant cost)

The number of nodes in group p is $$\le \sum_{i=p+1}^{i=2^p} \frac{n}{2^{i}} \le \frac{n}{2^p}$$

And so in total, any group p gets $\le \frac{n}{2^p} \times 2^p = n$ credits.

There are $\le log^*(k)$ groups in total (because the greatest rank is $log(k)$).

Therefore a total of $\le n \log^*{k}$ credits are spent.

I'm under the impression that the accounting method is where the actual cost will be less than the total amount of credit spent (provided we are always in credit).

So this analysis gives $O(n + n \log^*(k) + m + k)$, which isn't what I wanted.

Edit to add question: What's wrong with the method above?


texts: Difference between graph-partitioning and graph-clustering

texts: What is the difference between graph-partitioning and graph-clustering in graph theory?


texts: What is the most efficient algorithm to get percentile distribution from histogram distribution?

texts:
So let's say you have a histogram distribution represented as an array where each element is equal to the number of numbers from the underlying data set that are equal to that element's index.

For example, if your underlying data had 5 0's, 18 1's, 11 2's, 0 3's, etc., then the array representing this distribution would look like...
histogramBinSizes = [5, 18, 11, 0, ...]

Now, let's say you want to get the percentile distribution, which would be represented as an array where each element is equal to the number of numbers from the underlying data that fall in that percentile. What's the most efficient algorithm to get the percentile distribution array? (Maybe call this array percentileBinSizes)

To make the question easier, assume the numbers in the underlying data range from 0 to 100. That would make it so that histogramBinSizes and percentileBinSizes both have lengths of 101. Is there an even more efficient algorithm when this constraint is added?

I tagged this question with data structures as well as algorithms because I'm open to solutions that use a different data structure besides arrays. However, the input and output should still be arrays.


texts: What is the impact of synchronisation overhead on parallel speedup?

texts:
When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used?

Is coarse-grained parallelism better than fine-grained parallelism in certain situations?


texts: Words equal to the concatenation of their odd and even position - characters

texts:
Let $\Sigma = \{0, 1\}$ and $$L = \{ w \in \Sigma^* | w = \mathrm{odd}(w) · \mathrm{even}(w) \},$$ where $\mathrm{odd}(w) = w_1, w_3, w_5 \ldots{}$   and $\mathrm{even}(w) = w_2, w_4, w_6, \ldots{}$ are the words constructed from the characters in all the odd and even positions of the string. I.e. $w = 0110110110 \in L$, because $\mathrm{odd}(w) = 01101, \mathrm{even}(w) = 10110$ and $w = 01101 \cdot{} 10110 = \mathrm{odd}(w) \cdot{} \mathrm{even}(w)$.

  Is $L$ regular?

I've tried using the Pumping Lemma for strings of the sort $0^{2n+1}1$ but I can't fix the value of $v^i$ from $w = uvx$ to have an either even or odd length.

I also tried to construct the DFA but it seems to need an infinite number of states to "track" which characters of $w$ get mapped to $\mathrm{odd}(w) \cdot \mathrm{even}(w)$, so my best bet is it's irregular, which means I need to find a way to prove it with the Pumping-Lemma.

Any ideas how I can find a suitable string for the Pumping Lemma?


texts:
I want to show that

  MAX−CLIQUE={(G,k)|the largest clique of G is of size exactly k} is
  DP-complete

The idea is reduce MAX-CLIQUE to

  C={(G1,k1,G2,k2) | G1 has a k1-clique and G2 does not have any
  k2-clique}

which I already know is DP-hard.

I was seeing the solution on the second page of this link, but it seems that there is a mistake in the fifth paragraph, since the graph that builds G′_1, is equal to the product tensor of the path of cardinality k1 with the graph G1, so the clique number is the minimum of the clique numbers of the factors. And this always gives 2, since every path has a clique number equal to 2.


texts: Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls

texts:
We are given $2n - 1$ boxes with a total of $B$ black and $W$ white balls. In the $i$-th, box there are $w_i$ white and $b_i$ black balls. It is required to choose $n$ boxes so that, the sum of the white balls is at least $W/2$, and the sum of black balls is at least $B/2$.
  Solve for $O(n\log{n})$.

What I am currently thinking is this:

Generate some hashtable to be able to track the boxes that we chose.
Sort the boxes by the quantity of the white (in increasing order) balls and chose the last $n$ balls every time keeping them in our hashtable.
Sort by the quantity of the black balls and do the same. Check every time to see if we already chose the box or not. Here comes the problem: Suppose we didn't. Then we can face a situation where we already have $n$ boxes that have in total at least $W/2$ white balls but at the same time, they have in total less than $B/2$ black balls. How can we overcome this problem?

We can't just switch the chosen boxes that have the least number of white balls with the one that have the maximum available number of black balls since the box with white balls can contain significant amount of black balls on its own.


texts: Understanding time complexity for kth minimum in CLRS

texts:
In chapter 10.3. Selection in worst - case linear time ($k$th minimum) from Introduction to Algorithms by Cormen, Leiserson and Rivest, the time complexity expected for step 5 of the algorithm presented in this chapter is said to take $T(n)=7n/10 + 6$ at worst.

From my point of view the time complexity is the one specified above because the number of elements larger than the median of all medians is at least $3n/10-6$, thus the remaining search space is $7n/10 + 6$, where $n$ is the size of input data.

How off am I?


texts:
I am having trouble understanding the class $coNP$. We defined

$$coNP = \left\{ \overline{A} : A \in NP \right\}$$

As far as I know, a language $A$ is in $NP$ if, and only if, a non-deterministic turing machine $M$ exists, which outputs $1$ if $w \in A$ and $0$ if $w \notin A$. But if this is true, then a turing machine $M'$ must exist which simulates $M$ and inverts the output:

$$M' = \begin{cases}0 \text{ if } M = 1\\1 \text{ if } M = 0\end{cases}$$

Therefore, $w \in A \implies w \notin L(M')$ and $w \notin A \implies w \in L(M')$, meaning that $L(M') = \overline{L(M)}$.

As $M'$ works in non-deterministic polynomial time, $L(M') \in NP$, and as $L(M') = \overline{L(M)}$, $\overline{L(M)} \in NP$, but $\overline{L(M)} \in coNP$ as well. As this holds true for all languages in $NP$, why isn't $coNP = NP$?


texts: Space complexity for connectivity problem with given graph diameter

texts:
Given $(G,D,d)$, a graph, the graph diameter and the maximum outdegree of the graph.
Verify that $G$ is strongly connected in $O(D\log d + \log n)$ space complexity.

I thought about using the $STCON$ problem for the whole nodes in the graph, but that will yield a space complexity of $O(n^2 \log^2n)$ (according to Savitch's theorem).

Then I thought about using a DFS traversal (it will be needed twice, actually), but I don't know how to prove it's space complexity.


texts: Partition a graph such that each subgraph fits the machine constraint

texts:
Lets assume there is no upper limit on number of machines.

Here are the goals of partition:

Each node in the graph has a weight. There is an upper limit on total weight stored on a machine. All the nodes are not fitting on one machine, hence we are starting with partition.
When we store an edge on a machine, then the weight of both nodes is being placed on that machine.
All machines are same and have a capacity c
Each node should have all its edges on a single machine. If sum of weights of all neighbors of a node is greater than c, only then its data should be split on more than one machine. In which case, minimize the number of machines to which data is split.
Edge data can be repeated across machines. This relaxation is necessary to satisfy the condition that each node of the graph should have all its neighbors information co-located on a single machine in the network. (unless not possible)
Minimize the total number of machines used.

Corollary: If each node's edges data can be fitted on one machine, then to access any node's edges information we will only have to access one machine on the network.


texts: Do a pair of parallel edges form a cycle in a graph

texts:
Whenever there is a back edge, a cycle is detected.
Then, do a pair of parallel edges form a cycle in a graph? If no, why it is not a back edge?


texts: What would be the time complexity if a recursive function is inside a loop?

texts:
I am confused in calculating the time complexity for a recursive function inside a loop.

Function (int n){
   if(n<=1) return;
   for(int i=1;i<=3;i++)
       Function(n/3);
   }

in the text book answer written for this is theta(n). Please explain how is it so?


texts: Is there a good analogy between spectral representation of a signal and graph theory?

texts:
I am working on some time series problems where the Fourier representation of the signal in the frequency domain is also important. I am wondering if there is any connection between time series signals consisting of sinusoidal/inherently periodic functions (functions that can be cleanly represented by a sum of sinusoids) and graph theory.
Thanks,
Josiah


texts: Semantic parsing with Grammatical Framework - is this possible?

texts:
So far I have learned about categorial grammars, type logical grammars and formal semantics of natural language, the relevant tools are Cornell Semantic Parsing Framework https://github.com/clic-lab/spf and Grails 3 Type Logical Theorem prover http://www.labri.fr/perso/moot/grail3.html. My preferences are strongly biased in favor of symbolic methods and that is why I was sure that I am learning the best technique in the domain of symbolic methods.

But now I have discovered that Grammatical framework https://www.grammaticalframework.org/ (GF) is based on categorial grammars, I am still learning what this means and why the mainstream categorial grammar and type logical semantics literature in no way mentions GF.

But it would nice to hear how GF is connected with semantic parsing and semantic parsers? Is it possible from the GF grammars more or less automatically construct categorial grammar parser and lexicon? By semantic parsing and formal semantics I mean more or less Montague grammars and the use of logical formulas (usually lambda calculus or sophisticated logics in guise of lambda calculus) for the representation of the meaning of the natural language texts.

And more general question - GF is more or less connected with the frame semantics and FrameNet (I am still learning what this means), so - the question is - how frame semantics is connected with formal semantics of natural language? Can I assume that frame semantics is less formal, more coarse grained semantic than formal semantic. I.e. frame semantics is just collection of crude information that can be used for the derivation of the formulas for the formal semantics, i.e. can I assume that the frame net is just one step towards full formal semantics and that encoding frame semantical knowledge into logical form can give the formal semantics? Are there efforts to do this?

So - actually - I am trying to find connection between GF and frame semantics from the one side with the catgorial/type logical grammars with Montagua approach to the other side.

My topic belongs to the computer science, because linguists in no case develops such theories and because most of relevant articles are indexed by DBPL.

The GF Book https://www.grammaticalframework.org/gf-book/ has chapter 1.9 about relation with other grammars, the connection with categorial grammars is mentioned but not explicitly stated and deepened.


texts: What's the time complexity bound for the Knapsack with real weights?

texts:
Let's start with the formalism:
Let $W$ be the total weight of our bag, $1,...,n$ be our elements, $w_1,...,w_n$ their corresponding weights, and $v_1,...,v_n$ their corresponding values.

As is known, the knapsack problem for integer weights can be solved by dynamic programming (or equivalently, using recursion + memoization), with time complexity of $\mathcal O(nW)$, where $W$ is the total weight our bag can hold, and $n$ is the number of items.

However, for real numbered weights, the algorithm fails (just imagine a billion items with weight $<1$, and $W=1$). We probably can round them in a clever way and then scale them up to be integers again, but that'd blow the size of the problem up in an inacceptable way.

Another approach would be to use recursion instead of dynamic programming, because the idea behind the algorithm still works out - either the $n$'th item is in the optimal solution, or not.

However, even with memoization, we can easily choose our weights in a way so that all sums
$$\sum_{
\begin{align}
 i&\in M\\
M&\subseteq \{1,..,n\}
\end{align}} w_i$$

are distinct, leaving us with $2^n$ weight-sums to memoize.

Is there any optimal algorithm that manages to keep the time complexity pseudopolynomial?


texts: How does one know what statements in Coq require Induction?

texts:
I was trying to learn Coq using the famous book Software Foundations. In it I found the following:

Theorem mult_0_r : forall n:nat,
  n * 0 = 0.
Proof.
  induction n as [| n IHn].
  - simpl. reflexivity.
  - simpl. rewrite -> IHn. reflexivity.
Qed.

which I understand perfectly but find rather unintuitive. I understand perfectly how each step works but it would have never occurred to me to use induction to prove such a trivial fact. In fact in the mathematical proof I had in mind that would have been a fact/property (or I guess an axiom) of 0. i.e. $\forall n \in N, n \cdot 0 = 0$ is true by definition. I guess in Coq (or the way we set up numbers? thats not true).

My biggest complaint or worry is that if such a trivial thing requires induction I feel now I am unable to recognize what needs induction (at least in Coq). I know it needs it here because I am in the induction chapter. But in normal maths its usually quite obvious because the problem is obviously recursive. But I wouldn't have really thought of that proposition as recursive. For example it goes on to prove more things as exercises:

Theorem plus_n_Sm : ∀n m : nat,
  S (n + m) = n + (S m).
Proof.
  (* FILL IN HERE *) Admitted.
Theorem plus_comm : ∀n m : nat,
  n + m = m + n.
Proof.
  (* FILL IN HERE *) Admitted.
Theorem plus_assoc : ∀n m p : nat,
  n + (m + p) = (n + m) + p.
Proof.
  (* FILL IN HERE *) Admitted.

which I am sure are not too difficult, but my worry is that in isolation I would have never thought such trivial statements required something as sophisticated as induction. I didn't even learn induction until last 2 years of highschool and didn't really do it seriously until college. So now I see trivial statements requiring what seems to me, sophisticated mathematics.

I just feel my intuition got really lost. When I do Coq proofs (in isolation), how do I know when to use induction and on what? I doubt there is a general procedure (of course) but proofs do exist. So there must be something guiding us to use induction in Coq.


texts: generalized translation operator on graph

texts:
David IShuman in " vertix-frequency analysis on graph" claims that,"we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting and When we apply this transform to a signal with frequency components that vary along a path graph, the resulting spectrogram matches our intuition from classical discrete-time signal processing. Yet, our construction is fully generalized and can be applied to analyze signals on any undirected, connected, weighted graph."

in this paper generalized translation operator that allows us to shift a window around the vertex domain so that it is localized around any given vertex, just as we shift a window along the real line to any center point in the classical windowed Fourier transform for signals on the real line.

generalized translation operator:

$$(T_{i}f)(n) := \sqrt{N}(f*\delta_{i})(n) = \sqrt{N}\sum_{\ell=0}^{N-1}\hat{f}(\lambda_{\ell}) \chi^{*}_{\ell}(i)\chi_{\ell}(n) .$$

See the picture

Question

How do I understand the motion algorithm on the graph?
How to label irregular graphs with high dimensional data?

Thanks.


texts: Is the language $\{ 0^m10^n \mid m,n\geq1 \}$ regular?

texts:
$L = \{ 0^m10^n|m\geq1 \wedge n\geq1 \}$
Is this a regular language?

A language is regular when there is a DFA accepting the language. Since there is a DFA accepting this language I suppose that it is a regular language. But as I have seen in the book it says that it is not regular. So I am confused. Can someone guide me on this?


texts: How to state a recurrence that expresses the worst case for good pivots?

texts:
The Problem
Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and $\frac{3n}{4}$(a good pivot). Also with probability $\frac12$ the pivot selected will be between 1 and $\frac{n}{4}$ or between $\frac{3n}{4}$ and $n$(i.e.  a bad pivot)

1.State a recurrence that expresses the worst case for bad pivots.
2.State a recurrence that expresses the worst case for good pivots.

My Work:
I understand the overall idea of quicksort - pivot all the elements around the pivot(less-> to the left, right -> to the right) and repeat the process for the elements to left of the pivot and for the elements to the right of the pivot
Here is the recurrence I came up with for 1 -$ T(n) =
\begin{cases}
c  & \text{if $n$ is 1} \\
T(n-1) + n, & \text{if $n$ is > 1}
\end{cases}$
I was able to work out this recurrence by reasoning that if I just chose the worst possible pivot(either greatest or least), I would have to traverse through all the elements(the $n$) and then repeat this process for the rest of the elements(n-1)

I am having trouble with coming up with a recurrence that expresses the worst case for good pivots. The two I came up with is if you choose a pivot of $\frac{n}{2}$ and if you choose a pivot of  $\frac{n}{4}$

The recurrence for a pivot of $\frac{n}{2}$ would be  $ T(n) =
\begin{cases}
c  & \text{if $n$ is 1} \\
2T(\lfloor(n/2)\rfloor) + n, & \text{if $n$ is > 1}
\end{cases}$
I wasable to reason this out because if you had a pivot of $\frac{n}{2}$, you have to evaluate all the elements with regards to the pivot(the $n$) and then partition the equal proportions to the left and to the right of the pivot.

The recurrence for a pivot of $\frac{n}{4}$ would be $ T(n) =
\begin{cases}
c  & \text{if $n$ is 1} \\
T(\lfloor(3n/4)\rfloor) + T(\lfloor(n/4)\rfloor) + n, & \text{if $n$ is > 1}
\end{cases}$

Which one of these would express the worst case for good pivots?


texts:
I'm struggling to understand the absorption law proof and I hope maybe you could help me out.

The absorption law states that: $X + XY = X$
Which is equivalent to $(X \cdot 1) + (XY) = X$

No problem yet, it's this next step that stumps me. How can I apply the distributive law when there are two "brackets"?

How can I manipulate $(X \cdot 1) + (XY) = X$ to give me $X \cdot (1+Y)$?

I understand that the absorption law works. I would just like to see how the algebra proof works.

Thank you!


texts: Is the following Greedy algorithm to generate Gray Codes always correct?

texts:
I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites).
However, I then had an idea for a Greedy Gray Code Algorithm: Start the Gray Code at 0 and at every step, find and change the single smallest bit such that we get a new, not-visited-before number. Keep on repeating this until we have exhausted all the 2^N possible numbers with N bits.
I was sure that this approach wouldn't work for some values of N, but so far, it has worked for all N from 1 to 30. This was quite surprising for me, especially as I haven't seen this Greedy approach mentioned anywhere as a solution to the Gray Code Problem.
So, my question is, does this Greedy algorithm for generating N-bit Gray Codes always work? Is there a proof of its correctness? Otherwise, what value of N causes this algorithm to not be able to generate a correct Gray Code?


texts: 1M = 2^20, while the max number of memory locations for 16 bits is 2^16. How could there be a memory size of 1M x 16? Or can there? Wondering about this for a question we were given..


texts: Conditions for applying Case 3 of Master theorem

texts:
In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this.
$a\geq1$, $b>1$, $f$ is a nonnegative function defined on exact powers of b. The recurrence relation for $T$ is $T(n) = a T(n/b) + f(n)$ for $n=b^i$, $i>0$.

For the third case, we have $f(n) = \Omega(n^{\log_ba +\epsilon})$ for some fixed $\epsilon>0$ and that $ af(n/b)\leq cf(n)$ for fixed $c<1$ and for all sufficiently large $n$. In this case, $T(n) =\Theta(f(n))$ since $f(n) = \Omega(n^{\log_ba +\epsilon})$.

I was wondering if the condition that $f(n) = \Omega(n^{\log_ba +\epsilon})$ is unnecessary since the regularity condition $ af(n/b)\leq cf(n)$ for all $n>n_0$ for fixed $c<1$ and for some $n_0$ implies that
$$
\begin{align*}
f(n)&\geq m\left(\frac{a}{c}\right)^{\log_b(n/n_0)} \text{ where } m=\min_{1\leq x\leq n_0}{f(x)}\\&\ge\left(\frac{n}{n_0}\right)^{\log_b(a/c)}=\Theta(n^{\log_ba +\log_b(c^{-1})})=\Theta(n^{\log_ba +\epsilon}).
\end{align*}
$$
This will hold as long as $f(n)$ is non-zero. Hence $f(n)=\Omega(n^{\log_ba +\epsilon})$.
Therefore we merely need to add the condition that $f(n)$ is positive for all but finitely many values of $n$ for case 3. Am I correct about this?


texts:
I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during the exploration of the adjacency list of a vertex $w$, if $v$ has not already been processed, then $v$ is added to the stack. A vertex is marked a processed when it exits the stack (contrary to BFS, where a vertex is marked as seen when it enters the queue).
That way, the stack may contains duplicates during the execution of the DFS. Since each vertex is processed at most once, the size of the stack for a graph $(V, E)$ is $O(|V| + |E|)$.
Since I wondered if it was possible to get $O(|V|)$ space memory for the DFS, I tried to find a data structure of stack without duplicates. I found a solution for the DFS (given as an answer to this question), but the structure I found has restrictions: it works in space $\Theta(n)$ in the case I know in advance that the values entering the stack will be in $[\![0, n-1]\!]$.
My question is: is there a more efficient way to implement a stack without duplicates (in a stack without duplicate, if I push an element already in the stack, then this element is put at the top of the stack, and the duplicate is deleted), in the general case where I don't know in advance the values entering the stack? The time complexity for operation of pushing/popping should be in $O(1)$ worst case, amortized or average case (in this order of preference). Also, is there a way to use $\Theta(n)$ space memory, $n$ being the current size of the stack (and not the maximal size).


texts: Bellman-Ford without getting stopped by negative cycles

texts:
Let $s$ be the source vertex. In the standard Bellman-Ford algorithm (e.g. the version found in CLRS), when there is a negative cycle reachable form $s$, the algorithm will return that a negative cycle is found.

But let's say I am interested in the shortest path from $s$ to some vertex $a$, and it might be that there is a negative cycle reachable from $s$, but it could also be that no such negative cycles have a path to $a$. So technically there is still a shortest path from $s$ to $a$. But Bellman-Ford would still say "negative cycle detected" although it is irrelevant! How might Bellman-Ford be modified to still spit out either the shortest path or that there is no shortest path?

Attempt: At first I saw thinking of running Bellman-Ford until $2n$ (or some large number) and then seeing if the value for $s$ to $a$ stays stable, but I found an example that invalidates this. It appears that I must find all negative cycles reachable from $s$ and check if each of them can reach $a$. That seems like an immense amount of work! So is there any clever way to do this?


texts: Is there a way to uniquely map every natural number x < N to another number y < N uniquely and randomly?

texts:
Imagine you have a number x, when x ∈ [0, N]. Is there any algorithm that can map x to y, so that y is also y ∈ [0, N] with the mapping being unique, and the distribution of all y is distributed pseudorandomly across the whole range? I know it's possible by just generating a set from 0 to N, shuffling it, and using x as an index. I want to know if there is some smarter way to do this that doesn't involve a memory footprint that is linear to x.
The Pigeonhole principle shows that this is impossible when y > x, and it is trivially possible when x = y (well...  y := x), but is this possible in a manner when y is randomly distributed?
My first (bad) attempt in C# was to use a golden ratio and travel around a circle, since mathematically this is guaranteed to give a unique angle every time. In theory (phi * n) mod 360 is sort of random looking and unique. Sadly this only works if you have infinite precision and not at all when you have discrete buckets for the output, so this idea didn't really work out, even when N = 255:

So out of pure curiosity I'm wondering - is there some beautiful algorithm to map this so that it doesn't involve either a predefined list of candidate numbers or a list of already used numbers, or so on?