texts: Lock-free, constant update-time concurrent tree data-structures?

texts:
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.

I have researched various different methods of getting update times down to $\mathcal{O}(1)$ worst-case update time [1-7].

Recently I begun looking into lock-free data-structures, to support efficient concurrent access.

Have any of these worst-case $\mathcal{O}(1)$ update-time techniques been used in the implementation of lock-free data structures?

I ask because; to me, they seem like the obvious practical extension of this "theoretical enhancement".

Tarjan, Robert Endre. “Updating a Balanced Search Tree in O(1) Rotations.” Information Processing Letters 16, no. 5 (1983): 253 – 257.
Driscoll, J R, N Sarnak, D D Sleator, and R E Tarjan. “Making Data Structures Persistent.” In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 109–121. STOC  ’86. New York, NY, USA: ACM, 1986.
Levcopoulos, C., and Mark H. Overmars. “A Balanced Search Tree with O(1) Worst Case Update Time.” Acta Inf. 26, no. 3 (November 1988): 269–277.
Fleischer, Rudolf. A Simple Balanced Search Tree With O(1) Worst-Case Update Time
Dietz, Paul F, and Rajeev Raman. “A Constant Update Time Finger Search Tree.” Information Processing Letters 52, no. 3 (1994): 147 – 154.
Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas, and Kostas Tsichlas. “New Dynamic Balanced Search Trees with Worst-case Constant Update Time.” J. Autom. Lang. Comb. 8, no. 4 (July 2003): 607–632.
Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas. “Optimal Finger Search Trees in the Pointer Machine.” J. Comput. Syst. Sci. 67, no. 2 (September 2003): 381–418.


texts: Regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$

texts:
Design a regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$

So basically we have the language $L=\{11,011,110,0011,1100\ldots\}$.
I find the expression to be $R=(0+1)^*11(0+1)^*$.
But I found here the answer to be $R=(0 + 10)^*(11 + \epsilon)(0 + 10)^*$.
I cannot differentiate these two answers and the logic behind the later answer.
EDIT: In my answer, the first $(0+1)^*$ may provide $11$, so after this another $11$ is not permissible since at most one pair of $11$ is required. But what's the logic behind $(11+\epsilon)$?


texts: procedures and immutable data to simulate return values

texts:
Let's say I have a programming language that allows procedures, i.e., methods without return values, and immutable data-structures, so no sideeffecting inside a procedure. Is it possible to simulate a program written in a language with return values in our language?

In other words, do return values allow for a more advanced model of computation? I guess it may be possible with Continuation-passing style, but i would appreciate other thoughts on this.


texts: k-means clustered data: how to label newly incoming data

texts:
I have a data set with labels that were produced by a $k$-means clustering
algorithm. Now there is some data (with the same data structure) from another
source and I wonder what is the most sensible way to label this new, yet unseen
data? I was thinking about either

calculating the distance to the prior $k$-means centroids and label the data to the the nearest centroids accordingly
run a new algorithm (e.g. SVM) on the new data using the old data as the training set

Unfortunately, I couldn't find anything about this particular problem. There are
only a few questions about the general use of $k$-means as a classification model:

Can $k$-means clustering do classification?
How to segment new data with existing $k$-means model?


texts: Comparing asymptotic complexity of functions $\log{n}$, $(\log{n})^c$ and $\sqrt{n}$

texts:
I usually follow approach of taking logs and putting arbitrary large powers of $2$ for $n$ and reducing the given function to some constant value for large value of $n$. So in this case I did it as follows:

$\log{n}$

Putting $n=2^{2^{2^{16}}}$ and taking $\log$

$\log{\log(2^{2^{2^{16}}})}={2^{16}}$

$(\log{n})^c$

Putting $n=2^{2^{2^{16}}}$, $c=2$ and taking $\log$

$\log({(\log{2^{2^{2^{16}}}})^2})=\log({2\times(\log{2^{2^{2^{16}}}})})=\log({2\times(2^{2^{16}})})=\log{2}\times\log{2^{2^{16}}}$

$=1+2^{16}$

$\sqrt{n}$

Putting $n=2^{2^{2^{16}}}$ and taking $\log$

$\log{\sqrt{2^{2^{2^{16}}}}}=\log{2^{2^{2^{{16}^{\frac{1}{2}}}}}}=\log{2^{2^{2^8}}}=2^{2^8}=2^{16}$

So it looks like:

$\log{n}=\sqrt{n}<(\log {n})^c$

However I checked that $\log{8}>\sqrt{8}$. But, $\log{(2^{2^{2^{16}}})}=64$, whereas $\sqrt{2^{2^{2^{16}}}}$ is much larger number making equality between the two unlikely.

So where I am making mistakes in above calculations?
How above three functions compare asymptotically?


texts: Is there a data structure to represent changes to a DAG over time, with fast reproduction of instances of the DAG?

texts:
Consider a directed acyclic graph (DAG) of topics and links.  Apart from the root topic, topics are situated under one or more parent topics, and links, as well, are situated under one or more parent topics.  Now imagine that the DAG changes over time as users add, remove and update link and topic relationships and metadata (name, title, etc.).
Is there a data structure that can capture this dimension of changes to the DAG over time, readily reproducing a version of the DAG at a specific point in time?  This would be analogous to resetting Git to a previous HEAD.  Unlike Git, however, in which mutations are made to the file system in order to get to another point in time, ideally a single copy of our data structure could allow multiple viewers to access it, without one viewer affecting others' views of it (they could each have different pointers into it, though).  Also unlike Git, we can make do with a linear sequence of versions instead of needing a tree of versions.  Also unlike Git, we are recovering a DAG rather than a tree (i.e., the file system without hard links).
Perhaps, but not necessarily, the data structure would be a graph of some kind that incorporates the DAG at each point in time in a complex way, which in a sense would make it a super-DAG.  Do people know of anything along these lines?


texts: How to detect plurals in English sentences?

texts:
I'm wondering how to detect English plurals in natural language sentences.

Such as:

fish
computers
houses
...

Using Earley parsing I'm able to get to the s or no-s, but I have difficulties in understanding how to figure out whether the ending s is because the word is in plural form. Or whether with no-s the word is in plural form.

Is this kind of thing doable without some database of words and their plurals? I could leverage such database though, if such exists.


texts: what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA?

texts:
I saw this term "Glushkov NFA" at http://lambda-the-ultimate.org/node/2064 . Search engines are returning references to articles that use glushkov nfa, but nothing specific about the glushkov nfa itself.

What is Glushkov NFA? How different is it from the NFA created from Thompson Construction?


texts: Can CYK Parsing algorithm generate the parsing tree in O(n^3)?

texts:
I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free Grammar in $O(n^3)$.

But this does not make sense because I cannot see how NonDeterministic Context Free grammar can be parsed in $O(n^3)$. Then, while reading Hopcroft and Ullman (2006) pages 304 I found:

  In $O(n^3)$ time the algorithm constructs a table that tells whether w is in L $\in$ Note that when computing this running time the grammar itself is considered fixed and its size contributes only a constant factor to the running time which is measured in terms of the length of the string w whose membership in L is being tested.

So, the correct affirmation is: There is no way a NonDeterministic Context Free Grammar parsing tree can be built in $O(n^3)$ time, only its word membership can be determined in $O(n^3)$ time by the CYK algorithm. NonDeterministic Context-Free Grammars Parsing Trees can only be built in Exponential Time (worst case)?

Related:

Chomsky Hierarchy and P vs NP
What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?


texts: Understanding the reduction of REGULARTM from ATM

texts:
REGULARTM is defined as below:

REGULARTM ={〈M〉| M is a TM and L(M)is a regular language}.

I am trying to understand the proof of REGULARTM being undecidable from Sipser's book "Introduction to the Theory of Computation". The book says:

We let R to be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following manner.
S = “On input〈M,w〉, where M is a TM and w is a string:

1.Construct the following TM M2.

    M2=“On input x:
        1.If x has the form 0^n1^n,accept.
        2.If x does not have this form, run M on input w and accept if M.”
2.Run R on input〈M2〉.
3.If R accepts,accept; if R rejects,reject.”

The problem that I am facing is in the 2nd substep of the 1st step which says:

If x does not have this form, run M on input w and accept if M.

What if M does not halt on w? Then the decider S that we are building would not halt.


texts: Difference b/w a drawn 2d path and a sample

texts:
Background: I'm working on an application which is supposed to teach users how to write Japanese kanji. Each kanji is represented as an array of strokes. Each stroke is an array of 2d points.

Strokes (2d paths) are supposed to be drawn in certain order, so my question is limited to recognizing similarity b/w single drawn and sample paths. I don't need to search paths by their shape or anything like that, I just want to tell if a drawn path is "close" to a sample.

I also want to specify "accuracy" of drawing with these parameters:

Distance - each stroke has a specific location in a kanji, but little offset is allowed.
Angle - each stroke should be drawn in a specific direction. If it has a proper shape, but drawn backwards, that's an error. Ideally, I want to notify a user that (s)he draws a shape correct, but backwards. I might just run an algorithm a second time for reversed stroke just to tell that.
Scale - little variation is allowed, especially for tiny strokes
Shape - generally, strokes are simple, but some of them can have up to 3-4 "turns", and segments b/w those turns can be straight or curved. You can look at the list of radicals to see how much details there are. However, I don't need an extra precision, since users will draw strokes using mouse or touch screen, so drawn paths might have pretty major deformations. I just want to be able to distinguish shapes like "V", "N", and "W".

I've tried to use DTW, but it only works good for measuring distance, and fails to find major differences in shape - e.g., if I draw "N" shape and only draw first two segments ("|" and "\" connected), the result of calculating DTW distance can be OK with an error threshold I set, but the shape is obviously wrong, and DTW can't tell that.

I also tried to check angle with DTW, semi-successfully, and then gave up after I realized that this can't be used to deal with shapes. I saw DTW used in similar applications, and all of those suffer from telling that the long 2nd stroke in "え" is always wrong, and/or failing to tell the difference b/w vertical line and a "hook", which makes those apps either useless (any stroke goes) or unusable (can't get it right no matter how accurate you are).

Next, I found shape context algorithm, but I think it is not applicable to my task:

It uses thin plate splines model, which does not preserve straight lines, which is desired. I know I can use affine transformations instead, but then I don't know how to impose limitations on that transformation. As I stated above, I want to limit differences in position, rotation, and scale.
In my task, sample points from drawn and sample strokes are already "matched" to each other, 1-to-1, because I can just take N points from drawn stroke with equal steps, and match them to N points from sample stroke. So, initial steps of this algorithm are not even needed.
I believe that in my task it is not ideal to use log-polar histograms as point descriptors. Instead, I can just use an array of N-1 vectors from current point to other points as a reach descriptor of each point.

