texts: Algorithm for solving incremental max flow problem

texts: I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed and edge weights are all integers. I can find the maximum flow the first time, by Ford-Fulkerson's algorithm or some variant, but at each step thereafter it would be great if I could use a different (faster) algorithm to find the max flow. At each step, only one of the edge weights is changed, and it is only changed by a value of +1 or -1. What sort of algorithm could do this incremental update for me? It needs to be faster than recomputing the max flow from scratch. It could also be two separate algorithms (but similar I would hope): one for the incrementing case and one for the decrementing case. Thanks in advance for the help!


texts: Wikipedia does not list insertion complexity for arrays - why?

texts:
Wikipedia does not list insertion complexity for arrays in the list of linked-list implementations.

Is this because insertion operations are not defined on the array ADT?


texts:
If the frame buffer has 8 bits per pixel and 8 bits are allocated for  each of the R, G, B components, what would be the size of the
      lookup table?
      a) 24 bytes
      b) 1024 bytes
      c) 768 bytes
      d) 256 bytes

I read about Framebuffer and what I understood is

"It stores the color values (in case of color frame buffer) in indexed form. So if we have $8-bit$ color, then possible colors are  $2^8$*So frame buffer would store color values for each pixel on screen and it's size would depend on screen resolution. Corresponding actual color values (or codes) would be stored in lookup table"

So, Lookup table would have
$2^8 = 256$ entries, which is $256$ bytes, since each entry is of 8-bits = 1 byte.

But that is not the correct answer to above question. So, can anyone tell, where am I going wrong ?

Also, question says frame buffer has 8-bit per pixel and 8-bits are allocated for each RGB , This means for each pixel, frame buffer has $8,8,8,8$ bits allocated ?


texts: How to transform an arbitrary graph into a fixed vector representation?

texts:
Actuality I work in computer vision, specifically on a problem known as "scene graph modeling." This problem aims to convert an image $I$ in a graph $G=(V,E)$ where the nodes $V$ represent the objects (and the features) in scene and the edges $E$ the relationships between objects. An interesting paper on this topic is Graph R-CNN for Scene Graph Generation (Note that unlike of only to detect the objects in an image, the scene graph aims to capture the contextual information of image). A graph is a mathematics structure rich in information, and it would be very interesting to integrate graphs in a machine learn approach. In order to achieve this task is necessary to transform a graph in a vector representation. Some works that intend solve this problem are the following:

SEMI-SUPERVISED CLASSIFICATION WITH
GRAPH CONVOLUTIONAL NETWORKS: The problem with this algorithm is that assumes a fix number of nodes. After training, this algorithm take a graph $G=(V,E)$ as input  (whit $N$ nodes, that is, $|V|=N$) and outputs a fixed vector representation.
graph2vec: Learning Distributed Representations of
Graphs: This algorithm is flexible due to permit build a vector representation from a graph $G$ without restrict the number of nodes. However, it needs to know the whole space graph. That is, given a set $G=\{g_{1},g_{2},\dots,g_{i},\dots,g_{m}\}$, where $g_{i}$ is the i-th graph, this algorithm builds a vectorial representation $V=\{v_{1},v_{2},\dots,v_{i},\dots,v_{m}\}$, where $v_{i}$ is the i-th vector associated with the graph $g_{i}$. This algorithm is originally proposed to text analysis, where the features in nodes are of low dimension, I do not know if it can work using high dimension features in nodes.

I would like to know if there is another simple algorithm that allows me to convert any graph into a fixed vector representation.


texts: What these simple rules of logical implications mean

texts:
Their are many rules of logics, predicate calculus, inferences and syllogisms which haunt me always. It feels better when I find some sensible name to particular rule which also gives me intuition about the meaning of the rule. Recently I came across some simple tautologies:

$((x \rightarrow y)\wedge(x \rightarrow \neg y))\rightarrow \neg x$
$((x \rightarrow y)\vee(x \rightarrow \neg y))$

I am struggling to find intuition or reasonable interpretation of their meaning:

Interpreting  rule 1:
If a first variable $x$ implies both: second variable $y$ and its
negation $\neg y$, then why the negation of first variable $\neg x$
should always hold? Does it mean to imply that no such variable can
exist which can imply both: another variable and its negation?
Interpreting  rule 2:
Why should a first variable $x$ should always imply either (any
given) second variable or its negation?
Finally are there any formal names used to refer these rules?

I must be missing something very basic.


texts: How to prove/disprove distribution of division over union

texts:
How can I prove distribution of division over union in relational algebra, i.e. the following:

$$(R \cup S) / X \overset{?}{=} (R / X) \cup (S / X)$$


texts:
In computer architecture class, my lecturer was explaining about I/O interfaces and modules, but somehow neither me nor my classmates understood almost a word he said.. We still don't get which parts of a computer is an I/O interface.
For example, which one of these are an I/O interface? A VGA card or PCI Express?


texts:
So I have the question:

Prove that any directed cycle in the graph of a partial order must only involve one node.

So I know that a partial order must be transitive, antisymmetric, and reflective, but from there I am pretty lost. I also know that any path of one or more edges from a node to itself is a directed cycle, but from there I am having trouble connecting everything.

I kind of need help as to where to start thinking, and the first step as to how to answer this question.


texts: in the lambda calculus with products and sums is $f : [n] \to [n]$ $\beta\eta$ equivalent to $f^{n!}$?

texts:
$\eta$-reduction is often described as arising from the desire for functions which are point-wise equal to be syntactically equal. In a simply typed calculus with products it is sufficient, but when sums are involved I fail to see how to reduce point-wise equal functions to a common term.

For example, it is easy to verify that any function $f: (1+1) \to (1+1)$ is point-wise equal to $\lambda x.f(fx)$, or more generally $f$ is point-wise equal to $f^{n!}$ when $f: A \to A$ and $A$ has exactly $n$ inhabitants.  Is it possible to reduce $f^{n!}$ to $f$?  If not, is there an extension of the simply typed calculus which allows this reduction?


texts: Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable

texts:
I came across following facts:

  Set of finite languages over a finite alphabet is countable.
  Set of languages over finite alphabet is uncountable.
  I believe proof of this will be similar to below fact number 3.
  Set of languages over {0,1} is uncountable.

I came across proof of fact 1 here and of fact 3 here.

Summary of fact 1 proof:

  Let your finite alphabet be $Σ={a_1,…,a_ℓ}$ and let $\#$ be some character not in $Σ$. Let $L={w_1,…,w_n}$ be a finite language over $Σ$. Then the string $\#w_1\#w_2\#…\#w_n$ maps different $L$ to different integer.

Summary of fact 3 proof:

  Let $L$ be set of all finite length strings over $\{0,1\}$. We can generate a one-to-one mapping from $L$ to $\mathbb{N}$ : just add a 1 in front of each string in W and interpret the resulting strings as binary numbers. So $L$ is countable. Now let $L_{\{0,1\}}$  is countable, where $L\{0,1\}=\{L_1,L_2,L_3,…\}$ with each $L_i$ being a language over $\{0,1\}$. Given that each $L_i$ is a set whose elements are strings from $L$, and since $L$ is countable, we can build a table whose row indices are language indices and whose column indices are string indices as follows: for each table cell with row index $i$ and column index $j$, write 1 if the language $L_i$ contains the string $s_j$ or 0 otherwise.

  We flip the value of every diagonal cell on the table above, then collect all strings $s_j$ such that the diagonal cell on the column of $s_j$ has a 1 after flipping:

  Lets call it $L_{diag}={s_2,s_3,...}$.
  $L_{diag}$ is a language with a special property: it is different from every language $L_i∈L_{\{0,1\}}$. This implies $L_{diag}≠L_i$ for all $L_i∈L${{0,1}} and therefore $L_{diag}∉L_{\{0,1\}}$. However, since $L$ is a set of strings which are in $L$, $L_{diag}$ is a language over {0,1} and therefore $L_{diag}∈L_{\{0,1\}}$, a contradiction. Hence $L_{\{0,1\}}$ cannot be countable.

Doubts

I get both the proofs, but I dont get why approaches followed in each of them cannot be used to prove other fact incorrect. That is:

Why I cant use fact 1 proof approach to prove fact 3 is incorrect, that is "set of languages over {0,1} is countable".
Cant I form similar string string $\#w_1\#w_2\#…\#w_n$ for different languages to map them to different integers?
Why I cant use fact 3 proof approach to prove fact 1 is incorrect, that is "set of finite languages over a finite alphabet is uncountable"?

Cant I form similar table for finite languages and then form $L_{diag}$ which wont belong to the set of finite languages?


texts: Maximum number of matched vertexes in a one-to-many bipartite graph

texts:
I have a variant of bidding problem at hand.
There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who are satisfied. A bidder is satisfied if he gets all the items that he bid for in the first place. For eg-

Bidders = A,B,C
Items = 1,2,3,4

Bidder    Bids
A         1,2
B         2,3
C         3,4

In this case its only possible to satisfy 2 bidders at max.

I've tried to model the problem to a maxflow problem and have taken several approaches but to no avail
My approaches so far-

Tried to model this problem as a bipartite matching problem. The only problem being that instead of a one-one mapping I have a one-many mapping with an AND condition.
A maxflow problem with edges going from source to each vertex with a capacity of number of bids. Problem here being ensuring that all edges from a bidder are selcted.
A maxflow problem with both upper bounded and lower bounded edge capacities.


texts: Speeding up the Rummikub algorithm - explanation required

texts:
Regarding this question: Rummikub algorithm.
I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four colours are involved). Then, I reached the part in which the says that the algorithm runs in $O(ABCD(A+B+C+D))$ time, which is easy to determine why.
However, he the goes on to saying that we can speed up the algorithm so as to run in $O(ABCD)$ time by changing
"the recurrence to ensure this occurs only once while maintaining correctness, which leads to $O(1)$ time for every 'cell' in the DP-table".
My problem is: I do not see how this can be done. I have tried playing around a bit with the recurrence, but I do not see how it can be modified, or what else we should keep track of so that we can speed up the time.
Can someone please give me a hint/explanation on how this can be done?


texts: Looking for bibliography on specific 2D graphics topics

texts:
Can someone provide me with good book sources about any of the following graphics topics with mathematical and/or code explanation ? I find these topics so interesting and it surprises me I haven't encountered any of those in CG books. Those books contain the usual drawing shapes, and image manipulations. And all those books of general random walks in mathematics and computer sciences don't mention them either.

Simplex Noise
Reaction-Diffusion Algorithm
Perlin Noise and Perlin
Flow Fields
Voronoi Noise
Worley Noise
Any other type of Noise!
Cardioids/Cycloids/Epicloids and other spirograph algorithms
Lissajous curves
Langton's Ant
Steinberg Dithering
Any maze/labyrinth making algorithms
Circle Packing
Metaballs (in 2D)


