texts: Running time of random pivot quicksort on random and sorted arrays

texts:
I don't understand why I am getting the following execution times for the quicksort with a random pivot.
Times are in microseconds they are the average of five executions.
Random array:              9097
Sorted array:              4250
sorted backwards array:    4396
This doesn't make sense to me. It is obvious that the best execution time is for the sorted array, because you don't swap values, but why does the sorted backwards array have a similar execution time? Shouldn't it be more similar to the time obtained on a random array, or even bigger?
Here is my version of quicksort:
function sort(A[1], ..., A[n])
  if n ≤ 1, immediately return
  let x be a random number in 1, ..., n
  swap A[1] and A[x]
  i ← 2
  j ← n
  pivot ← A[1]
  while i ≤ j:
    while i ≤ n and A[i] < pivot: i ← i + 1
    while A[j] > pivot: j ← j - 1
    if i ≤ j: swap A[i] and A[j], i ← i + 1, j ← j - 1
  end while
  swap A[1] and A[j]
  sort(A[1], ..., A[j-1])
  sort(A[j+1], ... A[n])
end function


texts: How many structurally different trees can be formed with n nodes?

texts: Is there any exact formula for finding number of structurally different unlabeled trees can be formed with $n$ nodes? I searched a lot and I found some approximation formulas, e.g. here.


texts: Is there a term for the common semantics of global variables, static local variables, and fields?

texts:
I'm working on a graph representation of software for a static analysis project, and I'm finding a distinction that I have no name for between different types of variables.

On one side of the division, we have local variables and parameters, which are not subject to modification by other threads during the execution of a method. For these variables, static single assignment form is valid.

On the other side of the division, we have global variables, fields, and C/C++ static local variables, which can be modified by other threads, meaning static single assignment form is not necessarily valid, as the variable may be modified by a separate thread during the execution of the method.

Is there any existing term for this division?


texts: I wonder, how is that operating systems make use of libraries as stdio.h if they themselves are the services? I am right? Is the operating system that interacts with the hardware to operations of I/O? How you write to a file system with the C library, for example?


texts:
Given an undirected graph G(V,E), find the minimum number of vertices to remove so that the Edge Set of the graph becomes empty.
In other words: If we remove one vertex we remove that vertex along with all edges connected to that vertex. Find the minimum number of vertices to remove so that there are no edges left in G after their removal.


texts: Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?


texts: When a trained RNN is tested, is the number of time-steps same for every input?

texts:
I am a beginner in deep learning so bear with me. If I want to unfold the RNN in order to represent the relation of output to the input as a non-recursive functions I would have to know the number of time steps it takes for the RNN to make a prediction, correct? Hence it is important for me to know if the number of time steps is the same for every test input.

Will the number of time steps for an RNN which is unchanged in any way always stay the same?


texts:
Let $P$ be a given polygon in $\mathbb{R}^{2}$ such that all the vertices lie on integral points $\mathbb{Z}^{2}$. An integral polygonal sub-divison of $P$ is a subdivison of $P$ into integral sub-polygons. I would like to know:

If there is an algorithm to generate all such sub-divisons?  I would prefer an easier to implement (possibly less efficient) algorithm over a more efficient one. I do not want probabilistic algorithms unless they have a very high efficiency.
 To illustrate the problem here are some pictures:

The initial polygon is like this:

An allowed sub-divison

An invalid sub-divison

Thank you in advance.


texts: Is there a pseudo polynomial time algorithm for this 0-1 quadratic subset sum problem?

texts:
Say that we have some (integer) weights $w_{1,1},w_{1,2},...,,w_{m,m}$ and a target sum $W$.

Suppose that we want to find whether there are $a_1,...,a_m \in \{0,1\}$ such that

$$\sum_{i = 1}^{m} \sum_{j = i}^m a_i a_j w_{i,j} = W.$$

I read through the Wikipedia article on the quadratic knapsack problem. It mentions (but does not completely spell out why) that pseudo polynomial dynamic programming algorithms can only function as  a heuristic for the QKP.

Has it been shown that there is no pseudo polynomial time algorithm for this 0-1 quadratic subset sum problem under reasonable assumptions?


texts: a regular language so that $unary(L) \notin $Context Free Languages

texts:
I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free.

unary of $L$ is defined by:
$$unary(L) = \{0^{1x}  : x \in L  \}$$

Example $L = \{0, 11\} $ $\rightarrow  unary(L) = \{00, 0000000\}$

Any help would be great.


texts: Minimum number of states in DFA accepting strings where the numbers of a and b are divisible by X and Y respectively?

texts:
While studying automata theory a typical problem that I face is of the following type:

  Constructing a DFA with minimum number of states for all strings over
  $\{a,b\}$ which have number of $a$’s divisible by $X$ and number of $b$’s
  divisible by $Y$ (where $X$ and $Y$ are some positive integer values).

Is there some standard way of solving such problems?

I looked it up over the net and most people seem to have an idea that minimum number of states will be $X \cdot Y$. I don't think that is right. I constructed a DFA with 15 states for $X = 6$ and $Y = 8$.

Also along a similar line suppose the problem is changed slightly and we are
given "number of $a$'s mod $X$ = $P$ and number of $b$'s mod $Y$ = $Q$".

I believe this type of problem will also have a similar solution as the above problem. Only difference will be in the final states of the two machines. Can someone please confirm whether I am right about this?


texts: Why is a sequence of n Push, Pop, Multipop operations O(n²)?

texts:
From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453:

  Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The worst-case cost of a Multipop operation in the sequence is $O\left(n\right)$, since the stack size is at most $n$. The worst-case time of any stack operation is therefore $O\left(n\right)$, and hence a sequence of $n$ operations costs $O\left(n^2\right)$, since we may have $O\left(n\right)$ Multipop operations costing $O\left(n\right)$ each. Although this analysis is correct, the $O\left(n^2\right)$ result, which we obtained by considering the worst-case cost of each operation individually, is not tight.

Part of this seems badly written:

  [...] since we may have $O\left(n\right)$ Multipop operations costing $O\left(n\right)$ each.

Why would they count the number of some items in terms of running time, $O\left(n\right)$? The way I interpret this is that a sequence of only $n$ multipops(n) will result in $O\left(n^2\right)$, but after the first one, I imagine the stack is empty.

Someone try and explain how the worst case cost of a sequence of $n$ push, pop, multipop is $O\left(n^2\right)$. Or perhaps what may help is if you can rewrite the problem statement... maybe that's what is confusing.

Question:  Do the push, pop, and multipop cumulatively add up to $n$, or is it $n$ push, $n$ pop, and $n$ multipop operations?


texts: Proof of equivalence of regular expressions (0 + 1)(0 + 1)* and (0 + 1)*(0 + 1)

texts:
How would I prove that the regular expressions RS and SR where R = (0 + 1) and S = (0 + 1)* are equivalent? The '+' sign represents union of two regular expressions and two expressions RS are concatenated.

From what I know, either you must prove using existing rules about equivalence of regular expressions (example: commutativity or associativity of union) or you must prove that L(RS) is a subset of L(SR) AND L(SR) is a subset of L(RS) where L is the language denoted by the regular expression in the parentheses.

However, I am struggling to come up with a proof. Could someone give me a hint?


texts: Why splitted text files is bigger than a large one with the same content?

texts:
I have this large text file that when unzipped has about 2GB.
I split this one into multiple(more than 5 million) files and now I have a folder of about 20GB, how is this possible?


texts: Polynomial reduction, #P-hard problems, and approximations

texts:
Consider two statements.
Statement 1: The problem #3SAT (finding the number of satisfying instances to a 3SAT problem) is #P-hard.
Statement 2: Additively approximating #3SAT upto $\pm 2^{n/2}$ error is #P-hard (a proof is given here).
Now, consider any other problem B that is also #P-hard. The solutions to B lie in the set $[0, c]$, for $c > 0$ (for example, for #3SAT, $c = 2^{n}$, as there can be, at maximum, $2^{n}$ satisfying assignments).
Are Statements 1 and 2 sufficient to show that any $\pm \frac{c 2^{n/2}}{2^{n}}$ additive error approximation to B is also #P-hard?
More generally, given that an additive error approximation to a particular hard problem of a complexity class is also hard for that class, does this hold (upto a normalizing constant) for any hard problem of that same class? If not, is this statement true for multiplicative approximations? And are there explicit counterexamples?


texts: How to express Rob Pike's classic Go Code presentation in Hoare's CSP Algebra?

texts:
At 15:30 in this talk  (p13 of this presentation here) Rich Hickey mentions the formalisms available for reasoning about Communicating Sequential Processes. He then goes on to mention that these haven't yet been applied to Clojure's core.async.

The only reference I know of for CSP is Hoare's book. I can see some examples of formalisms to describe CSP here.

Suppose I wanted to do the most basic of CSP as per Rob Pike's presentation in Go (slide 43 of this).

var (
    Web = fakeSearch("web")
    Image = fakeSearch("image")
    Video = fakeSearch("video")
)

type Search func(query string) Result

func fakeSearch(kind string) Search {
        return func(query string) Result {
              //time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
              return Result(fmt.Sprintf("%s result for %q\n", kind, query))
        }
}

How would I express this as an Algebraic statement? What benefit would it give me?

Taking a stab at it - I get

(Web → P) Π (Search → Q)  Π (Video → R)

Which tells me that the Search process can choose to interact with Web or Video depending on which environment the Search Process chooses to communicate with.

Assumptions

I'm told that you can't do this in pure CSP because of the timer. For an answer I'm happy to  assume we'll ignore the timer part of this.


texts: Metrics on which Clock Cycles Per Instruction(CPI) depends

texts:
In the book - Computer Organization and Design: The Hardware/Software Interface [RISC-V Edition] by Patterson and Hennessy, CPI is defined like this:

The term clock cycles per instruction, which is the average number of clock
cycles each instruction takes to execute, is often abbreviated as CPI. Since different
instructions may take different amounts of time depending on what they do, CPI
is an average of all the instructions executed in the program. CPI provides one
way of comparing two different implementations of the identical instruction set
architecture, since the number of instructions executed for a program will, of
course, be the same.

I am solving question 1.7 from the Exercises section of chapter 1:

1.7 Compilers can have a profound impact on the performance
of an application. Assume that for a program, compiler A results in a dynamic
instruction count of 1.0E9($I_A)$ and has an execution time of 1.1 s($T_A$), while compiler B
results in a dynamic instruction count of 1.2E9($I_B)$ and an execution time of 1.5 s($T_B$).
a. Find the average CPI(both $CPI_A$ and $CPI_B$) for each program given that the processor has a clock cycle
time of 1 ns.
b. Assume the compiled programs run on two different processors. If the execution
times on the two processors are the same, how much faster is the clock of the
processor($P_A$) running compiler A’s code versus the clock of the processor($P_B$) running
compiler B’s code?
c.  A new compiler C is developed that uses only 6.0E8 instructions($I_C$) and has an
average CPI($CPI_C$) of 1.1. What is the speedup of using this new compiler versus using
compiler A or B on the original processor?

