texts: $O(1)$ time, $O(1)$ state random access Brownian motion?

texts:
I would like to generate discrete samples $0 = B(0), B(1), \ldots, B(T)$ of a Brownian motion $B : [0,T] \to \mathbb{R}^d$.  It is possible to get $O(\log T)$ time random access into a consistent sequence of samples $B(k)$ by  constructing the path in tree fashion.  We choose $B(T) = \sqrt{T} Z_0$ where $Z_0$ is a standard Gaussian, then let  $B(T/2) = B(T)/2 + \frac{\sqrt{T}}{2}Z_1$ where $Z_1$ is an independent standard Gaussian, construct $B$ for the intervals $[0,T/2]$ and $[T/2,T]$ independently conditional on $B(0), B(T/2), B(T)$, and so on recursively.

Since any particular $B(k)$ constructed in this fashion only depends on $O(\log T)$ Gaussian random values, this gives us $O(\log T)$ time random access into a consistently sampled sequence of Brownian motion as long as we have random access random numbers.  The only state   we need is the random seed.  As long as we use the same seed, evaluations of $B(k)$ for different $k$ will be consistent, in that their joint statistics will be the same as if we had sampled Brownian motion in sequential fashion.

Question: Is it possible to do better than $O(\log T)$, while preserving the $O(1)$ state requirement (only the seed must be stored)?

My sense is no, and that it would easy to prove if I found the right formalization of the question, but I don't know how to do that.


texts:
Consider the following computation: 2^N (TWO TO THE POWER OF ‘N’, for Int. N>0),
being executed on a processor with 32 bit internal, user and ALU registers.
The registers rightmost bit is bit 0 and the leftmost bit(the sign) is bit 31.
WHAT is the SMALLEST value of ‘N’ that will cause the Overflow Status Flag (V) to be set?

Seems like the calculation should be as simple as plugging values in for N but I don't quite understand if there are any other components to take into account, any help is appreciated.


texts:
I've managed to get a VM code of a function that performs integer division. After some work, I translated it into high-level language. I know the translation I made is correct, since I was able to compile it and get the exact VM code I started with.
I'm providing here the high-level pseudo-code.

   function int divide(int x, int y) {
        int i, res, isNeg, var3;
        if(y = 0){
            Sys.error(3);
        }

        isNeg = ((x<0) && (y>0))  ||  ((x>0)&&(y<0));
        B[0] = Math.abs(y);
        x = Math.abs(x);

        while((i<15) &&  (!var3)){
            var3 = (32767 - (B[i] - 1))  <  (B[i] - 1);
            if(!var3){
                B[i+1] = B[i] + B[i];
                var3 = (B[i+1] - 1) > (x-1);
                if(!var3){
                    i = i + 1;
                }
            }
        }

        while(i > (-1)){
            if(!((B[i] - 1) > (x - 1))){
                    res = res + A[i];
                    x = x - B[i];
            }
            i = i - 1;
        }

        if(isNeg){
            res = -res;
        }
        return res;
    }

Some notes: A and B are both static arrays. A holds all the powers of 2 (i.e A[i] = 2^i, i=0...15). Each int variable is 16-bit in 2's complement representation (and thus, 32767 is the greatest number that can be represented).
The thing is, I'm not sure how the algorithm works (and it does). Could someone explain this division algorithm?


texts:
I have a homework question that is as follows:
L(P) is a language of ASCII input strings for which a given program, P, returns "yes". Is the set of all input strings P decidable, such that P is a decision program and L(P) is decidable?
My intuition leads me to believe that the set is, in fact, decidable but I am having a tough time proving my answer.
Would appreciate any help on this. Thanks


texts: Alternative Method for Computing Two's Complement Binary -> Decimal

texts:
I proposed this method of converting a two's complement binary number to decimal to my professor and he said it was wrong. Some older guy in the class just shook his head at me and gave me a condescending stare. I'm willing to admit I'm wrong when I'm wrong but I can't find a case where it doesn't work.

Example

Take a two's complement binary representation of -38

1 0 1 1 0 1 0

The method I was taught is, starting at the right, keep the bits until you encounter a 1. Then flip all bits after that one. Which gives

0 1 0 0 1 1 0 = 38

The method I thought was easier since it doesn't involve any binary manipulations is treat the most significant bit as having a minus sign. So you would simply calculate the answer as

1*(-64) + 0*(32) + 1*(16) + 1*(8) + 0*(4) + 1*(2) + 0*1 = -38

What is wrong with my method?


texts: Can the House Robber problem be solved with a Sliding Window solution?

texts:
I was reading an article on how to solve sliding window problems and it said:

Fast/Lagging
This one is a little different, but essentially the slow pointer is simply referencing one or two indices behind the fast pointer and it’s keeping track of some choice you’ve made.
In the House Robber problem you are trying to see what the maximum amount of gold you can steal from houses that are not next door to each other. Here the choice is whether or not you should steal from the current house, given that you could instead have stolen from the previous house.

So, I tried to solve the House Robber problem using a Sliding Window (fast/lagging) solution.  It worked for a lot of test cases, but there were some that it just would not solve.
I came to the conclusion that it wasn't possible as the problem is recursive (you don't know whether to rob this house and next-door-but-one unless you know whether to rob next-door-but-one and next-door-but-one, unless you know whether... etc. etc.)
So, I clicked the Solution button on leetcode and the solutions presented were recursion and tabulation.
Is it possible to solve this problem using a 'sliding window'?


texts: How do I prove regular/non-regular with Nerode-Theorem? How to use it?

texts:
$L_{1}=\left\{w \in\{a, b\}^{*} | \#_{a}(w)=0\right\}$

$L_{2}=\left\{w \in\{0,1\}^{*} | w=u v u \text { with } u, v \in\{0,1\}^{*}\right\}$

I have problems to prove regularity with the nerode theorem

The idea behind this is that the nerode classes have to be finite for a regular language

How do I use this?

For L1 I know this

There is only $b^{n}$ due to the fact that there language does not accept any a

Let m$\neq$n than there exists $b^{n}b$ and $b^{m}b$ for all m $\in \mathbb{N}$\n an n $\in \mathbb{N}$\m and of all them are in L

For 2 I know this

Let vu be x so for all a,b $\in \{0,1\}^{\star}$ ax an bc are in L.


texts: Is Newton's Method to compute the zeros of a function an algorithm?

texts:
Looking for Newton's method in Wikipedia, I read the following:

  In numerical analysis, Newton's method (also known as the
  Newton-Raphson method), named after Isaac Newton and Joseph Raphson,
  is a method for finding successively better approximations to the
  roots (or zeroes) of a real-valued function.

After describing briefly the method, the Wikipedia page adds:

  This algorithm is first in the class of Householder's methods,
  succeeded by Halley's method. The method can also be extended to
  complex functions and to systems of equations.

The emphasis on "algorithm" is mine.

I know Wikipedia is not always to be trusted, and I have been
wondering whether Newton's method as described in Wikipedia does
qualify as an algorithm, and what could be the reasons why it would
qualify or not qualify.

The same question applies to other similar methods, such as the whole
family of Householder's methods, also described in Wikipedia, but an
answer in the Newton-Raphson case is enough.

Note, as a last remark, that the same question could be applied to Euclid's method to compute GCD as described in Wikipedia, though I expect the answer would be: "yes, because ...".

Related questions:

What exactly is an algorithm?
Do Turing machines assume something infinite at some point?


texts: Partition partition with constraint of equal size

texts:
I see the problem here which is the well know partition problem but with constraint that the size of both sets must be equal.

I look at the answer and I don't understand that why Colin said add max(S)⋅length(S), and run the algorithm as normal would make the size of both sets equal. I think for long time.

And i think that his claim for send s∈S to 1+s⋅length(S) is wrong?

Example:

Initial set: 1 2 3 9

1+s⋅length(S)= 1+s(4)=5 9 13 37

After running the traditional Boolean algorithm, what I got is one set of 5 9 13, another set of 37?

Can anyone explain to me? Especially the max(S)⋅length(S) one.


texts: Compiler backend generated from declarative description of the architecture

texts:
Is it possible, given a declarative description of an architecture's register layout and instruction semantics and machine code encodings, to autogenerate a compiler back-end?

If so, has anyone ever done this?


texts: Using visible line segments to compute a visibility polygon

texts:
Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the region in $P$ consisting of all points $q$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ is completely in the polygon $P$.

As for now, let's ignore the case where a line segment lies completely on the ray.

Now I have a collection of line segments (edges of the polygon) which are visible from point $p$. The problem is that not every line segment in the collection is fully visible which is why I can't simply connect them into a polygon. I first need to compute which part of each line segment is visible and connect those. This last step is what I struggle with.

Here are two examples:

In the left example edge $\overline{AD}$ is partially seen from $p$, in the right example it's $\overline{GH}$ (rest of the edges are completely visible).

For the left example, how can I use the fact that $\overline{EB}, \overline{BC}, \overline{AD}$ and $\overline{DE}$ are visible from point $p$ in order to compute the visibility polygon?

I struggle with finding an algorithm to do this which doesn't fail for every second case I apply it to. Any suggestions?


texts: parsing at semantic level due to ambiguities

texts:
I have a VHDL elaboration engine/simulator. As I understand it, the language syntax allows for ambiguities at syntax level. That is, an assignment

pin_value <= bus(5)

can be interpreted as picking a child of the bus by index. Here the bus is a signal (an object). However, it can also be that paranthis are applied to a type

int_signal <= integer(1.1)

which should be interpreted as type conversion.

I wonder. The elaborator should take the parse tree, instantiate objects and tie them together resolving the names. However, the parser has no idea if the prefix at the parensis is a type or array. So, it treats all parensis as indexed objects.

simple_assignment ::= target <= value_expression { , value_expression }
value_expression ::= name | literal | function_call | type_conversion
name ::= simple_name | indexed_name
indexed_name ::= prefix ( expression { , expression } ) // example: REG_ARRAY(5)
type_conversion ::= type_mark ( expression )

I do not see how can I distinguish between value_expression and type_conversion at syntactic level. My parser parses both as indexed_name and name resolution, when fails to find array object, falls back into type conversion. I am asking if such case analysis it the only way to handle the problem or more strighnforward approach exists that I am missing?


texts: why swap function is use in union find algorithm? How rank or size array is used for optimization

texts:
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (size[a] < size[b])
            swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
}

Q1.why we need this swapping?
can't we do like this without swapping

if (size[a] < size[b])

        parent[a] = b;
        size[b] += size[a];

Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node


texts: Is the set $\{ | L(M) \text{is a finite set}\}$ RE, co-RE or neither?