texts: Does my "hollow list" structure exist already?

texts:
I came up with an implementation in c for arrays which can be extremely large yet only use an amount of memory proportional to how much data you have written to it. What I want to know is if there is a name for this kind of list or structure. Here is my code in C for the structure and example use:

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

typedef struct hollow_list hollow_list;

struct hollow_list{
    unsigned int size;
    void *value;
    bool *written;
    hollow_list *children;
};

//Creates a hollow list and allocates all of the needed memory
hollow_list hollow_list_create(unsigned int size){
    hollow_list output;
    output = (hollow_list) {.size = size, .value = (void *) 0, .written = calloc(size, sizeof(bool)), .children = calloc(size, sizeof(hollow_list))};
    return output;
}

//Frees all memory of associated with a hollow list and its children
void hollow_list_free(hollow_list *l, bool free_values){
    int i;
    for(i = 0; i < l->size; i++){
        hollow_list_free(l->children + i, free_values);
    }
    if(free_values){
        free(l->value);
    }
    free(l);
}

//Reads from the hollow list and returns a pointer to the item's data
void *hollow_list_read(hollow_list *l, unsigned int index){
    if(index == 0){
        return l->value;
    }
    unsigned int bit_checker;
    bit_checker = 1<<(l->size - 1);
    int i;
    for(i = 0; i < l->size; i++){
        if(bit_checker & index){
            if(l->written[i] == true){
                return hollow_list_read(l->children + i, bit_checker ^ index);
            } else {
                return (void *) 0;
            }
        }
        bit_checker >>= 1;
    }
}

//Writes to the hollow list, allocating memory only as it needs
void hollow_list_write(hollow_list *l, unsigned int index, void *value){
    if(index == 0){
        l->value = value;
    } else {
        unsigned int bit_checker;
        bit_checker = 1<<(l->size - 1);
        int i;
        for(i = 0; i < l->size; i++){
            if(bit_checker & index){
                if(!l->written[i]){
                    l->children[i] = hollow_list_create(l->size - i - 1);
                    l->written[i] = true;
                }
                hollow_list_write(l->children + i, bit_checker ^ index, value);
                break;
            }
            bit_checker >>= 1;
        }
    }
}

int main(){
    int a = 221;
    int b = 222;
    int c = 9;
    int d = 89;

    hollow_list h;
    h = hollow_list_create(30);

    hollow_list_write(&h, 221999999, &a);
    hollow_list_write(&h, 9999, &b);
    hollow_list_write(&h, 22999999, &c);
    hollow_list_write(&h, 1, &d);

    printf("%d\n", *((int *) hollow_list_read(&h, 221999999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 9999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 22999999)));
    printf("%d\n", *((int *) hollow_list_read(&h, 1)));
    printf("\n");
    printf("\n");
    printf("\n");
    printf("%d\n", a);
    printf("%d\n", b);
    printf("%d\n", c);
    printf("%d\n", d);

    c = 56;
    printf("%d\n", *((int *) hollow_list_read(&h, 22999999)));
}

These lists seem to be really useful alternatives to linked lists, and fast too: the worst case scenario for a read or write to a list is O(log n) for a list of n elements. I'd be surprised if this kind of structure didn't already exist, but I would simply like to know what it is called so I could refer to it by it's proper name haha.


texts: Simple Recognition Algorithm, How Does It Work?

texts: I am trying to understand how a simple image recognition of an image with dynamic size could work. What I have seen is that parts of the images are taken and evaluated. For example a simple finger recognition could be done turning the image grayscale, taking parts of the image and evaluating them. What I understand is how these parts are evaluated and how this could be done on an image with dynamic size ratio. Is a kernel function needed, or how do you proceed when you take the different parts of an image?


texts: Formulating Integer Program for passing packages on a cycle

texts:
Can't seem to figure out the IP formulation for this.

Question
Suppose there are $n$ people connected in a circular fashion as demonstrated by the diagram.

Individuals need to send packages to each other but can clearly only pass the packages in a clockwise or anticlockwise direction. Each person has at most one package to send to another person. So let $P_i$ denote the number of passes between person $i$ and person $i+1 \pmod{n}$. We want to minimize $\max\limits_{0 \leq i \leq n-1} P_i$. So basically, we want to minimize the number of passes between pair(s) that have the most number of passes between them. We can also think of this problem like a network where certain connections (edges) are exhausted so in order to reduce stress between those nodes, we can redistribute the flow in the opposite direction.

My Attempt

We notice that if we have $k$ packages to distribute, there are a maximum of $2k$ paths that each package can take to get to its destination since each package can either go clockwise or anticlockwise. Intuitively, these paths can overlap and the greatest number of overlaps will be equivalent to $(\max\limits_{0 \leq i \leq n-1} P_i)$. So ideally we want to minimize overlaps but how to actually formulate this is my problem.

EDIT

Here is the formulation I came up with.

$R_{ij} =
\left\{
 \begin{array}{ll}
  1  & \mbox{if edge $(i,i+1 \pmod{n})$ is on route $j$}\\
  0 & \mbox{otherwise }
 \end{array}
\right.$

$X_{j} =
\left\{
 \begin{array}{ll}
  1  & \mbox{if route j is chosen}\\
  0 & \mbox{otherwise }
 \end{array}
\right.$

We assume that route $j$ distributes some package clockwise and route $j+1$ distributes the same package anticlockwise.

IP formulation:

$
\begin{array}{ &  &}
Min: & \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{2k-1} R_{ij} X_j\\
s.t. & X_j + X_{j+1} = 1 \\
     & X_{ij} = 0 \ or \ X_{ij} = 1
\end{array}
$

Essentially what this is saying is that, we minimize the number of passes across each edge, for each of the possible $2k$ routes. The first constraint makes it so that only a clockwise or anticlockwise route must be taken to distribute the $j$-th package. It makes sense to me but i'm not sure.


texts: Approximate probabilities of passing a NIST statistical test

texts: I am working with random number generation and testing, so I'm using NIST statistical tests to examine my random numbers. Now I want to compare my solution with other RNGs, but i can't find any probabilities of passing a NIST statistical test for them. So does anyone have that info? Info about both PRNGs and TRNGs would be appreciated.


texts: Automaton recognizing ambiguously accepted words of another automaton

texts:
Let $A$ be a nondeterministic automaton. Let $X(A)$ the set of words for which there at least two accepting paths.

In one of the previous exam, for which no answers are available, it is required to prove that there exist a deterministic automaton whose language is $X(A)$. Furthermore, if the original automaton has $k$ states, then the new automaton should have $3^k$ states.

I have tried multiples approaches to no avail:

Make an automata that keeps track of which path was taken, but the size of the automata grew infinitely because of cycles...
An automaton for each state I also kept track of which state it came from, but it was just a scaled down version of previous attempt. Which didn't work if the path started to converge early.
Tried an automaton where I encoded each state with the set of all the states from automaton $A$. And for each state I included whether I went through that state 0, 1 or more than 2 times.


texts: Use minimum number of swaps so each bin contains balls of the same color

texts:
There are $n$ bins, the $i$th bin contain $a_i$ balls. The balls has $n$ colors, there are $a_i$ balls of color $i$. Let $m=\sum_{i=1}^n a_i$.

A swap is take a ball from one bin and swap with a ball from another bin. We want minimum number of swaps such that each bin only contain balls with the same color.

I know a easy special cases $a_i\leq 2$ for all $i$. (If $a_i=2$ for all $i$, then you can even do it by swapping each ball at most once.)

Edit: This is wrong because finding $c(D)$ is NP-hard.

If we know which color goes to which bin, the problem is easy.

Consider a multi-digraph $D=(V,A)$, $V=\{v_1,\ldots,v_n\}$. If we know color $i$ goes to bin $b(i)$, then there are $k$ parallel arcs $(j,b(i))$ in $A$ iff bin $j$ contains $k$ balls of color $i$. Each component of the graph is Eulerian.
The minimum number of swaps required is $m-c(D)$, where $c(D)$ is the number of arc disjoint cycles that covers $A$.
We can swap by "following" a Eulerian circuit. (a swap using an arc of a minimal cycle can change it to a smaller minimal cycle and a self loop). Once the entire graph is set of self loops, we have made all the necessary swaps.

How hard is this problem in general?


texts: Adapt a one-tape turing machine's algorithm that find the center of a string in O(nlog(n)) to find the first third

texts:
I have found this answer that finds the center of an input string in nlog(n) complexity. I have tried to use it as a starting point to find an algorithm that finds the character(s) that separate the string in two parts (1/3 + 2/3) by changing some elements of the initial algorithm but I can't find the right modifications that really works on every example. Which adaptations can be made to the initial algorithm that will work for every length ?
I add the image for the machine that finds the center.
Example: for n=3k+1 and n=3k+2
XXXX -> XMXX

XXXXX -> XMMXX


texts: Alternative criterion for approximate maximum-weight perfect matching algorithms

texts:
Is there any literature on approximate maximum-weight perfect matchings where the approximation criterion is not the factor between the approximate and exact weight sum achieved by each solution, but instead the cardinality of the intersection of the edge sets in the approximate and an optimal solution? The relevant class of graphs $G(V_1\cup V_2,E)$ is bipartite and assumed to have perfect matchings, i.e., $|V_1| = |V_2| = N$.

To be clear:

An $(1-\epsilon)$ approximation algorithm obtains a solution, i.e., a perfect matching $E'\subset E$, for which, for some $\epsilon > 0$, the sum of edge weights is equal or greater than $(1-\epsilon)$MWM, where MWM is the maximal sum of edge weights among all perfect matchings. Assume that $\mathcal{E}$ is the set of optimal solutions. I seek an algorithm which produces a perfect matching $E''$ satisfying $\max_{E'\in\mathcal{E}}|E''\cap E'|\geq(1-\epsilon)N$. I am willing to restrict the problem to the class of graphs for which the optimal solution is unique, and therefore the complicating term "$\max_{E'\in\mathcal{E}}$" can be removed from the problem definition.

Randomized algorithms, in the sense that output satisfies the required inequality with probability $1 - \delta$, for some $\delta > 0$, are also welcome.

I am familiar with Duan and Pettie's work, and most references therein.


texts:
I was reading through the classic CLRS with the intention of reviewing the hash tables theory, more specifically the hash function definition I just wanted a reference to quote.

I cannot find a formal definition given but I think it's fair to say a hash function (not univerisal) $h$ is a surjective map from a set of keys $K$ to a subset of integers $U$, for each $k \in K$ we define $h(k)$ to be the hash value of $k$. From the explanation given in CLRS it seems though this restriction on $U$ (be integers) might be too restrictive, however since I think the definition has to show some practical aspects I think this might be correct.

