texts: Not sure how to interpret the question: how to find egg-breaking height

texts:
I have the below homework question as an assignment of my Computer Science Foundation class.

  Throwing eggs from a building. Suppose that you have an N story building, and plenty of eggs. Suppose also that an egg is broken if it's thrown off floor F or higher, and intact otherwise. First devise a strategy to determine the value of F such that the number of broken eggs is ~lg N when using ~lg N throws, then find a way to reduce the cost of ~2lg F when N is much larger than F.

I'm not entirely sure what the question is asking for. I believe, and what I attempted, is to provide an algorithm as a solution that has a runtime of log N.

From the description of the problem, I attempted to write a binary tree implementation. I'm not sure if this is correct. I'm not asking for an answer, but perhaps some guidance on what the problem is looking for.


texts: Combinatory Logic formula obtained from lambda term, proof?

texts:
I translated the following $\lambda$-term:

$z(\lambda b.ba)(tt)(\lambda y.y)$

in the following CL formula:

$z(CIa)(tt)I$

through the Markov algorithm.

Now I'd like to prove the translation was correct, and I know that's done by applying arguments to such CL formula and execute each constant by its rule.

If I apply it this way

$z(CIa)(tt)I y b$

the I constant is run first, since it has the required arguments, thus obtaining the following:

$z(CIa)(tt) y b$

but I don't know how to further proceed, "pushing" the $b$ inside, in order to "activate" the $C$ constant.


texts:
I got stuck in Ladner's Proof while reading "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. Pardon me if I'm missing something really obvious here but the authors do the following:

For every function $H\colon\mathbb{N}\to\mathbb{N}$ define

$$SAT_H=\{\psi01^{n^{H(n)}}: \psi \in SAT \ and \ n=|\psi|\}$$

Now $H$ is defined as follows:

$H(n)$ is the smallest number $i<\log \log n$ such that for every $x\in\{0,1\}^*$ with $|x|\le \log n$, $M_i$ (TM encoded by binary representation of $i$) outputs $SAT_H (x)$ within $i|x|^i$ steps. If there is no such number $i$ then $H(n)=\log \log n$.

$M_i$ outputs $SAT_H (x)$ is equivalent to the statement that: The machine $M_i$ on an input $x$ outputs a 1 $\iff$ $x \in SAT_H$.

My question is:
By definition of $SAT_H$, every string in it will have length exactly $n+1+n^{H(n)}$.

For every string $x\in\{0,1\}^*$ with $|x|\le \log n$, we note that $|x|<n+1+n^{H(n)}$. So there does not exist any string $x\in\{0,1\}^*$ with $|x|\le \log n$ and $x \in SAT_H$.

This would mean that the machine $M_i$ should trivially output 0 for every string $x\in\{0,1\}^*$ with $|x|\le \log n$. But then how would such an argument be used for a proof? Where exactly am I going wrong?


texts: Intersection of context free with regular languages

texts:
The intersection of a context free language L with a regular language M, is said  to be always context free. I understood the cross product construction proof, but I still don't get why it is context free but not regular.

The language generated by such an intersection has strings that are accepted both by a PDA and a DFA. Since it is accepted by a DFA, shouldn't it be a regular language? Plus, if the intersection is regular, it also implies context free, since all regular languages are also context free.

Can someone explain to me why the language obtained by such an intersection is not regular?


texts:
In the book "The New Turing Omnibus", an excercise reads as the follows:

  "Show that no finite automaton can accept the language consisting of
  all words of the form $a^n b^n, n=1,2,3,...$ The formula represents
  $n$ a's followed by $n$ b's."

I have no idea why a finite automaton shouldn't accept such words. Couldn't one simply design an automaton that reads a word and always outputs "Accepted"?


texts: How can I prove that my greedy algorithm for least guards is optimal?

texts:
This is the problem:

  An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of 10 meters (5m on the right, 5m on the left with him being in the middle).

No matter where the artworks are put in the hallway we want the minimal amount of guards as possible.

My Greedy Algorithm:

Start at the beginning of the hallway.
Find the position of the closest artwork from the entrance.
Put the guard at position closest artwork + 5m ahead.
Eliminate all the artworks covered by the guard.
Re-do the process but this time start where the range of the previous guard ended

Now how do I write a proof for this? How do I prove that my algorithm is indeed optimal? Which mathematical proof techniques can I use?


texts: "Most Similar Vector Problem" on an Integer Lattice

texts:
I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum.

Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$, I would like to find an integer vector $v \in L$ such that the angle between $u$ and $v$ is as small as possible. That is, I would like $$v \in \text{argmax}_{w \in L} \frac{u.w}{\|u\|\|w\|}$$

Here, the objective function is just the cosine between the vectors $u$ and $w$.

I am wondering if this problem can be formulated as a well-known integer lattice problem (such as a closest vector problem). If so, is there an algorithm that I could use to solve it? Any help or resources would be greatly appreciated.


texts: Time complexity of optimal algorithm for solving this problem

texts:
Given an $N\times N$ matrix $M$ whose elements are integers, find the largest element that occurs in each row of the matrix.

I tried using hashtable as follow:

