texts:
I ran into a very hard question.
We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of this array. we want to finding average of all possible $c_{ij}$ in this array. if 4 basic operation in math $(+,-,*,/)$ can be done in $O(1)$. the best algorithm can be works in $O(n)$.
this example is example from my made easy preparation class. anyone can describe me in simple words how this algorithm can be?


texts: Balanced weight distribution into buckets, but with a twist (aka sharding a list into k even shards)

texts:
Is there an existing algorithm that can solve the following problem?

Problem

Given an list N comprised of integers of various values, shard the list into k buckets such that:

The sum of the integers in each bucket are roughly evenly divided (as much as possible
Only consecutive integers are placed in the same bucket

Example:

Given k (the number of buckets) = 4

List N = [4 1 2 6 19 1 10 3 2 2]

A Valid Solution

[4 1 2] [6] [19] [1 10 3 2 2]

(Since the bucket weights add up to 7, 6, 19, 18)

An Invalid Solution

[1 1 2 2 2 3] [1 4 6] [10] [19]

(Where the bucket weights would add up to 11, 11, 10, 19)

It's invalid because the buckets no longer contain only numbers that were adjacent in the original list.

Thanks!


texts: Why doesn't Knuth's linear-time multiplication algorithm "count"?

texts:
The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of logarithmically-sized multiplications. It runs in linear time.

The article acts like this algorithm somehow doesn't count as a "true" multiplication algorithm. More significantly, it's considered to be an open question whether multiplication can be done in even O(n lg n) time!

What details of this algorithm disqualify it from counting as a "true" multiplication algorithm?

My guesses are:

Precomputing the table takes more than linear time. On the other hand, it can still be done in n lg n time so that would still seem to be impressive.
Random access is somehow not allowed. But then why can other algorithms use things like hash tables and pointers?
It somehow scales wrong as you increase a machine's word size, like if you have a 256 bit machine that does 256 bit multiplications in a single instruction then there's no point to this algorithm until you have more than 2^256 elements. On the other hand, we bother with the inverse-ackermann factor in union-find.
The "is there a linear time multiplication algorithm?" question is secretly in terms of some weaker machine, but this only gets hinted at.


texts: Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)

texts:
I have some propositions regarding BSTs , please can someone confirm whether they are true or false:

Question :

  1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$

  2.We wish to find the number of children of the predecessor node of $n_1$ , with respect to inline traversal (That is the number of
  children of node $n_2(val_2)$ with $val_2$ being the greatest number
  $val_2 < val_1$)

  3.Assume for simplicity that the BST dosen't have any repetition

Proposition 1: Let $n_1$ have two children .Then $n_2$ has atmost one child i.e the number of children of $n_2$ can't be two

Proposition 2: Let $n_1$ have only one child and $n_1$ is not root ,then also $n_2$ has atmost one child.

Please ascertain whether these propositions are true , but if false can someone provide a counter example ?


texts: What did Turing mean when saying that "machines cannot give rise to surprises" is due to a fallacy?

texts:
I encountered below statement by Alan M. Turing here:

  "The view that machines cannot give rise to surprises is due, I
  believe, to a fallacy to which philosophers and mathematicians are
  particularly subject. This is the assumption that as soon as a fact is
  presented to a mind all consequences of that fact spring into the mind
  simultaneously with it. It is a very useful assumption under many
  circumstances, but one too easily forgets that it is false."

I am not a native English speaker. Could anyone explain it in plain English?


texts:
I tried posting this in the math forum but I didn't get any responses. I was hoping someone could give me some advice for how to approach the following problem.

If $n$ is a positive integer, let $S_n$ denote the group of permutations of the set $\{1,2,\dots, n\}$. For a permutation $\pi$ in $S_3$, let $e_\pi$ be the bit permutation of bit strings of length 3. For each $\pi \in S_3$ determine the number of collisions of the compression function $h(x) = e_\pi(x) \oplus x$.

Does anyone have any advice on how to approach this?


texts:
I'm struggling to understand this question using pumping lemma to prove a language is not regular. Any help would be appreciated.

Prove using the Pumping Lemma that the following language is not regular.
{0^n^3 |n ≥ 0 is an integer}

From my understanding a language isn't regular if the power is linear. But I just cant get my head around using the Pumping Lemma to prove this even after reading other examples of Pumping Lemma.
I think most expressions require you to split them into seperate parts, but I just dont understand how this is possible for this expression.


texts: Proof that a quantum computer is equivalent to some logical circuit

texts:
My question is about the quantum computer. I have tried to prove that the quantum computer is equivalent to some logical circuit.
I know this has already been proven, but I will present my attempt:

First we know that the quantum computer is composed of quantum logic gates
https://en.wikipedia.org/wiki/Fredkin_gate. According to this link, this gate is universal
So any quantum computer can be made up of those gates
Now we make a logical circuit simulating the Fredkin gate
Then each quantum circuit can be simulated by a logical circuit

Is this proof valid?


texts: Can you connect an output from a logic gate to 2 or more logic gates or inputs?

texts:
I have been given this diagram of a circuit:
https://www.google.com/search?q=full+adder+logic+gate&rlz=1C1CHBF_enCA831CA831&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjCjZzc_PbfAhXCj4MKHahtCvcQ_AUIDigB&biw=1536&bih=792#imgrc=GFIqfN5OgCdtRM:

The second XOR gate looks like its output is being connected as inputs of 2 different gates at the same time. Am I interpreting this incorrectly or is it possible to send the a single output to 2 gates simultaneously?


texts: Operating System that had the convoy effect

texts:
I read some things about the convoy effect (or problem), and at one source there was mentioned, that it was "implemented" in "historic" or very old outdated operating systems. I did a bit of research but found no OS with implemented convoy effect.
Do you know an OS wich had the convoy effect "implemented"?


texts:
I am currently studying hash tables in an introductory course to computer science. I was taught that  hash table is a data structure that associates a key to an index (a hash table) and then to the value associated to the key.

I don't understand why the hash function doesn't directly associate the key to the value


texts: Find the computational complexity of a concatenated system

texts:
I have a network which includes $L$ blocks ($B_1,\cdots,B_L$) connected one after the other. I have an algorithm having computational complexity $\mathcal{O}(N)$ which runs in each block individually.

I first run the algorithm  on $B_1$ and get the output. Based on that output, I select the second data set in $B_2$. Then run the same algorithm on $B_2$ and get the output, and so on till $B_L$. The important thing is that the present data set depends on the previous block output.

Now I want to know the overall system complexity. I guess it is  $\mathcal{O}(LN)$. Is that right?


texts: What is the significance of negative weight edges in a graph?

texts:
I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles.

So, I wonder what's the real world significance of negative weight edges? A plain English explanation would be helpful.


texts: Union of regular languages that is not regular

texts:
I've come across that question :
"Give examples of two regular languages which their union doesn't output a regular language. "

This is pretty shocking to me because I believe that regular languages are closed under union. Which means to me that if I take two regular languages and union them, I must get a regular language.

And I think I understand the proof of that : In my words, if the languages are regular, then there exist automatas that recognize them. If we take all the states (union), and we add a new state for the entry point, and we modify the transition function for the new state with epsilon, we are ok.  We also show that there exist a path from every state etc.

Can you tell me where I'm wrong, or maybe another way to approach the question.

Source of the question, exercise 4, in french.

Also, the same question is asked with the intersection.


texts: What are examples of applications of the tree decomposition of a graph?

texts: I am looking for specific applications of the tree decomposition (of a graph), because I want to motivate its existence. What are examples of problems that are more easily solvable using the junction tree of a graph (rather than tackling the problem directly on the graph)? Please, provide also the references to the papers or books that mention these specific applications.


texts: What areas in EE overlap closely with CS

texts:
I am doing bachelors in Electronics & Communication Engg.. But most of my work happened to be in Web development.. I am thinking to do my bachelor thesis which very closely overlaps with my recent work.

Are there any specific areas in CS, EE (may be Computer Networking in broad terms) that I can take up?


texts: How to transpile generic functions into language that do not support generics?

texts:
Currently, I am developing a transpiler for my own language, however, I find difficulties to transpile generic functions. For example, how would you translate the following Java-like code in to C?

interface Comparable<T> {
    boolean compare(T that);
}

class Person implements Comprable<Person> {
    public string name;
    public boolean compare(Person that) {
        return this.name.compareTo(that.name);
    }
}

// The generic function
<T extends Comparable<T>> boolean isSorted(T[] xs) {
    for(int i = 1; i < xs.length(); i++)
        if(xs[i-1].compare(xs[i]) > 0)
            return false
    return true
}

My current solution is to use Javascript prototypes. So, the code above would be translated into the following Javascript (workable in Google Chrome):

class Person { }

Person.prototype.compare = function (that) {
    return this.name.localeCompare(that.name);
}

function isSorted(xs) {
    for (var i = 1; i < xs.length; i++)
        if(xs[i-1].compare(xs[i]) > 0)
            return false;

    return true;
}

However, Javascript prototype suffers performance issue (I tested it myself), so I am looking for other ways to translate generics without using prototypes. That is why I'm looking for example on how to translate that into pure C.

Note: You might also translate it to any language you like, as long as you did not use generics.


texts: How to implement random sampling with continuous variables?

texts: How functions like rnorm in R (and similar functions) create a random sample ? If I want to implement one algorithm to simulate this procedure what can I do? When you have the pdf or pmf of a distribution how can you use this to create a random sample with a computer? Is there some book on this topic?Is this a numerical analysis topic? I searched alot but I couldn't find any information about this.


texts: Generating all factorials up to $n$: faster than naive approach?

texts: I'm aware of prime decomposition and parallel approaches to calculating one factorial; however, if I want the factorials of all numbers up to $n$, is there anything more efficient than the naive approach? As far as I can tell, at least the prime decomposition algorithms aren't any more useful here than the naive approach. Karatsuba multiplication may be useful, but that's something that would have to be dealt with in the data structure that handles arbitrarily large integers, if I'm not mistaken.


texts:
On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known radii and positions with respect to the origin. (It is possible that some smaller sub-circles are partially or entirely inside some larger sub-circles.)

The entire plane is gridded uniformly into pixels with sides being horizontal and vertical (along coordinate axes). The size of the pixels is fixed and known a priori but otherwise much smaller than the size of parent circle; there are on the order of few $\times 10^{5}$ pixels all over the parent circle.