Can you either give me:
1. A paper/book with a formal definition
2. Confirm if my definition is correct?

Thank you


texts: Sequencing or continuation-passing in pure lambda-calculus

texts:
I am trying to solve the following exercise given here.
Consider the following number representation. How to define the addition?
|0| = λx.x
|1| = λx.λx.x
 ...
|n + 1| = λx.|n|

The successor and predecessor operators are easy to define:
Succ n = λx.n
Pred n = n (λx.x)

An "obvious" solution for defining the addition is to use the successor operation plus the test for zero together with the fixed point combinator, something like (Y F) for F given below (the operator if and booleans are defined as usual):
F = λf.(λm n. if (Is0 m) n (Succ (f (Pred m) n))

But defining Is0 seems non-trivial. The problem is that a numeral |N| consumes N+1 arguments, and N arguments are simply erased by it. Hence, if I apply such a function, it seems reasonable to stop its application when it becomes clear that the numeral, e.g. is not an identity. I guess it is some sort of continuation, but I cannot imagine how to model it in the pure lambda-calculus. Maybe someone knows any tips that may help?
A sequencing operator can also help to define the addition. If an application of a numeral |m| is delayed until a numeral |n| is applied to all its arguments, the result will be exactly a numeral |n+m|. Maybe there exists a variant of such a sequencing combinator in the pure lambda-calculus?
The answer which is provided by the author of the exercise uses a non-pure operation (namely, IsProcedure which checks whether its argument is a function).
UPD: It is not hard to do a CPS in lambda-calculus (details for CBV can be found here). Seems that is not enough for solving the problem.
UPD: If we have some version of quote-eval functions for the pure lambda-calculus, then there must be a function $eq$, which recognizes whether the quoted lambda-expressions are syntactically equal, and we can construct Is0 using $eq$. But I doubt that $eq$ is definable. The reason is "genericity lemma" (Barendregt book, lemma 14.3.24). If we were able to test equality on the quoted lambda-terms then ($eq$ (Quote $\Omega$) (Quote $\lambda x.x$)) would return $False$, and the genericity implies that ($eq$ (Quote $\lambda x.x$) (Quote $\lambda x.x$)) would also return $False$. Does that contradict a possibility of constructing Quote in the pure lambda-calculus?


texts: What is the difference between Lambda and Cramer's V / Pearson's C coefficient?

texts:
My textbook lists Cramer's V and Pearson's C as well as Goodman and Kruskal's Lambda as coefficient for measuring the association between nominal variables. It does not state the difference between Cramer's V/Person's C and Lambda explicitly or on what basis you'd want to use these different coefficients (with the exception that Lambda can be used for non-symmetrical which does not seem to be the case for Cramer's V and Pearson's C).
In SPSS, using a sample data file and calculating all three coefficient, I'm finding Cramer's V and Pearson's C do not differ from each other while Lambda (symmetrical) differs a large amount.
Am I correct in understanding that Cramer's V and Pearson's C measure the association between two variables, same as say Phi would for to dichotomous variables? If so, what does Lambda represent, and how in a sample data file can it differ substantially from the other two aforementioned coefficient?
Thanks for anyone in the know :-) I've tried searching online but having difficulty finding a clear answer on the difference and when to utilize these different coefficients.


texts: Efficient triangular decomposition of an integer

texts:
Euclidean division is an iterative process
that has been made super-efficient at the CPU level, right?
Its specification is that if I do (q, r) = f(n, d), I get super efficient result verifying that n = d * q + r with maximal q.
I need to perform a similar decomposition of an integer number, into the highest inferior triangular number and a remainder. In the same terms, this is (i, r) = g(n) verifying that n = i * (i + 1) / 2 + r with maximal i.
What's the way to go? What's the fastest I can get compared to euclidean division?


texts:
I have a nested function as follow:

def make_adder(n):
    def add(x):
        return x + n
    return add
>>> plus_3 = make_adder(3)
>>> plus_5 = make_adder(5)
>>> plus_3(4) 7
>>> plus_5(4) 9

What's the formal names of make_adder and add?
Can I call them 'outer function' and 'inner function'?


texts: Hessian-Free instead of LSTM for Recurrent Net Machine Translation

texts:
Last year, Ilya Sutskever and collaborators came out with a paper about a recurrent LSTM net that learns sequence to sequence mappings for machine translation. It's somewhat surprising that the authors used LSTM instead of Hessian-Free to train this net since the first author was one of the innovators behind the development of Hessian-Free methods for recurrent nets (citation).

I was wondering if anyone has tried Hessian-Free for learning sequence to sequence mappings for machine translation. If so, does it work? Is its performance inferior to LSTM's in some way?

Suggestions of other places to post this kind of question are welcome; although, the obvious place - metaoptimize - is currently so slow and spam-ridden I decided to try here first.


texts: Maximizing the sum of selected elements in a matrix

texts:
I’m trying to find an efficient algorithm for the following optimization problem:

Given a matrix $A$ with elements $a_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n<k$) such that the sum of the elements is maximized, subject to the constraint that any index of $a_{ij}$ is only used once. In other words: if element $a_{ij}$ has been selected, no other elements from rows and columns i and j can be selected.

Notes:
 - It is allowed to select elements from the diagonal.
 - The order of magnitude of $k$ is 10,000.

I have a dynamic programming algorithm but the downside is that it can't be parallelized.

The problem resembles the assignment problem. This can be solved using the Hungarian Algorithm, which can be easily parallelized using Java 8 streams. However, the assignment problem has the constraint that from each row and column only one element can be selected. This is less strict than above problem since it allows to select both $a_{ij}$ and $a_{ji}$.

Question: do you know how to adjust the Hungarian Problem for the stricter constraint?

Context:
This algorithm is used to optimize large-scale power storage, which can be modelled as a collection of spread options.


texts:
I am trying to find order of an bellow algorithm but I have no idea about, the problem like below

we have an array of $n$ element name $T[1...N]$ and we have that $0\leq T[i] \leq i$ and $T[i] \in \mathbb{Z}$ then if we have that $\sum_{i=1}^{n}T[i] = s$ what will be the order of following pseudo code

K := 1
for i = 1 to n do
    for j = 1 to T[i] do
        K := K + T[i]

I should prove it, but I just don't know what should I prove. is it $O(s)$ or $O(n+s)$ or $O(n)$ ? between these three one I need best guess. I just need some suggest to solve this. thanks

First I was thinking that it's $O(s)$ but if $T[i] = 0$ for $1 \leq i \leq n$ then then it should be $O(n)$. after that one of my friend said in fact $s = \frac{n (n + 1)}{2}$ so when we say that it's $O(s)$ in fact it's $O(n^2)$ so that the better answer is $O(s)$ because for some examples $O(n)$ is wrong, for example when $T[i] = i$ for all $i$. I think $O(s)$ should be right answer.


texts:
I want to write a constraint with ORs in a MILP. In particular, the following:

$$x \ge c \lor x \le -c \lor x=0,$$

where $c$ is just a real number.

Can anyone give me some hints?


texts: Is a function looking for subsequences of digits of $\pi$ computable?

texts:
How can it be decidable whether $\pi$ has some sequence of digits? inspired me to ask whether the following innocent-looking variation is computable:

$$f(n) = \begin{cases}
  1 & \text{if \(\bar n\) occurs in the decimal representation of \(\pi\)} \\
  0 & \text{otherwise} \\
\end{cases}$$

where $\bar n$ is the decimal representation of $n$ with no leading zeroes.

