texts: Efficient compression of simple binary data

texts:
I have a file containing ordered binary numbers from $0$ to $2^n - 1$:

0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

7z did not compress this file very efficiently (for n = 20, 22 MB were compressed to 300 kB).

Are there algorithms that can recognize very simple structure of data and compress file to several bytes? Also I want to know what area of CS or information theory studies such smart algorithms. "AI" would be too broad, please suggest more concrete keywords.
Notion of symmetry should play fundamental role in data compression, but search queries "symmetry in data compression" and "group theory in data compression" surprisingly return almost nothing relevant.


texts:
I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.

Note that these topics are not easily digested without a background in (mathematical) logics. If you have problems with basic terms, please read up on those, for instance Logics in Computer Science by M. Huth and M. Ryan (in particular chapters one, two and four) or An Introduction to Mathematical Logic and Type Theory by P. Andrews.
For a short introduction into higher order logic (HOL) see here.

I looked at Coq and read the first chapter of the intoduction to Isabelle amongst others; Types of Automated Theorem Provers

I have known Prolog for a few decades and am now learning F#, so ML, O'Caml and LISP are a bonus. Haskell is a different beast.

I have the following books

"Handbook of Automated Reasoning" edited by Alan Robinson and Andrei Vornkov

"Handbook of Practical Logic and Automated Reasoning" by John Harrison

"Term Rewriting and All That" by Franz Baader and Tobias Nipkow

What are the differences between Coq and Isabelle?
Should I learn either Isabelle or Coq, or both?
Is there an advantage to learning either Isabelle or Coq first?

Find the series' next question here.


texts: Resource bounded reductions for RE-Complete problems

texts:
Given that the halting problem is RE-Complete, we can reduce any problem in RE to an instance of the halting problem. Are there are any results on the time-bounds for this reduction? Can we do this reduction in polynomial time in general? Exponential time? Polynomial space?

On the surface, defining an oracle machine like $P^{H}$, where $H$ is a black-box that solves the halting problem in $O(1)$ time seems to provide a tremendous amount of power over $P$ alone. However, if the reduction from a problem in $P$ (primes, 2-SAT, etc) to the halting problem takes exponential time (or worse!) then $P^{H}$ isn't that much more powerful than $P$ in terms of what it can solve quickly.


texts: Why is the complexity of this nested for loop not $O(n^2)$?

texts:
I have the following pseudo-code:

mystery(n):
if n <= 50 :
    for i = 1 ... n :
        for j = 1 ... n :
            print i*j
else :
    mystery(n-1)

For the following nested for loop:

for i = 1 ... n :
        for j = 1 ... n :

For every i in n, j iterates through n as many as i times. So, why is it that the complexity is not $O(n^2)$?


texts: What is the result of a reduction operation called?

texts:
Is there a commonly used term for the result of a reduction operation?

"reductant" does not quite sound right...


texts: Is there any published paper about automated planning software used in the ESA Rosetta mission?

texts:
The Rosetta spacecraft has reached a comet in August 2014 and sent a
lander on its surface. It was one of the greatest science news of the year.

Automated Planning and Scheduling techniques are really important in the operations of these kinds of missions. At the last ICAPS there was even an invited talk by one of the staff members involved in the automated planning technologies used in the spacecraft.

Is there any published paper on the planning technologies used in the spacecraft? I've only found this one, but it does not appear to have been published in conferences or journals. Has it or something similar been published somewhere?


texts:
A question on the interesting result in http://arxiv.org/pdf/1110.6126v1.pdf

It is shown $\Pi_2^P \not\subset P^{NP}$. But http://en.wikipedia.org/wiki/Polynomial_hierarchy says $\Pi_2^P = CoNP^{NP}$.

Does this mean an oracle in NP under which $P$ is not $CoNP$ has been shown?

Could someone elaborate?


texts: deterministic finite automaton for "does contain substring $w$" is of linear size

texts:
A (non-deterministic) finite state automaton for "all strings that contain substring $w$" is very simple. Just make the path for $w$ and add looped transitions for all letters at the first initial state and the last final state.

When asked to make a deterministic automaton in general we might expect that the automaton can be of exponential size (see the warning of Yuval in the case where $w=101$: Write a regex to match string that does NOT contain a certain pattern).

However, Knuth-Morris-Pratt tells us that a pattern match automaton for $w$ is of linear size, and can be constructed in linear time. That means that the deterministic automaton for "contains substring $w$" is of linear size too (failure links can be replaced by transitions, on for each mismatching letter).
Luke has used KMP to provide an automaton for the example "not ABCDABD" in his answer Automaton for substring matching.

My question is the following: will the standard determinization of a "substring $w$" automaton always lead to a linear sized automaton? Here I mean the practical version of the construction, where unreachable states are not constructed (so not the full $2^Q$ subset construction). Is the answer direct from the construction, or do we need KMP?

A little observation. In the construction there might be many states that contain the original final state. As they all will accept and also all transitions for ever will lead to accepting states (once we have seen $w$) these states can be grouped into one single state. I do not know whether that is a necessary trick to avoid exponential explosion, see https://cs.stackexchange.com/a/11842/4287


texts: How to find an array of probabilities that give equal products

texts:
I'm trying to figure out if there is an algorithm which can solve the following:
Given an array of randomly generated values, for example: $$[54.6, 1.96, 5.0, 31.31]$$
Find an array of equal length, in this example $[x_1, x_2, x_3, x_4]$ such that:
$$54.6 \cdot x_1=1.96\cdot x_2=5.0\cdot x_3= 31.31\cdot x_4$$
and
$$x_1 + x_2 + x_3 + x_4 = 1.0$$
Any suggestions for an algorithm to solve this?


texts: How to restore diagonal-symmetric matrix that has been shuffled?

texts:
I have a square matrix M, which originally looked like this:

133 199 101 121
142 133 199 101
156 142 133 199
108 156 142 133
 (so symmetric around the diagonal). Not only that, but each diagonal is constant, so M'[i, j] = M'[p, q] if i + j == p + q , however it has been shuffled both row-wise and column wise. The only solution I could think of was brute forcing all permutations of the rows and columns which is O(n!*n!), which is obviously suboptimal. I also thought of the fact that in this specific matrix, the value counts are 1 2 3 4 3 2 1, but the original matrix is way bigger and there are many duplicate values.

The last idea I have is some sort of greedy reshufling that would work like so:

for each column, find the column that has the most similar values (albeit shuffled).
place them together
repeat until convergence
repeat for rows.
repeat 1-4, but this time take into account the ordering too.

That idea seems unsatisfying though.

The full data is not too huge, 5000x5000, and I only need to restore it once, so I'm not nessecarily looking for the most efficient way, just a robust and easy to implement solution.


texts: Machine Learning method maps from $\mathbb{R}$ to $\mathbb{R}^2$

texts:
I have worked with image classification and image segmentation etc.
While working with images we are either mapping from $\mathbb{R}^2\to\mathbb{R}$ or $\mathbb{R}^2\to\mathbb{R}^2$. Are there any machine leaning methods that can map from $\mathbb{R}\to\mathbb{R}^2$. For example, I have a feature vector of $3$-$5$ elements and I want to map it to $32\times32$ (approximately).
Is is possible? If it is, by which methods?


texts: Finding maximum information gain subinterval of an array containing points from 2 classes

texts:
Suppose we have an $N \times 2$ array $A$ where the two entries $A(k,1)$ and $A(k,2)$ give the number of occurrences of each of two classes at position $k$. Given a sub-interval $I$ of indices between $1$ and $N$, the information gain associated with the interval is a constant plus

$$p_I(p_{in} \log p_{in} + (1 - p_{in})\log(1 - p_{in})) + (1 - p_I)(p_{out} \log p_{out} + (1 - p_{out})\log(1 - p_{out}))$$

where

$$p_I = (\sum_{k \in I} A(k,1) + A(k,2)) / (\sum_{k} A(k,1) + A(k,2))$$

i.e. $p_I$ is the fraction of points contained in the interval $I$, and

$$p_{in} = \sum_{k \in I} A(k,1) / (\sum_{k \in I} (A(k,1) + A(k,2)))$$

i.e. $p_{in}$ is the fraction of class 1 when restricting to interval $I$, and similarly $p_{out}$ is the fraction of class 1 when restricting to outside interval $I$. In the formulas it is understood that $0 \log 0 = 0$.

It is trivial to find the subinterval that maximizes information gain in $O(N^2)$ time just by brute force. However, finding the maximum sum subinterval can be done in $O(N)$ time using Kadane's dynamic programming algorithm. Can we similarly get some sort of speed up for information gain? I tried a recursion where you split the range in half and optimize the left half, then optimize the right half, and then find the optimal solution in the left half that reaches the middle of the array, and similarly find the optimal solution in the right half that reaches the middle of the array, and concatenate those two solutions, so that overall there are 3 candidates for the global optimal solution (either just in left half, or just in right half, or crossing the middle of the array). However experiments have shown that this fails when the global optimal solution crosses the middle of the array. Maybe some sort of non-linear transformation can make it work? Or another optimization strategy?


texts: Reaching local optimality in simulated annealing

texts:
I am currently reading about local search techniques. I understand that local search algorithms tend to get stuck in local optima and therefore usually do not find globally optimal solutions. Thus, there are more sophisticated approaches that enable us to leave local optima and may improve the overall solution quality (e.g. simulated annealing or genetic algorithms).

What I'm thinking about is the following: As far as I understand it, the simplest approaches like hill-climbing (best-fit) are at least guaranteed to find locally optimal solutions with regard to the specified neighborhood. Don't we lose this property when using simulated annealing or genetic algorithms? Even for the first-fit version of hill-climbing it is no longer guaranteed to find a local optimum while getting the advantage of a possible runtime reduction.

Is it a tradeoff between an increased possibility to reach globally optimal solutions (or a reduced runtime in the first-fit hill-climbing case) and a higher risk of not even getting a locally optimal solution?


texts: strange choice of constant when showing $an + b = O(n^2)$ ("Introduction to Algorithms" book)

texts:
In the third edition of Introduction to Algorithms, the authors state:

  ... when $a$ > 0, any linear function $an+b$ is $O(n^2)$, which is
  easily verified by taking $c = a + |b|$ and $n_0 = max(1, -b/a).$

[In the above, $c$ and $n_0$ come from the standard definition of big-oh:

$f(n)$ is in $O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le cg(n)$ for all $n \ge n_0$.]

I have no trouble accepting that $an+b \in O(n^2)$, but I'm questioning the motivation/origin of the weird choice of $n_0$.

If we assume that $ n \ge 1$, then, since $a > 0$, we have $an^2 \ge an$ and since $n^2 \ge 1$ we have $|b|n^2 \ge |b| \ge b$, implying that $(a+|b|)n^2 \ge an+b$. So it seems that $n_0$ could simply have been taken as $1$. Or am I messing up somewhere?


