texts: Proving $\{0^{2^n}\}$ is not regular using pumping lemma

texts:
I am currently learning the pumping lemma, and encountered the following question, which I am unable to solve:

Prove that $L = \{ 0^n \mid \text{$n$ is power of 2}\}$ is not regular.

I considered $w = 0^{2^n}$, where $n$ is the pumping lemma constant. Then I divided $w$ into $xyz$, where $y \ne \epsilon$ and $|xy| \leq n$. Hence, $|y|$ will be between 1 and $n$. So, $|xy^kz|$ satisfies $L$ if $|y| = 2$ for all values of $k$ and it is within the bound. So, how is $L$ irregular?
The question is to prove it is irregular but here it is coming as regular.


texts:
Given: A rooted, directed, a-cyclic graph $G$. Let $r_0$ be the root node and $t_0$ be another target node. Each node in $G$ is assigned a non unique id/color ($ID_i),\ 1<i<N$ for some integer N.

Problem: Is there a directed path from $r_0$ to $t_0$, such that for some $ID_x$ there is no node in that path with $ID_x$ as its $ID$. In other words, the nodes in the path do-not cover all the $IDs$.

Comments: Clearly the problem is in $NP$ since if we are given such a path we can easily verify it. I suspect the problem is also in $P$ and can be solved in polynomial time. But, I am struggling to find an algorithm for the same.

Can someone please help with this?


texts:
$\Sigma^* - \{\epsilon\} = \Sigma^+$

  $L^* - \{\epsilon\} = L^+$

  Which of the above is always true?

I was following a discussion on a site and I came across this question. Some fellow scholars claimed that the second statement is not always true.
The answer they provided is this:

  $S_1$: $Σ^* – \{ϵ\} = Σ^+$: TRUE  // Always true, definition of $Σ^+$

  $S_2$: $L^* – \{ϵ\} = L^+$: FALSE // May or may not be true

  False when $ϵ$ belongs to $L$, then $L^+$ and $L^*$ will both contain $ϵ$.

  PS: In $S_2$, it depends purely on the given language.

But I have this doubt:

How can $L^+$ contain $ϵ$? we obtain $L^+$ by deleting $ϵ$ from $L^*$, and in $L^*$ of the language where $L=\{ϵ\}$, $L^*$ will only contain $ϵ$, so if we remove $ϵ$ from it, then the language should become $\emptyset$, which is nothing but $L^+$ here. So shouldn't the second statement also be true?

Say $L^+  = \{ϵ,ϵϵ,ϵϵϵ,\dots\}$.

Now an important point. Note that we say Set of all strings, now in set theory duplicates are not allowed, moreover $ϵ= ϵϵ =ϵϵϵ =\dots$. They are all just the same. So $L^∗$ should be only $\{ϵ\}$, rather than $\{ϵ,ϵ,ϵϵ,ϵϵϵ,\dots\}$, right?


texts:
I have the following interface:

public interface TreeElement<T>{
    public List<TreeElement<T>> getChildren();
}

Now, suppose I have a collection of TreeElement<T> representing a valid tree. How to find it's root element? Is there something more efficient than iterating over the whole collection?


texts: What is the general class of this algorithm?

texts:
You have an array of N numbers. Find all the numbers that occur more
  N/5 times in the array.

This can be obviously done in O(n log n) time and O(1) space, or O(n) time and O(n) space, but the catch is that it can be done in O(n) time and O(1) space.

After hours of thinking I found the solution, which is absolutely the same as described here (and it is not hard to extend it for M times).

My question is: does this problem belongs to some general class of algorithms? and what kind of similar problems are there? Like dynamic programming, greedy or recursion (these are clearly wrong classes)?

I was looking at the streaming algorithms, but it does not look this is the case.


texts: Competitive ratio of this paging algorithm

texts:
In the paging problem, we have a cache of size $k$ and a universe of $n>k$ pages.

In an online setting, we get requests for pages $p_1,p_2,\ldots p_t$, and are required to have page $p_i$ loaded at the cache at time $i$.

Our goal is to minimize the load cost; that is, we pay a cost every time a page is loaded into the cache, and thus we aim to maximize the "cache hits".

In the unweighted case, where each load costs 1, the LRU algorithm achieves a competitive ratio (CR) of $k$, which is known to be optimal for deterministic algorithms.

Next, consider the weighted case, where each page $i$ has a loading cost of $c_i$, and the goal is to minimize the sum of loading costs.

There are known algorithms for this problem which also achieve a CR of $k$, but I couldn't find this next algorithm, and was wondering what's its CR (especially since its much simpler than the two algorithms I know which achieve a $k$ competitive ratio).

We initialize a "marking" bit for each cached page to be $0$.
Upon request for a cached page, set its bit to $1$.
Upon request for an uncached page, evict the smallest weight page with bit $0$ from the cache, and insert the arriving one with bit $1$.
If all of the cache bits are $1$, set them all to $0$.

  What is the competitive ratio of the above algorithm?


texts: I'm reading a paper about constraint satisfaction problem and found a term "binary Max and binary Min" operations but I dont know the meaning. If someone know could you please explain for me? I googled it but didn't find nothing.


texts: Alternatives to phi nodes in static single assignment

texts:
I have read somewhere about an alternative SSA representation that doesn't use phi nodes but instead uses parameterized basic blocks.

Something like this in an SSA with phi:

block_a:
    value_a = ...
    jump block_c
block_b:
    value_b = ...
    jump block_c
block_c:
    value_c = phi (block_a: value_a), (block_b: value_b)
    ...

Would look like this in SSA with parameterized basic blocks:

block_a:
    value_a = ...
    jump block_c(value_a)
block_b:
    value_b = ...
    jump block_c(value_b)
block_c(value_c):
    ...

My two questions are:

What is this called?
What other alternatives to phi nodes exists in SSA?


texts: Calculating modulus of large non-factored numbers

texts:
The internet is full of algorithms to calculate the modulo operation of large numbers that have the form $a^e \bmod p$. How about numbers with unknown factorization. More precisely, let's say I have a 4-byte sized modulus prime $p$, and a large number $a$ stored in memory as an array of bytes, that is, $a = [a_{k-1}, a_{k-2},\dots, a_0]$, where $ k \gg 4$.

How to calculate the modulo operation $a \bmod p$ efficiently?
Please, cite a reference for your algorithm if it is possible.


texts: Applying Brewer's theorem (CAP) to a single node

texts:
I'm going through Brewer's theorem and its proof by Nancy Lynch and Seth Gilbert. But the paper left me with one question. What prevents the theorem from being applicable to a single node?

I haven’t encountered any explicit definition of network partition that restricts its applicability to a network. There are some hints in [1] that suggest that a network partition with a single node would mean cutting off all communication to that node itself. This doesn’t make a whole lot of sense to me because you could always have a partition with all the service nodes on one side and the client node on the other. No service could possibly tolerate that.

A single node data object can be consistent and available if requests sent to it get through. To me, the definition of a network partition and where it applies leaves something to be desired. What am I missing here?

[1] Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services by Seth Gilbert and Nancy Lynch


texts:
Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (Foldable being one example).

There is one obvious way in which using monoids can be used to improve performance: the programmers is asserting the operation's associativity, and so operations can be parallelized.

I'm curious if there are any other ways a compiler could optimize the code, knowing that we're dealing with a monoid.


texts: Using a point as an input for a perceptron

texts:
Can a point be used as the input for a perceptron/neural net?

The relationship between the two numbers that make up a 2D point does not affect the output, but does this not matter when the satisfactory weights are found?

If I wanted to use a point $(x,y)$ as an input for my perceptron, would I simply have two input nodes, one for $x$ and one for $y$?


texts: Can a CPU be replaced without interrupting the processes running on it?

texts:
When I need to replace the CPU of my computer, I turn it off, replace the hardware, then reboot it. But what if you need to replace the CPU (in a single CPU machine) without stopping the processes running on it?

Is that possible, and if so, how?

This is a theoretical question. It doesn't matter if the procedure is complicated and impractical or cost-intensive.


texts: Is there a language for which any string (that works) can be shown to not be pumped using the Pumping Lemma?

texts:
Of course, whenever the Pumping Lemma for Regular Languages (or CFLs) is applied to a language $L$, only a single string $w \in L$ and $|w| \ge p$ needs to be picked (to eventually show that $w$, when pumped, leaves the language).

Is there a non-regular (or non-context-free) language $L$ for which every string $w \in L$ having $|w| \ge p$ can be used to derive a contradiction?


texts: understanding constraint satisfaction problem: map coloring algorithm

texts:
I am trying to implement this recursive-backtracking function for a constraint satisfaction problem from the given algorithm:

function BACKTRACKING-SEARCH(csp) returns solution/failure
    return RECURSIVE-BACKTRACKING({},csp)
function RECURSIVE-BACKTRACKING(assignment,csp) returns soln/failure
    if assignment is complete then return assignment
    var <- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
    for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do
        if value is consistent with assignment given CONSTRAINT[csp] then
            add {var = value} to assignment
            result <- RECURSIVE-BACKTRACKING(assignment, csp)
            if result != failure then return result
            remove {var = value} from assignment
    return failure

The input for csp in BACKTRACKING-SEARCH(csp) is a csp class that contains a) a list of states, b) the list of colors, and c) an ordered dictionary with a state as the key and the value is the list of neighbors of the state that cannot have the same color.

The problem is that I am having a hard time understanding how the algorithm works correctly. If anyone can give me a proper explanation of this algorithm, it would be very much appreciated. Some specific questions I have is:

    if assignment is complete then return assignment

I assume that since assignment is inputted as an empty dictionary {}, that this will return the solution, that is, the dictionary that contains states and their colors. However, I don't understand how I can check if the assignment is complete? Would it be something like checking the size of the dictionary against the number of states?

    var <- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)

The input csp class contains a list of states, I assume this could just be var equal to popping off a value in the list? I guess, what's confusing me is I'm not sure what the parameters (VARIABLES[csp], assignment, csp) are doing, given my input.

    for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do

Again, confused on what the inputs of (var, assignment, csp) are doing exactly. But I assume that it'll go through each value (neighbor) in dictionary of the state?

        if value is consistent with assignment given CONSTRAINT[csp] then
            add {var = value} to assignment
            result <- RECURSIVE-BACKTRACKING(assignment, csp)
            if result != failure then return result
            remove {var = value} from assignment

How do I properly check if value is consistent with assignment given constraints[csp]? I assume that constraints should be something that should be apart of my csp class that I haven't implemented yet? I don't understand what this if statement is doing in terms of checking. It would be quite useful if someone can clearly explain this if statement and the body of the if statement in depth.