If the decimal expansion of $\pi$ contains all finite digit sequences (let's call this a universal number (in base 10)), then $f$ is the constant $1$. But this is an open mathematical question. If $\pi$ is not universal, does this mean that $f$ is uncomputable?


texts: how to prove that the diagonal language K is r.e

texts:
To prove that K= $\{x \mid \phi_x(x)$ halts and accepts$\}$ is r.e.:

we can recognize K by: for any x, we simply run x on machine $\phi_x$ and accept if the machine accpets else reject and that's it...

In general, for proving a set is r.e. , we must recognize every element IN the set? How do we deal with functions like
f(x)= 1 if x is in K and 0 if x is not in K? is f computable?


texts: Minimal DFA for language of all strings over $\{a,b\}$ whose penultimate symbol is $b$

texts: Design a minimum state deterministic finite automata for accepting those strings over the alphabet $\{a, b\}$ whose last but one symbol is $b$.


texts: Why researchers don't study the parameterizations of the problems unlikely to be NP-Hard?

texts: I have seen the parameterization of the very well known problems like vertex cover, hitting set etc which are NP-hard (NP-complete precisely). Many researchers in the past have been studied the parameterization of these problems. My question is why researcher's don't study the  parameterizations of the problems unlikely to be NP-Hard?


texts: Average-Case Analysis of a Simple Max-Finding Algorithm

texts:
Given this piece of code:

FindMax(L):
   k = len(L) - 1
   max = L[k]
   k = k - 1
   while(k >= 0):
      if(L[k] > max):
         max = L[k]
      k = k - 1
   return max

How would you go about computing the average-case complexity with respect to the number of times $max$ is assigned? The way I've been taught to approach a question like this is to partition the sample space into events that could represent all possible inputs. But I'm having a hard time deciding what that partition should be


texts: Context free grammar for nested arrays separated by commas

texts:
I have to define a context free grammar for the following rules:

(i) A pair of square bracket tokens [] surrounding zero or more values separated by commas.
(ii) A value can be another array or a number.

A number is represented by the token NUMBER. So for example, [NUMBER, [NUMBER, NUMBER], NUMBER]. is valid.

I am stuck as how to approach this.

My intuition is always to look at the question and see that S->LSQ VALUE RSQ, VALUE->VALUE COMMA VALUE | VALUE | ARRAY | e | NUMBER, ARRAY -> LSQ NUMBER RSQ, NUMBER ->NUMBER. But I know this slips up.

What steps can I take to ensure I am always thinking in the right way?


texts: Confused about the correctness proof of Dijkstra's algorithm

texts:
In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow:

  Let u be v's predecessor on a shortest path P:s->...->u->v from s to
  v. Then, If d(u) = δ(s,u) and edge (u, v) is relaxed, we have  d(v) =
  δ(s,v), where the funciton δ(x, y) denotes the minimum path weight
  from x to y.

I wonder why we need the condition d(u) = δ(s,u) in this lemma. If Path P: s->...->u->v is a shortest path from s to v, then by the property of optimal substructure, the subpath s->...->u of P must also be a shortest path from s to u. Therefore, d(u) must equal to δ(s,u).

Does there exist the case that d(u) ≠ δ(s,u) but P: s->...->u->v is a shortest from s to v? If it does, can someone offer an example here.

Any help will be appreciated

  PS: if you are interested in the entire proof. Check here, the proof starts at 45:30


texts: Finding cache block transfer time in a 3 level memory system

texts:
Following question was asked in one of entrance exams for a graduation programme. Please help me try to solve it :

A computer system has an L1 cache, an L2 cache, and a main memory
unity connected as shown below. The block size in L1 cache is 4 words.
The block size in L2 cache is 16 words. The memory access times are 2
nanoseconds, 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache
and main memory unit respectively.

When there is a miss in L1 cache and a hit in L2 cache, a block is
transferred from L2 cache to L1 cache. What is the time taken for this
transfer?

(A) 2 nanoseconds
(B) 20 nanoseconds
(C) 22 nanoseconds
(D) 88 nanoseconds

When there is a miss in both L1 cache and L2 cache, first a block
is transferred from main memory to L2 cache, and then a block is
transferred from L2 cache to L1 cache. What is the total time taken
for these transfers?

(A) 222 nanoseconds (B) 888 nanoseconds
(C) 902 nanoseconds (D) 968 nanoseconds

First thing that came to my mind was, how to calculate the transfer time using the given access time. During a miss, a block of data is moved from main memory to cache. Then CPU will access it. So, wouldn't be access time > transfer time ?
Then I thought, lets assume access time = transfer time & do the calculation.
Now first question. The question already states there is a miss in L1, so I will not consider L1 access time. Since there is a miss in L1 & hit in L2, a entire block from L2 has to be moved to L1. L2 block size is 16 words, but data bus size is 4 words.
So we have to move 4 words * 4 times.
To transfer 4 word it takes 20 ns. To transfer 4 words, its 80ns. Isn't it the time transferred from L2 to L1 ? The question does not say anything about accessing L1 after moving the data. But 80ns is not in the option !
Similar case with second question also.
Time to move main memory to L2 = 4 words * 4 times = 4 * 200 = 800ns
Time to move L2 to L1 = 80ns [earlier calculation]
So total time taken is 880ns. Which is again not in the option.
Either I am doing a very big mistake or options are wrong or question isn't framed correctly. If I am doing anything wrong, please give me some hint & I will try to work on this exercise again.


texts: How does a recurrent connection in a neural network work?

texts:
I am reading a very interesting paper on genetic algorithms which define neural networks.  I am familiar with how a feedforward neural network operates, but then I came across this:

Where node #4 goes back to connect to #5.  I was wondering how this is handled?  Does the state of node 4 get kept from the last timestep and applied to node 5 when it is time to calculate its activation?


texts:
I started reading the book "Data Structures and Network Algorithms" by Robert Tarjan, which is a classic (but a bit outdated - 1983) and I am a bit perplexed by the  paragraph in the first chapter, Page 3, first paragraph. I have attached the paragraph below:

  An important caveat concerning random-access and pointer machines is that if the machine can manipulate numbers of arbitrary size in constant time, it can perform hidden parallel computation by encoding several numbers into one. There are two ways to prevent this. Instead of counting each operation as one step (the uniform cost measure), we can charge for an operation a time proportional to the number of bits needed to represent the operands (the logarithmic cost measure). Alternatively we can limit the size of the integers we allow to those representable in a constant times log n bits, where n is a measure of the input size, and restrict the operations we allow on real numbers. We shall generally use the latter approach; all our algorithms are implementable on a random-access or pointer machine with integers of size at most n for some small constant c with only comparison, addition, and sometimes multiplication of input values allowed as operations on real numbers, with no clever encoding.

Would somebody be able to explain this paragraph or point me to some references that elaborates it better?


texts:
Let $\Sigma = \{0,1\}$, and suppose that $A$ is a regular language.
Define $$A' = \{ u \mid \exists a, b \in\Sigma: abu \in A\}$$ i.e., $A'$ is obtained from $A$ by taking every string in $A$ and removing its first 2 characters. Show that $A'$ is regular.

My solution so far is:

$ab \in \Sigma^*$ which is regular.
$A$ is a regular language
$abu ∈ A$, this means $u$ must be regular for all $abu \in A$ so $A'$ is regular.

Not sure if this makes sense, but please let me know if there's a better way, more formal.

Note: It's not an assignment, I'm just studying for my exam.


texts: How does this addition for Church numerals work with Y combinator?

texts:
I am currently preparing for an exam. In one of the old exams, you have to create a $\lambda$ expression $add$ that can add two church numerals. But the church numerals are not the usual ones, but defined like this:

\begin{align}
s_0 &= &\lambda x.\ x\\
s_1 &= &\langle c_{false}, s_0 \rangle\\
s_2 &= \langle c_{false}, s_1 \rangle &= \langle c_{false}, \langle c_{false}, s_0 \rangle \rangle\\
s_3 &= \langle c_{false}, s_2 \rangle &= \langle c_{false}, \langle c_{false}, \langle c_{false}, s_0 \rangle \rangle \rangle\\
\dots
\end{align}

where

\begin{align}
  \langle x, y \rangle &= \lambda p. \ p\ x\ y \text{ (pairs)}\\
  c_{true} &= \lambda t.\ \lambda f.\ t\\
  c_{false} &= \lambda t.\ \lambda f.\ f\\
  \text{succ} &= \lambda n. \langle c_{false}, n \rangle\\
  \text{pred} &= \lambda n.\ n\ c_{false}\\
  \text{isZero} &=  \lambda n.\ n\ c_{true}\\
  Y &= \lambda f.\ (\lambda x.\ f\ (x\ x))\ (\lambda x.\ f\ (x\ x))
\end{align}

The solution

They give the solution:

\begin{align}
  \text{Add} &= \lambda \text{add}.\ \lambda m.\ \lambda n.\ (\text{isZero } m)\ n\ (\text{succ }\ (\text{add}\ (\text{pred}\ m)\ n)\\
 \text{add} &= Y\ \text{Add}
\end{align}

Where $Y$ is the Y combinator.

Question

I don't understand this answer. I can't even exactly point out what I don't understand. One problem is certainly the Y combinator. Can somebody eventually break it down to easier pieces and explain it to me?

Eventually an example ($s_0 + s_0$, $s_1 + s_0$, $s_1 + s_1$, $s_2 + s_1$) would also help.

What I understand

I think I understood everthing above "the solution". So I understand that the number is simply how often you build pairs of $\lambda x.\ x$ and $c_{false}$. I understand that $succ$ only wraps its argument in another pair and $pred$ only returns the second part of such a pair.

Examples

0 + 0

\begin{align}
  0+0 &= \text{add } s_0\ s_0\\
 &= (Y\ Add)\ s_0\ s_0\\
 &= (\lambda f.\ (\lambda x.\ f\ (x\ x))\ (\lambda x.\ f\ (x\ x)))\ Add\ s_0\ s_0\\
 &= (\lambda x.\ Add\ (x\ x))\ (\lambda x.\ Add\ (x\ x))\ s_0\ s_0\\
 &= (Add\ ((\lambda x.\ Add\ (x\ x))\ (\lambda x.\ Add\ (x\ x))))\ s_0\ s_0
\end{align}

Is that correct? It seems to me as if I did something wrong there.


texts: How to prove that the pre-order tree traversal algorithm terminates?

texts:
I see structural induction the usual way for proving an algorithm's termination property, but it's not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that the pre-order tree traversal algorithm is terminable:

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left)
  preorder(node.right)

How should I prove?


texts: Is this a regular language + context free

texts:
Is $L_1 = \{0^n1^m0^{n+m}\mid m,n \geq 0\}$ regular? What is its context free grammar and proof?
Second, is the following language context-free?
$$L_2=\{0^a1^b2^c \mid a,b,c \geq 0 \text{ and } c = ab+1 \}$$
I am trying to prove this via the pumping lemma but am stuck. For CFG however, I have no idea. For the context-free language I tried applying CFL pumping lemma but am confused.


texts: A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

texts:
The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $M$ is "$1$" if $M_0$ will halt on $w_0$ and "$0$" if it will not.

From this statement only, it does not follow that there must be an ($M_0,w_0$) pair for which it is impossible to predict if $M_0(w_0)$ halts or not. It only means there is no general way to decide this question for all ($M_0,w_0$) pairs.

So my question is the following: Does there exist a ($M_0,w_0$) pair for which it is known that it is impossible to predict whether $M_0(w_0$) halts or not? If yes, is there a known example or construction for an ($M_0,w_0$) pair such that?


texts: Generating a random, dense set of points subject to proximity restrictions?

texts:
I recently read a paper about hyperuniform distributions, which mentioned that one way to generate a rectangle filled with hyperuniformly-distributed points is the following:

Choose a uniformly-random location in the rectangle.
If that location is not within distance $r$ of any previously-chosen point, add a new point at that location.
Repeat until all locations are within distance $r$ of a previously-chosen point.

It's not too hard to do this by sitting in a loop choosing random locations and comparing that location against every previously-chosen point, adding the location in if it isn't too close to anything else. We can speed up the test in part (2) by using something like an R-tree or a dynamically-rebuilt k-d tree.

However, I'm not sure how to answer the following questions:

How do we efficiently tell when every location in the rectangle is within $r$ units from some previously-chosen point? In other words, is there an efficient data structure for maintaining a rectangle and a set of circles in that rectangle in a way that efficiently answers queries of the form "is there an uncovered location in the rectangle?"
Is there an efficient way to uniformly sample from the free space in the rectangle other than doing rejection sampling? From the behavior I've seen with the programs I've written so far it's not at all uncommon for there to be just a tiny sliver of free space left in the rectangle that's extremely unlikely to be hit by choosing points in the rectangle uniformly at random and just hoping that we end up in it.

Thanks!


texts: How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits?

texts:
A shuffling algorithm is supposed to generate a random permutation of a given finite set. So, for a set of size $n$, a shuffling algorithm should return any of the $n!$ permutations of the set uniformly at random.

Also, conceptually, a randomized algorithm can be viewed as a deterministic algorithm of the input and some random seed. Let $S$ be any shuffling algorithm. On input $X$ of size $n$, its output is a function of the randomness it has read. To produce $n!$ different outputs, $S$ must have read at least $\log(n!) = \Omega(n \log n)$ bits of randomness. Hence, any shuffling algorithm must take $\Omega(n \log n)$ time.

On the other hand, the Fisher-Yates shuffle is widely believed to run in $O(n)$ time. Is there something wrong with my argument? If not, why is this belief so widespread?


texts: Is it possible to obtain a total function by composition of partial functions?

texts:
This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis:

  If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., $g_k$ by composition then $h$ is (partially) computable.

What I understand from this theorem is if there is at least one partial function among the composed function then $h$ is partial function. Am I right?

Here is an example, the functions $x$ and $x+y$ and $x.y$ are total but  $x-y$ is a partial function. it is possible to obtain $4x^2-2x$ by composition of these functions in the following way, this function is total but it is obtained from an non-total function ($x-y$).

$2x = x+x$

$4x^2 = (2x)(2x)$

$4x^2-2x$          composition of $x-y$

This is an example from the book, is this example a contradiction of the theorem?


texts: Is $2^{1+\sqrt{mn}}$ an upper bound for the size of the DFA resulting from the determinisation of n DFAs of size m

texts:
(all automata sizes are expressed in number of states in this question)

There exist NFAs of size $n$ for which the smallest DFA recognizing the same language is of size at least $2^n$.

Let $\Sigma$ be a vocabulary, and let's consider $n$ regular languages $L_i \subseteq \Sigma^*$ respectively recognized by $n$ DFAs $D_i=\{Q_i, q^0_i, F_i , \delta_i \}$ whose size are bounded by $m$.

We consider the epsilon-free NFA $N$ built by merging the $n$ DFAs such as $N=\{Q=\bigcup Q_i, q^0, F=\bigcup F_i , \delta \}$ where $\delta = \bigcup \delta_i$ with the additional constraint that $\forall \sigma \in \Sigma \, \delta(q^0, \sigma) = \{q |  \delta_i(q_i^0, \sigma)=q \,  \, 0 \leq i \leq n \}$ (note that in $N$ the $q^0_i$ are not anymore initial states since there is a unique initial state $q^0$).

Let $D_N$ be the DFA resulting from the powerset construction of $N$ and $D_N^M$ be the DFA resulting from the minimisation of $D_N$.

Is the size of $D_N^M$ at most $2^{1+\sqrt{mn}}$ ?

An equivalent question is : let $L \subseteq \Sigma^*$ be the language resulting from the union of the $n$ regular languages $L_i$, is the size of the smallest DFA recognizing $L$ always below $2^{1+\sqrt{mn}}$ ?

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

Many thanks, Luz


texts: Applicability of Dijkstra's algorithm to hypergraphs

texts:
When I search for Dijkstra's algorithm and hypergraphs, I don't get any results discussing it. The Wikipedia page regarding Dijkstra's algorithm doesn't mention hypergraphs and the one regarding hypergraphs doesn't mention Dijkstra's algorithm. When I search for shortest path algorithms for hypergraphs, I only get results with complicated algorithms.

But when I look at Dijkstra's algorithm, I can't seem to see anything in it where it uses the fact that each edge only connects two nodes.

Wikipedia states this pseudocode:

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                                    // Initialization
3
4      create vertex set Q
5
6      for each vertex v in Graph:
7          if v ≠ source
8              dist[v] ← INFINITY                          // Unknown distance from source to v
9              prev[v] ← UNDEFINED                         // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                              // The main loop
15         u ← Q.extract_min()                            // Remove and return best vertex
16         for each neighbor v of u:                      // only v that is still in Q
17             alt ← dist[u] + length(u, v)
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev

The only time this algorithm mentions connections is in line 16, where it says "for each neighbor v of u".

Could I simply use this algorithm for hypergraphs and only get correct results?


texts:
I have heard a term "procedural algorithm" before so I'm curious what would constitute a non-procedural algorithm? Are there any examples?

As far as I understand, there are maze generation algorithms that generate mazes procedurally - randomly or pseudo randomly using a seed value of some kind. The opposite of that would be making a maze manually by hand but that wouldn't equal to using an algorithm any longer so I'm a bit confused on this topic.

Any sources, links to examples are welcome.


texts: Is there a paper/implementation/tool on automatically finding/suggesting similar questions for a given question?

texts:
I would like to know whether there is a method to find similar questions for a given question, just like this stackexchange.com does.

Is there any paper or tools?
I tried keywords such as "deduplication" and "linking" but it was not successful.


texts: Why is a set of attributes X not a key if X → Y holds but there exists a strict subset V of X where V → Y?

texts:
Apologies if I butchered the question, I wasn't quite sure how to word it.

In the Ramakrishnan text (2nd edition) on page 423 (in the section on functional dependencies) this statement is made:

  If $X \rightarrow Y$ holds, where [$X$ is the set of key attributes and] $Y$ is the set of all attributes, and there is some subset $V$ of $X$ such that $V \rightarrow Y$ holds, then $X$ is a superkey; if $V$ is a strict subset of $X$, then $X$ is not a key.

I got the basic idea here (that if $X$ contains some $V$ where $V \rightarrow Y$ then $X$ is a key that contains a smaller key), but I must be misunderstanding something on the second case. Why isn't $X$ a key in the second case? It would seem that a strict subset would be a stronger case for being a "key within a key" which is how I understand a superkey to be structured.


texts:
I am new to graph theory and confused with ancestors definition in DAG(or in general graph).
For example in the following DAG

1--->2--->3<---4<---5

If I start DFS from 1 vertex first then path covered is 1--2--3. Then next if I start DFS from vertex 5,
then the path covered is 5--4. Vertex 3 is not visited again.  So visited order is 1 2 3 5 4.
What about the ancestors of 3. Are they only 1,2 or 4,5 also ?
what about ancestor Ancestor of 4. Is it only 5 or 1,2 also as they were also visited before visiting 5 ?


texts: Are there NP problems, not in P and not NP Complete?

texts:
Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete?  My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

If there is a problem that is $\mathsf{NP}$ (and not $\mathsf{P}$) but not $\mathsf{NP\text{-}complete}$, would this be a result of no existing  isomorphism between instances of that problem and the $\mathsf{NP\text{-}complete}$ set?  If this case, how would we know that the $\mathsf{NP}$ problem isn't 'harder' than what we currently identify as the $\mathsf{NP\text{-}complete}$ set?


texts: examples for languages of natural numbers

texts:
I need to find examples for language $L_i$  $i\in[1,3]$ of natural numbers that is:

$L_1\in$ $RE \backslash R$

$L_2\in$ $coRE\backslash R$

$L_3\in$ $\overline{ R \cup RE}$

My idea was in any case to take a language in the desired language class, and find some sort of function from the language to the natural numbers. But I do not know if this is the right way to approach the problem, and how exactly to find such function.


texts: How do computers synchronize their clocks with the standard time

texts:
I'd like to know how clock synchronization is done on computers, I've read this wikipedia article however it didn't give me exactly what I was looking for, I'll outline the problem I'd like answered:

My computer has the current time stored inside it which is maintained by a clock however this clock is subject to clock drift so it is nessisary to synchronize my computers time occasionally. Say my computer would like to do such a synchronization, then it would need to make a request to some time keeping server. This server would then respond to my computer with the correct time however there would be an inaccuracy due to the fact that the servers response would not be received immediately. My computer could attempt to estimate the travel time for the response however this is bound to be inaccurate. For this reason I suspect that GPS is used to synchronize time on computers. I'd imagine this is done by having the computer receive the time directly from the satellite and synchronize based on that.

I'd like to know if this is correct, if not, how is time synchronization done? Thanks


texts: The relationship between matrix inversion, the HHL algorithm, and the unlikely scenario that $BQP = PSPACE$

texts:
I am studying the quantum computing algorithm presented in the paper Quantum algorithm for linear systems of equations}.

