texts: Is a Knapsack Problem with only Color Constraints NP-Complete?

texts:
I have a knapsack problem that has been frustrating me for weeks, in which we consider a set of n items, described by their integer value, and being of one of C colors.

There exists a constraint on the number of different colors of objects in the knapsack (but no "weight" constraint), and the goal is to maximize the value of the knapsack.

It's basically the same setting as in this model http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.9533&rep=rep1&type=pdf except that there is only one knapsack and the items are "weightless".

Is this problem hard, easy, yet to be classified? I would really appreciate any pointers. Please and thank you in advance.


texts: Binary decision diagram for a six-figure Boolean function

texts:
Let $p$ be the six-figure Boolean function with the following definition:

  $p(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5})=\begin{cases}
  true & \text{if } x_{0}=x_{5} \text{ and } x_{1}=x_{4} \text{ and } x_{2}=x_{3}, \\
  false & \text{else.}
\end{cases}$

  This function obviously yields $true$ iff $x_{0}x_{1}x_{2}x_{3}x_{4}x_{5}$ is a palindrome. Provide a BDD for $p$ relative to a variable ordering of your choice.

My problems begin when I try to define an appropriate variable ordering, so I am only able to guess it: $x_{0}=x_{5} < x_{1}=x_{4} < x_{2}=x_{3}$.
I'm actually pretty lost with this exercise and any help is much appreciated (sorry for not being able to provide a better own approach).


texts: Is there a physical analogy to the Turing Machine?

texts:
Recently in my CS class I've been introduced to the Turing Machine.

After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine.

I was completely unaware of the existence of computer tapes or how tapes and machines interacted until today. I still can't see why a machine would read tapes but a scanner is perhaps a closer conception to the Turing machine where paper is considered a tape and whatever goes inside of a scanner is whatever a Turing machine would do.

But in any case, isn't the idea of a Turing machine quite archaic? We have so many physical (rather than hypothetical) devices in our office or living room that seems to do what the Turing Machine does.

Can someone provide a better example drawing from reality so that the essential functionalities of this hypothetical conception is captured?


texts: How should I design a hash table where all the keys are permutations?

texts:
I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys.

Given that I know how all the keys look up front, it seems I that there should be an optimal hashing function, and an optimal size of the table to store the values in.

Is this true? If so, how can I create the perfect hashing function? And also, how can I determine the optimal size for the hash table?

update: I'm looking to store all of the possible permutations, where each will be stored only once, which means the table should in the end contain exactly all 362 880 keys (since I have a hard limit on my algorithm for which I need to optimize my worst case scenario.)


texts:
I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063:

  ...and therefore the running time is $\Omega(m!)=\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$...

How can the second inequality be possible since $n!$ is super-exponential and it grows always faster than $2^n$? Perhaps i'm making a too stupid mistake?


texts: Extracting features for texture classification

texts:
I'm a beginner in the field of pattern recognition and computer vision. I'm working on a project right now to classify t-shirt patterns into three categories i.e. solids, stripes and checks. I have close up training images of the t-shirt images. A sample shirt image looks like this

I have looked at a bank of gabor filter features, but they are computationally expensive. It would of great help if someone could point me out in the general direction for working forward. Any help is appreciated.

EDIT - I found the solution in D.W.'s answer below, though my solution is not very good. I'm classifying solid patterns by counting the number of line segments in the image. If they fall below a certain number, I'm classifying them as solid. If not, I further classify them into stripes or checkered using HoG features and a linear SVM. The accuracy achieved was around 91%. It was a little low due to some misclassified samples in the training set.


texts: Show that the Kleene star of any unary language is regular

texts:
An exercise asks me to show that the Kleene star of any unary language $L$ is regular. $E$ is the alphabet, $E = \{ 1 \}$

Here's my reasoning :

$L$ is regular $\implies$ $L^*$ is regular (closure property)
$L$ is not regular

$L$ contains the word of length 1 $\implies$ $L^* = E^* \cup \{\epsilon\}$ $\implies$ $L^*$ is regular (since $E^*$ is regular, and the union of two regular languages is regular)
$L$ does not contain the word of length 1 -> ... ?

This is where I'm stuck. I don't know what to do if $L$ does not contain the word of length 1. I do not think that there exists a relation between $L^*$ and $(L \text{ complement})^*$.

Does anyone have any idea to continue this proof ? Thank you.


texts: Relaxing the stack in a push down automata

texts:
Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol can succeed (i.e. "getting rid" of the stack), we get a non-deterministic finite automata.

If we convert two such PDAs, whose languages recognized are the same, and assuming all states are reachable, to NFAs in this fashion, are the languages recognized by the NFAs still the same?

Here's a simple example.  Consider the language $\{a^n b^n : n \in \mathbb{N}\}$.  Here's one simple PDA for it.  The PDA has two states, $q_0,q_1$.  When it is in state $q_0$ and it reads the symbol $a$ on the input tape, it pushes $A$ on the stack and remains in state $q_0$.  When it reads the symbol $b$ on the input table and the stack is non-empty, it pops whatever is on the stack and moves to state $q_1$.  The PDA accepts if the stack is empty at the end of the input string.  If we convert this PDA to a NFA, we get a NFA with two states $q_0,q_1$ and transitions $q_0 \stackrel{a}{\to} q_0$, $q_0 \stackrel{b}{\to} q_1$, $q_1 \stackrel{b}{\to} q_1$.  This NFA accepts the language $a^* b^*$.  There are other ways to build a PDA for the language $\{a^n b^n : n \in \mathbb{N}\}$; if we apply the same conversion to them, does the corresponding NFA always accept the language $a^* b^*$?


texts: is-child-of, is-instance-of as intensional and extensional inheritance relation - is object-oriented modelling an great oversimplification?

texts:
I am trying to build knowledge base in OpenCog cognitive architecture (http://wiki.opencog.org/w/The_Open_Cognition_Project) and I see that OpenCog lacks usual means to express notions of object-oriented modelling paradigm.

E.g. OpenCog has no classes, but it has concepts (concrete concept can be class or instance, or both class and instance of some other class). And inheritance among classes can be expressed as intensional inheritance link relationship among concepts.

E.g. OpenCog does not divide concepts in classes and instances, in OpenCog the notion A is instance of class C one express via extensional inheritance link relationship among concepts A and C.

One can read more about it in http://wiki.opencog.org/w/InheritanceLink. To make things more interesting (or confusing), the is-child-of notion can be expressed as set-membership relationship, but is-instance-of notion can be defined via relation among sets of attributes.

My questions are -

Is object-oriented modelling and notions and oversimplification that can not be used in more advanced knowledge bases which try to express commonsense and advanced knowledge?
Are OpenCog notions (as mentioned in my question) of intensional and extensional inheritance - are those notions used in other projects/endeavours and are there other non-OpenCog research that uses those notions?
What modelling approach one should adopt in building sophisticated knowledge bases for Artificial General Intelligence applications? Is Object-Oriented modelling paradigm too Procrustean and narrow and applicable only for software coding?
How sound is to preceive classes as the sets? In my experience as a programmer I don't perceive classes as the sets, because classes can be independent from its member, classes can have class level function, classes are used for the creation of class instances, so - class is not merely and set of instances, class is something more.


texts:
I've been reading around the area of complexity and arithmetic operations using logic gates; one thing that is confusing me is that
\begin{equation}
\Theta (n^{2})
\end{equation}
is quoted as being the complexity for multiplication for iterative adition. But addition of a number requires \begin{equation}
log_2(n)
\end{equation}
operations, 1 for each bit or 8 times that for each nand gate involved in doing this. So it strikes me as obvious that adding that number n times will have a complexity of
\begin{equation}
n \log_2(n)
\end{equation}
Which is definitely less than
\begin{equation}
\Theta (n^{2})
\end{equation}
So where is this additional factor of
\begin{equation}
\frac{n}{\log_2(n)}
\end{equation}
coming from?


texts: Turing-unrecognizable language - what TM does?

texts:
I have a problem giving "intuitive" explanation to turing-unrecognizable languages.

We can prove that, say, ${\overline{A_{TM}}}$ is not turing-recognizable, because that would make ${{A_{TM}}}$ decidable, but what would the $TM$ do if it doesn't accept, reject of loop?


texts:
I am reading William Stallings Computer Organization & Architecture to understand about control unit & micro-operations.

Stallings explain that interrupt cycle requires 3 time units to complete :

t1 : MBR <- (PC)
t2 : MAR <- Save_Address
     PC <- Routine_Address
t3 : Memory <- (MBR)

t1 : Save the current PC value to MBR

t2 : Save_Address provides the memory location where the value of PC has to be stored. It is saved in MAR.

Routine_Address gives the address for Interrupt Service Routine

t3 : The MBR (which has old value of PC) is stored to memory location (whose address provided by MAR)

But this is how I am thinking, the above operations can be completed in only 2 time units.

t1 : MBR <- (PC)
     MAR <- Save_Address
t2 : PC <- Routine_Address
     Memory <- (MBR)

I checked twice & I find no dependency among micro-operations performed in time unit t1 & t2.

So, is my approach correct ?


texts:
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.
If we assume on the contrary, then there exists a pumping length $p$. In that case, the word looks like $xyz$ where $|xy| \leq p$. If $y$ does not have the same number of $a$'s and $b$'s then $xy^iz$ for $i>1$ will give us a contradiction. Otherwise $y$ has the same number of $a$'s and $b$'s. This does not lead me to anywhere. I tried creating cases where this would fail -- seems like there isn't any.
This link answers it, but I do not understand what they mean by "a regular language is one that uses finite memory". I have encountered similar reasoning before, I have not been able to figure it out.
This answer seems to check if a number satisfies the criteria using regex. Is that a different form of regex?


texts: set cover where only certain special subsets are allowed

texts:
I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate enough for my needs.

Specifically I have a fixed, finite, list of special sets and I am trying to create a function which when given a set returns the smallest list of special sets which cover that given set, and that list should contain no sets which contain elements not in that given set. The fixed list seems like it should make the problem easier to solve than set cover, but I'm not sure how the additional requirement of no extra elements affects the difficulty. My sets also have a known maximum size which should also make this easier to solve.

A toy version of the problem is as follows:

  Let $U$ be the set $\{a,b,c,d,e,f,g,h\}$. All the sets we mention from
  here on will be subsets of this set.

  Let $S$ be a list of special sets. For this version of the problem we
  can use the following list:

  $$ S = [\{a,b,c,d,e,f,g,h\}, \{a,b,c,d\}, \{e,f,g,h\}, \{a,e\}, \{b,f\}, \{c,g\}, \{d,h\}, \{a,b\}, \{b,c\}, \{c,d\}, \{d,e\}, \{e,f\}, \{f,g\},\{g,h\}, \{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{f\}, \{g\}, \{h\}]$$

  For a given set $G$ what is the smallest list of sets which are part
  of $S$ which cover $G$, (that is where the union of the sets in the
  list is $G$).

For the above toy problem, the greedy approximation I've implemented, if presented with a set like $\{b, c, g, h\}$, produces $[\{c, g\}, \{b\}, \{h\}]$ instead of the smaller list $[\{b, c\}, \{g, h\}]$.

Has this sort of problem been well studied? Is there a known non-approximate algorithm given the additional constraints, that would be better than naive dynamic programming? A well-known name for the version of set cover where extra elements are not allowed would also be useful.


texts:
For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{i+1}) -max\{w(v_i,v_{i+1})) | 1\leq i \leq k$}

