texts: Algorithm to mimimally pair up points in 3D space

texts:
Given a set of $n$ points $P$ and a set of $n$ points $Q$ in 3 dimensional space, what's the fastest algorithm to uniquely pair points in $P$ with points in $Q$ so that the sum of the square of the distance between points in $P$ and their corresponding point in $Q$ is minimized? Each point in $P$ must be matched with one and only one point in $Q$, and vice versa.

Another way to look at the problem: if $P$ and $Q$ are matricies with 3 columns and $n$ rows, how can I reorder the rows of $P$ so as to minimize the frobenius norm of $P - Q$?

This problem can be solved in $O(n^3)$ by creating a cost matrix $M$ where $m_{i,j}$ is the distance between point $P_i$ and point $Q_j$, and then by using the hungarian algorithm to find the minimal assignment, however I feel like there's a faster way.

Even if there isn't an exact solution, are there any fast approximations?

Edit: for my specific use-case, the points in $P$ are the points on a $m \times m \times m$ grid and $n=m^3$


texts:
A Hidoku is a $n \times n$ grid with some pre-filled integers from 1 to $n^2$. The goal is to find a path of successive integers (from 1 to $n^2$) in the grid. More concrete, each cell of the grid must contain a different integer from 1 to $n^2$ and each cell with value $z ≠ n^{2}$ must have a neighbor cell with value $z + 1$ (can also be diagonally).

Is it NP hard to decide whether a given Hidoku is solvable? What reduction could be used?

Edit: according to the comments, I give a little clarification. Given is a grid of cells, some of them already contain values (integers from 1 to n²). We must fill all remaining cells with integers from 1 to $n^2$, such that no two cells have the same value and that every cell with value $z ≠ n²$ has a neighbor with value $z + 1$. That is, after filling out the cells, we must find the path $1, 2, 3,\cdots, n^2$. In the grid, which logically visits each cell.

An example of a Hidoku woud be http://www.janko.at/Raetsel/Hidoku/018.c.gif.
An already solved Hidoku is http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif, where you can see the path I was refering to.


texts:
today I had to deal with this exercise:

  If $x \approx y$, we might expect some cancellation in computing $log(x)- log(y)$. On the other hand, $log(x) - log(y) = log(\frac{x}{y})$, and the latter involves no cancellation. Does this mean that computing $log(\frac{x}{y})$ is likely to give a better result? (Hint: For what value is the log
  function sensitive (highly elastic)?)

I would assume that in double precision the second expression would be more accurate, but replicating the calculations in R did not show any differences between these two expressions.

x1 <- (1/0.999999999999)
y1 <- (1/0.99999999999999)

log(x1)-log(y1)
log((x1/y1))
1/log(1.00000001)


texts: Time Complexity of Universal Turing Machine Simulations and the Time Hierarchy Theorem

texts:
I have a little problem to understand the proof of the Time Hierarchy Theorem (Hennie and Stearns, 1966) that ensures the existence of a language acceptable in $U(n)$ but not acceptable in $T(n)$ for any functions $T(n),U(n)$, such that $U(n)$ is time-constructible and

$$n \leq T(n) = o\left(\frac{U(n)}{\log T(n)}\right).$$

This proof is based on the existence of the Universal Turing machine simulating any Turing machine with time complexity $T(n)$ in time $T(n) \log T(n)$.

I understand (and believe) the proof that every $k$-tape Turing machine can be simulated by a two-tape Turing machine with a logarithmic overhead. However, I understand this construction only if the simulated Turing machine is fixed, not in the case of the Universal TM simulation.

I see one "problem" in the reasoning given in the cited paper (and also in several standard books on computational complexity) related to the construction of the Universal machine. This "problem" is that in the Universal machine simulation, one computational step of a simulated machine is supposed to be executed in constant time by the Universal machine. In other words, the length of the description of the simulated machine is supposed to be constant.

But is this OK? Since in the proof of the Time Hierarchy Theorem, the input given to the simulated Turing machine is exactly this description, and thus, the description is somehow dependent of $n$. I am aware of that the description can be lengthened by a sequence of leading bits, but this does not seem to solve this problem.

That is, I cannot figure out why the computation step of a simulated machine can be supposed to be executed in a constant time by the Universal machine. The paper of Hennie and Stearns does not pay much attention to this, it merely states that this time is something that is implicitly assumed to be a constant. Similarly in the textbooks I have read on the topic.

I simply cannot figure out why the time complexity of the simulation is $T(n)\log T(n)$, and not $n T(n) \log T(n)$.

I am almost sure that I am missing something. However, I am trying to understand this for a relatively long time and somehow I cannot figure this out.


texts: Hamming distance required for error detection and correction

texts:
I have already asked a pair of questions on the hamming distance, hamming code, valid and invalid codewords on this website, because I cannot understand those concepts fully, and in a few weeks or less, I am going to have an exam also on those topics, I really do not understand. I have tried to take a look to wikipedia articles, but it is, for me, quite complicated to understand.

My question this time is more concrete. I have a figure, representing how many errors can we detect and correct according to the hamming distance. The thing I am not understanding is why, for example, with an hamming distance of 3, we can just detect 2 bit flips and correct 1 bit flip. I know there are 2 formulas (that you can see in the picture), which bring us to that result, but I would like understand why those formulas are correct. Why, with an hamming distance of 3, we can just detect 2 errors and correct 1.

This is picture:


texts: Is there a publicly available informer tagger or dataset?

texts:
I am working on a question answering system. I've learned that informer spans are valuable features for question classification. However from what I've read I wasn't able to find any publicly available dataset for this task, or a trained tagger. Is there any? People seem to just hand-label their dataset.

If there aren't any available, then how does one label the dataset and build the tagger?


texts:
For chaining two points A and B

A(x1,y1) at index i in array
B(x2,y2) at index j in array

//condition
if ( i<j and x1<=x2 and y1<=y2 and !(x1==x2 and y1==y2))
    then A and B are in a increasing sequence (chain)

For example:
A = { (0,0), (1,0), (1,1), (2,1), (2,0)}

longest sequence (cahin) is = {(0,0), (1,0), (1,1), (2,1)} i.e 4 elements

we have to find the longest sequence (chain) of points.

How to approach for this?

solution required is less than O(N^2)