Attempted Solution:

a.

Using the formula $T = I * CPI * CC$
where $CC = $ clock cycle time, I calculated part a of the question
$CPI_A = \frac{T_A}{I_A * CC_A} = 1.1$
Similarly, $CPI_B = 1.25$

b.

Given, execution times on two different processors are same
Again using the formula, I calculated
$\frac{T_A}{T_B} = \frac{I_A * CPI_A * CC_A}{I_B * CPI_B * CC_B}$
My task is to find $\frac{CC_A}{CC_B}$, which I am unable to, since I don't know the value of $CPI_A$ and $CPI_B$.

c.

Again, using the formula, I calculated
$\frac{T_A}{T_C} = \frac{I_A * CPI_A * CC_A}{I_C * CPI_C * CC_C}$
My task is to find $\frac{T_A}{T_C}$, which I am unable to, since I don't know the value of $CPI_A$. Here I know that, $CC_A = CC_C$, since the processor remains same.

In part b and part c of the solution, will the value of $CPI$ be same as that calculated in part a. If so, please explain why? What are the metrics on which $CPI$ depends. Does it not change with processor, or execution time, or any other metric?


texts: BIT: Unable to understand update operation in Binary index Tree

texts:
I have just read this answer and was very satisfied and it is indeed a fantastic answer. It taught me the working of BIT.

But at the end, the second last paragraph is where I am struggling.
It says,

  Similarly, let's think about how we would do an update step. To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward. We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

But if I see, take some example, it does not work just as by simply switching 1's and 0's, according to me.

e.g. lets take we want to update value at node 5 = 101
Switching 1s and 0s, we get 010...
Now applying the procedure they have given earlier, we will end up updating some other node or so.

I must be getting it wrong. Please correct me.

Thank you in advance.


texts: algorithm for number of subsequences containing at most k numbers with no element repeated in each of the subsequence

texts:
For e.g if the array is 2,2,3,3,5 and k=3
there are total 18 subequences
1 subequence of length 0(i.e empty subsequence)
5 subsequences of length 1

8 subsequences with length 2

4 subsequences with length 3

how to proceed?


texts: Recently it's been in the headlines that IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory. This is several thousand times smaller than one would expect the memory requirements of such a simulation to be. How were they able to do this? Did their simulation run correspondingly faster? Does the capacity to simulate quantum computers this way using conventional algorithms have any impact on our current understanding of the capabilities of quantum computers when compared to classical ones?


texts: Genetic algorithm neural networks converges, but suddenly stops

texts:
I'm trying to create a genetic algorithm to train neural networks (because I'm to bad at back-propagation), and it works well until generation 18, where the loss stops to decrease and gets constant. The loss gets from 112 to about 90 in 18 generations and almost doesn't change:

Here is the genetic algorithm (I think the problem doesn't come from the neural network algorithm as it's very basic) in python :

# This is my reproduce function :
def reproduce(first,other,mutate=0):
    child = Entity() # Creates a new Neural Network (class Entity is the class of the Neural Networks)
    # Only two synapse matrices, each get the mean of its two parents
    child.syn0 = (first.syn0 + other.syn0)/2
    child.syn1 = (first.syn1 + other.syn1)/2
    if mutate:
        # Add some mutation if it's enabled, but it didn't work without it
        child.syn0 += child.syn0*(np.random.random()*mutate-mutate/2)
        child.syn1 += child.syn1*(np.random.random()*mutate-mutate/2)
    return child

ent = [Entity() for _ in range(20)] # Creates 20 new Neural Networks with random weigths on their synapses

nb_dna = 1
gen = 0
scores = []
max_gen = 100

while gen < max_gen:
    np.random.seed(int(time.time()))
    # The Neural Networks goes forward.
    for i,e in enumerate(ent):
        e.set_input(int(np.floor(np.random.random()*nb_dna)))
        e.forward()
        # In the forward function, the score is calculated as the result of a squared error cost function

    if gen < (max_gen-1):
        # Do natural selection
        ent.sort(key=lambda x: x.score) # Sort my ascending score (the lowest the score is, the closest the NN is to the expected result
        ent = ent[:4] # Kill all entities except the five 1st

        # Reproduce the winners
        for i in range(4):
            for j in range(4-i):
                # 1st reproduces with 2nd, 3rd, 4th and 5th,
                # 2nd with 3rd, 4th and 5th,
                # 3rd with 4th and 5th,
                # and then 4th with 5th
                    new = reproduce(ent[i],ent[j],mutate=0.2) # Changing the mutation rate "mutate" will only change the convergence speed
                    ent.append(new)
    gen += 1

Can you tell me if I'm doing something wrong, or if I'm going the wrong way ?
Else, is that the best I can get ? It's actually the first "real" genetic algorithm I create (previous ones were easy JS algorithm to try to find a target word, starting with random letters)


texts:
I understand how vector clocks detect concurrent events, but they are designed for a fixed number of nodes, so we can't easily add and remove nodes. And with interval tree clock we can.

Could you help me grasp how they work: Interval Tree Clocks: A Logical Clock for Dynamic Systems. I don't understand the graphic notation. Some examples with explanation would be greatly appreciated.


texts: Is there an algorithm to find out if a truthtable can be represented as 2-sat, and if so find its 2-cnf?

texts: I know that not all truthtables have a corresponding 2-cnf representation, but is there a way to find out if a given truthtable has a 2-cnf representation, and if so to find what that is?


texts: How to obtain edge set that containing the widest path from s to t by partitioning and searching?

texts:
Problem. To obtain a path from vertex s to vertex t whose minimum-weight edge must be the maximum one among the ones of all the paths from s to t. This path is just the bottle-neck path from s to t.

The following is my algorithm for finding bottle-neck path by sub-ranges searching. Actually I just want to get the smallest set that containing the widest path from s to t.

In the algorithm, searching is for the subset that contains path from s to t. The steps make sure the smallest edge in the result subset belongs to the widest path from s to t.

Suppose variables as the following.

$m$ -- the number of total edges.

$E_i$ -- the set which does not contain path from s to t at the $i_{th}$, while for all edges in $E_i$, the weight is bigger than or equal to the maximum minimum-weight edge in all s-t paths. $E_0$ is empty.

$T_i$ -- the set which is a sub-range that contain the maximum minimum-weight edge. We need to partition it into sub-ranges.

$k_i$ -- the number of sub-ranges at the $i_{th}$ recursion. It’s calculated out in Step 1.

Steps.

Step 1 - If $Size(T_i) = 1$ then the algorithm stops. Else $k_i = f(Size(T_i))$.

  $f(Size(T_i))$ is a function whose argument is $Size(T_i)$. I am not sure what it should be.

Step 2 - Partition $T_i$ into $k_i$ descending sub-ranges. We use $R_j$ to stand for the $j_{th}$ sub-range whose weight of edges are only smaller than the ones in $j-1$ sub-ranges before it.

  Partition is done by Fibonacci Heap. We don't need edges in one sub-set keep in order.

Step 3 - Let $Total = E_i$.

Step 4 - Repeat. Get sub-range $R_j$ from $k_i$ sub-ranges in descending order. ($k_i$ times at most)

$Total = Total + R_j$
If there is a path from s to t in $Total$(its cost is $O(m)$),

  we know that $Total$ contains the biggest minimum-weight edge.

$E_{i+1} = Total - R_j$.
$T_{i+1} = R_j$.

  In the next recursion, $R_j$ is partitioned to find a smaller set which
  containing the maximum minimum-weight edge.

Go to Step 1.

  Recursively increase $E_i$, and decrease $T_i$ and $k_i$. Until the $Size(T_i) = 1$.

After the algorithm stops, we get the target set $E_{i_{max}}$ containing all the edges which are bigger than or equal to the maximum minimum-weight edge. So the widest path from s to t is in $E_{i-{max}}$.

If set $f(Size(T_i)) = Size(T_i)/2$, on average, the final recursion time will be $i_{max} = log_2 m$.

My question is that there should be a better $f(Size(T_i))$, what is it? And how to figure it out?


texts: Random observations of a total ordering, how much they tell us?

texts:
Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know is a set of random observations from pairwise order of the elements. The observation matrix $B\in\{0,1\}^{n\times n}$ is  generated randomly as follows:
$$B_{i,j} \sim \begin{cases} \text{Bernoulli}(p)\qquad  \text{ if } i>j \\ 0  \qquad \qquad \qquad \text{ otherwise} \end{cases}$$
in which $p\in[0,1]$ is a constant. The formula above means that elements above diagonal are drawn iid from $\text{Bernoulli}(p)$ and the rest of the elements are $0$. Matrix $B$ denotes our observations of the ordering, i.e. if $B_{i,j}=1$ we know the the the order of $a_i$ and $a_j$, and otherwise don't. The reason that elements on the lower triangle of $B$ are zero is because symmetric observations are reduntant.

Question 1

Let $K$ denote the number of orderings of $a_1,..., a_n$ that are consistent with our partial observations. Since $B$ is a random variable, $K$ is also a random variable. The question is, what the expected value of $K$ and what is its concentration around the mean as a function of $p$? There are two extreme cases: (1) if $p=0$ all orderings are valid and hence $K=n!$ (2) if $p=1$ we have the complete ordering and $K=1$.

For $0<p<1$ however $K$ would not be a constant. My guess is that for sufficiently large $n$ if $p\gg \mathcal{O}(\frac{\log n}{n})$ would lead to to $\mathbb{E}[K]\to 1$. The rationale behind this is that we would have $\omega(np) = \omega(n \log n)$ comparisons which is an asymptotically larger than the number of comparisons most sorting algorithms make. However, this is far from clear since the observations are taken at random.

The answer is ideally a distribution with parameter $p$ for the number of possibilities. But if that's not possible, tail bounds or the expected value and variance are also acceptable.

Question 2

The motivation behind the definition of $K$ was to capture how much uncertainty is left. But it seems to be overestimating it or not express it very well, because if we don't know a few pairs $K$ will grow exponentially with this number. So I was thinking of another natural way to define it.

Let $O\in\{0,1\}^{n\times n}$ be the result of our observations, in which $O_{i,j}=1$ designates that we have observed $a_i<a_j$. From this matrix we can compute the transitive closure $O^\star$, which applies transitive property to find all the "smaller-than" relations in the data. For example if we have $O_{i,j}=1$ and $O_{j,k}=1$ we will have $O^\star_{i,k}=1$. This holds also for a chain of arbitrary length.

