texts: Efficient alternatives to inclusion-exclusion

texts:
Say you've got a number of sets $S_1,...,S_n$ given and are supposed to calculate $\,\,\displaystyle\big|\bigcup_{i=1}^n S_i\big|$ .

The basic approach probably would be to use the classic inclusion-exclusion principle $\displaystyle\sum_{\emptyset \not= I \subseteq \{1, \dotsc, n\}} \left(-1\right)^{|I|+1}|A_I|$ , where $A_I = \,\,\displaystyle\bigcap_{i\in I}^n S_i$ .

However, inclusion-exclusion feels like it's terribly inefficient - after all, we need to sum over $\displaystyle\sum_{i=1}^n\binom{n}{i} = 2^n-1$ possible sets.

While I guess that there's no algorithm with polynomial complexity for this problem, I'm curious about alternatives that are more efficient (i.e. have polynomial run time in most cases), or are simply largely different.

I'd be thankful if you could name alternative algorithms or optimizations to inclusion-exclusion.

The particular problem I'm trying to write an algorithm for is unsatisfiability in Propositional logic for formulas in CNF. I.e. we have a finite set of atomic formulas $\{p_1,...,p_m\}$. Over these atomic formulas, the clauses of the CNF of the formula are built after these rules:
For ever atomic formula $p$, there may either appear $p$, $\lnot p$ or none of the two in the clause.

As the whole problem was either $NP$ or $co-NP$, there most likely isn't a polynomial algorithm, but I am struggling to just make it anyhow just a little bit more efficient than inclusion-exclusion (besides using ideas that have little to do with the algorithm itself like pure-literals or pure-clauses).

Yes, each set itself is discrete with each element in the set being specified. One example would be $\{  \{\bar A, B   \},\{B,C   \},\{ A,B  \} \}$. However, to fit the example, the initially given inclusion-exclusion algorithm would need to be modified.

This is the case as every clause in the CNF is a representative for a bigger clause, e.g. in the above example $\{\bar A, B   \}$ stands for
$
\{\bar A, B ,C  \}
\{\bar A, B  ,\bar C \}
$
 and $\{B,C   \}$ stands for
$
\{B,C, A   \}
\{B,C  ,\bar A \}
$

You get the actual set the representative represents by the following algorithm:

Be $M$ a set of the clause, and $S$ our output set. Add $M$ to $S$. Now repeat as long as possible:

  Find an atomic formula $A$ so that $A\notin K$ and $\bar A \notin
 K$ for some $K\in S$. Remove $K$ from $S$.  Add $K\cup \{A\}$
  and $K\cup \{\bar A\}$ to $S$.

Finally, delete all sets in  $S$ where $A,\bar A \in S$ for some $A$ and return $S$.

(An atomic formula in this case is simply any letter somewhere in $M$ without the bar (i.e. $A$ for $\bar A$))

This version of the algorithm however is at this point pretty dumb. You can improve it by not explicitly generating the actual sets and calculate it with the representants and applying some arithmetic instead.

It goes like this:
Let $A_1,...,A_n$ be our atomic formulas that appear in a set of clauses $\mathcal{K}$. For every $K\in\mathcal{K}$ you can calculate how many sets $K$ actually represents by counting the elements of $K$, let's name it $c$, and calculate $2^{n-c}$.
So, we calculate the sum all the way above, i.e. $$\displaystyle\sum_{\emptyset \not= I \subseteq \{1, \dotsc, n\}} \left(-1\right)^{|I|+1}|A_I|\text{ , where }A_I = \,\,\displaystyle\bigcap_{i\in I}^n S_i$$
just that we calculate $|A_I|$ not by $\big|\,\,\displaystyle\bigcap_{i\in I}^n S_i\big|$, but by calculating how many sets $\,\,\displaystyle\bigcup_{i\in I}^n S_i$ represents (with special case $|A_I|=0$, if $A_I$ contains $A$ and $\bar A$ for some atomic formula).


texts: Non-deterministic Turing machine to solve graph colouring

texts:
Consider the graph coloring problem: given an undirected graph $G$ and a natural number $n$ return yes if we can color the graph with n different colors and no otherwise.

I am able to design a deterministic Turing machine that would solve it with a greedy approach trying the different combinations of coloring with the $n$ colors. I think this takes exponential time although I'm not sure how to proof it.

However, I am not able to conceive a nondeterministic Turing machine that would do so. Can someone guide me designing an algorithm for this machine?


texts: Is it possible to implement a Neural Network using a graph data structure?

texts:
I'm trying to implement a feedforward neural network using a graph.
The thing is: I haven't found any example in which is used a graph data structure.
So far the examples I've found used arrays.

Can anyone please point me in the direction of some literature on the topic or some tutorial?


texts: Programming language semantics prototyping tool

texts:
Is there any tool for prototyping a programming language semantics and type system and that also allows for some sort of model checking of standard properties, like type soundness?

I'm asking this, because I'm reading a book on Alloy and it provides the exact functionality that I want, but for models expressed using relational logic.

I'm aware of Ott, but it does not have this sort of "model checking" capability, since it is focused on generating code for proof assistant systems.

Any reference on such tool existence would be nice.


texts: Can nested structures be encoded more "readably" with a single delimiter?

texts:
Imagine you have two systems of delimiting.  One with paired delimiters, [ and ]:

 [abc]

Then another system which uses a single interstitial delimiter, /:

 a/b/c

It's easy to see how to encode structure in the first case, as they nest cleanly:

[ab[cd[e]f]]

But let's say you are looking to encode arbitrary nested structures in the second scheme, using only some number of interstitial delimiters.  Whatever the encoding winds up being, a/////b//c////d///e///f would be an example of "following the rules", while //a//b/c///d///e///f/// would not.

So you're basically able to put a unary-encoded integer from 0..∞ (let's say 0 is /, 1 is //) between your elements.

It's obviously possible to encode, though the results won't necessarily be pretty or visually intuitive.  One way would be to consider you have two factors to record at each step.

Whether a nesting level is being entered or not for the ensuing token or if it's going to stay the same.  So for a?b, we want to know ...a[b... or ...ab...
how much of a nesting drop the ensuing token has after it.  So for d?e, we want to know e.g. ...d[e]... or ...d[e]]... or ...d[e]]]

The first is just a yes or no, and the second is a number which can range from 0 to however many nesting levels you've gotten so far.  So multiply the nesting level to drop by 2, add 1 if you're going a level deeper in and leave it alone otherwise.

[ab[cd[e]f]] => a 0 b 1 c 0 d 3 e 4 f => a/b//c/d///e////f

That's pretty mechanical, but if I've got it right, I think it verifies it can be done.

But here's my question: Is there a known encoding for this kind of problem that would more intuitively convey the structure to a human reader, perhaps at the cost of making longer strings?  Let's say a system that would decay such that simple cases like [ab[cd]e] could look more like a/b//c///d//e or similar, while still being able to encode everything distinctly?

I realize the quality I'm asking for is a bit "nebulous", but perhaps you see what I mean.  One thing I don't like about the encoding I chose above is it imposes a left-to-right "leaning" property, when there isn't anything particularly left-like or right-like about the nesting properties being encoded.  I wonder how that might be excised by making different choices.


texts: HOG vs. neural networks for person detection

texts:
I am very new to computer vision, (a high school student) and I am working on a project to count the number of people present in a room. I have tried to use the HOGDecriptor for person detection provided by OpenCV (HOGDescriptor_getDefaultPeopleDetector()) but it is very inaccurate, understandably. I was thinking that it may be advantageous to train my own system, since each camera setup would be specific to a certain room. This would greatly restrict the bounds of what the computer has to recognize. (What I mean by this is that if I am analyzing a conference room, little about the environment changes, other than the addition of people. This would limit the scope of the detection problem.)

My question is whether to use a HOGDescriptor or a Neural Network. I was planning on using a HOGDescriptor but was advised that a Neural Network may be more accurate. At the same time however, the way I understand a Neural Network works is that I provide the number of input neurons as well as the number of output neurons, and the training algorithm creates the hidden neurons in between. The problem with this approach is that I would like to be able to count an arbitrary number of people in the camera frame, and thus I could not provide the training algorithm with a definite number of end neurons. I addition, I am able to mark frames positive or negative (whether or not they include people in them) quite easily, but providing the description of the number of people in them would be significantly harder. For both these reasons, it would seem to me that HOGDescriptors would work better, because they do not need to be told how many people are in the frame, and they can create an arbitrary number of "end neurons."

Any help clarifying the benefits of both technologies, as well as advice on which to use, would be greatly appreciated. I realize that this question might be very elementary, but I am willing to learn and will take all responses very seriously. Thank you.


texts: Efficiently determine relative ordering between two elements in a PO-set

texts:
What algorithms/heuristics exist for efficiently determining the relative order between two elements in a partially ordered set?

In my case, the PO-set is stored as a directed acyclic graph where an edge is an happened before relation and I am streaming live data into this PO-set. Nodes usually have less than 5 backward edges, with 1 being the most common, and there will be at most 10^6 nodes. The newly inserted nodes usually have edges to the previously most recently inserted nodes.

I am usually doing this query just after I've added a node to the graph, to find the relative ordering between the inserted node and a few select other nodes, so the traversal paths tend to overlap a lot. I am also maintaining a total order of the PO-set as I go, which might be useful for this as well.

My current solution consists of starting at both nodes and moving backwards one step at a time from both simultaneously (or rather, one step for the left node, then one step for the right) until I find a common ancestor node, or run out of edges to traverse. This is not very fast, but I don't have that many elements in the set yet so it works for now.

The main problem is the worst case runtime of O(n) as n will grow in the future. Is there a way to do this faster?


texts: What is correct time complexity of the substring generation algo

texts:
The naive algorithm for generating all unique substrings involves traversing all the string from 1..n, thus takes $\mathcal{O}(n^2)$, but it also involves maintaining a list for all generated substring to check everytime for repetitions.
So the total time can't be $\mathcal{O}(n^2)$, since there is an added checking of uniqueness, which means that I have to maintain a list of all previous generated substrings.
So how is it correct that when it is said that the algorithm takes only $\mathcal{O}(n^2)$ time.
There is obviously an added cost at each substring generation.
The actual time complexity should be as pointed out by Raphael should be something like the following -:
$\mathcal{O}(n^2) + (\mathcal{O}(m^2) * \mathcal{O}(n)))$
where $m$ is the total number of substrings generated $n(n+1)/2$, and the time to compare 2 different strings is the smaller length between two strings, assuming the strings are being compared character by character.
Now if the above is correct then what I am confused about is should it be plus or a multiply with the comparision cost.


