texts:
Would it be possible to build a progress bar that estimates progress using entropy?

Consider a web browser that is downloading a large file (for instance), which displays a progress bar indicating the amount of progress in the download.  Let $X$ denote the value of the complete file; it is not known until the download completes.  At time $t$, we have downloaded part of the time, so let $Y_t$ denote the information/data received by time $t$.  Initially, at $t=0$, we do not know $X$ (there is some prior distribution on $X$).  The observed data narrows down the set of possible values of $X$.  The more we observe, the less uncertainty there is about $X$; once we've finished downloading the entire thing, the value of $X$ is known and there is no more uncertainty.

Could we use the entropy $H(X | Y_t)$, or something like that, to estimate progress so far and build the progress bar?  Would this work theoretically?  Would it work in practice?  Would it be useful?

Would something similar work for software installation or other uses of progress bars?


texts: Could an NP-hard problem have a mechanical or physical solution method?

texts:
Is there any NP-hard problem that we can find a mechanical "polynomial time" solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we can move water. If this pipe system was suitably built, could we solve say some routing problem by seeing if water flows from one node to another?

So by a mechanical solution, I mean a physical configuration and not a computer program, i.e. I am not looking for a computer algorithm. I also used "polynomial mechanical solution" to describe a solution on a physical device that runs in time polynomial in the order of the input. For example, a piping system could yield the answer in "number of nodes squared" seconds.


texts:
As I was watching a video about single qubit quantum gates, I came across the following gate:
$$\begin{bmatrix}e^{i\sigma}&0\\0&e^{i\theta}\end{bmatrix}$$ The video didn't mention the name of the gate. It gave only the matrix and the following information:

$|0\rangle \rightarrow e^{i\sigma}|0\rangle$
$|1\rangle \rightarrow e^{i\theta}|1\rangle$
$\alpha |0\rangle + \beta|1\rangle \rightarrow \alpha e^{i\sigma}|0\rangle + \beta e^{i\theta}|1\rangle$

In the comments below the video, someone asked what $\sigma$ and $\theta$ could be, and the reply was all real numbers, but this was from someone other than the video maker, so I don't know if this is true.

What is the name of this gate?


texts: The relationship between the capacity and the service rate

texts:
Assume a M/M/1 system is in it's steady state, given the capacity of the system is 200 req/sec at the maximum clock speed of 1 GHz, I'm confused how to get the service time for it? Does the capacity equal to the service rate in this scenario? So can I let the Capacity = μ = 1 / Ts?
Also, knowing the Ts, and given a desired throughput = 60 req/sec, with average per-request latency =  10 ms, do I able to get a response time/Tq with this parameters, and hence compare it to the desired throughput to see if the system can satisfy the customer?


texts:
show whether $n2^n = 2^{O(n)}$ is true or not.

In my opinion, it's false because O(n) can be n and thus the equality will be wrong, because $n2^n$ grows much faster than $2^n$


texts: Clustering Application with a Huge Number of Clusters

texts:
I am wondering if there are any clustering applications in practice where the number of clusters, i.e., the $k$ in the $k$-means problem is very high ($k>50$, optimally $k>200$), if possible with a citation.
The clustering can take place in any metric space.


texts: Why is the Turing Machine a popular model of computation?

texts:
I am a CS undergraduate. I understand how Turing came up with his abstract machine (modeling a person doing a computation), but it seems to me to be an awkward, inelegant abstraction. Why do we consider a "tape", and a machine head writing symbols, changing state, shifting the tape back and forth?

What is the underlying significance? A DFA is elegant - it seems to capture precisely what is necessary to recognize the regular languages. But the Turing machine, to my novice judgement, is just a clunky abstract contraption.

After thinking about it, I think the most idealized model of computation would be to say that some physical system corresponding to the input string, after being set into motion, would reach a static equilibrium which, upon interpretation equivalent to the the one used to form the system from the original string, would correspond to the correct output string. This captures the notion of "automation", since the system would change deterministically based solely on the original state.

Edit:

After reading a few responses, I've realized that what confuses me about the Turing machine is that it does not seem minimal. Shouldn't the canonical model of computation obviously convey the essence of computability?

Also, in case it wasn't clear I know that DFAs are not complete models of computation.

Thank you for the replies.


texts: How to find Time complexity of merge sort with parameter?

texts:
public static void MergeSort(int[] a, int p) {
  MergeSort(a, 0, a.length - 1, p);
}
private static void MergeSort(int[] a, int start, int end, int p) {
  if (end - start > 0) {
    int middle = (start + end) / 2;
    MergeSort(a, start, middle, p);
    MergeSort(a, middle + 1, end, p);
    Merge(a, start, middle, end, p);
  }
}
private static void Merge(int[] a, int start, int middle, int end, int p) {
  int[] b = new int[Math.min(end - start + 1, p)];
  int i = start, j = middle + 1, k = 0;
  while (i <= middle && j <= end && k < p)
    if (a[i] < a[j]) b[k++] = a[i++];
    else b[k++] = a[j++];
  while (i < middle && k < p)
    b[k++] = a[i++];
  while (j <= end && k < p)
    b[k++] = a[j++];
  for (k = 0; k < b.length; k++)
    a[start + k] = b[k];
}

I need to Find Time complexity  of MergeSort ?

the time complexity of Merge is O(min (p,n)) ,so the time complexity of   MergeSort  is O(min (p,n)log(min (p,n)))

is this correct and if not how to find the correct time complexity?

and if I want to prove that MergeSort return Array that containing the first  p elements that are the smallest and they are sorting ?

thanks.


texts: How to add two positive or negative integers using the same Turing Machine

texts:
I want two know how can I add two positive or negative integers using the same Turing Machine
I am using unary numbers in the following way:
0 = 1; 1 = 11; 2 = 111; 3 = 1111 ...
I know how to add two postive integers and I am using this site for tests: https://turingmachinesimulator.com/
name: add two positive integers
init: q0
accept: q3
//-------DELTA FUNCTION:
q0,1
q1,_,>
q1,*
q3,_,>
q1,1
q2,_,>
q2,1
q2,1,>
q2,*
q3,1,>
This is pretty simple, but when it comes to negative integers I have no idea where to start.


texts:
Undirected graph is given which has M edges and N vertices we have to convert every edge from u−v to u→v or v→u such that the total outdegree of every vertex is even.

For example, consider a graph which has the edges 1-2, 1-3, 2-4, 3-4. We can direct it as 1→2, 1→3, 2←4, 3←4, so outdegrees of 1,2,3,4 are respectively 2,0,0,2 which are all even.

Which method or algorithm is suited for least time complexity? M and N are between 1 and 100,000.


texts: Does the concept of subtype require dynamic method binding?

texts:
https://en.wikipedia.org/wiki/Subtyping says

  In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutability, meaning that program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype.

In the concept of "subtype", when explaining "substitutability" as "program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype", does it assume/require dynamic method binding (e.g. the one specified as virtual functions in C++)?

Specifically, given a type B with a method m(), a function

void f(B b){
    b.m();
}

and a subtype S of B which redefines m() method,  which does S being a subtype of B according to the meaning of "substitutability" in the wikipedia article mean:

either if calling f() with an instance s of S, then b.m() in f() will invoke S.m() instead of invoking B.m(), (this case   requires dynamic method binding.)
or if replace B with S in the definition of f(),

void f(S s){
    S.m();
}