$\sim 1\%$ of the area of the parent circle is colored in the form of a few clumps across the parent circle covering $\sim 10^{3}$ pixels.  These colored pixels are mostly inside sub-circles; all are entirely inside the parent circle. We are given the 2D Cartesian coordinates for (the centers of) all colored grids.

Each colored grid is associated with the smallest sub-circle that contains it.  If the pixel falls within multiple sub-circles, only the smallest of the circles should be chosen.

Finally, I would like to calculate the total number of colored grids associated with each sub-circle. Is there an efficient algorithm for this?


texts: Algorithm for drawing the horizon given the current coordinates, elevation and field of view

texts:
I have a large database containing coordinates along with an elevation number.
If I am a person looking in some direction (0-360) with an n degree field of view, and located at some coordinate and at some elevation, how can I generate an image representing the horizon? What algorithm should I use?


texts: Implementing reliable pairwise average in distributed systems

texts:
Consider an asynchronous and unreliable distributed system. Each node has a value. Suppose that p and q are two neighbor nodes of the system (p_val and q_val are the values of p and q respectively). p and q want to compute the average of their values and change their values to the average. If one node changes its value to the average, the other node should change as well. This problem is called distributed reliable pairwise average.

  Question: Is it possible to implement distributed reliable pairwise average? or it is impossible?

I think that it is impossible. Please consider the following simple protocol:

Each node sends its value to the other node.
Each node after receiving the value of the other node changes its value to the average.

Suppose that p receives q_val but q doesn't receive p_val due to occurring a link-failure, so if p changes its value to the average, it is not correct. It seems that they need to send acknowledgments. If they start to send acknowledgments, they enter an endless loop.


texts:
I am looking for the terminology/concepts which express the nontechnical notion of the "layer" structuring of programs, the languages in which they are written, and a formal type theory.

For instance, we might have types defined for a single module, written in a language with a certain type system which may be a subset of a very abstract theory like system F, F-Omega, or CoC.

Is there a word or notion to express this "scale" of typing?


texts: Is it possible to create a human thinking and acting program on a computer?

texts:
Does Artifical Intelligence need something else, something that is not so limited as a computer to achieve the goal of building a humanly thinking and acting program?

If so, what might this be? I don't know much about quantum computers, but might they be a solution?


texts: Why do AlphaGo and AlphaGo Zero include board history in the input features

texts:
Both AlphaGo and AlphaGo Zero include prior board states as input features (the "Turns Since" planes for AlphaGo, and the repeated 8-step history planes for AlphaGo Zero).

What is the purpose of including this history information in the input to the neural networks?

If we ignore the ko rule, the best move at a position should not depend on the history of moves leading up to that position. If we don't ignore ko, a single step of board history should be sufficient in the vast majority of games, so including 8 steps of history seems excessive (and possibly even harmful, since if the same position were reached by two different paths, the learned response might not be shared between those two paths).

This doesn't seem to be discussed in either of the papers, or in any of the media reporting that I have seen.


texts: What is the min # of moves to sort an array from 1 to n?

texts:
Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to
any place you want (insert to any place, not swap). Prove the minimum number of "moves" to sort the array is n - k, where k = the length of the longest increasing subsequence.

Ex: array is [1, 2, 5, 3, 4, 7, 6]

Longest increasing subsequence is [1, 2, 3, 4, 6], which is of length 5. Hence, the answer is 7 - 5 = 2 moves. You move numbers 5 and 7 to the correct spots.

I'd like a proof / intuition on why this has to be the minimum # of moves.


texts: IDAstar on pancake sorting problem, how many node expansions

texts:
I am attempting to implement IDAstar and so just need to double check my reasoning.
Suppose I am trying to solve the following pancake sorting problem using IDA-star assuming all operations have a cost of 1 and assuming that I am using the zero-heuristic:

start state= 1 0 2 3 4 5
goal state= 0 1 2 3 4 5

I believe that it would take 2 node expansions to solve this problem instance using IDAstar as follows:

First sweep with a threshold of zero would expand the start state.
Second sweep with a threshold of 1 would expand the start state again and this is when we discover the goal state.

is this correct?


texts: Is there any guarantee in asynchronous systems?

texts:
We know that in an asynchronous system, no assumptions about process execution speeds or message delivery times are made. My question is: can we present any guarantee in asynchronous systems?
Some examples of the guarantees that I'm looking for are:

Consider two processes $p$ and $q$. $p$ sends a message an infinite number of times to $q$. $q$ delivers the message finally if two processes are correct (a process that never crashes is said to be correct).
If 1. is correct, then: no edge-cut in the network persists forever between the correct processes.


texts: Is there any grammar parseable by LALR(1) but not LR(1)?

texts:
https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, LALR(1) is a strict subset of LR(1): each grammar parseable by LALR(1) is parseable by LR(1), but not the other way around.

I'm surprised because it seems I've managed to create a grammar for which this tool: https://mdaines.github.io/grammophone/ says it is not LR(1) but is LALR(1) .

Therefore: Am I mistaken in my belief that LALR(1) is a strict subset of LR(1)? Or is Grammophone buggy and unreliable?


texts: What is the main concept of using lexical,linguistic, semantic or syntactic approach in NLP for cyberbullying

texts:
Am really in need of some explanation, am working on a nlp cyberbullying detection tool which i will deploy to the web using django framework, however, am stuck on some idea, can someone explain to me....What is the main concept of using lexical,linguistic, semantic or syntactic approach in (NLP) and how is applied in cyberbullying or what are the step, i know POS-tag is way of grouping word and look for dependency in other word, my idea of pos-tag is a synonym of semantic because pos-tagging is a process linking words to it root and representation word in a understandable context correct me if wrong.

I read an article where a paper tackled a project using predictive analysis approach with feature extraction techniques, navie baye for classification and to train the model, in the discussion they also spoke on how other team used Semantics approach to classifier cyber bullying . I know of data cleaning, tokenisation stemming and most of feature extraction model, however, am stuck on the problem of approach which is what is the relevant on lexical, semantic or syntactic and how are they been approached.


texts: proof of correctness for greedy knapsack algorithm

texts:
I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement 1 if statement 1 ≥ statement 2 but I don't really know how. Any help on this matter will be really appreciated. Thanks!

Statement 1 and Statement 2 refers to the red highlighted boxes, from the attached picture, tagged as 1 and 2 respectively.

Original source: http://oucsace.cs.ohiou.edu/~razvan/courses/cs4040/lecture15.pdf


texts:
I'm struggling to understand one part from the book "Cracking the coding interview".
The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full and we have to reallocate.

Inserting $X$ elements take $O(2X)$ (because $\frac{X}{1} + \frac{X}{2} + \frac{x}{4} + \ldots + 1  \approx  2 X$)

I perfectly understand until this point but I don't understand second sentence:

  "Therefore, $X$ insertions take $O(2X)$ time. The amortized time for each insertion is $O(1)$."

How did she came to this conclusion?


texts: Notation for asymptotic bounds on both sides

texts:
I am writing my first paper, and one of the results can be written as follows:

  For any $W,\epsilon$ such that $\epsilon = o\left(\frac{\log^4 W}{W\log\log W}\right)$ and $\epsilon=\omega\left(\frac{\log\log W}{W}\right)$, we obtain a $o(\min \{W, \frac{1}{\epsilon}{\log^2 W}\})$ space algorithm, improving the state of the art.

Is there some standard notation, say $\Gamma$, so I could write:

  For any $W$ and $\epsilon=\Gamma\left(\frac{\log\log W}{W}, \frac{\log^4 W}{W\log\log W}\right)$, ...

?

Will appreciate any help !


texts: How could an SMT solver be implemented as simple as possible?

texts:
I'm trying to figure out how an SMT solver works as simple as possible.
Let's assume we have a simple input program with symbolic values x and y.
E.g.

if (x+y < 20) {
   if (x > 10) {
      if (y > 10) {
        assume(false);
      }
   }
}

Here we have different paths, depending on the conditions. To reach assume(false) each condition has to be true, so our outcoming formula is:

$x+y < 20 \,\,\,\,\,\wedge \,\,\,\,\, x > 10 \,\,\,\,\, \wedge \,\,\,\,\, y > 10$

So far, so good. What happens next, step by step?

I would like to implement, as simple as possible, a solver which gets as input something like the formula above and delivers specific output to reach the end of the path - here assume(false), i.e. x = 2147483647, y = 2147483647 (jfi: x+y would be -2) - for overflow detection or similar.

I know there are a lot of SMT solvers on the internet, but I couldn't find a really simple self-explaining one. Looking forward to a suggestion.


texts:
Here I have the method for pumping lemma to prove that a language $L$ is not regular:

Suppose to the contrary that L is regula, then $\exists$ DFA $A$, s.t. $L(A) = L$.
Let $n$ be the number of states in $A$.
So, $\forall w ∈ L(A)$, if $|w| \ge n$, then $w = xyz$,
where $x$, $y$, and $z$ as in Pumping Lemma.
Choose a suitable $w \in L$, where $|w| \ge n$.
Find an $i$, such that $xy^iz \not\in L$.
Since $xy^iz \in L(A)$, $L(A) \neq L$.
4 contradicts 1, so 1 cannot be true and therefore
$L$ cannot be regular

First of all, what are we trying to prove here in other words? That the language $L$ cannot be represented by a FSM, therefore cannot be considered "regular" because a regular language is only regular if it can be represented by a FSM?

Second, how am I supposed to find "$n$" which is the number of states in $A$? Is this also known as the pumping length?

What is the proper way in which we are supposed to break up the string chosen string $w \ge n$ into 3 parts ($xyz$)?

For example this teacher broke it up in this way:

$$\begin{align*}
w &= a^{n}ba^{n+2}\\
i &= 2 \\
xy^2z &= a^{n+∣y∣}ba^{n+2}
\end{align*}$$

How is the above equation equivalent? Why is he choosing $|y|$ and adding to to $n$?

And why would any of this prove that $L$ is not regular? I'm really confused about the whole thing.


texts:
Let G b the following CFG (Where S is the start symbol):

S→aB|aDc
B→bBc|c
D→bc|c

(a) Show that G is ambiguous.
(b) Show that G is not an LR(1) grammar.
(c) Modify G into an equivalent grammar G′ that is LR(1). Explain why G′ is an LR(1) grammar and why G and G′ are equivalent.

My current answers:

(a) I showed that there exists two left derivation trees for string abcc - therefore it is ambiguous.

(b) I simply stated that an LR(1) grammar is not ambiguous by definition, and since (a) shows it is ambigious it follows that G is not an LR(1) grammar.

(c)
G':

S→aB
B→bBc|c