texts: $<M>$ is the encoding of a TM and L(M) is the language accepted.


texts: what does this phrase mean: "train a policy network"

texts:
I am familiar with the basics (and perhaps a substantial amount of basics) of imitation learning and reinforcement learning. In IL (imitation), we take demonstrations from an assumed expert, which we also assume has the most efficient policy.

What does this statement mean: This will train a policy network using the expert dataset and store the results.

Question: Why do I need to TRAIN a policy network? What is it for?
Are there any algorithms that come with this training a policy?

Thanks


texts:
I want to understand what are addressing modes that can be used in IBM Power8 microprocessors.
In Pdp 11, Most operands can apply any of eight addressing modes to eight registers.
But how having  124 × 2 GPR, What are the addressing modes does Power8 has and does it work like the pdp-11 or differently?
Apparently the manual doesn't have enough information about how many different ways you can access memory.


texts: How do I compare these ranges of numbers efficiently?

texts:
I'm looking for an efficient way of testing eights.  What happens is I need to check if a value is eights and discard it.

The numbers I need to check for are:

8.8888, 88.888, 888.88, 8888.8, 88888.00                // 5 digits
88.8888, 888.888, 8888.88, 88888.8, 888888.00           // 6 digits
888.8888, 8888.888, 88888.88, 888888.8, 8888888.00      // 7 digits
8888.8888, 88888.888, 888888.88, 8888888.8, 88888888.00 // 8 digits

However, these are actually represented in integer form.  Which is the number multiplied by 10000.

So 8.8888 is represented as an int64 with the value 88888, and 888888.00 is represented as 888880000

There are quite a few values here to check.  My simple approach was to just compare each one directly from a table.  But then I thought perhaps I should maybe do something more efficient like masking and comparing each digit.  But my crude approach did not work.  It seems cumbersome and potentially a bit slow to convert to a string and compare eights that way.  This code will run on an embedded system which checks these values many times over so I would like it to be reasonably performant and easy to understand.

Note that I won't have less than 5 digits represented or more than 8 really.

This is what I am currently doing.  Not sure if it's the best approach but it works.

bool TestEights(__int64 rt)
{
    char rts[20];
    bool eights = true;

    sprintf_s(rts, sizeof(rts), "%llu", rt);

    int len = strlen(rts) - 1;
    int dec = len - 5;
    for (int i = len; i > 0; i--) {
        if (i >= dec) {
            eights &= rts[i] == '0' || rts[i] == '8';
        }
        else {
            eights &= rts[i] == '8';
        }

    }

    return eights;
}


texts: How can I determine the input size of an algorithm?

texts:
Could you explain to me the input size of the algorithm with these cases? I can't understand the cases with multiple input parameters. Thanks.

algorithm_1( a[1,...,n], b[1,...,n] )
    for i ← 1 to legth[a] step 1 do
        for j ← 1 to legth[b] step 1 do
            x++
    return 0

-

algorithm_2( a[1,...,n], b[1,...,n] )
    return 1

-

algorithm_3( a[1,...,n], n )
    for i ← 0 to n step 1 do
        sum += a[i]
    return sum

-

algorithm_4( m, n )
    for i ← 0 to n step 1 do
        sum += m*2
    return sum


texts: Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?

texts:
$ L = \{ww^{R}  \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $  and $ |w|_{b} \not\equiv |w|_{c} \} $

I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My selected word : $ a ^ {m! + m} c ^ {m! + m} b ^ {m} b ^ {m} c ^ {m! + m} a ^ {m! + m} $ where the first $ b ^ {m} $ are the distinguished characters.

It seems to me that it isn't possible to pump this word in any way possible so it isn't contex-free langauge. Have I right?


texts: DFA for words with $a$s not a multiple of 3 and at least one $c$

texts:
Consider this language: $$L = \{w \in \{a,c\}^* \mid 3\nmid\#a(w)\land\#c(w)>0\}$$.

Here is an automaton for the first part of language, but I do not know how to devise and attach the second part of the condition $\#c(w) > 0$. Because $C$ can come in any state.


texts: Vector clock :why Singhal Kshemkalyani differential technique require FIFO for message passing?

texts:
Singhal–Kshemkalyani’s differential technique is based on the
  observation that between successive message sends to the same process,
  only a few entries of the vector clock at the sender process are
  likely to change. This is more likely when the number of processes is
  large because only a few of them will interact frequently by passing
  messages. In this technique, when a process  Pi sends a message to a
  process Pj , it piggybacks only those entries of its vector clock that
  differ since the last message sent to Pj.

I am understanding above but not the following statement

  this technique requires that the communication channels follow FIFO
  discipline for message delivery.
  link

Chapter 3 -Logical clock from above book and sub topic is Efficient implementations of vector clocks

Thanks lot.


texts: Why does the distribution of pseudorandom numbers change when operating like this?

texts:
We were introduced to the standard C rand() function, and how to use it.

At some point during the class we were asked how to roll a die. The simple answer was to create a random number, take its modulo 6, and add 1.

rand()%6 + 1

However, the right answer was building a function that returns a value in the range [0,1) and then operating with that function to get a random number between 1 and 6.

Since most people in my class haven't seen probability yet, we weren't told why this was the right answer, but the class's assistant told us that taking the modulo of the random number produces a normal distribution of the numbers, while the other function we built:

rand / ((double) RAND_MAX + 1)

produces a uniform distribution.

Could anyone explain why this happens? I'm not a CS student myself so my knowledge is very basic

Thanks in advance.


texts: Are the terms "Language Implementation", "Runtime" and "Virtual Machine" synonymous?

texts:
To describe the implementation of a dynamic programming language, I have seen the terms "Runtime" (e.g. Security transparency in the Python runtime), "Virtual Machine" (Python Virtual Machine (PVM), YARV (Yet another Ruby VM)) and "Interpreter" (Matz's Ruby Interpreter) used. JavaScript also uses the word "Engine".

IMO the word "Interpreter" strictly describes only part of a language implementation: that which steps through and executes bytecode. "Interpreter"  excludes other parts of the implementation, such as a garbage collector.

Are the other terms, "Runtime", "Virtual Machine" and "Engine" synonymous with the language implementation as a whole? Are these terms interchangeable?


texts: Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )

texts:
Let denote $\mathbf{x} = \{x_1,x_2,...,x_N  \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$
$$
f(\mathbf{x},n) = \sum_{\sigma_1,...,\sigma_n} \left(\prod_{i=1}^n x_{\sigma_i}\right)
$$
with $\sigma_1,...\sigma_n \in \{1,2,...,N \}$ and $\sigma_i \ne \sigma_j$ for $i\ne j$
(the definition of the $n$-th symmetric sum can also be found here)
Let define $g(\mathbf{x},a)$  be the sum of symmetric sum
$$
g(\mathbf{x},a)= \sum_{n=0}^N a^{\mathbb{mod}(n,2)} f(\mathbf{x},n)
$$
with $a \in \Bbb R$ and
$\mathbb{mod}(n,2) = \begin{cases}
1 \quad \text{ if } n \text{ odd} \\
0 \quad \text{ if } n \text{ even}
\end{cases}$
Example 1: N = 2:
$$
g(\mathbf{x},a)= 1 - a(x_1 +x_2) + (x_1 x_2)
$$
Example 2: N = 3:
$$
g(\mathbf{x},a)= 1 - a(x_1 +x_2+x_3) + (x_1 x_2+x_2 x_3+x_3 x_1) - a x_1 x_2 x_3
$$
The complexity of $g(\mathbf{x},a)$ is $\mathcal{O}(2^n)$ with a naive algorithm. Indeed, the sum $g(\mathbf{x},a)$ has exactly $2^N$ terms and we sum up the terms sequentially
$$
g(\mathbf{x},a)= \sum_{n=1}^N\left( a^{\mathbb{mod}(N,2)} \sum_{\sigma_1,...,\sigma_n} \left(\prod_{i=1}^n x_{\sigma_i}\right)\right)
$$
My question: does there exist a better algorithm for computing $g(\mathbf{x},a)$ which is less complex than $\mathcal{O}(2^N)$?
My attempt: There exists special cases where $a=\pm 1$ that can factorize the sum $g(\mathbf{x},a)$ as follows
$$
g(\mathbf{x},a)= \prod_{n=1}^N(x_i+a)
$$
and then the sum can be computed in $\mathcal{O}(N)$. I try to find a mathematical method like this for $a \ne \pm 1$ without success. In fact, all difficulties lie on the modulo function $\mathbb{mod}(n,2)$.


texts: Constructing a NFA from a regular expression

texts:
I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression.
I started by constructing the NFA that accepts $R=ab^*(\epsilon \cup c)$

Next I tried to continue the concatenation part by adding the following to the NFA as follows:

Is that correct? is there a quick approach to construct NFA from long regular expressions?


texts: Condition for infinitude of the language of a finite state automaton

texts:
There is a theorem which says that:

  Given a finite state automaton having $n$ states, if there exists a string $w$ whose length satisfies $n \leq |w| \leq 2n-1$ then the language accepted by the automaton is infinite.

I understand the constraint $|w| \geq n$, but I don't understand why the constraint $|w| \leq 2n-1$ is there.


texts: Reduction between $\Sigma^*$ and $\emptyset$

texts:
Throughout the subject of reductions, I was wondering:

  If we take $L_1 = \Sigma^* $ and $L_2 = \emptyset$, is $L_1 \leq L_2$? is $L_2 \leq L_1$?

What I mean is, Is there some sort of reduction between any of the two with the other one?

I tried this:

  Let us try $L_2 \leq L_1$, we need to show that such a reduction exists. Suppose f(x) is that reduction function in which $x \in L_2$ iff $f(x) \in L_1$.

But there aren't any $x$ in $\emptyset = L_2$, does that show that such a reduction doesn't exist?


texts: Algorithm to compute shape and volume of polyhedrons (polytope) formed by finite planes

texts:
Definition: In geometry, a polyhedron (plural polyhedra or polyhedrons) is solid in three dimensions with flat polygonal faces, straight edges, and sharp corners or vertices.

We have a closed domain with a certain number of faces (a cube,  pyramids). For example: Imagine we distribute n finite plane (for simplicity flat circular disc objects with a given location, diameter, and orientation) within a closed domain. These plates within region intersect each other as well as with boundaries of the domain. As a result of these intersections, some closed polyhedrons (Convex or Concave) may be formed.

The Objective is to find the shape and volume of polyhedrons formed by the intersection of these distributed finite plates.

I am not Computer Engineer nor mathematics. I have done a quick research and I found some keywords and topics (Spatial occupancy enumeration, Cell decomposition, Boundary representation among others.). I guess this problem should be well known and well studied in some fields. If you know an algorithm for that or any open source software that can be used for solving the above problem please let me know. I really appreciate any clues.


texts: Approximation algorithms for Euclidean Traveling Salesman

texts: I am trying to find a way to solve Euclidean TSP in a polynomial time. I looked at some papers but I couldn't decide which one is better. What is the general approximation algorithm for solving this problem in polynomial time?


texts: Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average?

texts:
Given an $n$-bit integer, I am interested in performing an increment operation using as few bit reads as possible. The standard binary code (standard binary representation of numbers), requires $n$ bit reads and writes in the worst case, though only $2 - 2^{1-n}$ bit reads on average (i.e $2$ bit reads on average asymptotically). On the other hand, there are codes like the Binary Reflected Gray Code that only require $1$ bit write in the worst case (since all integers in the sequence have hamming distance one). However, the BRGC requires $n$ bit reads in the worst and average case. In addition, there are other codes, such as the Recursive Partition Gray Code, which improve the average number of reads down to $O(\log n)$.

I would like the know if there is a code that can outperform the standard binary code with regards to the average number of reads. I have, however, no restrictions on the number of bit writes or the number of reads in the worst case. I feel like there should be a lower bound that says you cannot do better on average than $2 - 2^{1-n}$, but haven't been able to find a reference.

Edit: I know there is a lower bound of $\log n + 1$ reads in the worst case due to Fredman in 1978, but I am not aware of a lower bound for average case.


texts: Average codeword length in Huffman encoding at most log n

texts:
I am interested in the following question:

Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords.

I'm thinking of a worst case when the full binary tree (generated by Huffman's algorithm) has height $n-2$, but I still have to take the letter frequency into account, and I am stuck.
(Also I observed that the letter frequency shrinks by a factor of two when traversing down the tree.)


texts: Is TD-learning considered a model-based algorithm?

texts: Differently from Sarsa and Q-learning, pure temporal difference learning (TD-learning) works with state value functions $V(s)$ and not state-action Q value functions $Q(s,a)$. It means that, in order to select the best action at state $s$, the resulting state $s'$ for every possible action must be computed, so we can get $V(s')$. Thus, we need a model for computing $s'$ from a $(s,a)$ pair. Is that correct? Does that mean that TD-learning can be considered a model-based technique? Or in the case of TD-learning we consider it just a value updating algorithm and ignore the control part, thus removing the need for a model?