texts: Proof of correctness for a triangulation-algorithm

texts:
I'm working on the following exercise:

  Consider a point set $S = \{ p_1, p_2, ..., p_n \}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have pairwise different $y$-coordinates and are sorted in increasing order of them, i.e., $y(p_i) < y(p_j) $ if and only if $i < j$.
  Develop an algorithm that computes a triangulation of $S$ and needs $O(n)$ runtime and memory.

I got the following algorithm (based on Andrew's monotone chain algorithm) from Marcelo Fornet in his answer to one of my previous questions (I condensed it a bit):

Input: a list P of points in the plane.

Precondition: There must be at least 3 points.

# Initialize T as empty list to store triangulation
Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        Add the last two points from L and P[i] to T (the triangulation)
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from U and P[i] to T (the triangulation)
        remove the last point from U
    append P[i] to U

The triples of points in T will be the triangles

While I understand how this algorithm works I'm struggeling to show it's correctness in a formal way.

My idea would be to use induction on the invariant that this algorithm always prodcuces a triangulation of the given point set. This is what I tried:

Assertion: The said algorithm always returns a triangulation for a given point set.

The assertion is clear for a set of three points, so we got our induction start.

Now lets suppose the assertion holds for all sets with at most n points.

But I'm stuck at the induction step. I tried to make a case analysis wether the new point $p_{n+1}$ lies in the upper or the lower half of the convex hull of $\{p_1,....,p_n\}$, but it didn't work out.

I'd be thankful for any kind of help.


texts: How to find partition set of a Partition Problem using its decision problem

texts:
I understand Partition Problem is NP-complete.

Given we have a magic black box that can answer Yes or No for the partition problem. I was wondering how to come up with a polynomial time algorithm to find the actual set using this black box.

Thank you.


texts: Dividing a array to into k parts using dynamic programming

texts:
I am thinking about how to break an array into k parts using DP with the following requirement.

Array A of size n divided into k parts

All elements are positive integers and order is fixed.
The maximum difference between the sum of elements in 2 groups is minimized.

You may think of a scenario: there is a book with many chapters and I want to put different characters in different volumes as even as possible.
It is hard to think how to do that because if I use DP and add one $a_i$ at a time, the algorithm will always put the newly added $a_i$ to a new group until all group is filled.
Any help is appreciated.


texts: What will be the pictorial diagram of this transition table?

texts: I was doing my homework and I am confused on what I'm doing, it can't be that straightforward. I'm making a mistake somewhere. I tried looking for practice problems but they don't cover my issue either, I'm still confused. What will be the pictorial diagram for the following transition table?


texts:
Assume a point set $P[n]$ with $n$ points which align in one plane in the euclidean space, so $p(x,y) \in \mathbb{R}^2$. Looking for an algorithm to construct an AABB (axis aligned bounding box) I did not find anything. But I thought that the simpliest appraoch could be the best: traverse all $p \in P$ and keep track of the minimum and maximum value of each dimension. The AABB is spanned by the two points $(x_{min},y_{min})$ and $(x_{max},y_{max})$. This clearly runs in $\mathcal{O}(n)$.

Now I struggle proving this kind of obvious fact (the best algorithm runs in $\mathcal{O}(n)$). It is clear that all points of the set have to be checked for inclusion which the algorithm does, given the fact that the set is not preprocessed in any way, like ordered.

What is a good formal approach for proving this?

Side note: Is there a better algorithm for constructing an AABB?


texts: Direct reduction from Near-Clique to Clique

texts: An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ where $|S|=k$, $(u,v)\notin E$, and $S$ forms a clique in $(V,E\cup\{(u,v)\})$. How can I show a direct reduction from Near-Clique to Clique?


texts: Can we say McCarthy and Hoare had the same objective in the 60s regarding a mathematical theory of computation?

texts:
I don't think there's any way to ask a very precise question here, so this might be considered opinion based.  Nevertheless, it seems the question is clear enough because I'm asking whether these two initial steps towards a theory are trying to achieve the same thing.  It seems to me Hoare went towards an imperative-calculus and McCarthy went towards a functional-calculus for deriving programs hand in hand with mathematical proofs.  Can we say they both went towards that each in different (imperative, functional) ways?

I'm comparing A Basis for a Mathematical Theory of Computation by John McCarthy with An Axiomatic Basis for Computer Programming by Sir Charles Anthony Richard Hoare.

To me the main contribution (or the most interesting part) of McCarthy's paper is given in section 3.2, recursion induction, where he exemplifies how one can prove two algorithms being equivalent --- algorithms as specified by the language defined in the paper.  (I possibly have this opinion because to me so much of his work is no news, since I'm familiar with Lisp and recursion.)

My understanding it at least partially confirmed by what he says right in the introduction [introduction, point 2, page 2].

  To define a theory of the equivalence of computation processes. With
  such a theory we can define equivalence preserving transformations.
  Such transformations can be used to take an algorithm from a form in
  which it is easily seen to give the right answers to an equivalent
  form guaranteed to give the same answers but which has other
  advantages such as speed, economy of storage, or the incorporation of
  auxiliary processes.

Extra-credit.  It seems Dijkstra followed along Hoare's approach because even after the 70s he kept on using precisely Hoare's notation, introduced in Hoare's paper in 69.  I would appreciate answers also linking Dijkstra's opinion on the matter --- although really not required.


texts: Is the complexity class $P$ closed under rotation, where rotation is defined as $\text{rot}(L) = \{ wv \mid vw \in L \}$?  How would we prove it?


texts: How to discuss coefficients in big-O notation

texts:
What notation is used to discuss the coefficients of functions in big-O notation?

I have two functions:

$f(x) = 7x^2 + 4x +2$
$g(x) = 3x^2 + 5x +4$

Obviously, both functions are $O(x^2)$, indeed $\Theta(x^2)$, but that doesn't allow a comparison further than that.  How do I discuss the the coefficients 7 and 3. Reducing the coefficient to 3 doesn't change the asymptotic complexity but it still makes a significant difference to runtime/memory usage.

Is it wrong to say that $f$ is $O(7x^2)$ and $g$ is $O(3x^2)$ ?
Is there other notation that does take coefficients into consideration? Or what would be the best way to discuss this?


texts: Finding all minimal upper bounds in a partially ordered set

texts:
I have a partially ordered set of numbers, represented as a vector<set<int>> (e.g. if $2 \preceq 4$ in this order, then poset[2] contains 4). Given 2 elements $x$ and $y$, what is an efficient way to find all their minimal upper bounds (that is, those which aren't greater than any other upper bound, but there may be other upper bounds which aren't comparable to them)?
If I also maintain an inverse relation (i.e. inverse_poset is also a vector<set<int>> and inverse_poset[4] contains 2), I can do this:

compute intersection of poset[x] and poset[y];
for each element z of intersection, check if inverse_poset[z] and intersection have a common element other than z. If not, z is a minimal upper bound.

Is there a better way? Especially one which doesn't need inverse_poset?
EDIT: I didn't make it clear in the initial question, but new elements and edges can be added to the poset over time (but not removed). So any preprocessing should ideally be cheap to maintain when they are.


texts: Last fall I went on a tour of the Blue Waters supercomputer at the University of Illinois.  I asked whether anyone ever used the entire computer.  I was told that it was always working on multiple projects.  That made me wonder about the usefulness of supercomputers.  Perhaps Blue Waters is unusual in that it has to be shared by industry and the university - I don't know.  I assume there's some overhead in managing the processors and memory of a single supercomputer.  Would it be more cost effective to build smaller computers?  Can anyone help me to understand the value of supercomputers?  Or is it that sometimes they are dedicated to single projects?


texts: Complexity of Sorting Integers on a Multitape Turing Machine

texts:
How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access... how much does losing that cost us? Also, MTMs can't use log-sized words.

Say we have $N$ integers from $[0, 2^B)$. It's not too hard to adapt existing sorting algorithms to get an upper bound on the sorting time. A radix sort would normally take $O(B N)$ time, but on an MTM we have to store the bits of the integers. This increases the cost of moving items by a factor of $B$, giving an actual running time of $O(B^2 N)$ operations for radix sort on an MTM. Merge sort and quick sort also have their runtimes expand by a factor of $B$ due to item movement, from $O(N \log N)$ to $O(B N \log N)$.

Since $O(B N \log N)$ is better than $O(B^2 N)$ in some cases and worse in others, we can alternate strategies to sort on an MTM in $O(B N \min(B, \log N))$ time.

Is that bound tight, or is there some way to avoid moving items so much? Does sorting $N$ integers of size $B$ take $\Theta(B N \min(B, \log N))$ time on MTMs?


texts: Approximate target subset by intersecting other subsets

texts:
Let $S$ be a finite set of integers (this set contains about 200000 elements). Let $T \subset S$ be a particular subset of $S$ called target. $S$ keeps growing. So does $T$. Each new element of $S$ might or might not be in $T$.

No (known, or practical) algorithm can determine if an element $s \in S$ is in the target set: a human being must give the final word (ie, it is subjective). It is estimated that $T$ has about 30000-35000 elements. I already know $T_1$, a first approximation of $T$, with about 25000 elements. I also already know some thousands of elements of $S$ that are certainly not in $T$.

What I want is a way to approximate $T$ as closely as possible, and present only those elements to a human being. Also, for each new element of $S$, I want to determine if it has high probability of being in $T$ -- and present only those with high probability to a human being.

Now, I describe what I can use to try to approximate $T$.

Each integer $s \in S$ has some labels associated. These can be represented as subsets $L_i \subset S, \forall i \in \{1, ..., n\}$ ($n$ is about 250). These subsets are known, determined by algorithms (ie, I have functions $l_i \to \{in,out\}$ such that $l_i(s) = in \iff s \in L_i$).

Some label algorithms are very fast, some are slow. Anyways, these labels (ie, the sets $L_i$) have already been determined. Some of these labels contain very few (1-100) elements, some contain a lot (100000-150000). Many labels are independent, some are closely related (ie, I know that some labels are subsets of others, I know that some are disjoint, etc).

So, given this framework, what kind of algorithms can I use to approximate $T$? They can be interactive, ie, they could get better after each new approximation of $T$, if this makes the problem easier.

I thought about using a genetic algorithm to determine which labels, when intersected, give good approximations of $T$. However, this can get slow, with a naïve intersection algorithm (ie, suppose $L_1, L_2, L_3$ are to be intersected; if they are all "big" (50000-150000), it can be quite time consuming to calculate the intersection! -- now, imagine a gene that would require to intersect, say, 50 labels...).