The complexity needs to be $O(V+E\log V)$.
Obviously i thought about dijkstra, define a new weight function s.t shortest path according to that weight function is the shortest path we looking for, and that just run dijkstra algorithm on the graph using the new weight function, however I cant think about such function, does anyone have an idea?
Thanks in advance.


texts: Knapsack problem with the restriction on the number of items

texts: Suppose $X$ is a set of integers. I am interested in the algorithm which computes the number of ways to represent an integer $W$ as a sum of exactly $k$ elements from $X$. Is it possible to modify the standard knapsack algorithm so that it does the job? Thank you for your suggestions!


texts: Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

texts:
Assume for the regular knapsack problem we have additional information - maximal weight of every item - lets denote it as P. Using this information, I want to solve the problem using dynamic programming in $O(n^2P)$.
Anyone have an idea how to solve it?


texts: Understanding the correctness of the Euler Tour Technique

texts:
I can't prove the correctness of the following algorithm by R. E. Tarjan amd U. Vishkin, as described on wikipedia:

  Given an undirected tree presented as a set of edges, the Euler tour
  representation (ETR) can be constructed in parallel as follows:

  We construct a symmetric list of directed edges:

  For each undirected edge $\{u,v\}$ in the tree, insert $(u,v)$ and $(v,u)$ in the edge list.
  Sort the edge list lexicographically. (Here we assume that the nodes of the tree are ordered, and that the root is the first element in
  this order.)
  Construct adjacency lists for each node (called ''next'') and a map from nodes to the first entries of the adjacency lists (called
  ''first''):
  For each edge $(u,v)$ in the list, do in parallel:

  If the previous edge $(x,y)$ has $x \neq u$, i.e. starts from a
  different node, set $first(u)=(u,v)$
  Else if $x \neq u$, i.e. starts from the same node, set
  $next(x,y) = (u,v)$

  Construct an edge list (called $succ$) in Euler tour order by setting
  pointers $succ(u,v)$ for all edges $(u,v)$ in parallel according to
  the following rule:

  $ \mathrm{succ}(u,v)=\begin{cases}
                  \mathrm{next}(v,u) & \mathrm{next}(v,u)\neq \mathrm{nil} \\
                  \mathrm{first}(v)&\text{otherwise}.
                 \end{cases}$

Why the edge list constructed in the last step is an Euler tour? What theorem or lemma gurantees that every single edge is visited?


texts: Synchronous model: is taking steps simultaneously equivalent to having fixed upper bounds for communication/processing delays?

texts:
I've just started reading about theory of distributed systems and am a bit confused. There seem to be two ways of defining a synchronous distributed system and I'm not sure whether they are equivalent.
Lynch, in her book Distributed Algorithms (p. 5) writes

The synchronous model: This is the simplest model to describe, to program, and to reason about. We assume that components take steps simultaneously, that is, that execution proceeds in synchronous rounds.

Several other sources, in contrast, define the synchronous model in terms of known upper bounds for computation and communication delays. For instance, Cachin et al. in their book Introduction to Reliable and Secure Distributed Programming (pp. 45-46) write

[...] a synchronous system comes down to assuming the following properties:
Synchronous computation. There is a known upper bound on processing delays. That is, the time taken by any process to execute a step is always less than this bound. [...]
Synchronous communication. There is a known upper bound on message transmission delays. That is, the time period between the instant at which a message is sent and the instant at which the message is delivered by the destination process is smaller than this bound.

Even Lynch herself, in a paper she cowrote with Dwork and Stockmeyer (Consensus in the Presence of Partial Synchrony) also uses a definition similar to the one by Cachin et al.:

[...] it might be assumed that there is a fixed upper bound $\Delta$ on the time for messages to be delivered (communication is synchronous) and a fixed upper bound $\Phi$ on the rate at which one processor’s clock can run faster than another’s (processors are synchronous), and that these bounds are known a priori and can be "built into" the protocol.

Are these synchronous models equivalent? For instance, is an impossibility result in one also an impossibility result in the other, and vice versa? And is the minimum number of nodes necessary to tolerate a given failure (e.g., byzantine or crash) the same, whether we define synchronous to mean that processes proceed in synchronized steps or whether we define it as meaning that transmission and computation delays are upper bounded and known?


texts:
I have difficulties understanding the definition of the class Max-SNP (optimization variant of strict NP), thus I have to following basic question:

If a problem is known to be Max-SNP hard, does this imply NP-hardness of the problem?


texts:
Setup: Suppose you have a dog running around in a fenced yard (2D). Every x seconds, you mark down the coordinates of the dog. This dog is a puppy - easily distracted, full of energy, and very speedy :) Expect quick, jagged motions, running in circles, and periods where he needs to catch his breath :)

Problem: At any point, you would like to predict where the dog is going to be kx seconds into the future (k being an integer).

I would like to know what types of techniques may be most suitable for solving this? My knowledge breadth in this subject matter is very limited. I'd like to identify a few candidates that I could then deep-dive into

My original thought was to use Langrange-form polynomials to interpolate the latest n points, then extrapolate. The dog's path is continuous, and smooth, so a polynomial approximation seems reasonable; however, the danger lies in forcing the polynomial through the available data. It seems like we want the polynomial that best approximates the data, rather then the lowest degree polynomial that exactly fits the available data - especially if x is substantial.
Ideally, since every prediction can be measured against what actually occurred, there  should be some method of learning on-the-fly. However, since the data isn't static, I don't know how I would apply techniques of somewhat aware of like SVMs or linear regression.

I apologize if I didn't use terms correctly, this is not my area of expertise.


texts: determining timeouts / retry attempts in distributed systems

texts:
Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution of response time?

For example, suppose I have a client program which requests a web page from some server, and I know roughly the probability distribution of its response time, e.g. 95% of the time I'll get a response with a gamma distribution, and 5% of the time my request will get lost and a response never sent. So maybe 80% of the time I'll get a response within 100 milliseconds, and 90% of the time I'll get a response within 500 milliseconds.

On one hand, I could set a timeout of 500 milliseconds and retry with another request after then. Or I could set a timeout of 100 milliseconds. A longer timeout means I have more chance of success, but I have to wait longer. A shorter timeout means I can reduce my wait time potentially, at the cost of increasing the chance of failure (I give up too early; the server will respond). Or I could just send two identical requests up front and take whichever response arrives first -- this seems like it might be the optimal strategy, but something seems wrong here. (why then wouldn't I send 100 identical requests? I guess I'm not modeling the fact that lots of additional requests would clog the server queue.)

Please help; I know this is a fairly general question, but I have no idea where to look for more information of this type. I never took any classes on distributed systems in college + am trying to improve responsiveness of a client program.


texts:
Is the language $L = \{a^nb^m : n = 2^m\}$ context-free?

Assume L is a context-free language. Then $\ \exists p\in \mathbb{Z}^{+}:\forall s\in L\left | s \right |\geq p. s = uvxyz,\left | vy \right |\geq 1,\left | vxy \right |\leq p. s_i = uv^{i}xy^{i}z\in L\forall i\geq 0\ $.

Let s = $\ a^{2^p}b^{p}\ $

Pumping i times will give a string of length $\ 2^{p} + (i - 1)*j\ $ a's and $\ p + (i - 1)*k\ $ b's where $\ 1 \leq j + k \leq p\ $

Case 1: $\ j \neq 0\ $ $\ k \neq 0\ $

??

Case 2: $\ j = 0\ $ $\ k \neq 0\ $

??

Case 3: $\ j \neq 0\ $ $\ k = 0\ $

??

It can be concluded from this that L is not a context-free language.


texts: choosing right neural network architecture and input features

texts:
As a short example suppose we have a  kind of pollution sensor  and a jet fan in a tunnel.

Jet fan turn on/off according to the automatic scenario based on pollution sensor value.

Pollution itself is based on some parameters like number of cars in the tunnel, direction of wind,speed of wind etc.

And number of cars can be predicted according to date and time (month,day,hour,...) and some other parameters.

.

I want to generate an online simulation of this system, so that for the current state of the system can “predict”  value of pollution  sensor in the short-term furture (ex 1 hour).

What is the best neural network architecture for this and what will be good input features?

What I thought about input features is

Sensed value in the previous time period

    X1:Pollution value

    X2:wind speed

Actuator status :

    X3:jetfan status (on/off)

date and time  :

    X4:season
    X5:month
    X6:day in week


texts: How many strings for CLOSEST STRING lower bound to apply

texts:
In the CLOSEST STRING problem, one is given (bit-)strings $s_1, \dots, s_t$, each of length $L$ and an integer $d$. The question to be answered is whether there exists a string $s$ that has hamming distance to each $s_i$ that is at most $d$.
In this paper, the authors show that (assuming ETH) the problem cannot be solved in time sub-exponential in $d$, but no requirements on $t$ seem to be placed.
However, for $t = 2$, the problem seems to be easy.
Solution for t=2:
Let $s_1$ and $s_2$ be the two input strings. Let $k$ be the hamming distance between $s_1$ and $s_2$. If $k/2 \leq d$, then output "yes", otherwise output "no".
Question:
Which requirements on $t$ need to be placed for the lower bound in the paper to hold?


texts: Is the language Turing machine-Input pairs for which the computation loops recognizable?

texts:
I'm wondering if the following language is $L \in \mathsf{R}$, $L \in \mathsf{RE} \setminus \mathsf{R}$, $\overline{L} \in \mathsf{RE} \setminus \mathsf{R}$:
$$L=\{<M,w> \,\mid M \mbox{ Loops on input } w\}$$
to be clear: We say that a TM loops on a string if during its run on the string it repeats the same sequence of configurations. Note that every TM that loops on a string is a TM that doesn’t halt on the string but not every TM that doesn’t halt on a string is a TM that loops on the string.
I'm leaning towards $\overline{L} \in \mathsf{RE} \setminus \mathsf{R}$ and wondering if it's possible to map $\overline{L}$ to HALT?