texts: If P = NP, how do I prove I can find the maximum clique in polynomial time?

texts:
I want to prove that if P = NP, then there is a polynomial time algorithm for finding the largest clique in an undirected graph.

I understand how to use a verifier to find this but my issue is since P = NP it doesn't want me to use a verifier. I'm not sure how to approach this.


texts: How to quickly find a few bisimulations on a given labelled digraph?

texts:
We are given a labelled directed graph, where both vertices (or states) and edges (or transitions) have labels. Informally, two states are bisimilar when they have the same label and they can simulate each other's transitions. On the states the two states evolve to, the same again is true.

More formally, a binary relation $R \subseteq S \times S$ is a simulation iff $\forall (p,q) \in R$

$p$ and $q$ have the same label, and
if $p \overset{a}{\longrightarrow} p'$ then $\exists q', q \overset{a}{\longrightarrow} q'$ and $(p',q') \in R$.

A relation $R$ is a bisimulation iff $R$ and $R^{-1}$ are simulations. The largest bisimulation on the given system is called the bisimilarity relation.

There are algorithms for finding the bisimilarity relation, that run in $O(m \log n)$ time and $O(m+n)$ space, where $n$ is the number of states and $m$ the number of transitions. An example is the Paige-Tarjan RCP algorithm from 1987.

However, consider a simpler problem. Instead of finding all the bisimulations, I just want to find a few of them. Can it be done faster than in loglinear time? If so, how? For example, let's say one is given two states $p,q \in S$ such that they have the same label and they can make the same transitions. What I find problematic is to check that the states they lead to are once again bisimulations. In other words, one could also ask if there is a quick way to decide if two given states are a bisimulation.


texts: Characterization of computationally universal functions

texts:
Is it correct to state that $u$ is a universal function if and only if
$$
\forall f : \text{RE} \quad
\exists g : \text{R} \quad
\exists h : \text{R} \quad
f = h \circ u \circ g
$$
where RE is the set of recursively enumerable functions and R is the set of recursive functions? (Should R be replaced with something like PR?) If so, does anyone know of a reference that states universality in this generic form?
Defining "universal function"
I suppose we could define "universal function" itself as follows: Let $\phi : \mathbb{N} \rightarrow \mathbb{N} \rightharpoonup \mathbb{N}$ be an enumeration of all partial computable functions $\mathbb{N} \rightharpoonup \mathbb{N}$. Let $\psi : \mathbb{N} \rightharpoonup \mathbb{N}$ where
$$
\psi(n) = \phi(\pi_1(n))(\pi_2(n))
$$
where $\pi_1, \pi_2 : \mathbb{N} \rightarrow \mathbb{N}$ are the first and second Cantor unpairing functions. Then $u : A \rightarrow B$ is universal if and only if
$$
\exists g : R \cap (\mathbb{N} \rightarrow A) \quad
\exists h : R \cap (B \rightarrow \mathbb{N}) \quad
\psi = h \circ u \circ g
$$
This resembles a definition of computable functions given in page 24 of Cutland's Computability: An Introduction to Recursive Function Theory.
Addendum
In a sense, I'm looking for a definition of universality that is more "axiomatic", "abstract", and "generic" than the definition that is usually given, which pertains to partial functions from naturals to naturals specifically. My candidate definition requires only that RE be defined/understood over the relevant domain. (From that, co-RE and therefore R fall out automatically.)
To give an example of what I mean from a different area of mathematics, the reals can be constructed as Cauchy sequences or Dedekind cuts of rationals. However, they can also be directly axiomatized as the (unique) Dedekind-complete ordered field.
I can try to bootstrap the definition of universality from the naturals-to-naturals case, but doing so requires more artificial machinery and is less elegant. I'm wondering whether there's a more "direct" approach. That's why I'm asking for references that discuss how universality is defined in more general domains (than naturals-to-naturals) directly.
Notions like the effective topos and realizability might be relevant.


texts: Time complexity of linear programming with small number of variables

texts:
I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm for exact solving of the linear program, where the dependency on $m$ is as small as possible. More formally:

The time complexity of solving the linear program is known to be $O(n^a m^b)$ for some constants $a$ and $b$.
What is the best known pair $a, b$ where the value of $b$ is the minimum possible?


texts:
I have some questions about energy emitted when one bit of information is processed.

Landauer's principle states the minimum possible amount of energy required to erase one bit of information is k T ln2
Considering this,

How this formula is found? In terms of energy and memory unit, what is the processing cost per bit for normal and reverse operations respectively?


texts: How to find a possibility of match in Naive Bayes Classifier?

texts:
My math level is very very poor so I can't get the statistics.
Can anyone explain in simple words?
I.e. if I have frequency data:

Apple:
    Colors:
        Green = 3, Red = 2, Orange = 0;
    Shape:
        Sphere = 5, Ellipsoid = 0.
Orange:
    Colors:
        Green = 0, Red = 0, Orange = 5;
    Shape:
        Sphere = 5, Ellipsoid = 0.

I have many so fruits with frequencies, of course.
How can I get a possibility for object {Color: Red, Shape: Sphere} that it's an apple?


texts: An example of something you can formally verify with proofs in Software Development

texts:
I have been working on understanding formal verification of software. Formal methods include things like modeling your software with Petri Nets, Automata, or State-Transition Graphs. Other techniques for formal verification include using type systems, model checking, automated theorem proving, proofs, and doing program derivation. Finally, there is testing, but I wont go into that here.

I have asked several questions regarding these topics:

What to prove and how to prove it
What you want to "prove" in algorithms
High-level requirements for a Proof of "Saving to the Database"
How to prove a function returns a value
How proofs can be applied to a simple logging function
How to prove a side effect in a function
How to prove $c = a + b$ using Program Verification Techniques
How to use Hoare Logic to Prove this Assertion
How to apply Hoare Logic to this function
How to apply Operational Semantics to this function

The gist of the answers is essentially, you can't apply formal proofs to realistic software applications. This is a bit disappointing to hear, especially when there are projects such as CompCert, the "formally verified" C compiler. My first question is, what exactly they mean (in CompCert) by "formally verified". Wondering which of the following (or something different) this includes:

Model Checking
Formal Proofs (e.g. Hoare Logic)
Type Theory
Transition Systems
Operational Semantics / Denotational Semantics

My second question is, what is a realistic application of proofs to formally verify software (i.e. a web application example, not a textbook example). After asking these questions, I am discouraged that there are no applications of formal proofs to practical software development.

At first I thought that using Coq I could somehow write "formal proofs" for my code, and walk away with a sense of confidence that my code was "formally verified". But now I don't know if that has any practical or realistic meaning. That was what I was getting at in How to prove a function returns a value, High-level requirements for a Proof of “Saving to the Database”, and How proofs can be applied to a simple logging function.

Then I imagined that perhaps Operational Semantics or Hoare Logic could help in "formally proving" the behavior of functions. But the gist of the answers was "it's too hard" or "it's impractical". Nevertheless, it seems that CompCert accomplished it (but not sure if they used Hoare Logic, Operational Semantics, or others), or maybe I am missing something. So what my sense is is there is no use in Hoare Logic or Operational Semantics in practical software development. I would like to be proven wrong on that.

I realize that Model Checking is a good candidate for matching a program model with a specification. But the question still remains, how you know that your model is correct in the first place. That is where it seems formal proofs or some other formal verification technique could shine somehow (which is what this question is about). Wondering how in practice you can apply formal proofs to software development. How to verify that your Model Checking model is correct. It seems the only answer is "formal proofs". But then the question is how. How to apply formal proofs to your model to verify it is correct. I've tried asking questions about it but have had no luck.


texts: Having trouble proving a language is NP-complete