Let $S$ be the sum of all elements of $O^\star$. If we can conclude the relations between all pairs, $S$ will attain its maximum value of $S=n(n-1)/2$, and so $I=\frac{S}{(n(n-1)/2)}$ is a value which will show how much we know about the ordering, with $1$ meaning we exactly know the ordering, and $0$ meaning we don't know anything. Now the question is: what is its mean $\mathbb{E}[I]$ as a function of $n$ and $p$? And if it's possible to analyze, what is the concentration of $I$ around its mean? Also, what is the threshold for $p$ as a function of $n$ that makes $\mathbb{E}[I]$ jump to $0$ or $1$?

By simulations I found that when $n\to\infty$, even for a small value of $p=\frac{\log n}{n}$ leads to $I\to1$ with high probability. The reason for this seeming discrepancy between $I$ and $K$ is that if we have $m$ unknown pairs in $O^\star$, then $K$ will grow exponentially w.r.t $m$ while $S$ will only be affected linearly. Although the $I$ and $\log K$ are related, I don't think there is an exact relationship between them.


texts:
Given two integers $a$ and $b$, determine if $a$ and $b$ are equivalent modulo any $k \, (k: 1 \lt k \lt |a - b|)$.

If $\exists$ an integer $ (k: 1 \lt k \lt |a - b|) \text{ and }a \equiv b \mod k$, then the algorithm would return true, otherwise it would return false.

I thought of this problem today.

Before attempting to solve it, I want to know if there is existing literature on the problem. However, I would need to know the problem to do research on it.


texts: Floating point format: why must `1−emax ≤ q+p−1 ≤ emax`?

texts:
From the Wikipedia page on the IEEE Standard for Floating-Point Arithmetic,

  The possible finite values that can be represented in a format are determined by the base (b), the number of digits in the significand (precision, p), and the exponent (q) parameter emax:

  ...

  q must be an integer such that 1−emax ≤ q+p−1 ≤ emax (e.g., if p=7 and emax=96 then q is −101 through 90).

I can't figure out the reasoning behind the above inequality. I would've thought (in my simplicity) that it would be -emax ≤ q ≤ emax or something similar. What am I missing?


texts: How is the implementation of pipes in a OS

texts: I understand that a pipe is a form of IPC where a process creates a link to communicate with some other process (a child maybe), taking each one a end of the pipe. File descriptors are created for read and write and they can use it in half-duplex or full-duplex. My question is if the implementation of this schema is something like shared memory or message passing.


texts:
It is an open question that whether $\mathsf{DFS\text{}}$ can be done in $O(m+n)$ time and $O(n)$ bits of space, where $n,m$ represent the number of vertices and edges in a undirected graph. see this for DFS

DFS for directed graph is known to be in RNC i.e. randomised NC. $\mathsf{DFS\text{}}$ also known to be $\mathsf{P\text{-}Complete}$ problem.

My question is what would happen if someone shows that  $\mathsf{DFS\text{}}$ can be done in $O(n+m)$ time and in $O(n)$ bits of space?Is it likely in that situation for DFS to admit polyloga-rithmically fast, parallel algorithm using only polynomial resources (see this research paper)?


texts: Why are there multiple computer languages instead of multiple libraries?

texts:
If someone realizes that a computer language is deficient under some aspect or the other, couldn't he just create a library for the new language instead of a new language?

Couldn't you have a library In C that lets you process list as if they were lisp? Or that write simple code as if it was Python?

Why does evolution have to mean breaking with the past?


texts:
I'm trying to write a regular expression for some particular license plates. They consist of one up to three capital letters, a hyphen, one up to two capitol letters and one up to four numbers. The license plate should not exceed the 8 symbols.

Example: AA-AA123

What I have until now is the following:

because there has to be at least one letter before the hyphen, I have this expression for the first letter:
$$
P = (A\cup B \cup...\cup Z)
$$

For the second letter:
$$
D = (A\cup B \cup...\cup Z\cup empty)
$$
empty indicates the possibility that there could not be a letter.

For the numbers is basically almost the same procedure:
$$
E = (1\cup 2 \cup...\cup 9)
$$
$$
F = (1\cup 2 \cup...\cup 9 \cup empty)
$$

now for my explicit expression I think the answer would be:
$$
K= PDD^* - PDEF^*F^*
$$

but I'm not quite sure. I think this means I have 8 symbols, at least one letter before the hyphen but I could have up to three, the hyphen (that is a must), at least one letter after the hyphen but up to two and at least one number but I could have up to 4.

Something tells me I have something wrong here, I'm still new in the regular expressions world and I appreciate any help I could get in advance.


texts:
Assume that there are n students, who have to be evenly assigned to m groups. For every student, a preference ranking of of the m groups is given.

I partially order assignment by pointwise preference, i.e. one is better or equal to another if for every student, the assigned group is ranked higher or equal.

What algorithm can I use find “locally optimal” solutions, i.e. assignments where there are no strictly better solutions?

I assume there will be multiple locally optimal solutions. Is there a sensible way to order them without giving the students an incentive to be dishonest in their ranking, i.e. without encouraging strategic voting? If so, can that be solved?

And finally: What are the right terms to search for research that solves this and related problems?


texts: Are there competitions for integer programming?

texts: Are there competitions for integer programming like there are for SAT and MAXSAT?


texts: Is it NP-complete to decide if chromatic and clique numbers agree?

texts:
It is known that finding chromatic number $\chi(G)$ and clique number $\omega(G)$  are both NP-complete problems.

Is the problem

  Given graph $G$, is $\omega(G)=\chi(G)$?

NP-complete as well?

Side question: is there a name for such graphs?


texts: Modelling a basic sequential circuit as a transition system?

texts:
I'm going through Dr Joost-Pieter Katoen's slides and stumbled upon this:

For some reason I can't quite make out how the transition system relates to the sequential circuit. If I had a question for instance that asked me to convert the circuit into a TS, what steps should I take to approach it (using this one as an example).

Grateful for any help.


texts: Uniformly random efficient sampling of shortest s-t paths, with optimal random bits

texts:
Motivated by Efficiently sampling shortest s-t paths uniformly and independently at random,
The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of seemingly unnecessary random bits.
My question is:

Can the solution be improved to use a single random number in interval $[0,w(t))$, where $w(t)$ is the total number of shortest paths from $s\text{-}t$.
Alternatively, can the solution be improved to use $\left\lceil \log_2 w(t)\right\rceil $ random bits?


texts: Suppose we have a neural network (such as google uses for instance) which detects an object in images, which could be a cat or car. Suppose that it is instead an alien artifact that we dont have pictures of. What methods are there given this neural network to produce an image of the object it detects in images?


texts: Which type of control unit used in modern processor?


texts: Need help in a question regarding polynomial oracle reductions

texts:
Prove the following:

If there is a polynomial oracle reduction from $S1$ to $S2$:

a. If $S2\in\ P$ so $S1\in\ P$

b. If $S2\notin\ P$ so $S1\notin\ P$

The way I see it - If there is a polynomial oracle reduction from $S1$ to $S2$, you can solve $S1$ with $n^k$ questions to $S2$. If $S2\in\ P$, and $S2$ is solved with $n^k$ actions, it means $S1$ can be solved in $n^{n^k}$ actions - $\in\ P?!$

(I translated the phrase 'polynomial oracle reduction' from hebrew, so ask me if you don't understand what I meant).


texts: $P$-complete problems and Logspace reductions

texts:
It is known that HORN-3SAT is complete for $P$ under Logspace many-one reductions ($<_L^m$).

This implies that $\bar{A} <_L^m A$ for any $P$-complete problem $A$, where $\bar{A}$ means the complement of $A$. This immediately follows from that fact that $P$ is closed under complement and the $P$-hardness of $A$.

My question is to find such Logspace many-one reduction $\bar{A} <_L^m A$ for any $P$-complete problem $A$ (such as HORN-3SAT). The reduction must show the mapping between short certificates of $A$ and $\bar{A}$.

EDIT: As David stated in his comment on the case of HORN-3SAT problem,  we know that Logspace function exists but it seems that it is hard to find explicitly.


texts: A variant of Travelling Salesman: Is it NP-complete if its sub-problems are NP-complete?

texts:
Suppose there is a travelling salesman who wants to travel through N cities in k countries(k <= N). For convenience, he will travel all the cities within a certain country and then move to another. In each country, he wants to find out the shortest simple path to traverse through all the cities.[Classic TSP problem]

Q1. Suppose moving to another country costs nothing. Is that still a NP-complete problem? Any suggestion for a proof?

Q2. (There could be connections with certain costs between two cities in two different countries.) Suppose the salesman has to visit the countries (but not cities) in a certain order. Is that still a NP-complete problem? Any suggestion for a proof?

(Precisely, I should have used "NP-hard problem". I hope you can translate it into the decision version.)

Q1:
It is intuitive that a general TSP instance can be reduced to this problem for k = 1. What I know about is that you can reduce a general instance of a known NP-c problem into a "special" instance of the problem that you wish to reduce to. However, I think "k=1 (with N)" is a very special case that it is much harder than instances when k > 1. That's why I am not quite certain if this intuitive approach is correct.

"This is a dump of an exercise problem, not a question." I feel sorry for my algorithm teacher. I made this exercise up for a similar situation in my research (not in the area of algorithm for sure). If I let k = 1, the instance got reduced to seems to be the hardest instance which I doubt if it is general. Since the sub-problems are NP-c (in decision version), let the cost for jth country with m cities be $T_j(m)$, then $\Sigma_k T_j(m)$ is much smaller than $T(N)$. Also, the problem is not that hard when k = N. (k is part of the input?)

"Is it NP-complete if its sub-problems are NP-complete?" (So I made up the problem.) If so, that intuitive approach seems correct.

Q2:
I think it is kind of related to Q1. I didn't post it because I tend to solve it on my own.(Hints are welcome.) If you solve it, I may have to consider putting you as a coauthor later :).

Thanks


texts: I've heard that computers cannot forget anything, but yesterday my teacher told me that a computer can lose its memory from getting very hot. Is that true that computers can lose information? How and why does this happen? Can the lost information be retrieved back?


texts:
I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents.

Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the same size n, for each possible value of $i$ where $i \in [0, ... k]$.

A path is defined as k line segments connecting a sequence of k+1 coordinates, made up of one coordinate from each set $S_i$ in consecutive order. I want to find n paths such that (a) no two paths have the same point for a given index i in the sequence, and b) the combined path length of all the paths is minimized. In other words, assign coordinates from each set without replacement to construct paths with the goal of making the total path length as small as possible.

Right now i can do the minimization from some $i$ to $i+1$, but I am not sure if locally minimizing each step will yield a global minimum. I know I could brute force it, but that explodes really quickly.


texts: Is $n$ times $O(1)$ equivalent to $O(n)$?