texts:
I'm working through "Types and Programming Languages" by Benjamin Pierce and I don't quite understand the notation. Particularly on Page 106, (chapter 9 Simply Typed Lambda-Calculus) there is a lemma (9.3.7):

$$
\text{If } \Gamma \vdash t:T \text{ and } x \notin dom(\Gamma) \text{, then } \Gamma, x:S \vdash t:T.
$$

I understand the idea roughly but I can't quite read this statement out in english. How do I translate the turnstile symbol (\vdash in tex) in this context? In the book I've seen $$ \vdash t:T $$ translated as t is a closed, well-typed term but I don't quite see how to apply that in this context. Looking around apparently the turnstile symbol is also used to mean provable.

Gamma is the typing context and provides binding of variables and their types. t:T means the term t is has the type T. The function dom(gamma) is the set of variables bound by Gamma.

So my best guess for translating this is as follows:

If the term t having type T is a closed, well-typed term under the typing context gamma and x is not in the set of bound variables of gamma, then the term t having type T is still a closed, well-typed term in the typing context gamma after binding the term x having type S.

Is this roughly right? It makes sense but I still feel a bit shaky on the translation. Anyone have any other suggestions, corrections, or comments?
Thanks


texts: Given regular expression construct regex for the complement language

texts:
Disclamer: this is my uni assignment, which is rated comparatively low, thus I assume that the answer should be simple.  Hints are appreciated (as opposed to direct answers).

  Write an algorithm which accepts a regular expression $r$ and produces a language $\overline{L[r]}$.

I think it is reasonable to assume that all operations I need to consider are just the concatenation, union and Kleene star.  For simplicity, I assumed the alphabet to be $\{a,b,c\}$.  I also think that I can invert individual operations as follows:

$a^* \to (a^*(b+c))^+$.
$(a+b) \to (\epsilon+(c(a+b+c)^*))$.
$ab \to \epsilon+((aa+b+c)(a+b+c)^*)$.

But attempting to combine these operations produces wrong results, for example:

$$
a^*b^* \to \\
(a^*(b+c))^+(b^*(a+c))^+ \to \\
(\epsilon+((a^*(b+c))^+(a^*(b+c))^++b+c)(a+b+c)^*)(\epsilon+((b^*(a+c))^++a+c)(a+b+c)^*))
$$

doesn't seem to do what I expect it to because, for example, it will match the empty string on both sides.

Should I perhaps consider transforming the regexp into DFA and "inverting" the DFA instead?


texts: How to define a similarity between two graphs?