texts:
I'm asked to prove that, if P=NP, that 0*1* is NP-complete, but I'm having trouble going about doing it. I know it's fairly easy to prove it's NP by creating a TM to verify an input (which can be done in O(n) time, and that's polynomial).

But then I now have to reduce an NP-complete problem to 0*1* in order to prove that 0*1* is NP-complete. I'm thinking reducing SAT to it, but I have no idea how to do that, since in SAT all you can use is and, or, and negate, and there's no way to tell if a 1 came before a 0 in an input by doing that (at least, as far as I can tell).

Thanks


texts: What's an intuitive distinction between semi-computable problems and noncomputable problems/functions?

texts:
The definitions I've found were highly technical and using terms I've never seen before.

Say, I have a certain irrational number e that I get get closer and closer to with a computer and I want to determine if there is a particular digit d appearing after a certain position. Or what about the halting problem (give a program and ask 'will the computer ever halt?')? Are these problems semi-computable problems or noncomputable?


texts: Does the empty language have a CFG in CNF?

texts:
I just not sure does empty set have a context-free grammar in Chomsky normal form?

That is, for $B=\emptyset$, then a context-free grammar is $S \to S$, I think which doesn't have a Chomsky normal form. I am not sure. Can some one explain?


texts: Filling in the holes of a computable function for reduction

texts:
As part of a reduction I am trying to come up with a computable function that will fill in the holes of another function. Suppose $A$ is the set of all $n$ such that $\Phi(x,n)$ halts for all $x \in \mathbb{N}$, and suppose $B$ is the set of all $n$ such that $\Phi(x,n)$ halts for almost all $x \in \mathbb{N}$ ($\mathbb{N}$ minus finitely many natural numbers). I'm trying to show that $A \leq_m B$, i.e. $a \in A \Leftrightarrow f(a) \in B$ for some $f$.

What I have so far is: Suppose $f(x) = S^1_1(x,p)$ for some program encoded by $p$. let $f(a) \in B \Leftrightarrow \Phi(x,f(a))$ halts for almost all $x \Leftrightarrow \Phi(x,S^1_1(a,p))$ halts for almost all $x \Leftrightarrow \Phi(x,a,p)$ halts for almost all $x \Leftrightarrow$ (somehow by def of p) $\Phi(x,a)$ halts for all $x \Leftrightarrow a \in A$.

I'm stuck on what the program P should be to complete this proof. I think that it should "fill the holes" from almost all to all natural numbers. Any hints?

Note: $\Phi$ is the universal $L$ program and $S^1_1$ is from the S-n-m theorem (or parameter theorem).


texts: Can queueing model capture insights of a system in terms of CPU utilization & service delay?

texts:
After some efforts, I'm really doubtful about the application of that queueing model in analyzing network servers (specially in my case, IP Multimedia Subsystem) as well as predicting the workload. Therefore, as a newbie in this area, the purpose of my question is to ask if somebody can give me some advice for my following issue.

I am performing some analysis to measure network metrics (i.e. delay) or resource utilization by using M/G/1 queueing model. But my issue is that the analytical value is too much different from the experimental value (with Poisson traffic generator). For CPU utilization, I realize that it varies time by time and really is not what I expected based on analytical model with different inputs (i.e. arrival rate). And same problem with delay.

I've seen several papers that adopt M/M/1 and its variants to model a system to measure the delay. The point is that many of them have validated their model via simulation instead of doing real experiments (via testbed or in production environment). While the others omit the queueing delay due to many factors.

Any idea or suggestion is highly appreciated.


texts: Check if no linear combination is within a hypercube

texts:
Shapes

Let $C$ be the unit hypercube in $\mathbb{R}^{n}$.
Let $\vec{o}$ be a point in $\mathbb{R}^{n}$.
Let $B$ be a $n \times m$ matrix. The columns of $B$ are a set of linearly independent vectors in $\mathbb{R}^{n}$.
$m \le n$
$n$ is about 15 to 20.
Let $O$ be a $m$ dimensional coordinate with columns of $B$ as axes and $o$ as
the origin.

Projection

Given point $\vec{x}$ in $\mathbb{R}^{n}$.
$\textit{proj}_{O}(\vec{x}) = B\vec{y}$ where vector $\vec{y}$ minimizes square norm of $B\vec{y} - (\vec{x} - \vec{o})$.
That is solving a least square problem.
$B\vec{y} = QQ^{T}\vec{x}$ where $B = QR$.
QR factorization would need $2n^3$ flops. The two matrix-vector multiplications would each need $2n^{2}$ flops. (source).

Goal

I want to know if there exists any point ($\vec{z}$) within the hypercube such that $\vec{z} = \textit{proj}_{O}(\vec{z})$. That means $\vec{z}$ can be exactly represented by the coordinate system $O$.

Method

The center of the hypercube is $\vec{c} = \frac{1}{2}\vec{1}$.
Find $\vec{u} = \textit{proj}_{O}(\vec{c})$
If $\vec{u}$ is within the hypercube, return true.
Otherwise, find corner $\vec{v}$ of the hypercube that is closest to $\vec{u}$
Find $\vec{w} = \textit{proj}_{O}(\vec{v})$
If $\vec{w}$ is within the hypercube, return true.
Otherwise, return false.

Question

Is the method correct?
Is there a faster way?


texts: Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?

texts:
Strassen's algorithm uses the divide and conquer approach to divide the matrix multiplication of two  nxn matrices to multiplication of 7 2x2 matrices to get an overall complexity O(n^c) where c=log_2(7). I also read a paper which proved that it was impossible to multiply two 2x2 matrices in less than 7 multiplication operations.

So my question is, what's so special about 2x2? Why not break the original matrix multiplication to  3x3 matrix multiplication. Surely, if we can make the multiplication in 21 multiplications or less, then we would have a better result than dividing it to 2x2. And then why stop at 3x3, when you can divide the problem to 4x4, or in general axa?


texts: Local Cache miss using MESI Coherence Protocol

texts:
My notes on MESI state that there are a few courses of action when we experience a local cache miss on read, depending on the global state of the data (whether other copies already exist, and the state they exist in)
I'm having some trouble understanding how we know the state of the data when we miss on a read.
As far as I'm aware, MESI data is attached to each cache line, so if we have do not have a copy of the required data (we missed on the read) then how do we know the relevant MESI data, so we can make the decision on how to react to the miss? (whether we should read from memory, check for shared/modified copies etc)


texts: Elementary proof of compact space = exhaustible space?

texts:
The work of Martín Escardó has demonstrated close parallels between classical topology o one hand and computability on the other hand.  (See for example "Infinite sets that admit fast exhaustive search" 22nd Annual IEEE Symposium on Logic in Computer Science (2007)  443–452)
Escardó identifies continuous functions with computable functions, and open sets with recursively enumerable sets.

Another identification is between the exhaustible sets on one hand and compact sets on the other.  A set $S$ is exhausible if, given a total predicate $P:S\to\mathbf{Bool}$, one can always decide whether $P$ holds for every element of $S$.  According to Escardó, there is a close relationship between exhaustible and compact sets.  For example:

Finite sets are both compact and also obviously exhaustible.
The natural numbers are not compact and are not exhaustible. (If they were, we could solve the halting problem.)
But the one-point compactification of the naturals is exhaustible.
The Cantor set of all sequences of booleans, that is all functions $f:\Bbb N\to\mathbf{Bool}$ is both compact and exhaustible.

I have found the discussion of compactness in Escardó's papers very hard to follow, with many forward references.  The nearest thing to a proof that I can identify is in section 8 of his notes on "synthetic topology of data types". The proof in chapter 8 is very advanced.  In these notes compactness is initially defined to be exhaustibility, which doesn't make it easier to follow what is going on.

My question is:

  I keep hoping for an elementary proof, one which relates the conventional definition of compactness, in terms of open covers, to exhaustibility. I have not been able to find one myself and I have not been able to extract one from Escardó's papers.  Is there such a proof?


texts: Literature similar to Minsky's "Steps Toward Artificial Intelligence" (1961)?

texts:
With great pleasure I was just reviewing Marvin Minsky's publication "Steps Toward Artificial Intelligence" from 1961.

Now I would like to know whether there are any more compilations about the approaches to artificial intelligence with a similar depth and scope by authors with similar credibility, dating before or after the above mentioned work.

Is there any other notable publication that follows up on this (besides obviously Russel & Norvig's AIMA)?

Or maybe something presenting the problem from a different angle (e.g., from the "bottom up"-side of things, Deep Learning maybe)?

I'm interested in sources that attempt to outline or help understand the big picture of research in artificial intelligence. Not so much about the actual progress in specific disciplines.


texts: Approximation with imperfect dichotomy oracle

texts:
Given an unknown $x$ and an oracle $O(r)$ such that:

If $O(r)$ is true then $x \geq r$.
If $O(r)$ is false then $x < 2r$.

Conversely, the oracle has a defined behaviour only outside the interval $(x/2, x]$, and may output anything between.

We want to find a factor 2 approximation of $x$.

What is the strategy with a minimal number of calls to $O$?


texts: The common understanding of what oracle does is that it answers a question after a single operation.  So at first glance, it runs in $O(1)$.  But, doesn't it need to actually read the input?  Wouldn't this take at least $n$ steps?  If so then wouldn't an oracle run in $O(n)$?


texts: Quantum computer simulators with proper measurements

texts:
I have been looking for quantum computer simulators and came across QCAD (http://qcad.osdn.jp/). It is stated on their website that "Measurement gates on QCAD are different from real measurements."

I wonder if other simulators, like those listed on Quantiki (https://quantiki.org/wiki/list-qc-simulators), might have the same problem of incorrectly mapping the design with the experimental values.


texts: Prove that  is not a element of NOT-SELF

texts:
I know this has been a question but based on a past experience, i thought i would rewrite it so i can get input and ask questions faster.

Suppose we have
$$\text{NOT-SELF}=\{\langle M\rangle \mid  M \text{ is a Turing machine that does not accept }\langle M\rangle\}$$
the set of all machines that don't accept their own coding.

Let $Z$ be a TM such that $L(Z)$ is a subset of $\text{NOT-SELF}$. Prove that $\langle Z\rangle$ is an element of $\text{NOT-SELF}$.

My answer so far is very broad and I'm trying to improve it.

If $\langle Z\rangle$ is not an element of $\text{NOT-SELF}$, than $\langle Z\rangle$ can’t be an element in $L(Z)$. Since there’s a condition that $L(Z)$ is a subset of $\text{NOT-SELF}$,  this contradicts so $\langle Z\rangle$ must be an element of $\text{NOT-SELF}$.


texts: Minimise given size using dynamic programming

texts:
Given numbers $0<x_1<x_2< \dots<x_{n^2}<1,$ for every subset of $n$ of them $x_{i_1}<x_{i_2}< \dots<x_{i_n},$ let us consider the size: $$\max\{x_{i_1}, x_{i_2}-x_{i_1}, x_{i_3}-x_{i_2},\dots,x_{i_n}-x_{i_{n-1}},1-x_{i_n}\}$$
Give an algorithm to find the minimal size that subset of $n$ numbers can achieve.

My thoughts:
I would like to use dynamic programming.
I started by defining the following:
$$d(1) = x_{i_1}, d(j)=\max\{d(j-1), x_{i_j}-x_{i_{j-1}}\}$$
The solution to the problem will have to minimise the following:
$$\max\{d(n),1-x_{i_n}\}$$

I got stuck here, and my question is how can I continue to finish the solution.
Any help is appreciated.


texts:
I have an array of lines in 1D represented by coordination and weight, it can be only positive weight. I want to find all the lines that intersect a point in a given range.

Is there any efficient way of doing it?


texts: Difference between multi-tape Turing machine and single tape machine

texts:
A beginner's question about "fine-grained" computational power.
Let $M_k$ be a $k$-tapes turing machine, and let $M$ be a single tape turing machine. We know that $M_k$ and $M$ both have the same "computable power". In addition, one can simulate $M_k$ on $M$ in a way that every computation which takes $O(t(n))$ on $M_k$ will take $O(t(n) \log(t(n))$ on $M$.
Here is my question:
Is there a language $L$ such that $L$ can be decided in $O(n)$ time in $k$-tape Turing machine (for fixed $k$, say 2), but can't be decided in $O(n)$ time in a single tape machine? (every single tape machine which decides $L$ needs $\Omega(n \log n)$ time).
In addition, are there any examples of two computational models (classical, not the quantum model) with the same computable power, but with fine-grained differences in their running time? (I guess that major changes in running time would contradict the extended Church-Turing thesis, which is less likely).


texts: What algorithm to use for this kind of routing optimization?

texts:
Let's imagine a situation in order to fully understand the problem : let's say a lone human is walking back home at a very late time. He needs to find the safest path home. He naturally use the GPS with a start point A and a destination point B. Now the data I have may be GPS locations with an information stating the danger of that location, and those datas are usually available for the whole city. How can I actually plot the safest and also (if possible) fastest route from A to B using my datas ?

I actually looked for the way google maps plot it's routes and I understood it used the Dijkstra's algorithm, but it doesn't seem to be adapted to my problem.

I believed google maps could actually send me back every possible routes from A to B, then I could use my datas to calculate the safest route using a TSP algorithm (probably the ACS applied to the TSP) in order to optimize the use of the datas and with edge weights corresponding to the associated safety of the sub-path ?

Or maybe another algorithm should be used ?


texts: Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete?

texts: Given a NP-complete problem $A$, with parameter $a$ and a problem $B$ with parameter $b$, such that a problem in $A$ of size $\mathcal{O}(2^a)$ is $\mathcal{O}(b)$ when translated to $B$, is $B$ EXPTIME or NEXPTIME complete? I.e. If a problem of exponential size relative to a NPC problem is of linear size in another problem, is the other problem exponential time complete? (I think there needs to be an upper bound on the complexity of translating, but I'm not entirely sure what that would be.)


texts: Proving that a class of languages is a subset of RE for Rice Theorem

texts:
Consider language $L = \{<M> |L(M) \subseteq L(0(0\cup1)^*) \}$
  where $<M>$ is a valid encoding of a turing machine.

I know that the language is applicable for Rice Theorem.
Now, I understand that in this case the language group in $RE$ is:

$C = \{L\subseteq \Sigma^*|L\subseteq L(0(0\cup1)^*)\}$

However, I'm not sure how to prove that each of these languages is in the $RE$ class. Note That an alphabet wasn't given in the exercise so I guess that there can be other letters. I thought at first it had something to do with the languages being subests of a regular language, but then again $\Sigma^*$ is a regular language and all other languages are its subsets.


texts:
I'm trying to understand why:
$$L_{\Sigma^*}=\{\langle M\rangle|L(M)=\Sigma^*\}\notin coRE$$
As I see it TM, $\langle M\rangle$, should accept all the inputs, and if one of the inputs rejected it's not $L(M)=\Sigma^*$ any more, so why it's not? $$L_{\Sigma^*}\in coRE$$
$*$ I familiar with the reductions $HP\le L_{\Sigma^*}$ and $HP\le \overline{L_{\Sigma^*}}$ to proof $L_{\Sigma^*}, \overline{L_{\Sigma^*}}\notin RE$


texts: Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm'

texts:
I'm working on solving an algorithm problem defined as follows (important parts in bold):

  Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.

  You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build?

  The parameter of the function findNb will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + ... + 1^3 = m if such a n exists or -1 if there is no such n.

Okay, so here's how I've been approaching the problem from a theoretical standpoint:

The summation 1^3 + 2^3 + ... + n^3 is equal to [n(n+1)/2]^2 = m.
Taking the square root of both sides yields |n(n+1)/2| = sqrt(m). We can disregard the absolute value sign because n will always be positive. So n(n+1)/2 = sqrt(m).
Therefore, n(n+1) = 2*sqrt(m). This problem is essentially asking us to find two consecutive numbers, n and n+1, such that their product is equal to 2*sqrt(m).

My code

def find_nb(m):
    target = 2*math.sqrt(m)
    for n in range(1, int(math.sqrt(target))+1):
        if n*(n+1) == target:
            return n
    return -1

Here, I've defined target to be 2*sqrt(m). I'm looping from n=1 to n=sqrt(target) (inclusive) because there is no point in going beyond the square root of the target when trying to find two numbers, n and n+1, whose product equals the target.

The issue...

This code runs into floating-point precision issues that are fairly consistent across all tests that failed. Here are some screenshots of tests that failed:

Notice that in all of these cases, the value I end up returning is 1 less than the value I stopped looping at. This is quite odd, and I'm not sure what could be causing this behavior.

If you compute the values using a good calculator, you'll find that it is indeed an issue of floating-point imprecision. I'm not sure how to deal with that. My code fails for 33/69 test cases.

Alternative approach

In yet another attempt, I tried doing the most straightforward solution possible: looping from n=1 to n=m and calculating [n(n+1)/2]^2 for each iteration, then comparing this to m. And, unsurprisingly, that solution is not accepted because it takes too long to execute for very large values of m!

So I tried looping from n=1 to n=sqrt(m) to at least simplify the range of values I'm working with. But clearly, the exponentiation, division, and multiplication add up in terms of complexity, and thus this revised approach also results in an execution timeout.

Question

How am I supposed to solve this problem? Is it possible to solve this problem without introducing floating-point errors and without the algorithm taking an unreasonable amount of time for large input values?


texts: How to enumerate all combinations of $n$ binary variables s.t. their sum is $k$?

texts:
Suppose we are given $n$ variables $X_i, i=1,\dots,n$, each taking values from $\{0,1\}$, and a constant integer $k$ with $ 0\leq k \leq n$.

What are some efficient ways to enumerate all possible combinations of values of $X_i$'s subject to the constraint $\sum_{i=1}^n X_i = k$?

A naive way is to first enumerate one by one all possible combinations of values of $X_i$'s without the constraint  $\sum_{i=1}^n X_i = k$, and for each combination, check if it satisfies  $\sum_{i=1}^n X_i = k$ (if it does, keep it; if it doesn't, discard it).

That naive way may be inefficient.
For example, when $k=1$, a more efficient way will be for each $i$, letting $X_i=1$ and $X_j =0, \forall j \neq i$.

So I wonder for general $k$, what are some efficient ways to do the above task?


texts: If a problem is "not semi-decidable" and "not decidable" can we say it is "undecidable"?

texts:
I was under impression that when a Language (or problem) is not semi-decidable and not decidable then we can say it's undecidable and I think it makes sense also based on diagram.

However, in my assignment the TA struck out "undecidable" and wrote "not semi-decidable". Why is "undecidable" wrong if it's both not semi-decidable and not decidable?


texts: How does the Weibull distribution work as fault model in wireless sensor networks?

texts:
I am a little bit confused with the concept of using the Weibull distribution or other distribution for fault model. As I understand, in simulation this distribution is often used for modelling a fault in components.

On the other hand when designing systems we often assume some components might become faulty and we use fault detection method to know where the distinct component is faulty or not.

I want to categorize faulty sensor in 5 groups: transmitter circuit/battery condition/micro controller/receiver circuit and sensor circuit fault and correlated these kinds we can have different attribute in network.

The question is, how can i write the Weibull distribution function to produce these kinds of fault in a wireless sensor networks?


texts:
Prove that each property below characterizes forests...

a. every induced subgraph has a vertex of degree at most one.

When proving a characterization, do we have to prove both directions, like an if and only if, or does it suffice to prove only one direction?


texts: Word embeddings with documents and users

texts:
I understand how one can generate a latent vector space from a collection of words or documents, using something like Glove, word2vec, doc2vec, etc. I don't understand how this representation can be turned into features for something generating these documents at a "higher level", like a user or a product.

Here's a concrete example: I have users on a website who are generating reviews, which are written in English. Suppose I want to make a binary classification of users on whether or not they will stop using the site in the next month. How do I go from a word embedding, or a list of document embeddings for each user, into features for the user?

I believe this third level comes up a lot in practice. For example,

users ->  multiple reviews -> words. Task: predict if a user will want to buy product X.
items -> multiple reviews -> words. Task: group items into sales categories.
artists -> multiple songs -> audio (audio embedded into a space). Task: group artists into genres.

I feel as though this is a common use case but I lack the vocabulary to search for it effectively. Apologies if this is a repeat question.

EDITED: I edited the question for clarify of the problem formulation.


texts: Turing-recognizable languages closed under star operation

texts: I'm tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I'm confused about how this is true. For example, I have a TM to recognize a language A = { a2n: n >= 0 }, all strings of a's which length is a power of 2. So here's where I get confused, if I have A*, then I can have (aa)*, which could then lead to (aa)(aa)(aa) = aaaaaa, and this has a length that is not a power of 2. What part of my logic here is wrong?


texts: Why can't edit distance be solved as L1 distance?

texts:
Given two strings $x$ and $y$ over the alphabet $\Sigma$ one defines the edit-distance $\text{ed}(x,y)$ as the minimum number of substitutions, insertions and deletions of characters required to transform $x$ into $y$.

If $m = \max ( \text{len}(x),\text{len}(y) )$ then padding with appropriate zeroes on the smaller string one can define $x$ and $y$ as both being elements of $\Sigma^m$. Now both $x$ and $y$ are vertices of the cube $\Sigma^m$.

Now isn't $\text{ed}(x,y)$ the shortest distance between $x$ and $y$ in this cube graph? Why isn't edit distance found by finding shortest paths in this cube?


texts: $\Omega(\sqrt[3]{n})$ lower bound on random-access memory?

texts:
Here is a perhaps naive question that has been tingling me: Is there an $\Omega(\sqrt[3]{n})$ asymptotic lower bound for addressing arbitrarily large memory randomly? My cause of belief is that the shortest path to any memory stored physically must be through three-dimensional space, and the diagonal here must have some minimal length.

For example, when sorting arbitrarily many elements, then addressing these elements must eventually cost something proportional to the distance, and even if you have high-speed cable between every single point in some space, it seems as if there is a geometric limit bounded at higher than $\Omega(n \lg n)$.

What is wrong with my argument?


texts: Algorithms : most lightweight circle in directed graph that goes through specific vertex

texts:
I have directed Graph G(V,E) with weight function w. so that weight of each (u,v) is a positive value.
I need to find the most lightweight circle in the graph that vertex k' is part of it.

I've also given an algorithm i can use which can find the most lightweight path for a graph with positives weights ( i can use it only once).

I thought about creating a sub graph G' where all vertices and edges that are strongly connected components. find the graph which k' is part of it. then find for the most lightweight adjacent edge from k' to some v of vertices. from that v i can run the algorithm given and find the lightweight path then add the weight of the vertex missing ( (k',v) ).

is that seems correct ? I'm in the beginning of this course and I feel i'm not there yet.


texts: Why does garbage collection extend only to memory and not other resource types?

texts:
It seems like people got tired of manual memory management, so they invented garbage collection, and life was reasonably good.  But what about every other resource types?  File descriptors, sockets, or even user created data like database connections?

This feels like a naive question but I cannot find any place where anyone has asked it.  Let's consider file descriptors.  Say a program knows that it will only be allowed to have 4000 fds available when it starts.  Whenever it performs an operation that will open a file descriptor, what if it would

Check to make sure that it isn't about to run out.
If it is, trigger the garbage collector, which will free a bunch of memory.
If some of the memory freed held references to file descriptors, close them immediately.  It knows the memory belonged to a resource because the memory tied to that resource was registered into a 'file descriptor registry', for lack of a better term, when it was first opened.
Open a new file descriptor, copy it into new memory, register that memory location into the 'file descriptor registry' and return it to the user.

So the resource would not be freed promptly, but it would be freed whenever the gc ran which includes at the very least, right before the resource was about to run out, assuming it isn't being entirely utilized.

And it seems like that would be sufficient for many user defined resource cleanup issues.  I managed to find a single comment here that references doing cleanup similar to this in C++ with a thread that contains a reference to a resource and cleans it up when only it has a single reference remaining (from the cleanup thread), but I can't find any evidence of this being a library or part of any existing language.


texts: Efficient parameterization of low vertex count polygons

texts:
I'm trying to design a method to represent polygons as vectors. There are many ways to do this, but I have a few goals and I'm not sure what representation is best to fulfil these. The objectives are:

I want there to be a simple (efficiently computable) distance function between polygons that gives a measure of how different the contained region of two polygons are.
The function does not have to be completely invertible or one-to-one, but it should be possible to reconstruct something close to the original from it.
The vector for the representation should be the same dimension no matter the polygon.

This might seem a bit strange but I'll give an example of what I mean. The best way I've been able to come up with is to send out "rays" from the centroid of the polygon in even angular intervals. I then measure the length of these rays always starting from the same direction and going counter clockwise. The lengths become my vector representation of the shape.

I think this easy algorithm works fairly well but it has a few flaws. I'm using the euclidean distance between the vectors as my distance function and I'm not sure how well it really works. Also, as seen in the picture where the blue circle is, concave shapes can give rise to awkward situations like this where I'm not sure where to stop the ray.

Maybe it's also helpful to know why I need this. It will be used to find the most similar polygon in a database to a specific shape.

My question is just if you know of, or can come up with, a better or simpler way to do this representation than the one I have.

Thank you!


texts: Finding closest edge to a point in a planar graph

texts:
I have a point location problem (in a planar graph) with a twist: rather then finding which region the point is located in, I would like to find the closest segment (edge) to a point, ideally with a O(log n) complexity.
So far I was not successful in finding any reference that would discuss this specific problem. Is there any treatment you know of?
For this problem, we can assume that the graph is embedded in a Euclidian plane in a known way, where vertices are mapped to points and edges are mapped to straight line segments.


texts:
I'm looking for best algorithms to compare two Circular Linked List?

For example :

List 1 = 1-3-5

List 2 = 3-5-1

I want to compare "same" or "not same"  but need fast algorithm.


texts: Showing that a problem in X is not X-Complete

texts:
The Existential Theory of the Reals is in PSPACE, but I don't know whether it is  PSPACE-Complete. If I believe that it is not the case,  how could I prove it?

More generally, given a problem in some complexity class X, how can I show that it is not X-Complete? For example, X could be NP, PSPACE, EXPTIME.


texts: How to find the minimum and maximum of subroutine median3(x,y,z) from a totally ordered set?


texts: How to minimally extend a digraph such that all nodes are on a cycle?

texts:
Let's say we have a directed graph with $n$ nodes and $m$ edges. For each node we want to make path that will start from this node, possibly traverse some other nodes and finish in the same node, in other words we want to make a cycle through each node. It is allowed to add edges that start and finish in the same node.

We want to use minimum number of edges.

Let's for example consider the following graph. We can add edges: $(1,1),(2,2),(3,3),(4,4)$. But that will cost us to add 4 edges, and we can make the cycles with adding only one edge $(4,1)$.

I think that first we should find all the paths in the graph, and then link the last node with the first node, this will allow us to minimize the added edges, and surely will make all the nodes in the path linked in the cycle.

But the problem is find all the paths, I cannot think of the algorithm that will find us all pairs of paths, also the problem is if there is more than one path between the first and the last nodes, please give me some hints on how to solve this problem.

Also, I think that finding all paths in the graph is $NP-hard$ and it may be really slow, but the number of nodes is small, less than 20, so even solution of time complexity $O(2^N)$ are good.


texts: How to use Runge–Kutta methods in a second order ODE

texts:
Consider a second order equation $F=ma=m\ddot{x}$.
In the language of Euler's method

$\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$
$\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$
$x(t+dt)=x(t)+\dot x(t)dt$

Basically, the entire iteration was the second order force equation $F(t,x(t),\dot x(t))$.
However, here one wanted to apply Runge–Kutta method(standard "RK4", not Runge–Kutta–Nyström or else) to solve that equation.
For notation simplicity, let $v\sim \dot x$, $a\sim \ddot x$(velocity and acceleration).
From $x(t),v(t),a(t)$:
$ka1=F(t,x(t),\dot x(t))$; $kv1=v(t)+a(t)\frac{dt}{2}$; $kx1=x(t)+v(t)\frac{dt}{2}$;
$ka2=F(t+\frac{dt}{2},kx1, kv1)$; $kv2=kv1+ka1\cdot \frac{dt}{2}$; $kx2=kx1+kv1\cdot \frac{dt}{2}$;
$ka3=F(t+\frac{dt}{2},kx2, kv2)$; $kv3=kv2+ka2\cdot dt$; $kx3=kx2+kv2\cdot dt$;
and finally
$ka4=F(t+dt,kx3, kv3)$;
The final acceleration was collected to be
Iteration Update Method 01
$\ddot x(t+dt)=(ka1+ka2\cdot 2+ka3\cdot 2+ka4)/6$; where
$\dot x(t+dt)=\dot x(t)+\ddot x(t)dt$;
$x(t+dt)=x(t)+\dot x(t)dt$
with such loop the iteration was able to run in RK4 method and things worked very nicely and coincided with the analytical calculation for an example which Euler method was known to fail.(Tested)
However, my question arise from a mistake where it made the code fail to work. It went like this:
In addition to the $\ddot x(t+dt)$ condition, one further to average the speed directly,
Iteration Update Method 02
$\ddot x(t+dt)=(ka1+ka2\cdot 2+ka3\cdot 2+ka4)/6$;
$\dot x(t+dt)=(\dot x(t)+kv1\cdot 2+kv2\cdot 2+kv3)/6$; and
$x(t+dt)=x(t)+\dot x(t)dt$;
Notice that the new update method attempted to use the $\dot x(t)$  to take care of the "overflow". Intuitively, not only the acceleration $\ddot x$ was "RK4"-ed, but also, the velocity $\dot x$ was "RK4"-ed as well. However, thought still able to produce a sensible graph, the Iteration Update Method 02 was proven to have failed after the analysis.
Question 1: Why Iteration Update Method 01 worked? Even though it approximated $\frac{d^2y(t)}{dt}=f(t,y(t),\dot y(t))$ instead of $\frac{d y(t)}{dt}=f(t,y(t))$?
Question 2: Why Iteration Update Method 02 failed? Shouldn't it work better since it averaged more stuff?


texts: Finishing degree requirements NP-complete: Choosing 1 element from each set avoiding conflicts

texts:
The question, which I have slightly paraphrased to get rid of the fat, is this: There are $k$ areas of study in which you need to take 1 course. For each area of study, there is a set of courses $C_1,C_2,\dots,C_k$ that you have not yet taken. There are no conflicts between courses in the same area of study, but there can be conflicts between courses in different areas of study. You have a list of $(class1, class2)$ pairs in different areas of study that are in conflict. Can you choose 1 course from each area so that there are no conflicts? Is this an NP-complete problem?

Here is what I have so far:
K-AREA-COURSE-REGISTRATION ∈ NP: Given a random list of k courses, we can check that we have one course from each area in O(k) time. We can also check for conflicts in O(k^2) time (check each pair of courses for conflict).

K-AREA-COURSE-REGISTRATION is NP-complete: Reduce 3-SAT to K-AREA-COURSE-REGISTRATION. Each 3-SAT literal becomes a course (same literal in different clause is a different course). Each clause becomes an area of study (clauses become the $C_k$ sets). Create conflicts between two courses $a,b$ if, in the original 3-SAT problem, $a=x$ and $b=\bar{x}$. Choosing one course from each set will set at least 1 literal in each 3-SAT clause true. The conflicts will stop us from setting a single literal both true and false

Question: Do I have/do you have any tips in accounting for the case of two courses $a,b$ which both map to the same literal $x$ in the original 3-SAT but are in different clauses (therefore in different $Ck$ sets). I may be able to use conflicts to make sure both $a$ and $b$ are chosen, but I was thinking I could just ignore this since all that matters in 3-SAT is at least one literal.


texts: Why doesn't the binary fraction representation match the decimal fraction representation?

texts:
The Problem: What value does the hexadecimal number x55544552 represent in data type IEEE floating point?

My Work:
     I first wrote out that hexadecimal number in binary and got

0101 0101 0101 0100 0100 0101 0101 0010

   Now I have my three different sections, the sign, 0, the exponent 10101010 - 127, or 170 - 127, 43, and the fraction portion  101 0100 0100 0101 0101 0010, or 5522770.

    Now I can write out my IEEE floating representation as
        1.552270 $*$ 2 $^{43}$
   To simplify that expression, I decided to move the decimal point 23 slots to the right(the whole exponent proportion) and got
   (1 101 0100 0100 0101 0101 0010) * 2 $^{20}$) or 13911378 * 2$^{20}$.

To me, all my math made sense. When I checked
my answer on  Hex to IEEE Float, everything matched up but I couldn't figure out this part on the web application.
The web application has a specified section called fraction which represents the fraction of the floating point representation. In binary, the fraction is 1 .10101000100010101010010 but in decimal, the web application says the fraction is 1.6583655. When I converted 10101000100010101010010 to decimal, I got 5522770. Shouldn't the fraction decimal representation be 1.5522770 or am I missing something?


texts:
Why is it true? I understand why $n^g$ but how does the $f$ get there in the power??
I believe from the context that it's not just that $\binom{n}{f}^g$ is strictly smaller than $n^{f g}$, but rather that it really belongs to this class, which means it's also tightly bounded by it or very close. But why is it?


texts: Number of Final States Subset Construction for NFA to DFA

texts:
"Suppose we use the subset construction to convert a $7$-state NFA $M = (Q,\Sigma, \delta, q_0, F)$ into a DFA $M' = (Q', \Sigma, \delta', q_0, F')$ for the same language. Then $M'$ will have $|Q'| = 128$ states. If $|F| = 2$, then $M'$ will have $|F'| = 96$ final states."

From the subset construction, I know there are $\mathcal{P}(Q)$ new states in the machine, which means there are $2^7 = 128$ new states in $M'$. I am not sure mathematically why there are $96$ final states.

Observations:

I see that if I have an initial NFA with $3$-states $\{1,2,3\}$ and a $|F| = \{1\}$, then $P(\{1,2,3\}) = \left\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \right\}$. I can also note that there are now $4$ final states and can conjecture $|F| = 2^{n} - 2^{n-k} = 2^{3} - 2^{3-1} = 4$, where $k$ is the number of final states. I also notice that each particular state occurs $2^{n} - 2^{n-k}$ times in the construction.

However, if I let there be $2$ final states (say $\{1,2\}$) in the initial machine, the new machine will have $5$ final states, not $2^3 - 2^{3-2} = 6$. I can see this is because $\{1,2\}$ is a state that contains both elements, and is  being double counted.

I would prefer simple well-written intuitive answer rather than an overly mathematical one.


texts: Turing reduction problem, intersection is equal to an empty set

texts:
$L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)=\emptyset\}$ prove to be undecidable.
My approach:
We will prove this by reduction $L_{\emptyset} \leq_T L_c$  We begin by assuming that $L_c$ is decidable and that we have access to a black box $Q$ which decides it. We want to construct another Turing machine $H$ which decides $L_{\emptyset}$.