texts: Why update weights and biases after training a Neural Network on whole set of training samples

texts:
I am reading the book Neural Networks and Deep Learning by Micheal  Nielsen. In the second chapter of his book, he describes the following algorithm for updating weights and biases for a neural network:

In the 2nd step, the algorithm computes the error for a sample and backpropogates it through the layers. This happens for all of the training samples (please correct me if I am wrong because this is what I assume is going on). Then in the 3rd step, the weights and biases are updated. My question is, why does the algorithm wait until the third step to update the weights and biases. That is, why can't it do it after each training sample instead of after a whole set of training samples?
Thank you so much for your help and I appreciate it.


texts:
In my Operating Systems class I have an exercise to sketch out how a round-robin algorithm would apply to a specific scenario, which is the following:

Now the correction that I was provided with by the lecturer is the following:

But I do not understand how this is correct. After referring to the lecture that was given on this specific topic, I understood that Round-Robin maintains a queue with threads and each thread has a time quantum of tens of milliseconds of CPU time. When a thread has exhausted its time quantum CPU time it goes straight to the end of the queue. I also know that, threads that do not full use their time quantum CPU time, will be put in a separated queue, resulting in multilevel queue. After my understanding, this last part is ignored here. Here is the resolution of the exercise that I came up with:

The "-" stand for executing time, the "v^v^v" stands for blocking time, pretty much like in the correction picture.
Note that my version, and the version of the correction match up until the 1st pink dashed line.

Finally, the question is: How come that after the 1st pink dashed line, A is assigned to the CPU? (in the correction version), instead of B, which is, after my understanding, the next process in the queue to be executed(See "Ready queue") in my version of the exercise.

Please note that there are priorities, but according to the definition of round-robin fashion, priorities are not considered for it(I know that in most OSs the plain vanilla round-robin is not applied, but please ignore that); priorities are there for other parts of the exercise which have nothing to do with this issue.


texts: How to find splitting point in [0,1] to maximize sum of sign function?

texts:
Given two $n$-number arrays $a_1, a_2, \ldots,a_n \in [0,1] $ and $b_1, b_2, \ldots,b_n \in [0,1] $. We would like to find the real number $x^{*} \in (0,1)$ s.t:

$x^{*} =\arg\max_{x} \sum_{i=1}^n  \mathrm{sgn} \big( (a_i-x) (b_i -x)\big) $

Where $\mathrm{sgn} = 1 $ if $x \geq 0$ and
 $\mathrm{sgn} = -1$ if $x < 0$

This question raised from my research work. I am looking for an efficient way to determine value of $x$.


texts: Time complexity of languages recognized by linear bounded automata with restricted number of writes

texts:
Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. Must $L$ belong to $P$, the class of languages decidable in polynomial time? Even more stringently, does there exist a deterministic decider for $L$ that runs in $O(n)$ time, where $n$ is the size of the input? Of course, if we can answer the second question in the affirmative, then we can answer the first question as well.

One approach I'm considering to answering the first question is looking at the length-increasing grammar associated with $L$, and devising an algorithm that checks if this grammar is capable of generating its input in polynomial time.

I'm not sure how to approach the second question. Of course, the tape head for the constrained LBA is writing at worst $O(n)$ times for any input, but the computation on the input still may involve transitions that don't write to the tape.


texts: Processes running in Distributed Systems (Advanced Operating System)

texts:
I had a test today, there was a question that was a bit confusing. Anyway I am asking the question, from memory, and explaining what I answered. It would be great if someone could explain if I did answer it correctly or not.

The question is that assume a ring of 6 processes in an asynchronous system(each process runs the code as soon the as the conditions of its code becomes true). Each of these processes have a number x. The number's value is changed based on an algorithm as such:

Do if there exists a neighbor of process i
   whose value X value is less than process i's
   X value, then skip the loop
   For all process i's neighbors, if process i's
   X value is less than it's neighbors X value plus one (X+1)
   then process i's X = X + 1(increment one)

endDo

the system can be imagined to be like this:

So basically my answer was that the maximum difference can be 1. Because every process needs to check two neighbors and based on the first condition, it cannot increment if it is bigger than it's neighbors. Suppose they all start from one, and process 0 checks process 1's X value. Since its also zero, then the second condition will be true and it will increment and become 1. it will check process 5. Suppose by now process 5 has run the same program and become 1. Since value of process 5 is 1 process 1 will increment its value by one, and becomes 2. But after it becomes two, it will check process 1. if it was still one, then the first condition is true and it will not increment. if it wasn't then it will become 3. But if this becomes three then process 5, will run the code and become 2. So in no condition the difference will be more than 1. This scenario can be extended to all six values.

EDIT:

Now what I am not sure is if my assumptions are true. Since it's an asynchronous system, is it possible that on of the processes, and it's neighbors  will keep adding it's value of X while some other process remains zero? I doubt that, since based on the algorithm, it seems that the will at most add 2 value to its X, but not more than that.


texts: How does the bitlength of the divisor affect the running-time complexity of division algorithms?

texts:
Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is the complexity of the Newton-Raphson division.

My question is this: what are some of the best known (wrt. running-time complexity as a function of $n$) algorithms for division of two numbers, of m, and $n < m$ digits respectively? That is, how much complexity can be gained when the two numbers are not assumed to be of the same length?

I wouldn't want to treat $n$ as a constant as I'm in particularly interested in the case of $n \in O(\log{m})$. So I'm not looking for answers that treat $n$ as in $O(1)$.


texts: Maximum sum of depths of all external nodes in a Binary Tree

texts:
Let $T$ be a (possibly improper) binary tree with $n$ nodes, and let $E(T)$ be the
sum of the depths of all the external nodes of $T$.  (In a proper binary tree each node have 0 or 2 children.  An external node is a leaf, i.e., any node that is not an internal node.)

Is there a configuration for $T$ such that $E(T)$ is $\Omega(n^2)$?  Is there an infinite sequence of trees $T_1,T_2,T_3,\dots$ such that $T_n$ has $n$ nodes and $E(T_n) = \Omega(n^2)$?

I have found 2 extreme cases for $E(T)$:

each internal node has 1 child (then $E(T)$ is $O(n)$), or
each internal node has 2 children (then $E(T)$ is $O(n \log_2 (n))$).

I have tried shaping the tree like this:

but as you can see it grows asymptoticly similar to Arithmetic Series and $E(T)$ is $O(n)$. I even showed it algebraically.

Internal nodes are just arithmetic sum, and leafs are the last term of this sum times 2.

$x$ - level of a tree
$$\sum_{i=1}^{x}i=\frac{x(x+1)}{2}$$
$$\frac{x(x+1)}{2} + 2x = n$$
solving for x gives
$$x = \sqrt{2n+\frac{25}{4}} - \frac{5}{2}$$
$x$ is $\Omega (\sqrt{n})$.
Now lets try calculation $E(T)$:
There are $2x$ leafs each with depth $x$
$$E(T) = 2x \cdot x $$
$$E(T) \text{ is } \Omega (2\sqrt{n} \cdot \sqrt{n}) = \Omega(n) $$
So my question is how this tree should look like?


texts:
Define $Tape_M(t, i)$ as the symbol in the $i$-th cell of the tape of Turing machine $M$ with empty input at step $t$.

  Does there exist a Turing machine $M$ such that no algorithm can compute $Tape_M(t, i)$ within $o(t)$ (or $o(t/\log(t))$ ) time?

Actually, it is inspired by the celebrated time hierarchy theorem. I believe that it is true but I have trouble proving it. I think diagonalization may be a right direction (like what we do for time hierarchy theorem), but I am not certain how to diagonalize.


texts: How does a two-way pushdown automaton work?

texts:
Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape.

I recently had the question of determining the computational power of two-way PDAs in the Chomsky hierarchy. I don't entirely understand two-way PDAs, but I can see how with the ability to read in both directions on the input, it could handle languages of the form $L=\{0^n 1^n 2^n\}$. I can't say that for sure, but it seems that would make it powerful enough to least handle context-sensitive languages.

This is all a guess because I don't know exactly how they work. Can someone explain the process of how a two-way PDA operates, maybe even on my example?