Idea is to use hash-table(let's call it $ht_1$) to keep track of count of occurrence of each element.
Now, To handle case where element repeats in same row we use another hash-table(call this $ht_2$). Now before performing increment in $ht_1$ we check whether this element is already occurred in this row itself or not. If not then and then we perform increment in $ht_1$.

Then once you finish processing whole array as just described make one more pass on array and this time keep track of max element which have exactly $N$ occurrence as noted by $ht_1$.

So overall this runs in $O(N^2)$ expected time.

But Because use of hash-table worst case time complexity is still $O(N^4)$.

Now, I wonder can I do better than this? Means is there any way to solve in $O(N^2)$ in worst case.

Note: There is no other constraint on this.


texts: Appearance-based methods for object detection

texts: Object detection can be divided into Feature-based methods and Appearance-based methods. I want to find out what the most common Appearance-based methods are for object detection. There is not much information about which are the most common approaches, therefore it would be useful to hear from someone who have experience in computer vision and object detection algorithms in particular.


texts: Why are comparisons so expensive on a GPU?

texts:
While trying to improve the performance of my collision detection class, I found that ~80% of the time spent at the gpu, it spent on if/else conditions just trying to figure out the bounds for the buckets it should loop through.

More precisely:

each thread gets an ID, by that ID it fetches its triangle from the memory (3 integers each) and by those 3 it fetches its vertices(3 floats each).
Then it transforms the vertices into integer grid points (currently 8x8x8) and transforms them into the triangle bounds on that grid
To transform the 3 points into bounds, it finds the min/max of each dimension among each of the points

Since the programming language I am using is missing a minmax intrinsic, I made one myself, looks like this:

procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      if c < min:
         min = c

   return (min, max)

So on the average it should be 2.5 * 3 *3 = 22.5 comparisons which ends up eating up way more time than the actual triangle - edge intersection tests (around 100 * 11-50 instructions).

In fact, I found that pre-calculating the required buckets on the cpu (single threaded, no vectorization), stacking them in a gpu view along with bucket definition and making the gpu do ~4 extra reads per thread was 6 times faster than trying to figure out the bounds on the spot. (note that they get recalculated before every execution since I'm dealing with dynamic meshes)

So why is the comparison so horrendously slow on a gpu?


texts: 3SAT solvable in polynomial time...but with exponential tuning?

texts:
Suppose there exists an algorithm that solves 3SAT in a polynomial number of steps.  However, this algorithm requires some 'tuning' parameters, and the value of these tuning parameters take an exponential number of steps(given the input) to determine.

Would this place 3SAT in P? (since it can be solved in polynomial time given the appropriate parameters)

Or would 3SAT remain in NP? (since it still takes an exponential number of steps to ultimately solve)

Edit: just to clarify, the question is about whether or not 3SAT would 'move' to P or 'remain' where it currently is...NP.  If 3SAT 'moves' to P it obviously would still be contained in NP.


texts: how can i know if a First order logic sentences is valid or unsatisfiable or neither?

texts:
i have trouble with understand this type of questions ,

i know how i can determine if the sentences is valid or unsatisfiable in Propositional logic , but in FOL i can't

for example , i have the following sentences in FOL :

1 = 2

the professor said this is neither valid nor unsatisfiable

but , i think it is always unsatisfiable , because 1 != 2 !!!

can someone explain to me how can i answer this type of question

thank you all


texts: Proof of correctness of the XL-algorithm for polynomial systems

texts:
Section 12.4 of G.V. Bard's Algebraic Cryptanalysis discusses the XL-algorithm (first reported by N.T. Courtois and A. Shamir in Efficient algorithms for solving overdefined systems of multivariate polynomial equations and Courtois' thesis).

The technique is based on the following. Say we have a system of polynomial equations such as:

$$
1+x+y+z+wz+yz = 0\\
x+z+wx+wy+wz+xy+xz+yz=1\\
w+y+wx+xz+yz=0\\
x+wx+wy+wz+yz=1\\
$$

This is the example in Bard's book and I am guessing we are in $GF(2)$. The system is clearly underdetermined. The algorithm says that you should enhance the degree of the equation from $d$ to $D>d$ (usually $D=d+1$ or $D=d+2$) and make a list $L$ of monomials of degree $D-d$ or less starting with the monomial $1$ of degree $0$. You then take those monomials and multiply them by the above system and solve the linearized system.

The resulting system has $m\lvert L\rvert$ where $m$ was the initial number of equations.

Is there a proof of correctness of the method? Is there a simple way to prove that it is correct mathematically?


texts: Calculating fractions of accesses from various levels of memory? (L2 - Main)

texts:
I'm currently studying computer architectures module, and during the workshop I came a across a series of questions that I struggled to being to answer.

The question goes;

*You have an L1 data cache, L2 cache, and main memory. The hit rates and hit times for
each are:
50% hit rate, 2 cycle hit time to L1.
70% hit rate, 15 cycle hit time to L2.
100% hit rate, 200 cycle hit time to main memory.

What fraction of accesses are serviced from L2? From main memory?

My answer: (200*0.7)/15 = 9.3

To be completely honest, I don't know how to approach these type's of questions, I'd be grateful if someone could point me to resources.


texts: Eigenvalues of an induced subgraph of a random graph

texts:
Suppose $G$ is a random graph on $n$ vertices where each edge appears with probability half. Suppose someone looks at the resulting graph and chooses an arbitrary subset $W$ of vertices of size $k>\sqrt{n}$.  How do the eigenvalues of the induced subgraph $G[W]$ behave?
In other words can we say that for every $W$ of size $k$, the eigenvalues of $G[W]$ will be close or related to that of a random graph from $G(k,1/2)$?


texts: How to find a condition which leads to deadlock in non-reentrant locks

texts:
A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

A. x=1,y=2
B. x=2,y=1
C: x=2,y=2
D: x=1,y=1

Though, answer is option D but is there any possibility to have deadlock in other 3 options. If yes, then what it is because not able to visualize other options. Kindly explain.


texts: Can we prove using pumping lemma that language F = {$a^ i b ^j c ^k$ | i, j, k ≥ 0 and if i = 1 then j = k} is not regular?

texts:
I am currently solving a problem in which we have to show that we can not prove using pumping lemma that the language mentioned in the question is not regular.Here is the full question

Consider the language F = {$a^i b^j c^k$ | i, j, k ≥ 0 and if i = 1 then
j = k}.
a. Show that F is not regular.
b. Show that F acts like a regular language in the pumping lemma. In other        words, give a pumping length p and demonstrate that F satisfies the three conditions of the pumping lemma for this value of p.
c. Explain why parts (a) and (b) do not contradict the pumping lemma.

But, I am able to prove it using pumping lemma that language is not regular. For that I take:

pumping length as 3
x:a ; y:b ; z:c
$xy^lz$ ∈ F for l = 1
$xy^lz$ ∉ F for l > 1

Is there some problem with the above shown proof or the question is wrong.


texts: What is the use case of multi-type-parameters generic interface?

texts:
Previously, I ask a similar question, but the answer given only demonstrates the usage of multiple-type-parameters(MTP) data structure, but not MTP generic interface.

Based on my experience, generic interface is useful for generalizing algorithms. For example, the sorting algorithm can be defined as such:

// Java code

interface Comparable<T> {
    Boolean compareTo(T other)
}

void <T extends Comparable<T>> sort(List<T> elements) {
    // body
}

So, the code above demonstrated the usage of single-type-parameter generic interface.

However, I have not encountered any use case for multiple-type-parameter generic interface up until now.

Thus, I am hoping that some one could provide me some use cases regarding multiple-type-parameter interfaces.

Also, if possible, please explain how multiple-type-parameter could improve some situation.

(For example, the Comparable interface allows the sort function to be generalized, so that one do not need to define multiple sort function for different types of element)

P/S: I ask this question because I am considering whether to include MTP generic interface in my new programming language.


texts: Can xor and xnor for quasi-reduced BDDs be implemented just like union?

texts:
Below is an algorithm for union of two quasi reduced BDDs p and q resulting in r.

bdd Union(bdd p, bdd q)
  local bdd r;
1 if p=0 or q=1 then return q;
2 if q=0 or p=1 then return p;
3 if p=q then return p;
4 if Cachecontainsentry⟨UnionCODE,{p,q}:r⟩ then return r;
  //p.lvl = q.lvl in case of quasi reduced BDDs
5 r ← UniqueTableInsert(p.lvl, Union(p[0], q[0]), Union(p[1], q[1]));
6 enter⟨UnionCODE,{p,q}:r⟩ in Cache;
7 return r;

Since there is no variable skipping, p.lvl is always equal to q.lvl. I have a question about this algorithm.

If I want to implement Xor or Xnor for quasi-reduced BDDs, can it be done the same way as union or should I implement the expression pq' + p'q where q' = !q.


texts: Regular Expression as basis for creating this grammar

texts:
I made a right-linear grammar from a regular expression:

The alphabet is:

$Σ = \{a, b, c\} $

Regular expression:

$r = cc^{*}(ba)^{*}bb$

My solution, it seems a little too short like I'm leaving something out. Maybe someone can see where I went wrong on the right-linearity:

$ S \to cA $

$ A \to b a A | B | cA $

$ B \to bb $


texts: My professor asks this question: Binary Search tree has Rotation Method to prevent it from degenerating into a linear structure (unbalanced tree). Why is there no need for such method for Binary Heaps?


texts: How to generate a random reducible flow graph?

texts:
Is there any known algorithm to generate a random reducible flow graph (single root, single sink) with a given maximum cardinality $N$?

Ideally, the distribution should be uniform over the set of reducible flow graphs of cardinality $\leq N$.
Alternatively, it could be uniform over the possible topologies of reducible flow graphs of cardinality $\leq N$ (e.g. graphs that are isomorphic or that differ just for the length of some chain can be considered equivalent).
The exact distribution is not dictated by my use case (random testing), so I would also be interested in other non-uniform distributions that assign a non-zero probability to any possible topology.

Two approaches that I found so far are:

Randomly generate a flow graph (same considerations as before regarding the distribution), test if it is reducible, repeat until it is reducible.
Construct a graph from a grammar, for example the one described in Sec. 7 of "Flow Graph Reducibility", randomly choosing the rule to apply and recursively applying the algorithm to generate the sub-graphs.

I'm pretty sure that the time complexity of (1) would be too high to be used in practice (let say, $N=1000$). (2) is feasible, but it lacks forward edges that exit from a loop, which are crucial in my use case. It would be possible to define another grammar, but then the question is whether the new grammar can actually generate any graph topology.


texts: What graph problems are hard to solve even for a small number of verticies?

texts:
The only graph problem that I worked with is TSP. It is exponentially hard, but there are tons of heuristics which allows to find near to optimum solution.

So I was wondering, is there any graph problems (or optimization problems which could be mapped onto graph) that are exponentially hard and can not be solved (even approximatly) efficiently for small and mid-sized systems? (let's say 10-20 verticies)


texts: Term for an approximation that becomes better as the problem grows

texts:
For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and $\textrm{Max}$ is the exact maximal value.

What term describes an algorithm in which the approximation factor is a function $F(n)$ of the problem size, and $F(n)\to 1$ as $n\to \infty$?


texts:
Address 0000 stores 0xde
0001 stores 0xad
0002 stores 0xbe
0003 stores 0xef
Treat the data stored as 2 16 bit integers, what are the two values stored?
I thought the answer would be 0xadde and 0xefbe but I was wrong. Why?


texts: Implementing a linear programming feasibility test in 3D

texts:
I have a little problem which requires determining if a system of linear inequalities in 3D is infeasible. The constraints (or oriented planes) are added one by one, so there is an opportunity to stop as soon as the system becomes infeasible. Basically this:

class LPSolver {
    // add constraint ax + by + cz + d < 0 (plane equation), and return false if infeasible
    bool add_constraint(int a, int b, int c, int d);
};

Coefficients a, b, c, d happen to be integers and x, y, z are true reals (computing x, y, z is not required and even undesirable to avoid numerical error).

From thinking about the problem, I have figured out that at most 3 constraints are required to show infeasibility. This seems to point to a solution where the class should keep track of 3 constraints or planes, whose intersection point is in the feasible space. When a new constraint is added, the fast path is that this point (intersection of 3 planes) satisfies the new constraint, in which case nothing needs to be done and we keep track of the same 3 constraints. Otherwise, we need to recompute the constraints. The new constraint just added is definitely one of the 3 constraints to track, and we need to search for the other two, but this seems to require quite a bit of cleverness to avoid exhaustive search.

This seems to be an interesting problem and I would like to implement a solution myself rather than using a library, but I don't have formal training in convex optimization so I'm looking for a reference implementation, pseudo code or a research paper.


texts: Difference between HSI and YCbCr for pattern recognition by color

texts:
I am doing a project on face detection in C#. I want to find the skin area by using skin color segmentation. For that purpose, I have to extract the skin area.

I know I can use HSI or YCbCr, but what is the exact difference between these?


texts:
I'm studying advanced database and I can not understand some concepts related to the join.
I hope I'm in the right place to post my doubts, otherwise I'm sorry.

I realized that to make the equijoin there are several families.
In particular, the family that is based on the Cartesian product includes three main methods: nested loops, nested blocks and nested scans.

The nested loop method iterates on the outer relation R (tipically the smaller one) and for each tuple of R, it scans the internal relation S and applies the join condition.
Then it just use the join definition: Cartesian product + selection.
The cost of this process is:

C = |R| + |R| * |S|

You can get an improvement if instead of considering the tuples, consider the pages.
In this case the cost is:

C = P_R + |R| * P_S

Why? I do not understand.

From what I remember of Operating Systems, the logical memory is divided into pages and the physical memory in frames, where the pages are of the same size of the frames.
This is done to permit the non-contiguous allocation of files.

A tuple instead of what corresponds? I guess as a record (one line) of a table, but in this context what is it?

The nested blocks method is a further improvement because in main memory maintains a block of tuples of R.
The improvement is obtained by scanning S only once for each group of tuples of R.
A version of this charging algorithm in the tuples of R memory, then proceeds to S and examines the memory to find the S tuples that match any tuple of R.
This reduces the number of necessary S scans.
In this case the cost is:

C = P_R + P_R * P_S

I must admit that I did not understand very well this algorithm.
Someone could explain it better?

Thus a block is a set of tuples? And a set of tuples form one page?
I'm very confused.

Maybe some sketch could help me, I have not found that showed the tuples.

Thank you all

If I understand correctly, this is how I imagine the logical memory, physical memory, pages and frames:

Nested loops (tuple)

Again, as I understand it:

I apologize but I have not yet understood the nested loop (pages) and nested block :(

What do you mean with "We can achieve some improvement checking the tuples stored on one page of relation S for each record in relation R"?

And with "In Block nested approach each block in the inner relation S is read once for each block in the relation R which gives you the desired cost"?

I feel a bit stupid, sorry.


texts: Graph coloring with fixed-size color classes

texts:
I'm interested in coloring a graph, but with slightly different objectives than the standard problem. It seems like the focus of most graph-coloring algorithms (DSATUR etc) is to minimize the number of color classes used.
My goal, in contrast, is to maximize the number of color classes of fixed size N.
As a concrete example, say I have a graph with 100 nodes, and I'd like to color the graph with color classes of size N = 30. With an optimal algorithm and the right graph, I could find 3 such groups that color 90 total nodes, with 10 nodes left over. A lesser algorithm might only produce 2 such groups, with 40 nodes left over that cannot be colored with a size-30 color class.
I figure I can solve this problem with a Greedy Algorithm, but it won't be optimal. Or I could model this in a constraint solver, but it might not employ some clever graph-specific tricks that could come in handy.
Does this specific problem have a name? Or an established algorithm to solve it? Thank you!
EDIT:
It was rightfully pointed out that my question is ambiguous! I can explain much more thoroughly, my apologies for the confusion.
First, let me define the size of a color class. I've seen this terminology elsewhere but might be using it incorrectly. The size of a color class is the number of nodes assigned to that color. I will denote this: size(C_i) = <number of nodes colored C_i>.
Now, to define a fixed size color class. This is a color class with size N. To use the example above, I'm interested in colorings with colors such that size(C_i) = 30.
As far as the optimization objective: I want to color a graph to maximize the number of size-30 color classes. If you'll permit me some Python pseudocode:
n_size_30_colors = len([c for c in colors if size(c) == 30])
maximize(n_size_30_colors)

To complete the example, take these two possible colorings of a graph with 100 nodes. Each number represents the number of nodes colored by that color:
Coloring 1: {55, 25, 20} (n_size_30_colors = 0)
Coloring 2: {30, 30, 20, 20} (n_size_30_colors = 2)
Coloring 3: {30, 30, 30, 10} (n_size_30_colors = 3)

Even though Coloring 1 uses fewer colors, Coloring 3 is optimal because it returns the most size-30 color classes. The size-55 color class in Coloring 1 is "wasteful" in that those 25 extra nodes are not useful; an optimal solution for this problem would distribute those nodes to other color classes, hopefully yielding more size-30 colors.
I hope this clarifies things somewhat, and thanks again!


texts:
How come $REC$ languages are included in $NRE$.

The definition of a language in $REC$ is . $L \in REC$ if there is a turing machine $M$ that recognizes the language $L$ and that stops on any given input.

It makes sense that $REC$ is included in $RE$;

$L \in RE$ if there is a turing machine $M$ that recognizes the language $L$ but may stop on some inputs;

The inclusion still makes sense right now.  But when we go to the $NRE$ i find it hard to understand;

$L \in NRE$ if there DOES NOT EXIST ANY turing machine $M$ that can recognize the language.

How can a language in $REC$ be in $NRE$ if $REC$ assumes that such a language would have a turing machine that stops on every intput yet a language that is $NRE$ must not have any turing machine that can recognize it?

Could the given definition of $NRE$ be wrong?
An explanation would be welcomed!


texts:
Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$ such that $dist_T(s,t)=dist_G(s,t)$, i.e., $s$ and $t$ are connected by a shortest path.

How would you approach this problem?

Note: it seems that if there is only a single shortest path, we could simply reduce the weight of each of its edges by $1/n^2$ and find a simple MST. However, this doesn't seem to work when there are many short paths.

A generalization of the problem which is also interesting would be getting a set of terminal pairs $\{s_i,t_i\}_{i=1}^k$ which are required to be connected by a shortest path in the MST. This variant might prove to be NP-hard.


texts: What are applications of the levels of the Chomsky hierarchy?

texts:
I've recently finished a course on languages in computer science, so we covered characteristics of regular, context-free, decidable and semi-decidable languages. While that is all well and good, we never went into any detail on what applications of this knowledge are (other than compilers being context-free language recognizers). I've tried googling for answers but wasn't able to find anything relevant. I'm wondering if someone can just explain what current applications for each 'type' of language are and perhaps link further material for reading.

Thank you.


texts: Is this modification of the subset-sum problem NP-complete?

texts:
Suppose we have input $s_1,\dots,s_n \in \mathbb Z$ and $t \in \mathbb Z$. We want to know if there exist variables $x_1,\dots,x_n$ in which each $x_i=1/2^k$, where $k \in \{0,1,2,3,4,\dots,\infty\}$, such that $s_1x_2+\dots+s_nx_n=t$.

Is this problem NP-complete? Is it solvable in polynomial-time?


texts:
I'm having trouble understanding the point of Subnet Masks.

I was reading a nice article on Tech-FAQ on the topic, but it has left me a bit confused.

When I first heard about Subnets, it was explained to me that these are small independent networks connected to the main internet at one point. For example in an office building there would be a subnet for the thousand computers there, instead of wasting a thousand regular IP addresses.

However, from this article it seems a subnet is a collection of computers with similar IP addresses and a subnet mask is used to describe which bits are the ones in range of your subnetwork.

Example from the article:

So what's the point of this? We still don't save IP addresses and if I want to contact Dave at Company X and Bill at the same Company X I still have to send messages to 105.23.44.89 and 105.23.44.90.

How do subnets make life any easier or contribute anything?


texts: Please provide me a solution of Max-Heapify using Recursion Tree

texts:
I tried my best to solve the recurrence relation.

$T(n) \le T(2n/3) + \Theta(1)$

Using the recursion tree.

I could reach out the boundary condition when at depth i:

$i= \log_{3/2}n$

Can someone please help me out in adding the costs and taking out the upper-bound.
I know at each depth the cost is increasing by a power of $2$, i:e- $2^i$.

What I have done so far is adding up the costs:

$\sum_{i=0}^{log_{3/2}n-1} 2^i+ \theta(log_{3/2}n)$.

Please correct me if I am wrong.
Thank you.


texts: What are ways that you might analyze relations extracted from text

texts: In the coursera NLP course, Dan Jurofsky says you might want to extract relations from text to serve as input to other algorithms. What are examples of ways that researchers have used or might use relations extracted from text as the input for later "downstream" algorithms?


texts: Is there a zero-knowledge protocol for bit vector agreement?

texts:
Suppose Alice knows a secret vector of $N$ bits, say $A=\langle a_1, a_2, \ldots, a_N\rangle$ and Bob similarly knows $B=\langle b_1, b_2, \ldots, b_N\rangle$.  Is there a protocol that allows them to determine the number of bits that their vectors have in common, without revealing any additional information about what the vectors are or what positions agree?

That is, we would like Alice and Bob to be able to determine the size of the set $$X(A,B) = \{i\mid a_i=b_i\}$$ without learning anything else about $A$ and $B$, and without revealing any information to an eavesdropper.

Obviously if $X(A,B) = N$ or $X(A,B)=0$, then Alice now knows Bob's vector and vice versa, and in other cases each gets some incomplete information about the other vector, but that is unavoidable.  Perhaps that means that a true zero-knowledge protocol is by definition impossible.  But  I would like the information leakage to be no greater than this necessary amount.


texts:
Do URI's, as defined in rfc3986, form a regular language?

How can I tell?

There's a BNF grammar provided, but I don't know how to check that it has a unique representation of every URI, or that it describes a regular language.


texts:
I need some advice on how to determine the runtime of this loop :

s=0
 for ( i=1 , i <= 2^m ; i=i*2 ) {
   s++
}
return s

With

$C_1$ =  actions performed once before entering the loop and
$C_2$ = actions performed one after entering the loop,

I see that $T(m) = C_1 + C_2 \cdot 2^m$.

How can I  determine $T(m)$?


texts: Generate a dataset for binarization of text in images

texts:
I want to generate a dataset of binarized masks of scene-text images to use them to train a model. I have no previous experience in dataset synthesization especially related to font-rendering.

Can anyone provide me some links to articles/blogs/related-github-projects?


texts: Number of maximal cliques in graphs without common neighbourhoods

texts:
Let's consider a graph $G(n)$ of $n$ vertices such as no two vertices in $G$ have the same exact neighbors (different open neighbourhoods to be more specific; I wonder if this kind of graphs have already a name). Which is the maximum number of maximal cliques of such graphs? Is that amount polynomically bounded?
Additional related question: which extra conditions must such graphs have to be planar? This is in fact a related question because planar graph does indeed have a polynomically bounded amount of maximal cliques.


texts: Why should 3-Opt be used over 2-opt for solving TSP?

texts: I know the working of 2-opt and 3-opt local search algorithm. But I could not find any example where solution improvement is not possible using 2-opt but 3-opt. I am looking for a proper explanation along with diagrams where TSP solution is not improved by 2-opt but 3-Opt can improve it.


texts: Machine Learning: how to correctly calculate gradient descent for simple linear problem

texts:
So, I was trying to learn machine learning, and, after watching a couple of Andrew Ng's lectures decided to try and write a simple piece of code to determine what someone's salary would be based on the number of years they worked at a company by this simple linear function:

salary = w1 * numberOfYears + w0

I then used the least square method to calculate the error between the predicted results and the actual results and tried to minimize the error of the gradient of that function:

Error = (1/2) [ sum of (predicted - actual)^2 for all samples (x, y) ]

The predicted value is the one calculated by the linear equation above, and actual = y.  w1 and w0 are weights to the function that are set to some initial values (0 and 0 for example) and are changed to decrease the error throughout the process of gradient descent.

Steps to the algorithm:

1)  Choose some (random) initial values for the model parameters (w).
2)  Calculate the gradient G of the error function with respect to each model parameter.
3)  Change the model parameters so that we move a short distance in the direction of the greatest rate of decrease of the error, i.e., in the direction of -G.
4)  Repeat steps 2 and 3 until G gets close to zero.