Without going through all the details, the HHL algorithm is able to apply an inverted matrix to a normalized vector prepared in a quantum state in time complexity $\tilde{O}(\log(N)s^2\kappa^2/\epsilon)$, i.e. in order to solve $A |x \rangle = |b \rangle $, it computes an estimate $|x \rangle = A^{-1} | b \rangle$ where

$N$ is the dimension of the matrix

$s$ i the sparsity of the matrix

$\kappa$ is the condition number of the matrix

$\epsilon$ is the desired error bound

In an argument for the optimality of the algorithm the authors construct a reduction from a general quantum circuit to a matrix inversion problem with a proof (page 4).

Now here is where I get confused, the authors write:

  The reduction from a general quantum circuit to a matrix inversion problem also implies that our algorithm cannot be substantially improved (under standard assumptions). If the run-time could be made polylogarithmic in $\kappa$, then any
  problem solvable on $n$ qubits could be solved in poly(n) time (i.e. $BQP=PSPACE$), a highly unlikely possibility

Why does this imply that $BQP = PSPACE$? Any insights much appreciated.

Edit: later in the paper there is a bit more info that might help..

  Recall that the $TQBF$ (totally quantified Boolean formula satisfiability) problem is $PSPACE$-complete, meaning
  that any k-bit problem instance for any language in $PSPACE$ can be reduced to a $TQBF$ problem of length $n = poly(k)$. The formula can be solved in time $T ≤ 2^{2n}/18$, by exhaustive enumeration over the variables.

I would be happy to provide any additional info that one feels is missing from this question.


texts: Explaining eye tracking to 9-10 year olds

texts:
I was recently asked to explain eye tracking to 4th grade students and talk to them about its applications.

  What is eye tracking?

  An eye tracker is a device that uses projection patterns and optical
  sensors to gather data about gaze direction or eye movements with very
  high accuracy. Most eye trackers are based on the fundamental
  principle of corneal-reflection tracking:

I did not have time to prepare an activity, and I showed them some videos and they asked me questions. They got it, but I don't believe this is the best introduction.

I was thinking something along the lines of Christopher Bishop's Royal Institution Christmas Lectures with volunteers and physical objects.

How would you explain it to 9-10 year olds?


texts: Complexity of scalar operations for integers

texts:
I am currently studying the complexity of matrix multiplication and Wikipedia's article says "The matrix multiplication algorithm that results of the definition requires, in the worst case, n³ multiplications of scalars and (n−1)n² additions for computing the product of two square n×n matrices. Its computational complexity is therefore O(n³), in a model of computation for which the scalar operations require a constant time (in practice, this is the case for floating point numbers, but not for integers)."

I'd like to know why integers' scalar operations does not require constant time.


texts: Do problems in P have a minimum number of YES and NO instances?

texts:
If a decision problem A belongs to the polynomial complexity class P, must there be at least one YES instance and one NO instance of the problem? I know that in the definition of a Turing machine an accept state and separate reject state are defined but I'm not sure if that applies to this case. Is it maybe possible to have only YES instances or only NO instances?

Thanks very much in advance.


texts: Please suggest a good for mathematical section of studying cryptocurrency.


texts: Would it be feasible to use a breadth first search algorithm for finding a solution to the 3x3x3 rubiks cube?

texts:
I am trying to implement a rubiks cube solving program,and I am trying to figure out which algorithm to use,so far I have only come up with using breadth first search to find a shortest path from the initial configuration node to the solution node.
Each edge of the graph would be a 90 degree turn of a face of the rubiks cube(180 degree turns considered as 2 turns).
As for representing each configuration of the rubiks cube in a node I am thinking of using a 3x3x3 array of integers.Each element of the array would be an int from 1 to 6 representing each of the colours.
So if I used the Breadth First Search Algorithm for finding an optimal solution to the rubiks cube, would it run without taking up too much memory or too much time on an average computer?


