texts: How to make an unambigous grammar of a programming language

texts:
We know that the decision problem of whether an arbitrary context-free grammar is ambiguous is undecidable. My question is how are made the unambigous grammar of programming language? My guessing is that maybe starting from a simple grammar, which is easy to prove that is not ambigous, then adding some rules for which the new grammar is also not ambiugous, of course there must be some theorems which say what kind of rules can be added.
If my guessing is correct I would like to know that theorems.


texts: I cannot find an invariant for the following program

texts:
I have the following:

(|$y=0; x=c$|) while(x > 0){y=y+a; x=x-1;} (|$y= a*c$|)

This seems like a fairly simple program and I can intuitively tell that the post condition $y=a*c$ is true when the loop terminates, but I cannot a find a good invariant. Of course, I think I can say the variable $a$  is an invariant, but I don't think that it would prove the partial correctness of this program.

Any help is greatly appreciated.


texts: Configuration space for multi robot system

texts:
I have a problem that I think can be casted in the following way.

Suppose I have a simple closed polygon $\mathcal{P}$ and $n$ squares (bounding boxes) $\mathcal{B}_1, \ldots, \mathcal{B}_n$, you can think of these bounding boxes as robot who can move in the interior of the polygon. Each box $\mathcal{B}_i$ lies inside $\mathcal{P}$, they can both rotate and traslate (so they have free parameters $x_i, y_i, \theta_i$, also assume there's at least one choice of the parameters $x_1,y_i,\theta_1,\ldots, x_n,y_n,\theta_n$ such that $\mathcal{B}_i \cap \mathcal{B}_j = \emptyset$ for each $i \neq j$.

My problem would be to find/describe all possible configurations such that this is true they never intersect.

The closest thing I managed to find is the computation of the configuration space, but I only have a reference for a single robot.

Is there any algorithm or library that would allow given the polygon and all the free robots to compute the configuration space?

PS. I'm assuming the interior of the polygon is a subset of $\mathbb{E}^2$, and $\mathcal{P}$ isn't necesserely convex.

What I'm asking is either some known algorithm to do this or a free library that can compute this for me. Or alternatively I can reuse the single robot case to compute the configuration space of the whole system (because I would assume this is possible).

Also I'm not interested in the path planning, but just the configuration space.

My current statement of the problem is the following I want to find a representation of the polytope

$$
\mathcal{C} = \left\{(x_1,y_1,\theta_1, \ldots, x_n, y_n, \theta_n) : \mathcal{B}_i(x_i,y_i,\theta_i) \subset \mathcal{P}^\circ, i =1,\ldots,n, \;\mathcal{B}_i(x_i,y_i,\theta_i) \cap \mathcal{B}_j(x_j,y_j,\theta_j) = \emptyset, 1 \leq i < j \leq n \right\}
$$

Which, I think, can be factored as

$$
\mathcal{C} = \left( \prod_{i=1}^n \left\{ (x_i,y_i,\theta_i) : \mathcal{B}_i(x_i,y_i,\theta_i) \subset \mathcal{P}^\circ \right\} \right) \cap
\left( \bigcap_{1 \leq i < j \leq n} \left\{ (x_1,y_1,\theta_1, \ldots, x_n, y_n, \theta_n) : \mathcal{B}_i(x_i,y_i,\theta_i) \cap \mathcal{B}_j(x_j,y_j,\theta_j) = \emptyset \right\} \right)
$$

Which means the problem can be decomposed into classic configuration space computation, the only set I'm not entirely sure of is

$$
\left\{ (x_1,y_1,\theta_1, \ldots, x_n, y_n, \theta_n) : \mathcal{B}_i(x_i,y_i,\theta_i) \cap \mathcal{B}_j(x_j,y_j,\theta_j) = \emptyset \right\}
$$

Which resemble to me the computation of a configuration space with a robot and an obstacle, however the obstacle can freely move around so I'm not sure how to compute the configuration space in this case.


texts: Clarification on Solving Recurrence Relations (Linear)

texts: I'm trying to understand how to find the asymptotic complexity of a linear recurrence relation. So far, what I understand is that if only one linear recurrence call is made (ex. cn + T(n-4)), substitution or the recurrence tree can be used. However, what should one do if there are 2 or more linear recurrence calls? For the example I got in class (shown below), I got that T(n) = T(n-4) + logn + T(n-10). I tried setting a lower bound of T(n)> log n + 2T(n-10) since that's how we solved Fibbonacci Numbers, but I wound up with a complex summation that I could not solve. Any help is appreciated, thank you!


texts: BST - Sufficient condition for connecting a node to a parent

texts:
Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree.

I want to prove that if I insert a node X into the tree and node X is greater than node Y and less than the successor of node Y then X will be added as the right child of Y.

Intuitively, this makes sense to me but my question is how do we prove this formally?


texts: Is it possible to reduce the cost based rule further by applying a heuristic rule?

texts:
How can the Cost-Based Approach:

Linear search on a heap file that has
no index
Binary search on a sorted file that
has no index
Equality search on an attribute that
has a hash index
Equality search on an indexed
primary key
Inequality search on an indexed
primary key
Equality search on an indexed
(clustered) non-primary key
Equality search on an indexed (nonclustered) non-primary key
Inequality search on an indexed (B+
Tree) non-primary key

be combined with different transformation rule of heuristic to reduce the workload in DBMS?


texts: Two criteria for an edge to belong to all MSTs

texts:
Let $G$ be a connected undirected graph, with integral positive weights on the edges, and let $e_1$ be an edge of $G$. As part of an assignment I proved the following Lemma 1:

  The edge $e_1$ appears in any MST of $G$ iff $e_1$ is a light edge in any cut $C$ that it crosses.

Is it equivalent to the following Lemma 2?

  An edge $ = (, )$ appears in all MSTs of $$ iff every cycle including $$ has an edge $′$ with $() < (')$.

The latest is clearly a negation of the red rule for MSTs.
I think they are equivalent but can't prove it.


texts: Let's say I have a decision problem  $P$ on graphs for which I know that it is NP-hard on graphs with maximum degree $d$. Does this then imply that it is NP-hard on $d$-regular graphs? Although it might seem obviously true, maybe it is inherent in the reduction to show that $P$ is hard, that some vertices have degree less than $d$.


texts: Ordering the tasks to minimize penalties

texts:
So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows:

In your calendar you have an $L$ list of all the tasks you need to complete today. For each task $i \in L$ the duration $d_i \in \mathbb{N}$ is specified which indicates the time required to complete it and a penalty factor $p_i \in \mathbb{Z^+}$ which aggravates the delay. You must determine in what order to perform all the tasks to get the result that accumulates less total penalty.
Note that:
• In an instant you can only perform one task,
• Once you start a task, you must continue it until it is completed, and
• All tasks must be completed.
The actual penalty associated with a task $i \in L$ is the completion time $t_i$ of its completion, multiplied by its penalty $p_i$.
The completion time $t_i$ corresponds to the time elapsed from the start of the working day (i.e. from time instant 0) to the time the task has been completed.
Provide an algorithm (as efficient as you can) to solve it.

I have figured out that the completion of a task $i ∈ L$ with completion time $t_i$ must
started at instant $t_i - d_i$.
I'm stuck with the optimization criteria. I tried sorting the tasks by $p_i$ decreasingly, or by $p_i * d_i$ increasingly and doing the tasks in such order, but it doesn't work. I can find a counter-example for both approaches. What would be a good optimization criteria for this problem?


texts: Showing a language is a subset of another language?

texts:
I'm actually trying to give an example of a language being context-free and its superset that isn't context-free. I came up with this, but I'm not sure if this particular language is a superset of the other.

Let A be a context-free language. A = {a^n b^n | n >= 0}.

Let B be a non context-free language. B = {a^n b^n c^n | n >= 0}.

What I'm not sure of is if A is a subset of B. I saw something regarding proving if a regular language is a subset of another regular language, but I don't know if it applies to this situation.

Can someone provide some clarity on this, please?


texts: Prove that $L_1 = \{\, 0^m 1^k 2^n \,\vert\, \lvert m - n \rvert = k \,\}$ is not regular using Pumping lemma

texts:
I have been trying to understand Pumping lemmas for a while now, I am doing this exercise and I think that the pin has finally dropped. However, I am unsure if I am doing it even remotely correctly. I will briefly explain my attempt and thus my solution. Thereafter I would discuss a few points that are not as clear to me just yet. The exercise is the same as in the title. Here is my solution, but in-case you have forgotten:

Prove that $L_1 = \left\{\, 0^m 1^k 2^n \,\vert\, \lvert m - n \rvert = k \,\right\}$ is not regular using Pumping lemma

So, in order to show that a language is not regular, we first must assume it to be regular (in-order to be able to use pumping lemma). If $L_1$ is regular, then there exists a constant $n$ such that  $ s \in L_1 $  and $ |s| \ge n$ implies that there is a string $xyz$ satisfying

$s = xyz$
$ |y| \ge 1 $ and $ |xy| \le n $
$xy^iz \in L1 $ for all $ i \ge 0 $

We'll try to extract a contradiction. This is how I did it
I first create a string such that $ m + k = n $, my string was $0^1 1^1 2^2$ or just $0 1 2 2 $ I then split this string into three parts $ x y z $ so that $x = 0 \\ y = 1 \\ z = 22$

I then selected $ i \Rightarrow 2 $ which gives us , by the third rule, $ xy^2z  $. This gives us the string
$ 01122 \notin L1 $ because $1 + 2 \neq 2 $

That is my solution, I hope you could understand it. Now to my discussion points:
As you see, I have provided a contradiction,  which should be enough. However, what I also want to know is that in other exercises , say $\{\, a^n b^n \,|\, n \ge 1 \,\}$ you select a Pumping length $P$ and then typically get a string that is $a^p b^p$ i.e say that $ P = 3 $ you'd get $aaabbb $  AND then you divide into strings, but since the powers are all different in my exercise, picking a $P$ would not be as helpful, right?

Is it possible to select a Pumping length $P$ here too? Do I need to check the other conditions as well? As I understand it, a language is proven non-regular if it can't satisfy all of the requirements at the same time.

To clarify the question, when I meant 'how do I apply $P$'? I meant, how do I apply to the already existing powers ($m$, $k$ and $n$). Do I simply attach P to each power which would make it $ 0^{PM} 1^{PK} 2^{PN} $ ? A follow-up question: When I select $P$, must I then also select $M$, $K$ and $N$? So say I select $ P = 3 $ , should I also select $M = 1$, $K = 1$ and $N = 2$?

Thanks to the guy down under I know understand how to select a string ($ 0^p 1^p 2^2p $) for instance. But, then I don't know how to split the string. Can do it like this:

$x= 0^r$ , $y=0^{p-r}1^t$ and $z = 1^{p-t}2^{2p} $? Would this string be in the language ? I assume it would be as $xyz = 0^p 1^p 2^{2p} $ BUT Idk, I might be doing it all wrong

Then if I select $i = 2$ so $xy^2z$ I would get $xy^2z = 0^r 0^{2p-2r} 1^{2t} 1^{p-t}2^{2p} = 0^{2p-r}1^{p + t}2^{2p} \notin L$ Thus our contradiction, is this correct thinking then?

To answer the guy below:
Assume $L$ is regular, then there exist a constant $p$ such that $ s \in L$ and $|s| \ge p$ implies that there exist string $xyz$ satisfying following:
$1) s = xyz$
$2) |y| \ge 1$ and $|xy| \le p $
$3) xy^iz \in L$ for very $i \ge 0$