still work, i.e. f() can operate with both B and S, i.e. "subtype" only requires  thatS also has a method m() with the same signature as B.m()? (This case doesn't require dynamic method binding.)

Thanks.


texts: Is this problem in P: Finding a common key for a collection of systems of equations?

texts:
Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all possible linear combinations of the equations in $B$.

Given $S_i \subset B$ for $i=1,\cdots,m$, is that possible to compute, in polynomial time, a
$K \subset M$ with minimum size such that $S_i \cup K$ is a full rank system of equations (i.e., the values of all of the variables can be obtained by solving $S_i \cup K$)?

An example: Let $B=\{b_1=1,b_2=0,b_3=1\}$, $S_1=\{b_1=1,b_2=0\}$, and $S_2=\{b_2=0,b_3=1\}$.
$K=\{b_1+b_3=0\}$ is the solution because both $S_1\cup K$ and $S_2 \cup K$ can be solved uniquely and $K$ has the minimum size 1.


texts:
Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can
$$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to
$$ H_{\rm ave} = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n H_{ij}.$$ For all the examples I can think of, these two quantities are of roughly the same order of magnitude.

To make this into a formal question, define
$$\phi(n) = \max_{\mbox{undirected graphs with } n \mbox{ nodes }} \frac{H_{\rm max}}{H_{\rm ave}}.$$ How fast does $\phi(n)$ grow with $n$?


texts:
For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has?
For example a DFA that accepts $\{w \in \{a,b\}^* : w \text{ contains } bbb\}$ should it reject the actual string $bbb$ because it does not contain an $a$?


texts:
Let $T_1,T_2 \subseteq T_\Sigma$ be regular tree languages, f a symbol with arity 2.

To proof: $\{f(t_1,t_2) \mid t_1 \in T_1, t_2 \in T_2\} \subseteq T_{\Sigma \cup \{f\} }$ is regular.

So it's basicaly a tree with f as root and t1 and t2 as left and right children.

My Idea:

I tried to proof regularity by giving a deterministic Tree automaton and I thought to evalute all leafs on the left side with the transition function of t1 and the right side with transition function of t2, and would check if both or one of them end up in an accepting state. The problem is to decide when i should take function t1 or t2.


texts: Probability of k-connectedness for a random graph with given degree sequence

texts:
For a degree sequence $(d_1,\ldots, d_n)$ with $\min d_i \geq k$ pick a graph with that degree sequence uniformly at random. What's the probability that the graph is k-connected?

I know that for Erdos-Renyi graphs the k-connectivity threshold coincides with with the appearance of degree k vertices, but that doesn't say much about the probability when we only know that the minimum degree is $k$.

This question is related to this question. I'd like to estimate how many graphs you need to sample before picking a biconnected graph.


texts: Do Core Computer Programs Have To Function By Powers Of 2?

texts: As an example, the sRGB Gamut is 256 x 256 x 256 (all powers of 2). I'm aware that computers are generally binary. However, is it simply a matter of simplicity that sRGB was made this way, or was it ESSENTIAL? After all, it probably could've safely provided just as many detectable colors with 192 X 192 X 192.


texts: Avoiding "side effects" in recursive functions

texts:
I am writing a function to find the intersection between two sets.

The non-functional requirements of the assignment include avoiding "side effects".

function intersection(a, b) {
  return helper(a, b, []);
}

function helper(a, b, c) {
  if (a.length == 0) {
    return c;
  }

  if (b.contains(a[0])) {
    return helper(a.slice(1, a.length), b, c.concat([a[0]]));
  }

  return helper(a.slice(1, a.length), b, c);
}

Would mutating the argument c in the above code be considered a side effect?

The specific assignment is written in OCaml, so, though the above example is in an imperative language, I want to stay true to the spirit of functional programming.

Please don't provide any alternate solutions to the problem.


texts: Prime factorization for compressing streams of random numbers

texts:
We covered compression/encoding/decoding of data streams very briefly last lecture and I had an odd idea:
Let's say I have a stream of random 8-Bit numbers. Now the probabilty to encounter each number is 1/256.
If I prime factorize each number though I get a stream of prime numbers where I can calculate the probabilty of encountering a specific prime number by looking at how often it appears in all prime factorizations of all 8-Bit numbers.
Here's a couple of issues straight away:

0 and 1 are special cases, they dont have a prime factorization
per-se
the transform is not invertible, you'd have to use seperation
symbols

One way to "solve" both issues is to include 1 as a prime number and encode a number x as a prime factorization of number (x + 1) which allows for 0 and 1 and still fits into 8-Bits because the largest 8-Bit prime is 251. The 1 at the beginning of each prime factorization also serves as a separation symbol.
Could I use this way to somehow ("efficiently") encode a random stream of data?


texts:
We know that $O(f(n)+g(n))=O(max(f(n),g(n)))$.

So can we say that $\Omega(f(n)+g(n)) = \Omega(min(f(n),g(n))$?
Then what is $\Theta(f(n)+g(n))$ equal to?


texts:
Let $U=\{1,2,3\cdots m-1\}$ and some $n$ keys from $U$. Is it possible to sort these $n$ keys in $O(n \log \log n)$ time using $O(n)$ space?

Model of computation is RAM.


texts: Showing that an algorithm is 2-approximation

texts:
I'm having trouble showing that this algorithm is 2-approx.

  We are given a set P of n points on the plane, and a positive integer k. We want to
  partition these points into k sets such that the largest distance between any two points which
  belong to the same part is minimized. Show that the following is a 2-factor approximation
  algorithm.

  Set S = ∅.

  For i = 1, . . . , k do

  Select the farthest point from S and add it to S.

  EndFor

  Put each point p ∈ P in the same part as the closest point in S to p.

I honestly don't know where to start. I can see that after each iteration, the distance between any point in P and the points in S become smaller. But after that I can't really see any good observations.


texts:
On page two of this discussion of spanning trees there are two different tree structures shown, one labeled DFS tree starting from a as the root and the other labeled Spanning tree created by DFS. If I were to write this out on paper my spanning tree would have looked more like the former than the latter.

Are these distinguished here for convenience, one to show the tree structure of the algorithm vs one showing how the spanning tree fits within the original graph layout? Is this a standard convention, to show the spanning tree in the same layout as the original graph? Would it be wrong to diagram the spanning tree using the first layout?


texts: Why don't integer multiplication algorithms use lookup tables?

texts:
It seems to me that we can use lookup tables for multiplication of two integers of size $\log(n)/2$, and that the number of entries for each table of these numbers should be $O(n)$.

Now, multiplying two $n$-bit naturals together can be assisted by using an FFT of size $O(n / \log(n))$.  It seems to me that we can then perform the multiplications and additions for the FFT using the lookup tables.

I'm wondering why this method doesn't or hasn't seemed to get any attention.  Is it because of memory bandwidth problems?

It just seems to me that using tables would be quicker, so I'm hoping that someone can provide me with a better intuition.


texts: Difference between Turing machine end state and halt

texts: Is there a difference between the end state of a Turing machine and the halt state? Especially, for example the Busy Beaver 3. It is said that it is with 3 states but there is also a halt. Is the end state $q_2$ or the $halt$?


texts:
In the propositions-as-types paradigm, we are still faced with the question : what types are propositions ? I currently know 3 different answers :

Coq's sort Prop and its typing rule that asserts it is closed under products indexed by abtirary types
$$\frac{A : \mathsf{Type}_i \qquad x : A \vdash B(x) : \mathsf{Prop}}
     {\prod_{x : A} B(x) : \mathsf{Prop}}$$
HoTT's HProp, which are types where all elements are equal, together with the HProp truncation fun A:Type => ∥A∥, which assigns an HProp to each type A.
Coq's new SProp. As far as I understand, SProp is almost the same as HProp, but instead of explicit rewrites, the type checker will be happy to implicitely convert any element of an SProp into another. So I won't discuss SProp anymore here.

I see some common points between Prop and HProp, the main one being that Coq is compatible with the axiom of proof irrelevance, which asserts that all Props are HProps. Also there is the similar guarded match. Coq accepts to destruct a proof of a Prop only when it is proving a Prop. Likewise, the recursion principle of the HProp truncation accepts to lift ∥A∥ -> B into A -> B, only when B is an HProp. Another common point is seen via Coq's extraction mechanism : all proofs of Props will be discarded, because they map to singleton types.

However I don't clearly see how either of these definitions captures the concept of a proposition. A HProp makes some sense to me, because uniqueness allows to interpret inhabitants as mere proofs that the HProp is true. But then one can argue that a proposition does have different proofs, some being simpler than others for example. Or some using more or less axioms than others (constructive proofs versus classical proofs for instance). Concerning Coq's Prop, I understand that it is impredicative, but I don't think it explains enough. And why didn't Coq take proof irrelevance as a hard typing rule (where 2 proofs are the same Prop would be judgementally equal, rather than propositionally equal) ? I think it would be compatible with HoTT, if we redefine eq in sort Type rather than Prop.

Part of the answer might come from the function extensionality axiom. If it is not there, then it is very hard to prove that a type is a HProp. So Coq's Prop might be a way to handle propositions without assuming funext. For instance, the closure of HProp by the forall quantifier needs funext, so Prop's typing rule might be seen as an instance of funext.

Are there other definitions of propositional types ?


texts: A heuristic for finding a maximum disjoint set

texts:
Background

I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares.

This problem is NP-complete. Many papers suggest approximation algorithms (see Maximum Disjoint Set in Wikipedia), but I need an exact algorithm.

My current solution uses the following divide-and-conquer strategy:

Calculate all horizontal and vertical lines that pass through corners of the candidate squares. Each such line separates the candidates into three groups: candidates that are entirely at one side of the line, candidates that are entirely at the other side of the line, and candidates that are intersected by the line. Now there are two cases:

Easy Case: There is a separator line $L$ that does not intersect any candidate square. Then, recursively calculate the maximum-disjoint-set among the squares on one side of $L$, recursively calculate the maximum-disjoint-set among the squares on the other side of $L$, and return the union of these two sets. The separator line guarantees that the union is still a disjoint set.
Hard Case: All separator lines intersect one or more candidate squares. Select one of the separator lines, $L$; suppose that $L$ intersects $k$ squares. Calculate all $2^k$ subsets of these intersected squares. For each subset $X$ that is in itself a disjoint set, calculate the maximum-disjoint-set recursively as in the Easy Case, under the assumption that $X$ is in the set. I.e., recursively calculate the maximum-disjoint-set among the squares on one side of $L$ that do not intersect $X$, recursively calculate the maximum-disjoint-set among the squares on the other side of $L$ that do not intersect $X$, and calculate the union of these two sets with $X$. Out of all $2^k$ unions, return the largest one.

Question

My question is: What is the best way to select the separator line $L$?

There are two conflicting considerations: On one hand, we want $L$ to intersect as few squares as possible, so that the power set is not too large. On the other hand, we want $L$ to separate the candidate squares to subsets of balanced size, preferrably equal size, so that the recursion ends as fast as possible. What is the best way to balance these conflicting considerations?

EDIT: Additional details

My current heuristic is to pick the separator line that intersects the least number of squares. This heuristic allows the algorithm to process input sets with up to $n=30$ candidates, in several seconds. The optimal solution in these cases has about 10 squares. In general, the number of squares in the optimal solution is near $2\cdot\sqrt{n}$.

When the input grows beyond 30 candidates, the running time becomes much slower (several minutes and more). My goal is to find a heuristic that will allow me to process larger sets of candidates.


texts: Empty string in language with grammar in Chomsky normal form

texts:
In their book, Ullman et al says:

  Every nonempty CFL without $\epsilon$ has a grammar $G$ in which all productions are in one of two simple forms, either:

  $A\rightarrow BC$, where $A,B$ and $C$, are each variables, or
  $A\rightarrow a$, where $A$ is a variable and $a$ is a terminal

  Further $G$ has no useless symbols. Such a grammar is said to be in Chomsky Normal Form or CNF.

whereas wikipedia says:

  In formal language theory, a context-free grammar $G$ is said to be in Chomsky normal form if all of its production rules are of the form:
  $A → BC$,   or
  $A → a$,   or
  $S → ε$,
  where $A$, $B$, and $C$ are nonterminal symbols, $a$ is a terminal symbol (a symbol that represents a constant value), $S$ is the start symbol, and $ε$ denotes the empty string. Also, neither $B$ nor $C$ may be the start symbol, and the third production rule can only appear if $ε$ is in $L(G)$.

Also this site says:

  Any Context free Grammar that do not have $ε$ in it’s language has an equivalent CNF.

So, whats correct?

Can we have $S\rightarrow \epsilon$ in CNF or not? (According to Ullman, no, according to wikipedia, yes) If yes, can other non terminals have $\epsilon$ production? (According to all sources, no)
Can $L(G)$ contain $\epsilon$? (According to Ullman and third reference, no, according to wikipedia, yes)

Am I missing something? and incorrectly trying to relate these sources out of some context?


texts: DFA for Strings with third symbol from RHS as 1

texts:
How can we make a DFA for given condition in title from alphabets {0,1} (binary).

What can be the regular expression for this?

My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'm wrong and help find the correct expression and it's DFA.


texts: Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

texts:
I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that generates $\sum ^*$).

In his textbook, there is a polynomial reduction from $\bar{{ATM}}$ (complement of $ATM$, where $ATM$ is the language that a $TM$ accepts input string $w$) to $ALLCFG$, where the reduction works by mapping $\sum ^*$ to all non-accepting configurations, i.e. if there is an accepting configuration from $G$, then $G$ does not generate $\sum ^*$.

But Sipser does not seem to clarify if $ALLCFG$ is also not turing-recognizable. Since $\bar{ATM}$ (a non computably enumerable language) polynomially reduces to $ALLCFG$, does this mean that $ALLCFG$ is also not computably enumerable? i.e. not turing-recognizable.

Which brings me to my main quesiton -- if $ALLCFG$ is indeed not-turing recognizable, then its complement should be turing recognizable since it would in turn reduce to $ATM$ -- but how should this language be phrased?

P.S. It could not be whether a $CFG$ generates a string $s$ since this language is decidable, but $ATM$ is turing-recognizable only and not decidable


texts: virtual machine based programming languages vs low level

texts:
I took programming lecture it was about C/java and how to build compilers, so I wanted to know.
As far I see, languages like Java/C# are developing their virtual machine CLR/JVM with good base and are improving repeatedly to increse its speed and their JIT compiler.
So I was wondering, is it possible in near future that languages such as JAVA or C# to be faster than C++ ? Or is it logically impossible ?


texts: Does an algorithm exist for scheduling jobs on two processors?

texts:
I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found one processor, or n processors - but none for two. I thought it'd be popular but I can't find if anyone's done this before?

My idea is just like the normal interval scheduling algorithm, to implement a greedy approach. First, sort by earliest starting time. Then, start by scheduling the first job to the first processor. The second job to the second processor. From there, schedule the next job to the processor who is going to finish their job first.

I think it would work, but I think this is in O(n^2) time and I'm trying to get to O(n) or O(n log n)

Any help is appreciated :)


