texts: How to optimize a function by maximizing 1 variable and minimizing another?

texts:
Problem

I want to implement an optimization algorithm for my file transfer program.

The program buffers data in a local file before uploading to central server periodically and it compresses the files before transferring.

I would want the program to intelligently predict the time and size thresholds before transferring.

The objective function could be defined as following

f(u) = theta1*u + (theta2*u)/b + theta3

where

u is the size of data
b is the network bandwidth (bps)
f(u) is the time taken to transfer u bytes of data.
theta1*u refers to amount of time taken to compress u bytes of data
theta2*u*b refers to time taken to transfer compressed data.
theta3 is constant protocol overhead

I want to be able to optimize the transfer by minimizing time and maximizing uncompressed size.
If I were to simply minimize f(u) that would have been easy but then in this particular case , I would also want to maximize amount of data to be transferred.
The idea is to be able to come up with a machine learning algorithm which can change as per different network scenarios and fluctuating bandwidth , rather than user providing it at start of program.

Of course, I would implement it with some sane seed values and keep them within sane boundaries.

Solution space

Given the nature of this problem , which class of algorithms should I be looking into? Would gradient descent be the right way to approach this? is it possible to apply maximize and minimization on same function of 2 different variables? Am I over-thinking this ?


texts: When did our current concepts of program modularity develop?

texts:
I take it that the concept of a modular subroutine call/return existed prior to the concept of a call stack (and hence to the possibility of recursive subroutines or of recursion limits). I would guess that reentrant routines were conceived prior to preemptive multitasking (perhaps in the context of recursion or of hardware interrupt events). I expect some of these related concepts (like the notion of function arguments and return values, and local variable scopes) would have developed in concert with early high-level languages, although some would also be reflected in the evolution of different hardware instruction sets.

Does anyone know when (and in what order) these concepts developed? Are there any resources that cover the history of practical computer science at this level?


texts: Does Turing Machine divergence depend on the input?

texts: If there is a Turing Machine $M_e$ (computing some partially computable function $f$), is there an algorithm to decide if $f$ diverges for all possible inputs?


texts: Books on scientific computing, efficent NN inference, and matrix multipication

texts:
I'm trying to learn more about how inference, matrix multiplication, and scientific computing (primarily with tensors/matrices). I'm not sure what the classics here are or what good sources are. I'm primarily looking for books but classic texts of any kind are welcome (including both papers, blogs, and articles on real world implementations).
I'd like to gain an understanding of both how to implement algorithms like GEMM as efficiently as BLAS implementations do and also how to perform inference on neural networks efficiently. When I say "efficiency" I mean both latency and throughput as is classically meant but I also mean energy efficiency as well. Energy efficiency seems to be covered less however.
What are good references/books in this area?


texts:
From the Introduction section of Homotopy Type Theory book:

  Type theory was originally invented by Bertrand Russell ... It was later developed as a rigorous formal system in its own right(under tha name "$\lambda$-calculus").

Can anyone explain me this sentence? I'm having trouble seeing $\lambda$-calculus as a type system.

(also in the same paragraph, $\lambda$-calculus called as "Church's type system")


texts:
I searched linear solver library and found out PETSc library which considered to be powerful and useful library. PETSc consists implementations of various iterative methods with preconditioners and sparse matrix storing methods. All methods are realized sequentially and in parallel using MPI.

I was very glad for creaters of PETSc. I downloaded it and installed. However, when I start reading user's guide I encountered following text:

PETSc should not be used to attempt to provide a “parallel linear solver” in an otherwise sequential
code. Certainly all parts of a previously sequential code need not be parallelized but the matrix
generation portion must be parallelized to expect any kind of reasonable performance. Do not expect
to generate your matrix sequentially and then “use PETSc” to solve the linear system in parallel.

I was surprised! Did PETSc developers really parallelize only matrix generating part? What is a benefit of using PETSc as parallel solver if linear system solving part runs sequentially?


texts: How do you solve this [1,5,9,4] pair numbers problem?

texts:
So given an array of [1,5,9,4], find all pairs of numbers that can sum/subtract/divide/multiply to another number in the array(that number is not part of the pair), and return the total count of pairs satisfying this condition. (If a pair has 2 math operators that fit to the same number or if a pair can combine to 2 different numbers, dont count it twice).

How do I start this? and how do I explain my asymptotic complexity(Im a noob wit this)?


texts: Prove or Disprove: an infinite intersection of regular languages is a context-free language

texts:
Let $L_1, L_2,...$ and $L=\cap_{k=1}^{\infty}L_k$ be languages over $\Sigma ^{*}$.
Prove /Disprove: if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, then $L$ is a context-free language.
I know that statement is false, but couldn't find an example to disprove it.
Would appreciate your help:)


texts: Number of distinct single-assignment forms with $j$ binary function calls?

texts:
Given $n$ inputs and $k$ outputs and $j$ identical binary function calls to $g$, how many possible distinct single-assignment forms are there?

The only assumption made about $g$ is that if $a = c \wedge b = d$ then $g(a, b)  = g(c,d)$.

Each SSA form consists of two parts. The first is a temporary assignment part:

t1 = g(_, _)
...
tj = g(_, _)

Where each _ can be any of the inputs $i_1$ through $i_n$ or a previously calculated $t_x$. After that follows an output assignment part:

o1 = _
...
ok = _

where _ can be $i_1$ through $i_n$ or $t_1$ through $t_j$, but not another $o_x$. The output of the SSA form is $(o_1, o_2, \dots, o_k)$.

Trivial counting doesn't work, because the following two SSA forms seem different, but are equivalent (with $n = 4$, $k = 1$, $j = 3$):

t1 = g(i1, i2)       t1 = g(i3, i4)
t2 = g(i3, i4)       t2 = g(i1, i2)
t3 = g(t1, t2)       t3 = g(t2, t1)
o = t3               o = t3

Also this doesn't account for irrelevant changes that are still equivalent (with $n = 3, k = j = 1$):

t1 = g(i1, i2)       t1 = g(i1, i3)
o = i1               o = i1

Questions:

What is $f(n, k, j)$, giving the number of distinct SSA forms?
Does there exist an efficient way of iterating over these SSA forms?
What if we also assume $g(a, b) = g(b, a)$?


texts: Locality sensitive hashing with non-scalal values

texts:
Locality sensitive hashing works well when matching is between vectors of scalars, but I now need to extend LSH to compare matrices. Each matrix is formed of n readings from m sensors forming a n by m matrix. Comparison between differing columns is inappropriate.

I could turn the matrices into vectors of length n * m and ensure permutations only occurred with blocks of length n. For example

[1 2 3]
[4 5 6]
[7 8 9]

would map to

[1 2 3 4 5 6 7 8 9]

with the the units for permutation being [1 2 3], [4 5 6] and [7 8 9].

My first thought is that the restriction on permutation will weaken the statistical properties that LSH relies upon, but if n (the number of permutable items) is large enough compared to m (the size of each non-permutable items) the this will asymptotically disappear as a concern.

My other thought is to project the n * m matrix on to a vector of lower dimension which it is valid to permute, since each scalar in the vector encodes part of each column in the vector assuming n vectors of length m being projected onto a single vector of length n or less.

How could I achieve such a projection, without losing excessive information? Is it preferable over relying on the former's asymptotic behaviour?


texts: How many different heaps are there of a given shape?

texts:
Let's say we have a tree like this:

Suppose we are given $N$ distinct elements, $N$ being the number of vertices in the tree (in this case, $N=13$).

  In how many ways can we distribute the given $N$ elements in the tree so that it has the max-heap property (any vertex is larger than its children)?


texts: Algorithms to generate random nowhere-neat rectangulation?

texts:
I want to generate random rectangular partition of a given $m*n$ rectangle under the  constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle into smaller rectangles such that the original rectangle is not divided into two subrectangles.

My interest is in generating rectangular partitions that satisfy these two conditions: 1- No two adjacent rectangles share a common side (i.e. the union of two adjacent rectangles is not a rectangle).  2- At most two corners meet at a point.

Similar partitions appear under other names that include rectangulations, Tatami tilings, and non-slicing floorplans.

  What algorithms are there that generate random fault-free rectangular partitions?

Update:
Here is an example of random Mondrian rectangular partitions. Here the original rectangle is divided into two subrectangles. However, it is the opposite of what I want.

I do not require uniform distribution. I do not require a specific number of tiles, I only require that the number of tiles $T$ is within some fixed ratio $\epsilon \lt 1$ of $mn$ where $m= \theta(n)$ ($T=\epsilon*m*n$).


texts: How to reduce Checkers to P and NP-complete?

texts:
NxN Checkers where both players are playing to win is EXPTIME complete.
If we fix NxN to be 8x8 and prepare a very large lookup table then it can be solved in constant time and space.
How to formulate Checkers to make it P and NP-complete? (2 different formulations)
Note: I am interested in usual competitive Checkers. Not 'Lose-in-1 Checkers in NP-complete.'


texts:
I am having difficulty with the concept of $LK-\Phi$ proofs, here is a question I have been working on:

  Let $\Phi = \{Pafa\}$, where $P$ is a binary predicate symbol and $f$ is a unary function symbol. Give an $LK-\Phi$ proof of $\exists y Pby$. You do not need to show exchanges and weakenings.

My intution for these questions is very little unless it is blatantly obvious over what to do, but I do know that in the system $LK$ we have a $LK-\Phi$ proof if we have $A\to A$ or $\to A$ where $A\in\Phi$. So in this situation I think I set this up as the following:

$$\to \exists y Pby$$and then I would have a sequent above it where I would apply the $\exists R$ rule, which would create the sequent above as: $$\to Pba$$ but from here I am not sure at all what to do whether I need to rely on some sort of trick or anything? Any help would be greatly greatly appreciated, this is for an exam I am studying.


texts: Recursive Algorithm Copying Array vs. Time Complexity

texts:
If I am implementing binary search using a recursive algorithm on an array it will be bounded by $O(\log(n))$.
However, what will occur if the array is NOT passed by referenced and rather by value.
This means that the recursive call will have to first copy the elements of the array (half the original items).
Does this mean that the resulting time complexity for a pass-by-value binary search using an array is $O(\log(n)\cdot\log(n))$ or $O(\log(n)^2)$?


texts:
Is there an efficient algorithm for the following problem?

Given: a $m$-vector $b \in \{0,1,2\}^m$, and a $m \times 2m$ matrix $A$, with the promise that for every $b' \in \{0,1,2\}^m$, there exists $x' \in \{0,1\}^{2m}$ such that $Ax'=b' \pmod 3$

Goal: find $x \in \{0,1\}^{2m}$ such that $Ax'=b' \pmod 3$