(Which answers your first question)
We pick our string $s = o^p 1^p 2^{2p}$ as the property of a string in a language must be $m + k = n  $ $  (p + p = 2p)$
We then split the string into three parts $xyz$ , I am going to split them differently to you. $x = 0^p$ $ y = 1^p $ and $z = 2^{2p} $ if we then select $ i = 2$ we get  $xy^2z = 0^p 1^{2p} 2^{2p} \notin L $ BECAUSE $ 1 + 2 \neq 2$


texts: Why is software emulation of alternative architectures so hard/slow?

texts:
I recall hearing briefly about this back in one of my CS courses on hardware, but I can't recall many of the details, nor can I find anything online that talks about it. A search on Google only yields a bunch of pages about Android emulators and people complaining that PCSX2 is slow. I'd like to know, in general, why software emulation of hardware is inefficient.

Can anybody point me to a good resource or explain briefly here?


texts: Get a fixed-size family of k-element subsets

texts:
I have an n-element set, and I want to consider families of its k-element subsets of fixed size s. For example, if n = 3, k = 1, s = 2, we have these families:

{{1}, {2}}, {{1}, {3}}, {{2}, {3}}

In my problem n, k, s are not so small, e.g. s = n = 50, k = 20.

Let us say all such families are ordered lexicographically (or really in any clearly stated order). I want to have an efficient way to get a family by its number.

I have only a following idea: enumerate all k-element subsets of n-element set (there is an efficient algorithm to get i-th element by i). Then enumerate all s-element subsets of comb(n, k)-element set, using the same operation. Now we need to generate a number in range (0, comb(comb(n, k), s)) and turn it firstly to the number of s-element subset and then to a family of k-elements sets.

However, I want to know, if there is a more beautiful approach than just generating first combination and then second combination by its numbers.


texts: Classification when some classes are dependent

texts:
I think my problem can easier be explained via an example: Assume we have a dataset containing the images of 10 different mammals, let's say lion, elephant, cat, ... and horse. We have a 20-class image classification task where we want to detect whether an image belongs to lion-male or lion-female or cat-male or cat-female or ... horse-male or horse-female. As you see, the classes can be simply clustered into 10 mammal classes, i.e., (some) classes are highly dependent.

This example is a kind of made up. Two strategies, imaginable to solve this problem is either we ignore this dependency and treat it as a 20-class classification task or use a hierarchical structure to first classify them into 10 class of mammals and then into male or female. The later however, ignores the fact that there might be (and in fact is) some shared properties in all males or in all females that can be used to discriminate them.

I was wondering if there is a methodological way to address this type of classification tasks. I'm looking for a keyword to google it.
Thanks


texts: Proof of NP-completeness of graph isomorphism through edge contractions that reduce a metric

texts:
Duplicate:
  NP-completeness of graph isomorphism through edge contractions with an edge validity condition

I know that graph contractability is $NP$-complete. To be specific given $G=(V_1,E_1)$ and $H=(V_2,E_2)$, can a graph isomorphic to H be obtained from G by a sequence of edge contractions ?

However my problem is a little bit different from the traditional graph contractability. In the traditional graph contractability problem we contract the original graph by different sequences of edge mergings. However in my problem each node is associated with some metric. At each step only a subset of edges are candidates for contracting or merging. Contracting one edge may affect the subset of edges that are legal for contracting at next step. By contracting one edge, we also replace the metrics of the two endpoint nodes with a new smaller metric. We are trying to find an H such that the sum of the metrics of nodes in H is minimal.

Any hint on whether this problem is $NP$-hard($NP$-complete) or not. If so any hint on how to prove it ?

Here are more descriptions: Each node has a 0/1-string label. We define a function to measure the similarity between two labels of the adjacent nodes(i.e. the length of the common prefix of the two labels). At each step only the two adjacent nodes with maximal similarity can be merged (there may be several of them). After we merge the two nodes we label the new node with the common prefix of the original two labels. We also have to preserve the uniqueness of the label. We do no merge if it violates uniqueness of labels. We add up the length of the label of each node in the final graph and try to find the minimum of this number. Or in a more abstract sense, Is labeled graph G contractible (while maintaining our needed invariants e.g. uniqueness of labels) to (given) labeled graph H ?


texts:
I have a heap with $n$ elements.
$k$ represent a number that is the height of one of the elements in the tree.

I need to compare two run times and prove what i claim.

The 2 run times are:
$$
(1)O(\lg n \cdot (\lg n - k))
$$

And:
$$
(2)O(2^k \cdot \lg n)
$$

Where:
$$
\lg n - k
$$
Is a constant value.

For the first run time formula, its seems that we get: $O(\lg n)$

But how do i find the run time (and prove) for the second run time?

Thanks.


texts: How to efficiently create balanced KD-Trees from a static set of points

texts:
From Wikipedia, KD-Trees:

  Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. [..] This algorithm presorts n points in each of k dimensions

I fail to understand how that is actually done. Consider this example:

Lets say I have 5 points in an array.

0 = (4, 7)
1 = (2, 9)
2 = (5, 4)
3 = (3, 6)
4 = (2, 1)

I suppose we now want to create 2 sorted arrays, one by X and one by Y ?

Sort them by X     Sort them by Y
1 = (2, 9)         4 = (2, 1)
4 = (2, 1)         2 = (5, 4)
3 = (3, 6)         3 = (3, 6)
0 = (4, 7)         0 = (4, 7)
2 = (5, 4)         1 = (2, 9)

We start creating the KD-Tree. Lets split by X axis, at the first step. We select the median of the points, 3 = (3, 6), so the Left and right trees will like this:

Left  (first half)
1 = (2, 9)
4 = (2, 1)

Right  (second half)
0 = (4, 7)
2 = (5, 4)

Now we want to sort the Left and the Right trees by Y axis. How are we supposed to make use of the points that we sorted previously by Y axis ?

The only solution in my eyes is to re-sort the Left and Right trees respectively, by Y axis. What is Wikipedia talking about ?


texts: Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?

texts:
I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists.

Is there a good / quick / easy way to see that in fact finding a Hamiltonian path should be much harder than finding a Euler path?


texts:
How do I prove the following proposition?

Let $T$ be a tree, and let $S$ be a subset of the vertices. If $|S|$ is even then we can partition $S$ into pairs $(x_i,y_i)$ such that the paths $x_i-y_i$ are edge-disjoint.


texts: spanning tree implemented by a min priority queue

texts: if it is executed on unconnected graphs what will it execute? I thought it won't execute since it is unconnected but since it is being implemented by min priority queue, will that affect the results?


texts: The range of functions defined by pure lambda terms

texts:
Consider a full set-theoretic model of the simply typed $\lambda$-calculus with infinite base types. Say that an element in this model is pure if it is the semantic value of some closed pure term in this model, and impure otherwise.

Intuitively pure functions ought to be blind to the differences between impure functions. This makes me suspect something like the following is true:

  If a pure function in this model takes at least one impure value, it takes every value (i.e. $[[\alpha]]$ is surjective if $[[\alpha]]$ takes at least one impure value.)

Is it?


texts: How to decide whether a language is decidable when not involving turing machines?

texts: For instance, consider L = {k : the binary expansion of sqrt(2) contains k consecutive 1s}. Obviously Rice Theorem would not work. I also tried the method of how it is to PCP undecidable but still no luck. How to prove that this is undecidable?


texts: Can I find all the common subsequences between 2 sequences by using dynamic programming?

texts:
I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one.

Thank you.


texts: Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

texts:
Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed by the grammar $S \rightarrow aSa\ |\ aa$.

It appears to only parse words from the language $\{a^{2^n}\ |\ n \ge 1 \}$.

I generated such a parser using this ABNF Parser Generator with the production rule S = "a" S "a" / "aa" and the parser does not recognize the word aaaaaa, for example.

I would expect it to use the production $S \rightarrow aSa$ until the concatenation of the parse tree's terminal nodes from the left starts with 7 a's, and then go up the parse tree choosing the production $S \rightarrow aa$ instead until the tree looks like this:

   S
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a


texts: Bellman-Ford Termination when there is no change on vertex weights?

texts:
We know the bellman-ford algorithms check all edges in each step, and for each edge if,

  d(v)>d(u)+w(u,v)

then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the length of best finding path for vertex u. if in one step we have no update for vertexes, the algorithms terminate. with supposing this algorithms, for finding all shortest path from vertex s in graph G with n vertex after k<n iterate is finished, can we conclude:

1) number of edges in all shortest paths from s is at most k-1

2) weight of all shortest paths from s is at most k-1

I Think Neither the number of edges nor their total weight is limited by k-1 with the defining problem, but my TA says (1) is True. How can describe these conditions?


texts: Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?

texts: If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$ in quasi-polynomial time? As I found, we cannot find any quasi-polynomial time solution for NP-hard problems (or at least it is a strong conjecture) such as finding the minimum vertex covering set.


texts: Are nearly all natural numbers compressible?

texts:
A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov complexity is less than its length, $K(s) < |s|$. The Kolmogorov complexity of a string is defined as the size of the smallest Turing machine (TM) that writes the string and halts when given a blank tape. I want to define the size of a TM as the number of states the machine has. I want to use a simple type of TM known as a Busy Beaver. BB's use two symbols, 0 and 1. A BB blank tape is initialized to all 0's and is unbounded in both directions.

Let the Kolmogorov complexity of natural number $n$, $K(n)$, be the number of states in the smallest BB that writes $n$ 1's and halts when given a blank tape. I use this definition so I can use known results about busy beavers, particularly Rado's sigma function, $\sum(n)$. $\sum(n)$ is defined as the maximum number of 1's an n-state BB can write and halt when given a blank tape. It is known $\sum(n)$ grows faster than any recursive function. This shows there is no recursive limit on how much a natural number can be compressed.

$\sum(2)=4$ so $K(4)=2$. This means 4 is a compressible number. This is the definition of the BB:

A0: 1RB / B0: 1LA

A1: 1LB / B1: 1RHalt

"A0: 1RB" means in state A on input 0 write 1, move one position right, and switch to state B. We can "extend" this machine to create new machines that compress natural numbers. To extend this machine replace the halt state with a new state. On input 0 this state writes 1 and halts. On input 1 it writes 1, moves one position right, and stays in the same state.

