texts:
I am looking at the following:

Costruct a composite turing machine, that reverses the words $w_1$ and $w_2$ over the alphabet $\{\_, x_2, \ldots , x_m\}$ as follows:
$$\ldots \_ w_1\_ w_2\underline{\_} \ldots \mapsto \ldots \_ w_2^R\_ w_1\underline{\_} \ldots$$
The first symbol of $w_2^R$ is on the position where the first symbol of $w_1$ was at the beginning.

The suggested solution is the following:
We have to define the TM that reverses an arbitrary non-empty string of the alphabet:
$$\ldots \_ w \underline{\_}\ldots \rightarrow  \ldots \_ w^R \underline{\_}\ldots$$
This can we done as follows:

This TM does the same as the one that copies a string, but this reverses the word and shifts the reversed copy to the original word.

We get the following TM:

If none of the words is empty, the TM reverses $w_2$ and copies $w_1$ at the position on the right of $w_2^R$. Now $w_1$ must be deleted. To do that we connect $w_2^R$ and $w_1$ by $z$, that is not in the alphabet, to one word. We shift that word on $w_1$ and delete $z$. The TM halts on the right of $w_1$.

$$$$

I haven't really understood the definition of the reversing TM (the first picture). Could you explain it to me?

We have that $R$ is the TM that goes to the right till it reads a blank. $L$ is the TM that goes to the left till it reads a blank. $V$ is the TM that translates.

The function of TM is the following:

First the word $w_2$ is reversed. Then the TM copies the word $w_1$ on the right of $w_2^R$. So, on the tape we have now $w_1\_w_2^R\_w_1$.
We have to shift $w_2^R\_w_1$ to the left, by overwriting it on the first $w_1$, right? To shift $w_2^R\_w_1$ we have to connect that to one word, so we replace the blank by a symbol $z$ that is not in the alphabet. After having shifted the new word we delete again the symbol $z$. Have I understood it correctly?


texts: Bloom filter variant(using only half of it)

texts:
A Bloom filter is an array $B[1..m]$ of bits, together with a collection of $k$ independent ideal random hash functions $h_1,h_2,...,h_k$. To insert an item $x$ into a Bloom filter, we set $B[h_i(x)] ← 1$ for every index $i$. To test whether an item $x$ belongs to a set represented by a Bloom filter, we check whether $B[h_i(x)] = 1$ for every index $i$. This algorithm always returns True if $x$ is in the set, but may return either True or False when $x$ is not in the set. Thus, there may be false positives, but no false negatives.
If there are n distinct items stored in the Bloom filter, then the probability of a false positive is $(1 − p)k$, where $p ≈ e^{−kn/m}$ is the probability that $B[j] = 0$ for any particular index $j$. In particular, if we set $k = (m/n) ln 2$, then $p = 1/2$, and the probability of a false positive is $(1/2)(m/n) ln 2 ≈ (0.61850)m/n$.
After months spent lovingly crafting a Bloom filter of size m for a set S of n items, using exactly $k = (m/n) ln 2$ hash functions (so p = 1/2), your boss tells you that you must reduce the size of your Bloom filter from m bits down to $m/2$ bits. Unfortunately, you no longer have the original set S, and your company’s product ships tomorrow; you have to do something quick and dirty. Fortunately, your boss has a couple of ideas.
(a)First your boss suggests simply discarding half of the Bloom filter, keeping only the subarray $B[1 .. m/2]$. Describe an algorithm to check whether a given item $x$ is an element of the original set S, using only this smaller Bloom filter. As usual, if $x ∈ S$, your algorithm must return True.
(b) What is the probability that your algorithm returns True when $x ̸∈ S$?
Can I ask for some help for part (a) and (b)? I'm really stuck for that.
Here's what I got so far for (a), given an item $x$, if $b[h_i(x)]=0$ for some $i$, then output FALSE($x \not \in S$). If all $B[h_i(x)] =1 \forall i \in [k]$, this means all the value of the hash function lies in the half of the bloom filter, so we output TRUE. On the other hand, if all $B[h_i(x)] =1$ in the half of the bloom filter, but we don't know about the hashed value of the other discarded half bloom filter, then we still output TRUE.
Is my direction for (a) right? Also, how to approach part (b)?


texts: What is the difference between AM and IP

texts:
Intro

I am trying to understand how those two models of interactive proof are different. I understand that

$\text{AM}$ relies on public coins (the prover knows the random bits used by the verifier)
$\text{IP}$ relies on private coins (the prover does not)

And here are some common results in those classes

Goldwasser and Sipser showed that if we allow a polynomial number of rounds $Q$, we have that $\text{IP}[Q] \subseteq \text{AM}[Q+2]$.
It has also been shown that if we allow a constant number of rounds $k$ in $\text{AM}$, we have that $\text{AM}[k] \subseteq \text{AM}[2]$

This seems to imply that if we limit $\text{IP}$ to a constant number of round $k$, we also have that $\text{IP}[k] \subseteq \text{AM}[k+2] \subseteq \text{AM}[2]$, and that these classes are very similar.

The thing that bugs me

But then, why do we have the huge difference that
$\text{IP} = \text{PSPACE}$, while $\text{AM} \subseteq \prod_2^{\text{P}}$?

(see the Complexity Zoo on AM and IP)

Question(s)

Why the difference? My assumption is that there is a convention to use $\text{AM}$ to speak about $\text{AM}[k]$, private coin, constant $k$ rounds protocols, and $\text{IP}$ to speak about $\text{IP}[\text{poly}]$ public coin, polynomial rounds protocols. Is it correct?
Do the results holds if we swap the classes? $\text{IP}[k] \subseteq \prod_2^{\text{P}}$ does, but what about $\text{AM}[\text{poly}] = \text{PSPACE}$?
As an additional question, we do know that a constant number of messages $k$ can be condensed into only two messages. Is there a similar result for a polynomial number of messages?


texts: Fork() execution and number of processes

texts:
If a process executes the following code

fork();
fork();
fork();

The total number of child processes created is given as 7 by a text book.
But how does that happen

fork generates 2 processes right? Are both the processes referred to as child processes? One process is the parent parent and one is the child right?
Even if both the processes are referred to as child processes,2*3=6? The main process is not a child process,how does the number 7 come into the picture.

Update:


texts:
From what I learned, viola jones needs images with faces upfront. Tilting the head a few degrees to each side can botch the algorithm. Is it possible to take an image, take a several rotated copies of it and run the algorithm on each one?

This limitation sounds like only a minor neusense to me. Is there a stronger reason for the limitation?


texts:
I'm studying for a test, and got stuck on Time Complexity questions. Hope you guys could show me how to solve these.
I searched everywhere I could but didn't find a way.

they are two different qustions.


texts: Prove $\{xy: x \in A \land y \in B \land |x| = |y|\}$ is context-free

texts:
This is problem 2.44 from Introduction to the theory of computation by Michael Sipser.

If $A$ and $B$ are languages, define $A \diamond B = \{xy: x \in A \land  y \in B \land  |x| = |y|\}$
Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a $CFL$.