texts:
I am having a hard time figuring out if
$$\sum^n_{i=0} O(1) =O(n)\,.$$

I think it doesn't but I am unable to find a convincing explanation for that, does anyone have an intuitive yet mathematical answer for that?


texts:
In Lovász writes [1] :

  bipartite graph has a perfect matching, which is a special case of the clique problem

Why is bipartite perfect matching a special case of clique problem?

The Work of A.A. Razborov by L. Lovász (1990)


texts: How to understand the notion of boolean query via Immerman's definition

texts:
A query is any mapping $I:STRUC[\sigma] \to STRUC[\tau]$ that is polynomially bounded. A boolean query is a map $I_b: STRUC[\sigma] \to \{0,1\}$. A boolean query can also be thought as the susbset:
  $$
\{ A \in STRUC[\sigma] \ \mid \ I_b(A) = 1 \}
$$

From this definition of query, used by Immerman in his book "Descriptive Complexity", how are boolean queries and general queries related? It seems from the definition that they are two different things entirely. Is there an intuitive way to link the two concepts? Thank you!


texts: what do the tape contents of a turing machine look like after halting?

texts: what do the tape contents of Turing machine look like after halting? Are there empty symbols after the qaccept or reject?


texts: Vertex cover problem with 2-element vertices

texts:
Let $G = (W, E)$ be an undirected graph, where $W = \{(v_i,v_j) \in V \times V : v_i > v_j\}$ and $E$ is a set of $2$-element subsets of $W$ such that, given two edges $e_1 = (w_1, w_2)$ and $e_2 = (w_1, w_3)$, $(w_2, w_3) \in E$ necessarily if there exists some $v$ belonging to $w_1$, $w_2$ and $w_3$. (For example, if $((v_1, v_2), (v_1, v_3)) \in E$ and $((v_1, v_2), (v_1, v_4)) \in E$, then $((v_1, v_3), (v_1, v_4)) \in E$.)

In such a scenario, we want to remove the minimum number of vertices in $W$ to disconnect the graph, taking into consideration that whenever we remove a vertex $w = (v_1, v_2)$, the rest of the vertices containing $v_1$ or $v_2$ must be removed as well.

My question is whether this is actually the vertex cover problem in disguise or, somehow, the restrictions applied above make it easier or more difficult to solve it.

As an example, consider the following graph, where it's clear that removing $v_2$, $v_3$ or $v_4$ leads to the disconnection of the majority of vertices in $W$.


texts: Big-O with nested loops and "variables" in the T(n)

texts:
So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code:

int sum = 0;
for(int i = 1; i < n; i *= 2) {
    for(int j = n; j > 0; j /= 2) {
        for(int k = j; k < n; k += 2) {
            sum += i + j * k;
        }
    }
}

Now from what I calculated for the loops, first loop runs log(n) times, second loop runs (log(n) * log(n)) times and the third loop is the one which is causing confusion, because I believe it runs for (n - j)/2 times. My question is can I assume it to be n/2 times, because I think it won't be a tight upper bound if I do that. Or is there a different approach that I am missing?


texts: What determines the number of inputs and outputs when initialising weights in a convolutional neural network?

texts:
Following Deep MNIST for Experts tutorial on Tensorflow, I realize I don't understand where the choice of numbers comes from when initializing weights.

In the tutorial, they first show the below function for creating random weights.

def weight_variable(shape):
  initial = tf.truncated_normal(shape, stddev=0.1)
  return tf.Variable(initial)

However, the shape parameter has me confused when the tutorial shows the next line of code:

W_conv1 = weight_variable([5, 5, 1, 32])

The tutorial says the following:

  The first two dimensions are the patch size, the next is the number of input channels, and the last is the number of output channels.

I don't understand the significance of the last two values, 1 and 32.

What decides what values you input there? And what do they affect?

When I'm designing my own neural network, could I put any value I like for the last two, or if I were to change them in a neural network would it 'break' the entire network?


texts: Finite Automata -- Determine if a set is regular

texts:
I have been at this for hours. The question is:

Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular,
where $\#(n, x)$ denotes the number of $n$ in string $x$.

So far, I have used the pumping lemma to determine that the opposite is not regular, i.e. that if $\#(0,x) \leq k$, the language is not regular.
I have also constructed a nondeterministic finite automaton that I thought I could use to prove that this set is regular since that is generally the way to go about proving regularity. I can't really draw it, but at start state $s$, if $0$ is read in, then move to state 1 (or state $'0'$). If a $0$ is read in, either stay in state 1 or move to state 2. If a $1$ is read in, move to state 2. However, I honestly don't know what to do further.


texts: How to find all minimum cuts in network flow

texts:
In a network flow graph, using the Ford–Fulkerson algorithm, we can find a residual graph G_f which no augmenting paths. This gives us a way of finding one minimum cut (a cut (S, T) with minimum capacity) where S is the set of vertices reachable from the source vertex s in G_f (and it is clear that this set of vertices are not in T, the cut that is on the side of the sink vertex t).
Analogously, we can repeat the Ford–Fulkerson algorithm to find a residual graph G'_f that is anchored at the sink t, such that we can find another minimum cut (S', T') where T' is the set of vertices reachable from the sink vertex t in G'_f. It is possible that (S, T) and (S', T') are different (see my made-up network flow below with 2 different minimum cuts):

The question there is, is there are more comprehensive way of finding other minimum cuts in the the flow network? Or are there only ever a maximum of 2 minimum cuts in a flow network?


texts: Language whose intersection with a CFL is always a CFL (2)

texts:
This is a follow-up to this question, which asks for an example of a non-regular language $L$ which satisfies the following condition, intersection resilience:

  If $L'$ is context-free then so is $L \cap L'$.

We know that all regular languages are intersection-resilient, and clearly every intersection-resilient language is context-free. Ginsburg and Spanier showed in 1964, in their paper Bounded ALGOL-like languages, that every context-free subset of $x^*y^*$ is intersection-resilient (Theorem 6.1, Corollary 2).

  Which languages are intersection-resilient?


texts:
I suspect this may be more of a concept / theory question, but, I haven't been able to wrap my brain around what exactly a binary file is.

I've read links such as the below:

https://en.wikipedia.org/wiki/Binary_file

https://betterexplained.com/articles/a-little-diddy-about-binary-file-formats/

But, the piece of the puzzle that's confusing me, is that ALL files are stored as 1's and 0's on a hard-disk, or, in RAM, etc.
(i.e. there's no physical engraving of the hex characters "6F" onto a disk platter for example; it's still a binary format that the data is stored in).

So, if all files are stored as binary, then, presumably it's an operating-system, (& filesystem) concept to refer to something as "binary" file?


texts:
I know that the subset sum problem is NP-Complete because I can reduce a known NP-Complete problem to subset sum.

However, since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete. I then realized that the dynamic programming solution in fact tries all possible combinations and because of this, is in fact the same as a brute force approach. Is this a valid insight into why subset sum is NP-Complete?


texts: Where can I find a data set of graphs with known domination numbers?

texts:
I implemented an algorithm to find the minimum dominating set of a graph. I want to check the output of the algorithm against some graphs for which the domination number has been determined.

Where can I find graphs with a known domination number?


texts: What is the formalism to prove statements about uniqueness of functions with certain signatures

texts:
Suppose I want a function like

f: ((A, B) -> C) -> A -> B -> C

A statement I've often seen made is that f has just one implementation, namely the 'curry function', i.e. g => a => b => g(a, b)

Taken at face value this doesn't seem to actually be true, I can always define f as acting differently from this in special cases, e.g. I can say it is g => a => b => g(a, b) except when A = B and then I define it as g => a => b => g(b, a).

Nonetheless, it's intuitively clear enough what is meant by 'has just one implementation'.

I would like to know the correct formalism in which statements like the above can be proven.

At a guess I would suspect it is category theory? The above feels a bit like the notion of a natural transformation, but I don't really see the details.


texts:
I need some help with the following task:

I have to construct a DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$.

How can I recognize that the new substring $y$ begins? For example: $w=zy$, where
$z = 1111$ and $y = 1001$.

This is what I have so far:


texts: What are some real world examples of nearly sorted lists

texts: I found that sorting algorithms such as Insertion Sort and Djikstra's Smoothsort approach O(n) complexity when the list is nearly sorted. What are some real world scenarios where a list is nearly sorted?


texts: Is there any use case for the bottom type as a function parameter type?

texts:
If a function has return type of ⊥ (bottom type), that means it never returns. It can for example exit or throw, both fairly ordinary situations.

Presumably if a function had a parameter of type ⊥ it could never (safely) be called. Are there ever any reasons for defining such a function?


texts: Is there a poly-time algorithm for expanding out polynomials

texts:
so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of
$$
z = (x+y)(x-y) \implies x^2+xy-xy+y^2
$$
but for any input with $n$ number of operations.
$$
z = (x_1+x_2+x_3+...+x_n)\cdot(x_1+x_2+x_3+...+x_n)\cdot...\cdot(x_1+x_2+...x_n) = ?
$$

I tried just doing the basic "by hand" method, but to me that seems like it would be on the scale of $n!$. Is there a better way of doing this? Thank you!


texts: How to understand pushdown automata intuitively?

texts: What is an intuitive way of understanding what a push down automaton is capable of computing?


texts:
I'm confused about how the bead-tiling algorithm for the Dubins' TSP from this article works:

On  the  Dubins  Traveling Salesperson Problems:
novel  approximation algorithms
Ketan Savla, Emilio Frazzoli, Francesco Bullo
http://www-bcf.usc.edu/~ksavla/papers/KS-EF-FB:06h.pdf

What does the algorithm return?  Does it return this path that has been going over all (meta-)beads almost log2(n) times? Or only the final path obtained from the last recursive phase?

  a  Dubins  tour  is  constructed  with  the  following
  properties: ...
  This  process  is  iterated ⌈log2n⌉ times, ...

Also, does this result path go back to the top left corner since it started there?
If yes, why waste some length of our path to go back to the top, instead of going to the first node encountered to obtain our Dubins tour?

  ... it  visits  all  (meta-bead)  rows  in  sequence  top-to-down, alternating between left-to-right and right-to-left passes, ...

A minor issue is also the complexity stated. it states the computational complexity is of order n. I personally thought it to be so much more.

  The  computational  complexity  of  the  RECURSIVE BEAD-TILING ALGORITHM is of order n.

All in all, to express it in one simple question :
What does the bead-tiling algorithm do?


texts:
I have a lexicographical order on integer $n$-tuples, where $(x,y,\dots) > (a,b,\dots)$ if $x>a$ or if $x=a$ and $y>b$, and so on to the end of the tuple (I called it lexicographic because of its similarity to the natural order on strings of $n$ characters). In this order I have a range, defined inclusively by a pair of tuples.