UPDATE:

  The model is a generalization of a pushdown automaton in that two-way motion is allowed on the input tape which is assumed to have endmarkers.


texts: Steps to convert regular expressions directly to regular grammars and vice versa

texts:
I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars):

Then I came across many examples that claimed to use these rules to prepare regular grammars from given regex. However I was not able to understand how they are actually using these rules, as they directly gave final regular grammar for given regex. So I decided to try some examples step by step and find whats going on.

Below is one such examples which tries to step by step find RLG and LLG for regex $0^*(1(0+1))^*$. At each step, same color is used to match part of regex getting translated into corresponding part in grammar.

Preparing RLG

Notice that rule in first table says $e^*$ gets translated to RLG productions taking form $S\rightarrow eS | \epsilon$. However in example above, we can see that, to emulate * in regex, we have to put $\epsilon$ in step 2 (green color) as indicated by the rule, but also need to add bunch of other stuff in step 4 (blue color), which are not directly indicated by the rule (though somewhat intuitive extension of the rule).

Preparing  LLG

While preparing LLG also, we can see that, to emulate * in regex, we have to put $\epsilon$ (green colored) in step 1 as indicated by the rule, but also need to add bunch of other stuff in step 2 (green colored), which are not directly indicated by the rule (though again somewhat intuitive extension of the rule).

Apart from star closure, there are many stuff that I dont find straight forward or at least requiring extra awareness (that cannot be easily put in step-by-step procedure) while preparing grammar. For example, while preparing RLG, to emulate $0^*$, I can do $S\rightarrow 0S|\epsilon$ as indicated by first table. But in above example, I have to remain extra aware that there is something more $((1(0+1))^*)$ after $0^*$ which forces me to put $A$ in $S\rightarrow 0S | A | \epsilon$ production in step 2. Other facts I should be aware of:

While preparing RLG, I should start from left of the regex
While preparing LLG, I should start from right of the regex

I observed many more such small points which all I need to be aware at each step of preparing grammar. It makes me feel fuzzy.

Am I going correct with this at all? Is there any book which discuss regex to regular grammar direct conversion, giving clear step by step procedure? Or there is simply no such procedure and I am unnecessarily trying to make it up from examples?


texts: What does an input string of epsilon mean?

texts:
I am currently reading Introduction to the Theory of Computation (Sipser), and after introducing epsilon labeled transition arrows, the book shows the following NFA:

I was following it until I read the following :

Practice with it to satisfy yourself that it accepts the strings ϵ, a, baba and baa...

What does an input string of ϵ mean?


texts: Deriving lower and upper bounds for T(n) = T(n-1) + T(n-2) + 10

texts:
The solution is to find the upper and lower bounds from:

2T(n-2) < T(n) < 2T(n-1) + 10

So I have to find

T(n) > 2T(n-2)

and

T(n) < 2T(n-1) + 10

My question about this solution method is not how to solve those recurrence relations. It's about why this method can be used in the first place. I thought solving a recurrence relation is about finding the precise runtime and not about finding the approximate runtime between its lower and upper bounds. Is there a way to solve the recurrence relation without using this method and finding out the precise runtime?


texts: I have a dense matrix and a set of rows. I would like to check if adding any single row from the set to the original matrix would make the new matrix rank deficient. Right now I am doing a full LU decomposition each time. This feels wasteful, and I have a hunch that I should be able to keep some information between iterations. Does anyone know of a way to speed this up?


texts: Can algorithm discovery be brute forced?

texts:
Ultimately, when you compile them to machine code, algorithms are just 1's and 0's. So then - could you brute force the genesis, and thus the discovery of new, useful algorithms? Say, in pursuit of polynomial time algorithms for NP-complete problems.

Of course, rather than pure brute force, perhaps some intelligent force could be applied as a refinement.

My back-of-the-napkin-ish attempt to answer the question. Just an exercise; I don't really trust it.

In theory, yes - absolutely. The question is whether, in practice, it could be done in a reasonable amount of time in a cost-effective manner.
The amount of possible permutations of 1's and 0's is $2^n$ where n = the number of bits in your code.
Roughly how many bits does it take to write algorithms? To answer this question, I googled for a quick sort implementation in c, and compiled it to machine code. The result was about 10,000 bytes. So 80,000 bits. Let's say 100,000 bits for a round number.
There are $2^{100,000} = 10^{30,103}$ permutations of 1's and 0's.
You'd have to test each of these permutations. Let's say it takes 1 minute to test a permutation of 1's and 0's. Then that'd take $10^{30,097}$ years to finish testing. No good.
Perhaps the parameters could be tweaked. Let's try just 1,000 bits and 1 second to test each permutation. $2^{1000} = 10^{301}$ permutations. That'd take $10^{295}$ years.
Even if we used a lot of computing power, that'd still only cut the exponent down by 5 or 10, maybe. So ultimately, it seems impractical to actually brute force. The question then becomes whether we can combine intelligent force with brute force in algorithm generation.
Even though brute force seems impractical, I wonder if future generations will have insane computational power that we would never dream of. If so, brute forcing algorithm generation may be possible. Of course, they may have figured out all the algorithms by then.


texts: Is there a point to an all-encompassing programming language?

texts:
There are many programming languages in use throughout the world today, including languages that specialize in database manipulation, functionality, object-orientation, concurrency, etc. Would there be any point in making a language that could do all these things very well, or is it best to keep these languages separate to some degree?

The reason I ask is because I had been interested in building a very basic compiler. As I became more familiar with the concepts behind compilers and the hurdles and obstacles to overcome, I realized that I should probably come up with a language that had some sort of goal. I spoke with a friend about a language that could "do it all", and he said that there was simply no point. I am still confused as to why he might claim this.


texts: Is there a generic procedure to produce (hard enough) decision problems?

texts:
This comment by @DerekElkins suggests a general method of constructing decision problems for problems with bit-strings as output, of which a slightly formalised version is the following:

  Given a problem $X$, where we expect output for input $x$ to be $X(x)$, construct the following decision problem $B_X$: Given $(n,x)$ for some $n\in \mathbb{N}$, does the $n$-th bit of $X(x)$ exist and is it equal to $1$?

Clearly, this produces a decision problem for any problem $X$. However, the resulting 'bit-checking' problem may be easier than the original problem $X$. A simple case is when $X(x)$ is exponential in $x$: Suppose $X(m)$ is listing all permutations of $1,\ldots,m$ in lexicographical order. Then clearly $X$ can only be solved in $\Omega(m!)$, but detecting a single bit means we only have to check a single permutation, which can be found in polynomial time. So, in this case, the 'bit-checking' problem is easier than the original.

Therefore, I wondered if there is a general procedure that creates a decision problem that isn't 'easier', for any of the following definitions of 'isn't easier':

$X$ can be solved in $\Theta(f(x))$ if and only if $B_X$ can be solved in $\Theta(f(x))$
$X$ is in $P$ if and only if $B_X$ is in $P$

I'm ok with additional assumptions if those are convenient, such as assuming that the output $X(x)$ is polynomial in $x$ for case 1 or any other (general) subset of problems.


texts: Recurrence relations when function call is made inside loop

texts:
int fun (int n)
{
  int x=1, k;
  if (n==1) return x;
  for (k=1; k<n; ++k)
     x = x + fun(k) * fun(n – k);
  return x;
}

  What is the value of fun(5)?

I find it difficult to realize a recurrence tree when the functions are called inside loops so I decided to go with the recurrence relations.

This is what I came up with :

However, the recurrence relation given in the solution book is slightly different:

I don't understand where I went wrong. I included 1 inside the summation since x loops with every iteration. So why is the 1 in the second equation outside?


texts: What are exceptions and how they will be raised in pipeline

texts:
Hi I am not sure what is exception here and how it will be raised in following case

Sub $11,$2,$4
And $12,$2,$5
Or $13, $2,$6
Add $1,$2,$1
Slt $15,$6,$7

I was reading and encountered that

 add $1,$2,$1

will cause an exception. Could you guys please help in understanding what is exception here.


texts: is determinism = non determinism for one counter automata?

texts:
This language I think is not accepted by a deterministic one counter but accepted by a non-deterministic one counter :

$L = \{a^{i}b^{j}c^{k} \mid (i=j) \vee (j=k) \text{ such that } i\geq0, j\geq0, k\geq0\}$

But how to prove this claim?

Or is it the case that they are equivalent?


texts:
I have this code here which performs the 'leader election' among a specified number of processes. In Promela, it is written as:

  #define N 5       /* this is the number of processes */
  #define I 3   /* node that is given the smallest number    */
  #define L 10  /* size of the buffer, channel of channels  (>= 2*N) */

   mtype = { one, two, winner };
   chan q[N] = [L] of { mtype, byte};

   byte nr_leaders = 0;

  proctype node (chan in, out; byte mynumber)
  { bit Active = 1, know_winner = 0;
    byte nr, maximum = mynumber, neighbourR;

    xr in;  /* exclusive recv access to channel in */
    xs out; /* exclusive send access to channel out */

    printf("MSC: %d\n", mynumber);
    out!one(mynumber);
  end:  do
    :: in?one(nr) ->
        if
        :: Active ->
            if
            :: nr != maximum ->
                out!two(nr);
                neighbourR = nr
            :: else ->
                /* in case the number equals the max one */
                assert(nr == N);
                know_winner = 1;
                out!winner,nr;
            fi
        :: else ->
            out!one(nr)
        fi

    :: in?two(nr) ->
        if
        :: Active ->
            if
            :: neighbourR > nr && neighbourR > maximum ->
                maximum = neighbourR;
                out!one(neighbourR)
            :: else ->
                Active = 0
            fi
        :: else ->
            out!two(nr)
        fi
    :: in?winner,nr ->
        if
        :: nr != mynumber ->
            printf("MSC: LOST\n");
        :: else ->      /* declare the winner */
            printf("MSC: LEADER\n");
            nr_leaders++;
            assert(nr_leaders == 1)
        fi;
        if
        :: know_winner
        :: else -> out!winner,nr
        fi;
        break
    od
  }

  init {
    byte proc;
    atomic {
        proc = 1;
        do      /* iterate through the processes */
        :: proc <= N ->
            run node (q[proc-1], q[proc%N], (N+I-proc)%N+1);
            proc++
        :: proc > N ->
            break
        od
    }
  }

I'm interested in how I can edit this so I can verify that all processes terminate after I run the code through Spin and that all the processes agree about the one elected leader (that there's one leader).