H = “On input (< M >, w).
    Construct the following machine M’
M’ = “On input w.
    Ignore input w and reject.
    Run decider Q on (< M >,< M’>)
    If Q accepts, reject.
    If Q reject, accept.

I'm mainly concerned about my choice of $L_{\emptyset}$ (maybe $L_{halt}$ is better suited here?) and the part where I run the decider $Q$ on ($\langle M \rangle, \langle M'\rangle)$. Any help would be much appreciated, Thank you!


texts: Finding Regular expression for FSM with more than one final state

texts:
I am trying to find Regular expression for a FSM with more than one final state(in my case 2).

In this I am getting two different RE for state q4 and q5. So my question is If we get more than one different RE for one FSM with more than one final state, is it correct??


texts: Logarithmic guarantees for randomized search trees

texts:
In this paper [1], "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being inserted into the tree.

The authors assume that randomness is "hidden" from the user:

  All expectations are with respect to randomness that is "controlled" by the update algorithms. For the time being we assume that the priorities are kept hidden from the "user." This is necessary to ensure that a randomized search tree is transformed into a randomized search tree by any update. If the user knew the actual priorities it would a simple matter to create a very "non-random" and unbalanced tree by a polynomial number of updates.

I don't actually understand what is meant by that. Specifically, I don't understand what the user might be able to do to affect the runtime by observing the generated priorities. My ideas of trying to understand that are:

The user might be able to provide keys in certain order to make the resulting trees unblanaced! However, I don't think this is right because the priorities are not generated based on key values.
I understood the paragraph wrongly and they actually mean that the priority generation is controlled by the user not just seen by the user.

[1] https://faculty.washington.edu/aragon/pubs/rst96.pdf


texts: Carry Look Ahead Adder for stabilize the sum

texts:
An four-bit carry-look-ahead adder for computing the sum of 2 numbers
, where A and B are integers represented in 2's complement form. If the decimal value of A is 3, the decimal value of B that leads to the longest value for the sum to stabilize is __________________

I know adder is used for adding two numbers and carry look ahead adder is used for propagating the carry. But how it could be used for stabilising a sum, I couldn't understand this part and couldn't able to answer


texts: Name for the "starting vertex" and "ending vertex" of a directed edge

texts:
Say a graph contains a directed edge e from vertex a to vertex b.  Is there a standard name for vertex a relative to edge e?  And similarly for vertex b?

Something akin to vectors in high school physics, where the initial point of the vector is called the "tail" and the terminal point of the vector is called the "tip"?  I'd like to say something like "a is the tail of edge e" or "b is the terminal vertex of edge e."


texts:
I am studying computational theory with Sipser's textbook. I can't quite understand the definition of "reduction". For example, "this problem can be reduced to ATM ..."