texts: Not quite-infinitely expandable human-friendly naming system?

texts:
This may be a known problem, with known approaches, but I can't find the right way to search for it.

I would like to name points along a line of unknown final length such that their name reflects their relative position to all other named points on that line.  One should be able to insert an arbitrary number of names at any point along the line including outside the existing first and last named points. A lexicographical sort of the point names would always result in a list of points in a monotonic order.

An order of magnitude estimate of the total number of points to be ultimately named can be supplied up front

Additional restrictions:

Names must be stable, no-renaming after initial assignment
Names may be constructed from a limited character set: 25 lowercase letters a-z with 'L' removed.
The naming scheme should not require an extreme fan-out of name length when adding names either outside the existing points or between two adjacent points. E.g. Imagine that I want to add something before the name 'a', that wouldn't be possible while maintaining linear order during sorting.  Starting with 'b' only delays the issue.  Same for z on the other end.

Names should be of the shortest possible length such that a human could easily glance at one and then write it out elsewhere for most names.

It is highly likely that one would want to insert names between previously adjacent names, and then later between adjacent named points in that previous insertion.

The real-life use case for this is the creation of spatial names for all features of a given kind, say genes, in a species when we don't know in advance the total set of features.  This is because different individuals only contain a subset of the total sequence space that the whole population of organisms encompass.  The problem is easy to solve with static sets of sequences, but not if you allow them to expand at any point along the line (chromosomes) with the addition of new information.  The set sizes of interest encompass 10^5 -10^7 items.


texts: Dynamic programming algorithm with an O(n) performance that will give the optimal solution

texts: I am currently learning the dynamic substructure and optimal solution for the coin change-making, and one of the questions given from my teacher is to describe an overall O(n) dynamic programming algorithm that will give the optimal solution and why is it O(n)? Can anyone help me to understand the question? Thank you!


texts: Expression Problem: Why are simple parameterized types a non-solution?

texts:
I'm studying the expression problem at the moment and it seems like I'm missing something. I used a data-centered approach (i.e. OOP) as the basic setup and then introduced two type variables, one for each operand in Add. These type variables are bounded to subtypes of Exp - this constraint is further narrowed down, when a new operation is added. For example in Java this would look like this:

interface Exp {
    int eval();
}

class Lit implements Exp {
    int value;

    public Lit(int value) {
        this.value = value;
    }

    @Override
    public int eval() {
        return this.value;
    }
}

class Add<T extends Exp, U extends Exp> implements Exp {
    public T e1;
    public U e2;

    public Add(T e1, U e2) {
        this.e1 = e1;
        this.e2 = e2;
    }

    @Override
    public int eval() {
        return this.e1.eval() + this.e2.eval();
    }
}

interface ExpP extends Exp {
    String print();
}

class LitP extends Lit implements ExpP {
    LitP(int value) {
        super(value);
    }

    @Override
    public String print() {
        return "" + this.value;
    }
}

class AddP<T extends ExpP, U extends ExpP> extends Add<T, U> implements ExpP {
    AddP(T e1, U e2) {
        super(e1, e2);
    }

    @Override
    public String print() {
        return this.e1.print() + " + " + this.e2.print();
    }
}

public class Main {
    public static void main(String[] args) {
        ExpP add2to3 = new AddP<>(new LitP(2), new LitP(3));
        System.out.println(add2to3.print() + " = " + add2to3.eval());
    }
}

Now, type parameterization is a very obvious and simple approach, so there must be something wrong with it. Which requirement does this (non-)solution violate?

I'm aware of correct solutions like The Expression Problem, Trivially! and The Expression Problem Revisited, which are similar in structure. I merely strive for a better understanding of the topic.


texts: Context-free grammar for $\{ a^n b^m a^{n+m} \}$

texts:
I've got a problem with this task. I should declare a context-free grammar for this language:

$\qquad \displaystyle L := \{\, a^nb^ma^{n+m} : n,m \in \mathbb{N}\,\}$

My idea is: We need a start symbol, for example $S$. I know that I can generate the first $a$ and the last $a$ by $S \to a a$. I don't know what is the next idea to solve this task.


texts:
If there is a way to identify if two sets of points can be separated by a line?

  We have two sets of points $A$ and $B$ if there is a line that separates $A$ and $B$ such that all points of $A$ and only $A$ on the one side of the line, and all points of $B$ and only $B$ on the other side.

The most naive algorithm I came up with is building convex polygon for $A$ and $B$ and test them for intersection. It looks time the time complexity for this should be $O(n\log h)$ as for constructing a convex polygon. Actually I am not expecting any improvements in time complexity, I am not sure it can be improved at all. But al least there should be a more beautiful way to determine if there is such a line.


texts: Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))

texts:
Suppose I have an algorithm whose running time is
 $O(f(n))$ where $f(n) = O\left(\frac{\log n}{\log\log n}\right)$

And suppose I can change this running time in $O(1)$ steps into $O\left(f\left(\frac{n}{f(n)}\right)\right)$, i.e. I can get an algorithm whose running time is $O(g(n)) = O\left(\frac{\log\frac{n}{\frac{\log n}{\log\log n}}} {\log\log\frac{n}{\frac{\log n}{\log\log n}}}\right) = O\left(\frac{\log\frac{n\log\log n}{\log n}} {\log\log\frac{n\log\log n}{\log n}}\right)$.

I'm pretty sure that $g(n) < f(n)$ for big enough $n$ (by using wolfram alpha) but wasn't able to prove it.

My questions are:

Is $g(n) < f(n)$ in fact true (starting from some n)?
Is $g(n)$ asymptotically better the $f(n)$, i.e. is $g(n) = o(f(n))$
Assuming this is asymptotically better, I can do this step again and further improve the running time of the algorithm. Meaning that in 1 more step I can make my algorithm run in time of $O\left(\frac{n}{f\left(\frac{n}{f(n)}\right)}\right)$, and I can repeat this process as many times as I want. How many times should the process be repeated to get the best asymptotically running times and what will it be? obviously repeating it $O(f(n))$ times will already have a running time of $O(f(n))$ only for the repetition of this process and will not improve the overall algorithm complexity.


texts: Why is the running time of edit distance with memoization $O(mn)$?

texts:
I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with height $\max\,\{m,n\}$, m and n being lengths of two given strings.

However I am not getting why it is $O(mn)$ after memoization. Can someone please help me understand this?

I also know that, in the case of dynamic programming, the complexity will be number of distinct sub-problems we solve (because we save the solution of subproblems).

How do I calculate distinct sub-problems I am solving in Edit Distance.

P.S. I am not asking here for tabulation approach (top-down method) or explanation int the form of tabulation approach. This question on Stack Overflow contains the code of Edit Distance with memoization.


texts:
I am working on a problem of whose complexity is unknown.
By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use.

Finally, I have decided to go for the most primitive method -- Turing Machines.

Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here).

So, assuming that there are no problems to perform an NP-hardness reduction, how does one prove that a problem is NP-hard? Are there any publications that does this?

I also want to add that I know how to perform an NP-hardness reduction. However, the problem that I am tackling is a "localized" geometric problem, that it does not allow me to model any given instance of 3SAT, 3-coloring, vertex cover, etc.

The immediate question comes to mind: "what if the problem is polynomial time solvable?"
Well, that is also a possibility, but I want to exhaust everything before I move onto designing an algorithm.


texts: Meaning of Free (Arbitrary Abstract Algebra Term)

texts: I'm currently learning abstract algebra and the word free appears (free monoid, free vector space) throughout different literatures. Is there a general (and simple) definition of the word (and possibly examples in functional programming) or is it merely a highly overloaded word? Many Thanks!


texts: Cannot understand reductions from the halting problem and its complement

texts:
When I was going through the reductions from $HP$ and $\overline{HP}$ in this handout, I do not understand how everywhere the following claim is made: $$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt on x} ⇒ M′ \text{ does not accept any strings} ⇒ L(M′)\text{ is finite} ⇒ M′ \in L_5.$$ Why does $M$ not halting on $x$ imply that $M'$ does not accept any string at all?
My understanding initially was that $M'$ is a non-deterministic Turing machine that simultaneously runs $M$ on all possible inputs, but that doesn't seem right. Can someone please take a few examples, $(L_3, L_4, L_5$ if possible) and explain how the reductions are performed?
Also, I do not understand what $\tau(⟨M,x⟩) = ⟨M'⟩$ means.
I do understand how reductions are done after reading a few pages from Sipser. I still don't understand how they're done in the linked handout though. If anyone can even comment on what book uses the same notation or the reduction procedure as the handout, it would be of a lot help!


texts:
I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases.

Let $G$ be a directed graph and $u \in V(G)$.

We want to prove that $  BFS(G,u) = DFS(G,u)$.

$\text{BASE CASE}$

$V(G) = \{u\}$

$BFS(G, u) = \{u\} \quad DFS(G,u) = \{u\}$

$BFS(G,u) = DFS(G,u) \quad Qed.$

$\text{INDUCTIVE HYPOTHESIS}$

$BFS(G,u) = DFS(G,u) \;\;\forall G, u \in V(G)$.

$\text{INDUCTIVE STEP}$

$(i)\;G' = (V(G) \cup\{v\}, E(G))$