texts:
I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min vertex cover problem instead of the decision version of the vertex cover problem. The problem I am having with reducing from the decision version is that a vertex cover of size k maps to the $Y$ of size $ \leq ck$, where $c$ is a constant. A decision version for problem $Y$ for me makes no sense, as there will always be a brekpoint distance between two genomes. I tried to research on the internet but I always only find reductions from decision problems. Could we reduce from non-decision problems.

Also when doing reductions from the vertex cover problem. I can't assume the given instance $G,k$ is such that k is the size of the optimal vertex cover right? $k$ is just any size of a Vertex cover.


texts: Is there any importance in problems whose witness for membership in a set, cannot be bounded by a polynomial?

texts:
The class NP can be defined as a polynomially bounded relation $R$. Where $x \in R$ if there exists some $y$ that has length bounded by $p(|x|)$, where $p$ is some polynomial.

Why do we not study the case where $y$ is not bounded by a polynomial?
Is there any significance in problems of this nature; in-efficient proof systems?


texts:
I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how to interpret it. It runs as follows:

  Let $\Gamma$ be a group and $S$ be a subset of $\Gamma$ not including the
  identity element. Suppose that the inverse of every element in $S$ also
  belongs to $S$. The Cayley graph of $\Gamma$ with respect to $S$ is the graph
  $CG(\Gamma, S)$ with vertex set $\Gamma$ in which two vertices $x$ and $y$ are
  adjacent iff $xy^{-1}\in S$.

Okay. I follow so far.

  Recall that the n-cube is the graph whose vertex set is the set of all
  n-tuples of 0s and 1s, where two n-tuples are adjacent if they differ
  in precisely one coordinate.

Makes sense.

  Show that the n-cube is a Cayley graph.

What does it mean to talk about "$xy$" when $x$ and $y$ are n-tuples? What is the inverse of an n-tuple?

Someone I asked about the problem suggested that I treat $\Gamma$ here as the additive group $({\mathbb Z}/2{\mathbb Z})^n$, and so take $xy^{-1}$ to mean elementwise subtraction of $y$ from $x$, mod 2. But then it seems like $(0, 0, ..., 0)\in\Gamma$ and, since it's the identity element, every vertex will have an edge connecting to it, and that isn't what the n-cube looks like. Googling, I also see that there is an interpretation of tuples as nested sets, but then I don't see how the product of two nested sets would ever be in S, since it will have a different cardinality from either of the original tuples. Interpreting the tuples as vectors can't work either since then $xy^{-1}$ will have different dimensions than either of the original tuples.

What is this question asking?


texts: What is branch factor for beam search in RNNs like TensorFlow's Magenta?

texts: TensorFlow's Magenta melody generation module has a parameter for branch_factor1. What is it?


texts: Calculate the complexity of an algorithm

texts:
I have an algorithm here and it wants me to calculate the complexity:

for (i=1;i<n;i++)
  for (j=1;j<i*i;j++)
    if (j%i==0)
       for (k=0;k<j;k++)
          sum++;

First of all, I think that i have different complexities for best, average and worst case but I don't know how to find them. I have one though and I said that in the best case I will have the 2 fors and count as operation the 'if'. So i have a double sum (ΣΣ 1) with bounds being the values of i,j in the for loops. That's all i did.


texts: Combining Ontology and Relational Databases in Question Answering system

texts:
I'm introducing to the Natural Language Processing field and it's application. I'm planning to build a question answering system for a project, but some approaches are making me a bit confuse about the use of ontologies and it's application on the architecture of the system. I understand that an Ontology in definition is a way to represent concepts, relations about certain domains allowing semantic annotations also.

Some approaches uses an Ontology like a database, in which user's input (In natural language) is transformed to a SPARQL query by semantic parser and then the knowledge is retrieved of the ontology...But then, I asked my self if Ontology usually is a static knowledge that rarely changes and I want my system can increase knowledge of the domain with new instances or concepts because there are other systems (this is only a module of a big system) that probably are going to need data about instances present in the ontology to retrieved some specific attributes that could change over time... then, relational database comes to mind... And instead of using an ontology as a  big database for whole project, why not to build a relational database with the instances of the domain where attributes can change dinamically and add new ones without make constantly in the ontology... So I could develop an ontology that represent the schema of the database, so I can map the natural language query of the user with the terms present in the ontology so I transform it to a SQL query which then I'm going to retrieved the answer in a relational database... I need to figured out how to parser instances of the ontology in the database with this approach.

Could this approach be correct ? I mean, using the ontology as a intermidiate between user query and relational database? , the only problem I see with this approach is that I need to figured out how to link instances of the database in the ontology ..

Thanks for your help,
Greetings.


texts:
I'm currently working on a static analysis work in which I need to check whether a given formula is met or not. I hope the following example clarifies my requirement.

Suppose we have a list of three-addressed expressions whose operators are simple arithmetic and bit-wise operators (such as add, sub, and, xor). Each expression could have constant literals or variable symbols. For example, consider the following list:

a = b + 1
c = d
c = c xor d
a = a + c
a = a + 4

What I need is that to see whether a given formula is established or not. For example, the following formulas:

a == b + <some_constants>   # In this example: Yes, because a == b + 5
a == d + <some_constants>   # In this example: No

So can a SMT solver (Z3 for example) help me in this situation? If not, could you please point me out if there is a suitable tool applicable for this requirement?


texts: Enumerating the List of `nPr` (n Permute r) objects

texts:
I have been using MATLAB for a particular project, and have seemed to find a function that may or may not exist. This question isn't MATLAB specific, more algorithm specific.

I have a list of 12 items, indexed from 1 to 12. I want to be able to create a list of all possible permutations of these 12 items where I only want to select 6 of them per entry.

Here is a reference to what nPr is for those unfamiliar.

In MATLAB, there is a function called perms(A) such that it calculates nPn where n = A.length. However what I am looking for is nPr where n = 12 and r = 6. Is there a way to either

Exploit the perms function such that it does nPn such that n = 6, but in a way that it actually calculates nPr where n = 12 and r = 6.
Write a recursive algorithm to replace the perms(A) function and create a perms(A,r) function?

Any pointers or tips would be much appreciated and helpful.


texts: Facebook Hackercup 2013: Balanced Smileys

texts:
On Facebook HackerCup 2013, they asked the following question:

  Your friend John uses a lot of emoticons when you talk to him on
  Messenger. In addition to being a person who likes to express himself
  through emoticons, he hates unbalanced parenthesis so much that it
  makes him go :(

  Sometimes he puts emoticons within parentheses, and you find it hard
  to tell if a parenthesis really is a parenthesis or part of an
  emoticon.

  A message has balanced parentheses if it consists of one of the
  following:

  An empty string ""
  One or more of the following characters: 'a' to
  'z', ' ' (a space) or ':' (a colon)
  An open parenthesis '(', followed
  by a message with balanced parentheses, followed by a close
  parenthesis ')'.
  A message with balanced parentheses followed by
  another message with balanced parentheses.
  A smiley face ":)" or a
  frowny face ":("

  Write a program that determines if there is a way to
  interpret his message while leaving the parentheses balanced.

Balancing parentheses is talked about in a lot of places.  E.g. (()) vs ()().  You can count

'(' = +1
')' = -1

Then you have to make sure your sum never falls below 0.

In this question they consider :) and :( as balanced and I wonder how much it changes things. One solution says that you can replace r'[^a-z:() ], '', ':)' -> '}' and ':(' -> '{'.

While I agree with the first sub, why are the last two substitutions valid?


texts: building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }

texts:
$\{a^p; p$  is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \}$
I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ is. Is there a way to draw the NFA regardless?


texts: How do you say when a language is Turing-complete only in a trivial way?

texts:
I didn't know how to ask this question before but now that I'm reading about typed lambda calculus I think I've got a better idea.

There is this answer to a question asking whether CSS is Turing complete or not (note that this question is NOT about CSS at all), which I consider is not (at least in certain way, and this "certain" is what my question below is about), even if you can simulate Rule 110 with it, which is proven to be Turing complete. My intuition behind it is that only an insignificant subset of what CSS can output can be the result of a calculation. You cannot perform any calculation on colors or sizes to be set to element's styles.

Now I found an even simpler example while reading about typed lambda calculus. This article's overview describes a lambda calculus that can use booleans. I noticed that, in addition to the untyped lambda calculus operations, there is the conditional operation (if t1 then t2 else t3), which makes perfect sense. Without this, you wouldn't be able to do anything with booleans, and I would go ahead and say is really not Turing complete, or at least that is Turing complete but only in a trivial way.

So my question is, if this typed lambda calculus with booleans wouldn't have that conditional operator, would you say is Turing complete? If not, why not, and if yes, how would you express the fact that you cannot do any operation at all on it's main type of data which is what you'd expect from any Turing complete language in a categorical, technical way such that is clear that the Turing completeness of the language is really meaningless?

The reason why I'm giving so much importance to this is because I was recently trying to create a small Turing complete language myself and while doing it, got to a point in which my language was Turing complete but only in this trivial way (wasn't as obvious as the boolean lambda calculus without conditionals above, though). If I would have asked "Is this language Turing complete?" I would have probably got "Yes" as an answer and I would've think I'm done creating my language. But I really was not. And when asking myself why am I still working on my language, I'd like to be able to state exactly what is that my language is missing.


texts: Calculating the classification threshold efficiently

texts:
I have a multi-label classification problem, in which each input sample has a set of zero or more output labels.

I have a multi-class classifier which, for every input sample, returns a certain score for each of the output labels.

One way to use this multi-class classifier for multi-label classification is to calculate a threshold score, and select for the output all labels that get a score above the threshold.

My question is: what is the most efficient way to calculate the threshold score?

Currently we use the following scheme:

Train the multi-class classifier on 90% of the training set.
Run the base multi-class classifier on the remaining 10% of the training set (which we call "development set"). Keep all the scores in a large array.
Create a set of all scores that are returned by the base multi-class classifier for any input and any label. Call the set $S$.
For every score $s \in S$, and for every input sample in the development set, calculate the positive labels returned when the threshold is $s$. Compare to the gold-standard. Calculate the precision, recall and $F1$.
Select the score $s_max$ that yielded the maximum $F1$.

This is not efficient because there are many different scores and the method is linear in the number of different scores.

We plotted the $F1$ against the scores and noticed that this is a concave function - it has a single maximum. So, we thought of using binary search to find the maximum point. But, we are not sure that the function will always be concave.