What exactly does "to reduce" mean? I can't draw the picture in my head. Can anyone can help me understand this definition?


texts: Why having a simple multiplication loop and very good avalanche isn't enough to produce well-distributed hash values?

texts:
Modern non-cryptographic 32- and 64-bit valued hash functions, for example, lookup3, MurmurHash3 and CityHash, have quite sophisticated loops, each iteration of which include many multiplications, XORs and rotates. Why this is needed, since there are good avalanche procedures (32 -> 32 and 64 -> 64 bits), which mix the bits effectively randomly. So, even if this simple loop:

hash = seed;
while (input_len >= 8)
    hash = hash * prime + fetch_8_input_bytes();
... do something for rest 0..7 bytes of input

produce whatever flawed, biased results for similar input (or a certain subset of input), finalizing avalanche:

return good_avalanche(hash)

"fixes" this.

The last deal is direct collisions, but they are often not so important, assuming hash function produce decently little collisions. I think the above multimplication loop does.

What I'm missing?


texts: Which data structure can be used to determine most experienced person in a shift?

texts:
Problem Statement: There are $n$ hours in a day and you have $w$
workers.  For each worker $i$ you will be given $x_i$ (work experience),
$s_i$ (shift start time) and $e_i$ (shift end time) on a separate line.
Here $s_i$ and $e_i$ are both inclusive.  At any given hour $t$ in a
day, you have to determine who is the most experienced worker available.
I thought of two approaches:

Keep an interval array of size $n$.  For each worker $i$, from index
$s_i$ to $e_i$ of the array, fill it with $x_i$ if current value in
the array is lesser.  This is memory intensive.

Store $\left( x_i, s_i, e_i \right)$ for each worker $i$ in a list.
Loop through the list for every $t$ provided to find the most
experienced person.  This is CPU intensive.

I want to know which data structure can be used to solve this problem
optimally.


texts: I'm teaching Architecture this semester, and I'm using Computer Organization and Design (Patterson & Hennessy) as the text. The book contains a table that has the typical access time and cost of SRAM, DRAM, flash, and hard disk as of 2012. Costs have come down pretty steeply in the last 4-5 years though, and I'd like to give my students a more up-to-date version. And while I can easily find cost/GB on the other 3 technologies, I'm having a hard time finding an up-to-date cost for SRAM. Can anybody help with that?


texts: Splitting permutations into transpositions

texts:
Suppose we are given an array $\texttt{a[]}$ of $n$ non-negative integers. The algorithm should give back $\texttt{-1}$ if an integer appears more than once in $\texttt{a[]}$.

Otherwise we interpret $\texttt{a[]}$ as a permutation $\pi:\{0,\ldots, \texttt{max(a[])}\} \to \{0,\ldots, \texttt{max(a[])}\}$ sending $\texttt{i}$ to $\texttt{a[i]}$ for $\texttt{i} \in \{0,\ldots,n-1\}$, and $\pi(k) = k$ for $k\geq \texttt{length(a[])}$.

What could be an algorithm to write $\pi$ as represented by $\texttt{a[]}$ as a sequence of transpositions, and what is the complexity?


texts: Sort an array that contain two sorted array in $O(n)$

texts:
Given an array $A[1..n]$. $A$ is mixed of two sorted arrays $B$ and
$C$ of equal sizes, such that $B$ is in the ascending order and $C$ is in
the descending order.
Consider the following example: $B=[2,4,6,8]$ and $C=[9,7,5,1]$. As a
result $A=[2,9,7,4,6,5,8,1]$. Interestingly, The instructor said: $A$
can be sorted in $O(n)$. Anyone can give me a hint?

My attempt:
I tried to partition the array $A$ into sorted arrays $B$ and $C$, but I could not do it because my approach encountered counterexamples.


texts: Are there any algorithms that run in (2 ↑ ↑ n)?

texts:
I’m wondering whether there are any algorithms that use so much time that they must be represented using Knuth up-arrow notation.

Required: Use more than one up-arrow for time complexity.

Bonus points:

Have the algorithm be useful.
Have the algorithm be useful and optimized


texts: Relations between the knapsack problem, the bin packing problem, and the set packing problem?

texts:
I wonder what relations are between the knapsack problem, the bin packing problem and the set packing problem?

From their mathematical formulations, I don't see the first two belong to the third one i.e. the set packing problem, although I feel the third one sounds more general than the other two.

Or under what conditions there are some conversions between each other?

Thanks!


texts: Prove Partition is NP-Complete using that SubsetSum so is it

texts:
The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete.

The Partition problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ can be partitionated in two subsets such that the difference between the sums of the both sets are lesser or equal to $K$.

Prove that the partition problem is NP-Complete using that SubsetSum so is it.

Any ideas?


texts: Could min cut be easier than network flow?

texts:
Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut.  Therefore, the complexity of computing a minimum $(s,t)$-cut is no more than the complexity of computing a maximum $(s,t)$-flow.

Could it be less?  Could there be an algorithm for computing a minimum $(s,t)$-cut that is faster than any max-flow algorithm?

I tried finding a reduction to reduce the $(s,t$)-max-flow problem to the $(s,t)$-min-cut problem, but I wasn't able to find one.  My first thought was to use a divide-and-conquer algorithm: first find a min-cut, which separates the graph into two parts; now recursively find a max-flow for the left part and a max-flow for the right part, and combine them together with all of the edges crossing the cut.  This would indeed work to produce a maximum flow, but its worst-case running time might be as much as $O(|V|)$ times as large as the running time of the min-cut algorithm.  Is there a better reduction?

I realize the max-flow min-cut theorem shows that the complexity of computing the value of a max-flow is the same as the complexity of computing the capacity of a min-cut, but that's not what I'm asking about.  I'm asking about the problem of finding a max-flow and finding a min-cut (explicitly).

This is very closely related to Compute a max-flow from a min-cut, except: (1) I'm willing to allow Cook reductions (Turing reductions), not just Karp reductions (many-one reductions), and (2) perhaps given $G$ we can find some graph $G'$ such that the min-cut of $G'$ makes it easy to compute the max-flow of $G$, which is something that's out of scope for that other question.


texts: Getting a tighter upper bound on the following function

texts:
We have the following function which determines the Nth fibonacci number:

int fib(int n){
    if(n<=0) return 0;
    else if (n==1) return 1;
    return fib(n-1)+ fib(n-2)

}

Find the time complexity

I am currently reading the book "Cracking the coding interview" and the answer it gave is quite disappointing.  The book says that there are 2 branches per call, and we go as deep as N, therefore the runtime is $O(2^N)$ and it later explains that a tighter upper-bound is $O(1.6^N)$, but it doesn't go over it because the mathematics are "very complex. It doesn't even point out the place where we can find the approach to get the desired upper-bound. I don't want to defame "cracking the coding interview", but I think that more consistency must be shown. My question is, how do we get $O(1.6^N)$ for the algorithm?. It doesn't look like top notch math.


texts: Algorithm to merge multiple polylines into contours

texts:
There is a set of 2D polylines, each polyline defined by an ordered array of vertices (each vertex is joined with the previous one by a line, if drawn). Together, when drawn, these polylines form one or more contours, but they can be fragmented (a single contour consisting of several polylines)

The task is to build new polylines, based on the original points, so that the new ones form only "outermost" contours. This is illustrated by the pictures. The first one is the original set of poly lines, each shown with a different color. The second picture is what I'd like to have: 4 arrays-polylines (4 contours)

I need to build an algorithm to transform the first pic into the second one. I suppose there should be a simple solution but not sure which side to tackle this task from. How to approach this? Thanks for any clues!


texts:
The question is:

Return the length of the longest, non-empty, contiguous subarray of A with sum at most K.
For example: A=[5,2,-1,0,3],K=1, the result is [2,-1,0]

I am inspired by Shortest Subarray with Sum at Least K. Is it possible to solve this corresponding problem with a monotonic queue? If True, how? If not, Why?
I have struggled with it for a long time. Hope for your help.


texts:
I am confused on the following:
In the following trivial code:

for (int i = 0; i < n; i++) {
  for(int j = i + 1; j < n; j++) {
     for(int k = j + 1; k < n; k++) {
          //some code here
     }
   }
}

I know that the complexity is N^3. But I am confused on some details.
The outer loop is executed N times.
The inner loop I thought that it was executed N*(N-1) times but when I tested with a small example of n=5 it is executed actually N*(N-1)/2 times. And the inner most loop I am lost on how the exact number of times it is executed. I originally thought that it is executed N(N-1)(N-2) but this is wrong again by using a small n the numbers don't work out.
So my question is:
1) Can someone help me understand how the exact complexity is calculated on this trivial example?
2) What is the usual process? Do we select some small numbers and try to derive a formula or what?


texts: Does a Non-Deterministic Turing Machine solve all problems in P in constant time?