In more detail:  I have a system of equations Ax (mod 3) = b. Each entry for A and each entry for b is 0, 1 or 2 ("ternary"). We're looking for a solution x where each entry is 0 or 1 ("binary"). For example:

p q r   b
1 0 1 | 2
1 2 1 | 1

has one solution: p=1, q=1, r=1.

For square matrices A, this often has no solution. For example

p q r   b
1 0 0 | 1
0 1 0 | 1
0 0 1 | 0

Does have a solution (p=1, q=1, r=0), but

p q r   b
1 0 0 | 1
0 1 0 | 2
0 0 1 | 0

Does not have a solution, since q can only be 0 or 1 (as x should be binary).

I found from practice that practical/useful NP-complete problem instances can often be written in this way with an m x n matrix with m << n << 2m (often n is about 1.5m), but in this question, I'm only interested in cases where n=2m and the equation does have solution. This is at least the case when something stronger than linear independency holds. I think the right condition is that matrix A is such that Ax (mod 3) = b has a binary solution for every ternary vector b.
For example, the matrix A with n=2m:

1 1 0 0 0 0 | ?
0 0 1 1 0 0 | ?
0 0 0 0 1 1 | ?

always has a binary solution. Unfortunately, even if the rows are linearly independent, row operations can generally not achieve such a matrix (with 2 pivot columns in each row) except for trivial problems.

Take for example

              b
1 1 0 0 0 0 | ?
0 0 1 1 0 0 | ?
2 0 0 0 1 1 | ?