What advice do you have for making this process more efficient?


texts: Steiner tree problem in graphs of diameter 3

texts:
I have an unweighted undirected graph $G(V, E)$ of diameter 3 and a subset $T\subseteq V$ of these vertices. I want to find the minimum tree $(V', E')$ that contains all vertices in $T$, minimizing the number of nodes $|V'|$.

Is it true that $|V'|\le 2|T|$? If $G$ is of diameter 2 it is easy to prove that this is true. Also for diameter 4, it is not true always since we can take a path graph of 5 vertices with $T$ as two leaves.


texts: What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?

texts:
I am having much trouble understanding the following definition (of certificate complexity - for decision trees) from Arora and Barak's book Computational Complexity: A Modern Approach. Perhaps there is a typo in it:

  Definition 12.3 (page 262). Let $f : \{0,1\}^n \to \{0, 1\}$, and $x \in \{0,1\}^n$. A 0-certificate for $x$ is a subset $S \subseteq \{0,1\}^n$, such that $f(x') = 0$ for every $x'$ such that $x'|_S = x|_S$ (where $x|_S$ denotes the substring of $x$ in the coordinates in $S$$)\ldots$

So, given that $S$ is a subset of $\{0,1\}^n$, what on earth does $x|_S$ mean? (Their parenthetical remark is not clear to me.)

  Is there in fact a typo in what $S$ is?

I've looked online at a few other authors' definitions of certificate complexity, and it seems to me that $S$ should actually be a subset of $[n] = \{1,2,\ldots,n\}$. Is this correct? If so, then $x|_S$ would make sense.

Finally, I'll note that I have looked online for an errata list, but I could not find anything very comprehensive.


texts: Is the inverse of MST cut property true? Why?

texts: If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?


texts: Notation for expressing function call count during a program run

texts:
Which notation can be used for expressing how many times that function or subroutine called during a run of a program?

Example program pseudocode:

$
a \gets 0 \\
\textbf{While } a \neq 5 \textbf{ do} \\
\quad \textit{function1()} \\
\quad a \gets a + 1 \\
\textbf{end}
$

$g: functions \rightarrow \mathbb{N}$ and for this example it is: $g(function1()) = 5$

I want to use it for expressing empirical observations depending on function call count.

Most of the time less than |iterSearch(searchState)|/3 child node searched during experiments.

What are the possible notations for function $g$ ?


texts: Decidability of the language of DFAs accepting only odd-length strings

texts:
Let $L$ be the language $\{\langle M \rangle : M\text{ is a DFA that accepts only odd-length strings}\}$.
Prove that $L$ is decidable.

How wrong is my answer?
Create a TM $T$ that decides $L$:

Create an equivalent input string $v$ that is in the language $L(M)$.

Give encoding to $T = \langle M, v \rangle$.

TM $T$ simulates $M$ on input $v$.

If TM $T$ halts and accepts, accept. Otherwise, reject.

I would like to know how off I am with my answer.


texts: Finding runtime of a recurrence relation with a fractional power

texts:
Consider the following algorithm and find the tightest Big-$O$:

Assume $\texttt{multiplyKS}$($A,B$) is $O(n^{1.58})$ and $\texttt{Add}($A,B$)$ is $O(n)$.

If my runtime is $T(n)$, I have:

Lines 1 through 2 is $T(0)=d$, where $d$ is some constant
Line 3 is $T(n/2)$
Line 4 is $cn^{1.58}$, where $c$ is some constant
I ignore lines 5 through 6 because they are negligible, long term
Lines 7 through 8 is $kn$, where $k$ is some constant

Then I have:

$T(n)=T(n/2)+cn^{1.58}+kn$

After some research, I found that I can simplify (?) my runtime, by def. of Big-$O$, to:

$T(n)=T(n/2)+cn^{1.58}$

Have I done this correctly? If so, does this imply that I can use the Master Theorem to find Big-$O$?


texts: Multiple Knapsack using Dynamic Programming

texts:
Def MKP (Multiple Knapsack Problem): Given a set of n items and a set of m bags (m <= n), with

pj: profit of item j
wj: weight of item j
ci: capacity of bag i

select m disjoint subsets of items so that the total profit of the selected items is a maximum, and each subset can be assigned to a different bag whose capacity is no less than the total weight of items in the subset.

I'm wondering if there is a reasonable way of solving MKP using DP. I get the point in 0-1 Knapsack Problem. The recurrence is quite straightforward, add item/ not add item.

dp[item][capacity] = max{
     value[item] + dp[item - 1][capacity - weight[item]],
     dp[item - 1][capacity]}

However, I cannot see how to get an recurrence equation for the MKP. Should I extend the recurrence equation to "add item bag 1/ not add item bag 1/ add item bag 2/ not add item bag 2" and so on and so forth? It does not seem a good approach as the number of bags becomes larger and larger.


texts: What do f(x) and g(x) represent in Big O notation?

texts:
I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) \in O(g(x))$.
Obviously $f(x)$ is the running time of the given algorithm we are comparing against infinity, but what does $g(x)$ represent?


texts: Is there any relationship between grammar being ambiguous and the language itself?

texts: According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language itself , is there any kind of relationship between the language itself and the ambiguous nature of a particular grammar that could generate it. Also , I am having another doubt , Is it possible that there should exist,infinite number of grammars that could generate the strings of a particular language ?


texts: What's the difference between Adaptive Control and Hierarchical Reinforcement Learning?

texts: After watching Travis DeWolf presentation on scaling neural computation, I'm a bit confused about the difference between Reinforcement Learning (whether hierarchical or not) and Adaptive Control. They both seem to be exploring environments and minimizing error through learning, but they're obviously used for very different applications. Can someone explain to me what's the difference between these two tasks and based off that difference, what would be a good way to combine them?


texts: Difference between pattern matching and pattern searching in terms of DFA/Regex

texts:
E.g.

Matching Problem The DFA of regex good is like a chain.

match:     "good"
not match: "people do not give good comments are not good people"

Searching Problem The DFA used in searching regex good could be:

1 matching:  "good"
2 matchings: "people do not give good comments are not good people"

Here are the questions:

In the above two problems, it seems the searching problem's DFA is the matching problem's DFA plus some backedges and an additional state (here state 0). Is this the difference in general?
What is the regex of searching problem in this case?


texts:
Given n disks in the plane, i want to compute the lowest point in their intersection area, im looking  for a simple randomized incremental algorithm.
There are some circles in the plane, these circles have an intersection R, the point with the lowest y in R is what i mean.
Why i thought of RIC is that maybe we can add circles incrementaly and updating the intersection area each time and also the optimal point should be updated if it possible with the lower time.
I think this problem have some similarity with 2D half-plane intersection (2D LP). In that problem we were looking for an optimal point in respect of the cost vector.  But subproblems in that problem was finding the intersection between a half-plane and a convex region with can be reduced to a simpler 1D problem. That 1D problem is half-line intersection, which is easier to solve.
Here but i have trouble to define a simpler subproblem. Also in the Analysis for expected time, i don’t see how to use backward analysis here.
I also guess maybe we can solve this problem with finding the convex-hull of those circles, then we look for it’s core with half-plane intersection, but i really uncertain about this idea.


texts:
In programming language theory, there are operations which are distinguished between static and dynamic, e.g. static/dynamic scoping, static/dynamic typing, ....

Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language?

Let me explain the above question and my thoughts and confusions about it.

Is it correct that a static operation means the operation is
performed at compilation time, and a dynamic operation means it is
performed at run time?
When an operation is performed by an interpreter, is it at
compilation time or run time?

It seems to me that people often says it is at run time.

But if I am correct, an interpreter first translates and then
executes a program, so to answer the question, do we need to specify
whether the operation is performed when the interpreter translates
or executes a program?
Does a static operation imply that the language under consideration
is implemented by a compiler but not by an interpreter?
Does a dynamic operation imply that the language under consideration
is implemented by an interpreter but not a compiler?

Thanks.


texts: Give me ideas for an undergraduate final year math project about Boolean Satisfiability and SAT solvers

texts:
Context
I am a student starting an undergrad math project.
I was instructed to read Donald Knuth's Fascicle 6: Satisfiability and come up with ideas for a project from this material.

I have 13 weeks to do the project.
I have carefully read the Example applications section of the book and over Christmas I managed to encode Conway's Game of Life into Boolean Logic and search for interesting seeds that evolve into predetermined patterns.

Today I am struggling to think of a research question (or project idea) involving this material that I can answer or complete under my time constraints.
I could provide encodings to Boolean Logic for every example application Knuth discusses.
I could translate all the applications in the Example applications section into python 3.
Here are the applications Knuth discusses in the Example Applications section.
A recipe book for boolean encodings for these could be useful to future readers?

The Waerden Function
Exact covering
Four Color Theorem
Fault Testing
Machine Learning
Game of Life
Mutual Exclusion
Digital Tomography

Perhaps I could solve some new problem using a SAT solver?
Question

Suggest an undergrad research project involving SAT solvers and Boolean encoding

Due to my inexperience I am struggling to come up with a decent research question.
I would love to add a tiny leaf to the tree of knowledge.


texts: Can the loops be in any order in the Floyd-Warshall algorithm?

texts:
I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j]
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

Our professor told us that the loop for k MUST be outside the i and j loops. I am unable to understand why this must be the case. He said that if k is inside we will only compute the best 2 edged or 1 edge path from i to j. I just don't see it. Can someone help?


texts:
According to chess rules, the (undirected) graph generated from the Knight move on a keypad is the following:

$$
\begin{array}{ccccc}
3 & - & 4 & - & 9 \\
| & & | & & | \\
8 & & 0 & & 2 \\
| & & | & & | \\
1 & - & 6 & - & 7
\end{array}
$$

The question is:

Consider the uniform distribution on all $n+1$-sequences $(s_i)_{i=0}^n$ starting with $s_0=0$.  What is the expected value and the standard deviation of $\sum_{i=1}^n s_i \bmod n$, under this distribution on sequences?

My naive approach is simply traverse every single sequence of fixed given length and do the calculation. But as the $n$ grows, the number of visits grows exponentially. For example, for $n=1024$, the number of sequences exceeds $6.04\times 10^{367}$. Hence a DFS or any kind of traverse is not a feasible approach.

So my second thought is using some analytic method. To get a few ideas, I first did some simulations on $\sum s_i$ (without modular reduction) with $10^5$ trials. The program generates the following distribution which doesn't match any obvious candidate so I couldn't advance further. So I am thinking if this is the correct way to tackle this problem. Any hint or help is appreciated.