A0: 1RB / B0: 1LA / C0: 1RHalt

A1: 1LB / B1: 1RC / C1: 1RC

This 3 state machine writes 5 1's and halts. This proves $K(5) \leq 3$ and 5 is a compressible number. In fact, all numbers greater than 3 are compressible by at least 2 because we can write the first 4 1's using only 2 states. $\forall n(n>3 \rightarrow K(n) \leq n-2)$

We know natural number $n$ can be represented as a binary number with $log_2(n)+1$ bits. Let a number be super compressible if $K(n) < log_2(n)+1$. We see 4 is super compressible because $K(4)=2 < log_2(4)+1 = 3$. It is known $\sum(5) \ge 4098$. This means $K(4098) = 5$ and 4098 is super compressible. By extending this 5-state machine we can show 4099 through 4107 are also super compressible. In general, the range $\sum(n)$ through $\sum(n)+log_2(\sum(n))-n$ will be super compressible. For example, it is known $\sum(6) \ge 3.515 * 10^{18267}$. This proves the range $3.515 * 10^{18267}$ through $3.515 * 10^{18267} + log_2(10^{18267})$ is super compressible.

Are all large enough natural numbers super compressible? If not, why not?

Note there are lots of machines besides the ones defined by $\sum(n)$. There are probably lots of halting 5-state machines that write more that $2^5$ 1's and less than 4098 1's. All such machines define ranges of super compressible numbers. I previously asked a similar question without getting an adequate answer.


texts: How does virtual memory work when it need to save data in physical memory into disk?

texts:
I'm reading a textbook which desribe VM as:

a data structure stored in physical memory known as a page table that maps virtual pages to physical pages. The address translation hardware reads the page table
each time it converts a virtual address to a physical address. The operating system
is responsible for maintaining the contents of the page table and transferring pages
back and forth between disk and DRAM.

A page table is an array of page table entries (PTEs). M. If the valid bit is set, the address field indicates the start of the corresponding physical page in DRAM where the virtual page is cached. If the valid bit is not set, then a null address indicates that the virtual page has not yet been allocated. Otherwise, the address points to the start of the virtual page on disk.
So my question is, let's the PP0(VP1) has been modified and need to be written back to disk to make the change permanent. But the the PTE1 only has address(PP0) pointed to main memory, it has lost disk address VP1, so how can the changes be made to disk in this scenario?


texts: How does MIPS ( or any other multi-byte word arch ) fetch a word?

texts:
I've recently been studying MIPS as part of a CS course, but something bugs me.
We've seen so far that MIPS increments the PC by 4 each cycle because each word is in fact comprised of 4 bytes (32 bits), each with their own address.
I've also seen that a theoretical RISC machine has instructions that should only take a single cycle to execute.

Ignoring memory latency, how does it manage to generate an address for each 4 bytes?
It can't have four adders for memory address calculation right? That'd be too expensive! Or am I incorrect in this assumption?
I've also seen other architectures that manage to pull multiple bytes from memory (even multiple words) in a single step/cycle/instruction, but how is this achieved if each byte needs an address?


texts: prove(disprove) asymptotic exact bound (theta)

texts:
I want to prove (or disprove) that

$$\sum_{i=1}^n\log_2 i = \Theta(n\log_2 n)\,,$$

but I totally get stuck with this example. May someone help me with that.


texts: What's are the consequences of subject expansion property?

texts:
Subject reduction is a well and widely used property of typed rewriting systems.
Subject expansion is much less known.
What are the applications of this property and which systems enjoy it?


texts: In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. In case of PDA where transitions are of the type $a,b \to c$, with $a$ being the input alphabet being read, $b$ being the stack element being read and popped and $c$ being the stack element being pushed. In NFA I understood the splitting upon $\epsilon$ as the ability to guess. So I assumed that a PDA in a state $r$ with stack being $S$ splits into  two PDA only when the transition is $\epsilon,\epsilon \to \epsilon \\$ ( that is when $a=b=c=\epsilon$ in the figure below the PDA splits into two with one being in state $r$ and other in $s$ with same stack $S$ ). But now I am a bit doubtful, about when does a PDA split. I feel I am wrong and am misunderstanding something trivial. ( The figure below just shows the part of a larger PDA ). How would it affect the power of a PDA if it were only allowed to split on $\epsilon,\epsilon \to \epsilon$ transition?


texts: Can the reproduction function of an evolutionary algorithm consider gene strength?

texts:
I am trying to solve the Zen Garden puzzle using an evolutionary algorithm. My question relates to evolutionary algorithms in general.

Bit about evolutionary algorithms:
An evolutionary algorithm is an algorithm which tries to solve a given problem in a semi-random way. Most often I have seen it is implemented thusly: for a given starting state of the problem a generation of random solution approaches for is generated. Each speciemen (approach) has a set of genes which define it. Each speciemen is then used to try and find a solution to the problem. If no solutions are found, then we try to determine the fitness of each speciemen by some set of rules. For example- if the problem was to collect all treasures on a map, then the fitness a speciemen could be determined by the ammount of treasures it managed to collect. Once we determine their fitness we try to crossbreed the speciemen semi-randomly, giving higher chance of reproduction to those with higher fitness. This way we create a new generation of speciemen, where each of them has some genes from both of its parents. Then we try to solve the problem using the new generation of speciemen and the cycle goes on until a solution is found or we reach some kind of pre-determined limit of max-generations.

Question: Can the reproduction function which determines how speciemen (solution attempts) reproduce take into account some kind of gene strength to also determine which genes are best to be passed down to the child of two speciemen? What I mean by that is that for example if I could measure how much a certain gene contributed to the solution attempt can I give the gene a higher chance to be passed on or should child genes be passed on randomly?


texts: How is this definition of the quantum Fourier transform to be understood?

texts:
In regards to the quantum Fourier transform Page 845 of The Nature of Computation states

  The amplitudes $\tilde{a}_\mathbf{k}$ are the Fourier coefficients of $a_\mathbf{x}$,
  $$\tilde{a}_\mathbf{k} = \langle \mathbf{k}|\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_\mathbf{x}(-1)^{\mathbf{k\cdot x}}a_\mathbf{x}\,.$$

Here $x$'s are the standard basis vectors and the $k$'s are (presumably) the Fourier basis. And $\psi = \sum_\mathbf{x} a_\mathbf{x}|\mathbf{x}\rangle$.
To pick a concrete example let the number of qubits, $n$, be 2. The book isn't clear on this but my first guess is that the $\mathbf{k}$'s should be these:

$$
\begin{bmatrix}1/2\\1/2\\1/2\\1/2\end{bmatrix}, \begin{bmatrix}1/2\\-i/2\\-1/2\\i/2\end{bmatrix},\begin{bmatrix}1\\-1\\1\\-1\end{bmatrix},\begin{bmatrix}1/2\\i/2\\-1/2\\-i/2\end{bmatrix}.
$$

Though, I've also heard the argument that they should be the columns of

$$H \otimes H = \begin{bmatrix}1/2 & 1/2 & 1/2 & 1/2\\1/2 & -1/2 & 1/2 & -1/2\\1/2 & 1/2 & -1/2 & -1/2\\1/2 & -1/2 & -1/2 & 1/2 \end{bmatrix},$$

where $H$ is the $2\times 2$ Hadamard matrix. However, the book also states that

  each "frequency" is, like $\mathbf{x}$, an $n$-dimensional vector mod 2.

And I don't see how to convert the entries of either of these bases into elements of $\mathbb{Z}_2$.
Ignoring that issue I immediately run in to the following. Take the first vector of either basis as $\mathbf{k}$ and compute the Fourier coefficient $\tilde{a}_\mathbf{k}$ according to the definition above while also using $|\psi\rangle = \begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2\end{bmatrix}^T$ as an example. On the one hand

$$
\langle\mathbf{k}|\psi\rangle = 1\,.
$$

But on the other hand

$$
\frac{1}{\sqrt{2^n}}\sum_\mathbf{x}(-1)^{\mathbf{k\cdot x}}a_\mathbf{x} = \frac{1}{2} \left((-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2}\right) = i\,.
$$

What am I not getting here?


texts:
We do not know if $P=NP$ has an impact on $VP=VNP$ however how about $P=PP$?

Is $PP$ and $VNP$ related and would $P=PP$ or $P=PSPACE$ imply $VP=VNP$?

Is there a way to show $\#P$ is in $FP^{PP}$?


texts:
Like including parenthesis (( and )), addition, subtraction, multiplication, and division, and the Order of Operations in mind.
I tried (in Lark EBNF):
%import common.WS
%ignore WS
%import common.SIGNED_NUMBER -> NUMBER

start: exp
?exp : add
     | mul
     | sub
     | div
     | NUMBER
     | frac
     | parenthesis
?parenthesis: "(" exp ")"
add  : exp "+" exp
sub  : exp "-" exp
mul  : (exp "*" exp) | NUMBER parenthesis
div  : exp "/" exp

I wonder if the Order of Operations would make arithmetic a context-free grammar.
Originally this post


texts: What is a "contradiction" in constructive logic?

texts:
In Practical Foundations for Programming Languages, Robert Harper says

  If for a proposition to be true means to have a proof of it, what does it mean for a proposition to be false? It means that we have a refutation of it, showing that it cannot be proved. That is, a proposition is false if we can show that the assumption that it is true (has a proof) contradicts known facts.

But then, this begs the question- what is a contradiction in constructive/intuitionistic logic?

Is this meant in the sense of deriving $(\bot\text{ true})$ somehow? How would this happen in a sensible way? Would a judgment of the form $(A \supset \bot \text{ true})$ need to be introduced?

Alternatively, is it perhaps meant in the sense of the reader using their discretion to informally label something as contradictory? For example, interpreting $a = b$ and $a \neq b$ as conflicting propositions.


texts: Computing intersections between a set of polylines in 2D

texts:
Given a set of 2D polylines such that each polyline:

May have self-intersections;
May intersect some of (or all) the other polylines,

How do I efficiently find all pairs of intersecting segments and the coordinates of each corresponding intersection point? (We may assume that no three segments intersect in the same point.)

In other words: is it possible to find all intersections more efficiently than using algorithms designed for finding intersections in a set of segments? If it is possible, how? If it isn't, why not?

Each polyline is represented as a sequential list/array of points corrensponding to the endpoints of the segments (so if there are N points, there are N-1 segments in a polyline).

Ideas:

Using the Bentley-Ottmann sweep line algorithm. The problem is that it takes a set of segments as its input, which means we have to first convert our polylines into a set of segments which seems to eliminate the potentially useful information about the connected endpoints and increases the number of input points. This seems to be a waste of computing resources if there is a way to use the input polyline points directly instead.
Sweep line algorithms rely on sorting the input points by one of the coordinates. Knowing that each of the input polylines is already a sequential list of points, perhaps this could help at least partially to eliminate the need for sorting?


texts:
I'm trying to show Amplification works for randomized algorithms, and for randomized approximation algorithms.