On this link: http://spinroot.com/spin/Doc/SpinTutorial.pdf on page 31, there's a SPIN property liveliness which includes the verification of termination, so that's what I'm trying to implement now, besides the mutual agreement of the leader.

Thanks for the input!


texts: Minimum number of nodes to select such that every node is at most k nodes away

texts:
I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck.

Given a binary tree where each node in the tree can either be selected
or unselected, implement a function k_away() which returns the minimum
number of nodes that need to be selected so that every node in the
tree is at most k nodes away from a selected node.

The above image shows an example of k_away() selecting 2 nodes (denoted by the darkened circles) so that every node is now at most 3 away from a selected node.

So, the nodes simply contain a pointer to the left child, a pointer to the right child, and a boolean marking it as selected or not:
struct Node {
    Node *left;
    Node *right;
    bool selected = false; // starts out false
};

The problem specifies a constraint of having a time complexity of O(n) and an auxiliary space complexity of O(n).
What I've thought of so far:

It seems like there are 2^n potential solutions (if I can choose to either select or not select every node and there are 2 of them), so brute force is a bad idea
I've searched around for similar problems and the closest thing I can find is the Dominating Set problem which seems... impossible to solve at this moment in polynomial time. I doubt this problem was given as an impossible problem.
Running DFS to get to the leaf nodes, then counting height as recursion unrolls. Every k away, marking the node as selected. This seems to work on small test cases, but does not return the minimum number away.
Running BFS on the root node to find all nodes k away while using another data structure to mark all visited nodes as 'covered', and then recursively running the BFS on each k-away node. This also seems to work on small test cases, but again doesn't return the minimum number away.


texts: find the strong component containing the vertex v

texts:
I'm trying to solve this question for practising purposes:

"Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, describe a simple quadratic-time algorithm for computing the strong components of a digraph."

The question can be found here . It is question 31.
They give a couple of hints:

"Partial solution: To compute the strong component containing s

Find the set of vertices reachable from s
Find the set of vertices that can reach s
Take the intersection of the two sets

Using this as a subroutine, you can find all strong components in time proportional to t(E+V), where t is the number of strong components."

My thoughts so far:

In order to find the vertices reachable from s, I can to DFS (or BFS, but will stick with DFS) from s. If n is the number of vertices and m is the number of edges this takes O(n+m) time, which seem fine for the purpose. I need to safe every discovered vertex somewhere. Not sure which datastructure works best for this. I will come back to this problem later.
In order to find all vertices that can reach s, I could bild/compute the reverse of the graph and to another DFS from a again. Computing the reverse of the graph should be O(n+m) and the DFS is O(n+m). So in total I have 3*O(n+m) which is just O(n+m). Of course the discovered vertices also need to be safed.
I'm not sure about how to build the intersection. Of course this is going to depend on how I saved the nodes before. So here are my ideas:

Building the intersection:

If I saved the nodes in two separate arrays (one for the first DFS and one for the second) I possibly could use a Hash-Table. This should be O(|firstNodes| + |secondNodes|) time. Maybe this would be ok, since O(|firstNodes| + |secondNodes|) is smaller than O(n+m), but it doesn't seem optimal to me and it need extra space.
What if I mark the nodes I discoverd with the first DFS. Then I do the second DFS and check if nodes are already marked. If yes, I mark them "special" as belonging the the strong component? I wouldn't have a list afterward that gives me the vertices of the strong component s belongs to but the strong component is still computed? For this approach I would need extra space at every node (in order to mark it).
In order to find all strong compoonents in time proportional to t(E+V) I could then to the same procedure on a vertex that is not yet marked as belonging to a strong component -> as long as there are such vertices, therefore t times. I would need to make sure, that every strong component is marked differently (e.g. increaing integers) and that the "I fould you" marks from the DFS are gone after each iteration (but not the marks for the strong components).

What do you think? What have I missed?
Thank you and happy Easter!


texts: Memory Requirement for a Computable Problem

texts:
I was thinking whether it is true that every computational problem intrinsically has a minimum ammount of memory required for any algorithm that computes it.
But then i was confused to what "memory requirement" really means and how we could quantify it .
Looking for how Computational Complexity treats the memory requirement of a computational problem made me even more confused, because it always consider memory requirement under Turing Machines ... so it really doesnt treat the memory requirement as universal as it could ( applied to any possible model of computation : be it FSM, Lambda Calc, or whatever ).

Let me elaborate on my confusion.

It was intuitively thinking of characterizing the memory requirement of algorithms in terms of levels of memory.     For automatas,  binary addition of numbers too small so we don't need carriers would be a problem that would require no memory at all .
But addition with carriers and  1-momment delaying would be problems at least 1 level of memory.  Binary multiplication of arbitrarily large numbers, however, would require arbitrarily large levels of memory .    It's so wierd that Combinational Logic circuits can solve all those problems ( arithmetic with carriers ) if it doesn't have any memory at all ( no flip-flop ). How can we understand that ? Is a combinational logic circuit doing computations ? Can we see it as a weak model of computation ?

I had a hope that Space Complexity in the Computational Complexity discipline cold formalize this idea of "levels of memory, but it seems that since the framework is always Turing Machines, everything requires memory, even a simple addition without carriers ( in fact, it needs memory to simulate combinational logic circuits that are models of computation that don't require memory )  .

But there are many problems with this notion of "levels of memory".

1 - What does a level of memory really mean ?  Do we universally have only two ways of encoding those levels of memory :  either on the states of a machine , or on auxiliary memory read by a machine.

2 - In case the first question is true, would the correspondence for encoding levels of memory on the states of a machine be :   n levels of memory require at least 2^n states ?  At least, for Finite State Machines, it seems to be that way .
But what about the correspondence for encoding levels of memory on auxiliary memory ( tape-memory ) read by a machine ?

Anyways,  i'm really stuck with this doubt for some time and any clarification ( suggestion of a topic for me to read, or any resource at all  ,   explanations and any insight about that ) on how we can understand treat this memory requiment concept universally would be really helpful.

Thanks a lot in advance.


texts: If inorder traversal of a tree is in ascending order will the tree definitely be a BST?

texts: For a binary search tree (BST) the inorder traversal is always in ascending order. Is the converse also true?


texts: Optimal way to pack items with multidimensional weight such that the number of items is minimized?

texts:
I am given a set of items S = {a1,a2,a3,...,an}. Each item has a corresponding M dimensional bit vector indicating the properties of that item. For example, if item x has corresponding vector: {0, 1, 0}, then item x does not have property 1, does have property 2, and does not have property 3.
I am also given a M dimensional "goal" vector indicating the number of items I need that match each property. For example, if my goal vector is: {1, 3, 2}, then I need 1 item with property 1, 3 items with property 2, and 2 items with property 3.
My question is, how can I select a subset of items from the set S such that the constraints listed in the goal vector are met exactly and so that the number of items selected from S is minimized? What is the name of this problem, and what is an efficient algorithm for solving it? Also, what algorithm would I use for the opposite scenario where I would like to maximize (instead of minimize) the number of items used?
Could this be a variation on the knapsack problem or the bin packing problem?


texts: Regular language? Union of the dictionary and an non-regular language

texts:
I'm attempting to figure out if a union of two languages is regular.

$$
L_1 = \{all\ the\ words\ in\ the\ Oxford\ dictionary\} \\
L_2 = \{w : w\ has\ twice\ as\ many\ a's\ as\ b's\}
$$

$L_2$ is well established to be a non-regular language. However, I am not sure if $L_1$ would be considered a regular language. The language should be finite (albeit large), which suggests it is regular, but I'm not certain.

If $L_1$ is regular, then I would consider the union $L_1 \cup L_2 $ would also be regular, as by the same argument, the language would be finite.

What does everyone think?


texts:
I'm currently reading Nancy Lynch book about distributed systems, chapter about IO automaton. And I have following questions related to book exercise 8.13(c).

We are given some automaton A with sig(A) is empty. Traces(P) is the set of sequences  over {1,2}  in wich every occurance of 1 is immediatly followed by a 2. I need to show that P is neither a safety property nor a liveness property. and show explicitly that P could be expressed as intersections of S and L.

Here is my problem: I can show that P is not safety because it breaks prefix-closed property, e.g. {2,1,2} has no prefix belonging to P (it should be of the  form {...,1} which is impossible for P). But I don't know how to deal with L property -- either it is empty or include trace(P) -- trace(P) $\subset$ trace(L). If it is empty then traces(P) is empty because traces(P)= traces(S) $\cap$ traces(L) which is wrong. So I think that traces(P) is subset of traces(L).

Is my conclusion related to traces(L) is right?

How can I explicitly express traces(P)=traces(S) $\cap$ traces(L) for this problem?

Thanks in advance.


texts: Calibrating a Markov Chain with little data

texts:
I am trying to calibrate a Markov Chain. Usually you would have the amount that "moves" from one state to the other and then the resulting value, with data at any given time with the following arrangement:

$$
\begin{matrix}
F_{a,a} &  F_{a,b}  & F_{a,c}\\
F_{b,a} &  F_{b,b}  & F_{b,c}\\
F_{c,a} &  F_{c,b}  & F_{c,c}\\
\end{matrix}
$$

The problem is that I have data in this arrangement for the complete set:

$F_i = F_{i,a}+F_{i,b}+F_{i,c}$ for $i = a,b,c $

I was wondering if there was any way I could obtain the $F$ parameters for all the combinations of $a,b$ and $c$; some sort of proxy of them; or even a way of getting the resulting parameters of the calibrated model with this data.


texts: How to do amortized analysis for an expanding array?

texts:
If you have an array that expands when it is completely filled and the new size is
N = N + 1 + ceiling(log2(N)) (N is the current size, and then N becomes the new size)
(log2 is log base 2).

How can you do an amortized analysis for this? It is confusing because the size of the expansion of the array increases as N increases.


texts: CFG - Left factoring in recursive nested productions

texts:
I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with the follow exception. I've provided the simplest case to illustrate the problem below.

S -> a b S | T
T  -> a c T | d T | ϵ

This grammar rightly generate a FIRST(S) - FIRST(T) clash, as both S and T can generate a as a first terminal.

One (clearly wrong) attempt to left-factor the a terminal was to substitute T into the S production.

S -> a b S | a c S | d S | ϵ

This would allow for left factoring like so:

S -> a U | d S | ϵ
U -> b S | c S

However, this grammar is no longer equivalent, as it would accept the string acab when the original grammar would not.

I'm hoping that there is some way to manipulate this grammar that I'm not aware of to eliminate the FIRST(S) and FIRST(T) clash. Is there a method to left-factor a terminal in recursive nested productions as is described above?