Yet, this algorithm looks very promising for shape matching. Maybe there is something similar which is applicable to my task. I couldn't find anything better yet, so even the name of an algorithm would be very nice.


texts: Why can't OS's keep audio and video recording in sync?

texts:
It seems every program that purports to record webcams fails to keep audio and video in sync.  Moreover, there are probably man millenia being spent by people trying to correct for this during editing.

While it is understandable that OS's may have to buffer incoming raw audio and video prior to compression, if necessary taking gigabytes of RAM, it is less understandable that they can't keep the two in sync during recording.

This points to an architectural flaw in common with the major OSs.  What is the problem?


texts: Find plane within margin of error of >50% of points

texts:
There are $N < 3\times10^4$ 3D points. At least 50% of them lie approximately in the same plane, i.e. the distance between the plane and each point is at most $p$. Find such a plane.

Attempt: since the number of points in the plane is at least 50%, we can randomly sample 3 points from the set. They will all be in the plane with probability 12.5%. We build a plane through these 3 points and check that at least 50% of points lie approximately in it. Within 10-20 samples we'll find the plane.

Problem: because of the margin of error there's not just one plane going through 3 points, but many possible planes. How do we examine all of them?

How would you tackle this problem?


texts: Problems with the proof of Huffman Optimality in Cover's book

texts:
There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me.

First question is why he assumes that we can "Consider an optimal code $C_m$. Is he assuming that we are encoding a finite number of words so that
$\sum p_i l_i$ must have a minimum value? Here I give you the relevant snapshot.

Second, there is an observation made on this notes that was also done in my class before proving the theory of optimality of huffman codes, that is,

  observe that earlier results allow us to restrict our attention to
  instantaneously decodeable codes

I don't really understand why this observation is necessary.


texts: Efficient way to count number of intersections of line segments

texts:
On my computer science course's exam I was given the following task:
You are given $n$ segments that lies on the same line: $i$-th segment starts at coordinate $from_i$ and ends at $to_i$. Your task is for each segment count number of other segments that intersects it.
EXAMPLE INPUT:
5
7 8
8 9
0 3
2 7
10 15
EXAMPLE OUTPUT:
2 1 1 2 0
I've implemented the naive algorithm:
def count_intersections(i):
    counter = 0
    for j in range(len(data)):
        if i != j:
            if data[i][0] <= data[j][0]:
                left = data[i]
                right = data[j]
            else:
                left = data[j]
                right = data[i]

            if right[0] <= left[1] <= right[1]:
                counter += 1
            elif left[0] <= right[0] <= left[1]:
                counter += 1

    return counter

n = int(input())
data = []
for i in range(n):
    data.append(tuple(map(int, input().split())))

for i in range(n):
    print(count_intersections(i), end = ' ')

As you can see, I just iterate through eacher other segment and increment counter if it intersect the given one. Time complexity of my solution is $O(n^2)$. And because of this I got Tme Limit Error.
Do you know more efficient solution? Maybe some extraordinal Data Structure?


texts: How can somebody use these gates to create other gates like pauli's or other gates? Also how can somebody go from pauli's to CNOT, Hadamard and Φ quantum gates?


texts: Evaluate run time and compare these algorithms

texts:
Algorithm A divides the problem into 5 sub-problems of half the size. Solving each sub-problem then combining the solutions in linear time.

Algorithm B solves problems of size n by dividing them into 9 sub-problems of size n/3, and recursively solving each sub-problem then combines solutions in 26*n^2 time.

Algorithm C solves problems of size n by recursively solving two sub-problems of size n-1 then combines the solutions in constant time.

Questions:

What method would you use to compare these algorithms? Show how to apply said method.

What are the running times of each? which would you chose? Explain

When implemented, the algorithms may not perform as you ranked them for small input sizes, why can this be the case?

I know the following:

I think for A the recurrence recurrence relation is given by T(n) = 5T(n/2)+O(n) But is this what he means by what method I would use? and what does that make the running time of it?


texts: Implementing the Schur decomposition of a matrix

texts: I'm trying do implement the Schur decomposition of a matrix, but I can't find any good articles for the theory. Could someone share one?


texts: Is unconstrained quadratic programming NP-hard?

texts: I could not find the answer on the Internet. The case of  quadratic programming with constraints is already solved on this forum, see Transforming SAT to Quadratic Programming in polynomial time. But what happens if there are no constraints or if the only acceptable constraint is that the variables are non-negative?


texts:
I have a clue as to how this code/traversals work but I'm still confused.

For example, in the first traversal (Preorder), it prints 31, 12, 25 but then it backtracks all the way to 68? How does it know to do this? My professor referenced a stack but I am still a bit confused.

As for the other codes, I don't know how to backtrack on them at all. I understand the first one quite a bit but for the next 2, not so much.


texts: How does knowing the input size make the time complexity of a function constant?

texts:
After reading the question and answers on Time complexity of min() and max()? I would like to clear up some confusion on the relation between time complexity and size of input.
First, I've noticed most of the time people omit what exactly n represents in big O notation. Usually it's related to the input, but it may be the value or length in bits or something else. Am I right that it's usually inferred from context?
When is a function O(1) vs O(n)? I had thought that only functions that do not depend on the input would be O(1) for example
foo()
{
  return "bar"
}

Or accessing certain data structures like an array arr[0] or a map would have operations of O(1). But in the linked question some answers stated this is only true if the size is known. What difference does this make? Even if the size is known, some operations may take O(n). For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed. So why do some people say knowing the size makes it constant time?


texts: How to find out if a piecewise function is partially computable?

texts:
I know exactly what a partially computable function is, but I've seen a few functions that I really can not understand why they are not partially computable. As an example in Davis book page 78, he says the following function is not partially computable: ($\uparrow$ means undefined and $\downarrow$ means defined)

Given an infinite set C such that $\phi(c,c) \uparrow$ for all $c \in C$ and such that

  $$
H_4(x) =
\begin{cases}
1 & IF \phi (x,x) \downarrow \\
0 & x \in C \\
\uparrow & Otherwise \\
\end{cases}
$$

is not partially computable.

Or in page 77 he says the following is partially computable while I cannot understand what is difference between these two functions!

Given an infinite set B such that $\phi(b,b) \uparrow$ for all $b \in B$ and such that

  $$
H_3(x) =
\begin{cases}
1 & IF \phi (x,x) \downarrow \\
0 & x \in B \\
\uparrow & Otherwise \\
\end{cases}
$$

Or between these two functions which one is partially computable? ($K=\{ n \in N | \phi(n,n) \downarrow \}$)

  $$
f_1(x) =
\begin{cases}
2 & x \in K \\
\uparrow & Otherwise \\
\end{cases}
$$

  $$
f_2(x) =
\begin{cases}
\uparrow & x \in K \\
2 & Otherwise \\
\end{cases}
$$

So I would like to know what makes a piecewise function to be partially computable?

UPDATE:

Since $K$ is recursively enumerable (in face m-complete), it is not recursive so checking membership in this set is semi decidable. I guess $f_2(x)$ should be partially computable but I'm not sure!


texts:
For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation of what a fractional matching is. How does it compare to an integral matching?

If this question seems too basic, could I please have a link to somewhere that explains it?


texts: Does there exist a problem for which no existing solution can be parallelized on a Turing machine?

texts:
I'm asking for problems for which we know there exists a solution for which an equivalent parallel program cannot be written on a Turing machine.
Alternatively, have we proven the opposite to be true - that for every problem, there exists at least one parallelizable solution?


texts: Undirected graph with 12 edges and 6 vertices

texts:
For school we have to make an assignment, and part of the assignment is this question:

  Describe an unidrected graph that has 12 edges and at least 6
  vertices. 6 of the vertices have to have degree exactly 3, all other
  vertices have to have degree less than 2. Use as few vertices as
  possible.

The best solution I came up with is the following one. Here the number in the circles is the degree of that vertex, now I was wondering if there is a better solution, if so, can somebody explain this to me?

I do not need a better answer, just a push in the right direction - if needed.


texts: Algorithm for solving a mixed integer programming problem in polynomial time?

texts:
I have the following mixed integer programming (MIP) problem:
$$
\begin{array}{rll}
\text{Maximize } & z=k \\
\text{subject to }
& a_ik - m_i \geq 0 & (i=1,\dots,n) \\
& b_ik - m_i \leq 1 & (i=1,\dots,n) \\
\text{where}
& k \in \mathbb{R}_{\geq 0}, m_i \in \mathbb{N}_0 & (i=1,\dots,n),
\end{array}
$$
where $a_i,b_i$ are non-negative real numbers such that $0 \leq a_1 < b_1 < a_2 < b_2 < \dots < a_n < b_n$ (defining $n$ "forbidden intervals" $(a_i,b_i)$), $k$ is an unknown repetition frequency, and $m_1,\dots,m_n$ are unknown integers (telling how many repetitions will occur before the different intervals).
(Alternatively, the MIP-problem can be rephrased as "Find the minimal $x \in \mathbb{R}_{>0}$ such that $mx\not\in(a_i,b_i)\ \forall\ m\in\mathbb{N},i\in\{1,\dots,n\}$". It is by defining $k=1/x$, and $m_i$ as the largest non-negative integer for which $m_i x \leq a_i$, that the MIP formulation can be obtained.)
I need to either come up with an algorithm to solve this problem in polynomial time, or prove that the problem is NP-hard (or NP-intermediate if not NP-hard, I guess). I have tried to come up with a poly-time algorithm but not been successful, but I don't really know how to prove NP-hardness either.
How can I prove that this problem is NP-hard, or alternatively, is there some algorithm with a polynomial (in terms of the input size, i.e., the size required to store the input in memory) worst-case time complexity that can solve it?
In general, how do one prove NP-hardness? What I understand, for a given problem H, if every problem in NP problem can be reduced H in polynomial time, then H is NP-hard. But how do I prove that this is the case? There has to be close to infinitely many problems in NP, so is it enough to show for one of the problems that are NP-complete that it can be reduced to H in polynomial time? Is there some list of NP-complete problems that I can look at to try to prove that this MIP problem is NP-hard?


texts: Can Hall's theorem be applied to scheduling problems?

texts: If I have a scheduling problem, is it possible that Hall's theorem can be applied? I was thinking that the graph representation of the scheduling problem can be the preferences of the people / workers getting scheduled. Is there any such result or counter-claim?


texts: multiple sequence alignment using HMM and simulated annealing