texts: If a non-deterministic Turing machine can just "guess" the correct answer to a problem, does it do this in constant time/immediately? Also, does this also apply to problems in NP too?


texts: Shortest traverse path in a matrix given the start point $(i,j)$

texts:
Given a $m\times n$ matrix and a starting position $(i,j)$, how can we find the shortest path to go through all the elements at least once if we can only move by a single unit (i.e. up, right, left or down) at a time?
Currently all I could think of was moving to the nearest corner and then traversing from there, but that would not be the shortest path unless the start position is already a corner. And unfortunately I couldn't find anything similar to this problem.


texts: How do we know INVERSIONS-COUNT algorithm implemented in balanced tree really works?

texts:
How do we know INVERSIONS-COUNT algorithm (exercise 14.1-7 from here), implemented in balanced tree really works?

We assume that the tree data structure we're using is an order statistic tree which means that a) it's a balanced binary tree, b) each node $x$ is augmented with $size$ field which tells us the size of the node's subtree (its inner nodes, including $x$).

We also have an array $L[1..n]$ which contains the values of the keys of the tree (not necessarily sorted).

The algorithm uses two helper functions:

RANK(Tree, node_x) - returns the rank of the key of node_x in array $L$.

SEARCH(Tree, L[i]) - returns the node with the same key as the element $L[i]$ in the given array.

This is the code:

Construct an order statistic tree T for all the elements in L
   t = −|L|
   for i from 0 to |L| − 1 do
      t = t + RANK(T, SEARCH(T, L[i]))
      remove the node corresponding to L[i] from T end for
   return t

If the array is sorted then there're no inversions. Therefore t is incremented each time by $1$ because in sorted array each new element is the minimal one and has rank $1$ (because we delete the last node).

If the array is not sorted then why are we guaranteed that the ranks will at some point "overtake" t and produce the correct amount of inversions?


texts: Amortize time for a counter with the operations INCREMENT and DECREMENT

texts:
Let a binary counter with the operations INCREMENT and DECREMENT.

I need to show that you can't implement this kind of counter with constant amortized time per operation.

Hence, I need to show that there's a series of $N$ operations with amortized time of $\omega(N)$.

My Try:
Let's assume we made $2^k-1$ INCREMENT operations. Hence, our counter is a sequence with $k$ 1's. Now, Let's consider a sequence of $N$ operations alternating between DECREMENT and INCREMENT (DEC,INC,DEC,INC,DEC...)

Each operation must be $\Theta(k)$. Somehow, I need to figure out that it has to be that the amortize time is $\omega(N)$. How?


texts: Can NFAs determinization be efficient given that the statespace is exponential?

texts:
I have recently learned about using powerset construction for conversion of NFA to DFA - however this only seems to be feasible when the number of states we are working with are 3 or less, as $2^k$ seems to grow unmanageable very quickly.

I have a problem with 6 states, meaning that if I were to use powerset construction, I would have 64 states. What is a more efficient way?


texts: What is the difference between the situation calculus and the propositional logic of context?

texts:
I have been reading a lot of papers by John McCarthy lately. As early as 1963, he developed the situation calculus, but then starting in 1987, he developed what came to be known as the propositional logic of context (PLC) (McCarthy, 1987; McCarthy, 1993). Surprisingly, he doesn't really describe the relationship between situation and context or how one formalism fits into the other (or perhaps they don't, but he doesn't say that either).

I have come across one paper that sheds some light on the relationship between situation and context, but it mainly discusses situation in the context of situation theory, which appears to be distinct from the situation calculus. Does anyone know of a good reference that discusses jointly the situation calculus and PLC? Or can you provide an explanation of their relationship here on SE?


texts:
Let L1 be a language generated by a CFG.
Let L2 be a language generated by a regular grammar.
Is L1 = L2 ?

Is the above problem decidable or undecidable ?

If L1 = L2 then L1 $\cap$ L2' = $\phi$

So the above problem can be written as

CFL $\cap$ RL = $\phi$ or CFL = $\phi$ which is decidable.

So the answer should be decidable according to me but my professor marked it wrong saying it's undecidable

Where am I going wrong ?


texts:
What is the lower bound for finding the third largest in a set of $n$ distinct elements?

For the case of finding the second largest, we have the tight lower bound of $n + \lceil \lg n \rceil -2$. The adversary argument can be found in this lecture, which also provides an optimal algorithm using the "Tournament Method".

Edit (04-04-2017): Removing the algorithm for finding the third largest element which turns out to be wrong.


texts: $k$-way merge but without an absolute order

texts:
I have $k$ lists that I would like to combine to a single list. Each list's elements are unique and are sorted in a particular order, but there is no notion of an absolute order, and different items across lists can only be compared if they are equal. To give a specific example (here I use $<$ to indicate the sorting inside each list):

l1 = a < b < c
l2 = b < d

l1 + l2 should result in one of the following (and I don't care which one it results in):

a < b < c < d
a < b < d < c

If the lists are incompatible, e.g. a < b and b < a then I want to get an error. The resulting list (if it exists) should respect all of the orderings of the sublists. Also all the items should be unique in the result.

I thought about modifying k-way merge somehow but it's not clear to me how to do that without a global order. By the way, I'll probably be happy with a $O(nk)$ solution.

Perhaps a better way to phrase the problem is this. I'd like to construct an order vector given $k$ pieces of that order vector (or get an error if that's impossible).

Here's an algorithm that I think works for $k=2$. Find and mark all the duplicates - I think this is $O(n)$ - then start writing down elements from first list until you hit a duplicate, once you do add all elements from second list until you hit that same duplicate, then write down the duplicate and continue. The part where it's a bit more tricky with $k>2$ is that the duplicate may not be in every list to do the above (and this process cannot be done sequentially, i.e. l1+l2+l3 is generally not the same as (l1+l2)+l3, where + denotes this operation of finding the superset order list).

It should be easy to extend the above to any $k$. Use a hash to find which lists each unique element belongs to. Then traverse along the first list using the above logic - writing down all elements until you hit first duplicate, in which case write down all elements (that haven't been written down yet) in all other lists before that duplicate and keep doing that until you reach the end of first list. If haven't reached the end of second list, continue same algorithm there and so on. Each list will be traversed twice - once to get the duplicates, and second time to do the above, making it $O(n)$. A compatibility error will be discovered if you iterate along a list but can't find the duplicate (because it was already written down in an earlier pass).


texts: Efficient data structure for storing integers in a range?

texts:
Say I'm constantly given integers from the range $[1,2^{32}]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ values will have been treated.

What's the best way to store which integers have been treated so far so that we can search if the current integer is a duplicate?


texts: Can all NP-complete cryptosystems be broken if one is broken?

texts:
I was just reading something about NP-hard problems and cryptosystems.

I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) optimisation problem. A successful attack on one such NP-hard cryptosystem $A$ would mean that every other NP-hard cryptosystem $B$ would be vulnerable to that same attack; just reduce $B$ to $A$ and use the available attack.

That would actually mean that we would be able to extend Information Set Decoding attack of Code-based systems to any NP-hard based cryptosystem.

Is this consideration correct?


texts:
Consider I have the following recurrence

$$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\,.$$

Now, by the master theorem, if we evaluate $n^{\log_{b}{a}}$, we get $n^{\log_{b}{a}} = n^{\log_{3}{10}} = n^{2.095}$. Now, can anyone please explain me, which of the three cases apply? If you plot these functions you can see that $n^2\log^5 n$ clearly dominates. So, the answer should be $\Theta(n^2\log^5n)$.

However, if you try plugging in values in this calculator, you see that the answer is $\Theta(n^{\log_{3}{10}})$. Does anyone have a formal reason? I am still confused as to which of these conditions apply.


texts: Algorithm to determine paths that define shape of connected rectangles

texts:
Say you have a bunch of rectangles like these:

They get organized into 3 distinct final shapes like this:

As you can see, there are a few "complete contours", as in here:

The way you figure out the contour of the thing is by visually going around the edge of the final shape, sort of like this:

The question is, given that you start with a set of arbitrarily sized curves, in this case, rectangles (assume they were drawn as real rectangles), how to efficiently/effectively figure out what the final paths are on the final set of shapes. So in the pink drawing, there are 4 paths that define the whole system. I am having a hard time imagining how you would formulate this as perhaps a graph theory problem or something in order to iterate through a list of rectangles, determine their "connectivity", then create some sort of mental sketch of the "perimeter". It seems like it would get complicated fast.

Wondering if there are any areas of research that delve into this stuff, or if there is a straightforward solution to the problem.


texts: How exactly does on describe the formal semantics of the Applied $\pi$-Calculus?

texts:
In "Mobile Values, New Names, and Secure Communication", Abadí and Fournet describe thet Applied-$\pi$-Calculus. Although I understood a great part of the description of the Applied $\pi$-Calculus, I'm still a bit confused as to what exactly its formal semantics consists of.

The authors define (on page 2):

  A signature $\Sigma$ consists of a finite set of function symbols, such as f, encrypt, and pairm each with an arity.

On page 3, they say that

  Given a signature $\Sigma$, we equip it with an equational theory, that is, with an equivalence relation on terms that is closed under substitution of terms for variables.

Then they proceed, still on page 3, to define Structural equivalence, which also is an equivalence relation, but defined on extended processes and not terms.

So after reading the paper a number of times and consulting some other resources on the Internet, I have concluded that the semantics of the $\pi$-Calculus depends on a given signature (and hence is "parametrized" in a sense); and that it is composed of:

the signature and its equational theory, which is provided by us, depending on the application context (I may include symmetric cryptography functions and some equations modeling their behavior, and no asymmetric constructions at all, for example);
the structural equivalence relation for processes;
the internal reduction relation (structural semantics used for plain processes);
the reduction relation including interaction with the environment.

Is this correct, or did I miss anything?


texts: Does regret change when the loss function is dependent on the previous predictions?

texts:
The loss function of each expert in the expert advice problem(or any online learning problem) depends on the time($t$)  and expert advice at that time($f_{t}(i)$).
suppose in this problem, loss function depends on the previous prediction of the algorithm.
$$ l _{t} (i) = p_{1} p_{2} \cdots p_{t-1}f_{t}(i)$$
such that $p$ show prediction of algorithm.
Does the upper bound of regret change?


texts: Contraction Hierarchies minimal distance proof

texts:
I am trying to implement "Contraction Hierarchies" algorithm and reading the white paper and watching video lectures [6,7]. But still I can't understand proof for the following lemma:

Lemma 1. $d(s, t) = min(d(s, v) + d(v, t) : v $ is settled in both
searches $)$.
Proof. We only give a proof outline for self-containedness
since the CH-query is a special case of the HNR-query for which a
detailed yet simple correctness proof is given in [4]. In particular,
here we only consider the case where shortest paths are unique.
Let $v$ denote the largest node on the shortest path $P$ from $s$ to $t$. We first claim that the sequence of prefix maxima of $P$ forms the shortest path from $s$ to $v$ in the upward graph $G↑$. If $s = v$ there is nothing to prove. Otherwise, consider any pair $(u, w)$ of subsequent prefix maxima in $P$ and the overlay graph $G′ = (u..n, E′)$ existing at some point during contraction. Since the shortest path from $u$ to $w$ uses only interior nodes smaller than $u$, and by definition of the properties of an overlay graph, $(u, w) ∈ E′$ and $c(u, w) = d(u, w)$. Moreover, $u < w$ and hence $(u,w) ∈ G↑$. Analogously, the sequence of suffix maxima of $P$ forms the shortest path from $v$ to $t$ in the downward graph.
[4]  Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Demetrescu, C. (ed.)
WEA 2007. LNCS, vol. 4525, pp. 66–79. Springer, Heidelberg (2007)

What I currently understood: There is a path $P$ from $s$ to $t$ and there is a node $v$ in it, with the highest importance order. The path from $s$ to $v$ consists from the prefix maxima, i.e. $s = v_0 \to v_1 \to v_2, ... , v_k = v$. Where $v_i-1 < v_i$ and $v_{i-1} \to v_i$ uses only nodes $< v_{i-1}$:

The rest of the proof is unclear. Mostly the overlay graph $G'$


texts:
Let $L$ be the set of strings of length $n$ (say $n=400$, for example). Let $N = \{0,1,\dots,|L|-1\}$. I am looking for a function $f : N \to L$ with the following properties:

$f$ is efficiently computable
$f$ is a bijection
$f$ is pseudorandom (not necessarily cryptographically)
Given some interval $[a,b]$ and a regular expression $r$, we can efficiently test if there exists $n \in N \cap[a,b]$ such that $f(n)$ satisfies $r$.

Does such a $f$ exist?

The tricky part is finding a function that satisfies both the second and fourth requirement.

One thought I had was to define $f(x) = c + px \pmod{|L|}$ for some constant $c$ and prime $p$. This satisfies the first three properties, but I don't think its regex searchable.

(The motivation is that such a $f$ would amount to a searchable library of Babel.)


texts: How to enforce synchronization with two semaphores

texts:
Assume I have 4 threads, A B C D respectively.
A finishes before B starts.
B finishes before C or D start.
How should I initial values and synchronize threads with 2 semaphores?


texts:
Let $L$ be any language on a nonempty alphabet. Show that $L$ and $\overline L$ cannot be both finite.

This is exercise 7 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz.
My attempt: $L$ is a subset of $\Sigma^*$, so it can be either finite or infinite. If $L$ is finite, then $\overline L$ is infinite. If $L$ is infinite, that is, $L = \Sigma^*$, then $\overline L = \Sigma^* - L = \Sigma^* - \Sigma^* = \emptyset$. Therefore, $L$ and $\overline L$ cannot be both finite.
Is it correct? I tried to write a direct proof. Thanks in advance.


texts: top-N recommendation in collaborative filtering

texts: I have started to read about user-based and item-based collaborative filtering techniques. I understand how a rating of the target user for a particular item is predicted. How top-N recommendation list is created in user-based/item-based collaborative filtering??


texts: Finding an element in an unsorted array equal to its rank in $O(n)$ time

texts:
I'm trying to figure out a way to think about this problem. Background: Given an unsorted array of distinct integers (can be positive or negative), I want to determine if there is an element in the array that is equal to its rank (i.e. if I do $S = Sort(Array)$, I want to find an element s.t. $S[i] = i$).

Some approaches I have thought about.

Radix sort: But there's no guarantee on what is the largest/smallest element here
Any comparison based sorting method: But that gets me at least $O(n \lg n)$ time.

So it seems that I am not supposed to sort before I figure out what the ranks of the elements in the array are. I also feel that it needs to be a selection type algorithm, but I am not sure how that can be applied here. Any ideas on where to go from here?


texts:
In his lectures on computer science, Feynman talks about finite state machines:

he present a simple delay finite state machine

  Let me now give a specific example of an FSM that actually does
  something, albeit something pretty trivial - a delay machine. You feed
  it a stimulus and, after a pause, it responds with the same stimulus.
  That's all it does. Figure 3.4 shows the "state diagram" of such a
  delay machine.

I just don't see the utility of using two states here, why not just use a machine with one state?


texts: Precise relation between complexity classes(focus on P, NP and EXPTIME)

texts:
I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes.

What I know so far:

$P \subseteq EXP$ (from Time Hierarchy Theorem [1])
We don't know an exact relation between $P$ and $NP$, and between $NP$ and $EXPTIME$. What do we know:

2.1 $\forall problem \in P \Rightarrow problem \in NP$ (Any problem in $P$ is in $NP$.)

2.2 $\forall problem \in P \Rightarrow problem \in EXPTIME$ (Any problem in $P$ is in $EXPTIME$.)
In $P$ vs $NP$:

3.1 We haven't found an $ NP $ $complete$  $problem $ that we can solve in polynomial time (this would imply $P = NP$)

3.2 We haven't found a proof that states that we can't find an polynomial (running time) algorithm for an $NP$ $complete$ $problem$ (this would imply $P \neq NP$)

3.3 From 3.1 and 3.2 we can't state anything about the cardinality of $NP-P$. Most of scientists belive that $P \neq NP$ so there are $NP$ problems that we can't solve in polynomial time.

First, if you find and "hole" in what is stated above, please correct me.

Now for my questions:

A. What can we say about $NP$ vs $EXPTIME$? Are there $EXPTIME$ $complete$ problems not in $NP$? For me it sounds like the $P$ vs $NP$ problem just one "level" (in the hierarchy) higher.

B. How does one go about finding a proof like in 3.2? Obviously we haven't found such a proof but I am looking to understand. The first idea that comes to mind is to go with a proof by contradiction. Not finding such a proof doesn't say much (maybe we are not "smart" enough). What else could we try? The problem reduces, in my opinion, to proving that an algorithm in "elegant" (in running time; that means that it is "the fastests")

Kind of bonus question:

C. How does this relate to Godel's incompleteness theorem? Maybe the better question (quite outside of the scope of the original question) is how much of the math we use on answering these questions can be considered a formal system(so we can apply Godel's result)? What parts are not "formal"?

D. I wasn't able (yet) to look very far into [1]. If possible, can someone give me an informal insight on how it handles defining a strict lower (time) bound for a certain problem?

[1]https://en.wikipedia.org/wiki/Time_hierarchy_theorem


texts: Solve a recurrence by drawing the recursion tree?

texts:
I'm studying for an entrance exam and I have sample questions. One of the questions is this

  Prove that recurrence $T(n) = T(n/5) + T(4n/5)+n/2$
  has a solution $T(n) = \omega(n \log n)$.

  Solve by drawing the recursion tree.

This is what I drew on my paper:

root:  n/2 => (4n/5)/2

           => (n/5)/2

right sub tree:  (4n/5)/2 => (16n/25)/2

                          => (4n/25)/2

left sub tree:   (n/5)/2  => (4n/25)/2

                          => (n/25)/2

From what I saw online when I was searching for a solution to this question I noticed people were drawing the trees and saying Big O something as an answer. I'm wondering how do they determine that Big O notation is the correct answer for this question or if my tree is correct?


texts: Starvation Condition in CPU/Process Scheduling?

texts: Let's say OS is using preemptive CPU scheduling. A process P1 gets a chance to run for some time and then next higher priority process comes and preempts P1. After that higher priority processes are coming regularly and P1 never gets chance. Is this condition called starvation or not?


texts:
I have written an algorithm for sorting that I thought of, and I'm not sure if it exists.  Basically, it runs through each index of an array and if the value of index n > the value of the index n+1, they get swapped.  My java code is below.

Here is the example of it running on an array of length 4.

(Given) [3,2,7,5]
(Step 1 [first loop]) [2,3,7,5]
(Step 1 [second iteration]) [2,3,7,5] (3<7, so no change)
(Step 1 [third iteration]) [2,3,5,7]
Sorted array detected, stopped.

This is my Java.

  public static int length = 10;
public static int[] data = new int[10];
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    // TODO Auto-generated method stub

    data[0] = 1;
    data[1] = 10;
    data[2] = 5;
    data[3] = 11;
    data[4] = 9;
    data[5] = 2;
    data[6] = 7;
    data[7] = 9;
    data[8] = 8;
    data[9] = 10;
    printstar();
    System.out.println();
    while(inOrder()){
        exchange();
        printstar();
    }

}

public static void exchange(){
    int temp = 0;
    for(int i=0;i<length-1;i++){
        if(data[i] > data[i+1]){
            temp = data[i+1];
            data[i+1] = data[i];
            data[i] = temp;
        }
    }
}

public static boolean inOrder(){
    for(int i = 0; i<length-1;i++){
        if(data[i] > data[i+1]){
            return true;
        }
    }
    return false;
}

public static void printstar(){
    for (int i =0; i < length; i++){
        System.out.print(data[i]+ " ");
    }
    System.out.println();
}

To clarify, printstar() prints the array.  inOrder() returns true if the array is not in order.  Returns false if it is in order.  exchange() changes the values.

In summary, has a swapping algorithm like this been used before?


texts: Did Date and Darwen's "Third Manifesto" have a lasting impact?

texts:
In 1995, two DB theory researchers, C.J. Date and H. Darwen, published a text with the rather impressive-sounding name "The Third Manifesto" with their ideas regarding future DBMSes, which would better harmonize a relational model with object-oriented programming, including user-defined types.

It is my understanding that object-relational DBMSes has been mostly/entirely abandoned as a subject of research. So, has this manifesto had a significant impact on the DBMS world community over the past 23 years? If so, what are the salient aspects of this impact?


texts:
Lets consider the following language : $L = \{1w |w \in \Sigma^*\}$ (Alphabet is 0 and 1).

I know this language is regular, I just have to prove it now, the Problem here is the number of equivalence classes, I thought it would be:
$[1] = \{x|x $ starts with 1$\}$ and $[\epsilon] = \{x| x$ doesn't start 1$\}$.
But now I am dubious, isn't it possible for L to have 3 equivalence classes one containing words that start with 1 and one class that has epsilon as its only element?

Thanks in advance


texts:
We are given the following language

B = {$<M,i>$ : M is a turing machine and $i \in \mathcal{N}$ and M accepts some string in atmost $i$ steps }

Is language B decidable ?

As per a hint from another fellow user, I decided to construct the following decider for B. Call it D.

D = On input

Enumerate all the strings in $\Sigma^*$ in lexicographical order (shortlex). Let the generated sequence be $s_1,s_2,...$ where each $s_k$ denotes all strings of lenght $k$
Simulate each string in $s_k$ on M for atmost i steps.
If any of them is accepted, ACCEPT.
When we have finished evaluating strings for length $s_i$, output REJECT.

Is this the correct decider for B ?