texts:
I would like to know how to alter/add NOTs when applying Duality principle.

Suppose I have P = XY(X+Y) +  NOT(Y), how to find its dual?

My book says that while applying Duality Principle to a relation:

Change all 0s to 1s
Change all ORs to ANDs
Change all ANDs to ORs

But it doesn't say anything about NOTs.


texts:
Is $O(T+\log T)= O(T\log T)$?

I think this is true but I do not know how to show it mathematically?

Please show it using the definition.

Also, if it is true, is the following true?

$O((T+\log T)^{1/n})= O((T\log T)^{1/n})$


texts: Generating hard puzzles for a backtracking snake

texts:
Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer.

There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get from one side to the other, i.e. to move from column $c$ to column $c+1$, the snake must choose an integer from both. Whatever the snake picks from column $c$, it can never pick the same integer again in $c+1$, nor from any column that appears later.

For example, suppose each entry in column 1 has integer 1, each entry in column 2 has integer 2, and so on. Now the snake can move very freely: in fact, we have $h$ choices in each of the $w$ columns. Even a blind snake gets through the matrix easily.

The goal is to generate matrices that are difficult for a snake that performs some kind of exhaustive backtracking search. The matrices can be tall, but preferably not wide. Can we assign the integers to $M$ such that there is exactly one (i.e. a unique) path through it? The hope is matrices with unique valid paths through them are difficult for a backtracking snake.


texts: How to extend a hash function to manipulate longer integers?

texts:
Carter and Wegman introduced in the paper Universal Classes of Hash Functions the $H_{1}$ universal class of hash function. This is essentially the function
$h_{a,b}(x) = ((a\cdot x+b)\mod p)\mod m$. I am using here the more common notation from CLRS book respective description, and not from the paper.

Some notation:

$x$ is the input to hash function (the key) and takes values in $\{0..u-1\}$
$p$ is a prime $\geq u-1$
$a$ is a random number in $\{1..p-1\}$
$b$ is a random number in $\{0..p-1\}$
And obviously the outputs of hash function are in $\{0..m-1\}$

The problem is that if key word $x$ is large enough, the multiply and add operation involved in the hash function maybe lead in an overflow.
For example if $u= 2^{32}$, $x= 2^{32}-1$, then we cannot hold the outcome of $a\cdot x + b$ in a 32-bit word. But even if we can (using 64 bit word) the least prime $p$ we can use is $4294967311$ which can be represented by 34 bits. In that case $a$ and $b$ will possibly have values of 34 bits long, so a 64 bit word can't hold the outcome of $a\cdot x + b$ leading in an overflow.

The authors of the paper describe a way to manipulate longer integers in proposition 8 and the following paragraph, using hash functions working with shorter integers.

Can anyone please demystify the way we can extend this function to manipulate longer integers and why this is working? The paper can be found  here here


texts: Does a simple calculator have compilers?

texts:
When I input something wrong in my Casio fx-82MS calculator it shows Syntax error on its screen.

So does even a simple calculation on a most simple calculator like this goes through compilation phases? or is it directly the hardware that is doing all the stuff and showing the output or is there some kind of very basic software running and undergoing compilation?


texts:
The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

Recursion tree. We see that
$$\begin{align}
\sum_{i = 0}^{\log_{3}(n)}n2^i & = \Theta(n^{1+\log_3(2)})\\
& \ll T(n) \\[1em]
& \ll \sum_{i = 0}^{\log_{\frac{3}{2}}(n)} n2^i \\[0.5em]
& = \Theta(n^{1+\log_{\frac{3}{2}}(2)})
\end{align}$$
but cannot, as I can see, get $\Theta(T(n))$ exactly.
Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for $p$, one better than $2+2^{p+1}=3^p$. I believe such a closed form does exist, it might be found with domain transformations or something like that.

This is problem 2(m) from Jeffrey Erickson's notes on recurrences:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

Any help is appreciated.


texts: Practical importance of Turing machines?

texts:
I am an electrical engineer, and only had one CS course in college 26 years ago. However, I am also a devoted Mathematica user.

I have the sense that Turing Machines are very important in computer science. Is the importance only in the theory of computer science? If there are practical implications/applications what are some of them?


texts: Identity in the category of types and functions

texts:
In the model of (functional) programming languages as a category where the objects are types and the arrows are functions, I'm trying to really understand what's really the identity arrow.

Barr-Wells "Category Theory for CS" says you need the id function, but I wonder: it really has to be the "do nothing" function? For any type A, doesn't any function f:A->A work? If looking at type level, I can't distinguish the functions, shouldn't be ok?

I'm trying to find a counter-example but couldn't.

EDIT:
I was thinking on the Hask category but I guess my question in Category Theory terms is:
Does every endomorphism in an object A is isomorphic to the identity arrow in A?


texts: Which type of computer programs could be called intelligent agents?

texts:
I know some computer programs can be modeled as intelligent agents, for example a chess program which plays against a human. The environment is the chess board stored in the memory and actuators are commands to move a piece. Another intelligent program may react to the user commands.

My question is could any computer program be regarded as an intelligent agent? for example a media player, or a simple calculator?

If no, which characteristics a program should possess to be called an intelligent agent?


texts: Why is the sequence, "1,3,2,4", not a bitonic sequence?

texts:
A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.

According to the definition of a bitonic sequence, we know that a graph of a bitonic sequence can have at most one "peak" and one "valley".

So, why is the sequence 1,3,2,4 not a bitonic sequence?

I have referred the book, "Parallel Computing", by M. J. Quinn.


texts:
I have written a math library which handles really big numbers with good precision. Each digit is stored in a nibble and a 'nibble array' makes up the number. There is no epsilon portion, as for currency calculation big brother is happy enough to loose penny fractions with int like rounding.

My problem is $a^b$ . It's all ok if $b$ is an integer value, but what if it has decimal digits.

But how to calculate $4.613765^{3.14259}$ from first principles. It's so long since I did a-level math I don't know where to begin.

  How to calculate $a^b$ when $b$ is not an integer?


texts: How to use butterfly network for data copy?

texts:
I know butterfly networks (and benes as well) allow routing a packet from any input to any output node. Congestion is $\sqrt{n}$ but with bene it can be $1$.
Now assume that in a butterfly network, each switch is a selection switch, i.e. the switch has two inputs terminals and two outputs terminal but it "copies" one of the inputs to both of its output terminals( based on control bit).
I am trying to resolve a bit different problem. Let there are $n$ input nodes and $n$ output nodes. Following are the requirements of the problem:

For each input packet $i$, we want $k_i$ output nodes to have $i$.
$\sum_{i=1}^{n}k_i=n$

Note that the problem does not care about the arrangement of output but just the number $k_i$, like any $k_i$ output nodes can have packet $i$.  I have tried few examples on the butterfly network and it works fine but I am not sure how can we prove correctness for this network.


texts: Local to global algorithms in gossip based P2P networks

texts:
Suppose we have a peer to peer network of, say, $n$ peers. Peers communicate by an asynchronous randomized gossip protocol (Push, Pull, Push/Pull doesn't really matter here). The task is for any local peer to get an (approximate) picture of the global communication in all of the network over time.

I mean after some time $t_1$, each local peer $k$ should have a data structure that is the record of every gossip event that took place in all of the network up to a time $t_2$, with $t_2\leq t_1$. This data structure should provide knowledge about the appearance of events globally over space and time.

To make it "simple", we can assume, that communication channels never fail. Every peer can reach every peer. However since peers might crash or disappear, we can not just choose some central peer that records everything and then redistributes its knowledge.

A solution exist in the so called hashgraph algorithm, which goes roughly as follows:

Every peer stores locally a directed acyclic graph, to record the gossip events. Vertices are the gossip event together with an identifier of sender and receiver. Each vertex has two incoming edges, which might be called $sender\_parent$ and $receiver\_parent$. $sender\_parent$ is an edge from the previous gossip event of the sender and $receiver\_parent$ is an edge from the previous gossip event of the receiver. Outgoing edges are of arbitrary number.

Each time a peer connects to another peer it askes for the previous gossip event of the receiver, then creates a new vertex locally to record *this event. Then it transfers all of the graph along to the other peer. (This is a simplification for the push protocol and can be tweaked appropriately for pull or push/pull as well)

The question now is, whether or not this is essentially (up to isomorphism) the only way to do it. The hashgraph algorithm is patented. Therefore it would be good to know if other solutions exist. With such local to global views, network analysis can be quite efficient.

Edit: The system is free to implement any kind of communication contend, which makes the task possible.


texts: Can we recognize wheter a Turing machine is a decider?

texts:
Let

$L=\{ \langle M \rangle \mid M \text{ is a Turing Machine which halts on all inputs}\}$.

Is this a Turing-recognizable language? I guess that it is neither Turing-recognizable, nor co-Turing-recognizable, but I can't prove it.


texts: In the second chance page replacement algorithm, if a page's reference bit is already set to 1, and the next page in line of the reference string is the same page, does the reference bit stay at 1 or is it reset to 0?


texts: Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}