Amplification for randomized algorithms:
Given a randomized algorithm with time complexity $f(n)$ and error probability $\frac{1}{4}$, show there is an algorithm that solves the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\varepsilon}\right)\right)$ run time, and error probability of $\varepsilon$, for a given $\varepsilon>0$.

I managed to show this running the original algorithm $k$ times, and choosing by majority vote the answer. Using Multiplicative Chernoff Bound (Which I've proven as well), I've shown $k\geq O\left(ln\left(\frac{1}{\varepsilon}\right)\right)$ gives us the required results.

Now I'm trying to do the same for approximation algorithms.

Amplification for randomized approximation algorithms: Given a randomized approximation algorithm that returns an $\varepsilon$-additive-approximation with a probability of $\frac{3}{4}$, with run time complexity of $f\left(n\right)$, show there is an algorithm that returns an $\varepsilon$-additive-approximation with a probability of $1-\delta$, for the same problem, but with $O\left(f\left(n\right)log\left(\frac{1}{\delta}\right)\right)$ run time, for a given $\delta>0$.

The first thing that comes to my mind, is use a similar approach as before - run the original algorithm $k$ times, but this time instead of using majority vote, return the average.

I have to somewhow find a $k\geq O\left(ln\left(\frac{1}{\delta}\right)\right)$ such that $\mathbb{P}\left[\left|OPT-\frac{1}{k}\underset{i=1}{\overset{k}{\sum}}X_{i}\right|>\varepsilon\right]<\delta$.

I tried using the triangle inequality, then using union bound, but this doesn't lead me to being able to use Chernoff. In order to use Chernoff, I thought of defining an indicator random variable for each run of the original algorithm, stating if the result - $X_{i}$ is bad (that is, if $\left|X_{i}-OPT\right|>\varepsilon$), but this is where I get stuck.

Would appreciate any help. Thanks!


texts: Why is the common explanation to the halting problem an oversimplification?

texts:
So watching many youtube channels, the explanation to the impossibility of solving the halting problen involves assuming you can, doing the opposite, and feeding it back into itself to create a paradox.
What I don't get is why this is an (over)simplification. The logic seems to check out. What is the flaw in this reasoning?


texts: Time complexity of printing prime numbers within a range?

texts:
I've written an answer to this question, which asks about the following:
What is the time complexity for the given code that prints prime numbers from start to end? Is it $O(end*\sqrt{n})$?
/**
 * Print prime numbers between start and end inputs
 * Time-Complexity: O(end * sqrt(n))
 * Space-Complexity: O(1) only one value as input
 * @param start, end
 * @return
 */
public void printPrimeSeries(int start, int end) {
    for (int i = start; i < end; i++) {
        if (findPrimeOrNot(i)) {
            System.out.println("The value " + i + " is a prime number");
        }
    }
}

public boolean findPrimeOrNot(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter start number for prime:");
    int startInput = scanner.nextInt();

    System.out.println("Enter end number for prime:");
    int endInput = scanner.nextInt();

    PrimeNoSeries primeNoSeries = new PrimeNoSeries();
    primeNoSeries.printPrimeSeries(startInput, endInput);
}

Notice: That's not my code. It's by mahesh87.
My answer to that is:

In your case $n$ is end - start. In $O$ notation $n$ represents the problem size, which is the range between start and end in your case. In $O$ notation you are interested in the worst case, therefore we can assume that start is always 0. Now $n$ is just an alias for end.
As we have defined $n$, it's obvious that printPrimeSeries is just $O(n)$ (from 0 to end). The method uses findPrimeOrNot that iterates from 2 to Math.sqrt(n), which is $O(\sqrt{n})$. Combining both is $O(n)O(\sqrt{n})$, which is just $O(n\sqrt{n})$.
Notice that the $O$ notation tells you something about the asymptotic behaviour of the algorithm. It doesn't matter too much if there are 2 parameters, at least in this case.
So yes, your assumption is fully correct (ignoring that you've written end instead of $n$).

Other users have proposed that the correct answer is $O((end - start)\sqrt{end})$. I think this is a valid point of view but it doesn't provide any beneficial information in terms of $O$ notation for the given case.
Now my question: What is the formally correct way to describe the time complexity of the given algorithm? Is my reasoning valid or is it just plain wrong?


texts: In complexity, why do we find upper bounds, not lower bounds?

texts: In algorithms we use to find Big-O (upper bound), Big-omega (lower bound) and Big-Theta but why we are always interested in finding upper bounds instead of lower bounds?


texts: Formal grammar with constraints on the number of each symbol

texts: I have a language where each type of symbol is only allowed a particular number of times, but the order isn't important. For example, lets say there are three symbols $a, b, c$, and a valid string in the language consists of at most 5 $a$, 3 $b$ and 2 $c$ characters. So $ababbc$ is valid, $ccbbbaaaaa$ is valid, but $abcabcabc$ is not. I'm struggling to come up with a grammar that satisfies such constraints without resorting to enumerating each possibility. Is it possible to have a concise set of rules that encode these constraints?


texts: What kind of structural features of strings can be described by regular grammars?

texts:
Context-free grammars, as well as other types of grammars, can naturally
associate structure with the strings of the defined language, for
example tree structures in the case of context-free language.

What kind of structural features can be thus described by regular grammars,
and associated with the strings of the language.

One answer is of course that it can associate a non-terminals with
each prefix (or suffix) of the string. That sorts the prefixes (or
suffixes) into sets that may intersect, depending on the grammar.
But what else would you see?

related question : Why CFG can specify structure of sentence but Regular grammar cannot?


texts: Finding an isomorphism between finite automata

texts:
Im having trouble figuring out how to determine if two finite automata are the same apart from renumbered states.

More specifically, heres an example:

It's easy to generate a regular expression by hand and see that both FA produce:
b + (ab*a(a+b)), though their states are renumbered, they are identical.

What I'm trying to do is figure out a way to check if the two states are the same apart from state renumbering without generating a regular expression.

Since the states are just renumbered, I'm thinking it has something to do with permutations of the states(1 2 3 4) but am not seeing how to determine if they are equivalent. I'm thinking it has something to do with input like this and relating it to the 24 permutations of the states:

Left       Right
1 a 2      4 a 3
1 b 4      4 b 1
2 a 3      3 a 2
2 b 2      3 b 3
3 a 4      2 a 1
3 b 4      2 b 1

Im more so trying to figure out the algorithm to renumber the states Any ideas or help is greatly appreciated!


texts: How to prove that the complement of a regular language is always regular?

texts:
If A & B are regular languages, prove that complement of A is also regular language. (Closure of regular languages under complementation)

Can anyone help me with the proof??


texts: Difference in having * inside vs outside of brackets for NFA

texts: If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^* \cup1^*)$ vs $(0 \cup1)^*$ in otherwords what difference does it make for the diagram if the star is on the inside or outside of the brackets?


texts:
Consider a restriction on 3-SAT in which no literal occurs in more than two clauses.
How do we show that this is NP complete ?

(edit - I was getting confused over the definition on the 3-SAT,here by 3-SAT it implies that a clause can have at most 3 literals.)


texts: Path in directed, weighted, cyclic graph with total distance closest to D?

texts:
Input: Directed, weighted, cyclic graph G. Two distinct vertices in that graph, A and B, where there exists a path from A to B. A distance d.

Output: A path between A and B with distance closest to d. The path need not be a simple path - it can contain repeated edges and vertices.

Which algorithms exist to solve this problem? I'm looking for an optimal solution, but I'm also interested to see if there are any approximation algorithms as well. Efficiency is not a huge concern - I just want to get an idea of the algorithms available.

Bonus question: are there any algorithms to compute a path from A to B that visits every node at least once, while finding the distance closest to d?


texts: While considering the wrap around time, why are the headers not considered?

texts:
In many texts and places as in here the wrap around time is found as :
$$\text{Wrap-Around Time = $\frac{2^{32} \text{ bytes}}{\text{Bandwidth in Bytes/sec}}$} $$
The wrap-around time is defined as the time in which the first sequence number of TCP has to be reused.
While considering the wrap-around time, why are the headers (of TCP or IP) not considered? I mean, the raw $2^32$ bytes are not just the only ones to be transmitted over the network. Also, the headers need to be transmitted and they do require some time for transmission. Why is it considered as if the entire stretch of bytes is continuous? Or is it so that the headers are just ignored?
$\quad\quad\quad\quad\quad\quad$


texts:
I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to destination)?
I have few ideas about it:

Find best path, then exclude trips (from path) from transportation network
and rerun algorithm. (It's not clear for me how to choose new departure time).
Find best path P, then rerun algorithm with adjusted departure
    time so it's not possible to use P. (I think some good paths may be missed here)

What is the way to find next best paths?


texts: Efficiently find elements which are out of place in an otherwise sorted list

texts:
I have some data that includes two columns for dates, and I want to retrieve - based on these two columns - all the instances where an illegal operation has occured. An operation is illegal if the value in Col B breaks chronology in the column.

Structure

    *    Col A    *    Col B    *
    *    Opened   *    Moved    *
Row * --------------------------*
 1  * 06/20 10:00 * 06/22 08:10 *
 2  * 06/20 10:30 * 06/22 08:40 *
 3  * 06/21 10:00 * 06/22 08:30 *
 4  * 06/21 11:00 * 06/22 08:50 *

The table is sorted on Col A, from smallest to largest.

The rule is that the oldest open item should be moved first.
Thus, moving some arbitrary item that isn't the oldest open item is illegal.

Example

The item in row 3 was moved at 08:30, but at that time there was an older item (row 2) that should have been moved first. That means that row 3 represents an illegal operation and should be marked or returned.

My case

My data set is in the range of millions of rows. I need an accurate method for finding these illegal operations, but I am a little stuck on how to approach the problem.

The most workable idea I've had so far, I think, is to build a helper column where the data from Col B is sorted lowest to highest, compare this step by step with the original column, and shift the data downwards every time the data doesn't match. This will leave the helper column with blanks indicating illegal operations in the corresponding row in the original dataset.

Another idea was to compare the current, preceeding and following dates - but this has seemingly expensive weaknesses. Although rare it's conceptually possible that several illegal operations can immediately follow each other, meaning that I have to compare some arbitrary higher number of dates (let's say 15 instead of 2 (the preceeding + following)) for each step in a loop.

While one of these sub-optimal ideas probably will do the work, in the sense that the job gets done eventually, I struggle with the thought that there isn't a better way to solve this.


texts: Trying to understand a token file for lexical analysis

texts:
I am reading this article about compiler. I am facing some problem in understanding the content of the token file. Specifically, what is the meaning of the following lines:

    [ \t\n]                 ;
    [a-zA-Z_][a-zA-Z0-9_]*  SAVE_TOKEN; return TIDENTIFIER;
    [0-9]+\.[0-9]*          SAVE_TOKEN; return TDOUBLE;
    [0-9]+                  SAVE_TOKEN; return TINTEGER;