Possible solutions:-
1) LIS (NlogN) link
2) Posets (I don't understand if you can explain)


texts: Processor consistency and cache coherence

texts:
Consider this example from Wikipedia:

P1 |    W(x)1
----------------------------------
P2 |        R(x)1   W(x)2
----------------------------------
P3 |                R(x)2   R(x)1
----------------------------------
P4 |                R(x)1   R(x)2

Where P1 - P4 are different processors that issue read and write instructions to variable x in the given orders (their written and read values are given as well).
It is clear that this example is Processor Consistent so it must also be Cache Coherent. But how is this possible in this example?


texts: Subtracting a two's complement value from another two's complement value

texts:
I'm trying to solve the following problem:

$$ 6AD3 - AF20 $$

Both of these are hex values in two's complement.

I keep getting one answer but it's turning out worng. What I tried to do, was take the complement of AF20, which I got as 50D1, and instead of subtracting, I added it to 6AD3, and I got BBA4, however, I am being told this is the wrong answer.

Where am I going wrong?


texts: Minimum cost tour for a simple connected graph having exactly two odd degree vertices

texts:
This is one of the special cases for Chinese Postman Problem.
I know the answer is (Cost of all Edges + Cost of shortest path between the odd degree vertices). How do I prove this?

I am trying to prove the solution to this UVA problem.


texts: How does a Single Pass Compiler does parsing,analyzing and generating code all at once?

texts: I would like to know how a single pass compiler does parsing,analyzing and generating code all at once as said in P.14 of SIngle Pass Compilers.Is it possible to do all these at once since you can't generate an code without parsing or analyzing it which should be done earlier before producing the object code?


texts: Is the power of a natural number logspace-computable?

texts:
Given a constant $n\in\mathbb{N}_+$, is the simple power function
$$
λ\,x\in\mathbb{N}_+.\,x^n
$$
logspace computable by a logspace transducer (which has a read-only input tape, a working read-write tape (on which the transducer is allowed to use $\mathcal{O}(\log (\text{input size}))$) cells, and a write-only output tape), assuming that the input and the output are in binary?  (It is not even clear to me how to do it for $n=2$ in logspace.) Any ideas or references?


texts: Is this language recursively enumerable?

texts:
Let $P=\{L \mid  \exists w\in \Sigma^* s.t. w\in L  \wedge \forall z>w\colon z\in L\}$ .

Now denote $L=\{\langle M \rangle \mid L(M)  \in P \}$.

That is, $L$ is the set of all TMs $M$ s.t. there exists a $w\in \Sigma^*$ s.t. $w$ is accepted by $M$ and for each $z>w$, $z$ is accepted by $M$ as well.

I am trying to find out whether $L$ is in $RE$ or not.

I can easily show that $L$'s complement is $\notin RE$ using Rice's Theorem. But here, if using Rice's Theorem, I can only show that $L \notin R$, but I have no guarantee over $RE$.

I thought about using reduction - either to prove $L\in RE$ or to disprove, but none came about. I thought about using $L_{acc}$ or its complement, $L_{\Sigma^*}$, but could not come up with an idea that will work for either direction of the reduction.

Could someone assist?


texts: What is the output of below algorithms on a disconnected Graph?

texts:
If I apply Dijkstra's ,BFS or Bellman-ford algorithm on a disconnected Graph then will the output be a tree or a disconnected Graph only because even if we have a disconnected Graph and we run Dijkstra's algorithm on it then it will return shortest path in the connected component only , but we maintain a predecessor array in all the algorithms which has information about the parent from which the node learnt the path so it will values for all the vertices , so even if we have a disconnected Graph then still other vertices will also be printed .

So output is Graph right for all the algorithms whether the graph is undirected or directed ?


texts: number of comparisons in searching algorithms

texts:
i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these.

For linear search :

procedure Linear_search(a1,a2,...,an:integers,k)
1.location = 0;
2.for i = 1 to n      #n+1 times
3.    if (a_i = k)  then location = i # n times
4.return location;

so total comparisons are =n+n+1=(2n+1). Right?

For Binary Search and ternary search,we know the algorithm.But the number of comparisons are,

T(n) = T(n/2) + 2,  T(1) = 1
 T(n) = T(n/3) + 4, T(1) = 1

Hence solving this will give 2clogn + O(1) and 4clogn + O(1).

how to constants(2 ,4) are formed??
Also correct me if my comparsions are wrong.


texts: Solving the recurrence $T(n)=T(n−1)/T(n−2)$

texts:
How can I solve this?
I saw Solving the recurrence $T(n)=T(n-1)*T(n-2)$ but I don't know how I can apply it to $T(n)=T(n-1)/T(n-2)$?


texts: Why is the node with the greatest DFS post-order number not necessarily a sink?

texts:
A sink in a directed graph is a node with no outgoing edges. If I perform a depth first search, why is it that the node with the least post-order number (and thus the highest pre-order number) not necessarily a sink - isn't this node found last?

Also, intuitively, the node with the greatest post-order number should be a source - a node with no incoming edges.


texts: How does the use of oracle Turing machines not lead to contradictions?

texts: How can we ensure that we are continuing to make sound and valid statements about complexity classes when using oracle Turing Machines?  According to my understanding (based on the definitions given in introductory textbooks on the subject)  oracle Turing machines can determine the membership status of a string with respect to an oracle language in one computation step.  However the oracle languages often used are provably impossible to solve in constant time (take an EXPTIME-complete oracle, for example).  To me this seems like "opening the door" to contradictions and after all, anything follows from a contradiction.


texts:
I do not know if I miss something in the definition of a hyper-cube, but as far as I understand, Hyper-cube graphs have 2^n vertices and if written in binary form, "one-bit difference" strings of numbers are linked with an edge.

From this definition, De Bruijn graph does not look like it is a hyper-cube, because 000 and 010 for example, are not adjacent.


texts: is it possible to have a mapping reduction between 2 NP complete languages?

texts:
so i have a good understanding about languages that belong to NP, P and NP complete, and how Polynomial reduction works between languages that belong to those areas.  but i just can't figure out a conclusion about mapping reduction between languages in those areas.
for example if i have 2 languages - A and B, that both of them are NP-Complete,
can i do a  A ≥m B (mapping reduction) or B ≥m A ?


texts: Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?

texts:
Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$.

Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $x,y\in (\Sigma \cup N)^*$ and $\mathcal{S}(G)$ are the sentential forms of $G$.

Given $G$, I'd like to determine a set $C = \{ b \mid wabz \in \mathcal{S}(G), b \in \Sigma \cup N \}$.

To clarify, in this case, $w, x, y, z, a, b$ are strings of terminals and non-terminals and $b$ is of length one.

I can see how to do this if $a$ is also of length one; each $b$ is a member of the follow set of $a$ (including non-terminals).

However, I am curious if it's possible for a sequence of characters. For my application, the string $a$ is not much longer than the right hand side of the productions in $G$.

The distinction between terminals and non-terminals is somewhat mute in my application because I am using a generative grammar; and I believe that this won't lead to much trouble since $b$ is of length one.


texts: Did Wheeler really believe that physics was undecidable?

texts:
John Archibald Wheeler was a famous physicist

It has been stated that he thought that there was a strong connection between undecidability and quantum physics

  This idea was given an early formulation by Wheeler
  himself: in unpublished notes to a discussion held with,
  among others, Roger Penrose and Simon Kochen, he
  identifies the point of origin of the ‘quantum principle’
  as the undecidable propositions of mathematical logic

(https://arxiv.org/pdf/1805.10668.pdf)

But then, this same physicist proposed that the universe was similar to a computer and that reality emerged as digital informational processes in form of bits (It from Bit): https://en.wikipedia.org/wiki/Digital_physics

As far as I know, digital physics models cannot be undecidable. They must be decidable (If not, we could never construct an algorithm which would get a correct answer to a yes/no question)

So, what is happening here? Did Wheeler change of mind?


texts: Deriving the average depth for a randomly generated binary search tree

texts:
If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken an arbitrary tree with a left subtree containing $i$ nodes and the right subtree containing $n-i-1$ nodes.

Correct me if I'm misunderstanding this, but since these left and right subtrees can be anything (where $i=0,1,2,...,n-1$) then the average of $D$ is given by $$\langle D \rangle=\dfrac{1}{n}\left(2\sum_{i=0}^{n-1}D(i)+\sum_{i=0}^{n-1}(n-1)\right)$$ where I divided by $n$ since there are $n$ different left/right-subtree possibilities. What I don't understand is that online sources and my textbook equates this to $D$ itself. In other words, I don't quite understand why we're allowed to set $\langle D(n) \rangle = D(n)$.

Ignoring that, I continued on and I'm also running into the problem where my book is writing $$ D(n) =\dfrac{1}{n}\left(2\sum_{i=0}^{n-1}D(i)+(n-1)\right)$$ and seems to be ignoring the sum altogether. The reason why I say this is because later the book claims that $$ nD(n) =2\sum_{i=0}^{n-1}D(i)+n(n-1)$$ This doesn't make any sense to me since I had a $$\sum_{i=0}^{n-1}(n-1)\in O(n^2)$$ term in my expression so multiplying by another $n$ should be give me something like $$ nD(n) =2\sum_{i=0}^{n-1}D(i)+O(n^3)$$ instead. I feel like I'm missing something obvious but I can't quite figure it out. Any ideas?


texts: Program synthesis based on function properties

texts:
I am fairly new at program synthesis and the use of SMT solvers for this purpose. Given a function g, I want to generate all the functions f and h such that the following holds:

  f . g = h . f

Are there program synthesis tools and techniques that would allow me to search the program space for these functions?

I am assuming the search space is going to be extremely large for general programming languages like Haskell. How should one go about pruning the search space: would one have to drastically reduce the search space by defining a small language and performing the search over this language? It seems that the type constraints of the above equation would also help in pruning the search space. Any observations or pointer to tools, papers, or presentations would be appreciated.


texts:
I work on a recommender system framework which is implemented with a variant on Funk SVD (See his explanation of his algorithm here).

However the framework that we are trying to integrate doesn't support Funk SVD, only SGD (Stochastic Gradient Descent).

Since shouldn't these be compatible? In other words, I should be able to create the U and V matrices with SGD and then treat them like they were made via the Funk SVD process?

Are there any disadvantages of using this versus the algorithm detailed by Funk?


texts: Can someone help me fully grasp idea and time/space complexity with this code?

texts:
My understanding is the following:
Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first loop enumerates the second list b with the operation append() which is done in O(1) time therefore the first loop is O(n). The second loop I am confused if the sorting plays a factor since I know the sort method is O(nlogn) time. Within the second loop I am a bit confused about the operations as far as what it is specifically doing which I wanted to ask about although I do understand the fact that if the i-th element in a is < c it goes into the if statement.
Space = Overall I think it is O(n) as the only additional space needed was the list x plus the input space and the length of x grows as a or b grows.
Given the following Python code:
a = [3, 1, 2]  # input length will be size n
b = [1, 2, 3]  # input length will be size n
c = 4

def foo(a, b, c):
    res = 0
    if not a:
        return res

    x = []
    for i, j in enumerate(b):
        x.append((j, i))

    for j, i in sorted(x, reverse=True):
        if a[i] < c:
            res += a[i] * j
            c -= a[i]
        else:
            res += c * j
            break
    return res

Can someone help go over what the time and space complexity is plus the idea behind it mainly?


texts: How to guess the value of $j$ at the end of the loop?

texts:
for ( i = n , j = 0 ; i > 0 ; i = i / 2 , j = j + i ) ;

All variables are integers.(i.e. if decimal values occur, consider their floor value)

Let $\text{val}(j)$ denote the value of $j$, after the termination of the loop. Which of the following is true?

(A)$\quad \text{val(j)} = \Theta(\log(n)) $
(B)$\quad \text{val(j)} = \Theta(\sqrt n) $
(C)$\quad \text{val(j)} = \Theta(n) $
(D)$\quad \text{val(j)} = \Theta(\log\log n) $

Please explain, is there any easy way to guess the value of $j$?


texts: Running time complexity of Binary Search Trees and Big-Omega

texts:
I know that the main operations (Insert, Search, Delete) have a worst-case running time of $\mathcal{O} (h)$. But I wanted to dig into this deeper.

Basically I am having some difficulties understanding "Big-Omega" when it comes to the worst-case time complexity. I usually define them as follows:

Let $t(x)$ be the number of steps taken by an algorithm $\mathcal{A}$ on input $x$.

Let $T(n)$ be the worst-case running time complexity of $\mathcal{A}$.

$T(n) = max(t(x))$ where max is over all inputs x of size n.

Then $T(n) \in \mathcal{O}(g(n))$ if for every input of size $n$, $\mathcal{A}$ takes at most $c \cdot g(n)$ steps.

Moreover,

$T(n) \in \Omega(g(n))$ if for some (there exists) inputs of size $n$, $\mathcal{A}$ takes at least $c \cdot g(n)$ steps.

Returning to BSTs....

We know that for all inputs of size $n$, in the worst case, the height of the tree is $n$, which means we need to visit all $n$ nodes in the worst-case. This is the "ultimate" worst case (forgive my lack of rigour here!), meaning it cannot get any worse, and hence $\mathcal{O}(n)$ running time. But we also know that a tree may be balanced, in which case we could argue that there exists such an input (a balanced tree) such that we would take at least $\Omega(logn)$ for the running time. This is still a "worst case", but a lower bound to that worst case.

I don't feel that is quite right, nor does it make much sense. Perhaps I am just lacking an understanding of how to determine when $T(n) \in \Omega(g(n))$.

any help appreciated!


texts: Show that only a few multiples of .01 decimal are powers of 2

texts:
I am asking this to advance the argument that BigDecimal is better than float or double for representing exact amounts of currency.

Can someone refer me to a proof that between any two integers there are only four values that multiples of .01 and can be exactly represented in base 2?  Or at least confirm I'm correct in my belief that it's true?


texts: Efficient algorithm to fulfil a set of coordinate constraints

texts:
I have a set of labelled points and a set of distance constraints between pairs of points, consisting of a lower and upper distance bound. There is definitely an arrangement of the points in 3D space that fulfils all distance constraints.

I wish to generate arrangements of the points where all constraints are fulfilled. Any approach is allowed as long as each arrangement is independently generated from the others.

What algorithm is most suitable? Mainly in terms of efficiency.

As an extension, how would I incorporate constraints on the angle defined by three points? And on the dihedral angle defined by four points (the dihedral angle between points ABCD is the angle between the plane defined by ABC and the plane defined by BCD)?


texts:
This is the question:

  By definition of the IEEE754 standard, 32-bit floating point numbers
  are represented as  follows:

  S (1 bit)  E (8 bits)  M (23 bits)  S: Sign bit  E: Exponent  M:
  Mantissa

  Which of the following is the correct “mask bits” in hexadecimal to be
  used for  extracting only the exponent part of the above format?
  Here, “mask bits” means a bit  pattern which is logically ANDed
  withthe 32-bit floating point value.

  a) 107FFFFF  b)  7F800000  c)  FF100000  d) FF800000