Then there is a binary solution for every b, but the question now is, is there a quick algorithm so that we can find it for any given A and b (where A meets the requirement that a solution exists for every b')?


texts:
I'm trying to classify and come up with a reasonable solution for the following problem (abstracted from a real world problem).

Problem

Imagine StackOverflow started offering a subscription where companies could buy X number of impressions per month for a set of tags.

For example, you might be interested in running an ad with 50000 impressions on the following tags: javascipt, typescript, react, nextjs, nodejs, webpack.

StackOverflow "promises" you will get 50000 impressions, but they are free to distribute them across the above tags however they desire (could even be 100% to one tag).

How should StackOverflow optimize the distribution so that they can sell/deliver the maximum number of impressions?

For simplicity, assume:

we know the number of impressions each tag receives per month ahead of time and it doesn't change
each impressions only belongs to a single tag

My Research

I believe this might be similar to the Knapsack or Bin packing problems.

The simplest way to approach this is with a "first-fit" (or maybe better described as "first come, first-serve") algorithm:

Get all active "subscriptions" (impressions & tags), ordered by Created Date ASC
For each "subscription", grab the first tag and "consume" as many impressions as we can.  If the subscription still has remaining impressions, move to the next tag.
Repeat with next subscription

That might play out something like this:

==Inventory==

Tag          Impressions
javascipt    2000
typescript   5000
react        5000
nextjs       5000

== Subscriptions ==

Acme:  8000  (javacript, typescript, react, nextjs)
Stark: 5000  (javacript, typescript)

== Allocation Results ==

Acme:
 - javacript:  2000
 - typescript: 5000
 - react:      1000

Stark:
 - javacript:  0
 - typescript: 0

The optimization for this solution is clearly horrible.  In the example above, while we had more than enough impressions to go around, we allocated the only ones that "Stark" could purchase before we got around to them.

Is there an official name to this problem and what does the optimal solution look like?


texts: How to build a finite automaton for right quotient of a regular language?

texts:
Let $L$ be a regular language over $\Sigma=\{a,b,c\}$. Build a finite automaton for $L/\{a\}$.

Because $L$ is regular then a DFA exists for it: $A=(\Sigma, Q, q_0, F, \delta)$.

Let $M$ be a finite automaton, $L(M)=L/\{a\}$.

$M=(\Sigma, Q\times\{0,1\}, (q_0,0), \delta', F\times\{1\})$ with the transition function defined below for all $q\in Q, \sigma \in \Sigma$:
$$
\delta'((q,0),\sigma)=(\delta(q,\sigma),0)\\
\delta'((q,0),\epsilon)=(\delta(q,a),1)
$$

The reasoning is that in state $0$ we just read letters in $M$ because those exact letters also exist in $L$. But when we reach end of input in $M$ via $\epsilon$ we still need to read $a$ in $L$. I'm not sure if it's valid to assume that $\epsilon$ means end of input?


texts: How to understand the probablistic analysis of skiplist?

texts:
I've been studying the skiplist analysis from the open data structures book here:
Open Data Structures
I've understood the first 3 lemma's, (after looking at how they use indicator variables in the section 1.3.4 of the book).
However, Lemma 4.4 seems pretty vague. Especially, how is
$$\sum_{r=1}^{\lfloor\log n\rfloor}1 + \sum_{r=\lfloor\log n\rfloor+1}^\infty n/2^r\leq\log n + \sum_{r=0}^\infty 1/2^r\,?$$


texts: Why if L and ¬L (Complement of L) are turing-recognized both are turing-decidable?

texts:
I can't understand this theorem:
If both L and L complement are turing-recognized, both are turing-decidable
Proof:

w is M input
if w ∈ L then M1 accepts w and M accepts w
if w ∉ L then M2 accepts w and M rejects w

M is a TM containing M1 and M2.


texts: Bijective algorithm(s) that can shuffle a range of numbers back and forth

texts:
I've spent the last hours trying to come up with an algorithm that shuffles an ordered set of numbers (i.e a simple range of numbers) in a way that I can retrieve from a shuffled value the original value that was on that position without the need to store all relationships between shuffled values and their counterparts.

The statement above may not make any sense to you, but I've learned some terms while trying to find such algorithm that may help me to describe what I mean...

First of all I believe that this algorithm/function is bijective, which means it is deterministic and one member of $A$ has only one correspondent member of $B$ and vice-versa:

Another peculiarity is that input and output domains are exactly the same so, following the above example, $A$ = $B$ = $D$ with $D$ being a range from $m$ to $n$.

To sum everything up (sorry I'm pretending that I know math):

$D = \{x \in \mathbb N\ | m \le x \le n \}$

$
\forall x \in D  \land \forall y \in D\\
f(x) = y \implies \exists  g(y) = x
$

What could be done to simply implement $f$ and $g$ ?

The closest solutions I've found are some kind of block cipher which I'm unable understand nor tweak to achieve the desired behavior which is much simpler.

As one last attempt to explain this, here is a simple use case:

Consider integer codes that can range from 1 to 2^31
On the backend these codes are used sequentially, getting increased one by one
Instead of sending one of these codes for a client, our function picks another code from that range to represent the original one
Despite we need to use those codes sequentially we are only sending the random values for the clients so it looks random from his perspective
When we receive this code back the from the client we're able to tell the original code
We would also be able to change the way that these codes are "shuffled", so different codes could be exposed over time while leaving the original ones untouched on our side

Sorry if I wasn't clear enough or destroyed math notations forever.


texts: How to express a parabola as a Bezier curve

texts:
I need to create a parabolic shape with a given starting point, maximum point, and end point. I thought the most efficient way to do this is to use a bezier curve. However there is no major relationship (that I could find) that relates a control point of a Bezier curve with its maximum point (which is why I am asking this question)
So given the starting point and ending point as well as the maximum point of a parabola, is it possible to write an algorithm which could calculate the control points of a Bezier curve that would be the same shape of a parabola? If so how?
Update: After some searching on the internet I found this question on SO which answers the opposite of what I am trying to achieve. It finds the max/min of a bezier curve while I am trying to find the control point of a parabola. I could subject the given formula for the control point, but this requires me to play around with t and I sense a lot of inefficiency, all the other resources seem to deal with curvature, which is not what I'm after. Is there any good way to deal with this problem?
Quick Fix: So I used this question from SO and the references in this answer from the mathematics stack to research on these curves. Then I played with the equations until I found something. If the third control point lies on the perpendicular bisector of the starting and ending points, the maximum/minimum point also lies on the bisector. Logically this makes sense as then the curve is symmetric. For my use case, the curve has the same y coordinate when it starts and ends, and the third point is between the two points (Visualisation here) so I exploited this and substituted $t = 0.5$ into $ M = A*(1-t)^2 + B*2t(1-t) + C*t^2$ where A is the starting point, C the ending point B the 3rd control point and M is the max/min point. A little bit of rearrangement gives that $B = 2M-0.5C-A$ which is perfect for my use case, as I only have to calculate the y coordinate because the x coordinate is effectively the x coordinate of B, but is still not general enough to act as a answer to my question. Perhaps someone could generalise it?
(I am beginning to feel as if this should have been posted in the math stack. Apologies for being so short sighted and not realising the mat.)


texts: The sequence in which every symbol minimizes conditional complexity?

texts:
I formulate the question in terms of universal distributions. Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$.

Start with some $\omega_0$. Each subsequent element is given by $\omega_n=\arg \max_a\mathbf M(a|\omega_{1:n-1})$.

What are the properties of $\omega$? For example, is it necessarily computable? Does the answer depend on the choice of $\mathbf M$?

The equivalent formulation is the following but it does not really help me advance with the problem.

Is there a universal lower semicomputable $\lambda$-supermartingale $t$ and a binary sequence $\tilde\omega$ such that $t$ always "goes up" along $\tilde\omega$ but never succeeds?

This type of problem arises when a player plays against a reactive environment and the sequence the player observes is not exogenous. A more general question is what is the short-run behavior of $\mathbf M$ since asymptotic results do not seem to help here.

UPDATE

As an example, consider a simple coordination game with payoff matrix:

(1,1)     (0,0)

(0,0)     (1,1)

Consider two players who infinitely repeatedly play this game. Their goal is to maximize the payoff. Assume that the player are myopic that is they care only about the payoff in the current period.

Each player observes his opponent's history and tries to match him. Each player has a prior distribution about his opponent's play and updates it using Bayes's rule.

Now assume that the prior distribution is Solomonoff's $\mathbf M$. Then every period a player chooses an action $\arg \max_a\mathbf M(a|\omega_{1:n-1})$ where $\omega_{1:n-1}$ is the opponent's history. The other player does the same, thus the rule $\omega_n=\arg \max_a\mathbf M(a|\omega_{1:n-1})$.


texts: Prove correctness of iterative LCM algorithm

texts:
I have been trying to prove the following algorithm, without success.

Here is the C-Style pseudocode:

//j,k >= 0
int get_lcm(int j, int k){
    int c = j;
    int d = k;
    while(c != d){
        if(c < d){
            c += j;
        } else {
            d += k;
        }
    }
    return c;
}

I tried to find the loop invariant, which ended up being something like:
$$
\begin{aligned}
&c\le\text{LCM}(j,k) \wedge d\le\text{LCM}(j,k) \wedge c=aj \wedge d =bk\\
&(a,b \in N)
\end{aligned}
$$
I'm not sure how to proceed from here. I understand intuitively why the algorithm works, but I'm having trouble putting out an actual formal proof of it.

I need to come up with an invariant such that $c=d=LCM(j,k)$ when $c=d$. I'm having trouble showing how $c, d \le LCM(j,k)$ after one iteration.

Can anybody please help me? Thank you for your time.


texts: How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in a undirected graph?

texts:
How can an maximum flow algorithm for directed graphs, i.e. Edmond-Karp, be adapted to compute a minimum $s$-$t$ cut in an undirected graph ?

I've seen it stated that one can apply a maximum flow algorithm to compute a minimum $s$-$t$ cut in an undirected graph. However, trying to adapt the Edmond-Karp algorithm this doesn't make much sense, or does it ?

I know a graph can be viewed as an undirected graph with $(u,v)$ and $(v,u)$ replacing $\{u,v\}$...


texts: How to find m directed paths connecting the maximal number of vertices in an unweighted directed acyclic graph?

texts:
Consider an un-weighted directed acyclic graph (DAG) consists of m source (root) vertices and n target vertices. When there is only one source vertex (m=1), the problem to find a directed path connecting a maximal number of target vertices is the longest path problem in a DAG, which can be optimally solved within linear computation time. At the moment, the un-weighted DAG has m source (root) vertices. The objective is to find m directed paths where each path originates from one unique source vertex such that the total number of the target vertices connected by the m paths is maximal. Each target vertex and each edge can be passed multiply by the m paths. However, when counting the number of the connected vertices, the multiply visited target vertex just be treated as one single target vertex.

I want to know whether and how the above mentioned problem can be optimally solved within linear computation time. Thanks for your answer.


texts: Can loops like this one be algorithmically transformed into multiplication

texts:
Are there known techniques for converting a loop like the following to an if and a multiplication?

while (x < 0) {
    x += 60;
}

It seems clear that this could be replaced with something like the following

if (x < 0) {
    x += f(x, 60);
}

where f contains no loops, presumably using multiplication. This would have the benefit of being faster for sufficiently large negative numbers.

Is there a well understood algorithm for finding f for an arbitrary loop of this form?


texts:
let's say L is a regular language.
And there in an NFA automata with epsilon moves A,in which for every accepting state δ(q,σ)=Ø.
How can I prove that there must be an automata A as defined for L?


texts: Knapsack with non-overlapping rectangles

texts:
Given a large rectangle and a set $S$ of small rectangles each with a value $v_i$. My problem is to find a collection of rectangles $T\subseteq S$ to put in the large rectangle so as to maximize the overall value $\sum_{i\in T}v_i$, subject to the constraint that the selected small rectangles cannot overlap with each other.

I suppose the problem is NP-hard.  Can we design an approximation algorithm (PTAS or constant-factor approximation ratio) approaching the optimum?


texts: Understanding the recursive fast Fourier Transform Algorithm from CLRS

texts:
Consider the following recursive fast Fourier transform algorithm from CLRS:

I believe that I understand this algorithm correctly: you split the input coefficients into the odd and even terms, recurse, and combine using the roots of unity.

However, I am aware that you can also use this recursive fast Fourier transform algorithm to evaluate polynomials at roots of unity modulo $n$ rather than just complex roots of unity over the set of complex numbers.

Given a coefficient vector $(8, -4, 2, 3, -5, -4, 2, 1)$, which represents $8 - 4x + 2x^2 + \cdots + x^7$, I want to evaluate the corresponding polynomial at eight $8^{\text{th}}$ complex roots of unity modulo $17$, which I know to be $1, 2, 4, 8, 16, 15, 13$. Moreover, I want to do this with the fast Fourier transform described above. I think that if I am working over the integers modulo $17$, then I need to use $2$ as my primitive root of unity rather than $e^{2\pi i/n}$, but I can be wrong about this.

I will show you my work, and why I think it is incorrect.

Firstly, I recurse and divide the original problem into two subproblems:

$$(8, -4, 2, 3, -5, -4, 2, 1) \rightarrow^{\text{subproblems}} (8, 2, -5, 2) \text{ and } (-4, 3, -4, 1) $$

Next, I will solve the problem $(8, 2, -5, 2)$ by recursing:

$$(8, 2, -5, 2) \rightarrow^{\text{subproblems}} (8, -5) \text{ and } (2, 2).$$

Next, I will solve the subproblem $(8, -5)$ by combining the solutions of $(8)$ and $(-5)$, which are just $8$ and $-5$. I obtain $y_0 = 8 - 1 \cdot 5 = 3$ and $y_1 = 8 - 1 \cdot (-5) = 13$. In a similar manner: $(2, 2)$ returns $4$ and $0$. From here, I can solve combine these two solutions to solve $(8, 2, -5, 2)$ by computing $y_0 = 3 + 4 = 7$, $y_1 = 13 + 2 \cdot 0 = 13$, $y_2 = 3 - 4 \equiv 16$, and $y_3 = 13 - 2 \cdot 0 \equiv 13$. So we return $7, 13, -1, \text{ and } 13$.

I repeat the same procedure on $(-4, 3, -4, 1)$, for which I omit steps, but I will post them upon request. We find this call returns $(4, 12, 13, 4)$.

Finally, I combine for the final solution and I get $y_0 = 4 + 7 = 11, y_1 = 13 + 2 \cdot 12 \equiv 3, y_2 = 16 + 4 \cdot 13 \equiv y_3 = 13 + 8 \cdot 4 \equiv 11, y_4 = 7 - 4 \equiv 3, y_5 = 13 - 2 \cdot 12 \equiv 6, y_6 = 16 - 4\cdot 13 \equiv 15, \text{ and } y_7 = 13 - 8 \cdot 4 \equiv 15$.

But when I plug in the roots of unity manually into this polynomial through Wolfram Alpha, I get different answers. What am I doing wrong?


texts:
Here is a minimal working example of the question:

Consider a network with nodes arranged in a pyramid:  $1$ node in the first row, $1+d$ nodes in the second, $1+2d$ nodes in the third, and so on, for $m$ rows.  (So $n = m + (m-1)md/2$ nodes total.)  Each node takes a state of 0 or 1.  All nodes not in row $m$ have $1+d$ "parents" in the next row, and these parents are "local".  For example, if $v$ is the $k$th node in row $r < m$, then its parents are nodes $k$ through $k+d$ in row $r+1$.

For each node $v$ in a row $r < m$, there is a table $T_v$ that lists all possible combinations of states of the parents of $v$ and, for each combination, assigns a state of 0 or 1 to $v$.

Let $d\text{-RETROSPECT}$ denote the decision problem of determining whether there is an assignment of states to the nodes of the network that assigns state 1 to the node in the first row and is consistent with all $T_v$.

Are there $d$ for which $d\text{-RETROSPECT}$ is NP-hard?

It seems unlikely that I am the first person to contemplate this.  (In fact, in a famous paper in 1990, Cooper showed that if the parents are not required to be local, then the problem is indeed NP-hard for at least $d \geq 2$.)  Is a direct proof possible in the local case---e.g., by a polynomial-time reduction from a known NP-complete problem?  Or, if not, does anyone know of recent relevant literature?


texts: Is "capability-based security" vs "hierarchical-protection-domain based security" a false dichotomy?

texts:
The wikipedia page on capability-based security states:

  Capability-based security is to be contrasted with an approach that uses hierarchical protection domains.

However, in order to implement capability-based security, we still need a kernel that ensures that user processes are only able to use the capabilities they have been assigned. Hence we still need a distinction between kernel mode and user mode, which is exactly what hierarchical protection domains are. In fact, as far as I know, most OS'es use only 2 hierarchical protection domains (user and kernel) in practice (I think Windows 10 has domains 0,1,2,3, but that 2 and 3 are only rarely used).

So it seems to me that kernels that implement capability-based security do not make less use of hierarchical protection domains than other operating systems.

Isn't it more accurate therefore to say that capability-based security is one way of using hierarchical protection domains to achieve security? (rather than fundamentally different from hierarchical protection domains)


texts: Formal Verification of Functional Programs

texts:
So I've been interested in learning more about formal verification, and I've seen a lot of interesting things like ACSL and JML which are based on the concept of Hoare triples.

My question is, that these seem to be a way to describe the behaviour of imperative programs via specification languages that are mostly functional (plus universal and existential quantifiers).  But I don't even know the keywords to search to start learning how one would perform formal verification of code in a pure functional language like Haskell.

Could anyone provide a link to material or the name of the equivalent/analogue of Hoare triples for pure functional computation?  Or do you need a fundamentally different approach in the purely-functional realm?


texts: Can anybody suggest some algorithms for computing the edit distance other than Wagner–Fischer algorithm?

texts:
I'm currently working with finding edit distance between two string of unequal length. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But I'm dealing with some cryptographic measure with edit distance where algorithm with dynamic programming is not suitable. Please have a look at the algorithm. If we want to do this computation homomorphically, circuit-based computation is needed here which will time consuming one. Usually homomorphic computation works well where there is more additions than multiplications.

This is why, I'm looking for another algorithm rather than the above one.


texts: Count unhappy numbers in a large interval

texts:
An unhappy number is a number that is not happy, i.e., a number $n$ such that iterating this sum-of-squared-digits map starting with n never reaches the number 1.

For example, $23\rightarrow 2^2+3^2 = 13 \rightarrow  1^2 + 3^2 = 1$, so $23$ is a happy number. But, number $2$ is not and you can verify it.

The problem around my question (from 2010 acp icpc problem set) is to count unhappy numbers in an interval $[\textrm{lo}, \textrm{hi}]$. I'm looking for an algorithm that is practical for $\textrm{hi}$ up to $10^{18}$.

How can I  write an algorithm for this problem, efficient and correct?

I know that the solution is with dynamic programming, but I don't know how can I get it.

My approach when I read the problem was use a backtracking to mark all numbers in the interval, like a dfs, and see that when you're processing a number and got the result, you should mark all numbers with form permutations of digits for the initial number. Then, I thought that a backtracking approach is faster. But this is not enough for contest, because the interval is $[1, 10^{18}]$ so, clearly dynamic programming is the way.


texts:
I have the following two CFL: $A =\{a^m b^n c^n\}$ and $B = \{a^m b^m c^n\}$.
I don't understand why the intersection of this languages is $\{a^n b^n c^n\}$: can anyone explain to me why the power is to the $n$ and not to the $m$ or something else?
Thank you in advance.


texts: Optimal algorithm for making queries to a database

texts:
There is a database of, let's say, 500k English two-word combinations (e.g. "clover arc", "minister horse"). I can search for an arbitrary string and I will get a list of the alphabetically first 1000 entries containing this string; the time each query takes is proportional to the number of results it returns, plus some constant overhead. I have a certain dynamic number of the unique results I want to get (e.g. 400k, 490k, 499k) and I want to spend as little time as possible sending queries to get them. By what algorithm should I craft my queries to achieve this?

One possible naive approach would be as following:

Search for every single letter.
Check which queries have maxed out the 1000 result limit.
For each of those, make 26 new queries, appending every letter of the alphabet to them.
Go to 2, until all queries give fewer than 1000 results.

However, this is obviously quite suboptimal, since every time we expand the tree the previous results get essentially obsoleted - almost all of them (except for those where the letter combination was at the end of the word) will be present across the queries generated from it, plus there will wasted overhead time on impossible combinations (e.g. we had a maxed-out query of "qu" and on the next level we'll be requesting "quq" and "qux", which will certainly not give any results).

How would you approach this?

(I apologize in advance if this is the wrong SE to ask this kind of question, but I couldn't find a better match.)


texts: Relation between the "Point-Cover-Interval" problem and the "Interval Scheduling" problem

texts:
Point-Cover-Interval Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains some point, that is $\forall I \in \mathcal{I}: \exists p \in P, p \in I$.

  Interval Scheduling Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a maximum number of intervals such that no two of them overlap.

Interestingly, the two problems above have exactly the same greedy algorithm, illustrated by the following figure (from [1]; for the interval scheduling problem; see the "Greedy Algorithm" part below).

Since they share the same algorithm, I expect that they are the same (or, at least closely related) problem, say, in the view of reduction. However, I failed to reduce them to each other.

  Question: Are these two problems the same? Or what is the relation between them? Can we reduce them to each other?

Note that the first problem asks for a minimum solution while the second one for a maximum solution.

Greedy Algorithm:
The greedy algorithm for the "Interval Scheduling" problem is as follows:

sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$.
while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}$, do:

add $I$ into the result-set; (darker lines in the figure)
delete all intervals from $\mathcal{I}$ that conflicts with $I$ (dashed lines in the figure).

For the "Point-Cover-Interval" problem, we simply collect the finishing time point of each interval $I$ chosen in each iteration in the algorithm above.

[1]: Algorithm Design. By Jon Kleinberg and Éva Tardos. (Section 4.1)


texts: What is the advantage of Randomized Quicksort?

texts:
In their book Randomized Algorithms, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set into two parts, is chosen at random.

I have been racking my (admittedly somewhat underpowered) brains over this for some time, but I haven't been able to see what advantage this algorithm has over simply picking, say, the middle element (in index, not size) each time.

I suppose what I can't see is this: if the initial set is in a random order, what is the difference between picking an element at a random location in the set and picking an element at a fixed position?

Can someone enlighten me, in fairly simple terms?


texts:
If we start with the definition of L being in NP if "there exists a polynomial NTM that decides L" (where polynomial for an NTM means the length of the worst run as a function of the size/length of the input / the maximal tree depth)

There is a proof that L is in NP iff there exists a polynomial TM verifier for L.
Regarding the "L is in NP" -> "there exists a polynomial TM verifier for L" side:
Let N be that NTM
I fail to understand how given (w, R) where R is the encoding for an accepting run of N on w, we can verify this in polynomial time in regards to w (as this is how the time complexity for a Verifier is defined)

We can show R's length is polynomial in w, but how would we verify that it is a valid run for N in polynomial time?
We need to verify every 2 consecutive configurations in R are valid, but since for NTM's the transition function maps to a set of (Q x Gamma x {L,R}) possibilities - I can't figure out how this is possible.

Update:

Let me clarify a little further.
An obviously bad (non polynomial) solution would be to have the verifier initially write the whole encoding on N on its tape, and then "search through it" to see if a transition is valid. But since the encoding of N is certainly not necessarily polynomial in N, this doesn't work.

It seems the answer has to rely on having the "inner workings" of N "embedded" in the verifier therefore avoiding time complexity issue as we are avoiding time complexity issues by having things "embedded" - but I fail to see how that could then be used further.
I see how this opens an avenue of possibility, but can't see it through.
I'm assuming there is some low-level technical grunt work so that the right transitions can be "embedded" straight into the verifier.


texts: What would a formal grammar for a binary file format look like?

texts:
Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive.

What would a context-sensitve grammar for a simple binary format look like?

For example, let's consider a length-prefixed array with the following layout:

64 bits | [size * 8] bits
size    | data

I suppose the language that corresponds to this format would be:

$$n b^n \\
n \in [0, 2^{64}[ \\
b \in [0, 2^8[$$

Left-context-sensitive grammars have the following structure:

$$\alpha A \rightarrow \alpha \gamma$$

I don't understand how this formalism could generate or be used to parse a language which contains part of the grammar itself in it. Does the following grammar make any sense?

\begin{align}
Bit & \rightarrow 0 \\
Bit & \rightarrow 1 \\
Octet & \rightarrow Bit^8 \\
Size & \rightarrow Octet^8 \\
Size \; Data & \rightarrow Size \; Octet^{Size} \\
Array_s & \rightarrow Size \; Data \\
\end{align}

I reason that the grammar above matches the structure of left-context-sensitive grammars. It seems clear to me that the next-to-last line of the grammar directly corresponds to the definition above:

\begin{align}
\alpha & = Size \\
A & = Data \\
\gamma & = Octet^{Size} \\
\end{align}

The trickiest non-terminal seems to be $Size$. It is not clear to me exactly how it influences the grammar's semantics. It is simultaneously part of the input and the grammar, serving as the number of repetitions for $Octet$.

I have seen many grammar-based approaches to parsing binary file formats. They include formalisms such as attribute grammars,[1][2] adaptive grammars, the recently introduced data-dependent grammars,[1][2] parser combinators [1][2][3][4][5] and even scattered context grammars.[1]

All these tools go beyond the definition above, so I keep wondering about the nature of binary file formats. If it is not possible to describe their language with a context-sensitive grammar, does that mean they are more powerful in the Chomsky hierarchy?


texts: Grouping elements optimally other than NP-hard approach

texts:
Given a number $N$, I need to make a new array $B$ of size $n$ (index-1 based) such that the product of $B[i]-(i-1)$ for $1 \le i \le n$ is equal to $N$ and $B[n]$ is minimum and $B[i] \ge B[i-1]$ and $B[i] \ge 1$.

I found the prime factors of $N$ and sorted them in decreasing order and if they are greater than $n$ then I divided them in $n$ groups optimally (minimizing the maximum product of a group). What can be the other approach since dividing in $n$ groups is NP-hard problem and I would like to get a better approach?

The approach fails sometimes.
Like for N=384 and n=6 the best answer is

4 5 6 6 6 6

since

(4-(1-1))*(5-(2-1))*(6-(3-1))*(6-(4-1))*(6-(5-1))*(6-(6-1))=384

while this approach gives

4 5 5 5 6 7

since

(4-(1-1))*(5-(2-1))*(5-(3-1))*(5-(4-1))*(6-(5-1))*(7-(6-1))=384


texts:
This question was cross-posted to cstheory.SE here.

Imagine you're a very successful travelling salesman with clients all over the country. To speed up shipping, you've developed a fleet of disposable delivery drones, each with an effective range of 50 kilometers. With this innovation, instead of travelling to each city to deliver your goods, you only need to fly your helicopter within 50km and let the drones finish the job.

Problem: How should your fly your helicopter to minimize travel distance?

More precisely, given a real number $R>0$ and $N$ distinct points $\{p_1, p_2, \ldots, p_N\}$ in the Euclidean plane, which path intersecting a closed disk of radius $R$ about each point minimizes total arc length? The path need not be closed and may intersect the disks in any order.

Clearly this problem reduces to TSP as $R \to 0$, so I don't expect to find an efficient exact algorithm. I would be satisfied to know what this problem is called in the literature and if efficient approximation algorithms are known.


texts: Is there an example of real polynomial representation of a Boolean function with $4$ variables whose polynomial degree is $2$ that depends on $4$ variables?


texts: Turing Machine that halts iff the tape contains at least two '1's

texts:
Contruct a Turing Machine that halts if and only if the tape it is on contains at least two '1's.

My attempt:

The gist of this turing machine is that it has to check all of the cells, and since it is infinite in both directions, one way of indexing it is a follows

Thus it has occurred to me to write a pseudocode for the TM's behaviour like this:

n:= 0           //number of '1's encountered
i:= 0           //index
while(true)
{
  if(n==2)
    halt
  for k=0 upto i
  {
    check()
    if(i even)
      move left
    if(i odd)
      move right
  }
  i++
}

Where check is the function defined as follows:

check()
{
if(current cell contains 1)
  n++
}

But this seems really hard to implement as a turing machine, especially since there are two variables involved. My guess is that I am overthinking and there is a much cleaner, nicer and elegant solution.

So my question is: What would be a better solution?


texts: Does computability according to Church-Turing thesis include side effects?

texts:
To my understanding:

The Church-Turing thesis means that one could theoretically compute anything that can be computed using either a Turing Machine or the Lambda Calculus.
The Lambda Calculus is based on mathematical functions. This leads to the inability of "pure" functional programming languages based on Lambda Calculus to have side-effects (in the sense that a language like C would have side effects).

To me that would imply that side-effects are not part of computability, but something in addition to it.

e.g. I would say that real-world memory writes that cause physical side-effects  are not of the same nature as the imaginary writes to the tape in a Turing Machine. Or put another way: if I'm writing values to memory whose purpose is to serve as a result in a calculation, Turing completeness would be theoretically relevant; but if I'm writing to a region of memory designed to instruct a robot arm to do things, Turing completeness would be theoretically irrelevant.

Is my understanding correct?


texts: Question about Prims algorithm where weights are between 1 and some constant W

texts:
I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3).  I am wondering if anyone can make a clarification as to the stated running time of the solution.

Q:  Given that we know the edge weights on a graph are between $1$ and some constant $W$, how fast can we make Prim's algorithm run?

Solution:

Uses an array of linked lists where each index corresponds to a given weight [$1\dots W + 1$]
Each link linked lists contains a series of vertices with the weight of the index as their key

The run time given is $O(E)$

They break it down as follows:

$O(1)$ to find the vertex with smallest weight
       - I understand this part since we scan at most $W$ array slots to find a non-empty list and $W$ is constant.

$O(1)$ for decrease key
     - This makes sense as far as the actual removing of a link from one list and inserting it into another

My question is about the decrease key step.  Say for example we pull the node $A$ from the 3rd slot, that is the next node to be processed.  We look at $A$'s adjacency matrix and see that it has edges to $B, C, F$.  Since we are using linked lists we have no choice other than to look at all array slots from $4$ to $W$ and see if we can find the vertices listed in the linked list for that particular index. Then delete the vertex from its current list and add it to the correct list if we find it. Possible search time = $O(V)$ [since we store vertices in the linked lists and could search all before finding our desired vertex] not $O(1)$.

Since each decrease key takes $O(V)$ and we process all vertices running time = $O(V^2)$.

If anyone could let me know where I am going astray in my analysis I would greatly appreciate it.


texts: Decidability of equality of expressions involving exponentiation

texts:
Let's have expressions that are finite-sized trees, with elements of $\mathbb N$ as leaf nodes and the operations {$+,\times,-,/$, ^} with their usual semantics as the internal nodes, with the special note that we allow arbitrary expressions as the right-hand side of the exponentiation operation. Are the equality between such nodes (or, equivalently, comparison to zero) decidable? Is the closure under these operations a subset of algebraic numbers or not? (Turns out, it isn't: https://en.wikipedia.org/wiki/Gelfond%E2%80%93Schneider_theorem, which disallows an easy reduction to solutions about algebraic numbers.)

This question is similar to this: Decidability of Equality of Radical Expressions but with the difference that here the exponentiation operator is symmetric in the type of the base and the exponent. That means that we could have exponents such as $3^\sqrt 2$. It isn't clear to me, whether allowing exponentiation with irrationals retains the algebraic closure.

This question is also similar to Computability of equality to zero for a simple language but the answers to that question focused on the transcendental properties of combinations of $\pi$ and $e$, which I consider out of scope here.


texts: Context-free grammar for $L=\{0^n1^{2n} \mid n \geq 0\}$

texts:
How can I express this language $L = \{0^n 1^{2n} \mid n ≥ 0\}$ as a context-free grammar?

I am new to this field and I am not sure what should I do. Please help me.


texts: Creating a grammar for a a language for instructions, with repititions

texts:
I have a language that consists of instructions for movement on a 2D-plane. You start at coordinate [0,0]

The instructions

DOWN 1 UP 10 LEFT 5 RIGHT 1

means you will move to coordinate [9,-4].

There is also the REP command which means you perform the instructions inside the REP X times.

For example

REP 2 "DOWN 1 FORWARD 10 LEFT 5 RIGHT 1"

means you will move to coordinate [18,-8].

I came up with this grammar

Instruction --> DOWN Num | UP Num | LEFT Num | Right Num | REP Num " Sequence "

Sequence --> Instruction Sequence | Instruction

Which works to some extent. However I want to be able to parse the grammar using recursive descent and if I am not not mistaken you can't do that with grammars that use left recursion.

Any ideas on how I could alter my grammar to make it suitable for recursive descent?


texts: What are the rules for positive recursive types in dependent type theory?

texts:
I've recently started independently learning type theory, using a combination of papers found online and ncatlab.org (but have not worked with category theory), and am about to start reading TAPL.

I'm interested in understanding how recursive types can be substituted for inductive types in dependent type theory (we assume dependent sums, dependent products, identity types and finite types 0, 1, 2 in our background theory), however I am unable to find a definition for recursive types that doesn't use unrestricted fixpoint operators and hence lack strong normalisation.

I've attempted to do this myself, but the dependent eliminator seems slightly too weak, and a restriction on if b then x else y such that the boolean expression is evaluated before x and y can be reduced seems to be required for normalisation.

$$\frac{A:\text{Type} \vdash F(A):\text{Type} \\ A\text{ is positive in }F(A)}{\mu A.F(A):\text{Type}}$$

$$\frac{a:F(\mu A.F(A))}{S(A):\mu A.F(A)}$$

$$\frac{B:\text{Type}, b:B \vdash C(b,B):\text{Type} \\ B:\text{Type}, e: \prod_{b:B}C(b,B))\vdash R(B,e) : \prod_{f:F(B)}C(f,F(B))}{rec(R):\prod_{a:\mu A.F(A)}C(a, \mu A.F(A))}$$

$$\frac{B:\text{Type}, b:B \vdash C(b,B):\text{Type} \quad a:\mu A.F(A)\\ B:\text{Type}, e: \prod_{b:B}C(b,B))\vdash R(B,e) : \prod_{f:F(B)}C(f,F(B))}{rec(R)S(a)=R(\mu A.F(A),rec(R))a:C(a, \mu A.F(A))}$$

Where A is positive in F(A) precisely when A does not occur in any type indexing any dependent product types in F(A).

Is my formulation correct? What is the correct way to formulate rules for normalising recursive types, and are there any references that I could look at that expand on these?


texts: How does a computer remember the address of a data variable in a program, in the main memory?

texts:
Suppose I write a program as below:

int main()
{
int a = 3;
int b = 4;
return 0;
}

Suppose the computer stores the address of 'a' as 0x00104. How does it associate 'a' with 0x00104?


texts: Can someone help me understand cache conscience radix sort? (excerpt from journal article attached)

texts:
Article:

CC-Radix: a Cache Conscious Sorting Based on Radix sort

(IEEE 2003)

I'm trying to figure out what the author means by this section:

  Explanation of CC-Radix For clarity reasons, we explain the recursive
  version of CC-Radix sort as shown in Figure 3. However, we use the
  iterative implementation of CC-Radix for the evaluations in this paper
  because it is more efficient. The parameters of CC-Radix are bucket, which
  is the data set to be sorted, and b, which is the number of bits of the
  key that still have to be sorted. Constant b is explained below.

CC-Radix(bucket, b)

￼if fits in cache (bucket) then
   Radix sort(bucket, b )
￼￼￼￼￼￼else
   sub-buckets = Reverse sorting(bucket, )
   for each sub-bucket in sub-buckets
      CC-Radix(sub-bucket, )
endfor
￼￼￼￼￼endif
end

  Figure 3. Pseudocode of CC-Radix The algorithm starts by checking
  whether the data struc- tures to sort bucket fit in cache level Li.
  Those data struc- tures are vectors S and D and the counter vectors C, one
  for each of the digits of the key. If so, CC-Radix calls Radix sort.
  If the data structures do not fit in cache level , the algorithm
  partitions that bucket into sub-buckets by sorting the bucket by the
  most significant digit using the counting algorithm (explained above).
  Here, we call this process of partitioning, Reverse Sorting, and it
  takes into account the computer architecture of the machine. For each
  sub-bucket, the CC-Radix sort is called again. Note that the first
  call to the routine processes the com- plete data set. Further calls
  to the routine process sub- buckets. Note also that certain subsets of
  the data may need more Reverse sorting calls than others depending on
  the data skew.

  Now, we explain the details of Reverse sorting and the sizing of the
  parameters of Radix sort. Reverse sorting. After each call of Reverse
  sorting, the number of digits that remain to be sorted for a specific
  sub- bucket is decremented by one.

I don't understand the "Reverse Sorting" part of this - how is that supposed to work?

I know this is a long shot, but I'm really stuck on what they mean.  Any help is appreciated!


texts:
Given two equally sized sets, $P$ of Boolean predicates and $E$, I want to decide if there exists a bijective function $f: P \rightarrow E$, such that
\begin{align}
\forall p \in P \; p(f(p))
\end{align}
It seems like a special case of having a weight matrix $W$ where $w_{ij}=0$ if $P_i(T_j)$ and otherwise $1$, and then solving the general Assignment Problem.
For practical reasons calculating such a weight matrix up front is not desirable, as evaluating $p$ is not necessarily cheap.
I have also thought about whether it could be formulated as some variant of Stable Marriage Problem, where the men have a predicate that needs to satisfied instead of a ranked preference list over all women.
I don't think the proposed problem sounds very exotic, so I might just be looking in a wrong direction.


texts:
In the pseudocode guide for my syllabus, an example of a record data type is given as below:

TYPE Student
    DECLARE Surname : STRING
    DECLARE FirstName : STRING
    DECLARE DateOfBirth : DATE
    DECLARE YearGroup : INTEGER
    DECLARE FormGroup : CHAR
ENDTYPE

However, for enums and pointers it gives the following examples:

TYPE Planet = (Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune)

TYPE Pointer = ^<Type name>

There seem to be 2 inconsistencies here: the lack of the opening/closing "tag" structure from the record type, and also the use of equals signs in the enum and pointer examples.

I'n not sure if there is a conceptual difference between these types of types which explains the difference, of if it is due to an oversight on the writers of the guide.

Could someone please clarity this for me and explain the conceptual difference if there is one?


texts: Gale-Shapley Stable matching where one man's preference list changes

texts:
Given $n>1$ women and men. Let $M$ be the stable matching given by the Gale-Shapley algorithm with men proposing. Is there a stable matching instance such that:
changing one man's preference list results in matching $M'$ - a stable matching given by the Gale-Shapley algorithm with men proposing under this slightly altered preference list - where every man strictly prefers his partner in $M$ over his partner in $M'$ (according to their original preference list used to get matching $M$).
The answer should be yes but I'm not sure how or why. The first thing that came to mind is to try to use induction. I came up with a scenario for $n=2$ but I don't know how to extend it to greater $n$.


texts: Trying to detect recurring events at certain intervals, e.g. daily, weeekly, monthly, annually

texts:
I don't have much experience with ML but am looking for some guidance on where I should start.

I have timestamp data mapped to a certain category, e.g. travel, food, groceries, etc.

Judging by some other posts and answers, would it be correct to break the data into these intervals (day, week, month, year) and then try to detect patterns across the intervals?  Are there any particular approaches or algorithms I should investigate first?  Thanks!


texts: Determining cycle time and and hold time in logic circuits

texts:
First I have general question. In a circuit with both logic and D edge flip flop does hold time have to satisfy $t_{hold} < t_{setup}($D-FF$) + t_{pd-min}$(Logic),

or is it enough that $t_{hold} \le t_{setup}($D-FF$) + t_{pd-min}$(Logic) ?

Also i have a question about a specific circuit:

with the following times:

the question is how much time at least, before and after the fall of the clock does the Input have to be steady? when it is given that $t_{hold}=8ns$

Now, from what I know, the input has to be kept steady for at least $t < t_{pd-min}$(Logic) +$t_{setup}$ time. So I don't understand how $t_{hold}$ comes into consideration here. I'll be glad if could explain.


texts: Advantage of the Monte Carlo method over a regular periodic sampling

texts: I am unclear on when to use the Monte Carlo random sampling method for algorithm design. The classic example that I keep seeing is using random points within some bounding rectangle to determine the area of some irregular figure. Wouldn't a regular periodic sampling provide more repeatable results for this application then using the Monte Carlo (random sampling) method?


texts: Performance of smooting vs viterbi algorithm with HMMs

texts:
To experiment, I implemented a discrete HMM; the transition matrix and emission model are randomly, uniformly generated. Then, a sequence of random states and emissions are produced by the HMM. Then I run smoothing (forward-backward algorithm) to identify the most likely states at each time. Finally I run the viterbi algorithm to identify the most likely sequence.

Because I know the true sequence of states, I can compare how well the two algorithms predict the actual sequence. With #states = 2, #emission types = 2, and sequenceLength=100, viterbi gets about 60% of the states correct, while smoothing gets about 73% correct.

Does this make sense? My prior was that viterbi would get more correct than smoothing, but I'm relatively uncertain. Also, it seems disappointing that viterbi is only 10% better than random guessing. I'm wondering if there's a bug in my implementation.

Any confirmation one way or the other would be greatly appreciated.


texts: Comparing coefficients of boolean functions

texts:
Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the set of $i$ such that $a_i=1$ and $\bar{1}_a$ is the complement of $1_a$. How do you represent $c_a$ in terms of $p(a)$?

Is for all $b\in\{0,1\}^n$, $c_{b} = \sum_{a\in\{0,1\}^n}(-1)^{<b,a>}p(a)$?


texts:
This post and this post indicate that when the dimensionality gets higher, KDTree gets slower.

Per scikit-learn doc, the KDTree becomes inefficient as D(dimensions) grows very large (say, $D>20$): this is one manifestation of the so-called “curse of dimensionality”.

Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?


texts: What are the major differences between row polymorphism and subtyping

texts:
I hear often that row-polymorphism is a better approach than subtyping, but I have difficulty finding anything comparing them in detail. I'm especially interested in the perspective of a user of the system.

I did come across this blog post, but it leaves me with more questions than before. For example, it makes a claim that a system with subtyping will assign one type, whereas a system with row typing will assign another; does that mean that if a system that purportedly has subtyping assigns the "row typing" type, that it purports incorrectly?

The one major difference I do see is that row typing makes it possible to align the types of arguments (that is, write a two argument function that concerns itself only with the a field of its arguments, but requires that its arguments have the same fields).


texts: Is the problem of evaluating a boolean formula on a given assignment P-complete?

texts:
I know that the CIRCUIT VALUE problem is P-complete.
In the CIRCUIT VALUE problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given circuit on the given input.

I wish to know if the problem of evaluating a Boolean formula on a given assignment is also P-complete. From one hand, it seems that a Boolean circuit and a Boolean formula are very similar objects. Also, the proof of that CIRCUIT VALUE is P-complete results from the Cook-Levin problem, the same theorem that actually shows that SAT is NP-Complete, so I don't see a reason why this problem won't be P-Complete.
From the other hand, it seems pretty easy to evaluate a Boolean formula in logarithmic space, so if this problem is indeed P-complete I think it would imply L = P which is unknown.

So I think I'm missing something.. any ideas people?


texts: simple question about epsilon and estimation turing machines

texts:
i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple limit: $lim_{n \rightarrow \infty} {3-\frac{7}{n}}$.

now i used $3 - \epsilon$ and i am trying to show that  there can't be any $\epsilon>0$ so that the estimation of the algorithm is $3-\epsilon$, because there exists a "bigger estimation" - and this is the part i am not sure about, what is the correct direction of the inequality? $3-\frac{7}{n} > 3 - \epsilon$ or the opposite? i am trying to show that the estimation ration is close to 3.

i think that what i wrote is the correct way, but not sure. would appreciate knowing what is correct in this case. thanks.


texts: Algorithm to find out the number of times a number occurs consecutively in an array in a range specified

texts:
I have an array say

8 3 5 4 4 4 4 4 3 2 7 11 12 7 7 7 7 1 2

total =17 elements
now you are given a range say [2,11] both included ,now you have o find out the element that has occurred the max number of times and the number of times it has occurred

A simple traversing through the array in the range  and keeping the track of the each element is one solution but time complexity is O(N) and if we are given N queries time complexity = O(N^2). Any faster algo than this ?


texts: Prove the following language is in L (LogSpace)

texts:
I'm trying to prove the following language is in $L$ (decided by a TM in $O(\log n)$ space):

$$A = \{ (C,x) \mid  C(x)=1\text{ and $C$ is a Boolean formula with depth }\log(n)\}\,,$$
where $n = |(C,x)|$. Equivalently, $C$ can be a Boolean circuit with maximum fan-out of $1$.)

Checking if a word $w$ is in "the right format" (meaning: $w=(C,x)$ for some $C$ Boolean formula/circuit, $x$ – input) takes $O(1)$ space. I'm not sure on how to check the value of the formula (thought of using recursion, but not sure how) such that it will need only $O(\log n)$ space. Also, how can I check that the depth of the circuit is $\log n$?


texts:
In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states

  $P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$

"Accepted in polynomial-time" is defined by:

  $L$ is accepted in polynomial time by an algorithm $A$ if it is accepted by $A$
      and if in addition there exists a constant $k$ such that for any length-n string $x\in L$,
      algorithm $A$ accepts $x$ in time $O(n^k)$.

"Accepted" is defined by:

  The language accepted by an algorithm $A$ is the set of strings
          $L = \{ x \in \{0,1\}^* \mid A(x) = 1 \}$,
      that is, the set of strings that the algorithm accepts.

But what if we take $k = 0$, and algorithm $A(\cdot) = 1$, which just returns 1 for everything?
Wouldn't that mean, that $P$ is just class of all languages?


texts: pseudo-polynomial reduction from 3-Partition to Partition

texts:
A problem $\Pi'$ is pseudo-polynomially reducible to the problem
$\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially bounded time, such that, given the solution $S_I$ to $I$, the solution $S_I'$ to $I'$ can be found in pseudo-polynomial time.

It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete.

And it is easy to show that "3-Partition $\leq_{pp}$ Partition."

Hence, I can conclude that Partition is strongly NP-complete. (However, we already know that Partition problem is ordinary NP-complete.)

Am I missing something!?


texts: Why do some architectures use a CMP instruction before branching while others just branch?

texts:
My initial guess is that you will have more instruction space for the immediate in your branch instruction when you first use a CMP instruction. However, you have to use 2 instructions each time you want to branch: a CMP and then the branch instruction.

So are there any advantages to using CMP?


texts:
Possible Duplicate:
  Restricted version of vertex cover

Suppose we have a $(A,B,E)$ bipartite graph and a positive integer k. Suppose that k is smaller than $|A|$ and we want to find one of those k element subsets of $A$ which covers the most points from $B$. I can only come up wirh exponential algorithms. Is this in $P$?

Also is mixed integer programming for maximal flows in $P$? It can be easily formulated as such.


texts: Can somebody please explain what are these variables doing here?

texts:
I have this algorithm:

I understand overall what's happening here, we're shrinking the blossoms (odd cycles) to end up with a bipartite matching problem, and then opening them again to get a maximum matching in this graph. But I don't understand it algorithmically, like what do the variable considered and label represent. Can somebody please clarify that?
Edit This is taken from chapter 10 of 'Combinatorial Optimization: Algorithms and Complexity' book by Papadimitriou and Stieglitz.


texts: Check whether an undirected graph contains a simple cycle of length four using the "Squares" method

texts:
The following problem is exercise 4.3 of the book "Algorithms" by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

  Squares. Design and analyze an algorithm that takes as input an undirected graph $G = (V,E)$ and determines whether $G$ contains a simple cycle (i.e., a cycle which does not intersect itself) of length four in $O(|V|^{3})$ time.

This can be solved by checking for each pair of vertices $u$ and $v$ whether they share at least two common neighbors; see the answer.

However, in the book, the authors gave a single-word hint: Squares.

Following the hint, I square the adjacency matrix $M$ of $G$ twice (i.e., $M \to M^2 \to M^4$) and check whether $M^4[i][i]$ is true for some $i$. But this attempt fails because it produces "false positives" by treating $a-b-a-b-a$ or $a-b-c-b-a$ as cycles of length four.

How to fix the "false positives" in the squaring method above?


texts: How can unifying 2 sentences in first-order logic result in a variable becoming 2 different things?

texts:
I'm working on a program which must use inference in first-order logic, and everything is working great except for 1 thing which I don't understand.

The book I'm using, "Artificial Intelligence A Modern Approach" by Russell and Norvig, shows a proof on page 349 which has me confused.
They combine the two following sentences:
~Loves(x,F(x)) v Loves(G(x),x)
~Animal(x) v Loves(Jack,x)
And they combine into:
~Animal(F(Jack)) v Loves(G(Jack),Jack)

This makes absolutely no sense to me because the variable "x" becomes both "F(Jack)" and "Jack", and that seems wrong to me.

Using the Unify function which I created by following the pseudocode provided in the book returns a failed substitution, but if the combination of the previously mentioned sentences is correct then what kind of substitution would need to be returned? (I know it's not just {x/Jack} because that would result in the sentence "~Animal(Jack) v Loves(G(Jack),Jack)", Animal would be missing the function F as shown in the example.)

Any help would be extremely appreciated!


texts: Enumerate partitions of a set with blocks of equal size

texts:
Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$?

In The art of computer programming (Fascicle 3B) by Knuth, there's a mention of an algorithm by Ruskey that can list all partitions with $c$ blocks. I could just use this algorithm and discard all partitions that violate the constraint on the  equal size of blocks, but I would visit many useless partitions.

Is there a better way?


texts: Is it possible to reconstruct graph if we have given matrix of shortest pairs

texts:
I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally:

Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such that from this graph we only have given matrix $g$ of size $N \cdot N$ elements, such that $g(i, j)$ gives the shortest path between nodes $i$ and $j$, note that it doesn't mean that nodes $i$ and $j$ are directly connected with edge.

What I think

We can say that node $x$ belongs on the path from node $a$ to node $b$ if and only if: $g(a,b) = g(a, x) + g(x, b)$.

If we fix nodes $a$ and $b$ in $O(N \cdot N)$ and we iterate over all other nodes, we will get total complexity of $O(N^3)$.

Is it possible to reduce this complexity to $O(N^2)$.

Thanks in advance.


texts: Formal proof of language accepted by a specific CFG

texts:
Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules:
\begin{align}
&S \to aS \mid B \\
&B \to abBc \mid \epsilon
\end{align}
Please provide a formal proof for the following claim:
$$
L(G) = \{ a^i (ab)^j c^j : i,j \in \mathbb{N} \}.
$$


texts:
I've looked through all the other similar questions, but I don't feel like I understood exactly what I'm supposed to do with my case, so I'm hoping I'm not the only one.

In an exercise I'm doing, I'm told to consider a computational system with a direct mapping cache, that can store 16 blocks of 4 bytes, and 32-bit addresses.

I'm then given 8 addresses in hexadecimal, and I'm supposed to say what will be the content of the 16 blocks.

One of the adresses in question is: 0xC4001234
I've calculated the tag as 21 bits, set being 4 bits, and offset being 5 bits.
Yet, I'm not sure how I'm supposed to know in which block it will be.
My teacher's Powerpoint said that the "set" is used to locate the block in the memory, but I'm not sure how. I thought I'd convert the address into binary and use the 4 bits to calculate where the block will be, but then I have some adresses that match in the same block.

I was wondering if anyone could show me how to do this one address, so I can do this exercise and hopefully pass my exam. Thanks.


texts:
How can I prove that $\mathsf{DTIME}^{\mathrm{Htm}}(n^2)$ is contained in $\mathsf{DTIME}^{\mathrm{Htm}}(n^3)$?

(sorry about how it is written. I mean the set of languages decided by a deterministic TM with an oracle to $\mathrm{Htm}$ in $n^2$ time and $n^3$ time).

If someone can please write the proof, it will be great.


texts: Is it possible to figure out cache size and associativity using the length of offset, index, tag fields?

texts:
I have a question where I am asked to find the size of a cache. I am given the following info:

a) the length of a memory address

b) the number of bits for offset, index, and tag fields.

I know I can use the numbers of bits to easily solve the line size and the number of sets. But as far as I know, there is no way for me to find the cache size without knowing the associativity, which we are not given.

Is there any way to find the associativity from the length of the memory address and the number of tag/index/offset bits?

Although it is tempting to assume the cache is direct mapped because we are not given associativity, the next question asks what the cache mapping scheme is and this prof is notoriously tricky, so I'm assuming there's more to it.


texts: Essential difference between Assembly languages to all other programming languages

texts:
I understand that any assembly programming language has so little abstraction, so that one who programms with it (OS creator, hardware driver creator, "hacker" and so on), would have to know the relevant CPU's architecture pattern very well.

For me, this requirement to know the relevant CPU's architecture pattern very well is the essential difference between assembly programming languages to the rest of ("higher") programming languages that don't require that, so we get:

nonassembly/high programming languages
assembly/low programming languages
machine code languages which usually won't be used as programming languages but theoretically can be used as such (and as any other type of computer language for that matter)

Is this the only essential difference, if not, what else there is?


texts: Complexity of a Turing Machine when changing its alphabet to binary

texts:
I found in 'Computational Complexity: A Modern approach' Book the following statement that i dont quite understand its proof:

  For every f : {0, 1}∗ → {0, 1} and time-constructible T : N → N, if f is computable in time T(n) by a TM M using alphabet A, then it is computable in time 4log|A|T(n)by a TM M ̃ using the alphabet {0,1,Blank,◃}.

The proof is on the link :

First Part of proof

Second Part

So basically if we have a running time of T(n) on a certain alphabet A and we wanna switch to binary.. we gonna have to multiply it by log(|A|) (log of base 2, the number of bits to represent an element from A) because every step will be multiplied by the number of bits used to represent the element.

But in the proof, starting from the second paragraph, i dont really understand what they say and how they end up with the '4' in '4log|A|T(n)'.


texts:
We know $UP\subseteq NP\subseteq PP$.

  Is $UP^{\oplus P}\subseteq NP^{\oplus P}\subseteq PP^{\oplus P}$?

I think the first $UP^{\oplus P}\subseteq NP^{\oplus P}$ is straightforward since whatever queries an $UP$ machine can do we know an $NP$ machine can do.

  How to show second $NP^{\oplus P}\subseteq PP^{\oplus P}$?


texts: How to compare algorithms in class NC time complexity with other classes?

texts:
I know these relations :

\begin{gather}
\mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \dots \subseteq \mathrm{NC}^i \subseteq \dots \subseteq \mathrm{NC} \\
\mathrm{NC}^i \subseteq \mathrm{AC}^i \subseteq \mathrm{NC}^{i+1} \\
\mathrm{NC}^1 \subseteq \mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{AC}^1 \subseteq \mathrm{NC}^2 \subseteq \mathrm{P}
\end{gather}

But I don't know how to compare an algorithm with time complexity of $\mathrm{NC}^i$ to an algorithm with Polynomial complexity?

For example, Topological sort $\mathrm{NC}^2$ with BFS $\mathcal{O}(|V| + |E|)$


texts: Error in pivot selection algorithm for merge phase [Sorting]

texts:
In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart on the other GPU-partition). That pivot element is crucial for being able to merge the two partitions, given that we have already sorted them on each GPU locally.
However, the pseudo-code for that pivot-selection, as shown in the paper, doesn't seem to reflect the whole truth since when implementing it 1:1, the selected pivot element is off by some elements in some cases, depending on the input - the amount of elements to sort and therefore the amount of elements per partition (the chunk of data that each GPU gets).
To get more specific, the problem is - to my understanding - that the while loop is exited too early due to the stride being reduced down to zero before the correct pivot element has been found. In general, the approach is binary search-like, where the range of where the pivot can fall, is halved each iteration.
Can anyone spot what needs to be done here?
Here is a C++ implementation of the pivot selection:
size_t SelectPivot(const std::vector<int> &a, const std::vector<int> &b)
{
  size_t pivot = a.size() / 2;
  size_t stride = pivot / 2;
  while (stride > 0)
  {
    if (a[a.size() - pivot - 1] < b[pivot])
    {
      if (a[a.size() - pivot - 2] < b[pivot + 1] &&
          a[a.size() - pivot] > b[pivot - 1])
      {
        return pivot;
      }
      else
      {
        pivot = pivot - stride;
      }
    }
    else
    {
      pivot = pivot + stride;
    }
    stride = stride / 2;
  }
  return pivot;
}

P.S.: I tried ceiling the stride in order to not skip iterations when the stride is odd, but this introduced the issue of moving out of bounds of the array and even after handling those cases by clipping to the array bounds, the pivot was not always correct.


texts:
I need an $O(|V||E|)$ algorithm to detect if a graph has a minimum spanning tree with diameter 3.
This paper mentions that it is possible for any diameter by finding the vertex 1-center which can be done using Floyd's algorithm, but I need something much simpler only for the case of diameter 3.


texts: Simplification of regular expression and conversion into finite automata

texts:
This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. I want to create an FA for the regular expression

$\qquad \displaystyle (a+b)^* (ab+ba)^+a^+\;.$

My first question is that how we can simplify this expression? Can we we write the middle part as $(ab+ba)(ab+ba)^*$? will this simplify the expression?

My second question is whether the automaton given below is equivalent to this regular expression? If not, what is the mistake?

This is not a homework but i want to learn this basic example. And please bear me as a beginner.


texts: How to think when devising a TM that decides if a DFA rejects some string?

texts: The title should explain my question thoroughly enough. I can't seem to get started anywhere. Intuitively it seems like some kind of brute-forcing would work i.e if the DFA has the symbols $\Sigma$ you would simply be passing strings from $\Sigma^*$ until the DFA rejects. What would even be the time complexity of this though? Or am I completely out and about?


texts:
I had a problem of generating project network graph (like there and there) from list of activities and their dependencies.

Informal description:

Every activity is represented as edge of directed acyclic graph (DAG), so such layout of the graph is called activity-on-edge, as opposed to activity-on-node layout. If the dependency of two activities can not be represented as single vertex, the zero-weight edge (drawn as dotted line) is added to satisfy this dependency.

There is example of activities and dependencies table. In addition, the weights of activities are given.

Desired project network graph looks like this:

Formal description:

Given a list of directed edges names, their weights and list of their predecessor edges (so there is a path between head of predecessor edge and tail of listed edge), build a directed acyclic graph having exactly one vertex with no predecessor edges (source) and one vertex with no successor edges (sink).

Question:

So, the problem of generating project network graph and making some analysis of related project looks so easy if we represent activities not as the edges of DAG but nodes (e.g. activity-on-node layout). But is there an algorithm solving this generating problem? Could we use prepared activity-on-node graph to generate corresponding activity-on-edge graph?


texts: Why does the GS1 DataMatrix encode diagonally instead of vertically or horizontally?

texts:
Perhaps this is the wrong exchange, so if there is a better place to post this please tell me!

The DataMatrix encodes diagonally in a sort of zig zag pattern, as shown below.

Why don't they encode horizontally or vertically, like how it's done in QR Codes? If they did this it would appear to eliminate the need for confusing diagonal wrapping. QR code encoding algorithm for reference below:


texts: Is every decidable language recognizable by a Turing Machine space-bounded by some f(|w|)?

texts:
The negative answer to decidable = non-contracting grammar? suggests the following question:

Is there a decidable language that can be recognized only by a space unrestricted Turing Machine (i.e. with infinite tape but in finite time)?

This is, are there words, w, in a decidable language for which cannot be determined a bound f(|w|)?


texts: Significance of quantifier ordering in quantified boolean formulas (kQBF vs. QBF)

texts:
I am studying solvers of quantified boolean formulas (QBF) as a generalization of SAT solving. The standard DIMACS format of SAT specification is extended to QDIMACS, which adds "a ..." and "e
..." lines denoting which variables are to be existentially quantified and which variables are to be universally quantified.

For instance, a simple QDIMACS input such as:

p cnf 2 3
a 1 0
e 2 0
1 2 0
-1 0
-2 0

...would be correspond to the formula $\forall x \exists y \ (x \lor y) \land \neg x \land \neg y$ where $x$ and $y$ range over $\{T, F\}$. SAT is an instance of QBF where all the variables are existential.

The above is an example of 2QBF, where we have two layers of quantifiers. A more complex QDIMACS problem with alternating quantifiers might be:

p cnf 2316 15282
e 1 17 2 18 3 19 4 ... 0
a 1598 1599 1600 1601 1602 1603 0
e 65 81 66 82 67 83 68 ... 0
a 1610 1611 1612 1613 1614 1615 0
e 193 209 194 210 195 211 196 ... 0
a 1616 1617 1618 1619 1620 1621 0
-2 -18 0
-3 -19 0
-4 -20 0
-5 -21 0
-6 -22 0
-7 -23 0
...

Anyways, on to my question. I don't understand why 2QBF != QBF. It seems to me for any formula $F$ and variables $x$, $y$ ranging over the booleans that $\forall x \exists y \ F$ is equivalent to $\exists y \forall x \ F$.

To demonstrate my thinking, I will consider the Shannon expansion of the universal quantifier.

\begin{align}
\forall x \exists y \ F \iff& (\exists y \ F[x \to T]) \land (\exists y \ F[x \to F]) \\\\
\exists y \forall x \ F \iff& \exists y \ (F[x \to T] \land F[x \to F])
\end{align}

Suppose $\exists y \ (F[x \to T] \land F[x \to F])$ is satisfiable. Then the same assignment would extend to both $\exists y \ F[x \to T]$ and $\exists y \ F[x \to F]$.
Suppose $\exists y \ (F[x \to T] \land F[x \to F])$ is unsatisfiable. Then at least one of $\exists y \ F[x \to T]$ or $\exists y \ F[x \to F]$ is also unsatisfiable.

Thus $\forall x \exists y \ F \iff \forall y \exists x \ F$.

A similar question has been asked before here, but there appears to be ambiguity over the domain of the quantifiers. They should range only over true or false and not over other mathematical objects or propositional variables. This is in correspondence to the standard interpretation of the SAT problem.

For instance, $\forall x \exists y \ x \leftrightarrow y$ would not be true since setting $y$ to $x$ is not valid.

Is my interpretation of QBF correct? Is there a counterexample I'm missing?


texts: Why does the converse of the clock condition imply that any two concurrent events occur at the same time?

texts:
In Lamport's paper, Time, Clocks, and the ordering of Events in a Distributed System he says that the converse of the clock condition does not hold and if it did, we could expect concurrent events to occur at the same time. I am not sure how he arrives at this conclusion.
The Clock Condition is:
For any events a, b in a distributed system:
if a -> b then C(a) < C(b).
The converse does not hold:
if C(a) < C(b) then a -> b.
Where C(n) assigns a logical clock number to any event in the system. Logical clock numbers monotonically increasing values for each process in the system and two conditions hold in order for partial orderings given that the clock condition is true:

if a and b are both events in a process P_i and a comes before b, then C_i(a) < C_i(b)

if a is a sending event in P_i and b is a receiving event in P_j then C_i(a) < C_j(b).

Intuitively I can see why the converse does not hold. It is possible in the system of logical clocks that C(a) < C(b) when we do not have a partial ordering that guarantees the relation a -> b. But I have no clue why the converse being true would imply that any two concurrent events occur at the same time.


texts:
I know that the grammar

<expr> = <expr> + <expr> | <num>
<num> = 0|1

is ambiguous because it cannot decide between (1+1)+1 or 1+(1+1).  However, that would also mean that

<expr> = <expr> + <num> | <expr> * <num> | <num>
<num> = 0 | 1

would also be ambiguous because it couldn't tell if 1+1*1+1 is (1+1)*(1+1) or ((1+1)*1)+1.  Or does it distinguish between these by terminating the interpretation as soon as it finds one match?

If it does terminate on a first match, then would 1+1*1+1 necessarily get interpreted as the first option since it is possible to interpret the "main operation" as being +?


texts: Minimum hamming distance of multiple binary words

texts:
Our task is to compute the minimum hamming distance for the following 16-bit words:

0000000000000000
0011001100110011
0101010101010101
0000111111110000
0011111111000000
1100110000000000
1111111111111111

This minimum distance is defined as the minimum of all distances between every combination of two of these bitstrings, so the first approach would be to calculate all of these individual distances. I'm pretty sure this is not the right way to do it, since there are 21 possible combinations.

Then I came across this answer on StackOverflow which says that:

  We have a theorem that d_min=weight(sum(all codes)); weight is the
  number of non zeros in the result string . In your example modulo add
  all string codes like first column of all and second....... then we
  get code as [ 0 0 1 1 0 ], weight of this is 2 ( no. of non zeros),
  i.e the minimum distance of hamming code

but is that really true? If we for example take the three bitstrings

0000
1000
1110

the minimum hamming distance is obviously 1 but the calculation based on that answer would result in 0110 and would suggest that the minimum distance is 2. Am I right about this and is that answer wrong? Or did I miss something really simple that I'm just not noticing?

I also read this answer which - if I understood it correctly - states that there is no simple way of finding the result.


texts: Example of typed lambda term with recomputed argument

texts: What is an example of a typed lambda term $\lambda x.\phi : A \to B$ and a term $a : A$ such that, when $\beta$-reducing the term $(\lambda x.\phi)(a)$, the argument $a$ must be repeated/recomputed several times?


texts: Given a pair of coordinates $(x,y)$ in 2D, find the points inside the circle $C((x,y),R)$

texts:
Suppose that there are a set of $n$ points $P = \{(x_1,y_1), \dots, (x_n,y_n)\}$ in 2D.

Given two coordinates $(a,b)$ and a number $r \in \mathbb{R}$, is there an algorithm with $O(|Q| + \log n)$ running time that can find the point set $Q \subseteq P$ containing those points of $P$ that are inside the circle with center $(a,b)$ and radius $r$?

(That is, I want to find all points in $P$ with coordinates $(i,j)$ such that $(i-a)^2 + (j-b)^2 \leq r^2$.)

[I originally asked about a solution with running time $O(\log n)$, but as Pål GD correctly points out, the answer to that question was "not possible".]


texts: Complexity of Alpha-Beta pruning with optimal move ordering

texts: I originally read that Alpha-Beta pruning has time complexity of $O(b\ ^{m/2}\ )$ with perfect ordering (where b = branching factor, m = maximum ply depth) but have recently come across claims that this can be reduced to $O(2\ ^{m/2}\ )$ with optimal ordering. Does anyone know of a proof for this claim?


texts:
I have two pseudorandom generators $G_1$ and $G_2$ from $k$ bit to $2k$ bit. I have another PRG $G_3$ from $k$ to $2k$ bits. Now I buildup a new function from $k$ to $4k$ as follows:

Let $x$ be $k$ bit then apply $G_3$ on it on $x$. Then let output by $y$.   Apply $G_1$ on first $k$ bits and $G_2$ on last $k$ and join the resulting output. Then resulting function is a PRG. How do you prove this?


texts:
I have a question as follows

  Consider the relations $r1(P, Q, R)$ and $r2(R, S, T)$ with primary keys $P$ and $R$ respectively. The relation $r1$ contains $2000$ tuples and $r2$ contains $2500$ tuples. The maximum size of the join $r1⋈ r2$ is :

My attempt - Suppose all value of $R$ in $r1$ are same.  Then it should be $4499$.

But it's given $2000$. Am I missing something?


texts: Proving undecidability for a language which contains string with certain syntax

texts:
Lets say we have the following problem:

$$\mathcal{L}_1 = \{\langle \mathcal{M} \rangle | \mathcal{M}\ \text{is a Turing machine and $\mathcal{L}(\mathcal{M})$ contains a string with exactly three zeros}\}$$

We would like to prove that $\mathcal{L}_1$ is undecidable. I would generally use Rice's theorem to prove that a language is undecidable, but in the present case, we aren't dealing with a semantic property of the language but rather its syntax. In cases where we have to prove based on the language's construction, how would the process look like and differ from proving with Rice's theorem?


texts: Does a generator really stops the execution at the machine code level, and does it not use the stack?

texts:
Never have I heard of a partially executed function before.  But it seems the idea of it has been out for some time. Does a generator really stop execution at the machine code level, and that next time when the iterator is invoked, then there is a jump back to that machine code location to continue the execution?

Or is it done by having some private variables and states to control what to return? Is stopping execution of machine code and resuming to that location possible?

It seems quite strange, as

it differ from mathematics for what a function is. (in math, there is no partially executed function).
the traditional function will add to the stack, and once finished, everything is popped from the stack. But the generator is like a function that stays... so nothing is popped from the stack. So does it use something other than the stack for memory? (the heap?)

Example: JavaScript ES6 Generator:

function* generator() {    // note the asterisk
    yield 1;
    yield 3;
    yield 5;
}

const iterator = generator();

console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());

result:

{value: 1, done: false}
{value: 3, done: false}
{value: 5, done: false}
{value: undefined, done: true}

Example 2: a generator that can give an infinite number of changing color names:

function* generator() {
    const colors = ["red", "green", "blue"];
    let   i = 0;
    while (true) {
        yield colors[i];
        i = (i + 1) % colors.length;
    }
}

const iterator = generator();

console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());