How can I speed this, without sacrificing too much the precision?


texts: Does quicksort for increasing order work faster if the input set is more decreasing sorted?

texts:
In CLRS's Introduction to Algorithms,

  The following procedure implements quicksort:

QUICKSORT(A; p; r)
1 if p < r
2 q D PARTITION(A; p; r)
3 QUICKSORT(A; p; q-1)
4 QUICKSORT(A; q+1; r)

  To sort an entire array A, the initial call is QUICKSORT(A; 1;
  A.length).   The key to the algorithm is the PARTITION procedure,
  which rearranges the subarray A[p..r] in place.

PARTITION(A; p; r)
1 x = A[r]
2 i = p - 1
3 for j = p to r - 1
4     if A[j] <=   x
5         i = i + 1
6         exchange A[i] with A[j]
7 exchange A[i+1]  with A[r]
8 return i +1

The quicksort algorithm sorts a set in increasing order, where the pivot is chosen to be the last element in the current array.

I am trying to figure out the worse case and best case to the algorithm.

But I am more interested in whether quicksort will be faster, if the input set is originally more close to the final sorted result. In the concern, I guess the choice of pivot may not matters.

After some thought, the following questions make me think that quicksort will be slower if the input set is more close to the final sorted result.

Is it correct that

when the input set is already in decreasing order, the assignments and exchanges in the for loop in PARTITION will be skipped?
Does quicksort work faster when the input set is already more sorted in decreasing order?

Thanks.


texts:
I came across following fact in Automata book by Hopcroft, Ullman:

  Theorem 1: For every PDA accepting by empty stack (PDAeS), there is an equivalent one state PDA accepting by empty stack.

I was wondering how this applies to:

PDA accepting by final state (PDAfS)
Deterministic PDA accepting by empty stack (DPDAeS)
Deterministic PDA accepting by final state (DPDAfS)

My understanding is, it applies equally to PDAfS, since I read in the book that both PDAfS and PDAeS are of equal power. Am I right? Also what about DPDAs?

Also I came across this post, which states:

  Theorem 2: All PDAs are equivalent to two state PDAs.

I want to know what all variants (PDAfS, PDAeS, DPDAeS, DPDAfS) it refers to by PDA? Reading the explanation given in the problem itself, my guess is that it is possible with PDAeS and DPDeS. Am I right?

Added later

I came across two more theorems in the book:

  Theorem 3: For every regular language L, there is DPDAfS, such that L = L(DPDAfS)
  Theorem 4: For every regular language L, there is one state PDAeS, such that L = L(PDAeS)

So in all above highlighted theorems (total four, two originally stated and two added later), I want to know to what they apply? PDAeS, PDAfS, DPDAeS, DPDAfS.

So let me enumerate problems explicitly:

(From theorem 1)

For every PDA, is there equivalent one state PDAfS?
For every DPDA, is there equivalent one state DPDAeS?
For every DPDA, is there equivalent one state DPDAfS?

(From theorem 2)

Is all PDAs are equivalent to some two state PDAeS?
Is all PDAs are equivalent to some two state PDAfS?

(From theorem 3)

For every regular language L, is there DPDAeS, such that L = L(DPDAeS)? (details in Update 1)

(From theorem 4)

For every regular language L, is there one state PDAfS, such that L = L(PDAfS)?

Update 1

Realized that the answer to 6th question is no. DPDAeS are not even capable of generating all regular languages. This leads to the possible next question:

Cant any DPDAeS generate any regular language?

PS:

Sorry, if you didnt like how I am referring to PDAs with fS and eS suffixes (which mean "acceptance by final state" and "acceptance by empty state" respectively). But I find it very convenient.
Sorry for asking absolutely too much on one post. But all those problems form a part of one big problem: how FAs, PDAeS, PDAfS, DPDAeS, DPDAfS and their variants (one state and two state) generate each other.


texts: Domain theory gives an amazing theory of computability in the presence of simple types. But when parametric polymorphism is added there doesn't seem to be a nice theory that explains whats going on quite as nicely as domain theory explains computation over simple types. Certainly I wouldn't expect such a thing to exist for System-F because no set theoretic models of System-F exist. What about a restriction of System-F that has predictive and has a universe hierarchy? Has this been studied? Is there a nice domain theory that applies to it? Going further what about dependent types? Can domain theory somehow be mixed with weak $\omega$-groupoids to accomplish something?


texts: How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem

texts:
Task:
A Hamiltonian path of a graph is a path that visits all nodes of the graph exactly once. The hamiltion path problem (HPP) consists in deciding whether a given graph has such a path. Similarly, the 1/2 hamiltion path problem (1/2-HPP) asks for a path that visits exactly half of the nodes.
Show that: $HPP \le_{P} 1/2-HPP$

Question: Can anyone give me a hint on how to prove $HPP \le_{P} 1/2-HPP$


texts:
I have Java function as input and want to get it's order for example O( n )
I search in the internet very hard but didn't find any thing can help me, is there any algorithms or package may help me.


texts:
Given two 2-3 trees I would like to merge them in $O(n_1+n_2)$
I've solved before that if I get an ordered list then I can turn it into 2-3 tree in $O(n)$.
My questions is how can I turn two trees into one ordered list in $O(n_1+n_2)$ and then I know how to solve this.


texts:
This is a HW question, so Im not expecting full solutions or anything, but would love some direction. Also English is not my first language, so I apologize in advance.

We define a new class of languages - VNL:

  all languages L s.t there exists M - a DTM with:

  an input-read-only tape.
  a "witness" tape which is a "one-time" read-only and can be read only as stay/right (the tape head cant move left).
  a work tape which is read/write.
  Also there exists p a polynomial s.t. for every w $\in \{0,1\}^*$:
  $w\in L\ \iff\ \exists u\in\left\{ 0,1\right\} ^{p\left(\left|w\right|\right)}:\ M\left(w,u\right)=acc$
  M is of O(log(|w|)) space complexity (where w is the input).

Now we need to prove VNL=NL. I think I managed the VNL$\subseteq$NL direction:

  Let L$\in$VNL. then there exists M a DTM as we described before.
  I then define a NDTM - $M_L$ on input w: that runs M on w,u where u is randomly generated, bit by bit, everytime M wants to move right.
  It only needs to store an index to make sure u is of the right size, and that takes log(p(|w|) space, which is still logarithmic space complexity, and also running M is logarithmic. I also explain why M meets the other demands (but as they are somewhat trivial, I don't write them here to keep this post a bit shorter).

I have two questions:

  I'm not entirely sure how to do the other direction (NL$\subseteq$VNL).
  What I tried so far was: take L$\in$NL. $M_L$ is the logarithmic NDTM for it. I define M (of our new type) to treat the "witness" tape as a series of configurations. Somehow I'm supposed to verify its a legitimate configurations series resulting in M accepting w. Perhaps draw 2 consecutive configurations to the work tape and somehow verify the the transition between them is legitimate? Would love help with that.
  For another section of the question we remove the demand that the witness tape is read only to the right (which means I can read it as many times as I want). We're supposed to determine to which class VNL equals now. I thought about NP, but encountered some difficulties during the proof. Would also love help with that.

Thank you!


texts: Mapping reducibility vs. Turing reducibility

texts: Let $A$ and $B$ be two languages. If $A \le_{m} B$ ( reducible by mapping ) then I know that if $B$ is decidable so is $A$ and if $B$ is recognizable so is $A$. And  if $A \le_{T} B$, then if $B$ is decidable so is $A$. But I can't say the same thing for recognizability which  I can see by example when  $A \equiv L_{\phi}$ ( the empty language ) and if $B \equiv A_{TM}$ ( acceptance language ). I know this is because of the fact that we assume the orcale to decide $B$ while proving $A \le_{T} B$. Why is it so that we assume the oracle to decide and not recognize $B$ while comparing relative difficulty of two two languages ? Sorry for vague terminology of relative difficulty, I have not yet begun reading about complexity theory and hierarchies and for now only have a vague idea about it.


texts: Lambda Calculus Prove Equality Excessive (Haskell-oriented)

texts:
I'm on a lambda calculus with parametric polymorphism a la Hindley-Milner Haskell-oriented course and I'm currently facing this exercise which I got stuck on.

Prove that $(\forall m\downarrow, n\downarrow :: N)\space (m+n)-m=n$

Definitions:

$(+)=\backslash m \space n \rightarrow case \space m \space of \space \{0\rightarrow n, Sx \rightarrow S(x+n)\}$

$pred = \backslash n \rightarrow case \space n \space of\{0\rightarrow 0,Sx\rightarrow x\}$

$(-)= \backslash m \space n \rightarrow case \space n \space of \space \{0\rightarrow m,Sx\rightarrow pred(m-x)\}$

Seems super simple but there's a part at which I got stuck. I also can only use the following already proven statements (may not need all):

$1) \space m+0=m$

$2) \space m + Sx = S(m+x)$

$3) \space m+n=n+m$

So here's what I did so far: I decided to prove this by using induction over m

$m=0, \space (0+n)-0=n-0=n$ is true (applying the given definitions for the functions)

$m=x, \space (m+n)-m=n$ is true (Hypothesis)

$m=Sx, \space (Sx+n)-Sx=n$ is true (Thesis)

Proof for $m=Sx$:

$(Sx+n)-Sx=S(x+n)-Sx=pred(S(x+n)-x)$ At which point I got stuck. I obviously have to get that $S$ out of $S(x+n)-n$ to have $(x+n)-n$ and apply the Hypothesis but I can't figure out how. Any ideas?


texts: Is there an appropriate design pattern for this problem?

texts:
In terms of good OOP design, what is the best way to structure the code described below.
The data
I have a set of commands. Each command has an identifier, deadline, and a set of jobs to be done.
Each job has an identifier, a processing_time, a set of successors and we must precise the command to which it belongs. A successor of a job is necessarily a job that belongs to the same command. Visually, each command has its graph of jobs.
What needs to be done?
I need to construct big graph out of all the graphs by adding two dummy nodes. One node is directed to all the jobs from all the commands that has no predecessors. On the other hand, all the jobs of all the commands that has no successors will be directed to the other dummy node. Here is a figure to make things clear (a project is a command). The start and end are the two dummy nodes I am talking about. Note that those dummy nodes don't belong to any command.

From now on, I will only manipulate the big graph (doing graph traversal algorithms etc).
My attempt 1

