texts: How to find the minimal DFA for the language?

texts:
Design a minimal DFA for the language which contains numbers in the form of binary strings starting with $101_2$ and is divisible by $100_{10}$?

I think the numbers will be 700,1400,2100 ... in the form of binary strings which are starting with $101_2$ and are even divisible by $100_{10}$.

100 is divisible by 25 and 4.

For divisible by 4 - Minimum 3 state DFA is possible For divisible by 25 - Min 25 state DFA is possible.

Hence, for divisible by $100_{10}$ - Minimum 100 states DFA is possible .

So, for starting with $101_2$, I have to add 3 extra states along with one dead state.

So, total states in minimal DFA = 100 + 3 + 1 = 104

Is my approach correct or am I missing something?


texts: Decoding cyclic code, assuming we have no errors

texts: Assuming the coded data is errorless and given generator polynomial coefficients. By what algorithm can I decode the data coded by matrix constructed by given generator polynomial?


texts: Inference of a measure for a decreasing chain

texts:
Set $I_n = \{0,\ldots,n-1\}$.
Given integers $v_0,\dots,v_{n-1} \in \mathbb{N}$, find an integer $t>0$, a map $f:\mathbb{N} \times I_n \to \mathbb{N}^t$, and a well-founded order $>_t$ on $\mathbb{N}^t$ such that: $$\forall i \in I_n, m \in \mathbb{N}. f(m,i) >_t f(m+v_i,i+_n 1)$$
where $+_n$ is addition in $\mathbb{Z}_n$ and $v_0+\dots+v_{n-1}<0$.  Is there an efficient algorithm to do that?
Explanation and motivation
The directed weighted graph $0 \stackrel{v_0}\to 1 \stackrel{v_2}\to \ldots \stackrel{v_{n-2}}\to n-1 \stackrel{v_{n-1}}\to 0$ describes how a magnitude $m \in \mathbb{N}$ varies. For transition $i \stackrel{v}{\to} j$, $m$ gets updated with $m+v$. It must hold that $\sum_{i = 1}^n v_i < 0$. Consider the following problem:
Give an assignment of values in $\mathbb{N}^t$ to nodes and an order that decreases at each transition. That is, if $\text{nodes} = \{0,\ldots,n-1\}$, I want to build a map $f:\mathbb{N} \times \text{nodes} \to \mathbb{N}^t$ with $t > 0$ satisfying: $\forall i \in \text{nodes}. f(m,i) >_t f(m+v_i, i +_n 1)$ where $>_t$ is a well-founded order on $\mathbb{N}^t$.
Is there an algorithm that can built such an $f$ and $<_t$?
Example (my try):
Assume you have the following chain is given:
$1 \stackrel{+3}{\to} 2 \stackrel{-2}{\to} 3 \stackrel{-2}{\to} 1$
In this case, $+3-2-2 = -1 < 0$.
Let's start at 1.
Since $m$ increases, I will annotate measure $(2,m)$ in $1$ and measure $(1,m)$ in $2$ so that lexicographic order decreases.
At $2$, measure $m$ decreases so I can leave annotation $(1,m)$ as it was.
At $3$, measure $m$ decreases so I can copy annotation $(1,m)$ from $2$.
Coming back to $1$, I have a problem, since I had annotated $(2,m)$ before, but now I have annotated $(1,m)$ and these are clearly different measures.
Can you help me out of this problem?
Note on the meaning of the specification
Just to make sure the specification matches my needs, the problem tries to  model how some quatity $m$ varies in a loop of successive function applications. The functions form a loop that ends at $0$. It is guaranteed  that when traversing the whole loop, quantity $m$ decreases (according to the variations $v_i$). In each function one have to check that in the next call certain measure $f$ (depending on the parameter $m$) decreases.


texts: Making a recursive formula for finding amount of ways to spend money on beer

texts:
So far, i've only made recursive formulas for finding simple patterns such as fibonacci, however i can't seem to get my head around this.

The information available is that there are $n$ different beers with different prices, the $i$th beer has a price $p_i$.  Students have $C$ amount of money

How would you make a recursive formula for the amount of ways students can spend exactly $C$ money on beer?


texts: Prove language is not Turing-recognizable using contradiction

texts:
Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable.
Note: Prove by contradiction. No need for reduction.
This is the problem I am trying to solve. I'm confused on how to do this without using reduction.


texts: Time Complexity of k-clique problem with fixed k

texts:
My question expands on a related question on the link, Why is the clique problem NP-complete?
In that post the author argued that while the $k$-clique problem is NP-complete; for a fixed $k$ the $k$-clique problem is polynomial time solvable. The question "Prove that the presence of 3-clique in a graph can be decided in polynomial time" also appears in the book, S. K. Basu, "Design Method and Analysis of Algorithms, PHI, 2005, pg159.

To avoid any confusion, I felt it important to clarify that this would only be possible if the graph $G=(V,E)$ ($V$ is the set of vertices and $E$ is the set of edges) is fixed. In such a case a polynomial number of steps $R^m,$ (where $R=f(V,E)$, i.e. $R$ is a constant given by some function of vertices and edges) can be used to find the solution of 3-clique for example.  So the conclusion that finding 3-clique for a fixed graph has polynomial time complexity works perfectly fine until this point.

But such a polynomial time algorithm with time complexity less than or equal to linear time complexity can not be designed to find 3-clique, i.e. $m>1$. Assuming that $k$ is fixed but $G$ is not fixed, in that case the complexity of finding 3-clique will then be exponential, unless someone can provide a polynomial time algorithm with complexity $R^m$, where $m\leq 1$ to find 3-clique for a fixed arbitrary graph. Since we are unable to prove that a polynomial time algorithm does not exist for 3-clique problem on an arbitrary graph, the computational complexity of the problem will hence be treated as being NP-complete based on the relationship $3SAT\leq_p k$-clique, a proof of which can be found in many standard books on algorithms.


texts:
I have already read different things about hamming distance, hamming code, detection and correction of memory errors, but I am still not understanding many things.

I know that the hamming distance between 2 codewords is the number of bits to be reversed to convert one codeword into the other.

I know that the hamming code is the set of all possible codewords. The codewords are composed of data bits and control bits, hence the number of bits in a codeword is n = m + r, where m is the number of data bits and r is the number of check bits. And the number of possible codewords with n bits should be $2^n$.

One thing I am not understanding is what are these valid and invalid codewords and how to 'calculate' them? Why a codeword is valid and invalid? What is the connection with the parity bits? How to find an invalid codeword?

I'm sorry if I am asking many things together, but I am really not understanding exactly the concepts I cited above.


texts: Would this be true for complexity classes?

texts:
For each integer k > 1, define the complexity class:
 $QP_{k}:= \cup_{c>0} Time(2^{c  * log^{k} n})$

Then for all integers k > 1, $QP_{k} \subset QP_{k+1}$.

Would this be a true assertion?