result:

{ value: 'red', done: false }
{ value: 'green', done: false }
{ value: 'blue', done: false }
{ value: 'red', done: false }
  ...


texts: Training a neural network by classifying its own output

texts:
The usual way one trains a neural network is to give it some input and provide the correct classification.

But what about letting the neural network produce its own inputs, and then classifying those?

Imagine the following "algorithm".

Use a neural network to generate 2 images (random at the beginning)
Let the user pick which one is more "interesting"
Update the neural network based on the choice

Do you think that as a general principle this might make sense, i.e. there might be an approach that generates more "interesting" images over time? Has something similar been done until now? What approaches/papers/libraries might best help one achieve such a goal?


texts:
I am struggling to answer the following question:

  How many different languages over the unary alphabet {a} are
  recognized by 2-state DFAs?

According to the textbook, the hint was to first calculate the number of 2-state DFAs over that alphabet and then see if any of those DFAs accept the same language.

I am able to calculate the number of 2-state DFAs over that alphabet (Because a DFA is defined as a quintuple $(Q, \Sigma, \delta, q_0, F)$, there are:

$Q$: 1 possibility (The number of states is already defined in the problem)
$\Sigma$: 1 possibility (The alphabet is already defined in the problem)
$\delta$: 4 possibilities (2 possible input states * 1 possible input character * 2 possible output states) = 4 possibilities)
$q_0$: 2 possibilities (The start state can be one of the 2 states)
$F$: 4 possibilities ($\emptyset$, $\{q_0\}$, $\{q_1\}$, $\{q_0, q_1\}$)