texts:
Can anyone help me with Multiple Sequence Alignment (MSA) using Hidden Markov Model (HMM) by giving an example or a reference except these 2 references:

1-Eddy, Sea.R., et al.Multiple alignment using hidden markov models, 2-Boer Jonas, Multiple alignment using hidden Markov models, Seminar Hot Topics in Bioinformatics.

I know that there are 3 states: match, deletion and insertion and I know the emission probabilities and transitions probabilities can be learned by viterbi algorithm but what is vague is that if I want to do multiple alignment I need to have HMM and if I want to have HMM I need to have aligned sequences but we know that sequences are unaligned and also with simulated annealing we can Enter randomness to the model and have better solutions and also this algorithm is different with E-M algorithm and I have another question how many states our model of HMM for this problem should have at the first step, does the number of states change during the time of convergence or it is fixed from the first??

If anybody can help me to understand what really happens in this MSA with HMM I'll appreciate.

I should explain that there have been found more sequences of DNA,RNA and protein but there are less information about structures and functions of each protein so we do MSA to understand the similarities between sequences and find out whether they are homologous (have a same ancestor) or not and find out the unknown structure and functions of sequences.


texts: Why are sensors transducers when analogue-to-digital-converters (ADC) do the actual conversion?

texts: As sensors only sense continuous quantities whereas an ADC is a device which actually converts one form of input to another.


texts:
Can you find the function that satisfy the relation?

$$f(n) = \Theta(g(n)), f(n) = o(g(n))$$


texts: quicksort invariant 3 conditions with loop invariant

texts:
in studying Quicksort using the book "Introduction to Algorithms"  by Cormen, Leiserson, Rivest and Stein, they describe in order to show correctness, an invariant must hold for the 3 stages of the loop, the initialization, the maintenance and termination of the loop.

Based on the following algorithm, I don't understand properties 1 and 2 below:

Here is the algorithm I'm referencing:

Might someone help me understand conditions

1) if $p \leq k \leq i$ then $A[k] \leq x$

In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have i = p-1

2) if   $i + 1 \leq k \leq j - 1 $ then $A[k] > x$

In the algorithm for example, when we first enter the for loop, and j = 1, then $i$ would be 0.... I don't see how this works.

Thanks


texts: Confusion about definition of languages accepted by Turing Machine, very basic question

texts:
I'm studying for an upcoming exam and my book gives the following definition:
Let $M$ be a Turing machine, then the accepted language $T(M)$ of $M$ is defined as $T(M) = \{x \in \Sigma^* \mid z_0 x \vdash^* \alpha z \beta; \alpha, \beta \in \Gamma^*; z \in E\}$.
As a side note, $\vdash$ denotes the transition from one configuration of the TM to the next, and the $^*$ denotes an arbitrary number of applications of this relation.
What I'm confused about is that under this definition of acceptance, I only have to enter the end state once and even if I leave it, the word would be accepted, or I could loop in this end state. In push down automata or regular automata, we do not have this problem as we move through the word sequentially from beginning to very end, especially in push down automata where the stack is separated from the input word.
Now I read in most other definitions, additionally to ending up in an end state, the Turing machine must also halt, meaning that it must end in a state that has no transitions. Although I'm not sure what this would mean for deterministic Turing machines as they have to have transitions for all configurations of the machine.
To wrap it up:
Question 1: Is halting required? Is it a useful property for accepting languages or is there a reason the definition was given as is?
Question 2: How would you define "halting" for deterministic Turing machines?


texts: Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged

texts:
Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of $e$
decreases by some positive number, how to prove the the MST is unchanged (still $T$) ?

It seems obvious by Kruskal's algorithm if the weight of all edges are different, if the weights are same, or some of them are same, how to prove it?


texts:
I've stumbled at the first OralMessage algorithm in Lamport, et al's paper.

I've searched the web and there are dozens of sites, restating in exactly the same terms and examples, which isn't helping me.

Lamport claims the algorithm can handle (n-1)/3 traitors, and works when the commander is a traitor.

My restatement of the algorithm:

The commander sends a value to each of the lieutenants.(round 0)
Each lieutenant:
forwards each message he receives to the other lieutenants:
don't forward messages that already have your name          (eg you are b and receive 'cb1')
don't forward messages if they already have (N - 1)/3 names. (eg N=10 and you receive 'gcd0')
add your name to front of message before forwarding         (eg you are b and receive 'c0', send 'bc0')
after all messages have been sent, each lieutenant:
examines the received messages and makes their decision.
if its a tie, then decide 0.

I'm not sure how to do 3, the paper says the algorithm "assumes a sequence of [majority] functions" (nested?)
In the example, I'm assuming to take the majority in each vector of round 2 (ie left to right), and then take the majority of these.

EXAMPLE

Commander is a traitor, N=7, M=(7-1)/3=2, so 6 lieutenants one of whom is a traitor. I have assigned the lieutenants letters b-g.

Here are the messages received at each node in rounds 1 & 2, assuming a node can send to itself. (the messages in brackets are redundant from B's point of view. I don't know if this is important.):

<(b1) ,c0   ,d0   ,eX   ,f1   ,g1   >

<     ,(cb1),(db1),(ebX),(fb1),(gb1)>
<(bc0),     ,dc0  ,ecX  ,fc0  ,gc0  >
<(bd0),cd0  ,     ,edX  ,fd0  ,gd0  >
<(beX),ceX  ,deX  ,     ,feX  ,geX  >
<(bf1),cf1  ,df1  ,efX  ,     ,gf1  >
<(bg1),cg1  ,dg1  ,egX  ,fg1  ,     >

Note:
'dc0' is sent to everyone by 'd' (because 'd' was the last to prepend their name)
'X' indicates an unreliable message. 'e' is a traitor and always sends unreliable messages

BUT 'step 3' gives 1,0,0,X,1,1 which is no better than round 1.
AND the majority of these is 1 if X is 1, and 0 if X is 0. So the traitor can confound us.

What am I doing wrong?


texts: What is the worst case scenario for Dinitz's algorithm?

texts:
The complexity of Dinitz's algorithm (used to find maximum flow in a network) is O(V²E). I am trying to find a network, which is forcing the algorithm to use as much steps as possible.

I was thinking about a complete graph with some smart configuration of capacities, but I am not able find anything, that would seem to be clearly the worst case.

It is a homework for my Algorithms class, please post advices to point me in the right direction, not complete solutions. Thanks a lot!

(Sorry about my English.)


texts: walk / traverse a disjoint set that has union rank and path compression

texts:
I'm studying CLRS section 21.3, which introduces a union rank + path-compressed implementation of disjoint set. The implementations of MAKE-SET, UNION, LINK, and FIND-SET on p 571 of the book all work with nodes themselves, where each node has a parent pointer and rank.
Exercise 4 in that section claims that if you wanted to traverse all the nodes in the set (e.g. to print them) you only need a single extra attribute for each node, and the book claims that you can implement this without sacrificing the asymptotic complexity of union rank + path compression.
The data structure that immediately comes to mind is a circular list with single (not double) links. In this case, the "single extra attribute" the exercise asks for would be the next pointer of each node. We could just maintain that list in parallel with the disjoint-forest + union rank + path-compression.
However, the problem is that when trying to merge two sets, you would also need to merge their circular lists, and for a singly linked circular list, I'm pretty sure you cannot combine them into one without traversing through one of them first. This traversing would certainly destroy the asymptotic efficiency of union rank + path compression here.
Of course, you could slightly augment the circular list by keeping track of both its head and the node before the head, i.e. the tail. However, in order to do this, you can no longer work directly with the nodes, but would need to maintain a circ-list object (one for each set) with head and tail pointers. This would also mean that you can no longer call UNION on two nodes directly, but rather need to maintain a set object that has a pointer to its circ-list object as well as its root. All this seems to be somewhat more than the "exactly one extra attribute for each node`, since you also need O(1) extra attributes for each set.
Is what the exercise asking for actually possible, or do I need to make one of the concessions above?


texts: How to compare A* with DP approach in finding shortest Path?

texts:
Consider a hypercube defined over $n$ dimensions where the edges are associated to strictly positive weights, and nodes are marked with $n$ bit-strings, e.g. the source is marked as (0,0,0) in a 3-dimension hypercube and the farthest node is marked as (1,1,1) (termed as 'target'). Any two neighboring nodes differ by precisely 1 bit.

Task: Find the shortest path from source to target on the given hypercube.

Approaches:
  1) Dynamic programming approach. --- Complexity $O(n2^{n})$
  2) A$^*$ approach.

What are the factors on which these two approaches can be compared apart from run-time and space requirements?

I tried to run an experiment and found A$^*$ discovers 103 different paths (I meant 103 different new entries where added to priority Queue of A$^*$) before reaching the goal state on a weighted hypercube over 5 dimensions. Since the graph had only $2^5 = 32$ nodes, how could I have compared the no of nodes touched by A$^*$ was less than DP approach which covers the whole graph.

Is it correct that efficiency of A* over DP is $103/(5* 2^{5})$ as mentioned in the above example?


texts: Will the future quantum computers use the binary, ternary or quaternary numeral system?

texts:
Our current computers use bits, so they use the binary numeral system. But I heard that the future quantum computers will use qubits instead of simple bits.

Since in the word "qubit" there is the word "bi" I first thought that this meant that quantum computers would use binary (base 2).

But then I heard that qubits had three possible states: 0, 1, or a superposition of 0 and 1. So I then thought that this must mean that they will use ternary (base 3).

But then I saw that one qubit can hold as much information as two bits. So I thought that this maybe mean that they will use quaternary (base 4).

So which numeral system will the future quantum computers use: binary, ternary or quaternary?


texts: Difference between deterministic and nondeterministic universal turing machine

texts:
It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a deterministic UTM can simulate another deterministic TM with running time $t(n)$ in time $ t(n)\log(t(n))$.

My question is: why is there a $\log(t(n))$ slowdown in the simulation of a deterministic TM by a UTM, as opposed to a constant factor slowdown in the nondeterministic case?


texts: Calculating probability of reaching state in DTMC

texts:
Consider a highly-connected graph of states & transitions where each transition is marked with a weight (representing probability of occurring) and the graph satisfies the Discrete Time Markov Chain (DTMC) property: for each state the outflow transition weights are reals (or just rationals, if that makes a difference) in [0,1] which sum to 1, and the transition weights stay constant in time. So a finite state machine where the system moves through the states probabilistically, basically. For example:

Where $a_{0,1} + a_{0,2} = 1$, $a_{1,0} + a_{1,3} = 1$ etc.

Assume we start the system in the state where $x = 0$; what is the probability that the system reaches the state where $x = 3$, and what is the algorithm for determining that probability? From my small knowledge of probability, the algorithm requires summing of the probabilities of all finite paths that eventually reach $x = 3$; for example:

$P[F (x = 3)] = a_{0,1}\cdot a_{1,3} + a_{0,2}\cdot a_{2,3} + a_{0,1}\cdot a_{1,0} \cdot a_{0,1} \cdot a_{1,3} + \ldots$

Since it's possible for the system to loop indefinitely before reaching $x = 3$, this equation includes an infinite sum of infinite products and is beyond my ability to solve. How is something like this calculated?


texts: Concurrent Garbage-Collectiong/Compacting Memory Allocator

texts:
I'm developing an algorithm for concurrent heap garbage collection/compaction. It will be used in low latency systems that need to scale well to a lot of clients, e.g. web servers.
I thought about an algorithm that would be suitable but it does have a few flaws.
I'm not very good at describing algorithms, so please correct me if my description isn't clear, but here it goes:

There are two heaps of equal size
There's an object handle table, which contains memory address and lock of each object.
The index to the handle table is the handle of an object.
Each heap has a linked list of all objects, which contains type and size of the object.
Objects are copied from one heap to another

The GC/compaction algorithm is designed to be incremental and concurrent.
This is the Pseudocode, which runs in all threads from time to time.
Atomic operations are marked with  // atomic.
current = heapFrom->currentCopyObj; // atomic
heapFrom->currentCopyObj = current->Next; // atomic

while(heapTo->currentCopyObj->freeSpaceToNextObj < current->size) // atomic
{
    heapTo->currentCopyObj = heapTo->currentCopyObj->Next; // atomic
}

size = current->Size;
oldAddress = current->Address;
newAddress = heapTo->currentCopyObj->Address;

handleTable->LockObj(current->Handle); // atomic

memcpy(heapTo->currentCopyObj->Address, current->Address, current->Size);

heapTo->InsertIntoObjectList(heapTo->currentCopyObj, current); // atomic
heapFrom->RemoveFromObjectList(current); // atomic

handleTable->SetHandleAddress(current->Handle, newAddress); // atomic

handleTable->UnlockObj(current->Handle); // atomic

Allocation of objects is done using a sort of bump allocator, which allocates objects at the end of each heap, handle allocation is done using an O(1) algorithm, which uses either a bump allocator or cached handle slots.
This should make allocation quite fast, O(1) theoretically.
This algorithm has a few flaws though:

Object writes have to be locking, reads can be concurrent with copying
It does not achieve very good heap compression
High memory overhead due to handle table
Not very cache friendly due to handle table

Would this algorithm work? If it would, how could I solve some of the problems it has?
Or is there a better algorithm that does not have these flaws?


texts: Searching for efficient method to compute $a^n \bmod p$ for large numbers

texts: I need  an efficient algorithm with clear steps to compute $a^n \bmod p$ when $n$ is large enough and $p$ also. I'm looking for something equivalent to the built-in PowerMod function in Mathematica.


texts:
Let $S$ be a sequence of $k$ many numbers. The position of the number in the $S$ matters. In the $S$ there are only $j$ many different numbers are there means $S$ contains many duplicates. Position is a query which needed to be answered, position(i) returns the element at position $i$ in $S$.

Trivial way to store them is using array which will takes $O(S)$ space and position can be solved in $O(1)$ time.

I am looking for a representation that takes $O(j)$ space (or somewhere near to it) and such that position can be solved in $O(1)$(even in more time is also ok)?

Please suggest some papers also.


texts:
In Types and Programming Languages by Pierce,

  ML-style let-polymorphism was ﬁrst described by Milner (1978). A num-
  ber of type reconstruction algorithms have been proposed, notably the clas-
  sic Algorithm W (Damas and Milner) of Damas and Milner (1982; also see
  Lee and Yi, 1998). The main diﬀerence between Algorithm W and the pre-
  sentation in this chapter is that the former is specialized for “pure type
  reconstruction”—assigning principal types to completely untyped lambda-
  terms—while we have mixed type checking and type reconstruction, permit-
  ting terms to include explicit type annotations that may, but need not, contain
  variables. This makes our technical presentation a bit more involved (espe-
  cially the proof of completeness, Theorem 22.3.7, where we must be careful
  to keep the programmer’s type variables separate from the ones introduced
  by the constraint generation rules), but it meshes better with the style of the
  other chapters.

What are the difference and relation between  type checking and type reconstruction?

Does type checking apply only to terms with explicit type annotations which don't contain type variables?

Does type reconstruction apply only to terms either without explicit type annotations, or with explicit type annotations containing type variables?

Thanks.


texts: Multi Knapsack each with different constraints

texts:
It seems that there's no end to knapsack variations… here's the one I bumped into (at work):

There are:

  N items, each with the usual value and weight properties.
  M bins, each with an upper bound and a lower bound on the total weight of the items that can be assigned to it. (That is, the total weight of the items assigned to bin $j=1,\ldots,M$ should be at least $L_j$ and at most $U_j$, for some pre-defined $L_j, U_j$.)

But here comes the main problem:

  Each bin accepts only items from a specific (pre-defined) subset of the N items.

The task is to maximize the overall value with no need to use all the bins (due to the minimum weight).

What do you think ? Is this tractable ? How would you tackle/model and solve it (given the necessity of extracting the "ID"s of the items in each bin) ?

My knowledge in this specific field isn't enough… so, thanks in advance!


texts: Could you explain this signed fixed point number equation?

texts:
How do I interpret this equation?

  Decimal value of signed fixed point number
  $-2^3+2^0+2^{-1}+2^{-2}$
  $$ V = (-1)^{b_{N-1}}\times 2^{N-P-1} + \sum_{i=0}^{N-2}(b_i\times 2^i)\times 2^{-P}\,.$$

$N$ is the number of bits. The point is at a fixed position, $P$ from the right.

Another question: why is it $-2^3$ instead of just a minus sign in front of $2^0$?


texts: Properties of roots of recurrence relations in the context of exponential algorithms in order to decrease the upper bound of the running time

texts:
The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is an excellent book to start learning how to design exact exponential algorithms. In their second chapter, they introduce the recurrence relations in context of a branching algorithm:

$T(n) \leq T(n-t_1) + T(n-t_2) + \dots T(n-t_r)$

To solve this equation we assume $T(n) = c^n$, then $c$ should be a (complex) root of $x^n - x^{n-t_1}-x^{n-t_2}-\dots-x^{n-t_r}=0$ ⇾ the running time of this branching algorithm is thus governed by the largest (real) root of this equation. We call $\tau(t_1,t_2,\dots,t_r)$ the branching factor of these $t_r$ numbers which is thus the largest positive real root of the corresponding equation. The branching vector is defined as $t = (t_1,t_2,\dots,t_r)$

I am mainly interested in editing such branching algorithms in order to reduce the running time. Often, I get in a situation where I can either do:

(1) Remove a branch entirely (i.e. make the number of arguments in the branching factor lower)

(2) Have a choice between two branching vectors, say $x$ and $y$. The branching vectors are equal except for two elements: we have $x_i < y_i$ and $x_j > y_j$ with $i \neq j$. ($x_i$ is thus element at position $i$ of branching vector $x$).

I have two questions:

(1) Intuitively, it seems to me that if I remove a branch entirely, this lowers the running time of the algorithm. We essentially try to find the number of leaves of the branching algorithm; per definition if we remove an entire branch the number of leaves should lower, hence should the running time. However, I can find no such theorem/proof in the literature.

Mathematically, you essentially have a equation of the form $\sum a_i x^{n - c_i} = 0$, where we only care of the largest positive real root. Now if I create the same equation, but now lower one of the $a_i$ values, does my positive real root decrease? I assume this is some fundamental/elementary theorem somewhere but cannot seem to find it.

(2) The book has a Lemma (2.3): $\tau(i,j) \ge \tau(i + \epsilon, j - \epsilon)$ for all $0 \le i \le j$ and all $0 \le \epsilon \le \frac{j-i}{2}$. I cannot use this lemma in most cases of this problem. I am going to assume that I will just have to calculate the roots for each branch, right? And then take the minimum? Or is there some more fundamental theorem to this?


texts: Are fixed-point combinators general recursive?

texts: I don't know if I'm using the vocabulary correctly, but what I'm interested in is this: If your language has fixed-point combinators, is it Turing-complete?


texts: Algorithm to find sequence of minimum moves to sort 13 card hand

texts:
Just for fun I am trying to write a program to sort the 13 cards (from a standard pack of 52) in a Bridge hand by performing human-like moves on the hand.

A sorted bridge hand is arranged by suit, with alternating colors of suit (if possible), and the cards are sorted by decreasing rank within each suit. For example

♣QJ3♥K4♠AQ974♦K76 is a sorted hand
♥K4♣QJ3♠AQ974♦K76 is not a sorted hand because the two black suits are touching
♣QJ♥K4♠AQ974♦K76♣3 is not a sorted hand because the clubs are not together
♣3JQ♥K4♠AQ974♦K76 is not a sorted and because the clubs are not sorted in decreasing rank.

The goal is to sort the 13 randomly dealt cards using the least number of the following human-like moves:

A card can be temporarily removed from the hand and inserted back somewhere else. For example the ♣3 in ♣QJ♥K4♠AQ974♦K76♣3 can be inserted after the second card to sort the hand.
Any number of consecutive cards can similarly be removed from the hand and inserted back somewhere else. For example the ♣QJ3 in ♥K4♣QJ3♠AQ974♦K76 can be moved to the front. This is considered one move.

What is an efficient algorithm to find the sequence of the minimum number of such moves to sort the hand?


texts: Reduce Vertex Cover with size k to Vertex Cover with size n/2

texts:
Disclaimer: This is a homework question.

I would like to reduce vertex cover problem to the following problem:

$$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$

I have divided the problem into three parts:

$k = n/2$: This case is trivial.
$k > n/2$: Yes in vertex cover problem does not necessarily mean yes in $L$.
$k < n/2$: No in vertex cover problem does not necessarily mean no in $L$.

I know that I need to change graph $G$ into $G'$ somehow to map results of VC to $L$.

Any advice on how to do so is appreciated.


texts: Handling eqaulity constraints in genetic algorithms

texts: I am trying to solve an optimization problem with strength pareto algorithm (SPEA2). My decision variable have lower and upper bounds as well as an equality constraint (sum(dp) = 1). I am unable to handle equality constraints. Please advise.


texts: How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$?

texts:
I'm asking this, because in every exercise I check if I can relate it to one of the things I know,

like:$A_{TM}$, $\overline{A_{TM}}$, ${HALT_{TM}}$,$\overline{HALT_{TM}}$, $E_{TM}$, $\overline{E_{TM}}$, $ALL_{TM}$