In my implementation I have this code:

for(int i = 0; i < numSamples; i++) {
    double error = prediction(data.X[i]) - data.Y[i];
    while(nearsZero(error)) {
        for(int j = 0; j < w.length; j++) {
            w[j] -=  0.1 * error * data.X[i][j];
        }
        error = data.Y[i] - prediction(data.X[i]);
    }
}

If I run this with only one sample (meaning ignore the outermost loop), then the weights continuously subtract a value that is continuously nearing infinity (or -infinity).  If I change the w[j] -= ... to a w[j] += ... then the function works for the first value and sets initial w that will solve it for one sample (but that isn't what I was supposed to do as far as I can tell).  Also, when I add multiple samples the numbers just do the same thing on the second sample that they were doing on the first sample when I had -=.

I feel like gradient descent doesn't make sense here because it was demoed on graphs like z=y^2+x^2, which looks like a big bowl with one central min that it will find eventually.

On the graph in my problem the graph looks like a parabola that extends to infinity in both directions and has infinite min values along a line.

I'm not sure what it is that I am doing wrong, but I would assume that it's something to do with my understanding of the problem.  If anyone knows how to get this working I would appreciate it.

EDIT: Updated data.X[i] in the while loop to data.X[i][j].  Each data point i should have some value Y[i] and an array of X values at X[i].


texts:
I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following:

We can define the distance between two points in ways other than euclidean. In the plan, the $L_m$ distance between points $p_1$ and $p_2$ are given by the expression $(|x_1-x_2|^m+|y_1-y_2|^m)^{1/m}$. euclidean distance, there, is $L_2$-distance. Modify the closest pair algorithm to use the $L_1$-distance, which is also known as the Manhattan distance.

I understand its an easy modification, however when I've been comparing my intuition with that of solutions provided online (e.g. https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html), all I can find is that they all point to the number of points in the $\delta$ x $2\delta$ is increased to 10 (from 8), adding one point to the middle of both squares formed by the rectangle (here marked with red below):

Can anyone explain to my why this is the case? Intuitively I cannot see why it should be the case that the number of points in the rectange should increase, when switching to another $L_m$-distance?

The Manhatten distance $\geq$ Euclidean distance from what I can see in all instances, but why should this infer, an increase in points found in the $\delta$ x $2\delta$ space.

What am I missing?


texts:
I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as:

  the field of study that gives computers the ability to learn without
  being explicitly programmed

?

You can find many, many references to this definition on the internet, but I haven't been able to track down the source. Some give it as his 1959 paper on checkers, but I don't find any such definition there.


texts: Is it decidable whether a linear language contains a square?

texts:
A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings).