A class Command that has the attributes id, deadline, jobs (dictionary whose keys are jobs ids and whose values are objects of type Job)
A class Job that has the attributes id, processing-time, successors, command(object of type Command)
A class Problem where I put parsed data. It has an attribute commands (a dictionary whose keys are the ids of commands and whose values are objects of type Command )

Doing this, I will need later to merge all the tasks of all the jobs in a a new variable. I don't want to do it this way, I want the architecture to take into account the  fact that i will only be manipulating jobs and not jobs grouped by commands (as in my commands attribute in the class Problem). How to do it in that way?
Attempt 2
I am thinking about removing the jobs attribute from the class Command. Indeed, from a command point of view I don't need to know which jobs belongs to me.
PS: I am using Python.


texts: Find isomorphism of graph with maximal number $x$ such that $f(x)\neq x$ - assuming $NP=P$

texts:
For $f : V → V$ which is authomorphism of directed graph $G = (V, E)$,
  $$\#f = |\{v : f(v) \neq v\}|$$  For graph $G$ we denote:   $$\#G =
 \max\{\#f : \text{$f$ is isomorphism $G$} \}$$

  Prove that if $P = NP$ then function $G\to\#G$ is polynomially
  computable.

My problem is that I can't think about isomorphisms. I know that thanks to assumption in polynomial time I can check if two graphs are isomorphic. The problem is however that I can't generate candidate for checking it.


texts: Why are HMMs appropriate for speech recognition when the problem doesn't seem to satisfy the Markov property

texts:
I'm learning about HMMs and their applications and trying to understand their usages. My knowledge is a bit spotty, so please correct any incorrect assumptions I'm making. The specific example I'm wondering about is for using HMMs for speech detection, which is a common example in literature.

The basic method seems to be to treat the incoming sounds (after processing) as observations, where the actual words being spoken are the hidden states of the process. It seems obvious the hidden variables here are not independent, but I do not understand how they satisfy the Markov property. I would imagine that the probability of the Nth word is not just dependent on the N-1 word, but on many preceding words before that.

Is this simply ignored  as a simplifying assumptions because HMMs are very good at correctly modeling speech detection problems, or am I not clearly understanding what the states and hidden variables in the process are? The same problem would appear to apply to a great deal of applications in which HMMs are quite popular, POS tagging, and so forth.


texts:
Let
\begin{align*}
    L_1 &=\{\langle M,w\rangle \mid M\text{ halts on }w\}\\
    L_2 &=\{\langle M,w\rangle \mid M\text{ does not halt on }w\}\,.
\end{align*}
Here $M$ represents encoding of a Turing machine (T.M.) and $w$ is the input string. What is the class of $L=L_1 \cup L_2$?

I read that the union would be a regular language as a string has to belong to either $L_1$ or $L_2$ (i.e., halt or not halt) so their union would be a regular language.

I have a doubt. Suppose we assume $L$ as a recursively enumerable (R.E.) language then there exists a T.M. which halts on all "yes" cases. Here yes cases means strings which belong to either $L_1$ or $L_2$.
So, if a string belongs to $L_2$, then the T.M. should halt which means that we are able to halt and say "yes" even if machine doesn't halt on this string (according to condition of $L_2$). This solves halting problem and hence assumption is not correct and so $L$ should be non recursively enumerable.

I know that there is some flaw in the explanation given above but I am not able to find it.

Can someone please help me?


texts:
In my lecture I saw the problem of
$\text{EXACT-CLIQUE} = \{\langle G,k\rangle : \text{the largest clique in $G$ is of order $k$}\}$

I understand this problem is obviously not in NP as we would need to check all cliques, but if we consider the complement of the problem, (i.e. is the largest clique not of order $k$), wouldn't this be in NP? Because we could simply use non-determinism to guess a clique bigger than $k$ and then check if it indeed makes a clique. My lecturer said however that the problem is not in co-NP but I did not understand the explanation.


texts: Is something more than Turing complete Turing complete?

texts:
In complexity theory, we do not call a decision problem that is not in NP "NP-complete".

But in computability, do we call a machine model "Turing complete" if it can compute functions which Turing machines can not?

The definition from Wikipedia didn't address this problem explicitly, and likely assumed yes:

  A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.

For example, if there is a system that can:

Compute every Turing-computable function.
Compute the halting problem for a Turing machine.

And nothing else. Is it Turing complete?


texts: Restricted Boltzmann machine confusing details

texts:
Hi I'm new to RBM and machine learning/computer vision in general, and I'm using the code from: http://blog.echen.me/2011/07/18/introduction-to-restricted-boltzmann-machines/ while reading on https://en.wikipedia.org/wiki/Restricted_Boltzmann_machine for some theories. But right now i'm totally confused. In the code there is a part:

# Calculate the activations of the hidden units.
      hidden_activations = np.dot(visible, self.weights)
      # Calculate the probabilities of turning the hidden units on.
      hidden_probs = self._logistic(hidden_activations)

I assume the equivalence in wikipedia would be the conditional probability, but when I look that up, nothing makes sense! I mean, what are v and h, are they supposed to be vectors or values? (I assume they are in fact just values, as wikipedia only talks about each seperate samples while the code groups all of them into a matrix, but even them it's still hazy :( ). I'm new to this so my question may be a little dumb but please help me. Thank you very much!
P/s: Sorry I am unable to post the equations :(


texts: Determining set of states that satisfy a CTL formulae

texts:
I'm trying to understand CTL formulae, and until now I've understood everything (or at least I thought I did). I have the following Kripke strucure:

Now given the following CTL formulae A(g U EG (b v y)) , which states does it satisfy?

I know that the answer is {s1,s2,s3} (according to lecture notes), but I don't understand that.

This is what I have tried so far to solve it:

I solve EG(b v y) first and for this I get {s1,s3} because from these states there exists a path where either b or y holds globally.
Then I group it together again and solving A(g U EG(b v y)) which I understand as "Along all paths, g holds until there exist a path where b or y holds" and as I already know the last part of it, I understand it as "Along all paths, g holds until either s1 or s3 holds".

To me s2 is the only obvious answer because g holds in s2 until y holds in s1. I don't understand why s1 or s3, is a part of the answer.

Anyone care to explain? Or at least show the steps you take to derive the answer?


texts: Proving using Beta Reductions (Lambda Calculus)

texts:
I am working on proving something by using Lambda Calculus and Beta Reductions, and I was following along a tutorial on another problem and attempted to carry over the knowledge onto a different problem and I am a little confused on the last step.

The problem is to prove $\textbf{or true false}$.

Here are my steps: (if there are any improvements or errors please let me know)

Step 1: Begin writing the identity for OR along with the parameters true and false.

$(\lambda x. \lambda y.(x ~ true ~ y)) ~ true false$

Step 2: Replace the $x$ terms with true.

$(\lambda y.(true ~ true ~ y)) ~ false $

Step 3: Replace the $y$ terms with false.

$ true ~ true ~ false \equiv (true ~ true) false $

Step 4: (I am a little shaky on this step, however I saw it done this way). Expand on one of the terms by replacing with it's identity. So we break true into:

$ (\lambda x. \lambda y. x) true ~ false $

Step 5: Again, replace x with true.

$(\lambda y.true) ~ false$

Step 6: $\textbf{this is the step i am most confused on}$
It looks as if since there is no way we can distribute the false to the y we simply just drop both of them since it is not an applicable function. Which then returns you with true, which stands to reason that true or false is true.

Can anyone shed light on Step 6? Or if I am correct and thats the rationale please let me know!


texts: How to do well in Computational theory courses?

texts:
I'm having a lot of trouble solving problems in my Comp Theory class. I just have no idea how to formulate arguments for certain things like proving the concatenation of two non reg langs can have reg languages, or whatever. I know it sounds cliche and really corny, but I don't want to just google the answers. It may be fine for doing well on an assignment, but I know for a fact that I'm not getting the benefits of actually failing over and over again, and then solving the problem. However, most of the time I don't even know how to fail. I just can't even approach a problem. I just look at it, and have no idea on how to approach it.

For those who have taken this class and were just as lost as I am, how did you get through it?


texts: What is the average time complexity, for a single linked list, for performing an insert?

texts:
I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list.

The longer the list, the longer it will take on average to do the insert.

However according to bigocheatsheet it is O(1) or has no dependency on the size of the list.

What is wrong here?


texts: Alternate proof of the Caro-Wei theorem for lower bounding the independence number

texts:
Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ that are pairwise non-adjacent. So Caro-Wei says that $\alpha(G) \geq \sum_{d_i \in V(G)}{\frac{1}{1+d_i}}$. The standard probabilistic proof goes as follow, here we let $V(G)=\{1,2,...,n\}$:

Consider the set $S_n$ of permutations of the vertices in $G$ and $\sigma \in S_n$ be a permutation in $S_n$. Let $A_i$ be the event that $\sigma(i)<\sigma(j), \forall j \in N(i)$ namely all neighbours $j$ of the vertex $i$ gets maps to by $\sigma$ to some number greater than $\sigma(i)$. There are $\binom{n}{1+d_i}$ places that $\sigma$ can map the vertex $i$ and its neighbors to. Futhermore, $\sigma(i)$ is the smallest, so there are $d_i!$ ways for the neighbours of  $i$ to be map to and $(n-d_i-1)!$ ways for the remaining number to be permuted. So $P(A_i)=\frac{\binom{n}{d_i+1} d_i!(n-d_i-1)!}{n!}=\frac{1}{1+d_i}$. Now consider the subset of the vertex set of $G$, $U=\{i \mid A_i = \text{true}\}$. Notice that two vertices in $U$ does not share an edge. The expected value $E[|U|]=\sum_{i\in \{1,...,n\}}{\frac{1}{1+d_i}}$. So done.

But I'm wondering if there is a proof not involving probabilistic method.


texts:
Given the SAT problem, the NAE (not all equal) SAT adds the restriction that there must exist two literals in a clause which have different truth values in a satisfying assignment.
We can show that the NAE3SAT is an NP complete problem by reducing 3SAT to the NAE3SAT by replacing each clause $C_i = (x \lor y \lor z) $ with two clauses of the form $(x\lor y \lor d_i) \land (\lnot d_i \lor z \lor F)$ where $F$ denotes the false literal and $d_i$ is dummy variable.
I am trying to extend this reasoning to the case with 4 literals per clause, NAE4SAT but it seems less straightforward than I have expected.


texts:
Given a vector $x=(x_1,\cdots,x_n)$ such that $0\leq x_i \leq1$ and $\sum_{i=1}^n x_i=1$. I would like to find a vector $x^*$ such that ($l_1$ norm ) $||x-x^*||_1\leq \delta$, where $\delta >0$.

How can we generate the $x_i^*$ so that still $\sum_{i=1}^n x^*_i=1$?


texts: What does it mean to "show algebraically" in propositional logic?

texts:
The biconditional operator $\iff$ of Propositional Logic can be defined by the identity
$p \iff q \equiv (\lnot p \lor q) \land (\lnot q \lor p) \quad (1.1)$
Use the identity $(1.1)$ and identities from the list on page 2, to show algebraically that
$p \iff q \equiv (\lnot p \land \lnot q) \lor (q \land p)$
State which identity you are using at each step.

What does this question mean by asking to "show algebraically"? I have tried referring to my notes and online search but no luck with a definition! These propositions are already algebraic, are they not? Having some issues understanding the wording of the question. This is from a mock university test. I'm assuming it wants me to demonstrate using a truth table?


texts:
Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

  If h(n) is always lower than (or equal to) the cost of moving from n
  to the goal, then A* is guaranteed to find a shortest path. The lower
  h(n) is, the more node A* expands, making it slower.


texts:
You are given a 40x40 grid. Each point of the grid is either 0 or 1. You are also given an infinite amount of 1x40 rectangular slabs.

How to find out the minimum number of slabs required to cover all the points which have a value 1?

NOTE: The 1x40 slabs can overlap with each other.


texts: Deterministic Nonfinite Automaton - Longest Block of Ones

texts:
How to Think About Algorithms - Jeff Edmonds

Exercise 2.2.2

The problem asks to find  $\sum$, Q, δ, s, and F of this program if we see it as an automaton. Edmonds characterized this as deterministic non-finite automaton since 'n' is not bounded.

$\sum$ is {0,1} but I'm not sure how to model Q and the transition functions.

One guess is just simply Q = { q[p_max, q_max, length_max, p_current, length_current] }, with each of the 5 variables taking a value in the set of size around n ( { 1, 2, 3, ... , n} ), which will have O(n^5) states

but even if I use this brute force approach I can't easily define transition functions that determine the next state based on current state and the input read each iteration (0 or 1).

The biggest difficulty is modeling conditionals. When you are at a state q_1, the next state seems to be defined not just by 0 or 1 input but also by the length variables.

He didn't provide any solutions and I did a lot of research but still lost.

Any suggestions?


texts:
Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$.
Can S be solved with oracle access to only one problem in $NP$?

That is, can B and C somehow be combined into one problem in $NP$ (thus showing S is in $P^{NP}$)?


texts:
Is QMA known to contain Co-NP?
If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)


texts:
In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), highest common factor (hcf), or greatest common measure (gcm), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

Given an integer N. Now Find how many GCD(A,B)=B Where 1≤A≤B≤N
For example,for N=3 the result will be 5.It can be found in the following way.

GCD(1,1)=1 OK

GCD(1,2)=1

GCD(1,3)=1

GCD(2,1)=1 OK

GCD(2,2)=2 OK

GCD(2,3)=2

GCD(3,1)=1 OK

GCD(3,2)=1

GCD(3,3)=3 OK

Here we get 5 combination where GCD(A,B)=B
But how can I calculate it for 1≤N≤10^9 efficiently?


texts: What exactly representational bottleneck in InceptionV3 means?

texts:
I am trying to understand the concepts behind the InceptionNet V3 and got confused with the meaning of representational bottleneck. They said

  One should avoid bottlenecks with extreme compression. In general the
  representation size should gently decrease from the inputs to the outputs
  before reaching the final representation used for the task at hand.

and one thing I get from this is that we should not use polling or convolutions with large strides. But when I arrived in the section 5 (Efficient Grid Size reduction) they said that doing polling before the convolution violates that mentioned principle but doing polling after convolution don't violate.

Doing the left one we decrease the number of features by a factor of one quarter and then the features are doubled. In other words a decrease of 35*35*320*0.75 = 294K features and then an increase of 17*17*320 = 92.48K features. And doing the one in the right the features are doubled and then decrease by the same factor of one quarter. And doing this one, the real decrease in the pooling phase is bigger: 35*35*640*0.75 = 588K.

So, why one approach violates the principle and the other don't? What am I missing here?

Another thing that confused me is the solution found by them to avoid the computational cost of doing conv. before polling.

The polling part of the solution is not violating the principle of representational bottleneck once it make the exactly same operation with dimensionality reduction mentioned earlier?


texts: Relation between Undecidable problems and NP-Hard

texts:
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)
I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.