I also have a rectangular box in $n$ dimensions defined by a pair of integer $n$-tuple corners. A tuple is in the box if every one of its elements is greater than the corresponding element in the first corner, and also less than the corresponding element in the second corner.

Given two tuples to serve as the ends of the range (under the lexicographic ordering), and another two tuples defining the corners of the box, I would like to determine if there is any overlap between the tuples in the range and the tuples in the box. What is the most elegant way to do this?


texts:
I did some searching before I decided to ask this question and there was nothing similar to my question that helped me. So I came to CS stack-exchange for hints.
So, I am currently working on a proof to show that if $L$ is regular then $OP(L)$ is also regular without the use of pumping lemma. For the sake of this question, I am using $\{0,1\}$ as alphabet.

$$OP(L) = \{w \mid wz ∉ L \text{ for every } z ∈ \{0,1\}^+ \}.$$

At the moment, I have a hard time starting the proof. What I understand is that, if $L$ is regular then we can define a DFA that can decide $L$. And then we can define another machine for $OP(L)$ with every transition from $M$ along with $\epsilon$-transitions.

Am I on the right track? I could really use some hints.


texts: Topics from theoretical computer science suitable for a bachelor (undergrate) thesis?

texts:
Is the field of theoretical computer science so complex, that it is just "too much" for a bachelor thesis? Unfortunately I haven't found any old thesises because the relevant chair of the university hasn't been occupied for years.

Because of theoretical computer science is the only topic that really interests me, I thought of writing my bachelor thesis in this field. What would be suitable topics or at least fields that can be arranged in the limited focus of a bachelor thesis? I thought of topics like parametrized complexity or formal software verfication (which is actually a bit of the target)


texts:
Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)?

I have read this question but it asks for generations of all combinations, not combinations at random.

I general I'm aware of rejection sampling, however it's very inefficient.

I also came across reservoir sampling, but that appears to be primarily geared towards very large or unknown n. I'm more interested in large but finite n (definitely not large enough to not be able to fit in memory. Well. An n-sized array itself will fit in memory, but the state space of all n-choose-k combinations might not).

Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts?

Thanks in advance.

Edit: To be a bit more specific, a 5-choose-3 space over the string 'ABCDE' would look like this:

['ABC', 'ABD', 'ABE', 'ACD', 'ACE', 'ADE', 'BCD', 'BCE', 'BDE', 'CDE']

(Note: this is combination without replacement). And I want to be able to sample from this space with uniform distribution, using a general algorithm (one that works with arbitrary n and k).


texts:
I was reading Wikipedia about the von Neumann bottleneck.

Surely there is some simple answer to this. Why can we not read and write to the same address at the same time? We can if the addresses are different.


texts: Double exponentials vs single exponentials

texts:
Here are four tenets I cannot reconcile:

Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant
Exponential time algorithms run in $O(2^{n^k})$ with $k \in \mathbb{N}$ constant
The former bound grows stricly faster than the latter; i.e., there exist algorithms that run in double exponential time but not in exponential time
Applying $a^{b^c} = a^{bc}$ to the double exponential bound we have $O(2^{2^{n^k}}) = O(2^{2^{nk}}) = O(2^{2nk})$, which falls within the previously stated exponential bound

I feel I am missing some subtlety relating to the definition of an exponential-time algorithm as running in $O(2^{\mathrm{poly}(n)})$ rather than $O(2^{n})$, but I am not sure precisely where the subtlety lies.


texts:
Parser-generators like nearleyjs can return a parse forest instead of a parse tree.
Since not all input may result in a parse forest (eg, the input may exercise only a non-ambiguous subset of the grammar), how do you programmatically choose the 'correct' parse tree from the forest?
One option is to always choose the first element from the array of parse-trees returned.
Another option is to flag the returning of a parse-forest (instead of a single tree) as an error. But then, this would defy the whole point of having Earley-like parsers that allow parsing of ambiguous grammars!
Also, since only some input may result in a parse-forest (instead of a single parse-tree), how do you rule out surprises in a live/Production environment? Assumption: For non-trivial or non-trivially long grammars, it's not humanly possible to create tests that cover all inputs.


texts: Why does the inequality $d[v_i] \ge d[v_i−1] + w(v_i−1, v_i)$ hold when all vertices are labelled with their shortest path values upon?

texts:
Let $G = (V, E)$ be a weighted, directed graph with weight function $w : E \to R$, and let $s \in V$ be a source vertex. Assume that G does not contain a negative cycle reachable from $s$. Then, if we execute relaxation steps resulting in $d[v] = \delta(s, v)$ for all $v \in V$ . Then the predecessor subgraph $G_\pi$ is a shortest-path tree rooted at $s$.

When proving that the unique path in $G_\pi$ are shortest paths, in CLRS, we assume a path  $p = (s = v_0, v_1, . . . ,v_k = v)$ to be a path in $G_π$.

For $i = 1, 2, . . . k$ we have both $d[v_i] = \delta(s, v_i)$ and $d[v_i] \ge d[v_i−1] + w(v_i−1, v_i)$.

How does this inequality hold when proving the correctness of the algorithm that calculates the shortest path tree? Since upon termination and according to the hypothesis, $d[v] = \delta(s, v)$ for all $v \in V$, by the triangle inequality, shouldn't the inequality be$d[v_i] \le d[v_i−1] + w(v_i−1, v_i)$ ?


texts: Automaton-based model checking on finite traces

texts:
I want to check whether a formula in finite LTL is valid on a finite, linear trace.