What is * and + at the end of the expressions ?

Thanks in advance for explaining me.


texts: What aspects of linguistics are necessary or good for natural language processing?

texts: What aspects of linguistics are necessary or good to know for natural language processing? What references do you recommend for studying those aspects? Thanks!


texts: A book introducing proof theory needed (many-sorted FOL, classical non-Gentzen calculus, satisfiability in partial algebras, induction)

texts:
We define a signature as a triple $$\Sigma\ =\ (S,F,\mathrm{type})$$ where $S$ is a set of sorts, $F$ a set of $n$-ary function symbols $f$ of the type $\mathrm{type}(f)$ $=$ $(M_1,\dotsc,M_n\dashrightarrow M_{n+1})$, where $n\ge 0$ and all $M_i$ lie in $S$ ($1\le i\le n$).

A $\Sigma$-algebra for us is a pair $$A\ =\ (G,H)$$ where $G$ is a family of carrier sets for sorts in $S$, and $H$ is a family of (in general partial) functions of the correspoinding type, one function per symbol in $F$.

We consider an infinite set of fresh typed variables and define $\Sigma$-terms as usual: all nullary constants in $F$ are terms, all variables are terms, and if $t_1,\dotsc,t_n$ are terms of type $M_1,\dotsc,M_n$, and $\mathrm{type}(f)=(M_1,\dotsc,M_n\dashrightarrow M_{n+1})$, then $f(t_1,...,t_n)$ is a term of type $M_{n+1}$.

We define first-order formulas (over the equality and the $\mathrm{defined}$ predicate) as usual:

$t=t'$ is a formula where $t$ and $t'$ are terms,
$\mathrm{defined}(t)$ is a formula where $t$ is a term,
if $\varphi$ and $\varphi'$ are formulas, so are $\varphi\lor\varphi'$, $\neg\varphi$, $\forall x{\in}M\colon \varphi$, etc.

Given an assignment $\eta$ of the free variables of a formula $\varphi$, we  define $A,\eta\models\varphi$ (the validity of $\varphi$ in an algebra $A$) inductively as usual. Special cases:

$A,\eta\models t=t'$ iff $t$, $t'$ are either both undefined or both defined with the same value under $\eta$.
$A,\eta\models\mathrm{defined}(t)$ iff  $t$ (which contains partial function symbols in general)  has a well-defined value in $A$.

So far, nothing really new has happened: yet another variation of a many-sorted first-order logics for partial algebras/structures has been described.

Question: which book or journal paper describes a classical, first-order proof system (providing a checkable and possibly useful relation $\vdash$ such that $A,\eta\vdash t$ implies $A,\eta\models t$) for

all partial algebras
all partial term-generated algebras (i.e., where each element of each carrier set is an interpretation of some ground term)?

Of course, you can use induction in the second case in addition.

Yes, I took a look into the To-Truth-Through-Proof book and into https://www.fecundity.com/codex/forallx.pdf, and they are somewhat far away. Are there books which are a better fit?


texts:
I have been trying to get to grips with what an exponential object is using a poset as an example.
So in the poset...
{2, 4, 6, 8, 9, 12, 14, 30, 36, 48, 60, 72, 84} x is related to y iff x is a factor of y.

I understand eg: hom(- x 60) is isomorphic to hom(-, 84^60)
so...

2x60 = 2... and 2->84

4*60 = 4... and 4->84

etc...

so the set of things that when producted with 60 the result is related to 84 is {2, 4, 6, 8, 12, 14, 36, 48, 72 84}.

So 84^60 is an object that all these objects is related to... but what exactly is 84^60 in this poset?

Is there a user friendly soundbite such as the product of two objects being the greatest common divisor?

...or have I got completely the wrong end of the stick?

Thanks in anticipation!


texts: We are given $n, m$ with $n - m > 1$. Let $S$ be the set of all $n$-bit words. Form $2^{n-m}$ disjoint subsets of $S$ of size $2^m$, denote a typical one of them by $A$, and let $B = S \setminus A$. With $H(a,b)$ denoting the Hamming distance of elements $a \in A$ and $b \in B$, let $G(a) = \max_{b \in B} H(a,b)$ and $F(A) = \min_{a \in A} G(a)$. How could one construct the $A$s such that the $F(A)$ values are as small as possible?


texts: DAG for contiguous subsequence of maximum sum

texts:
I have trouble understanding DAG behind the "contiguous subsequence of maximum sum problem". Let's say I denote by S(i) maximum of sums of contiguous subsequences ending in i. So S(i) are my subproblems. To calculate S(i) I need S(i-1) so the edge will be between node i and i-1. Denoting the sequence by a_i, I think my DAG will look like this:
a_1 -> a_2 -> ... -> a_n
I feel like this doesn't tell me anything. In Chapter $6$ of the book Algorithms (Dasgupta et al.), they find a correspondence between problem and edges in the graph. I don't really see that here. I don't know if I grasped the idea of DAG right, something feels off.


texts: How to find the maximum element in a multi-tree under logN time?

texts:
Here N represents the number of elements in the multi-tree.
Please state the algorithm that you have used to do so. It would be great if you can implement this in Java/C++ too and post the code as well.

Also I used union-find to initialize the tree. You can consider or not consider this algorithm. I just need the algorithm to search for the maximum element in a multi-tree. That would clear my problem.


texts: Find minimum set of vertices that are reachable from all other vertices

texts:
I have a DAG and I wish to find the minimal set of vertices that have a path to all other vertices.

My solution was to simply find all the vertices that their incoming degree is 0.
However, if there are two vertices in the DAG that have an indegree of 0 and that point to a common vertex then one of the two vertices is surplus.

Any help appreciated.


texts:
Currently, I'm trying to understand the definition and notion of MaxSNP and MaxSNP-hardness. I see that several combinatorical problems such as Max-3SAT are in MaxSNP since one can easily express them as first order predicates quantified over the set of all structures.

The question is: Is the definition of MaxSNP applicable to flow problems? I'm struggling with the formulation of a flow problem, which incorporates sets of real numbers rather than discrete sets of elements as solutions, as first-order predicates. For example, are the traditional max flow and min-cost flow problems in MaxSNP? (clearly, it's not MaxSNP-hard, but is it in MaxSNP?)


texts:
int function(int n)
{
   int i;

   if (n <= 0) {
       return 0;
   } else {
       i = random(n - 1);
       return function(i) + function(n - 1 - i);
   }
}

Consider the recursive algorithm above, where the random(int n) spends one unit of time to return a random integer which is evenly distributed within the range [0,n]. If the average processing time is T(n), what is the value of T(6)T(6)?

(Assume that all instructions other than the random cost a negligible amount of time.)

This question was on Brilliant and I was following along their solution

              T(n)=T(i)+T(n−1−i)+1
              T(n)=T(0)+T(n−1)+1
              T(n)=T(1)+T(n−2)+1
                    ....
              T(n)=T(n−2)+T(1)+1
              T(n)=T(n−1)+T(0)+1

       nT(n)=2(T(0)+T(1)+....+T(n−2)+T(n−1))+n..........(1)
       (n−1)T(n−1)=2(T(0)+T(1)+...+T(n−2))+n−1).........(2)

Subtract 1 from 2

            nT(n)−(n−1)T(n−1)=2T(n−1)+1

$\frac{T(n)}{n+1}$ = $\frac{T(n-1)}{n}$ + $\frac{1}{n(n+1)}$.   They mention this is a telescoping sequence.

They say T(0) = 0 and then get

$\frac{T(n)}{n+1}$ = $\frac{1}{(1)(2)}$ + $\frac{1}{(2)(3)}$ + ... + $\frac{1}{n(n+1)}$ = $\frac{n}{n+1}$.  I do not understand how they got to this equation from the previous.


texts: Deriving the average number of inversions across all permutations

texts:
In the answer by Raphael to the question "Is there a system behind the magic of algorithm analysis?", there is an equation:

$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A) \tag{1},$$

where $A$ is an array, $\mathbb{E}[C_{\text{swaps}}]$ is the expected number of swaps it takes to sort a random permutation with Bubblesort, $n$ is the length of $A$, and $\operatorname{inv}(A)$ is the number of inversions of $A$.

Then (1) is equal to the following equation:

$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}. \tag{2}$$

But I don't understand how to prove (2) based on (1). Could anyone please give me a proof?


texts: Can Double Hashing return the same value 2 times?

texts:
$h(i,k)=(h^{}_{1}(k)+i * h^{}_{2}(k)) mod |T|$

as it defined in wikipedia

I would like to know if it possible that Double Hashing return the same value for given $k$ when $i=1$ and $i=2$. Or from the other side, is it possible to build $h^{}_{2}$ in such way to that it never happen?


texts: Will ternary computers be faster than binary?

texts:
If we had a computer in base 3 which used the characters {0, 1, 2} instead of just {0, 1} (and we implemented a ternary logic on the hardware), will this computer be faster than computer using binary?
Why or why not?

If we had a computer with even a higher base than 3 will it be more fast or slow? Which is the best base for fast processing and computation?


texts:
Consider the following pseudo code for mapreduce to find the frequency of words in a collection of documents:

map(String key, String value)
// key: document name
// value: document contents
 for each word w in value
   EmitIntermediate(w, "1")

reduce(String key, Iterator values):
// key: word
// values: a list of counts
  for each v in values:
    result += ParseInt(v);
    Emit(AsString(result));

So the map step gets each word as a key and output its frequency in a document. Does the reduce step sum the counts of each word?


texts: How to calculate a direct mapped chace capacity with tag and valid bits?

texts:
I've seen some very useful posts about this, but none took into consideration both the tag and valid bits. This is a question I took from a notebook in my computer engineering course.

  Consider a machine with a direct mapped cache, with 1 Byte blocks and 7 bits for
  the tag. This machine has a RAM with 2 KB capacity. Calculate the cache's total capcity, counting the tag bits and valid bits.

Breaking a cache into parts, I have the tag bits, set index and block offset.

I already know I have 7 tag bits, but then I'm really not sure how to calculate the rest, because in this type of question we are usually given the words per block. I think the offset is 3, because 2^3 (8 bit blocks).

I feel like the question itself doesn't give enough, shouldn't it be stated how the system address is (byte/word addressable)? Also, is the RAM capacity relevant to the question at hand?


texts: Why can't we derandomize the PCP theorem by iterating over all possible $\log n$ random strings?

texts:
Let's say I can solve problem $A$ in polynomial time using only $\log n$ bits of randomness, with a $\ge \frac{2}{3}$ chance of a correct answer.  Then surely I can solve $A$ determistically by running my algorithm for $A$ over all random strings of length $\log n$ (of which there are a polynomial number) and take a popular vote of the outcomes.

I don't understand, then, why we would ever talk about $O(\log n)$ amounts of randomness in complexity classes that are closed under polynomial factors.  More specifically, the PCP theorem says $NP = PCP[O(\log n), O(1)]$ - why isn't that the same as $PCP[0, O(1)]$?