Anyone know? :(


texts: Why is this language involving reversal regular?

texts:
For a language to be regular it needs to be recognized by DFA/NFA.

Let $L = \{ xy^rzyx^r \mid |x| , |y|, |z| \ge 1 \}$ over the alphabet $\{0,1\}$.

$x^r$ means the reverse of $x$.

A DFA has no memory, so how can it handle the reverse check?


texts: What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?

texts: It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?


texts: How do I apply patch sized features to larger images?

texts:
I've been trying to teach myself some machine learning, and I wanted to ask what seems a simple question, but I've not been able to find any resources that explain the next step.

Let's say I am doing semi-supervised learning, and have a few hundred sparsely distributed feature extractors, trained on random 32x32 regions (the unsupervised part of the process).

I now want to take the larger images in my training set, and do some supervised learning based on the feature extractors I now have. In this case, multi-label classification.

The bit I'm not clear on is what I do with the full sized image from my training set:

Take random samples from it? -- seems like it would be pot luck if it picks an area needed to identify appropriate labels
Take overlapping tiles with a sliding window? -- seems like I'd end up with absurd dimensionality, since for each tile, I get a whole vector of features
Take adjacent tiles? -- dimensionality still nonsensical, and probably translation sensitive as well

It's a hypothetical example, but let's say my inputs are 800x600 photographs, i.e. the input is about 100-1000 times bigger than the samples I used in the unsupervised learning stage.


texts: Why does Banded Needleman-Wunsch give alignments with no more than d base pairs of indels?

texts:
A common modification to the Needleman-Wunsch to reduce running time is to only fill in the cells along a diagonal band of the matrix (slides 27/28). Let 2d + 1 represent the width of the band. Then based on the provided text, this ensures that the total number of inserts and deletes does not exceed d.

However, I can't understand the intuition behind the algorithm. If we let L represent a list of the size of each mutation in the alignment in-order (where negative sizes represent deletions), doesn't the band restriction merely say that the sum of values in any prefix slice of L must stay between -d and d? But the total number of mutations could easily exceed d.

E.g. If d = 4, throughout a long alignment, there could be 5 distinct mutations, where L refers to a series of [insertion, deletion, insertion, insertion, deletion] with sizes: [3,-2,2,1,-4]. Visually, such an alignment would represent a wiggly line through the DP matrix that results in plenty of small insertions and deletions, alternating to ensure that the alignment stays within the band.

In other words, the band does not actually restrict the total number of insertions and deletions as claimed? If I'm misunderstanding something, I'd appreciate any clarification. Thanks!

P.S. Was unsure if this post should go under the bioinformatics stackexchange beta.


texts: Turing Machine equivalence in MinTM proof

texts:
The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows:

  $C=$ "On input $w$:

  Obtain, via the recursion theorem, own description $\langle C \rangle$.
  Run the enumerator $E$ until a machine $D$ appears with a longer description than that of $C$.
  Simulate $D$ on input $w$."

$MIN_{\mathrm{TM}}$ is infinite, so at least one $D$ occurence will be observed.

Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal.

I would like to understand three things from this proof:

How do we know that $MIN_{\mathrm{TM}}$ is inifinite?
Why $C$ is equivalent to $D$?
Why "Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal"?. Why do we expect $D$ to be minimal?

Edit :
I have some opinions (I want to verify) about my questions. Please correct me If I am wrong.

Equivalence is based only on ability to construct same language recognizers
or to say $L(M_1) = L(M_2)$


texts: How to calculate the complexity of a TM?

texts:
I have the language

$\{ w \mid w \text{ contains an equal amount of symbols } a \text{ and } b\}$.

I want to show that the language is in the class $\textsf{P}$. To do this, I must give an implementation level description of the relevant Turing machine. I'm not very knowledgeable on Turing machines, but I think I would be able to write down a possible transition function, but from this how do I compute the complexity, in order to show it is in the class $\textsf{P}$?


texts: How to display distinct rows from single column without using DISTINCT keyword and count() function?

texts:
How to display distinct rows from single column without using DISTINCT keyword and [having count(*) > 1 ] ?  My question is can we do this using sub-queries or co-related sub query ?
If yes how we can do this ?

Please let me know.
Thanks.


texts:
So I am looking at some Operating Systems exercises and we have

  A swapping system eliminates holes by compaction. Assuming a
             random distribution of many holes and many data segments and a
             time to read or write a 32-bit memory word of 10 nsec, about how
             long does it take to compact 128 MB? For simplicity, assume that
             word 0 is part of a hole and that the highest word in memory
             contains valid data.

  The solution is : 128 x 2^20 / 4 = 2^25 memory address

      compaction time = (read + write) * # of memory access
                      = 2 x 10 x 10 ^ -9 x 2^25
                      = 671 ms

Problem is I dont understand the 128 x 2^20 / 4 = 2^25 memory address part ? How did we get 2^20 in this case? I gues the 4 is 4 bytes =32 bits so I kinda understand that.

Now in 2 x 10 x 10 ^ -9 x 2^25 what is 2 here?


texts: Introductory Book on Pseudo-Random Number Generation

texts:
I'm a rank amateur in the area of pseudo-random number generation. I've recently found out that certain generators are better than others (e.g. mt19337 vs rand in C++) and learned what modulo bias is.

My Request

I'm looking for an introductory book on pseudo-random number generation.  Does one exist?

My Requirements

The book must be understandable by someone with the following mathematics background:

calculus
discrete math (combinatorics, logic and proofs, set theory, mathematical induction, functions and relations, inclusion-exclusion, generating functions, recurrence relations, graphs/graph algorithms)
linear algebra (vectors,matrix algebra, eigenvalues, transformations, diagonalization)
introductory numerical analysis (computer arithmetic and errors, root-finding algorithms, computational techniques for matrices, numerical integration and differentiation)

I would prefer a book that does not require knowledge of any specific programming language:

Would like algorithms to be presented in a pseudocode style (e.g. Introduction to Algorithms by Cormen)
If the book isn't language neutral, I know the following languages: Python, Java, C++,C,Ruby.

I'm looking for a book that is accessible to a fairly inexperienced CS undergraduate:

I have a basic understanding of stacks, linked lists, trees, heaps, hash tables and graphs
I'm comfortable with basic programming concepts

The book should cover pseudorandom number generation at an introductory level:

I'm not looking for a complete encyclopedic treatment on every research paper ever published in the area, but enough content to gain an entry level understanding in the area that you'd expect someone to learn in a first undergraduate course on pseudo-random number generation. For example if someone asked you for a book on introductory calculus you'd probably recommend a book that covers limits, differentiation, related rates, approximation of derivatives, L'Hopital's Rule and some basic continuous optimization. I'm looking for something similar in the area of PRNG. It's hard for me to specify exactly what I'm looking for because I know next to nothing about the area, but try and think of what you'd expect a complete amateur in the area to be able to reasonably learn in a semester.

What I've Tried

I'm looking at Chapter 3 of Donald Knuth's art of computer programming volume 2. The book seems quite old and uses some kind of assembly that I don't understand. If this is the authoritative reference, I'll find my way around these issues, but other books would be nice.


texts: I've read over the proof for Robbin's Theorem, but I am not seeing why DFS will always give you a correct orientation of directed edges to solve the problem.


texts: Finding a (minimal?) program that maps $M$ items to indices $[0,M)$

texts:
Let's say there are $M$ strings that we are trying to create a perfect hash for such that we get as output of the hash $[0,M)$ with no collisions, when hashing those $M$ items.

I know that there are algorithms that can help you achieve this by finding salt values to use with a given hash function that will cause this to happen (like this one http://blog.demofox.org/2015/12/14/o1-data-lookups-with-minimal-perfect-hashing/).

However, all of the algorithms I've seen are randomized/probabilistic: e.g., there is a probability $p$ for any particular salt value to yield a perfect hash, so keep trying until you find one.

Is there any deterministic algorithm for constructing a perfect hash?

Second, is there a deterministic algorithm to construct a perfect hash that is minimal in size (the smallest program that is a valid perfect hash on these $M$ items)?

Security isn't a concern, and while efficiency of the algorithm to find the mapping is nice, it isn't a requirement. Evaluating whatever mapping program was found should be as efficient as possible though.


texts:
I have to compute the space complexity of this function:

double foo(int n){
     int i;
     double sum;
     if(n==0) return 1.0;
     else
          for(i=0;i<n;i++)
              sum+= foo(i);
     return sum
}

What I have done:

When function is called, the activation record is created on the call stack. For $foo(n)$ let the size of AR be $x$.

$foo(0)$ does not place any recursive calls.
$foo(1)$ places 1 recursive call. Terminates at $foo(0)$.
$foo(2)$ places 2 recursive calls to $foo(0)$ and $foo(1)$.
$foo(1)$ places another recursive call.
Therefore total calls placed is 2+1.
$foo(3)$ places 3 recursive calls to $foo(0)$,$foo(1)$ and $foo(2)$. Therefore total calls placed is $3+0+1+3= 7$ recursive calls.
$foo(4)$ places 4 recursive calls. $4+0+1+3+7= 15$.

Hence we can see that $foo$ produces calls in the pattern: 0,1,3,7,15,31,...

This shows us that $foo(n)$ produces $(2^n)-1$ recursive calls.

If we count the total no. of recursive calls made by $foo(n)$ it becomes a geometric series and evaluates to approximately $(2^n)-n$.

Hence I am getting Space complexity to be $O(2^n)$.

However several books have merely listed the answer as $O(n!)$ without giving an explanation. I just want to know where I am going wrong in my approach.


texts: Classification problem where one attribute is a vector

texts:
Hello I am a layman trying to analyze game data from League of Legends, specifically looking at predicting the win rate for a given champion given an item build.
Outline
A player can own up to 6 items at the end of a game. They could have purchased these items in different orders or adjusted their inventory position during the course of the game.
In this fashion the dataset may contain the following rows with:
   champion id   |                 items ids               | win(1)/loss(0)
----------------------------------------------------------------------------
       45        |   [3089, 3135, 3151, 3157, 3165, 3285]  |       1
       45        |   [3151, 3285, 3135, 3089, 3157, 3165]  |       1
       45        |   [3165, 3285, 3089, 3135, 3157, 3151]  |       0

While the items are in a different order the build is the same, my initial thought would be to simply multiply the item ids as this would give me an integer value representing that combination of 6 items.
While there are hundreds of items, in reality a champion draws off a small subset (~20) of those to form the core (3 items) of their build. A game may also finish before players have had time to purchase 6 items:
                items ids
------------------------------------------
   [3089, XXXX, 3151, 3285, 3165, 0000]
   [XXXX, 3285, XXXX, 3165, 3151, 0000]
   [3165, 3285, 3089, XXXX, 0000, 0000]

XXXX item from outside core subset
0000 empty inventory slot

As item 3089 compliments champion 45 core builds that have item 3089 have a higher win rate than core builds which are missing item 3089.
The size of the data set available for each champion varies between 10000 and 100000. The mean is probably around 35000.
Questions

Is this a suitable problem for supervised classification?
How should I approach finding groups of core items and their win rates?


texts: Is following grammar has language which is inherently ambiguous?

texts:
Grammar is as follow:

$S \rightarrow aaAb | aab | A$

$A \rightarrow aaAb | aAb | \epsilon$

I think that this grammar has equivalent unambiguous grammar as follow.

Let’s first rewrite the grammar as below such that this grammar has same language as one in question:

$S \rightarrow aaSb | aSb | \epsilon$

Because this grammar generates $L = \{a^nb^m: m \le n \le 2m\}$

This grammer is just using two production in some order to derive string and then use null production to complete derivation.

So, idea is that we can some how order use of production such that any use of $S \rightarrow aaSb$ production does not come before use of any production of form $S \rightarrow aSb$. And following this idea it’s very easy to generate this grammar.

$S \rightarrow aSb | A$

$A \rightarrow aaAb | \epsilon$

.

Another arguments goes as follow:

Because $2k_1 + k_2 = n$ and $k_1 + k_2 = m$ for some $nonnegetive \space integer \space k_1, k_2$. (here $k_1$ and $k_2$ corresponds to number of use of production of form $S \rightarrow aSb$ and $S \rightarrow aaSb$ respectively.)

After solving the above equations we find that $k_1 = m-n$ hence value of $k_1$ will be unique for any perticular string. Which means that we must have to use some fix number of times the production of form $S \rightarrow aSb$. Which consequenly means that in our last rewritten grammer there is a fix point for a perticular string where you have to perform $S \rightarrow A$.

Please help me with this. I want to know whether this language is inherenly ambigous or not?


texts: Solving membership problem for a PDA-generated language without converting the PDA to a CFG

texts:
The classic solution for the membership problem of a language generated by a PDA is to convert said PDA to a CFG and then to use CYK or a similar algorithm. I was wondering if there are any known algorithms to solve this problem without a conversion to a CFG.

My attempt at a naive solution was to "emulate" a PDA, but if there's a transition of form $(q, \varepsilon, A, q, AA)$, then the stack grows infinitely and emulation never halts.


texts: first intersection of two arrays of integers - double binary search feasible?

texts:
I'm interested to find the fastest possible way to find the first element of an intersection of two integers arrays (first match)

Looking for the 'fastest' algorithm I have seen different methods with different time complexities (to calculate the arrays intersection)

i.e: $O(N+M)$, $O(N * log(M)$,...

Also I have seen some references to an algorithm able to do this by implementing a double binary search to find the first match with time complexity $O(log(n)+log(m))$

Do you know about some reliable source or pseudo-code about this algorithm if such exists?


texts: Deterministic query complexity and polynomial degree

texts: What is the current best upper bound known on deterministic decision tree complexity of a Boolean function in terms of its polynomial degree? Also, what is the current widest separation known between these two measures?


texts: Encoding the pigeonhole principle in CBMC

texts:
CBMC is a Bounded Model Checker for ANSI-C and C++ programs. It also supports SystemC using Scoot. It allows verifying array bounds (buffer overflows), pointer safety, exceptions and user-specified assertions.

For the pigeon-hole principle I understand that the constraints are:

Each Pigeon is in some Hole.
Two different Pigeon can't be in same hole.

Let's take an example of 4 pigeons and 3 holes. I need to convert this into a CBMC check. I'm trying using two for loops, but I can't find how to do it.


texts: Computing FOLLOW sets for a LL(1) grammar

texts:
I am trying to learn compiler design. But I get confused when I have to deal with computing the follow set specifically for the empty word.

Given the grammar:

S-> ABC
A-> Aa|b
B-> Bc|d
C-> Ce|f

I've come up with the following first and follow sets:

1 S->ABC   First(1)-{b}
2 A->bA'   First(2)-{b}
3 A'->aA'  First(3)-{a}
4 A'->E    Follow(4)- ??
5 B->dB'   First(5)-{d}
6 B'->cB'  First(6)-{c}
7 B'->E    Follow(7)- ??
8 C->fC'   First(8)-{f}
9 C'->eC'  First(9)-{e}
10 C'->E   Follow(10)- ??

Please help me determine the follow sets I've indicated with ??. Is there a formula I can use to determine the follow sets?


texts: Lamport logical clock: what does partial mean in the concept of `Partial ordering`?

texts:
In lamport's paper[1], he define two concept The partial ordering and The totally ordering.

What does partial mean in partial ordering?

assumption: this ordering only handle two cases, one is to order events happening in single process, second is communication events between two process. It can't handle concurrent events, so it's named as Partial ordering.

Is my assumption correct?
What does totally ordering mean?

Does that mean it can handle all the events in a distributed system?

Reference

Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System.”


texts:
I am going through some past exam paper questions on regular languages for some revision, and I am having a bit of trouble with converting general ideas into formal mathematical proofs.

The question is:

  Given regular expression $S$, prove formally that $S^* = (S^*)^*$.

My problem is expressing this in a formal proof. Here is what I have worked through so far (it is a bit all over the place and just a collection of ways to express the problem mostly)

$S^* = (S^*)^*$

this implies:

$S^* \subseteq (S^*)^*$ and $S^* \supseteq (S^*)^*$

if we assume that there exists $w_k$ such that $w_k \in S^*$

then the base case for the proof is:

$k = 0$   $(w_k = \epsilon)$ (empty word, always in $S^*$ and $(S^*)^*$ by definition)

$k = 1$   $(w_k \in S^*)$

and that's kind of where my ability to reason ends.

I think the rest of it will be something like:

$w_{k+1} = w_kx$

ie. $w_k$ concatenated with $x$ where $x \in S^*$

but how can I show that $w_{k+1} \in (S^*)^*$?

Any help to push me in the right direction would be greatly appreciated.


texts:
We have an $x$-monotone path $\mathbb{P}$ in the input. We want to store the path $\mathbb{P}$ in a data structure such that we can answer this type of the query.
Given any circle $\mathbb{C}$ and any two indices $i$ and $j$ with $1 \leq i \leq j \leq n$, report the first point of the subpath $\pi [ p_{i}, p_{j} ]=(p_{i},p_{i+1},...,p_{j}) $ is out of the $\mathbb{C}$.

We construct a balanced binary search tree storing the points $p_{1}, p_{2}, ... , p_{n}$ in its leaves. At each node of the tree, we store the extreme points of the convex hull of all points stored in its subtree.

To answer a query, we compute $\mathcal{O}(\log{}n)$ canonical nodes whose subtree span the vertices on the subpath $\pi [ p_{i}, p_{j} ]$. For each canonical node, we check whether or not the extreme points are in the $\mathbb{C}$. If all the extreme points lie inside $\mathbb{C}$, data structure reports $j$ otherwise it reports the first extreme point $L$ which is outside of the $\mathbb{C}$.

Now, I want to know what the worst Query time is.


texts: Examples of specialized instructions of assembly language not available in compilers?

texts:
In my CS computer organization textbook, there's this blurb on the advantage of assembly over a high-level language.

  Another major advantage of assembly language is the ability to exploit specialized instructions - for example, string copy or pattern-matching instructions. Compilers, in most cases, cannot determine that a program loop can be replaced by a single instruction. However, the programmer who wrote the loop can replace it easily with a single instruction.

How can a loop be replaced by string copy or pattern matching? Can somebody give an example on specialized instructions that are not available in a high-level language and how a specialized instruction can replace a loop?


texts:
This picture is from Computer System Architecture 3rd Edition by Morris Mano. Is it possible to interchange the data of any two registers in a single clock pulse? I know that the data of DR (data register) and AC (accumulator register) can be interchanged in a single clock pulse. But other than this I don't understand how data replacement between two registers can be accomplished.
Thank you.


texts: What is the level of the material contained in the book Data Structures and Algorithm Analysis in C++ (4th Ed) by Weiss?

texts:
The question is pretty much explained in the title. I have the necessary discrete math background and would like to learn algorithms and data structures in the process (of coding) - so the book quoted in the title seems a good read. Since the author states clearly in the preface that the book is suitable for an advanced data structures course or a 1st year graduate course on algorithm analysis, my question seems answered already. But I guess my real question is how much material is contained in the book and how advanced it is, say compared to the following resources:

Two MIT graduate-level courses - Advanced Algorithms (http://people.csail.mit.edu/moitra/854.html) by Ankur Moitra and Advanced Data Structures (https://courses.csail.mit.edu/6.851/spring12/) by Eric Demaine.

PS: I want to become a C++ programmer (generically speaking) with a strong algorithm and data structures background. Not really sure what material I should dive into. Any suggestions on this are also very welcome!


texts: What kind of order is binary tree ancestry?

texts:
Let isAncestor be a relation on binary tree nodes such that isAncestor x y means y can be reached from x in n steps from parent to child, where n may be zero. It is clear from this definition that isAncestor is a partial order. (Two nodes are mutual ancestors if and only if they are identical, and ancestors of ancestors are also ancestors.)

But on a second reflection, isAncestor is not just a partial order. For instance, it has the property forall x y z, isAncestor x z -> isAncestor y z -> ( isAncestor x y \/ isAncestor y x ), which I don't think is common to all partial orders.

Is there a kind of order that precisely designates isAncestor? Since binary trees are extensively studied in CS, I'm guessing there must be a name and a well known set of properties for this kind of relation.


texts: Is the union between a regular language and a random language also a regular language?

texts: If not can we draw any conclusion about the newly fromed language, the language that represents the union between a regular language and a non regular language  (not context free but a truly random language ).


texts:
Given the grammar:

$S \to AS\mid \varepsilon$
$A \to A1\mid 0A1 \mid \varepsilon$

Generate a new unambiguous grammar that generates the same language as the grammar above.

I have no idea how to make it unambiguous, I have proven already that the given language has two leftmost derivations for the string 01101.


texts: left/right derivations of grammars and parse trees

texts:
I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct.
$S-> NP$ $V$ $NP$
$NP ->$ the $N$
$N ->$ cat | mouse
$V ->$ ate
LEFT
$S-> NP$ $V$ $NP$
$S->$ the $N$ $V$ $NP$
$S->$ the $N$ $V$ the $N$
$S->$ the cat $V$ the $N$
$S->$ the cat ate the $N$
$S->$ the cat ate the mouse
RIGHT
$S->NP$ $V$ $NP$
$S->NP$ $V$ the $N$
$S->$ the $N$ $V$ the $N$
$S->$ the $N$ $V$ the mouse
$S->$ the $N$ ate the mouse
$S->$ the cat ate the mouse
My Thoughts
My lecture material says that we operate on the left/rightmost non terminal, I'm not 100% sure how to differentiate terminals and non-terminals but I assumed that if it became an English word it was a terminal hence I skipped it as long as there was a production remaining with another identifier in it.
Parse Tree
I genuinely don't know how to create the parse trees and I appreciate any input in helping me figure it out.
edit: I forgot to mention, I know that the parse tree should be the same for the left and right derivation of the above grammar, just don't know how to build one, all examples I find online are too complex for my understanding, I just started learning about this stuff very recently.


texts: Solving recurrence relation when cost of all combining steps is constrained

texts:
I have a recurrence relation $T(n) = \left( \sum_{i=1}^{k} T(d_i n) \right) + f(n)$, where each $ 0 < d_i < 1$, $f(x) > 0$ for all $\, x > 0$ and $f(xy)=f(x) \cdot f(y)$ for $x,y\geq 0$.

I am asked to give an asymptotically tight bound on $T(n)$ if $\sum_{i=1}^{k} f(d_i) < 1$ and if $\sum_{i=1}^k f(d_i) = 1$ using the substitution method, and I am told not to worry about the base case. I am following the substitution method from CLRS section 4.3 and  basically means guess an upper bound, and then prove by induction.

I tried several guesses when $\sum f(d_i n) < 1$, but I get stuck regardless of my choice. If $T(n) = O(f(n))$, it must be true that
\begin{align*}
T(n)&\leq c f(d_1n) + c f(d_2 n) + \dots + cf(d_k n) + f(n)\\
&= c(f(d_1 n) + f(d_2 n) + \dots f(d_k n)) + f(n) \\
&< c + f(n) & \text{Since} \sum f(d_i n) < 1
\end{align*}
Which is false, unless $c < 0$, which can't be the case.

If $T(n) = \lg f(n) $ then it must be true that

\begin{align*}
T(n) &\leq c \lg (f(d_1 n)) + c \lg(f(d_2 n)) + \dots + c \lg(f(d_k n)) + f(n) \\
&=c [\lg f(d_1) + \lg f(n) + \lg f(d_2) + \lg f(n) + \dots + \lg f(d_k) + \lg f(n)] + f(n) \\
&=c \left( \left(\sum_{i=1}^{k} \lg f(d_i)\right) + k \lg f(n) \right) + f(n).
\end{align*}
Not sure how to proceed here. When I tried $T(n) = O\left(f(n)^2\right)$, I got

\begin{align*}
T(n) &\leq c \left( \sum_{i=1}^n f(d_i n)^2 \right) + f(n) \\
&< c + f(n) & \text{ since } \sum f(d_i n ) < 1 \implies \sum f(d_i n)^2 < 1  \\
&\leq c f(n)^2
\end{align*}
which doesn't seem too tight, but I'm not sure. Any comments or pointers on how to proceed? I presume it involves incorporating the constraints on $\sum f(d_i)$ in some other way, but right now I am not seeing how to do so.


texts: Why is binary search faster than ternary search?

texts:
Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space.
If, instead, we used 'ternary search', we'd cut away two-thirds of our search space at each iteration, so the worst case should take $\log_3 N < \log_2 N$ iterations...

It seems that ternary search is faster, so why do we use binary search?


texts: How can we assume that basic operations on numbers take constant time?

texts:
Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$.  For example, we assume this when we say that comparison-based sorting is $O(n\log n)$, but when numbers are too big to fit into registers, we normally represent them as arrays so basic operations require extra calculations per element.

Is there a proof showing that comparison of two numbers (or other primitive arithmetic functions) can be done in $O(1)$? If not why are we saying that comparison based sorting is $O(n\log n)$?

I encountered this problem when I answered a SO question and I realized that my algorithm is not $O(n)$ because sooner or later I should deal with big-int, also it wasn't pseudo polynomial time algorithm, it was $P$.


texts: Can all types of problems be converted to decision problems?

texts:
We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well?
Description of the types of problems is given here:
Computational problem.

Edit: So, the comments suggest that I state more precisely what I mean. I'm not entirely sure how to do that, so I'll tell you where I'm coming from. I understand that a Turing machine can solve only decision problems (It can accept or reject a string). I am wondering if a Turing machine can solve all kinds of problems - which is why I ask, can all those types of problems be expressed as decision problems?

A better way to put it would probably be, can all those types of problems be expressed in a way that they might be solved by a Turing machine?


texts:
Does anyone know of an algorithm who is able to return how similar a DFS Tree is from another DFS Tree? (Or any kind of tree in general)

I'm not looking for a true or false. Instead, I would like it to return something in the form of "DFS A is ~87% similar to DFS B"

Thanks!


texts: Data normalization when control has multiple values in CS/CE

texts:
(This question was originally posted at https://academia.stackexchange.com/questions/68675 but was considered too specific for Academia.)

In computer science/engineering research papers relating to performance improvement wherein execution time is normalized to control benchmarks (i.e. speedup plots), how is that normalization generally implemented when the control(s) is/are executed multiple times in order to avoid the possibility of other processes/interrupts/etc. taking processor time and skewing the results? My first thought would be to just use the minimum time achieved for each benchmark, but as that would probably not be the minimum possible execution time in most cases and, depending on the situation, overall execution time rather than best-case execution time may be more important, is it better to just accept the skewing and go off the means? Or is it better to use the median for each set of results?


texts: Traverse Matrix in Reverse Diagonal strips

texts:
I thought this problem had a trivial solution, couple of for loops and some fancy counters, but apparently it is rather more complicated.

So my question is, how would you write (in C) a function traversal of a square matrix in diagonal strips.

Example:

1 2 3
4 5 6
7 8 9

Would have to be traversed in the following order:

[3],[2,6],[1,5,9],[4,8],[7]


texts:
Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $v_{i}v_{j}$ we have the constraint $x_{i}+x_{j}\geq 1$, for each variable we have $0\leq x_{i}\leq 1$ and we have the objective function $\min \sum\limits_{1}^{n}{x_{i}}$. We say such a linear programming problem LP. Note that it is NOT an integer linear programming problem.
We find a half integral optimal solution of LP that we say $S_{hi}$. For each variable $x_{i}$ that takes value 0 in $S_{hi}$, we add the constraint $x_{i}=0$ to LP.
For each odd cycle of $G$, add to LP the constraint $x_{a}+x_{b}+x_{c}+...+x_{i}\geq \frac{1}{2}(k+1)$ where $x_{a},x_{b},x_{c},...,x_{i}$ are the vertices of the cycle and $k$ is the number of vertices of the cycle. We find a new optimal solution of LP that we say $S$.
If $x_{i}$ is a variable that takes value $0.5$ in $S_{hi}$ and value $\gt 0.5$ in $S$, can we say that there is at least a minimum vertex cover of $G$ that contains the vertex associated to $x_{i}$?
The idea behind the question: in an odd cycle $c$ with $k$ vertices, the number of vertices needed to cover the cycle is $\frac{1}{2}(k+1)$, therefore for each odd cycle we add to LP the constraint $x_{a}+x_{b}+x_{c}+...+x_{i}\geq \frac{1}{2}(k+1)$. If in $S_{hi}$ the sum of the variables of $c$ is $\frac{k}{2}$ (that is all the variables of $c$ take value $\frac{1}{2}$), then in $S$ at least a variable $x_{i}$ of $c$ takes vale $\gt \frac{1}{2}$ and the vertex associated to $x_{i}$ belongs to at least a minimum vertex cover of the given graph.


texts: Primes not dividing sequence $a_{n+1} = 1 + a_0 a_1 \cdots a_n$

texts:
Prove that there are infinitely many primes that divide none of the elements of the integer sequence
$a_{n+1} =1+a_0 a_1 \cdots a_n$, with a starting point of $a_0 \geq 0$.

I thought about $$\log (x_n-1)=\log x_0x_1\cdots x_{n-1}= \log x_0 + \log x_1 +\cdots+\log x_{n-1} $$ to solve the problem but couldn't.


texts: For proof automation in Coq, when is it appropriate to use canonical structures or Equations instead of Ltac?

texts:
There are a few possible approaches to proof automation in modern Coq.

Writing proof scripts with Ltac. This is the approach described in http://adam.chlipala.net/cpdt/, which the author uses to great effect in projects like http://adam.chlipala.net/papers/BedrockPOPL15/. It can significantly reduce the amount of proof code required, but requires a good handle on the quirks of Ltac and does not seem straightforward to debug.
Canonical-structures-based automation. This is the approach described in https://people.mpi-sws.org/~beta/lessadhoc/, and used in Mathcomp. It involves taking advantage of Coq's type inference mechanism to automatically execute logic programs that search for certain kinds of proof terms. It's described in that paper as less ad-hoc than the Ltac-heavy approach, but not necessarily faster, and can be more verbose due to needing to use the canonical structures mechanism for something it wasn't directly designed for.
Dependent types/Equations. The Equations plugin (https://www.irif.fr/~sozeau//research/publications/drafts/Equations_Reloaded.pdf) seems to faciliate in Coq the same convenience when working with dependently typed programs as a language like Agda or Idris. With this approach the elaborator acts as a form of automation, and the amount of proof code is reduced by having algorithms create, manipulate and pass around proof terms directly.

There are also some modern developments that complement these.

Ltac2. This is meant as a replacement for Ltac, with fewer quirks and potentially better performance, as described in https://popl19.sigplan.org/details/CoqPL-2019/8/Ltac2-Tactical-Warfare. The paper states that "Ltac2 is still in an active development phase, but the foundations of the language have been settled. More than anything, it is in need of users in order to polish the rough edges". If it is meant to be a superior replacement to Ltac, then should it be considered instead of Ltac for new projects, since it's already ready for user testing?
Metacoq. This provides metaprogramming features that allow the development of higher level tools, as described on https://www.irif.fr/~sozeau/research/publications/drafts/The_MetaCoq_Project.pdf, and presumably simplify the use of proof by reflection, a technique used in both canonical-structures-based an Ltac-heavy approaches.

My question is, if I'm starting a new project, what criteria should I use to determine which approach or combination thereof to adopt? As a concrete example, imagine I want to verify the easy-to-verify parts of a program that connects to a server over the internet, downloads some data, processes the data somehow, then serves the processed data over TCP. By easy-to-verify I mean not verifying the TCP/HTTP stack, or proving from scratch the correctness of well-known algorithms used in the data processing. When I consider how I'd structure this it seems like the structure would be quite different depending on which of the above approaches I used, and I lack the experience to make a judgement regarding which would produce the best result in terms of maximising the output of verified code per unit of development time. What factors should necessitate the use of canonical structures or Equations instead of just plain Ltac?


texts: Satisfiability with relational operators instead of boolean variables

texts:
Question

What is the state of the art for relation/equality satisfiability problems and where can I find papers clearly describing algorithms used (Or even better: implementations of them. Or even better: javascript implementations - I know that's a long shot)?

I.e. How do I solve satisfiability of: x > 10 && y < 5 && x < y

Long introduction

boolean satisfiability

The boolean satisfiability problem is quite well documented. However I cannot find algorithms for cases when propositions are relational operators rather than booleans.

For example:

To find out if a sentence like p && !p has any values of p for which it is true, is well documented and ready-made algorithms exist. Often the sentence is transformed to Conjunctive Normal Form (CNF) and then a CNF-SAT solver is used. For example:

http://logictools.org/index.html

relational/equality satisfiability

However I cannot find algorithms for cases when propositions are relational operators rather than booleans. Think of a statement like x > 10 && !(x < 5) or x > 10 && y < 5 && x < y. This seems a way less studied problem.

For example: Transforming equality logic to propositional logic is very theoretical, I couldn't really understand it and thus use it for implementation.

Solving Satisfiability and Implication Problems in Database Systems actually lead me to a solution. It explains how to solve satisfiability for sentences with only conjunctions. Knowing that, I can transform any sentence to Disjunctive Normal Form (DNF) and apply the algorithm to each conjunction in the DNF. If one of the conjunctions is satisfiable, the whole sentence is.

However, it seems that this is not the most efficient way to solve it. First, this paper is from 1996 and I expect the field to have progressed. Second, converting to DNF is exponentially complex while converting to a equisatisfiable CNF can be done in polynomial time. Most boolean satisfiability solvers seem to convert to CNF and then solve using heavily studied algorithms. It seems a similar approach would be preferable for relational satisfiability.

So my question is: What is the state of the art for relation/equality satisfiability problems and where can I find papers clearly describing algorithms used (Or even better: implementations of them. Or even better: javascript implementations - I know that's a long shot)

I have searched for 2 days in different fields such as SQL query optimizers (contradiction/tautology detection) and theoretical CS but haven't been able to find anything else than the above DNF solution.


texts: Generating uniform random connected graphs: doubt about Wilson's algorithm

texts:
I want to generate a random connected simple labeled graph with $n$ vertices and $m$ edges, selected uniformly over all connected graphs with such $n$ and $m$. I found this approach. It says: build a random spanning tree using a loop-erased random walk (also called Wilson's algorithm); then add remaining $m-n+1$ edges between random pairs of vertices.

I implemented and investigated this algorithm and have several doubts.

First, what do they denote with random spanning tree in the first part? A random spanning tree of $K_n$? If so, there are $n^{n-2}$ of them, so we may directly restore the tree by its (random) Prüfer sequence. Why do we need the loop-erased random walk here? As far as I experimented it gives the same distribution as the Prüfer-based generation.

Second. If I'm right at the first part and each tree is equiprobable, then different graphs may have different probabilities. For example, if $n=4$ and $m=4$, we have two graphs (I skipped the labels as they are irrelevant here):

o--o    o---o
|  |    |\ /
o--o    o o

The first one can be produced from some spanning tree in 4 distinct ways, while the second one only in 3 ways. If all trees are equiprobable, this obviously introduces bias in graphs.

Where is my mistake? I don't understand Wilson's algo and the distribution on trees is not uniform, or I don't understand the latter part, or this algorithm is in fact incorrect?

Finally, if it is incorrect, how does one generate a random connected graph? The approach of generating a random graph and checking its connectivity fails if $m = \Theta(n)$.

P.S. When saying about randomness, I assume that I have an oracle which returns me a uniform random number in range $[0, n)$ for a reasonable $n$.


texts: Describe a TM through denotation of the transition function

texts:
I'm trying to describe a TM through denotation of the transition function. Given is a TM that recognizes the language

$$
L ={\{w\#w} \mid w \in {\{0,1}\}^*\}
$$
over the input alphabet:
$$
\displaystyle\sum = {\{}0,1,\#\}
$$

My guess is first to place a word
$$
w \in {\sum}^*
$$

on the tape, and in every cell a symbol one after the other:

and the rest would be denoted with squares. Something like this
$$
...w|\#|w|\square...
$$
the head would be on the first Symbol from $w$

So I guess now I know that
$$
\Gamma = \{w,\#,\square\}
$$

I could probably try to make a table using what I have now:

for $w$:

$q_0 = (q_0,w,\#,R)$  R would be the direction the head is going

$q_1 = (q_{yes},w,\#,N)$ N means the head doesn't move and $q_{yes}$ means that the TM accepts w

Im not sure if what I'm doing is correct. I would appreciate if someone could tell me if I'm on the right track.


texts:
What is the runtime complexity of the following implementation of Bubblesort (for integers)?

    #define SWAP(a,b)   { int t; t=a; a=b; b=t; }

    void bubble( int a[], int n )
    /* Pre-condition: a contains n items to be sorted */
    {
       int i, j;
      /* Make n passes through the array */
      for(i=0;i<n-1;i++)
      {
     /* From the first element to the end
       of the unsorted section */
        for(j=1;j<(n-i);j++)
        {
        /* If adjacent items are out of order, swap them */
       if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
       }
    }
}


texts:
I would like to extend ECMAScript by adding new keywords and syntax to it, for example:

|variableName| stipulates a special kind of variable which I would like to be able to include in a normal ECMAScript line of code, for example:

|variable1| = 1 + 1
|variable1| = |variable2|.length - 3

a more complex one would be:

@SpecialObject[propertName:propertyValue,..., propertyNameN:propertyValueN] {
    {|variable1| == true} => {
        console.log("condition 1 applies")
        |variable1| = false
    }
    .
    .
    .
    {|variable2|.length !== 0} => {
        console.log("variable 2 contains elements")
        |variable2| = Date.now()
    }
}

I have built an initial prototype by impementing my own lexer and parser (using Chevrotain), but it is quite limited as it only supports those specific constructs of my new syntax, what I would like to do is to make it more powerful by being able to include ECMAScript code in my syntax, how could it be done?


texts: Transition diagram for following token number

texts:
number ->  digits(.digits)?(E[+ -]?digits)?
This transition diagram runs the  above mentioned token I can not understand this how this is work.what is meaning of "?"Symbol and digits. can anyone explain me this


texts:
Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA

some nodes have multiple in/outgoing edges
single start state
there might be multiple final states
a state can contain self loops where a symbol is consumed
no epsilon transitions

What i'm trying to do is generate a regular expression from this graph.
I've found the following topic using Brzozowski algebraic method: https://cs.stackexchange.com/q/2392

However, it seems to be for DFA's, so my question:

can I use Brzozowski algebraic method OR Transitive closure method with my NFA, or do i need conversion first?

I need an algorithm that can be done by a computer to automatically generate a regex from a given graph.


texts: Show this language is non-regular using pumping lemma: B = {ww | w ∈ {a,b,c,...,z)*}

texts:
The question I'm working from is:

Prove whether or not a finite automation exists that recognises the following language:

B = {ww | w ∈ {a,b,c,...,z)*}

EDIT

So I believe this is a non-regular language. My understanding of pumping lemma is not great but this was my solution:

S = apbapb

Where S is a valid string in the language and p is the pumping length.

S = aaaabaaaab for example when p = 4

S = xyz // s can be split into xyz components

| x y | <= p

SO y must be all a's before the first b e.g. a | aaa | baaaab

xy2z = aaaaaaabaaaab

xy2z is not in B

Therefore B is not regular

Apparently though this is wrong, please could someone explain why / how to obtain the right answer?


texts:
Here is a question i came across :

  Given two arrays, write a function to compute their intersection.Here we will allow the duplicates.

  Note:
  Each element in the result should appear as many times as it shows in both arrays.
  The result can be in any order.

  Example 1:
  Input: nums1 = [1,2,2,1], nums2 = [2,2]  --->  Output: [2,2]

we can solve this using Hashing/2-pointer/Binary-search methods.But here is a follow-up question ,

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

How to solve then ??


texts:
The class $C_{1,\epsilon }$ of decision problems solvable by an NP machine such that

If the answer is 'yes,' at least 1/2 and at most $1-\epsilon$ of computation paths reject.
If the answer is 'no,' all computation paths reject.

Is there a name for this class that looks like $RP$?

Is this in $RP$ or $coRP$?

The class $C_{2,\epsilon }$ of decision problems solvable by an NP machine such that

If the answer is 'no,' at least 1/2 and at most $1-\epsilon$ of computation paths accept.
If the answer is 'yes,' all computation paths accept.

Is there a name for this class that looks like $coRP$?

Is this in $RP$ or $coRP$?

What is $C_{1,\epsilon }\cap C_{2,\epsilon}$?

Is it in $ZPP$?


texts:
Is there a processor architecture that falls outside the CISC and RISC categories?

I'm vaguely familiar with RISC and CISC; my research thus far indicates that either a processor is RISC or CISC, with CISC comprising a large number of architecture types. From the wikipedia article about CISC:

  The term (CISC) was retroactively coined in contrast to reduced instruction set computer (RISC)1[2] and has therefore become something of an umbrella term for everything that is not RISC...

Wiki isn't a perfect resource, but the Google Scholar papers I'm finding don't discuss the architecture types in broad terms. Hoping someone can help clarify!


texts:
Is a computer with infinite memory and infinite word size a Truing machine equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) if we allow constant-time linked link element insertion (at the beginning of the list)?
I doubt this because element insertion requires memory allocation and allocation is usually not a constant-time operation.


texts: How to prove semi-decidable = verifiable?

texts:
A language L is verifiable iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗: x ∈ L ⇔ there exists y such that R(x, y)

A language is semi-decidable iff there is some Turing machine that accepts every string in L
and either rejects or loops on every string not in L.

How can we show that the class of semi-decidable problems is equivalent to the class of verifiable problems? Or are they not?


texts:
I have to draw a DFA or NFA for a language that has two symbols lets say {0,1}. The condition is "such that exactly one of the two symbols 0 or 1 appears at least three times." I understood this as if 0 appears three times or more than 1 can be there for 0,1 or 2 times and if 1 appears for 3 times or more DFA fails and goes to dead state. The same will happen for the case if 1 appears 3 times or more and if 0 can be there for 0,1 or 2 times and if 0 appears for 3 times or more DFA fails and goes to dead state. I have been trying to create a DFA for this but failing everytime on condition like "01010". I am not sure if it is possible to create a DFA or NFA for this. I guess this is solvable by PDA only.
Need help in making sure that I am thinking in right direction.


texts:
Given is the following graph which is logically divided into layers (with Dijkstra's shortest paths algorithm):

 Vertices   Layer

    Root      0
   /   \
  A     B     1
 / \    |
C   D   E     2
 \  |  /
  \ | /
    F         3

Now I'm looking for an algorithm which groups vertices when they have a (single) common ancestor in the previous layer, e.g. for the graph in the example the groups would be:

0: A, B
1: C, D
2: E
3: F

I know that this is doable by visiting vertices and comparing ancestors but I was wondering whether there is a well known algorithm for it.

Update: My question is really only related to find groups. I'm aware of the fact, that I can traverse vertices and test for incoming edges and group those vertices. Furthermore, the graph is fully constructed.

One (now deleted) answer mentioned DFS, which creates a search forest (as BFS creates a search tree which I basically used for levels, though I mentioned Dijkstra). So, I assume that combining BFS and DFS could give me the desired result.


texts: Decide whether an $n$-bit positive integer is composite

texts:
Question:

Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP?

I know that for every composite number, a factor of the number is a certificate.
Verification proceeds by dividing the number by the factor and checking if the reminder is zero. My question is whether the verification can be done in  polynomial time of $n$? it seems that we need to use at most $2^n/2 = 2^{n-1}$ factors to test, does that mean we should use exponential time to verify?


texts: Lower bound on $c_n = 4c_{\lfloor n/2 \rfloor} + n$

texts:
Define a sequence $c_1,c_2,\dots$ by the equations
$$ c_1=0, \quad c_n = 4c_{\lfloor n/2 \rfloor} + n \text{ for all } n > 1. $$
Prove that $\frac{(n+1)^2}{8} < c_n$ for all $n \geq 2$.
Hint: $\lfloor \frac{n}{2} \rfloor \geq \frac{n-1}{2}$ for all $n$.

How do I solve this question? I have no idea how to start.


texts: Is closed form of summation less costly?

texts:
I imagine finding the closed form of an algorithm should yield fewer steps than the original. But in the case of a summation from 1 to n, I'm not sure if it actually does.

Here's the original sum

Sum(N)
   total = 0
   for x = 1 to N
       total = total + x
   ret total

Here's the closed form

Sum(N)
    ret N*(N-1)/2

I think the argument is that '*' is only a single operation vs many '+' operations, but I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition.

Please correct me if my above claims are incorrect. My questions are: Does the closed form in this particular case yield fewer steps? Is closed form intended to reduce number of operations on the machine itself, and does it ever do that?


texts: choice of data structure for domino tilings

texts:
A domino tiling is a tesselation of a region in the plane by 2 × 1 squares.  What is a good data type for storing and manipulating such objects?

In my current manipulation, use an array to store all the half-squares numbering them 1-2 for a horizontal domino, 3 4 for a vertical.  It's not ideal but I can draw the tiling in ASCII or using a graphics editor.

     _ _         _ _
1 2 |_ _|  3 3  | | |
1 2 |_ _|  4 4  |_|_|

In some applications, I have to identify specific features within array.  For example, I might have to count all instances of 2 ×2 squares of dominos in my array, excluding things like

 _ _
 _|_   2 1
|_ _|  1 2

These queries are not difficult, but they make me start to question my use of arrays.


texts: Find K largest elements using a priority queue

texts:
Say we have a Priority Queue of size 1000 that is implemented using Max Heap.

Now if i want to get the top 5 elements, the most laid back method is to poll the maximum 5 times, resulting in a set of five maximum numbers. The complexity of a poll function using heap is Log N. Hence, retrieving 5 top values or say, K top values will result in complexity KLogN.

Is there any other way of getting the top K values using priority queue with lesser complexity?

The solution Find k maximum numbers from a heap of size n in O(klog(k)) time seems to increase the complexity rather than decreasing it, which is why i am trying to think about some other logic.  there is a sort function in the logic which will itself consume kLogk for finding one. hence say, for 5 items..it will be k*(kLogK) if K=5? hence, its not decreasing complexity.


texts: Quantum computing - Difference between a binary bit and a Q-bit

texts:
I have recently watched this introductory video on quantum computing where the speaker talks about $n$ Q-bits and the representation of $2^n$ states.

What I didn't get is the word state.How is it different from a classical computer working with $1$'s and $0$s in which each bit can represent 2 states ($0$ or $1$) so that the $n$ bits can generate $2^n$ states.


texts: which paper to take that would best fit to becoming a data scientist?

texts:
My name is Webber from Auckland, New Zealand. I am currently in my second year studying the bachelor of computer and information science. I have chosen to do a double major in computational intelligence and analytics. My goal is to become a data scientist after graduation. I am currently trying to decide which paper to take for the following semester, the options are "physical database design" and "Data structures and algorithms" (I have attached the following images of the paper descriptor for both courses).

My question is, which paper should I choose for the next semester that would be best fit for my goal to becoming a data scientist?

Thank you in advance and I look forward to hearing from you.

Regards
Webber
Inline image 1Inline image 2Inline image 3


texts:
Sometimes I can see the recurrence relationship and other times I cannot. This is one of those times. I've gone through a few iterations of trying to solve it but I also find a set of values where my idea fails. If I go exponenetial I can figure it out... but that's a specific no-no.

I'm good with nudges in the right direction. Please make it a little strong though.

Problem

Suppose it’s nearing the end of the semester and you’re taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: It will be assigned an integer number on a scale of 1 to g > 1, higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects. You have a total of H > n hours in which to work on the n projects cumulatively, and you want to decide how to divide up this time. For simplicity, assume H is a positive integer, and you’ll spend an integer number of hours on each project. To figure out how best to divide up your time, you’ve come up with a set of functions{fi :i=1,2,...,n}(rough estimates, of course) for each of your n courses; if you spend h≤H hours on the project for course i, you’ll get a grade of f_i(h). (You may assume that the functions f_i are nondecreasing: if h' < h, then f_i(h')≤f_i(h).) So the problem is: Given these functions{f_i}, decide how many hours to spend on each project (in integer values only) so that your average grade, as computed according to the fi, is as large as possible. In order to be efficient, the running time of your algorithm should be polynomial in n, g, and H; none of these quantities should appear as an exponent in your running time.


texts: MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size integer array, along an index that maps each substring to the appropriate position of the array. This index has size $1+2+..+n= O(n^2)$. So why the storage cost it is said to be $O(n)$ at the textbooks?


texts: Data structure to store a large power-law graph with constantly updated structure

texts:
I am looking for data structures to store power-law (hence mostly sparse, but few dense too) graphs whose structure is continuously being modified, including new vertices being added and edge weights being modified.

Any pointers on potential data structures and their speed/space complexity will be greatly helpful!

Background info: I will be running iterative variational inference algorithms on the graph - so speed is important. And will be running them on a GPU - so space is important. But I cant yet apriori quantify their ratio (speed:space). So will experiment with different data structures to see what works. My current solution is to use a database (SQL etc) which gets updated continuously on the side by a parallel routine that spits data in COO format, and at the time of running an algorithm, I fetch it into a CSR format. In this case, the graph is not being current and I am not sure if these formats are good for power-law graphs.


texts: In which reference can I find a definition for the equivalence of DFAs?

texts: How is the equivalence of DFA defined?  I found the equivalence of states --- James Hein, section 5.3, page 301.  But he doesn't define equivalence between entire automata.  (Ullman and Hopcropft seem to define neither.)


texts: Fastest search algorithm in a sorted list with certain error rate-limiting constraints

texts:
This problem came up during the Google CTF 2017. For background information about the challenge you can search for GoogleCTF A7 ~ Gee cue elle.

Problem description:

A random number N between 0 and 39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815 (~3.9*10^115 or 64^64) is selected
You have to find the correct number N
You can take a guess X, and get a response whether the number X is greater or lower than N
The twist:

you can only perform 13 guesses in 30s without hitting a 90s timeout - 13/30
if your guess was lower, then you get an error and you can only have 2 errors in 30s without a 90s timeout - 2/30
you have only 2240s time to find the correct value

I had a short discussion with the challenge creator about the solution and he solved it like the broken egg problem. His algorithm basically runs in constant time. As max number is 64^64, he divides the problem in 64 buildings with 64 floors. And a broken egg is an error. This means it takes overall pretty constant 1920s. I think the problem is not equivalent to the egg problem, but somehow the algorithm performs here really really well.

I chose a skewed binary search. Instead of splitting the search field into 50:50, I skew to one side 2/13=0.15 15:85. This way the probability of hitting the punishing error condition is pretty unlikely. My intuition tells me, that this should be the most efficient algorithm, but apparently it's not.

I thought the 0.15 skew would be the best ratio, but after analysing the time it takes with different ratios, the most efficient value seems to be around ~0.22. My calculation is obviously wrong, but what would have been the correct calculation to find ~0.22?

Why does the egg problem algorithm perform better (as in faster on average)?
What is the on average fastest algorithm here? And why is it not based on a skewed binary search?

Any thoughts and comments are welcome.


texts:
Hey guys so I picked up Introduction to the Theory of Computation and started studying finite automata and Turing machines. I was given the following language as an exercise in class, in which I need to build a Turing machine with only one tape and no extra tape space that accepts the following language:
$$\{0^{3^k} 1^p, \text{ where $k > 0$ and $p$ is a multiple of $k$}\}$$
How can one build a single tape Turing machine that accepts this kind of language without using any extra tape space?
I found an example for $\{0^n 1^n\}$ in Introduction to the Theory of Computation but I cannot figure out how to build a machine for the language mentioned above.


texts: Using inductive hypothesis on recurrence relation?

texts:
I have a recurrence relation as follows
$$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$
Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor operator ($\lfloor\cdot\rfloor$).


texts: How to extract the buildings bottom surfaces from a large city 3D mesh?

texts:
I have a 3D mesh comprised of city buildings, no ground surface, just buildings.
The goal is to extract the buildings bottom surfaces.
So far I have tried to cut the mesh by a threshold computed from the vertices height histogram - it works good for relatively flat areas, but fails badly for areas with uneven ground level. Now I'm looking towards some approach based on graph algorithms, but nothing concrete so far. Does anybody have an idea how to solve this problem?


texts:
QUESTION

Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$?

MORE DETAILS

I'm asking this as I want to be able to construct $\overline A$ (the complement of $A$) in poly-space complexity.

More specifically, I want to receive $\left <A,w \right >$ as input ($A$ is an NFA) and decide if $w \in \overline A$. So I want to construct $\overline A$ and simulate (in poly-space) $\overline A$ on $w$.

MY ATTEMPTS

I know that determinizing an NFA (using Subset-Construction) can blow up exponentially. But, I thought that the determinization and/or the simulation can happen "on the fly", where each step overrides the previous one.

Other then this thought, I can't manage to develop it into an actual algorithm (if it's at all possible).

Thank you.


texts: Is it possible to encode logical expression and interpret it with SQL?

texts:
Is it possible without any forms of eval or stored procedures to execute a query, which interprets logical expression, encoded in some way in a table (or two tables) of relational database?

For example, one table can contain a mapping for variable names into their truth values (V1), and another table or two (L1 and L2) - encode logical expressions, eg, in a conjunctive normal form.

Then some clever SQL query will interpret the logical expression from L1-L2, and apply values for variables from V1. (And of course same can also be done for multiple different expressions in the same query).

At first, this seems non-trivial to construct, but SQL has aggregating functions, so theoretically should be possible?


texts:
I was reading that system f-sub (polymorphic lambda calculus with sub-typing) and I was quite confused with its one checking rule called "T-TAPP".

This rule as following (ctx denotes the typing context)

   ctx |- t1 : ∀X<:T11. T12    ,    ctx |- T2<:T11
   -----------------------------------------------
            ctx |- t1 [T2] : [X-->T2]T12

I could not understand how '[x-->T2]T12' will be used (I know it is substitution). This rule appears on page 10 in the following source.
I am looking for two type checking examples, in which above inference rule will be applied and at least one example is a case of type checking failure.

Could anyone provide me with concrete examples?
Description of system F-sub


texts: Is there an algorithm for converting Turing machines into equivalent Lambda expressions?

texts:
We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I'm sure.

But is there an algorithm, a systematic way for us to convert a Turing machine into a Lambda Calculus expression? Is it impossible to have such algorithm? (meaning does it go down to undecidability or NP-Completeness?)
if not, are there any papers or algorithms for doing so?


texts: Graphs that are connected vs strongly connected vs reachable

texts: What is the difference between "connected", "strongly connected", and "reachable" in a graph?


texts: How to show that this problem is NP-hard: Find two subsets of 2 given sets such that the difference between the subset sums is $\leq v$

texts:
As input, given two finite sets of integers $X = \{x_1,...,x_m\}$, $Y = \{y_1,...,y_n\} \subseteq Z$, and a non-negative integer $v ≥ 0$. The goal is to decide if there are non-empty subsets $S ⊆ [m]$ and $T ⊆ [n]$ such that
$$ \left|\sum_{i\in S}x_i-\sum_{j\in T} y_j\right| \leq v$$
How to show this problem is NP-hard? I'm quite confused.
What I got so far is to reduce from subset sum problems, since the form is set to less than v.  So I need to have 2v+1 subset sum problems to verify


texts:
How can I show that the following language is neither semi decidable nor co-semi decidable without using Rice's Theorem?

Further for the following language, how would I show that it IS co-semi decidable but not decidable for |Σ| > 1


texts: Distinguishing between side-by-side liquid streams

texts:
I'm new to computer vision and am looking for advice. I'd like to perform computer vision on a spiral system, in this system a down flowing liquid separates into different regions based on density:

The regions can be visually distinguished based on colour. What I'm hoping to do is automatically detect changes in the average colour of each region, width of each region and perhaps total breakdown of regions.

Could you please suggest which techniques of computer vision would be best for this type of analysis? and would you suggest an approach using Matlab or python + library (any)?


texts: Elimination rule for the equality type aka J axiom

texts:
I'm implementing a interpreter for lambda calculus,
and now I want to add the equality type.
The introduction rule for it is easy,
but the elimination rule is rather obscure for me.
I found this stackoverflow thread, but it explains the J axiom only in one sentence. How can it be understood intuitively?


texts: Can a computable program have an infinite output?

texts:
Can a computable program produce an infinite output from its (presumably finite) input?

*I wouldn't think so for similar argument as to why it can't compute over an infinite input.

A follow on (basically the same?) question: Are there non-halting programs that are computable?

Thanks!


texts: Is it possible to efficiently create a bloom filter with 10^12 buckets on a single machine with 32GB of RAM and a hard drive. We can assume that the keys are already on the disk and are small in size?


texts: Neural network diverging instead of converging

texts:
I have implemented a neural network (using CUDA) with 2 layers. (2 Neurons per layer). I'm trying to make it learn 2 simple quadratic polynomial functions using backpropagation.

But instead of converging, it is diverging (the output is becoming infinity)

Here are some more details about what I've tried:

I had set the initial weights to 0, but since it was diverging I have
randomized the initial weights (Range: -0.5 to 0.5)
I read that a neural network might diverge if the learning rate is
too high so I reduced the learning rate to 0.000001
The two functions I am trying to get it to add are: 3 * i + 7 * j+9
and j*j + i*i + 24 (I am giving the layer i and j as input)
I had implemented it as a single layer previously and that could
approximate the polynomial functions better than it is doing now
I am thinking of implementing momentum in this network but I'm not
sure it would help it learn
I am using a linear (as in no) activation function
There is oscillation in the beginning but the output starts diverging
the moment any of weights become greater than 1

I have checked and rechecked my code but there doesn't seem to be any kind of issue with it.

So here's my question: what is going wrong here?

Any pointer will be appreciated.


texts:
I know that the exact cover problem has a pseudopolynomial algorithm when the cover size is a given constant (as here: Is set cover still NP-complete if you have a given k?).

However, I am interested in approaches to solving a variant of Exact cover (or rather, twice-exact cover, that I asked about here: Solving a variant of the Exact cover problem) that has a solution of a known size that is not a constant, but rather of a known size that is $O(n)$.

The problem arises from reconstruction of the faces of (perhaps non-convex) Polyhedra given their vertices and edges (as detailed in the comments to the linked question), and the known size arises from Euler's formula for Polyhedra $V-E+F=2$ (and therefore I am looking for an twice-exact set cover of the set of edges, with size $F=E-V+2$).

what kind of approaches exist for solving such a problem? (I have thought of some Linear programming approach, but I have had difficulties formulating the conditions, and I do not know how fast would it run).

Thank you in advance.


texts: Number of ways n can be written as sum of at least two positive integers

texts:
I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. The number 5 can be written as

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Here's a solution for given $n$.

# zero-based array (first index is 0)
ways = [1, 0, ..., 0] (n zeroes)

for i in 1, ..., n-1:
    for j in i, ..., n:
        ways[j] = ways[j] + ways[j-i]

print ways[n]

This solution is elegant and efficient, but unfortunately, I do not understand the logic. Can someone please explain the logic of this solution to the problem? Is there a way to make this algorithm easy to understand?


texts: Fastest algorithm for finding the longest palindrome subsequence

texts:
First of all we must read a word, and a desired size.
Then we need to find the longest palindrome created by characters in this word used in order.
For example for size = 7 and word = "abcababac" the answer is 7 ("abababa").

Postscript: the size of the word is smaller than 3000.


texts: Parallel merge sort using hypercube connection template

texts:
I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear.

What I don't understand is how it's applied on the merge sort in §11.4 The point I'm most interested is the parallel_merge function in the pseudocode, i.e. parallel merge algorithm.

The point I'm most interested is the parallel_merge function in the pseudocode, i.e. parallel merge algorithm.

procedure parallel_mergesort(myid, d, data, newdata)
begin
  data = sequential_mergesort(data)
  for dim = 1 to d
    data = parallel_merge(myid, dim, data)
  endfor
  newdata = data
end

Please, explain to me step by step, assuming we have an array of twelve elements $(3,1,5,7,4,2,8,9,4,2,7,5)$ and we've broken this data to four processors like this:

$\qquad ((3,1,5),(7,4,2),(8,9,4),(2,7,5))$.

What data will have each process after each iteration? I understand why we use the hybercube template in this algorithm, but why do we have exactly $i$ compare-exchanges at the $i$-th level? I mean, when $i=1$, we compare-exchange data from processes $1-2, 3-4, .. P-1, P$. That's not $1$, that's $P/2$? Do I misunderstand something?


texts: Branch and Bound running time and golden ratio

texts:
This is a follow up question to When does Branch and Bound exactly stop giving solutions for the bin packing problem

After testing many instances I found out that when r = V / Vtotal <= ϕ (Golden Ratio) the algorithm takes a lot of time to printout the result.

When the ratio r is so close to ϕ , I noticed that : V / Vtotal = (V + Vtotal) / V    (which represents the geometric relationship of the two quantities V and Vtotal in the Golden Ratio).

However, few of the instances having a ratio r > ϕ can take too long to print the results too.

So can this problem be related to ϕ or not?

PS: I got the idea of comparing it to ϕ after checking this answer Lower bound on running time for solving 3-SAT if P = NP


texts: Are subsets of $PSPACE$ closed under common operations

texts:
By "subsets of $PSPACE$" I am referring to classes like $SPACE(n^k)$ for some constant $k$ (e.g. $k = 42$).

Under the union, intersection, and concatenation operations, such subset is apparently closed.

For the Kleene star and polynomial-time reduction, I am not so sure. Here's what I have tried:

To show that $PSPACE$ is closed under Kleene star, assume that some $L \in PSPACE$. To decide whether some input $w \in L^*$, we can non-deterministically split the $w$ into $i$ chunks ($1 \leq i \leq n$, and $i$ is chosen non-deterministically), and check if each chunk is in $L$. If that check can be done in $O(n^k)$ space, this whole procedure can be done in $NSPACE(n^k) \subset SPACE(n^{2k}) \subset PSPACE$ (the first inclusion is by Savitch's theorem). In a similar manner, I tried to show that a subset like $SPACE(n^k)$ is NOT closed because $2k > k$.
To show that $PSPACE$ is closed under polynomial time reduction, suppose some $L_2 \in PSPACE$ and some $L_1 \leq_p L_2$. Since the reduction is in polynomial time, it uses at most polynomial space, so $L_1 \in PSPACE$. I tried to show that something like $SPACE(n^k)$ is NOT closed under polynomial time reduction by saying that the reduction might runs in $O(n^j)$ time and $j > k$, then the whole process will use at most $O(n^j)$ space, which is no longer in $SPACE(n^k)$.

My doubts:

For the Kleene star closure proof, we can't guarantee that deciding $L^*$ will necessarily use $O(n^{2k})$ space, since we don't have $NSPACE(n^k) = SPACE(n^{2k})$.
For the polynomial time reduction closure proof, such a $O(n^j)$ space reduction exists, but it might not actually uses more than $O(n^k)$ space.

I can't really convince myself one way or the other, so any help is appreciated.


texts: Why does NTM need to derive certificate to prove "If a language is in in NP iff it is decidable by some nondeterministic polynomial time TM"?

texts:
(Sipser's Chapter 7: Time COmplexity, Pgs 294-295)

If we have to prove the forward direction, then we must have the certificate along with the verifier. I don't get why we are "guessing the certificate"--essentially constructing the verifier-- if we already know one exists.

On the other hand, if you don't have the certificate, you can use a NTM to derive it and check w against c. So you don't need to pass any input into V. So V is useless.

I don't really understand this proof.


texts: Is asking a LL(1) parsing table for this grammar a trap?

texts:
I'm trying to solve some exercises for the upcoming Compilers' exam.
Teacher gave us some sheets from previous exams to practice with - no answers provided.

  Let $\mathcal{G}$ be the following context-free grammar:
  $$
\begin{aligned}
A &\to BC \\ B &\to aD\; |\; bD \\ C &\to BCC \; | \; aCd \; | \; \epsilon \\
D &\to aD \; | \; bD \; | \;\epsilon
\end{aligned}
$$
  Provide the LL(1) parsing table for $\mathcal{G}$.

Ok. Before rushing into the construction of the table, I've asked myself: is this really a LL(1) grammar? A quick look at the definition of the grammar is already telling me that probably it is not. The dragon book gives the following criteria for establishing whether a cfg is LL(1):

  A grammar $\mathcal{G}$ is LL(1) if and only if whenever A → α | β are two
  distinct productions of $\mathcal{G}$, the following conditions hold:

  FIRST(α) and FIRST(β) are disjoint sets;
  if ε is in FIRST(β), then FIRST(α)  and FOLLOW(A) are disjoint sets;
  likewise if ε is in FIRST(α).

What caught me first was the production rules for nonterminal $C$, so I computed the first sets involved in them:

$$
\begin{aligned}
\mathrm{FIRST}(BCC) &= \mathrm{FIRST}(B) = \lbrace a, b \rbrace \\
\mathrm{FIRST}(aCd) &= \lbrace a \rbrace \\
\mathrm{FIRST}(\epsilon) &= \lbrace \epsilon \rbrace.
\end{aligned}
$$

Of course, at least two of these sets are not disjoint, so it follows that the grammar is not LL(1).

How shall I proceed? Does this suffice as answer, or shall I provide an equivalent LL(1) grammar with its parsing table? What would you do?


texts: I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've started by using BFS (breadth-first search) to find the shortest path from v to another vertex u, and then running BFS again to see if an alternate path can be found from v to u. I think this is too time consuming however. Does anyone have any hints as to how the solution can be found with a shorter execution time?


texts:
Consider the decision problem Bip[3–1], define as follows:

Instance: $G = (S,T;E)$, bipartite graph, with $d_G(s) = 3$ for all $s \in S$.
Question: Does there exist $S' ⊆ S$ such that in $H = [S'∪T]_G$ we have $d_H(t) = 1$ for all $t \in T$?

I should prove that 3SAT reduces to Bip[3-1].

I understand what the problem says, but I don't know how such relations could be proved, and neither have I found any decision problems similar to this.

Would appreciate any help.


texts: How does BIRCH (Balanced Iterative Reduction Using hierarchical) CF Tree insertion algorithm work?

texts: I am studying Cluster Analysis and I came across BIRCH (Balanced Iterative Reduction Using hierarchical) http://en.wikipedia.org/wiki/BIRCH_(data_clustering) CF Tree insertion algorithm. I am confused what does branching factor(B), threshold for diameter of cluster in a leaf(T) means and in general how the algorithm works. It will be of immense help if someone can please explain it using an example. Thanks in advance.


texts: How many possible prime implicants are there in total for a 4-variable Karnough-map?

texts: The answer for this question is 81. But I count figure out why. Can someone explain to me how does this work. Thank you.


texts: predictor/corrector and gear integration for positive and negative time steps

texts:
I have a predictor method that takes differential equations for 214 biological species and integrates them in time using positive time steps. Right now it is able to successfully integrate the differential equations when the time step is positive, so  it can integrate forwards in time and I was looking to see if it could be integrated backwards in time.  By that I mean I was looking to see if the differential equations could be integrated using a negative time step, based on using the following method for integrating the differential equations.

The predictor method uses the forward Euler equations for each species in order to predict its value at the next time step.

The corrector method uses the trapezoidal rule.  So the predictor-corrector method is based on Heun's method.  It also uses three terms in the gear integration method which is implemented alongside Heun's method.

So I was wondering, is it possible to use this integration with a negative time step, thereby integrating the differential equations backwards in time?

Essentially, I am integrating the differential equations with boundary conditions at time $t = 0$ and using a time step $\Delta$t such that $\Delta$t $> 0$.  So I was looking to see if the integration method I used above could work if I used the same boundary conditions at time $t = 0$ and used a time step such that $\Delta$t $< 0$.  This step size is also denoted as $h$ in various explanations of predictor corrector methods as shown here:  https://en.wikipedia.org/wiki/Predictor%E2%80%93corrector_method

If it can be done, how would I go about doing that?


texts: Kosaraju with connections between SSCs (strongly connected components)

texts:
First of all I did find similar questions here on Computer Science but nothing what would provide real answer for this problem.

I have a graph which i condense into SSC (strongly connected components) by Kosaraju's algorithm. Now what I need is to find connections between those SSCs. The best would be to somehow inject this process into Kosaraju's runtime but I did not come up with tangible solution there. My algorithm is logically similar to the one on wikipedia: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm (I can't provide my code because it is a school assignment)

I would very much appreciate any tip from smarter folk than me. :D

More information/What I came up with:
I thought about it and did not come up with better solution then after finishing Kosaraju I will go through each vertex, check his in/out edges and if the edge's other side is not part of this SSC than add this edge as connecting edge to my SSC. But this process is very expensive as i need to:

For each vertex go over its all edges
Compare every edge end with vertexes in SSC.

Computation would be something like edges X [vertexes in its SSC]. If my graph would be one huge SSC than I would basically get V*E. There is no way this is best approach, I bet it is actually one of the worst.


texts: Get nodes that are participating in any cycle in a graph

texts:
I have a problem that states the following :

  Given a cyclic graph , output for each node if the node removes all cycles in the graph.

The most trivial way to do this is using a Union-find disjoint set , and for each node , try not putting it in the Union-find disjoint set , if there are no cycles , then this node should output "Yes" , otherwise "No".

This approach would take about $\Theta(N^2)$ time and $\Theta(N)$ memory.

The problem also stated that $N \leq 1,000,000$ which would definitely get a TLE (Time Limit Exceeded) Answer on any problem.

So, my question is, What's the algorithm that would take $\Theta(N \lg N) $ or $\Theta(N)$ time and $\Theta(N)$ memory?


texts: How to approach DFA construction with substring constraints?

texts:
We have to construct a DFA over the alphabet 0 and 1 for:

  Every substring of four symbols has at most two 0's. For example, 001110 and 011001 are in the language, but 10010 is not since one of its substrings, 0010, contains three zeros.

I haven't reached to regular expression in the book which I am using. I am currently in unit 2 and regular expressions is from unit 3.


texts: I have a model counting program bob.  On some graph coloring formulas, bob got the right answer only after removing clause learning.  That is to say, with clause learning, bob sometimes counts duplicate solutions, while satisfiability remains stable.  This would be big news if true.


texts: Can every DFA be converted to an equivalent one that has a single accept state

texts: I know that it is true for NFAs. It seems similar.


texts: Is there a difference between the name scheduler and scheduling?

texts: Sometimes I read about the term "scheduler" (offline-scheduler, online-scheduler,...) and then I see terms called "scheduling" (offline-scheduling, online-scheduling, preemptive scheduling, non preemptive scheduling). Currently I think, that scheduling is the real work and scheduler is just a umbrella term. Is that correct ?


texts: Characterisation of graphs that are not 3-colorable

texts: We know that all graphs with odd cycles (odd number of vertices) are not 2-colorable. Is there a similar characterisation for 3-colorability? I am looking for undirected graphs that are not 3-colorable depending on a single graph property e.g. vertices/edges parity or anything else that can be generalised.


texts: How did they cancel out O-terms in this fraction?

texts:
While reading a book about algorithms, I came across this derivation:

$$
\frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)} =
\frac{2\ln(2N) + O(1)}{\ln N+O(1)} =
2 + O\left(\frac{1}{\log N}\right).
$$

Could somebody please explain to me how we went from the left to the right?


texts:
I have this algorithm ("cyclic sort") to sort an array which contains unique numbers from 1 to $n$:

Input: A[1], ..., A[n]
i ← 1
while i ⩽ n:
  j ← A[i]
  if A[i] ≠ A[j]:
    swap A[i] and A[j]
  else:
    i ← i + 1
  end if
end while

How can I prove that in worst case, the running time of this algorithm is still asymptotically $O(N)$?

My observation:

Although $i$ will not increase right after each swap, when it does increase, the next number of required swaps will also decrease.
The maximum number of swaps at $i = 1$ will be $N-1$.

Second question is: Is the running time still $O(N)$ if it contains duplicate numbers?


texts:
What is the optimal way to cut B chocolate bars to share equally between N people?

Here is an example of different cuts for B = 5 chocolate bars and N = 6 people.

Strategy 1: cut each chocolate bar in 6 equal parts and, then, give 5 parts for each person. Number of cuts: 5 x 5 = 25.

Strategy 2: cut 3 bars in 2 equal parts and cut 2 parts in 3 equal parts and, then, give 1/2 bar and 1/3 bar for each person. Number of cuts: 3 x 1 + 2 x 2 = 7.

What is the optimal solution for the general problem?

Thanks, Humberto.


texts: Are combinatory logic terms always larger?

texts:
So there is an algorithm to convert lambda calculus terms to combinatory logic using SK combinators. It produces things that explode in size. I would like to know more about this explosion in size. I can't seem to think of a better algorithm however. I have heard of functional languages being practically compiled to combinators so it seems that a better algorithm must exist. I looked up David Turner's paper on the topic and he basically just says to apply a few optimizations and that they cause a "considerable improvement".

Does "considerable improvement" mean that the size drops to only a polynomial increase? Is there a known way to convert lambda terms to combinatory logic with only a polynomial (or less?) increase in size? If such an algorithm exists is it practical?


texts:
Disclaimer: I'm not a compiler expert.  I'm simply curious and come seeking enlightenment.
I've seen people claim that -- for efficiency -- for loops should generally use a zero comparison for termination.  So rather than:
void blink1(int n) {
    for (int i=0; i<n; i++) {
        blink_led();
    }
}

you should write:
void blink2(int n) {
    for (int i=n; i>0; i--) {
        blink_led();
    }
}

I thought that was a little silly: why put the burden on the human if a compiler could interpret both cases as "blink_led() n times"?
But using Mr. Godbolt's Compiler Explorer, I now think I'm wrong.  For all the compilers I tried, the "compare against zero" always produced a shorter loop.  For example, x86-64 gcc 10.2 with -O3 optimization produced the following inner loops:
blink1:
    ...
.L3:
        xor     eax, eax
        add     ebx, 1
        call    blink_led
        cmp     ebp, ebx
        jne     .L3

vs
blink2:
    ...
.L12:
        xor     eax, eax
        call    blink_led
        sub     ebx, 1
        jne     .L12

So here's the question
This seems like such a common case.
Why can't (or why doesn't) the compiler notice that the effect of the for loop is simply "do this thing N times" -- whether counting up or counting down -- and optimize for that?


texts: How is readiness of instructions fetched from RAM signaled to the CPU?

texts:
In simple CPU architectures, such as the one discussed here https://youtu.be/zltgXvg6r3k?t=109, an instruction loaded from RAM is executed exactly one clock cycle after it is loaded into the instruction register. This fact is key to the whole architecture working.
However, I am told that in real/modern architectures it takes hundreds of clock cycles to fetch instructions from RAM (using caches in between). But that completely throws off my understanding of how things work. I am told that often or ultimately the CPU has to undergo "pipeline stall", but I can't find any schematic description of how stalling works, or how the CPU is signaled to re-commence once the instruction from RAM has been fetched at some indeterminate number of future clock cycles.
Could someone please outline the techniques/processes that enable instructions ordered from RAM to get executed after some indefinite number of clock cycles in the future?


texts: Why do we use several bits instead of a single bit for storage of objects in Bloom Filters

texts:
Bloom filters are a variant of hash tables except it is much more space efficient at the cost of a low probability of false positives .

How it works : Assume there are 10000 bits , 3 hash functions and an object Foo is to be inserted into the Bloom Filter .

Insertions : Foo will be hashed by the 1st hash function and the 3405 bit index is set to 1 , Foo is hashed by the second hash function and the 1001 bit index is set to 1 , Foo is hashed by the third hash function and the 5555 bit index is set to 1 .

Check exist : Foo will be hashed to the three different hash function and if all the bits at the respective index is set to 1 , the object is said to exist with a small chance of false positive else the object cant be found .

My question is : Why do we use more than 1 (in this case 3 bits ) to determine if a objects exist in the Bloom Filter , doesnt it increase the chances of collision with other objects which may also set the same bit to 1 . To me , it seems best to use a single hash function as it saves the most space (1 bit only) and least chances of collision with other objects in the Bloom Filter


texts: Is the random forests algorithm Turing-complete? As in, can any algorithm be represented by a given "tree" in the forest?


texts: Is Kalman filter used in automata (besides cellular automata) and parsing grammars?

texts:
I am new to Kalman filter and parsers. I understand that it's suitable for prediction/estimation on the go, when you have something to measure (not only the model), and when changes always occur in the measurement or model.

However, for the case of finite automata, pushdown automata, or grammars, usually the automata or grammars do not change. However, I found papers combining Kalman filter and fuzzy automata, or Kalman filter and cellular automata.

Does this means Kalman filter is not suitable to be used in finite/pushdown automata or context-free grammars, unless those models are equipped with fuzziness, probability, or weights?

Is there any parser or parsing method using Kalman filter? I would appreciate it very much if you share your wisdom about why it's used or not used.