Question: Is it decidable whether a linear grammar generates a square?

What did I do? I know that it is undecidable whether a linear grammar contains a palindrome, and that it is undecidable that a context-free grammar contains a square. Both via reduction from PCP. Given two sequences $(u_1,\dots, u_n)$ and $(v_1,\dots, v_n)$, strings of the form  $u_{i_1}\dots v_{i_k}\#v_{i_k}\dots u_{i_k}$ are linear, whereas those of the form $i_1\dots i_k u_{i_1}\dots u_{i_k}\#j_1\dots j_k v_{j_1}\dots v_{j_k}\#$ are context free.


texts: Is there a solution for this maze problem in polynomial time?

texts:
Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now here comes the tricky part: suppose each room needs a set of keys for you to enter, and inside each room you can find another set of keys. Keys can be repeated and one key may be needed to enter on more than one room. You can only enter the room if you have all keys required.

You have an arbitrarily large number of chests with gold inside and each chest needs one key which can be found in the maze. You already have a set of keys that you can use. You can use a key more than once. The question is: how do you collect the keys you need as fast as possible?


texts: bipartite d regular expender explicit construction

texts:
I am looking for an explicit (and simple) construction of a d regular bi bipartite graph which is an expander. I searched the web and didn't find any sufficient answer.
The only explicit graph I did managed to find(and understand) was the margolis graph, but as far as I can understand this graph is not a bipartite (for example (0,0) has a self edge).

Please help me.


texts: Can a KD tree be used as a decision tree through nearest neighbor queries?

texts: If I were to construct a KD tree representing a sufficiently dense space, could it be used as a decision tree by querying it for the nearest neighbor to the point to classify?


texts: Deterministic vs. Non-Deterministic PDA?

texts:
The following is an example of language $a^nb^n$ where $n \geq 1$

From what I have heard that in finite state machines if you see epsilon moves, then it is NFA otherwise it is DFA. But in this case, the definition was: "If a PDA has more than one paths going accept state then it is non-deterministic PDA" but what about epsilons?

So, Is this an example of Non-deterministic or Deterministic PDA? How to recognize NPDAs from DPDAs? Can I create both NPDA and DPDA for this language as above?


texts: What guarantees Paxos to converge (terminate)? (i.e. not run forever without a consensus)

texts:
I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and was wondering, what guarantees Paxos to converge and not run forever without a consensus/agreement on a value? Is it guaranteed to converge always or is it a probabilistic bound that the probability that it does not converge is really really small?

Because I was reading condition $P2^c$ and it seems possible to me that because of that condition, Paxos might loop forever if we are not careful (I think, maybe I am wrong, but I would love to know why!) Take the following case:

I was a little worried about the case when, say that a majority was close to forming but there is a new node that wants to propose his new value but was unlucky and did not happen to communicate with that growing set that nearly formed a majority (its not a majority yet, but it was reaalllyyy close!). That node was ready to prepare his value but was that unlucky and reasoned "Ok, none of the nodes I spoke to had a value, thus, time to propose my value!" but his sequence number is much higher than the previous one that was forming on the other side and it starts to spread, wouldn't it be because we want to satisfy (b) in $P2^c$? i.e. doesn't it damage the convergence to a decision (never mind the run time, it might never converge...)? Even in the case of a very good quality network..?

Because now this new node has a higher value and his value spreads like a disease and it could happen again, right before it was about to form a majority with his own value. That situation could happen again and again and again no value is decided! Right? What prevents Paxos from being in this situation? Or what is the argument to convince me that its really unlikely to happen many times and that it converges in polynomial time most of the time?

Recall condition $P2^c$ is the following:

$P2^c$