I removed the nonterminal D, which makes it unambiguous.

Questions:

Is there a more suiting answer for (b)?

How do I explain why G' is an LR(1) grammar in (c)?

Thank you!


texts: Does the master theorem apply to T(n) = 3T(n/3) + nlogn?

texts:
I am given an example of a case where the master theorem does not apply, but it seems like it should apply.

This was the reasoning:

$T(n) = 3T(n/3) + n \log n$ with $
 a = 3, b=3, f(n) = n\log n$ and  $n\log_b a = n\log_3 3 = n$

$f(n)$ is asymptotically larger than $n\log_b (a)$
, but not
polynomially larger. The ratio $n \log n / n = \log n$ is
asymptotically less than $n^\epsilon$
for any positive $\epsilon$. Thus,
the Master Theorem doesn’t apply here

However, it seems like case 2 of the master theorem should apply here.
We have $f(n) = n\log n$, and thus $f(n) = \theta(n^{\log_3 3} \log n$)

Then: $T(n) = \theta(n^{\log_a b} \log^{k+1}n) = \theta(n\log^2 n)$

Which is correct?


texts:
I have a question asking for the minimum and maximum height $h$ of a B-Tree with 1000 elements under following conditions:

each block can save 1 to 4 records,
the number of internal nodes is between 3 and 5 and
the root has between 3 and 5 children.

The solution is given as $4\leq h \leq7$. How this is reached?


texts: Is the minimum bottleneck spanning tree also a minimum spanning tree for an undirected graph with unique edge weights?

texts:
I can see a counterexample such as this:

But I can also see in some cases it could be the same. I am trying to understand what property makes a MBST also a MST?


texts: connected components - determining "groups" in Go

texts:
I would like to write an analysis of go positions.  Part of it requires me to determine the "groups" on the board and count their "liberties".

Any Go "position" is a collection of black x white o and empty . on the board.  So I using an 2D array.

o.x.xxx..x
xoo.xoxxoo
....x...ox
.ox.o.o.o.
xox..xx...
.xox.x.xx.
o..oxxoooo
..o..xxo.o
.o...oxoo.
.xo..oxxox

I need to identify the components of the same type (o, x or .)  connected by horizontal or vertical moves.  Diagonal does not count.

...o...    vs    .x.x
oo...oo          x.x.

Once I have identified a group, I need to count the liberties or empty spaces around that group.

Here is a group of x pieces with 9 spaces around it

 234       ..ox
1xxx5     .xxxo
 89x6      o.xo
   7         .

However, 4 of them are covered with o pieces, and 5 of them have empty spaces . around it.  So our gropu of x pieces only has 5 liberties.

. should count as 1 liberty, the o pieces should not count (contribute 0) and the x pieces should have been included in the group to begin with.

Is there a systematic way to identify connected groups on the board?  And then to count the liberties.


texts: How to Specify the Behavior of Automata for Verification

texts:
I am wondering what it takes to "verify" or "prove" that an automaton is correct. What the components are that are required. It seems that an automaton would be an easier thing to formally verify as sound than say an arbitrary function. Not sure though what needs to be verified in an automaton, which is what brings up the question.

Thank you!


texts: A simple algorithm to solve the MST Sensitivity Analysis problem in linear time when the MST is a path

texts:
The problem. Given an undirected, connected, edge-weighted graph $G=(V, E_G; w)$ and a minimum spanning tree (MST) $T=(V, E_T)$  of $G$, the MST sensitivity analysis problem asks to find, for each edge $f \in E_T$, the increase between the total weight $\sum_{e \in E_T} w(e)$ of $T$ and the total weight of a MST of $G-f$.
Let $n=|V|$ and $m=|E_G|$. It is known that the above general problem can be solved in time $O(m \log \alpha(m, n))$, where $\alpha$ is the inverse Ackermann function. I am interested in a restricted version of the above problem in which $T$ is guaranteed to be a path.
The paper linked above shows a reduction between the general MST sensitivity analysis problem and the problem of computing a MST. One of the steps of the reduction involves solving the MST sensitivity analysis problem on an instance of the restricted problem. The author claims that this can be done in linear time and "this is an easy exercise".
Does anybody know or has a reference to a simple linear-time algorithm to perform the sensitivity analysis of a graph when its MST is a path?
An involved solution on the RAM model.
If we number the vertices of $G$ with the integers from $1$ to $n$, as they appear when traversing $T$ from one endpoint of the path to the other, then we only need to find, for each edge $(u,v) \in E_T$, an edge $(x,y) \in E_G \setminus E_T$ with $x \le u$ and $y \ge v$ such that $w(x,y)$ is minimized.
This can be equivalently reformulated as follows:
we are given $m$ horizontal segments whose endpoints have integer $x$-coordinates in $\{1, \dots, n\}$. We need to report, for each $x \in \{1, \dots, n\}$, the height of the highest (or lowest) segment intersecting the vertical line passing through $x$.
This is essentially the problem of computing the upper/lower envelope of a set of horizontal segments, which can be solved in linear time on the RAM model provided that a list of the segments' endpoints in left-to-right order is known (this is the case our instances since the sorted endpoints of the segments are the endpoints of the non-tree edges as they appear in a traversal of the path).
Such an algorithm requires bit manipulations and I wouldn't consider coming up with it an easy exercise, so I doubt that this is what the author had in mind.


texts:
below is two pictures in regards to Executable and Linkable Format(ELF):

My questions is:
we know that Relocatable Object Files in ELF format are binary code(0s and 1s), so is Elf64_Symbol struct just used to represent its content more naturely and enhance readability without saying sth like in .symtab 0-31 bits(int is 32 bit) is string table offset, the following 32-39 bit(size of char) is .... etc, so Elf64_Symbol struct is mainly used for readability?and we don't actually need it in coding. is my understanding correct?


texts: Regular expression for the language containing neither aa nor bb

texts:
I want to create a regular expression for the language

$L=\{ w \in \{a,b\} |$ w has neither aa nor bb as a subword$\}$.

I've tried various things, but I can't seem to get the correct regular expression.


texts: Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?

texts:
I'm currently reading the book Introduction to the Theory of Computation (2nd or 3rd Ed.) by Michael Sipser, and have stumbled upon a question in Chapter 1 - Regular Languages, namely when the author is presenting the proof idea of Theorem 1.49 - "The class of regular languages is closed under the star operation." using NFA.

The approach suggested is that, if we have a regular language $A_1$ and want to prove that $A_1^*$ also is regular, we can take an NFA $N_1$ and modify it into an $N$ as in the image below, which is then a particular NFA recognizing $A_1^*$.

He noted:

  One (slightly bad) idea is simply to add the start state to the set of accept states. This approach certainly adds $ε$ to the recognized language, but it may also add other, undesired strings.

I have drawn the "bad" NFA as below and tried to figure out why this will result in undesired strings. However, I can't find an example of when the an undesired string is recognized. Why will this idea result in the NFA recognizing undesired strings?

Could someone point this out for me or give me a hint, or have I misunderstood the author? Thanks in advance!


texts: if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC?

texts:
if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC ?

If yes then how can we generate a polynomial time verifier algorithm for the same ?


texts: How to get the optimized quicksort algorithm's time complexity

texts:
I learned in my data structures class that QuickSort can be optimized by calling the InsertionSort method when the length of the subarray is less than a certain threshold. However, when it comes to the actual time complexity calculation of the optimized version of QuickSort, I'm having trouble finding the result. The problem is as follows.

An optimized-QuickSort function calls the InsertionSort method instead of itself when the size of the sublist is less than k. Assuming that the time complexity of QuickSort and InsertionSort is $c_1n\log n$, $c_2n^2$ respectively, what is the time complexity of optimized-QuickSort? (Calculate for the average case)

I assumed that the sublist is split into 1:1 by each step. As a result, I got $c_1nlog$($n\over k$) + $c_2nk$, but I am definitely not sure of my answer since I don't know if my assumption is correct. In the textbook, the average case of a non-optimized QuickSort was supposed to be calculated by assuming the partition could be the first element, second element, third element, ... , last element and then dividing the whole sum by n.

I would appreciate some help! Thanks.


texts: Clarifiaction on the NP-hardness of k-SUM-variants

texts:
I am currently looking into the $k$-Sum Problem and some of its variants. However i stumbled onto an inconsistency, that i can not seem to fix.

If we begin with $3$-Sum, the 'textbook'-definition goes something along the way of

  Let a set $S$ of $n$ integers be given. Are there $a,b,c\in S$ such that $a+b+c=0$.

From this definition however it is not immediatly clear, whether $a,b$ and $c$ have to be distinct. Compare this to this paper. In the Introduction they state

  The $k$-SUM problem is the parameterized version of the well known NP-complete problem SUBSET-SUM,and it asks if in a set of $n$ integers, there is a subset of size $k$ whose integers sum to $0$.

This seems to imply, that duplicates are not allowed, as sets usually dont permit duplicates. However in Section 2.2 of the same paper they reduce $k$-SUM to $k$-Table-SUM and link to Section 3.1 of this paper, where the reduction only works in the case, where duplicates are allowed.

Are these two variants equivalent? If so, are there possibly any sources on this? And furthermore, is $k$-Table-SUM NP-hard? Intuition and "closeness" to the $k$-SUM would suggest this, but i haven't found a proof for this apart from the linked sources with the noted inconsistencies.

Thanks!

Edit:

I finally found two sources that can answer this properly. The first contains a reduction from 'Perfect Code' to $k$-SUM without duplicates, however the k-SUM instance is constructed in a way, that allowing duplicates wouldn't find any other solution here (specifically at 22.5.3). In case anyone is not familiar with perfect code, at 22.2.1 the authors reduce Indepenent Set to Perfect Code.

The second source actually links to the first. They reduce $3$-SAT to $k$-SUM in Theorem 5.1. Note that the proof specifically states, that they seperate the instance into d blocks, and then make sure that $k$-SUM only finds one entry per block. This is exactly the same as $k$-Table-SUM and also easily reduced to $k$-SUM with duplicates, similar to the accepted answer.


texts:
Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness.

Besides connectedness, $G$ is guaranteed to have enough connectivity so that removal of a reasonably small amount of vertices do not disconnect the graph and there are several paths between two specified vertices (removing one or two vertices do not let $G$ be a tree).

I have looked it up on the Internet and could not find any research. Maybe it is because I do not know the proper keywords.

Is there any research on this topic? If so, could you provide a reference?


texts: Is this restricted promise-3SAT version coNPComplete?