texts:
I'm about to work with concept drift problem in data streams.

I need to start with real data sets from UCI machine learning repository and add to them concept drift (in attributes domain).

Do you know tools that can help me with this?
Maybe someone knows it is possible to use MOA[1] framework for this?

What is best way to approach this if I have to do it by myself?

[1] http://moa.cms.waikato.ac.nz/


texts: L= ${ a^mb^nc^pd^q: m+np+q }$ context free?

texts:
I cant find the grammar to prove it is context free but. I also tried a PDA but couldnt make it.
Can someone suggest a grammar for this?


texts: No Naive Set Theoretic Models of Polymorphic Lambda Calculus?

texts:
In Philip Wadler's paper on Theorems for Free he states in Section 2 on Parametricity that

  there are no naive set-theoretic models of polymorphic lambda calculus

In the naive set-theoretic model types are sets and functions are set-theoretic functions which seems reasonable. So why does he say there are no naive set-theoretic models of polymorphic lambda calculus?


texts: Analysis quickselect: Median of Medians with duplicates

texts:
in This Lecture Notes 1 (page 3), it is said concerning quickselect with median of medians:

  If there are repeated elements
  ...
  Alternatively, one has to refine the algorithm and the analysis
  (see CLR).

But in my copy of CLRS (2011), the authors assumed that the elements are distinct.

How would one refine the algorithm and the analysis?

(I'm aware that you can make elements distinct in O(n), but I'm interested in the alternative)

[1] - https://people.eecs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf


texts: A case study for search techniques in AI

texts: We are teaching an artificial intelligence class and we need a different case study other than geographical maps (the popular example is the map of Romania) to explain the difference between Breadth-first search and Depth-first search solutions. We plan on giving it to the students to use as a semester project.


texts: Normal Order Reduction - is Leftmost Outermost order simply Leftmost?

texts:
This is a quick question.  I've been reading up on Lambda Calculus, and I see Normal Order as "outermost leftmost first", and Applicative Order described as as "innermost leftmost first".

I think this makes sense to me, but the explanation is often accompanied by a diagram of a tree (such as pages 15-17 in this document), and I am unclear about why that would be needed.

Is it the case that the first application in Normal Order will always be the leftmost lambda symbol within the lambda string?  (This presuming that there is something to apply to this lambda.  If not, we would simply move on to the next one, from left to right.)


texts: What is the difference between the input set of a BSS RAM and a language?

texts:
I'm currently learning some things about BSS RAMs.
For sake of simplicity, please imagine them as a Turing machine over the reals.
Now, this machine gets some real numbers as input. The input values form nearly a string, but are not of finite length as decimal representation. Additionally, there are infinitely many real numbers.

A language on the other hand is often defined as being a subset of Kleene's Hull over a finite (!) alphabet.

Is it valid and reasonable to define languages over an infinite alphabet to represent the input set of a BSS RAM?


texts: What is postorder traversal on this simple tree?

texts:
Given the following tree:

Which traversal method would give as result the following output: CDBEA?

The answer in my study guide is Postorder, but I think postorder would output: DEBCA. Am I wrong?


texts: Why is Uniform cost search called "uniform" cost search?

texts:
By this possibly good attempt to explain this, the "uniformity" in the Uniform cost search is actually the uniformity of the heuristic function.

Is this explanation correct ? If yes, then don't all un-informed cost searches (like BFS, DFS, etc) have no heurstic and thus, be called as "uniform cost searches" ?


texts: Application of Brent's Cycle Detection Algorithm

texts:
I would like to find cycles in a finite length list of numbers where there is no function:

xn = f(xn-1).

For example, in the list:

3, 12, 11, 46, 1034, 23, 12, 11, 46, 1034, 5

x0 = 3, x1 = 12, etc. and the cycle starts at x1 with a length of 4.

There is a Java implementation of Brent's Cycle Algorithm here which includes some sample data with the expected output.

Brent Cycle Algorithm Test

Enter size of list
9

Enter f(x)
6 6 0 1 4 3 3 4 2

Enter x0
8

First 9 elements in sequence :
8 2 0 6 3 1 6 3 1 6

Length of cycle : 3
Position : 4

Here you can see that x0 = 8 and that the 8th entry in the entered list is 2 (using a zero based index), which when used as an index gives 0, which when used as an index gives 6 and so on producing the first 9 elements in the sequence 8, 2, 0, 6, etc.