The given answer is b : 7F800000, but i have no idea why, can anyone give me an explanation, i'm greatly appreciated!

Is that because :

7F800000 = 0111 1111 1000 (8)

While others answer contain more "1" in binary format?


texts: Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one?

texts:
So if we have a complex equation in regular algebra we can use properties like distrbuivity, associativity and commutativity to make an equation simper or more compact.

Can we use some sort of techniques on regular expressions to make them more simpler?

For example what is the relation between concatenation and kleene star? If we have a concatenation with an union between two expressions that have kleene star can we draw a conclusion using some sort of property to distribute the concatenation somehow or do something else. I just started learning this subjects and I may not be very good at expressing what I think right now.


texts: Where can a student learn image processing?

texts:
I am a student of computer science with interest in image processing. I have learned how to apply a few effects to images like making them grayscale, sketching them out of lines, etc.

I would like to learn more about the algorithmic techniques  behind creative manipulation of images like making them sepia-tone, smudging them, etc.

Can someone please point me in the right direction?
How do I learn the fundamentals of these algorithms?


texts: Balance groups based on average, element constraints and size

texts:
It's a complex situation, where I want to balance groups of numbers based on the average of these numbers, while keeping the group size unchanged and not breaking elements constraints.

Let me explain in detail what I mean:

I need to switch elements between the groups in order to balance the group average.
However the elements with the same color needs to stay in the same group, and the groups must not change size.

What would be a good approach for solving this problem? I'm using c++ to code a matchmaking system for a game, and that's the mathematical problem I'm stuck with currently.

My knowledge of mathematical notations are quite weak, so I would prefer some sort of pseudo-code as answer (if possible)


texts: Product Matching problem in pattern matching

texts:
The Product Matching problem is defined as follows:
Input: Text T=t0,...,tn and pattern P=p0,...,pm over alphabet Σ=N .

Output : All of the i places in the text where exists ci which holds
ti+j = ci * pj for every j=0,...,m

For example:
T= 2,3,9,12,1,8 P = 1,3,4
so in index 1 there is a match for ci=3 because:
1*3 = 3 , 3*3=9, 4*3=12

I've only managed to think about the naive way of multiplying the pattern for each number that gives
us less or equal value to max{T} and then checking it with a regular O(N) pattern matching algorithm.


texts:
Let $ G=(V,E) $ be a directed graph with a real weight function $w$ defined on the edges and $ a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the minimal weight of all paths from $b$ to $a$. How do you find two paths $l_1,l_2$  such that:

$l_1=(a,v_1,..,v_n,b)$
$l_2=(b,u_1,..,u_m,a)$
$w(l_1) + w(l_2)\leq 1.1(\alpha + \beta)$
From all the paths holding the above, bring to minimum the sum of weights on the edges $e=(u,v)\in l_1$ such that $(v,u)\in l_2$

Less formally, I want to find a path starting at $a$ ending with $b$ and returning to $a$ such that the path is not too long (at most 10% longer than the optimal solution) and tries to use as much as different roads as possible (if it used some road $(x,y)$ when going from $a$ to $b$ , it would try to avoid the road $(y,x)$ when going back to $a$)


texts: Trading Auction - Need help with calculating price / quantity of restricted underlying securities for matching

texts:
I'm having some difficulty with implementing a non-brute force algorithm for solving the following Problem. If I can get something even close to O(N^3) i'd be happy at this point.

Auction: https://www.investopedia.com/terms/a/auctionmarket.asp