"For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that
(a) no acceptor in S has accepted any proposal numbered less than n,
or
(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S."

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research


texts:
Let $A$ and $B$ be two deterministic finite automata. How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free?

Intuitively, I feel that $L_E$ should not be context-free because we must try each string $\in \Sigma^*$ (where $\Sigma$ is the alphabet) and check if the string $\in L(A)$ or $\in L(B)$. However, this reasoning sounds informal to me. How do I formalize this proof?


texts:
As the functions are of 2 type:1.Pre-defined/library functions,2.User defined functions.

What type of function is main() function?

This doubt comes in my mind while writing a program we define the main() function as we do the others.

Please help!!!


texts: Is there a path of length $k$ between given vertex to a subset of vertices in a connected directed graph

texts:
I am trying to find an efficient algorithm that on input
$ (G,s,A,k) $ returns true iff $G$ is a connected directed graph, $s$ is a vertex in $G$, $A$ is a set of vertices in $G$ and there is a path of length $k$ from $s$ to a vertex in $A$

What is the best run time we can get here?

I am currently stuck with this slow algorithm (there might be some minor problems but the concept is of the importance) $T$ that on input $(G,s,A,k)$:

for all vertices $t$ in $A$:

if $k=1$ and $t$ is a neighbor of $s$ return TRUE

if $k=0$ and $s=t$ return TRUE

for all neighbors $r$ of $s$ return $T(G,r,\{t \},k-1)$

this algorithm is rather slow because it exhausts all possibilities.

*cycles of any size (1 or more) are allowed in the graph and in the paths


texts:
The definition of NP-hard problem in Wikipedia is :
NP-hardness (non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP".

There are NP-hard problems not in NP class. My question (more curiosity) concerns the NP in the definition. Since a NP-hard maybe is not in NP class, why we call it NP-hard?

When we say we have a NP-complete problem, then this problem is indeed in NP class.


texts: Longest path with limited edge traversals

texts: Given a graph where each edge has a capacity, is there an efficient algorithm to find the longest path in the graph which does not pass through an edge more times than its capacity? The exact problem I'm trying to solve is given a list of words, find the longest chain of words such that the last letter of the $n^{th}$ word in the chain is the same as the first letter of the $n+1^{th}$ word in the chain. So the number of vertices would be 26 (the length of the alphabet), and each edge would represent the words that start with the letter which its from vertex corresponds to and ends with the letter which its to vertex corresponds to. The list is about 60,000 words long, so something like $O(cV)$ or $O(cV^2)$ where $c$ is the total capacity would be nice.


texts: Occurrences notation in "Compiling Pattern Matching to Good Decision Trees"

texts:
From Compiling Pattern Matching to Good Decision Trees (Luc Maranget, Proceedings of ML '08, pp. 35–46. ACM, 2008.)

  We also consider the usual occurrences. Occurrences are sequences of integers that describe the positions of subterms. More precisely an occurrence is either empty, written $\Lambda$, or is an integer $k$ followed by an occurrence $o$, written $k\cdot o$. Occurrences are paths to subterms, in the following sense:
  $$\begin{align*}
v/\Lambda &= v\\
c(c_1, \dots, v_a)/k\cdot o &= v_k/o \quad(1\leq k\leq a)
\end{align*}$$

Could anyone explain the occurrences notation a bit?


texts: Determining Number of States in a Turing Machine

texts:
I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. The example (Example 28.1, page 211) reads as follows:

  Here is a TM that accepts the non-context free set $\{a^nb^nc^n \mid
 n\geq 0\}$.

  Informally, the machine starts in its start state s,
  then scans to the right over the input string, checking that it is of
  the form $a^* b^* c^*$. It doesn't write anything on the way across
  (formally, it writes the same symbol it reads). When it sees the first
  blank symbol _, it overwrites it with a right endmarker ].

  Now it scans left, erasing the first c it sees, then the first b it sees,
  then the first a it sees, until it comes to the [. It then scans
  right, erasing one a, one b, and one c. It continues to sweep
  left and right over the input, erasing one occurrence of each letter
  in each pass.

  If on some pass it sees at least one occurrence of one
  of the letters and no occurrences of another, it rejects.
  Otherwise, it eventually erases all the letters and makes one pass
  between [ and ] seeing only blanks, at which point it accepts.

  Formally, this machine has $Q = \{s, q_1, ... , q_{10}, q_a, q_r\}, Σ
= \{a,b, c\}, Γ = \Sigma ∪ \{[, \_, ]\}$

Are they simply creating states based on their informal definition? Or is there some methodology they are implementing that determines the number of states? If there is some sort of methodology, is it a general methodology that can be applied to other Turing machines?


texts: Decomposing a closed walk in a directed graph into cycles

texts:
Let's say I have a closed walk $W$ in a directed graph $D$. Represent $W$ as a list of arcs $(a_1, a_2, \dots, a_k)$. Since it's a closed walk, there may be repeated edges, but the source vertex of $a_1$ must equal the target vertex of $a_k$. My claim is that the multiset of arcs $W'=\{a_1, a_2, \dots, a_k\}$ can be partitioned into sets (not multisets) $W'_1, W'_2, \dots, W'_m$ such that the arcs in each $W'_i$ form a simple cycle.

There is a simple algorithm to output these cycles. Travel along $W$ until you visit a vertex $v$ for the second time. Output the arcs between the two occurrences of $v$ (which form a cycle). Repeat this process until the walk is empty.

I'm using this "walk decomposition" lemma in a paper, and it seems like something that should be easy to find in the literature, but I can't find it anywhere. Can anyone point me in the right direction?


texts: Are type constructors always injectives even in presence of quantified type variables (subtyping)?

texts:
Are type constructors, in a language that feature subtyping and quantification of type variables, like scala or Java, always injective?

That is, is an equivalent of haskell lower function, as seen here, safe in such a language? (even if the implementation use typecasting)

#ifdef LANGUAGE_TypeFamilies
type family Inj f
type instance Inj (f a) = a
newtype Lower a b = Lower { unlower :: Inj a := Inj b }
-- | Type constructors are injective, so you can lower equality through any type constructor
lower :: f a := f b -> a := b
lower eq = unlower (subst eq (Lower refl :: Lower (f a) (f a)))

By quantified type variables I mean, eg. for java:

class F<T extends F<T>> {}

class G<T extends F<? super G<T>>> extends F<G<T>>{}

Where G and F are type constructors and T is a (quantified) type variable.
In the above context the question become:

For every types A and B, if we know that the types G<A> and G<B> are the same type (in the sense of leibnizian equality), can we safely conclude that A and B are the same type?

Subsidiary question: If we cannot generally conclude on type constructor injectivity (eg. due to weird properties of subtyping), what are the properties that type variables must satisfy to guarantee injectivity?

This is a practical question in the context of implementing Leibniz equality for Java.


texts:
I have a question about the Mano base computer. The state diagram, shown below, implies that the output device will set the FGO flag to "1" after the job is done to continue the output activity from the PC (and to zero when device is busy).

But in most cases we don't have anything to do with the output and the flag stays at "1" and the cycle enters the interrupt routine every time.  It seems like this leads to the computer running the interrupt routine most of the time.

Is this a bug in this system or am I missing something?


texts: Time complexity of Sieve of Eratosthenes

texts: Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?


texts: Is the strictly positive condition in Coq and Agda an aproximation?

texts:
Languages like Coq and Agda enforce that their inductive types occur "strictly positively" in their definitions. That is, the type should not occur to the left of an arrow of an argument of a constructor. This is because if no such condition were made the fixed point combinator could be written and the systems would become inconsistent. Ok great but perhaps this is overly zealous in eliminating these kinds of paths to inconsistency. It reminds me of the the difference between Coq and Agda recursion. Agda allows for recursion in multiple arguments where as Coq requires that one of the arguments always decrease. Is there something similar that we can do with inductive definitions?

Is there a better rule that could be used to allow for more definitions?


texts: Optimal encoding scheme for semi-rewritable memory?

texts:
Let's define a "semi-rewritable" memory device as having the following properties:

The initial blank media is initialised with all zeroes.
When writing to the media, individual zeroes can be turned into ones.
Ones can not be turned back into zeroes.

Making a physical interpretation of this is easy. Consider for instance a punch card where new holes can easily be made, but old holes can not be filled.
What makes this different from a "write once, read many" device is that a used device can be rewritten (multiple times), at the cost of reduced capacity for each rewrite.
Implicit assumptions I would like to make explicit:

The memory reader has no information about what was previously written on the device. It can therefore not be relied upon to use a mechanism such as "which symbols have been changed?" to encode data on a device rewrite. That is, the reader is stateless.
On the other hand, different "generations" of the device may use different encoding schemes as the available capacity shrinks.
The data stored can assumed to be random bits.

Sample storage scheme, to demonstrate rewrite capability:
Information in this scheme is stored on the device as pairs of binary symbols, each pair encoding one of the three states of a ternary symbol, or [DISCARDED] in the case where both symbols have been written.
The first generation thus stores data at a density of $\frac{log_2(3)}{2} \approx 0.79$ times that of simple binary encoding.
When the device is rewritten, the encoder considers each pair of binary symbols in sequence. If the existing state matches the one it desires to write, the encoder considers the data written.
If on the other hand the pair doesn't match, it writes the necessary modification to that pair, or in the case where that isn't possible, writes the symbol [DISCARDED] and considers the next pair instead until it has successfully written the ternary symbol.
As such, every rewrite would discard $\frac{1}{2}$ of existing capacity.
For a large number of cycles, the device would in sum have stored $log_2(3) \approx 1.58$ times the data of a simple one-time binary encoding.
(For a variation of the above, one could also encode the first generation in binary and then apply this scheme on every subsequent generation. The loss from the first generation to the second would be larger, and the total life time capacity reduced, but the initial capacity would be larger).
Question:

Is it possible to have a better life-time capacity than $log_2(3)$? I suspect the the real asymptotic capacity is 2.

Can a scheme do better than having $\frac{1}{2}$ capacity loss between rewrites?


texts: Halting problem for polynomial space bounded Turing machines

texts:
A polynomially bounded Turing machine is the one which, on input $w$, uses no more than $f(|w|)$ cells on its tape, where $f$ is a polynomial. For this problem halting is decidable.

I do not understand why is halting decidable for this problem because $f$ is unknown to us.


texts: number of ways evaluation of expression such that value not changed

texts:
one example:

How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among one variable is not correct (i.e: $(i)+j+k$ is not acceptable) ?

as an example for expression $i+j+k$, parenthesis like $i+(j+k)$, $((i+j)+k)$ are correct parenthesis but $(i)+j+k$ is not. I take a complete short example as follows.


texts: Finding the length of the longest increasing path in a matrix

texts:
Problem:

Given a matrix, find the length of the longest increasing path. We can move up, down, left, or right.

Example:

$$
\begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7
\end{pmatrix}
$$

Output: 7

Longest path is 1, 2, 3, 4, 5, 6, 7

Question:

I am not sure if this post is relevant to this site. I having some trouble coming up with a system to solve this problem. I am not too advanced with programming, I am more of a mathematician by trade but I know some stuff about data structure and algorithms.

If possible, an ideal answer for me would be a step by step guide in solving this problem. My initial thought was to find the smallest number in the $(i, j)$ position and start with the first $(i,j)$ position that was found. Then check up, down, left, right to see which number is larger. But then I thought okay what if there are more than 1 position that is larger? I am pretty stuck with this so any help would be useful.

I found solutions to this online but reading other peoples code is nauseating and I don't find it useful at all.


texts:
The type Bool, as in the datatype with just two point constructors true false : Bool and no higher-dimensional constructors, has decidable equality which is easy to prove directly, e.g. via a type family that maps true to Unit and false to Void. Then we can apply Hedberg's theorem to show that Bool is a Set.

What is a direct, elementary proof of IsSet Bool that doesn't go via Hedberg's theorem?


texts: Complexity classes of undecidable Turing Machines

texts:
I'm finding it difficult to find the information online and I can't find the information in my college notes but i'm wondering what complexity-class languages like Atm and Halttm (The TM that always accepts, the TM that always halts respectively) are in. If anyone could explain which class they're in an why that would be great.
Also what about languages like NEtm(langague of TM no equal to null). What langague would that fall into and why. Thanks in advance


texts: How to properly name the two types of RAM in a Paper?

texts:
How do I name VRAM and RAM properly in a paper?
"Video RAM" is clear but the "normal" RAM? Is it called "CPU RAM" or "Processor RAM" or "Main RAM" or totally different?


texts: Why does Travelling Salesman Problem pose the restriction that each vertex can only be visited once?

texts:
According to the wiki page of TSP as a graph problem,

  It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once

Then what if a triangle is given, with two edges weighed $1$ and the third weighed $100$,obviously, the shortest path to visit all three vertices are passing the two $1$-weighed edges twice.

So what's the meaning of such a restriction?


texts: kth nearest vertex in a unweighted graph

texts:
Given an unweighted undirected graph $G$ with $10^5$ vertices and a subset $S$ of special vertices and an integer $k$, I want to find the $k$th nearest special vertex for each vertex.  What algorithm can I use for this problem?

I'm actually thinking of algorithm for finding shortest paths from every vertex to all other vertices (like Floyd-Warshall algo, but in our case graph is unweighted and we need much better performance).


texts:
A question I came across describes a scenario of an information system in a clerical office and states-

"Identify the sets of S={subjects}, O={objects} and P={privileges} for the above
systems of the manufacturing organisation, and model the case using an access
control graph."

Further, the question says-

"Your graph should indicate links representing
overriding or modifying operations."

What is a access control graph? I came across the following 2 diagrams, the latter depicts the BLP model. Which one should be used in this context?


texts: Test two LTL expression trees for equivalence

texts:
Is there an algorithm on how to check if two LTL expressions (represented as binary trees) are semantically equivalent? Since there are many smaller equivalences such as
$a\Rightarrow b \equiv \neg a \vee b$ or  $F(a) \equiv true U a$ as well as commutativity, distributivity, etc. that need to be considered.
My initial idea was to create the truth table for both expressions and compare them. But then the temporal operators would not be taken into account. Creating and comparing the automaton for each expression sounds like it would be rather inefficient.
Is there a better way to do this?


texts: Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

texts: On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to $\log W$, where, I believe, $W$ is the size of the knapsack. Why is the size of the input related logarithmically to $W$?


texts: Why we take decreasing order of finishing times and NOT increasing order of discovery times in kosaraju algorithm?

texts:
We take decreasing order of finishing times in $G^t$ (transpose of Graph G) to know whther the path exists in other direction as shown below. But why can'nt WE take increasing order of discovery time in $G^t$ as i feel it forces to take the path in other direction.
In below figure, in G we took path x and in $G^t$ we see for path y. But the same result i am getting if take in increasing order of discovery times.


texts: Are the sets of all finite automata and pushdown automata countable?

texts: So considering that set of all turing machines is countably infinite, can we also say that set of all FA machines(DFA/NFA) or set of all PDA machines(DPDA/NPDA) are countably infinite, Considering that we can build all of them with Turing machine?


texts: Redundant States During Removal of Null-Moves (Regular Expression to DFA)

texts:
I've had this little doubt bothering me since four semesters now, so I've come here to resolve it. Theoretical CS was probably not the right place to ask.

Coming to the question, my old coursebook (Theory of Computer Science - Automata, Languages and Computation (Eastern Economy Edition) by KLP Mishra) details the conversion of the regular expression -:

$(0 + 1)^* (00 + 11)(0+1)^*$

to a finite automaton. The book details the process as follows:

I am able to grasp the process uptil step (d). I do not understand how (e) was obtained, and there is no explanation given. I tried to convert (d) to (e) by removing null-moves, but I am not able to get (e) - I obtain a bunch of redundant states (extra initial and final states).

It is not possible to use the DFA minimization procedure to obtain (e) after the null-moves are deleted, simply because this isn't a DFA yet - it's still an NFA. Note that I've not shown the NFA to DFA conversion procedure, which was on the next page. Could someone point me in the right direction?

There are no steps given to obtain (e) from (d). That's what's confusing - I know I have  to remove the null-moves but not how to get the neat and 'minimized' transition system given by (e).


texts: Difference between a skiplist and an Indexable skiplist

texts:
Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little example?), I can only find so little about it online.
Thanks.


texts:
The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that:

predict(nonterminal, production) ==
     if epsilon in FIRST(production):
         first(production) union follow(nonterminal)
     else:
         first(production)

where production is a sequence of symbols which can include nonterminals, terminals, and epsilon.

what's the algorithm for an LL(2) parse table?


texts: What is the effect of having a transition in an epsilon-NFA upon "$\epsilon$,0"?

texts:
When a transition between two states is achieved via any of the symbols $\epsilon,0$, how does the $\epsilon$ effect the transition between the two states?

Does it simply mean that the $0$ is ignored, since it is technically in both states at the same time?


texts: Is it better to store the magnitude of an arbitrary-precision number in BigEndian or LittleEndian order in an integer array?

texts:
I'm implementing a class which provides arbitrary-precision arithmetic (also called "bignum", "BigInteger", etc.).

My questions is about a practical implementation detail:

I'm wondering if there is a significant difference in implementation and computational complexity between an implementation which stores the magnitude in an integer array in BigEndian order vs. LittleEndian order.

My data structure is basically:

class BigInt
  val signum: Int
  val magnitude: Array[Int] // two-complement (unsigned)

Supported operations are for instance:

+, -, * (Long multiplication, Karatsuba, Cook3, Schönhage-Strassen), /, squaring
Conversion to other number types
Comparison, equality, representation as a String

The implementation is immutable, so every operation will return a new value and will not change the any existing.

Feel free to ask for clarifications!


texts:
I am having hard times learning Dynamic Programming.

I looked around the web and found many tutorials with examples.

Each time I tried to figure out how to solve a new problem before looking at the solution my mind locked up and I could not continue trying...

I do not where to start!! For example, in divide and conquer I know how to start but In dynamic programming there is no a fixed starting point or at least (technique).

Last try I moved forward but I found that the solution was in a completely different direction.


texts: Analysis of Weighted Quick Union with Path Compression

texts:
I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function).

I understand why it is $O ( m \log^{\ast} ( n ) ) $ as it is proven on wikipedia.

So the question is, why is WQUPC $O( m \alpha (n) ) $? I would prefer a rigorous analysis, but an intuitive explanation would also be useful.


texts: Conjunctive normal form to simple elementary algebra

texts:
I'm curious to know the computational complexity class of each step in this method of converting a CNF formula into simple elementary algebra.

An example:
$$\phi=\left(x_1 \vee x_2 \right) \wedge \left(\neg x_1 \vee x_3 \right) \wedge \left(\neg x_2 \vee \neg x_3 \right) \tag{CNF} $$
Let $\neg a = 1-a$

Let $a \vee b= a+b-ab$

Let $a \wedge b = ab$

Then:
$$\phi=\left(x_1 + x_2 -x_1x_2\right) \left(1-x_1+x_1x_3\right) \left(1-x_2x_3 \right) \tag{AFF} $$
I refer to this step as algebraic factor form (AFF) (I am unfamiliar with any canonical terminology)
Then expanding these brackets out gives
$$\phi = x_1-{x_1}^2+x_2 - 2x_1 x_2 +{x_1}^2x_2 + {x_1}^2x_3-{x_2}^2x_3+2x_1{x_2}^2x_3-x_1^2x_2^2x_3-x_1^2x_2x_3^2-x_1x_2^2x_3^2 + x_1^2x_2^2x_3^2 \tag{EAF}$$
Which is in elementary algebra form.

Finally, using ${x_1}^2=x_1, \; \; {x_2}^2=x_2, \; \; {x_3}^2=x_3$ we get
$$\phi = x_1-{x_1}+x_2 - 2x_1 x_2 +{x_1}x_2 + {x_1}x_3-{x_2}x_3+2x_1{x_2}x_3-x_1x_2x_3-x_1x_2x_3-x_1x_2x_3 + x_1x_2x_3$$
Which simplifies to:
$$\phi = x_2 - x_1x_2 + x_1x_3 - x_2x_3 \tag{SEAF}$$
Which I call simple elementary algebra form.

If there are already established names for these formulas please let me know and I will amend asap.

So my question is: What are the computational complexity classes of each transformation in (CNF) $\rightarrow$ (AFF) $\rightarrow$ (EAF) $\rightarrow$ (SEAF)

I'm interested to know which parts are P and which parts are NP

Thanks in advance for any answers, Ben


texts:
There is a saying by Computer Science Professor's everywhere :

PDA Checks the intelligence of Students, as certainly there is no approach except power and imagination
of mind to solve problems and design PDA...

While thinking today i thought How can we design automata of a^2n b^(2n-1)

I tried my best :
For example let q0 is initial state and top of the empty stack has Z.

So, Let say Transition of (q0, a , Z) = (q1,Z)

            Transition of (q1, a , a) = (q1,a)

            Transition of (q1, b , a) = (q2,-)

            Transition of (q2, $ , Z) = (qf,Z)

I was able to solve this problem all of a sudden...

My doubt is still the same, How to be the best in solving PDA problems and Is there any way
to define a strategy to solve problems ?

P.S. Your comments are welcome if i did something wrong in above stated question


texts: Are non-trivial sets formed by set operations on NPC sets still in NPC?

texts: I know that from this answer to a question on the class NPC, that NPC is not in general closed under intersection and union.  However, the answer used languages which form trivial languages under these set operations and trivial languages are of course not NP-complete.  If the intersection or union is non-trivial, does the result still hold?  Also, I'm also wondering about the Cartesian product of two NP-complete languages since that is another set operation.


texts: When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state?

texts:
A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current character being read.
If the machine halts when it's in an accepted state and at the same time the whole input has been consumed the input string is considered to be accepted.
Now, when introduce $\epsilon$ transitions the machine doesn't necessarily halt when the whole input string has been consumed, for it is possible that there are still $\epsilon$ transitions available.
Suppose we have a NFA that is in an accepted state and also that the whole input has been consumed, but there are still $\epsilon$ transitions available in this state, can we considered the input string to be accepted or do we need to "follow the trail" of $\epsilon$ transitions until we reach a state where no other transition is available?


texts: Requiring at least one alldiff constraint to be satisfied converted to SAT

texts:
For generating certain hard puzzles, I am trying to model a problem (ultimately) in SAT. I don't know how to do that, so I am starting with CSP because it's more expressive. In CSP, there is a global alldiff constraint, which requires all variables to take on different values from their domains. I have a set of alldiff constraints. However, out of this set, I only require at least one of them to be true. That is, not all of them have to be satisfied.

For concreteness, suppose we have 8 variables $x_1,\ldots,x_8$. Each take values from the domain $\{0,1,2\}$. We want to satisfy the following formula:

$$\text{alldiff}(x_1,x_2,x_3) \lor \text{alldiff}(x_1,x_6,x_7) \lor \text{alldiff}(x_4,x_5,x_6) \lor \text{alldiff}(x_3,x_4,x_8).$$

We are happy if at least one of the 4 alldiff clauses is satisfied, e.g., if $x_1=0$, $x_2=1$, and $x_3=2$, we are already happy.

But how is then modeled in SAT? Specifically, how do we write an alldiff constraint in SAT?


texts: How to know a certain grammar is parse-able

texts:
Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it.

What makes a certain grammar parse-able and contain semantics? How do I decide a written information is parse-able?


texts:
Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol? Say f is the transition function, why does having

f(qi, 1, 0)       -> (qj, 0)
f(qi, epsilon, 0) -> (qj, 0)

cause nondeterminism?

I would understand that if I had

f(qi, 1, 0) -> (qj, 0)
f(qi, 1, 0) -> (qz, 0)

it would cause nondeterminism, because looking at the same input symbol I can choose to move to either qj or qz, that's nondeterminism to me. However the former doesn't make sense at all... This is what Michael Sipser says in his book.


texts: How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

texts:
Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$.  The brute-force method would require $N(N-1)$ distance calculations, which is not acceptable.  I attack the problem by first sorting the cells in a grid¹, such as in this answer, followed by brute-force within each grid cell and a number of neighbours (which is easily calculated from the cell size $w*h$ and the maximum distance $t$).

My solution seems to work acceptably well for my purposes, and the results appear to be correct.  However I'm neither a computer scientist nor a mathematician, and I'm not sure what tools I could use to calculate the optimal cell size.  In fact, I developed the aforementioned possibly naive algorithm because it seemed like a reasonably okay method.  I guess the optimal cell size depends in some way on $N$, $t$, on the cost of the distance function, and on the implementation of the sorting in cells, on the distribution of points, and on other things.  How would I make a guess of the optimal values of $w$ and $h$, with or without a priori knowledge on the approximate number of pairs I expect to find?

Does the answer change if the N points are divided in two sets $S_1$ and $S_2$, and each pair shall consist of one element from each set?

¹Not necessarily euclidian.  The points may, for example, be locations on a sphere, i.e. on Earth, with latitude and longitude.


texts: The VC dimension when the samples are fixed

texts:
The VC dimension is usually used in the following way. There is a space of hypotheses. There is an unknown probability distribution. We sample some training-samples from this distribution. We find the hypothesis that scores best on the training-samples. If the VC dimension is sufficiently small and the number of samples is sufficiently large, then this best hypothesis will also perform probably-approximately-well on any set of test-samples drawn from the same distribution. Specifically, if the VC-dimension is $D$ and the number of samples is at least:
$$
N := \Theta\bigg(\frac{D + \ln{1\over \delta}}{\epsilon}\bigg)
$$
then, with probability at least $1-\delta$, the test-error will be at most $\epsilon$.

I am interested in the following alternative setting. Instead of a probability distribution, we have a ''fixed'' set of samples, determined by an adversary. We pick half of these samples at random, calculate the best hypothesis on this half, and then test it on the other half.

MY QUESTION IS: is it possible to use the VC dimension in the second setting? I.e, is there a formula, similar to the one above, that relates the total number of samples in the population, the probability of learning, and the learning error?


texts:
If a decision problem is in P, is the associated optimization problem then also efficiently solvable?
I always thought that this is the case but according to Wikipedia page on Decision Problems the complexity of a decision and function problem might differ and to me a function problem was always a special case of an optimization problem, hence I was under the impression that if the decision problem is efficiently decidable the same applies to the corresponding optimization problem.


texts:
as part of my homework assignment I have to proof that the following language is not regular using the pumping lemma:

$L = \{w\in \{a,b,c\}^* \; | \enspace z(a,w) = z(b,w) + z(c,w)\}$

The function $z(x,w)$ denotes the number of symbols $x$ in word $w$.

I started my proof by assuming that the language is regular. That means that there must exist an integer $m>1$ so that $|w| \geq m$ is fulfilled.
 I have then chosen the following word which is part of L.

$w = a^{2m}b^mc^m$

After that I split my word in three parts ($x$, $y$ and $z$). Because $|xy| \leq m$ and $|y| > 0$ must be true, at least one character $a$ has to be in $y$.

I have read that I have to choose an $i$ such that the word $w_1 = xy^iz$ is not part of my language any more. I am not quite sure how I can proceed from above to finish my proof.

Could somebody please give some advice on this?


texts: What does the structure ($S_t^x P$) in this Existantial Instantiation imply, Skolemization?

texts:
The sheet of equivalences given to us in class provides the two equivalences

\begin{array}{|c|c|c|}
\hline
\text{Universal Instantiation} & \forall x ~ P(x) \implies {S_t}^x P & \exists y ~ \forall x ~ P(x) \implies \exists y ~{S_t}^x P \\ \hline
\text{Existential Instantiation} & \exists x ~ P \implies {S_t}^x P & \forall y ~ \exists x ~ P \implies {S_{A(y)}}^x P\\ \hline
\end{array}

1. Does the structure $S_t^x P$ imply Skolemization of $x$ to some new constant $t$? Is this Skolemization sometimes written as $x/t$?

2. Is there a difference in meaning between $P(x)$ and $P$ between Universal and Existential Instantiation?

3. Does the notation $S_{A(y)}^x$ read as "replace the constant $x$ with some function $A(y)$", is this still considered Skolemization?


texts: What is the fastest way to input all of 30 million human "go" move into the computer that haven't digitized?

texts:
What is the fastest way right now to input all of 30 million "go" move from the beginning into the computer that haven't digitized?

The idea is came from Google's AlphaGo


texts: Is entropy a good indicator of the quality of a lossy compression?

texts:
Say I want to quantitively evaluate the effectiveness of several color-to-grayscale conversion algorithms, which can be considered as lossy compression. Would entropy be a good indicator?

To calculate the entropy of a file, I first convert it to a byte stream with hexdump(1) or some other methods (see below). Next, this stream of bytes is considered as a Markov chain, and its transition matrix is estimated by examining consecutive bytes, from which entropy is calculated. The stationary distribution can be estimated by counting all bytes in the file if needed.

There are three caveats, however:

Sometimes you need to use longer "byte"s. For example, if the file is encoded with UTF-16, then an atomic unit should contain exactly 16 bits. Fortunately, almost all pictures use True color (24-bit), or 8-bit or RGB respectively, so this won't be a big problem.
Pictures are inherently 2D structures, and hexdump basically coerces them to 1D linear structures, but that's inappropriate. The file should be traversed in another way so that the positional change is as smooth as possible, like

* > *   * > *               * > * > * > *
  /   /   /                  /----<----/
*   *   *   *               * > * > * > *
| /   /   / |    <- GOOD     /----<----/     <- BAD
*   *   *   *               * > * > * > *
  /   /   /                  /----<----/
* > *   * > *               * > * > * > *

The input and output of algorithms to be compared against each other must be the same.

Any thought is appreciated!


texts: Double, down facing arrow in operational semantics

texts:
What is the meaning of the double, down facing arrow $\Downarrow$ in the context of operational semantics? Here's the example formula that uses it:

$$\frac{s_0 \vdash M_1 \Downarrow P_1, s_1 \; ... \; s_{n-1} \vdash M_n \Downarrow P_n, s_n}{s_0 \vdash M \Downarrow P, s_n}$$

It would be also beyond priceless if you could explain in words what do other pictograms of this formula mean. I feel that $\vdash$ here doesn't mean what it usually means in logic (is provable from). However the general form of this formula is the derivation rule (I can understand it from the context). It is a rather general derivation rule though (it is followed by few other more specific examples which use all the same pictograms).

The source of the formula: On Exceptions versus Continuation in the Presence of State by Hayo Thielecke. It cites several other sources, but I couldn't find the explanation of the symbols used.


texts: Deutsch algorithm uses two qubits to determine the type of function. But what if we have only one qubit? How the algorithm would be implemented? And especially, how $U_f = |x\rangle |y \oplus f(x)\rangle$ would look like?


texts: Matrix multiplication over range in $O(n)$

texts:
Let $Q$ denote the number of queries.

I have a $25 \times 25$ matrix in each cell of an array of size $n$. Let us denote this array by $A$. It's a special matrix, more specifically, all elements are $0$ are $1$ and only on cells adjacent to the main diagonal and on the main diagonal itself, allowing faster multiplication.

I have $Q$ queries, each represented by 2 values, $l$ and $r$. Each query needs to be answered by the multiplication of all matrices between the indexes $l$ and $r$. More specifically $\Pi_{i=l}^{r} A_i$. Let $l_i$ denote the value of $l$ for the $i$th query and similarly for $r$. It is given that $l_{i-1}\le l_i$ and $r_{i-1}\le r_i$for all valid $i$.

I can use a segment tree and answer queries, However that adds an unwanted $\log{n}$ factor. I want to know if there is some faster algorithm, that will allow me to answer all queries in $O(Q+n)$ multiplications. Unfortunately, The matrices are not necessarily invertible.

I believe it's some application of 2 pointers, But I'm not able to figure out how exactly it would work.


texts: Context Free Grammar to Regular Expression?

texts:
I want to learn whether I can create regular expressions from the given Context Free Grammar. I found some examples that can be translated to regular expressions. However, all of them were like this: "S-> aB | bC". Whereas my example is like: "S-> AB | BC". Here is my example:

Can I create RE's from this? What is the reason? I want to fully understand why I can and why I cannot. Thank you.


texts: How was the four color theorem proved using brute-force search?

texts: I recently learned some graph theory in Discrete Structures for Computer Science, we learned about the Four Color theorem, I realize there is a mathematical proof for this topic, but how was it initially proved using computation 50 years ago?


texts: Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

texts:
Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs?

Example 1:
set(a, b, c, d, e)
pairs(a>b, ce)

Example 2:
set(a, b, c, d, e)
pairs(a>b, d>b, c>d, d>e)


texts: How can I find the maximum weight between any two nodes in an undirected graph?

texts:
This is referring to not the length of the path, but the sum of the weights of the path traversed. I am getting confused by the variety of algorithms out there.

Suppose that for a graph represented by a dictionary of tuple keys and integer values, my simple idea is to check each pair of nodes to see which nodes connect and simply add up the maximum weight seen so far. I don't know of a better starting point than this.


texts:
I have the following 2-bit binary multiplier

How can I modify this 2-bit binary multiplier to make it a 3-bit binary multiplier?

I notice that there are 2 half-adders, and there are a bunch of ANDs to begin with. It is tricky to see a pattern here, I would normally use a truth table but there would be a wopping 64 combinations. Any other strategies I could use here?


texts: Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?

texts:
Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking about everything that might happen in case of robbery, one problem came into my mind and it can be described as follows.

Suppose that you and your family decided to go on a trip abroad, that would last for around 7 days. After spending some nice time with your family, you return back only to realize that your home had been robbed. You call the police and the police asks for the data stored in the camera.

Now, you know for sure that the robbery happened during those 7 days that you were gone, and you definitely know that the camera will show the people doing the robbery at some specific point of time, problem is, you do not know when.

Now, assuming that no one had seen anything at all and that the only source of information would be the data stored by the camera, how would the police find the time during which the robbery happened? Can they do something better than watching every single second of the footage available?

In computer science terms, assume that you are given an array of size $N$, where all the elements are white, except for one which is black. Now you can imagine that the white elements are just images stored by the camera and the indexes of the array represent seconds. If no robbers are depicted in the image, then this image is white, otherwise it is black.

So now you want to find that second where the robbers are depicted in the image, so you are looking for the index of the black element in your array. Can you do better than actually scanning the entire array to find that index?


texts:
We have to derive an optimal binary encoding for the infinite set of symbols $\{s_1, s_2, \dots \}$. They're distribution is given by
$$p(s_i) = 9 \cdot 10^{-i}$$

My intuition was to use a Huffman encoding. Obviously the Huffman encoding
algorithm needs to first find the smallest two elements, which we can't do. But, if we imagine the last step of the Huffman algorithm, it would have the two elements $s_1$ and the supersymbol $s_2s_3s_4\dots$ with probabilities $0.9$ and $0.1$ respectively. Thus, (if left is $0$ and right is $1$) symbol $s_1$ would get codeword $0$. The other symbols would all get a codeword starting with $1$. This tree is clearly self similar. If we represent binary trees as tuples with an empty tree as the nullset $\varnothing$, we have that this tree is given by

$$ T = (\varnothing, T) $$

That is, a left branch which is empty an the right branch which is identical to the whole tree. Thus, we get the codewords

$$ s_1 \mapsto 0, s_2 \mapsto 10, s_3 \mapsto 110, s_4 \mapsto 1110, \dots $$

Now, I know that these are optimal. You can do a proof by contradiction showing that changing any of these codewords and still satisfying the Kraft inequality will cause the expected length to increase.

My question is, is the fact that this infinite Huffman tree arrived at the answer a coincidence or is there a way to formalize Huffman encoding for an infinite set of symbols.


texts: How to design synchronisation algorithm to combine two automata?

texts:
I have two automata of states, transition and events (Etat, Transition, evenements) and I want to create a function that create the synchronized product between those two automata. For instance, given plant and spec automata, plant :

donnees=("nomprob", # name of the problem
        [("e1",True),("e2",True),("e3",True),("s1",False),("s2",False),("s3",False)], # events
        ("plant",[("S4",True,False),("S1",False,False),("S2",False,True)], # first automata (spec) states
            [("S4","S1",["e1","e2","e3"]),("S1","S2",["e1","e3"]),("S1","S4",["s1","s2","s3"]),("S2","S1",["s1","s2","s3"])]), # first automata (spec) transitions
        ("spec",[("S0",True,False),("S1",False,False),("S2",False,True)], #second automata (plant) states
            [("S0","S1",["e1","e2","e3"]),("S1","S2",["e1","e2","e3"]),("S1","S0",["s1","s2","s3"]),("S2","S1",["s1","s2","s3"])] # second automata (plant)transitions
        )
    )

I want to have, if it is correct :

I thought to do

for (Etat_s, Etat_p) in plant, spec:
    we create a new state Etat_{s.name,p.name}
    for (transition_s, transition_p) in Etat_s, Etat_p:
        new state with the concatenation of the names of the ends of the transitions
        if transitions' events are the same:
            we add a transition from Etat_{s.name,p.name} to this last state
        else if transition's are different
            here I don't know

Added to the issues I have in the algorithm above, I'm sure I would create too many states.

Merge of finite automata : I don't have issues with the merged language $L_1||L_2$ as it seems it is the same events. So let $M1 = (Q_1, Σ, δ_1, q_{01}, F_1)$ and $M2 = (Q_2, Σ, δ_2, q_{02}, F_2)$ be two finite automata with the same input alphabet. We define a finite automaton $M_{||}$ such that $L(M_{||}) = L(M1)||L(M2)$ as follows:

$$M_{||} = (Q, Σ, δ_{||}, q0, F∩)$$

where

$Q = Q1 × Q2$,
$δ_{||}((q_1, q_2), a) = {(δ1(q_1, a), q_2),(q_1, δ_2(q_2, a))}$,
$q_0 = (q_{01}, q_{02})$,
$(q1, q2) \in F\bigcap$ iff $q_1 ∈ F_1$ and $q_2 ∈ F_2$.

By the way, this is part of a project, where the code has been written in French, sorry for that, but which you can find here.


texts:
I had this question on a previous homework assignment and was unable to answer it. I've done some research and am not really able to find anything that clears this up for me. Would appreciate any help or explanation.

Q2. Consider a direct-mapping cache of 128 lines and a main memory block size of 8 bytes. What cache line number does byte address 120010 map to?


texts: When is the concatenation of a language $L$ with $\Sigma^*$ regular?

texts:
I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\{0^n1^n|n\geq 0\}$ and $\Sigma^*$ was regular (over the alphabet $\Sigma = \{0,1\}$). Another provided a counterexample by the concatenation of $\{a^{n^2}b|n\geq 0\}$ with $\Sigma^*$, which is irregular (over the alphabet $\Sigma = \{a,b\}$). Could someone provide clarification as to why some concatenations with $\Sigma^*$ are regular while others aren't? Both cases concatenate an irregular language unrecognisable by a DFA to one that is, and I don't understand how this produces a language that is recognisable.

Links to source questions:
https://math.stackexchange.com/questions/649335/are-languages-regular-if-their-concatenation-is-regular
Why is $\Sigma^*$ concatenated with some language regular?


texts: Why is this true: “There are countably many Turing Machines”

texts:
It is said that there are uncountably many languages but only countably many Turing Machines. Could someone make this clear to me?
And this doesn't mean that the set of TM is finite, yes?


texts:
I am having trouble understanding a question related to Huffman Coding. We haven't studied it a lot, so I am not even sure how to start.

Given $n ≥ 2$ characters, with probabilities $p_{1} \geq p_{2} \geq ... \geq p_{n}$ Let $p_{i} = 2^{k_{i}}$ with $k_{i} \in \mathbb{N}$ and $\sum_{i=1}^{n} p_{i} = 1$

Show that $p_{n-1} = p_{n}$ and that the minimum expected codelength amount to
$$- \sum_{i=1}^{n} p_{i} \log p_{i}$$

Help?


texts: What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot?

texts: If I were to sort the list of numbers 1,7,5,7,1 using Hoare's algorithm as described at the very beginning of wikipedia item on Hoare partition scheme with 5 being the pivot, and the indexes start at 1 and 1, then what would happen? If they are switched, nothing is really sorted. And the same goes for the two indexes both landing on numbers greater than the pivot, for example, 7 and 7. How would Hoare's algorithm handle such a case?


texts: Ambiguous Grammar and SLR parsing table : No conflicts?

texts:
We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-then-else grammar which is pretty much ambiguous.

So I started with the following rules ( as given in Principles of Compiler Design, Aho and Ullman, 2002 Reprint)

$$
S \rightarrow iCtSS' \\
S \rightarrow iCtS \\
S \rightarrow a \\
S' \rightarrow eS \\
S' \rightarrow \epsilon \\
C \rightarrow b \\
$$

S is the statement, and C is the condition. All apart from S', S and C are terminals, and epsilon refers to null.

The given grammar is written in a way that conforms to recursive descent parsing.

Augmented the grammar as

$$
S\prime\prime \rightarrow .S \\
S \rightarrow .iCtSS' \\
S \rightarrow .iCtS \\
S \rightarrow .a \\
S' \rightarrow .eS \\
S' \rightarrow .\epsilon \\
C \rightarrow .b \\
$$

And then generated the instances-set as

$$
I_{0} [ S\prime\prime \rightarrow .S, S \rightarrow .iCtSS', S \rightarrow .iCtS, S \rightarrow .a, S' \rightarrow .eS, S' \rightarrow .\epsilon, C \rightarrow .b]\\
I_{1} [S \rightarrow i.CtSS', S \rightarrow i.CtS, C\rightarrow.b]\\
I_{2} [S \rightarrow a.]\\
I_{3} [S'\rightarrow e.S, S \rightarrow .iCtSS\prime, S \rightarrow .iCtS]\\
I_{4} [S \rightarrow \epsilon.]\\
I_{5} [C \rightarrow b.]\\
I_{6} [S \rightarrow iC.tSS\prime, S\rightarrow iC.tS]\\
I_{7} [S\prime \rightarrow eS.]\\
I_{8} [S \rightarrow iCt.SS\prime, S \rightarrow iCt.S, S \rightarrow .iCtSS\prime, S\rightarrow.iCtS, S\rightarrow.a]\\
I_{9} [S \rightarrow iCtS.S', S \rightarrow ICtS., S' \rightarrow .eS, S' \rightarrow .\epsilon]\\
I_{10} [S \rightarrow iCtSS'.]\\
$$

Based on these sets that I made, I constructed a parsing table

However, as per my derivation of the instance-sets, there were no conflicts in the table (the grammar being ambiguous), I was not sure if I worked it out correctly. One thing that adds to the dilemma that there has been no instance where S was the first non terminal in grammar, and so there are no states that can accept the final variable S during parsing.

Can anyone please help me with this? I checked it further online and they mentioned that the ambiguous grammar tended to have conflicts, but there were none in this case. Where am I going wrong?

Thanks.


texts: Prove that the language of unary not-prime numbers satisfies the Pumping Lemma

texts:
Here is a question from Daniel I. A. Cohen's book Introduction to Computer Theory:

  Consider the language:

  $\quad \mathrm{PRIME}' = \{ a^n \mid n \text{ is not a prime} \} = \{ \varepsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots \}$

  Prove that $\mathrm{PRIME}'$ is non-regular.
  Prove, however, that $\mathrm{PRIME}'$ does satisfy the pumping lemma.

Part 1. is really easy to prove. I start my proof of part 2. like this:

We pick $m$ s.t. $m \geq 4$.
The opponent picks $w = a^{n^2}$, where $n$ is any prime number greater than m.

Now I don't know how to decompose $w$ into $xyz$. Any help would be appreciated.

Update: According to the answers below, $\mathrm{PRIME}'$ doesn't satisfy the Pumping Lemma we commonly talk about (requiring $|xy| \leq m$). I have checked the book at the library and found there are two versions of the Pumping Lemma in it. The weaker one, which clearly this question refers to, doesn't require a fixed pumping length.


texts:
I was searching for a difference on both ways of proving that a language is not regular but I didn't came up with much.

Let us take the following as an example:

$$ L = \{ a^n b^n \mid n \ge 0\} $$

Could someone tell me the differences between both theories and how to prove the language I brought is not regular according to each approach.

I know this is a basic example – that is the reason I chose it, make it simple rather than make it harder.

Thank you in advance!


texts: Why is step 4 and 5 necessary in this Cycle Cover Superstring Algorithm?

texts:
(Shortest Common Superstring:
Input: A set S = {s1, . . . , sn} of strings over an alphabet Σ.
Feasible solutions: Each superstring w of S, i.e., each string w that contains all strings $s_i$ ∈ S as substrings. )
I just finished implementing cycle cover superstring algorithm, but step 4 and 5 just doesn't make sense to me.

Why is it important that we compute a minimum cycle cover for the representative vertices? They will be replaced by the concatenation of all prefixes in the cycle followed by the representative itself, and then these strings will not be merged, they will be concatenated together to achieve a superstring. Why is maximizing overlaps a goal, if we don't merge, only concatenate? I found a different algorithm for Cycle Cover Superstring, and here step 4 and step 5 are left out!

To me, the second algorithm makes perfect sense so I decided to implement that one, but could anybody tell me why would be the first one better? It seems to give the same output but it's slower. I'm afraid I misunderstood something.
The first algorithm can be found in Algorithmic Aspects of Bioinformatics.
The second algorithm can be found in Approximation Algorithms
for the Shortest Superstring Problem by Martin Paluszewski (first link if you google it)
EDIT: I tested the two algorithms with multiple examples on paper and on computer using my implementation. The outcame wasn't always the same, but the length of the superstrings was always the same, which means that both algorithms are good, only that the second one is faster. I'm more concerned about that my interpretation of the first algorithm isn't correct - once it states that the representatives are merged in order, and then that they have to be concatenated. I posted this question hoping that somebody would notice that I somehow misinterpreted the first algorithm.


texts: Disparity calculations and camera centers

texts:
I'm learning about the disparity calculations and want to calculate the distance for a known pixel. I have calibrated and rectified images already. Now I just want to calculate Z for some pixel x,y.

the opencv tutorial says: "The depth of a point in a scene is inversely proportional to the difference in distance of corresponding image points and their camera centers.
"
According to this paper https://www.ri.cmu.edu/pub_files/pub2/willson_reg_1993_1/willson_reg_1993_1.pdf there are a lot of different camera centers.
What kind of camera center should I use?
Should I use the principal point Cx,Cy from the camera matrix? That doesn't quite make sense since they differ between cameras. If I  just use the Center of the frame in pixels, it doesn't take into account projection center. I'm lost in all these centers. Tutorial makes it look so easy.  Anyone has practical experience with the topic? Also my cameras have different focal values. Which one do I use?
PS>also why does the right arrow, next to x' points to the right, as if suggesting that it takes the distance from the left camera center.