texts:
Given a $3SAT$ problem the decision version of the problem (if it has a solution or not) is $NPComplete$. Now, given that we consider the promise version of the $3SAT$ problem, the promise is every $3SAT$ problem provided always has at least 1 solution.

Query: Does every solution of the above $3SAT$ problem instance have a particular property (one that can be tested in polynomial time. For eg: 'for any solution $A_i$, $N$ numbers immediately smaller than A are co-prime' or something similar; where $N$ is the input length)?

The problem and property can be encoded as a pair consisting of $3SAT$, and another $N$ input circuit of polynomial size ($N^c$ for some constant $c$)

This promise version is definitely in $co-NP$ (as if there is a solution that does not satisfy the given property, that solution is the $co-NP$ certifcate of polynomial length).

Is this problem also $co-NPComplete$ (as it still involves getting the failing solution first)?


texts: Prove that $\texttt{prefix}(L)$ is regular

texts:
Given that $L = \lbrace 0^n1^n : n \geq 0\rbrace$ is a non-regular context-free language, prove that $\texttt{prefix}(L)$ is regular.

So far I have provided that the grammar to produce this language is:
$S \rightarrow 0S1 \thinspace | \thinspace \epsilon$

Would you go about proving $\texttt{prefix}(L)$ is regular just like you would any language, proving that $\Sigma^\star$ = $\texttt{prefix}(L)$, or by induction on the length of the words in $\texttt{prefix}(L)$.


texts: In topological data analysis, do bar codes that begin and end at the same index mean anything?

texts:
The typical workflow in topological data analysis is from point cloud data to filtration to a list of bar codes corresponding to each dimension.

A filtration is a sequence of simplicial complexes, each one a subset of the next; where a simplicial complex is a gluing of many simplices such that the intersection of any two simplices (if it exists) is a simplex. Each simplicial complex can be obtained from the point cloud data by, for example, taking a sequence of distances and connecting points which fall within that distance to form a graph, then identifying complete subgraphs as simplices to make a simplicial complex. This is called the Vietoris-Rips complex. Another common way to construct a filtration is the Cech complex, which makes a simplex out of a set of points iff balls of a certain radius intersect.

The filtration is the input to the algorithm which computes persistent homology. Simplicial homology is the simplest of homology theories and it allows one to identify connected components, tunnels, hollow volumes, and higher dimensional cavities in a simplicial complex. Persistent homology does the same for filtrations, except it also measures how long each cluster/hole lasts in the sequence of complexes. The computation is a bit tricky, to learn about it I would refer you to the paper that showed that the computation is actually practical. The output of persistent homology is a bar code diagram for each dimension. A bar code has a beginning, which is the index in the filtration where the cluster/hole begins, and it might have an end where the cluster/hole dies.

So it seems natural to disregard bar codes that have the same beginning and end; they don't persist at all. Even if a feature is present only in the ith complex in the filtration, it will have the bar code (i, i+1) because it dies in the (i+1)th complex.

However, I want to be completely sure because I'm maintaining a TDA package. I just finished a patch and was considering adding an extra feature where these apparently meaningless bar codes are automatically filtered out.


texts:
Given a $n \times m$ grid, define a valid coloring as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent if they share a side. How many valid colorings are there? Let $f(n, m, k)$ be the answer.

I search for a way to compute $f(n, m, k)$ fast, primarily in terms of time complexity. However, a polynomial-time solution is not required.

This problem was proposed in Codesprint 5 at HackerRank with constraints $1 \le n,m \le 8$ and $k \le 10^9$. However, I am not asking for this particular case, so it does not matter so much. It is worth mentioning there is a discussion on TopCoder, but I do not get it after several readings.

Approaches. I present my thoughts as following. First, we may explicitly enumerate all colorings. This works only on very small instances, because the number of colorings is growing exponentially. In order to see this, consider an $1 \times m$ grid and $k = 3$ colors. The first cell may be colored in $3$ ways and each following cell in $2$ ways, which yields $f(1, m, 3) = 3 \cdot 2^{m - 1}$.

Let's consider $n = 2$. If $m = 1$, we simply get $f(2, 1, 3) = 6$. Assume, we know $f(2, m, 3)$ for some $m \in \mathbb{N}$. Let $X$ and $Y$ be the colors in the rightmost / last column for an abritrary valid coloring of $2 \times m$ grid. In $(m + 1)^{th}$ column, there are $2$ colors for the top cell $(Y$ and the third color, say $Z$). Distinguish between two cases.

Case #1: Top cell has color $Y$. Then, our bottom cell can get color $X$ or color $Z$. There are two possible choices.

Case #2: Top cell has color $Z$. Then, our bottom cell must have color $X$.

Altogether, there are $3$ possibilities for the next step, i.e. $f(2, m + 1, 3) = 3 \cdot f(2, m, 3)$. Using our base case and solving the recurrence, the result comes out to be $f(2, m, 3) = 2 \cdot 3^m$.

These counting arguments get more complicated for larger values of $n$, even for $n = 3$ I do not find an explicit formula. In the original problem, there are significantly more colors than cells. It should be sufficient to consider colorings with exactly $1, 2, \dots, mn$ colors (let $a_{i}$ be the respective answers) and compute $\displaystyle \sum_{i = 1}^{mn} \binom{k}{i} a_{i}$. Therefore, don't worry too much about this step.

Hints and approaches are appreciated as well as solutions and references.


texts: Find max flow in a network with all capcities of $\sqrt 2$ and one with 2

texts:
Given a graph $G(V, E)$ with capacities on the edges such that all edges have a capacity of $\sqrt2$ apart from one edge with a capacity of 2. need to find max flow efficiently.

I can run Dinic on this graph or FordFulkerson but I know it can be more time-efficient.

What I have tried -

transform all edges capacity to be 1, then find max flow using Dinic algorithm on 0-1 network that is more efficient than a general network.
then If the edge that had a capacity of 2 isn't saturated it won't be saturated on the original graph so we can just find the min-cut and multiply the number of edges that cross the min-cut by $\sqrt 2$ and that's the max flow.
but if it's saturated I'm stuck.


texts: Lexing and parsing a language with juxtaposition as an operator

texts:
Normal human math notation treats juxtaposition as implied multiplication, e.g., $2x$ means $2$ multiplied by $x$. This does not seem to be a common feature of computer languages, although it was, for example, supposed to be included in the language Fortress (now a dead project).

Lexing and parsing such a language seems to me like it would be difficult within the usual lexer-parser framework. In a computer language, unlike human math notation, we want to have variable names that are more than one letter. So if we need to lex the string xyz, we have a problem, because this could, e.g., mean x*yz if x and yz are variables, but it could also mean xy*z if xy and z are variables. The lexer normally wouldn't have this type of information available, so it would have no way of resolving the ambiguity.

Are there ways of reducing this problem to a more standard form that can be handled by a traditional lexer-parser pair, or does it require qualitatively different techniques?


texts: Intersection of Decision Tree Boundaries in Higher Dimensions

texts:
I have trained two binary decision tree classifiers with splits in $\mathbb{R}^4$. Same data, but from two different patches.  Now, I want to find the exact intervals where the two trees disagree.
The splits are along the lines of:
\begin{align*}
& (x_1 > 0.35592521727085114) \wedge  (x_3 \leq-0.13628841191530228) \implies 0, \\
& \vdots \\
& (x_3 \leq -0.013720870949327946) \wedge (x_1 > 0.35592521727085114) \wedge (x_3 > -0.13628841191530228) \implies1. \\
\end{align*}
($x_2$ and $x_4$ are allowed to live anywhere between their absolute bounds.)
Any advice on how to approach this?  I've read some material on interval trees, and theoretically at least I can see how they might be expanded to higher dimensions, but I'm wondering if someone out there has experience with a particular tree variant, or other data-structure that would be appropriate in this case.
Help very much appreciated.


texts:
I just wanted to know if there are actually jobs only devoted to creating and optimising algorithms after finishing a Bachelors degree. Or is it only restricted to PhD's?

I solve problems on SPOJ and CodeForces, but I'm not sure if I'd get a job doing something like that.


texts: If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction?

texts:
I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we call it a contradiction and declare the language is not context free or do we say there is no contradiction?
If its the former, it will declare (a)^n(b)^n as non-context free using Pumping Lemma even though we know its a context free language, since some of the cases will not obey the 3 conditions at the same time.
Edit:
By cases, I mean v and y's existence in different parts of the string. In a string aaaaabbbbb, either v or y could fully be in a, partially be in a and b or fully be in b.  ( Assuming you break the string into S = uvxyz where v and y are the repeating pieces)


texts: A program that cannot be written in (simply-)typed lambda calculus but only in lambda calculus or Turing-complete language

texts:
Programmers do sometimes write a program that creates infinite loop if some particular input is passed into the program.

But Simply-typed lambda calculus has to stop - so the question is, can anyone show some "useful" program in Turing-complete language (e.g. untyped lambda calculus) that does not go into infinite loop but cannot be written in (simply-)typed lambda calculus?

from comment section:

"Yes I know all of these and I know that they are more expressive and those - but halting problem would only have meaning if there is an algorithm (program) that typed ones cannot express - otherwise, we can write all programs into typed one and see whether it is well-formed, right? Then we automatically know whether a program halts or not. This is what I am asking."


texts:
For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem is an integer linear programming (ILP) problem, and its relaxed version becomes a linear programming (LP) problem, which we can efficiently solve.
Questions: Are there common techniques which show that, for a particular problem:

An LP solution will always be an ILP solution?
There exists an LP solution that is also an ILP solution?
A particular LP algorithm (e.g. simplex method) finds an ILP solution.

By "solution", I, of course, mean a vector on which the objective reaches its optimum.


texts: O(m+n) Algorithm for Linear Interpolation

texts:
Problem

Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the linearly interpolated values of the query points according to the data. We assume $q_i \in (\min_j x_j, \max_j x_j)$

I heard off-hand that this problem could be solved in $O(m+n)$ time but can only think of an $O(m \log n)$ algorithm. I can't seem to find this particular problem in any of the algorithm textbooks.

Linearithmic Algorithm

interpolated = []
for q in qs:
    find x[i] such that x[i] <= q <= x[i+1] with binary search
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)

This gives us a runtime of $O(m \log n)$, it's unclear to me how to get this down to $O(m + n)$ as the search for $x_i$ must be done for every query point.


texts: Are Big-Theta functions asymptotic monotonically non decreasing?

texts: For example, suppose $f(n) = \Theta(n^2)$, then does that mean for any sufficiently large $n$, $f(n) \le f(n+1)$? Is it a general case for all Big-Theta?


