texts:
Source of the problem is https://codeforces.com/contest/1152/problem/D . I think i understood the problem , but if possible please explain the problem in simple way and the solution also .I tried very hard to understand the solution mentioned on the website but i was unsuccesful . The problem is  following-

Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length 2n.

The definition of correct bracket sequence is as follows:

The empty sequence is a correct bracket sequence,

If s is a correct bracket sequence, then (s) is a correct bracket sequence,

If s and t are a correct bracket sequence, then st is also a correct bracket sequence.

For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie?

solution source  - https://codeforces.com/blog/entry/66696

Please refer to the link for examples .


texts: Finding three factors of a number with minimal sum

texts:
Suppose that we have a number $x \in \mathbb{Z}^+$.

I am seeking an algorithm to find three numbers $a, b, c \in \mathbb{Z}^+$ such that $a \times b \times c = x$ and $a + b + c$ is minimum.

Is this problem a variant of subset sum? Am I stuck with an exponential time algorithm?

Examples

$32 = 4 \times 4 \times 2$
$36 = 4 \times 3 \times 3$
$11 =  11 \times 1 \times 1$
$6 = 2 \times 3 \times 1$


texts: How to simplify a rational function with floating point real coefficients (GCF)

texts:
How does one compute the simplified form of a rational function where the coefficients of the polynomial are floating point numbers (real, though I expect using complex numbers would be the same).

Wikipedia says it is possible using SVD, but I'm unsure about how to represent the polynomial so as to do use this.


texts:
I have a question regarding Turing machines.

Are these two tapes the same thing?

First one =  _ _ _ _ * A A A B B B

Second one =  * A A A B B B

_ denotes a blank tape cell.


texts:
This question is about computation/computational physics.

Imagine that you want to solve $10^6$ equations of motion, and you have $10^6$ degrees of freedom (position of the particle).

How many RAM memory would you need (theoretically) to do this?

(I am not interested in the final answer, I am just interested in the thinking of estimate this.)

Thank you


texts:
Lets say I have given following grammar which generates arithmetic expressions in reverse polish notation:

$G=({E},{a,+,*},P,E)$
$P={ E \rightarrow EE+ | EE* | a }$

I know this grammar is unambiguous.

What I do not understand is how I can prove this.

I already searched a lot to in google, etc. but everyone only says, that reverse polish notation are unambiguous, but not WHY.

Can you give me any hints?


texts: Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?

texts: Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine with a psuedo-random number generator can't do? (a trivial thing it can do would be generating truly random numbers)


texts: Transformation from one feature space to another

texts:
I have found the following example:

  As an example consider the case when the input space  $ {\mathcal{X}}$
  consists of images of  $ 16\times 16$ pixels, i.e. $ 256$ dimensional
  vectors, and we choose $ 5$th order monomials as non-linear features.
  The dimensionality of such space would be

  $\displaystyle \left(\begin{array}{c}5+256-1\\ 5\end{array}\right) \approx 10^{10} \;$

  Such a mapping would clearly be intractable to carry out explicitly.
  We are not only facing the technical problem of storing the data and
  doing the computations, but we are also introducing problems due to
  the fact that we are now working in an extremely sparse sampled space.
  By the use of the SRM principle, we can be less sensitive to the
  dimensionality of the space and achieve good generalization.

  The problems concerning the storage and the manipulation of the high
  dimensional data can be avoided. It turns out that for a certain class
  of mappings we are well able to compute scalar products in this new
  space even if it is extremely high dimensional. Simplifying the above
  example of computing all $ 5$th order products of $ 256$ pixels to
  that of computing all $ 2$nd order products of two ''pixels'', i.e.

  $\displaystyle {\boldsymbol{x}} = (x_1,x_2)$   and$\displaystyle \quad\Phi({\boldsymbol{x}}) = \left(x_1^2,\sqrt{2}x_1x_2,x_2^2\right)\;$

The problem that I have is in understanding the last formula, from where does the author gets those values for the individual transformation? To me, it seems that he is applying the formula of analytical geometry of a circle, but I am not quite sure.

Also how does the author apply the transformation from $ {\mathcal{X}}$ to $\displaystyle\quad\Phi({\boldsymbol{x}})$?


texts: Number of permutations of set {1, 2, ..., n} for which insertion sort will perform exactly n permutations

texts:
I have had the following problem at my last exam:

For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons.

My thinking was: there must be exactly one inversion of succeeding elements so any of the pairs (2, 3) or (3, 4) ... or (n-1, n) has to be swapped in the sorted sequence. So I answered n-2 because there's n-2 such pairs. But the answer was 2(n-1). Why?


texts: The difference between a Hoare Triple/Assertion and a Typed Function

texts:
I have been trying to wrap my head around applying Hoare Logic and am running into the question of how Hoare triples are any different from (simply) a typed function.

That is, say you have a typed function $f : A \to B$. The initial state for the function is thus $A$, and the final state is $B$. Similarly, in Hoare Logic, it would be like $\{A\}\ f\ \{B\}$. It's like the Hoare Triple is a typed function application or something, but I'm sure functional programming has those typed as well.

The types could be complex types such as dependent types that have constraints on the input as well, so you can handle things like $x > y$ and the like. So I'm wondering, what the differences are between Hoare Triples and Typed Functions (in any type system) generally.


texts: The purpose of the splitting lemma for $\mathsf{SF(\Sigma^*})$

texts:
We've definied the splitting lemma for starfree languages as follows:
Let $L \in \mathsf{SF}(\Sigma^*)$ and $A, B \subseteq \Sigma$ with $A \cap B = \emptyset$. Then it holds true that for $K_i, L_i \in \mathsf{SF}(B^*)$: $$L \cap B^* A B^*= \bigcup_{\text{finite}} K_iAL_i$$
I can not see why this is useful by any means. At first, I thought that we might use this to "translate" some $L$ to its starfree equivalent, but we use $L \in \mathsf{SF}(\Sigma^*)$ as a precondition for the lemma, and furthermore, we don't even get a starfree representation of $L$ through this. So what do we use this for?


texts: Determine whether a variable has positive influence in Boolean function

texts:
Given a Boolean function $f$ over the set of variables $X =\{ x_1,...,x_n \}$, the influence of $x_i$ is defined as the probability that changing only $x_i$ on random input changes $f$.
Given a function $f$ presented in $\text{CNF}$, and a coordinate, are there any known methods for determine if the coordinate has positive influence?


texts: Can a greedy algorithm have more than one subproblems to solve after making greedy choice?

texts:
For example:
s = <s1 s2 s3> is my problem,

I make greedy choice s2 and solve s1 and s3 in a greedy way.

In CLRS, it was mentioned regarding "designing greedy algorithms"

  Cast the optimization problem as one in which we make a choice and are
  left with one subproblem to solve

So why is it that we are left with only one subproblem in greedy method after making greedy choice?


texts: Is this a known question in matrix sketching?

texts:
Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m \ll D $ dimensional columns and stack them up as a matrix $A'$ of dimension $m \times n$ such that

$$\|A^TA - A'^T A'\|_2 < \epsilon$$

for some given $\epsilon$.

Is this some standard questions that is known? It would be very helpful if someone could kindly point me to the closest available literature on this!

If one takes a SVD of $A$ and looks at the top $m$ left singular vectors say $\{ u_i \}_{i=1}^m$ and the top $m$ right singular vectors say $\{ v_i \}_{i=1}^m$ and the top $m$ singular values being $\{ \sigma_i \}_{i=1}^m$ then most likely for a given $m$ the best $A'$ is $A' = \sum_{i=1}^m \sigma_i u_i v_i^T$. But doing this calculation will take time polynomial in $D$ and $n$.

I am hoping if there are matrix sketching techniques or subspace learning techniques which will achieve this in $O(polylog(n,D))$ time.


texts: How to check for ambiguous grammar if you don't know the string

texts: Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know how to check for ambiguity when you're given a particular string but what about the cases when it's not? Is there any algorithm to do this?


texts: Calculating the cost for each operation in amortized analysis

texts:
According to what I've read in the CLRS book , we calculate the amortized cost for a complete set , and not for a single operation.But in an exam question , it was asked about an operation amortized cost and there hadn't been any info on the analyze function.

In these scenarios, how would one calculate the cost for an operation?
For example , In the fibonacci heap , the extraction cost is considered.
Is there any standard for this or is the exam question wrong?

Thanks.


texts: Model for formula $\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)$

texts:
I am new to LTL and I am trying to understand how it works. My question is: is there such $\sigma$ that:

$ \sigma \models [\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)]$

I know that:

$\sigma \models \Box \psi: \forall k \, [(\sigma, k) \models \psi] \\
\sigma \models [\psi \Rightarrow \phi]: (\sigma \models \neg \psi) \vee (\sigma \models \phi) \\
\sigma \models \Box \psi \iff \sigma \models \neg\Diamond \neg \psi$

So

$\sigma \models [\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)] \iff \\(\sigma \models \Diamond (\neg\psi \land \neg\phi)) \vee [(\sigma \models (\Box \psi)) \vee (\sigma \models (\Box \phi))]$