texts: How does the problem of having a coffee-machine close relate to vertex cover?

texts:
Meeting rooms on university campuses may or may not contain coffee machines. We would
  like to ensure that every meeting room either has a coffee machine or is close enough to a
  meeting room that does have a coffee machine. (For any two meeting rooms, the architect
  has told us whether or not they are close enough.) Our problem is to determine among all the
  meeting rooms of any university campus, which ones should have coffee machines so that we
  use as few coffee machines as possible. Specify this problem as an optimization problem on a
  graph. Formulate the corresponding Coffee-machine Decision Problem (abbreviated Coffee).
  Prove that the Coffee Machine Decision Problem is NP-complete.

  Hint: You could use Vertex Cover. For every edge, add two more edges and one more vertex.

I'm confused at the hint given and why this problem isn't just a straight reduction from Vertex Cover.  What's the point of adding two more edges and a vertex for every edge?


texts: $\omega$-automata where string is accepted iff a final state is accessible from starting state

texts:
I am wondering if $\omega$-automata with the following acceptance condition are valid.
An input string is accepted iff one of the final states occurs at least once.
This differs from Buchi automata in that the final state only has to occur once, not infinitely often.
Does this kind of automata have a name? Is it interesting or important?


texts: Prove the probability of which a hash function is collision-free

texts:
Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct points in $\{0, 1\}^n$. If we choose $h$ randomly form $H$ and let $E$ be the event that $h(x_1), ..., h(x_M)$ are all distinct. We need to show that $Pr[E] \ge \frac{3}{4}$.

$\textbf{Markove's inequality:}$ If $X$ is a random variable which only takes non-negative values then, for any $t \ge 0$, $Pr[X \ge t] \leq E[X]/t$.

The idea is to compute $Pr[h(x_i) = h(x_j)]$, compute the expectation of the random variable $Z = |\{(i,j) : h(x_i) = h(x_j)\}|$ and use the Markove's inequality to prove the question.

For two independent points $x_i$ and $x_j$, the probability that $h(x_i)$ and $h(x_j)$ are equal is $1 - \{\text{the probability two independent points has the different hash values}\}$, which is $1 - \frac{2^{n/2}}{2^{n/2}}\cdot \frac{2^{n/2} - 1}{2^{n/2}}$. That shows $Pr[h(x_i) = h(x_j)] = \frac{1}{2^{n/2}}$.

As for the random variable $Z$, maybe we can let $Z_{i,j} = 1 \text{ if }h(x_i) = h(x_j)$. Otherwise, $Z_{i,j} = 0$. Then we can get $Pr(Z_{(i,j)}) = \frac{1}{2^{n/2}}$. This is where I stuck. I know how to compute the expectation the single random variable, which is $\sum_{i=1}^{n} x_i P(X = x_i)$. But I have no idea how to expand this formula to the pair random variable $(i,j)$. Also I am a little confused how Markove's Inequality could be used in this proof.

Could someone give me some hints? Any help would be appreciated. Thanks in advance.


texts: trouble recovering rotation and translation from essential matrix

texts:
I am having trouble recovering rotation and translation from an essential matrix. I am constructing this matrix using the following equation:
\begin{equation}
E = R \left[t\right]_x
\end{equation}
which is the equation listed on Wikipedia. With my calculated Essential matrix I am able to show the following relation holds:
\begin{equation}
\left( \hat x \right) E x = 0
\end{equation}
for the forty or so points I am randomly generating and projecting into coordinate frames. I decompose $E$ using SVD then compute the 2 possible translations and the two possible rotations. These solutions differ significantly from the components I'm starting with.
I have pasted a simplified version of the problem I am struggling with below. Is there anything wrong with how I am recovering the these components?
import numpy as np

t = np.array([-0.08519122, -0.34015967, -0.93650086])

R = np.array([[ 0.5499506 , 0.28125727, -0.78641508],
    [-0.6855271 , 0.68986729, -0.23267083],
    [ 0.47708168, 0.66706632, 0.57220241]])

def cross(t):
    return np.array([
    [0, -t[2], t[1]],
    [t[2], 0, -t[0]],
    [-t[1], t[0], 0]])

E = R.dot(cross(t))

u, _, vh = np.linalg.svd(E, full_matrices=True)

W = np.array([
[ 0,-1, 0],
[ 1, 0, 0],
[ 0, 0, 1]])

Rs = [u.dot(W.dot(vh.T)), u.dot(W.T.dot(vh.T))]
Ts = [u[:,2], -u[:,2]]


texts: Are degree and order the same thing when referring to a B-Tree

texts:
I know the term order of a B-tree. Recently I heard a new term: B tree with minimum degree of 2.

We know that the degree is related to a node but what is the degree of a tree?
Does degree impose any kind of a restriction on height of a B-tree?


texts:
In Concrete Mathematics
Textbook by Donald Knuth and Oren Patashnik ,
ch.2 Sum ,sec2.2
He wrote:

  The average number of  comparison steps made  by quicksort when it's applied to $n$ items in random order satisfies the recurrence :
  $$C_0=0;$$
  $$C_n = n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k$$

The question is how he get the relation :

$$C_n = n + 1 + \frac{2}{n}\sum_{k=0}^{n-1}C_k$$?


texts: Why do negative array indices make sense?

texts:
I have came across a weird experience in C programming. Consider this code:

int main(){
  int array1[6] = {0, 1, 2, 3, 4, 5};
  int array2[6] = {6, 7, 8, 9, 10, 11};

  printf("%d\n", array1[-1]);
  return 0;
}

When I compile and run this, I don't get any errors or warnings. As my lecturer said, the array index -1 accesses another variable. I'm still confused, why on earth does a programming language have this capability? I mean, why allow negative array indices?


texts: How does an NFA use epsilon transitions?

texts:
In the picture below, I'm trying to figure out what exactly this NFA is accepting.

What's confusing me is the $\epsilon$ jump at $q_0$.

If a $0$ is entered, does the system move to both $q_0$ and $q_1$ (the accept state)?
If a $1$ is entered, does the system move to both $q_1$ and $q_2$?
Does the system only move to $q_1$ (accept state), if no input is given (empty string)?


texts: How do I search for Verification of Quantum Computing

texts:
So, in quantum computing, each qbit has a 50/50 chance of being in either the state of 1 or 0 when you measure it. Simple enough.

But I've heard reports a while ago about some company having successfully added two relatively small numbers and gotten out the right answer the majority of the time. The question I am trying to solve is: How? How would you verify a quantum result (without assuming you have the answer already available that you can compare it to)?

That, however, is not what I'm asking of this Stack Exchange. Instead, I am wanting to know what search terms in Google I can use to find this answer. "how to verify quantum computing results" doesn't turn up anything more than 1 academic paper (which I am actually reasonably confident has the answer I'm looking for). At least with the search, I get nothing more that is relevant to what I'm actually looking for.

Thus why I come here in hopes that someone might actually know what I would need to search to get more relevant results.


texts: Poly-time reduction from directed Hamiltonian Path to undirected HP, both with with known start and end

texts:
this is homework, so PLEASE do not give me the solution(!), but help me get there on my own.

I've got to proof that directed Hamilton Path with fixed stard and ending and undirected Hamilton Path with fixed start and ending are poly-time-equivalent.

I can do that for directed to undirected no problem by adding one reverse edge for every edge there is. That takes O(|E|) time, which is polynomial.

Now, I've got to show that there is a polynomial reduction from UNDIRECTED to DIRECTED Hamilton pahts, meaning that
iff(!) I know that an undirected graph has a Hamiltonian Path from x to y, can I tweak it in polynomial time so that it is a directed graph with an Hamiltonian path from x to y?

I've tried doing it incrementally, starting with x then
saving one alternate representation of the graph for every outgoing edge and deleting all edges that have been used.
This is going to take non-detetministic space, so it is goind to take non-deterministic time, which indicates that that idea is crap.

I've tried just modifying the path itself and then noticed that that is not going to work, since getting the path is NP-hard.

Can anyone give me a hint?


texts: Minimal set of inequalities including good points but excluding bad points

texts:
Suppose I have a collection of good convex sets and bad convex sets in $\mathbb{R}^d$ (where $d$ can be big). Each convex set is defined by a series of closed ranges in each dimension $d$ - a hyperrectangle if you will. For 2D an example set could be $\{(x, y) : x \in [1, 5]\wedge  y \in [-2, 3]\}$. All sets are sparse, that is, for the majority of the dimensions the convex set in that dimension just covers range $[0, 0]$, each set only has a non-zero width in a couple dimensions. This means each hyperrectangle could be efficiently described by listing its vertices despite the high dimensionality.

If the convex hull of the good sets is disjoint from all bad convex sets, there exists a set of hyperplanes (AKA inequalities) that together separate the good from the bad sets. The convex hull immediately gives you such a set of hyperplanes, but it's not minimal - it uses more hyperplanes than necessary.

Can we efficiently compute a minimal set of hyperplanes that separates the good from the bad sets? If one hyperplane suffices we can find it using linear programming, but I don't know how to compute it if more than one hyperplane is needed.

If the answer is no, can we get at least an efficient heuristic/greedy algorithm?


texts: Is there an algorithm for a number line from $0$ to $n$

texts:
Where $n + 1 = 0$
and $0 - 1 = n$?

The $n + 1 = 0$ case can be achieved by using the modulus operator, but I can't figure out how to treat the $0 - 1 = n$ case.


texts: Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language

texts: Let's assume that we're working over a finite alphabet $\Sigma=\{a, b\}$. How can one prove that $$L_2=\{w_1w_2...w_m| m ∈ \mathbb{N}, ∀i(w_i ∈ L)\}$$ is a regular language, provided that L is regular? By the way, L is a fixed language in the problem that I am solving, but it's regularity is trivial to prove so I have omitted it. This next step, however, I can't think of a valid way to prove. I would be glad if you guys could give me a hint.


texts: Recognizer for decidable language and words it doesn't halt on

texts:
Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only recognizes B but does not decide it - there are words not in B that M doesn't halt on (for words not in B M might either reject or not halt).

Let A = {w | M does not halt on the word w}.

Which of the following has to be true:

1) A must be decidable

2) A might not be decidable but it has to be recognizable

3)  A might not be recognizable but its complement has to be recognizable.

4) It might be that A and its complement are both not recognizable.

I was asked this question and i think that the answer is 3.

What i don't understand is why give the extra information about some decidable language B that M recognizes if the complement of A will always be recognizable regardless of whether it recognizes some decidable language B -> for any TM, the set of all the words it does halt on will always be recognizable. The recognizer for A complement will be - run M on w and accept if it halts).