texts:
Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G_1 = (V, E_1)$,  $G_2 = (V, E_2)$. $\newcommand\mG{\mathbb G}$(Let's denote the set of all graphs over the vertices $V$ with $\mG$, so $G_1, G_2 \in \mG$).
Now I'd like to measure how similar (up to isomorphism) those graphs are, so ideally we'd have a metric
$$d: \mathbb G \times \mathbb G \to \mathbb R_{\geq 0}.$$
This should satisfy all the usual axioms of a metric

$d(G, H) = 0 \iff G \simeq H$ (Here we consider isomorphy as equality.)
$d(G, H) = d(H, G)$
$d(G, H) + d(H, I) \geq d(G, I)$

Is there a "useful" example of such a metric?
I know this is a little bit vague, but what I mean by that is that it should not be the trivial metric, and somehow relate to what we intuitively think would make sense: For example it would be nice if the distance if you remove one edge is smaller than if you remove two or more edges, or (I'm not sure if it actually makes sense, so it certainly is not necessary) that the distance between the empty graph and the complete graph is maximal.
For the sake of simplicty you can assume that $V$ is finite.


texts:
I need to compute the bottleneck shortest paths from s to all vertices of a graph by modifying the Dijkstra’s algorithm. I found this explanation on Wikipedia(Link to Wikipedia) but I would appreciate if you can elaborate it a bit for me.

  If the edges are sorted by their weights, then a modified version of
  Dijkstra's algorithm can compute the bottlenecks between a designated
  start vertex and every other vertex in the graph, in linear time. The
  key idea behind the speedup over a conventional version of Dijkstra's
  algorithm is that the sequence of bottleneck distances to each vertex,
  in the order that the vertices are considered by this algorithm, is a
  monotonic subsequence of the sorted sequence of edge weights;
  therefore, the priority queue of Dijkstra's algorithm can be replaced
  by an array indexed by the numbers from 1 to m (the number of edges in
  the graph), where array cell i contains the vertices whose bottleneck
  distance is the weight of the edge with position i in the sorted
  order. This method allows the widest path problem to be solved as
  quickly as sorting; for instance, if the edge weights are represented
  as integers, then the time bounds for integer sorting a list of m
  integers would apply also to this problem

So I need to sort my vertex by weight starting from A? I would appreciate if you can explain me the steps in this algorithm.

Thanks


texts: How much faster are out machines (generally) than Arthur C. Clarke's machine in 1953's "The 9 Billion Names of God"?

texts:
In Arthur C. Clarke's short story, "The 9 Billion Names of God", two software/hardware engineers are contracted by a monastery to generate 9 billion string permutations from a 13-character alphabet. The only rules are that no character can occur 4 times in a row and each string must be 9 characters long. They estimate that the amount of processing time is 2,000 hours of computer time. The story was written in 1953.
For fun, using that same algorithm, I want to determine how much faster my current desktop (Mac Pro 3.2 GHz 16-Core Intel Xeon W) is than the fictional machine of ACC's 1953.
Instead of running the whole thing, which would take a while, I generated all the "a" words (those beginning with "a") and timed it. On my desktop, it took 1,358 seconds.
1,358 * 13 chars == 17,654 total seconds ~= 5 hours.
2,000 / 5 == my machine is 400x faster than ACC's 1953 machine. But that doesn't feel right. That's a lot, sure, but I figured it would be more.
Is my math wrong?
Swift

// 13-char alphabet
let letters: [Character] = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "k", "l", "m", "n"]

func shangriLa(_ name: String) -> [String] {
  if name.count == 9 {
    return [name]
  }
  var names = [String]()
  for letter in letters {
    if (name.count <= 2) || canAppendLetter(name, letter: letter) {
      names.append(contentsOf: shangriLa(name + String(letter)))
    }
  }
  return names
}

private func canAppendLetter(_ name: String, letter: Character) -> Bool {
  return name[name.count - 3] != name[name.count - 2] || name[name.count - 2] != name[name.count - 1] || name[name.count - 1] != letter
}

extension String {
  subscript(offset: Int) -> Character {
    self[index(startIndex, offsetBy: offset)]
  }
}

Notes: I chose Swift because I'm a mobile developer with an interest in sci-fi, not a computer scientist or mathematician :)
Another Note: did I put this in the right StackXXX network? Happy to move it if not!


texts: How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?

texts:
Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the number of disk accesses?

Are there known algorithms for this problem? I searched for external matrix multiplication etc. but couldn't find much.


texts: Equivalence of independent set and set packing

texts:
According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent.

The Independent Set search problem is: given a graph $G(V,E)$ and an integer $n$, find $n$ vertices no two of which are adjacent.

The Set Packing search problem is: given a finite collection $C$ of finite sets and an integer $n$, find $n$ sets that are pairwise disjoint.

I think they are equivalent based on the following bidirectional reduction:

→: Given an independent set problem on a graph $G(V,E)$, create a collection of $C$ of sets, where for each vertex $v \in V$ there is a set $S_v \in C$ containing all edges adjacent to $v$. Now, every set packing in $C$ corresponds to a set of vertices no two of which have an edge in common, i.e., this is an independent set in $G$ of the same size.

←: Given a set packing problem on a collection $C$, create a graph $G(V,E)$ where for every set $S \in C$ there is a vertex $v_S \in V$, and there is an edge between $v_{S_1}$ and $v_{S_2}$ iff the sets $S_1$ and $S_2$ intersect. Now, every independent vertex set in $G$ corresponds to a set of sets from $C$ no two of which intersect, i.e., this is a set packing in $C$ of the same size.

My question is: is my reduction correct? If so, are these problem equivalent? Is it possible to use approximation algorithms for one problem on the other problem?


texts: Converting If-else condition to Linear Programming

texts:
I have a constraint in a linear programming formulation with two variables: $X \ge Y$

To which I want to apply the following if-else conditions:

if Y=1:
    X=1
else:
    X=0

Where $X$ and $Y$ are binary.

How can I fit this if-else into linear programming? Do I need to define another variable? It looks as an AND operation, between $X$ and $Y$.


texts: How to conceptually represent attributes (characteristics) of an object in logics?

texts:
I am reading about/working on the knowledge representation using OpenCog framework http://wiki.opencog.org/w/OpenCog_Framework which essentially is special kind of probabilistic logic (s.c. PLN - Probabilistic Logic Networks) that smoothly generalizes crisp logic (by assigning strength and confidence to the crisp truth value).

My question is - how to represent attributes in logic (in OpenCog or in any other logic). E.g. I want to express the statement 'An apple #1 has price 1$' (#1 is Apple; #1.price=1$). How can I do this in any logic?

My current solution is that I need to define 3 entities: apple a1, price p1, 1$_value v1 and enter those entities into whole-part relationships: whole_part_relation(a1, p1), whole_part_relation(p1, v1). Those relations are for instances and apparently similar relations can be formed for classes (concepts) as well. Is my representation of attributes by whole-part-relationships acceptable?

OpenCog has list of all supported types of terms (s.c. Atoms) and their relationships (e.g. Links) http://wiki.opencog.org/w/Category:Atom_Types but one can see that attribute link/relationship is not first class citizen in this logic as it is not in many other logics as well.

So - my question is - how to represent attributes in the logics in which attributes are not first class citizens?

There is need to formalize software development, to mode real world, to create knowledge bases for e.g. robotics and therefore the conceptualization of notion of attribute (characteristic) is important!


texts: k-polynomial time approximation algorithm for set cover (k = max size of subsets)

texts:
Problem Definition: Given a universe set $U = \{1, 2, \dots, n\}$ and a collection of $m$ subsets $S_1, S_2, \dots S_m \subseteq U$, find the minimum collection of subsets that cover $U$.
I am specifically trying to find a $k$ polynomial time approximation algorithm for set cover where $k$ is the largest size of the subsets. In other words, $k = \max_{i=1}^m|S_i|$
I have the following ILP and relaxed LP programs as shown at the end of page 1 and start of page 2 from these lecture notes of Luca Trevisan.
I know that the factor of the polynomial time approximation algorithm depends on the rounding factor necessary in the LP. In the case for weighted set cover, the rounding factor would depend on $m$, the number of subsets.
I have determined a lower bound on the number of subsets based on the defined $k$ to be as follows: $\lceil \frac{n}{k} \rceil \leq m$.
I don't know how to use this (or if this is the correct relationship) to show something along the lines of $A(I) \leq \alpha OPT(I)$ where $A(I)$ is the approximation algorithm solution, $OPT(I)$ is the optimal solution, and $\alpha$ is related to $k$.
How would you go about solving this problem?


texts: Inference rules for deriving invariants in Hoare logic

texts:
The following algorithm is supposed to compare two strings $S_1$ and $S_2$ ("/\" for empty string):

X = S1
Y = S2

E = true
// (1) S1 = S2 <=> X = Y and E = true
while X != /\ and Y != /\ and E == true
  if head(X) == head(Y)
    X = tail(X)
    Y = tail(Y)
  else
    E = false
// (2) S1 = S2 <=> X = /\ and Y = /\ and E = true
if !(X == /\ and Y == /\)
  E = false
  // (3) S1 != S2 and E = false
else // an empty else; just for inserting an assertion (i.e., 3' below) here
  // (3') S1 = S2 <=> E = true
// (4) S1 = S2 <=> E = true
return E

There are five invariants:

(1). $S_1 = S_2 \iff X = Y \land E = true$

(2). $S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true$

(3). $S_1 \neq S_2 \land E = false$

(3'). $S_1 = S_2 \iff E = true$

(4). $S_1 = S_2 \iff E = true$

I can understand these invariants and how they are derived from the previous ones in an intuitive and thus informal way. For example, we can derive (3') from (2) as follows:

  At point (2), we know that $S_1$ equals $S_2$ iff $X = \Lambda \land Y = \Lambda \land E = true$. At point (3'), we further know that $X = \Lambda \land Y = \Lambda$. Thus, at this point, we only need to check whether $E = true$ to decide whether $S_1 = S_2$ holds.

However, the reasoning above cannot be justified by the conventional inference rules of propositional logic by which we would have

$$S_1 = S_2 \iff (X = \Lambda \land Y = \Lambda \land E = true) \land (X = \Lambda \land Y = \Lambda),$$
which is $S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true.$

Problem: What are the inference rules for the derivation from (2) to (3')?

Related Post: Developing invariants for comparing two strings

Edit:
As pointed out by @chi in the comment, it should be
$$\big(S_1 = S_2 \iff (X = \Lambda \land Y = \Lambda \land E = true)\big) \land (X = \Lambda \land Y = \Lambda),$$
which implies (3')
$S_1 = S_2 \iff E = true$ as the answer given by @kne shows.


texts: Create a DFA and a NFA where the word includes (two) consecutive zeroes

texts:
I have chosen an example task to see if I understood DFA and NFA correctly.

So let's say we have that task:

  Given alphabet $\Sigma = \{0,1\}$ and the language $L = \{w \mid w \text{ includes two consecutive zeroes}\}$. Create a DFA and a NFA for the language with as
  less as possible states.

The following description is just a rough one (there are much more attitudes a DFA / NFA has). Please tell me if it's correct anyway because these are the ones I'm not sure about.

For this example, each state of the DFA needs at least two outgoing arrows. So each state needs at least one outgoing arrow $0$ and one outgoing arrow $1$ because we have $\Sigma = \{0,1\}$. We do not really need to care about incoming arrows, there can be any number of incoming arrows.

For the NFA, however, we do not need to care how many outgoing / incoming arrows we use for each state.

So here I made a DFA and a NFA where the words include two consecutive zeroes. Did I do it correctly?


texts: Representing a sentence using propositional logic

texts:
I am confused regarding a propositional logic representation of a sentence.

Please note that this sentence is not realistic:

"A person who is male (M) is smart (S) if he is tall (T), but otherwise is not smart."

Which of the following propositional logic formulas correctly represents the above:

(a) $(M \wedge S) \iff T$

(b) $M \Rightarrow (S \iff T)$

Note that $\Rightarrow$ and $\iff$ represents "only if/implies" and "iff and only if," respectively.

The solution to the problem is (b)

The solution claims that (a) is NOT an option because it asserts, among other things, that all tall people are male, which is not what is asserted. This makes sense to me, I think (not confident, but this is not the main point of this post).

The solution claims that (b) IS a correct representation because it is saying that if a person is male, then they are smart IF AND ONLY IF they are tall. I don't understand that, and based on my current understanding, I don't agree with this because the "IFF" part is saying that if the person is tall, then they are smart, and that is not what the problem statement said. The problem statement only states that a person who is male is smart if he is tall.

So I feel like (b) is not correct, but if you swap out the $\iff$ for $\Rightarrow$ then it becomes correct.

Am I misunderstanding something here?


texts: How does dynamic memory-allocation exactly work?

texts:
I have wondered about ordinary code. Assume we are running this code on any modern System like Unix/Linux/Mac/Windows. This code is C, but it should work with every language which is close to the hardware.

int a = 8;
//printf("%d", (int)&a);

This will show obviously that the system allocated the int dynamically. So there is no static address used. Now we continue by:

a = a+1;

Now, my question follows:

Since the address to "a" is allocated dynamically, we need presumably a pointer which points to a pointer pointing to "a". But how do we store this pointer? We would again need a dynamically allocated address and would, therefore, pass the problem. So, in my mind, we need static addresses the program can use, but how does the process know these addresses?

How does the process store its own allocations, so that after initializing a variable, the process knows what the variable actually is or at least where the variable was allocated?

If this question is not clear enough, please comment below.

Thank you!


texts: What does this mean: "The compile-time and load-time address-binding methods generate identical logical and physical addresses"?

texts:
I read this in my Operating System textbook. Does it mean that the logical addresses generated by compile-time binding scheme are the same as the logical addresses generated by load-time binding? Or does it mean that the logical addresses and the physical addresses generated are the same in both compile-time binding as well as load-time binding?

If the first interpretation is correct, then how is it possible to generate same logical addresses in both compile-time and load-time? AFAIK in compile-time binding, we already have a fixed location in the memory where we'll load our program, so we can generate absolute addresses. But in load-time scheme, we do not know where the program will be loaded in memory. So we put relative addresses. How can absolute and relative addresses be the same?


texts: Does the reduction of places and transitions in Petri nets bring any benefits for model checking?

texts:
I have a process model P and I have transformed it with some rules to Petri net p1 and with some different rules to Petri net p2, i.e., I have two Petri nets which both represent process model P.
p1 has n places and n transitions.
p2 has log n places and log n transitions.
But the number of reachable markings for both Petri nets is the same.
Suppose, n is a very large number, e.g., over a million.
Can Petri net p2 have any advantages over p1 to verify properties (e.g., CTL formulas) of P, using a model checker?


texts: Reducing A(TM) to some decidable problem

texts:
We know that A(TM) is undecidable, what if we reduce A(TM) to A(DFA) which is decidable? How will we prove that A(DFA) is decidable?

I couldn't find an example or theory.

Thanks


texts: Circle Hough Transform. Improvement by knowing edge direction

texts:
I'm studying Hough Transform.
I have fully understood the HT for detecting lines and successfully implemented it. I have more problems with the circle detection HT.
Given a circle, if the radius is known i have to work in a 2d parameter space (each point in the image space becomes a circle in the parameter space; the intersection of all the circles gives me the center of the image circle).
If the radius is not known the parameter space becomes 3d.
What i don't understand is why if i know the direction of the edges, even if my radius is unknown the parameter space lowers to 2d.


texts:
I've question from CLRS that's about constants and functions in asymptotic notations.

$\Theta (g(n)) = \{f(n) :there\;exist\; positive\;constants\;c_1, c_2, n_0\;such\;that$
$0 \leqslant c_1g(n)\leqslant f(n) \leqslant c_2g(n)\; \forall \;n\geqslant n_0 \}.$

Why do we require positive constants here, what is the main reason for this? Secondly, why $g(n)$ and $f(n)$ need to be asymptotically nonnegative functions. What happens when $g(n)$ and $f(n)$  is asymptotically negative and the above constants negative also? Why do we restrict the general case to above?


texts: Trouble with Big-O notation proof by definition

texts:
Let $a,b>0$. Prove
$\left(\log\left(n\right)\right)^{a}=O\left(n^{b}\right)$.

I'm supposed to find an algorithm to find the log(n) largest elements in an array and return them sorted and explain why it's bounded by $O(n^{b})$, but the thing is I'm having trouble proving the above and I'm kind of stuck.. Any tips?


texts: what’s wrong with this quantum key distribution scheme?

texts:
I’m reading about the BB84 quantum key distribution scheme, and I’m surprised that it’s conceptually more complicated than seems necessary to me. What’s wrong with this conceptually simpler scheme?

Alice chooses two random strings $x,y \in \{ 0,1\}^{2n}$
Alice encodes $x$ into qbits, choosing the basis in which to encode the ith qbit according to whether $y_i$ is 0 or 1.
Alice sends the qbits to Bob (Bob himself doesn’t generate any random strings).
Once Bob confirms to Alice (on an insecure but authenticated channel) that he’s received the qbits, Alice sends $y$ to Bob (on an insecure but authenticated channel).
Bob decodes all the qbits using $y$. He then chooses $n$ bits at random from $x$, and sends these $n$ classical bits to Alice (using the insecure channel), together with an encoding of which bits he picked.
Alice confirms whether the first $n$ qbits are indeed the same as the first $n$ bits in $x$. If they are, then they know that Oscar didn’t observe the qbits, and they use the other $n$ bits as the key. If one of them is not the same, they know that Oscar meddled with the process.

Does this work?


texts: How do you compute the time complexity of distributed algorithms?

texts:
How to compute the run-time of distributed algorithms in message passing systems? I was reading across and found it very weird that any computation done in each node is considered to take $\mathcal{O}(1)$ time due to the unreliability in the time it takes to pass messages. Since this approach is not practical at all, I am assuming that I have not understood it properly. Could someone please explain?

By impractical, I mean that I can simply solve any NP-Hard problem in distributed computing trivially in $\mathcal{O}(n^2)$ time by passing information throughout the network and then brute-forcing for the solution in $\mathcal{O}(1)$ time and this obviously seems stupid since in real life message passing shouldn't take more time than a brute-force solution over the search space.


texts: Proof that type does not have decidable equality in Agda

texts:
Can one create such function in Agda ?

ℕ→ℕ-undecidable : ¬ ( (f g :  ℕ → ℕ ) → Dec (f ≡ g))
ℕ→ℕ-undecidable = ?

I am particularly interested in proof using cubical Agda.


texts: How to compare/cluster millions of strings?

texts:
I have around 1,000,000 of strings of variable length (from 200 to 50000) that can contain 5 characters (A, B, C, D, E).

What I actually want is to cluster them together if they are similar enough. By similar enough I mean they have an edit distance < $t$. This $t$ should be dependent on the length of the strings being compared. So for example, if I'm comparing two 200-length strings, $t$ could be 20, while comparing two 1000-length strings $t$ could be $100$

I've been reading a lot of literature lately but can only seem to find approaches that are not actually viable for so many strings, and I'm not much into probabilistic approaches so maybe you can help me out there.

The problem is that comparing them in pairs to cluster them would already be very costly even if the comparison was performed in $O(1)$ time (which is obviously not the case).

I've been reading about using indexes such as BWT and mixing it with things like the pigeonhole principle (Given two strings $P$ and $T$, let $p_1$, $p_2$, ..., $p_{k+1}$ be a partitioning of $P$ into $k+1$ non-overlapping non-empty substrings.  If $P$ occurrs in $T$ with up to $k$ edits, then at least one of $p_1$, $p_2$, ..., $p_{k+1}$ must match exactly) but as I said before, I think it is unfeasible because of the quantity of strings and their length.

Also, some algorithms perform comparison in $O(t \cdot min(m,n))$ where $t$ is the desired edit distance (they will be clustered together if edit distance <= $t$) and $m$ and $n$ are the length of the strings. But this can also be a problem because with large strings, $t$ could also be large.

So, do you know about anything that could help me in my case? Also, algorithms that can be made parallel are very welcome, as I intend to run this in a very large cluster with 400+ cores. Is there any fast probabilistic algorithm that can reduce the amount of comparisons needed for example?


texts:
I am learning Shamos's rotating calipers algorithm for finding the diameter of a convex polygon in his Ph.D. thesis; Page 78.

It reads

  Consult Figure 3.23 and notice that parallel lines of support cannot be made to pass through every pair of points. For example, no lines of support through vertices $D$ and $F$ can be parallel. This means that $DF$ is not a diameter. A pair of points that does admit parallel supporting lines will be called antipodal.

Problem: How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?

My Informal Attempt: See Figure 3.23. Intuitively, by rotating the line $DC$ about $C$ and then $CB$ about $B$, we can get two parallel lines of support passing through $F$ and $B$. However, is $FB$ necessarily longer than $FD$? If so, how to prove it?

  A line $L$ is a line of support of a convex polygon $P$ if it meets the boundary of $P$ and $P$ lies entirely on one side of $L$. (Definition 3.6; Page 69)


texts: Minimum number of bits to represent negative number

texts:
Minimum number of bits required to represent $(+32)_{base10}$ and  $(-32)_{base10}$ in signed two's compliment form?

My attempt:
32 = 0100000 ( 1st zero - sign bit as positive)
So to represent +32 we need 7 bits
-32 = 1100000 (1st bit 1 - sign bit as negative)
So to represent -32 we need 7 bits

But answer is given as 6 bits to store -32 and 7 bits to store +32(positve case i understood, negative in my opinion it should be 7 bits). His reason - one 1 bit enough to represent negative number. I am confused. Please clarify here

Also i have following Questions:-

Can we say number of bits required to represent a negative number is strictly less than( or less than equal to) number of bits required to represent that corresponding positive number?
how can we generalise minimum number of bits required to represent a given positive and negative number say +N and -N in signed magnitude representation, signed 1's complement notation and signed two's compliment notation.


texts: Has Anyone Actually Created a System that Writes Computer Programs from specification?

texts:
Has anyone ever actually written a system (software or detailed explanation on paper with simple examples) that generates computer programs?  I input $Prime(x) \wedge x<10$ and it creates a program that lists the prime numbers less than 10.  $Prime(x)$ is simply defined as
$$1<x \wedge \not\exists A\; s.t. 1<A \wedge A<x \wedge x=A\times B,\mbox{ with }
A,B\in \mathbb{N}$$
Professors say they can but nobody gives actual complete examples.


texts:
What is the trend over time for the size of registers of x86 CPUs? I know that we have today 512-bit registers, but is there a kind of Moore's Law to predict the size of registers in the future?

Thank you very much.


texts: Longest Path A*, Admissible Heuristics, and Optimalness

texts:
Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path.

I have some number of classes, each with a list of unique nodes, with each node having its own value.  Im attempting to determine the best possible combination of a node from each class to determine the combination or path that has the greatest weight.  To do this, I am viewing these classes as a tree, with each Level having the nodes contained within a single class.

Then I search through this tree using A Star, or more specifically, im searching through my tree based on a search stack.  Once a node is explored, its children are inserted in a sorted order based on their weight (plus their ancestors weight) plus the possible future weight (my heuristic).  Then the top of the stack, with the highest value is selected to search next.

To do this I have an overestimating heuristic, that is it never underestimates the the optimal solution.

If I am looking for the highest weight and not the lowest weight, is this heuristic admissible, and thus my algorithm optimal?

PS: A FormalIsh defination of the current algorithm.

Let S = {S1, S2, ... , Sn}

and each Si has a set of items and a NULL, which represents an item not chosen from this set.

Si = {I1, I2, ... , Im, NULL}

Also each item only ever exists in one set, IE Si U Sj = Si + Sj

Each Item, Ii has an associated value, Vi.

The problem is to select a maximum of M offers, one from each set, when summed yield the highest value. I call this selection a Path, Pi.  A path can be complete, meaning it has a selection from all S, or it can be partial where only x offers are contained within it.  Also M

In addition, there exists a function IsCompatable(path) that returns true if a path is compatible. Whether a path is compatible or  is completely arbitrary.  The Max valued path must be compatible.  This is why I can not trivially select the M largest Items from each set.

In addition each set contains a NULL item, so that an item need not be selected from that set.

The Trivial Algorithm would to make a search tree and generate all possible combinations of items in S, with each path to the trees leaves said to be a path.

let G(P) be the current value (the summed value of each item) of the partial path.
Let H(P) be an estimation (heuristic) of the value of the future path.
H(P) = The Y values from Y items from Y Si in S. Each item is the item with the maximum value in the Si where i > len(P). Y = M - the current length of the partial path P.

To Find the path with the greatest value, I keep a sorted Queue of partial paths, sorted on their values + their possible future values, ie G(Pi) + H(Pi).  I Initialize this Queue by adding paths contained in S1.

While the Queue is not empty or a path has not been found:
    p = Pop the path from the top of Q
    if p is Complete:
        A full path has been found
        return p
    find the possible children of p by adding an item to p from the next set.
    for child in Children:
        if IsCompatable(child):
            add child back to Q in sorted order on G(child) + H(child)

There it is, now is my Heuristic admissible?


texts:
This person was asked: "Why is a blockchain implementation different than a distributed consensus system like Raft?"

In part of their answer they replied:

  For one, Raft is not Byzantine fault tolerant, i.e., not designed to account for arbitrary failures. If a participant fails by telling different peers different things, consensus fails. In context of blockchain, this would be equivalent of a malicious consensus participant lying.

Another wrote:

  As others have mentioned, Blockchain has Byzantine Fault Tolerance. Raft and other consensus based systems such as Paxos do not.

My question is: What is the algorithm for Blockchain's Byzantine Fault Tolerance?


texts: Minimum number of edges for $n$ vertex graph to be connected

texts:
I was reading about connectedness of a graph where I came across following points:

  The $n$ vertex graph with the maximal number of edges that is still disconnected is $K_{n-1}$ (complete graph with $n-1$ vertices) with an additional vertex, which has $\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$ edges.
  Adding any additional edge must connect the graph. So the minimum number of edges for $n$ vertex graph to be connected is $\frac{(n-1)(n-2)}{2}+1$.

I am ok with the first point but not with the second point. The minimum number of edges for $n$ vertex graph to be connected should be $n-1$. Then how does that second point makes sense? How does the minimum number of edges for $n$ vertex graph to be connected is $\frac{(n-1)(n-2)}{2}+1$? Was the text trying to say something else? Is $\frac{(n-1)(n-2)}{2}+1$ number characterizes/pertains to some other condition on the graph?


texts: Turing machine that can read and write simultaneously equivalence proof

texts:
How would I go about proving that a TM that can both read and write at the same time is equivalent to a typical TM?

For constructing a read+write TM from normal TMs, my idea is to split the state of writing and reading simultaneously to two separate states (one for writing and one for reading). Not quite sure if this works..

Also, am not sure how to construct a normal TM from read+write TM.

Thank you!


texts: Confused about pumping lemma, What i'm missing?

texts:
When I apply pumping lemma on this language:
${L=\{010^n:n\ge0\}}$ over the alphabet ${\Sigma =\{0,1\}}$ I get that it is non-regular despite the fact that it is regular.

let ${n=4}$, then $w=010000$
$w=xyz$ ,  $ { \mid xy\mid \leq n} $ and $ {\mid y\mid \geq 1}$
$x=0$ , $y=10$ , $z=000$
let $i =2$
$xy^2z = 01010000$ $\not\in L$ so L is non-regular.

so, what I'm missing?


texts: How can one find an element in a Merkle tree?

texts:
How can one find an element in a Merkle tree, as effectively as possible?

Each internal node has a hash value. So I think, first, hash the value to find, and if an internal node has the same value exactly, get its leaf node. But this is correct in 2-depth, not all cases. Because each internal node has a hashed what is concatenation of their child nodes, by the avalanche effect, the concatenated hash value is unexpected.

So I cannot find the value to do hash and compare.


texts: How to model a set of categorical values in the input of a neural network

texts:
One of the inputs to my neural network is a set.  I have a set $S = \{s_0, s_1, ..., s_n\}$ in which all values $s_i$ are constant. An example of such a set could be the set of French wines (Beaujolais, Languedoc-Rousillon, Champagne) or the set of players in a sports event (Player A, Player B, ...). The input to the neural network is a subset $T$ of $S$ (e.g., Player A competing against Player B or Beaujolais wine being served at a table, but nothing else).

Due to the restrictions of my neural network design, all input values must be normalized within the interval $[0,1]$. How would I encode the set $T$ to obtain an input to the neural network?  How do I normalize the values in my set $S$ in a way to respect this condition?

My current idea is to use one boolean input per $s_i$: there would be $\#(S)=n$ boolean inputs, all set to 0 except for the values in $T$, which would be all 1. However, this presents the obvious flaw that for large $n$ there would be a lot of input neurons. Moreover, if one imposes the additional restriction of having at most $m$ elements in $T$, the resulting model would not efficiently correspond to the model (i.e. what if $m+1$ values were set to true)?

Is there a better way of modeling such a situation? Or better, is there a standard way for handling input sets with multiple possibilities?


texts: How to determine how many dots are in a resource in a resource allocation graph?

texts: I understand most concepts regard a resource allocation graph but I see that some resources have more dots (not sure what they are actually referred to) in them than others such as the example below, R1 and R3 have one dot, R2 has two dots and R4 has three dots. I cannot find anything online that explains this so I would just like to know, how would you determine how many dots should be in a resource when drawing the graph?


texts: Why this Nondeterministic Finite accept this string?

texts:
I am reading in my book that this NFA machine accept the string 10100. If we follow the execution, we will find our self in branch with the state final q0.

The only answer for me is that when we are in state q0 after 1010 and 0 is coming we can't move any more so this branch will die even it is in the final state. Am I right?


texts: NP Complete Proof - Polynomial Reduction

texts:
We know that the INDEPENDENT-SET problem is NP Complete i.e $\langle G',k'\rangle$ means graph $G'$ has an Independent set of size $k'$. I am preparing for the finals an a sample question is to prove TRIANGLE-FREE-SET to be NP Complete.
$$TRIANGLE-FREE-SET:=\{\langle G,k\rangle| \text{$G$ has a subset of vertices of size $k$ whose induced subgraph is triangle free}\}$$

To give a polynomial reduction of IS instance $\langle G',k'\rangle$ to TFS, I thought of adding an extra vertex and connecting this extra vertex to all the original vertex of the IS problem instance and then have $k=k'+1$. However, I am stuck trying to prove that if $\langle G,k\rangle \in TFS$ then $\langle G',k'\rangle \in IS$. Any leads appreciated.


texts: Why Bloom filter needs $\frac{m}{n}\ln{2}$ hash functions?

texts:
I show from Wikipedia that the optimal number of hash functions is:

  $k =\frac{m}{n}\ln{2}$.

However it's not obvious for me why, even after reading the Wikipedia article (such as the one on false positives). Anyone interested in explaining with simple words? :)


texts: Proving ambiguity of this Context Free Grammar

texts:
I ran into this exercise problem from Introduction To The Theory Of Computation by Sipser. Given a context free grammar:

$ S \rightarrow SS \ | \ T \\ T \rightarrow aTb \ | \ ab $

I have to show that the grammar is ambiguous. So I have to find at least two leftmost derivation of a string. I have tried a lot but have failed to come up with a counter-example. I think T describes the following grammar:

$ L = {\{a^nb^n} \ | \ n > 0 \} $

But if I take $SS$, it is equivalent to taking $TT$, then it generates the strings like $ a^n b^n a^nb^n $, which is entirely different from L. So how can I come up with a string that has two leftmost derivation in this grammar. Any sort of help would be appreciated!

Below is the picture from the exercise.


texts: Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma

texts:
I have the following alphabet:
$Σ = {0, 1, . . . , 9}$

and the Language $L$ defined as:
$L = \{ abc | a + b = c\} $

where substrings $a$, $b$ and $c$ are interpreted as ordinary integers.

My answer so far:

Assume $L$ is context-free. Then the pumping lemma for context-free languages applies to $L$.

Let $n$ be the the constant given by the pumping lemma.

Let $z=10^n20^n30^n$ clearly $z \in L$ and $|z| \geq n$

By the lemma we know that $z = uvwxy$ with $|vwx| \leq n$ and $ |vx| \geq 1$

There exists possibilities...

My questions:

I can see 8 possibilities where $vwx$ can be within $z$. For example in the beginning including the 1 and overlapping with the initial $0^n$. Another example the initial $0^n$. Is this one way to think in this particular question? How can I pump and show that the result does not belong to $L$?

Thank you for your time.


texts:
Ususally a grid pattern (circles or squares) is used for camera calibration. Features (circles or corners) are detected in a function (e.g. findCirclesGrid in OpenCV) and passed to the a camera calibration  function (e.g. calibrateCamera in OpenCV) together with corresponding object points (object coordinates).

Is it possible to calibrate a camera with circles which are "randomly" spread on a plane (object coordinates known)?
If yes, how does it affect the feature detection, i.e. findCirclesGrid? Is it less accurate?
If yes, how does it affect the calibrateCamera function? Can all parameters such as distortion for example still be computed?


texts: Turing Completeness of System Which Randomly Fails to Complete Calculations

texts: If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python implementation which, upon every variable assignment, with probability $\frac13$ decreased the value by $1$, with probability $\frac13$ increased the value by $1$ and otherwise kept the value constant, would it be Turing complete? This seems to be able to perform all of the calculations which Python is able to perform, just not reliably.


texts: Problem that is only solvable in a given space

texts:
I was wondering if a computational problem exists with the following properties:

It should be solvable only having $K$ bytes of memory, or solvable with $K' < K$ bytes of memory only in exponential time on $K - K'$ (or such an high degree polynomial in $K - K'$ that for any practical purpose the computation is unfeasible).
The input to the problem should not be bigger than $O(\ln(K))$.
The output to the problem should not be bigger than $O(\ln(K))$.
The time complexity of the problem should be less or equal than $O(K \ln (K))$.

I have thought of many possible solutions but could always find a counterexample. Any sub-optimal suggestion or pointer is also very appreciated.


texts: Deciding complexity class of a TM s.t M(0) = accept

texts:
Below is a sample of 2 homework TM where Im not sure what complexity class they fit in. Also have to decide the complexity class of the complement. These 2 in particular confuse me because I got a different answer so I feel I may be missing something:

S = { : M is a TM s.t. M(0) = accept} U = { : M is a TM s.t. M(0)[20000] = accept}

The options are P, NP, coNP, EXP, Decidable, Recognizable, lang (all strings).

S: I read this as 'M checks if the input is 0, if yes accept'. My first instinct is that S is in P as it simply checks the if the input is 0 which is a single operation, so I would say it can be solved in polynomial time. Someone else decided RE for S and lang for S complement respectively, which I just dont understand if correct.

U: I read this same as S, but runs (to a maximum of?) 2000 steps. I'd also place this in P for both U and its complement. Other answer is P as well but I don't see how the addendum of 2000 makes a difference.

Thanks for any clarification.


texts: What machine learning techniques work on ASTs?

texts:
I am interested in experimenting with machine learning on the ASTs of programming langauges (e.g. some Java code). I would like to develop an algorithm that determines if a given AST satisfies some predicate. I have a training set of programs that do and do not satify the predicate.

The machine learning techniques that I am aware of operate on vectors or matricies. Are there techniques that operate on trees?


texts: How does node expansion work in a graph for AI search?

texts:
I want to try and write an example that solves the problem of travelling from one location to another described in the book AI: A modern approach. The problem involves getting from a particular city in Romania called Arad to Bucharest and the problem can be expressed as a graph like in the following image:

If when constructing the graph a Node holds a reference to its parent, the action that was applied to get there and the current state at that node plus the path cost, how would node expansion work?

I am not sure how I can expand Arad to give the three nodes attached because Arad does not hold a reference to its children, instead the children hold a reference to Arad.
** Edit I am now thinking (whilst I am still unsure how a node is expanded) that child nodes are not built until a node is expanded. Is this correct?
I could maintain a mapping between a node and its children as a hashtable or something like this but I don't think this would scale to a larger problem where there the journey were much larger.
Equally I could search all nodes at expansion time and then find which have Arad as their parent if I kept some sort of information about each node such as its number in the graph\tree, or the easiest would be for each node to hold a reference to all its child nodes but this does not match the description of a node and its properties specified in the book.
Can somebody explain how node expansion should work in a graph as I am guessing at how I might do it which might not be right.


texts: this language and acceptance by queue automaton

texts:
I don't know how to prove or show that:
$ L_1 = \{xx|x \in \Sigma^\ast\} $ (that can be accepted by queue automaton)
If it would be possible, show by deterministic queue automaton, if not, by non-deterministic queue automaton.
If it's not that hard (and if I can), please give me a hint.
Thanks in advance.


texts: NP-Hard problems that are not in NP but decidable

texts:
I'm wondering if there is a good example for an easy to understand NP-Hard problem that is not NP-Complete and not undecidable?

For example, the halting problem is NP-Hard, not NP-Complete, but is undecidable.

I believe that this means that it is a problem that a solution for can be verified but not in polynomial time. (Please, correct this statement if this is not the case).


texts: GOTO vs. including line in loop - will it affect efficiency?

texts:
Let's say I have an algorithm something like as follows:

1 eliminate stuff from a list called reactions
2 for each element in reactions:
3    if one thing is computable:
4        compute it
5    else:
6        eliminate element from reactions, GOTO 1

Can I change it too

1 eliminate stuff from a list called reactions
2 while length of reactions is > 0:
3    while thing is computable:
4        for each element in reactions
5            compute it and append it to list called relevant_reactions
6            eliminate element from reactions
7    eliminate element from reactions

without any changes in efficiency? If there are any ways to improve the efficiency please let me know.

For reference, this algorithm is from page 8 of the paper Reachability Problems for Continuous Chemical Reaction Networks. The reason this question is important is because the main result of this paper is showing that the algorithm runs in polynomial time.

The reason the 6th and 7th lines are the same is to eliminate both those elements where the thing is not computable and those where it is computable (those are moved to a new list). I feel like there's a better way to do that part, however, so any advice there would be appreciated.

I should point out that the main reason I am rewriting the algorithm is to remove the GOTO 1. It's hard to implement in Python 3 (my language of choice) and it seems to be generally considered bad practice.

I should also point out what exactly the "thing is computable" is for sake of context/completeness. Basically, that line is computing a vector (that must be $\in \mathbb{Q}^R_{\geq 0}$) that is multiplied by a matrix and when added to another vector should equal another vector. The vector elements are concentrations of chemicals. The matrix contains the net change of various reactions. It would look something like this: (vector that represents current state of the system) + (matrix of net change of every reaction in the list reactions)*(vector we are solving for) = (vector representing current state) and the element in reactions (the one in the iteration of the for loop, also in the vector we are solving for) must be greater than 0. If you found that confusing, no wonder, I did too (especially the last part). The relevant part in the paper is line 3 of Algorithm 1 in section 3. The exact line is

  Compute a vector $F_{\rho}\in\mathbb{Q}^R_{\geq 0}$ such that $\mathbf{c}+\mathbf{M}F_{\rho} = \mathbf{d}$ and $F_{\rho}(\rho) > 0$, if one exists


texts: Stereo images rectification and disparity: which algorithms?

texts:
I'm trying to figure out what are currently the two most efficent algorithms that permit, starting from a Left/Right pair of stereo images created using a traditional camera (so affected by some epipolar lines misalignment), to produce a pair of adjusted images plus their depth information by looking at their disparity.

Actually I've found lots of papers about these two methods, like:

"Computing Rectifying Homographies for Stereo Vision" (Zhang - seems one of the best for rectification only)
"Three-step image rectiﬁcation" (Monasse)
"Rectification and Disparity" (slideshow by Navab)
"A fast area-based stereo matching algorithm" (Di Stefano - seems a bit inaccurate)
"Computing Visual Correspondence with Occlusions via Graph Cuts" (Kolmogorov - this one produces a very good disparity map, with also occlusion informations, but is it efficient?)
"Dense Disparity Map Estimation Respecting Image Discontinuities" (Alvarez - too long for a first review)

Could someone please give me some advice for diving into this wide topic?

What kind of algorithm/method should I treat first, considering that I'll work on a very simple input: a pair of left and right images and nothing else, no more information (some papers are based on additional, pre-obtained, calibration information)?

Speaking about working implementations, the only interesting results I've seen so far belongs to this piece of software, but only for automatic rectification, not disparity.

I tried the "auto-adjustment" feature and it seems really effective. Too bad there is no source code.


texts: How can I reduce Subset Sum to Almost Subset Sum?

texts:
Maybe this is quite simple, but I am having some trouble how to do this reduction. I want to reduce Subset Sum to Almost Subset Sum.

Subset Sum: given a set of positive integers $A=\{a_1,a_2, \dots,a_n\}$ and an integer $M$, decide if there is a subset of $A$ with a sum equal to $M$.

Almost Subset Sum:

Input: a set of positive integers $A=\{a_1,a_2, \dots,a_n\}$, and a positive integer $M$.

Goal: decide whether there is a subset of $A$ with sum $S$ such that $|M −S| < d$ where $d = ⌊\log M ⌋$?


texts: How is diagonalization a valid argument for the undecidability of the halting problem?

texts:
All proofs for the undecidability of the halting problem seem to be based directly or indirectly on self-reference.

def g():
    if halts(g):
        loop_forever()

My question is: how can the input of a TM contain the TM itself and its input?

If the description of the TM has states and transitions, then it has more than its input therefore the input of the TM has infinite size because it contains both the TM and the input.


texts: Another feasible way to implement multi-level page table?

texts:
The advantage of a multi-level page table is that we can swap the inner-level page tables to some secondary storage. If however we want quick access to the whole address space, we have to keep all page tables in memory. Then there are no savings.

However, imagine that not the innermost page-table pointed to the final frame, but that each page table contributes a bit to get the final address. In other words, we divide each virtual address into sections and map these instead.

I.e. we have a virtual address 1011 that maps to 1110 using a 2-level page table. Then the outer-level page table maps 10 -> 11 and the 2nd-level page table with index 3 (from binary 11) maps 11 -> 10. Together we get the address 1110.

I was learning about multi-level page tables and they were quite confusing to me. This is the way I initially imagined they worked. Now obviously, this restricts how we can map the virtual address space to the physical address space, i.e. pages with the same prefix will have physical locations close to each other. However, I don't see the problem with this approach.

Why is this approach not used if it can save memory? Or do I have some error in my thinking?


texts: Travelling salesman very rough min and max estimates

texts:
Is there a way to find very rough minimum and maximum estimates for the travelling salesman problem? The estimates only need to be within the roughly same magnitude, but it's important that the minimum estimate is lower (or equal) to the actual distance and that the maximum estimate is higher (or equal) to the actual distance.

EDIT:
Metric TSP unfortunately does not apply.
To add some context: I'm searching for non-dominated fronts (pareto fronts) for a Multiobjective TSP, e.g. optimizing for multiple variables like travel time and distance. I'm using NSGA-II which requires an upper and lower bound for each objective function, which translates into rough estimates for single-objective TSP, with the constraint that the upper estimate has to be higher than the real max distance and vice versa.


texts: In Asyptotic notation if g(n) < f(n) is it possible to have f(n)<=c*g(n)

texts:
I am studying asymptotic notation and I was thinking of a possibility where if g(n) < f(n) is it possible to have f(n)<=cg(n). For example if -
f(n)=6n+5 and g(n)=4n+5, such that it possible to say (6n+5)<=2(4n+5) where 2 is c. Are f(n) and g(n) here valid function in term of asymptotic notation.


texts: What is the difference between a Type and an Abstract Type?

texts:
In my data structures course we are given definitions for Type and Abstract Type but they confuse me.

  A type is a set of values and the operations you can do on them. The set of operations is called an interface.

Wait, what? Do this mean that Type = set of values + interface?

  An Abstract Type is a type only accessible through its interface.

I fail to see how this differ from the Type definition. You always need to use the interface in order to do anything with the set of values. Are there types that can be accessed without having a set of operations defined on them a.k.a an interface?


texts:
Let $L_1$ and $L_2$ be two languages over an alphabet $\Sigma$. The quotient of $L_1$ and $L_2$ is the language
  $L_1/L_2 = \{x : \exists y \in L_2, xy \in L_1\}$

  Show that if $L_1$ is regular and $L_2$ is any language, then $L_1/L_2$ is regular.

I've looked up online how to do this but it not very helpful. So far I know that $L_1$ and $L_2 \in \Sigma^*$    and that $L_1 = \{xy \mid x \in \Sigma^* \text{ and } y \in \Sigma^*\}$ and we can say it is regular by concatenation and $L_2 \in \Sigma^*$  which is any language.

From here, we can say that in $L_1$, $x$ has an accept state before going to the DFA for $y$ and $L_1 / L_2$ would just be eliminating the DFA for $y$, leaving you with just $x$, which still has an accept state, which makes it regular. I don't know how to put this in words and not pictures.


texts: Graph Algorithm (Modification on Dijkstra?) : Tech Interview

texts:
Problem: Suppose we had a directed graph $G(V,E)$ with strictly positive edge weights, a nonempty set $A$ (special vertices) such that $A \subseteq V$, a positive integer $C$, and a starting vertex $S \in V$. Find the shortest path starting at $S$ and containing at least $C$ vertices in $A$ (cycles are OK). If no path exists, output -INF or +INF. Polynomial time algorithms only (in $V$, $E$, and $C$).

My attempt: If there are at least $C$ vertices in $A$ that I want to find, then maybe I could replicate the graph $C$ times, where each replicated graph is like a layer. So when running Dijkstra, if I step into a special vertex, that vertex connects me to its counterpart in the next layer. If there are 10 vertices in the graph and I want to find when I step into the special vertices 3 times, then there will be 30 total vertices because each layer contains the identical looking 10 vertices.

I have issues translating this idea to any sort of (pseudo) code. Perhaps my idea isn't even valid; in that case, any help would be appreciated in proposals of a different solution.


texts: Counting permutations whose elements are not exactly their index ± 1

texts:
This is a special case of the question:
Counting permutations whose elements are not exactly their index ± M

The $M=0$ case has already been solved, but no one was sure how to work out the non-zero cases.

So I decided to try to just brute force some values and search the results for a recursion relation.  As a test I first tried $M=0$ and searched for recursion relations that looked like:
$$ a_n = \sum_{1\le i \le k} (A_i n + B_i) a_{n-i} $$
where $k$ is some cutoff of how far back to search, $A_i \in \{-1,0,1\}$ and $B_i$ some small integers.  It was correctly able to find:
$$a_n= (n-1)a_{n-1} +(n-1)a_{n-2}$$

So I then tried for $M=1$ and found:
$$ a_n= (n) a_{n-1} +(-n+2) a_{n-3} + (-1)a_{n-4} $$

It's possible it's just a coincidence, but I ran a brute force approach to calculating the $M=1$ cases overnight to get a couple more values and it still holds. But even with this potential answer in hand, I cannot figure out a reason this recursion would hold.

Is there a simple combinatoric argument I'm missing here?


texts:
Given $n$ points $(x_1, y_1), \ldots, (x_n, y_n)$ on a 2-dimensional plane.
  A point $(x_1, y_1)$ dominates $(x_2, y_2)$ if $x_1 > x_2 \land y_1 > y_2$.
  A point is called a maxima if no other points dominate it.

I can come up with an $O(n \log n)$ algorithm to find all the maxima. However, I failed to solve:

  Problem: What is the lower bound for the "finding all 2D maxima" problem (say, on the comparison model)? And how to prove it?


texts: Can reversing the final and non-final states of a DFA produce the complement of the original language?

texts:
Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of the language that was accepted by the original automata?

What if we talk about a Non deterministic finite automata instead of a DFA?


texts: What complexity class decision problems can be solved by only addition, multiplication, division and subtraction?

texts:
So in what complexity class would all decision problems in that class can be transformed into a problem (by many-one reduction) that its solution only involves basic arithmetic operation of multiplication, division, addition and subtraction?

So, like this: for every problem, there is input and output (we consider only those that halt) and my question is that is there any complexity class that all problems in the class can be transformed into a problem that involves only elementary arithmetic of the form of arithmetic function involving only arithmetic like $2^x+x^5/4-4x+2$ where $x$ is input coded as natural number.


texts: To remove all comments in a JavaScript file, do we need just a scanner or also a parser?

texts:
I was asked how to remove comments in a JavaScript program, but once I gave the regular expression solution, I was asked what if there are comments like text inside of a string:

let hi = " // here ";
let foo = "   use this: /*   ";
let foo2 = "   \" and that */   ";

it also can get complicated with the cases with string being able to be quoted by ' and the backtick `:

let hi2 = 'here //';
let i = 123;
let hi3 = `here //  ${i  /* don't use j */}`;
let hi4 = `here //  ${i  // don't use j
                         // because j is not good
                     }`;
let hi5 = ` and use there ' " \' \" \`  /*  */`;
let hi6 = ` this is really closing, not quoted backtick \\`;
let hi7 = `here //  ${i  /* don't use j in `` */}`;

So I mentioned a scanner (lexical analyzer) and a parser (like yacc or bison) can be used. So we can build a tree of node representing the program, and then wherever it is a comment type of node, we can remove it. (comment nodes have no children, I think? If they do, then can just change the comment to nothing, the empty string).

But is it true that all we need is a scanner?  We can tokenize all the text, and then we get each element which is a string, an operator, the left and right operands, and also the comment elements.

And then we can just remove all the comment elements and then reconstruct the program using all the tokens.

So probably we don't even need the program code to be represented as a tree, but just as a series of tokens.  So if we already have a scanner and parser, all we need is a scanner, and when we supply it with the proper grammar rules, we can remove all the comments?

(is the following considered grammar or just finite state automata and do we just use it to form the tokens?)


texts: Grammar of regular languages vs. context free languages

texts:
Let $L$ be some language.
What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language?

For example, in case $L$ is regular,
could you say that there exists a context-free grammar $S$ such that every derivation rule of $S$ is of the form:

$$V \rightarrow \sigma_1 \sigma_2 \cdots \sigma_k V_1V_2 \cdots V_m$$

In other words, the prefix of the rule contains only symbols of $\Sigma$ and the postfix contains only variables of $V$.


texts: Help with context free grammar excercise

texts:
So, I have an exercise in which I have to write a context free grammar for this language:
$$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$
meaning every string with any number of $a$'s, $b$'s and $c$'s in that order, with the amount of $a$'s greater than the amount of $c$'s and the amount of $b$'s greater than zero.
I am having trouble figuring out the rule that makes sure there are more $a$s than $c$s.
I have:
$$\begin{align}S&\to aABC | ab\\
A&\to aA | a\\
B&\to bB | b\\
C&\to cC | c\\
\end{align}$$
I know this is wrong because I should be adding an $a$ every time I add a $c$, but I don't know how to write that.


texts: Prove the boolean function E = F + G contains of the sum of the minterms of F and G

texts:
I'm given a boolean function E which is result of the sum of F and G (Where both F and G are boolean functions for sure).
By using K-Map I can easily understand why E would have the sum of the minterms of F and G but I want a mathematical and written proof for that.
Is there any?


texts: Information-theoretic limits for a weighing puzzle

texts:
Consider the following problem:

You are given $n$ coins with labels $1, \ldots, n$. You know that coins have weights $1, \ldots, n$, but you don't know whether the labels are correct (i.e. they can be in a different order). Using balance scales (the outcomes are $>$, $=$ or $<$) at most $k$ times, determine whether the labels are correct.

I'm not exactly interested in how to solve the problem: the original problem was for $n=6$ and $k=2$, and I know solutions. What I'm interested in is the following: when I heard the problem, I first tried to determine whether a solution even exists from the information-theoretic standpoint. I.e. is the amount of information revealed by $k$ weighings even potentially enough? I don't know how to approach it.
For example, for $n=6$ and $k=2$ there exist $2$ solutions:

 compare $1,2,3$ with $6$ and then compare $3,5$ with $1,6$
 compare $1,3$ with $5$ and then compare $1,2,5$ with $3,6$

But if we estimate the amount of information naively, then we conclude that with $2$ weighings we can only distinguish $3^k=9$ permutations, which is much less than required $6!$.


texts: Can the definition of regular languages be simplified?

texts:
Wikipedia says

  The collection of regular languages over an alphabet Σ is defined
  recursively as follows:

  The empty language Ø is a regular language.
  For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language.
  If A and B are regular languages, then A ∪ B (union), A • B (concatenation), and A* (Kleene star) are regular languages.
  No other languages over Σ are regular.

I think that if it is closed under concatenation, then it must be closed under Kleene star, because we can take B to be A. So the definition can be without being closed under Kleene star?


texts: Min no.of operations required to convert an array to which it should contain elements of equal frequency

texts:
I have come across this tricky problem. An array of N elements should be converted to another array within k operations such that, distinct element's frequency should be

Equal and
A largest possible prime number

e.g. [2, 2, 2, 3, 3, 4] and k = 3 Here element 4 can be converted to 3 in one operation and by doing so, the frequency of all elements will be equal to (3) and that is the largest possible prime number we can get.

Another eg. [1, 1, 1, 1, 2, 2, 2, 6] and k = 3 we can convert two 1s into any new number x in 2 operations and convert one 2 to 6 in one operation. By doing so, the frequency of elements will be equal (2) and that is the largest possible prime number we get.

Also, we have to check whether it is possible within k operations.

Please help me out :) I couldn't understand the math behind these type of problems i.e. Min/Max no of operations required etc.,

Edited to add below steps tried so far:

1) Find the list of prime divisors of N which is less than N. for example, if N = 6 there are two prime numbers which can divide N i.e. 3 and 2 and if N = 8 there is only one prime number that can divide 8 that is 2.

2) Example no. 1, Take the other factor of largest found prime divisor, that will become the number of distinct elements in the array. i.e. N = 6 divided by prime 3 (the largest) is 2 and yes we need only 2 distinct numbers with frequency 3.

3) Take e.g. 1, the frequencies are [2]=3, [3]=2, [4]=1 comparing the first two frequencies. How to actually come up with required no.of operations to make the target array of two distinct elements of frequencies 3 ?

Whether by comparing each item from sorted(descending) frequency list with the largest prime divisor and add to HashSet and the number of operations is the sum of all HashSet values? In example no. 1, compare 3 with [2]=3 the difference is 0, compare 3 with [3]=2 the difference is 1. So, the num of operations will be 1 (0+1) ignoring the additional distinct elements frequencies.

Apply the same to example 2, and we need to add zero for new distinct element and ignore it.

After this I couldn't proceed because I thought I'm bit overthinking. Please try yours and help me.

Would really appreciate if a mathematical form/notation is defined for the above approach.


texts: Multiple paths for a accepting string in NFA?

texts:
If a string(w) is accepted by an NFA, then corresponding to w,
can there be multiple paths each starting from the start state and ending at an accepting state?


texts: Hash for verifying both compressed and uncompressed data?

texts:
Is it possible to have a single hash function output simultaneously verify a compressed block of data as well as its uncompressed counterpart?

Trivially one could just use a hash function twice (once on the uncompressed version and again on the compressed version) and concatenate the outputs, or use a hash function that internally does that, but I wonder if it's possible otherwise.

For example, imagine we've got these functions:

Hash getHash(byte[] data);
byte[] compress(byte[] data);
byte[] decompress(byte[] data);
bool verify(byte[] data, Hash hash);

...then I'm looking for these properties for a nontrivial byte array D (that is uncompressed):

verify(compress(D), getHash(D)) == verify(D, getHash(compress(D))) == verify(D, getHash(D)) == true
D == decompress(compress(D)) for all D, i.e. lossless compression
verify(E, getHash(D)) == false "most of the time" when E != D, i.e. collision "resistant" hashing

This could be useful when verifying persisted compressed data: you could verify the correctness of the compression algorithm and of the uncompressed data both at the same time without having to decompress it or store multiple hashes.

I'm not sure where to start looking for this. I think what I'm describing is some kind of homomorphism but apparently I need to level up my search skills. It seems like a Difficult Problem™; for example, the Deflate algorithm outputs data structures like a Huffman tree/table, and the mathematical relationships of serialized data structures being run through hash functions aren't immediately obvious to this OP.


texts: Given 2 sets of n points: minimize sum of traveled distances

texts:
I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean distance.

I am aware that this transportation problem is a special case of the earth mover distance problem, but since its unweighted (and over points) I am wondering if there is a more efficient algorithm than the cubic time hungarian method for it?


texts:
What is meant by saying an algorithm runs in time $Poly(|S|,n,\frac{1}{\epsilon})$.

Can somebody explain with an example.


texts: Where can i find literature about the $\frac{4}{3}$-conjecture for approximation of the Metric TSP?

texts:
In Graph-Theory there are many ways for efficient approximation-algorithms to solve the Metric TSP. The best solution seems to be the Christofides Heuristic with a factor of 1.5 to the optimal solution. My Teacher said, there would be the so called $\frac{4}{3}$-conjecture, which states: there might be a approximation solution for the metric tsp, that has only a $\frac{4}{3}$-factor.

But i cannot find any literature or further information about this assumption. Maybe you can?


texts: How are REGEXP implemented in programming languages?

texts:
Is there a good general paper about the interpretation or compilation
of REGEXP in programming languages for pattern matching, with or
without variables? I am not looking for a quick explanation about the
construction of DFAs, but for a real paper on how it is actually done
in programming languages implementation, and what is considered simple
or difficult. I expect differences between languages may have an
inpact. A formal paper on how REGEXP implementation should be done is
useful too :-)


texts: Longest double increasing subsequence (LIS variant)

texts:
I'll start with the definitions:Let $S = s_1s_2...s_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p_1p_2...p_k$ (not necessarily continuous) where for each $2<i\leq k$ we have $p_{i-2} < p_i$. For example, if $S = 1 \space 4\space 2\space 7\space 1\space 6$, a possible double increasing subsequence is $P = 1\space 2\space 7\space 6$ because $7 > 1$ and $6 > 2$. (For every sequence $S$ with more than 2 elements, there's a trivial subsequence of length 2) The problem is to determine the length of longest double increasing subsequence (LDIS) of a given series of integers, $S$.

This is what I've done: I defined $C[i]$ to be the length of the LDIS of the series that ends with $s_i$, and $E[i]$ to be the element before the last element of the LDIS that ends with $s_i$. In the example aforementioned, $C[6] = 5$, and $E[6]=7$. If there are several options for $E[i]$, we'll take the minimal one. For example for $C[5] = 2$ we have 3 different options for LDIS, all of lengths 2: $4 \space 1$,  $2 \space 1$ and  $7 \space 1$ (Trivial LDIS's), so we'll define $E[5] = 2$.

Now my dynamic programming solution is just like LIS solution (the $n^2$, not the $nlogn$):
If $C$ and $E$ are my $n$-sized arrays, $C[1] = 1, E[1] = \inf$(meaning there's no previous value), $C[2]=2,E[2]=s_1$, and for every $2<i\leq n$ we finding $C[i]$ by iterating over the previous $i$ calculates values, and we take the maximum over the $C[i]$'s such that $s_i>E[i]$, plus 1. (Again, if there are several candidates, we take E[i] as the minimal of the possible options) After calculating all $n$ values, we iterate over the array and choose the index that hold the maximal $C[i]$.

This is my mind set in general, maybe I've missed several details but I believe I delivered the idea. Now these are my problems with my solution:
1) It misses strong, well defined recursive formula. I can phrase some sort of recursive relation according to the regularity of the question, but it feels kinda forced. (Despite of the iterative solution I've describe, which is fairly simple)
2) I've ran the algorithm on several examples and it seems to give a right answer, but as a consequence of 1, I have hard time "believing" my solution is correct. I feel like there's more simple and elegant solution to the problem.

Any ideas will be vastly appreciated, thanks in advance.


texts: Is there an algorithm which can compute every algorithm's time complexity?

texts: I think of an algorithm which computes the time complexity. It would be great if a code editor could compute the time complexity of the selected lines and even compare two pieces of codes in order to help developer to select one of them. I heard something related with halting problem but couldn't figure out.