texts: Algorithm for detection of overlaping between vectors

texts:
I am currently developing a math-physics program and I need to calculate if two vectors overlap one another, the one is vertical and the other is horizontral. Is there any fast algorithm to do this because what I came up so far, has a lot of repeats. Eg lets say we have vector V1((0,1),(2,1)) and a V2((1,0),(1,2)) where the first parenthesis is the coordinates starting and the second coordinates that the vector reaches. I want as a result to take that they overlap at (1,1)

So far the only idea I came up is to ''expand'' each vector to a list of points and then compare the lists e.g for V1 its list would be (0,1) (1,1) (2,1)


texts:
I am taking an algorithm analysis class and am stuck on one of my homework problems and would appreciate it if I could receive some guidance.

The problem I'm stuck on is proving that the empty language and $\{0, 1\}^*$ are the only languages in P that are not complete for P with respect to polynomial-time reductions (problem 34.3-6 in CLRS 3rd edition). The first part of the problem seems fairly straightforward enough (proving the empty language criteria). However, I'm not sure where to even begin when I have to prove the criteria for $\{0, 1\}^*$. I'm NOT looking for the answer, however I would appreciate some guidance on how I can begin to think about this problem.


texts: Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?

texts:
Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar?

I don't believe this has a context-free grammar, but please correct me if I'm wrong.


texts: Problem with Blossoms while searching for augmenting pathes

texts:
I have problems understanding the effect of Blossoms while searching for augmenting pathes (in the matching problem).
If I have the following graph

Can't I find the augmented path from n1 to n13?

Isn't DFS as well as BFS always able to find the augmented path?
If I understand correctly, because of the Blossoms there should be at least one BFS/DFS tree, which cannot reach n13, is that correct?


texts: Is there a function $t$ fulfilling $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?

texts: $f:\mathbb{N} \to \mathbb{N}$ is in $\mathcal{O}(0)$ only if $f(n) \neq 0$ for a finite number of values of $n$. Therefore, $\mathcal{O}(0) \subset \mathcal{O}(1)$ strictly. Is there something in between, i.e. a function $t:\mathbb{N} \to \mathbb{N}$ with $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?


texts:
I have a recurrence relation:

$$f(a,b) = \begin{cases}
  1 & (a,b) = (0, 0)\\
  1 & (a,b) = (a, 0)\\
  0 & (a,b) = (0, b)\\
  2a & (a,b) = (a,1)\\
  f(a-1,b) + f(a-2, b-1) + f(a-1,b-1) & \mathrm{otherwise}
\end{cases}$$

Where the constraints: $1 \leq a \leq 10^9$ and $1 \leq b \leq 1000$. I tried using recursion to find out the values but the time complexity was very high. I also tried using a dp table but that has a high time complexity as well. Also, since a can be upto $10^9$, it isn't possible to create such a large table as the space complexity will be too high and I'll get a runtime error. I want to optimize this code so that its time complexity gets reduced. Can anyone help me to achieve this? I mean which data structure to use or what algorithm should I implement to achieve this?


texts: Every graph with $\delta(G) \ge 2$ has a cycle of length at least $\delta(G)+1$?

texts:
I'm reading up on graph theory using Diestel's book. Right on the outset I got confused though over proposition 1.3.1 on page 8 which reads:

  Proposition 1.3.1. Every graph G contains a path of length $\delta(G)$ and a cycle of length at least $\delta(G)+1$ (provided that $\delta(G) \ge 2$).

Following the proof I can see why this would be true if G actually contains a cycle, but I keep thinking there are many graphs, like the path graph itself and connected trees, with $\delta(G) \ge 2$ but which don't have any cycles.
I found this question on the same proposition, asking to prove it. The accepted answers there seem to quote Diestel's proof verbatim, assuming G just has a cycle.

I'm pretty sure I'm missing something, so I wonder why one would choose this formulation or whether I'm simply misunderstanding the proposition. Is it assumed that graphs are cyclic unless stated otherwise? Might this be specific to the context in a way I managed to overlook?

As a reminder, $\delta(G)$ is the minimum degree, taken over all vertices of $G$.


texts: Is reaching in less lines semi-decidable?

texts:
Assuming we have two programs $p_1$ and $p_2$ and two line numbers $n_1$ and $n_2$. Does $p_1$ reach $n_1$ in less computational steps than $p_2$ reaches $n_2$? By reduction from Halting, this is clearly not decidable, but I think it is semi decidable.

To do so, I would build an interpreter, that executes $p_1$ and $p_2$ simultaneously step by step and count the steps for each program. As soon as $p_1$ reaches $n_1$, I compare the number of steps to $n_2$ and return true if it is less. If $p_2$ reaches $n_2$ first, I return false. In case no program reaches $n_1$ or $n_2$, nothing happens (following semi-decidability).


texts: Proving a language to be Recursively Enumerable?

texts: I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L is representing paths on the Cartesian plane which can begin and end at any point so say begin at (1,3) and end back at (1,3). My Question is, you would be able to represent a Turing Machine for this, right? Hence it would be Recursively Enumerable.


texts: Are these special (one production) Context-Free Grammars always unambiguous?

texts:
Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

$S \rightarrow aSb\;|\;\epsilon$
$S \rightarrow aSbS\;|\;\epsilon$
$S \rightarrow aSaSb\;|\;\epsilon$
$S \rightarrow aaSaaSbb\;|\;\epsilon$
$S \rightarrow aSbScSdSeSf\;|\;\epsilon$
etc...

Grammars like these uphold 4 basic rules:

The non-terminal symbol $S$ can never appear next to itself.

e.g. $[\;S \rightarrow aSSb\;|\;\epsilon\;]$ would not be allowed.

The non-terminal symbol $S$ can appear at the beginning or end of a production but not on both sides at the same time.

e.g. $[\;S \rightarrow SabaS\;|\;\epsilon\;]$ would not be allowed.
e.g. $[\;S \rightarrow Saba\;|\;\epsilon\;]$ or $[\;S \rightarrow abaS\;|\;\epsilon\;]$ would be allowed.

The sequence of terminal symbols that exist between each non-terminal $S$ cannot all match. (EDIT: This rule is redundant, Rule 4 already ensures that at least two sequences of terminals are non-matching)

e.g. $[\;S \rightarrow aSaSa\;|\;\epsilon\;]$, $[\;S \rightarrow abSabSab\;|\;\epsilon\;]$, etc. would not be allowed.
e.g. $[\;S \rightarrow aSaSb\;|\;\epsilon\;]$, $[\;S \rightarrow abSabSaf\;|\;\epsilon\;]$, etc. would be allowed.

The sequence of terminal symbols at the beginning and end cannot match.  (i.e. $[\;S \rightarrow ☐_1SaS☐_2\;|\;\epsilon\;]$ s.t. $☐_1 \neq ☐_2$ where $☐_1$ and $☐_2$ are a sequence of terminal symbols)

e.g. $[\;S \rightarrow aSbSa\;|\;\epsilon\;]$, $[\;S \rightarrow aaSbSaaS\;|\;\epsilon\;]$, etc. would not be allowed.
e.g. $[\;S \rightarrow aSbSb\;|\;\epsilon\;]$, $[\;S \rightarrow aaSbSaxS\;|\;\epsilon\;]$, etc. would be allowed.

  The grammar cannot be made to break any of the above rules via a $S \rightarrow \epsilon$ production. (Vimal Patel)

  e.g. $[\;S \rightarrow aSbSaSbS\;|\;\epsilon\;]$ could become $[\;S \rightarrow abSabS\;|\;\epsilon\;]$ if the first and third $S \rightarrow \epsilon$, thus violating Rule 4.

Are (Context-Free) Grammars, that follow these 4 rules, always unambiguous? It would seem so. I really don't see any conceivable way that such Grammars could be ambiguous.

(Note: To show why Rule 4 is necessary consider the grammar $S \rightarrow aSbSa\;|\;\epsilon$ with the string $aababaababaa$. A visual derivation can be found here.)

I've spent a lot of time thinking about this question and have had a hard time finding any way of either proving or disproving it. I've tried showing that Grammars like these are $LL(1)$. However, it seems only Grammars of the form $S \rightarrow aSb\;|\;\epsilon$ are $LL(1)$. Grammars like $S \rightarrow aSaSb\;|\;\epsilon$ are not $LL(1)$. Maybe I need to use a higher $k$ for $LL(k)$?

(This question is a follow-up/reformulation of a previous question.)

I would really appreciate any help I could get here.


texts: Find a minimum-weight perfect b-matching, where b is even

texts:
How would one find a minimum-weight perfect b-matching of a general graph, where the number of edges incident on each vertex is a positive even number not greater than b?

A minimum-weight perfect b-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly b edges from M.


texts: Can we decide if a number is a power of any given $K$ in polynomial-time?

texts:
It is simple to decide powers of 2 in $O(n)$ time because it's just "0-bit Unary" after bit-1. (eg. $1000$ is a power of 2 in binary).
I haven't found many other trivial powers of $K$ that can be decided in polynomial-time with the binary-length of the input.
Question
Can we decide if a number is a power of any given $K$ in polynomial-time and in a practical amount of time?
Something not naive such as keep dividing $N$ by $K$ until you reach the smallest value $2$ for deciding a power of 2.


texts: $m/p$-equivalence holds after union with an arbitrary finite language

texts:
Problem 1: Let $A,B$ be languages over some alphabet $\Sigma$, if $A \equiv_m B$, then for every finite language $C$, $A \cup C \equiv_m B \cup C$.

Problem 2: Problem 1 but using polynomial time reductions.

Note: $A \equiv_m B$ means $A \leq_m B$ and $B \leq_m A$, same for $\equiv_p$. Every finite language can be decided in polynomial time.

By hypothesis, we have reductions $f$ from $A$ to $B$ and $g$ from $B$ to $A$, the obvious choice for a reduction from $A \cup C$ to $B \cup C$ would be: $$h(w) := \begin{cases} w &\text{ if } w \in C\\ f(w) &\text{ if } w \notin C \end{cases},$$ with this definition it follows that if $w \in A \cup B \Rightarrow h(w) \in B \cup C$, however, if $w \notin A \cup C$ I can't say that $h(w) = f(w)\notin B \cup C$, at most, $f(w) \notin B$.

My idea was to redefine $h$ like this:$$h(w) := \begin{cases} w &\text{if } w \in C\\ f(w) &\text{if } w \notin C \land f(w) \notin C\\ X(w) &\text{if } w \notin C \land f(w) \in C \end{cases},$$ where $X(w)$ must lie in $B \cup C$ when $w \in A \backslash C$, and outside $B \cup C$ when $w \notin A \cup C$. The problem now is how to define the mapping $X$, I can't ask whether $w \in A$ or not because $A$ may not be decidable (or decidable in polynomial time for problem 2) and here I'm stuck.