I would say there is such $\sigma$ since I don't see any contrarguments but I'm not sure if I can say anything about $\psi$ or $\phi$ except that both are formulas (so I don't know how to show any specific example).


texts: Determine if there is a path with alternating edge colours in directed graph

texts:
Given directed graph $G = \langle V, E \rangle$, such that some vertices are red, and some vertices are black, and some edges are blue or green, decide for all vertices $v \in V$ if there is path from $v$ to some red vertex with alternating edge colours (no edges of same colour are adjacent in the path, e.g. blue -> green -> blue -> ...).

If $G$ is acyclic, the problem looks simple - just use DFS. But how can one solve it if there are cycles in $G$?


texts: Cardinality of sets and strings -> confused

texts:
I have a question regarding the cardinality of sets and strings.
If $ \Sigma^* $ is empty, the cardinality is 1, because the empty word $ \varepsilon $ is counted.
If $ \Sigma^+ $ is empty, the cardinality is 0, because the empty word is excluded from the set.
If $ \Sigma $ includes at least one symbol, the cardinality of $ \Sigma^* $ is inifite.
If I use a string without the definition of $ \Sigma $, for example to define a variable, then I have problems to understand the cardinality. So if I set a variable to a string: $ a = "a" $, the cardinality of the string is 1. But if I set a variable to an empty string: $ a = "" $, the cardinality is also 1, because "" is the same as the empty word $ \varepsilon $.
The first time I noticed this was in a book whereas the definition of Pumping Lemma allows $ i=0 $ for the pumped word-part $ y $. Which means for me that $ y^0 = \varepsilon $ is allowed, because $ \varepsilon $ counts with 1. At the same time, others sources mention that it's not allowed to define $ y = \varepsilon $ for the Pumping Lemma.
Is the book wrong with allowing $ i = 0 $, or are the other sources wrong by disallowing $ y = \varepsilon $? Or do I completely misunderstand this?
Thank you!


texts:
Look at the last problem on page 2 here,
http://www.cs.nyu.edu/~khot/CSCI-GA.3350-001-2014/sol3.pdf

All one wants to do is to convert a $x \in \{ 0,1\}^n$ into a $y \in \{0,1\}^k$ . Then just a linear transformation would have been enough. Why install this vector "b"?
If $a_1,x_1,x_2 \in \{0,1\}^n$ and $b_1,y_1,y_2 \in \{0,1\}$ then why is demanding simultaneous satisfaction of the equations $a_1^Tx_1 + b_1 = y_1, a_1^Tx_2 + b_1 = y_2$ the same as claiming the simultaneous satisfaction of the equations, $a_1^T(x_1 \oplus x_2) = y, b_1 = y \oplus y_1$ ?( where $y = y_1 \oplus y_2$)


texts: Subsampling of Frequent Words in Word2Vec

texts:
I am reading through the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf

Under section 2.3 on page 4 the authors discuss subsampling of frequent words.

Now based on my understanding of subsampling of frequent words, the goal is to reduce the number of times we sample frequent words. But here is what the paper states:

"To counter the imbalance between the rare and frequent words, we use a simple subsampling approach: each word $w_i$ in the training set is discarded with probability computed by the formula

$$P(w_i) = 1 - \sqrt{\frac{t}{f(w_i)}}$$

where $f(w_i)$ is the frequency of word $w_i$ and $t$ is a chosen threshold typically around $10^{-5}$."

Now, I am interpreting $f(w_i)$ as an integer value that essentially counts the number of times $w_i$ occurs in the corpus. But this seems to not make any sense because all words then discarded with probability $.99$ or greater. Should I instead be interpreting $f(w_i)$ as $\text{count}(w_i)/\text{total_count}$ where $\text{total_count}$ is the number of words in the corpus?


texts:
The problem is, K_longestPath:

  We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each other city. We have to find a path that goes through each such city without forming a cycle.

We are given the Graph with a valid configuration of cities and we have to find if there exists such a path.

At first I was thinking solving this with Hamiltonian path, but to show that the problem is NP-complete I have to find an algorithm that will change it's inputs to be inputs for this problem that we got, and I don't know how to do this..


texts:
I have a basic question about the power of Linear Programming that has been bothering me for some time.  I believe there is something simple I am missing.

Linear Programming is $\mathsf{P}$-complete, which means that every problem in $\mathsf{P}$ can be reduced to it using an $\mathsf{NC}$ reduction.  (See the wiki for some nice background)

However, it has been shown that the perfect matching polytope has exponentially many facets (see this recent STOC paper for example. This shows it even has exponential extension complexity---i.e. even using extra dimensions we require an exponential number of inequalities).

However, the classic Blossom Algorithm can find a perfect matching in polynomial time--determining if a graph has a perfect matching is in $\mathsf{P}$.

This seems like a conflict to me: we can reduce the perfect matching problem to Linear Programming, but its polytope must be exponentially large.  What am I mising?  Is there processing during the reduction that avoids using the entire matching polytope?


texts: Predecessor function with recursive types

texts:
I am defining the type Nat of natural numbers a recursive sum type:

$$ Nat = \mu X. Unit \oplus X$$

Now, I have defined zero as the term:

zero : Nat
zero = fold Nat (Inl tmUnit tyNat tyUnit)

and successor as

succ : Nat -> Nat
succ n = fold Nat (tmInr n tyNat tyUnit)

Please note, that I am not completely sure of these two implementations; they might be wrong - I accept comments on them too.

Now, my question: I want to implement a predecessor function. I have both an isZero function and an if-then-else construct. How could I to this?


texts:
This is a conceptual issue that I am having in designing an algorithm for a memory allocator that works in conjunction with memory pooling.  Free blocks are put on one of several free lists within the pool.  The size of the block determines which list it is on.  The question is how to figure out if the adjacent physical memory blocks are free and available for coalescing when they are on different lists? Or, in other words, how to figure out if physically adjacent memory blocks are also free when the blocks are on different lists and then combine them.

Granted, the time on this is expensive so I plan to run this only when a suitable block cannot be found or carved out of an existing block.

The only viable approach that I can think of is to scan the entire pool while looking for a signature.  Then search all the lists to verify that the address of that block is on a list.

I have done some research and found the following links:

How does worst-fit memory allocation react when encountering contiguous empty memory blocks?
http://faculty.kfupm.edu.sa/ICS/saquib/ICS202/Unit34_MemoryManagement.pdf

Any suggestions or ideas?


texts: Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements

texts:
Let's say we have a binary min-heap of size $n$, and we want to get an array of the smallest $\log n$ values in the heap, sorted. What is the best complexity that we can get and how do we implement it?

The simplest solution would be using $\text{Get-Min, Delete-Min}$, $\log n$ times, and that would be of time complexity of $O(\log ^2 n)$.

I've been told that this problem can be solved in time complexity of $O(\log n \log \log n)$, but I couldn't figure out an algorithm that reaches that time complexity.


texts: How do I choose the right model for production?

texts: I am trying to build a classification algorithm having 28 classes. These classes consists of Logo of companies like adidas , Nike etc. I have very low dataset below than 100 images and greater than 70 images. I have trained CNN model but not got decent results. We all know that if error of the test data is high , then model is overfitted and if model performs poorly on test set it is also overfitted. If training loss decreases , and then starts increasing gradually model is also overfitted. There are any scenarios to identify the problem . Which identification should I choose in my case.


texts: Master Theorem Case 3 Regularity Condition

texts:
In case 3 of the master theorem, we have to show that

$$ af(n/b) \leq cf(n). $$

I don't understand how I can setup this formula. As an example, we have

$$ T(n)=3T(n/4) + n \lg n.$$

In this case $a=3$ and $b=4$.
This gives us $O(n^{0.793})$ which is smaller than $f(n) = n \lg n$ which means case 3.

Now, the solution is:

$$af(n/b)= 3(n/4) \lg(n/4) \leq (3/4)n\lg n.$$

I'm not sure how we got the above? $af(n/b)$ in my book is $3(n/4)$ so where does $\lg(n/4)$ come from? Also, since $f(n)$ is $n \lg n$, shouldn't the evaluation be:

$$3(n/4) \leq n \lg n ?$$


texts: Regex for at least three 1's and at most four 0's

texts:
The alphabet is {0,1}, express all finite strings containing at least three 1's and at most four 0's.

I've come up with a method that enumerate every possible number of 0's:

$$111^{+}+0111^{+}+1^{+}011^{+}+111^{+}01^{*}+00111^{+}+......$$
But for three 1's and four 0's this is far too complex.

Need some help.


texts: Is transfer learning applied on only similar datasets only?

texts: I am trying to make a CNN model on different brands of logos . Firstly , I wrote a CNN from scratch and trained it on which I got 70% accuracy, I have total 40 classes and each class has 100 images . I know it is too short, that is why I am now moving towards pretrained model. My question is that I read on Internet that Transfer learning applied on only similar datasets like lets say VGG model trained on Cats and Dogs , so we can use it for training the tiger images also . Can I use different dataset like I am using MobileNet on different brands of logos . Will it give good accuracy ?


texts:
If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained by BFS.

Here, I consider that each weight of the edge is the minimum of the end vertices and the weight of the path is the sum of the edges divided by the number of edges on the path.

I am unable to use BFS for such algorithm. Please suggest me a suitable known algorithm to solve such problem. The following problem is solved manually, but I wish to solve it by using some known algorithm.


texts: Proving equivalence of two substitutions by induction

texts:
I'm trying to prove the following reduction:
$$
     t\{x:=u\}\{y:=v\} = t\{y:=v\}\{x:=u\{y:=v\}\}
$$
under the following assumptions:

$x \neq y$
$x$ is not a free variable of $v$ (in symbols, $x \notin \operatorname{fv}(v)$).

My idea is to do it by induction, but I'm a bit stuck with the base case. I would appreciate if someone can explain to me how to write such a proof. I'm including what I tried, which is wrong or incomplete.
Base case: $t = m$ is just a variable.
On the left side we have:
if m = x ⟹ u{y:=v} (if u=y then v else u)
else     ⟹ m{y:=v} (if m=y then v else m)

On the right side we have:
if m=y ⟹ v{x:=u{y:=v}} (if u=y then v{x:=v} else u{x:=u}
  so we get either (v=x ⟹ v else v) or (u=x ⟹ u else u)
else   ⟹ m{x:=u{y:=v}} (if m=y then m{x:=v} else m{x:=u}
  so we get either v or m

I understand we end up getting the same four branches, but is that considered really a proof? Is this the proper way to write such a proof and conclude the base case? Also, the given assumptions didn't help much here, so I think I'm missing the part where I need to use those assumptions...
I think once the base case is proven, we can do the following:
Case $t = t_1t_2$:
$$t\{x:=u\}\{y:=v\} \Longrightarrow t_1t_2\{x:=u\}\{y:=v\}
\Longrightarrow \\ t_1\{x:=u\}\{y:=v\} t_2\{x:=u\}\{y:=v\},$$
and we have just proven in the base case that
$t_1\{x:=u\}\{y:=v\} = t_1\{y:=v\}\{x:=u\{y:=v\}\}$  and  $t_2\{x:=u\}\{y:=v\} = t_2\{y:=v\}\{x:=u\{y:=v\}\}$,
so
\begin{align}
&t_1\{x:=u\}\{y:=v\} t_2\{x:=u\}\{y:=v\} \\ =& t_1\{y:=v\}\{x:=u\{y:=v\}\} t_2\{y:=v\}\{x:=u\{y:=v\}\} \\
= &t_1t_2\{x:=u\}\{y:=v\} \\ = &t_1t_2\{y:=v\}\{x:=u\{y:=v\}\}.
\end{align}
Now only case left is $t= \lambda m . t$.
So we have $(\lambda m . t)\{x:=u\}\{y:=v\}$,
which can be directly re-written as $\lambda m . t\{x:=u\}\{y:=v\}$, which is the base case again...
Could someone please help me finish this proof correctly and explain to me the right way to do it?


texts: computational complexity of a tree pruning algorithm

texts:
I've just designed an algorithm to prune a tree related to a particular fluid dynamics problem, and I need to determine its computational complexity; however, since I'm just a newcomer (from mechanical engineering) to the computational complexity theory, I'm not sure about the following reasoning:

The while loop iterates once, which means it continues till all elements of $L$ are examined. Moreover, the running time of each line as assumed to be 1.

AFAIK, the outer loop (line 1) counts $n$ assuming that $L$ has $n$ elements. Thus, the computational complexity is proportional to the input size. Moreover, each inner operation of the algorithm counts 1, so the overall computational complexity should be $O(n)$.

Can you please confirm the credibility of the reasoning above?


texts:
I have the following quotation from my compiler's course (in the context of graph coloring):

  Because it is slow, graph coloring tends to be used in batch
  compilers, while linear scan tends to be used in JIT compilers.

I couldn't find a clear definition online. So, what makes a compiler be a batch compiler?


texts:
I'm reading this chapter https://www.deeplearningbook.org/contents/mlp.html of the Deep Learning book, and on page 209, they have this equation (assume there is no regularizer and no bias parameter):
$$
\nabla_{W^{(k)}}J = gh^{(k-1)T}
$$
I'm not sure how this equation is derived, because
I thought based on the equation they give on page 203: $\nabla_xz = \left(\frac{\partial y}{\partial x}\right)^T\nabla_y z$, then should we have $\nabla_{W^{(k)}}J = \left(\frac{\partial a^{(k)}}{\partial W^{(k)}}\right)^T\nabla_{a^{(k)}} J = h^{(k-1)T}g$ (because $g=\nabla_{a^{(k)}}$ and $a^{(k)} = W^{(k)}h^{k-1}$)  instead?


texts: How should i guide a program to perform correct things?

texts:
I want to make a small model of A.I. which can learn itself. I am inspired by 1000+ monkey theorem which states that if 1000+ monkey bangs a keyboard for enough long, then they will eventually produce a Shakespeare's play. So, if you give a banana to one monkey when he produce a correct word, then he would eventually learn to do correct things. I think it is related to neural network.

So, practically i want to start with basic alphabets and digits and then my program would permutate and combine those to form words. Now, if the words they form matches with those in English Dictionary, i want to reward the program. However i couldn't think of any possible approach to this. How could this be implemented?


texts: Why when I unchecked DMA in Windows 7, the CPU usage was still very low?

texts:
I am studying about PIO mode and DMA mode for accessing IO devices, and based on what I have read, in PIO mode the data transfer have to go through the CPU.

So I have unchecked DMA in Windows 7 (which I guess will enable PIO mode):

And I copied and pasted a large file to see the CPU usage, and the CPU usage was still very law (about 5%). Shouldn't PIO mode exhaust the CPU?


texts: Optimization in multivalued logic. Optimal strings with given patterns

texts:
This question comes from an application in multivalued logic.

Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the letters with one of the indices. Examples are the following:

$$A_1 \\ B_4 \\ C_3 \\ ... $$

Suppose, additionally, that there is a total binary relation $\mathcal{R}$ on items $*_i <= *_j$ for each pair $ i, j \in \{ 1,..., 5 \} $ where $*$ denotes one of the letters $A,B$ and $C$. The relation is reflexive and transitive.

Consider a set of strings of length $5$ freely generated by the alphabet $A, B, C, ...$ disregarding ordering. Examples are the following:

$$ AABBC \\ AAAAB \\ AABCC \\ ... $$

Since order doesn't count, a string $AABBC$ is the same as $ABBAC$.

Let's call such strings templates. The templates can be "filled in" with the indices to form tuples of items using the following rules:

R1: there may be no repetitions of indices disregarding the letter type, e.g.

$$A_1, A_1, B_2, C_3, C_4$$

and

$$A_1, A_2, B_2, C_1, C_4$$

are both forbidden since the index $1$ is used two times.

R2: ordering in a tuple does not count, e. g.

$$\left( A_3 A_2 B_1 B_4 C_5 \right)$$

is the same as

$$\left( A_2 A_3 B_1 B_4 C_5 \right)$$

One can think of such "filling in" the templates as filling in a truth table with several logical levels in general.

Let us denote the set of all freely generated strings of length $5$ from the $A,B$ and $C$ by $\mathbb{Tmp}$. Let $\mathbb{Tpl}$ denote the set of all tuples generated by index assignments according to the rules R1 and R2. We can define a mapping $U:\mathbb{Tpl} \mapsto \mathbb{Tmp}$ which removes the indices from a tuple and gives its underlying template. For example:

$$ U \left( A_2 A_3 B_1 B_4 C_5 \right) = AABBC  $$

We say that a tuple $T$ satisfies the template $t$ if $U(T) = t$. We say that $T$ satisfies a set of templates $\tau = \left(t_1, t_2, ..., t_l \right)$ if there exists a template $t_i \in \tau$ for some $i \in \left( 1,2,...,l \right)$ s. t. $U(T) = t_i$.

Suppose, that we are given a set of templates $\tau$ and a total binary relation $\mathcal{R}$ on items.

What is the greatest item (greatest in the sense of the binary relation $\mathcal{R}$) of all the least items of all the tuples satisfying the templates $\tau$. In other words, what is the maximin item of the tuples?

The bruteforce algorithm is evident: take a template, build all the corresponding tuples, compare elements in each tuple and find the least, compare all the outcomes of the previous step, take the greatest. I am sure this is an $NP$-complete problem if the underlying truth table is irreducible.

What if we order all the items to obtain a sequence like this:

$$ C_2 <= B_4 <= C_1 <= C_5 <= B_1 <= A_2 <= C_3 <= A_3 <= B_3 <= C_4 <= A_4 <= A_5 <= B_5 <= A_1 <= B_2$$

Let's call this sequence $S$.

Can it simplify the problem by any chance?

For instance, consider the templates:

$$\tau = \left( AAAAB, AAABB, AAABC \right)$$

Can there be an algorithm more effective than the bruteforce? I was thinking in the following way: one can start in the sequence $S$ form left to right and "drop" items until there is no more letters to drop (otherwise, the templates are violated) or if the indexing requirement is violated.

Example of such a procedure goes like this:

drop $C_2$, drop $B_4$, drop $C_1$, drop $C_5$, drop $B_1$, drop $A_2$, drop $C_3$, drop $A_3$, $B_3$ must be picked

So no tuple may contain an item greater than $B_3$.

It seems to offer a minor complexity reduction and only for simple templates. For more complex ones, there are subtleties which I won't discuss here. But I am suspicious that there is a fundamental limitation in this problem which makes every algorithm not really better than the bruteforce.


texts: Classification of intractable/tractable satisfiability problem variants

texts:
Recently I found in a paper [1] a special symmetric version of SAT called the 2/2/4-SAT. But there are many $\text{NP}$-complete variants out there, for example: MONOTONE NAE-3SAT, MONOTONE 1-IN-3-SAT, ...

Some other variants are tractable: $2$-$\text{SAT}$, Planar-NAE-$\text{SAT}$, ...

Are there survey papers (or web pages) that classify all the (weird) $\text{SAT}$ variants that have been proved to be $\text{NP}$-complete (or in $\text{P}$) ?

Finding a shortest solution for the $N$x$N$ extension of the 15-Puzzle is intractable by D. Ratner and M. Warmuth (1986)


texts: Find a straight line to divide two convex polygons by equal area

texts:
Suppose, we have two non-overlapping convex polygons $A$ and $B$. How can we draw one straight line which divides $A$ into two parts of equal area and also divides $B$ into two equal area parts?
Also, can we do this in complexity $O(n^2)$ or better? ($n = |A| + |B|$)


texts: algorithm analysis - complex dependant nested loop

texts:
First of all, I know there are many questions like this on the site. But I think this case is a bit different.

Consider the following code:

int i, j, k;

for (i = 1; i <= n; i++){
    for (j = 1; j <= (n-i); j++) {
        System.out.print(" ");
    }

    for (k = 1; k <= (i-j); k++) {
        System.out.print(i);
    }

    System.out.println();
}

What would be the time complexity of this code? It seems like O(n^2) to me but I can't justify it properly.

How our professor told us to compute complexity is just by adding all the summations together from every line.

$$
(n+1) + \sum_{j=1}^{N-i} + \sum_{j=1}^{N-i} + \sum_{k=1}^{i-j} + \sum_{k=1}^{i-j} + n
$$

However, I've never seen examples with summations like $\sum_{j=1}^{N-i}$, It's always either $\sum_{j=1}^{N-1}$ or some constant number being subtracted from N, which is easier to sum. So, How would I solve this? And is it O(n^2)?


texts: calculating a shortest path in a table structure that changes in real time

texts:
I have a table that looks like this

In table NPC - are AI like characters that move from one point to another. Player - a character that is controlled by the user.

In any moment the player character might move to any cell of the table. But NPC has a particular goal cell that they should reach while moving. For example, blue NPC needs to read blue cell.

Other NPC are also moving. My goal is to write an algorithm that would allow NPC to reach the cell using the shortest path. As far as I understand it is a typical shortest path problem.

My question is - is there some algorithm that particularly optimized to handle such workflows, or any algorithms will suffice - just with recalculating the path after each move?


texts: How "meaningful" is Turing test? Are there better measures?

texts:
How "meaningful" is Turing test?

Because even though it's sometimes presented as a "scientific" way of classifying the goodness of AI, I do view it as a sort of naive, left-handed way for defining or measuring computer intelligence.

Because there are many more aspects to computer intelligence than mere "whether it can trick some people into believing that they talk with a human". Sure if the computer can answer any question similarly to how a humans expert would, then that would be pretty "hard", but computer intelligence is not there yet and it's unsure, whether it'll ever be due to the long-known differences between formal and informal semantics. It could be just a problem of inhuman system design capability. That is, no-one can ever in practice develop a computer program that's that good. It would just be too large.

Nowadays intelligence of computer programs could be measured by e.g. quantities of statements that they can evalute. That is, just the number of possibilities that they're able to process. Because even the goal of the Turing test would be a computer program with large enough database and large enough semantic analyzer and reasoner.

So, are there better measures?


texts: Choose m points out of n that form the polytope with the maximum volume in hyperspace

texts: Let's say I have a set $A$ of $n$ points represented by real vectors of length $l$. What type of algorithm would I use to find the subset $B$ of $m$ ($m$ is arbitrary, to be chosen) points that maximizes the volume of the polytope with vertices defined by $B$?


texts: $\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

texts:
The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al.

In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$ contains a pointer to the block of storage representing the table. The field $num[T]$ contains the number of items in the table, and the field $size[T]$ is the total number of slots in the table. Initially, the table is empty : $num[T] = size[T] = 0$.

$\text{Table-Insert(T,x)}$
$1\quad \text{if $size[T]=0$}$
$2\quad\quad \text{then allocate $table[T]$ with $1$ slot}$
$3\quad\quad size[T] \leftarrow 1$
$4\quad\text{if } num[T] =size[T]$
$5\quad\quad\text{then allocate $new{\text{-}}table$ with $2 \cdot size[T]$ slots}$
$6\quad\quad\quad\text{insert all items in $table[T]$ into $new{\text{-}}table$}$
$7\quad\quad\quad\text{free $table[T]$}$
$8\quad\quad\quad table[T] \leftarrow new{\text{-}}table$
$9\quad\quad\quad size[T] \leftarrow 2 \cdot size[T]$
$10\quad \text{insert $x$ into $table[T]$}$
$11\quad num[T] \leftarrow num[T] + 1$

For the amortized analysis for the a sequence of $n$ $\text{Table-Insert}$ the potential function which they choose is as follows,

$$\Phi(T) = 2.num[T]-size[T]$$

To analyze the amortized cost of the $i$th $\text{Table-Insert}$ operation, we let $num_i$ denote the number of items stored in the table after the $i$ th operation, $size_i$ denote the total size of the table after the $i$ th operation, and $\Phi_i$ denote the potential after the $i$th operation.
Initially, we have $num_0 = 0, size_0 = 0$, and $\Phi_0  = 0$.
If the $i$ th Table-Insert operation does not trigger an expansion, then we have $size_i = size_{i-i}$ and $num_i=num_{i-1}+1$, the amortized cost of the operation is $\widehat{c_i}$ is the amortized cost and $c_i$ is the total cost.

$$\widehat{c_i}=c_i+\Phi_i- \Phi_{i-1} = 3 \text{ (details not shown)}$$

If the $i$ th operation does trigger an expansion, then we have $size_i = 2 . size_{i-1}$ and $size_{i-1} = num_{i-1} = num_i —1$,so again,

$$\widehat{c_i}=c_i+\Phi_i- \Phi_{i-1} = 3 \text{ (details not shown)}$$

Now the problem is that they do not make calculations for $\widehat{c_1}$, the situation for the first insertion of an element in the table (line 1,2,3,10,11 of code only gets executed).
In that situation, the cost $c_1=1$, $\Phi_0=0$ and $num_1=size_1=1 \implies \Phi_1 = 2.1-1 =1$
We see that $\Phi_1=1 \tag 1$
So, $$\widehat{c_1}=c_1+\Phi_1-\Phi_0=2$$
But the text says that the amortized cost is $3$, (I feel they should have said the amortized cost is at most $3$, from what I can understand)
Moreover in the plot below,

The text represents graphically the $\Phi_1=2$ which sort of contradicts $(1)$, but as per the graph if we assume $\Phi_1=2$ then $\widehat{c_i}=3, \forall i$
I do not quite get where I am making the mistaken.


texts: Check if graph is regular given adjacency matrix

texts:
I have the following problem:

Write a function
whose input is an adjacency matrix A of a graph G. The function returns true
if G is a regular graph and false otherwise.

I understand that a graph is regular if the degrees of all the vertices are the same.
Therefore, I have written the following code which calculates the amount of degrees for each column:
def sumColumns(A):
  columns = []
  for i in range(0, len(A[0])):
    total = 0
    for j in range(0, len(A)):
      total += A[j][i]
    if total > 0:
      columns.append(total)
  return columns

def isRegularGraph(A):

  # Get list of degrees
  cd = sumColumns(A)

  if not len(cd) > 0 or  cd[0] != cd[len(cd) - 1]:
    return False

  # Do comparisons from i to i - 1
  for i in range(0, len(cd) - 1):
    if cd[i] != cd[i + 1]:
      return False
  return True

My question is, do I also need to check row wise if the number of degrees are the same column wise?
Is there a better algorithm to do this?


texts: Is a single string enough to prove regular expressions inequivalent?

texts:
Which of the following regular expressions generate a language that is different from the rest?

  (a+b)$^*$a(a+b)$^*$(a+b)$^*$
  b$^*$ab$^*$a(a+b)$^*$
  (a+b)$^*$ab$^*$ab$^*$
  b$^*$ a(a+b)$^*$ab$^*$

RE 1 generates a language that contains the string 'a' which no other language among 2,3,4 contains, so can I say this language is different from all others?  Does it suffice to show that a single string is not present in the language and hence its different from the rest?


texts: Cover k edges to minimize the length of the longest uncovered path in a tree

texts:
You are given a tree $G\langle V, E\rangle$ and an integer $k$. The goal is to cover $k$ edges of the graph, to minimize the length of the longest uncovered path in the tree (and to return this path's length)
Constrains: $O(n\log n)$ time and $O(n)$ space.

Now, the scheme of the algorithm is kinda obvious (from the given constrains). We need to priorities the edges and pick the highest $k$-edges (technically, we throw all edges to a priority queue and pick the first $k$)
So, I think, the keys should tell us how centric the edge is.
My first attempt was BFSing the graph from some node and BFSing again from the most distant node of the first scan.
Each node will get two values: distance from the first starting node and distance from the second starting node.
Though, I'm not sure how well this method grasp the notion of centric.
I'd be glad to hear your thoughts about the current idea or your own ideas.


texts: Language of balanced parentheses; Biconditional proof about parentheses

texts:
Let L be language of balanced parentheses.

(a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L.

(b) Prove If w is in L, then there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s.

After much thought, I don't seek what I'm supposed to be doing. All I know is that I'm supposed to be using induction.

Here is the grammar that generates L: $S\to SS|(S)|\epsilon$


texts:
I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct?

If I want to search for an element 2, it will make 2 comparisons. If I want to search for an element 22, it will also make 2 comparisons. But according to formula Θ(lg n), with n=2, it should make only one comparison in worst case. I'm not able to connect these 2 facts. Please help me. (For any even number of elements, I'm not able to draw tree. Because at some point, left side has one node and right side has 2 nodes)


texts: How can I find worst time complexity for a Regular Expression problem?

texts:
I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution?

One way is to perhaps use The Master Method for recursive functions, but that hides the "how?" part. I am trying to get much better at calculating complexities of algorithms on the fly.

Following is my solution for a problem which says that for an input text and a pattern, implement regular expression matching with support for '.' and '', where '.' matches a single character and '' matches none or more of the previous element.

var isMatch = function(text, pattern, mem=new Map()) {
    let key = text + '__' + pattern, pLen = pattern.length,
        tLen = text.length, first_match;
    if (!mem.has(key)) {
        if (pLen === 0) {
            mem.set(key, tLen === 0);
            return tLen === 0;
        }
        first_match = (tLen !== 0 && (pattern[0] == text[0] ||
                       pattern[0] == '.'));
        if (pLen >= 2 && pattern[1] == '*'){
            mem.set(key, (isMatch(text, pattern.substring(2), mem) ||
                    (first_match && isMatch(text.substring(1), pattern, mem))));
        } else {
            mem.set(key, first_match && isMatch(text.substring(1),
                    pattern.substring(1), mem));
        }
    }
    return mem.get(key);
};

My crude analysis so far:

From what I see here is that recursive calls to isMatch are the main contributor to overall time complexity. (Assuming that Map used for cacheing doesn't have very expensive operations). One set of isMatch calls is being called by taking a substring of given patter while the other set of calls to isMatch is being done by substring of given text.

So overall complexity should be describable in terms of length of pattern  (p) and length of text (t) but I am not sure how to deduce the time complexity.


texts: Minimum changes to be made to get Max-flow between each pair of vertices in an undirected graph

texts:
I was asked the following problem in an interview:

Let M be a N X N matrix, such that:

M[i][j] >= 0; 1 <= i,j <= N and i != j

M[i][j] = 0; if i = j

M[i][j] = M[j][i]; 1 <= i,j <= N

We are allowed to increase any of the entry in M[i][j] by any positive number, that we can increase the value of any cell in M[i][j] as much as we want.

Let M' be the matrix obtained by changing some values in M and x be the sum of all the changes made in M.

The task is to obtain M' such that it represents a graph with N vertex and satisfies following two conditions:-

M'[i][j] = max flow between vertex i and j, since the graph is undirected, trivially M'[i][j] = M'[j][i].
x is minimized, that is sum of all the changes made in M to get M' is minimum.

consider for example,

M =
0 7 11 6
7 0 9 8
11 9 0 4
6 8 4 0

M'=
0 9 11 8
9 0 9 8
11 9 0 8
8 8 8 0

x = 16.

Here is how I approached the problem.

Assume that in M, M[i][j] refers to the weight between vertex i and j.
Try creating a Maximum Spanning Tree from the values in M[i][j](I used Kruskal's Algorithm).
Now, while adding an edge between some pair i and j in the Maximum ST, one of the two conditions may arise- either no path exists between i and j, in this case simply add this edge between them, since we have been adding edges in a non-increasing order(as we are creating a Maximum Spanning Tree) this will be a 'bottleneck-edge' in the path between i and j, and so according to the Ford Fulkerson's algorithm this is also the max flow between i and j, so no changes required to be made(i.e. nothing to increase here as the max-flow is equal to the initial value M[i][j]). The other case is when there already exists a path between i and j, and since we are adding edges in non-increasing fashion, the current flow between i and j will be greater than the value M[i][j], thus M[i][j] need to be incremented. This change will be equal to 2*(current_flow_between_i_and_j - M[i][j])(as both M[i][j] and M[j][i] need to be changed and by equal amount).

And my approach was actually giving correct answer to the example test cases given by the interviewer, but to my surprise the interviewer told me that my approach was wrong and won't always work. I even tried my approach on test cases made by myself, and it seems to work correctly(or atleast this what I think). Where am I wrong in my approach and what can be a correct solution?


texts: Simulating continuous time semi-Markov state machine and changing transition probability on the fly

texts:
The problem that I'm trying to solve (well, I think that I almost did, but need a review from someone more experienced) is about changing probability of the transition for semi-Markov state machine during simulation.

Let's assume that M=<S,T> defines machine with S states and T probabilistic transitions between states. Elements of T are triplets (s_out, s_in, lambda). So the probability of moving from state s_out to s_in is exponential and defined as exp(-lambda*t).

To simulate it I get random value from [0;1), transform it to exponential and save as next event. What happens is that after saving it but before invoking another event may occur (so it is not a pure Markov state machine) and change the lambda. So the event time should be recalculated.

The problem is that it cannot be just recalculated as such changes may occur quite frequently constantly shifting the event time to the future.

What I think is correct is to adjust recorded event time on ratio time_to_event_from_now * lambda_old / lambda_new. Does it sounds right to you? Maybe the problem description recalls the paper/book where this problem solved?


texts: Why is the object destructor paradigm in garbage collected languages pervasively absent?

texts:
Looking for insight into decisions around garbage collected language design. Perhaps a language expert could enlighten me? I come from a C++ background, so this area is baffling to me.

It seems nearly all modern garbage collected languages with OOPy object support like Ruby, Javascript/ES6/ES7, Actionscript, Lua, etc. completely omit the destructor/finalize paradigm. Python seems to be the only one with its class __del__() method. Why is this? Are there functional/theoretical limitations within languages with automatic garbage collection which prevent effective implementations of a destructor/finalize method on objects?

I find it extremely lacking that these languages consider memory as the only resource worth managing. What about sockets, file handles, application states? Without the ability to implement custom logic to clean up non-memory resources and states on object finalization, I'm required to litter my application with custom myObject.destroy() style calls, placing the cleanup logic outside my "class", breaking attempted encapsulation, and relegating my application to resource leaks due to human error rather than automatically being handled by the gc.

What are the language design decisions which lead to these languages not having any way to execute custom logic on object disposal? I have to imagine there is a good reason. I'd like to better understand the technical and theoretical decisions that resulted in these languages not having support for object destruction/finalization.

Update:

Perhaps a better way to phrase my question:

Why would a language have the built-in concept of object instances with class or class-like structures along with custom instantiation (constructors), yet completely omit the destruction/finalize functionality? Languages which offer automatic garbage collection seem to be prime candidates to support object destruction/finalization as they know with 100% certainty when an object is no longer in use. Yet most of those languages do not support it.

I don't think it's a case where the destructor may never get called, as that would be a core memory leak, which gcs are designed to avoid. I could see a possible argument being that the destructor/finalizer may not get called until some indeterminate time in the future, but that didn't stop Java or Python from supporting the functionality.

What are the core language design reasons to not support any form of object finalization?


texts: I have 10 million categorical variables (each variable has 3 categories). What is the best way to encode these 10 million variables to train a deep learning model on them? (If I use one hot encoding, then I will end up having 30 million variables. Also, embedding layer with one output makes no sense (it is similar to integer encoding and there is no order between these categories) and embedding layer with two outputs does not make that much difference. Usually, we use embedding layer when number of categories is a lot). Please give me your opinion.


texts: Counting solutions to system of linear equations modulo prime

texts: I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to calculate number of solutions of such systems when all pivots are non-zero? (i.e. one and more solutions)


texts: Fastest way to search a word in a word list?

texts:
I have a word list like "English Open Word List" used to create word games.
The list is in txt file with space between words, like;
aa
aah
aahed
.........and so on.
I want to search it while typing the letters in the word, like google suggestions in the search bar.
What is the fastest algorithm to do it? In any language?


texts: How do nondeterministic Turing machines compute general function problems?

texts:
(Hope this hasn't been asked before, but I didn't find anything.)

In my understanding, nondeterminism applies to decision problems only, due to the requirement of the existence of an accepting path. In Wikipedia, the class $NP$-easy is defined to be solvable in deterministic poltime, with access to an oracle for a decision problem in NP. So this seems to back my assumption.

My question is: Is there an accepted way to define a non-deterministic Turing machine to compute a general function problem? (And is it always by a detour over an oracle for a decision problem?)


texts: Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a problem known to be in NP had a polynomial time quantum solution, would that be enough to show that P=NP?


texts: Asymptotic bounds of the following operations

texts:
I have a very simple question about the best possible big-O bounds for the following data structure:
It starts out empty When you add an element, it is inserted, and the index it was at is associated with it. So if it was the first item inserted, it's index would be zero:
14 12 19 <- items
 0  1  2 <- associated indices

Now if I delete 12 in this instance, the indexes for the other items are updated like so:
14 19
 0  1

Adding another element, like 10:
14 19 10
 0  1  2

If I were to delete 14, the 19 and 10 have their indices decreased by one.
In addition to adding and removing elements, you must also be able to search for a specific element and it should tell you what the index of that element is.
What is the tightest possible asymptotic bounds for these methods? Obviously I could do O(n) for removing elements and make search and add O(1). However, I was able to use a Fenwick tree to get O(log(n)) on add, search, and remove. Is it possible to do better than this?


texts: What kind of language uses an infinite alphabet?

texts: Kind of what it says on the tin. Let's say I have a countably infinite alphabet $A$ and a "language" $L = \{s_1s_2 | s_1,s_2 \in A\}$ (i.e. all possible strings of length 2). Now, my question is this: does it even make sense to think of this in terms of formal languages? Is there some construct akin to a state machine that I can use to model such a thing? And do any of the above answers change if $A$ is uncountable?


texts: Algorithm to find a simple path with maximum weight less than a constant in DAG

texts:
Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should not exceed a given constant $K$.

Perhaps my question is elementary but I cannot find any solution. Indeed, it is well known that finding a simple path with maximum weight in $G$ is polynomial, but by adding the fact that this total weight should not exceed a given constant $K$, will the problem remain polynomial? because we need to keep at each node the set of path lengths that can be reached by the next vertices.


texts: use of unconditional transfer of control instruction

texts: I did not understand why unconditional transfer of control instruction is used in cpu.So if we already know we have to jump to an instruction and skip  some instruction irrespective of any condition then why do we not avoid writing those instruction as they will not be executed and replace them with instruction that will be executed after jump instruction


texts: Graph coloring decision problem NP-complete

texts:
Given a graph $G = (V, E)$ and a natural number $k$, consider the problem of determining whether there is a way to color the vertices with two colors in such a way that at least $k$ edges are polychromatic.
Prove that this problem is NP-complete.

I thought about reducing it to the 3-colorability problem, but I can't figure out a possible transformation that would work.
Any leads?


texts: Is there a space-filling curve with constant-time indexing?

texts:
The Hilbert curve and other space-filling curves I've read about seem to have mapping operations from 1-D index to N-dimensional coordinates that are efficient, but amount to a log-ish tree search IIUC.

Are there any space-filling curves that have constant-time conversion from 1-D to N-D space (maybe relying on constant time integer arithmetic)? Is this an impossible requirement?


texts: How Can I Recognize When to Use ε-Transitions in an NFA?

texts:
I am learning about finite automata for the first time.  I am having trouble understanding the purpose of ε-transitions in an NFA, which seem to be crucial to counting the number of states in an NFA and therefore an equivalent DFA.

Here is an example question that confuses me: What is the minimum number of states a DFA recognizing the language of a(bc)*d can have?

To answer this question, I first drew this NFA (dashed line indicates acceptance):

Because I think the above NFA is already a DFA, I thought the answer was "5".

However, the correct NFA and equivalent DFA look like this:

Which means the answer is "4".  I understand why these are correct.  But, I have some questions:

1) Is my original drawing actually an NFA?  If not, why?

2) If the original drawing is an NFA, does it describe the language a(bc)*d?  If not, why?

3) If the original drawing is an NFA that describes the language a(bc)*d, is it also a DFA?  If not, why?

4) If the original drawing is an NFA and DFA that describes the language a(bc)*d, why should I have known to draw the NFA with ε-transitions instead?


texts: "Process functions" in iterative and recursive depth-first search

texts:
I was reading The Algorithm Design Manual by Steven Skiena, and I noticed his use of "process functions" in depth-first search and breadth-first search. Consider the following pseudocode for depth-first search:

DFS(G,u)
    state[u] = "discovered"
    process_vertex_early(u)
    entry[u] = time
    time = time + 1
    for every vertex v adjacent to u
        if state[v] = "undiscovered"
            parent[v] = u
            process_edge(u,v)
            DFS(G,v)
        else if state[v] != "processed" or G is directed
            process_edge(u,v)
    state[u] = "processed"
    exit[u] = time
    process_vertex_late(u)
    time = time + 1

Notice the use of the process_vertex_early, process_edge, and process_vertex_late functions.

I am attempting to implement an iterative version of depth-first search to avoid a stack overflow with larger graphs. Here is the pseudocode for my attempt:

DFS(G)
    mark every vertex in G as "undiscovered"
    mark the start and finish time for every vertex in G as (0, 0)
    time = 0
    for every vertex vrtx in G
        create empty stack S
        if vrtx is "undiscovered"
            S.push(vrtx)
        while S is not empty
            time = time + 1
            u = S.top
            if u is "undiscovered"
                u.start_time = time
                mark u as "discovered"
                process_vertex_early(u)
            done = true
            for every vertex v adjacent to u
                if v is "undiscovered"
                    done = false
                    v.parent = u
                    process_edge(u,v)
                    S.push(v)
                else if v is not "processed" or G is directed
                    process_edge(u,v)
            if done
                S.pop
                mark u as "processed"
                u.finish_time = time
                process_vertex_late(orig)

I ran both versions of the code for a sample graph of 10 vertices and generated the following data:

Iterative data:
vertex  early   edge    late    s_time  f_time  parent
0       1       1       1       1       18      -1
1       1       1       1       14      14      5
2       1       1       1       13      13      5
3       1       3       1       5       11      7
4       1       3       1       2       17      0
5       1       6       1       3       16      4
6       1       3       1       6       10      3
7       1       3       1       4       12      5
8       1       3       2       8       8       9
9       1       3       1       7       9       6

Recursive data:
vertex  early   edge    late    s_time  f_time  parent
0       1       1       1       1       20      -1
1       1       1       1       14      15      5
2       1       1       1       16      17      5
3       1       2       1       7       10      6
4       1       2       1       2       19      0
5       1       4       1       3       18      4
6       1       2       1       6       11      9
7       1       2       1       8       9       3
8       1       2       1       4       13      5
9       1       2       1       5       12      8

Here is the adjacency list for the graph I used:

0 : 4
1 : 5
2 : 5
3 : 6,7
4 : 0,5
5 : 1,2,4,7,8
6 : 3,9
7 : 3,5
8 : 5,9
9 : 6,8

I know that the vertices will be visited in different orders for the recursive and iterative implementations and that neither order is right or wrong, which is why the values for s_time, f_time and parent are different. The early and late columns represent the number of times each function was called for each vertex, while the edge column represents the number of times the process_edge function was called for each vertex as the u vertex. I feel like these values should be the same for both implementations or at least more similar than they are.

My question is: have I preserved the semantics of the original algorithm with my iterative translation? What changes, if any, should I make?


texts: Nearest Neighbor Search in Spherical Coordinates

texts:
I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates. Then given these points in their spherical coordinates how can I go about determining their NN. I need an algorithm that is efficient (relatively) and more importantly accurate.

EDIT: For sake of argument and for the philosophical point let's accept the 'loss of information' to quickly summarize my research in astrophysics does not allow me to simply convert to Cartesian coordinates and use a nearest neighbor algorithm due to the universe expanding and me dealing with something called redshift. TLDR: I cannot convert to cartesian and must use an algorithm in spherical coordinates for nearest neighbor.


texts:
Can addition (or subtraction)  of polynomials of degree $< n$ be done in constant time ?

I am quite new to algorithms. I thought about using sorted arrays for storing the coefficients. But the addition of two sorted arrays appears to be $\in O(n)$. However, I am not convinced that this is the best solution. Could someone please help clarify?


texts:
Is there an algorithm that could check whether it is possible to win in the current situation in solitaire? That is, can we remove all cards from the table in a certain number of moves?
Description of the game:
Two decks of cards (36 pieces each) are connected and shuffled, and then they are laid out in 8 piles of 9 cards each. Possible work only with the top cards in each of the piles, namely, transfer one or several consecutive cards of a lower value to a card of a larger one (suits are not taken into account). If there are 9 cards in one of the piles in the correct order (ace-king-queen-jack-10-9-8-7-6), then this set is removed. If all the cards are removed from one pile, it can still be used and any card can be placed on top


texts: How to identify periodic pattern recognition

texts:
I'm dealing with a time series that consists of one year's data of the result of some measurement. The time index is in second and the result of the measurement is a non-negative integer.

Interestly, after some tweaks & transformation & plot of the original data, I found that in some days the data shows a periodic pattern within that each day.

For an instance, I found that on one day throughout the whole day a specific measurement (integer) is recorded every 1 minute. The pattern is obvious because the integers are almost the same and spaced in nearly 1 minute interval while others are kind of random.

Whilst it is relatively easy to spot the pattern I found it hard to precisely state it. The main issues here are that

The "specific" integers are slightly varying, say the majority of the integers are 1700, but occasionally I can find 1800, 1600, or 1701, etc;
The "specific" integers are different across days and sometimes even different within one day.
The interval is not necessarily 1 minute and furthermore, it is not the same even within a single day. Say, in the morning the pattern is spaced in 58 second interval whilst in the afternoon, it is in 61 second interval;
The interval is not very precise either. Say, in the first 2 hours patterns are spaced in 60 second interval but then a 61-second interval occurrs and then after that going back to the 60-second interval again;

Because the data is huge and so I want to see if I can programmatically identify the patterns (if it exists for a day) and also retrieve those "specific" integers in the pattern.

Anyone suggest an approach? Or any guidance?

Thanks.


texts: Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time

texts:
I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. More precisely, the algorithm should find an upper and a lower bound on the chromatic number. The closer the bounds are to the chromatic number, the better.
If it isn't clear, the input to the algorithm is a graph. The exact representation of a graph isn't fixed (that is, I will switch data structures if it makes sense).
I already know about Brooks' theorem, which gives an upper bound in linear time and constant space, but I'm hoping for something stronger.
Related Mathoverflow question: https://mathoverflow.net/questions/33812/lower-bounds-for-chromatic-number-of-a-graph


texts:
How do you set the number of words in the visual dictionary?

I tried to understand the different steps to obtain the visual dictionary first:

Feature detection:

Examines every pixel to see if there is a feature present at that pixel.

Feature description:

Each image is abstracted by several local patches
Feature representation methods deal with how to represent the patches as numerical vectors.

Codebook generation:

Convert vector-represented patches to "codewords"
Codewords are then defined as the centers of the learned clusters
by using K means and/or the Euclidean distance will be computed.

I am assuming that the Bag of Words is used for image classification, but I don't really understand how you set the number of words in the visual dictionary. I would really appreciate the help or please correct me if I was wrong in the steps of obtaining the visual dictionary!


texts: If A is poly-time reducible to B, is B poly-time reducible to A?

texts:
Basically, is the following statement true?

  $A \leq_p B$ $\rightarrow$ $B \leq_p A$


texts: How to evaluate dynamical conditioning/pseudo code

texts:
I am having a hard time even to formulate my question, so here it is:

I have an application that the user can go in and define on a webpage the logic one wants to evaluate for the student to comply with:

  Student must take classes (MATH111 OR (MATH101 AND MATH103))

I have an array of all its enrolled classes like:

  [MATH101,MATH102,MATH123,MATH444]

How do I evaluate my array on that expression to check if the students satisfies the AND/OR clause?


texts: Matrix for modular exponentiation in Shor's algorithm

texts: I'm trying to simulate Shor's algorithm with a model using vectors for quantum registers and matrices for quantum gates, however I'm stuck at the modular exponentiation bit of Shor's algorithm, having no idea how to build the corresponding matrix (unlike Hadamard and QFT). How can I build said matrix?


texts: O(n) sorting array by value - get indexes

texts:
I am in search of a linear-time sorting algorithm that is capable of returning an array B of indices A, sorted on the value of the corresponding element of A.

For example:

Input = [2, 6, 8, 9, 1, 7, 0]
Output = [6, 4, 0, 1, 5, 2, 3]

Things I have tried:

Storing the index and value in one number, using something like this:

long number = value << 16 | index;

And then applying Countingsort. This however did not work since the JVM couldn't handle an array of ~ 2 million elements. (= the highest "number" value).

The logical solution to that problem was put everything in a map, but I was unsure whether it would still be linear..


texts: Given a Deterministic Finite Automata (DFA) $M_1$, does there always exist a Pushdown Automata (PDA) $M_2$ that accepts the same language as $M_1$?  I.e. can any DFA be simulated by a PDA?  Intuitively, it makes sense to me that a PDA is more powerful since it has an arbitrary amount of memory and can therefore accept more languages than a DFA, but how could this be formally proven?


texts: Merging and Unmerging Sets of Trees Efficiently

texts:
Background

Given multiple trees, I'd like to merge all of the them and be able to efficiently unmerge arbitrary trees in the set. For example, here are some JSON trees:

Tree 1:

{
  a: {
    b: 1
  },
  c: [{}],
  d: 3
}

Tree 2:

{
  a: {
    z: 1
  },
  c: [
    {
      x: 1
    },
    {
      x: 2
    }
  ],
  d: 4
}

merge(t1, t2) would yield:

{
  a: {
    b: 1
    z: 1
  },
  c: [
    {
      x: 1
    },
    {
      x: 2
    }
  ],
  d: 4
}

Note the overwrite of primitives (d).

Problem

I'd like to be able to merge some order set of trees like the above (the order is important because of the overwriting of primitives) AND be able to efficiently unmerge one of the trees.

Mathematically, I want two functions $merge$ and $unmerge$ such that the following holds true:

$$
unmerge(merge(t_1,...,t_n,...,t_p), t_n) = merge(t_1,...,t_{n-1},t_{n+1},...,t_p)
$$

where $p,n \in Z^+$ and $n \leq p$.

Simple solutions like "delete all of the nodes on $t_n$ from the merged tree" obviously doesn't work in many cases.

More robust solutions like creating immutable copies of the interim trees might would has you could take the cached tree $merge(t_1,...,t_{n-1})$ and then merge in the subsequent trees $t_{n+1},...,t_p$. However, in the worst-case ($n=1$) this is equivalent to just remerging the entire set; ideally, there would be some less computationally complex solution.

Would love any advice or pointers for further research. Thanks!


texts: Algorithm to match numbers with minimum number of moves

texts:
This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far.

Given a series of numbers, e.g.

[3, 1, 1, 1]

How would one most efficiently turn all of the numbers into the same number, with the minimum number of "moves"? By "move" is meant adding or removing one from a number.

In the above example, the most efficient moves would be:

[1, 1, 1, 1]

This would require 2 moves, reducing the first number twice.

I can't figure out the best way to find this out, given much larger arrays of hundreds of numbers.

I originally tried computing the rounded average number (sum of all divided by length), and then reducing them to the computed average, but the above example broke this, requiring 4 moves instead of 2.

I suppose I could figure:

The average,
The mode,
The median

and get the edit distance of each of them, choosing the minimum distance. However, I am not sure that this would be correct in every single instance. How can I know?


texts: How to check the existence of a split sandwich in polynomial time

texts:
I've been reading the Graph Sandwich Problems from Golumbic, Kaplan and Shamir paper and can't figure out the algorithm to check if a split sandwich exists. I'm assuming that I should not be searching for a clique or independent set before generating the set of equations but I'm really confused at that part.
My understanding was that I needed to create the set of equations without assign any value to the variables an then check if it was a satisfiable system. But that way I can have a satisfiable system even if I don't have a split sandwich.


texts: Every acyclic graph can be transformed structurally to a tree. Therefore, every node on odd numbered levels can be colored with color $X$ and every node on even numbered levels can be colored with color $Y$. Is the reasoning valid?


texts: Determining if we can balance these graph weights

texts:
Let $G$ be a complete directed graph with $n$ vertices. Each vertex $v$ has a weight $w(v)>0$, such that the sum of all vertex weights is $n$. We have that the edge $e$ from $u$ to $v$ has a weight $0 \leq w(e) \leq w(u)$.

We say that these weights can be balanced, if there exists a directed spanning tree, $T$, and function on the edges of $T$, $f$, where $0 \leq f(e)\leq w(e)$, such that for every vertex $v$, we have that $$w(v) + \sum_{e \in I_v} f(e) - \sum_{e \in O_v} f(e)=1$$ where $I_v$ is the set of all edges in $T$ going into $v$, and $O_v$ is the set of edges in $T$ going out from $v$.

Is determining whether the weights can be balanced a known problem? It sounds like a network flow problem, but I'm not too familiar. What's an algorithm which could solve this?


texts:
I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive be considered part of a regular set? Lets say I have that same set, but instead of being even, they are divisible by 5, would it still be a regular set?

I've been looking at this helpful guide I found online, but I'm still confused about what can be defined as a regular set.


texts: Number of "hamiltonian tours" from upper left to lower left corner of a grid graph?

texts:
I got the following as an interview question:

Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction.  This is the number of Hamiltonian paths from upper left to lower left: a path such that every vertex is visited only once, and (this follows from the first statement) such that each edge is used at most once.

The grid world is a 4x10 matrix (4 rows and 10 columns).

Is it really this hard?

Matrix method for counting Hamiltonian cycles

And:

Number of Hamiltonian Paths from Lower Left to Upper Right

These papers seem dated--94, 97--but are they really asking a question that qualifies for publishing in a combinatorical journal?

Then I ran into this:
SO question: number of Hamiltonian paths

And am thinking dynamic programming, or divide and conquer...but it is really not clear how one would go about doing this. Is there a way to solve this problem in reasonable time?


texts:
I'm reading through the paper Transactors: A Programming Model for Maintaining
Globally Consistent Distributed State in Unreliable
Environments by John Field and Carlos Varela.

I have basic knowledge about the lambda calculus (typed lambda calculus to be more precise) thanks to a class I took at my university.

However, I'm stuck finding out what the rule shown below actually means. I have looked through the Types and Programming Languages book by Benjamin Pierce but I can't seem to find an explanation.

Could somebody help me understand what rule pur7 means?


texts: What are the differences between computer vision and image processing? For example, in object recognition, what are the roles of computer vision and image processing?


texts: Integer knapsack problem with bounded weights

texts:
Is there any literature about the complexity of the integer knapsack problem with bounded weights? To make it clear, I want an optimal solution to the following problem:

$\max \sum_{i=1}^k c_i \cdot x_i$

$\sum_{i=1}^k w_i \cdot x_i \leq W$

$x_i \in \{0,\ldots,k_i\}$

where $k_i$ is an item-specific limit for the number of copies that can be taken of item $i$ and $w_i$ is integral but bounded by $k$.

I'm not sure whether it is NP-hard or not...in contrast to the "traditional" knapsack problem, it would be possible to iterate over $w_i$ here (in polynomial time), but not to iterate over the whole sum since the values $k_i$ are not bounded by a polynomial. On the other hand, I cannot imagine a reduction of an $NP$-hard problem. Any ideas?


texts: Size of address registers and data registers in relation with memory size

texts:
Suppose that a processor can address directly up to 4 Gigabyte main memory and can operate words with size 32 bit. Find how big should be the size of the "MAR" (memory address registers), "MDR" (memory data registers) and accumulator registers in this computer?

My answer: MDR is 32 bit wide since it exchanges data not only via the data bus but with the CPU data registers. How about MAR and accumulator? how are they related to the 4 gigabyte main memory?


texts:
Suppose that we have a family $F=\{a_1,\dots,a_s\}$ of sorted arrays
to merge. Our strategy is to choose two of them, say $a_i$ and $a_j$,
remove them from $F$, merge them and put the resulting array back into
$F$; we keep doing that until there is only one array in $F$. We will
use a greedy strategy: at each step, we choose $a_i$ of minimal length
in $F$, and $a_j$ of minimal length in $F-\{a_i\}$.

What data structure would you use to store $F$?

Obviously, I assumed F $F$ be an array of array as each element of F is an array of integers.

However, I think it is asking about Abstract Data Structures that were taught at a class. We are taught about Priority Queue ADT, Stack ADT, Queue ADT, and heap so far.

Can F be one of them? If so, please explain why F can be such structure.

Thank you,


texts: Spanning-Tree-Protocol and BFS? (Distributed Computing)

texts:
Given is graph with networks and bridges/switches. We know, the root
Bridge is the bridge with the minimal Bridge-ID. The connections between every bridge and network is 1.

In the lecture slides they calculated the "best"(shortest) path from one network to the root bridge. I assume they used BFS, because it would be the easiest way to calculate the shortest path, but if they used BFS, why is the algorithm called Spanning-Tree-Algorithm?


texts: Which priority queue implementations are stable?

texts:
I can't answer this question. It seems simple but I really don't know how to approach it.
Here it is:

A priority queue is said to be stable if deletions of items with equal priority value occur in the order in which they were inserted. Which of the following priority queue structures are stable:

linked lists ordered in increasing priority (key)
balanced search trees (e.g., 2-3 trees)
heaps
leftist heaps

Explain why, or give counter-examples.

I don't need a full solution just a way to approach this problem. I would prefer to solve it on my own.


texts: What is the worst case scenario for next fit bin packing?

texts:
So I know the Next Fit Bin Packing algorithm is bounded by two times the optimal solution for the problem, but I can not think of an order of arriving elements that actually takes twice the number of bins necessary.

Something like:

50 -> 25 -> 50 -> 25 -> 50 -> 25 -> 50 -> 25

would result in:

|25| |25| |25| |25|

|50| |50| |50| |50|

bins with next fit while the optimal solution would be:

|50| |50| |25 * 2|

|50| |50| |25 * 2|

Which is only one bin difference.
So what actually is the worst order of elements for the next fit bin packing algorithm?


texts: What are the definitions of syntax and semantics?

texts:
For a formal language $L \subseteq \Sigma^*$ over an alphabet
$\Sigma$. From https://proofwiki.org/wiki/Definition:Syntax

  The syntax of a formal language is its structure, and is specified by
  a formal grammar of the formal language.

From http://en.wikipedia.org/wiki/Syntax_%28logic%29

  In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning

How do you define the "structure" of a formal language,
and therefore define the syntax of a formal language? Ideally define
them formally or mathematically?
The syntax of a formal language should be defined formally, because it pertains to the formal language which is defined formally as a subset of $\Sigma^*$, right?
Raphael once said that the syntax of a formal language is
the language itself. Is it true?
From http://en.wikipedia.org/wiki/Syntax_%28logic%29

  Syntax is usually associated with the rules (or grammar) governing the composition of texts in a formal language that constitute the well-formed formulas of a formal system.

We shouldn't equate the two concepts: the syntax of a formal language, and a formal grammar of a formal language, should we?

Note that a formal language can have several formal grammars that all generate the language. When a formal language has multiple different formal grammars that generate it, is the syntax different for different grammar?

Also a formal language may not have a formal grammar that can generate it, and still syntax should make sense to such a formal language?

For a non-formal language $L'$  over an alphabet  $\Sigma$,

What are
the definitions of its syntax and its semantics, ideally
mathematically?
When defining its syntax, how do you distinguish what pertains to
the formal part of the language, and what is not?
Can its semantics be defined as a mapping $L' \to S$ where $S$ is some other
set?
Maybe, for example, when $L'$ is a programming language?
Maybe, for example, when $L'$ is a natural language, such as English?

Thanks and regards!


texts: Why whenever a caller or client modifies a library collection class, all iterators are made invalid?

texts: Whenever a caller or client modifies a library collection class, all iterators are made invalid (with the exception of the iterator through which the change was made, in the case of remove). Give a reason for this rule in the case of an array list (using a dynamically sized array, in which an iterator has a pointer to the array) and in the case of list (using linked list nodes, in which case the iterator points to one or more list nodes).


texts: Optimal pairing of $N$ points, lying on the circumference of a circle, by non-intersecting line segments

texts:
Good day.

Consider N points forming a circle (N is even and is between 1 and 200).

The task is to calculate the minimum cost of linking all 2 points (as pairs) without any lines intersecting.

Each point is given an ID. The cost to link 2 points a and b is (id(a)+id(b))²

Please note: a point can't be part of 2 pairs.

Example:
N=4

a=1, b=2, c=1, d=2

Cost=18

Here's how I approached the problem:

First we locate the point with the smallest id and the node with the greatest id value.
If one is odd and the other is even then we link them. Else, we locate the point with the second biggest id value and we link the located points.

The cost is calculated and saved, and the points are removed from our structure (C++ std::list for example) and the function is called recursively twice, each time with a subset of the current circle, left part and right part (2 new circles)

The base case for the recursive function is returning the square of the sum of 2 points if N=2

Thank you.


texts: 4 Vertex Cover Problem is not NP Complete why?

texts: With Given Graph $G$ why finding that $G$ has a vertex cover of at most $4$ is in $P$ and Not in NP Complete. it means there us poly-time algorithm for this problem !!?


texts: Can two free variables in lambda calculus have different values?

texts: I am studying lambda calculus for the first time and I was trying to do the reduction beta of the lambda term $(\lambda x.xy)y$. Can I assume that these two free variables $y$ are the same? Or do I need to rename the rightmost $y$?


texts: Equivalence of Context-Free-Grammar and Context-Free-Grammar in CNF

texts:
Given any Context-Free-Grammar, $G$, and another in Chomsky Normal Form, $G_c$, how can we check if both $G$ and $G_c$ generate the same language?

One of the trivial ways I know of is to convert $G$ into a CNF form. which motivates my second question,

Can two different Context-Free-Grammars in CNF, $G_c$ and $G_c^\prime$, generate the same language? (I would appreciate a proof of it)


texts: Is $\{a^mb^nc^{mn}\mid m>n\}$ a context-free language?

texts:
Been trying to figure it out for an hour myself and another hour looking around, I cannot find anything with the $c^{mn}$ part.

$$L=\{a^mb^nc^{mn}\mid m>n\}$$


texts: What is the O time complexity for this algorithm?

texts:
is the Big-O for this O(1) or some asymptotic like 1/n?

Saying that because if it defaults, the time limits at about 1000000 ns, but if it returns while in the loop, it is about a fraction of that. The time seems to increase very slightly as the inputs increase.

public static int[] call(int b, int c) {
    int[] f = new int[2];
    final double n = 1.13;

    for (int x = -100; x < 100; x++) {
        for (int y = -100; y < 100; y++) {
            if (((n+x)*(n+y)) == ((n*n)+(b*n)+c)) {
                f[0] = x;
                f[1] = y;
                return f;
            }
        }
    }
    return f;

    /* // timer method
     * long startTime = System.nanoTime() ;
     * call();
     * long endTime   = System.nanoTime() ;
     * long totalTime = endTime - startTime;
     * System.out.println(totalTime);
     *
     *      f(2, 1)   : 499284
     *      f(4, 4)   : 487452
     *      f(6, 9)   : 501479
     *      f(8, 7)   : 493296
     *      f(10, 21) : 500602
     *      f(12, 36) : 505862
     *
     */

}

Also, please ignore that the code is wonky.


texts: What kind of optimization problem this belongs to?

texts:
Supervised learning is: given $X$ and $Y$, we want to find a good predictive function $f$ such that $f(X)$ is "close" to $Y$. Examples include XGBoost (ensemble of decision trees), neural networks, $\ell_1$-regularized linear fit, etc.

In the problem I am encountering I have $X$. Each row of $X$ describes each day's scenario, for example, the financial market descriptors of that day. I don't have $Y$. $Y$ is the decision for each day, for example, whether I should buy/hold SP500. For each $Y$, I will have some scoring, say score(Y) system to describe whether my decision is good over a long period of time. Now, I want to find simple, robust $f$ such that $f(X)$ gets the low score. Of course, for arbitrarily complex $f(X)$, the score score(f(X)) can be very low but the higher complexity generally means worse model for the problem I am tackling on. So there should be some regularization parameter that I could tune to control the complexity of $f$. The $f$ can be anything, like supervised learning. It could be ensemble of decision trees (XGBoost, random forest, etc...), linear (L1-regularized fitting etc.). I am currently essentially hard coding my problem into a optimization problem to solve on. But I think there should be a field out there tackling such problems.

If so, what is this type of problems generally called. And what's the state of the art packages currently in python. Thank you.


texts: Is Halting problem only applicable to infinite languages

texts:
Is the halting problem, only applicable for infinite languages?

I assume that if the language is finite, then we can search over all words?


texts: Quick access to top element of subsets of elements

texts:
I have a set S of (key, value) pairs and a large number of subsets of S. I'm looking for a data structure that would efficiently execute the following operations :

Add a (key, value) pair to S and to a collection of subsets.
Delete a (key, value) pair from a collection of subsets containing this pair (not all of them).
Return the max value of a subset.

Right now my solution is to have, for every subset, a binary heap coupled with a hash table (so I can access the element I want to delete in constant time).

I wonder if there's a more efficient way to do this that would capitalize on the fact that these subsets have elements in common (so sorting them for every subset sounds like a bit of a waste).


texts: how to verify permutation generated in constant amortized time?

texts:
Here is an algorithm that generates the next permutation in lexicographic
order, changing the given permutation in-place:

Find the largest index k such that a[k] < a[k+1]. If no such index exists, exit (the permutation is the last permutation).
Find the largest index l such that a[k] < a[l].
Swap a[k] with a[l].
Reverse the sequence from a[k+1] up to and including the final element a[n].

Is the next permutation generated in constant amortized time and if yes, how to verify it?


texts: Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?

texts:
I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars.

However, I've encountered this statement from my notes:

  With $\epsilon$ productions in the grammar, we may have to look
  beyond the current non-terminal to what can come after it

In my opinion, this suggests that $FOLLOW$ is not necessary for $LL(1)$ grammars that have no $\epsilon$ transition. Am I wrong? And if I'm not, why is this the case?

Thanks


texts: Why do we study closure properties of formal languages?

texts: In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is important to study such properties?


texts: Why are syntax trees used in genetic programming?

texts:
Reading a course on genetic programming, the first chapter describes the syntax tree as the basic representation of programs in genetic programming.

What are the reasons leading to the choice of a syntax tree in genetic programming? Are there any particular assets in using this representation?


texts: Converting a Recurrence Relation to its Closed Form

texts:
I have a recurrence relation of the form given below (taken from Analysis of Algorithms - An Active Learning Approach by Jeffrey J. McConnell):

$T(n) = 2T(n - 2) - 15 $

$T(2) = T(1) = 40 $

I am asked to find a closed-form for the recurrence relation i.e. to remove the recursive nature of the equations.

Working:
My professor said it would be easier if you could see the patterns taking form if you expand the equations up to a few steps. So,

$T(n) = 2T(n - 2) - 15 $

$= 2(2T(n - 4) - 15) - 15$

$= 4T(n - 4) - 2\times 15 - 15 $

$ = 4(2T(n - 6) - 15) - 2\times15 - 15$

$ = 8T(n - 6) - 4 \times 15 - 2\times15 - 15$

I observe that the coefficient of $T$ in each step is a power of 2. The size of the problem during each recursive call decreases by 2. Also, there is a -15 term multiplied by the next power of 2.

But I am stuck here and do not know how to proceed further i.e. to obtain a closed-form. The book says to consider cases when $n$ is odd and even. But I do not get it at all. Any help would be appreciated.

Note: The material hasn't covered advanced topics like solving recurrence relations yet.


texts: Help me resolve my doubts about infinities, exemplified by an example of non DFA acceptable language

texts:
I have always had a hard time making sense of infinities.

Example: the language $L = \{ \epsilon , 01, 0011, 000111, 00001111, ... \}$ is not DFA acceptable because a machine capable of accepting it would require an infinite amount of states.

I can draw a DFA with ellipses in the middle to represent it's expansion.  I can prove that:

For all strings x in L, using a machine M = mentioned DFA, under some finite expansion, I can accept all strings y in L, such that $|y| \leq |x|$ and such that M has $|x| + 2$ states and such that all strings in compliment(L) are not accepted by M.

All of those machines are finite.

The problem that prevents me from making the leap to claim that L is then DFA acceptable, is that I need to prove that there exists a largest string in L, but there is no largest string in L.

Anyways, I know this sounds stupid because knowing what is proven about convergence and divergence, I should be able to make mathematical sense of this.  The problem is that no matter how much I know about infinity, I still do not think that what is said about convergence and divergence seems logical.  I always have this feeling that something is wrong.

So I guess I just wonder how I can look at it so that it makes more sense.

In short, when a DFA needs a state for each character of a string in order to accept the string, and the language is an infinite set of strings whose enumeration could be represented as a sequence of strings increasing in length, how is it that a DFA needs an infinite amount of states to accept all of those strings, given each string is finite?


texts: What is the common way to approximate contour with quad?

texts: I'm trying to find quads on stream from my webcam. cv2.HoughLinesP sometimes returns more lines then needed. How can I approximate them to contour of exactly 4 points that fits returned result best? I'd like to know the most common way to do this, it looks like an obvious question and I don't want to reinvent the wheel.


texts: Can we have a general function of any function this way?

texts:
Lets say we need a function to add two numbers and another function to multiply two numbers.

To take a trivial example, consider the function $F(a, b, c, d) = a \cdot (c+d) + b \cdot (c\cdot d)$
If $a=1$ and $b=0$, then $F$ adds $c$ and $d$.  If $a=0$ and $b=1$, then $F$ multiplies $c$ and $d$.

So to evaluate both add and mult I can have only one function $F$ with variable inputs.

Can we have a general function that can evaluate any arbitrary function ? of course with an upper bound on the complexity ? If yes how do we prove in theory that such a general function is possible ? What is this called in theory ?


texts:
In preparation for an exam, I've come upon the following problem.  Given the constructors :

[]: -> T LIST

[a]:T-> T LIST

cons(a,x) : T x T LIST -> T LIST ( a is added to the beginning of the list)

And the functions :

size(l) : T LIST -> N (number of elements in l)

reverse(l): T LIST -> T LIST ( reverses the order ofthe elements in the list)

unique(l) : T LIST -> T LIST - returns a list of the elements in 'l' that only appear once

repeated(l) : T LIST -> T LIST - returns a list of the elements in 'l' that appear more than once

max?(e,l) : T x T LIST -> Bool - returns true if 'e' is the maximum element in the list, false otherwise

Prove by structural induction that :

max?(e, l) -> max?(e, unique(reverse(l))) || max?(e, repeated(reverse(l)))

I've managed to simplify this to :

max?(e, l) -> max?(e, unique(l)) || max?(e, repeated(l))

But I don't see how to proceed towards proving what is asked...

Used definitions of functions:

    unique([]) = []
    unique([e]) = [e]
    unique(cons(e, L)) = cons(e, unique(L)), if member(e, L) = false unique(cons(e, L)) = unique(L), if member(e, L) = true

    repeated([]) = []
    repeated([e]) = [e]
    repeated(cons(e, L)) = cons(e, repeated(L)), if member(e, L) = true unique(cons(e, L)) = unique(L), if member(e, L) = false

    reverse([]) = []
    reverse([e]) = [e]
    reverse(cons(e, L)) = append(reverse(L), [e])

    also,
    member : Element x List -> Bool
    member(e, []) = false
    member(e, [a]) = (e == a) (true, if a is equal to e; false, if a isn't equal to e)
    member(e, cons(a, L)) = (e == a) V member(e, L) (V is logical disjunction)

    append : List x List -> List
    append([], L) = L
    append([e], L) = cons(e, L)
    append(cons(e, L1), L2) = cons(e, append(L1, L2))


texts: How does casting really work for primitive data types?

texts:
I have written the following C code which purpose it is to flip an unsigned number in binary representation and give back an unsigned number:

long flippingBits(long n) {
    return (unsigned)(~n);
}

int main(){
    long a = flippingBits(someNumber);
    ...
}

This code does work fine. What about this code?

unsigned long flippingBits(long n) {
    return (~n);
}

int main(){
    unsigned long a = flippingBits(someNumber);
    ...
}

This code indeed prints out negative numbers. WTF. This is beyond my intuition. So is there an (architectural) way, to explain this phenomenon? How does the casting of primitive data types work?


texts: Naming for (memory near optimal) datastructres

texts:
Assume that we wish to solve some problem that has a information theoretic memory lower bound of $\mathcal B$ bits.
In computer science, there are a few classes for data structures which are close to the memory lower bound of the problem that they solve:

Compact data structure is one that uses $O(\mathcal B)$ bits (i.e., it is asymptotically optimal).
Succinct data structure uses $\mathcal B(1+o(1))$ bits (e.g. $\mathcal B + 7{\mathcal B \over \log \mathcal B}$).
Implicit data structure uses $\mathcal B+O(1)$ bits (e.g., $\mathcal B + 38$).

I couldn't find a name for the following classes, and wondering if such naming exist:

1. Data structures that use $\mathcal B + \text{polylog}(\mathcal B)$ bits.
2. Data structures that for every fixed $\epsilon>0$ uses less than $\mathcal B (1+\epsilon)$ bits (the data structure takes $\epsilon$ as a parameter that may influence its runtime).


texts:
How can someone synchronize two or more threads using serialization? According to my professor's slides and code assignments you can use serialization to solve the synchronization problem. (He doesn't explain what serialization is).

I tried to do my research but serialization means that you put data in a specific order. I would understand that it means the same thing in this case (Running threads in a specific order). But what I most confused about is the syntax of the question. My question is:

Does serialization mean synchronization? How would one synchronize threads using serialization?


texts: Each finite segment of a noncomputable integer sequence is computable

texts:
Wikipedia claims that "each finite segment of noncomputable sequence of integers is computable".

It continues to clarify: For any noncomputable function, "for any given value of n, [...] a trivial algorithm exists (even though it may never be known or produced by anyone)".

While I do believe this for the given example with busy beavers, I am not certain this is always correct. Is there a proof of this statement?