My problem (likely due to my lack of understanding about the purpose or use of Brent's Algorithm) is that the numbers in the list I provided (3, 12, 11, 46, etc.) cannot be used as indexes (indicies?) to access the next number in the list.  In other words, there is no f(x) such that xn = f(xn-1).

Does this put Brent's Algorithm out of reach for my application?  Maybe there's a simple modification to Brent's Algorithm that hasn't occurred to me.


texts:
My lecturer told me that when I use an arithmetic I-Type command (ADDI,SUBI etc.) , the IMM field gets sign extended, and when I use a logic I-Type command (ORI,ANDI etc.) , the IMM field is just bits.

He also said that if the IMM field contains a negative number, it is represented in 2's complement.

Let's say I have a command, and two binary numbers X Y, so that X's 2's complement representation looks exactly like Y in regular representation.

Note: X is negative and not the same as Y.

Given a question in which I should say what is the value in the IMM field in an arithmetic I-Type command, how do I know if it's X or Y?


texts: Can anyone explain why pictures are not considered 2D, but rather high dimensional? Especially with regards to CV and AI.


texts: Can a Turing Machine decide only non-regular languages?

texts:
I have an assignment where i need to create a Turing machine that decides an infinite language $L\subset \{0,1\}^*$ for which all $L'\subseteq L$, if $|L'|=\infty$, then $L'$ is not a regular language.

I think this is not possible due to Rice's Theorem. It's not possible to tell for a Turing Machine if a language is regular or not.

Moreover, on any given input, the machine can loop so it cannot decide an infinite language $L$.

Is this the right answer? It seems too easy to be the answer... Any input would be appreciable. Thanks in advance.


texts: Conditions under which the 3-partition problem is not strongly NP-complete?

texts:
I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article:

  Let B denote the (desired) sum of each subset Si, or equivalently, let the total sum of the numbers in S be m B. The 3-partition problem remains strongly NP-complete when every integer in S is strictly between B/4 and B/2.

Does this mean that if the multiset contains elements that fall outside the range B/4-B/2 the problem is no longer strongly NP-complete and admits heuristics or other optimizations? Am I interpreting that right?

Also am I correct in assuming that this problem (at least when it is strongly NP-complete) pretty much requires an exhaustive search (unless P=NP)?

I've sifted through some papers but haven't been able to figure this out.


texts: n closest points in a set of lat/long coordinates

texts:
Here's my problem:

I have a website where people can search based on their location (which is converted to lat/long coordinates). I have many products stored in a database with their lat/long coordinates. I also have a function to calculate the distance between two points based on their coordinates.

Now I'm looking for a way to find one of these things:

The n nearest products to the user's location.
All the products within a radius of x kilometers from the user's location.

Both solutions would be fine for my application.

Currently I just iterate over all the database entries, find their distance, and sort them. This obviously gets way too slow with a lot of entries.

Are there any algorithms/data structures I can apply here to make it faster?

Thanks in advance!


texts: Simulating a sequence of events concurrently subject to a happened-before partial order

texts:
I am building a strategy game where multiple units(5 - 20) is fighting each other in the same time.

I have a logic part that calculate those actions for each turn, and than pass it to the game engine to animate. This is the list of action that I currently supporting:

perform attack
perform miss
perform taking damage
perform dying
perform moving

If I animate all the actions at once than it look messy:

  Unit A attacks unit B, while unit B is not even there, it went to
  attack unit C

If I animate all the actions one by one, than it looks lame

  Unit A attacks unit B, the other 18 units is just stand and waiting
  for the unknown...

How can I find what actions I can perform in parallel?

For now my best solution, is to wait for unit to finish attacking before attacking it, it cover many scenarios but it still got halls.

  Unit A attacks unit B, unit C waiting for A to finish attacking in
  order to attack him. Unit D attacks and kill unit C.

Edit based on D.W answer:

This solution cover most of the cases but, I found a hall in it.

Think about the next scenario

  A attacks B, B attacks C, C attacks D

Because each of those action has a dependency on the prevues one, your algorithm would suggest to break it in to 3 sequences.

A attacks B
B attacks C
C attacks D

How ever I would like to break it in to, two sequences:

A attacks B, C attack D
B attacks C

I want to use your algorithm solution iff B kills C.


texts: Finding the largest 3-clique-free induced subgraph

texts:
Consider this problem:

Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that:

$G'$ is an induced subgraph of $G$
$G'$ has no 3-cliques
$|V'|$ is maximal

So the least number of vertices must be eliminated from $G$ so that 3-cliques are eliminated.
An equivalent problem would be to find a 2-coloring for $G$ such that if $(v_1, v_2, v_3) \in V$ and $((v_1, v_2), (v_2, v_3), (v_3, v_1)) \in V$,

$(v_1.color == v_2.color \wedge v_2.color == v_3.color \wedge v_3.color == v_1.color) = False$

The (absolute) difference between the number of nodes with color 1 and the number of nodes with color 2 is maximal.

Can anyone think of a polynomial-time algorithm to solve one of these problems?


texts: is the complexity of an algorithm connected to the "classification" of a optimization problem?

texts:
I wonder if the complexity is connected to an optimization problem. In general but also specifically e.g. when having a look at $ O(n^2) $. Does this just describe the complexity in general or does it also mean does the underlying algorithm has to be a nonlinear optimization problem? Or is it also valid for linear tasks?

In simple words: Can a nonlinear task be solved in $ O(n) $?


texts:
What is induction-induction?

The resources I found are:

the HoTT book, at the end of chapter 5.7.
nLab's article
a paper called Inductive-inductive definitions
this blog post also mentions inductive-inductive types

The first two references are too brief for me, and the latter two are too technical. Can anyone explain it in layman's term?
It would be better if there's Agda code.


texts: A question from Computer Organization on Peak Clock Frequency

texts:
Given below are 3 different pipelined processors:

$P_1:\ 4\ stages\ with\ delays\ \ \ \ 0.6_{ms}\ \ 0.8_{ms}\ \ 0.6_{ms}\ \ 1.1_{ms}\\
P_2:\ 4\ stages\ with\ delays\ \ \ \ 2.0_{ms}\ \ 1.8_{ms}\ \ 2.0_{ms}\ \ 1.0_{ms}\\
P_3:\ 5\ stages\ with\ delays\ \ \ \ 1.0_{ms}\ \ 0.8_{ms}\ \ 1.0_{ms}\ \ 1.5_{ms}\ \ 1.5_{ms}$

One has to find the Peak Clock Frequencies of each $\mathbf{P_i}$. Pipeline buffer register latency is Zero.

I don't know how to solve this, but I've come up with an intuitive formula for calculating peak frequency of clock for processor $P_i$ as $$\mathcal{C_{p.f}}=\frac{1}{max(d_i)}$$ where $d_i$ is individual stage delay for processor $P_i$. For example for $P_2$ it's $\frac{1}{2}KHz = 0.5 KHz$.

Now I don't know whether it's the correct way to calculate peak frequency.
If it's not, can anyone tell me what is it?

P.S: I also don't know whether this is the right place to ask this question.
But I didn't have any idea about where to post it otherwise.


texts: Is it necessary that two isomorphic graphs must have the same diameter? As far as I know, their adjacency matrix must be retained, and if they have the same adjacency matrix representation, does that imply that they should also have the same diameter?


texts: Effect of Copy-On-Write on 2 processes sharing address space

texts:
I am studying operating systems and was going through Copy On Write mechanism.
From Wiki:

  When one process modifies the memory, the operating system's kernel intercepts the operation and copies the memory; thus a change in the memory of one process is not visible in another's.

It says a particular virtual page is remapped if any of the processes that are sharing the address space tries to modify any data value. So, I tried testing it by writing following code :

#include<stdio.h>
#include<stdlib.h>

int main()
{
        pid_t pid;
        int a = 30;
        pid = fork();

        if(pid == 0)
        {
                printf("Parent\t %x\t %d\n",&a,a);
        }
        else
        {
                printf("Child\t %x\t %d\n",&a,a);
                a = 25;
                printf("Child\t %x\t %d\n",&a,a);
        }

        return 0;
}

Now when I run the program, the output I get is :

$ ./test
Child    ae9dfe3c        30
Child    ae9dfe3c        25
Parent   ae9dfe3c        30

I understand why the address in first and third line are same but my doubt is why is the memory location in second line same as the other two? It should be different because the child process is modifying the value of a ?


texts: How to construct a Turing machine for a language

texts:
I have proved that language $L$ is not regular and think that it is recognizable by a Turing machine. I want to prove it by constructing a Turing machine for it.

$L=\{0^n|n \in A\}$
where $A$ is set of all numbers that do not contain 1 in their base 3 representation. However, n is in base 10.

What I have done so far:
When I was proving that the language is not regular, I used the fact that there cannot be any arithmetic sequences in $A$. I think if I work on the number of 1 in base three, I may get somewhere.


texts: Intersection and partial quantity decidability

texts:
I'm still insecure in the section decidability (no proof needed, I want to divine it):

X is decidable and Y is undecidable. Is the intersection of X and Y decidable or undecidable?

X is decidable and Y is a partial quantity of X. Is Y decidable, too or not?

Thanks!


texts: Finding all paths from s to t in linear time

texts:
I was looking at the following algorithm which prints all the paths from node s to node t and I have some questions I don't understand

The basic idea is :

DFS-Visit(s)
Change current status to "currently visiting"
If neighbor is t -> print the path (from the stack trace or any way)
If not: DFS-Visit on neighbors
When done visiting neighbors: change status to "not-visited yet"

It seems like it's run-time is exponential, however - could I use the memorization technique like in dynamic programming to turn this into linear time ? since a lot of calculations are repeating

The example given in the algorithm is a DAG, but I couldn't find an regular graph that makes this algorithm fail.

It seems highly unlikely that this algorithm is possible in linear time on a regular graph... Wouldn't that help me to calculate shortest path from s to t in linear time ?


texts: Difference between Computing Architecture and Platform in Computer Science

texts:
I was looking for an appropriate term to call my proposal. I knew it is either platform or architecture. But could not simply and clearly distinguish them in an academic manner. So, I searched the web and the literature and found few definitions on architecture and platform as follows that sound logical.

Software Architecture: A set of system elements and relations associated with them [reference: documenting software architecture: views and beyond]
Platform: A set of subsystems and technologies providing a coherent set of functionalities through interfaces and specified usage pattern that any subsystem that depends on the platform can use without concern of the detail of how the functionality provided by the platform is implemented1.

However, still is it not clear what are the differences. I guess researchers often use these two terms interchangeably with marginal consideration on their differentiations. Looking at the definitions, I figured out that architecture likely specifies structural properties of systems and usually tries to describe the structure of a system and its consisting components and their relationship. Using architecture, developers cannot produce a system that works according to that architecture. However, platform is trying to specify structural and behavioural attribute of a system by describing its subsystems and their relationship. Platform also provides an abstract by which developers can create new software systems that rely upon the platform.
Is this interpretation accurate enough? One may argue that platform is prepared on top of an architecture and without architecture one may not be able to propose platform.
In your idea, what else are the differences and distinguishing lines between these two terms?


texts: Is the preprocessing process using the tfidf vectorizer really useful for model learning?

texts:
I am a student who is studying machine running alone.
As far as I know, the Tf-idf Vectorizer is a function that combines the Count Vectorizer and the Tf-idf Transformer.
I was wondering if the Tf-idf Transformer process could actually have a impact on the model learning process.
In my experience, there seemed to be no model performance difference between using CountVectorizer and Tf-idf Vectorizer in preprocessing String vector.
Is there a situation where we need to consider the Tf-idfVectorizer rather than the CountVectorizer when processing a String Vector?


texts:
Question: Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters? And how many words can we form with up to 4 letters?

I was thinking about the logic behind this and came up with this: perhaps the number of words that can be formed with 4 letters is $4^3 = 64$ words. Is that correct?

I could not think about how many words up to 4 letters, because that includes words with 1, 2 and 3 letters.


texts: Allocating flows in a network while avoiding a particular node

texts:
I am considering a network with the max flow problem in a particular situation. I have a set of flows which should pass a certain node A and and another set of flows which should avoid A and pass through another node B. The flows can cross each other at any other arbitrary node.

Under what category of network flow problems should this be considered?


texts: How do I prove that a language is regular?

texts:
In order to prove that the following language is regular, would I use a pumping lemma?

The set $A$ of all strings that are substrings of some string in $L$, where $L \subseteq\Sigma^*$. $L$ Must be regular.


texts: Is there an online preprocessing algorithm for Range Minimum Queries (RMQ)?

texts:
Is there a linear time online version of the preprocessing RMQ algorithm? That is, an algorithm that allows to update the data structure when appending additional elements at the end of the input array in O(1) (worst case or amortized) time per element (while still allowing answering arbitrary queries in constant time)?
I am aware of the sliding queries algorithm, which is online by nature but restricts the type of allowed queries. I've also seen this more general question, which is still unanswered by the time of writing this post.


texts: How to prove the asymptotic upper bound for $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$?

texts:
I met the problem

  Show that the solution to $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$

while reading Introduction to Algorithm. It's a question about the substitution method for solving recurrences.

Should I just assume $T(n/2 + 17) \leq O((n/2 + 17) \log(n/2 + 17))$ and then prove $T(n) \leq O(n \log n)$? Is this inductive assumption enough to solve it?


texts: Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

texts:
I am experimenting with the sorting of arrays and their execution times.
While using bubblesort, insertsort and quicksort, I have observed that relative standard deviation (%RSD) of execution times, for five hundred arrays of the same size containing random integers, decreases if the size of the arrays increases.

For example: if the %RSD of execution times while sorting 500 arrays, of size fifty elements each, is observed as 7%, the same for arrays with five hundred elements each is about 2.5%.

So the question is: why this value of change decreases with the increase in the array size?

P.S. I am using a cycle-accurate simulator (gem5) and taking exact clock cycles.


texts: Valid bit incoherence between TLB and Page Table

texts: In the fourth row of the TLB the valid bit is 0. The corresponding row in the pagle table (fifht row) has the valid bit 1. How is this possible? What events leads to this incoherence?


texts: Trapdoor functions that depends only on NP-hard?

texts:
As far as I can tell, there are no examples of trapdoor functions which hardness assumptions is merely hardness of some NP-hard problem in worst case. That is, a trapdoor function in which, it is proved that, if there is an PPT algorithm that can invert it with non-negligible probability, then there is a PT algorithm which can solve the worst case of some NP-hard problem.
If I am wrong on the above, can you show me an example of such function?
If I am not, why is it so hard to make such a trapdoor function? Is there a concrete reason why it's hard to develop such function (beside "we haven't figure it out yet")?
This supposedly "duplicate" question (Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?) doesn't actually answer this question. That question isn't why worst case NP-hard isn't enough to make an encryption out of it. This question is essentially about why there had been no successful attempt at reducing average-case hardness down to worst-case NP-hard, for the purpose of making trapdoor function. There had been problems where average-case is just as hard as worst-case, so the fact that not all problems has worst-case=average-case doesn't mean you can't use different problems where that is true.


texts: Regular languages that can't be expressed with only 2 regex operations

texts:
I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but
I have been told that you need all three of the regular operations (concatenation, union, and star) for that to hold.

For example, I have been told that if I can only use the union and concatenation regex operations (2 out of the 3), there would be a regular language I can't describe with just those two.

Same with just Kleene star and union. What are some examples of this?


texts: Data Searching from a large data set without reading each element

texts:
I have just started learning algorithms and data structures and I came by an interesting problem.
I need some help in solving the problem.

There is a data set given to me. Within the data set are characters and a number associated with each of them. I have to evaluate the sum of the largest numbers associated with each of the present characters. The list is not sorted by characters however groups of each character are repeated with no further instance of that character in the data set. Moreover, the largest number associated with each character in the data set always appears at the largest position of reference of that character in the data set.
We know the length of the entire data set and we can get retrieve the data by specifying the line number associated with that data set.
For Eg.
C-7
C-9
C-12
D-1
D-8
A-3
M-67
M-78
M-90
M-91
M-92
K-4
K-7
K-10
L-13
 length=15
get(3)= D-1(stores in class with character D and value 1)
The answer for the above should be 13+10+92+3+8+12 as they are the highest numbers associated with L,K,M,A,D,C respectively.
The simplest solution is, of course, to go through all of the elements but what is the most efficient algorithm(reading the data set lesser than the length of the data set)?


texts: Does big-Oh notation in optimization follow the same convention as in CS?

texts:
I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class.
Now I am doing a project on optimization. In our optimization class, we were introduced to the notion of rate of convergence which are characterized by the ratio:
$\lim\limits_{k \to \infty} \dfrac{|x_{k+1} - L|}{|x_k-L|}$
where $L$ is the limit of the sequence $(x_k)$. And from there we define linear, superlinear and sublinear convergence raes.
However, when I looked up on some reference online, the above notions of rate of convergence is almost never used. Instead, all the convergence rates are characterized in terms of big-Oh. Quoting from the slides:

Theorem: Gradient decent with fixed step size $t\le\frac{1}{L}$ satisfies $f(x^{(k)})-f(x^*)\le\frac{\|x^{(0)}-x^*\|^2}{2tk}$.
I.e. gradient decent has convergence rate $O\left(\frac{1}{k}\right)$.
I.e. to get $f(x^{(k)})-f(x^*)\le\epsilon$, we need $O\left(\frac{1}{k}\right)$ iterations.

Unfortunately, these authors never define what their notations mean. I am in need of citing the definitions of big-Oh for my class project.
Is there any disparity between the rate of convergence in terms of big-Oh (and other asymptotic) used in optimization versus that used in CS (as can be found in a standard textbook such as CLRS)?
Is there an optimization textbook that addresses big-Oh notation?


texts: Minimum number of sets of unreachable vertices for directed acyclic graph (DAG)

texts:
I have a DAG with vertices $V$ and edges $E$.  If $v,w \in V$ are vertices such that $v$ is not reachable from $w$ and $w$ is not reachable from $v$, I will say that $\langle v,w \rangle$ is an unreachable pair.

I want to implement an efficient algorithm which takes this DAG as input, and produces as output a list of sets of pvertices such that:

For each unreachable pair of vertices $\langle v,w \rangle$, at least one of the output sets contains both $v$ and $w$,
Every pair of vertices $v,w$ that are contained in the same output set must be an unreachable pair, and
The number of output sets must be the minimum possible.

Is there a polynomial-time algorithm for this problem?

As an example, we have the following DAG with topologically ordered vertices
A,B,C,D,E:

A is connected to [D, E]
B is connected to [D, E]
C is connected to [E]
D is connected to []
E is connected to []

which means that we have the following unreachable vertex pairs:

1. <A, B>
2. <A, C>
3. <B, C>
4. <C, D>
5. <D, E>

The expected output is composed of the following three vertex sets:

1. {A, B, C}
2. {C, D}
3. {D, E}

The output was not {A,B} {A,C} {B,C} {C,D} {D,E} because the minimum number of  possible output sets is 3 instead of 5 as given above. Otherwise it would satisfy the first two conditions, but not the third condition.

As another example, consider the same DAG vertex set V but where the edge set E is empty. Since all vertex pairs would be unreachable, the expected output is the vertex set V itself.


texts: Context-free grammar for language involving multiplication

texts:
I'm struggling to find the context-free grammar for the following language:
$$
L = \{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\}
$$
Any help would be appreciated.


texts:
What is difference between following two problems, their decidability and recognizability status:

Given Turing Machine TM "accepts" given string w.
Given Turing Machine TM "halts on" given string w.

I feel first problem means,

  whether given TM "halts by accepting" given string

and second problem means,

  whether given TM "halts by accepting or rejecting" given string

If I am correct, then is their any difference between their decidability and recognizability status?

For 2nd language, if TM accepts w, then it will eventually halt, but if it does not accept w, then it may keep looping infinitely. Hence its undecidable but recognizable.

I believe 1st problem is subset of 2nd problem and hence it is definitely recognizable. But I am confused about decidability of 1st problem, since it eliminates "halt by rejecting" criteria from 2nd problem. Does that make it decidable?


texts: The equation for how much data is produced every period

texts:
I am trying to find out how much data we produce to project how much we will produce in the future. I find stuff like this and this:

  There are 2.5 quintillion bytes of data created each day at our current pace, but that pace is only accelerating with the growth of the Internet of Things (IoT). Over the last two years alone 90 percent of the data in the world was generated.

But that doesn't show you any research or papers outlining equations.

I am not looking for anything exact as it's not an exact thing. It's like Moore's law I imagine, sorta thing. I would simply like to know roughly an equation I could turn into some code potentially and use to type in estimate('timestamp', 29841419481) and get a number. Just looking for a basic math equation, I am not sure how to calculate these exponential growth type of things.


texts:
I want to do an analysis on the sum $ \Sigma_{i=0}^n  f(i)$. All that is known about $f(i)$ is that $f(i) \in \Theta (i \log i ) $.

How do I do this?


texts: Does the following piece of code lead to a deadlock?

texts:
Process X

/* other code for process x*/
  while (true)  {
  1) varP = true;
  2) while (varQ == true)
     {
        /* Critical Section */
  3)    varP = false;
     }
}
/* other code for process X */