And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)


texts: Is it possible that $\mathsf{L} = \mathsf{NP}$?

texts:
When I studied computer science 10 years ago, it was still an open question whether $\mathsf{L}$ and $\mathsf{NP}$ are truly different classes. Is that still the case or has the inequality been proven in the meantime?

(I know this is a somewhat stupid question, but there's nothing about it in the complexity zoo, and googling L and NP is surprisingly ineffective ;-))


texts: Array algorithm to fill an array in equal but alternate binary choices as close as possible given an already fixed configuration

texts:
Stuck on a problem with my roommate and can't seem to find any parallels to this.
The problem is simple to understand: you have two possible binary options: T or F.
You are given an array which already has some of these options filled out e.g.
[T, X, X, F, X, T] - (Here X means unfilled)
What we want to do is to fill this array out such that the number of Ts and Fs are as equal as possible, and that they are as close to alternating as possible. The key word is approximation here, they don't have to be strictly equal or strictly alternating. Some leeway is fine.
Any thoughts?


texts: Attribute grammars: How are attributes implemented?

texts:
I've read about attribute grammars, but I haven't found out, how are the attributes often implemented?

To me they scream objects (of classes), but they could be also variables.

But are there any general rules as to how the attributes should be implemented in a practical implementation? Or is it free form?


texts: Greedy Best-First Search Performance for Tree and Graph Space

texts:
I am currently reviewing the GBFS algorithm and when looking at its completeness I am confused between the difference of it being

not optimal in Tree Search for Finite and Infinite Spaces
that it is optimal for finite Graph State spaces but not when infinite?

Anyone able to help pick this apart and explain it?


texts: Derive Turing Machine with high level description

texts:
So I have been going over Turing machines for my revision and came across an old worksheet with the question:

Derive a Turing Machine using high level description with stages to decide on the following language {<,>|           }.

I thought I understood Turing machines and CNF until I came across this but I can't figure it out. There is no answer sheet for this so I was wondering could someone answer it with steps to guide me through it so I can understand?


texts: Are the Before and After sets for context-free grammars always context-free?

texts:
Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the start symbol of $S$. Let $\operatorname{SF}(G)$ be the set of sentential forms of $G$.

Let $\alpha \in \operatorname{SF}(G)$ and let $\beta$ be a substring of $\alpha$ - we call $\beta$ a fragment of $\operatorname{SF}(G)$. Now let

$\operatorname{Before}(\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in \operatorname{SF}(G) \}$

and

$\operatorname{After}(\beta) = \{ \delta \ |\ \exists \gamma . \gamma \beta \delta \in \operatorname{SF}(G) \}$.

  Are $\operatorname{Before}(\beta)$ and $\operatorname{After}(\beta)$ context-free languages? What if $G$ is unambiguous? If $G$ is unambiguous, are $\operatorname{Before}(\beta)$ and $\operatorname{After}(\beta)$ also describable by an unambiguous context-free language?

This is a followup to my earlier question, after an earlier attempt to make my question easier to answer failed. A negative answer will make the encompassing question I'm working on very hard to answer.


texts:
In StarCraft Brood War, a map's maximum dimension in either the X or Y direction is 256 cells. A map's dimension is required to be a multiple of 32. Each cell is 32 pixels in both directions (And probably some path finding limitations) and I assume this is the reason for the previous requirement. Thus 256*32=8,192. But when we're talking about the addresses of the game, where does this number come from? What bit size is this number being stored in? 4? 8? 16? (Or, alternatively, is it being stored in multiple addresses being "patched together" so to speak, like in other games?)

From my own (limited) experience with looking at the RAM of games in emulators or through something like Cheat Engine, I'm accustomed to an address being either 4 or 8 hex numbers long (Such as 015F or 015FFA2B)


texts: How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?

texts:
I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the helper methods in my calculations.

If I have an array with a fixed size of 32 indices, and I have a function that sums up the elements in that array, will that function be $O(n)$, or $O(1)$?  I think that a function that sums up the elements of an array is $O(n)$ because each element of an $n$-length array must be visited, but if the function only sums up arrays of length 32, is it still $O(n)$?


texts:
I found in some exercise in computation the following step:

I can't understand why is it equal terms, based of what I know about De morgan's law:

OR should be replaced by AND
where $w=\varepsilon$ come from


texts: The optimal way to reverse engineer a binary classification problem

texts:
I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it.

In a scenario very similar to popular binary classification machine learning contests, competitors are required to submit their answers to the test set containing N data points. The accuracy of the submission will be announced. The competitors can then submit a new answer, and the new accuracy will always be published, no matter improved or not.

If the competitor has no information about the test set at all, what is the optimal way (in the sense that the least submissions are needed) to crack the challenge?


texts: What kind of formal semantics can describe HTML and CSS? Are there endeavours to do this. HTML/CSS layouts are espcially complex, so formalization can be of help.


texts: How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?

texts:
Admittedly, homework.

For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this formula, for example $C_1=x_1\wedge \neg x_3\wedge x_4$

The tasks is to do this in a little bit more sophisticated way than to choose a random assignment, see if it satisfies the formula, repeat N times. More specifically the tasks tells us to:

Uniformly at random choose a clause $C_i$ in $\phi$.
Set the values of the variables in $C_i$ so that $C_i$ is satisfied.
Set the values of the remaining variables randomly.
In this way sample only satisfying assignments and sample all of them.

I fail to understand: ALL OF THEM? If I want to sample ALL satisfying assignments then I'm not sampling, but rather I'm counting?

Further the task asks:

For a given assignment $p_i$ what is the probability of sampling $p_i$? That's an easy question: $\frac1{2^{n-m}}$ where $n$ is the number or distinct variables in $\phi$ and $m$ is the number of variables in $C_i$. Or am I wrong?
How you can use the result of the previous question (the previous question was to sample trivially as I described above) to construct an estimate for the number of satisfying assignments? I don't know.

Well, I can check if this random assignment satisfies any other clauses than $C_i$. But how can I use the result?

My Googling yielded this page: http://theoryapp.com/dnf-counting-and-the-monte-carlo-method/ But this is even more confusing for me. Instead of choosing the clause $C_i$ uniformly, the site tells us to "pick up a clause $C_i$ with probability $P_i=\frac{\left|S_i\right|}{\sum_{j=1}{l}\left|S_j\right|}$, where $S_i$ is the collection of assignments satisfying $C_i$ and $l$ is the amount of clauses in $\phi$ and then pick up an assignment from $S_i$." But then we are told to "Check whether this assignment satisfies $\phi$. Finally, count the number of satisfying samples; denote the count by $M$". This is nonsense, each assignment that satisfies clause $C_i$ for any $i$ must necessary satisfy the whole formula?

Admittedly, this basic course on probability and statistics is the first course where I feel like a total idiot.

Any tips? I'm loosing hopes to be able to figure this out on my own.

Finally, I'm not sure, is this question more appropriate on scicomp.stackexchange.com?


texts: How to show $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ is not context-free using pumping lemma

texts:
I've been struggling with this problem for quite a while now and don't really understand what to do for the pumping lemma here.
We have the language $L = \{0^{i}1^{i^{2}}| i \ge 0\}$ and we need to prove that it is not context-free by use of the pumping lemma.
Would someone be able to help explain how to use the pumping lemma to show it is not context-free for this language?


texts:
I have a background in physics and have taken some few classes online in Machine learning. But I really do not understand how this Robot lawyer  can work:

A 19-year-old made a free robot lawyer that has appealed $3 million in parking tickets

I am very interested in this type of artificial intelligence but I have no idea what to start reading about the topic.

Have somebody any idea of what type of algorithm he is using?

Here is what the article says:

  Browder programmed his robot based on a conversation algorithm. It uses keywords, pronouns, and word order to understand the user's issue. He says that the more people use the robot, the more intelligent it becomes. Its algorithm can quickly analyze large amounts of data while improving itself in the process.

Can the same algorithm also make the answer based on law data?


texts: What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?

texts:
The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace d[u] + weight(u,v) < d[v] with d[u] + weight(u,v) <= d[v]. What would be an example of the algorithm working incorrectly with that replacement?

def dijkstraShortestPath(G,s,t):
  d[v] = Infinity for all v in G.vertices
  d[s] = 0
  unsureVertices = G.vertices
  while len(unsureVertices) > 0:
    u = a vertex in unsureVertices so that d[u] is minimized
    if d[u] == Infinity:
      break
    for v in u.getOutNeighbors(): //all v are in unsureVertices
       if d[u] + weight(u,v) < d[v]:
         d[v] = d[u] + weight(u,v)
         v.parent = u
    unsureVertices.remove(u)
  if d[t] == Infinity:
    return "Can't reach t from s!"
  path = []
  current = t
  while current!= s:
  path.append(current)
  current = current.parent
  path.append(current)
  path.reverse()
  return path


texts: Why does computer have branch and jump instructions

texts:
I could guess why computers have arithmetic operations like add, sub, and mult instructions. It is to compute numbers, but I don't get why branch and jump instructions exist.
I am asking what theory or purpose for implementing branch and jump instructions is there?
I've tried to get rid of branch and jump instructions and what effect it will cause on the computation, but I could not get the result.


texts: Linear programming formulation of cheapest k-edge path between two nodes

texts:
Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges.

Here is my attempt using a flow network:
\begin{align}
\min \sum_{(i,j) \in E} c_{ij}x_{ij}
\end{align}
\begin{align}
\sum_{j \in V} x_{ji} - \sum_{j \in V} x_{ij} &=
\begin{cases}
    -1,& \text{if } i = s\\
    1,              & \text{if } i = t\\
0, & \text{otherwise}\\
\end{cases} && \forall i \in V\\
\sum_{(i,j) \in E} x_{ij} &= k &&\\
x_{ij} &\geq 0 && \forall (i,j) \in E\\
\end{align}

However, this doesn't eliminate cycles which are disjoint from the $s$-$t$ path. I can use subtour elimination constraints like in the Miller Tucker Zemlin formulation of the Travelling Salesman Problem but this enforces a simple path making the problem harder than it should be.

Any ideas on alternative formulations?

Update: This is part of a slightly bigger formulation here, where $z$ is a slack variable which scalarizes multiple objectives with a rectified-linear function:

\begin{align}
\min \sum_{k \in K} z_{k}
\end{align}
\begin{align}
\sum_{(i,j) \in E} c^{k}_{ij}x_{ij} - z_{k} &\leq 1 && \forall k \in K\\
\sum_{j \in V} x_{ji} - \sum_{j \in V} x_{ij} &=
\begin{cases}
    -1,& \text{if } i = s\\
    1,              & \text{if } i = t\\
0, & \text{otherwise}\\
\end{cases} && \forall i \in V\\
x_{ij} &\geq 0 && \forall (i,j) \in E\\
\end{align}

Solutions are integral when solving with a linear program, but suggestions for more efficient algorithms would be appreciated.


texts: Computational complexity of coefficients

texts:
I have some recurrence relationships I use to compute some coefficients of a series. I want to know what the time complexity of computing these is. Suppose I know the coefficients $a_0,...,a_n$, and I want to compute $c_0,...,c_n$ as follows

$ c_{n}=\begin{cases}
e^{b_{0}}, & n=0\\
\frac{1}{n}\sum_{k=1}^{n}kb_{k}c_{n-k}, & n\geq1
\end{cases}$

where

$b_{n}=\begin{cases}
\frac{1}{a_{0}}, & n=0\\
-\frac{1}{a_{0}}\sum_{i=1}^{n}a_{i}b_{n-i}, & n\geq1
\end{cases}$

So far this is what I have. If we know $b_0,...,b_{k-1}$ then $b_k$ can be computed in $O(k)$ time, so to compute $b_0,...,b_{n}$ takes $\sum_{k=0}^{n}O(k)=O(n^2)$ time.

Now suppose that we know $b_0,...,b_{k}$ and $c_0,...,c_{k-1}$ then it takes  $O(k)$ time to compute $c_k$. Thus to compute $c_0,...,c_{n}$ it takes $\sum_{k=0}^{n}O(k)=O(n^2)$. Ofcourse we have to take into account the time it takes to compute  $b_0,...,b_{n}$ which is $O(n^2)$.

So can I conclude that the time it takes to compute $c_0,...,c_{n}$ is

$O(n^2)+O(n^2)=O(n^2)$??


texts: Would proving P≠NP be harder than proving P=NP?

texts:
Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP.

Let Q be one of known NP-hard problems.
To prove P=NP, we need to design a single polynomial time algorithm A for Q and
prove that A correctly solves Q.

To prove P$\neq$NP, we need to show that
no polynomial time algorithm solves Q.
In other words,
we have to rule out all polynomial time algorithms.

I have heard people say this makes the second more difficult task
(assuming that it is really true).

  Is there a reason to think that proving P=NP (assuming that P=NP)
  would be easier than proving P$\neq$NP (assuming that P$\neq$NP)?


texts: Which kind of branch prediction is more important?

texts:
I have observed that there are two different types of states in branch prediction.

In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay.
In the instruction pipeline, where the fetching is more problem since the instructions do not actually get executed till later.

Which of these is very important (as in which of these really matters in the CPU now-a-days)? If both are equally important or in case the second one is more important then Why do we not have two instruction pipeline (probably of half the length ) and then depending on the branches, just choose one of them and then again start the population from the beginning?


texts:
It's conceptually simple to state what an "unordered pair" is supposed to be in set theory. Yet, in homotopy type theory I have trouble formalizing this. A first naive try in agda syntax:

data UPair (A : Type ℓ) : Type ℓ where
  mkpair : (x y : A) → UPair A
  uswap : ∀ a b → mkpair a b ≡ mkpair b a

This fails, since there are actually two different paths between e.g. mkpair 1 2 and mkpair 2 1, that is we have uswap 1 2 and sym (uswap 2 1). Again, these can be forced equal by a one-higher path constructor, but one would have to continue for ever.

Obviously, if A is an n-truncated type, we can stop at some point. Generally truncating at some level fails because it might forget some non-trivial paths in A. Take for example the set-truncation of the above type and A = S¹, the circle, then the path i. mkpair (loop i) base is lost and identified with refl (mkpair base base).

Can we generally write down the type of unordered pairs of a parameter A : Type ℓ? Can the resulting type live inside the universe ℓ?

Clarification:

Let A· = (A , a) be a pointed type. Define UPA· = (UPair A, mkpair a a) as a pointed type. I would then expect Ωₜ UPA· ≡ UPair (Ωₜ A·). These correspond to singleton sets.

Let A∙ = (A, a, b) be a bipointed type with a ≢ b. Then I expect that the map (a ≡ a) × (b ≡ b) → mkpair a b ≡ mkpair b a given by (pa , pb) → (λ i → mkpair (pa i) (pb i)) ∙ uswap a b is an equivalence.


texts:
I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the parse table it had conflicts. Am I doing some thing wrong or is the answer given wrong?

My texbook defines:

  For LL(1) Grammar if there is left recursion or left factoring then that grammar is not LL(1) grammar if this applies to this grammar then it is not a LL(1) grammar

$E \to E+T \mid E$

$T \to T$#$F \mid F$

$F \to (E) \mid i$

I also have one more question: "Is there a Grammar which can be LL(1) but not LALR(1)"


texts: Minimum changes to obtain an alternating sequence

texts:
I've been studying dynamic programming lately and came across a problem that is, I believe (might be wrong, though), a modification of the classic longest alternating subsequence (LAS) problem.

But instead of asking you what is the maximum length, this problem asks what is the minimum number of changes you would have to do to any V[i] element such that the whole input array becomes an alternating sequence. Changes can only be subtractions, not additions.

Example: 2 5 8 6 1 2

In this case the minimum number is 1: you can make the 8 a 4, for example.

The answer could be 0 as well if the whole sequence is already alternating.

For solving the LAS, I know we need to retain in DP[i][0] the size of the longest alternating subsequence ending at i for which the last element is greater than the previous one and in DP[i][1] the same when the last element is lesser than its previous. And we build this by iterating from 1 to i-1.

But how can I find the changes I'd need to make to turn the whole sequence into an alternating one?


texts:
The Wikipedia entry about "Alphabetical order", says:

To determine which of two strings of characters comes first when arranging in alphabetical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order.

I am intrigued specifically about:

If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order.

Is there any formalisation of this process ? Perhaps, in the realm of First Order Logic, Mathematics or Computer Science ?
What is the reasoning behind these rules ?

I could not find any references. I will appreciate any insights into this.


texts: What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class?

texts:
I understand how you can use a contradiction in regard to a DPDA to show a language has finitely many Myhill-Nerode equivalence classes, but what is the method used to show each string of a language accepting palindromes is in its own Myhill-Nerode class?

Thanks


texts:
Given:

$L_1 = \{0^k1^k|k \in \mathbb{N}\}$

$L_2= \{1\}$

$L_1 \leq_p L_2$

There must be a function

$$f:Σ^* \rightarrow Σ^*$$
such that
$$w \in L_1 \iff f(w) ∈ L_2$$

Let's say a word in $L_1$ is mapped to $1$ in $L_2$.
If it is not in $L_1$ it is mapped to $0$.

So each word in $L_1$ is mapped to $1$.

So the input for the Oracle of $L_2$ would always be $1$?

Is this a correct Karp reduction?


texts:
I am currently reading a survey paper on the multiplicative weight update meta-algorithm. I am not quite sure what they mean by "meta-algorithm". Is it simply a general algorithm that can be used for different purposes?

I couldn't find any exact definition for this term, though I have found examples of meta-algorithms such as Boosting in machine learning.


texts: Detect a specific frequency in an input signal without using fourier transform

texts:
I am trying to learn FPGA programming, and I would like to analyze an audio input.
I would like to know what kind of frequencies are present in the signal but without using Fourier transform - there are two reasons for this.
First one is I dont need to know the exact frequency of the incoming signal, and the second reason is simple - I have just started learning FPGA and Fourier transform is beyond my skill level to implement.
So, are there any methods of checking if a signal of given frequency is part of the audio input?
Say, I would like to know if any signal in frequency range 3KHz-5KHz is present in the input.
How can such a problem be approached?
Edit.
My first thought was to use a pair of low and high pass filters to do the job, but I am not sure if this would work well, because they only pass through the current signal.


texts: Greedy Heuristic for the Traveling Salesperson Problem

texts:
We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any given point and connect it with the nearest point and then connect that to the next nearest one until all points are covered - then going back to the first point.

Where "P" is the starting and ending point.

The second approach, which gives the optimal answer, is the "closest pair of points" or "Engstes-Paar-Heuristic". I don't understand how this approach works because from the looks of it, you simply make a straight line but I don't understand this approach.

Sorry about the possible name changes, it's originally in German.


texts:
What kind of algorithm can have $O(1/n)$ complexity, where $n$ is a natural number?

Or, is there any algorithm that the time it takes decreases when the data input increases?


texts: Boolean variable that captures whether an inequality holds

texts:
I have an integer linear program with variables $x_1,\dots,x_n$.  I have an inequality $a_1 x_1 + \dots + a_n x_n \ge b$ that I care about; it may or may or not hold.

I want to introduce a boolean variable $y$, with the intent that $y=1$ if this inequality holds or $y=0$ if it doesn't.  How can I write linear inequalities to constrain $y$ to take this value?

All of $a_1,\dots,a_n,b$ are constants.  I know upper and lower bounds for all of the $x_i$'s.


texts: Is this problem decidable? (computation of $M_1$ longer than $M_2$ on every input)

texts:
Is this problem decidable?

Given two representations of Turing machines $R(M_1), R(M_2)$, is the length of the computation of $M_1$ longer than the length of the computation of $M_2$ on every input?

My guess is not decidable. I am not sure, however, how to justify it.

I tried this: Lets enumarate all possible words from $\{0,1\}^*$ and run $M_1$ and $M_2$ simultaenously. If $M_1$ accepts/rejects and $M_2$ is still running, output NO. If $M_2$ stops and $M_1$ is still running, check next word. However, if neither $M_1$, nor $M_2$ do not halt on the word, I am stuck and cannot decide it (because I will get an instance of the halting problem for each combination of word and Turing machine).

Is this reasonable or is it a wrong assumption?


texts: NP-completeness of a Generalized Version of Subset Sum

texts:
I am curious about the NP-completeness (or if not, an efficient algorithm) for the following generalization of the subset sum problem:
In subset sum, we are given a number $t$ and a collection $S$ of integers with $|S|=n$, and ask if we can use a subset $S'\subseteq S$ to sum up to $t$. We can generalize the problem by extending the operation allowed: instead with only addition, we can permit addition together with multiplication and parenthesization.
It seems with the extended case, the usual reduction technique of encoding 3SAT in the problem breaks down, as parenthesization together with multiplication is difficult to handle (on the other hand, it seems like multiplication itself is easier to handle, as it can be expressed as a summation of identical elements).
Intuitively this generalized problem looks much harder; however, I haven't managed to find a way to prove its NP-completeness. I'm wondering if it can be indeed proven to be NP-complete, and what sort of reduction technique could be used in this problem.


texts: Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

texts:
Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two NFA, one being in state $r$ and other being in $s$, if there is a transition of the type $r \xrightarrow{\epsilon} s$. If there is a cycle of the type $r \xrightarrow{\epsilon} s \xrightarrow{\epsilon} q_1....\xrightarrow{\epsilon} q_k \xrightarrow{\epsilon} r$, where $q_i$ are some states of NFA, then it's no use remembering another NFA in state $r$ upto the point where input has been read till alphabet $w_i$.
If a PDA ( non-deterministic ) is in state $r$ ( and input is read till $w_i$ ) and there exists a cycle $r \xrightarrow{\epsilon,\epsilon \to a} s \xrightarrow{\epsilon,\epsilon \to a} q_1....\xrightarrow{\epsilon,\epsilon \to a} q_k \xrightarrow{\epsilon,\epsilon \to a} r$ ( where transition $\epsilon,\epsilon \to a$ means thatnothing after $w_{i}$ is read from input, nothing is popped or read from stack and alphabet $a$ is pushed onto the stack ) then before reading the next input alphabet $w_{i+1}$ there will be infinite PDA in states $r,s,q_1,...q_k$ because unlike the NFA although the states are finite stack contents can be different ( infinite possibilities ), if I am not wrong.

As with NFA and PDA the power of non-determinism comes from $\epsilon$ transitions. So I assume that non-deterministic Turing machine also gets it's non-determinism from $\epsilon$ transitions like NFA and PDA ( more like PDA ). I know that a deterministic Turing machine can simulate a non-deterministic one ( I know the proof which uses bread-first search ). But now I am doubtful as to how that is possible. Because if a cycle of the type in PDA above, exists in the state diagram of the non-deterministic Turing machine then before reading the next symbol $w_{i+1}$ the deterministic Turing machine even when simulating a configuration in some branch of non-deterministic Turing machine ( while bfs ) would have to keep track of infinite Turing machine (  again the states are finite but the symbols on the tape have infinite possibilities ).
So how exactly non-determinism in defined in case of Turing machines ? Am I misunderstanding something trivial ? Do non-deterministic Turing machines use $\epsilon$ transitions ?

I am sorry for my trivial doubts. If anything is incorrect I can update my question.


texts: What are current approaches to auto-parallelisation?

texts: I am looking for answers which provide short overview of models and current state of research for auto-parallelisation of sequential code.


texts: Troubles understanding this Interval Scheduling question

texts:
Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.

Consider the Interval Scheduling problem. We have seen that the “earliest deadline-first” greedy algorithm finds an optimal set of jobs.

Consider now the “shortest-job-first” greedy
algorithm, which initially sorts the jobs by increasing duration — i.e., so that f(1)−s(1) ≤ f(2)−s(2) ≤
. . . ≤ f(n)−s(n). It then considers the jobs in this order; each job considered is added to a set A (initially
empty) if it does not conflict with any job currently in A. Thus, at the end, the algorithm has produced a
set of non-conflicting jobs A. (In contrast, the “earliest-finish-time-first” algorithm initially sorts the jobs
by increasing finish time — i.e., so that f(1) ≤ f(2) ≤ . . . ≤ f(n). Other than the initial sorting of jobs,
the two algorithms are the same.)
We have seen that the “shortest-job-first” greedy algorithm does not necessarily produce an optimal
set of jobs.

In this problem you must prove that it produces a set of feasible jobs whose size is at least
half the size of an optimal set. Thus, in some sense, the set of jobs produced by this algorithm is not too
bad compared to the optimum. (Contrast this to the “earliest-start-time-first” algorithm, which produces
a set of jobs whose size can be an arbitrarily small fraction of the optimal.)
More precisely, let m be the size of an optimal set of jobs, and let A be the set of jobs computed by
the shortest-job first greedy algorithm. Prove that |A| ≥ m/2.

Hint. Let B be any optimal set of jobs and j be any job in A. What is the maximum number jobs in B
with which j conflicts?


texts: Card dealing problem with constraints (blacklisting),

texts:
A friend of mine and I are trying to teach a bot play a card game (bela)

We are using monte carlo tree search (MCTS) to estimate the probability of winning hand in regards to multiple possible (!important) card configurations.

We are randomizing both plays and possible card configurations. The problem is not all card configurations are possible in the later stages of the game, according to the rules (e.g. you have to follow the card suit cast by the first player if you can do so).

So, not to iterate over every (illegal) combination of cards, we have come up with an idea of blacklisting certain cards for a certain player, so that the algorithm doesn't go through card combinations that cannot happen according to rules.

To summarize, we need to deal N cards over M players in such a way that no player receives a card they shouldn't receive according to rules (each player has its own set of blacklisted cards).

The main problem is, reshuffling cards until the constraints are met doesn't seem feasible (even after millions of iterations we never satisfy all the constraints (factorials)).

Can you point us to a direction which would efficiently solve our problem?

Thanks!

Edit #1 as per comment below:

Problem definition in summary(second attempt): There are n players and m cards available(n=3, m=x*3, x E (1,8)). Each player has its own list of illegal cards(cards she/he shouldn't receive). How to spread m cards over n players so no violation of constraints occurs. Constraints are satisfied if no player received a card that is subset of hers "blacklisted" cards.

We need efficient algorithm that doesn't just randomly spawn card configurations until constraints are met.


texts:
Let $G=(X\cup Y, E)$ be an unweighted bipartite graph. We are given that for every $W\subseteq X$ it holds that $|W|\leq |N(W)|$, where $N(W)$ is the neighborhod of $W$ in $Y$ (aka Hall's marriage condition).

My goal is to find a subset $W^*\subseteq X$ with $|W^*| = |N(W^*)|$, if such a subset exists (obviously it need not exist). Since I'm not aware of a formal name for this property, I'd refer to such a $W^*$ as a saturated set.

Questions:

Is this property widely known? Does it have a different name?
Assuming the marriage condition holds, it is straightforward to show that every union of saturated sets is also saturated. One interesting problem is to find the maximum saturated set. I describe below a somewhat naive solution with runtime $O(|V|\cdot |E|)$, but I suspect it can be solved even faster. Any idea?
Allegedly, a weakly easier problem is to find a saturated set, not necessarily the maximum one (again, assuming the marriage condition holds). Can we solve this problem faster than $O(|V|\cdot |E|)$?

Edit:
Here's a sketch for the algorithm I mentioned above: Assume the marriage condition holds for $G$. Then, as said, with a bit theory work we can show that

Lemma: Let $G$ be a bipartite graph satisfying the marriage condition. Then, every union of saturated sets is also saturated.

The Lemma suggests that there exists a unique maximum saturated set. The question can hence be stated differently:

  Given a node $x\in X$, determine whether it participates in a saturated set or not.

If the answer is yes, then it also participates in the maximum saturated set. The pseudo algorithm goes as follows:

Run the Hopcroft–Karp algorithm to find a maximal matching $M$ that covers $X$ in $O(\sqrt {|V|}|E|)$ time. Such a matching exists due to the marriage condition.
For every node $x\in X$,

Temporarily add a node $x'$ to $X$, which is connected to every neighbor of $x$. Call the graph we obtain $G_x$.
Notice that $M$ is a partial matching of $G_x$ that is almost maximal (up to one edge); thus, we can find a maximal matching $M_x$ for $G_x$ by finding an augmenting path in $G_x$, in $O(|V|+|E|)$ time (same details as in Hopcroft–Karp).
If $|M|<|M_x|,$ continue. Else, if $|M|=|M_x|$, add $x$ to the returned set.

The analysis follows from first principles. If there exists any saturated set $W\subseteq X$ with $x\in W$, i.e., $|W|=|N_G(W)|$ then
$$
|W\cup \{x'\}|=|W|+1 = |N_G(W)|+1=|N_{G_x}(W)|+1,
$$
so $W\cup \{x'\}$ violates the marriage condition in $G_x$. Consequently, $|M|=|M_x|$. We can analogously show that if $x$ does not participate in any saturated set, then $|M_x|=|M|+1$.


texts: How to show that these two disjoint sets $A$ and $B$ exist

texts:
I came across this problem which asks to show the existence of two disjoint Turing-recognizable sets $A$ and $B$ such that no decidable set $C$ can separate them...
In this case, a set $C$ is said to separate $A$ and $B$ if $A \subseteq C$ and $B \subseteq \overline{C}$ ... If only $A$ is Turing-recognizable, then we could easily set $A$ to be $A_{TM}$ and $B$ as $\overline{A_{TM}}$. However, in this case both $A$ and $B$ are Turing-recognizable .... I think that $A$ and $B$ should be constructed using diagonalization, but could not think of a way to do it ... Any help ?


texts: Known algorithms: subgraph with highest/lowest diameter?

texts:
Let be $G=(V,E)$ a directed graph without self loops, where each node has an out-degree of at least $k$.

We want to find a $E'\subset E$, so that $G'=(V,E')$ has the following properties:

Almost all nodes in $G'$ have an out-degree of: $l \le k$
$G'$ has the highest possible diameter

The almost all nodes part is to relax a bit the problem.

e.g. if $G'$ is a DAG, the last $l$ nodes can't have an out-degree of $l$. But a DAG, or a linear graph, can have a high diameter.

There is also the similar problem, where we want to find $G'$ with the lowest possible diameter.

I have some ideas on how to solve these problems, without finding the optimal solution. In particular the variant max diameter seems doable.

However I'd like to know if there is some literature about these (or similar, or simpler) problems. And if there are algorithms to find optimal or approximated solutions.
I couldn't find anything.

Thanks


texts: Fast implementation of basic addition algorithm

texts:
Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being added. Design the algorithm to be fast, so that it avoids doing excessive work on carries of zero.

I encountered this question looking over last year's final for my algorithms course. I'm not really sure how to answer it, although it seems like it isn't a very challenging question.


texts: Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

texts:
I'm currently reading the elements of programming book and have come across a section I don't quite understand

  A computational basis for a type is a finite set of procedures that enable the construction of any other procedure on the type. A basis is efficient if and only if any procedure implemented using it is as efficient as an equivalent procedure written in terms of an alternative basis. For example, a basis for unsigned k-bit integers providing only zero, equality, and the successor function is not efficient, since the complexity of addition in terms of successor is exponential in k

Given the successor function , wouldn't addition be linear? e.g. getting get the result of a + b the complexity would be O(b) starting from a? I know this is likely not the case as I'm sure the book knows more about what it's saying than me, but can someone explain why this operation would be exponential?


texts: Is a sum of n terms considered O(1) or O(n)?

texts:
Say I have $n$ numbers in an array and I have to compute the sum of those numbers. Is the complexity considered as $O(1)$ or $O(n)$?

Clarification

Say I have 10 constants, I could precompute the total and claim that overall, the complexity is $O(1)$. Yet, if I have 10 assigned variables, I would have to perform 10 additions to compute the total, which implies $O(n)$.

Another way to formulate my question is: Does $O()$ depends on the number of unknowns (i.e. variables) only? How are constants considered?


texts:
Given DTIME($n^2$) contains NTIME($n^{100}$) show that P=NP.

I think it's supposed to be straightforward but I just can't see it.

Take $L$, a language in NP. $L$ has a Turing machine which runs in NTIME$(f(n))$. If $f(n)$ is $\Omega(n^{100})$ it's obvious, but what about $O(n^{100})$?


texts: Evaluating two different Algorithms, which one will scale better?

texts:
I'm evaluating two different algorithms to choose one for my implementation, they just do calculations on top of arrays, get some input of $n$ elements, and produce some output of $m$ elements, and I'm looking for an opinion about which one will scale better.

The output they provide given the input is exactly the same on both cases, the computation time for the second is slightly better, maybe a 20%...

As I have the code from both, I have been able to get some counts out of the main loop, where the processing happens (they are iterative).

The first Algorithm behavior reminds me a lot merge sort, for a input $n$, every iteration just process half of the elements, so for $n=4000$ each iteration process half of the elements until there is no more $i_1=2000,i_2=1000,i_3=500,...,i_x=1$

The second Algorithm is just linear, I did the same count thing, and with input $n=4000$, looks like it just process $\approx n/c$ (some $c$) elements per iteration, so $i_1=266,i_2=266,i_3=266,...,i_x=266$

(They do not depend on the numerical values in the input)

Which one will you choose?


texts: Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?

texts:
I'm looking for a problem that allows me to generate random instances which:

Take arbitrary time to compute (i.e., I can generate an instance that I know would take at least 10 days to solve in an Intel I7);
Is inherently sequential (no matter how many processors you throw at it, it won't be solved faster than 10 days);
Can produce N (say, 2^256) equiprobable outputs;
Given an output, it is easy to verify it is correct.

Example:

Find the smallest N such that sha256^N(seed) < K. You can configure K so that it would take no less than X days given current hardware. The final hash can be any one of 2^256 possible values. But verifying is hard: the only way to prove an N is correct is re-doing the whole computation, so it doesn't really fit.
Find an N such that sha256(seed+N) < K. You can configure K so that it would take no less than X days given current hardware. The final hash can be any one of 2^256 possible values. It is easy to verify the output is correct. But it is embarrassingly parallel.


texts: Why don't nodes carry as many pointers as possible in a skip list?

texts:
From this main picture explaining how skip lists work from Wikipedia, we see that some nodes carry different amounts of pointers to other parts of the list:

Wouldn't it make more sense to have every node carry 4 pointers (since this is the height of this specific example)? For instance, node with value 2 would also have pointers to nodes 4, 6 and 7 and not just to node 3.

I'm asking because I need a data structure that would allow me to traverse the list as quickly as possible. Having each node carry as many pointers as possible would allow me to carry out lots of parallel requests. Also, each arrow in my implementation is actually a network call, so if I can achieve higher concurrency to retrieve all 10 items would be best.


texts: Dynamic Programming - How to get the solution from the predecessor matrix

texts:
Whenever I'm coding a dynamic program , I usually struggle building the solution from the predecessor matrix . How should use the predecessor matrix to find the solution ?

Thanks,


texts: Find the element $x$ that maximizes $f(x)$ for $x \in \sum A_i$

texts:
I have a collection of sets $A_i \subset \mathbb{Z}$ where I want to find the global maximum after combining the sets using sumset.
The sumset is
$$ A + B = \{ a + b : a \in A , b \in B \} $$
and $R$ is the combination of each set $A_i$
$$ R = \sum A_i $$
Then with some function $f : \mathbb{Z} \rightarrow \mathbb R$, I want to select the element $x \in R$ such that $f(x)$ is maximized.
Practically, each element in a set is a 64 bit unsigned integer, so each set is bounded by $M = 2^{64}-1$ and the output of a sumset operation never produces an element exceeding that bound. Also each set is sparse.
I have a solution for this but I am looking for optimizations or different approaches. I currently use sparse polynomial convolution based on Johnson's Sparse Polynomial Arithmetic (1974) [1]. In summary, I am implementing sparse polynomial convolution first, and then iterating over terms of that result to select the element such that $f$ is maximized.
My current method is to represent each set by its characteristic function. Then the sumset operation becomes the convolution of two of polynomials. Normally, FFT would be used next but since the set is sparse, using a dense array to hold the polynomial produces many zeros, so I instead resort to using a sparse polynomial where each is a sorted array of integers representing the exponents with non-zero coefficient. This step is computed by distributing the terms of one polynomial over the other to create a set of polynomials multiplied by one term. Since each term is represented solely by the exponent, this is just adding to each value in an array, which maintains the sorted property. Then I combine them using a $k$-way merge using a heap. Then, after each convolution is performed ending with the resulting polynomial $r$, the function $f$ is mapped over the exponents of $r$, and the exponent that maximizes the value of $f$ is the solution.
I've implemented this approach and it works well on small cases, but as each $|A_i|$ increases, $|R|$ increases exponentially and won't fit in machine memory. The issue is that I am generating the entire set $R$ whereas I only need a single element of $R$. A followup would be finding the elements $x_k$ that result in the top $k$ values of $f(x_k)$, in which case generating the entire set $R$ allows it to be ranked for any value $k$.
The most recent research I found on sparse polynomial multiplication is Roche's What Can (and Can’t) we Do with Sparse Polynomials? (2018) [2], which continues from Johnson's work and notes that there hasn't been any significant change in this problem since the idea of using a heap.
[1]: http://www.cecm.sfu.ca/~mmonagan/teaching/TopicsinCA11/johnson.pdf
[2]: https://arxiv.org/pdf/1807.08289.pdf