texts:
I have the following question :
\begin{align}
L_2 = \{a,k\ \mid \text{ a is a 3DNF (disjunctive normal form) and} \\
\text{there exists an assignment $z$ satisfying exactly $k$ clauses in }a\}
\end{align}
I know that $L_2 \in$ NPC.
Show that $L_2 \in$ NP is relatively easy, I'll skip that part.
I try to show that $L_2 \in$ NPC using a reduction from VC $\leq_p L_2$ (VC is vertex cover which we know in its NPC)
I defined the following function $f$ :
$$f(G,k)=(a,k)$$
I thought of something like that for each node $i$ in $G$ will define a literal $x_i$, and make it in 3DNF format, $a=\bigvee(x_i \wedge x_i \wedge x_i)$ where $1 \leq i \leq n$ where $n$ is the number of nodes in $G$.
We can define that following $z$ such that $z$ safifies exactly $k$ clauses, just give $'1'$ literal $x_i$ such that the node $i$ is in the VC, and $'0'$ otherwise, so such $z$ exists.
So easy to see that $(G,k) \in$ VC $\implies (a,k) \in L_2$ since we showed explicitly such $z$ that safifies exactly $k$ clauses.
But I'm not sure the other side holds $(G,k) \not\in$ VC $\implies (a,k)\not\in L_2$ we given a graph that doesn't have VC in size $k$ but I think due to my building of a ($a=\bigvee(x_i \wedge x_i \wedge x_i)$) we can find $z$ that safifies exactly $k$ clauses (actually we can find $z$ that safifies $x$ clauses where $1 \leq x \leq n$ where $n$ is number of nodes in $G$.
So my reduction doesn't hold?


texts:
People usually say Coq does not allow writing non-terminating functions. I have a question regarding that.

Does Coq allow writing exactly all terminating functions? In other words, what are the completeness and soundness properties of Coq's procedure for checking well-foundness of fixpoint definitions?


texts: Is automatic multicore support at the hardware or compiler level possible?

texts:
Due to technical constraints, single thread performance has been increasing more slowly and adding cores has been adopted to offer greater potential increase in performance.

However, multicore support currently appears to require the programmer to manually divide the work, control communication/synchronization, etc. For many processor intensive games and simulations (such as DCS), such complicated multithreading effort has been limited, and these programs depend extremely heavily on single thread performance.

Could a processor with multiple cores divide the work automatically?

Alternatively, could a compile convert single-threaded code to mulithreaded code?
In the current world, multicore support has to be done by hand as far as I know, with a result being that many processor intensive games and simulations (such as DCS) depend extremely heavily on one CPU core to avoid complicated multithreading.


texts: find an element in array that appeared at least 51% times

texts:
Given an array with n rational numbers, element in is array called popular if it have appeared at least in 51% of the indices.

I have to design an algorithm that finds such element in O(n) worst case complexity time, that if there is one.

The only ideas I have is to use hash tables but the complexity time is O(n) in average and counting sort but it only works with natural numbers.

Is there anything I am missing or I can use ?


texts: This costs minimization problem, is it solvable in polynomial time?

texts:
I have the following problem: I have $c$ conflicts, named $(c_1, \ldots, c_c)$, where each conflict $c_i$ has certain size $s_i\in\mathbb{N}_0$: the number of times conflict $c_i$ has happened. Also, I have $m$ conflict resolution methods, named $(m_1, \ldots, m_m)$. Each method $m_j$ cannot be used more than $u_j\in\mathbb{N}_0$ times, and each time you use it, you have to pay $p_j\in\mathbb{N}_0$ dollars, but you get that each conflict $c_i$ connected to $m_j$ is reduced by $\min(r_{ji}, s_i)$ units ($s_i \leftarrow s_i - \min(r_{ji}, s_i)$, for each $c_i$ connected to $m_j$).
Once some $s_i=0$, the corresponding $c_i$ must be removed, and once some $u_j=0$, node $m_j$ cannot be used anymore so it can be removed as well.

The problem is solving all conflicts (making every node $c_i$ dissapear after making $s_i=0$) by repeated uses of the available methods, expending a minimal amount of money.
For example, if we call $E$ our total expended money (with an initial value of $0$), and, for the sake of simplicity, assume that every $r_{ji} = 1$, one use of $m_2$ implies the following updates:
E <- E + p
u2 <- u2 - 1   # If u2 becomes 0, remove m2 from the graph.
s3 <- s3 - 1   # If s3 becomes 0, remove c3 from the graph.
s4 <- s4 - 1   # If s4 becomes 0, remove c4 from the graph.
s5 <- s5 - 1   # If s5 becomes 0, remove c5 from the graph.

It's guaranteed that all conflicts can be solved. In other words, each $s_i\leq\sum_j(\{r_{ji}*u_j : m_j\text{ is neighbor of }c_i\})$.
Can this problem be solved polynomically? My guess is yes by using first the method that has the least "cost-per-conflict". In other words, at each iteration, make one use of the $m_j$ that minimizes $p_j/\sum_i(\{min(r_{ji},s_i) : c_i\text{ is neighbor of }m_j\})$ and afterwards remove all nodes that became $0$.
But, since the removal of conflicts increases the "costs-per-conflict" of the surviving methods for the next iteration, I'm not sure if this eager algorithm will lead to an optimal solution or whether a solution algorithm requires dealing with combinatorial explosion to be optimal.
In other words; I'm not sure if such eager algorithm causes that early eager choices will force an unneccesary number of uses of more expensive methods later, avoidable by not taken so eager choices earlier, like any other NP-hard problem.


texts:
I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.
I have a set of species made from a number of components.
Let's number each component $0, 1, 2 ... n$.
So now each species can be described as a set of these components. Each species is unique.
I am given a set of species, and I need to check whether any subset of these species fulfills the following condition: that the number of species in this subset is greater than the number of unique components in this subset.
For example: the set of species {[0, 1, 2], [0, 2], [1, 2], [0, 1]} fulfills the criterion, as the set has 4 species and 3 unique components. The set of species {[0, 1, 2], [0, 2], [1, 2], [0,1], [3,4]} also fulfills the criterion, as a subset of the set fulfills the criterion. The system {[0, 1, 2], [0, 2]} does not fulfill the criterion, as there are 2 species and 3 unique components.
In case it is relevant: there can be many species and components (20) but the number of components per species remains relatively small (2-5)
An easier version of this problem is also of interest to me: I have system which I know does not fulfill the criterion. The question is: if I add this species, will it fulfill the criterion?
This problem is equivalent to determining if a system of equations is over determined.
Edit: The criterion is equivalent to checking if the Gibbs Phase Rule is being violated in a system with only pure solid phases with at least 1 degree of freedom in addition to pressure and temperature. In this situation the number of phases is equal to the number of solids. There has a 0 or positive number of degrees of freedom left in the system or it becomes over constrained, so $0 \geq \text{number of components} - \text{number of species}$


texts: How do I assign homes to hospitals based on locality? (clustering, kmeans?)

texts:
I have a large set of $(X)$ hospitals and $(Y)$ homes, where $(Y)$ is much larger than $(X)$, and their respective coordinates. Each hospital can handle any home within a 50 mile radius, and up to 10,000 homes. Homes can be assigned to one hospital. How do I create assignments of homes to hospitals such that as many homes can be assigned a hospital? Performance doesn't matter that much.
I was thinking of potentially getting each hospital to do a breadth first search to reach as many homes as possible near it. For this, I was thinking of calculating the distance to all homes from each hospital, then going through each home and matching with the nearest hospital until all homes are filled or can't be any more.
Would this be a good approach? What would a better approach be? Are there clustering algorithms that could help here such as kmeans?


texts: How approximate are "approximate" nearest neighbor (ANN) search algorithms?

texts:
Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are.

If I have a (more or less) randomly distributed point cloud what is the likelihood that I get the exact nearest neighbor given a target point within the clouds bounding box?  I know that it is dataset dependent... but does anyone have a good numerical study somewhere that shows trends?


texts: Subexponential algorithm for Np-complete problems

texts:
https://cstheory.stackexchange.com/a/3627/32204

Could someone explain to me why this reasoning is false. I don't understand it! To me this sounds plausible!


texts: Abstract data types (model, principle of no junk)

texts:
I have the following abstract data structure

Now i have to find a model that satisfies the principle of no junk and proof that

Could someone advise me to get to a solution and to understand the whole topic?

Thank

1 spec NatSet = Bool and Nat then
2
3 sorts
4 natSet = emptySet | add(natSet, nat)
5
6 ops
7 isEmpty: (natSet) bool,
8 contains: (natSet, nat) bool,
9 union: (natSet, natSet) natSet,
10 intersect: (natSet, natSet) natSet
11
12 vars
13 s,s’: natSet,
14 n,n’: nat
15
16 axioms
17 isEmpty(emptySet) = true
18 isEmpty(add(s, n)) = false
19
20 contains(emptySet, n) = false
21 contains(add(s, n), n) = true
22 n 6= n’ ⇒ contains(add(s, n), n’) = contains(s, n’)
23
24 union(emptySet, s) = s
25 union(add(s, n), s’) = add(union(s,s’), n)
26
27 intersect(emptySet, s’) = emptySet
28 intersect(s, emptySet) = emptySet
29 intersect(add(s, n), add(s’, n)) = add(intersect(s, s’), n)
30 n 6= n’ ⇒ intersect(add(s, n), add(s’, n’)) =
31 union(intersect(s, add(s’, n’)), intersect(add(s, n), s’))
32 end


texts: Can we add dependent type into an existing imperative programming language?

texts:
As we know, dependent type allows programmers to write bugless programs.
But as I know there's only very few languages support dependent type, like Haskell with extensions, Idris, Agda, F*, etc.

Since these are all functional languages, is there any possibility to add dependent type into an imperative language?

I've googled and found some papers like http://www.ats-lang.org/MYDATA/Xanadu-lics00.pdf or https://www.cs.bu.edu/~hwxi/academic/papers/XanaduAbs.ps, but they create their own languages.


texts: Why aren't we researching more towards compile time guarantees?

texts:
I love all that is compile time and I love the idea that once you compile a program a lot of guarantees are made about it's execution. Generally speaking a static type system (Haskell, C++, ...) seems to give stronger compile-time guarantees than any dynamic type system.

From what I understand, Ada goes even further with regards to compile time checking, and is able to detect a greater range of bugs ahead of execution. It's also considered fairly safe, given that, at some point in time, it was chosen for delicate fields (when programming errors may cost human lives).

Now, I wonder: if stronger static guarantees, leads to code that is more documented and safe, then why aren't we researching more in that direction?

An example of something that seems to be missing, would be a language that instead of defining a generic int type that has a range determined by the number of bits of the underlying architecture, one could have ranges (in the following example Int [a..b] describes an integer type between a and b included):

a : Int [1..24]
b : Int [1..12]
a + b : Int [2..36]
a - b : Int [-11..23]
b - a : Int [-23..11]

or (taking this from Ada):

a : Int [mod 24]
b : Int [mod 24]
a + b : Int [mod 24]

This language would select the best underlying type for the range and would perform compile time checking on the expressions. So that, for example, given:

a : Int [-3..24]
b : Int [3..10]

then:

a / b

will never be not defined.

This is just an example but I feel like there's a lot more that we can enforce at compile time. So, why there seems so little research on this? What are the technical terms that describe this idea (so that I can find more informations on this topic)? What are the limits?


texts:
NFA (nondeterministic finite automata) accepts only finite words while a NBA (nondeterministic Büchi automata) accepts infinite words (and hence $\omega-$regular languages).
I think the example automata accepts finite word like $A,B,A,B$. But it also accepts infinite words like $A,B,A,B,...$.
How can i know if the example-automata accepts the finite language $(AB)^*$ or the infinite language $(AB)^{\omega}$(is the automata an NFA or NBA)?
Can it be differed and if yes how?


texts: Is there a complexity metric for finite state machines?

texts:
I'm working on evolving Turing machines (with binary symbols / infinite tape) for simple operations (e.g. sorting) using genetic algorithms. I'm interested in using the complexity of the FSM for each Turing machine as one of the criteria to guide the evolution process.

However, I couldn't find any references as to a canonical complexity metric for FSMs. I imagine the metric would include some combination of the number of states, number of transitions, and number of input symbols, but I'm not sure how these would be combined appropriately into a normalized metric.

Is there a canonical (ideally normalized) complexity metric for finite state machines?


texts: Does SAT always have short analytic proofs?

texts:
By analytic proof, I mean mainly resolution and also other valid syntactical manipulations of the set of clauses, old and new. So this is a search over problem space rather than solution space. The question is:

Is there a family of instances of SAT that doesn't have polynomial-size analytic proofs of their satisfiabilities?

If all families have short analytic proofs, then if we can find them in short time, that means P = NP. But even if there aren't always, there still may be other means to solve SAT in polynomial-time. So this is only one way to attack P vs. NP. But it's curious to know on its own.


texts: Does a greedy task selection algorithm find a c-approximate solution?

texts:
I was told this question may be better suited here.

  A scheduling problem can be stated as: Given a set
  $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and
  end times, choose the maximum size subset of non-overlapping tasks.
  Choosing tasks greedily by earliest finishing time gives an optimal
  solution, but what about heuristics: earliest starting time, shortest
  length, and fewest incompatibilities? Does each heuristic find a
  $c$-approximate solution, for some constant $c$?

How do you typically solve problems like this? How can we know whether a $c$-approximate solution is found (i.e. a subset of tasks whose size is at least 1/$c$ of the optimum)? I don't see how we can bound a heuristic, it seems like there are a lot of possibilities for the answers that it will return.

For example, in the earliest start time heuristic, we can always guarantee that it will select one task (the first one- with earliest start time), but it doesn't seem like we can guarantee anything more.

For the shortest length, it seems like we can get closer to the optimal solution, and to me it seems like we can always guarantee that if the optimal solution is $m$ tasks, shortest length will select $m-1$ tasks.


texts: Hoare correctness proof for a recursive definition of multiplication

texts:
Given the program:

{y=y0 ^ y>=0}
    z=0;
    while (y>0){
        z=z+x;        (1)
        y=y-1;
    }
{z=x*y0}

I am having trouble finding the invariant, I've tried:

z=xy-xy
z<=xy
z=0xy

with/without the precondition as the invariant, but none of my attempts can be used to prove the post-condition. Any help would be greated appreciated!

Moreover, if the code at (1) is changed to z=z*x;, how should I modify my invariant?


texts:
I have an undirected graph where I need to find routes of minimum cost in a point to multi-point, but where cost can be reduced by creating intermediate "packs" of routing terminals. I am currently unable to accurately and in reasonable time locate where I can pack my terminals.

In the whole problem, from a connected graph $G$, a node $s$ and a set of nodes $t$ we are looking for a collection of path that have the following properties:

All elements of $t$ must have a path to either $s$ or an intermediate point. These paths are weighted the sum of their arc distance.
If an element of $t$ have a path to an intermediate point, there must be between 3 and 5 paths from distinct nodes of $t$ to that point.
All intermediate points must have a path to the $s$. These paths are weighted the double of the sum of their arc distance.
We look for an algorithm approaching or computing exactly a minimum weight solution.

Note that because the weight is being proportional to distance, we will admit a minimum weight solution is easily found once the intermediate points, along with the set of $t$ nodes that have a path to it, are know.

For example in this graph I'd expect the algorithm to return me a pack $\{t1, t2, t3, t4, t5\}$ on node $p$ because it would be the minimum cost setup:

Total cost here being 7 for routing $t$ points + 6 for routing the intermediate point = 13, much less than if all $t$ were routed to the source (5*4 = 20) and a bit less than if they were packed at point 3 (5*2 + 2*2 = 14)

We need to find as close as possible to the optimal setup, but in our actual datasets, there is usually over 400 terminals, and we can't enumerate all possible partitions of 3 to 5 terminals to compute a routing. How can I efficiently find these intermediate stage routing points (where to "pack" my terminals) ? Is there any existing research or algorithms on the matter ?


texts: Difference between "information" and "useful information" in algorithmic information theory

texts:
According to Wikipedia:

  Informally, from the point of view of algorithmic information theory, the information content of a string is equivalent to the length of the shortest possible self-contained representation of that string.

What is the analogous informal rigorous definition of "useful information"? Why is "useful information" not taken as the more natural or more fundamental concept; naively it seems a purely random string must by definition contain zero information, so I'm trying to get my head around the fact that it is considered to have maximal information by the standard definition.


texts: On an HDD if data is fragmented the discs need to be spun to where the next block in the file is, so how and where data is stored can make a big difference in how long it takes to retrieve the data. With an SSD is the retrieval time for fragmented data constant (due to no moving parts and it being entirely electronic)? Does this mean it doesn't matter how the data is stored on the drive?


texts:
What algorithm can be used to correct a two-bit error in a message protected by a 32-bit CRC, assuming the CRC polynomial allows that? I'm seeking something for 480-bit payload, able to detect uncorrectable errors, fast in the worst case, and compact.

Because I have hardware support for that, I'm most interested in the CRC-32 IEEE 802.3 primitive polynomial (allowing two-bit error correction for payloads up to 2974 bits),
$$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$$
but the question is of theoretical interest for others, such as the CRC-32K polynomial proposed by Koopman (allowing two-bit error correction for payloads up to 16360 bits)
$$(x+1)(x^3+x^2+1)(x^{28}+x^{22}+x^{20}+x^{19}+x^{16}+x^{14}+x^{12}+x^9+x^8+x^6+1)$$

Assume payload data of $b$ bits (assimilated to the coefficients of a binary polynomial $B(x)$ of degree less than $b$), to which is appended a CRC computed with binary polynomial $P(x)$ of degree $c=32$, as $C(x)=(B(x)\;x^c)\bmod P(x)$. It is then stored in memory $b+c$ bits of $B(x)\;x^c+C(x)$. On reading is it computed the syndrome $S(x)=(B'(x)\;x^c+C'(x))\bmod P(x)$. Assuming there has been at most two bits in error, and $b$ is small enough:

If $S(x)=0$, then there has been no error.
Otherwise, if there exists $i$ with $0\le i<b+c$ such that $S(x)=x^i\bmod P(x)$, then there has been a single error, and $i$ tells where, allowing correction.
Otherwise, there has been two errors and there exists $i$ and $j$ with $0\le i<j<b+c$ such that $S(x)=(x^j+x^i)\bmod P(x)$; again finding $(i,j)$ allows correction.

The case of a single bit in error is relatively easy; that's a discrete logarithm problem, with an easy size versus speed compromise: we can have a precomputed table allowing solving in a single lookup for $i$ multiple of $k$, and use that $k$ times. But I'm stuck with the case of two bits where I have nothing much better than trying all $j$ and doing as for a single bit in error.


texts: How to construct an ordinary matching from a fractional matching?

texts:
Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge  $e \in E$ to a fraction $f(e) \in [0,1]$, with the constraint: for $v \in V$, $\sum_{e \ni v}f(e) \leq 1 $.

My question is : does the fractional matching give a matching that we know (of $G$) i.e. with no conflicting edges? I am confused, since there is no criteria for choosing a fraction  $f(e) \in [0,1]$, for every $e \in E$. For example, if we have $e_{1}, e_{2} \in E$ such that $v \in e_{1}, e_{2} $ and I assign $f(e_{1})=1/4$ and $f(e_{2})= 1/2$, then $f(e_{1})+f(e_{2})=3/4 \leq 1 $, hence both $e_{1}$ and $e_{2}$ should belong to the fractional matching.

Thank you in advance.


texts:
See some related questions in Cont: NP-hard or not: partition with irrational input or parameter

  Given a set $N=\{a_1,...,a_{n}\}$ with $n$ positive numbers and $\sum_i a_i=1$, find a subset $S\subseteq N$ such that $F(\sum_{i\in S} a_i;\alpha)$ is maxmized, where $F(\cdot;\alpha)$ is a known fixed function with parameter as $\alpha$.

Method 1.

To prove the complexity of the problem above, I set $\alpha=1$. Then $x_*=\textbf{argmax}_{0\le x\le 1} F(x;\alpha=1)$ can be calculated, which is an irrational number and $x_*\approx 0.52$.

Instance

  Given a set $N=\{a_1,...,a_{n+2}\}$ with $n+2$ numbers where

  $a_1,...,a_n$ are positive and rational,
  $\sum_{i=1}^n a_i = 0.02$,
  $a_{n+1}=x_*-0.01$, and
  $a_{n+2}=0.99-x_*$,

determine whether we can find a subset of $N$, such that the sum of the subset is $x_*$.

NP-complete

  Since $x_*$ is irrational, the desired subset cannot contain both of the last two numbers.
  Since the sum of any subset not containing the $(n+1)$th element is smaller than $x_∗$, the desired subset must contain the $(n+1)$th element.
  The remaining question is to find a subset of the first $n$ numbers whose sum is 0.01

So the original problem is NP-complete.

Criticism

Since $x_*$ is irrational, I can't store irrational numbers in a machine properly and my proof is not correct.

Method 2

Set $\alpha$ with some value which may be irrational, such that $\textbf{argmax}_{0\le x\le 1} F(x;\alpha)$ is rational. Then repeat the process in method 1 and the problem can be reduced from a subset sum problem. This proof does not have the issue of encoding irrational numbers.


texts: Complement of non-deterministic finite automation

texts: Given an NFA, is there a way to “take its complement” and obtain an NFA that recognizes the complement language?


texts:
I am from ECE background and trying to solve channel allocation problem. Let's assume I have three users and three available channels. I would like to allocate channel among them in such a way that average BER would be minimum.
For example, consider BER matrix for each user for each frequency allocation
\begin{bmatrix} User/frequency & User1 & User2 &  User3 \\ f1 &0.01 & 0.05 & 0.3\\f2 & 0.12 & 0.045 & 0.02 \\ f3 &0.02 & 0.01 & 0.01 \end{bmatrix}

Now, I would like to allocate channels f1--> User1, f2--> User3 and f3-->User2, which gives least average BER (Sum of each users BER/no of users).
(Note: Same frequency can't allocated to different users.)

Brute force is obliviously one solution, but I am trying to find optimized solution.


texts:
I have laid out the various cases that would make this not a context free language already and proved all but one for this  set:

\begin{equation}
A = \{a^f b^g    \mid      f = g^2\}
\end{equation}

I am having trouble trying to explain how if v was a's and x was b's for this problem.  Exactly how would I prove that using this case is it not a context free language.  Steps and explanation would help.

Thank you!


texts:
Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need  to be sorted. Let $array_i$, $array_j$ and $array_k$ be the values at those indices and now you make a right shift to it, that is $new$ $array_i$= $old$ $array_j$ and
$new$ $array_j$= $ old$ $array_k$ and $new$ $array_k$=$old$ $array_i$. Find the minimum number of operations required to sort the array or if is impossible how to determine it.

Example :
Consider $array= [3,1,2]$; consider indices $(1,3,2)$ in the given order after applying one operation it is $s =[1,3,2]$.

Can anybody share your approach.


texts: An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$

texts:
If $n<100$ then $O(n^2)$ is more efficient, but if $n\ge 100$ then $O(n\log n)$ is more efficient.

I am sure that this statement is valid, but I don't know how to prove it or justify it. Can someone please help me?


texts: Removing common background in image processing phase for classification

texts:
I'm trying to build a machine learning classifier that can detect which object is in an image. I have a labled training set of images and am currently in the image processing phase. Each of these images has one of the objects. However, almost all images have these objects embedded in a very common background color amongst all images.

These are not the images i'm training on but they give the general idea:

The background red is more or less uninformative of what object is in the picture. In order to reduce the dimensionality of my problem, I'd really like to apply an algorithm that somehow extracts the object from the common background. My idea after that was then to resize the resulting images all to some common dimension. Then i was going to try to do some deep learning. Does anyone know any algorithms in computer processing that can do this?


texts: Calculating the structural integrity of a pixel grid

texts:
Preface
So this is a question that came from an idea for a game. This game is voxel-based, and I am interested in calculating structural integrity, with some blocks that break after a limit has been reached.
I know Medieval Engineers and 7 Days to Die implemented something along these lines, though I would like to see if I can solve this (with some help) before ripping someone's implementation.
Of course links to more examples are appreciated.
Problem
In a 2D grid of constant size, there exists an anchor which all pixels/nodes must connect to. For example the bottom row will act as the "ground" and anchor all nodes. Finding unanchored nodes is easy, so assume all nodes are anchored.
Each node/pixel will have a mass, for simplification, this will be "1 block" of mass.
From there we need to find how much load each node is under (i.e. the amount of mass the node is supporting), and therefore how much "stress".
In this problem load and stress are the same.
My Implementation
For every node:

Split the mass of a block based on its valid connections i.e. paths that are not a dead end.
The fraction of mass on the neighbor node represents the fraction of weight of the source node it supports.
Repeatedly traverse splitting the mass until you get every path to an anchor node.

You should end up with a total number on each node representing how much "mass" it is supporting.
Example:

Mass distribution of one node
Each color represents the initial path from the source node/pixel for clarity.
The source mass is divided into three since the bottom path (in this example one block) cannot reach the anchor without going back on itself.
From this we can see the node with the most stress from the source node is D2, with the runner-up being C2. B3 is not affected by the source because it is not supporting it.
Of course there are limitations with this solution:

Bad time complexity
Scales poorly with #nodes
adding or removing one node is expensive

My solution involves finding every path from source to anchor for every block, which is bad.
I made a (very slow) example below, where the bottom of the grid is the anchor.
[Codepen Example]
Question:
How do I improve this algorithm or simplify the model in which stress is calculated so it can perform near real-time?


texts:
I have two data sets of a particular structure:
User 1:
  Salad1: Tuna, Mayo, Lettuce
  ...
  Breakfast1: Egg, Avocado, Toast

User 2:
  Salad1: Tuna, Mayo
  ...
  Breakfast1: Egg, Toast, Sausage

There are thousands of dishes, and the goal is to ensure that all the ingredients from User 1 dish are present in the corresponding recipe of User 2 data set.
We can't overwrite the recipe in User 2 data set, removing their additions - we only need to ensure that the ingredients from the corresponding User 1 dishes are present, and add them in if they are absent.
My solution:
Create a list of hashes for each recipe from each User:
Salad1|Tuna~Mayo~Lettuce
Breakfast1|Egg~Avocado~Toast

Perform a 'difference' operation on the two string arrays and end up with a list of those recipies that don't match. Break away the dish identifier from each resulting string, find the dish in the second data set and append the missing ingridient.
Benefits of my solution
As you can see, once we add the 'Lettuce' to the Salad1 recipe of User2, the relevant dish will stop coming up in the 'Difference of hashes' output, and the consequent synchronisations will take much less time.
Problems with my solution
Sadly, the Breakfast1 recipe of User2 will keep flagging up the difference even after we add the 'Toast' entry to it, because here the user has added 'Sausage' to the list.
This way, if User2 chooses to add a 'special ingridient' to each recipe we will end up evaluating every single dish in his database for having ingridients of the corresponding dish in User1 data set.
Essentially: my approach reduces the amount of individual dishes that I need to evaluate (iterate over ingridients to see if the ingridients from the User1 dataset are present), but I still need to evaluate those where extra ingridients were added.
The challenge
Is there any established algorithm that would take the two datasets above, and return only 'dishes' from the second data set that need 'ingridients' added to them?


texts: How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ?

texts:
How are these Context-Free Pumping Lemma Approaches differ?
Maybe this might help understand pumping lemma better

$(a^{i}b^{i}c^{j}d^{j} \mid i, j \geq 0$}

$(a^{i}b^{j}c^{i}d^{j} \mid i, j \geq 0$}

$(a^{i}b^{j}c^{j}d^{i} \mid i, j \geq 0$}

I understand we use contradiction with these conditions

$|vwx| \leq p$
$|vx| \geq 1$
for every $i \geq 0$, $uv^{i}wx^{i}y \in L$.


texts: Is a signal handler invocation an upcall?

texts: I am struggling with the definition of an upcall. Presumably, an upcall is a mechanism that allows the kernel to execute a function in userspace. By this definition, an invocation of a signal handler is an upcall because the handler runs in userspace and it is executed by the kernel. However, I noticed that upcalls are sometimes counterposed to signal handlers, without any reasonable explanations. So, is signal handler invocation an upcall, and if not, why?


texts:
I was learning Hidden Markov model, and encountered this theory about convergence of Markov model.

For example, consider a weather model, where on a first-day probability of weather being sunny was 0.9 while that of being rainy - 0.1. The transition distribution probabilities were - probability of sunny on current day given weather was sunny on previous day - i.e P(sun/sun) = 0.9. Similarly other probabilities were - P(sun/rain) = 0.3, P(rain/rain) = 0.7, and P(rain/sun) = 0.1.

Using bayes inference, we can find probability of distribution of weather on day Xt. It was mentioned that, after some point (i.e at state t = infinite), the probability distribution of weather on a day converges to p(sun) = 0.75 and p(rain) = 0.25.

Can someone explain this convergence mathematically? How does it converge to this distribution? It doesn't matter what's the distribution on day 1, the model always converges to the same values.


texts: computer science vs computer programming?

texts:
What's the difference between Computer Science and Computer Programming? I've spent nearly all my experience with compsci writing programs and what not, and I certainly like it, but I feel like there's a higher level I could pursue, like the ideas precede concrete programming.

I suppose my question is, what does it mean to be a computer scientist?

EDIT: I've done some thinking, and I have a somewhat more specific question-- what's the difference between the stuff on this stackexchange and the stuff on the cstheory stackexchange?


texts: Find the longest subsequence of two strings

texts: I want to know which is the best way to find the longest common subsequence of two strings


texts: What does the decision boundary of XOR problem look like?

texts: My textbook walks through an example of solving the XOR problem in machine learning using a two-dimensional RBF network. It does this by setting the centers for the two basis functions at [0,0] and [1,1]. Afterwards, it challenges us and asks to imagine what the decision boundary for an RBF would look like if the two centers were instead at a sample of each class (class 0 could be [0,0] and class 1 could be [1 0]). Since there is only two classes, wouldn't this result in essentially a straight line, or would it look like something else? Is there any reason why we would want to do this?


texts: Are there more Turing-unrecognizable languages than recognizable?

texts: Say you generated a language by looking at the output of a lexicographic enumerator and flipping a coin for each string, adding it to the language on heads. What would be the chance of this language being Turing-recognizable?


texts: Unrolling multi-variable mu (μ) expressions in type theory

texts:
Unrolling an iso-recursive μ-type expression such as, say, one isomorphic to natural numbers:

μα.1+α

using

unroll : μα.T → T[μα.T / α]

by three steps, for example, gives:

μα.1+α
μα.1+(1+α)
μα.1+(1+(1+α))
...

If I instead have a polymorphic list, such as:

λα.μβ.1+αβ

is there a necessary relative order to the expansion of λ and μ? Say I instantiate α to T:

μβ.1+Tβ
μβ.1+T(1+Tβ)
μβ.1+T(1+T(1+Tβ))
...

Can we instead unroll μ before applying the λ at an arbitrary step?

λα.μβ.1+αβ
λα.μβ.1+α(1+αβ)
λα.μβ.1+α(1+α(1+αβ))
...

It looks in this case like we could. What I'd really like to know though is how to expand an expression having more than one μ variable; say:

μα.μβ.1+αβ

I could start with a few unrolls with β:

μα.μβ.1+αβ
μα.μβ.1+α(1+αβ)
μα.μβ.1+α(1+α(1+αβ))
...

...starting with α instead looks more complicated:

μα.μβ.1+αβ
μα.μβ.1+(μβ.1+αβ)β
μα.μβ.1+(μβ.1+(μβ.1+αβ)β)β
...

...or maybe α-β alternation could work, say starting with β:

μα.μβ.1+αβ
μα.μβ.1+α(1+αβ)
μα.μβ.1+(μβ.1+αβ)(1+(μβ.1+αβ)β)
...

...or starting with α:

μα.μβ.1+αβ
μα.μβ.1+(μβ.1+αβ)β
μα.μβ.1+(μ(1+αβ).1+α(1+αβ))(1+αβ)
...

Where does it all end? I can't imagine they end up equivalent. Is there a standard approach?


texts:
I'm playing around with some historical stock data and attempting to optimize a portfolio.

I essentially have created a function that generates certain statistics about a portfolio (right now it's composed of a list of equities with corresponding weights). The portfolio is constant and tracked over a historical time range to arrive at some statistics regarding its performance (sharpe ratio, sortini, etc).

Given that the function that generates the Sharpe ratio isn't really smooth, I've decided to approximate the gradient in order to maximize the Sharpe ratio given input weights subject to the constraint that they add up to 1.

What would be the best way to go about doing this? Is this even feasible for this kind of data?


texts:
I got stuck on this question while studying for final exam.

I thought about reducing L' to L to prove that L' is recognizable since L is recognizable. I am not 100% sure if that is correct.


texts: Algorithm to Minimize a Regular Expression

texts:
I am referring to regular expressions with alphabet {$0$, $1$}. We want to minimize them so that they have the least possible number of symbols and operators. Is there an algorithm to do this?

For instance, what is done on this page in the accepted answer:

https://stackoverflow.com/questions/35112630/minimize-specific-regular-expression

Is there a formal algorithm to explain the process that the answer went through?


texts: Will we be able to « see » COVID (or any other viruses) in our environment in the future?

texts: Given that cameras, computer vision and AI are constantly evolving with greater zoom, macro, processing power... is it possible that some day cameras would be able to « scan » a room and detect COVID (or any other viruses) somewhere, such as on the door knob? In other words, could evolved cameras and AI be able to see and track viruses in our environment?


texts: Distributed algorithms for finding n largest elements

texts:
It's easy to come up with a simple distributed algorithms for finding the maximum element in a set (totally ordered): Divide and conquer.

There are a few publications that present algorithms for distributed maximum-finding. The challenge is to pass the  fewest messages between nodes.

Does anyone know of algorithms that tackle the same problem for the distributed "n-largest-finding" problem?

A naive solution is a repeated application of a distributed maximum-finding algorithm by successively slicing off the maximums. Another naive solution is to use a distributed sort. These two are probably not even that bad in the extreme cases (very small n, very large n). But how about finding the 10% largest elements (the top decile)?

For reference: There's a question on SO, CUDA: Finding the N largest values of a sparse array, which leads to just using a sort.


texts: How to count all contiguous subsequences with positive sum?

texts:
I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$.
I need to count how many contiguous subsequences have positive sum.

This pseudocode demonstrates exactly the behavior I want, but is too slow for large $n$:

c = 0
for i = 1 to n do
    for i = j to n do
       if sum(u[i:j]) > 0 then
           c = c + 1
return c

Partial sums can be used to optimize it, but it will still be $O(n^2)$.

Here are some examples if they help:

[-1, 1, -1, -1, -1] $\rightarrow$ 1

[1, -1, 1, 1, -1, 1] $\rightarrow$ 14

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1] $\rightarrow$ 55

Does there exist linear or $n \log n$ solution?


texts: How to find the reverse of a binary string with simple binary operators?

texts:
I was wondering is it possible to create a simple circuit that detects if an input (a binary string) is a palindrome?
So my approach is to feed the input to a circuit that reverses the input, ie if the input is 0111010, I need the output to be 0101110. Is this possible to achieve with only, and/or/xor/not and these simple operators in a generic way (on paper, not looking to implement a circuit with a predefined number of bits)?
Once I have this reversed output, I can use it with an "and" gate to compare to the original input and see if they match, but I'm stuck at the first part.
I appreciate your suggestions
Thanks in advance


texts: $\#P$ closure under binomial coefficients?

texts:
It is quite straightforward to understand $\#P$ closure under addition and multiplication since there are canonical $NTM$ constructions.

Is there illustrative non-trivial example to understand $NTM$ construction for closure under binomial coefficients?


texts: How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

texts:
When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of edges of i or on the list of edges of j. Other times, it's important to have an (i, j) on i and a (j, i) on j.

I was wondering how do you call graph representations of one type and graph representations of the other type? Without concrete names to give to each one of them, code or even conversations about certain algorithms get confusing really fast.


texts: Reduction variation for the q-coloring problem

texts:
I'm trying to prove that $q$-COL $\leq^P_m q$-COL$_{2q-1}$, where $q$-COL$_{2q-1}$ is the restriction of the q-coloring problem to graphs of maximum degree $2q-1$. Now, it seems fairly obvious "if you can color a graph of any maximum degree with $q$ colours, then you can colour a graph of maximum degree $2q-1$ with $q$ colours", the second is a subset of the first. Am I correct this far?

Assuming the previous assumption is correct, I need to find a function or mapping from $G$ to $G'$. It would seem that I need to pick a vertex $v \in G$, and $v' \in G'$ and colour $v'$ the same as $v$, then follow the pattern of $v$, for up to $2q-1$ connections, and then leave the rest alone.

In my head this works, but I'm fully new in reductions and would appreciate your input about this. I'd also appreciate any pointers on how to formalise it. Thank you!


texts: Proof via induction for small-step semantics

texts:
I'm doing a course in Computer Programming Languages and I'm trying to prove the following (roughly following Pierce's Types and Programming Languages book):

if $t \rightarrow^* t'$ then $if\; t\; then \; t2 \; else \; t3 \rightarrow^* if\; t'\; then \; t2 \; else \; t3$

I'm a little confused about where to start; as far as I know, I'm supposed to define a base case, then prove it via induction.

I've started my proof by assuming these base cases:

$P(\frac{}{true \rightarrow^* true})$ and
$P(\frac{}{false \rightarrow^* false})$.

I'm stuck at this point, and I don't really how know to proceed.

edit: I've added the syntax in an effort to clear things up.


texts: Studying Skiena. War Story: What’s Past is Prolog

texts:
I am reading The Algorithm Design Manual, 2nd Edition.
The book gives an example task and then explains how to solve it step by step.
(The task and solution is detailed here)

But I don't follow one step from the solution. That step doesn't contain enough details for me so I don't understand it. I'm asking if someone can explain it.

Below I rewrote the task in a shorter form than in the book:

Given n ordered strings (lets call them rules) of m characters. The strings are indexed starting from 1 (not 0)

The goal is to construct the trie with the minimum possible number of edges. The leaves of the resulting trie (each leaf represents a string) have to be in the same exact order as the given collection of strings.

We are free to pick an arbitrary character position on each step of constructing the trie (e. g., we are free to start constructing the trie from character position 2 as opposed to starting from 1). Thanks to this ability we can minimize the built trie. Lets call picking a character - probing.

Example:

From the four rules below it's possible to build different tries depending on the order of picking characters from the strings.

S1: (a,a,a)
S2: (b,a,a)
S3: (c,b,b)
S4: (d,b,b)

The book says that

  Probing at the p-th position, 1 <= p <= m, partitioned the rules into runs R1,...,Rr, where each rule in a given run Rx = Si,...,Sj had the same character value of Si[p].

  Since the rules were ordered, each node in the subtree must represent the root of a run of consecutive rules, so there were only ${{n}\choose{2}}$ possible nodes to choose from for this tree...

  ...

  The rules in each run must be consecutive, so there are only ${{n}\choose{2}}$ possible runs to worry about.

My question: How does the fact the rules are consecutive lead to the inference that there are ${{n}\choose{2}}$ possible nodes/runs after probing at the p-th position?


texts: Sampling numbers from a weighted set that sum to constant value

texts:
So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to weights $W$ such that the sampled numbers sum to a given constant positive integer $k$.

The naive way to do it, as I understand it, is to find out all combinations of numbers from $S$ that sum to $k$ and add their weights and choose one of the combinations according to the sum of weights. But doing that is $O(|S|^k)$, which is unacceptably large.

What I'm doing right now is do a weighted shuffle of $S$ according to weights $W$, and picking number in the obtained order until the requirement is fulfilled. If, for example, the order obtained is $3, 2, 3, 2, 1$ and $k = 4$, then I'll pick $3$, ignore $2$ (as picking it will exceed $k = 4$) and pick $1$. This approach turns out to be $O(n\log\ n)$.

Does anyone have a better idea for doing this sampling in a way that is faster than exponential but more robust than what I'm currently doing now?


texts: Iterative version for towers of Hanoi recursive algorithm

texts:
How could I describe an iterative version of the following algorithm?
I was thinking something along the lines of:

move $k-2$ smallest disks right on the stack
check if stacks are empty
move the largest available disk to available stack

But when I trace it I'm getting caught up when I have more than one stack available for the largest available disk to move to.
generalTH(n_disks,k_stacks)
  if n<k:
    ### in 2n-1 moves reassemble ###
    return
  m = n-2
  generalTH(n-m,k)
  generalTH(m,k-1)
  generalTH(n-m,k)


texts: Why do floating point additions sometimes produce equal results?

texts:
I have tried two sentences on my computer :

2 + 10^(-18) == 2
2^(-55) + 2^(-57) == 2^(-55)

My computer gives TRUE and FALSE respectively. Why does the computer give two different results? Shouldn't the computer give the same output?


texts:
How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3)

I was told it takes:

$$2(n-2) + 1 =  2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

  The worst case occurs if the first list empties when there is
  exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers
  requires 2 comparisons before going into the big list. After this, we only need 1 more
  comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the $2(n-2)$ came from... What does:

  The worst case occurs if the first list empties when there is
  exactly 1 item in each of the other two.

even mean?

When it says "prior to this", its not clear to me what exactly happened before hand...

What does the "big list" referring to? How did we even get a "big list"?

Btw, I am not looking for an asymptotic answer.

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left[ (c-1)(n-(c-1)) + \sum^{c-2}_{i=1} i\right]$$

The extra term for merging is not entirely clear to me.


texts: Is GAP NP-hard with at most two balls per bins?

texts:
The generalized assignment problem (GAP) [1] is given by:

Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and for each item $i$ and bin $j$, we are given a size $s(i, j)$ and a profit $p(i, j)$.
Objective: Find a subset $U ⊆ S$ that has a feasible packing in $B$ and maximizes the profit of the packing.

In [1], the authors proved that GAP is NP-hard even when:

$p(i,j) = 1$ for all items $i$ and bins $j$.
$s(i,j)=1$ or $s(i,j)=1+δ$ for all items $i$ and bins $j$.
$c(j)=3$ for all bins $j$.

Analyzing this instance, I can see that GAP is NP-hard when $p(i,j)=1$ for all items $i$ and bins $j$ and each bin can pack at most three balls. This observation raises the following question for me.

My question: Is GAP NP-hard when $p(i,j) = 1$ for all items $i$ and bins $j$ and each bin can pack at most two balls?

[1] A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem


texts:
Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,

person 1 has item A, C, D, and wants item F

person 2 has item B, C, and wants E

person 3 has item E, and wants G
...

You get the idea. So it's basically a supply/demand matching problem, and if we represent this as a person-item matrix, it's gonna be a very sparse one.
So my question would be:

How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?
How do I find the shortest series (or path) that involves more than 2 people (so one-to-one exchange I think I've figured how by using some matrix operations)?
What would be the complexity for finding longest/shortest paths?

Any advice would be appreciated.


texts: i have researched it on wikipedia and it produces me an unusual example and stories about Turing,so what i understand is if an program run in loop,an electronic device in cpu or in computer structure would stop that program,or an code will be processed by the input to decide if the program will be executed or will be halted after that.So what is the halting problem actually?


texts: How to convert process / cpu core based upon MIPS?

texts:
I want to know how can i find number of cpu cores/processor supported given i have the MIPS value?

For e.g I want to know the number of matching cores/processor to process speed of 18 triilion instructions / sec.


texts:
I have encountered a problem in class, tried solving it and faced a problem, I will include my ideas, and the problems i faced.

Assume F is a PRF,

1.denote  $P_k(x) = F_k(x) ⊕ F_k(1^n)$ for any $n ∈ N, k ∈ \{0,1\}^n$ and $x ∈ \{0,1\}^n$. Is P necessarily a pseudorandom function?

2.denote $P_k(x) = F_k(x) ⊕ 1^n$ for any $n ∈ N, k ∈ \{0,1\}^n$ and $x ∈ \{0,1\}^n$. Is P necessarily a pseudorandom function?

My solution:

I noticed that for every $k$ it happens that $P_K(1^n)=F_k(1^n) ⊕ F_k(1^n)=0^n$ therefore i thought that $P_k$ isn't a PRF and i constructed $D^o$  distinguisher, thus leaves me with $|P(D^{P_k(.)}(1^n)=1)-P(D^{f(.)}(1^n)=1)|=1-v(n)$ where v(n) is negligible.

The question here is : do I need to show $v(.)$ and which function it is?

I have assumed towards contradiction that $P_x$ is not a PRF, thus a distinguisher $D^o$ (with an oracle)  can distinguish that it is not random in PPT time ( please excuse my english).
such that $|P(D^{P_k(.)}(1^n)=1)-P(D^{f(.)}(1^n)=1)|>\frac1{P(n)}$ where $p(n)$ is a polynom.
now that i have this assumption and understanding i created a new distinguisher that encloses $D$ and use it in order to get my contradiction- that F isn't a PRF if $P_x$ isn't.

I have a bit of a problem with showing how the enclosing distinguisher will lead to a contradiction.

I Hope that i was correct with my method, and if it is indeed a solution to these two problems.


texts:
It is claimed in my textbook that

  In a 32-bit system, The instruction LDR r4,[r6] lets you address a
  logical space of 4GB.

I know where the 4GB comes from, It is simply 2^32 / (1024 x 1024 x 1024).

However, My question is why is it bytes and not bits ?

Why when we raise 2^32, we should talk about bits and not bytes. And so 4GB doesn't make sense to me .

For me It would make sense if it is (2^32/8)/ (1024 x 1024 x 1024)


texts: Why is this execution happens-before consistent?

texts:
In section 17.4.5 "Happens-before Order" of Java Language Specification, a trace is examined for the notion of happens-before consistency.

The trace is shown in the figure in which $A$ and $B$ are shared variables with initially $A = B = 0$.

An execution order of the trace is as follows.

In this execution, the reads see writes that occur later in the execution order. The document says that it is happens-before consistent. I am quite confused about this. In my opinion, this execution order does not even satisfy program order. Why is it happens-before consistent?


texts: The name for this genetic algorithm variant

texts:
What is the name for this variant of genetic algorithm. I'm sure I have read about this in Wikipedia, but now I could not find it:

There in no thing as sequential population. The phenotypes lives and dies just like people. The death comes after random period of time. During life phenotypes can have children. The better phenotype is (fitness function) the bigger is chance to have (more) children. The better phenotype is the better can be it's candidate form wife or husband. Yes, phenotypes have sex (man or woman).


texts: Can the program determine the frequency of the CPU or is it impossible?

texts: In order to understand the question, imagine a simple situation. Alice tells Bob that her CPU's frequency is X Hz. Bob does not take her word for it. Bob can not meet with Alice and check what frequency her processor really has. Can Bob send her a soft program that accurately determines the frequency of Alice's CPU? Is such a program possible or not in principle?


texts:
Okay, so I have been doing competitive programming for the past few days in C++. And day before yesterday, I stumbled upon this concept of linked list.

Now, what I do while implementing most problems pertaining to linked list is that I store all the values of the linked list nodes in a vector, and do operations on them which has been asked as per the question, then refill the nodes with the newly updated values of the vector. Now, most of the questions can be done by me really easily, as I am pretty comfortable with using vectors now. I just wanted to ask this community if this was a bad approach towards using linked list, and should I stop using it altogether.

I will give an example to sort a linked list in $O(N\log N)$ time, which I used. Following is a function that sorts a linked list-

ListNode* Solution::sortList(ListNode* A) {
    vector<int> vect;
    ListNode* temp=A;
    while(A!=NULL)
    {
        vect.push_back(A->val);
        A=A->next;
    }
    A=temp;
    sort(vect.begin(), vect.end());
    for(int i=0; i<vect.size(); i++)
    {
        A->val=vect[i];
        A=A->next;
    }
    return temp;
}


texts: Merits and demerits of convolutional and linear block codes

texts:
Continuing on from my previous post...

Both convolution and linear block codes can be used for error correction. The main benefits I gathered from using convolutional codes is that, it's easy to implement and does better (than linear codes) in cases where you have higher error probability rates and noisy channels. Information bits are spread along the sequence. Lastly, these codes have memory.

However, linear block codes, especially the newer ones such as polar code, can actually achieve the channel capacity. And, in block codes, information bits are followed by parity bits and code information in blocks. Lastly, they are memory less.

Given this, what other merits and demerits are there to using convolutional or linear block codes?

I ask this because I have a system which has low processing power and high error rate, caused by mostly burst errors.  What would be the better coding to use and why? It is also to be noted that this error rate is very erratic. A number of factors affect the error rate: time the RF modules are turned on, noise, temperature, obstacles, etc. I tried a Reed-Solomon code, but it still doesn't do the job.


texts: Is the language of all non-palindromes context-free?

texts:
Is the language $L = \{ w \mid w \in (a,b)^* \wedge w \text{ is not a palindrome} \}$, context-free? I think this grammar:

$
S \rightarrow aSa \mid bSb \mid aAb \mid bAa\\
A \rightarrow aAa \mid bAb \mid aAb \mid bAa \mid a \mid b \mid aa \mid ab \mid ba \mid bb
$

generates it, but I'm unable to conclude anything using the pumping lemma for context free languages.


texts:
I am trying to understand how does Pollard's rho algorithm actually work, but I just can not wrap my head around it. I already read its section in the CLRS book and also on internet but still can not understand its structure or analysis.
This is a java implementation of the pseudocode from the CLRS book along with euclid gcd algorithm:

public static void pollardRho(int n) {
    Random rand = new Random();
    int i = 1;
    int x0 = rand.nextInt(n);
    int y = x0;
    int k = 2;
    while (true) {
        i++;
        int x = (x0 * x0 - 1) % n;
        int d = gcd(y - x, n);
        if (d != 1 && d != n) {
            System.out.println(d);
        }
        if (i == k) {
            y = x;
            k *= 2;
        }
        x0 = x;
    }
}

public static int gcd(int a, int b) {
    // fixes the issue with java modulo operator % returning negative
    // results based on the fact that gcd(a, b) = gcd(|a|, |b|)
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b != 0) {
        int tmp = b;
        b = (a % b);
        a = tmp;
    }
    return a;
}

Why does it choose $x = (x_0^2 - 1) \mod n$?
What does $y$ actually represent and why is it chosen to be equal to $\{x_1,x_2,x_4,x_8,x_{16},...\}$?
Why does it compute $\text{GCD}(y-x,n)$ and how does $d$ turns out to be a factor of $n$?
And why is the expected running time is $O(n^{1/4})$ arithmetic operations and $O(2^{\beta/4} \beta^2)$ bit operations assuming that $n$ is $\beta$ bits long?

I understand that if there exists a non-trivial square-root of $x^2 \equiv 1 \pmod{n}$ then $n$ is a composite and $x$ is a factor, but $y - x$ is not a square root of $n$ is it?


texts: Multiple Knapsack Problem with Set of Admissible Balls

texts:
We have $m$ bins and $n$ balls.

Each bin $i=1,2,\ldots,m$ can contain at most two balls (not any two balls but two balls from some specific set), see 3.
Each ball $j=1,2,\ldots,n$ can be put into bin $i=1,2,\ldots,m$.
For each bin $i=1,2,\ldots,m$, there is a collection of sets $S_i=\{X_1,X_2,\ldots,X_{k_i}\}$ for given $k_i$ ($k_i\geq0$ and $k_i\leq\binom{n}{2}$). Each $X_j\in S_i$ is a 2-cardinality set and it represents the set of two balls that can be put into bin $i$. We can only choose at most one set from $S_i$.

For example, for $m=2$ and $n=3$. Say we have $k_1=0$ and $k_2=2$ and $S_1=\emptyset$. $S_2=\{\{1,2\},\{2,3\}\}$. This means that:

Ball $1$, $2$ or $3$ can be each put into bin $1$ or bin $2$. This is always true (for all instances of the problem).
In bin $1$, we cannot put any set of two balls.
In bin $2$, we can put balls $1$ and $2$ or balls $2$ and $3$.

We want to assign the maximum number of balls into the bins. Is this easy or hard?

Since, we have the assumption that $|X_j|=2$, I was thinking that maybe we can solve it in polynomial-time. I am trying to prove that it is easy by reducing it to maximum flow.

A problem similar to this one but more general was posted here Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?.


texts: Regular Languages in $ \mathsf{\text{}NC^1}$

texts:
Theorem : To prove $ \mathsf{\text{} Regular} \subseteq \mathsf{\text{}NC^1}$.

To prove the theorem stated above we need some theorems and definitions given below :

Barrington Theorem : A branching program of constant width and polynomial size can be easily converted (via divide-and-conquer) to a circuit in $\mathsf{\text{}NC^1}$.

Proof Idea of Barrington Theorem is like small depth boolean circuit implies small group program and small group program implies small branching program.

Monoid : In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

I google and find out a research paper but not able to understand much (some of the things that I have understood I have written above). A high level proof idea or an resource to prove the theorem stated above will be helpful.