What am i missing ? Is the info about B redundant ?


texts: These sample CNF formulas in DIMACS files are in P? (Schaefer's dichotomy theorem)

texts:
Here is my earlier question. But there was no full answer.

I've decided to include specific DIMACS files:

http://jarvis2.hmcloud.pl/sat/cnf.formula.10 (15.8MB)

http://jarvis2.hmcloud.pl/sat/cnf.formula.15 (53.5MB)

http://jarvis2.hmcloud.pl/sat/cnf.formula.20 (134.6MB)

Are these CNF formulas fulfilling a condition of Schaefer's theorem dichotomy?

If so, what kind?

Schaefer's theorem dichotomy conditions:

all relations which are not constantly false are true when all its arguments are true;

all relations which are not constantly false are true when all its arguments are false;

all relations are equivalent to a conjunction of binary clauses;

all relations are equivalent to a conjunction of Horn clauses;

all relations are equivalent to a conjunction of dual-Horn clauses;

all relations are equivalent to a conjunction of affine formulae.


texts:
Given a regular Expression: 0^a 1^b 0^c, where a+b=c and a,b,c >= 0.
Find the cfg for this expression.
Here is what I tried to do:

s -> AsB

A -> 01

B -> 0

But then a language could be 010100 which does is not apart of the expression.
I tried other ways but then I was not able to fulfill the a+b=c rule.

e = epsilon

Using the Hint Below:

S -> 0S0 | A

A -> 1A0 | e


texts: Is there any field that studies the equivalent of cellular automata, but for arbitrary graphs rather than 1D cells?

texts:
A cellular automaton consists of a sequence of cells, each with a state, and a globally symmetric transition rule based on the neighbors of a cell. They can be interpreted as graphs where each cell is a node, and each node has an edge to a neighbor.

Is there any field studying that system, but generalized to arbitrary graphs - i.e., allowing cells to have, for example, 3 or more neighbors?


texts: Proving following regular expressions equal to one another?

texts:
How would I go about proving the following two regular expressions are equal to one another:

( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)*

I can "see" why they are equal to one another because the second ( a + b )* is a redundant term as the expression will always have an ab together. But how can I formalize this and show, in general, that this is true ?


texts: Algebraic Dynamic Programming breakdown of a simple problem (e.g. climbing staircase)

texts:
I found recently about Algebraic Dynamic Programming. As I understand, it's a formalization that immensely simplifies developing solutions for DP problems.

I spent a few days trying to grok it, to no avail. Perhaps in part it's because papers on ADP seem to require strong background in Formal Language theory, which I don't have. But lack of resources on ADP doesn't help either.

I'd really appreciate if someone acknowledgeable could show a step-by-step solution that applies ADP to a simple DP problem. Incidentally, the paper¹ has included multiple examples, but they left me with more questions than answers. It is because the paper overwhelms with a bunch of complex definitions, some of which (such as definition of ~~~ and ... functions) are even defined much later after their actual use. It also doesn't help that examples chosen are not the simplest. So when I look for example at "El Mamun's problem" solution, I see disconnected code pieces with a bunch of missing parts, which author magically calls a solution. Maybe it could've helped had author posted a full compilable solution, but that didn't happen.

So let's say, "climbing staircase" is a straightforward problem, which allows to concentrate on ADP rather than the problem. It sounds like:

  You are climbing a staircase that has n steps. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Can someone show an ADP breakdown of it? Or really, I don't mind if you're going to prefer some other simple problem to demonstrate an ADP approach.

For the record: a "DP" solution to it in Haskell:

solve1StepOrMore :: [Int] -> Int -> Int
solve1StepOrMore prevSteps lenLadder
      | lenLadder == 0 = step2
      | otherwise      = solve1StepOrMore [step2, step1 + step2] (lenLadder - 1)
      where
        step1 = prevSteps !! 0
        step2 = prevSteps !! 1

solve lenLadder
      | lenLadder == 0 = 0
      | otherwise      = solve1StepOrMore [0,1] lenLadder

main = do
  print $ (show $ solve 0) ++ ", expected 0"
  print $ (show $ solve 1) ++ ", expected 1"
  print $ (show $ solve 2) ++ ", expected 2"
  print $ (show $ solve 3) ++ ", expected 3"
  print $ (show $ solve 4) ++ ", expected 5"

A Discipline of Dynamic Programming over Sequence Data, link
Implementing Algebraic Dynamic Programming in the Functional and the Imperative Programming Paradigm, link


texts: Convert NURBS curve into Cubic Bezier Curve

texts:
From this:

  Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials.

I don't understand what it means, and don't yet know if it really means that there is absolutely no way to convert a NURBS curve into a cubic bezier curve (or spline, since I think bezier splines are multiple bezier curves connected together). I get confused because I also read this:

  No matter it is Uniform or Non-uniform, NURBS is just made by one or a bunch of Bezier curve; and if you bear with me, what you need to know about NURBS math is just the Bezier-series-equations.

Even just saw this:

  NURBS curve can always be converted to piecewise Bézier by repeated knot-insertion.

So some say it's possible, others not.

If it is true that you can't model NURBS with Bezier curves, then I would like to know why rational functions and polynomials can't be morphed into one another, at least at a high level (what is preventing the transformation between the two). In that case I would also like to know if there is a way to approximate a NURBS curve with Bezier curves, even though you lose some precision or the curve changes slightly. I would then just like to know how much you lose when approximating a NURBS curve with a Bezier curve, and what the algorithm or technique is called so I can further explore how to do it. If there is a standard algorithm for accomplishing this, that would be cool to know instead too.


texts:
I have been given a task to dynamically learn the optimum value of a parameter in a Heuristics Filtering Algorithm used in a tool.

The accuracy of the tool increase as the value of K in the heuristics filtering algorithm increases. How ever a lower K leads the tool towards a low resource consumption (memory, time and temporary storage).

How can I dynamically learning the optimum value of K using Machine Learning techniques so that the tool can dynamically generate an optimal value of K.

I have been looking into Reinforcement Learning and learning from online resources. First, the problem has to be modeled as a Markov Decision Process (s, a, r, s'). I got stuck at what my State Space s should be. My set of actions a (they represent the value that k should be) are {10,20,30...,100}. Is Reinforcement Learning the way to go in the first place? If not, what other machine learning techniques do you suggest? I'm not into AI but I enjoy solving problems


texts: I want to generate a random partition of an $N\times N$ grid into $N$ connected groups having $N$ tiles each. How would I do this?  Max grid size will be 10x10. Below is an example for a 5x5 grid.


texts: Proving a dynamic programming recurrence for coin exchange correct

texts:
Suppose I have $n$ kinds of coins $c_1, c_2, \dots, c_n$. I'm given: $S$, an amount of money I should construct with minimum number of coins.

I came into the following formula:

$$
T(n,S) =
\begin{cases} T(n-1,S) & \text{if $c_n > S$}, \\
\min(1+T(n,S-c_n), 1+T(n-1,S-c_n), T(n-1, S)) & \text{otherwise}.
\end{cases}
$$

The formula feels right to me, however when I try to prove it formally I hit the wall.

Is the formula indeed correct?
Can someone guide me how to prove it?


texts: Newton method using automatic differentiation

texts:
I wrote a large Matlab code which solves partial differential equations. Now I would like to test the code on nonlinear problems, for which I need the Newton-Raphson iteration for systems of nonlinear algebraic equations.
How do I employ automatic differentiation in Matlab to use the Newton-Raphson iteration?


texts: When estimating camera motion from the fundamental matrix, why can translation only be recovered up to scale using epipolar geometry?

texts: I was wondering once you have recovered the fundamental matrix F such that xFx' = 0. If you try to recover translation and rotation from F, I am told that this is possible only up to scale? Why so?


texts:
In the seminal distributed systems paper The Part Time Parliament (the Paxos protocol), Leslie Lamport names fictional legislators who are involved in the Paxon parliament protocol.

According to this writing, he notes that:

  I gave the Greek legislators the names of computer scientists working in the field, transliterated with Guibas's help into a bogus Greek dialect.

Does anyone have any information on the scientists that the legislators are named after? A list of the legislators in the paper and the corresponding computer scientists would be the ideal answer.

I think the first legislator mentioned in the paper, "Λινχ∂", is named after Nancy Lynch since it could be pronounced as "Linch". Also, "Λεωνίδας Γκίμπας" from the bibliography is Leo Guibas. I'm completely lost as to who the others are.


texts: Sorting geometric array in linear time without finding majority element

texts:
It's an exercise I was given:
We say array of numbers $A$ is geometric if:
 It has size $n=2^k-1$
 It has $\log n$ distinct numbers
 For each $0\leq i \leq k-1$ there exists an element in the array that appears exactly $2^i$ times.
 For example: $[8,5,2,5,5,5,8], k=3$
I need to sort the array in $\mathcal{O}(n)$ time and space.
I can solve it by using any algorithm that finds majority element in linear time.
My question is, can we solve it without finding using algorithm that finds majority element?


texts: Worst Case Scenario for Quicksort algorithm with pivot element n/2

texts:
What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element?
I know that if I choose the left or rightmost element as pivot ,the worst case occurs if:

Array is already sorted in same order
Array is already sorted in reverse order
All elements are same

and that the complexity in that cases is $\mathcal{O}({n^2})$.
However, this cases should not be a problem if I take the middle index of the partition as my pivot element.


texts: Powerset construction of minimal NFA will result into minimal DFA?

texts:
I was just thinking about the powerset construction and it is clear to me that the powerset construction will result into a DFA $D$ with possibly redundant states, as the NFA $N$ is not minimized. But in case where $N$ is minimal will $D$ will also be minimal?

So is there a DFA $D'$ with less states for the same Language $L$, assuming that only accessible states are added to $D$? I think it cannot be, since a redundant state in $D$ would result into a redundant edge in $N$ and this would contradict the assumption, but I am not sure.

Thanks.


texts: Algorithm to organize a tournament where the team componentes change each round

texts:
So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of the players. The trick is every team should change in each round so that not only everyone played against everyone but the teams are not repeated.

I've tried implementing it using greedy search with backtracking, but it just takes too long to find a valid solution, so what I'm asking for is sugerences of an algorithm more efficient that I can use to solve this problem. This are the especifics of the problem:

There is a multiple of 4 number 'n' of players.
There is at least n/4 fields to play, so that in each round all players have a match.
No player can play twice with the same partner, so in each round the teams must change.
No player can play twice against the same opponent. At the end of the tournament, each player must have played against the rest.

The algorithm must search the ideal combination of matchs so it meets the requeriments above.

Any ideas? Thank you in advance.

EDIT 2: It's not possible for 4 players.

ROUND 1

Player 1 & Player 2 vs Player 3 & Player 4

So far so good.

ROUND 2

Player 1 & Player 3 vs Player 2 & Player 4

Player 1 already played against Player 4, not a valid solution. The other possibility:

ROUND 2'

Player 1 & Player 4 vs Player 2 & Player 3

Player 1 already played against Player 3, not a valid solution either.

EDIT: It is double tennis, sorry for the misunderstanding.
Each player must have played against the rest, but it's not mandatory that each player ended up playing with the rest.
Question edited for clarity.


texts: An online algorithm to find the Pareto frontier elements

texts:
I'm looking for an online algorithm that takes a stream of elements and preserves the elements that are on the Pareto frontier (e.g. all non-dominated elements).

For instance. Given the following inputs, the retained Pareto frontier set would evolved as follows:

(3,7)

insert element b/c it's the first element
pareto set now includes {(3,7)}

(7,3)

insert element b/c it's not dominated in the first
pareto set now includes {(3,7), (7,3)}

(8,4)

insert element b/c it's not dominated; remove (7,3) which it is dominated in both dimensions
pareto set now includes {(3,7), (8,4)}

(1,1)

do not insert because it's dominate in both dimensions
pareto set now includes {(3,7), (8,4)}

(9,9)

insert element b/c it's not dominated; remove all other elements because this dominates them in both dimensions
pareto set now includes {(9,9)}

In my example I'm using 2-tuples, but I'm looking for an algorithm that could handle N-tuples for "small" N (say <10).

The naive solution is to just to compare each element with all elements currently in the set. In practice the naive approach might not be so bad (e.g. sub $O(n^2)$) because elements will regularly be expelled by the comparison set. But I was wondering if there was a known efficient algorithm for this. I'm interested in efficiency in memory and in computational complexity. (Ha! And as a matter of fact, I'm looking for the set of algorithms that are Pareto optimal with respect to memory and computational complexity.)

My current application of this is in building a Lucene search-document Collector that doesn't collect the most relevant documents (the typical use case for a search engine), but collects the Pareto optimal documents along specified dimensions.


texts: Do the following concepts belong to syntax or semantics?

texts:
I am not very sure about the difference between syntax and semantics.

Does each of the following concepts belong to syntax or semantics?

terms
values:   terms that are possible ﬁnal results of evaluation.
types
(typing) context
evaluation (rules)
typing (relation)?

Here are two examples from Types and Programming Languages by Pierce.

For example, I thought evaluation (rules) belongs to operational semantics, so values should also belong to operational semantics, by the definition of values. Why does the book list "values" under "Syntax"?


texts: Can we show a language is not computably enumerable by showing there is no verifier for it?

texts:
One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following:

  $A \subseteq \Sigma^*$ is c.e. iff there is a decidable language $V\subseteq \Sigma^*$ (called verifier) s.t.
  for all $x\in \Sigma^*$,

  $x\in A$ iff there exists a $y\in\Sigma^*$ s.t. $\langle x, y \rangle \in V$.

So one way to show that a language is not c.e. is to show that there is no decidable verifier $V$ for it. Is this method useful to show that languages are not c.e. in practice?


texts: Count substrings with same first and last characters

texts:
We are given a string S, we need to find count of all contiguous substrings starting and ending with same character.

Examples :

Input  : S = "abcab"
Output : 7
There are 15 substrings of "abcab"
a, ab, abc, abca, abcab, b, bc, bca
bcab, c, ca, cab, a, ab, b
Out of the above substrings, there
are 7 substrings : a, abca, b, bcab,
c, a and b.

Input  : S = "aba"
Output : 4
The substrings are a, b, a and aba

a) One approach would be to use brute force, (O(n^2)) approach where check for each substring and increment count
Please suggest optimal solutions