For infite traces I would create a Kripke structure of the trace and a Büchi automaton for the negated formula, and check if the intersection is empty.
Would this also work with a finite trace and formula in FLTL? I already tried adding another atomic proposition "alive" to the Kripke structure and automaton (like here https://spot.lrde.epita.fr/tut12.html). But how could I do it without this additional atomic proposition?


texts: Sometimes two outpus of Fredkin gate are swapped when constant bit is 0, sometimes when it is 1. What variant is right or more modern? If it was conscious decision to change behavior what was motivation for it?


texts: Lamport's Bakery algorithm with other > relation

texts:
i'm reading an old exam and one question was:
Which property of the Bakery algorithm is violated with the following change?

- mutual exclusion
- deadlock freedom
- starvation freedom

Algorithm: (i is the number of a thread)

choosing: array[0..n-1] of boolean (init false);
number: array[0..n-1]

loop forever:
1:  choosing[i]<-true;
2:  number[i]<-1+max(number);
3:  choosing[i] <-false;
4:  for all j in {0,..,n-1} with j!=i do
5:     await(choosing[j]=false)
6:     await((number[j]=0) or (number[j],j)>>(number[i],i))
7:  critical section
8:  numbe[i]<-0;

Change: Replace Line 6 with await((number[j]=0) or (number[j]>number[i]))

I think the deadlock freedom is violated because it is possible that two threads get the same value for number[i]. If two threads have the same number no one will pass the new 6. line. Is that correct? And if deadlock freedom is violated, is starvation freedom automatically violated too?


texts: How can I divide a set of strings into subsets of fixed size with maximal homogeneity?

texts:
Suppose I have a set of 1000 binary strings of fixed length. I wish to divide these 1000 strings into 10 subsets of 100 strings each, in such a way that the subsets are maximally homogeneous. I want each subset of 100 to be as internally similar as possible. Similarities between subsets of 100 are of no consequence.

I believe the best way to quantify homogeneity for my purposes is with simple matching coefficient. A straightforward greedy algorithm to define the subsets appears to be $O(n^2)$, but I'm not convinced this finds the optimal result. Is there proof either way? Is there another algorithm I should consider? Another homogeneity metric?

The resulting algorithm needs to be polynomial time.


texts: Where is the theory about "binary toggling games"?

texts:
Let us -- using parameters $M, N$ and $L$ --

create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in
\{0\ ..\ N-1\}, \forall k \in \{0\ ..\ M-1\}$.
create an N-bit long vector $A_0$ and initialize it to ones.
create an $M$-bit long vector $S$ and initialize it randomly in the same manner as any $V_k$.
for $i$ from $0$ to $M$, if $S[i] = 1$, then $A_i = A_{i-1} \oplus V_k$, otherwise $A_i = A_{i-1}$, resulting in $A_M$ after $M$ steps
present an agent/player with $A_M$ together with all vectors $V_k$ and make him return $S$ or the set of indices of vector $S$ where $S[i] = 1$. It follows that $A_M \oplus V_{i_0} \oplus V_{i_1} \oplus V_{i_2} \oplus\ ...\ \oplus V_{i_{last}} = A_0$.

A simple example with $N=4$ and $M=3$:

$A_M = [0, 1, 0, 1]$, $V_0 = [1, 1, 0, 1]$, $V_1 = [0, 0, 1, 1]$, $V_2 = [0, 1, 1, 1]$

solution $\rightarrow S = [1, 0, 1],$ because $A_M \oplus V_0 \oplus V_2 = [1, 1, 1, 1]$

This problem occurs in many games I have encountered and never really gave it much thought, until now. For the purpose of this question, I have called it the "binary toggling game".

What I wonder is:

what are "binary toggling games" really called
what is the theory being them: algorithms, their complexity (classes), edge cases, etc.

Could you please provide links? I hope they exist.


texts: Using the pumping lemma to prove that a language is context-free

texts:
I am new to automata theory.

Could you give me a little hand with the correct use of the pumping lemma?
I understand now how to proof a language is not context-free, but how do I use the pumping lemma to proof it is?

Do I find one way to break the word into: uvwxy so that v and x can be pumped? Is that enough and can I pick it in such a way that u or w or y are empty. I understand from the lemma that as long as v or x are not empty it is good. But can only w be empty and the rest be at least one character?

I did read on this topic, but I am just trying to make sure that what I understood is correct and there aren't other not so obvious things I should consider. Please help.


texts: Can we find size of total interval in O(N)

texts:
Let's say we have given $N$ intervals in the form $[x, y]$, both $x,y$ are integers , we want to find the number of integers covered by at least one interval of all $N$ intervals,  (look in the example for better understand).

The intervals may or may not intersect.

Example: Let N = 3, and the intervals: $a_1 = [1, 5], a_2 = [3, 7], a_3=[5,7]$ The count of the integers is 7, because they cover the numbers: $1,2,3,4,5,6,7$

Is it possible to get such size in $O(N)$ time complexity

I tried to come up with solution but I think that we should sort the intervals in some way and then to search them in linear time, but I cannot think how should we make the search and how to sort them.


texts: Why is a negative number a pseudo-positive number in ones' complement?

texts:
I'm studying ones' complement representation and I read in a book that a negative number in ones' complement is a pseudo-positive of value $R^n - 1 - |x|$.

However there is no demostration and I can't find it anywhere. If someone could tell me the reason I will be very thankful.


texts: Is this a syntax error or a semantic error?

texts:
I came across the following question

The error in the expression " if x>y x=2; " is detected by
a. Syntax analyzer
b. Lexical analyzer
c. semantic analyzer

I know that the parentheses of x>y are missing, but it is not syntax error right? as all the syntaxes are correct, but we are missing a pair of parenthesis.. so is this a semantic error?
The correct answer is given as a.


texts: Regular set corresponding to regular language

texts:
I have  just started learning regular expressions and I don't have anybody around me to help me building conceptions. So I rely on online mediums. My question is whether every regular set corresponds a language.
I had a regular expression $(0+10^*)$ and I was trying to find the regular sets. My books suggests that $L=\{0, 1, 10, 100, 1000, 10000,\ldots\}$. But I was thinking why they did not consider the strings starting with $0$ and then only one $1$ and zero or more number of occurrences of $0$, like $010, 0100, 01000$ etc.

Aren't these strings belong to $L$?
Is this $L$ a language? (According to me, it is a language because it is the set of strings over $\{0,1\}$.


texts: $\lambda$-terms equal modulo $\alpha$-renaming, is this an equivalence relation?

texts:
Want to clarify few things.

It is said that two $\lambda$-terms are equal up to renaming of bound variables, such as $\lambda x.x$ equals $\lambda y.y$, so I think it is a relation actually, about how two terms are equal.

Is that (such equality up to renaming) is same as equivalence relation?

To show a relation is an equivalence relation on a set, have to prove it is reflexive, symmetric, or transitive. I know, but have not done any practice on it.

Let's say, I want to prove following

$\frac{}{x = x}$    \two variables
$\frac{ t_1 = t_3  \,\,\, t_2=t_4 } {t_1 \, t_2 \, = \,t_3 \, t_4}$ \applications
$\frac{ t_2=[y / x]t_2 }{\lambda x.t_1 \, = \, \lambda y.t_2}$ \abstractions

where $[y / x]t_2$ replace $x$ by $y$ in $t_2$ and $y$ is not occur in $t_2$.

I think above 3 rules are true.

How can I show proof of they holds? does that proof related to the proof of $\alpha$-equivalence is an equivalence relation on $\lambda$-terms?

I am bit fonfused, it would be great if anyone help me clear things for me.


texts: Equivalence of two definitions of mutual information

texts:
I am learning quantum computing and as a background study, I am currently learning fundamentals of classical information theory.
I thought it best to ask my doubts here.
In Nielsen and Chuang, it is stated that mutual information I(X:Y) of two random variables X and Y is the information they have in common while in some books, it is written that mutual information I(X:Y) is the information one variable(say X) has about the other(say Y). I can't understand it intuitively how the two definitions are equivalent. Also, the symmetric property of mutual information,i.e., I(X:Y)=I(Y:X) is obvious to me from the first definition but not from the second one.


texts: Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?

texts:
I read a theorem which states that:
If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant performance ratio r, then NP = P.

But I never understood the reasoning behind this!!


texts: Is there a decidable problem which has a proof that it cannot be proved to have a particular deciding Turing machine?

texts:
I came across the question Is there an algorithm that provably exists although we don't know what it is? I was able to follow the example "Given an integer $n\ge0$ is there a run of $n$ or more consecutive 7s in the decimal expansion of $\pi?$" given in one of the answers. The answer shows that the problem in example is decidable although we don't know which is the correct algorithm. Let $P$ be a problem which is decidable, we know that for some for some finite integer $k > 1$ one of the Turing machines $M_1,M_2,..,M_k$ decides the problem, but we don't know which of them exactly is the decider. Is it possible that $P$ has a finite proof which tells us that it is not possible to prove exactly which of the machines is the decider ? Or is it always, that the proof exists proving that exactly one of the machines is the decider but we don't know it ?

I am not even sure if my question makes sense. I could make changes or remove the question if it does not not. Sorry for the vague definition of a proof.


texts: Robustness of non-context-free proof against trivial manipulation

texts:
First, we state here a theorem that is well-known in computability theory:

  $L=\{xx\mid x\in\Sigma^*\}\notin CFL$ for every fixed $|\Sigma|\geq2$

And, the standard proof is using pumping lemma. At first sight, we rarely face the language $L$ exactly as defined above in a broader theoretical research. Instead, what might be more frequent is $$L'=\{\text{some-simple-manipulation}(x)x\mid x\in\Sigma^*\}$$ Perhaps, those simple manipulation are necessary for unambiguous encoding. For example, symbol doubling, prefix, postfix, etc. Those are quite frequent and unavoidable.

Now, the question is: Can the above theorem still hold under these simple manipulations?

Symbol doubling (as commented below) is a good starter, if one feels the question too broad.

Or even worse, there may be some simple manipulation that push $L$ down to CFL again.


texts: What are randomized algorithms and what are they used for?

texts:
I wanted to know what are randomized algorithms and what are some of their uses?

When do you think they outperform "standard" algorithms?


texts: How do computers remember where they store things?

texts: When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?


texts: Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$

texts:
I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold.
$T(n)= 5T(n/4) + n^2$
Guess: $T(n) = O(n^2)$
Prove: $T(n) \leq cn^2 $
Breakdown
$ T(n) \leq 5(c(n/4)^2) + n^2 $
$ = (5/16)cn^2 + n^2 $
$ \leq cn^2 $
For the last step to hold I'm not sure what the value of c should be because of the (5/16). My guess would be c >= 1 and I'm not sure if that would hold.


texts:
I'm aware that a qubit can exist in an infinite number of states and that when measured it collapses into one state, with the probability of each state being directly affected by it's latitude.

My question is: Why is this in any way useful? Surely you can't use a unit of information meaningfully when you don't know what it will be..?

Surely, not knowing what a quantum bit is going to be is detrimental to computing? I'm evidently missing something since we know that quantum computing works, but why?


texts: Replacing n with 2n in asymptotic bounds

texts:
I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.

In the proof of the theorem $6$ of the paper on page 632, the authors go on proving the difference between the probabilities of sampling all irreps, $|p - q|_1$ of a subgroup inside the symmetric group $S_n$.

I want to compute the same bound for the symmetric group $S_{2 n}$. Should I just replace the $n$ in $2^{-\Omega(n)}$ and make it $2^{-\Omega(2n)} = 2^{-\Omega(n)}$?

Or, do I have to work it out from the scratch as follows?

$$
| p - q|_1 = \sum_\rho | p_\rho - q_\rho|
 \nonumber\\
  \le \sum_\rho \frac{d_\rho}{\left(2 n\right)!} 2^{O\left( n\right)}  n^{\frac{n}{2}}
  \nonumber\\
   \le \sum_\rho \frac{\sqrt{\left(2n\right)!}}{\left(2 n\right)!} 2^{O\left( n\right)}  n^{\frac{n}{2}}
    \nonumber\\
     \le  \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}}{\sqrt{\left(2 n\right)!}}
        \nonumber\\
            =  \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}\sqrt{\left(2 n\right)!}}{\sqrt{\left(2 n\right)!}\sqrt{\left(2 n\right)!}}
                    \nonumber\\
            =  \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}\sqrt{\left(2 n\right)!}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}\sqrt{\left(2 n\right)^{2n}}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}\left(2 n\right)^{n}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}n^{n}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{3n}{2}}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{3n}{2}}}{\left(2 n\right)^{\left(2 n\right)}}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{3n}{2}}}{ n^{2 n}}
\nonumber\\
= \frac{2^{O\left( n\right)}  }{ n^{\frac{n}{2}}}
\nonumber\\
= \frac{2^{O\left( n\right)}  }{ 2^{-\frac{n}{2}} n^{\frac{n}{2}}}
\nonumber\\
= \frac{2^{O\left( n\right)}  }{  \frac{n}{2}^{\frac{n}{2}}}
\nonumber\\
\le \frac{2^{O\left( n\right)}  }{  \left(\frac{n}{2}\right)!}
\nonumber\\
\lll 2^{-\Omega \left(n\right)}
$$


texts:
This is more of a conceptual question.

I have learned about Neural Nets, and I have some clue as to how Support Vector Machines work. I read somewhere however that given the appropriate kernel (is that right?), the SVM is identical to the Neural Net. Could someone who understands this please enlighten me as to how that's possible?


texts: Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?

texts:
Let $n, k > 0$ and $0 < m < nk$. I want to fill an $n$-length array $A$ with random integer values in the range $[0,k]$ such that $\sum_{i=0}^{n -1} A[i] = m$. Furthermore, all such arrays should be equally likely (that is, any valid array should occur with equal probability to any other). For example, if $n = 3, k = 2, m = 3$, any of these results should be equally likely:

$$[0,1,2]$$
$$[0,2,1]$$
$$[1,1,1]$$
$$[2,1,0]$$
$$[1,2,0]$$
$$[1,0,2]$$
$$[2,0,1]$$

The closest solution I could find was this, which is $O(n)$ assuming that we use a linear-time sort and shuffle (such as radix sort and Fisher-Yates respectively). However, this approach does not limit what the integers in each array position can be. Is there a $O(n)$ algorithm which solves the version of this problem described above?


texts:
I have converted nfa to dfa. But when I checked with some examples, it looks like it is wrong.

This is the full question.
Convert the nfa defined by
δ(q0, a) = {q0, q1}
δ(q1, b) = {q1, q2}
δ(q2, a) = {q2}
δ(q1, λ) = {q1, q2}
with initial state q0 and final state q2 into an equivalent dfa.

First, I made a table.

             a          b
ɸ            ɸ          ɸ
{q0}         {q0,q1}    ɸ
{q1}         ɸ          {q1,q2}
{q2}         {q2}       ɸ
{q0,q1}      {q0,q1}    {q1,q2}
{q1,q2}      {q2}       {q1,q2}
{q0,q2}      {q0,q1,q2} ɸ
{q0,q1,q2}   {q0,q1,q2} {q1,q2}

Finally, I have drawn dfa according to table above.

The bold line is accepting state.

Thanks for your help/


texts: How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n]

texts:
I was asked this question today:
given a very long string x, which contains only lower case alphabets. A valid substring can only started with [a, b, c, d, e] and ends with [h, i, j, k, l, n]
IF we sort the valid substrings alphabetically, what will be the first one and what will be the last one?
If we do need to sort all the substrings, then we might need a suffix tree or suffix array. However, here we do not need to sort --- we don't care all the substrings except the first and last one. So I am wondering if there is any more efficient solution than using suffix array.
Thanks


texts: Reachibility between first and last layer in grid graph in logspace

texts:
I am trying to prove that there exists logspace deterministic Turing machine that check if exists path between first row and last row in grid graph. Grid graph is matrix of $0s$ and $1s$, the undirected edge exists between two $0s$  or $1s$ - one the left, right, up, down.   Path can contains only $0s$ or only $1s$.