I have an algorithm in place that can do a generic Auction (accumulating bids and offers over a fixed period of time, leading up to an event whereby bids and offers are matched to determine a reference price (the price securities are sold at in the auction)however we've just implemented a level of complexity that is throwing me for a loop.

We have a security with underlying shares that contain restrictions on who can own them. During an auction, we need to ensure that buyers can only buy shares they're allowed based on the underlying restriction.

Example:

Security: Foo
-Class A Shares
-Class B Shares
-Class C Shares

Buy Orders

John can only buy Class A and Class B (Wants to buy 500 at $1.50)
Sally can only buy Class B, and Class C (Wants to buy 300 at $1.52)
Joel can buy any class. ((Wants to buy 200 @ 1.49)

Sell Orders

Xavier owns 500 (200 Class A, 300 class B) and is selling 400 at $1.42
Jennifer owns 1000 shares (800 Class B, 200 class C) and is selling 650 at $1.50
Martha owns 1500 shares (300 Class A, 1200 class C) and is selling 400 at $1.52

When a user puts in  Buy / Sell auction order, they don't care what class of shares they're buying or selling, we can determine what they are buying or selling.

The goal is trying to find the price point where the most shares can be sold, while making sure that we're filling all orders that can be filled.

I've ran through multiple scenarios on calculating it from a price perspective, and the underlying class perspective, calculating the # of shares that can be sold at each price point, but I'm at a blank as each way I do it, i find I'm missing shares that could be traded.

Example: The following illustrates (when we have a correct price) that we also need to match buyer & seller  using the most restricted / least tradable security so we match those who can't trade with much first, then go for those that are less restricted.

The above isn't hard to solve, it's getting to that point, to figure out the best price and tradeable amount.

Any thoughts or ideas on this?


texts: Knapsack-like problem with profit formula

texts:
Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once.

The profit is given by the following formula:
$$
\min(\mathit{takenweights}) \times \sum_{i=1}^m \mathit{takenreps}(i),
$$
where $m \leq M$.

For example, if $M = 3$, the weights are $3,5,6,2,4,9$, and the reps are $8,3,4,10,7,4$, then the output should be $60$, obtained by taking the third, fifth and sixth dumbbells (minimum weight $\min(6,4,9) = 4$ and total rep $4+7+4=15$).

I was thinking of using two double arrays, one for the minimum and one for the profit, where $dp(i,j)$ is the maximum profit obtained by taking $i$ dumbbells among the first $j$, and $dp_{\min}(i,j)$ is the minimum for $dp(i,j)$.

However, I couldn't find a recursion formula.

Do you have any suggestions?


texts: Finding the smallest-cost way to deliver goods

texts:
I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each supplier. In particular, each supplier ("source") specifies a minimum and maximum quantity of the product that should be taken from them (i.e. the "minimum" indicates that we must purchase at least that amount, whereas the "maximum" indicates that we must take no more than that amount). So the sum of the minimums is less than the sum of the total product we must provide, and the sum of the total product we must provide is less than the sum of the maximums.
My manager tells me that they have computer code that can solve the capacitated minimum spanning tree problem (see: https://en.wikipedia.org/wiki/Capacitated_minimum_spanning_tree). Using this as a oracle, how can you determine a method to determine which supplier(s) should deliver their products to which destination(s) at a lowest total cost (or explain why it can't be used to solve the problem)? I'm provided with the costs $c_{i, j}$ of transporting from source $i$ to destination $j$, and I'm also provided with the minimum and maximum quantities of product to be taken from each supplier.

This is a practice problem that I encountered while studying NP completeness and reductions.
I know that I need to somehow construct a graph to pass into the blackbox but coming up with the graph is the tricky part. I thought about constructing a graph with all of the $c_{i, j}'s$ as edge weights, but then I can't get the maximum and minimum quantities to come into play. I've thought about this problem for a while now, but I still can't figure it out. Does anyone have any suggestions? This reduction seems a lot more complicated than the other ones I've seen, or maybe I'm just overthinking it?


texts: Does an insecure router bypass the privacy guarantee of a VPN connection?

texts:
If I have a router that has a vulnerability that allows an attacker to gain full control it, does using a VPN on the network with the said router prevent an attacker from being able to snoop on the connection?
In other words, does using a VPN secure the connection from a device to a router? And would a VPS make a difference in this scenario?


texts: A recursively enumerable language and a recursively enumerable set

texts:
I am confused between these two terminologies: recursively enumerable language, recursively enumerable set.

Do they have the exactly same meaning?


texts: Proving that the language $\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$ is not regular

texts:
I'm trying to prove that the following language is not regular:
$$\{ w^n\mid w \in \{0,1\}^∗, \, n  \ge 2 \}$$
I'm trying to prove this with the pumping lemma, but I'm kind of confused because $w$ is a language, not an expression like $a^n b^n$, and I don't know how can I partition that into three parts.


texts: Algorithm for generate all solutions to a linear Diophantine equation

texts:
Consider the linear Diophantine equation of the form:
$$\sum_{i=1}^{k}a_ix_i=n.$$
My goal is to list all the non-negative solutions to this equation. I wrote the following recursive algorithm, but I am not sure if it is the most efficient way to build the solutions. Here is the current version:

def recsolve(n, L, cursol, result = []):
if len(L) == 1:
    ak = L[0]
    if n%ak == 0:
        result.append(cursol + [n//ak])
    return

else:
    a1 = L[0]
    end = math.floor(n/a1)
    for k in range(0, end + 1):
        recsolve(n-k*a1,L[1:], cursol + [k],result)

result = []
n = 5
L = [1,2,3]
recsolve(n, L, [], result)
print(result, "; Number of solutions:", len(result))

I would be grateful if someone could suggest more efficient approaches to finding all solutions to a linear Diophantine equation.


texts: Complexity of pattern matching for modus ponens logical conclusions

texts:
Is a Turing machine with added the following contant-time operation equivalent (in the sense that polynomial time remains polynomial time and exponential time remains exponential time) to a (usual) Turing machine:
By predicates I will mean predicates in first-order predicate calculus. (Note that predicates may have free variables.)

constant-time modus-ponens resolution (yes or no) and then adding $y$ to the end of this array if yes, for given predicates $x$ and $y$ and an array (or a linked list) of predicates. By definition of modus ponens, it's yes, if and only if some element of the arrays is $X\Rightarrow y$ where $X$ is a pattern matching $x$.

Remark: The above operation is a part of the standard procedure of proof-checking is first-order predicate logic.
If the above hypothesis is false, then what is the running time upped bounds of the above operation in different kinds of Turning machine equivalents (such as Turing machine, Markov algorithms, von Neumann architecture with infinitely many infinitely big words of memory, etc.)?
BTW, is von Neumann architecture with infinitely many infinitely big words of memory a Turning machine equivalent? (I think yes, but not 100% sure.)


texts: General version of pumping lemma for regular languages, how many partitions to consider

texts:
The pumping lemma for regular languages states, that one should consider a string $w = xyz, w\in L$, that is, every possible division of $w$ into $xyz$.

The article on wikipedia says, that this version is a special case of a more general version, in which one should consider strings $uwv = uxyzv$.

When using that general version of the lemma, does it require considering every possible partition of the string into $uxyzv$? I.e. does it require considering every possible $u$ and $v$?


texts: What is the most efficient way to compute factorials modulo a prime?

texts:
Do you know any algorithm that calculates the factorial after modulus efficiently?

For example, I want to program:

for(i=0; i<5; i++)
  sum += factorial(p-i) % p;

But, p is a big number (prime) for applying factorial directly $(p \leq 10^ 8)$.

In Python, this task is really easy, but i really want to know how to optimize.


texts: What does it take to create a new programming language and its toolchain?

texts:
I am super novice to this topic, so my apologies if my question looks completely nonsense to you all!
Imagine you want to create a new programing language that transpiles to a more common high/low-level language such as C, LLVM IR, Cranelift, MLIR, libFirm, GIMPLE ... how would you do that and what are the steps towards that goal?

I can imagine that the first step is to have a context-free grammar using BNF or any of its variants/flavors (hence the question here). Data types/structures, classes, functions, operators, loops, if-statements, ... should be probably represented by regular expressions. One may reuse some of the pieces already used in other programming languages. For example here the ANTLR grammar for many different languages.

Next step one may use tools such as lex, Flex, Yacc, GNU Bison, ANTLR ... to generate/develop a parser automatically.

I have no clue what could be the next steps and if there are tools to automate the rest of the toolchain. For example given the RegEx representation of the basic building blocks of the language, generate a transpiler automatically. I would appreciate it if you could Eli5 how a new programing language and its toolchain is made.


texts: Using a rotation matrix to transform/shift a pinhole camera

texts:
I have a pinhole camera model with the following extrinsic (in Earth Centered, Earth Fixed Coordinate, (ECEF) system) and intrinsic parameters.

focal length (x,y) = 55000 px, optical center = (2400,540)

camera center (x,y,z), (ground coordinates) = -2322996.2171387854 -3875494.0767072071 5183320.6008059494 (ECEF)

Rotation matrix (3x3, camera to ground frame)  =  [[0.88982706839551795,-0.45517069374030594 ,0.032053516353234932], [-0.44472722029994571, -0.84940151315102252, 0.28413864394171567], [-0.10210527838913171, -0.26708932778514777, -0.95824725572701552]]

I need to shift the camera so that it points to the correct position on the ground based on a ECEF transformation matrix (4 X 4), which looks like this:

[[0.99999922456661872, 0.00043965959331068635, -0.0011651461883787318,   7033.5303197340108],
[-0.00044011741039666426, 0.99999982604190574, -0.00039269946235032278     ,814.02427618065849],
[0.0011649733316053631, 0.00039321195895935108, 0.99999924411047925      ,4139.9400998316705], [0, 0, 0, 1]]

The 3 x 3 matrix portion formed by the first three rows and columns are the rotation component, the first three values in the last column is the translation component. My general understanding is that I need to add the translation component to the camera center coordinates, while multiply the camera to ground rotation matrix with the rotation component. Is this sufficient, or would I need to do something extra ?


texts:
What is a reducible flow graph?   sorry if this is a stupid question but I'm having trouble finding an answer.
Also multiple equivalent definitions and some motivation would be nice too.


texts: Emergent complexity and Turing Completeness

texts:
Is there some link between the concept of emergence and Turing Completeness?  The ideas feel intuitively like they might be linked, but I can find nothing online.

The idea came to me because I was exploring Conway's Game of Life, and it was hard not to suppose a link between these two properties.

Edit: In response to Raphael's point, I have a clarification to the question (which I thought was implied, but in hindsight, it really wasn't)

Must it be the case that systems that exhibit weak emergent complexity are also Turing Complete?


texts: print the nodes of an immutable single-linked list in reverse order

texts:
Assume you have a single-linked list of length n. The list is immutable. A node node has a method next and  node.next() returns a reference to the successor of node. node.print() prints the value of node node or does some other stuff, such etails don't matter.

Is it possible to print the nodes of the list in reverse order in linear time using only a constant amount of space?

Details:

For the last element of a list next points to a special node named NIL that represents the end of a list. For NIL next() and print() are not defined.

The following simple pseudocode program prints the nodes in the order of the list. FIRST_NODE points to the first node of the list. Variable names that store references to nodes are prefixed by 'node_'.

node_current=FIRST_NODE
while node_current!=NIL
    node_current.print()
node_nurrent=node_current.next()

This algorithm calls of the medthod next n-times and there is one variable that can hold a reference to a node.

To print the k-th node of the list one can traverse the list from the start node to the k-th node in k steps. So to print the list in reverse order the following algorithm works

node_first=FIRST_NODE
node_last=NIL
while node_last!=node_first
    node_current=node_first
    while node_current!=node_last:
        node_previous=node_current
        node_current=node_current.next()
    node_previous.print()
    node_last=node_previous

It needs about $\frac{n^2}{2}$ calls of method next and needs 4 variables that can hold a reference to a node: node_first (the first node of the list), node_last (the last node that was printed), node_current (the node that is currently investigated) , node_previous (the predecessor of node_current)

It can be shown that there are algorithms that need about $O(n^{\frac{1}{k}})$ space and $O(n)$ time for an arbitrary choosen k from {2,3,4,...} to print a single-linked list in reversed order. It is also possible to do this in $O(\log n)$ space  and $O(n \log n)$ time.
 This can be found here

Can one do this better?

My question: Is there an algorithm with $O(1)$ space complexity and $O(n)$ time complexity  that prints such a list in reverse order?

Please note that the definition of the problem excludes an algorithm that prints a list in reversed order in linear time with $O(1)$ space for node references while changing the references of the list:

The list is traversed form start to end and the references are reversed during this traversal: the reference from a node to its successor is overwritten by a reverence to its predecessot. If on arrives at the and of the list is straersed form the former end (which is now the start) to the former start (which is now the end) and the nodes are printed.


texts: modular arithmetic in rolling hash algorithm

texts:
My question was around the rolling hash function in RobinKarp algorithm. It is intuitive for me to understand how to get from xi to xi+1 without the mod, however with the mod i am not sure how we still get the right answer. Is there any mathematical theroem anyone could quote which would help me understand?

So i get,

xi = (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1
xi+1 = (xi - (ti)R^0)/R + (ti+m)R^M

but whats the guarantee,

xi = [ (ti)R^0 + (ti+1)R^1 + .. + (ti+m-1)R^M-1 ] mod Q
xi+1 = [ (xi - (ti)R^0)/R + (ti+m)R^M ] mod Q

.. and so on will be correct even after introducing mod Q

Pretty sure its some basic mod arithmetic theorem i am missing here.


texts: How to find minimum number of k-input LUTs needed to express a n variable boolean function?

texts:
An k-input LUT (look up table) takes in atmost k-inputs and gives 1 output (which is a function of the k inputs). I need to devise an algorithm to find the minimum number of k-input LUT's required to express a n variable boolean function.

For example : - n=8 and k=4 8 input variables are a0,a1...a7

1) f1(a0,a1,..a7)= a0*a1 +a3*a4 + a5*a7 + a6*a8 Requires 3 LUTs : LUT1 :a0*a1 + a3*a4 =x1 LUT2 :a5*a7 + a6*a8 =x2 LUT3 : x1+x2

2) f2(a0,a1,..a7)= a0*a1 +a3*a4 + a5*a7 + a6 Requires 2 LUTs : LUT1: a0*a1 +a3*a4 =x1 LUT2: x1+a5*a7+a6

NOTE: I want to solve this for the particular case of n=8 and k=4. Though, I would like to extend it to other cases like (n,k)= (8,2).


texts: NL - iterating all edges of a graph in log space

texts: Given a turing machine which has logrtmic space, and consists of an input tape and a working tape, Is it possible to iterate all egdes of an input graph? I know the answer is probably NO, because clique and other similer NP problems  belongs to NP and not to NL. Unfortunately, I can't find a satisfying and clear explanation to that fact. Can some one make it more clear for me?


texts: How to find highest normal form of a relation, given its functional dependencies

texts:
Let's say that I have a relational model, defined as:

$$X(A,B,C,D,E,F,G)$$ with the functional dependencies:
$$f_1: \{A,B,C\} \to \{D,E,F,G\}$$
$$f_2: \{A,B\} \to \{C\}$$

Using this information I need to determine the highest normal form (for us it's BCNF) that this relation will go to. It's clear that the relation is already in it's atomic form, therefore it's already in it's first normal form. The to proceed to the second normal form, I found that the candidate key is $\{A,B\}$ and since all non prime attributes are fully dependent on the candidate keys, it's in the second normal form. But from this point I'm not sure where to go because all the non prime attributes (excluding $C$), $D,E,F,G$ are dependent on $C$ which is also a non prime attribute.

How can I separate this relation and proceed to the third normal form?

PS - I'm not sure if this is the right place to ask a database question but since the stack exchange for database is for professionals, I thought I should post it here. If someone knows a better stack exchange for this sort of a question, I'll transfer it over to that one.


texts: Competitive programming: Good Subsets problem

texts:
An array of length K is called good if for each subarray of the array, the sum of the subarray is not divisible by K+1. You are given an array A of length N. Find the number of subsequences of length B of array A which are good. Since the answer can be large, return it modulo 10^9+7.
Constraints:

1 <= N <= 1000

1 <= A[i] <= 100000

1 <= B <=10

Time limit: 1 sec
Input format: The first line contains an integer N denoting the number of elements in an array. Second-line contains N space-separated integers representing array elements. The third line contains an integer B
Sample Input 1:
4

2 3 4 5

1

Sample Output 1:
2

Explanation: Here B=1, so any good subsequence should not have any subarray divisible by 2 (2 because B+1 = 2). Therefore, 2 possible subsequences are {3} and {5}. We cannot consider {3,5} because the sum of 3+5 is divisible by 2. Also the same reason for other ignored subsequences.
Sample Input 2:
3

3 5 4

4

Sample Output 2:
3

Explaination: Possible subsequences are {3},{4},{3,4} because no subset of these subsequence is divisible by 5 (here B=4)
I came up with a recursive approach but it was getting TLE (Time limit Exceed).


texts: Can an artificial neural network convert from cartesian coordinates to polar coordinates?

texts:
Given cartesian coordinates $x$ and $y$ as input, can a neural network output $r$ and $\theta$, the equivalent polar coordinates?

This would seem to require an approximation of the pythagorean theorem (which requires approximations of $x^2$ and $\sqrt{x}$) and $\sin$, $\cos$, or $\tan$ approximations. Is this possible?

If so, how many hidden layers would it take? I'm using an LSTM.


texts: How get the permutation of two lists but the elements of each list remain in the same order?

texts:
So if I have lst1 = [a, b] and lst2 = [x, y] the result would be:

[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]

I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).

But I'm wondering if there may be a nicer way to do this?

edit: Some more elaborate info here


texts:
I am looking at the following non-deterministic finite automata which accepts all strings that end with at least 2 bs.  I am wondering what would happen when you have the input string 'abba' with this automata:

The possible computations I have so far are

q0, q0, q0, q0, q0

q0, q0, q1, q2, ??

q0, q0, q0, q1, ??

Would anyone be able to fill in the '??'s in this automata and be able to explain why they occur?


texts: Complexity of two cycles which differ by $1$ in length

texts:
Given an undirected graph $G(V,E)$, our problem asks whether $G$ contains $2$ simple cycles which differ by $1$ in length.

What is the complexity of this problem?


texts: algorithms and the sequencing of numbers given a value

texts:
The numbers in the table below are the result of executing an algorithm that has one parameter $n$, a non-negative integer, and produces sequences of integers as outputs. For values of $n$ from 0 to 5, the algorithm produces the following sequences of numbers as outputs:

$n = 0$: 0, 2.
$n = 1$: 3, 5, 7, 9.
$n = 2$: 6, 8, 10, 12, 14, 16.
$n = 3$: 9, 11, 13, 15, 17, 19, 21, 23.
$n = 4$: 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
$n = 5$: 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37.
$n = 6$: ?

I just started a course and I don't understand. I get the pattern differences and I understand all the patterns that are formed such as each outputs first number is a multiple of three and then the lists rise by two for each output given. When I put this down off of what I was given as a reference in the class it tells us to create an algorithm for this, but we have not been given but a few ways to do this so I tried:

$n^2-2\cdot0$ which would be $36-0=36$.
$n^2-2\cdot1$ which would be $36-2=34$.
$n^2-2\cdot2$ which would be $36-4=32$.
$n^2-2\cdot3$ which would be $36-6=30$.
$n^2-2\cdot4$ which would be $36-8=28$.
$n^2-2\cdot5$ which would be $36-10=26$.

So my outputs come out as 36, 34, 32, 30, 28, 26.
Is this correct? If not, where am I going wrong?


texts: How strong is a FSM with long enough(but not infinite) tape?

texts:
Like turing machine, but your tape is finite. To make a program valid it should have a limit result when the length of tape tends to infinity.

Whether the tape has two ends or is cyclic doesn't matter, for placing a special dot on cyclic tape is like a two-end tape, and running back at the end on a two-end tape makrs cyclic.

Also it can solve its own halting problem by testing the running time. The conflict program is invalid, it has no result limit.

What's more?


texts: Decidability of the halting problem on real-life finite computers given unlimited input

texts:
It has been my understanding that, technically, our computers are Finite State Machines.  And, since FSMs halt when they run out of input, the halting problem is technically solvable.  At some point, we must reach an identical state without consuming input if there is an infinite loop.

I also understand that doing this in practice would take far, far, far too long to be useful.  Thus, I have read over and over that, yes, technically the halting problem is solvable for real computers, but it doesn't matter, because we can't do it in practice.

However, in a real computer, while we have a finite (vast) set of states, isn't it the case that we don't have finite input?  Input can easily be generated from non-cyclical random events, such as random radioactive decay, or the motion of water in a stream.  Doesn't this mean that, in fact, our computers are not truly Finite State Machines, and that the Halting Problem is not merely practically unsolvable, but genuinely unsolvable?


texts: Is my reasoning wrong that $PSPACE$ should not equal $EXPTIME$?

texts:
It's impossible for a problem to require exponential space without being exponential-time.

Consider that if an $EXPSPACE~~complete$ problem can be solved in $2^n$ time. It will now fall into the class $EXPTIME$.
Then $EXPSPACE~~complete$ problems are in $EXP$ if they can be solved in $2^n$ time. This means they can reduce into $EXP~~complete$ problems and vice versa.

To me, this should be easy to write a proof that $EXPTIME$  = $EXPSPACE$.
My intuition tells me that if $Exptime$ = $Expspace$; then $PSPACE$ != $EXPTIME$,
Because $PSPACE$ already is not equal to $EXPSPACE$.
Question
As an amateur, what would make this reasoning be wrong or right?


texts: Is {a^i b^j c^k | i≤j or (k=j≤i)} context sensitive?

texts:
$$L = \{a^i b^j c^k \mid i \le j \text{ or } (j \le i \text{ and } j = k)\}$$

I think the given language is CSL as i can break this language like this

$$L = \{a^i b^j c^k \mid i \le j \text{ and } j = k\}
 \cup \{a^i b^j c^k \mid j \le i \text{ and } j = k\}
 \cup \{a^i b^j c^k \mid i \le j \text{ and } j \le i \text{ and } j = k\}$$

Last language i,j are independent, hence DCFL.

When we take union of these languages, we get CSL.

Is my approach right?


texts: Given n strings, is one of them a substring of another?

texts:
Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$.  I would like to know whether any of those strings is a substring of any other string in the collection.  In other words, I'd like an algorithm for the following task:

Input: $S_1,\dots,S_n$

Output: $i,j$ such that $S_i$ is a substring of $S_j$ and $i\ne j$, or None if no such $i,j$ exist

Is there an efficient algorithm for this?

If we replace "substring" with "prefix", there is an efficient algorithm (sort the strings, then do a linear scan to compare adjacent strings; sorting will ensure that substrings are adjacent).  But it seems more challenging to test whether any string is a substring of any other string.  A naive algorithm is to iterate over all pairs $i,j$, but this requires $\Theta(n^2)$ substring tests.  Is there a more efficient algorithm?

I guess we could call this "all-pairs substring testing", or something like that.

My ultimate goal is to prune the collection so no string is a substring of any other, by removing each one that is a substring of something else in the collection.


texts: Claimed problems with Lisp dynamic scoping

texts:
What would be the problem of running the following scala codes assuming we are working with dynamic scoping and a global stack to store environments as some variants of Lisp do?

def fact(n:Int,f:() => Int):Int =
 if(n == 0) f()
 else fact(n-1,() => n*f())
fact(7,() => 1)

def incrementer(x:Int)  = y => y+x
incrementer(2)(3)


texts:
So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear.

Now to go from that NFA to the complement of the NFA, since I can't just flip accept and reject states, this means turning the NFA into a DFA.

If $n$ is the number of states in the NFA, the DFA simulating the NFA can have $2^n$ states.

So would the process of regex to NFA to complement of the NFA be $O(2^n)$?

Trying to figure out what big-O notation it would be.


texts: How to devise an algorithm that suggests feasible cooking recipes?

texts:
I once had a veteran in my course that created an algorithm that would suggest cooking recipes. At first, all sort of crazy recipes would come out. Then, she would train the cooking algorithm with real recipes and eventually it would suggest very good ones.

I believe she used something related to Bayes Theorem or Clustering, but she is long gone and so is the algorithm. I have searched the internet but looking for cooking recipes will yield any sort of results but not the one I am looking for. So, my question is:

  What techniques can be used to devise an algorithm that (randomly) suggests feasible recipes (without using a database of fixed recipes)?

Why would I bother looking for a cooking algorithm? Well, it was a very good example of a real world application of the underlying concepts, and such algorithm could be useful in different settings that are closer to the real world.


texts: SSID evaluation within the 802.11 protocol

texts:
Inspired by a question on superuser, I was reading up on the 802.11 protocol. This made me wonder if the SSID is actively used outside the authentication and association process. I know that it can be included in beacon frames which will get evaluated after a connection between AP and client has been established. But since within beacon frames the SSID value is optional, it makes me think it does not get evaluated.
So my question is, will the SSID usually be evaluated during a connection between AP and client after the authentication and association process? Is this a required within the 802.11 protocol or is this up to the implementation?
I hope computer science is the right site to ask this question since I don't feel it belongs on Network Engineering because it's too theoretical.


texts: Data structure able to perform fast and simple updates

texts:
Let's say we want to build data structure able to perform two operations.

First one, query is asking for the sum of values in the range $[i, j]$. And the second one, the update is setting all values on the range $[i, j]$ to have value $1$. On the beginning all elements of the array are $0$.

What is the fastest data structure that we can build, not only in terms of big-O, but also in real performance.


texts: Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$

texts:
For the graph colourability problem, we are given a graph and our goal is to find a colouring of the graph with the fewest possible number of colours so that no two adjacent vertices have the same colour. This problem is known to be NP complete.

Suppose that we have an algorithm $A$ that runs in polynomial time and tells us whether our graph can be coloured by using $\leq k$ colours. We can query this algorithm as many times as we want.

Would this imply that the graph colourability problem also be in $P$?

My approach would be to begin querying for $k=1$, and then keep incrementing $k$ until we get a positive response from $A$, which is going to be the answer to our problem.

However, if we know how many colours we can use to colour our graph, how do we then actually colour each node? Is there a known algorithm for this?


texts: How precise is the statement "STLC is the internal language of CCCs"?

texts:
I'm studying some basic category theory in the context of type theory and came across the statement "simply typed lambda calculus is the internal language of cartesian closed categories". However terms and substitutions in the internal language of CCCs are the same data type, unlike in (traditional) STLC. Speaking in Agda, we have

π¹ : ∀ {Γ σ} -> Γ × σ ⊢ Γ
π² : ∀ {Γ σ} -> Γ × σ ⊢ σ
_[_] : ∀ {Γ Δ σ} -> Γ ⊢ σ -> Δ ⊢ Γ -> Δ ⊢ σ

where π¹ is supposed to be a substitution constructor and π² and _[_] are supposed to be term constructors.

This additional first-orderness allows to abstract over substitutions, so we can e.g. write (using de Bruijn indices)

I : ∀ {Γ σ} -> Γ ⊢ σ ⇒ σ
I = ƛ var 0

silly : ∀ {Γ Δ σ} -> Γ ⊢ Δ ⇒ σ ⇒ σ
silly = ƛ (I [ var 0 ])

I don't know what silly is, but it doesn't look like a regular lambda term to me.

So is the internal language of CCCs actually more expressive than STLC or am I misunderstanding something?


texts:
I took an algorithms class on Coursera. The professor in the video about hash tables said that

  What's true is that for non-pathological data, you will get constant time operations in a properly implemented hash table.

What does "non-pathological data" mean? Can you give some examples?


texts: Generate an AST from an indefinite grammar and logic

texts:
As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a developer in this case, because it would not be useful to a"normal" user) must write what it takes in a file for the program to get the necessary elements in order to be able to analyze and produce an AST from code (or other) written in the logic and grammar defined by the user.
I've already done AST for a predefined syntax and grammar, but now I don't see how I could do it...

Here is what a user-defined grammar and logic file might look like:

=== grammar ===

.number:
    | valid as <-(0-9)*> // Number between 0 and 9, positive or negative taken * times
.sign:
    | addition       '+' as <+>
    | substraction   '-' as <->
    | multiplication '*' as <*>
    | division       '/' as </>

=== logic ===

.CorrectFollowing:
    | follow [number; sign] with \ {[0]: sign; [-1]: sign} // Must strictly start with a number and end with a number with interval

=== program ===
.MyTest:
    | 4+2-1 // --> 5

As you can guess, this grammar and syntax form a simple calculator. We can see an example in the === program === .

I explain you quickly to put you in context:

In the part === grammar ===, we define 2 things :

1. number
2. sign

In these labels, we can find the definition of a token between two' and the name that accompanies it, so that we can identify it in the file (the names and tokens are chosen by the user). So here :

- valid (see explanation above)

- addition ('+')
- substraction ('-')
- multiplication ('*')
- division ('/')

From all this, the program must be able to analyze and produce an AST from a code following the syntax and grammar defined. So, here, === program === contains the example.

Here is what the AST of the program given in the last part of the code should look like:

     -
    / \
   +   1
  / \
 4   2

(The priority of the operations (must be) / is respected: the program identifies that it is indeed a calculation.)

The problem is, I don't have any ideas how to implement this (C++). I've already managed to segment the different labels in a std::map<std::string, std::vector<std::string>>, but for the rest...

PS: Sorry, I already asked this question in SO, but I was advised to go here. What I did.


texts: Why is this language over {a,b,c} regular?

texts:
The language of all words over the alphabet {a,b,c} such that

the number of as in the word
minus the number of cs in the word

is divisible by three.

How is this language regular? Lecturer notes says that it is, and then provides no explanation at all.
I tried drawing a DFA for it, but it just seems that the longer the word, the more states there will be and there could be an infinite amount, which is not allowed?
Please help, thanks.


texts: What Is The Appropriate Action To Take When You're Shortest Path Algorithm Finds A Negative Weight Cycle?

texts:
Typing out negative weight cycle again and again is kind of annoying, so for the rest of the question I'm going to abbreviate it to NWC.

I'm writing an optimized version of Bellman-Ford's Shortest Path Algorithm on a directed, weighted graph. When I give it a regular graph with no NWC's, it works fine, and finds the answer correctly. But when I give it a NWC, it loops forever. So, I put a system into the implementation where it finds out if there is a NWC, which it does correctly, but now I'm stuck on what to do once I find it.

My first thought was to just go on regularly while setting every vertex in the cycle to negative infinity, but every single vertex after that becomes negative infinity too, and soon enough, a huge chunk of the graph becomes negative infinity and I'm getting bugs left and right because I'm subtracting to negative infinity, adding to negative infinity, while also setting the distance to negative infinity. I technically could fix all the bugs, but then lot's of valuable information on the other vertices is lost because of one little NWC.

My next thought was to just terminate the program, but then again lot's of information is lost on the other vertices.

So,  what is the correct action to be taken when you find a NWC?


texts: Connection between probabilistic algorithm and distributional algorithm

texts:
A basic question about the connection between two notions. I am sure these are known notions in CS but I struggle with the basics:
First Definition:
A probabilistic algorithm $A(n)$ decides $L$ if for every $x \in L$, it holds that $\Pr(A(x) = 1) \geq 1 - \epsilon$, and for every $x \notin L, \Pr (A(x) = 0) \leq \delta$.
Second definition:
Given a language $L$ and a distribution $D$ on the instances of $L$, the algorithm $A$ decides $L$ with respect to $D$, if it holds that for every $x$ which is drawn from $D$, the above requirements hold ($\Pr(A(x) = 1)\geq ...$).
Clearly, the first notion is "stronger" in some sense: in the second definition, I may force the algorithm make as many mistakes as I want, by creating a different distribution on which he cannot handle.
My main question is the following:
If for a problem there exists an algorithm $A$ such that $A$ decides $L$ with respect to the uniform distribution, does it mean that $A$ decides $L$ for every input (with high probability)? I somewhat "feel" that uniform solving for a uniform distribution is harder, does this feeling correct?


texts: Given two sorted arrays check if one is subset of another

texts:
Question: Given two sorted arrays A1 and A2, check if A2 is a subset of A1. Also, assume there might be duplicates.
Example:
 A1 = [0,0,0,0,1], A2 = [0,1] // should return true
 A1 = [-1,0,1,2,3,4,5], A2 = [1,2,3] // should return true

Answer: My answer is below and works, but I believe my running time is slow. Not sure if there is another algorithm I can leverage.

FYI: this is not for school or project, just curious with solving problems.

function isSubArrayOfAnother(a1, a2) {
        if (!a1 || !a2 || a1.length === 0 || a2.length === 0) {
            return false;
        }

    let loc = a1.indexOf(a2[0]);
    let allIndexes = [];

    while(loc > -1) {
        allIndexes.push(loc);
        loc = a1.indexOf(a2[0], loc + 1);
    }

    for(var i=0; i<allIndexes.length; i++) {
        let isMatch = true;
        let tempIndex = allIndexes[i];
        for (var j = 0; j< a2.length; j++) {
            if (a2[j] !== a1[tempIndex++]) {
                isMatch = false;
                break;
            }
        }
        if (isMatch)
            return isMatch
    }
    return false;

}


texts: What complexity does this 'how many ways to climb' algorithm have?

texts:
I have a solution to the following problem:

  Given a stairway of $n$ stairs, which you can climb from $1$ to $m$ at the
  time ($1 \leq m \leq n$), return all the ways you can climb the stairway.

  E.g. for $n = 3$, $m = 2$, the possible ways to climb are $[2,1], [1,2], [1,1,1]$

// outputs all the ways to react total using steps from 1 to max;
// returns the count of iterations
function permut(total, max, out) {
  // store unfinished tracks; start with an initial track
  let iter = [{ val: [], sum: 0 }];
  let count = 0;

  // take the next track until there are none
  for (let i of iter) {
    for (let s = 1; s <= max; s++) {
      // append step value to the current track
      // assume constant complexity
      let val = [...i.val, s];
      let sum = i.sum + s;

      count++;

      if (sum === total) {
        // we've reached the top;
        // do not expand current track further
        out(val);
        break;
      }

      // add an unfinished track and start over
      iter.push({ val, sum });
    }
  }

  return count;
}

Codesandbox: https://codesandbox.io/s/busy-cdn-7idu9

However, I can't figure out the time complexity relatively to $m$ and $n$. For $m = 1$ the number of iterations is $n$, for $m = n$ it's $2^n - 1$.

Also, is there a canonical solution to this problem?


texts: Relationship between #of cores and Dynamic Power

texts: The book I'm currently reading specifies that Dynamic Power = (1/2) * Capacitive Load * (V^2) * frequency However, that is assuming it's a single-core system. I wonder if we're calculating the Dynamic Power of a dual-core system, would that be twice the formula of Dynamic Power above ?


texts: Calculating match % and ranking according to that

texts:
I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown top 5 matches along with their match percentages. If two users have 10 common questions and their answers match for 8 of those questions then their match % will be 80%.

I can make this but my concern is about efficiency. A way of making this: If a user wants to see his top matches then match % (or match ratio) will be calculated for him vs every other user in the system. This will be stored in a temporary array. Array is sorted. Top 5 matches from the array are displayed.

Any less resource intensive way to calculate and show top matches?

Edit: If the top matches can be calculated without first calculating match percentages then i'm open to that.


texts:
In the proof of existence of length preserving one way functions assuming the existence of one way functions, see

Length-preserving one-way functions

We need $p(n)$ to be a function which can not only be computed in polynomial time, but also, its inverse should be polynomial time computable. How do we ensure that ? $p(n)$ can be chosen to be monotonically increasing. But is that sufficient ?


texts:
When reading about data types, "type definition" is often used without any prior explanation to what it means.

For example, in https://en.wikipedia.org/wiki/Type_system, we have the sentence "...  since C++ has stronger rules regarding type definitions  ..."

Any help in clarifying what the difference between, for example, type and type definition is greatly appreciated!


texts: Efficiently computing minimal elements over partially ordered sets

texts:
I have a list of sets that I would like to sort into a partial order based on the subset relation.

In fact, I do not require the complete ordering, only the minimal elements.

If I am not mistaken, each minimal elements should define one separate component  of the respective graph - and this component should be a meet-semilattice.

What would be the most convenient space and time efficient way to solve this problem? Perhaps there is a way that does not require to build the entire graph? Perhaps there is a known algorithm under a better terminology than what I have naively described above?

I am aware that the time and space requirements are underspecified above, but I would be happy about any suggestions, whether they are proven to be optimal or not...

Background: I am currently building an entire graph database that holds all  the edges between the sets and then look for the nodes that have no generalizations, but this is quite complicated, slow and requires a lot of (disk) space. The list mentioned above contains roughly 100 million sets.


texts: how to cover a point matrix with right angle lines connecting each pair of dots

texts:
I'll describe the problem below, I'm not sure if it's an exist algorithm problem. The problem is from a small game.

Here is a matrix, probably with some cells blocked(couldn't pass through)
There are several pairs of numbered points
connect each pairs of points with right angle lines, the lines shouldn't intersect
lines and points should cover all available places

So, how to find out the solution if the solution exists? Here is an example image.

Problem:

One solution:

I'm not sure if it could be solved by any exist algorithm, so please tell me what algorithm I should use, or give me some hint to solve it. Runnable code would be better!


texts:
I am going through the following lecture notes by Frank Pfenning :

http://www.cs.cmu.edu/~fp/courses/15317-f17/lectures/02-natded.pdf

In page no 5 I cam across the introduction rule  .

The rule reads that $A$ is contained in $B$ if $B$ is true  under the assumption that  $A$ is true .

But in the text a subtle point about the beginning bar of the proof is mentioned which are a below in the images :

Why would it be incorrect to say that "The truth of A leads to the truth of B " . Even if the truth of A has been
introduced durng the process of proving the truth of B , it surely means that the truth of A leads to truth of B . As in
the graph or pictorial representation there are no other statement which are in conjuction with "A" anywhere .

What is the subtlety here in emphasing a misconception or a misleading picture obtained from omiting the bar ?

P.S : I did go through the following paragraphs illustrating the proof of a statement . This paragraph
emphasizes on some phenomenon called discharging of assumptions , which I feel would require a detail understanding
and might come up in the next question that I would be posting so as to gain a better understanding of the content .
But for the time being , I would try to understand the matter in this question with the hope that it might help while
understanding the following topics .


texts:
I'm constructing a deterministic finite automata (DFA) for a language of all strings defined over $\{0,1\}$ whose length is even and number of $1$s is odd. I constructed each DFA separately and then combined:

Is the given procedure for combining DFAs correct?
EDIT: Originally wrote union; actually taking the intersection.
Would someone suggest material on constructing DFAs
given restrictions on length and number of $0$s or $1$s?

According to link given by Merbs, I have developed this FA.   This FA does not accept a language of even length.


texts: How do processors fetch instructions that are longer than the word length?

texts: From what I have read, instructions under x86 can be as long as 15 bytes. Since x86 is a 32-bit architecture (64-bit for x86-64 obviously) how does it handle these long instructions? How are they stored in memory, and how are they fetched?


texts: Conversion of a YAML file to XLSX using Python

texts:
I want to convert a set of yaml files in a folder into an xlsx file. I thought I'd start with trying to convert one yaml file into an xlsx file. The yaml files in the folder are all in the format given below:
info:
    city: Bangalore
    competition: IPL
    dates:
       - 2008-04-18
    gender: male
    match_type: T20
    outcome:
           by:
              runs: 140
           winner: Kolkata Knight Riders
    overs: 20
    player_of_match:
        - BB McCullum
    teams:
        - Royal Challengers Bangalore
        - Kolkata Knight Riders
    toss:
        decision: field
    winner: Royal Challengers Bangalore
    umpires:
        - Asad Rauf
        - RE Koertzen
    venue: M Chinnaswamy Stadium
    innings:
        - 1st innings:
        team: Kolkata Knight Riders
        deliveries:
                     - 0.1:
                           batsman: SC Ganguly
                           bowler: P Kumar
                           extras:
                                  legbyes: 1
                           non_striker: BB McCullum
                           runs:
                                batsman: 0
                                extras: 1
                           total: 1

The data continues for each ball of the match (0.2, 0.3, 0.4 ... 20.0) and shifts to the second half of the game (second innings) and continues further
My attempt at converting one of these yaml file into an xlsx file:
import pandas as pd
import yaml as ya
with open(r"location of folder") as f:

    data = ya.load(f, Loader=ya.FullLoader)
    df1=pd.DataFrame(data['info'])
    df1.to_excel(r"location of folder\output.xlsx")

However, after running the above code, I got the following errors:
File "c:\Users\kosal\hello\prj.py", line 8, in <module>
    df1=pd.DataFrame(data['info'])
  File "C:\Users\kosal\anaconda3\lib\site-packages\pandas\core\frame.py", line 529, in __init__
    mgr = init_dict(data, index, columns, dtype=dtype)
  File "C:\Users\kosal\anaconda3\lib\site-packages\pandas\core\internals\construction.py", line 287, in init_dict
    return arrays_to_mgr(arrays, data_names, index, columns, dtype=dtype)
  File "C:\Users\kosal\anaconda3\lib\site-packages\pandas\core\internals\construction.py", line 80, in arrays_to_mgr
    index = extract_index(arrays)
  File "C:\Users\kosal\anaconda3\lib\site-packages\pandas\core\internals\construction.py", line 401, in extract_index
    raise ValueError("arrays must all be same length")

I do realize why this error is coming up but I have no idea as to how I should go about fixing it.
P.S. I can't find an appropriate tag for this question and hence have used the 'python' tag.


texts: Accuracy and performance between a division and subtraction for a ratio in decibels

texts:
For comparing two images, one can use the Peak Signal-to-Noise Ratio (PSNR) metric, defined as follows:

$\mathrm{PSNR} = 10 \cdot \log_{10}\left(\frac{\mathrm{MAX}^2}{\mathrm{MSE}}\right) = 20 \cdot \log_{10}(\mathrm{MAX}) - 10 \cdot \log_{10}(\mathrm{MSE})\ dB.$

with $\mathrm{MAX}$ being the maximum gray-scale value ($2^8-1 = 255$ in my case), and $\mathrm{MSE}$ being the mean squared error.

My question is, among the definition with division ($\mathrm{PSNR}_{\div}$) and subtraction ($\mathrm{PSNR}_{-}$), which one is the most numerically accurate? And which one is the most computationally efficient?

I made an experiment with MATLAB R2015a, and for some MSE values, I have different scores. For instance, knowing that the machine epsilon is $\epsilon = 2.2204e{-16}$, for $\mathrm{MSE} = 1708.25$ and $\mathrm{MSE} = 1710.00$, I have $\left| \mathrm{PSNR}_{\div} - \mathrm{PSNR}_{-} \right| = 1.42109e-14$ and $7.10543e-15$ respectively. What can I conclude?

Note: in $\mathrm{PSNR}_{-}$, $20 \cdot \log_{10}(\mathrm{MAX})$ can be reduced to a pre-computed constant.


texts: What language features would I need to remove from a real programming language to make it decidable?

texts:
Let's say that I want to restrict certain features of a common programming language--for instance, C--such that the result is decidable, and thus no longer Turing-complete.  What language features, at minimum, would I need to remove to make a given programming language decidable?

For the purpose of this question, let's assume the following:

The original language in question is imperative.
We're not restricting memory in any meaningful way.
The result isn't hideously crippled (e.g. no subsets of C that only consist of printf calls).


texts:
In my computability class we were given a practice final to go over and I'm really struggling with one of the questions on it.

Prove the following statement:
If $L_1$ is a regular language, then so is
$L_2 = \{ uv |$ $u$ is in $L_1$ or $v$ is in $L_1 \}$.

You can't use the pumping lemma for regular languages (I think), so how would you go about this? I'm inclined to believe that it's false because if $u$ is in $L_1$, what if $v$ is non-regular? Then it would be impossible to write a regular expression for it. The question is out of 5 marks though and that doesn't seem like enough of an answer for it.


texts: RC-Code if I have a generator matrix for a specific code how do I get the distance to the dual code?

texts:
$\mathcal{R} \mathcal{S}_{6, 3}$ and $a_{i} \in \mathbb{F}_{11}$
G=\begin{pmatrix}1&1&1 &1&1&1\\ 0&1&2 &3&4&5\\ 0&1^2&2^2 &3^2&4^2&5^2 \end{pmatrix}
G=\begin{pmatrix}
1&1&1 &1&1&1\\0&1&2 &3&4&5\\ 0&1&4 &9&5&3 \end{pmatrix}
I now have to determine the distance to the dual code.
Any clue how to accomplish this?
Thanks for any help.


texts: Convert $1.75\times10^{15}$ to IEEE-32 format?

texts:
$1.75\times10^{15}$

I know how to convert decimal to binary

$(1.75)_{10}$ is equal to $(1.11)_2$

But to represent $10^{15}$ is the main problem for me. I can solve the question but this is the point where I got stuck.
How can I represent $10^{15}$ in base 2 ?


texts:
I am implementing the Christofides algorithm for TSP problem and currently I have one issue with the MST result. Let's assume that I have one graph $G$, whereas I can get $MST_1$ and $MST_2$ where both are Minimum Spanning Trees, because $G$ contains more than one edge with the same weight.

In image [2] below, the difference between $MST_1$ and $MST_2$ is basically the $Arlington \to Somerville$ or $Arlington \to Belmont$ (or vice-versa) connection. Depending on the internal representation of the graph, whether a adjacency matrix or list, this could happen by just altering which node will be the first, e.g. if $Arlington$ will be processed earlier than $Somerville$.

The difference of dealing with one or the other, is the next steps of Christofides algorithm, that requires to apply the Minimum-Weight Perfect Matching algorithm on the odd nodes.

The $MST_1$ has only $4$ odd nodes and the perfect matching result is $Arlington \to Medford$ and $Cambridge \to Everett$, which I will call $MWPF_1$.
The $MST_2$ has $6$ nodes and the perfect matching result is $Arlington \to Medford$, $Somerville \to Everett$ and $Belmont \to Cambridge$, which I will call $MWPF_2$.

The next step from Christofides is to merge both edges from $MST$ with the ones from perfect matching.

Now, if we choose to merge both $MST_1$ and $MWPF_1$, we will end up with nodes only with even degrees that's what we want as the next step is to calculate the Eulerian Circuit.

But, if we choose $MST_2$ and $MWPF_2$, we will end up with only one new edge, as other two are already present ($Somerville \to Everett$ and $Belmont \to Cambridge$) in $MST_2$.
The result then will be $4$ odd vertices and no possible Eulerian Circuit can be generated out of this merge!

How this should be dealt in Christofides algorithm? Should all the $MSTs$ generated from one graph to be tried out?


texts:
It might be a very basic question.$\\$
I am considering the SVM optimization problem here.$\\$
In a training set where the data is linearly separable, and we are using a hard margin (no slack allowed), the support vectors lie along the supporting hyperplanes but is the inverse true that all points lying along the supporting hyperplanes are support vectors?


texts: Designing a PDA w/o $\epsilon$-moves and $\leq 2$ states to accept an $\epsilon$-free CFL by final state

texts:
I understand that any CFL can be accepted by a PDA by final state or empty store but I have been rather stumped by this question.
The question states that the PDA has at most 2 states. Clearly 1 will be the start state while the other will be the final state (they cannot be the same since otherwise the empty string will be accepted). My initial idea was to take a grammar for $L$ in GNF (Greibach Normal Form) (refer to Ran's answer below for details on how a CFG in GNF can be converted to a PDA having 1 state and no $\epsilon$-transitions that accepts by empty store) and then give a PDA for this that meets the specification. But the problem is that I cannot find a way to do this without having an $\epsilon$-move at the final step when I have to move to the final state after the stack is empty. Any help would be greatly appreciated.

The PDA can be specified as $M = (K, \Sigma,\delta, q_0, Z_0, \{q_f\} )$ where
$q_0$ is the initial state, $Z_0$ is the initial stack symbol and $q_f$ is the final state. The exact question is

  Show that if $L$ is a CFL and $\epsilon$ does not belong to $L$, then there is a PDA $M$ accepting $L$ by final state such that $M$ has at most 2 states and makes no $\epsilon$-moves.

Thus, the PDA should

accept by final state
have at most 2 states
make no $\epsilon$-moves


texts: Interval Scheduling Problem with more than One Resource

texts:
Consider the interval scheduling problem, see also here.

In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest finish time, choose the next compatible one, and so on.

Now, let us say we have two resources instead of one. How do I schedule my jobs now? As my idea goes, again you start by sorting the requests in order of finish time. My problem is, how do I proceed after that? Do I choose the resources in sequential or in an alternate fashion?

If I go for sequential manner, I schedule all the possible jobs in the first resource and then do the same for second resource with the jobs yet to be scheduled.

If I go for alternate fashion, I choose the first possible job in the first resource, then second possible job in the second resource and so on.

In each case we will have take in to account the chosen jobs being compatible, needless to say.

I can not decide which of these is going to be optimal.

Any input will be appreciated.


texts: Designing of reliable multicast algorithm, regarding validity, can you deliver before multicasting

texts: As the title says, if an algorithm delivers $m$ before multicasting $m$, does the validity property still hold? I would argue that it doesn't matter, as the purpose of validity is to ensure that the process reaches consensus with the other processes that it multicasts to.


texts: What if traversal order of two of pre-order, in-order and post-order is same?

texts:
Supposing a tree T has the identical:

Pre-order traversal and in-order traversal
Pre-order traversal and post-order traversal
In-order traversal and post-order traversal

How does T look like?

From the previous discussion in SO, I learned that pre- and post-order are same iff. only one node is in the T.

How about the left two conditions?

I suppose that only purely left-skewed tree can make post- and in-order the same, and only right-skewed tree can make pre- and in-order the same.

Am I on the right way?

Edit: To avoid being solely a 'yes' or 'no' problem, the actual doubt is that how to prove this statement, but I have a idea about the proofs using contradiction. So maybe this problem is a little redundant.


texts: Understanding definition of NP and co-NP

texts:
From some of the texts I read, one definition of NP is: "An equivalent definition of NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." and that we have the following, where $n$ is the length of the input:

$$
\text{NP}=\bigcup \text{NTIME}(n^k)
$$

This means that one way a  problem can be shown to be $\in \text{NP}$ is if we can construct a non-deterministic TM $N$ using a polynomial time verifier $V$ on a certificate $C$, or:

TM $N$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$, accept

But if I use the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$, wouldn't this imply that $\text{co-NP} \subseteq \text{NP}$, since I can construct a TM $N'$ that can recognize co-NP:

TM $N'$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$ for any branch, reject
3. if all branches reject the guessed certificates, accept

In this case, since all branches of $N'$operate in polynomial time, $N'$ should also be able to solve problems for co-NP in non-deterministic polynomial time.

But since it is not yet sure if NP=co-NP, how should I understand the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$?


texts: I have a question about simplifying O-notation. Specifically, why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$ where $t(n)$ is the running time of an algorithm?


texts: Suggestions for Short Examples Contrasting Functional Programming Languages

texts:
A fellow student and I are writing a paper on functional programming for a programming languages course, part of which will be comparing and contrasting Lisp (Scheme), ML (SML), and Haskell. We'll be coding the same algorithm in each language and we're at a bit of a loss for exactly what to code. We would be grateful for some suggestions for algorithms that fit the bill (described below). We'll work out the code---we're just looking for suggestions. But if there's a particular tricky point or useful idiom we'd welcome a heads-up.

We envision the code being about a page. In particular, the professor wants something more substantial than a line or two. To the degree possible, we'd like to use this to contrast the styles of the three languages and at the same time showcase the benefits of functional programming. I considered quicksort, but the standard Haskell code is just a line or two.

I would have tagged this with "homework" and "soft question" (as well as "ML" and "Haskell"), but those tags don't seem to exist. Also, I wasn't sure whether Computer Science or Stack Overflow was the right place for this, but decided on Computer Science because we're not really looking for worked-out code or solutions to a particular coding problem. Instead we're looking to demonstrate the benefits of the functional programming paradigm and three important branches thereof.


texts: Flaw with Knuth original attribute grammar paper

texts:
Knuth's original attribute grammar paper (title: Semantics of Context-Free Languages) apparently had a flaw where circularity is always detected but
some noncircular AGs may be reported to be circular. Knuth later constructed
an exact algorithm which is exponential in time. I am wondering what was the fix? which part of the algorithm was the source of the problem?


texts: How do you prove that this tree path calculation function works, from first principles mathematically?

texts:
I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the array size, and chunk size (don't even need to use the tree itself!):
const data = [
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 105, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
 1, 2, 3, 4, 5, 6, 7, 8, 9, 0
]

const tree = divide(data, 5)
assert(tree, walk(5, 100, 42), 3)
assert(tree, walk(5, 100, 44), 105)

function assert(tree, path, value) {
  let drill = tree;
  while (path.length) {
    drill = drill[path.shift()]
  }
  if (drill !== value) {
    throw new Error(`${drill} != ${value}`)
  }
  console.log('It matches', value)
}

function walk(chunkSize, dataSize, index) {
  let depth = Math.floor(Math.log(dataSize - 1) / Math.log(chunkSize)) + 1
  let path = []
  let i = 0
  while (i < depth) {
    path.unshift(index % chunkSize)
    index = Math.floor(index / chunkSize)
    i++
  }
  return path
}

function divide(data, size) {
  if (data.length <= size) return data
  const result = []
  for (let i = 0; i < data.length; i += size) {
    result.push(data.slice(i, i + size))
  }
  return divide(result, size)
}

How can you prove, mathematically, that this is the solution to the problem? That walk will give you a path to the corresponding index in the tree? How do you show from first principles mathematically that this is how it works? To me this is just pure magic, I don't see how anyone could have figured this out other than through brute force and then just memorizing the answer haha.


texts: What is implied probability, in the context of universal codes?

texts:
From Wikipedia:

  Each universal code, like each other self-delimiting (prefix) binary
   code, has its own "implied probability distribution" given by $ p(i)
 ={2}^{-\ell(i)} $  where $\ell(i)$ is the length of the $i$th codeword and $p(i)$ is the corresponding symbol's probability

What is "implied probability"?

Given that prefix code are not fix-length codes, then I don't get what "implied probability" means, for example, given a 3 bits length code, implied probability is ${2}^{-3} = \frac{1}{8}$ but what does it mean? is it about choosing the code between others? or choosing random between all possible of three bits? as here we are talking about prefix codes, so length will vary among codes, so there could be only one code of three bits, so probability of get it would be 1? Any clarification will help!


texts: Suggest a Data Structure To Manage 2 Sets

texts:
I was given the following problem which really baffled me, and I would like some guidance in solving it.

I want to make a data-structure which represents two sets $A,B\subseteq \mathbb{R}$, so that I can Insert an element to a set of my choosing in $O(\log n)$ (where $n$ is the number of elements existing in both sets).

However, it is also required to be able to find in $O(1)$ some $x \in A\cup B$ such that the amount of elements in $A$ lesser than $x$, equates to the number of elements in $B$ greater than $x$, if exists:

$$\left | \left \{ y\in A: y<x \right \} \right | = \left | \left \{ y\in B: y>x \right \} \right |$$

Now the obvious direction is to use balanced trees (say AVL). I can use the same tree for both sets or separate to 2 different trees. I also presume I should store more data in the nodes, However I'm not sure which. I thought about storing the number of elements smaller and greater but that would make the Insert method $O(n)$, since I have to update many nodes in the respective tree.


texts: What is the number of expressions containing n pairs of matching brackets with nesting limit?

texts:
I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching brackets such that no more than $l$ open brackets are not closed at any given point?

For instance, for $n=3$ and $l=2$ the answer is $4$. All possible combinations are $(())()$, $()(())$, $()()()$, $(()())$. We cannot have $((()))$ since there are three open brackets that are not closed at the middle.


texts:
I have a list of nodes l = [1, 2, 3, ... , n] and a list of tuples p = [(1, 2), (2, 3), ...], where the latter represents which pairs of nodes have an edge between them.

I would like to write a function that takes the above as input and returns a subset of the powerset of l where each set has nodes which construct a complete graph based on p (sans the empty set).

For example, suppose I have l = [1, 2, 3] and p = [(1, 2), (2, 3)]. Then the output of this function would be [(1), (2), (3), (1, 2), (2, 3)].

What would be the most efficient way of implementing this function?


texts: Why operating system needs interrupt stack, if it has process control block?

texts:
I'm reading about an operating system but some concept confuses me.

What doesn't confuse me:

When an interrupt or system call or processor exception occurs, it happens when user mode tries to switch to the kernel mode, the operating system uses PCB(process control block) to save needed stuff, namely - hardware completing previous instructions, saves program counter, stack pointer, registers, changes execution state and so on. For each process has a separate process control block. This seems logical.

What confuses me:

But after several subchapters, I've read that interrupt or system call or processor exception occurs, an operating system needs to save some information - program counter, stack pointer, registers, execution state and so on. But this time saves not in PCB, it saves in "interrupt stack". It also said for each process needs the separate location of "kernel stack".

After that appears a few questions:

Is "interrupt stack" and "kernel    stack" the same thing, just
different named?
If the operating system already has PCB, why it needs to use "kernel
stack. Yes, for each process operating system has separate PCB. And
the separate location for each process in kernel stack.
Does the operating system use both kernel stack and PCB? If it does,
why not just one of these?
What difference between PCB and kernel stack, if they are used for the
same tasks

P.S Operating System Principles and Practice


texts:
I came across some code today for converting binary to decimal, and I realised that I don't fully understand how it works.

Here it is in Python:

#Binary to denary conversion
binary = input("Input a number in binary:")
denary = 0
for digit in binary:
  # A left shift in binary means x2
  denary = denary * 2 + int(digit)
print("Your denary number is: " + str(denary))

To help myself understand it I tried "converting" from base 10 to base 10. E.g.

For 246:

d = 0
d *= 10, d += 2, d = 2
d *= 10, d += 4, d = 24
d *= 10, d += 6, d= 246

I'm having trouble seeing how this works for binary to decimal though. Could someone please give me a clear explanation that's thorough and easy to follow?


texts:
Let $G(V, E)$ be an undirected weighted (positive) graph. Given a path $s-t$ find the path that minimizes the maximum weight of any of its edges. This is the minimax path problem.

It is know that a minimum spanning tree $T$ of $G$ gives a minimax path between every pair of nodes. After calculating the MST I want to be able to query any pair of nodes and get the "heaviest" edge of the path in the tree. Ideally I would like to preprocess the MST in linear time and query in constant time.

Wikipedia provide a $O(1)$ lookup with Cartesian trees (preprocess in linear time) and lowest common ancestor but I don't understand it.

Any ideas?