Process Y

/* other code for process Y */
while (true)
{
  1) varQ = true;
  2) while (varP == true)
     {
        /* Critical Section */
  3)    varQ = false;
     }
}
/* other code for process Y */

For the above piece of code, it can be easily observed that Mutual exclusion isn't ensured i.e. both X and Y can access critical section at the same time. My doubt is regarding whether there exists a deadlock.

Consider the sequence of execution $X_1 Y_1 X_2 X_3 Y_2 Y_1 Y_2\cdots$ where X and Y represent the processes and the subscripts denote the numbered statements. Once the above sequence happens during the concurrent execution of $X$ and $Y$, $X$ stays stuck in its critical section and $Y$ never enters its critical section. Can this be viewed as a deadlock where the access to rest of the code of $X$ is denied by $Y$ and $Y$ is denied access to its CS by $X$?


texts: Is it possible to write a program that calculates an algorithm's time complexity?

texts:
Title is self explanatory.

I have searched here on this site and haven't found any discussion about this.

Is it somehow related to Turing's Halting problem (which is undecidable)?


texts: How hard is finding restricted assignment of 3-SAT satisfying $7/8$ of the clauses?

texts:
The PCP theorem implies (with other results) that there is no polynomial time algorithm for MAX 3SAT to find an assignment satisfying $7/8+ \epsilon$ clauses of a satisfiable 3SAT formula unless $P = NP$.

There is a trivial polynomial time algorithm that satisfies $7/8$ of the clauses. How hard is it to find an assignment that satsfies at least $7/8$ of the clauses but no more than $7/8 +\epsilon $ for some $\epsilon \gt 0$? Is this task still $NP$-hard?


texts: If pref(L) is regular, does that imply L is regular?

texts:
I have this exercise for homework:

  Say we have a language L. we know that the language pref(L) (all the prefixes of L, including all the words in L itself) is a regular language. Does this imply that the language L is regular as well?

I took the NFA of pref(L) and divided it (via 2 epsilon transitions from q0) to 2 separate NFA's, as 1 defines L and the other defines pref(L)\L.

What I actually got is a NFA for L, which means it is regular.

I am not sure this is the way or if it legal. I'd be glad for another lead.


texts:
I am trying to model the following problem correctly as a min-cut network flow problem. I have $n$ books and 2 boxes. I also have books that I know must go in one of the two boxes. In addition, each book has a certain profit if I put it in the same box with another book. So for instance, if I pair book $i$ with book $j$ I might have a profit of 10 dollars so long as they're in the same box. If I have 3 books in one box, I'd have to sum the profit of 1 and 2, 2 and 3, and 1 and 3. I want to find the best way to assign the not-yet assigned books to either box 1 or 2 to maximize my profit. Formally:

2 boxes: $b_1$ and $b_2$
Set: $N$ of $1...n$ books
$S_1$ = set of all books that must go to box 1
$S_2$ = set of all books that must go to box 2
$p_{ij}$ = The profit by having books $i$ and $j$ in the same box
Objective (roughly): $max(\sum_{i=1}^{2}\sum p_{ij})$ (maximize the profit over all boxes)

My ideas so far:

Formulate the problem as a min-cut problem because we are trying to end up with two sets of books (one for box 1, one for box 2). Would it be correct to say that $-min(-\sum_{1}^{2}\sum p_{ij})$ is equivalent to our maximization above? I tried simplifying it further but I'm not sure how.

Make source node for box 1, node for each book not assigned (not in $S_1$ and not in $S_2$) and a sink node for box 2.

My question:

With the previous formulation in mind, I'm confused on what the edges would be like. I have edges from box 1 to the book nodes and then the book nodes to box 2 but I'm not sure if this makes sense, largely because I need to make sure my summation notation is correct and how to turn that into an appropriate graph. Could anyone offer advice on the minimization I wrote above and how to translate it to a graph correctly?


texts: Directed HAM Cycles with Additional Constraints to SAT

texts:
The $n$ dimensional hypercube $Q_n$ is a graph that has a vertex $v_s$ for each string $s \in \{0, 1\}^n$ and an edge between two vertices $v_s$ and $v_t$ if and only if the Hamming distance between $s$ and $t$ is $1$.

I would like to find directed hamiltonian cycles in this graph that satisfy a certain property, and was thinking of feeding my problem to a SAT solver. The problem can be encoded as follows. We define a variable $x_{si}$ to denote that the vertex $v_s$ appears in the $i$-th position of the cycle. Then, for each $s \in \{0,1\}^n$, we define the contraints $\bigvee_{i} x_{si}$ (each vertex appears in one position of the cycle) and  $\neg x_{si} \vee \neg x_{sj}$ for all $i \neq j$ (each vertex appears at most once in the cycle). Finally, we also require the constraints  $\neg x_{si} \vee \neg x_{t(i+1)}$ for all pairs of strings $s$ and $t$ that have Hamming distance greater than $1$ (i.e pairs of vertices that do not have an edge cannot appear consecutively in the cycle ordering).

Now, I would like to add the following requirement on my cycle. For some specified integer parameter $k$, we must be able to partition the vertices of the graph into vertex disjoint copies of $Q_k$ such that the vertices in a specific copy of $Q_k$ are all assigned the same "direction". How can I capture this set of requirements easily in my reduction?


texts: What's the difference between a Generalized Nondeterministic Finite Automaton (GNFA) and a Generalized Transition Graph (GTG)?

texts:
I've recently come across a few articles that talk about a "Generalized Transition Graph" (GTG), but I've never heard of such a thing before. This other answer to a similar question leads me to believe that GNFAs are simply GTGs with a different name where GNFA is the more standard nomenclature/name.
There is a Wikipedia article on GNFAs that describes them as:

...a variation of a nondeterministic finite automaton (NFA) where each transition is labeled with any regular expression.

which from what I understand is described by others as a GTG. Unfortunately, there's no article on Generalized Transition Graphs on Wikipedia. The definitions for GTGs that I have come across are:

https://sites.cs.ucsb.edu/~cappello/136/lectures/6/slides.pdf
https://er.yuvayana.org/generalized-transition-graph-gtg-definition-with-example/
https://www.slideshare.net/ArhamKhanG/generalized-transition-graphs

So again, are GNFAs the same as GTGs?


texts: Peaking finding when equals is taken out of the equation

texts:
I am going through the online course MIT OCW 6.006, lecture 1. It introduces a binary search algorithm that finds a peak in O(lgN) time.

A peak A[i] is defined as A[i]>=A[i-1] and A[i]>=A[i+1]. But I wonder what if the definition takes the equal sign out A[i]>A[i-1] and A[i]>A[i+1], a peak is defined as an element that is strictly larger than its neighbour.

Obviously, the binary search algorithm will not work without changes, because for a case that A[i]=A[i-1] and A[i]=A[i+1], it cannot decide to go left or right.

So, is there any algorithm that stills take O(lgN) time? (I personally think no, because for an array of equal numbers, aka the case that a peak does not even exists, you need to examine all elements)


texts:
I know that the formula for the evaluation function in A* Search is given by:

$f(n)=g(n)+h(n)$

I was wondering what would happen if I made h(n) negative. I suppose it doesn't make sense to have path costs that are positive but an estimate that is negative so maybe I shouldn't be asking this question?

However, let's take the situation where g(n) is negative. This will definitely wreck optimality but what about completeness? And in such a situation, I will probably need to use a negative h(n) anyways because the path costs themselves will be negative. So if I do this, will the resulting search algorithm be complete? (I know it definitely won't be optimal).


texts: How does the OS Scheduler give/take control of HW?

texts:
Imagine a uniprocessor system with a simple operating system with non-threaded processes and basic virtual memory (paging, no segmentation, no replacement to disk, etc).

Now assume a simple preemptive scheduler, round-robin, for example.

Because it is a uniprocessor, the scheduler must hand over control of the processor momentarily for any other processes it schedules to run. How does it regain control? It can't generate interrupts, as it is not running.

I originally assumed there must be some kind of register containing the time to return control to the scheduler, and a register pointing to the location of the scheduler. But if these registers existed, what would a nonpreemptive scheduler do with them? How would the processor know the difference between a preemptive and nonpreemptive scheduler, i.e. how would it know whether to use the registers to return, or allow the process to run to completion?


texts: How to go from an unstructured disassembler to a control flow graph based decompiler?

texts:
I have a project which includes a disassembler which makes old virtual machine formats playable online. It's a very simple disassembler; it basically processes the instructions outputting a code fragment which continues until it gets to any kind of branch or jump statement. The branch will set the program counter to its new value, and then the disassembler will produce a new code fragment again continuing until it reaches any branch.
I would like to move to a true decompiler which can turn this unstructured mess into true if statements and loops. I've seen at least two algorithms for this, namely the Relooper algorithm and the Stackifier algorithm, and I think I can mostly understand how they work at a high level, but I'm feeling stuck for how to implement them. These algorithm descriptions leave out, naturally, the details of what kinds of structs and enums you'd use to implement them. The Relooper uses three types of blocks, Simple, Loop, and Multiple, but it doesn't explain what sort of structs you'd need to expose to the algorithm before it can produce an output with just its Simple, Loop, and Multiple blocks.
I've realised I can't jump straight to using an algorithm like the Relooper, I need to learn more about compilers/decompilers first. Most resources I've seen on compilers start by parsing source code, whereas I need to start with a disassembler. Can you make any recommendations on resources explaining how to implement a decompiler based on a disassembler?


texts: What is the "continuity" as a term in computable analysis?

texts:
Background
I once implemented a datatype representing arbitrary real numbers in Haskell. It labels every real numbers by having a Cauchy sequence converging to it. That will let $\mathbb{R}$ be in the usual topology. I also implemented addition, subtraction, multiplication, and division.
But my teacher said, "This doesn't seem to be a good idea. Since comparison is undecidable here, this doesn't look very practical. In particular, letting division by 0 to fall in an infinite loop doesn't look good."
So I wanted my datatype to extend $\mathbb{Q}$. Since equality comparison of $\mathbb{Q}$ is decidable, $\mathbb{Q}$ is in discrete topology. That means a topology on $\mathbb{R}$ must be finer than the discrete topology on $\mathbb{Q}$.
But, I think I found that, even if I could implement such datatype, it will be impractical.
Proof, step 1
Let $\mathbb{R}$ be finer than $\mathbb{Q}$ in discrete topology. Then $\{0\}$ is open in $\mathbb{R}$. Assume $+ : \mathbb{R}^2 → \mathbb{R}$ is continuous. Then $\{(x,-x): x \in \mathbb{R}\}$ is open in $\mathbb{R}^2$. Since $\mathbb{R}^2$ is in product topology, $\{(x,-x)\}$ is a basis element of $\mathbb{R}^2$ for every $x \in \mathbb{R}$. It follows that $\{x\}$ is a basis element of $\mathbb{R}$ for every $x \in \mathbb{R}$. That is, $\mathbb{R}$ is in discrete topology.
Proof, step 2
Since $\mathbb{R}$ is in discrete topology, $\mathbb{R}$ is computably equality comparable. This is a contradiction, so $+$ is not continuous, and thus not computable.
Question
What is bugging me is the bolded text. It is well-known that every computable function is continuous (Weihrauch 2000, p. 6). Though the analytic definition and the topological definition of continuity coincide in functions from and to Euclidean spaces, $\mathbb{R}$ above is not a Euclidean space. So I'm unsure whether my proof is correct. What is the definition of "continuity" in computable analysis?


texts: Is there any good method to find if a grammar is optimal for a problem?

texts:
I've been thinking about grammatical evolution problems and how the grammar influences the algorithm performance. It came to my mind the huge impact that the grammar that you're using has in the time that takes an algorithm to reach an optimum solution.
The simplest example would be if your problem doesn't involve trigonometric operations. If you're trying to find f(x) = 3x - 1/2, including sins, tangents or square roots in your grammar will, almost certainly, slowen your algorithm as the population complexity will grow. Other not-so-evident simplifications for a grammar would be trigonometric identities:
tan(x) = sen(x) / cos(x)

Talking about this last example, I don't know how to determine the importance of the impact of including tan(x) between the grammar rules to produce valid solutions. Or in other words, knowing if adding tan(x) will be better in terms of performance than don't doing it and thus, forcing the evolution to combine two or more operators and terminals to being able to use that operation and making the grammar ambiguous.
So this two are the questions:

Is there any way of knowing if a grammar is optimal for finding a solution?
Which evolutionary algorithm or machine learning method (considering that I'm almost profane in this discipline, some explanation is wellcome) would you use for finding optimal or sub-optimal grammars?

Thanks


texts: How to prove "if every subset of a set is a CFL, then the set must be regular."

texts:
"If every subset of a set is a CFL, then the set must be regular."

I want to prove it, could anyone please give me some hints?


texts: Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $

texts:
Iv'e been struggling a lot with this one.
I am looking for a data-structure (could be a modification of an existing type of data-structure, or a combination of more than one data-structure), which supports the following methods, all with time complexity (at worst-case) of $O(log(n))$:

Insert(v) - insert v to the structure
search(v) - search for v
delete(v) - delete node with value v
updateKeys(x,v) - for each node with a value greater then x, add v to it's value, where v is a positive number.

For example, if I had the following set of elements: ${1,2,5,8,10,15,20}$
, using updateKeys the following way: $ updateKeys(10,5) $ would change the set to : $ {1,2,5,8,15,20,25} $.

Well, I had a lot in my mind.
Basically, my assignment is on the following data-structures:

Hash tables - which sounded good at first, but I couldn't think of a way to find all elements larger than or equal to x.
AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than $ log(n) $. Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.
A combination of the two above - looked promising at first, but again, I couldn't find a way to find those elements.
Heap - for some reason it sounds like a good direction since I have some sort of order, but update the values with log(n) time? seems impossible.
Skip list - here I thought about using skip list since the most bottom layer is sorted in increasing order, so I thought about finding the minimum value larger than x, and then update all of it's followers from the right. Sounds good, but it is definitely not within $ O(log(n)) $, since for the following set ${1,2,3,4...10}$, and for $ x=1 $, I need to iterate 10 numbers, which is $ O(n) $

We also studied B-trees, ADT structures...

Then, almost hopeless, I started reading about data structures that weren't even taught in our course, such as range trees, BIT trees and so on.For some reason, some of them seemed suitable for this purpose, but since it's not in our syllabus, I don't think we are even allowed to use them.

Thanks in advance.


texts: Calculating the Time complexity using Radix sort

texts:
Im trying to determine what is the time complexity of sorting numbers with a specific range and base.
I have n numbers in the range of 1-n^10 and the base for the radix sort is n/log n.
I have tried to calculate it using log equations but im getting to a linear result, I dont know wether im right or wrong.
Thank you very much.


texts: Computing parity function on n variables with O(n) gates

texts:
Sipser example 9.29

He says: "one way to do so (compute the parity function with O(n) gates. One way to do so is build a binary tree that computes the XOR function, where the XOR function is the same as parity on 2 variables, and then implement each XOR gate with two NOTs and two ANDs, and one OR. ... Let A be the language of strings that contain an odd number of 1's. Then A has circuit complexity O(n)."

I'm not seeing the steps that lead to saying that A has circuit complexity of O(n). Why can we say that if we implement a binary tree of XORs we can compute the parity with O(n) gates?


texts:
According to 1, "a path cover of a directed graph G is a set of disjoint paths in G which together contain all the vertices of G".
In my research, I met a similar problem. There, you can add and subtract paths in G, and, should cover $G$ (exactly once) by a combination of addition of subtraction of a subset of paths in $G$.
Is this problem a variant of path covering? What is the name of this type of problems?
I try to set the problem formally. $V=\{v_1,v_2,\cdots,v_{|V|}\}$is a vertex set and $G=(V,E)$ is a directed graph. Let $\mathcal{P}$ be a set of all path in $G$. Let $P = \{p_i\}_{i=1,2,\cdots,|P|} \subset \mathcal{P}$.
For $p∈ \mathcal{P}$, $vec(p)∈ \mathbb{Z}^{|V|}$ denotes a vector of which $i$-th element is $1 (0)$ if the path $p$ contains (does not contain) the vertex $v_i$. For example, if $V=\{v_1,\cdots,v_6\}, p \text{ is a path as: }v_1\to v_3 \to v_5$ then $vec(p)=(1,0,1,0,1,0)$
The problem is you need find the vector $(a_1,a_2,\dots,a_{|P|})∈ \mathbb{Z}^{|P|}$ such that
$$\sum_{i=1}^{|P|}a_i vec(p_i) = (1,1,1,\cdots,1)∈ \mathbb{Z}^{|V|}.$$
For example, if you have $G$ and $P$ shown in the following figure, then $(a_1,a_2,a_3) = (1,-1,1)$ because (intuitively) $p_1 - p_2 + p_3 = V$.

I think the problem becomes bit interesting if you add some constraints for $P$. For my case,
$$P = \{p \mid v_i ∈ V, vert(p) = {v_i}\cup anc(v_i)\},$$
where $vert(p)$ is a set of vertices that are contained in $p$, and $anc(v)$ denotes a set of vertices that are ancestors of $v_i$
1 Diestel, "Graph Theory 5th ed." p.52.


texts: What is the name of the following algorithm?

texts:
I am  using the following algorithm to solve an optimization problem I have. I was wondering if there is a proper name for this algorithm in the literature.

Let $f(x)$ be my objective function.

I guess some $x_0$ and see have it performs.

Next, I randomly generate around $x_0$, some $\{x_k \}$ for $k \in [1:K]$  and see how the compare to $x_0$.  If I find  $x_n$ that perform better than $x_0$.
I perform the same procedure again with $x_n$.

I am only starting to learn about algorithms and would be grateful if you point me to the name and some reference on similar algorithms


texts: How can I generate Rubik's cube algorithms equivalent to a given algorithm?

texts:
I am developing a computer program that solves the Rubik's cube. It is not anything advanced nor fast. It solves the cube by the Friedrich method, using algorithms that I use in real life to solve the cube. Because of that, the output solving algorithm is quite a long one and I was wondering is there is a way to transform the output to an equivalent algorithm, but shorter. This might actually be impossible, but I think this is a question worth asking. For example here is a list of equivalent algorithms that orient the corners of the last layer of that cube state shown in the image.

L.E.:
Friedrich splits the solve in 4 steps(cross, inserting corners and their corresponding edges(F2L), orienting the last layer(OLL) and permuting the last layer(PLL)). So far my program only solves the cross, and I am now beginning to code the algorithms for the second step(F2L). All the algorithms I find online for F2L, OLL and PLL are designed to be remembered and/or executed as easily and naturally as possible, so they are not necessarily the shortest ones. Using Kociemba's program I can find shorter algorithms equivalent to those used by humans only for PLL, where the entire cube stays the same except for the edges and corners of the last layer. This is because Kociemba only gives the algorithms that leads to complete solve of the cube(and only for PLL we need this solution). For F2L for example I don't know what configurations I should put the cube in in order to output the algorithm that only inserts the desired pair(corner and edge) in the correct place and doesn't care about the cubies in the last layer, or the cubies in the other corners(that are not solved yet). I hope that makes sense. I make this program for a project for my Algorithms course, first year in CS and the requirements are that it must solve any given state of the 3x3x3 cube and output the shortest solution. I know group theory can be used, but it is much more complex and requires more time than I was given to finish the project, so I thought that Friedrich would be easier to achieve.

So far my outputs an algorithm for solving the cross that averages at 10 moves with a maximum of 19 in half turn metric. The execution time varies from 0.02 to 0.03 seconds per cube. This data was obtained from running the program on 1500 randomly generated cube states.


texts: How can one byte hold 256 possibilities?

texts:
Forgive this seemingly "troll-ish" question, but I must lack the ability to understand how one byte (two nibbles, eight bits, however you wish to describe it) can hold 256 different states, possibilities, values or such.

First of all, one bit would look like this:

Any way of being able to input two states (in the poor example above, two separate circuits at different voltages can be treated logically as "yes" or "no").

So if one bit is two possible states, multiplication factors yield that by two:

Bit = 2 values

Two bits = 4 values

Three bits = 6 values

Four bits = 8 values

Five bits = 10 values

Six bits = 12 values

Seven bits = 14 values

Eight bits = 16 values

In total, I get a sum of sixteen values multiplying the factors by two for every increasing bit. How would it make sense that one byte can hold 256 different values in a circuit?

In a four bit adder, we'd have something like this:

This also yields 8 possible values. How would it get 128? Could anyone clarify this confusion??

NOTE: This doesn't have to just apply to adders circuits with transistors and logic gates, but to the pits and lands on an optic disc, the platter representation of data on a disk drive, flash drive binary storage, RAM, anything. I just want to know how increasing factors of two is multiplied by (seemingly) powers thereof.


texts: Is it generally possible to convert CNF to Horn clauses?

texts: My intuition is that it is not generally possible, but I cannot think of a proof.


texts: Finding the final state of the $1$ dimensional "split the twos" automata

texts:
This problem is from a coding competition ( Website Here ) in Mexico that does not provide solutions and has me stuck.

Consider the following automata:

Every state $B_k$ is an array of fixed length $n$ such that $B_k[i]$ an integer for all $0\leq i \leq n-1$

The state $B_k$ can be obtained from the state $B_{k-1}$ as follows:

$B_k[i] = B_{k-1}[i] + C_{k-1}[i]$ if $B_{k-1}[i] < 2$ and $B_k[i] = B_{k-1}[i] - 2 + C_{k-1}[i]$ if $B_k[i] \geq 2$.

The quantity $C_{k}[i]$ is defined as the number of entries $B_k[i-1],B_k[i+1]$ that are at least $2$. (If $i$ is equal to $0$ or $n-1$ then $C_k[i]$ can be at most $1$).

We are given an arbitrary initial state $B_0$ of size $n\leq 10^6$ where each $B_0[i]$ is $0,1$ or $2$.

So in coloquial terms the only thing this automaton does is send a $1$ to the left and right if one of the entries is $2$ or more.

It is not hard to see that after a finite number of steps $B_k$ becomes invariant ( Because $B_k[0]$ cannot be equal to $2$ an infinite number of times we can use induction on $n$ for example) .

I would like to find the final state, something along the speed of $\mathcal O(n\log(n))$ seems to be required for the solution to pass.

Original statement:


texts: Unable to understand an inequality in an application of the pumping lemma for context-free languages

texts:
The problem

Prove that the language

$\qquad L = \{a^n b^j \mid n = j^2\}$

is not context free using pumping lemma.

Approach taken by the book

To prove such statements, the book takes the approach of a game played against an opponent who strives to fail our effort to prove that the language is not context free. The steps involved in the game are as follows:

The opponent chooses m such that for all w $\in$ L, |w| >= m
We choose the string w
The opponent decomposes w in uvxyz such that |vxy| <= m and |vy| >= 1
We pump v and y i-times to get the string uv$^i$xy$^i$z.

Now, if for any i = 0,1,2,...

uv$^i$xy$^i$z $\notin$ L

the language L is not context free.

The solution to the above problem

Opponent chooses m
We choose w = a$^{m^2}$b$^m$
The opponent decomposes w in uvxyz as follows:

Pumping v and y i-times yields string with m$^2$+(i-1)k$_1$ a's and m+(i-1)k$_2$ b's.
If opponent takes k$_1$ $\ne$ 0 and k$_2$ $\ne$ 0, we can take i = 0, such that

(m-k$_2$)$^2 \leq$  (m-1)$^2$             ... since k$_2\ne$ 0 making minimum value of k$_2$ is 1

= m$^2$-2m+1

< m$^2$ - k$_1$

Q. This last line I did not understand. How is -2m+1 < -k$_1$? Especially because I can find the below decomposition uvxyz for which -2m+1 > -k$_1$.

I must be missing some stupid algebra here.

The solution further continues saying that the pumped resultant string does not belong to L.

Similar argument can be done if user select k$_1$ = 0 and k$_2$ $\ne$ 0  or k$_1$ $\ne$ 0 and k$_2$ = 0


texts: I was having a look at the block product principle for finite monoids. I wanted to see the derivation of LTT = Acom$*$LI, using an example. But I can't come up with a non-trivial example of a monoid in LI. Any help is appreciated.


texts: How to prove that the decidable languages are closed against iteration only by enumerators?

texts:
We have the $L\in R$, how can we prove that $L^*\in R$ only by enumerators?

I try to use induction, but as I understand I wrong...
I'd like to get any help!


texts: Proof (by contradiction) of the emptiness problem

texts:
I fail to understand the proof of the Emptiness Problem

$E_{TM} = \{\langle M \rangle | M $ is a TM and $L(M) = \emptyset\}$

1) Use the description of $M$ and $w$ to construct $M_1$, which on Input $x$ behaves as follows:

If $x \neq w$, reject
If $x = w$, run $M$ on input $w$ and accept if $M$ does

2) Run $R$ on input $\langle M_1\rangle$

3) If $R$ accepts, reject; if $R$ rejects, accept

I do understand the basic idea of a reduction and in particular the reduction of $A_{TM}$ to $Halt_{TM}$, however,

I do not see how $E_{TM}$ could be used as a subroutine to solve $A_{TM}$. The whole construction of $M_1$ confuses me a lot. To me it looks like $M_1$ is just like a filter that rejects everything except $w$
But why does $M_1$ even have to check if $x$ equals $w$? As soon as $S$ is fed with a particular pair $\langle M,w\rangle$, $x$ will be equal to $w$, no? how can it be anything different than $w$?


texts: Improve the runtime of hashtable operations by keeping lists in sorted order

texts:
The following is a question from the textbook Introduction to Algorithms, however a solution to the problem is not given...

  Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?

For this question I believe the running time would be the same for searching if the list are sorted, because they are linked lists, and one still needs to traverse the entire list in order to find a value.

For inserting however, it would take longer because one can't just insert a value to the head of the list because the order must now be preserved. It would no longer be $O(1)$ I believe.

For deletion I have no idea.

In fact, I'm not quite sure if any of my answers are correct, can someone please help me out here?


texts: Finding a closed formula for recurrence relation

texts:
I'm trying to find a closed formula for the below recurrence relation:

For the first one, $n$ is some power of 2

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

$$T(n) = \begin{cases}
1  & \text{if $n=0$} \\
T(n-1) +3^n & \text{else}
\end{cases}$$

I tried to use the substitution and tree methods but I'm not sure what I'm doing and I think I get the wrong answer.