My try:
Let us define the following languages:
$$L_1 = \{ x\#y : |x| = |y| \}$$
$$L_2 = \{ x\#y : x \in A \land x\in B \}$$
$L_1$ is context-free, can be proven in a similar way to as done here
$L_2$ is concatenation of regular languages, and hence regular.
Context-free languages are closed under intersection with regular languages, and hence $L_1 \cap L_2 = \{x\#y: x \in A \land  y \in B \land  |x| = |y|\}$ is context free.
Let us define the homomorphism $h$ such that $h(\#)=\epsilon$ and as the identity homomorphism for all other symbols.
$h(L_1 \cap L_2)=A \diamond B$, and since Context-free languages are closed under homomorphism, we conclude the requested result.

Does my proof make sense?


texts:
In Vol. 1 Issue 1, Jan. 1958 of the magazine Communications of the ACM, Dr. Saul Gorn discusses the advantages of the computer architecture of Edvac to that of Eniac.

He states that the Edvac had a three-plus-one address word structure, and that the tendencies of his time period were to use one-address hardware and three-plus-zero address pseudo-codes. He then goes on to say that for the future he imagines using variable instruction-word-length machines.

My questions: What is a three-plus-one address word structure? What is a one-address hardware and three-plus-zero address pseudo code? What do these terms mean exactly? I understand what a word is, but not to an extent that would allow me to understand these terms contextually.

Link to this issue of CACM: here. I believe an ACM membership is required to access the magazine. This question refers to Dr. Saul Gorn's Letter to the Editor.


texts: What's the difference between Acfg and ALLcfg

texts: In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM   or the same or similar uses with CFGs, etc. Does the single A stand for any, some, one, or all instances of the class whether it's a TM, a CFG, or anything else? Conversely, ETM and EQTM are obvious as to what they mean.


texts: Probability that two elements are compared in randomized quicksort

texts:
I am having an issue in a specific part of the randomized quick-sort analysis.

As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random index, instead of just choosing a specific index each time.

Now suppose that we give an array of size say $n$ to our randomized quicksort algorithm.

Now I request to have a look at the proof of lemma-7.1 in the text given below. Now we have given an array to our algorithm which can be of any permutation of the elements, but in the paragraph just after the proof of $lemma-7.1$.

why is the author considering a sorted instance of our input array while doing the analysis?

Moreover if look at the text after equation $(7.2)$ where there have justified their logic of finding the probability that $z_i$ shall be compared with $z_j$ in our algorithm. Now in that they are considering the subset {$z_i$,...,$z_j$}. Isn't this case of comparison of $z_i$,$z_j$ getting too specific if we consider that specific subset only? I mean to say we are using randomized approach and the probability of comparison might be derived using a more broader look, such as a permutation of all possible cases or so.

That we are using a specific subset and that too sorted is not convincing as to how are we getting the correct probability for our algorithm...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

And the probability of $1/(j-i+1)$ -> total no. of elements in the
                                        subset is also fixed for
                                                specific $i$ and $j$

In considering the probability of comparison of $z_i$,$z_j$, the subset in which the two elements are there and which is to be partitioned can be anything(i.e composed of any possible element) and of any size (not just $j-i+1$)...

May be the randomization condition is actually taking everything in
account but I am not getting it. Please can you explain me the logic they are using to find the said probability and also please convince me that we are correctly finding the probability of comparison.

For reference i am attaching the corresponding pages of INTRODUCTION TO ALGORITHMS 3RD ED-- CLRS


texts:
Please assume for the sake of this session that humans can fluently read and understand machine languages and time isn't a problem in that regard.
I, not a computer scientist, would at least theorize that a unary machine language is possible but might just be much "less comfortable" than binary machine language.
Is unary machine code a concept?


texts: An algorithm for comparing a DFA and a regular expression

texts:
Assuming I have an encoding of a DFA $<M>$ and a regular expression $<r>$, I'm interested in finding an algorithm for comparing whether or not $L(M)=L(r)$.

I have thought about converting $r$ into an NFA, and then converting the NFA to a DFA, but the problem is that this process may result in a totally different DFA.

Another idea I had was to convert the DFA to a regular expression. But with this idea, I have two problems: first is that I'm not sure how exactly is ut done, and second - even if I will succeed in doing so, I might again end up with a totally different regular expression (that has the same language, but written differently).

Obviously, a third approach would be to start looping all over $\Sigma^*$, but this is an infinet process...

Does someone have a different idea or a way to improve my approaches to this problem?

I would like my algorithm to be able to both return "true" if $L(M)=L(r)$ and false otherwise (my third approach can only return false, but will never return true).


texts: Determine when Strassen's algorithm for matrix multiplication is better than regular MM

texts:
I'm trying to find out how to determine the size of the matrices $n$ such that Strassen's algorithm for matrix multiplication is better than the regular algorithm. I know that Strassen's algorithm is $\Theta(n^{lg 7})$, and regular matrix multiplication is $\Theta(n^3)$.

My reasoning goes along the following lines:

When the size of the matrices to be multiplied is $2x2$, Strassen's algorithm carries out 7 multiplications and 24 additions, whereas the regular multiplication requires 8 multiplications and 4 additions.

So I can do something like this, by the definition of the $\Theta$ notation

\begin{align}
31 &= c_1 2^{lg 7} \\
31/7& = c_1
\end{align}

Using a similar reasoning,

\begin{align}
12 &= c_22^{lg 8} \\
12/8 &= c_2 \\
3/2 &= c_2
\end{align}

If this is valid, having determined the constants all that remains is to set the equalities using these constants, and solve for $n$.

I would just like to know if my train of thought is correct, and if it isn't, how to go about finding the size of the matrix $n$ such that Strassen's algorithm is better. I know this might depend on specific implementations of hardware, architecture and so on, but the divide and conquer approach doesn't necessarily have to be used until the algorithm reaches the base case $2x2$. I want to know when to switch to another algoritm, which in this case is the regular matrix multiplication.


texts: When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$

texts: Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges."  and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$".  Then why do even use $ |E| = \Theta (|V|^2)$?, understand that $\Theta$ is the correct(tightest) bound in asymptomatic notation.  It seems to me that $|E| = \Theta (|V|^2)$ can never happen, so why do we use it?


texts: machine learning classification with financial instrument/time series data

texts:
I am new to machine learning and have started brainstorming some model ideas that involve financial instrument/time series data. I was thinking it might be useful to use a classification algorithm to predict if an instrument was in fact up or down y% (TRUE/FALSE) after n days, based on i.e. a combination of technical indicator states for each learning example.

That said, in researching the idea I came upon an article that stated training examples in time series data are not independent of each other:

"Time series data has a natural temporal ordering - this differs from typical data mining/machine learning applications where each data point is an independent example of the concept to be learned, and the ordering of data points within a data set does not matter"

My question is as follows: is the above true only if we are trying to predict the continuous value of an asset n days into the future? As far as my idea outlined in the first paragraph is concerned, would this then still be valid considering I am not (apparently) taking into account the specific relationship


texts: How to train SVM in matlab / python for MultiLabel data?

texts:
I am training a problem such that my output (y) could be more than one class. For example, the SVM could say, this input vector is class 1, but it could also say, this input vector is classes 1 AND 5. This is not the same as a multiclass SVM problem, where the output could be ONE of multiple classes. My output could be ONE or SEVERAL of multiple classes.

Example: My training data looks like (for each training vector X)

X_1   [1 0 0 0]
X_2   [0 1 1 0]
X_3   [0 0 0 1]
X_4   [1 1 0 1]

Where the right side is the Y to be predicted (here I am showing an example with 4 classes, where a 1 indicates class membership).

I understand that I need to probably use a structural SVM such as discussed here: http://www.robots.ox.ac.uk/~vedaldi/svmstruct.html

However, this is all very confusing to me.

I do NOT want to simply do one-vs-all classifiers for each of the possible output classes, however. I need to somehow take into account class relationships, so I guess what I need is a structural SVM. My training data will have some instances tagged with single classes and other instances tagged with multiple classes.

I guess I'm asking how to tackle this problem and if you know any packages to do so in MATLAB or python.


texts: I understand type systems like the simply typed lambda calculus, system F and the calculus of constructions include a different subset of all lambda terms. But what, precisely, are the terms each of those systems include/exclude? Is it possible to express the intuition behind the criteria with words?


texts: Finding the "most modular" subset of graph vertices, i.e. that minimize disagreement inside and outside

texts:
Let $G = (V, E)$ be a graph.  I want to find the subset of vertices of $G$ that minimizes a certain modularity cost.  In our setting, the modularity cost of a subset $X$ is defined as the number of non-edges within $X$ plus the number of edges from $X$ to the outside, all this divided by $|X|$.  Intuitively, it is the number of edges to add/delete so that $X$ becomes an isolated clique, divided by $|X|$.

To put it formally, for $X, Y \subseteq V$, possibly overlapping, denote

$$E(X, Y) = \{\{u,v\} : u \in X, v \in Y, uv \in E\}$$

Also denote
$$\overline{E(X, Y)} = \{\{u,v\} : u \in X, v \in Y, u \neq y, uv \notin E\}$$

I would like to find the subset $X \subseteq V(G)$ that minimizes

$$
\frac{|E(X, V \setminus X)| + |\overline{E(X, X)}|}{|X|}
$$

Is there anything in the literature about this?  I'd like to know if it's NP-hard, approximable, etc.

This relates to the densest subgraph problem, which can be found in polynomial time.  But densest subgraph ignores the outside edges.  Densest subgraph exploits a supermodular formulation, which does not apply here.There are also some (actually lots) of community detection papers out there, but I haven't found one that deals with this particular cost.


texts: Difference between heuristic-based searching and optimal path searching

texts:
I'm currently studying for an AI computer-science course.
One thing is difficult for me to grasp and somewhat vaguely explained in my course-material:

I understand that with search-methods like e.g. beam search, hill-climbing... you can search based on a certain knowledge about the problem which can tell you in each state an approximation off how close you are to finding the solution. Currently I've reached a chapter about Optimal Search algorithms. An important algorithm in that chapter is Uniform Cost which is based on the lowest accumulated "travel-cost", with as desired consequence that the algorithm will reach a solution in a branch with the lowest accumulated travel cost. Now, I don't understand that travel cost and how it differs from a normal heuristic value. Can someone explain the difference and how it effects finding a solution?


texts: Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

texts:
I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum flow at the maximum cost (or gain).

I'm planning to solve this problem by negating the arc costs and then to compute the maximum flow at the minimum cost.

So, my question concerns to prove or refute if this technique is valid; that is if the negated result of minimum cost after solving the max-flow/min-cost on the transformed network corresponds to the minimum cost. I would use a cancel cycle algorithm.

Thanks in advance for any help


texts:
I have been reading a paper Finding Maximal Pairs with Bounded Gap:

An in there, there is a sentence (page 6 second paragraph):

  The “smaller-half trick” is used in several methods for finding tandem repeats,
  e.g. [2, 5, 26]. It says that the sum over all nodes v in an arbitrary binary tree of size n of terms that are $O(n_{1})$, where $n_{1}\leq n_{2}$ are the numbers of leaves in the subtrees rooted at the two children of v, is $O(n\log n)$

Although it sounds very straightforward, I just cannot see why this is true. Could someone with some experience regarding this trick please explain why this is true?
I read several other papers but just don't see it.


texts: Regularity of a language contains more 1's than 0's

texts:
The language of all bitstrings with more 1s than 0s, i.e.,

$ A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular.

I know I should apply Pumping Lemma and the proof as well, what I cannot understand is' the meaning of question itself. To be more precise, my question is' how the formal and informal sections of the question are the same?


texts: Proof of message complexity on the network

texts:
I try to provide a strict and mathematical rigorous proof to the following problem in Distributed Algorithms.

Prove or make a contradiction: if to vertices $a$ and $b$ on the network $G$ are located on the distance $k$ from each other, and there are $k^2$ different paths on different edges, so it is possible to transfer $k^2$ messages from $a$ to $b$ in time $\text{O}(k)$.

In my opinion. it's not true, I will try to show why. Let's say we have a network as on the picture with vertices $a$ and $b$, all vertices are different and there are 3 paths. The distance from $a$ to $b$ is $k$, in the case of synchronous communication, on every $k/2$ vertices the is collision of $k^2$ messages (the number of paths). In general, it's possible to build a network (not like on the picture), where the worst case occurs (first outgoing messages goes on the longest path and last outgoing message on the shortest path, finally they will make collision again).

Finally, we will get, $\sum_{0}^{\frac{k}{2}} k^2$ - collisions, which is greater than $\text{O}(k)$.

Does it make sense? Is it enough rigorous?


texts: any hope to solve np hard problem using deep learning?

texts: I know some basic machine learning and deep learning. Now a days deep learning solve many types of problem. I working working optimization problem like np, np hard problem. Is there any hope to solve np hard problem using deep learning


texts: Operating System: Performance of Demand Paging

texts:
I am reading Operating systems from the book "Operating System Concepts" by Peter Baer Galvin, 7th edition.

  Performance of Demand Paging:

  Let p be the probability of a page fault (0 $\leqslant$ p $\leqslant$1). We would expect p to
  be close to zero—that is, we would expect to have only a few page faults. The
  effective access time is then
  effective access time = (1 - p) x ma + p x page fault time.

  To compute the effective access time, we must know how much time is
  needed to service a page fault.

  Example If we take an average page-fault service time of 8 milliseconds and a
  memory-access time of 200 nanoseconds, then the effective access time in
  nanoseconds is

  effective access time = (1 - p) x (200) + p (8 milliseconds)

  = (1 - p) x 200 + p x 8.00(1000

  = 200 + 7,999,800 x p.

My doubt when there is a page table hit it we should multiply p by (ma + ma) because, we need one memory access to access page table from memory and one more memory access to access the actual page from memory.
In my opinion formula should be
effective access time = (1 - p)x(ma+ma) + p x page fault time.

Where ma is memory access time

Please let me  where am I wrong?


texts: Interpreting probabilistic time turning machines

texts:
I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better:

$$ Pr_{r \in \{0,1\}^l}[A(r) = \text{"yes"}]$$

Where r is a truly random bit string and A is a polynomial time deterministic machine.
I've been having some problems understanding what this expression means conceptually (or intuitively).

So far these are some of my thoughts and I will try to point out my doubts too.

A is just a standard TM so we can image that on l steps, it will yield $2^l$ branches. Each branch has a chance of occurring depending on which r occurs. Therefore, I was wondering if the above probability expression just mean "the fraction of branches that out yes"? Is that basically the same as the chance that A will output yes on the given random bit string? The thing that was confusing me and I was not sure how to deal with it was that, A(r) always outputs the same thing ("yes" or "no") on a given r (say it always accepts or rejects if r = 1010100 or something), it didn't seem to me that it a probabilistic sense, unless we randomly choose r. So I was wondering how the community interpreted this equation and what it mean.

Also, since this is a probability, it seems to me that A(r) is just r.v. that only takes two values (yes or no), right? So this distribution only has two probability values, the one that A outputs yes or no, right? I was wondering how that related to the string r and I was not sure how to resolve this.


texts:
I am trying to calculate the length and width of objects using a camera. The camera (90° angle from the top) and the background is fixed.

See this Link https://www.pyimagesearch.com/2016/03/28/measuring-size-of-objects-in-an-image-with-opencv/

As an example I take a picture from a US quarter from a distance of 10 inches. To calibrate I calculate how many pixels the US quarter has. When I stack 25 quarters will I still be able to get an accurate measurement or is this not possible?

Also would it work any better if I have an image from the top and one from the front?

I appreciate any help :)


texts: Source entropy and other questions related to information theory

texts:
Kolmogorov-Sinai entropy (KS) explains the mathematical concept behind KS entropy.

$$h ( T ) =\sup\limits_{\xi} \, h ( T , \xi )$$

defines the formula for KS where the left-hand side is nothing but the Shannon's entropy. In many papers I have seen that KS is defined as the supremum over source entropy. These conflicting views raises the following questions

What is the difference between Shannon's entropy and source entropy (source entropy given by $\lim \frac{1}{n}\cdot h(T)$ where $n$ is the length of the word or sequence,unsure though).
Would source entropy be the entropy of the raw signal before it has been quantized or should it be that of the quantized?
Is 'n' the length of the data series or the number of quantization levels>
Topological entropy (TS) explains topological entropy whose formula looks exactly as KS. So, what is the difference since KS is also known as metric entropy and not known as Topological entropy?


texts: Language of walks in a grid – context-free?

texts:
Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square up, down, left and right, respectively.

Now consider the langauge of all strings representing closed walks (walks that end at their start point). To me, this would seem like any combination of $u$, $d$, $l$ or $r$. So would the language be represented as $L = \{u,d,l,r\}^*$? If so, this wouldn't be context-free right? Thanks.


texts: Average case complexity of search data structures

texts: Algorithms are generally studied in terms of average case complexity and worst case complexity? Is there also a kind of analysis called "average worst case" complexity?


texts:
I was reading (wikipedia) about how the rope data structure might be suitable for a text editor.  Within the article it mentions "If only nondestructive versions of operations are used, rope is a persistent data structure. For the text editing program example, this leads to an easy support for multiple undo levels."  I don't understand how the undo works in this.

For example, let's say i had an existing rope with the left leaf as "hello" and the right leaf as "world".  The parent (root) would have the value 5 (length of hello).  Then, if i were to delete "world" i am just left with the root and left (hello) node.  Now, if i wanted to "undo" the delete, haven't I already discarded the "world" node?  Traditionally "undo" is done by placing things on a stack, but in this case I don't understand if using a stack what to put on it or how to do the undo in general.


texts: Can an LL(k) parser parse any grammar without left recursion or common prefixes?

texts:
I'm being asked to create a "top down grammar" for a certain language (I'm pretty sure there's no such thing as a "top down grammar" but I think it means write a grammar that an LL(k) parser can parse).

I'm pretty sure the language is not LL(1), but I can remove left-recursion and common prefixes from it and still have an unambiguous grammar. But I'm a little confused about the significance of that. If I successfully removed left-recursion and common prefixes and the grammar is still unambiguous, is the language LL(k)? And does that mean it can be parsed by a top-down parser?


texts:
Given a sequence $x \in \{ 1,2,3...,\vert \Sigma \vert \}^*$ one wants to create a sketch of it say $s(x)$ of size $\frac{2c}{3}k (ln^2 k)$ bits. And that seems to be achieved as follows,

pick at random 2k-wise independent hash functions,

$h : [n \vert \Sigma\vert] \rightarrow [(k/3)ln (k)$

$h^0 : [n \vert \Sigma\vert] \times [2ln(k)] \rightarrow [c ln^2 (k)]$

(where apparently $c = 72e$ helps!)

For each new element $\sigma_i \in x$ the following update is done to the sketch

Let $bucket = h((i-1)\vert \Sigma\vert + \sigma_i )$
For $t \in \{1,2,3..,2ln(k)\}$

$sub-bucket = h^0((i-1)\vert \Sigma\vert + \sigma_i,t  )$
$d = (bucket-1)2cln^3k + (t-1)cln^2(k) + sub-bucket$
$s(x)_d = s(x)_d \oplus 1 $

Can someone kindly explain as to what exactly happened here?
I am not seeing the intuition at all..


texts: Why the name static and dynamic in static and dynamic scoping

texts:
I am wondering, from where static and dynamic scoping got their names.

After understanding the concept of static and dynamic scoping in C, what I assume is that whenever we failed to find out the declaration of the variable within the scope of the function than in order to resolve this name, we refer the global variable (which is declared at the time of compilation). As name resolution of a variable is done by a global variable which is declared at the time of compilation (static), therefore this scoping is called static scoping.

On the other hand, if the name of a variable is resolved by a dynamic variable (variable created at runtime) than it is called dynamic scoping.

Is this the reason why the static name is given to static scoping and dynamic to dynamic scoping?


texts:
I am trying to fuse point clouds into one. These Point clouds are acquired from multiple cameras. Below is the detailed information about setup-

Three Kinect v2 sensors are mounted on tripods in such a way that they are making 120 degree angle from each other in a horizontal plane. Hence one can assume that these Kinect sensors are kept in the circumference of a sphere and pointing towards the center of the sphere. All three Kinect sensors are tilted vertically downwards approximately 30 degrees. The object which is being scanned is kept inside the sphere and visible from all Kinect sensors.

I am able to acquire three point clouds simultaneously from these sensors. Now I want to fuse three clouds to make 1 compete cloud.

What algorithm would I use for this?


texts: The constant in the merge sort recurrence

texts:
Assuming that the worst case running time of merge sort can be described with this recurrence:

$\
T(n) =
\begin{cases}
  \theta(1) & \text{if }n = 1\\
  2T(\frac{n}{2}) + \theta(n) & \text{if } n\gt 1
\end{cases}
$

Introduction to Algorithms says that it is possible for the same constant $\ c $ to represent the time required to solve problems of size $\ 1 $ as well as the time per array element of the divide and combine steps, so that

$\
T(n) =
\begin{cases}
  c & \text{if }n = 1\\
  2T(\frac{n}{2}) + cn & \text{if } n\gt 1
\end{cases}
$

How is there a constant $\ c $ that can represent both times? Shouldn't the proper way to describe the recurrence be

$\
T(n) =
\begin{cases}
  a & \text{if }n = 1\\
  2T(\frac{n}{2}) + bn & \text{if } n\gt 1
\end{cases} \text{where }a\ll b
$

If the answer is dependent on the psuedocode provided in the book, I'll post it here. However, there is a single if statement in a trivial mergesort (size 1). Surely, the cost of that single if statement can't be the same as the sum of the costs of all the steps taken in the merge step, as well as the constant-time division of the problem into smaller problems?

Sorry if this has been asked before.


texts: Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable?

texts:
Let $PAL = \{ww^R\ | w\in\{0,1\}^*\}$.

Then let $A = \{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\}$

Is A semi-decidable (Turing recognizable or recursively enumerable)?

My try!

I said it is so here is my proof, tell me if I am way off base or tell me if A ought not to semi-decidable in the first place.

$\underline{Proof}$

A is semi-decidable by The Certificate Theorem, which states that:

If $A\subseteq\Sigma^*$ then $A\in SD$(semi-decidable) iff there is some decidable relation, $R\subseteq \Sigma^* \times \Sigma^*$, such that $\forall x\in\Sigma^*$, $x\in{A}$ iff $\exists y$ such that $R(x,y)$ holds.

We know that if $x\in{A}$ that means that $x=\langle M\rangle$, so we can choose $y = \langle M,w\rangle$ where $w\in{PAL}$. What we know is that when $M$ takes $w$ as an input it will accept (since we choose $w$ as an input), if that is the case then $w\in{L(M)}\subseteq{PAL}$. That means that $A\in{SD}$. QED

Any help would be greatly appreciated, have a great day!


texts:
I am intrigued by and understand the very basics of Proof Carrying Code (PCC) and I recognize that LLVM is a machine-independent intermediate language.  LLVM is the intermediate form of many languages, including the new Rust language.  Typed Assembly is another style of intermediate form which can be used to generate PCC proofs but it has not gained the same popularity/utility.  I've heard of Singularity, Verve and JX.

As I understand it, generating PCC proofs are within practicality even for large programs, but that their resulting size and verification burden (necessary only once per "installation") are non-negligible.  I don't care about 10x (discardable) proofs nor several hours of verification - I'm very interested in a provably-safe operating environment.

Is there anything missing from the LLVM language or type system that would prevent us from emitting such proofs?  Or can you tell that am I missing something about the bigger picture?

More

  PCC for what properties? Memory safety?

Yes, memory safety which I believe is a minimum policy required to ensure that a process cannot take over the kernel or another application.  Seems to me that (popularly) a message passing interprocess-communication scheme restores some of the functionality taken away by direct memory access (Erlang, Singularity OS).

  Do you have a citation/reference for your statement about practicality?

Here's something that suggests its practicality to me: "It has been shown that proofs for Java type safety can be compressed to 12%–20% of the size of x86 machine code ... but unfortunately this increases the proof checking time by a factor of 3".
-- Interpretation of Necula, Oracle-Based Checking of Untrusted Software by Franz

  What research have you done?

I've been following this topic (including the names I mentioned previously) over the years reading and absorbing what I can comprehend.

  I think it helps to separate "is it possible to do PCC for LLVM bitcode?" from "why doesn't the Clang compiler currently implement PCC?"

Yes, I'm mostly interested in "is it possible to do PCC for LLVM bitcode?" - but I'm not being too specific because I'm not confident that I understand how all the pieces fit together which is why I'm here trying to get an answer from a human who already gets it and can contribute to the understanding of people who are merely at my stage of understanding.

But see, related to your "why doesn't the Clang compiler currently implement PCC?", I would have assumed that the LLVM compiler (the one that goes from LLVM to assembly) would be the one capable of emitting the proof, since it still has higher level concepts of the code before it gets erased in the final binary (as does, I believe, TAL) and of interest because type-safe languages like C# and Rust compile to LLVM, possibly with enough type information to unify the approach among all LLVM languages.  So had I been more specific, I'd be getting shat on for that.

  I think it would help to clarify exactly what you're asking about

That's pretty much what I'm looking for!


texts: Linear programming IFF with equality constrain

texts:
Is it possible to write the following logical constrain in linear programming?

Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is

$y=1 \Longleftrightarrow v=k$.

I need this kind of constraint in linear programming to use it in AMPL, but I really can't find a way to write it down as a linear constraint.


texts: On what abstraction is a filesystem actually built on?

texts:
Data is read in terms of a block from a storage device(magnetic, optical, flash). Size of the block depends upon the filesystem and os. The physical device may have different units of storage like sectors.

Do filesystems create the abstraction layer directly over the physical device, or do they work over something called as a block device?

If they work over the block device then does it mean that when we create a partition table(gpt, msdos, mac) then block device abstraction is created and filesystems(fat, ntfs, ext) are then created for partitions of the device over the block device layer?


texts: If $L_1L_2$ is regular language then $L_2L_1$ is regular to?

texts:
We have two languages: $L_1,L_2$. We know that $L_1L_2$ is regular language, so my question is if $L_2L_1$ is regular to?

I try to find a way to prove it...

I can't assume of course that $L_1,L_2$ are regular...
So I look for a way to prove it.

I'd like to get any hint!

Thank you!


texts: Is every algorithm on bounded resources O(1)

texts:
Suppose that I have a restricted Turing Machine - it has finite tape and takes bounded input. Consider a program that halts on every input (which is at most $k$ bits). The set of inputs is finite, therefore the function describing running time is bounded and hence is $\mathcal O (1)$.

Therefore, when analyzing any algorithm that has been tuned to support some machine requirement (ex. input is 32 bit integer), if it halts, we may say it's $\mathcal O (1)$.

What am I missing here? What are arguments supporting/opposing this point of view?


texts: Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method

texts:
I'm trying to solve this recurrence. I applied the iterative method:
$$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum_{i=0}^{k-1}(n-2i)^2$$ So $n-2k=1$ when $n=2k+1$ and we have: $$\sum_{i=0}^{(n-3)/2}(n-2i)^2$$ Now how can I demonstrate that this series is $\Theta(n^3)$?


texts: Converting truth table to algebraic normal form

texts:
Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)?

I have seen that Sage has one implementation (official documentation):

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("12fe342a")
sage: B.algebraic_normal_form()
x0*x1*x2*x3*x4 + x0*x1*x2 + x0*x1*x3*x4 + x0*x1*x3 + x0*x1*x4 + x0*x2*x3*x4 + x0*x2*x4 + x0*x3*x4 + x0*x3 + x0 + x1*x2*x4 + x1*x3 + x1*x4 + x2*x3*x4 + x2*x3 + x2*x4

But, nowhere I could find the algorithm.

It would be helpful if someone kindly explains with a suitable example.

UPDATE The answer can be found here. It is copied below.


texts: Having problem understanding the formal definition of NP

texts:
So I'm having a tad bit of a problem deciphering the formal definition of NP. In my text book (Algorithm Design, Tardos et al) it says that a problem $X$ belongs to $NP$ iff;

there exists a "certificate" string $t$ such that $|t| \le p(|s|)$ for a polynomial function $p$ and an input string $s$.
there exists an efficient certifier $B$ that takes $s$ and $t$ as inputs and has polynomial time complexity.

I'm having a hard time understanding this problem in a more practical sense. Say for example I had to verify a solution for a Graph Coloring problem. Then I would take the graph $G = (V, E)$ and the number of allowed colours $K$ as input (the problem instance) aswell as the proposed solution (Let's call it $S$) that consists of the coloring of the graph $G$. In this example, what would be $s$ and what would be $t$?


texts: Difference between page table and inverted page table

texts:
I do not understand the difference between page table and inverted page table.
I know that both are used to translate the logical addresses into physical addresses produced by the processes necessary to store data in memory.

This is what I know on the page table.

Generally each page table contains an element for each virtual page and a table exists for each process.
This can lead to huge tables (programs with many pages).

I can imagine a page table like this:

Instead, this is what I know on the inverted page table.

It has only one page table for all processes.
This table has an entry for each real page (block of physical memory).
Each element contains the virtual address of the page stored in that physical location, with information about the process that owns that page.

So I represent the inverted page table like this:

Am I doing it right? Did I get it right?

Thank you

I don't understand if the information I have learned theoretically then I understood well.

I do not think that is more efficient an interved page table than a normal page table, indeed I find it most confusing.

As I understand it, each frame of the physical memory has a corresponding entry in the inverted page table.
I suppose that the memory has a large number of frames, then the inverted page table is huge and how do I keep it in RAM?
While if you use the page tables "normal", I do not keep all of them in memory at the same time, you just keep those of the currently active processes, or not?

And it is reversed (the arrows are reversed), as I map a logical address into a physical?


texts: What is the difference between consensus and mutual exclusion in Distributed Systems?

texts:
If we can achieve consensus, does it imply we can achieve mutual exclusion? Is there a difference?

Example : Paxos solves the consensus problem, can it also be used to solve mutual exclusion?


texts:
Let SAT-100 be the following problem:

Input: Any boolean logic formula

Output: True if there exists a combination of exactly 100 input variables that satisfy the formula.

This is the description of a problem that is apparently in $P$. (old exam question)

I have tried to design an algorithm but I got stuck, so here it goes:

Input: boolean logic formula F
    If(count(variables in F)) < 100:
       return false
    else
        # try all combinations of input variables

And here is the problem: building and evaluating all combinations of input variables can't seem to be polynomial because:

$$ { n \choose 100} = \frac{n! }{100!  \cdot (n-100)!} \in \mathcal{O}(n!)
$$

and this nasty factorial can't be bounded with any polynomial that I know of.

I don't think  the exam is wrong, so I must have overlooked something.


texts:
I am looking to create a series of closed volumes that represent the empty voids made by rooms in a house.

In order to do this, all I have is the raw geometry of all the elements that encapsulate these spaces (walls, floors and ceilings), in the form of closed meshes.

Some additional requirements...

The elements that encapsulate a space may not fit together perfectly, i.e, the room may not be watertight.
The shape of the room could be quite complex, i.e the dome like roof of a conservatory.
Rooms will have openings for doors and windows that will need to be ignored.


texts:
Let's suppose I have an NP-complete problem A.

Can there be $A_1$, $A_2$ such that $A_1$ and $A_2$ are disjoint, $A = A_1 \cup A_2$, and $A_1$ and $A_2$ are NP-complete?

My guess would be yes.  For example, just partition SAT into formulas with an even number of variables and formulas with an odd number.

Follow up:  Can I partition $A$ into infinitely many such $A_i$? (I suppose yes: take formulas with $2^n$ variables, $3^n$, $5^n$, $7^n$, $11^n$, or something like that)


texts: I understand that knapsack problem is solved with dynamic programming in O(nW) time which is not polynomial but there is a greedy solution for knapsack problem which solves it with O(nLgn) time so how is it that there exists an algorithm with polynomial time for knap sack but it is still considered a npComplete?


texts: Logical formula in DIMACS, SAT, Schaefer's dichotomy theorem and software to test it

texts:
I have a very complicated formula logical (CNF) in the file DIMACS.
The question is as follows. The formula has hundreds of millions of clauses (assume billion) and a lot of variables.
It is a reconstruction of a logic circuit.
MiniSAT returns me the result for the SAT problem very quickly (a few seconds).
Can I increase the amount of input logic circuit but time solving logical formula does not increase exponentially. It increases very slowly (and sometimes completely not increasing).
Is there any ready-made software / scripts that can help me understand why the SAT solver solves the problem so quickly?
For example, if there is the software that the input file will DIMACS, and writes the output if the formula is P class (and at which the condition?) of Schaefer's theorem dichotomy?
Schaefer's theorem dichotomy conditions:

all relations which are not constantly false are true when all its arguments are true;
all relations which are not constantly false are true when all its arguments are false;
all relations are equivalent to a conjunction of binary clauses;
all relations are equivalent to a conjunction of Horn clauses;
all relations are equivalent to a conjunction of dual-Horn clauses;
all relations are equivalent to a conjunction of affine formulae.


texts: Proving that Hamiltonian Cycle is reducible to a travelling problem?

texts:
I chanced upon the following question online:

  A company has two trucks, and must deliver a number of parcels to a
  number of addresses. They want both drivers to be home at the end of
  the day. This gives the following decision problem.

Instance: Set V of locations, with for each pair of locations
v, w ∈ V , a distance d(v, w) ∈ N, a starting location s ∈ V ,
and an integer K.

  Question: Are there two cycles, that both start in s, such that every
  location in V is on at least one of the two cycles, and both cycles
  have length at most K?

The solution provided uses Hamiltonian Cycle to prove the parcel problem is NP-Complete.

  Given any instance of Hamiltonian Cycle with n vertices, construct the
  following special instance of the above problem.

  Copy the graph and make the distance d(v, w) equal to 2 if there is    an edge in the graph, and 4, otherwise.
  Label one of these vertices as s. Add one vertex 0 such that d(s, 0)    = d(0, s) = n and d(v, 0) = d(0, v) = 2n + 1 for all v != s. The
  threshold K is equal to 2n.

The explanation provided is as follows:

  The only thing we have to do is to keep the other driver busy, which
  is easily taken care of by including an additional vertex with
  distance K/2 from s and distance K + 1 to all other addresses.

I tried constructing a simple graph of N = 3 whereby each vertex is connected by an edge of distance 2. Then I introduced a new node which is distance 4 away from the source vertex(i.e. starting point), and distance 7 from every other vertex.

But I am unable to understand how this construction fits into the original decisional problem. What exactly does the solution mean by "keeping the other driver busy?"

Solution link.


texts: Isn't ZKP is a reduction to a hard problem, rather than true zero knowledge?

texts:
Take for example "Hamiltonian cycle for a large graph". The proof works by starting with a graph G that contains a hamiltonian cycle, then constructing an isomorphic graph H, and then either showing the mapping between the graphs G and H or releaving the cycle in H.

It is said that we prove that that we know a hamiltonian cycle in G without revealing it.

But this assumes the verifier does not have unlimited computational power. If he had it, he could ask to reveal the cycle in H, and use his unlimited computational power to work out the isomorphism. I understand that if the verifier had unlimited power, he could find the cycle in G directly. But that's not my point. What I find strange is that we are relying on "hard problems" in the proof itself.

Are there ZKP protocols that do not rely on hard problems? Hard problems are only hard according to the state of the art. It is not proven that NP is not P, therefore, in my mind, this sounds like security through obscurity in some sense.


texts: What's the name of this tree-like data structure?

texts:
I'm currently experimenting with some tree-like data structures and came up with a structure that has the following properties:

It consists of nodes and leaves
It has a single root element
Both nodes and leaves each hold a single element
Each node can have a non empty list of subtrees (a leaf could be considered a node with an empty list of children)
All elements inside the tree are of the same type and can be compared against each other
There are no duplicated elements inside a tree (this is especially interesting when it comes to inserting elements)

An implementation of this in Haskell could look like this (without the Eq constraint on a that would be required to compare the elements):

data Tree a = Node a (NonEmpty (Tree a)) | Leaf a

From my (rather limited) theoretical knowledge about data structures like this I think that it is some kind of unordered, unique tree.
I guess that there is a well-known data structure somewhere out there and I'm hoping that someone can point me to the name as well as some resources about it.

I'm especially interested in algorithms for typical operations on this data structure:

Traversing the tree
Adding a single element to a tree
Removing a single element from a tree
Adding a tree to another tree (if the root element is already contained in the target tree, the tree should become a subtree to this element)
Removing an element (including its children) from a tree

To summarize: Is this data strucure well known? If so, what is the name for it and where can I find more information about efficient algorithms for operations on this data structure?


texts: Someone explain the Venn diagram for the logic equation (A+B)(B+C)

texts:
I posted a similar question  here, however I have another question regarding Venn diagrams and logic circuits...

In this problem:

$$(A+B)(B+C)$$

Wouldn't the Venn diagram look something like this?

Because it simplifies to $B + AC$? And you can either have the $B$ region, the $AC$ region, or both?

However, apparently it's supposed to look something like this:

Which I don't understand... Because by the logic that you have $AB$ and $BC$, couldn't you justify saying that you can also shade in $A$, or shade in $C$ (by themselves)?

OR, does saying $A$ mean you shade in EVERYTHING that contains $A$? And only don't shade in the intersection if you had something that said $A * \overline{B}$?


texts: How to remove cycles from a directed graph by edge contraction?

texts:
We have cyclic directed graph (possibly disconnected). For cycles consisting of two vertices A->B and B->A, we replace them by a single vertex. In case of A->B, B->C, C->A we also replace them by one vertex. We replace N vertices when all reachable from each other. Edges leaving a vertex stay as edges leaving the group containing the vertex.
For example,

digraph cyclic {
        rankdir=BT;
01
2->3
3->2
5->2
6->4
8->3
9->4
a->4
a->9
9->a
b->8
b->c
c->b
6->7
7->8
8->6
}

We must obtain

digraph acyclic {
        rankdir=BT;
01
5->23
678->23
678->4
a9->4
bc->678
}

How is algorithm?
Practical application of problem: we have class where method depends from fields and other methods. How decomposite to max number smallest classes? we allow multiple inheritance, inheritance diamond, but not allow cycles.


texts: Is "Find a Steiner Tree of cost < K" NP-hard?

texts:
Finding the minimum Steiner tree is well known NP-hard.
It seems obviois that asking "find a Steiner tree of cost < K" has to be NP hard, because I could solve the original problem by repetedly calling an algorithm that solves the second. But is this "repeteadly call"/loop a valid reduction? There seems to be something fishy with it, isn't it exponential in the number of bits of K (like the famous knapsack DP algorithm)?

Thanks


texts: Can Pareto Optimality be compared to Nash Equilibrium?

texts:
Given a state $s$, and a value function $v^i$ that determines the expected payoff for the i-th agent in that state, can the two definitions below, one of Nash equilibrium and another of Pareto optimality be compared to one another?

Nash equilibrium:
$$v^i(s, \pi^i_*, \pi^{-i}_*) \ge v^i(s, \pi^i, \pi^{-i}_*)\ \ \  \forall\ \  i \in \{1, 2, \cdots,N\}$$

Pareto optimality:
$$v^i(s, \Pi_\#) \gt v^i(s, \Pi)$$ for atleast 1 agent $i$,
and,

$$v^j(s, \Pi_\#) \ge v^j(s, \Pi)\ \ \  \forall\ \  j \in \{1, 2, \cdots,N\}$$

Notation Used

Nash Equlibrium = $(\pi^i_*, \pi^{-i}_*)$

Pareto Optimal stragey = $\Pi_\#$


texts: Efficiently locating the maximum value in interval over large amounts of data points

texts:
I have a set of $n$ two-dimensional data points $(x_i,y_i)$.  I want to efficiently answer the following query: Given an arbitrary interval of $x$-values, find the highest and lowest points within that interval.  In other words, for this query we are given an interval $[\ell,u]$, and we want to find the point $(x_i,y_i)$ such that $x_i \in [\ell,u]$ and $y_i$ is maximal (or minimal).

What data structure would be appropriate for this task?  I'm interested in both the static case (where the set of points doesn't change) and the dynamic case (where we also want to be able to insert and/or delete points from the set).


texts:
Can any expert explain the reasoning behind the constraint in the
following formulation of the minimum spanning tree?

  To formulate the minimum-cost spanning tree (MST) problem as an LP, we associate a variable $x_e$ with every edge $e \in E$. Each spanning tree $T$ corresponds to its incidence vector $x^T$, which is defined by $x^T_e = 1$ if $T$ contains $e$ and $x^T_e = 0$ otherwise. Let $\Pi$ denote the set of all partitions of the vertex set $V$, and suppose that $\pi \in \Pi$. The rank $r(\pi)$ of $\pi$ is the number of parts of $\pi$. Let $E_\pi$ denote the set of edges whose ends lie in different parts of $\pi$. Consider the following LP:
  $$
\begin{align*}
\min &\sum_{e \in E} c_ex_e \\
\text{s.t. } &\sum_{e \in E_\pi} x_e \geq r(\pi) - 1 \quad \forall \pi \in \Pi, \\
& x \geq 0. \\
\end{align*}
$$


texts: Algorithm To Process Purchases Efficiently and Apply Constraint

texts:
I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows:

customerId  itemId  cost

The customer could have purchased the same item more than once in a day and at different times so there will be multiple entries for a customer and item combination. At the end of the processing, the program should print the customerId and the total cost of all their purchases, but with a discount applied so that the cost of the most expensive item is removed.

My algorithm is as follows:

Create a map, call it M-1, with the customerId as key and a running total cost as the value i.e. customerid -> running_total_cost.
Create another map, call it M-2, with the key as (customerId and itemId) and for the value the running subtotal. That is, it keeps a tab on how much of this item this customer has bought.
For each line in the file, upsert into M-1 the customerId and add the cost of this item to the running total. Also upsert an entry in M-2 containing the running total of this customer and item purchased. So M-1 has this structure:

customerId  RunningTotal

And M-2 has this structure

customerId ItemId RunningTotal

After the file has been completely processed in step 3, for each entry in M-1, get the customerId and look-up the customer in M-2. In M-2, run a loop so that it finds the most expensive purchase this customer made. This can be done by creating a temporary variable and looping through the purchases the customer made and comparing the current value of this variable with the next value. Replace the value of the variable with the new highest total At the end, the highest value will remain.
Print table

My question is whether this can be processed any faster than this?

UPDATE

I believe I have an optimal solution for this now. The algorithm is as follows:

Make one pass through the file. For each line, create a map with the following structure

Map[CustomerId, Map[ItemId, subtotal]]

After processing the file completely and making the above map, then do the following loop

for each customerId
  count = 0
  total = 0
  highestSubtotal = 0
  for each itemId
     total += subtotal
     highestSubtotal = max(highestSubtotal, subtotal)
     count += 1
print CustomerId, if count > 1 then total - highestSubtotal else total

I don't think I can optimise that anymore unless anybody can think of something else.


texts:
As we know Dynamic programming has two techniques.

Bottom up dynamic programming approach.
Top down memoization approach

Normally dynamic knapsack problem is solved using Bottom up dynamic programming approach.can we solve dynamic knapsack problem using Memoization approach?


texts:
I'm trying to understand what is the minimum of the following function,

$$
f(\mu) = \frac{1}{n}\sum_{i=1}^n F\left(\frac{\pi(i)}{n}\right) (x_i - \mu )^2
$$

where $F$ is a step function that assign $1$ to any $t \in [0, \gamma]$ and $0$ in $(\gamma, 1]$, $\pi$ is a permutation that sorts the $i$s based on the ascending ordering of the losses $( x_i - \mu )^2$ and  $\mu$ and $x_1,\ldots,x_n$ are real numbers. I was thinking that perhaps the minumum of $f$ is achieved by the trimmed mean, namely: sort the $x_i$s discard the first $(1-\gamma)/2$ and the last $(1-\gamma)/2$ of the $x_i$ and compute the arithmetic mean of the remaing points. However, it isn't as a simple numeric example shows.

Any ideas or maybe suggestions (perhaps it is a known problem)? Many thanks in advance.


texts: What is the name of the problem? (partitioning graph into three covers)

texts:
I was wondering if this problem has a name:

Given a simple graph whose edges are colored red, blue and green, $G=(V,B\cup R\cup G)$, is there a vertex-coloring $c:V\to \{B,R,G\}$ such that every edge has an endpoint with the same color?

Also, is this known to be NP-complete?

This can also be viewed as a special case of CSP (or a generalization of 2SAT) where each constraint is a disjunction of 2 variables that could take one of three values, and there are no two constraints on the same variables-pair.


texts: Curry–Howard correspondence and functional programming "reliability"

texts:
The first time I heard about functional programming, someone told me "it's more reliable to code in a functional style because your type system is like a proof of correctness".
I recently learnt about the Curry-Howard (CH) correspondence and I think this is what he was using as a basis for his assertion about functional languages.
However, I have trouble understanding how far this leads to "more reliable programs".
Especially, here is my understanding:

In the CH view, a function type A -> B is the same as an implication $A \implies B$ in some constructive view of logic, and so on... (union type, product of type, etc.)
So if we end up being able to build an instance t of a type T it means we used only the available function types / implications using the available variables / assumptions.

Still, there are many ways a program written this way could be incorrect :

If I have several variables a, b, c, ... of the same type A available, I may use a transformation A -> B on the wrong one.
I may have different functions with the same signature A -> B but different use cases, and the type system won't be able to detect if I use the wrong one.

My questions are:

In practice, do functional programming languages enforce things like "there should be no more than one instance of a type" or some variant to avoid those kinds of errors ?
Is there a theoretical background in which we enforce more restrictions on functional languages and give the "more reliable" a stronger meaning ?


texts: Convert DAG whose transitive reduction is non-planar to a planar DAG with same transitive closure

texts:
For any non-planar DAG, we can compute the transitive reduction, and sometimes it will be planar (e.g. $K_5$).

However, sometimes the transitive reduction is also non-planar. For example, $K_{3, 3}$'s transitive reduction is just $K_{3, 3}$.

Alternatively, it's possible to add vertices and adjust the edges to maintain the same transitive closure as $K_{3,3}$, while producing a planar graph:

Here $U_{i}$ means "utility i" and $H_i$ means "house i", as per the Three Utilities Problem.

Is there an algorithm that can accomplish this for a general DAG, so that the resulting graph is planar and can be used with Thorup's algorithm?


texts:
In Bandit Based Monte-Carlo Planning by Levente Kocsis and Csaba Szepesvári (2006) they propose the UCT algorithm which is derived from the UCB1 algorithm.

UCB1 algorithm:
$$X_j + \sqrt{\frac{2\ln n}{n_j}}$$

where $X_j$ is the average reward for machine $j$, $n_j$ is number of times $j$ has been played and $n$ is the entire number of games played.

In comparison, UCT is
$$\frac{W_i}{n_i} + c \sqrt{\frac{\ln N_i}{n_i}}$$
where $\frac{W_i}{n_i}$ is  win:lose ratio (the same as $X_j$),
$c$ is temperature parameter, which is often set to $\sqrt{2}$ (so they just put it in front...)
and $\frac{N_i}{n_i}$  is number of total games played for parent Node / number of games played for the corresponding node, which is the same as $\frac{n}{n_j}$.

So what's new here?


texts: I am an IB student doing SL math. For my math IA i picked the topic of monopoly and the optimal way to play. However, in this IA there is a massive matrix that needs to be built to see how the long term possibilities of landing on a given square. I found someone's code on this page https://arxiv.org/pdf/1410.1107.pdf, but I don't know how to code it. I took a grade 11 course in computer science, but I barely know anything LOL. I used visual studio in this class, and I hope that I can use visual studio to code this. Can someone help? I have no idea if it's possible. thanks guys!


texts: In a single cycle datapath, do 'decode' and 'operand fetch' occur simultaneously?

texts:
After instruction has been fetched, does it go to control unit and register file at the same time or one after the other?
For example if the control unit and register read both have 80ps delay, and we're calculating the total delay for a cycle, would we take their delay as 80ps(if they occur simultaneously) or if they happen one after the other so in that case delay of decode and operand fetch would be 160ps. Which one is correct?


texts: Optimal solution for Weighted points problem

texts:
Problem:

  Fix a constant $k$. Given a set of $2d$-dimensional points $N = \{N_1, N_2, N_3, \dots, N_n\}$, each associated with an arbitrary weight, find a set of points $X = \{X_1, X_2, X_3, \dots, X_k\} \subseteq N$ such that the pairwise distance between any two points in $X$ is at least $D$, and $\sum_{i=1}^k \mathit{Weight}(X_i)$ is maximized.

It would be nice if I could get the exponential solution and then an efficient heuristic so that I can relate to why and how the problem reduces.
The greedy way to do it would be to sort the points by weight and exclude points which are at distance $D$ from the current point that is being processed. Is there a better way to do it?


texts: Graphs with chromatic number $(\chi(G) \ge 3 )$ other than odd cycle (Triangle free)

texts:
Chromatic number denoted by $\chi(G)$ of graph $G$ is the minimum number of colours required to properly colour the given graph.

For ODD Cycle chromatic number is 3 and it does not contain triangle as a subgraph. I thought about complete , star, wheel graphs etc, but they don't satisfy the conditions.

I am looking for examples of graphs of $\chi(G)$ $\ge 3$, but does not contain a triangle or odd cycle as subgraph.


texts: What are the justifications and historical reasons regarding the choice between the words 'calculus' and 'algebra'?

texts:
The principles of calculus, historically, are differentials and integrals [1], while those of algebra are operators and equation solving [2]. Contemporary principles are analysis and abstract objects, respectively.

As an example case, why is relational algebra not called a calculus, and why is the π-calculus not called an algebra?


texts:
I have the following context-sensitive grammar:

$$
\begin{align*}
&S \to xSy \mid a \mid b \\
&Xa \to aa \\
&Xb \to bb \\
&Y \to a
\end{align*}
$$

I know what it does, as it always ends in $a$ and is preceded by 3 $a$s or 3 $b$s. I'm just not sure how to write this in set notation and would appreciate any help. Would it be something like this?
$$ L = \{a^n,b^m \mid n \ge 1, 0 < m \le 3 \} $$


texts: Why cannot we reduce the Emptiness problem of LBA to the Acceptance problem of LBA?

texts: I am a little bit confused about the emptiness problem of the linear bounded automaton (LBA). I know that this problem is undecidable. However if we assume that is decidable, what could be wrong if we reduce it to the acceptance problem of LBA?


texts:
I'm doing my homework, but there's one task that I didn't get the idea.

Task:

Recall the alternative definition for the star of a language A that we gave just before Theorem 2.3.1. In Theorems 2.3.1 and 2.6.2 (which is about closure under union operation), we have shown that the class of regular languages is closed under the union and concatenation operations. Since $A^* = \cup_{=0}^\infty ^$, why doesn’t this imply that the class of regular languages is closed under the star operation?


texts: Upper bound $T(n) = 9T(\sqrt[3]{n}) + O(1)$

texts:
The problem is this: Use the recursion-tree method to give a good asymptotic upper bound on $$ T(n) = 9T(\sqrt[3]n) + \Theta(1). $$ I am able to get the tree started and find a pattern with the sub-problems, but I am having difficulty finding the total cost of the running times throughout the tree. I cannot figure out how to get the number of sub-problems at depth $i$ when $n=1$. I have a feeling the answer is $O(\log_3 n)$, but I cannot verify that at the moment. Any help would be appreciated.

The recurrence can be written as $$T(n) = 9T(\sqrt[3]n) + C, $$ where $C$ is some constant, since any constant will always be treated as 1 asymptotically. My recursion tree is explained by each level below:

Level 0: This is the constant $C$

Level 1: $T(\sqrt[3]n)$ is written 9 times which represent the sub-problems of $C$. This adds up to $9C\sqrt[3]n$.

Level 2: Each of the 9 sub-problems from level 1 gets divided into 9 more sub-problems, which are each written as $T(\sqrt[9]n)$. All of these add up to $81C\sqrt[9]n$.

Sub-Problem Sizes and Nodes: The number of nodes at depth $i$ is $9^i$. We know that the sub-problem size for a node at depth $i$ is $n^{1/3^i}$. The problem size hits $n=1$ when this size equals 1. Solving for $i$ yields:

$$ (n^{1/3^i})^{3i} = 1^{3i} n = 1^{3i}. $$

This results in $n$ being 1 which doesn't give a logarithmic form!


texts: How does secondary clustering occur in hashing?

texts:
One of my friends said me that secondary clustering is the phenomenon occurring when the probe sequence has the same initial value. This definition shows that secondary clustering occurs in linear probing as well and not only in quadratic probing (which I misunderstood while reading the CLRS text).
Secondary probing occurs as friend said and the same thing is written in CLRS and since the definition was given in the quadratic probing section, and how the language was used made it look like that secondary clustering occurs only in quadratic probing.

“Also, if two keys have the same initial probe position, then their probe sequences are the same, since $h(k_1, 0) = h(k_2,0)$ implies $h(k_1, i) = h(k_2, i)$. This property leads to a milder form of clustering, called secondary clustering.”- CLRS 2nd edition page $240$.

What I understood after reading the excerpt again is that : secondary clustering says that small small clusters start building at longer distances.

I feel that this is caused by two keys having the same probe sequence as a result of which say if $k_1$ , $k_2$, and so on the keys have the same probe sequence and if they are inserted in that order, and their probe sequence are $x_1,x_2,...$ then $k_1$ gets position at $x_1$, $k_2$ at $x_2$ and so on.. Thus this leads to the formation of clusters spaced at longer distances. But I feel this explanation which I came up to be quite vague, at least I could not visualize with a example of the situation.

I want to know how two keys having the same initial probe positions leads to this secondary clustering?
Primary clustering means that long stretches of clusters are formed and they tend to grow in side because of the fact that that a cell following a cluster of $i$ elements in a hash table with $m$ slots has a probability of $\frac{i+1}{m}$ to get filled. This is the cause of primary clustering. I want something this concrete to convince me.


texts: Stroke Extraction to recreate Chinese characters

texts:
I was going through the project lists of Andrew NG from his Stanford machine learning course and I found a project based on recreation of calligraphic characters. To do so firstly we need to extract strokes from characters and I can only understand it in bits and pieces and I cannot understand at all how to implement it in matlab.

I also read the research paper that the stroke extraction method is based on. But I did not understand that too like there were some terms that I could not understand. And not to mention I can't understand just how to implement all the pixel related operations mentioned. I am a beginner in image processing. Ss please any help is appreciated.

Quoting some lines from the paper:

  We use the direction contribution of the segments to estimate the degree for each pixel on the thick-line image. Given a binary image, for each black pixel $p(r,c)$, let $D_k(r,c)$ denote the orientation distance between the pixel and the boundary point along the $k$th quantized orientation, where $k = 1, 2, \dots, M$, and $M$ is an integer that denotes the quantization number from $0^\circ$ to $360^\circ$ . The orientation distance is called point-to-boundary orientation distance (PBOD). The distribution of the PBODs contains information
  about the degree of each pixel. We can easily tell that the PBODs along the quantized orientations of the branches are much larger than that along other quantized orientation. So, to estimate the degree of each pixel, we need only calculate the number of the crests of the distribution of all the PBODs of the pixel. Figure 2 shows some cases of the distribution. The resolution of quantization is $3^\circ$.

What is quantisation and orientation distance, and how to implement these in matlab?


texts: How to find a context-free grammar from a difficult language?

texts:
Some Languages are trivial to find their respective context-free grammar. Like for example $ L= \{a^nb^n: n \geqslant 0\}$. However some are really difficult to solve. I would like to have some advice on how I can tackle them.

For example I have the following language that I have been trying to solve for a while :

I tried to divide the problem into three cases as follow:

case i: na $\le$ nb

case ii: nb $\le$ na $<$ 2nb

case iii: na $\ge$ 2nb

The first case was easy to solve however I am stuck in case ii. At this point I don't even know if the procedure that I chose is the correct one.

EDIT: It is not an duplicate 3 of the links that you have provided me are not the same problem one of them is the same suggests the same strategy however doesn't solve the problem.


texts: Faster maximum weight matching algorithm in bipartite graph

texts:
I need to do a maximum weight matching in bipartite graphs rather than maximum weight perfect matching (which means that there is no need to match all the nodes).

The nodes each side are both (at most) the level of 10^3 and are usually unbalanced in size. The graph is globally sparse while locally dense. (I don't know whether this will give any insight. You may ignore this and see the problem as a maximum weight matching in a complete graph.)

To explain this more precisely, I'll give some examples:

Example 1: 100 lefthand side nodes and 1,000 righthand side nodes, with sparse rate varying from 1.0, 0.5, 0.2, 0.1 to 0.01. By sparse rate, I mean there are at all sparse_rate * lefthand_nodes * righthand_nodes non-zero arcs.
As I need to find a maximum weight matching rather than a maximum weight perfect matching, I have to add additional 900 nodes to the lefthand side and fill the weight matrix (1000 * 1000) with zero because the common bipartite maximum weight matching algorithms I found are all prepared for perfect matching. That makes the actual sparse rate even smaller (equals 0.1 * the given sparse rate).
Example 2: 1000 lefthand side nodes and 1000 righthand side nodes, with sparse rate varying from 1.0, 0.5, 0.2, 0.1 to 0.01.
Example 3: (To explain locally dense) 100 lefthand side nodes (equally divided into 10 groups L_1, L_2, ..., L_10, with 10 nodes in each group) and 1000 righthand side nodes (equally divided into 10 groups R_1, R_2, R_3, ..., R_10, with 100 nodes in each group). L_i and R_j are densely connected if i == j but sparsely connected if i != j.

I know KM(Kuhn－Munkres algorithm) can achieve O(n^3) and now it is in use. The problem is that I want to do this task faster and I can tolerate controllable loss less than 5% (that is, the result sum of weight should be no less than 95% of the optimal solution).

But in my opinion, approximation algorithms seems a bad option as the greedy algorithm (sort the arcs, and choose applicable arcs to match from maximum weight to minimum weight) achieves the best result in most cases and runs very fast (and the running time is stable).

So do any of you guys know some algorithms can practically outperform the KM algorithm? Or any other papers look promising. Suggestions are welcomed!

Following are some methods I have tried:

I have tried a linear approximation algorithm from Linear-Time Approximation for Maximum Weight Matching which is proved to achieve $O(1-\epsilon)$ in $O(m/\epsilon*\log(1/\epsilon))$ time. It seems good, but I implement it and find it preforms worse than KM in practical (for the given cases) and sometimes its results are worse than results of greedy algorithm. :(
I have trie an algorithm called csa: An efficient cost scaling algorithm for the assignment problem. This works slightly better than KM when lefthand side nodes and righthand side nodes are balanced but significantly slower than KM when unbalanced. I think the problem may come from the huge amount of zero arcs I've added.

Thanks a lot!

EDIT 2016/09/01: More precise condition, some examples added, "locally dense" explained, some other methods tried.


texts: What is the difference in time-complexity for sorting these 2-d arrays?

texts:
Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements

Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements.

It is given that each row is sorted in ascending order,
Can you sort each of these in $O(n\log(n))$ or better using comparison sort?

I'm leaning towards k-way merge implementing a min-heap following this implementation merging sorted arrays, but I can't seem to figure out what the difference between this cases is.

$B$ for example will have $10$ elements constantly in the min-heap, so the time complexity will be $10n \log(10) \in O(n)$? Is this even possible in comparison sorts?

While $A$ would have $n/10$ elements in the min-heap, but are the run times equivalent?


texts: Slicing clusters of non-black pixels from an image into separate images

texts:
The backstory

I have spectrograms of certain repeating sounds. The background of the spectrograms are black and could easily be made transparent if that would help. The sounds are easily distinct from the background. As shown below, each sound is a series of connected pixels of various colors.

What I want to do

I would like to separate each of the sounds into separate images or slices. That is, from the above example I would like to isolate the sounds into something like the following example.

If you are familiar with Unity 3D, they do something similar with their "Sprite Slicer" that creates a rectangle around objects on a transparent image.

My attempt of an algorithm

Select non-black pixel
For each neighboring pixel
  If pixel is black
    Try each non-visited neighboring pixel again, traveling a maximum of three pixels away ( a sort of threshold )
  If pixel is non-black
    Add to a list of significant pixels and travel to neighboring pixels
Mark selected pixels as visited and select a new non-black pixel

This would result in a list of lists containing pixels where each list is the extracted sound or cluster of pixels that could be compiled into images.

My concerns

I know this has been done before and is called something, but for the life of me I cannot find the words to describe it (hence the poor title).

My algorithm feels non-standard and potentially slow and poorly written. It should work, but it's not it.

Questions

What is this called, how can I find more about it?

How do I succeed in extracting the sub-images as shown by the example?


texts: Non-deterministic Turing Machine recognizing a context-free Language

texts:
This question is taken from an exam of a Computer Theory Course.

  Describe how a NON-Deterministic Turing Machine with two tapes recognize the language generated from the grammar: $ S \rightarrow SS | (S) | )S( | \epsilon $.

Tape 1: Read-Only & monodirectional
Tape 2: Read and Write, bidirectional

My guess:

Example of string generated by this language: $w_1 = ()())($  $w_2 = )()($
$w_3 = )))((()($

I think that the Turing Machine should recognize strings such that for every open (close) parenthesis there is another close (open) one.

With non-determinism: I need to guess where a portion of string is generated by a valid production, but i have some troubles to formalize this concept. Any hints?

For the string $w_2$:
One configuration in the computation tree would be $)(q_c)($ where $q_c$ identify the starting point of the production.


texts: Does Linear Discriminant Analysis make dimensionality reduction before classification?

texts:
I'm trying to understand what LDA exactly does when used as a classifier, i've understood how the dimensionality reduction works and i've understood that the classification task is carried out with the application of Bayes' theorem, but i still can't figure out if LDA executes both operation when used as a classification algorithm.
It's correct to say that LDA as a classifier executes by itself dimensionality reduction and then applies Bayes' theorem for classification?
If that makes any difference, i've used LDA in Python from the sklearn library.


texts: What is the complexity of this subset merge algorithm?

texts:
Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath.

The original algorithm posted had a major flaw in its working. I tried my best but could not get the desired accuracy in presenting the algorithm in pseudo code and/or Set Theory notation. I am thus posting python code, which has been tested and produces the desired results.

Note that my question, however, remains the same: What is the time complexity of the algorithm (assuming that powersets are already generated)?

# mps is a set of powersets; below is a sample (test case)
mps = [
        [       [], [1], [2], [1,2]     ],
        [       [], [3], [4], [3,4]     ],
        [       [], [5], [6], [5,6]     ]
      ]

# Core algorithm
# enumerate(mps) may not be required in languages like C which support indexed loops
len = mps.__len__()
for idx, ps in enumerate(mps):
    if idx > len - 2:
            break;
    mps[idx + 1] = merge(mps[idx], mps[idx+1])   # merge is defined below

# Takes two powersets and merges them
def merge (psa, psb):
    fs = []
    for a in psa:
            for b in psb:
                    fs.append(list(set(a) | set(b)))
    return fs

Output: mps[-1]   #Last item of the list

Running the above example will result in listing out the powerset of $\{1,2,3,4,5,6\}$.


texts:
Define:
$
\lg x = \log_2x
$.

Let
$
f(n), g(n)
$
be some non-negative functions.

Define
$
f(n) = \Theta (g(n))
$
if
$$
\exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n)
$$

I want to prove that the function defined by the recurrence relation
$
T(n) = 16(T/4) + n^2\lg^3n
$
has the asymptotics
$
T(n) = \Theta(n^2\lg^3n)
$

I wanted to prove that by substitution method:

$$
T(n/4) \leq n^2\lg^3n
$$

Now,

$$
T(n) \leq 16(n^2\lg^3n) + n^2\lg^3n = 17n^2\lg^3n
$$

But in order for the proof to work, I should have gotten

$$
T(n) \leq n^2\lg^3n
$$

I also need to show that this is a lower bound, but I want to start by showing that it's an upper bound.

What is the right way to prove these things?


texts: Language of TMs such that one state is visited most often

texts:
To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset \Gamma$ are the input and working alphabet, $q_0, q_F$ are the initial and final states, and $\delta : Q \times \Gamma \times Q \times \Gamma \times \{L,N,R\}$ is the transition function. I am talking about single-tape TMs without input or output tape, so the initial configuration of input $w$ is just $B^{-\omega} q_0 w B^\omega$, where $B$ is the blank symbol.

The language I am considering is $L$ of all Turing machines $M$ which satisfy the following: There is a state $q$ of $M$ such that on the run of $M$ on the empty word $\varepsilon$, $q$ is visited more often than any other state.

"More often" talks about the cardinality, i.e. $q$ is visited more often than $p$ if $p$ is visited $n$ times (finitely often) and ($q$ is visited infinitely often or $q$ is visited finitely often but $>n$ times).

I came up with this language as an exercise for students, when I found that neither I nor any colleague I asked could come up with precise decidability results.

It is clear that $L$ is not coRE and therefore undecidable. We can, for example, reduce the epsilon halting problem $H_\varepsilon$ to $L$ by inserting a new state and have the TM visit that state once after each step of computation.

Unsolved so far is the question whether $L$ is RE. When allowing multiple tapes, it is not, as we can reduce $\overline{H_\varepsilon}$ to $L$. However, for single-tape TMs, our last guess was that it is enumerable by using the fact that a positive input which does not halt has to stay in a single state forever and can only expand the tape into one direction from that point on. We could not come up with an exact solution so far though.


texts: Dynamic testing of down casts as explained in TAPL

texts:
On page 195 of Pierce's TAPL book, he states that one can replace a down-cast operator by some sort of dynamic type test. Then he gives the following rules:

T-Typetest:

$\dfrac{\Gamma \vdash t_1:S \;\; \Gamma,x:T \vdash t_2:U \;\; \Gamma \vdash t_3:U}{\Gamma \vdash \text{if } t_1 \text{ in } T \text{ then } x \to t_2 \text{ else } t_3 \to t_3: U}$

E-Typetest1:

$\dfrac{\vdash v_1:T}{\text{if } v_1 \text{ in } T \text{ then } x \to t_2 \text{ else } t_3 \to [x \mapsto v_1]t_2}$

E-Typetest2:

$\dfrac{\nvdash v_1:T}{\text{if } v_1 \text{ in } T \text{ then } x \to t_2 \text{ else } t_3 \to t_3}$

There is no further explanation and I'm unaware of how to interpret these rules. Reviewing them, I realize that the first is a typing rule and the second and third are evaluation rules. However, the syntax is a bit strange. What are the arrows in each branch of the if? Why the if includes the insyntax?


texts:
We can use DFS to find a cycle in a given graph. The idea is that a cycle exists if we can find back edge in the graph. First I just want to detect if a cycle exists, if so return true else false. Here is what I have got so far:

DFS(G,s)
  for all v in V do
    color[v] <- white; parent[v] <- nil
  end for
  DFS-Visit(s)

G is the given graph and s is the starting node.

DFS-Visit(u)
  color[u] <- gray
  for all v in Ajd[u] do
    if color[v] = gray then
       return true // found cycle
    if color[v] = white AND DFS-Visit(v) then
       return true // found cycle rooted in v
  end for
  color[u] <- black
  return false // no cycle found

Ajd[u] is the list of u's neighbours. So by processing the children of u we might discover a node that is marked gray. If so u and v are connected with a back edge and we found a cycle.

Now I want to extend this algorithm to output the found cycle. Any ideas on how to do that? I thought about using a stack and simply push all u's in DFS-Visit onto the stack. When true is returned I can output the cycle by taking the nodes from the stack. What do you think?

Using a stack won't solve my problem, because the stack will contain nodes that are not part of the cycle.

I have another idea. When we found a cycle we know v=u. To print the cycle we have to go back using the parent list until we reach u:

DFS-Visit(u)

  color[u] <- gray
  foundCycle <- false
  vv <- nil

  for all v in Ajd[u] do
    if color[v] = gray then
       vv <- v
       foundCycle <- true // found cycle
       break
    if color[v] = white then
       parent[v] <- u
       DFS-Visit(v)
  end for
  color[u] <- black

  if foundCylce then
      printCycle(vv, u)

printCycle(v,u)
  if v=u then
     print v
  else
     print v
     printCycle(parent[v], u)


texts:
Let $M$ be a DFA.

I would like to prove that $L(M)$ is infinite if and only if there exists a string $w \in L$ such that $|Q| \leq |w| \leq 2 \cdot |Q| $.

My idea was to use the fact that the shortest string in $L(M)$ is of size at most $|Q|$, but I am not sure precisely how I should use this. Or is there a different approach?

Thanks!


texts: Which tools or softwares are mostly used for the purpose of modeling a computer network?


texts:
With the hill-climbing search algorithm, I do not quite understand how the algorithm can get stuck at "plateaus/ridges." Moving one step back, what exactly denotes a "maximum" or "minimum" in a problem? For instance, in the 8-queens problem, it is said that it hits a local minima 86% of the time. Can someone please elaborate more on how and what denotes maximas and minimas and given this, how the algorithm can get stuck at a plateau.

What I know so far is the following:

Expand the current state, find the best neighbor, and that becomes the new current state.
No looking beyond one step from where you are, no memory


texts: How a Symbolic Evaluator Generates Test Input for this Example

texts:
Say we have some complicated function that determines if a string matches an XSS attack string, and throws an error or does something else in that case.

function somethingWithXSSVulnerability(x) {
  var regex = /<script(.*)>(.*)<\/script>/
  if (x.match(regex)) {
    throw new Error('XSS')
  } else {
    return x
  }
}

In trying to understand symbolic evaluation in regards to test generation, I am wondering how it would generate a test for this case. How it would generate an x such that it matched the regex. It could be a lot more complicated than a regex, a grammar for example. The test case generating the error would be something like:

// yes case
somethingWithXSSVulnerability('<script>alert("foo")</script>')
// no case
somethingWithXSSVulnerability('anything else even <script> w/o closing tags')

To really test it, it might need to generate an alert or try setting a cookie or something, so there it is becoming even more complicated.

But I am trying to get a sense of how the symbolic evaluator generates a test for this case. How it determines the value of the input to the function. It seems like it would have to understand the structure of the regex, then reverse-engineer an input to match it. Wondering if that is so.


texts: Is there a regular grammar for the language $\{ w : |w|_0 = |w|_1 \}$?

texts: I need to prove whether the language $ L = \{w \in \{0,1\}^* \mid |w|_0 = |w|_1 \}$ can be written as a regular grammar. Obviously it can, but how do I prove it?


texts: Clarification with Kuhn-Munkres/Hungarian Algorithm

texts:
I have been attempting to get my mind around the Kuhn-Munkres/Hungarian Algorithm. I have been using the following statement of the algorithm which I found here.

Based on my readings on the algorithm, my understanding is that the improvement of the feasible vertex labeling in step 2. is supposed to be such that $G_l \subset G_l'$.

The part I'm getting stuck on is that it seems to me that it is possible for there to be an edge $xy$ in $G_l$ with $y \in T$ but $x \not \in S$ resulting in the fact that
$$
l'(x) + l'(y) = l(x) + (l(y) + \alpha_l) \not = w(xy)
$$
and so $ xy \not \in G_l'$ and $G_l \not \subset G_l'$.

Can anyone point out where I'm going wrong?


texts: Edges in and out of cycles and their relation to connectivity of the graph

texts:
We know that if an edge is a part of a cycle in an undirected connected graph $G$, then if we remove that edge the graph is still connected.

Is the opposite true? If an edge is not a part of a cycle in a connected graph $G$, and we remove that edge, then the graph we get is disconnected?

P.S.: I think that it is true, and the direction for a proof is to look at one vertex it connects, and the edges that connect the vertices with it as on component, and the other end as another component, and showing that if we cut out that edge, we get two components, such that the graph is not connected. What do you think?


texts: Tight condition making unit-disk-graphs planar

texts:
Here's a nice property about unit-disk-graphs :

Suppose $V\subseteq\mathbb{R}^2$ is a finite set of points in the plane. Build the graph $G_V=(V,E)$ such that $(v,v')\in E$  iff  $d(v,v')\le2$, where $d$ denotes the euclidian distance. $G_V$ is the unit-disk-graph associated to $V$.
Unit-disk-graphs and planar graphs are two distincts classes of graphs but the following statement presents a suffisent condition for a unit-disk-graph to be planar.

If for all $v,v'\in V$ we have $d(v,v')>\sqrt{2}$, then $G_V$ is planar.

$\bullet$ My question is : i.e. Is this value tight ?
Is it possible to find a set $V\subseteq\mathbb{R}^2$ such that $\forall v,v'\in V, d(v,v')\ge \sqrt{2}$ and $G_V$ is not planar ? And if the answer is positive, what is the smallest counter-example ?


texts: We need to convert wireframe representations of 3D objects into a representation consisting of 6 orthogonal views each containing nested (non intersecting) closed contours, each having a Z (depth/height) value. We are only concerned with 3D shapes compatible with the target representation. Can someone at least point us to any related existing algorithms?


texts: Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages

texts:
So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\text{shrink}_a(L) = \{\text{shrink}_a(w)\mid w\in L\}$ and where $\text{shrink}_a(w)$ is the string formed from $w$ by replacing every maximal substring of two or more $a$'s by a single a. For example, $\text{shrink}_a(baaab) = bab$.

So I was browsing around for other examples to study, and I came across the following proof for the prefix operation: Proving that recursively enumerable languages are closed against taking prefixes (the proof given by the user Wu Yin). I thought that this was a very cool way of proving something like this, instead of just directly building an alternate TM. I'm curious to know, can anyone come up with a proof that is of a similar style and flavor to the one pointed above? I would be very curious to see a similar bijective proof regarding countable/uncountable sets!!

This has reminded me that there can be many ways to prove something, so I wanted to see what kind of flavor other people's proofs might have to this sample problem. I find that too often, students (and myself included) get caught up in a single procedure for finding solutions to a particular type of problem and neglect to see other ways of showing the same result.


texts: Master Theorem and rounding up to the nearest integer

texts:
For the master theorem for recurrences of the form

$$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)\,,$$

what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/b$? My guess is that this would only allow splits that are natural numbers, and obviously you can't split into a non-integer number, but I can't see anything beyond that.


texts: The operator $A(L)= \{w \mid ww \in L\}$

texts:
Consider the operator $A(L)= \{w \mid ww \in L\}$. Apparently, the class of context free languages is not closed against $A$. Still, after a lot of thinking, I can't find any CFL for which $A(L)$ wouldn't be CFL.

Does anyone have an idea for such a language?


texts: How to do last step of Krom's algorithm for solving 2SAT problems

texts:
I was making a program for solving 2 SAT problems, using Krom's algorithm. I did not found a lot of information searching in Google, so I used Wikipedia's description of Krom's algorithm to implement it but I'm stuck in the last step.

If I understand it well, the algorithm could be resumed in this:

1) You have to reduce your original 2 CNF boolean formula using Krom's inference rule as much as you can:

(a or b) and (¬a or c) => (b or c)

2) While preserving consistency, for each variable in the original formula, you must add only one of these special clauses: (x or x) and (¬x or ¬x).