Can't see how to define $X$ without making questions about being in $A$ or $B$, those questions should be avoided because a $TM$ computing $h$ might loop forever. I'm starting to think that the problem needs some hypothesis like $A,B$ being decidable/decidable in polynomial time languages (the problem seems sound to me though, I can't find counterexamples to it).


texts: With a grammar, does precedence and associativity change the accepted language?

texts:
When parsing, certainly precedence and associativity effect the AST. But, do precedence and associativity alter the set of accepted sentences? In other words, can precedence and associativity be "ignored" (defined in some random precedence all associating left, say) in the grammar, and then the AST fixed later based on (possibly dynamic) precedence and associativity conditions?

I am concerned only with LL grammars and their common variants.


texts:
So when you are decrypting an encryption with modular arithmetic, I know the modulus operator (%) gives the remainder of a/b, but what if a is less than b?

For example, 5%2 is 1, since the answer is 2 remainder 1. But for something like 2%9, how do you find the answer?


texts: Converting maximization to minimization in aproximation algorithms

texts:
Suppose algorithm A is given for a maximization problem and we are asked to show that it is a 1/2-approximation algorithm.

As you know it is enough to show

Sol >= 1/2 OPT

What I need to know is, is it true to assume this problem as a minimization one and prove

Sol <= 2 OPT

Or is there any correspondence between these two?


texts: How does maths consistency impacts on computer science?

texts: Lot of mathematicians have made several efforts to answer the question : are mathematics consistent ? Although we haven't yet had a proof of consistency, and surely we will never (Gödel second theorem), does this question has an impact on computer science ? I mean, does the work of those mathematicians, like Gödel's theorems or formal deduction systems, shows new answers or new problems in computer science ? What would happen in computer science if, for example, we found a paradox in set theory ?


texts: QuickSelect with Median of Medians runtime

texts:
I know that Median of medians itself is $O(n)$.
With a good pivot, QuickSelect is $O(n)$, too -- but with a bad one, it's $O(n^2)$.
But if I now were to use the element gotten through median of medians as the pivot for QuickSelect, what would the new worst-case runtime of QuickSelect be? Would it be $O(n)$ guaranteed too?

Why would it not be $O(n\log n)$? I'm a bit confused, I guess. Since we have to choose the median of medians, which takes $O(n)$, for each subproblem, and we have $\log n$ subproblems (always recursing on one side of the median).


texts:
Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors.

I want to know about the exponential analogue, which would cover problems that can be decided in polynomial time using an exponential number of processors.

What I'm looking for is a name for this class and any known relations between this class and other complexity classes, or any canonical problems for the class. It seems straightforward that it would contain NP and co-NP, and i think it is contained within PSPACE, but I'm not sure much else about it.


texts:
I realized that almost no one explained how to selected the type variable T1

 Γ ⊢ e1 : T1 -> T  ,  Γ ⊢ e2 : T1
 -------------------------------- T-APP
 Γ ⊢ e1 e2 : T

when doing type checking (from bottom to top).

So, the question is how T1 is introduced? Is there any condition about T1?


texts: Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence

texts:
Suppose that sequence $A$ contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ and sequence $B$ contains $m$ integers $b_1,b_2,b_3,\ldots,b_m$. We know that $m \geq n$. We assume without loss of generality that both sequences $A$ and $B$ are sorted in ascending order.

What's the fastest algorithm to determine if there exists an integer $k$ such that the sequence $a_1+k,a_2+k,a_3+k,\ldots,a_n+k$ is a subsequence of the sequence $B$?

Here is a naive algorithm, which would take $O(n(m-n))$ time. Store the sequence $B$ as a hashtable. For each element $b_j$ of the $B$ (except the largest $n$ elements), use $b_j-a_1$ as your guess at $k$; you can verify this guess by checking whether each of $a_1+k,\dots,a_n+k$ are in the hashtable $B$. This takes $O(n)$ expected time per guess at $k$, and you make $m-n$ guesses, so in total the expected running time is $O(n(m-n))$. Can we do better?

I came across this problem while trying to match two binary images (testing whether one image contains the other).


texts: Minimum number of vertices whose removal makes the graph an independent set

texts:
It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W[1]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent set of size greater than equal to $k$.

I was looking at the complementary problem - "Whether or not removal of at most $k$ vertices from a graph can make the resulting graph an independent set".

  If the input graph $G$ contains a set $W$ of size at most $k$ for
  which $V(G)\setminus W$ is independent set, then it can be found in
  $2^{O(k \log k)}\cdot n^{O(1)}$ time as follows:

  Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
  There are now only $k^2$ edges in the current graph.
  Let $A$ be set of all vertices on which at least one edge is incident, then $V(G)\setminus A$ is an independent set of size at
  least $(n-2k^2)$.
  So $W$ must be contained in set $A$ whose size is at most $2k^2$. We can scan over all ${2k^2}\choose{k}$ subsets of A to check removal
  of which set makes the graph an independent set.

My question is does the new problem has $2^{O(k)}\cdot n^{O(1)}$ time algorithm?


texts: How DMA improves I/O operation efficiency?

texts:
I am reading Computer Architecture & Organization by William Stallings to understand I/O operations. Stallings pretty well explains why Programmed I/O (CPU keeps checking the I/O module register status) & Interrupt I/O (CPU still has to over look data transfer between I/O module & memory) are not efficient & introduces to DMA, where DMA itself handles everything.

But, however, he also mentions that during a DMA operation, CPU sits idle & has no control over memory bus. If CPU has to sit idle, then how it is better than other two methods ?

Page no. 415, Computer Architecture & Orgazination by Morris Mano:

  During the DMA transfer, the CPU is idle and has no control of the memory.

Only way it make sense to me is that, CPU can perform any operation which does not involve memory bus during a DMA operation. So, CPU will not be idle. Or am I missing something ?

I think author has formulated in a bad way. It can be phrased like:

  During DMA transfer, the CPU has no control of memory buses and thus cannot perform any operations involving memory. However it can perform other operations like arithmetic, logical or can operate on data in cache.

Am I right?


texts: Making a NFA for accepting a string only if it contains the given substrings

texts:
First I'll introduce the problem with just two substrings. Say you are asked to construct a NFA which accepts the input string if it has both "bb" and "aba" as substrings.

The solution we came up with in class was that we'll make a NFA with multiple start states (a start state with $\epsilon$-transitions to each of our desired multiple start states). We'll have two cases, one where the substring "aa" occurs before the substring "aba" and one where the substring "aba" occurs before the substring "aa".

Following is the NFA diagram:

But the problem with that solution is that it doesn't generalize well (for example, now if I have to check that the given string contains 10 given strings as substrings, if I have to make a branch for every permutation, I'll have 10! branches).

Is there a simpler solution to this where the complexity of the NFA to be drawn does not increase as factorial of the number of substrings?


texts: Algorithm to find nodes with given a distance

texts:
We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between individual confluences and distances between piers and confluences on any particular river segment.

How would we algorithmically find if there exist piers, that are distance $X$ from each other? ( They need to be in the same stream)

The red dots are the piers.

This is a homework problem I can't solve, so hints are welcome.

What i am considering.

Checking individual stream until the distance between the first and furthest pier is bigger than the given distance, then backtrack and go left on the confluence, basically use DFS, but then i can't quite grasp the recursion behind it.

Will keep updated if i move somewhere.

What i considered.

 Let's begin at the start of the river, we check if there is a pier on the closest 2 segments, let's say there is one, we pass it and arrive at the second confluence, again we explore and check if we have the correct distance if there are any piers, if there are and if it's the distance X we are done, if the distance is too large, we enqueue pier 1 and start anew at current spot, if the distance is not sufficient we can enqueue, we can move forward and check again, if the distance is too large, we can dequeue a pier  either continue or dequeue again...

This algorithm would just always choose the only one river turn, if the river is endless and there exists such a pair of piers on that particular stream, it would find it.
But i can't figure out a way of searching all the streams simultaneously.

Another Idea is to create sets of pier distances sort them and greedily try to combine them to get the distance, but there are too many streams so it would be ineffective again..


texts: How to find corresponding points between two photos when there's a repeated pattern?

texts:
Suppose that I have two photos, I1 and I2 and I want to find a set of corresponding points between the two photos to define a homography between them. There are many algorithms for this purpose, namely SIFT which is scale invariant. The problem is that when there's a pattern in both photos (like repeated windows), SIFT starts to fail and most of the corresponding points it gives are false and outliers. So, what can I do in cases like these?

How can I avoid this problem? Are there other algorithms that behave better when there's a pattern in both photos?


texts: Equally optimal nodes during minimax with alpha-beta pruning

texts:
Alpha-beta pruning is an optimization for minimax that reduces the number of nodes visited without changing the final result. However, both minimax and alpha-beta only return the optimal node value (not the optimal node itself), which means that in practice, a programmer must implement a method for identifying which of the root's children corresponds to the optimal value. For example, the results of the search may be stored in a tree structure that associates nodes with their values. The root node's optimal child can then by identified by finding the child whose value is the same as the root's value.
The return value of both alpha-beta and minimax should be independent of the order in which nodes are visited. However, in practice, multiple sibling nodes may have the optimal value, so we must implement a method for choosing between equally optimal children of the root. There are two main ways to do this:

With both algorithms, we can break ties in a way that depends on the order in which nodes were visited, for example by choosing the first or last optimal child that was visited.
With minimax, we can break ties in a way that is independent of the order in which nodes were visited, for example by choosing the optimal child whose bitboard representation is smallest.

Now, here is the crux of my question: Is it correct that alpha-beta terminates the search after finding an optimal child? If so, this would mean that there may be other optimal children that will not be identified by the search. If this is the case, then am I correct in thinking that with alpha-beta pruning, it is impossible to break ties between optimal nodes in a way that is independent of the order in which nodes are visited?
If this is correct, then it would mean that changing the order in which nodes are visited during alpha-beta search (for example, by visiting the more promising nodes first) will affect the moves chosen by a game engine, because it will affect which node the engine identifies as optimal at each game position. (This is not a problem, but it seems like something to be aware of when implementing and testing a game engine that uses alpha-beta pruning.)


texts: Should names of built-in funtions be part of BNF grammar?

texts:
We're creating our own programming language for a subject. And we're confused whether to add the names of the functions we want to have in our language (like our own version of print) in the BNF grammar.

Reserved words should be recognized by the lexer, right? How about function names?


texts:
I am reading the book: "Code: The Hidden Language of Computer Hardware and Software"  and in Chapter 2 author says:

  Morse code is said to be a binary (literally meaning two by two) code
  because the components of the code consists of only two things - a dot
  and a dash.

Wikipedia on the other hand says:

  Strictly speaking it is not binary, as there are five fundamental
  elements (see quinary). However, this does not mean Morse code cannot
  be represented as a binary code. In an abstract sense, this is the
  function that telegraph operators perform when transmitting messages (see quinary).