For example in following graph there exists such path:

0 0 1 0
0 0 1 1
0 0 0 1
0 0 0 1

For following there is no such path

0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1

How to prove it ?


texts: Computational complexity of generating a random vector

texts:
I'm new to the concept of computational complexity and trying to understand the topic in depth. I went through some references mentioned by some old questions, however, I had this question and not sure if my understanding is correct.
I want to know the complexity of generating a uniform random vector, over $[0, 1]$, of size $N$ using say a random number generator in Python or Matlab.
Is it $\mathcal{O}(N)$ cause I'm generating $N$ random numbers and the complexity of generating each one of them is $\mathcal{O}(1)$ or is it simply $\mathcal{O}(1)$?


texts:
I have  a system where disk requests come to a disk drive for cylinders in the order 10, 22, 20, 2, 40, and 38 at a time when the disk drive is reading from cylinder 20.  The seek time is 6ms per cylinder.  I have to find total seek time if the disk scheduling algorithm is First-Come-First-Serve (FCFS).

To find the answer I used a formula:

total seek time=0.254*sqrt(d)(for each cylinder and sum them)

But that gave the incorrect result.
What formula(s) should I be using to handle questions like this?


texts: Recurrence for quaternary search algorithm

texts:
I have to come up with the recurrence for the quaternary search algorithm.

My initial thought is $T(n)=4T(\frac{n}{4})+c$ because the algorithm examines all four subproblems, and each is one quarter the size of the entire array. But this can't be right because that yields a complexity of $O(n)$. I looked on Google and the complexity of quaternary searches are supposed to be $\log_4n$, but I don't know what the recurrence would be to get me that complexity.

Any help would be greatly appreciated. Thanks!


texts: Communication complexity and query complexity model

texts:
I have some doubts for the relationship between communication complexity model and query complexity model. In my understanding, query complexity model are same as decision tree complexity model. Let $F(x, y) = f(g(x_{1}, y_{1}), ..., g(x_{n}, y_{n}))$, then based on lifting theorems, if the dimension $d$ of binary strings is large enough, then deterministic communication complexity of $F$ is equal up to $d$ times the decision tree complexity of of $f$.
My question is, could we basically draw the claim that all the complexity result on computing certain $f$ we obtain on query complexity model is similar (with some constant factor) as in communication complexity model on computing certain $F$, at least when $d$ is large ?


texts: Is there a name for the class of operations containing prefix, suffix, etc?

texts:
I'm currently doing some research on operations on languages, specifically prefix, suffix, infix and outfix.

For example, for a language $L$, the prefix set of $L$ is:

$pref(L) = \{x \mid xy \in L, y \in \Sigma^* \}$

Infix is

$inf(L) = \{w \mid xwy \in L, x,y \in \Sigma^* \}$

and outfix is:

$outf(L) = \{xy \mid xwy \in L, w \in \Sigma^* \}$

I'm wondering, is there a name for the "class" of operations which contains all of these? I think I might have seen "bitfix" used in a paper somewhere, but it seems to mean something different.


texts: How many telescoping constructors will I have?

texts:
The Builder Pattern solves the problem of Telescoping Constructors; that is, having a single constructor for every possible parameter combination (including those combinations for which a parameter is omitted).

So for example:

  public Food(int id, String name) {
    this(id, name, 0, 0, 0);
  }

  public Food(int id, String name, int calories) {
    this(id, name, calories, 0, 0);
  }

  public Food(int id, String name, int servingSize) {
    this(id, name, 0, servingSize, 0);
  }

  public Food(int id, String name, int fat) {
    this(id, name, 0, 0, fat);
  }

  public Food(int id, String name, int calories, int servingSize) {
    this(id, name, calories, servingSize, 0);
  }
  public Food(int id, String name, int calories, int fat) {
    this(id, name, calories, 0, fat);
  }

  public Food(int id, String name, int servingSize, int fat) {
    this(id, name, 0, servingSize, fat);
  }

  public Food(int id, String name, int calories, int servingSize, int fat) {
    this(id, name, calories, servingSize, fat);
  }

If you set the Builder Pattern up properly, using the voluminous amount of code required, you can simply:

Food food = new FoodBuilder().SetName("Bananas").SetCalories(120).Build();

using any combination of parameters in any order.

Assuming that each parameter in the constructor will always reside at the same relative location while still allowing for omitted parameters, how would one calculate the number of constructors required given the number n of optional parameters needed?

(in the above example, id and name are required parameters, while calories, servingSize, and fat are all optional parameters).


texts: Consensus number of memory-to-memory swap

texts:
I think that consensus number of mem-to-mem-swap(a,b) operation which atomically swaps the values between shared locations a and b (shared R/W memory) is infinite , but I'm having trouble proving it.
I thought about implementing CAS with mem-to-mem-swap but comparing atomically is problematic, I think there is straightforward consensus protocol but I can't think about one.


texts:
Classical DFS:
A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic.
A DFS is usually used to find an ordering of the tasks that satisfies all of the precedence constraints, classical DFS algorithm can do it by building the sequence step by step.
An extension:
Consider now the following variation. Each node $j$ is weighted by a value $w_j$. When we are currently at node $j$, this weight will determine the next node to visit (the one with the higher weight).

Moreover, imagine that each time a node is added to the list, we recompute the weight for the unvisited nodes using a given function (we don't care about the nodes that has already been added to the sequence).  Thus at step $t$, the $w_j(t)$  of node $j$ can be different from its weight at step $t+1$.

Questions: Is there a name of this problem ? How to solve it efficiently? (e.g If a node has several successors, one needs to determine the successor with highest weight, so which data structure to use?)
N.B The image is only used for an illustration purpose. The graph is not assumed to be a binary tree.
Edit: the graph is assumed to be connected


texts:
I'm having some thoughts and I'd like to have your opinion about it.
Given a basic, normal instance of SMP (men-women, men choose), we define $\mu$ to be the set of all stable matches.

Each member of $\mu$ consists of men-rank, which describes the satisfaction index of the men - which in this case the member with the highest rank is the male-optimal match.

So if we run the stable-match known algorithm, the output would be the match with the highest rank, because the algorithm always returns the men-optimal and female-pessimal match - lets denote this match by $A$.

Now, lets replace the roles, and run the algorithm again.
We denote the output match by $B$ - which is the female-optimal and male-pessimal match.

Assuming $A=B$:

Can we say that this instance has a unique stable match?
What else can we say about this instance?


texts:
During the process of deadlock detection, the wait-for graph can be obtained from the resource-allocation graph. To detect whether there is a deadlock using the wait-for graph, can topological sort be used?

By making a slight modification, i.e., instead of removing the source as done in usual topological sort, we can remove the node (here, node represents a process) which does not point to another node first and proceed in this manner. As soon as the algorithm detects that it cannot proceed further and there are still nodes existing in the wait-for graph, it can be concluded as deadlock.

Other tags are topological-sort and deadlock-detection.


texts: A real life system that faces and solves the dining philosophers problem

texts:
I'm looking for an application of the dining philosophers problem. Is there some real life system that faces the concurrency problem of "the dining philosophers problem" and implements a solution? I've been searching for over an hour.

It would be even better if the implemented solution is Tanenbaum's solution described here.


texts: Is there a name for X when X bitwise OR Y is Y?

texts:
I'm wondering if there is a mathematical or computer science term for a number X such that Y | X = Y? For example:
66536 | 1000 == 66536

In this case, 1000 is the "insert name here" of 66536. Perhaps there is no name for this..? I've tried searching for "bitwise OR returns itself" and other such terms but without luck so far.


texts: Finding the Range of Solutions for KSum Variation

texts:
Preface

I asked a question before where I was looking to understand the complexity class of the following problem:

  Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.

I had found a $O(k)$ algorithm as hinted at by the accepted answer. After playing around with the results of this algorithm, I found that it was not 100% what I was looking for.

Problem

Given a range of integers $\{a,a+1,...,b-1,b\}$, find the range of the $i^{th}$ element of all subsets of size $k$, sorted in increasing order, that sum to $s$:

For example, given $k = 3$, $a = 1$, $b = 8$, and $s = 11$ we get the following list of all possible solutions sorted in increasing order:

{ 1 | 2 | 8 }
{ 1 | 3 | 7 }
{ 1 | 4 | 6 }
{ 2 | 3 | 6 }
{ 2 | 4 | 5 }

By grouping each column, we can see the ranges of values for each of the $i^{th}$ elements in the set:

$\{1,2\}$
$\{2,3,4\}$
$\{5,6,7,8\}$

Question

I would like an algorithm that in constant time could generate the range of values for a $i^{th}$ element for all subsets summing to $s$ for a given $a$ and $b$.

 get_ith_range(int k, int a, int b, int s, int i)
    int lower_bound, upper_bound
    // Some cool O(1) algorithm...
    return (lower_bound, upper_bound)

I do not mind if it is not $O(1)$, but I feel as though there should be a way to get there at least in $O(k)$.

Attempts

Currently, I have a way to generate the smallest for the $1^{st}$ range and the largest for the $k^{th}$ range (not in constant time though). But, I have not been able to even get to where I could generate the full $i^{th}$ range in any case.

Using my solution from my previous question, I can in $O(k)$ time produce the smallest possible value and the largest:

while k:
    k -= 1
    temp = int((k)*(2*a+k-1)/2)
    if s > b+temp:
        yield b
        b -= 1
        s -= b
    else:
        yield s-temp
        while k:
            k -= 1
            yield a+k

The last value generated by the above algorithm will be the smallest possible value. Also, the first value generated is the largest possible value.

Although, the largest can be done trivially (which is how I came up with the above greedy algorithm):

# (number of values)*(smallest + largest)/2 => sum {smallest,...,largest}
temp = int((k-1)*(2*a + k - 2)/2)
if s < b+temp:
    max = b-temp
else:
    max = b


texts: How does Instruction Set Architecture (ISA) affect performance?

texts:
If 2 CPUs have the same Instruction Set Architecture, which of the following properties will be the same?

Clock Rate
CPI
Execution time
No. of instructions
MIPS


texts:
A cache-aware sorting algorithm sorts an array of size $ 2^{k} $  with each key of size 4 bytes. The size of the cache memory is 128 bytes and algorithm is the combinations of merge sort and insertion sort to exploit the locality of reference for the cache memory (i.e. will use insertion sort when problem size equals cache memory).

  What are the best case and worst case running time of the algorithm?


texts: Keep k+ties largest elements in a stream

texts:
I have $n$ numbers that come one by one, and when the last element comes, I want to output $k$ largest elements and those that are ties with the minimal element from this top-$k$ element.

For example, I have $[10, 7, 7, 9, 10, 10]$ and $k = 4$, then I want to output $[10, 9, 10, 10]$. However, if $[10, 7, 7, 9, 10]$ and $k = 4$ I want to output $[10, 7 , 7, 9, 10]$. Note that in the first example number of unique elements is less than $k$.

If I didn't want these ties, I'd probably use min-heap and keep track of top-$k$ elements in that heap, replacing minimum every time larger element comes from the stream. However, with ties I would have to perform searching inside the heap the element if it's already there and only then perform replacement/addition.

What is the best way to keep track of top-k + ties elements from the coming array of integers?

Note: $n>>k$.


texts: Are Turing machines with a limited but exponential tape decidable?

texts:
The Halting problem for Turing machines which work on a tape of at most $k$ cells can be solved: There is a limited number of distinct configurations available, providing an upper bound of steps before nontermination is determined.

Now let us give each cell an exponent: It stores how often the symbol in the cell is to be repeated, i.e. we use a run-length encoding. The machine then works on this tape under preservation of the exponent.

The number of distinct values is still limited to $k$, but the effective tape length is no longer bounded. I'm fairly certain this class of Turing machines suffers from the Halting problem just like regular, unbounded machines do, but I'm looking for a concise proof.

$k$ can be assumed to be $\geq 7$.

Example:

Starting in configuration $x^3$ A $y^2$ $z^5$ with $\delta(A,y) = w,right,A$ and $\delta(A,z) = v,left,B$, execution will be:

$x^3$ A $y^2$ $z^5$
$x^3$ $w^1$ A $y^1$ $z^5$
$x^3$ $w^2$ A $z^5$
$x^3$ $w^1$ B $w^1$ $v^1$ $z^4$

In this example, the maximum number of cells used so far is 4 (or 5 if the head is seen as a splitting point), seen in the final step. The total effective tape length is $3+2+5=10$, but this number is not limited for our purposes.

Just for curiosity, to make the example machine nonhalting, replace $\delta(A,z) = v,right,A$ and add $\delta(A,\sqcup) = u,right,A$, and the machine will increase the exponent of $u$ indefinitely.


texts: Flow in a network: Conservation of flow definition

texts:
This might be too easy... But I just don't get it.

I've been reading about flow in networks and I stumbled upon this definition in wikipedia: https://en.wikipedia.org/wiki/Flow_network

$\sum\limits_{w\in V} f(u,w) = 0 $
$(\forall u \in V-\{s, t\})$

That implies
$\sum\limits_{(u,v)\in E} f(u,v) = \sum\limits_{(v, z)\in E} f(v,z)$

It sounds trivial, but how does that implication work?
The flow is 0 when there is no edge. So I think I can rewrite the first sum to:

$\sum\limits_{w\in V} f(u,w) = 0 \iff
\sum\limits_{(u,v)\in E} f(u,v) = 0 $ for a node $u$

That would result in every flow being zero, wouldn't it?
What am I doing wrong?

Thanks in advance :)