But in many cases I can not find the connection and then get stuck with the question.

For example:$$L = \big\{ \langle M \rangle \mid M \text{ is TM and }M \text{ accepts only palindromes}\big\}$$ I know the solution to this question, I am not asking for a solution to this.

I want to understand the line of thought so that I will begin to solve questions like this.
What are the guidelines?

What is the first thing that should come to my mind with such questions?

My initial thought was always to look for words like accepts to associate it to $A_{TM}$, $\overline{A_{TM}}$ or halts to associate it to ${HALT_{TM}}$,$\overline{HALT_{TM}}$ but that does not help me so much.

My questions are not only related to the example but to the questions in general of this kind, that I need to determine.

Thanks.


texts: Showing that deciding whether a given TM accepts a word of length 5 is undecidable

texts:
I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this:

Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$
accepts any string of length $5$, i.e., $L(M)$ contains a string of length $5$. The above figure shows how we can use this to construct a Turing Machine that can solve the Halting
problem.

The output $M′$ of our translator behaves as follows:

$M′$ erases its own input and replaces it with the string w.
It them simulates $M$ on $w$.
If $M$ halts on $w$, then it goes into a final state (accepts its input).
It is clear that if $M$ halts on $w$, $M′$ accepts all its inputs. So it accepts a string of length 5 as well.
If $M$ does not halt on $w$, $M′$ does not accept any string at all. So it does not accept any
string of length 5 either.
So $L(M′)$ includes a string of length $5$ if and only of $M$ accepts $w$. So by running $M_5$ on $M′$, we can decide if $M$ halts on $w$ or not. But we know that this is not possible since the halting problem is undecidable. Hence $M_5$ does not exist and the given problem is undecidable.

What I am confused about is: "if $M$ halts on $w$, $M′$ accepts all its inputs" and "If $M$ does not halt on $w$, $M′$ does not accept any string at all". Can someone clarify why this is the case? I've been trying to work out the logic for so long. If any of you guys could help this would be great!

Source


texts: Space Complexity of Bottom-Up Merge Sort

texts:
What is the space complexity of Bottom-up merge sort?
It uses iteration rather than recursion so it will not use stack. But will an auxiliary array be used for the merge operation?
Please explain.
Thank you.


texts: Why does left recursion have to be eliminated?

texts:
For example,

Let the Grammar be:

S->Sa|B

Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa

What's wrong with this?

Why is right recursion a solution to the problem?

S->BS'
S->aS'|e


texts:
I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$.

What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can there be an NFA with no non-final states whose minimal NFA has some non-final state?

Oh , no nonfinal states means all are final states. So DFA - all final states means every string gets accepted. So language is $\sum^*$. For NFA, it need not be $\sum^*$. Please correct me if i am wrong here. Other case --> If there are no final states(all non-final states) means in DFA, language accepted is empty language. In case of NFA with no final state means empty language right?


texts:
According to CLRS the master method requires the recurrence to be of form $T(n) = aT(n/b) + f(n)$ where $a \ge 1 $ and $b > 1$ are constants and $f(n)$ is asymptotically positive.

This makes it sound like even $a \not\in \mathbb{Z}_+$ is a legitimate value of $a$ as long as $a \ge 1$.

I have trouble visualising what kind of an algorithm would have, say, $a = 1.5$. Can anyone provide an example of an algorithm with non-integer $a$?


texts: What is the category theory interpretation of higher order abstract syntax?

texts:
Suppose you have a simple sort of lambda calculus abstract syntax tree. The fine details don't really matter.
data T = Unit | Void | T :*: T | T :+: T | T :-> T | I

data Term x a where
  Var :: x -> Term x x
  Int :: Int -> Term x I
  Add :: Term x I -> Term x I -> Term x I
  Apply :: Term x (a :-> b) -> Term x a -> Term x b
  Lambda :: (x -> Term x b) -> Term x (a :-> b)

lam :: (Term x a -> Term x b) -> Term x (a :-> b)
lam f = Lambda (\x -> f (Var x))

newtype Program a = Program (forall x. Term x a)

How is this sort of structure to be interpreted according to category theory?
I understand that closed cartesian categories are supposed to capture the notion of the lambda calculus and have written more than one compiler from such a higher order abstract syntax abstract syntax tree to closed cartesian categories myself but still don't really "get" what higher order abstract syntax is supposed to mean in terms of category theory.
lam doesn't really seem to be a sort of functor to me. If lam was some functor operation wouldn't we want a type sort of like lam :: (a -> b) -> Term x (F a :-> F b) orlam :: (Term x a -> Term x b) -> Term x (F a :-> F b) for some sort of F.
I thought this sort of thing might be related to the Yoneda embedding and tried explicitly thinking of the free variable parameter as an environment argument and Lam as a category not just a AST.
data T = Unit | Void | T :*: T | T :+: T | T :-> T | I

data Lam env result where
  Id :: Lam a a
  (:.:) :: Lam b c -> Lam a b -> Lam a c

  Coin :: Lam env Unit
  Left :: Lam a (a :+: b)
  Right :: Lam b (a :+: b)
  Fanout :: Lam env a -> Lam env b -> Lam env (a :*: b)
  Curry :: Lam (b :*: a) c -> Lam a (b :-> c)
  Absurd :: Lam Void r
  First :: Lam (a :*: b) a
  Second :: Lam (a :*: b) b
  Fanin :: Lam a r -> Lam b r -> Lam (a :+: b) r
  Uncurry :: Lam a (b :-> c) -> Lam (b :*: a) c

  -- Some extra stuff
  Int :: Int -> Lam env I
  Add :: Lam env I -> Lam env I -> Lam env I

newtype Program a = Program (forall env. Term env a)

But I didn't really find the Yoneda embedding to simplify things much.
yo :: (forall env. Lam env a -> Lam env b) -> Lam a b
yo f = f Id

I don't have a problem figuring out how to compile one representation to another but I just don't understand what higher order abstract syntax is supposed to mean.
And to be clearer I'm not just looking for what higher order abstract means for Cartesian closed categories but what it means for any sort of language whether it be about some sort of affine language or is some sort of relational Prolog sort of thing.


texts: Switching between user-level and kernel-level threads

texts:
After reading difference between user-level threads and kernel-level threads ,now I am in doubt of context switching.Context switching is managed by OS when switching between processes/threads but google didn't clarify me when i asked it that in which case more number of switching will take place for these cases :

1). User-level thread switched to another user-level

2).kernel-level thread switched to another kernel-level

3). User-level thread switched to kernel-level

Anyone please make it clear


texts: How to reduce this with all 4 of normal applicative by-name by-value?

texts:
Given

mult = \x -> \y -> x*y

I am trying to reduce

(mult (1+2)) (2+3)

with each of the strategies:

normal-order
applicative-order
call-by-name
call-by-value

My attempt:

For both applicative and by-value I get the same (because no intermediate lambda expression contains anything reducible, hence applicative does not do reduction under lambda either)

(mult (1+2)) (2+3)
(mult 3) (2+3)
(\y -> 3*y) (2+3)
(\y -> 3*y) 5
3*5
15

With normal and by-name: I am supposed to substitute (2+3) into the body of (mult (1+2)). But that does not have a body, unless I do a reduction. But then it is not normal-order, nor call-by-name, since it is not the outermost I reduce. Hence it seems to me that these evaluation strategies "get stuck". But I am probably misunderstanding smth.

Please show me the correct evaluation.


texts:
Recently I've run across the "Two eggs, 100 floors" problem:

You are given two eggs, and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