We know that $BFS(G',u) = BFS(G,u)$ if $u \ne v$ (and so does $DFS$), because $v$ is disjoint from the rest of the graph, and so the proof follows from the hypothesis.

But if $u = v$ ?

$(ii)\;G' = (V(G), E(G) \cup (v,w)) \quad v,w \in V(G)$

How can I use the hypothesis here?


texts: Is structural induction on terms applicable when a function is involved?

texts:
Assume an evaluation-relation on terms $t \Downarrow v$. If I want to prove correctness of a function $\phi$ w.r.t. evaluation, I have to show that the following implication always holds:

$$\frac{\phi(t) \Downarrow \phi(v)}{t \Downarrow v}$$

Naturally, this is a candidate for structural induction. But on what structure? Is it sufficient to run the induction over terms, or do I have to run it over the derivation tree? Structural induction is usually only allowed for direct sub-terms, but the function could, in principle, yield completely different results.

Is it sensible to consider $\phi$ part of the promise or do I have to consider it a part of the recursive structure?


texts: In ID3 algorithm, which attribute to choose if information gains are equal?

texts: In the ID3 algorithm for building a decision tree, you pick which attribute to branch off on by calculating the information gain. What happens if the calculated information gain is equal for two different attributes? Can you choose either attribute as the new branch?


texts:
I am currently working on an algorithm that will help to improve shaken blurry images. I know there are plenty of them, such as deconvolution, that is pretty useful though I don't really know how to "cook" such things.

My current objective is to restore the shaken trajectory and then do some kind of deblurring. (blind deconvolution)

What algorithms considered the best in this area? What standard implementations exist?


texts:
I've searched online for this but I only seem to find answers for a similar equation:

T(n) = T(n/3) + T(2n/3) + cn

But the one I'm trying to solve is:

T(n) = T(n/3) + T(2n/3)

Base case: We can assume T(a) = Theta(1) for any constant a.

I've succeeded in proving (by induction) that T(n) = O(n*log(n)). I thought the answer should be Theta(n*log(n)), but I cannot prove that T(n) = Omega(n*log(n)).

So my question is - am I correct that the answer is O(n*log(n)), and NOT Theta(n*log(n))? IF that's true that would really be great...

If I'm wrong I will of course explain where I'm stuck in the induction process...

Thanks!

P.S. If you need to, please try to explain using induction, because I haven't learned all methods for solving these problems yet.


texts: Practical applications of the palindromic substring problem?

texts:
The longest palindromic substring problem is certainly an interesting intellectual exercise, and seems to be popular in coding interviews in industry. As an interesting puzzle, its popularity for interviews is not too hard to understand--it's not too hard to find an $O(N^2)$ solution, and if someone manages to come up with a linear time solution, they're probably either a genius or at least well-read, which is arguably as valuable.

Given the apparent frivolity of the problem, however, it seems like a surprising amount of effort has gone in to analyzing it. There are at least three published linear-time solutions (by Manacher, Jeuring, and Gusfield). But, is it actually useful for anything? Are there other problems in which finding a palindromic substring is a necessary step? And in the absence of a direct application, did any of the known solutions to this problem reveal new techniques that have been applicable elsewhere?


texts: How is the (local) clustering coefficient defined for vertices with degree 1

texts:
We want to compute the clustering coefficient $C$ for an undirected graph $G = (V, E)$.

The clustering coefficient $C$ for a graph $G$ is the average over all local clustering coefficients $C_i$, whereby $C_i$ is the local clustering coefficient of a vertex $v_i$ such that $i$ is a generic index and $v_i$ is a member of the network, i.e. $v_i \in V$.

The local clustering coefficient $C_i$ is defined as the ratio between the number of existing edges within the neighborhood of a vertex and the number of possible edges within the neighborhood of a vertex. Therefore, $C_i = \frac{2n}{k_i (k_i -1)}$, such that $n$ is the number of edges within the neighborhood of vertex $v_i$ and $k_i$ is the degree of vertex $v_i$.

For vertices with $k_i = 1$, the denominator becomes $0$ and the whole term becomes undefined.

Given that the clustering coefficient is the ratio between the number of possible edges in the neighborhood of a vertex and the actual number of edges, a vertex with $k_i = 1$ cannot have any edges within its neighborhood, as there no such neighborhood. Hence, is it reasonable to use $C_i = 0$ in cases where $k_i = 1$?


texts: Is there a formalization of the computational model for quantum computers?

texts:
There are several equivalent computation models, each capable of simulating each other. For example, the lambda calculus or the SKI calculus which are based on rewriting, Cardelli's object calculus, Hoare's communicating sequential processes, and of course the universal Turing machine, all of them formally defined.

I do understand that though there are possibly different ways of building quantum computers, the ways we build them today are Turing-complete and equivalent to the other models of computation. My question is: have anyone formalized a mathematical computation model for a quantum computer (such as the D-Wave)? (As the other models, I assume this could be used as a programming language.)

(I do understand that a possible answer would be "the quantum mechanics", but that's not exactly what I'm looking for...)


texts:
Is there a way to take the interection of two NPDAs?

I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.


texts: Workflow of the Naive Surface Nets algorithm

texts:
I'm trying to understand the Naive Surface Nets algorithm which is related to surface generation out of Voxels. I've learned of it here

So far I understood that the naive surface nets algorithm calculates the "optimal" edge crossings for a given input. Problem is that I don't understand how it's supposed to calculate the edge crossings compared to the marching cubes algorithm. If the input data is represented in binary values (only one and zero) like for marching cubes algorithm shouldn't the computation of the edge crossings have the same results?

I suppose a step by step showcase of what the algorithm does for aquiring the surface of 2D sample voxels data would help me a lot understanding it.
For example for this data the marching cubes algorithm gives as result the image show below (the lines). Would the naive surface nets algorithm return the same result?

Where red stands for binary 1 and blue for binary 0 asuming each voxel has the same space between each other (as always I think).


texts: Preferring forward edges to cross edges during graph DFS traversal

texts:
It's well known that depth-first search order of a graph is (usually) not unique, and multiple orders are possible depending on the order in which successors are processed for each node. Let's consider rooted directed graphs in the following discussion.

Muchnick 1997 gives an example:
.

Intuitively, DFS with (more) forward edges is "better"/"more useful" than one with (more) cross edges. Is there a methodology/algorithm for ordering successor selection to construct such DFS spanning trees (like (b) in the example above)? (Of course, an algorithm better than generating all possible DFS trees in exponential time and then selecting "the best".)


texts: Computer Architecture: How to determine the bits of the address used to access the cache?

texts:
Given a non-associative, direct-mapped cache and its cache capacity, block size, and address size, how would I go about determining what bits of the address are used to access to cache? Is there a generalized formula?
If there is a generalized formula, how would that formula change or stay the same for an X-way set associative cache?


texts: Indexed family of all unary partial computable functions

texts:
Please help prove the following statement:

  The indexed family of all unary partial computable functions that have total computable extension is computable.

Definitions:

Total function - a function which is defined for all inputs of the right type, that is, for all of a domain.
A function $g$ is called an extension of the partial function $f$ if $\operatorname{Dom}(f) ⊆ \operatorname{Dom}(g)$ and $g(x) = f(x)$ for any $x \in \operatorname{Dom}(f)$, where $\operatorname{Dom}(f)$ is the domain of the function.
Let $S$ be nonempty countable set (possibly finite). Any surjective map $\nu\colon \omega \twoheadrightarrow S$ from the set $\omega$ of natural numbers onto the set $S$ is called an enumeration .
An indexed family of functions is called computable if it has at least one computable enumeration.

Additional information:

The indexed family of all unary computable functions is not computable.


texts: Explain the process of formation of word senses in WordNet

texts:
Regarding the word sense disambiguation problem, read the following fact  written on Knowledge-based Word Sense Disambiguation using Topic Models:

  Note that although WordNet is the most widely used sense repository, the sense distinctions can be too ﬁne-grained in many scenarios. This makes it difﬁcult for expert annotators to agree on a correct sense, resulting in a very low inter-annotator agreement (72%) in standard WSD datasets.

I would like to understand better the process of assignment of a sense to a word but there is no detailed explanation at the web.

Can somebody here give some examples of cases which are hard to find a sense using WordNet?


texts: give potential function - binary heap - extract-min in amortized const time and insert in log amortized time

texts:
Consider an ordinary binary min-heap data structure with n elements supporting
the instructions INSERT and EXTRACT-MIN in O($\lg n)$ worst-case time. Give a
potential function $\Phi$ such that the amortized cost of INSERT is $O(\lg n)$ and the amortized cost of EXTRACT-MIN is $O(1)$.

I try to solve it, but I got in stuck:

Attempt
Let $c_i$ denotes real cost of $i-th$ operation, and $a_i$ denotes amortized cost.
Let $\Phi(D_i) = \text{number of elements after i operations}$
INSERT:$$a_i=c_i+ \Phi(D_i) - \Phi(D_{i-1}) \le \log(i) + (i)\log(i) - (i-1)\log(i-1) \le 3\log(i+1) = O(\log(i))$$
EXCTRACT-MIN:$$
a_i=c_i + \Phi(D_i) - \Phi(D_{i-1}) \le \log(i) + i\log(i) - (i+1)\log(i+1) =\log(i) + i\log(i) - i\log(i+1) - \log(i+1) < 0
$$

As you can see, my problem is that I get number lower than $0$. Can you help me ?


texts:
The AND function in the lambda is:

and = (λ a. λ b. a b F)

I have following expression:

and T T

then the result will become T and I am asking me why?

When I do the beta reduction, then I understand, why I've got T:

(λ a . λ b . a b (λ x . λ y . y)) (λ x . λ y . x) (λ x . λ y . x)
(λ b . a b (λ x . λ y . y))[a →(λ x . λ y . x)] (λ x . λ y . x)
(λ b . (λ x . λ y . x) b (λ x . λ y . y)) (λ x . λ y . x)
((λ x . λ y . x) b (λ x . λ y . y))[b→(λ x . λ y . x)]
(λ x . λ y . x) (λ x . λ y . x) (λ x . λ y . y)
(λ y . x)[x →(λ x . λ y . x)] (λ x . λ y . y)
(λ y . (λ x . λ y . x)) (λ x . λ y . y)
(λ x . λ y . x)[y→(λ x . λ y . y)]
(λ x . λ y . x)
T

But when I shortened it like:

T T F

then I've got F, because:

T T F
T F
F

What am I interpreting wrong?


texts: What is the significance of the imaginary parts in the output of an Inverse Fourier Transform? Can I avoid them?

texts:
Starting with an image, I have taken its fourier transform and then modified it, and finally taken the inverse fourier transform of the modified fourier transform to get my resulting image.  In my result, I get a lot of very small imaginary components in each pixel.  My question is what causes these, and is there some insight into how I can play with a fourier transform in such a way that I won't get these imaginary components once I invert the transform at the end?

The reason this is an issue for me is because although I can simply zero out the imaginary components, or take the magnitude of each complex number as the pixel value and still obtain the resulting image that I desire, once I take the fourier transform of that new image, it does not yield the fourier transform that I used to generate the image previously.  Because the English is getting messy, it's much easier to see in pseudocode:

function fft(input):
   return 2D fourier transform of input 2D array

function ifft(input):
   return 2D inverse fourier transform of input 2D array

function fix(image):
   zero out imaginary component in each pixel of input image (2D array)
   return updated image

// Suppose we have computed an input 2D matrix, and are ready to ifft it to get an image
input = /*...*/
test1 = fft(ifft(input))
test2 = fft(fix(ifft(input)))

While test1 will yield back the matrix (up to floating point errors) input that we started with, the image generated is not a real image.  If we attempt to fix the image, we find that test2 significantly differs from our input.

What I would like to do is understand how to modify the fourier transform in such a way that I can achieve my original input after going through the process of taking the inverse fourier transform, storing that as a valid image, and then taking the fourier transform of that image.


texts: How does software detect if an interrupt has occurred if it cannot set it's own interrupt handlers?

texts:
I'm currently working on designing a relatively simple processor using a custom ISA .
It will use interrupts for I/O .

From what i know , once the interrupt controller issues an interrupt , the processor acknowledges it and set it's PC to the IVT , from where it executes the relevant interrupt handler , which specifies what the CPU does .

These interrupt handlers are set by the OS and cannot be modified by the user-mode process.

My question is this : how does the process know when an interrupt has occurred ? the cpu might execute the handler and place the acquired controller data in a memory location , but how is the application notified ? what are the common methods of doing this ?

For example , say i have a platform game ; when i press the assigned jump key , the cpu will acquire the keyboard data , but how does it go from there to actually making the sprite jump in a video game ? does the app still have to check for controller input at regular intervals ?


texts: Event Prediction through Machine Learning

texts:
I have a large data set consisting of ca. 40 categorical data items and a few interval data items (real numbers, less than 5 such items). Most categories should have a lot of values that repeat themselves over and over, and very few that appear very rarely. Some categories are also overcategories of others (like country and city). The outcome of each data is either 1 if the event occurred, or 0 if it did not occur.

The idea is to calibrate a machine learning model or a statistical model that can predict for every given data row the probability that the outcome is 1. The data set I will use will have at least 1 million rows.

Which machine learning approaches and statistical models will perform well on such a task? My initial thoughts are logarithmic regression and support vector machines (with extensions like random forest).

How do I deal with the interval data items? The easiest approach is obviously to convert different ranges into categories, which I think will not be a problem.

What libraries and tools can I use when my data set has a size of 10 GB? I am interested in tools/libraries that include machine learning algorithms but also statistical tools to help me find attributes with significant influence on the outcome. I can code in Java and C++ at the moment. I looked into Root, a data analysis tool from CERN for large data sets, and its machine learning module TMVA, but it can only handle real numbers and integers as input as far as I know.


texts: Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

texts:
$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known exact algorithm that solves $3$-$\mathrm{Partition}$.

Is there a fast (e.g subexponential) algorithm for $3$-$\mathrm{Partition}$? Is it possible to solve it faster than using SAT solvers?


texts: Can SSL be hacked if we know some of plain data?

texts:
As I know, SSL/HTTPS is two stage, first stage is public key encryption/decryption which transfers key of the second stage which is symmetric. It is true we don't have key, but we can have some of plain data and guess key so (at least some of messages), do you agree it is possible so?

Thanks!


texts: How to find the shortest path from some vertex in set $S$ to set $S'$

texts:
If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That is, we are looking for a shortest path among all $S$-$S'$ paths. We can also assume all edge weights are positive.

Here is how I have approached this problem so far:

I already have the distance matrix information $(d)$ for graph $G$ which was calculated by applying the Floyd-Warshall algorithm in a previous operation.

I then iterate over all vertices in $S$ for each vertex in $S'$ and find the pair $(s_1,s_2)$ with the smallest value in matrix $d$.

Dijkstra's algorithm is then used to calculate the shortest path between $s_1$ and $s_2$, so connecting vertex sets $S$ and $S'$.

Is there a more efficient way of achieving this same outcome?


texts:
It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary in C#, etc.)

Having just covered (a,b), red-black & AVL trees in my algorithms class, here's what I got out (also from asking around professors, looking through a few books and googling a bit):

AVL trees have smaller average depth than red-black trees, and thus searching for a value in AVL tree is consistently faster.
Red-black trees make less structural changes to balance themselves than AVL trees, which could make them potentially faster for insert/delete. I'm saying potentially, because this would depend on the cost of the structural change to the tree, as this will depend a lot on the runtime and implemntation (might also be completely different in a functional language when the tree is immutable?)

There are many benchmarks online that compare AVL and Red-black trees, but what struck me is that my professor basically said, that usually you'd do one of two things:

Either you don't really care that much about performance, in which case the 10-20% difference of AVL vs Red-black in most cases won't matter at all.
Or you really care about performance, in which you case you'd ditch both AVL and Red-black trees, and go with B-trees, which can be tweaked to work much better (or (a,b)-trees, I'm gonna put all of those in one basket.)