But then again, another Wikipedia page includes Morse Code in 'List of binary codes.'

I am very confused because I would think Morse Code actually is ternary. You have 3 different types of 'possibilities': a silence, a short beep or a long beep.

It is impossible to represent Morse Code in 'stirct binary' isn't it?

By 'strict binary' I mean, think of stream of binary: 1010111101010.. How am I supposed to represent a silence, a short beep and / or a long beep?

Only way I can think of is 'word size' a computer implements. If I (and the CPU / the interpreter of the code) know that it will be reading 8 bits every time, then I can represent Morse Code. I can simply represent a short beep with a 1 or a long beep with a 0 and the silences will be implicitly represented by the word length.(Let's say 8 bits..) So again, I have this 3rd variable/the 3rd asset in my hand: the word size.

My thinking is like this: I can reserve the first 3 bits for how many bits to be read, and last 5 bits for the Morse code in a 8bit word. Like 00110000 will mean 'A'. And I am still in 'binary' BUT I need the word size which makes it ternary isn't it? The first 3 bits say: Read only 1 bit from the following 5 bits.

Instead of binary, if we use trinary, we can show morse code like: 101021110102110222 etc.. where 1 is: dit 0 is: dah and 2 is silence. By using 222 we can code the long silence, so if  you have a signal like *- *---    *-  you can show it like: 102100022210, but it is not directly possible using only with 1's and 0's UNLESS you come up with something like a 'fixed' word size as I mentioned, but well this is interpreting, not saving the Morse Code as it is in binary. Imagine something like a piano, you have only the piano buttons. You want to leave a message in Morse Code for someone and you can paint buttons to black. There is no way you can leave a clear message, isn't it? You need at least one more color so you can put the silences (the ones between characters and words. This is what I mean by trenary.

I am not asking if you can represent Morse Code in 57-ary or anything else.

I have e-mailed the author (Charles Petzold) about this; he says that he demonstrates in Chapter 9 of "Code" that Morse Code can be interpreted as a binary code.

Where am I wrong with my thinking? Is what I am reading in the book, that the Morse Code being a Binary a fact or not? Is it somehow debatable? Why is Morse Code is told be quinary in one Wikipedia page, and it is also listed in List of Binary Codes page?

Edit: I have e-mailed the author and got a reply:

-----Original Message-----

From: Koray Tugay [mailto:koray@tugay.biz]

Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

From: "Charles Petzold"

To: "'Koray Tugay'"

Subject: RE: Is Morse Code really binary? Date: 3

Mar 2015 23:04:35 EET

Towards the end of Chapter 9 in "Code" I demonstrate that Morse Code can be interpreted as a binary code.

-----Original Message-----

From: Koray Tugay [mailto:koray@tugay.biz]

Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

I am not hiding his e-mail as it is really easy to find on the web anyway.


texts: When does Gaussian elimination solve exact 1-in-3 SAT?

texts:
Terms:

A literal is a variable or its negation.

A clause is a set of literals.

An exact 3-in-1 clause is satisfied if an assignment of values to variables results in exactly 1 true literal and 2 false literals.

Exact 3-in-1 SAT is the problem, given a set of exact 3-in-1 clauses, is there as assignment of variables that satisfies all clauses?

Question:

This corresponds to a linear algebra problem, sort of:

Let true be 1 and false be -1.

For each variable v and its negation w, add the equations:

v + w = 0

(This is because 1 + (-1) = 0)

For each exact 3-in-1 clause (a b c), add the equations:

a + b + c = -1

(This is because two -1's and one 1 will add up to -1.)

It's possible solving the equations results in a value other than 1 or -1. However if the solution to the system of equations is only 1 and -1, I suspect that's a valid solution to the original exact 1-in-3 problem.

So, when does Gaussian elimination solve exact 1-in-3 SAT?

Here's an example when it does:

These clauses:

(1 2 3)
(2 3 -2)
(2 3 -3)

Correspond to this matrix:

1, 0, 0, 1, 0, 0, 0
0, 1, 0, 0, 1, 0, 0
0, 0, 1, 0, 0, 1, 0
1, 1, 1, 0, 0, 0, -1
0, 1, 1, 0, 1, 0, -1
0, 1, 1, 0, 0, 1, -1

Reduced row echelon:

1, 0, 0, 0, 0, 0, 1
0, 1, 0, 0, 0, 0, -1
0, 0, 1, 0, 0, 0, -1
0, 0, 0, 1, 0, 0, -1
0, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 0, 1, 1

Therefore solution (via far-right column) is: (1 -2 -3)

Does this always work on larger matrices with 2*n rows and 2*n+1 columns where n is the number of variables? (I think it may need non-redundant (linearly independent?) rows.)


texts: Sorting when there are only O(log n) many different numbers

texts:
We have $n$ integers with lot's of repeated numbers. In this list, the number of distinct elements is $O(\log n)$. What's the best asymptotic number of comparisons for sorting this list?

Any idea or hint or pseudo code? In fact I want to learn pseudo code.


texts: Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?


texts: "The Annotated Turing" on listing all binary numbers between 0 and 1

texts:
In his book "The Annotated Turing" in the first sentence on page 32 Charles Petzold wrote:

These are binary numbers between 0 and 1, and (judging from the way we
created these numbers) all the binary numbers between 0 and 1, and
hence all the real numbers between 0 and 1.

And then at the bottom of the page there is a note:

It may also seem as if we've stumbled on a method to enumerate all the
real numbers between 0 and 1...

Followed by a brief explanation of why we really have not.
These two sentences contradict each other. The first one says we've made a list of all real numbers and the bottom note says we have not. So I have to questions regarding this:

Is it a mistake or am I getting something wrong?
If we have not listed all the real numbers between 0 and 1, then what have we listed?


texts: Gaussian Process doubt for machine learning

texts:
How to find hyperparameters (in Gaussian Process) by log marginal likelihood.
Suppose we have mean function as $m=ax^2 +bx + c$.
so we have $hyperparameters = \{a,b,c,sigma_y,sigma_n,l\}$;
How we calculate all these parameters by log marginal likelihood and by partial derivatives?


texts: Is Turing machine a programmable machine or Is it like a fixed program computer?

texts: We all know Random Access Machine (RAM) models are programmable machines. We can program a same machine for different problems with the help available instruction set. But in the case of Turing machines,we give full description of TM including transition table (which is equivalent to stored program in RAM model). So should it be considered like a stored program computer? Because for two different languages L1 & L2 we give two different TMs T1 & T2. We never describe two different transition table for same TM.


texts: You are in a xy plane with a set of points F. You also have a collection P of N sets { P1,...., Pn} where each of the set consist of points of the form (Px,Py). Each set has a different number of points. The problem is given a value k and a distance D, find points existing in F which are within D distance of any point in Pk. What is the optimal way of solving this?


texts: Is grammar S→aaab | aab in LL(2) but not SLL(2)?

texts:
I'm trying to figure out how to create grammars which are LL(k) and not SLL(i).

Is this grammar LL(2) and not SLL(2)?

$S \to aaab \mid aab$

Where S is a starting symbol. I think it is not SLL:

FIRST$_2$(aaab) is FIRST(aab)

And I think that it's LL(2) and LL(1) too because there are no non-terminal symbols which could cause conflict.

Is it true?


texts: Is the shadow ray in a Whitted ray tracer occluded by transparent objects?

texts:
In a Whitted ray tracer, each ray-object intersection spawns a transmitted ray (if the object was translucent), a reflected ray and a shadow ray. The shadow ray contributes the direct lighting component.

But what happens if the shadow ray intersects a transparent object? Is the direct lighting component ignored? How will diffuse objects submerged in water be lit if they don't get any direct light contributions from the shadow ray?


texts: Is the difference between between an union and a product of two DFA lies in their accepting states?

texts:
It seems to me that in order to construct the union and the product of two DFA we use basically the same method.

The difference is that when we make the accepting states for the resulting DFA. Suppose $A_{1}$ an DFA with $F_{1}$ as an accepting state, and $A_{2}$  an DFA with $F_{2}$ as an accepting state. In the case of an union of $A_{1}$ and $A_{2}$, the accepting states have either $F_{1}$ or $F_{2}$ or both, and in the case of a product, the accepted state is {$F_{1},F_{2}$}. Am I correct?


texts: Are there connections between the theory of computation and machine learning?

texts: I am wondering if studying the Theory of Computation/ Computational Complexity theory, specifically Sipser's 'Introduction to the Theory of Computation' will help me do machine learning/statistics/data science better. Are there any connections? I intend to study the book even if there aren't any connections.


texts: Why is 2s complement of 000 equal to 111, but 9s complement of 000 is not 888?

texts:
I'm pretty confused so I hope I don't mix up the different terms here.

The two's complement representation of decimal 0 is simply 000

The two's complement of 000 is 111

I imagine that complementing a number is equivalent to flipping bits in binary

The nine's complement of 000 is 999

This is what confuses me. Are two's complement and nine's complement similar (except for the base change obviously)?
If they are, then I'd expect the nine's complement of 000 to be 888 because 8 is the biggest digit in radix 9 and therefore the complement operation would assign the highest digit (8) to the lowest value input (0) [I imagine a folding from the center]

Obviously this is totally wrong but I'm not sure which part I've misunderstood.


texts: A pumping lemma for deterministic context-free languages?

texts:
The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove that certain languages are not context-free.

Is there a pumping lemma for deterministic context-free languages?  That is, is there a lemma akin to the pumping lemma that can be used to show that a language is not a DCFL?  I'm curious because almost all of the proof techniques I know to show that a language is not a DCFL are really complicated, and I was hoping that there was an easier technique.


texts: Canadian traveller problem on directed acyclic graphs

texts: What is the complexity of the Canadian traveller problem  variant where the only thing that is seen is a single node ahead on a directed acyclic graph so that we cant go back once we go to a new node and there are some nodes that have a probability associated and we dont know the probability of others?


texts:
I am not sure this is the right forum to ask.

For a machine learning training, I need a dataset of old top news by keywords that can be organized by date. From where I can download it? I have seen that Google News API can provide only real time news.


texts: Why can we assume an algorithm can be represented as a bit string?

texts:
I am starting read a book about Computational Complexity and Turing Machines. Here is quote:

  An algorithm (i.e., a machine) can be represented as a bit string once
  we decide on some canonical encoding.

This assertion is provided as a simple fact, but I can't understand it.

For example, if I have an algorithm which takes $x$ as input and computes $(x+1)^2$ or:

int function (int x){
   x = x + 1;
   return x**2;
}

How that can this be represented as string using alphabet $\{0, 1\}^*$?


texts:
I am quite new to Red-Black trees, and therefore I am having a bit of difficult time trying to understand them.

One of the properties of the Red-Black tree is that every red vertex must have two black children, meaning one cannot have two consecutive red vertices.

Can someone explain to me why this is an essential property? What are the benefits of having such a property?