texts: I have read in my subject "Operating Systems" that CPU can't access secondary memory. Any program that is stored on secondary memory is executed once its retrieved from secondary memory to primary memory. Is this true?  If the CPU can't execute code directly out of secondary memory, why not?


texts: Practical communication example for a data rate scenario

texts:
Having difficulty with the following question.
I can answer parts I and II but having trouble finding a practical example.
Question:

Compute the maximum data rate of the following communication links;
I) 4000Hz bandwidth and a signal to noise ratio(SNR) of 20dB;
II) noiseless channel of 2.4GHz bandwidth with 64 signalling levels;
Provide a practical communication example for each scenario.

Any help would be greatly appreciated.


texts: Is a bitstring easier to compress if it has lower Kolmogorov complexity?

texts:
I have two bitstrings that are 100 bits long.  Bitstring A has a Kolmogorov complexity (KC) of 90 and bitstring B has a KC of 10.  Intuitively, I think bitstring B is probably easier to compress than bitstring A.

"Easier to compress" means a larger proportion of 100 bit bitstrings with B's KC can be compressed by a standard compression algorithm, than bitstrings with A's KC.

What I mean is that B probably has much more regularity that can be exploited by a compression algorithm such as Lempel-Ziv, whereas A is probably much more random and irregular.

Is this intuition correct?  If so, how is this relation quantified?  Can I say B is 9 times as likely to be compressible than A?


texts:
So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has:

$$ \begin{align}
S  &\rightarrow 0BS2 \mid 012 \\
B0 &\rightarrow 0B \\
B1 &\rightarrow 11 \\
\end{align} $$

I agree that the above works, but what is wrong with just saying:
$S\rightarrow 0S12 |\epsilon$

The above also generators the same number of $0$s as $1$s and $2$s.


texts:
I have a full bipartite graph with node sets $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. Each node has a weight, $v_i$ for $a_i$ and $w_i$ for $b_i$. Each node $a_i$ is connected to exactly one node of $B$, say $b_j$, via an edge $e_i$, whose weight is $\min(v_i,w_j)$. Now I want to find a one-to-one mapping from $A$ to $B$, whose sum of edge weights is as small as possible.
My idea is to sort $v_i$s increasingly and $w_i$s decreasingly and then find the sum of all $\min(v_i,w_i)$ after sorting. Is it correct? Can you give a proof/disproof?
I have run computer simulations for $n=5,6,\ldots,10$ with random vertex weights and found no counterexample.


texts: small size and small depth circuit for set intersections

texts:
Input: Given sets $S_i \subseteq \{1,2,3,4,\cdots,n\}$ for $1 \leq i \leq n$.

Output: sets intersection with restriction (pick first set $S_1$. If $a \in S_1$ such that $a$ is the least element then do $S_1\cap S_a$. Next go to least element (say $b$) in $S_1\cap S_a$ and do $S_1\cap S_a \cap S_b$)

Finally I want to find the $S_1\cap S_{i_1}\cap S_{i_2}\cdots \cap S_{i_{k-1}}$ where $i_1$ least element in  $S_1$ and $i_2$ least element in  $S_1\cap S_{i_1}$, $i_3$ least element in  $S_1\cap S_{i_1} \cap S_{i_2}$, $\cdots$,
$i_{k-1}$ least element in $S_1\cap S_{i_1}\cap S_{i_2}\cdots \cap S_{i_{k-2}}$.

Can we build circuit for this above problem?

What happens if $k$ is fixed?
what happens if $k$ is $\log n$?

Can we have logspace algorithm for this problem?

I am familiar with circuits and logics and please help out.

I tried as follows:

first construct a matrix $A$ with $n \times n$ with entries zero's and one's.
Find the entry $(i,j)$ is one if $S_i$ have element $j$. other wise zero.

Now we need to find the first non zero entry (say a) in $S_1$ row in $A$ and do or gate $S_1$ row with $S_a$ row in $A$.
Again find the first non zero entry (say b) in $S_1 \vee S_a$ row and
do $S_1\vee S_a \vee S_b$.

Now this process I can not able to find the depth and size of circuit. Please let me know what is the circuit size and depth in this process.


texts:
I'm going through Cormen et al.'s Introduction to Algorithms and I am a little thrown off by some of the subtleties of solving recurrences with the substitution method.  Given the recurrence:

$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1, $$

We guess that the solution is $T(n) = O(n)$. Thus we try to show that $T(n) \le cn$. By substituting our guess, we are left with,

$T(n) = cn + 1$, which is not $\le cn$.

Makes sense. But then in the next paragraph, he writes that if we guess for $T(n) = O(n^2)$,  we can make the solution work. However, wouldn't the solution still be off by a constant of 1, since:

$$T(n) = O(n^2) = 2c(n/2)^2 + 1?$$

Or am I not substituting correctly for $O(n^2)$? Seems like I'm missing something trivial about this.


texts: Shortest path between any origin to any destination through some way stations

texts:
How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm?

You can visit those way stations in any order. There will be multiple origins and multiple destinations, but a path from any origin to any destination will suffice as long as it's the shortest.


texts: Problem Set Solutions/Interrupts & Exceptions/Problem 1

texts:
Using Tomasulo’s algorithm, for each instruction in the listed sequence determine when (in which cycle, counting from the start) it issues, begins execution, and writes its result to the CDB. Assume that the result of an instruction can be written in the last cycle of its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that. The execution time of all instructions is two cycles, except for multiplication (which takes 4 cycles) and division (which takes 8 cycles). The processor has one multiply/divide unit and one add/subtract unit. The multiply/divide unit has two reservation stations and the add/subtract unit has four reservation stations. None of the execution units is pipelined – each can only be executing one instruction at a time. If a conflict for the use of an execution unit occurs when selecting which instruction should start to execute, the older instruction (the one that appears earlier in program order) has priority. If a conflict for use of the CBD occurs, the result of the add/subtract unit has priority over the result of the multiply/divide unit. Assume that at start all instructions are already in the instruction queue, but none has yet been issued to any reservation stations. The processor can issue only one instruction per cycle, and there is only one CDB for writing results.

Can someone explain why for Instruction 1 the write happens in cycle 5 ?
It is given in the question that MUL takes 4 cycles to execute. So write  for I1 should have happened in cycle 6 ?


texts:
Let $\Sigma$ be an alphabet. Have a look at following definitions frequently used in literature containing Kleene star and Kleene plus.

$\Sigma^* := \Sigma^+ \cup \{\varepsilon\}$
$\Sigma^+ := \Sigma^* \setminus \{\varepsilon\}$

These definitions lead to different sets iff $\varepsilon \in \Sigma_i$ for some $i$. What's the proper one in general context?
Is it similar to mathematical issues like multiplicative identity in rings or including zero in the set of natural numbers?