texts: Reducing context-free languages with polynomial-time reductions

texts:
So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$.

Can $L \le_p M$ ? Why or why not? How do polynomial time reductions even work with CFLs in general?


texts: Is the "modular subset product" problem NP-complete?

texts:
While examining some $NP$-complete problems relating to sets of integers, a question flashed through my mind: whether the $NP$-completeness of these problems is retained when integer arithmetic is replaced by modular arithmetic?

A concrete example is the subset product problem, which was known to be $NP$-complete. I wonder if we consider the problem over ring $\mathbb{Z}_n$, as formulated below, it is still $NP$-complete?

  Given $t, n \in \mathbb{N}$ and a finite set of integers $S$, determine whether there exists $S' \subseteq S$ such that $\prod_{s \in S'}s \equiv t \pmod n$.

My principal difficulty in approaching the problem is that I cannot figure out how the (polynomial) reduction works, supposing the $NP$-completeness is retained, due to the "cyclic" behavior of modular arithmetic. I've tried to search for variants of the problem but no luck. Thank you for any explanations, suggestions or references.


texts: Is $\lceil\log n\rceil!$ polynomially bounded?

texts: Considering the definition, $f(n) = O(n^k)$, for some constant $k$. If I choose $k = 100$ and plot, it shows $n^{100} > \lceil\log n\rceil!$  for all $n > 1$.  However, the solutions to Introduction To Algorithms (2009) say  that $\lceil\log n\rceil!$ is not polynomially bounded. What's going on?


texts: How to Add IEEE 754 Floating Point Numbers

texts:
I'm trying to add two 16 bit numbers that use a similar format as IEEE 754. The format is in the image below:

I can't figure out how to add together two numbers for the life of me.

Specifically, 0x82A3 + 0x0B98. In my attempt to solve this, I got 0x0B98 as the final sum, but that doesn't seem right to me.


texts: Applying Case 3 of Master Theorem to $T(n) = 9T(n/3) + n^3$

texts:
Given $T(n) = 9T(n/3) + n^3$,
I know that $a =9$, $b=3$, and $f(n) = n^3$
and $n^{\log_{3}9} = n^2$
thus Case 3 applies: $n^{\log_{b}a} < f(n)$, $n^2 < n^3$.
Can someone explain how to apply the regularity condition and how to check the regularity condition?
$af(n/b) \le cf(n)$ where $c < 1$
I appreciate your help!


texts: Can graph execution be better optimized than imperative programs?

texts:
I've been reading about Google's TensorFlow, and the way it represents calculations with graphs that are then executed by an engine. While the concept is interesting, I would like to understand why they made that choice instead of the arguably simpler imperative programming found e.g in PyTorch.

The TensorFlow documentation lists several advantages:

  Parallelism. By using explicit edges to represent dependencies    between operations, it is easy for the system to identify operations that can execute in parallel.
  Distributed execution. By using explicit edges to represent the values that flow between operations, it is possible for TensorFlow to partition your program across multiple devices (CPUs, GPUs, and TPUs) attached to different machines. TensorFlow inserts the necessary communication and coordination between devices.
  Compilation. TensorFlow's XLA compiler can use the information in    your dataflow graph to generate faster code, for example, by fusing together adjacent operations.
  Portability. The dataflow graph is a language-independent    representation of the code in your model. You can build a dataflow graph in Python, store it in a SavedModel, and restore it in a C++ program for low-latency inference.

Portability makes sense, I'm more interested in the performance aspect. It seems that doing parallel and distributed computations doesn't require graph execution, since PyTorch does it too. I assumed that creating a graph enabled the engine to do optimizations that could not be done with an imperative program.

But then I read about TensorFlow's upcoming eager mode, which basically does away with the graph API and lets us use imperative programming like in other libraries. The documentation for eager mode suggests that it approaches and could reach the performance of graph mode:

  For compute-heavy models, such as ResNet50 training on a GPU, eager
  execution performance is comparable to graph execution. But this gap
  grows larger for models with less computation and there is work to be
  done for optimizing hot code paths for models with lots of small
  operations.

One thing I didn't find is distributed training with eager mode, but as mentioned earlier, other imperative libraries seem to offer that despite not using graphs.

I'm not sure what to make of this. Does graph execution have a performance advantage over imperative programming after all?


texts: Is there a computer language with optional dependent types?

texts:
I'm looking for a computer langauge with "dependent types" but...
The problem with it having a full implementation is that you end up having to write formal type proofs to get even anything simple done. (Agda/Iris). These are fine if you are writing a proof checker but not for general programming.
As a compromise it would be nice to have a language that would allow "unsafe" dependent type casting where you don't have to give a proof. e.g. you might have a type "PrimesBiggerThan3" and a type "OddNumbers" and you could cast from the first to the second without having to give a formal Type Proof. The proof could just say "TrustMeOnThis".
Does such a language exist, or is there one like this that is useful?


texts: How do I find depth and height of all nodes in a bounded semilattice?

texts: I'm writing a program where I have a bounded semilattice (it has a root element at the top, all edges point downwards, and a node may have multiple parents). I need to precompute each node's depth (the max number of edges from the root node) and height (the max number of edges to any leaf). I have a naive implementation for just the heights where every node is compared to all it's descendants, so probably O(n^2). What is a faster algorithm that computes both height and depth?


texts: How to convert a recursive function to a non recursive one using stack while keeping memoization?

texts:
Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'.
I could simply count it using a recursive function as follows:
def num_ways(s: str) -> int:
    if len(s) > 0 and s[0] == '0':
        return 0

    if len(s) <= 1:
        return 1

    if len(s) >= 2 and int(s[:2]) > 26:
        return num_ways(s[1:])

    return num_ways(s[1:]) + num_ways(s[2:])

However, this function can be easily optimized by using memoization technique. (I'll avoid showing off memoization into that code to keep it tidy, but you can assume I could use such a decorator that would be responsible for this job)
Alright! But what if I want to use a stack to replace that recursion? (I don't want to use a bottom-up dynamic programming approach in this case)
So I could have something like this:
def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)

    ways = 0
    while stack:
        cur_s = stack.pop()

        if len(cur_s) > 0 and cur_s[0] == '0':
            continue

        if len(cur_s) <= 1:
            ways += 1
            continue

        if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
            stack.append(cur_s[1:])
            continue

        stack.append(cur_s[1:])
        stack.append(cur_s[2:])

    return ways

It works! But how can I optimize it by memoizing duplicate work as well as I'm able to do in the recursive method? Moreover, is there a better way to convert from a recursive function to a stack-based non-recursive one?


texts: What are the differences between propositional logic and temporal logic?

texts: I am currently studying temporal logic and find it much similar to propositional logic. However, temporal logic seems to be slightly more specific because it encapsulates more precise meaning symbols, like until, eventually, next etc.. My question is are there other major differences with temporal logic and propositional logic? And can everything expressed in propositional logic be expressed in temporal logic too and vice versa? Perhaps, why would one use one over the other or vice versa?


texts:
There's an interview question.

In my opinion, os can calculate cache hit rate and miss rate(with the total running time of process and the number of transfer of block of memory to cache).
But how can know the size of cache? Is it possible to calculate with os's certain information? (such as size of transfer size to cache)

We can assume anyting we need to calculate easily(like only one cache-no l1 l2 and so on, cache is fully associative or set associative or directed mapped and so on)


texts:
I never learned a lot of mathematics (generally only arithmetic) and never learned computer science in a formal frame.
I emphasize that I don't mean to ask about a "function" in programming ("procedure"/"method"), rather only about the difference between the formal definition of function in mathematics to the formal definition of function in (theoretical) computer science, if at all there is any such difference (unless computer science don't share the exact definition common in mathematics).
Is there difference between a function in mathematics to a function in computer science?


texts: Algorithm to find smallest difference in array

texts:
We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array.

One such algorithm is to sort the array and check adjacent pairs of numbers. This takes time $O(n\log n)$.

Is there a faster way, e.g., an $O(n)$ algorithm?