Total possibilities = 4 * 2 * 4 = 32. However, I am having trouble figuring out how many of the 32 DFA's accept the same language. The textbook says that there are 12 different DFAs that need to be considered due to symmetry, yielding 6 different languages—but I do not understand how the author got to that result.


texts: Halting problem - one issue that's bothering me

texts:
To my knowledge, halting problem asks if there exists a program that decides whether a program being tested, given some input data (no matter what program it is, or what input data we give) will terminate or not. The answer to this problem is 'no'. In other words, there is no 'single' program that can verify it for all possible pairs (some algorithm, some input data).

But it doesn't mean we can't decide if particular program X will terminate or not.

I can't comment other answers yet, but one of them brought my attention:

  In practical terms, it is important because it allows you to tell your
  ignorant bosses "what you're asking is mathematically impossible".

Maybe you can tell me what that person meant? In my scenario, my ignorant boss can ask me to verify (actually, prove or disprove) if my program (that's a particular program) will terminate or not. And of course there are pairs (algorithm, input data) that can be proven to terminate (or never terminate).

The question is - can I prove it for every such pair (program, input data) separately? Even if the answer is yes, then there's a problem - there can be infinitely many 'input data'. So it's quite natural to ask - can I prove, for every algorithm, that this algorithm will terminate (or the opposite), no matter what input data I provide?


texts: Merging Sorted lists using Heap Data Structure

texts:
Suppose there are $\lceil\log n\rceil$ sorted lists of $\lceil\frac{n}{\log n}\rceil$ elements each. The time complexity of producing a sorted list of all these elements is:  (Hint: Use a heap data structure)

$O(n \log \log n)$
$θ(n \log n)$
$Ω(n \log n)$
$Ω(n^{\frac{3}{2}})$

My approach:

I know complexity of heap sort is $O(n \log n)$. But little bit confused form where to start.