texts:
Following an exercise from Hopcroft-Ullman's Introduction to automata theory:

Let's define $k-MDFA$ as two way deterministic finite automaton with $k$ markers, similarly to two way $DFA$ but with ability to place (or pick up) a marker on the input cell currently under the head, but with limitation to placing at most $k$ markers at any time during computation, and with single cell only being able to hold at most 1 marker at any given time.

Formally, it's a tuple $A=(Q, \Sigma, \delta, s, F)$ where

$Q$ is finite set of states
$\Sigma$ is the input alphabet
$\delta : Q \times (\Sigma \hspace{2pt}\cup \hspace{2pt} \{\vdash, \dashv\})\times \{0,1\} \rightarrow Q \times \{\textbf{L,R}\}\times \{0,1\}$ is the transition function
$s$ is the initial state and $F$ is the set of accepting states

Input tape of the automaton for word $w \in \Sigma^*$ is $\vdash w \dashv$.

Moreover the transition function satisfies $\delta(q,\vdash,m) = (q', R, m')$,  $\hspace{2pt}\delta(q, \dashv, m) = (q', L, m')$ for all $q \in Q, \hspace{2pt} m \in \{0,1\}$ and for some $q' \in Q $ and $m' \in \{0,1\}$ (we do not allow automaton to leave the input).

If automaton attempts to place more than $k$ markers on the tape, the computation stops with rejection.

I have proved that $1-MDFA$ recognize exactly regular sets, but I can also show that with $2-MDFA$ I can recognize language $\{ ww : w \in \Sigma^*\}$, which is not a context free language. The second fact is fairly simple - here's an outline of how such automaton would work:

Check parity of input's lenght
Locate the middle of input by placing markers at both ends of the word, and then moving them one step closer towards the middle alternatingly.
Place marker on the first cell of input and on first cell of second half of the input
Compare letters under markers, if they differ enter reject state, if they are same, move both markers 1 step to the left and repeat. If you are about to move right marker onto symbol $\dashv$ enter accept state.

As such, clearly languages recognized by $k-MDFA$ are not contained in $CFL$ for $k \geq 2$.

My questions are:

Does increasing the amount of markers increase the computation power of $k-MDFA$ for $k \geq 2$?
Does allowing nondeterminism increase computation power of $k-MDFA$?
Can $k-MDFA$ recognize all context-free languages? If so, what's the minimal $k$ capable of expressing $CFL$?

Any references are welcome, if the question shows ignorance in the subject, I apologise.


texts: What is the complexity of the emptiness problem for 2-way DFAs?

texts:
I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape.

According to Wikipedia, they are equivalent to DFAs, though the equivalent DFA might be exponentially larger. I've found state complexity for their complements and intersections, but not for their emptiness-testing.

Does anyone know of a paper where I could find this?


texts: Magic Square Check for NxN Matrix - with Minimum Complexity?

texts:
Is there any algorithm that works better than $\Theta(n^2)$ to verify whether a square matrix is a magic one? (E.g. such as sum of all the rows, cols and diagonally are equal to each other).
I did see someone mention a $O(n)$ time on a website a few days ago but could not figure out how.


texts:
Can quantum computer become perfect chess player?

Can it determine whether (when both players are perfect) win white or black? (or is it dead heat?)


texts: What algorithm solves high-order unification for untyped terms in most cases?

texts:
High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a => b, where a and b are terms on the simply typed lambda calculus, a containing free variables, finds a substitution S such that aS => b, where => stands for "has the same beta normal form" (up to variable renaming). For example, given the following problem:

a = (λt . t
    (F (λ f x . (f (f (f x)))))
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

One can come with the solution:

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

Since that substitution makes a = b hold. My question is: what's an efficient (i.e., polytime) algorithm that solves this problem for as many cases as possible?


texts: Why worst case running time of Insertion sort is $\Theta(n^2)$

texts:
From Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
Theorem 3.1
For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

The worst case run time complexity of insertion sort is $O(n^2)$. However in case of sorted array the running time of the algorithm is $\Omega(n)$.

Don't these two things contradict with Theorem 3.1 when we say that run time complexity of Insertion sort in worst case is $\Theta(n^2)$.
Not sure if I am trying two mix different concepts; please help me in either case.


texts: Sedgewick analysis of algorithm, difference between theory of algorithm and scientific approach

texts:
I'm trying to improve my skills in analysis of algorithms. I think Sedgewick's "introduction to the analysis of algorithm" is a good, I'm reading carefully the first chapter, at least I'm trying. And the following is mentioned:

  The first, popularized by Aho, Hopcroft, and Ullman and Cormen,
  Leiserson, Rivest, and Stein, concentrates on determining the growth
  of the worst-case performance of the algorithm (an “upper bound”). A
  prime goal in such analyses is to determine which algorithms are
  optimal in the sense that a matching “lower bound” can be proved on
  the worst-case performance of any algorithm for the same problem. We
  use the term theory of algorithms to refer to this type of analysis.

Which explains the approach adopted in CLRS

It is also mentioned

  The second approach to the analysis of algorithms, popularized by
  Knuth, concentrates on precise characterizations of the bestcase,
  worst-case, and average-case performance of algorithms, using a
  methodology that can be refined to produce increasingly precise
  answers when desired. A prime goal in such analyses is to be able to
  accurately predict the performance characteristics of particular
  algorithms when run on particular computers, in order to be able to
  predict resource usage, set parameters, and compare algorithms. This
  approach is scientific: we build mathematical models to describe the
  performance of real-world algorithm implementations, then use these
  models to develop hypotheses that we validate through experimentation.

So this is the approach adopted by Knuth (I guess the analysis in "The art of computer programming" follow such approach).

I do get the general idea of course, but not the application, is there a specific application of these concepts you can point out? For example I do know the CLRS analysis of quicksort for example, how would this be any different from a scientific approach?


texts:
I am trying to solve a recurrence by using substitution method. The recurrence relation is:
$$T(n)=4T(n/2)+n^2$$
My guess is $T(n)$ is $\Theta(n\log n)$ (and I am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that $T(n)\le cn^2\log n$ but that did not work, I got $T(n)\le cn^2\log n+n^2$.

I then tried to show that, if $T(n)\le c_1 n^2\log n-c_2 n^2$, then it is also $\mathcal O(n^2\log n)$, but that also did not work and I got $T(n)\le c_1n^2\log(n/2)-c_2 n^2+n^2$.

What trick can I use to show that? Thanks.


texts: Sampling from a Acyclic Deterministic Finite Automaton

texts:
Assume you have a finite language $L$ succinctly represented as a acyclic DFA $M$ (models can't be much simpler than that :) ).

  How can we efficiently sample a word from $L$ with uniform distribution?

Note that counting the number of words in $L$ is easily doable in linear time in the size of $M$, which might be useful for the sampling process.

Clarifications:

$L(M)=L$.
$M$ is acyclic (has no loops).
Sampling means you output each word $w\in L$ w.p. $\frac{1}{|L|}$.


texts: How is Rice's theorem applicable to this decision problem?

texts:
I recently had a test in introduction to computability and I got the following question wrong.

The question

Input: A classical Turing machine $M$ with a 2-dimensional tape.

output: Does there exists a Turing machine $H$ that runs in polynomial time such that for any input $x$, if $M$ halts then $M(x)=H(x)$

Which of the following is correct?

(a) This decision problem is trivial.

(b) This decision problem is decidable, but not trivial.

(c) This problem is undecidable, according to Rice's theorem.

(d) This problem is undecidable, but Rice's theorem is not applicable.

My answer

I chose option (d) because the polynomial time requirement is not semantic, but the professor marked option (c) as the correct answer. Could anyone explain this?

Background

Rice's theorem and the terms "trivial" and "semantic" are explained here.


texts: Is it possible to build a computer that would output $10^{10^{100}}$ symbols and halt, without using ~$10^{100}$ space?

texts:
My recent question on Programming Puzzles and Code Golf got some fair attention and showed that not only it is very easy to output $10^{100}$ symbols and halt, but actually quite convenient in many programming languages as well.

While posting it I was wondering whether I should ask for $10^{10^{100}}$ instead but decided against that because while theoretically straightforward, I think it's simply physically impossible within this universe.

Here's my reasoning: to iterate over some command $b^m$ times, one needs $O(m)$ space to maintain the counter. Physical computers of today aside, $10^{100}$ just exceeds the estimated number of particles in the known universe by many orders of magnitude.

My question is not about alternative possibilities of physical realization of memory storage but about the principle. I'm not well-grounded in restricted Turing computation. Are there some tricks towards reducing the space complexity below $O(m)$ given that the value of the counter is never needed, just the fact that it counts the proper number of times and then halts?


texts: Find cheapest path from 1st city to the $n$th city

texts:
The title may be a bit misleading, but this is essentially a DP problem.
The problem is that we have $n$ cities labeled from $1, ... n$ and we are trying to find the cheapest way to travel from 1 to $n$. There is a cost for travelling from $i$ to $j$, $i < j$, cost being $c_{ij}$ but I'm only allowed $k$ hops at most.

The $k$ constraint has me stumped. Intuitively, we recurse from $i$ to $n$ for each value of $n$. How would I solve this using at most $k$ hops? And what would the complexity be?


texts: Given a function and its complexity, what is the complexity of its circuit?

texts:
For example,
given an element-wise function $f$, with input $x\in\{0,1\}^{p\times n}$, the complexity $T(f(x))=O(n)$, and that all numbers are represented using $p$ binary digits. Suppose that we also know the complexity of each individual operations inside $f$. For example, multiplication takes $O(m^{1.585})$ using Karatsuba algorithm, here $m$ is the number of digits of the product. Similarly, suppose that we know all the complexity of arithmetic operations like addition, subtraction, division, square root etc. In addition, suppose that we also know the complexity of all the basic boolean cells, e.g. Full Adder, Subtractor, Multiplier etc.

What is the complexity, in terms of number of boolean gates, of its equivalent boolean circuit? Can we derive a formula containing $n,p,m$?

If so, what is the complexity of a boolean circuits of a Cholesky decomposition, with input $X\in\{0,1\}^{p\times n\times n}$?


texts: Does this imply Hamiltonian path cannot be decided in nondeterministic logspace?

texts:
Suppose I nondeterministically walk around in a graph with n vertices.

When looking for a Hamiltonian path, at some point I’ve walked n/2 vertices.

There are (n choose n/2) different combinations of vertices I could have walked (meaning the unordered set, not the ordered walk).

Each of those states must be distinct from one another.

If not, then, depending on the remaining n/2 vertices, I would decide the wrong answer.

Therefore, midway through the path, at n/2, I need (n choose n/2) different states. That is too big for logspace.

Therefore you cannot decide a Hamiltonian path by nondeterministically walking around.

Does this imply Hamiltonian path cannot be decided in nondeterministic logspace - at least by "walking around"?


texts: The number of operations of Explicit and Implicit Euler for 1D hear equation

texts:
I'm studying with "Numerical Solution of Partial Differential Equations by K.W.Morton and D.F.Mayers". On page 25, it says "2(add) + 2(multiply) operations per mesh point for the explicit algorithm (2.19)", but it seems 3(add) + 2(multiply) to me, how did I get wrong?

(2.19)  $U_j^{n+1}=U_j^{n}+\mu(U_{j+1}^{n}-2U_j^{n}+U_{j-1}^{n})$

My counting is

2(add) and 1(multiply) inside the bracket

1(multiply) for $\mu$ and the brackets

1(add) for $U_j^{n}$ and the rest


texts: Transform Standard-Dual program to Canonical-Dual program

texts:
Say I have the following Standard-Dual linear program:
$$max<\vec b, \vec y>$$
$$s.t.:A^Ty \le \vec c$$
$$\vec y \ge \vec 0$$
Is there a way to transform it to a Canonical-Dual and equivalent linear program, i.e., that of the following form:
$$max<\vec b', \vec y'>$$
$$s.t.:A'^Ty' \le \vec c'$$
$$\vec y' \in \mathbb R^n$$


texts: How long does the Collatz recursion run?

texts:
I have the following Python code.

def collatz(n):
    if n <= 1:
        return True
    elif (n%2==0):
        return collatz(n/2)
    else:
        return collatz(3*n+1)

What is the running-time of this algorithm?

Try:

If $T(n)$ denotes the running time of the function collatz(n). Then I think I have
\begin{cases}
T(n)=1 \text{ for } n\le 1\\
T(n)=T(n/2) \text{ for } n\text{ even}\\
T(n)=T(3n+1) \text{ for } n\text{ odd}\\
\end{cases}

I think $T(n)$ will be $\lg n$ if $n$ is even but how to calculate the recurrence in general?


texts: How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step

texts:
Consider the following matrix:

Input:
The entire list of coordinates ranging from (0,0) to (4,4).

A list indicating certain coordinates which cannot be used to generate a path reached.

So,

each position on the grid is a node
nodes share an edge if exactly one coordinate differs by exactly 1
X nodes (and their associated edges) are deleted

The problem then becomes, find the shortest path in the graph between two nodes. If the nodes are not in the same connected component, there is no such path.

Output:
The shortest path between S and E, considering the positions of the X nodes, given by a sequence of coordinates.

So in the above picture, a possible route may be the following:
(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)->(4,3)->(4,4)

A total of eight steps.

If the Xs occur in a way that prevents any movement (i.e, Xs at (0,1),(1,1), and (1,0), it should return -1 or indicate in some other way no path is possible.)

I have received advice that the A* search algorithm (pseudocode in this link) is relevant to this problem, but I am having difficulty seeing how to apply it.


texts:
I was studying operating system concepts from Silberschatz, Galvin and Gagne's book (sixth edition) and I have some questions about the flow of execution of a program. A figure explains the processing of the user program:

We get an executable binary file when we reach the linkage editor point. As the book says,

  The program must be brought into memory and placed within a process for it to be executed.

I have several questions about this flow:

Before the program is loaded into the memory, the binary executable file generated by the linkage editor is stored in the hard disk. The address where the binary executable file is stored in the hard disk is the logical address as generated by the CPU ?
If the previous answer is yes, Why CPU has to generate the logical address ? I mean the executable file is stored somewhere in the hard disk which pertains to an address, why does CPU has to separately do the stuff ? CPU's main aim is processing after all!
Why does the executable file needs to be in the physical memory i.e ram and can not be executed in the hard disk? Is it due to speed issues ?


texts:
I am studying about algorithm correctness and have enctountered this problem.
function add(y,z)
comment Return y + z, where y,z are natural numbers
x :=0; c:=0; d:=1;
while(y>0)v(z>0)v(c>0) do
    a := y mod 2;
    b := z mod 2;
    if a XOR b XOR c then x := x+d;
    c:= (a AND b) v (b AND c) v (a AND c);
    d :=2d; y:= floor(y/2);
    z := floor(z/2);

The book that I'm reading says that loop invariant is $(y_j + z_j + c_j)d_j + x_j = y_0 + z_0$ and I honestly can't understand the conclusion. How do you come up with this? Why is this true?


texts: Give an implementation leveldescription of a TM

texts:
L = {x=y ⊕ z|x, y, z are binary integers, and x is the XOR of y and z}

is non-regular, i.e., no FA exists that could recognize the language. How can I give an implementation level description of a TM that decides on L?


texts: Algorithm for grouping identical neighbors in a list

texts:
I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries.

Example list:

1,1,1,1,1,2,2,2,3,3,1,1,1,2,2,2,2,2,2,2,2,2,4,4,4,4,1,1,1,1,1,1

After 'compression'

1,2,3,1,2,4,1

Is there an algorithm for doing this that is faster than O(n)? In other words, faster than just looking at the next neighbor?

while (1)
    n = 0, m = 1
    if (list[n] == list[m])
        remove list[m]
    else
        n = m
        m = m + 1
    if (m > list.size)
        break

If not, what about this problem makes it O(n)?


texts: We used to have analog computers several decades ago. Modern days computers are Digital. What about Quantum computers? Is it analog or digital? I am asking this since qubit can be many things at the same time.


texts: How can a Turing machine run another machine for an infinite amount of strings?

texts:
The proof in my textbook, that $E_{TM}$ can be decided by oracle machine $O^{A_{TM}}$, uses a Turing machine $P$ such that for an input $w$:

$P$ runs the Turing machine $M$ on all strings of $\Sigma^*$
If $M$ accepts the string, $P$ accepts

$O^{A_{TM}}$ then asks the oracle if $<P,w> \in A_{TM}$

I can't seem to understand why $P$ can run $M$ for all strings of $\Sigma^*$ because this is an infinite amount of strings. I do, however, understand that $P$ actually never has to run and is purely constructed to ask the oracle if it accepts.


texts: Determine if the language of words with same number of 1's and 2's is context-free or not

texts:
$$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
I have tried creating PDA to determine if this was context-free or not. It seems like it would be because whenever a 1 is pushed onto the stack, there always is a 2 to get pop it out. The 0's are what is bothering me at the moment. Do we need to include them, or we can exclude them entirely?
I would do this with pumping lemma, but we did not learn that for our class.


texts:
In the proof of Trakhtenbrot's theorem (as given in "Elements of Finite Model Theory" by Leonid Libkin), for every Turing machine $M$, author constructs a FO sentence $\Phi_M$ of vocabulary $\sigma$ such that $\Phi_M$ is finitely satisfiable iff $M$ halts on the empty input. Then he says that as the latter is known to be undecidable so the theorem holds.

My doubt is, the vocabulary $\sigma$ that was constructed depends on the Turing Machine $M$. But the theorem holds for any relational vocabulary with at least one binary relation symbol and also it should not depend on the machine $M$. Perhaps the claim of author is enough to imply the theorem for arbitrary vocabulary, but I am unable to see how.


texts: Heuristics to transform a recursively enumerable set into a diophantine set

texts: The class of recursively enumerable sets is equal to the class of Diophantine sets. Given a recursive function, is there a way to produce a diophantine equation such that the trace of calls to the recursive function matches the set of integer solutions of the equation? Heuristic arguments are valid. On the other hand, shouldn't a constructive proof of the above statement yield such an automatic conversion.


texts: What are some of the most ridiculous claims in computer science that we haven't disproved?

texts:
What are some of the most ridiculous possible claims in computer science that we haven't disproved?
E.g. For example the claim that ZPP=exptime is absurd but has not been disproven.


texts:
A sorting network is a circuit-based approach to sorting, built out of CompareExchange gates, which compute the function:
$$\mathsf{CompareExchange}(x,y) = (\min(x,y), \max(x,y))$$
The input to the circuit can be assumed to be in $\{0,1\}^n$ (which is viewed as $n$ separate wires).
As sorting networks are phrased in terms of circuits, their control flow can only be a function of $n$, and many $O(n\log n)$ sorts cannot be phrased in terms of sorting networks naively.

A perfect halver is a weakening of the notion of a sorting network. It is another circuit made out of CompareExchange gates, but it does not "fully sort" its input. Instead, it separates the input into a "high set" $H$ and a "low set" $L$, such that all $\ell\in L$ are less than or equal to all $h\in H$, and $|H| = |L| = n/2$.

Given a perfect halver of depth $f(n)$ one can construct a sorting network in depth $O(f(n)\log n)$ via a simple recursion. Since there is a lower bound $\Omega(\log n)$ on the depth of perfect halvers (see for example the introduction of this), this gives a bound $\Omega((\log n)^2)$ on the depth of any such construction, which corresponds roughly to a $\Omega(n (\log n)^2)$ sorting algorithm.
This is usually stated to motivate the construction of $\epsilon$-halvers, which are $O(1)$ depth and the main technique behind the AKS sorting network, which achieves $O(\log n)$ depth.

I have an application where a perfect halver would be desirable, even if it's $O(\log n)$ depth (assuming it has good constants). I'm having difficulty finding any constructions of perfect halvers though, as all of my searches seem to lead to AKS-related constructions.

Are there any constructions of perfect halvers with $O(\log n)$ depth in the literature? I'm interested in practical constructions, so answers like "Use AKS", while technically $O(\log n)$ depth, are uninteresting to me.

The motivation is sorting in a particular situation where all elements in the array $A$ occur with the same frequency, so a $O(\log n)$ depth perfect halver directly leads to an $O(n\log n)$ sorting algorithm on these restricted problem instances (which are of independent interest to me).


texts: Two Generals Problems - What's wrong with my approach?

texts:
Some time ago, I've come across the Two Generals Problem and that it cannot be resolved. Now, recently, I've had an idea how to approach it. IMHO, it is a very obvious way to handle it but I haven't found this way to handle it anywhere and therefore assume my idea is flawed but I can't find the error.
The approach I've found online (from Wikipedia):

A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertainty of the communications channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received.

This seems very crude and the chance of a non-delivery stays at $(1-p)^c$.
My Approach

General A sends a message to General B when to attack. The message contains the following information:

Attack at time $T$.
Send confirmation of receival.
I will not confirm your confirmation.
I will resend the time of attack after time $t$ if I did not get a confirmation.

That way, General A can be sure General B got the message when he gets the confirmation. General B can be $(1 - p)^{m \cdot c}$ sure that it passed after not getting the time of attack again, where

$p$ := probability the confirmation passed
$m$ := multiple of time $t$ that has passed.
$c$ := count of messages sent per time unit (one of the solutions I've come across is to send a lot of messages at the same time).

It does not solve the problem that General B can't be 100% sure that General A received the confirmation but after some time, he can be very certain.
Special Case
Now, if we were to change the scenario slightly, we can reach a 100% certainty for both:

Assume both Generals do not only communicate in order to synchronize the attack but also for other purposes. In that case, General A can send the message:

Attack at time $T$.
Send confirmation of receival.
I will not confirm your confirmation.
I will resend the time of attack after time $t$ if I did not get a confirmation.
I will not send any other communication until I've received your confirmation.

That way, General A can be sure that General B received the plan, when he gets the confirmation and General B can be sure General A received the confirmation when General A sending messages about something else.

So, what is wrong with my approach?


texts: How to show that a language {w|ww^R in A} is regular, A being regular?

texts:
Been working on my homework and I've been stuck on a question for over a week now. Not really asking for a solution but if someone could point me towards the right direction that would be great, as I have literally no idea of how to go about this. A previous question asked us to show that for any DFA that accepts A, we can create a NFA that accepts {wR | w in A}, which was pretty easy (just reverse the DFA).

This question asks: Show that if A is a regular language, then so is {w|wwR in A}, where wR is the reverse of the string w.

I know that if I have two regular expressions, then their concatenation is also a regular expression, that's simple. But this asks me to show that the first-half of some of the strings in A is a regular expression. No idea how to show that this is true. It's not even intuitive to me that this is true, except that the question implies it is.

Anyone got any idea of where to start about this? Thanks!


texts: Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time

texts:
I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values:
a, b, c, d ⊆ ℝ
i ⊆ {true, false}

// unconditional inequality constraints
a < b

// conditional inequality constraints
i -> b < c
i -> b < d
!i -> b > c
!i -> a < d

and I would like to answer questions about the system, such as "is a greater than d?" and "is c less than d?".
One approach would be to formulate this as an integer linear program: in the example above, the non-indicator variables would have domains [0, 3], the indicator variables [0, 1] and a feasible solution might be:
i = 0 (false)
a = 0
b = 1
c = 0
d = 2

I could then answer "is a greater than d?" by comparing the integer values assigned to a and d.
However, I could get the wrong answer for "is c less than d?": the solution above suggests yes, but there exists another feasible solution
i = 0 (false)
a = 0
b = 3
c = 2
d = 1

in which the answer appears to be no. (The correct answer is that we cannot determine the relationship between c and d.)
Now, I could generate ALL the feasible solutions, iterate over them, and check whether c < d in each one -- but I have to answer enough of these questions that this approach would be too slow.
Is there a more efficient and elegant way? Perhaps constraint programming is not even the right way to think about this -- I considered formulating it as a directed graph-search problem instead, where directed edges represent inequality relationships, but my actual system contains conditional constraints as well. The wonderful answer that I received on a related question (https://scicomp.stackexchange.com/questions/36090/constraint-programming-problem-with-conditional-constraints-and-some-unknown-ind) directed me here. Glad for any suggestions or references to relevant papers or textbooks!
Edit: After asking this question to several people (both here and elsewhere), I have received multiple suggestions to reduce these constraints to a comparability graph. To illustrate the challenges of this approach, I have added conditional constraints to my example system above. Is there a way to incorporate such constraints into a comparability graph?


texts: Nilsson's sequence score for 8-puzzle problem in A* algorithm

texts:
I am learning the A* search algorithm on an 8-puzzle problem.

I don't have questions about A*, but I have some for the heuristic score -  Nilsson's sequence score.

Justin Heyes-Jones web pages - A* Algorithm explains A* very clearly. It has a picture for Nilsson's sequence scores.

It explains:

Nilsson's sequence score

  A tile in the center scores 1 (since it should be empty)

  For each tile not in the center, if the tile clockwise to it is not the one that should be clockwise to it then score 2.

  Multiply this sequence by three and finally add the total distance you need to move each tile back to its correct position.

I can't understand the steps above for calculating the scores.

For example, for the start state, what h = 17?

  0 A C

  H B D

  G F E

So, by following the description,

B is in the center, so we have 1

Then for each title not in the center, if the **tile** clockwise to **it** is not the one that should be clockwise to it then score 2. I am not sure what this statement means.

What does the double starred title refer to?

What does the double starred it refer to?

Does the double starred it refer to the center title (B in this example)? Or does it refer to each title not in the center?

Is the next step that we start from A? So C should not be clockwise to A, then we have 2. And then B should be clockwise to A, then we ignore, and so on and so forth?


texts: How do we know $\neg \neg LEM$ isn't provable in MLTT?

texts:
I've been trying (fruitlessly) to prove something which I now know is not provable. Take the following definitions:
$$LEM \equiv \prod_{A : Type} \neg A \vee A$$
$$DNE \equiv \prod_{A : Type} \neg \neg A \to A$$
$$C(x) \equiv DNE \to x$$
I wanted to prove $\prod_{A : Type} C(A) \to \neg \neg A$. In trying to prove it the key thing to prove seemed to be $\neg \neg DNE$. I couldn't figure out how to prove this however. I thought it must be provabale however. Note that the above would be logically equivalent (implication goes both ways) to $\neg \neg DNE$ because the formula trivially implies it.

But this simple formula proved tricky. It feels like $\neg \neg DNE$ should hold because $DNE$ is consistent with MLTT. At least I had it in my mind that it already held but I couldn't seem to find a prove of it. Finally I started searching. I knew that $\neg \neg LEM$ was equivalent and found this: https://ncatlab.org/nlab/show/excluded+middle#DoubleNegatedPEM

This states that $\neg \neg LEM$ is not provable. This is the same as saying that $\neg LEM$ is consistent, at least in MLTT and other such theories. I'm certainly aware that there exist statements for which both the statement and its negation are equivalent but I hadn't realized that $LEM$ and $DNE$ were examples of this in MLTT. I'm kind of baffled that $\neg \neg \neg A \to \neg A$ holds but $\neg DNE$ is still consistent. That's a subtle point about quantifier placement that I must of missed last time I thought about this sort of thing.

Normally in logic when we want to show that something isn't provable we either show that a property that is preserved by all the inference rules (and holds for all axioms) is false for the given statement or we directly find a model for the logic and show that the given statement is false in the model. The only models I know for constructive logics are fairly complicated. For propositional logic we have Heyting algebra but the quantifier here leaves us no hope of using that. I vaguely recall that it is possible to extend these algebras to the quantifier case by doing something like taking the least upper bound or greatest lower bound of a set of instances of the algebra generated by substituting constants in the set being quantified over into the formula. I don't remember exactly how this works nor am I really clear that I could extend a result from first order constrictive logic (the logic of constructive set theory).

How do we know this? Do we have a simple enough model that would explain this? Do we just know from trying to prove it that we get stuck? After trying to prove it myself I feel intuitively that we'll always get stuck and I can explain it more or less as "you have a very limited number of ways to dig down and after digging down, you get stuck really quickly" but that's quite informal. Is there a meaty formal explanation of why this isn't provable?


texts:
I'm trying to practice myself with random algorithms.

Lets call a CNF formula over n variables s-formula if it is either unsatisable or it has at
least $\frac{2^n}{n^{10}}$ satisfying assignments.

I would like your help with show a randomized algorithm for checking the
satisfiability of s-formulas, that outputs the correct answer with probability at
least $\frac{2}{3}$.

I'm not really sure how to prove it. First thing that comes to my head is this thing- let's accept with probability $\frac{2}{3}$ every input. Then if the input in the language, it was accepted whether in the initial toss($\frac{2}{3}$) or it was not and then the probability to accept it is $\frac{1}{3}\cdot proability -to-accept$ which is bigger than $\frac{2}{3}$. Is this the way to do that or should I use somehow Chernoff inequality which I'm not sure how.


texts: Avoiding the trivial certificate in complexity class NP

texts:
One definition of the class NP is that there is a certificate whose size is bounded by a polynomial function of the problem instance size which can be used on a deterministic TM, along with the original input, to decide whether the input is a part of the language.

Doesn't this definition allow the trivial loophole where we let the certificate simply be 1 if the input is a part of the language and 0 otherwise?  Then the deterministic just uses the certificate entirely and totally ignores the input.


texts: Is the $x$ in $\frac{\mathrm{d}}{\mathrm{d}x}$ a symbol in the sense of Harper's PFPL?

texts:
The role of $x$ in $\frac{\mathrm{d}}{\mathrm{d}x} y$ not only confuses my calculus students, it has also puzzled some well known mathematicians. Questions one might ask are:

Does the $x$ in the denominator bind the $x$ in $y$? (Clearly no, since $\frac{dx^2}{dx}=2x$.)
Can one substitute for $x$ in the denominator? (Looks like not, what should $\frac{dx^2}{d3}$ mean?)
Is the $x$ in the denominator itself bound?

I was wondering if interpreting that $x$ as a symbol, in the sense of Bob Harper's Practical Foundations for Programming Languages (Chapter 1.2 on abstract binding trees) might solve these riddles, and if this had already been worked out by someone?

Here's a quote from PFPL:

  It will often be necessary to consider languages whose abstract syntax
  cannot be specified by a fixed set of operators, but rather requires
  that the available operators be sensitive to the context in which they
  occur. For our purposes it will suffice to consider a set of symbolic
  parameters, or symbols, that index families of operators so that as
  the set of symbols varies, so does the set of operators. [...] The
  only difference between symbols and variables is that the only
  operation on symbols is renaming; there is no notion of substitution
  for a symbol.


texts:
I've found a simple multiply-with-add hash function in an old Usenet post.
Can someone identify what hash algorithm is it? An algorithm name or any attribution?

size_t hash(const char* data, size_t length, size_t seed = 1)
{
    for (size_t i = 0; i < length; i++)
    {
        seed = seed * (UCHAR_MAX + 2U) + data[i];
    }

    return seed;
}


texts: Constructing an NFA that is equivalent to a regular expression

texts:
I am a little stuck at attempting to give an NFA for the regular expression $0^+(10^+0)^∗$
, where the alphabet is ${0, 1}$. I have tried to construct multiple NFA's state diagram and the closest I can come up with is
However, I see that this NFA also accepts $0^+(10^+0)^∗0^*$. Is there any way I can alter this state diagram so that it only recognizes $0^+(10^+0)^∗$? I feel that I am missing something simple here...


texts: Multi-Objective Implicit Hitting Set for Multi-Objective MaxSAT

texts:
MaxSAT is a problem related to SAT where there is a finite collection of hard and soft clauses which share boolean variables. The hard clauses must be satisfied while the soft clauses have a weight. The sum of weights of the satisfied clauses is to be maximized.
Multi-Objective Max-SAT is generalization where soft clauses have multiple weights which count towards different objectives. The optima is therefor often not a single assignment but a set of points that show the tradeoff between the objectives. For $n+1$ linearly independent objectives one expects an "$n$ dimensional manifold" as paretofront, the set of points that are not dominated by other points. Max-SAT problems by their nature have a discrete and finite space of possible objective values.
$x^*$ domaninates $y$ in maximization problem if and only iff for all $n$ objectives:
$$     (f_1(y) <= f_1(x^*) \land  f_2(y) <= f_2(x^*) \land \ ... \ \land  f_n(y) <= f_n(x^*) )
     \land (f_1(y) + f_2(y) + \ ... \ + f_n(y)  < f_1(x^*) + f_2(x^*) + \ ... \ + f_n(x^*) ) $$
The MaxHS Algorithm for MaxSAT works as follows:
Require: P=(p, L, c) an equivalent minimization problem
Ensure: returns S ∈ Solc(P) if Sol(P)!=∅, and other-wise “no solution”

  K:=∅;
  while not(∅ ∈ K) do
    let S be s.t. S ∈ minimumcostHS(c,K);
    if p(S) then return S;
    K := union(K,{extractcore(S)});
  return “no solution”;

where L is the finite set of variables occurring in the soft clauses, p a predicate over $2^L$ which checks whether the hard clauses are satisfiable under this partial assignment, and c: $L→R^+$ the cost of this partial assignment.
The algorithm is described in more detail here.
Seeing how a SAT solver is used as oracle to see whether a choice of variables occurring in the soft clauses is viable and learn more about the problem using cores produced by the SAT attempt in case of failure. It stands to reason that a slight modification of the algorithm can produce the pareto frontier of an multi-objective SAT problem.
Such as:
Require: P=(p, L, c) a minimization problem
Ensure: returns S ∈ Solc(P) if Sol(P)!=∅, and other-wise “no solution”
  PF:=∅;
  K:=∅;
  while not(∅ ∈ K) do
    let S be s.t. S ∈ minimumcostHS(c,K);
    if p(S) then
      PF := union(PF,{S});
      accept(S);
    else
      K := union(K,{extractcore(S)});
  return PF;

where L is finite set, p a predicate over $2^L$, and c: $L→(R^+)^n$.
This requires additional modifications of minumumcostHS such that it's aware of the pareto nature of the problem and that it doesn't have to search for solution which would be dominated by something that is already accepted (using this mechanism one could also exclude assignments that are equal in all objectives to something known).
Do you have any suggestions what algorithm i could use for minumumcostHS and accept to complete the algorithm such that it finds one assignment for all objective combinations that are part of the pareto set?
minimumcostHS for MaxSAT is implemented using Integer linear programming.


texts: How to construct this generalized xor without needing an extra vector?

texts:
Operator - Generalized Symmetric Difference

If you take binary xor and generalize it to other radices
you can do so by the absolute value of the difference of each
element in a radix vector.
However this doesn't have the same properties as the binary
symmetric differene.
The reason is that in throwing away the "sign" of the difference
we are unable to reconstruct an operaand given the result and the other
as we can in binary xor. So we lose the nice property

ABA = B

However we keep other nice properties like

A0 = A

AA = 0

There is a way to maintain this property. However, as far as I can tell
it involves emitting 3 vectors for any result. The first vector is the usual
symmetric difference, the other two vectors are binary vectors of equal length
to the first that record the sign of the result, one such vector for each
order of the operands, on being the binary complement of the other. In this way, an original operand can be recovered, given the result and the other opernad, AND that other operands "sign" vector.

For example :

Say we have 2 base 10 vectors corresponding to the numbers 1137 and 9284, what i
s the xor of these two numbers in base 10?

        7  3  1  1              4  8  2  9

        4  8  2  9              7  3  1  1

Signed
Result  3 -5 -1 -8             -3  5  1  8

Sign
Vector  0  1  1  1              1  0  0  0

Symmetric
Difference              3 5 1 8

Recover 1137 given 8153 and 9284

3  5  1  8
+  -  -  -
4  8  2  9

7  3  1  1

My question is : is there a better construction of generalized symmetric difference in any radix > 2 such that we don't need to 'remember the sign' ?


texts:
Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?

Init an empty set.
Add an element to a set.
Given two set, report whether they intersect.


texts: space complexity of DFA intersection problem

texts:
the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper significance in computational complexity theory.[1][2] it is O(n2) time with no better lower bounds known, and tight bounds possibly having major implications on multiple complexity class separations. looking for insight/ refs.

  what is the best known space complexity of determining DFA intersection (emptiness)? how does the best known algorithm work?

[1] Deciding emptiness of intersection of regular languages in subquadratic time / cstheory SE
[2] Two DFA intersection emptiness connections to SETH & L vs P / cstheory SE


texts: Filling a matrix with the sum of conditional values

texts:
I have $P$ vectors of size $N$ with elements in $\{0,1\}$. Each vector $v$ has a value $\alpha_v$.

I would like to Fill a square matrix $M$ of size $N\times N$ in the following way:

$$\forall i,j \in \{1,2,...,N\}~ M_{i,j} = \sum_{\text{vectors}~v : v_i  v_j =1} \alpha_v$$

Is it possible to fill the matrix $M$ in time complexity better than $O(P\cdot N^2)$?

Assuming that each vector has at most $Q$ elements equal to $1$, is it possible to do better than $O(P\cdot(N+Q^2))$ ?


texts: Deterministic Communication Complexity of Equality if inputs differ by at most 1

texts:
The set equality problem in 2 party communication complexity is known to require $n$ bits of communication between Alice and Bob, for $n$-bit inputs $X$ and $Y$.

Suppose that we promise that the symmetric difference of $X$ and $Y$ is $\le 1$. Is the required communication for a deterministic protocol still $\Omega(n)$?

My thoughts: I believe that the complexity becomes $O(\log n)$ because of the following: When Alice gets its input $X$ of size $k$, she knows that Bob's input differs at $\le 1$ index. Thus, there are only $\le {n \choose 1}n + 1 = O(n^2)$ possibilities for $Y$, given $X$; the "+1" is the case where $X=Y$. So there should be a way to convey this information from Bob to Alice using only $O(\log n)$ bits.
Is my reasoning correct?


texts: Closed-form Expression of the Expected value of the Cost of D&C Algorithm?

texts:
Let there is a binary-string, $B$, of length $N$. The probability of occurrence of 0 and 1 in this binary-word is $p$  and $q$ , respectively. Each bit in the string is independent of any other bit.

There is an algorithm (divide and conquer) which finds the location of 1’s in a given binary-string, in Q # of steps (cost).

I am looking for some close-form solution of the expected # of steps,$E[Q]$, with given probabilities $p$ and $q$ for a string of length $N$.

For instance, for $N=4$ the cost ,${{Q}_{i}}$,  for each possible word is:
[\begin{matrix}
   {{B}_{i}} & {{Q}_{i}} & {{P}_{i}}  \\
   0000 & 1 & {{p}^{4}}  \\
   0001 & 5 & {{p}^{3}}q  \\
   0010 & 5 & {{p}^{3}}q  \\
   0011 & 5 & {{p}^{2}}{{q}^{2}}  \\
   0100 & 5 & {{p}^{3}}q  \\
   0101 & 7 & {{p}^{2}}{{q}^{2}}  \\
   0110 & 7 & {{p}^{2}}{{q}^{2}}  \\
   0111 & 7 & p{{q}^{3}}  \\
   1000 & 5 & {{p}^{3}}q  \\
   1001 & 7 & {{p}^{2}}{{q}^{2}}  \\
   1010 & 7 & {{p}^{2}}{{q}^{2}}  \\
   1011 & 7 & p{{q}^{3}}  \\
   1100 & 5 & {{p}^{2}}{{q}^{2}}  \\
   1101 & 7 & p{{q}^{3}}  \\
   1110 & 7 & p{{q}^{3}}  \\
   1111 & 7 & {{q}^{4}}  \\
\end{matrix}]
From the discrete probability theory, we can evaluate the expected cost of the above case ,$N=4$,as follow $\begin{align}
  & \therefore E[Q]=\sum\limits_{i=0}^{{{2}^{N}}-1}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) \\
 & \Rightarrow E[Q]=\sum\limits_{i=0}^{15}{{{Q}_{i}}({{p}^{N-i}}}{{q}^{i}}) \\
 & \Rightarrow E[Q]={{p}^{4}}+4\times 5\times {{p}^{3}}q+2\times 5\times {{p}^{2}}{{q}^{2}}+4\times 7\times {{p}^{2}}{{q}^{2}}+4\times 7\times p{{q}^{3}}+1\times 7\times {{q}^{4}} \\
 & \Rightarrow E[Q]={{p}^{4}}+20{{p}^{3}}q+10{{p}^{2}}{{q}^{2}}+28{{p}^{2}}{{q}^{2}}+28p{{q}^{3}}+7{{q}^{4}} \\
\end{align}$

However, for very large values of N, say 1024, it is computationally not possible to evaluate the cost of each possible binary string (i-e ${{2}^{1024}}=\text{1}\text{.79}\times \text{1}{{\text{0}}^{308}}$ binary words). So, this is the problem I am stuck in.

Is it possible to deduce some analytical/ close-form expression for evaluating the expected value of the cost of this algorithm for a given length N and probabilities p and q (instead of brute-force method defined above)?

I will be very thankful, if someone could help in this regard.

ADDITIONAL INFORMATION:

Divide & Conquer Algorithm:
    Lets take 0000 0001, for instance:

First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.
Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?
Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.
This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.

Efficient Way for evaluating the cost of Above algorithm:
(courtesy to Yuval Filmus)

Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=0101$. Then the sequence is
$$ 11,1, $$
and so $N = 3$ and the cost is $7$.