The reason for that is because a B-tree stores data more compactly in memory (one node contains many values) there will be much fewer cache misses. You could also tweak the implementation based on the use case, and make the order of the B-tree depend on the CPU cache size, etc.

The problem is that I can't find almost any source that would analyze real life usage of different implementations of search trees on real modern hardware. I've looked through many books on algorithms and haven't found anything that would compare different tree variants together, other than showing that one has smaller average depth than the other one (which doesn't really say much of how the tree will behave in real programs.)

That being said, is there a particular reason why Red-black trees are being used everywhere, when based on what is said above, B-trees should be outperforming them? (as the only benchmark I could find also shows http://lh3lh3.users.sourceforge.net/udb.shtml, but it might just be a matter of the specific implementation). Or is the reason why everyone uses Red-black trees because they're rather easy to implement, or to put it in different words, hard to implement poorly?

Also, how does this change when one moves to the realm of functional languages? It seems that both Clojure and Scala use Hash array mapped tries, where Clojure uses a branching factor of 32.


texts: How do I prove that EQTM ={: L(M1) =L(M2)} is undecidable (assume that M1 and M2 are encodings of TMs)

texts:
I am trying to revise for an exam, I have encountered this question and have seen an example solution, but it was provided by my lecturer, and it was fairly sparse and somewhat incomplete.

She jumps straight into a proof that has very little context, then ends it with "see Theorem 5.2" and that is why it is undecidable which is from a textbook none of the students actually purchased because we were told everything we need will be in the slides.

I know that I should approach this by using reduction, but from what I can barely understand this is a very basic reduction type proof, which I was hoping to understand to tackle harder questions.

If possible can this be explained to me in detail? Thanks.


texts: Computational complexity of numerically estimating the roots of a polynomial

texts:
The Wikipedia article on finding the roots of polynomials mentions all sorts of methods to do so. But it doesn't give, nor can one easily figure out by following the links, known lower and upper bounds on time complexity in various models (and which approaches achieve them).

So, if we're given the $n$ real coefficients of a degree $n-1$ univariate polynomial - each of them as a floating point value with $m$ mantissa digits and $p$ exponent digits - what's the time complexity for a random-access machine to compute all of its real + imaginary roots to within $\delta$ of their actual values? How much for just the real roots?

Note:

this goes some of the way to relate coefficient complexity measures to search space size.
If you'd rather answer for a slightly different formalization of the problem, that's fine too.
The "best bound I know personally is XYZ" is also a useful answer.
Do not assume the roots are distinct or all real.


texts: What is the difference between "use case" and "function"?

texts: In the use case diagram, we draw use cases as an ellipse. Are the use cases the same as functions? I mean by functions, those functions which we write in the program.Thank you in advance.


texts: Minimum vertex-weight directed spanning tree where the weight function depends on the tree

texts:
Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$.

The weight function assigns a non-negative weight to each node, which depends on the node's ancestors in $T$.  Specifically, for some fixed sets of nodes $S_1, S_2, \dots, S_k \subseteq V$, the weight of node $v$ is the number of sets $S_i$ that contain $v$ and all its ancestors in $T$.

Any suggestion how to approach this problem?


texts: retrieve file format from unknown binary file

texts:
Is it possible, somehow, maybe by using some kind of brute force algorithm, to try and figure out what kind of file one is dealing with when one only has the raw binary without file format or meta information at all ?

If one wold use a tool such as Hopper Disassembler, how would one go about figuring out what kind of file one is dealing with?


texts: How does the problem of "Scheduling to Minimize Lateness" exhibit optimal substructure?

texts:
The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos):

Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ jobs, their processing time $t_1, t_2, \ldots, t_n$ and deadlines $d_1, d_2, \ldots, d_n$. We assume that all jobs were available to start at the common start time $0$.
Output: A schedule of these jobs to minimize their maximum lateness.
Suppose a job $J_i$ is scheduled at time $s_i$, then its lateness is defined to be $l_i = s_i + t_i - d_i$ (it is $0$ if $s_i + t_i \le d_i$.)

It is known that this problem can be solved by a greedy algorithm which schedules the jobs in the non-decreasing order of their deadlines.

I am confused about its optimal substructure property (not explicitly described in the book).
Let $L(s, S)$ be the optimal lateness obtainable from scheduling the jobs in $S$ which are available to start at the common start time $s$.
On the one hand, by enumerating over the possible first jobs to schedule, we get the following recurrence:
$$L(s, S) = \min_{1 \le i \le n} \Big(\max\big(L(0, \{J_i\}), L(t_i, J \setminus \{J_i\})\big)\Big).$$
Intuitively, this problem exhibits optimal substructure.
On the other hand, it seems that the problem does not exhibit optimal substructure with respect to the form of subproblems defined above.
To illustrate this, consider three jobs $J = \{J_1, J_2, J_3\}$ with processing time $t_1 = 6, t_2 = 2, t_3 = 2$ and deadlines $d_1 = 2, d_2 = 7, d_3 = 8$. An optimal solution is to schedule $J_1, J_3, J_2$ in that order, producing a maximum lateness of $4$. However, this optimal solution does not contain the optimal solution to the subproblem of scheduling $\{J_2, J_3\}$ given the common start time $t_1 = 6$, which is $L(6, \{J_2, J_3\}) = 2$ by scheduling $J_2, J_3$ in that order.
This contradicts the "definition" of the optimal substructure property given in CLRS (Sections $15.3$ and $16.2$; 3rd edition):

A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.

Problem: How does the problem exhibit optimal substructure?


texts: Meaning of "pushing x down" and "pulling x up" in database query handling

texts:
In this book there is a lot of mention of "pushing x down". For example:

  Pushing NOT operations down and eliminating them

  NOT operations need to be pushed downwards for correctness reasons. Attention has to be paid to the IS NOT NULL and IS NULL predicates. XXX complete set of rules go into some table

  ...

  Typical steps during this rewrite phase are unnesting nested
  queries, pushing selections down, and introducing index structures.

  ...

  When pushing down projections, we only apply them just before a pipeline breaker

  ...

  Logical query optimization turned out to be a little difficult: pushing selections down and reordering joins are mutually interdependent.

  ...

  In this section, we consider pushing down (pulling up) unary operators into (from) the arguments of binary operators. Thus, we are interested in equivalences of the form $f(e_1 ◦ e_2) ≡ f(e_1) ◦ e_2$ and $f(e_1 ◦ e_2) ≡ e_1 ◦ f(e_2)$.

From that last example I can vaguely see that e.g. $f(e_1 ◦ e_2) ≡ f(e_1) ◦ e_2$ there is a "moving out" of $e_2$ from the equation, but I'm not sure what direction up/down and not sure what the meaning/purpose is in doing this. Wondering what exactly this means.