(For Krom, a formula is consistent if there aren't both of these special clauses at the same time in the formula)

3) You assign to each variable TRUE or FALSE depending on which of these special clauses has been added to the formula. If the variable x has the special clause (x or x) then we assign TRUE to x; and if the variable y has the special clause (¬y or ¬y) then we assign FALSE to y.

4) This is the step where I am stuck.

My problem is that I don't know what to do once I have made the assignments to the variables. And the last paragraph of the Wikipedia describing the algorithm doesn't explain it clearly. Do I have to check satisfiability on this formula or also in the original formula as well?

Furthermore, for example:

I have this formula:(a or b)

Then I add for each variable its special clause (as the algorithm doesn't specify which of them you should pick) like this (a or b) and (¬a or ¬a) and (¬b or ¬b)

So I assign to the variables a and b the value FALSE, but then the first clause (the clause on the original formula) becomes false. What do I do in that case? Could somebody explain me the last step of Krom's Algorithm for solving 2SAT problems?


texts: Why do Computers use Hex Number System at assembly language?

texts: Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? Why it looked so beneficial to them?


texts: Optimal Loading of a Hopping Airplane Minimum Cost Flow Problem

texts: I have a Problem with an Optimal Loading a Hopping Airplane example . This is the Part of Minimum Cost Flow Problem.. .. I dont understand a Picture at all. I should to make one example with numbers and i need to show, how could i send flow along the Airline with bigger Revenue und possible smallest cost... Thank you for your Attending..


texts: Which hazards are solved by instruction reordering?

texts:
I am not clear on whether it's data and control hazards, or control hazards only. Also, the "solved" word confuses me - technically, instruction reordering is used to solve dependences and thus prevent hazards from happening in the first place. Once they do happen, though, it's stalls and forwarding. Would that make the answer "None"?

Is my thinking wrong?