This page (http://datagenetics.com/blog/july22012/index.html) explains how to solve this puzzle very well, but I've run across an extension that asks for an algorithm for what floor to drop the first egg from.

When considering this for the 2 eggs, 100 floors problem, I found that the first floor to throw the egg from (14) matched the minimum number of throws required to find the floor for which the egg doesn't break from when thrown.

However, when extending this to 3 eggs, the total number of throws needed becomes 9, but that doesn't mean that the FIRST egg throw needs to be made from the 9th floor. Intuitively, it would need to be from a higher floor than 14.

Thus, my question is not "how do you minimize the number of throws" as the original puzzle states. My question is: How do you determine what floor to drop the FIRST egg from when you have n eggs and k floors? Is it possible to find a generalized approach for that?


texts: What is the name for the theory that guarantees proof for negative and not for all possible positives

texts:
I have heard of some people mentioning the general rule that says that you can only ever guarantee that a program will not capture the negative cases but you can never guarantee that it captures all the positive cases.

I am only roughly summarizing what i heard and don't know the exact definition or exact phrase but the meaning remains the same as mentioned.

I am wondering if there is any formal theory or proof for the same or even if this incorrect.


texts: What mathematical terminology exists for "embellished trees"?

texts:
I'm looking for some pointers on proper mathematical (FP?, category-theory?) terminology.

My apologies if the below is somewhat imprecise; I suppose the precision is precisely what I'm looking for in the answer.

Say you have a particular Abstract Syntax Tree. Now you also have some editor that allows you to annotate arbitrary nodes in the tree by hand. For example to either highlight nodes, or tie particular textual annotations to nodes ("comments").

The datatypes that allow you to store the information as produced by this editor are somehow "embellished versions" of the original datatype for the AST. E.g. for each node we now have a node that also knows whether it is highlighted or not, and recursively contains such nodes. Values from such datatypes have at least the property that you can throw away the annotations and end up with the original tree.

There is also some notion of "coupling" between the embellished AST's nodes and the "underlying AST"'s nodes, i.e. we can always point at the "source" for any embellished node. This is also to say: if there are two ways of embellishing, we can connect them.

What is the proper framework to (generally) think about this?


texts: If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

texts:
My problem is mainly from this lecture notes on convex optimization here page4

Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer programming problem

\begin{equation*}
\begin{aligned}
& \underset{}{\text{minimine}}
& & \sum_{u,v\in E}|x_u-x_v| \\
& \text{subject to}
& & x_s =1 ,x_t=0 &x_v\in \left\{ 0，1\right\}  \forall v \in V
\end{aligned}
\end{equation*}

then we can relax to:

\begin{aligned}
& \underset{}{\text{minimine}}
& & \sum_{u,v\in E}|x_u-x_v| \\
& \text{subject to}
& & x_s -x_t =1
\end{aligned}

for  $0 \leq l \leq 1$ we define $S_l:= \left\{v|x_v \geq l\right\} $ then we have $$\sum_{u,v\in E}|x_u-x_v| \geq\int^{1}_{0}|\delta_l(S_l)|dl$$
where $\delta_l(S_l) $ denotes the crossing edge in $S_l$

how to see this inequality ?


texts: Choosing an independent hash function, given hash function value

texts:
Supposed we have a function $h:U\to [m_1]$. Given this hash function,  can we generate without using randomization or a universal hash collection another hash $h':U \to [m_2]$, which depends on $h$ and the values of $h'(x)$ are uniform? i.e., for every value $y\in [m_2]$ we have $\Pr_{x} (h'(x)=y|h(x)=t)=1/m_2$ ($x$ is chosen at random).

I know that if $U=[2^t]$, $m_1=2^{n_1}$, $m_2=2^{n_2}$, $t>n_1+n_2$ and $h(x)$ is the first $n_1$ bits of $x$ this problem is easy: we can select $h'(x)$ to be the bits $n_1+1$ till $n_2$ of $x$. My question is how to generalized this approche.


texts: Can we obtain a state diagram of a single Turing machine

texts: When illustrating what states are in Turing machine, often the examples of programs, like a checker that checks an input number is even number, are given. But different programs seem to have different number of states - if so, how can Turing machine be described with the set of finite number of states, along with others? In other words, if we follow the formal definition of Turing machine, can we construct a state diagram of a Turing diagram, assuming infinite memory exists?


texts: Are accepting states and unaccepting states distinguishable?

texts:
Is it true that for all DFA that if $A$ is an accepting state and $B$ is not, that $B$ is always distinguishable from $A$.

I don't think it's true, just because I think I can create a DFA.

$B$ reads b -> $A$

$A$ reads b -> $A$

If you start at $B$ while reading a b and at $A$ you read a b you end up in the accepting state $A$. Now is there an algorithm to see if my construction is valid?


texts: Example of a non-context free language that nonetheless CAN be pumped?

texts: So basically L satisfies the conditions of the pumping lemma for CFL's but is not a CFL (that is possible according to the definition of the lemma).


texts:
I read a paper which mentioned routine induction many times.
But when I google it, there are nothing showed up.

I think routine induction means the induction on the structure, analyzing possible cases in proofs.
am I right?

Just to make sure, I am asking it here.


texts: Computing a histogram with the number of extant values not known in advance

texts:
(This may be more fitting for CSTheory, I'm not sure.)

I'm looking for an practical or theoretical work (that is, academic papers, online jots, pseudocode or code) regarding efficient algorithms for the following problem:

Unknown-Number-of-Bins Histogram

Inputs:

An array of integers $a$, of length $n$.

Outputs:

An array of integers $\text{bins}$ of length $m <= n$.
An array of unsigned integers $\text{counts}$, also of length $m$.

Output Requirements:

For every $i \in \{0...m-1\}$ it must be the case that

$\bigl|\bigl\{ j \in \{0...n-1\} \mid a_j = \text{bins}_i \bigr\}\bigr|$
$ = \text{counts}_i$

In other words, $\text{bins}$ and $\text{counts}$ constitute a histogram of $a$, with one bin for every unique value in $a$.
It is not required for $\text{bins}$ or $\text{counts}$ to be sorted.

Other Notes:

Complexity is considered as a function of both $n$ and $m$.
Low time complexity is required both asymptotically and for relatively low values of $m$ - but it is not required for low values of $n$.
No hiding monstrosities in the $\mathop{O}(\cdot)$ constants please! This should be usable in practice.
A parallel(izable) approach? You are most welcome :-)
Low space complexity is a plus.
Deterministic algorithms preferred, and barring that, go easy on those coin flips.

Clearly, there are many way to go about this, some very straightforward, e.g. "sort the input, then build a sorted histogram in a single pass", in $\mathop{O}(n \log{n})$ time. Of course I'm interested in something better....


texts:
"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type (a -> b) -> (c -> d -> a) -> c -> d -> b. Apparently, this is an instance of fmap, i.e. a functor between two categories.

The question is: what is the domain and the codomain of this functor? How do we interpret this functor in terms of functional programming?


texts: Showing that Bayes classifier is optimal

texts:
Consider domain $X$, label set $ Y=\{0,1\}$ and the zero-one loss.

Given any probability distribution D over $ X\times \{0,1\} $, we've defined the Bayes classifier $ f_D $ to be-

$$ f_{D}(x)=
\begin{cases}
1 & \text{if }\mathbb{P}[y=1|x]\geq\tfrac{1}{2}\\
0 & \text{otherwise.}
\end{cases} $$

I wish to prove that, for any classifer $ g\colon X\rightarrow\{0,1\}$,
$ L_D(f_D)\leq L_D(g)$, which means that $ f_D$ is optimal.

$L_D(h) $ is defined to be the "true error" of the classifier $h$. That is,  $L_D(h)=D\{(x,y)\mid h(x)\not = y\}$.

I'm having some hard time proving this given the definitions above, and some hints/intuition will be appreciated.


texts: Proving non-regularity via syntactic congruence classes?

texts:
Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation:
$$x \equiv_M y \Leftrightarrow \forall v \in \Sigma^*. (xv \in L \leftrightarrow yv \in L).$$
One corollary of the Myhill-Nerode theorem is that if $\equiv_M$ has infinitely many equivalence classes, then $L$ is not a regular language.
There's a different equivalence relation called syntactic congruence which is also due to Myhill:
$$x \equiv_S y \Leftrightarrow \forall u \in \Sigma^*. \forall v \in \Sigma^*. (uxv \in L \leftrightarrow uyv \in L).$$
My question is the following: is it also the case that if $\equiv_S$ has infinitely many equivalence classes, then $L$ is not a regular language? I've tried a smattering of regular languages and each one I've tried has a finite number of these equivalence classes, but I don't see a way to get a general proof to that effect (and I'm not even sure one exists!)


texts: Longest subsequence accepted by DFA (Dynamic Prog algorithm)

texts:
Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists.

This problem has a runtime of $O(qn)$ where $q$ is the number of states of the DFA, and $n$ is the length of the string.

This problem is supposed to be solved using Dynamic Programming.

I can't figure out how to get a bound lower than $O(2^n)$.

My recurrence (it's $O(2^n)$ with memoization) --

Consider the string to be $A[1 .. n]$. And consider the substring $A[1 .. i]$ for $i < n$. I know the length of the longest subsequence accepted by the DFA for this substring. Next, I consider the substring $A[1 .. i+1]$.

If this substring has a longer subsequence that is accepted by the DFA, the max value is updated. If not, the max value is kept the same.
To figure out if the max value got updated, I have to search for all subsequences accepted by the DFA that have $A[i+1]$ included in them, as well as the entire substring $A[1 .. i+1]$.

This last thing can be memoized. That is, the end point of the entire substring $A[1 .. i]$ can be memoized. So when we need to check if $A[1 .. i+1]$ works, we just need to go to the next state after reading $A[i+1]$.

We can also memoize a lot of the earlier problems we solved. We memoize the pair (subsequence, end-state).

Here's an example:
Consider the string $a_1a_2a_3a_4$.

$a_1$:
Takes $O(1)$ to check. Then memoize.

$a_1a_2$:
Check $a_2$. Takes $O(1)$. Then memoize.
Check $a_1a_2$. Takes $O(1)$ as checking $a_1$ was previously memoized. Then memoize.

$a_1a_2a_3$:
Check $a_3$: Takes $O(1)$. Then memoize.
Check $a_1a_3$, $a_2a_3$: takes $O(1)$ per check, as $a_1$, $a_2$ were previously memoized. Then memoize.
Check $a_1a_2a_3$: Takes $O(1)$ as checking $a_1a_2$ was previous memoized.

$a_1a_2a_3a_4$:
Check $a_4$: Takes $O(1)$. Then memoize.
Check $a_1a_4$, $a_2a_4$, $a_3a_4$: takes $O(1)$ per check, as $a_1$, $a_2$, $a_3$ were previously memoized.
Check $a_1a_2a_4$, $a_1a_3a_4$, $a_2a_3a_4$: takes $O(1)$ per check, as $a_1a_2$, $a_1a_3$, $a_2a_3$ were previously memoized.
Check $a_1a_2a_3a_4$: takes $O(1)$ as $a_1a_2a_3$ was previously memoized.


texts:
According to Cayley's formula, we have number of spanning trees on a complete graph as n^n-2 and number of labelled trees with n vertices as n^n-2

If the tree is rooted then in each tree we can choose a root in n ways so total number of rooted labelled trees is n^n-1.

Here when computing the total number for rooted labelled tree, why don't we consider the ordering of elements ?

For example if we have a regular graph with 3 vertices then one of the spanning tree is 1->2->3. Here each element can be root and we can have remaining elements at right or left. So why don't we consider the ordering (right or left) in the formula?


texts:
I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that:
The MST problem belongs in NP-Class.
(I mean, i think it is correct, but could someone classify that as wrong because he would expect P instead of NP?)


texts:
I was reading about maximum flow algorithms comparing the efficiency of the different ones. On the Wikipedia Ford-Fulkerson algorithm page, they present the Edmonds-Karp algorithm as the BFS (instead of DFS) variant of Ford-Fulkerson algorithm.

The point is on time complexity, Ford-Fulkerson algorithm has $O(|E||f_{max}|)$ whereas Edmonds-Karp is presented to run in $O(|V||E|^2)$. My main is question is then, how can I decide which of these algorithm is the faster on an arbitrary max-flow problem ?

I feel very unconfortable with the $f_{max}$ even if I understand it, because determining it is the goal of the algorithm so estimating it is likely to be hard on the very general case. Depending on problem, $f_{max}$ may be very high with respect to $|E|$, even if one can possibly apply a scale factor on all edges.

I also do not understand where the runtime difference comes from. Generally BFS and DFS have the same expected runtime, the difference between them is more on problem dependant space requirement and features like shortest path, topological order...


texts: When is the AKS primality test actually faster than other tests?

texts:
I am trying to get an idea of how the AKS primality test should be interpreted as I learn about it, e.g. a corollary for proving that PRIMES ⊆ P, or an actually practical algorithm for primality testing on computers.

The test has polynomial runtime but with high degree and possible high constants. So, in practive, at which $n$ does it surpass other primality tests?
Here, $n$ is the number of digits of the prime, and "surpass" refers to the approximate runtime of the tests on typical computer architectures.

I am interested in functionally comparable algorithms, that is deterministic ones that do not need conjectures for correctness.

Additionally, is using such a test over the others practical given the test's memory requirements?


texts: Efficient algorithm for enumerating minimal vertex separators

texts:
Let $G$ be a non-empty connected undirected graph, which is not a complete graph. We treat $G$ as a set, writing $G \setminus \{v\}$ for vertices $v$, etc; subsets of $G$ should be understood as induced subgraphs. A set $S \subseteq G$ is called a separator if $G \setminus S$ is a disconnected graph. A separator $S$ is called minimal if there is no $S' \subsetneq S$ such that $S'$ is a separator of $G$.

For practical(-ish) reasons I am interested in enumerating the minimal separators of graphs $G$.

  What are fast algorithms to enumerate the minimal separators of $G$?

In the 1999 paper Generating All the Minimal Separators of a Graph, the authors give an algorithm that gives all the minimal separators in $\mathcal O(|V|^3|T|)$, where $T$ is the set of all minimal separators. I have found it quite fast in practical situations where $|T|$ is not too large.

Are there any better or alternative algorithms out there?

I am interested in solutions that work for general graphs.


texts: Are there NP languages whose verification is P-complete?

texts:
A decision problem is in NP if a candidate "yes" can be verified in polynomial time.

Are there decision problems whose "yes" is verified with an algorithm that is P-complete (reducible in logspace)? Are those problems in NP?

If so, can the "yes" be verified in logspace?

I'm told "for every NP language we can find a verifier that uses only logspace."


texts: Planning upgrades of products with dependencies

texts:
I have a set of deployed products $A$, $B$, $C$, ... Each product has a set of releases $A_1$, $A_2$, ... Right now suppose I am deploying the first release of each product. I would like to try to upgrade to the latest release of each product, if possible. Each product release can potentially depend on some range of releases of another product, e.g. $A_3$ might require that some release $B_n$ where $n \ge 4$ is deployed. If $B$ is currently on version 3 then I cannot upgrade $A$ to $A_3$ — I need to first upgrade $B$ to $B_4$ or higher (assuming that itself does not violate any constraints). I can only upgrade a single product at a time. We can assume that there are no cycles in these dependencies. Some questions I have:

It's clear that even without circular dependencies there might not be any upgrade path, e.g. if the only constraints are $A_1$ requires $B_1$ and $A_2$ requires $B_2$, then I cannot reach $A_2$ and $B_2$. Can I efficiently determine whether there is any valid upgrade path to the latest release of each product?
Can I efficiently determine the smallest number of upgrades I have to perform in order to reach the latest release of each product?
Slightly more open-ended: is there possibly some more general version of this problem that I can read about? I'm very curious about it but I don't want to clutter my post with too many questions, so I would love to read a more thorough discussion of this problem if possible.


texts: Are there any beginner-friendly courses teaching how to create a programming language?

texts:
There are many excellent step-by-step courses (free and paid) teaching you how a specific programming language works and how to use it to create applications. I've benefited a lot from these courses.
Now, I'm looking to go a layer deep and learn how to create a programming language from scratch (such as javascript or python). However, I haven't found a single "step-by-step" course (that's beginner-friendly and that contains practice exercises) that teaches how to create such languages.
In short, I'm looking for a course that teaches how to create a programming language, with the same quality as the courses that teach you how to create applications using the most popular languages today.
Does such a course exist in the first place and if so, could you show me where? And if not, what other quality resources are available?
(apart from the odd article on the internet with just an overview of the process of creating a language or a youtube video that doesn't explain anything step-by-step being far from being beginner-friendly or instructive)


texts: Book containing many important CS papers

texts:
Several years ago my professor gave me a book that contained the most important computer science papers, including Von Neuman's paper on architectures and Dijkstra's Go-To paper. The book was an older, blue hard-cover.

Sadly, it got lost somewhere... and so I thought this might be a good place to see if anybody can point me at its editors, title, place where I can purchase it?

Does anybody know the book?


texts: Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time?

texts:
After looking at other questions and my textbook, I seem to get some confusion.

I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem.

But the statement describing reduction seems obscure to me at least in the beginning of my studies in computational complexity.

So, can we transform an exponential algorithm for NPC (which we have) into an exponential algorithm for another non-NPC NP problem in polynomial time?


texts: What is a "trap" in the context of system virtualization?

texts:
My professor's notes on system virtualization refer a lot to the term "trap", but don't seem to explicitly define it. I can't seem to find any definition on Google either, other than a small article on "trap-and-emulate".
From context I sort of understand that trapping is 'catching' any operations that the virtual OS performs which it no longer has the privilege for (as it is now operating in restricted mode), and forwarding them to the hypervisor to be handled.

However could someone who has a more solid understanding of this give me a better definition?

(also I apologize for poor tagging, as there doesn't seem to be a relevant tag for virtual systems)


texts:
An array is $d$-sorted if every key in the array is located at a distance at most $d$ from its location in the sorted array.
I need to write an algorithm that get a $d$-sorted array of length $n$ and sort it in the following running times:

$\Theta(n)$ if $d$ is constant
$\Theta(n\log\log n)$ if $d = \Theta(\log n)$.

My attempt:
I wrote the following pseudo-code:
Sort_d_array(A[],d)
 min-heap-size <- d
 for i <- 1 to n
    BUILD-MIN-HEAP(min-heap,heap-size)
      if min-heap not empty
        then EXTRACT-MIN <- A[i]
          if i+d<=n
            then heap-insert-min(min-heap,A[i+d])

But in terms of runtime, all I get is $O(n\log\log d)$.
My method: I initialize $i \gets 1$ and then I build a min-heap that contains the first $d$ elements.
As long as the heap is not empty, I use EXTRACT-MIN and put the element at index $i$ in the array. If $i+d \le n$, then I add the element at index $i+d$ to the min-heap.
Any help?


texts: Difference between "sort" and "universe"

texts:
A very basic question.
As title, what is the difference between "sort" and "universe" in type theory?
Are they interchangable?
Or are there only finite number of sorts, but infinite universes?


texts: Resolution exponential lower bound... alternative proofs?

texts:
I am reading the Resolution proof system exponential lower bound via Haken's bottleneck method for the Pigeonhole Principle as presented in Arora and Barak's Computational Complexity: A Modern Approach, Chapter 15. However, I don't like how the proof is presented in the book and I am having some difficulties following it.

Does somebody know of alternative sources where this same proof is presented? I know there are different techniques to show exponential lower bounds for Resolution, but I want something based on the Pigeonhole Principle. It's just that the phrasing in this book is truly confusing.


texts: How could 'Complete and Easy Bidirectional Type Checking' handle invariant parameters on type constructors

texts:
The paper Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism provides examples for checking if one function type is a subtype of another, which I think demonstrates checking constructors with parameters which are covariant or contravariant.

I can not see an example of the subtype rule for type constructors with type parameters which are invariant.

For example consider some impure, mutable stack type:

type Stack : * -> *

push : forall a. Stack a -> a -> ()
pop : forall a. Stack a -> a

The type parameter on Stack represents a type that can be inputted and outputted from the stack, which makes it neither covariant nor contravariant.

To implement the subtyping rule for two Stack types could I simply apply the subtyping rule twice? Something like:

C1 |- a <: b -| C2    C2 |- b <: a -| C3
----------------------------------------
     C1 |- Stack a <: Stack b -| C3


texts: What would be the time complexity for following recurrence?

texts:
T (n) = T (n/2) + 2^n

I am solving this using master theorem and I calculated it to be big theta(log2 n) (log n to the base 2). But answer state it to be 2^n.

Any help would be appreciated.


texts: Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time

texts: There are various $\mathcal O(n \log n)$ or worse solutions, but I'm looking for one that runs in $\mathcal O(n)$, or a proof that none exist.


texts: How do I explain that a polynomial time reduction is in fact polynomial time?

texts:
I have as an assignment question to show that $QuadSat=\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$ is $\sf NP$-Complete.

My solution is as follows, which is pretty much copied almost 100% from a textbook example with only an extra requirement for satisfiablity at the end...

  $$QuadSat\leq_{p} Clique$$
  Let $\phi$ be a formula with k clauses such as
  $$\phi=\bigwedge_{1}^{k}(a_k\vee b_k\vee c_k)$$
  The reduction $f$ generates the strong $\langle G,k\rangle$, where $G$ is an undirected graph defined as follows:

  The nodes in $G$ are organized into $k$ groups of three nodes each called the \textbf{triples}, $t_1, \dots, t_k$. Each triple corresponds to one of the clauses in $\phi$, and each node in a triple corresponds to a literal in the associated clause. Label each node of $G$ with its corresponding literal in $\phi$.

  The edges of $G$ connect all but two types of pairs of nodes in $G$: No edge is present between nodes in the same triple, and no edge is present between two nodes with contradictory labels. $QuadSat$ is satisfiable if and only if the resulting graph $G$ contains four or more $k$-$cliques$. Each unique $k$-$clique$ in $G$ represents a set of satisfying assignments to $QuadSat$.

  The reduction runs in polynomial time, because the construction of the graph is a polynomial function; one pass through all the triples to create all the vertices for $V$, and one pass through the same triples to create the edges.

I feel like my explanation as to why my reduction is polynomial in time is severely weak, possibly bordering on wrong. How can I explain this better?

And something else: I think this only proves that QuadSat is in NP, but not necessarily NP Complete. How can I prove this?


texts: Reduction between Parity-SAT and approximate counting

texts:
Consider two problems as defined here.
Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases:

The number of satisfying assignments for $f(x)$ is $\geq 2^{k+1}$.
The number of satisfying assignments for $f(x)$ is $\leq 2^{k}$.

We are promised that one of these cases is true. $k$ is some integer between $0$ and $n-1$.
Parity-SAT: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, output $1$ if the number of satisfying assignments to $f(x)$ is even.
Is there a way to reduce Parity-SAT to approximate counting (or vice versa)?


texts:
I understand what address buses and data buses and control buses do, but...

Why does data not go to the keyboard controller, or come from the VDU output controller?


texts: what is the complexity of the below code?

texts:
I wanted to calculate the complexity of this pseudocode. In my knowledge, it is $n^2$ because the last loop only runs 8 times. I wrote a program to test it tends to run 8^logn (approximately). can you help me to find the correct answer_
1: procedure f(n)
2:   for i := 1 to n do
3:       for j := 1 to n do
4:           print(i)
5:           print(n)
6:       end for
7:   end for
8:   if n > 1 then
9:      for i := 1 to 8 do
10:         f([n/2])
11:     end for
12:  end if
13: end procedure


texts: Are point clouds faster to render than triangle meshes? What are the advantages of using one over the other?

texts: I searched online but I couldn't find any comparison between rendering a point cloud and rendering a triangle mesh.


texts: Pumping lemma on {a^n | n=3^k} — help finishing the proof

texts:
I am working on a pumping lemma question and trying to prove that the following is not regular, but I can't finish the proof, if someone can help me it will be great.

So I am given this language:
$L = \{ a^n | n = 3^k , k≥0 \}$ .
Ok. I choose $w = a^{3^m}$. I know for sure that $y = a^t$ ($y$ must be any number or $a$'s), where $t≥1$. $x = a^{(3^m)-t}$ and $y = a^t$. I pump twice, so $i =2$ and  $xy = a^{(3^m)+t}$.

Now, is this enough to finish the proof? What is my $xyz$? and how do I prove that my $w$ is not in the language?
Thank you so much for whoever decide to help me out!


texts:
I have a question concerning several NP-hard problems and why they are (or are not NP-complete).

I understand the concepts behind NP-hard and NP-complete: Problem lies in NPC if it is NP-hard and also in NP (we can verify its solution in polynomial time).

I know that Traveling Salesman (TSP) is NP-hard but isn't NP-complete (NPC), because in order to verify its solution, we would need to check that no better solution exists and hence solve it in polynomial time (so its not in NP).

However, problems like Knapsack or ILP (Integer Linear Programming) are said to be in NPC. Why is that? Isn't there the same analogy as with TSP? If someone gives us a solution and claims it is optimal, we would need to verify that no better solution exists and therefor solve these problems to obtain it in polynomial time.

Why is ILP and Knapsack in NPC and not just NP-hard? I hope my question is not too confusing, I will try to rephrase it if so.


texts: How to cluster images based on meta-information in tags

texts:
Context and Motivation

I have researched online for an algorithm (independent of a programming language AND in the context of Machine Learning) that accepts images as inputs with the expectation that individual images contain tags in the form of semi-structured information (for example, in the JSON format) that identify physical objects inside each image.

My goal is to find a clustering algorithm that will cluster objects based on common occurences of strings (i.e. physical objects described by a word, for example 'tree', 'mountain', 'airport' etc) contained in the tags about the images AND NOT on the input features of individual images contained in the pixels.

Question

My question is a binary question (Yes / No) - has such an algorithim been studied in published papers? If yes, can you refer me to a source or a list of sources that explores, explains, discusses, codes AND/OR contains instructions on how to implement the algorithm?

Input:

A set of images with semi-structured tags identifying physical objects in each indiviual image.

Output:

A set of clusters where images are grouped based on commonly occuring objects in the images.

Thanks and appreciation in advance.


texts:
So the question is:
"Given an undirected graph G=(V,E) with positive edge weights, and E'⊆E, show an algorithm that finds, from all the minimum spanning trees, the one that has more edges from E' ".


texts: Can a simulation be conducted in which the inhabitants would observe infinite time divisibility?

texts:
In this video, a physics theorist talks with his collegues claiming to have found evidence for Simulation Theory. I'm not here to ask about the various proofs for and against ST - that's basically in the realm of philosophy at this point.

But one of the physicists claims that because of the nature of mathematics, it's impossible to simulate a particular aspect of our universe: infinite divisibility of time. The theorist responded that math can be used to describe infinite time division, which is all the simulation would need to do.

My question is this: In Computer Science, can we determine whether it is or is not possible through any currently known medium of computing to create a simulation in which the inhabitants would be able to observe infinite time divisibility?

Elaboration:

If you simulate things at a rate of infinite divisions per second of simulated time, you could never simulate the entire second right? The simulation would hang infinitely? The question is whether you could simulate based on something other than an interval, like in quantum physics, things (seem to) happen more or less precisely on a small level based on whether or not they're being observed (Disclaimer: that's a severe oversimplification).

Whether in CS this method of simulation (resulting in observed but perhaps not literal infinite time divisibility) is fundamentally possible via the computing formats we're aware of is my question. I think it's quite an interesting fundamental CS question.

Somehow the simulation would have to describe the occurrence of events via functions, not increments, which make it look like to an observer within the simulation that there is no smallest increment.


texts: Round Robin, confused about how to processes are handled related to arrival order

texts:
See this picture, in parentheses are (arrival time, execution time required)

Why doesn't the "p5" process is processed before "p6"? Why do p3 and p4 are finished and p5 is executed only after the processes that arrive at "11" are executed?


texts: Trouble seeing the contradiction in diagonalization proof

texts:
I've seen the proof on a pdf online, and I'm having trouble seeing the contradiction.
If $(\langle T\rangle,z)=w \in D$, so when we emulate $T(w)$ with $U$ (universal machine), it accepts within the time bound,  so $M_D(w)=1$ and also $T(w)=1$.
Aren't you supposed to define $D$ as above, but accept only $x=(\langle M\rangle,z)$ where $M$ rejects $x$ within the time bound?


texts:
A greedy algorithm for finding a minimum feedback vertex set
is to  pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (That is, the algorithm looks at the lowest cost per cycle space decreased node picks it and continues to do so as long as the graph continues to have cycles.) What is the approximation guarantee of this algorithm?

Note: $\delta_H(v) = \text{cyc}(H) - \text{cyc}(H-v)$ where
$ \text{cyc}(H) $ is the dimension of the cycle space of $H$.

See also Exercise 6.1 of Vazirani's "Approximation Algorithms".


texts: Why shuffling by picking random position in all array instead of a part is not correct

texts:
There is a famous problem to generate a random permutation of elements in an array - it's called shuffling. My understanding of that problem is that I have to put every element in an array into a random position. So for each element in an array I can generate a random position and put it there by swapping:

for (let i = 0; i < a.length; i++) {
    const position = rand.nextInt(a.length);
    const tmp = a[i];
    a[i] = a[position];
    a[position] = tmp;
}

This is almost what the improved Fisher–Yates shuffle algorithm is doing. However my solution is not correct. According to the link I need to generate numbers from the 0..i range, not from 0..length. Can anyone please explain me why it is so?

In my implementation all the numbers are still put into random positions, so what's the problem?


texts: What kind of numerical image features should I use to distinguish between the attached types of poses?

texts: I've around $500$ binary (black and white) images, of which I attach $2$ samples. I'm working on a machine learning problem of classifying images like them. I'd like to know what image features I can use that'd be very distinct for distinct images of this type. I tried HOG features, but the difficulty is they're very high dimensional (even for a $64 \times 64$ image, the HOG feature dimension is $1764$), so the models will overfit. Hence the question. Thanks!


texts:
P.S. I have added the tag 'history', if there is any historical connotation.

Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.


texts: Is it decidable whether a Turing machine will ever leave the start state on any input?

texts:
Is $L=\{ M | M\text{ leaves the start state on every input}\}$ decidable?

I have an intuition that the following language is undecidable, since the complement $L^C$ seems to not be recursively enumerable. Some TM might remain on the start state for $k$ steps, but then leave at $k+1$ steps, so we can't get a definitive answer whether it will ever leave the start state.

What known non-decidable TM can be reduced to A to show that a contradiction arises?


texts: Does there exist a undecidable infinite language with only a finite undecidable subset?

texts:
I know that there's no such thing as a finitely sized undecidable language. However, does there exist an undecidable language where a finitely sized set of undecidable elements are 'hiding among' an infinite set of decidable elements?
In order to formalize this, let's build a deciding machine that answers $\text{YES}$, $\text{NO}$, or $\text{MAYBE}$. A correct decider for a language may always answer $\text{MAYBE}$, but if it answers $\text{YES}$ or $\text{NO}$ its answer must be correct. Such a decider can always be constructed for any (undecidable) language - in the worst case it simply always returns $\text{MAYBE}$.
Does there exist an undecidable language $L$ for which a correct decider exists that only answers $\text{MAYBE}$ for a finite number of elements of $L$?


texts: Define a list using only the Hindley-Milner type system

texts:
I'm working on a small lambda calculus compiler that has a working Hindley-Milner type inference system and now also supports recursive let's (not in the linked code), which I understand should be enough to make it Turing complete.

The problem now is I have no idea how to make it support lists, or whether it already does support them and I just need to find a way to encode them. I'd like to be able to define them without having to add new rules to the type system.

The easiest way I can think of a list of x is as something that is either null (or the empty list), or a pair that contains both an x and a list of x. But to do this I need to be able to define pairs and or's, which I believe are the product and the sum types.

Seems that I can define pairs this way:

pair = λabf.fab
first = λp.p(λab.a)
second = λp.p(λab.b)

Since pair would have the type a -> (b -> ((a -> (b -> x)) -> x)), after passing, say, an int and a string, it'd yield something with type (int -> (string -> x)) -> x, which would be the representation of a pair of int and string. What bothers me here is that if that represents a pair, why is that not logically equivalent to, nor implies the proposition int and string?. However, is equivalent to (((int and string) -> x) -> x), as if I could only have product types as parameters to functions. This answer seem to address this problem, but I have no idea what the symbols he uses mean. Also, if this does not really encode a product type, is there anything I can do with product types I couldn't do with my definition of pairs above (considering I can also define n-tuples the same way)? If not, wouldn't this contradict the fact that you cannot express (AFAIK) conjunction using only implication?

Also, how about the sum type? Can I somehow encode it using only the function type? If so, would this be enough to define lists? Or else, is there any other way to define lists without having to extend my type system? And if not, what changes would I need to make if I want to keep it as simple as possible?

Please keep in mind that I'm a computer programmer but not a computer scientist nor a mathematician and pretty bad at reading math notation.

Edit:  I'm not sure what's the technical name of what I have implemented so far, but all I have is basically the code I've linked above, which is a constraint generation algorithm that uses the rules for applications, abstractions and variables taken from the Hinley-Milner algorithm and then a unification algorithm that gets the principal type. For instance, the expression \a.a will yield the type a -> a, and the expression \a.(a a) will throw an occurs check error. On top of this, there is not exactly a let rule but a function that seems to have the same effect that lets you define recursive global functions like this pseudo-code:

GetTypeOfGlobalFunction(term, globalScope, nameOfFunction)
{
    // Here 'globalScope' contains a list of name-value pair where every value is of class 'ClosedType',
    // meaning their type will be cloned before unified in the unification algorithm so that they can be used polymorphically
    tempType = new TypeVariable() // Assign a dummy type to `tempType`, say, type 'x'.
    // The next line creates an scope with everything in 'globalScope' plus the 'nameOfFunction = tempType' name-value pair
    tempScope = new Scope(globalScope, nameOfFunction, tempType)
    type = TypeOfTerm(term, tempScope) // Calculate the type of the term
    Unify(tempType, type)
    return type
    // After returning, the code outside will create a 'ClosedType' using the returned type and add it to the global scope.
}

The code basically gets the type of the term as usual, but before unifying, it adds the name of the function being defined with a dummy type into the type scope so that it can be used from within itself recursively.

Edit 2: I just realized that I'd also need recursive types, which I don't have, to define a list like I want.